An Online Relay Selection Scheme in Power Controllable Wireless Sensor Networks

Abstract

We propose a data forwarding scheme termed dynamic energy-based relaying (DER) for wireless sensor networks (WSNs). In the DER scheme, all nodes try to forward their data packets toward the nodes that are optimal distance closer to the data sink. They also take the relaying node estimated lifetime into consideration in the selection process. When necessary, they will choose nodes that are closer to the data sink as relays or even the data sink itself. This distributed approach equalizes energy consumption of different relaying nodes based on their residual energy, balancing their expected lifetimes. We analyze our proposed scheme in both one-dimensional and two-dimensional networks with different setups including different residual energy, traffic rate, and network regions. Our study shows that the proposed scheme achieves a network lifetime close to the scheme based on linear programming techniques and global information or centralized processing.

1. Introduction

Wireless communication has become ubiquitous with the development of miniature wireless devices. The substantially reduced size of wireless devices makes it possible to deploy wireless networks with large populations. One such example is wireless sensor networks (WSNs) [1]. In WSNs, a large number of small sensors are deployed to a field to accomplish the goal of autonomous event detection and data gathering. The sensed results should be transmitted toward data sinks, which serve as the interface between the network and a human. Depending on the nature of WSN applications, single or multiple data sinks are possible.

Large wireless networks, such as WSNs, are expected to have profound technological and economic impacts on our society. Their success is nonetheless determined by whether they can efficiently deliver information from target areas toward data sinks. This task is complicated by severe energy constraints of sensors in WSNs. In the tiny sensors, the size and energy reserve of the sensor battery are extremely limited. Battery replacement or recharge can be difficult. Therefore, use of the limited energy should be planned carefully [2].

In this work, we focus on the delivery of sensing data from the sensors toward a data sink in WSNs. We investigate the types of WSNs with relatively low rate of data generation so that transmission competition is not an issue or can be resolved by other mechanisms [3]. While a sleeping technique may be useful to put some sensors to a state of minimum energy usage, we believe that the fundamental problem of data forwarding remains in WSNs. In other words, how should the active sensors deliver sensing data toward the data sink?

Our main contribution in this work is a new data forwarding scheme. Our scheme takes advantage of the information that sensor nodes find out during previous one-hop transmissions. These include one node estimated lifetime and those of the potential relays, one of which is the optimal relay based on the overall energy consumption of the traffic by the sender alone. With the use of such information, nodes can make their local decisions to choose which of the potential relays to help them forward data packets. Our dynamic and distributed router selection technique can balance the node lifetime on the fly regardless of traffic generation, residual energy, or even node movements. On the contrary, linear programming solutions require global information and centralized processing, which are commonly considered difficult and costly to obtain in WSNs. For example, any change in node sleep/active status, membership, or failure will trigger a new round of global information update and traffic forwarding pattern recomputation and distribution.

The rest of the paper is organized as follows. Section 2 summarizes related work. In Section 3, we formulate the problem and investigate the optimal forwarding distance in both 1D and 2D WSNs. We further generalize several forwarding rules to be used in the performance evaluation. In Section 4, we introduce the DER scheme and investigate its properties in various network settings. In Section 5, we evaluate DER performance. Section 6 concludes our work.

2. Related Work

Sensor networks have been an active research field in recent years. Lots of research was focused on efficient information forwarding with different constraints [2, 4, 5]. Many studies focused on routing, such as sensor protocols for information via negotiation (SPIN) scheme by Kulik et al. [6], geographic and energy aware routing (GEAR) by Yu et al. [7], and the low-energy adaptive clustering hierarchy (LEACH) protocol by Heinzelman et al. [8]. Directed diffusion [9] employs initial data flooding and gradual reinforcement of better paths to deliver information from sensors toward observers. Chang and Tassiulas [10] combined two metrics, residual power and energy cost of sending packets, to evaluate and choose routes for data forwarding in sensor networks. Their main idea is to avoid nodes with low residual energy and to favor short hops. Different to their approach, our proposed technique chooses an appropriate transmission distance (range) based on the comparison of estimated lifetime among the sender and the potential relays. Elhafsi and Simplot-Ryl proposed orthogonal routing (ORouting) [11], which is a localized energy-efficient greedy routing scheme. ORouting allows a sender to choose a forwarding node that is the closest to the line connecting the sender and destination pair. Being a greedy algorithm, ORouting is energy efficient but suffers from the hotspot problem [12], which is the main focus in our work. Backpressure routing was proposed and investigated in [13], which eliminates the route establishment procedure [14].

Our approach is also different from [15, 16], which focus on the design of medium access control techniques and sleeping schedules in low-duty WSNs. Interestingly, our DER scheme can be implemented in low-duty WSNs, where some of the sensors should be put to sleep in order to further extend the network lifetime. This is similar to the application of the DER scheme in dynamic networks.

The benefits of using mobile relays were investigated in [17]. The few mobile relays were assumed to be more resourceful, a different assumption to ours. In [18], the problem of optimum relay placement was investigated with one of the goals of maintaining global connectivity. The energy cost and its effect on network lifetime of public key encryption were investigated in [19]. A chaotic oscillator model was used to devise a relay strategy in WSN in [20].

