無線感測網路中繼節點佈建方法之研發-以室內環境為例

Abstract

中繼節點佈建方法乃是用較少量的中繼節點佈建於適當的位置以增進無線感測網路的通訊品質。由於無線感測網路的感測節點廣泛的應用在各個領域，為了讓節點間達成無線通訊的行為，必須在不相連的節點中有效的佈建中繼節點，因此如何有效地佈置中繼節點是個困難且耗費時間的問題。本論文係以二維幾何搜尋演算法為基礎並採用無線電傳播效應之網路拓撲評估模式，提出一種嶄新的無線感測網路中繼節點佈建方法，其特性分別為逐一計算每個候選中繼節點連接至其所有鄰近節點的數量，並根據鄰近節點的連接數，選擇一個擁有最多鄰近節點的候選中繼節點而佈建；以及藉由精確評估鏈結狀態方法來決定網路拓撲型態。模擬的結果指出本研究所提出之佈置中繼節點方法與相關文獻所提之佈建方法相比，本方法大幅降低中繼節點的佈建數量，其中在網路節點密度為 1/250 節點數/平方公尺的條件下，本文所提出之精確評估鏈結狀態方法對中繼節點的佈建數量的改善，降低 30% 的中繼節點之佈建數量；而二維幾何搜尋演算法亦可降低 20% 的中繼節點之佈建數量。

The connectivity of a given static, disconnected wireless sensor network can be improved by deploying additional relay nodes in the network, forming connections between separate clusters of connected nodes. Finding optimal locations to place the relay nodes is a difficult and time-consuming problem. In this research, we propose a heuristic relay node deployment method to provide more efficient relay node deployment comparing to related works. In this method, a two dimension geometric search algorithm is proposed to discover a proper location where adding a single relay node results in connecting as many as possible disconnected node pairs. Besides, in order to devise a practical method, a realistic model for link connectivity estimation and network topology determination is proposed, which takes into account radio propagation effects, including the large-scale path loss, shadow fading, and small-scale fading. Simulation results indicate that the proposed method significantly reduces the number of relay nodes required for repairing disconnected WSNs. There are about 20% of improvements contributed by the proposed two dimension geometric search algorithm, and about 30% of improvements donated by the proposed link connectivity estimation model.