1 Introduction

Multihop wireless networks have various civilian or military applications and have drawn considerable attention in recent years. One of the major concerns in designing multihop wireless networks is to save the energy consumption as the wireless nodes are often powered by batteries only. Energy-aware routing protocols [1–10] have been well-studied. Most of these energy-aware routing protocols consider new energy-related metrics, such as a function of the energy required to communicate on a link [1, 2, 5] or the nodes’ remaining lifetime [3] or both [11], instead of classic route metrics such as hop count or delay.

Recently, a new class of communication techniques, cooperative communications (CC) [12, 13], have been introduced to allow single antenna devices to take advantage of the multiple-input–multiple-output (MIMO) systems. This CC explores the broadcast nature of the wireless medium and allows nodes that have received the transmitted signal to cooperatively help by relaying data for other nodes. Previous study has shown significant performance gain of CC in various wireless network applications: broadcasting [14–16], topology control and connectivity [17–20], and throughput maximization [21].

Recent works [22–27] have investigated the impacts of CCs on the problem of minimum power routing. For example, Khandani et al. [23] and Li et al. [22] both study the methods of finding the minimum energy cooperative route for a wireless network. They have developed several heuristic algorithms to decide the next hop node and the nodes which will participate the CC to the next hop. All these methods only focus on minimizing the total energy consumption of routing the packet from the source node to the destination node. However, it is well known that consistently using the minimum cost path for routing may lead to uneven energy distribution among nodes, which could substantially reduce the lifetime of the network.

Therefore, in this paper, we focus on studying the impact of CC on energy balancing among nodes. We introduce a new cooperative scheme to carefully select cooperative relay nodes from one-hop neighbors around the current node and make smart decisions on their transmission power. It can be applied to any underlying energy-aware routing protocol, and only need local information to perform the optimization on CCs. We formally prove that our cooperative routing method can indeed balance the energy consumption among nodes to prolong lifetime of the network. Notice that Pandana et al. [11] also study how to maximize network lifetime by using cooperative routing. However, they limit the scope of cooperative relay within the nodes on the route and concentrate on minimizing the total energy consumption of all cooperative nodes. This significantly limits the effectiveness of their method on energy balancing. In contrast, we allow all one-hop neighbors around current node to participate the energy-balanced cooperative relay and aim to balance their remaining energy. In addition, under our CC model, one of their methods regresses to the minimum energy path based routing.

The rest of this paper is organized as follows. In Sect. 2, we summarize related works in energy-efficient routing and cooperative routing for wireless networks. In Sect. 3, we introduce the network model and CC model used by our routing protocol. In Sect. 4, we present our energy-balanced cooperative routing (EBCR) protocol and theoretically prove that the protocol guarantees the improvement of balancing remaining energy among nodes in the network. Section 5 presents the simulation results on random networks by comparing the EBCR routing with the minimum energy path routing. Finally, Sect. 6 concludes the paper with a summary and an outlook for future work.

2 Related work

Since energy is a scarce resource which limits the lifetime of wireless networks, a number of energy efficient routing protocols [1–10] have been proposed recently using a variety of techniques. Classical routing algorithms may be adapted to energy-related criteria rather than metrics such as delay or hop distance. Most of the proposed energy-aware metrics are defined as a function of the energy required to communicate on a link [1, 2, 5] or a function of the nodes remaining lifetime [3]. By taking these energy-aware metrics, many centralized minimum energy routing protocols [3–5] and energy efficient localized routing protocols [6–10] have been proposed and widely used in wireless ad hoc networks or sensor networks.

Cooperative communication models introduce a new element in designing energy efficient routing algorithms for wireless ad hoc networks. Recent work [22–27] has investigated the impacts of CCs on the problem of minimizing power routing. Khandani et al. [23] first formulate the problem of finding the minimum energy cooperative route for a wireless network and develop a dynamic-programming-based algorithm as well as two polynomial-time heuristic algorithms. Li et al. [22] also study the finding minimum energy cooperative route problem, but they assume that the last L predecessor nodes along the path are allowed for cooperative transmission to the next hop. They propose an algorithm which uses the Dijkstra’s algorithm with a modified relaxation procedure to reflect the CC cost. In [24], a cooperation-based routing algorithm minimum power cooperative routing (MPCR) algorithm is proposed. This algorithm constructs the minimum-power route using any number of the proposed cooperation-based building blocks that require the least possible transmission power. In [26, 27], the cooperative multi-hop routing under more complex fading model is studied for the purpose of energy savings.

