宋军全，周 凯*，华惊宇

(1.浙江工业大学理学院，杭州 310023；2.东南大学移动通信国家重点实验室，南京 210096)

无线自组网络MANET(Mobile Ad Hoc Network)是一种具有全新的信息获取、信息处理与传输技术的通信网络，具有组网快捷、灵活，且不受有线网络约束的优点，可用于紧急搜索、灾难救助、军事、医疗等环境中，具有广泛的应用前景。MANET已经引起了学术界和工业界的高度重视，被称为是21世纪最有发展前景的技术之一［1］。

MANET环境下，节点间的无线链路及由此而形成的网络拓扑结构随节点的位置分布和移动、信道的变化等因素呈现出动态变化的特性，网络的路由技术面临挑战。近年来，国际上对MANET路由协议的研究日趋活跃，除了表驱动路由协议和按需路由选择协议，信息理论学者还提出了合作分集路由，认为传统路由并不是最好的路由。合作分集通过多个中继采用广播传输发送信息，目的节点选择许多中继信号中最好的，或者将多个中继信号进行组合处理。这种路由方案必须对同一个信号经过多个路径传播后的同步和定时进行严格处理，或者对每一条中继的无线信道进行处理，网络节点计算非常复杂。传统的以节点为中心的分布式MANET网络路由复杂且每个分布式节点计算量庞大，造成网络传输的实时性、吞吐量、端到端延时、网络服务质量QoS(Quality of Service)等性能下降，不适合MANET。从而探索一种新型的路由协议，对MANET网络技术的研究具有重要的意义［2］。为此，很多研究者提出使用启发式算法进行路由搜索，如遗传算法、神经网络、Grover搜索算法、蚁群算法等［3］。

蚁群算法是近年来提出的一种源于大自然的仿生类算法，对于解决组合优化问题和通信网络问题有很好的应用前景。它主要通过蚂蚁在寻路过程中与环境之间的信息交换，实现蚂蚁群体间的信息传递，并最终达到寻找最优路径的目的。蚁群算法通过信息素的不断更新，实现最终收敛于最优路径的目的。蚁群算法是一种正反馈机制，同时具有随机性、自适应性和分布式等特点，适合并行计算和求精确解。因此，本文沿用了蚁群算法思想，并将其融入MANET路由设计方案，以更好地解决路由的能量控制问题，提高网络生存时间，最终实现合理有效利用网络资源的目的。

1 网络节点特性数学模型

MANET节点之间是靠无线电进行通信，可以建立网络节点一阶能量消耗模型，如图1所示。发送数据能量消耗包括发射电路耗能、放大电路耗能两部分，接收数据只有接收电路消耗能量。一阶能量消耗模型数学模型可以表示如下［4］:

图1 MANET网路节点一阶能量消耗模型

其中，ETx表示发送者能量消耗，ERx表示接收者能量消耗，Eelec表示发射电路和接收电路的能耗，l表示发送数据包包含的比特数，d表示传输距离，εfs是常数。上述参数典型值为:Eelec=50 nJ/bit，εfs=10 pJ/(bit·m2)［5］。

网络中所有节点处于动态移动状态，本节将描述网络节点的运动状态以及节点间的连通状况。节点i在时刻t的位置、速率和运动方向可以依次表示为(xi(t)，yi(t))、vi(t)、θi(t)。因此，节点运动特性可以用下式描述［6－7］:

在时刻t，节点i和节点j之间的距离可以表示为式(3):

在MANET中，两节点间直接通信距离为R。如果两点间的距离小于R，则两节点可以直接通信；否则两节点间需要通过中间节点转发才可以进行通信。定义节点连通性矩阵D(t)=(dij(t))N×N。如果元素为“1”，表示两点间可以直接通信，如果元素为“0”，表示两节点间不能直接通信。因此，矩阵中的元素应满足如下条件:

在时刻t，节点i的节点度Degreei(t)表示与此相连接的节点数量，可以表示如下:

2 基于能量控制的蚁群优化算法

根据网络节点特性分析，本节将结合蚁群算法思想，建立基于能量控制的蚁群路由算法。该算法的基本原理是:当进行路由搜索时，上一跳节点i需要考虑以下两方面进行路由选择:与之相邻节点j组成的链路剩余能量τij(t)；与之相邻节点j的度数Degreej(t)。通过以上两个方面，从而确定节点j作为下一跳节点的概率。

链路的剩余能量是由组成这条链路的两端节点的最少剩余能量所决定，当其中一端节点因能量消耗而退出网络时，此条链路也就失效。因此，链路剩余能量τij(t)的计算方式可以如下所示:

其中，Ei(t)表示节点i在时刻t的剩余能量。通过以上分析，可以给出相邻节点j被选择作为下一跳节点的概率 pij(t)表示如下［8－9］:

其中，α和β两个参数分别反映数据在网络传输过程中所积累的剩余能量信息和节点度数信息在路由选择过程中的相对重要性，α+β=1。

本文提出的基于能量控制蚁群路由模型，其具体算法如下:

Step 1:当需要进行网络数据传输时，首先确定源节点标号s和目的节点标号k。寻找源节点一跳范围内的节点j，形成节点集合J{j|dsj(t)=1}。比较目标节点标号k是否在集合J中:如果是，则终止计算，选择节点k进行信息传输；如果不是，则进行节点概率计算［10－11］。

