On virtual-force algorithms for coverage-optimal node deployment in mobile sensor networks via the two-dimensional Yukawa crystal

Abstract

As theoretical proof has shown that a hexagonal topology can obtain maximal coverage with a fixed number of sensor nodes, node deployment for mobile sensor networks has the objective of forming a hexagonal network topology while consuming minimum energy. Using virtual-force algorithms to move initially randomly distributed nodes into a target topology is one of the widely studied methods for achieving this goal. In this work, a novel virtual-force algorithm based on physical laws in a dusty plasma system (i.e. VFA-DP) was applied within a mobile sensor network deployment scenario. The VFA-DP force has a central attracting force which can provide a screening effect via exponential decay. Here, to evaluate how perfect the final grids become from virtual-force algorithms, we introduce a performance metric based on the pair correlation function in a crystalline structure. Via simulation studies, we determined that the topology resulting from the VFA-DP is much closer to a hexagon. The analysis also indicated that the VFA-DP converges faster than another virtual-force algorithm based on the Lennard-Jones potential (VFA-LJ), resulting in lower communication-related energy costs in real deployment scenarios. The method developed in this article is derived from studies of crystalline structure from condensed matter physics and shows clear evidence of when the regular lattice is ready. It will provide some guidance for engineering by aiding deployment in complex geometric areas or those recovering from disaster.

Keywords

Mobile sensor network virtual-force algorithm node deployment Yukawa potential

Introduction

Mobile sensor networks (MSNs), owing to advanced capabilities in sensing and commutation, have enabled novel applications^1,2 such as disaster management, factory automation, environment monitoring, and offshore exploration. For applications which require a massive number of sensor nodes, mobile sensors deployment methods should meet the performance requirements imposed by diverse applications³ and provide maximal coverage.⁴ Another requirement is that during the deployment process, the entry cost should be at a minimum. Energy cost can be divided into two categories, one for communication and the other for node movement. The static approach, deploying sensor nodes to a pre-determined destination,⁵ lacks adaptivity to the environment and disaster recovery. Thus, people prefer to use self-organized relocation schemes⁶ to guide sensor nodes, autonomously forming optimal coverage topology.

Recently, some properties of a physical system composed of a small number of particles have been reported.^7,8 Via simulations, some experience or guidance for different virtual force methods, as well as different physical parameters within the same form of force regarding engineering, can be achieved. In this theory, when kinetic energy is dissipated, the system approaches a structure that has minimal potential energy, oscillates around the equilibrium point and falls into the potential well. The above idea is one type of naive method employed for understanding the phase transform process in particle systems. If the system has only one potential energy global minimum point, the system will then evolve into the structure associated with this potential energy minimum. However, there are some local minimum points for particular systems. For example, the lowest energy arrangement for an infinite number of atoms described by the Lennard-Jones potential is hexagonal close-packing. However, under pressure, the lowest energy structure switches between cubic and hexagonal close packing.⁹ Based on the Lennard-Jones potential (i.e. VFA-LJ), such has been observed within existing virtual force methods for MSN deployment. In particular, in Garetto et al.,¹⁰ the network topology converged to a hexagonal structure. However, how physical parameters impact the final grids is also not clear although physicists have observed that. In general, pressure from the environment can accelerate crystal formation and improve the quantity of the grids. As a result, here, comparing the grid quantity and the convergence speed required for obtaining a perfect hexagon from different virtual force methods is the main focus of the simulation studies in our work.

Hexagonal topology provides maximum coverage with a minimum number of sensor nodes.^11–13 As such, existing virtual-force algorithms^10,14–17 have sought to push sensor nodes to formulate hexagonal deployment. Zou and Chakrabarty’s¹⁶ publication is the first widely cited work for introducing virtual force algorithms into the MSN. Garetto et al.’s¹⁰ work was the first to achieve hexagonal deployment for a relatively large number nodes, and also contained practical engineering discussions for a real MSN work. However, no systematic review of these form solutions has provided a fundamental understanding of the principles behind the method, and most of these ad hoc approaches have resulted in imperfect structures. Here, we provide a virtual-force algorithm for coverage-optimal node deployment in MSNs via the two-dimensional (2D) Yukawa crystal and propose some of the necessary components required for the model to make the sensors converge to a hexagonal structure.

