无线传感网络中基于功率控制的机会路由设计

郝 军， 贾新春， 师晓东， 韩宗源， 杨 波



无线传感网络中基于功率控制的机会路由设计

郝 军1， 贾新春1， 师晓东1， 韩宗源2， 杨 波1

(1.山西大学 数学科学学院， 山西 太原 030006； 2.中国铁道科学研究院 电子计算技术研究所，北京 100081)

传感器节点的能量有限性与无线链路的不稳定性，使得无线传感器网络中的路由设计成为一个具有挑战性的问题.机会路由利用无线链路的广播特性，可容许多个候选节点机会地参与数据包转发，从而提高网络吞吐量.通过马尔科夫链来建模机会路由，得到了影响候选节点选择的两个关键路由度量：ExNT与EEC.结合功率控制技术，研究发射功率对这两种路由度量的影响，设计相应的候选节点选择算法，进一步给出基于功率控制的机会路由协议(PCOR)的具体执行过程，并在网络模拟平台NS2中仿真实现.通过与其它几种典型机会路由协议的对比分析，验证了该协议在提升整体网络性能的同时，可以有效降低网络的总能耗.

无线传感器网络； 机会路由； 马尔科夫链； 功率控制

0 引言

无线传感器网络是一种具有良好的信息采集、处理和传输能力的新型分布式网络，并被广泛应用于环境监测、军事应用、医疗护理等领域.然而，物理环境因素与节点的有限能量严重影响无线链路质量，难以保证信息的可靠传输.同时，频繁的路由构建与大量的数据重传也给路由协议的设计和优化带来了困难[1].因此，如何针对无线传感器网络设计一套合理的路由策略，来减少较差链路质量引起的数据包重传，同时降低节点的能量消耗是很有必要的.

机会路由是由Sanjit Biswas等人提出一种新的路由策略[2].不同于传统路由中预先选择单个特定节点作为下一跳转发者，机会路由充分利用无线链路广播的特性，通过选择一组候选节点来进行数据包的转发.转发节点选择的多样性使得机会路由可以更好的适用于能源有限且链路质量较弱的网络场景中，并且可以提高数据包传输的可靠性，减少数据包重传引起的不必要能量消耗.

路由度量的选择是机会路由中候选节点选择算法的关键因素.早期的研究工作延续了传统路由的思想，利用物理距离、传输时延、ETX等路由度量来设计相应的数据转发机制[3,4].然而，文献[5]证明基于传统路由度量的机会路由并不能找到合适的候选节点，甚至会退化网络的性能.文献[6]中提出的任意路径期望传输次数 (Expected Any-path Transmission,EAX)充分考虑了数据传输过程中的多条潜在路径，被广泛用于机会路由的设计当中.然而，EAX的递归特性与繁琐的运算过程使得候选节点选择算法的时间复杂度较大，并不适应于大规模的动态传感器网络.

与此同时，功率控制作为解决能耗问题的主要手段，同样被用于机会路由的设计当中[7-9]. 其中，文献[7]通过定义基于能耗的路由度量，设计了一种功率可调的机会路由协议EEOR，使得网络中所有节点的能量消耗最小化.文献[8]则结合休眠唤醒机制，提出了基于功率控制的协同机会路由来提升数据包的转发效率.然而，上述文献只考虑通过调节节点的发射功率来降低网络能量消耗，而没有考虑到节点功率变化对候选中继节点选择多样性的影响，即降低节点功率通常以减少链路选择多样性为代价，而较少的候选节点个数则会导致单跳数据包重传次数以及端到端时延的增加.

针对上述问题，本文利用马尔科夫链来建模机会路由中数据包转发过程，并给出影响候选节点选择的两个关键路由度量：期望传输次数(Expected Number of Transmissions,ExNT)与期望能量消耗(Expected Energy Consumption, EEC).研究发射功率分别对这两种度量的影响，设计了基于最优发射功率的候选节点选择算法，并给出基于功率控制的机会路由协议PCOR的实现步骤.最后，在网络仿真软件NS2中将PCOR与其它几种典型机会路由进行对比分析，验证所提协议的有效性.

