BANDWIDTH MANAGEMENT 41

Step 4: ﬂow f receives clique (channel) prices

q

t( )µ

from all cliques q through which it passes,

where

E f V q( ) ( )Ç ¹ Æ

;

Step 5: ﬂow f calculates shadow price of a ﬂow f :

f q qf

q E f V q

t t R

: ( ) ( )

( ) ( )λ µ

Ç ¹Æ

=

å

;

Step 6: ﬂow f adjusts rate

f f f

x t x t( 1) ( ( ))λ+ =

;

Step 7: ﬂow f sends rate updates

f

x t( 1)+

to all cliques q through which f passes, where

E f V q( ) ( )Ç ¹ Æ

.

This algorithm iteratively converges to optimal (price, rate) allocation. The detailed proof can

be found in Reference [13].

3.2.2 Decentralized Clique Construction

The ﬁrst tier treats maximal cliques as entities that are able to perform communication and compu-

tation tasks. Obviously, these tasks need to be performed by the network nodes that constitute the

maximal clique. As a starting point, the second tier requires a decentralized algorithm to construct

maximal cliques. We will utilize the unique graphical properties of the wireless link contention

graph to facilitate efﬁcient clique construction.

We will ﬁrst decompose the wireless ad hoc network topology into overlapping subgraphs, and

maximal cliques are constructed based only on local topological information within each of the

subgraphs. Since only wireless links that are geographically close to each other will form an edge in

the wireless link contention graph, the communication and computation overhead is signiﬁcantly

reduced (an example of such decomposed subgraphs is in Figure 2.2, Chapter 2). It means, after

we decompose wireless networks into subgraphs, maximal cliques will be constructed within the

subgraphs based on local, wireless, and topological information. We will denote the maximal clique

that contains wireless link

s SÎ

as q(s) and the set of all maximal cliques that contain the wireless

link s as Q(s) = {q(s)}. For example, in Figure 3.1b, with d

int

= d

tx

, for a wireless link s = {1,2}, the

set of maximal cliques is Q(s) = Q({1,2}) = {q

1

}, and for a wireless link s = {3,2}, the set of maximal

cliques is Q({3,2}) = {q

1

, q

2

, q

3

}. It can be shown that the contention graph G

c

[V

c

(s), E

c

] with V

c

(s)

being a wireless link two-hop neighbor set contains sufﬁcient and necessary topological information

to construct Q(s) when d

int

= d

tx

; and G

c

[V

c

(s), E

c

] contains necessary topological information to

construct Q(s) when d

int

> d

tx

[13].

The cliques in Q(s) set are constructed by one of the vertices of s which is selected as its del-

egation node, denoted as v(s). Then the delegation node v(s) uses a clique-construction algorithm, for

example, the Bierstone algorithm [16, 98] or Dharwadker’s algorithm [97] to construct all maximal

cliques

q Q s( )Î

on graph G

c

[V

c

(s), E

c

]. We describe the clique-construction algorithm by Dhar-

wadker [97], using our notation in Table 3.1 and show on the example from Figure 3.1b the con-

struction of one maximal clique q

1

. One can follow the same algorithm to construct other cliques q

2

and q

3

in Figure 3.1b. Note that Dharwadker [97] also includes correctness proofs, implementation

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.