基于蚁群算法的长链状无线传感网络路由算法

高 静，朱永利，李丽芬

（华北电力大学控制与计算机工程学院，河北保定 071003）

基于蚁群算法的长链状无线传感网络路由算法

高 静，朱永利，李丽芬

（华北电力大学控制与计算机工程学院，河北保定 071003）

针对输电线路监测系统对无线传感器网络实时性和可靠性要求较高的特点，提出了一种用于线路监测传感网络的带信息素负增长的蚁群算法。该算法中不需要网络节点维护全局信息，但需要赋予唯一的编号。启发函数计及了链路的时延、收包率和距离汇聚节点的跳数，并经过试验增加了以参数α的不同选取可以调整跳数在整个选择过程中所占的重要程度。算法还为当前不可行和拥塞节点设置定时器，超时后可重新参与路由选择。仿真结果表明，相比基本蚁群算法，该算法能够找到具有更好性能的路由。

长链状无线传感器网络；输电线路监测；蚁群算法；路由

无线传感器网络（Wireless Sensor Network，WSN）是由一组传感器节点通过无线介质连接构成的无线网络，它采用Ad Hoc方式配置大量微型的智能传感节点，通过节点的协同工作来采集和处理网络覆盖区域中的目标信息［1，3］，它可被部署在各种非布线区、电源供给困难和人员不易到达的区域。基于无线传感器网络的输电线路在线监测技术是一门多学科高度交叉、知识高度集成的新兴技术［2］，其网络的拓扑结构一般为长链辐射状，这种传感器网络多具有集中式数据接收、多跳传输、多对一流量模式等特征。

目前人们对于这种长链状无线传感网络的研究比较少，对于长链状输电线路监测用无线传感网络的研究就更少，文献［7］中提出的路由算法是基于固定簇头的分层路由，采用汇聚节点查询的方式，簇头对簇内的节点数据进行整合并转发，但并不适合事件驱动的实时应用。PAGASIS（Power－EfficientGathering in Sensor Information Systems）［6］协议是一种典型的基于链状结构的路由协议，该算法的核心思想是利用贪婪算法生成一条由所有节点组成的单链，链上的节点只与自己的邻居节点通信。该协议追求的目标是节点能耗的均衡和网络寿命的延长，但是当节点链过长时，数据传输时延将会急剧增长，不适合实时应用。因此，虽然结构和本系统有相似之处，但是却不满足本系统的性能要求。文献［8］提出一种基于云模型的多蚁群路由优化算法，利用多规则云发生器来调整信息素残留系数，利用多蚁群来同时找到多条路径；文献［11］提出一种将蚁群算法与遗传算法结合的路由优化算法，提高了最优解的质量，但算法对于性能较弱的传感器节点来说稍显复杂。

文献［5］提出一种信息素负反馈的机制，通过在较好的路径上留下正信息素，在较差的路径上留下负信息素，从而提高了算法的性能和效率。笔者在以上算法的基础上，提出一种用于线路监测传感网络的带信息素负增长的蚁群算法，算法为每个节点设置编号，用于指引蚂蚁的行动，从而避免环路的产生。仿真实验结果证明了算法具有较好的路由性能。

1 输电线路监测传感网络简介

1.1 输电线路监测系统的网络模型

架空输电线路的距离长，中途有众多的挂有绝缘子的杆塔，每个杆塔的每相上设置一个传感节点，在每组输电线上设置一个汇聚节点，用于收集该站各条出线的所有传感节点的数据，并与线路监控中心服务器相连，用于保存各绝缘子泄漏电流的历史数据。抽象出的无线传感器网络模型如图1所示。三个节点为一组，表示线路的三相，节点采集到的数据通过无线链路进行多跳传输，采用全向天线，通信范围能达到2－3跳。

1.2 基于输电线路监测的无线传感器网络特点

基于输电线路监测的无线传感器网络具有如下几个特点：（1）节点部署相对规则，部署后不再移动；（2）区域节点密度比较小，相邻杆塔相距几十米到几百米，有的甚至上千米；（3）节点能量不受限，通过在输电线路上套装可开口的特制互感器，并在二次侧对感应电流进行整流、稳压即可取得电源；（4）节点定位、时间同步可通过安装GPS来解决；（5）数据传输对实时性、可靠性有较高的要求；（6）汇聚节点及其附近节点除了要传输自身的数据还需转发其他节点的数据，任务量比较重，较易出现网络拥塞现象。

