于 秦，王伟东，张兰心，毛玉明



基于轮作的无线传感网络链式路由协议

于 秦，王伟东，张兰心，毛玉明

(电子科技大学通信与信息工程学院 成都 611731)

为了节省无线传感器节点能耗，延长无线传感网络的生存周期，提出一种基于轮流作业策略的RPB无线传感网络链式节能路由协议。该协议基于PEGASIS链式协议并结合GAF协议进行改进。仿真结果显示，在保证有较高网络覆盖度的前提下，相较于传统的无线传感网络PEGASIS、LEACH和EEPB等路由协议，RPB协议在节能上更为突出，且在传感节点死亡超过总数的一半时，能实现节点在网络中较为均匀的分布。

节能; 轮作; 路由协议; 无线传感网络

针对无线传感器节点能量有限的问题，为了延长无线传感网络的生存周期，研究人员提出了许多能量高效的算法[1]。其中PEGASIS(power-efficient gathering in sensor information system)链式协议[2]是建立在LEACH(low energy adaptive clustering hierarchy)分簇算法[3]基础上的改进协议，通过贪婪算法生成一条由所有节点组成的单链，然后由链中的节点轮流担任LEADER节点，并在融合全网数据后将数据发往基站。这种做法可以在最大程度上减少节点的耗能，EEPB(energy-efficient PEGASIS- base protocol)[4]则是基于PEGASIS协议的改进算法；GAF(geographical adaptive fidelity)[5]协议是以节点的地理位置为依据的算法，通过把检测区域划分成虚拟的单元格，每个单元格中的节点可以认为是等价的，因此在一个时间段内，一个单元格只需要一个节点实施数据采集，同一单元格内的其他节点可以进入睡眠以节省能量。上述算法的不足主要体现在：PEGASIS中已经加入链的邻居不能被再次访问，因此相邻节点间长链不可避免，且节点轮流当选LEADER策略会导致远离基站的节点过早死亡；而GAF则要求节点配备GPS等额外设备来获取节点地理位置信息，增加了无线传感器节点的制造成本。此外，还有在GAF和PEGASIS的基础上改进的GSSC[6]协议，该协议同GAF一样把检测区域分成虚拟单元格，格间节点按距离组成多条链，也需要节点拥有全局位置信息。而CRBCC[7]则是在PEGASIS的基础上并行建成多跳链，链首之间又建链，挑选其中一个链首向基站发送消息，该协议有效地减少了数据传输时延，但节能性略差于PEGASIS。类似的还有CCM[8]，要求节点均匀地分布在监测区域。在分析各种算法后，本文提出了一种基于轮作和链式的无线传感网络节能路由新算法RPB(rotation and PEGASIS-based protocol)。

1 无线传感网络随机分布模型及覆盖控制

在对协议进行描述之前，先介绍无线传感网络随机分布及覆盖控制模型。参考文献[9]已经证明，在一个覆盖的网络模型中，如果传感器节点在监测区域内呈密度分布为的均匀分布，区域内节点个数的概率服从泊松分布，其概率密度函数为：

证明：

(4)

2 协议描述

RPB协议由3个阶段组成：链路建立阶段、LEADER节点选取阶段和数据传输阶段。

2.1 链路建立阶段

在链路建立阶段，基站广播hello消息，节点应答后基站即获取全网信息，如节点ID、存活状况、节点到基站的距离等，此时当一个节点收到其他节点发送给基站的信息时，可以通过键值对的方式记录所有其他节点的ID及这些节点与自己的距离。然后，基站广播最远节点(END)的ID并从离基站最远的节点开始建立链路，END节点在记录中寻找距离自己最近的未加入链的节点，通过发送数据量很少的请求消息让目标节点加入链中，其中，请求消息含有当前已经加入链路的节点个数，其他节点监听到该消息时更新自己的链路信息，如果监听到的请求消息信息与自身记录信息不符，可通过询问邻居节点的方式获得当前链路。

当节点能量即将耗尽时，为了确保节点留有一定的剩余能量并能在下一个数据发送周期开始前通知邻居，设节点最小剩余能量为，其中为节点作为LEADER发送一次数据到基站所消耗的能量，当节点能量小于等于，节点不再进入睡眠，并通知被接替工作的节点(假设为节点)，如果节点周围没有剩余能量大于的节点在下一轮接替其工作，则节点也不再进入睡眠，每一轮都参加链路建立和数据传输。

图1 链路建立过程

由该算法构成的链如图2所示(图中未加入链的带“*”的节点为本轮进入睡眠的节点，带“+”的节点为下一轮将进入睡眠的节点)。

图2 由RPB算法构成的链

2.2 LEADER节点选取阶段

