Sage Journals: Discover world-class research

Abstract

Although duty-cycling is a promising approach to reduce energy consumption in wireless sensor networks, sufficiently long network lifetime may not be achieved due to the hot spot problem. Moreover, a long duty cycle interval can lead to high end-to-end delay, which is not desired in delay-constrained applications. In order to address the hot spot problem and long end-to-end delay, this article proposes a novel energy-balanced node deployment algorithm for maximizing network lifetime in duty-cycled wireless sensor networks while taking into account a delay requirement. In addition, energy-balanced node deployment considers network connectivity and sensing coverage constraints, which are also important factors when wireless sensor networks are deployed. An optimization problem is first formulated where the objective function and constraints are estimated based on node distribution in the area and the network parameters. Then, a non-deterministic algorithm is proposed to derive the optimal number of nodes in each circular layer that meets given constraints and maximizes network lifetime. Numerical analysis and simulations have been conducted to validate the proposed algorithm. The results show that the proposed algorithm can achieve higher network lifetime than other schemes.

Keywords

Network lifetime node deployment delay requirement wireless sensor networks

Introduction

A wireless sensor network (WSN) consists of a number of nodes deployed in the monitored area to collect and transmit data to a sink node. Due to the development of low-cost and multi-functional sensors, WSNs have been applied to many areas, including military, surveillance missions, and agriculture, among others.^1–4 In WSNs, reducing energy consumption (i.e. prolonging network lifetime) has been attracting a lot of attention since sensors are usually provided with limited power. In this article, network lifetime is considered as the period from the time of WSN launch until the first node runs out of energy.⁵ In order to prolong network lifetime, a duty-cycling technique can be used, in which nodes become active during a wake-up period, and sleep for the rest of a duty cycle interval. Although the duty-cycling method reduces energy consumption significantly, a long duty cycle interval can cause high packet delay, which is not desired in delay-constrained applications.^1,2 Therefore, in WSNs for such applications, when duty cycling is used to lengthen network lifetime, a delay constraint should be considered, that is, packets are required to arrive at the sink within a certain time.

Moreover, network lifetime is highly affected by the hot spot phenomenon where some nodes need to transmit more packets than other nodes.⁶ Specifically, nodes closer to the sink usually forward more data and they consume more energy than others. Hence, this hot spot issue reduces network lifetime considerably and causes unbalanced energy consumption in the network, that is, some nodes still have a lot of energy when the first node dies.

In order to deal with the hot spot problem, several node deployment algorithms were studied. Node deployment strategies can be classified into two types: deterministic and non-deterministic algorithms.

The former assumed that nodes have the same capabilities, such as transmission range and initial energy budget.^7–12 Then, in order to balance energy consumption, they determine the number of nodes and positions of the nodes, and place nodes in pre-determined positions. Although deterministic deployment algorithms can control sensing coverage and network connectivity, this approach requires the exact positions of the nodes, which is costly and impractical.

To avoid pre-determined deployment, the latter (non-deterministic node deployments) can be used, in which nodes do not need to be placed at pre-determined positions. According to node distribution, we may classify non-deterministic node deployment schemes into two groups: uniform and non-uniform node distributions.

In the first group, nodes are deployed randomly with a uniform distribution throughout the whole area.^12–19 Note that since the positions of the nodes are random variables, it is important to satisfy sensing coverage and network connectivity constraints with the desired probability. However, none of those works^12–19 considered network connectivity, sensing coverage constraints, and a delay requirement. In the second group, the authors estimated node distribution in each region according to data traffic in the area in order to prolong network lifetime.^20–22 Node density in the regions can be different from each other. However, neither of those studies^20–22 considered the delay bound that is required in delay-constrained applications. For example, although Liu et al.²² considered network connectivity and sensing coverage constraints, they did not address the delay requirement. In addition, some node deployment algorithms required a large number of nodes to maximize network lifetime.^13,20

In order to address the limitations in existing algorithms, we propose a novel non-deterministic energy-balanced node deployment algorithm (EBND), which determines the appropriate number of nodes in each circular layer in order to maximize network lifetime while satisfying delay, network connectivity, and sensing coverage constraints in duty-cycled WSNs. Unlike several schemes that required a large number of nodes, EBND can determine the number of nodes in each region given total number of nodes. This brings great flexibility to our algorithm compared to existing ones.

In this article, we first formulate an optimization problem to maximize network lifetime with constraints on packets delay, network connectivity, and sensing coverage, which are estimated as a function of the number of nodes in each circular layer. Then, an algorithm is proposed to find the optimal number of nodes in each layer in order to maximize network lifetime while satisfying the constraints. Numerical analysis and extensive simulations have been conducted to validate the proposed algorithm by comparing with other node deployment schemes under different network parameters. Numerical results indicate that EBND requires a smaller number of nodes and consumes less energy than Olariu’s algorithm.¹³ Moreover, simulation results show that EBND can achieve longer network lifetime than other deployment schemes while satisfying the required constraints.

The rest of this article is organized as follows. The sections “Related work” and “System model and assumption” describe existing work and the system model, respectively. Then, the “EBND with delay, network connectivity, and sensing coverage requirements” section presents the main algorithm in detail. Numerical results and the performance study are presented in the sections “Numerical results” and “Performance study,” respectively. Finally, the section “Conclusion” concludes the article and discusses future work.

Related work

In this section, we describe several existing node deployment algorithms and then compare these schemes with ours. Node deployment schemes can be classified into deterministic^7–12 and non-deterministic.^12–22

In deterministic node deployment, the number of nodes in each region and all nodes’ positions are estimated in order to satisfy a given requirement, such as maximizing network lifespan or balancing energy consumption. The strength of this kind of deployment is network connectivity and sensing coverage can be controlled strictly. However, it is clear that the cost of this deployment is high, especially when the total number of nodes and total area size increase.

For instance, two well-known deterministic node deployments were presented: grid and tri-hexagon tiling (THT) schemes.¹² In the grid deployment method, the entire area is divided into a grid of cells where each crosspoint hosts a sensor node. In the THT scheme, the authors considered semi-regular tiling that uses triangles and hexagons in a two-dimensional plane. Nodes are placed at the vertices of the triangles or hexagons. Although the authors evaluated and compared energy consumption, k-coverage, and packets delay between these schemes, they did not consider the constraints of delay, network connectivity, and sensing coverage.

Wu et al.⁹ considered sensor nodes that are deployed in a circular area with multiple layers, and all sensors were homogeneous and used the same maximum transmission range. The authors defined sub-balanced energy consumption as a feature where nodes in all layers (except the outermost) run out of energy simultaneously. In order to achieve sub-balanced energy depletion, the number of nodes in each layer should be greater than that in the farther layer by $q$ times ( $q$ is an integer greater than 1). Because the number of nodes follows a geometric rule, this algorithm requires a lot of nodes, particularly as the area’s radius increases.

In order to achieve better balanced energy consumption and longer network lifetime than Wu’s scheme, Ferng et al.⁷ proposed three node distribution strategies. Sensor nodes that have the same transmission range are deployed in an area with multiple concentric layers. Since there is a large number of redundant nodes in inner layers, it is not necessary for nodes to turn on and to sense the environment all the time. The authors calculated the minimum number of nodes in each layer in order to fully cover the monitored area, and only those nodes are allowed to sense and transmit data to the sink at any one time, while other nodes in the layer are in sleep mode. That reduced the number of generated packets. Therefore, energy consumption for transmitting and receiving data is much reduced, and network lifetime can be prolonged.

However, both of Wu’s and Ferng’s schemes use deterministic node deployment algorithms, that is, nodes are required to be placed at exact, pre-determined positions. This is impractical, especially in a large area. Therefore, in this work, we propose a non-deterministic node deployment algorithm that does not require placing nodes at pre-determined locations. Moreover, the proposed algorithm takes into account delay, sensing coverage, and network connectivity constraints, while the above-mentioned algorithms do not.

