Distributed optimization of lifetime and throughput with power consumption balance opportunistic routing in dynamic wireless sensor networks

Abstract

This article studies a joint performance optimization on the network lifetime and network throughput for an energy-constrained dynamic wireless sensor network. We propose a fully distributed power consumption balance opportunistic routing scheme to cope with the dynamic network that is not considered in the classic low-energy adaptive clustering hierarchy routing and evenly allocate power consumption among the sensor nodes for obtaining longer network lifetime. Moreover, a fully distributed optimization solution, whose distinctive feature to the Lagrange dual approach is capable of handling the changing network, is developed to achieve joint performance optimization of objectives. We mathematically prove the convergence of the proposed solution and analyze its computational complexity. Extensive simulation results illustrate the effective measures to deal with the varying network of power consumption balance opportunistic routing and the best tradeoff performance achieved by the proposed solution and evaluate the more positive impact on the network lifetime of power consumption balance opportunistic routing than the existing routings and better ability to adapt the dynamic network of the proposed solution than the Lagrange dual approach.

Keywords

Network lifetime wireless sensor networks opportunistic routings distributed optimization dynamic networks

Introduction

In a wireless sensor network (WSN), each sensor node is tasked to capture data and deliver them over wireless channels to the sink nodes for further data analysis and decision-making. In general, maximizing the network lifetime and network throughput are critical issues in WSNs. Nevertheless, the prolongation of the network lifetime always leads to the decrease in network throughput. How to make a tradeoff between the network lifetime and network throughput for the overall system performance remains a challenging problem. Moreover, WSNs usually comprise a large number of sensor nodes deployed randomly in a highly dynamic and hostile environment, resulting in the frequent change in network topology. In this article, for a joint network lifetime and throughput optimization under dynamic network settings, we focus on an opportunistic routing and a distributed optimization solution.

Low-energy adaptive clustering hierarchy (LEACH) routing is the classic clustering-based protocol that utilizes randomized rotation of local cluster heads to extend the network lifetime. However, LEACH routing does not take account of the dynamic networks. Moreover, neglecting the influence of transmission distance and the periodical clustering of LEACH routing limit maximization of the network lifetime. To overcome these problems, we propose a fully distributed power consumption balance (PCB) opportunistic routing scheme. It enables network topology update to cope with the dynamic network. For longer network lifetime, it abolishes clustering scheme and weakens the impact of long-distance transmission on node power consumption to save node energy. Furthermore, it adopts a new next-hop selection strategy to equally utilize power among the sensor nodes.

The Lagrange dual approach is frequently used to achieve the optimal solutions. But it could not handle the changing network. To solve this problem, we develop a fully distributed optimization solution, which is capable of tackling the changing networks, to achieve the joint performance optimization of the network lifetime and network throughput. The proposed solution decomposes the original problem into two stages. In the first stage, the optimization is executed at each individual node for maximizing the node lifetime and throughput. The second stage utilizes the results of the first stage to bring global optimization on the network lifetime and throughput.

The remainder of this article is organized as follows: section “System modeling” describes a generalized system model. Section “PCB opportunistic routing protocol” introduces the PCB opportunistic routing scheme. Section “Problem statement” formulates the proposed distributed optimization solution. In section “Theoretic analysis,” the convergence performance and computational complexity of the proposed solution are theoretically analyzed, and we prove Lemma 1 for the next section. Extensive simulation results are presented and discussed in section “Simulation results.” Finally, section “Concluding remarks” concludes this article.

Related work

In the past, a variety of routing and rate control schemes have been proposed to maximize the lifetime of WSNs.^1–10 Madan and Lall,¹ He et al.,² and Cetin et al.³ studied distributed routing algorithms for maximizing the lifetime. Wang et al.⁴ proposed a cross-layer design approach for minimizing the energy consumption of a multiple-source and single-sink WSN. Zhu et al.⁵ exploited the interaction between the network lifetime maximization and fair rate allocation. Furthermore, many researches concentrated on LEACH routing protocol to prolong the network lifetime. Based on LEACH routing, Li et al.⁶ proposed an improved cluster head reappointment algorithm (LEACH-R), to overcome the shortcoming of LEACH that each node would be frequently elected as the cluster head for several times and consumed some energy for this. Haneef et al.⁷ utilized redundancy of the deployed nodes to increase energy efficiency in multi-group-based LEACH, outperforming LEACH at the network lifetime. A protocol named Bayesian network model LEACH realized uniform distribution of cluster heads that is not guaranteed in LEACH to extend the network lifetime in Ghasemzadeh et al.⁸ Quynh et al.⁹ presented energy and load balance LEACH routing (EL-LEACH), which showed a cluster head selection strategy for covering defects brought by the original method of LEACH, to achieve better energy consumption, load balance, and network lifetime. Ahmad et al.¹⁰ controlled election and selection of cluster heads to uniform load on cluster heads and took the free association mechanism to remove back transmissions in adaptive clustering habit routing scheme for minimizing the overall energy consumption of the network. Whereas these studies are all on the basis of the static network and do not consider the dynamic settings. Thus, we propose a fully distributed PCB opportunistic routing to handle the varying network and obtain longer network lifetime than the existing routings.

How to maximize network throughput has been studied by extensive works. And most of them take the Lagrange dual approach to achieve the optimal solutions. Fida et al.¹¹ used a route selection metric based on the reception probability of Rician fading channel for avoiding the low-throughput routes of the conventional route selection metrics to optimize network throughput. Sappidi et al.¹² utilized in-network computation for statistical functions to reduce the volume of traffic transmitted, achieving maximized throughput in a WSN. The research results of Verdone et al.¹³ showed that the density of the sensor nodes and the query interval decided optimized area throughput for different scales in a multi-sink clustered WSN. Based on the proposed mobile-relay-assisted data collection model, the achievable throughput capacity of large-scale WSNs is analyzed by choosing appropriate mobility parameters in Liu et al.¹⁴ Xie et al.¹⁵ solved the throughput performance deterioration problem by referring to the notion of fairness and demonstrated the availability of throughput maximum under an equal proportion of channel occupancy time for each contending node. Moreover, the tradeoff between throughput optimization and energy consumption optimization is considered. Ren and Liang¹⁶ proposed a throughput maximized Medium Access Control (MAC) protocol, redividing each pico-net into several subsets in which communication pairs can make communication simultaneously, to maximize throughput and achieve short latency. However, these works are also founded on the static network and do not consider the condition that the change in a network happens. Hence, in this article, a fully distributed optimization solution, which has better ability to adapt the dynamic network than the Lagrange dual approach, is proposed to optimize the network lifetime and throughput simultaneously.

System modeling

A WSN could be modeled as a directed graph $G (V, Z)$ , where V is the set of network nodes and Z is the set of directed links between the nodes. The set V includes two disjoint subsets S and R representing the sensor nodes and sink nodes, respectively. Each sensor node has a maximum transmission range $d_{max}$ . A directed link $(j, i) \in Z$ exists between the jth node and the ith node if their distance $d_{ji}$ satisfies $d_{ji} \leq d_{max}$ .

Suppose that there are N nodes in a WSN. The ith node has a N-dimensional vector $H_{i}$ to reflect its communication relationship with the other nodes. Let $H_{i}^{j}$ be the jth element of $H_{i}$ and $H_{i}^{j} = 1$ if the jth node could communicate with the ith node, or else $H_{i}^{j} = 0$ . Assume that the ith node has a N-dimensional vector $f_{i}$ that represents data transmission rates from the other nodes to the ith node. The jth element $f_{i}^{j}$ of $f_{i}$ represents the data transmission rate from the jth node to the ith node. Let $f_{i}^{j} = 0$ if the jth node does not send data to the ith node. Thus, the node throughput at the ith node is $f_{i} = H_{i} \cdot f_{i}$ and the traffic of the neighbors around the ith node is $B_{i} = \sum_{j \in b_{i}} f_{j}$ , where $b_{i}$ is the set of neighbor nodes around the ith node. Accordingly, the network throughput is formulated as $G_{net} = \sum_{i \in R} f_{i}$ .

