Self-Organized Connectivity Control and Optimization Subjected to Dispersion of Mobile Ad Hoc Sensor Networks

Abstract

This paper addresses the problem of the connectivity control and the self-organized deployment/dispersion of a team of mobile ad hoc sensor nodes. First, to reduce redundant communication links while preserving global connectivity, a distributed link removal algorithm is developed that only requires local information of no more than two-hop neighbors. Secondly, for the purpose of preserving essential links while avoiding collisions, a combined piecewise-continuous motion controller is designed to regulate the motion of mobile sensors between two consecutive switches. The proposed hybrid control system can autonomously disperse a team of mobile sensors towards their final configuration with guaranteed connectivity and collision avoidance. Theoretical analysis and computer simulations have confirmed the efficiency and scalability of the proposed schemes.

1. Introduction

The self-organized connectivity control and dispersion of mobile ad hoc sensor networks (MASNs) has been extensively investigated due to its promising potential applications in various fields, such as remote supervision of hazard substances, exploration of unknown fields, and cooperative sensing. Enhancing the coverage of the MASNs could be beneficial, if not critical, for a variety of missions, such as environmental monitoring and disaster management. Moreover, from the wireless communication point of view, the sparse network structure resulted from the enhanced coverage can effectively reduce radio interferences, which is critical for the elimination of excessive message overheads and the reduction of the latency [1]. Furthermore, in energy critical wireless sensor networks, the reduction of message overheads as well as the complexity of the self-organizing algorithms can extend the service lifetime of the systems.

In a mobile sensor network, the mobility of sensor nodes provides the possibility for the nodes to deploy to a configuration with desired properties from an arbitrary initial distribution in a self-organized manner. The aforementioned concept of MASNs has attracted numerous research efforts. Among various topics that have been covered, emphasis is placed on the consensus of a group of mobile sensors, such as flocking and rendez-vous, with a particular interest in coverage and connectivity control. Self-organized dispersion, on the other hand, is another fundamentally essential aspect of the system and requires more research efforts.

Self-organized dispersion of MASNs can be loosely defined as maximizing coverage with a minimum number of mobile sensors [2]. Significant application potentials of self-organized dispersion have recently led to a surge of research attentions. Techniques including inverse agreement control law [3], clique-intensity algorithm [2], and “artificial physics” frame-work [4] have been developed to regulate the evolution of the underlying networks. Coverage control of mobile networks is another promising research area that is closely related to self-organized dispersion, and numerous efforts have concentrated on the deployment of mobile sensors [5–8], coverage control in stationary WASN [9], and coverage control of autonomous agents [10]. Commonly used models include Voronoi diagrams [7, 8] and potential functions [10, 11]. Voronoi diagrams method can partition the field into many subareas dedicated to each mobile sensor, allowing sensors to move to maximize coverage in its own subarea. However, the assumption that mobile sensors can easily detect most of its Voronoi neighbors through local communication may not be satisfied in a real network, due to the limited communication range of the mobile sensors, which may not be sufficient for covering all Voronoi neighbors. Potential function, on the other hand, is able to fulfill the self-organized coverage control of mobile sensor nodes in a more local and distributed manner. The concept of this approach is to imitate the behavior of electromagnetic particles: whenever two electromagnetic particles are too close in proximity, a repulsive force pushes them apart. In mobile ad hoc sensor networks, this method can help move sensors from high density to low density areas, thereby dispersing the team to improving the overall network coverage.

Connectivity control of MASNs is rapidly becoming a hot research topic in the field of multiagent systems, and various strategies have been developed in recent years, including both centralized [12, 13] and decentralized [14–20] approaches. A common way to maintain connectivity in mobile networks is to shrink the communication links between any two neighbors whenever they tend to break [21]. Most studies have attempted to maximize Fiedler value [13] and to add communication links to increase connectivity [22]. However, these approaches often result in a tight network structure with dense communication links, which may largely restrict the mobility of mobile sensors and jeopardize the coverage and cooperation efficiency. More importantly, from the wireless communication point of view, high network density can severely aggravate radio interferences [1]. To deal with these problems, Zavlanos and Pappas [15] proposed a distributed market-based control strategy, which is able to reduce redundant communication links based on local estimation of spanning subgraph. This strategy, however, requires full knowledge of the network structure, which may cause large delay in dense and large-scale networks [23]. In [17], a connectivity control strategy is presented with a particular consideration of the relationship between the communication range and the sensing range, that is, radio range is at least twice the sensing range. The proposed control scheme can guaranteed a connected network with optimized sensing coverage. How to disperse the networked sensors to achieve a sparse topology is not yet discussed. It is also worthwhile to mention that certain topology control methods [24, 25] in ad hoc senor networks have been developed that similarly deal with the issue of removing redundant communication links. However, these works are mainly based on stationary network structure. The important issues of combing global connectivity and dispersion of mobile sensors with respect to mobility control strategy have not been addressed properly.

Contributions

Aiming at bridging the gap between dispersion and connectivity, we first present a distributed link removal algorithm (DLRA) to reduce redundant communication links while preserving global connectivity. The proposed algorithm is fully distributed and only requires local information of no more than two-hop neighbors. Then, by integrating DLRA with a novel combined piecewise-continuous potential function, a distributed connectivity control system is developed to disperse a team of mobile sensors with guaranteed connectivity and collisions avoidance. The present work provides answers to the following questions.

(1)

How to remove communication links with respect to global connectivity based only on local information of neighbor status?

(2)

How to disperse a team of sensors with connectivity preservation, collision avoidance, and limited actuation?

(3)

Is the generated network structure sparse enough to fulfill dispersion requirement?

The rest of the paper is organized as follows: Section 2 provides necessary terminologies and notations. Section 3 presents the DLRA algorithm that is developed to address the link removal problem with respect to global connectivity. Section 4 introduces a distributed combined piecewise-continuous potential function to control the motion of mobile sensors. Computer simulations are included in Section 5, and this paper is concluded in Section 6 with a discussion of future research works.

2. Problem Formulation

