[[alternative]]Patrolling mechanisms for distributed targets in mobile wireless sensor networks

碩士[[abstract]]目標物覆蓋(Target Coverage)問題在無線感測網路中一直受到廣泛的討論，然而，在過去的研究中，大都假設目標物間相互連結，但在實際的環境中，目標物可能分散於許多不連續區域中，導致過去的研究無法達到理想的目標。本論文提出一Distributed Partitioning and Cooperating Mechanism for Target Patrolling Tasks in Disconnected Wireless Sensor Networks機制，考慮目標物(Target Points)分散於許多不連續區域的場景，針對多個行動資料收集站(Mobile Sink)之移動路徑進行分工與規劃，使Mobile Sinks能利用最有效率的巡邏收集分散於網路中的目標物資訊，此外，為了避免Mobile Sink工作量的不平衡，本論文依據巡邏迴圈效率以及Mobile Sink數量將目標物群組化以及平衡Mobile Sinks之配置，除了於目標物群組內建置有效率的目標物巡邏迴圈外，亦根據目標物間不同的距離及權重適當的調整Mobile Sink之速度，使目標物擁有固定的監控資訊更新週期，並藉此達到降低移動成本及穩定的資料取樣頻率。[[abstract]]Target coverage problem has been one of the most widely dicussed issues in Wireless Sensor Networks(WSNs). Most of the previous researches assume that target points are near to each other and can be easily connected. However, in the actual enviroments, target points may be scattered in several disconnected areas. This paper proposes a Distributed Partitioning and Cooperating Mechanism(DPCM) for patrolling the target points which might be scattered in several disconnected areas. The proposed DPCM partitions the targets that are far away with each other into different groups, constructs a path for each group as well as allocates mobile sinks to the constructed paths. The contributions of the proposed DPCM is that the overall length of the constructed paths can be as short as possible and the workload of each mobile sink can be balanced. In addition, each mobile sink further controls its speed such that the user defined patrolling frequency for each target can be satisfied. Performance studies reveal that the proposed DPCM outperforms existing works in terms of the decreasing the Mobile Sink’s workload, shorten the target point’s monitoring interval and reduce the total monitoring length.[[tableofcontents]]目錄 目錄 IV 圖目錄 VI 表目錄 VIII 第一章 簡介 1 1.1. 研究背景 1 1.2. 論文架構 5 第二章 國內外相關研究 6 2.1. Connected Wireless Sensor Networks 6 2.2. Isolated Wireless Sensor Networks 8 2.3. Target Sweep Coverage in Wireless Mobile Sink Networks 9 第三章 目標物分群機制 13 3.1. 網路環境設定 14 3.2. 問題描述 15 3.3. Patrolling Tasks Phase (PTP) 18 3.4. Mobile Sink Distribution Phase 26 3.5. Speed Control Phase 29 3.6. 效能評估 34 3.6.1. Simulation Model 34 3.6.2. Performance Study 35 第四章 異質性網路建置路徑機制 48 4.1. 網路環境與問題描述 49 4.1.1. 網路環境 49 4.1.2. 問題描述 51 4.2. An efficient Target Patrolling for Heterogeneous Mobile WSNs 54 4.2.1. Target Selection Phase 54 4.2.2. Patrolling Path Construction 60 4.3. 效能評估 64 4.3.1. Simulation Model 64 4.3.2. Performance Study 65 第五章 結論 75 5.1. 結論 75 參考文獻 77 附錄 英文論文 80 圖目錄 圖 一 、同質網路環境 15 圖 二 、Targets Partition 19 圖 三 、Pseudo code of Targets Partition 25 圖 四 、Mobile Sink distribution 28 圖 五 、Pseudo code of Mobile Sinks allocation 29 圖 六 、行動感測網路中目標物覆蓋演算法之SDT比較 37 圖 七 、行動感測網路中目標物覆蓋演算法之SD比較 38 圖 八 、行動感測網路中巡邏迴圈建置長度的比較 39 圖 九 、行動感測網路中使用者要求目標物監控時間的差距比較 40 圖 十 、行動感測網路中使用者要求目標物監控時間的電量消耗情形 41 圖 十一 、行動感測器之能源使用效率比較 43 圖 十二 、行動感測網路中使用者要求目標物監控時間的差距比較 44 圖 十三 、行動感測網路中使用者要求目標物監控時間的電量消耗比較 45 圖 十四 、行動感測網路中初始速度與監控目標物的完整性比較 46 圖 十五 、行動感測網路中分群個數的SDT比較 47 圖 十六 、異質網路環境 50 圖 十七 、異質性行動感測網路中監控迴圈建置長度的比較 67 圖 十八 、異質性行動感測網路中監控迴圈建置長度與異質行動感測器數量的關係圖 68 圖 十九 、異質性行動感測網路中監控迴圈建置長度與目標物個數的關係圖 69 圖 二十 、異質行動感測器的個數與目標物被監控的需求變化下的目標物需求被滿足的百分比 70 圖 二十一 、異質感測網路中目標物需求百分比與異質行動感測器的電量消耗關係圖 71 圖 二十二 、異質感測網路中目標物對感測元件的需求百分比對平均監控路徑長度的影響 72 圖 二十三 、異質網路中模擬場景的大小對目標物需求被滿足的百分比其影響程度 73 圖 二十四 、異質網路中異質行動感測器數量與執行時間對目標物需求被滿足的百分比其影響程度 74 表目錄 表 一 、本論文模擬參數 34 表 二 、異質性網路符號列表 51 表 三 、本論文模擬參數 64[[note]]學號: 699410493, 學年度: 10