选取LEADER节点时，参考常用的无线传输能量耗费模型(radio energy dissipation model, REDM)。基于该模型，传输一个比特的消息，节点消耗的能量为：

(6)

接收该消息需要消耗的能量为：

(8)

2.3 数据传输阶段

在数据传输阶段，每个传感器节点调整自身发射功率以便只有最近邻居才能听到，然后进入数据传输阶段。数据传输阶段使用Token(令牌)机制，Token很小，因此在传输过程中耗能较小，其传输过程如图3所示。END节点0首先获得Token，沿着数据链将数据传给1，1将0发来的数据和自身采集的数据进行融合后传给2，然后2将Token传给端节点4；2以同样的方式收集到4和3的数据以后与自身采集的数据融合，沿着LEADER节点方向将数据传到5[10]。

LEADER节点以同样方式收集到所有数据并进行融合后发送到基站，至此一轮数据收集结束。在该轮进入休眠的节点此时醒来，被接替工作的节点设定定时器并进入睡眠，协议从链路建立阶段的“基站广播hello消息，节点应答后基站即获取全网信息”这一步骤之后重新开始下一轮数据传输。

图3 数据传输过程

3 仿真实验

结合上述覆盖模型，通过MATLAB以不同的密度将无线传感器节点部署在不同的场景中，并改变的值，观察其面积覆盖率。其中传感器节点的感知半径由传感器本身性能决定。本文假设，对每个场景下的不同节点总数分别进行500次节点随机撒播模拟，并取在一轮里面工作节点的平均个数(结果统一向下取整)，得到的数据如表1和表2所示。

当所有节点在一轮里全部投入工作，即其最大面积覆盖率对应25、50和100个节点分别为86.6%、98.2%和99.97%。

当所有节点在一轮里全部投入工作，即其最大面积覆盖率对应50、100、150和200个节点分别为63.39%、86.6%、95.09%和98.2%。

表1 50 m×50 m场景下节点随机撒播模拟

表2 100 m×100 m场景下节点随机撒播模拟

3.1 仿真场景及参数

本文在100 m×100 m的场景中随机放置了100个节点，其中基站的位置为(50,300)，其他具体仿真参数如表3所示。

表3 仿真参数

3.2 不同协议性能对比分析

通过MATLAB分别对LEACH、PEGASIS、EEPB(为定义距离门限时用户自定义的系数，本文取值1.2)和RPB进行仿真对比，得到的结果如图4所示，其中轮数越大表示网络的生存时间越长。

从存活节点图可以看出链式协议比簇类协议在减少能量消耗、延长网络生命周期方面的优势较为突出，而通过轮作的策略使得RPB比EEPB的生存时间延长了15.04%，比PEGASIS的生存时间延长了28.72%，比LEACH的生存时间延长了115%，其中RPB优于EEPB的部分主要为休眠节点所贡献。

图4 不同协议的对比仿真

表4为死亡节点占所有节点不同百分比下的协议轮数对比，可见RPB首个死亡节点出现比EEPB早，这是由于选取链首的策略不一样造成的。死亡节点占10%时出现的轮数比EEPB延后了11.3%，而死亡节点占50%以及死亡节点占100%时，RPB相对EEPB延后了14.6%和15%。

表4 死亡节点占所有节点的百分比

图5为网络的剩余能量图，从网络能量消耗曲线可以看出，LEACH的斜率较大，曲线较陡，PEGASIS次之，EEPB和RPB的曲线斜率较小也较为平缓。由此可见，在一定时间内，链式协议的剩余能量明显多于分簇式协议的剩余能量。以EEPB和RPB参照节点能量来选择LEADER节点，因此消耗曲线看似一条直线，而LEACH和PEGASIS则以概率或者轮流的方式来选择簇头或者链首，因此消耗曲线在剩余能量较低的地方斜率会发生变化，这是因为远离基站的节点此时都已经死亡，只剩下离基站近的存活节点在工作。

图5 网络的剩余能量图

3.3 改变节点数量时不同协议性能对比分析

通过MATLAB分别对LEACH、PEGASIS、EEPB和RPB在不同节点数量时的性能进行仿真和对比分析，其结果如图6所示。

分析图6的数据可得，当改变时，基于分簇的LEACH协议由于节点并没有分摊将数据发送到基站所消耗的能量，因此在存活时间上没有改善，而链式协议由于节点分摊了将数据发送到基站所消耗的能量，因此存活时间得以延长。通过协议间比较可以发现，当=100时，RPB比EEPB的存活周期延长了15.04%，比PEGASIS延长了28.72%；当=150时，RPB比EEPB的存活周期延长了23.63%，比PEGASIS延长了39.35%；当=200时，RPB比EEPB的存活周期延长了39.1%，比PEGASIS延长了54.89%。可见，随着监测区域中节点密度的提高，可以进入休眠的节点也随着增加，休眠轮作调度的优越性也渐渐显示出来。

