An Energy-Efficient CKN Algorithm for Duty-Cycled Wireless Sensor Networks

Abstract

To prolong the lifetime of a wireless sensor network, one common approach is to dynamically schedule sensors' active/sleep cycles (i.e., duty cycles) using sleep scheduling algorithms. The connected K-neighborhood (CKN) algorithm is an efficient decentralized sleep scheduling algorithm for reducing the number of awake nodes while maintaining both network connectivity and an on-demand routing latency. In this paper, we investigate the unexplored energy consumption of the CKN algorithm by building a probabilistic node sleep model, which computes the probability that a random node goes to sleep. Based on this probabilistic model, we obtain a lower epoch bound that keeps the network more energy efficient with longer lifetime when it runs the CKN algorithm than it does not. Furthermore, we propose a new sleep scheduling algorithm, namely, Energy-consumption-based CKN (ECCKN), to prolong the network lifetime. The algorithm EC-CKN, which takes the nodes' residual energy information as the parameter to decide whether a node to be active or sleep, not only can achieve the k-connected neighborhoods problem, but also can assure the k-awake neighbor nodes have more residual energy than other neighbor nodes in current epoch.

1. Introduction

Wireless sensor networks (WSNs) are normally powered by batteries with limited energy, which are difficult or impossible to be recharged or replaced. A common approach for saving the sensor nodes' energy is to select a subset of nodes to remain active/awake and let others go to sleep in a given epoch. Most of current literatures on sleep scheduling in WSNs are to achieve point coverage and/or node coverage problems [1]. Point coverage problem (also called spatial coverage) focuses on selecting a set of active nodes in an epoch so that every point of the deployment space is covered, while considering some optimization goals, for example, minimizing energy consumption [2], minimizing average event detection latency [3]. Node coverage problem (also called network coverage) focuses on choosing a set of active nodes, in which (1) they construct a connected backbone and (2) sleeping nodes are direct neighbors of at least one active node [4]. This node coverage problem is to ensure that any two nodes in the network can communicate with each other through the connected backbone.

The Connected K-Neighborhood (CKN) algorithm is a distributed sleep scheduling algorithm [1], which can reduce the number of active nodes efficiently. It keeps the network k-connected and optimizes the geographic routing performance. Supporting the geographic routing performance is not studied in any previous point coverage and node coverage researches. Although, the CKN algorithm performs well with the geographic routing protocols, the following questions are not addressed in paper [1]. (1) How frequently should the CKN algorithm be executed in the network so that it can really help to save energy, for each time executing the CKN algorithm also consumes energy? Intuitively, executing the CKN algorithm will consume a mass of energy with substantial data transmission to exchange local information between nodes and their neighbors, which influences the energy consumption distribution of network. (2) Do all active sensor nodes in the CKN algorithm [1] consume the energy uniformly in each epoch? We identify the nonuniform energy consumption problem, as shown in Figure 1. It is recognized that when executing the CKN algorithm in WSNs, sensor nodes with less residual energy are possible to be selected, which may result in that the energy of these sensor nodes can be fast consumed. The problem is caused by: the CKN algorithm chooses the active nodes absolutely based on the $rank$ s that are randomly given at the beginning of executing the CKN algorithm in each epoch. In other words, the CKN algorithm cannot ensure the network energy is balancedly consumed.

Figure 1

Nonuniform energy consumption problem. In (a), the black nodes represent the nodes which have more residual energy than those of node $N_{0}$ , the grey and white nodes have less energy than $N_{0}$ 's, and the white node has the least energy. In (b), the green nodes represent the active nodes according to the CKN algorithm in a WSN, and the sensor nodes with less residual energy are selected.

Motivated by above two major issues, we conduct theoretical studies on two important questions based on the CKN algorithm. The first question is as follows. Is the CKN algorithm energy saving for any given value of k and the epoch? If not, how frequently should the CKN algorithm be executed so that the network is energy saving? In order to find out the relationship between the epoch and the energy consumption, we build a probabilistic model for the CKN algorithm to compute the probability that each random node goes to sleep and the expected total number of epochs during each node's lifetime. We formulate the lower bound of an epoch to keep the CKN algorithm energy efficient.

We address the second question based on the analysis for the first problem: How do we design a new sleep scheduling algorithm based on the CKN algorithm that can balance the energy consumption to prolong network lifetime further? Satisfying all those requirements that the CKN algorithm holds, a new decentralized sleep scheduling algorithm is challenging. In the light of the discussions for the question 1, we propose a new sleep scheduling algorithm, named energy-consumption-based CKN (EC-CKN), to prolong the network lifetime. The advantage of the EC-CKN algorithm over the original CKN algorithm is that it takes the nodes' residual energy information as parameter to decide whether a node to be active or sleep. The EC-CKN algorithm inherits all the major properties of the CKN algorithm, that is, solving the k-connected neighborhoods problem. Meanwhile, it also makes a significant new contribution to the energy efficiency by assuring the k-active neighbor nodes have more residual energy than other neighbor nodes in the current epoch. A theoretical analysis on the energy consumption of the EC-CKN algorithm is given to show the correctness of the new contribution.

The rest of the paper is as follows. Section 2 shows the network model. Section 3 presents the original CKN algorithm regulation and its properties. Section 4 builds a probabilistic model to compute the probability that a random node goes to sleep. Section 5 presents the EC-CKN algorithm. Section 6 demonstrates the properties of the EC-CKN algorithm. Section 7 shows the simulation results about the original CKN algorithm and the EC-CKN algorithm, comparing theoretical values and simulation results. Finally, Section 9 concludes the paper.

2. Network Model

2.1. Communication Network Model

A multihop sensor network is modeled by a graph $G = (S, E)$ , where $S = {s_{1}, s_{2}, \dots, s_{n}}$ is the set of sensor nodes and E is the set of directed links. Each node has a uniform transmission radius of $r_{t}$ , and the necessary condition of $(s_{i}, s_{j}) \in E$ is $| s_{i} - s_{j} | \leq r_{t}$ and a node $s_{j}$ is the next hop of $s_{i}$ to the sink by the routing protocol. If $(s_{i}, s_{j}) \in E$ , we use $l_{i, j}$ to denote $(s_{i}, s_{j})$ . Each node also has a uniform interference radius of $r_{f}$ . An node $s_{j}$ is interfered by the signal from $s_{i}$ , if $| s_{i} - s_{j} | \leq r_{f}$ and $s_{j}$ is not the intended receiver. Let $I_{i}$ be the interference region that centers at $s_{i}$ with the interference radius $r_{f}$ . Each node is only equipped with a single radio interface and has the uniform initial energy $ℰ_{0}$ . The entire network lifetime is divided into epochs, and each epoch is T. At the beginning of each epoch, a node transmits packets in $T_{1}$ , and then it runs the sleep scheduling algorithm to decide the state of the next epoch in $T_{2}$ (where $T = T_{1} + T_{2}$ ) as shown in Figure 2.

Figure 2

The lifetime of a node $s_{u}$ consists of many epochs. Each epoch includes packet transmission time and sleep scheduling algorithm's execution time.

2.2. Event Generation Model

Assume each node has a uniform sensing radius $r_{s}$ . Let $C_{u}$ denote the sensing region of the node $s_{u}$ , which centers at $s_{u}$ with the sensing radius $r_{s}$ . An event occurs when the sensing unit of a node $s_{u}$ picks up a signal with the power above a predetermined threshold within the sensing region $C_{u}$ [5]. Suppose the temporal event behavior over the entire sensing region, 𝒜, is a Poisson process with an average event rate λ. Let $p_{X Y} (x, y)$ denote an independent probability distribution of the spatial distribution of events. Let $p_{e}$ denote the probability that an event is detected by a node $s_{u}$ , given the fact that it occurred in 𝒜:

\begin{matrix} p_{e} & = \frac{\int_{C_{u}} p_{X Y} (x, y) d x d y}{\int_{A} p_{X Y} (x, y) d x d y} \end{matrix},

(1)

where

p_{X Y} (x, y)

is the spatial distribution of events that is characterized by an independent probability distribution. Let

p_{m} (T, n)

denote the probability that n events occur in an epoch T at a node

