確保多角度覆蓋移動目標物於方向性感測器網路

Abstract

在無線網路的環境下，如何確保對於目標物的覆蓋是很重要的一項議題，覆蓋率直接的反應出對於環境的監控狀態。至今為止，已經有許多研究在解決覆蓋的問題， 其大致分為空間覆蓋問題以及目標物覆蓋問題兩種。此外，各種問題對於覆蓋的定義大不相同，舉凡如“單一方向性覆蓋”、“角度覆蓋”以及“多角度覆蓋”等各種問題定義。 早期研究只考慮空間的覆蓋率或者是目標物的覆蓋率，隨著方向性感測器的發展，學者們開始探討目標物被覆蓋的角度，依照覆蓋的角度不同有可能會對於目標物產生不同的判斷。

因此，在這篇研究中將探討“多角度覆蓋問題”，我們會先解釋此類型的覆蓋問題以及所遭遇到的困難，再提出兩種方法。由於此類問題已被證明為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.