In addition, previously investigated virtual force methods have all been based on a fully ad hoc approach where nodes generally have both a repulsive and an attractive force to one another.^10,16 The method we propose here¹⁸ has a central attracting force that acts like a pressure within normal physical systems. This pressure force helps the convergence speed and the grid quantity. Furthermore, we use a pair correlation function, which has been used to evaluate particle systems in statistical mechanics,¹⁹ to evaluate the final grid quantity. It can also be used to effectively describe the convergence process of the whole network. Our hope is that this work can provide some guidance for engineering by aiding deployment in complex geometric areas or those recovering from disaster.

This article is organized as follows. In section “Sensor network model,” we present a network model for an MSN and formulate the coverage-optimal node deployment problem. In section “Virtual-force algorithms for node deployment,” a fundamental analysis of existing virtual-force algorithms is presented. In section “Virtual-force algorithm based on Yukawa potential,” we propose a novel virtual-force algorithm based on physical laws within a 2D dusty plasma system, as well as a novel performance metric based on the pair correlation function for the same physical system. In section “Simulation results,” we compare the proposed algorithm with existing virtual-force algorithms for two aspects, including the following: (1) the similarity between the resulting deployment topology and a perfect hexagon, and (2) the convergence rate toward a stable hexagonal structure. Section “Conclusion and future work” consists of concluding remarks.

Sensor network model

For the study, we assumed that all sensor nodes had identical capabilities in sensing, communication, computation, and mobility. The coverage field consists of a 2D plane, and sensors can move freely within the plane. Each sensor node has a sensing radius of $r_{s}$ and a communication radius of $r_{c}$ . As illustrated in Figure 1, both the sensing and communication ranges are assumed to be a disk. Within the sensing radius, the sensor can detect the local environment. Within the communication range, the sensor node can communicate with any other sensor falling into the disk area. Every node has the ability to know its own location and can exchange its position with sensors over the communication range. Details of the communications between the sensors are not discussed here.

Figure 1.

Both the sensing and communication ranges were assumed to be a disk, with radii of $r_{s}$ and $r_{c}$ , respectively: (a) sensor model and (b) coverage model.

Mathematically, the problem of covering a square with a minimum number of disks has been intensely investigated. Placing disks on the vertices of a triangular lattice (or, equivalently, at the center of regular hexagons) is known to be optimal in terms of the number of disks needed to achieve a full coverage plane. This asymptotic optimality was initially demonstrated rigorously in the Kershner¹¹ and was recently rediscovered in the Zhang and Hou.²⁰

For MSNs, a similar problem has also been addressed in Pompili et al.² and Bai et al.⁴ Specifically, if $r_{c} \geq \sqrt{3} r_{s}$ , deploying sensor nodes in the hexagonal pattern provides both coverage and connectivity, and is optimal in terms of the number of sensor nodes required. In the following discussion, we always assume that the statement $r_{c} \geq \sqrt{3} r_{s}$ is true.

With an optimal deployment topology (i.e. hexagons), the minimum number of sensor nodes required to fully cover a target square area can be derived as follows

N^{*} (l, r_{s}) = (\frac{l - \sqrt{3} r_{s}}{\sqrt{3} r_{s}} + 1) \times (\frac{2 l - 2 r_{s}}{3 r_{s}} + 1)

(1)

where $l$ is the length of a side of the target square area.

In Figure 2, we plot the minimum number of sensor nodes required to cover a square region as a function of the sensing radius. The optimum number of sensor nodes decreases quadratically as the sensing radius increases.

Figure 2.

The minimum number of sensor nodes, each with a sensing radius, $r_{s}$ , is needed to provide full coverage for an area of $l \times l$ . The optimal number of sensor nodes decreases quadratically as the sensing radius increases. In this graph, $l = 10$ .

Virtual-force algorithms for node deployment

Two types of equations describe particle motion. The first equation type is a first-order differential equation, given by the following

\frac{d r (t)}{dt} = min {L_{\max} \frac{F (t)}{| F (t) |}, F (t)}

(2)

\frac{d r (t)}{dt} = L_{\max} \cdot \frac{F (t)}{| F (t) |} \cdot e^{- \frac{1}{| F (t) |}}

(3)

