基于蚁群算法的能量均衡传感网地理信息路由

孙 颖

（沈阳大学 信息工程学院，辽宁 沈阳 110044）

基于蚁群算法的能量均衡传感网地理信息路由

孙 颖

（沈阳大学 信息工程学院，辽宁 沈阳 110044）

提出了一种基于蚁群算法的能量均衡传感网地理信息路由算法，用来保证具有生存周期的无线传感器网络能够在不损失其传感能力的情况下，生存更长的时间.实验证明，此算法能够均衡网络中的能量消耗，延长网络生存时间，并能有效提高报文发送成功率，避免拥塞.

蚁群算法；地理信息路由；能量均衡路由；无线传感器网络

近年来，一种新型的分布式系统—— 嵌入式网络系统显示出了广阔的应用前景.其中，无线传感器网络成了监控和分析物理环境最受欢迎的平台.无线传感器网络是由大量无处不在的，密集布设在无人值守的监控区域的具有通信与计算能力的微小传感器节点，构成的能够根据环境自主完成指定任务的智能自治监控网络系统.无线传感器网络是一种资源严格受限的分布式系统，采用多跳对等的通信方式，其网络拓扑动态变化，具有自组织、自治、自适应等智能属性.

无线传感器网络出现之后，路由方面的研究就成为了该领域的研究热点，目前关于路由的研究主要集中在几个方面，一类是基于能量的路由；一类是基于服务质量的路由；一类是基于最短路径的路由.

本文结合了能量感知路由和地理信息路由，通过同蚁群算法的有机集成，提出了一种基于蚁群算法的能量均衡传感网地理信息路由算法（Ant－colony－based Geographic and Energy Balance Routing，AGEBR）.该算法具有算法简单并支持分布式的特点，很容易在资源受限的无线传感器网络节点上实现.实验证明，该算法具有能够均衡网络中的能量消耗，延长网络生存时间，并能有效提高报文发送成功率，避免拥塞的特点.

1 相关工作

能量感知路由和基于地理位置的路由之前的相关工作，以及目前在无线传感器网络中利用环境能量资源的可行性启发了我们在此方面的工作.

1.1 能量感知ad－hoc路由算法

在过去的几年里，能量感知路由算法很受重视.Woo等人提出了5条能量感知定理［1］；Chang等人提出了一系列的流量递增算法和一个流量变向算法［2］；Li等提出了一种“在线”能量感知路由算法和一种基于区域的路由算法［3］.所有的这些工作都是基于如下的假定，即节点具有有限的或定量的能量供应，并且这些能量中不包括节点从环境获取的额外能量.

1.2 基于地理位置的ad－hoc路由协议

基于地理位置的路由协议的可行性取决于区域的可变性，以及路由决策过程是可定位的.发送报文的节点只需要获得自己、一跳节点和目的节点的位置.对于传统的基于地理位置的路由算法，报文通过局部和贪婪的方式发送到能够为其提供至目的节点的最优方式的一跳邻居.在贪婪模式下，笛卡儿路由算法［4］选择到目的节点的最近的邻居作为下一跳，而MFR（Most Forward within Radius）［5］更倾向于与目的节点具有最短工程距离（当前节点和目的节点之间的直线距离）的邻居.

当前一些针对无线ad－hoc和传感器网络的实验研究［6］表明无线链路可能出现较高的不可靠性，当评价更高层次的协议时，这种不可靠性需要被明确计算在内.文献［7］表明了大型“传统区域”的存在性，在其中的链路质量存在高变动性，包括好的和不可靠的链路.这种链路的存在暴露了贪婪算法的重要缺陷，即距离目的节点最近的邻居（有可能是距离转发节点最远的）可能与转发节点之间的链路较差.脆弱的链路可能导致包丢失率升高和发送率的急剧下降，或者在添加重传机制的情况下，增加能源消耗.基于地理位置的路由的当前工作认识到了这种信道条件下的现实问题.Seada等［8］提出了距离－跳数和能源权衡的基于地理位置的路由算法.他们总结出期望的报文传输，PRR（包接收率）×Adavancement，是一种可供选择的度量，这种度量用于对利用ARQ（Automatic Repeat reQuest）机制的无线网络丢失情况做出基于局部地理位置的路由算法决策.Zorzi和Armaroli也独立地提出了同样的链路度量［9］.上述工作的焦点在于报文收发情况，因此有关节点的能耗并未考虑.虽然GEAR（Geographic and Energy Aware Routing）［10］考虑了节点的剩余能量信息，但并没有考虑到无线信道的实际环境.

2 算法适用的传感器网络模型

2.1 网络模型

本文描述的网络是一个随机分布的无线传感器网络，含有1个sink节点，其余都是source节点.每个source节点i（i＝1，2，3，…）都周期性发送数据给sink节点.每个节点都有一个射频最大通信半径Rm，节点间的物理距离小于Rm，就能相互通信.以Pij表示节点i，j之间能否通信，则可生成通信矩阵