1.3 节点编号

节点的辐射状规则部署给节点的编号带来了方便。本文采用给节点进行编号的方式来表明节点离汇聚节点的远近，从而在路由建立过程中对节点的选择提供参考。由于本文只对一段线路进行研究，故编号采用两段的方式，汇聚节点编号为0－0，离汇聚节点最远的一层节点由上到下依次编号为1－1，1－2，1－3，次远层的节点编号为2－1，2－2，2－3。编号的前一段表示离汇聚节点的远近，编号越大，离汇聚节点越近，编号的后一段表示同层节点的位置关系。

图1 输电线路监测系统的无线传感器网络模型

2 线路监测传感网络的带信息素负反馈路由算法的提出

像蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁穴到食物源的最短路径。人们经过大量的研究发现，蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为信息素（pheromone）的物质，蚂蚁倾向于朝着该物质强度高的方向移动，于是表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后者选择该路径的概率越大。通过这种正反馈性，蚂蚁依据转移概率由位置i转移到位置j，算法通过多次迭代收敛到最优结果［4］，蚁群算法已经被用于求解计算机网络中的QOS路由［10，11］等问题。

文献［5］提出了一种信息素负反馈的机制，按照解的好坏对蚁群进行排序，设置一个比例参数φ∈（0，1］，排名前m×φ的蚂蚁将有权在其经过的路径上留下正信息素，此信息素有吸引同伴的作用，排名在m×φ之后的蚂蚁在其经过的路径上留下负信息素，此信息素将警告同伴不要走这条路径。

2.1 路由建立过程

2.1.1 准备工作

（a）借助GPS定位系统获得节点的地理位置信息并对节点进行统一编号，设节点的编号为n1－n2；

（b）通过HELL0包周期性向邻居节点广播自己的信息。在HELL0包中除了包含节点的坐标位置信息以外，还包括时间戳，这样每个节点都会获得相邻节点的地理位置信息，并从收发节点的时间差中减去接收节点的处理时间，就可以获得邻节点的通信延时，来表示网络的负载情况，设通信延时为delay；

（c）计算链路收包率（packet reception rate，PRR），PRR＝Lr／Ls，Lr为成功接收到的数据包个数，Ls为链路发送的总数据包数。

（d）设置公告板，用于记录每个源节点到sink节点的最优路径，初始化为空；

（e）集合DE（Died End）用于放置不可行和拥塞的节点，初始化为空，当节点负载过重时，向子节点发送反向压力信标，并将自己放在集合DE中，集合中每个节点设置一个定时器，超时即被解禁，从本集合中移除，重新成为活跃节点，参与数据的转发。

每个节点维护一张邻节点情况表，用于记录邻节点的编号、延时和链路收包率。

设置延时和链路质量的约束条件：

2.1.2 建立过程

（a）初始化网络中每一条边的信息素为1；在每一次迭代中，网络中的每一个结点s都有Ant＿Count只目的节点为sink的正向蚂蚁Fs－＞sink出发，它的任务是找到一条通往sink节点的高性能的可行路径；正向蚂蚁与逆向蚂蚁采用比数据分组更高优先级的链路队列，从而加快路径建立的速度；

（b）在每个节点i上，集合NC为节点i的所有邻节点集合中满足约束条件（1）和（2）的节点集合，将不属于DE集合并且节点的n1编号大于i的n1编号的节点，即相对比节点i离sink节点更近的邻节点放入集合NC1中。

（1）如果｜NC1｜＞0，则蚂蚁依据转移概率在邻节点中选择下一个要遍历的节点，选择相邻节点j作为下一个遍历结点的转移概率Pij定义如下：

启发式函数综合考虑了链路质量、节点对之间的时延和距离汇聚节点的跳数，以期选择出满足实时性和可靠性要求的路径。

（2）如果｜NC1｜＝0，即不存在比节点i离sink节点更近的节点，则蚂蚁回退一步，并将节点i放入集合DE中；

