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

1

,

f

2

, f

3

, and f

4

(e.g., ﬂow f

4

goes from node 5 to node 4). The corresponding wireless link contention

graph for the Figure 2.3a ﬂows 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 ﬂows 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 subﬂows 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 ﬂow f

1

, x

2

being the rate of ﬂow f

2

and

x

3

being the rate of ﬂow 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 ﬂows 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 ﬂows 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 ﬂow 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 ﬂows 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 deﬁnitions 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 deﬁned 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.