An Improved Group-Based Neighbor Discovery Algorithm for Mobile Sensor Networks

Abstract

Wireless sensor networks have been widely used in a variety of commercial and military applications, which often require neighbor nodes to establish connection quickly. Due to high mobility of nodes, it is a challenging issue to reduce discovery delay. Most discovery designs are based on pairwise and fixed duty cycle, in which discovery is passively achieved when two nodes wake up at the same time. In order to further improve the efficiency of neighbor discovery in mobile sensor networks, this paper proposes an improved group-based neighbor discovery algorithm (IGND) which dynamically adjusts the nodes’ active time based on spatial properties. This paper describes the network model and the algorithm implementation in detail. Simulation results show that the improved algorithm has a good effect in reducing discovery latency and promoting discovery efficiency.

1. Introduction

With the rapid development of modern information technology, electronic equipment has evolved from the previous fixed ones to modern mobile ones and the volume becomes ever-smaller. The research directions are also moving from static sensor networks to mobile ones [1], which gradually become a research hotspot. Mobile sensor networks are mainly used in national defense, environmental monitoring, wildlife monitoring, and other aspects. In mobile sensor networks, sensor nodes first discover their neighbors constantly through communicating with each other in the moving process. Then the collected information will be forwarded.

Neighbor discovery has attracted research attention in recent years. Lots of excellent algorithms are proposed and their efficiency is also verified, such as Disco [2] and U-Connect [3]. However, previous works mainly focus on how to ensure a pair of nodes can wake up simultaneously, which has long discovery latency. Besides, the above algorithms are based on the fixed duty cycle, which brings longer discovery latency. The design goal of these traditional discovery schemes is to discover neighbors with a more energy-efficient method, no matter how long it will take, as long as it is bounded. However, in many mobile applications, neighbor discovery has to be fast enough to enable crucial requirements, in which energy is not the most pressing concern. Thus, the need for a novel and quick discovery scheme for mobile sensor network arises.

Therefore in this paper, we advocate a group-based discovery with dynamical duty cycle. The adjusting of duty cycle is based on the potential number of neighbor nodes. An additional energy budget (in term of additional active slots) is used to perform quick neighbor discovery. By adjusting the time when nodes stay awake, more potential neighbor nodes can be discovered. Then the discovery latency can be reduced and the overall performance of the network can be improved. Specifically, our contributions are as follows.

• (i)

Most of the previous work focuses on scheduling designs for pairwise discovery with fixed duty cycle. We propose the group-based discovery with dynamic duty cycle, which can reduce discovery delay with small overhead.

(ii)

By fully extracting the spatial properties, nodes’ active time is adjusted based on the potential number of neighbor nodes, which can speed up the discovery process and is practical for many mobile applications.

(iii)

The performance of the proposed design is evaluated by extensive simulation studies. The results show that the discovery latency is reduced further compared with existing works.

The rest of the paper is organized as follows. Section 2 discusses the related works. Section 3 presents the network model and assumptions. Section 4 describes the basic design and makes a brief analysis of discovery delay. Section 5 presents the simulation results. Section 6 concludes the work.

2. Related Works

After years of research on the wireless sensor network, neighbor discovery is no longer a new technology, and lots of references and materials are available. The research of node discovery in which nodes always stay awake focuses on directional antenna [4, 5]; however, node discovery algorithms based on duty cycle are various, especially when the sensor nodes stay in mobile environments in which there is a high demand for discovery time, that means to find neighbor nodes as fast as possible.

There are many excellent algorithms of node discovery in mobile sensor network, such as stochastic-based protocols [6, 7], quorum-based protocols [8, 9], Disco [2], U-Connect [3], multichannel [10, 11], and conflict-based node discovery [12]. All these focus on how to ensure a pair of nodes to wake up simultaneously by a certain type of scheduling algorithm; after verification, these algorithms are effective and can ensure the nodes to discover their neighbors within a boundary of time. In stochastic-based protocols [6, 7], the nodes monitor, transfer, or sleep in stochastic cycle, getting a tradeoff compromise between the energy consumption and discovery delay. Quorum-based protocols [8] clarify the limitations on ensuring pairwise nodes to overlap in wake up time within a bounded time. Disco [2] introduces a neighbor discovery algorithm based on Chinese Reminder Theorem [13], in which the algorithm selects a pair of prime numbers as the cycle of nodes, and the selected prime numbers should meet the requirements of duty cycle. U-Connect [3] proposes a uniform neighbor discovery algorithm for symmetric and asymmetric duty cycle setting. It should be noted that U-Connect [3] for symmetric asynchronous solution is a 1.5-approximation algorithm, and the Quorum [8, 9] and Disco [2] are 2-approximation algorithms.

