无线传感器网络中PEGASIS协议的研究与改进*

刘伟强，蒋 华，王 鑫

(桂林电子科技大学计算机科学与工程学院，广西桂林541004)

无线传感器网络广泛应用于军事、农业、智能家居等领域，它在本世纪得到了大力的发展，其中无线传感器路由协议是发展的重点［1］。通常传感器节点的能源装置不方便更换，能源问题成为制约无线传感器的关键因素［2］，因此无线传感器路由协议的首要目标是提高传感器能量的利用率，延长网络生存时间。因此，大量低功耗路由协议被提出，其中PEGASIS(Power-Efficient Gathering in Sensor Information Systems)协议是无线传感器网络中经典的低功耗路由协议之一，它是由Stephanie Lmdsey等人在LEACH协议基础上提出的链式协议［3］。该协议的主要思想是将网络中所有节点连成一条链，基站在链中选择一个簇头，通信时信息从链的两端开始沿链将数据传输给簇头，再由簇头发送给基站。相对于LEACH协议，该协议在一定程度上提高了网络能量利用率，但也产生了通信时延过长，远离基站的簇头节点容易死亡的缺点，同时网络能量利用率有待进一步提高。针对PEGASIS协议的这些不足，本文重点研究如何提高该协议的网络生存时间与降低其数据传输延迟，并提出了一个能解决这些问题的新协议。

1 相关工作

对于PEGASIS协议的研究，前人已经做了很多工作。文献［4］在PEGASIS协议基础上提出了一个新协议EECB，该协议在选择链首时将节点剩余能量与节点到基站距离考虑在内，且通过阀值方式避免了长链的出现，有效地延长了网络生存时间，但没有解决数据通信延迟问题。文献［5］通过结合LEACH协议与PEGASIS协议提出一种改进协议，该协议选簇头、成簇阶段与LEACH协议相同，簇内通信采用单跳直接通信与链通信方式相结合，簇间通信采用链式通信方式，该方式解决了PEGASIS协议中通信延迟大的问题，但没有解决长链问题。文献［6］提出一种带树几何算法(Strip Tree Geometry Algorithm)，运用该算法建链时避免了长链的产生，该协议延长了网络生存时间，但没有解决时延长的问题。文献［7］在分析了PEGASIS协议的基础上提出了分层链树的路由协议HCTRP(Hierarchical Chain-Tree Routing Protoeol)，该协议根据传感器节点与基站的距离，把整个网络划分为以基站为圆心的环状层次区域，然后构造从外层节点经由内层节点到基站的链状路由树，数据沿着链状路由树路径传输到基站，该协议在一定程度上延长了网络生存时间。文献［8］提出了EEPB协议，此协议通过引入距离门限避免相邻节点间产生长链，并且在主链的基础产生了支链，该协议避免了长链，提高了能量利用率，但同样没有解决时延大的问题。

该文在PEGASIS协议基础上采用树的思想与分簇思想提出了一种分簇成树的新路由协议。该协议通过对监测区域划分成多个子区域，节点根据自身所在的子区域建立路由树，数据沿着路由树路径传输到基站，解决了PEGASIS协议中存在长链、通信时延大的缺点，提高了网络能量的利用率。

2 PEGASIS协议描述

PEGASIS协议是由LEACH协议发展而来，但又与LEACH协议的拓扑结构大不相同，LEACH协议是簇结构，而PEGASIS协议是链式结构，它通过贪婪算法将网络中所有节点建成一条链，网络收集到的信息在链上传递至由基站选定的链头节点上，再由簇头发送给基站［9］。建链从离基站最远的节点开始，该节点发送试探信号，通过监测其他节点的应答信号的强弱来确定离自己最近的节点，并将离自已最近的节点加入链中。然后被加入的节点也按上面所述方式确定离自己最近的节点(不包括已入链的节点)并将其加入链，依此类推最终形成一条包括所有节点的链。当基站选定簇头节点后，就采用令牌控制机制进行数据传输。首先将令牌信号传递给链两端的节点，链两端的节点向链中的下一个节点发送数据，接收到数据的节点将自己的数据和接收到的数据进行数据融合处理，然后将融合后的数据再发送到下一个节点，最终由链头节点融合两端的数据并发送给基站。当链中有一个节点死亡时，网络需要重新建链［10］。

PEGASIS协议中除了“长链”两端的节点与链头节点之外，绝大多数节点只需将信息发送给离自己最近的节点，所以相对于LEACH协议，PEGASIS中所有节点平均通信距离较短，整个网络能量消耗较小。但PEGASIS协议有如下缺点:

