一种HCTRP协议下PEGASIS最优路径算法

丁绪星 王婷婷 褚 浩 李 磊

(安徽师范大学物理与电子信息学院 安徽 芜湖 241000)

一种HCTRP协议下PEGASIS最优路径算法

丁绪星 王婷婷 褚 浩 李 磊

(安徽师范大学物理与电子信息学院 安徽 芜湖 241000)

WSNs区域内节点随机分布不均匀，采用HCTRP-PEGASIS路由算法建链时仅参考节点彼此之间的距离，致使部分传感器节点做过多无用功，造成网络能源浪费、节点过早衰竭死亡。给出新算法使建链时除了参照节点彼此之间的距离，同时考虑实际传感器通信半径、相邻节点的当前能量、当前节点密度，进而确定下一个接替节点；以此类推在每个子区域内，最终形成一条数据冗余少、能耗低的数据传输链。仿真显示，相对于LEACH、PEGASIS、HCTRP-PEGASIS，网络生存周期改进算法提高约20%；网络平均总能耗平均到每个节点，改进算法至少降低9 J。故子区域内建链时，结合节点实际通信范围及节点密度等因素来选择链上组员，可以进一步降低网络功耗，提高网络能量利用率，并且延迟第一个节点死亡时间。

WSNs HCTRP协议 PEGASIS协议 路由算法

0 引 言

WSN广泛应用在军事、医疗、环境监控和行业管理等领域，故如何降低因传感器节点自身能量以及计算和通信能力限制带来的网络的能源消耗，一直是研究的热点问题[1]。在LEACH[2]协议基础上，提出一种新的基于链(Chain)的路由算法——PEGASIS协议。其相对LEACH算法而言，可降低重构簇的成本，并利用数据融合降低数据收发过程的频率，有效地减少能量的消耗。

PEGASIS是一种典型链状结构路由协议[3]。该协议的中心思想：贪婪算法将网络中所有节点构建成一条路径链，之后节点沿着路径链将数据传递至基站[4-5]，如文献[6]提出的PDCH协议。该协议采用双簇头选择链树层次结构，使非簇头与簇头之间的距离最小化，避免“长链”产生；同时也减少所有节点的数据传输接收次数。文献[7]针对PEGASIS协议过程中的数据冗余和延迟问题，提出E-PEGASIS协议，该协议将部署子集内的节点使用支配集概念来进行激活，并因传感器节点的随机分布形成随机的稀疏WSN网络部署这一属性，来确定目标链首时，需计算节点的周围节点与基站的接近度。E-PEGASIS协议不仅延长网络生命周期，同时能很好利用传感器网络部署区域的随机覆盖率。文献[8]提出的PEGASIS改进算法，该协议根据神经网络思想选择链头，运用蚁群算法遵循信息素的强度的方法，在各子区域内寻找最佳路径将数据发送至基站。此方式创建的数据路径链，致使链树更分布式。继而极大减小数据传输距离的总平方，乃至延长网络生命周期。与此同时PEGASIS改进协议动用最小化的传输距离和的平方和，来间接的反映节点彼此之间的距离和节点的剩余能量。

除了以上改进协议，近几年又提出了基于HCTRP协议下PEGASIS算法；如文献[9-10]，该算法为预防“长链”现象出现，先将整个区域划分为均等的子区域，然后在各个子区域内并行构建多条子数据链，以此将整个区域覆盖，完成数据汇集任务。是以用“化整为零”的思路既减少数据链的长度，又降低出现“长链”机率。不过综上分析发现提出的大多数优化PEGASIS协议都未注意以下问题[11]：

1) 比拟位于基站近的孤独节点，距离远的孤独节点与BS通信，需要消耗更多的能量。

2) 均在节点随机均匀分布的情况下，运用方法来进一步提升网络生命周期以及减少网络功耗，而未研究网络节点随机分布不均匀情况下算法的适应性。

