Distributed Movement Control for Building a Ring in Mobile Wireless Sensor Networks

Abstract

Many applications in wireless sensor networks require some sensors to form a ring or multiring-based shape in the target area, such as intrusion detection, border surveillance, routing overlay formation, and network full coverage. In this paper, we study the problem of sensor redistribution to build a ring-based shape for mobile sensor networks. We first give the theoretical analysis on what is optimal sensor movement with the given random deployment. Then, we propose a fully distributed movement control algorithm to achieve ring-based shape for mobile sensor networks. We formally prove that our algorithm can achieve a ring-based distribution within finite time. We also present the procedures of applying our algorithm to form multiring-based distribution. Finally, we present extensive simulations to verify that our approach outperforms other schemes in terms of both the moving distance and convergence time.

1. Introduction

A typical wireless sensor network (WSN) is composed of hundreds to thousands of sensor nodes reporting their data to the information collector, referred to as the sink node. Sensor nodes are usually of low-cost and low-power, having limited sensing, computing, and communication capabilities. In recent years, with the rapid progress in advanced VLSI and radio frequency (RF) technologies, WSNs have attracted lots of interest due to their potential use in various applications such as military surveillance, environment monitoring, fire detection, target tracking, and emergency navigation [1–4].

Ring-based shape is an important formation for many practical applications of WSN, such as a ring-based overlay among the target area [5, 6] to forward data, which can enhance the data transmission efficiency and avoid the energy hole problem for the whole network. In addition, some applications require ring-based barrier among the border to detect illegal intrusion or radiation spills around nuclear borders or monitor the spread of forest fire and so on [7]. Generally, resource-limited sensor nodes are dropped from airborne vehicles for remote surveying of unattended environment without a preconfigured infrastructure [8]. Those sensor nodes are typically left unattended and remain static after initial deployment. Sometimes, establishing ring-based shape over a hostile or dangerous target area could be a daunting task. To illustrate the point, imagine the following scenario: where static sensors are deployed for monitoring wildfire applications, events such as winds, malicious attacks, and sensor failures are likely to cause network partitions. Thus, it is necessary to make use of mobile sensors, such as attaching sensors to robots or vehicles [9], or self-propel via springs [10] or wheels [11].

Inspired by the potential applications of sensor mobility, there have been some research efforts on the sensor redistribution for mobile sensor network [12–16]. However, due to the power-constrained batteries, it is a critical consideration in designing energy conserving movement plan for each sensor node. Considering that energy consumption in moving is larger than in communication and processing, we are motivated to study the optimal sensor redistribution problem to form a ring-based shape while minimizing total moving distance. Generally, the sensor movement control can be classified into two types: centralized execution and distributed execution. In centralized execution, the movement plan is calculated in a sink node or cluster node, and the final results are broadcast to all mobile sensors. However, the selection of cluster node and the exchange of global location information during dynamic movement would put a heavy traffic burden. Hence, distributed movement execution to form a ring-based shape should be researched, in which each sensor updates its position only using local information from its neighbour sensors, thus saving energy and ensuring scalability.

In this paper, we try to investigate the problem of moving sensors to achieve a ring-based shape with minimum moving distance. Firstly, the optimal sensor layout with random deployment is presented. Then, a fully distributed sensor redistribution algorithm for mobile sensor networks is proposed. Formally, our algorithm is proven to provide ring-based distribution and terminates within a finite time. Simulation results are presented to show the effeteness of our algorithm. The rest of the paper is organized as follows. Section 2 discusses the related literature. Section 3 describes the network model, problem formulation, and theoretical analysis on optimal sensor redistribution. A fully distributed sensor redistribution strategy is proposed in Section 4. Section 5 presents the simulation results for our algorithms, and Section 6 concludes our paper.

2. Related Work

More recently, there has been growing interest in optimizing the sensor redistribution to improve network performance. Aiming at increasing network coverage, the authors in [12] proposed a potential-field-based approach to deployment, which does not require model of environment or centralized control. In [16], the authors assumed there were virtually attractive and repulsive forces among sensors. Using these virtual forces, mobile sensor nodes spread throughout the target area with a uniform distribution such that the network coverage rate is maximized. In [17], the authors propose a NSGA-II-based approach to redistribute mobile sensors to achieve full network coverage as well as to eliminate energy hole. In [18], the authors proposed a Voronoi diagram-based distribution model, in which each sensor iteratively calculates its Voronoi polygon to detect the coverage holes and moves to a better position to improve the coverage rate. In [15], the authors proposed three independent algorithms (VEC, VOR, and MiniMax), by pushing or pulling nodes to cover the gaps based on virtual forces. These three algorithms have similar performance in a bounded area, whereas only VEC algorithm can be used in both unbounded and bounded areas. In [19], the authors investigate how to move sensors to some locations while still preserving the degree of coverage under partially controlled placement. In [20], the sensing field was divided into grids, and the sensors moved from high-density grids to low-density ones such that the densities remain constant. However, all the above efforts only concern maximum network coverage and cannot directly apply to ring-based applications.