(1)建链时会出现“长链”情况，导致“长链”两端节点过早死亡。

(2)信息从链两端传送到链头再发送给基站的过程造成的时延不可接受。

(3)一旦有节点死亡，整个网络需重新建链，网络维护代价过大。

3 PEGASIS-I协议原理

3.1 协议描述

PEGASIS-I(PEGASIS-Improved)协议运行时对基站的位置有一个要求，需要基站在监测区域的中间。该协议包括3个步骤，每个步骤下又包括若干子步骤:

第1步，基站分配工作:

(1)所有节点将自己的位置信息与ID信息发送给基站，基站将整个监测区域看成以自身为圆心的圆形区域，然后基站跟据监测区域节点的密度形成一个角度θ(0＜θ＜π/2)，并且计算每个节点离基站的距离。

(2)基站以某一标记点为参照将监测区域分成［2π/θ］个以基站为圆心扇形子区域并标上子区域标记，然后基站将节点ID与节点所在的区域一一对应起来。比如:节点V在子区域Ⅱ，基站即形成位置对应关系location(V)=Ⅱ。如图1所示。

图1 区域划分图

(3)基站做完上述工作后将节点的位置关系和节点与基站的距离等信息广播，让所有节点知道自己是属于哪个子区域内以及自己与基站的距离是多少。

第2步，每个区域的节点开始建树，建树遵循如下规则:

每个区域内节点V通过发送能量递减的测试信号，并监测应答信号来确定离自己最近的相邻节点V'，如果最近节点V'满足如下条件则将它设定成节点V的父节点:

(1)节点V'所在的区域编号和节点V相同;

(2)节点V'离基站的距离比 V离基站的距离近;

如果最近节点V'不能同时满足以上两个条件，则节点V找到离自己次近的节点，直到找到同时符合上面两个条件的且离自己最近的节点做为自己的父节点。如果节点V确定V'可以作自已的父节点，则V向V'发出想作为其子节点的信息，V'收到子节点要求加入的信息后发出“接受”信息。这样V就成为了V'的子节点，在网络通信时，V将自身收集到的数据发送给V'。

网络中所有节点按第2步的方式操作后，整个网络中所有子区域内节点匀形成了一棵路由树，如图2所示。

图2 节点数据传输路径图

第3步，数据传输阶段

数据传输从树的叶子节点开始经树枝、树干传输到树根，树根再将数据发送给基站。数据传输时遵守以下规则:

(1)如果一个节点有多个子节点，它必须为每个子节点分配数据发送时间段，避免数据接收冲突。

(2)父节点收到子节点发来的数据后须回复一条接收完毕的信息，当父节点将自己所有子节点的数据收集完后将子节点的数据与自己的数据融合，然后将融合后的数据发送给自己的父节点。如果子节点发送完信息后过一段时间没有收到父节点的回复信息则认为父节点死亡，该子节点重新按照第2步中的方法重新为自己确定父节点。

(3)如果父节点在规定的时间里没有接收到相应子节点的信息，则认为该子节点死亡，不再等待该子节点的数据。

(4)如果有新节点加入网络中，新节点先将自已的位置信息单跳直接发送给基站，基站收到信息后根据它所在的位置确定它与基站的距离以及它属于哪个区域，然后将这些信息广播给新节点，然后新节点根据这些信息按照步骤2的方法加入到其所在子区域的路由树中。

3.2 节点与子区域的对应方法

新协议中存在如何确定节点在哪个子区域的问题，此节描述了解决该问题的方法。为了对监测区划分子区域，首先基站在监测区域中距离基站x0处设定一个标记点(Mark)，然后对监测区域建立以基站为原点的直角坐标系，以基站BS与标记点Mark连成的直线为横轴X，以经过基站并垂直于横轴的直线为Y轴，并使Mark点位于X轴正半轴上。因此BS坐标为(0，0)，标记点 Mark 坐标为(x0，0)。区域内所有节点的位置坐标一一对应转换到该直角坐标系上，形成对应的虚坐标。因为节点的真正位置坐标是相对于地球来说，而虚坐标则是相对于该直角坐标系的位置。以下所称坐标均指虚坐标。

坐标系建立后，基站根据参数θ将监测区域分成［2π/θ］个子区域，将X轴正半轴上边的子区域开始从1开始编号，沿逆时针方向依次递增，如图1所示。下面是说明如何根据节点的位置来确定节点所属的子区域。

代入数据化简可得:

