标题: 确保多角度覆盖移动目标物于方向性感测器网路
Ensuring Multi-Angle Coverage in Directional Sensor Networks with Mobile Targets
作者: 黄虹颖
Huang, Hong-Ying
曾煜棋
Tseng, Yu-Chee
网路工程研究所
关键字: 覆盖问题;方向性感测器;即时性排程;感测器网路;无线通讯;coverage problem;directional sensor;real time scheduling;sensor network;wireless communication
公开日期: 2010
摘要: 在无线网路的环境下,如何确保对于目标物的覆盖是很重要的一项议题,覆盖率直接的反应出对于环境的监控状态。至今为止,已经有许多研究在解决覆盖的问题,
其大致分为空间覆盖问题以及目标物覆盖问题两种。此外,各种问题对于覆盖的定义大不相同,举凡如“单一方向性覆盖”、“角度覆盖”以及“多角度覆盖”等各种问题定义。
早期研究只考虑空间的覆盖率或者是目标物的覆盖率,随着方向性感测器的发展,学者们开始探讨目标物被覆盖的角度,依照覆盖的角度不同有可能会对于目标物产生不同的判断。

因此,在这篇研究中将探讨“多角度覆盖问题”,我们会先解释此类型的覆盖问题以及所遭遇到的困难,再提出两种方法。由于此类问题已被证明为NP-Complete的问题,
首先我们以非线性规划为基础提出一个集中式的方法,但因为非线性规划无法保证可以在多项式的时间内结束,因此我们再进一步提出启发式的方法来解决此问题。
最后,从实验的数据中可以得知,此篇研究所提出的两种方法,皆可提高环境的覆盖率并且符合使用者对于环境的限制。
In a wireless sensor network, ensuring coverage of objects is one of the most fundamental issue, which reflects how a field or targets are monitored by sensors. There are various versions of the coverage problem such as area and target coverage problems. And there are many kind of definitions about cover, for example, single-orientation coverage, angle coverage and k-coverage. In the early studies, they are usually concerned about the cover ratio in a field or weather the object is covered or not. Recently, some researches start to consider about the covered angle of object and the number of coverage. Besides, more and more researches relax the restrict within the directions of sensors. It means, there are more complicated scenario about the coverage problem.

In this paper, we first explain the problems about (k,w)-angle coverage problem. Then we propose two methods to solve this problem. Since this problem is a NP-Complete problem, we first propose a centralized algorithm based on non-linear programming. Although centralized algorithm can approach the optimal solution, it can not guarantee to terminate in polynomial time. Thus, we also propose a distributed scheme based on greedy algorithm. In our simulation results, we have shown that both of our approaches succeeded to enhance the cover rate under the constraints.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079856541
http://hdl.handle.net/11536/48419
显示于类别:Thesis