All of the research above focuses on minimizing the total energy consumption in cooperative routing. However, in this paper, we concentrate on balancing the energy among nodes and prolong the lifetime of the network. Pandana et al. [11] in study how to maximize network lifetime of network by using cooperative routing. They define the link cost by normalizing the transmission power with the residual energy at each node. Their methods first find the least cost route based on their link costs, then use the last L nodes in the route to perform cooperative relay for current node. Even though their methods indeed can balance energy consumption on certain level, they limit the scope of cooperative relay within the nodes on the route, which restricts the effectiveness on balancing energy. In contrast, in this paper, we consider one-hop neighbors around the route and use all possible neighbors to perform cooperative relay aiming at energy balancing. In addition, their method aims to minimize the total normalized energy consumption of all participating nodes, while our study want to balance the remaining lifetime among all participating nodes in CCs. Notice that under our CC model, which is different with their model, simply minimizing the total energy consumption of all nodes on the minimum energy path regresses to the minimum energy path itself without CCs.

In addition, cross-layer cooperative routing problems have been studied recently. Zhang et al. [25] study the joint problem of routing selection in network layer and contention avoidance among multiple links in MAC layer in a CC aware network. They convert the decision problem into an optimization problem which can be solved by linear programming. They also provide a distributed cooperative scheme to approximate the optimal solution. Recently, Sharma et al. [28] study the joint optimization problem of relay node assignment and flow routing for concurrent sessions under CC to maximize the throughput. They model the problem as a mixed integer linear programming problem and provide a novel solution based on the branch-and-cut framework.

3 Network models and assumptions

In this section, we briefly introduce the network models and assumptions in our proposed cooperative routing protocol.

We consider a connected multihop wireless network with n nodes \(V=\{v_1, v_2, \ldots, v_n\}\). Every node v i can adjust its transmission power P(v i ) which is limited by a maximum value P MAX . If a sending node v i wants to communicate with node v j directly, the transmission power of node v i must satisfy

$$ P(v_i)\cdot (d(v_i,v_j))^{-\alpha}\geq{\tau}\quad(P(v_i)\leq{P_{MAX}}). $$

Here, α is the path loss exponent (between 2 and 4), τ is the minimum average signal-to-noise ratio (SNR) for decoding received data successfully, and d(v i , v j ) is the distance between node v i and node v j . We also assume the transmission time of a packet is one unit time. With P MAX , we can define a direct communication graph G = (V, E) where V is the node set and E is the direct link set of all possible direct communication among nodes. Let N(v i ) represent the set of direct neighbors of node v i , i.e., for any \(v_j \in N(v_i), (d(v_i,v_j))^{-\alpha}\cdot \tau \le P_{MAX}\).

We assume that each node has a distinctive identity and each node knows its position information either through a low-power GPS receiver or localization methods. By a single-hop exchange, each node can gather the location information of its neighbors. By using this position information, a node can calculate the distances to its neighbors and use them to optimize its transmission power.

Our CC model is similar to those of [17–20] but different from those Footnote 1 of [11, 24]. CC model takes advantage of the physical layer design that combines partial signals containing the same information to obtain the complete information. Thus, a complete communication from node v i to node v j can be achieved by CC if v i transits the same signal simultaneously with a set of helper nodes H(v i ) and their transmission power satisfies

$$ \sum_{v_k\in{v_i\cup {H(v_i)}}}{P(v_k) \cdot(d(v_k,v_j))^{-\alpha}}\geq{\tau}\quad(P(v_k)\leq{P_{MAX})}. $$

