無線感測器自動化網路佈署協定設計與實作

Abstract

近年來無線感測網路的技術蓬勃發展，其應用也推陳出新，事實上，對於無線感測網路而言，如何提供有效的感測覆蓋率是決定網路運作效率的重要因素。在這份三年的計畫中，我們致力於設計居家智慧型無線感測網路，我們在感測器上配置行動裝置使其具有行動能力，並針對居家環境設計一自動化感知傳測器佈署協定(Coverage-Aware Sensor Automation protocol，以下簡稱CASA)，實現此居家型高智慧網路，藉由動態感測器的自動佈署，以提供使用者所需的感測覆蓋率。此外，有別於其他先前的研究，我們所設計的CASA協定允許網路中同時使用齊性或非齊性感測器，也就是說，CASA協定亦適用於感測範圍(sensing range)不同的感測器，在使用上具有較大的彈性。事實上，CASA協定主要由EVFA-B、CFPP、SSOA這三個機制構成。EVFA-B會針對我們設計的距離門檻值 使感測器彼此之間運作引力或斥力，其合力結果會將感測器逐漸推向合適的位置，以強化網路中的感測覆蓋率。為了達到高品質的感測覆蓋率，我們研究出EVFA-B中所使用的環境參數與網路拓墣有相當大的關係，例如:監控面積大小與網路中的感測器數量，我們期望EVFA-B能提供有效的自動化佈署。此外，我們發現當感測器重新佈署時，在移動的過程中可能會有碰撞問題發生，因此我們規劃CFPP演算法，針對每一台感測器的移動路徑，事先偵測潛在的碰撞發生地點，並重新調整感測器的移動時程，藉此避免碰撞發生。除此之外，當網路中有某些感測器發生故障或電力不足的情形，我們設計SSOA演算法進行局部的修復行動，也就是說，當有感測破洞發生(sensing void)時，SSOA會選擇此破洞周圍某些合適的感測器去修補它，而不是使用EVFA-B重新佈署整個網路，藉此有效節省電力消耗。除此之外，我們發現如何選擇合適的救援感測器，事實上屬於Maximum-Weight Clique Problem(以下簡稱MWCP)，此問題被公認為NP-hard，我們將MWCP簡化(reduce)為選擇救援感測器的問題，發現我們的weight值可能有正有負，然而目前能解決MWCP的演算法只考慮weight值恆正的情況。因此，最終我們定義救援感測器選擇的問題時，只考慮weight值恆正的情況，如此一來才存在有效率的polynomial-time演算法，而weight值為負的情況就使用EVFA-B代為解決，藉由此合作機制，CASA協定可以達到有效率的覆蓋率要求。在真實的環境中使用嵌入式系統運行CASA協定，藉此設計一個可以容許感測器故障，藉由自動化佈署以延長網路使用壽命的居家智慧型監控網路(MoNet)。此外我們會藉由觀察覆蓋率達成率、網路自我修復能力、移動所耗費的電力，並實地模擬當緊急災害的發生時，MoNet的事件回報率，藉此估測CASA協定的效率。