Sage Journals: Discover world-class research

Abstract

In wireless sensor networks, when sensor nodes are operated with different ratios of active slots, this is called asymmetric duty cycles. Furthermore, cycles with the same ratio of active slots per cycle for all nodes are called symmetric duty cycles. In wireless sensor networks, most applications require both symmetric and asymmetric duty cycles. The balanced incomplete block design–based wake-up schedule is known to be the optimal solution for symmetric duty cycles. However, because this schedule cannot support asymmetric duty cycles, the balanced incomplete block design–based wake-up schedule is not suitable for wireless sensor networks. Herein, we propose a new scheme called the block combination–based asynchronous wake-up schedule to resolve this issue for asymmetric duty cycles. Block combination–based asynchronous wake-up schedule combines different blocks using a block combination operation. The combined schedule guarantees common active slots between sensor nodes in asymmetric duty cycles. To demonstrate the superior performance of block combination–based asynchronous wake-up schedule, we implement a TOSSIM-based simulation and compare the experimental results with recent neighbor discovery protocols such as balanced incomplete block design, prime-based block design, Disco, U-Connect, SearchLight, Hedis, and Todis. We then prove that block combination–based asynchronous wake-up schedule outperforms the others.

Keywords

Wireless sensor network neighbor discovery protocol block design sensor schedule balanced incomplete block design

Introduction

In wireless sensor networks (WSNs), sensor nodes can be deployed anywhere and at any time. If they are deployed within an inaccessible area, it is difficult to manually replace the batteries of the sensor nodes. If the lifetime of the sensor nodes is long and does not require battery replacement for more than a decade, we can reduce the amount of resources and costs required for battery replacement. Thus, extending the lifetime of sensor nodes has become a critical issue in WSNs. There are various studies on extending the lifetime of sensor nodes in WSNs. Among the techniques discussed in these studies, we focus on the neighbor discovery protocol (NDP), which is used when sensor nodes are deployed at network setup.

NDP helps sensor nodes find their neighbors to create a network topology at network initialization. In WSNs, an NDP is not a simple one-time technique, because a sensor can be in and out of communication range at any time. Therefore, how quickly the network topology is configured is directly related to extending the lifetime of the sensor nodes.

In WSNs, sensor nodes are operated with symmetric or asymmetric duty cycles. In an asymmetric duty cycle, all sensors choose their duty cycles independently. This leads to sensor nodes with different ratios of active slots within one length of repetition cycles. In contrast, when sensor nodes pick the same duty cycle, this is called a symmetric duty cycle. Thus, when symmetric duty cycles are used, all sensor nodes have the same ratio of active slots for each cycle. When sensor nodes have the same ratio of active slots within one cycle, they are said to have the same duty cycle. Generally, WSN applications require both symmetric and asymmetric duty cycles because sensor nodes have different goals depending on the intended application. Therefore, the NDP used in a WSN should support both symmetric and asymmetric duty cycles; otherwise, the NDP cannot be used for a wide range of WSN applications.

Balanced incomplete block design (BIBD) is a schedule scheme known for its optimal scheduling of symmetric duty cycles.¹ BIBD constitutes active and sleep slots of particular lengths depending on the duty cycles. The index of the active slots of the periodic cycle time must be fixed because the BIBD scheme lacks a block-generating method. Although there is currently no method for generating new duty cycles, compared to the schedules of other NDPs, the schedule made by BIBD has the shortest total cycle length and active slots. However, BIBD has one critical problem pertaining to the requirements of WSN applications that are operated with different active ratios depending on the application goals: BIBD is incapable of supporting both symmetric and asymmetric duty cycles in a WSN. Thus, BIBD is not widely utilized in WSN applications.

There have been many attempts to solve the lack of support for asymmetric duty cycles in BIBD. For instance, of the recently proposed NDPs, there is prime-based block design (PBD),² which is based on BIBD. Because PBD adds an active slot to one prime number index position every cycle, its energy efficiency is low. Moreover, the discovery latency is increased because the overall cycle length increases. Similarly, the block cycle length-based asymmetric rendezvous protocol (BCLP)³ method was proposed to improve the added active slot to each prime number index position of PBD. However, BCLP also has the disadvantage that the overall discovery latency is not improved because it guarantees common active slots through the intermittent help of the active slot, not by increasing the number of active slots.

Herein, we propose the block combination–based asynchronous wake-up schedule (BC-AWS), which applies the BIBD NDP method using a block chaining technique (which is widely used in the security field). The proposed NDP utilizes the always-meeting attribute of the set of BIBDs existing in one duty cycle to make a valid connection between each block. A meeting ensured by using a pivot slot for connection. A pivot slot is a connection point for connecting each block. It enables asymmetric duty cycles to be handled by the BIBD, which otherwise cannot guarantee the presence of common active slots between sensor nodes in asymmetric duty cycles.

To demonstrate the performance of the proposed BC-AWS, we perform a mathematical analysis according to the number of block chains and the duty cycle of the sensor. In addition, the actual sensor network environment is implemented using the TOSSIM simulator to implement several of the latest NDPs, including BC-AWS, BIBD, U-Connect, Disco, QUORUM, SearchLight, Hedis, Todis, and PBD. The simulator developed for performance comparison is equipped with the PowerTossim module for energy measurement and a time-check module to measure latency.

The composition of this article is as follows. In section “Related work,” we describe the latest NDP based on QUORUM, prime, and block designs and describe block chaining and related research. In section “Background and problem statement,” the basic components of wireless networks are described, a basic definition for the block chain application is provided, and the problems of the existing BIBD approach are examined. Section “BC-AWS” introduces the proposed NDP based on the block chain and analyzes its mathematical proof and performance. Section “Performance evaluation” explains the simulation environment for the experiments and compares the latest NDPs based on energy measurement and discovery latency. Finally, in the last section, the contents of this article are summarized and future research themes are introduced.

Related work

Many researchers have proposed various NDPs for WSNs, including block design-based, QUORUM-based, and prime-based NDPs. These NDPs have different characteristics, such as a small number of active slots, fast discovery time for asymmetric duty cycles, and short total cycle lengths. Among the various proposed NDPs, we can classify the three main protocols as prime number-based, QUORUM-based, and BIBD-based protocols.

