基于蚁群“觅食”机制的深海自组织网络路由算法F－ACO＊

田子希 胡洪宁 田林洁

（1.驻上海地区舰炮系统军事代表室 上海 200135）（2.海军工程大学 武汉 430033）

1 引言

基于节点地理位置信息的定向洪范算法能较好地解决在水声网络中寻找最优路径的问题［1］。但是这种算法将加重网络的负载，特别是当目标节点运动速度不大、网络中节点密度很稀松时，容易造成算法失败［13］。另外，在水下获得高精度的节点地理位置信息较难，这对于地理路由算法而言无疑是雪上加霜。因此，寻找一种不借助节点地理位置信息、但又不降低性能的算法就显得迫在眉睫了。

蚁群算法［2］最早是由 Marco Dorigo等学者在真实蚂蚁觅食行为的启发下提出的一种元启发式算法。开始是为了解决TSP［3］（旅行商问题），在随后短短的22年内，它的应用已经扩展到优化问题领域的方方面面，同时由最初的AS［2］算法衍生出一系列经典算法［4～5］，这些算法在组合优化问题方面取得了丰硕的成就［6］，国内有代表性的是张勇徳提出的多目标蚁群算法［7］以及金浩提出的“基于觅食－返巢机制”的蚁群算法 MO－FHACO［8］。其中，MO－FHACO算法的核心是将蚂蚁的信息素分为食物信息素和蚁巢信息素。即，从蚁巢出发的蚂蚁，释放蚁巢信息素，循着食物信息素到达食物源；从食物源返回的蚂蚁，释放食物信息素，循着蚁巢信息素最终回到蚁巢［8］。虽然这种机制能较好的解决一些连续域多目标优化问题，但在算法的初期信息素仍然困乏，蚂蚁比较盲目，收敛速度慢。这些问题导致蚁群算法很难在通信延时严重的稀疏深海自组织网络加以应用。

本文受蚁群觅食返巢的这一整个生物过程启发，提出一种新的“觅食”机制。并基于此机制提出一种新的深海自组织网络蚁群优化算法F－ACO。该算法能较好地解决稀疏网络普遍存在的“空洞”问题［9，11］；同时，随着通信次数的增加，数据包将越来越集中于当前网络最优路径进行传播，通信的时延与网络能量的消耗也越来越小。

2 基于蚁群“觅食”机制的深海自组织网络路由算法

2.1 “觅食”原理

遵循“食物的气味”来寻找食物，是自然界大部分动物最重要的基本生存技能之一，蚂蚁也不例外。本算法就是利用这一生物学特性，在蚁群算法中加入食物自身散发的信息素这一因素。即蚂蚁行走时释放蚂蚁信息素，食物自身散发引导蚂蚁前进方向的气味信息素。

深海 水 声 网 络 由 两 种 节 点 组 成［9，11］：super－node、normal－node。其中，normal－node构成深海通信网络的主体，负责数据信息的传递；super－node负责信息的产生与接收，它既有“食物”性质，又有“蚁巢”性质。具体如下：

1）开始的时候，super－node均为“食物源”，设定好各自“气味”传递的最大步数，在整个网络中进行F－ACO算法的第一部分：气味扩散算法。

2）当super－node有通信需求时，立即转变为“蚁巢”，并依照网络中各节点存放的目标super－node的“气味”信息，出动“蚂蚁”寻找两个节点之间的通信路径；

3）处于“食物源”的super－node，其“气味”信息素以“洪范”的方式迅速在全网蔓延，“气味”携带“食物源”的地理位置信息和标志信息；“气味”η浓度大小由到达该normalnode的所用跳数多少决定：跳数越多，“浓度”η越小。

4）“目标蚁巢”以“食物气味”作为信息素的初始条件，出动“蚂蚁”到“食物源”；即开始“蚂蚁”只走有“气味”的路线；随后，决定“蚂蚁”路径的由“气味”和“信息素”共同决定；

2.2 信息素更新机制

信息素包括：“食物气味”信息素和“蚂蚁”信息素。

其中，“食物气味”信息素是由“食物源”super－node发出的，发生在蚁群算法进行路径寻找之前，用于对信息素的初始化。从“蚁巢”super－node出发的蚂蚁初次寻找路径时，其邻节点的“食物气味”越浓，则被选为蚂蚁下一跳节点的概率越大。有了初始的食物信息素，蚂蚁避免了开始寻找路径时的盲目性。食物气味信息素的更新公式为

其中，Γfood为“食物源”super－node的气味信息素；L 表示气味最大能传递的跳数，这也和自然界法则一致；k表示从“食物源”到达该点共花了k跳转发；

在蚁群系统（ACS）［10］的更新机制基础上，本算法蚂蚁信息素的更新机制对局部更新策略进行了修改，具体更新机制如下：

1）路径构建