Figure 1 shows a simple example of CC. Node v 1 wants to transmit data to node v 2. v 1 can first transmit to its nearby neighbors v 3 and v 4, then the three nodes transmit simultaneously to v 2 using CC. If the combined SNR is larger than τ, v 2 can successfully decode the data. Physical layer techniques for implementation of CC could be found in [29]. Carefully selecting the helper set and using CC can reduce the transmission power. v 1 can directly reach v 2 using at least \(P^{d}(v_1)=\tau \cdot(d(v_1,v_2))^\alpha\) transmission power. If the total transmission power P cc(v 1) + P cc(v 3) + P cc(v 4) < P d(v 1) when using CC, CC can reduce the total transmission power from the direct transmission between v 1 and v 2. More importantly, CC can also spread the energy consumption among multiple nodes which can benefit the energy balancing in the network. In the above example, if P cc(v 1) + P cc(v 3) + P cc(v 4) ≥ P d(v 1), but max{P cc(v 1), P cc(v 3), P cc(v 4)} is smaller than P d(v 1), CC has potential to balance the energy, more than the direct communication between v 1 and v 2. In this paper, we apply CC in the one-hop neighborhood along the energy efficient path to balance the energy in the whole network.

Fig. 1
figure 1

Cooperative Communication (CC): v 1 together with its helpers v 3 and v 4 transmit simultaneously to v 2 using CC

Full size image

We assume that the initial battery level of each node v i is E 0(v i ) and the battery level of v i at time t is E t(v i ). For all definitions, when the time t is clear in context, it could be ignored. When node v i transmits a packet using transmission power P t(v i ), its battery level reduces to E t+1(v i ) = E t(v i ) − P t(v i ) × 1. Here, for simplicity, we ignore the receiving energy cost and assume that the size of a packet is the same and the time to send a packet is unified to one unit time. Thus, P t(v i ) × 1 is the energy consumed from transmitting the packet in a unit time. But our proposed cooperative routing protocol can be easily extended to handle the cases without these assumptions. When E t(v i ) ≤ 0, node v i is running out of its battery and dies out. Let \(E_{min}(S)=\min_{v_i \in S}E^t(v_i)\), which is the minimum remaining energy of a node set S. As usual, we define the lifetime of the network T as the time when the first node dies out, i.e., T = {min t| E t(V) = 0}.

In this paper, we assume that the underlying routing decision (the route connecting the source and the destination) has been made by certain non-CC routing strategy, such as energy-efficient ad hoc routing protocols or shortest path based routing algorithms. We only focus on how to apply CC technique to further improve the energy balancing along the selected path.

Table 1 lists all the symbols used in the paper.

Table 1 Summary of notations
Full size table

4 Energy-balanced cooperative routing (EBCR)

In this section, we first introduce how our proposed cooperative routing (EBCR) can balance the energy along a single path from its source v s to its destination v d , then we further discuss how the EBCR performs under multiple-flow routing and prove its optimality.

4.1 Balancing energy along single path

As explained in last section, our cooperative routing algorithm starts from a path generated by an underlying non-cooperative routing protocol. Assume the path is \(\pi=v_0,v_1,v_2, \ldots, v_h\), where v s  = v 0 and v d  = v h . Our goal is to perform CC for each hop v i v i+1 along the path, such that after the transmission v i and its helpers H(v i ) have the balanced remaining energy and the minimum remaining energy among them is maximized. Therefore, we hope that the energy along the path is balanced too. See Fig. 2 for illustration. Here, we assume that each node v i exchanges the information of its remaining energy and position with neighbors so that v i also has information of its neighbors. We also assume that the energy consumed by exchanging control packets is ignorable.

Fig. 2
figure 2

Illustration of EBCR to pick the helper set H(v i ) (including v j and v k in this example) for current node v i which will send the same packet simultaneously to next hop node v i+1. The large circle represents neighborhood N(v i ) of v i and the small circle represents one of the potential cooperative helper sets PH(v i ) of v i

Full size image

