標題: 無線感測網路中行動感測器派遣演算法
Energy-Efficient Algorithms for Dispatching Mobile Sensors in a Wireless Sensor Network
作者: 張民憲
Min-Hsien Chang
彭文志
Wen-Chih Peng
資訊科學與工程研究所
關鍵字: 無線感測網路;行動感測器;派遣演算法;節能演算法;wireless sensor network;mobile sensor;dispatching algorithm;energy-efficient algorithm
公開日期: 2005
摘要: 在一混合式之無線感測網路中,固定式感測器負責偵測事件的發生,
而行動感測器可以移動至事件發生點以便作進一步分析。行動感測器最耗能的操作即為移動,如何減少感測器之移動距離同時能讓其完成任務為一富有挑戰性之研究題目。若某些特定行動感測器一直被指派到不同的地點,他們的能量很快就會耗盡,並造成殘存感測器之工作負擔變大。在平衡各感測器之工作負擔的前提之下,本論文提出一有效派遣行動感測器之演算法,並且適用於任意數量之可動式感測器以及事件發生點。行動感測器的數量大於事件發生點時,本論文將其轉化為一最大配對數之配對問題(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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009317537
http://hdl.handle.net/11536/78748
顯示於類別:畢業論文


文件中的檔案:

  1. 753701.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。