位于节点（初始为super－node，中间为 normal－node）i的蚂蚁c，根据伪随机比例规则从其邻节点中选择节点j作为下一跳节点。这个规则［2］如下

其中，q是均匀分布在［0，1］中的一个随机变量，实验时取q0＝0.5为固定参数。

2）全局信息素更新

每次迭代后，只有一只蚂蚁（至今最优蚂蚁）被允许释放蚂蚁信息素：

其中，Cbs代表该蚂蚁走过的路径长度。实验时ρ取0.5。

3）局部信息素更新

在路径构建过程中，蚂蚁每经过一条边（i，j），都将更新该边上的信息素，这一点与ACS算法一致，不同的是更新的规则不同，本算法按下式更新局部信息素：

其中，ε为蒸发系数，取0.1；Δτ0为蚂蚁释放的信息素，实验时取0.2。这两个值均为常数。初始的时候，默认网络中任意边的蚂蚁信息素均为0.1。

2.3 减少水声网络通信负载的措施

传统的ACO算法在路径寻找时，需要花费大量的网络通信负载和节点的信息发送能量，这对传播时延大、网络稀疏、节点能量有限的水下自组织网络是大为不利的。因此，为了减少网络通信负载，F－ACO算法进一步做以下处理：

1）气味扩算算法部分在网络节点播放自身信息、构建各自邻节点表的时候进行。具体如下：

（1）和normal－node构建邻节点表一样，super－node节点也是每隔一段时间在一跳范围内广播带有自身标识的信息帧。

（2）在网络中只有super－node节点的信息帧被转发。当normal－node接收到该信息帧时，首先判断是否接收过该帧，接收过则直接丢弃，否则进一步判断该帧是直接由super－node发送过来，还是由normal－node节点转发过来的。如果是前者，则首先回应一个带自身标识的ACK，通知super－node。然后将该帧中的步数减一，并在一跳范围内广播该帧；若是后者，则直接将该帧中的步数减一，然后在一跳范围内广播该帧一次。

2）将数据包的每一次传递作为蚂蚁算法进行路径寻找的一次迭代，同时对并行处理的蚂蚁做以下处理：

（1）数据包分为包头和包身。包身保存要发送的数据信息，包括源、目标节点；包头用于处理蚂蚁算法问题。保存的信息为：参加该数据包传递的各蚂蚁相关信息以及对应蚂蚁选择的下一跳节点的标识集合。

（2）节点接收到数据包时，首先根据包头的下一跳节点集合确定自己是否在选择之列。如果不在，则直接丢弃该数据包；否则，进一步确定是哪几只蚂蚁选择本节点的，然后保存这几只蚂蚁的相关信息，分别针对这几只蚂蚁进行下一跳节点选择。包头中其他没有选择本节点作为下一跳节点的蚂蚁信息则直接被该节点删除。

3 实验验证

实验采用的是文献［9，11～12］中所提及的网络模型，整个水声通信网络由400个“normal”节点构成，这些“normal”节点均被随机布置在10×10平方公里的正方形区域内，图1给出了网络中的节点初始分布情况。

图1 网络中节点的分布情况

初始化后，网络中各节点构建相应的邻节点表，同时FACO的第一部分算法也在此时进行。图2给出了网络中节点的邻节点图。为了加以区别，图3给出了网络中右上角的super－node（用“＋”表示）的进行气味散布，而左下角super－node接收“气味”的（用“蓝色＋”表示）实际情况。颜色代表各节点的“气味”浓度高低：浓度从高到底，颜色从红转变为蓝。

图2 节点的相邻情况

图3 “气味”在网络中的散布情况

由图3可见，距离“食物源”super－node越“近”，“食物的气味”越浓，中间的各节点颜色也越红。

DREAM是一种典型的定向洪泛路由算法，具有一定的代表性，因此本文将以此协议作为参照，通过仿真对比来检查F－ACO算法的性能。为了便于充分发挥DREAM算法的性能，除其他实验条件与F－ACO算法一致外，实验时还将网络中所有节点的地理位置信息作为已知条件告知DREAM。

实验场景为：一个super－node（左下“＋”）作为产生信息的源节点，在1小时内随机发送100个数据包给另一个目标super－node（右上“＋”）的情况。DREAM算法运行时，网络中所有节点均能获得自身的地理位置信息；F－ACO算法运行时，则不能获得节点的地理位置信息。

图4、图5分别给出了通信100次之后，两种算法进行数据包传递的实际路径。

由图4不难发现，由于网络的稀疏度较高，DREAM协议需要大量的节点参入到数据包的转发和重传过程中，但同时也保证了数据包沿着多条路径成功到达目标节点，协议的健壮性较好，相应的网络能量的消耗和资源的浪费也较大。同时，由于每次传递都是独立事件，算法并不保存路由表，因此在下一次传递时，同样甚至更多的网络能量和资源将被消耗。

