[[alternative]]Mobile sensor relocation problem with energy-balanced and timely consideration

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