Transcript Spatial Throughput Of Multi-Hop Wireless Networks Under

Cross-Layer Performance
Analysis for Decentralized
Multihop Wireless Networks
Tarik Tabet
Raymond Knopp
Mobile Communications Laboratory
Ecole Polytechnique Fédérale de Lausanne
Lausanne, Switzerland
[email protected]
Mobile Communications Department
Eurecom Institute
Sophia-Antipolis, France
[email protected]
Motivation/Goal



Rapidly-deployable small-scale multihop wireless
networks (e.g. broadband hotspots for emergency/disaster
relief)
Motivated by Cross-Layer mechanisms
(PHY/MAC/Routing) aiming at maximizing the spectral
efficiency of the network
Tool for characterizing the transport capacity of such
networks (bit m/s) from a “microscopic” point-of-view as a
function of topological parameters (e.g. node population
density) and system parameters (propagation, bandwidth,
Interplay between Tools
Interference statistics
Random Network Topologies
(Spatial Processes)
•Kleinrock+Nelson (COM-84)
•Sousa (IT 1992)
•Baccelli (2003)
Multiple-Access/Coding for
Decentralized Channels
(Collision Channels)
•Massey+Mathys (IT-1985)
•Caire + Tuninetti (IT-2000)
Achievable link
throughput/delay
Geographic Routing Strategies
and performance metrics
•Baccelli et al (2003)
Network and propagation
model

Nodes are spatially distributed in the plane according to a
homogeneous spatial Poisson process[NelsonK84]. The
number of nodes in a region S of area A(S) is:

The propagation model is described by the signal attenuation
due to the distance r between the transmitter and the
receiver and the Rayleigh fading (narrowband/flat):
System model and setting

Slotted transmission structure. Messages are potentially coded
across many slots (interference diversity).

Slotted Gaussian Collision channel with fading.

An infinite number of packets available for each source (stability
of protocols is ignored in this study, no queuing).

ACK/NACK feedback signaling channel is error-free and delayfree.

Single-user decoding.
System model and setting…

Block-fading channel model.
Signal strength
Slot duration
t
System Model and Setting
time
slot
User transmission
System model and setting…


For routing based on average SINR (RS1,RS2), the fading is
an i.i.d process across successive slots -> diversity against
fading with coding. In a real system, this can be achieved
via slow frequency hopping across a large system bandwidth.
For (RS3), we assume a long-term static channel (i.e.
constant over slots) -> diversity against fading is realized
by a form of multiuser diversity in the routing scheme.

Each node transmits a packet with probability p and remains
silent with probability 1-p such that transmit and receive
nodes have spatial Poisson distributions with average node
density p and (1-p) respectively.

Each node transmits with fixed power P.
MAC protocols

Nodes access the channel at random and employ simple
protocols to retransmit the erroneously received packets.

Two retransmission protocols: Slotted Aloha and Incremental
Redundancy. Analytical techniques are based on [CaireT01]
adapted to this channel interference scenario.

Spatial Poisson process characterization leads to a new
representation of interference and collisions between
concurrent transmissions for the Gaussian collision channel
with fading.
MAC protocols…

We compare these strategies to the generalization of the collision
channel without feedback or delay constraints [MasseyM85].
collision
1
2 3
1

2 3
Decoding interval
4
5
4 5
As it will be seen later, the measure of success of a transmission will
be an achievable ergodic throughput of this channel.
MAC protocols…

In the case of coded slotted aloha or incremental redundancy,
the decoding stops after the reception of an ACK on the
feedback channel leading to a finite average delay.

When packets from different nodes collide, it may still be
possible to successfully decode the packet with the strongest
received signal power, which is known as the "capture effect”.

The coded slotted aloha could be generalized to an M slotted aloha where each codeword is split in M parts and
transmitted in M slots (in order to benefit from some
diversity). We consider that the M blocks are independent
and M is fixed. M controls the average delay.
Signal model

The signal model is given by:

where the index s denotes the slot, yj,s the received
signal at node j, xk,s the transmitted signal from
node k, nj,s the background noise at node j.
Link performance of different schemes is
characterized by the instantaneous average
mutual information (information outage
probability)
Information outage probability

The instantaneous average mutual information for a (i, j) pair of
nodes:
where
Information outage
probability…

We need to compute the MGF of V [Sousa92]
the p.d.f of the distance between a transmitter and a receiver is
given by:
Information outage
probability…
We finally obtain :
and
is the Gamma function.
Incremental Redundancy

It adjusts the code rate by incrementally transmitting redundancy
information until decoding is successful.

Node k encodes its message information of b bits each
independently of other nodes by using a channel code with code
book
where N is the slot length and L is the
accumulated number of slots.

Codewords are divided into L sub-blocks of length N, and we let
for
denote the punctured code of length
obtained
from
by deleting the
last sub-blocks.
Incremental Redundancy…

If successful decoding occurs at the l-th transmission,
the effective coding rate for the current codeword is R/l
bit/dim where R=b/N.

For the sake of computing information theoretic
quantities, we let
.

Following the analysis in [CaireT01], we define the
throughput as:
bit/dim
where  is the mean delay measured in slots for the
transmission of an information message.
Incremental Redundancy…



In incremental redundancy, the receiver has memory of the past
signals since it accumulates mutual information.
The probability of successful decoding after l transmitted slots is
given by:
where
and we used the fact that
for
.
The throughput is:
Slotted Aloha

Again the throughput is defined as:
bit/dim.

In Aloha, the receiver has no memory of the past
signals, and the probability of successful decoding
after l transmitted slots is given by:
Slotted Aloha…

The mean delay is then given by:

And the throughput:
Spatial throughput
expressions

The spatial throughput is expressed as a function of the
product of the number of the simultaneously successful
transmissions per unit space by the average jump made by
each transmission [NelsonK84].

We carry out its optimization with respect to the channel
access probability p (MAC) and target Spectral Efficiency
R (PHY)

The relationship between the spatial throughput and the
Gupta-Kumar transport capacity is described in [Baccelli03].
Expected forward progress

The expected forward progress of a packet in the direction of its final
destination F, is the distance Z between the transmitter and the
receiver (an intermediate node) projected onto a line towards the
final destination and the transmission to that receiver is successful.
Routing strategies

In the following we consider three routing strategies:
one that maximizes the expected forward progress by moving
the packet to the node most forward towards the final
destination (RS1).

the second moves the packet to the closest node in range.
Similar strategy is considered in [GrossT02] where the
transmit range is on the order of
, n being the number
of nodes in an unit area, and in [YuenY03] in the context of
mobile infostations networks (RS2).

The third where the next hop is selected to exploit the best
channel and to be the most forward -> attempt to exploit
instantaneous channel state information at transmission when
choosing candidate routes (RS3).
Spatial throughput

The spatial throughput is defined as
where
is the expected forward progress for strategy
and
(for u=RS1, RS2),
for slotted Aloha and
for
incremental redundancy.
,
Maximal expected forward
progress (RS1)

We are looking for a receiver that maximizes the forward
progress, and we consider a sender centric transmission model

We obtain finally
Closest node in range (RS2)

The p.d.f of the minimum distance between the transmitter
and the receiver among all the receive node distances is :

The expected forward progress for this strategy is:
Channel driven maximal
forward progress (RS3)





Exploit multi-user diversity for slowly varying channels
in dense networks.
Instantaneous CSI is available at the transmitter in order
to select the next hop which is the most forward and with
the best channel.
The forward progress is:
The outage probability is conditioned on the knowledge
of the channel at the transmitter.
We make use of a result on stable distributions with
exponent 1/2.
Channel driven maximal
forward progress RS3…
The MGF of V is given by:
Channel driven maximal
forward progress RS3…

The outage probability is then:
Which leads to an expected forward progress for RS3
where
:

Numerical results

The spatial throughput is expressed as a function of
different system parameters: the transmit SNR
P/N0the target information rate R, the transmit
probability p, and the node density .

The optimal throughput vs. the target
information rate is derived by maximizing over the
channel access probability p.
Spatial Throughput (bit – m /dim/m2)
Numerical Example: SNR = 5dB, =1 node/m2
Rate R
Numerical results…



The channel driven strategy performs substantially better
than the other strategies by exploiting transmissions only
to nodes with instantaneously good channels.
This suggests that routing should be based on the
instantaneous channel strength of the link, which could
require fast route updates (in comparison to existing
routing protocols for ad hoc networks) if the channel
changes rapidly.
For the maximal expected forward progress, routing is
based on a spatial empirical average of the SINR's at the
transmitter among the nodes in its proximity. This is
reasonably simple for slowly varying channels and could
be included in existing routing protocols.
Future directions

Receiver-oriented MAC where scheduling (SINRbased) of transmitters at the receiver.

MIMO and directional antennas: interference
mitigation + spectral efficiency increase.

Analysis of multi-user detection techniques.

Non-uniform or event-driven traffic
Conclusions

We derived formulas for the spatial throughput for simple MAC
protocols and transmission strategies for random networks
described by a spatial Poisson point process. ->Allows for an
operational assessment of an ad hoc deployment.

It is shown that coding and retransmission protocols are a viable and
simple solution for providing fully decentralized multiple-access
communications in ad hoc wireless networks despite harsh
propagation characteristics (interference from nearby competing
nodes). Random exclusion and a decentralized protocol allow for
the mitigation of the interference coming from other nodes.

A routing protocol aiming to maximize the expected forward
progress and exploiting multi-user diversity is shown to significantly
outperform other routing schemes.