WSN 中节点布置优化的一种改进PSO 算法

摘要：覆盖是无线传感器网络中的一个关键问题，它决定了网络监测及追踪目标的准确性。该文介绍了覆盖的一个关键指标即盲区a。尽管在无线传感器网络中，全覆盖是可以实现的，但与此同时，付出的成本也是昂贵的。因此，该文将该问题公式化，在满足盲区比例的情况下，求得最低的成本。该文旨在使用一组最优传感器在成本最低的情况下使覆盖区域1-a最大。该文采用改进的PSO完成目标的优化。实验结果表明网络中传感器的数目及冗余量减少，同时传感器布置的效率提升。

关键词：WSN；覆盖；PSO

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）30-6724-03

现今，无线传感器网络（WSN）因为其自身的优异自适应能力、灵活性、自组织能力广泛应用于学术及工程领域。近几年WSN【6-7】吸引了许多学术者的目光。

传感器覆盖是WSN中一个基本的问题。它反映了如何更好地进行环境的监测，成为物理现象、目标探测分类及目标追踪此类应用的基础。由于传感器网络应用的多样性，传感覆盖的定义也有众多的解释。然而只有各向同性的传感器在学术领域被广泛研究。例如，许多研究区域或点的问题的研究【8-11】中传感器的感知能力被抽象成一个圆形区域（或圆盘），此时事件或目标是否能被探测到取决于它是否发生或处于这个圆形区域内。

传感器节点的部署是无线传感器网络的关键问题。一个传感器网络的部署可以有两种方式，一种是随机布置，另一种是有计划地放置【1】。当环境未知、危险的情况下，不可手动布置传感器，可能依靠飞机等工具将传感器节点随机放置在目标监测区域。相反，如果目标监测区域清晰明了，则可通过详细的计划部署传感器节点以达到一点的目标要求。

粒子群算法（PSO）是J.Kennedy与R.Eberhat在1995年提出的。该算法模仿鸟类捕食行为优化相关问题。在算法中，鸟的位置被随机初始化于解空间中，一只鸟被称为一个粒子，这些粒子按照一个规则在在解空间内移动，在经过几次迭代之后即可得到最优的解。粒子群算法保留了全局搜索策略，采用简单的速度位移模型，避免了复杂的遗传操作。同时，粒子群算法具有全局收敛能力强的优点，它可以动态跟踪当前的搜索情况以其特定的记忆能力不断调整自身的移动策略。在实际应用中，粒子群算法是非常适合复杂的优化问题。

1 相关工作

最近覆盖问题已受到广泛关注。许多研究者重点关注地是区域覆盖问题，考虑如何部署传感器覆盖以完全覆盖监测区域[2]，如何选择移动传感器来覆盖目标区域。[2]提出了一个最优覆盖多项式时间求解算法，其结合了结合计算几何和图论理论，特别是Voronoi图和图搜索算法。

对于目标区域的覆盖，基于位置的网络方法是最受欢迎的。[5]开发了一种算法来部署一种高效节能的无线传感器网线，降低成本并且延长网络的生存时间同时保证覆盖的质量。问题被看成是0/1整数规划问题，这是很难计算的。

移动传感器节点是用来覆盖监测区域以完成全覆盖的目标。如何选择最佳位置和最佳路径已成为大多数人关注的话题。[4]利用粒子群算法优化移动传感器的路径。不过在实际应用中，移动传感器的价格比较昂贵，并且在移动过程中会消耗大量能量。

有些优化算法在解决传感器布置问题上也很受关注，[13]使用了遗传算法优化传感器的最优位置。但是它需要更多的传感器节点，存在冗余现象。

本文的目的在于优化WSN的覆盖率，使得覆盖率达到1-a。a是目标区域内空白区域即未被覆盖区域占目标监测区域的比例。参数θ是一个很小的正数，设定它的值小于0.1。

2 改进的粒子群算法优化传感器部署

B.无线传感器网络覆盖模型

无线传感器网络由大量具有感知与通信能力的传感器节点组成。传感器布置的优化策略通过有效计算传感器节点的位置，可以扩展覆盖区域、改善通信性能。传感器节点的感知与通信范围是相同的，同时将每个传感器的覆盖模型表述了一个具有圆心和半径的圆。假设Sj放置于位置（xj，yj），目标监控点位于（x，y），则Sj与X之间的距离为[（xj-x）2+（yj-y）2]。

假设给定一个目标区域A，A可以被划分为mxn块子区域，如果子区域之间的距离小于感知半径，一个子区域则会被多个传感器覆盖。

4 结论

本文采用了改进这的PSO算法优化传感器覆盖问题，目的在于找到一组最优的传感器组合覆盖目标监

测区域，以使其满足最少的节点完成目标监测区域的覆盖。同时在本文中也考虑了传感器联通的问题。实验结果表明改进的PSO算法具有良好的收敛性，且能用较少的节点达到网络覆盖率的要求。

未来，PSO算法可用于异构传感器网络中，即选择不同类型的传感器节点覆盖目标监测区域。它可以在降低成本的同时也保证了网络的覆盖率及联通性需求。另外PSO算法也可以用于优化移动节点的移动路径以满足网络中的通信需求。

参考文献：

[1] I. F.Akyildiz， W. Su， Y. Sankarasubramaniam， and E. Cayirci，”Wireless Sensor Networks： a Survey，” Elsevier Journal of Computer Networks， vol.38， pp . 393-422， March 2002.

[2] S. Meguerdichian， F. Koushanfar， M. Potkonjak， and M. B. Srivastava，”Coverage Problems in Wireless Ad-hoc Sensor Networks”， in Proc. 7th Annual ACM/IEEE International Conference on Mobile Computing and Networ king， July 2001， pp.139-150.

[3] W.Jiao， G.B.Liu，K.Wang ，”Improved PSO Algorithm Based on Diversity of Particle Swarm” ，Journal of System Simulation，2009.

[4] X.Xue，S.WANG，J.J.Ma，”Parallel Particle Swarm Optimization Based Mobile Sensor Node Deployment in Wireless Sensor Networks”，CHINESE JOURNAL OF COMPUTERS， 2007.

[5] Frank ，Y.S.Lin， P.L.Chiu.”Energy-Efficient Sensor Network Design Subject to Complete Coverage and Discrimination Constraints”.

[6] G.J. Pottie， W.J. Kaiser，” Wireless sensor networks”， Communications of the ACM 43 （5） （2000）， pp 51-58.

[7] P. Santi， “Topology Control in Wireless Ad Hoc and Sensor Networks”， John Wiley and Sons， 2005.

[8] S. Slijepcevic， M.Potkonjak， “Power， efficient organization of wireless sensor networks”， in IEEE International Conference on Communications （ICC 2001）， Helsinki， Finland， Vol.2， pp. 472–476.

[9] D. Tian， N.D. Georganas ，” A coverage-preserving node scheduling scheme for large wireless sensor networks”， in Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications （WSNA2002）， Atlanta， GA， United States， pp. 32–41 .

[10] X.Wang， G.Xing， Y.Zhang， C.Lu， R.Pless， and C.Gill， “Integrated V2-502011 3rd International Conference on Computer and Network Technology （ICCNT 2011）coverage and connectivity configuration in wireless sensor networks”， in Proceedings of the First International Conference on Embedded Networked Sensor Systems （Se nSys2003）， Los Angeles， CA， United States， pp.28–39 .

[11] H.Zhang， J.C.Hou，”Maintaining sensing coverage and connectivity in large sensor networks”， TheWireless Ad Hoc and Sensor Networks： An International Journal，2005.