Our work is closely related to the “hotspot” problem, meaning that those nodes closer to the sink will die faster than others. There are many approaches to address this problem. One is linear/integer programming based. The problem of maximizing lifetime subject to certain constraints of source-destination information rates was first formulated as a linear programming problem in [10]. The authors in [2, 21, 22] considered similar linear/integer programming formulations. Another approach is taking advantage of mobility. The authors in [23] generalized this idea and made both the sink and some relay nodes mobile. The authors in [24] used a mobile sink to transport data instead of allowing the sensor nodes to transmit, which may not be feasible in many situations. The authors in [25] used a very simple approach of adding more nodes near the sink, provided that we have some control over the node density in a network. However, this is not feasible if sensors are randomly deployed. Powell et al. [26] used a random selection technique to balance the energy of sensor nodes with different initial energy in the same slice of WSNs. Perillo et al. [12, 27] employed a more intelligent transmission power control policy, such as longer transmission range for nodes that are farther away from the data sink. They also used clustering techniques mixed with transmission power control. It was shown that the benefit of employing such a policy is rather limited. Efthymiou et al. [28] considered forwarding rules. In each step, when a node needs to forward data, it randomly makes the decision of sending either to the next hop or directly to the sink. Ferrara et al. designed and evaluated MACRO to find optimum forwarding nodes [29]. A cross-layer approach from physical layer to transport layer, termed XLP, was proposed in [30]. Different from our approach, XLP is based on receiver-contention and simple threshold comparison. ALBA was proposed in [31] to address traffic congestion in medium-high traffic-load networks with a combined strategy of geographic routing and MAC. In [32], security and energy consumption issues of short hops were addressed by outer space routing that might consume more energy globally. On the contrary, our approach is to dynamically adjust the forwarding distance of each node based on estimated lifetime comparison.

Another closely related work is [33], in which a multihop/direct forwarding (MDF) scheme was proposed and evaluated for static WSNs. In the MDF scheme, sensor nodes will forward data packets to either the node locating at the optimal distance ( $h^{*}$ ) from itself or the data sink directly. The transmission ratio of these two branches helps to balance the energy consumption and thus node lifetimes. The main difference of our work and [33] is that the scheme in [33] requires the knowledge of each node distance toward the data sink and that of the farthest node. We argue that such distance information is unavailable in many WSNs, especially networks that are more dynamic. The proposed DER scheme in our paper is expected to work well in dynamic networks.

Our work is also related to the problem of optimizing transmission range in wireless networks [34–36] and hop selection [37]. In this work, the wireless network was assumed to have high node density and consist of nodes with relatively low mobility and short transmission range. As justified by the assumption of high node density, the authors further assumed that intermediate router nodes are always available at the desired location whenever they are needed.

3. Problem Formulation and Preliminaries

3.1. Problem Formulation

WSN main goal is to collect information and transmit it to the sink, but data transmission consumes extra energy compared to idling. We simplify the following relay node selection problem from various WSN settings (some of these assumptions, such as 1D network and homogeneous traffic rate, will be removed in our later discussions. Furthermore, our initial investigation focuses on static networks and we will evaluate the performance of our proposed scheme in dynamic networks in Section 5).

Problem 1.

In a WSN with N nodes and one common data sink, each node generates λ packets per unit time. How should the sensors choose their relays in order to maximize the network lifetime of the WSN?

We establish the following notations.

• (i)

N is the total number of nodes, excluding the data sink. Nodes are indexed as $i=\mathrm{1,2},\dots ,N$ .

(ii)

$T_{i,j}$ is the the traffic rate (Traffic rate is measured in packets per time unit) sent from node i to node j, $i,j=\mathrm{0,1},\dots ,N$ . $T_{i,i}=0$ . $T_{i,j}$ may not be an integer.

(iii)

$T_i$ is the the total traffic rate sent out from node i, $i=\mathrm{1,2},\dots ,N$ .

(iv)

$d(i,j)$ is the distance between node i and node j.

(v)

Power consumption of sending one packet from node i to node j is

$$\begin{array}{cc}& E=k_0+{\left[d\right(i,j\left)\right]}^{\omega },\end{array}$$

(1)

where $\omega$   is the path loss exponent and assumed to be 2 in this work. We call $k_0$ the energy constant, which includes all power consumption of transmission that is unrelated to transmission distance, such as circuit processing consumption. (Note that $k_0$ has been normalized in such a way that the coefficient of the $[d(i,j){]}^2$ term is 1. In this case, the time unit has been modified accordingly).

(vi)

$E_i$ is the energy consumption of node i (to send out data packets):

$$\begin{array}{cc}& E_i={\sum }_{j=0}^N‍T_{i,j}\left[k_0+{\left[d\left(i,j\right)\right]}^2\right].\end{array}$$

(2)

(vii)

ℰ is the maximum node energy consumption.

(viii)

$\bar{E}$ is the average energy consumption of all nodes.

We make the popular assumption that sensors are assumed to consume similar amount of energy in idle and reception mode. Transmission modes consume more energy, and in this work we modeled and investigated this extra amount of energy in a similar way to [8]. (The transmit/receive/sleep energy consumption was modeled as 24.75 mW, 13.5 mW, and 15 μW in [30]. Since we assume that nodes have synchronous sleep cycles, all awake nodes consume similar amount of energy except the transmitters, which consume 11.25 mW more energy than other (awake) nodes. In [30], no change of transmission power was modeled. Here we model different transmission powers as well as transmission ranges based on the path-loss exponent (see Figure 14). The MicaZ mote is a good example of this kind, which consumes 15.3 and 31.3 mW of energy when transmit level is at 3 and 31 (maximum), resp. [38].) We further assume that each node is able to change its transmission range by adjusting the transmission power [39]. Their maximum transmission range is limited by a threshold, $R_{\max \hspace{0.17em}}$ [8]. This parameter will affect the selection of ℓ to be defined in Section 4. Node location information, which only needs to run once in static networks, can be obtained through different techniques [40, 41]. Although nodes may go to sleep to conserve energy or wake up to deliver messages at any time, for simplicity, we assume that they follow the same pre-defined sleep/wake-up cycle.

We first introduce our definition of network lifetime, which is measured as the time when the first node runs out of battery energy. Other network lifetime definitions are possible, such as the time when α, $0<\alpha \le 1$ , of all nodes run out of battery energy. We will investigate these different network lifetimes in Section 5.

