基于蚁群算法的搜索区域受限的WSN 路由协议

张 波，安 乐，汤一波

（辽宁大学 信息学院，辽宁 沈阳110036）

0 引 言

无线传感器网络（wireless sensor network，WSN）是由大量具有通信与计算能力的微小传感器节点构成的自组织网络系统，是一种全新的信息获取和处理技术，广泛应用于国防军事，环境监测，反恐救灾及目标跟踪等领域［1－3］。

传感器节点的能量是无线传感器网络中最宝贵的资源之一，能量控制一直是无线传感器网络研究的焦点。为了有效延长网络生存时间，减少路径建立和数据传输时的能量消耗，下一跳节点的选取就成为了路由策略的关键。因此，设计节能，高效的路由协议成为无线传感器网络的研究热点［4，5］。

1 相关工作

蚁群算法是由Dorigo等人在1992年提出来的一种性能优良的启发式随机优化算法，它通过蚂蚁之间的信息交流与协作最终找到最优解。蚁群算法最初用于解决TSP 问题，后来用于模拟生物过程，网络路由优化，生产调度，车辆路径规划等复杂问题［6－8］。文献［9］提出一种基于蚁群算法的ARAWSN 算法，该算法采用了自适应和自组织的寻优机制进行路径的建立。ARAWSN 算法虽然可以找出网络中的最优路径，但是没有考虑节点的剩余能量，使得节点的能量消耗过快从而导致节点的快速死亡，减少了网络的生存时间。考虑到节点剩余能量带来的问题，文献［10］提出了一种多种群蚁群优化路由算法MACO。该算法能够均衡传输能量消耗和节点的剩余能量。但是MACO 算法在选择下一跳节点的时候没有考虑到该节点周围节点能量分布的情况，以至于全局节点消耗的不均匀，降低了网络的生存时间。文献［11］提出了基于位置意识的无线传感器网络路由算法ELACO，该算法限定了下一条节点的选择范围，有效地加快了最优路径的收敛时间。但是ELACO 算法对下一跳节点的选择范围限定的太小，使得产生的最优路径受到了一定的影响。

针对以上论文的不足，提出了基于蚁群算法的搜索区域受限的WSN 路由协议。该算法充分考虑了节点的周围能量密度，并对ELACO 算法的候选区域进行了改进，使得全局网络节点能量更加均衡的消耗，有效地增加了无线传感器网络的生存时间。

2 SACACO 路由算法

2.1 算法思想

随着传感器节点能量的消耗，传感器节点之间能量存在差异，使得网络中的能量分布情况极其的不均衡，按照传统的蚁群算法选择下一跳节点的时候一般只考虑节点本身的一些属性，例如剩余能量，邻居节点间距离等，并没有考虑该节点周围的能量分布情况，使得在最后形成的路径上进行数据传输的时候并没有使全网中能量消耗的更加均衡。如图1所示。

图1 节点能量分布

在图1中阴影部分代表区域能量比较高的地方，如果在选择路径时优先走这样的区域，必定会均衡全网的能量消耗。区域能量只是SACACO 算法考虑的一个因素，因为在建立路由路径时过分的突出区域能量的重要性可能会导致建立的路径增长，从而在传输数据时加大了能量的消耗。针对这个情况对蚁群算法进行了改进，节点的能量密度用单位面积内的能量大小作为衡量标准。SACACO 算法在设计转移概率公式的时候，把节点的周围能量密度作为一个重要因素。这样就可以实现全网能量的相对均衡的消耗。

为了寻找出最优路径，中间节点在选择下一跳节点的时候可能会遍历所有的邻居节点，导致发送过多的查询消息，从而消耗过多的节点能量。如果把节点的选择范围限制在一定的范围之内，那么就会大大减少这种不必要的查询扩散，从而大大的减少全网的能量消耗。

2.2 问题描述

为了方便描述，假设随机部署的无线传感器网络具有以下特点：

