无线传感器网络中的节能路由算法研究

李 平，戴 劲

(长沙理工大学计算机与通信工程学院，湖南 长沙 410114)

1 引言

无线传感器网络WSN(Wireless Sensor Network)是由多个节点组成的面向任务的无线自组织网络，它主要由感知单元、传输单元、存储单元和电源组成，在完成感知对象的信息采集、存储和简单的计算后，通过传输网络传送给远端的监控中心。无线传感器网络由一组微型传感器通过Ad Hoc方式组成，网络中的传感器监控区域的感知对象的信息及数据可以协作地感知、采集和处理，并发送给使用一定形式终端设备的用户。无线传感器网络属于Ad Hoc网络，“Ad Hoc”在拉丁语中的意思是“专用的、特定的”，因此Ad Hoc网络通常也被称为无固定设施的网络或自组织网络，它能够快速、灵活和方便地自动组网。传感器网络具有集中式数据收集、多跳数据传输、多对一流量模式等特征[1,2]。

无线传感器网络中的节点多采用能量有限的电池供电，因此，降低节点能量消耗在整个网络的设计中需要重点考虑[3]。一些路由算法(如泛洪路由协议、定向扩散路由、自适应路由算法、基于地理位置信息的路由[4,5])虽然降低了整个网络的能耗，但网络生存时间却缩短了，这是因为在这些算法中某几个中转节点因承担了过多的数据传输任务而过早耗尽自身的能量而失效。因此，本文在最小跳数的基础上提出一种保护节点能量的路由算法。该算法通过建立最小跳数和对节点剩余能量的保护，使得数据包沿着能耗最优的路径向Sink节点发送。在MATLAB环境下对该机制进行了仿真实验，实验结果表明，该算法能降低能耗，均衡和延长网络生存时间。

2 相关工作

目前，国内外学者对选择性转发攻击的研究取得了一定的成果。Jain等人[6]提出的能量多路径路由EAMR(Energy-Aware Multi-path Routing)机制是在源节点到目的节点间建立的多条路径，在多条路径上传输数据的多个拷贝或把数据分成多个相等部分并发传输，使得数据传输均衡消耗整个网络的能量，延长整个网络生存期。文献[7]提出了一种根据建立虚拟簇，实现延长了网络生存期和多媒体数据的节能传输，但是并没有减少多媒体数据传输量。文献[8]对多媒体节点活跃期与休眠期划分的方法是通过数据分组的具体内容来实现。文献[9]提出了一种多媒体传感器网络分布式能量管理算法CDPM(Computer Distributed Power Management)利用邻居信息通信代价，并通过逐帧比较减少了传感开销，但该算法无法保证能耗均衡。文献[10]探讨无线传感器网络中采用节点非均匀分布策略的能量空洞问题。

本文在上述基础上，构建了一种节约能量的无线传感器网络，通过建立最小跳数和对节点剩余能量的保护，使得数据包沿着能耗最优的路径向Sink节点发送，从而能降低能耗和延长网络生存时间。

3 生存网络模型

假设传感器网络中的节点随机分布在一个正方形监测区域内，该网络具有以下特性：

(1)无线传感器网络的环境以汇聚节点为中心，节点随机而稠密地分布在一个区域内，每个节点在网络中有唯一的标识号ID，并且其发射功率为固定值。为便于表示，做如下定义：

设Pj表示标识号ID为j的节点；P={Pj|Pj表示标识号ID为j的节点}，则P为有限集合，其元素个数为网络节点数n；Ej为Pj的现存能量；根据节点能量消耗和通信模型，每个节点的初始能量是ε且大于0，Sink没有能量限制，节点发送和接收k比特数据的能耗分别为：

Er(k，d)=kEelec+kEampd2

(1)

Er(k)=kEelec

(2)

其中，Eelec为收发数据时电路电子能耗；Eamp为信号放大器电路的能耗；d为发送节点与接收节点之间的距离。显然,每个节点发送1 bit数据的能耗大于接收1bit数据的能耗。