1 网络模型与假设

1.1 网络模型

考虑一个由N个节点组成的无线传感器网络，传感器节点被随机部署且具有各自编号，其中标号为1的节点为源节点，标号为N的节点为目的节点，其余为中继节点.假设每个传感器节点具有调节发射功率Pt的能力与相同的最大发射功率Pt-max，相应的最大通信半径定义为Rmax.任意两节点i与j间的物理距离记为di,j，故di,j≤Rmax时两个节点能够直接通信.此时，无线网络可利用一个拓扑图G=(V，E)表示，其中V={1,2,…,N}为N个传感器节点构成的顶点集，E={|0∈E,∀j∈V}为节点i的邻居节点集.

在机会路由中，数据包通过多跳以前向无环路的方式由源节点传向目的节点.节点i从其邻居节点中选择若干节点组成候选节点集CS(i)={ci(1),ci(2),…,ci(|CS(i)|)}，其中ci(m)表示节点i的优先级为m的候选节点，|·|表示集合元素个数.成功接收到节点i发送数据包的候选节点间根据预先给定的优先级彼此协调，确定唯一的节点来转发该数据包.该过程将一直重复，直到数据包成功到达目的节点.

1.2 能耗模型

鉴于无线传感器节点的有限能量资源，路由协议在满足数据高效传输的同时，必须考虑节点的能量消耗以及网络的能量均衡.本文采用文献[10]中的经典能耗模型来刻画无线传感器网络中数据包转发与接收过程中的能耗情形.针对发送者与接收者间不同的距离，分别使用自由空间与多路径衰减信道模型来描述功率的损耗.这样，节点i节点j发送数据时的能量消耗为：

(1)

传感器节点接收lbit数据时的能量消耗为：

ERx=l·Eelec

(2)

1.3 数据包成功转发概率

在无线通信过程中，影响无线链路质量的两个主要因素有：路径损耗与阴影衰落.发射功率的辐射扩散及信道的传播特性都会造成功率的损耗，且一般认为对于相同收发距离，路径损耗相同；而阴影衰落由发送者和接收者之间的障碍物造成[11].由于信号在无线信道传播过程中遇到的障碍物会使信号发生随机变化，从而造成接收信号功率的随机变化，因此本文采用对数正态阴影模型来描述这些因素造成的信号随机衰减.在这个模型中，距离d处的接收功率Pr(d)为：

Pr(d)dBm= Pt dBm-PL(τ)dB-

(3)

其中,Pr(d)与Pt分别是单位为dBm的接收功率与发射功率，PL(τ)为依赖于天线特性与平均信道损耗的系数，τ为天线远场参考距离，γ为路径损耗指数，随机变量ψdB服从均值为0、标准差为σdB的正态分布.

通常，接收功率大于一定的阈值PRTX时，数据包才能成功地转发.使用上述模型，距离为d且发射功率为Pt时的无线链路中数据包成功转发概率为：

p(Pt,d)=Prob(Pr(d)≥PRXT)=

(4)

其中，Q为标准正态随机变量x大于z的概率函数：

(5)

2 路由度量的计算与分析

2.1 基于马尔科夫链的建模

在机会路由中，源节点发出的数据包可以随机地被多个候选节点转发，且路由决策是在候选节点接收到数据包后根据当前的网络信息进行的，不受之前节点的影响，直到达到目的节点.这种数据传输的行为具有一定的无后效性，因此可以利用吸收态马尔科夫链来建模机会路由中数据的传输过程[12].如图1所示，节点{1,2,…,N-1}都可作为过渡状态.节点i在自身产生或接收到来自其它节点的数据包时，会将其立即转发给候选节点集CS(i)，当候选节点ci(m)成功接收并转发该数据包时，可视为状态i到状态ci(m)的一次转移；若CS(i)中的节点都接收失败，则节点i会重新发送数据包，这被认为状态转移到了自身.由于网络中的数据到达目的节点N后就不会被再次转发，因此节点N可作为马尔科夫链中的一个吸收状态.

图1 机会路由下的吸收态马尔科夫链

