一种基于二进制差分算法的WSN多约束路由算法

肖 刚，贾国辉，周忠良

(1.中国电子科技集团公司第20研究所，西安 710068；2.国防信息学院，武汉 430010；3. 中航工业成都凯天电子股份有限公司，成都 610031)



一种基于二进制差分算法的WSN多约束路由算法

肖 刚1，贾国辉2，周忠良3

(1.中国电子科技集团公司第20研究所，西安 710068；2.国防信息学院，武汉 430010；3. 中航工业成都凯天电子股份有限公司，成都 610031)

针对无线传感器网络(WSN)中多约束路由算法问题，侧重考虑WSN在军事应用中的主要约束因素，利用二进制差分(BDE)算法良好的鲁棒性和记忆性，提出了一种基于BDE算法的路由算法。仿真实验表明该算法提升了寻找最优路由的时间，减少了网络的能耗，是一种有效的寻优方式。

无线传感器网络；二进制差分算法；多约束

0 引 言

在现代战场环境下，数据信息的实时采集传输逐渐成为影响战局的重要因素，而无线传感器网络凭借其成本低、规模大、自组织性和隐蔽性好等多方面特性正越来越多地应用到军事领域中，比如军情侦察、战场实时监控、目标定位追踪、核化攻击等多方面应用，尤其是在数据链的终端数据采集方面，无线传感器网络(WSN)可以通过其组网方式和可靠性来应对战争中某些传感器节点被摧毁的情况，使网络可以继续工作，所以如何让WSN拥有更好的可靠性和更长的使用寿命是WSN网络在战场应用中的一个重要研究方向。

路由算法是无线传感器网络中的一个主要的研究内容，WSN通过路由算法来寻找到达目的节点的最佳路径。在无线传感器网络的实际应用中，最佳路径的选择会受到多方面因素的制约，只有综合考虑各种因素的路由算法才能在现实应用中取得预想的效果。针对战场环境和数据链的应用要求，能耗问题、带宽问题和丢包率问题是本文关注的主要约束条件[1]。

二进制差分算法具有不错的收敛特性和鲁棒性，并且具有记忆能力，本文将其应用在多约束路由问题中，实验结果表明，二进制差分路由算法的寻优能力强于目前常用的蚁群算法[2]。

1 WSN网络多约束路由模型

能量的最大效能使用是无线传感器网络极其重要的设计标准，而随着WSN应用范围的扩大，应用场景的多样化，在例如高质量的战场场景中，丢包率和时延等服务质量参数也变成重要的衡量设计的标准，这就要求现实应用中无线传感器网络的路由算法满足多种约束条件，使算法更灵活，更具有实际应用价值。但低丢包率和低时延有可能会导致能耗增加，进而降低网络的使用寿命，所以对于面向实际应用的无线传感器网络，如何通过平衡优化路由算法来达到多约束条件下的能耗最少变得极为重要。

为了更好地研究该问题，需要建立一个可量化、易衡量的路由模型。在无线传感器网络中，节点间的能量差异性，通信能力的不同，信息传播环境的差别，这些因素都会影响最优路由的选择，这些差异性就导致在建立路由模型的过程中要考虑到这些约束条件。多约束路由问题就是在多个约束条件的制约下，找到最优路径的问题，进而可以让该问题抽象成求最小Steiner树问题。Steiner树是一棵连接所有节点的总代价最小的分布树，其连接特定图中的特定组成员所需的链路数最少，其中Steiner树的求解是一种P=NP的NPC问题，又由于在实际的WSN中存在多种约束条件，故复杂度高的算法不利于解决WSN中的多约束路由算法，而采用启发式算法求解Steiner树[3]。

在WSN中，主要考虑2个方向的约束条件，即业务指标和网络能耗。业务指标主要包括丢包率、时延、带宽以及时延抖动等指标，这些指标主要用来衡量服务质量的水平。网络能耗则包括了节点间传递带来的能量消耗以及节点自身维持工作所需要的能量[4]。

