# Utility-Based Joint Routing, Network Coding, and Power Control for Wireless Ad Hoc Networks

Authors: Kaiqian Ou; Yinlong Xu; Xiumin Wang; Wang Liu
Journal: International Journal of Digital Multimedia Broadcasting
 (2011)

---

## Abstract

Energy saving and high delivery reliability are two essential metrics in wireless ad hoc networks. In this paper, we propose a joint power control and network coding (PCNC) scheme which regulates the transmission power to reduce the overall energy usage and uses network coding to improve reliability by reducing the number of packet retransmissions. To argue for PCNC scheme, we investigate both unicast and multicast routing scenarios. To evaluate routing optimality, we adopt expected utility as a metric, which integrates energy cost, reliability, and benefit value. Based on the expected utility, we explore the optimality in both unicast and multicast routing. For unicast routing, we propose an optimal algorithm. We show the NP-hardness of multicast routing problem, and also design a heuristic solution. Results from simulations demonstrate that PCNC improves the performance in terms of expected utility compared with existing techniques.


---

## Body

## 1. Introduction

Wireless ad hoc networks drew lots of attention in recent years because of its potential applications in various areas. However, ad hoc networks suffer the energy shortage due to the limited power supply devices [1, 2] and unreliable communication caused by the unstable wireless medium [3, 4]. Therefore, saving energy and improving message delivery reliability are two important issues in the design of wireless ad hoc protocols.Wireless communications (e.g., sending a message) are usually the most energy-consuming events in wireless networks. Thus, one of the most straight approaches to reduce energy consumption is decreasing the transmission power at the senders. However, decreasing the transmission power will reduce the reliability of the link, which may incur packet loss during data propagation [5]. Packet loss leads to packet retransmissions, which consumes more energy. To balance energy cost and reliability, several approaches have been proposed, especially, transmission power control (TPC) and network coding (NC).TPC, which has been studied in [5, 6], focuses on adjusting transmission power level on each sender to reduce the energy consumption. In [5], TPC is applied to study the tradeoff between end-to-end reliability and energy consumption based on the probability link model. Different from [5], Li et al. [6] integrated TPC with retransmission to address the problem of energy-efficient reliable routing for wireless ad hoc networks. With TPC, the transmission power can be decreased at each node for the packet retransmissions. Their experimental results also demonstrate the benefits of adopting TPC and retransmission.Recently, NC has received extensive research attentions in networking area. Instead of just forwarding the input packets, a relay node with NC encodes input packets into some encoded ones and sends them out. After receiving the required number of encoded packets, a receiver can decode out the original packets. Recent work [7] shows that NC can improve reliability by reducing the number of packet retransmissions in wireless lossy networks.Motivated by the advantages of TPC (reducing transmission power) and reliability benefit of NC (reducing retransmission times), this paper studies the tradeoff between energy cost and reliability using a joint power control and network coding (PCNC) scheme. We will study the benefits of PCNC on unicast and multicast in wireless ad hoc network and adopt a widely used metric,expected utility [8–11], which integrates link cost, link stability, and system benefit to evaluate the performance of the system. We define the system utility as(1)U=AR-C,
where the cost C of a system is the total expected energy consumption, and the benefit A of a system is the gain of successful message delivery, and R is the reliability of the routing. Delivery reliability and energy cost depend on not only routing path, but also how to conduct TPC and NC at senders. Therefore, the challenge is that a routing algorithm based on PCNC needs to determine not only the optimal routing path (or tree), but also the optimal combination of transmission power assignment and coding strategy at each sender.The main contributions of our work are summarized as follows.(1)
We systematically integrate routing, TPC, and NC in wireless ad hoc networks based on utility metric.(2)
For unicast, we propose an optimal routing algorithm to determine the maximum utility path with the optimal combination of transmission power assignment and coding strategy at each sender along the path.(3)
For multicast, we show that finding an optimal multicast tree to maximize the expected utility is NP-hard and propose a heuristic approach named MIEUDF.(4)
Simulation results show that our proposed routing schemes outperform existing schemes in terms of expected utility in both unicast and multicast scenarios.The rest of the paper is organized as follows. We first introduce related work in Section2. Section 3 gives the preliminaries, which show the network coding scheme and the link model. The utility metric is described in Section 4. In Section 5, we propose the optimal routing algorithm for unicast session. The heuristic solution of multicast routing is proposed in Section 6. The simulation results are presented in Section 7. Finally, we conclude the paper in Section 8.


## 2. Related Work

Transmission power control (TPC), which allows a sender to adjust its transmission power level, is used to improve the performance of the network. Correia et al. [12] adopted TPC to decrease energy consumption while maintaining the reliability of the channel in wireless sensor networks. Pierpaolo et al. [13] proposed a distributed TPC method to improve the energy efficiency of routing algorithms in ad hoc networks. By integrating TPC with retransmission, Li et al. [6] proposed energy-efficient reliable routing schemes in wireless ad hoc networks.Network coding (NC) is an approach pioneered by Ahlswede et al. [14], with which a relay node encodes the input packets and outputs the encoded ones. It has been shown that NC offers exciting benefits in terms of throughput, reliability, cost, and delay in wireless networks [15–18]. Specifically, the reliability gain of NC was studied recently in [7, 19, 20]. The work in [19] confirmed that NC could increase the reliability by reducing the number of transmissions in unicast communication. In multicast, the work in [7, 20] showed that NC improves network reliability.A new metric calledexpected utility was developed and shown achieving a better performance than other metric (cost and reliability)[10]. Later, expected utility was widely used to evaluate system performance [8, 9, 11]. Based on expected utility metric, M. M. Lu and J. Wu [8] applied network coding to routing problems in unreliable wireless environments and demonstrated that network coding improves the system performance. J. Wu, M. Lu, and F. Li [9] explored the optimality of opportunistic routing (OR) for a utility-based routing, and studied [11] the data-gathering problem in wireless sensor networks by adopting the utility-based metric.


## 3. Preliminaries

We summarize the main notations used in this paper in Table1. Suppose that a given message consisting of x equal-size packets is assigned with a benefit value A, that is, the system will obtain benefit value A for each destination successfully receiving the message.Table 1
Summary of key notations.
NotationMeaningxThe number of equal-size packets in a messageABenefit value of given messageVSet containing all nodes in a networkdu,vThe distance between nodeu and vpuTransmission power level of nodeunuPredetermined number of transmitted packets on nodeuru,vPacket link reliability over link(u,v)Ru,vMessage link reliability over link(u,v)Ru~vMessage path reliability along path from nodeu to vCuPre-determined energy consumption on senderuUQExpected utility along pathQREUuRemaining expected utility of nodeu to a given destinationUTExpected utility through treeTIEUuIncremental expected utility of added destinationu in MIEUDF


### 3.1. Network Coding Scheme and Assumptions