In BIBD-based NDPs, the original BIBD schedule scheme uses a mathematical theorem to create a new schedule for the sensor nodes.¹ It is known to be an optimal solution. Thus, this NDP has a shorter total cycle length than other NDPs. The original BIBD NDP has good discovery latency in WSNs owing to this short total cycle length. The block design–based asynchronous neighbor discovery protocol (BAND)⁴ extends the original BIBD NDP to support various duty cycles, addressing the problems of the BIBD block generation method.⁵ Moreover, BAND’s performance is similar to that of the original BIBD. However, the original BIBD and BAND approaches cannot support asymmetric duty cycles. Therefore, to solve this problem, OR-based NDPs combine two different blocks using an OR operator.⁶ The combined block consolidates common active slots with used blocks when combining blocks. However, this is an inferior approach, because an OR-based NDP needs more active slots than other BIBD-based NDPs, such as BIBD and BAND.

In a QUORUM-based NDP, QUORUM uses one column and one row of an $n \times n$ matrix for sensor scheduling.⁷ As a result, a QUORUM-based NDP requires a longer total cycle length than a BIBD-based NDP. Although a QUORUM-based NDP has a long total cycle length, it is preferable for sensor scheduling because it supports both symmetric and asymmetric duty cycles. Hedis⁸ reduced the total length of a QUORUM-based NDP to remove unnecessary energy consumption resulting from a long cycle length. SearchLight⁹ also reduced the total length using a pivot slot on the first column. However, since a QUORUM-based NDP fundamentally uses a matrix to create sensor schedules, it is inefficient in terms of energy consumption.

In a prime-based NDP, DISCO uses two prime numbers for sensor scheduling in a WSN.¹⁰ This guarantees that sensor nodes have at least one common active slot using the Chinese remainder theorem (CRT)¹¹ in both symmetric and asymmetric duty cycles. The CRT is a theorem that finds a value of x that has the same value if the two numbers are relatively prime. It is used in various fields, such as mathematics, security, banks, and networks.

However, DISCO’s total cycle length is longer than those of other NDPs because its total length is $p_{1} \times p_{2}$ . U-Connect¹ reduces the total length of DISCO using only one prime number index position. However, U-Connect requires additional active slots to guarantee the presence of common active slots between sensor nodes in asymmetric duty cycles. Recently, the use of PBD has been proposed. PBD reconciles both BIBD-based and prime-based NDPs. PBD reduces the active slot requirement of U-Connect, but it still needs a long total cycle length, that is, $p \times v$ .

There are other studies based on block design-based, QUORUM-based, and prime-based mechanisms.^12–16

Background and problem statement

In this section, we first define a wake-up schedule function (WSF) using graph elements such as nodes and edges. In particular, when introducing block designs for sensor schedules, elements and blocks are defined to express the wakeup and sleep of sensor nodes in WSNs. This section explains why BIBD cannot handle asymmetric duty cycles.

We represent a WSN using a graph $G (N, UE)$ , where N is the set of sensor nodes and UE is the set of edges. For example, if node $u_{1}$ is within the communication range of sensor node $u_{2}$ , an edge $(u_{1}, u_{2})$ exists in UE. We assume that all edges are bidirectional. The notation $| U E_{u} |$ represents the number of neighbor sensors of u, where $U E_{u} = {(u_{1}, u_{2}) | u_{1} = u or u_{2} = u}$ and $U E_{u} \subset UE$ . For instance, if node u has five neighboring sensors, $| U E_{u} | = 5$ = 5. We assume that a sensor discovers neighbors by exchanging HELLO messages, so long as they wake up at the same slot and there is no collision or wireless error. More precisely, when a sender sends a HELLO message to a recipient within the communication range, the recipient receives it. At this time, the radio modules of the sender and the receiver must remain on the same schedule. If the sender and the receiver normally send HELLO messages to each other, the sensors can say that they have found their neighbors. In this article, we consider a slotted network in which time is divided into slots, and time is assumed to flow in slot units.

Theoretical basis of wakeup design

In this subsection, we introduce combinatorial block design theory in mathematics that plays a key role in our work. Block design theory is applied to various computer science applications. We introduce two definitions for a design and a BIBD.¹⁷

Definition 1

A design is a pair (X, A) such that the following properties are satisfied:

X is a set of elements called points;

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

In the combinatorial block design theory, the elements of the set X are not restricted to integers but can be numbers or literals or symbols. The indexes in the slot indexes are integers, so we consider all elements of the set X to be integers.

Definition 2

Let v, k, and λ be positive integers such that v > k ≥ 2. A (v, k, λ)-Balanced Incomplete Block Design (which we abbreviate as (v, k, λ)-BIBD) is a design (X, A) such that the following properties are satisfied:

|X| = v;

Each block contains exactly k points;

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

