朱大伟,李纪欣

1(太原科技大学 计算机科学与技术学院,太原 030024)

2(中国电子科技集团公司第三十三研究所 科技发展事业部,太原 030032)

无线传感器网络(Wireless Sensor Network,WSN)[1]是由大量静止或移动的传感器节点组成,节点通过自组织的无线通信协议实现数据处理、传输以及通讯等功能形成的分布式并行系统.近年来在野外监控、军事监测等众多领域受到广泛关注和应用.WSN 节点[2]一般随机部署在目标监测区域内,节点能量通过自身干电池提供,由于地理环境和节点的分布特点,更换电源的可操作性差,所以能量成为制约无线传感器网络生命周期的首要因素.为了充分合理利用无线传感器网络,依据无线传感器网络节点随机分布和节点能量有限的两个特性.两个问题需要着力解决,一个是在随机分布的节点之中尽快找到一条尽可能最优的收敛路径,另一个是保证收敛路径上的节点消耗尽可能少的能量且相对负载均衡,以延长节点使用时长和网络的生命周期.

为了寻找最佳路径,国内外展开广泛深入的研究,很多切实有效的方法被提出.其中最具代表性的是将蚁群算法与无线传感器网络路由算法相结合.蚁群优化算法将问题求解的快速性、全局优化性以及高度的自组织性等特点合理结合,与无线传感器网络低能耗、自组织的大规模网络路由快速建立要求极其相似,有助于建立面向数据为中心的汇聚路由[3].梁华为将蚁群算法与无线传感器网络路由算法相结合,提出了最基本的蚁群无线传感器路由算法ARA (ACO-Based Routing Algorithm)[4],寻优能力十分有限.在此基础上,焦斌改进的蚁群算法IARA (Improved Ant-based Routing Algorithm)[5],综合考虑了节点剩余能量,传输方向和节点距离等因素,重点改进了蚁群算法的概率公式.此外,罗旭提出了改进的蚁群算法OARA (Optimization in Ant-based Routing Algorithm)[6],考虑到节点之间的距离和节点的剩余能量,在概率公式中引入罚函数和动态权重因子.然而上述的各种改进蚁群算法综合起来存在蚁群算法收敛与否取决于搜索半径的选择、路径存在往返跳跃导致额外能量消耗、选取节点能量过低无法支持信息传输等问题.

为了克服上述弊端,本文通过采取“三步递进式”寻找下一跳候选节点的方法来优化传统蚁群算法,并分别提出了DEARA (Dynamic Energy ARA)和DDEARA(Dynamic Direction Energy ARA)蚁群算法.首先,DEARA 算法通过分别引入动态半径搜索因子保证蚁群算法能够收敛和能量预测因子避免节点能量过度消耗出现负值的不合理现象.其次,DDEARA 算法在DEARA 算法基础之上引入方向因子[7],避免反方向无关节点被选为下一跳候选节点,进一步提高算法寻优能力.DEARA 和DDEARA 蚁群算法优化措施是在逐步缩小下一跳候选节点的范围,这一具体的确定性因素,而不是仅仅提高了某些节点被选为下一跳节点的概率值,这一随机性因素,使得寻优结果符合预期设想.

1 系统模型

1.1 网络模型

本文研究的无线传感器网络模型如图1所示,由N个随机分布的无线传感器节点构成自组网多跳网络模型[8].图中,无线传感器节点随机的部署在一定区域内,位置相对固定且具备自定位功能.无线传感器网络可以通过区域内分布的无线传感器节点,实时采集区域内的相关信息,并以“自组织”的方式构建一条通路,通过最外侧的节点(网关),将信息经基站sink 节点汇总到因特网中,以便后期的分析处理.为了分析方便且不失一般性,考虑网络中分布的所有节点一致,即符合相同的能量传输模型,且初始能量相同为E0(不妨设E0为单位1 J).定义剩余能量值小于Einit(Einit=0.1 J)的节点为死亡节点,该节点的剩余能量已无法成功传输一次完整数据,因此不能被选为下一跳候选节点.为了便于死亡节点的分析,下面重点分析节点能量传输模型.

图1 无线传感器网络模型

1.2 能量传输模型

在无线通信过程中,网络节点能耗主要包括电路损耗与功率放大损耗[9],文献[10]给出了相应的能量损耗模型,当前节点W向距离为d的节点传输Bbit数据时,如果两通信节点之间间距为d(d≤d0)就选取自由空间模型,通信节点数据传播速率衰减和d2成正比.当位置间距为d(d>d0)就选取多路径衰减模型,且数据传输所损耗能量和d4成正比.由此给出节点传输数据能耗如式(1)所示:

在节点通信过程中,每个节点接收并处理B bit数据时所需要消耗的能量如式(2)所示:

其中,Eelec表示传感器网络在传输或者接收数据时电路上的损耗.εamp代表数据在多路径衰落模型传输过程中的损耗.

2 蚁群系统(ACS)算法模型

1992年Dorigom 在他的博士论文中首次引入了蚁群算法(Ant Colony Optimization,ACO)[11].蚁群算法是一种启发式的仿生进化算法,属于随机搜索算法的一种[12].蚂蚁从巢穴出发寻找食物的过程中,根据其他蚂蚁在路径上留下的“信息素”浓度,最高效率的寻找到离巢穴最近的食物.基本蚁群算法作为最原始的蚁群算法,在解决小规模旅行商问题时全局收敛速度快,但是在面对大规模旅行商问题时全局收敛速度较慢.针对这些问题,Dorigo 和Gambardella 在1997年共同提出了蚁群系统(Ant Colony System,ACS)[13].在基本蚂蚁算法基础之上提出了3 点改进.首先,下一跳状态转移规则得到优化.其次,只在最优路径上作全局信息素更新.最后,全局信息素的更新的同时结合局部信息素更新规则.

2.1 下一跳状态转移规则的优化

在ACS 中,蚂蚁 对下一跳节点的选择都是根据一个伪随机比例[14]来进行的,从当前节点i到下一节点j的选择遵循式(3)～式(5).

