莱维飞行的粒子群优化算法在WSNs 覆盖增强中的应用*

2015-04-01 12:19谢佳华
传感器与微系统 2015年11期
关键词:网络覆盖覆盖率节点

卢 玲,谢佳华

(武警工程大学 信息工程系,陕西 西安710086)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)广泛应用到国防军事、环境监测、交通管理、医疗健康、工商服务、反恐抗灾等诸多领域[1,2]。WSNs 最早源于军事应用,也是目前最为成熟的应用领域,广为人知的有美国的智能微尘、C4ISRT 系统、沙地直线等,这些系统的共同特点是协助实现了战场态势的有效感知,以其独特的优势,达到了实时性、准确性、全面性获取战场信息的目的[3,4]。

WSNs 面临的挑战之一是节点能量的有限性,一般情况下节点的能量不能补充,能量耗尽后节点就不能完成信息的采集、传输等任务,关键节点死亡后,还可能破坏网络的性能,导致整个网络瘫痪。节点的合理部署是WSNs 应用中首先要考虑的问题,能够为解决节点能量、网络通信带宽、计算处理能力等资源受限难题提供条件[5,6]。通过节点部署,能够优化利用网络资源、提高网络效率,进而改善感知、传感、通信等服务质量[7]。

目前,国内外诸多学者对WSNs 的覆盖控制进行了深入的研究,提出和改进了大量切实可行的算法应用到该领域,达到了很好的效果。Ian F Akylidiz 在文献[8]中深入地总结了覆盖中应该考虑的问题和解决的方法。陶丹等人在文献[9]中综述该领域国内外研究进展的同时,讨论了有向传感器网络覆盖的基本理论和算法,并提出亟待解决的问题。文献[10 ~12]分别从不同的角度改进粒子群优化(particle swarm optimization,PSO)算法并应用到WSNs 的覆盖控制中。文献[13]证明了PSO 算法比其他算法在WSNs 覆盖优化中具有明显的优势。

PSO 算法存在的最大缺点是容易陷入局部最优,可能搜索不到全局最优值[14],为了解决这一问题,本文提出一种将莱维飞行(Levy flight,LF)策略与PSO 相结合的(LFPSO)算法。在WSNs 覆盖优化过程中,每次粒子更新完位置后,不直接计算优化覆盖目标函数,而是使用LF 进一步更新个体的位置,而后再计算目标函数值,避免陷入局部最优,达到提高粒子群算法的优化性能的目的,从而提高了PSO 算法的收敛速度和求解能力。

1 相关模型的建立

本文根据研究实际,建立了节点感知模型、网络覆盖模型和覆盖优化数学模型,并对模型进行了具体的描述。

1.1 感知模型

感知模型的确定是研究WSNs 覆盖的基础[15]。目前,主要的感知模型包括布尔感知模型、概率感知模型、精确感知模型和有向感知模型四种[16],如图1 所示,根据应用的实际需求和研究目的的不同,可以选取不同的感知模型。

图1 节点感知模型Fig 1 Node sensing model

本文采用精确感知模型,具体数学描述如下:设监测区域为二维区域,可以设Si(i=1,2,3,…,N)为传感器节点集,N 为节点个数,其中,Si的坐标为(xi,yi)。Pj为监测区域内的任意一点,则Si对Pj的感知概率为

式中 d(Si,Pj)为感知节点Si到监测区域内点Pj的欧氏距离,当节点的感知半径为Re时,则在本文中设r1=0.5Re,r2=Re。α 是与传感器节点物理性能和感知环境有关的参数。

根据上式,对于监测区域内确定的一点Pj,所有传感器对它的联合检测概率可以表示为

式中 Sall为该监测区域内的所有感知节点集合。设置一个目标被传感器检测到的联合概率阈值φ,则传感器被监测到的限制条件为

1.2 覆盖模型

监测区域可以划分为m×n 的网格,每个网格是否被覆盖用式(2)来确定,而是否满足覆盖率用式(3)判断。所以,区域覆盖率可以定义为满足式(2)且满足式(3)的网格数与总的网格数m×n 的比值

设监测区域的总节点数为S,工作节点数为S',则工作节点利用率可用表示为

节点均匀分布的WSNs,其能量的消耗会均衡一些,这样可以避免失效节点过早出现,起到平衡负载、节省能量的作用。覆盖均匀性一般用节点间距离的标准差来表示,即

其中

式中 Ci为第i 个节点与邻居节点的距离;n 为节点总数目;Ki为第i 个节点的邻居节点(传感范围相交的节点)的个数;Dij为第i 个节点与第j 个节点之间的距离;Mi为第i个节点与其所有邻居节点的距离的平均值。