在机会路由中，源节点以广播形式发送数据包，候选节点以优先级依次转发，直到数据包成功到达目的节点.基于这一思想，可进一步求得上述吸收态马尔科夫链的一步转移概率矩阵Q=(qi,j)N×N.当i∈{1,2,…,N-1} 为过渡状态时，它到其它状态及自身的一步转移概率可由公式(6)给出：

(6)

其中,pi表示候选集CS(i)中所有节点都接收失败时节点i的重传概率，pi,ci(m)=p(Pt(i),di,ci(m))为节点i以功率Pt(i)成功转发数据包到其候选节点ci(m)的概率，可由公式(4)计算得到.针对吸收状态N，其一步转移概率为：

(7)

结合公式(6)与(7)，观察转移概率矩阵Q可得：Q为准上三角矩阵，可简写为公式(8)的形式.

(8)

其中，M∈R(N-1)×(N-1)表示N-1个过渡状态之间的转移概率矩阵，S∈R(N-1)×1为过渡状态到吸收状态的转移概率.

引理1[13]对于任意吸收态马尔科夫链，I-M可逆且满足：

(9)

其中，I为适当维数的单位矩阵，且定义F=(I-M)-1为马尔科夫链的基础矩阵.

2.2 期望传输次数

在无线传感器网络中，数据包的传输次数是衡量路由协议的一个重要度量.鉴于机会路由中数据包转发的随机性，本文利用马尔科夫链的相关性质从数学期望的角度来研究源节点成功发送数据包至目的节点的期望传输次数ExNT.设随机变量Xi为状态i成功转移到吸收态N的转移次数(i=1,2,…,N-1)，利用公式(8)，可得从过渡态i出发经过h步到达吸收态N的转移概率：

p[Xi=h]=(Mh-1×S)i

(10)

此时，节点i发送数据包到达目的节点所需的ExNT由转移次数Xi的期望值得到.结合公式(10)与引理1，节点i的期望传输次数ExNT(i,Pt(i))计算如下：

(11)

注意到，期望传输次数ExNT(i,Pt(i))的计算是基于数据包成功到达目的节点这一事件，公式(11)的分母(F×S)i表示了状态i成功转移到吸收态N的条件概率.此外，由于目的节点不再继续转发数据包，定义ExNT(N,Pt(N))=0.

相比于机会路由中通常使用的路由度量ETX与EAX，通过马尔科夫链建模所得的ExNT，给出了节点发送数据包成功到达目的节点所需的期望传输次数的闭合表达形式，避免了传统度量中的递归运算，极大地降低计算复杂度，适用于候选节点的选择与排序算法.

2.3 期望能量消耗

能量受限一直是无线传感器网络中的关键问题之一，也是路由设计时不得不考虑的因素.这里给出机会路由中期望能量消耗EEC的表达式，既可用于候选节点选择算法，又可以评估相应路由协议的性能.考虑节点i发送数据包到达目的节点N这一过程的期望能量消耗，主要分为两部分：(1)节点i以广播的形式发送数据包到其候选节点；(2)候选节点集CS(i)中的节点作为新的发送者向目的节点N转发数据包.

假设候选节点间接收数据包的事件是相互独立的，则节点i广播一次数据包，其候选节点集CS(i)中至少有一个节点接收到的概率为ρ=1-pi，这就意味着数据包到达候选节点集所需要的期望传输次数为1/ρ，广播一个数据包相应的能量消耗可由公式(1)得到.在节点i发送数据包给其候选节点集这一过程中，除了节点i以功率Pt(i)广播数据所需要的能量，同时也要考虑候选节点接收数据包所消耗的能量，可借助公式(2)以期望的形式获得.因此，这一过程中的期望能量消耗Cb(i,Pt(i))可如下计算：

(12)

设Cf(i,Pt(i))为候选节点集CS(i)作为一个整体向目的节点N转发数据包所需要的期望能量消耗.在机会路由中，优先级最高且接收到上一阶段数据包的候选节点将率先转发这个数据，不然优先级次之的候选节点转发.这就意味着，若节点j转发该数据包，当且仅当j成功收到该数据包且优先级比它高的所有候选节点都接收失败.类似于文献[6]中EAX的表达形式，此阶段的期望能量消耗是基于候选节点集中至少有一个节点收到数据包这一事件，因此Cf(i,Pt(i))的表达形式如下：

