摘要：无线传感器网络（WSN）路由中，节点未充分考虑路径剩余能量及链路状况进行的路由会造成网络中部分节点网络寿命减少，严重影响网络的生存时间为此，将蚁群优化算法与非均匀分簇路由算法相结合，提出一种基于蚁群优化算法的无线传感器非均匀分簇路由算法该算法首先利用考虑节点能量的优化非均匀分簇方法对节点进行分簇，然后以需要传输数据的节点为源节点，汇聚节点为目标节点，利用蚁群优化算法进行多路径搜索，搜索过程充分考虑了路径传输能耗、路径最小剩余能量、传输距离和跳数、所选链路的时延和带宽等因素，最后选出满足条件的多条最优路径，完成源目的节点间的信息传输实验表明，该算法充分考虑路径传输能耗和路径最小剩余能量、传输跳数及传输距离，能有效延长无线传感器网络的生存期

　　关键词：蚁群算法； 能量均衡； 非均匀分簇； 无线传感器网络； 路由算法

　　中图分类号：TP393 文献标志码：A

　　0引言

　　无线传感器网络（Wireless Sensor Network，WSN）是一种获取和处理信息的新兴技术，被大量应用到环境监测和野外设备监控方面[1-2]，但WSN节点仅依靠电池供电，不合理的能量消耗会使网络过早出现死亡节点而降低网络生存期因此如何设计节约节点能耗且提高网络通信质量的WSN路由算法成为研究热点

　　人们提出了分簇路由算法以减少开销，方便管理节点和控制信道接入，提高资源使用效率[3]Heinzelman等[4]提出了经典的低功耗自适应分簇（Low Energy Adaptive Clustering Hierarch，LEACH）协议，采用随机选取节点作为簇头的分簇方式来降低网络能耗，但通信采用单跳方式，所有簇头直接向基站传送信息，能耗较大

　　之后提出的改进算法EECS[5]通过候选节点广播自己的剩余能量来竞选簇头，簇头的选择要考虑自身到基站的距离，但远离基站的簇比靠近基站的簇要求更多的能量，在均衡全网能耗上并不理想

　　文献[6]首次提出利用非均匀分簇的思想来解决这个“热区”问题，但是它考虑的是一个异构网络，簇头为超级节点，而且位置是事先计算好的，无需动态构造簇的操作

　　文献[7]提出了一种基于非均匀分簇的无线传感器网络路由协议EEUC，通过非均匀分簇来均衡网络能耗，但需要周期性地随机竞选簇首，而且竞选簇首时只考虑了节点的剩余能量，未考虑链路可靠性和实时性

　　后来在非均匀分簇基础上又提出基于最小生成树的非均匀分簇算法UCRAMST[8]、基于粒子群的非均匀路由算法[9]等

　　以上算法只从剩余能量的角度来考虑，并没有考虑链路的其他状况，无法选择最优的路径进行路由，会导致更多不必要能量的消耗

　　基于蚁群算法（Ant Colony Algorithim，ACA）[10-13]的无线传感网路由协议是目前国内外研究的热点之一基于蚁群算法的路由协议通过蚂蚁包的发送，每个节点都可以获悉网络当前实际情况，并根据信息素概率公式选择下一跳，非常适合设计这种能量负载均衡同时又可综合考虑链路状态和实时性的多路径分簇路由协议

　　文献[14]中提出的ARA算法是最早的将蚁群算法应用于无线移动自组织网络的按需多路径算法，路由的建立依靠前向蚂蚁和后向蚂蚁来实现，开销比较小

　　文献[15]中提到的IEEABR算法是一个主动式的路由协议，采用累加的方式进行信息素更新，但这样的策略容易陷入局部最优，使个别路径上的节点过早死亡，从而对整体的网络寿命和通信能力产生不利影响

　　在以往WSN非均匀分簇路由算法研究中，采用非均匀分簇可避免“热区”而导致节点死亡，但较少考虑能量以外的其他环境参数，采用蚁群算法模型可以较好解决非均匀分簇路由算法没有充分考虑簇首与基站之间各跳的带宽、实时性、路径上剩余的最小能量、距离目的节点的跳数来进行最优路径选择的问题

