On energy efficiency of geographic opportunistic routing in lossy multihop wireless networks

Abstract

Geographic opportunistic routing (GOR) is an emerging technique that can improve energy efficiency in lossy multihop wireless networks. GOR makes local routing decision by using nodes’ location information, and exploits the broadcast nature and spatial diversity of the wireless medium to improve the packet forwarding reliability. In this paper, our goal is to fully understand the principles and tradeoffs in GOR, thus provide insightful analysis and guidance to the design of more efficient routing protocols in multihop wireless networks. We propose a local metric, one-hop energy efficiency (OEE), to balance the packet advancement, reliability and energy consumption in GOR. We identify and prove important properties about GOR on selecting and prioritizing the forwarding candidates in order to maximize the expected packet advancement. Leveraging the proved properties, we then propose two localized candidate selection algorithms with O(N ³) running time to determine the forwarding candidate set that maximizes OEE, where N is the number of available next-hop neighbors. Through extensive simulations, we show that GOR applying OEE achieves better energy efficiency than the existing geographic routing and blind opportunistic routing schemes under different node densities and packet sizes.

1 Introduction

Many recent experimental studies on multihop wireless networks (including wireless ad hoc and sensor networks) have shown that wireless links can be highly unreliable [1–3]. Recently, a new routing paradigm, known as opportunistic routing (OR) [4–6] (or contention-based routing [7]), was proposed to cope with the unreliability of link quality in such networks.

Different from traditional routing (TR), where a single next-hop node is predefined for each packet forwarding at the network layer, OR selects multiple neighboring nodes as forwarding candidates at network layer and chooses one candidate that successfully received the packet as the actual forwarder at the MAC layer. In other words, TR makes routing decision before each actual physical layer transmission, while OR does it after each physical transmission according to the instant packet reception results at the neighboring nodes.

The philosophy behind OR is to improve the transmission reliability by utilizing the spatial diversity of the wireless medium to obtain better performance (such as energy efficiency, reliability and throughput). The intuition is that owing to the broadcast nature and spatial diversity of the wireless medium, the probability of at least one forwarding candidate correctly receiving the packet will increase when more forwarding candidates are involved. Thus, the retransmission overhead is reduced and the packet will get more chance to be forwarded towards the destination for each transmission. The reduced retransmission not only reduces the transmission and reception energy consumption on nodes, but also alleviates the medium contention. Therefore, OR can improve energy efficiency and throughput.

One type of OR schemes, geographic opportunistic routing (GOR) [4, 5, 7, 8], uses nodes’ location information to define the forwarding candidate set and prioritize candidates. The advantage of GOR over link state based OR (such as ExOR [1] and least-cost opportunistic routing (LCOR) [9]) lies in several aspects. For one, nodes need to know only the local information (location and/or link quality) of their one-hop neighbors in order to forward packets and hence the state stored is minimum. Further, GOR conserves energy and bandwidth since discovery floods and state propagation are not required beyond a single hop.

In this paper, we focus on the energy efficiency issue about GOR in wireless sensor networks (WSNs). In WSNs, the major portion of energy consumption comes from packet transmission and reception [10]. Although GOR can improve energy efficiency by reducing the MAC layer retransmission, it involves more forwarding candidates than traditional geographic routing (GR). Therefore, it consumes more reception energy. There exist tradeoffs between packet advancement, reliability and energy consumption in GOR. Unfortunately, the analysis of this tradeoff is missing in the literature.

In this paper, we propose a local metric, One-hop Energy Efficiency (OEE), to strike a good balance between the benefit (packet advancement and reliability) and the cost (energy consumption) in GOR. We identify and prove important properties about GOR on selecting and prioritizing the forwarding candidates in order to maximize the expected packet advancement (EPA). Leveraging the proved properties, we then propose two localized candidate selection algorithms to determine the forwarding candidate set that maximizes OEE. These two algorithms both achieve O(N ³) running time, where N is the number of available next-hop neighbors. Through extensive simulations, we show that GOR applying OEE achieves better energy efficiency than the existing geographic routing and opportunistic routing schemes. We would like to emphasize that although we mainly focus on the energy efficiency issue, which is a major concern in sensor networks, the framework and analysis presented in this paper are expected to be extensible and applicable to other multihop wireless networks and be useful when analyzing other performance such as throughput.

The rest of the paper is organized as follows. The related work is introduced in Sect. 2. Section 3 proposes the definitions of EPA and OEE, and formulates the energy-efficient GOR problem. Several important properties about the EPA and the corresponding forwarding candidate set are revealed and analyzed in Sect. 5. Two efficient localized candidate selection algorithms are proposed in Sect. 6. Simulation results are presented in Sect. 7. Conclusions are drawn in Sect. 8.

2 Related work

Our work mainly relates to the following two research topics: geographic routing and opportunistic routing.

2.1 Geographic routing

In geographic routing [11–19], the forwarding node is aware of the location information of its own, its neighbors, and the destination, thus a packet can be effectively forwarded towards the direction of its destination. The node location information can be obtained by prior configuration, by the Global Positioning System (GPS) receiver, or through some sensor self-configuring localization mechanisms [20, 21]. As each node only needs to maintain its neighbors’ information, the properties such as good scalability, statelessness, and low maintenance overhead make geographic routing an efficient technique especially in large-scale wireless sensor networks.

Several recent experimental studies on wireless ad-hoc and sensor networks [1, 2] have shown that wireless links can be highly unreliable and this factor must be explicitly taken into account when devising higher-layer protocols. More recent works on geographic routing therefore are more focused on this practical lossy channel situation. Seada, et al. [17] articulated the distance–hop energy tradeoff for geographic routing. They concluded that packet advancement timing packet reception ratio, is an optimal metric for making localized geographic routing decisions in lossy wireless networks with ARQ (Automatic Repeat reQuest) mechanisms, and is also a good metric for No-ARQ scenarios. Zorzi and Armaroli also independently proposed the same link metric [22]. Lee et al. [18] presented a more general framework called normalized advance (NADV) to normalize various types of link cost such as transmission times, delay and power consumption. Unfortunately, these metrics only apply to geographic routing which involves single forwarding candidate and cannot be directly applied to GOR.

2.2 Opportunistic routing

Opportunistic routing integrates the network and MAC layers. At the network layer, a set of forwarding candidates or a region are selected. At the MAC layer, one node is chosen as the forwarder depending on the node’s availability and wireless link quality. Several MAC rendezvous [23, 24] and coordination schemes [4, 7, 25] have been proposed to coordinate nodes involved in the OR and ensure a single relay is chosen to forward the packet at each hop.

There are generally two types of OR, location-aided [4, 5, 7, 8] and link state based ones [6, 9]. In this paper, we focus on the former, the geographic opportunistic routing (GOR).

One of the most detailed works in GOR is GeRaF [4] where candidate forwarders that are geographically closer to the destination than the current forwarding node are divided into sets of priority regions with nodes closer to the destination having higher relay priorities. One similar work to [4] is [5] where the network layer specifies a set of nodes by defining a forwarding region in space that consists of the candidate nodes and the data link layer selects the first node available from that set to be the next hop node. A delay constraint hop counts optimization scheme with adaptive node wake-up discipline is studied in this work. [7] proposed contention-based forwarding for mobile ad hoc networks and discussed three suppression strategies to avoid packet duplication. [26] compares the performances such as power consumption, delay and packet delivery ratio of greedy geographic routing with region based OR. [27] proposes a framework to model OR in low traffic scenarios.

All of these GOR schemes blindly involve all the available next-hop neighbors as forwarding candidates. None of these GOR achieves good balance between packet advancement, reliability and energy consumption. None of them provide a thorough understanding of how the selection of the forwarding candidate set will affect the energy efficiency. Although a recent work on GOR studied the throughput and delay performance of GOR by selecting a subset of available next-hop neighbors as forwarding candidates, energy efficiency is not its concern [8]. The questions, such as “(a) how many and which neighbor nodes should be involved in the local opportunistic forwarding?”; and “(b) what criteria should affect the relay priority among the forwarding candidates?”, remain unanswered. In this paper, we will answer these questions with energy efficiency as a major concern.

3 System and energy consumption model

3.1 System model

In this paper, we assume the local GOR scenario as in Fig. 1. Assuming node i, i.e., the transmitter, is forwarding a packet to a sink/destination D. i _j is one of i’s neighbors which are closer to D than i. Let $\mathcal{C}$ be the set of i _j . We call $\mathcal{C}$ as the available next-hop node set of node i. Let $N=|\mathcal{C}|$ denote the number of nodes in $\mathcal{C}$.

Fig. 1

Example in which node i is forwarding a packet to a remote destination D

Each i _j corresponds to a pair, (d _j , p _j ), where d _j defined in Eq. (1) is the packet advancement to the destination when packet sent by i is relayed by i _j , and p _j is the packet reception ratio (PRR) from node i to i _j . Note that d _j is the advancement, not the distance between the node i and its neighbor i _j .

$$ d_{j} = Dist(i,D) - Dist(i_{j},D) $$

(1)

where Dist(i, D) and Dist(i _j , D) are the Euclidean distance between i and D and between i _j and D, respectively.