To denote the latency resulting from channel contention, we introduce a concave increasing latency function $l (\cdot)$ ¹⁷ over one hop, whose input is the data load of the medium. Accordingly, we define the cost function $C_{i}$ of the ith node as the latency experienced by all communications that run through the ith node during channel contention, that is, $C_{i} = l (f_{i} + B_{i}) f_{i}$ . Then, the average cost $\bar{C}$ of all nodes is formulated as $\bar{C} = (1 / N) \sum_{i \in V} C_{i}$ .

Moreover, define $V_{P} = (1 / n_{S}) \sum_{i \in S} (P_{i} - \bar{P})^{2}$ as the variance of power consumption among the sensor nodes, where $n_{S}$ is the number of sensor nodes, $P_{i}$ is the power consumption of the ith sensor node, and $\bar{P} = (1 / n_{S}) \sum_{i \in S} P_{i}$ is the average power consumption of the sensor nodes. The smaller the $V_{P}$ , the more equal the power usage among the sensor nodes. Assume that the ith sensor node has an initial energy $E_{i}$ and a lifetime $T_{i} = E_{i} / P_{i}$ , then the network lifetime is defined as $T_{net} = min_{i \in S} T_{i} = min_{i \in S} E_{i} / P_{i}$ .

PCB opportunistic routing protocol

Compared with LEACH routing protocol, the proposed PCB opportunistic routing scheme makes two improvements. The first is to achieve longer network lifetime, and the second is adapt to the dynamic network. To these ends, first, it cuts down the periodical clustering of LEACH routing to save the power consumption. Second, it takes into account the impact of transmission distance on power consumption. As is well known, the shorter the transmission distance, the less the transmit power required. In LEACH routing, a sensor node directly sends its data to the cluster head regardless of their distance. When the sensor node is far away from its cluster head, it uses a large amount of transmit power, which may lead to its early death and decrease $T_{net}$ . PCB opportunistic routing with smaller $d_{max}$ than LEACH routing allows the communication between the sensor nodes and decomposes one-hop long-distance transmission into multi-hop short-distance transmission so as to avoid the early death in LEACH routing. Third, when forwarding the received data, it uses a new next-hop selection strategy to achieve equal power consumption among the sensor nodes. Based on the above three, the proposed PCB opportunistic routing outperforms LEACH routing at the network lifetime. Fourth, it supports the changing network, which is not considered in LEACH routing.

We now introduce some definitions and notations of PCB opportunistic routing. For a minimal number of hops to the sink node, the sensor nodes are classified into several levels. As shown in Figure 1, the 1st, 3rd, and 4th sensor nodes are considered as the third-level nodes because they need a minimum of three hops to reach the 10th sink node. Thus, the second, fifth, sixth, and seventh sensor nodes that need two hops are the second-level nodes. Following the same principle, the eighth and ninth sensor nodes are the first-level nodes.

Figure 1.

Topology of the WSN.

Furthermore, we define the sensor node as an exclusive node when the number of the next low-level nodes it can connect is one. In Figure 1, the fourth node in the third level is an exclusive node as it only connects to one second-level node, that is, the seventh node. Similarly, the second, fifth, and seventh nodes in the second level are all exclusive nodes.

PCB opportunistic routing consists of three processes, that is, initialization, next-hop selection, and network topology update. The way of initialization uses LEACH protocol. It means that all nodes in a randomly distributed WSN (i.e. Figure 1) make sure their communication relationships in the ad hoc way. Within the maximum transmission range $d_{max}$ , the ith sensor node tries to communicate with the other nodes by one-hop or multi-hop for $H_{i}$ , determine its own level as well as levels of its neighbors, and decide whether it is an exclusive node.

When selecting the next hop, a sensor node follows the five principles that are listed below:

Next-hop selection starts from the highest level node, in a decreasing order to its next low-level node over the next hop, then one by one, and finally ends at the sink node. Next-hop selection among the sensor nodes in the same level is not allowed.

The exclusive nodes have the priority on next-hop selection. Afterward, other sensor nodes in the same level select their own next-hop nodes, one by one, from near to far around the exclusive node.

The sensor node selects only one next-hop node.

The sensor node selects the next-hop node whose node throughput is the least among the next low-level nodes of its neighbors.

The sensor node selects the nearest next low-level node under the circumstance that the next low-level nodes of its neighbors have the same node throughput.

Note that when next-hop selection process is finished, it will maintain stable until the network variation happens.

Take Figure 1 as an example. Assume that the amount of captured data at each sensor node is equal. Based on the principles above, the fourth exclusive node in the highest level first selects the seventh node in the next low level. Then, obeying principle (4), the third node in the highest level selects the sixth node in the next low level. According to principle (5), the first node in the highest level selects the second node in the next low level; moreover, the second and fifth exclusive nodes in the second level select the eighth node in the first level, and the seventh exclusive node in the second level selects the ninth node in the first level. Thereafter, following principle (4), the sixth node in the second level selects the ninth node with the least node throughput among the first-level nodes of its neighbors. Finally, the 8th and 9th nodes in the first level send data to the 10th sink node. To make a comparison, assume that in LEACH routing, the first, second, fifth, and eighth sensor nodes are in the same cluster and the eighth sensor node is elected as the cluster head. The first node would use a lot of power to transmit data to the cluster head for the long distance, which would lead to its early death. However, in PCB opportunistic routing, the first node could send its data to the much nearer second node, which could forward data of the first node to the eighth node, so as to save much power of the first node avoiding its early death.

Network topology update, including re-initialization and re-selection of the next hop, is triggered when the change in the network occurs. The sensor nodes that detect the change would notify the sink node, and then the sink node sends re-initialization messages to all the sensor nodes, telling them to do initialization and next-hop selection processes again.

Problem statement

Optimization problem

The total power of a sensor node is mainly used for two functions: (1) data transmission and (2) data reception. Based on the power consumption model widely used in WSNs,^2,5 the transmission power consumption at the ith sensor node can be denoted as $P_{i}^{t} = ε_{ij} \cdot \sum_{j : (i, j) \in Z} f_{j}^{i}$ , where $ε_{ij} \in (0, 1)$ is the transmission energy consumption coefficient of link $(i, j)$ . The reception power consumption at the ith sensor node can be formulated as $P_{i}^{r} = ξ \cdot f_{i}$ , where $ξ \in (0, 1)$ is the energy consumption coefficient of the radio receiver. Therefore, the total power consumption of the ith sensor node is given by $P_{i} (f_{i}) = P_{i}^{t} + P_{i}^{r} = ε_{ij} \cdot \sum_{j : (i, j) \in Z} f_{j}^{i} + ξ \cdot f_{i}$ .

Maximizing the network lifetime and network throughput are two contradictory objectives. To make a tradeoff, we use a simple and efficient weighting method,¹⁸ to combine these two objectives into a single objective function. That is, $max {α T_{net} + (1 - α) G_{net}}$ , where $α \in [0, 1]$ is a weighted system parameter. Mathematically, the joint optimization problem can be formulated as follows

P 1 : max {α T_{net} + (1 - α) G_{net}}

(1)

s.t.

$T_{net} = min_{i \in S} T_{i} = min_{i \in S} (E_{i} / P_{i})$ ;

$G_{net} = \sum_{i \in R} f_{i}$ ;

