标题: 無線行動感測器佈署之路徑規劃演算法設計及實作
Design and Implementation of Path Scheduling Algorithms for Wireless Mobile Sensors Deployment
作者: 林駿安
林亭佑
電信工程研究所
关键字: 行動感測器佈署;路徑規劃;mobile sensors deployment;path planning
公开日期: 2014
摘要: 在本論文中,我們著重於研究行動感測器佈署過程中的路線規劃,主要目的是為了
自主監測網路,並且提出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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070160259
http://hdl.handle.net/11536/76347
显示于类别:Thesis