A node is a neighbor of i when PRR from i to it is larger than some non-negligible probability threshold p _T ¹. From the definition of d _j and p _j , we know that d _j  > 0 and p _T  < p _j  < 1. The PRR information on each link can be obtained by using probe messages [28] or estimated by Signal-to-Noise Ratio (SNR) [3]. We assume the PRR on each link is independent. Let $\mathcal{F}$ denote the forwarding candidate node set of node i, which includes all the nodes selected to get involved in the local opportunistic forwarding. Let $r=|\mathcal{F}|$ denote the number of nodes in $\mathcal{F}$. Here $\mathcal{F}$ is a subset of $\mathcal{C}$, while in the existing OR schemes [4, 6], $\mathcal{F}=\mathcal{C}$. We assume all the nodes in $\mathcal{C}$ and $\mathcal{F}$ are descending ordered according to the advancement s.t. d _m  ≥ d _n , ∀ m < n.

The GOR procedure is described as follows. A sender, node i, selects $\mathcal{F}$ based on its knowledge of $\mathcal{C}$ (d _j ’s and p _j ’s) and some performance goal (e.g. energy efficiency). When the forwarding candidates in $\mathcal{F}$ receive the packet broadcasted by i, they follow a specific priority to relay the packet. That is, the first-priority candidate should attempt to relay the packet when it received it correctly. If it failed to receive the packet, the second-priority candidate will claim the forwarding responsibility if it received the packet successfully, otherwise the third-priority one, etc. In short, a forwarding candidate will only relay the packet if all the nodes with higher priorities failed to do so. The actual forwarder will become a new transmitter and suppress all the other potential forwarders in $\mathcal{F}$. When no forwarding candidate has successfully received the packet, the sender will retransmit the packet if retransmission is enabled. The sender will drop the packet when the retransmissions reach the limit. This procedure iterates until the packet arrives at the destination. When the packet gets stuck due to a communication void where no available next-hop neighbors are closer to the destination than the current node, the packet will be dropped. Mechanisms such as FACE routing [14] or perimeter forwarding in GPSR [15] can be applied here to deal with the communication void problem, but it is beyond the scope of this paper.

In this paper, we focus ourselves on greedy forwarding, and aim to achieve energy efficiency by locally selecting and prioritizing forwarding candidates in a judicious way.

3.2 Energy consumption model

In wireless networks, the energy consumption from communication mainly comes from three parts: transmission, reception, and idle listening [29]. For GOR, packet forwarding is a random event due to its opportunistic nature. So we use

$$ \bar{E}_{or}=\bar{E}_i + \bar{E}_{{\mathcal{F}}} + \bar{E}_{o} $$

(2)

to represent the expected energy consumption for one local opportunistic forwarding. ${\bar{E}_i, \bar{E}_{\mathcal{F}}}$, and $\bar{E}_{o}$ are the expected energy consumption on transmitter i, all nodes in the candidate set $\mathcal{F}$, and other neighboring nodes of node i, respectively. Each of these three energy consumption consists of transmission, reception, and idle listening parts. Note that ${\bar{E}_i, \bar{E}_{\mathcal{F}}}$, and $\bar{E}_{o}$ depend on many factors, such as neighborhood size, forwarding candidate set, forwarding priority, MAC protocol, link quality, node wakeup/sleep pattern, packet size, data rate, transmission power, receiving power, and idle listening power, etc. The energy consumption for delivering one packet from a source S to a destination D is the total energy consumption of all the nodes involved into the OR.

4 Local metric: opportunistic energy efficiency (OEE)

Recall that our goal is to approach a minimum energy consumption to delivery the packet from the source to destination by locally selecting forwarding candidate set at each hop. In this section, we will first introduce the metric of EPA to describe how much closer a packet can be forwarded towards the destination per transmission in GOR given a forwarding candidate set $\mathcal{F}$. We then examine the expected energy consumption of one-hop local opportunistic forwarding given relatively ideal MAC and wakeup/sleep mechanism. We finally propose our a new local metric: opportunistic energy efficiency OEE), which indicates one-hop expected packet advancement per unit of energy consumption.

4.1 Expected packet advancement (EPA)

Recall that our goal is to achieve the tradeoff between the packet advancement, reliability and energy consumption. We now introduce the metric of EPA to describe how much closer a packet can be forwarded towards the destination per transmission in GOR.

Let $\pi_{j}(\mathcal{F}) = \langle i_{j_{1}},i_{j_{2}}, \ldots ,i_{j_{r}}\rangle$ be one permutation of nodes in $\mathcal{F}$, and the order indicates that nodes will attempt to forward the packet with priority $i_{{_{{j_{1} }} }} > i_{{j_{2} }} > \cdots > i_{{j_{r} }}$. We define the EPA for the ordered forwarding candidate set $\pi_{j}(\mathcal{F})$ in one opportunistic forwarding attempt in GOR as in Eq. (3).

$$ {\rm EPA}(\pi_{j}({\mathcal F})) = \sum_{k=1}^{r}d_{j_{k}}p_{j_{k}}\cdot \prod_{n=0}^{k-1}(1-p_{j_{n}}) $$

(3)

where $p_{{j_{0} }} : = 0$. The physical meaning of Eq. (3) is the expected packet advancement achieved by GOR using the ordered forwarding candidate set $\pi_{j}(\mathcal{F})$. When r = 1, Eq. (3) degenerates to the metric of advancement  ×  PRR in traditional geographic routing [17, 18].

4.2 Opportunistic forwarding MAC

Note that $\bar{E}_{or}$ depends on many factors, such as MAC and wakeup/sleep patterns. For different opportunistic forwarding coordination protocols and sleep/wakeup patterns, the energy consumption in the network should be different. In this paper, in order to get more insight about the impact of candidate selection on the energy efficiency of GOR, we assume the following relatively ideal coordination scheme and wake-up mechanism.

Assuming all the nodes of node i is sleeping in the beginning of a local opportunistic forwarding. When node i wants to forward a data packet to its forwarding candidates, it uses a low-power wakeup radio to wakeup the desired forwarding candidate(s) [30]. In the wakeup packet, the address or ID of the forwarding candidate(s) are included. The sequence of the address represents the forwarding priority. When receiving the wakeup packet, each neighboring node will exam if it is in the forwarding candidate set. If not, it will keep sleeping. Otherwise, it will wake up in order to receive the subsequent data packet. Assuming all the forwarding candidate nodes can be woken up reliably and fast slotted acknowledgement (FSA) [25] is used to coordinate the opportunistic forwarding. After sensing the channel has been idle for a DIFS (distributed inter-frame space), the transmitter locally broadcasts the data packet. Each candidate waits for a short time before deciding whether it should broadcast ACK. Candidates with lower priority will wait longer. If the first-priority candidate receives the packet correctly, with a time delay of SIFS (short inter-frame space), it will send out an ACK. The ACK is used for acknowledging the sender of the reception as well as suppressing other candidates from duplicate forwarding. Meanwhile, all the other candidates sense the channel for a short period of time to tell whether they detect this ACK. If the answer is positive, they stop sensing the channel and simultaneously suppress their own attempts of sending ACK and forwarding the data packet. Otherwise, they assume the first-priority candidate missed the data packet and the second-priority candidate takes the responsibility of sending ACK and all the remaining lower priority candidates continue to monitor this second ACK. The coordination process goes on until some successful candidate finally sends out an ACK. By receiving the ACK, the transmitter and forwarding candidates will go back to sleep. If none of the candidates successfully received the packet, the sender will retransmit that packet after a timeout (e.g., 3SIFS + ACK time). It has shown in [25] that FSA is very efficient and can ensure the forwarding priority and avoid duplicate forwarding almost for sure.

4.3 Expected energy consumption of one-hop opportunistic forwarding

Under the above wakeup mechanism and coordination protocol, we can decide the energy consumption at transmitter and candidate sides.

The power consumption of the low-power wakeup circuit is about 2.6 μ W [30], which is negligible comparing to the power consumption of data transmission/reception and idle listening. That is, we assume $\bar{E}_{o}=0$.

At transmitter side, we have the following expected energy consumption:

$$ \bar{E}_{i} = \bar{E}_{i}^{tx} + \bar{E}_{i}^{rx} + \bar{E}_{i}^{idle} $$

(4)

where

$$ \bar{E}_{i}^{tx} = {\frac{1}{P_{{\mathcal{F}}}}}E_{data\_tx} $$

(5)

$$ \bar{E}_{i}^{rx} = E_{ACK\_rx} $$

(6)

$$ \begin{aligned} \bar{E}_{i}^{idle} &\approx \frac{1}{P_{{\mathcal{F}}}}(E_{to} + p_{1}E_{SIFS} + 2p_{2}(1-p_{1})E_{SIFS} \\ &+ \ldots + rp_{r}\Uppi_{j=1}^{r-1}(1-p_{j})E_{SIFS}) \end{aligned} $$

(7)

where ${P_{\mathcal{F}}}$ is the probability of at least one forwarding candidate correctly receiving the packet. So ${{\frac{1}{P_{\mathcal{F}}}}}$ is the number of expected transmissions the transmitter will make and Eq. (5) represents the expected energy consumption of transmission at transmitter. Equation (6) says for a successful data forwarding, there is one ACK received by the transmitter. For representation simplicity, in Eq. (7), we assume the transmitter always wait to time and cost E _to energy before transmission. Then for each transmission (first time or retransmission) from the transmitter, the transmitter has to wait SIFS time and cost E _SIFS with probability p ₁ if node i ₁ correctly receives the packet. It then has to wait 2SIFS and cost 2E _SIFS with probability p ₂(1 − p ₁) if node i ₁ does not correctly receive the packet but i ₂ does, etc.

