| 摘要: | 本論文在多重感測元件之無線異質型感測網路上，同時考慮目標點覆蓋問題與網路連結性問題(Multiple Sensing Units for Target Coverage and Connectivity problem, MU-TCC problem)。為了簡化問題，本論文優先考慮多重感測元件之目標點覆蓋問題(Multiple Sensing Units for Target Coverage problem, MUT problem)，並將此問題轉換成集合涵蓋問題(Set Cover problem)，再以整數線性規劃(ILP)建構出本問題的模型，並據以求出最佳解。然而ILP屬於NP-complete之問題，本論文因而進一步提出分散式演算以貼近無線感測網路之真實運作情況。本論文先針對MUT problem提出剩餘電量優先考量式演算法(Remaining Energy First Scheme for Target Coverage problem, REFS-TC)，REFS-TC將根據感測器本身電量的多寡來決定是否開啟感測元件。為進一步提升感測器間能量消耗的平衡，本論文另外提出能源效率優先考量式演算法(Energy Efficient First Scheme for Target Coverage problem, EEFS-TC)。有別於REFS-TC，EEFS-TC將同時考量本身與鄰居的電量與感測能力，使整個網路的能源消耗更有效率。
根據以上的研究成果，本論文接著討論MU-TCC problem，並將此問題轉換成具連結性的集合涵蓋問題(Connected Set Cover problem)，本論文同樣地以整數線性規劃(ILP)建構出MU-TCC problem的模型並求出最佳解。此外，根據REFS-TC與EEFS-TC設計的精神，分別將REFS-TC與EEFS-TC修改為REFS-TCC與EEFS-TCC來解決MU-TCC problem。REFS-TCC根據感測器本身電量的多寡來決定是否開啟感測元件或是通訊元件以符合感測需求且確保所有的感測資料可以回傳至資料收集器(Sink)。而EEFS-TCC則是根據感測器(Sensor)對網路之感測貢獻與連結貢獻程度來決定是否開啟感測元件或是通訊元件。
就我們所知，本論文是第一篇處理MU-TCC problem的論文。不論是EEFS-TC相對於REFS-TC，或是EEFS-TCC相對於REFS-TCC，由實驗模擬結果顯示EEFS-TC與EEFS-TCC皆更能有效運用無線感測器上的有限電池電量。此外實驗模擬也顯示EEFS-TC或EEFS-TCC相較於ILP運算出的最佳網路存活時間差距不大，而分別相較於REFS-TC或REFS-TCC亦皆更能有效延長網路存活時間。
The thesis considers the target coverage and connectivity problem in wireless heterogeneous sensor networks (WHSNs) with multiple sensing units, named MU-TCC problem. In order to simplify the MU-TCC problem, only the target coverage problem is firstly considered. This kind of target coverage problem can be reduced to a set cover problem and be further formulated as integer linear programming (ILP) constraints. However, solving the ILP problem is an NP-complete problem. Therefore, two heuristic but distributed schemes, REFS-TC and EEFS-TC, are proposed in the thesis to solve this kind of target coverage problem. In REFS-TC (Remaining Energy First Scheme for Target Coverage,) each sensor considers its remaining energy and neighbors’ decisions to enable its sensing units to ensure all targets being covered by the sensing attributes which are required to be covered at each target. The advantages of REFS-TC are its simplicity and less communication overhead incurred. However, in order to make the best use of the sensing units and the communication module on each sensor, another scheme, called EEFS-TC (Energy Efficient First Scheme for Target Coverage,) is proposed as well. Different from REFS-TC, a sensor in EEFS-TC considers its sensing capabilities and remaining energy as well as those of its neighbors to make a better decision to turn on its sensing units and to ensure each target being covered by required attributes.
Based on the discussion above, the connectivity issue is further considered. Similarly, the MU-TCC problem can be reduced to a connected set cover problem and be also formulated as ILP constraints. In addition, REFS-TC and EEFS-TC are also modified as REFS-TCC and EEFS-TCC, respectively. In REFS-TCC (Remaining Energy First Scheme for Target Coverage and Connectivity,) each sensor considers its remaining energy and neighbors'' decisions to schedule its sensing units and the communication module to ensure all targets being covered by all required sensing attributes and sensing data can be delivered to the sink. For EEFS-TCC (Energy Efficient First Scheme for Target Coverage and Connectivity,) a sensor considers the coverage contribution of its sensing units among its neighbors and the connectivity contribution of its communication module to make a better decision to turn on its sensing units and the communication module such that the coverage requirements are preserved and the sink can collect all sensing data.
To our best knowledge, this thesis is the first one to solve the MU-TCC problem for WHSNs with multiple sensing units. Simulation results show that the proposed schemes can prolong the network lifetime effectively. The performances of EEFS-TCC and EEFS-TC are very close to those of ILP solutions, respectively. Furthermore, both EEFS-TCC and EEFS-TC respectively outperform against REFS-TCC and REFS-TC in network lifetime. |
