24 QUALITY OF SERVICE IN WIRELESS NETWORKS OVER UNLICENSED SPECTRUM
2.2.3 Integrating Example
We present another example in Figure 2.2 [13] to illustrate all the concepts together as discussed
in Sections 2.2.1. and 2.2.2. Furthermore, in Table 2.2, we will summarize all concepts in a tutorial
manner.
Figure 2.3a shows the topology of the wireless ad hoc network as well as the ongoing flows f
1
,
f
2
, f
3
, and f
4
(e.g., flow f
4
goes from node 5 to node 4). The corresponding wireless link contention
graph for the Figure 2.3a flows and topology is shown in Figure 2.3b. In Figure 2.3b, we assume
that the interference range d
int
is the same as the transmission range d
tx
(d
int
= d
tx
). In Figure 2.3c,
we show the link contention graph when the interference range is twice as large as the transmission
range (d
int
= 2*d
tx
).
In this example, there are four end-to-end flows f
1
= {{1,2}, {2,3}, {3,4}, {4,5}}, f
2
= {{7,6},
{6,3}}, f
3
= {{6,3}, {3,2}, {2,1}}, and f
4
= {{5,4}}. In Figure 2.3b, there are three maximal cliques in
the contention graph: q
1
= {{1,2}, {3,2}, {3,4}, {3,6}}, q
2
= {{3,2}, {3,4}, {4,5}, {3,6}}, and q
3
= {{3,2},
{3,4}, {3,6}, {6,7}}. In Figure 2.3c, there is only one maximal clique q
1
= {{1,2}, {3,2}, {3,4}, {3,6},
{4,5}, {6,7}} because d
int
= 2*d
tx
.
We use y
ij
to denote the aggregated rate of all subflows along wireless link {i,j}. For example,
y
12
= x
1
+ x
3
, y
36
= x
2
+ x
3
with x
1
being the individual rate of flow f
1
, x
2
being the rate of flow f
2
and
x
3
being the rate of flow f
3
. In each clique, the aggregated rate may not exceed the corresponding
channel capacity. In particular, when d
int
= d
tx
, then
FIGURE 2.3: Wireless Link Contention Graph and Resource Constraints: Example with four flows f
1
,
f
2
, f
3
, f
4
shown in Figure 2.2a network topology of wireless ad hoc nodes; and corresponding cliques for
the four flows in cases Figure 2.2b d
int
= d
tx
and Figure 2.2c d
int
= 2*d
tx
[13].
QOS-AWARE RESOURCE ALLOCATION 25
y
12
+ y
32
+ y
34
+ y
36
C
1
;
y
32
+ y
34
+ y
45
+ y
36
C
2
;
y
32
+ y
34
+ y
36
+ y
67
C
3
;
when d
int
= 2*d
tx
, then y
12
+ y
32
+ y
34
+ y
45
+ y
67
C
1
'.
When it comes to end-to-end flow rate allocation, the resource constraint imposed by shared
wireless channels is as follows. When d
int
= d
tx
,
3 1 3 0
3 1 2 1
2 2 2 0
x C
æ ö
ç ÷
£
ç ÷
ç ÷
è ø
and when d
int
= 2*d
tx
, then (4 2 3 1) C
'.
As we can see, the unique characteristics of location-dependent contention in wireless ad hoc
networks imply a fundamentally different resource model compared to the case of wireline networks.
In wireline networks, the capacity of a link represents the constraints on flows contending for its
bandwidth which is independent from other links. However, in case of wireless ad hoc networks,
the capacity of a wireless link is interrelated with other wireless links in its neighborhood. This
strong interference and dependency must be taken into account with respect to models of resource
constraints and allocations in wireless networks as we show in Section 2.3, discussing utility-based
description and price-based description of optimal resource allocation. In Table 2.2, we summarize
concepts and the corresponding definitions used in this chapter.
TABLE 2.2: Glossary of concepts.
CONCEPT DEFINITION
Clique In an undirected graph, a complete subgraph is called a clique, i.e., a
subset of its vertices form a clique if every two vertices in the subset are
connected by an edge
Maximal clique A maximal clique is defined as a clique that is not contained in any other
cliques, i.e., it is a clique that cannot be extended by including one more
adjacent vertex
(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.