智慧型環境之全域感測器佈署及局部覆蓋率修復網路協定設計

Abstract

在本論文中，我們著重於設計智慧型環境無線感測網路，並在異質性感測器(具有不同的感測範圍) 上裝備行動裝置使其具有行動能力，藉此協助感測器的自動化佈署。我們設計一自動化感測器佈署協定(Coverage-Aware Sensor Automation protocol，以下簡稱CASA)，以實現自動化智慧監控網路。CASA 協定主要是由EVFA-B、SSOA兩個機制所構成。有別於其它先前的研究只探討部分佈署問題，我們針對全域佈署(EVFA-B) 和局部修復(SSOA) 的問題提出完整的研究。EVFA-B 透過我們設計的距離門檻值dth 使感測器彼此之間產生相應的引力或斥力，其合力結果會將感測器逐漸引導至合適的位置，以強化網路中的感測覆蓋率。為了達到高品質的感測覆蓋率，我們研究出不錯的相關權重參數與環境參數有密切的關係，例如: 監控面積大小與網路中的感測器數量，並驗證了EVFA-B 能夠有效的自動化佈署。此外，當網路中有某些感測器發生故障或電力不足的情形時，我們設計的SSOA 演算法會選擇感測破洞周圍某些合適的感測器去進行局部修復，而不是使用EVFA-B 重新佈署整個網路，藉此有效節省通訊和移動所造成的電力消耗。我們發現如何選擇合適的救援感測器是屬於Maximum-Weight Clique Problem (以下簡稱MWCP)，此問題被公認為NP-hard，我們將MWCP 轉化(reduce) 為救援感測器的選擇問題。因此，即使感測器發生故障還是能夠維持足夠的感測覆蓋率，藉此有效地延長網路運作時間。此外，我們藉由觀察監控覆蓋率、網路自我修復能力、移動所消耗的電力，以評估我們提出的CASA 協定的使用效能。我們並進一步地在實際的監控網路(MoNet) 中實現CASA 協定，藉此證實CASA協定的可行性。

In this thesis, we focus on smart wireless sensing environments and deal with heterogeneous sensors (having different sensing ranges) equipped with actuation facilities to assist in the sensor self-deployment. A coverage-aware sensor automation (CASA) protocol was previously proposed to realize an automated smart monitoring network. Two centralized algorithms are included in the CASA protocol suite: EVFA-B and SSOA. Unlike most previous works that tackle the deployment problem only partially, we intended to address the problem from both global deployment (EVFA-B) and local repairing (SSOA) perspectives. The enhanced virtual forces algorithm with boundary forces (EVFA-B) exerts weighted attractive and repulsive forces on each sensor based on predefined distance thresholds. Resultant forces then guide the sensors to their suitable positions with the objective of enhancing the sensing coverage (after a possibly random placement of sensors). To achieve high coverage ratio, we inferred that good choices for the associated weight constants greatly depend on sensor population and monitored area size, while independent of sensing radius. Furthermore, in the presence of sensor power depletions and/or unexpected failures, our sensor self-organizing algorithm (SSOA) is activated to perform local repair by repositioning sensors around the sensing void (uncovered area). This capability of local recovery is advantageous in terms of saving the communication and moving energies. Selection of local rescue sensors with mixed negative and positive weights is NP-hard, and can be reduced from the maximum-weight clique problem. As a result, adequate sensing coverage can be maintained even in the face of sensor node failures, effectively extending network functioning time. Performance of the proposed sensor deployment strategies is evaluated in terms of surveillance coverage, network self-healing competence and moving energy consumption. We further implemented our CASA protocol suite in a real-life monitoring network (MoNet) to demonstrate the protocol feasibility.