The self-redistribution to form a ring-based shape is related to a well-studied problem in the field of swarm robotics, such as uniform circle formation [21, 22]. In this problem, very simple robots are required to uniformly place themselves on the predefined ring. The main difference between their work and ours is that, in their work, the energy consumption is not the main research target. Concerning that ring-based shape is important for WSNs, some approaches have also been proposed to build ring-based shape for both static and dynamic WSNs. In [23], the authors proposed a multilevel virtual ring-based framework for wireless sensor network, which can support the peer-to-peer applications for WSNs. However, how to construct multilevel rings among the target area is not considered. In [3], the authors propose a ring overlay construction algorithm by selecting only a subset of sensors for static WSNs. In [6], rings on the basis of relays are also used to eliminate energy hole of WSNs. Assuming all sensors are attached on mobile robotics, the authors in [24] studied the problem of self-deploy mobile sensors to satisfy a ring-based connection. Since the barrier coverage is a typical application of WSNs, the authors in [25] proposed a hybrid Gaussian-ring deployment to provide a higher intrusion detection probability for attacks at the edge of the network. It has recently come to our attention that the authors in [26] have proposed a decentralized redistribution control algorithm to form a ring-based barrier surrounding the region for mobile wireless sensor network. In their algorithm, each node iteratively collects neighbouring information and updates its position using virtual force. The major differences between their work and ours lie however in that, (i) in our work, we intend to achieve a ring-based shape with the minimum moving distance. We have given a theoretical analysis on what is optimal sensor layout to provide a ring-based distribution with the minimum moving distance; (ii) our distributed sensor redistribution algorithm is based on the above optimization analysis and is hence theoretically founded. As will be shown in Section 5, our algorithm requires fewer working rounds and moving distances in achieving a ring-based distribution.

3. Network Model and Problem Formulation

3.1. Network Model

In this section, we present our network model and basic assumptions. Assume that a set of N homogeneous mobile sensors are deployed in a circular area with radius $r_0$ to monitor some physical phenomenon. We refer to the set of deployed sensors as $S=\{s_1,s_2,\dots ,s_N\}$ . Each sensor node i $(\mathrm{1}\le i\le N)$ has an ID and a fixed transmission range $R_c$ and is aware of its location $(x_i,y_i)$ . Note that the location awareness is impractical in a highly dense network. In recent years, many research efforts have been proposed to address the localization problem [27]. However, this requirement can be relaxed slightly in our work if each node is aware of its relative location to the neighbors. We have the following definition regarding ring-based distribution.

Definition 1 (ring-based distribution).

A ring-based distribution is a circle among the target area, which starts from an initial random placement on the target area. And after redistribution control, the sensors must lie on a predefined ring in an equally spaced manner within finite time, as shown in Figure 1.

Let the angular coordinate of sensor i be $(r,{\theta }_i)$ ; if the set of sensors guarantee a ring-based distribution, we have

$$\begin{array}{cc}& r=r_{\mathrm{0}}.\end{array}$$

(1)

Since these sensors are distributed along the ring in an equalized way, as shown in Figure 1(a), the angle between any two nearest neighbor sensors can be calculated as

$$\begin{array}{cc}& {\theta }_{\text{opt}}=\frac{\mathrm{2}\pi }{N}.\end{array}$$

(2)

Define the angle between sensors i and j as ${\theta }_{ij}$ , which can be calculated as

$$\begin{array}{cc}& {\theta }_{ij}={\theta }_j-{\theta }_i.\end{array}$$

(3)

If all sensors form a ring-based distribution and sensor j is the sensor i's nearest neighbor, we have

$$\begin{array}{cc}& \left|{\theta }_{ij}\right|={\theta }_{\text{opt}}.\end{array}$$

(4)

Figure 1

Random deployment and ring-based shape.

3.2. Problem Formulation

As sensors are randomly deployed, the initial distribution may be distributed along the predefined ring with random offsets. Our movement control for ring-based distribution mainly focuses on moving these deviated sensors to the ring. To avoid consuming much energy during the moving process, the movement distance should be reduced, to efficiently utilize network energy and extend network lifespan.

