適用於無線感測網路之節能路由與中繼感測器安置演算法

Abstract

無線感測網路 (wireless sensor networks, WSNs) 是由許多散佈於各地的感測節點 (sensor nodes) 所組成，主要用以蒐集各種環境資料，例如溼度、壓力、溫度等。 節能路由與中繼感測器安置是無線感測網路重要的研究議題，在本論文中我們提出數種適用於無線感測網路之節能路由與中繼感測器安置演算法 (relay sensors placing algorithm)，其中包括兩種節能叢集路由演算法 (energy-aware cluster-based routing algorithms), 兩種訊息渡輪路由演算法 (message ferry routing algorithms), 及一種中繼感測器安置演算法。 在節能路由 (energy-aware routing) 議題中, 叢集路由演算法 (cluster-based routing algorithm), 具有增加擴展性與有效性之優點, 如何以叢集路由演算法來最大化無線感測網路之生命週期 (lifetime) 亦是一個重要的研究議題。 針對節能路由議題，我們提出兩種適用於無線感測網路的節能叢集路由演算法 (cluster-based routing algorithm), 稱為 ECRA 及 ECR-2T。ECRA 及 ECRA-2T 之效能優於其他演算法。 這是因為 ECRA 及 ECRA-2T 旋轉叢集頭 (intra-cluster-heads)以平衡每個感測器的負荷量。 ECRA-2T 具有縮短傳輸距離的優點。 有關訊息渡輪路由 (message ferry routing) 議題, 在特殊環境裡, 例如戰場、疫區、廣域監視區等, 大多數路由演算法無法將接收到的訊息傳送至目的地。 因此, 如何在分離的無線感測網路 (partitioned wireless sensor networks) 中收集資料, 是一個重要的研究議題。 針對訊息渡輪路由議題，我們提出兩種適用於有容量限制(buffer-limited) 的無線感測網路的路由演算法, 稱為 MFRA1 及MFRA2。MFRA1 及 MFRA2 將原拜訪路徑 (initial visit sequence) 分割成一些次路徑 (sub-sequences), 在一個完整的拜訪順序中 (a complete sequence), 過載感測器 (overflow sensor) 會被message ferry 拜訪兩次, 因此能繼續正常運作。 MFRA1 及MFRA2 在資料遺失量 (the amount of data loss) 之效能優於其他演算法。 因為其他方法忽略了感 應器的過載 (overflow) 問題。 在中繼感測器安置 (relay sensors placing) 議題中, 隨機部署的無線感測網路中, 存在通訊缺口(communication gaps), 如何以 最少的中繼感測器來保持網路連通, 是一個重要的研究議題。 針對中繼感測器安置 (relay sensors placing) 議題，我們提出一種適用於無線感測網路的中繼感測器安置演算法, 稱為 ERSPA。 ERSPA 在平均中繼感測器數量的效能優於Minimum Spanning Tree 演算法及 Greedy 演算法。 Minimum Spanning Tree 演算法 所需的平均中繼感測器數量約為 ERSPA 的兩倍。 這是因為 ERSPA 將中繼感測器安置在最佳位置以連通整個感測網路。

In WSNs, there are spatially distributed sensors which cooperatively monitor environmental conditions, such as humidity, pressure, temperature, motion, or vibration, at different locations. Energy-aware routing, message ferry routing andrelay placing problems are important research issues in wireless sensor networks. In this dissertation, we design several efficient algorithms in wireless sensor networks, including two kinds of energy-aware cluster-based routing algorithms, two kinds of message ferry routing algorithms, and a relay placing algorithm. In energy-aware routing problem, cluster-based routing protocols have special advantages that help enhance both scalability and efficiency of the routing protocol. Likewise, finding the best way to arrange clustering so as to maximize the network's lifetime is now an important research topic in the field of wireless sensor networks. For energy-aware routing problem, we propose an energy-aware cluster-based routing algorithm (ECRA) for wireless sensor networks to maximize the network's lifetime. The ECRA selects some nodes as cluster-heads to construct Voronoi diagram and rotates the cluster-head to balance the load in each cluster. A two-tier architecture (ECRA-2T) is also proposed to enhance the performance of the ECRA. The simulations show that both the ECRA-2T and ECRA algorithms outperform other routing schemes such as direct communication, static clustering and LEACH. This strong performance stems from the fact that the ECRA and ECRA-2T rotate intra-cluster-heads to balance the load to all nodes in the sensor networks. The ECRA-2T also leverages the benefits of short transmission distances for most cluster-heads in the lower tier. In message ferry routing problem, some particular environments such as battlefield, disaster recovery and wide area surveillance, most existing routing algorithms will fail to deliver messages to their destinations. Thus, it is an important research issue of how to deliver data in disconnected wireless sensor networks. For message ferry routing problem, we propose two efficient message ferry routing algorithms in partitioned and buffer-limited wireless sensor networks, denoted as MFRA1 and MFRA2. MFRA1 and MFRA2 fix the overflow by partitioning the initial visit sequence into some sub-sequences such that the ferry visits the overflow node twice in the resulting sequence. The above process will continue until a feasible solution is found. Simulation results show that both MFRA1 and MFRA2 are better than other schemes in terms of the amount of data loss, because the other schemes neglect the case of sensor overflow. In relay placing problem, randomly deployed sensor networks often make initial communication gaps inside the deployed area, even in an extremely high density network. How to add relay sensors such that the underlying graph is connected and the number of relay sensors added is minimized is an important problem in wireless sensor networks. For relay placing problem, we propose an efficient relay sensors placing algorithm (ERSPA) for disconnected wireless sensor networks. Compared with the minimum spanning tree algorithm and the greedy algorithm, ERSPA achieves better performance in terms of the number of relay sensors added. Simulation results show that the average number of relay sensors added by the minimal spanning tree algorithm is approximately two times that of the ERSPA algorithm. This is because ERSPA places the relay sensors in optimal places to connect the maximum number of initial connected sub-graphs such that the average number of relaysensors can be minimized.