$l (f_{i} + B_{i}) \leq T_{i}, \forall i \in S$ ;

$f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p} \leq A, \forall (j, i) \in Z$ .

Constraint (3) shows that the latency of the ith sensor node should be no more than node lifetime $T_{i}$ . Constraint (4) is the wireless network channel interference constraint. It specifies that the sum of needed transmission data and interference data must be no more than maximized rate A of the wireless shared medium, and $Ψ (j, i)$ is the set of links that would interfere with the communication between the jth node and the ith node when it is alive.¹⁹

In Problem P1, $G_{net}$ of the objective function is not concave, thus this problem is not a convex problem that is usually difficult to solve in practice. Therefore, we introduce a new variable $G_{net}^{\ln} = \ln G_{net}$ ,¹⁵ which is directly proportional to $G_{net}$ . $G_{net}$ achieves its maximum when $G_{net}^{\ln}$ arrives at the maximum. However, the order of magnitude of $G_{net}^{\ln}$ is much less than $T_{net}$ . We define a coefficient $λ_{f}$ to adjust the order of magnitude of $G_{net}^{\ln}$ to make $λ_{f} \cdot G_{net}^{\ln}$ and $T_{net}$ comparable. Thus, the original objective function is rewritten as $max {α T_{net} + (1 - α) \cdot λ_{f} \cdot G_{net}^{\ln}}$ . Moreover, we use $G_{net}^{\ln} = \ln G_{net} = \ln \sum_{i \in R} f_{i}$ to replace the original constraint (2). Then, to match up with the expression form of $G_{net}^{\ln}$ , we take the logarithm of constraint (4). Thus, constraint (4) is equally changed to $\ln (f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p}) \leq \ln A$ .

After the above transformation, Problem P1 becomes

P 2 : max {α T_{net} + (1 - α) \cdot λ_{f} \cdot G_{net}^{\ln}}

(2)

s.t.

$T_{net} = min_{i \in S} T_{i} = min_{i \in S} (E_{i} / P_{i})$ ;

$G_{net}^{\ln} = \ln G_{net} = \ln \sum_{i \in R} f_{i}$ ;

$l (f_{i} + B_{i}) \leq T_{i}, \forall i \in S$ ;

$\ln (f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p}) \leq \ln A, \forall (j, i) \in Z$ .

Proposed distributed optimization solution

According to the definitions of $T_{net}$ and $G_{net}^{\ln}$ , we know that the optimal $T_{net}$ and $G_{net}^{\ln}$ come out from the optimal node lifetime $T_{i}$ and node throughput $f_{i}$ . In order to obtain the optimal $T_{net}$ and $G_{net}^{\ln}$ , we first need to find out the optimal $T_{i}$ and $f_{i}$ . Hence, the solution of Problem P2 can be divided into two stages. The first stage, as shown in subproblem P2a, fulfills at each individual node to find out the optimal $T_{i}$ and $f_{i}$ . In the second stage, as shown in subproblem P2b, the sink node collects the results of the first stage and determines the optimal $T_{net}$ and $G_{net}^{\ln}$

P 2 a : max {α T_{i} + (1 - α) \cdot λ_{f} \cdot \ln f_{i}}

(3)

s.t.

$T_{i} = (E_{i} / P_{i}), \forall i \in S$ ;

$l (f_{i} + B_{i}) \leq T_{i}, \forall i \in S$ ;

$\ln (f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p}) \leq \ln A, \forall (j, i) \in Z$ .

P 2 b : max {α T_{net} + (1 - α) \cdot λ_{f} \cdot G_{net}^{\ln}}

(4)

s.t.

$T_{net} = min_{i \in S} T_{i} = min_{i \in S} (E_{i} / P_{i})$ ;

$G_{net}^{\ln} = \ln G_{net} = \ln \sum_{i \in R} f_{i}$ .

Note that $\ln f_{i}$ is directly proportional to $f_{i}$ and $f_{i}$ acquires its maximum when $\ln f_{i}$ reaches the maximum.

Based on the results of subproblem P2a sent from each sensor node, the sink node determines the final solution by $max T_{net} = min_{i \in S} T_{i}^{*}$ and $max G_{net}^{\ln} = \ln \sum_{i \in R} f_{i}^{*}$ , where $T_{i}^{*}$ and $f_{i}^{*}$ are the optimal lifetime and throughput of the ith node obtained at the first stage, respectively. Namely, subproblem P2b can be solved by

\begin{matrix} max {α T_{net} + (1 - α) \cdot λ_{f} \cdot G_{net}^{\ln}} \\ = α min_{i \in S} T_{i}^{*} + (1 - α) \cdot λ_{f} \cdot \ln \sum_{i \in R} f_{i}^{*} \end{matrix}

(5)

It is noted that the solution to P2b can only be obtained at the sink node during the second stage. To solve subproblem P2a in a fully distributed way, we employ the adaptive penalty-based distributed stochastic optimization algorithm.²⁰ In particular, P2a can be solved as an unconstrained optimization problem by penalty functions as follows

\begin{matrix} W_{i} (f_{i}) = max_{f_{i}} [α T_{i} + (1 - α) \cdot λ_{f} \cdot \ln f_{i}] \\ + η \cdot δ^{EP} (T_{i} - \frac{E_{i}}{P_{i}}) + η \cdot δ^{IP} [l (f_{i} + B_{i}) - T_{i}] \\ + η \cdot δ^{IP} [\ln (f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p}) - \ln A] \end{matrix}

(6)

where $η > 0$ is a scalar parameter that controls the relative importance of adhering to constraints. The corresponding penalty functions are

