Collision-Free Motion Algorithms for Sensors Automated Deployment to Enable a Smart Environmental Sensing-Net

Ting Yu Lin, Kun Ru Wu, You Shuo Chen, Yan Syun Shen

研究成果: Article同行評審


As natural habitats protection has become a global priority, smart sensing-nets are ever-increasingly needed for effective environmental observation. In a practical monitoring network, it is critical to deploy sensors with sufficient automated intelligence and motion flexibility. Recent advances in robotics and sensors technology have enabled automated mobile sensors deployment in a smart sensing-net. Existing deployment algorithms can be employed to calculate adequate destinations (goals) for sensors to perform respective monitoring tasks. However, given the calculated goal positions, the problem of how to actually coordinate a fleet of robots and schedule moving paths from random initials to reach their goals safely, without collisions, remains largely unaddressed in the wireless sensor networking (WSN) literature. In this paper, we investigate this problem and propose polynomial-time collision-free motion algorithms based on batched movements to ensure all the mobile sensors reach their goals successfully without incurring collisions. We observe that the grouping (batching) strategy is similar to the coloring procedure in graph theory. By constructing a conflict graph, we model the collision-free path scheduling as the well-known k-coloring problem, from which we reduce to our k-batching problem (determining the minimum number of required batches for a successful deployment) and prove its NP completeness. Since the k-batching problem is intractable, we develop CFMA (collision-free motion algorithm), a simple yet effective batching (coloring) heuristic mechanism, to approximate the optimal solution. Performance results show that our motion algorithms outperform other existing path-scheduling mechanisms by producing 100% sensors reachability (success probability of goals reaching), time-bounded deployment latency with low computation complexity, and reduced energy consumption.


深入研究「Collision-Free Motion Algorithms for Sensors Automated Deployment to Enable a Smart Environmental Sensing-Net」主題。共同形成了獨特的指紋。