无线网状网中延长网络生命周期的机会路由

徐 倩，徐玉斌

(太原科技大学 计算机科学与技术学院，太原 030024)

无线传感器网络[1](Wireless Sensor Networks, WSNs)是由很多个传感器节点构成的多跳网络，普遍应用于各个领域。由于网络中节点的能量由电池供应，能量存储有一定的限制，所以如何改善网络的生存周期，使节点的能量消耗变得均衡尤为重要。而在无线传感器网络中，在均衡能量消耗方面，设计低能耗的路由协议起到了举足轻重的作用，其中，Biswas[2]等人首先提出的机会路由[3-4]充分利用无线链路的广播特性和异变性，考虑节点选择下一跳转发路径的机会性，从而有效提高了无线多跳网络的可靠性，减少了数据传输次数，对照传统的路由协议，机会路由有效的提高了网络的生命周期。在节能机会路由的研究中，文献[5]结合节点的成功传输次数与节点剩余能量，提出了一种候选节点选择策略，对网络的生存时间有了明显的提高。文献[6]利用地理信息，提出一种自适应转发集优化算法，优化传输效率并最大化网络生命周期。文献[7]综合考虑了节点剩余能量和链路上收发双方总能耗，同时引入随机网络编码，设计了一种转发节点集选择算法。不仅保证了数据传输的可靠性，也优化了网络生存时间。上述研究从优化节点候选集出发，通过减小节点传输数据的能耗来降低网络能量消耗。由于候选集节点的数量大小也会影响无线网络的性能，文献[8-10]分别提出几种控制节点数量的方法。文献[10]考虑了节点间隔距离、网络密度等因素，设计了一种候选节点数量选取算法，减少了网络中冗余的候选节点，提升了网络的性能。

智能电表网状网(AMI mesh network)是由多个智能电表组成的一种多跳无线网络，相比于有线通信的组网方式，无线通信的模式使得传感器节点部署便利，成本低廉[11]。文献[12]以此为背景，将机会路由应用在智能电表网状网中，提出尽快完成采集数据传输的机会路由问题，将机会路由候选节点选择问题建模并求解。文献[13]考虑数据流的分布，将机会路由选择问题描述成凸优化问题，并且提出了一种多流机会路由算法以提升网络吞吐量。

本文以智能电表为应用背景，在多跳无线的组网形式下，结合该网络固有的特征，设计了一种基于地理位置信息、以均衡节点能耗为目的的机会主义路由协议GEOR，旨在保证数据传输可靠性的同时，有效延长网络的生命周期。

1 问题描述

如图1所列举的一个简单无线网状网示例图，其中，节点D作为目的节点，剩余节点均作为源节点。其网络特征总结如下：

(1) 网络中节点排列有序，节点间最小间隔距离相同；

(2) 已知地理位置信息，且网络拓扑结构基本不变；

(3) 在数据采集阶段，源节点传送单个数据包到目的端。

图1 无线网状网拓扑结构
Fig.1 Topology of wireless mesh network

传统的以地理距离为测度的机会路由(如GeRaF)，仅考虑地理位置来决定节点转发优先级，造成过度利用距离目的节点较近节点的问题，第一个死亡节点的出现时间较早，导致整个网络的生命周期较短。针对上述问题，将节点的剩余能量作为参考因素，提出了一种将节点剩余能量与地理距离结合的路由测度，在选择节点转发集时，优先选择距离目的节点近且能量高的节点，考虑如下路由测度公式：

REEi=REi/d(i,D)

(1)

其中，REi指代节点i的剩余能量，d(i,D)指代节点i与目的节点D之间的距离。

以RRE作为一种候选集节点选择测度，虽然提高了网络生命周期，但在选取下一跳节点时，仍然会对距离目的节点较近的节点造成一种能量负担。考虑图2所列举的一个简单网络，S为源节点，D为目的节点，A,B,C作为转发节点。令d(S,D)表示两节点S与D的间隔距离，其中，d(B,D)= 20 m，d(C,D)=10，初始能量EB=EC=50 J，计算可得节点B与C的路由测度分别为：RREB=50/20,RREC=50/10，则选择测度值较大的节点C作为下一跳节点，当节点C的能量消耗至25 J时，RREB=RREC，此时节点B的能量值较大，与均衡节点能耗的初衷相悖，并且这样更容易出现节点过早死亡。

图2 网络拓扑结构
Fig.2 Network topology

由上述描述，在网络拓扑结构变化较小的情况下，距离目的节点较近的节点有更大的机会转发数据，并且其余节点转发数据的机会受到候选集中节点间距离差值大小的影响。所以，如何结合节点剩余能量与位置信息选择下一跳转发节点，尽可能使得每个节点的剩余能量在一个较小的范围内波动，是本文所要解决的问题。