依据以上问题以及更大程度上防止“长链”、减少数据传输过程中传输次数，本文在基于HCTRP协议的PEGASIS算法基础上深化研究。本文算法为建设最优数据传输路径，遴选链上成员不仅考虑节点彼此之间的距离，而且还有节点剩余能量、周边节点密度、节点通信半径等因素。如此在节点随机不均匀分布境况(特别是节点密集区域)建链时，通过探寻出一条最优路径链，解决建链过程中部分节点做过多无用功以及数据传输路径链迂回复杂等问题。

1 HCTRP-PEGASIS协议

在PEGASIS基础上，提出的HCTRP-PEGA-SIS路由算法[12]。该算法包括两个阶段，即节点区域划分阶段和节点建链及数据传输阶段。HCTRP-PEGASIS算法网络结构如图1所示。

图1 HCTRP-PEGASIS算法

1.1 节点区域划分阶段

在系统初始化阶段，根据基站BS划分区域有很多方式。例如根据节点与BS的距离，将整个区域分为逐次叠加同心圆子区域，节点随机分布在各个层次里。如图1(a),而每个子区域内节点分布密度等其他参数可由BS根据实际情况(例如节点数量，区域大小等)确定。

1.2 节点建链阶段

子区域划分好后，经过节点建链阶段后形成的链树如图1(b)所示，以某一子区域为例，建链过程如下：

1) 选出该子区域里距离BS最远的节点定为根节点，随即从根节点开始建链。

2) 计算根节点与附近所有邻居节点之间的距离，记为di。

3) 将其中最小值di所对应的neighbor定为链上承接节点；循环2)和3)直到建链传承到领导节点，进行4)。

4) 领导节点则将整个链上的数据接收并融合后Broadcast给BS。

5) 确立孤独节点(未当选为链上成员节点)，使孤独节点直接与BS通信。

1.3 能耗模型

承接节点接收上一节点采集的数据以及将自身采集的数据与接收数据融合后传递给下一承接节点都须要消耗一定的能量，故在这个过程应用能耗模型为：在无线通信电路发送和接收一字节的能量消耗分别为Et和Er，而Et和Er计算如式(1)和式(2)所示。

Et=α+λ×dn

(1)

Er=β

(2)

式(1)和式(2)中参数具体数值如表1。假设节点a向节点b发送m bit数据包，b将自己的数据与mbit的数据包融合后，向节点c发送的是一个Mbit数据包。在这个过程a发送数据包消耗的能量则为m×Et，b接收数据包消耗的能量则为m×Er。

表1 参数设置

2 HCTRP-PEGASIS改进协议

HCTRP-PEGASIS算法建链过程是在传感器节点密度均匀随机分布情景下实行，然而实际WSN应用环境，传感器节点是随机不均匀分布(可能某些区域传感器节点分布得比较密集)，便意味着某区域因分布过多节点，致使部分传感器节点复式采撷已有数据，导致网络资源浪费。同时也容易形成曲折复杂的“长链”，增加整个网络功耗。是以本文根据传感器实际通信半径对HCTRT—PEGASI-S协议作进一步的优化。

本文算法是在节点建链阶段作出改进，关于各子区域内的节点，不是直接使用贪婪算法将各子区域内所有节点尽可能都选用为链上组员，而是综合考虑预选节点的剩余能量、预选节点与上一承接节点之间的距离、预选节点周围节点分布密度以及节点通信半径等因素，来挑选链上成员节点。如此在各子区域即确立一条最优数据传输路径链。

2.1 传感器网络模型

创建一个由N个传感器节点组成的WSN网络，该网络应用环境为周期性的数据收集，并基于以下假设：

(1) 基站BS节点固定设立在测试区域的中心位置。

(2) 所有节点完全相同，随机不均匀散布于网络区域内；每个节点不仅可以和网络中其余任何节点相互通信，也可以直接与BS节点通信。

(3) 节点能量有限且初始能量相同。

(4) 信道对称且无线电信号在各个方向上能耗相同。

(5) 节点传输数据消耗的能量取决于传输离。

2.2 算法过程

2.2.1 改进算法主链处理方式

