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 $(1 \leq i \leq 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, θ_{i})$ ; if the set of sensors guarantee a ring-based distribution, we have

\begin{matrix} r = r_{0} . \end{matrix}

(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{matrix} θ_{opt} = \frac{2 π}{N} . \end{matrix}

(2)

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

\begin{matrix} θ_{i j} = θ_{j} - θ_{i} . \end{matrix}

(3)

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

\begin{matrix} | θ_{i j} | = θ_{opt} . \end{matrix}

(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 - y$ -axis of sensor $i \in N$ before and after movement control as $(r, θ_{i}^{'})$ and $(r_{0}, θ_{i})$ . Assume each sensor moves from its initial location to final location directly; thus the moving distance of sensor i is

\begin{matrix} f (i)  =  \sqrt{{(r_{0} * \cos θ_{i} - r * \cos θ_{i}^{'})}^{2}  +  {(r_{0} * \sin θ_{i} - r * \sin θ_{i}^{'})}^{2}} . \end{matrix}

(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, θ_{i}^{'}), i = 1, \dots, N}$ , and the predefined ring is located at $(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} Min \sum_{i = 1}^{N} f (i) \\ s . t . r = r_{0} \\ \exists j \in N : ((θ_{j} \leq θ_{i}) \land (| θ_{i j} | = θ_{opt})), \forall i = 1, \dots, N, i \neq j, \\ \exists j \in N : ((θ_{j} \geq θ_{i}) \land (| θ_{i j} | = θ_{opt})), \forall i = 1, \dots, N, i \neq j, \\ θ_{opt} = \frac{2 π}{N}, \\ θ_{i j} = θ_{j} - θ_{i}, \\ f (i)  =  \sqrt{{(r_{0} * \cos θ_{i} - r * \cos θ_{i}^{'})}^{2}  +  {(r_{0} * \sin θ_{i} - r * \sin θ_{i}^{'})}^{2}}, \end{array}

(6)

where

(r, θ_{i}^{'})

and (

r_{0}, θ_{i}

) are the angular coordinates of sensor i before and after redistribution and

θ_{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

θ_{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 $θ_{1} \leq θ_{2} \leq \dots \leq θ_{N - 1} \leq θ_{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 $θ_{1}^{'} \leq θ_{2}^{'} \leq \dots \leq θ_{N - 1}^{'} \leq θ_{N}^{'}$ , 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 \leq j$ , we have $θ_{i} \leq θ_{j}$ . After movement control, these two nodes are moving to two new locations $(r_{0}, θ_{1})$ and $(r_{0}, θ_{2})$ , where $θ_{1} \leq θ_{2}$ . According to the difference of the angular coordinate, one of the following cases may happen, as shown from (A1) to (A6): (A1)

$θ_{1} \leq θ_{i} \leq θ_{j} \leq θ_{2}$

In this case, if misordering of these two nodes happens, we have $θ_{i}^{'} = θ_{2}$ , $θ_{j}^{'} = θ_{1}$ , and the moving distance of $d_{1}$ is

\begin{array}{l} d_{1} = r_{0} * (| θ_{i}^{'} - θ_{i} | + | θ_{j}^{'} - θ_{j} |) \\ = r_{0} * (θ_{2} - θ_{i} + θ_{j} - θ_{1}) . \end{array}

(7)

If no misordering happens, we have $x_{i}^{'} = x_{1}$ , $x_{j}^{'} = x_{2}$ , and the total moving distance of $d_{2}$ is

\begin{matrix} d_{2} = r_{0} * (θ_{i} - θ_{1} + θ_{2} - θ_{j}); \end{matrix}

(8)

thus

\begin{matrix} d_{1} - d_{2} = 2 * r_{0} * (θ_{j} - θ_{i}) \geq 0 . \end{matrix}

(9)

(A2)

$θ_{i} \leq θ_{1} \leq θ_{j} \leq θ_{2}$

In this case,

\begin{matrix} d_{1} - d_{2} = 2 * r_{0} * (θ_{j} - θ_{1}) \geq 0 . \end{matrix}

(10)

(A3)

$θ_{i} \leq θ_{1} \leq θ_{2} \leq θ_{j}$

In this case,

\begin{matrix} d_{1} - d_{2} = 2 * r_{0} * (θ_{2} - θ_{1}) \geq 0 . \end{matrix}

(11)

(A4)

$θ_{i} \leq θ_{j} \leq θ_{1} \leq θ_{2}$

In this case,

\begin{matrix} d_{1} - d_{2} = 0 . \end{matrix}

(12)

(A5)

$θ_{1} \leq θ_{2} \leq θ_{i} \leq θ_{j}$

In this case,

\begin{matrix} d_{1} - d_{2} = 0 . \end{matrix}

(13)

(A6)

$θ_{1} \leq θ_{i} \leq θ_{2} \leq θ_{j}$

In this case,

\begin{matrix} d_{1} - d_{2} = 2 * r_{0} * (θ_{2} - θ_{i}) \geq 0 . \end{matrix}

(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 $θ_{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 $τ_{1}$ (sec), where $τ_{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_{0}, θ_{k})$ and the nearest neighbour sensor m, detects their angle $θ_{m k} < θ_{opt}$ , then the following movement is executed. The starter k pulls m with an angle of $| θ_{opt} - θ_{m k} |$ . 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}, θ_{m}^{'}) = (r_{0}, θ_{m} + θ_{opt} - θ_{m k})$ . Otherwise, the desiredLocation of m is updated as $(r_{0}, θ_{m}^{'}) = (r_{0}, θ_{m} - θ_{opt} + θ_{m k})$ . Since there may already exist some other sensors q in the location $(r_{0}, θ_{m}^{'})$ , to satisfy the initial order of their angular coordinate, the following cases should be dealt with: if $θ_{m}^{'} < θ_{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 $θ_{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 $(0,1) < p$

Select a back off timer $τ_{1}$ = rand ( $0, T$ );

Step 2. //back off

If no start-acting messages is heard in $τ_{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_{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 $θ_{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 $θ_{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 ( $θ_{1}, θ_{2}, \dots, θ_{N}$ ). Define $β_{i}$ as the angle of two adjacent nodes in S. To ensure $β_{i}$ does not exceed $θ_{opt}$ , we define $β_{i}$ as

\begin{matrix} β_{i} = {\begin{cases} θ_{i + 1} - θ_{i}, & if (θ_{i + 1} - θ_{i} \leq θ_{opt}), \\ 0, & otherwise . \end{cases} \end{matrix}

(15)

Define $f (S)$ as the sum of $β_{i}$ ,

\begin{matrix} f (S) = \sum_{i = 1}^{N - 1} β_{i} . \end{matrix}

(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 π - θ_{opt}$ .

Now consider the change of $β_{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 $β_{i}$ is increased to $θ_{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 $β_{i}$ < $θ_{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, $θ_{j, i - 1} = d_{opt}$ , $θ_{i - 1, i} = ε$ . Thus $f (S_{t + 1})$ can be calculated as

\begin{array}{l} f (S_{t + 1}) = (\sum_{k = 1}^{j - 1} θ_{k}) + θ_{j, i - 1} + θ_{i - 1, i} + (\sum_{k = i}^{N} θ_{k}) \\ = (\sum_{k = 1}^{j - 1} θ_{k}) + θ_{opt} + ε + (\sum_{k = i}^{N} θ_{k}), \end{array}

(17)

while

\begin{matrix} f (S_{t}) = (\sum_{k = 1}^{j - 1} θ_{k}) + θ_{j} + θ_{i - 1} + (\sum_{k = i + 1}^{N} θ_{k}) . \end{matrix}

(18)

Since $θ_{j} + θ_{i - 1} < θ_{i j} < θ_{opt}$ , thus we have

\begin{matrix} f (S_{t + 1}) > (S_{t}) . \end{matrix}

(19)

(B3)

If i is an ordinary or a starter node with $θ_{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 \neq 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_{opt}$ and the total length of the multirings as $l_{total}$ ; the desired number of sensors to form multiring-based distribution can be calculated as

\begin{matrix} N_{total} = \frac{l_{total}}{d_{opt}} . \end{matrix}

(20)

Since all

N_{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}

D_{i}

and the desired number of sensors in

C_{i}

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 (n, n - 1, \dots, 1)$

if $D_{i} > {E D}_{i}$

Select $D_{i} - {E D}_{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} - {E D}_{i})$ ;

Applying our distributed algorithm to form a ring

based distribution for ring $R_{i}$ .

Elseif $D_{i} \leq {E D}_{i}$

Select ${E D}_{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} + ({E D}_{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.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work is supported by the National Natural Science Foundation of China under Grant no. 61173153 and no. 60903159; the National Science Foundation for Distinguished Young Scholars of China under Grant no. 61225012 and no. 71325002; the Fundamental Research Funds for the Central Universities under Grant nos. N110404014, N110318001, N110204003, N100218001, and N120104001; the China Postdoctoral Science Foundation funded project under Grant no. 20110491508 and no. 2012T50248; the Specialized Research Fund of the Doctoral Program of Higher Education for the Priority Development Areas under Grant no. 20120042130003; the Specialized Research Fund for the Doctoral Program of Higher Education under Grant no. 20110042110024.

References

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 105

2-s2.0-0036688074

10.1109/MCOM.2002.1024422

Jia

Chen

Chang

Tan

Energy efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm

Computers and Mathematics with Applications 2009 57 11-12 1756 1766

2-s2.0-67349235580

10.1016/j.camwa.2008.10.036

Davis

T. W.

Liang

Kuo

C.-M.

Liang

Analysis of power characteristics for sap flow, soil moisture, and soil water potential sensors in wireless sensor networking systems

IEEE Sensors Journal 2012 12 6 1933 1945

2-s2.0-84860532455

10.1109/JSEN.2011.2179933

Redondi

Chirico

Borsani

An integrated system based on wireless sensor networks of patient monitoring, localization and tracking

AD Hoc Networks 2013 11 1 39 53

Banerjee

King

C.-T.

Building ring-like overlays on wireless ad hoc and sensor networks

Proceedings of the IEEE International Conference on Mobile Ad Hoc and Sensor Sysetems (MASS '06)

October 2006

286 295

2-s2.0-39049103910

10.1109/MOBHOC.2006.278567

Jia

Zhang

Chen

Wang

Yan

On the problem of energy balanced relay sensor placement in wireless sensor networks

International Journal of Distributed Sensor Networks 2013 2013 9

342904

10.1155/2013/342904

Kumar

Lai

T. H.

Arora

Barrier coverage with wireless sensors

Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom '05)

September 2005

284 298

2-s2.0-32144431768

10.1145/1080829.1080859

Younis

Akkaya

Strategies and techniques for node placement in wireless sensor networks: a survey

Ad Hoc Networks 2008 6 4 621 655

2-s2.0-39149099807

10.1016/j.adhoc.2007.05.003

Lee

Magistretti

Zhou

Gerla

Bellavista

Corradi

Efficient data harvesting in mobile sensor platforms

Proceedings of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom '06)

March 2006

352 356

2-s2.0-33750319884

10.1109/PERCOMW.2006.47

10.

Chellappan

Bai

Xuan

Mobility limited flip-based sensor networks deployment

IEEE Transactions on Parallel and Distributed Systems 2007 18 2 199 211

2-s2.0-33846863593

10.1109/TPDS.2007.28

11.

Dantu

Rahimi

Shah

Babel

Dhariwal

Sukhatme

G. S.

Robomote: enabling mobility in sensor networks

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN '05)

April 2005

404 409

2-s2.0-33744928874

10.1109/IPSN.2005.1440957

12.

Howard

Mataric

M. J.

Sukhatme

G. S.

Mobile sensor network deployment using potential fields: a distributed scalable solution to the area coverage problem

Proceedings of the 6th International Conference on Distributed Autonomous Robotic Systems (DARS '02)

2002

299 308

13.

Poduri

Sukhatme

G. S.

Constrained coverage for mobile sensor networks

Proceedings of the IEEE International Conference on Robotics and Automation

May 2004

165 171

2-s2.0-3042582668

14.

Wang

Lim

H. B.

A survey of movement strategies for improving network coverage in wireless sensor networks

Computer Communications 2009 32 13-14 1427 1436

2-s2.0-67650604371

10.1016/j.comcom.2009.05.004

15.

Wang

Cao

La Porta

T. F.

Movement-assisted sensor deployment

IEEE Transactions on Mobile Computing 2006 5 6 640 652

2-s2.0-33646437020

10.1109/TMC.2006.80

16.

Zou

Chakrabarty

Sensor deployment and target localization based on virtual forces

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies

April 2003

1293 1303

2-s2.0-0042014539

17.

Jia

Chen

Wang

Exploiting sensor redistribution for eliminating the energy hole problem in mobile sensor networks

EURASIP Journal on Wireless Communications and Networking 2012 2012, article 68

10.1186/1687-1499-2012-68

18.

Wang

Cao

La Porta

Zhang

Sensor relocation in mobile sensor networks

Proceeding of IEEE International Conference on Computer Communications (INFOCOM '05)

March 2005

2302 2312

2-s2.0-25644433619

19.

Leoncini

Resta

Santi

Partially controlled deployment strategies for wireless sensors

Ad Hoc Networks 2009 7 1 1 23

2-s2.0-53549108630

10.1016/j.adhoc.2007.11.010

20.

Yang

SMART: a scan-based movement-assisted sensor deployment method in wireless sensor networks

Proceeding of the IEEE International Conference on Computer Communications (INFOCOM '05)

March 2005

2313 2324

2-s2.0-25644454458

21.

Chatzigiannakis

Markou

Nikoletseas

Distributed circle formation for anonymous oblivious robots

Proceedings of the Experimental and Efficient Algorithms: 3rd International Workshop (WEA '04)

2004

22.

Katreniak

Biangular circle formation by asynchronous mobile robots

Proceedings of the 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO '05)

May 2005

185 199

2-s2.0-24944489162

23.

Gao

Multi-level virtual ring: A foundation network architecture to support peer-to-peer application in wireless sensor network

Proceedings of the Australasian Telecommunication Networks and Applications Conference (ATNAC '09)

November 2009

1 6

2-s2.0-77953780116

10.1109/ATNAC.2009.5464898

24.

Flocchini

Prencipe

Santoro

Self-deployment of mobile sensors on a ring

Theoretical Computer Science 2008 402 1 67 80

2-s2.0-46049100000

10.1016/j.tcs.2008.03.006

25.

Narendranad

Vaibhav

Hailong

Dharma

Hybrid gaussian-ring deployment for intrusion detection in wireless sensor networks

Proceedings of the IEEE International Conference on Communications (ICC '12)

2012

549 5553

26.

Kong

Liu

M.-Y.

Automatic barrier coverage formation with mobile sensor networks

Proceedings of the IEEE International Conference on Communications (ICC '10)

May 2010

1 6

2-s2.0-77955399011

10.1109/ICC.2010.5501990

27.

Sugihara

Gupta

R. K.

Sensor localization with deterministic accuracy guarantee

Proceedings of the IEEE Annual IEEE International Conference on Computer Communications (INFOCOM '11)

April 2011

1772 1780

2-s2.0-79960849531

10.1109/INFCOM.2011.5934976

28.

Zhu

Ding

Distributed cooperative localization of wireless sensor networks with convex hull constraint

IEEE Transactions on Wireless Communications 2011 10 7 2150 2161

2-s2.0-79960557279

10.1109/TWC.2011.051311.100698