则向量a与b的逆时针夹角φ的表达示如下:

即设节点V(xv，yv)所在的子区域编号为φ，则φ的表达示如下:

至此，通过上述公式便可求出任意节点V所在的区域号，于是有location(V)=φ，如图3所示。

图3 区域计算说明图

3.3 能量模型

本协议能量模型与融合模型采用文献［11］中的模型。式(6)中d为传输距离，ETx(k，d)表示传感器节点发送k bit数据通过距离d时的能耗，由发射电路耗损和功率放大耗损两部分构成。功率放大耗损根据发送者和接收者之间的距离分别采用自由空间模型和多路径衰减模型。Eelec为发射电路的耗损能量。εfs和εmp分别表示两种信道模型下功率放大所需能量。式(7)表示接收k bit数据的能量耗损，仅由电路耗损引起。式(8)为将接收到的n个节点发送过来的n kbit数据与本身的k bit数据融合，融合成k bit数据再发送出去。

数据发送:

数据接收:

数据接收:

4 仿真结果及分析

利用MATLAB软件对PEGASIS协议与改进协议进行仿真比较，分别从网络的生存时间与网络延迟两方面来评价新协议的性能。仿真时因为节点所在位置是随机选取，随机因素大，所以下面每个仿真数据中除了图6的数据外其余数据匀为循环50次，取平均值后再取整的结果。仿真中所有节点固定，节点死亡后不再补充新的节点，节点分布为电脑随机分配，节点通信功率可调，即节点可以根据距离来调整发射功率的大小，其他具体实验参数如表1。

表1 参数设置

4.1 参数的确定

在新协议中θ参数非常重要，它直接影响新协议的性能。在监测区域中节点的密度不同，最佳参数值的设置也不同。下面通过仿真来确定在新协议在实验条件下最合适的参数值，使得新协议在本实验条件下达到最佳性能。图4是当θ取不同的值时，新协议运行的节点存活数与轮数关系仿真图，图中的“pi”表示 π，从图中可看出:当 θ取值为 π/8时，网络所有节点存活时间最短，新协议性能最差，当θ取值为π/3时，网络节点存活时间最长，新协议性能最好，故在该实验条件下最合适的参数值设置是 θ=π/3。

4.2 网络能量利用率

新协议的首要目标就是要提高网络能量利用率，由2.2节中簇内建树的算法可以知道每个节点均将信息发送给朝基站方向离自身最近的节点，避免了长链的出现。另外，所有树根均靠近基站，通信距离短。这些都有助于网络能量利用率的提高，下面通过仿真来验证新协议的能量效率。图4是两协议运行时轮数与网络节点存活数关系图。文中以50%节点死亡时的轮数作为网络生存时间，并对第1个节点开始死亡的轮数、10%节点死亡的轮数、30%节点死亡的轮数、50%节点死亡的轮数、全部节点死亡的轮数进行了比较，结果如表2所示。从表2中的结果我们可以看出新协议比PEGASIS协议的生存周期提高了198%，第一个节点死亡时间更是大大的推迟了，10%、30%、100%节点死亡时间也都得到了很大的改善。从以上结果可以看出新协议在网络生存时间方面相比于原协议有了长足的进步，其原因是新协议避免了“长链”且和与基站通信的树根离其站很近。

图4 θ取不同值时节点存活情况图

表2 两种协议不同生命期对比结果

4.3 通信延迟

设网络中每个节点发送信息的延迟为t，共有n个节点平分布在监测区域内。在PEGASIS协议中延迟最好的情况是基站选择了链正中间的节点作为簇头节点，此时总通信延迟T1为:

图6是两个协议延迟情况图，在计算时延时文中设定每个节点通信时延为1 ms。在新协议中各个子区域并行通信，整个网络时延等同于时延最长的子区域的通信时延。从图中可以看出，PEGASIS协议的时延很不确定，时高时低，这与该协选取的簇头位置有关，当簇头位置是通信链的中间位置时网络整体时延最小，簇头为链的两端时时延最大。新协议的时延比较固定，不会上下不停的波动。图6所表示的是每一轮通信网络的延迟情况，但轮数相同时，两协议对应的存活节点数不一定相同，不能直接得出它们延迟的对比情况，只能体现其不同生命期整延迟情况。图7是表示两协议运行时两协议延迟与网络之间的关系，它是两协议运行50次取平均值的结果，它能更清楚的表明两协议的延迟情况。文中对0%、10%、30%、50%节点死亡时的延迟进行了比较，比较结果如表3所示。从表3可以看出在0%、10%、30%、50%节点死亡时的时期新协议的延迟分别降低了70%、66%、64%、58%，数据表明:新协议有效降低了网络时延，并且存活节点越多，延迟降低的幅度越大。