Let $E_i^{\text{initial}}$ be the initial energy at node i. It is clear that network lifetime L is bounded by

$$\begin{array}{cc}& L\cdot E_i\le E_i^{\text{initial}}\hspace{1em}\forall i=\mathrm{1,2},\dots N,\end{array}$$

(3)

where $E_i$ is given by (2) and $i=\mathrm{1,2},\dots ,N$ .

The goal is to find the maximum L subject to (3) and

$$\begin{array}{cc}& {\sum }_{j=1}^N‍T_{j,i}+\lambda ={\sum }_{j=0}^N‍T_{i,j}.\end{array}$$

(4)

This is a linear programming problem with constraints on each node traffic flow, as pointed out by Perillo et al. [27]. We propose a distributed scheme in Section 4 instead. In our proposed scheme, each of the nodes only needs to obtain feedback from its relays and adjust its forwarding strategy accordingly. But first, we look at a simplified version of the problem.

3.2. Optimal Forwarding Distance in 1D Networks

In this subsection, we focus on WSNs where sensor nodes are evenly distributed on a straight line. In other words, the nodes form a chain as illustrated in Figure 1. The data sink is located at one end of the line. All nodes have the same data generation rate $\lambda =1$ .

Figure 1

Illustrations of the CF, the DF, and the MF schemes in a one-dimensional network. Nodes are assumed to be evenly distributed. In the CF scheme, nodes send to the closest neighbor. Direct transmissions toward the data sink are employed in the DF scheme. In the MF scheme, multihop forwarding is used with hop distance of h units.

Based on overall energy consumption, the optimal hop distance can be shown to be [33, 36]

$$\begin{array}{cc}& h^{*}\approx {\left(k_0\right)}^{1/2}.\end{array}$$

(5)

(Note that such an optimality is referred to as the best transmission range that will minimize the overall energy consumption of forwarding traffic toward the sink. As we will explain in the following sections, such a distance may not be the best distance when considering lifetime. For instance, employing such an “optimal” transmission range will cause the “hotspot” problem. In our proposed scheme, this “optimal” transmission range will be employed only when it will not cause the early depletion of the relay node) In a chain network shown in Figure 1, the hop distance must be positive integers, and therefore

$$\begin{array}{cc}& h^{*}\approx \max \left(1,{\left(k_0\right)}^{1/2}\right),\end{array}$$

(6)

where $〈·〉$ represents rounding to the closest integer.

Such an optimal transmission range may be interpreted as follows: when h is higher than $h^{*}$ , the energy consumption of each hop increases due to the exponential path loss, wasting energy in each hop. However, when h is lower than $h^{*}$ , more hops are needed in order to reach the destination, consuming more energy because of the term $k_0$ . We will exploit such an optimal transmission range in our proposed scheme in Section 4.

The above optimal transmission range minimizes the total energy consumption to send data packets from one node toward the data sink. However, it does not provide insights in network lifetime defined as the time when the first node runs out of energy.

Consider the node with i unit distance to the data sink in an N-node chain network. When a transmission range of h is employed by all nodes, the total traffic rate forwarded by node i is $\lfloor (N-i)/h\rfloor +1$ . The total energy consumption of this node is

$$\begin{array}{cc}& E_i=\left(\lfloor \frac{N-i}{h}\rfloor +1\right)\left(k_0+h^2\right)\approx \left(\frac{N-i}{h}+1\right)\left(k_0+h^2\right).\end{array}$$

(7)

Thus, the average energy consumption of all nodes can be calculated as the average of $E_i$

$$\begin{array}{cc}& \bar{E}=\left(\frac{1}{h}\frac{(N-1)}{2}+1\right)\left(k_0+h^2\right)\approx \frac{1}{h}\frac{\left(N-1\right)}{2}\left(k_0+h^2\right),\end{array}$$

(8)

since N is usually large. Optimizing $\bar{E}$ with respect to h, we obtain the optimal transmission range $h^{*}$ as given by (5). Thus, (5) indeed minimizes the average energy consumption.

Next we calculate the optimal transmission for those nodes in hotspot. One can observe that those nodes close to the source will forward large amounts of packets and may consume a lot of energy. Thus, it is reasonable to assume that, for those nodes in hotspot, $(N-i)/h\gg 1$ . Then, (7) reduces to $((N-i)/h)(k_0+h^2)$ . Again, optimizing E with respect to h, we obtain the optimal transmission range $h^{*}$ as given by (5).

3.3. Some Special Forwarding Schemes

We study several special forwarding schemes in an N-node chain network summarized in Table 1 (see Figure 1). These results have been published in [33]. We include them here for the completeness of our work.

Table 1

Different forwarding schemes discussed in this paper.

Scheme	Details
LPF	Forwarding scheme based on linear programming
CF	The Closest forwarding scheme
DF	The Direct forwarding scheme
MF	The multihop forwarding scheme
GF	The genie forwarding scheme

The linear programming forwarding (LPF) scheme is the forwarding rule derived from linear programming as in (3). The energy consumption of the LPF scheme serves as a realistic lower bound for our study.

In the closest forwarding (CF) scheme, a node only forwards its traffic to its closest neighbor toward the data sink. Therefore, $T_{i,j}=0$ except when $i-j=1$ . When $k_0$ is close to 0, the CF scheme consumes the least overall energy. The energy consumption of nodes, however, is unbalanced. For node i, $E_i^{(\text{CF})}=(N-i+1)(k_0+1^2)$ , where $i=\mathrm{1,2},\dots ,N$ . The maximum node energy consumption occurs at node 1, ${ℰ}^{(\text{CF})}=N(k_0+1)$ .

