基于蚁群算法和能耗均衡的改进LEACH协议*

2016-07-05周智勇王海涛王世界

通信技术 2016年4期

关键词：蚁群算法

周智勇，陈　晖，王海涛，王世界

(1.解放军理工大学通信工程学院研三队,江苏南京 210007；2.解放军理工大学训练部, 江苏南京 210007)

基于蚁群算法和能耗均衡的改进LEACH协议*

周智勇1，陈晖2，王海涛2，王世界1

(1.解放军理工大学通信工程学院研三队,江苏南京 210007；2.解放军理工大学训练部, 江苏南京 210007)

摘要：在分布式传感器网络的场景下，结合传统的LEACH协议提出了一种基于有限信道信息的蚁群优化(ACO)路由算法。该算法中传感器节点只需要获取与相邻节点间的信道信息，而不需要了解网络的全局信息，就能够逐步逼近最优路径。在此基础上，提出了一种基于能耗均衡的路由传输方案，有效改善了LEACH协议中簇头节点能耗不均衡的情况。仿真实验表明：基于蚁群算法和能耗均衡的改进路由方案，能够利用局部信息快速搜索到能耗最低的路径，并在传输过程中有效地均衡簇头能耗，从而有效提高了网络生存时间。

关键词：网络生存时间；LEACH协议；蚁群算法；能耗均衡

0引言

近年来，无线传感器网络(wireless sensor networks, WSNs)技术在物联网、战场目标监控和信息收集等领域的得到了广泛的应用[1]。传感器网络由分布在一定区域内的大量传感器节点和负责收集信息的汇聚节点组成。通常情况下，传感器节点由自身携带的电池供电，因而能量有限并且难以再次充电。如何降低传感器网络中的能量消耗已经成为了当前传感器网络的研究热点，而路由协议的设计就是其能耗优化的关键技术之一。

文献[2]提出的LEACH(low energy adaptive clustering hierarchy)协议是一种典型的分层路由协议，LEACH协议通过簇结构分层的方式,当传感器节点有传输数据包的需求时固定向上层的簇头节点发送数据包，少量的簇头节点间通过接力等方式将数据包传送到Sink节点处。这种分层的方式有效避免了节点在传输信息时的无方向和无序性，避免信息洪泛所造成的网络冗余信息过多的现象。文献[3-6]等对传统的LEACH进行了改进，其中文献[3-4]主要针对LEACH协议中簇头节点的选取规则进行重新设计，在簇结构形成阶段选取簇头时考虑各个传感器节点的剩余能量、与其他节点的平均距离等因素，文献[5-6]则在不同限制条件下对于簇结构的形成和簇头节点的形成进行了讨论。可以看出，当前对于LEACH协议的改进主要集中在LEACH协议第一阶段，也就是对于簇结构和簇头节点选取的规则进行优化。而对于簇形成之后簇头节点信息传递过程中的不同路由方式对于提升网络生存时间的影响研究则比较少，尤其是对于没有统一的管理节点，各个节点均不了解网络全局信息的分布式传感器网络的场景的研究比较缺乏。

文献[7]提出的定向扩散的方法，使距离Sink节点较远的外层节点方向性地向距离Sink节点较近的节点传送数据。文献[8-10]提出在分布式传感器网络中基于搜索树的路由方案。可以发现，当前对于簇结构形成之后路由的搜索主要以能耗最低的最优路由为目标。文献[11]的NBEERP(negotiation-based energy efficient routing protocol)路由协议提出节点保留多条可以到达网络汇聚节点Sink的路由，但其保留多条路径的目的在于提高网络的鲁棒性，而没有关注保留多条路径对于均衡簇头节点能耗、提升网络生存时间的意义。针对这一研究现状，本文提出了一种能够综合利用多条路径均衡传送信息的路由传输方案。

文章着重了研究基于蚁群算法和能耗均衡的LEACH路由方案，并对该方案的网络生存时间和覆盖性能进行了仿真和对比，具体的工作和章节安排如下所示：

