Transcript Analysis of IEEE 802..

Analysis of IEEE 802.16
Mesh Mode Scheduler Performance
IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS,
VOL. 6, NO. 4, APRIL 2007
Min Cao, Wenchao Ma, Member , IEEE, Qian Zhang, Senior Member , IEEE,
and Xiaodong Wang, Senior Member , IEEE
Presentd by Chan Chih-Yuan (詹志元）
2007/03/26
OPLAB, NTUIM
1
Author (1/4)
Min Cao
• Currently he is a Ph.D. candidate in the
Department of Electrical and Computer
Engineering, University of Illinois at UrbanaChampaign.
• His research interest include mobile computing
and distributed systems, performance analysis and
wireless networks.
2007/03/26
OPLAB, NTUIM
2
Author (2/4)
Wenchao Ma
• Received the Ph.D. degree from the University of
Florida, Gainesville, in 2003.
• He also worked with Microsoft Research Asia
before 2005 as an associate researcher and
currently works with Lenovo Corporate Research
and Development as researcher staff.
• His research interests include wireless multimedia
networks, mobility management, mobile computing,
mobile IP, P2P technology and broadband wireless
access.
2007/03/26
OPLAB, NTUIM
3
Author (3/4)
Qian Zhang
• Received Ph.D. degrees from Wuhan University, China. Dr. Zhang
joined the Hong Kong University of Science and Technology in
Sept. 2005 as an Associate Professor.
• Her current research interests are in the areas of wireless
communications, IP networking, multimedia, P2P overlay, and
wireless security.
• Dr. Zhang is an Associate Editor for
the IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS,
the IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY,and
Computer Networks.
2007/03/26
OPLAB, NTUIM
4
Author (4/4)
Xiaodong Wang
• received the Ph.D degree from Princeton University, all in
Electrical Engineering. Since January 2002, he has been with the
Department of Electrical Engineering, Columbia University
• His current research interests include wireless communications,
statistical signal processing, and genomic signal processing.
• He currently serves as an Associate Editor for
the IEEE TRANSACTIONS ON COMMUNICATIONS,
the IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS,
the IEEE TRANSACTIONS ON SIGNAL PROCESSING,
the IEEE TRANSACTIONS ON INFORMATION THEORY.
2007/03/26
OPLAB, NTUIM
5
Outline
•
•
•
•
•
Introduction
IEEE 802.16 Distributed Scheduling
Performance Analysis
Evaluation
Conclusion
2007/03/26
OPLAB, NTUIM
6
Introduction (1/4)
• In order to improve network coverage and scalability,
mesh mode is supported in Wireless MAN.
• In the mesh mode, the nodes are organized in an ad-hoc
fashion, and all nodes are peers can act as routers to
relay packets for their neighbors.
• A node can choose the links with the best quality to
transfer; and with an intelligent routing protocol, the
traffic can be routed to avoid the congested area.
2007/03/26
OPLAB, NTUIM
7
Introduction (2/4)
• Although the mesh mode exhibits better flexibility and
scalability, the distributed channel access control is more
complex because every node compute its transmission
time without global information.
• In distributed scheduling, every node competes for
channel access using a pseudo-random election
algorithm based on the scheduling information of the
two-hop neighbors, and data subframes are allocated
through a request-grant-confirrm three-way handshaking
procedure.
2007/03/26
OPLAB, NTUIM
8
Introduction (3/4)
• It is necessary to understand the distributed scheduler
behavior thoroughly to optimize the network throughput
and delay performance. In this paper, we focus on the
performance of the distributed scheduling algorithm.
• The IEEE 802.11 DCF (distributed coordination function)
also supports ad hoc mode. However, these
performance analysis approaches for the IEEE 802.11
cannot be applied to the IEEE 802.16 mesh mode
because the two protocols differ in many fundamental
aspects.
2007/03/26
OPLAB, NTUIM
9
Introduction (4/4)
• Particularly, we develop a stochastic model to analyze
the control channel performance.
• This model considers the important parameters that
could affect the system performance like the total node
number, holdoff exponent value, and topology.
• With this model, the channel contention situation and
connection setup time variance can be evaluated clearly
under different parameters.
2007/03/26
OPLAB, NTUIM
10
IEEE 802.16 Distributed Scheduling
• The transmission opportunity and minislot are the basic
unit for resource allocation in the control and data
subframes respectively.
7 OFDM symbols
2007/03/26
OPLAB, NTUIM
11
• In IEEE 802.16 mesh mode, the channel access in the
control subframe is coordinated in a distributed manner
mong two-hop neighbors, and the data subframe slot
allocation is performed through the control message
exchange so that there is no contention in the data
subframe.
• Each node competes for transmission opportunities in
the control subframe based on its neighbors’ scheduling
information such that in a two-hop neighborhood, only
one node can broadcast its control message at any time.
2007/03/26
OPLAB, NTUIM
12
• Once a node wins the control channel, a range of
consecutive transmission opportunities are allocated to
this node, which is called an eligible interval and the
node can transmit in any slot in the interval.
Every node needs to determine its next eligible interval
during the current one.
• A pseudo-random function based distributed election
algorithm defined in the standard is used to decide
whether the node wins a candidate transportation
opportunity.
• If it wins, the reservation information is broadcast to the
neighbors, otherwise the next slot is selected as a
candidate and the procedure repeats until the node wins.
2007/03/26
OPLAB, NTUIM
13
• By broadcasting the MSH-DSCH (Mesh Mode
Distributed Scheduling) messages, each node can have
the scheduling information of its two-hop neighbors.
• In the MSH-DSCH message, two parameters are
included for control channel scheduling - Next_Xmt_Mx
and Xmt_Holdooff_Exponent.
• The first parameter indicates the sequence number of
the first slot in the eligible interval and the eligible length
is L = 2Xmt_Holdoff_Exponent transmission opportunities. The
holdoff exponent value can decide a node channel
contention frequency and affect all the nodes in two-hop
neighborhood.
2007/03/26
OPLAB, NTUIM
14
• In order to solve the contention, the standard defines a
pseudo-random function with the slot sequence number
and all IDs of the competing nodes as inputs.
• The output values are called mixing values. If the current
node ID and the slot number generate the largest mixing
value, it wins this slot and broadcasts the new schedule
to the neighbors.
• If the node fails, the next transmission opportunity is set
to be the temporary transmission slot and the above
competing procedure is repeated until it wins in a slot.
2007/03/26
OPLAB, NTUIM
15
2007/03/26
OPLAB, NTUIM
16
2007/03/26
OPLAB, NTUIM
17
Outline
•
•
•
•
•
Introduction
IEEE 802.16 Distributed Scheduling
Performance Analysis
Evaluation
Conclusion
2007/03/26
OPLAB, NTUIM
18
PERFORMANCE ANALYSIS
A. Model and Approach
• The control subframe is independent of the data
subframe. We consider the modeling and analysis of the
control subchannel, which is characterized by the
distributed election algorithm.
• Assume that the number of nodes in the network is N.
Let
denote the set of 2-hops neighbor nodes of
node k,
denote the set of nodes whose the
schedules are unknown in the neighbor nodes set
.
2007/03/26
OPLAB, NTUIM
19
• Let
node k, then
denote the holdoff exponent of
is the holdoff time of node k.
is the eligibility interval of node k.
• Let
denote the number of slots that node k fails
before it wins the first slot with the pseudo-random
competition, which is a random variable, then the interval
between successive transmission opportunities is
.
• Let
denote the number of transmission times of
node k up to slot t, then
is a counting process with
interevent time
2007/03/26
.
OPLAB, NTUIM
20
• To simplify the analysis, we make the following
assumptions:
• (1)the counting process of each node eventually reaches
its steady state and the intervals are i.i.d., that is,
,
forms a stationary and ergodic renewal process.
• (2)the renewal processes of different nodes are mutually
independent at their steady states.
2007/03/26
OPLAB, NTUIM
21
• Note that the distribution of the renewal intervals of each
node depends on the number of competing nodes in its
neighborhood and their holdoff exponent.
• Our analysis is based on the above assumptions.
2007/03/26
OPLAB, NTUIM
22
• Suppose that the expected number of competing nodes
in slot s for the node k is
.
• As a result of the pseudo-random election algorithm, the
probability that this node wins the slot is
• So the probability mass function of
2007/03/26
OPLAB, NTUIM
is
23
• To get the distribution of , we need to find
. But
depends on the distributions of
since all the nodes in the neighborhood of node k are
candidates to compete with node k.
• the following approach to solve this problem:
derive
in terms of
by modelling the distributed
election algorithm, and then by using the relation
we obtain a set of close form equations for
to
solve them
2007/03/26
OPLAB, NTUIM
24
B. Collocated Scenario
1) Identical Holdoff Exponents:
• we first assume equal holdoff exponents, i.e.,
. Hence when the nodes are
collocated, the transmission interval
has the same
distribution,
• Let
be a renewal process ant t be any chosen time
slot, the spread,
is the renewal interval in which t
lies.
2007/03/26
OPLAB, NTUIM
25
2007/03/26
OPLAB, NTUIM
26
Renewal Process
• A renewal process is a generalisation of the Poisson
process. In the same informal spirit, we may define a
renewal process to be the same thing, except that the
holding times take on a more general distribution.
2007/03/26
OPLAB, NTUIM
27
• The limiting distribution of excess time is established by
the following lemma, which is a corollary of the Renewal
Reward Theorem. The proof is similar to that for the
continuous-time version of the lemma in [20]
• The limiting distribution of the excess time is
for fixed
where
and
is an indicator function.
2007/03/26
OPLAB, NTUIM
28
• By the stationary and ergodic assumption, we can take
the limiting distribution of excess time as its stationary
distribution
• The distribution of τ is given in terms of {p(s)} as
where
2007/03/26
OPLAB, NTUIM
29
2007/03/26
OPLAB, NTUIM
30
• Since the renewal process of node k and node j are
assumed to be statistically independent, at the current
transmit time t of node k, the time from t to the next
transmit time of node j is simply the excess time
of node j.
• By the assumption that the renewal process is stationary
and that the distributions of are identical, we can simply
denote
as e.
2007/03/26
OPLAB, NTUIM
31
2007/03/26
OPLAB, NTUIM
32
2007/03/26
OPLAB, NTUIM
33
• When the holdoff exponents of all the nodes are identical
this probabilities is the same for any two nodes k and j.
• By the assumption of statistical independence
• Hence the expected number of nodes competing with
node k in slot s is
and the competing nodes in slot s for node k is
• Substituting (9) into (1) we get
2007/03/26
OPLAB, NTUIM
34
2007/03/26
OPLAB, NTUIM
35
• Combining (8) and (10), we get a set of equations by
which we can solve for p(s), s=1,2,.... Typically,
as
, so we can truncate the tail and consider only
p(s), s=1,2,…,L for some large L, and then solve the
fixed point equations by using standard iterative method.
• By observing the histograms of our simulation, we find
that the distribution of S can be approximated by a
geometric distribution. So we make a further
approximation that
2007/03/26
OPLAB, NTUIM
36
• Then we have
similar to (4) and (5) we can
derive the distribution of
as follows
and the distribution of
2007/03/26
as
OPLAB, NTUIM
37
• Then the probability that another node j will compete with
node k in the given slot
is
2007/03/26
OPLAB, NTUIM
38
• For the geometric distribution,
for all s, hence
for all s, which implies that the number of
competing nodes in each slot s should be the same. Here
we approximate M as the expectation of
as
• Using (14) and (15) and after some manipulations, we
get
2007/03/26
OPLAB, NTUIM
39
• By observing the histograms of our simulation data, we
find that the distribution of S can be approximated by a
geometric distribution. So we make a further
approximation that
• Then we have
. Similar to (4) and (5) we can derive
the distribution of τ as follows
2007/03/26
OPLAB, NTUIM
40
• The distribution of
as
• Then the probability that another node
with node k in the given slot
2007/03/26
OPLAB, NTUIM
will compete
is
41
• Substitute
, and
the above equation in terms
into (17), we express
of as
• A fixed point iteration can be used to obtain E[S] from
(18).
2007/03/26
OPLAB, NTUIM
42
• 2) Nonidentical Holdoff Exponents:
Now we consider the case where holdoff exponents
is not identical.
2007/03/26
OPLAB, NTUIM
43
2007/03/26
OPLAB, NTUIM
44
• Denote
as the probability that node j will
compete with node k in the given slot
, which is
given by (21), where
.
• Again, by the assumption of statistical independence,
2007/03/26
OPLAB, NTUIM
45
• Similarly we can find the distributions of
by the fixed point iterations. We further assume that
are geometrical distributed as before,
that is, assume
• Hence the distribution of
2007/03/26
is
OPLAB, NTUIM
46
2007/03/26
OPLAB, NTUIM
47
2007/03/26
OPLAB, NTUIM
48
• To estimate
, we proceed as follows
• Derive
from (21), (23) and (25). Here we
directly give the approximation result as
2007/03/26
OPLAB, NTUIM
49
• Note that
combining (26) and (27), we have
• Again we can solve for
2007/03/26
using fixed point iteration.
OPLAB, NTUIM
50
• 3) General Topology Scenario:
• (1)the neighborhood node sets of different nodes
may be different
• (2)there exist unknown nodes, hence besides the
competing cases 1 and 2, there are unknown competing
nodes.
• Since unknown nodes are always regarded as
competing nodes in each slot by the distributed election
algorithm, we have
2007/03/26
OPLAB, NTUIM
51
• Taking unknown nodes into account
• Again we can solve for
2007/03/26
using fixed point iteration.
OPLAB, NTUIM
52
D. Performance Metrics Estimation:
• Let
denotes the time node A needs to
accomplish a three-way handshaking with node B.
• Now we can derive
given the distributions of
of all nodes
•
is the time interval between node A sending a
Request to B and B replying a Grant to A.
is the time interval between B sending the Grant and
A replying with a Confirm.
2007/03/26
OPLAB, NTUIM
53
• By the independence assumption, and further assuming
that the renewal processes of node A and B have run for
a long time so that we can assume that
follows a
limiting distribution as the excess time
• However,
may not follow the same distribution as
since it is dependent on
, thus the limiting
distribution does not hold.
It is very complicated to find the exact distribution of
since the renewal interval
is not geometrical
distributed.
2007/03/26
OPLAB, NTUIM
54
• Note that when
, the renewal process of node A
can be considered to run for a long time after sending
Request, so in this case we can assume that
• In this case,
• On the other hand, when
,
since the
portion of excess time
is negligible, and
2007/03/26
OPLAB, NTUIM
55
• Empirically, estimated as
Compromising factor
•
• Based on the simulation data, we find
identical holdoff exponents case and
nonidentical exponents case.
2007/03/26
OPLAB, NTUIM
for the
for the
56
• Once
is known, from (25) we can calculate
• Employing the results of
from previous
subsections, we can determine
for any two
neighbor nodes handshake A and B by using (32) and
(33).
2007/03/26
OPLAB, NTUIM
57
Outline
•
•
•
•
•
Introduction
IEEE 802.16 Distributed Scheduling
Performance Analysis
Evaluation
Conclusion
2007/03/26
OPLAB, NTUIM
58
Evaluation
• A. Simulation Methodology
1) Collocated Scenario:
• The total transmission opportunities in control channel
becomes 256 when the exponent value is 4.
• Varying the total node number from 10 to 128 to study
the scheduler performance
2007/03/26
OPLAB, NTUIM
59
2) General Topology:
• The scheduling information of some neighbors beyond
one hop may become stale.
• The reason is that some one-hop neighbors could not
update the schedule information in time for some specific
transmission order.
• A neighbor node becomes unknown node once is
schedule information is stale and always be treated as
potential competitor.
2007/03/26
OPLAB, NTUIM
60
2007/03/26
OPLAB, NTUIM
61
• B. Numerical Results
(1) Transmission Interval:
• In the identical case:
• The node transmission intervals increase with the total
node number and exponent values.
• When N becomes larger, the contention becomes more
intensive so that a node has to compete more times
before wins.
2007/03/26
OPLAB, NTUIM
62
2007/03/26
OPLAB, NTUIM
63
• In the nonidentical exponent case:
• Divding the N nodes into five group of equal size. The
nodes in each group takes the same exponent value
from the set {0,1,2,3,4}.
• The analytical and simulation results are also compared.
The system behaves similarly as in the identical
exponent scenario with longer transmission intervals.
2007/03/26
OPLAB, NTUIM
64
• (2) Three-Way Handshaking Time: (1/2)
Holdoff Time Dominates
2007/03/26
OPLAB, NTUIM
65
• (2) Three-Way Handshaking Time: (2/2)
2007/03/26
OPLAB, NTUIM
66
• (3) General Topology Scenario:
2007/03/26
OPLAB, NTUIM
67
Outline
•
•
•
•
•
Introduction
IEEE 802.16 Distributed Scheduling
Performance Analysis
Evaluation
Conclusion
2007/03/26
OPLAB, NTUIM
68
CONCLUSIONS (1/2)
• In the mesh mode, every node competes for the channel
access in a distributed manner and tries to broadcast its
scheduling information periodically.
• This model assumes that the transmit time sequences of
all the nodes in the control subframe form statically
independent renewal processes.
2007/03/26
OPLAB, NTUIM
69
CONCLUSIONS (2/2)
• A good reservation scheme should guarantee the
bandwidth allocation fairness and improve the channel
utilization at the same time.
• Such a reservation scheme needs the information such
as the connection setup time and contention success
probability provided by this model.
• Our future work is to propose such a reservation scheme
taking into account the tradeoff between system
resource utilization and the connection QoS requirement.
2007/03/26
OPLAB, NTUIM
70
• In our study, we assumes the transmit time sequences of
all the nodes in the control subframe form statistically
independent renewal processes.
• Based on this assumption, we develop a stochastic
model to estimate the control channel performance.
2007/03/26
OPLAB, NTUIM
71