Keywords

1 Introduction

Wireless sensors networks have gained a lot of attention since 1990s and been introduced into several fields of technology [1,2,3,4,5]. They are becoming a dominant part in military and civil sensing and communication applications, as well as a part of healthcare and environmental monitoring [1,2,3,4,5,6].

The ability of a coordinated set of sensors to monitor a particular area efficiently and effectively are at the center of sensor networks’ coverage capability [2]. The fragmented information about the monitored area collected by individual nodes requires effective network connectivity in order to be mutually exchanged and efficiently transferred towards the data sink. In order to achieve flexible and robust communication systems of mobile nodes, the sensors should remain within the communication range of each other so that all the nodes maintain connectivity readiness with multiple neighboring nodes and the network is fully connected.

Many challenges arise in achieving the goal of optimal coverage with moving nodes, while simultaneously trying to minimize consumed energy and time spent on optimizing the WSN of ever smaller and versatile mobile nodes [5, 6]. A well designed WSN should allow sensors to operate autonomously through local operation policy, efficient communication with the local neighbors only, remain independent of sensor’s initial position, adaptable and flexible – adjusting rapidly to the changing conditions.

In this report, we introduce a specific variant of the Voronoi-based coverage algorithm [7, 8] augmented with specific nodes provision procedure, which allows mobile nodes to be distributed efficiently and conflict–free inside any unknown two-dimensional bounded (indoor) area of interest. Compared to the other approaches like virtual force-based algorithms [5], our approach achieves the stable, converged, fully connected network much sooner while investing much fewer deployment energy measured by the total amount of nodes displacement from the entry point. The network composed of homogeneous nodes converges to the near-perfectly balanced, uniformly distributed, blanket-coverage WSN only slightly distorted around the bounds of the target area. The most robust feature of our agile WSN deployment method is that is fully decentralized, autonomous and can rapidly self-adjust to any bounded indoor area without any prior knowledge of the geometrical structure of the target space. The reflection of this is that the number of nodes involved in the deployment process is unknown at the start but is dynamically determined by gradual and conflict-free absorption of as many nodes as required to achieve full connectivity.

We evaluate the deployment performance of our algorithm based on two metrics: (1) the total distance travelled by nodes from their starting point until their final allocation, additionally compared to the absolute optimal possible, and (2) the degree of coverage achieved by network measured by the percentage of the total target area that is within sensing reach nodes in terms of area covered.

The rest of the report is organized as follows: Sect. 2 covers previous related work; and Sect. 3 discusses our Voronoi-based algorithm in more details. Section 4 reveals the simulation results and comparison with previous work results; and Sect. 5 finalizes the paper with conclusions and future work plans.

2 Discussion of Related Work

Researchers have gained a substantial inspiration through analysis of animal behavior in coverage of their territories [11, 12]. Animal strategies of self-organization within the surrounding environment, reaching a dynamic steady state coverage, have inspired the application of modelled versions of such behaviors in mobile networks. Voronoi tessellations are among the behaviors observed in such studies. The authors in [11, 12] discussed the behavior of animal territories such as male tilapia mossambica and how they form the polygonal shapes at high densities. Assuming all members of the species have same strength, the pressure between the neighbors balances their perpendicular bisector and creates the boundary between them, which lead to formation of Voronoi polygons, whereby each member of the flock tends to occupy its immediate surroundings in a way to be as far from its neighbors as possible. By applying the behavior of such territories into mobile network, the sensor nodes tend to achieve uniform distribution as the particles are at the center of mass of their Voronoi polygonal region. The overall Voronoi regions may not be equally sized, but the total covered area and the number of edges follows some computable definite distribution with finite standard deviation [12].

The Voronoi tessellation technique improves the WSN network uniformity and enhances the system lifetime and energy usage, especially when dealing with homogeneous sensor nodes (nodes of same properties and capabilities). The authors in [9, 10] implemented node-spreading Voronoi algorithm (NSVA) on the sensor nodes to move them toward their Voronoi centroid inside an unknown area of interest. The tessellation cells are bounded by the nodes’ sensing range to maintain connectivity during the deployment. Their NSVA algorithm showed to be efficient in terms of average distance travelled by the nodes in comparison with another technique based on genetic algorithm, which they applied as well.