2 GEOR路由协议设计

2.1 节点剩余能量模型及转发测度

由文献[14]的描述，first-order能耗模型中，传输k位数据包的发送能耗etx(d,k)与接收能耗erx(k)分别如下：

etx(d,k)=(eelec+eamp·dr)·k

(2)

erx(k)=eelec·k

(3)

其中，eelec为无线收发器运行开销，eamp为传输开销，d为传输距离，r为信道衰减指数。

在GEOR协议中，节点传输单个数据包的能量消耗主要包括发送能耗etx与接收数据的能耗erx.即节点的剩余能量RE(residual energy,RE)可表示为：

RE=E0-etx-erx

(4)

其中，E0表示节点初始能量。可以看出，节点接收或发送固定大小的数据包，其能量消耗值是一定的。

为了弱化节点间固有距离对其转发机会的影响，同时使源节点能够以较小的跳数传递数据到目的节点，避免忽略能量过多的节点，本文提出了一种新的路由测度。以下给出节点剩余能量与任一节点到目的节点的距离比值(Residual Energy Distance Ratio)：

(5)

其中，α,β是调节因子，根据网络密度的大小及节点间最小间隔距离来设置相应的值。网络密度大，β取值较大，节点最小间隔距离越大，α的取值越大，反之距离越小，α的取值也相应减小。从式(5)中可以看出，节点的剩余能量越大，越靠近目的节点，则其RED就越大。

本文将节点的RED值作为路由的测度，根据其大小进行候选集的选取并对节点进行优先级排列。

2.2 GEOR协议的候选集选择算法

此路由协议中将节点的RED值作为路由测度，根据该值进行候选节点集的选取并对节点进行优先级的排列。以下是GEOR路由协议的工作原理：

(1) 信息获取阶段。节点通过一次全网广播，即可获知任意节点的位置信息；

(2) 候选集选取阶段。比较源节点与邻节点的测度值RED大小，将RED值大于源节点的邻节点加入候选转发集中，(候选集的大小不超过最大值Maxsize)并依照RED值大小对节点进行优先级排序；

(3) 数据发送阶段。源节点S向候选集中的节点发送单个数据包，接收到数据包且优先级最高的那个节点作为下一跳转发节点。以此循环，当目的节点接收到数据包时，数据发送结束。

定义如下符号：Fs表示源节点S的候选集；neighbor是邻居节点集；Vi表示邻居节点；REDVi表示节点Vi的路由测度；size_Fs表示候选集节点数量大小；Maxsize表示候选集中最大的节点数。

候选集选择算法伪代码如下：

setFS←φ

forVi∈neighbor

descendant order byREDVi

ifREDVi>REDS

FS←FS∪Vi

ifsize_Fs>Maxsize

returnFs

end if

end if

2.3 参数α,β的取值描述

在选取α,β值时，应满足如下条件：

0<α

(6)

0<β

(7)

其中，Maxdis表示网络中节点间最大间隔距离，取α,β为整数。

考虑到不同的网络背景下，网络密度与节点间隔距离都会影响对参数值的选取，在此，为了获得合适的参数值，本文通过多次实验，比较了在不同的参数值下，整个网络生命周期的长短，选取网络生命周期最大时相应的α,β值。

具体算法如下：

r←0 //网络生命周期r初值为0

for allα

for allβ

equation(5)←(α,β) //将参数α与β带入式(5)

get bestr//运行程序得到本次实验bestr

if bestr>r

r←best

else

r←r

end

whileris biggest

returnα,β

end while

2.4 节点通信范围算法

在数据传输后期，随着节点能量的消耗，节点间的能量分布开始表现出不均衡性。若仍然使用初始的固定功率，保持相同的通讯范围，可能存在以下问题：当保持节点通信范围不变时，发送节点的剩余能量可能已经不足以支持传输数据所要消耗的能量，从而造成节点死亡。但是如果缩小节点的传输范围，能更好的避免过早出现第一个死亡节点。虽然这也加重了整个数据传输过程中的能耗，但发送信息附近的节点有了更多的转发机会。下面通过一个简单的实例进行说明，假设节点A的通信范围为10 m，传输一个数据包到10 m远所消耗的能量为0.5 J，经过一段时间的数据传输后，节点A的剩余能量为0.5 J，即如若保持节点A的通信范围不变，那节点A再进行一次数据传输后就会死亡。但是，若将节点A的通信范围变小，不仅满足了自身发送数据所要消耗的能量，也增大了邻居节点转发数据的机会，这样能更好的延长网络生命周期。

