基于改进蝙蝠算法的无线传感器网络的移动节点部署*

袁　曦， 张曦煌

(江南大学 物联网工程学院，江苏 无锡 214122)



基于改进蝙蝠算法的无线传感器网络的移动节点部署*

袁曦， 张曦煌

(江南大学 物联网工程学院，江苏 无锡 214122)

摘要:针对传统的无线传感器网络(WSNs)中存在的移动节点部署的分布不均匀、网络覆盖度太低等各种问题，提出了一种基于改进蝙蝠算法(BA)的移动节点部署策略，通过蝙蝠算法的收敛特性，不断迭代寻求问题的最优解，从而不断优化传感器节点的部署。Matlab仿真表明:提出的算法可以显著改善传感器节点的覆盖密度，并且节点分布也相对比较均匀。

关键词:蝙蝠算法； 无线传感器网络； 移动节点部署

0引言

无线传感器网络(WSNs)是由大量成本低、处理能力有限、能量资源受限的无线传感器节点组成[1,2]。节点通过一定的部署方法自组织形成网络，实现对目标区域的有效监控。而合适的网络部署对于无线传感器网络来说是至关重要的，良好的网络布局可以显著提高网络节点覆盖率、减少全局网络能量损耗、增加网络健壮性等。

目前已有很多对无线传感器网络移动节点部署相关的报导：文献[2]基于改进蛙跳算法提出新的策略，在一定程度上增加网络覆盖度，文献[3]针对蛙跳算法容易陷入局部最优解而提出基于虚拟力的改进蛙跳算法，文献[4，5]则通过改进鱼群算法优化移动节点部署。

本文基于改进蝙蝠算法(BA)，通过寻求最优解的过程，使网络节点部署均匀，改善网络节点覆盖度，优化网络能耗。

1蝙蝠算法简介

蝙蝠算法是剑桥大学的学者Yang提出的一种基于模拟自然界蝙蝠通过超声波进行搜索的群智能优化算法[6～12]。在蝙蝠算法中，将待优化问题的解作为搜索空间中的一个蝙蝠，每个蝙蝠都有其对应的适应度值，蝙蝠群体通过调整频率、响度、脉冲发射率，追随当前最优蝙蝠在解空间中进行搜索。大量研究结果表明：相对于粒子群算法、 遗传算法等群智能算法，蝙蝠算法可以动态控制局部搜索和全局搜索间的相互转换过程，较好地避免算法陷入局部最优解。

2基于蝙蝠算法的无线传感器网络节点部署策略

2.1无线传感器网络节点部署模型

现在假定在一个二维平面区域M2={(x,y),0≤x≤m,0≤y≤m}中，开始随机布置n个传感器节点，n个节点集合可以表示为w=(C1,C2,…,Cn)；对于特定节点Ck，其位置可以通过一定手段定位获得，现假设其位置表示为PCk=(xk,yk)，节点的感知半径为r，即每个节点的覆盖模型是以节点坐标为圆心，r为半径的圆。

若目标位置为P=(x,y)，则对于节点PCk，其与目标的距离为

(1)

节点PCk对目标P的覆盖度为

(2)

对于目标P，被所有节点联合检测到的概率为

p(C)=1-∏(1-Fxy(P,PCk)),

(3)

则无线传感器网络节点覆盖率为

(4)

对于所有传感器节点，假设相邻节点最大距离和最小距离为Dmax和Dmin，则节点相对部署均匀度为

E(w)=Dmin/Dmax.

(5)

显然，若E(w)越大，则所有传感器节点之间部署相对比较均匀。

通过式(4)和式(5),可以得到算法目标方程

FM(w)=αR(w)+βE(w).

(6)

其中,α和β为权值影响因子。

2.2改进的蝙蝠算法

在传统的蝙蝠算法中，蝙蝠的位置和蝙蝠的飞行速度都是随机生成，未考虑位置和速度的相关性，故存在一定缺陷，本文通过引进权值因子来改进蝙蝠算法。

假设某个蝙蝠初始位置是P，其初始速度为v0(i)，初始速度计算为：

假设二维平面区域中心为P0=(x0,y0),则蝙蝠与中心的距离为D

(7)

(8)

故

(9)

式中V为速度常量。

2.3部署策略

故通过蝙蝠算法和无线传感器网络节点网络模型，节点部署优化策略如下：

1)初始化节点个数和蝙蝠的个数。

2)随机初始化节点的位置，从而获取每个蝙蝠的信息。

3)根据设定的目标方程计算得到最优蝙蝠，并通过最优蝙蝠更新所有节点的位置和速度，更新公式如下

38%吡唑醚菌酯·啶酰菌胺水分散粒剂将2种不同作用机制的药剂混配，亩用药80 g，2年对黄瓜灰霉病的防治效果分别为80.16%和80.14%，说明该药剂对黄瓜灰霉病的防治效果优良，是防治黄瓜灰霉病的良好药剂。在黄瓜灰霉病发病初期施用第一次药，以后每隔7天用药一次，连续施药3次。以喷雾方式施用，使用制剂量40-80 g/亩为宜，可有效地控制黄瓜灰霉病发生蔓延，也可考虑和其它类型杀菌剂交替使用。

fi=fmin+(fmax-fmin)β,

(10)

(11)

(12)

4)对于最优蝙蝠，采取随机更新方式更新蝙蝠位置和速度，并更新蝙蝠响度和频度。

具体更新策略如下：

1)产生一个随机数rand1,如果rand1>ri(ri为第i只蝙蝠的脉冲频度),则对当前最优蝙蝠位置进行随机扰动得到新的位置，然后替换原位置。

