Optimal Routing for Decode-and-Forward based Cooperation in Wireless
  Networks
Optimal Routing for Decode-and-Forward based Cooperation
in Wireless Networks
Lawrence Ong and Mehul Motani
Department of Electrical & Computer Engineering
National University of Singapore
Email: {lawrence.ong, motani}@nus.edu.sg
Abstract
We investigate cooperative wireless relay networks in which the nodes can help each
other in data transmission. We study different coding strategies in the single-source single-
destination network with many relay nodes. Given the myriad of ways in which nodes can
cooperate, there is a natural routing problem, i.e., determining an ordered set of nodes to
relay the data from the source to the destination. We find that for a given route, the decode-
and-forward strategy, which is an information theoretic cooperative coding strategy, achieves
rates significantly higher than that achievable by the usual multi-hop coding strategy, which
is a point-to-point non-cooperative coding strategy. We construct an algorithm to find an
optimal route (in terms of rate maximizing) for the decode-and-forward strategy. Since the
algorithm runs in factorial time in the worst case, we propose a heuristic algorithm that
runs in polynomial time. The heuristic algorithm outputs an optimal route when the nodes
transmit independent codewords. We implement these coding strategies using practical low
density parity check codes to compare the performance of the strategies on different routes.
1 Introduction
Research in high data rate wireless systems has enabled applications to go wireless and become
more interesting, e.g., wireless Internet access, mobile video conferencing and mobile TV on buses
and trains. These applications would have been impossible without high rate wireless transmission
links. As many wireless devices are battery operated, power constraint is often imposed on them
to make sure that they maintain a certain desired lifespan. In this paper, we investigate optimal
routing problem to maximize the transmission rate in the wireless network where there is a power
constraint on each node.
The wireless channel is inherently broadcast, in that messages sent out by a node are heard
by all nodes listening in the same frequency band and in communication range. This opens up
opportunities for richer forms of cooperation among the wireless users/nodes. For example, rather
than using point-to-point multi-hop routing (a direct adaptation from wired networks), where a
node only transmits to the next node in the “route”, cooperative strategies, such as information
theoretic relaying [1, 2, 3] and opportunistic routing [4], could be used. These richer forms of
cooperation can lead to efficient distributed algorithms and can increase the end-to-end data
rates. The gain from cooperation has been shown in information theoretic analyses [5][6] and
demonstrated in practical implementations [7, 8, 9].
We now briefly describe what we mean by these richer forms of cooperation, often using the
term “coding” to highlight that our approach stems from information theory [10]. Figs. 1(a)–(c)
depict wireless networks in which node 1 is the source, nodes 2 and 3 are relays, and node 4
is the destination. In Fig. 1(a), since every node can hear what node 1 transmits, the simplest
strategy is for node 4 to directly decode from node 1, which we call the single-hop coding strategy
(SH). However, when nodes 1 and 4 are situated far apart, signals from node 1 go through severe
attenuation before they reach node 4. This is when relay nodes 2 and 3 can help. Referring to
http://arxiv.org/abs/0704.0499v1
Figure 1: Different coding strategies for multiple relay channels.
Fig. 1(b), node 1 transmits to node 2. Node 2 fully decodes the data and re-transmits to node
3. Node 3 does the same and relays the data to node 4. This is the well known multi-hop coding
strategy (MH). Although we can view relay nodes helping the source to transmit data as a form of
cooperation, as far as decoding is concerned, SH and MH are still point-to-point strategies (a node
only decodes from one node) and we categorize them as non-cooperative coding strategies. Taking
a closer look at MH, we see that node 3 can hear and decode node 1’s transmission (although
it is intended for node 2). This suggests a cooperative coding strategy, depicted in Fig. 1(c), in
which node 3 decodes transmissions from nodes 1 and 2, and node 4 decodes transmissions from
nodes 1–3. This cooperative way of encoding and decoding stems from an information theoretic
approach and is termed the decode-and-forward coding strategy (DF) [1, 2, 3].
Regardless of whether MH or DF is used for data transmission, there is a sequence of nodes
through which data flows. Kurose and Ross [11] define a route as “the path taken by a datagram
between source and destination”. The datagram “hops” from one node to the next node, capturing
the scenario in which a node receives data only from a node behind and forwards data only to the
node in front. However, in the cooperative coding paradigm, data does not flow from one node to
another; rather it is from many to many with complex ways of cooperating. To describe the flow
of information in these new modes of cooperation, we define a route as follows.
Definition 1 The route taken by a packet from the source to the destination is an ordered set of
nodes involved in encoding/transmitting and receiving/decoding of the packet. The sequence of the
nodes in the route is determined by the order in which nodes’ transmit signals first depend on the
packet.
Remark 1 If a group of nodes transmits simultaneously, then they can be ordered arbitrarily
within the group. For example, consider a four node network, in which node 1 first broadcasts the
message, and then nodes 2 and 3 listen and simultaneously transmit to node 4. The route here
can be described by {1, 2, 3, 4} or {1, 3, 2, 4}.
Remark 2 Fig. 1 describes three coding strategies for the same four-node network. The route
for SH in Fig. 1a is {1, 4}. The routes for MH and DF in Figs. 1b & 1c respectively are both
{1, 2, 3, 4}.
Given the myriad of ways in which nodes can cooperate, there is a natural routing problem
in the cooperative coding paradigm. Furthermore, route selection directly affects the end-to-end
data transmission rate. For DF, the current routing solutions for MH cannot be applied trivially.
In this paper, we construct an algorithm to find an optimal route (in terms of maximizing rates)
for DF.
Our contributions in this paper are as follows.
1. We show how much gain one can expect using DF, a cooperative coding strategy, over MH,
a non-cooperative coding strategy, on the same route.
2. We construct an algorithm that finds rate maximizing routes for DF.
3. We construct a heuristic algorithm that runs in polynomial time. We show that the heuristic
algorithm finds an optimal route for DF when the nodes send independent codewords.
4. We implement DF using low-density parity-check (LDPC) codes [12][13]. Also, we show the
performance of codes using different coding strategies and on different routes.
This paper investigates cooperative coding and routing in the wireless network based on an
information theoretic approach. A few idealized assumptions are made (e.g., infinite block length,
unbounded communication range). Some of these assumptions are, however, relaxed in the simu-
lations in Section 8.
1.1 Related Work
Communications in wireless networks has been progressing from MH to that using cooperative
strategies. More research is being directed toward designing codes that are based on information
theoretic cooperative coding strategies to harvest the gain in transmission rates predicted by
information theory. Examples of codes based on cooperative coding strategies include DF-based
Turbo codes [14][15] and LDPC codes [16, 17, 18, 19] for the single relay channel. It has been
mentioned that some of these codes can be extended to the multiple relay channel [2][3][5][6].
In the past, link optimization (i.e., maximizing the transmission rate between node pairs)
and route optimization were done separately. Routing was optimized after the links between the
nodes had been established. Algorithms such as Bellman-Ford [20, Section 24.1][21] and Dijkstra’s
algorithm [22] that assign costs to all links were used to find a route with the lowest cost from
source to the destination. These ways of separating routing and coding are not optimal for MH
or DF as the rates of the links change depending on which route is chosen. Realizing the inter-
dependency between links and routes, it has been suggested that links and routes be jointly
optimized [23, 24, 25, 26]. This gives rise to cross-layering [27] in the OSI model. However, in
these joint routing and coding work, data transmission from the source to destination is still based
on MH. Routing algorithms that are optimized for MH might not be suitable for DF.
In Ad hoc On-demand Distance Vector Routing (AODV) [28] and Dynamic Source Routing
(DSR) [29], the source node broadcasts a route discovery packet. Neighboring nodes receive and
re-broadcast the packet. When the destination receives the packet, a route is formed by tracing
the path that the packet took. These routing algorithms minimize the transmission delay but
might not optimize the transmission rate.
In Extremely Opportunistic Routing (ExOR) [4], a node broadcasts its data to a set of potential
relays. Nodes in this set transmit acknowledgments and then selected nodes forward the data.
Though ExOR does not have predefined routes, MH is used on the effective route taken by a
packet.
As far as we know, routing algorithms for cooperative coding have not been investigated. In
this paper, we propose algorithms to find optimal routes for DF-based codes in the multiple relay
channel. Our work complements code design by finding the best route (rate maximizing) on
which the codes can be used. As previous work focused on cooperative coding for the single relay
channel, in this paper, we implement DF-based LDPC codes on the multiple relay channel. We
then compare the transmission rate of different coding strategies on different routes.
We focus on the multiple relay channel [2][3][5][6], which is a single-source single-destination
network, as a first step towards understanding general multiple-source multiple-destination net-
works. We study DF because it is one of the “more implementable” information theoretic coding
strategies [19, 14, 15, 16, 17, 18].
2 Motivating Cooperation
2.1 Network Model
We consider a D-node network S = {1, 2, 3 . . . , D − 1, D} with one source (node 1) and one
destination (node D). Node i, ∀i ∈ S, either transmits at fixed average power Pi or turns off.
We use the standard path loss model for signal propagation. The received power at node t from
node i is given by Pit = κd
it Pi, where dit is the distance between nodes i and t, η is the path
loss exponent (η ≥ 2 with equality for free space transmission), and κ is a positive constant. The
receiver at node t is subject to thermal ambient noise of power Nt. We assume duplex nodes, i.e.,
nodes can transmit and receive simultaneously. We assume that all nodes have the same noise
variance.
Given this network model, we investigate how nodes can cooperatively send messages from the
source to destination. We study and compare several coding strategies.
Remark 3 We consider single-flow networks. This is the first step in understanding a more
complicated problem of multiple flows. The relevance of our work in multiple-flow networks is as
follows:
1. In a multiple-flow networks where each flow uses an allocated orthogonal channel, the rate
of each flow can be optimized in respective channel using the algorithm derived in this paper.
2. In a multiple-flow network with existing flows, if we wish to add a new flow, the algorithm
in this paper finds an optimal route for the new flow. Note that adding a new flow might
affect existing flows. We can restrict the transmit power of nodes in the new flow to control
the interference introduced.
2.2 Single-Hop Coding Strategy (SH)
In SH, the source directly transmits data to the destination. The signal-to-noise ratio (SNR) at
the destination, node D, is given by γSH(D) = P1DN
. The Shannon capacity of this SH link is
RSH =
log (1 + γSH(D)) . This rate depends on the source-destination distance and can be poor
if the source and destination are situated far away from each other (because of signal attenuation).
Remark 4 We assume that nodes that do not participate in relaying the data for a source-
destination pair do not cause interference. Another way to account for the external noise is to
include it in the receiver noise.
2.3 Multi-Hop Coding Strategy (MH)
In MH, we make use of the relays to aid the transmission from the source to the destination. The
source simply transmits to the next relay. The first relay decodes the message and re-transmits
it to the second relay, and so on until the destination. This can improve the transmission rate
if the attenuation from the source/relay to the next relay is reduced as compared to that in SH.
However, since all relays transmit simultaneously, there exists interference, beside noise, at the
receiver.
In the rest of this paper, we denote a route by M = {m1,m2, . . . ,m|M|}. We define the
set of all possible routes from the source (node 1) to the destination (node D) by Π(S) =
{m1,m2, . . . ,m|M|} : m2, . . . ,m|M|−1 are all possible selections and permutations of the relays
(including the empty set), m1 = 1,m|M| = D
Using the routeM, the SNR at node mt is
γMH(mt,M) = Pmt−1mt
|M|−1
i=1,i6=t
Pmimt +Nmt
. (1)
Since all relays and the destination must fully decode the messages, the transmission rate from
the source to the destination using routeM is
RMH(M) = min
m∈M\{m1}
log (1 + γMH(m,M)) . (2)
We term RMH(M) the rate supported by the route M using MH. The maximum rate using by
MH, optimized over all possible routes, is
RmaxMH = max
M∈Π(S)
RMH(M). (3)
We note that there may exist more than one route that support this maximum rate.
2.4 Decode-and-Forward Cooperative Coding (DF)
Using DF [1, 2, 3], each decoder decodes transmissions from all nodes behind. E.g., the third node
in the route decodes the transmissions from the first and the second node. So, the third node
decodes each source message using two blocks of received codewords. In addition, assuming that
the nodes in front decode the messages correctly, a node knows what they transmit and hence it
cancels the interference from these nodes. It has been shown that in order to maximize the DF
rate on routeM, node mi transmits Xmi =
j=i+1
αmimjPmiUmj , for 0 ≤
j=i+1 αmimj ≤ 1,
∀i = 1, . . . , |M|−1. Umj are independent Gaussian random variables with unit variance. {αij |j =
i+1, . . . , |M|} are the power splits of node i, allocating portions of its transmit power to transmit
independent sub-codewords Uj . Doing this the SNR of node mt in routeM is
γDF(mt,M) = N
αmimjPmimt
. (4)
Using the routeM, DF can achieve rates up to
RDF(M) = max
m∈M\{m1}
log (1 + γDF(m,M)) , (5)
and the maximum rate using by DF is
RmaxDF = max
M∈Π(S)
RDF(M). (6)
Definition 2 We define the reception rate of node m in routeM as Rm(M) =
log (1 + γDF(m,M)) .
It is the rate at which node m can fully decode the messages. The same concept applies to MH.
Remark 5 In practice, a relay in the route might decode a message wrongly, and hence forward
the wrong message. When this happens, the nodes behind, when trying to cancel the co-channel in-
terference introduced by this relay, will introduce more noise at their decoders. While this scenario
is not captured in (4), we allow imperfect interference cancellation in our simulations (Section 8).
2.5 Comparing the Strategies
It is easy to see that, for any chosen routeM with four nodes or more, γDF(m,M) > γMH(m,M), ∀m ∈
M. Also, we can show that for anyM∈ Π(S),
RDF(M) = RMH(M) = RSH, for |M| = 2, (7a)
RDF(M) ≥ RMH(M), for |M| = 3, (7b)
RDF(M) > RMH(M), for |M| ≥ 4, (7c)
 1000
 5  10  15  20  25  30  35