In order to apply CC, we need to pick the helper set for current node v i which will send the same packet simultaneously to v i+1. We first define a potential cooperative helper set \(PH(v_i) \subset N(v_i)\). Obviously, in PH(v i ), we only consider those neighbors of v i which are closer to v i than v i+1 (here, the closeness is defined based on the Euclidean distance between the neighbor to the current node v i , and this can be easily obtained since each node knows its own position and positions of its neighbors); otherwise directly sending the packet to v i+1 is more energy efficient. Therefore, PH(v i ) could be any subset of \(\{ v_k | v_k \in N(v_i) \hbox{ and } d(v_i,v_k) < d(v_i,v_{i+1}) \}\).

Given a potential helper set PH(v i ) with size k, we first introduce an algorithm to calculate the remaining energy of v i and its helper set H k (v i ) under CC model. The basic idea of the algorithm is as follows. We first calculate the transmission power P h(v i ) needed to reach the farthest neighbor inside PH(v i ), then use it to update the remaining energy of v i by E t+1(v i ) = E t(v i ) − P h(v i ). For other nodes v j in PH(v i ), the remaining energy is E t+1(v j ) = E t(v j ). Then we sort all these k + 1 nodes (defined as set A) in the descending order by its remaining energy E t+1(v j ). Assume that the sorted set is \(\{v_1^{\prime}, v_2^{\prime}, \ldots, v_{k+1}^{\prime}\}\). Our algorithm will greedily pick those nodes with larger remaining energy to be helpers of v i , until their cumulated signal strength at v i+1 is larger than or equal to τ, i.e., \(\sum_{j=1}^{w}(E^{t+1}(v_j^{\prime}) -E^{t+1}(v_{w+1}^{\prime}))(d(v_j^{\prime},v_{i+1}))^{-\alpha} \ge \tau\). If the cumulative power strength of the first w nodes in PH(v i ) is enough to reach v i+1, our algorithm will just use these w nodes as v i ’s helpers during CC. We try to balance every helper’s remaining energy after the transmission. Let E x be the remaining energy of all w nodes. We need

$$ \sum_{j =1}^{w}(E^{t+1}(v_j^{\prime}) -E_x)(d(v_j^{\prime},v_{i+1}))^{-\alpha} = \tau. $$

Thus,

$$ E_x = \frac{\sum_{j =1}^{w}E^{t+1}(v_j^{\prime})(d(v_j^{\prime},v_{i+1}))^{-\alpha}-\tau}{\sum_{j =1}^{w}(d(v_j^{\prime},v_{i+1}))^{-\alpha}}. $$

If the energy consumption of v i with CC (E t+1(v i ) − E x ) + P h(v i ) is less than the energy consumption of direct transmission \(\tau \cdot (d(v_i,v_{i+1}))^{\alpha}\), we return E x as the estimated energy and the first w nodes \(\{v_1^{\prime}, v_2^{\prime}, \ldots, v_w^{\prime}\}\) as the helper set H k (v i ). If \(E^{t+1}(v_i) -E_x+P^h(v_i) \ge \tau \cdot (d(v_i,v_{i+1}))^{\alpha}\), then CC with nodes in PH(v i ) is not useful and v i directly sends the packet to v i+1. In that case, we return \(E^{t+1}_k(v_i)=-\infty\) and H k (v i ) = {v i }. Algorithm 1 shows the detailed algorithm. By running this algorithm, for a given HP(v i ), we can decide which nodes have to involve into the cooperative routing and what are their transmission power during CC.

Figure 3 illustrates a simple example where there are 4 nodes inside A = PH(v i ) ∪ {v i }. Under CC model, the sender v i first sends the packet to other nodes in A. Then v i refreshes its remaining energy. The sorted remaining energy of the nodes in A is shown in the figure. The sender v i is assumed to have the second largest remaining energy, i.e. \(v_2^{\prime}=v_i\). Based on Algorithm 1, we try to find first w nodes whose cumulated signal strength at v i+1 is strong enough as τ. In this example, w = 3. Then a target remaining energy E x is calculated. As the output of Algorithm 1, \(v_1^{\prime}\) and \(v_3^{\prime}\) will help \(v_2^{\prime}\) (v i ) to perform CC transmission. After the transmission, the remaining energy of these three nodes is E x .

