淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


系統識別號 U0002-0708201414193700
中文論文名稱 具電量平衡考量及反應時間限制之行動感測器搬遷問題研究
英文論文名稱 Mobile Sensor Relocation Problem with Energy-Balanced and Timely Consideration
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 102
學期 2
出版年 103
研究生中文姓名 黃郅崴
研究生英文姓名 Chih-We Huang
學號 601410870
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2014-06-16
論文頁數 48頁
口試委員 指導教授-鄭建富
委員-黃啟富
委員-潘孟鉉
委員-鄭建富
中文關鍵字 移動無線感測網路  移動感測器  感測器故障  反應時間  感測器搬遷問題 
英文關鍵字 mobile wireless sensor networks  mobile sensor  sensor failure  response time  sensor relocation problem 
學科別分類 學科別應用科學資訊工程
中文摘要 在無線感測網路中,感測器搬遷問題(Sensor Relocation problem)是一項非常重要的研究議題。感測器搬遷問題與感測器部署問題(Sensor Deployment problem)的最大差別在於感測器搬遷問題具有嚴格的反應時間限制。其原因在於感測器部署問題處於網路的初始化階段,此階段的目標是讓建構出來的無線感測網路達到一定的覆蓋程度即可,因此通常不會有嚴格的反應時間限制。然而感測器搬遷問題處於無線感測網路的運作階段,因此必須盡可能在不影響監控任務下,利用冗餘感測器來完成故障感測器的替換及空洞處理。這也就是為什麼感測器搬遷問題會有較為嚴格的反應時間限制。在本論文中,我們將針對移動無線感測網路下的感測器搬遷問題做一探討,提出新的感測器搬遷演算法。在減少訊息量方面,我們將利用quorum的概念來傳送訊息封包,並搭配本論文所設計出的封包代轉停止條件(Stopping Criteria)來減少訊息封包之傳送量。在減少反應時間以及減少移動距離方面,冗餘感測器將採連座式移動(Cascaded Movement)的方式來進行故障感測器的替換及空洞處理。在連座式排程(Cascading Schedule)規劃方面,將藉由加入網路存活時間估計值(estimated value of network lifetime)考量,來避免不必要的感測器移動。經由實驗結果可以證明我們所提出的感測器搬遷演算法在訊息量、反應時間、移動距離以及網路存活時間上皆有著很好的表現。
英文摘要 The Sensor Relocation problem (SR problem) is an important issue in Wireless Sensor Networks (WSNs). The main difference between SR problem and Sensor Deployment (SD) problem is that SR problem has a strict response time requirement. Because the SD problem occurs during network initialization, so there is no strict response time requirement. The SD problem is solved as long as the required coverage level is met. However, the SR problem occurs during operation of WSNs, we need to minimize the impact on the surveillance task while replacing faulty sensors with redundant sensors. In this thesis, we revisit the SR problem in mobile WSNs. In order to reduce the amount of message exchange, the proposed SR algorithm uses the concept of quorum to send RICH packets (in columns) and HUNGRY packets (in rows). With the proposed stopping criteria, the proposed algorithm can further reduce the amount of these two types of packets to send. In terms of response time and moving distance, the proposed algorithm moves redundant sensors to faulty sensors and coverage holes by cascaded movement. It also considers the estimated value of network lifetime in the planning of cascading schedule. Hence, the SR problems caused by inappropriate cascading schedules can be avoided. Overall, the proposed SR algorithm has the following features: smaller amount of message exchange, shorter response time, shorter moving distances, smaller number of requesting places, and longer network lifetime. The performance evaluation done in this research has confirmed its superior performances in all these aspects.
論文目次 目錄
圖目錄 Ⅴ
表目錄 Ⅶ
第一章、簡介 1
第二章、相關研究 4
2.1Robot-Assisted SR Problem 4
2.2Self-Relocation SR Problem 5
第三章、問題定義以及環境假設 12
第四章、方法描述 14
4.1Requesting place與冗餘感測器之配對 14
4.2Cascading Schedule之規劃 22
第五章、實驗分析及模擬 30
第六章、結論 38
參考文獻 39
附錄-英文論文 43

