WSN中基于蚁群算法的单向链路路由算法

唐万伟

(唐山学院 智能与信息工程学院，河北 唐山 063020)



WSN中基于蚁群算法的单向链路路由算法

唐万伟

(唐山学院 智能与信息工程学院，河北 唐山 063020)

提出了一种无线传感器网络中基于蚁群算法的单向链路路由算法，该算法采用单向链路和双向链路相结合的方法，寻找源节点到目的节点的最优路径。仿真结果表明，该算法能够选择参数性能好的路径，最优路径上的总时延远远小于只支持双向链路的传统蚁群算法，而且最优路径的收敛速度明显加快，由此节省了无线传感器网络中的能耗。

无线传感器网络；路由算法；蚁群算法；单向链路

0 引言

无线传感器网络(Wireless Sensor Network，简称WSN)是由大量静止或移动的传感器以自组织和多跳的方式构成的无线网络，它以协作的方式感知、采集、处理和传输网络覆盖地理区域内被感知对象的信息，并最终把这些信息发送给网络的所有者。随着WSN技术不断的发展，近年来对WSN的研究也越来越受到人们的关注[1]。在WSN中，由于节点传输能力的不同，以及障碍物的阻挡等问题，会使得通信链路中存在大量的单向链路。因此有研究者提出了基于单向链路的路由算法，采用维护多跳反向路由的方法支持单向链路[2]，但这种方法的弊端是数据包在转发中需要携带完整的反向路由，加大了网络资源的消耗。而如何有效降低能耗以延长网络的生命周期是WSN中最具挑战性的关键问题之一[3-5]。有学者提出了一个应用到强连通支配集中的常数近似算法，将强连通支配集运用到强连通支配和吸收集中[6]，但是这种算法也增加了额外的开销。而有效利用极为有限的带宽资源是WSN设计中另一个关键问题。有学者在经典的AODV协议的基础上利用协作中继技术扩大覆盖范围来解决单向链路问题[7]，但是该方法用到WSN时会出现因覆盖范围扩大造成通信链路间的干扰问题。笔者在只支持双向链路蚁群算法[8]的基础上提出一种无线传感器网络中基于蚁群算法的单向链路路由算法，该算法采用单向链路和双向链路相结合的方法，寻找源节点到目的节点的最优路径。

1 路由算法分析

无线传感器网络中由于节点发射功率差异及干扰等因素会导致网络中单向链路的出现，如图1所示。目前所提出的路由协议大多是基于双向链路的，即把单向链路屏蔽，而只利用双向链路[9]。这些协议在某些情况下可能使通信无法正常工作，如图2所示。

图1 节点发射功率差异引起的单向链路

图2 屏蔽单向链路使得通信无法进行的情况

笔者根据传统的蚁群算法[10]，提出一种适用于WSN中的基于蚁群算法的单向链路路由算法，其中蚂蚁是网络中的控制报文，总体上分为前向蚂蚁(forward ants，Fants)、后向蚂蚁(backward ants，Bants)以及广播后向蚂蚁(broadcast backward ants，Bbants)，路由的选择是通过蚂蚁之间的交互信息来最终确定。该算法的路由建立过程的具体步骤如下：

Ⅰ.打开节点，使节点接入网络，并且每个节点都需要维护一个信息素表用来记录到邻居节点的转移概率。

Ⅱ.在源节点产生、发送m只Fants，并将源节点置于禁忌表tabuk中，其中k=1，2，…，m。m为在源节点发送的蚂蚁数目。禁忌表tabuk记录第k个蚂蚁走过的路径。

Ⅲ.根据下面的转移概率公式(1)选择下一跳节点，然后将该节点置于tabuk表中，重复本步骤直到源节点发送的m个Fants都找到目的节点或者没有下一跳节点可走时结束。

(1)

上式中，τij(t)表示t时刻在ij路径上积累的信息素强度；ηij(t)表示蚂蚁从节点i转到节点j的期望程度，allowedk={V-tabuk}表示蚂蚁下一步允许选择的节点集，V是节点i的邻居节点集；tabuk为禁忌表，表示蚂蚁k走过的节点集；α为信息启发式因子，表示轨迹的相对重要性；β为期望启发式因子，表示能见度的相对重要性。

Ⅳ.经过t时间后，源节点发送的m只Fants都完成了一个循环，此时判断每只Fants是否都找到了自己对应的目的节点，如是就生成一个相应的Bants单播出去。否则产生Bbants，寻找Fants到达节点前一跳的路径，到达前一节点后，依据相应的Fants中的信息更新信息素；中间节点重复本步骤，直到到达源节点。

Ⅴ.清空tabuk，跳到步骤Ⅱ，再顺序执行步骤Ⅲ，Ⅳ，Ⅴ步，直到k次迭代都完成。

该算法中，网络路由的建立过程即为源节点到目的节点的最优路径的寻找过程。

2 仿真与分析