figure aa
Fig. 3
figure 3

Example for Algorithm 1

Full size image

Now we are ready to present our main algorithm (Algorithm 2) of the proposed EBCR. Basically, it tries all possible initial setting of PH(v i ) by running Algorithm 1 for each setting and picks the solution with the largest remaining energy as the final decision. If the best solution E t+1 k* (v i ) ≥ 0, we perform CC with its helper set H k*(v i ), otherwise, send the packet directly to v i+1. Notice that the proposed EBCR algorithm only use 1-hop neighbor information around node v i and its time complexity is only O(m 2) where m is the number of neighbors whose distances from v i are less than v j ’s. Since usually the number of neighbors of a node is small unless the network is very crowded, the additional computation cost of the proposed method over the routing task is very limited and the requirement of computation capability on each individual node is very low.

Our cooperative routing problem can efficiently balance the remaining energy among nodes. Figure 4 illustrates an example with just three nodes. Assume that all nodes can communicate with each other directly and have the same initial energy 32τ, i.e., E 0(v 1) = E 0(v 2) = E 0(v 3) = 32τ. The distances among them are marked in the figure. Let α = 2 and the underlying routing is minimum energy routing. Assume that we want to send a packet from v 1 to v 3. Without CC, v 1 need transmit at power of 16τ, thus E v1 = 32τ − 16τ = 16τ. Then E min (V) = 16τ. If with our cooperative routing, v 1 will choose v 2 as its helper. First, v 1 needs to send the packet to v 2 using the transmission power of 4τ. Then v 1 and v 2 transmit the packet simultaneously to v 3 with transmission power of 6τ and 10τ respectively, so that the power strength at v 3 is \(6\tau \cdot 4^{-2} +10\tau \cdot 4^{-2} = \tau\). After the transmission, the remaining energy of both v 1 and v 2 is 22τ. Thus, the minimum remaining energy of the network E min (V) = 22τ, which is larger than the one without CC. In addition, the remaining energy among all the three nodes are more balanced.

figure ba
Fig. 4
figure 4

Example of cooperative routing with a single flow

Full size image

Next we formally prove that our proposed EBCR can indeed balance remaining energy of the network. Recall that the minimum remaining energy of a network is the minimum of remaining energy of individual nodes in the network.

Theorem 1

For a routing task between a pair of source and destination nodes, the proposed EBCR can improve the minimum remaining energy of the network.

Proof

Assume that E min (V) is the remaining energy of the network V with the proposed cooperative routing, while \(E_{min}^{\prime}(V)\) is the remaining energy of the network without using the proposed cooperative routing. In the network, there are three types of nodes: nodes in the original path π (denoted as R), nodes acting as helpers during CC (denoted as H), and nodes which do not participate in any packet forwarding process even under CC (denoted as U). So V = R ∪ H ∪ U. Assume that E min (S) and \(E_{min}^{\prime}(S)\) are the minimum remaining energy of node set S with and without cooperative routing, respectively. Then we consider the minimum remaining energy of these three types of nodes separately. First, the remaining energy of U does not change, i.e., \(E_{min}(U)=E_{min}^{\prime}(U)\). Second, the remaining energy of helpers H may be reduced by using CC (\(E_{min}(H) \le E_{min}^{\prime}(H)\)). However, since our cooperative routing guarantees that all helpers’ remaining energy is not less than the sender’s remaining energy after cooperative routing, E min (H) ≥ E min (R). This also shows \(E_{min}^{\prime}(H) \ge E_{min}(R)\). Third, the remaining energy of R must be extended by using CC, thus \(E_{min}(R) \ge E_{min}^{\prime}(R)\). Since E min (V) = min {E min (R), E min (H), E min (U)} = min {E min (R), E min (U)} and \(E_{min}^{\prime}(V) = \min \{E_{min}^{\prime}(R),E_{min}^{\prime}(H),E_{min}^{\prime}(U)\}\), we now have \(E_{min}(V) \ge E_{min}^{\prime}(V)\). Therefore, using cooperative routing can indeed lead to larger minimum remaining energy of the network.