Define the coordinate in $x\text{-}y$ -axis of sensor $i\in N$ before and after movement control as $(r,{\theta }_i^{\prime })$ and $(r_0,{\theta }_i)$ . Assume each sensor moves from its initial location to final location directly; thus the moving distance of sensor i is

$$\begin{array}{cc}& f\left(i\right)=\sqrt{{\left(r_{\mathrm{0}}*\cos {\theta }_i-r*\cos {\theta }_i^{\prime }\right)}^{\mathrm{2}}+{\left(r_{\mathrm{0}}*\sin {\theta }_i-r*\sin {\theta }_i^{\prime }\right)}^{\mathrm{2}}}.\end{array}$$

(5)

Here, we assume that all sensors move to their final location with no oscillation. However, if one sensor moves to its final location with oscillation, the eventual moving distance is larger than $f(i)$ .

Definition 2 (optimal movement control for a ring-based distribution).

Let all sensors be first randomly deployed with the initial coordinates $\{(r,{\theta }_i^{\prime }),\hspace{0.17em}\hspace{0.17em}i=\mathrm{1},\dots ,N\}$ , and the predefined ring is located at $(\mathrm{0,0})$ with radius $r_0$ . The optimal movement control for a ring-based distribution means to find an optimal movement plan for each mobile sensor, such that after movement control, the distribution of all sensors forms a ring-based shape, and the total moving distance of the entire network is minimized. Without loss of generality, the above problem can be formalized as

$$\begin{array}{c}\mathrm{Min}\hspace{1em}{\displaystyle \sum }_{i=\mathrm{1}}^{N}f\left(i\right)\\ \text{s}.\text{t}.\hspace{1em}\hspace{0.17em}r=r_{\mathrm{0}}\\ \exists j\in N:\left(\left({\theta }_j\le {\theta }_i\right)\wedge \left(\left|{\theta }_{ij}\right|={\theta }_{\text{opt}}\right)\right),\hspace{1em}\forall i=\mathrm{1},\dots ,N,\hspace{0.17em}i\ne j,\\ \exists j\in N:\left(\left({\theta }_j\ge {\theta }_i\right)\wedge \left(\left|{\theta }_{ij}\right|={\theta }_{\text{opt}}\right)\right),\hspace{1em}\forall i=\mathrm{1},\dots ,N,\hspace{0.17em}i\ne j,\\ {\theta }_{\text{opt}}=\frac{\mathrm{2}\pi }{N},\\ {\theta }_{ij}={\theta }_j-{\theta }_i,\\ f\left(i\right)=\sqrt{{\left(r_{\mathrm{0}}*\cos {\theta }_i-r*\cos {\theta }_i^{\prime }\right)}^{\mathrm{2}}+{\left(r_{\mathrm{0}}*\sin {\theta }_i-r*\sin {\theta }_i^{\prime }\right)}^{\mathrm{2}}},\end{array}$$

(6)

where $(r,{\theta }_i^{\prime })$ and ( $r_0,{\theta }_i$ ) are the angular coordinates of sensor i before and after redistribution and ${\theta }_{\text{opt}}$ is the optimal angle when all sensors form a ring-based distribution. Constraints (1), (2), (3), and (4) ensure that after redistribution all sensors are lying on the predefined ring, and the angle between any two neighbour sensors is equal to ${\theta }_{\text{opt}}$ , which means all sensors are lying on the ring in an equally spaced manner.

3.3. Optimal Redistribution

Similar to [24], we assume that when sensors are randomly located on the ring $r_0$ , these sensors are restricted to move along the ring during movement control. This movement restriction will cause the moving trajectory of each sensor to be similar like an arc instead of a straight line, and the total moving distance is little larger than moving along a straight line. However, this restriction can always satisfy the first constraint of the optimization problem and reduce the design complexity of the movement control. We have the following theorem regarding the final optimum sensor layout in achieving minimum moving distance for a ring-based distribution.

Theorem 3.

Let the initial randomly deployed sensor set along the predefined ring be $s_1,s_2,\dots ,s_N$ , and let their angular coordinates satisfy ${\theta }_1\le {\theta }_2\le \cdots \le {\theta }_{N-1}\le {\theta }_N$ . If all sensors are allowed to move along the ring, and the sensors $s_1,s_2,\dots ,s_N$ in angular coordinates still preserve initial order after movement control, which means ${\theta }_1^{\prime }\le {\theta }_2^{\prime }\le \cdots \le {\theta }_{N-1}^{\prime }\le {\theta }_N^{\prime }$ , the minimum total moving distance can be achieved.

Proof.