将本文提出的单向链路的蚁群算法和只支持双向链路的蚁群算法，在两种网络拓扑的情况下做一比较。

第一种情况，在源节点和目的节点之间只存在单向链路。设计3个节点的网络拓扑图如图3所示。节点(x，y，z)代表实际通信中物体的三维坐标。仿真参数α=1，β=1，迭代次数K=20，每次迭代中Fants个数m=10，源节点S=1，目的节点D=3。对只支持双向链路的蚁群算法及WSN中单向链路的蚁群算法进行仿真。

图3 只有单向链路可到达目的节点的网络拓扑图

仿真结果表明，对于只支持双向链路的蚁群算法，源节点1始终无法找到目的节点3的路径。而运用WSN中单向链路的蚁群算法进行仿真时，能够找到到达目的节点的路径1→3，以及1→2→3，并会选择1→3作为传输路径以节省网络资源。

第二种情况，同时存在单向链路和双向链路的情况。设含有8个节点的网络拓扑图如图4所示。图中由于障碍物的阻挡在节点0和节点3之间，以及节点7和节点2之间存在单向链路。仿真参数同上。

图4 单向和双向链路同时存在的网络拓扑图

在此网络中存在8个节点，且有两条单向链路，设源节点为S=0，目的节点D=7分别对只支持双向链路的蚁群算法和WSN中基于蚁群算法的单向链路路由算法进行仿真，得出结果只支持双向链路的蚁群算法date1和WSN中基于蚁群算法的单向链路路由算法date2如图5所示。

图5 网络拓扑仿真结果

由图5可以看出，只支持双向链路的蚁群算法到达最优路径的收敛速度明显低于本文提出的WSN中基于蚁群算法的单向链路路由算法，并且当网络拓扑中存在的单向链路上的性能参数优于双向链路时，单向链路上的时延是小于双向链路的。

3 结论

本文提出的WSN中基于蚁群算法的单向链路路由算法通过使用单向链路和双向链路相结合的方式，使最优路径上的总时延远远小于仅支持双向链路的传统蚁群算法的总时延，因此节省了WSN网络中的能耗。

[1] 王辛果，张信明，陈国良.时延受限且能量高效的无线传感网络跨层路由[J].软件学报，2011，22(7)：1626-1640.

[2]RamashubramanianV，MosseDBRA.AbidirectionalroutingabstractionforasymmetricmobileAdHocnetworks[J].IEEE/ACMTransactionsonNetworking，2008，16(1)：116-129.

[3] 王小明，卢俊岭，李英姝，等.模糊随机环境下的无线传感器网络多约束多路径路由[J].计算机学报，2011，34(5)：779-791.

[4] 刘权，王晓东.MR2-GRADE：一种基于梯度值的无线传感器网络高能效多径干扰避免路由协议[J].电子学报，2011，39(3)：147-152.

[5] 郝晓辰，窦晶晶，刘浩然，等.基于链路质量的WSN代价均衡路由选择算法[J].电子与信息学报，2012，5(9)：1212-1218.

[6]ThaiMT，TiwariR，DuDZ.OnconstructionofvirtualbackboneinwirelessAdHocnetworkswithunidirectionallinks[J].IEEETransactionsonMobileComputing，2008，7(9)：1098-1109.[7] Yamada K， Umebayashi K， Kamiya Y， et al. A study on routing protocol suitable for directional links[J]. Radio and Wireless Symposium，2010，21：1596-1597.

[8] 孙艳歌，刘明，许芷岩.Ad Hoc网络中基于双向收敛蚁群算法的QoS路由算法[J].微电子学与计算机，2006，23(10)：1-3.

[9] 王换招，梅涛，姬凯，等.基于单向链路的低开销Ad Hoc路由策略[J].北京邮电大学学报，2010，33(2)：111-115.

[10] 胡祥培，丁秋雷，李永先.蚁群算法研究评述[J].管理工程学报，2008，22(2)：74-79.

(责任编校：夏玉玲)

A Unidirectional-Link Routing Algorithm for WSN Based Ant Colony Algorithm

TANG Wan-wei

(College of Intelligence and Information Engineering， Tangshan University， Tangshan 063020， China)

Based ant colony algorithm， the author of this paper proposes a unidirectional-link routing algorithm for wireless sensor network(WSN)， in which one-way links and two-way links are combined to determine the optimal path from the source node to the destination node. The simulation results show that the algorithm is capable of deciding best performance parameters， and that the total delay of the path is far less than that of the traditional ant colony algorithm， which supports only bidirectional links， and that the convergence speed of the path increases significantly， thus reducing the energy consumption in wireless sensor networks.Key Words： wireless sensor network； routing algorithm； ant colony algorithm； unidirectional link

唐万伟(1984-)，男，辽宁凌源人，讲师，硕士，主要从事无线通信技术、信号处理研究。

TP393

A

1672-349X(2016)03-0009-03

10.16160/j.cnki.tsxyxb.2016.06.003