We give an example of BIBD. If X = {1, 2, 3, 4, 5, 6, 7} and A = {{1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {5,6,1}, {6,7,2}, {7,1,3}}, the design (X, A) satisfies the three properties listed in Definition 2. Thus, (X, A) is a (7, 3, 1)-BIBD. Note that the collection A is not necessarily unique. For example, another set A′ = {{1,2,3}, {1,2,5}, {2,3,4}, {2,3,7}, {2,4,7}, {4,5,6}, {5,6,7}} also satisfies the properties of Definition 2, and (X, A′) is also a (7, 3, 1)-BIBD.

By the combinatorial block design theory, we cannot guarantee the existence of BIBD for arbitrary combination v, k, and λ. By Theorem 2.1.2 in Stinson,¹⁷ it is proved that if h is the power of a prime number, then there exists $(h^{2} + h + 1, h + 1, 1)$ -BIBD. We denote b as number of blocks. Design (X, B) is a symmetric BIBD if the size of |X| equals the number of blocks, that is, v. For instance, a (7,3,1)-BIBD is a symmetric BIBD and (10,4,2)-BIBD is not a symmetric BIBD. We consider a $(h^{2} + h + 1, h + 1, 1)$ -BIBD where h is the power of a prime number. Because the number of blocks is given by $b = (h^{2} + h + 1) (h + 1) / (h + 1) = h^{2} + h + 1$ , the number of blocks equals size X. We know that if h is the power of a prime number, then the $(h^{2} + h + 1, h + 1, 1)$ -BIBD is a symmetric BIBD. Herein, we assume that v, k, and λ all satisfy the relations $v = h^{2} + h + 1$ , $k = h + 1$ , and $λ = 1$ , where h is the power of a prime number.

In the next section, we define a WSF for WSNs. If sensor nodes use a block design (X, A) for their schedule, they have a single block $(v, k, λ)$ -BIBD. In such a case, if sensor nodes u use a WSF for their schedules, their schedules are represented as a polynomial with the following characteristic functions

f_{u}^{v} (t) = \sum_{i \in A} χ_{E_{i}} (t)

where A is a block of $(v, k, λ)$ -BIBD, $χ_{E_{i}} (t)$ is the characteristic function yielding “1” when $t \in E_{i}$ , and “0” otherwise. For example, if a sensor node u uses a (7,3,1)-BIBD for its schedule, the elements of one block $A = {1, 2, 4}$ , and its WSF is $f_{u}^{7} (t) = χ_{E_{1}} (t) + χ_{E_{2}} (t) + χ_{E_{4}} (t)$ . That is, u wakes up at slot indexes 1, 2, and 4 in each cycle. The WSF $f_{u}^{v} (t + v) = f_{u}^{v} (t)$ is satisfied because a WSF is a periodic function. If the total length of scheduling is v, this means that the indexes of the active interval $E_{i}$ , with a characteristic function 1, are equivalent to mod v. That is, $i \equiv i + v$ . Given the wake-up schedule $f_{u}^{v} (t)$ for node u, $f_{u}^{v} (t - t_{0}) = \sum_{i \in A} χ_{E_{i}} (t - t_{0})$ represents the time shift of the original schedule by $t_{0}$ .

In this case, the total number of active slots for one cycle is calculated by $\int_{0}^{v} f_{u}^{v} (t) dt = \sum_{i \in A} \int_{0}^{v} χ_{E_{i}} (t) dt$ . Similarly, the duty cycle of the sensor node is

DC = \frac{1}{v} \int_{0}^{v} f_{u}^{v} (t) dt

Herein, we use bit-AND operations such as $Λ$ to show the common active slots between sensor nodes. For example, if $f_{u_{1}}^{v} (t) = χ_{E_{1}} (t) + χ_{E_{2}} (t) + χ_{E_{4}} (t)$ and $f_{u_{2}}^{v} (t) = χ_{E_{2}} (t) + χ_{E_{3}} (t) + χ_{E_{5}} (t)$ , the common characteristic function of $f_{u_{1}}^{v} (t)$ and $f_{u_{2}}^{v} (t)$ is $f_{u_{1}}^{v} (t) \land f_{u_{2}}^{v} (t) = χ_{E_{2}} (t)$ . Therefore, if $\int_{0}^{v} [f_{u_{1}}^{v} (t) \land f_{u_{2}}^{v} (t)] \geq 1$ , they have common active slots (Figure 1).

Figure 1.

Common active slot between two different sensor schedules using bit-AND operations.

Problem statement

In this section, we present the limitations of BIBD when used in WSNs. One of the main shortcomings of BIBD-based NDPs is that they cannot support asymmetric duty cycles.¹² In a typical heterogeneous WSN, support for both symmetric and asymmetric discovery scenarios are desirable because the diversity in node properties, such as mobility, energy level, sensing modality, and transmission ranges, result in different traffic demands and duty cycles. An ideal NDP must support both symmetric and asymmetric duty cycles.

We consider sensor nodes $u_{1}$ and $u_{2}$ , which have different schedules $(v_{i}, k_{i}, λ_{i})$ for $i = 1, 2$ , where $v_{i} = h_{i}^{2} + h_{i} + 1$ , $k_{i} = h_{i} + 1$ , and $λ_{i} = 1$ . Let the cycle length of the two sensor nodes $u_{1}$ and $u_{2}$ , respectively, be $v_{1} and v_{2}$ . The cycle lengths are different integers, so we can assume that $v_{1}$ is less than $v_{2}$ . We then have four cases: (1) if $v_{1}$ is not a prime number and $v_{2}$ is a prime number, then $v_{1}$ and $v_{2}$ are relative primes. (2) If $v_{1}$ is a prime number and $v_{2}$ is a prime number, then we certainly know that $v_{1}$ and $v_{2}$ are relative primes. (3) If $v_{1}$ is a prime number and $v_{2}$ is not a prime number, then we cannot guarantee that $v_{1}$ and $v_{2}$ are relative primes. (4) If $v_{1}$ is a not prime number and $v_{2}$ is not a prime number, then we cannot guarantee that $v_{1}$ and $v_{2}$ are relative primes. It is a well-known property that if the cycle lengths of two sensor nodes are relative primes, then the two sensor nodes have common active slots according to CRT.¹¹ Thus, of the above four cases, cases (1) and (2) result in two sensor nodes always having common active slots. However, if $v_{1}$ and $v_{2}$ are not relative primes, as in cases (3) and (4), the two sensor nodes may not have common active slots. Section 4 elaborates on these four cases. Given the above cases, we propose a means of introducing common active slots for cases (3) and (4).

For example, let us consider two sensor nodes $u_{1}$ and $u_{2}$ that have schedules in blocks (1,2,4) and (3,6,7,12,14) in a (7,3,1)-BIBD and (21,5,1)-BIBD, where h is 2 and 4, respectively. As shown in Figure 2, for the selected WSFs $f_{u_{1}}^{7} (x) = χ_{E_{1}} (t) + χ_{E_{2}} (t) + χ_{E_{4}} (t)$ and $f_{u_{2}}^{21} (x) = χ_{E_{3}} (t) + χ_{E_{6}} (t) + χ_{E_{7}} (t) + χ_{E_{12}} (t) + χ_{E_{14}} (t)$ , there is no common active slot within the first 21 slots. Because 7 is a factor of 21, this pattern will be repeated during the sensor operating time. Therefore, there is a chance that two neighboring sensors $u_{1}$ and $u_{2}$ will never discover one another, because there is no common active slot between $f_{u_{1}}^{7} (x)$ and $f_{u_{2}}^{21} (x)$ .

Figure 2.

An example of two asymmetric BIBD-based discovery schedules with no common active slot: $f_{u_{1}}^{7} (x) = χ_{E_{1}} (t) + χ_{E_{2}} (t) + χ_{E_{4}} (t)$ and $f_{u_{2}}^{21} (x) = χ_{E_{3}} (t) + χ_{E_{6}} (t) + χ_{E_{7}} (t) + χ_{E_{12}} (t) + χ_{E_{14}} (t)$ .

Next, we show that there always exist prime numbers $p_{1}$ and $p_{2}$ such that $p_{1} \leq v_{1} and p_{2} \leq v_{2}$ under the condition $v_{1} \neq v_{2}$ . Because $v_{1}$ and $v_{2}$ are two different integers, we can assume that $v_{1} < v_{2}$ with $v_{1} = h_{1}^{2} + h_{1} + 1$ and $v_{2} = h_{2}^{2} + h_{2} + 1$ , where $h_{i}$ is the power of prime numbers for $i = 1, 2$ . Because $v_{1} < v_{2}$ , we know that $h_{1} < h_{2}$ . We can say that $h_{1} + 1 \leq h_{2}$ because $h_{i}$ is an integer for $i = 1, 2$ . We can easily obtain the inequalities $h_{1}^{2} < (h_{1} + 1)^{2} = h_{1}^{2} + 2 h_{1} + 1 \leq h_{2}^{2}$ . Because $h_{i}$ is the power of primes, we know that the following equations hold: $h_{1} \leq h_{1}^{2} < h_{1}^{2} + h_{1} < (h_{1} + 1)^{2} = h_{1}^{2} + 2 h_{1} + 1 \leq h_{2}^{2} < (h_{2} + 1)^{2}$ . According to Legendre’s conjecture,¹⁵ we can say that there exist $p_{1}$ and $p_{2}$ such that $p_{1}$ is less than $v_{1}$ and $p_{2}$ is greater than $v_{1}$ but less than $v_{2}$ . We see that Legendre’s conjecture holds for every n when 1 ≤ n ≤ 11,193,806,023. This indicates that the conjecture holds in $(1, 193, 806, 023)^{2}$ cases. The number of applicable cases exceeds $10^{18}$ . This means that our proposed method can be applied to cycle lengths of approximately $10^{18}$ , which is a sufficiently large cycle length for meaningful WSN applications.

BC-AWS

We now propose our novel BC-AWS. BC-AWS intelligently decides whether to add an active slot, and it supports both symmetric and asymmetric operation by comparing the cycle lengths between the sensor nodes against the greatest common divisor (GCD). For example, if the sensor nodes define their active and sleep slots using the BC-AWS within the given cycle length, they calculate the GCD value. Depending on the GCD, the sensor nodes then decide whether to add an active slot. If the GCD is 1, a common active slot of the co-prime numbers is guaranteed by the CRT. Therefore, the BC-AWS does not add an active slot to the sensor schedules. If the GCD is not 1, the BC-AWS adds one active slot at a prime index. Figure 6 presents the pseudo-code of BC-AWS.

Block generation scheme

In this section, we introduce the process by which we create blocks in a $(v, k, λ)$ -symmetric BIBD. Applying Theorem 2.1.3 in Dutta and Culler,¹⁰ the blocks in a $(v, k, λ)$ -symmetric BIBD can generate the next block by shifting one particular block. Because design (X, B) is a $(v, k, λ)$ -symmetric BIBD, the number of blocks is v. In a $(v, k, λ)$ -symmetric BIBD, v blocks can be expressed as $B = {B_{1}, B_{1}, \dots, B_{v}}$ . We can hence express v blocks as follows

\begin{array}{l} B_{1} = {b_{11}, b_{12}, \dots, b_{1 k}} \mod v \\ B_{2} = {b_{11} + 1, b_{12} + 1, \dots, b_{1 k} + 1} \mod v, \dots \\ B_{v} = {b_{11} + (v - 1), b_{12} + (v - 1), \dots, b_{1 k} + (v - 1)} \mod v \end{array}

Because the set is X = {1, 2, …, v}, without loss of generality, we can choose the first $B_{1}$ that contains 1. This means that the smallest element of $B_{1}$ is $b_{11} = 1$ . In such a case, among the elements of $B_{j}$ such that $1 \leq j \leq v$ , there must exist an element that satisfies $b_{jj} = b_{11} + (j - 1)$ . Because $b_{11} = 1$ , each element resides within $1 < (b_{11} + j - 1) < v$ . This means that blocks $B_{j}$ include elements that are identical to those in index j. Thus, for $1 \leq j \leq v$ , $B_{j}$ contains a point j, and all the blocks are included in a particular element that is identical to an index number called a pivot point.

Figure 3 shows a (21,5,1)-symmetric BIBD where the base block is (1,2,7,9,19). In such a symmetric BIBD, each block in B is generated by shifting just one position. If the shifted elements are greater than 21, we can calculate modulo 21.

Figure 3.

Pivot slots for a (21,5,1)-BIBD.

Block combination operation

We now propose a new block combination operation to combine several blocks, because the proposed method requires diverse blocks to create one schedule. In a $(v, k, λ)$ -symmetric BIBD, because there are v blocks in B, we can write these blocks as $B_{1} = {b_{11}, b_{12}, \dots, b_{1 k}}$ , $B_{2} = {b_{21}, b_{22}, \dots, b_{2 k}}$ , …, $B_{n} = {b_{n 1}, b_{n 2}, \dots, b_{nk}}$ . We choose $m (\leq v)$ blocks in B, that is, $B_{i_{1}}$ , $B_{i_{2}}$ , …, $B_{i_{m}} \in B$ . We define the block combination operation ⊎ as

\begin{array}{l} D = B_{i_{1}} ⊎ B_{i_{2}} ⊎ \dots ⊎ B_{i_{m}} \\ = {b_{i_{1} 1}, b_{i_{1} 2}, \dots, b_{i_{1} k}, b_{i_{2} 1} + v, b_{i_{2} 2} + v, \dots, b_{i_{2} k} + v, \dots, b_{i_{m} 1} + (m - 1) v, b_{i_{m} 2} + (m - 1) v, \dots, b_{i_{m} k} + (m - 1) v} \end{array}

where $1 \leq i_{1}, i_{2}, \dots, i_{m} \leq v$ .

For example, in a (21,5,1)-BIBD, the block combination operation between $B_{1} = {1, 3, 4, 9, 11}$ and $B_{2} = {4, 7, 8, 13, 15}$ is given as $D = B_{1} ⊎ B_{2} = {1, 3, 4, 9, 11, 25, 28, 29, 34, 36}$ (Figure 4).

Figure 4.

Example of block combine operation.

Pivot moving sequence scheme

In the case of a $(v, k, λ)$ -symmetric BIBD, there are several acceptable v blocks. Our proposed scheme only uses some of the available blocks to generate schedules, excluding those where v is not prime, because sensor nodes must guarantee the existence of common active slots according to CRT if v is a prime number.

Because design (X, B) is a $(v, k, λ)$ -symmetric BIBD, B contains the number v such that B = { $B_{1}, B_{2}, \dots, B_{v}$ }. To choose some of the blocks in B, we consider the index sequence in B. The index sequence of blocks can be expressed as $〈 a_{i} 〉$ , such that $a_{i} = i$ for $1 \leq i \leq v$ .

Next, we propose the pivot moving sequence (PMS) to efficiently select blocks for block combination. We can create such a sequence to choose one block for each cycle. Let $X = {0, 1, 2, \dots, v - 1}$ , and let the number of elements of |X| not be a prime number if we choose a prime p = min {| v-p |: p in P} and we let $l = v - p$ . We consider a PMS for the block index sequence $s (n : v, p)$ ; let the first element in the sequence be $a_{1} = p$ . Sequence $s (n : v, p)$ satisfies the following conditions

a_{n + 1} = {\begin{matrix} p & if & n = 0 \\ a_{n} - l & if & n \geq 1 and a_{n} > l (\mod v) \\ a_{n} - 2 l & if & n \geq 1 and a_{n} \leq l (\mod v) \end{matrix}

(1)

For instance, the number of blocks for a (21,5,1)-BIBD is 21. Its index sequence is $〈 a_{i} 〉 = 〈 1, 2, \dots, 21 〉$ , where |X| = 21. Because the greatest prime number less than 21 is 19 and $l = v - p$ , by applying equation (1), we obtain the PMS sequence $s (n : 21, 19) = 〈 19, 17, 15, 13, 11, 9, 7, 5, 3, 1, 18, 16, 14, 12, 10, 8, 6, 4, 2 〉$ . Because sequence $s (n : 21, 19)$ is the index sequence of the block, the blocks chosen from B are $B_{19}, B_{17,} B_{15}, \dots, B_{4}, B_{2}$ . Let D be a set of blocks in which the indices satisfy relation (1). It is clear that set D $D = {B_{a_{1}}, \dots, B_{a_{p}}}$ is a subset of B. Figure 5 shows the example of PMS.

Figure 5.

Distance of the pivots in the $B_{i} and B_{i - l}$ , and $B_{i} and B_{i - 2 l}$ .

Lemma 1

Let the pivot $p v_{i}$ in $B_{i}$ satisfy $p v_{i} > l$ . Then, the distance between the $p v_{i}$ of $B_{i}$ and $p v_{i - l}$ of $B_{i - l}$ in $B_{i} ⊎ B_{i - l}$ is p. (2) Let the pivot in $B_{i}$ satisfy $p v_{i} \leq l$ . Then, the distance between the $p v_{i}$ of $B_{i}$ and the $p v_{i - 2 l}$ of $B_{i - 2 l}$ in $B_{i} ⊎ B_{i - 2 l}$ is $2 \times p$ .

Proof

Because $l = v - p$ , we know that $i - l = i - (v - p)$ . Trivially, we can obtain $i - v + p \equiv i + p (\mod v)$ . Therefore, we know that $B_{i} ⊎ B_{i - l} = B_{i} ⊎ B_{i + p}$ . Thus, the pivot $p v_{i - l}$ in $B_{i - l}$ is given as $p v_{i - l} = p v_{i} + p$ because $p = p v_{i - l} - p v_{i}$ . Thus, we know that distance l is p. (2) Because $p v_{i} \leq l$ and $i \leq l$ , we know that $i + p \leq v$ . In addition, we know that $i + 2 p > v$ . Thus, we arrive at $i + 2 p \in B_{i + 2 p} = B_{i - 2 l}$ . This means that the distance of the pivot is $2 p$ .

Guarantee of a common active slot

If v is not a prime number and p is the greatest prime number less than v, D contains p number blocks, that is, the cardinality of |D| = p. To wake up the nodes at all p slots, we add an element if the block index $a_{n}$ is less than or equal to l. That is, if $a_{k} \leq l$ , then $B_{a_{k}}$ is amended with one more element $a_{k} + p$ . Block $B_{a_{k}}$ is given as $B_{a_{k}} = B_{a_{k}} \cup {a_{k} + p}$ . This means that for blocks in D with block index $a_{n} \leq l$ , we add one more slot index of pivot plus p. In contrast, if v is a prime number, |D| = 1. In other words, the sensor nodes effectively use a $(v, k, λ)$ -symmetric BIBD without modification in this case.

Figure 6 shows the pseudo-code for implementing this process. It first calculates the total length of the received block. It then obtains the value of l, which is the distance between the total length of a block and a chosen prime number. Subsequently, the algorithm compares the current index with l. If the index value is less than l, the algorithm adds one active slot to the $p + index$ . In particular, if the total length is a prime number, the algorithm just uses the original block schedule. If not, the algorithm can continually select the blocks to be combined to generate the schedule using PMS.

Figure 6.

Pseudo code of block combination–based asynchronous wake-up schedule.

When sensor node u has schedule blocks D for a $(v, k, λ)$ -symmetric BIBD, we denote the WSF as follows

f_{u}^{L} (t) = \sum_{i \in D} χ_{E_{i}} (t)

where L is a least common multiple of v and p (i.e. $L = least common multiple (LCM)(v, p)$ ) and p = min {|v – p|: p∈P}.

The following theorem shows that if any two sensor nodes $u_{1}$ and $u_{2}$ have schedules $f_{u_{1}}^{L_{1}}$ and $f_{u_{2}}^{L_{2}}$ with schedule blocks D₁ and D₂, respectively, then the two nodes have a common active slot.

Theorem 1

Let the WSFs of $u_{1}$ and $u_{2}$ be $f_{u_{1}}^{L_{1}} (t - t_{1})$ and $f_{u_{2}}^{L_{2}} (t - t_{2})$ , respectively. Let $v_{1} \neq v_{2}$ , $v_{1}, v_{2} \notin P$ , and let D₁ be the joint block of B₁ and D₂ be the joint block of B₂. Then, $\int_{0}^{T} [f_{u_{1}}^{L_{1}} (t - t_{1}) \land f_{u_{2}}^{L_{2}} (t - t_{2})] \geq 1$ , where $T = (v_{1} \cdot p_{1}) \times (v_{2} \cdot p_{2})$ .

Proof

From Lemma 1, we know that the distance of every pivot is p. We already assume that $v_{1}$ and $v_{2}$ are not prime numbers. Because $v_{1}$ and $v_{2}$ are different numbers, without loss of generality, we can assume that $v_{1} < v_{2}$ . Because we choose the prime numbers $p_{i} = min {| v_{i} - p | : p \in P}$ for i = 1,2, we know that $p_{1} < p_{2}$ . Because $p_{1}$ and $p_{2}$ are different prime numbers, their GCD $(p_{1}, p_{2}) = 1$ . According to CRT, there exists a positive integer that satisfies the following congruence equations

x \equiv t_{1} (\mod p_{1})

x \equiv t_{2} (\mod p_{2})

This means that $u_{1}$ and $u_{2}$ have the same characteristic function $χ_{E_{w}} (t)$ , where $w \in {x_{0}, x_{0} + p_{1} p_{2}, x_{0} + 2 p_{1} p_{2}, \dots}$ . Thus, we know that $\int_{0}^{T} [f_{u_{1}} (t) \land f_{u_{2}} (t)] \neq 0$ when $T = (v_{1} \cdot p_{1}) \times (v_{2} \cdot p_{2})$ .

In Theorem 1, we showed that the cycle lengths of two nodes are not prime numbers. If the two nodes have cycle lengths that are prime numbers, we can apply CRT directly, and we know that the two nodes have a common active slot. In addition, when one of these two nodes has a cycle length value that is a prime number and the other does not, we can apply Theorem 1. Thus, we obtain two nodes that have a common active slot.

Remark 1

If $u_{1} and u_{2}$ have schedules where $v_{1}, v_{2} \in P$ , they always have common active slots by virtue of the CRT. (2) If $u_{1} and u_{2}$ have schedules where $v_{1} \in P$ and $v_{2} \notin P$ , they have common active slots due to the applicability of the special case of Theorem 1.

Figure 7 shows common active slots between nodes $u_{1}$ and $u_{2}$ . In this example, $u_{1}$ uses a (7,3,1)-BIBD and $u_{2}$ uses a (21,5,1)-BIBD. Because $v_{1}$ is a prime number, it does not add an active slot to the schedule. Furthermore, $v_{2}$ is not a prime number. Consequently, the prime number 19 is selected through the algorithm in Figure 6. Then, $f_{u_{1}}^{7} (t)$ and $f_{u_{2}}^{133} (t)$ have common active slots at indices 19 and 133 according to the CRT.

Figure 7.

Common active slot between node $u_{1}$ and $u_{2}$ .

Numerical analysis

In this section, to show that BC-AWS is mathematically superior to BIBD and PBD, we examine the length of the whole cycle corresponding to the duty cycle and the change of the worst-case latency when packet drops occur.

In detail, the latency boundary means the total cycle length of sensor scheduling. The reason is that most sensor nodes find their neighbor sensors within their communication ranges. For example, if sensor nodes use (7,3,1)-symmetric BIBD for their scheduling, their latency boundary for one cycle is 7.

First, the cycle length for the duty cycle is the total length of one cycle performed by the sensor node to find a neighboring node. Figure 8 shows a graph comparing the total cycle length for the duty cycle. The X-axis represents the duty cycle, and the Y-axis represents the length of the entire cycle. Compared to PBD, which provides asymmetric duty cycles using a prime number, the proposed BC-AWS has the same cycle length as BIBD, which is the optimal algorithm. These results show that the proposed BC-AWS not only provides asymmetric duty cycles but also performs well because it has the same performance as BIBD, which is the optimal algorithm.

Figure 8.

Total cycle length of NDPs each duty cycle.

In the case of Figure 9, latency occurs when the data that is transmitted while the sensor node is communicating in the sensor network environment is lost. In the case of the BC-AWS method proposed herein, the BIBD demonstrates optimal performance regardless of packet loss. In contrast, for PBD, the latency due to packet loss is higher than those of BIBD and BC-AWS. The root cause of this result is that the overall cycle length of PBD is greater than those of BIBD and BC-AWS.

Figure 9.

Worst-case latency of NDPs each duty cycle.

Performance evaluation

This section shows the experimental results of comparing BC-AWS with BIBD, U-Connect, DISCO, QUORUM, SearchLight, Hedis, Todis, and PBD in symmetric as well as asymmetric duty cycle scenarios. Here, the QUORUM and BIBD protocols are only evaluated for the symmetric case, because they cannot support both symmetric and asymmetric duty cycles.

Simulation parameters

To evaluate BC-AWS and other NDPs, we implemented the proposed BC-AWS scheme in TOSSIM. We then integrated the Power-TOSSIM module into TOSSIM to measure the energy consumption during the discovery phase. Moreover, we assumed that our sensor nodes use CC2420¹⁸ radio modules for communication. For a link model and channel access scheme, we consider CSMA/CA¹⁹ and the University of Southern California (USC) link module.²⁰ We assume that 50 sensor nodes are randomly deployed within a 100 m × 100 m field. Furthermore, our simulation has a 15-ms time slot, and each sensor toggles its radio module on or off based on the discovery scheduling. Moreover, sensor nodes use the maximum power of the radio transmission chip to exchange packets.

We consider four symmetric duty cycles: 1%, 2%, 5%, and 10%. For asymmetric duty cycles, the asymmetry ratio, R, is defined as follows

R = \frac{duty cycle of higher duty cycle node}{duty cycle of lower duty cycle node}

For example, if one group of sensor nodes has a 10% duty cycle and the other group has a 5% duty cycle, the R value is 2 = $10 % / 5 %$ .

Tables 1 and 2 show the parameters of the NDPs compared herein for the 1%, 2%, 5%, and 10% duty cycles. U-Connect uses only a prime number p. DISCO uses two prime numbers, $p_{1}$ and $p_{2}$ . In the case of SearchLight and Hedis, to generate the schedule, the length of one row of the matrix is a value. Todis uses the median value m of three values (m − 2, m, m + 2). Similarly, QUORUM has one row m of the matrix for the sensor schedule parameters. PBD, BIBD, and BC-AWS use the BIBD optimal length h for the schedule parameter. PBD also has an additional prime number p.

Table 1.

Setting parameter for each NDP.

Protocol	Parameters	Active slots	Cycle length
U-Connect	p	$\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_{1} p_{3}, p_{1} p_{4} \end{matrix}}$
SearchLight	t	t	$t^{2}$
Hedis	n	2n–2	$n^{2}$
Todis	m	m	(m–2)m(m + 2)
PBD	h p	$h + 1 + α$	$h^{2} + h + 1$
BIBD, BC-AWS	h	H + 1	$h^{2} + h + 1$
Quorum	m	2m–1	$m^{2}$

NDP: neighbor discovery protocol; PBD: prime-based block design; BIBD: balanced incomplete block design; BC-AWS: block combination–based asynchronous wake-up schedule.

Table 2.

NDP parameter values for each duty cycle.

Protocol	10%	5%	2%	1%
U-Connect	p = 13	p = 29	p = 73	p = 149
Disco	p ₁ = 17, p₂ = 23	p ₁ = 37, p₂ = 43	p ₁ = 93, p₂ = 103	p ₁ = 197, p₂ = 199
SearchLight	t = 20	t = 40	t = 100	t = 200
Hedis	n = 20	n = 40	n = 100	n = 200
Todis	m = 30	m = 60	m = 150	m = 300
PBD	h = 9, p = 89	h = 19, p = 379	h = 49, p = 2447	h = 97, p = 9497
BIBD, BC-AWS	h = 9	h = 19	h = 49	h = 97
Quorum	m = 19	m = 39	m = 199	m = 199

NDP: neighbor discovery protocol; PBD: prime-based block design; BIBD: balanced incomplete block design; BC-AWS: block combination–based asynchronous wake-up schedule.

Experimental results of BC-AWS

In this section, we analyze the experimental results of BC-AWS at 1%, 2%, 5%, and 10% duty cycles. In particular, we consider the maximum, minimum, and average latency and energy consumption for the evaluation elements.

In Figure 10, we can see maximum, minimum, and average latencies of the BC-AWS in a symmetric environment. In the graph, we know that the latency increases when the duty cycle decreases. At that time, the latency exponentially increases rather than simply linearly increasing the latency. The reason is that the total cycle length of the low-duty cycle is longer than that of a high-duty cycle. Also, a long total cycle length means that the sensor nodes need more time than in a short total cycle length if sensor nodes drop packets during communication.

Figure 10.

Discovery latency for a symmetric duty cycle at BC-AWS.

Figure 11 shows experimental results of BC-AWS in an asymmetric environment. The latency of the asymmetric environment is similar to the symmetric experimental results. However, the average latency of an asymmetric environment has a lower energy consumption than that of a symmetric environment. The reason is that there are three cases, such as 10%–10%, 1%–1%, and 10%–1%, if the sensor nodes have 10% and 1% duty cycles. That is, in an asymmetric environment, a pair of sensor nodes is one of three different sets, such as 10%–10%, 1%–1%, and 10%–1%. Thus, the 1%–1% and 10%–1% pair make the latency long. Therefore, the experimental results of the asymmetric duty cycle have a worse performance than the symmetric duty cycle.

Figure 11.

Discovery latency for asymmetric duty cycle at BC-AWS.

Figure 12 shows the energy consumption of BC-AWS in a symmetric duty cycle. Unlike the experimental results of latency, the graph pattern of energy consumption is linear instead of exponential, which is a pattern of latency. The reason is that the energy consumption is small if sensor nodes turn off their radio modules to prevent communication between sensor nodes.

Figure 12.

Energy consumption for symmetric duty cycle at BC-AWS.

Figure 13 shows the energy consumption of BC-AWS in an asymmetric duty cycle. Unlike the pattern of energy consumption in a symmetric duty cycle, the energy consumption in an asymmetric duty cycle is increased exponentially. The reason is that not all sensor nodes have the same duty cycle in an asymmetric duty cycle. That is, although some sensor nodes find their neighbors, they consume their energy until sensor nodes with low-duty cycles find their neighbor nodes. For example, if there are three connections between sensor nodes such as 10%–10%, 10%–1%, and 1%–1%, although sensor nodes with a 10% duty cycle find their neighbors, they consume energy until they find neighbor sensor nodes with a 1% duty cycle.

Figure 13.

Energy consumption for asymmetric duty cycle at BC-AWS.

Experimental results for the symmetric case

In this section, we examine the results of employing symmetric duty cycles. In terms of energy consumption, we know that low-duty cycles consume more energy than high-duty cycles owing to the frequent occupation of active slots of each cycle in the low-duty case. This energy consumption is particularly dependent on the type of NDP employed. For example, because prime-based NDPs use two prime numbers and because sensor nodes have QUORUM-based NDPs for their scheduling, they have high energy consumption for low-duty cycles. Furthermore, BIBD-based NDPs such as BIBD, BC-AWS, and PBD, are better than prime-based or QUORUM-based NDPs because of their short total cycle lengths. In particular, BC-AWS is the best-known among all the above mentioned NDPs. The reason is that within its total length, each cycle is the same as that for BIBD, which is known to be the optimal solution for the symmetric-duty-cycle case. In contrast, PBD NDPs add one more active slot in each cycle. Critical problems occur if the discovery time is delayed. Consequently, within particular limitations of the duty cycles, the implementation of BC-AWS can save the energy of up to one active slot. Therefore, BC-AWS outperforms the other NDPs.

Similarly, in terms of discovery latency, BC-AWS is comparable to PBD and superior to other NDPs, such as U-Connect, DISCO, BIBD, QUORUM, SearchLight, Hedis, and Todis. This is because they have one more active slot, and BC-AWS increases the ratio of common active slots owing to slot rotation, which makes all sensor nodes simultaneously choose the same pivot slot (Figure 14).

Figure 14.

Energy consumption and discovery latency for a symmetric duty cycle.

Experimental results for the asymmetric case

In the case of asymmetric duty cycles, sensor nodes have different duty cycles. Prime-based NDPs consume more energy than QUORUM-based and BIBD-based NDPs because the sensor nodes in that case require longer discovery times owing to the CRT. Similarly, if the QUORUM-based NDP of Todis chooses the last row and column for sensor scheduling, its energy consumption is higher than that of other NDPs. However, if sensor nodes use BIBD-based NDPs, such as BC-AWS and PBD, they always end up outperforming prime- or QUORUM-based NDPs, because BIBD-based NDPs possess the optimal total cycle length. The discovery latency results reflect the energy consumption results. The discovery latency for BIBD-based NDPs is better than that for other NDPs, such as U-Connect, DISCO, SearchLight, Hedis, and Todis. Moreover, BC-AWS is superior to PBD due to its pivot slot drifting scheme.

Therefore, these experimental evaluations of symmetric and asymmetric duty cycles prove that BC-AWS outperforms representative NDPs such as U-Connect, Disco, QUORUM, SearchLight, Todis, and Hedis. Moreover, for symmetric duty cycles, BC-AWS exhibits the same performance as BIBD, which is the optimal solution for a symmetric environment.

The energy consumption of U-Connect is highest because half of the cycle length is dedicated to active slots. The performances of SearchLight and Hedis are similar because both use half of the NDP matrix for active slots (Figure 15).

Figure 15.

Energy consumption and discovery latency for an asymmetric duty cycle.

The energy performance of Disco is poor because this scheme constructs sensor schedules using two different prime numbers, which increases the total cycle length (recall that the cycle length in this scheme is the multiplication of two prime numbers). The long cycle length increases the time required for sensor nodes to find their neighbors. Therefore, the energy consumption is higher than for short cycle lengths. Overall, BC-AWS outperformed both matrix-based and prime-number-based NDPs by virtue of the BIBD-based NDP operation. The BC-AWS needs assistance from prime numbers if two sensor nodes lack common active slots within the LCM.

Conclusion

In this article, we proposed a novel protocol for sensor discovery scheduling called BC-AWS, which uses a block combination operation and pivot moving scheme. The proposed NDP joins blocks of BIBD using block combination operation ⊎. When BC-AWS chooses blocks with a single pivot slot, it continually compares the index of the pivot slot against the value of parameter l. If the index of the pivot slot is smaller than the value of l, the schedule is sufficient. If not, BC-AWS appends another block to the very bottom of the block with twice the value of l and adds one active slot after the prime index. This always guarantees common active slots between sensor nodes owing to the CRT and properties of the BIBD. In addition, the active slots in BC-AWS are similar to those in the original BIBD, which is known to be the optimal solution. We evaluated the availability of common active slots between sensor nodes with different duty cycles based on theorems and lemmas. Moreover, we implemented a simulation comparing BC-AWS with other NDPs to prove the superior performance of BC-AWS. Through experimental results, we proved that the discovery latency and energy consumption of BC-AWS is lower than those of other NDPs, such as PBD, U-Connect, Disco, SearchLight, Hedis, and Todis. Subsequently, we proved that BC-AWS can support both symmetric and asymmetric duty cycles, and it performs well compared to recent NDPs.

In future studies, we will consider adapting our algorithm to various Internet of Things environments, such as smart cities, intelligence transportation systems, and long-term evolution systems. Moreover, we plan to combine block design and the prime theorem with urban engineering and traffic engineering solutions because our society is expected to move toward the Internet of Everything, where people, processes, data, and things are interconnected to demonstrate new capabilities, richer experiences, and unprecedented economic prosperity.

Footnotes

Handling Editor: Zhong Shen

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 Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2015R1D1A1A01058786).