At the forwarding candidate side, we have the following total expected energy consumption in the set $\mathcal{F}$:

$$ \bar{E}_{{\mathcal F}} = \bar{E}_{{\mathcal F}}^{tx} + \bar{E}_{{\mathcal F}}^{rx} + \bar{E}_{{\mathcal F}}^{idle} $$

(8)

where

$$ \bar{E}_{{\mathcal{F}}}^{tx} = E_{ACK\_tx} $$

(9)

$$ \bar{E}_{{\mathcal{F}}}^{rx} = (r-1)E_{ACK\_rx} + {\frac{r}{P_{{\mathcal{F}}}}}E_{data\_rx} $$

(10)

$$ \begin{aligned} \bar{E}_{{\mathcal F}}^{idle} &\approx {\frac{r}{P_{{\mathcal{F}}}}}(E_{to} + p_{1}E_{SIFS} + 2(1-p_{1})p_{2}E_{SIFS} \\ &+ \ldots + rp_{r}\Uppi_{j=1}^{r-1}(1-p_{j})E_{SIFS}) \end{aligned} $$

(11)

Equation (9) says one of the forwarding candidates will eventually send an ACK when the forwarding is successful. Equation (10) indicates that when one forwarding candidate transmits the ACK, the other r − 1 candidates receive it. It also indicates that for each data transmission from the transmitter, there are r receptions at the forwarding candidates. Equation (11) is similar to Eq. (7), except that we time r in the front. Because the idle listening time are the same at transmitter and candidates side, but we have r candidates.

By substituting Eqs. (5, 6), and (7) into Eq. (4), Eqs. (9, 10), and (11) into Eq. (8), and then Eq. (7) and Eq. (8) into Eq. (2), with $\bar{E}_{o}=0$, Eq. (2) can be represented as

$$ \begin{aligned} \bar{E}_{or} &= {\frac{1}{P_{{\mathcal{F}}}}}[E_{data\_tx} + rE_{data\_rx} \\ &+ (r+1)(E_{to}+ \sum_{i=1}^{r}i\cdot E_{SIFS}\cdot p_{i}\Uppi_{j=1}^{i-1}(1-p_{j}))] \\ &+ E_{ACK\_tx} + rE_{ACK\_rx} \end{aligned} $$

(12)

Usually data packet is much longer than ACK frame, thus consumes more energy. The idle listening energy consumption is largely minimized due to the use of an efficient MAC protocol and low-power radio triggered wakeup. So from Eq. (12), we can know that, the majority of the energy consumption comes from data transmission and reception.

Node that, although the energy consumption is based on relatively ideal wakeup and coordination mechanisms, our framework and methodology presented in this paper should be general enough to be applied to other coordination or wakeup/sleep mechanisms.

4.4 Opportunistic energy efficiency

We propose a new local metric, opportunistic energy efficiency (OEE), which aims to strike a good balance between the routing efficiency and energy consumption. Given a forwarding candidate set $\mathcal{F}$, the new metric is denoted as $OEE(\mathcal{F})$ and defined in Eq. (13).

$$ OEE({\mathcal{F}}) = {\frac{EPA({\mathcal{F}})}{P_{\mathcal{F}}\bar{E}_{or}}}\cdot L_{data} $$

(13)

where L _data is the data packet length in bits. Note that ${\frac{EPA(\mathcal{F})}{P_\mathcal{F}}}$ is the expected packet advancement for a successful opportunistic forwarding considering retransmissions. If the unit of $EPA(\mathcal{F})$ is meter, and $\bar{E}_{or}$ is Joule, the unit of $OEE(\mathcal{F})$ is bmpJ. The physical meaning of $OEE(\mathcal{F})$ is the expected bit advancement towards the destination by consuming one Joule of energy for a successful one-hop opportunistic forwarding.

4.5 Problem definition

In this paper, our goal is to find $\mathcal{F}^{*}$ to maximize the metric $OEE(\mathcal{F})$ in each local opportunistic packet forwarding, which can be formulated as the following optimization problem:

$$ {\mathcal F}^{*} = \mathop{\hbox{argmax}}\limits_{\forall {\mathcal F}\subseteq {\mathcal C}} OEE ({\mathcal F}) $$

(14)

The intuition to maximize the OEE is as follows. Maximizing OEE implies a large EPA in the numerator, which will result in fewer transmissions and hops for delivering a packet from the source to the destination. Maximizing OEE also implies a small denominator, which indicates lower energy consumption at each hop. Therefore maximizing OEE tends to minimize the energy consumption to forward a packet from the source to the destination, that is, to maximize the energy efficiency. Note that maximizing OEE cannot guarantee a global optimum of energy efficiency due to the lack of the global information. It is common for all the location based routing schemes that make greedy local routing decisions and trade significantly reduced routing (i.e., route establishment, update, and maintenance) overhead with suboptimal routing performance. However, we will show in Sect. 7 that our energy-efficient GOR applying OEE metric achieves better performance than blind GOR and GR solutions.

Solving this optimization problem needs to answer the following two questions: (a) How many and which nodes should be involved in the local forwarding? b) What priority should they follow to forward a packet?

This optimization problem is a combinatorial problem. One naive way to solve this problem is to enumerate all the possible candidate set $\mathcal{F}$, which yields a complexity of O(eN!), where e is the base of natural logarithm and N is the number of available next-hop neighbors. It is, however, infeasible when N is large. In the next section, we will reveal some important properties about GOR on selecting and prioritizing the forwarding candidates in order to maximize the EPA, which will guide us to design a heuristic algorithm to solve the optimization problem in polynomial time.

5 Properties about GOR and candidate set

5.1 Increasing property of EPA

Intuitively, increasing the number of forwarding candidates would result in a better chance of larger packet advancement towards the destination. We first present Proposition 5.1 to confirm this intuition.

Proposition 5.1

(Strictly increasing property) Given $\mathcal{C}$ with N nodes, let $EM(\mathcal{C},r)$ denote the maximum EPA defined in Eq. ( 3 ) achieved by selecting r nodes from $\mathcal{C}$ as forwarding candidates, then $EM(\mathcal{C},r)$ is a strictly increasing function of r. That is

$$ {\rm EM}({\mathcal C},m)<{\rm EM}({\mathcal C},n), 1\leq m < n\leq N $$

(15)

Proof

This proposition is intuitive. Due to space limit, we omit the proof here. Interested readers can refer to [31] for a detailed proof.□

Proposition 5.1 basically indicates that the more nodes get involved in GOR, the larger the EPA can be. So the GOR that involves all the nodes in $\mathcal{C}$ will achieve the largest EPA. However, it is not always the most energy efficient way to forward packets by involving all the nodes in $\mathcal{C}$. As from Eq. (12), we know one transmission is accompanied with r receptions at the forwarding candidates, so involving all the nodes in $\mathcal{C}$ consumes the most energy. On the other hand, traditional geographic routing involving only one forwarding candidate has the least energy cost consisting of only one transmission and one reception, but it achieves the least EPA per hop, which indicates lower routing efficiency as more hops (transmissions) are needed to reach the final destination.

5.2 Relay priority rule

Proposition 5.2 answers the relay priority question.

Proposition 5.2

(Relay priority rule) Given a forwarding candidate set $\mathcal{F}$ with r (r ≥ 1) nodes, the EM $(\mathcal{F},|\mathcal{F}|)$ (the maximum EPA by using all the nodes in $\mathcal{F}$ ) can only be obtained by giving the node closer to the destination higher relay priority, that is, $\forall i_p, i_q \in \mathcal{F}$, if d _p  ≥ d _q , i _p has higher priority than i _q . We can break the tie by assigning arbitrary priority order to nodes with equal advancement. As d ₁ ≥ d ₂ ≥ … ≥ d _r , $EM(\mathcal{F},|\mathcal{F}|)$ can be calculated as follows.

$$ {\rm EM}({\mathcal F},|{\mathcal F}|)= \sum_{k=1}^{r}d_{k}p_{k}\cdot \prod_{n=0}^{k-1}(1-p_{n}) $$

(16)

where $p_{0} : = 0$.

Proof

We proof Proposition 5.2 by induction.□

First, for r = 1, there is only one node in $\mathcal{F}$, then obviously Eq. (16) holds.

Next, we assume Eq. (16) holds for r = N (N ≥ 1), we want to prove Eq. (16) holds for r = N + 1.

Assume $|\mathcal{F}| = N+1$. $\mathcal{F}$ can be divided into two complementary sub-sets, $\mathcal{F}_{1}=\mathcal{F}\setminus\{i_{m}\}$ with N nodes and $\mathcal{F}_{2}=\{i_{m}\}$ with one node. Then the EPA of any permutation $\pi_{j}(\mathcal{F})$ of the N + 1 nodes, can be expressed as the combination of the EPAs of the corresponding permutations of N nodes in $\mathcal{F}_{1}$ and the other node i _m in $\mathcal{F}_{2}$. Then EM $(\mathcal{F},|\mathcal{F}|)$ is expressed as:

$$ \begin{aligned} {\rm EM}({\mathcal F},|{\mathcal F}|) &= \max_{1\leq m\leq N+1}\left\{\sum_{k=1}^{m-1}d_{k}p_{k}\cdot\prod_{w=0}^{k-1}(1-p_{w})\right.\\ &\quad\left.+\,\sum_{k=m+1}^{N+1}d_{k}p_{k}\cdot{\frac{\prod\nolimits_{w=0}^{k-1}(1-p_{w})}{1-p_{m}}}+\,d_{m}p_{m}\cdot{\frac{\prod\nolimits_{w=0}^{N+1}(1-p_{w})}{1-p_{m}}} \right\} \end{aligned} $$

