EasiND: Neighbor Discovery in Duty-Cycled Asynchronous Multichannel Mobile WSNs

Abstract

Neighbor discovery is one of the first steps to establish communication links between sensor nodes; thus it becomes a fundamental building block for wireless sensor networks (WSNs). Traditional neighbor discovery protocols mainly focus on static wireless networks or networks where all nodes operate on the same frequency. However, the proliferation of mobile devices and multichannel communications post new challenges to neighbor discovery problem. In this paper, we present a neighbor discovery protocol named EasiND for asynchronous duty-cycled multichannel mobile WSNs. First, we propose a neighbor discovery system based on quorum system, which can bound the discovery latency in multichannel scenarios with low power consumptions. Second, we design an optimal asynchronous neighbor discovery system for multichannel mobile WSNs based on cyclic difference set. It is optimal in the sense that it minimizes the power consumption with bounded discovery latency under desired duty cycles. Finally, we validate the performance of EasiND through both theoretical analysis and test-bed evaluations. EasiND provides a 33.3% reduction in power-latency product in theory compared to U-Connect. Meanwhile, test-bed evaluation results show that EasiND decreases average discovery latency by up to 86% compared to U-Connect and achieves at least 93.5% average fraction of discoveries in a predefined time limitation under various network conditions.

1. Introduction

Neighbor discovery, namely, the ability for each node to find the neighboring nodes in the physical proximity, is one of the first steps and a fundamental building block in configuring and managing wireless networks, since a node first has to find at least one potential target node within its communication range before initializing any data communications. For example, the information obtained from neighbor discovery, namely, the set of nodes that a node can directly communicate with, is needed to support basic functionalities such as medium access control and routing. Furthermore, this information is also needed by topology control and clustering protocols to enhance the performance and efficiency of the networks. Due to its critical importance, neighbor discovery has received a lot of attention, and a number of approaches have been proposed in the literature [1–9]. Most existing neighbor discovery schemes are designed for static wireless networks [2, 4, 10–13] or networks where all nodes operate on the same frequency (single-channel communication networks) [1, 3, 5]. Therefore, those neighbor discovery methods cannot be directly applied to multichannel mobile WSNs.

The rapid proliferation of millions of mobile sensor nodes and smart phones has resulted in a wide variety of mobile applications, such as mobile social networks and mobile sensing applications [14–17]. Meanwhile, the multichannel communications which allow radios tune their operating frequency over different channels provide new opportunities for improving the performance of wireless networks; thus they have been widely adopted by current WSN systems [18–20]. The mobility of sensor nodes and multichannel communication make neighbor discovery in such multichannel and mobile WSNs more challenging, especially to implement neighbor discovery schemes with high energy efficiency and low discovery latency without requiring clock synchronization between sensor nodes. So far, only several related methods have been proposed for multichannel WSNs [21–23]. These neighbor discovery schemes designed for personal area networks focus on reducing discovery latency but put less effort on energy conservation. However, discovery latency, energy consumption, and fraction of discoveries are all critical performance metrics for neighbor discovery scheme in asynchronous duty-cycled multichannel mobile WSNs. On the one hand, most mobile devices or sensor nodes are battery powered and require low energy consumption to prolong the network life as long as possible. On the other hand, in time-sensitive and data-intensive mobile applications, in order to enable full potential contact opportunities, it is very important for sensor nodes to discover as many as possible neighbors in a short time period.

To cope with the previous problems, we design a novel neighbor discovery scheme, named EasiND, for asynchronous duty-cycled multichannel mobile WSNs. The key goal for EasiND is to reduce power consumption, while still enabling effective neighbor discovery, where effectiveness can be determined by both the ability to discover more neighbors in a reasonable time constraint and the latency to discovery these neighbors.

The main contributions of this paper are summarized as follows.

• (i)

We first formulate the neighbor discovery problem in multichannel WSNs by connecting it with quorum system. Also, we introduce an algorithm using the intersection property of quorum system to construct a neighbor discovery system, which enables successful discoveries over multiple channels between any two neighbor discovery sequence.

(ii)

Without requiring global clock synchronization, we propose an algorithm to construct asynchronous neighbor discovery system for duty-cycled multichannel mobile WSNs by utilizing the rotation closure property of cyclic quorum systems. Our algorithm can bound the worse-case discovery latency and achieve minimum discovery latency in theory at desired duty cycle. Meanwhile, our scheme yields better performance in trade-off between power consumption and discovery latency.

(iii)

We evaluate our method through both theoretical analysis and test-bed experiments. Evaluation results show that our method consistently outperforms U-Connect in terms of power-latency product and fraction of discoveries under various network conditions.

The rest of the paper is organized as follows. We discuss related work on neighbor discovery in Section 2. In Section 3, we review some definitions and concepts about cyclic quorum system. Section 4 describes design details of EasiND. In Section 5, we present a detailed evaluation of EasiND. Finally, Section 6 concludes the paper.

2. Related Work

Neighbor discovery protocols for duty-cycled asynchronous wireless networks mostly operate on a time-slot basis, where they divide the time into slots and all nodes use the same size of the time slot. Based on the protocol used, nodes wake up during some specific active time slots to run the neighbor discovery process, and keep asleep during the remaining time slots. Once they are active in overlapping time slots, a successful discovery would happen between two neighbors. To be energy efficient, a neighbor discovery scheme must use as few active time slots as possible to discover as many neighbors as possible within a reasonable time limitation.

Current neighbor discovery methods fall broadly into the following two categories.

2.1. Single-Channel Based Methods

The neighbor discovery protocols where all nodes operate on the same operation frequency belong to this category. These neighbor discovery protocols can be further divided into two classes, probabilistic and deterministic.

The schemes proposed in [2, 4, 10, 24] are probabilistic, where each node chooses operating in transmit, listening or sleep states with certain predefined probability. In birthday protocol [10], nodes listen, transmit, or sleep in a probabilistic round-robin fashion, which provides a concrete way to trade off between discovery energy efficiency, success in discovering neighbors and discovery latency. The methods in [2, 24] are based on additional feedback mechanism. If a node cannot receive a beacon due to collisions, it transmits a feedback message. If a node does not receive any feedback message after transmitting a beacon, it goes into a passive state on the assumption that the beacon was successfully received. The paper [4] studies neighbor discovery in multipacket reception networks where packets from multiple transmitters can be received successfully at a receiver.

