在無線感測網路中，感測器搬遷問題(Sensor Relocation problem)是一項非常重要的研究議題。感測器搬遷問題與感測器部署問題(Sensor Deployment problem)的最大差別在於感測器搬遷問題具有嚴格的反應時間限制。其原因在於感測器部署問題處於網路的初始化階段，此階段的目標是讓建構出來的無線感測網路達到一定的覆蓋程度即可，因此通常不會有嚴格的反應時間限制。然而感測器搬遷問題處於無線感測網路的運作階段，因此必須盡可能在不影響監控任務下，利用冗餘感測器來完成故障感測器的替換及空洞處理。這也就是為什麼感測器搬遷問題會有較為嚴格的反應時間限制。在本論文中，我們將針對移動無線感測網路下的感測器搬遷問題做一探討，提出新的感測器搬遷演算法。在減少訊息量方面，我們將利用quorum的概念來傳送訊息封包，並搭配本論文所設計出的封包代轉停止條件(Stopping Criteria)來減少訊息封包之傳送量。在減少反應時間以及減少移動距離方面，冗餘感測器將採連座式移動(Cascaded Movement)的方式來進行故障感測器的替換及空洞處理。在連座式排程(Cascading Schedule)規劃方面，將藉由加入網路存活時間估計值(estimated value of network lifetime)考量，來避免不必要的感測器移動。經由實驗結果可以證明我們所提出的感測器搬遷演算法在訊息量、反應時間、移動距離以及網路存活時間上皆有著很好的表現。

The Sensor Relocation problem (SR problem) is an important issue in Wireless Sensor Networks (WSNs). The main difference between SR problem and Sensor Deployment (SD) problem is that SR problem has a strict response time requirement. Because the SD problem occurs during network initialization, so there is no strict response time requirement. The SD problem is solved as long as the required coverage level is met. However, the SR problem occurs during operation of WSNs, we need to minimize the impact on the surveillance task while replacing faulty sensors with redundant sensors. In this thesis, we revisit the SR problem in mobile WSNs. In order to reduce the amount of message exchange, the proposed SR algorithm uses the concept of quorum to send RICH packets (in columns) and HUNGRY packets (in rows). With the proposed stopping criteria, the proposed algorithm can further reduce the amount of these two types of packets to send. In terms of response time and moving distance, the proposed algorithm moves redundant sensors to faulty sensors and coverage holes by cascaded movement. It also considers the estimated value of network lifetime in the planning of cascading schedule. Hence, the SR problems caused by inappropriate cascading schedules can be avoided. Overall, the proposed SR algorithm has the following features: smaller amount of message exchange, shorter response time, shorter moving distances, smaller number of requesting places, and longer network lifetime. The performance evaluation done in this research has confirmed its superior performances in all these aspects.

目錄
圖目錄	Ⅴ
表目錄	Ⅶ
第一章、簡介	1
第二章、相關研究	4
2.1Robot-Assisted SR Problem	4
2.2Self-Relocation SR Problem 	5
第三章、問題定義以及環境假設	12
第四章、方法描述	14
4.1Requesting place與冗餘感測器之配對	14
4.2Cascading Schedule之規劃	22
第五章、實驗分析及模擬	30
第六章、結論	38
參考文獻	39
附錄-英文論文	43

圖目錄
圖1. 無線感測網路之生命週期	2
圖2. Cascaded movement	7
圖3. Cascading Schedule	8
圖4. 網格Grid(x+1,y)中的感測器皆發生故障	8
圖5. BCS演算法之執行範例	10
圖6. 網路環境	12
圖7. RICH封包傳送方式	16
圖8. 直角三角形CDE以及CF'E	17
圖9. Grid(i+1,j+1)之header可以通訊的範圍	17
圖10. 當網格中沒有header可以發送HUNGRY封包	20
圖11. HUNGRY封包的代傳停止條件	21
圖12. Members of cascaded movement的挑選範圍	25
圖13. 橫跨多個網格的移動	26
圖14. cascading schedule例子	26
圖15. The Pseudo Code of SRM algorithm	28
圖16. The Pseudo Code of SRS algorithm	29
圖17. RICH封包之傳送量比較圖-1	31
圖18. RICH封包之傳送量比較圖-2	31
圖19. HUNGRY封包之傳送量比較圖-1	32
圖20. HUNGRY封包之傳送量比較圖-2	32
圖21. HUNGRY封包數量及RICH封包數量之關係圖	33
圖22. 反應時間比較圖-1	34
圖23. 反應時間比較圖-2	34
圖24. 進行cascaded movement時，所需包含到的感測器數量	35
圖25. 不同故障率下之網路存活時間	36
圖26. 不同尺寸場景之網路存活時間	37

表目錄
表1 參數設定	30