2.2 能量模型

Kansal等人［11］提出了一种能量的数学模型，当节点的功率满足某种条件时，节点可以做到持续工作，而不会能量耗尽.

式中，ρ为能量获取功率，σ1、σ2分别为能量阈值，当节点电池的初始能量大于σ1＋σ2时，则在T时间内，节点能够持续稳定的工作.因此，在电池初始容量足够的假设下，通过调节能量消耗功率E（t），就可以满足节点持续稳定工作的条件.

本文中假设能量获取功率全网相同，但其较小或为零，因此总有传感器节点不能满足持续工作的条件，电能总有一天会耗尽.即T将小于某个常数.本文的目标是使每个传感器节点的T值尽可能相同，保证全网能量同时耗尽.这样，也就保证了全网在传感功能不受影响的情况下工作最长的时间.

在每一时刻，节点都能获知剩余能量，以及未来T时间内的能量获取值ρT，如果没有能量补充，则该值为0.因此，通过调节能量消耗功率来控制节点在这一时间内持续稳定工作.

从另一个角度考虑，在满足这个条件的情况下，节点的剩余能量值与能量获取值之和越高，所能支持的功耗E（t）频率就越大.而节点的能耗大小可表示为

式中，Ec（t）为节点工作时的功耗，是由节点的任务循环（duty－cycle，DC）决定的，Es（t）是节点的静态功耗，一般来说是个常量，即

因此，根据式（5）就能确定节点的最小DC，使能量消耗最大且不影响节点持续工作.

通过选路，控制更多的报文由DC最大的点发，就能充分利用网络中的能量.而传感网关心的另一个问题是网络的性能，即最小化时延.尽管DC频率高的点拥有更多的能量用于转发数据，但也无法保证其所在的整条路径上不存在拥塞.

2.3 任务模型

本文中所涉及的无线传感器网络中每个传感器节点的任务包含两个方面：数据采集和发送任务，这和传感器的功能和工作周期有关；路由和转发任务，其他节点的报文通过该节点转发，最终到网关的报文.路由和转发任务不是每个节点都有，节点具有该任务有两个条件，一是在位置上不在边缘，属于中间节点，有被选为路由的可能，二是节点具有路由和转发的功能.

3 算法描述

蚁群算法［12］又称蚂蚁算法，根据仿生学家的研究结果，蚂蚁具有找到蚁穴与食物源之间最短路径的能力.

Step 1 在算法初始化中，每个节点都被赋予一定的信息素，每个报文作为一个蚂蚁.蚂蚁k（k＝1，2，3，…）在运动过程中根据节点上信息素的浓度决定选择哪个节点作为下一跳.蚂蚁k可选的下一跳的集合为allowedk.allowedk中的元素要满足地理位置上更靠近sink的节点才有资格作为下一跳，即

式中，d j，sink是邻居j到sink节点的物理距离，d i，sink是k当前所在的节点到sink节点之间的物理距离.

Step 2 在搜索过程中，蚂蚁k根据各条路径上的残留信息量和路径的启发信息计算状态转移概率.在t时刻蚂蚁k由节点i转移到节点j的概率（t）使用式（8）确定.

式中，τj（t）是节点j上残留信息素数量；allowedk，表示蚂蚁k下一步允许选择的节点集合；α为信息素启发因子；β为期望启发式因子，α，β都是常数；ηij（t）为启发信息，在本文中其表达式如下：

用来度量地理位置信息的重要性，距离网关越近的节点，成为下一跳的概率就越大.

Step 3 为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步后，要对残留信息进行更新处理，根据节点不同其表达式有2个，发送节点为：

式中，Δτi（t）是每次调整的信息素，ρ（0＜ρ＜1）为节点的信息素更新挥发系数，则1－ρ为信息残留系数.这样成功发送时，收发双方都会增加信息素，这样会提高被选择为下一跳的概率.而如果路径上某一位置因为拥塞或其他原因导致发送不成功，不成功的信息也会在路径上扩散，并在有限个报文周期之内扩散到整条路径，进而会帮助在以后的选路过程中绕过出问题的链路.

4 实验和分析

4.1 仿真场景

为了验证本文提出的算法的有效性，进行了仿真实验.仿真使用了MATLAB软件，仿真场景如下，在一个半径为100 m的圆内随机分布着30个传感器节点（source节点），同时圆心处拥有一个sink节点，所有传感器节点的数据收集和发送任务10 s生成一次，即发送一个报文，每个报文初始化成一个蚂蚁.信息素启发因子α为1；期望启发式因子β为1.

4.2 结果分析

本文对仅根据剩余能量选路的Mint Route，和文中提出的考虑能量均衡的蚁群AGEBR进行了比较.以下所有仿真结果都为3次相同条件仿真的平均值，显示距离网关不同距离上节点的生存时间和数据转发能力.

