在無線感測網路中的覆蓋及連結問題

Abstract

無線感測網路的新興技術，將使得我們的生活更加便利，它的環境之中包含了許多便宜的無線感測器，每一個感測器都具有收集、儲存、以及處理環境資訊的能力，此外，感測器和感測器之間還能透過無線的方式互相通訊。要使得一個感測網路可以成功的運行，感測器必須要能夠同時保持感測的覆蓋程度、網路的連結性、以及長時間運行的能力。在本論文之中，我們首先探討在二維及三維空間之中的覆蓋問題，接著，我們研究在一個感測網路中，感測的覆蓋程度和通訊的連結性之間的關係，然後，為了延長網路的運行時間，我們提出了分散式的能源節省暨覆蓋維持協定。 覆蓋問題是無線感測網路的基礎問題之一，它反應了一個無線感測網路是如何地被感測器所監看或追蹤。在本論文之中，我們把這個問題定義成一個判定問題：給定一個參數k，我們的目標是要去判定，是不是在一個感測網路所服務的區域上的每一位置，都能被最少k個感測器所偵測到。在二維的平面上，每一個感測器的感測範圍可以是相同或不同半徑的圓形，而在三維的立體空間之中，我們將感測器的感測區域假設成圓球(不必是相同的半徑)，我們首先提出這個問題在二維空間之中多項式時間的演算法，接著，我們更進一步的証明這個問題在三維空間之中，也可以在多項式的時間之內解答，而我們所提出來的解法，都可以很容易地轉換成分散式的協定。 要讓一個感測網路可以順利的運行，感測器必須要能夠同時兼顧感測的覆蓋程度以及網路的連結性，這個問題己經在[35, 43]之中被探討，這兩篇文獻都提出了一個類似的結論，那就是，當通訊的半徑大於等於兩倍的感測半徑時，覆蓋的程度可保証網路的連結性。在本論文中，我們從另外一個角度來探討這個問題，並提出了不依賴上面假設的解決方案，這也暗示著，[35, 43]所提出的方法，可以被歸類成我們所提出的方法之中的一個特別情況。 此外，保持足夠的覆蓋程度和達成系統長時間的存活，是在設計網路的拓樸時兩個互相衝突的因素，在本論文中，我們提出分散式的協定來安排感測器工作及休眠時間，可以有效率的提升網路的存活時間，並同時維持被偵測區域足夠的覆蓋，所提出的協定類似[40]所提的模型，然而，我們的方法可以大量的減少計算複雜度，以及平衡感測器之間電能的消耗。

The wireless sensor network is an emerging technology that may greatly facilitate our life. Such environments may have many inexpensive wireless nodes, each capable of collecting, storing, and processing environmental information, and communicating with neighboring nodes. For a sensor network to operate successfully, sensors must maintain sensing coverage, network connectivity, and long lifetime. In this dissertation, we first study the coverage problems both in 2D and 3D spaces. Next, we investigate the relationship between sensing coverage and communication connectivity of a sensor network. Then, decentralized energy-conserving and coverage-preserving protocols are proposed to prolong the network lifetime. 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 dissertation, 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 k sensors, where k is a given parameter. The sensing ranges of sensors in a 2D space can be unit disks or non-unit disks while in a 3D space the sensing regions of sensors are modeled by balls (not necessarily of the same radius). We first present polynomial-time algorithms, in terms of the number of sensors, to solve this problem in a 2D space. Next, we show that tackling this problem in a 3D space is still feasible within polynomial time. The proposed solutions can be easily translated into efficient polynomial-time distributed protocols. For a sensor network to operate successfully, sensors must maintain both sensing coverage and network connectivity. This issue has been studied in [35, 43], both of which reach a similar conclusion that coverage can imply connectivity as long as sensors' communication ranges are no less than twice their sensing ranges. In this dissertation, we investigate this issue from a different angle and propose more general decentralized solutions that do not rely on the above assumption. Hence, the results in [35, 43] can be regarded as special cases of what proposed in this dissertation. Besides, to maintain sufficient coverage and to achieve long system lifetime are two contradicting factors in designing the topology of a network. In this dissertation, we propose 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 similar to the model in [40]. However, our approach can significantly reduce the computational complexity incurred, and balance the energy expenditure among sensors.