本文改进算法节点区域划分方式：BS放置在坐标原点且每象限均二等分，如此将整个网络平均划分为八个子区域。每个子区域内，首先将距离基站BS最远的节点设置为开始节点(Startnode)，距离BS最近的节点设置为领导节点(Leadnode)。然后Startnode参考传感器实际通信半径D，则会在通信D范围外的繁多节点来选择承接节点；再综合考虑预选节点的当前能量、周围预选节点数目、Startnode与预选节点之间距离。现为说明方便将这些因素借用参数Edist表示，则参数须满足式(3)比例关系。

最后，Startnode再依据式(3)计算参数Edist，挑选链上下一承接节点，Edist计算如公式：

Edist=(dmax/d)+(Eroot/Einit)

(3)

其中dmax为网络中任意两个节点之间最远的距离。Eroot为预选节点的当前能量，Einit为节点的初始能量且为固定值。计算Startnode与附近所有预选节点的Edist值，最终确定最大值Edist所对应的节点成为链上成员。随之承接节点重复以上工作，直到承接到Leadnode，则主链路径创建完毕。其具体流程如图2所示。

图2 构建主链流程图

2.2.2 改进算法孤独节点通信方式

HCTRP-PEGASIS协议中孤独节点是与BS节点直接通信，以致部分孤独节点传送数据，因距离BS节点耗费大量能量而过早死亡。为延长孤独节点寿命，本文算法改进方式：将孤独节点直接与周围已创建的某条数据路径链上的某个节点进行通信。孤独节点同样根据与附近所有数据链上节点的距离以及链上节点的当前能量，来选择中继节点。为方便计算现用参数edist来表示，edist计算如公式：

edist=(d/dmax)+(einit/eclust)

(4)

其中dmax为网络中任意两个节点之间最远的距离，einit为所选链上某节点的当前能量，einit为节点的初始能量且为固定值。

孤独节点通信方式如流程图3所示。孤独节点按照此方式间接与BS节点通信，使其降低能量消耗、通信省时便利。

图3 孤独节点流程图

3 仿真结果及分析

本文采用Atos-SensorSim仿真平台，将LEACH、PEGASIS、HCTRP-PEGASIS算法、 HCTRP-PEGASIS改进算法,分别在100 m×100 m网络环境下进行仿真。若节点能量小于1 J时，则判定节点死亡，且以后不再补充新的节点。其他具体实验参数如表2所示。

表2 参数设置

将200个传感器节点随机不均匀地散布在100 m×100 m的区域内，在系统初始化初阶，区域划分后在第三象限随机节点分布90个，第四象限节点随机分布60个，其他两个象限各随机分布25个节点，如图4所示。

图4 100 m×100 m的区域划分

图5为HCTRP-PEGASIS协议仿真结果。从图5中直观观察出，每一区域内从最远节点开始建链，之后直接选择其最近的节点作为下一承接节点，直至将该子区域内的所有节点连贯为一条数据传输链。确定承接节点时，子区域内的数据同步经由开始节点逐层向内传递至领导节点，最终领导节点将该区域内全部数据接收融合后传递给基站BS。

图5 HCTRP-PEGASIS算法

图6是HCTRP-PEGASIS算法孤独节点通信方式的仿真结果，从图6中我们看到距离基站很远的孤独节点，依旧采用与BS直接通信的话，孤独节点则会大量消耗自身能量，如此缩短了节点的存活周期。综合图5和图6的仿真结果可知，HCTRP-PEGASIS算法尽管在一定程度上避免出现“长链”以及减小时间延迟。但是若某区域节点分布较密集的话，不仅“长链”现象如故，而且数据传输路径链迂回弯曲复杂。如此因部分节点重复采集数据造成数据冗长多余。

图6 HCTRP-PEGASIS协议孤独节点通信方式

图7为本文改进算法的仿真结果。从图中可以得出，在每一子区域内从最远节点(Startnode)建链；开始节点根据参数D和式(3)确定下一承接节点。当承接节点确定后，则升级为新的Startnode后，然后继续根据参数D和Edist挑选新的承接节点；是以在各子区域内构建一条最优数据路径链。这样节点采集的数据则沿着路径链传输直至领导节点，之后经由领导节点融合传输至BS。由图7我们可以看出，改进协议特别是在节点密集处，仅从星罗棋布的节点里抉择其中能量大且与上一个承接节点距离适中的节点作为该链下一承接节点，进而极大程度减少链的蜿蜒曲折和复杂度。