where $L_{\max}$ is the maximum length that one particle can move within one step and $F$ is the total force imposed on a particle by other particles in an environment. To avoid system oscillation, the maximum length that a particle can move within one step is introduced. Previous virtual-force algorithms in this category include the previous studies.^21–24 Whether or not this type of system resembles any physical system is difficult to say, but mathematically, the movement of particles in these systems will decay exponentially. Since these systems are not generally used for making large quantities of nodes evolve into a regular lattice, we do not discuss them here.

The second type of equation is a second-order differential equation, generally of the following form

m \frac{d^{2} r (t)}{d t^{2}} = F (t) - m ν \frac{d r (t)}{dt}

(4)

where the term on the left-hand side corresponds to particle acceleration, the second term on the right-hand side corresponds to a frictional damping force, and $F$ corresponds to the total imposed on the particle at time $t$ . For a potential field, $F$ can be written as $F (t) = - \nabla ϕ (t)$ , where $ϕ (t)$ corresponds to the total potential imposed by other particles and the environment. The above system results in a dynamic equilibrium physical system (as explained below). As such, here, we focus on the second-order system.

Various inter-particle forces can be categorized into two types. In the first type, the force between particles is always a repulsive force. In general, these types of systems use a confinement force to limit the particles. The confinement force can be the centralized attracting force as for a dusty plasma system^18,25 or a force added from the boundary, as in Howard et al.¹⁴ In the second type, particles can have both a repulsive and an attractive force within each other (i.e. the Lennard-Jones force).²⁶ For such a case, when the distance between two particles is less than a particular threshold, a repulsive force occurs between them. When the distance is larger than the threshold, an attractive force occurs between them. When the distance is equal to the threshold, there is no force between them. In this physical system, interactions between the particles comprise a potential well for trapping particles at the threshold point. One popular approximation for the Lennard-Jones potential is given by the following

ϕ_{LJ} (r) = ϵ {{(\frac{r_{m}}{r})}^{12} - 2 {(\frac{r_{m}}{r})}^{6}}

(5)

where $ϵ$ is the depth of the potential well and $r_{m}$ is the distance at which the potential reaches its minimum. Examples in this category are included in the literature.^10,16,17,27 Apparently, systems using the Lennard-Jones potential do not necessarily need a confined force to make them converge to equilibrium. Table 1 gives a virtual-force algorithm classification for the different type of virtual forces.

Table 1.

A system for virtual-force algorithm classification. Type I uses repulsive force only, while type II uses both a repulsive and an attractive force.

Potential	Type I	Type II
First order	N/A	Wong et al.,²¹ Chen et al.,²² Wang et al.,²³ and Kribi et al.²⁴
Second order	Howard et al.¹⁴ and Heo and Varshney¹⁵	Garetto et al.,¹⁰ Zou and Chakrabarty,¹⁶ Poduri and Sukhatme,¹⁷ and Lee et al.²⁷

In equation (4), the damping term $m ν d r (t) / dt$ dissipates kinetic energy out of the particle system. Thus, the system should evolve into a static structure that has a minimum in potential energy. The minimum can be a local or global minimum. The goal of the sensor deployment process is to make the node evolve into a large hexagonal structure with few iteration simulation steps and less of a moving distance for the nodes. To measure the quality of the fine grids, as well as the process that node systems use to evolve into this structure, we used the pair correlation function as a quantitative measurement method.

We observed that among VF approaches of nodes deployment,^10,14–17 only Garetto et al.¹⁰ achieved a regular lattice (i.e. hexagon) for mass nodes. Thus, we only compared our simulation results with those reported in Garetto et al.¹⁰

Virtual-force algorithm based on Yukawa potential

Dusty plasma particles^18,25 interact in the classical physics regime, and particles inside this system are relatively easy to control and observe. Thus, this system has been extensively studied for basic phase transforms or kinetic theory.²⁸ In a dusty plasma system, the nonlinear equation of motion¹⁸ for a dust particle $i$ of mass $m$ and charge $Q$ is given by

m \frac{d^{2} r_{i}}{d t^{2}} = - \nabla ϕ_{i} - m ν \frac{d r_{i}}{dt}

(6)

where the electrostatic potential $ϕ_{i}$ is written as

ϕ_{i} = {kr}_{i}^{2} (t) + \sum_{i \neq j}^{N} \frac{Q^{2}}{4 π ϵ_{0} r_{ij}} e^{- \frac{r_{ij}}{λ_{D}}}

