無線感測網路中省電並維持覆蓋程度之分散式協定

Abstract

無線感測網路是日前蓬勃發展的技術之一。藉由提供普遍存在的感測、計算以及通訊能力，無線感測網路大大地便利了人類的生活。覆蓋問題是感測網路中十分重要的議題之一，它反映了一個無線感測網路被感測器偵測或追蹤的程度。在這篇論文當中，我們將覆蓋問題視為一個決策問題，它的目標就是在決定是否在此感測網路服務區域內的每個點都被至少□個感測器所覆蓋。在這邊，□是一個給定的參數，且每個感測器的感測區域由不同半徑的球來作為模型。這個問題若只考慮二度空間，在[12]內已有一有效率的演算法來解決。在這篇論文中，我們將證明在三度空間仍然能夠有效率地解決這個問題。此外，我們提出的解法可轉換為一個有效率的分散式協定。我們將提出一個省電的排程協定來驗證我們得到的結果。 就另一方面來說，在設計感測網路拓墣時，維持足夠的覆蓋程度以及延長系統壽命是兩個互相矛盾的因素。在這篇論文當中，我們提出了幾個能夠延長系統壽命的分散式協定。這些協定透過排程感測器的活動與睡眠週期，來達到延長系統壽命的目的，但同時亦能夠維持整個區域足夠的覆蓋程度。這些協定的架構與[32]的架構極為相似，但改進了[32]在許多方面的結果。首先，我們的方法能夠大量地降低需要的計算複雜度，且同時在決定區域覆蓋程度時能夠達到較佳的精確度。再者，我們進一步延伸這個結果來支援某些區域所需要的多層覆蓋。也就是說，我們藉由不時開啟或關閉感測器，使得區域中任何一點在任何時間都能被至少k個感測器所覆蓋，此處k為一整數。最後，我們並提出幾個最佳化的機制，希望能夠平衡或降低感測器的電量消耗，且進一步提升[23]的效能。

The wireless sensor network is an emerging technology that may greatly facilitate human life by providing ubiquitous sensing, computing, and communication capability. One of the fundamental issues in sensor networks is the coverage problem, which reflects how well a sensor network is monitored or tracked by sensors. In this thesis, we formulate this problem as a decision problem, whose goal is to determine whether every point in the service area of the sensor network is covered by at least α sensors, where α is a given parameter and the sensing regions of sensors are modeled by balls (not necessarily of the same radius). This problem in a 2D space is solved in [12] with an efficient polynomial-time algorithm (in terms of the number of sensors). In this thesis, we show that tackling this problem in a 3D space is still feasible within polynomial time. Further, the proposed solution can be easily translated into an efficient polynomial-time distributed protocol. We demonstrate an application of the derived result by proposing an energy-conserving scheduling protocol. On the other hand, to maintain sufficient coverage and to achieve long system lifetime are two contradicting factors in designing the topology of a sensor network. In this thesis, we propose several decentralized protocols that schedule sensors’ active and sleeping periods to prolong the network lifetime while maintain the sensing field sufficiently covered. The proposed protocols are based on a model similar to that of [32], but improve the results of [32] in several senses. First, our approach can significantly reduce the computational complexity incurred, and at the same time achieve better accuracy in determining the coverage of the sensing area. Second, we extend the result to support multi-layer coverage of the sensing field. That is, we allow turning sensors on and off such that any point in the sensing field is always covered by at least k sensors, or so-called k-covered, where k is any integer. Third, we further enhance the results of [32] by proposing several optimization mechanisms to further balance or reduce sensors’ energy expenditure.