（1）网络中的节点随机部署。

（2）节点的通讯半径都是相同的。

（3）节点自身装有GPS系统，能够比较准确的测量自身的地理位置。

（4）无线链路是对称的。

无线传感器网络用G＝（V，E）表示，其中V＝｛v1，v2，…，vn｝表示传感器节点的集合，n 为节点的个数；E 为无线传感器网络边的集合。用di，j表示节点vi和vj之间的距离，R 表示每个节点的通讯半径。

2.3 基于蚁群算法的搜索区域受限的WSN 路由算法（SACACO）

定义1 节点vi的周围能量密度

式中：N（vi）（N（vi）＝｛vj｜di，j≤R，vj∈V，i≤n，j≤n｝）为节点vi的邻居节点集合，ei，ej为节点vi，vj的剩余能量。Si，j为以vi为圆心，R 为半径的圆和以vj为圆心，R 为半径的圆相交部分的面积。式（1）的物理意义是节点vi的R 通讯半径内单位面积所含有的能量值。

定义2 用R（vi，R）表示一个以vi为圆心，R 为半径的圆。用R（vs，ds，i）表示一个以Sink为圆心，以ds，i为半径的圆，其中ds，i为节点vi和Sink之间的距离。记圆R（vi，R）和圆R（vs，ds，i）的相交区域Qi为节点vi的前向候选区域。

定义3 位于节点vi的前向候选区域Qi中的节点称为节点vi的前向候选节点。节点vi的前向候选节点集合记为P（vi）。

在进行路由选择时，下一跳节点的集合不再是该节点所有的邻居节点，而是前向候选节点集合。如图2 所示。这样就限制了查询消息的扩散范围，减少了不必要的能量消耗，同时加快了路由路径的建立速度。

图2 节点的前向候选区域

这里提出一种新的蚂蚁前向选择概率模型，此模型考虑了节点的周围能量密度情况。在SACACO 算法中，蚂蚁m 按照下面定义的概率行为规则在前向候选区域中选择下一跳节点。在节点vi上的蚂蚁k选择下一跳节点的概率为

式中：τ（i，j）——节点vi到节点vj的信息素强度，τ（i，j）＝1／di，j，η（i，j）——能量启发函数，按式（3）计算

在式（2）中β是能量启发因子，用于反映在选择下一跳节点时剩余能量和周围能量密度的重要程度。β越大表示蚂蚁在选择下一跳节点时考虑剩余能量和周围能量密度的程度越大。

下一跳节点应该在前向候选区域中进行选择，这样每选择一个节点就会朝着Sink节点更进一步，直到Sink节点为止。在路径建立过程中，如果前向候选区域中没有节点，则路由无法选择下一跳节点，这样便陷入了路由空洞。如图3（a）所示，当节点vi在前向候选区域中选择vj作为下一跳节点时，节点vj发现自己的前向候选区域中没有节点，这时便陷入了路由空洞，节点vj为空洞节点。为了解决路由空洞问题，这里采用反馈算法，即当前向候选区域没有节点时，那么查询信息会返回到路由空洞节点的上一跳节点。上一跳节点在它的前向候选区域中重新选择下一跳节点，但这时选择节点的时候将不再选择路由空洞节点进行信息转发。如图3（b），路由空洞节点vj向上一跳节点vi发送路由不通消息，vi接收到消息后重新进行路由选择。当节点vi选择下一跳节点时，它就会从前向候选区域中选择节点vk，不再选择vj作为下一跳节点。

图3 路由空洞解决方法

前向蚂蚁k从源节点出发，到达下一个节点的时候按式（4）进行局部信息素的更新

式中：ξ——一个参数，ξ满足0＜ξ＜1，τ0——信息素的初始值。

当所有蚂蚁到达汇聚节点后，汇聚节点将对所有蚂蚁所携带的路径信息进行比较，从中选择最优路径；在最优路径上派出后向蚂蚁，并按式（5）进行全局信息素的更新