(1)第二部分在接力传输方式下对传感器网络的能耗情况进行系统描述和公式建模，对与传统的LEACH协议和蚁群算法的运行过程进行了简要的描述；

(2)第三部分主要描述了本文提出的基于蚁群算法和能耗均衡的路由方案的运行过程，给出算法的细节，并对该方案的有效性进行了初步的分析；

(3)第四部分在分布式传感器网络中基于有限的信道信息条件下对于蚁群算法搜索最优路径的有效性进行了仿真验证，并对本文提出的基于蚁群算法和能耗均衡的路由方案与其他文献中提出的路由方案进行了比较仿真。

(4)第五部分对实验结果和本文的主要工作进行总结。

1模型描述

1.1通信模型

传感器网络采用传统的LEACH分簇路由协议[2]。设定我们需要监控的区域为二维区域A，以汇聚节点Sink(0,0)为圆心，半径为y=250 m的圆形区域。监控目标D在区域A内随机出现。当监控目标D在传感器节点m的感知距离内时，传感器节点m生成可以传输的信息。生成的数据包将通过LEACH协议传输到汇聚节点Sink处。

1.2能耗模型

本文中点对点通信采用QPSK方式，根据文献[12]，该通信方式的误码率特性为：

(1)

bQPSK=sin2(π/4)

(2)

式中，ρ表示接收端信噪比。若通信需要的最低误码率要求为ΨQPSK≤ρrequire时，通过查表的方式可以逆向得到最低接收信噪比为ρ0。发送功率与接收端信噪比满足路径损耗方程：

(3)式中，P、N0分别为发送功率、噪声功率，h为理想瑞利信道的衰落系数，d为发送端和接收端的距离，α为路径损耗系数，Gt、Gr分别为发送和接收天线增益。当ρ=ρ0时，可以计算出发送端需要的发送功率：

(4)

1.3LEACH协议

LEACH协议的运作过程可以准备阶段和稳定阶段，在准备阶段进行簇头节点的选取和簇的形成，在稳定阶段进行数据的搜集和传输。网络循环经历准备阶段和稳定阶段。如图1所示。

图1　LEACH协议运行过程

在准备阶段，节点随机被选作簇头节点，所有簇头节点广播通告信息ADV，其他传感器节点根据接收到的不同的ADV信号强度选择加入信号最强的簇头所在的簇。

在稳定阶段，当有传感器节点需要向Sink节点传输数据，该节点首先将数据包发送至其所在的簇的簇头节点，由簇头节点通过其他簇头节点将信息接力到Sink节点处。

1.4蚁群算法

蚁群算法(Ant Colony Algorithm, ACO)是一种新兴的仿生算法，具有较强的鲁棒性和优良的分布式计算机制，适合本文分布式传感器网络的场景中。蚁群算法用于解决本文路由搜索为的基本流程如图2所示。

图2　蚁群算法运行流程

1.5网络生存时间

文献[13-15]对网络生存时间进行了不同的定义，其中文献[13-14]将网络生存时间定义为从网络开始运行到出现能量耗尽的节点时所经历的时间，而文献[15]将网络生存时间定义为从网络开始运行到网络对监控目标区域的覆盖率下降到容忍值的时间。本文采取前一种的定义方式，这是因为一旦网络中出现死亡节点，死亡节点周边其他传感器节点的能耗急剧增加，导致其他的传感器节点很快耗尽电池的能量。能够有效推迟第一个节点的死亡时间的节点分布模型具有很大可能能够推迟大部分节点的死亡。

2基于蚁群算法和能耗均衡的LEACH路由方案

