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 ﬂow

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 ﬂows 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 ﬂows.

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;

ﬂows 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 deﬁning the optimal resource allocation problem (see Figure 3.1);

we consider rate x

f

of a ﬂow and aggregated rate y

ij

of all subﬂows along the node i and

node j;

we describe the resource constraints on rate allocation among ﬂows f via clique-ﬂow 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 ﬂow f is the sum of maximal cliques prices m

q

through which the

ﬂow 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 deﬁnitions from Chapter 2. Detailed summary

of concepts and corresponding deﬁnitions 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 ﬂows 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 ﬂows 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 deﬁnitions 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 ; subﬂow s of ﬂow 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.