Transcript Document

Interference-Aware Multicasting
in Wireless Mesh Networks
Sudheendra Murthy, Abhishek
Goswami, Arunabha Sen
Networking 2007
1
Outline






Introduction
Problem Formulation
Optimal Solution
Proposed Algorithms
Simulation Environment and Results
Conclusion and Comments
2
Introduction

WMN has fueled research work in providing better
support to multimedia applications like





real-time video transport and
VoIP services.
Common to these applications is the need for a multicast
framework.
Early efforts in providing multicast support in WMN
ignored to consider the interference effects.
We present a novel multicast framework that considers


the effects of interference and
constructs a multicast structure that provides maximum
bandwidth.
3
Introduction


Our objective is to identify multicast forwarding
group nodes whose transmission includes least
amount of interference.
The main contributions:





We provide a novel formulation of the problem as a
graph problem.
We prove the NP-completeness of the problem.
We provide an Integer Linear Program technique.
We provide a centralized heuristic algorithm and describe
a distributed implementation.
We compare the performance of the proposed heuristic
with the optimal, shortest path and minimum Steiner
tree solution.
4
Outline






Introduction
Problem Formulation
Optimal Solution
Proposed Algorithms
Simulation Environment and Results
Conclusion and Comments
5
Network Model







RT: transmission range.
RI: interference range.
G(V, E): directed potential communication graph.
dist(u, v): Euclidean distance between u and v.
One radio/node, one common channel.
Any node can be the source node in the multicast
tree.
RI = q × RT with q ≧ 1.
6
Network Model

H(V, F): directed potential interference graph

Vertex set corresponds to the mesh routers.



(u, v) in H implies that the transmission of u can
cause interference at v.
Our interference model



captures the idea of co-channel interference occurring at
the receiving nodes.
The conflict graph and potential interference model can
be derived from each other.
The potential interference graph modeling makes our
7
problem definition more elegant.
Graph Definitions and Notations


: In-degree
: Out-degree





N[v]: includes v and the neighbors of v.
, neighborhood of a vertex
subset S.
〈S〉G : the weakly induced subgraph of graph G
on the vertex set S. Including N[S] and E∩(S×N[S]).
9
Problem Definition



The maximum data rate is limited by
bottleneck link.
The data rate of bottleneck link is
determined by the amount of interference
experienced by the receiver of the link.
Our goal is to find the group of forwarding
nodes that induce the least interference on
the forwarding nodes and the receivers.
10
Problem Definition

Given G(V, E), H(V, F), source s, receiver set R, find
vertex set S such that




The subgraph of G weakly induced by S, i.e., 〈S〉G has
directed paths connecting s to each receiver.
The maximum in-degree of the vertices of the subgraph
of H weakly induced by S is minimized.
We term this problem as the Minimum-Degree
Weakly Induced Connected Subgraph (MDWICS)
problem. => NP-complete.
The optimal subset S of the MDWICS problem
result in the least interference.
11
Outline






Introduction
Problem Formulation
Optimal Solution
Proposed Algorithms
Simulation Environment and Results
Conclusion and Comments
12
Optimal Solution



We provide an ILP formulation to solve the MDWICS
problem.
Xi,j=1, if edge (i,j) is in the optimal solution, 0 otherwise.
fpi,j=1, if there is a flow from s to receiver p through link
(i,j)
, 0 otherwise.


yi,j=1 for edge (i,j)
, if node i is the transmitter in the
optimal solution, 0 otherwise.


Be used to ensure connectivity from s to receiver r.
Be used to capture the interference caused by i’s transmission on
node j.
The objective is to minimize D,

The maximum in-degree of al the nodes in the interference subgraph.
13
Constraints
14
Flow Conservation Constraints
15
Outline






Introduction
Problem Formulation
Optimal Solution
Proposed Algorithms
Simulation Environment and Results
Conclusion and Comments
16
S: a feasible solution set of vertices that contain paths from
the source to all receivers.
W: contains the set of visited vertices.
Distributed Protocol

Based on the Optimized Link State Routing (OLSR)
protocol.




OLSR could be used in mesh networks to maintain the
state and quality of the links.
The TC (Topology control) messages are efficiently
dispersed in the network through multipoint relays
(MPRs).
Each node is uniquely identified by its IP address.
The source with its topology information
independently computes the set of multicast
forwarding group nodes.
18
Distributed Protocol

It then disseminates through the MPRs,




a MC_FG message consisting of the IP addresses of
the forwarding group nodes and
a MC_JOIN message to the multicast group members.
MC_JOIN message is to inform the multicast
group members about the initiation of the
session.
The session ID is included in every packet
forwarded by the multicast source.

If a node receiving this packet has the session ID
listed in its FG table, it forwards the packet.
19
Outline






Introduction
Problem Formulation
Optimal Solution
Proposed Algorithms
Simulation Environment and Results
Conclusion and Comments
20
Simulation Results

We compared the performance of out heuristic with








shortest Path Tree (SPT) algorithm,
minimum Steiner Tree (MST) approximation algorithm and
The optimal solution obtained by solving the ILP formulation.
# of nodes was fixed to be 70.
The locations of 70 nodes were randomly generated.
The transmission radius was fixed at 100m.
The multicast source and receivers were selected
randomly.
The interference-degree is

the maximum number of forwarding group mesh nodes that
affect any node in the multicast structure.
21
Outline






Introduction
Problem Formulation
Optimal Solution
Proposed Algorithms
Simulation Environment and Results
Conclusion and Comments
24
Conclusion





We categorized the interference-aware
multicasting problem as a graph problem of finding
a weakly induced subgraph of minimum degree.
We introduced a new model of interference.
We presented an efficient greedy-based heuristic
algorithm.
The simulation results provide substantial evidence
of the superior performance of our heuristic.
Future work:


Analyzing the performance of the distributed algorithm
and
Providing approximation bounds to the centralized
25
algorithm.
Comments


This paper not only provide ILP solution, but also
heuristics to approach the optimal solution.
Some mechanisms are used to minimize
interference in order to maximize bandwidth.


However, there is no result about bandwidth or
throughput provided.
In the distributed protocol, we can not see
anything about minimize interference.
26