In the direct forwarding (DF) scheme, all nodes forward their traffic directly to the data sink. Therefore, $T_{i,j}=0$ except when $j=0$ . Similarly to the CF scheme, the energy consumption of nodes in the DF scheme is unbalanced either. Node energy consumption increases with the distance from the data sink. For node i, $E_i^{(\text{DF})}=k_0+i^2$ , where $i=\mathrm{1,2},\dots ,N$ . The maximum node energy consumption occurs at node N,   ${ℰ}^{(\text{DF})}=k_0+N^2$ .

In the multi-hop forwarding (MF) scheme, all traffic is sent through the optimal hop distance, $h^{*}$ given by (6), toward the data sink. The MF scheme is similar to the CF scheme except that nodes do not send to their closest neighbors. Therefore, $T_{i,j}=0$ except when $i-j=h$ or when $i<h$ and $j=0$ .

In the MF scheme, node energy consumption increases as node index decreases, depending on the number of other nodes sending traffic through it. Node i receives $\lfloor (N-i)/h\rfloor$ packets from nodes that are farther away from the data sink, where $\lfloor x\rfloor$ is the floor function returning the largest integer that is not larger than x. Therefore, node i will send out $\lfloor (N-i)/h\rfloor +1$ packets. The energy consumption of node i is then

$$\begin{array}{cc}& E_i^{\left(\text{MF}\right)}=\left[k_0+\min {\left(h,i\right)}^2\right]\cdot \left(\lfloor \frac{N-i}{h}\rfloor +1\right),\end{array}$$

(9)

where $i=\mathrm{1,2},\dots ,N$ and the min function represents those nodes that are less than h units from the data sink. The maximum node energy consumption is

$$\begin{array}{cc}& \begin{array}{c}{\mathcal{E}}^{\left(\text{MF}\right)}=\max \left[\left(q+1\right)\left(k_0+p^2\right),q\left(k_0+h^2\right)\right],\end{array}\end{array}$$

(10)

where p is the remainder and q the quotient when N is divided by h.

In the genie forwarding (GF) scheme, there exists a genie who is able to redistribute the energy among the N nodes without any extra cost. Therefore, the residual energy of all N nodes is always balanced. The GF scheme is similar to the MF scheme, except that the GF scheme has a cost-free energy-balancing genie. We can imagine this scheme to be operating in a network where all nodes share a virtual massive battery. Its node energy consumption serves as an unrealistic lower bound in our study.

Similarly to the MF scheme, the prebalanced energy consumption of node i is

$$\begin{array}{cc}& E_i^{\left(\text{GF}\right)}=\left[k_0+\min {\left(h,i\right)}^2\right]\cdot \left(\lfloor \frac{N-i}{h}\rfloor +1\right),\end{array}$$

(11)

where $i=\mathrm{1,2},\dots ,N$ . Due to the energy-balancing activity performed by the genie, all the nodes consume the same amount of energy. Therefore, the maximum and average node energy consumption are the same, as

$$\begin{array}{cc}& \begin{array}{c}\begin{array}{c}{\mathcal{E}}^{\left(\text{GF}\right)}={\bar{E}}^{\left(\text{GF}\right)}=\frac{{\sum }_{i=1}^N‍E_i^{\left(\text{GF}\right)}}{N}.\end{array}\end{array}\end{array}$$

(12)

We calculated energy consumption of different nodes in four of these special forward rules (the CF, the DF, the MF, and the GF schemes) and showed them in Figure 2. These were numerical results for a 1D network with 200 nodes. Node energy consumption of the DF scheme increases exponentially with node index (distance from the data sink). The CF scheme exhibits a reversed trend, that is, node energy consumption decreases as node index increases (Puccinelli and Haenggi [37] suggested against the use of short-hop routings). Compared to the CF and the DF scheme, the MF scheme leads to a much more balanced energy consumption for the nodes. Still, a declining trend as i increases can be seen. The GF scheme results in an efficient and balanced energy consumption for all nodes. This, however, is achieved by the genie.

Figure 2

Comparison of node energy consumption for the CF, the DF, the MF, and the GF schemes ( $N=200$ , $k_0=100$ ).

3.4. Optimal Forwarding Distance in 2d Networks

The same optimal transmission range as in (5) can be obtained in a 2d wireless network. We assume that the network is deployed as a circular sector with angle θ and the data sink is located at the apex (in practice, this might not be true; however, most shapes of the networks with one data sink not locating in networks can be approximated as a circular sector). All nodes with the same distance to the data sink have the same forward traffic rate. This can be achieved by the means of traffic balancing among these nodes. The density of the network is ρ.

Let $R_{2D}$ denote the distance between the farthest node and the data sink. Consider all nodes d unit distance away from the data sink, as shown as the inner arc in Figure 3. Let $\delta x$ be a small distance away from the arc. Then there are $\rho \theta d\delta x$ nodes in this small region between the outer and inner arcs. When a transmission range of h is used, the total traffic rate forwarded by all nodes on the inner arc (including their own traffic) is

$$\begin{array}{c}\rho \theta \delta xd+\rho \theta \delta x\left(d+h\right)+\cdots +\rho \theta \delta x\left(d+\lfloor \frac{R_{2D}-d}{h}\rfloor h\right)\\ \hspace{1em}\hspace{1em}=\rho \theta \delta x[\left(\lfloor \frac{R_{2D}-d}{h}\rfloor +1\right)d\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\frac{1}{2}\left(\lfloor \frac{R_{2D}-d}{h}\rfloor +1\right)\lfloor \frac{R_{2D}-d}{h}\rfloor h]\\ \hspace{1em}\hspace{1em}=\rho \theta \delta x\left(\lfloor \frac{R_{2D}-d}{h}\rfloor +1\right)\left[d+\frac{1}{2}\lfloor \frac{R_{2D}-d}{h}\rfloor h\right]\\ \hspace{1em}\hspace{1em}\approx \rho \theta d\delta x\left(\frac{R_{2D}-d}{h}+1\right)\left(1+\frac{R_{2D}-d}{2d}\right)\\ \hspace{1em}\hspace{1em}\approx \rho \theta d\delta x\left(\frac{R_{2D}-d}{2d}\right)\left(1+\frac{R_{2D}-d}{h}\right).\end{array}$$

