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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2906201020085500
中文論文名稱 行動感測網路中目標物覆蓋之具時效性資料收集與感測器派遣機制
英文論文名稱 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 Engineering
學年度 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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2015-07-01公開。
  • 同意授權瀏覽/列印電子全文服務,於2015-07-01起公開。


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