式中：ρ——信息素的挥发速率；Lbest（Lbest＝1／L）表示最优路径；L 是最优路径的长度。

在数据传输的时候，路径上有的节点可能会由于能量的过多消耗而死亡，这时数据传输会异常终止，数据无法及时到达汇聚节点。为了解决这个问题，SACACO 算法采用多路径算法。在源节点发现有源数据需要传输时，它会同时发出多个种群的蚂蚁，每个种群的蚂蚁之间互不干扰，这样最后就形成了多条路径，增加了路由成功率。

SACACO 算法的具体步骤如下：

步骤1 源节点派出前向蚂蚁。蚂蚁中含有源节点和目标节点ID 号，目标节点坐标，所经过的中间节点ID 号，所经过的中间节点之间的距离。

步骤2 根据当前节点的通讯半径和当前节点和Sink节点之间的距离，计算出当前节点的前向候选区域。

步骤3 在前向候选区域中根据式（2）计算出下一跳转发节点。如果本节点前向候选区域中没有节点，则执行步骤4；否则执行步骤5。

步骤4 根据路由反馈策略，向上一跳节点发送路由不通消息。上一跳节点在接收到消息后，在它的前向候选区域中选择次优节点进行路由信息转发。

步骤5 根据式（4）更新所走路径的局部信息素。

步骤6 所有的蚂蚁到达Sink节点后，在蚂蚁的最优路径上派出反向蚂蚁并根据式（5）更新全局信息素。反向蚂蚁到达源节点后，一次路由选择结束。

步骤7 重复执行步骤1～步骤6，直至达到最大循环次数或者90%以上的蚂蚁会选择同一条路径时，路由选择结束。

3 仿真实验与分析

实验将SACACO 算法与文献［6］的ARAWSN 算法，文献［7］的MACO 算法以及文献［8］的ELACO 算法在NS2仿真环境下进行了比较。进行五次独立实验，每次实验独立实验五次。实验的具体仿真环境是：在100×100m2的正方形区域内，五次实验部署的节点数分别是：100，120，140，160，180；每个节点的初始能量设为2J，通讯半径为30m。Sink节点的能量足够大。每个中间节点需要转发的数据包大小为500Byte。使用不同算法发送50 个数据报。设α为1，β为2。节点发送大小为k比特的信息给相距为d的目标节点时的能量消耗如下式所示

式中：E1——发送或接收的功耗，设为50nJ／bit；a，b 为这两种情况下单位功率放大所需能量，设为100pJ／bit／m2。天线类型为全向。

图4是在100×100m2区域中分布120个节点重复实验五次的时候所取得的平均结果。从中可以看出存活节点数随时间变化的关系，在算法ARAWSN，MACO，ELACO，SACACO 下，节点随着时间的增长逐渐减少；并可以看出执行算法ARAWSN 时，网络节点消亡的最快，SACACO算法消亡的最慢，从而可以得知SACACO 算法有着更长的网络生存时间。

图4 存活节点数随时间的变化

图5是区域中分布120个节点的时候执行各种算法所得到的结果，从图中可以看出SACACO 和ELACO 算法建立路径所消耗的能量差距不大，MACO 算法消耗的能量最大。这里可以说明SACACO 算法不仅可以增加网络的生存时间，而且在路径生成消耗上也有比较好的性能。

图5 不同算法生成路径所消耗能量

图6可以看出算法SACACO 算法有着较高的路径生成效率。这样可以提高网络对事件的反应速度，从而满足一定的对时间有一定要求的需求。

图7是使用不同算法成功发送50个数据包时节点的能量效率仿真结果。从中可以看出，使用ARAWSN，MACO，ELACO，SACACO 算法时节点能量效率总趋势依次增大。

综上所述，SACACO 算法综合考虑了传感器节点的周围能量密度情况，设置了比较合理的前向候选区域。使用蚁群算法能够更加智能的搜索和优化路由路径，有效的均衡了全网的能量消耗，增加了网络的生存时间。