Network coding scheme allows intermediate node(s) between the source and destination(s) to encode the incoming packets, and then forward the encoded ones. In this paper, we assume that the given original message is divided by source node intox fixed-sized packets, B1,B2,…,Bx. In this paper, we assume that random linear network coding over a finite field GF(q) is adopted in the wireless network, that is, a transmitted packet is a linear combination of B1,B2,…,Bx with coefficients are randomly selected from GF(q) [21]. Some more assumptions on coding scheme are as follows.  (1)
There is a limitation on the number of encoded packets of a message transmitted (also calledpre-determined number) at each sender i, denoted as ni, which is adjustable as in [8]. If no limitation on the number of transmitted packets, the power cost may be extremely high for energy-limited devices.(2)
An intermediate node will transmit its pre-determined number of encoded packets only when it has receivedx independent encoded packets. Without this assumption, more energy consumption is wasted on sending useless packets that cannot be used to reconstruct the original message.Based on the above coding scheme, a message is transmitted hop-by-hop from source to destination in form of encoded packets. However, a message is not guaranteed to be successfully delivered to a destination, due to pre-determined number rather than unlimited number of transmitted encoded packets. The pre-determined number should reflect the importance of the corresponding message, because an important message requires high reliability and more encoded packets being transmitted. The increment of the number of transmitted packets can directly increase the transmission reliability (see Section4.3). Under this coding scheme, the tradeoff between expected energy consumption and message delivery reliability is explored in the rest of this paper.


### 3.2. Link Model

In this paper, we use the similar link model in [5], which is also widely used in other works [22–24]. Assume that the transmitted packets are fixed-size of B bits, and all nodes transmit at the same rate.Consider the link shown in Figure1, where a packet of a message is transmitted from node s to d through the zero mean additive white Gaussian noise (AWGN) channel. Following [5], the probability of packet successful reception is given by  (this formula is achieved using AWGN channel with Rayleigh fading assuming the sender does not have information about the fading state, See [5] for more details) (2)rs,d(ds,d,ps)=exp⁡(-ds,dk(2B-1)βps),
where B is the packet size, ds,d is the distance between node s and d, ps is the chosen transmission power level at node s, and k is the propagation power loss exponent, usually assumed to be between 2 to 4. As in [5], the noise power and fading parameter are assumed to be constant across the network, denoted as β. Since B, k, and β are all assumed to be constant, a sender can adjust its transmission power to control the probability of packet successful reception over a link.Figure 1
Link model: nodes sends a packet of message to node d over link (s,d).In this section, we introduced two adjustable parameters at each senderi, transmission power level pi and pre-determined number ni of transmitted packets. In the next section, we will analyze how these adjustable parameters at senders affect energy consumption and message delivery reliability, and hence the expected utility.


## 3.1. Network Coding Scheme and Assumptions

Network coding scheme allows intermediate node(s) between the source and destination(s) to encode the incoming packets, and then forward the encoded ones. In this paper, we assume that the given original message is divided by source node intox fixed-sized packets, B1,B2,…,Bx. In this paper, we assume that random linear network coding over a finite field GF(q) is adopted in the wireless network, that is, a transmitted packet is a linear combination of B1,B2,…,Bx with coefficients are randomly selected from GF(q) [21]. Some more assumptions on coding scheme are as follows.  (1)
There is a limitation on the number of encoded packets of a message transmitted (also calledpre-determined number) at each sender i, denoted as ni, which is adjustable as in [8]. If no limitation on the number of transmitted packets, the power cost may be extremely high for energy-limited devices.(2)
An intermediate node will transmit its pre-determined number of encoded packets only when it has receivedx independent encoded packets. Without this assumption, more energy consumption is wasted on sending useless packets that cannot be used to reconstruct the original message.Based on the above coding scheme, a message is transmitted hop-by-hop from source to destination in form of encoded packets. However, a message is not guaranteed to be successfully delivered to a destination, due to pre-determined number rather than unlimited number of transmitted encoded packets. The pre-determined number should reflect the importance of the corresponding message, because an important message requires high reliability and more encoded packets being transmitted. The increment of the number of transmitted packets can directly increase the transmission reliability (see Section4.3). Under this coding scheme, the tradeoff between expected energy consumption and message delivery reliability is explored in the rest of this paper.


## 3.2. Link Model

In this paper, we use the similar link model in [5], which is also widely used in other works [22–24]. Assume that the transmitted packets are fixed-size of B bits, and all nodes transmit at the same rate.Consider the link shown in Figure1, where a packet of a message is transmitted from node s to d through the zero mean additive white Gaussian noise (AWGN) channel. Following [5], the probability of packet successful reception is given by  (this formula is achieved using AWGN channel with Rayleigh fading assuming the sender does not have information about the fading state, See [5] for more details) (2)rs,d(ds,d,ps)=exp⁡(-ds,dk(2B-1)βps),
where B is the packet size, ds,d is the distance between node s and d, ps is the chosen transmission power level at node s, and k is the propagation power loss exponent, usually assumed to be between 2 to 4. As in [5], the noise power and fading parameter are assumed to be constant across the network, denoted as β. Since B, k, and β are all assumed to be constant, a sender can adjust its transmission power to control the probability of packet successful reception over a link.Figure 1
Link model: nodes sends a packet of message to node d over link (s,d).In this section, we introduced two adjustable parameters at each senderi, transmission power level pi and pre-determined number ni of transmitted packets. In the next section, we will analyze how these adjustable parameters at senders affect energy consumption and message delivery reliability, and hence the expected utility.


## 4. Utility Metric Model

In this section, we first introduce utility metric for both unicast path and multicast tree as functions of energy consumption and transmission reliability. Then, we study how to calculate energy consumption and message link/path reliability based on TPC and NC.


### 4.1. Utility for Unicast

We first consider a simple case, where a source nodes sends a message to a destination node d using a link (s,d), as illustrated in Figure 1. Denote pre-determined energy consumption at node s as Cs which is defined as the transmission power times the pre-determined number of transmitted packets and message link reliability as Rs,d which is defined as the probability of x independent encoded packets being successfully received by d. The system has the probability of Rs,d to obtain benefit value A at the cost of Cs, and may consume energy Cs obtaining zero benefit with the probability of 1-Rs,d with less than x independent encoded packets being successfully received by d. The expected utility over this link is(3)Rs,d(A-Cs)+(1-Rs,d)(-Cs)=Rs,d×A-Cs.We then consider a general case with single destination where source nodes sends the message to destination d over path Q=〈s=v0,v1,v2,…,vH-1,vH=d〉, as shown in Figure 2. For a multihop path scenario, the probability of destination d successfully receiving the message is message path reliability, that is, the probability that a message is successfully transmitted over all links along Q rather than message link reliability in Formula (3). Let Rvt~vh denote the message path reliability from node vt to vh along the path. According to network coding scheme described in Section 3.1, each intermediate node will relay the message to its downstream node only after it successfully receives the message from the source. So, Rvt~vh=∏i=th-1Rvi,vi+1. Since the probability of destination d successfully receiving the message is Rv0~vH, the system gets expected benefit Rv0~vH×A. For an intermediate node vi, the probability of consuming pre-determined energy is equal to the probability that the message is successfully transmitted from source to vi, that is, Rv0~vi. Therefore, expected energy consumption at node vi is equal to Cvi×Rv0~vi. The total expected energy cost along the path is the sum of the expected energy consumption at each sender, that is, ∑i=0H-1Cvi×Rv0~vi. Then, the expected utility of path Q, denoted as UQ, is expected benefit contributed by the single destination minus the total expected energy cost at all senders along the path(4)UQ=Rv0~vH×A-∑i=0H-1Cvi×Rv0~vi,
where Rv0~vi=∏j=0i-1Rvj,vj+1.Figure 2
Unicast path example: nodes sends a message to node d over path Q=〈s=v0,v1,v2,…,vH-1,vH=d〉.