(2) 设节点之间的通信半径为R，如果物理距离|Pi-Pj|≤R,则称Pi和Pj为邻居节点，记Si={Pj|Pj∈P,且|Pi-Pj|≤R}。

(3) 所有传感器节点部署后静止不动, 所有节点都具有相同的性质(如初始能量值、通信半径、能耗值)，地位是对称平等的。

(4) 数据从源节点传输到Sink节点所用的时间称为传输时延；所有数据包传输时延的平均值称为平均时延，在上述假设下，同一数据包的传输时延仅仅与数据传输所经历的节点数目有关。

根据上述定义和假设，源节点Q向Sink节点发送数据时，无线传感器网络可看做是一个有向图。

设H={Hk|Hk表示所有源节点Q到Sink节点的路径}，其元素个数为链路的总数r，Zk表示路径Hk所包含的节点的数目。fij为Pi发送到Pj的数据流，因此节点Pi发送的数据流总和为：

(3)

从而可以得出节点的生存时间为：

(4)

4 最小跳数建立

协议中的节点都有唯一的标识号ID，初始化汇聚节点的跳数(hop设置为0)，其余节点的跳数设为极大值。Sink节点根据需要向网络广播数据查询消息，当邻居节点接收到数据包时，将数据包中的hop值加1作为新值与自身存储的hop值相比较，若新的hop值小于原来存储的hop值，则用新值替换原存储值；将数据包中的hop值换为新值，并替换原来节点的标识号ID。在自己的邻居列表中为Sink节点中添加一个信息，并根据查询消息修改表项中的neighborre_energy(即邻居节点的剩余能量)、neighborhops值(即邻居节点的最小跳数)和neighborID(即邻居节点的ID)。然后根据节点信息修改查询消息的内容，将信息包中的hop值加1并将剩余能量和其自身ID写入消息包，继续广播此查询消息。若新的hop值大于原来存储的hop值，则不作处理。

其它节点接收到数据包时做上述同样的处理，这样的过程一直持续下去，这样每个节点均建立了到Sink节点的多条最小跳数路径并记忆了各条路径的最小节点能量。

最后数据沿着查询消息的反向路径向汇聚节点传送，汇聚节点将每个节点的最小跳数和最小节点能量保存在本地节点信息中。

4.1 节点选择阶段

将符合条件的邻居节点的ID和需要转发的数据信息保存在本地中，若选择的接收数据节点在邻居节点中找不到合适的转发节点，则放弃本次邻居节点的选择，返回上一个节点，重新从本地中查看并选择另一个符合条件的邻居节点进行数据转发。

若有多个邻居节点到Sink节点的跳数相同，就选择剩余能量最多的邻居节点作为中继节点来转发数据包。

4.2 保护节点能量

在数据转发阶段，某些节点因承担较多的数据转发任务，从而消耗过多的能量，根据式(3)和式(4)，若某个节点的剩余生存时间小于某个阈值时，它向其它节点发送esc消息，声明该节点将不再作为转发节点，邻居节点收到该消息后，从本地信息中删除该节点的信息。同时，选择其邻居节点中能量最多的节点承担该节点相应的传输任务，承担传输任务的节点向周围的邻居节点发送work消息。如此一来，经过该低能量节点的路径将会被删除，节点的负荷处理能力也将降低。当在节点周围没有感兴趣的事件时，通信与计算模块就属于闲置模块，把这些模块调到低功率的状态或者关掉，即休眠状态。这种能量保护策略可以有效地降低节点的能量消耗，延长节点的生存时间，从而延长了网络的生命周期。

5 仿真实验

通过仿真实验，本文对基于能量均衡的路由算法的性能进行了验证，并将其与定向扩散协议在网络生存期和传输时延等方面进行了对比分析。

仿真实验条件设置：网络中所有节点随机分布在一个500 m×500 m的正方形监测区域内，平面中随机分布500个传感器节点，节点初始能量ε=200 J，Eelec=0.05 nJ/bit，Eamp=0.001 pJ/(bit·m2)，通信半径R=15 m，数据包长度L=160 bit。