[1]	A. Ababnah, B. Natarajan, “Optimal Control-Based Strategy for Sensor Deployment,” IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, vol. 41, no. 1, pp. 97-104, 2011.
[2]	H. Alemdar, C. Ersoy, “Wireless Sensor Networks for Healthcare: A Survey,” Computer Networks, vol. 54, pp. 2688-2710, 2010.
[3]	L. Atzori, A. Iera, G. Morabito, “The Internet of Things: A Survey,” Computer Networks, vol. 54, no. 15, pp. 2787-2805, 2010.
[4]	F. Aurenhammer, “Voronoi diagrams – A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys, vol. 23, pp. 345-406, 1991.
[5]	C.F. Cheng, K. T. Tsai, “Distributed Barrier Coverage in Wireless Visual Sensor Networks with β-QoM,” IEEE Sensors Journal, vol. 12, no. 6, pp. 1726-1735, 2012.
[6]	C.F. Cheng, T. Y. Wu and H. C. Liao, “A Density-Based Barrier Construction Algorithm with Minimum Total Movement in Mobile WSNs,” Computer Networks, DOI: 10.1016/j.bjp.2013.12.001, 2013.
[7]	G. Fletcher, X. Li, A. Nayak, I. Stojmenovic, “Randomized Robot-assisted Relocation of Sensors for Coverage Repair in Wireless Sensor Networks,” Proceeding of the Vehicular Technology Conference Fall (VTC-F 2010), pp. 1-5, 2010. 
[8]	M. Garetto, M. Gribaudo, C. Chiasserini, E. Leonardi, “A Distributed Sensor Relocation Scheme for Environmental Control,” in Proceeding of the IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS 2007), pp. 1-10, 2007.
[9]	D. Gu, “A Game Theory Approach to Target Tracking in Sensor Networks,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 41, no. 1, pp. 2-13, 2011.
[10]	D. M. Han, J. H. Lim, “Smart Home Energy Management System Using IEEE 802.15.4 and Zigbee,” IEEE Transactions on Consumer Electronics, vol. 56, no. 3, pp. 1403-1410, 2010.
[11]	S. He, J. Chen, P. Cheng, Y. Gu, T. He, Y. Sun, “Maintaining Quality of Sensing with Actors in Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 9, 2012. 
[12]	R. V. Kulkarni, A. Forster, G. K. Venayagamoorthy, “Computational Intelligence in Wireless Sensor Networks: A Survey,” IEEE Communications Surveys & Tutorials, vol. 13, no. 1, pp. 68-96, 2011.
[13]	W. Li, Y. I. Kamil, A. Manikas, “A Wireless Array based Cooperative Sensing Model in Sensor Networks,” Proceeding of the Global Communications Conference (GLOBECOM 2008), pp. 1-6, 2008.
[14]	W. Li, Y. I. Kamil, A. Manikas, “Wireless Array Based Sensor Relocation in Mobile Sensor Networks,” Networks,” Proceeding of the International Conference on Wireless Communications and Mobile Computing (IWCMC 2009) , pp. 832-838, 2009.
[15]	A. V. Savkin, F. Javed, A. S. Matveev, “Optimal Distributed Blanket Coverage Self-Deployment of Mobile Wireless Sensor Networks,” IEEE Communications Letters, vol. 16, no. 6, pp. 949-951, 2012.
[16]	Y.Y. Shih, W.H. Chung, P.C. Hsiu, A.C. Pang, “A Mobility-Aware Node Deployment and Tree Construction Framework for ZigBee Wireless Networks,” IEEE Transactions on Vehicular Technology, vol. 62, no. 6, pp. 2763-2779, 2013.
[17]	F. Stajano, N. Hoult, I. Wassell, P. Bennett, C. Middleton, K. Soga, “Smart Bridges, Smart Tunnels: Transforming Wireless Sensor Networks from Research Prototypes into Robust Engineering Infrastructure,” Ad Hoc Networks, vol. 8, pp. 872-888, 2010.
[18]	C. Suh, Y. B. Ko, “Design and Implementation of Intelligent Home Control Systems Based on Active Sensor Networks,” IEEE Transactions on Consumer Electronics, vol. 54, no. 3, pp. 1177-1184, 2008.
[19]	G. Wang, G. Cao, T. L. Porta, W. Zhang, “Sensor Relocation in Mobile Sensor Networks,” Proceeding of the International Conference on Computer Communications (INFOCOM 2005), vol. 4, pp. 2302-2312, 2005.
[20]	B Wang, H. B. Lim, D. Ma, “A Coverage-Aware Clustering Protocol for Wireless Sensor Networks,” Computer Networks, vol. 56, no. 5, pp. 1599-1611, 2012.
[21]	C. Wang, H. Ma, Y. He, S. Xiong, “Adaptive Approximate Data Collection for Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 6, pp. 1004-1016, 2012.
[22]	X. Wang, S. Wang, “Hierarchical Deployment Optimization for Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 10, no. 7, pp. 1028-1041, 2011.
[23]	J.L. Wardlaw, I. Karaman, A. Karsilayan, “Low-Power Circuits and Energy Harvesting for Structural Health Monitoring of Bridges,” IEEE Sensors Journal, vol. 13, no. 2, pp. 709-722, 2013.
[24]	F. Hu, Y. Xiao, Q. Hao, “Congestion-Aware, Loss-Resilient Bio-Monitoring Sensor Networking for Mobile Health Applications,” IEEE Journal on Selected Areas in Communications, vol. 27, no. 4, pp. 450-465, 2009.
[25]	O. Younis, M. Krunz, S. Ramasubramanian, “Node Clustering in Wireless Sensor Networks: Recent Developments and Deployment Challenges,” IEEE Networks, vol. 20, no. 3, pp. 20-25, 2006.
[26]	Q. Yang, S. He, J. Li, J. Chen, Y. Sun, “Energy-Efficient Probabilistic Area Coverage in Wireless Sensor Networks,” IEEE Transactions on Vehicular Technology, DOI: 10.1109/TVT.2014.2300181, 2014.
[27]	H. Yang, Y. Qin, G. Feng, H. Ci, “Online Monitoring of Geological CO2 Storage and Leakage Based on Wireless Sensor Networks,” IEEE Sensors Journal, vol. 13, no. 2, pp. 556-562, 2013.
[28]	D. Zorbas, C. Douligeris, “Connected Coverage in WSNs Based on Critical Targets,” Computer Networks, vol. 55, no. 6, pp. 1412-1425, 2011.
[29]	Y. Zou, K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Transactions on Embedded Computing Systems, vol. 3, no. 1, pp. 61-91, 2004