Transcript QoS Routing and Scheduling in TDMA based Wireless Mesh

QoS Routing and Scheduling
in TDMA based Wireless
Mesh Backhaul Networks
Chi-Yao Hong, Ai-Chun Pang ,and Jean-Lien C. Wu
IEEE Wireless Communications and Networking Conference, 2007.
WCNC 2007.
Mei-zhen Chen
Outline
 Introduction
 Motivation
 The
Proposed Mechanism
 Performance Evaluation
 Conclusions
Introduction
wired connections
wireless connections
wired/wireless connections
(MR)
(WMBNs)
Introduction (cont.)

Authors present an integrated mechanism for realtime applications over TDMA-based WMBNs ,and
propose QoS-aware routing and scheduling
algorithms under the integrated mechanism.
 The algorithms can work with any type of network
topologies, and the link capacity and interference are
taken into account to guarantee QoS .
Motivation

An appropriate routing algorithm needs to find one or
more feasible routes for each pair




interference
• signal-to-interference-and-noise ratio (SINR)
Selected routed paths
• a linear-programming optimization technique
The routes shall not be restricted by a particular topology
The actual traffic demand of an MR varies as depending on
application needs of its serving clients
• a dynamic routing strategy
The Proposed Mechanism
-assumptions (1/4)

Consider a single-channel single-transceiver MAC.
 There is only one gateway in the network.
 Packet loss is assumed to be neglected.
 The TDD (time division duplexing) mode is chosen
here for uplink and downlink transmissions.

the traffic demand of an MR v, D[v]
The Proposed Mechanism
-assumptions (2/4)


The IEEE 802.16 standard provides multiple transmission
rates by applying different modulation schemes and coding
rates.
The receiver minimum input level sensitivity, RSS
The receiver
signal-to-noise
ratio (SNR)
The sampling
frequency in MHz
The number of
OFDM subcarriers
2
log2  Nused 
BW is the channel bandwidth and η is a constant sampling factor.
The number of
allocated
subchannels
The Proposed Mechanism
-assumptions (3/4)

On the other hand, RSS is also given by
where EIRP is the effective isotropically-radiated power
Gt(dBi) : transmitter antenna gain.
Gr(dBi) : receiver antenna gain.
SLt : transmitter loss
SLr : receiver loss.
TxPower(dBW) : the transmission power.
LM(dB) : the link margin.
PL(dB): the transmission path loss.
The Proposed Mechanism
-assumptions (4/4)

The MRs in WMBNs are assumed to be stationary
and communicate without obstructions, the fading
effects are negligible.
 Adopt two-ray ground reflection model as our path
loss model.
The Proposed Mechanism
gateway
-flowchart
The Proposed Mechanism
-routing algorithm (1/4)

Authors slightly modify the Dijkstra’s algorithm to
find a path from the gateway to a particular MR.
 the weights of wireless links could be changed as
the alteration of network flows.
 the modified algorithm terminates immediately
after the path from the gateway to the target MR is
discovered
The Proposed Mechanism
-routing algorithm (2/4)


A mesh network is modeled as an undirected graph G = (V,E)
 V : MRs
 E : wireless links
E[G] : set of the wireless links.
 R[i, j] : the bit rate of link (i, j) derived.
 B[i, j] : the available bandwidth of link (i, j).
 D[v] : the traffic demand of router v.
 I[v] : the granted bandwidth of router v. (initially set by 0)
 U[G] : a subset of the nodes whose demands have not been
satisfied.
 P[G] : a subset of the wireless links along the selected path.
The Proposed Mechanism
-routing algorithm (3/4)
W[i, j] : the occupancy
ratio of a link (i, j).
S[m, n] : the subtracted
bandwidth quantity of
link (m, n) interfered by
link (i, j).
The Proposed Mechanism
-routing algorithm (4/4)

to maximize the achievable traffic demand of router v,
D’[v]
The Proposed Mechanism
-scheduling algorithm

F[i, j] : whether the demand of link (i, j) is already
scheduled in the current schedule period

S[i, j] : whether link (i, j) is interfered by any other
active links
The Proposed Mechanism
-scheduling algorithm (cont.)
extract nonblocking links
Q[G]: the subset of
the links whose
demands are satisfied.
Performance Evaluation (1/5)





20MRs are randomly distributed
25 × 25 km2 area
A gateway is placed in the center of the area
The packet overheads conform to the RTP, UDP, IP
and IEEE 802.16 packet formats.
The event-driven simulation is implemented by C++
programs.
Performance Evaluation (2/5)
Performance Evaluation (3/5)
Performance Evaluation (4/5)
Performance Evaluation (5/5)
the mean traffic demand: 150Kbps
Conclusions

Authors considered the QoS problem for routing and
scheduling in TDMA-based WMBNs.
 Authors proposed an integrated routing and
scheduling mechanism to provides QoS guarantees.
 A linear programming optimization was devised to
solve the amount of non-collision bandwidth.