No. of nodes in route, |M|
Samples taken for each |M| = 105
(1) DF rate/MH rate
(1) DF rate/SH rate
(2) DF rate/MH rate
(2) DF rate/SH rate
Figure 2: Ratio of average transmission rate SH, MH, and DF versus |M| for two cases: (1)
d1D = 10 and (2) d1D = |M| − 1.
and RmaxDF ≥ R
MH ≥ RSH.
However, it is not clear how much again, on average, we can expect using DF compared to
MH and SH. Now, we compare the rates of SH, MH, and DF for randomly generated routes of
different lengths in a line topology. We consider two cases: (1) d1D = 10 and (2) d1D = |M| − 1.
Then |M|− 2 nodes are randomly placed along the straight line joining nodes 1 and D. Note that
in case 1, node density increases with the number of nodes while in case 2, the average adjacent
node spacing is constant for all |M|. We set Pi = Ni = 1 for all transmitters and receivers, and
κ = 1, η = 2. For each randomly generated route, we calculate the transmission rate using SH, MH,
and DF. Here we restrict the nodes to transmit independent codewords for easier optimization,
i.e., we set αij = 1, ∀i, ∀j = i+ 1 and αij = 0, ∀j 6= i+ 1.
Fig 2 shows the results for cases 1 and 2. For a route of 25 nodes, the DF rate is roughly two
orders of magnitude higher than that of SH and MH for both cases. Moreover, as we increase the
number of nodes in the route, the gain of DF over MH/SH increases for both cases.
We note that if the nodes are allowed to send arbitrarily correlated codewords, the DF rate
can be higher. For example, consider the route M = {(0, 0), (0.5, 0), (2, 0), (3, 0), (4, 0)}. With
independent codewords,
RDF(M)/RMH(M) = 2.95, but with arbitrarily correlated codewords,
RDF(M)/RMH(M) = 4.40.
3 The Optimal Routing Problem
We define the optimal route set for DF as
QDF , {M ∈ Π(S) : RDF(M) = R
DF } (8)
where Π(S) is a set of all possible routes from the source to the destination. We define the optimal
route set because the rate maximizing route may not be unique. Then the optimal DF routing
problem is
Find at least oneM
DF ∈ QDF and RDF
The optimal route set and routing problem for MH are similarly defined.
Finding optimal routes for MH and DF by brute force is hard, as it involves testing all routes
in Π(S). In Sections 4 and 5, we construct an algorithm that finds M
DF, potentially without
having to test all routes in Π(S). However, this algorithm runs in factorial time in the worst case.
Hence, in Section 7, we proposed a heuristic algorithm, which runs in polynomial time.
4 The Nearest Neighbor Algorithm
Now, we present an algorithm to find an optimal route for DF. In the section, we assume that
nodes use independent codewords, i.e., we set αij = 1, ∀i, ∀j = i+ 1 and αij = 0, ∀j 6= i+ 1.
Remark 6 Although the theorems in this section are proven assuming that the nodes send in-
dependent codewords, we can also show that they hold even when the nodes transmit arbitrarily
correlated codewords [30].
Remark 7 We consider independent codewords in this section because coherent combining is
practically infeasible. When the nodes are operating in the GHz range, it is difficult, if not im-
possible, to synchronize the carriers to nanosecond accuracy. Furthermore, even if we have very
precise clocks, coherent combining is still unlikely in a multiple-node network. For example, in a
four-node route, even if we manage to synchronize nodes 1 and 2 to allow coherent combining at
node 3, we might not be able to ensure that they will coherently combine at node 4.
First, we define the nearest neighbor with respect to a route.
Definition 3 Node i /∈M is a nearest neighbor with respect to the routeM iff
Pmi ≥ Pmj , ∀m ∈ M, ∀j ∈ S \ (M∪ {i}). (9)
Note that nearest neighbor might not be unique. Now, we describe the nearest neighbor algorithm
(NNA).
Algorithm 1 (NNA)
1. Initialize M = {m1}, where m1 = 1.
2. If there exists a unique nearest neighbor i∗ with respect to the current routeM, we append
i∗ to the current route: M←M∪ {i∗}. Else, the NNA terminates prematurely. Since M
is an ordered set, the notation A ∪ B means appending ordered set B to the end of ordered
set A.
3. Step 2 is repeated until the destination node, node D, is added intoM.
The algorithm is said to terminate normally if node D is added to the route. Otherwise, the
algorithm is said to terminate prematurely. If the NNA terminates normally, we have the following
theorem.
Theorem 1 Consider a multiple node wireless network with one source and one destination. If
the NNA terminates normally, then the NNA route is optimal for DF.
To prove Theorem 1, we need the following lemmas.
Lemma 1 When we add the unique nearest neighbor, node a∗, to routeM, the rate supported by
the new route M1 =M∪ {m|M1| = a
∗} is greater or equal than the rate supported by the route
formed by adding any other node toM. Mathematically,
RDF(M∪ {a
∗}) ≥ RDF(M∪ {b}), ∀b ∈ S \ (M∪{a
∗}). (10)
Proof: [Proof for Lemma 1] ConsideringM2, the reception rate of node m|M2| = b is
Rb(M∪ {b}) =
1 +Nb
 , (11)
