标题: 无线行动感测器布署之路径规划演算法设计及实作
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