Deterministic neighbor discovery protocols let nodes wake up at specific time slots according to a deterministically designed schedule. The approaches presented in [1, 3, 11–13] belong to this category. The methods presented in [11, 13] are quorum based. In [11], the time is divided into a sequence of slots which are grouped into a $m\times m$ row major grid matrix within contiguous slots, where m is a global parameter which depends on the required duty cycle. Each node randomly picks a row and a column, in which the node keeps awake and the discovery between these two nodes will occur at two intersections. The paper [12] formulates wakeup schedule as a block design problem in combinatorics and gives an optimal solution which achieves minimum idle state energy consumption with bounded neighbor discovery latency. The Disco proposed in [1] is based on Chinese Remainder Theorem, where each node selects two prime numbers independently and begins to transmit and receive whenever the local counter of node is divisible by either of two primes. The sum of two primes' reciprocal is equal to node's duty cycle. To improve Disco's performance, U-Connect proposed in [3] presents an activation pattern using one prime p. Instead of just waking up only one time slot every p time slots, U-Connect also wakes up $(p+1)/2$ time slots every $p^2$ time slots. U-Connect achieves lower discovery latency when compared to Disco. The paper [9] presents a group-based discovery protocol as a performance add-on to existing pairwise mobile discovery designs. It designs a schedule reference mechanism among nodes to accelerate the discovery process. The paper [7] proposes an on-demand generic discovery accelerating middleware for many existing neighbor discovery protocols.

2.2. Multichannel Based Methods

In the literature, a lot of research work has been done for single-channel wireless networks. However, there are little work on neighbor discovery problem for multichannel wireless networks. Only several recent approaches are proposed for personal area networks or wireless mesh networks [21–23]. The SWEEP strategies in [22] are designed for IEEE 802.15.4-based networks operating in the beacon-enabled mode. SWEEP determines the listening schedule of discovering node to detect a foreign personal area network. Such a schedule decides when to listen on which channel and for how long. The paper [23] improves the performance of SWEEP by aggressively changing the channel after short, specifically selected time periods of observation with reusage of observations made on a given channel. The approach proposed in [21] is designed for multichannel wireless mesh networks. The focus of all the previous schemes is to minimize the discovery latency and they are inefficient in energy consumption.

In contrast to existing work, we study the neighbor discovery problem in asynchronous duty-cycled multichannel mobile WSNs. Our paper is motivated by the QCH introduced in [25], which establishes control channel for multichannel and dynamic spectrum access networks. Because QCH does not consider energy consumption problem, it cannot be directly applied to duty-cycled multichannel mobile WSNs. We extend QCH and propose a novel neighbor discovery protocol named EasiND for duty-cycled multichannel mobile WSNs. The main goal of EasiND is to reduce energy consumption, while still enabling effective neighbor discovery for multichannel communications, where effectiveness can be determined by both the ability to discover more neighbors in a reasonable time constraint and the latency to discovery these neighbors.

3. Preliminaries for Quorum System

In this section, we introduce some background knowledge related to the cyclic quorum system that will be used throughout this paper.

Definition 1.

Given a cycle length n, let $U=\{\mathrm{0,1},\dots ,n-1\}$ be a finite universal set of n elements. A quorum system G under U is a collection of nonempty subsets of U, which satisfies the following intersection property:

$$\begin{array}{cc}& \forall g,h\in G:\hspace{1em}g\cap h\ne \varnothing .\end{array}$$

(1)

Each $g\in G$ is a subset of U and is called a quorum.

Definition 2.

A set $D=\{a_1,a_2,\dots ,a_k\}$ modulo n, $a_i\in \{\mathrm{0,1},\dots ,n-1\}$ , is called a cyclic $(n,k,\lambda )$ -difference set if for every $d\not\equiv 0$ (mod n) there are exactly λ ordered pairs ( $a_i,a_j$ ), $a_i,a_j\in D$ such that $a_i-a_j\equiv d$ (mod n).

Definition 3.

A set $D=\{a_1,a_2,\dots ,a_k\}$ modulo n, $a_i\in \{\mathrm{0,1},\dots ,n-1\}$ , is called a relaxed cyclic ( $n,k$ )-difference set if for every $d\not\equiv 0$ (mod n) there exists at least one ordered pair ( $a_i,a_j$ ), $a_i$ , $a_j\in D$ such that $a_i-a_j\equiv d$ (mod n).

Theorem 4.

A group of sets $g_i=\{a_1+i,a_2+i,\dots ,a_k+i\}$ modulo n, $i\in \{\mathrm{0,1},\dots ,n-1\}$ , is a group of cyclic quorum sets if and only if $D=\{a_1,a_2,\dots ,a_k\}$ is a relaxed cyclic ( $n,k$ )-difference set.

Theorem 4 has been proved in [26], which demonstrates that we can construct cyclic quorum system using cyclic difference sets. For example, $D=\{\mathrm{0,1},2\}$ modulo 4 is a relaxed cyclic (4,3)-difference set. The sets $G=\{\{\mathrm{0,1},2\},\{\mathrm{1,2},3\},\{\mathrm{2,3},0\},\{\mathrm{3,0},1\}\}$ are a cyclic quorum system constructed by relaxed cyclic (4,3)-difference set $D=\{\mathrm{0,1},2\}$ (mod 4). The paper [13] has proved that any quorum g in a cyclic quorum system under $U=\{\mathrm{0,1},\dots ,n-1\}$ must have a cardinality $|g|\ge \sqrt{n}$ . That is to say, given n, the minimum size k of the quorums in cyclic quorum system is the $\sqrt{n}$ . In fact, we can achieve this theoretical lower bound by constructing the Singer difference sets [27]. Next, we give the Singer difference sets theorem which is introduced and proved in [28].

Theorem 5.