1.3 覆盖优化数学模型

根据覆盖模型可知,在WSNs 工作过程中,希望在满足一定覆盖率的前提下,工作节点数越少越好,节点利用率越低越好,另外,节点之间的均匀性也对网络的性能起到重要作用,显然,节点的覆盖均匀性值越小越好。所以,综合式(4)、式(6)、式(7)的加权作为WSNs 覆盖优化的目标函数

其中,w1,w2和w3为权值,w1+w2+w3=1。

2 LF-PSO 算法

本文尝试引入布谷鸟算法与PSO 算法结合,降低陷入局部最优的概率。

2.1 LF 策略

LF 行实际上是一种随机行走的方程,更新公式为

其中,α 为步长因子,⊕表示点对点的乘法,由上式可知,下一次位置由当前位置和转移概率共同决定,L(λ)为服参数λ 的随机搜索向量,L(λ):μ=t-λ,1 <λ <3,该分布说明了位置的变动符合幂律分布的随机变动过程。LF 的位置更新策略可表示为

2.2 LF-PSO 算法步骤

PSO 算法在计算早期具有较好的收敛速度,但在后期计算中容易陷入局部最优解,是因为在计算初期能保持很高的种群多样性,然而随着迭代次数的增多,大多数群体集中在一个最优解的附近,便出现了早熟现象。为了解决这一问题,在处理WSNs 覆盖问题的过程中,本文提出LF—PSO 算法,其流程如下:

1)设置WSNs 传感器节点覆盖环境;

2)初始化参数:种群规模,粒子速度、位置,最大迭代次数maxIter;

4)判断是否符合设定的终止条件,若符合,转步骤(8),否则,转步骤(5);

7)r 为随机产生的一个数,r∈[0,1],若r >0.5,则根据式(9)重新更新鸟巢的位置,并继续更新个体的历史最优位置和全局最优位置,否则,转向步骤(5);

8)输出WSNs 节点覆盖的最优解;结束。

3 仿真优化

3.1 参数设置

为了验证LF-PSO 算法在WSNs 覆盖优化中的有效性,对该算法在Matlab 2008 上进行仿真。

首先找出在规定区域内达到预期覆盖率所需要的节点数,并求出覆盖率随着节点数增加的增长率;然后在不同节点数的情况下分别比较PSO 算法和LF—PSO 算法的优化效果;最后分别比较在相同仿真条件下不同算法覆盖优化性能。

参数设置为:区域为10 m×30 m;节点数为35;感知半径1 为3 m;网格为20(row)×60(column));迭代次数为200。

3.2 仿真实验

本文设置以下3 个仿真实验分别从不同的角度验证算法的有效性:

实验1:在规定的监测区域内分别随机抛撒从15 个到50 个传感器节点,每次传感器数比上一次递增5 个且每次随机抛撒5 次,并分别计算它们的覆盖率的平均值(平均值为5 次抛撒所得覆盖率的平均值)及其覆盖率的增长率。仿真结果图如图2 所示。

图2 节点数与覆盖率及其覆盖率增长率的关系Fig 2 Relationship between number of node and coverage ratio and its rate of increase

实验2:在规定的区域内分别随机抛撒从15 ~50 个传感器节点,每次传感器数比上一次递增5 个,分别用PSO 算法和本文提出算法进行覆盖优化,覆盖率情况如图3 所示。

图3 两种PSO 算法的覆盖优化性能比较Fig 3 Coverage performance comparison between two kinds of PSO algorithms

实验3:在监测区域随机抛撒35 个传感器节点,计算其覆盖率,并计算在PSO[12]、人工鱼群算法[17](artificial fish swarm algorithm,AFSA)、遗 传 算 法[18](genetic algorithm,GA)在相同优化条件下的覆盖率以及LF—PSO 算法的覆盖率。在覆盖率的求解过程中,采取5 次抛撒求平均覆盖率的方法。比较结果如表1。

表1 不同算法优化下的覆盖率比较Tab 1 Comparison of coverage rate under different algorithms optimization

3.3 仿真分析

实验1 的仿真结果显示:在随机部署的情况下,对于规定的监控区域(10 m×30 m),当传感器节点数低于35 个时,覆盖率随着节点数的增加而以较快速度增长,当节点数多于35 个时,覆盖率的增长率随着节点数的增加而缓慢增长,综合覆盖率曲线图和覆盖率增长率曲线图可知,当传感器节点数目为35 个时,为覆盖率增长的临界点,所以,对于该区域,选取35 个传感器节点进行优化比较合适。

由实验2 仿真结果可知,传感器节点数目不同的情况下,分别用PSO 算法和LF—PSO 算法进行优化,后者的优化效果明显比前者的要好,证明了LF—PSO 算法性能的优越性。

