無線感測網路的缺洞偵測及修補新策略

Abstract

在無線感測網路中，缺洞偵測及修補對於維持穩定的覆蓋區域是很重要的問題。由於感測器的電源耗盡或是感測器的損壞，可能會產生一些缺洞在我們感興趣的區域(簡記為RoI)。因此，缺洞偵測和修補是相當重要的。針對缺洞偵測，Kang 等人在文獻[3] 中提出了一個分散式、不用座標、以點為基礎的演算法，利用邊界關鍵點來找出缺洞。在本篇論文中，我們首先採用Kang 等人的作法，用邊界關鍵點來找出缺洞。接著，我們設法降低缺洞的邊數，其目的在使得缺洞修補所需的感測器數量能夠下降；我們降低缺洞邊數的方法是：用邊界關鍵點所對應的感測器圓盤之圓心來取代原本的邊界關鍵點，並移除多餘的圓心。對於缺洞的修補，Shiu 等人在文獻[9] 提出了一個分治法(divide-and-conquer) 的方法先將缺洞切割成一些三角形，再修補每個三角形。在本篇論文中，我們提出了一個動態規劃(dynamic programming) 的演算法找出最短的切割線長度來將缺洞切成一些三角形。本篇論文最重要的貢獻是：我們發現，D 若越小，則T 越小；其中D 為將缺洞切割成三角形的切割線總長度，T 為用來修補缺洞的感測器總數量。相較於文獻[3]，我們的缺洞修補演算法保證沒有殘餘的缺洞，也就是 說，RoI 是完全覆蓋的；相較於文獻[9]，我們的缺洞修補演算法所使用的T 通常較小。

In wireless sensor networks (WSNs), hole detection and hole healing are two important problems in maintaining a stable coverage. Coverage holes may arise in a Region of Interests (RoI) due to the running out of batteries of sensors or due to the damage of sensors. Hence, the development of means to detect and to heal the coverage holes is of great significance. For hole detection, Kang et al. [3] provided a decentralized, coordinate-free, node-based coverage hole detection algorithm which maps out the coverage holes by connecting the identified boundary critical points. In this thesis, we first adopt the approach of [3] to map out the boundary critical points. Then, we try to reduce the number of edges of coverage holes; the purpose is to reduce the total number of healing sensors. Our approach to reduce the number of edges of coverage holes is: we replace each boundary critical point with the center of the corresponding sensing circle, and remove redundant centers. For hole healing, Shiu et al. [9] used a divide-and-conquer deployment algorithm based on partitioning the hole into triangles and then, healing each triangle. In this thesis, we propose a dynamic programming approach to minimize the total length of diagonals used in partitioning the hole into triangles. The most important contribution of this thesis is that we find that T can be minimized if D is minimized; where T is the total number of healing sensors and D is the total length of diagonals used to partition coverage holes into triangles. Compared to [3], our hole-healing algorithm guarantees that there is no remaining hole, i.e., the RoI is fully covered. Compared to [9], our hole healing algorithm usually has a smaller T .