Let q be a prime power; then there exists a ( $n,k,1$ )-difference set under $Z_n$ . Such a difference set is called a Singer difference set. Here, $n=q^2+q+1$ , $k=q+1$ , and $Z_n$ denotes the set of nonnegative integers less than n.

Because $n=q^2+q+1$ and $k=q+1$ , so k approximates the lower bound $\sqrt{n}$ .

Definition 6.

Given an integer $i\ge 0$ and a quorum g in a quorum system G under U, we define $g+i=\{(x+i)\mathrm{mod}n:x\in g\}$ .

Definition 7.

A quorum system G under U is said to have the rotation closure property if $\forall g,h\in G$ , $i\in \{0,\dots ,n-1\}$ , $(g+i)\cap h\ne \varnothing$ .

For instance, the quorum system $G=\{\{\mathrm{0,1},2\},\{\mathrm{1,2},3\},\{\mathrm{2,3},0\},\{\mathrm{3,0},1\}\}$ under $\{\mathrm{0,1},\mathrm{2,4}\}$ has the rotation closure property.

The following theorem has been proved in [13].

Theorem 8.

The cyclic quorum system satisfies the rotation closure property.

4. Design of EasiND

In this section, we present the design of EasiND neighbor discovery protocol in detail. EasiND allows some nodes with no prior clock synchronization information to discover other networks or devices which would dynamically adapt their operating frequency over different channels. The discovery is completed in bounded time when nodes are within the transmission range of each other in ideal communication environment. For the ease of presentation, we first provide the problem formulation and introduce the synchronous neighbor discovery problem in duty-cycled multichannel mobile WSNs and then describe the asynchronous neighbor discovery system.

4.1. Problem Statement

We consider the following network scenarios. There are one or more mobile nodes which move around some existed networks or devices with unpredictable mobility patterns to collect data from or want to join in the existed networks. The existed networks adapt their operating frequency over different channels according to current communication conditions, and they periodically transmit beacons to let mobile nodes to discover them. Therefore, our neighbor discovery protocol EasiND consists of two key components, beacon scheduling sequence (BSS) and channel scanning sequence (CSS). Suppose there are N channels in our duty-cycled multichannel networks, labeled as $\mathrm{0,1},\dots ,N-1$ . For example, in IEEE 802.15.4-based 2.4 GHz WSN, there are 16 channels numbered from 11 to 26 that can be used in our implementation of EasiND. We assume that time is divided into neighbor discovery periods (NDPs), where each NDP is composed of T time slots. For the sake of expression, we assume that each time slot is of unit duration so that each NDP is also T. We assume that all nodes use the same duty cycle; namely, we consider symmetric duty-cycled systems and leave the neighbor discovery in asymmetric duty-cycled multichannel WSNs to future study. Moreover, we assume that all nodes in network are synchronized with each other for the time being. We will present the design of asynchronous neighbor discovery system which does not require global clock synchronization in Section 4.3.

Next, for the sake of clarification, we present the design of BSS and CSS, respectively. The uniform formulation of BSS and CSS is reasonable, as we will see.

A BSS determines the intervals of time at which each network or device transmits beacons on its current operating channel. We represent a BSS s of period T as a set of triples:

$$\begin{array}{l}s=\{(0,x\left(0\right),c),(1,x\left(1\right),c),\dots ,(i,x\left(i\right),c),\dots ,\\ \hspace{0.5em}(T-1,x(T-1),c)\},\end{array}$$

(2)

where $c\in \{\mathrm{0,1},\dots ,N-1\}$ and $x(i)$ is a binary value function which is defined by the following formulation:

$$\begin{array}{cc}& x\left(i\right)=\{\begin{array}{cc}0,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}\text{node}\hspace{0.17em}\hspace{0.17em}\text{goes}\hspace{0.17em}\hspace{0.17em}\text{to}\hspace{0.17em}\hspace{0.17em}\text{sleep}\hspace{0.17em}\hspace{0.17em}\text{in}\hspace{0.17em}\hspace{0.17em}\text{the}\hspace{0.17em}\hspace{0.17em}i\text{th}\hspace{0.17em}\hspace{0.17em}\text{time}\hspace{0.17em}\hspace{0.17em}\text{slot},\hfill \\ 1,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}\text{node}\hspace{0.17em}\hspace{0.17em}\text{becomes}\hspace{0.17em}\hspace{0.17em}\text{awake}\hspace{0.17em}\hspace{0.17em}\text{in}\hspace{0.17em}\hspace{0.17em}\text{the}\hspace{0.17em}\hspace{0.17em}i\text{th}\hspace{0.17em}\hspace{0.17em}\text{time}\hspace{0.17em}\hspace{0.17em}\text{slot}.\hfill \end{array}\end{array}$$

(3)

The triple $(i,x(i),c)$ indicates that network transmits beacons in the $i\text{th}$ time slot of a BSS period T on channel c if $x(i)$ is equal to 1.

A CSS determines the schedule with which each mobile node scans all available channels. We denote a CSS r of period T as a set of triples:

$$\begin{array}{l}r\hspace{0.17em}=\hspace{0.17em}\{(0,x\left(0\right),c_0),(1,x\left(1\right),c_1),\dots ,(i,x\left(i\right),c_i),\dots ,\\ \hspace{0.5em}(T-1,x(T-1),c_{T-1})\},\end{array}$$

(4)

where $c_i\in \{\mathrm{0,1},\dots ,N-1\}$ represents the channel index of sequence r in the $i\text{th}$ time slot of a CSS period and i is the slot index. The triple $(i,x(i),c_i)$ indicates that mobile node becomes awake and goes to operate on channel $c_i$ at the $i\text{th}$ time slot when $x(i)$ equals 1.

Given two sequences s and r, if $(x,y,z)\in s\cap r$ and $y=1$ , the triple $(x,y,z)$ is called an overlap between s and r. In this case, the $x\text{th}$ time slot is called rendezvous time slot and channel z is called rendezvous channel between s and r. If network selects s and mobile node selects r, respectively, as their neighbor discovery scheduling sequence, then successful discovery occurs in the rendezvous time slots on rendezvous channels.

