Sage Journals: Discover world-class research

Abstract

During the initial deployment time, wireless sensors continually search their neighbors. The neighbor discovery is not an one-time event because the network topology can be changed anytime due to node mobility and failure. The neighbor discovery protocol helps sensor nodes to find neighboring sensors within their communication range. This study proposes a novel neighbor discovery protocol called the prime-number-assisted block-based neighbor discovery protocol, which intelligently changes the sensor schedules based on the greater common divisor of two sensors’ discovery cycle lengths. For example, for two sensors whose duty cycles are different, if the lengths of their discovery schedules are relatively prime, the prime-number-assisted block-based neighbor discovery protocol simply uses the balanced incomplete block design–based neighbor discovery protocol without adding any additional active slots; otherwise, it changes the original balanced incomplete block design–based schedule using a prime number. In this study, we compare the performances of prime-number-assisted block-based neighbor discovery protocol and other recently proposed neighbor discovery protocols (U-Connect, Disco, SearchLight, and Hedis) using a TOSSIM simulator. The experimental results confirm the superiority of prime-number-assisted block-based neighbor discovery protocol over other neighbor discovery protocols in terms of discovery latency and energy consumptions.

Keywords

Network neighbor discovery protocol wireless sensor network block design protocol

Introduction

In wireless sensor networks (WSNs), sensor nodes are typically battery-powered, and the replacement of the battery may not be practical. So, each sensor turns on and off its radio module in order to reduce the energy consumption. However, a sensor cannot effectively determine when to communicate with its neighbors until it receives neighbor’s radio On/Off schedule. Therefore, a protocol for exchanging sensor’s radio On/Off pattern information is required.

A Neighbor Discovery Protocol (NDP) determines sensor’s sleep/wake schedule that is appropriate for a given duty cycle. By using the sleep/awake schedule, a sensor node determines when to turn its radio module on or off. Another important property of NDPs is that they must guarantee the existence of a specific point of time for any pair of neighboring nodes to be active simultaneously so that they can communicate with each other at this rendezvous moment.

In a symmetrical mode, all sensors operate at the same duty cycle. In contrast, in the asymmetrical duty cycle mode, the duty cycles of two neighbors are considered to be heterogeneous. The applications of WSNs have various traffic and monitoring requirements, and a set of neighboring sensors may operate with different duty cycles. Consequently, the capability of supporting both symmetric and asymmetric duty cycle modes is strongly desired.

The Balanced Incomplete Block Design (BIBD)–based NDP is known as an optimal solution for neighbor discovery in terms of the worst-case discovery latency for a given duty cycle.¹ However, the BIBD-based NDP is only applicable to WSNs with a symmetrical duty cycle mode.

To address the problem of the incompatibility of the BIBD-based NDP in an asymmetrical duty cycle environment, the prime-number-based NDP Prime Block Design (PBD)² adds mandatory wake-up slots when the slot indexes are multiple of the selected prime number. These additional active slots allow two neighboring sensors with different duty cycles to communicate with each other. However, due to the additional wake-up slots, PBD increases the energy consumption.

In this article, we propose a variation of the BIBD-based NDP, called the prime-number-assisted block-based neighbor discovery protocol (PNB-NDP) that supports both the symmetrical and asymmetrical duty cycle modes. The key contributions of this article are as follows. First, we proved that, when the lengths of two BIBD-based discovery schedules used by two neighbors are relatively prime, there always exists overlapping active slots between two sensors without having any additional active slot. Second, when the lengths of two BIBD-based discovery schedules used by two neighbors are not relatively prime, the proposed protocol guarantees the existence of overlapping active slots between any pair of sensors by adding mandatory prime-based wake-up slots to the schedule of only one sensor. Finally, by implementing several representative NDPs as well as PNB in the TOSSIM simulator and Power TOSSIM Module, we conducted a simulation study. The results of our experiments show that the proposed PNB-NDP outperforms other NDPs in terms of energy efficiency and discovery latency.

The article is structured as follows: in the “Related work” section, we summarize the representative NDPs in the literature. The “Background and problem statement” section discusses the relationship between BIBD and discovery schedule, and shows the problems of BIBD in asymmetric WSNs. “The PNB-NDP” section elaborates a new neighbor discovery approach called PNB-NDP. The “Experimental analysis” section presents the results of our experimental study. Finally, the conclusion and future works are discussed in the “Conclusion” section.

Related work

There are many NDPs proposed for sensor networks in the literature. We categorize the representative NDPs in the literature into the following three groups: BIBD-based NDPs, matrix-based NDPs, and prime-number-based NDPs.

In matrix-based NDPs, discovery schedules are derived from an n × n matrix. The early matrix-based NDP³ arbitrarily chooses one column and one row from the n × n matrix, and assigns them to a sensor for discovery schedule. The selected row and column are then replaced by active slots of the sensor nodes. Rest slots are sleep slots. However, because the total length of a discovery schedule in a matrix-based NDP is n × n, the discovery latency of matrix-based NDPs is high. Note that the discovery latency is one of key criteria for NDPs. Furthermore, the original matrix-based NDP cannot support WSNs with an asymmetric operation, in which neighboring sensor nodes may have different duty cycles. To resolve these problems, some variations of the matrix-based NDP such as SearchLight⁴ and Hedis⁵ were introduced. The modified matrix-based methods halve the length of the original matrix-based discovery schedules while supporting both symmetric and asymmetric operations. Owing to the shortened cycle length, SearchLight and Hedis have a shorter discovery latency and lower energy consumption than the original quorum-based NDP.³ However, the discovery latency of SearchLight and Hedis deteriorates as the duty cycle decreases.