### 4.2. Utility for Multicast

We consider the scenario consisting of multiple destinations where a source nodes sends the message to multiple destinations through a multicast tree as shown in Figure 3. Let T be the multicast tree, and D be the set of destinations, including all leaves and some intermediate nodes of T. A node i∈D may contribute benefit value A to the system with a probability of Rs~i because the probability of node i successfully receiving the message is Rs~i. Let SS be the set of senders on the tree, including the source and all intermediate nodes. A node j∈SS may have pre-determined energy consumption with a probability of Rs~j because node j consumes energy only after it successfully receives the message from the source s. We use UT to represent the expected utility of tree T. The expected utility of the multicast tree is the aggregated benefit of all destinations minus the total expected energy cost at all senders on the tree:(5)UT=∑i∈DRs~i×A-∑j∈SSRs~j×Cj,
where Rs~t=∏∀(u,v)∈s~tRu,v.Figure 3
Multicast tree example: nodes sends a message to multiple destinations in D through the tree.


### 4.3. Energy Consumption and Message Reliability

In this subsection, we study how to calculate energy consumption and message link reliability based on the two parameters at each sender, transmission power and pre-determined number of transmitted packets.Let(u,v) be a link, where node u is the sender and node v is u's downstream node. Assume that the transmission power and the pre-determined number of transmitted packets at u are pu and nu, respectively. According to the definition of predetermined energy consumption,(6)Cu=pu×nu.In the following, we are to calculateRu,v based on pu and nu. From (2), the packet delivery reliability over linkru,v, that is, the probability of a packet being successfully transmitted over a link can be obtained as(7)ru,v(pu,du,v)=exp⁡(-du,vk(2B-1)βpu).Since the message link reliabilityRu,v is the probability that x independent encoded packets being successfully transmitted over link (u,v), we can calculate Ru,v by summing up the probability that exactly j(j≥x) packets successfully transmitted over the link. Without loss of generality, we assume that different packet transmissions are independent. Therefore, the packet transmissions can be regarded as a Bernoulli experiment. So, the probability of successfully receiving exact j packets follows binomial distribution, (nuj)·ru,vj(1-ru,v)nu-j.By summing up the totalnu-x+1 probabilities that exact j (nu≥j≥x) out of nu packets are successfully received by node v, we obtain the expression of the message link reliability over link (u,v) as(8)Ru,v=∑j=xnu(nuj)ru,vj(1-ru,v)nu-j,
where ru,v=exp(du,vk(2B-1)/βpu).From (6) and (8), the predetermined energy consumption at u, Cu, and the massage link reliability over link (u,v), Ru,v, both depend on the adjustable transmission power and pre-determined number of transmitted packets at sender u. In the following, we use Cu(pu,nu) to denote the predetermined energy consumption at node u, and Ru,v(pu,nu) to denote the message link reliability over link (u,v).By applying (6) and (8) to (4) or (5), we can calculate the expected utility for a given path or tree based on the transmission power level and the pre-determined number of transmitted packets at each sender.


## 4.1. Utility for Unicast

We first consider a simple case, where a source nodes sends a message to a destination node d using a link (s,d), as illustrated in Figure 1. Denote pre-determined energy consumption at node s as Cs which is defined as the transmission power times the pre-determined number of transmitted packets and message link reliability as Rs,d which is defined as the probability of x independent encoded packets being successfully received by d. The system has the probability of Rs,d to obtain benefit value A at the cost of Cs, and may consume energy Cs obtaining zero benefit with the probability of 1-Rs,d with less than x independent encoded packets being successfully received by d. The expected utility over this link is(3)Rs,d(A-Cs)+(1-Rs,d)(-Cs)=Rs,d×A-Cs.We then consider a general case with single destination where source nodes sends the message to destination d over path Q=〈s=v0,v1,v2,…,vH-1,vH=d〉, as shown in Figure 2. For a multihop path scenario, the probability of destination d successfully receiving the message is message path reliability, that is, the probability that a message is successfully transmitted over all links along Q rather than message link reliability in Formula (3). Let Rvt~vh denote the message path reliability from node vt to vh along the path. According to network coding scheme described in Section 3.1, each intermediate node will relay the message to its downstream node only after it successfully receives the message from the source. So, Rvt~vh=∏i=th-1Rvi,vi+1. Since the probability of destination d successfully receiving the message is Rv0~vH, the system gets expected benefit Rv0~vH×A. For an intermediate node vi, the probability of consuming pre-determined energy is equal to the probability that the message is successfully transmitted from source to vi, that is, Rv0~vi. Therefore, expected energy consumption at node vi is equal to Cvi×Rv0~vi. The total expected energy cost along the path is the sum of the expected energy consumption at each sender, that is, ∑i=0H-1Cvi×Rv0~vi. Then, the expected utility of path Q, denoted as UQ, is expected benefit contributed by the single destination minus the total expected energy cost at all senders along the path(4)UQ=Rv0~vH×A-∑i=0H-1Cvi×Rv0~vi,
where Rv0~vi=∏j=0i-1Rvj,vj+1.Figure 2
Unicast path example: nodes sends a message to node d over path Q=〈s=v0,v1,v2,…,vH-1,vH=d〉.


## 4.2. Utility for Multicast

We consider the scenario consisting of multiple destinations where a source nodes sends the message to multiple destinations through a multicast tree as shown in Figure 3. Let T be the multicast tree, and D be the set of destinations, including all leaves and some intermediate nodes of T. A node i∈D may contribute benefit value A to the system with a probability of Rs~i because the probability of node i successfully receiving the message is Rs~i. Let SS be the set of senders on the tree, including the source and all intermediate nodes. A node j∈SS may have pre-determined energy consumption with a probability of Rs~j because node j consumes energy only after it successfully receives the message from the source s. We use UT to represent the expected utility of tree T. The expected utility of the multicast tree is the aggregated benefit of all destinations minus the total expected energy cost at all senders on the tree:(5)UT=∑i∈DRs~i×A-∑j∈SSRs~j×Cj,
where Rs~t=∏∀(u,v)∈s~tRu,v.Figure 3
Multicast tree example: nodes sends a message to multiple destinations in D through the tree.