Let the total distance on misordering movement be $d_1$ , and let the total distance with no misordering movement be $d_2$ . This theorem can be proved by contradiction. Assume that there are two misordering nodes after movement control; $d_1<d_2$ is possible.

Without loss of generality, for two initial deployed nodes i and j, where $i\le j$ , we have ${\theta }_i\le {\theta }_j$ . After movement control, these two nodes are moving to two new locations $(r_0,{\theta }_1)$ and $(r_0,{\theta }_2)$ , where ${\theta }_1\le {\theta }_2$ . According to the difference of the angular coordinate, one of the following cases may happen, as shown from (A1) to (A6):

• (A1)

${\theta }_{\mathrm{1}}\le {\theta }_i\le {\theta }_j\le {\theta }_{\mathrm{2}}$

In this case, if misordering of these two nodes happens, we have ${\theta }_i^{\prime }={\theta }_2$ , ${\theta }_j^{\prime }={\theta }_1$ , and the moving distance of $d_1$ is

$$\begin{array}{l}{d}_{\mathrm{1}}=r_{\mathrm{0}}*\left(\left|{\theta }_i^{\prime }-{\theta }_i\right|+\left|{\theta }_j^{\prime }-{\theta }_j\right|\right)\\ =r_{\mathrm{0}}*\left({\theta }_{\mathrm{2}}-{\theta }_i+{\theta }_j-{\theta }_{\mathrm{1}}\right).\end{array}$$

(7)

If no misordering happens, we have $x_i^{\prime }=x_1$ , $x_j^{\prime }=x_2$ , and the total moving distance of $d_2$ is

$$\begin{array}{cc}& d_{\mathrm{2}}=r_{\mathrm{0}}*\left({\theta }_i-{\theta }_{\mathrm{1}}+{\theta }_{\mathrm{2}}-{\theta }_j\right);\end{array}$$

(8)

thus

$$\begin{array}{cc}& d_{\mathrm{1}}-d_{\mathrm{2}}=\mathrm{2}*r_{\mathrm{0}}*\left({\theta }_j-{\theta }_i\right)\ge \mathrm{0}.\end{array}$$

(9)

• (A2)

  ${\theta }_i\le {\theta }_{\mathrm{1}}\le {\theta }_j\le {\theta }_{\mathrm{2}}$

In this case,

$$\begin{array}{cc}& d_{\mathrm{1}}-d_{\mathrm{2}}=\mathrm{2}*r_{\mathrm{0}}*\left({\theta }_j-{\theta }_{\mathrm{1}}\right)\ge \mathrm{0}.\end{array}$$

(10)

• (A3)

  ${\theta }_i\le {\theta }_{\mathrm{1}}\le {\theta }_{\mathrm{2}}\le {\theta }_j$

In this case,

$$\begin{array}{cc}& d_{\mathrm{1}}-d_{\mathrm{2}}=\mathrm{2}*r_{\mathrm{0}}*\left({\theta }_{\mathrm{2}}-{\theta }_{\mathrm{1}}\right)\ge \mathrm{0}.\end{array}$$

(11)

• (A4)

  ${\theta }_i\le {\theta }_j\le {\theta }_{\mathrm{1}}\le {\theta }_{\mathrm{2}}$

In this case,

$$\begin{array}{cc}& d_{\mathrm{1}}-d_{\mathrm{2}}=\mathrm{0}.\end{array}$$

(12)

• (A5)

  ${\theta }_{\mathrm{1}}\le {\theta }_{\mathrm{2}}\le {\theta }_i\le {\theta }_j$

In this case,

$$\begin{array}{cc}& d_{\mathrm{1}}-d_{\mathrm{2}}=\mathrm{0}.\end{array}$$

(13)

• (A6)

  ${\theta }_{\mathrm{1}}\le {\theta }_i\le {\theta }_{\mathrm{2}}\le {\theta }_j$

In this case,

$$\begin{array}{cc}& d_{\mathrm{1}}-d_{\mathrm{2}}=\mathrm{2}*r_{\mathrm{0}}*\left({\theta }_{\mathrm{2}}-{\theta }_i\right)\ge \mathrm{0}.\end{array}$$

(14)

In all these cases, $d_1<d_2$ cannot hold; thus the theorem is proved.

4. Distributed Movement Control

Theorem 3 implies that there exists an optimal solution for the ring-based distribution when the final layout still preserves the initial order of angular coordinates. Now, the next issue to be addressed is how to remove nodes from a random layout to form such an optimal layout. Due to the uncertainty of deployment, some sensor nodes may deviate from the predefined ring with radius $r_0$ . Assume that all sensors know the predefined ring of the region, and these sensors which are deviated from the ring should move to the ring first. Assume that each sensor is aware of its initial location and the intended ring, and those deviated sensors are allowed to move to the ring along the vertical direction, which results in the minimum moving distance and energy consumption, as shown in Figure 2.