Another popular approach to construct a discovery schedule is using prime numbers. We categorize this scheduling construction approach as prime-number-based NDPs in this article. Note that most prime-based NDPs naturally support both symmetric and asymmetric operations because adding active slots at the slot prime indexes always have a rendezvous point (a common active slot) between any two sensors. This property is conferred by the Chinese Remainder Theorem (CRT).⁶ Two popular NDPs based on prime numbers are Disco⁷ and U-Connect.⁸ In Disco, each sensor randomly chooses a prime number to build its discovery schedule. When two neighboring sensors choose distinct prime numbers, there always exist common active slots between two discovery schedules because two selected prime numbers are relatively prime. Unlike Disco, U-Connect uses a single prime number to build discovery schedules. To construct a new discovery schedule, U-Connect adds active slots up to half of the cycle length and adds periodic active slots using a prime number. The main drawback of the prime-based NDPs is the discovery latency. The worst-case discovery latency of prime-based NDPs is the product of two prime numbers. Therefore, if a pair of sensors uses a large prime number for building their discovery schedules, the worst-case discovery latency between these two neighboring sensors would increase significantly.

The last category of NDPs is BIBD-based NDPs that constructs sensor schedules through block designs.¹ Constructing neighbor discovery schedules using block designs was initially introduced for networks with a homogeneous duty cycle (symmetric networks), and it was proved that the BIBD-based approach produces an optimal solution for the neighbor discovery problem in a symmetric network. However, it might be unsuitable for heterogeneous WSN applications due to the lack of supporting asymmetric neighbor discovery operations. To overcome this problem, we proposed several NDPs such as OR-based⁹ and XOR-based¹⁰ NDPs. However, these approaches require a number of additional active slots, which increases the energy consumption during the neighbor discovery phase.

Recently, PBD has been proposed in Lee et al.² However, to support both symmetric and asymmetric configurations, PBD always adds an extra active slot into the original BIBD-based NDP, which again increases the energy consumption. In this article, we propose a novel NDP called the PNB-NDP. Unlike PBD, PNB-NDP removes the need for adding active slots in most scenarios. More precisely, if the length of discovery cycles of potential neighbors is relative prime, PNB-NDP just uses the original BIBD-based schedule without having any additional active slot. This article extends the results of our previous study,¹¹ where we analyzed the relation between PBD and greatest common divisor (GCD) of the lengths of discovery cycles.

Background and problem statement

In this section, we introduce how the BIBD blocks are used for neighbor discovery in WSNs, and analyze the inherent problem of BIBD-based NDPs.

Relation between block designs and discovery schedules

Block designs are combinatorial structures inherent in many mathematical contexts and used in various fields such as experimental design, finite geometry, software testing, cryptography, and algebraic geometry.¹² Among the block designs, the BIBDs are most suitable for NDP due to their structure properties shown below.

Next, we give two definitions of combinatorial block designs, then define the relation between block design and sensor schedule. Definition 1 specifies the basic properties of a (X, A) design.

Definition 1: A design is a pair (X, A) satisfying the following properties:

X is a set of elements, called points, and

A is a collection (i.e. multiset) of nonempty subsets of X, called blocks.

BIBD is a well-studied block design for WSNs. BIBD is defined as follows.

Definition 2: Let $v$ , $k$ , and $λ$ be positive integers such that $v > k ⩾ 2$ . A $(v, k, λ)$ -BIBD is a design (X, A) that satisfies the following properties:

|X| = v.

Each block contains exactly k points.

Every pair of distinct points is contained in exactly λ blocks.

