請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10538
標題: | 應用於無線感測網路中之物體監控與追蹤演算法 Object Monitoring and Tracking Algorithms in Wireless Sensor Networks |
作者: | Cheng-Ta Lee 李政達 |
指導教授: | 林永松 |
關鍵字: | 無線感測網路,物體監控,入侵偵測,縱深防禦,物體追蹤,服務品質,電能效率,系統模擬,拉格蘭日鬆弛法,數學規劃,網路最佳化, wireless sensor networks,object monitoring,intrusion detection,in-depth defense,object tracking,quality of services,energy-efficiency,system simulation,Lagrangean relaxation,mathematical modeling,network optimization, |
出版年 : | 2010 |
學位: | 博士 |
摘要: | 無線感測網路(Wireless Sensor Networks, WSNs)的規劃設計上,有兩個重要的研究議題:首先是如何建構一個能滿足服務品質之應用需求的無線感測網路,第二則是如何延長無線感測網路之生命期。從應用的觀點來看,改善服務品質之需求,必須考慮無線感測網路對於應用的支援,如環境監測、物體入侵監控與物體追蹤等的能力。此外,由於感測器的電力有限,一般而言,很難再充電,故如何延長無線感測網路的生命期,也是規劃無線感測網路的重要議題。
在本論文中,我們提出物體監控與追蹤相關應用服務之演算法,首先我們發展了五個演算法,是先將問題描述為數學最佳化模型,這些都是複雜的無線感測網路規劃問題,我們採用啟發式、系統模擬與拉格蘭日鬆弛法來解決這一系列最佳化問題。此外,我們發展了一個以預測為基礎的演算法來支援物體追蹤服務。茲將每一研究主題之內容與成果簡述如下: 在邊緣監控(boundary monitoring)服務中,我們提出BMAFS與BMAMS演算法來支援該服務,BMAFS演算法是考慮在一個任意拓樸的無線感測網路中,找出監控範圍(monitoring region)之邊緣感測器節點(boundary nodes),為了滿足生命期最大化之服務品質,即以電能效率(energy efficiency)為考量,配置具有k個群(group)的無線感測網路之邊緣感測器節點,每個群輪流支援入侵監測服務。實驗結果顯示,此機制可以有效地延長無線感測網路入侵監測服務之生命期。在上述研究議題中,我們將容錯的問題考量進來, BMAMS演算法考慮當有節點故障或是節點電力耗盡時導致檢核點未被覆蓋,我們可以規劃將鄰近的節點移動覆蓋至未被覆蓋之系統檢核點(check points),使得整個網路的服務不致於中斷。 我們亦將縱深防禦(in-depth defense)的觀念加諸在上述研究議題中,亦即同時考量有縱深的監控範圍,當有入侵者進入監控範圍時,提供早期預警的功能,讓防禦者有更充裕的時間來因應,此問題並同時將整體系統的防禦率加入整個縱深防禦系統的規劃中,在此我們提出LDA與NLDA演算法來支援縱深防禦服務,LDA演算法配置具有k個群(group) 的無線感測網路之多層監控範圍節點,每個群輪流支援入侵監測服務。實驗結果顯示,此機制可以有效地延長無線感測網路入侵監測服務之生命期。此外,NLDA演算法是將一個入侵情境轉化成數學規劃問題,用以描述系統之整體防禦率與早期預警率,並且透過三階段的評估流程找出能有效地延長無線感測網路入侵監測服務之生命期之群組配置模式。此外,該法能夠用於解決具備不完美資訊特質的問題,透過適當的情境描述,加入隨機的變異性情況,使問題更貼近於真實情況,有效地提升縱深防禦系統之生命期。 在物體追蹤(object tracking)服務中,我們提出TOTA與POTA演算法來支援該服務,TOTA演算法是一個以樹為基礎(tree-based)的物體追蹤演算法,此研究的實驗結果顯示,所提演算法不但可得到高品質的解,且具有效力(effectiveness)、擴展性(scalability)與強固性(robustness)。另外,我們亦發展POTA演算法以動態預測為基礎(dynamic prediction-based)的物體追蹤演算法,此法使用喚醒較少的節點來進行物體追蹤,並利用動態預測模式來提升預測的準確性,利用此機制可以有效地延長感測網路物體追蹤服務之生命期。 由實驗結果顯示,我們所提出的六個演算法均可有效地支援物體監控與追蹤之相關應用服務。 There are two important challenges in WSNs design. One is to construct an efficient WSN for applications to guarantee desired quality of service (QoS). The other challenge is to prolong the lifetime of WSNs. From application viewpoint, the abilities of environment surveillance, object intrusion detection, and object tracking have to support the QoS. Besides, it is difficult to recharge or replace the battery for numerous sensors in the most scenarios. Therefore, how to prolong the lifetime of WSNs also becomes a key issue. In this dissertation, we focus on the network planning problem to support object monitoring and object tracking services from various perspectives. We develop five algorithms to solve optimization problems based on Lagrangean relaxation method, simulation techniques, and heuristic approaches. In addition, we develop one prediction-based algorithm based on modified Viterbi algorithm to solve object tracking problem. We present each topic briefly as follows: For boundary monitoring problem, we propose two algorithms, BMAFS and BMAMS, to support boundary monitoring services. The BMAFS is to construct boundary monitoring for grouping capabilities, and it tries to find the maximum k groups of sensors for boundary monitoring of the sensor field to prolong the system lifetime. In the test problems, the experiment results show that the proposed algorithm achieves optimality in the boundary monitoring for grouping capabilities. The BMAMS is to address the problem of boundary node relocation, and it can move previously deployed sensors to cover uncovered check points due to failure of other nodes or battery exhaustion of other nodes. The mechanism can further prolong the system lifetime. The experiment results show that the proposed BMAMS gets effectiveness in the boundary monitoring services for mobile and grouping capabilities. For in-depth defense problem, we propose two algorithms, LDA and NLDA, to support in-depth defense services. The LDA is to construct layered defense for wireless sensor networks of grouping capabilities. It tries to find the maximum k groups of sensors for layered defense of the monitoring region to prolong the system lifetime. The experiment results show that the proposed LDA gets efficiency in the layered defense for grouping capabilities. The NLDA is to construct non-layered defense of supporting different types of intruders for grouping capabilities, and it tries to find the maximum k groups of sensors for non-layered defense subject to the constraints of defense rate, early warning rate, battery capacity, intruder behaviors, and defender strategies. The NLDA can prolong the system lifetime and provide lead time alarms. The experiment results show that the proposed NLDA gets applicability and effectiveness in the non-layered defense services of supporting different types of intruders for grouping capabilities. For object tracking problem, we propose two algorithms, TOTA and POTA, to support object tracking services. The TOTA is to construct an object tracking tree for object tracking. Such tree-based algorithm can achieve energy-efficient object tracking for given arbitrary topology of sensor networks. The experiment results show that the proposed TOTA gets a near optimization in the energy-efficient object tracking. Furthermore, the algorithm is efficient and scalable in terms of the running time. The POTA is to construct a dynamic prediction-based algorithm for object tracking. Such the POTA can minimize the number of nodes participating in the tracking activities, minimize out of tracking probability, and maximize the accuracy of object predicted position. The POTA can prolong the system lifetime. The experiment results show that all six algorithms can support object monitoring and tracking services efficiently. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10538 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf | 1.42 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。