無線感測器網路覆蓋率最佳化之研究

Abstract

無線感測器網路(WSNs)是同時由許多具有計算、通訊與感測能力的裝置(或稱為無線感測器節點)所組成。因為無線感測器節點的能量有限(通常搭載電池)，各式各樣的能量效率研究大量出現。在這些研究中，無線感測器網路的能量效率覆蓋率問題在近幾年引起許多關注。該問題主要研究如何維持全覆蓋率(或高覆蓋率)，並同時延長網路壽命(lifetime)。一般為了使感測器網路能夠覆蓋所有的監測關注點 (point of interest, POI)，可能的方法是將感測器節點隨機佈署在關注點附近，抑或利用直升機大量丟撒節點於監測關注點附近。有鑑於此，設計一個有效率且明智的感測節點管理機制，以確保網路可達成長時間的全覆蓋率監測，有其必要性。 為了滿足上述的需求，本研究在第二章提出一套集中式的覆蓋率控制演算法，其利用瀰集進化演算法(Memetic algorithm, MA)找出冗餘的感測節點並將之關閉(睡眠狀態)以減少能量耗損，而剩餘的必要節點將維持運作並達成全覆蓋率。在系統運作後，節點的能量將隨著時間的增加而耗盡，導致覆蓋率的損失。為了有效恢復覆蓋率，所提之覆蓋率控制演算法將喚醒部分睡眠中的節點，以不足覆蓋率中的損失。第三章提出一混合式覆蓋率最佳化控制架構，該架構利用MA將感測器網路節點組織成數組互斥集合(disjoint sets)，每個集合內的節點皆能夠完整覆蓋所有POI。MA可將互斥集合數最大化，透過依序啟動這些所屬不同集合的節點群，有效維持網路的全覆蓋率。當啟動的節點無法維持全覆蓋率時，將利用一啟發式遞迴演算法快速喚醒睡眠中的節點。若仍無法恢復全覆蓋率，則啟動下一個互斥集合內的節點，同時關閉原本已在運作的節點群，以確保網路的全覆蓋率和網路壽命的延長。 所有上述的演算法皆透過完整的電腦模擬與實際測試來進行效能評估，實驗結果顯示本文所提的方法在效能上皆優於過去的方法，且具有實際應用之價值。

Wireless sensor networks are formed by numerous sensor nodes comprising processors, communication interfaces and sensors. Due to the limited energy for the sensor nodes, a variety of energy-efficient issues of WSNs have raised in studies. Among these issues, the energy-efficient coverage issue in wireless sensor networks (WSNs) has drawn much attention in recent years. The focus of the energy-efficient coverage issue is how to sustain a full coverage and a longer network lifetime. In order to cover a set of points of interest (POIs) with known locations in a remote sensing field (i.e., achievement of full coverage), generally, the possible solution is to deploy sensor nodes remotely from an aircraft or deploy some nodes nearby the POIs in a non-deterministic manner. In the case of node deployment, therefore, it is critical to implement judicious management for these sensor nodes deployed randomly with energy efficiency designs. Hence, the long-term full coverage surveillance can be ensured. In order to meet such the energy-efficient coverage requirements described above, in Chapter 2, a coverage control using memetic algorithm (CoCMA) to find the redundant sensor nodes and inactivate them (in a sleeping mode) for a deployed WSN is presented. Only fewer necessary nodes remain inactive to cooperate to monitor whole POIs. Afterwards, the lack of coverage could be compensated, since some of the sleeping nodes would be awaked by a sink node performing a Wake-Up scheme. In Chapter 3, a hybrid framework for coverage optimization (HyFCO) to tackle the energy-efficient coverage issue is presented. First, the HyFCO allows disjoint sets with a maximal size. Every disjoint set is composed of some of sensor nodes which cooperate to cover all POIs. The HyFCO activates the disjoint set successively, and thus the energy-efficient full coverage requirement can be met. Once coverage holes which are caused by energy depletion of sensor nodes in a disjoint set are found, the HyFCO would utilize a heuristic recursive algorithm (HRA) to rapidly repair the lost coverage. Both the presented CoCMA and HyFCO are evaluated via computer simulations and/or real-world tests. The experimental results show that the proposed algorithms outperform existing approaches.