The equality holds for the definitions of EM $(\mathcal{F},|\mathcal{F}|), \mathcal{F}_{1}$ and $\mathcal{F}_{2}$, and the inductive hypothesis. Then we only need to prove for any integer m (1 ≤ m ≤ N),

$$ \begin{aligned} A&:=\sum_{k=1}^{m-1}d_{k}p_{k}\cdot\prod_{w=0}^{k-1}(1-p_{w}) + \sum_{k=m+1}^{N+1}d_{k}p_{k}\cdot{\frac{\prod\nolimits_{w=0}^{k-1}(1-p_{n})}{1-p_{m}}}\\ &\quad+d_{m}p_{m}\cdot{\frac{\prod\nolimits_{w=0}^{N+1}(1-p_{w})}{1-p_{m}}} \\ &\leq B:=\sum_{k=1}^{N+1}d_{k}p_{k}\cdot \prod_{w=0}^{k-1}(1-p_{w}) \end{aligned} $$

Subtracting A from B, we have

$$ B - A={\frac{1}{1-p_{m}}}\sum_{k=m+1}^{N+1}(d_{m} - d_{k})p_{m}p_{k}\prod_{w=0}^{k-1}(1-p_{w})\geq 0 $$

The above inequality holds, because d _m  ≥ d _k . Then the Eq. (16) holds for r = N + 1. So it holds for any r (r ≥ 1).

Proposition 5.2 indicates that when a forwarding candidate set is given, the maximum EPA can be achieved by assigning the relay priority to each node based on their distances to the destination. That is, the furthest node should try to forward the packet first; if it failed (i.e., did not receive the packet correctly), the second furthest node should try next, and so on. For example, in Fig. 1, if nodes i ₂ and i ₄ are chosen as forwarding candidates, we should assign i ₂ higher reliability than i ₄. If two nodes have the same advancement towards the destination, we can assign either one with higher priority. We will show in Sect. 6, considering reliability, we will choose the candidates who contributes more on the reliability if they have the same expected advancement.

Note that this proposition does not mean we should always select i ₁ and i ₂ in Fig. 1 in order to maximize the EPA when the candidate set size is 2. Actually, choosing i ₂ and i ₃ maximizes the EPA when two forwarding candidates are involved.

A coordination scheme similar to the ones in [3, 4, 25] is necessary here to coordinate the transmission among the forwarding candidates. However, the detailed design of the coordination scheme is beyond the scope of this paper. In this paper, we assume the relay priority can be ideally followed. The analysis result is the upper bound of the EPA that GOR can achieve.

Based on Proposition 5.2, we redefine EM$(\mathcal{C},r)$ as follows,

$$ {\rm EM}({\mathcal C},r) = \max_{1\leq j\leq {\rm C}_N^r}\{\sum_{k=1}^{r}d_{j_{k}}p_{j_{k}}\cdot\prod_{n=0}^{k-1}(1-p_{j_{n}})\} $$

(17)

where $N=|\mathcal{C}|$, and C ^r _N is the number of combinations of selecting r (1 ≤ r ≤ N) nodes from the N nodes in $\mathcal{C}$. For each combination j, we have $d_{{_{{j_{1} }} }} > d_{{j_{2} }} > \cdots > d_{{j_{r} }}$ and $p_{{j_{0} }} : = 0$. Here the number of choices is the number of combinations, as when r nodes are selected, the order of them is already determined by the Relay priority rule (Proposition 5.2).

Next, we will identify and prove two important properties about the EM$(\mathcal{C},r)$ function. First, we look at the characteristics of the forwarding candidates that are selected to achieve EM$(\mathcal{C},r)$ with various sizes r. We prove the Containing property for those node sets. Following that, the Concavity of the function EM$(\mathcal{C},r)$ is proved.

5.3 Containing property of feasible candidate set

Define $\mathcal{F}^{*}_r$ as a feasible forwarding candidate set that achieves the $EM(\mathcal{C},r)$. For a given $\mathcal{C}$, we have the following containing property of $\mathcal{F}^{*}_r$’s.

Lemma 5.3

(Containing property) Given the available next-hop node set $\mathcal{C}$ with $N (1\leq N<\infty)$ nodes, $\forall \mathcal{F}^{*}_{r-1}, \exists \mathcal{F}^{*}_{r}$ , s.t.

$$ {\mathcal{F}}^{*}_{r-1} \subset {\mathcal{F}}^{*}_{r}\quad\forall 1\leq r\leq N $$

(18)

Proof of Lemma 5.3

Please refer to “Appendix 1” for the proof.□

Lemma 5.3 indicates that an (r − 1)-node set that achieves EM$(\mathcal{C},r-1)$ is a subset of one feasible r-node set that achieves EM$(\mathcal{C},r)$.

5.4 Concavity of maximum EPA

Following Lemma 5.3, we have the concave property of EM$(\mathcal{C},r)$ as in Proposition 5.4.

Proposition 5.4

(Concavity of maximum EPA) Given the available next-hop node set $\mathcal{C}$ with N (N ≥ 1) nodes, $EM(\mathcal{C},r)$ , defined in Eq. ( 17 ), is a concave function of r. That is, $\forall 1\leq r<N, \hbox{EM}(\mathcal{C},r+1)-\hbox{EM}(\mathcal{C},r)< \hbox{EM}(\mathcal{C},r)-\hbox{EM}(\mathcal{C},r-1).$

Proof

According to Lemma 5.3, assume $\mathcal{F}^{*}_{r+1}\setminus\mathcal{F}^{*}_{r}=\{i_{k}\}$, and $\mathcal{F}^{*}_{r}\setminus\mathcal{F}^{*}_{r-1}=\{i_{j}\}$. There are two cases for the advancement relationship between node i _k and i _j .

• (1) d _k  ≥ d _j .

Then $\mathcal{F}^{*}_{r+1}, \mathcal{F}^{*}_{r}$ and $\mathcal{F}^{*}_{r-1}$ can be represented as

$$ \begin{aligned} {\mathcal F}^{*}_{r+1} &= \langle{\mathcal A}_{1},i_{k},{\mathcal A}_{2},i_{j},{\mathcal A}_{3}\rangle,\\ {\mathcal F}^{*}_{r} &= \langle{\mathcal A}_{1},{\mathcal A}_{2},i_{j},{\mathcal A}_{3}\rangle,\\ {\mathcal F}^{*}_{r-1} &= \langle{\mathcal A}_{1},{\mathcal A}_{2},{\mathcal A}_{3}\rangle \end{aligned} $$

(19)

where $\mathcal{A}_{i} (1\leq i\leq 3)$ is ordered node set and can be ∅. Here, we also handle $\mathcal{A}_{i}$ as one node by giving the same definition of ${d_{\mathcal{A}_{i}}}$ and ${p_{\mathcal{A}_{i}}}$ as in Eq. (35) (see “Appendix 1”). The following advancement relationship holds that

$$ d_{{\mathcal A}_{1}}\geq d_{k}\geq d_{{\mathcal A}_{2}}\geq d_{j}\geq d_{{\mathcal A}_{3}} $$

(20)

Because EPA($\mathcal{F}^{*}_{r}$) is the largest EPA achieved by selecting r nodes, we have

$$ \begin{aligned} B&:={\rm EPA}({\mathcal F}^{*}_{r})-{\rm EPA}(\langle{\mathcal A}_{1},i_{k},{\mathcal A}_{2},{\mathcal A}_{3}\rangle)\\ &=(1-p_{{\mathcal A}_{1}})[p_{k}\cdot {\rm EPA}({\mathcal A}_{2})-{\rm EPA}(i_{k})] \\ &\quad+(1-p_{{\mathcal A}_{1}})(1-p_{{\mathcal A}_{2}})[(p_{k}-p_{j}){\rm EPA}({\mathcal A}_{3})+{\rm EPA}(i_{j})]\geq 0 \end{aligned} $$

(21)

Then,

$$ \begin{aligned} &[{\rm EPA}({\mathcal F}^{*}_{r}) - {\rm EPA}({\mathcal F}^{*}_{r-1})] - [{\rm EPA}({\mathcal F}^{*}_{r+1}) - {\rm EPA}({\mathcal F}^{*}_{r})] \\ &= B + (1-p_{{\mathcal A}_{1}})(1-p_{{\mathcal A}_{2}})p_{k}p_{j}(d_{j}-{\rm EPA}({\mathcal A}_{3})) >0 \end{aligned} $$

(22)

Inequality (22) holds because $\sc{B}\geq 0$ (inequality (21)) and ${d_{j}-{\rm EPA}(\mathcal{A}_{3})>d_{j}-d_{\mathcal{A}_{3}}\geq 0}$.

So ${\rm EPA}(\mathcal{F}^{*}_{r}) - {\rm EPA}(\mathcal{F}^{*}_{r-1})>{\rm EPA}(\mathcal{F}^{*}_{r+1}) - {\rm EPA}(\mathcal{F}^{*}_{r})$ when d _k  ≥ d _j .

• (2) d _k  < d _j .

Then $\mathcal{F}^{*}_{r+1}, \mathcal{F}^{*}_{r}$ and $\mathcal{F}^{*}_{r-1}$ can be represented as