(7)

Here, $r_{i}$ is the radial distance from the center, $r_{ij}$ is the distance between two particles $i$ and $j$ , $ν$ is the damping coefficient, $λ_{D}$ is the Debye length of the plasma, and the sum includes all particles within the communication range. The first term on the right-hand side in equation (7) is the externally imposed harmonic potential that provides radial confinement, the so-called central attraction force where the spring constant, $k$ , can be adjusted to control inter-particle separation. The second term on the right-hand side of equation (7) represents the Yukawa potential, a so-called screened Coulomb potential. The Yukawa potential decreases very fast after $r_{i}$ exceeds $λ_{D}$ . The particles’ interaction is very weak if the distance between them is much larger than $λ_{D}$ . As a result, for real mobile sensor applications, by choosing a $λ_{D}$ that is much smaller than $r_{c}$ , one can make node interactions in the MSN accurately resemble the Yukawa potential.

In the physical world, it has been observed that under this system, the resulting plasma, in a 2D setting, forms a hexagonal structure.²⁵ Inspired by this physical observation, we adopted the physical system for a dusty plasma as a basis for a novel virtual-force algorithm for node deployment. The resulting network topology is expected to be a hexagonal structure.

A molecular simulation was performed to emulate how sensor nodes move from an initial random deployment into a structured hexagon. A second-order leapfrog scheme was utilized for the time discretization in equation (6), as follows

r_{i + 1} = r_{i} + v_{i} dt + a_{i} (dt)^{2} / 2

(8)

v_{i + 1} = v_{i} + (a_{i} + a_{i + 1}) dt / 2

(9)

where $v$ and $a$ are the particle velocity and the acceleration at each step, respectively. In addition, a simple staggered leapfrog scheme was not employed because, to achieve a better convergence speed, the time step-length was constantly changing according to the Courant–Friedrichs–Lewy condition in the simulation. For MSNs, before computing the new velocity, the sensor node broadcasts an advertisement (ADV) message so that neighbors are aware of their position. After obtaining all of the position information of neighbors, the sensor node can calculate $r$ and $v$ using equations (8) and (9), respectively.

For completeness, the pseudocode of the leapfrog schema solution for VFA-DP within the MSN is shown in Algorithm 1. To prevent the description from becoming cumbersome, we omitted details that could either be inferred or implemented using standard techniques.

Algorithm 1: Distributed algorithm for leapfrog in VFA-DP in mobile sensor networks
Event: node $p$ ’s timer expires at time step $t_{i}$ begin Exchange node positions $r_{i + 1} \leftarrow r_{i} + v_{i} \times Δ t + \frac{1}{2} \times a_{i} (Δ t)^{2}$ compute $a_{i + 1}$ using equation (6) and (7) $v_{i + 1} \leftarrow v_{i} + \frac{1}{2} \times (a_{i} + a_{i + 1}) \times Δ t$ set timer to $t_{i + 1} \leftarrow t_{i} + Δ t (by CFL condition)$ replace $v_{i}$ , $r_{i}$ with $v_{i + 1}$ , $r_{i + 1}$ end

Algorithm 1: Distributed algorithm for leapfrog in VFA-DP in mobile sensor networks

Event: node

p

’s timer expires at time step

t_{i}

begin
Exchange node positions

r_{i + 1} \leftarrow r_{i} + v_{i} \times Δ t + \frac{1}{2} \times a_{i} (Δ t)^{2}

compute

a_{i + 1}

using equation (6) and (7)

v_{i + 1} \leftarrow v_{i} + \frac{1}{2} \times (a_{i} + a_{i + 1}) \times Δ t

set timer to

t_{i + 1} \leftarrow t_{i} + Δ t (by CFL condition)

replace

v_{i}

r_{i}

with

v_{i + 1}

r_{i + 1}

end

Furthermore, for evaluating different virtual-force algorithms, it is important to have an objective measurement of system performance in two aspects, including the network topology and the convergence rate. Here, we introduce a novel performance metric based on the pair correlation function within the crystalline structure in order to evaluate the proximity from any network topology to a perfect hexagon and to compare the convergence rate of virtual-force algorithms.