　　文献[16]提出的利用蚁群的非均匀分簇路由算法考虑了带宽和实时性，但没有考虑已成功发送数据的路径消耗的能量以及路径上节点的最小剩余能量，在路由更新时没有考虑节点到目的节点的跳数，会导致局部路径最优

　　因此，本文将蚁群优化算法与非均匀分簇路由算法相结合，提出一种基于蚁群优化算法的无线传感器非均匀分簇（Ant Colony based Energy Balanced Uneven Clustering，ACEBUC）路由算法优化非均匀分簇方法考虑节点能量对节点进行分簇，而蚁群优化算法则进行多路径搜索，搜索过程考虑路径上剩余的最小能量、距离目的节点的跳数、所选链路的时延和带宽等因素，更合理地更新信息素和设计下一跳的概率公式

　　1蚁群算法

　　蚁群算法是由意大利学者Dorigo等[10-11]提出的一种基于种群的启发式仿生进化系统蚁群算法最早用于解决著名的旅行商问题（Traveling Salesman Problem，TSP），采用了分布式正反馈并行计算机制，易于与其他方法结合，并具有较强的鲁棒性[12-13]

　　基于蚁群算法的路由协议中，每个节点维护一张路由表和一张附加表：

　　路由表记录目标节点地址和到达目标节点地址的下一跳的启发式信息值；

　　附加表包含网络蚂蚁流量的分布信息，记录蚂蚁经过的节点

　　通过设计选择下一跳的概率公式和启发式信息值可设计不同的路由算法

　　以往的相关研究证明，基于蚁群的路由算法能延长网络生存时间，但是会陷入局部最优，导致能量消耗“热区”

　　本文结合非均匀分簇的能量均衡的优势设计基于蚁群的路由协议，以解决两者的不足，达到延长网络生存时间的目的

　　2网络模型

　　考虑一个M×M的正方形区域内随机分布N个传感器节点，本文假设：1）在观测区域内，传感器节点和基站在部署后均不会发生位置移动；2）所有节点都是同构的；3）链路是对称的，若已知对方发射功率，节点能够根据接收信号的强度（Received Signal Strength Indication，RSSI）来计算到发送者的近似距离；4）根据接收者的距离远近，节点可以调整其发射功率来节约能量 　　本文在EEUC的非均匀分簇结构的基础上采用ACEEUC算法进行优化EEUC采用分布式拓扑控制算法非均匀分簇结构，如图1所示

　　用一个n个点m条边的无向加权连通图G（V，E）作为网络模型，V是簇首和汇聚节点，E是边集设C是簇首集合，有N个元素，Sink是汇聚节点，路由问题就是在G中寻找从C中任意要发送数据的节点到Sink节点满足性能要求的多条路径设每一跳链路i上所消耗的能量为ei，链路延迟为ti，链路带宽为bi现要求N跳路由链路要满足目标函数f（Sink）最小：

　　本文用EDF表示融合单位比特数据消耗的能量假设邻近节点采集的数据具有较高的冗余度，每个成员发送长度为b的数据包，簇头可以将其成员的数据融合成长度为b的数据包，而簇间通信冗余度很低，不能融合

　　3ACEBUC路由算法

　　本文提出的ACEBUC算法按轮次分为簇首选举、路径搜索、数据传输、簇内调整和路由更新能量均衡主要体现在采用非均匀分簇的方式解决基站附近容易出现热区的问题，本文的簇首选举方法是在文献[7]方法上进行优化改进，而在路径搜索方面则采用基于蚁群的簇首多跳路径搜索，将节点能量和链路的时延及带宽信息作为启发式信息

　　3.1簇首选举

　　采用非均匀分簇的方式可以解决基站附近容易出现热区的问题，EEUC对候选簇首的选择是依据LEACH算法中的随机获取每个节点成为候选簇首的概率t，且与设定的阈值T进行比较，选出t　　本文提出的ACEBUC算法考虑尽可能增长网络生存时间，簇首选举只在第一轮采用全网络竞争方式，后续轮在簇内进行调整选择簇首候选节点应该是能量较充足的节点为让剩余能量多的节点成为候选节点的概率增大，现对T（i）作如下改进：