Cf(i,Pt(i))=

(13)

最后，结合公式(12)和(13)，节点i以功率Pt(i)发送数据包到达目的节点N所需的期望能量消耗为：

(14)

3 机会路由的研究与设计

3.1 最优发射功率

无线链路质量会随着距离的增加而大幅度衰减，选择远处的候选节点会导致数据传输的不可靠性，而发射功率可有效改善数据包成功转发概率与候选节点的数目.发射功率的增加使得更多的节点参与到数据包的转发过程，源节点向目的节点转发数据的期望传输次数ExNT逐渐降低，但是节点发送数据包所消耗的能量也随之增大，极大地影响整个网络的能量消耗.因此，如何调整发射功率来合理地选择候选节点，使得机会路由的设计在提升整体网络的性能的同时降低网络的总能耗是本文主要研究的问题.

这里通过对ExNT与EEC两种度量归一化处理后加权求和，为每个节点定义一种新的综合度量α(i,Pt(i))：

(15)

其中，λ∈[0,1]为权重因子，可根据网络应用的需求来确定.通过对ExNT与EEC理论分析可得：当节点调整其发射功率，使得候选节点数目恰好为1时，ExNT达到最大，即ExNTmax(i)针对节点i来说是一个常值；同样地，当节点的发射功率取到最大值Pt-max时，相应的EEC也达到最大.

(16)

然而，考虑到微分方程组求解的计算复杂度与传感器节点硬件的约束，上述最优发射功率的理论求解方法并不适用于能源有限的大规模无线传感器网络.在本文中，通过对节点的发射功率进行分层，为每个传感器节点设计了一种分布式候选节点选择算法，使得节点所选取的发射功率尽可能地逼近最优情形.算法的伪代码如下：

α(i)=∞,CS(i)=Ø;

for (l=1;l≤K;l++)

Pt(i)=Pt_max/K×l;

αl(i)=α(i),CSl(i)=CS(i);

N*(i)={n1,n2,…,n|N(i)|};

for(j=1;j≤|N(i)|;j++)

if αl(i)>α(nj) then

CSl(i)=CSl(i)∪{nj};

Update αl(i) based on Eq.(15);

end if

end

end

l*=argmin{α1(i),α2(i),…,αK(i)};

α*(i)=αl*(i),CS*(i)=CSl*(i).

在该算法中，K为功率分层数，N*(i)表示依综合路由度量值从小到大排序后的邻居节点集.通过对发射功率进行分层，从N*(i)中逐步挑选节点，加入候选节点集CS(i)中，且基于公式(15)实时更新路由度量α(i,Pt(i))的值，直到其大于邻居节点的值时停止.最后在这些不同功率分层中选出最优情形，这样便得到可用于机会路由设计的最优发射功率与候选节点集.

3.2 PCOR的设计

结合上一子节中的候选节点选择算法，本文设计了一种基于功率控制的机会路由PCOR，它是由路由探测、候选节点选择与排序、协调策略三大部分组成：

(1)路由探测：在路由协议的开始阶段，每个节点以最大发射功率Pt-max发送探测包以获得所有可能的邻居节点信息，这些节点在接收到探测包后通过回执ACK来建立节点之间的通信链路，并将自身的ID与状态反馈给发送者.然后，利用接收报文信号强度RSSI来估计多条无线链路的质量，结合邻居节点的反馈信息，发送节点初步构建路由表，选择距离目的节点更近的邻居节点.

(2)候选节点选择与排序：利用路由探测阶段所获取的网络信息，每个节点逐步调整自身发射功率，使用3.1节中的算法来寻找最优发射功率及相应的候选节点集.当网络中所有节点的候选节点集不再改变时，按照各节点的路由度量值α(i,Pt(i))从小到大的次序对候选节点进行优先级排序.

