 |
| 系統識別號 |
U0002-2106201100353900 |
| 中文論文名稱
|
網格化之混合式無線感測器網路空洞修復機制 |
| 英文論文名稱
|
Grid-based hole recovery mechanism in hybrid wireless sensor networks |
| 校院名稱 |
淡江大學 |
| 系所名稱(中) |
資訊工程學系博士班 |
| 系所名稱(英) |
Department of Computer Science and Information Engineering |
| 學年度 |
99 |
| 學期 |
2 |
| 出版年 |
100 |
| 研究生中文姓名 |
黃國峰 |
| 研究生英文姓名 |
Kuo-Feng Huang |
| 學號 |
896410148 |
| 學位類別 |
博士 |
| 語文別 |
英文 |
| 口試日期 |
2011-06-10 |
| 論文頁數 |
98頁 |
| 口試委員 |
指導教授-王英宏
委員-廖弘源
委員-施國琛
委員-陳振炎
委員-陳朝欽
委員-許輝煌
委員-王英宏
|
| 中文關鍵字 |
混合式感測器網路
空洞修復
網格化
虛擬引力
移動式節點
|
| 英文關鍵字 |
hybrid sensor network
hole recovery
grid-based
virtual force
mobile nodes
|
| 學科別分類 |
學科別＞應用科學＞資訊工程
|
| 中文摘要 |
無線感測器網路(Wireless Sensor Networks, WSNs)其技術可廣泛應用在許多領域中，尤其是環境監測。然而，由於部署無線感測器節點時的不平均，或有障礙物例如湖和山丘的存在，或感測器節點的電量耗盡與被外力破壞等因素，進而造成無線感測器網路中存在著空洞(Hole)，而這些空洞會使無線感測器網路的效能降低。因此，如何找出這些空洞的位置，並利用這些空洞位置所獲得的資訊進行空洞修復，提升無線感測器網路之效能，是一個相當重要的研究議題。
本論文提出一個基於網格化之混合式無線感測器網路空洞修復機制。藉由網格式架構的方式，利用網格首節點廣播及代傳空洞偵測資訊，再由資料收集點加以計算空洞之位置等資訊，並利用虛擬引力決定具移動性感測器節點進行空動修復動作，以提高網路整體效能。經由模擬實驗證明本論文所提出之空洞修復機制可有效的維持網路的高覆蓋率，並可延長感測器網路之生存時間，以提升無線感測器網路之效能。
|
| 英文摘要 |
In wireless sensor networks, the nodes are typically empowered with scarce energy resource and limited computing power. The network can not get fully connectivity due to the randomly deploy static sensor nodes which may cause the hole problem. However, the network performance could be improved by the high coverage ratio because of saving the energy for transmitting. Hence, the hole problem is one of the important issues in wireless sensor networks.
We proposed a hole recovering mechanism based on grid architecture with mobile sensor nodes. The virtual force theory is used for determining which mobile sensor node should recover the hole. The proposed mechanism could efficiently maintain high coverage ratio and prolong the entire network lifetime. The simulation results demonstrate that our mechanism indeed recover routing holes and prolong the network lifetime.
|
| 論文目次 |
Contents III
List of Figures V
List of Tables VI
1. Introduction 1
2. Related Works 4
2.1 Wireless Sensor Networks 4
2.1.1 Hardware Components 6
2.1.2 Charateristic Requirements 9
2.1.3 Salient Features of Sensor Networks 11
2.1.4 Common Design Problems in WSNs 14
2.2 Coverage and Connectivity Issues in Wireless Sensor Networks 17
2.2.1 Mathmatical Frameworks 18
2.2.1.1 Sensing Model 18
2.2.1.2 Communication Model 19
2.2.1.3 Coverage Model 21
2.2.2 Coverage based on Exposure Paths 23
2.2.2.1 Minimal exposure path: Worst-case coverage 23
2.2.2.2 Maximal exposure path: Best-case coverage 26
2.2.2.3 Maximal breach path: Worst-case coverage 27
2.2.2.4 Maximal support path: Worst-case coverage 28
2.2.3 Coverage based on Sensor Deployment Strategies 29
2.2.3.1 Imprecise detection algorithm (IDA) 29
2.2.3.2 Potential field algorithm (PFA) 30
2.2.3.3 Distributed self-spreading algorithm (DSSA) 32
2.2.3.4 Bidding Protocol (BIDP) 33
2.2.3.5 Energy-efficient Coverage Hole Self-repair in Mobile Sensor Networks (DSEPA) 33
2.2.3.6 On-demand Deployment Algorithm for a Hybrid Sensor Network (On-demand) 34
3. Grid-based hole recovery mechanism 35
3.1 Virtual Force Formulation 39
3.2 Network Initiation Phase 40
3.2.1 Griding Phase 40
3.2.2 Hole Detecting Phase 47
3.2.3 Hole Recovering Phase 53
3.3 Network Maintaining Phase 57
4. Simulation and Results 61
4.1 Simulation Environment 61
4.2 Simulation Results and Analysis 63
5. Conclusion and Future Works 68
Bibliography 70
Appendix A. Publication List 75
Appendix B. “Grid-based Mobile Target Tracking Mechanism in Wireless Sensor Networks” JOURNAL OF COMMUNICATIONS 79
Appendix C. “QPPS : Qos Provision Packet Scheduling Algorithm in High Speed Downlink Packet Access” JOURNAL OF WSEAS TRANSACTIONS ON COMMUNICATIONS 87
List of Figures
Figure 2-1: Main sensor node hardware components 6
Figure 2-2: Example of probabilistic sensing model 19
Figure 2-3: Example of communication model 20
Figure 3-1: System framework 37
Figure 3-2: Example of system environment 38
Figure 3-3: Relation between R and d 41
Figure 3-4: Example of numbering grid 42
Figure 3-5: Example of gridding network scenario 44
Figure 3-6: Procedures of gridding phase 45
Figure 3-7: Procedures of message forwarding 47
Figure 3-8: Procedures of hole detecting 51
Figure 3-9: Example of completing hole detecting phase 52
Figure 3-10: Procedures of selecting MNs 55
Figure 3-11: Procedures of network maintaining phase 58
Figure 4-1: Message complexity 64
Figure 4-2: Coverage ratio 65
Figure 4-3: Energy consumption 66
Figure 4-4: System lifetime 67
List of Tables
Table 3-1: Grid Information Table 43
Table 3-2: Det_Hole_Message Format 48
Table 3-3: Det_Hole_Ack Format 49
Table 3-4: Hole Grid Information Table 53
Table 4-1: Simulation parameters 62 |
| 參考文獻 |
[1] E. S. Biagioni and K. W. Bridges, “The application of remote sensor technology to assist the recovery of rare and endangered species”, High Performance Computing Applications, Vol. 17, No. 3, August 2002, pp. 315-324.
[2] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson, “Wireless sensor networks for habitat monitoring”, Proceedings of ACM Wireless Sensor Networks and Applications, Atlanta GA, September 2002, pp. 88-97.
[3] L. Schwiebert, S. K. S. Gupta, and J. Weinmann, “Research challenges in wireless networks of biomedical sensors”, Proceedings of ACM Sigmobile, Rome, Italy, July 2001, pp 151-165.
[4] J. Aslam, Z. Butler, F. Constantin, V. Crespi, G. Cybenko, and D. Rus, “Tracking a moving object with a binary sensor network”, Proceedings of the ACM Embedded Networked Sensor Systems, Los Angeles, USA, November 2003, pp. 150-161.
[5] H. T. Kung and D. Vlah, “Efficient Location Tracking Using Sensor Networks”, Proceedings of IEEE Wireless Communications and Networking, New Orleans, Louisiana, USA, Vol. 3, March 2003, pp. 1954-1961.
[6] J. F. Chen, Y. H. Wang, K. F. Huang, T. W. Chang, “Grid-based Mobile Target Tracking Mechanism in Wireless Sensor Networks”, Journal of Communications, Vol. 5, No. 6, June 2010, pp. 475-482.
[7] A. Agah, S. K. Das, K. Basu, and M. Asadi, “Intrusion detection in sensor networks: a non-competitive game approach”, Proceedings of IEEE Vehicular Technology, Los Angeles, USA, Vol. 4, Fall 2004, pp. 343-346.
[8] R. Roman, J. Zhou, and J. Lopez, “Applying intrusion detection systems to wireless sensor networks”, Proceedings of IEEE Consumer Communications and Networking, Las Vegas, USA, Vol. 1, January 2006, pp. 640-644.
[9] G. T. Sibely, M. H. Rahimi, and G. S. Sukhatme, “Robomote: A Tiny Mobile Robot Platform for Large-Scale Sensor Networks”, Proceedings of IEEE Robotics and Automation, Washington DC, USA, May 2002, pp. 1143-1148.
[10] Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization Based on Virtual Forces”, Proceedings of IEEE INFOCOM, San Franciso, USA, Vol. 2, March 2003, pp. 1293-1302.
[11] A. Howard, M.J. Mataric, and G.S. Sukhatme, “An Incremental Self-Deployment Algorithm for Mobile Sensor Networks”, Autonomous Robots, Vol. 13, No. 2, 2003, pp 113-126.
[12] A. Howard, M.J. Mataric, and G.S. Sukhatme, “Mobile Sensor Networks Deployment Using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem”, Proceedings of Distributed Autonomous Robotics Systems, Fukuoka, Japan, June 2002, pp. 299-308.
[13] M. Locateli and U. Raber, “Packing equal circles in a square: a deterministic global optimization approach”, Discrete Applied Mathematics, Vol. 122, October 2002, pp. 139-166.
[14] I. F. Akyildiz, W. Su, Y. Sankasubramaniam, and E. Cayirci, “Wireless Sensor Networks: A Survey”. Computer Networks, Vol. 38, pp.393–422, 2002.
[15] G. Asada, M. Dong, T. S. Lin, F. Newberg, G. Pottie, and W. J. Kaiser, “Wireless Integrated Network Sensors: Low Power Systems on a chip”. Proceedings of 24th European Solid State Circuits Conference, Netherlands, September 1998, pp. 9-12.
[16] G. Boriello and R. Want, “Embedded Computation Meets the World Wide Web”. ACM Communications, Vol. 43, Issue 5, pp. 59–66, 2000.
[17] J. Burrell, T. Brooke, and R. Beckwith, “Vineyard Computing: Sensor Networks in Agricultural Production.” IEEE Pervasive Computing, Vol. 3, Issue 1, pp. 38–45, 2004.
[18] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao, “Habitat Monitoring: Application Driver for Wireless Communications Technology.” ACM Special Interest Group on Data Communication, Vol. 31, No. 2, pp. 20-41, Apr. 2001.
[19] R. Szewczyk, E. Osterweil, J. Polastre, M. Hamilton, A. Mainwaring, and D. Estrin, “Habitat Monitoring with Sensor Networks.” ACM Communication, Vol. 47, Issue 6, pp.34–40, 2004.
[20] G. J. Pottie and W. J. Kaiser, “Embedding the Internet: Wireless Integrated Network Sensors.” ACM Communications, Vol. 43, Issue 5, pp. 51–58, 2000.
[21] V. Raghunathan, C. Schurgers, S. Park, and M. B. Srivastava, “Energy-Aware Wireless Microsensor Networks.” IEEE Signal Processing Magazine, Vol. 19, pp. 40–50, 2002.
[22] J. M. Kahn, R. H. Katz, and K. S. J. Pister, “Next Century Challenges: Mobile Networking for “Smart Dust”.” Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking, Seattle, WA, pp. 271-278, August 1999.
[23] J. M. Rabaey, M. J. Ammer, J. L. da Silva, D. Patel, and S. Roundy, “PicoRadio Supports Ad Hoc Ultra-Low Power Wireless Networking.” IEEE Computer, Vol. 33, Issue 7, pp. 42–48, 2000.
[24] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks.” IEEE Transactions on Wireless Communications, Vol. 1, Issue 4, pp. 660-670, 2002.
[25] S. Kulkarni, A. Iyer, and C. P. Rosenberg, “An address-light, integrated mac and routing protocol for wireless sensor networks.” IEEE/ACM Transactions on Networking, Vol. 14, Issue 4, pp.793–806, 2006.
[26] C. Savarese, J. M. Rabaey, and J. Beutel, “Locationing in distributed ad-hoc wireless sensor networks.” Proceedings of the USENIX Technical Annual, pp. 317-327, May 2002.
[27] P. Gupta and P. R. Kumar, “The capacity of wireless networks.” IEEE Transactions on Information Theory, Vol. 46, Issue 2, pp.388–404, 2000.
[28] D. W. Gage, “Command control for many-robot systems.” Unmanned System Magazine. Vol. 10, Issue 4, pp. 28-34, 1992.
[29] S. Megerian, F. Koushanfar, G. Qu, G. Veltri, and M. Potkonjak, “Exposure in wireless sensor networks: Theory and practical solutions.” Wireless Networks, Vol. 8, Issue 5, pp.443-454, 2002.
[30] Y. Zou and K. Chakrabarty, “Sensor deployment and target localization in distributed sensor networks.” IEEE Embedded Computer System, Vol. 3, Issue 1, pp.61-91, 2004.
[31] S. Megerian, F. Koushanfar, G. Qu, G. Veltri, and M. Potkonjak, “Exposure in wireless sensor networks: Theory and practical solutions.” Wireless Networks, Vol. 8, Issue 5, pp. 443–454, 2002.
[32] X.-Y. Li, P.-J. Wan, and O. Frieder, “Coverage in wireless ad-hoc sensor networks.” IEEE Transaction Computer, Vol. 52, pp.753–763, 2003.
[33] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Coverage problems in wireless ad-hoc sensor networks.” Proceeding of IEEE Computer Communications, Anchorage, AK, pp. 115–121, April 2001.
[34] G. Veltri, Q. Huang, G. Qu, and M. Potkonjak, “Minimal and maximal exposure path algorithms for wireless embedded sensor networks.” Proceeding of Embedded Networked Sensor Systems, Los Angeles, pp. 40–50, Nov. 2003.
[35] S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak, “Exposure in wire less ad-hoc sensor networks.” Proceeding of Mobile Computing and Networking, Rome, Italy, pp. 139–150, July 2001.
[36] S. S. Dhilon, K. Chakrabarty, and S. S. Iyengar, “Sensor placement for grid coverage under imprecise detections.” Proceeding of 5th Information Fusion, Annapolis, MD, pp. 1-10, July 2002.
[37] S. Poduri and G. S. Sukhatme, “Constrained coverage in mobile sensor networks.” Proceeding of Robotics and Automation, New Orleans, LA , pp. 40-50, April–May 2004.
[38] N. Heo and P. K. Varshney, “A distributed self-spreading algorithm for mobile wireless sensor networks.” Proceeding of IEEE Wireless Communications and Networking, New Orleans, LA, pp. 1597-1602, March 2003.
[39] G. Wang, G. Cao, and T. LaPorta, “A bidding protocol for deploying mobile sensors.” Proceeding of IEEE Network Protocols, Atlanta, GA, pp. 80-91, Nov. 2003.
[40] R. Wu, J. He, T.J. Li, H. S, “Energy-efficient coverage hole self-repair in mobile sensor network.” Proceeding of IEEE New Trends in Information and Service Science, Beijing, China, pp. 1297-1302, June 2009.
[41] L.C. Shiu, C.Y. Lee, T.W. Song, and C.S. Yang “On-demand deployment algorithm for a hybrid sensor network.” Proceeding of IEEE Embedded and Ubiquitous Computing, Shanghai, China, pp. 697 – 702, Dec. 2008.
[42] Minghua Yang, Yuanda Cao, Li Tan, Jiong Yu, “A New Self-Deployment Algorithm in Hybrid Sensor Network.” Proceeding of IEEE Intelligent Information Technology Application, Shanghai, China, pp. 268-272, Dec. 2008
|
| 論文使用權限 |
同意紙本無償授權給館內讀者為學術之目的重製使用，於2016-06-29公開。同意授權瀏覽/列印電子全文服務，於2016-06-29起公開。 |
 |
|
 |