Another approach is to rely on laws of physics to arrange sensor nodes, rather than Voronoi tessellations, so in [13] an algorithm is implemented based on the equilibrium of molecules where the nodes move according to distance-dependent forces coming from their neighbors. The new position for each node is indicated by summing all forces affecting the nodes. The process reach its end if one of the following conditions is met: either nodes move less than a certain threshold value, or if the nodes keep moving back and forth around the same location for many times.

Our algorithm is based on re-calculating Voronoi diagrams every time a new sensor node enters the area of interest; and the movement of these nodes is guided towards the center of their cells. The differences from [9, 10] are: (1) the Voronoi cells are generated after discovering dimensions of the area, and (2) not bounded by the nodes sensing range based on information about their neighbors. In addition to that, nodes will enter one at a time to the area based on requirements other than having a fixed number of nodes. The communication range and sensing range are not identical but follow a certain relationship. More details are in the following section.

3 Voronoi-Based Algorithm

Our newly introduced technique for self-deployment of mobile sensor nodes is based on Voronoi tessellations with the goal of maximizing coverage while maintaining connectivity inside the area of interest [7, 8]. We call it Bio-Inspired Self-Organized Network (BISON) algorithm. The assumptions for BISON are the following:

  1. 1.

    All the nodes are homogeneous, having the same sensing, communication computation and mobility abilities. This helps greatly in optimizing the network lifetime and reducing the overall power consumed.

  2. 2.

    The deployment of the sensor nodes happens one at a time from either edge of the area to make the experiment more realistic.

  3. 3.

    Each node has the ability to distinguish its location and other nodes’ locations through GPS and multilateration method, in order to ease the process of plotting Voronoi diagrams with respect to available sensor nodes in the area [14].

  4. 4.

    The communication range (RC) and sensing range (RS) form circular shapes with the following relationship between them [13, 15, 16]:

    $$ R_{C} = \sqrt 3 R_{S} $$
    (1)

    This relation aims to provide large communication abilities among sensor nodes while minimizing the overlapping between their sensing ranges; which also helps in covering as much as possible from the interested area, without wasting resources of adding more nodes to the system.

  5. 5.

    No errors are assumed to be available in terms of determining location of nodes or in data transmission.

The self-organized deployment process starts with launching two sensor nodes from the starting point (area entry) to discover the space dimensions and broadcast the information to the incoming nodes. A third and following sensor nodes are inserted to follow standard Voronoi Center-Mass guided transition policy throughout the explored area i.e. they move towards the centers’ of their corresponding Voronoi polygons.

The Voronoi boundaries are determined based on the following definition:

$$ V_{i} = \left\{ {x \in A :d\left( {x,n_{i} } \right) < d\left( {x,n_{j} } \right)} \right\} $$
(2)

where A is the area of interest, x is a random point inside the area, V i is the Voronoi cell that belongs to sensor node ni. The process of moving nodes towards their Voronoi centroid is simply a sequence of identical operations of recalculating the center of mass for each updated Voronoi polygon and moving to it from node’s previous location. This process stops when the sum of movements of all nodes become smaller than a certain threshold value related to the size of the explored space i.e. 1% of the space length.

Each new sensor is inserted to join the coverage network if all of the following conditions are met:

  1. 1.

    Any node has its nearest neighbor node further than the communication range RC (i.e. not all nodes are within the communication range)

  2. 2.

    The distance between the entry point and its closest node is greater than the sensing range RS (i.e. the network evolved to make space for new entry)

These conditions will ensure mutual communication connectivity among all nodes and avoid premature over provisioning that create inefficiently crowded entry point area.

The results presented in the following section prove that our algorithm allowed nodes to be distributed uniformly covering the entire area after travelling much shorter transition distances compared to the algorithms discussed in [9, 10].

4 Simulation Results

Our simulation analysis is done using MATLAB. The assigned parameters are sensing range RS = 1, area of 10 × 10, and the shifting threshold of RS/100. The code allows us to monitor the movement of nodes until reaching optimum positions, while calculating the required time, number of nodes, total distance travelled, and overall coverage achieved. The simulation is repeated 20 times and the results are averaged. Figure 1(a) shows the two nodes discovering the area of interest in order to broadcast the dimensions to the incoming nodes. In Fig. 1(b) and (c) more nodes are entering the area and are being distributed to maintain coverage and establish connectivity among them. Figure 1(d) shows the final distribution of nodes in the area, and the lines connecting the nodes together represent how many nodes are connected in the system. Our approach required 43 nodes for the given geometry, all of which are connected to at least one neighboring node. This implies that our system is reachable by any node.