相较于DREAM算法，虽然F－ACO算法不能使用节点的地理位置信息，但是在气味信息素与蚂蚁信息素的双重作用下，随着通信次数的增加，算法将越来越收敛于当前最优的路径进行数据包的传递，同时在2.3节介绍的减少网络通信负载的措施下，F－ACO进行数据包传递时所消耗的能量和时间会越来越小，最终分别固定于某一值。图6、图7分别给出了两种算法的时延对比图和每次传递网络能量消耗情况的对比图。

图4 通信100次后，采用DREAM算法的实际传播情况

图5 通信100次后，采用F－ACO算法的实际传播情况

图6 时延对比图

图7 每次传递消耗的网络能量对比

F－ACO算法在前20次的数据包传送过程中，气味信息素的影响使得蚂蚁偏重于选择“气味浓度”较高的节点。此时，蚂蚁选择路径完全依赖气味信息素，因此会有较多的节点参入路径的选择过程；在21次～100次数据包传送期，路径上信息素浓度的高低与信息素挥发系数成正比，而“气味浓度”在全部通信过程中并没有变化，使得蚂蚁有更大的可能探索新的路径。图6、图7中F－ACO的时延和能量损耗的抖动现象正是这种“探索”能力的有利证明。

DREAM算法不保存路由表，每次都利用节点的地理位置信息定向洪范数据包。在通信的初始阶段，下一次传送的数据包会受到上一次传送的数据包的干扰而增加数据包的传输试验，这也就解释了在前五次数据包分别传送时，传播时延会略有上升的现象；在第五次数据包传送之后，由于网络中的负载已经达到一个稳定值，网络的时延和每次传播的能量损耗会稳定于一个固定值。而在整个实验过程中，参入传播的节点会基本不变，因此每次能量的损耗也将是一个固定值。

4 结语

针对深海水声网络无法获知节点地理位置信息的情况，本文提出了一种替代高效地理路由协议的算法：FACO。该算法不需要知道节点的地理位置信息，路径寻找过程和数据包传递同时进行，在“气味”信息素与“蚂蚁”信息素的双重作用下，随着通信次数的增加，数据包的传递路径将越来越收敛于当前网络最优路径。实验证明F－ACO算法在减小时延、节约网络能源等性能方面都有出色的表现，在无法获知节点地理位置信息的深海水声网络中具有良好的应用前景。

［1］I F Akyildiz，D Pompili，T Melodia.Underwater Acoustic Sensor Networks：Research Challenges［J］.Ad Hoc Networks，2005，3（3）：257－279.

［2］Marco Dorigo，Thomas Stutzle.Ant Colony Optimization［M］.America，Cambridge：The MIT Press，2004.

［3］COLORNI A，DORIGO M，MANIEZZO V，et al.Distributed optimization by ant colonies［C］／／Proc of the first European Conference on Artificial Life.Paris：Elsevier，1991：134－142.

［4］GAMBARDELLAL M，DORIGO M.Ant－Q：a reinforcement learning approach to traveling salesman problem［C］／／Proc of the 12th international Conference on Machine Learning，1995：252－260.

［5］Thomas S，HOLGER H H.MAX－MIN ant system［J］.Future Generation Computer Systems，2000，16（8）：889－914.

［6］Gambardella L M，Taillare E D，DORIGO M，et al.Ant colonies for the quadratic assignment problem［J］.Journal of the Operational Research Society，1999，50（2）：167－176.

［7］张勇德，黄莎白.多目标优化问题的蚁群算法研究［J］.控制与决策，2005，20（2）：170－173，178.

［8］金浩，刘维宁.基于觅食－返巢机制连续域蚁群算法［J］.计算机工程与应用，2012，48（1）：24－26.

［9］HU Hongning，LIU Zhong，YANG Bin.BFDREAM：A new routing protocol for deep sea acoustic network［C］／／2010IEEE 10th INTERNATIONAL CONFERENCE ON SIGNAL PROCESSING PROCEEDINGS（ICSP2010）.Beijing：Springer Verlag，2010：2377－2381.

［10］Dorigo M，Gambardella L M.Ant Colony System：A cooperative learning approach to the traveling salesman problem［C］／／IEEE Transactions on Evolutionary Computation，1997，1（1）：53－66.

［11］HU Hongning，LIU Zhong，LI Lu.A real－time directed routing protocol based on projection of convex holes on underwater acoustic networks［C］／／The 3rd Internatioal Conference on Networks Security，Wireless Communications and Trusted Computing（NSWCTC2011）.Wuhan，2011：44－48.

［12］Rice J，Creber B，Fletcher C.Evolution of Seaweb Underwater Acoustic Networking［C］／／OCEANs 2000MTS／IEEE Conference and Exhibition，Providence，Rhode Island：IEEE，2000：2007－2017.