δ^{EP} (x) = {\begin{matrix} 0, x = 0 \\ < 0, x \neq 0 \end{matrix}, δ^{IP} (x) = {\begin{matrix} 0, x \geq 0 \\ < 0, x < 0 \end{matrix}

where EP and IP denote the equality penalty and inequality penalty, respectively. In practice, we use $δ^{SEP} (\cdot)$ and $δ^{SIP} (\cdot)$ to approximate $δ^{EP} (\cdot)$ and $δ^{IP} (\cdot)$ , respectively. Here, $δ^{SEP} (\cdot)$ and $δ^{SIP} (\cdot)$ are formulated as

δ^{SEP} (x) = - x^{2}, δ^{SIP} (x) = min (0, x^{3})

where SEP and SIP denote the simulated equality penalty and simulated inequality penalty, respectively. For simplifying expression, we define

\begin{matrix} J_{i} (f_{i}) & = max_{f_{i}} [α T_{i} + (1 - α) \cdot λ_{f} \cdot \ln f_{i}] \\ = α E_{i} {[ε_{ij} \cdot \sum_{j : (i, j) \in Z} f_{j}^{i} + ξ \cdot f_{i}]}^{- 1} + (1 - α) \cdot λ_{f} \cdot \ln f_{i} \end{matrix}

(7)

\begin{matrix} m_{i} (f_{i}) = & δ^{SEP} (T_{i} - \frac{E_{i}}{P_{i}}) + δ^{SIP} [l (f_{i} + B_{i}) - T_{i}] \\ + δ^{SIP} [\ln (f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p}) - \ln A] \end{matrix}

(8)

Hence, equation (6) is converted into $W_{i} (f_{i}) = J_{i} (f_{i}) + η \cdot m_{i} (f_{i})$ .

To find $f_{i}^{*}$ , the following iterations run with a constant step-size $μ$ ²⁰

ς_{i, n} = f_{i, n - 1} + μ \hat{\nabla_{f_{i}}} J_{i} (f_{i, n - 1})

(9a)

ψ_{i, n} = ς_{i, n} + μ η \nabla_{f_{i}} m_{i} (ς_{i, n})

(9b)

f_{i, n} = \sum_{j \in b_{i}} a_{i}^{j} ψ_{j, n}

(9c)

where n is the iteration number, $ς_{i, n}$ and $ψ_{i, n}$ are the intermediate variables, $μ$ is the constant step-size, and ${a_{i}^{j}}$ is the set of non-negative combination coefficients of the neighbors around the ith node, which satisfy

a_{i}^{j} = 0, when j \notin b_{i}

\sum_{j = 1}^{N} a_{i}^{j} = 1, i = 1, \dots, N

In addition, $\hat{\nabla_{f_{i}}} J_{i} (f_{i, n - 1})$ is

\hat{\nabla_{f_{i}}} J_{i} (f_{i, n - 1}) = (1 - α) \frac{λ_{f}}{f_{i, n - 1}} - α E_{i} ξ \cdot P_{i} (f_{i, n - 1})^{- 2} + v_{i, n - 1}

(10)

where $v_{i, n - 1}$ is the random perturbation term (or gradient noise) that makes $ς$ , $ψ$ , and f in the diffusion strategies (9a)–(9c) become random variables, and $P_{i} (f_{i, n - 1}) = ε_{ij} \cdot \sum_{j : (i, j) \in Z} f_{j}^{i} + ξ \cdot f_{i, n - 1}$ .

Because $\nabla_{f_{i}} δ^{SEP} (T_{i} - (E_{i} / P_{i})) = 0$ , $\nabla_{f_{i}} m_{i} (ς_{i, n})$ is denoted as

\nabla_{f_{i}} m_{i} (ς_{i, n}) = 3 \sum_{k = 2}^{3} D_{k} (ς_{i, n})^{2} \cdot {\overset{\cdot}{D}}_{k} (ς_{i, n})

(11)

where ${\overset{\cdot}{D}}_{k} (ς_{i, n}) = (\partial D_{k} / \partial ς_{i, n}), k = 2, 3$ and $D_{2} (ς_{i, n}) = l (ς_{i, n} + B_{i}) - E_{i} \cdot P_{i} (ς_{i, n})^{- 1}$ , ${\overset{\cdot}{D}}_{2} (ς_{i, n}) = \overset{\cdot}{l} (ς_{i, n} + B_{i}) + E_{i} \cdot ξ \cdot P_{i} (ς_{i, n})^{- 2}$ , $D_{3} (ς_{i, n}) = \ln (ς_{i, n} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p}) - \ln A$ , and ${\overset{\cdot}{D}}_{3} (ς_{i, n}) = (ς_{i, n} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p})^{- 1}$ .

It is worth mentioning that the first stage should also be conducted at the sink node. Since the sink node is supposed to be power infinite, lifetime maximization is no longer a problem, and throughput maximization becomes the sole objective of the sink node. Therefore, constraints (1) and (2) of subproblem P2a become invalid. For the sink node, subproblem P2a is rewritten as follows

P 2 a' : max {\ln f_{i}}

(3′)

s.t.

$\ln (f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p}) \leq \ln A, \forall (j, i) \in Z$

Besides, equations (6)–(8) are re-depicted as follows

\begin{matrix} {W'}_{i} (f_{i}) = max_{f_{i}} \ln f_{i} \\ + η \cdot δ^{IP} [\ln (f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p}) - \ln A] \end{matrix}

(6′)

J'_{i} (f_{i}) = max_{f_{i}} \ln f_{i}

(7′)

m'_{i} (f_{i}) = δ^{SIP} [\ln (f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p}) - \ln A]

(8′)

Meanwhile, equation (9c) remains the same, equations (9a) and (9b) are omitted, and this results in the worthlessness of equations (10) and (11). The reason is that equations (9a) and (9b) acquire $ψ_{i, n}$ transmitted to the next hop; however, for the sink node, the next-hop nodes do not exist and equation (9c) leads to $f_{i, n}$ for achieving the optimum $f_{i}^{*}$ . That is to say, equations (9a)–(9c) are converted into

f_{i, n} = \sum_{j \in b_{i}} a_{i}^{j} ψ_{j, n}

(9′)

It is noted that when the network changes, the optimization of the lifetime and throughput at each node could run with the new parameters offered by the network topology update process of PCB opportunistic routing. After that, the second stage finds out the optimal $T_{net}$ and $G_{net}^{\ln}$ under the new network.

Practical problem

The computational complexity of the proposed distributed solution is determined by the computational complexity in two stages. At the first stage, the other nodes correlated to the ith node would obtain the optimums when the variable $f_{i, n}$ converges to the optimum $f_{i}^{*}$ . Note that achieving the optimums of the correlated nodes is not conditional on converging to $f_{i}^{*}$ at the ith node and vice versa. Achieving the optimums of the correlated nodes and converging to $f_{i}^{*}$ at the ith node are paratactic and simultaneous. It is worth mentioning that the optimization of each individual node is simultaneous at the first stage. Thus, the computational complexity of the first stage is actually the maximum of the computational complexity of each node, which is $O (n)$ . At the second stage, the sink node obtains the optimal solution of Problem P2 according to the received $T_{i}^{*}$ and $f_{i}^{*}$ from all the nodes. The computational complexity of $α min_{i \in S} T_{i}^{*}$ is $O (1)$ and the computational complexity of $(1 - α) \cdot λ_{f} \cdot \ln \sum_{i \in R} f_{i}^{*}$ is $O (1)$ as well; thus, the computational complexity of the second stage is $O (1) + O (1) = O (1)$ . Hence, the computational complexity of the proposed distributed optimization solution is $O (n) + O (1) = O (n)$ .

To realize the proposed distributed optimization solution, each node is considered as a processor of a distributed computation system. Assume that the processor of the ith node keeps track of variable $f_{i}$ . At initialization phase, each node contacts with the other nodes to gain $H_{i}$ , then the ith node obtains $b_{i}$ and its path to the sink node. After the distributed optimization of each individual node at the first stage, the second stage brings the optimal solution to Problem P2 as shown in equation (5).

There are three points need to emphasize: (1) for the static network, $H_{i}$ and $b_{i}$ are fixed; (2) from equation (9c), we know the distributed optimization of each individual node is correlated, and thus, the other nodes correlated to the ith node would reach the optimums when the variable $f_{i, n}$ converges to the optimum $f_{i}^{*}$ ; and (3) at the first stage, the correlated nodes could communicate with each other through established links in PCB routing to transfer needed $ψ_{j, n} (j \in b_{i})$ in a distributed manner, rather than send $ψ_{i, n}$ to the sink node and then broadcast.

When the communication overhead issue²¹ is taken into account, all the update operations at the first stage can utilize those variables stored in the local node or link, except the updated rates $f_{j}$ and $ψ_{j, n} (j \in b_{i})$ that are needed to be transmitted by extra packets. For example, according to equations (9b) and (11), the definition of $B_{i}$ , and equation (9c), to update $ψ_{i, n}$ and $f_{i, n}$ , the packet carrying $f_{j}$ and $ψ_{j, n}$ is only required to transmit along the link between the jth node and the ith node. If we adopt the float type in implementation, each $f_{j}$ or $ψ_{j, n}$ takes up only 4 bytes, thus it is negligible compared to the main data traffic. Roughly estimated, the time spent by the whole network to reach the stability is equal to the number of iterations required for convergence multiplying the update time interval of each iteration. It is found in Deb and Srikant²² that an update interval is about two to three times the one-way propagation delay of the particular receiver. An update interval is sufficient for the updated rates’ interaction between the nodes. Therefore, the entire overhead of the proposed distributed solution is quite small.

Theoretic analysis

As is stated above, subproblem P2b can be resolved easily by choosing $T_{net}$ and calculating $G_{net}^{\ln}$ , which do not need iterations; thus, the convergence performance of the proposed distributed optimization solution is determined by that of subproblem P2a.

Theorem 1

The iterations at each individual node in the first stage converge to an optimum $f_{i}^{*}$ .

Proof

According to the proposed distributed optimization solution, the optimization at each individual node is to seek the optimum of equation (6) obtained by the optimum $f_{i}^{*}$ . We introduce equations (12) and (13) to denote $W_{i} (f_{i}) = Y_{T_{i}} + Y_{f_{i}}$ , where $Y_{T_{i}}$ represents the set of the terms related to node lifetime, and $Y_{f_{i}}$ represents the set of the terms related to node throughput

\begin{matrix} Y_{T_{i}} = max_{f_{i}} α T_{i} + η \cdot δ^{SEP} (T_{i} - \frac{E_{i}}{P_{i}}) \\ + η \cdot δ^{SIP} [l (f_{i} + B_{i}) - T_{i}] \end{matrix}

(12)

\begin{matrix} Y_{f_{i}} = max_{f_{i}} (1 - α) \cdot λ_{f} \cdot \ln f_{i} \\ + η \cdot δ^{SIP} [\ln (f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p}) - \ln A] \end{matrix}