　　其中：Eri是si节点的剩余能量，Erave为全网平均剩余能量，p为簇头节点占所有节点百分比的期望值

　　网络内的簇首个数对网络的生存时间存在影响，过多或者过少都不合适，为了减少能耗，需要在选择簇首阶段确定理想簇首数，同时确定簇首的广播半径本文采用由文献[5]提出的理想簇首数目：

　　3.2基于蚁群的路径搜索

　　在簇首将数据传输到目的节点的这个阶段，簇首首先对簇内数据进行融合，然后数据以多跳通信的方式发送至目的节点，随后，非簇首节点进入休眠状态以节约能量多路径搜索是基于蚁群算法的模型，簇首节点释放蚂蚁寻找从簇首到目的节点的有效路径，每个蚂蚁都有自己的内存表，用禁忌表来存储已经过的节点，以后在搜索中不能访问这些节点，用簇首节点表（allowed）存储允许访问的节点ACEBUC协议中规定前向蚂蚁要携带以下信息：所有簇首节点ID、能耗Ecost、剩余能量Eremain、信息素τkij、概率pki，j（t）、已访问节点字段VisitedNode、时延delayij和带宽bandwidthij；后向蚂蚁要携带已访问节点字段VisitedNode、链路最小剩余能量EkminRemain和链路平均消耗能量EaveCost

　　ACEBUC协议中规定前向蚂蚁要携带以下信息：所有簇首节点ID、产生前向蚂蚁的源节点地址SrcAdd、已访问节点字段VisitedNode，蚂蚁访问过节点已消耗的能量总和Esum，蚂蚁从源节点出发的时间SrcTime；蚂蚁经过簇首建立的路由表信息包括：能耗Ecost，剩余能量Eremain，信息素τkij，下一跳概率pki，j（t）；后向蚂蚁要携带已访问节点字段VisitedNode，此后向蚂蚁对应的前向蚂蚁从源节点出发的时间SrcTime，链路最小剩余能量Emin，链路平均消耗能量Eavg

　　每个前向蚂蚁的任务是找一条连接源节点到目的节点的路径，在源节点和目的节点之间的节点若没有路由信息，则广播前向蚂蚁，若有路由信息则按着下一跳的信息素概率公式单播发送前向蚂蚁，其下一跳选择只能从allowed中以某种概率搜索，概率pki，j（t）的计算公式为式（9）：

　　在路径搜索中，前向蚂蚁分组里携带了从源节点出发的时间，这样端到端的时延很容易获得，同时链路带宽和发送数据包的大小已知；

　　利用数据包传输的延迟时间，汇聚节点可以计算出源节点到汇聚节点的数据发送率，将这个速率与预期速率相比较，若小于预期速率，则意味着产生了丢包同时在前向蚂蚁到达一个簇首后更新簇首路由表，根据能耗模型公式计算接收能耗以及到下一跳的发射能耗总和，同时更新路由表的剩余能量，然后更新蚂蚁携带的信息包中的总消耗能量，直到找出满足目标函数的最优路径

　　3.3路由更新

　　当源数据节点的簇首si将数据成功发送到目的节点之后，统计传输信息的转发时延，根据后向蚂蚁获取路径上的最小剩余能量以及路径的平均能耗、距离目的节点的跳数，更新各簇头sj的信息素浓度在蚁群算法中，信息素增强为式（12），路由更新采用式（13）ACEBUC算法对信息素的更新不是传统的累加方式，而是节点每次收到后向蚂蚁就重新计算链路信息素，这样数据包在网络上的分布更均匀此定义对sj节点的信息素更新公式如（14）所示

　　3.4簇内调整

　　在第一轮数据传输的最后，要判断路由经过的簇首能量水平，若簇首能量高于簇平均能量，保持原簇首不变；反之，进行簇内调整，选取大于平均能量的节点进入簇内候选节点，低于平均能量的节点进入休眠设候选簇首个数为m，在候选簇首中再依据式（8）求得下一轮簇首新选出的簇首广播原簇首ID、自身ID、自身剩余能量的消息通知簇内成员及其他簇首成员，所有簇首节点收到簇头调整信息后更新各自对应的路由表信息