4.2 Balancing energy along multiple routes

So far, we only consider to cooperatively route a single flow in the network. But the proposed cooperative routing method can also handle multiple flows by serving them one by one. However, different serving order may lead to different remaining energy of the network. Notice that the remaining energy of nodes changes after serving one flow, thus the selected helper sets for each flow may vary under different serving orders. Figure 5 illustrates such an example. There are two flows from node v 1 and v 3 to v 4, respectively. Assume that the initial energy of the nodes are E 0(v 1) = 32τ, E 0(v 2) = 44τ, E 0(v 3) = 24τ, and E 0(v 4) = 36τ, respectively. If we apply our cooperative routing, both v 1 and v 3 will use v 2 as its helper to perform cooperative routing. However, v 2 helps which flow first will affect the remaining energy of the network. Case 1: v 2 helps v 1 to transmit its packet to v 4 first. After four rounds’ transmission, the final remaining energy of the four nodes are E(v 1) = 28τ, E(v 2) = E(v 3) = 16τ, and E(v 4) = 36τ. Thus, the minimum remaining energy of the network is 16τ. Case 2: v 2 helps v 3 to transmit its packet to v 4 first. After four rounds’ transmission, the final remaining energy of all nodes are E(v 1) = E(v 2) = E(v 3) = 20τ, and E(v 4) = 36τ. Thus, the remaining energy of the network is 20τ. Therefore, the remaining energy level of the network is different with different order. But, for both cases, the remaining energy of the network is better than without cooperative routing which is 8τ.

Fig. 5
figure 5

Example of EBCR routing with multiple flows. Different serving order of CCs will lead to different remaining energy level of the network

Full size image

Fortunately, with any serving order our cooperative routing protocol can guarantee the improvement of minimum remaining energy of the network compared with the routing algorithms without using cooperative routing.

Theorem 2

For a routing task between k pairs of source and destination nodes, the proposed EBCR can improve the minimum remaining energy of the network.

Proof

Again let E min (S) and \(E_{min}^{\prime}(S)\) be the minimum remaining energy of node set S with and without cooperative routing, respectively. When k = 1, we already prove that \(E_{min}(V) \ge E_{min}^{\prime}(V)\) in Theorem 1. Now we consider that k > 1, i.e., there are k packet flows in the network. We want to prove that after all of these k packets \(p_1,p_2,\ldots,p_k\) arrive to their final destinations, \(E_{min}(V) \ge E_{min}^{\prime}(V)\).

The proving technique is similar with the one used in Theorem 1. We now divide the all nodes V into k + 1 disjoint node sets. With the cooperative routing, we divide V into node sets: \(R_1,R_2,\ldots,R_k,U\). Here, R i includes a subset of nodes participate in the cooperative routing of packet p i and U is the set of nodes which do not participate any route. If a node v k participates multiple flows, it only belongs to the set R i in the last flow it participates (i.e., p i is the last packet it transmits). Obviously, \(V = R_1 \cup R_2 \cup \ldots \cup R_k \cup U\). Similarly, we can define k + 1 node sets for the case without cooperative routing, and let them be \(R_1^{\prime}, R_2^{\prime}, \ldots, R_k^{\prime}\) and \(U^{\prime}\). \(V = R_1^{\prime} \cup R_2^{\prime} \cup \cdots \cup R_k^{\prime} \cup U^{\prime}\).

First, \(U \subset U^{\prime}\) since some nodes in \(U^{\prime}\) will be helpers in cooperative routing. Thus, \(E_{min}(U) \ge E_{min}^{\prime}(U^{\prime})\).

Assume that v min is the node with least remaining energy in set R j . It is either a node on the original route of packet p j or a helper for a node on that route. If it is a node on the original route of packet p j , the remaining energy of v min must be larger than or equal to the remaining energy of the same node in the set \(R_j^{\prime}\), because our algorithm can guarantee to enlarge the remaining energy of node v i at each step. Thus, \(E_{min}(R_j) = E(v_{min}) \ge E^{\prime}(v_{min}) \ge E_{min}(R_j^{\prime})\). If the node v min is a helper of a node v p on that route of packet p j , there are three cases and we discuss them one by one.