(13)

Assume that all constraints are satisfied, thus, $D_{k} (f_{i}) \leq 0, k = 2, 3$ . Note that $1 << l (f_{i} + B_{i}) << T_{i}$ , $\overset{\cdot}{l} (f_{i} + B_{i}) \geq 0$ , $\overset{\cdot\cdot}{l} (f_{i} + B_{i}) \leq 0$ , and $η, α$ are close.

Algorithm 1 Proposed distributed optimization solution
1. The first stage: distributed optimization of each individual node
2. Initialization
3. Set $n = 1$ for all $i, j$ ;
4. Fetch $H_{i}$ and $b_{i}$ stored in the local processor;
5. Receive $f_{i, 0}$ and ${a_{i}^{j}}$ from sensor nodes;
6. Calculate $f_{i, 0}$ according to $f_{i, 0} = H_{i} \cdot f_{i, 0}$ .
7. Repeat
8. Updating at theith node:
9. For the ith sensor node,
10. Fetch the random $v_{i, n - 1}$ of the ith sensor node;
11. Update the $f_{i, n}$ by equations (9a)–(9c).
12. For the ith sink node,
13. Update the $f_{i, n}$ by equation (9′).
14. end for
15. $n = n + 1$ .
16. Until the variable $f_{i, n}$ converges to the optimum $f_{i}^{*}$ .
17. Calculate $T_{i}^{}$ of all sensor nodes and $f_{i}^{}$ of all nodes according
18. To the definitions.
19. The second stage at the sink node
20. Receive $T_{i}^{}$ and $f_{i}^{}$ from all nodes;
21. Achieve the optimal solution to Problem P2 by equation (5).

Because ${\overset{\cdot}{δ}}^{SEP} (T_{i} - (E_{i} / P_{i})) = 0$ , the first-order derivative of equation (6) is

\begin{matrix} {\overset{\cdot}{W}}_{i} (f_{i}) = \frac{\partial W_{i}}{\partial f_{i}} = {\overset{\cdot}{Y}}_{T_{i}} (f_{i}) + {\overset{\cdot}{Y}}_{f_{i}} (f_{i}) \\ = 3 η D_{2} (f_{i})^{2} \cdot \overset{\cdot}{l} (f_{i} + B_{i}) \\ + E_{i} ξ P_{i} (f_{i})^{- 2} \cdot [3 η D_{2} {(f_{i})}^{2} - α] \\ + (1 - α) \frac{λ_{f}}{f_{i}} + 3 η D_{3} (f_{i})^{2} \cdot {\overset{\cdot}{D}}_{3} (f_{i}) \end{matrix}

Because $D_{2} (f_{i})^{2} >> 1$ and all parameters are positive, $3 η D_{2} (f_{i})^{2} - α > 0$ and ${\overset{\cdot}{D}}_{k} (f_{i}) \geq 0, k = 2, 3$ . Thus

\begin{matrix} {\overset{\cdot}{Y}}_{T_{i}} (f_{i}) = 3 η D_{2} (f_{i})^{2} \cdot \overset{\cdot}{l} (f_{i} + B_{i}) \\ + E_{i} ξ P_{i} (f_{i})^{- 2} \cdot [3 η D_{2} {(f_{i})}^{2} - α] \geq 0 \\ {\overset{\cdot}{Y}}_{f_{i}} (f_{i}) = (1 - α) \frac{λ_{f}}{f_{i}} + 3 η D_{3} (f_{i})^{2} \cdot {\overset{\cdot}{D}}_{3} (f_{i}) \geq 0 \end{matrix}

Hence, ${\overset{\cdot}{Y}}_{T_{i}} (f_{i}) \geq 0, {\overset{\cdot}{Y}}_{f_{i}} (f_{i}) \geq 0$ and ${\overset{\cdot}{W}}_{i} (f_{i}) = {\overset{\cdot}{Y}}_{T_{i}} (f_{i}) + {\overset{\cdot}{Y}}_{f_{i}} (f_{i}) \geq 0$ .

The second-order derivative of equation (6) is

\begin{matrix} {\overset{\cdot\cdot}{W}}_{i} (f_{i}) = & \frac{\partial^{2} W_{i}}{\partial {f_{i}}^{2}} = {\overset{\cdot\cdot}{Y}}_{T_{i}} (f_{i}) + {\overset{\cdot\cdot}{Y}}_{f_{i}} (f_{i}) \\ = 3 η D_{2} (f_{i}) [2 {\overset{\cdot}{D}}_{2} {(f_{i})}^{2} + D_{2} (f_{i}) \cdot \overset{\cdot\cdot}{l} (f_{i} + B_{i})] \\ + E_{i} ξ^{2} P_{i} (f_{i})^{- 3} \cdot [2 α - 6 η D_{2} {(f_{i})}^{2}] - (1 - α) \frac{λ_{f}}{{f_{i}}^{2}} \\ + 3 η D_{3} (f_{i}) [2 {\overset{\cdot}{D}}_{3} {(f_{i})}^{2} + D_{3} (f_{i}) \cdot {\overset{\cdot\cdot}{D}}_{3} (f_{i})] \end{matrix}

where ${\overset{\cdot\cdot}{D}}_{2} (f_{i}) = \overset{\cdot\cdot}{l} (f_{i} + B_{i}) - 2 E_{i} \cdot ξ^{2} \cdot P_{i} (f_{i})^{- 3}$ and ${\overset{\cdot\cdot}{D}}_{3} (f_{i}) = - (f_{i} + \sum_{p \in S} \sum_{(p, q) \in Ψ (j, i)} f_{q}^{p})^{- 2}$ .

Since $D_{2} (f_{i})^{2} >> 1$ and all parameters are positive, $2 α - 6 η D_{2} (f_{i})^{2} < 0$ and ${\overset{\cdot\cdot}{D}}_{k} (f_{i}) \leq 0, k = 2, 3$ . Thus

\begin{matrix} {\overset{\cdot\cdot}{Y}}_{T_{i}} (f_{i}) = 3 η D_{2} (f_{i}) [2 {\overset{\cdot}{D}}_{2} {(f_{i})}^{2} + D_{2} (f_{i}) \cdot \overset{\cdot\cdot}{l} (f_{i} + B_{i})] \\ + E_{i} ξ^{2} P_{i} (f_{i})^{- 3} \cdot [2 α - 6 η D_{2} {(f_{i})}^{2}] \leq 0 \\ {\overset{\cdot\cdot}{Y}}_{f_{i}} (f_{i}) = - (1 - α) \frac{λ_{f}}{{f_{i}}^{2}} + 3 η D_{3} (f_{i}) \\ \cdot [2 {\overset{\cdot}{D}}_{3} {(f_{i})}^{2} + D_{3} (f_{i}) \cdot {\overset{\cdot\cdot}{D}}_{3} (f_{i})] \leq 0 \end{matrix}