能耗:主要包括两方面：一是指节点单位时间内自身工作消耗的能量，二是指节点间传输单位大小的数据所消耗的能量。实际应用中，WSN中往往采用体积小巧的电池作为供电源，但其储电量有限，也就制约了网络的工作时间。若网络中作为枢纽的节点能量耗尽，容易对整体网络的持续生存造成威胁，所以平衡网络所有节点的使用情况十分重要。

带宽: 指节点间在单位时间内能通过链路的数据量。在WSN网络中，带宽参数主要由终端节点的自身特性决定，具体有业务带宽和路径带宽，前者取决于WSN网络的工作内容，后者则由参与传输的节点的自身带宽决定[5]。

时延: 一个节点从开始发送数据包到数据包发送完毕所需要的全部时间，在WSN中，时延主要受数据传输中的环境干扰、传输竞争、网络堵塞、数据处理等多方面因素的影响。

(1)

(2)

(3)

带宽约束：

(4)

时延约束：

(5)

能耗约束：

(6)

式中：BW、DL、EL分别为网络带宽、时延和能耗的约束限制。

以上3种约束是本文主要讨论的约束条件，本文在该3种约束条件限制下对路由算法进行讨论研究。

2 二进制差分算法原理

二进制差分算法(BDE)是一种源自生物圈中“优胜劣汰”思想的启发式智能算法。因为其具有较强的全局搜索能力和健硕的鲁棒性，而且算法的运算简单，所以近些年BDE被越来越多的研究人员所关注和研究，并应用到众多领域中去。区别于差分进化算法主要针对连续空间函数寻找最优解，二进制差分算法主要是针对离散空间的最优解问题[6]，使差分进化的思想应用到更广的范围中去。

BDE算法根据问题解个体间的差别重新组合成一个新的解空间，通过新解空间和初代解空间的比较，择优选出更优秀的个体，组成下一代的解空间，迭代运算，直到解空间趋近于最优解[7]。

BDE算法区别于基本差分算法，其解空间通过二进制编码，若只通过简单变异行为得到新个体有一定概率不满足解空间的约束条件，为了能满足取值范围，需先将解向量映射到[0,1]之间[8]，即：

(7)

而对于经过变异后，但不在范围内的解按照sigmoid函数映射到[0,1]之间，如公式(8)所示：

(8)

再将解空间按照公式(9)的分段函数，组成由0和1组成的解空间，最后执行交叉操作[9]：

(9)

3 二进制差分算法的WSN多约束算法描述

(1) 设置参数。缩放因子P，交叉概率常数CR，衰减因子α，迭代次数上限tmax，解个数k。

(2) 剔除不满足约束限制的链路，简化网络拓扑结构。

(3) 令t=1。

(4) 适应度评价。适应度定义为：

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

式中：A，C，F分别为fel，fbw，fdl的权重系数，表示节点能耗、带宽和时延在适应度中的比重，由于本网络比较关注能耗问题，所以权重系数设置如下：A=1，C=0.6，F=0.6。

(5) 变异、交叉操作。依据式(10)计算出全部个体的适应度，随机选取2条不同的等节点数的路径，将2条路径中除了源点和终点以外的点做差，乘缩放因子P加到路径Q的各节点上，作为新的路径。其中，路径Q为随机选出的第3个路径或种群最优路径。

(6) 差分选择。将(5)操作后的新路径，与Q进行比较，选择竞争胜利的路径进入下一代。

(7) 结束判定。若t

4 仿真实验及结果

分析用二进制差分算法和蚁群算法的求解最优解的性能，如图2、图3、图4所示，分别从费用、时延、能耗三方面对2种算法进行比较。

图2 BDE算法和ACO算法能耗比较

图3 BDE算法和ACO算法费用比较

图4 BDE算法和ACO算法时延比较

