簡易檢索 / 詳目顯示

回結果列表
研究生： 郭宏恩
Kuo, Hung-En
論文名稱： 在指向性感測網路中使用目標視景分群演算法達成多重覆蓋
Using Target-View Segmentation Algorithm to Achieve Target Multi-Coverage in Directional Sensor Networks
指導教授： 斯國峰
Ssu, Kuo-Feng
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電腦與通信工程研究所
Institute of Computer & Communication Engineering
論文出版年： 2008
畢業學年度： 96
語文別： 英文
論文頁數： 38
中文關鍵詞： 指向性感測器 、覆蓋 、分群
外文關鍵詞： schedule, segment, wireless sensor network, directional sensor, coverage
相關次數： 點閱：68  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 指向性感測器將感測區域集中在一個固定角度內，因此與全向性感測器相比，更適合用在目標監測及精確資料感測。為了達到某些應用需求，必須將目標區分為多種覆蓋程度，使需要較高覆蓋程度的目標能隨時被較多的感測器所覆蓋。由於感測器的能量有限，如何選擇最少的感測器使最多目標被多重覆蓋是個重要的問題，也就是目標多重覆蓋問題。本篇論文證明此問題為NP完備，並提出一種啟發式演算法，稱為目標視景分群演算法。該演算法以分群為基礎來處理多重覆蓋的變化，能減少需要活動的感測器數量，並考慮剩餘電量來延長網路生命週期。模擬結果驗證該演算法對於覆蓋的變化有良好適應，並減少了需要活動的感測器數量，明顯地延長了網路生命週期。

    Compared to isotropic sensors, directional sensors concentrate their sensing fields with a fixed angle, which is more suitable for target monitoring and accurate data sensing. For some application requirements, targets are necessarily classified into many coverage levels. Targets with higher coverage level should be covered by more sensors in any time. Due to limited power of sensors, how to reduce the number of active sensors to satisfy multi-coverage of maximum targets becomes an important problem, addressed as the target multi-coverage problem. A Target-View Segmentation Algorithm (TVSA), a heuristic solution, is also described. TVSA uses a group-based approach to handling the multi-coverage variation for reducing the number of needed active sensors. Residual power is also considered by TVSA to extend the network lifetime. Simulation results verify that TVSA not only adapts well to coverage variation, but decreases the number of active sensors and prolongs the network lifetime.

    Chapter 1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 2 Related Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 3 Target Multi-Coverage (TMC) Problem : : : : : : : : : : : : : : : : : : 7 3.1 Directional Sensor Network Model . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Target Multi-Coverage (TMC) Problem . . . . . . . . . . . . . . . . . . . 9 4 Target-View Concept : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 4.1 Target-View Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 View-Selection with Target Condition . . . . . . . . . . . . . . . . . . . . 12 4.2.1 Normal condition . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2.2 Critical condition . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2.3 Unsatisfied condition . . . . . . . . . . . . . . . . . . . . . . . . . 13 5 Target-View Segmentation Algorithm (TVSA) : : : : : : : : : : : : : : 16 5.1 Phase 0: Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2 Phase 1: Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.3 Phase 2: View-Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.4 Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6 Performance Evaluation : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22 6.1 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.2.1 Segment Range Parameter D . . . . . . . . . . . . . . . . . . . . 23 6.2.2 Data Gathering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 6.2.3 Network Lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.2.4 Coverage Variation . . . . . . . . . . . . . . . . . . . . . . . . . . 31 7 Conclusion and Future Work : : : : : : : : : : : : : : : : : : : : : : : : : 33 7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 References : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35 Vita : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 38

    [1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102–114, August 2002.
    [2] J. Carle and D. Simplot-Ryl, “Energy-efficient area monitoring for sensor networks,” IEEE Computer, vol. 37, no. 2, pp. 40–46, February 2004.
    [3] P. Lehne and M. Pettersen, “An overview of smart antenna technology for mobile communications systems,” IEEE Communications Surveys, vol. 2, no. 4, pp. 2–13, November 1999.
    [4] F. Dai and J. Wu, “Efficient broadcasting in ad hoc wireless networks using directional antennas,” IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 4, pp. 335–347, April 2006.
    [5] R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, and D. Culler, “An analysis of a large scale habitat monitoring application,” in 2nd International Conference on Embedded Networked Sensor Systems (SenSys), Helsinki, Finland, November 2004, pp. 214–226.
    [6] M. Rahimi, R. Baer, O. I. Iroezi, J. C. Garcia, J. Warrior, and D. Estrin, “In situ image sensing and interpretation in wireless sensor networks,” in 3rd International Conference on Embedded Networked Sensor Systems (SenSys), San Diego, California, United States, November 2005, pp. 192–204.
    [7] J. Djugash, S. Singh, G. Kantor, and W. Zhang, “Range-only slam for robots operating cooperatively with sensor networks,” in IEEE International Conference on Robotics and Automation (ICRA), Orlando, Florida, United States, May 2006, pp. 2078 – 2084.
    [8] L. Wang and Y. Xiao, “A Survey of Energy-Efficient Scheduling Mechanisms in Sensor Networks,” Mobile Networks and Applications, vol. 11, no. 5, pp. 723–740, October 2006.
    [9] S. Slijepcevic and M. Potkonjak, “Power efficient organization of wireless sensor networks,” in IEEE International Conference on Communications (ICC), vol. 2, Helsinki, Finland, June 2001, pp. 472–476.
    [10] D. Tian and N. D. Georganas, “A coverage-preserving node scheduling scheme for large wireless sensor networks,” in ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), Baltimore, MD, United States, September 2002, pp. 32–41.
    [11] X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated coverage and connectivity configuration in wireless sensor networks,” in First International Conference on Embedded Networked Sensor Systems (SenSys), Los Angeles, CA, United States, November 2003, pp. 28–39.
    [12] M. Cardei, M. T. Thai, Y. Li, , and W. Wu, “Energy-efficient target coverage in wireless sensor networks,” in Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), vol. 3, Miami, FL, United States, March 2005, pp. 1976–1984.
    [13] Y. Cai, W. Lou, M. Li, and X. Li, “Target-oriented scheduling in directional sensor networks,” in Proceedings of 26th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Anchorage, AK, United States, May 2007, pp. 1550–1558.
    [14] J. Ai and A. A. Abouzeid, “Coverage by directional sensors in randomly deployed wireless sensor networks,” Journal of Combinational Optimization, vol. 11, no. 1, pp. 21–41, Feburary 2006.
    [15] B. Krishnamachari, D. Estrin, and S. Wicker, “The impact of data aggregation in wireless sensor networks,” in Proceedings of the 22nd International Conference on Distributed Computing Systems Workshops, Vienna, Austria, July 2002, pp. 575– 578.
    [16] J. Heidemann, F. Silva, C. Intanagonwiwat, R. Govindan, D. Estrin, and D. Ganesan, “Building efficient wireless sensor networks with low-level naming,” in 18th ACM Symposium on Operating Systems Principles, Banff, Alberta, Canada, October 2001, pp. 146–159.
    [17] R. R. Brooks and S. S. Iyengar, Multi-sensor fusion: fundamentals and applications with software. Upper Saddle River, NJ, United States: Prentice Hall, 1998, pp. 94–143.
    [18] B. Karp and H. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,” in Proceedings of the 6th annual international conference on Mobile computing and networking, Boston, Massachusetts, United States, August 2000, pp. 243–254.
    [19] M. Cardei and J. Wu, “Energy-efficient coverage problems in wireless ad-hoc sensor networks,” Computer Communications, vol. 29, no. 4, pp. 413–420, Febrary 2006.
    [20] C. Huang and Y. Tseng, “A survey of solutions to the coverage problems in wireless sensor networks,” Journal of Internet Technology, vol. 6, no. 1, pp. 1–8, March 2005.
    [21] S. Yang, F. Dai, M. Cardei, and F. P. J. Wu, “On connected multiple point coverage in wireless sensor networks,” International Journal of Wireless Information Networks, vol. 13, no. 4, pp. 289–301, October 2006.
    [22] R. M. Karp, Complexity of Computer Computations. New York, United States: Plenum Press, 1972.
    [23] D. S. Hochbaum, Approximation algorithms for NP-hard problems. New York, United States: PWS, 1996.
    [24] M. Cardei and D. Du, “Improving wireless sensor network lifetime through power aware organization,” ACM Wireless Networks, vol. 11, no. 3, pp. 333–340, May 2005.

    下載圖示 校內：2011-06-06公開
    校外：2013-06-06公開
    QR CODE