基于混沌粒子群算法的无线传感器网络覆盖优化

摘 要:

为了改善传感器节点随机部署时的不合理分布,提高网络覆盖率,以网络覆盖率为优化目标,提出了基于混沌粒子群的无线传感器网络覆盖优化算法。该算法利用混沌运动的遍历性和随机性,克服了粒子群算法后期陷入局部最优的缺点。仿真结果表明，该算法比基本粒子群算法具有更好的覆盖优化效果。

关键词:

无线传感器网络;混沌;粒子群算法;覆盖优化;覆盖率

中图分类号:

TP393.04; TN915.04

文献标志码:A

英文标题

Coverage optimization of wireless sensor networks based on

chaos particle swarm algorithm

英文作者名

LIU Weiting, FAN Zhouyuan

英文地址(

School of Electronics and Information, Jiangsu University of Science and Technology, Zhenjiang Jiangsu 212003, China

英文摘要)

Abstract:

To improve the ueasonable distribution of sensors random deployment, increase network coverage rate, taking the network coverage rate as the optimized goal, an optimization method of wireless sensor networks coverage based on Chaos Particle Swarm Optimization (CPSO) was proposed in this paper. Based on the ergodicity, stochastic property of chaos, the algorithm can avoid the shortage of being easily trapped in a local extremum at the later evolution stage. The simulation results indicate that the addressed algorithm is superior to particle swarm optimization in coverage optimization.

英文关键词Key words:

Wireless Sensor Network (WSN); chaos; particle swarm algorithm; coverage optimization; coverage rate



0 引言

无线通信,以及嵌入式微机电系统技术的快速发展,使无线传感器网络成为可能。无线传感器网络在灾难预警与救助、环境控制、智能楼宇、精细农业等诸多领域都具有广阔的应用前景[1]。

对于无线传感器网络的各种应用,网络覆盖是一个重要的衡量标准[2-3]。为了达到预定的网络覆盖率要求,传统的方法是大规模部署静态节点,过多的节点容易引起通信冲突；而利用移动传感器节点则可以改善这种状况,考虑到移动节点的成本问题,如何优化移动节点位置,并使用有限的节点到达最大的覆盖范围,成为一个值得研究的领域[4]。文献[5]提出一种移动节点的最大覆盖范围的方法,建立远离和靠近两种模型,通过节点间距离调整节点位置；但随着节点数增加,计算量变得相当大。文献[6-7]提出基于粒子群算法的覆盖优化方法,这些方法均能够提高覆盖率,但是基本粒子群算法在空间搜索时,容易陷入“早熟”现象,影响覆盖优化效果。

本文将粒子群算法和混沌算法相结合,求解以移动传感节点位置为输入参数、网络覆盖面积为目标的无线传感器网络覆盖优化问题,提出了基于混沌粒子群的无线传感器网络覆盖优化方法。该算法利用粒子群算法较快的收敛速度和混沌搜索的遍历性、随机性,不仅保证了算法的收敛速度,而且有效避免了基本粒子群算法的“早熟”现象。仿真实验证明,该算法能有效地优化节点布局,扩大网络覆盖率。

1 问题描述

1.1 网络模型

假设在待监测区域内随机部署n个节点,用si代表无线传感器网络中的第i号节点,则传感器节点集合为s={s1,s2,s3,…,sn}。针对无线传感器网络特性,对网络作如下假设:

1)网络中的各节点具有相同的感知半径Rs 和通信半径Rc,且有Rc=2Rs。

2)各节点能够获取自身和其邻居节点的位置信息。

3)移动节点能量较充足,能够支持移动节点完成位置迁移过程。

1.2 节点测量模型

针对实际应用中监测环境的复杂性,以及节点二元测量模型的不够准确的缺点,本文采用文献[8]中的概率模型来计算网络覆盖率。设无线传感器网络中的节点si的坐标为(xi,yi)。监测区域中任意点P的坐标为(xp,yp),则节点si对目标点P的检测概率为:

Cp (si ,p) =