Let $I(s,r)$ denotes a binary value function that indicates whether the triple $(x,y,z)$ is an overlap between s and r, for example,

$$\begin{array}{cc}& I_{x,z}(s,r)=\{\begin{array}{cc}1,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}\exists y=1,\hspace{0.17em}\hspace{0.17em}\text{s.t.}\hspace{0.17em}\hspace{0.17em}\left(x,y,z\right)\in s\cap r,\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(5)

Let $O(s,r)$ denotes the number of overlaps between s and r. Then, we have

$$\begin{array}{cc}& O(s,r)=\sum _{x=0}^{T-1}\hspace{0.17em}‍\sum _{z=0}^{N-1}‍I_{x,z}(s,r).\end{array}$$

(6)

Let $P_x(s)$ denotes a binary value function which indicates whether node keeps awake in the time slot x in the sequence of s of period T. Specifically, $P_x(s)$ is defined as follows:

$$\begin{array}{cc}& P_x\left(s\right)=\{\begin{array}{cc}1,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}y=1,\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(7)

Let $D_{\text{BSS}}(s)$ and $D_{\text{CSS}}(r)$ denote the number of time slots on which nodes keep awake in the sequences s and r of period of T, respectively. Then, we have

$$\begin{array}{cc}& D_{\text{BSS}}\left(s\right)=\sum _{x=0}^{T-1}‍P_x\left(s\right),\\ D_{\text{CSS}}\left(r\right)=\sum _{x=0}^{T-1}‍P_x\left(r\right).\end{array}$$

(8)

Based on our assumption of symmetric duty-cycled system, we have $D_{\text{BSS}}(s)=D_{\text{CSS}}(r)$ .

Thereby, we have the following neighbor discovering system design problem.

Problem 9.

Give T and C, where C denotes the duty-cycle used by nodes in our system, the neighbor discovery system in duty-cycled multichannel mobile WSNs is to devise a set of BSS of period T denoted as S, and a set of CSS of period T denoted as R, which satisfy the following three properties:

• (1)

$\forall s\in S$ and $\forall r\in R$ , $|s|=T$ and $|r|=T$ ;

(2)

$k\ge 1$ , where $k={\min }_{\forall s\in S,\forall r\in R}\{O(s,r)\}$ ;

(3)

$D_{\text{BSS}}(s)=D_{\text{CSS}}(r)\le C\times T$ .

From (2) and (4), we know that the only difference between the constructions of s and r is that the BSS s uses the same channel during the whole period of T; however, the CSS r should visit all the channels available in the system. Therefore, we can design a uniform set of neighbor discovery sequences of period of T for BSS and CSS using (4), denoted as Q. So, we have $S\subset Q$ and $R\subset Q$ . The set Q is called a neighbor discovery system of period of T. The k and $D_{\text{BSS}}(s)/T=D_{\text{CSS}}(r)/T$ are the overlapping degree and duty cycle of the neighbor discovery system Q, respectively.

It is already clear that a neighbor discovery system Q is a quorum system under the universal set $U=\{(x,y,z)\mid x\in [0,T-1],y\in \{\mathrm{0,1}\},z\in \{\mathrm{0,1},\dots ,N-1\}\}$ , because it satisfies the intersection property: any two sequences in Q have at least one overlap. Each neighbor discovery sequence in Q is a quorum.

4.2. Construction of Quorum-Based Neighbor Discovery System in Duty-Cycled Multichannel Mobile WSNs

In this section, we present an algorithm which uses a quorum system to construct a neighbor discovery system Q for duty-cycled multichannel mobile WSNs; namely, we need to construct a set of BSS S and CSS R of period T, such that they satisfy three properties defined in Problem 9. We refer to such algorithm as Algorithm 1.

Algorithm 1: Quorum-based neighbor discovery system construction algorithm.

Input:

  m, N, a channel set $C=\{0,1,\dots ,N-1\},U=$

   $\{\mathrm{0,1},\dots ,m-1\}$ , a quorum system G under U and a

  binary variable b, $b=0$ demonstrates that we need to

  construct BSS s, otherwise, to construct CSS r;

Output:

  Q;

(1)  $Q=\varnothing$ ;

(2) for $j=0$ to ( $|G|-1$ ) do

(3)  for $f=0$ to ( $N-1$ ) do

(4)   for   $i=0$ to ( $m-1$ ) do

(5)    if   $i\in g_j$   then

(6)     if   $b=0$   then

(7)       $x(i+f·N)=1$ ;

(8)       $c=c_{\text{bss}}$ ;

(9)     else

(10)      $x(i+f·N)=1$ ;

(11)      $c=c_{\text{css}}=f$ ;

(12)    end if

(13)   end if

(14)   if   $z\notin g_j$   then

(15)     $x(i+f·N)=0$ ;

(16)     $c=c_r$ , randomly selected from the set

      $\{\mathrm{0,1},\dots ,N-1\}$ ;

(17)   end if

(18)  end for

(19) end for

(20)  $S=S\cup s$ , $R=R\cup r$ , $Q=S\cup R$ ;

(21) end for

4.2.1. Construction of BSS

First, we introduce the algorithm to construct BSS set S, which is easily to be modified to construct CSS set R as we will see. Without loss of generality, we assume that each BSS s is composed of N segments, where each segment is composed of m time slots. Therefore, the period of each BSS is $T=m\times N$ . Specifically, suppose $m=7$ and $N=3$ ; then, we have the following construction process.

• (1)

First, we construct a universal set $U=\{\mathrm{0,1},\mathrm{2,3},\mathrm{4,5},6\}$ and a quorum system G under U. Let $G=\{g_0,g_1,g_2,g_3\}$ ; then we can construct the following quorums:

$$\begin{array}{cc}& g_0=\{\mathrm{0,1},2\},\\ g_1=\{\mathrm{0,2},3\},\\ g_2=\{\mathrm{1,2},3\},\\ g_3=\{\mathrm{1,2},4\}.\end{array}$$

(9)

(2)

Using the quorum $g_0\in G$ , we construct a BSS $s_0$ using the following procedures.

• (i)

