一种无线传感网络的三维K覆盖算法.docVIP

 一种无线传感网络的三维 K 覆盖算法# 方钰，左伟* （同济大学电子与信息工程学院，上海 201804） 5 10 15 20 25 30 35 40 摘要：为了保证无线传感网在三维空间中鲁棒性，本文提出了一种在大规模三维环境中无线 传感网络 k 覆盖控制算法，目标环境可以是一定程度上不规则的空间。对三维空间按一定粒 度以点的形式进行剖分，用迭代的贪婪的启发式方法确定传感器在点分之后的空间中的位 置，每一步迭代完成一个传感器节点的放置，直到所有划分点被 k 覆盖。仿真算例表明，此 算法可以快速、有效的解决大规模、不规则目标区域中的 k 覆盖问题，并与随机策略的算法 相比，达到相同的覆盖目的有着明显的优越性。 关键词：计算机应用技术；无线传感网；三维空间；k 覆盖 中图分类号：TP393 A Three-dimensional K-coverage Algorithm for Wireless Sensor Networks FANG Yu, ZUO Wei (School of Electronics and Information,Tongji University, Shanghai 201804) Abstract: IFor ensuring robustness of wireless sensor networks in three-dimensional space, this paper presents a k-coverage algorithm in large-scale three-dimensional wireless sensor networks and the target environment can be irregular to a certain extent. Firstly, the three-dimensional target environment is divided in the form of points according to a certain granularity. And then, determine the position of sensors in the processed space with the iterative greedy heuristic method. After each iteration, complete the placement of a sensor node until the all granularity points can be k-covered . From the simulation examples we can see that this algorithm can solve large and irregular target area k-coverage problem quickly and efficiently, and compare with the algorithm of random strategy, the former has obvious advantages to achieve the same target. Key words: computer application technoledge; WSN; three-dimensional space; k-coverage; 0 引言 随着无线通信技术，嵌入式计算技术，传感技术，以及微电子技术的发展，无线传感器 网络（Wireless Sensor Network，WSN）随之产生。传感器节点由于其放置方便，移动灵活， 亦能根据相应的算法进行自组织，网络扩展性好等特点，被应用到诸如军事、航空、反恐、 防爆、救灾、保健、家居等各个领域，尤其是在人所不能到达的、恶劣的环境中传感器网络 发挥着独有的作用。 无线传感器网络的覆盖问题描述为：在传感器节点数目一定的情况下，让网络覆盖范围 尽可能的大，或是在覆盖范围一定的情况下达到全覆盖所需的传感器数目尽可能的少。覆盖 的好坏反应了无线传感网的服务质量的好坏，也是无线传感网研究中的基本问题之一。文献 [1] Path 和 Maximal-Support Path，很好的解决了二维平面上的覆盖问题。而为了使目标区域的 覆盖质量尽可能的高，所以我们提出了 K 覆盖问题。所谓 k 覆盖就是目标区域中的任意一 基金项目：国家自然科学基金；高等学校博士学科点专项科研基金资助课题(200802471075) 作者简介：方钰（1977-），女，副教授，主要研究方向为：移动计算、传感器网络与可穿戴计算. E-mail: fangyu@t