1, d(si ,p)≤Rs -Re

exp(-λ1 α1 β1 α2 β2+ λ2 ), Rs -Re< d(si ,p) < Rs+ Re 

0, 其他 (1)

其中:d(si,p)为传感器节点si与目标点P的欧氏距离;Re(0

图1是式(1)定义下,λ和β取不同值时目标点检测概率的变化曲线。

图片

图1 不同参数下的检测概率曲线



整个监测区域的传感器节点对目标点P同时进行检测的联合检测概率为: 

Cp(sall,p)=1-∏i=n(1-Cp(si,p))(2)

其中：sall为测量目标点的传感器节点集合。令cth为目标点能够被检测到的概率阈值,则目标点能被有效检测到的条件为:

minxp,yp{Cp(sall,p)}≥Cth(3)

1.3 网络覆盖模型

为了有效评价网络的覆盖性能,将待测区域划分成m×n个网格,再将单元格简化为像素点。本文中,网络覆盖率定义为满足式(3)要求的单元格数量占总的单元格数量的比例,即:

Cr=∑mxp=1 ∑nyp=1Cp(sall,p)m×n(4)

均匀性也是衡量网络覆盖质量的一项指标。覆盖的均匀性可以保证节点也分布均匀,这样可以让网络能量消耗相对均衡一些,避免由于能量耗竭而过早出现失效节点。均匀性一般用节点间距离的标准差来表示,标准差越小则覆盖均匀性就越好[9]。

U=1n∑ni=1Ui；Ui=(1ki∑kij=1(Di,j-Mi)2)12 (5)

其中:n为节点总数;ki为节点i的邻居节点数;Di,j为节点i和节点j之间的距离;Mi为节点i与其所有邻居节点之间距离的平均值;U为网络的均匀度,U越小,网络覆盖均匀性越好。

第2期 

刘维亭等：基于混沌粒子群算法的无线传感器网络覆盖优化



计算机应用 第31卷

2 基于混沌粒子群的无线传感器网络覆盖优化

2.1 粒子群算法基本描述

设搜索空间为j维,则粒子i根据式（6）、（7）来更新自己的速度和位置:

vk+1ij=w(k)×vkij+c1r1j((pbest)kij-xkij)+c2r2j((gbest)kgj-xkij)(6)

xk+1ij=xkij+vk+1ij(7)

其中:c1为微粒自身加速度权重系数；c2为全局加速度权重系数,r1j和r2j为0～1的随机数；xkij和vkij分别为粒子i在第k次迭代中第j维的位置和速度,二者均被限制在一定范围内;(pbest)kij是粒子i在第j维的个体极值的位置;(gbest)kgj是群体在第j维的个体极值的位置;w为惯性权重系数[6]。

w(k)=0.9-0.5kMax_step(8)

其中:k为当前的迭代步数,Max_step 为最大迭代数。

2.2 混沌优化算法基本原理

混沌优化算法的基本思想是利用类似载波的方法将混沌状态引入到优化变量中,并把混沌运动的遍历范围“放大”到优化变量的取值空间,然后利用混沌变量搜索[10]。用于载波的混沌变量选用Tent映射[11]:

Yi+1=2Yi,0≤Yi≤0.5

2(1-Yi),0.5

2.3 基于混沌粒子群的无线传感器网络覆盖优化算法

假设群体中有m个粒子,每个粒子中包含n个节点,每个粒子代表一种节点分布方案。以xi表示粒子i的位置向量,xi=(xi1,yi1,xi2,yi2,…,xik,yik,…, xin,yin)。其中,xi中各元素依次表示节点1到n的横、纵坐标。它所经历的最好位置记为pbest =(pbesti1,pbesti2,pbesti3,…,pbestid),d=2n；群体中所有粒子所经历的最好位置记为gbest。

不同粒子中节点具有不同的位置,不同的节点位置对应着不同的网络覆盖率。混沌粒子群优化算法基本思想是以基本粒子群算法为主, 将节点位置向量作为输入参数,式(4)作为目标函数。在每次迭代中,以概率pk对群体最优位置gbest进行混沌优化, 引导gbest跳出局部最优。进行混沌优化的概率pk表示为:

pk=1-11+ln k;k为当前的迭代步数(10)

基于混沌粒子群的无线传感器网络覆盖优化过程如下:

1)初始化n个传感节点位置,在监测域内随机生成各个粒子的速度和位置，并根据式(1)～(4) 计算初始节点随机分布的网络覆盖率。