a.=150时，不同协议的节点存活图

b.=150时，不同协议的节点剩余能量图

c.=200时不同协议的节点存活图

d.=200时，不同协议的节点剩余能量图

图6 当取不同的值时各个协议的性能比较

4 结 论

结合无线传感网络节点被密集撒播的特点，对某些感知范围被其他节点完全或绝大部分覆盖的节点实行休眠轮作调度策略，以及改变节点加入链的条件和LEADER节点的选取策略，可以进一步实现减少节点能耗，从而为保证一定覆盖率的前提下实现最大限度减少节点耗能提供了一种解决方案。对实时性不高，节点撒播较为密集且需要持续长久地监测目标的场合，其优势比较明显。

[1] 孙利民, 李建中, 陈渝, 等. 无线传感器网络[M]. 北京:清华大学出版社, 2005.

SUN Li-min, LI Jian-zhong, CHEN Yu, et al. Wireless sensor network[M]. Beijing: Tsinghua University Press, 2005.

[2] LINDSEY S, RAGHAVENDRA C. PEGASIS: Power- efficient gathering in Sensor information system[C]//Proc of IEEE Aerospace Conference. Los Alamitos, CA: IEEE Computer Society Press, 2002: 1-6.

[3] HEINZELMAN W R, CHANDRAKASA A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//IEEE Proceedings of the Hawail International Conference on System Science. [S.l.]: IEEE, 2000: 1-10.

[4] 余勇昌, 韦岗. 无线传感器网络中基于PEGASIS协议的改进算法[J]. 电子学报, 2008, 36(7): 1309-1313.

YU Yong-chang, WEI Gang. An improved PEGASIS algorithm in wireless sensor network[J]. Chinese Journal of Electronics, 2008, 36(7): 1309-1313.

[5] XU Y, HEIDEMANN J, ESTRIN D. Geography-informed energy conservation for ad hoc routing[C]//Proceedings of 7th Annual International Conference on Mobile Computing and Networking (MOBICOM’01). [S.l.]: ACM, 2001: 70-84.

[6] LOHAN P, RAJNI C. Geography-informed sleep scheduled and chaining based energy efficient data routing in WSN[C]//IEEE Students’ Conference on Electrical, Electronics and Computer Science. [S.l.]: IEEE, 2012: 9-12.

[7] ZHENG Geng-sheng, HU Zheng-bing. Chain routing based on coordinates-oriented clustering strategy in WSNS[C]//Computer Network and Multimedia Technology. Wuhan: [s.n.], 2009: 1-4.

[8] TANG Fei-long, LLSUM Y, GUO Song, et al. A chain-cluster based routing algorithm for wireless sensor network[J]. Journal of Intelligent Manufacturing, 2012, 23(4): 1305-1313.

[9] 高德民, 钱焕延, 徐江, 等. 无线传感器网络随机分布模型及覆盖控制研究[J]. 传感技术学报, 2011, 24(3): 412-417.

GAO De-min, QIAN Huan-yan, XU Jiang, et al. Wireless sensor network random distribution model and coverage control research[J]. Chinese Journal of Sensors and Actuators, 2011, 24(3): 412-417.

[10] LIM Se-jung, PARK Myong-soon. Energy-efficient chain formation algorithm for data gathering in wireless sensor networks[J]. International Journal of Distributed Sensor Networks, doi: 10.1155/2012/843413.

编 辑 税 红

Rotation-Based WSN Chain Routing Protocol

YU Qin, WANG Wei-dong, ZHANG Lan-xin, and MAO Yu-ming

(School of Communication and Information Engineering, University of Electronic Science and Technology of China Chengdu 611731)

In this paper a rotation and PEGASIS-based energy-efficient chain routing protocol is proposed to reduce energy consumption in wireless sensor nodes and prolong the life span of wireless sensor networks (WSNs). The proposed protocol is an improved protocol of geographical adaptive fidelity (GAF) protocol based on (power-efficient gathering in sensor information system, PEGASIS) chain protocol. Simulation results demonstrate that the proposed protocolhas better performance in energy conservation than traditional routing protocols, such as PEGASIS, LEACH and EEPB. Moreover, more uniform distribution of the wireless sensor nodes could be realized when more than a half of the sensor nodes died.

energy-efficient (EE); rotation; routing protocol (RP); wireless sensor networks (WSN)

TN919

A

10.3969/j.issn.1001-0548.2015.02.006

2013-07-15；

2014-12-31

国家自然科学基金(61104042)；中央高校基本科研业务费专项资金(ZYGX2012J082)

于秦(1974-)，女，博士，副教授，主要从事无线网络、移动通信和信息安全方面的研究.