無線行動感測器佈署之路徑規劃演算法設計及實作

Abstract

在本論文中，我們著重於研究行動感測器佈署過程中的路線規劃，主要目的是為了 自主監測網路，並且提出Collision-free Path Planning(以下簡稱CFPP) 演算法，使數個 行動感測器在移動過程中免於碰撞。CFPP 演算法以幾何公式為基礎，並且會仔細地安 排行動感測器的移動路線避免在自動化佈署過程中發生碰撞。除了collision-free 的特性 之外，我們CFPP 演算法也擁有deadlock-free 的特性，確保行動感測器/機器人能百分 之百的到達想要的位置/目的地。效能評估的結果顯示我們的CFPP 演算法在尋找路徑 的時間、物理移動耗能以及到達目的地比率都優於其他機制。原有的CFPP 演算法假設 行動感測器的體積是可以被忽略的，並且行動感測器視為只是在2D 平面上的移動點。 為了將CFPP 演算法應用於實際的感測系統中，我們將CFPP 演算法改良成有考量體積 大小的CFPPv 演算法。我們更進一步使用LEGO 公司的NXT 移動式機器人來驗證演算 法在現實環境中的可行性。

In this thesis, we address the path scheduling problem for mobile sensors deployment. We target on autonomous monitoring networks and propose a Collision-Free Path Planning (abbreviated as CFPP) algorithm to realize moving multiple mobile sensors without collisions. The proposed CFPP algorithm, based on geometric formulations, carefully schedules the moving paths to avoid sensors colliding into each other while performing self-deployment. In addition to the collision-free feature, our CFPP also possesses the deadlock-free property, which ensures a 100% reachability for mobile sensors/robots to arrive at desirable locations/destinations. Evaluation results show that CFPP outperforms other mechanisms in terms of computation time, moving energy, and destination reachability. The original CFPP algorithm assumes the sensor volume is neglected and regarded as a moving point on a 2D plane. In order for the CFPP algorithm to be applied in realistic sensing systems, we develop a modified CFPPv algorithm to take the sensors volume into consideration. We further implement the CFPPv algorithm based on LEGO NXT mobile robots to demonstrate the protocol feasibility in a real-life environment.