Dept.

of Electrical and Computer Engineering, and

Coordinated Science Lab
University of Illinois, Urbana-Champaign
Wireless Network Information Theory
L-L. Xie and P. R. Kumar
Email prkumar@uiuc.edu
Web http://black.csl.uiuc.edu/~prkumar
DIMACS Workshop on Network Information Theory,
March 17-19, 2003
Wireless Networks
u Communication networks formed by nodes with radios
u Ad Hoc Networks
Current proposal for operation: Multi-hop transport
Nodes relay packets until they reach their destinations
They should be spontaneously deployable
anywhere
On a campus
On a network of automobiles on roads
On a search and rescue mission
They should be able to adapt themselves to
the number of nodes in the network
the locations of the nodes
the mobility of the nodes
the traffic requirements of the nodes
u Sensor webs
Current proposal for ad hoc networks
u Multi-hop transport
Packets are relayed from node to node
A packet is fully decoded at each hop
All interference from all other nodes
is simply treated as noise
u Properties
Simple receivers
Simple multi-hop packet relaying scheme
Simple abstraction of wires in space
u This choice for the mode of operation
gives rise to
Routing problem
Media access control problem
Power control problem
..
Interference
+
Noise
Interference
+
Noise
Interference
+
Noise
Interferenc
e
+
Noise
Three fundamental questions
u If all interference is treated as noise, then how much information
can be transported over wireless networks?
u What is unconditionally the best mode of operation?
u What are the fundamental limits to information transfer?
u Allows us to answer questions such as
How far is current technology from the optimal?
When can we quit trying to do better?
E.g.. If Telephone modems are near the Shannon capacity then we can stop
trying to build better telephone modems
What can wireless network designers hope to provide?
What protocols should be designed?
If interference is treated as noise ...
If all interference is regarded as
noise
u then packets can collide destructively
u A Model for Collisions
Reception is successful if Receiver
not in vicinity of two transmissions
u Alternative Models
SINR b for successful reception
Or Rate depends on SINR
or
r
2
r
1
(1+D) r
1
(1+D)r
2
u Theorem (GK 2000)
Disk of area A square meters
in nodes
Each can transmit at W bits/sec
u Best Case: Network can transport
u Square root law
Transport capacity doesnt increase linearly, but only like square-root
Each node gets bit-meters/second
u Random case: Each node can obtain throughput of
Scaling laws under interference model

Q W An
( )
bit-meters/second

Q
1
nlogn








bits/second
A square meters
n nodes
c
n
Optimal operation under collision
model
u Optimal operation is multi-hop
Transport packets over many
hops of distance
u Optimal architecture
Group nodes into cells of size about log n
Choose a common power level for all nodes
Nearly optimal
Power should be just enough to guarantee network connectivity
Sufficient to reach all points in neighboring cell
Route packets along nearly straight line path from cell to cell

c
n

1
n
0
Range
Bit-Meters
Per Second
Per Node

c
n
Broadcast
No
connectivity
Multi-hop
Networks
But interference is not interference
u Excessive interference can be good for you
Receiver can first decode loud signal perfectly
Then subtract loud signal
Then decode soft signal perfectly
So excessive interference can be good
u Packets do not destructively collide
u Interference is information!
u So we need an information theory for networks to determine
How to operate wireless networks
How much information wireless networks can transport
The information theory should be able to handle general wireless
networks
Towards fundamental limits in
wireless networks
Wireless networks dont come with
links
u They are formed by nodes with
radios
There is no a priori notion of links
Nodes simply radiate energy
Nodes can cooperate in complex ways
Nodes in Group A
cancel
interference of
Group B at
Group C
A
B
C
X
while Nodes in
Group D amplify and
forward packets
from Group E to
Group F
D
E
F
Signal
One strategy: Increase Signal for Receiver
Instead, why not: Reduce Interference at Receiver
Interference + Noise
SINR = One strategy: Decode and forward
Instead, why not: Amplify and Forward
while
.

u Some obvious choices

Should nodes relay packets?
Should they amplify and forward?
Or should they decode and forward?
Should they cancel interference for other nodes?
Or should they boost each others signals?
Should nodes simultaneously broadcast to a group of nodes?
Should those nodes then cooperatively broadcast to others?
What power should they use for any operation?

