Fakahr Abbas and Tanvir Ahmed

Impact of Interference on Multi-hop Wireless Network
Performance:ABSTRACT
In this paper, the main focus is to find the maximum throughput of given network in
which there is specific placement of wireless nodes in physical space and a specific
traffic workload. A key issue impacting performance is wireless interference
between neighboring nodes. Here, we model such interference using conflict graph
and present methods for computing upper and lower bounds on the optimal
throughput for the given network and workload. To compute these bounds, we
assume that the packet transmission at the individual nodes can be finely and
carefully controlled and scheduled by a central entity.
1. INTRODUCTION
A fundamental issue in multi-hop wireless networks is that performance degrades
sharply as the number of hops traversed increases. For example in a network of
nodes with identical and omni-directional radio ranges, going from a single hop to 2
hops halves the throughput of a flow because wireless interference dictates that
only one of the 2 hops can be active at a time.
In
this paper, a key distinction of our approach is that we work with any given wireless
network configuration and workload specified as inputs. The work done by Gupta
and Kumar was based on the assumption of random node placement and
communication pattern. We make no assumption about the homogeneity of nodes
with regard to radio range or other characteristics, or regularity in communication
pattern. We use a conflict graph to model the effects of wireless interference. The
conflict graph indicates which groups of links mutually interfere and hence cannot
be active simultaneous. We formulate a multi-commodity flow problem to compute
the optimal throughput that the wireless network can support between the sources
and sinks. We show how our methodology can accommodate a diversity of wireless
network characteristics such as the availability of multiple non-overlapping
channels, multiple radios per node and directional antennas. We also show how
multiple MAC protocol models as well as single-path and multi-path routing
constraints can be accommodated. We will use our technique to evaluate how the
per-node throughput in a multi-hop wireless network varies as the number of nodes
grows. In order to evaluate per-node throughput, an assumption is made that all the
nodes are in saturation mode. Despite above, the following 3 scenarios are also
discussed, (i) Multipath routing under the protocol interference model. (ii) Multipath
routing under the physical interference model. (iii) Single path routing under both
models.
2. COMPUTING BOUNDS ON OPTIMAL THROUGHPUT

2.1
Background and Terminology
Here, we find the throughput of wireless networks under two models of

interference: protocol model and physical model as proposed by Gupta and Kumar
[1]. Consider a network with N nodes arbitrarily located on a plane. Let
di j
N denote the nodes and
ni
Each node
denote the distance between nodes
is equipped with a radio with communication range
potentially larger interference range
ni
ni
, 1 i
and
Ri
nj
and
R' i . For simplicity, we consider single
wireless channel. We consider two models, the Protocol Model and Physical Model,
to define the conditions for a successful wireless transmission. These models are
similar to those introduced in [1].
Protocol Model:
If there is a single wireless channel, a transmission is successful if both of the
following conditions are satisfied:
1.
di j
Ri
2. Any node
nk , such that
R' k
dk j
is not transmitting.
Physical Model:
ni wants to transmit to node
Suppose node
SS i j
strength
received at
SNR i j
>
, of node
ni s transmission as
n j . The transmission is successful if

SNR threshold
, where
signal to noise ratio at the node

received from node
nj
n j . We can calculate the signal
SNR i j
nj
for transmission
ni . The total noise,
consists of the ambient noise,
denotes the
N j , at node
N a , plus the interference due to other
ongoing transmission in the network.

We say that a network throughput D is feasible if there exists a schedule of
transmissions such that no two interfering links are active simultaneously, and the
total throughput for the given source-destination pairs is D. In our problem
formulation here, we focus on maximizing the total throughput between sourcedestination pairs.
2.2 Multipath Routing under the Protocol Interference

Model
2.2.1 Conflict Graph

To incorporate wireless interference into our problem formulation, we define a
conflict graph, F, whose vertices correspond to the links in the connectivity graph,
C. There is an edge between the vertices
l pq
li j
and
l pq
in F if the links
li j
and
may not be active simultaneously.
2.2.2 Lower Bound

In order to find a lower bound of the network throughput D, we make the following
observations. Links belonging to a given independent set in conflict graph F can be
scheduled simultaneously. Suppose there are a total of K maximal independent sets
in graph F. Let
,0
I 1 , I 2 ,
Ik
denote these maximal independent sets and
i 1 denote the fraction of time allocated to the independent set. The
lower bound results reveal that:

K
'
i 1
i=1
fi j
(because only one maximal independent set can be active at a time)
i Ca p i j
l i j I ,
i
(because the fraction of time for which a link may be active
is constrained by the sum of the activity periods of the independent sets it is a

number of ).
2.2.3 Upper Bound