For instance, suppose that the set X is {1,2,3,4,5,6,7} and the multiset A consists of {{1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {1,5,6}, {2, 6, 7}, {1,3,7}}. Clearly, the design (X, A) satisfies the three properties listed in Definition 2. In particular, (X, A) is a (7,3,1)-BIBD. Note that a (7,3,1)-BIBD is not unique. For example, the multiset $A'$ = {{1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6}}; the (X, $A'$ ) also satisfies the three properties specified in Definition 2 . Thus, (X, $A'$ ) is also a (7,3,1)-BIBD.

In the BIBD theory, the BIBD is symmetric if the number of blocks equals to the cardinality of the universal set. It was proven that there exists a $(h^{2} + h + 1, h + 1, 1)$ -BIBD, where h denotes the power of the prime.¹² This study focuses on this type of BIBD. The symmetry of $(h^{2} + h + 1, h + 1, 1)$ -BIBD is easily checked. For convenience, we let $v = h^{2} + h + 1$ , $k = h + 1$ , and $λ = 1$ . Here, every block in BIBD contains $k$ points (elements).

Sensor nodes can be either active or sleep. During the neighbor discovery phase, they continually switch between active and sleep modes. In this article, we use a binary string to represent a neighbor discovery schedule. The binary number “1” corresponds to the active slot where a sensor turns its radio on, and “0” represents the sleep slots where the radio is off. The sensor schedules are represented by sequences of binary numbers as shown in Definition 3.

Definition 3: Define the universal set X as ${1, 2, \dots, v}$ , and let a block be a nonempty subset of $X$ . A block-A-based schedule of a node $u$ is defined as a binary sequence $S_{u}^{v} = {〈 a_{i} 〉}_{i = 1}^{v}$ such that $a_{i} = 1 if i \in A (\mod v)$ $and 0 otherwise$ .

For example, suppose that block A in the sensor schedule is {1,2,4}. If a sensor node uses block A for scheduling, it wakes up to exchange data packets at the beginning of slots indexed 1, 2, or 4 (see Figure 1). The number of active slots over the entire cycle length (expressed as a percentage) is called the duty cycle of the schedule. If a block-A-based schedule $S_{u}^{v}$ of a sensor node $u$ is $S_{u}^{v} = 〈 a_{1}, a_{2}, \dots, a_{v} 〉$ , then the duty cycle is given by $DC = \frac{\sum_{i = 1}^{v} a_{i}}{| X |} \times 100 %$ , where the base block A is a nonempty subset of the universal set. For example, the duty cycle of the schedule shown in Figure 1 is 3/7 × 100 = 43%.

Figure 1.

An example of a schedule using block design.

Unless the crystal clocks in a WSN are fully synchronized, each sensor turns on the radio module at different times. That is, in an asynchronous WSN, there is some skew of the clocks in the network, and the beginnings of each discovery cycle are not perfectly aligned. For example, if the block-A-based schedule of a sensor node $u$ starts at an arbitrary slot $d > 0$ (called the $d$ clock drift), the schedule sequence is given by $S_{u}^{v} = {〈 a_{i + d} 〉}_{i = 1}^{v}$ , where $a_{i} = 1 if i - d \in A and a_{i} = 0$ and $otherwise$ . Because of message collisions, channel interference, and impulsive noise, a pair of neighboring sensors may not be able to discover each other during their overlapped active slots. Therefore, the sequence $S_{u}^{v}$ satisfies $a_{i + nv} = a_{i}$ for all i in $[1, v] n$ and $n \in Z^{+}$ . Note that a sensor must repeat its discovery schedule at multiple times during the discovery phase or the entire operation period.

During the discovery phase, sensor nodes independently find neighboring sensors using the discovery schedule $S_{u}^{v}$ . Their cycle lengths are up to their assigned duty cycle, which may or may not be equal. If the duty cycles differ among the neighboring nodes, the two neighbors may not have any common active slot within their discovery cycle. The nodes will repeatedly switch the radio module on and off until the end of the discovery phase. The sensor nodes will find each other if there exist common active slots within the least common multiple (LCM) of their cycle length. Otherwise, they will not discover each other during the operation time. The location of common active slots between sensor nodes can be obtained using a notation ⊗. The operation ⊗ between two discovery schedules $S_{u_{1}}^{v_{1}} and S_{u_{2}}^{v_{2}}$ represents the sequence $S_{u_{1}}^{v_{1}} \otimes S_{u_{2}}^{v_{2}} = {〈 a_{i} \times b_{i} 〉}_{i = 1}^{L}$ , where $a_{i}$ and $b_{i}$ are members of $S_{u_{1}}^{v_{1}}$ and $S_{u_{2}}^{v_{2}}$ , respectively, and $L = LCM (v_{1}, v_{2})$ . Thus, $\sum_{i = 1}^{L} a_{i} b_{i}$ denotes the number of common active slots between $S_{u_{1}}^{v_{1}}$ and $S_{u_{2}}^{v_{2}}$ within the cycle length L.

Problem of BIBD-based scheduling

The BIBD-based NDP protocol provides an optimal solution for a sensor network with asymmetric duty operations.⁸ For example, we assume a sensor network environment in which sensors do not know neighbor’s discovery schedules. In other words, sensor nodes $u_{1}$ and $u_{2}$ may have different duty cycles at the network initial time. They do not aware of the existence of neighbors at the beginning of the discovery phase. Consider two sensor nodes $u_{1}$ and $u_{2}$ with different duty cycles. Note that there is no common active slot between them, as shown in Figure 2. Sensor node $u_{1}$ uses the {1,2,4} block in the (7,3,1)-BIBD, that is, $S_{u_{1}}^{7}$ = $〈 1, 1, 0, 1, 0, 0, 0 〉$ , and $u_{2}$ uses the {3,6,7,12,14} block in the (21,5,1)-BIBD, that is, $S_{u_{2}}^{21} = 〈 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0 〉$ . Clearly, $S_{u_{1}}^{7} \otimes S_{u_{2}}^{21}$ $= \sum_{i = 1}^{21} a_{i} b_{i} = 0$ . As LCM(7,21) = 21, this pattern repeats indefinitely. Therefore, there is no common active slot between $S_{u_{1}}^{7}$ and $S_{u_{2}}^{21}$ , and nodes $u_{1}$ and $u_{2}$ will never discover each other.

Figure 2.

Problem of symmetric BIBD.

As shown in the previous example, a discovery scheduling algorithm based on a symmetric BIBD does not always guarantee the existence of a common active slot in an asymmetric WSN. Thus, in the next section, we propose a new protocol that solves the asymmetric problem of the BIBD-based NDP.

The PNB-NDP

This section elaborates the proposed NDP for asymmetric WSNs, called PNB-NDP, that intelligently decides when to add an additional active slot. The proposed NDP first builds a discovery schedule using the BIBD-NDP for a given duty cycle. Then, it compares the lengths of two discovery schedules with two given duty cycles to determine the need of additional active slots.

Let L₁ and L₂ be the lengths of a discovery schedule S₁ and S₂, respectively. If the GCD of S₁ and S₂ is 1, that is, GCD(S₁, S₂) = 1, the original BIBD discovery schedule has a common active slot between S₁ and S₂ (see Lemma 1). In other words, if GCD of the lengths of the discovery cycles is 1, the PNB-NDP does not add any active slot on top of the BIBD schedules. However, if GCD(S₁, S₂) is not 1, S₁ and S₂ may not have any common active slot (as shown in Figure 2), and PNB-NDP adds additional active slots to the original BIBD schedule.

Lemma 1: Let two symmetric BIBDs $(X, A)$ and $(Y, B)$ be $(v_{1}, k_{1,} λ_{1})$ and $(v_{2}, k_{2,} λ_{2})$ respectively, where $GCD (v_{1}, v_{2}) = 1$ . Let the schedule of $u_{1}$ with a base block $A_{u_{1}}$ in $A$ be $S_{u_{1}}^{v_{1}} = {〈 a_{i} 〉}_{i = 1}^{v_{1}}$ and that of $u_{2}$ with a base block $B_{u_{2}}$ in $B$ be $S_{u_{2}}^{v_{2}} {〈 b_{j} 〉}_{j = 1}^{v_{2}}$ . Now consider two sensor nodes indexed by i where $i \in {1, 2}$ . If the schedules of $u_{i}$ are $S_{u_{i}}^{v_{i}}$ , and the nodes start at arbitrary slots indexed by $d_{i}$ , they have at least $k_{1} k_{2}$ common active slots, that is, $\sum_{i = d}^{L + d} a_{i} b_{i} = k_{1} k_{2}$ , where $d = max {d_{1}, d_{2}}$ .

Proof: We first consider a case in which two sensor nodes have zero clock drift, that is, $d_{1} = d_{2} = 0$ . The sensor nodes u₁ and u₂ are active in the ith slot iff (i modulo $v_{1}$ ) ∈ $A_{u_{1}}$ and (i modulo $v_{2}$ ) ∈ $B_{u_{2}}$ , respectively. Since $GCD (v_{1}, v_{2}) = 1$ , by applying CRT, we solve the following congruence equations for $1 ⩽ s ⩽ k_{1}$ and $1 ⩽ t ⩽ k_{2}$

\begin{matrix} x \equiv i_{s} (\mod v_{1}) and \\ x \equiv j_{t} (\mod v_{2}) \end{matrix}

(1)

Let the solution of the above congruence equations be $x_{st}$ . The common elements in $S_{u_{1}}^{v_{1}}$ and $S_{u_{2}}^{v_{2}}$ have the same $k_{1} k_{2}$ values and $a_{x_{st}} = b_{x_{st}} = 1$ .

Next, we consider that sensor nodes $u_{i 1} and u_{i 2}$ experience nonzero clock drifts $d_{1}$ and $d_{2}$ , respectively. Sensor node $u_{1}$ is active at the slot index $i_{s}$ , if $i_{s} - d_{1} \in A_{u_{1}}$ (where $1 ⩽ s ⩽ k_{1}$ ), and node $u_{2}$ stays awake at the slot index $i_{t}$ , if $i_{t} - d_{2} \in B_{u_{2}}$ (where $1 ⩽ t ⩽ k_{2}$ ). Therefore, applying CRT, we have

\begin{matrix} x \equiv i_{s} (\mod v_{1}) and \\ x \equiv i_{t} (\mod v_{2}) \end{matrix}

(2)

where $1 ⩽ s ⩽ k_{1}$ and $1 ⩽ t ⩽ k_{2}$ .

Thus, there exist common elements in $S_{u_{1}}^{v_{1}}$ and $S_{u_{2}}^{v_{2}}$ , and the number of common elements is $k_{1} k_{2}$ and $a_{x_{st}} = b_{x_{st}} = 1$ . Consequently, we can always obtain $\sum_{i = d}^{L + d} {a_{i} b}_{i} = k_{1} k_{2}$ .

As shown in Figure 2, if $GCD (v_{1}, v_{2}) \neq 1$ , the existence of common active slots between the schedules of the two sensor nodes cannot be guaranteed. To resolve this issue, we introduce the extended block and the extended block-based schedule. Assuming that the cardinality of the universal set X is not prime, |X| = $v$ is not prime. We then choose a prime number satisfying $p = \min {| v - p | : p \in P, p ⩽ v}$ , where $P$ is the set of prime numbers. The extended block will be the union of a block of the design $(v, k, λ)$ -BIBD and the selected prime p, that is, $\bar{A} = {a_{1}, a_{2}, \dots, a_{k}} \cup {p}$ . The extended block-based schedule $S_{u}^{vp}$ is defined as $S_{u}^{vp} = {〈 a_{i} 〉}_{i = 1}^{vp}$ , where $a_{i} = 1 if i \in \bar{A}$ . Otherwise, $a_{i} = 0$ .

Before considering the case where $GCD (v_{1}, v_{2}) \neq 1$ , we introduce Oppermann’s conjecture¹³ in Lemma 2, which plays an important role in our study. Due to the space limitation, we do not include the proof of Lemma 2.

Lemma 2: For any integer $n > 1$ , there exists at least one prime number between $n^{2} - n$ and $n^{2}$ and at least one other prime number between $n^{2}$ and $n^{2} + n$ .

The theorem below states that when the GCD of the cycle lengths of any pair of schedules is not 1, the block-based schedule $S_{u_{1}}^{v_{1}}$ and the extended block-based schedule $S_{u_{2}}^{v_{2} p_{2}}$ have at least $k_{1}$ common active slots.

Theorem 1: Let two symmetric BIBDs $(X, A)$ and $(Y, B)$ be $(v_{1}, k_{1,} λ_{1})$ and $(v_{2}, k_{2,} λ_{2})$ respectively, where $GCD (v_{1}, v_{2}) \neq 1$ . Let sequences $S_{u_{1}}^{v_{1}}$ and $S_{u_{2}}^{v_{2} p_{2}}$ are assigned for sensor nodes $u_{1}$ and $u_{2},$ respectively, with arbitrary starting delays $d_{1}$ (for $u_{1}$ ) and $d_{2}$ (for $u_{2}$ ). Then, $\sum_{i = 1}^{L} a_{i} b_{i} ⩾ k_{1}$ , where $L = LCM (v_{1}, v_{1} p_{2})$ .

Proof: Assume $v_{1}$ ≠ $v_{2}$ and 0 < $v_{1}$ < $v_{2}$ . As $v_{1} = h_{1}^{2} + h_{1} + 1$ and $v_{2} = h_{2}^{2} + h_{2} + 1$ , we can assume that $h_{1} < h_{2}$ , and hence that $h_{1} + 1 ⩽ h_{2}$ . Thus we know that $h_{1}^{2} + h_{1} + 1 < {(h_{1} + 1)}^{2} = h_{1}^{2} + 2 h_{1} + 1 ⩽ h_{2}^{2} a n d v_{1} < h_{2}^{2}$ . Let us choose a prime number $p_{2}$ such that $p_{2} = min {| v_{2} - p | : p \in P, p ⩽ v_{2}}$ , where $P$ is the set of all prime numbers. By Oppermann’s conjecture, $p_{2}$ exceeds $v_{1}$ . As $p_{2}$ is also prime, it has no factor of $v_{1}$ and $GCD (v_{1}, p_{2}) = 1$ .

The schedule of $u_{1}$ is the sequence $S_{u_{1}}^{v_{1}} = 〈 a_{i} 〉$ such that $a_{i} = 1$ if $i \in A_{u_{1}}$ . Otherwise, $a_{i} = 0$ . Similarly, the schedule of $u_{2}$ is the sequence $S_{u_{2}}^{v_{2} p_{2}} = 〈 b_{i} 〉$ such that $b_{i} = 1$ if $i \in A_{2}$ or $i \equiv 0$ (mod $p_{2}$ ). Otherwise, $b_{i} = 0$ .

If both schedules have zero clock drift (i.e. $d_{1} = d_{2} = 0$ ), we clearly have $\sum_{i = 1}^{L} a_{i} b_{i} ⩾ k_{1} .$ When the clock drifts are nonzero, sensor node $u_{1}$ is active at the slot indexes $i_{s} - d_{1} \in A_{u_{1}}$ (where $1 ⩽ s ⩽ k_{1}$ ), and sensor node $u_{2}$ stays awake at the slot indexes $i_{t} - d_{2} \in B_{u_{2}}$ (where $1 ⩽ t ⩽ k_{2}$ and also wake up at $p_{2} - d_{2}$ ) (see proof of Lemma 1). Thus, we know that $u_{1}$ awakens at the slot indexes $i_{1}, i_{2}, \dots, i_{k_{1}}$ (modulo $v_{1}$ ) and $u_{2}$ awakens at the slot indexes $j_{1}, j_{2}, \dots, j_{k_{2}}$ (modulo $v_{2}$ ) and $p_{2} + d_{2}$ (modulo $p_{2}$ ). By applying CRT, for $1 ⩽ s ⩽ k_{1}$ , we obtain

\begin{matrix} x \equiv i_{s} (\mod v_{1}) and \\ x \equiv d_{2} (\mod p_{2}) \end{matrix}

(3)

By CRT, two schedules $S_{u_{1}}^{v_{1}}$ and $S_{u_{2}}^{v_{2} p_{2}}$ have at least $k_{1}$ common active slots within every $v_{1} \times p_{2}$ slot.

Let us give an example of the location of the additional slots for the case in Figure 2. Note that the block $A_{1} = {1, 2, 4}$ is selected from the (7,3,1)-BIBD, and the block $A_{2} = {3, 6, 7, 12, 14}$ is selected from the (21,5,1)-BIBD. Since GCD(7,21) = 7, PDB-NDP adds extra active slots. Since the greatest prime number below 21 is 19, the extended block is $\bar{A_{2}} = {3, 6, 7, 12, 14} \cup {19}$ . Thus, the schedule of $u_{2}$ is $S_{u_{2}}^{21 \times 19}$ . By CRT, the two sensor nodes have common active slots at indexes 57, 95, and 114 (see Figure 3).

Figure 3.

Common active slot of prime-number-assisted block-based NDP.

The cycle length of PNB-NDP depends on whether the sensor nodes are supported by a prime number. Assume the discovery cycles of two neighboring sensors are derived from two symmetric BIBDs $(v_{1}, k_{1,} λ_{1})$ and $(v_{2}, k_{2,} λ_{2})$ . If $GCD (v_{1}, v_{2}) = 1$ , the cycle length boundary between the sensor nodes is $v_{1} \times v_{2}$ . If $GCD (v_{1}, v_{2}) \neq 1$ , the cycle length boundary is $v_{1} \times (v_{2} \times p_{2})$ . In fact, applying the number of common active slots reduces the worst-case latency. That is, the latency is shorter than the product of the cycle lengths of the different sensors. For example, if $GCD (v_{1}, v_{2}) = 1$ , then $v_{1} \times v_{2} - [k_{1} \times v_{2} + v_{1} \times k_{2}] = h_{1}^{2} \times h_{2}^{2} - (h_{1} + 1) (h_{2} + 1) = h_{1}^{2} \times h_{2}^{2} - k_{1} \times k_{2} < h_{1}^{2} \times h_{2}^{2} - h_{1} \times h_{2} = h_{1} h_{2} (h_{1} h_{2} - 1)$ . If $GCD (v_{1}, v_{2}) \neq 1$ , the latency length is $v_{1} \times p_{2} - k_{1} \times p_{2} = h_{1}^{2} \times p_{2}$ .

In terms of the worst-case scenarios, $PNB$ -NDP outperforms the existing representative NDPs because its operation is based on symmetric BIBDs. Moreover, because it guarantees only one common active slot between the sensor nodes within one cycle, it yields favorable active ratios. Table 1 compares the performances of PNB-NDP, U-Connect, Disco, SearchLight, and Hedis in terms of active ratio, worst-case latency, and normalized value. In this table, the performances of PNB-NDP are normalized to 1. Particularly, the energy consumption of PNB-NDP equals that of BIBD because, for the most cases where the GCD of two cycle lengths is 1, no new active slot will be added.

Table 1.

Active ratio and worst-case latency of each NDP.

Protocol	Active ratio	Normalized	Worst-case latency
U-Connect⁸	$\frac{3 p + 1}{2 p^{2}} ≅ \frac{1.5 \sqrt{L}}{L}$	1.5	$p_{1} p_{2}$
Disco⁷	$\frac{p_{1} + p_{2}}{p_{1} \cdot p_{2}} ≅ \frac{2 \sqrt{L}}{L}$	2	$\min {\begin{matrix} p_{1} p_{3}, p_{1} p_{4} \\ p_{2} p_{3}, p_{2} p_{4} \end{matrix}}$
SearchLight⁴	$\frac{2}{st} ≅ \frac{2 \sqrt{L}}{L}$	2	$s t^{2}$
Hedis⁵	$\frac{2 m - 2}{m^{2} - m} ≅ \frac{2 \sqrt{L}}{L}$	2	$m^{2}$
PNB-NDP	$\frac{(h_{i} + 1) + α}{(h_{i}^{2} + h_{i} + 1)} ≅ \frac{\sqrt{L}}{L}$	1	$h_{j}^{2}$

PNB-NDP: prime-number-assisted block-based neighbor discovery protocol.

Experimental analysis

This section compares the proposed NDP with recent NDPs (U-Connect, Disco, SearchLight, and Hedis) in an experimental environment. For this purpose, the following experimental matrices are constructed:

Worst-case discovery latency: the amount of time required for all sensor nodes to find their neighboring sensors.

Number of active slots: the total number of active slots until the end of the discovery phase while node operating in an asymmetric environment.

Energy consumption: total energy consumption during the discovery phase.

TOSSIM¹⁴ and NS-2¹⁵ are widely used simulation platforms for WSN studies. The key difference between NS-2 and TOSSIM is that NS-2 mainly deals with packet-level network simulation, whereas TOSSIM covers bit-level TinyOS sensor network environment. Our simulation study was conducted using TOSSIM rather than NS-2. This is because TOSSIM simulates not only the network but also the execution of each node—the distributed nature of sensor networks.¹⁶ For the performance comparison, we implemented the proposed PNB-NDP scheme, two prime-number-based NDPs (U-Connect and Disco), and two matrix-based NDPs (SearchLight and Hedis) in TOSSIM.¹⁴ To measure the energy consumption during the discovery phase, we integrated the Power TOSSIM Module¹⁷ into the TOSSIM simulator. For radio communications, we assumed that the sensor nodes were equipped with the CC2420 radio module.¹⁸ The channel access scheme was based on CSMA/CA.^19,20 For the network topology, we randomly deployed 50 sensor nodes within a 100 m × 100 m field. The duration of a discovery slot was set to 15 ms, and each sensor toggled its radio module on and off over the duration of each slot based on the assigned discovery schedule.

For representative duty cycles (1%, 2%, 5%, and 10%), we obtained suitable parameters for each NDP. The active and cycle lengths and parameters of each NDP are listed in Tables 2 and 3, respectively.

Table 2.

Active and cycle length comparison of each NDP.

Protocol	Parameter	Active slots	Cycle length
U-Connect	$p^{2}$	$\frac{3 p - 1}{2}$	$p^{2}$
Disco	$p_{1} p_{2}$	$p_{1} + p_{2}$	$\min {\begin{matrix} p_{1} p_{3}, p_{1} p_{4} \\ p_{2} p_{3}, p_{2} p_{4} \end{matrix}}$
SearchLight	st	st	$s t^{2}$
Hedis	m	2m – 2	$m^{2}$
PNB-NDP	$h$	$h + 1 + α$	$h^{2} + h + 1$

PNB-NDP: prime-number-assisted block-based neighbor discovery protocol.

Table 3.

Parameters of NDP.

Protocol	1%	2%	5%	10%
U-Connect	p = 149	p = 73	p = 29	p = 13
Disco	$p_{1} = 197$ $p_{2} = 199$	$p_{1} = 93$ $p_{2} = 103$	$p_{1} = 37$ $p_{2} = 43$	$p_{1} = 17$ $p_{2} = 23$
SearchLight	st = 200	st = 100	st = 40	st = 20
Hedis	m = 200	m = 100	m = 60	m = 20
PNB-NDP	$h = 97$ (9507,98,1)Symmetric BIBD	$h = 49$ (2451,50,1)Symmetric BIBD	$h = 19$ (381,20,1)Symmetric BIBD	$h = 9$ (91,10,1)Symmetric BIBD

PNB-NDP: prime-number-assisted block-based neighbor discovery protocol; BIBD: balanced incomplete block design.

To evaluate the impact of duty cycles on the discovery latency during asymmetric operations, we considered six duty cycle pairs: (10%, 5%), (10%, 2%), (10%, 1%), (5%, 2%), (5%, 1%), and (2%, 1%).

Figure 4 shows the worst-case discovery latencies of U-Connect, Disco, SearchLight, Hedis, and PNB-NDP. In this figure, the x-axis denotes the selected pairs of high-duty cycles and low-duty cycles in an asymmetric environment. The y-axis represents the worst-case discovery latency in 10⁶ s. Obviously, the discovery latency gets longer as the duty cycle decreases. Note that PNB-NDP outperformed U-Connect, Disco, SearchLight, and Hedis in all six duty cycle pairs. The performance differences among NDPs in a high-duty asymmetric scenario such as (10%, 5%) are not significant. However, as the duty cycle decreases, the performance gaps between PNB-NDP and other NPDs increase significantly. The superior performance of PNB-NDP is inherited from BIBDs, which offer the optimal solution for symmetric duty cases. Since PNB-NDP added only one slot on top of the original BIBD-based discovery cycle, the overhead introduced by PNB-NDP is minimal, and the performance of PNB-NDP is much better than other NDPs. Therefore, although PNB-NDP’s theoretical worst-case discovery latency gets considerably longer in an asymmetric environment (as shown in Figure 3), PNB-NDP still offers an efficient solution for neighbor discovery in asymmetric WSNs without compromising the discovery latency.

Figure 4.

Worst-case discovery latency of the NDPs at asymmetric WSNs.

For the worst-case discovery latency, we consider the maximum distance between two common active slots. In PNB-NDP, the existence of the common active slots between two sensors is guaranteed as shown in Theorem 1. Furthermore, the PNB-NDP structure of the sensor schedule uses the BIBD-based NDP, which minimizes the number of active slots for a given duty cycle. By intelligently adding up to one active slot within a cycle, PNB-NDP produces highly efficient discovery schedules for asymmetric WSNs. In contrast, during the discovery phase, U-Connect uses a larger number of total active slots than other algorithms to detect neighboring sensor nodes. This is because U-Connect picks a very large prime number to build a discovery schedule for a given duty cycle, and, as a result of that, the length of the worst-case discovery latency gets extremely large. Like U-Connect, Disco also constructs sensor schedules based on two different prime numbers. Thus, Disco needs lots of total active slots during the entire discovery phase.

Figure 5 shows the energy consumptions of the sensor nodes during the discovery phase measured by PowerTOSSIM.¹⁷ The y-axis of this graph represents the consumed energy in millijoules (mJ) for a sensor network with asymmetric duty operations. The energy consumption of U-Connect is highest because half of the cycle length is dedicated to active slots at the beginning of the discovery phase. The performances of SearchLight and Hedis are similar because both use the half of the NDP matrix for active slots.

Figure 5.

Average energy consumption for asymmetric duty operations.

The energy performance of Disco is poor because this scheme constructs discovery schedules using two different prime numbers, and it increases the total discovery cycle length significantly (recall that the cycle length in Disco is the product of two prime numbers). Note that the worst-case discovery latency is proportional to the length of the discovery cycle. Overall, PNB-NDP outperformed both matrix-based and prime-number-based NDPs by virtue of the efficiency of the BIBD-based NDP operations.

Conclusion

This study proposes a novel NDP called PNB-NDP, which uses symmetric BIBDs for neighbor discovery in both symmetric and asymmetric WSNs. The proposed approach intelligently determines whether to add an active slot or not based on the lengths of two BIBD schedules, and the overhead for supporting asymmetric WSNs is insignificant.

Owing to the optimality of the BIBD-based schedules and the smart insertion of additional active slots, PNB-NDP outperforms existing NDPs (such as U-Connect, Disco, SearchLight, and Hedis) for asymmetric WSNs. In our simulation study, the performances of the various NDPs are compared using the TOSSIM simulator. According to the results of the simulation study, the discovery latency and energy consumption of PNB-NDP are substantially lower than those of other NDPs.

For the future work, we plan to combine the proposed algorithm with recent advanced technologies such as artificial intelligence (AI). For example, the selection of efficient blocks from the list of existing block designs¹² for NDP is not straightforward. Therefore, using AI techniques, we would be able to recommend a set of near-optimal block designs that can be used for neighbor discovery with a given set of configuration parameters.

Footnotes

Handling Editor: Salvatore Serrano

Authors’ note

Woosik Lee is now affiliated with Research Center, Social Security Information Service, Seoul, Republic of Korea.

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: This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2018R1D1A1B07048675).