The pair correlation function, denoted as $g (r)$ , represents the probability of finding two particles separated by a distance $r$ . In a 2D plane, it is defined as follows

g (r) = (\frac{S}{N}) \frac{N (r, Δ)}{2 π r Δ}

(10)

where $S$ is the area occupied by a 2D plane, $N$ is the number of sensor nodes contained in $S$ , and $N (r, Δ)$ indicates the number of particles falling between a radius of $r - Δ / 2$ and $r + Δ / 2$ .

We define the distance measurement between any network topologies and a perfect hexagon, as follows

δ_{pc} (Ω, Ω_{H}) = \frac{\int_{0}^{r_{T}} ∥ g_{Ω} (r) - g_{Ω_{H}} (r) ∥^{2} dr}{\int_{0}^{r_{T}} ∥ g_{Ω_{H}} (r) ∥^{2} dr}

(11)

where $Ω$ corresponds to any network topology, $Ω_{H}$ refers to a perfect hexagon, and $r_{T}$ is the bound of support over which the pair correlation function is defined. We call this distance measurement the pair correlation diversion.

Pair correlation diversion provides an objective metric for evaluating virtual-force algorithms. The smaller the distance metric, the closer the network topology is to a perfect hexagon. Moreover, it can also be used to characterize the convergence rate of any virtual-force algorithm. Beginning from an initial node distribution, the pair correlation diversion decreases as the algorithm progresses. When the algorithm converges to a stable structure, the value remains within a stable level (due to the randomness of the simulation it may actually fluctuate a little over a small range). The slope of the pair correlation function curve, as a function of the simulation steps, indicates how fast the virtual-force algorithm converges.

Simulation results

In this section, we present our simulation results using the proposed VFA-DP as compared to the previous VFA-LJ.¹⁰ In simulations for both algorithms, the coverage area is a square and is, initially, randomly covered by a number of sensor nodes. Initial node deployment is assumed to be uniformly distributed and is the same for both algorithms. Because each virtual-force algorithm corresponds to a different physical system, we adopted a normalized approach for time scale in order to obtain a fair comparison.

We first visualized the similarity between the resulting network topologies and a perfect hexagon. In Figure 3, the resulting network topologies, with the Voronoi region for each sensor node, for both the VFA-DP (cf. Figure 3(c)) and VFA-LJ (cf. Figure 3(b)) are compared along with initial node deployment (cf. Figure 3(a)). In Figure 3(b), notice that there are a few imperfect Voronoi regions located near the right-lower corner of the target area. As a comparison, there is no obvious non-perfect Voronoi region in Figure 3(c). Therefore, network topology resulting from our proposed VFA-DP was closer to a perfect hexagon than that from the previous VFA-LJ.

Figure 3.

Node deployment for the virtual-force algorithms: (a) the initial node distribution, (b) the final node distribution for VFA-LJ, and (c) the final node distribution for VFA-DP. The network topology resulting from VFA-LJ has some defects, while the topology resulting from VFA-DP resembles a perfect hexagon.

As illustrated in Figure 4, the comparison can be made objectively using the pair correlation function $g (r)$ . Here, $a$ is the average equilibrium distance obtained from the final node distribution in Figure 3(a)–(c). Therefore, in order to discuss the network topology for the VFA-DP and the VFA-LJ based on $g (r)$ , it is better to normalize the node distance $r$ against $a$ . After the normalization, the ratio $r / a$ indicates the different rounds of the neighboring sensor nodes for a given node. Then, the $g (r)$ function shows the number of the nodes for different $r / a$ . Figure 4(a) presents the pair correlation function for initial node deployment with that of a perfect hexagon. The black lines indicate the $g (r)$ values of a perfect hexagon. The blue dashed line is the $g (r)$ variation from the initial node deployment against the ratio $r / a$ . As can be determined, the pair correlation function of the initial network topology is almost flat and represents uniformly distributed node deployment. The corresponding pair correlation diversion was determined to be 0.85. In Figure 4(b), we compare the pair correlation functions for network topologies resulting from both the VFA-DP and VFA-LJ with that of a perfect hexagon. As can been seen, the blue dashed line (from the VFA-DP) was closer to that of a perfect hexagon. Specially, the peaks were consistent with the black lines, which means the positions of sensor nodes from the VFA-DP were more consistent with the required locations from the perfect hexagon. However, the peaks of the red line (from the VFA-LJ) were lower and shifted from the black lines. It means that the positions of sensor nodes from the VFA-LJ deviated from the required positions of the perfect hexagon. The corresponding pair correlation diversions were 0.1768 and 0.5387 for VFA-DP and VFA-LJ, respectively. The network topology resulting from the VFA-DP was better than that obtained from the VFA-LJ.