Hence, ${\overset{\cdot\cdot}{Y}}_{T_{i}} (f_{i}) \leq 0, {\overset{\cdot\cdot}{Y}}_{f_{i}} (f_{i}) \leq 0$ and ${\overset{\cdot\cdot}{W}}_{i} (f_{i}) = {\overset{\cdot\cdot}{Y}}_{T_{i}} (f_{i}) + {\overset{\cdot\cdot}{Y}}_{f_{i}} (f_{i}) \leq 0$ . ${\overset{\cdot}{W}}_{i} (f_{i})$ will converge to 0. ${\overset{\cdot}{W}}_{i} (f_{i}^{*}) = 0$ and ${\overset{\cdot}{W}}_{i} (f_{i}) > 0$ for all $f_{i} \neq f_{i}^{*}$ . In equation (6), $W_{i} (f_{i})$ increases with iterations and $W_{i} (f_{i}^{*})$ gets the optimum of equation (6). Therefore, the optimum of equation (6) and the optimum $f_{i}^{*}$ exist.

Considering another condition that the ith node is the sink node with infinite power, equation (6) is replaced by equation (6′). The first-order derivative of equation (6′) is

\overset{\cdot}{W}'_{i} (f_{i}) = \frac{\partial {W'}_{i}}{\partial f_{i}} = {f_{i}}^{- 1} + 3 η D_{3} (f_{i})^{2} \cdot {\overset{\cdot}{D}}_{3} (f_{i})

Because all the parameters are positive and $D_{k} (f_{i}) \leq 0, {\overset{\cdot}{D}}_{k} (f_{i}) \geq 0, k = 2, 3$

\begin{matrix} {f_{i}}^{- 1} \geq 0 \\ 3 η D_{3} (f_{i})^{2} \cdot {\overset{\cdot}{D}}_{3} (f_{i}) \geq 0 \end{matrix}

Hence, $\overset{\cdot}{W}'_{i} (f_{i}) \geq 0$ .

The second-order derivative of equation (6′) is

\begin{matrix} {\overset{\cdot\cdot}{W}'}_{i} (f_{i}) = \frac{\partial^{2} {W'}_{i}}{\partial {f_{i}}^{2}} = - {f_{i}}^{- 2} + 3 η \cdot D_{3} (f_{i}) \\ \cdot [2 {\overset{\cdot}{D}}_{3} {(f_{i})}^{2} + D_{3} (f_{i}) \cdot {\overset{\cdot\cdot}{D}}_{3} (f_{i})] \end{matrix}

Because all the parameters are positive and ${\overset{\cdot\cdot}{D}}_{k} (f_{i}) \leq 0, k = 2, 3$

\begin{matrix} - {f_{i}}^{- 2} \leq 0 \\ 3 η \cdot D_{3} (f_{i}) [2 {\overset{\cdot}{D}}_{3} {(f_{i})}^{2} + D_{3} (f_{i}) \cdot {\overset{\cdot\cdot}{D}}_{3} (f_{i})] \leq 0 \end{matrix}

Hence, $\overset{\cdot\cdot}{W}'_{i} (f_{i}) \leq 0$ .

It is clear that equation (6′) has the same derivative properties as equation (6); thus, the optimum of equation (6′) and the optimum $f_{i}^{*}$ at the sink node also exist.

Above all, this theorem is established.

Theorem 2

Starting from any sufficiently small $f_{i, 0}$ at the ith node, the proposed distributed optimization solution converges to the optimum $f_{i}^{*}$ in finite iterations.

Proof

In fact, equation (6) could be written as $W_{i} (f_{i}) = Y_{T_{i}} + Y_{f_{i}}$ at each sensor node. We take equations (9a)–(9c) to run iterations for the optimum $f_{i}^{*}$ . The iterative interactions between the nodes would finally end with a set of optimums, at which $W_{i} (\cdot)$ is maximized and equation (6) converges.

For the terms related to node lifetime, ${\overset{\cdot}{Y}}_{T_{i}} (f_{i}) \geq 0, {\overset{\cdot\cdot}{Y}}_{T_{i}} (f_{i}) \leq 0$ . It has ${\overset{\cdot}{Y}}_{T_{i}} (f_{i}^{*}) = 0$ and ${\overset{\cdot}{Y}}_{T_{i}} (f_{i}) > 0$ for all $f_{i} \neq f_{i}^{*}$ . $f_{i}$ continually increases as long as $f_{i} \neq f_{i}^{*}$ and terminates at $f_{i}^{*}$ , at which ${\overset{\cdot}{Y}}_{T_{i}} (f_{i}^{*}) = 0$ and $Y_{T_{i}} (f_{i}^{*})$ is maximized.

For the terms related to node throughput, ${\overset{\cdot}{Y}}_{f_{i}} (f_{i}) \geq 0, {\overset{\cdot\cdot}{Y}}_{f_{i}} (f_{i}) \leq 0$ and $Y_{f_{i}}$ is a concave increasing function, whose maximum corresponds to the optimum $f_{i}^{*}$ . Whenever $f_{i} \neq f_{i}^{*}$ , $f_{i, n}$ increases to next $f_{i, n + 1}$ such that $Y_{f_{i}} (f_{i, n + 1}) > Y_{f_{i}} (f_{i, n})$ .

When both $Y_{T_{i}}$ and $Y_{f_{i}}$ are maximized, the distributed optimization at the ith sensor node converges to $f_{i}^{*}$ .

When the ith node is the sink node, equations (6′)–(9′) replace equations (6)–(8) and (9a)–(9c), and the results still remain the same. Detailed proof for the sink node is omitted.

In addition, for easy comparison of the performance of PCB opportunistic routing with LEACH routing, to be detailed in section “Simulation results,” we propose the following lemma.

Lemma 1

The average cost $\bar{C}$ of all the nodes is directly proportional to network throughput $G_{net}$ .

Proof

According to definitions of $\bar{C}$ and $G_{net}$ , we know $G_{net}$ could be considered as the sum of sink node throughput $f_{i} (i \in R)$ , so the proportional relation between $\bar{C}$ and $G_{net}$ is the same as that between $\bar{C}$ and $f_{i}$ .

Differentiating $\bar{C}$ on $f_{i}$ , we get

\overset{\cdot}{\bar{C}} (f_{i}) = \frac{1}{N} \sum_{i \in V} [\overset{\cdot}{l} (f_{i} + B_{i}) \cdot f_{i} + l (f_{i} + B_{i})]

where all the variables and parameters are positive.

As we know $l (f_{i})$ is a concave increasing function of $f_{i}$ , thus, $\overset{\cdot}{l} (f_{i} + B_{i}) > 0$ and $l (f_{i} + B_{i}) \geq 0$ . $\overset{\cdot}{\bar{C}} (f_{i}) > 0$ . The average cost $\bar{C}$ of all the nodes is directly proportional to node throughput $f_{i}$ at the ith sink node. Hence, the average cost $\bar{C}$ of all the sensor nodes is directly proportional to network throughput $G_{net}$ .

Simulation results

In this section, we will evaluate the overall performance of PCB opportunistic routing scheme and the proposed distributed optimization solution. We consider static WSNs with 10 nodes randomly distributed in a square region of $50 m \times 50 m$ , as illustrated in Figure 1, where the 10th node is the sink, and the others are the sensor nodes. The sensor nodes follow the PCB opportunistic routing scheme to transmit sensor data to the sink node. Numerically, the values of all the related model parameters are tentatively listed in Table 1.