2)初始化每个粒子的个体最优pbest和群体最优位置gbest。

3)对各个粒子,按式(6)～(7)更新速度和位置，重新根据式(1)～(4)计算每个粒子更新位置后的网络覆盖率。

4)将每个粒子更新位置后的覆盖率与pbest对应的覆盖率比较,如果较大,则更新pbest。

5)将群体中的每个粒子的个体最优pbest对应的覆盖率与gbest对应的覆盖率比较,如果较大,则更新gbest。

6)根据式(10)确定当前对gbest进行混沌优化的概率pk,同时生成一个0～1的随机数r,如果r

7)将gbest中各节点坐标映射到定义域[0,1]内,即Y0=gbest-ab-a,其中[a,b]为节点坐标范围。

8)由Y0根据式(9)进行迭代生成一组混沌序列Ym(m=1,2,…),把产生的混沌变量序列Ym通过逆映射gbestm=a+(b-a)Ym (m=1,2,…)返回到原解空间,得到m个解组合。

9)分别通过式(1)～(4)计算各个组合时的网络覆盖率,找出覆盖率最大的一组,同未进行混沌优化时的最优位置的覆盖率比较,如果大,则更新gbest。

10)如果达到预设最大代数,则结束,并返回群体最优分布;否则返回2)。

2.4 算法复杂性分析

由上述算法优化过程描述可知,算法的计算量主要是更新位置、速度,计算网络覆盖率和混沌迭代优化。设粒子群规模为M1,节点数为N,最大迭代次数为Max_step,混沌迭代优化次数为M2,待测区域划分成m×n个网格点。位置和速度更新的时间复杂度为O(Max_step×M1×2N),计算覆盖率的复杂度为O(Max_step×M1×m×n),而对于混沌迭代优化来说,在最坏的情况下,它的时间复杂度为O(Max_step×M2×2N)，因此算法总的时间复杂度为O(Max_step×(M1×2N+M1×m×n+M2×2N))，相比基本粒子群,只是增加了O(Max_step×M2×2N)。

3 仿真实验

3.1 仿真设置

假设在50m×50m的监测区域中随机部署40个无线传感器节点,所有节点感知半径Rs是5m,通信半径Rc为10m,概率模型中λ1=1,λ2=0,β1=1,β2=1.5,测量可靠性参数Re=0.5Rs=1.5m，c1=1,c2=1,Cth=0.8,Max_step=300。

3.2 实验结果与分析

为了对比分析算法的覆盖情况,采用相同的仿真条件,传感器节点的初始位置随机生成在监测区域,如图2所示。图中的“*”表示传感节点的位置,圆表示感知半径为Rs的区域。

图片

图2 初始节点分布



图3~4分别为经基本粒子群和混沌粒子群算法优化后的传感节点位置,如果节点间的距离小于或等于通信半径,则互为邻居节点,“—”表示两个节点互为邻居节点。

对比图3和图4,经基本粒子群算法优化后的节点分布不是十分均匀,重复覆盖较多,且可根据式(5)得出网络均匀度为1.14；而经混沌粒子群优化后的节点布局较为均匀,重复覆盖也相对较少,网络均匀度为1.06,比经基本粒子群算法优化后的网络均匀度低,可知后者具有更好的覆盖均匀性。

图片

图3 基本粒子群算法优化后的节点位置

