基于PEGASIS协议的改进算法

基于PEGASIS协议的改进算法摘要作为基于链状机构的路由协议的代表，PEGASIS协议存在三方面的不足：一是链的生成算法会导致相邻节点间产生长链；二是链头节点选取方法会导致节点间能量消耗不均衡；三是链头节点的通信频率增加了通信开销。本文基于PEGASIS协议提出了一种新算法，通过引入距离门限避免相邻节点间产生长链；通过考虑节点剩余能量以及节点到基站的距离来选取链头节点；通过降低链头节点的重选频率来节省通信开销。关键词：距离门限；路由算法；选取策略AnImprovedAlgorithmBasedonPEGASISProtocolsABSTRACTAsthechain-basedroutingprotocolonbehalfofinstitutions,therearelessthanthreePEGASISprotocolaspects:Firstgenerationalgorithmchainwillresultinalongchainbetweenadjacentnodes;thesecondisthechainheadnodeselectionmethodwillresultinunevenenergyconsumptionbetweennodes;Third,theheadnodechaincommunicationfrequencyincreasedcommunicationoverhead.BasedPEGASISprotocolproposesanewalgorithm,byintroducingathresholdtoavoidlongdistancebetweenadjacentnodesinthechain;andbytakingintoaccounttheresidualenergyofnodetonodedistancefromthebasestationtoselecttheheadnodechain;chainbyreducingthefrequencyofthere-electionoftheheadnodetosavecommunicationoverhead.Keywords:distancethreshold;routingalgorithm;selectionstrategy1.引言在无线传感器网络中，节点的能量是有限的，一旦自身的电量消耗完，对节点进行充电或者更换电池都是不易实现的。因此，如何提高网络能量的有效性、均衡节点能量的消耗、延长网络的寿命等问题便成为无线传感器网络路由协议所要考虑的重要问题。PEGASIS协议是一种典型的基于链状结构的路由协议，是一种基于LEACH协议基础上建立起来的路由协议，其核心思想是利用贪婪算法生成一条由所有节点组成的单链，链上的节点已知自己所在的地理位置，链上的节点只与自己的邻居节点通信。除端点节点外，每个节点都要将自己收到的数据与自己产生的数据进行数据融合，然后再将融合后的数据沿簇头节点的方向传递给相邻节点，一直持续到数据到达簇头节点，簇头节点通过数据传送至基站（汇聚节点）。虽然PEGASIS在节点能耗均衡和网络寿命延长方面取得了较好的结果，但是PEAGSIS仍然存在以下三方面的不足：一、由于PEGASIS的建链方法是基于最近邻居节点算法，已经加入链的节点和死亡的节点均不能被再次访问，这就难免会造成相邻节点间长链的产生；二、采用簇头节点轮流担任的机制，会导致离基站较远的节点率先死亡；三、每一轮通信结束后都重新选取链头节点，会增加通信开销。图1利用PEGASIS算法建链很显然，图中有几个节点之间的距离比其他链路长的多，我们称这些链路为长链。这些节点在发送数据时要消耗大量的能量。为了节约能量，在建链的过程中就必须采取措施以避免邻居节点间长链的产生，下面就一问题展开相应的探究。2.PEGASIS的算法改进建链方法也是从离基站最远的节点开始建链，为了判断相邻节点之间的链路是否为长链，设定一个用于判断链路是否为长链的距离门限并用chd表示，如图2所示，假设已经有i个节点加入了链，节点v和节点v+1之间的链路长度用vd表示。d1d2d31234i-1id图2由i个节点组成的部分链如果相邻两个节点之间的链路长度大于等于chd，便称两个节点之间的链路为长链，采用方程（1）定义距离门限：11[/(i1)],1,2...i1ichvvdd（1）在所有待加入的节点中，假设节点i+1是最靠近节点i的节点。在节点i+1加入链之前，现将自身与节点i之间的距离id与chd进行比较:（1）如果ichdd，表示节点i+1和节点i之间的链路不是长链，那么节点i+1通过直接与节点i相连的方式加入链；（2）如果ichdd，表示节点i+1和节点i之间的链路是长链，这时节点i+1不能直接与节点i相连，节点i+1将从链上找出距离自身最近的节点。假设在所有已经加入的节点中，节点j离节点i+1最近。如果节点i+1与节点j之间的距离小于chd，那么节点i+1将通过与节点j相连的方式加入链；如果节点i+1与节点j之间的距离大于等于chd，那么说明此时长链不可避免，节点i+1仍然通过与节点i相连的方式加入链。图3改进算法建链取=1.1，重新计算后得到的链不再是单链，而是有分支的链，图1中的长链已经不存在了。所以通过设立距离门限的建链方法可以有效地避免相邻节点间产生长链，从而可以有效地节约能量。如果的取值为无穷大，那么距离门限将趋于无穷大，这将导致任何两个节点之间的距离都将小于chd，即任何两个节点之间都不会产生长链，在这种情况下，改进的算法与PEGASIS算法完全相同。3.结论通过分析典型的基于链状结构的PEGASIS算法，我们发现虽然PEGASIS算法在能耗方面比LEACH算法优越，但是同样存在着不足：一是链的生成算法容易导致相邻节点间产生长链；二是由于链头节点选取方法容易导致节点间能量消耗分布不均匀；三是每一轮通信结束后都重新选取链头节点，增加了通信开销，本文针对第一点提出了改进算法，通过在建链过程中引入距离门限避免相邻节点间产生长链的方法，来减少能量的消耗。