　　4仿真与分析

　　现对EEUC、ACOUC、IEEABR算法和本文提出的ACEBUC算法分别用NS2进行了仿真，并在能耗、可靠性、实时性、路由成功率方面进行分析ACEBUC的工作方式是周期性采集目标数据传输给汇聚点，适用于对野外环境进行周期性信息采集和实时监控，节点随机布撒或分布在被监控设备周围 　　实验中所用的参数如表1所示，其中能量消耗模型所用参数取自文献[5]

　　4.1簇首特征

　　本文采用改进的EEUC算法的非均匀分簇方式，在文献[9]中指出簇首数目由参数R0c和c共同决定，同时由实验证明在c=0.5时，网络存活时间最长在c固定时，簇首数目与R0c成反比本文取c=0.5，由式（5）可知理想簇头个数为2～56，由图5可知， 可取30m进行实验，生成的簇头数为40，在理想簇首范围内

　　4.2网络能量消耗

　　EEUC算法均采用每轮依据概率重新选取簇头，每轮生成的簇首数目会有波动，而一个稳定的分簇算法应在网络拓扑固定的情况下，生成较一致的簇首数目；ACOUC算法在信息素更新时仍采用累加信息素的方式，并没有考虑在路由成功后，具有较高信息素的路径由于承担过多数据发送任务反而消耗过多能量；IEEABR算法由于没有采用非均匀分簇的方式，容易知道在靠近汇聚点的簇首耗能较大；ACEBUC仅在首轮采用竞选方式，之后在簇内进行选举，因此簇首数目稳定，整个网络具有较好的稳定性

　　在每一轮次中所有簇首消耗的能量在所有节点消耗的总能量中占大部分比重通过实验统计四种算法每轮簇首消耗的能量，第一个实验点记录首轮消耗能量，之后随机抽取9轮进行统计，结果如图6所示由图6可以看出，ACEBUC仅在首轮消耗较多的能量，之后在簇内竞选簇首，比EEUC、ACOUC、IEEABR算法能更好地实现节能

　　4.3可靠性和实时性

　　ACEBUC算法在簇内节点将数据发送给簇首节点之后，由簇首节点将数据进行融合，并采用蚁群改进算法，充分考虑链路的能量、带宽和时延进行下一跳路由选择通过实验分别比较EEUC、ACOUC、IEEABR和ACEBUC算法的丢包率和时延情况由图7、8可以看出，EEUC算法的丢包率相对较高、时延较大，因为该算法采用多跳方式，但是在路由选择时并没有充分考虑链路状况，只是简单考虑节点的能量，因此在数据传输时会出现较高的丢包率；ACOUC、IEEABR均采用蚁群算法模型，在路由选择时充分考虑了链路状况，因此丢包率和时延相对较低；ACEBUC采用多跳传输，考虑了链路状态，选择最优最可靠的路径，出现丢包的情况较少，时延相对较小

　　4.4网络生存时间

　　通过仿真记录每轮结束节点存活数量直到节部死亡比较四种算法的网络存活时间由图9可以看出， EEUC采用竞争选取簇头方式，并考虑能量空洞问题，但是在路由选择时并没有考虑链路状况；而ACEBUC算法不像EEUC算法每轮都要在全网络进行簇首选举，只是在首轮在全网络内进行簇首选举，之后采取在簇内竞选簇首的方式，实现了节能，路由采用蚁群改进算法，使网络生存时间长于EEUC算法；ACOUT与IEEABR算法在定义路由信息素时都没有合理考虑路径的能量消耗速度、路径上剩余的最小能量、距离目的节点的跳数等，在路由时容易陷入局部最优，网络生存时间不如ACEBUC长

　　4.5路由成功率