and the reception rate of the node m|M1| = a
∗ in routeM1 is
Ra∗(M∪ {a
∗}) =
1 +N−1a∗
Pmia∗
 . (12)
Clearly, if Pma∗ ≥ Pmb, ∀m ∈ M with at least one inequality, Ra∗(M1) > Rb(M2). Hence
RDF(M1) ≥ RDF(M2). Hence we have Lemma 1.
We have proven that at any point of time during route construction, in order to maximize the
rate supported by the route, we must choose the nearest neighbor (assuming it exists). Next, we
show that choosing the nearest neighbor will not harm the rate supported by the route even when
more nodes are added.
Lemma 2 Let M = {a∗1, a
2, . . . , a
} be a route formed by adding the nearest neighbor one by
one starting from the source. Now, arbitrarily add K nodes to M. The first node b1 is not
a nearest neighbor and the rest may or may not be nearest neighbors. In other words, M1 =
{a∗1, a
2, . . . , a
, b1, b2, . . . , bK}, where b1 is not a nearest neighbor toM. We can always replace
b1 by the nearest neighbor a
|M|+1
(assuming it exists) to obtain
{a∗1, . . . , a
|M|, a
|M|+1, b1, . . . , bK−1},
if a∗|M|+1 /∈ {b1, . . . , bK−1},
{a∗1, . . . , a
|M|+1
, b1, . . . , bk−1, bk+1, . . . , bK},
if a∗
|M|+1
= bk, for some bk ∈ {b1, . . . , bK−1},
where RDF(M2) ≥ RDF(M1).
Proof: [Proof for Lemma 2] For both cases in (13), the reception rates for the first |M| nodes
in both M1 and M2 remain the same as each of them decodes from the same nodes behind the
route. In equations,
(M2) = Ra∗
(M1), ∀i = 2, 3, . . . , |M|. (14)
From Lemma 1, Ra∗
|M|+1
(M2) > Rb1(M1).
Now, we study the case when a∗
|M|+1
/∈ {b1, . . . , bK−1}. For nodes {b1, . . . , bK−1} inM2, with
an additional node behind, i.e., a∗
|M|+1
, the reception rates of these nodes are higher than the
same nodes inM1:
Rbi(M2) > Rbi(M1), ∀i = 1, 2, . . . ,K − 1. (15)
Now, we study the case when a∗
|M|+1
= bk for some bk ∈ {b1, . . . , bK−1}. Similar to the first
case, with an additional transmitting node a∗
|M|+1
, the nodes {b1, . . . , bk−1} in M2 have higher
reception rates compared to those inM1, i.e.,
Rbi(M2) > Rbi(M1), ∀i = 1, 2, . . . , k − 1. (16)
For nodes {bk+1, . . . , bK}, there is no change in the reception rate because each of them has exactly
the same nodes behind them in bothM2 andM1. So,
Rbi(M2) = Rbi(M1), ∀i = k + 1, k + 2, . . . ,K. (17)
Lemma 2 follows by noting thatRDF(M2) = mini∈M2\{a∗1} Ri(M2) ≥ mini∈M1\{a∗1} Ri(M1) =
RDF(M1).
Lemma 3 For a route that contains all nearest neighbors, the supported rate is always higher or
equal to any route, of the same length, with one or more non-nearest neighbors in it.
Proof: [Proof for Lemma 3] Lemma 3 can be proven by applying Lemma 2 recursively until
the entire set is replaced by nearest neighbor nodes.
Now we consider routes of different lengths but that end on the same node.
Lemma 4 Consider a route M1, where node 1 is the source, and node m|M1| = D is the desti-
nation, that is
M1 = {m
1,m2, . . . ,m|M1|}. (18)
Here, one or more nodes in {m2, . . . ,m|M1|} are not nearest neighbors. The following route where
all nodes are added according to the NNA (assuming that it does not terminate prematurely)
supports rate as good or higher than that supported byM1.
M2 = {m
2, . . . ,m
}, (19)
where m∗|M2| = D and |M1| not necessarily equals |M2|. In other words, RDF(M2) ≥ RDF(M1).
Proof: [Proof for Lemma 4] First of all, we consider the case |M1| = |M2|. The results follows
immediately from Lemma 3. Second, we consider |M1| > |M2|. We consider first |M2| nodes in
M1, i.e.,M
1 = {m
1,m2, . . . ,m|M2|}. Then,
RDF(M2) ≥ RDF(M
1) ≥ RDF(M1). (20)
The first inequality is obtained by applying Lemma 3. M2 andM
1 are of the same length. The
former is formed using the NNA while the latter is not. The second inequality can be argued as
follows. The first |M2| nodes in both routesM
1 andM1 are identical. Hence the reception rates
are the same. However, there are additional nodes in M1 whose reception rate might be lower
than RDF(M
1). Hence, the rate supported byM
1 can only be higher than that ofM1.
Lastly, consider |M2| > |M1|. We replace the transmitting nodes inM1 with nearest neighbors
and obtain
M3 = {m
2, . . . ,m
|M1|−1
,m|M1| = D}. (21)
Note that m|M1| might not be the nearest neighbor. Clearly, using Lemma 2, RDF(M3) ≥
RDF(M1). Now,
RDF(M2)
= min{Rm∗
(M2), . . . , Rm∗
|M1|−1
(M2), Rm∗
(M2),
. . . , Rm∗
|M2|−1
(M2), Rm∗
(M2) = RD(M2)}, (22a)
≥ min{Rm∗
(M3), . . . , Rm∗
|M1|−1
(M3), RD(M3)}, (22b)
= RDF(M3) ≥ RDF(M1). (22c)
The inequality in (22b) is because inM2, {m
, . . . ,m∗
|M2|−1
} are added to {m∗1, . . . ,m
|M1|−1
before D. A necessary condition for this is
Pmn ≥ PmD, ∀m ∈ {m
1, . . . ,m
|M1|−1
∀n ∈ {m∗|M1|, . . . ,m
|M2|−1
}, (23)
with at least one strict inequality for each n. Hence, Rn(M2) > RD(M3), ∀n ∈ {m
, . . . ,m∗
|M2|−1
With additional nodes transmitting to D inM2, RD(M2) > RD(M3). Hence, we have Lemma 4.
Proof: [Proof for Theorem 1] From Lemma 4, we know that if the NNA terminates normally,
the route (from the source to the destination) formed using the NNA can support transmission
rates as high as any other route. In other words, the NNA finds a route that supports the highest
rate achievable by DF. Theorem 1 follows.
Remark 8 We note the NNA terminates normally if and only if a unique nearest neighbor exists
at each step. In the next section, we extend the NNA to an algorithm which terminates normally
given any network topology.
5 The Nearest Neighbor Set Algorithm
In this section, we modify the NNA so that it terminates normally in any multiple node wireless
network with a single source and a single destination. We term this algorithm the nearest neighbor
set algorithm (NNSA). First, we define the nearest neighbor set.
Definition 4 The nearest neighbor set N = {n1, n2, . . . , n|N |} with respect to routeM = {m1,m2,
. . . ,m|M|} is defined as the smallest set N where each n ∈ N ⊆ S \ M satisfies the following
condition.
Pmn ≥ Pma, ∀m ∈M, ∀a ∈ S \ (M∪N ), (24)
with at least one strict inequality for every pair of (n, a) ∈ {(n, a) : n ∈ N , a ∈ S \ (M∪N )}.
Now we describe the NNSA.
Algorithm 2 (NNSA)
1. Starting with the source node, we have M = {1}.
2. Find the nearest neighbor set N . The original route M branches out to |N | new routes as
follows:
Mi ←M∪ {ni}, i = 1, . . . , |N |. (25)
3. For each new route in (25), step 2 is repeated until the destination is added to all routes.
When the algorithm terminates, we end up with many routes from the source to the destination.
We term these routes NNSA candidates. We calculate the supported rate of each candidate and
choose the one which gives the highest supported rate. The following theorem says that any NNSA
candidate that gives the highest supported rate is an optimal route for DF.
Theorem 2 Consider a single-source single-destination multiple node wireless network. The
NNSA candidate routes that give the highest supported rate are optimal for DF.
Proof: [Sketch of proof for Theorem 2] Using the technique used in the proof of Theorem 1,
we can show that adding a node that does not belong to the nearest neighbor set can only
be suboptimal. We can always replace that node with one from the nearest neighbor set and
obtain an equal or higher rate. In other words, we can show that the supported rate of M1 =
{1,m2, . . . ,m|M1|−1, D}, with one or more nodes in {m2, . . . ,m|M1|} not from the nearest neighbor
set, is lower or equal to the supported rate ofM2 = {1,m
2, . . . ,m
|M2|−1
, D}, where all nodes in
M2 are added according to the NNSA. In other words, RDF(M2) ≥ RDF(M1).
The NNSA finds all possible routes for which every node is added from the nearest neighbor
set. Hence one or more of the NNSA candidates must achieve the highest rate achievable by DF.
This gives us Theorem 2.
Remark 9 We can show that a shortest optimal route, defined as some MSOR
∈ QDF, s.t.
|MSOR
| ≤ |M|, ∀M ∈ QDF, is contained in one of the NNSA candidates that supports R
Remark 10 The NNSA might output optimal routes that include more nodes from the network
unnecessarily. In other words, shorter optimal routes exist. However, from Remark 9, we can find
the shortest optimal route by pruning the optimal routes output by the NNSA.
6 Complexity of NNSA
With the NNSA, we can now search for the optimal route in the NNSA candidate set, as compared
to searching in Π(S) using brute force. The number of candidates determines the number of routes
whose rate we need to calculate to find optimal routes for DF. We note that the size of the NNSA
candidate set might still, in the worst case, equal |Π(S)|. Using brute force, the number of
permutations we need to check is |Π(S)| = 1 +
+ · · ·
= O((D − 1)!), where
D is the total number of nodes in the network and
n×(n−1)×···×1
(n−k)×(n−k−1)×···×1
We ran the NNSA on 10000 randomly generated networks with a varying number of nodes
uniformly distributed in a 1m×1m square area. The source, relays and destination were randomly
assigned. On average, half of the NNSA candidate set sizes were less than 0.715% of the size of
Π(S) for the 8-node channel and less than 0.253% for the 11-node channel.
We note that the average size of the NNSA candidate set does grow factorially with the number
of nodes. However this does increase the range of finite size networks for which we can find optimal
routes. Furthermore, the NNSA provides insights for designing heuristic algorithms to find good
routes for DF based codes. In the next section, we propose heuristic algorithms which find routes
in polynomial time.
Remark 11 The NNSA builds routes from the source. Relays are added to the route regardless
of where the destination is. We will use this observation in designing heuristic algorithms.
7 Heuristic Algorithms
In the NNSA, the optimal route is constructed by adding the “next hop” node one by one to the
partial route. The node to be added is from the nearest neighbor set. If the nearest neighbor set
contains more than one node, the current route branches to more than one route, leading to a
possibly large NNSA candidate set size.
To avoid this, we consider a heuristic approach that starts from the source node and repeatedly
adds only one “good” candidate from the nearest neighbor set until the destination is reached. For
the choice of the next hop node, we consider the node which receives the largest sum of received
power from all the node in the existing route. We call this the maximum sum-of-received-power
algorithm (MSPA). By choosing only one node to be added to the partial route, we prevent the
algorithm from branching out to multiple routes. This heuristic approach yields only one route,
regardless of the network size. We now explicitly describe the MSPA.
Algorithm 3 (MSPA)
1. Start with the source node: M = {1}.
2. For every node t ∈ S\M, find the sum of received power from all nodes inM to t,
i∈M Pit.
3. Let a∗ be any node with the highest sum of received power, i.e.,
i∈M Pia∗ ≥
j∈M Pjt, ∀t ∈
S \M. Append node a∗ to the route: M←M∪ {a∗}.
4. Repeat steps 2–3 until the destination is added to the route.
Remark 12 Assuming that the value of the previous sum-of-received-power computations are
cached, the complexity of step 2 in MSPA is O(D) because there are at most (D − 1) nodes
not in the route. The complexity of the comparisons in step 3 is O(D). Steps 2–3 are repeated at
most (D − 1) times, giving a worst case complexity of the MSPA of O(D2). Recall that D = |S|.
It turns out that the MSPA is optimal if the nodes are restricted to sending independent
codewords, as proven in the following theorem.
Theorem 3 In a single-source single-destination multiple node wireless network in which the
nodes send independent codewords, the MSPA route is optimal for DF.
Proof: [Proof for Theorem 3] Consider an optimal route
M1 = {m
2, . . . ,m
k+1, . . . ,m
}. Suppose that the first k nodes of the MSPA route
are the same as this optimal route but the (k + 1)-th node is different, i.e., the MSPA route is
M2 = {m
2, . . . ,m
, a, . . . } where a 6= m∗
Since a is added to the route by MSPA, a necessary condition is
i=1 Pm∗i a ≥
j=1 Pm∗jm
. So,
Ra(M2) ≥ Rm∗
(M1). (26)
Now, consider the case where a 6= m∗i , ∀i = k + 2, . . . , |M|. We add a to M1 and obtain
M3 = {m
2, . . . ,m
, a,m∗
k+1, . . . ,m
}. Then,
(M3) = Rm∗
(M1), i = 2, . . . , k (27a)
Ra(M3) ≥ Rm∗
(M1) (27b)
(M3) > Rm∗
(M1), i = k + 1, . . . , |M|. (27c)
So, RDF(M3) ≥ RDF(M1).
Suppose a = m∗n, for some n ∈ {k + 2, . . . , |M|}. We swap the position of a and obtain
M4 = {m
2, . . . ,m
, a,m∗
k+1, . . . ,m
n−1,m
n+1,m
}. Then,
(M4) = Rm∗
(M1), i = 2, . . . , k, n+ 1, . . . , |M| (28a)
Ra(M4) ≥ Rm∗
(M1) (28b)
(M4) > Rm∗
(M1), i = k + 1, . . . , n− 1. (28c)
So, RDF(M4) ≥ RDF(M1).
In summary, we choose an optimal route. Starting from the second node, we compare the
optimal route with the MSPA route. If the nodes are different, we insert (or swap, if the node is in
the optimal route but at a different position) the node in the MSPA route to the optimal route to
obtain a new optimal route. Repeat this by comparing the new optimal route to the MSPA route
and changing the first node that differ until the MSPA is contained in an optimal route. Then,
we have Theorem 3.
Remark 13 However, unlike the NNA and the NNSA, the MSPA does not output an optimal
route when the nodes are allowed to send arbitrarily correlated codewords. Consider a four-node
network with node coordinates 1(0,0), 2(0.418,0), 3(0.209,0.6755), and 4(0.995,0). Assume Pi =
1, Ni = 1, κ = 1, η = 2. The MSPA route is M1 = {1, 2, 4}. The NNSA outputs M1 and
M2 = {1, 2, 3, 4}. It is easy to compute that RDF(M1) = 1.30826 and RDF(M2) = 1.31576.
8 DF with LDPC Codes
In the previous section, we computed achievable rates of different strategies and routes based on
an information theoretic approach. In this section, we compare the different strategies and routes
in a line network using practical low density parity check (LDPC) codes [12][13] with incremental
redundancy. The aims of this section are:
1. To illustrate that DF on the multiple relay channel is implementable.
2. To demonstrate that DF performs better than MH under certain network topologies.
3. To show that routing backward (away from the destination) can be good in DF.
4. To demonstrate that the NNSA route performs better than other routes using DF.
Figure 3: Network topology.
 1e-05
 1e-04
 0.001
 0.01
 0  1  2  3  4  5  6  7  8
Eb/N0 (dB)
LDPC in 4-node network. 1(0,0.5) 2(0,0.4) 3(0,1) 4(0,1.5)
DF M=1234
DF M=134
DF M=1324
DF M=124
SH M=14
MH M=1234
MH M=134
Figure 4: Performance (information bit error rate (BER) versus transmit SNR) of different strate-
gies on different routes in a 4-node network.
From Fig. 4, we see that for a given route, DF performs better than MH. An interesting
observation is that routing backward helps in DF but not MH. We find that the NNSA route
(which is also the MSPA route), i.e., {1, 2, 3, 4}, achieves the lowest BER compared to other
routes using DF.
Remark 14 We note that the total transmit energy differs depending on the length of the route.
One might argue that route {1, 4}, though having a higher BER, is better as only 1/3 power is
consumed compared to route {1, 2, 3, 4}. However, we stress that this paper finds a route that max-
imizes the transmission rate, given that each node must transmit within a given power constraint.
Whether or not the node transmits, it is not important in the route comparison.
Remark 15 We plotted BER versus SNR in Fig. 4. If the maximum raw channel data rate
(in bps) is Ψmax, then the throughput is Ψ = (1 − PER) · Ψmax, where PER is the packet error
rate and depends on the BER and the packet size. In simulations, we found that packet error rate
(PER) had the same behavior as BER.
9 Concluding Remarks
We first showed that DF gives a significant transmission rate gain over MH, for an arbitrary
route in the wireless network. We presented an algorithm, the nearest neighbor set algorithm
(NNSA), to find optimal routes, which maximize the rates achievable by DF. As this algorithm,
in the worst case, runs in factorial time, we designed a heuristic algorithm, the maximum sum-
of-received-power algorithm (MSPA), that runs in polynomial time. We showed that the MSPA
finds an optimal route when the nodes can only send independent codewords. However, unlike
the NNA and the NNSA, the MSPA does not find an optimal route when the nodes are allowed
to send arbitrarily correlated codewords. We implemented DF on practical networks using LDPC
codes with incremental redundancy to compare different routes.
We would like to highlight that for a given route, the choice of coding strategies, be it MH or
DF, does not affect the spatial re-use of the system. In both strategies, the nodes in the route
(except the destination) transmit at the same power level. The difference lies in how the nodes
decode the data.
We also note that there are some practical problems in implementing DF in large networks.
First, since real-world systems have finite transmit power constraints, nodes have a finite commu-
nication range, beyond which they cannot be heard. Second, large networks may be distributed
over a wide area and cooperation over large distances may not be feasible. The solution is to
partition the network into clusters and perform cooperative coding locally in the cluster, e.g., local
DF, in which only nodes in a cluster cooperate with each other.
References
[1] T. M. Cover and A. A. El-Gamal, “Capacity theorems for the relay channel,” IEEE Trans.
Inform. Theory, vol. IT-25, no. 5, pp. 572–584, Sept. 1979.
[2] L. Xie and P. R. Kumar, “An achievable rate for the multiple level relay channel,” IEEE
Trans. Inform. Theory, vol. 51, no. 4, pp. 1348–1358, Apr. 2005.
[3] G. Kramer, M. Gastpar, and P. Gupta, “Cooperative strategies and capacity theorems for
relay networks,” IEEE Trans. Inform. Theory, vol. 51, no. 9, pp. 3037–3063, Sept. 2005.
[4] S. Biswas and R. Morris, “Opportunistic routing in multi-hop wireless networks.” Computer
Communication Review, vol. 34, no. 1, pp. 69–74, 2004.
[5] L. Ong and M. Motani, “Myopic coding in wireless networks,” Proceedings of the 39th Confer-
ence on Information Sciences and Systems (CISS 2005), John Hopkins University, Baltimore,
MD, Mar. 16–18 2005.
[6] ——, “Myopic coding in multiple relay channels,” 2005 IEEE International Symposium on
Information Theory (ISIT 2005), Adelaide Convention Centre, Adelaide, Australia, Sept. 4–9
2005.
[7] A. Sendonaris, E. Erkip, and B. Aazhang, “User cooperation diversity–part i: System de-
scription,” IEEE Trans. Comms., vol. 51, no. 11, pp. 1927–1938, Nov. 2003.
[8] ——, “User cooperation diversity–part ii: Implementation aspects and perfomance analysis,”
IEEE Trans. Inform. Theory, vol. 51, no. 11, pp. 1939–1948, Nov. 2003.
[9] T. L. Lim, V. Srivastava, and M. Motani, “Selective cooperation based on link distance esti-
mations in wireless ad-hoc networks,” The 2006 IEEE International Symposium on a World of
Wireless, Mobile and Multimedia Networks (WOWMOM 2006), Niagara-Falls, Buffalo-NY,
June 26–29 2006.
[10] T. M. Cover and J. A. Thomas, Elements of Information Theory. John Wiley and Sons,
1991.
[11] J. F. Kurose and K. W. Ross, Computer Networking: A Top-Down Approach Featuring the
Intnernet. Pearson Education, 2003.
[12] R. G. Gallager, “Low density parity check codes,” IRE Trans. Inform. Theory, vol. IT-8, pp.
21–28, Jan. 1962.
[13] D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans.
Inform. Theory, vol. 45, no. 2, pp. 399–430, Mar. 1999.
[14] B. Zhao and M. C. Valenti, “Distributed turbo coded diversity for relay channel,” Electronics
Letters, vol. 39, no. 10, pp. 786–787, May 2003.
[15] Z. Zhang, I. Bahceci, and T. M. Duman, “Capacity approaching codes for relay channels,”
2004 IEEE International Symposium on Information Theory (ISIT), Chicago, USA,, June
27–July 2 2004.
[16] M. A. Khojastepour, N. Ahmed, and B. Aazhang, “Code design for the relay channel and
factor graph decoding,” Thirty-Eight Annual Confrernce on Signal, Systems, and Computers,
Asilomar, Pacific Grove, California, Nov. 7–10 2004.
[17] A. Chakrabarti, A. De-Baynast, A. Sabharwal, and B. Aazhang, “Low density parity check
codes for the relay channel,” under revision for IEEE JSAC special issue, 2006.
[18] J. Ezri and M. Gastpar, “On the performance of independently designed ldpc codes for the
relay channel,” 2006 IEEE International Symposium on Information Theory (ISIT 2006),
The Westin Seattle, Seattle, Washington, July 9–14 2006.
[19] P. Razaghi and W. Yu, “Bilayer ldpc codes for the relay channel,” IEEE International Con-
ference on Communications (ICC), Istanbul, Turkey (2006), 2006.
[20] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT
Press and McGraw-Hill, 2001.
[21] B. L. Su, Y. M. Huang, and F. Lee, “Distributed location-aware transmission for ad hoc
networks,” 17th APAN Meetings and Joint Techs Workshop, Honolulu, USA, Jan. 2004.
[22] E. W. Dijkstra, “A note on two problems in connection with graphs,” Numerische Math,
vol. 1, pp. 269–271, 1959.
[23] R. L. Cruz and A. V. Santhanam, “Optimal routing, link scheduling and power control
in multihop wireless networks,” 22nd Annual Joint Conference of the IEEE Computer and
Communications Societies (INFOCOM), vol. 1, pp. 702–711, Mar. 30 – Apr. 3 2003.
[24] Y. Li and A. Ephremides, “Joint scheduling, power control, and routing algorithm for ad-
hoc wireless networks,” 38th Annual Hawaii International Conference on System Sciences
(HICSS), Jan 3–6 2005.
[25] G. Lu and B. Krishnamachari, “Energy efficient joint scheduling and power control for wireless
sensor networks,” Sensor and Ad Hoc Communications and Networks (IEEE SECON), pp.
362–373, Sept 26–29 2005.
[26] J. H. Zhang, H. T. Wu, Q. Zhang, and B. Li, “Joint routing and scheduling in multi-radio
multi-channel multi-hop wireless networks,” 2nd International Conference on Broadband Net-
works, vol. 1, pp. 631–640, Oct. 3–7 2005.
[27] V. Srivastava and M. Motani, “Cross-layer design: a survey and the road ahead,” IEEE
Communications Magazine, pp. 112–119, Oct 2005.
[28] C. Perkins, “Ad hoc on demand distance vector (aodv) routing,” IETF, Internet Draft, draft-
ietf-manet-aodv-00.txt, Nov. 1997.
[29] D. B. Johnson and D. Maltz, “Dynamic source routing in ad hoc wireless networks,” in Mobile
Computing. Kluwer Academic Publishers, 1996, vol. 353.
[30] L. Ong and M. Motani, “Optimal routing for the decode-and-forward strategy in the gaus-
sian multiple relay channel,” accepted and to be presented at the 2007 IEEE International
Symposium on Information Theory (ISIT 2007), Acropolis Congress and Exhibition Center,
Nice, France.
	Introduction
	Related Work
	Motivating Cooperation
	Network Model
	Single-Hop Coding Strategy (SH)
	Multi-Hop Coding Strategy (MH)
	Decode-and-Forward Cooperative Coding (DF)
	Comparing the Strategies
	The Optimal Routing Problem
	The Nearest Neighbor Algorithm
	The Nearest Neighbor Set Algorithm
	Complexity of NNSA
	Heuristic Algorithms
	DF with LDPC Codes
	Concluding Remarks