s_{u}

. Therefore, the probability of no events occurring in

C_{u}

over an epoch T is given by

\begin{matrix} p_{m} (T, 0) & = \sum_{i = 0}^{\infty} \frac{e^{- λ T {(λ T)}^{i}}}{i!} {(1 - p_{e})}^{i} \\ = e^{- p_{e} λ T} . \end{matrix}

(2)

Let

p_{m} (T)

denote the probability that at least one event occurs in an epoch T at a node

s_{u}

p_{m} (T) = 1 - p_{m} (T, 0) = 1 - e^{- p_{e} λ T} .

(3)

That is the probability of at least one event occurring at the node

s_{u}

is an exponential distribution characterized by a spatially weighted event arrival rate

λ_{u, u} = λ \times p_{e}

2.3. Buffer Analysis

Now, we consider two sources of traffic as an input to the buffer of each node [6].

Generated Packets

The sensing unit of a node senses events and generates packets as discussed in Section 2.2. These packets are generated packets. For a node $s_{u}$ , the rate of the generated packets is denoted by $λ_{u, u}$ .

Relay Packets

A node also receives packets from its upstream nodes and then forwards them to the sink node. (Along the data stream from a source node to the sink node by the routing protocol, downstream nodes are closer to the sink node, and receive packets sent by the node. Upstream nodes are far away from the sink node, and transmit packets to the node). These packets are referred as relay packets. The rate at which a node $s_{u}$ receives relay packets from a node $s_{v}$ is denoted as $λ_{v, u}$ .

Therefore, the input packet rate of $s_{u}$ 's buffer, $λ_{u}$ , can be written as

λ_{u} = λ_{u, u} + λ_{u, r} = λ_{u, u} + \sum_{v \in N_{u}^{in}} λ_{v, u},

(4)

where

λ_{u, r}

is the total relay packet rate at the node

s_{u}

𝒩_{u}^{in}

is the set of nodes that have the node

s_{u}

as the next hop, and

λ_{v, u}

is the packet rate from the node

s_{v}

to the node

s_{u}

. Let

γ_{u}

be the output rate of a node, which is given by

γ_{u} = (1 + e_{u}) λ_{u},

(5)

where

e_{i}

is the packet error rate.

2.4. Channel and Energy Consumption Model

The energy consumption model characterizes energy consumption of a node in the network. Suppose there is no energy consumption when a node is sleep. If a node is active, we classify the energy consumption into three general categories.

(1) The Constant Energy Consumption

is the minimum energy needed to sustain a node when it is active without the packet transmission. It includes, for example, the battery leakage, energy consumed during the state transformation.

(2) The Additional Energy Consumption

is the energy consumed by the data transmission during the sleep scheduling algorithm running time.

(3) The Conventional Energy Consumption

includes the receiving energy consumption and the transmitting energy consumption except the local information exchange in the sleep scheduling algorithm, which is based on the first-order radio model [7].

The energy loss is due to the channel transmission, $ϵ_{amp}$ is the transmit amplifier. And the transmitting energy consumption for a bit packet is

E_{t x} = E + ϵ_{amp} \cdot r_{t}^{2},

(6)

and the receiving energy consumption is

E_{r x} = E,

(7)

where ℰ is energy consumed by the transmitter or receiver circuitry.

2.5. Lifetime Definition

There is no universally agreed definition of network lifetime as it depends on the specific application. The lifetime can be measured by the time when the first node exhausts its energy, or when a certain fraction of nodes is dead, or even when all nodes are dead. Alternately, it may be reasonable to measure the network lifetime by application-specific parameters, such as the time when the network can no longer relay sensory data packets. In this paper, we define the network lifetime is the time when the first sensor node run out its energy from the beginning. The general network lifetime is the exact individual lifetime of each active node [8].

Theorem 1.

For a sensor network, each node has nonrechargeable initial energy $ℰ_{0}$ , the average general network lifetime $𝔼 [ℒ]$ , is given by

E [L] = \frac{E_{0}}{E_{c} + λ_{r} E [E_{r x}] + γ E [E_{t x}]},

(8)

where

E_{c}

is the constant energy consumption on the first died node,

𝔼 [E_{r x}]

is the expected receiving energy consumption, and

𝔼 [E_{t x}]

is the expected transmitting energy consumption.

Proof.

Suppose there are M independently and identically distributed trials on the same sensor network to record the network lifetime ℒ, the receiving energy consumption of each bit $E_{r x}$ , and the transmitting energy consumption of each bit $E_{t x}$ . For the mth trial ( $1 \leq m \leq M$ ), the total energy consumed by the first died node during the whole lifetime is

E_{0} = E_{c} L^{m} + \sum_{i = 1}^{N_{r x}^{m}} E_{r x}^{m} (i) + \sum_{i = 1}^{N_{t x}^{m}} E_{t x}^{m} (i),

(9)

where

N_{r x}^{m}

is the number of bits to be received, and

N_{t x}^{m}

is the number of bits to be transmitted of the first died node during the network lifetime of the mth trial. Summing (9) up over the M trials and dividing both sides by M, we obtain

\begin{matrix} E_{0} = & \frac{1}{M} \sum_{m = 1}^{M} L^{m} [E_{c} \\ + (\frac{\sum_{m = 1}^{M} N_{r x}^{m}}{\sum_{m = 1}^{M} L^{m}}) \times (\frac{\sum_{m = 1}^{M} \sum_{i = 1}^{r x} E_{r x}^{m} (i)}{\sum_{m = 1}^{M} N_{r x}^{m}}) \\ + (\frac{\sum_{m = 1}^{M} N_{t x}^{m}}{\sum_{m = 1}^{M} L^{m}}) \times (\frac{\sum_{m = 1}^{M} \sum_{i = 1}^{N_{t x}^{m}} E_{t x}^{m} (i)}{\sum_{m = 1}^{M} N_{t x}^{m}})] . \end{matrix}

(10)

Note that

\lim_{M \to \infty} (\sum_{m = 1}^{M} N_{r x}^{m}) / (\sum_{m = 1}^{M} ℒ^{m}) = λ_{r}

is the average receiving rate and

\lim_{M \to \infty} (\sum_{m = 1}^{M} N_{t x}^{m}) / (\sum_{m = 1}^{M} ℒ^{m}) = γ

is the average transmitting rate.

The average receiving energy consumed in the ith received bit can be written as

E [E_{r x}] = \lim_{M \to \infty} \frac{\sum_{m = 1}^{M} E_{r x}^{m} (i) X_{m} (i)}{D_{r x} (i)}, 1 \leq i \leq N_{r x},

(11)

where

𝒳_{m} (i) = 1

for

1 \leq i \leq N_{r x}^{m}

and 0 otherwise.

D_{r x} (i) = \sum_{m = 1}^{M} 𝒳_{m} (i)

is the total number of the occurrence of the ith received bit among the M trials, and

N_{r x} = \max_{m} {N_{r x}^{m}}

is the maximum number of received bits during the network lifetime. The probability that the received bit chosen randomly happens to the ith received bit is given by

p_{r x} (i) = \lim_{M \to \infty} \frac{D_{r x} (i)}{\sum_{m = 1}^{M} N_{r x}^{m}}, 1 \leq i \leq N_{r x} .

(12)

Averaging (11) over the received bit chosen randomly indexing i, the expected receiving energy consumption is defined as

\begin{matrix} E [E_{r x}] & ≜ E_{r x}^{i} {E [E_{r x} (i)]} \\ = \lim_{M \to \infty} \frac{\sum_{m = 1}^{M} \sum_{i = 1}^{N^{m}} E_{r x}^{m} (i)}{\sum_{m = 1}^{M} N_{r x}^{m}}, \end{matrix}

(13)

where

𝔼 [E_{r x} (i)]

is the average energy consumed in ith bit packet,

𝔼_{r x}^{i} {\cdot}

denotes the expectation over the randomly chosen received packet indexing i.

Similarly, the expected transmitting energy consumption is

\begin{matrix} E [E_{t x}] & ≜ E_{t x}^{i} {E [E_{t x} (i)]} \\ = \lim_{M \to \infty} \frac{\sum_{m = 1}^{M} \sum_{i = 1}^{N_{t x}^{m}} E_{t x}^{m} (i)}{\sum_{m = 1}^{M} N_{t x}^{m}}, \end{matrix}