References

Kandhalu

Lakshmanan

Rajkumar

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

Lee

Youn

Song

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

Youn

Lee

Song

. Block cycle length-based asymmetric rendezvous protocol for IoT applications. In: Proceedings of the 16th ACM/IEEE international conference on information processing in sensor networks, Pittsburgh, PA, 18–20 April 2017, pp. 287–288. Pittsburgh, PA: ACM.

Choi

Lee

Song

et al . Block design-based asynchronous neighbor discovery protocol for wireless sensor networks. J Sensors 2015; 2015: 951652.

Choi

HH.

Neighbor discovery protocol based on inhibited and priority access controls for multihop cellular networks. J Korea Inst Inform Commun Eng 2013; 17(11): 2533–2540.

Lee

Choi

Song

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

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.

Chen

Fan

Bian

et al . On heterogeneous neighbor discovery in wireless sensor networks. In: Proceedings of IEEE INFOCOM, Kowloon, 20 November 2015, pp.693–701. New York: IEEE.

Bakht

Trower

Kravets

Searchlight: won’t you be my neighbor? In: Proceedings of the 18th annual international conference on mobile computing and networking, Istanbul, Turkey, 22–26 August 2012, pp.185–196. New York: ACM.

10.

Dutta

Culler

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

11.

Ding