ORCID iDs

Woosik Lee

Teukseob Song

References

Zheng

Hou

Sha

Optimal block design for asynchronous wake-up schedules and its applications in multihop wireless networks. IEEE T Mobile Comput 2006; 5(9): 1228–1241.

Lee

Youn

Song

et al . Prime block design for asynchronous wake-up schedules in wireless sensor networks. IEEE Commun Lett 2006; 20(7): 1437–1440.

Jiang

Tseng

Hsu

et al . Quorum-based asynchronous power-saving protocols for IEEE 802.11 ad hoc networks. Mob Netw Appl 2005; 10: 169–181.

Bakht

Trower

Kravets

RH.

Searchlight: won’t you be my neighbor? In:

Proceedings of 18th annual international conference on mobile computing and networking (MobiCom ’12), Istanbul, 22–26 August 2012, pp.185–196. New York: ACM.

Chen

Fan

Bian

et al . On heterogeneous neighbor discovery in wireless sensor networks. In: Proceedings of IEEE international conference on computer communications (INFOCOM), Kowloon, Hong Kong, 26 April–1 May 2015, pp.693–701. New York: IEEE.

Ding

Pei

Salomaa

Chinese Remainder Theorem: applications in computing, coding, cryptography. Singapore: World Scientific Publishing, 1996.

