系統識別號 | U0002-0208200714240700 |
---|---|
DOI | 10.6846/TKU.2007.00076 |
論文名稱(中文) | 具多重感測元件之無線感測網路上的目標點覆蓋與連結整合研究 |
論文名稱(英文) | Integrating Target Coverage and Connectivity for Wireless Heterogeneous Sensor Networks with Multiple Sensing Units |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 資訊工程學系碩士班 |
系所名稱(英文) | Department of Computer Science and Information Engineering |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 95 |
學期 | 2 |
出版年 | 96 |
研究生(中文) | 劉柏均 |
研究生(英文) | Bo-Jun Liu |
學號 | 692191439 |
學位類別 | 碩士 |
語言別 | 英文 |
第二語言別 | |
口試日期 | 2007-06-14 |
論文頁數 | 99頁 |
口試委員 |
指導教授
-
石貴平(kpshih@mail.tku.edu.tw)
委員 - 陳裕賢 委員 - 陳宗禧 委員 - 王三元 委員 - 石貴平 |
關鍵字(中) |
連結性 能源效率 多重感測元件 目標點覆蓋 無線感測網路 無線異質型感測網路 |
關鍵字(英) |
Connectivity Energy-Efficiency Multiple Sensing Units Target Coverage Wireless Sensor Network(WSN) Wireless Heterogeneous Sensor Network(WHSN) |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
本論文在多重感測元件之無線異質型感測網路上,同時考慮目標點覆蓋問題與網路連結性問題(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. |
第三語言摘要 | |
論文目次 |
Contents I List of Figures V List of Tables VII 1 Introduction 1 1.1 Introduction to WSNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Introduction to WHSNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 The Coverage in WHSNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 The Connectivity in WHSNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 Research Overview and Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Related Work 9 2.1 Target Coverage Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Target Coverage and Connectivity Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 WHSNs with Multiple Sensing Units . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3 Solutions to Target Coverage Problem 13 3.1 MUST Problem Statements and ILP Constraints . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13 3.1.2 MUST Problem Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1.3 ILP Constraints for MUST Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Distributed Schemes for MUT Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.1 Remaining Energy First Scheme for Target Coverage(REFS-TC) . . . . . . . . . . 20 3.2.2 Energy Efficient First Scheme for Target Coverage (EEFS-TC). . . . . . . . . . . . 23 4 Solutions to Target Coverage and Connectivity Problem 29 4.1 MU-CSC Problem Statements and ILP Constraints . . . . . . . . . . . . . . . . . . . . . . 29 4.1.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.1.2 MU-CSC Problem Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.1.3 ILP Constraints for MU-CSC Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 Distributed Schemes for MU-TCC Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2.1 Remaining Energy First Scheme for Target Coverage and Connectivity (REFS-TCC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2.2 Energy Efficient First Scheme for Target Coverage and Connectivity (EEFS-TCC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5 Performance Evaluations 49 5.1 Scenarios for MUT Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.1.1 Simulation Environment and Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.1.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.1.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2 Scenarios for MU-TCC Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.2.1 Simulation Environment and Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.2.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6 Conclusions and Future Work 77 6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Bibliography 79 Appendices 85 A Publications List 85 A.1 Journal Paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 A.2 Conference Papers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 B International Conference Versions 87 List of Figures Figure 3.1 An illustrated example, where 5 sensors are scheduled to cover 2 targets . . . 16 Figure 3.2 Example of ILP results for MUST problem . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Figure 3.3 Time Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Figure 4.1 An illustrated example, where 5 sensors are scheduled to cover 2 targets (a) the topology, (b) the coverage and connectivity relationships . . . . . . . . . . . 31 Figure 4.2 Example of ILP results for MU-CSC problem. . . . . . . . . . . . . . . . . . . . . . . . 35 Figure 4.3 The forwarding zone of Sn, Z(s). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Figure 5.1 (a) The energy consumption and (b) the remaining energy vary in each round . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Figure 5.2 The snapshots of the remaining energy of sensors in (a) REFS-TC and (b) EEFS-TC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Figure 5.3 The network lifetime depends on the number of (a) sensors (b) targets (c) attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Figure 5.4 The impacts of the numbers of sensors and targets on the network lifetime in terms of (a) REFS-TC and (b) EEFS-TC . . . . . . . . . . . . . . . . . . . . 55 Figure 5.5 (a) The energy consumption and (b) the remaining energy to the network lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Figure 5.6 The snapshots of the remaining energy of sensors in (a) REFS-TC and (b) EEFS-TC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Figure 5.7 The network lifetime depends on the number of (a) sensors (b) targets (c) attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Figure 5.8 The impacts of the numbers of sensors and targets on the network lifetime in terms of (a) REFS-TC and (b) EEFS-TC. . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Figure 5.9 The impact of Beta on the network lifetime for MU-TCC problem without Communication and Computation Overhead . . . . . . . . . . . . . . . . . . . . . . . . . 65 Figure 5.10 (a) total energy consumption and (b) total remaining energy in each round . . 66 Figure 5.11 The snapshots of the remaining energy of sensors in (a) REFS-TCC and (b) EEFS-TCC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Figure 5.12 The impacts of the numbers of (a) sensors, (b) targets, and (c) attributes on the network lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Figure 5.13 The impact of the numbers of sensors and targets on the network lifetime in terms of (a) REFS-TCC and (b) EEFS-TCC . . . . . . . . . . . . . . . . . . . . . . . 69 Figure 5.14 The impact of Beta on the network lifetime. . . . . . . . . . . . . . . . . . . . . . . . . 70 Figure 5.15 (a) total energy consumption and (b) total remaining energy in each round when control overheads are considered. . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Figure 5.16 The snapshots of the remaining energy of sensors in (a) REFS-TCC and (b) EEFS-TCC when control and communication overheads are considered. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Figure 5.17 The impacts of the numbers of (a) sensors, (b) targets, and (c) attributes on the network lifetime when control and communication overheads are considered. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Figure 5.18 The impact of the numbers of sensors and targets on the network lifetime in terms of (a) REFS-TCC and (b) EEFS-TCC when control overhead is considered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 List of Tables Table 5.1 Simulation settings for MUT problem without communication and computation overhead. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Table 5.2 Energy consumption model for MUT problem without communication and computation overhead. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Table 5.3 Simulation settings for MUT or MU-TCC problem including communication and computation overhead. . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Table 5.4 Energy consumption model for MUT or MU-TCC problem including communication and computation overhead. . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Table 5.5 Simulation settings for MU-TCC problem without communication and computation overhead. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Table 5.6 Energy consumption model for MU-TCC Problem without communication and computation overhead. . . . . . . . . . . . . . . . . . . . . . . . . . . 64 |
參考文獻 |
[1] N. Ahmed, S. S. Kanhere, and S. Jha, "The holes problem in wireless sensor networks: A survey," ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9, no. 2, pp. 4-18, Apr. 2005. [2] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: a survey," Computer Networks, vol. 38, no. 4, pp. 393-422, Mar. 2002. [3] I. Cardei, "Energy-efficient target cverage in heterogeneous wireless sensor networks," in Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), Oct. 2006, pp. 397-406. [4] M. Cardei, M. T. Thai, Y. Li, and W. Wu, "Energy-efficient target coverage in wireless sensor networks," in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, Mar. 2005, pp. 1976-1984. [5] M. Cardei, J. Wu, M. Lu, and M. O. Pervaiz, "Maximum network lifetime in wireless sensor networks with adjustable sensing ranges," in Proceedings of the IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), vol. 3, Aug. 2005, pp. 438-445. [6] Crossbow technology, inc. [Online]. Available: http://www.xbow.com [7] M. Ding, D. Chen, A. Thaeler, and X. Cheng, "Fault-tolerant target detection in sensor networks," in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Mar. 2005. [8] J. Ford, "Telecommunications with MEMS devices: An overview," The 14th Annual Meeting of the IEEE lasers and Electro-Optics society, vol. 2, no. 12, pp. 415-416, Nov. 2001. [9] D. Ganesan, A. Cerpa, W. Ye, Y. Yu, J. Zhao, and D. Estrin, "Networking issues in wireless sensor networks." Journal of Parallel and Distributed Computing, vol. 64, no. 7, pp. 799-814, 2004. [10] C.-F. Huang and Y.-C. Tseng, "The coverage problem in a wireless sensor network," in Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), 2003. [11] Q. Huang, C. Lu, and G.-C. Roman, "Reliable mobicast via face-aware routing," in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Mar. 2004. [12] ILOG CPLEX. [Online]. Available: http://www.ilog.com [13] K. Kalpakis, K. Dasgupta, and P. Namjoshi, "Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks," The International Journal of Computer and Telecommunications Networking, vol. 42, pp. 697-716, Aug. 2003. [14] K. Kar and S. Banerjee, "Node placement for connected coverage in sensor networks," in Proceedings of the First Workshop on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), Mar. 2003. [15] Q. Li, M. D. Rosa, and D. Rus, "Distributed algorithms for guiding navigation across a sensor network," in Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), Sep. 2003, pp. 313-325. [16] S. Megerian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, "Worst and best-case coverage in sensor networks," IEEE Transactions on Mobile Computing, vol. 4, no. 1, pp. 84-92, Jan. 2005. [17] H. O. Sanli, R. Poornachandran, and H. Cam, "Collaborative two-level task scheduling for wireless sensor nodes with multiple sensing units," in Proceedings of the 2nd Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), Sep. 2005, pp. 350-361. [18] Y. Shang and H. Shi, "Coverage and energy tradeoff in density control on sensor networks," in Proceedings of the 11th International Conference on Parallel and Distributed Systems (ICPADS), vol. 1, Jul. 2005, pp. 564-570. [19] K.-P. Shih, Y.-D. Chen, C.-W. Chiang, and B.-J. Liu, "A distributed active sensor selection scheme for wireless sensor networks," in Proceedings of the IEEE International Symposium on Computers and Communications (ISCC), Jun. 2006, pp. 923-928. [20] K.-P. Shih, S.-Y. Wang, H.-C. Chen, and B.-J. Liu, "On target coverage in wireless heterogeneous sensor networks with multiple sensing units," in Proceedings of the IEEE International Symposium on Computers and Communications (ISCC), July 2007. [21] K.-P. Shih, S.-S. Wang, P.-H. Yang, and C.-C. Chang, "CollECT: Collaborative event detection and tracking in wireless heterogeneous sensor networks," in Proceedings of the IEEE International Symposium on Computers and Communications (ISCC), Jun. 2006, pp. 935-940. [22] T.-P. Shuai and X.-D. Hu, "Connected set cover problem and its applications," Lecture Notes in Computer Science (LNCS), vol. 4041, pp. 243-254, 2006. [23] D. Tian and N. D. Georganas, "A coverage-preserving node scheduling scheme for large wireless sensor networks," in Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), 2002, pp. 32-41. [24] G. Wang, G. Cao, and T. L. Porta, "Movement-assisted sensor deployment," in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 4, Mar. 2004, pp. 2469-2479. [25] G. Wang, G. Cao, T. L. Porta, and W. Zhang, "Sensor relocation in mobile sensor networks," in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 4, Mar. 2005, pp. 2302-2312. [26] J. Wang and N. Zhong, "Efficient point coverage in wireless sensor networks," Journal of Combinatorial Optimization, vol. 11, no. 3, pp. 291-304, May 2006. [27] X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill, "Integrated coverage and connectivity con¯guration in wireless sensor networks," in Proceedings of the ACM International Conference on Embedded Networked Sensor Systems (SENSYS), 2003, pp. 28-39. [28] T. Yan, T. He, and J. A. Stankovic, "Differentiated surveillance for sensor networks," in Proceedings of the ACM International Conference on Embedded Networked Sensor Systems (SENSYS), 2003, pp. 51-62. [29] S. Yang, F. Dai, M. Cardei, and J. Wu, "On multiple point coverage in wireless sensor networks," in Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), Nov. 2005, pp. 757-764. [30] H. Zhang and J. C. Hou, "Maintaining sensing coverage and connectivity in large sensor networks," in Proceedings of International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, Feb. 2004. [31] Q. Zhao and M. Gurusamy, "Maximizing network lifetime for connected target coverage in wireless sensor networks," in Proceedings of the IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Jun. 2006, pp. 94-101. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信