在本文提出的基于蚁群算法和能耗均衡的LEACH路由方案中，蚁群算法主要用于在LEACH协议中簇结构形成之后簇头间的路由搜索过程。由于蚁群算法只需要各个簇头间的信道信息而不需要了解网络的全局信息，因而蚁群算法的路由搜索方案适用于不存在中心控制节点的分布式传感器网络当中。各个簇头节点间的信道信息可以在簇头节点选取和簇结构形成阶段获取，各簇头节点根据其他簇头节点广播的ADV信息，获取临近的信道状态，并将这些信道状态作为初始的局部信息。

各簇首节点确定初始信道信息之后，向周围簇头发送少量数据，数据的在节点之间的接力传输过程遵循蚁群算法。各数据包每前进一步，所在的簇首节点即存储并更新禁忌表(这里禁忌表即为数据包已经访问过的簇首集合)，若发现禁忌表中已经包含了Sink节点，则立即停止该数据包的传递。将所有数据包均前进一步作为一个循环，每次循环之后需要进行信息素的更新，即各簇首节点根据自身发送功率分布情况，以节点间传输的功率信息类比作为蚁群算法中的信息素进行实时更新，进而获得新的路由转移概率值，为下一个循环中各数据的传递提供参考。至此，蚁群路由算法的一个运转周期结束。经过足够多个周期的运转之后，各簇首节点能够根据所存储的转移概率值和禁忌表信息，建立路由表。

为了找到与Sink之间的最优路径，簇头节点需要根据反馈信息不断更新和存储最优路径。通过这一过程，能够实现从局部最优路径逐步逼近全局最优路径。

能耗均衡的方案主要用于网络稳定运行阶段，其主要思想是当簇头节点需要向Sink节点传输数据时，依概率选择能耗最低和次最低的路径进行传输。能耗均衡的主要目的是避免过度使用同一条路径对该路径上的传感器节点造成过大的能耗压力。本文设定选择最优能耗路径和次优能耗路径的概率与其路径能耗成反比，即能耗较低的路径被选择的概率大，而能耗较高的路径被选择的概率小。设定选择最优路径的概率为：

(5)

选择次优路径的概率为：

(6)

式中，Eoptimal和Esub_optimal分别表示最优路径和次优路径上的能耗。网络经过足够长时间的运行，最优和次优路径上的能耗均为：

(7)

虽然能耗均衡的方法提升了每次传输所消耗的能量，但能耗均衡的方法能够较好的分配数据传输所产生的传输能耗，降低只利用最优路径进行传输对于最优路径上的节点的能耗压力。可以推测，当网络规模较大，尤其是簇头节点数量较多时，最优路径和次优路径能耗差值较小，此时能耗均衡的方案效果更佳明显。本文提出的基于蚁群算法和能耗均衡的LEACH路由方案具体细节如下：

算法名称：基于蚁群算法和能耗均衡的LEACH协议改进方案。

输入：传感器节点与邻近节点间信道信息。

输出：

步骤1：

根据LEACH协议，网络中的节点选举簇头节点，簇头节点向周围节点等功率广播被选作簇头节点的信息ADV，其他节点依据接收信号ADV的强度加入各个簇，其他簇头节点根据接收信号ADV得到信道信息。

步骤2：

整个论坛都炸开来，网友回帖回了十几页，有鼓励，有惊叹，有支持，惟独没有抨击。太多人知道罗漠的寂寞，有人对他说，你们的爱情感动了所有人，可是逝者已矣，如果楚西有灵，她也必是不愿见你孤独一生。

各簇头节点根据先验信息和功率信息素初始值，对各自状态转移概率进行初始化设置。随后各簇头根据初始转移概率向Sink节点发送少量数据包，任意数据包在接力传输过程中每实现一跳，相应的簇头节点立即对禁忌表进行修改并存储，当全部数据包均前进一步完成一个周期之后，所有簇头节点更新功率信息素，并计算存储新的状态转移概率值，进入新的周期。经过充分迭代之后，蚁群算法实现收敛，输出路由表信息。

步骤3：

根据步骤4输出的路由表信息，各个簇头节点都能搜索各自到Sink节点的能耗最优和次优路径，并将最优和次优路径保存。

