Transcript The Complexity of Channel Scheduling in Multi-Radio Multi

The Complexity of Channel
Scheduling in Multi-Radio
Multi-Channel Wireless
Networks
Wei Cheng & Xiuzhen Cheng
The George Washington University
Taieb Znati
University of Pittsburgh
Xicheng Lu & Zexin Lu
National University of Defense technology
Outline





Introduction
Network Model
The Complexity of OWCS/P
PTAS for OWCS/P
Summary
Introduction – Background

Multi-Radio Multi-Channel (MR-MC) to
enhance mesh network throughput
• Equipped with multiple radios, nodes can
•
communicate with multiple neighbors
simultaneously over orthogonal channels to
improve the network throughput.
The key problem is the channel scheduling,
which aims to maximize the concurrent traffics
without interfering each other.
Introduction – Interference Model

P(hysical) interference-free model
• if two nodes want to launch bidirectional
communications, any other node whose
minimum distance to the two nodes is not larger
than the interference range must keep silent.

Hop interference-free model (no position)
•
… is no larger than H hops must keep silent.

Introduction – Problem

Optimal Weighted Channel Scheduling
under the Physical distance constraint
(OWCS/P)
• Given an edge-weighted
graph G(V,E)
representing an MR-MC wireless network,
compute an optimal channel scheduling O(G) ∈
E, such that O(G) is P interference-free and the
weight of O(G) is maximized

Optimal Weighted Channel Scheduling
under Hop distance constraint (OWCS/H)
Introduction – Motivation


Both the physical interference-free
model and the hop interference-free
model are popular but their relations
have never been addressed in literature.
Current complexity results for OWCS
Related Research


Channel allocation, routing, and packet
scheduling have been jointly considered
as a IP problem
Channel Assignment
• Common channel
• Default radio for reception
• Code based approach
Related Research

The complexity of scheduling in SR-SC
networks
• OWCS/H>=1 is NP hard
• OWCS/H>=1 has PTAS
Network Model



Geometric graphs G(V,E), |V | = n
a set of C ={c1, c2, · · · , ck} orthogonal
channels
∀ node i ∈ V , 1 ≤ i ≤ n, it is equipped
with ri radios and can access a set of Ci
⊆ C channels, where |Ci| = ki.
Formal Definition




Edge-Physical-Distance
Edge-Hop-Distance
OWCS/P: Seek an E’ such that any pair
of edges in E’ has an Edge-PhysicalDistance >P, and E’ is the maximum
OWCS/H: Seek an E’ such that any pair
of edges in E’ has an Edge-PhysicalDistance >H, and E’ is the maximum
The Complexity of OWCS/P

Lemma : OWCS/P=1 and OWCS/H=1 are
equivalent in SR-SC wireless networks.
• Intuition: the interference graphs of G(V,E) for
•
the cases of P=1 and H=1 are the same
Proof:
• OPT/P=1 is a feasible solution to OWCS/H=1
• We can not add another edge to OPT/P=1 for
OWCS/H=1
• Similarly, OPT/H=1 is optimal to OWCS/P=1
The Complexity of OWCS/P

Theorem : OWCS/P>=1 is NP-Hard in
SR-SC wireless networks.
• OWCS/H=1 is NP-Hard  OWCS/P=1 is NP•
Hard
OWCS/P>1 is polynomial time reducible to
OWCS/P=1
The Complexity of OWCS/P

Theorem: OWCS/P>=1 is NP-Hard in
MR-MC wireless networks.
Known
Known
PTAS for OWCS/P

Polynomial-Time Approximation Scheme
(PTAS) for NP-Hard problem.
• a polynomial-time approximate solution with a
•
performance ratio (1 − ε) for an arbitrarily
small positive number ε .
Let Ptas(G) denote the solution given by the
PTAS procedure and O(G) the optimal
solution for the OWCS/P≥1 problem in a MRMC network G.
• We will prove that W(Ptas(G)) ≥ (1 − ε)W(O(G))
PTAS for OWCS/P-construction

Griding:
• Partition network space
•
into small grids with
each having a size of (P + 2) × (P +2).
Label each grid by (a, b), where a, b = 0,
1, · · · ,N − 1, with N the total number of grids
at each row or column.
• The id of the grid at the lower-left corner can be
denoted by (0, 0).
• Denote the ith row and the jth column of the
grids by Rowi and Colj , respectively.
PTAS for OWCS/P-construction

Shifted Dissection:
• Partition vertically the network space
• by columns of the grids Colj and rows of the grids
Rowi, where j | (m+1)= k1 , i |(m+1)= k2, k1 k2 = 0,
1, · · · ,m. Remove all the edges whose both end
nodes are in Colj or Rowi
• Obtain a number of super-grids with each
containing at most m×m grids. Total (m + 1)2
different dissections
• Denote each dissection by P , where a, b
a,b
indicate that Pa,b is obtained by shifting
Col0 to column b and Row0 to row a.
PTAS for OWCS/P-construction

Computation
• Consider a specific Pa,b
• For each super-grid B in P
a,b
,
• compute an maximum weight
• Let
channel scheduling SB for B.
Sa,b be the union of all SB’s
• Sa,b is a feasible solution for OWCS/P
• Repeat for all Pa,b
PTAS for OWCS/P-algorithm
PTAS for OWCS/P-complexity

Computing SB takes polynomial time.
• the area of B is at most (m(P + 2) + 2)2
• For a specific channel
• The number of SB’s edges in
each ((P + 2)2) grid is
bounded by O(1).
• Then the number of edges in SB is bounded by O(m2)
• Time of computing SB through enumerating is bounded
by |EB|O(m2)
• For all K channels
•
Time of computing SB through enumerating is bounded
by |EB|O(m2)K
PTAS for OWCS/P-performance

For all partition Pa,b
• Sa,b is the optimal solution for Ea,b
• Let
yields
,
PTAS for OWCS/P-performance

A grid will NOT be included in any supergrid among all (m+ 1)2 partitions for 2m+
1 times.
• An edge will NOT be included in any super-grid
among all (m+ 1)2 partitions for at most 2m+ 1
times.
Summary
Summary

The proposed PTAS for OWCS/P is also
a PTAS for OWCS/H in MR-MC wireless
networks.
• Replace P by H
Summary

OWCS/H=1 is equivalent to OWCS/P>=
under the polynomial transformation
• OWCS/H=1 is equivalent to OWCS/P=1
• OWCS/P>1 is polynomial time reducible to
OWCS/P=1

Physical interference free model is more
precise
• Need position information
Q&A
Thanks!