根据仿真结果分析，在算法运行的前18次，BDE算法可以迅速缩小最优解的搜索范围，而ACO算法在前期相对速度有些缓慢，原因是ACO算法寻找新解的效率不高，不能提高种群的多样性，相反BDE算法通过交叉变异生成新解，通过竞争产生下一代种群，可使种群的适应度水平明显提高。

当运行到18～63次的时候，BDE算法进入稳定搜索阶段，此时解的质量相对较高，所以迭代运算对于解质量的提升速度减缓，ACO算法也相比早期阶段进入相对缓慢的阶段，2种算法都在这个阶段取得接近最优解的路径。

最后运行至100次期间，BDE算法的迭代效果不明显，取得了最优解。而ACO算法几乎停滞了迭代，但只得到了局部最优解，优化效果不理想。

对2种算法分别进行50次算法运算，将50次运算结果取平均值进行比较，如表1所示。

表1 2种算法50次实验的平均指标

由表1可知，BDE算法整体求解能力和寻优效率优于ACO算法，尤其是在费用和能耗方面优势明显。ACO算法和BDE算法的平均迭代次数相差不大，但ACO算法得到的结果往往只是局部最优解，而BDE算法全局搜索能力更好，生成新解能力强，可以扩大路径的选择范围，因而BDE算法比ACO算法具有更好的求解能力。仿真结果表明，该网络最佳路径为(1→8→14→23→33→36→45)，对应的费用为61.75。

5 结束语

本文在分析WSN路由评价模型的基础上，提出一种基于二进制差分算法的多约束路由算法。仿真结果表明，该算法比传统算法有更好的寻找最优解的能力，其在多方面有较突出的性能指标。

[1] 于海斌，曾鹏，梁韦.智能无线传感器网络系统[M].北京：科学出版社，2006.

[2] 肖伟，全惠云．基于蚁群算法的多路径多约束QoS路由的研究[J]．计算机工程与应用，2008，30(7)：89-94．

[3] 胡细．移动自组织网络中若干问题的建模与分析[D]．上海：上海大学，2007．

[4]HusseinFarouekSalama．MulticastRoutingforReal-timeCommunicationofHigh-speedNetworks[D].Raleigh:NorthCarolinaStateUniversity,2006.

[5]WilliamStallings．无线通信与网络[M].北京：电子工业出版社，2006.

[6] 毕晓君．信息智能处理技术[M]．北京：电子工业出版社，2010.

[7]EngelbrechtAndriesP.计算群体智能基础[M].谭营译．北京：清华大学出版社，2009．

[8]DengCS,ZhaoBY,YangYL,etal.Novelbinarydifferentialevolutionalgorithmfordiscreteoptimization[A].ProceedingofFifthInternationalConferenceonNaturalComputation[C],2009:346-349.

[9] 毕晓君,王义新.多模态函数优化的拥挤差分进化算法[J].哈尔滨工程大学学报,2011,32(2):223-227.

[10]蔡慧，刘洪波.基于K均值聚类的随机网络拓扑模型[J].计算机工程与设计，2009，30(5)：1089-1901．

A WSN Multi-constraint Routing Algorithm Based on Binary Difference Evolution Algorithm

XIAO Gang1，JIA Guo-hui2，ZHOU Zhong-liang3

(1.The 20th Research Institute of CETC,Xi’an 710068，China;2.College of National Defense Information Science,Wuhan 430010，China;3.Chengdu CAIC Electronics Co.Ltd,Chengdu 610031，China)

Aiming at the problem of multi-constraint routing algorithm in wireless sensor network (WSN),this paper considers the main constraint factors of WSN applied to military,uses the perfect robustness and memory of binary difference evolution (BDE) algorithm to present a routing algorithm based on BDE algorithm.The simulation experiments show that this algorithm can improve the time of searching for optimal routing and reduces the energy consumption of network,so the routing algorithm in this paper is an effective optimization method.

wireless sensor network;binary difference evolution algorithm;multiple constraint

2014-12-10

TN915

A

CN32-1413(2015)02-0056-04

10.16426/j.cnki.jcdzdk.2015.02.015