$$ \begin{aligned} {\mathcal F}^{*}_{r+1} &= \langle{\mathcal A}_{1},i_{j},{\mathcal A}_{2},i_{k},{\mathcal A}_{3}\rangle,\\ {\mathcal F}^{*}_{r} &= \langle{\mathcal A}_{1},i_{j},{\mathcal A}_{2},{\mathcal A}_{3}\rangle,\\ {\mathcal F}^{*}_{r-1} &= \langle{\mathcal A}_{1},{\mathcal A}_{2},{\mathcal A}_{3}\rangle \end{aligned} $$

(23)

Similarly, with

$$ B:={\rm EPA}({\mathcal F}^{*}_{r})-{\rm EPA}(\langle{\mathcal A}_{1},{\mathcal A}_{2},i_{k},{\mathcal A}_{3}\rangle)\geq 0 $$

(24)

we can derive that

$$ \begin{aligned} &[{\rm EPA}({\mathcal F}^{*}_{r}) - {\rm EPA}({\mathcal F}^{*}_{r-1})] - [{\rm EPA}({\mathcal F}^{*}_{r+1}) - {\rm EPA}({\mathcal F}^{*}_{r})] \\ &\quad = {\sc B} + (1-p_{{\mathcal A}_{1}})(1-p_{{\mathcal A}_{2}})p_{k}p_{j}(d_{k}-{\rm EPA}({\mathcal A}_{3})) >0 \end{aligned} $$

(25)

So ${\rm EPA}(\mathcal{F}^{*}_{r}) - {\rm EPA}(\mathcal{F}^{*}_{r-1})>{\rm EPA}(\mathcal{F}^{*}_{r+1}) - {\rm EPA}(\mathcal{F}^{*}_{r})$ when d _k  < d _j .

From the analysis above, we know for arbitrary finite number N, we have ${\rm EPA}(\mathcal{F}^{*}_{r}) - {\rm EPA}(\mathcal{F}^{*}_{r-1})>{\rm EPA}(\mathcal{F}^{*}_{r+1}) - {\rm EPA}(\mathcal{F}^{*}_{r}), \forall 1\leq r\leq N-1$, that is, EM$(\mathcal{C},r)$ defined in Eq. (17) is a concave function of r.□

Combining Propositions 5.1 and 5.4, we know that giving an available next-hop node set $\mathcal{C}$ of node i with N nodes, the maximum EPA of selecting r (1 ≤ r ≤ N) nodes is a strictly increasing and concave function of r. This means that although the maximum EPA keeps increasing when more nodes get involved, the speed of the increase slows down. When more nodes are involved, the gained extra EPA becomes smaller and smaller.

5.5 Reliability increasing property

Following the Containing property in Lemma 5.3, we have the Reliability increasing property in Corollary 5.5.

Denote $\mathcal{F}^{*}_{r}=\langle i_{r_{1}},i_{r_{2}},\ldots,i_{r_{r}}\rangle$. Define the one-hop reliability ${P_{\mathcal{F}^{*}_{r}}}$ in Eq. (26) which is the probability of at least one node in $\mathcal{F}^{*}_{r}$ correctly receiving the packet sent by node i for one transmission.

$$ P_{{\mathcal F}^{*}_{r}}=1 - \prod_{n=0}^{r}(1-p_{r_{n}}) $$

(26)

where $p_{{r_{0} }} : = 0$.

Define P ^*(r) in Eq. (27) which is the maximum one-hop reliability achieved by one of the feasible $\mathcal{F}^{*}_{r}$’s.

$$ P^{*}(r)=\max_{\forall {\mathcal F}^{*}_{r}}\{P_{{\mathcal F}^{*}_{r}}\} $$

(27)

Corollary 5.5

P ^*(r ) defined in Eq. ( 27 ) is an increasing function of r.

Proof

The proof is straightforward following Lemma 5.3. Assume one $\mathcal{F}^{*}_{r}$ achieves P ^*(r), then $\exists \mathcal{F}^{*}_{r+1}$ s.t. $\mathcal{F}^{*}_{r+1}\supset\mathcal{F}^{*}_{r}$. According to the definitions of P ^*(r) in Eq. (27) and the one-hop reliability in Eq. (26), we have

$$ P^{*}(r+1)\geq P_{{\mathcal F}^{*}_{r+1}} > P_{{\mathcal F}^{*}_{r}}=P^{*}(r) $$

So P ^*(r) is an increasing function of r.□

Corollary 5.5 indicates that the maximum one-hop reliability corresponding to the forwarding candidate set that maximizes the EPA also increases when more forwarding candidates are involved. The increasing of the maximum EPA implies increasing of the reliability. Therefore, the EPA is a good metric for balancing the packet advancement and reliability.

6 Selecting forwarding candidates in polynomial time

Based on the properties proved in Sect. 5, we are ready to propose two heuristic polynomial time algorithms to find an approximation of the optimal forwarding candidate set $\mathcal{F}^{*}$ in Eq. (14). One algorithm is based on Proposition 5.2 and Lemma 5.3, and the other one is a dynamic programming based on Proposition 5.2.

6.1 Algorithm based on Lemma 5.3

The input of Algorithm 1 is the next-hop neighboring node set ($\mathcal{C}$) and the function to compute $\bar{E}_{or}$. Algorithm 1 searches the optimal candidate sets $\mathcal{F}'$ that maximizes EPA with different number of candidates. Based on the Containing property in Lemma 5.3, in order to find an $\mathcal{F}'$ with r nodes, we add a new node into the optimal candidate set with r − 1 nodes. For feasible sets having the same maximum EPA, we choose the one that achieves higher one-hop reliability (lines 9 and 10). During the search, we compute the OEE for each examined candidate set, and find the one ($\mathcal{F}^{\deg}$) that maximizes the OEE (G ^°) in lines 12 and 13. Note that $\mathcal{F}^{\deg}$ is not necessary the same as $\mathcal{F}'$.

Algorithm 1 Finding an $\mathcal{F}^{\deg}$ based on Lemma 5.3

It is not difficult to find an algorithm to calculate EPA$(\mathcal{F})$ and G (in line 8) in ${\mathbf O}(|\mathcal{F}|)$ running time. So Algorithm 1 costs ${\mathbf O}(N^3)$ running time.

Table 1 shows the procedure of finding the G ^° and $\mathcal{F}^{\deg}$ by applying Algorithm 1 on the example in Fig. 1. We assume the following parameters: $E_{data\_tx}=1, E_{data\_rx}=0.5, E_{to} = 0.025, E_{ACK\_tx}=0.1, E_{ACK\_rx}=0.05, E_{SIFS} = 0$. L _data is normalized as 1 unit. The procedure runs from Round 1 to Round 5, and in each round it runs from the top to the bottom. In the first round, $\langle i_{3}\rangle$ is found as the node achieving the maximum EPA as well as the maximum OEE by selecting one forwarding candidate; in the second round, we test the sets containing i ₃, and $\langle i_{2},i_{3}\rangle$ is found as the optimal node set by selecting two forwarding candidates; in the third round, we test the set containing i ₂ and i ₃, and $\langle i_{1},i_{2},i_{3}\rangle$ is found as the optimal node set by selecting three forwarding candidates. We can find that although the EPA increases, OEE drops. Since by involving more forwarding candidates, the advancement gain is marginal, while more energy is consumed at the candidate side. Finally, we find that $\langle i_{2},i_{3}\rangle$ achieves the maximum OEE.

Table 1 Procedure of finding a maximum energy efficiency OEE and the corresponding forwarding candidate set $\mathcal{F}^{\deg}$ using Algorithm 1 on the example in Fig. 1

We further use a brute-force algorithm to enumerate all the possible forwarding candidate sets and find that the optimal $\mathcal{F}^{*}$ that achieves the maximum OEE in Eq. (14) is also $\langle i_{2},i_{3}\rangle$, which indicates that Algorithm 1 indeed finds the optimal forwarding candidate set in this example.

6.2 Dynamic programming algorithm

We now introduce another efficient dynamic programming algorithm.

Recall that nodes i _j ’s (1 ≤ j ≤ N) in $\mathcal{C}$ are ordered according to the advancements as $d_{1}\geq d_{2}\geq \ldots \geq d_{N}$. Denote the set $\langle i_{q},i_{q+1}, \ldots ,i_{N}\rangle$ (1 ≤ q ≤ N) as $\mathcal{C}_q$. Following the denoting, $\mathcal{C}_{1}=\mathcal{C}$. According to the Relay priority rule in Proposition 5.2 and the definition of EM$(\mathcal{C},r)$, we then have,