如图5所示,网络的初始覆盖率为55.96%，在经过202次迭代后,基本粒子群算法下的网络覆盖率收敛至稳定值80.60%,不再增加；而此时混沌粒子群算法下的网络覆盖率为84.48%,待迭代300次后收敛到全局最优解,覆盖率达到84.56%。这说明,早期混沌粒子群算法相对基本粒子群能较快地搜索到群体最优值,而后期基本粒子群过早陷入局部最优,而混沌粒子群算法则依靠对群体最优位置的混沌优化,跳出局部最优,相对增强了全局寻优能力,这样可以更加有效地优化节点布局,提高网络覆盖率。

图片

图图片

图为了进一步验证本算法的覆盖性能,在不同的初始节点分布情况下,分别进行10次独立的优化实验,两种优化算法的平均覆盖率、300次迭代平均耗时、平均网络均匀度和每个节点的平均移动距离如表1所示。

表格(有表名)

表1 10次独立优化的覆盖性能比较

算法覆盖率/%耗时/s均匀度平均移动距离/m

基本粒子群81.051082.351.1725.52

混沌粒子群84.931468.221.0824.36



从表1可以看出,基于混沌粒子群的优化策略在覆盖率上相比基本粒子群优化策略提高约4%，且平均网络均匀度较后者低,这说明经混沌优化后节点分布更加均匀,节点能量消耗也相对均衡一些；同时,每个节点的平均移动距离少了约1.2m,这样可以减少由于节点移动所带来的能量消耗。由于混沌粒子群算法中增加了混沌优化环节,导致计算复杂度有一定增加,计算耗时相比基本粒子群多。不过,随着计算机软硬件技术的发展,通过功能强大的中心节点可以克服这个问题。

4 结语

本文将混沌优化和粒子群算法结合,应用到无线传感器网络的覆盖优化中,提出了基于混沌粒子群的网络覆盖优化算法。该算法采用更为精确的概率检测模型,以网络覆盖率为重要目标,对节点最优位置进行混沌优化,引导其跳出局部最优。仿真实验表明,该算法在提高网络覆盖率,减少节点移动距离,以及降低网络均匀度等方面,优于基本粒子群算法,能有效地实现使用有限的节点达到较高覆盖性能的目的。

参考文献:

[1]

于宏毅,李欧,张效义.无线传感器网络理论、技术与实现[M].北京: 国防工业出版社,2008.

[2] HUANG CF, TSENG YC. The Coverage problem in a wireless sensor network [J].Mobile Networks and Applications.2005,10(4): 519-528.

[3] CARDEI M, WU J. Energyefficient coverage problems in wireless Ad Hoc sensor networks [J]. Computer Communications, 2006, 29(4): 413 -420.

[4] WANG BANG, BENG L H, MA DI. A survey of movement strategies for improving network coverage in wireless sensor network [J]. Computer Communications, 2009,32(13/14): 1427 -1436.

[5] 何璇,郝群,宋勇.一种移动无线视频传感器节点的覆盖算法[J].传感技术学报, 2009,22(8): 1163-1168.

[6] WANG XUE, WANG SHENG. Dynamic deployment optimization in wireless sensor networks [C]// Intelligent Control and Automation, LNCS 344. Berlin: Springer, 2006: 182-187.

[7] 林祝亮,冯远静.基于粒子群算法的无线传感网络覆盖优化策略[J].计算机仿真,2009, 26(4):190-193.

[8] LI SHIJIAN, XU CONGFU, PAN WEIKE. Sensor deployment optimization for detecting maneuvering targets [C]// Proceedings of 7th International Conference on Information Fusion. Washington, DC: IEEE Computer Society, 2005: 1629-1635.

[9] 刘丽萍,王智,孙优贤.无线传感器网络部署及其覆盖问题研究[J].电子与信息学报, 2006,28(9):1752-1757.

[10]李兵,蒋尉孙. 混沌优化方法及其应用[J].控制理论与应用,1997,14(4): 613-615.

[11]程志刚,张立庆. 基于Tent 映射的混沌混合粒子群优化算法[J].系统工程与电子技术, 2007,29(1):103-106.

推荐访问:粒子 混沌 传感器 算法 覆盖