Unlike deterministic node deployment strategies, non-deterministic deployment algorithms^13–21 do not require pre-determined placement of nodes, and most of them tried to address the problem of network lifetime maximization by adjusting the transmission range or determining node density in each area. For example, uniform random deployment¹² was presented, in which nodes are deployed randomly with a uniform distribution throughout the whole area. Although the authors compared energy consumption, coverage, and packets delay against grid and THT node deployments, they did not try to maximize network lifetime or satisfy sensing coverage, network connectivity, and delay constraints.

Olariu and Stojmenovi¹³ studied the problem of balancing energy consumption, or maximizing network lifetime in the network, by finding the appropriate transmission range for nodes in each layer. The entire area is divided into multiple concentric layers where nodes are scattered randomly with a uniform distribution. The authors formulated energy consumption of nodes in each layer as a function of the transmission range of nodes in layers along with other parameters. In order to balance energy consumption, they derived a set of transmission ranges of nodes in layers, which increases from the innermost to the outermost layer as predicted. However, since the obtained transmission range is much lower than the maximum transmission range, Olariu’s scheme requires many more nodes than other algorithms that use the maximum radio range.

Song et al.¹⁴ aimed at maximizing network lifetime by adjusting transmission ranges of nodes for each layer in the WSN. They assumed that nodes in the same layer have the same transmission range and, for a given node deployment, network lifetime of the nodes is calculated as a function of node transmission ranges and other network parameters,¹⁴ such as the number of nodes in each layer and the layer’s width. Therefore, among a list of possible transmission ranges, they can obtain a set of transmission ranges that achieves maximal network lifetime. Since searching for an optimal set of transmission ranges is non-deterministic polynomial-time (NP)-hard, they proposed two heuristic algorithms to obtain a nearly optimal list with lower complexity. However, requirements of delay, sensing coverage, and network connectivity were not considered in their work.

Demertzis and Oikonomou²⁰ proposed a non-uniform node distribution in order to address energy hole problem and to prolong network lifetime. The authors used two kinds of sensor node: active and dormant. While active nodes sense and transmit data, dormant nodes work as energy reservoirs, that is, when an active node exhausts its energy, a nearby dormant node becomes active. According to traffic load, the density of dormant nodes is determined in each region. Then, active nodes are deployed randomly with a uniform distribution through the whole area, while dormant nodes are scattered with a higher node density for closer regions to the sink. However, this algorithm requires a large number of nodes, for example, the number of dormant nodes is roughly 10 times higher than active nodes. Compared to EBND, some of the non-deterministic algorithms required a large number of nodes.^13,20

There were several studies on maximizing network lifetime under different quality of services (QoS) constraints. However, QoS constraints in EBND differ from existing work.^23–25 Specifically, in Xiao et al.,²³ each node is randomly assigned into one of $k$ disjoint subsets where at any time, sensor nodes of only one set are active while others are in sleep mode. In order to maximize network lifetime, the authors aimed to obtain the maximum value of $k$ while considering constraints of network coverage and delay. Meanwhile, EBND derives the appropriate number of nodes in each layer to maximize network lifetime with the requirements of network connectivity, sensing coverage, and delay. In Du et al.,²⁴ authors considered a sleep/awake mechanism for the sensing process to prolong network lifetime under the constraint of only network connectivity. In Yao et al.,²⁵ a data collection protocol was studied in order to maximize network lifetime with the requirement of only the packets delay.

The concentric layers infrastructure was discussed in existing studies of maximizing network lifetime in WSNs^13–15 in which a number of sensors are deployed in an area with the sink at the center of that region. Sensors are classified into concentric layers according to their distances to the sink. Note that although the concentric rings feature is used in this work, EBND considers WSNs with non-uniform node deployment while uniform node distribution was assumed in literatures.^13–15 Moreover, given the assumption that nodes are provided with the same transmission range, EBND determines the number of nodes in each layer in order to maximize network lifetime under desired constraints. Whereas, Olariu and Stojmenovic,¹³ Song et al.,¹⁴ and Tran-Quang and Miyoshi¹⁵ considered nodes with the adjustable communication range in order to lengthen network lifetime in WSNs.

System model and assumption

In this work, we assume that nodes are deployed in a circular area with the sink node at the center, and each node knows its position. Nodes are assumed to have the same transmission range, $R$ , and the same sensing range, $r$ . The area is divided into circular layers.^13,22,26 The total number of nodes is $N$ . EBND determines the number of nodes in each circular layer ${N_{i}}$ $(1 \leq i \leq k)$ in order to maximize network lifetime, then $N_{i}$ nodes are deployed randomly with a uniform distribution throughout layer $i$ . Note that each layer may have different node distributions in order to maximize network lifetime. Let $c$ denote the width of layer $j$ $(1 < j \leq k)$ , and $l$ is defined as the radius of the entire area. The innermost layer is the circular area around the sink with radius $R$ . In other words, node $A$ belongs to layer 1 if the distance between node $A$ and the sink node, $d_{A}$ , satisfies $0 \leq d_{A} \leq R$ , meaning it can transmit packets directly to the sink. Node $A$ belongs to layer $j$ $(1 < j \leq k)$ if $d_{A}$ satisfies

R + c (j - 2) < d_{A} \leq R + c (j - 1)

(1)

where $0 \leq d_{A} \leq l$ . The total number of layers, denoted by $k$ , is calculated as follows

k = ⌈ \frac{l - R}{c} ⌉ + 1

(2)

Let $R_{j}$ denote the radius of layer $j$ , and $R_{j}$ can be calculated as follows