Step 2:寻找上一跳节点i一跳范围内的节点j，形成节点集合J{j|dij(t)=1}，将判断目标节点标号k是否在集合J中或者跳数是否超过上限。如果在集合J中或者跳数超过上限，则终止计算；否则，根据式(7)，计算每个一跳范围内节点j的被选择pij(t)，选择高概率的节点作为下一跳节点。节点m被选择作为下一跳节点的条件如下所示:

Step 3:完成节点概率计算，确定下一跳节点进行数据转发后，循环进行Step 2，直到目标节点标号k出现在下一跳的集合J中或者跳数达到上限为止［12］。

综上所述，基于能量控制的蚁群路由算法模型框架图，如图2所示。

图2 基于能量控制的蚁群路由算法模型框架图

3 网络仿真

为了进一步分析提出的基于蚁群优化思想的路由协议的性能，本节建立了网络仿真模型对协议进行分析。在一个1 000 m×1 000 m的网络中，散落着80个节点，这些节点在网络中随机移动。移动的速度在［0，5 m/s］之间变化，运动角度在［0，2π］之间随机变化，变化概率服从均匀分布。当节点在下一时刻将要运动至边界时，进行反向运动。在网络中假设每个节点的一跳通信范围是100 m。在初始时刻，节点的位置分布如图3所示。

为了说明基于蚁群优化思想的路由协议的优越性，本文定义网络中最后一个节点退出网络的时间为表示网络生存时间的指标，最后退出网络的节点被称为瓶颈节点。最后一个节点退出网络的时间越迟，说明网络的生存时间越长。动态源路由协议DSR(Dynamic Source Routing)是一种典型的按需驱动路由协议，许多路由协议都在DSR协议上发展而成。本节采用Matlab软件进行网络仿真，每个节点最初时的能量为“1”。在基于能量控制的蚁群路由算法中，参数 α=β=0.5，ρ=0.5。对网络的两种协议(DSR路由协议与蚁群算法路由协议)进行仿真，得到瓶颈节点能量的仿真图如图4所示。由图可见，基于蚁群优化思想的路由协议能够提供保障网络能量，从而提高网络生存时间。

图3 网络节点位置分布图

图4 两种算法协议下的瓶颈节点能量变化图

为了分析α和β两个参数对于网络剩余能量所产生的影响，对不同的参数组合进行网络仿真，仿真图如图5所示。由图可见，基于蚁群优化思想的路由协议下，不同的参数α能够提供不同的网络能量保障。

图5 各种参数下网络能量仿真图

4 结束语

在深入分析无线自组网络路由协议之后，提出了一种基于蚁群优化思想的路由算法。在这种方法中，首先系统地分析网络节点能量变化特性；然后基于蚁群能量优化思想建立节点选择概率函数；最后选择高概率的节点进行数据转发。仿真结果表明:该文提出的路由算法能够提供能量保障、延长网络生存时间等特点，弥补了已有算法的不足。

［1］任敬安，涂亚庆，张敏，等.基于蚁群优化的Ad Hoc网络生存时间和其他网络性能平衡路由协议［J］.计算机工程与科学，2011，33(11):15－24.

［2］曲大鹏，王兴伟，黄敏，等.移动自组织网络下的基本蚁群路由算法［J］.计算机应用，2011，31(5):1166－1169.

［3］王镇，刘学军.WSN中基于蚁群算法的Qos路由协议［J］.传感技术学报，2011，24(11):1625－1631.

［4］周少琼，徐祎，田上成，等.基于蚁群算法的Ad hoc网络节点信息感知路由研究［J］.探测与控制学报，33(1):75－79.

［5］梁淑萍，毛力，马亦先.基于蚁群算法的Ad Hoc网络QoS组播路由研究［J］.微电子学与计算机，28(7):28－33.

［6］胡彧，王静.基于蚁群算法的LEACH协议研究［J］.传感技术学报，2011，24(5):747－751.

［7］陈凤超，李融林.基于路由代价的无线传感器网络蚁群路由算法［J］.华南理工大学学报(自然科学版)，2011，39(5):36－43.

［8］莫桂江.蚁群－遗传算法的无线传感器网络路径优化［J］.微电子学与计算机，2011，28(9):54－59.

［9］黄如，苗澎，陈志华.基于预测模式蚁群优化的传感网节能路由机制究［J］.传感技术学报，2010，23(5):701－707.

［10］Liao W H，Kao Y，Fan C M.Data Aggregation in Wireless Sensor Networks Using Ant Colony Algorithm［J］.Networks and Computer Applications，2008，31(4):387－401.

［11］郑慧君，张巍，滕少华.基于改进蚁群的无线传感器网络路由［J］.计算机应用研究，2010，27(1):99－100.

［12］Kallapur，Pranesh V Chiplunkar，Niranjan N.Toplogy Aware Mobile Agent for Efficient Data Collection in Wireless Sensor Networks with Dynamic Deadlines［C］//Advances in Computer Engineering(ACE)，2010 International Conference on Bangalore，Karnataka，India，2010:352－356.