A Distributed Algorithm to Establish Strong Connectivity in Spatially Distributed Networks via Estimation of Strongly Connected Components

This paper presents a distributed algorithm for ensuring the strong connectivity of spatially distributed networks where the communication network topology depends on both the position and communication range of the nodes. This is achieved by adding new links via adjusting the communication range and/or controlling the position of the nodes. The distributed algorithms rely on the estimation of strongly connected components of a dynamic network topology, accomplished through the utilization of the maximum consensus algorithm. The proposed strategies are scalable and converge in a finite number of steps without requiring information on the overall network topology. Finally, the proposed distributed algorithm is demonstrated through two case studies of ensuring strong connectivity in wireless networks with static and mobile nodes.

I. Introduction

A spatially distributed network (SDN) consists of numerous devices/nodes with limited sensing, data processing, and communication capabilities. SDNs have been widely used to represent wireless sensor networks [1], [2] and robotic networks [3] for estimation, optimization, and control purposes. As SDNs may not have a control center, data processing/decision-making should be designed and implemented at the node level with direct data exchange between the neighboring nodes, also known as distributed estimation/optimization/control [4]. The communication network topology in SDNs is constructed based on the locations of the nodes and their communications range, as a node can only send information to the nodes within its communication range. Since the individual node may have different but limited communication range, the network topology in SDNs can then be modeled as a directed graph.