Figure 4.

The pair correlation function: (a) for initial node deployment and (b) for the final node distributions (VFA-DP and VFA-LJ). The pair correlation function resulting from the VFA-LJ is misaligned with that for a perfect hexagon.

In addition, to evaluate the convergence rate of virtual-force algorithms, here, we leverage our proposed pair correlation diversion. The reader should note that energy consumption is proportional to the number of convergence steps. Thus, the faster the convergence rate, the less communication energy consumed. Users can adjust the calculation range of the VFA-DP to reduce the computational complexity and stop the VFA-DP based on the environment scenario and application requirements.

In order to compare the converge speeds of the VFA-DP and the VFA-LJ, in Figure 5, the calculation range of the VFA-DP was chosen to be slightly greater than one equilibrium distance $a$ . It means that the Yukawa potential was only calculated from the closest neighboring nodes of a given node, which is consistent with the VFA-LJ. In such a case, there is not much difference in the computational complexity between these two virtual-force algorithms. Thus, Figure 5 plots the pair correlation diversion as a function of the time index within the algorithm simulation process for both VFA-LJ and VFA-DP. Both curves exhibit similar trends including two phases. In the first phase, the diversion value decreases dramatically as time proceeds. The slope of the curve indicates the rate at which the algorithm converges. In the second phase, the diversion remains flat as time proceeds. During this phase, the algorithm generates a stable network topology. The converged value indicates how close the resultant topology is to that of a perfect hexagon.

Figure 5.

The pair correlation diversion decreases as the simulation steps increase. When the value is stabilized at a fixed value, the algorithm converges and the resulting network topology is stable.

As shown in Figure 5, our proposed VFA-DP converged much faster than the VFA-LJ and the converged diversion value of the VFA-DP was smaller than that of the VFA-LJ. For the same initial node deployment, the VFA-DP converged in approximately 1500 steps while the VFA-LJ converged in approximately 5000 steps, almost three times slower. The converged diversion value for the VFA-DP was approximately 0.2, while the diversion value for the VFA-LJ was around 0.4, indicating that the VFA-DP generated a better network topology. The difference may be caused by the fact that a dusty plasma system has a central confinement force, which can help the system fix defects in the initial distribution.

The dusty plasma system has a global attractive force that is related to pressure in the actual physical world. This pressure can help matter transform into a liquid or a solid crystal. As a result, it is no wonder that dusty plasma results in a better lattice and converges quicker. Systems using a Type II force (Table 1) can also utilize the attractive force to accelerate convergence and to achieve a better lattice. The central attractive force makes the method proposed in this article different from other virtual-force deployment methods due to partially centralized algorithms. Such are likely another example where centralized algorithms yield benefits to the engineering community.²⁹ In engineering, sensors should generally receive orders from center commanders and send collected information outward. As a result, it may not be an extra task for an engineering system to have a central attractive force.

For the Lennard-Jones potential in Garetto et al.,¹⁰ the final node distance is also the equilibrium point of the potential field. For a dusty plasma field, it is not easy to predict the final node distance in the resulting network topology, which may not be good for engineers. However, in our proposed VFA-DP, the node distance can be adjusted by carefully choosing the spring constant $k$ and the charge $Q$ in equation (7). Using a fixed $Q$ , we attempted to adjust $k$ to see how the final node distance responded to the adjustment. In Figure 6, we present the variation of the equilibrium distance $a$ between two sensor nodes for the VFA-DP as a function of spring constant $k$ . Here, $k_{0}$ is the value of $k$ used in Figure 3(c) and $a_{0}$ is the average node distance obtained from the final distribution in Figure 3(c). By adjusting the ratio $k / k_{0}$ , we can increase or decrease the spring constant and obtain the corresponding normalized node distance $a / a_{0}$ to check the influence of $k$ on the VFA-DP. It is obvious that a small spring constant can effectively increase the equilibrium distance, which will also increase the coverage area of the whole network. Thus, via simulation, predictions or plans for the node distances can be obtained prior to engineering in practice. As a result, in engineering, not only the form of the force but the value of the parameters also play an important role, which requires additional study.

