A Coverage-Aware Distributed k-Connectivity Maintenance Algorithm for\n Arbitrarily Large k in Mobile Sensor Networks

Abstract

Mobile sensor networks (MSNs) have emerged from the interaction between\nmobile robotics and wireless sensor networks. MSNs can be deployed in harsh\nenvironments, where failures in some nodes can partition MSNs into disconnected\nnetwork segments or reduce the coverage area. A k-connected network can\ntolerate at least k-1 arbitrary node failures without losing its connectivity.\nIn this study, we present a coverage-aware distributed k-connectivity\nmaintenance (restoration) algorithm that generates minimum-cost movements of\nactive nodes after a node failure to preserve a persistent k value subject to a\ncoverage conservation criterion. The algorithm accepts a coverage conservation\nratio (as a trade-off parameter between coverage and movements) and facilitates\ncoverage with the generated movements according to this value. Extensive\nsimulations and testbed experiments reveal that the proposed algorithm restores\nk-connectivity more efficiently than the existing restoration algorithms.\nFurthermore, our algorithm can be utilized to maintain k-connectivity without\nsacrificing the coverage, significantly.\n