7.2 The Single Stage Game (SSG) Competition Model

135

For accurate evaluation, they are included in the simulation model where they carry background traffic for applications that require limited QoS support (modeled by Ethernet traffic traces).

7.2.2Action, Action Space A, Requirements vs. Demands

The action defines the actual operation a player performs, based on requirements. A player that attempts to allocate resources must be aware of the fact that there are competing players, i.e., the player’s opponents that also try to meet their individual requirements. An action is taken based on the expected actions of all involved players. The selection process that assigns an action to particular requirements is called the decision-taking process. This decision-taking process implements what is called behavior and strategy, i.e., the way it aims to meet certain requirements. Behaviors are discussed in Section 8.3 as part of the SSG. Strategies are discussed in the context of MSGs in Section 9.1.

Let N be the number of players, in a simplified case, N=2.11 The periodic superframes define discrete time stages numbered by n. In each superframe, i.e., time stage, a player i Ν =1,..., N decides to take an action ai ( n ) , i.e., to select a certain demand, as explained in the following.

7.2.2.1Abstract Representation of QoS

The QoS requirements that are important in the CCHC coexistence problem are (1) the share of capacity that determine any throughput within a QBSS, (2) the resource allocation periods that determines any MSDU Delivery delay within a QBSS, and (3) the variation of the delays of allocated resources. This variation of the delays of allocated resources can be calculated as time derivation of the resource allocation periods. The player’s QoS requirements are taken from the traffic specifications of isochronous MSDU streams that are carried within the QBSS, as well as the HiperLAN/2 activity that a CCHC tries to support. From the perspective of a CCHC, HiperLAN/2 MAC frames are an application that it tries to carry. Here, it is assumed that the way of resource allocation changes slowly in comparison to the speed of the game, i.e., the decision-taking processes. This assumption allows claiming stationarity of the underlying decision processes.

11In this thesis, the CCHC coexistence problem is analyzed for the two player scenario only. In general, the approach taken here can be extended to games with more than two players.

136	7. The Game Model

Three abstract and normalized representations of the QoS parameters are defined in the following.

1.

The normalized

share

of

capacity

Θi( n )

at stage n, a

real

number without dimension, which is required(

Θreqi ) ,

de-

manded(

Θdemi ( n )) , or observed

(

Θobsi ( n )) by a player i. See

Section 7.2.2.2 for the definition of

QoS demand. It is always as-

sumed that the QoS requirements stay constant throughout the

game,

therefore,

the

requirement Θreqi

is

not

dependent

on

n. Θi ( n ) [ 0...1] ,

where

the

extreme cases

Θi ( n ) = 0

and

Θi ( n ) =1

mean the full deferral of resource allocation throughout

the game stage n and the complete allocation of

all resources of

game stage n, respectively.

2.

The normalized resource allocation period ∆i( n )

, i.e., the time

between the starting points of two consecutive resource allocations

at stage n, a real number without dimension, which also can be re-

quired(

∆reqi ) , demanded(

∆demi

( n )) , or observed

( ∆obsi ( n ))

by a player i. Again, the requirement ∆reqi

is not dependent on n. As

before, ∆i( n ) = [ 0...1]

. With ∆i( n ) →0 ,

the

number of

re-

source allocations increases, and with ∆i( n ) =1 , only one resource

allocation per game stage n is allocated. As part

of

the realistic

models, a minimum number of TXOPs per superframe is required,

which

means

that

∆i( n ) < 0.1

in

all

stages.

However,

∆i( n ) >ε > 0 in all stages, with ε

being defined by the precision

of the medium access, which is in this thesis determined through

the value of aSlotTime (9 µs in the 5 GHz wireless LAN 802.11a).

Typically, ε = 9 µs /SFDUR = 4.5 10

−5 when SFDUR = 200ms .

3.

The normalized delay variation Ξobsi

( n ) at stage n, a real num-

ber without dimension, which is observed, but never demanded. An

upper bound for the tolerable variation can be given as requirement.

Here, delay means the delay of a resource allocation, which is re-

lated to the common definition of

delay, for example the MSDU

Delivery delay in 802.11, but is not the same.

7.2 The Single Stage Game (SSG) Competition Model				137
The normalized QoS is represented through three real numbers,
	Θ = [ 0...1]
QoS		∆ = [ 0...1]		,
		Ξ = [ 0...1]

where Ξ is an optional parameter as explained below. All three parameters can have values between 0 and 1, without dimensions. The definitions of the QoS parameters Θ, ∆,Ξ are given with the following Equations (7.1)…(7.5).

The parameter Θi( n ) represents the share of capacity a player i requires, demands, or observes at game stage n:

			1	Li ( n )
	Θi( n ) =			∑ dli ( n ) ,	(7.1)
		SFDUR( n )
				l =1
	where Li ( n ) is the number of		allocated TXOPs of		player i per game stage n,