R_{j} = {\begin{matrix} R & if j = 1 \\ R + c (j - 1) & if 2 \leq j \leq k \end{matrix}

(3)

Define $A_{j}$ as the area of layer $j$ bounded by the radius of layers $j$ and $(j - 1)$ . The size of $A_{j}$ can be determined as follows

A_{j} = {\begin{matrix} π R^{2} & if j = 1 \\ π (R_{j}^{2} - R_{j - 1}^{2}) & if 2 \leq j \leq k \end{matrix}

(4)

Let random variable $S_{j}$ denote the forwarding area of nodes in layer $j$ . The forwarding area, as shown in Figure 1, of a sender in layer $j$ is defined as the intersection area between the transmission region of the sender and the circular area with radius $R_{j - 1}$ .

Figure 1.

Network model.

Sensors use a duty-cycling strategy, that is, nodes turn on the radio during an active period and turn it off for the rest of duty cycle interval $T$ . In this article, a routing algorithm, called layer-based forwarding (LF) algorithm, which is extended from Dao et al.²⁷ is used. Unlike Dao et al.,²⁷ LF uses neighboring nodes scheduling information. All sensor nodes randomly select the wake-up time during the duty cycle interval by using the same pseudo-random algorithm. Specifically, nodes exchange their seed values and IDs at the beginning of network formation. Using exchanged seed values, each node learns the schedules of its neighboring nodes.

Let potential forwarders of a node represent all neighboring nodes belonging to the forwarding area. When it has a data packet, the sender waits until a node among all potential forwarders wakes up and forwards the packet to the node that wakes up earliest. Since a node is able to predict the schedules of its neighbors, the sender should be in sleep mode until the next hop becomes active. This strategy can help nodes reduce energy consumption by turning off the radio when unnecessary.

In this article, the energy model is the one referred in Heinzelman et al.²⁸ On the transmitter side, there are transmission electronics and a transmission amplifier, while the receiver side consists of reception electronics. Transmission power $p_{t}$ and reception power $p_{r}$ can be calculated as follows

\begin{matrix} p_{t} = (β_{1} + β_{2} d^{α}) L \\ p_{r} = β_{3} L \end{matrix}

(5)

where $α$ is the power coefficient, $β_{1} L$ is transmission electronics energy consumption, $β_{2} d^{α} L$ is energy consumed by the transmission amplifier, and $β_{3} L$ is reception electronics energy consumption. $L$ and $d$ denote the data rate of each node (bps) and the transmission range, respectively.

EBND with delay, network connectivity, and sensing coverage requirements

In this section, we study an optimization problem with the objective of maximizing network lifetime while satisfying the delay, network connectivity, and sensing coverage requirements given the number of nodes. First, the problem definition is presented. Then, we describe the objective function and constraints as a function of the number of nodes in layers. Finally, the full problem formulation and the proposed algorithm are discussed.

Problem definition

We define the critical node as the node that consumes energy the most in the network. It is not known a priori which node in the network will be the critical node. The layer to which the critical node belongs is called the critical layer.

Then, the problem is to minimize the energy consumption of the critical node (i.e. maximize network lifetime) while satisfying the required delay, network connectivity, and sensing coverage given the total number of nodes.

Let $e_{cn}$ denote the energy consumption of the critical node. Recall that there are $N$ nodes in the network. $X_{j}$ is defined as the expected packet delay of node $j$ $(1 \leq j \leq N)$ and $ξ$ denotes the delay requirement. $γ^{c}$ and $γ^{s}$ represent the required connectivity and sensing coverage ratios, respectively. $γ^{c}$ is the number of nodes with at least one path to the sink divided by the total number of nodes. $γ^{s}$ is the ratio of the covered area to the entire area.

Also, let $P_{i}^{c}$ denote the connectivity probability of a node in layer $i$ , which represents the probability that a node in layer $i$ has at least one path to the sink node. In addition, the sensing coverage probability of a position is defined to be the probability that the position is covered by at least one sensor node. $P_{i}^{s}$ denotes the sensing coverage probability of an arbitrary position in layer $i$ .

Then, the optimization problem can be defined as follows

minimize e_{cn}

(6)

subject to

X_{j} \leq ξ, j = 1, 2, . . ., N

(7)

P_{i}^{c} \geq γ^{c}, i = 1, 2, . . ., k

(8)

P_{i}^{s} \geq γ^{s}, i = 1, 2, . . ., k

(9)

The objective function implies that we maximize network lifetime by minimizing the energy consumption of the critical node. Recall that it is not known which node among $N$ nodes will become the critical node. We will discuss in the next subsection how to formulate the objective function under the given circumstance where any arbitrary node can become the critical node.

Equation (7) shows the expected delay of all nodes in the network should be less than the delay constraint. In addition, constraints of network connectivity and sensing coverage are presented in equations (8) and (9), respectively. In the next subsections, the objective function and constraints are discussed in detail.

Energy consumption

We first present the total energy consumption of nodes in layer $i$ as a function of the number of nodes in layers. Let $e_{tx}$ and $e_{rx}$ denote the transmission and reception energy for a packet. $E_{i}$ is defined as energy consumption for transmission and reception of all nodes in layer $i$ in cases where each node generates and transmits only one packet. Define $N_{i}$ and $k$ as the number of nodes in layer $i$ and the total number of layers, respectively. Therefore, $E_{i}$ can be calculated as follows

E_{i} = {\begin{matrix} N_{i} e_{tx} if i = k \\ N_{i} e_{tx} + \sum_{j = i + 1}^{j = k} N_{j} (e_{tx} + e_{rx}) if 1 \leq i \leq k - 1 \end{matrix}

(10)

where $N_{i} e_{tx}$ is energy spent by all nodes in layer $i$ to transmit packets they generated, and $\sum_{j = i + 1}^{j = k} N_{j} (e_{tx} + e_{rx})$ is the energy that all nodes in layer $i$ consume to receive and forward data packets from the outer layers. According to the routing algorithm, nodes in the outermost layer only transmit their own packets, but do not forward packets from neighboring nodes. Therefore, the energy consumption of nodes in layer $k$ can be expressed in the first line of equation (10).

Note that since nodes in the same layer are deployed randomly using the uniform distribution and they randomly choose the wake-up time during the node interval, nodes in the same layer can be considered to have the same probability of being selected as the next forwarder. Therefore, by the law of large numbers,²⁹ the remaining energy of nodes in a layer will have the same value when the network operation time is sufficiently long.

Therefore, in order to minimize the energy consumption of the critical node, we minimize the energy consumption of an arbitrary node in the critical layer, and the objective function can be rewritten to address the problem of minimizing the energy consumption of an arbitrary node in the critical layer.

Let $e_{i} = E_{i} / N_{i}$ denote the energy consumption of an arbitrary node in layer $i$ and can be calculated as follows

e_{i} = {\begin{matrix} e_{tx} if i = k \\ e_{tx} + \frac{\sum_{j = i + 1}^{j = k} N_{j}}{N_{i}} (e_{tx} + e_{rx}) if 1 \leq i \leq k - 1 \end{matrix}

(11)

Then, by the definition of the critical layer, the objective function is equivalent to minimizing $max_{i} (e_{i})$ with $1 \leq i \leq k$ . Because $(\sum_{j = i + 1}^{j = k} N_{j}) / N_{i} > 0$ , a node in layer $k$ will consume the smallest amount of energy among nodes in the network. Then, the objective function in equation (6) can be rewritten as follows

minimize \max_{i} (\frac{\sum_{j = i + 1}^{j = k} N_{j}}{N_{i}}), i = 1, 2, . . ., k - 1

(12)

Delay constraint

Note that the expected delay of packets from nodes in the outermost layer is longer than the delay from the inner layers. If nodes in layer $k$ meet the delay constraint, nodes in the inner layers also satisfy the delay requirement. Therefore, in this article, the desired delay bound for nodes in the outermost layer is considered. Recall that $ξ$ denotes the delay requirement. Let $μ$ define the expected end-to-end (E2E) delay of packets in layer $k$ .

Expected latency $μ$ should be shorter than or equal to given delay requirement $ξ$ . Since $μ$ is the expected E2E delay of a packet in layer $k$ , it can be expressed as follows: $μ = μ_{2} + \dots + μ_{k - 1} + μ_{k}$ where $μ_{j}$ is the expected one-hop delay of a node in layer $j$ . Note that $μ_{1} = 0$ , that is, nodes in the first layer can transmit data packet to the sink immediately, because the sink is assumed to be active all the time. One-hop delay includes processing time and waiting time. In this manuscript, waiting time is from the time a node has a packet (its own packet or a packet received from a neighboring node) to the time a forwarder wakes up. However, processing time can be ignored, since it is much lower than the waiting time until the next-hop node wakes up. Therefore, one-hop delay can be estimated as the waiting time until the next-hop node becomes active. Let $T$ denote the duty cycle interval of nodes in the network. Now, we will estimate the expected one-hop delay as a function of the network parameters, such as the number of nodes in each layer, the duty cycle interval, and the area radius. Then, the expected delay of nodes in layer $k$ can be approximated using one-hop delays.

We consider a node in layer $j$ that has $m_{j}$ potential forwarder(s). Let random variable $D_{i'}$ denote the wake-up time of the $i' th$ node among the $m_{j}$ potential forwarder(s) $(1 \leq i' \leq m_{j})$ . Since sensor nodes randomly and independently choose a wake-up time, $D_{i'}$ are independent and identical random variables. The distribution function of $D_{i'}$ is $F_{D_{i'}} (d_{i'}) = P (D_{i'} \leq d_{i'}) = d_{i'} / T$ if $0 \leq d_{i'} \leq T$ . Let random variable $Y_{j}$ denote the one-hop delay of a packet at layer $j$ , then $Y_{j}$ will be defined as follows: $Y_{j} = \min (D_{1}, D_{2}, . . ., D_{m_{j}})$ . Let $P (Y_{j} < y_{j} | m_{j})$ define the probability that one-hop latency is shorter than $y_{j}$ given $m_{j}$ , that is, it is the probability that at least one $D_{i'} < y_{j}$ exists if the node has $m_{j}$ potential forwarder(s). Then, the cumulative distribution function $F (y_{j} | m_{j})$ of $y_{j}$ given $m_{j}$ can be expressed as follows

\begin{matrix} F (y_{j} | m_{j}) = 1 - probability that all D_{i'} > y_{j} \\ = 1 - Π_{i' = 1}^{m_{j}} (1 - F_{D_{i'}} (y_{j})) \\ = 1 - {(1 - \frac{y_{j}}{T})}^{m_{j}} \end{matrix}

(13)

Now, distribution function $F (y_{j})$ can be obtained using Bayes’ theorem, that is

\begin{array}{l} F (y_{j}) = \sum_{m_{j} = 0}^{N - 1} P_{j} (m_{j}) F (y_{j} | m_{j}) \\ = \sum_{m_{j} = 0}^{N - 1} P_{j} (m_{j}) [1 - {(1 - \frac{y_{j}}{T})}^{m_{j}}] \end{array}

(14)

where $P_{j} (m_{j})$ is the probability that a node in layer $j$ has $m_{j}$ potential forwarders in the forwarding area. Then, probability density function $f (y_{j})$ can be obtained by computing a derivative of distribution function $F (y_{j})$

\begin{matrix} f (y_{j}) = \frac{dF (y_{j})}{d y_{j}} \\ = \sum_{m_{j} = 1}^{N - 1} P_{j} (m_{j}) \frac{m_{j}}{T} {(1 - \frac{y_{j}}{T})}^{m_{j} - 1} \end{matrix}

(15)

Then, the expected one-hop latency of nodes in layer $j$ can be calculated as follows²⁷

\begin{matrix} μ_{j} = \int_{0}^{T} y_{j} f (y_{j}) d y_{j} \\ = \sum_{m = 1}^{N - 1} P_{j} (m) \frac{T}{m + 1} = E [\frac{T}{m_{j} + 1}] \end{matrix}

(16)

where $m_{j}$ is the number of potential forwarders of a node in layer $j$ .

After applying a Taylor expansion for function $1 / X$ around $E [X]$ , we can obtain the expectation of the inverse function as follows: E[1/X $\approx E] [(1 / E [X]$ ) $- (1 / E [X]^{2}) (X - E [X]) + (1 / E [X]^{3}) (X - E [X {])}^{2}] = (1 / E$ $(1 / E [X]) + (1 / E {[X]}^{3}) Var [X]$ . Now, using the Taylor expansion, equation (16) can be written as follows: $μ_{j} = E [1 / m_{j} + 1] \approx (1 / E [m_{j} + 1]) + (1 / E [m_{j} + 1]^{3}) Var [m_{j} + 1]$ . In our model, the second term $((1 / E [m_{j} + 1]^{3}) Var [m_{j} + 1])$ is quite small compared to the first term $(1 / E [m_{j} + 1])$ , for example, the first term is 2.81 s and the second term is 0.21 s, that is, the first term is 13.38 times higher than the second. Then, we can ignore the second expression, and equation (16) can be estimated relatively, as follows

μ_{j} = E [\frac{T}{m_{j} + 1}] \approx \frac{T}{E [m_{j} + 1]} = \frac{T}{E [m_{j}] + 1}

(17)

Define $ρ_{j}$ as the node density in circular layer $j$ . The expected number of potential forwarders of a node in layer $j$ can be expressed as $E [m_{j}] = ρ_{j - 1}$ $E [S_{j}] = (N_{j - 1} / A_{j - 1}) E [S_{j}]$ where forwarding area $S_{j}$ is defined in the section “System model and assumption.” Therefore, expected one-hop delay $μ_{j}$ can be rewritten in relation to the number of nodes, $N_{j - 1}$ , in layer $j - 1$ as follows: $μ_{j} \approx T / E [m_{j}] + 1 = T / (N_{j - 1} / A_{j - 1}) E [S_{j}] + 1$ .

Define $α_{j} = E [S_{j + 1}] / A_{j}$ , and the delay constraint in equation (7) can be rewritten as follows

\begin{array}{l} \frac{T}{\frac{N_{k - 1}}{A_{k - 1}} E [S_{k}] + 1} + \frac{T}{\frac{N_{k - 2}}{A_{k - 2}} E [S_{k - 1}] + 1} + \dots + \frac{T}{\frac{N_{1}}{A_{1}} E [S_{2}] + 1} \leq ξ or, \\ \frac{T}{α_{k - 1} N_{k - 1} + 1} + \frac{T}{α_{k - 2} N_{k - 2} + 1} + \dots + \frac{T}{α_{1} N_{1} + 1} \leq ξ \end{array}

(18)

where the $j th$ layer’s area, $A_{j}$ , is calculated in equation (4).

Network connectivity and sensing coverage

In WSNs, network connectivity and sensing coverage should be guaranteed with a desired probability. In this subsection, we estimate the minimum number of nodes, or, the minimum node density, that satisfies both network connectivity and sensing coverage constraints. Node density, $ρ$ , is defined as the ratio of the number of nodes to the size of the monitored area.

First of all, we take into account the required network connectivity that is presented in equation (8). Recall that $P_{i}^{c}$ denotes the network connectivity probability of a node in layer $i$ and $γ^{c}$ is the desired network connectivity ratio of nodes (e.g. $γ^{c} = 0.99$ ). We consider network connectivity for nodes from layer 2 to layer $k$ since nodes in the innermost layer are always connected to the sink. Let $p_{j}^{f}$ denote the probability that a node in layer $j$ has at least one potential forwarder in the forwarding area. The probability that there is no node in forwarding area $S_{j}$ is $e^{- ρ S_{j}}$ , so $p_{j}^{f} = 1 - e^{- ρ_{j - 1} S_{j}}$ where $ρ_{j}$ is node density in layer $j$ . The probability that a node in layer $i$ has at least one path to the sink, $P_{i}^{c}$ , can be expressed as follows

P_{i}^{c} = Π_{j = 2}^{i} p_{j}^{f} = Π_{j = 2}^{i} (1 - e^{- ρ_{j - 1} S_{j}})

(19)

Note that if nodes in the outermost layer satisfy the required network connectivity, nodes in other layers also satisfy this constraint. Hence, the sufficient condition to achieve the network connectivity requirement can be written as follows

P_{k}^{c} = Π_{j = 2}^{k} p_{j}^{f} \geq γ^{c}

(20)

From equation (20), since $p_{j}^{f}$ cannot exceed 1, the necessary condition to satisfy the network connectivity requirement is as follows

\forall p_{j}^{f} \geq γ^{c}, j = 2, 3, . . ., k

(21)

Let $ρ_{i}^{c}$ denote the minimum node density in layer $i$ $(1 \leq i \leq k - 1)$ that meets the above necessary condition for nodes in further layer $i + 1$ , so $ρ_{i}^{c}$ can be estimated as follows

ρ_{i}^{c} = \min (ρ) s . t . 1 - e^{- ρ S_{i + 1}} \geq γ^{c}

(22)

The necessary condition is used to narrow the range of number of nodes in each layer. Note that nodes in the outermost layer do not relay data packets, so there is no required node density for the outermost layer, that is, $ρ_{k}^{c} = 0$ .

Second, we consider the required sensing coverage that is described in equation (9). Recall that $r$ and $P_{i}^{s}$ denote the sensing range and the sensing coverage probability of layer $i$ , respectively. The probability that point $A$ is covered by at least one node equals the probability that there is at least one node in the circular area centered at $A$ with radius $r$ . We define $S$ as the sensing area of a node, that is, $S = π r^{2}$ . Since nodes are deployed randomly with a uniform distribution in each layer, the number of nodes scattered inside the sensing range of point $A$ follows a Poisson distribution with mean $ρ S$ . Therefore, the probability that there is no node in the sensing area of a node is $e^{- ρ S}$ , and $P_{i}^{s}$ can be expressed as follows

P_{i}^{s} = 1 - e^{- ρ S}

(23)

Recall that $γ^{s}$ denotes the required sensing coverage ratio (e.g. $γ^{s} = 0.99$ ). $ρ_{i}^{s}$ is defined as the minimum node density to meet the sensing coverage constraint of layer $i$ . Then, $ρ_{i}^{s}$ can be determined as follows

ρ_{i}^{s} = \min (ρ) s . t . 1 - e^{- ρ S} \geq γ^{s}

(24)

Finally, we determine the node density threshold in circular layer $i$ , that is denoted by $ρ_{i}^{th}$ , in order to meet both the required network connectivity and sensing coverage constraints, that is, $ρ_{i}^{th} = max (ρ_{i}^{c}, ρ_{i}^{s})$ . Hence, $ρ_{i}$ (node density in layer $i$ ) should be greater than or equal to $ρ_{i}^{th}$ , that is, $ρ_{i} \geq ρ_{i}^{th}, i = 1, 2, . . ., k$ . Since $ρ_{i} = N_{i} / A_{i}$ , these constraints can be formulated in relation to the number of nodes in each layer, $N_{i}$ , as follows

\frac{N_{i}}{A_{i}} \geq ρ_{i}^{th} = max (ρ_{i}^{c}, ρ_{i}^{s}), i = 1, 2, . . ., k

(25)

Recall that $ρ_{i}^{c}$ is the minimum node density in layer $i$ that meets the necessary condition for the connectivity requirement. Therefore, in order to fully satisfy the connectivity constraint, we need to consider the sufficient condition in equation (20). By substituting $ρ_{j} = N_{j} / A_{j}$ into equations (19) and (20), the sufficient condition for the connectivity constraint can be rewritten as follows

Π_{j = 2}^{k} (1 - e^{- \frac{N_{j - 1}}{A_{j - 1}} S_{j}}) \geq γ^{c}

(26)

Problem formulation

Finally, using equations (12), (18), (25), and (26), the problem can be formulated as follows

minimize \max_{i} (\frac{\sum_{j = i + 1}^{j = k} N_{j}}{N_{i}}), i = 1, 2, . . ., k - 1

(27)

subject to

\frac{T}{α_{k - 1} N_{k - 1} + 1} + \frac{T}{α_{k - 2} N_{k - 2} + 1} + \dots + \frac{T}{α_{1} N_{1} + 1} \leq ξ

(28)

\frac{N_{i}}{A_{i}} \geq ρ_{i}^{th} = max (ρ_{i}^{c}, ρ_{i}^{s}), i = 1, 2, . . ., k

(29)

Π_{j = 2}^{k} (1 - e^{- \frac{N_{j - 1}}{A_{j - 1}} S_{j}}) \geq γ^{c}

(30)

\sum_{i = 1}^{k} N_{i} = N

(31)

Equation (27) implies that the energy consumption of the critical node is minimized. Recall that the energy consumption of an arbitrary node in layer $i$ can be considered to be proportional to $(\sum_{j = i + 1}^{j = k} N_{j}) / N_{i}$ . Since the critical node consumes the most energy in the network, minimizing the energy spent by the critical node is equivalent to maximizing network lifetime. Therefore, the objective function can be derived as shown in equation (27). Furthermore, we can rewrite the objective function as follows

minimize Y s . t . \forall e_{i} \leq Y, i = 1, 2, . . ., k

(32)

where $e_{i}$ denotes the energy consumption of a node in layer $i$ . Equation (28) presents the delay requirement of a node in the network. The network connectivity and sensing coverage constraints are formulated in equations (29) and (30). Finally, equation (31) states that the sum of the number of nodes in each layer is equal to the given number of nodes.

Algorithm

In order to solve the optimization problem, all feasible cases are examined. The algorithm works as follows:

Set the optimal number of nodes in each circular layer, $optN [k]$ , to empty, and set minimum energy consumption $Y^{\min}$ to infinite. Calculate node density threshold $ρ_{i}^{th}$ , then the minimum number of nodes and the maximum number of nodes in layer $i$ are estimated, respectively, as $N_{i}^{\min} = A_{i} ρ_{i}^{th}$ and $N_{i}^{\max} = N - \sum_{j = 1, j \neq i}^{j = k} N_{j}^{\min}$ .

For each feasible set of $curN [k] = {N_{1}, N_{2}, . . ., N_{k}}$ that satisfies $N_{i}^{\min} \leq N_{i} \leq N_{i}^{\max}$ $(1 \leq i \leq k)$ and the sum of number of the nodes in all layers equals the given number of nodes, $\sum_{i = 1}^{k} N_{i} = N$ , check whether expected packet delay $μ$ and the sufficient condition for the required connectivity meet the given constraints.

Among the sets of $curN [k]$ that meet the delay requirement, find $optN [k]$ that leads to the minimum value of $Y$ .

The formal algorithm is presented in Algorithm 1. In order to determine the time complexity of the proposed algorithm, first, we obtain the number of feasible cases to deploy $N$ nodes into $k$ layers. Recall that $N_{i}^{\min}$ denotes the minimum number of nodes in layer $i$ in order to satisfy the required network connectivity and sensing coverage, that is, layer $i$ needs at least $N_{i}^{\min}$ nodes. Let $m$ define the number of remaining nodes, that is, $m = N - \sum_{i = 1}^{k} N_{i}^{\min}$ . Hence, the proposed algorithm is equivalent to the problem of deploying $m$ nodes into $k$ layers. This problem is actually the same as putting $k - 1$ vertical lines among $m + k - 1$ possible positions. The number of feasible cases is $(\begin{matrix} m + k - 1 \\ k - 1 \end{matrix})$ , that is, $(Π_{i = 1}^{k - 1} (m + i)) / (k - 1)!$ , and the highest order of this formula is $m^{k - 1} / (k - 1)!$ . Therefore, the time complexity of EBND node deployment algorithm is $O (m^{k - 1} / (k - 1)!)$ , where $m = N - \sum_{i = 1}^{k} N_{i}^{\min}$ .

Algorithm 1. Algorithm for finding the solution.
Input: $R, c, k, N, T, ξ, r, γ^{c}, γ^{s}$ $R$ : The transmission range $c$ : The layer width $k$ : The number of layers $N$ : The total number of nodes $T$ : The duty cycle interval $ξ$ : The delay bound $r$ : The sensing range $γ^{c}$ : The required network connectivity $γ^{s}$ : The required sensing coverageOutput: $optN [k] = {N_{1}, N_{2}, . . ., N_{k}}$ Initialize $Y^{\min} = \infty$ , $optN = {\emptyset}$ Calculate $A_{i}, ρ_{i}^{c}, ρ_{i}^{s}$ $(1 \leq i \leq k)$ , $ρ_{i}^{th} = max (ρ_{i}^{c}, ρ_{i}^{s})$ , $N_{i}^{\min} = ⌈ A_{i} ρ_{i}^{th} ⌉$ , $N_{i}^{\max} = N - \sum_{j = 1, j \neq i}^{j = k} N_{j}^{\min}$ for each $curN [k] = {N_{1}, N_{2}, . . ., N_{k}} s . t . N_{i}^{\min} \leq N_{i} \leq N_{i}^{\max}$ $and \sum_{i = 1}^{K} N_{i} = N$ do Calculate $μ$ if $μ \leq ξ$ and $Π_{j = 2}^{k} (1 - e^{- \frac{N_{j - 1}}{A_{j - 1}} S_{j}}) \geq γ^{c}$ then $tmpY = \max_{i} (e_{i})$ If $tmpY < Y^{\min}$ then $Y^{\min} = tmpY$ , $optN = curN$ end endendreturn $optN [k]$ .

Algorithm 1. Algorithm for finding the solution.

Input:

R, c, k, N, T, ξ, r, γ^{c}, γ^{s}

R

: The transmission range

c

: The layer width

k

: The number of layers

N

: The total number of nodes

T

: The duty cycle interval

ξ

: The delay bound

r

: The sensing range

γ^{c}

: The required network connectivity

γ^{s}

: The required sensing coverageOutput:

optN [k] = {N_{1}, N_{2}, . . ., N_{k}}

Initialize

Y^{\min} = \infty

optN = {\emptyset}

Calculate

A_{i}, ρ_{i}^{c}, ρ_{i}^{s}

(1 \leq i \leq k)

ρ_{i}^{th} = max (ρ_{i}^{c}, ρ_{i}^{s})

N_{i}^{\min} = ⌈ A_{i} ρ_{i}^{th} ⌉

N_{i}^{\max} = N - \sum_{j = 1, j \neq i}^{j = k} N_{j}^{\min}

for each

curN [k] = {N_{1}, N_{2}, . . ., N_{k}} s . t . N_{i}^{\min} \leq N_{i} \leq N_{i}^{\max}

and \sum_{i = 1}^{K} N_{i} = N

do Calculate

μ

μ \leq ξ

and

Π_{j = 2}^{k} (1 - e^{- \frac{N_{j - 1}}{A_{j - 1}} S_{j}}) \geq γ^{c}

then

tmpY = \max_{i} (e_{i})

tmpY < Y^{\min}

then

Y^{\min} = tmpY

optN = curN

end endendreturn

optN [k]

Numerical results

In this section, we compare EBND with Olariu’s scheme.¹³ MATLAB was used to validate these algorithms. The required number of nodes and the total energy consumption of all nodes in the network are selected as performance metrics. We first briefly summarize Olariu’s scheme. Then, we present the network parameters and how to calculate energy consumption. Finally, the obtained results with different network parameters are analyzed.

In Olariu’s scheme, the transmission range of a node in layer $i$ is the same as the width of layer $i$ . In order to achieve balanced energy consumption, the authors derive the transmission range of nodes in each layer according to the given network parameters. However, the obtained transmission radius of nodes in inner layers is much smaller than the maximum transmission radius, which reduces network connectivity. To avoid the connectivity issue, Olariu’s scheme requires a large number of nodes.

The communication energy parameters ( $β_{1}, β_{2}$ , and $β_{3}$ ) are referred to as follows²⁸

\begin{matrix} β_{1} = 50 \times 10^{- 9} J / bit \\ β_{2} = 10 \times 10^{- 12} J / bit / m^{2} (when α = 2) \\ or β_{2} = 0.0013 \times 10^{- 12} J / bit / m^{4} (when α = 4) \\ β_{3} = 50 \times 10^{- 9} J / bit \end{matrix}

(33)

where $α$ is the power coefficient. Recall that $N$ is the number of nodes in the network. Let $a$ denote the number of packets generated by each node during the simulation period; $t_{p}$ and $t_{sim}$ are defined as packet transmission time and simulation time, respectively; $λ$ is defined as duty-cycling rate; and $p_{tx}$ , $p_{rx}$ , and $p_{sleep}$ are power consumption for transmission of one data packet, reception of one data packet, and sleep mode, respectively. Let $n_{tx}$ and $n_{rx}$ denote the total number of packet transmissions and receptions, respectively, when each node generates only one packet. Then, $n_{tx}$ and $n_{rx}$ can be calculated based on the number of nodes, $N_{i}$ , in layer $i$ as follows: $n_{tx} = Σ_{i = 1}^{k} i N_{i}$ and $n_{rx} = Σ_{i = 1}^{k} (i - 1) N_{i}$ .

The total energy consumption in the network can be estimated as follows

\begin{matrix} E = a t_{p} (n_{tx} p_{tx} + n_{rx} p_{rx}) + (1 - λ) t_{sim} N p_{sleep} \\ + (λ t_{sim} N - a t_{p} (n_{tx} + n_{rx})) p_{idle} \end{matrix}

(34)

where $a t_{p} (n_{tx} p_{tx} + n_{rx} p_{rx})$ is transmission and reception energy, $(1 - λ) t_{sim} N p_{sleep}$ is the energy consumption of all nodes in sleep mode, and $(λ t_{sim} N - a t_{p} (n_{tx} + n_{rx})) p_{idle}$ is the energy consumption of all nodes in the idle mode.

In this section, the transmission range and sensing range are set to 30 and 10 m, respectively. The area radius changes from 60 to 100 m. The network connectivity requirement, $γ^{c}$ , is {0.8, 0.9, 0.99} and the required sensing coverage ratio, $γ^{s}$ , is 0.5. In order to witness the effect of the required network connectivity ratio on network performance, the small value of $γ^{s}$ was used. Duty-cycling rate, $λ$ , is 3%. Each node generates 100 packets during the simulation period that lasts for 7200 s.

The difference between EBND and Olariu’s scheme is that instead of using a random node deployment with a uniform distribution, EBND determines the appropriate number of nodes $N_{i}$ in each layer to maximize network lifetime while satisfying the constraints, then deploys $N_{i}$ nodes in layer $i$ randomly with a uniform distribution. Moreover, in EBND, the maximum transmission range is used for all nodes, whereas the transmission range of nodes increases from the innermost layer to the outermost one in Olariu’s scheme.

As shown in Figure 2, with the greater area radius or the greater required network connectivity $(γ^{c})$ , the number of nodes and the total energy consumption of nodes increase in both EBND and Olariu’s scheme. However, Olariu’s scheme always demands a much higher number of nodes and more consumed energy than EBND.

Figure 2.

Comparison with Olariu’s scheme: (a) the total number of nodes and (b) the total energy consumption.

This result is attributed to the following fact. In Olariu’s scheme, the transmission range of nodes in inner layers is much smaller than the maximum radio range. For example, when the area radius is set to 80 m, the transmission ranges of nodes in layers 1 to 5 are {8.19, 16.02, 21.64, 28.82, 28.82} m, respectively. More specifically, nodes in layer 1 can only transmit a signal up to 8.19 m, while the maximum radio range is 30 m. The connectivity range of these nodes is reduced $(30 / 8.19)^{2} = 13.4$ times compared to nodes that use the maximum transmission range. As a result, Olariu’s scheme requires more nodes and more energy consumption than EBND scheme.

Performance study

In this section, we present a performance comparison between EBND and three well-known node deployment strategies,¹² that is, random, grid, and THT node deployments. We do not take into account Olariu’s scheme¹³ because Olariu’s method requires a large number of nodes and high consumed energy as discussed in the previous section.

Simulation setup is shown in Table 1. The bold numbers are the default values. In order to provide high network QoS, high values of network connectivity and sensing coverage requirements (i.e. 0.99 and 0.995, respectively) are chosen. Several parameters of the Mica mote family³⁰ are used, that is, the transmission range and transmission rate of nodes. Layer width $c$ is set to the half of the transmission range. The expected delay requirement for the outermost layer, DR, is set to 30 s. Every $T$ seconds, sensors wake up for $0.03 \times T$ to listen to the channel. Every 72 s, a node generates a 46-byte packet.

Table 1.

Network parameters.

Parameter	Value
Number of nodes $(N)$	{300, 325, 350, 375, 400, 425, 450}
Area radius	{225, 243.8, 262.5, 281.3} m
Sensing range $(r)$	{37.5, 50, 75, 100} m
Delay requirement $(ξ)$	30 s
Network connectivity $(γ^{c})$	0.99
Sensing coverage $(γ^{s})$	0.995
Transmission range $(R)$	75 m
Duty cycle interval $(T)$	30 s
Duty-cycling rate	3%
Data packet size	46 bytes
Packet generation interval	72 s
Transmission rate	250 kbps
Simulation time	7200 s

Bold texts highlights the default values.

For routing protocols, LF and lukewarm potato forwarding (LPF)³¹ are considered in order to evaluate network performance under different routing algorithms. Since LPF is a geometric routing algorithm that aims to achieve low packet delay in WSNs, we select LPF as a routing algorithm in addition to the proposed routing algorithm, LF.

Packet delivery ratio (PDR), average E2E delay, network lifetime, and average energy consumption are selected as performance metrics. Network parameters include the number of nodes, the area radius, and the sensing range. Network simulator 2 (NS2) is used to validate algorithms. Simulation results show that EBND outperforms random, grid, and THT node deployment schemes in terms of network lifetime, PDR, E2E packet delay, and average energy consumption.

The following subsections will discuss the obtained results in more detail.

Effects of number of nodes

We compare EBND with three other node deployment strategies that use two forwarding schemes, LF and LPF. The number of nodes varies from 300 to 450 while other parameters remain unchanged. According to the given number of nodes, EBND determines the optimal number of nodes in each layer. For example, given 375 sensor nodes, the number of nodes from the innermost layer to the outermost is {100, 74, 54, 47, 59, 41}, respectively.

As shown in Figure 3, with both routing algorithms, EBND achieves a higher PDR than random, grid, and THT node deployments. This is attributed to the fact that EBND alleviates the hot spot problem while other algorithms do not, that is, in EBND, the congestion caused by a many-to-one traffic pattern is reduced. In addition, EBND considers the required network connectivity that is 0.99 in the simulation setup. Therefore, PDR in EBND is higher than other evaluated node deployment methods. Moreover, Figure 3 shows that EBND results in smaller average E2E packet delay than three remaining node deployment schemes. The main reason is that EBND considers the required delay constraint while trying to balance energy consumption.

Figure 3.

PDR and average E2E delay with different numbers of nodes: (a) LF scheme and (b) LPF scheme.

In addition, Figure 4 illustrates network lifetime of EBND is always higher than that of random, grid, and THT node deployment schemes under both LF and LPF forwarding schemes. This result is due to the following reasons. In EBND, we deploy nodes based on the traffic in each layer in order to reduce the unbalanced energy problem, that is, the greater traffic, the more nodes we assign to the area. Unlike EBND, random, grid, and THT do not consider the amount of traffic, which leads to the many-to-one traffic pattern, or the hot spot problem. As a result, nodes in inner layers consume much more energy than other nodes. Therefore, network lifetime under these schemes is shorter than it is under EBND.

Figure 4.

Network lifetime with different numbers of nodes: (a) LF scheme and (b) LPF scheme.

Moreover, in EBND, when the number of nodes increases, we can place more nodes in the high traffic area to balance energy consumption. Hence, network lifetime can also be improved given the higher number of nodes. For example, when the number of nodes changes from 300 to 450, Figure 4(a) shows that network lifetime in EBND with the LF algorithm improves $(5419.97 / 3798.27) = 1.43$ times.

In contrast, the number of nodes does not affect network lifetime much in the three other schemes, that is, random, grid, and THT. As shown in Figure 4, when the number of nodes increases, network lifetime of three counterparts remains similar. This is due to the following reason. When the higher number of nodes is provided, both the number of nodes in each layer and the number of data packets forwarded from further layers increase at the same ratio. Hence, the traffic load of a node in each layer is actually unchanged; in other words, network lifetime cannot be improved by requesting more nodes. For example, Figure 4(a) illustrates that network lifetime under the random node deployment is {1411.4, 1220.9, 1411.29, 1181.6, 1412.62, 1358.88, 1425.9} while varying the number of nodes from 300 to 450 under the random deployment.

Note that, even with the LPF scheme, EBND achieves the higher performance (including network lifetime, PDR, average E2E delay, and energy consumption) than three considered node deployment methods. The reason is as follows. EBND aims at reducing the hot spot problem that is unavoidable in a lot of routing algorithms, for example, LPF. Therefore, although LPF is used as a forwarding scheme, the energy consumption of EBND is more balanced and network lifetime can be prolonged compared with three considered methods. PDR performance can also be improved due to the fact that the congestion is reduced. The delay constraint in the EBND node deployment algorithm helps to reduce the average E2E delay even in case of LPF.

As also shown in Figure 4, EBND under the LF scheme shows higher network performance than EBND under LPF. For example, when the number of nodes is 375, network lifetimes of EBND are 5003.94 and 3765.2 s in cases of LF and LPF, respectively. The main reason is that, in LPF, nodes are likely to forward packets to a specific neighboring node, called node’s parent, rather than other neighbors, that is, this specific node tends to experience the high traffic issue. As a result, the energy consumption in the LPF routing algorithm is more unbalanced and network lifetime is lower than LF.

Effects of area radius

In this subsection, we compare EBND to random, grid, and THT deployments with different area radii, under two forwarding schemes, LF and LPF. The area radius is set to {225, 243.8, 262.5, 281.3} m. In EBND, the number of nodes in each layer is obtained using Algorithm 1, for example, when the area radius is 225 m and the number of layers is five, the obtained number of nodes from layer 1 to layer 5 is {155, 91, 53, 41, 35}, respectively.

Figure 5 shows that PDR performance in other node distribution algorithms drops sharply, but PDR in EBND does not. The result comes from the fact that EBND tries to alleviate the many-to-one traffic pattern that causes congestion and collision in WSNs. Therefore, EBND can achieve a higher PDR than three considered node deployment schemes. In terms of E2E delay, EBND results in the lowest packet delay among the considered node distribution strategies. The reason is attributed to the fact that, in EBND, data packets are forwarded to the sink within the desired delay constraint while other algorithms do not take the delay requirement into account.

Figure 5.

PDR and average E2E delay with area radii: (a) LF scheme and (b) LPF scheme.

Moreover, as shown in Figure 6, under all node deployment strategies, network lifetime decreases with a greater area radius. This is attributed to the following fact. In EBND, first, the number of nodes satisfying sensing coverage and network connectivity is determined, and then, the remaining nodes (m) are assigned in such a way as to balance energy consumption. If the larger area is considered, the number of nodes required to meet sensing and network coverage constraints increases. Therefore, a smaller number of remaining nodes is assigned in the hot spot area to balance energy consumption. That causes decreased network lifetime under EBND. Meanwhile, in random, grid, and THT deployments, with the greater area radius and the fix number of nodes, node density decreases; that is, there are fewer nodes in the hot spot area, and these nodes need to forward more packets from further layers. This leads to decreased network lifetime. For example, with the THT node deployment and the LF routing scheme, network lifetime is {3300.64, 2502.75, 1606.74, 1169.42} s when the area radius is {225.0, 243.8, 265.0, 281.3} m, respectively.

Figure 6.

Network lifetime with area radii: (a) LF scheme and (b) LPF scheme.

Although network lifetime under the four node deployment strategies decreases, EBND always achieves the highest network lifetime compared to the three other algorithms. Unlike the three remaining algorithms, EBND deploys nodes based on the traffic in each layer in order to balance energy consumption as much as possible while satisfying delay, network connectivity, and sensing coverage constraints.

Figure 6 also shows that the increased average energy consumption is observed with a greater area radius. Specifically, there are more nodes in farther layers, that is, the average distance from the nodes to the sink is longer, and the average number of packet transmissions increases. Therefore, in four considered node deployment schemes, nodes spend more energy due to the increased area radius.

Effects of sensing range

In this subsection, we discuss the effect of sensing range on network performance in EBND, random, grid, and THT node deployments under LF and LPF routing algorithms. The sensing range is set to {37.5, 50, 75, 100} m while other parameters are kept constant. As can be seen from Figures 7 and 8, the sensing range only affects the network performance under EBND. In EBND, when the sensing range increases, the minimum number of nodes that meets the requirement of sensing coverage is smaller; that is, we can assign more nodes in crowded regions or inner layers to balance energy consumption, and hence, network lifetime increases. For instance, under the LF routing algorithm, when the sensing range varies from 37.5 to 100 m, network lifetime is enhanced 1.37 times, from 4082.68 to 5615.88 s, respectively.

Figure 7.

PDR and average E2E delay with sensing ranges: (a) LF scheme and (b) LPF scheme.

Figure 8.

Network lifetime with sensing ranges: (a) LF scheme and (b) LPF scheme.

Meanwhile, under EBND, the average E2E delay and average energy consumption decrease with the greater sensing range. This is because there are more nodes deployed in inner layers, and these nodes in the inner layers have lower delay and energy consumption than nodes in outer layers. Therefore, the average E2E packet delay and energy consumption decrease.

Note that only EBND considers the sensing coverage constraint, whereas random, grid, and THT schemes do not. Hence, there is no change in network performance with the different sensing ranges under the random, grid, and THT schemes.

Conclusion

This article addressed the issue of maximizing network lifetime considering delay, sensing coverage, and network connectivity constraints in WSNs. A novel EBND algorithm called EBND was proposed, in which we formulate an optimization problem to determine the optimal number of nodes in each layer to maximize network lifetime with multiple constraints.

In EBND, the objective function and constraints are estimated as a function of the number of nodes in the layers. We proposed an algorithm to attain the optimal number of nodes in each layer, given the total number of nodes. Numerical results indicate that EBND demands a smaller number of nodes and less consumed energy than Olariu’s scheme. Simulation results show that EBND can achieve longer network lifetime than other node deployment strategies considered while satisfying the constraints.

Footnotes

Handling Editor: Ju Wang

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 work was supported by the 2016 Research Fund of University of Ulsan.

ORCID iD

Thi-Nga Dao

References

Akyildiz

Sankarasubramaniam

et al . Wireless sensor networks: a survey. Comput Netw 2002; 38: 393–422.

Rawat

Singh

Chaouchi

et al . Wireless sensor networks: a survey on recent developments and potential synergies. J Supercomput 2014; 68: 1–48.

Yick

Mukherjee

Ghosal

Wireless sensor network survey. Comput Netw 2008; 52(12): 2292–2330.

Rashid

Rehmani

MH.

Applications of wireless sensor networks for urban areas: a survey. J Netw Comput Appl 2016; 60: 192–219.

Chen

Zhao

On the lifetime of wireless sensor networks. IEEE Commun Lett 2005; 9(11): 976–978.

Perillo

Cheng

Heinzelman

. An analysis of strategies for mitigating the sensor network hot spot problem. In: Proceedings of the 2nd annual international conference on mobile and ubiquitous systems: networking and services, San Diego, CA, 17–21 July 2015, pp.474–478. New York: IEEE.

Ferng

Hadiputro

Kurniawan

Design of novel node distribution strategies in corona-based wireless sensor networks. IEEE T Mobile Comput 2011; 10: 1297–1311.

Halder

Das Bit

Enhancement of wireless sensor network lifetime by deploying heterogeneous nodes. J Netw Comput Appl 2014; 38: 106–124.

Chen

Das

SK.

Avoiding energy holes in wireless sensor networks with nonuniform node distribution. IEEE T parall Distr 2008; 19: 710–720.

10.

Cheng

Chuah

Liu

Energy-aware node placement in wireless sensor networks. In: Proceedings of the global telecommunications conference, Dallas, TX, 29 November–3 December 2004, pp.3210–3214. New York: IEEE.

11.

Hou

Shi

Sherali

et al . On energy provisioning and relay node placement for wireless sensor networks. IEEE T Wirel Commun 2005; 4(5): 2579–2590.

12.

Poe

Schmitt

JB.

Node deployment in large wireless sensor networks: coverage, energy consumption, and worst-case delay. In: Proceedings of the Asian internet engineering conference, Bangkok, Thailand, 18–20 November 2009, pp.77–84. ACM.

13.

Olariu

Stojmenovic

. Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting. In: Proceedings of the 25th international conference on computer communications, Barcelona, 23–29 April 2006, pp.1–12. New York: IEEE.

14.

Song

Liu

Cao

et al . Maximizing network lifetime based on transmission range adjustment in wireless sensor networks. Comput Commun 2009; 32(11): 1316–1325.

15.

Tran-Quang

Miyoshi

. A transmission range adjustment algorithm to avoid energy holes in wireless sensor networks. In: Proceedings of the 8th Asia-Paciﬁc symposium on information and telecommunication technologies, Kuching, Malaysia, 15–18 June 2010, pp.1–6. New York: IEEE.

16.

Heo

Hong

Cho

EARQ: energy aware routing for real time and reliable communication in wireless industrial sensor networks. IEEE T Ind Inform 2009; 5(1): 3–11.

17.

Jarry

Leone

Powell

et al . An optimal data propagation algorithm for maximizing the lifespan of sensor networks. In: Proceedings of the 2nd international conference on distributed computing in sensor systems, San Francisco, CA, 18–20 June 2006. Springer-Verlag.

18.

Gatzianas

Georgiadis

. A distributed algorithm for maximum lifetime routing in sensor networks with mobile sink. In: Proceedings of the 12th European wireless conference: enabling technologies for wireless multimedia communications, Athens, 2–5 April 2006, pp.1–7. VDE.

19.

Marta

Cardei

Using sink mobility to increase wireless sensor networks lifetime. In: Proceedings of the international symposium on a world of wireless, mobile and multimedia networks, Newport Beach, CA, 23–26 June 2008, pp.1–10. New York: IEEE.

20.

Demertzis

Oikonomou

Avoiding energy holes in wireless sensor networks with non-uniform energy distribution. In: Proceedings of the 5th international conference on information, intelligence, systems and applications, Chania, 7–9 July 2014, pp.138–143. New York: IEEE.

21.

Lian

Naik

Agnew

GB.

Data capacity improvement of wireless sensor networks using non-uniform sensor distribution. Int J Distrib Sens N 2006; 2(2): 121–145.

22.

Liu

Jin

Cui

et al . Deployment guidelines for achieving maximum lifetime and avoiding energy holes in sensor network. Inform Sciences 2013; 230: 197–226.

23.

Xiao

Chen

et al . Coverage and detection of a randomized scheduling algorithm in wireless sensor networks. IEEE Trans Comput 2010; 59(4): 507–521.

24.

Gkatzikis

Fischione

et al . On maximizing sensor network lifetime by energy balancing. IEEE Trans Control Netw Syst 2017; PP(99): 1.

25.

Yao

Cao

Vasilakos

AV.

EDAL: an energy-efficient, delay-aware, and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks. IEEE/ACM Trans Netw 2015; 23(3): 810–823.

26.

Barsi

Bertossi

Sorbelli

et al . Asynchronous corona training protocols in wireless sensor and actor networks. IEEE T parall Distr 2009; 20(8): 1216–1230.

27.

Dao

Yoon

Kim

A deadline-aware scheduling and forwarding scheme in wireless sensor networks. Sensors 2016; 16(1): 59.

28.

Heinzelman

Chandrakasan

Balakrishnan

An application-speciﬁc protocol architecture for wireless microsensor networks. IEEE T Wirel Commun 2002; 1(4): 660–670.

29.

Ross

SM.

Introduction to probability models. 9th ed. Orlando, FL: Academic Press, 2006.

30.

Karl

Willig

Protocols and architectures for wireless sensor networks. John Wiley & Sons, 2005.

31.

Beraldi

Baldoni

Prakash

A biased random walk routing protocol for wireless sensor networks: the lukewarm potato protocol. IEEE T Mobile Comput 2010; 9(11): 1649–1661.

A node deployment algorithm for maximizing network lifetime in delay-constrained duty-cycled wireless sensor networks

Abstract

Keywords

Introduction

Related work

System model and assumption

EBND with delay, network connectivity, and sensing coverage requirements

Problem definition

Energy consumption

Delay constraint

Network connectivity and sensing coverage

Problem formulation

Algorithm

Numerical results

Performance study

Effects of number of nodes

Effects of area radius

Effects of sensing range

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References