Table 1.

Configuration of model parameters in the WSN.

Para.	Description	Value
A	Capacity of the wireless shared medium	5 Mbps
N	Number of nodes	10
$E_{i}$	Initial power of the ith sensor node	1 MJ
$ε_{ij}$	Transmission energy cost of link $(i, j)$	0.8 J/Mb
$ξ$	Consumption cost of the radio receiver	0.2 J/Mb
$λ_{f}$	Adjustment coefficient of $G_{net}^{\ln}$	$1 \times 10^{6}$
$α$	Weighted system parameter	0.5
$μ$	Iteration step-size	1.15
$η$	Scalar weight of constraints’ importance	0.4

Convergence behavior of the proposed solution

In accordance with subproblem P2a, Figure 3 shows the convergence behavior of node lifetime and node throughput in Figure 1. Specifically, Figure 3(a) illustrates the iterations of each sensor node lifetime, and the convergence of each node throughput is shown in Figure 3(b). It can be seen that both the optimization goals can achieve optimal values after about 500 iterations. Based on the performance of node lifetime and node throughput optimization, it is obvious that the proposed distributed optimization solution can converge to a steady state after a relatively short period of time.

Impact of the dynamic network

In this section, we take Figure 1 and 2 as an example to study the network topology update of PCB opportunistic routing. Figure 2(a) and (b) shows network topology updates of PCB opportunistic routing under the condition that the node moves and the condition that the sensor node dies, respectively. Precisely, in contrast to Figure 1, the variation in Figure 2(a) is the locomotion of the second node, which results in its larger distance to the fifth node and losing communication with the eighth node. The sensor nodes, which detect the change, inform the sink node by multi-hop transmission, and then the sink node sends re-initialization messages to all the sensor nodes. Re-initialization starts, where the second node builds communication with the third node. After that, the next-hop selection process brings us some changes that the first node sends data to the fifth node instead of the second node, and the second node transmits data to the sixth node rather than the eighth node. Moreover, when compared to Figure 1, the change in Figure 2(b) is the death of the ninth sensor node. It leads to that the 6th node, the 7th node, the 8th node, and the 10th node could not communicate with the 9th node. Therefore, the fourth node becomes the fourth-level node and the seventh node is considered as the third-level node in re-initialization. Also, it is given by the next-hop selection strategy that the seventh node sends data to the sixth node, and the sixth node transmits data to the eighth node. To summarize, the performance of the network topology update in PCB opportunistic routing in Figure 2 demonstrates that PCB opportunistic routing is capable of handling the dynamic WSN.

Figure 2.

Topology of the changed WSN: (a) the topology of the WSN in Figure 1 changed by the locomotion of the second node and (b) the topology of the WSN in Figure 1 changed by the death of the ninth sensor node.

The comparisons of re-convergence behavior of the proposed solution and the Lagrange dual approach under the dynamic network are illustrated in Figures 4 and 5. Figure 4 is the comparison under the locomotion of the node, that is, Figure 2(a), and Figure 5 is the comparison under the death of the sensor node, that is, Figure 2(b). The final values of Figure 3(a) are the initial values of any sub-figure about the network lifetime in Figures 4 and 5, and the final values of Figure 3(b) are the initial values of any sub-figure about network throughput in Figures 4 and 5. Specifically, Figure 4(a) and (b) expresses iterations of each sensor node lifetime and each node throughput in the proposed solution under the locomotion of the node, respectively. Apparently, node lifetime re-converges to a steady state after about 6000 iterations and node throughput re-converges after about 8000 iterations. However, Figure 4(c) and (d) indicates that optimization goals do not converge after 10,000 iterations in the Lagrange dual approach. Moreover, Figure 5(a) and (b) shows iterations of each sensor node lifetime and each node throughput in the proposed solution under the death of the sensor node, respectively. Unlike Figure 4(a) and (b), node lifetime re-converges to a steady state after about 6500 iterations in Figure 5(a) and node throughput re-converges after about 7600 iterations in Figure 5(b). The death of the ninth sensor node results in smaller node lifetime optimums and node throughput optimums than the locomotion of the second node. The reason is that the death of the ninth sensor node increases the burden of other sensor nodes to forward data and more power would be consumed to shorten node lifetime. The death of the ninth sensor node also decreases the paths to the sink node and this would increase the delay lowering the transmission efficiency to decrease node throughput optimums. Nevertheless, the locomotion of the second node only adjusts the amount of forwarding data of other sensor nodes and adjusts transmission paths rather than increases the burden to forward data and decreases the paths to the sink node. Thus, it is lighter than the death of the ninth sensor node that the extent of decreasing node lifetime optimums and node throughput optimums brought by the locomotion of the second node. Meanwhile, Figure 5(c) and (d) indicates that optimization goals still do not converge after 10,000 iterations in the Lagrange dual approach. In conclusion, the results in Figures 4 and 5 demonstrate that the proposed distributed optimization solution outperforms the Lagrange dual approach at re-convergence under the dynamic network.

Figure 3.

Convergence behavior of the proposed distributed optimization solution: (a) iterations of node lifetime and (b) node throughput.

Figure 4.

Re-convergence behavior of the proposed distributed optimization solution and the Lagrange dual approach for the locomotion of the node in the WSN: (a) and (b) the re-convergence process of the proposed distributed optimization solution and (c) and (d) the re-convergence process of the Lagrange dual approach.

Figure 5.

Re-convergence behavior of the proposed distributed optimization solution and the Lagrange dual approach for the death of the sensor node in the WSN: (a) and (b) the re-convergence process of the proposed distributed optimization solution and (c) and (d) the re-convergence process of the Lagrange dual approach.

Tradeoff between network lifetime and throughput

The impact of the weighted system parameter $α$ on the tradeoff between the network lifetime maximum and network throughput maximum is illustrated in Figure 6, where Figure 6(a) and (b) shows the impact of $α$ on the network lifetime and network throughput, respectively. We can observe that as $α$ increases, the corresponding optimal network lifetime increases with the decrement of the optimal network throughput. On the contrary, the network lifetime decreases and network throughput increases with the decrement of $α$ . Figure 6(c) indicates the tradeoff between the network lifetime and throughput when $α$ varies. We can observe that when $α$ increases to an extremely large value, for example, $α = 0.99$ , the network lifetime approximately achieves its maximal value, since at this moment the network lifetime maximization problem is the dominant problem. For the same reason, when $α$ decreases to a relatively small value, for example, $α = 0.01$ , the original optimization problem transforms to the overall network throughput maximization problem. Finally, it should be noted that $α = 0.5$ in Figures 3, 4, and 7.

Figure 6.

Impact of weighted system parameter $α$ on (a) network lifetime, (b) network throughput, and (c) the tradeoff between network lifetime and network throughput.

Figure 7.

Comparison of PCB opportunistic routing, EL-LEACH routing, LEACH-R routing, and LEACH routing on different network scales: (a) variance of power consumption among sensor nodes, (b) average cost of nodes, (c) network lifetime, and (d) network throughput.

Impact of PCB opportunistic routing

To evaluate the impact of PCB opportunistic routing on the network lifetime, in Figure 7(a) and (c) we investigate the performance of variance $V_{P}$ of power consumption among the sensor nodes and network lifetime $T_{net}$ for different routing schemes, that is, PCB opportunistic routing, LEACH-R routing,⁶ EL-LEACH routing,⁹ and LEACH routing. The comparisons of average cost $\bar{C}$ of the nodes and network throughput $G_{net}$ in these four routings are illustrated in Figure 7(b) and (d) for analyzing the influence of PCB opportunistic routing on network throughput. Note that the proposed distributed optimization solution is implemented in Figure 7.

