臺灣博碩士論文加值系統

在無線感測網路中，感測器可能因為電力失效、不平均初始佈置，或某些特殊事件而產生覆蓋漏洞。但是在大部份的情況，感測區域裡都還擁有足夠的感測器，感測器只需在有限的移動距離下移動到新的位置來達到需求的覆蓋率。
本篇論文裡，我們提出一個以網格為基礎的動態維護演算法。感測器利用鄰近的網格資訊，計算移動距離和方向來填補覆蓋漏洞。模擬結果顯示，我們的動態維護演算法在消耗電量和覆蓋率上都比其他方法還要好，並且可以應用在不同形狀的網格上。

Coverage holes in wireless sensor network, could occur due to unexpected failure, initial uneven deployment, and certain special event. But, most of time, they are still enough sensors to provide the requested coverage by moving some sensor to new location with limited distance.
In this thesis, we propose a grid-based algorithm for dynamic maintenance in wireless sensor network. The movement of each sensor is decided autonomously on the basis of limited local information. Sensor uses the information from neighboring grids to first uncover the coverage hole, and then to determine the moving direction and distance for recovering the coverage holes. Simulation results show that the proposed algorithm performs better than other method in terms of energy efficient, better coverage and can be use on different shapes of grid.

1 Introduction........1
1.1 Background and Motivation．．．．．．．．1
1.2 Scope of the Work．．．．．．．．．．．．．．．．．．．．3
1.3 Thesis Organization．．．．．．．．．．4
2 System Model........5
2.1 Definitions．．．．．．．．．．．．．．5
2.2 Estimation of Intersection Point with Grid (IPG)．．7
2.3 Estimation of Intersection Points with Sensing Disk of Other Sensor Nodes (IPN)．．．．．．．．．．．．．．．．．．．8
3 Grid-based Dynamic Maintenance Algorithm......10
3.1 Neighbor Discovery．．．．．．．．．．．．．10
3.2 Grid-based Hole Detection．．．．．．．．．11
3.3 Distributed Dynamic Maintenance．．．．．．13
4 Performance Valuation........17
4.1 Simulation Setup．．．．．．．．．．．．．17
4.2 Simulation Results．．．．．．．．．．．18
4.2.1 Coverage．．．．．．．．．．．．．．．．18
4.2.2 Energy Consumption．．．．．．．．．．．20
4.2.3 Termination．．．．．．．．．．．．．．23
4.2.4 Different Shapes of Grid．．．．．．．．24
5 Conclusion.......29
5.1 Contributions．．．．．．．．．．．．．．29
5.2 Future Directions．．．．．．．．．．．30
Bibliography．．．．．．．．．．．．．．．．31

[ Akyildiz 02]I. F. Akyildiz, S. Weilian, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Communications Magazine, vol. 40, pp. 102-14, 2002.
[Bai 06]X. Bai, S. Kumar, D. Xuan, Z. Yun, and T. H. Lai, "Deploying wireless sensors to achieve both coverage and connectivity," Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing Florence, Italy: ACM, 2006.
[Chakrabarty 02]K. Chakrabarty, S. S. Iyengar, Q. Hairong, and C. Eungchun, "Grid coverage for surveillance and target location in distributed sensor networks," IEEE Transactions on Computers, vol. 51, pp. 1448-1453, 2002.
[DS 2400]Data sheet for Crossbow wireless sensor networks radio module: MPR2400-MICAz ZigBee series.
[DS 2420]Data sheet for CC2420 2.4GHz IEEE 802.15.4/ZigBee RF transceiver.
[Gupta 06]H. Gupta, Z. Zongheng, S. R. Das, and Q. Gu, "Connected sensor cover: self-organization of sensor networks for efficient query execution," IEEE/ACM Transactions on Networking, vol. 14, pp. 55-67, 2006.
[Huang 05]C.-F. Huang and Y.-C. Tseng, "A survey of solutions to the coverage problems in wireless sensor networks," Journal of Internet Technology, vol. 6, pp. 1-8, 2005.
[Jiang 04] J. Jiang and W. Dou, "A Coverage-Preserving Density Control Algorithm for Wireless Sensor Networks," in Ad-Hoc, Mobile, and Wireless Networks, 2004, pp. 631-631.
[Lin 09]W. Z. Lin and R. Lai, Dynamic Multi-hop Maintenance for Sensor Networks with Limited Mobility, Master Thesis, Yuan Ze University, Taiwan, 2009.
[Megiddo 82]N. Megiddo, "Linear-time algorithms for linear programming in R3 and related problems," Proceedings of the 23rd Annual Symposium on Foundations of Computer Science: IEEE Computer Society, 1982.
[Mhatre 04]V. Mhatre and C. Rosenberg, "Design guidelines for wireless sensor networks: Communication, clustering and aggregation," Ad Hoc Networks, vol. 2, pp. 45-63, 2004.
[Nojeong 05] H. Nojeong and P. K. Varshney, "Energy-efficient deployment of Intelligent Mobile sensor networks," Systems, Man and Cybernetics, Part A:IEEE Transactions on Systems and Humans, vol. 35, pp. 78-92, 2005.
[Sack 00]J. R. Sack and J. Urrutia, Headbook of computational geometry, 1st ed. Amsterdam ; New York: Elsevier, 2000.
[Sahoo 07]P. K. Sahoo, S. Jang-Ping, and L. Wei-Shin, "Dynamic Coverage and Connectivity Maintenance Algorithms for Wireless Sensor Networks," International Conference on Communication Systems Software and Middleware, 2007. COMSWARE 2007, pp. 1-9.
[Sekhar 05]A. Sekhar, B. S. Manoj, and C. S. R. Murthy, "Dynamic coverage maintenance algorithms for sensor networks with limited mobility," Los Alamitos, CA, USA, 2005, pp. 51-60.
[Skyum 91]S. Skyum, "Simple algorithm for computing the smallest enclosing circle," Information Processing Letters, vol. 37, pp. 121-125, 1991.
[Wang 06]G. Wang, G. Cao, and T. F. La Porta, "Movement-assisted sensor deployment," IEEE Transactions on Mobile Computing, vol. 5, pp. 640-652, 2006.
[Welzl 91]E. Welzl, "Smallest enclosing disks (balls and ellipsoids)," Berlin, Germany, 1991, pp. 359-70.
[Wu 06]C.-H. Wu, K.-C. Lee, and Y.-C. Chung, "A Delaunay triangulation based method for wireless sensor network deployment," International Conference on Parallel and Distributed Systems, ICPADS 2006, 2006.
[Xiaoyun 08]L. Xiaoyun and D. K. Hunter, "Distributed Coordinate-Free Hole Recovery," IEEE International Conference on Communications Workshops, 2008. ICC Workshops ''08., 2008, pp. 189-194.
[Xingfa 06]S. Xingfa, C. Jiming, and S. Youxian, "Grid scan: A simple and effective approach for coverage issue in wireless sensor networks," Istanbul, Turkey, 2006, pp. 3480-3484.
[Zhen 08]J. Zhen, W. Jie, R. Kline, and J. Krantz, "Mobility Control for Complete Coverage in Wireless Sensor Networks," International Conference on Distributed Computing Systems Workshops, ICDCS ''08., 2008, pp. 291-296.