（3）到达sink结点后，前向蚂蚁Fs－＞sink将生成另一个逆向蚂蚁Bsink－＞s，它把自己的所有记忆转移给逆向蚂蚁，而自身将被删除。如果在到达目的结点前，正向蚂蚁的生存时间超过了最大生存时间max＿life，那么这个蚂蚁将被删除。逆向蚂蚁行进的路径与它对应的正向蚂蚁完全相同，但是行进的方向却正好相反，负责信息素的更新，其更新规则如下：

从以上公式可以看出：所选路径的总延时越小，包成功率越高，则相应路径的信息素增长越多，即信息素的增长与路径的质量成正比。

（4）更新公告板，如果当前求出的最优路径比公告板上记录的更优秀，则将其替换为本次求出的路径。

（5）达到最大迭代次数时算法结束。

2.2 数据传输过程

数据依据2.1节找到的最优路径进行传送，当节点的转发队列过长时，为保证转发的实时性，该节点发出警告信息alert，该alert消息记录了该节点的节点编号n1－n2，并通过洪泛将该消息通知给其它节点，之后放入集合DE中。当源节点接收到该alert消息时，判断该节点编号n1－n2是否在自己的路径列表中，如果在则n1－n2的上一跳节点根据2.1节路由算法重新寻找除n1－n2以外的新的下一跳节点。

3 算法分析及仿真结果

3.1 算法分析

本文算法为分布式的算法，蚂蚁从各个源节点出发并行工作查找到sink节点的最优路径，算法同时考虑了信息素浓度、节点间延时、链路的质量和节点距离sink节点的跳数。由公式（2）可以看出，链路的收包率越高，节点之间的延时越小，距离汇聚节点越近，则选择概率越大，从而可以很好地保证可靠性和实时性，并能尽量快速地、少跳数地形成到达汇聚节点的路由。算法引入负反馈机制，提高了解的质量，但却因为要排序比较而增加了算法的计算量，因排序而增加的比较次数为：n（n－fix（n＊φ）），复杂度为O（n）。另外，算法通过对每个节点进行编号，有效地避免了环路的产生。

3.2 仿真实验

本文用仿真软件MATLAB 7.1作为仿真平台，仿真实验时采用如图1所示的网络拓扑结构图，其中链路的时延、包成功接收率的值由系统随机产生，时延在1～10ms，包成功接收率在0.85～1之间，其中D＝9.5ms，R＝0.9。依据文献［5］的参数选择，α＝1，β＝4.5，ρ＝0.2，Q＝0.1，φ＝0.9，r表示节点的通信半径（单位为跳数），m表示本长链的节点层数。

图2和图3是在网络层数为100，节点的通信半径为3跳的情况下进行的，其中性能的评价依据公式（8）计算。从图中可以看出，当α＝0时，所选出的最优路径性能值最小，路径总跳数最多。这是因为启发函数中并没有考虑到跳数这个参数，所以尽管所选路径的单跳时延和链路包成功率最优，但因总路径的跳数更多，从而影响总路径的性能；当α＝1／r时，所选出的最优路径性能值最大，总跳数最少；而当α＝1／（r＊r）时，所选出的最优路径性能值和总跳数居中。原因就在于跳数在α＝1／r中所占得比重更大，但是过分增大α的值将会导致跳数掩盖掉其他两个参数。由图3看出，当α＝1／r时所选路径的总跳数在37到50之间，并没有导致参数跳数覆盖掉其他两个参数，所以本论文中取α＝1／r。

图2 不同α取值下最优路径性能变化情况

图3 不同α取值下所选路径总跳数的变化情况

图4 两算法最优路径性能变化情况

图4是在网络层数为100，节点的通信半径为2跳，迭代次数t为400，每个源节点的蚂蚁数量为6的情况下进行的，其中性能的评价依据公式（8）计算。从图2中可以看出，相比基本蚁群（Base Ant Algorithm，BAA）算法，带信息素负增长的蚁群算法（Base Ant Algorithm With Negative pheromone growth，BAWN）能找出性能更优秀的路径，这与文献［5］中的结论也是相一致的。