Figure 6.

The normalized distance between sensor nodes for VFA-DP. The $x - axis$ corresponds to the normalized spring constant against the constant used in Figure 3(c). The $y - axis$ corresponds to the normalized node distance against the average node distance in Figure 3(c).

Conclusion and future work

In this article, we investigated virtual-force algorithms for node deployment in MSNs, with an objective of formulating the hexagonal network topology for maximal coverage at a minimal cost (in terms of the number of sensor nodes required).

We proposed a novel virtual-force algorithm (VFA-DP) inspired by physical laws in a 2D dusty plasma system. As suggested by observations in dusty plasma, it would always formulate a hexagonal network topology. For evaluating the performance of virtual-force algorithms, we proposed a new metric based on the pair correlation function that characterizes the node distance distribution in a crystalline structure in order to objectively measure how close the resulting network topology is to a perfect hexagon and how fast the virtual-force algorithm converges. Numerical simulations indicated that our proposed VFA-DP outperforms the VFA-LJ for both criteria. Since our algorithm can converge with fewer simulation steps, the deployment method using the VFA-DP can make the nodes converge with fewer communication and movement steps, and consumes less energy for these functions.

However, the force field we proposed has two components. One is the repulsive force and the other is the confinement force. The balance of these two components makes the system converge into a regular lattice. While the Lennard-Jones type of interaction force just drives the system to the point that most of the neighboring particles distance is a zero-force distance, the Lennard-Jones system is fully distributed and can converge without a central force. However, we believe that it is this central force that makes our proposed VFA-DP have better performance than the VFA-LJ.

In addition, based on the theory and the equations, it is better to calculate the Yukawa potential and the corresponding velocity/acceleration for a given sensor node from enough nodes (in the calculation range) which need to be considered in the algorithm. It is more like a global calculation. One obstacle may affect the balance of the Yukawa potential calculation. In such a case, the proposed VFA-DP probably has more twisted structures than the VFA-LJ when we apply them in coverage areas with obstacles. The obstacle avoidance in these two algorithms is definitely an interesting topic which we want to study in the following project.

For future work, we will also focus on characterizing the communication and movement energy cost of the virtual force method, because minimizing energy consumption is a critical design challenge in sensor networks. Understanding the influence of the various physical parameters within the deployment process is also an interesting physical problem, as well as an engineering problem, which will provide guidance for engineering by aiding deployment in complex environment.

Footnotes

Acknowledgements

The authors thank Mr Yanhua Liu at University of New Hampshire for his support on VFA-LJ simulation and Professor Amitava Bhattacharjee at University of New Hampshire for sharing his insights in the dusty plasma.

Handling Editor: Luca Reggiani

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: R.T. was supported by the National Science Foundation of China (NSFC) grants 41674144 and 41974195, and the Open Projects Funding of Lunar and Planetary Science Laboratory from MUST (grant no. 119/2017/A3).

ORCID iD

Rongxin Tang

References

Akyildiz

Sankanrasubramaniam

, et al. Wireless sensor networks: a survey. Comput Netw 2002; 38(4): 393–422.

Pompili

Melodia

Akyildiz

. Deployment analysis in underwater acoustic wireless sensor networks. In: 1st ACM international workshop on underwater networks, Los Angeles, CA, 25 September 2006, pp.48–55. New York: ACM.

Younis

Akkaya

Strategies and techniques for node placement in wireless sensor networks: a survey. Ad Hoc Netw 2008; 6(4): 612–655.

Bai

Kumar

Xuan

, et al. Deploying wireless sensors to achieve both coverage and connectivity. In: 7th ACM international symposium on mobile ad hoc networking and computing, Florence, 22–25 May 2006, pp.131–142. New York: ACM.

Poduri

Pattern

Krishnamachari

, et al. Sensor network configuration and the curse of dimensionality. In: 3rd IEEE workshop on embedded networked sensors, Cambridge, 30–31 May 2006. New York: IEEE.

Wang

Cao

La Porta