(3)协调策略：每一跳的候选节点集通过基于时钟的协调机制选择出一个中继节点来实际进行数据包的转发.根据上一步所确定的优先级为每个候选节点确定相应的时槽.发送节点在发送数据包时，将排序后的候选节点列表包含在数据包的头文件中，所有成功接收到数据包的候选节点以类TDMA的方式进行ACK应答.在完成应答的候选节点中，由优先级最高的节点作为实际中继节点，其它节点则将数据包丢弃.而被选中的候选节点将以同样的方式机会地选择下一跳中继节点来进行数据包的转发.

这一协调与转发过程将一直重复，直到数据包到达目标节点.如果在某一跳中，发送节点没有接收到任何一个来自候选节点的ACK，发送节点将重新执行上述协调和转发过程.该路由协议的前两个部分确定了：哪些节点将参与数据包的转发以及如何转发，第三部分则给出了一种预防数据包重复传输的协调机制，这都有效地提高了网络中数据转发的效率.

4 仿真实验

在这一节中，利用数学工具Matlab与网络仿真软件NS2共同实现所提的协议PCOR，并评估其性能.在仿真实验中，监测区域选为500×500 m2的方形区域，源节点与目的节点分别置于对角线两端，其余传感器节点被随机地部署.

首先，分析公式(15)中权重因子λ对路由协议及网络性能的影响.固定网络节点数目N与发射功率划分的层数K(分别取为20、10)，从网络生存周期与吞吐量两个方面研究λ的变化对PCOR协议的影响.

从图2中观察到，随着λ的增加，候选节点的选择更偏重于传输次数的考虑，网络生存周期逐渐降低，网络吞吐量不断提升.因此，λ的取值可根据当前网络应用的需求来确定.当网络通信负载较低时，选择较小的λ可降低节点能耗，延长网络生存周期；对于实时监测的传感器网络来说，较大的可提高数据的转发效率，增加网络的吞吐量.

(a)网络生存周期曲线 (b)网络吞吐量曲线图2 网络生存周期与吞吐量随λ的变化趋势

然后，通过改变监测区域中节点的数目N与发射功率划分的层数K，来观察PCOR、ExOR[3]、OAPF[6]与EEOR[7]四种机会路由在相同环境下的网络生存周期以及网络吞吐量.其中，公式(15)的权重因子λ取为0.5，其它参数具体参见表1.针对不同的功率分层情形，ExOR、OAPF与EEOR同时使用在该情形下PCOR所确定的最优发送功率.

表1 仿真参数

图3(a)给出了网络生存周期在每个节点的初始能耗为100J的情形下随网络密度与功率分层数增加的变化趋势.注意到，在采用4种机会路由的情形中，网络生存周期都随着节点数目的增加而大幅度延长.这是由于更多的候选节点加入到了数据包的得转发过程当中，均衡网络负载的同时，延长了各传感器节点的寿命.功率分层数较低时，EEOR在每一跳选择转发节点过程中，选取期望能量最小的候选节点集，因此有最大的网络生存周期.当分层数K达到20时，PCOR选取的发射功率更逼近最优的情形，在延长网络生存周期方面优于EEOR.由于ExOR与OAPF在候选节点选择阶段主要考虑数据包的传输，因此具有较低的网络生存周期.

网络吞吐量可以有效地反映网络性能，如图3(b)所示.当网络中节点数目增加时，节点可选择更多的候选节点来转发数据包，有效地提升数据包的转发效率，同时增大网络吞吐量.功率分层数较低时，OAPF在选择候选节点的过程中使用了基于EAX的优化算法，具有最大的网络吞吐量.随着节点数与分层数的增加，PCOR的发射功率逐渐逼近最优值，取得了更优的网络性能.由于EEOR侧重考虑协议的能量有效性，具有最差的数据转发效率.因此，PCOR是一种非常适应于无线传感器网络且高效的机会路由协议，在取得较好的网络性能的同时大幅度降低传感器节点的能量消耗.

(a)网络生存周期曲线

(b)网络吞吐量曲线图3 网络生存周期与吞吐量随网络节点数和功率分层数变化趋势的比较

5 结论

