|Abstract: ||近幾年的網路通訊相關研究中，無線感測網路(Wireless Sensor Networks, WSNs)已成為相當熱門的研究領域。透過大量佈設具有低成本、低耗電、小體積、短距無線通訊等特性的無線感測器(Sensors)所建構的無線感測網路已經被廣泛地應用。感測任務的成功與否與感測區域的覆蓋範圍(Coverage)維護與網路鏈結(Connectivity)狀況息息相關。一個可傳輸感測資料至資料收集器之無線感測器的覆蓋範圍才可被視為是有效的覆蓋範圍。目前的研究較少考慮到在網路維護階段，網路連結性對於有效覆蓋範圍的影響，故本論文將分別討論在區域覆蓋與目標點覆蓋之需求下，如何使無線感測網路以最節省電量的方式完成感測任務，以延長網路存活時間。此外，本論文也分別針對上述覆蓋需求與網路特性，提出解決方案。|
如前所述，無線感測網路會因為Sensors失去功能而使得網路產生分割(Partition)，Partition 將嚴重影響Coverage的情況與Connectivity的品質。因此，本論文首先在使用移動性的感測裝置(Mobile Sensor)的網路中，提出一個有效避免Partition 產生的懶惰移動以避免網路分割之通訊協定(A Partition Avoidance Lazy Movement，PALM)。由於任意的移動會造成Mobile Sensors 快速的消耗本身的電量，因此本論文首先提出一懶惰移動策略(lazy movement policy)。此策略可使Mobile Sensors 判斷網路是否即將產生Partition，進而決定是否需要進行移動。接著，本論文也提出一有效移動原理（principles of an effective movement)。根據此原理，Mobile Sensors 可計算一個可以使有效網路覆蓋區域增加最多，但是所需移動距離最短的位置。PALM 擁有下列特色(1)為分散式的協定；(2)能有效維護網路的Connectivity；(3) Mobile Sensors 移動次數少。
另一方面，本論文接著討論多重感測元件之異質型無線感測網路上的目標點覆蓋問題(Connected Target Coverage Problem)。本論文將無線感測器互相合作以涵蓋感測環境的問題轉換成連結集合涵蓋問題(Connected Set Cover Problem)，再以整數線性規劃(ILP)建構出本問題的模型，並求出最佳解。本論文接著提出剩餘電量優先考量式演算法(Remaining Energy First Scheme, REFS)，REFS 將使感測器以本身電量的多寡來決定是否開啟感測元件與通訊元件。為進一步提升感測器間能量消耗的平衡，本論文另外提出能源效率優先考量式演算法(Energy Efficient First Scheme, EEFS)。有別於REFS，EEFS 將同時考量本身與鄰居的電量、感測能力與通訊能力，使整個網路的能源消耗更有效率。就我們所知，本論文是第一篇解決多重感測元件之異質型無線感測網路上的目標點覆蓋問題的論文。
整體而言，本論文分別針對區域覆蓋需求下之無線感測網路與目標點覆蓋需求下之異質型無線感測網路，分別提出可有效延長網路存活時間的低電量消耗演算法。實驗模擬的結果顯示出PALM 較其他相關文獻所提出之協定更能避免Partition 的產生，使所有能夠工作的Mobile Sensors 可以貢獻他們的能力，以增加無線感測網路的存活時間。另外，針對異質型無線感測網路上的目標點覆蓋問題，實驗模擬顯示，EEFS 比REFS 更能延長網路存活時間，且與ILP 運算出的最佳網路存活時間相近。
A wireless sensor network (WSN) consists of numbers of sensors deployed in a sensing field in an ad hoc or prearranged fashion for the purposes of sensing, monitoring, or tracking environmental events. Unlike ad hoc networks, a WSN is application-specific, data-centric, and energy-constrained in essence. With the limitation in battery energy, all sensors have to cooperatively work to cover the sensing field of the interest. Thus, to develop efficient schemes beneficial to coverage but less energy waste is very important in WSNs. Basically, the coverage preserving protocols nowadays are proposed for area or target coverage. The impacts of the network connectivity on coverage preserving are not carefully considered. Clearly, even though one scheme can obtain maximal sensing coverage, without ensuring the connectivity of sensors to the sink, it is also useless. Therefore, in this dissertation, the coverage preserving issues for area and target coverage in more complicated network condition are discussed.
Recently, mobile sensors have been widely used in a variety of applications in WSNs to achieve the requirement of network coverage. Based on the mobile capability of the sensor, the dissertation proposes a distributed partition avoidance lazy movement (PALM) protocol for mobile sensor networks (MSNs). As mentioned above, connectivity and coverage are two major factors to the success of a sensor network. Therefore, PALM takes both connectivity and coverage into account to avoid network partition and keep high sensing quality. Since sensor movement is the major source of energy consumption, thus, in order not to cause frequent movement, PALM triggers sensor movement only when the network has a risk of partition, but not when coverage holes appear. The dissertation proposes a sufficient condition of keeping a network connected. Based on the condition, PALM adopts the lazy movement policy for a sensor to determine when to move and uses the principles of an effective movement for a sensor to decide where to move. Accordingly, PALM can keep the network connected and can make the effective coverage as large as possible to maintain high sensing quality.
On the other hand, the connected target coverage (CTC) problem in wireless heterogeneous sensor networks (WHSNs) with multiple sensing units, termed MU-CTC problem is considered in the dissertation. MU-CTC problem is firstly reduced to a connected set cover problem and further formulated as integer linear programming (ILP) constraints. However, the ILP problem is an NP-complete problem. Therefore, two heuristic but distributed schemes, REFS (Remaining Energy First Scheme) and EEFS (Energy Efficient First Scheme,) are proposed. In REFS, each sensor considers its remaining energy and neighbors'' decisions to enable its sensing units and communication unit such that all targets can be covered by required attributes, and the sensed data can be delivered to the sink. The advantages of REFS are its simplicity and less communication overhead incurred. However, to utilize sensors'' energy efficiently, EEFS is proposed as well. A sensor in EEFS considers its contribution to the coverage and the connectivity to make a better decision. To our best knowledge, this dissertation is the first one to consider target coverage and connectivity jointly for WHSNs with multiple sensing units.
In general, the issues mentioned above are actually essential and important in both area and target coverage. Overall, the protocols to avoid network partition and to schedule sensor’s activity are respectively proposed for the mobile sensor network and the heterogeneous stationary sensor network with multiple sensing units. In comparison with the related work, PALM can reduce the energy consumption and further extend the network lifetime in mobile sensor network due to the lazy movement policy and the principles of an effective movement. Simulation results verify the advantages of the proposed protocol. For the MU-CTC problem, simulation results show that REFS and EEFS can prolong the network lifetime effectively. Furthermore, EEFS outperforms against REFS in network lifetime.