:::

詳目顯示

回上一頁
題名:應用於無線感測網路中之物體監控與追蹤演算法
作者:李政達
作者(外文):Cheng-Ta Lee
校院名稱:國立臺灣大學
系所名稱:資訊管理學研究所
指導教授:林永松
學位類別:博士
出版日期:2010
主題關鍵詞:電能效&電能效&電能效&電能效&電能效&電能效&電能效&電能效&電能效&電能效&電能效&電能效&wireless sensor networksobject monitoringintrusion detectionin-depth defenseobject trackingquality of servicesenergy-efficiencysystem simulationLagrangean relaxationmathematical modelingnetwork optimization
原始連結:連回原系統網址new window
相關次數:
  • 被引用次數被引用次數:期刊(0) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:0
  • 共同引用共同引用:0
  • 點閱點閱:30
  無線感測網路(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.
[1]I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A Survey on Wireless Sensor Network,” IEEE Communication Magazine, pp. 102-114, August 2002.new window
[2]I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless Sensor Network: A Survey,” Computer Networks, vol. 38, pp. 393-422, 2002.
[3]Z. Guo, M.C. Zhou, and G. Jiang, “Adaptive Sensor Placement and Boundary Estimation for Monitoring Mass Objects,” Part B, IEEE Transactions on Systems, Man, and Cybernetics, vol. 38, pp. 222-232, 2008.
[4]C. Zhang, Y. Zhang, and Y. Fang, “Detecting Coverage Boundary Nodes in Wireless Sensor Networks,” IEEE International Conference on Networking, Sensing and Control, pp. 868-873, 2006.
[5]J. Lian, L. Chen, K. Naik, Y. Liu, and G.B. Agnew, “Gradient Boundary Detection for Time Series Snapshot Construction in Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, 2007.
[6]Y. Wang, X. Wang, B. Xie, D. Wang, and D.P. Agrawal, “Intrusion Detection in Homogeneous and Heterogeneous Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 7, pp. 698-711, 2008.
[7]G. Li, J. He, and Y. Fu, “A Group-Based Intrusion Detection Scheme in Wireless Sensor Networks,” The 3rd International Conference on Grid and Pervasive Computing Workshop, pp. 286-291, 2008.
[8]G. Li, J. He, and Y. Fu, “A Distributed Intrusion Detection Scheme for Wireless Sensor Networks,” 28th International Conference on Distributed Computing Systems Workshops, pp. 309-314, 2008.
[9]Y. Wang, Y.K. Leow, and J. Yin, “Is Straight-line Path Always the Best for Intrusion Detection in Wireless Sensor Networks,” International Conference on Parallel and Distributed Systems (ICPADS), pp. 564-571, 2009.
[10]H.T. Kung and D. Vlah, “Efficient Location Tracking Using Sensor Networks,” IEEE Wireless Communications and Networking Conference, pp. 1954–1961, 2003.
[11]C.Y. Lin and Y.C. Tseng, “Structures for In-network Moving Object Tracking in Wireless Sensor Networks,” IEEE First International Conference on Broadband Networks,” pp. 718–727, 2004.
[12]C.Y. Lin, W.C. Peng, and Y.C. Tseng, “Efficient In-Network Moving Object Tracking in Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 5, pp. 1044-1056, 2006.
[13]Y. Xu and W.C. Lee, “On Localized Prediction for Power Efficient Object Tracking in Sensor Networks,” Proceedings of the 23rd International Conference on Distributed Computing Systems Workshops, pp. 434–439, 2003.
[14]Y. Xu, J. Winter, and W.C. Lee, “Prediction-based Strategies for Energy Saving in Object Tracking Sensor Networks,” IEEE International Conference on Mobile Data Management, pp. 346–357, 2004.
[15]Y. Xu, J. Winter, and W.C. Lee, “Dual Prediction-based Reporting for Object Tracking Sensor Networks,” The First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, pp. 154–163, 2004.
[16]Y.F. Wong, W.K.G. Seah, L.H. Ngoh, and W. C. Wong, “Sensor Traffic Patterns in Target Tracking Networks,” Wireless Communications and Networking Conference, WCNC, pp. 4123-4126, 2007.
[17]Y.C. Wang and Y.C. Tseng, “Distributed Deployment Schemes for Mobile Wireless Sensor Networks to Ensure Multi-level Coverage”, IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 9, pp. 1280–1294, 2008.
[18]K. Mechitov, S. Sundresh, G. Agha and Y. Kwon. “Cooperative Tracking with Binary-Detection Sensor Networks,” University of Illinois at Urbana-Champaign, Technical Report, UIUCDCS-R-2003-2379, 2003.
[19]T. Camp, J. Boleng, and V. Davies, “A Survey of Mobility Models for Ad Hoc Network Research,” Wireless Communication and Mobile Computing, pp. 483-502, 2002.
[20]S. P. Manh Tran and T. A. Yang, “Evaluations of Target Tracking in Wireless Sensor Networks,” Proceedings of the 37th SIGCSE Technical Symposium on Computer Science Education, pp. 97-101, 2006.
[21]“The types of power consumption of MICAz 2.4GHz,” http://www.xbow.com/Products/productdetails.aspx?sid=164.
[22]S. P. M. Tran and T. A. Yang, “OCO: Optimized Communication & Organization for Target Tracking in Wireless Sensor Networks,” IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, pp. 428-435, 2006.
[23]P. K. Sahoo, K.-Y. Hsieh, and J.-P. Sheu, “Boundary Node Selection and Target Detection in Wireless Sensor Network,” IFIP International Conference on Wireless and Optical Communications Networks, pp. 1-5, 2007.
[24]P.L. Chiu and F.Y.S. Lin, “Sensor Deployment Algorithms for Target Positioning Services,” Doctoral Thesis, Graduate Institute of Information Management of National Taiwan University, 2007.
[25]S. Bhatti and J. Xu, “Survey of Target Tracking Protocols Using Wireless Sensor Network,” Fifth International Conference on Wireless and Mobile Communications, pp. 110–115, 2009.
[26]F.Y.S. Lin, H.H. Yen, and S.P. Lin, “A Novel Energy-Efficient MAC Aware Data Aggregation Routing in Wireless Sensor Networks,” Sensors, pp. 1295-2147, March, 2009.
[27]F.Y.S. Lin, H.H. Yen, and S.P. Lin, “Delay QoS and MAC Aware Energy-Efficient Data-Aggregation Routing in Wireless Sensor Networks,” Sensors, vol. 9, pp. 7711-7732, October, 2009.
[28]Y.F. Wen, F.Y.S. Lin, and W.C. Kuo, “A Tree-based Energy-efficient Algorithm for Data-Centric Wireless Sensor Networks,” 21st International Conference on Advanced Networking and Applications, pp. 202–209, 2007.
[29]C.T. Lee and F.Y.S. Lin, “An Energy-Efficient Lagrangean Relaxation-based Object Tracking Algorithm in Wireless Sensor Networks,” 20th International Conference on Information Management (ICIM), 2009.
[30]C.T. Lee, F.Y.S. Lin, and Y.F. Wen, “An Efficient Object Tracking Algorithm in Wireless Sensor Networks,” 9th Joint Conference on Information Sciences (JCIS) (9th International Conference on. Computer Science and Informatics), 2006.
[31]B.H. Liu, W.C. Ke, C.H. Tsai, and M.J. Tsai, “Constructing a Message-Pruning Tree with Minimum Cost for Tracking Moving Objects in Wireless Sensor Networks Is NP-Complete and an Enhanced Data Aggregation Structure,” IEEE Transactions on Computers, vol. 57, pp. 849-863, 2008.
[32]M.L. Fisher, “The Lagrangean Relaxation Method for Solving Integer Programming Problem,” Management Science, vol. 27, pp. 1-18, 1981.
[33]M.L. Fisher, “An Applications Oriented Guide to Lagrangian Relaxation,” Interfaces, vol. 15, pp. 10-21, 1985.
[34]R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, “Network Flows: Theory, Algorithm, and Applications,” chapter 16, Prentice Hall, 1993.
[35]S. Meguerdichian and M. Potkonjak, “Low Power 0/1 Coverage and Scheduling Techniques in Sensor Networks,” UCLA Technical Reports 030001, January 2003.new window
[36]G. Wang, G. Cao, T. L. Porta, and W. Zhang, “Sensor Relocation in Mobile Sensor Networks,” IEEE INFOCOM, vol. 4, pp. 2302-2312, March 2005.
[37]Y. Yoo and D.P. Agrawal, “Mobile Sensor Relocation to Prolong the Lifetime of Wireless Sensor Networks,” Vehicular Technology Conference, 2008. VTC Spring 2008. IEEE, pp. 193-197, 2008.
[38]R. Perry, A. Vaddiraju, K. Buckley, “Multitarget List Viterbi Tracking Algorithm,” Department of Electrical and Computer Engineering, Villanova University.
[39]Y.F. Wong, et al., “Sensor Traffic Patterns in Target Tracking Networks,” Wireless Communications and Networking Conference, WCNC, pp. 4123-4126 2007.
[40]Y. Zhu and A. Shareef, “Comparisons of Three Kalman Filter Tracking Algorithms in Sensor Network,” Proceedings of the 2006 International Workshop on Networking, Architecture, and Storages, pp. 61-62, 2006.
[41]P. Zeng, et al., “Bounding the Lifetime of Target Tracking Sensor Networks,” IEEE International Conference on ICC, pp. 3444-3449, 2006.
[42]O. Dousse, et al., “Delay of Intrusion Detection in Wireless Sensor Networks,” The Proceedings of the Seventh ACM International Symposium on Mobile Ad Hoc Networking and Computing, Florence, Italy, 2006.
[43]Y. Li and Y.H. Liu, “Energy Saving Target Tracking Using Mobile Sensor Networks,” IEEE International Conference on Robotics and Automation, pp. 3653-3658, 2007.
[44]C.Y. Lin, Y.C. Tseng, and T.H. Lai, “Message-Efficient In-Network Location Management in a Multi-sink Wireless Sensor Network,” Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, pp. 496-505, 2006.
[45]F.Y.S. Lin and Y.F. Wen, “Multi-sink Data Aggregation Routing and Scheduling with Dynamic Radii in WSNs,” IEEE Communications Letters, vol. 10, pp. 692-694, 2006.
[46]Y. Yang and M. Cardei, “Movement-assisted Sensor Redeployment Scheme for Network Lifetime Increase,” The Proceedings of the 10th ACM Symposium on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, Chania, Crete Island, Greece, 2007.
[47]W. Liang and Y. Liu, “Online Data Gathering for Maximizing Network Lifetime in Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 6, pp. 2-11, 2007.
[48]C. Schurgers, et al., “Optimizing Sensor Networks in The Energy-latency-density Design Space,” IEEE Transactions on Mobile Computing, vol. 1, pp. 70-80, 2002.new window
[49]E. L. Lloyd and G. Xue, “Relay Node Placement in Wireless Sensor Networks,” IEEE Transactions on Computers, vol. 56, pp. 134-138, 2007.
[50]A.S. Chhetri, et al., “Sensor Resource Allocation for Tracking Using Outer Approximation,” IEEE Signal Processing Letters, vol. 14, pp. 213-216, 2007.
[51]J. Li and X. Liu, “Survivability for Wireless Sensor Network Model, Evaluation and Experiment,” Fifth International Joint Conference on INC, IMS and IDC, pp. 1513-1516, 2009.
[52]H. Yang and B. Sikdar, “A Protocol for Tracking Mobile Targets Using Sensor Networks,” Proceedings of IEEE Workshop on Sensor Network Protocols and Application, pp. 71-81, 2003.
[53]H. Perros, “Computer Simulation Techniques: The Definitive Introduction,” chapter 1, 2009.new window
[54]F.S. Hillier and G.J. Lieberman, “Introduction to Operations Research,” fifth edition, chapter 23, McGraw-Hill, 1990.
[55]S. Megerian, F. Koushanfar, M. Potkonjak, and M.B. Srivastava, “Worst and Best-Case Coverage in Sensor Networks,” IEEE Transactions on Mobile Computing, pp. 84-92, 2005.
[56]“The specification of RPS-326,” http://migatron.com/products/rps-326/rps-326.pdf.
[57]M. Lu, J. Wu, M. Cardei, and M. Li, “Energy-efficient Connected Coverage of Discrete Targets in Wireless Sensor Networks,” Proceedings of 3rd International Conference Networking and Mobile Computing, ICCNMC, LNCS, vol. 3619. Springer, Heidelberg, pp. 43-52, 2005.
[58]A. Dhawan, C.T. Vu, A. Zelikovsky, Y. Li, and S. K. Prasad, “Maximum Lifetime of Sensor Networks with Adjustable Sensing Range,” Proceedings of the Seventh ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel Distributed Computing, 2006.
[59]C.T. Lee and F.Y.S. Lin, “Boundary Monitoring Algorithms for Wireless Sensor Networks of Grouping Capabilities,” IEEE International Conference on Wireless Communications, Networking and Information Security (WCNIS), Vol. 2, pp. 461-467, 2010.
[60]F.Y.S. Lin, C.T. Lee, and Y.Y. Hsu, “An Energy-Efficient Algorithm for Object Tracking in Wireless Sensor Networks,” IEEE International Conference on Wireless Communications, Networking and Information Security (WCNIS), Vol. 2, pp. 424-430, 2010.
[61]C.T. Lee, F.Y.S. Lin, and Y.S. Wang, “Maximizing the Lifetime of Layered Defense in Wireless Sensor Networks,” IEEE Asia Pacific Wireless Communications Symposium (APWCS), 2010.
[62]C. Mascolo and M. Musolesi, “SCAR: Contextaware Adaptive Routing in Delay Tolerant Mobile Sensor Networks,” Proceedings of the International Conference on Wireless Communications and Mobile Computing (IWCMC), 2006.
[63]B. Amutha and M. Ponnavaikko, “Energy Efficient Hidden Markov Model Based Target Tracking Mechanism in Wireless Sensor Networks,” Journal of Computer Science, vol. 5, no. 12, pp.1085-1093, 2009.
[64]J. Cartigny, D. Simplot, and I. Stojmenovic, “Localized Minimum-energy Broadcasting in Ad-hoc Networks,” IEEE Infocom, pp. 2210-2217, 2003.
[65]R. L. Keeney and H. Raiffa, “Decisions with Multiple Objectives: Preference and Value Tradeoffs,” Wiley, 1976.
[66]M. Vemula, M. F. Bugallo, and P. M. Djuric, “Target Tracking in a Two-tiered Hierarchical Sensor Network,” Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, vol. 4, pp. 969–972, 2006.
[67]J.B.D. Cabrera, C. Gutierrez, and R.K. Mehra, “Infrastructures and Algorithms for Distributed Anomaly-based Intrusion Detection in Mobile Ad-hoc Networks,” IEEE Conference on Military Communications (MILCOM), pp. 1831-1837, 2005.
[68]W. Chen, J. C. Hou, and L. Sha, “Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks,” International Conference on Network Protocols, pp. 284-294, 2003.
[69]S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. “Coverage Problems in Wireless Ad-hoc Sensor Networks,” INFOCOM, pp. 1380-1387, 2001.
[70]A. Savvides, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, “Location Discovery in Ad-hoc Wireless Sensor Networks,” unpublished, UCLA EE and CS Departments.
[71]D. P. Bertsekas, “Dynamic Programming and Optimal Control,” chapter 6, Athena Scientific, 2010.
[72]A. Wang, S-H. Cho, C.G. Sodini, and A.P. Chandrakasan, “Energy-efficient Modulation and MAC for Asymmetric Microsensor Systems,” Proceedings of ISLPED, pp 106-111, 2001.
[73]V. Tsiatsis, S. Zimbeck, and M. Srivastava, “Architectural Strategies for Energy Efficient Packet Forwarding in Wireless Sensor Networks,” Proceedings of ISLPED, pp. 92-95, 2001.
[74]I. Demirkol, C. Ersoy, F. Alagoz, “MAC Protocols for Wireless Sensor Networks: A Survey,” IEEE Communication Magazine, vol. 44, no. 4, pp. 115–121, 2006.
[75]J. N. Al-Karaki and A. E. Kamal. “Routing Techniques in Wireless Sensor Net works: a Survey,” IEEE Transactions on Wireless Communications, vol. 11, no. 6, pp. 6-28, 2004.
[76]J. Cheng, M. Xie, R. Chen, and F. Roberts, “A Mobile Sensor Network for the Surveillance of Nuclear Materials in Metropolitan Areas,” DIMACS Technical Report, Rutgers University, 2009.
[77]R. C. Chen, C. F. Hsieh, Y. F. Huang, “An Isolation Intrusion Detection System for Hierarchical Wireless Sensor Networks,” Journal of Networks, vol 5, no 3, 2010.
[78]Y. C. Wang and Y. C. Tseng, “Intentional mobility in wireless sensor networks,” chapter 1, Wireless Networks: Research, Technology, and Applications, 2009.new window


 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top