(13)

The estimate on the last line holds if $R_{2D}$ is large and d is small. Since all nodes forward this traffic rate evenly, the total traffic forwarded by any node on the inner arc should be the above expression divided by $\rho \theta d\delta x$ . Therefore, the total energy consumption of this node to send the information is

$$\begin{array}{cc}& E\approx \left(\frac{R_{2D}-d}{2d}\right)\left(1+\frac{R_{2D}-d}{h}\right)\left(k_0+h^2\right).\end{array}$$

(14)

Again, when we optimize the average energy consumption or the energy consumption for a node in hotspot with h, we obtain the same optimal transmission range $h^{*}$ as that in (5).

Figure 3

A 2d network deployed as a circular sector.

The above argument suggests that when one deploys the sensors with the same transmission range, the optimal transmission range given in (5) should be used to minimize energy consumption, especially, for those nodes in hotspot. (It is possible that no relay is $h^{*}$ distance closer to the data sink from the sender in the 2d network. Instead, one can find one in the neighborhood to serve as the relay.) Thus, we will present our technique with $h^{*}$ in (5) as the initial transmission range for each node and allow it to adjust the range independently. Such an adjustment is necessary to reduce the energy consumption of the nodes in hotspot and extend the overall network lifetime.

4. Problem Formulation and Scheme Design

We observe that the MF scheme, while energy efficient in forwarding the traffic for each of the nodes, suffers from the “hotspot” issue. That is to say, nodes that are closer to the data sink generally send out more traffic than those that are farther away. In order to balance this energy consumption and maintain energy efficiency, we propose the DER scheme.

4.1. Operational Details of the DER Scheme

The main idea of the DER scheme is that each node will send packets to a relay that is $h^{*}$ distance closer to the data sink. (Note that we have chosen $h^{*}$ based on the MF scheme. Such a distance might not be optimal in the DER scheme because of the different traffic split schedule. However, as we will show in Section 5 that our selection leads to a DER performance that is close to the LPF scheme, which is considered optimal but limited by its linear programming and global computation requirement.) This relaying node serves as the optimal relay. However, when the optimal relay has a shorter estimated lifetime than the sender, the sender should send to nodes that are even closer to the data sink than the optimal relay. The underlying reason of doing so is to balance the lifetime of the sender and the optimal relay, which has been demonstrated through our analysis in Section 3. For the sender, an increased forwarding distance consumes more energy, lowering its estimated lifetime. For the optimal relay, the decreased incoming traffic helps to reduce its energy consumption, increasing its estimated lifetime. Such a dynamic process is run throughout the network lifetime.

Denote by $\ell \ge 2$ the number of nodes to which a node considers to relay its traffic. We choose the set of nodes that are $h^{*}$ -distance-spaced consecutively. Term the source node node i (see Figure 4). The potential relays of the traffic from node i include

$$\begin{array}{cc}& ID\left(i,1\right),ID\left(i,2\right),\dots ,ID\left(i,\tau \right),\dots ,ID\left(i,\mathcal{l}\right),\end{array}$$

(15)

where

$$\begin{array}{c}ID\left(i,\tau \right)=\arg \underset{j=\mathrm{0,1},\dots ,N}{\min }\left[\left|d\left(i,0\right)-d\left(j,0\right)-\tau h^{*}\right|\right]\\ =\arg \underset{j=\mathrm{0,1},\dots ,N}{\min }\left[|d\left(i,j\right)-\tau h^{*}|\right],\end{array}$$

(16)

for $\tau =\mathrm{1,2},\dots ,\ell$ . Therefore, $ID(i,\tau )$ represents the index of the node whose distance to the sink is the closest to $d(i,0)-\tau h^{*}$ . If more than one node satisfies (16), one is randomly chosen.

Figure 4

Illustration of the DER scheme in 1D networks. Node i forwards traffic to node $ID(i,1)=i-h^{*}$ or $ID(i,\tau )=i-\tau h^{*}$ , where $\tau =\mathrm{2,3},\dots ,\ell$ and $\ell =\mathrm{2,3},\dots$ .

A special case is that, when $\tau >i/h^{*}$ , $ID(i,\tau )=0$ . In the 1d chain network as shown in Figure 4, $ID(i,\tau )=i-\tau h^{*}$ or 0 when $\tau \ge i/h^{*}$ .

We term the estimated lifetime of node i $\eta (i)$ . We assume that each node knows its potential relays estimated lifetimes. Such information can be piggy-backed on their communications during previous transmissions. As far as the energy consumption is concerned, all data traffic of node i should be sent to its optimal relay, node $ID(i,1)$ . However, when $\eta (i)>\eta (ID(i,1))$ , node i should forward its packets to other candidates in (15) through the following splitting rule:

$$\begin{array}{c}{T}_{i,ID\left(i,\tau \right)}=\frac{\eta \left(ID\left(i,\tau \right)\right)}{{\sum }_{{\tau }^{\prime }=2}^{\mathcal{l}}‍\eta \left(ID\left(i,{\tau }^{\prime }\right)\right)}.\end{array}$$

(17)

The forwarding rule can then be summarized as