Pei

Salomaa

Chinese remainder theorem: applications in computing, coding, cryptography. Hackensack, NJ: World Scientific Publishing Co, 1996.

12.

Wei

Zhou

et al . Lightning: a high-efficient neighbor discovery protocol for low duty cycle WSNs. IEEE Commun Lett 2016; 20(5): 966–969.

13.

Margolies

Grebla

Chen

et al . Panda: neighbor discovery on a power harvesting budget. IEEE J Sel Areas Commun 2016; 34(12): 3606–3619.

14.

Zhen

Lou

Wang

et al . On achieving asynchronous energy-efficient neighbor discovery for mobile sensor networks. IEEE T Emerg Top Comput 2016; PP: 1.

15.

Chen

Shu

et al . Group-based neighbor discovery in low-duty-cycle mobile sensor networks. IEEE T Mob Comput 2016; 15(8): 1996–2009.

16.

Zhang

et al . Neighbor discovery and rendezvous maintenance with extended quorum systems for mobile applications. IEEE T Mob Comput 2017; 16(7): 1967–1980.

17.

Stinson

DR.

Combinatorial designs: constructions and analysis. New York: Springer, 2004.

18.

CC2420 Preliminary Datasheet, https://inst.eecs.berkeley.edu/∼cs150/Documents/CC2420.pdf

19.

Oliver

Escudero

. Study of Different CSMA/CA IEEE 802.11-based Implementations. In: EUNICE 1999 Contribution, 1999, http://www.eunice-forum.org/eunice99/027.pdf

20.

USC Link Model, http://tinyos.stanford.edu/tinyos-wiki/index.php/TOSSIM

Block combination–based asynchronous wake-up schedule in wireless sensor networks

Abstract

Keywords

Introduction

Related work

Background and problem statement

Theoretical basis of wakeup design

Definition 1

Definition 2

Problem statement

BC-AWS

Block generation scheme

Block combination operation

Pivot moving sequence scheme

Lemma 1

Proof

Guarantee of a common active slot

Theorem 1

Proof

Remark 1

Numerical analysis

Performance evaluation

Simulation parameters

Experimental results of BC-AWS

Experimental results for the symmetric case

Experimental results for the asymmetric case

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References