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

卢 玲，谢佳华

(武警工程大学 信息工程系，陕西 西安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.