u Or should they use much more sophisticated unthought of strategies?
Tactics such as may be too simplistic
Cooperation through does not capture all possible modes of operation
How should nodes cooperate?
Broadcast
Multiple-access
Relaying
...
Decode and forward
Amplify and Forward
Interference cancellation
...
There are more things in heaven and earth, Horatio,
Than are dreamt of in your philosophy.
Hamlet
u The strategy space is infinite dimensional
u Problem has all the complexities of
team theory
partially observed systems
u We want Information Theory to tell us what the basic strategy should be
Then one can develop protocols to realize the strategy
A plethora of choices
Key Results: A dichotomy
u If absorption in medium
Transport capacity grows like Q(n)
when nodes are separated by
distance at least r
min
Square-root law is optimal
i
Since area A grows like W(n)
Multi-hop decode and forward is
order optimal
u Along the way
Total power used by a network bounds the transport capacity
Or not
A feasible rate for Gaussian multiple relay channels
Q An ( ) = Q n ( )
u If there is no absorption, and
attenuation is very small
Transport capacity can grow
superlinearly like Q(n
q
) for q > 1
Coherent multi-stage relaying with
interference cancellation can be
optimal
A quick review of information theory
and networks
Shannons Information Theory
u Shannons Capacity Theorem
Channel Model p(y|x)
Discrete Memoryless Channel
Capacity = Max
p(x)
I(X;Y) bits/channel use
u Additive White Gaussian Noise (AWGN) Channel
Capacity =
Channel
p(y|x)
x y
x y
N(0, s
2
)
Ex
2
P
S
P
s
2




, where S(z) =
1
2
log 1+ z ( )
I( X;Y) = p(x, y)
x, y
log
p(X, Y)
p(X) p(Y)






Shannons architecture for
communication
Channel Decode
Source decode
(Decompression)
Encode
for the
channel
Source code
(Compression)
Network information theory:
Some triumphs
u Gaussian scalar broadcast channel
u Multiple access channel
u The simplest relay channel
u The simplest interference channel
Network information theory:
The unknowns
u Systems being built are much more complicated and the possible modes
of cooperation can be much more sophisticated
How to analyze?
Need a general purpose information theory
The Model
Model of system: A planar network
u n nodes in a plane
u r
ij
= distance between nodes i and j
u Minimum distance r
min
between nodes
u Signal attenuation with distance r:
ig 0 is the absorption constant
Generally g > 0 since the medium is absorptive unless over a vacuum
Corresponds to a loss of 20g log
10
e db per meter
d > 0 is the path loss exponent
d =1 corresponds to inverse square law in free space
r
ij
r
min
i
j

e
-gr
r
d