Case 1

The last packet handled by v p is p j , i.e., \(v_p \in R_j\). Based on our algorithm, E(v min ) ≥ E(v p ), since v min is the helper of v p . Notice that the remaining energy of v p must also be larger than or equal to the remaining energy of the same node in the set \(R_j^{\prime}\). Consequently, \(E_{min}(R_j) = E(v_{min}) \ge E(v_p) \ge E^{\prime}(v_p) \ge E_{min}^{\prime}(R_j^{\prime})\).

Case 2

The last packet handled by v p is not p j but another packet p s , and v p is on the route of packet p s . Thus, \(v_p \in R_s\) and \(v_p \in R_s^{\prime}\). Recall that when v p involves into p j ’s forwarding, the remaining energy of v min is already larger than or equal to the remaining energy of v p , thus E(v min ) ≥ E(v p ). And in the end, the remaining energy of v p is also greater than or equal to the remaining energy of the same node in \(R_s^{\prime}\) at that time. Therefore, \(E_{min}(R_j) = E(v_{min}) \ge E(v_p) \ge E^{\prime}(v_p) \ge E_{min}^{\prime}({R_s^{\prime}})\).

Case 3

The last packet handled by v p is not p j but another packet p s , and v p is a helper for a node v q on the route of packet p s . Based on our cooperative routing algorithm, E(v p ) ≥ E(v q ) and \(E(v_q) \ge E^{\prime}(v_q)\). Hence, \(E_{min}(R_j) = E(v_{min}) \ge E(v_p) \ge E(v_q) \ge E^{\prime}(v_q) \ge E_{min}^{\prime}({R_s^{\prime}})\).

In summary, for any set R i , we can always find a set \(R_j^{\prime}\) such that \(E_{min}(R_i) \ge E_{min}^{\prime}(R_j^{\prime})\). Since \(E_{min}(U) \ge E_{min}^{\prime}(U^{\prime}), E_{min}(V)=\min(E_{min}(R_1),\ldots, E_{min}(R_k),E_{min}(U))\) and \(E_{min}^{\prime}(V)=\min(E_{min}^{\prime}(R_1^{\prime}),\ldots, E_{min}^{\prime}(R_k^{\prime}),E_{min}^{\prime}(U^{\prime}))\), we know that \(E_{min}(V) \ge E_{min}^{\prime}(V)\).

5 Simulation

In this section, we evaluate our proposed EBCR protocol by comparing its performances with the minimum energy path based routing protocol. In addition, we also implement a variation of our EBCR, EBCR back-N, in which the helpers of v i during CC are selected from the last N-hop nodes along the minimum energy path instead of one-hop neighbors of v i . However, the method to select helpers and assign transmission power is the same with EBCR. The underlying wireless networks are randomly generated and have 200 nodes. For convenience, we set the path loss factor α = 2 and the SNR threshold τ = 1. The initial energy level of each node E 0(v i ) is set to 99,000 units. Simulations are run in rounds. Each round we pick one source and one destination and perform one round of routing using different routing algorithms. We ignore the energy consumption of control packets and only consider the energy consumed by data packets, since the size of control packets is relevantly smaller than the size of data packets. Notice that we do consider the energy consumed by sending the data packets to the selected helper set at each node during CC operations, which is the major energy overhead of the proposed method. In addition, as shown in Sect. 4, the computational complexity of the proposed algorithm is just O(m 2) and m is smaller than the number of neighbors of the current node which is usually a small number. Thus, we also ignore the energy consumed from computations.

In the simulations, we take two metrics as the performance measurements:

  • Node Remaining Energy: current energy level of each node E t(v i ). We report the average, minimum, and standard variance of node remaining energy of all nodes in the network.

  • Lifetime: the lifetime of the network is defined as the total number of rounds of routing before the first node runs out of its power.