## 4.3. Energy Consumption and Message Reliability

In this subsection, we study how to calculate energy consumption and message link reliability based on the two parameters at each sender, transmission power and pre-determined number of transmitted packets.Let(u,v) be a link, where node u is the sender and node v is u's downstream node. Assume that the transmission power and the pre-determined number of transmitted packets at u are pu and nu, respectively. According to the definition of predetermined energy consumption,(6)Cu=pu×nu.In the following, we are to calculateRu,v based on pu and nu. From (2), the packet delivery reliability over linkru,v, that is, the probability of a packet being successfully transmitted over a link can be obtained as(7)ru,v(pu,du,v)=exp⁡(-du,vk(2B-1)βpu).Since the message link reliabilityRu,v is the probability that x independent encoded packets being successfully transmitted over link (u,v), we can calculate Ru,v by summing up the probability that exactly j(j≥x) packets successfully transmitted over the link. Without loss of generality, we assume that different packet transmissions are independent. Therefore, the packet transmissions can be regarded as a Bernoulli experiment. So, the probability of successfully receiving exact j packets follows binomial distribution, (nuj)·ru,vj(1-ru,v)nu-j.By summing up the totalnu-x+1 probabilities that exact j (nu≥j≥x) out of nu packets are successfully received by node v, we obtain the expression of the message link reliability over link (u,v) as(8)Ru,v=∑j=xnu(nuj)ru,vj(1-ru,v)nu-j,
where ru,v=exp(du,vk(2B-1)/βpu).From (6) and (8), the predetermined energy consumption at u, Cu, and the massage link reliability over link (u,v), Ru,v, both depend on the adjustable transmission power and pre-determined number of transmitted packets at sender u. In the following, we use Cu(pu,nu) to denote the predetermined energy consumption at node u, and Ru,v(pu,nu) to denote the message link reliability over link (u,v).By applying (6) and (8) to (4) or (5), we can calculate the expected utility for a given path or tree based on the transmission power level and the pre-determined number of transmitted packets at each sender.


## 5. Unicast Routing

In this section, we will model unicast routing and propose an optimal unicast routing algorithm.


### 5.1. Problem Statement

In a wireless ad hoc network, a source nodes initiates a unicast session to send a message to a destination d. The problem is to find a unicast path to deliver the message from s to d such that the expected utility is maximized. Let Q be a unicast path from s to d, Rs~iQ be the message path reliability from source s to node i along the path Q, where i is a node on Q. Let CjQ be the pre-determined energy consumption at sender j. According to (4), the expected utility along path Q is(9)Rs~dQ×A-∑j∈SSQRs~jT×CjQ,
where SSQ is the set of senders on path Q. Then, the maximum utility unicast problem can be formulated as(10)MaximizeUQ=Rs~dQ×A-∑j∈SSQRs~jQ×CjQ,Subjecttopj∈LS,j∈SSQ,nj∈NS,
where Q is a feasible path from s to d, LS={pmax/L,2pmax/L,…,pmax} is the set of transmission power levels available at each sender, pmax is the maximum possible power level, NS={x,x+1,x+2,x+3,…} is the set of the feasible pre-determined number of transmitted packets (note: at leastxpackets must be received by a node; otherwise, the destination cannot reconstruct the original message). In Formula (10), Rs~iQ and CjQ can be calculated according to Formula (6) and (8), respectively.The difficulty of optimal unicast routing is that the routing algorithm needs to determine not only the optimal routing path, but also the optimal selections of both transmission power and pre-determined number of transmitted packets at each sender along the path.


### 5.2. Optimal Solution

