网络能量受限的路由控制策略范文

《电子科技大学学报》2015年第二期

1网络模型

假设网络中有N+1个节点，最后一个节点称为目的节点D，前N个节点可以产生消息。简单起见，假设其中的一个节点(称为信息源S)产生消息m，其他N−1个节点称为中转节点。采用离散时间模型，每个时间间隔(称为时隙)为θ，第t个时隙是指时间区间[tθ,(t+1)θ]。信息源在第一个时隙开始产生消息m，m的最大生存周期为T(T个时隙)。对于任意两个节点i和j，它们之间的边为eij。eij=1表示节点i和j处于连接状态，可以相互通信；eij=0意味着二者处于断开状态。网络中任何一条边的状态转换关系如图1所示。本文采用概率two-hop算法，即信息源在每次遇到中转节点时不是绝对发送，而是以一定概率进行发送，以p(t)表示在第t个时隙所采取的概率。该概率可称为发送概率或发送策略，它是一个随机序列[9]，在任意时刻都可以看做一个随机变量，如在第t个时隙，p(t)就是随机变量，可以在[0,1]中任意取值。下面首先给出阈值概率的定义。需要注意的是，这里的发送概率主要是指信息源与中转节点之间的发送概率。而任何携带消息的节点(包含S)都以概率1向目的节点D发送消息。

2系统建模

假设在第t个时隙末携带消息的节点数为X(t)，E(X(t))表示对应的期望值。进一步假设每一个接受消息的节点只能在下一时隙才能进行转发，且消息足够小从而能够在一个时隙内完成传输，显然X(0)=1。因为路由策略的能量消耗与转发次数成正比，为简单起见，直接利用转发次数作为能量消耗的指标[9-12]。采用类似的方法，即用X(t)表示从时刻0到第t个时隙总共消耗的能量值。令F(t)表示在第t个时隙传输成功的概率(目的节点D得到消息)。如果限定为传输一条消息，允许消耗的最大能量为δ，则存在问题。

3最优控制策略

对于阈值概率，结合式(6)和式(8)，有。根据定理1，可以得出最优阈值概率。定理1最优阈值h*存在。证明：给定两个阈值h1<h2，其对应的期望值为1hE(X(t))和2hE(X(t))，根据式(12)可知，1hE(X(t))=2hE(X(t))，t<h1；1hE(X(t))<2hE(X(t)，t≥h1。根据文献[11]随机序列的定义，1hE(X(t))和2hE(X(t)都是随机序列，进一步结合式(11)可知，1hF(T)<2hF(T)，所以F(T)是h的单调递增函数。结合式(12)可知E(X(t))及F(T)都是h的单调递增函数。最优阈值h*可以按下述过程得到：1)h=1，sum=E(X(1))，如果sum<δ，转步骤2)，否则h*=h−1，进一步根据式(12)可以得出p(h)的值；2)h=h+1，sum=E(X(h))，如果sum<δ，转步骤2)，否则h*=h−1，进一步根据式(12)可以得出p(h)的值。如果h=T+1，则h*=T+1。下面证明最优概率是阈值形式。在证明之前，先给出随机序列的相关定理。定理2[9]给定两个随机序列x1和x2，则x1小于x2，记作x1<stx2，如果它们满足x1(t)≤x2(t)，t≥0；且至少存在一个常数c≥0，x1(t)<x2(t)。设f(x)是随机序列x的函数，如果两个随机变量x1<stx2且f(x1)<f(x2)，则f(x)是随机序列x的递增函数。定理3最优概率是阈值形式。证明：显然，发送概率是随机序列，而E(X(t))是对应的随机函数，令fpE(X(t))表示发送概率pf对应的E(X(t))。给定两个发送概率p1和p2，其在第t个时隙对应的值分别为p1(t)和p2(t)。存在一个常数c，满足：t≠c，p1(t)=p2(t)，t=c，p1(t)>p2(t)，0<c≤T。从定理3可知p2<stp1。下面证明E(X(t))是发送概率的递增函数。以ζi(t)代表节点i从时刻0到第t个时隙是否得到消息的指示变量，为1则指已经得到消息；为0则表示没有得到消息。

4性能分析

4.1仿真实验首先，采用机会网络仿真平台(opportunisticnetworkenvironmentsimulator,ONE)验证理论模型的正确性。因为采样周期越长，连接失败及短连接时间的边消失的概率就越大，这要求数据集具有较短的采样周期，本文选用Rollernet数据集[16]，其采样周期约为12s，比传统的RealityMining的600s及Infocom2005[18]的120s都要短。利用前3000s的数据，并且选取60个节点，连接平均持续时间为26.18s，节点平均度为4.75，由此可以得到α=0.05，β=0.57。如图2所示，令T从1增加到10，分别给出了δ=10和5时的结果。从图2可以看出，理论结果与实验结果非常接近。当δ=10时，平均误差为3.87%；δ=5时，平均误差为3.26%。这说明本文模型非常精确。下面不进行过多的仿真验证，只是通过数值结果对模型进行深入探讨。

4.2性能评估下面通过数值结果来说明最优策略是阈值策略，且利用仿真试验中的数据集。首先针对消息最大生存期T的变化进行探讨，假设T从1增加到20，且令δ=10。为了说明阈值策略的优越性，给出了随机策略所对应的理论结果。随机策略是指在每一步信息源都从[0,1]范围内随机选择发送概率。同样也给出了p(t)恒为1时的结果，实际上此时无能量限制，信息源始终以概率1发送。从图3可以看出最优阈值概率明显优于随机概率，且与无能量限制的时候非常接近，只在中间部分有一定的差别。这是因为当消息生存期较小时，最优阈值h*几乎等于T，即信息源始终以概率1发送；当T较大时，即使最优阈值h*小于T，由于有充足的时间来完成传输，其性能同样接近与发送概率恒为1的时候。但当T处于中间位置时，最优阈值h*小于T，因此中转节点得到消息的概率较小，且由于消息生存期不大，没有充足的时间来完成传输，此时最优阈值概率会稍小于无能量限制的情形。图4显示最优阈值策略明显优于其他策略。由于DTN网络通信的不可靠性，传输延迟可能比较大，所以DTN网络路由的主要指标就是尽可能提高传输成功率。但传输成功率的提高往往需要较多的副本，从而消耗更多的能量。下面探讨对于不同的传输成功率所消耗的能量。假设传输成功率从10%增加到100%，数值结果如图5所示。图5显示出随着传输成功率的增加，最小能量不断增加。此外，如果消息的有效期较长，则也可以用较少的能量来满足需要。

5结论

利用Edge-Markovian模型描述DTN中节点之间的连接关系，并研究了能量约束条件下two-hop算法的最优控制问题。首先通过离散时间Markov过程对算法的消息传播过程进行建模，在此基础上证明了最优发送概率必须服从阈值形式，并且给出了计算最优阈值策略的定理。仿真实验证明了模型的正确性，数值结果说明最优阈值概率优于随机概率。

作者：吴亚辉邓苏黄宏斌单位：国防科技大学信息系统工程重点实验室