Now we derive the upper bound on the network throughput. Consider the conflict
graph. A clique in the conflict graph is a set of vertices that mutually conflict with
each other. The total usage of the links in a clique is at most 1.We can find many
cliques and write corresponding constraints to define a polytope. We can then
maximize the throughput over the intersection of this polytope with flow polytope.
This will give us an upper bound on the throughput.
2.3 Multipath Routing under the Physical Interference

Model
Conflict Graph
To take interference effects into account under the physical interference model, we
construct a conflict graph F. Unlike in the protocol model, conflicts in the physical
model are not binary. Rather, the interference gradually increases as more
neighboring nodes transmit and becomes intolerable when the noise level reaches a
threshold.
2.3.1 Lower Bound

Analogous to independent sets, we introduce the notion of schedulable sets in the
Hx
physical model. A schedulable set

every vertex
li j
Hx ,
ipjq
lp q H
is defined as a set of vertices such that for

1. It follows that all links in a schedulable
set can be active simultaneously. It includes the following constraints.

K
'
x 1
x=1
fi j
, Where K is the number of schedulable sets found
x Ca pi j
l i j H ,
x
2.3.2 Upper Bound

To derive an upper bound, we consider maximal sets vertices in F such that for any
pair of vertices
li j
and
l pq
pq
i j
1. These correspond to the cliques in
the protocol interference model. Therefore for each such set, we add a constraint
that the sum of their utilization has to be no more than 1. These constraints may
result in a loose bound since there may not be very many cliques.
2.4 Discussion of Limitations:

First, this model does not provide an easy means for accommodating node mobility.
Node mobility would cause both the connectivity and conflict graph to change with
time.
Second, time-varying channels may
also pose a problem. Time-varying channel characteristics could result either from
the interference caused by other nodes or from physical effects, e.g. mobilityinduced fading.
Finally, the results suggest that our methodology is feasible for modest sized
networks of the order of few hundred nodes, which may be typical of neighborhood
wireless networks. However, the methodology in its current form is likely to be too
expensive for large-scale networks containing thousands or millions of nodes, e.g.
sensor networks.
3. CONCLUSION AND FUTURE WORK

In this paper, we have presented a model and methodology for computing bounds
on the optimal throughput that can be supported by a multi-hop wireless network. A
key distinction compared to previous work is that we work with any given wireless
network configuration and workload specified as inputs. No assumptions are made
on the homogeneity of nodes with regard to radio range or other characteristics, or
regularity in communication pattern. We use a conflict graph to model wireless
interference under various conditions (multiple radios, multiple channels, etc.). We
view the generality of our methodology and conflict graph framework as a key
contribution of our work.
Although the
bounds that we that we compute on the optimal throughput assume the ability to
finely control and carefully schedule packet transmission, the optimal routes yielded
by our analysis often outperform shortest path routes even under real-world
conditions such as uncoordinated scheduling and MAC contention. In ongoing work,
we are continuing to investigate the benefits of interference-aware routing under a
wide range of scenarios. Our next step after that would be to design a practical
interference-aware routing protocol, which addresses interesting challenges such as
constructing the conflict graph and computing optimal routes in a distributed
manner.
6. REFERENCES
[1] GUPTA, P., AND KUMAR, P. R. The capacity of wireless networks. IEEE
Transaction on Information Theory 46, 2 (Mar. 2000)

Fakahr Abbas and Tanvir Ahmed

Uploaded by

Copyright:

Available Formats

Fakahr Abbas and Tanvir Ahmed

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Fakahr Abbas and Tanvir Ahmed

Uploaded by

Copyright:

Available Formats

Impact of Interference on Multi-hop Wireless Network

2. COMPUTING BOUNDS ON OPTIMAL THROUGHPUT

Here, we find the throughput of wireless networks under two models of

N denote the nodes and

denote the distance between nodes

is equipped with a radio with communication range

potentially larger interference range

R' i . For simplicity, we consider single

n j . The transmission is successful if

signal to noise ratio at the node

n j . We can calculate the signal

ni . The total noise,

consists of the ambient noise,

N a , plus the interference due to other

ongoing transmission in the network.

2.2 Multipath Routing under the Protocol Interference

2.2.1 Conflict Graph

may not be active simultaneously.

2.2.2 Lower Bound

denote these maximal independent sets and

i 1 denote the fraction of time allocated to the independent set. The

lower bound results reveal that:

(because only one maximal independent set can be active at a time)

(because the fraction of time for which a link may be active

is constrained by the sum of the activity periods of the independent sets it is a

2.2.3 Upper Bound

2.3 Multipath Routing under the Physical Interference

2.3.1 Lower Bound

physical model. A schedulable set

is defined as a set of vertices such that for

set can be active simultaneously. It includes the following constraints.

, Where K is the number of schedulable sets found

2.3.2 Upper Bound

1. These correspond to the cliques in

2.4 Discussion of Limitations:

3. CONCLUSION AND FUTURE WORK

You might also like