Figure 2

Moving to the ring.

When all the sensors are lying on the ring, these sensors implement distributed moving control along the ring. The basic idea of moving sensors along the ring is to adjust the angle between any two neighbours to ${\theta }_{\text{opt}}$ , which is based on the interleaved execution including two fundamental activities: starter generation and neighbour moving.

4.1. Starter Generation

The process of moving sensors along the ring commences by randomly selecting some sensors as the starting node. In our paper, any node whose residual energy exceeds a predetermined power threshold $P_t$ will become a starter node with probability p. In general, $P_t$ is set to a value so as to ensure that the sensor can remain powered on with high probability until the end of neighbour moving execution. Then set a back-off timer of ${\tau }_1$ (sec), where ${\tau }_1$ is distributed uniformly in $[0,T]$ . When the timer expires, the node broadcasts a starter-acting message meanwhile to gather the information of its neighbours. The starter-acting message is an array of $〈$ sensorID, timeStamp $〉$ , indicating the ID of starting node and its current time. If the initial candidate node receives starter-acting messages before the back-off time finishes, its timer is cancelled and this node acts as an ordinary one, and then it replies to the starter node with the oldest timestamp and neglects other starter-acting messages. The reply message is an array of $〈$ sensorID, sensorLocation, starterID $〉$ , indicating the ID of ordinary node, its location, and its source starter node. This method helps to avoid many neighbour sensors becoming starting nodes at the same time effectively. Similar to the local data gathering [28], assume that each ordinary node replies to the starter node via broadcast, and each starter node can gather the information of all its neighbors without collision. As our algorithm is executed in a distributed manner, communication failures only slightly affect the convergence speed. Thus, the case with communication failures can be ignored.

4.2. Neighbour Moving

After the starter node gathers information from all its neighbours, it generates a moving message and moves its neighbours to form a perfect layout. The moving message is an array of $〈$ sensorID, desiredLocation $〉$ , indicating the ID of moving neighbours and its desired coordinates. However, some starters may have more than one neighbour node. In our algorithm, the nearest neighbour is taken first in the current working iterations. If a starter k, with its angular coordinates $(r_{\mathrm{0}},{\theta }_k)$ and the nearest neighbour sensor m, detects their angle ${\theta }_{mk}<{\theta }_{\text{opt}}$ , then the following movement is executed. The starter k pulls m with an angle of $\left|{\theta }_{\text{opt}}-{\theta }_{mk}\right|$ . Considering that node m may be in the right or left side of node k, then the following situations are executed: if node m is on the right side of node k, the desiredLocation of m is updated as $(r_0,{\theta }_m^{\prime })=(r_0,{\theta }_m+{\theta }_{\text{opt}}-{\theta }_{mk})$ . Otherwise, the desiredLocation of m is updated as $(r_0,{\theta }_m^{\prime })=(r_0,{\theta }_m-{\theta }_{\text{opt}}+{\theta }_{mk})$ . Since there may already exist some other sensors q in the location $(r_0,{\theta }_m^{\prime })$ , to satisfy the initial order of their angular coordinate, the following cases should be dealt with: if ${\theta }_m^{\prime }<{\theta }_m$ and node m is moving to the left side, then the node with smaller initial angular coordinate among q and m should further move with a very small deviation ε along the moving orientation as m. Otherwise, m is moving to the right side, and the node with larger initial angular coordinate among q and m should further move with a very small deviation ε along the moving orientation as m.

After moving the first nearest neighbour to the optimal location, the starter continues to move its current nearest neighbour to the optimal locations. When the angle between the starter and its current nearest neighbour equals ${\theta }_{\text{opt}}$ , the starter stops moving the neighbours, passes the token to its neighbours, acts as an ordinary, and sets its state in wait state.

As for an ordinary node, anytime when hearing messages from one starter node, it will wake up from the wait state. Then, the ordinary node first decides the type of the received message, and the following situations are executed: if the received message is a starter-acting message, the reply messages will be sent to the starter node; if the received message is a moving message, the ordinary node will move to the desired location, and additional movement adjustment will be executed if needed; if the received message is a token message, the ordinary node will become a new starter and will start moving its neighbours to optimal locations.