实验3 通过与其它文献提出的覆盖优化算法进行比较,在相同环境下的仿真结果显示:LF—PSO 算法能够较大程度地提高覆盖率,其原因主要在于LF—PSO 算法能够跳出局部最优值,使搜索结果最大限度的接近最优值,所以,该算法寻优能力更强。

4 结 论

本文针对传统的PSO 算法在实际应用中存在的不足,将LF 搜索的遍历性的特点与PSO 算法结合起来,克服了传统粒子群算法容易陷入局部最优的缺点,大大提高了算法的寻优能力。通过仿真实验表明:本文的算法有效可靠,能够较好地解决网络覆盖的优化问题。但在具体应用中如何使用PSO 算法进行覆盖优化,还需要进一步研究。

[1] 刘 军,朱维杰,陈岚岚,WSNs 在战场态势感知应用中的关键技术研究[M].北京:人民警出版社,2014.

[2] 邢冬平,段 富,樊茂森.基于极坐标的无线传感器网络覆盖盲区发现算法[J].传感器与微系统,2014,33(9):117-119.

[3] 魏 勋.基于虚拟势场的三维传感网覆盖控制技术研究[D].南京:南京邮电大学,2014.

[4] Sajadian S,Ibrahim A,Pignaton de Freitas,et al.Improving connectivity of nodes in mobile WSNs[C]∥2011 IEEE International Conference on Advanced Information Networking and Applications(AINA),IEEE,2011:364-371.

[5] He Xin,Yin Ke,Gui Xiaolin.The area coverage algorithm to maintain connectivity for WSNs[C]∥Ninth IEEE International Conference on Computer and Information Technology,CIT’09,IEEE,2009:81-86.

[6] 孙 朋.基于概率模型的无线传感器网络覆盖增强方法[D].南京:南京邮电大学,2014.

[7] Wang Bang,Lim Hock Beng,Ma Di.A survey of movement strategies for improving network coverage in wireless sensor networks[J].Computer Communications,2009(32):1427-1436.

[8] Ian F Akyildiz,Mehmet Can Vuran.Wireless sensor networks[M].HoboKen:John Wiley&Sons Ltd,2010.

[9] 陶 丹,马华东.有向传感器网络覆盖控制算法[J].软件学报,2011,22(10):2318-2334.

[10]刘丽萍,王 智.基于改进PSO 算法的WSNs 覆盖优化方法[J].计算机工程,2011,37(8):82-84.

[11]冯智博,黄宏光,李 奕.基于改进粒子群算法的WSNs 覆盖优化策略[J].计算机应用研究,2011,28(4):1272-1275.

[12]王华东,李 巍.混沌粒子群算法在WSNs 覆盖优化中的应用[J].科技通报,2012,28(8):114-119.

[13]Pratyay Kuila,Prasanta K Jana.Energy efficient clustering and routing algorithms for wireless sensor networks:Particle swarm optimization approach[J].Engineering Applications of Artificial Intelligence,2014(33):124-140.

[14]朱海系,李 平,程 剑.基于改进算法的PSO 算法的WSNs覆盖优化方法[J].计算机工程,2011,37(8):82-84.

[15]赵 旭,雷 霖,代传龙.无线传感器网络的覆盖控制[J].传感器与微系统,2007(8):62-66.

[16]Wang P,Dai R,Akyildiz I F.A differential coding-based scheduling framework for wireless multimedia sensor networks[J].IEEE Transactions on Multimedia,2013,15(3):684-697.

[17]黄瑜岳,李克清.基于人工鱼群算法的无线传感器网络覆盖优化[J].计算机应用研究,2013,30(2):554-556.

[18]殷卫莉,陈 巍.遗传算法在无线传感器网络覆盖中仿真研究[J].计算机仿真,2010,27(10):120-123.

[19]仲元昌,陈 锋,李发传,等.大规模无线传感器网络覆盖优化算法[J].传感器与微系统,2014,33(11):117-120.

猜你喜欢
网络覆盖覆盖率节点
民政部等16部门:到2025年村级综合服务设施覆盖率超80%
CM节点控制在船舶上的应用
我国全面实施种业振兴行动 农作物良种覆盖率超过96%
基于AutoCAD的门窗节点图快速构建
概念格的一种并行构造算法
TD-LTE网络覆盖质量评估浅谈
结合同频载干比综合评价GSM-R网络覆盖质量方案研究
浅析并线区段的GSM-R网络覆盖调整
基于喷丸随机模型的表面覆盖率计算方法
TD-LTE网络覆盖的分析方法研究