$$ {\rm EM}({\mathcal{C}}_{q},r) = \left\{ \begin{array}{ll} 0, &\quad r=0\; \quad \hbox{or}\quad N-q+1<r;\\ Max\{d_{q}p_{q}+(1-p_{q}){\rm EM}({\mathcal C}_{q+1},r-1),&\\ {\rm EM}({\mathcal C}_{q+1},r)\}, &\quad \hbox{Otherwise}. \end{array}\right. $$

(28)

EM$(\mathcal{C},r)$ (1 ≤ r ≤ N) can be efficiently calculated by applying Eq. (28) recursively using dynamic programming [32].

The pseudocode of the dynamic programming algorithm GetM-B is given in Algorithm 2, where $|\mathcal{C}|=N, F_{(q,r)}$ is the ordered node set corresponding to EM$(\mathcal{C}_{q},r), P_{(q,r)}$ is the corresponding one-hop reliability, and d _i ’s are sorted in descending order ($d_{1}\geq d_{2} \geq \ldots \geq d_{N}$). We also choose the feasible set that achieves higher one-hop reliability when two feasible sets have the same EPA (lines 16 to 17). The complexity of Algorithm 2 is also ${\mathbf O}(N^3)$.

Algorithm 2 Finding an $\mathcal{F}^{\deg}$ by dynamic programming

Table 2 shows the procedure of finding the G ^° and $\mathcal{F}^{\deg}$ by applying Algorithm 2 on the example in Fig. 1. We use the same settings as in Table 1. The procedure runs from Round 1 to Round 5, and in each round it runs from the bottom to the top. Note that although it finds the same $\mathcal{F}^{\deg}=\langle i_2, i_3\rangle$ as in Table 1, some of the tested node sets are different from the ones in Table 1. This $\mathcal{F}^{\deg}$ is also indeed the $\mathcal{F}^{*}$ achieving the maximum OEE in Eq. (14).

Table 2 Procedure of finding a maximum energy efficiency OEE and the corresponding forwarding candidate set $\mathcal{F}^{\deg}$ using Algorithm 2 on the example in Fig. 1

6.3 Algorithms 1 and 2 find optimal set

We exam how close the OEE and $\mathcal{F}^{\deg}$ obtained from Algorithms 1 and 2 are to the optimal ones. We randomly generate (d, p) pairs under different nexthop available neighbor size (N). d is within [1, 10] and p is within (0.1,1).

$$ E_{{data\_tx}} = 1,\quad E_{{data\_rx}} = 0.5,\quad E_{{to}}= 0.025,\quad E_{{ACK\_tx}} = 0.1,\quad E_{{ACK\_rx}} =0.05,\quad E_{{SIFS}} = 0. $$

We find that for each N from 1 to 8, Algorithms 1 and 2 always find the optimal set $\mathcal{F}^{*}$ in 1,000 random tests.

7 Performance evaluation

We evaluate the performance of our energy-efficient GOR (EGOR) scheme applying the candidate selection algorithms proposed in Sect. 6 under a sensor network scenario. We also compare the performance of EGOR with geographic routing (denoted as “GR”) which uses only one forwarding candidate that achieves the maximum EPA, and blind geographic opportunistic routing (denoted as “Blind GOR”) which involves all the available next-hop nodes as forwarding candidates. Recall that we focus ourselves on greedy forwarding. That is, when the packet gets stuck due to a communication void where no available next-hop neighbors are closer to the destination than the current node, the packet will be dropped in all the three schemes.

Without explicit explanation, we assume an ideal coordination and low-power triggered wakeup schemes are used, i.e. the forwarding priority is strictly followed and the idle listening energy consumption is minimized.

7.1 Simulation setup

The simulated sensor network has stationary nodes uniformly distributed in a 100  ×  100 m ² square region, with nodes having identical fixed transmission power of 5dbm. The source and the sink nodes are fixed at two corners across the diagonal of the square area. Various situations are examined by varying node densities, retransmission limits, and packet sizes. For each setting, we perform 50 independent runs, with 3,000 packets sent in each run. Node locations are randomly re-assigned and PRRs between nodes are re-calculated in each run. Each result in the figures represents the average value of the 50 runs, with 95% confidence interval indicated.

Channel Model: To simulate a realistic channel model for lossy WSNs, we use the log-normal shadowing path loss model derived in [3]. This model considers several environmental and radio parameters², such as the path-loss exponent (α) and log-normal shadowing variance (σ) of the environment, and the modulation and encoding schemes of the radio. Eq. (29) calculates the packet reception ratio as a function of the packet size, Signal to Noise Ratio (SNR), and distance between a transmitter and receiver. It resembles a MICA2 mote [33], which has data rate of 19.2 kbps, and the noise bandwidth 30 kHz. Non-coherent FSK and Manchester are used as the modulation and encoding schemes (ρ = 2), respectively. The environmental parameters are set to α = 3.5 and σ = 4. In reality, the SNR changes according to the variance of path-loss due to shadowing. To simulate a long-term (in seconds) PRR on each link, we average the PRR under 1000 channel realizations (SNRs) of the log-normal shadowing model. We assume the long-term PRR on each link is stable in each run.

$$ PRR(L_{p},d) = (1 - {\frac{1}{2}}e^{-{\frac{\gamma(d)}{2\times 0.64}}})^{8L_{pr}}(1 - {\frac{1}{2}}e^{-{\frac{\gamma(d)}{2\times 0.64}}})^{8\rho (L_{p}-L_{pr})} $$

(29)

where d is the transmitter-receiver distance, γ(d) is the SNR, ρ is the encoding ratio, L _p is the packet (including preamble, header, and payload) length in bytes, and L _pr is the physical layer preamble length in bytes. L _pr is fixed at 20 bytes to resemble a MICA2 mote in the simulation.

Energy Consumption Model: The energy consumption is obtained by multiplying the power consumption and the packet transmission/reception time as in Eq. (30). Under 5dbm transmission power, according to the power consumption for the MICA2 [33], the transmission power consumption (P _tx ) is 81mw, and both reception power consumption (P _rx ) and (P _idle ) are 30mw.

$$ \begin{aligned} E_{data\_tx} &= {\frac{8L_{p}P_{tx}}{R}}, E_{data\_rx} = {\frac{8L_{p}P_{rx}}{R}}, \\ E_{ACK\_tx} &= {\frac{8(L_{pr}+L_{h})P_{tx}}{R}}, E_{ACK\_rx} = {\frac{8(L_{pr}+L_{h})P_{rx}}{R}},\\ E_{to} &= P_{idle}t_{to}, E_{SIFS} \approx 0 \end{aligned} $$

(30)

where R is the data rate, which is fixed at 19.2kbps in our simulation. The L _h is the length of the MAC header containing the forwarding candidates’ addresses. A neighbor of a transmitter has to read these addresses to decide if it is a forwarding candidate or destination of this packet. L _h is various depending on the number of forwarding candidates. Assuming each MAC address length is 2 bytes, L _h  = 2r bytes, where r is the number of forwarding candidates. We assume t _to is 100 μs, which is actually much shorter than the transmission time of data and ACK frames.

Evaluation Metrics: We define the following metrics to evaluate the performance of these three routing schemes.

• Packet delivery ratio (PDR): percentage of packets sent by the source that actually reach the sink. This is a measure for reliability.

• Energy efficiency η(S, D): this metric is measured in bit-meters per Joule (bmpJ). It is calculated as in Eq. (31),

  $$ \eta(S,D) = {\frac{8\cdot L_{p}\cdot N_{s}\cdot PDR \cdot Dist(S,D)}{E_{total}}} $$

  (31)

  where N _s denotes the number of packets sent out from source S, L _p is the packet length in bytes, and E _total is the (transmission, reception, and idle listening) energy consumed by all the nodes (including those neighbors which overhear the packets but only read the header of the packets) involved in the routing procedure. We account for the distance factor, because the energy efficiency is indeed relevant to the distance between the communication pair due to the lossy property of multi-hop wireless links in WSNs.

7.2 Simulation results and analysis

7.2.1 Impact of node density

We use different node numbers (100, 125, 150, 175) to achieve various node densities corresponding to the average number of neighbors per node of 10, 12, 15, 17, respectively. The retransmission limit is set as 7. The packet size is 75 bytes. It takes more than 10 hops to reach the destination under each density for all the three routing schemes.

Figure 2(a) shows that EGOR achieves better energy efficiency than the other two routing schemes under different node densities. For every forwarding decision, EGOR chooses the forwarding set that maximizes the OEE, the EPA per unit energy consumption. Blind GOR involving all the available next-hop nodes in the routing achieves the worst energy efficiency. The main reason is that although Blind GOR achieves the highest per transmission reliability and uses fewer transmissions to deliver all the packets, it costs much more energy on reception. The excessive reception energy cost in Blind GOR due to unnecessarily involving all the available next-hop nodes in forwarding overwhelms the benefit of reliability.

Fig. 2

Simulation results under different node densities

Figure 2(b) shows the PDR of these three schemes. Both EGOR and Blind GOR achieve 100% PDR under different node densities, since they involve multiple candidates into the packet forwarding and achive high reliability. GR has the lowest reliability since it only involves one pre-defined next-hop node in each packet forwarding.

Actually, in this simulation, EGOR selects around 2.5 forwarding candidates on average under each node density. This observation suggests that only involving a few candidates is sufficient to take advantage of spatial diversity gain of OR. Blindly involving all the available next-hop nodes in GOR is an energy wasteful method.

7.2.2 Impact of packet size

Due to different applications and traffic types, the packet sizes can be different. We examine the impact of packet size on the performance of these three schemes. The node number is still set as 125, and the retransmission limit is 7. We set packet size at 75, 100, 125, and 150 bytes.

Figure 3(a) shows that EGOR achieves better energy efficiency than the other two schemes under different packet sizes. Blind GOR achieves the lowest energy efficiency. When packet size is larger than 100, the energy efficiency of GR is decreased as packet size is increased. When the packet becomes larger, it is more likely to be corrupted by the wireless channel. The energy efficiency has the same trend as the PDR in Fig. 3(b). An interesting observation is that the PDR and energy efficiency of GR are decreased when the packet size changes from 100 to 75, under which, GR selects some longer links which have lower PRR. However, the PDR of EGOR and blind GOR remains 1 under all the packet sizes. Since they involve multiple neighbors in the packet forwarding, although the link quality is degraded when the packet size is increased, the reliability is not affected. EGOR achieves a good balance between the reliability and energy cost by smartly involving only a few “good” neighbors in the opportunistic forwarding, so it yields the best energy efficiency.

Fig. 3

Simulation results under different packets sizes

7.3 Impact of MAC retransmission

We have done simulation to study how the retransmission limit affects the performance of the three schemes. Due to space limit, we do not show the results, instead we make the following summary.

The benefit of increasing retransmission limit for the Blind GOR is marginal but for the GR is obvious (especially when retransmission limit is less than 4). EGOR achieves the best energy efficiency among the three schemes when the retransmission is applied. When there is no retransmission, EGOR achieves similar energy efficiency as Blind GOR. When retransmission limit is larger than 3, the energy efficiency of EGOR does not change much as the PDR is already approaching to 1.

8 Conclusion and future work

In this paper, we study the GOR with energy efficiency as a major concern. We introduce the definition of EPA for arbitrary number of forwarding candidates in GOR and propose a new routing metric, OEE, which evaluates EPA per unit of energy consumption for each local opportunistic forwarding. OEE jointly takes into account packet advancement, reliability, and energy consumption in GOR. Through theoretical analysis, we first show that the maximum EPA can only be achieved by following a relay priority rule – giving the forwarding candidates closer to the destination higher relay priorities when a forwarding candidate set is given. We also show that giving an available next-hop neighbor set with N nodes, the maximum EPA achieved by selecting r nodes is a strictly increasing and concave function of r. We further show that when achieving the maximum EPA, an r-node subset is contained in an r + 1-node subset. However, solely maximizing the packet advancement at each hop by involving all the available next-hop nodes in the opportunist routing cannot achieve a good energy efficiency. Aiming at striking a good balance between routing efficiency and energy consumption, by leveraging the proved findings, we propose two localized candidate selection algorithms with O(N ³) running time. The algorithms efficiently determine the forwarding candidate set that maximizes the local metric, OEE. The performance of EGOR applying the algorithms maximizing the OEE is studied through extensive simulations and compared with those of the existing geographic routing and blind opportunistic routing schemes. The results show that EGOR achieves the best energy efficiency among the three schemes under different network densities, MAC retransmission limits, and packet sizes. The energy efficiency and control packet overhead of these three routing schemes are also studied under a state-of-the-art candidate coordination scheme. Our simulation results also show that although the EPA can be maximized by involving the most number of nodes in GOR, in terms of energy efficiency, only a very small number (around 2.5) of forwarding candidates are needed on average.

In this paper, we assume relatively ideal MAC and wakeup mechanisms in order to get more insight about the impact of candidate selection on the energy efficiency of GOR. However, the OEE proposed in this paper is general enough to be applied to different MAC protocols and wakeup/sleep schemes as long as the expected per-hop energy consumption can be formulated. We plan to test OEE in sensor network testbeds in the future.

Appendix 1

1.1 Proof of Lemma 5.3

Proof

We begin by proving the following useful result. Let $\mathcal{A}$ be an ordered node set $\langle a_1,a_2, \ldots ,a_M\rangle$ ³ with M ($1\leq M<\infty$) nodes, in which the nodes are ordered as $d_{{_{{a_{1} }} }} > d_{{a_{2} }} > \cdots > d_{{a_{M} }}$. Let $\mathcal{B}$, $\langle b_1,b_2,\ldots,b_N\rangle$ with N (0 ≤ N < M) nodes, be a subset of $\mathcal{A}$ such that $d_{{_{{b_{1} }} }} > d_{{b_{2} }} > \cdots > d_{{b_{N} }}$ and b _N  = a _M . For any node $q\notin\mathcal{A}$ with $d_{q} \le d_{{a_{M} }}$, we have the following inequality

$$ \begin{aligned} \Updelta A&:={\rm EPA}(\langle{\mathcal A},q\rangle)-{\rm EPA}(\langle q,{\mathcal A}\rangle)\\ \geq\Updelta B&:={\rm EPA}(\langle{\mathcal B},q\rangle)-{\rm EPA}(\langle q,{\mathcal B}\rangle) \end{aligned} $$

(32)

The equality holds only when $d_{{a_{1} }} = d_{{a_{2} }} = \cdots = d_{{a_{M} }} = d_{q}$.

As $\mathcal{B}\subset \mathcal{A}$, we can represent $\mathcal{A}$ as

$$ {\mathcal A} = \langle{\mathcal A}_{1},b_{1},{\mathcal A}_{2},b_{2},\ldots,{\mathcal A}_{N},b_{N}\rangle $$

(33)

where $\mathcal{A}_{i}$ (1 ≤ i ≤ N) is an ordered node set and can be ∅. Assume $|\mathcal{A}_{i}|=L_{i}$. Denote the kth element in $\mathcal{A}_{i}$ as $\mathcal{A}_{{i_{k} }}$. According to the definition of EPA of an ordered node set in Eq. (3), we have

$$ {\rm EPA}({\mathcal A}_{i}) = \sum_{k=1}^{L_i}d_{A_{i_{k}}}p_{A_{i_{k}}}\cdot \prod_{n=0}^{k-1}(1-p_{A_{i_{n}}}) $$

(34)

where $p_{{A_{{i_{0} }} }} : = 0$.

For convenience, we handle the ordered set $\mathcal{A}_{i}$ as a new node by giving the following definition.

$$ p_{{\mathcal A}_{i}} = 1 - \prod_{n=0}^{L_i}(1-p_{A_{i_{n}}}) \quad {\rm and}\quad \,d_{{\mathcal A}_{i}} = \frac{{\rm EPA}({\mathcal A}_{i})}{p_{{\mathcal A}_{i}}} $$

(35)

If $\mathcal{A}_{i}=\emptyset$, we can choose a positive real number for ${d_{\mathcal{A}_{i}}}$, s.t. ${d_{b_{i-1}}\geq d_{\mathcal{A}_{i}}\geq d_{b_{i}}}$, and ${p_{\mathcal{A}_{i}}=0}$. $d_{{b_{0} }}$ is chosen as a positive real number that makes the inequality ${d_{b_{0}}\geq d_{\mathcal{A}_{1}} \geq d_{b_{1}}}$ hold.

From Eq. (34) and (35), we can easily derive that

$$d_{A_{i_{1}}} \geq d_{{\mathcal A}_{i}} \geq d_{A_{i_{L_i}}},\;{\hbox{then}}\; d_{b_{i-1}}\geq d_{{\mathcal A}_{i}}\geq d_{b_{i}} \forall 1\leq i\leq N $$

(36)

Now EPA of $\mathcal{A}$ is represented as

$$ {\rm EPA}({\mathcal A}) = \sum_{k=1}^{N}[d_{{\mathcal A}_{k}}p_{{\mathcal A}_{k}} + d_{b_{k}}p_{b_{k}}(1-p_{{\mathcal A}_{k}})] \cdot\prod_{n=0}^{k-1}(1-p_{{\mathcal A}_{n}})(1-p_{b_{n}}) $$

(37)

where ${p_{\mathcal{A}_{0}}:=0}$ and $p_{{b_{0} }} : = 0$.

Define ${d_{\mathcal{A}_{N+1}}:=d_q}$ and ${p_{\mathcal{A}_{N+1}}:=p_q}$, then

$$ \Updelta A = \sum_{k=1}^{N}[p_{{\mathcal A}_{k}}(d_{{\mathcal A}_{k}}-d_{{\mathcal A}_{N+1}}) + (1-p_{{\mathcal A}_{k}})p_{b_{k}}(d_{b_{k}}-d_{{\mathcal A}_{N+1}})]\\ \cdot p_{{\mathcal A}_{N+1}}\prod_{n=0}^{k-1}(1-p_{{\mathcal A}_{n}})(1-p_{b_{n}}) $$

(38)

$$ \Updelta B =\sum_{k=1}^{N}p_{b_{k}}p_{{\mathcal A}_{N+1}}(d_{b_{k}}-d_{{\mathcal A}_{N+1}})\prod_{n=0}^{k-1}(1-p_{b_{n}}) $$

(39)

So

$$ \begin{aligned} \Updelta A - \Updelta B &= \sum\limits_{{k = 1}}^{N} {[(d_{{\mathcal{A}_{k} }} - d_{{b_{k} }} ) + (1 - p_{{b_{k} }} )(d_{{b_{k} }} - d_{{\mathcal{A}_{{k + 1}} }} )]} \\ \quad \cdot \left\{ {p_{{\mathcal{A}_{{N + 1}} }} \left[ {1 - \prod\limits_{{n = 0}}^{k} {(1 - p_{{\mathcal{A}_{n} }} )} } \right]\left[ {\prod\limits_{{n = 0}}^{{k - 1}} {(1 - p_{{b_{n} }} )} } \right]} \right\} \ge 0 \\ \end{aligned} $$

(40)

As ${\mathcal{A}\supset\mathcal{B}, \exists p_{\mathcal{A}_{n}}\neq 0 (1\leq n\leq N)}$. We also have ${d_{\mathcal{A}_{k}}\geq d_{b_{k}}}$ and ${d_{b_{k}}\geq d_{\mathcal{A}_{k+1}}}$. So inequality (40) holds, that is, inequality (32) holds.

Now we are ready to prove the containing property of $\mathcal{F}^{*}_r$’s. Recall that for arbitrary finite node number, $N=|\mathcal{C}|\geq 1$, we want to prove $\forall \mathcal{F}^{*}_{r-1}, \exists$ an $\mathcal{F}^{*}_{r}$, s.t. $\mathcal{F}^{*}_{r-1}\subset\mathcal{F}^{*}_{r}, \forall 1\leq r\leq N$. For each r, denote one feasible $\mathcal{F}^{*}_{r}=\langle r_{1},r_{2},\ldots,r_{r}\rangle$ and $d_{{r_{1} }} \ge d_{{r_{2} }} \ge \cdots \ge d_{{r_{r} }}$. We prove this Lemma by induction.

First, for arbitrary N, when r = 1, as $\mathcal{F}^{*}_{0}=\emptyset$, and $\mathcal{F}^{*}_{1}\neq\emptyset$, it is obvious that the containing property holds.

Second, when r = 2, implicating N ≥ 2, we want to prove $\forall \mathcal{F}^{*}_{1}, \exists \mathcal{F}^{*}_{2}$, s.t. $\mathcal{F}^{*}_{1}\subset\mathcal{F}^{*}_{2}$. Assume one feasible $\mathcal{F}^{*}_{1}=\langle 1_{1}\rangle$. We know node 1₁ achieves the maximum EPA among the N nodes. If we assume for any feasible $\mathcal{F}^{*}_{2}$, $\mathcal{F}^{*}_{1}\nsubseteq\mathcal{F}^{*}_{2}$, that is $1_{1}\notin\mathcal{F}^{*}_{2}$, then we can always replace node 2₂ as 1₁ to achieve at least an equal or larger EPA than EPA($\mathcal{F}^{*}_{2}$). Then the new node set containing node 1₁ should be one feasible node set achieving maximum EPA by selecting 2 nodes from the N nodes, thus the assumption is wrong, then $\exists \mathcal{F}^{*}_{2}$, s.t. $\mathcal{F}^{*}_{1}\subset\mathcal{F}^{*}_{2}$. That is, the containing property holds when r = 2.

Then, we assume $\forall \mathcal{F}^{*}_{m-1}, \exists$ an $\mathcal{F}^{*}_{m}$, s.t. $\mathcal{F}^{*}_{m-1}\subset\mathcal{F}^{*}_{m}$, when r = m (m ≥ 2), and we want to prove $\forall \mathcal{F}^{*}_{m}, \exists$ an $\mathcal{F}^{*}_{m+1}$, s.t. $\mathcal{F}^{*}_{m}\subset\mathcal{F}^{*}_{m+1}$, when r = m + 1, implicating N ≥ m + 1.

We will prove under the following two cases, the containing property holds.

Case I: $(m+1)_{1}=m_{i}, i\in \{2, 3, \ldots , m\}$.

Let node (m + 1) _j (2 ≤ j ≤ m + 1) be the first node in $\mathcal{F}^{*}_{m+1}$ but not in $\mathcal{F}^{*}_{m}$. We can always find such a node because $\langle (m+1)_{2},\ldots,(m+1)_{m+1}\rangle$ contains more nodes than $\langle m_{i},\ldots,m_{m}\rangle$. We know that EPA($\mathcal{F}^{*}_{m}$) is the largest EPA achieved by selecting m nodes, then

$$ {\rm EPA}({\mathcal F}^{*}_{m}) \geq {\rm EPA}({\mathcal F}^{*}_{m+1} \setminus \{(m+1)_{j}\}) $$

(41)

where $\mathcal{F}^{*}_{m+1}\setminus\{(m+1)_{j}\}$ is the ordered subset obtained by excluding (m + 1) _j from $\mathcal{F}^{*}_{m+1}$.

From the definition of EPA in Eq. (3), we have

$$ \begin{aligned} &{\rm EPA}(\langle (m+1)_{j},{\mathcal F}^{*}_{m}\rangle)\\ &\geq {\rm EPA}(\langle (m+1)_{j},{\mathcal F}^{*}_{m+1} \setminus \{(m+1)_{j}\}\rangle) \end{aligned} $$

(42)

Assume (m + 1) _j−1 = m _l (i ≤ l ≤ m), we have

$$ \begin{aligned} &\Updelta 1:={\rm EPA}(\langle m_{1},\ldots,m_{l},(m+1)_{j},m_{l+1},\ldots,m_m\rangle)\\ &\quad -{\rm EPA}(\langle (m+1)_{j},{\mathcal F}^{*}_{m}\rangle)\\ &={\rm EPA}(\langle m_{1},\ldots,m_{l},(m+1)_{j}\rangle)\\ &\quad -{\rm EPA}(\langle (m+1)_{j},m_{1},\ldots,m_{l}\rangle) \end{aligned} $$

(43)

$$ \begin{aligned} \Updelta 2:={\rm EPA}({\mathcal F}^{*}_{m+1})\\ -{\rm EPA}(\langle (m+1)_{j},{\mathcal F}^{*}_{m+1}\setminus \{(m+1)_{j}\}\rangle)\\ ={\rm EPA}(\langle(m+1)_{1},\ldots,(m+1)_{j-1},(m+1)_{j}\rangle)\\ -{\rm EPA}(\langle (m+1)_{j},(m+1)_{1},\ldots,(m+1)_{j-1}\rangle) \end{aligned} $$

(44)

According to the definition of (m + 1) _j and the assumption that (m + 1)₁ = m _i , we have $\langle (m+1)_{1},\ldots,(m+1)_{j-1}\rangle\subset\langle m_{1},\ldots,m_{l}\rangle$. Then according to inequality (32), we have $\Updelta 1 \geq\Updelta 2$, and combining with inequality (42), we get

$$ {\rm EPA}(\langle m_{1},\ldots,m_{l},(m+1)_{j},m_{l+1},\ldots,m_m\rangle)\geq{\rm EPA}({\mathcal F}^{*}_{m+1}) $$

(45)

According to the definition of $\mathcal{F}^{*}_{m+1}$, we have

$$ {\rm EPA}(\langle m_{1},\ldots,m_{l},(m+1)_{j},m_{l+1},\ldots,m_m\rangle)\leq{\rm EPA}({\mathcal F}^{*}_{m+1}) $$

(46)

From inequalities (45) and (46), we have

$$ {\rm EPA}(\langle m_{1},\ldots,m_{l},(m+1)_{j},m_{l+1},\ldots,m_m\rangle)={\rm EPA}({\mathcal F}^{*}_{m+1}) $$

(47)

We find the set $\langle m_{1},\ldots,m_{l},(m+1)_{j},m_{l+1},\ldots,m_m\rangle$ achieving the maximum EPA by using m + 1 nodes, and this set contains $\mathcal{F}^{*}_{m}=\langle m_{1},\ldots,m_{l},m_{l+1},\ldots,m_m\rangle$.

In the above proof, we implicitly assume N ≥ m + i. However, it’s easy to get that node (m + 1)₁ can not be m _i when N < m + i. Because according to the Relay priority rule in Proposition 5.2, when we assume (m + 1)₁ = m _i , we implicitly exclude nodes m ₁,…, m _i−1 as the forwarding candidates. The number of nodes that can be chosen is N − (i − 1) < (m + i) − (i − 1) = m + 1, then we do not have enough nodes to choose for $\mathcal{F}^{*}_{m+1}$.

Case II: (m + 1)₁ ≠ m _i , ∀ 2 ≤ i ≤ m

In this case, we have two sub-cases:

• 1) (m + 1)₁ ≠ m ₁