W
i
= g
j
(y
j
T
,W
j
)
u W
i
= symbol from some alphabet to be sent by node i
u x
i
(t) = signal transmitted by node i time t
u y
j
(t) = signal received by node j at time t
u Destination j uses the decoder
u Error if
u (
u Individual power constraint P
i
P
ind
for all nodes i
Or Total power constraint
Transmitted and received signals
N(0,s
2
)

= f
i ,t
(y
i
t-1
,W
i
)


{1,2, 3,K,2
TR
ik
}

=
e
-gr
ij
r
ij
d
i =1
i j
n

x
i
(t) + z
j
(t)
P
i
i =1
n
P
total


W
i
W
i

(R
1
, R
2
,..., R
l
) is feasible rate vector if there is a sequence of codes with

Max
W
1
,W
2
,...,W
l
Pr(

W
i
W
i
for some i W
1
,W
2
,...,W
l
) 0 as T
x
i
y
j
The Transport Capacity: Definition
u Source-Destination pairs
(s
1
, d
1
), (s
2
, d
2
), (s
3
, d
3
), , (s
n(n-1)
, d
n(n-1)
)
u Distances
L r
1
, r
2
, r
3
, , r
n(n-1)
distances between the sources and destinations
u Feasible Rates
(R
1
, R
2
, R
3
, , R
n(n-1)
) feasible rate vector for these source-destination
pairs
u Distance-weighted sum of rates
S S
i
R
i
r
i
u Transport Capacity


C
T
= sup
( R
1
,R
2
,K,R
n(n-1)
)
R
i
i=1
n(n-1)

r
i
bit-meters/second or bit-meters/slot
The Transport Capacity
u C
T
= sup S
i
R
i
r
i
Measured in bit-meters/second or bit-meters/slot
Analogous to man-miles/year considered by airlines
Upper bound to what network can carry
Irrespective of what nodes are sources or destinations, and their rates
Satisfies a scaling law
Conservation law which restricts what network can provide
Irrespective of whether it is of prima facie interest
However it is of natural interest
Allows us to compare apples with apples
= (R, R, 0) or = (0, 0, R)
1 2 3
R R
1 3
R
The Results
When there is absorption or
relatively large path loss
The total power bounds the transport
capacity
u Theorem (XK 2002): Joules per bit-meter bound
Suppose g > 0, there is some absorption,
Or d > 3, if there is no absorption at all
Then for all Planar Networks
where
C
T

c
1
(g ,d, r
min
)
s
2
P
total
c
1
(g ,d, r
min
) =
2
2d +7
g
2
r
min
2d+1
e
-gr
min
2
(2 - e
-gr
min
2
)
(1-e
-gr
min
2
)
if g > 0
=
2
2d+5
(3d - 8)
(d - 2)
2
(d - 3)r
min
2d-1
if g = 0 and d > 3
Idea behind proof
u A Max-flow Min-cut Lemma
N = subset of nodes

Then
R
l
{l:d
l
N but s
l
N}

1
2s
2
liminf
T
P
N
rec
(T)
P
N
rec
(T) = Power received by nodes in N from outside N
=
1
T
E
x
i
(t)
r
ij
d
iN

jN

t =1
T

2
P
rec
(T)
N
R
1
R
2
R
3
N
To obtain power bound on transport
capacity
u Idea of proof
u Consider a number of cuts
one meter apart
u Every source-destination
pair (s
l
,d
l
) with source at
a distance r
l
is cut by about
r
l
cuts
u Thus
r
l

R
l
r
l
l

c R
l
{l is cut by N
k
}

N
k

c
2s
2
liminf
T
P
N
k
rec
(T)
cP
total
s
2
N
k

O(n) upper bound on Transport

Capacity
u Theorem
Suppose g > 0, there is some absorption,
Or d > 3, if there is no absorption at all
Then for all Planar Networks
where
C
T

c
1
(g ,d, r
min
)P
ind
s
2
n
c
1
(g ,d, r
min
) =
2
2d +7
g
2
r
min
2d+1
e
-gr
min
2
(2 - e
-gr
min
2
)
(1-e
-gr
min
2
)
if g > 0
=
2
2d+5
(3d - 8)
(d - 2)
2
(d - 3)r
min
2d-1
if g = 0 and d > 3
Feasibility of a rate vector
u Theorem
A set of rates (R
1
, R
2
, , R
l
) can be
supported by multi-hop transport if
Traffic can be routed, possibly over
many paths, such that
No node has to relay more than
where is the longest distance of a hop
and
r
S
e
-2gr
P
ind
r
2d
c
3
(g ,d, r
min
)P
ind
+s
2








c
3
(g ,d, r
min
) =
2
3+2d
e
-gr
min
gr
min
1+2d
if g > 0
=
2
2+2d
r
min
2d
(d -1)
if g = 0 and d > 1
Multihop transport can achieve Q(n)
u Theorem
Suppose g > 0, there is some absorption,
Or d > 1, if there is no absorption at all
Then in a regular planar network
where
C
T
S
e
-2g
P
ind
c
2
(g ,d )P
ind
+s
2








n
c
2
(g ,d) =
4(1+4g )e
-2g
-4e
-4g
2g (1-e
-2g
)
if g > 0
=
16d
2
+(2p -16)d -p
(d -1)(2d -1)
if g = 0 and d >1
n sources each sending
over a distance n
Optimality of multi-hop transport
u Corollary
So if g > 0 or d > 3
And multi-hop achieves Q(n)
Then it is optimal with respect to the transport capacity
up to order
u Example
Multi-hop is almost optimal in a
random network
u Theorem
Consider a regular planar network
Suppose each node randomly chooses a destination
Choose a node nearest to a random point in the square
Suppose g > 0 or d > 1
Then multihop can provide bits/time-unit for every
source with probability 1 as the number of nodes n
u Corollary
Nearly optimal since transport capacity achieved is
W
1
nlog n








W
n
log n








Idea of proof for random source -
destination pairs
u Simpler than GK since
cells are square and contain
one node each
u A cell has to relay traffic if a random
straight line passes through it
u How many random straight lines
pass through cell?
u Use Vapnik-Chervonenkis theory
to guarantee that no cell is overloaded
What happens when the attenuation
is very low?
u Coherent multi-stage relaying with interference cancellation
(CRIC)
u All upstream nodes coherently cooperate to send a packet to
the next node
u A node cancels all the interference caused by all transmissions
to its downstream nodes
Another strategy emerges as of
interest ...
k k-1 k-2 k+1
u Coherent multi-stage relaying with interference cancellation
(CRIC)
u All upstream nodes coherently cooperate to send a packet to
the next node
u A node cancels all the interference caused by all transmissions
to its downstream nodes
Decoding
k-1 k-2 k-3 k
k k-1 k-2 k+1
u Coherent multi-stage relaying with interference cancellation
(COMSRIC)
u All upstream nodes coherently cooperate to send a packet to
the next node
u A node cancels all the interference caused by all transmissions
to its downstream nodes
Interference cancellation
k
k k+1
A feasible rate for the Gaussian
multiple-relay channel
u Theorem
Suppose a
ij
= attenuation from i to j
Choose power P
ik
= power used
by i intended directly for node k
where
Then
is feasible
a
ij
i
j
P
ik
i k
R < min
1 j n
S
1
s
2
a
ij
P
ik
i =0
k-1

2
k=1
j

P
ik
k =i
M
P
i
A group relaying version
u Theorem
A feasible rate for group relaying
R <
R < min
1 j M
S
1
s
2
a
N
i
N
j
P
ik
/ n
i
n
i
i =0
k -1

2
k =1
j

n
i
Unbounded transport capacity can
be obtained for fixed total power
u Theorem
Suppose g = 0, there is no absorption at all,
And d < 3/2
Then C
T
can be unbounded in regular planar networks
even for fixed P
total
u Theorem
If g = 0 and d < 1 in regular planar networks
Then no matter how many nodes there are
No matter how far apart the source and destination are chosen
A fixed rate R
min
can be provided for the single-source destination
pair
Idea of proof of unboundedness
u Linear case: Source at 0, destination at n
u Choose
u Planar case
P
ik
=
P
(k -i)
a
k
b
0 1 i k n
P
ik
Source Destination
Source
0
i
q
r
q
Destination
(i+1)
q
i
q-1
Superlinear transport capacity Q(n
q
)
u Theorem
Suppose g = 0
For every 1/2 < d < 1, and 1 < q < 1/d
There is a family of linear networks with
C
T
= Q(n
q
)
The optimal strategy is coherent multi-stage relaying with
interference cancellation
Idea of proof
u Consider a linear network
u Choose
u A positive rate is feasible from source to destination for all n
By using coherent multi-stage relaying with interference cancellation
u To show upper bound
Sum of power received by all other nodes from any node j is bounded
Source destination distance is at most n
q
0 1 i
q
k
q
n
q
P
ik
Source Destination
P
ik
=
P
(k -i)
a
where 1<a < 3- 2qd
Experimental scaling law
u Throughput = 2.6/n
1.68
Mbps per node
- No mobility
- No routing protocol overhead
-Routing tables hardwired
No TCP overhead
UDP
IEEE 802.11
u Why 1/n
1.68
?
- Much worse than optimal capacity = c/n
1/2
- Worse even than 1/n timesharing
- Perhaps overhead of MAC layer?
Log(Thpt)
Log( Number of Nodes)
IT Convergence Lab
u Movie
Concluding Remarks
u Studied networks with arbitrary numbers of nodes
Explicitly incorporated distance in model
Distances between nodes
Attenuation as a function of distance
Distance is also used to measure transport capacity
u Make progress by asking for less
Instead of studying capacity region, study the transport capacity
Instead of asking for exact results, study the scaling laws
The exponent is more important
The preconstant is also important but is secondary - so bound it
Draw some broad conclusions
Optimality of multi-hop when absorption or large path loss
Optimality of coherent multi-stage relaying with interference cancellation when no
absorption and very low path loss
u Open problems abound
What happens for intermediate path loss when there is no absorption
The channel model is simplistic - fading, multi-path, Doppler, ...
..
To obtain papers
u Papers can be downloaded from
http://black.csl.uiuc.edu/~prkumar
u For hard copy send email to
prkumar@uiuc.edu