圖目錄
圖1. 無線感測網路之生命週期 2
圖2. Cascaded movement 7
圖3. Cascading Schedule 8
圖4. 網格Grid(x+1,y)中的感測器皆發生故障 8
圖5. BCS演算法之執行範例 10
圖6. 網路環境 12
圖7. RICH封包傳送方式 16
圖8. 直角三角形CDE以及CF'E 17
圖9. Grid(i+1,j+1)之header可以通訊的範圍 17
圖10. 當網格中沒有header可以發送HUNGRY封包 20
圖11. HUNGRY封包的代傳停止條件 21
圖12. Members of cascaded movement的挑選範圍 25
圖13. 橫跨多個網格的移動 26
圖14. cascading schedule例子 26
圖15. The Pseudo Code of SRM algorithm 28
圖16. The Pseudo Code of SRS algorithm 29
圖17. RICH封包之傳送量比較圖-1 31
圖18. RICH封包之傳送量比較圖-2 31
圖19. HUNGRY封包之傳送量比較圖-1 32
圖20. HUNGRY封包之傳送量比較圖-2 32
圖21. HUNGRY封包數量及RICH封包數量之關係圖 33
圖22. 反應時間比較圖-1 34
圖23. 反應時間比較圖-2 34
圖24. 進行cascaded movement時,所需包含到的感測器數量 35
圖25. 不同故障率下之網路存活時間 36
圖26. 不同尺寸場景之網路存活時間 37