图7 HCTRP-PEGASIS改进算法

图8是HCTRP-PEGASIS改进协议孤独节点通信方式的仿真结果。从周围已创建的数据链根据式(4)从链上选择一节点，该节点不仅距离孤独节点近而且剩余能量大，孤独节点直接将采集的数据传送给该节点，然后经由该节点所在的数据链传输至BS，以此方式改进孤独节点的通信方式。

图8 HCTRP-PEGASIS改进算法孤独节点

现我们从网络生命周期和网络消耗两个方面，分析比较LEACH、PEGASIS、HCTRP-PE-GASIS协议、HCTRP-PEGASIS改进协议的性能指标。

从图9观察出，HCTRP-PEGASIS改进协议相比较HCTRP-PEGASIS协议、LEACH协议，很大程度上延长第一个节点死亡时间。相比较LEACH协议，本文改进算法延长近似45轮；相比较HCTRP-PEGASIS协议，本文改进协议延长近似30轮。若定义网络中最后一个节点死亡的轮数为网络生命周期，由图7可观察出HCTRP-PEGASIS改进协议最后一个节点死亡时所运行的轮数达95轮，而HCTRP-PEGASIS协议最后一个节点死亡时的网络生命周期轮数约为75轮，故在节点随机分布不均匀WSN网络下，HCTRP-PEGASIS改进协议比HCTRP-PEGASIS算法的生存周期提高了至少20%。

图9 节点存活对比图

LEACH、PEGASIS协议、HCTRP-PEGASIS协议、优化HCTRP-PEGASIS协议四种算法的网络能耗统计图如图10所示。由图10可观察出在整个过程中，四种协议的网络总能耗随着时间的推移，均是逐步增加，不过HCTRP-PEGASIS改进协议的网络总能耗低于其他三种协议的网络总能耗。PEGASIS协议和HCTRP-PEGASIS协议网络能耗基本相同，前20轮HCTRP-PEGASIS改进算法与LEACH两者的网络能耗相差甚微，但是20轮到50轮，HCTRP-PEGASIS改进算法对比LEACH，平均降低总能耗平均到每个节点可以降低能耗至少32 J。对比PEGASIS协议和HCTRP-P-EGASIS协议，前45轮HCTRP-PEGASIS改进算法平均降低总能耗平均到每个节点可以降低能耗100 J。因此在网络节点随机不均匀分布的环境中，按HCTRP-PEGASIS优化算法所建的数据传输链树，不仅降低整个网络功耗，而且合理利用网络资源，并延长网络的生命周期及进一步减少时间延迟。

图10 能量消耗对比图

4 结 语

HCTRP-PEGASIS路由协议在节点稠密区域建链仍然会产生“长链”以及部分节点未被合理利用，导致网络能耗大及网络资源的浪费。针对以上问题，将HCTRP-PEGASIS协议节点建链方式作出改进。其优化建链的思路：每一周期内为开拓最优数据路径链，挑选链上成员节点时，不仅考虑预选节点与开始节点的距离，同时考虑预选节点的当前能量及周围预选节点数目，来确立每一个承接节点，进而动态构建数据链。相应地也进一步改进了孤独节点通信方式。从网络消耗和网络生命周期两个方面，本文提出的基于HCTRP协议下的PEGASIS优化路由算法优于经典的LEACH 协议、PEGASIS协议、HCTRP-PEGASIS协议。

本文提出的HCTRP-PEGASIS改进协议虽然延长了网络的寿命，但是其寿命时间有待延长。今后需要继续优化该算法的主链建链方式和孤独节点的通信方式(着重研究孤独节点的通信方式)，使之具有更长的网络生命周期。

[1] Guo W,Zhang W,Lu G.PEGASIS Protocol in Wireless Sensor Network Based on an Improved Ant Colony Algorithm[C]//Second International Workshop on Education Technology and Computer Science.IEEE Computer Society,2010:64-67.