In the first set of simulations, we generate nine 200-node random networks. For each network, we randomly pick a pair of nodes as the source and the destination and keep running the routing between them using different routing methods, until the first node runs out of its power. In other words, this is a single flow case. The minimum energy routing protocol sends the packet directly along the minimum energy path between the source and the destination, while our EBCR (or EBCR back-N) method uses the neighbors (or last N-hop) of the nodes on the minimum energy path to cooperatively forward the packet. Figure 6 shows the results of one random network. Figure 6(a) plots the minimum node remaining energy of the network at each 200 rounds. With more routing task completed, the minimum node remaining energy of the network reduces. From the simulation results, the EBCR algorithm has the best performance among the three algorithms. The lifetime of EBCR is over six time of the one of the minimum energy routing. This confirms our theoretical proof in Section 4. Notice that EBCR back-N performs worse than EBCR, but still better than the minimum energy routing. Figure 6(b) shows the average node remaining energy of the network at each 200 rounds. Since the minimum energy routing protocol aims to minimize the total transmission energy, its average node remaining energy is better than the other two methods. However, its lifetime is much shorter than EBCR’s. Figure 6(c) shows the standard variance of remaining energy among nodes. The standard variance of node remaining energy of our EBCR routing is the minimum among those of all methods. This shows that it can balance remaining energy among nodes very well. Table 2 shows the lifetime of the nine different networks. The conclusions are consistent.

Fig. 6
figure 6

Results on a 200-node random network with a fixed source-destination pair. a Minimum node remaining energy, b average node remaining energy, c standard variance of node remaining energy

Full size image
Table 2 Lifetime (in rounds) of random networks with a fixed source-destination pair
Full size table

In the second set of simulations, we again generate nine 200-node random networks. Instead of using one fixed source-destination pair, we randomly pick a source-destination pair in each round. Thus, it is a multi-flow case. For each network, we keep running the routing for random source-destination pairs, until the first node runs out of its power. Figure 7 shows the results of one network. Clearly, the lifetime of the network is much longer than the one in the first set of simulation. From the results in Fig. 7, EBCR performs best among all methods in term of minimum remaining energy and energy balancing. Again, the curves of EBCR back-N and minimum energy routing are much shorter than those of EBCR. This confirms that our proposed method can prolong the lifetime significantly. Table 3 also shows the lifetime of all nine networks. Clearly, EBCR can prolong the lifetime of the network in multi-flow networks too.

Fig. 7
figure 7

Results on a 200-node random network with random source-destination pairs. a Minimum node remaining energy, b average node remaining energy, c standard variance of node remaining energy

Full size image
Table 3 Lifetime (in rounds) of random networks with random source-destination pairs
Full size table

For the third set of simulations, we again test all algorithms for the multi-flow cases over 50 different networks. For each network, we run 10,000 rounds (i.e., 10,000 routes) and record the node remaining energy after each 200 rounds. Results over 50 networks are averaged and plotted in Fig. 8. The advantage of EBCR over other two methods is obvious too. In summary, our EBCR algorithm can always balance the remaining energy among nodes and prolong the lifetime of the whole networks.

Fig. 8
figure 8

Results over 10,000 routes on 50 200-node random networks with random source- destination pairs in each round. a Minimum node remaining energy, b average node remaining energy, c standard variance of node remaining energy

Full size image

6 Conclusion

In this paper, we study the impact of CC on energy balancing in multihop routing. We introduce a novel routing scheme (EBCR) to select cooperative relay nodes and their transmission power for each hop. It can be applied to any underlying energy-aware routing protocol, and only need local information to perform the optimization on CCs. We formally prove that our cooperative routing method EBCR can indeed balance the energy among nodes and prolong the remaining lifetime of the network. Simulation results confirm the nice performance of our proposed method over the minimum energy routing. Even though our proposed method can balance the energy over any energy-aware routing protocols, it has several limitations too: (1) our proposed scheme does not work for mobile networks, since node movement will break the optimal selection of cooperative relays; (2) we assume a simplified CC model where fading effect is not considered; (3) in our proposed scheme, each node needs to know it’s position information, which requires certain devices (such as GPS) equipped or additional communication costs. We leave further improvement and implementation of our proposed cooperative routing methods in real networking systems as our next steps.