(14)

where

𝔼 [E_{t x} (i)]

is the average energy consumed in i th transmitted packet,

𝔼_{t x}^{(i)} {\cdot}

denotes the expectation over the randomly chosen transmitted packet indexing i.

3. A Brief Description of CKN

In [1], the studied WSN is represented as an undirected communication graph $G = (S, E)$ . $N_{u}$ is the set of $s_{u}$ 's neighbors. The connected K-neighborhood problem is defined as (i) each node has at least $\min {k, | N_{u} |}$ active neighbors, which can be called awake neighbors; (ii) all active nodes are connected. To solve the problem, the authors developed a sleep scheduling algorithm: connected K-neighborhood (CKN).

In CKN, each node $s_{u}$ picks a random rank $ran k_{u}$ , broadcasts the $ran k_{u}$ , and collects its neighbors' ranks in $R_{u}$ . And then, $s_{u}$ broadcasts $R_{u}$ and collects $R_{v}$ from its neighbors, where $s_{v} \in N_{u}$ . If $s_{u}$ or its neighbors has less than k neighbors, $s_{u}$ will remain awake. Otherwise, $s_{u}$ computes a subset $C_{u}$ of $N_{u}$ that is a set of nodes having $rank < ran k_{u}$ . “Before the node $s_{u}$ goes to sleep it needs to make sure that all nodes in $C_{u}$ are connected by nodes with $rank < ran k_{u}$ and each of its neighbors has at least k neighbors from $C_{u}$ ” [1].

The CKN algorithm has the following properties: first, each node $s_{u}$ (awake or not) with $| N_{u} |$ neighbors must have at least $\min {k, | N_{u} |}$ awake neighbors in each epoch; second, there is the minimal average number of awake nodes per epoch; finally, awake nodes change from epoch to epoch. For any $k \geq 1$ , there are more than $4 (k + \ln N)$ neighbors for each node, where N is the number of nodes in the network. Then, with high probability, $| CK N_{k} | = O (\ln N) \cdot | OP T_{k} |$ , where $| CK N_{k} |$ is the number of awake nodes by the CKN algorithm and $| OP T_{k} |$ is the number of awake nodes by an optimal algorithm that finds a minimum connected k-neighborhood as Figure 3.

Figure 3

Four examples of executing the CKN algorithm with different values for k. When $k = 1$ , a large number of sensor nodes can turn to sleep mode, but, when $k = 8$ , almost all sensor nodes have to be always-on. Here, black and unconnected sensor nodes are sleeping nodes.

4. Analysis of the CKN Algorithm

In this section, we build up a probabilistic model for the CKN algorithm to compute the probability that one node $s_{u}$ goes to sleep in each epoch. Based on the probability, we formulate the lower bound of an epoch to keep the CKN algorithm energy efficient.

Notations used in this section

$N_{u}$ is the set of $s_{u}$ 's neighbors, and $N_{u}^{'}$ is the set of $s_{u}$ 's 2-hop neighbors. $C_{u}$ and $C_{u}^{'}$ are the subsets of $N_{u}$ and $N_{u}^{'}$ having $rank \leq ran k_{u}$ . $| N_{u} |$ , $| N_{u}^{'} |$ , $| C_{u} |$ , and $| C_{u}^{'} |$ are the number of the elements in $N_{u}$ , $N_{u}^{'}$ , $C_{u}$ , and $C_{u}^{'}$ , respectively. Graphs $G_{C_{u}}$ and $G_{C_{u}^{'}}$ are composed of nodes and potential links in $C_{u}$ and $C_{u}^{'}$ .

For a homogeneous Poisson point process in two dimensions, the probability that a random node has n neighbors is [9]

P (| N_{u} | = n) = \frac{{(ρ π {r_{t}}^{2})}^{n}}{n!} \cdot e^{- ρ π {r_{t}}^{2}},

(15)

where

ρ = N / 𝒜

is the nodes density. And a node is isolated with a probability of

P (| N_{u} | = 0) = e^{- ρ π {r_{t}}^{2}}

. The expectation of the number of

s_{u}

's neighbors is

E [| N_{u} |] = ρ π {r_{t}}^{2} .

(16)

If there are at least k different paths connecting any two different vertices in the graph G, the graph is k-connected ( $k = 1,2, \dots$ ). The probability that the graph G is k-connected is

P (G^{k}) = {(1 - \sum_{n}^{k - 1} \frac{{(ρ π {r_{t}}^{2})}^{n}}{n!} \cdot e^{- ρ π {r_{t}}^{2}})}^{N} .

(17)

4.1. Sleep Probability in the CKN Algorithm

For the CKN algorithm, when a node $s_{u}$ has at least k neighbors, whether it goes to sleep is decided by two factors: (1) “any two nodes in $C_{u}$ are connected either directly or indirectly through $s_{u}$ 's 2-hop neighbors that have $rank$ less than $ran k_{u}$ ” and (2) “any node in $N_{u}$ has at least k neighbors for $C_{u}$ ” [1].

Lemma 2.

$| C_{u} | ~ B (| N_{u} |, p)$ and $| C_{u}^{'} | ~ B (| N_{u}^{'} |, p)$ are binomial distributions, where p is the probability that a node has $rank < {rank}_{u}$ .

Proof.

Let ${ran k_{1}, ran k_{2}, \dots, ran k_{| N_{u} |}}$ be the random ranks for nodes in $N_{u}$ . Suppose $ran k_{i} \in (0,1)$ and $i \in [1, | N_{u} |]$ . Let

\begin{gathered} x_{i} = {\begin{cases} 1, & if ran k_{u} - ran k_{i} > 0, \\ 0, & otherwise, \end{cases} \\ p = p_{i} (x_{i} = 1) = E (P_{ran k_{u} - ran k_{i} > 0}) = \frac{1}{2}, \\ q = p_{i} (x_{i} = 0) = 1 - p . \end{gathered}

(18)

Let

Z = \sum_{i \in N_{u}} x_{i}

, and the probability

z_{j} = j

\begin{matrix} p_{j} & = (_{j}^{| N_{u} |}) \cdot p^{j} \cdot q^{| N_{u} | - j} \\ = (_{j}^{| N_{u} |}) \cdot p^{| N_{u} |}, \end{matrix}

(19)

where

j \in [0, | N_{u} |]

and

| C_{u} | ~ B (| N_{u} |, p)

. Similarly,

| C_{u}^{'} | ~ B (| N_{u}^{'} |, p)

Theorem 3.

Under the CKN algorithm, the sleep probability of a node $s_{u}$ is

p_{s} (| C_{u} |) = {Prob}_{1} \cdot {Prob}_{2},

(20)

and the awake probability is

p_{a} (| C_{u} |) = 1 - p_{s} (| C_{u} |),

(21)

where

Pro b_{1}

, the probability a node

s_{u}

satisfies the first condition, is defined as

