36 QUALITY OF SERVICE IN WIRELESS NETWORKS OVER UNLICENSED SPECTRUM
to achieve statistically strong bandwidth guarantees. In Section 3.2, we will discuss a two-tier ap-
proximation algorithm of the rate optimization solver. This algorithm will present the calculation of
the starting rate and distribution of the rate information in wireless 802.11 multi-hop ad hoc net-
works. This algorithm represents actually a solution to the price-based resource allocation problem,
discussed in Chapter 2.3.2. In Section 3.3, we will switch to wireless 802.11 single-hop networks
and explore dynamic bandwidth management to provide statistical bandwidth guarantees. Each sec-
tion will provide also practical comments and insights to support some of the algorithmic work. We
will conclude the chapter in Section 3.4. with the summary and our lessons learned in the area of
bandwidth management.
3.2 PRICE-BASED ALGORITHM FOR RATE ALLOCATION
In this section, we present a decentralized two-tier algorithm that represents a solution to the price-
based resource allocation problem, formulated in Chapter 2. Recall, that we consider a wireless 802.11-
like ad hoc network, where each node forwards packets to its peer nodes, and each end-to-end flow
traverses multiple hops of wireless links from a source to a destination. The unique characteristics of
multi-hop wireless networks, compared to wireline networks, is that flows compete for shared chan-
nels if they are within the interference ranges of each other. This presents the problem of designing
a topology-aware resource allocation algorithm that is both optimal with respect to resource utilization
and its conformation to QoS requirements and fair across contending multi-hop flows.
As we discussed in Chapter 2, there are several important assumptions and models under
which we are considering solving the price-based resource allocation problem and designing the
resource allocation algorithm to achieve optimal rate allocation:
we will assume the protocol model, especially the 802.11 MAC protocol model;
flows f contend for shared wireless resources in a location-dependent manner and create
a wireless link contention graph G
c
, depending on the wireless interference range d
int
and
transmission range d
tx
;
we consider complete subgraphs in G
c
, called cliques, and especially maximal cliques q (it is a
clique that is not contained in any other cliques) because maximal cliques represent a basic
resource unit for defining the optimal resource allocation problem (see Figure 3.1);
we consider rate x
f
of a flow and aggregated rate y
ij
of all subflows along the node i and
node j;
we describe the resource constraints on rate allocation among flows f via clique-flow matrix
R = {R
qf
} and it represents the resource usage pattern;
the overall achievable channel capacity is a vector C = (C
q
, q Q) with C
q
being the achiev-
able capacity in each clique q;
1.
2.
3.
4.
5.
6.
BANDWIDTH MANAGEMENT 37
we consider feasible rate allocation x = (x
f
, f F ) if, and only if, Rx C;
we establish the shadow price m
q
of a maximal clique q, which corresponds to the Lagrange
multiplier of the Lagrangian form of the utility-based resource optimization problem (see
Equation 2.5 in Chapter 2);
the shadow price l
f
of a flow f is the sum of maximal cliques prices m
q
through which the
flow f traverses, i.e.,
f q qf
R
λ µ
=
å
(see Equation 2.8 in Chapter 2);
we are considering the price-based problem description D, presented in Chapter 2.3.2 through
equations 2.6–2.8.
Table 3.1 summarizes the symbols and model definitions from Chapter 2. Detailed summary
of concepts and corresponding definitions can be found in Chapter 2, Table 2.2.
7.
8.
9.
10.
FIGURE 3.1: Wireless Link Contention Graph and Resource Constraints: Example with four flows f
1
,
f
2
, f
3
, f
4
shown in Figure 3.1(a) with network topology of wireless ad hoc nodes; and three cliques q
1
, q
2
,
q
3
for the four flows in Figure 3.1b d
int
= d
tx
and one clique q
1
in Figure 3.1c d
int
= 2*d
tx
[13].
TABLE 3.1: Notations and definitions for Section 3.2.
SYMBOLS DEFINITIONS
G = (V, E), i V; e E;
E={e|e=(i,j), i V; j V, i, j are connected}
V is set of nodes and E set of wireless
links/edges , Node i V, Edge e = (i, j ), G
is a transmission graph
d
tx
, d
int
Transmission range and interference range
f F ; s S E Flow f ; subflow s of flow f
(continued )

Get Quality of Service in Wireless Networks Over Unlicensed Spectrum now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.