and SFDUR(n) the duration of the superframe in ms within this stage. Note that this value is assumed to remain constant throughout all games, in this thesis. A typical value for the SFDUR is 200 ms. The parameter dli ( n ) describes the length of resource allocation l (duration of TXOP l) of player i at stage n, l=1...Li , given in ms.

The parameter ∆imax ( n ) specifies the resource allocation period between subsequent resource allocations of one player i (TXOPs allocated by one player that follow each other), that a player i attempts to get allocated at game stage n:

	∆i		( n ) =		1	max Di ( n )			,	(7.2)
								i
	max				SFDUR( n )	l
								l =1...L ( n )−1
where Di ( n ) = t i		+1		( n ) −t i ( n ) is the time between the starting points of the two
l	l				l

TXOPs l and l+1 of player i in superframe n, again measured in ms. Note that

Di	i ( n ) = t i	( n +1) −t i i ( n ) exceeds the superframe n. In particular, this parame-
L	1	L
ter is related to the expected maximum delay of MSDU Deliveries.
The mean delay per game stage n for player i, i.e., ∆imean ( n ) , is defined as
			1	Li	( n )−1
		∆imean ( n ) =			∑ Dli ( n ) .	(7.3)
			SFDUR( n ) ( Li ( n ) −1)
					l =1

Note that in this equation, the last resource allocation interval of stage n is not considered, as it is exceeding the superframe, and thus is dependent on duration of the beacon that is transmitted at the beginning of the next frame.

138	7. The Game Model

The third QoS parameter that is an optional part of the model represents the maximum tolerable delay variation of the resource allocation times for player i. It is defined as

Ξi

( n ) =

1

max

Di ( n ) −Di

+1

( n )

,

(7.4)

max

SFDUR( n )

l

l

l =1...Li ( n )−1

and given in ms.

For the sake of completeness, the mean delay variation, also referred to as jitter, is defined as

Ξim ean ( n ) =	1	Li ( n )−1		Dli ( n ) −Dli +1( n )
		∑				.	(7.5)
	SFDUR( n ) ( Li ( n ) −1)
		l =1

The variation of the delays of allocated resources can be interpreted as time derivation of the resource allocation period. The focus of interest in the coexistence problem is a predictable support of QoS. Therefore, the maximum instead of the mean values of ∆ and Ξ are used and evaluated in the following:

∆i ( n ) :

!= ∆imax ( n ), Ξi ( n ) :

!=Ξimax ( n ) .

Figure 7.2 illustrates how the three QoS parameters, the share of capacity Θ , the resource allocation period ∆ , and the delay variation Ξ are related to the actual allocations within an SSG. In the example, some allocations of CCHC 2 are delayed due to the busy channel through earlier resource allocations. Note that the parameter Θ can only be observed, but is never demanded.

While the SSG is discussed in the rest of this section, attention to the index n is only paid where necessary. The QoS parameter Ξ is not used for determining an actual demand of a player. Further, the decision-taking processes that will be defined later do not consider this parameter. Only a maximum tolerable delay will be part of the game model.

SFDUR[ms] = superframe duration

1	related to
related to ∆obs	1
	Θobs

allocations by player 1 at the demanded points of time

allocated by CCHC1

delayed	delay
allocation

time

	allocated by
delay	CCHC2
related to ∆obs2	allocations by player 2 at
	demanded points in time

Figure 7.2: Illustration of the QoS parameters and their relation to the resource allocations.

7.2 The Single Stage Game (SSG) Competition Model

139

Despite this maximum tolerable delay, the QoS parameter Ξ is neglected in the following for the sake of readability. The parameters Li , Di , d i determine the times of the resource allocations of player i. They are illustrated in Figure 7.1. It is possible to express these parameters as functions of the QoS parameters:

	1
Li =			, ∆i > 0;
	∆i
Di = SFDUR ∆i ;				(7.6)
d i = SFDUR Θi ∆i .

The operator rounds to the nearest integer towards plus infinity. This operator is neglected in the following for the sake of analytical tractability of the model. Any value L>0 is allowed in the analytical model (this model is introduced in Chapter 8, p. 159). In real life and simulation, integer values are used only, i.e., L 1, 2,3,... .

7.2.2.2Definition of Action; Required, Demanded, and Observed QoS parameters Θ, ∆

Using the abstract QoS parameters, it is possible to define what is called an action ai ( n ) of player i at stage n. A player i takes its action ai ( n ) at the beginning of an SSG with the purpose to achieve in this SSG the level of QoS that is required. This requirement is not dependent on the stage n of the game and given by the QoS requirement ( Θreqi , ∆reqi ) of a player i.

An action is the selection of a set of QoS parameters that determine the resource allocations in this SSG. The selected QoS parameters are called the QoS demand

( Θdemi ( n ), ∆demi ( n )) of a player i and may vary significantly from the player’s QoS requirement. As an outcome of an SSG, the resulting QoS parameters are called

the QoS observations ( Θobsi ( n ), ∆obsi ( n )) of a player i.12 Demand and observation change dynamically in repeated SSGs and are therefore depending on the