[2] Sony C T,Sangeetha C P,Suriyakala C D.Multi-hop LEACH protocol with modified cluster head selection and TDMA schedule for wireless sensor networks[C]//Communication Technologies.IEEE,2015:539-543.

[3] Lindsey S,Raghavendra C S.PEGASIS:Power-efficient gathering in sensor information systems[C]//Aerospace Conference Proceedings.IEEE,2003,3:3-1125-3-1130.

[4] Yong-Chang Y U,Wei G.An Improved PEGASIS Algorithm in Wireless Sensor Network[J].Acta Electronica Sinica,2008,36(7):1309-1313.

[5] Gupta M,Saraswat L.Energy aware data collection in wireless sensor network using chain based PEGASIS[C]//Recent Advances and Innovations in Engineering (ICRAIE),2014.IEEE,2014:1-5.

[6] Wang L,Bi W,Cai Z,et al.Improved Algorithm Of Pegasis Protocol Introducing Double Cluster Heads In Wireless Sensor Network[C]//Computer,Mechatronics,Control and Electronic Engineering (CMCE),2010 International Conference on,2010:148-151.

[7] Ghosh S,Mondal S,Biswas U.Enhanced PEGASIS using ant colony optimization for data gathering in WSN[C]//International Conference on Information Communication and Embedded Systems,2016:1-6.

[8] Li T,Feng R,Fan Z,et al.An Improved PEGASIS Protocol for Wireless Sensor Network[C]//International Conference on Computer and Computing Science.IEEE Computer Society,2015:16-19.

[9] Chen Y L,Wang N C,Chen C L,et al.A Coverage Algorithm to Improve the Performance of PEGASIS in Wireless Sensor Networks[C]//Acis International Conference on Software Engineering,Artificial Intelligence,NETWORKING and Parallel/distributed Computing.IEEE,2011:123-127.

[10] Jin Wang,Jiayi Cao,Yiquan Cao,et al.An Improved Energy-Efficient Clustering Algorithm Based on MECA and PEGASIS for WSNs[C]//Third International Conference on Advanced Cloud and Big Data.IEEE Computer Society,2015:262-266.

[11] Mishra A K,Rahman R U,Bharadwaj R,et al.An enhancement of PEGASIS protocol with improved network lifetime for Wireless Sensor Networks[C]//Power Communication and Information Technology Conference.IEEE,2016:142-147.

[12] Jung S M,Han Y J,Chung T M.The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS[C]//The International Conference on Advanced Communication Technology.IEEE,2007:260-265.

ANOPTIMALPATHALGORITHMUNDERHIERARCHICALCHAIN-TREEROUTINGPROTOCOLBASEDONPEGASIS

Ding Xuxing Wang Tingting Chu Hao Li Lei

(CollegeofPhysicsandElectronicInformation,AnhuiNormalUniversity,Wuhu241000,Anhui,China)

In WSNs, the nodes have uneven distribution. When the hierarchical chain-tree routing protocol based on PEGASIS is used to build the chain, only the distance between nodes is referred to each other. Resulting in some of the sensor nodes do too much power, resulting in waste of network energy, node premature failure of death. In addition to the distance between the nodes, our approach also considered the actual sensor communication radius, the adjacent node’s current energy, the current node density, so as to determine the next successor node. By analogy, a data transmission chain with less data redundancy and low energy consumption was developed in each sub region. The simulation results showed that the proposed algorithm improved by about 20% in network lifetime and could reduce energy consumption of network among each node by at least 9 J compared with LEACH, PEGASIS, HCTRP-PEGASIS. Therefore, it is possible to reduce the network power consumption, enhance the energy efficiency and delay the first nodes death time by combining the node’s actual communication range and node density when the sub region is built into the chain.

WSNs HCTRP protocol PEGASIS protocol Routing Algorithm

TP393.04

A

10.3969/j.issn.1000-386x.2017.10.030

2016-10-28。国家自然科学基金项目(61401004)；安徽师范大学创新基金项目(2015cxsj121)。丁绪星，教授，主研领域：物联网技术，汽车电子与数字信号处理。王婷婷，硕士生。褚浩，硕士生。李磊，硕士生。