In this subsection, we propose an optimal unicast routing algorithm. An important observation is that the calculation of path utility can be conducted in a recursive way. Consider a pathQ=〈s=v0,v1,v2,…,vH-1,vH=d〉, as shown in Figure 2. Define the expected utility of subpath from vi to vH as the remaining expected utility (REU) of node vi, denoted as REUvi. Specially, REUv0=REUs=UQ and REUd=REUvH=A because the initial benefit value of the message is A. From (4), the recursive expression of REU is(11)REUvi={Aifi=H,Rvi,vi+1REUvi+1-Cviif0≤i≤H-1.Therefore, we can recursively apply Formula (11) starting from destination d to calculate the expected utility of any sub-path. Since Rvi,vi+1≤1 and Cvi>0, each iterative step of the calculation will reduce REU from the original value of A. To find the maximum utility path to destination d is equal to finding the minimum REU reduction path starting from the destination. So, the utility-based routing problem is similar to shortest path problem. But there are some differences: (1) our problem measures the distance in terms of expected utility rather than cost; (2) the solution of our problem requires to determine not only the next hop but also the values of both the transmission power and the pre-determined number of transmitted packets at each sender.Based on the Dijkstra's algorithm for shortest path problem, we design a routing Algorithm1 to maximize the expected utility from a source node to a destination node.Algorithm 1:Unicast(V,s,d,A).
(1)for allv∈Vdo(2)REUv←-∞.(3)   assign benefit value to destinationd:REUd←A.(4)end for(5)whiles∉Vdo(6)   Find nodev∈V with the largest REU.(7)   Remove nodev from V.(8)    For each nodeu∈V RELAX(v,u).(9)end while(10)procedure Relax(v, u)(11)   Find the optimalpu*and nu* to maximize Ru,v(pu, nu)×(12)REUv–Cu(pu,nu).(13)ifREUu< Ru,v(pu*, nu*)×REUv–Cu(pu*,nu*). then(14)   UpdateREUu with pu* and  nu*.(15)end if(16)end procedureIn Algorithm1, V is the set of all nodes in a network. pu and nu are the transmission power and pre-determined number of transmitted packets at u, respectively. pu* and nu* are the corresponding optimal values of pu and nu to maximize the expected utility over the link (u,v). The existence of pu* and nu* is guaranteed by the following theorem.Theorem 1.
For any link(u,v), the optimal values of both transmission power level  pu* and pre-determined number of transmitted packets  nu* exist such that the expected utility  Ru,v(pu,nu)×REUv-Cu(pu,nu) over the link is maximized.Proof.
See The appendix.The algorithm starts from the destination with the initial message benefit valueA and REUs of other nodes are initially set to -∞. At the beginning, V consists of all nodes in the network. In each iteration, this algorithm not only selects the node that reduces the REU to the least, that is, the node with largest REU will be removed from V, but also determines the corresponding optimal values of the transmission power and pre-determined number of transmitted packets at the selected node. The REU will be reduced at each intermediate node going backwards from the destination to the source node. When source s is selected and removed from V, the algorithm stops and outputs optimal path from s to d. Since Algorithm 1 is similar to Dijkstra algorithm, the time complexity of Algorithm 1 is O(|V|2).When a routing path for a given source-destination pair is determined, the source divides the message intox packets, generates ns* encoded packets, and transmits them using transmission power ps* to its downstream node along the optimal path. Only after receiving x linearly independent packets from the upstream node, an intermediate node i begins to send ni* encoded packets with optimal transmission power pi* to the next hop.


## 5.1. Problem Statement

In a wireless ad hoc network, a source nodes initiates a unicast session to send a message to a destination d. The problem is to find a unicast path to deliver the message from s to d such that the expected utility is maximized. Let Q be a unicast path from s to d, Rs~iQ be the message path reliability from source s to node i along the path Q, where i is a node on Q. Let CjQ be the pre-determined energy consumption at sender j. According to (4), the expected utility along path Q is(9)Rs~dQ×A-∑j∈SSQRs~jT×CjQ,
where SSQ is the set of senders on path Q. Then, the maximum utility unicast problem can be formulated as(10)MaximizeUQ=Rs~dQ×A-∑j∈SSQRs~jQ×CjQ,Subjecttopj∈LS,j∈SSQ,nj∈NS,
where Q is a feasible path from s to d, LS={pmax/L,2pmax/L,…,pmax} is the set of transmission power levels available at each sender, pmax is the maximum possible power level, NS={x,x+1,x+2,x+3,…} is the set of the feasible pre-determined number of transmitted packets (note: at leastxpackets must be received by a node; otherwise, the destination cannot reconstruct the original message). In Formula (10), Rs~iQ and CjQ can be calculated according to Formula (6) and (8), respectively.The difficulty of optimal unicast routing is that the routing algorithm needs to determine not only the optimal routing path, but also the optimal selections of both transmission power and pre-determined number of transmitted packets at each sender along the path.


## 5.2. Optimal Solution

In this subsection, we propose an optimal unicast routing algorithm. An important observation is that the calculation of path utility can be conducted in a recursive way. Consider a pathQ=〈s=v0,v1,v2,…,vH-1,vH=d〉, as shown in Figure 2. Define the expected utility of subpath from vi to vH as the remaining expected utility (REU) of node vi, denoted as REUvi. Specially, REUv0=REUs=UQ and REUd=REUvH=A because the initial benefit value of the message is A. From (4), the recursive expression of REU is(11)REUvi={Aifi=H,Rvi,vi+1REUvi+1-Cviif0≤i≤H-1.Therefore, we can recursively apply Formula (11) starting from destination d to calculate the expected utility of any sub-path. Since Rvi,vi+1≤1 and Cvi>0, each iterative step of the calculation will reduce REU from the original value of A. To find the maximum utility path to destination d is equal to finding the minimum REU reduction path starting from the destination. So, the utility-based routing problem is similar to shortest path problem. But there are some differences: (1) our problem measures the distance in terms of expected utility rather than cost; (2) the solution of our problem requires to determine not only the next hop but also the values of both the transmission power and the pre-determined number of transmitted packets at each sender.Based on the Dijkstra's algorithm for shortest path problem, we design a routing Algorithm1 to maximize the expected utility from a source node to a destination node.Algorithm 1:Unicast(V,s,d,A).
(1)for allv∈Vdo(2)REUv←-∞.(3)   assign benefit value to destinationd:REUd←A.(4)end for(5)whiles∉Vdo(6)   Find nodev∈V with the largest REU.(7)   Remove nodev from V.(8)    For each nodeu∈V RELAX(v,u).(9)end while(10)procedure Relax(v, u)(11)   Find the optimalpu*and nu* to maximize Ru,v(pu, nu)×(12)REUv–Cu(pu,nu).(13)ifREUu< Ru,v(pu*, nu*)×REUv–Cu(pu*,nu*). then(14)   UpdateREUu with pu* and  nu*.(15)end if(16)end procedureIn Algorithm1, V is the set of all nodes in a network. pu and nu are the transmission power and pre-determined number of transmitted packets at u, respectively. pu* and nu* are the corresponding optimal values of pu and nu to maximize the expected utility over the link (u,v). The existence of pu* and nu* is guaranteed by the following theorem.Theorem 1.
For any link(u,v), the optimal values of both transmission power level  pu* and pre-determined number of transmitted packets  nu* exist such that the expected utility  Ru,v(pu,nu)×REUv-Cu(pu,nu) over the link is maximized.Proof.
See The appendix.The algorithm starts from the destination with the initial message benefit valueA and REUs of other nodes are initially set to -∞. At the beginning, V consists of all nodes in the network. In each iteration, this algorithm not only selects the node that reduces the REU to the least, that is, the node with largest REU will be removed from V, but also determines the corresponding optimal values of the transmission power and pre-determined number of transmitted packets at the selected node. The REU will be reduced at each intermediate node going backwards from the destination to the source node. When source s is selected and removed from V, the algorithm stops and outputs optimal path from s to d. Since Algorithm 1 is similar to Dijkstra algorithm, the time complexity of Algorithm 1 is O(|V|2).When a routing path for a given source-destination pair is determined, the source divides the message intox packets, generates ns* encoded packets, and transmits them using transmission power ps* to its downstream node along the optimal path. Only after receiving x linearly independent packets from the upstream node, an intermediate node i begins to send ni* encoded packets with optimal transmission power pi* to the next hop.


## 6. Multicast Routing

In this section, we first formulate the maximum utility multicast routing problems, which is shown to be NP-hard. Then, a heuristic solution for multicast routing problem is proposed.


### 6.1. Problem Statement

Given a wireless network with a set of nodesV, a source node s∈V initiates a multicast session and sends a message to a set of destinations D⊆V. It is to find a multicast tree to deliver the message from the source to all destinations such that the expected utility is maximized. The problem is called maximum-utility multicast routing problem (MUMRP).LetRs~iT be the message path reliability from source s to a node i along a muticast tree T. Denote the set of senders on T as SST. Let CjT be the pre-determined energy consumption at sender j∈SST. According to Formula (5), the expected utility of tree T is(12)∑i∈DRs~iT×A-∑j∈SSTRs~jT×CjT.Then, the MUMR problem can be formulated as(13)MaximizeUT=∑i∈DRs~iT×A-∑j∈SSTRs~jT×CjT,Subjecttopj∈LS,nj∈NS,j∈SST,
where T is a feasible multicast tree connecting the source to all destinations in D. LS={pmax/L,2pmax/L,…,pmax} and NS={x,x+1,x+2,x+3,…} are the same as in Section 5. In (13), Rs~iT and CjT can be calculated according to Formulae (6) and (8), respectively.The difficulty to find a multicast tree with maximum-utility lies in that it not only determines the optimal tree but also optimal values of transmission power and pre-determined number of transmitted packets at each sender of the tree.The maximum-utility broadcast routing problem (MUBRP) is a special case of MUMRP. If the reliability of eligible links is 1 and pre-determined number of packets is fixed across the network, MUBRP can be reduced to the geometric minimum broadcast cover problem (GMBC) [25], which is shown to be NP-hard. Hence, MUBRP and further MUMRP are both NP-hard. In the following, we design heuristic solutions for MUMRP.


### 6.2. Heuristic Solution for MUMRP

In this subsection, we propose a heuristic solution for MUMRP. For MUMRP, each destination node inD will contribute benefit value A with successful message reception in a multicast session. Based on Prim's algorithm, we propose a greedy-based heuristic,maximum incremental expected utility destination first algorithm (MIEUDF), which greedily inserts a path that connects a destination to the current tree such that the incremental expected utility (IEU) of the added destination is maximized. The IEU of the new added destination is defined as its expected benefit minus corresponding expected energy cost. The MIEUDF algorithm iteratively adds the destination with the maximum IEU from the set of remaining destinations to an existing tree. The algorithm in pseudocode is presented in Algorithm 2. In Algorithm 2, IEUi denotes the IEU of destination i. The aggregated expected utility of the multicast tree is denoted as Uall. The multicast tree generated is recorded in T.Algorithm 2:MIEUDF(V,D,s,A,T).
(1)for allv∈D do(2)IEUv and s~*v assigned by UNICAST(V,s,v,A).(3)end for(4)T with only root s(5)Uall⟵0.(6)whileD≠∅ do(7)  remove the maximum IEU destinationu from D.(8)Uall←Uall+IEUu.(9)  insert the branch connectingu to T.(10)  determinept* and nt* for each sender t along the inserted(11)  branch ofT.(12)for each node v∈Ddo(13)ifs~*v shares sub-path with the inserted branch then(14)    increaseIEUvby expected power cost along the(15)    sharing sub-path.(16)end if(17)end for(18)end whileThe algorithm starts with a tree consisting of only the source nodes and Uall being zero. At the beginning, the IEU of each destination is assigned with the expected utility along the optimal path from source to itself generated by Algorithm 1. The optimal path from source s to any destination u is recorded as s~*u, and all generated optimal paths build up a tree rooted at s.At each step ofRepeat loop in the algorithm, the destination with largest IEU, say u, is removed from D and connected to the existing tree T through its optimal path, and contributes IEUu to Uall. For any relay node t along the new inserted branch of tree T, its transmission power and pre-determined number of transmitted packets, pt* and nt*, will be determined. Then, IEU of any other destination v will be increased by the expected energy cost along the inserted branch if s~*v share some sub-path with the branch, because the expected energy consumption for the sharing sub-path has been included in the newly inserted branch. During each iterative step, not only a destination is connected to the existing T, but also the corresponding optimal values of the transmission power and pre-determined number of transmitted packets of the newly added senders are determined. When D is empty, the algorithm stops and outputs a multicast tree T connecting the source to all destinations in D. Since Algorithm 2 calls Algorithm 1|D| times, its time complexity is O(|D|×|V|2).After multicast routing tree is determined,s divides the message into x packets, generates ns* encoded packets, and broadcasts the encoded packets to its downstreaming nodes along the tree using transmission power ps*. Only after receiving x linearly independent packets from its parent node, an intermediate node i in the tree begins to send ni* encoded packets to its children with transmission power level pi*.


## 6.1. Problem Statement

Given a wireless network with a set of nodesV, a source node s∈V initiates a multicast session and sends a message to a set of destinations D⊆V. It is to find a multicast tree to deliver the message from the source to all destinations such that the expected utility is maximized. The problem is called maximum-utility multicast routing problem (MUMRP).LetRs~iT be the message path reliability from source s to a node i along a muticast tree T. Denote the set of senders on T as SST. Let CjT be the pre-determined energy consumption at sender j∈SST. According to Formula (5), the expected utility of tree T is(12)∑i∈DRs~iT×A-∑j∈SSTRs~jT×CjT.Then, the MUMR problem can be formulated as(13)MaximizeUT=∑i∈DRs~iT×A-∑j∈SSTRs~jT×CjT,Subjecttopj∈LS,nj∈NS,j∈SST,
where T is a feasible multicast tree connecting the source to all destinations in D. LS={pmax/L,2pmax/L,…,pmax} and NS={x,x+1,x+2,x+3,…} are the same as in Section 5. In (13), Rs~iT and CjT can be calculated according to Formulae (6) and (8), respectively.The difficulty to find a multicast tree with maximum-utility lies in that it not only determines the optimal tree but also optimal values of transmission power and pre-determined number of transmitted packets at each sender of the tree.The maximum-utility broadcast routing problem (MUBRP) is a special case of MUMRP. If the reliability of eligible links is 1 and pre-determined number of packets is fixed across the network, MUBRP can be reduced to the geometric minimum broadcast cover problem (GMBC) [25], which is shown to be NP-hard. Hence, MUBRP and further MUMRP are both NP-hard. In the following, we design heuristic solutions for MUMRP.


## 6.2. Heuristic Solution for MUMRP

In this subsection, we propose a heuristic solution for MUMRP. For MUMRP, each destination node inD will contribute benefit value A with successful message reception in a multicast session. Based on Prim's algorithm, we propose a greedy-based heuristic,maximum incremental expected utility destination first algorithm (MIEUDF), which greedily inserts a path that connects a destination to the current tree such that the incremental expected utility (IEU) of the added destination is maximized. The IEU of the new added destination is defined as its expected benefit minus corresponding expected energy cost. The MIEUDF algorithm iteratively adds the destination with the maximum IEU from the set of remaining destinations to an existing tree. The algorithm in pseudocode is presented in Algorithm 2. In Algorithm 2, IEUi denotes the IEU of destination i. The aggregated expected utility of the multicast tree is denoted as Uall. The multicast tree generated is recorded in T.Algorithm 2:MIEUDF(V,D,s,A,T).
(1)for allv∈D do(2)IEUv and s~*v assigned by UNICAST(V,s,v,A).(3)end for(4)T with only root s(5)Uall⟵0.(6)whileD≠∅ do(7)  remove the maximum IEU destinationu from D.(8)Uall←Uall+IEUu.(9)  insert the branch connectingu to T.(10)  determinept* and nt* for each sender t along the inserted(11)  branch ofT.(12)for each node v∈Ddo(13)ifs~*v shares sub-path with the inserted branch then(14)    increaseIEUvby expected power cost along the(15)    sharing sub-path.(16)end if(17)end for(18)end whileThe algorithm starts with a tree consisting of only the source nodes and Uall being zero. At the beginning, the IEU of each destination is assigned with the expected utility along the optimal path from source to itself generated by Algorithm 1. The optimal path from source s to any destination u is recorded as s~*u, and all generated optimal paths build up a tree rooted at s.At each step ofRepeat loop in the algorithm, the destination with largest IEU, say u, is removed from D and connected to the existing tree T through its optimal path, and contributes IEUu to Uall. For any relay node t along the new inserted branch of tree T, its transmission power and pre-determined number of transmitted packets, pt* and nt*, will be determined. Then, IEU of any other destination v will be increased by the expected energy cost along the inserted branch if s~*v share some sub-path with the branch, because the expected energy consumption for the sharing sub-path has been included in the newly inserted branch. During each iterative step, not only a destination is connected to the existing T, but also the corresponding optimal values of the transmission power and pre-determined number of transmitted packets of the newly added senders are determined. When D is empty, the algorithm stops and outputs a multicast tree T connecting the source to all destinations in D. Since Algorithm 2 calls Algorithm 1|D| times, its time complexity is O(|D|×|V|2).After multicast routing tree is determined,s divides the message into x packets, generates ns* encoded packets, and broadcasts the encoded packets to its downstreaming nodes along the tree using transmission power ps*. Only after receiving x linearly independent packets from its parent node, an intermediate node i in the tree begins to send ni* encoded packets to its children with transmission power level pi*.


## 7. Simulation

In this section, we give an evaluation of our proposed PCNC-based utility routing algorithms. To evaluate the performance of PCNC-based utility routing scheme (PCNC), we compare PCNC with two existing methods: power control with retransmission-based routing scheme (PCRE) and NC-based routing scheme (NC).Compared with PCNC, PCRE only allows original packets to be transmitted in a network. With PCRE, the transmission power of sender will be adjusted to the optimum power that maximizes the expected utility. For comparison purposes, the redundancy ratio in PCNC is calculated, and then this ratio will be used as the average times of retransmission for each packet at each forward node in PCRE.Compared with PCNC, each sender in NC scheme will simply adjust its transmission power to be proportional to the distance between itself and its intended receiver and will select the optimum number of encoded packets transmitted to maximize expected utility. In the following simulations, the transmission power of each sender will be adjusted tod2, where d is the corresponding distance between the sender and its intended receiver, as in [8, 9].


### 7.1. Simulation Settings

We set up the simulations in a20×20 square field, where nodes are randomly deployed. All nodes are homogeneous with the same available transmission power set LS={pmax/L,2pmax/L,…,pmax}. We set pmax=60, L=10. The path-loss exponent k and constant β/(2B-1) are set to 2 and 5, respectively.For unicast routing, we fix the position of the sources and the destination d at locations (2,2) and (18,18), respectively. Other nodes are randomly deployed. For multicast routing, we randomly deploy nodes including source s. We conduct the experiments with different numbers of nodes and different numbers of packets in a message. The experiments are conducted 50 times for each setting, and the average is used to compare the performances of the three comparable algorithms.


### 7.2. Simulations for Unicast Routing

For unicast routing, we conduct experiments with two benefit values, 3000 and 6000.We first evaluate the impact of message sizex on utility-based unicast routing schemes. In the experiments, the message size x varies from 4 to 12, with a fixed total number of nodes 30. The experimental results are shown in Figure 4. We observe that PCNC outperforms PCRE and NC with various x value under two benefit values, and both PCNC and NC achieve much more expected utility than PCRE, whose utilities are almost negative. The significant performance gap between PCNC/NC and PCRE is because that NC makes any encoded packet transmitted identically useful for recovering a message, and gives redundancy for a whole message rather than a single packet using retransmission scheme. With the same pre-determined number of transmitted packets, NC increases the message delivery reliability significantly compared with retransmission, especially with larger x. Hence, with PCRE, the initial benefit value A will be reduced rapidly to negative, going backwards from the destination to the source. Compared with NC, PCNC increases the expected utility about 17%~125% with benefit value 3000, and 8%~28% with benefit value 6000, respectively. The reason that PCNC has better performance over NC is that with TPC, each intermediate node has more alternative choices on transmission power rather than fixed to d2, and thus optimal choice can reduce power consumption and hence increase the expected utility.The comparison between three schemes (PCNC, PCRE, and  NC) with different message sizes for unicast routing, when (a)A=3000 and  (b) A=6000.
(a)(b)We then evaluate the performance of the three algorithms with different numbers of nodes from 10 to 50.x is set to 6 in these groups of simulations. The experimental results are shown in Figure 5. The expected utilities of three algorithms slightly increase as the number of nodes grows. This is because a larger number of nodes results in more routing path choices from the source to a destination, and more routing path choices may lead to better performance in terms of expected utility. We also observe that PCNC achieves the largest expected utility among the three algorithms, and PCRE attains the smallest expected utility. Compared with PCRE, PCNC and NC increase expected utility significantly under two benefit values. Compared with NC, PCNC increases the expected utility about 25%~36% with benefit value 3000, and 8%~14% with benefit value 6000, respectively.The comparison between three schemes (PCNC, PCRE, and NC) with different numbers of nodes for unicast routing, when (a)A=3000 and (b) A=6000.
(a)(b)


### 7.3. Simulation for Multicast

In this subsection, we evaluate the performance of our proposed heuristic MIEUDF for MUMRP. To evaluate the performance of MIEUDF, we also compare it with two other comparative methods, PCRE and NC. We use two benefit values 1000 and 2000 in the following experiments.We first compare the performance of PCNC with two comparable algorithms, PCRE and NC, under different message sizes. The message sizex varies from 4 to 12. In this group of experiments, we limit the total nodes number to 20, including 10 destination node. These nodes are randomly dispersed in the target field. The experimental results is shown in Figure 6. From Figure 6, we observe that with various message sizes, the performance of PCNC is better than that of PCRE and NC under two benefit values 1000 and 2000. Note that PCRE in multicast scenarios achieves much higher expected utility than in unicasting scenarios, where almost all utilities are negative. It is because that a number of destinations contribute benefits to system in multicast instead of a single destination in unicast, and that the source may be deployed near to destination(s) rather than far away in unicast. Compared with PCRE, PCNC increases the expected utility by 76%~413% with benefit value 1000 and by 52%~523% with benefit value 2000. And compared with NC, PCNC increases the expected utility by 16%~70% with benefit value 1000 and by 5%~14% with benefit value 2000.The comparison among three schemes (PCNC, PCRE, and NC) with different message sizes for multicast routing, when (a)A=1000 and (b) A=2000.
(a)(b)We also evaluate the performance of MIEUDF with different number of destinations in the target field. We set the total number of nodes to 40, and vary the number of destinations from 10 to 30. The message sizex is set to 8. Figure 7 illustrates the expected utilities of three schemes PCNC, PCRE, and NC under two benefit values 1000 and 2000. From Figure 7, we observe that PCNC achieves the expected utilities of multicast tree 3~6 times and 2~3 times greater than that of PCRE with benefit values 1000 and 2000, respectively. Additionally, compared with NC, PCNC increases the expected utilities of multicast tree by 10%~36% and by 4%~13% with benefit values 1000 and 2000, respectively.The comparison among three schemes (PCNC, PCRE, NC) with different numbers of destinations for mulitcast routing, when (a)A=1000 (b) A=2000.
(a)(b)From the above results, we conclude that the performance of our proposed heuristic MIEUDF based on PCNC is better than other two schemes, PCRE and NC. The reason is that PCNC-based heuristic not only applies NC to enhance the message delivery reliability but also selects the optimal transmission power to reduce power consumption, and hence increases the expected utility of multicast session.


## 7.1. Simulation Settings

We set up the simulations in a20×20 square field, where nodes are randomly deployed. All nodes are homogeneous with the same available transmission power set LS={pmax/L,2pmax/L,…,pmax}. We set pmax=60, L=10. The path-loss exponent k and constant β/(2B-1) are set to 2 and 5, respectively.For unicast routing, we fix the position of the sources and the destination d at locations (2,2) and (18,18), respectively. Other nodes are randomly deployed. For multicast routing, we randomly deploy nodes including source s. We conduct the experiments with different numbers of nodes and different numbers of packets in a message. The experiments are conducted 50 times for each setting, and the average is used to compare the performances of the three comparable algorithms.


## 7.2. Simulations for Unicast Routing

For unicast routing, we conduct experiments with two benefit values, 3000 and 6000.We first evaluate the impact of message sizex on utility-based unicast routing schemes. In the experiments, the message size x varies from 4 to 12, with a fixed total number of nodes 30. The experimental results are shown in Figure 4. We observe that PCNC outperforms PCRE and NC with various x value under two benefit values, and both PCNC and NC achieve much more expected utility than PCRE, whose utilities are almost negative. The significant performance gap between PCNC/NC and PCRE is because that NC makes any encoded packet transmitted identically useful for recovering a message, and gives redundancy for a whole message rather than a single packet using retransmission scheme. With the same pre-determined number of transmitted packets, NC increases the message delivery reliability significantly compared with retransmission, especially with larger x. Hence, with PCRE, the initial benefit value A will be reduced rapidly to negative, going backwards from the destination to the source. Compared with NC, PCNC increases the expected utility about 17%~125% with benefit value 3000, and 8%~28% with benefit value 6000, respectively. The reason that PCNC has better performance over NC is that with TPC, each intermediate node has more alternative choices on transmission power rather than fixed to d2, and thus optimal choice can reduce power consumption and hence increase the expected utility.The comparison between three schemes (PCNC, PCRE, and  NC) with different message sizes for unicast routing, when (a)A=3000 and  (b) A=6000.
(a)(b)We then evaluate the performance of the three algorithms with different numbers of nodes from 10 to 50.x is set to 6 in these groups of simulations. The experimental results are shown in Figure 5. The expected utilities of three algorithms slightly increase as the number of nodes grows. This is because a larger number of nodes results in more routing path choices from the source to a destination, and more routing path choices may lead to better performance in terms of expected utility. We also observe that PCNC achieves the largest expected utility among the three algorithms, and PCRE attains the smallest expected utility. Compared with PCRE, PCNC and NC increase expected utility significantly under two benefit values. Compared with NC, PCNC increases the expected utility about 25%~36% with benefit value 3000, and 8%~14% with benefit value 6000, respectively.The comparison between three schemes (PCNC, PCRE, and NC) with different numbers of nodes for unicast routing, when (a)A=3000 and (b) A=6000.
(a)(b)


## 7.3. Simulation for Multicast

In this subsection, we evaluate the performance of our proposed heuristic MIEUDF for MUMRP. To evaluate the performance of MIEUDF, we also compare it with two other comparative methods, PCRE and NC. We use two benefit values 1000 and 2000 in the following experiments.We first compare the performance of PCNC with two comparable algorithms, PCRE and NC, under different message sizes. The message sizex varies from 4 to 12. In this group of experiments, we limit the total nodes number to 20, including 10 destination node. These nodes are randomly dispersed in the target field. The experimental results is shown in Figure 6. From Figure 6, we observe that with various message sizes, the performance of PCNC is better than that of PCRE and NC under two benefit values 1000 and 2000. Note that PCRE in multicast scenarios achieves much higher expected utility than in unicasting scenarios, where almost all utilities are negative. It is because that a number of destinations contribute benefits to system in multicast instead of a single destination in unicast, and that the source may be deployed near to destination(s) rather than far away in unicast. Compared with PCRE, PCNC increases the expected utility by 76%~413% with benefit value 1000 and by 52%~523% with benefit value 2000. And compared with NC, PCNC increases the expected utility by 16%~70% with benefit value 1000 and by 5%~14% with benefit value 2000.The comparison among three schemes (PCNC, PCRE, and NC) with different message sizes for multicast routing, when (a)A=1000 and (b) A=2000.
(a)(b)We also evaluate the performance of MIEUDF with different number of destinations in the target field. We set the total number of nodes to 40, and vary the number of destinations from 10 to 30. The message sizex is set to 8. Figure 7 illustrates the expected utilities of three schemes PCNC, PCRE, and NC under two benefit values 1000 and 2000. From Figure 7, we observe that PCNC achieves the expected utilities of multicast tree 3~6 times and 2~3 times greater than that of PCRE with benefit values 1000 and 2000, respectively. Additionally, compared with NC, PCNC increases the expected utilities of multicast tree by 10%~36% and by 4%~13% with benefit values 1000 and 2000, respectively.The comparison among three schemes (PCNC, PCRE, NC) with different numbers of destinations for mulitcast routing, when (a)A=1000 (b) A=2000.
(a)(b)From the above results, we conclude that the performance of our proposed heuristic MIEUDF based on PCNC is better than other two schemes, PCRE and NC. The reason is that PCNC-based heuristic not only applies NC to enhance the message delivery reliability but also selects the optimal transmission power to reduce power consumption, and hence increases the expected utility of multicast session.


## 8. Conclusion

In this paper, we combine power control technique with network coding scheme to attain a tradeoff between energy consumption and message delivery reliability. We adopt a probability link model to reflect the relationship between transmission power and link reliability, and introduce a single metric expected utility to integrate energy consumption and reliability. Based on the expected utility metric, we propose an optimal algorithm to achieve the maximum expected utility for unicast routing, and design a heuristic for multicast routing problems, respectively. Simulation results demonstrate that our proposed scheme PCNC outperforms other two alternative schemes, PCRE and NC. In the future, we would like to extend the utility metric to analyze throughput, delay, and other performance metrics when power control technique is integrated with network coding schemes.



---

*Source: 786915-2011-05-15.xml*