其中,α表示信息启发因子,表明轨迹的相对重要性.β表示期望启发因子,表明能见度的相对重要性.τij表示信息素浓度,ηij为路径启发因子,q0(0

2.2 局部信息素的更新

为了加强蚂蚁的搜索能力,结合极大极小蚁群算法[15],引入信息素的最小浓度 τmin,信息素的最大浓度τmax,这样能够避免因为某些路径的信息素浓度过大或者过小,导致蚂蚁过分集中而陷入局部最优,制约了蚁群算法的全局搜索能力.局部信息素更新公式如式(6)～式(8).

其中,τmin表示信息素最小浓度,τmax是信息素的上限值最大浓度,ρ为信息素的挥发系数,其值越大意味着路径上的信息素挥发越快,取值范围在(0,1).∆ τij表示本次循环中路径 (i,j)上 的信息素增量,表示蚂蚁k在(t,t+1)的时间段内留在路径(i,j)上的信息素量.Q表示信息素强度,是常量固定值,Lk为蚂蚁k在本次循环中经过的路径长度.

2.3 全局信息素的更新

在ACS 算法中,当所有蚂蚁完成一次迭代后,会对蚂蚁搜寻到的最优路径进行全局信息素更新.而其它非最优路径的信息素则按一定的系数不断减少.这样可以使大多数的蚂蚁下一次优先选择最优路径,提升了ACS 算法收敛速度.信息素全局更新公式如式(9)、式(10).

其中,Lelite表示一代所有蚂蚁搜索完成后全局最优路径的长度.

3 算法改进

传统蚁群优化算法均集中在提高节点被选中的概率值(随机事件发生的概率值),依然存在很大的盲目性与不确定性.本文改进算法通过逐步缩小下一跳候选节点的范围,然后在有限的候选节点范围内依照概率值进行选取下一跳节点,这样摆脱了传统蚁群算法的完全随机性.

3.1 动态半径搜索因子

利用动态半径搜索因子寻找下一跳候选节点能够提高蚁群算法的收敛性.动态半径搜索因子使得蚂蚁在当前半径圆内找不到下一跳候选节点时,即可通过扩大搜索半径直至能够找到下一跳候选节点为止,从而保证蚁群算法最终能够收敛.

蚂蚁k首先在以当前节点W为圆心,半径为r的圆内寻找符合条件的下一跳候选节点,如果半径为r的圆内没有符合条件的下一跳候选节点,则扩大搜索半径r至 2r,在半径为 2r的圆内继续寻找符合条件的下一跳候选节点.图2中显示有符合条件的节点1 和节点2,因此将节点1 和节点2 选为下一跳候选节点.动态半径搜索因子优势在于能够避免蚂蚁直接在较大半径范围内寻找下一跳候选节点.虽然下一跳节点离当前节点距离越远,本次蚂蚁寻找路径越容易收敛,但是由于距离较远,根据能量消耗公式可知,距离越大消耗的能量越大.经过一次完整数据传输之后,节点可能消耗了所有的能量,间接导致本次寻优的路径失效又要重新寻找最优路径.所以要限制蚂蚁搜索半径范围,优先在小范围内寻找下一跳候选节点,这样能够使更多节点参与到收敛路径中,通过多点参与均衡相邻节点之间距离,降低单个节点能耗,提高单个节点传输数据的次数,进而达到延长无线传感器网络寿命的目标.

图2 动态半径搜索因子示意图

3.2 能量消耗预测因子

节点能量消耗预测因子的引入,能够规避当节点消耗完剩余能量却没有传完所有数据的不利情况发生.蚂蚁在寻找下一跳候选节点时,首先要判断当前节点W和下一跳候选节点1 传输kbit数据时所要消耗的能量值E2是否大于当前节点W的剩余能量值E1.只有当(E2≤E1)时节点1 才会被成功选为下一跳候选节点.传统蚁群算法一方面由于没有能量消耗预测机制,很可能造成当前节点剩余能量值消耗完却只传输了部分数据,这样的一次传输工作是失败的,不仅浪费了当前节点和之前所有节点传输数据消耗的能量,而且还造成当前路径终点不可达.另一方面传统蚁群算法默认节点只要有能量就能继续工作且能够传完整数据,可能造成节点工作一次后剩余能量值为负的不合理现象.

3.3 方向因子

通过引入方向因子寻找下一跳候选节点,避免了反方向的无关节点被选中成为下一跳候选节点.传统的蚁群算法搜索下一跳候选节点时,都是在以当前节点W为圆心,半径为r的整个圆内寻找下一跳候选节点,可能寻找到与当前节点W和sink 节点N连线反方向范围内的节点2 作为下一跳候选节点,这样就增加了路径长度,既浪费节点能量又弱化算法寻优能力.方向因子的引入,可以限制下一跳候选节点在当前节点W和sink 节点N连线正方向的正负 90◦范围内寻找.如图3所示,当前节点W在r半径圆内有符合条件的节点1 和节点2,因为节点2、当前节点W以及sink 节点N形成的夹角 β (β>90◦),因此直接舍弃节点2.同理根据方向因子在节点3 和节点4 中选择节点3 作为下一跳候选节点.这样有利于蚂蚁一直在往 sink 节点N的方向寻找下一跳候选节点,避免找到反方向的无关节点,减少路径长度节约节点能量消耗,提高算法寻优能力.

图3 方向因子示意图

3.4 最优路径评价公式

传统蚁群算法依据路径最短评价指标寻找最优路径,仅仅考虑路径的距离长短,评价指标非常单一,本文算法评价指标引入了节点平均剩余能量、节点最小剩余能量、最短路径长度、条数、节点剩余能量方差.

其中,Eaver表示节点平均剩余能量,Emin表示路径所经过节点中消耗能量的最小值,表示第m只蚂蚁第k次迭代后走过的路径长度,表示第m只蚂蚁第k次迭代后走过的路径上的节点个数,表示第m只蚂蚁第k次迭代后走过的路径上所有的节点剩余能量值的标准差.

的数值越大代表的路径越好,每迭代完一次将最大值对应的路径作为本次迭代最优路径,然后更新此路径上的信息素,便于后继的蚂蚁寻找路径时优先考虑这条路径,所有的迭代完成后即可选出符合上述条件的最优路径.评价指标中引入节点剩余能量标准差,有利于最优路径上各节点剩余能量值大小接近.如果各节点剩余能量值悬殊太大,这样的路径可能发送一次完整数据就出现了死亡节点,此条路径就不能继续使用,必须重新寻找一条最优路径.

4 仿真实验及结果分析

为了验证上述的优化蚁群算法DDEARA 的有效性,采用蒙特卡洛方法进行计算机模拟仿真实验.在一个(10×10)的范围内,随机布置S(S=100)个传感器节点.为了便于描述且不失一般性,不妨设点(0,0)为起始发送节点,点(10,10)为终端sink 节点,整个仿真实验中共有t(t=100)代蚂蚁且每一代蚂蚁有n(n=100)只.每次传输2 000 bit数据.仿真结果如图4.

4.1 最优路径连线图

图4对比了ARA、IARA、OARA、DEARA、DDEARA 5 种算法最终收敛的最优路径连线图,直观显示了各种算法路径经过的节点个数以及节点分布情况.

从表1中可以看出ARA、OARA、IARA 算法各方面性能效果都差,由于ARA、OARA 算法路径中参与的中间节点个数非常少,导致收敛路径消耗的能量也非常小,但是相邻节点之间的距离很大.IARA 算法中参与的中间节点过多,尤其是存在很多反向节点,导致最终收敛路径长度较长以及路径耗能非常大.DEARA算法相比上述3 种算法收敛效果明显改善,最优路径长度适中,最关键的是相邻节点距离适中,但路径中仍然有较多中间节点尤其是反向的无关节点,导致路径消耗的能量仅次于IARA 算法.DDEARA 算法相比上述4 种算法性能效果最好,最优路线长度短,相邻节点之间距离适中,参与的中间节点个数合理,路径消耗的能量也很合理.由此可见动态半径搜索因子能够提高算法收敛能力,能量预测因子能够减少节点能量消耗,方向因子能够避免反向无关节点选取.

图4 5 种对比算法最优路径连线图

表1 不同算法性能对比

4.2 节点消耗总能量、剩余总能量

图5对比了ARA、IARA、OARA、DEARA、DDEARA 5 种算法各个节点最终平均能量消耗和剩余能量情况,直观显示了各个节点能耗分布情况.

从图5中可以看到,ARA、OARA、IARA 算法出现节点消耗能量值E2(E2>1J)、剩余能力值E1(E1<0J)的不合理现象,而DEARA、DDEARA 算法中节点消耗能量值E2(E2≤1J)、节点剩余能量值E1(E1≥0.1J),能量预测因子避免了节点能量过度消耗,不会出现节点剩余能量值为负的不合理现象.

图5 5 种算法节点能耗

4.3 DEARA、DDEARA 算法节点能耗

图6对比了DEARA、DDEARA 2 种算法各个节点平均能量消耗和剩余能量情况,直观显示了各个节点能耗分布情况.

图6 DEARA、DDEARA 算法节点能耗

图6显示了在DEARA 算法中节点消耗能量值E2普遍在(0.8−1J)范 围内,剩余能量值E1普遍在(0−0.2J)范围内.在DDEARA 算法中接近2/3 的节点产生了能量消耗且能量消耗值均匀分布在(0−1J)范围内.表明DDEARA 算法中参与的节点数目适中,节点位置分布均匀.

4.4 DEARA、DDEARA 算法每一代节点死亡个数

图7对比了DEARA、DDEARA 2 种算法每一轮迭代过程中出现的死亡节点个数,直观显示了首次出现死亡节点的迭代次数,以及每一代死亡节点个数分布情况.

图7 DEARA、DDEARA 算法每一代死亡节点个数

由图7可知 DEARA 和DDEARA 算法都是在45 代首次出现了死亡节点.DEARA 算法单次迭代死亡节点个数最多为8 个,而DDEARA 单次迭代死亡节点个数最多为2 个.DDEARA 算法死亡节点个数以及死亡节点出现的代数明显优于DEARA 算法.

4.5 DEARA、DDEARA 算法收敛路径长度

图8对比了DEARA、DDEARA 算法最终收敛路径的长度,直观显示了两种算法在整个迭代过程中最优路径的长度趋势.

图8 DEARA、DDEARA 算法收敛路径长度

图8显示DEARA 算法最终收敛路径长度在18.37,DDEARA 最终收敛路径长度在15.77,DDEARA 算法由于方向因子的引入,避免选取反向无关节点,使得寻优效果非常好,收敛路径更短.

5 结论与展望

针对现有的蚁群算法无法保证路径最终收敛,节点能量过度消耗,路径上存在无关节点等情况.本文首先通过引入动态半径搜索因子和能量预测因子,提出了改进的蚁群算法DEARA,一方面动态半径搜索因子能够保证蚁群算法最终收敛并提高了蚁群算法的收敛效果.另一方面能量预测因子使得节点能耗均匀且不会出现消耗完节点剩余能量却不能成功传输完整数据的情况.但是在DEARA 算法收敛路径中仍然存在部分反方向的无关节点,因此在DEARA 算法基础上通过引入方向因子提出了DDEARA 算法,方向因子避免了路径中反方向无关节点的选取,优化效果非常明显.经过“三步递进式”的蚁群算法优化,首先,使得最终的最优路径长度较短,经过的中间节点数目适中且位置分布均匀.其次,使得节点能耗较少,不会出现某区域节点集中死亡的现象.最后,使得路径上没有反方向的无关节点存在,减小路径长度,节约节点能耗.“三步递进式”蚁群算法DDEARA 寻优能力更强且寻优效果更好,提高了无线传感器网络的使用性能和寿命.

未来一方面可以着重研究“过载”节点能耗问题,本文没有考虑某个节点被多条路径同时选中为下一跳节点的情况,这样的“过载”节点由于承担多条线路的数据传输任务,导致这样的“过载”节点耗能严重,相比其他节点过早成为死亡节点,严重影响网络使用寿命.未来应该考虑节点的“负重”系数,严格限制节点同时被多条路径经过.另一方面可以考虑路径中一旦出现死亡节点之后,怎么样快速寻找其他节点代替死亡节点,恢复正常工作.