通过以上描述，适当改变节点通讯范围更加充分考虑了节点剩余能量的运用。这里，假设通讯范围为10 m的节点，最远可进行三跳将数据传递到目的节点。那么，通过逐级递减其跳数来控制节点的通信范围。本文会通过第3小结的实验来检测该节点通信范围算法的优劣。

具体算法为：

while 0

do=do-Mindis

Et←newEt

ifREi>newEt

return do

else

do=do-Mindis

Et←newEt

End

End

上述算法各个符号含义如表1：

表1 符号
Tab.1 Notations

符号含义REi节点i的剩余能量Et传输范围为do时节点发送数据所消耗的能量do节点传输范围Mindis节点间最小间隔距离

3 实验仿真及结果分析

将GEOR路由协议算法在MATLAB下进行仿真评估。与经典的路由协议ExOR及以能耗为目的的路由协议PLOR进行比较。

3.1 参数设置

仿真实验中，采用Shadowing模型反映无线信道多径衰落的特征，参照距离记为1 m，阴影方差记为4，路径损耗系数记为2，节点传输范围15 m.无线传感器网络节点有序排列在大小为45*45区间内，节点横坐标范围[20，62]，纵坐标范围[20，62]，节点间最小间隔距离Mindis为3 m，共部署了225个节点，目的节点位于坐标(65，41)处，节点初始能量为1J，目的节点能量不设限，参数α,β取值分别为10，3.数据包大小为512bytes，采用802.11MAC协议，最大传输率是250 kb/s，仿真时间以第一个死亡节点为准。

实验结果以网络生存周期及节点能量均衡性作为评估标准，定义评价指标如下：

(1) 网络生存周期：以出现第一个死亡节点为标准，评估整个网络成功完成一次数据传输的次数(源节点到目的节点成功完成一次数据传输记为一次循环r)；

(2) 节点能耗均衡性：第一个节点死亡时，用网络节点剩余能量的分布和方差来反应其均衡性。

3.2 实验结果分析

(1) 网络生命周期的比较。三种路由协议网络生命周期的试验比较结果如图3.从图中可以得知，路由协议ExOR最先出现死亡节点，PLOR协议次之，路由协议GEOR出现第一个死亡节点时的传输次数更长。结果表明，GEOR的网络生命周期得到了有效的提高。观察图3也可以看出，ExOR协议虽然第一个节点死亡时间较早，但并没有影响其整体传输数据的次数；而PLOR在220次数据传输后，出现大批节点死亡的情况，这是由于节点能量均衡性较好，在数据传输后期，多数节点都已濒临死亡，但其整体的数据传输次数没有ExOR表现的好。本文提出的路由协议GEOR不仅有效延长了网络生命周期，也表现出较好的成功传输数据的性能。

图3 网络节点死亡个数
Fig.3 Number of died of network nodes

(2) 节点能耗均衡性的比较。如下图4描绘了网络中出现第一个节点死亡时，各个节点剩余能量的分布情况，以此来表明网络节点能量均衡性问题。由图4可知，GEOR表现出更好的均衡性。通过计算获知ExOR，PLOR及GEOR的节点剩余能量平均值分别为0.96 J，0.34 J，0.07 J，方差分别为0.005 7,0.013 1，0.000 8.虽然ExOR方差较小，但从图4 可以看出，有一部分节点剩余能量为1 J，其未进行过数据传输，而目的节点附近节点的能量消耗过多。相比于PLOR协议，GEOR的能耗均衡性表现的更好。

图4 剩余能量分布
Fig.4 Distribution of residual energy

(3) 节点通信范围算法的实验仿真结果。在其余实验参数设置相同的情况下，将未使用本文节点通信范围算法的实验记为a，使用本文算法的实验记为b.图5描述了节点通信范围算法使用前后，网络生命周期的情况。从图中可以看出，实验a较早出现第一个死亡节点，实验b的网络生命周期有小幅度的提高，整体传输数据的次数相差不多。

图5 实验a，b死亡节点个数
Fig.5 Number of died nodes in the test a and b

4 结束语

针对无线网状网的网络特征，本文设计了一种新的路由协议GEOR.该协议结合节点剩余能量和位置信息，给出一种新的路由测度，并设计了一种新的节点通讯范围算法。实验结果表明：协议GEOR较好的延长了网络生命周期，实现了节点能量的均衡消耗。但在参数α,β的取值研究上无形加重了实验的负担，还有所欠缺。下一步工作中期望结合智能优化算法来改善参数值的选取。