TY - JOUR

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

AU - Lin, Ting Yu

AU - Wu, Kun Ru

AU - Chen, You Shuo

AU - Shen, Yan Syun

N1 - Publisher Copyright:
Author

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - autonomous sensors deployment

KW - Collision avoidance

KW - collision-free motion algorithm

KW - Environmental observation and monitoring

KW - graph theory

KW - Intelligent sensors

KW - Robot kinematics

KW - Robot sensing systems

KW - Sensors

KW - smart sensing network automation

KW - System recovery

KW - vertex coloring.

KW - Wireless sensor networks

UR - http://www.scopus.com/inward/record.url?scp=85122861006&partnerID=8YFLogxK

U2 - 10.1109/TASE.2021.3138198

DO - 10.1109/TASE.2021.3138198

M3 - Article

AN - SCOPUS:85122861006

SN - 1545-5955

JO - IEEE Transactions on Automation Science and Engineering

JF - IEEE Transactions on Automation Science and Engineering

ER -