Fig. 1.
figure 1

Snapshots of the distribution of nodes throughout the simulation. (a) Two starting nodes discovering the area of interest. (b) and (c) The distribution of nodes entering the area during intermediate stages, where (c) comes after (b) in timeline, (d) the final distribution of nodes covering the entire area and maintaining connectivity among them

Full size image

The metrics of evaluation computed to evaluate the system are the following:

$$ percentage \,area\, coverage = \frac{total\, area\, covered\, by \,sensor\, nodes}{area \,of\, interest} $$
(3)
$$ Average\, distance\, travelled(t) = \frac{1}{N}\sum\nolimits_{i = 1}^{N} {d(L_{{n_{i} }}^{0} ,L_{{n_{i} }}^{t} )} $$
(4)

Where N is total number of nodes at time t, \( L_{{n_{i} }}^{0} \) is the initial location of nodes at time 0, and \( L_{{n_{i} }}^{t} \) is the node’s location at time t.

Figure 2(a) clearly shows how our algorithm on average requires much shorter distance travelled to find the optimal nodes’ positions compared to NSVA algorithm [9, 10], which greatly helps in increasing the system lifetime and reduce the consumed deployment power. Figure 2(b) demonstrates the time evolution of the coverage area of our BISON network during the deployment and compares it to the equivalent process realized by NSVA algorithm. The percentage area coverage is found from the superposition of coverage areas of each node within its sensing range and compared to the total area of the target space. We have used a combination of geometric calculus and the Monte Carlo approximations to arrive at the results that are accurate to the 10th of a percent, allowing for a meaningful comparison.

Fig. 2.
figure 2

A comparison between (a) the averaged travelled distance and (b) the relative coverage area between the BISON and NSVA algorithms throughout the simulation.

Full size image

The results illustrated in Fig. 2 clearly prove that our BISON proceeds with the much more efficient deployment of the network coverage for the target space, overall requiring several times shorter sum of total transitions of the network nodes. Moreover, while both algorithms eventually reach similar final levels of target area coverage, BISON achieves it much quicker, typically maintaining between 10% and 20% advantage in the relative coverage throughout most, especially earlier stages, of the deployment process. The reason behind the unsmoothed curve for BISON algorithm is due to the insertion of sensor nodes throughout the simulation, which in turn changes the distribution of the existing sensor nodes in the target area.

In order to examine the distribution of the typical polygonal shapes obtained with the BISON, a histogram for the number of Voronoi polygon edges vs. relative frequencies is plotted and compared it with the coverage of animals’ territories behavior in [12]. The results in Fig. 3 revealed similar behavior to [12] in terms of distribution of the number of edges, and further examination of a larger scale systems indicates that BISON follows uniform distribution. The figure reveals a distribution of particles following a definite distribution with finite standard deviation [12].

Fig. 3.
figure 3

A comparison of the number of end-state Voronoi polygon edges between BISON algorithm and the known animal territories behavior [12].

Full size image

5 Conclusion and Future Work

A modified Voronoi algorithm based technique (BISON) is developed establishing a blanket coverage for an unknown area over a short time with minimum distance travelled by mobile sensor nodes. BISON is based on inserting sensor nodes one after the other until achieving optimum coverage while maintaining connectivity among them. The nodes’ movements are directed toward their Voronoi center of mass and they stop when the average sensors shift is below a defined threshold. The performance of the network is compared with recent previous work called node-spreading Voronoi algorithm (NSVA) and evaluated based on percentage area coverage and average distance travelled by the nodes. The simulation results revealed that BISON algorithm achieved higher coverage with much less average distance travelled by nodes compared to NSVA algorithm.

Our future work will focus on managing the distance between the sensor nodes together in terms of balancing between approaching the Voronoi center of mass and considering the maximum distance where nodes can be far from each other but still be connected. We will also consider 3D environment, where our algorithm is expected to rapidly self-compose or reorganize itself based on continuously changing conditions.