Let the dynamic graph $𝒢 (t) = (𝒱, E (t))$ denote a mobile network of n mobile sensor nodes with integrated wireless communication capabilities, where $𝒱 = (1, \dots, n)$ denotes the set of vertices indexed by the set of mobile sensors and $E (t) = {i, j ∣ f_{i j} (t) \geq ε, i, j \in 𝒱}$ , $0 < ε < 1$ denotes the time-variant set of communication links. We define $0 \leq f_{i j} (t) \leq 1$ to be a normalized nonnegative weighting function symmetric in its arguments, that is, $f_{i j} (t) = f_{j i} (t)$ , and assume that $f_{i j} (t) \neq f_{i k} (t)$ , $j \neq k$ . In this case, the adjacency matrix $𝒜 (t) = (a_{i j} (t))$ $\in ℝ^{n \times n}$ (we define $a_{i i} (t) \equiv 0$ for all i, thus there are no self-loops in the network) can be defined as follows:

\begin{matrix} a_{i j} (t) = {\begin{cases} a_{j i} (t) = f_{i j} (t), & (i, j) \in E (t), \\ 0, & otherwise . \end{cases} \end{matrix}

(1)

Note that any normalized nonnegative function can be treated as a weighting function. Nevertheless, to associate with the link quality, it is rather a natural choice that $f_{i j} (t)$ denotes received signal strength. Moreover, as indicated in radio propagation theory [1], in obstacle-free environment, signal fading can be treated as an exponential decay function of the Euclidean distance between i and j. In particular, we have the following definitions.

Definition 1.

For any node i in $𝒢 (t) = (𝒱, E (t))$ , the normalized received signal strength from node j is set to be:

\begin{array}{l} f_{i j} (t) \\ ≜ {\begin{cases} 1, & ∥ ξ_{i} (t) - ξ_{j} (t) ∥ < a_{0}, \\ \exp [- β (∥ ξ_{i} (t) - ξ_{j} (t) ∥ - a_{0})], & otherwise, \end{cases} \end{array}

(2)

where β (the value of β depends on the radio frequency, antenna gain, system loss, and environmental factors, etc.) is positive path-loss value, and $a_{0}$ is reference distance (see Figure 1).

Figure 1

Modeling normalized receive signal fading with Euclidean distance, where $𝒟 = ∥ ξ_{i} (t) - ξ_{j} (t) ∥$ , and $a_{0} = 2$ .

Definition 2.

An undirected weighted dynamic graph $𝒢 (t) = (𝒱, E (t))$ is defined as connected at time t if and only if there is at least one communicative path between any two vertices within it.

Furthermore, consider the vertices in $𝒢 (t)$ as n mobile sensors with single-integrator kinematic model given by the following:

\begin{matrix} {\dot{ξ}}_{i} (t) = u_{i} (t), \end{matrix}

(3)

where $ξ_{i} (t) \in ℝ^{N}$ and $u_{i} (t) \in ℝ^{N}$ denotes the position and velocity of node i, respectively.

Now the main objectives of this paper can be described as follows:

(1)

for any nodes i and j in $𝒢 (t) = (𝒱, E (t))$ , determine whether link $(i, j)$ is an essential communication link for connectivity maintenance, and then remove redundant communication links. The generated subgraph $𝒢_{s} (t) = (𝒱, E_{s} (t))$ contains only essential communication links, that is, $(i, j) \in E_{s} (t)$ ;

(2)

for the corresponding kinematic system ${\dot{ξ}}_{i} (t) = u_{i} (t)$ , derive a dynamic motion controller $u_{i} (t) \in ℝ^{N}$ for all sensors i between any two consecutive switches, so that (1) for any $(i, j) \in E_{s} (t)$ , it is guaranteed that $ε \leq f_{i j} (t) < φ$ ; (2) for any $(i, j) \notin E_{s} (t)$ , nodes i and j are dispersed into the set ${i, j ∣ f_{i j} \leq ε, i, j \in 𝒱}$ (see Figure 2).

Figure 2

The trajectories of node j and v denote the possible movements where $(i, j), (i, v) \in E_{s} (t)$ , and that of node k depicts the situation where $(i, k) \notin E_{s} (t)$ , that is, be removed from $𝒢 (t)$ and dispersed from each other.

3. Distributed Link Removal Algorithm with Respect to Global Connectivity

The objective of this section is to develop a distributed local connectivity control algorithm, aiming at removing redundant communication links to facilitate the self-organized dispersion of mobile sensors with respect to global connectivity.

3.1. Principle of DLRA

Let us first introduce the following definitions which categorize neighboring sensors into two distinctive neighbor relationship sets, namely, physical neighbor set and logical neighbor set.

Definition 3.

Node j is in the physical neighbor set of i, denoted $j \in {𝒩_{p}}^{[i]} (t)$ , if and only if $(i, j) \in E (t)$ .

Definition 4.

Node j is the logical neighbor set of i, denoted $j \in {𝒩_{l}}^{[i]} (t)$ , if and only if $(i, j) \in E_{s} (t)$ .

Definition 5.

For any node i in the network, we denote ${𝒩_{r}}^{[i]} (t) = (a_{j k} (t))$ as the neighbor relationship matrix (NRM) at time t, where $j \in {𝒩_{l}}^{[i]} (t)$ and $k \in {𝒩_{l}}^{[j]} (t)$ .

Based on the aforementioned definitions, the proposed DLRA is described as follows.

Information Exchange

The information that sensor i requires for the link removal algorithm is obtained by periodically receiving Heartbeat messages from all its neighbors in ${𝒩_{p}}^{[i]} (t)$ . The periodical messages sent by neighborj should at least contain the following information: node ID, position, logical neighbor set ${𝒩_{l}}^{[j]} (t)$ , and link weight with all its logical neighbors. After exchanging information with all its neighbors, each node is only aware of the status of its one-hop physical neighbors and two-hop logical neighbors.

Selecting Candidate Links to Be Removed

Upon receiving Heartbeat message from each individual physical neighbor, node i updates ${𝒩_{p}}^{[i]} (t)$ . As it is assumed that the initial network is connected, DLRA starts at time $t = t_{0}$ . Then, the process is started with initial condition that ${𝒩_{p}}^{[i]} (t_{0})$ $= {𝒩_{l}}^{[i]} (t_{0})$ , and ${𝒩_{r}}^{[i]} (t_{0})$ is constructed for each i. The selection of candidate links is as follows.

Step 1.

Look up neighbor relationship matrix ${𝒩_{r}}^{[i]} (t_{0})$ . If $\exists a_{k j} (t_{0}) \in {𝒩_{r}}^{[i]} (t_{0})$ , where $j \in {𝒩_{l}}^{[i]} (t)$ , there exists a triangle consist of sensor i, j, k. If and only if $a_{i j} (t_{0})$ $= \max {a_{i j} (t_{0}), a_{i k} (t_{0}), a_{j k} (t_{0})}$ , then denote link $(i, j)$ as candidate link to be removed from ${𝒩_{l}}^{[i]} (t)$ , put sensor j into candidate removal set ${𝒞_{d}}^{[i]} (t)$ , and remove corresponding row vector in ${𝒩_{r}}^{[i]} (t)$ (cf. line 2–7 in Algorithm 1).

Algorithm 1: Link removal mechanism for DLRA.

Upon receiving Hello message from j, update ${𝒩_{p}}^{[i]} (t)$ , send Hello message back. Upon finishing neighbor

discovery, set time $t = t_{0}$ and ${𝒩_{l}}^{[i]} (t_{0}) = {𝒩_{p}}^{[i]} (t_{0})$ . Construct ${𝒩_{r}}^{[i]} (t_{0})$ , Initialized.

$(1)$ For $i \in 𝒱$

$(2)$ while $\exists a_{k j} (t_{0}) \in {𝒩_{r}}^{[i]} (t_{0})$ and $j \in {𝒩_{l}}^{[i]} (t_{0})$ do

$(3)$ $\forall k \in {𝒩_{r}}^{[i]} (t_{0})$

$(4)$ if $a_{i j} (t_{0}) = \max {a_{i j} (t_{0}), a_{i k} (t_{0}), a_{j k} (t_{0})}$

$(5)$ ${𝒞_{d}}^{[i]} (t_{0} + Δ t) : = {𝒞_{d}}^{[i]} (t_{0}) \cup {j}$ , send Req $D (i, j)$ to j

$(6)$ end if

$(7)$ end while

$(8)$ Update ${𝒩_{r}}^{[i]} (t), {𝒞_{d}}^{[i]} (t)$ , hold

$(9)$ Construct ${𝒩_{r}}^{[i k]} (t) = [a_{j k} (t), a_{l k} (t), \dots a_{n k} (t)]$

$(10)$ $\forall k \in {𝒩_{r}}^{[i]} (t)$

$(11)$ while $a_{j k} (t) \times a_{l k} (t) \neq 0$ do

$(12)$ if $a_{i j} (t) = \max {a_{i j} (t), a_{i l} (t), a_{j k} (t), a_{l k} (t)}$

$(13)$ ${𝒞_{d}}^{[i]} (t + Δ t) : = {𝒞_{d}}^{[i]} (t) \cup {j}$ , send Req $D (i, j)$ to j

$(14)$ end if

$(15)$ end while

$(16)$ End

Step 2.

Update ${𝒩_{r}}^{[i]} (t)$ , so that there is no triangle in the updated topology. Let ${𝒩_{r}}^{[i k]} (t) = [a_{j k} (t), a_{l k} (t), \dots a_{n k} (t)]$ be the column vector of ${𝒩_{r}}^{[i]} (t)$ , where $(j, l \dots n) \in {𝒩_{l}}^{[i]} (t)$ . Check ${𝒩_{r}}^{[i k]} (t)$ for every $k \in {𝒩_{r}}^{[i]} (t)$ , if $\exists a_{j k} (t)$ , and $a_{l k} (t)$ , $j \neq l$ and $a_{j k} (t) \times a_{l k} (t) \neq 0$ , compare link weights $a_{i j} (t)$ , $a_{i l} (t)$ , $a_{j k} (t)$ , and $a_{l k} (t)$ , if $a_{i j} (t)$ $= \max$ ${a_{i j} (t), a_{i l} (t), a_{j k} (t), a_{l k} (t)}$ , then denote link $(i, j)$ as candidate link to be removed from ${𝒩_{l}}^{[i]} (t)$ , and put j into ${𝒞_{d}}^{[i]} (t)$ and remove corresponding row vector in ${𝒩_{r}}^{[i]} (t)$ (cf. line 8–15 in Algorithm 1 ( $Δ t$ is the execution time for node i in every edge removal procedure, we assume $Δ t$ is constant for any node).

Synchronized Local Coordination for DLRA (Algorithm 2)

A major challenge when dealing with dynamic network is that, the network topology may be changed during any consecutive switches, due to the movement and leaving/joining of the mobile sensors. Meanwhile, an unpredictable message delay may occur at any time. Therefore, a synchronization process is required for such situations. In particularly, a request and acknowledge mechanism is utilized to dynamically synchronize the disconnection of any redundant communication links between the corresponding vertices. That is, upon the determination of redundant communication link, for example, $j \in {𝒞_{d}}^{[i]} (t)$ , a request message $Req D$ $(i, j)$ will be sent from i to j. Upon receiving $Req D (i, j)$ sensor j will remove sensor i from the logical neighbor set ${𝒩_{l}}^{[j]} (t)$ and send back a acknowledge message $Ack D (j, i)$ based on the condition that $i \in {𝒞_{d}}^{[j]} (t)$ . The network structure will be constructed based on the subgraph $𝒢_{s} (t)$ , which is generated from the proposed local coverage enhancement algorithm (cf. Algorithm 2).

Algorithm 2: Synchronized coordination for DLRA.

Upon receiving Req $D (i, j)$ from j

$(1)$ For $i \in 𝓋$

$(2)$ if $j \in {𝒞_{d}}^{[i]} (t)$

$(3)$ ${𝒩_{l}}^{[i]} (t + Δ t) ≔ {𝒩_{l}}^{[i]} ∖ {j}$ , send Ack $D (i, j) = 1$ to j

$(4)$ else if $\exists {𝒩_{r}}^{[i j]} (t)$

$(5)$ ${𝒩_{l}}^{[i]} (t + Δ t) ≔ {𝒩_{l}}^{[i]} (t) ∖ {j}$ , send Ack $D (i, j) = 1$ to j

$(6)$ else send Ack $D (i, j) = 0$ to j

$(7)$ end if

$(8)$ else send Ack $D (i, j) = 0$ to j

$(9)$ end if

$(10)$ Upon receiving Ack $D (i, j)$

$(11)$ if Ack $D (i, j) = 1$

$(12)$ ${𝒩_{l}}^{[i]} (t + Δ t) ≔ {𝒩_{l}}^{[i]} (t) ∖ {j}$

$(13)$ else

$(14)$ ${𝒞_{d}}^{[i]} (t + Δ t) ≔ {𝒞_{d}}^{[i]} (t) ∖ {j}$

$(15)$ end if

$(16)$ End

3.2. Capabilities and Message Complexity of DLRA

We first prove that the connectivity is guaranteed while the redundant links are removed from the underlying network.

Theorem 6.

Given a network $𝒢 (t_{0}) = (𝒱, E (t_{0}))$ with initial connectedness and controllable links, the subgraph $𝒢_{s} (t) = (𝒱, E_{s} (t))$ generated from DLRA is connected all the time.

Proof.

Since neighbor discovery procedure and adding redundant links into ${𝒩_{p}}^{[i]} (t)$ do not violate network connectivity, we only need to consider the link removal mechanism for connectivity preservation.

Consider two nodes $i_{0}$ , $i_{n}$ where $i_{0}$ , $i_{n}$ are initially connected in $𝒢 (t_{0})$ through a series of vertices, for example, $i_{0} \leftrightarrow i_{1} \leftrightarrow i_{2} \dots i_{n - 1} \leftrightarrow i_{n}$ . Suppose that $(i_{k}, i_{k + 1}) \notin E_{s} (t)$ , and $i_{k}, i_{k + 1}$ are disconnected in $𝒢 (t_{s})$ , we have the following.

Case 1. $\exists v$ where $v \in {𝒩_{l}}^{[i_{k}]} (t_{0})$ and $v \in {𝒩_{l}}^{[i_{k + 1}]} (t_{0})$ , since $(i_{k}, i_{k + 1}) \notin E_{s} (t)$ . According to step 2 in Algorithm 1, we have $a_{i_{k} i_{k + 1}} (t_{0}) = \max {a_{i_{k} i_{k + 1}} (t_{0}), a_{i_{k} v} (t_{0}), a_{i_{k + 1} v} (t_{0})}$ , so $\exists i_{k} \leftrightarrow v \leftrightarrow i_{k + 1}$ , contradiction reached.

Case 2. $\exists v, u$ where $u, v \in {𝒩_{l}}^{[i_{k}]} (t)$ , and $u, v \notin {𝒩_{l}}^{[i_{k + 1}]} (t)$ , since $(i_{k}, i_{k + 1}) \notin E_{s} (t)$ , $a_{i_{k} i_{k + 1}} (t) = \max {a_{i_{k} i_{k + 1}} (t), a_{i_{k} v} (t), a_{u i_{k + 1}} (t), a_{u v} (t)}$ , so we have $\exists i_{k} \leftrightarrow v \leftrightarrow u \leftrightarrow i_{k + 1}$ , contradiction reached.

The proof of Theorem 6 is completed.

In addition, for Case 1, suppose that there exists a path $i \leftrightarrow v \leftrightarrow u \leftrightarrow i$ , and $a_{i v} (t) = \max {a_{u v} (t), a_{i v} (t), a_{i u} (t)}$ . From Algorithm 1 it can be seen that $(i, v) \notin 𝒢_{s} (t)$ , so contra-diction reached. Similarly, for Case 2, suppose there exists $i \leftrightarrow v \leftrightarrow u \leftrightarrow j \leftrightarrow i$ , same contradiction can also be met, which leads to the following corollary.

Corollary 7.

For any generated subgraph $𝒢_{s} (t) = (𝒱, E_{s} (t))$ , the shortest cycle is 5, that is, there are no such links as $i \leftrightarrow v \leftrightarrow u \leftrightarrow i$ or $i \leftrightarrow v \leftrightarrow u \leftrightarrow j \leftrightarrow i$ .

Furthermore, through removing redundant links, node degree in $𝒢_{s} (t)$ can be constrained within a certain spectrum. In particular, one has the following.

Corollary 8.

For a generated subgraph $𝒢_{s} (t) = (𝒱, E_{s} (t))$ where $ξ_{i} (t) \in ℝ^{2}$ , the upper bound of node degree is 5.

Proof.

To see contradiction, it is assumed that there are two links $(i, j)$ and $(i, k)$ in $𝒢_{s} (t)$ , where $(i, j)$ and $(i, k)$ enclose an angle $α \leq π / 3$ at node i. Furthermore, suppose that $a_{i j} (t)$ $< a_{i k} (t)$ and $j, k \in {𝒩_{l}}^{[i]} (t)$ , from Definition 1 we know that link weight is a monotonic function of vertices’ Euclid distance, for example, $a_{i j} (t) < a_{i k} (t) \Leftrightarrow ∥ ξ_{i} (t) - ξ_{j} (t) ∥ <$ $∥ ξ_{i} (t) - ξ_{k} (t) ∥$ . Since $a_{i j} (t) < a_{i k} (t)$ and $α \leq π / 3$ , it is straightforward that $∥ ξ_{j} (t) - ξ_{k} (t) ∥ < ∥ ξ_{i} (t) - ξ_{k} (t) ∥$ , see Figure 3, which leads to $a_{i k} (t) = \max {a_{i j} (t), a_{j k} (t), a_{i k} (t)}$ . Consequently, we can conclude from Algorithm 1 that $k \notin {𝒩_{l}}^{[i]} (t)$ , for example, $(i, k)$ $\notin 𝒢_{s} (t)$ , thus we reach a contradiction to the assumption that $(i, k) \in 𝒢_{s} (t)$ . This proved that no adjacent links in $𝒢_{s} (t)$ enclose an angle equal or less that $π / 3$ , from which the corollary follows.

Figure 3

As indicated in proof of Corollary 8, $∥ ξ_{j} (t) - ξ_{k} (t) ∥ <$ $∥ ξ_{i} (t) - ξ_{k} (t) ∥$ if and only if $a_{i j} (t) < a_{i k} (t)$ and $α \leq π / 3$ .

In addition, the request and acknowledge mechanism in Algorithm 2 guarantees that, despite of trivial one-hop delays of the acknowledge information, the communication links in $𝒢_{s} (t)$ remain symmetric all the time. Moreover, DLRA depends only on local information of no more than two-hop neighbors, so that the information exchange between mobile sensors will not invite large delay and communication overhead. In particular, we have the following.

Theorem 9.

The worst-case message complexity of DLRA is $O (n^{2} / 2)$ , where n is the number of sensors.

Proof.

Since DLRA depends only on two-hop neighbor information to determine redundant communication links, this requires two messages per sensor, and total $2 n$ messages will be sent. In addition, request and acknowledge mechanism requires two messages to remove each redundant link. In the worst case where $𝒢 (t_{0})$ is a undirected complete graph (UCG), and $E_{s} (t) = n - 1$ , the maximum redundant communication links to be removed is $n (n - 1) / 2 - (n - 1) = (n - 1) (n - 2)$ $/ 2$ , so the total messages to be sent is $(n - 1) (n - 2) / 2 + 2 n = (n^{2}$ $+ n + 2) / 2$ . In conclusion, DLRA has a total message complexity of $O (n^{2} / 2)$ .

Note that for large scale mobile networks with limited communication range, it is an unlikely case that the initial configuration is a UCG. Therefore, the message complexity can be reduced dramatically, which makes DLRA scalable to MASNs with a large number of mobile sensors.

4. Dispersion of Mobile Sensors

The invariance of network structure between any two cons-cutive switches in $𝒢 (t)$ is prerequisite for the realization of connectivity preserving dispersion of mobile sensors. The aim of this section is to develop a distributed motion controller that regulates the dispersion of mobile sensors in continuous space. First, we utilize a combined potential function to ensure that all essential links are remained connected and interagent collisions are avoided all the time during the self-organized dispersion of mobile sensors between any two consecutive topology updates.

We first introduce a repulsive potential function to deal with the collision avoidance between sensor i and all its physical neighbors $j \in {𝒩_{p}}^{[i]} (t)$ , defined as ${ψ_{i j}}^{r} (t)$ , where ${ψ_{i}}^{r} (t)$ = $\sum_{j \in {𝒩_{p}}^{[i]} (t)} {ψ_{i j}}^{r} (t)$ . In particular, we have

\begin{matrix} {ψ_{i j}}^{r} (t) ≜ {(1 - \frac{f_{i j} (t) - ε}{1 - ε})}^{- ρ}, \end{matrix}

(4)

where $ρ \in ℝ^{+}$ , and in this paper, associated with $f_{i j} (t)$ in (2), it yields

\begin{matrix} {ψ_{i j}}^{r} (t) ≜ {(1 - \frac{\exp [- β (∥ ξ_{i} (t) - ξ_{j} (t) ∥ - a_{0})] - ε}{1 - ε})}^{- ρ} . \end{matrix}

(5)

It is straight forward that, whenever two mobile sensors approach to each other, the repulsive potential ${ψ_{i j}}^{r} (t)$ will continuously grow until $ε \to 1$ , where the potential ${ψ_{i j}}^{r} (t) \to \infty$ , so that intersensor collision is avoided. Similarly, to restrict all essential communication links within $f_{i j} (t) \geq ε$ for all $j \in {𝒩_{l}}^{[i]} (t)$ , we introduce an attractive potential function, denote as ${ψ_{i j}}^{a} (t)$ , where ${ψ_{i}}^{a} (t) = \sum_{j \in {𝒩_{l}}^{[i]} (t)} {ψ_{i j}}^{a} (t)$ . Specifically, we have

\begin{array}{l} {ψ_{i j}}^{a} (t) ≜ {(1 - \frac{f_{i j} (t) - φ}{ε - φ})}^{- ρ} \\ = {(1 - \frac{\exp [- β (∥ ξ_{i} (t) - ξ_{j} (t) ∥ - a_{0})] - φ}{ε - φ})}^{- ρ} . \end{array}

(6)

It can be seen from (6) that whenever two mobile sensors with critical communication links move away from each other, the attractive potential ${ψ_{i j}}^{a} (t)$ will continuously grow until $ε \to φ$ , where the potential ${ψ_{i j}}^{a} (t) \to \infty$ , so that the intersensor connection is guaranteed.

The proposed potential functions entitle us to assign each node i in the network a distributed control law, which is given as the combination of the negative gradients of the two potentials in the $ξ_{i} (t)$ direction

\begin{array}{l} u_{i}^{'} (t) ≜ - K_{r} \nabla_{ξ_{i} (t)} \sum_{j \in {𝒩_{p}}^{[i]} (t)} {ψ_{i j}}^{r} (t) \\ - K_{a} \nabla_{ξ_{i} (t)} \sum_{j \in {𝒩_{l}}^{[i]} (t)} {ψ_{i j}}^{a} (t) . \end{array}

(7)

It is easy to observed from (7) that, the potential force can become infinite between pairs of sensors whenever $f_{i j} (t) \to 1$ or $f_{i j} (t) \to ε$ . In practice, such unbounded actuation is unrealistic for most mobile sensor systems. In this paper, a piecewise-continuous function method is proposed with respect to sensors’ actuation to approach the objective of bounded input.

Denote $u_{i}^{m} (t)$ as the upper bound of velocity for node i, in particular, for homogeneous systems, we have $u_{i}^{m} (t) = u_{j}^{m} (t)$ , where $i \neq j & i, j \in 𝒱$ .

Definition 10.

Given a mobile sensor networks with fixed underlying network structure $𝒢^{*} (t)$ , a distributed piecewise-continuous control law is assigned to each mobile sensor as follows:

\begin{matrix} u_{i} (t) ≜ {\begin{cases} u_{i}^{'} (t), & u_{i}^{'} (t) \leq u_{i}^{m} (t), \\ u_{i}^{m} (t) \times {\hat{u}}_{i}^{'} (t), & u_{i}^{'} (t) > u_{i}^{m} (t), \end{cases} \end{matrix}

(8)

where ${\hat{u}}_{i}^{'} (t) = u_{i}^{'} (t) / ∥ u_{i}^{'} (t) ∥$ represents the unit vector of $u_{i}^{'} (t)$ .

The definition of piecewise-continuous control law gives rise to the development of hybrid connectivity control system ℂ, as is described in Figure 4. In the connectivity control system, the proposed DLRA algorithm will first take every updated location of the mobile sensors as its input matrix to calculate the topology of the network. Therefore, after every interaction process, the redundant communication links will be determined and updated. Meanwhile, the output value of network topology from DLRA will in turn be utilized by the motion controller in every mobile sensor to assign different control functions to every neighboring sensor according to their neighboring types, that is, physical or logical neighbor. And the final output of the system is sensors’ velocity and moving direction in the next step. The bounded velocity is implemented by comparing the output velocity from the controller with the designated maximum speed in the mobile sensor systems.

Figure 4

Control system ℂ for the dispersion of MASNs.

Now we can conclude the main result of this paper.

Theorem 11.

Given a MASNs with initially connected underlying network $𝒢 (t_{0})$ , the distributed connectivity control system ℂ guarantees that the connectivity of $𝒢 (t)$ is maintained, interagent collisions are avoided and sensors’ velocities are bounded for all time $t > t_{0}$ .

Proof.

See Appendix.

Furthermore, preserving connectivity without removing redundant communication links often results in a restricted network structure, as indicated in Figure 5(a). We argue that the restriction can be avoided by utilizing DLRA. In particular, from Corollary 7 we proved that the generated core structure (core structure is a subgraph of $𝒢 (t)$ that contains only the logical neighbor links) of $𝒢 (t)$ is a substructure of α -Lattice [4, 26] (pentagon), and the absence of cycle shorter than 5 guarantees that no mutual influences exist between any distinctive links. Therefore, for any two logical neighbors i and j, we have

\begin{matrix} u_{i j}^{'} (t) ≜ - K_{r} \nabla_{ξ_{i} (t)} {ψ_{i j}}^{r} (t) - K_{a} \nabla_{ξ_{i} (t)} {ψ_{i j}}^{a} (t), \end{matrix}

(9)

deriving the equilibrium distance $𝒟_{e} = ∥ ξ_{i} - ξ_{j} ∥$ between i and j from the denotation that $u_{i j}^{'} (t) = 0$ , we have

\begin{array}{l} K_{r} \nabla_{ξ_{i} (t)} {ψ_{i j}}^{r} (t) + K_{a} \nabla_{ξ_{i} (t)} {ψ_{i j}}^{a} (t) \\ = ρ K_{r} {(1 - \frac{f_{i j} (t) - ε}{1 - ε})}^{- ρ - 1} \cdot \frac{\nabla_{ξ_{i} (t)} f_{i j} (t)}{1 - ε} \\ - ρ K_{a} {(1 - \frac{f_{i j} (t) - φ}{ε - φ})}^{- ρ - 1} \cdot \frac{\nabla_{ξ_{i} (t)} f_{i j} (t)}{φ - ε} = 0 \\ \overset{\nabla_{ξ_{i} (t)} f_{i j} (t) \neq 0, ε < f_{i j} < 1}{\Rightarrow} \\ \frac{K_{r} {(1 - ((f_{i j} (t) - ε) / (1 - ε)))}^{- ρ - 1}}{1 - ε} \\ = \frac{K_{a} {(1 - ((f_{i j} (t) - φ) / (ε - φ)))}^{- ρ - 1}}{φ - ε} . \end{array}

(10)

Integrating (3) with the aforementioned equation and after some algebra manipulation, it yields

\begin{matrix} 𝒟_{e} = a_{0} - \frac{1}{β} \ln \frac{1 + ε \cdot Φ}{1 + Φ}, \end{matrix}

(11)

where $Φ = {((ε - 1) / (ε - φ))}^{ρ + 2} \cdot {(K_{a} / K_{r})}^{ρ + 1}$ .

Figure 5

Illustration of network structure (a) restricted link $(j, k)$ is observed without removal of redundant links; (b) a typical α-Lattice (pentagon) structure generated by DLRA, absence of external constrains.

The aforementioned ratiocinations bring us the following result.

Corollary 12.

Considering a MASNs with initially connected underlying network $𝒢 (t_{0})$ , where the position of vertices $ξ_{i} (t) \in ℝ^{2}$ . The evolution of the system under the control system ℂ can reach a set of condition $𝒦 (𝒟_{i j} (t)) ≜ {𝒟_{i j} (t) ∣ 𝒟_{i j} (t) \geq a_{0} - \ln ((1 + ε \cdot Φ) / (1 + Φ)) / β, i, j \in 𝒱}$ within finite time $t < \infty$ .

5. Simulations

To evaluate the performance of the proposed control system for the self-organized dispersion of mobile sensor networks, a variety of simulations have been conducted, and the results are presented in this section. The simulations are focused on the connectivity control and dispersion of mobile sensor networks in $ℝ^{2}$ and $ℝ^{3}$ spaces. General parameters are set as in Table 1.

Table 1

Simulation parameters.

Symbol	Quantity	Value
$Δ t$	Execution time slot	0.01 s
$Δ T$	Interval of consecutive switches	0.1 s
ε	Minimum sensing capability of normalized RSSI	10%
φ	Optimized sensing value of normalized RSSI	40%
$a_{0}$	Restricted radium (Reference distance)	2 m
β	Path loss (outdoor, 802.11b)	0.02
ρ	Exponential gain	0.7
$K_{r}$	Repulsive potential gain	2500
$K_{a}$	Attractive potential gain	200
$K_{c}$	Restoration potential gain	10
$u^{m} (t)$	Maximum sensor velocity	5 m/s⁻¹

First, to evaluate the correctness and efficiency of the proposed DLRA, a static simulation is conducted. In the first scenario, 15 static sensors are initially deployed within an area of 20 m × 20 m, as can be seen from Figure 6(a), where dense communication links are observed, after the execution of DLRA, the topology of the wireless sensor network is finally simplified with only 15 communication links (cf. Figure 6(b)). In case of large sensor networks, a 100 sensors scenario is then performed, the initial configuration of the network topology can be found in Figure 6(c). The final results from DLRA is shown in Figure 6(d), where the sensor network becomes extremely sparse with only a few redundancy.

Figure 6

Simulation results for DLRA. (a) Original topology for 15 nodes; (b) final topology for 15 nodes; (c) original topology for 100 nodes; (d) final topology for 100 nodes.

To evaluate the proposed connectivity control system ℂ. We first simulate the dispersion of 10 sensors initially located within 20 m × 20 m $ℝ^{2}$ space. The evaluation of mobile sensor network is shown as in Figures 7(a)–7(d). For the purpose of illustration, the diamonds represent mobile sensors, and the circles represent the semidistance (semidistance represents a value that is 5% shorter than half of the communication range. The use of it here is for the sake of facilitating the observation) of communication range. Sensors are under the communication range of each other if and only if the two corresponding circles overlap. The total trajectories of mobile sensors are shown in Figure 7(e), where the solid diamonds denote the initial position of the sensors, final position is represented as hollow ones, and the trajectory is shown as the dotted lines. Furthermore, upon removal of redundant communication links, sensors are dispersed into $ℝ^{2}$ space, and the network reaches its final configuration within 30 seconds (see Figure 8(a)). Moreover, the average velocity of the sensors is decreased from the peak that is 5 m s⁻¹ (see Figure 8(c)), the bounded velocity is guaranteed.

Figure 7

Simulation results for 2D distributed mobile multiagent dispersion. (a)–(d) Evolution snapshots for 10 nodes; (f)–(i) evolution snapshots for 100 nodes; (e) mobile sensor's trajectories in 10 nodes case; (d) mobile sensor's trajectories in 100 nodes case.

Figure 8

Simulation results for 2D distributed mobile multiagent dispersion. (a) The converge of average number of physical neighbors and logical neighbors during simulation in 10 nodes case; (b) the converge of average number of physical neighbors and logical neighbors during simulation in 100 nodes case; (c) average velocity of mobile sensors during simulation in 10 nodes case; (d) average velocity of mobile sensors during simulation in 100 nodes case.

We further conduct a simulation for 100 sensors to verify the scalability of the proposed approach. Similarly to the case of 10 sensors, sensors are initially location in a $200 m \times 200 m$ $ℝ^{2}$ space, the trajectories of networked sensors evolve as in Figures 6(f)–6(i). It is noticeable that the average degree of node in both simulations are between 2 and 3, this phenomenon indicates that an asymptotically 1-connectivity (graph is 1-connected if it contains only one path between any pair of distinct vertices) graph structure is generated during the evolution of the network, such that the final configurations are sparse with only trivial signal conflictions.

The self-organized dispersion of MASNs in $ℝ^{3}$ space is also evaluated with similar simulation methodology. Sensors locate within 95% communication range of each other is connected by a blue line (see Figure 9), networks with 10 and 100 sensors are all investigated, and in both case, the initial locations are within 20 m × 20 m × 20 m $ℝ^{3}$ space. Note that Corollary 12 may not hold in the case of 3-dimensional space coverage optimization, this is due to fact that the lower bound of the node degree cannot be obtained and a certain freedom of mobile sensors may not exist with respect to the uncertain structure of the networks. Therefore, we then conducted a simulation to study the coverage efficiency of proposed system ℂ with respect to different number of sensors. As it can be seen from Figure 10(c), with the aid of the proposed coverage enhancement system, 7 mobile sensors can cover an area up to 25000 m² in size (nearly the size of total 4 standard football fields), under the constrain of limited communication range ( $R = 100$ m). The interagent distances between logical neighbors are converged into a constant value, which is above the minimum distance derived from Corollary 12, and the distances between nonlogical neighboring sensors are strictly above the communication range (see either Figures 10(a) or 10(b)). The results verified the proposed control system in its capability of coverage enhancement. Moreover, as it can be seen from Figures 10(a) and 10(b), no interagent distance whatsoever can reach zero, which indicates that the proposed method can also effectively handle the issue of collision avoidance. Moreover, the simulation results unfolded in Figure 10 suggest that the lower bound of the neighbors’ distance can also be guaranteed in a network of 10 mobile sensors. The question of whether this is a common case in 3-dimensional space coverage enhancement will be investigated in our future research. Nonetheless, the capability of the coverage enhancement system in 3-dimensional space, for example, can cover up to 1.4 × 10⁶ m³ with 7 mobile sensors, is still fairly convincing.

Figure 9

Evolution trajectory (snapshot) of 3D distributed dispersion of mobile sensors in different scales. (a) $n = 20$ , $t = 1$ ; (b) $n = 20$ , $t = 5$ ; (c) $n = 20$ , $t = 15$ ; (d) $n = 20$ , $t = 30$ ; (e) $n = 100$ , $t = 1$ ; (f) $n = 100$ , $t = 15$ ; (g) $n = 100$ , $t = 40$ ; (h) $n = 100$ , $t = 80$ .

Figure 10

The efficiency of the proposed connectivity control system ℂ. (a) Interagents distances in case of 2-dimensional coverage optimization; (b) interagents distances in case of 3-dimensional coverage optimization; (c) coverage area in case of 2-dimensional coverage optimization; (d) coverage space in case of 3-dimensional coverage optimization.

It is worthwhile to notice that simulation results in $ℝ^{3}$ space are analogous to that in the case of $ℝ^{2}$ (see Figure 7), which entitles us to obtain the following conclusions.

Correctness

A variety of simulations in $ℝ^{2}$ and $ℝ^{3}$ spaces verified the correctness of the distributed control system for self-organized sensor dispersion, so that objectives can be achieved.

Sensibility

The required time for reaching the final configuration is distinctive in $ℝ^{2}$ and $ℝ^{3}$ spaces. The dimension-sensible property shows a better performance in spatial dispersion.

Sparseness

Despite of dimension and network capacity, the final configurations of the networks are always sparse with small node degrees.

6. Conclusions

Self-organized dispersion of mobile ad hoc sensor networks with guaranteed connectivity and collision avoidance is studied in this paper. A distributed self-organized control system combined with a local dynamic link removal algorithm, namely, DLRA, is proposed to reduce redundant communication links and regulate the dispersion of mobile sensors. The proposed control system can disperse a team of mobile sensors with guaranteed connectivity and collision avoidance, and the DLRA does not require access to the whole topology information, and thus, the proposed approach is scalable and will not invite excessive delays and communication overhead in large scale networks.

Several extensions to this presented work will be studied in future research: to apply the mobile sensor networks into indoor environment, we plan to study the dispersion of networked mobile sensors in nonconvex environments; the impact of wireless communication on the connectivity of multiagent system is another promising topic. The proposed approach can also be extended for dispersion in leader-follower system and potential applications in hazardous and battlefield environments.

Footnotes

Appendix

Acknowledgments

The work is cosponsored by Nature Science Foundation of China (Grant nos. 61272432, 61202508), and China Postdoctoral Science Foundation (Grant no. 2011M500243). The authors would like to gratefully acknowledge the constructive and thorough comments of the reviewers, which is very helpful for improving the quality of the paper. The authors appreciate the constructive suggestions in the simulation methodology from Professor Michael M. Zavlanos. They also thank Dr. Yan C. Wang for the enlightening discussions in topology control algorithms.

References

Rappaport

Wireless Communications, Principles and Practice 2002

Upper Saddle River, NJ, USA

Prentice Hall

Ludwig

Gini

Robotic swarm dispersion using wireless intensity signals

Proceedings of the 22nd Int'l Symposium on Distributed Autonomous Robotic Systems

July 2006

135 144

Dimarogonas

D. V.

Kyriakopoulos

K. J.

Inverse agreement protocols with application to distributed multi-agent dispersion

IEEE Transactions on Automatic Control 2009 54 3 657 663

2-s2.0-63449119908

10.1109/TAC.2008.2011009

Spears

W. M.

Spears

D. F.

Hamann

J. C.

Heil

Distributed, physics-based control of swarms of vehicles

Autonomous Robots 2004 17 2-3 137 162

2-s2.0-3142697699

10.1023/B:AURO.0000033970.96785.f2

Chen

Kumar

Lai

T. H.

Local barrier coverage in wireless sensor networks

IEEE Transactions on Mobile Computing 2010 9 4 491 504

2-s2.0-77649274317

10.1109/TMC.2009.147

Tahbaz-Salehi

Jadbabaie

Distributed coverage verification in sensor networks without location information

IEEE Transactions on Automatic Control 2010 55 8 1837 1849

2-s2.0-77954729913

10.1109/TAC.2010.2047541

Wang

Shen

Flocking based distributed self-deployment algorithms in mobile sensor networks

Journal of Parallel and Distributed Computing 2012 72 3 437 449

Cortes

Coverage optimization and spatial load balancing by robotic sensor networks

IEEE Transactions on Automatic Control 2010 55 3 749 754

2-s2.0-77949425359

10.1109/TAC.2010.2040495

Zhou

Liang

Xie

Multiobjective coverage control strategy for energy-efficient wireless sensor networks

International Journal of Distributed Sensor Networks 2012 2012 10

720734

10.1155/2012/720734

10.

Zhong

Cassandras

C. G.

Distributed coverage control and data collection with mobile sensor networks

IEEE Transactions on Automatic Control 2011 56 10 2445 2455

11.

Yang

Topology control and coverage enhancement of dynamic networks based on the controllable movement of mobile agents

Proceedings of the IEEE International Conference on Communication

June 2011

Kyoto, Japan

1 5

12.

Zavlanos

M. M.

Pappas

G. J.

Potential fields for maintaining connectivity of mobile networks

IEEE Transactions on Robotics 2007 23 4 812 816

2-s2.0-34548161470

10.1109/TRO.2007.900642

13.

Kim

Mesbahi

On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian

IEEE Transactions on Automatic Control 2006 51 1 116 120

2-s2.0-31344434725

10.1109/TAC.2005.861710

14.

Razafindralambo

Simplot-Ryl

Connectivity preservation and coverage schemes for wireless sensor networks

IEEE Transactions on Automatic Control 2011 56 2418 2428

15.

Zavlanos

M. M.

Pappas

G. J.

Distributed connectivity control of mobile networks

IEEE Transactions on Robotics 2008 24 6 1416 1428

2-s2.0-58249142713

10.1109/TRO.2008.2006233

16.

Yang

Freeman

R. A.

Gordon

G. J.

Lynch

K. M.

Srinivasa

S. S.

Sukthankar

Decentralized estimation and control of graph connectivity for mobile sensor networks

Automatica 2010 46 2 390 396

2-s2.0-74149084751

10.1016/j.automatica.2009.11.012

17.

Stergiopoulos

Kantaros

Tzes

Distributed control of mobile sensor networks under RF connectivity constraints

International Journal of Distributed Sensor Networks 2012 2012 7

741821

10.1155/2012/741821

18.

Notarstefano

Savla

Bullo

Jadbabaie

Maintaining limited-range connectivity among second-order agents

Proceedings of the American Control Conference

June 2006

Minneapolis, Minn, USA

2124 2129

2-s2.0-34047202699

19.

Yang

Liu

Connectivity control of mobile multi-robot networks

Proceedings of the IEEE/ASME International Conference on Advanced Intelligent Mechatronics

July 2010

Montreal, Canada

123 128

2-s2.0-79951597961

10.1109/AIM.2010.5695798

20.

Distributed cooperative coverage and connectivity maintenance for mobile sensing devices

Proceedings of the 48th IEEE Conference on Decision and Control

December 2009

Shanghai, China

7891 7896

2-s2.0-77950829946

10.1109/CDC.2009.5399562

21.

Ajorlou

Momeni

Aghdam

A. G.

Connectivity preservation in a network of single integrator agents

Proceedings of the 48th IEEE Conference on Decision and Control

December 2009

Shanghai, China

7061 7067

2-s2.0-77950837335

10.1109/CDC.2009.5400614

22.

Xing

Wang

Xie

Jia

Rendezvous planning in wireless sensor networks with mobile elements

IEEE Transactions on Mobile Computing 2008 7 12 1430 1443

2-s2.0-56049108109

10.1109/TMC.2008.58

23.

Yang

J. Y.

Liu

A model based connectivity improvement strategy for vehicular ad hoc networks

Proceedings of the 76th IEEE Vehicular Technology Conference

September 2010

Ottawa, Canada

2-s2.0-78649393003

10.1109/VETECF.2010.5594525

24.

Wattenhofer

Zollinger

XTC: a practical topology control algorithm for ad-hoc networks

Proceedings of the 18th IEEE International Parallel & Distributed Processing Symposium

2004

Santa Ana, Calif, USA

216 222

25.

Jawahar

Radha

Sharath Kumar

Capacity-preserved, energy-enhanced hybrid topology management scheme in wireless sensor networks for hazardous applications

International Journal of Distributed Sensor Networks 2012 2012 12

280932

10.1155/2012/280932

26.

Olfati-Saber

Flocking for multi-agent dynamic systems: algorithms and theory

IEEE Transactions on Automatic Control 2006 51 3 401 420

2-s2.0-33644997478

10.1109/TAC.2005.864190