. Movement-assisted sensor deployment. In: 23rd international annual joint conference of the IEEE computer and communication societies, Hong Kong, China, 7–11 March 2004, pp.2469–2479. New York: IEEE.

Radzvilavičius

Rancova

Anisimovas

. Dimensional transitions in small Yukawa clusters. Phys Rev E 2012; 86(1): 016404.

Reichhardt

Olson Reichhardt

. Statics and dynamics of Yukawa cluster crystals on ordered substrates. Phys Rev E 2012; 85(5): 051401.

Barron

Domb

. On the cubic and hexagonal close-racked lattices. Proc Royal Soc London A: Math Phys Sci 1955; 227(1171): 447–465.

10.

Garetto

Gribaudo

Chiasserini

, et al. A distributed sensor relocation scheme for environmental control. In: IEEE international conference on mobile adhoc and sensor systems, Pisa, 8–11 October 2007, pp.1–10. New York: IEEE.

11.

Kershner

. The number of circles covering a set. Am J Math 1939; 61(3): 665–671.

12.

Szabo

Csendes

Casado

, et al. Equal circles packing in a square I—problem setting and bounds for optimal solutions. In: Szabo

Csendes

Casado

, et al. (eds) New trends in equilibrium systems. Boston: Springer, 2000, pp.1–15.

13.

Locateli

Raber

. Packing equal circles in a square: a deterministic global optimization approach. Discrete Appl Math 2002; 122(1): 139–166.

14.

Howard

Mataric

Sukhatmen

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

Arai

Fukuda

, et al. (eds) Autonomous robotic systems 5. Tokyo, Japan: Springer, 2002, pp.299–308.

15.

Heo

Varshney

. Energy-efficient deployment of intelligent mobile sensor networks. IEEE T Syst Man Cyb 2004; 35(1): 78–92.

16.

Zou

Chakrabarty

. Sensor deployment and target localization based on virtual forces. In: 22nd annual joint conference of the IEEE computer and communications societies, San Francisco, CA, 9 July 2003, pp.1293–1303. New York: IEEE.

17.

Poduri

Sukhatme

. Constrained coverage for mobile sensor networks. In: IEEE international conference on robotics and automation, New Orleans, LA, 6 July 2004, pp.165–171. New York: IEEE.

18.

Bhattacharjee

. Molecular dynamics simulations of mach cones in a two-dimensional Yukawa crystals. Phys Plasmas 2002; 9(8): 3349–3354.

19.

Chaikin

Lubensky

. Principles of condensed matter physics. Cambridge: Cambridge University Press, 2000.

20.

Zhang

Hou

. Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc & Sensor Wireless Networks 2005; 1(1): 89–124.

21.

Wong

Tsuchiya

Kikuno

. A self-organizing technique for sensor placement in wireless micro-sensor networks. In: 18th international conference on advanced information networking and applications, Fukuoka, Japan, 24 August 2004, vol. 1, pp.78–83. New York: IEEE.

22.

Chen

Sun

. Novel deployment schemes for mobile sensor networks. Sensors 2007; 7(11): 2907–2919.

23.

Wang

. Virtual forced-directed particle swarm optimization for dynamic deployment in wireless sensor networks. In: Huang

Heutte

Loog

(eds) International conference on intelligent computing. Berlin; Heidelberg: Springer, 2007, pp.292–303.

24.

Kribi

Minet

Laouiti

. Redeploying mobile wireless sensor networks with virtual forces. In: 2nd IFIP wireless days, Paris, 15–17 December 2009, pp.1–6. New York: IEEE.

25.

Merlino

Goreee

. Dusty plasma in the laboratory, industry and space. Physics Today 2004; 57(7): 32–39.

26.

Lennard-Jones

. On the determination of molecular fields. Proc Royal Soc London A: Math Phys Sci 1924; 106(738): 441–477.

27.

Lee

Dharne

Jayasuriya

. Potential field based hierarchical structure for mobile sensor network deployment. In: American control conference, New York, 9–13 July 2007, pp.5946–5951. New York: IEEE.

28.

Thomas

Morfill

. Melting dynamics of a plasma crystal. Nature 1996; 379: 806–809.

29.

Derr

Manic

. Wireless sensor network configuration—part I: mesh simplification for centralized algorithms. IEEE T Ind Inform 2013; 9(3): 1717–1727.