The detailed procedure for the execution of a starter node is shown in Algorithm 1. In summary, there are four messages used in our algorithm, including starter-acting message, moving message, token message, and reply message, where the last message is transmitted by ordinary node, and others are transmitted by starter node. A node acts as a starter only in one of the two following cases: (i) a node is a starter one which is generated in starter generation execution; (ii) a node is an ordinary one and hears the token messages from its previous starter.

Algorithm 1: Execution of a starter node.

Step  1. //energy decision

If Remain energy > $P_t$ and Rand $(\mathit{0,1})<p$

 Select a back off timer ${\tau }_1$ = rand ( $0,T$ );

Step  2. //back off

If no start-acting messages is heard in ${\tau }_1$

 Act as starter node and broadcast starter-acting message;

Elsegoto  Step  6;

Step  3. Receive reply messages from ordinary nodes and

    gather the information of all its neighbour sensors;

Step  4. Broadcast moving messages and move neighbours;

Step  5. //token passing

If the nearest neighbour is in optimal location

 Broadcast token messages and pass the token to

 the nearest neighbour sensors;

Else goto  Step  4;

Step  6. Act as an ordinary node;

Step  7. Set its state in wait state;

Figure 3 shows an example of the execution of the first two activities. Figure 3(a) depicts the initial configuration, with 4 sensors randomly located on the predefined ring, and sensor $s_2$ acts as the starter node and moves its first two nearest neighbour sensors $s_1$ and $s_3$ to the optimal location. In Figure 3(b), the starter moves its current nearest neighbour $s_4$ to the optimal location. Since there already exists node $s_3$ in this location, and the initial angular coordinate of $s_4$ is larger than that of $s_3$ , then $s_{\mathrm{4}}$ further moves very small deviation ε. Figure 3(c) depicts the starter configuration after the moving activity of $s_2$ . Since the angle between $s_2$ and its current nearest neighbour equals ${\theta }_{\text{opt}}$ , $s_2$ stops moving and passes token to $s_1$ and $s_3$ . In Figure 3(d), $s_1$ and $s_3$ become new starters, and $s_3$ moves $s_4$ to the optimal location. Note that finally achieved distribution is a perfect ring-based distribution, and the sensors in angular coordinate still preserve the initial order after movement, thus having the minimum total moving distance, as shown in Figure 3(e).

Figure 3

An example of starter generation and neighbour moving.

Theorem 4.

The sensor redistribution algorithm can terminate within a finite time and achieve a perfect uniform layout along the ring.

Proof.

In order to prove the theorem, it suffices to prove that, once the algorithm reached the stable state when the angle between any two neighbour sensors equals ${\theta }_{\text{opt}}$ , the sensors lying on the ring should be fixed.

Let S denote the set of sensors distributed in the ring. After reordering these sensors according to the angular coordinate, we rename S as ( ${\theta }_1,{\theta }_2,\dots ,{\theta }_N$ ). Define ${\beta }_i$ as the angle of two adjacent nodes in S. To ensure ${\beta }_i$ does not exceed ${\theta }_{\text{opt}}$ , we define ${\beta }_i$ as

$$\begin{array}{cc}& {\beta }_i=\{\begin{array}{cc}{\theta }_{i+\mathrm{1}}-{\theta }_i,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}({\theta }_{i+\mathrm{1}}-{\theta }_i\mathrm{\hspace{0.17em}\hspace{0.17em}}\le {\theta }_{\text{opt}}),\hfill \\ \mathrm{0},\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(15)

Define $f(S)$ as the sum of ${\beta }_i$ ,

$$\begin{array}{cc}& f\left(S\right)={\displaystyle \sum }_{i=\mathrm{1}}^{N-\mathrm{1}}{\beta }_i.\end{array}$$

(16)

Based on the above definition, if all the sensor nodes are distributed in an optimal layout, we can get the upper bound for $f(S)$ as $2\pi -{\theta }_{\text{opt}}$ .

Now consider the change of ${\beta }_i$ in one working round. At first, define $f(S)$ in working round t as $f(S_t)$ ; then in working round $t+1$ , the following three cases may occur, as shown from (B1) to (B3).

• (B1)

Node i is a starter, and the nearest neighbour is in its communication radius. Assume that node $i+1$ is its neighbour in the right side; then in one working round, node $i+1$ moves to the optimal location of node i, and ${\beta }_i$ is increased to ${\theta }_{\text{opt}}$ , as shown in Figure 4(a). Thus, we have $f(S_t+1)>f(S_t)$ .

(B2)