由图5可以看出，增加在每个源节点放置蚂蚁的数量，能够加快获得最优解的速度，但是随着迭代的进行，这种优势越来越弱。增加蚂蚁的数量会增加因排序而进行的比较次数，所以应该根据传感器节点的能力来选择合适的蚂蚁数量。

图5 源节点放置不同蚂蚁数量下最优路径性能变化情况

4 结论

本文以输电线路监测为应用背景，针对系统对无线传感器网络实时性和可靠性要求较高的特点，提出了一种用于线路监测传感网络的带信息素负增长的蚁群算法，通过对每个节点进行编号，有效地避免了环路。在算法中，距离汇聚节点越近，延时越小，可靠性越高的节点被选择的可能性越大，反向压力信标用来缓解某个节点任务过重的情况，从而预防拥塞的发生，定时器的设定可以使优秀节点在经过一个时间段的休眠后重新成为活跃节点，这也是对网络整体性能的一个考虑。对于启发函数中的参数α，本文是通过实验选取的，当α＝1／r时，相比较α＝0和α＝1／（r＊r）时在所选路径的性能上更优秀，但本文并没有给出α的最优表现形式。仿真实验表明，带信息素负增长的蚁群算法能够获得更高质量的解，因此该算法相比基本蚁群算法更适合于长链状无线传感器网络。

［1］Tilakk S，ABU－Ghazaleh NB，Heinzelman W.A Taxonomy of wireless micro sensor network models［J］.Mobile Computing and Communications Review，2002，1（2）：1－8.

［2］黄新波.绝缘子泄漏电流在线监测系统的设计与应用［J］.电测与仪表，2007，44（4）：9－14.

［3］孙利民，李建中，陈渝等.无线传感器网络［M］.北京：清华大学出版社.2005.

［4］Marco Dorigo，Thomas Stutzle著，张军，胡晓敏，罗旭耀等译.蚁群优化［M］.北京：清华大学出版社.2007.

［5］冯春时.群智能优化算法及其应用［D］.中国科学技术大学，2009.

［6］余勇昌，韦岗.无线传感器网络中基于PEGASIS协议的改进算法［J］.电子学报，2008，36（7）：1309－1313.

［7］王阳光，尹项根，游大海等.基于无线传感器网络的电力设施冰灾实时监测与报警系统［J］.电网技术，2009，33（7）：14－19.

［8］李丽芬，朱永利，张君艳.基于隶属云蚁群算法的长链形无线传感器网络路由优化［J］.计算机工程与科学.2010，32（11）：10－14.

［9］Kumar R，Wolenetz M，Agarwalla B，Shin J，Hutto P，Paul A，Ramachandran U.DFuse.A framework for distributed data fusion［C］.In：Proc1st ACM Conf on Embedded Networked Sensor Systems（SenSys’03），Los Angeles，CA.November，2003.114－125.

［10］Zhang Su－bing，Liu Ze－min.A QoS routing algorithm based on ant algorithm［C］.In：IEEE International Conference on Communications，2001，5：1581－1585.

［11］张君艳，朱永利，彭伟.大规模带状无线传感器网络QoS路由优化的研究［J］.电力科学与工程，2010，26（4）：11－15.

The algorithm based on an ant colony algorithm for wireless sensor networks with long－chain structure

GAO Jing，ZHU Yong－li，LI Li－fen

（SchoolofControl＆ComputerEngineering，NorthChinaElectricPowerUniversity，BaodingHebei071003，China）

With the high demand of real－time and reliability of monitoring system of power transmission lines，an ant colony algorithm with negative information growth is presented.Each node is no need to maintain the global information，but the only number must be given.The timer is set for the current not feasible and congestion nodes.nodes can participate in routing when the timer is overtime.The simulation results show that the proposed algorithm can obtain better performance than basic Ant Colony algorithm.

Long－chain of wireless sensor network；Transmission line monitoring system；Ant colony algorithm；Routing

TP301

：A

1001－9383（2011）03－0019－06

2011－06－30

国家自然科学基金资助项目（60974125）

高 静（1985－），女，河北廊坊人，硕士研究生，主要研究方向为无线传感器网络.