臺灣博碩士論文加值系統

本論文針對無線感測網路的動態維護，提出一個以密度控制為基礎的演算法。每個回合中，感測器以附近區域資訊建構多角形來引導移動方向及距離，並且同時兼顧節點密度的控制。模擬結果顯示，所提出的演算法在覆蓋率、收斂時間、能量消耗、密度測量、終止時間和變換通訊範圍的影響等方面均具備較佳的效能。

In this thesis, we propose an efficient dynamic maintenance algorithm not only for recovering the coverage holes and also for balancing the node density in wireless sensor networks. For each sensor node, a polygon can be constructed with limited local information to determine the moving direction and distance in each iteration. Simulation results reveal that the proposed mechanism performs better than other maintenance algorithms in terms of coverage, convergence, energy consumption, density measures, termination and impacts of communication range.

1. Introduction 1
1.1 Background and Motivation 1
1.2 Scope of the Work 3
1.3 Thesis Organization 3
2. System Model 4
2.1 Coverage Hole 4
2.2 Density Control Polygon 5
3. Density Control-based Dynamic Maintenance Algorithm (DCMA) 8
3.1 Proposed Algorithm 8
3.1.1 Construction Phase 8
3.1.2 Moving Phase 10
3.2 Oscillation Control 12
4. Performance Evaluation 14
4.1 Environment Setup 14
4.2 Simulation Results 14
4.2.1 Coverage 14
4.2.2 Convergence 15
4.2.3 Energy Consumption 16
4.2.4 Density Measures 18
4.2.5 Termination 18
4.2.6 Impacts of Communication range 19
5. Conclusions 21
5.1 Contributions 21
5.2 Future Directions 22
Bibliography 23

[Aky 02]I. F. Akyildiz and W. Su, Y. Sankarasubramaniam, and E. Cayirci,"A Survey on Sensor Networks," IEEE Communications Magazine, vol. 40, issue 8, pp. 102-114 August 2002.
[Ahm 05]N. Ahmed, S. S. Kanhere and S. Jha, "The Holes Problem in Wireless Sensor Networks: A survey," ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9, issue 2, pp.4-18, April 2005.
[Card 05]M.Cardei and D. Du, "Improving wireless sensor network lifetime through power-aware organization," ACM Wireless Networks, vol. 11, issue 3, pp.333-340 May 2005.
[Cheng 05]M. Cheng, L. Ruan and W. Wu, "Achieving minimum coverage breach under bandwidth constraints in wireless sensor networks," Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2005.
[Corke 07]P. Corke, R. Peterson and D. Rus, "Finding Holes in Sensor Networks," Proc. of the Workshop on Omniscient Space: Robot Control Architecture Geared toward Adapting to Dynamic Environments at ICRA 2007, April, 2007.
[DS CC24]Data Sheet for CC2420 2.4GHz IEEE 802.15.4/Zig Bee RF transceiver, http:// www.chipcon.com/files/CC2420_Data_Sheet_1_2.pdf.
[Gan 04]S. Ganeriwal, A. Kansal, and M. B. Srivastava, "Self aware actuation for fault repair in sensor networks," Proc. IEEE International Conference on Robotics and Automation, vol 5, pp. 5244-5249, Spain, May, 2004.
[Heo 05]Nojeong Heo and P.K. Varshney, "Energy-efficient deployment of Intelligent Mobile sensor networks," IEEE Transactions on Systems, Man and Cybernetics,vol.35, no.1, pp. 78-92, Jan. 2005
[How 02]A. Howard, M. J. Mataric and G. S. Sukhatme, "Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem," Proceedings of the 6th International Symposium on Distributed Autonomous Robotics Systems (DARS02)
, pp.299-308, Japan, June 25-27, 2002
[Hsin 06]Chin-fan Hsin and Mingyan Liu, "Randomly duty-cycled wireless sensor net-works: dynamics of coverage," IEEE Transactions on Wireless Communications, 2006.
[Huang 03]C. F. Huang and Y. C. Tseng, "The Coverage Problems in a Wireless Sensor Network," Porc. of the International Conference on Wireless Sensor Networks and Applications, 2003.
[Liu 08]C. Y. Liu, Remote Holes Detection Algorithms for Wireless Sensor Networks, Master Thesis, Yuan Ze University, Taiwan, 2009.
[Megi 83]N. Megiddo, "Linear-Time Algorithms for Linear Programming in R3 and Related Problems," SIAM J. Computing, vol. 12, pp. 759-776, 1983.
[Peri 03]M.Perillo and W. Heinzelman, "Optimal sensor management under energy and reliability constraints," Pro. of the IEEE Conference on Wireless Communications and Networking, March 2003.
[Sahoo 07]P. K. Sahoo, J. P. Sheu, and W. S. Lin, "Dynamic Coverage and Connectivity Maintenance Algorithm for Wireless Sensor Networks," Proc. of the International Conference on Communication Systems Software and Middleware (COMSWARE), pp. 1-9,January 2007.
[Sek 05]A. Sekhar, B. S. Manoj, and C. Siva Ram Murthy, "Dynamic Coverage Maintenance Algorithms for Sensor Networks with Limited Mobility," Proc. of the International Conference on Pervasive Computing and Communications (PerCom), pp. 51-60, March 2005.
[Sky 91]S. Skyum, "A Simple Algorithm for Computing the Smallest Enclosing Circle," Information Processing Letters, vol. 37, pp. 121-125, 1991.
[Wan 06]P.J. Wan, and C.W. Yi, "Coverage by randomly deployed wireless sensor networks," IEEE Transactions on Information Theory, pp.2658-2669, 2006.
[Wang 06]G. Wang, G. Cao, and T. L. Porta, "Movement-assisted sensor deployment," IEEE Transactions on Mobile Computing, Volume 5, Issue 6, pp. 640-652, Junly, 2006.
[Wel 91]E. Welzl, "Smallest Enclosing Disk (Balls and Ellipsoids)," New Results and New Trends in Computer Science, pp. 359-370, 1991.
[Yang 09]H. J. Yang, Grid-Based Dynamic Maintenance Algorithm for Sensor Networks with Limited Mobility, Master Thesis, Yuan Ze University, Taiwan, 2009.