Smaller $V_{P}$ means more equal power consumption among the sensor nodes that brings larger $T_{net}$ . It is seen that PCB opportunistic routing obviously outperforms EL-LEACH routing, LEACH-R routing, and LEACH routing at $V_{P}$ and $T_{net}$ . Precisely, $V_{P}$ in PCB opportunistic routing is 33% smaller than EL-LEACH routing, 49% smaller than LEACH-R routing, and 67% smaller than LEACH routing. $T_{net}$ of PCB opportunistic routing is also 25% larger than EL-LEACH routing, 43% larger than LEACH-R routing, and 78% larger than LEACH routing regardless of the network scale. Moreover, as the network scale increases, $T_{net}$ becomes smaller with the increment of $V_{P}$ . However, no matter what the network scale is, larger $\bar{C}$ leads to higher $G_{net}$ , which conforms to Lemma 1. $G_{net}$ of PCB opportunistic routing is only 3% lower than LEACH routing since $\bar{C}$ in PCB opportunistic routing stays 5% smaller than LEACH routing. On the other hand, $G_{net}$ of PCB opportunistic routing is 18% higher than EL-LEACH routing and 11% higher than LEACH-R routing. $\bar{C}$ in PCB opportunistic routing is 20% larger than EL-LEACH routing and 14% larger than LEACH-R routing. In addition, as the network scale increases, $G_{net}$ becomes higher with the increment of $\bar{C}$ .

Impact of network scale

To evaluate the impact of the network scale, we vary the size of networks and accordingly realize PCB opportunistic routing and the proposed distributed optimization solution over larger networks, where 20 and 30 nodes are randomly located in square regions of $80 m \times 80 m$ and $100 m \times 100 m$ , respectively. In addition, the comparison of the achieved network lifetime and throughput on different network scales is shown in Figure 7(c) and (d). We observe that as the network scale increases, the duty of data transmission at each sensor node becomes heavier, and thus sensor nodes will consume higher power in data transmission and reception, which results in the performance with higher network throughput and shorter network lifetime.

Concluding remarks

In this article, we have investigated the tradeoff optimization between the network lifetime and throughput for dynamic WSNs. By the PCB opportunistic routing scheme, which could cope with the dynamic network and aims to prolong the network lifetime, and the proposed distributed optimization solution, which can tackle the changing network, we solve the tradeoff topic in a fully distributed manner. The convergence of the proposed solution was mathematically proved and its computational complexity was analyzed as well. Extensive numerical and simulation experiments evaluated the effectiveness of the proposed PCB opportunistic routing scheme on dealing with the varying network and achieving longer network lifetime by comparing with the existing routing schemes, and we demonstrate that the proposed distributed optimization solution can provide the best tradeoff performance in dynamic network settings and has better ability to adapt the changing network than the Lagrange dual approach. Besides, the PCB opportunistic routing scheme and the proposed solution both well support different network scales.

Footnotes

Academic Editor: Federico Barrero

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: The work was supported in part by the NSFC, under grant numbers 61472234, 61271211 and 61622112.

References

Madan

Lall

Distributed algorithms for maximum lifetime routing in wireless sensor networks. IEEE T Wirel Commun 2006; 5(8): 2185–2193.

Lee

Guan

Distributed algorithms for network lifetime maximization in wireless visual sensor networks. IEEE T Circ Syst Vid 2009; 19(5): 704–718.

Cetin

Prasad

. A novel linear programming formulation of maximum lifetime routing problem in wireless sensor networks. In: Proceedings of 7th international on wireless communications and mobile computing conference (IWCMC), Istanbul, Turkey, 4–8 July 2011, pp.1865–1870. New York: IEEE.

Wang

Yang

. Network lifetime maximization with cross-layer design in wireless sensor networks. IEEE T Wirel Commun 2008; 7(10): 3759–3768.

Zhu

Chen

Bensaou

. Tradeoff between lifetime and rate allocation in wireless sensor networks: a cross layer approach. In: Proceedings of IEEE INFOCOM 2007, Anchorage, AK, 6–12 May 2007, pp.267–275. New York: IEEE.

Zhang

Liang

. Improvement of Leach protocol for wireless sensor networks. In: Proceedings of third international conference on instrumentation, measurement, computer, communication and control (IMCCC), Shenyang, China, 21–23 September 2013, pp.322–326. New York: IEEE.

Haneef

Zhou

Deng

. MG-LEACH: multi group based LEACH an energy efficient routing algorithm for wireless sensor network. In: Proceedings of 14th international conference on advanced communication technology (ICACT), PyeongChang, South Korea, 19–22 February 2012, pp.179–183. New York: IEEE.

Ghasemzadeh

Rezaeian

Touranposhti

. BN-LEACH: an improvement on LEACH protocol using Bayesian networks for energy consumption reduction in wireless sensor networks. In: Proceedings of 7th international symposium on telecommunications (IST), Tehran, Iran, 9–11 September 2014, pp.1138–1143. New York: IEEE.

Quynh

Phung

Quoc

. Improvement of energy consumption and load balance for LEACH in wireless sensors networks. In: Proceedings of international conference on ICT convergence (ICTC) 2012, Jeju Island, Korea, 15–17 October 2012, pp.583–588. New York: IEEE.

10.

Ahmad

Javaid

Khan

. ((ACH)²): routing scheme to maximize lifetime and throughput of wireless sensor networks. IEEE Sens J 2014; 14(10): 3516–3532.

11.

Fida

Tuah

Ngo

. Throughput optimization of wireless sensor networks in presence of Rician fading channel. In: Proceedings of 5th Brunei international conference on engineering and technology (BICET 2014), Bandar Seri Begawan, Brunei, 1–3 November 2014.

12.

Sappidi

Girard

Rosenberg

Maximum achievable throughput in a wireless sensor network using in-network computation for statistical functions. IEEE ACM T Network 2013; 21(5): 1581–1594.

13.

Verdone

Fabbri

Buratti

Maximizing area throughput in clustered wireless sensor networks. IEEE J Sel Area Comm 2010; 28(7): 1200–1210.

14.

Liu

Wang

. On the throughput capacity of wireless sensor networks with mobile relays. IEEE T Veh Technol 2012; 61(4): 1801–1809.

15.

Xie

Wei

Wang

. Tradeoff between throughput and energy consumption in multirate wireless sensor networks. IEEE Sens J 2013; 13(10): 3667–3676.

16.

Ren

Liang

Throughput and energy-efficiency-aware protocol for ultrawideband communication in wireless sensor networks: a cross-layer approach. IEEE T Mobile Comput 2007; 7(6): 805–816.

17.

Yang

Weber

Adapting wardrop equilibrium to facilitate optimal routing in wireless ad hoc networks. In: Proceedings of IEEE international symposium on a world of wireless, mobile and multimedia networks (WoWMoM) 2011, Lucca, Italy, 20–24 June 2011.

18.

Miettinen

Nonlinear multiobjective optimization. Norwell, MA: Kluwer Academic Publishers, 1999.

19.

Yuen

Liang

A distributed framework for correlated data gathering in sensor networks. IEEE T Veh Technol 2008; 57(1): 578–593.

20.

Towfic

Sayed

AH.

Adaptive penalty-based distributed stochastic convex optimization. IEEE T Signal Proces 2014; 62(15): 3924–3938.

21.

Kar

Sarkar

Tassiulas

A scalable low-overhead rate control algorithm for multirate multicast sessions. IEEE J Sel Area Comm 2001; 20(8): 1541–1557.

22.

Deb

Srikant

Congestion control for fair resource allocation in networks with multicast flows. IEEE ACM T Network 2004; 12(2): 274–285.