Dutta

Culler

. Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications. In: Proceedings of 6th ACM conference on embedded network sensor systems, Raleigh, NC, 5–7 November 2008, pp.71–84. New York: ACM.

Kandhalu

Lakshmanan

Rajkumar

U-connect: a low latency energy-efficient asynchronous neighbor discovery protocol. In: Proceedings of 9th ACM/IEEE international conference on information processing in sensor networks (IPSN ’10), Stockholm, 12–16 April 2010, pp.350–361. New York: ACM.

Lee

Choi

Song

et al . OR-based block combination for asynchronous asymmetric neighbor discovery protocol. Int J Control Autom 2015; 8(3): 45–52.

10.

Lee

Song

Youn

JH.

Asymmetric neighbor discovery protocol for wireless sensor networks using block design. Int J Control Autom 2017; 10(1): 387–396.

11.

Youn

Lee

Song

. Block cycle-length-based asymmetric rendezvous protocol for IoT applications. In: Proceedings of 16th ACM/IEEE international conference on information processing in sensor networks (IPSN ’17), Pittsburgh, PA, 18–21 April 2017, pp.287–288. New York: IEEE.

12.

Anderson

Difference methods. In: Ball

Welsh

(eds) Combinatorial designs and tournaments. Oxford: Oxford University Press, 1997, pp.39–58.