{Prob}_{1} ≜ {(1 - {e^{- ρ_{1} π r_{t}}}^{2})}^{| C_{u}^{'} |},

(22)

and

Pro b_{2}

, the probability

s_{u}

satisfies the second condition, is defined as

{Prob}_{2} ≜ P (| C_{u} | \geq k + 1) \cdot P (G_{C_{u}}^{k}) \cdot P ({C_{u}}_{N_{u} - C_{u}}^{k}) .

(23)

Proof.

If $s_{u}$ and its neighbors have at least k neighbors, the two conditions deciding $s_{u}$ whether to sleep or not can be interpret as the following corresponding conditions: (1) the graph $G_{C_{u}^{'}}$ is connected, and (2) the graph $G_{C_{u}}$ is k-connected and each node in the set $N_{u} - C_{u}$ has at least k neighbors in $C_{u}$ .

The probability that the graph $G_{C_{u}^{'}}$ is k-connected is

\begin{matrix} Pro b_{1} & \leq Prob (G_{C_{u}^{'}} is connected) \\ \leq P ({| N_{u} |}_{\min} \geq 1) \\ = {(1 - e^{{- ρ_{1} π r_{t}}^{2}})}^{| C_{u}^{'} |}, \end{matrix}

(24)

where

{| N_{u} |}_{\min}

is the minimum degree in the graph

G_{C_{u}^{'}}

, and

ρ_{1} = | C_{u}^{'} | / ({4 π t_{r}}^{2})

is the node density in the graph

G_{C_{u}^{'}}

The probability of the condition (2) is

Pro b_{2} = P (| C_{u} | \geq k + 1) \cdot P (G_{C_{u}}^{k}) \cdot P ({C_{u}}_{N_{u} - C_{u}}^{k}),

(25)

where

P (G_{C_{u}}^{k})

, the probability that the graph

G_{C_{u}}

is k-connected, can be expressed as

P (G_{C_{u}}^{k}) \leq {(1 - \sum_{n = 0}^{k - 1} \frac{{({ρ_{2} π r_{t}}^{2})}^{n}}{n!} \cdot e^{- ρ_{2} π r_{t}^{2}})}^{| C_{u} |},

(26)

and

P ({C_{u}}_{N_{u} - C_{u}}^{k})

is the probability that a node

s_{v} \in (N_{u} - C_{u})

has at least k neighbors in

C_{u}

, which is

P ({C_{u}}_{N_{u} - C_{u}}^{k}) = {(1 - \sum_{n = 0}^{k - 1} \frac{{({ρ_{2} π r_{t}}^{2})}^{n}}{n!} \cdot e^{{- ρ_{3} π r_{t}}^{2}})}^{| N_{u} - C_{u} |},

(27)

where

ρ_{2} = | C_{u} | / ({π t_{r}}^{2}), ρ_{3} = (| C_{u} | + 1) / ({π t_{r}}^{2})

, and

| N_{u} - C_{u} |

is the number of the elements in the set

N_{u} - C_{u}

4.2. Energy Consumption of the CKN Algorithm

Based on the result of the probability a random node goes to sleep, we can now analyze the node energy consumption for two cases: (1) it runs the CKN algorithm; (2) it does not run the CKN algorithm.

Lemma 4.

When a node $s_{u}$ executes the CKN algorithm, its energy consumption is

E_{ckn} (s_{u}) = E_{c}^{1} + 2 (E_{t x} + | N_{u} | \cdot E_{r x}),

(28)

and the energy consumption of a node during each epoch is

E_{epoch} (s_{u}) = E_{c}^{2} + T_{1} (λ_{r} E_{r x} + γ E_{t x}),

(29)

where

ℰ_{c}^{1}

and

ℰ_{c}^{2}

are the constant energy consumptions of a node during the time of the CKN algorithm executed and an epoch, respectively.

Theorem 5.

Under the CKN algorithm, the lower bound of an epoch keeping the network energy efficient is

\underset{̲}{T} \geq \frac{E [L] (E [E_{ckn}] + p_{a} \cdot E [E_{epoch}])}{E_{0}},

(30)

where

𝔼 [ℰ_{ckn}]

and

𝔼 [ℰ_{epoch}]

are the expectation energy consumption during the time of the CKN algorithm executed and the expectation of the energy consumption during an epoch.

Proof.

Suppose there are M i.i.d. trials on the same network that runs the CKN algorithm as the sleep schedule to record the network lifetime, $ℒ_{ckn}$ , and the epoch is T in each trial. For the mth trial, the total energy consumed by the first died node during the lifetime is

E_{0} = N_{epoch}^{m} E_{ckn} + \sum_{i = 1}^{N_{epoch}^{m}} E_{epoch}^{m} (i),

(31)

where

𝒩_{epoch}^{m}

is the number of epochs in the mth trial. Summing (31) up to the M trials and dividing both sides by M, we obtain

E_{0} = \frac{1}{M} [E_{ckn} \sum_{m = 1}^{M} N_{epoch}^{m} + \sum_{m = 1}^{M} \sum_{i = 1}^{N_{epoch}^{m}} E_{epoch}^{m} (i)] .

(32)

Note that

T \lim_{M \to \infty} (1 / M) \sum_{m = 1}^{M} 𝒩_{epoch}^{m} = 𝔼 [ℒ_{ckn}]

The average energy consumed in the ith epoch can be written as

\begin{matrix} E [E_{epoch}] & = \lim_{M \to \infty} \frac{\sum_{m = 1}^{M} E_{epoch}^{m} (i) Y_{m} (i)}{D_{epoch} (i)}, \\ 1 \leq i \leq N_{epoch}, \end{matrix}

(33)

where

𝒴_{m} (i) = 1

1 \leq i \leq 𝒩_{epoch}^{m}

and the node is awake in the ith epoch, and 0 otherwise.

D_{epoch} (i) = \sum_{m = 1}^{M} 𝒴_{m} (i)

is the total number of the ith epoch that the node is awake among the M trials, and

𝒩_{epoch} = \max_{m} {𝒩_{epoch}^{m}}

is the maximum number of epochs during the network lifetime. The probability that a randomly chosen awake epoch of a node happens to the ith epoch is given by

p_{a} (i) = \lim_{M \to \infty} \frac{D_{epoch} (i)}{\sum_{m = 1}^{M} N_{epoch}^{m}} = \lim_{M \to \infty} \frac{1}{M} \sum_{m = 1}^{M} p_{a} (m),

(34)

where

p_{a} (m)

is the nodes awake probability in the mth trial. Averaging (33) over the randomly chosen epoch indexing i, the expected ith epoch energy consumption except for the energy consumed by the CKN algorithm is defined as

E [E_{epoch}] ≜ \lim_{M \to \infty} \sum_{m = 1}^{M} \frac{E_{epoch}^{m} (i) Y_{m} (i)}{N_{epoch}^{m}} .

(35)

5. The Energy-Consumption-Based CKN Algorithm

We develop a new sleep scheduling algorithm to extend the network lifetime, which can still have all properties of the CKN algorithm.

A scalable distributed solution to the connected k-neighborhoods problem based on the nodes' current residual energy information is challenging for several reasons. First, a node can go to sleep assuming that there are at least k neighbors being awake to keep it k-connected. Second, the outcome of the algorithm must change over epochs so that all nodes have opportunities to sleep. Third, even though nodes decide to sleep or wake up based on their local information, the whole network must be globally connected. The aforementioned three challenges have been achieved by the CKN algorithm [1], which keep the network duty-cycled and connected k-neighborhood. Fourth, awake neighbors of any node $s_{u}$ have k-top residual. The last one makes sure the energy of the network consumed balancedly, which is the main strength that the EC-CKN algorithm has over the original CKN algorithm.

We address the challenges by proposing the EC-CKN algorithm. The pseudocode of Algorithm 1 depicts the EC-CKN algorithm, which is repeated in each epoch on each node. The algorithm takes an input parameter, k, the required minimum number of per node's awake neighbors. In EC-CKN algorithm, a node $s_{u}$ broadcasts its current residual energy information $E ran k_{u}$ (Step 1). It computes a subset $E_{u}$ of neighbors having $E rank < E ran k_{u}$ (Step 5). Before $s_{u}$ goes to sleep, it makes sure that any two nodes in $E_{u}$ are connected either directly or indirectly through the node that is in the $s_{u}$ 's 2-hop neighbors having $E rank < E ran k_{u}$ , and its neighbors have at least k neighbors from $E_{u}$ (Step 6). These requirements ensure that when a node has less than k neighbors, none of its neighbors goes to sleep, and when it has more than k neighbors, at least k neighbors decide to remain awake. Note that these requirements are easy to keep by computing locally with 2-hop neighborhood information. The current residual energy is exchanged in Steps 2 and 3.

Algorithm 1: Energy-consumption-based CKN (run the following at each node $s_{u}$ ).

Input: The least number of neighbors k

Output: Connected k-Neighborhood Network

(1) Get the current residual energy $E ran k_{u}$ ;

(2) Broadcast $E r a n k_{u}$ and receive the residual energy of its neighbors $N_{u}$ . Let $R_{u}$ be the set of the residual energy of nodes in $N_{u}$ .

(3) Broadcast $R_{u}$ and receive $R_{v}$ from each node $s_{v}$ where $s_{v} \in N_{u}$ .

(4) If $| N_{u} | < k$ or $| N_{v} | < k$ for any $s_{v} \in N_{v}$ , remain awake.

Return.

(5) Compute $E_{u} = {s_{v} | s_{v} \in N_{u} and E ran k_{v} > E ran k_{u}}$ ;

(6) Go to sleep if both the following conditions hold. Remain awake otherwise.

(i) Any two nodes in $E_{u}$ are connected either directly or indirectly through nodes that are the $s_{u}$ 's 2-hop neighbors that have $E r a n k_{v}$ larger than $E r a n k_{u}$ ;

(ii) Any node in $N_{u}$ has at least k neighbors from $E_{u}$ .

(7) Return.

6. Properties of the EC-CKN Algorithm

This section analyzes the network lifetime, the awake probability, and the energy consumption of the network under the EC-CKN algorithm.

Theorem 6.

For any $k \geq 1$ , the average network lifetime of the EC-CKN algorithm increases with the increases of the ratio of the network size N and k, $N / k$ .

Proof.

Suppose N nodes are placed uniformly at random within a deployment area such that the average number of neighbors per node is $ξ \geq 4 (k + \ln N)$ . Let $δ = (c k \ln N) / ξ$ , for constant $c > 96$ determined by the analysis. Consider executing the algorithm EC-CKN on the network, and let $E ran {k^{(i)}}^{*}$ be the residual energy of the δth largest residual energy selected by a node in the ith epoch. We claim that, w.h.p., all nodes with residual energy $< E ran {k^{(i)}}^{*}$ go to sleep. Because there are at most δ nodes with residual energy at least $E ran {k^{(i)}}^{*}$ , we have the average number of the awake nodes in each epoch is

{| EC |}_{k} \leq δ = \frac{c k \ln N}{ξ} .

(36)

And the average network lifetime under the algorithm EC-CKN can be written as

E [L_{EC}] = \frac{N T E_{0}}{{| EC |}_{k} \cdot E_{epoch} + (N - {| EC |}_{k}) \cdot E_{EC}},

(37)

where

ℰ_{EC} = ℰ_{ckn}

is the energy consumed by executing the EC-CKN algorithm, and T is the length of an epoch. In comparison with the energy consumed by the awake nodes in an epoch, the energy consumed by the sleep nodes in an epoch is considered negligible:

E [L_{EC}] \approx \frac{N T ξ E_{0}}{c k \ln N \cdot E_{epoch}} .

(38)

For the algorithm EC-CKN, a node could have four states: Init, Awake, Sleep, and Dead. Let $𝒮 = {I n i t = 0, A w a k e = 1, S l e e p = 2, D e a d = 3}$ be the set of the node's states, and $N_{s} = | 𝒮 |$ is the capacity of the states. Nodes can turn into the states Awake, and Sleep from the states Init, Awake and Sleep, respectively. And the state Dead can be only transformed from the states Awake and Sleep. Figure 4 shows the states transition graph in the algorithm EC-CKN, in which vertices are the states of nodes and the weights of edges are the transition probability between the two states in the ith epoch.

Figure 4

The Markov state transition probability graph of the EC-CKN algorithm.

Theorem 7.

Under the algorithm EC-CKN, the difference of the energy consumption between nodes $s_{u}$ and $s_{v}$ in the ith epoch is

d^{n} = {\begin{cases} T_{2} (Λ E_{r x} + Γ E_{t x}), & if n = 0, \\ T_{2} p_{u}^{a} (i - 1) (Λ E_{r x} + Γ E_{t x}), & otherwise, \end{cases}

(39)

where

Λ

and

Γ

are both the Skellam distributions and

p_{u}^{a} (i - 1)

is the average probability that a node is awake in the

(i - 1)

-th epoch.

Proof.

Let $𝒮_{u} = {𝒮_{u}^{0}, 𝒮_{u}^{1}, \dots, 𝒮_{u}^{i}, \dots}$ denote the states of $s_{u}$ in epochs, and let the chain

d : d^{0}, d^{1}, \dots, d^{i}, \dots

(40)

denote the difference between the energy consumed by nodes

s_{u}

and

s_{v}

in each epoch, where

s_{v} \in N_{u}

d^{i} = α ℰ_{v, epoch} (i) - β ℰ_{u, epoch} (i)

, where

ℰ_{u, epoch} (i)

and

ℰ_{v, epoch} (i)

are the conventional energy consumption of nodes

s_{u}

and

s_{v}

if they are awake in the ith epoch. The factors α and β depend on the state of nodes

s_{u}

and

s_{v}

. If

𝒮_{u}^{i} = 0 o r 1

α = 1

, and if

𝒮_{u}^{i} = 3

α = 0

, which is the same with β.

Suppose there are M independently and identically distributed trials. For the mth trial ( $1 \leq m \leq M$ ), the difference between the energy consumption of the two nodes in the ith epoch is

d_{m}^{i} = α E_{v, epoch}^{m} (i) - β E_{u, epoch}^{m} (i) .

(41)

The average difference of energy consumption in the ith epoch can be defined as

\begin{matrix} d^{(i)} & = \lim_{M \to \infty} \frac{T_{2}}{M} [\frac{\sum_{m = 1}^{M} [(α N_{v, r x}^{m, i} - β N_{u, r x}^{m, i}) E_{r x}]}{T_{2}} \\ + \frac{\sum_{m = 1}^{M} [(α N_{v, t x}^{m, i} - β N_{u, t x}^{m, i}) E_{t x}]}{T_{2}}], \end{matrix}

(42)

where

N_{u, r x}^{m, i}

and

N_{u, t x}^{m, i}

are the number of received bits and transmitted bits of the node

s_{u}

in the ith epoch during the mth trial.

T_{2}

is the time of the conventional data transmission time of each epoch. We discuss the difference between the energy consumption of two nodes in the following two cases.

Case 1 ( $i = 0$ ).

According to (33) and (14), we obtain

d_{(0)} = T_{2} [(λ_{v, r} - λ_{u, r}) E_{r x} + (γ_{v} - γ_{u}) E_{t x}] .

(43)

Case 2 ( $i > 0$ ).

According to (33) and (34), we obtain

d_{(i)} = T_{2} p_{u}^{a} (i - 1) [(λ_{v, r} - λ_{u, r}) E_{r x} + (γ_{v} - γ_{u}) E_{t x}],

(44)

where

p_{u}^{a} (i - 1)

is the expected probability that the node is awake in the

(i - 1)

-th epoch.

Note for

λ_{v, r}

and

λ_{u, r}

are two independent Poisson distributions,

Λ = λ_{v, r} - λ_{u, r}

is the Skellam distribution. Similarly,

Γ = γ_{v} - γ_{v}

is also the Skellam distribution.

Theorem 8.

Consider a random node $s_{u}$ , which has more than k neighbors, the probability that a node $s_{u}$ is awake in the ith epoch under the EC-CKN algorithm is

p_{a}^{i} = {\begin{cases} p_{a} (| E_{u}^{0} |), & if i = 0, \\ p_{a} (| E_{u}^{i} |), & otherwise . \end{cases}

(45)

Proof.

We introduce a new chain

D : 0, d^{0}, D^{0}, d^{1}, D^{1}, \dots, d^{i}, D^{i}, \dots,

(46)

to denote the difference between the residual energy of the two nodes

s_{u}

and

s_{v}

, where

s_{v} \in s_{u}

. Then, we obtain

D^{i} = {\begin{cases} d^{0}, & if i = 0, \\ D^{(i - 1)} + d^{0}, & otherwise . \end{cases}

(47)

Therefore, the number of elements in the set

E_{u}^{i}

| E_{u}^{i} | = | N_{u} | ϱ^{i}

, where

ϱ^{(i)} = {\begin{cases} \frac{D^{0}}{\max {d^{0}} - \min {d^{0}}} & if i = 0, \\ \frac{D^{i}}{\max {D^{i}} - \min {D^{i}}} & otherwise . \end{cases}

(48)

Theorem 9.

Under the EC-CKN algorithm, the upper bound of the network lifetime is

{\bar{L}}_{EC-CKN} = \frac{E_{0}}{\min \sum_{i} \sum_{a} σ_{i, a} E_{epoch}^{n}},

(49)

where

σ_{i, a}

is the steady-state probability that the action a is chosen when the chain is in the state i under the policy 𝒦.

Proof.

Now, we construct a Markov State Decision chain for each node $s_{u}$ :

S_{u}^{0}, a^{0}, S_{u}^{1}, a^{1}, \dots, S_{u}^{n}, a^{n}, \dots,

(50)

where

𝒮_{u}^{0} = 0

, and

𝒮_{u}^{n} \in {1,2, 3}

denotes the state in the nth epoch (

n \geq 1

), and

a^{n}

is the action under the state

𝒮_{u}^{n}

a^{n} = {\begin{cases} E_{u, epoch}^{n}, & if n = 0 or S_{u}^{n} = 1, \\ 0, & otherwise . \end{cases}

(51)

Let the policy $𝒦 = {κ_{u, i}^{n} (a)}$ denote the probability that the action a is chosen when $𝒮_{u} = i$ , which satisfies the following two conditions:

\begin{gathered} 0 \leq κ_{u, i} (a) \leq 1, \forall i, a, \\ \sum_{a} κ_{u, i} (a) = 1, \forall i . \end{gathered}

(52)

Under the policy 𝒦, the sequence of states

𝒮_{u}^{n}

constitutes a Markov chain with the transition probability

p_{u}^{n} (𝒦, i, j)

, which can be written as

\begin{matrix} p_{u}^{n} (K, i, j) & {= p}_{u} {S_{u}^{n + 1} = j | S_{u}^{n} = i} \\ = \sum_{a} p_{u}^{n} (i, j) κ_{u, i} (a) . \end{matrix}

(53)

For the policy 𝒦, let

σ_{i, a}

denote the steady-state probability that the chain is in the state i and the action a is chosen:

σ_{i, a} = \lim_{n \to \infty} P_{K} {S_{u}^{n} = i, a^{n} = a}

(54)

The vector

σ = {σ_{i, a}}

satisfies

\begin{matrix} (i) & σ_{i, a} \geq 0, \forall i, a, \\ (ii) & \sum_{i} \sum_{a} σ_{i, a} = 1, \forall i, a, \\ (iii) & \sum_{a} σ_{j, a} = \sum_{i} \sum_{a} σ_{j, a} p_{i, j}, \forall i, a, j, \end{matrix}

(55)

Equations (55)(i) and (55)(ii) are obvious, and (55)(iii) follows as the left-hand side equals the steady-state probability of being in the state j and the right-hand side is the same probability computed by conditioning on the state and action chosen one epoch earlier.

Suppose that a reward $ℛ (Y_{i}^{n}, a_{i}^{n}) = a^{n}$ is earned whenever the action $a_{i}^{n}$ is chosen in the state i in the n'th epoch. Since $ℛ (Y_{i}^{n}, a_{i}^{n})$ denotes the reward earned at the epoch n, the expected average reward per epoch under the 𝒦 policy can be written as

\begin{matrix} E [R (K)] & = \lim_{n \to \infty} \frac{\sum_{n}^{} \sum_{i \in S}^{} R (Y_{i}^{n}, a_{i}^{n})}{n} \\ = \sum_{i} \sum_{a} σ_{i, a_{i}^{n}} R (Y_{i}^{n}, a_{i}^{n}) \\ = \sum_{i} \sum_{a} σ_{i, a_{i}} a^{n} . \end{matrix}

(56)

Therefore,

𝔼 [ℛ (𝒦)]

can be interpreted as the following linear program:

\begin{matrix} \min & \sum_{i} \sum_{a} σ_{i, a} R (Y_{i}^{n}, a_{i}^{n}) \\ subject to & σ_{i, a} \geq 0, \forall i, a, \\ \sum_{i} \sum_{a} σ_{i, a} = 1, \forall i, a, \\ \sum_{a} σ_{j a} = \sum_{i} \sum_{a} σ_{i, a} p_{i, j}, \forall i, a, j, \end{matrix}

(57)

𝔼 [ℛ (𝒦)]

is a special case of the linear programm and is solved by a standard linear linear programming algorithm known as the simplex algorithm. The simplex algorithm solves the linear program by moving from an extreme point of the feasibility region to a better extreme point until the optimal is reached. So we can figure out the lower bound and upper bound of the lifetime by the linear programming (57).

Lemma 10.

Under the EC-CKN algorithm, the upper bound network lifetime is

{\underset{̲}{L}}_{EC-CKN} = \frac{E_{0}}{\max \sum_{i}^{} \sum_{a}^{} σ_{i, a} E_{epoch}^{n}},

(58)

where

σ_{i, a}

is the steady-state probability that the action a is chosen when the chain is in the state i under the policy 𝒦.

7. Simulation

Simulation Setup

In NetTopo [10], we conduct extensive simulation experiments. The studied WSN has the network size 800 × 600 m². The number of deployed sensor nodes are increased from 100 to 1000 (each time increased by 100). The value of k is changed from 1 to 10 (each time increased by 1). For every number of deployed sensor nodes, we use 100 different seeds to generate 100 different network deployment. A source node is deployed at the location of (50, 50), and a sink node is deployed at the location of (750, 550). The transmission radius for each node is 60 m.

Routing Algorithm

TPGF routing algorithm [11] is one of the earliest geographical multipath routing algorithms designed for facilitating the multimedia stream data transmission in static and always-on wireless sensor networks (WSNs). It focuses on exploring the maximum number of optimal node-disjoint routing paths in network layer in terms of minimizing the path length and the end-to-end transmission delay. TPGF routing algorithm includes two phases. Phase 1 is responsible for exploring the possible routing path. Phase 2 is responsible for optimizing the found routing path with the least number of hops. The simulation results with changed k values in this figure reflect the comparison between the original average length of paths and the optimized average length of paths.

Sleep Probability of the CKN Algorithm

The node's sleep probability has been analyzed in Section 4.1. Figure 5 describes the node's theoretic sleep probability based on the probability model that has been set up and covers the comparison between the simulation results and the theoretic value. We enlarge the some factors of the probabilistic model so that the theoretic value is greater than the simulation when $N / k > 100$ . While $N / k < 100$ , the theoretical results and simulation results approximate every much. Moreover, the same variation trend proves that our model is ponderable for nodes' sleep probability in the CKN algorithm.

Figure 5

Node's sleep probability. The theoretical results and simulation results do not match well when the network size gets bigger, such as $N = 700 1000$ . The reason is that we enlarge the probability that any two nodes in $C_{u}$ are connected either directly themselves or indirectly through $s_{u}$ 's 2-hop neighbors.

Network Lifetime Under the CKN Algorithm

Based on the node sleep probability from the probabilistic model and simulation, we can get the relative probability stretch variation curve with the epoch. Relative probability stretch is defined as a function of the expected number of epochs with k active neighbors compared to the expected number of epochs with a larger $| N_{u} |$ active neighbors. In our work, we assume that the radio dissipates $E_{elec} = 50$ nJ/bit to the transmitter or receiver circuity and $ϵ = 100$ pJ/bit/m², and the data rate is 20 kbps. In Figure 6, there is a key value of the length of the epoch time ( $M \cdot t$ ) when N and k are certain, which is the intersection of relative probability stretch and reference axis. The CKN algorithm is energy efficient if the epoch is less than the key value. Otherwise, the node will consume more energy by the CKN algorithm than it is always active.

Figure 6

Relative probability stretch varies with epoch.

Network Lifetime Comparison between the CKN Algorithm and the EC-CKN Algorithm

The network lifetime of the CKN algorithm and the EC-CKN algorithm in a WSN is represented by the number of epochs. We conduct simulation for the CKN algorithm and the EC-CKN algorithm in a WSN and compare the network lifetime under the same situation in Figures 7 and 8. Results in Figures 7(a) and 7(c) confirm that the energy consumption of the EC-CKN algorithm is better managed and balanced than the CKN algorithm. Results in Figures 7(b) and 7(d) reveal the influence of changing the value of k: decreasing the value of k in the EC-CKN algorithm can prolong the network lifetime, particularly when the network nodes are densely deployed. Figures 7(a) and 7(b) show the whole distribution and tendency varying from the different combinations between k and N (the total number of deployed nodes in the network). Correspondingly, Figures 7(c) and 7(d) have the same meaning for the EC-CKN algorithm. Figure 8 compares the network lifetime between the CKN algorithm and the EC-CKN algorithm, by conducting the two algorithms under the same scenario. And the results give a straight proof that the EC-CKN algorithm can provide longer network lifetime than the CKN algorithm.

Figure 7

The network lifetime of running the CKN algorithm and the EC-CKN algorithm, respectively. In (a), the ten lines of the lifetime results according to the CKN algorithm have a lot intersections, which means the energy consumption by the CKN algorithm in a WSN is not managed towards the energy-balancing direction. However, in (c), the ten lines of the lifetime results by the EC-CKN algorithm present smooth changing when the number of nodes and the value of k are changed and the lifetime increases when the ratio $N / k$ increases. This point clearly reflects that the energy consumption by the EC-CKN algorithm in a WSN is well managed towards the energy-balancing direction. Furthermore, simulation results in (b) and (d) also reveal that decreasing the value of k (let more nodes sleep) can definitely help to prolong the network lifetime of the EC-CKN algorithm in a WSN, but not the CKN algorithm.

Figure 8

Network lifetime comparison between the CKN algorithm and the EC-CKN algorithm. Y-axle represents the recorded number of epochs when the first node runs out of its energy.

8. Related Work

Network lifetime has been defined in various ways [12–17], and an energy-efficient mechanism may choose to maximize a certain type of network lifetime. One useful mechanism is the MAC layer power saving scheme, which reduces energy consumption by minimizing radio transceivers' idle time. SMAC [18] is an important MAC protocol designed for sensor networks, which forces sensor nodes to operate at low duty cycle by putting them into periodic sleep instead of idle listening. The timeout-MAC protocol (TMAC) improves SMAC by using an adaptive duty cycle [19]. Data-gathering MAC (DMAC) also uses an adaptive duty cycle, which provides low node-to-sink latency in convergecast communication by staggering the wake-up times of the nodes in the convergecast tree [20]. Pattern MAC (PMAC) [21] allows each sensor node determines the sleep-wake-up schedules based on its own traffic and the traffic patterns of its neighbors. BMAC [22] and XMAC [23] are two asynchronous duty-cycle-based protocols. In BMAC, each sensor node periodically wakes up to check whether there is any activity currently on the wireless channel or not. If so, the node remains active to receive a possible incoming packet. In this way, the node will receive one or more packets that are actually destined for other nodes. XMAC uses a strobed preamble to solve the overhearing problem in BMAC. A strobed preamble includes a sequence of short preambles prior to DATA transmission. Obviously, the preamble transmission of BMAC and XMAC occupies the wireless medium for a long time under the light traffic load. To solve the problem, WiseMAC [24] is proposed. WiseMAC is similar to BMAC except that senders efficiently reduce the length of the wake-up preamble by exploiting the sampling of the schedules of its neighbors.

Another common technique to minimize the energy consumption and extend the network lifetime is to put some sensors in the sleep state and put others in the active state for the sensing and communication tasks. When a sensor is in the sleep state, its processor is turned off, but a timer or some other triggering mechanism may be running to wake up the sensor. On the other hand, all the components in the sensor are turned on when it is in the active state. Therefore, the energy consumed in the sleep state is only a tiny fraction of that consumed in the active state. One complexity here is that different types of sensors may support different sets of states. For example, the μAMPS sensor has three sleep states: Monitor, Observe, and Deep Sleep [25]. A sleep scheduling mechanism allows each sensor to determine when it should switch its state and what state it will switch to. Kumar et al. adopt the randomized independent scheduling (RIS) mechanism extending network lifetime while achieving asymptotic K-coverage [26]. RIS assumes that time is divided into epochs based on a time synchronization method. At the beginning of a epoch, each sensor independently decides weather to become active with probability p or go to sleep with probability $1 - p$ . Thus, the network lifetime is increased by a factor close to $1 / p$ . Berman et al. presented a centralized and a distributed algorithm to maximize network lifetime while achieving K-coverage [27]. In the distributed algorithm, each sensor is in one of three states: active, idle, or vulnerable. In the vulnerable state, if the sensor discovers that part of its sensing area cannot be covered by any of its active or vulnerable neighbors, it immediately enters the active state. Otherwise, it enters the idle state if its sensing area can be monitored by either active neighbors or vulnerable neighbors with a higher energy level. Another distributed scheduling mechanism named lightweight deployment aware scheduling (LDAS) is proposed in [16]. Unlike the aforementioned distributed algorithm, LDAS does not ask if the sensor nodes are equipped with GPS or other devices to obtain location information. It assumes that each active node knows the number of its active neighbors. If the number of the active nodes exceeds a threshold, the node randomly selects some of its neighbors and sends tickets to them. When a node receives enough tickets from its neighbors, it may enter the sleep state after a random backoff period. Probing environment and adaptive sensing (PEAS) mechanism was designed for high-density sensor networks in a harsh environment [17]. Each node broadcasts a message with a transmission range of $t_{r}$ after sleeping for a random period. A node will go to the active state only if it receives no replies from its active neighbors. PEAS assumes that sensor nodes may fail frequently and unexpectedly, which makes synchronized sleeping algorithm infeasible. Coverage configuration protocol (CCP) is an integrated coverage and connectivity configuration protocol [4]. The protocol defines that nodes have three states: ACTIVE, LISTEN, and SLEEP. Each node is initially ACTIVE. When it receives a message, it goes to the LISTEN state and starts a random LISTEN timer. The node will go to SLEEP if it satisfies the following conditions: (i) its LISTEN timer expires; (ii) the network is still connected when it goes to SLEEP. In the SLEEP state, a node will set a random SLEEP timer. When the timer expires, it will enter the LISTEN state. PECAS (probing environment and collaborating adaptive sleeping) is an extension of PEAS. A active node in PECAS will go back to sleep after a specified period of time. It piggybacks the remaining ACTIVE time in its reply messages to its neighbors' probe message. Therefore, an active neighbor who will go to SLEEP can schedule itself to wake up before the node goes to SLEEP, which prevents the occurrence of blind spots. Adaptive self-configuring sensor networks topologies (ASCENT) is similar to PEAS, which is also designed for high-density sensor networks. However, unlike PEAS, ASCENT does not guarantee network connectivity. Low-energy adaptive clustering hierarchy (LEACH) [28] is a cluster-based protocol, which utilizes randomized rotation of cluster heads to distribute work load among the sensors. In LEACH, the lifetime of network is divided into epochs, and each epoch includes a set-up phase and a steady phase. During the set-up phase, cluster heads are selected and each sensor joins a cluster by choosing a cluster that needs the minimum communication energy. During the steady phase, each cluster head aggregates the data from the sensors in its cluster and then forwards them to the sink. To conserve energy, nonhead sensors go to sleep at all time except that they are transmitting data. E-LEACH [15] is an extension of LEACH, which adapts the cluster heads selection algorithm to the nonuniform starting energy level among the sensors and the required number of cluster heads.

9. Conclusion

When deploying real WSNs for practical applications, it is extremely important to have a good sleeping scheduling algorithm to balance sensor nodes' energy consumption and a reasonable length for an epoch towards energy saving is extremely important. In this paper, we make the following major contributions for supporting the real WSNs applications. (1) A theoretical study is given for the CKN algorithm, which formulates the lower bound of an epoch to keep the CKN algorithm feasible. (2) A new sleep scheduling algorithm, named as EC-CKN, is proposed to balance the energy consumption and prolong the network lifetime. (3) Extensive simulation work is conducted, which proved the energy consumption in the EC-CKN algorithm is well balanced.

Footnotes

Acknowledgments

This work is partially supported by Natural Science Foundation of China under Grant no. 61070181 and Natural Science Foundation of Liaoning Province under Grant no. 20102021. L. Shu's research in this paper was supported by Grant-in-Aid for Scientific Research (S)(21220002) of the Ministry of Education, Culture, Sports, Science and Technology, Japan.

References

Nath

Gibbons

P. B.

Communicating via fireflies: geographic routing on duty-cycled sensors

Proceedings of the 6th International Symposium on Information Processing in Sensor Networks (IPSN '07)

April 2007

440 449

2-s2.0-35348830482

10.1145/1236360.1236416

Hsin

C. F.

Liu

Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms

Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN '04)

April 2004

433 442

2-s2.0-3042785829

Cao

Abdelzaher

Stankovic

Towards optimal sleep scheduling in sensor networks for rare-event detection

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN '05)

April 2005

20 27

2-s2.0-33744944530

Wang

Xing

Zhang

Pless

Gill

Integrated coverage and connectivity configuration in wireless sensor networks

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenS '03)

November 2003

28 39

2-s2.0-18844371448

Sinha

Chandrakasan

Dynamic power management in wireless sensor networks

IEEE Design and Test of Computers 2001 18 2 62 74

2-s2.0-0035279599

10.1109/54.914626

Akyildiz

I. F.

Vuran

M. C.

Akan

O. B.

A cross-layer protocol for wireless sensor networks

Proceedings of the 40th Annual Conference on Information Sciences and Systems (CISS '06)

March 2006

1102 1107

2-s2.0-44049100471

10.1109/CISS.2006.286630

Heinzelman

W. R.

Chandrakasan

Balakrishnan

Energy-efficient communication protocol for wireless microsensor networks

Proceedings of the 33rd Annual Hawaii International Conference on System Siences (HICSS '00)

January 2000

223

2-s2.0-0033877788

Chen

Zhao

On the lifetime of wireless sensor networks

IEEE Communications Letters 2005 9 11 976 978

2-s2.0-28244455776

10.1109/LCOMM.2005.11010

Bettstetter

On the minimum node degree and connectivity of a wireless multihop network

Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '02)

June 2002

80 91

2-s2.0-0242696202

10.

Shu

Zhang

Chen

Wang

Hauswirth

NetTopo: beyond simulator and visualizer for wireless sensor networks

Proceedings of the 2nd International Conference on Future Generation Communication and Networking (FGCN '08)

December 2008

17 20

2-s2.0-62349142260

10.1109/FGCN.2008.18

11.

Shu

Zhou

Hauswirth

Le Phuoc

Zhang

Transmitting streaming data in wireless multimedia sensor networks with holes

Proceedings of the 6th International Conference on Mobile and Ubiquitous Multimedia (MUM '07)

December 2007

Oulu, Finland

24 33

2-s2.0-70450229717

10.1145/1329469.1329472

12.

Cerpa

Estrin

ASCENT: adaptive self-configuring sensor networks topologies

Proceedings of the IEEE Computer and Communications Societies (INFOCOM '02)

June 2002

1278 1287

2-s2.0-0036346460

13.

Deng

Han

Y. S.

Heinzelman

W. B.

Varshney

P. K.

Scheduling sleeping nodes in high density cluster-based sensor networks

Mobile Networks and Applications 2005 10 6 825 835

2-s2.0-29844453460

10.1007/s11036-005-4441-9

14.

Krishnamurthy

Stankovic

J. A.

Abdelzaher

Luo

Stoleru

Yan

Hui

Krogh

Energy-efficient surveillance system using wireless sensor networks

Proceedings of the 2nd International Conference on Mobile Systems, Applications and Services (MobiSys '04)

2004

270 283

2-s2.0-4544317953

15.

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks

IEEE Transactions on Wireless Communications 2002 1 4 660 670

2-s2.0-33646589837

10.1109/TWC.2002.804190

16.

Gao

Xiao

Lightweight networks

Mobile Networks and Applications 2005 10 6 837 852

10.1007/s11036-005-4442-8

17.

Zhong

Cheng

Zhang

PEAS: a robust energy conserving protocol for long-lived sensor networks

Proceedings of the 23th IEEE International Conference on Distributed Computing Systems (ICDCS '03)

May 2003

28 37

2-s2.0-0037630649

18.

Heidemann

Estrin

An energy-efficient MAC protocol for wireless sensor networks

Proceedings of the IEEE Computer and Communications Societies (INFOCOM '02)

June 2002

New York, NY, USA

1567 1576

2-s2.0-0036343658

19.

Van Dam

Langendoen

An adaptive energy-efficient MAC protocol for wireless sensor networks

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys '03)

November 2003

Los Angeles, Calif, USA

171 180

2-s2.0-18844402855

20.

Krishnamachari

Raghavendra

C. S.

An adaptive energy-efficient and low-latency MAC for data gathering in wireless sensor networks

Proceedings of 18th International Parallel and Distributed Processing Symposium (IPDPS '04)

April 2004

3091 3098

2-s2.0-12444253910

21.

Zheng

Radhakrishnan

Sarangan

PMAC: an adaptive energy-efficient MAC protocol for wireless sensor networks

Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS '05)

April 2005

237

2-s2.0-28444451509

22.

Polastre

Hill

Culler

Versatile low power media access for wireless sensor networks

Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys '04)

November 2004

95 107

2-s2.0-26444451023

23.

Buettner

Yee

G. V.

Anderson

Han

X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks

Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SenSys' 06)

November 2006

307 320

2-s2.0-34547480316

10.1145/1182807.1182838

24.

El-Hoiydi

Decotignie

J. D.

WiseMAC: an ultra low power MAC protocol for multi-hop wireless sensor networks

3121

Proceedings of the 1st International Workshop on Algorithm Aspects of Wireless Sensor Networks

2004

18 31 Lecture Notes in Computer Science

25.

Shih

Cho

S. H.

Ickes

Min

Sinha

Wang

Chandrakasan

Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks

Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MOBICOM '01)

July 2001

272 286

2-s2.0-0034777089

26.

Kumar

Lai

T. H.

Balogh

On k-coverage in a mostly sleeping sensor network

Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MOBICOM '04)

October 2004

144 158

2-s2.0-11244289227

27.

Berman

Calinescu

Shah

Zelikovsky

Power efficient monitoring management in sensor networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '04)

2004

2329 2334

28.

Heinzelman

W. R.

Chandrakasan

Balakrishnan

Energy-efficient communication protocol for wireless microsensor networks

Proceedings of the 33rd Annual Hawaii International Conference on System Siences (HICSS '00)

January 2000

223

2-s2.0-0033877788

29.

Sinha

Chandrakasan

Dynamic power management in wireless sensor networks

IEEE Design and Test of Computers 2001 18 2 62 74

2-s2.0-0035279599

10.1109/54.914626

An Energy-Efficient CKN Algorithm for Duty-Cycled Wireless Sensor Networks

Abstract

1. Introduction

2. Network Model

2.1. Communication Network Model

2.2. Event Generation Model

2.3. Buffer Analysis

Generated Packets

Relay Packets

2.4. Channel and Energy Consumption Model

(1) The Constant Energy Consumption

(2) The Additional Energy Consumption

(3) The Conventional Energy Consumption

2.5. Lifetime Definition

Theorem 1.

Proof.

3. A Brief Description of CKN

4. Analysis of the CKN Algorithm

Notations used in this section

4.1. Sleep Probability in the CKN Algorithm

Lemma 2.

Proof.

Theorem 3.

Proof.

4.2. Energy Consumption of the CKN Algorithm

Lemma 4.

Theorem 5.

Proof.

5. The Energy-Consumption-Based CKN Algorithm

Algorithm 1: Energy-consumption-based CKN (*run the following at each node s u *).

6. Properties of the EC-CKN Algorithm

Theorem 6.

Proof.

Theorem 7.

Proof.

Case 1 ( i = 0 ).

Case 2 ( i > 0 ).

Theorem 8.

Proof.

Theorem 9.

Proof.

Lemma 10.

7. Simulation

Simulation Setup

Routing Algorithm

Sleep Probability of the CKN Algorithm

Network Lifetime Under the CKN Algorithm

Network Lifetime Comparison between the CKN Algorithm and the EC-CKN Algorithm

8. Related Work

9. Conclusion

Footnotes

Acknowledgments

References

Algorithm 1: Energy-consumption-based CKN (run the following at each node $s_{u}$ ).

Case 1 ( $i = 0$ ).

Case 2 ( $i > 0$ ).