图1是网络生存时间的仿真结果.仿真过程为每个节点设置了近似相同的初始能耗.从结果可见，在相同的初始能量设置下，使用蚁群算法的网络能生存更长时间，这也证明了本文采用的选路策略比根据节点电池的剩余能量进行负载平衡的路由算法具有更好的节能效果.

图1 节点生存时间比较Fig.1 Survival time of nodes

本节也针对网络能量消耗进行了仿真.仿真中设定场景相比前一实验有所变化，主要是设定了离网关最近的14个路由节点拥有最多初始能量，实验模拟100 d的工作过程.获得以下实验结果：

表1、表2分别是两种路由情况下的能量消耗比，图2是每个节点的能量消耗比之间的对比关系.由表和图可以看出，AGEBR在平均能量消耗上略低于MintRoute，这是由于每次选路兼顾了路径可靠性，能够解决拥塞问题才会出现这样的结果.同时，由于考虑了负载均衡和能量均衡，使得各节点的能量消耗比例较为平均，方差较小.

表1 MintRoute中路由节点的能量消耗比Table 1 Energy consumption ratio of routing nodes in MintRoute

表2 AGEBR中路由节点的能量消耗比Table 2 Energy consumption ratio of routing nodes in AGEBR

图2 两种路由情况下不同节点的能量消耗比Fig.2 Energy consumption ratio of different nodes in two routing situations

5 总 结

由于蚁群算法具有天然的分布式特性，因此，本文采用的算法也具备分布性的特征，非常适合在传感网这种分布式网络上使用.同时，由于蚁群算法的实现也比较简单，没有太多的资源需求，因此也适合在传感网这种资源受限的网络上使用.

［1］ Singh S，Woo M，Raghavendra C S.Power－aware routing in mobile ad hoc networks［C］∥ MobiCom'98 Proceedings of the 4th annual ACM／IEEE international conference on Mobile computing and networking.New York：ACM New York，1998：181－190.

［2］ Chang J H，Tassiulas L.Energy conserving routing in wireless ad－hoc networks［C］∥ INFOCOM 2000.Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Tel Aviv，Israel：IEEE，2000（1）：22－31.

［3］ Li Q，Aslam J A，Rus D.Online power－aware routing in wireless ad－hoc networks［C］∥ MobiCom'01 Proceedings of the 7th annual international conference on Mobile computing and networking.New York：ACM New York，2001：97－107.

［4］ Finn G G.Routing and addressing problems in large metropolitan－scale internetworks ［R］.ISI／RR87180，University of Southern California：Information Sciences Institute，1987.

［5］ Takagi H，Kleinrock L.Optimal transmission ranges for randomly distributed packet radio terminals［J］.IEEE Transactions on Communications，1984，32（3）：246－257.

［6］ Zhao J，Govindan R.Understanding packet delivery performance in dense wireless sensor networks［C］∥SenSys'03 Proceedings of the 1st international conference on Embedded networked sensor systems.New York：ACM New York，2003：1－13.

［7］ Zuniga M，Krishnamachari B.Analyzing the transitional region in low power wireless links［C］∥IEEE Secon 2004，2004：517－526.

［8］ Seada K，Zuniga M，Helmy A，et al.Energy efficient forwarding strategies for geographic routing in wireless sensor networks［C］∥ SenSys'04 Proceedings of the 2nd international conference on Embedded networked sensor systems.New York：ACM New York，2004：108－121.

［9］ Zorzi M，Armaroli A.Advancement optimization in multihop wireless networks［C］∥ 2003 IEEE 58th Vehicular Technology Conference，2003（5）：2891－2894.

［10］ Yu Y，Estrin D，Govindan R.Geographical and energyaware routing：A recursive data dissemination protocol for wireless sensor networks［R］.TR－01－0023， UCLA：Computer Science Department，2001.

［11］ Kansal A，Srivastava M B.An environmental energy harvesting framework for sensor networks［C］∥International symposium on Low power electronics and design，2003：481－486.

［12］ 朱程辉，叶福林，基于蚁群算法的无线传感器网络路由算法［J］.微型机与应用，2010（15）：67－70.

Geographic Routing of Energy Balance Sensor Network based on Ant Colony Algorithm

SUNYing
（School of Information Engineering，Shenyang University，Shenyang 110044，China）

Ant－colony－based Geographic and Energy Balance Routing （AGEBR）were utilized to establish wireless sensor networks which had survival cycles.As a result，the sensor networks could last a longer period without losing their sensing ability.Experimental results demonstrated that the proposed approach can keep balance of the network energy consumption，prolong the network lifetime，and enhance the successful rate of sending packets without congestion.

ant colony algorithm；geographic routing；energy balance routing；wireless sensor network

TP 393.04

A

1008－9225（2012）02－0057－05

2011－11－18

辽宁省科学技术厅科技攻关项目（2011216004）.

孙 颖（1969－），女，辽宁沈阳人，沈阳大学副教授.

李 艳】