12This violates the terminology of game theory. The results of a game are usually referred to as “outcome” instead of the here used term “observation”. In this thesis, “observation” is used as synonym for “outcome” to highlight the wireless characteristic of the game. What is an outcome in a game of two players may be partially observed by other players that are located in the same area. These other players are not part of the game as it is defined here, but may face their own coexistence scenario in the near vicinity. From a cellular perspective on coexisting networks, the games that are developed in this thesis may be extended to models of societies of a large number of interacting individuals. Then, outcomes may be observed by neighbors, which is the motivation for referring to the game results as “observation” rather than “outcome”.

140	7. The Game Model

stage n. The action of a player is to determine the QoS demand taking into consideration its QoS requirement, the estimated demands of the opponent player -i,

( Θdem−i ( n ), ∆dem−i ( n )) , and the history of observations, here the observations of the previous stage n-1, i.e.,( Θobsi ( n −1), ∆obsi ( n −1)) . The superscript “~” indicates that the demands of any opponent player -i are not known to a player i, but esti-

mated from the history of observations.

Note that optimizing the estimation accuracy by taking into account a long history of past stages is out of the scope of this thesis.

An action of player i at stage n is formally defined as

Θi

( n )

Θreqi

Θi

( n −1)

Θ−i

( n )

→ ai( n ), ai Ai , (7.7)

dem

:=

,

obs

,

dem

i

i

i

( n −1)

−i

∆dem

( n )

∆req

∆obs

∆dem

( n )

where Ai is an infinite set of actions out of which a player i selects its action. This set represents a domain of an infinite number of alternatives from which a player selects an action. Player i selects its action out of Ai , player -i selects its action out of A−i . In accordance with the notation in literature, the index -i refers to the opponent of a player i. Possible actions are taken from intervals of real numbers,

Θ = [ 0...1]				, i Ν .	(7.8)
ai Ai =	∆ = [ 0...0.1]

The set of actions	Ai is a single coherent13 subset of		2 , and it is thus an
Euclidean space of	two dimensions, Ai	2 . The set of actions Ai is infinite
and nonempty because it allows an uncountable number of actions.
The set of actions	Ai is further defined as being (i) compact and (ii) convex as
explained in the following. To (i): the set		Ai is compact if	any sequence in this

space has a subsequence that converges to a limit point, which is a member of

the set		Ai	(Bronstein and Semendjajew 1992). In other words, the bounds of
the set		Ai	are members of Ai , and Ai			describes one single coherent subset
of	2 . This is true for the set of actions					Ai	defined in Equation (7.8). To (ii):
the	set	Ai	is convex	if, for any	ai ,bi Ai		and any real	numberα ( 0,1) ,
( α ai +(1 −α) bi ) Ai				(Bronstein	and	Semendjajew 1992).		In other words,

Ai has the property that all points lying at the line joining any pair of two points

13If any two arbitrary points of member of S, then the set S

a set S n can be connected through a curve that is completely a is said to be coherent.

7.2 The Single Stage Game (SSG) Competition Model						141
of	Ai are all members of		Ai (Green and Heller 1981:37). This is true for the
set of actions Ai		defined in Equation (7.8).
Let
			Α =×	i N	Ai , i Ν	(7.9)
be	the Cartesian	product	(or direct product) of all N			sets of actions,

here N=2 14. Note that in the following, games with two players are considered. The outcome of the game at stage n, i.e., the observations, are the result of the resource allocation process throughout the superframe at stage n. This stochastic process can be analytically described and simulated with the simulator YouShi, see Appendix B. In general,

	Θi	( n )	Θ−i	( n )			Θi	( n )	(7.10)
	dem	,	dem				obs	,
	i		−i				i
	∆dem	( n )	∆dem	( n )			∆obs	( n )

which depends on the demands of all involved players i, -i at stage n. An analytical approximation of the resource allocation process of two interacting players is developed for the equilibrium analysis and described in Chapter 8. The following Figure 7.3 illustrates the concept of requirement, demand, and observation as well as the decision taking process of a player i in repeated SSGs.

The requirement of player i in all stages is given by the QoS a player i is trying to achieve. This requirement does not change throughout the repeated games. Player i selects its demand at stage n as part of its action within the SSG n.

The demand is calculated based on the estimated demand of the opponent player -i, which is derived from the history of past observations. The observation, i.e., the outcome of an SSG n, is used to calculate the demand of the SSG n+1. In Figure 7.3, the label “z-1” denotes a time shift of one stage duration. Here, the outcome of a single previous stage n is used by the player at a particular stage n+1 to determine what action to take at this stage n+1.

14 The	Cartesian	product	(or	the	direct	product)	is	defined	as
Ai × A−i ={(a,b ) : a Ai and b A−i } . Α denotes therefore a subset of an Euclidean space of
four dimensions, A		4 , as a = (Θi , ∆i ) , and b = (Θ−i , ∆−i ) .