In traditional pairwise [2, 3, 6–12] algorithms, each node stays in active state and dormant state periodically, and the neighbor nodes in sensor networks must be in each other's communication range, only in this way we can ensure normal communication among nodes and data transmission. When two nodes schedule respectively according to their own work schedule and stay awake simultaneously, the two nodes can find each other, and add another one to their neighbor table, till now, a neighbor node is found.

Comparing with pairwise methods, group discovery [14, 15] reduces discovery delay significantly by proactively referring wake up schedules among a group of nodes. It also builds a schedule reference mechanism among nodes to expedite the discovery process. Nevertheless, in the initialization phase of group formation, there are only a small number of known schedules. Hence, nodes cannot proactively wake up in time to verify the neighbor nodes, which may bring long discovery latency.

In all, although there exist many excellent neighbor discovery algorithms [16], most of them are pairwise methods and the discovery latency is relatively higher. There is still much room to improve based on group discovery. In this work, we introduce a novel group discovery method with dynamic duty cycle.

3. Preliminaries for Neighbor Discovery

In this section, the network model and assumptions are defined for mobile sensor networks with low duty cycle [14, 17, 18]. Some background information on how mobile nodes can discover other nodes without any infrastructure support is also introduced.

If sensor nodes always stay awake to discover neighbors in the mobile sensor networks, the nodes may be in an idle state in most of the time. Namely, there is no information for broadcasting or transmission. Although the idle state can effectively reduce energy consumption, it still wastes a large amount of energy. According to statistics, the node accounts for approximately 99% of total energy consumption while in idle preparations [19].

In order to save the limited energy of sensor nodes, sensor nodes are often set with two kinds of states: active state and dormant state. And the time is divided into continuous fixed-length time slots. The node keeps the dormant state for most of time slots and becomes active in a few slots only for sensing and communicating. Specifically, sensor nodes can broadcast and receive information packets sent by neighbors in active state, while they turn off the modules of broadcasting and receiving in the dormant state.

By controlling active and dormant status of the sensors, the energy consumption can be reduced significantly. But it will also bring additional discovery latency because the sensors can discover each other only when neighbor nodes have overlapping active slots. In order to reduce the discovery latency, the group-based [14] neighbor discovery is proposed for low duty-cycle networks.

Figure 1 shows the group discovery process from a temporal perspective. At time $t=1$ , both node B and node C are in the active state and they are in communication range of each other, then node B discovers node C at time $t=1$ , and they form a group and become aware of each other's working schedule. Similarly, at time $t=5$ , node B discovers node A and adds it to its neighbor table. At time $t=10$ , node B wakes up proactively when node A is scheduled to be active and sends the schedule of node C to node A. At time $t=14$ , node A wakes up to verify whether node C is its neighbor; if so, node A finishes the discovering of the node C. Then a new group is formed and node A continues the neighbor discovery.

Figure 1

The group-based discovery process.

4. Algorithm Design

Our work is motivated by group-based discovery. The group-based discovery speeds up the discovery process by proactively referring wake up schedules among a group of nodes. The acceleration is mainly implemented from a temporal perspective. However, the embedded spatial properties are not fully considered. In fact, the position distribution of nodes in some scenarios can be obtained or estimated in advance. And the total number of nodes in a certain area can be estimated. Thus, the active time of nodes can be adjusted by comparing the number of possible total nodes and the discovered nodes by group-based algorithm. By adjusting the time when nodes stay awake, more potential neighbor nodes can be discovered. Then the discovery latency can be reduced. The following is the whole algorithm design.

Assume that the node's communication radius is $R$   and the moving speed is v. As shown in Figure 2, the node reaches $S^{\prime }$ from S. Its moving distance is

$$\begin{array}{cc}& \text{Distanc}{\text{e}}_{S\mathbf{\to }{S}^{\prime }}=v*t.\end{array}$$

(1)

Figure 2

Positions of before moving and after moving.

We denote the intersecting area of two communication circles as $\Delta S$ , and the area of new added region is $\Delta S^{\prime }$ . Consider the following:

$$\begin{array}{l}\Delta S=\mathrm{2}\left(\frac{\mathrm{2}\theta }{\mathrm{2}}*R^{\mathrm{2}}-S_{\text{SAB}}\right)=\mathrm{2}\left(\theta *R^{\mathrm{2}}-S_{\text{SAB}}\right)\hfill \\ S_{\text{SAB}}=\frac{\mathrm{1}}{\mathrm{2}}*\mathrm{2}R\sin \theta *\frac{\mathrm{1}}{\mathrm{2}}\text{Distanc}{\text{e}}_{S\mathbf{\to }{S}^{\prime }}\hfill \\ =\frac{\mathrm{1}}{\mathrm{2}}R\sin \theta *\text{Distanc}{\text{e}}_{S\mathbf{\to }{S}^{\prime }}\hfill \\ \cos \theta =\frac{\left(\mathrm{1}/\mathrm{2}\right)\text{Distanc}{\text{e}}_{S\to S^{\prime }}}{R}=\frac{\text{Distanc}{\text{e}}_{S\mathbf{\to }{S}^{\prime }}}{\mathrm{2}R}\hfill \\ \theta =\text{arccos}\hspace{0.17em}\frac{\text{Distanc}{\text{e}}_{S\mathbf{\to }{S}^{\prime }}}{\mathrm{2}R}.\hfill \end{array}$$

(2)

From the above formula, we can obtain the area of new added region as follows:

$$\begin{array}{cc}& \Delta S^{\prime }=\pi R^{\mathrm{2}}-\Delta S.\end{array}$$

(3)

Assume that the distribution of nodes in the network follows with λ, namely, $P~P(\lambda )$ . The number of nodes that will wake up is denoted as N, which is calculated based on the other known nodes’ schedules in group-based discovery algorithm. According to the characteristics of Poisson distribution, we know that the expected number of nodes in new added communication area S is as follows:

$$\begin{array}{cc}& E\left(S^{\prime }\right)=\lambda \Delta S^{\prime }.\end{array}$$

(4)

So the number of undiscovered nodes in the new added communication area S is

$$\begin{array}{cc}& E\left(S_{\text{no}}^{\prime }\right)=E\left(S^{\prime }\right)-N=\lambda \Delta S^{\prime }-N.\end{array}$$

(5)

Assume that the active time of a node, for example, node A, is $T_{\text{active}}$ , the proactive wakeup time is $T_{\text{proactive}}$ , and its period is T. We know that the ratio of the $E(S_{\text{no}}^{\prime })$ undiscovered neighbors are not within the active time of the node A is

$$\begin{array}{cc}& P_{\text{no}}^{\text{active}}={\left(\mathrm{1}-\frac{T_{\text{active}}+T_{\text{proactive}}}{T}\right)}^{E\left(S_{\text{no}}^{\prime }\right)}.\end{array}$$

(6)

In formula (6), $(T_{\text{active}}+T_{\text{proactive}})/T$ means that the ratio of one node is within the active time of the node A. Also we know that there are still some nodes that will not wake up within $T_{\text{active}}+T_{\text{proactive}}$ , then the active time of the node A should be adjusted to discover the neighbors that have not been found.

Now we change the active time of the node A from  $T_{\text{active}}$ to $T_{\text{active}}^{\prime }$ .

$$\begin{array}{cc}& T_{\text{active}}^{\prime }=\left(T_{\text{active}}+T_{\text{proactive}}\right)\left(\mathrm{1}+P_{\text{no}}^{\text{active}}\right).\end{array}$$

(7)

According to the new active time  $T_{\text{active}}^{\prime }$ , the node will additionally proactively wake up several slots to discover new potential neighbors.

As described above, the proposed algorithm is an improved group-based neighbor discovery algorithm, which fully utilizes the spatial properties. In the process of neighbor discovery, the active time of a sensor node is no longer fixed and dynamically adjusted according to the number of possible neighbor nodes. The added time slots are used to monitor and discover the neighbors in new added communication area, which can reduce the discovery latency further. The whole description of the proposed algorithm is as shown in Algorithm 1.

Algorithm 1

Input: The total number of sensor nodes n; Original duty cycle $D{C}_{\mathrm{0}}$ ; Time Slots

table of wake-up $Table\left(n\right)$ ; Neighbor tables of sensor nodes $NeighborTab\left(n\right)$ ;

Original time slot $t_{\mathrm{0}}$ ; Current time slot t; Next time slot $t_n$ ; The number of

discovered neighbors using group-based algorithm N.

Output: the number of discovered neighbors, discovery latency and energy

consumption.

(1) Init node parameters in mobile sensor network, including original duty cycle $D{C}_{\mathrm{0}}$ ,

the tables of time slots $Table\left(n\right)$ , neighbor tables $NeighborTab\left(n\right)$ and so on;

(2) At time t, node i moves from last position (Old Position), begins neighbor