图1是两种方法下的网络生存时间。定义仅当网络节点数目低于设定阈值时(本文仿真定义的阈值为30%)，网络失效。其中根据式(4)，当传感器节点的生存时间小于某一阈值时，我们认为它是失效的。从图1可以看出，由于靠近汇聚节点的区域出现能量空洞问题，导致系统的生命周期提早结束；而本文改进后，在路由选择时充分考虑路径中节点的剩余能量，遇到剩余能量较小的路径可以有效地避开，使得网络中的节点达到能耗均衡，只有当系统中剩余能量很少时，网络的生命周期才结束。

Figure 1 Survival time of the network graph图1 网络生存时间图

图2是两种协议的平均传输时延对比。节点传输半径增大时，传输所需的跳数减少，数据包传输时间将减少，两种算法的传输时延都呈递减的趋势。在定向扩散算法中，最优路径的建立是通过泛洪方式，需要的时间长，从而增加了网络时延。而本算法中，通过建立最小跳数来建立路径，从而能较快地找到最优路径，减少了网络时延。

Figure 2 Transmission delay图2 传输时延

6 结束语

无线传感器网络之所以引发网络能耗增加、生命周期缩短的不利影响，是由于网络中的一些节点负载过重而能源快速耗尽，网络传播路径的通信半径增大。本文提出了一种节能的路由算法，算法以均衡网络节点能耗为目的，优化路由选择的标准采用预测的结果，在路径建立过程中，下一跳节点选取邻居节点中剩余能量较多的节点。实验仿真结果表明，此算法有效防止了在路由建立时进行泛洪传播而造成大量的能量消耗，同时更好地均衡网络的能量消耗，最大限度地延长了网络的寿命。但是，此方法未必是能量节省的最优方法，如何能使网络生存时间更长，是今后需要研究的工作。

[1] Xiao R Y, Wu G. A survey on routing in wireless sensor networks [J]. Progress in Natural Science, 2007, 17(3):261-269.

[2] Wang J, Howitt I. Optimal traffic distribution in minimum energy wireless sensor networks[C]∥Proc of 2005 IEEE Global Telecommunications Conference, 2005:3274-3278.

[3] Liang W, Liu Y. Online data gathering for maximizing network lifetime in sensor networks [J]. IEEE Transactions on Mobile Computing, 2007, 6(1):2-11.

[4] Cheng Z, Perillo M, Heinzelman W B. General network lifetime and cost models for evaluating sensor network deployment straregies [J]. IEEE Transactions on Mobile Computing, 2008, 7(4):484-497.

[5] Zhao Ye-fei, Yang Zong-yuan, Xie Jin-kui. Pi-calculus based assembly mechanism of UML state diagram and validation of model refinement [C]∥Proc of International Conference on Electronic Computer Technology, 2009:604-609.

[6] Cai Jing-ming,Sun Ji-feng.Adaptive routing algorithm in wireless sensor networks [J]. Computer Engineering, 2009, 35(18):263-265. (in Chinese)

[7] Navratis S,Aahishek R,Jitae S.A QOS-based energy-aware MAC protocol for wireless mulitimedia sensor networks[C]∥Proc of Vehicular Technology Conference, 2008:183-187.

[8] Zhang Q, Xie Z P, Ling B. A maximum lifetime data gather-

ing algorithm for wireless sensor networks [J]. Journal of Software, 2005, 16(11):1946-1957.

[9] Nuran T, Wenye W. Self-orienting wireless multimedia sensor networks for maximizing multimedia coverage[C]∥Proc of IEEE International Conference, 2008:2206-2210.

[10] Wu Xiao-bing, Chen Gui-hai. The energy hole problem of non-uniform node distribution in wireless sensor networks[J]. Chinese Journal of Computers, 2008, 31(2):253-261. (in Chinese)

附中文参考文献：

[6] 蔡景明, 孙季丰. 无线传感器网络中的自适应路由算法[J]. 计算机工程, 2009，35(18):263-265.

[10] 吴小兵, 陈贵海. 无线传感器网络中节点非均匀分布的能量空洞问题[J]. 计算机学报, 2008,31(2):253-261.