表目錄
表1 參數設定 30
參考文獻 [1] A. Ababnah, B. Natarajan, “Optimal Control-Based Strategy for Sensor Deployment,” IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, vol. 41, no. 1, pp. 97-104, 2011.
[2] H. Alemdar, C. Ersoy, “Wireless Sensor Networks for Healthcare: A Survey,” Computer Networks, vol. 54, pp. 2688-2710, 2010.
[3] L. Atzori, A. Iera, G. Morabito, “The Internet of Things: A Survey,” Computer Networks, vol. 54, no. 15, pp. 2787-2805, 2010.
[4] F. Aurenhammer, “Voronoi diagrams – A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys, vol. 23, pp. 345-406, 1991.
[5] C.F. Cheng, K. T. Tsai, “Distributed Barrier Coverage in Wireless Visual Sensor Networks with β-QoM,” IEEE Sensors Journal, vol. 12, no. 6, pp. 1726-1735, 2012.
[6] C.F. Cheng, T. Y. Wu and H. C. Liao, “A Density-Based Barrier Construction Algorithm with Minimum Total Movement in Mobile WSNs,” Computer Networks, DOI: 10.1016/j.bjp.2013.12.001, 2013.
[7] G. Fletcher, X. Li, A. Nayak, I. Stojmenovic, “Randomized Robot-assisted Relocation of Sensors for Coverage Repair in Wireless Sensor Networks,” Proceeding of the Vehicular Technology Conference Fall (VTC-F 2010), pp. 1-5, 2010.
[8] M. Garetto, M. Gribaudo, C. Chiasserini, E. Leonardi, “A Distributed Sensor Relocation Scheme for Environmental Control,” in Proceeding of the IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS 2007), pp. 1-10, 2007.
[9] D. Gu, “A Game Theory Approach to Target Tracking in Sensor Networks,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 41, no. 1, pp. 2-13, 2011.
[10] D. M. Han, J. H. Lim, “Smart Home Energy Management System Using IEEE 802.15.4 and Zigbee,” IEEE Transactions on Consumer Electronics, vol. 56, no. 3, pp. 1403-1410, 2010.
[11] S. He, J. Chen, P. Cheng, Y. Gu, T. He, Y. Sun, “Maintaining Quality of Sensing with Actors in Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 9, 2012.
[12] R. V. Kulkarni, A. Forster, G. K. Venayagamoorthy, “Computational Intelligence in Wireless Sensor Networks: A Survey,” IEEE Communications Surveys & Tutorials, vol. 13, no. 1, pp. 68-96, 2011.
[13] W. Li, Y. I. Kamil, A. Manikas, “A Wireless Array based Cooperative Sensing Model in Sensor Networks,” Proceeding of the Global Communications Conference (GLOBECOM 2008), pp. 1-6, 2008.
[14] W. Li, Y. I. Kamil, A. Manikas, “Wireless Array Based Sensor Relocation in Mobile Sensor Networks,” Networks,” Proceeding of the International Conference on Wireless Communications and Mobile Computing (IWCMC 2009) , pp. 832-838, 2009.
[15] A. V. Savkin, F. Javed, A. S. Matveev, “Optimal Distributed Blanket Coverage Self-Deployment of Mobile Wireless Sensor Networks,” IEEE Communications Letters, vol. 16, no. 6, pp. 949-951, 2012.
[16] Y.Y. Shih, W.H. Chung, P.C. Hsiu, A.C. Pang, “A Mobility-Aware Node Deployment and Tree Construction Framework for ZigBee Wireless Networks,” IEEE Transactions on Vehicular Technology, vol. 62, no. 6, pp. 2763-2779, 2013.
[17] F. Stajano, N. Hoult, I. Wassell, P. Bennett, C. Middleton, K. Soga, “Smart Bridges, Smart Tunnels: Transforming Wireless Sensor Networks from Research Prototypes into Robust Engineering Infrastructure,” Ad Hoc Networks, vol. 8, pp. 872-888, 2010.
[18] C. Suh, Y. B. Ko, “Design and Implementation of Intelligent Home Control Systems Based on Active Sensor Networks,” IEEE Transactions on Consumer Electronics, vol. 54, no. 3, pp. 1177-1184, 2008.
[19] G. Wang, G. Cao, T. L. Porta, W. Zhang, “Sensor Relocation in Mobile Sensor Networks,” Proceeding of the International Conference on Computer Communications (INFOCOM 2005), vol. 4, pp. 2302-2312, 2005.
[20] B Wang, H. B. Lim, D. Ma, “A Coverage-Aware Clustering Protocol for Wireless Sensor Networks,” Computer Networks, vol. 56, no. 5, pp. 1599-1611, 2012.
[21] C. Wang, H. Ma, Y. He, S. Xiong, “Adaptive Approximate Data Collection for Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 6, pp. 1004-1016, 2012.
[22] X. Wang, S. Wang, “Hierarchical Deployment Optimization for Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 10, no. 7, pp. 1028-1041, 2011.
[23] J.L. Wardlaw, I. Karaman, A. Karsilayan, “Low-Power Circuits and Energy Harvesting for Structural Health Monitoring of Bridges,” IEEE Sensors Journal, vol. 13, no. 2, pp. 709-722, 2013.
[24] F. Hu, Y. Xiao, Q. Hao, “Congestion-Aware, Loss-Resilient Bio-Monitoring Sensor Networking for Mobile Health Applications,” IEEE Journal on Selected Areas in Communications, vol. 27, no. 4, pp. 450-465, 2009.
[25] O. Younis, M. Krunz, S. Ramasubramanian, “Node Clustering in Wireless Sensor Networks: Recent Developments and Deployment Challenges,” IEEE Networks, vol. 20, no. 3, pp. 20-25, 2006.
[26] Q. Yang, S. He, J. Li, J. Chen, Y. Sun, “Energy-Efficient Probabilistic Area Coverage in Wireless Sensor Networks,” IEEE Transactions on Vehicular Technology, DOI: 10.1109/TVT.2014.2300181, 2014.
[27] H. Yang, Y. Qin, G. Feng, H. Ci, “Online Monitoring of Geological CO2 Storage and Leakage Based on Wireless Sensor Networks,” IEEE Sensors Journal, vol. 13, no. 2, pp. 556-562, 2013.
[28] D. Zorbas, C. Douligeris, “Connected Coverage in WSNs Based on Critical Targets,” Computer Networks, vol. 55, no. 6, pp. 1412-1425, 2011.
[29] Y. Zou, K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Transactions on Embedded Computing Systems, vol. 3, no. 1, pp. 61-91, 2004
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2019-08-11公開。
  • 同意授權瀏覽/列印電子全文服務,於2019-08-11起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信