图6 使用不同算法时的路径成功率

图7 使用不同算法时节点的效率

4 结束语

提出了一种新的基于蚁群算法的搜索区域受限的WSN路由协议SACACO。SACACO 算法设定了更加合适的前向候选区域，使得节点在选择下一跳节点的时候只能在前向候选节点集合中进行选择，从而限制了蚁群算法的寻路范围，减少了寻路过程中的能量消耗；SACACO 算法同时考虑了网络能量的分布情况，在选择节点的时候考虑节点周围能量的分布情况，使得最后形成的路径所经过的地方是能量相对比较密集的地方，从而有效地延长了网络的使用寿命。

［1］ZHAO Yonghui，SHI Haoshan.An energy－balanced routing algorithm in wireless sensor networks［J］.（Engineering Sciences），2011，43 （2）：103－108 （in Chinese）. ［赵永辉，史浩山.一种无线传感器网络能量均衡路由算法 ［J］.四川大学学报 （工程科学版），2011，43 （2）：103－108.］

［2］Yick J，Mukherjee B，Ghosal D.Wireless sensor network survey ［J］.Computer Networks，2008，52 （12）：2292－2330.

［3］WU Chengdong，CHEN Fei.A LEACH－based routing protocol for wireless sensor network to optimize QoS ［J］.Northeastern University：Natural Science Edition，2009，30 （8）：1091－1094 （in Chinese）.［吴成东，陈飞.优化Qos的基于LEACH的无线传感器网络路由协议 ［J］.东北大学学报：自然科学版，2009，30 （8）：1091－1094.］

［4］Conti M，Francesco M D，Passarella A，et al.Energy conservation in wireless sensor networks：A survey ［J］.Ad Hoc Networks，2009，7 （3）：537－568.

［5］LIN Kai，ZHAO Hai，YIN Zhenyu，et al.A clustering Hierarchy arithmetic based on Energy prediction for wireless sensor network ［J］.Acta Electronica Sinica，2008，36 （4）：824－828 （in Chinese）.［林凯，赵海，尹震宇，等.一种基于能量预测的无线传感器网络分簇算法 ［J］.电子学报，2008，36 （4）：824－828.］

［6］Dorigo M，Birattari M.Ant colony optimization ［M］／／Encyclopedia of Machine Learning.Springer US，2010：36－39.

［7］Donati A V，Montemanni R，Casagrande N，et al.Time dependent vehicle routing problem with a multi ant colony system［J］.European Journal of Operational Research，2008，185（3）：1174－1191.

［8］Wang W，Wang Y，Li X Y，et al.Efficient interference－aware TDMA link scheduling for static wireless networks［C］／／Proceedings of the 12th Annual International Conference on Mobile Computing and Networking.ACM，2006：262－273.

［9］LIANG Huawei，CHEN Wanming，LI Shuai，et al.ACObased routing algorithm for wireless sensor networks［J］.Sensor Technology，2007，20 （11）：2450－2455 （in Chinese）.［梁华为，陈万名，李帅，等.一种无线传感器网络蚁群优化路由算 法 ［J］.传感器技术学报，2007，20 （11）：2450－2455.］

［10］LI Jianbing，ZHENG Wei.New multiple ant optimization routing algorithm for wireless sensor network ［J］.Computer Applications，2009，26 （7）：2686－2687 （in Chinese）.［黎剑兵，郑巍.无线传感器网络多种群蚁群优化路由算法 ［J］.计算机应用研究，2009，26 （7）：2686－2687.］

［11］WANG Xiaoming，AN Xiaoming.An energy and location aware ACO based routing algorithm for wireless sensor networks［J］.Acta Electronica Sinica，2010，38 （8）：1763－1769 （in Chinese）.［王小明，安小明.具有能量和位置意识基于ACO的WSN路由算法［J］.电子学报，2010，38（8）：1763－1769.］