. Delay
Analysis and Optimality of Scheduling Policies for Multi-Hop Wireless Networks
Abstract
We analyze the
delay performance of a multi-hop wireless network in which the routes between
source-destination pairs are fixed. We develop a new queue grouping technique
to handle the complex correlations of the service process resulting from the
multi-hop nature of the flows and their mutual sharing of the wireless medium.
A general set based interference model is assumed that imposes constraints on
links that can be served simultaneously at any given time. These interference
constraints are used to obtain a fundamental lower bound on the delay
performance of any scheduling policy for the system. We present a systematic
methodology to derive such lower bounds. For a special wireless system, namely
the clique, we design a policy that is sample path delay optimal. For the
tandem queue network, where the delay optimal policy is known, the expected
delay of the optimal policy numerically coincides with the lower bound. The
lower bound analysis provides useful insights into the design and analysis of
optimal or nearly optimal scheduling policies.
Existing
System
A large number of studies
on multi-hop wireless networks have been devoted to system stability while maximizing
metrics like throughput or utility. These metrics measure the performance of a
system over a long time-scale. For a large class of applications such as video
or voice over IP, embedded network control and for system design; metrics like
delay are of prime importance. The delay performance of wireless networks,
however, has largely been an open problem. This problem is notoriously
difficult even in the context of wireline networks, primarily because of the
complex interactions in the network (e.g., superposition, routing, departure,
etc.) that make its analysis amenable only in very special cases like the
product form networks. The problem is further exacerbated by the mutual
interference inherent in wireless networks which, complicates both the scheduling
mechanisms and their analysis. Some novel analytical techniques to compute
useful lower bound and delay estimates for wireless networks with singlehop
traffic were developed in. However, the analysis is not directly applicable to
multi-hop wireless network with multihop flows, due to the difficulty in
characterizing the departure process at intermediate links. The metric of
interest in this paper is the system-wide average delay of a packet from the
source to its corresponding destination. We present a new, systematic
methodology to obtain a fundamental lower bound on the average packet delay in
the system under any scheduling policy. Furthermore, we re-engineer well known
scheduling policies to achieve good delay performance viz-a-viz the lower bound.
Proposed
System
We analyze a multi-hop
wireless network with multiple source-destination pairs, given routing and
traffic information. Each source injects packets in the network, which
traverses through the network until it reaches the destination. For example, a
multi-hop wireless network with three flows is shown in Fig. 1. The exogenous
arrival processes AI (t), AII (t) and AIII (t) correspond to the number of
packets injected in the system at time t. A packet is queued at each node in
its path where it waits for an opportunity to be transmitted. Since the
transmission medium is shared, concurrent transmissions can interfere with each
others’ transmissions. The set of links that do not cause interference with
each other can be scheduled simultaneously, and we call them activation
vectors (matchings). We do not impose any a priori restriction on the set
of allowed activation vectors, i.e., they can characterize any combinatorial
interference model. For example, in a K-hop interference model, the links scheduled
simultaneously are separated by at least K hops. In the example show in Fig. 1,
each link has unit capacity; i.e., at most one packet can be transmitted in a
slot. For the above example, we assume a 1-hop interference model.
No comments:
Post a Comment