Then $(m+1)_{1}\notin \mathcal{F}^{*}_{m}$. Assume for any feasible $\mathcal{F}^{*}_{m}, \langle (m+1)_2,\ldots,(m+1)_{m+1}\rangle\neq\mathcal{F}^{*}_{m}$, we can replace $\langle (m+1)_2,\ldots,(m+1)_{m+1}\rangle$ in $\mathcal{F}^{*}_{m+1}$ by $\mathcal{F}^{*}_{m}$ to get a sequence $\langle (m+1)_1,\mathcal{F}^{*}_{m}\rangle$ which achieves at least an equal or larger EPA than EPA($\mathcal{F}^{*}_{m+1}$). So $\exists \mathcal{F}^{*}_{m+1}$, s.t. $\mathcal{F}^{*}_{m}\subset \mathcal{F}^{*}_{m+1}$.

• 2) (m + 1)₁ = m ₁

To find $\langle (m+1)_2,\ldots,(m+1)_{m+1}\rangle$ is equivalent to selecting m nodes achieving maximum EPA from the remained node set $\mathcal{C}_{m_{1}}\setminus\{m_{1}\}$ in which all the nodes have advancements larger than $d_{{m_{1} }}$. As $\mathcal{F}^{*}_{m}\setminus\{m_{1}\}$ is the node set that achieves the maximum EPA by selecting m − 1 nodes in $\mathcal{C}_{m_{1}}\setminus\{m_{1}\}$, by the induction assumption, we have $\mathcal{F}^{*}_{m}\setminus\{m_{1}\}\subset\langle (m+1)_2,\ldots,(m+1)_{m+1}\rangle$, then $\mathcal{F}^{*}_{m}\subset\mathcal{F}^{*}_{m+1}$.

From the induction above, we know for arbitrary finite node number, N ≥ 1, we have ∀ $\mathcal{F}^{*}_{r-1}, \exists \mathcal{F}^{*}_{r}$ s.t. $\mathcal{F}^{*}_{r-1}\subset\mathcal{F}^{*}_{r}, \forall 1\leq r\leq N$.□