We make the beacon transmission schedule for the first segment of m time slots using the following two equations:

$$\begin{array}{cc}& x\left(i\right)=\{\begin{array}{cc}1,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}i\in g_0,\hfill \\ 0,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}i\notin g_0,\hfill \end{array}\\ c=\{\begin{array}{cc}{c}_{\text{bss}},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}i\in g_0,\hfill \\ c_r,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}i\notin g_0,\hfill \end{array}\end{array}$$

(10)

 

where $c_{\text{bss}}$ is the channel which network operates on and $c_r$ is a randomly selected channel from $\{\mathrm{0,1},\dots ,N-1\}$ . $x(i)$ indicates in which time slots the network should keep awake. For the sake of uniformity, we schedule the network to work on channel $c_r$ when the node turns off its radio. In the practical implementation of EasiND, we make no difference between these two cases because it makes no sense to schedule an operating channel for a node when its radio is turned off.

(ii)

Repeat the previous procedure to make beacon transmission schedule for each of other two segments. It is should be noted that in the remaining segment, the time slot index i should be the modulo over m for constructing the previous two equations $x(i)$ and c.

(3)

Repeat step (2) for each of the other quorums in G, for example, $g_1=\{\mathrm{0,2},3\}$ , $g_2=\{\mathrm{1,2},3\}$ , and $g_3=\{\mathrm{1,2},4\}$ , to construct other three BSSs $s_1$ to $s_3$ . The four BSSs, namely, $s_0$ , $s_1$ , $s_2$ , $s_3$ , are the elements of the set S, where each sequence has a period of T.

The beacon transmission schedules in BSS set S are illustrated in Figure 1. One quorum in G is used to construct a beacon transmission schedule in S. Thus, we have $|G|=|S|$ . Note that $\forall s_0$ , $s_1\in S$ , there are two corresponding quorums $g_0,g_1\in G$ used to construct $s_0$ and $s_1$ , respectively. Every beacon transmission schedule in S has the same period of T, where $T=m\times N$ . Because of the intersection property of G, $g_0$ and $g_1$ overlap at least N times on a specific channel $c_{\text{bss}}$ in period of T.

Figure 1

An illustration of BSS set S with $m=3$ , $N=3$ , $c_{\text{bss}}=1$ . The pair in the grey box indicates that the network becomes awake on channel $c_{\text{bss}}$ , and the pair in the white box indicates that the network goes into sleep to save energy. The variable c in white box is randomly selected from the set $\{\mathrm{0,1},\dots ,N-1\}$ .

4.2.2. Construction of CSS

We employ the same algorithm to construct CSS set R, except that in Step (2) we use the following different equation to design channel scanning scheme. Here, $c_{\text{css}}$ is setted to different value in three segments, which indicates the channel that a node should scan. As shown in Figure 2, which illustrates the channel scanning schedules in R, the $c_{\text{css}}$ is set to 0 in the first seven time slots (first segment), and 1 in the second seven time slots (second segment), and 2 in the third seven time slots (third segment). Therefore, the node should have scanned each channel at least once in the period of T time slots. That is why we divide the period of T into N segments:

$$\begin{array}{cc}& c\left(i\right)=\{\begin{array}{cc}{c}_{\text{css}},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}i\in g_0,\hfill \\ c_r,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}i\notin g_0.\hfill \end{array}\end{array}$$

(11)

Figure 2

An illustration of CSS set R with $m=3$ , $N=3$ . The pair in the grey box indicates that the network becomes awake on channel $c_{\text{css}}$ , which is 0 in the first seven time slots (first segment), 1 in the second seven time slots (second segment), and 3 in the last seven time slots (third segment). The specific allocation procedure of $c_{\text{css}}$ refers to lines 8 and 11 in Algorithm 1. The pair in the white box indicates that the network goes into sleep to save energy. The variable c in white box is randomly selected from the set $\{\mathrm{0,1},\dots ,N-1\}$ .

Note that $\forall s\in S,\hspace{0.17em}\hspace{0.17em}r\in R$ ; we have $s\cap r\ne \varnothing$ because we use the same procedures and quorum system G to construct S and R. Therefore, the Q which includes S and R is a neighbor discovery system that satisfies the requirements of Problem 9. We refer to the neighbor discovery system constructed using Algorithm 1 as a quorum-based neighbor discovery system.

4.3. Quorum-Based Asynchronous Neighbor Discovery System in Duty-Cycled Multichannel Mobile WSNs

In this section, we present an asynchronous neighbor discovery system which does not require global clock synchronization based on the rotation closure property of cyclic quorum system. The objective is to design an asynchronous BSS set S and CSS set R, so that $\forall s\in S$ and $\forall r\in R$ overlap by at least half of a time slot for every NDP of period T; even the time slot boundaries are misaligned by an arbitrary amount.

We extend the concept of the rotation closure property in Definition 7 to enable its application to our asynchronous neighbor discovery system. We will demonstrate that a neighbor discovery system with the rotation closure property is an asynchronous neighbor discovery system which requires no global clock synchronization.

Definition 10.

Given an integer $i\ge 0$ , a BSS sequence s and a CSS sequence r in a neighbor discovery system Q of period T, we define

$$\begin{array}{l}s+i\hspace{0.17em}=\hspace{0.17em}\{\left(j,x\left(j\right),c\left(j\right)\right)\mid x\left(j\right)=x_s\left((j+i)\mathrm{mod}T\right),\\ \hspace{0.5em}c\left(j\right)=c_s\left((j+i)\mathrm{mod}T\right),\\ \hspace{0.5em}j\in \left[0,T-1\right]\phantom{\left(j,x\left(j\right),c\left(j\right)\right)}\},\\ r+i\hspace{0.17em}=\hspace{0.17em}\{\left(j,x\left(j\right),c\left(j\right)\right)\mid x\left(j\right)=x_r\left(\left(j+i\right)\mathrm{mod}T\right),\\ \hspace{0.5em}c\left(j\right)=c_r\left(\left(j+i\right)\mathrm{mod}T\right),\\ \hspace{0.5em}j\in \left[0,T-1\right]\phantom{\left(j,x\left(j\right),c\left(j\right)\right)}\},\end{array}$$