discovery using the group-based algorithm and adds the discovered neighbors to its

neighbor table $NeighborTab\left(i\right)$ . Meanwhile, the number of nodes that will proactively

wake up is calculated based on known other nodes’ schemes, namely N;

(3) At time $t+\mathrm{1}$ , node i reaches new position (New Position). It adjusts the active

time according to $T_{\text{active}}^{\prime }$ , several additional slots are added to monitor and discover

the potential neighbors in new area.

(4) Continue to perform the neighbor discovery using the above method recursively.

(5) Get the experimental data, such as discovery delay, energy consumption and so on;

5. Simulation Study

In this section, we evaluate the performance of the proposed algorithm with Disco and group-based discovery algorithm through simulation. In particular, we study the impact of node density, duty cycle, radio range irregularity, and node density and moving style on system performance.

5.1. Simulation Environment

The software platform of the simulation is Windows 7 Ultimate and Visual Studio 2008. We use C++ language to simulate the algorithm and consider the scenario that 78 sensor nodes are placed on a 500 m × 500 m square field. The commercial mathematics software MATLAB is used to process the results of the simulation.

5.2. Simulation Results

5.2.1. Impact of Node Density

The first simulation tries to investigate the impact of node density [20] on system performances. Two performance indexes are considered, which are discovery latency and energy consumption, respectively. Figure 3(a) shows the relationship between the node density and the discovery latency. From Figure 3(a), we can see that, with the density of sensor nodes increasing, the discovery latency of pairwise (Disco) algorithm increases, while the latency decreases for both the group discovery and IGND algorithms. Obviously, compared with Disco and the group discovery algorithms, our discovery algorithm IGND has the lowest discovery delay. As for energy, all three algorithms increase with the density of node increasing, and the proposed algorithm consumes more than that by the other two algorithms (Figure 3(b)).

Figure 3

(a) Node density versus discovery delay. (b) Node density versus energy consumption.

5.2.2. Impact of Nodes Duty Cycle

The second simulation studies the impact of duty cycle on the discovery latency and energy consumption of the sensor network. As shown in Figure 4(a), while the duty cycle increases, the discovery latency for all three algorithms decreases. It should be pointed out that Disco has significantly longer latency than the group discovery and the IGND algorithms, and the IGND algorithm has the best performance in the aspect of discovery latency. As for the energy consumption, Disco is far less than the other two algorithms, and energy consumption of the IGND algorithm is almost the same as that of the discovery design (Figure 4(b)). With the increasing of nodes’ duty cycle, more active time is used to discover neighbors and communicate with each other, which will have short discovery latency but consume more energy.

Figure 4

(a) Node duty cycle versus discovery delay. (b) Node duty cycle versus energy consumption.

5.2.3. Impact of Radio Range Irregularity

In the practical application, the radio communication range is usually irregular. This simulation studies the impact of radio range irregularity [21] on system performances. In the simulation, the radio range irregularity is assumed to change from 0 to 90%. Figures 5(a) and 5(b) show the impact of radio range irregularity on the discovery delay and the energy consumption, respectively. As shown in the above two figures, the latency and the energy consumption of all three algorithms increases when the radio range irregularity increases, and the proposed discovery design has the shortest latency with the same degree of radio irregularity. The IGND design consumes more energy than both Disco and the group discovery method, because there are additional slots to discover more neighbors.

Figure 5

(a) Radio range irregularity versus discovery delay. (b) Radio range irregularity versus energy consumption.

5.2.4. Impact of Mobility Patterns

In order to reveal the impact of mobility patterns on the system performance, we simulate the system performance in the following two mobility patterns: random way and hotspot way. From Figure 6(a), we can get that the discovery latency decreases for both the two patterns with the increasing of node density. As is well known, the nodes moving in hotspot way are often clustered in some places in the network, so the nodes with this mobility pattern have less latency than the nodes moving in random way. However, the nodes which cluster together usually exchange data frequently; therefore, the nodes moving in hotspot way consume more energy (Figure 6(b)).

Figure 6

(a) Random way versus hotspot way. (b) Random way versus hotspot way.

6. Conclusions

This paper proposes an improved group-based neighbor discovery, in which the active time of nodes is not fixed and changes according to the number of potential neighbor nodes. Simulations show that the improved group-based discovery algorithm with dynamical active time has better performance in mobile sensor networks with higher node density. Although this algorithm increases the energy consumption of nodes, it significantly reduces the discovery latency of nodes. We will provide theoretical analysis of the proposed algorithm and optimize the discovery design for the underwater sensor network in the future work.