针对无线传感器网络中节点能量有限与无线链路不稳定的特点，利用马尔科夫链对机会路由中数据转发过程进行建模，给出两种关键路由度量：ExNT与EEC的计算公式，进而研究发射功率的改变对路由性能的影响，设计了一种基于功率控制的机会路由协议PCOR.在与其它几种典型机会路由对比分析之后，所提协议在取得较好网络性能的同时，能够显著降低传感器节点的能量消耗，有效延长网络的生存周期.在未来的研究工作中，将在路由协议中加入数据重传次的约束，避免同一数据包大量重传现象的发生，保证数据更加实时高效地传输，进一步提升网络的吞吐量.

[1] Al Karaki J N,Kamal A E.Routing techniques in wireless sensor networks:A survey[J].IEEE Wireless communications,2004,11(6):6-28.

[2] Biswas S,Morris R.Opportunistic routing in multi-hop wireless networks[J].ACM Sigcomm Computer Commun- ication Review,2004,34(1):69-74.

[3] Biswas S,Morris R.ExOR:Opportunistic multihop routing for wire-less networks[J].ACM Sigcomm Computer Communication Review,2005,35(4):133-144.

[4] Rozner E,Seshadri J,Mehta Y,et al.Simple opportunistic routing protocol for wireless mesh networks[C]//2nd IEEE Workshop on Wireless Mesh Networks.Reston:IEEE Conference Publications,2006:48-54.

[5] Lu M M,Wu J.Opportunistic routing algebra and its applications[C]//IEEE International Conference on Computer Communications.Rio De Janeiro:IEEE Conference Publications,2009:2 374-2 382.

[6] Zhong Z F,Nelakuditi S.On the efficacy of opportunistic routing[C]//4th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks.San Diego:IEEE Conference Publications,2007:441-450.

[7] Mao X F,Tang S J,Xu X H,et al.Energy-efficient opportunistic routing in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(11):1 934-1 942.

[8] Hu H F,Zhu Q.Power control based cooperative opportunistic routing in wireless sensor networks[J].Journal of Electronics (China),2009,26(1):52-63.

[9] 张大鹏,康会莉,王新生.WSNs中一种基于EIETX的自适应功率控制的机会路由[J].传感器与微系统,2013,32(3):43-45.

[10] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,4(1):660-670.

[11] Rappaport T S.Wireless communications:Principles and practice[M].New Jersey:Prentice Hall PTR,1996.

[12] Darehshoorzadeh A,CerdAlabern L,Pla V.Modeling and comparison of candidate selection algorithms in opportunistic routing[J].Computer Networks,2011,55(13):2 886-2 898.

[13] Kemeny J G,Snell J L.Finite markov chains[M].Princeton,NJ:Van Nostrand,1960:43-54.

【责任编辑：蒋亚儒】

Design of opportunistic routing based on power control in wireless sensor networks

HAO Jun1， JIA Xin-chun1， SHI Xiao-dong1， HAN Zong-yuan2， YANG Bo1

(1.School of Mathematical Sciences, Shanxi University, Taiyuan 030006, China; 2.Institute of Computing Technologies, China Academy of Railway Sciences, Beijing 100081, China)

The design of routing protocols is a challenging problem due to the limited energy of sensor nodes and unreliability of wireless links in wireless sensor networks.Based on the broadcast nature of wireless transmissions,multiple candidate nodes cooperatively participate in the packet forwarding process in opportunistic routing,which can increase the network throughput effectively.Two crucial routing metrics:ExNT and EEC,which have a great impact on candidate selection,are modeled by the Markov chain approach.Combined with power control,the effects of transmitting power on these routing metrics are studied,and the corresponding candidate selection algorithm is designed.Furthermore,an opportunistic routing based on power control (PCOR) is described in detail and implemented in NS2.Compared with several existing opportunistic routing protocols,the experimental results indicate that the proposed PCOR not only improves the network performance,but also reduces the total energy consumption.

wireless sensor networks； opportunistic routing； Markov chain； power control

2016-06-01

国家自然科学基金项目(61374059，U1334210)

郝 军(1992-)，男，山西五台人，在读硕士研究生，研究方向：网络化控制系统、智能控制、无线传感器网络

1000-5811(2016)06-0176-07

TP393

A