(12)

where $x_s((j+i)\mathrm{mod}T)$ and $c_s((j+i)\mathrm{mod}T)$ are the $(j+i)\text{th}$ element in s, and $x_r((j+i)\mathrm{mod}T)$ and $c_r((j+i)\mathrm{mod}T)$ are the $(j+i)\text{th}$ element in r. For example, given $T=8$ , $m=4$ , $N=2$ , and

$$\begin{array}{l}r\hspace{0.17em}=\hspace{0.17em}\{(\mathrm{0,1},0),(\mathrm{1,1},0),(\mathrm{2,1},0),(\mathrm{3,0},c),\\ \hspace{0.5em}(\mathrm{4,1},1),(\mathrm{5,1},1),(\mathrm{6,1},1),(\mathrm{7,0},c)\},\end{array}$$

(13)

we have

$$\begin{array}{l}r+2\hspace{0.17em}=\hspace{0.17em}\{(\mathrm{0,1},0),(\mathrm{1,0},c),(\mathrm{2,1},1),(\mathrm{3,1},1),\\ \hspace{0.5em}(\mathrm{4,1},1),(\mathrm{5,0},c),(\mathrm{6,1},0),(\mathrm{7,1},0)\}.\end{array}$$

(14)

Definition 11.

A neighbor discovery system Q of period T is said to have the rotation closure property if $\forall s,r\in Q,\hspace{0.17em}\hspace{0.17em}i\in [0,T-1],\hspace{0.17em}\hspace{0.17em}s\cap (s+i)\ne \varnothing ,\hspace{0.17em}\hspace{0.17em}r\cap (r+i)\ne \varnothing ,\hspace{0.17em}\hspace{0.17em}r\cap (s+i)\ne \varnothing$ and $s\cap (r+i)\ne \varnothing$ .

Theorem 12.

If a neighbor discovery system Q of period of T satisfies the rotation closure property, any pair of $s\hspace{0.17em}\hspace{0.17em}(s\in S)$ and $r\hspace{0.17em}\hspace{0.17em}(r\in R)$ in Q must overlap at least once for every T consecutive time slots even when the time slot boundaries are misaligned by an arbitrary amount.

Proof.

Suppose that a neighbor discovery system Q satisfies the rotation closure property and two nodes, U and V, respectively; select sequences s and r from S and R. For the sake of easy description, we assume that the length of time slot is 1. We consider the following two cases.

• (1)

The time slot boundaries are aligned. Without loss of generality, we suppose that node U's clock is i slots ahead of node V's clock. Relative to node V's clock, node U's sequence s is equivalent to $r+i$ . Because of the rotation closure property of Q, we have $s\cap (r+i)\ne \varnothing$ . Therefore, two sequences s and r must overlap at least one time slot in the period of T. It is obvious that we can obtain the same results with the assumption that node V's clock is i slots ahead of node U's clock.

(2)

The time slot boundaries are misaligned. Suppose that node U's clock is ahead of node V's clock by an arbitrary amount of time, such as $i+\delta$ , where $i\in [0,m-1]$ , $0<\delta <1$ . If we advance node V's clock by δ, and the sequence r turns into $r^{\prime }$ , then, the boundaries of s and $r^{\prime }$ are aligned and must overlap at least one time slot in the period of T. Therefore, two sequences s and r must overlap at least δ time slot in every period of T.

Theorem 12 states that any neighbor discovery system Q with closure rotation property can guarantee successful discoveries between two nodes, which select BSS sequence from S and CSS sequence from R, respectively, although they are not synchronized with each other. We call such quorum-based neighbor discovery system which satisfies the rotation closure property an quorum-based asynchronous neighbor discovery system. Next, we introduce an algorithm to construct a quorum-based asynchronous neighbor discovery system.

4.3.1. Construction of Quorum-Based Asynchronous Neighbor Discovery System

Here, we extend the Algorithm 1 based on cyclic quorum system introduced in [26] to achieve this objective. Specifically, in step (1) of Algorithm 1, we first construct a relaxed cyclic ( $m,k$ )-different set $D=\{a_1,a_2,\dots ,a_k\}$ , then we construct a cyclic quorum system G which consists of group of cyclic quorum sets $g_i=\{a_1+i,a_2+i,\dots ,a_k+i\}\mathrm{mod}m$ , where $i\in \{\mathrm{0,1},\dots ,m-1\}$ . For example, we construct a relaxed cyclic (7,3)-different set $D=\{\mathrm{1,2},4\}$ and a cyclic quorum system G under D. Let $G=\{g_0,g_1,g_2,g_3,g_4,g_5,g_6\}$ , then we have

$$\begin{array}{cc}& g_0=\{\mathrm{1,2},4\},\\ g_1=\{\mathrm{2,3},5\},\\ g_2=\{\mathrm{3,4},6\},\\ g_3=\{\mathrm{4,5},0\},\\ g_4=\{\mathrm{5,6},1\},\\ g_5=\{\mathrm{6,0},2\},\\ g_6=\{\mathrm{0,1},3\}.\end{array}$$

(15)

After building the cyclic quorum system G, we construct BSS set S and CSS set R using the same procedures of step (2) and step (3) in Algorithm 1. An asynchronous BSS and CSS based on the previous relaxed cyclic (7,3)-difference set $D=\{\mathrm{1,2},4\}$ and cyclic quorum system G are illustrated in Figures 3 and 4. We refer to this construction algorithm for quorum-based asynchronous neighbor discovery system as Algorithm 2.

Algorithm 2: Quorum-based asynchronous neighbor discovery system construction algorithm.

Input:

  m, N, k, a channel set $C=\{\mathrm{0,1},\dots ,N-1\}$ , and a binary

  variable b, $b=0$ demonstrates that we need to construct

  BSS s, otherwise, to construct CSS r;

Output:

  Q;

(1)  $Q=\varnothing$ ;

(2) construct a relaxed cyclic ( $m,k$ )-difference set $D=$

   $\{a_1,a_2,\dots ,a_k\}$ ;