13.

Paz

GA.

On Legendre’s, Brocard’s, Andrica’s, and Oppermann’s conjectures, 2014, https://arxiv.org/pdf/1310.1323.pdf

14.

Levis

Lee

Welsh

et al . TOSSIM: accurate and scalable simulation of entire TinyOS applications. In: Proceedings of 1st international conference on embedded networked sensor systems (SenSys ’03), Los Angeles, CA, 5–7 November 2003, pp.126–137. New York: ACM.

15.

The Network Simulator - ns-2, https://www.isi.edu/nsnam/ns/

16.

Karl

A comparison of the architecture of network simulators NS-2 and TOSSIM. Stuttgart: Institut Für Parallele und Verteilte Systeme, 2005.

17.

Perla

Cathain

Carbajo

et al . PowerTOSSIM z: realistic energy modelling for wireless sensor network environments. In: Proceedings of 3rd ACM workshop on performance monitoring and measurement of heterogeneous wireless and wired networks, Vancouver, BC, Canada, 31 October 2008, pp.35–42. New York: ACM.

18.

Texas Instruments. CC2420 2.4 GHz IEEE 802.15.4 / ZigBee-ready RF transceiver. Dallas, TX: Chipcon Products, Texas Instruments, 2004, pp.1–87.

19.

Oliver

Escudero

. Study of different CSMA/CA IEEE 802.11-based implementations. In: EUNICE contribution, 1999, https://pdfs.semanticscholar.org/0cce/d27aeb40232715586e0bef30c1efa6e90e50.pdf

20.

Philip

Lee

Welsh

et al . TOSSIM: accurate and scalable simulation of entire TinyOS applications. In: First ACM conference on embedded networked sensor systems (SenSys’03), 2003, pp.126–137.

Prime-number-assisted block-based neighbor discovery protocol in wireless sensor networks

Abstract

Keywords

Introduction

Related work

Background and problem statement

Relation between block designs and discovery schedules

Problem of BIBD-based scheduling

The PNB-NDP

Experimental analysis

Conclusion

Footnotes

Authors’ note

Declaration of conflicting interests

Funding

ORCID iDs

References