28-02-2013, 02:59 PM
Robust Routing and Scheduling in Wireless Mesh Networks under Dynamic Traffic Conditions
Robust Routing.pdf (Size: 264.23 KB / Downloads: 59)
Abstract
Joint routing-and-scheduling has been considered in wireless mesh networks for its significant performance improvement.
While existing work assumes it, accurate traffic information is usually not available due to traffic dynamics, as well as inaccuracy and
delay in its measurement and dissemination. In addition, the joint routing and scheduling usually requires a centralized controller to
calculate the optimal routing and scheduling and distribute such policies to all the nodes. Thus, even if the accurate traffic information
is always available, the central controller has to compute the routing and scheduling repeatedly because the traffic demands change
continuously. This leads to prohibitive computation and distribution overhead. Therefore, in this paper, we propose a joint routingscheduling
scheme that achieves robust performance under traffic information uncertainty. In particular, it achieves worst-case optimal
performance under a range of traffic conditions. This unique feature validates the use of centralized routing and scheduling in wireless
mesh networks. As long as the traffic variation is within the estimation range, the routing and scheduling do not need to be recomputed
and redistributed. Through extensive simulations, we show that our proposed scheme meets the objective (i.e., optimize the worst-case
performance). Moreover, although it only guarantees the worst-case performance in theory, its average performance is also good. For
example, our proposed scheme can perform better than a fixed optimal routing and scheduling scheme in more than 80% of 500
random traffic instances. Our scheme provides insights on the desired properties of multipath routing, namely, spatial reuse and load
balancing.
INTRODUCTION
THERE has been a significant amount of interest in
wireless mesh networking for its deployment flexibility
and low cost. Joint routing and (TDM-based)
scheduling has been considered in wireless mesh networks
to improve performance [1], [2], [3], [4]. Most existing
work in joint routing and scheduling assumes accurate
traffic information, e.g., active source-destination
(s-d) pairs and the traffic demand for each pair. However,
accurate traffic information is hardly available because
traffic is dynamic and its accurate measurement is rarely
available. In addition, dissemination of traffic information
incurs delay and signaling overhead.
In this paper, we propose a robust routing-andscheduling
scheme to handle traffic dynamics and traffic
information uncertainty. To elaborate, the proposed
scheme optimizes the worst-case performance (in terms
of relative congestion level) for a range of traffic conditions
and it performs under a whole spectrum of
traffic information granularity.
SYSTEM MODEL
Interference
We note that various interference models have been
proposed in the literature, including graph-based and
SINR-based models. It is important to note that none
of our algorithms relies on the specifics of the interference
model used. The only input from the interference model
required by our algorithm is the sets of links that can
be scheduled simultaneously. Different interference models
may result in different sets of links that can transmit
simultaneously. As long as such an input is provided
by an interference model, the proposed algorithm can
be applied without modifications. We will show how
different interference models can be incorporated into
our framework. For simplicity, we will use graph model
and SINR model to indicate graph-based interference
model and SINR-based interference model, respectively.
Traffic Patterns and Demands
We use a traffic matrix to represent the traffic pattern
and demand. A traffic matrix is an n × n matrix where
the diagonal entries are set to 0. A traffic matrix provides
the traffic demand of each s-d pair. The ith row and jth
column of the traffic matrix, dij , denotes the amount of
traffic from the source node i to the destination node
j. We use the traffic matrix to model different amount
of traffic information available.
TRAFFIC-OBLIVIOUS ROUTING AND
SCHEDULING
Motivated by existing work on traffic-oblivious routing
in Internet, we propose a traffic-oblivious routing-andscheduling
(TORS) scheme that captures the interference
constraints in wireless networks. The objective of
a traffic-oblivious scheme is to handle uncertainty in
traffic information and achieve worst-case optimal performance
under the given range of traffic information.
We first introduce the notations.
Routing and Scheduling with Delay Considerations
Delay is an important issue in real-time applications,
such as audio, video, and gaming. In a wireless network,
packet delay is affected by many factors, including hop
count, link quality, congestion level, and scheduling. In
a TDM-scheduled network, hop count determines the
minimum delay of a packet: if a route has n hops, then
the packet delay is at least n time slots. Therefore, it is
necessary to eliminate extra-long candidate routes for
each s-d pair when delay is a concern. In this section, we
discuss p-TORS, a modified TORS with preprocessing to
eliminate extra-long routes.
PERFORMANCE EVALUATION
Simulation Setup
We use Qualnet [17] for performance evaluation. Qualnet
is a commercial wireless-network simulator that provides
good PHY layer modeling as well as upper-layer
protocol implementations. We use 802.11b PHY layer.
The data rate is 11 Mbps. Every node uses the same
transmission power. The channel model is the 2-ray
path loss model with slow fading. The conflict graph
is measured after the network is setup. For a link A, we
enable all the other links one by one, and measure the
throughput. If the throughput degrades after link B is
enabled, A and B interfere with each other. CBR is used
as the application for each active s-d pair. We use the
maximum possible payload size (i.e., 1500 bytes MAC
layer payload). The traffic demand varies, which will be
explained later in this section. For a multipath routing,
a node splits its traffic among multiple paths based on
the corresponding ratio on each path. We implement
the scheduling using TDMA with fixed length super
frames where each time slot is allocated to a maximal
independent set.
Traffic-Oblivious Routing and Scheduling
We first compare the throughput performance of the four
routing and scheduling schemes discussed in Section 4.1.
Although the objective of our framework is not to maximize
the throughput, we still expect a large throughput
gain over heuristic-based protocols (i.e., shortest path
routing and 802.11 scheduling). The results are tabulated
in Table 1. We only consider w = 1 here. As mentioned
earlier, when w = 1, there is no variation in the traffic
demand, which means that perfect traffic information is
given. In this case, TORS and Estimate both achieve the
same optimal performance. Through this simple case, we
want to show how optimal spatial reuse and scheduling
can improve the performance. Benefiting from optimal
scheduling only, SP+schd achieves 17% and 4%
higher throughput than SP+802.11 under single-sink and
double-sink pattern, respectively. Such gains increase to
57% and 19% under Estimate and TORS, as they benefit
from both the optimal spatial reuse and scheduling.
CONCLUSION
In this paper, we propose TORS, a joint routing-andscheduling
scheme, that achieves robust performance
under traffic information uncertainty. To elaborate, the
proposed scheme optimizes the worst-case performance
(in terms of relative congestion) for a range of traffic
conditions. The proposed scheme works under the whole
spectrum of traffic information uncertainty from perfect
traffic information to no traffic information. The performance
of TORS adapts to the granularity of the traffic
information available. The more accurate the information
is, the better the performance will be. We show that
TORS achieves optimal worst-case performance, as well
as good average performance. The performance of TORS
is robust under traffic dynamics, or even false traffic
information.