(3) construct a cyclic quorum system $G=\{g_0,g_1,\dots ,g_m\}$

  using the relaxed cyclic $(m,k)$ -difference set D;

(4) for   $j=0$ to ( $|G|-1$ ) do

(5)   for   $f=0$ to ( $N-1$ ) do

(6)    for   $i=0$   to ( $m-1$ ) do

(7)     if   $i\in g_j$   then

(8)      if   $b=0$   then

(9)        $x(i+f·N)=1$ ;

(10)       $c=c_{\text{bss}}$ ;

(11)     else

(12)       $x(i+f·N)=1$ ;

(13)       $c=c_{\text{css}}=f$ ;

(14)     end if

(15)    end if

(16)    if   $z\notin g_j$   then

(17)      $x(i+f·N)=0$ ;

(18)      $c=c_r$ , randomly selected from the set

       $\{\mathrm{0,1},\dots ,N-1\}$ ;

(19)    end if

(20)   end for

(21)  end for

(22)   $S=S\cup s$ , $R=R\cup r$ , $Q=S\cup R$ ;

(23) end for

Figure 3

An illustration of beacon scheduling system BSS S with $m=7$ , $N=3$ , $c_{\text{bss}}=1$ and a relaxed cyclic difference $D=\{\mathrm{1,2},4\}$ . The pair in the grey box indicates that the network becomes awake on channel $c_{\text{bss}}$ , and the pair in the white box indicates that the network goes into sleep to save energy. The variable c in white box is randomly selected from the set $\{\mathrm{0,1},\dots ,N-1\}$ .

Figure 4

An illustration of channel scanning system CSS R with $m=7$ , $N=3$ and a relaxed cyclic difference $D=\{\mathrm{1,2},4\}$ . The pair in the grey box indicates that the network becomes awake on channel $c_{\text{css}}$ , which is 0 in the first seven time slots (first segment), 1 in the second seven time slots (second segment), and 2 in the last seven time slots (third segment). The pair in the white box indicates that the network goes into sleep to save energy. The variable c in white box is randomly selected from the set $\{\mathrm{0,1},\dots ,N-1\}$ .

Because of the rotation closure property of the cyclic quorum system G, it is obvious to conclude that the neighbor discovery system Q of period T constructed by Algorithm 2 satisfies the rotation closure property.

5. Performance Evaluation

In this section, we evaluate the performance of EasiND with earlier method U-Connect proposed in [3].

5.1. Evaluation Metrics

We consider two metrics, namely, power-latency product (PLP) and fraction of discoveries (FD) to evaluate neighbor discovery system.

5.1.1. Power-Latency Product

In duty-cycled asynchronous multichannel mobile WSNs, energy efficiency and discovery latency are two key performance metrics to evaluate the neighbor discovery system. On the one hand, nodes adopt low duty cycle to reduce energy consumption. On the other hand, nodes need to complete quick successful neighbor discovery for further exchanging control information or data communication. Particularly, in mobile sensor networks, nodes require lower neighbor discovery latency to quickly establish network connection for time-sensitive data communication. It is obvious that there is a trade-off between achieving high energy efficiency and reducing the neighbor discovery latency. Therefore, we use the metric power-latency product (PLP) introduced in [3] to trade off between energy efficiency and discovery latency. It is defined as the product of the average power consumption with the worst-case neighbor discovery latency in an ideal communication channel.

5.1.2. Fraction of Discoveries

Another important metric, fraction of discoveries (FD), is often used to evaluate the performance of neighbor discovery protocol. In our paper, it is defined as the number of neighbors discovered in a fixed time limits. It is very important to discover more neighbors in a short time for data-intensive applications in mobile WSNs. For example, in order to increase the opportunities of delivering more data, network needs to discover more mobile sinks when they come into its communication range as quickly as possible.

5.2. Theoretical Analysis for PLP

As presented in the previous section, we adopt slotted neighbor discovery schedules. There are many advantages to employ slotted discovery mechanism as discussed in [3], such as easy implementation and overcoming clock drift problem. Therefore, the average power consumption can be defined as the ratio between active and dormant time slots. According to Theorem 5, we can construct an optimal cyclic quorum system G based on Singer difference set. Therefore, the average power consumption of EasiND constructed by G in period of T is

$$\begin{array}{cc}& P_e=\frac{k}{k^2-k+1},\end{array}$$

(16)

where $k-1$ is a prime power and $k^2-k+1$ is the size of neighbor discovery schedule segment, that is, $m=k^2-k+1$ . Then, the theoretical optimal PLP of EasiND is

$$\begin{array}{cc}& {\text{PLP}}_e=P_e\times m=k=\sqrt{m-\frac{3}{4}}+\frac{1}{2}.\end{array}$$

(17)

As presented in [3], the PLP of U-Connect is:

$$\begin{array}{cc}& {\text{PLP}}_u=\frac{3p+1}{2},\end{array}$$

(18)

where p is a prime and $p^2=m$ . So, we have

$$\begin{array}{cc}& {\text{PLP}}_u=\frac{3p+1}{2}=\frac{3\sqrt{m}+1}{2}.\end{array}$$

(19)

Therefore, from (17) and (19), we find out that the PLP of EasiND is only two-third of that of U-Connect in theory. Figure 5 shows the power-latency product for EasiND and U-Connect at various discovery latency requirements. Figure 6 illustrates the average energy consumption for EasiND and U-Connect at various discovery latency requirements. The ideal theoretical results demonstrate that EasiND reduces energy consumption and achieves better PLP performance when compared to U-Connect.

Figure 5

The power-latency product for EasiND and U-Connect at various discovery latency requirements.

Figure 6

The average power consumption for EasiND and U-Connect at various discovery latency requirements.

5.3. Test-Bed Evaluation

