無線感測網路中行動感測器派遣演算法

Abstract

在一混合式之無線感測網路中，固定式感測器負責偵測事件的發生， 而行動感測器可以移動至事件發生點以便作進一步分析。行動感測器最耗能的操作即為移動，如何減少感測器之移動距離同時能讓其完成任務為一富有挑戰性之研究題目。若某些特定行動感測器一直被指派到不同的地點，他們的能量很快就會耗盡，並造成殘存感測器之工作負擔變大。在平衡各感測器之工作負擔的前提之下，本論文提出一有效派遣行動感測器之演算法，並且適用於任意數量之可動式感測器以及事件發生點。行動感測器的數量大於事件發生點時，本論文將其轉化為一最大配對數之配對問題(maximum matching problem)，而在事件發生點大於感測器的數量時，我們將事件先叢集化，並將行動感測器分配到各叢集完成任務。為了減少感測器之間的訊息傳輸量，本論文提出一分散式演算法。模擬實驗結果證明本論文所提出之演算法能夠有效的延長行動感測器之系統生命週期(system lifetime)。

A hybrid sensor network consists of both static and mobile sensors, where the former is used to detect events while the latter can move to event locations for conducting more advanced analysis. By exploring the load balance of mobile sensors, we propose an algorithm CentralSD to efficiently dispatch mobile sensors. Our algorithm is general in which the numbers of mobile sensors and events are arbitrary. When the number of events is no larger than that of mobile sensors, we transform the dispatch problem to a maximum matching problem in a weighted bipartite graph. When there are only few mobile sensors to be dispatched to a large number of event locations, we propose an efficient clustering scheme to group event locations so that the maximum matching approach can be applied. To reduce messages incurred, we also develop a distributed algorithm GridSD. Extensive simulation results are presented to verify the effectiveness of our proposed algorithms.