$$\begin{array}{c}{T}_{i,ID\left(i,1\right)}=\mathbf{1}\left\{\eta \left(i\right)\le \eta \left(ID\left(i,1\right)\right)\right\}\cdot T_i,\\ T_{i,ID\left(i,\tau \right)}=\left[1-\mathbf{1}\left\{\eta \left(i\right)\le \eta \left(ID\left(i,1\right)\right)\right\}\right]\\ \cdot \frac{\eta \left(ID\left(i,\tau \right)\right)}{{\sum }_{{\tau }^{\prime }=2}^{\mathcal{l}}‍\eta \left(ID\left(i,{\tau }^{\prime }\right)\right)}\cdot T_i,\end{array}$$

(18)

where $\tau =\mathrm{2,3},\dots ,\ell$ and $\mathbf{1}\{·\}$ is the set indicator function.

The relay update should be performed periodically, but randomly for each node. The best frequency for such updates depends on the cost of residual energy estimation as well as extra cost to obtain the estimated lifetime of the optimal relay. While a high frequency may introduce extra cost, a low frequency may risk energy depletion of the optimal relay or forwarding traffic to nonoptimal relays unnecessarily. We investigate the update frequency on the performance of the DER scheme in Section 5.

4.2. Identifying Potential Relays

In the DER scheme, each node, i, should identify its potential relays, $ID(i,\tau )$ , $\tau =\mathrm{1,2},\dots ,\ell$ . This can be achieved by sending out query messages with a transmission range slightly larger than $\tau h^{*}$ and nodes with the closest distance toward the data sink will respond first. (The exact range of such query message depends on node density and tolerated delay.) Note that $h^{*}$ is the optimal forwarding distance toward the data sink even for nodes that are far away from the sink. The far-away nodes simply forward their traffic toward a node that is $h^{*}$ distance closer to the sink than itself. $h^{*}$ can be computed based on energy consumption constant through (5). Such a value can be stored on the sensors before they are deployed or the sensor can calculate it on the fly.

When such a query message is heard from node i, the sensor that is closest to the data sink among all sensors overhearing the query message should respond and volunteer to serve as the τth relay for node i. A competition mechanism can be administered in order to allow the best relay to respond. This process is similar to geographical routing [42].

4.3. Estimating Lifetime

For each node i, the estimation of $\eta (i)$ can be accomplished through dividing the residual energy by the average energy consumption rate so far:

$$\begin{array}{cc}& {\eta }^{(t+1)}\left(i\right)=\frac{e_i^{\left(t\right)}}{\left(e_i^{\left(0\right)}-e_i^{\left(t\right)}\right)/t},\end{array}$$

(19)

where the superscripts $(t)$ and $(t+1)$ represent the measurement of the t and $t+1$ rounds, respectively.

4.4. Employing the DER Scheme in Practice

In practice, WSNs may have sensors with different initial energy, different traffic generation rate, or irregular shape of network area. Sensor nodes are more likely to be randomly distributed instead of evenly distributed. We discuss the implications of such practical network settings on the implementation of the DER scheme in this subsection.

When sensor nodes have different residual energy, the DER scheme reacts to this according to the comparison of the estimated lifetime. Therefore, when a node has a lower residual energy than other nodes in the network, its estimated lifetime will be shorter. According to the forwarding rule, it will forward its traffic to the optimal relay. It will also be more likely to receive less incoming traffic than other nodes, further lowering its average energy consumption and extending its lifetime.

An up-to-date estimation of the relay node residual energy is critical to the successful operation of the DER scheme. Such information can be piggy-backed from the acknowledgment that is sent from the relay node to the data sender, which will barely introduce any extra cost and will update its data forward strategy as suggested in the DER scheme. Therefore, only one data packet needs to be sent before the sender is informed of the residual energy comparison of itself and its optimal relay.

If nodes have different traffic generation rates or rate fluctuation, such rates will affect their estimated lifetimes. Thus, when a node has more traffic than other nodes and higher energy consumption rate, its estimated lifetime will be shorter than other nodes in the neighborhood. This will in turn reduce its energy consumption in the coming rounds.

Irregular network shapes affect the identification of potential relays in the DER scheme. However, the dynamic feature of the DER scheme makes sure that the best set of relays will be found and used to forward data traffic toward the data sink. We present our simulation results in noncircular network aeas in Section 5.

5. Performance Evaluation

We used MATLAB to simulate and evaluate our proposed scheme and several related ones including the MF, the LPF, and the GF schemes. Testbed evaluations would certainly be realistic, but they hide the importance of accurate design with too much implementation details. Hence, we rely on computer simulations for our evaluation at this stage and leave the testbed evaluation for our future work. Unless specified otherwise, the network setup is assumed as follows: we deploy N nodes in a WSN and each of the nodes generates $\lambda =1$ packet in each second. These packets will be forwarded toward the data sink. The network lifetime and other performance metrics are measured and compared for different data forwarding schemes. We calculated the normalized lifetime of each scheme as its lifetime divided by that of the GF scheme. The energy constant $k_0$ is 1. The initial energy reserve of each of the nodes is assumed to be $1\times 10^3$  J. $\ell =8$ is used in the DER scheme. Furthermore, we have assumed that the nodes always obtain estimated lifetime of the potential relay nodes (i.e., an update cycle of 1 unit, see Figure 8). Note that these parameters (except ℓ) and results only have relative significance. Other values would lead to similar conclusions.

5.1. 1D Chain Network

We first investigate the performance of the DER scheme in 1d chain networks. In 1d networks, the N nodes are distributed evenly, with the distance between consecutive nodes being 1 unit, for example, meter (see Figure 1).