步骤4：

步骤5：

经过一段时间的运行，网络进行簇头节点的重新选举和簇的重构。

3仿真和数据分析

设定监控区域为二维区域A为以汇聚节点Sink(0,0)为圆心，半径为y=250m的圆形区域。需要监控的目标随机出现在区域A内，且目标的分布满足均匀分布。区域A内传感器总数为100个。其它仿真参数的设置如表1所示。

表1　仿真参数设置

图3展示了传统的以能耗最低路径为搜索目标的方案和本文基于ACO和能耗均衡的方案网络的生存时间的对比。这里的网络生存时间指网络从开始运行到网络出现第一个节点因耗尽能量而死亡的时间。从图中可以看到，在5次仿真中，本文提出的基于ACO和能耗均衡的LEACH算法能够有效延长网络的生存时间，提升的幅度最大可以达到12.5%。从而说明，能耗均衡能够较好地均衡网络中各个节点的传输能耗，从而推迟网络中第一个节点死亡时间的到来。

图3　网络生存时间比较

本文进而仿真了网络的覆盖率随着时间的变化情况。网络覆盖率定义为网络中所有传感器能够探测到的区域面积占目标总区域的比例。选择对于网络的覆盖率变化情况进行仿真的原因在于网络覆盖率的变化很大程度上反映了网络中节点的死亡情况。网络覆盖率的下降说明网络中死亡节点数量的增加。另外，网络覆盖率是网络实现其功能最重要的指标，当覆盖率下降到一定程度时网络已经失去正常运行的功能。

图4展示了在网络达到网络生存时间后，即出现第一个节点死亡后，网络覆盖率随时间变化情况。仿真中每隔10 000轮进行网络覆盖率的测算，由于仿真采用蒙特卡洛方法，因而曲线呈现略微的抖动。从图中可以看出，两种方案的初始覆盖率相当，并随着时间的推移逐渐下降，说明不断有节点因为能量耗尽而死亡。对比文献[9]中的搜索树的路由方法和本文中的基于ACO和能耗均衡的LEACH方案的覆盖率情况，网络在9×105轮之前，本文提出的方案覆盖率较高，而在9×105之后，本文的方案覆盖率较低。而网络在9×105轮时网络的覆盖率为50%，即网络只能对50%的区域实现有效的探测和信息感知，网络已经基本失去其基本功能。因而可以总结：本文提出的基于蚁群算法和能耗均衡的LEACH方案在网络正常运行的大部分时间覆盖率较之前以能耗最优路径为搜索目标的方案高，从而证明了本文提出的算法的优越性。

图4　网络覆盖率随时间变化的比较

4结语

针对传感器网络中较为关心的提升能量利用效率和网络生存时间问题，本文就分布式传感器网络的场景设计了一种基于蚁群算法和能耗均衡的改进LEACH协议方案。通过引入蚁群算法实现了数据路由过程中局部最优向全局最优的逼近，从而解决了有限信息条件下的路径搜索问题。在此基础上进一步设计了能耗均衡的路由选路方案，平衡了各个节点的传输能耗。改进的LEACH协议更加贴近于实际应用场景，同时具有更优的能耗性能。仿真结果表明本文提出的方法在提升网络生存时间和覆盖率等方面的优势。

参考文献：

[1]Akyildiz I F, SU W, Cayirci E. A Survey on Sensor Networks[J]. Communications Magazine IEEE,2002,40(8):102-114.

[2]Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]// Proceedings of the 33rd Hawaii International Conference on System Sciences,Hawaii:IEEE Press,2000:8020.

[3]Manjeshwar A, Agrawal D P. TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[J]. Proc Ipdps Workshops,2001:2009-2015.

[4]白永祥. 一种LEACH路由协议算法的改进与分析[J]. 通信技术: 2015, 48(09):1062-1067.