　　随机生成具有100至400个节点的随机网络拓扑结构进行路由仿真比较，对于每个网络拓扑，选择所有节点中距离最远的节点作为源和目的节点，这样2个节点间的可选路径较多从图10可以看出随着节点数的增加，网络规模增大，ACEBUC显示出算法的优势，其路由成功率要高于其他三个算法

　　5结语

　　本文将蚁群优化算法与非均匀分簇路由算法相结合，有效地减少了簇首选举和路由维护的开销，而且能实时寻找性能更好的路由仿真分析表明，ACEBUC的网络存活时间比EEUC、ACOUC算法都有显著提高但是在路由层次，本文采用的蚁群优化路由算法比较适用于大规模节点路由情况，对于节点较少且实验区域较小的情况并不需要采用蚁群路由算法，可以直接采用单跳发送数据

　　参考文献：

　　[1]AKYILDIZ I F， SU W， SANKARASUBRIMANIAM Y， et al. Wireless sensor networks： a survey [J]. Computer Networks， 2002， 38（4）： 393-422.

　　[2]ALKARAKI J N， KAMAL A E. Routing techniques in wireless sensor networks： a survey [J]. IEEE Wireless Communications， 2004， 11（6）， 6-28.

　　[3]汤波，罗昌俊。能量均衡的无线传感器网络分簇方法[J]. 计算机应用研究，2008，25（3）：878-880.

　　[4]HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H. Energyefficient communication protocol for wireless microsensor networks [C]// HICSS 2000： Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Washington， DC： IEEE Computer Society， 2000，8： 8020.

　　[5]YE M，LI C F， CHEN G H，et al. EECS： an energy efficient cluster scheme in wireless sensor networks [C]// IPCCC 2005： Proceedings of the 2005 24th IEEE Performance， Computing， and Communications Conference. Piscataway： IEEE， 2005： 535-540. 　　[6]SORO S， HEINZELMAN W B. Prolonging the lifetime of wireless sensor networks via unequal clustering [C]// IPDPS 05： Proceedings of the 19th International Parallel and Distributed Processing Symposium.Washington， DC： IEEE Computer Society， 2005： 8-15.

　　[7]李法成，陈贵海，叶懋，等。一种基于非均匀分簇的无线传感器[J].计算机学报，2007，30（1）：27-36.

　　[8]张明才，薛安荣，王伟。基于最小生成树的非均匀分簇路由算法[J].计算机应用，2012，32（3）：787-790.

　　[9]邹杰，史长琼，姬文燕。基于粒子群优化的非均匀分簇路由算法[J].计算机应用，2012，32（3）：787-790.

　　[10]COLOMI A，DORIGO M，MANIEZZO V. Distributed optimization by ant colonies[C]/ / ECAL 1991： Proceedings of the 1991 European Conference on Artificial Life.[S.l.]： Elsevier， 1991： 134-142.

　　[11]DORIGO M. Optimization learning and natural algorithms[D]. Milano： Politecnico di Milano， Department of Electronics， 1992.

　　[12]DORIGO M，STUTZLE T. 蚁群优化[M].张军，胡晓敏，罗旭耀，等译。北京： 清华大学出版社，2007： 3-7.

　　[13]DORIGO M，BONABEAU E，THERAULAZ G. Inspiration for optimization from social insect behavior [J]. Nature，2000，406（6）：39-42.

　　[14]GUNES M， SORGES U， BOUAZIZI I. ARA： the antcolony based routing algorithm for MANETs [C]// ICPP 2002： Proceedings of the 2002 International Conference on Parallel Processing Workshops. Piscataway： IEEE， 2002：79-85.

　　[15]童孟军，俞立，郑立静。 基于蚁群算法的无线传感器网络能量有效路由算法研究[J].传感技术学报，2011，24（11）：1632-1638.

　　[16]张荣博，曹建福。利用蚁群优化的非均匀分簇无线传感器网络路由算法[J].西安交通大学学报，2010，44（6）：33-38

　　[17]汤波，罗昌俊。能量均衡的无线传感器网络分簇方法[J]. 计算机应用研究，2008，25（3）：878-880.

　　转载请注明来源。原文地址：http://www.xzbu.com/8/view-4759226.htm