Node i is an ordinary node, and the current starter is its neighbour j ( $1<j<i$ ). As ${\beta }_i$ < ${\theta }_{\text{opt}}$ , then in one working round, the starter j will move all the nodes between i and j crossing node i. Without loss of generality, assume only one sensor is within i and j, and the distribution after moving node $i-1$ is ( $1,2,\dots ,j,i,i-1,i+1,\dots ,N$ ), as shown in Figure 7(b). Since the starter will continue moving i to its optimal location, and the initial angular coordinate of i is larger than $i-1$ , node i will further move a very small deviation ε, and the sensor distribution in round $t+1$ is updated as $S_{t+1}=(1,2,\dots j,i-1,i,i+1,\dots ,N)$ . In this distribution, ${\theta }_{j,i-1}=d_{\text{opt}}$ , ${\theta }_{i-1,i}=\epsilon$ . Thus $f(S_{t+1})$ can be calculated as

$$\begin{array}{l}f\left(S_{t+\mathrm{1}}\right)=\left({\displaystyle \sum }_{k=\mathrm{1}}^{j-\mathrm{1}}{\theta }_k\right)+{\theta }_{j,i-\mathrm{1}}+{\theta }_{i-\mathrm{1},i}+\left({\displaystyle \sum }_{k=i}^N{\theta }_k\right)\\ =\left({\displaystyle \sum }_{k=\mathrm{1}}^{j-\mathrm{1}}{\theta }_k\right)+{\theta }_{\text{opt}}+\epsilon +\left({\displaystyle \sum }_{k=i}^N{\theta }_k\right),\end{array}$$

(17)

 

while

$$\begin{array}{cc}& f\left(S_t\right)=\left({\displaystyle \sum }_{k=\mathrm{1}}^{j-\mathrm{1}}{\theta }_k\right)+{\theta }_j+{\theta }_{i-\mathrm{1}}+\left({\displaystyle \sum }_{k=i+\mathrm{1}}^N{\theta }_k\right).\end{array}$$

(18)

 

Since ${\theta }_j+{\theta }_{i-\mathrm{1}}<{\theta }_{ij}<{\theta }_{\text{opt}}$ , thus we have

$$\begin{array}{cc}& f\left(S_{t+\mathrm{1}}\right)>\left(S_t\right).\end{array}$$

(19)

(B3)

If i is an ordinary or a starter node with ${\theta }_i=0$ , which means that there exist no neighbour sensors in its communication radius, if this happens, there is at least one node having neighbours in its communication radius based on symmetry. Assume node k has at least one neighbour in its communication radius ( $1<k<N,k\ne i$ ). As k meets one of the above two situations of (B1) or (B2), after one working round, we will also have $f(S_{t+1})>(S_t)$ .

Apparently, in all the cases, $f(S_t)$ is an increasing function on rounds t. Therefore, after running a finite number of rounds, $f(S_t)$ would achieve its upper bound and finally form a perfect ring distribution. This completes the proof of Theorem 4.

Figure 4

Illustration of node distribution in one working round.

4.3. Multiring-Based Distribution

Define the distance between any two neighbour sensors as $d_{\text{opt}}$ and the total length of the multirings as $l_{\text{total}}$ ; the desired number of sensors to form multiring-based distribution can be calculated as

$$\begin{array}{cc}& N_{\text{total}}=\frac{l_{\text{total}}}{d_{\text{opt}}}.\end{array}$$

(20)

Since all $N_{\text{total}}$ sensors are randomly deployed in the target area, the deployment uncertainty may cause the number of deployed nodes to be more or fewer than the ring really needs. In order to apply our algorithm to form a multiring-based distribution, we first should move the needed number of sensors to all rings. Aiming at reducing the consumed energy during the moving process, the nodes are only allowed to move to the adjacent rings. Define the number of sensors deployed in ring $R_i$ as $D_i$ and the desired number of sensors in $C_i$ as $E{D}_i$ . Sensor redeployment to form an n-ring-based distribution can be executed in Algorithm 2.

Algorithm 2: Multiring-based distribution.

For each ring $R_i$ , $i\in (\mathrm{n},\mathrm{n}-\mathrm{1},\dots ,\mathrm{1})$

 if   $D_i>{ED}_i$

 Select $D_i-{ED}_i$ nodes close to $R_{i-1}$ from $R_i$ ;

 Move these nodes straight to $R_{i-1}$ and

 update $D_{i-1}=D_{i-1}+(D_i-{ED}_i)$ ;

 Applying our distributed algorithm to form a ring

 based distribution for ring $R_i$ .

Elseif   $D_i\le {ED}_i$

 Select ${ED}_i-D_i$ nodes close to $R_i$ from $R_{i-1}$ ;

 Move these nodes straight to $R_i$

 and update $D_{i-1}=D_{i-1}+({ED}_i-D_i)$ ;

 Applying our distributed algorithm to form a ring

 based distribution for ring $R_i$ .