图5 节点存活数与轮数关系图

图6 相同时刻延迟对比图

图7 存活节点数相同时延迟对比图

表3 两种协议不同生命期延迟情况对比结果

4.4 网络维护代价

在PEGASIS协议中一旦有节点死亡，整个网络所有节点需要重新建链，网络拓扑结构变化大，而PEGASIS-I协议中有节点死亡时，如果该节点是叶子节点则对网络拓扑结构没有影响，如果死亡节点是非叶子节点，则只需该节点的子节点重新确定其父节点，其他节点不会受到影响。总之，PEGASIS-I协议的维护简单，提高了网络能量利用率，延长了网络生存时间。

总结仿真结果，新协议相比于PEGASIS协有如下两个优点:(1)能量利用率高，有效延长了网络生存时间;(2)网络延迟低，使得网络反应更迅速;(3)网络维护消耗低。总之，新协议以上两方面明显优于PEGASIS协议。

5 结论

通过分析PEGASIS协议后发现，虽然它是由LEACH协议发展而来，相比于LEACH协议它能提高网络能量利用率，但同时存在以下几点不足:一是链的生成容易产生长链，使得长链两端节点容易死亡;二是信息延链传递使得网络延迟变得不可接受;三是网络维护消耗高，有节点死亡时需重新建链，增加了网络消耗［12］。针对这些不足，文中提出一种改进协议PEGASIS-I协议，新协议利用树的特性使节点与节点之间避免了长链，推迟了第1个节点的死亡时间，延长了网络生存周期;利用扇形分区的方式将网络分成若干个区域，减小了网络通信时延;简化网络维护方式，降低网络维护消耗。分析和仿真结果表明:改进后的算法在延长网络生存时间与降低网络延迟方面均有更优越的性能。但该协议存在树根节点通信负载过大的问题，下一步将进行如下的研究:改进树形链上节点的通信模式，减轻树根节点的通信压力。

［1］ 杨军，张德运，张云翼.基于分簇的无线传感器网络数据汇聚传送协议［J］.软件学报，2010，21(5):1127－1137.

［2］ Lee Y H，Lee K O，Lee H J，et al.CBERP:Cluster Based Energy Efficient Routing Protocol for Wireless Sensor Network［C］//Proceedings of 12th International Conference on Networking，VLSI and Signal Processing，Cambridge，20－22 February 2010，24－28.

［3］ Stephanie Lmdsey，CauligiS.Raghavendra.PEGASIS:Power-Efficient GAthering in Sensor Information Systems［J］.IEEE Aerospace Conference Proceedings，2002，3(3):1125－1130.

［4］ Yu Yongchang，Song Yichang.An Energy-Efficient Chain-Based Routing Protocol in Wireless Sensor Network［C］//2010 International Conference on Computer Application and System Modeling，2010，486－489.

［5］ 李建奇，曹斌芳，王立.一种结合LEACH和PEGASIS协议的WSN的路由协议研究［J］.传感技术学报.2012，25(2):263－267.

［6］ Se-Jung Lim，Myong-Soon Park.Energy-Eicient Chain Formation Algorithm for Data Gathering in Wireless Sensor Networks［J］.International Journal of Distributed Sensor Networks，2012，ArticleID843413，9pages，2012.

［7］ 王波，蒋卫，孙燚.改进PEGASIS的分层链树路由协议［J］.计算机系统应用，2009，12:98－102.

［8］ 余勇昌，韦岗.无线传感器网络中基于PEGASIS协议的改进算法［J］.电子学报.2008，36(7):1309－1313.

［9］ 戴世瑾，李乐民.高能量有效性的无线传感器网络数据收集和路由协议［J］.电子学报.2010，38(10):2336－2341.

［10］严英，郭丽，许建真.一种基于LEACH与PEGASIS协议的分层成链优化路由算法［J］.传感技术学报，2011，24(9):1311－1316.

［11］蒋畅江，石为人，唐贤伦，等.能量均衡的无线传感器网络非均匀分簇路由协议［J］.软件学报.

［12］Aliouat Z，Aliouat M.Efficient Management of Energy Budget for PEGASIS Routing Protocol［C］//Proc.of the 6th International Conference on Sciences of Electronics，Technologies of Information and Telecommunications.［S.l.］:IEEE Press，2012.