2)产生一个随机数rand2，如果rand2>Ai(Ai为第i只蝙蝠的脉冲音强),并且f(bfi)>f(BF)(BF为当前最优蝙蝠)，则移动至更新后的位置。

3) 当满足步骤(2)条件，则根据式(13)和式(14)更新脉冲频度r和脉冲音强A

(13)

(14)

其中,t为迭代轮数，γ为脉冲频度增加系数，α为脉冲音强衰减系数。

4)若达到迭代次数或达到精度要求，则退出蝙蝠算法；否则，回到步骤(3)。

5)输出最优节点部署。

3仿真结果与分析

实验仿真环境如下：实验选择在50m×50m的正方形区域内随机分布25个节点，传感器节点感知半径r为5m，通信半径为2 r，蝙蝠数目为20，区域被均匀分成2 500个粒子，蝙蝠发出的脉冲频率范围[-1，1],最大脉冲频度r0=0.75，最大脉冲音强A=0.25，脉冲频度增加系数γ=0.05，脉冲音强衰减系数α=0.95。

实验中，随机生成25个传感器节点，由图可以看出初始的节点部署相对比较拥挤，分布不均匀，区域覆盖面积比较低，如图1。

图1　随机分布的传感器节点Fig 1　Randomly distributed sensor node

通过Matlab模拟，算法在运行50轮时，所有传感器节点分布如图2所示。

图2　算法运行50轮时节点部署Fig 2　Node deployment while algotithm is operating 50 round

算法在运行100轮时，所有传感器节点分布如图3所示。

图3　算法运行100轮时节点部署Fig 3　Node deployment while algorithm is operating 100 round

算法在运行150轮时，所有传感器节点分布如图4所示。

图4　算法运行150轮时节点部署Fig 4　Node deployment while algorithm is operating 150 round

从图2～图4可以看出:随着算法的不断迭代，传感器节点开始慢慢分散，重合度开始降低，范围覆盖度上升，说明算法对于无线传感器网络的移动节点部署可以在一定程度上进行优化，从而改善网络环境。

在相同面积区域和同等初始部署情况下,实验对于本文算法和基于蛙跳算法进行了5组实验,实验结果取5次平均结果,比较数据和图表如表1和图5。

表1　不同算法对比结果

图5　不同算法覆盖率随迭代次数比较Fig 5　Comparison of coverage rate of different algorithms with iterations

从表1和图5中可以看出:改进蝙蝠算法得到的覆盖率较基于蛙跳算法有所提高， 这有效地提高了节点的覆盖范围，并且从表1中可以看出，本文算法的执行效率也较基于蛙跳算法的有所提高。

4结束语

本文通过分析传统无线传感器网络节点部署的一些缺点，提出了基于蝙蝠算法的网络节点部署优化算法。新算法通过给定的目标方程不断迭代，最终寻求最优解，获得最优节点部署。实验仿真结果表明：算法显著改善了网络节点部署，使节点部署更加均匀，网络覆盖度也明显增加。

参考文献:

[1]Heinzelman W,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[2]龙腾，孙辉，赵嘉.基于改进蛙跳算法的WSNs移动节点部署研究[J].计算机工程，2012,38(5):96-98.

[3]徐跃州,张欣.无线传感器网络的虚拟力蛙跳优化布局策略[J].传感器与微系统，2014,33(6):49-51.

[4]廖灿星,张平,李行善,等.基于混合人工鱼群算法的传感器网络优化[J].北京航空航天大学学报，2010,36(3):373-377.

[5]周利民,杨科华,周攀.基于鱼群算法的无线传感网络覆盖优化策略[J]． 计算机应用研究,2010,27(6):2276-2279.

[6]盛晓华,叶春明.蝙蝠算法在PFSP调度问题中的应用研究[J].工业工程,2013,16(1):119-124.

[7]孙文捷,张惠珍,张健,等.基于Fuch映射的混沌蝙蝠算法[J].上海理工大学学报,2014(1):26-30.

[8]凌远雄,叶春明,郭迎迎.改进蝙蝠算法在Job-shop调度问题上的应用[J].科技与管理,2014(1):37-40，61.

[9]盛孟龙,贺兴时,王慧敏.一种改进的自适应变异蝙蝠算法[J].计算机技术与发展,2014(10):131-134.

[10] 李枝勇,马良,张惠珍.蝙蝠算法在多目标多选择背包问题中的应用[J].计算机仿真,2013(10):350-353.

[11] 王战备.基于蝙蝠算法的无线传感器网络节点定位[J].计算机工程与应用,2014，50(11):90-94.

[12] 刘长平,叶春明.具有混沌搜索策略的蝙蝠优化算法及其性能仿真[J].系统仿真学报,2013,25 (6):1183-1188.

Mobile node deployment of WSNs on improved bat algorithm*

YUAN Xi, ZHANG Xi-huang

(School of IOT Engineering,Jiangnan University,Wuxi 214122，China)

Abstract:Aiming at problems that in traditional wireless sensor networks(WSNs) distribution of mobile node deployment is uneven and low coverage of networks,propose a mobile node deployment strategy based on improved bat algorithm (BA),through convergence properties of BA constantly iterat,seek the optimal solution,so as to optimize deployment of sensor node constanrly.Matlab simulation shows that,this algorithm can improve coverage density of node and node distribution is homogeneous.

Key words:bat algorithm(BA); WSNs; mobile node deployment

DOI:10.13873/J.1000—9787(2016)03—0144—03

收稿日期：2015—06—11

*基金项目：国家自然科学基金资助项目(61170120)

中图分类号:TN 393

文献标识码:A

文章编号:1000—9787(2016)03—0144—03

作者简介:

袁曦(1991-)，男，江苏泰兴人，硕士研究生，主要研究领域为无线传感器网络、人工智能计算。