Endif

5. Evaluation and Experimental Results

In this section, we will present the simulation results of our algorithm. All simulations are executed in Matlab 7.0. Two metrics, including the average moving distance and algorithm convergence time (measured by the working rounds), are imported to evaluate the performance of the proposed algorithm. Here, the working round is calculated by the number of tokens totally passed. And similar to sensor movement in [26], we further assume that all sensors move to the desired location along the ring simultaneously, and the moving speed is not considered in our paper.

At first, 20 mobile sensors are randomly deployed around a predefined ring $x^2+y^2={45}^2$ . Figure 5(a) shows their initial positions, Figure 5(b) indicates the nodes moving to the predefined ring, and Figure 5(c) shows the final distribution. From Figure 5, we can see that the sensors initially and randomly distributed over the target area and eventually formed a ring-based distribution. And we also can see that the final distribution still preserves the initial order of their angular coordinate after movement control, which means the minimum moving distance is achieved. Similar results were also obtained when the sensors were initially placed in a compact region, as shown in Figure 6. After applying our algorithm, the sensors also form a ring-based distribution.

Figure 5

Illustration of network distribution in different steps with random deployment on the area.

Figure 6

Illustration of network distribution in different steps with random deployment on a compact region.

Figure 7

Illustration of forming multiring distribution in different steps.

Considering that some application may require sensors to form multiple rings among the target area, such as to form a full coverage or form a multilevel barrier, we also test the performance of our algorithm in forming multirings. In this simulation, we randomly deployed 81 sensors among a circular area with radius 100, and each sensor has a fixed sensing radius of 25. In order to form a full coverage of the target area, we first divide the target area into 4 equal-spaced coronas with radius 25 and calculate the desired number of sensors for rings $R_1$ and $R_4$ as 5, 16, 26, and 34. Figure 7(a) shows their initial distribution, Figure 7(b) indicates the nodes moving to the predefined 4 rings, and Figure 7(c) shows the final distribution, where the small circles mean the coverage circle of each sensor. From the simulation results shown in Figure 7, we can see that our algorithm can also be applied to multiring-based applications and can form multirings quickly.

We further randomly deploy 20, 40, 60, 80, and 100 mobile sensors around the predefined ring. The average moving distance and convergence time with different number of sensors are shown in Table 1. From Table 1, we can see that smaller moving distance can be achieved when the number of sensors increases; this is mainly because the more the number of sensors deployed is, the smaller the optimal angle can be calculated, thus reducing the moving distance. And we also can find that the convergence time almost has a linear growth with the increase of deployed sensors, which is mainly because the movement control is executed in a distributed manner, which can ensure scalability when the number of sensors increases.

Table 1

Comparision of average moving distance and convergence time.

Number of sensors	Average moving distance	Convergence time
20	55.2	0.91
40	48.3	3.4
60	40.6	7.3
80	37.1	11.7
100	32.8	18.5

Considering that the BR algorithm proposed by [26] also intended to form a ring-based distribution for a target area, we further randomly deployed 50 mobile sensors around predefined rings with radius of 50, 60, 70, 80, and 90 and compared our algorithm with BR algorithm.

Figure 8 demonstrates the comparisons of average moving distance. With simulation results in Figure 8, we can find that the average moving distance is increasing as the radius of the ring becomes larger for both BR and our algorithm. Since in our algorithm all sensors are moving along the ring with no oscillation, our algorithm can minimize the moving distance during the process of movement control. However, the movement under BR is based on the virtual force among the neighbour sensors, the sensors may be moving along some place with oscillation, and the resulting moving distance is much longer than our algorithm. Figure 9 depicts convergence time with a different radius of the ring. Since in our algorithm the total covered angle of the ring increases with the working round, the working round for convergence is more than that of BR algorithm, which verifies the effectiveness of the proposed algorithm, as shown in Figure 9.

Figure 8

Performance comparison of average moving distance.

Figure 9

Performance comparison of convergence speed.

6. Conclusions

The problem of autonomous movement control to form a ring-based distribution by mobile sensors is addressed in this paper. We propose a fully distributed movement control algorithm for mobile sensor network to form a ring-based distribution with minimum moving distance. The algorithm was theoretically developed and only requires interaction of the closest neighbours of each sensor. Simulation results show that our algorithm has a good scalability and can converge to the optimal distribution rapidly. It can also be widely applied to different initial states such as random or arbitrary deployment. As part of our future work, we will implement our algorithm in real testbed and examine the performance of our algorithm in more complex environments.