系統識別號 | U0002-2906201020085500 |
---|---|
DOI | 10.6846/TKU.2010.01084 |
論文名稱(中文) | 行動感測網路中目標物覆蓋之具時效性資料收集與感測器派遣機制 |
論文名稱(英文) | Delay-Tolerant Data Collection and Sensor Dispatch Mechanisms for Disconnected Targets in Wireless Mobile Sensor Networks |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 資訊工程學系資訊網路與通訊碩士班 |
系所名稱(英文) | Master's Program in Networking and Communications, Department of Computer Science and Information En |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 98 |
學期 | 2 |
出版年 | 99 |
研究生(中文) | 謝震宇 |
研究生(英文) | Chen-Yu Hsieh |
學號 | 697420627 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | 英文 |
口試日期 | 2010-06-04 |
論文頁數 | 103頁 |
口試委員 |
指導教授
-
張志勇
委員 - 陳裕賢 委員 - 陳宗禧 委員 - 游國忠 委員 - 張志勇 |
關鍵字(中) |
目標點覆蓋 行動感測網路 具權重之目標點 具時效性資料收集 具監控品質需求之目標點 |
關鍵字(英) |
Target Coverage Wireless Mobile Sensor Networks Data Collection Weighted Target Quality of Monitoring of Target |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
目標物覆蓋(Target Coverage)在無線感測網路(Wireless Sensor Networks, WSNs)中是個很重要的研究議題。然而,在過去的研究中,大都假設目標物間相互連結。本論文所考慮的目標物(Target Points)乃分散於許多不連續區域中。為使目標物的資訊可在時限內傳達至收集站(Sink Node),行動資料蒐集裝置(Data Mule)必須設法以移動性來達成網路的連通及目標物資訊的收集等目的。本論文提出了Time-Constrained Target Points Patrolling (TCTP) Algorithm,使分處於各地的Data Mule以分散式的方式,在目標物之間建置出一有效率的巡邏路徑,進行感測及資料蒐集的任務,並使這個路徑中每個目標物具有相近的資訊更新時間週期,並考慮Data Mule的電量限制與充電問題。此外,本論文亦針對具不同權重的目標物提出Weight-TCTP(W-TCTP) Algorithm,使Data Mule對於重要性較高的目標物,給予其較高的感測與收集頻率,提高其資料更新之速度。 除了收集目標物的路徑建外,本論文亦針對Data Mule如何在初始階段快速到達目標物進行深入研究。本論文考慮一行動感測網路之派遣問題,每個目標物依重要性不同的監控品質(Quality of Monitoring, QoM)需求,但由於行動感測器在一開始隨機散佈於環境中,使行動感測器之間並無法利用通訊能力協調所要前往的目標物,這使得行動感測器的派遣面臨極大的挑戰。本論文考慮目標物分散在各區域且不連續,為了對這些不連結的目標物進行監控,本論文發展一有效率的Mobile Sensor Dispatching Mechanism (MDM),可使隨機散佈於環境中的行動感測器以最少的移動成本迅速的覆蓋目標物,且滿足目標物之QoM需求。此外,本論文還提出了Learning Dispatching Mechanism (L-MDM) ,使行動感測器在執行派遣工作的同時,利用與其他感測器短暫交會的機會,分享其移動經驗,使行動感測器透過可學習機制,以更高的效率覆蓋目標物且滿足目標物的QoM需求。 |
英文摘要 |
Target coverage problem has been widely discussed in Wireless Sensor Networks (WSNs). Different from the traditional target coverage problem, this paper considers the scenario that the target points are distributed over several disconnected areas. To collect the target information within a given time period, data mules should move and visit all target points for data collection in a disconnected network. Since the time interval (also referred to visiting interval) for consecutively visiting to each target point reflects the monitoring quality of this target point, the goal of this research is to minimize the maximal visiting interval for each target point. Given a number of data mules, this thesis initially proposes a Time-Constrained Target Points Patrolling (TCTP) algorithm which aims at constructing an efficient patrolling path for all data mules to visit each target point with a minimal visiting interval. Then a Weighted-TCTP (W-TCTP) algorithm is further proposed to cope with the weighted target problem where some targets might have higher weights and should have higher data update frequencies. In addition, this thesis consider the energy constraint of data mules and additionally proposes a RW-TCTP algorithm that treats energy recharge station as a weighted target and arranges all data mules visiting the recharge station before exhausting their energies. Simulation results reveal that the proposed TCTP and RW-TCTP mechanisms outperform the existing work in terms of visiting interval. In addition to the path construction problem, this thesis also considers the dispatching problem. In the considered environment, each target point gi is assigned with a Quality of Monitoring (QoM) value QoMi which representing the number of data mules required for monitoring the target. The given mobile sensors are randomly distributed in the monitoring region and thus they can not communicate with each other. As a result, the key challenge of the dispatching problem is that each mobile sensor should locally construct a visiting path passing thourhg all targets such that all targets can rapaidly satisfy their own QoMs with a minimal movement cost of mobile sensors. To cope with the dispatching problem, this thesis presents two efficient Mobile Sensor Dispatching Mechanisms (MDM) which aims to minimize the movement cost of mobile sensor while the QoM demand of each target is rapaidly satisfied. Experimental study shows that the proposed dispatching mechanism has a better performance than existing work in terms of movement cost of mobile sensors. |
第三語言摘要 | |
論文目次 |
目錄 IV 圖目錄 V 表目錄 VIII 第一章 簡介 1 第二章 相關研究 5 第三章 Data Collection Mechanisms (DCM) 9 3.1 Network Environment and Problem Formulations 10 3.2 Basic TCTP (B-TCTP) Algorithm 13 3.3 Weighted TCTP (W-TCTP) Algorithm 15 3.3.1 Path Construction (PC) Phase 15 3.3.2 Patrolling Phase 25 3.4 W-TCTP with Recharge(RW-TCTP) Algorithm 27 3.4.1 RW-TCTP algorithm 27 3.5 Performance Study 31 3.5.1 Simulation Model 32 3.5.2 Performance Study 33 第四章 Mobile Sensor Dispatching Mechanisms (MDM) 45 4.2 Mobile Sensor Dispatching Mechanism (MDM) 51 4.2.1 Basic Dispatching Mechanism (BDM) 54 4.2.2 Pessimistic Dispatching Mechanism (PDM) 56 4.2.3 Revenue- Based Dispatching Mechanism (RDM) 67 4.3 Learning Dispatching Mechanism (L-MDM) 70 4.3.1 Learning Policy 70 4.3.2 Earlier Termination Policy 71 4.3.3 Power Control Policy 71 4.4 Performance Study 73 4.4.1 Simulation Model 73 4.4.2 Performance Study 74 第五章 結論 88 參考資料 90 附錄—英文論文 92 圖目錄 圖(3.1) Delay-Tolerant Data Collection Network Environment 10 圖(3.2) Hamilton Patrolling Route 14 圖(3.3) Weighted-TCTP Patrolling Route 17 圖(3.4) Weighted-TCTP Patrolling Route (Weighted=x) 19 圖(3.5)(a) W-TCTP by Shortest-Length Policy 22 圖(3.5)(b) W-TCTP by Balancing-Length Policy 22 圖(3.6) W-TCTP Route Construct Algorithm 24 圖(3.7) Euler Circuit Patrolling Route 26 圖(3.8) Recharging Route 28 圖(3.9) RW-TCTP Algorithm 31 圖(3.10) 行動感測網路中目標物覆蓋演算法之SDT比較。 34 圖(3.11) 行動感測網路中目標物每次被拜訪之SDT比較。 35 圖(3.12) 行動感測網路中目標物覆蓋演算法之SD比較。 36 圖(3.13) CHB及TCTP演算法與目標物及DM數量關係之SD比較。 37 圖(3.14) 行動感測網路中目標物覆蓋演算法滿足VIP 權重值之移動成本比較。 39 圖(3.15) Shortest Policy以及Balancing Policy之SDT比較。 40 圖(3.16) Shortest Policy以及Balancing Policy之SD比較。 40 圖(3.17) Shortest Policy以及Balancing Policy在VIP數及權重值大小不同時之SDT比較。 41 圖(3.18) Shortest Policy以及Balancing Policy在VIP數及權重值大小不同時之SD比較。 42 圖(3.19) DM充電機制之能源使用效率比較。 44 圖(4.1) Mobile Sensor Dispatching Network Environment 47 圖(4.2) 行動感測器滿足目標物之QoM。 48 圖(4.3) Terminated Condition 53 圖(4.4) Basic Dispatching Mechanism 55 圖(4.5) BDM Algorithm 56 圖(4.6) Dispatching Fault 57 圖(4.7) (a) Expectant Weighted Value Calculating 60 圖(4.7) (b) Expectant Weighted Value Calculating 60 圖(4.8) eji之選擇 61 圖(4.9) Replaceable Target Node 62 圖(4.10) Cutting Rule 64 圖(4.11) Cutting Rule之運作 65 圖(4.12) PDM Algorithm 66 圖(4.13) Revenue-Based Dispatching Mechanism 68 圖(4.14) RDM Algorithm 69 圖(4.15) 目標物數量及行動感測器平均移動成本模擬。 75 圖(4.16) 目標物QoM值總及行動感測器平均移動成本模擬。 76 圖(4.17) 目標物數量及目標物QoM被滿足之感測器派遣時間模擬。 77 圖(4.18) 行動感測器總數及目標物QoM被滿足之感測器派遣時間模擬。 78 圖(4.19) 目標物QoM值總和及目標物QoM被滿足之感測器派遣時間模擬。 79 圖(4.20) 位於不同位置之目標物QoM被滿足之感測器派遣時間模擬。 80 圖(4.21) 場景中成功停留於不同位置之目標物的行動感測器所拜訪過的目標物個數模擬。 81 圖(4.22) 目標物QoM被滿足之感測器派遣時間及目標物數量及行動感測器數量之效能分析。 82 圖(4.23) 行動感測器花費在派遣工作上的能源成本及目標物數量及行動感測器數量之效能分析。 83 圖(4.24) 最短生命週期及目標物數量及行動感測器數量分析。 84 圖(4.25) MDM效能分析(QSD=5,TSD=50(m)) 85 圖(4.26) MDM效能分析(QSD=1,TSD=250(m)) 86 圖(4.27) MDM效能分析(QSD= 3,TSD= 150(m)) 87 表目錄 表(一) Data Collection Mechanisms模擬參數 32 表(二) Mobile Sensor Dispatching Mechanisms模擬參數 73 |
參考文獻 |
[1]M. Cardei, M. T. Thai, Y. Li, and W. Wu, “Energy-Efficient Target Coverage in Wireless Sensor Networks,” in Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM), March 2005. [2]W. Wang, V. Srinivasan, B. Wang, and K. C. Chua, “Coverage for Target Localization in Wireless Sensor Networks,” IEEE Transactions on Wireless Communications, vol. 7, no. 2, February 2008, pp. 667–676. [3]Hao Li, Huifang Miao, Li Liu, Lian Li, and Heping Zhang, “Energy Conservation in Wireless Sensor Networks and Connectivity of Graphs,” Theoretical Computer Science, ELSEVIER, vol. 393, no. 1–3, pp. 81–89, March 2008. [4]B. Y. Liu, P. Brass, O. Dousse, P. Nain, and D. Towsley, “Mobility Improves Coverage of Sensor Networks,” in Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (ACM MobiHOC), pp. 300–308, 2005. [5]C. Y. Chang, S. W. Chang, S. Y. Hsu, “A Decentralized Hole-Shape Regulation Technique for Enhancing Patrol and Deployment Tasks in Mobile WSNs.” IEEE/ACM Mobile Ad Hoc and Sensor Networks (IEEE/ACM MASS), October 2007. [6]C. Y. Chang, H. R. Chang, H. J. Liu, and S. W. Chang, “On Providing Temporal Full-Coverage by Applying Energy Efficient Hole-Movement Strategies for Mobile WSNs,” IEEE Wireless Communications and Networking Conference (IEEE WCNC), March 2007. [7]Weifang Cheng, Mo Li, Kebin Liu, Yunhao Liu, Xiangyang Li, Xiangke Liao1, “Sweep Coverage with Mobile Sensors,” IEEE International Parallel & Distributed Processing Symposium (IEEE IPDPS), 2008. [8]F.-J. Wu, C.-F. Huang, and Y.-C. Tseng, "Data Gathering by Mobile Mules in a Spatially Separated Wireless Sensor Network", Mobile Data Management, 2009 [9]Ryo Sugihara and Rajesh K. Gupta, “Optimal Speed Control of Mobile Nodeor Data Collection in Sensor Networks”, IEEE Transactions on Mobile Computing , Vol. 9, No. 1, January 2010. [10]Waleed Alsalih, Hossam Hassanein, and Selim Akl, “Routing to a Mobile Data Collector on a Predefined Trajectory”, IEEE International Communications Conference (IEEE ICC), 2009. [11]Miao Zhao and Yuanyuan Yang, “Bounded Relay Hop Mobile Data Gathering in Wireless Sensor Networks” IEEE Mobile Ad Hoc and Sensor Networks (IEEE MASS), 2009. [12]J. Hill and D. Culler, “A Wireless Embedded sensor Architecture for System-level Optimization,” Technical Report, Computer Science Department, University of California at Berkeley, 2002. [13] Waleed Alsalih, Hossam Hassanein, and Selim Akl, “Routing to a Mobile Data Collector on a Predefined Trajectory”, IEEE ICC, 2009. [14] Miao Zhao and Yuanyuan Yang, “Bounded Relay Hop Mobile Data Gathering in Wireless Sensor Networks” IEEE MASS, 2009. [15] J. Hill and D. Culler, “A Wireless Embedded sensor Architecture for System-level Optimization,” Technical Report, Computer Science Department, University of California at Berkeley, 2002. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信