以搜尋演算法為根基之無線感測網路佈建策略

Abstract

無線感測網路已充份應用在即時環境或人類行為之感測。然而，在 這個領域中網路的佈建問題仍然是設計上的主要考量之一。本論文 探討如何以最少的無線感測節點來達成無線感測網路之佈建要 求。比較其它相關的研究，我們考量三維空間中具障礙物之環境， 並同時考量在通訊與感測上具非規則訊號場型之無線感測節點。我 們的目標在基於退火搜尋方法上提出有效率的佈建演算法與改良 策略。其中，一個新的三維空間中的環境結構表示方法也在本文中 提出。本論文以實際環境做為實驗參數來驗證我們的演算法與改進 策略效能。藉由實際結果與模擬結果之雙重驗證下，其結果顯示我 們所提出的演算法與佈建策略顯著地提升了佈建的效率與精確性。

Wireless sensor networks has been widely considered as an effective way in civil and military domains. One of the main design issues is the sensor placement problem. In this paper, we target issues in the deployment of wireless sensors with an objective in the minimization of the number of adopted sensor nodes. Distinct from many previous results, we consider a three-dimensional space model with obstacles and irregular radiation patterns for both message communicating and sensing. Our goal is to develop a more effective way in executing search-oriented strategies to deploy sensor nodes, namely simulated annealing. We propose a data structure to represent a three-dimensional space to facilitate searching and develop several techniques to improve the performance of search algorithms. The capability of the proposed approach is demonstrated by real case studies in the deployment of sensor networks in several office flats.