BANDWIDTH MANAGEMENT 41
Step 4: flow f receives clique (channel) prices
q
t( )µ
from all cliques q through which it passes,
where
E f V q( ) ( )Ç ¹ Æ
;
Step 5: flow f calculates shadow price of a flow f :
f q qf
q E f V q
t t R
: ( ) ( )
( ) ( )λ µ
Ç ¹Æ
=
å
;
Step 6: flow f adjusts rate
f f f
x t x t( 1) ( ( ))λ+ =
;
Step 7: flow 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 first 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 efficient clique construction.
We will first 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 significantly
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 sufficient 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.