In Figure 5, we present the lifetime comparison of the DER, the MF, and the LPF schemes in 1d chain networks. From the figure, the normalized lifetime of the DER scheme is at most 5% lower than that of the LPF scheme. The MF scheme performs significantly worse. As N increases, the performance of all schemes worsens, as the hotspot problem becomes more severe. On the other hand, we argue that the chance of having such an extended network in practice is small. Note that the performance of the LPF scheme is achieved with the help of global information and linear programming computation on each node (or a central node). The performance of the DER scheme with different ℓ values is also compared in Figure 5. In general, a larger ℓ balances the estimated lifetime of more nodes but requires the sender to obtain estimated lifetime information from more nodes. Furthermore, ℓ is sometimes limited by $R_{\max \hspace{0.17em}}$ , the maximum transmission range of the sensors.

Figure 5

Normalized lifetime of the DER, the MF, and the LPF schemes in 1d chain network. In the DER scheme, $\ell =\mathrm{6,8},10$ has been evaluated. The performance difference of the DER schemes with different ℓ can be seen as negligible.

In Figure 6, we compare the performance of the DER scheme in 1d chain networks with heterogeneous traffic generation. The amount of traffic generated from the nodes is randomly chosen between $1-r_{\lambda }$ and 1 packet per second but fixed for each node throughout its entire lifetime. No noticeable difference of the normalized lifetime can be observed. Therefore, the DER scheme reacts to different traffic very well.

Figure 6

Normalized lifetime of the DER scheme in 1d chain network. The traffic generation on each node is assumed to be randomly selected between $1-r_{\lambda }$ and 1 packet per second on an average. Therefore, larger $r_{\lambda }$ represents more randomness of the traffic generation.

Figure 7 compares the performance of the DER scheme in 1d chain networks with different initial energy. The initial energy of each node is assumed to be randomly chosen between $1-r_e$ and 1 multiplied by $e_{\max \hspace{0.17em}}$ , the maximum initial energy. Therefore, higher $r_e$ represents more diversity in initial energy reserve. Based on Figure 7, higher $r_e$ leads to lower normalized network lifetime. This is because of the increased difficulty of balancing node energy as $r_e$ increases. However, even as $r_e=0.5$ , the performance of the DER scheme is similar to that of $r_e=0$ (equal initial energy). This shows the resilience of the DER scheme over different initial energy.

Figure 7

Normalized lifetime of the DER scheme in 1d chain network with different initial energy. The initial battery energy of each node is randomly chosen from $1-r_e$ and 1 multiplied by $e_{\max \hspace{0.17em}}$ , the maximum initial energy. Therefore, larger $r_e$ represents more randomness in the initial battery energy.

Figure 8

Lifetime of the DER scheme in 1d network. It can be observed that, even with an update cycle of one per 20 messages, the lifetime of the network remains unchanged. Only when the update cycle is increased to 100, a large network may experience a drop of lifetime by about 25%.

In Figure 8, we compared the network lifetime when different update cycles are employed in the DER scheme. The numbers shown in the figure represent the duration (in the unit of message transmission intervals). As we can see from the figure, even an update cycle of 20 units will not change the lifetime for networks with relatively small N. When this update cycle is increased to 100 units, a large network may experience a drop of lifetime by about 25%. This demonstrates that the DER scheme does not require frequent updates of estimated lifetime of the potential forwarding nodes. This is mainly due to the flexibility of our scheme.

We also compared the DER scheme with the LPF scheme in networks with dynamic node membership. In a 1d network of 100 nodes, some of the nodes will move away and never come back. Therefore, in the LPF scheme, the node which has forwarded traffic to the moved-away node has to randomly choose a new destination to forward its traffic. We use this simulation setup to demonstrate the benefit of the DER scheme intrinsic capability to react to network dynamics. The node movement was simulated as a simple move-away probability $P_{\text{dyn}}$ in each slot. In each time slot, each node randomly decides whether it will leave the current 1d network. Moved-away nodes never come back. The network lifetime comparison in the unit of slots is presented in Figure 9. The results are the average of 50 runs with different random seeds.

Figure 9

Lifetime comparison of the DER scheme and the LPF scheme in a 1d network where nodes move away with a probability of $P_{\text{dyn}}$ in each time slot. The network lifetime is shown in the unit of time slots. The DER scheme offers a network lifetime that is 3-4 times longer than the LPF scheme, in which the forwarding rules are assumed to be precalculated and distributed to the nodes.

Based on Figure 9, we can see that the DER scheme offers a much better network lifetime than the LPF scheme. This is because of its natural reaction towards the estimated lifetime of the routers. It might be argued that, in a network where LPF is employed, the forwarding rules should be recomputed once node(s) moved away. However, this will significantly increase the overhead of sending the topology to the central node for computation and distributing the traffic forwarding rules back to every node. In the DER scheme, however, each node reacts to the change based on the estimated lifetime and modifies its forwarding rule accordingly. As such, the overhead is much lower (note that the estimated lifetime can be piggy-backed to the sender through acknowledgment packets).

5.2. 2D Network

We have also investigated the performance of the DER scheme in 2d networks. In our default simulations, N nodes are distributed on a circular network region with a radius of n units. On an average, there are $2i$ sensors that are i units from the center of the region, where $i=\mathrm{1,2},\dots ,n$ . The total number of nodes is $N={\sum }_{i=1}^n‍2i=(n+1)n$ . Note that, in all networks including 2d ones, the DER scheme chooses the potential relays based on (16). Thus, in networks with randomly distributed nodes, the traffic rate of nodes may be different even if they have the same distance toward the sink (this is different to our assumption in the analysis of Section 3.4).

Results of circular network regions are shown in Figure 10, in which we present the normalized lifetime as a function of n, the radius of the circular region in the 2d network. The good match of the curves of the DER scheme and the LPF scheme underlines the good performance of the DER scheme especially when n is small. When n is getting large, the proposed DER scheme is outperformed by the LPF scheme in static networks. We can further see from the results in Figure 10 that a comparison between the DER scheme and the multi-hop/direct forwarding (MDF) scheme [33] is unnecessary. This is because the MDF scheme, which requires to know the distances toward data sink, has a performance approaching that of the LPF scheme. The DER scheme, on the contrary, does not require such information.