BAI Yong-xiang. Improvement and Analysis of LEACH Routing Protocol Algorithm. Communications Technology: 2015, 48(09):1062-1067.

[5]Heinzelman W B, Chandrakasan A P, Balakrishnan H. AnApplication-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002,1(4):660-670.

[6]Tripathi M, Gaur M S, Laxmi V, et al. Energy Efficient LEACH-C Protocol for Wireless Sensor Network[C]// The 3rd International Conference on Computational Intelligence and Information Technology. CIIT 2013: IET Press, 2013:402-405.

[7]Kulik J, Heinzelman W, Balakrishnan H. Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks[J]. Wireless Networks, 1999, 8(2/3):169-185.

[8]Gagarin A, Hussain S, YANG L T. Distributed Hierarchical Search for Balanced Energy Consumption Routing Spanning Trees in Wireless Sensor Networks [J]. Journal of Parallel & Distributed Computing, 2010, 70(9):975-982.

[9]Chang R Y,Chung W H. Best-First Tree Search with Probabilistic Node Ordering for MIMO Detection: Generalization and Performance-Complexity Tradeoff[J]. IEEE Transactions on Wireless Communications,2012,11(2):780-789.

[10]GUidoni D L,Boukerche A,Villas L A, et al. A Tree-based Approach to Design Heterogeneous Sensor Networks Based on Small World Concepts[C]// The 36th Conference on Local Computer Networks (LCN 2011). Bonn:IEEE,2011:666-672.

[11]王王春. 无线传感器网络路由协议的设计与仿真[D].成都：电子科技大学, 2004.

WANG Chun. Design and Simulation of Routing Protocol for Wireless Sensor Networks[D]. University of Electronic Science and Technology of China,2004.

[12]LIU K J R. Cooperative Communications and Networking[M]. Cambridge:Cambridge University Press,2009.

[13]CHENG P, CAI C N, LIU X. Energy-Aware Node Placement in Wireless Sensor Networks[C]//Global Telecommunications Conference, 2004. Dallas: IEEE Press, 2004: 3210-3214.

[14]ZHANG J, SONG C, Sharif H, et al. A Battery-Aware Deployment Scheme for Cooperative Wireless Sensor Networks[C]// Global Telecommunications Conference, 2009. Hawaii: IEEE Press, 2009:1-5.

[15]IShizuka M, Aida M. Performance Study of Node Placement in Sensor Networks[C]// International Conference on Distributed Computing Systems Workshops, 2004. Tokyo: IEEE Press, 2004: 598-603.

Modified LEACH Protocol based on Ant Colony Optimization and Energy Balance

ZHOU Zhi-yong1，CHEN Hui2，WANG Hai-tao2，WANG Shi-jie1

(1.Institute of Communications Engineering;2.Department of Training, PLA University of Science and Technology,Nanjing Jiangsu 210007,China )

Abstract：Under the scenario of distributed wireless sensor networks, and in combination with the traditional LEACH protocol, an ACO(Ant Colony Optimization) routing algorithm based on limited channel information is proposed. This algorithm,with only a limited neighbor channel information required for each node, and no need for global information,could generally approach the optimal route. In light of this, a route transmit scheme based on load balance is suggested, which could effectively solve the problem of energy consumption unbalance of between the cluster heads in LEACH. Simulation experiments show that the modified routing algorithm based on ACO and energy balance could search for the optimal route in a high speed with local message, and in addition, could effectively balance the energy consumption of between the cluster heads,and prolong the network lifetime.

Key words：network lifetime; LEACH protocol; ant colony optimization; energy balance

doi:10.3969/j.issn.1002-0802.2016.04.013

*收稿日期：2015-11-09；修回日期：2016-02-20Received date:2015-11-09；Revised date：2016-02-20

基金项目：国家自然科学基金(No.61301157)

Foundation Item:National Natural Science Foundation of China (No.61301157)

中图分类号：TP393

文献标志码：A

文章编号：1002-0802(2016)04-0446-06

作者简介：