We implement EasiND on our Ez240 wireless sensor node [29], as shown in Figure 7, using TinyOS 2.1 operating system. The Ez240 is equipped with a CC2420 radio [30], which operates on a total of 16 channels in 2.4 GHz ISM band, numbered from 11 to 26. Each of these channels is 2 MHz width with a center frequency separation of 5 MHz for adjacent channels. We also extend and implement the U-Connect on our Ez240 platform for comparison purpose. Here, we refer the extended version of U-Connect for multichannel WSNs as U-Connect-MC. Figure 8 shows the preparation time for data transmission on Ez240 node, which includes the time to turn on the radio, configures transmission frequency, and preprocess data for transmission. We can find that the time needed to prepare for data transmission ranges from 6 to 18 milliseconds under various experiments. We use $t_s$ to denote the length of a time slot. We have made various experiments under different $t_s$ value and found that discovery performance degrades when $t_s<18$ milliseconds. Therefore, we use $t_s=18$ milliseconds in the rest of the paper unless specified. Moreover, in order to maximize the probability of successful discoveries when time slots are misaligned, we use the same method introduced in [1] that nodes send a discovery message at the beginning and end of the time slot.

Figure 7

Ez240 wireless sensor node.

Figure 8

Evolution of preparation time for data transmission. CCA is enabled, and the link-layer retransmission is disabled.

We consider two kinds of duty cycle: 12% and 3%. In case of 12% duty cycle, EasiND uses $m=95$ and U-Connect uses prime number $p=13$ . In case of 3% duty-cycle, EasiND uses $m=993$ and U-Connect uses prime number $p=47$ . In both cases, we consider 3 channels, that is $N=3$ . Specifically, we set $c_{\text{bss}}=15$ and $c_{\text{css}}\in \{\mathrm{13,15,17}\}$ in our implementations. We also consider the influence of different number of neighbors on evaluation results.

5.3.1. PLP

Figures 9 and 10 show the discovery latency of EasiND and U-Connect-MC under different number of neighbors with duty cycle of 12% and 3%, respectively. Figures 9(a) and 10(a) describe the discovery latency of EasiND under each experiment trial with different number of neighbors, when nodes operate on 12% and 3% duty cycle, respectively, and Figures 9(b) and 10(b) demonstrate the discovery latency of U-Connect-MC. Each data point in Figures 9(c) and 10(c) is the average measurement from 100 individual experiment trials. As shown in Figures 9 and 10, we can see that EasiND can significantly reduce the discovery latency when compared to U-Connect-MC under all experiment conditions. The reduction ranges from 7% to 86% in case of 12% duty cycle and 35% to 73% in case of 3% duty cycle. The average time slots needed to discover one neighbor for EasiND and U-Connect-MC are about 167 and 180, respectively, with duty cycle of 12%. With the number of neighbors increasing, the time slots used by U-Connect-MC to discover all neighbors increases quickly, but the discovery latency required by EasiND increases much more slowly. For example, in case of 12% duty cycle, the average discovery latency for U-Connect-MC increases to 2547 time slots to discover all 11 neighbors, while EasiND only takes about 363 time slots. With the duty cycle decreasing, the discovery latency of both methods under all network conditions increases. The average discovery latency of U-Connect-MC to discover all 11 neighbors with duty cycle of 3% is 8851 time slots, which is much higher than EasiND's 3112 time slots. According to the definition of PLP, we can easily find that the PLP of EasiND is much lower than that of U-Connect-MC under all experiment scenarios. Therefore, when compared to U-Connect-MC, EasiND achieves a much better trade-off between power efficiency and discovery latency.

Figure 9

Discovery latency (number of time slots) under different number of neighbors with duty cycle of 12%.

Figure 10

Discovery latency (number of time slots) under different number of neighbors with duty cycle of 3%.

5.3.2. FD

Figures 11 and 12 show the fraction of discoveries of EasiND and U-Connect-MC under different number of neighbors with duty cycle of 12% and 3%, respectively, including the fraction of discoveries under each experiment trial for both methods in all scenarios as shown in Figures 11(a), 11(b), 12(a), and 12(b). Figures 11(c) and 12(c) show the comparison of average fraction of discoveries measured from 100 independent experiment trials between EasiND and U-Connect-MC. From Figures 11 and 12, we can observe that EasiND can discover more neighbors than U-Connect-MC in a predefined time limitations under all network scenarios. With the number of neighbors increasing, both methods' average fractions of discoveries show an overall decrease trend, but U-Connect-MC is more obvious. For example, U-Connect-MC's average fraction of discoveries decreases to 89.2% from 100% when number of neighbors increase from 1 to 11 in duty cycle of 12%. However, EasiND can discover at least 93.5% neighbors under all network scenarios in duty cycle of 12%. We also observe that both methods achieve better performance in fraction of discoveries when nodes operate on a lower duty cycle. This is because that more collisions would happen due to denser distribution of active time slots when nodes work on a higher duty cycle. Therefore, there is room for further improvement when we take collisions and cooperations between nodes into account, which are left for our future work.

Figure 11

Fraction of discoveries under different number of neighbors with duty cycle of 12%.

Figure 12

Fraction of discoveries under different number of neighbors with duty cycle of 3%.

5.3.3. Implications

We have investigated the impact of duty cycle and number of neighbors on neighbor discovery system performances. Both theoretical analysis and experimental results have shown that EasiND consistently outperforms U-Connect under all network scenarios. Because EasiND generally operates in an asynchronous manner, it still works well with misalignment of time slots and clock drift.

6. Conclusions and Future Work

This paper presents a novel asynchronous neighbor discovery method named EasiND for duty-cycled multichannel mobile WSNs. EasiND essentially builds an asynchronous neighbor discovery system based on cyclic quorum system, which consists of a group of beacon scheduling sequences and channel scanning sequences. EasiND can bound the discovery latency in multichannel communication scenarios and achieves an optimal performance in terms of power-latency product. Both theoretical analysis and test-bed evaluation have shown that EasiND significantly reduces the discovery latency with desired duty cycle by up to 86% and can discover more neighbors in a fixed time limitation when compared to U-Connect. Moreover, EasiND can achieve a better trade-off between power consumption and discovery latency than U-Connect.

As future work, we are pursuing two interesting directions: to (1) extend our study to asymmetric multichannel mobile WSNs and (2) investigate neighbor discovery when considering collisions and cooperations between nodes in multichannel mobile WSNs.