Figure 10

Normalized lifetime of the DER, the MF, and the LPF schemes in 2d circular network. The data sink is located at the center of the circular area with radius of n. The total number of nodes in the region is $N=(n+1)n$ .

Figure 11 demonstrates the lifetime performance of the DER scheme as compared to that of the LPF scheme as a function of energy constant, $k_0$ . Different ℓ values have been studied. The fluctuation of the lifetime comparison is due to the round-off function in (6) and $n/h^{*}$ . That is, when $k_0\le \sqrt{1.5}$ we have $h^{*}=1$ and a large improvement of DER can be seen when $h^{*}$ is changed from 1 to 2. As ℓ increases, the DER scheme achieves a performance closer to that of the LPF scheme. This, however, increases the overhead of the DER scheme because larger ℓ requires the sender to obtain estimated lifetime information from more nodes.

Figure 11

Lifetime comparison of the DER and the LPF schemes in 2d networks. The network radius is assumed to be $n=20$ .

Figure 12 compares the difference of residual energy on all nodes when the first node runs out of battery energy. The difference of residual energy is measured as the relative standard deviation of the residual energy, $\sigma /\mu$ , where σ is the standard deviation of the residual energy of all alive nodes and μ is the mean. We compare the performance of the DER scheme and the MF scheme. It can be observed that the DER scheme offers much lower (better) relative standard deviation as compared to the MF scheme in the 2d networks with N nodes randomly distributed to a circular 2d area. The performance of networks with rectangular regions are also shown in Figure 12. In these rectangular networks, the data sink is located at the lower-left corner of the areas. It can be observed that the performance results do not differ much from that of circular networks.

Figure 12

Relative standard deviation of node energy at the time when the first node runs out of energy. We compared the performance of the DER scheme and the MF scheme in both circular and rectangular regions. The DER scheme offers much more balanced residual energy than the MF scheme.

We present the performance of the DER scheme with different lifetime definition in Figure 13. The lifetime definition here is the time when α portion of the nodes run out of battery energy. From the figure, the lifetime curves increase slowly as α increases until reaching about 0.4. This suggests that the energy consumption is rather balanced. As N increases, the lifetime becomes shorter due to more traffic generated from the nodes even though there are more nodes to forward these data packets.

Figure 13

Performance of the DER scheme with different lifetime definition. The lifetime is defined as the time at which α portion of nodes run out of battery energy. N nodes are randomly distributed in circular networks.

Figure 14

Comparison of real lifetimes of different schemes used in practical 1d networks. These are simulation results based on energy consumption rate from [8].

We have also used MATLAB to simulate the lifetime of WSNs with practical energy consumption data. The results are presented in Figure 14. The energy consumption rates were obtained from [8]. As N increases, the network lifetime significantly decreases. The DER scheme performs slightly worse than the LPF scheme, both of which are much better than the MF scheme. A small ℓ does slightly shorten the network lifetime, as can be observed in the figure, especially when $N=10$ .

Finally, we compare the communication overhead of the DER scheme and that of a potential online LPF scheme with the data sink as a central station. We assume that 2 bytes of extra information with 20 bytes of header is needed in the DER scheme (to allow potential relays to notify the sender). A similar message needs to be transmitted from the node noticing a moved-away node to the data sink. The update period is 20 in our scheme and the network has $N=100$ nodes. The results are shown in Table 2. From this table, we can see that the DER scheme requires a constant communication overhead (in terms of energy cost). The online LPF scheme has a rising energy cost as $P_{\text{dyn}}$ increases. For instance, when $P_{\text{dyn}}=5\times 10^{-5}$ , the communication overhead of the online LPF scheme is four times as large as that of the DER scheme.

Table 2

Communication overhead comparison between DER and on-line LPF. This overhead has been converted to energy and has only comparative significance.

Scheme	$P_{\text{dyn}}=10^{-5}$	$P_{\text{dyn}}=2\times 10^{-5}$	$P_{\text{dyn}}=5\times 10^{-5}$
LPF	440	880	2200
DER	563	563	563

6. Conclusions

The severe resource constraints of the sensor nodes in wireless sensor networks (WSNs) call for carefully designed data forwarding techniques. A successful technique should balance the energy consumption of most nodes while lowering the overall power consumption in the source-to-sink data delivery. In this work, we have focused on the problem of optimizing the energy consumption among nodes with different energy and overall traffic load. Based on our observations, we have proposed a dynamic energy-based relaying (DER) scheme for WSNs.

In the DER scheme, each node makes its own decision on data relay selections. Such a decision is made with the help of the extra information piggy-backed from the communication that it has performed with its potential relays. Each of the nodes continuously asks the same question, “Will I live longer than my relay?” If a node figures that the optimal relay has a shorter estimated lifetime, it will forward its traffic further instead of forwarding traffic to the optimal relay. This is the key technique in our DER scheme that is responsible of balancing the energy consumption of nodes and equalizing lifetimes of the nodes in the network. The main drawback of employing the optimal transmission distance, as in the MF scheme, is that, while it minimizes the overall energy consumption, it causes a serious hotspot problem. In the DER scheme, however, a sender stops using the optimal relay when the latter is running low on energy. Instead, it forwards traffic further closer to the data sink.

Our scheme only requires local information (from several nodes that are equal steps away) and the decision can be made on the fly. Our evaluation through numerical study and simulations shows that the DER scheme achieves a performance close to those that can only be obtained through linear programming, which requires global information and/or centralized process.