A Game-Theoretic Framework for Medium Access Control
A Game-Theoretic Framework for Medium
Access Control
Tao Cui,Lijun Chen,Member,IEEE,and Steven H.Low,Fellow,IEEE
Abstract—In this paper,we generalize the random access game model,and show that it provides a general game-theoretic framework for designing contention based medium access control.We extend the random access game model to the network with multiple contention measure signals,study the design of random access games,and analyze different distributed algorithms achieving their equilibria.As examples,a series of utility functions is proposed for games achieving the maximum throughput in a network of homogeneous nodes.In a network with n traf?c classes,an N-signal game model is proposed which achieves the maximum throughput under the fairness constraint among different traf?c classes.In addition,the convergence of different dynamic algorithms such as best response,gradient play and Jacobi play under propagation delay and estimation error is established.Simulation results show that game model based protocols can achieve superior performance over the standard IEEE802.11DCF,and comparable performance as existing protocols with the best performance in literature.
Index Terms—Medium access control,Random access game, Nash equilibrium,Distributed strategy update mechanism,Wire-less LANs.
I.I NTRODUCTION
W IRELESS channel is a shared medium that is interference-limited.A contention-based medium ac-cess control(contention control)is a distributed strategy to access and share a wireless channel among competing wireless nodes.It dynamically adjusts channel access probability in response to the amount of contention in the network.Note that the amount of contention itself depends on the channel access probabilities chosen by the wireless nodes.Hence contention control is an iterative feedback system described mathematically as:
p i(t+1)=F i(p i(t),q i(t)),q i(t)=G i(p(t)),(1) where p i(t)is the channel access probability of node i, p(t)={p i(t)}is the corresponding vector,q i(t)is a vector of certain measures of contention observed by node i that depends on the vector p(t).The channel access probability p i(t)is usually implemented either through a backoff algo-rithm on contention window or as a persistence probability. For example,the standard IEEE802.11DCF has a backoff algorithm that induces a channel access probability and can Manuscript received August15,2007;revised March10,2008.This work has been supported in part by NSF grants CNS-0435520and CNS-0520349, and Caltech’s Lee Center for Advanced Networking.This paper has been presented in part at the International Wireless Internet Conference,October 2007,Austin,Texas,USA.
T.Cui,L.Chen and S.H.Low are with the Division of Engineering and Applied Science,California Institute of Technology,Pasadena,CA91125, USA(e-mail:{taocui@,chen@cds.,slow@}https://www.wendangku.net/doc/f712697189.html,).
Digital Object Identi?er10.1109/JSAC.2008.080909.be modeled by some function F i.The algorithm responds
to whether there is a collision,and hence the measure of contention q i(t)in DCF is the probability of collision whose
dependence on the channel access probability vector p(t)can
be modeled by some function G i.
The performance of a MAC,e.g.,the throughput,fairness
and collision,depends critically on the equilibrium and sta-bility of the dynamical system de?ned by(1).In[1],[2],
Chen et al.propose a general game-theoretic model,called
random access game,to understand the dynamical system (1)for the network where each node i observes a single
contention measure q i,and use it to guide the design of
new medium access protocols.The key idea of the random access game model is to consider each node i to have a
utility function U i(p i)as a function of its channel access probability p i.The goal of node i is to maximize its payoff
function u i(p):=U i(p i)?p i q i given the contention measure q i.Hence,the steady state properties of a MAC can be analyzed or designed through the speci?cation of the utility
function U i(p i)and the choice of contention measure q i(e.g.,
collision probability,or idle time between channel access,etc). Their speci?cation de?nes the underlying random access game whose equilibrium determines the steady state properties such as throughput,fairness and collision of the MAC.The adap-tation of channel access probability can be speci?ed through (F,G)and corresponds to different strategies to approach the equilibrium of the game.
In this paper,we extend the random access game model to the network where each node can observe multiple contention measure signals q i,study the design of random access games, analyze distributed algorithms achieving their equilibria,and show that the random access game model provides a general framework for designing contention based medium access con-trol.Speci?cally,in Section III,we describe the generalized random access game model,and provide conditions under which an equilibrium for the game exists and is unique.Sev-eral examples are provided on how to design random access games by forward engineering from desired operating points (e.g.,in terms of some target throughput and fairness)and based on heuristics.A series of utility functions is proposed for games achieving the maximum throughput in a network of homogeneous nodes.In a network with n traf?c classes,an N-signal game model is proposed which achieves the maximum throughput under the fairness constraint among different traf?c classes.Supermodular game is also considered,which guar-antees the existence of Nash equilibrium.Moreover,the best response strategy discussed in Section IV always converges to a Pareto dominant equilibrium of supermodular random access
0733-8716/08/$25.00c 2008IEEE
game.In Section IV,we also consider another two dynamic algorithms to achieve the equilibrium:gradient play and Jacobi play.We show that under mild conditions both algorithms converge to the unique equilibrium.We also establish the convergence of gradient play under propagation delay and estimation error.Due to the approximation made in utility function design,the dynamic algorithms may not converge exactly to the desired operating point.An equilibrium selection algorithm is thus proposed to make these algorithms actually hit the desired point.Simulation results show that game model based protocols can achieve superior performance over the standard IEEE802.11DCF,and comparable performance as existing protocols with the best performance in literature.
II.R ELATED W ORK
There are lots of works on medium access control.Here we only mention a few that are most closely related to this work.Game-theoretic approach has been applied extensively to study medium access,see,e.g.,[1]–[8].Jin et al.[3]study noncooperative equilibrium of Aloha networks and their local convergence.Borkar et al.[5]study distributed scheme for adapting random access.ˇCagalj et al.[6]study sel?sh behavior in CSMA/CA networks and propose a distributed protocol to guide multiple sel?sh nodes to a Pareto-optimal Nash equilibrium.Lee et al.[7],[8]reverse-engineer exponential-backoff-based MAC protocols using a noncooperative game model.
Related work also includes[9]that proposes an idle sense access method without estimating the number of nodes,which compares the mean number of idle slots between transmission attempts with the optimal value and adopts an additive increase and multiplicative decrease algorithm to dynamically control the contention window in order to improve throughput and short-term fairness.However,idle sense method intends to make contention windows equal for all wireless nodes and requires the calculation of optimal average number of idle slots between transmissions.It is not clear how to achieve this with different traf?c classes.A priority-based protocol is proposed in[10]to achieve fairness among?ows of different traf?c classes,which estimates the number of nodes in each class every step and computes the contention window size using these estimates.However,as commented in[11],protocols like that in[10]based on estimating the number of nodes do not converge.
III.G AME-T HEORETIC M ODEL OF C ONTENTION
C ONTROL
A.Random Access Game
Consider a set N of wireless nodes in a wireless LAN with contention-based medium access.In this paper,we consider single-cell wireless LANs,where every wireless node can hear every other node in the network.We assume all nodes always have a frame to transmit,and the network is noise free and packet loss is only due to collision.
In practice,it is hard for wireless nodes to learn the exact channel access probabilities of others.Each node infers the contention of the wireless network through observing certain contention measure signals q i(p),which are functions of the nodes’channel access probabilities.Following[1],[2],we model the interaction among wireless nodes as a random access game.
De?nition1:A generalized random access game G is de?ned as a triple G:={N,(S i)i∈N,(u i)i∈N},where N is a set of players(wireless nodes),player i∈N strategy S i:={p i|p i∈[νi,ωi]}with0≤νi<ωi≤1,and payoff function u i(p)=U i(p i)?p i C i(q i)with utility function U i(p i)and price function C i(q i).
This de?nition of game model is an extension of the basic random access game model proposed in[1],[2],which was de?ned for the network where each wireless node observes a single contention measure q i,to the network where each node can observe multiple contention measure signals q i.The dif-ference is the introduction of a price function C i(q i),instead of adapting directly to a contention measure q i.Although we can reduce the above de?nition to the basic random access game model by de?ning the contention measure q i=C i(q i), the introduction of the price function enables us to give physical interpretation to the contention measure signals.
As shown in[1],[2],random access game is a rather general model for contention control,as it can be reverse-engineered from existing protocols.To see this,note that the equilibrium point of(1)de?nes an implicit relation between channel access probability p i and contention measure signals q i.If this relation can be written as
C i(q i)=F i(p i),(2) the utility function of each node i is de?ned as
U i(p i)=
F i(p i)d p i.(3) Therefore,we can reverse engineer medium access control protocols and study them in game theoretic framework: medium access control can be interpreted as a distributed strategy update algorithm to achieve the equilibrium of the random access game.
In random access game,one of the most important questions is whether a Nash equilibrium exists or not.Denote the channel access probability for all nodes but i by p?i:= (p1,...,p i?1,p i+1,...,p|N|),and write(p i,p?i):=p.We have the following de?nition of Nash equilibrium[12].
De?nition2:A channel access probability vector p?is said to be a Nash equilibrium if no node can improve its payoff by unilaterally deviating from Nash equilibrium,i.e., u i(p?i,p??i)≥u i(p i,p??i),?p i∈S i.A Nash equilibrium p?is a nontrivial equilibrium if p?i satis?es
?
?p i
u i(p?i,p??i)=0,?i∈N.(4)
The reason to consider nontrivial Nash equilibrium is to avoid those equilibria in which some player takes strategy at the boundary of the strategy space,which usually results in great unfairness or low payoff.
Throughout this paper,we will only consider those con-tention measure signals that can be described by q i=G i(p?i). To facilitate analysis in the following,we list the assumptions that will be used in this paper.
A1:The utility function U i(·)is twice continuously dif-ferentiable,strictly concave and increasing,with?nite
curvatures bounded away from zero,i.e.,there exist some
positive constants μand χsuch that 1μ≥?1/U i (p i )≥1
χ.
A2:The inverse function (U i )?1
(C i (q i ))maps any q i into a point within S i for all i ∈N .
A3:At a nontrivial Nash equilibrium p ?,there exists a function Φi (p i )for each node i such that Φi (p ?i )=
Φj (p ?
j ),?i,j ∈N and Φi (p i )is strictly monotone in S i ,?i ∈N .
These assumptions are similar to those speci ?ed in [1],[2],and similarly,the following results are immediate.
Theorem 3:Under assumption A1,there exists a Nash equilibrium for any random access game G .
Theorem 4:Suppose A2holds.Random access game G has a nontrivial Nash equilibrium.
Theorem 5:Suppose that A1and A3hold and random ac-cess game G has a nontrivial Nash equilibrium.If additionally for all i ∈N ,C i (q i (p ))is strictly increasing in p ,then G has a unique nontrivial Nash equilibrium.
Since the equilibrium determines the operating point of medium access control,it is desired to have a unique nontrivial Nash equilibrium.Theorem 5guarantees the uniqueness of nontrivial Nash equilibrium.This will facilitate the design of medium access methods.B.Utility Function Design
As shown in the last subsection,random access game can be reverse engineered from the exiting protocols.An example of reverse-engineering the IEEE 802.11DCF was given in [1],[2].In the following,we give several examples to show how to design utility functions and random access games by forward engineering from desired operating points and based on heuristics.
1)Forward Engineering from Desired Operating Points:A System of Homogeneous Nodes:In [9],a medium access method is proposed by using the mean number of idle slots between transmission attempts.Let T c denote the average collision duration and T SLOT denote the slot duration.It is derived in [9]that when the number of users in the network |N |→∞,the throughput-optimal number of idle slots between two transmission attempts is
ˉn opt
i ∞=
e ?ξ1?e ?ξ
,(5)where ξsatis ?es 1?ξ=ηe ?ξand η=1?T SLOT /T c .Note that ˉn opt i ∞is completely determined by the protocol parameters but not by the number of nodes in the network.Let q i :=1? j ∈N /{i }(1?p j ).The probability of an idle slot is
(1?p i )(1?q i )=ˉn opt i ∞
ˉn opt i ∞+1
=e ?ξ.
(6)Applying (3)with C i (q i )=q i ,we obtain the utility function as
U i (p i )=p i +e ?ξlog(1?p i ).
(7)Note that U i (p i )does not satisfy A2but clearly the random
access game with utility (7)has a nontrivial Nash equilibrium.This also shows the limitation of Theorem 4.Utility (7)does not satisfy Theorem 5.In fact,there exist in ?nite number of equilibria for the game with (7).To design a game with unique equilibrium,we note that when |N |is large the optimal
attempt probability that maximizes the throughput is very small as shown in [9].We thus have
(1?p i )α(1?q i )=(1?p i )α?1e ?ξ≈e ?ξ,
(8)
where α>1and the approximation holds when αis not very large.Applying (3),we obtain the utility function as U i (p i )=p i +
e ?ξ
1?α
(1?p i )1?α.(9)Note that (9)still does not satisfy A2.But at least one non-trivial Nash equilibrium exists,i.e.,p ?i =1?e ?ξ/(α+|N |?1).De ?ne Φi (p i )=(1?p i )(1?U i (p i ))=e ?ξ
(1?p i )α?1,which is strictly increasing in p i when α>1.Also q i (p )is strictly increasing in p .By Theorem 5,the random access game G has a unique nontrivial Nash equilibrium.Note that due to the approximation made in (8),the equilibrium point obtained by (9)may not achieve the optimal number of idle slots ˉn opt i ∞.We will discuss in Section IV-D how to design equilibrium selection algorithm such that the equilibrium point by using (9)can actually hit ˉn opt i ∞.
A System of Heterogenous Nodes:We have considered the network with a single traf ?c class.We now consider a network with n >1different traf ?c classes as in [10].Let φi denote the weight associated with class-i traf ?c and f i denote the set of nodes carrying class-i traf ?c,1≤i ≤n .Without loss of generality,we assume that 1=φ1>φ2>···>φn >0and each wireless node carries only one class traf ?c.At equilibrium,to achieve the desired fairness among the nodes carrying the same traf ?c class,say class i ,the channel access probabilities of these nodes must be equal,denoted as p i .To achieve the desired fairness among different traf ?c classes,we must have [10]
p i (1?p j )φi =p j (1?p i )φj
,1≤?i,j ≤n.(10)The probability of a successful transmission from any node carrying class-i traf ?c is
P ti =|f i |p i (1?p i )|f i |?1
j =i
(1?p j )|f j |,(11)
and the probability of an idle slot is
P I = i
(1?p i )|f i |.
(12)
The optimal channel access probability of each node can be
obtained by maximizing the throughput subject to the fairness constraint (10).As shown in [10],it is dif ?cult to maximize the throughput directly.We instead consider the case that all |f i |are large.Let |f i |p i =ξi and ξ= n i =1ξi .By following similar argument as in [9],we ?nd that the throughput is maximized when ξis the solution to 1?ξ=ηe ?ξwhere ηis de ?ned as in (5).Note that p i also needs to satisfy (10).When |f i |is large,we use the approximation 1?p i ≈1.Finally,we obtain
ξi =|f i |φi
n
j =1|f j |φj
ξ.(13)
In [10],n +1contention measurements are used:the average number of consecutive idle slots and the average number of time slots between two consecutive successful class-j transmissions,which are equivalent to n +1contention
measure signals q k 0=P I and q ki =P ti ,i =1,...,n ,at node k ∈N .At equilibrium,we have
q ki =|f i |p i (1?p i )|f i |?1
j =i
(1?p j )|f j |≈|f i |p i e ?ξ≈ξi e ?ξ,
(14)and
q k 0
=
i
(1?p i )|f i |≈e ?ξ.
(15)
From (14),we obtain |f i |≈e ξq ik /p i .By using (13)and
assuming p i is small,we obtain
q ki (1?p i )?α≈q ki φi /p i
n j =1q kj φj
/p j q k 0ξ,(16)
where α>0.Applying (3),we obtain the utility function
U ki (p i )=1?φi ξ
α+1
(1?p i )α+1,i =1,...,n,(17)
and the price function
C ki (q k )= n
j =1q kj φj /p j
q k 0/p i
,i =1,...,n,(18)
where q k =[q k 0,q k 1,...,q kn ]T .Note that there are n utility and price functions at each node k .Each node k keeps and updates its own p i ,i =1,...,n ,denoted as p ki .At node k ,p i in (18)actually means p ki .Computing (18)does not require information exchange between nodes.
The game with utility (17)and price (18)does not quite ?t into the random access game model.The Nash equilibrium is not the proper solution concept either.Instead,the nontrivial equilibrium should be de ?ned as those p ?i that satis ?es
??p i
U i (p ?i )=C i (q ?
i ),?i ∈N .(19)
Clearly,there exists a nontrivial equilibrium in the resulting
random access game.We can further show that this nontrivial equilibrium is unique provided that p i <1/|N |,?i ∈N [13].2)Forward Engineering Based on Heuristics:Consider a random access game with the following payoff function
u i (p ):=U i (p i )?p i
j =i
(1?p j )=U i (p i )?p i q i ,(20)where C i (q i )=q i =
j =i (1?p j )is the contention measure signal representing the probability that all nodes except node i do not transmit.This payoff function is motivated by the heuristic that each wireless node should be “charged”according to the throughput it achieves.
It turns out that the random access game with payoff (20)is a supermodular game [14].Supermodular games have many nice properties such as the existence of Nash equilibria and the convergence of the equilibria under different strategy update algorithms.The simplicity of supermodular games makes concavity/convexity and differentiability assumptions unnecessary,though we make such assumptions in this paper.In the setting of random access games,the de ?nition of super-modularity and supermodular game reduces to the following.De ?nition 6:The payoff function u i (p i ,p ?i )has increas-ing differences (supermodularity)in (p i ,p ?i )if for all p ?i ≥
p ?i the quantity u i (p i ,p ?i )?u i (p i ,p
?i )is increasing in p i .For twice differentiable payoffs,supermodularity is equivalent
to ?2
u i (p )
?p i ?p j ≥0for all j =i .
De ?nition 7:A random access game G is supermodular
if for each node i ∈N the payoff function u i (p i ,p ?i )has increasing differences in (p i ,p ?i ).It is easy to verify that ?2u i (p )/?p i ?p j =
j =i,j =j (1?p j )≥0.The following result is immediate [14].
Theorem 8:A random access game G with the payoff function (20)is a supermodular game,and the set of Nash equilibria for G is nonempty.
As indicated by Theorem 8,no concavity/convexity assump-tion on utility function is required to guarantee the existence of Nash equilibria as in non-supermodular games.However,the uniqueness of Nash equilibrium may require stronger condition.Similarly to Theorem 5,we have the following corollary on the uniqueness of equilibrium for supermodular random access games.
Corollary 9:Suppose that utility function U i (·)is twice continuously differentiable,increasing and strictly convex,and the supermodular random access game G with the payoff (20)has a nontrivial Nash equilibrium.If Φi (p i )=(1?p i )U i (p i )is a strictly monotone function in S i ,then G has a unique nontrivial Nash equilibrium.
As an example,we consider the following utility function given in [1],[2]
U i (p i ):=1a i (a i ?1)b i
a i
ln (a i p i ?b i )?p i ,(21)
where 0
(b i a i
,b i +√b 2i +a i (a i b i ?b 2i
?b i )
a i ).It is easy to check that U i (p i )is strictly convex and Φ
i (p i )<0when p i
√b 2i +a i (a i b i ?b 2i ?b i )
a i
.From Corollary 9,the supermodular
game with utility function (21)has a unique nontrivial Nash equilibrium.
There are many ways to design utility functions and random access games.We only show a few examples in this section.The key message is that the random access game model is a rather general construction,as we can derive or design the game by reverse engineering from existing protocols and by forward engineering from desired operating points and based on heuristics.
IV.D YNAMICS OF R ANDOM A CCESS G AME
The dynamic of game studies how players could converge to an equilibrium.It is a dif ?cult problem in general.In random access games,wireless nodes can observe the outcome of the actions of others,but do not have direct knowledge of other nodes’actions and payoffs.We consider repeated play of random access game,and look for distributed strategy update mechanism to achieve the Nash equilibrium.
A.Basic Dynamic Algorithms
1)Best Response:The simplest update mechanism is the best response strategy:at each stage,every node chooses the best response to the actions of other nodes in the previous stage.Let p (0)be the largest vector in the strategy space (S i )i ∈N .At stage t +1,node i chooses a channel access probability
p i (t +1)=B i (p (t )):=max arg max p ∈S i
u i (p,p ?i (t ))
.
(22)
At each stage,if there are more than one best response probabilities,the algorithm (22)always chooses the largest probability.Clearly,if the above dynamics reaches a steady state,this state is a Nash equilibrium.As there is no conver-gence result for general games using this dynamics,we restrict our discussion to supermodular games with payoff (20)in this subsection.We have the following result.
Theorem 10:The best response strategy converges to a Nash equilibrium of random access game G .Moreover,it is the largest equilibrium p in the set of Nash equilibria.
The proof basically follows [14,Lemma 4.1]and the details can be found in [13],[15].If we set p (0)to the smallest vector in the strategy space and always choose the smallest probability,the best response strategy will converge to the smallest equilibrium p .When there exist multiple equilibria,the following theorem indicates that the equilibrium attained by (22)yields the highest aggregate payoff.
Theorem 11:The best response strategy converges to a Pareto dominant equilibrium,i.e.,u i (p )≥u i (p )for all p in the strategy space.
The following result guarantees that the best response converges to a nontrivial equilibrium.
Theorem 12:If the best responses to the smallest and largest vectors in the strategy space are within the strategy space,then nontrivial Nash equilibrium exists.Moreover,the best response strategy (22)converges to the largest nontrivial Nash equilibrium.
The proof of Theorem 11and Theorem 12can be found in [13],[15].By using Theorem 12,it is easy to obtain conditions on a i and b i in (21)such that the best response strategy converges to a nontrivial equilibrium of the corresponding game.
2)Gradient Play:One other update mechanism is gradient play [16].In gradient play,every node adjusts its channel access probability gradually in a gradient direction suggested by contention measure signals.At stage t +1,node i ∈N updates its strategy according to
p i (t +1)=[p i (t )+ i (t )(U i (p i (t ))?C i (q i (p (t ))))]S i ,(23)where the stepsize i (·)>0,[·]S i denotes the projection onto node i ’s strategy space.In the following,We assume that all nodes have the same stepsize i (t )= (t ),?i ∈N .
Theorem 13:Let C (p )=(C i (q i (p )))be a mapping and J C =(J C ij )be the Jacobian of C (p ).Suppose that the smallest
eigenvalue of J C ,λmin (J C ),satis ?es μ+λmin (J C
)>0,max j J C ij 2≤M ,and the random access game has a unique nontrivial Nash equilibrium p ?.The gradient play (23)con-verges geometrically to p ?if the stepsize (t )<μ+λmin (J C )
χ2+|N |M .The proof of Theorem 13is given in Appendix A.Theorem 13also shows the convergence rate of gradient play.As an example of using Theorem 13,we consider the utility function de ?ned in (9).By assuming that all nodes’strategy spaces are identical,i.e.,S i =[ν,ω].In this case,we have μ=
αe ?ξ
(1?ν)α+1,χ=αe ?ξ(1?ω)α+1
.(24)
To ?nd λmin (J C ),we note that
J C (p )=? i
(1?p i )
diag(x )2?xx T ,
(25)
where x =
11?p 1,...,1
1?p |N |
T
.Note that each entry of x is less than
1
1?ω.By using Rayleigh quotient [17],it is easy
to show that the maximum eigenvalue of diag(x )2?xx
T
is
less than 1
(1?ω)2.Thus,Theorem 13requires that λmin (J C )+μ≥?
(1?υ)|N |(1?ω)2+αe ?ξ
(1?ν)α+1
>0.(26)
Condition (26)is mild.For example,if we take ω=2/33and α=2,all ν∈[0,1]satisfy (26).We see that a larger αindicates a larger μ,which means a greater convergence rate by (44).
3)Jacobi Play:Finally,we consider another alternative strategy update mechanism called Jacobi play [18].In Jacobi play,every player adjusts current channel access probability gradually towards the best response strategy.At stage t +1,node i ∈N chooses a channel access probability
p i (t +1)=J i (p (t )):=[p i (t )+ i (t )(B i (p (t ))?p i (t ))]S
i ,(27)where the stepsize i (t )>0and B i (p (t ))is de ?ned in (22).When i (t )=1,we recover the best response strategy.In the case of supermodular game,if i (t )≤1,it is easy to verify that {p i (t )}is a nonincreasing sequence.Thus,Theorem 12still applies to Jacobi play.For general random access games,we can also show the convergence of Jacobi play in the same way as in gradient play,see [13]for details.B.Dynamic Algorithms under Propagation Delay
Due to propagation delay,wireless nodes may use feedback signals generated at different times.In this subsection,we dis-cuss the convergence of the algorithms in Section IV-A under propagation delay.We assume that the contention measure signals that node i uses to update its channel access probability result from the vector
p (τi (t ))= p 1(τi 1(t )),p 2(τi 2(t )),...,p |N |(τi
|N |(t ))
,(28)
where 0≤τi
j (t )≤t denotes the most recent time that node j ’s action affects node i ’s observation,and τi i (t )=t .
1)Best Response:The best response strategy (22)is mod-i ?ed to
p i (t +1)=B i (p (τi (t ))):=max arg max p ∈S i
u i p,p ?i (τi
(t ))
.
(29)
Parallel to Theorem 10,we have the following theorem on the convergence of the best response under propagation delay for supermodular games.
Theorem 14:The best response strategy (29)converges to a Nash equilibrium of the random access game G .Further-more,it is the largest equilibrium in the set of Nash equilibria.
Proof:We show this by induction.Suppose that p (τ+1)≤p (τ),?τ∈{0,...,t ?1}.It is true when t =0as p (0)
is the largest vector in the strategy space.As τi j
(t +1)≥τi j (t ),we have p j (τi j (t +1))≤p j (τi
j (t )).By induction hypothesis,
we get p ?i (τi j
(t +1))≤p ?i (τi j (t )).By supermodularity and [14,Lemma 4.1],we can show that p i (t +1)≤p i (t ).Therefore,the hypothesis is also true when τ=t .By induction,we have
p (0)≥p (1)≥···≥p (t )≥···,
(30)
or {p (t )}is a nonincreasing sequence.The remainder of proof follows that of Theorem 10.
All other results in Section IV-A for best response also hold in the case under delay.
2)Gradient Play:The gradient play (23)is modi ?ed to
p i (t +1)= p i (t )+ i (t ) U i (p i (t ))?C i (q i (p (τi (t )))) S i
.
(31)
Since at each step,nodes update channel access probabilities by a small amount,gradient play is expected to converge if τi j (t )is not far away from t ,?j ∈N .The following result con ?rms this intuition.
Theorem 15:Let C (p )=(C i (q i (p )))be a mapping and J C =(J C ij )be the Jacobian of C (p ).Assume a constant
stepsize i (t )= in (31).Suppose that J C
1≤M 1,max j J C ij 2
≤M 2,and the random access game has a
unique nontrivial Nash equilibrium p ?,and t ?τi
j
(t )≤B with constant B ≥0.The gradient play (31)geometrically converges to p ?if there exists >0and 0<γ<1such that
γ=1?2 μ?M 1 |N |γB + χ2
+M 2|N |2
γB .(32)The proof is given in Appendix B.We can similarly
establish the convergence of the Jacobi play under propagation delay.
C.Dynamic Algorithms under Estimation Error
In this section,we consider dynamic algorithms under esti-mation error.The dynamic algorithms require the information of contention measure signals.In practice,contention measure signals can be estimated via the observation of the wireless medium.As an example,we consider the contention measure –conditional collision probability used in the game for the network of homogeneous nodes studied in Section III-B1.Let n and ˉn denote the number of consecutive idle slots and its mean between two transmissions.As proposed in [1],[2],we can estimate the conditional collision probability by observing the idle period between transmissions:at every ntrans transmissions,each node updates ˉn according to
ˉn ←βˉn +(1?β)isum
ntrans ,where isum is the total number of idle slots during ntrans transmissions,and estimates its con-ditional collision probability according to q i =1?(ˉn +1)p i
(ˉn +1)(1?p i ).Due to the use of estimated contention measure signals,the algorithms in Section IV-A are in fact stochastic algorithms.In the following,we only consider gradient play.The results for Jacobi play can be obtained similarly.We assume that
C i (q i (p (t )))is replaced by ?C
i (q i (p (t )))=C i (q i (p (t )))+w i (t )in (23),where w i (t )is the estimation error.Without loss of generality,we write w i (t )as w i (t )=ˉw i (t )+?w i (t ),where ˉw i (t )=E {w i (t )}can be considered as the deterministic error and ?w i (t )=w i (t )?ˉw i (t )is the stochastic error with zero mean.We further assume that lim t →∞ˉw i (t )=ˉw i .The deterministic error may be caused by the bias of signal esti-mation and carrier sense error due to fading and background noise.For ease of understanding,in the following,we discuss deterministic and stochastic errors separately.The proof of the following theorems can be found in Appendices C,D and E.
Theorem 16:Let λmin (J C
)denote the smallest eigenvalue of J C and max j J C ij 2≤M .Let p ?denote the equilibrium de ?ned by
U i (p ?i )=C i (q i (p ?
))+ˉw
i .(33)
If p ?is within the strategy space and is the unique equilibrium
de ?ned by (33),the gradient play converges to p ?provided
μ+λmin (J C )>0and (t )<μ+λmin (J C )
χ2+4|N |M .
The uniqueness of p ?
can be obtained by using Theorem 5.Note that under certain conditions,by implicit function
theorem [19],(33)de ?nes an implicit function p ?(ˉw
)at the neighborhood of ˉw
=0.Therefore,for any >0,there exists a δ>0such that if ˉw
2<δ, p ?(ˉw )?p ?(0) 2< .So the gradient play converges to a neighborhood of the equilibrium point without errors.
For the stochastic error,we consider gradient play with variable stepsize and constant stepsize,respectively.
Theorem 17:Let λmin (J C )denote the smallest eigenvalue
of J C .Suppose that E {w i (t )}=0,E {w 2
i (t )}≤B ,and
∞ t =0 (t )=∞,∞ t =0
2(t )<∞,e .g ., (t )=1/t.(34)If p ?
is the unique nontrivial Nash equilibrium,the gradi-ent play converges to p ?with probability 1provided μ+
λmin (J C )>0.
Theorem 18:Let λmin (J C )denote the smallest eigenvalue of J C and max j J C ij
2
≤M .Suppose that E {w i (t )}=0,E {w 2
i (t )}≤B ,and (t )= ,?t .If p ?is the unique nontrivial Nash equilibrium,there exists a constant D (B, )>0such that
lim sup t →∞
p (t )?p ? 2≤D (B, )
(35)provided μ+λmin (J C )>0and <μ+λmin (J C
)
χ2+4|N |M .
By combining Theorems 16and 18,we can conclude that with constant stepsize,the stochastic gradient play converges to a neighborhood of the equilibrium point.
D.Equilibrium Selection
The equilibrium attained by using the dynamic algorithms in Section IV-A does not necessarily converge to the desired operating point when the utility functions in Section III-B1are considered.This is because the approximation used in (8).One approach of equilibrium selection is to estimate the number
of users via ?N
=log(1?q i )/log(1?p i )+1at equilibrium and to set the channel access probability to be the optimal
value computed by using ?N
.However,as commented in [11],this approach may not converge due to open loop control.The other approach is to use an outer loop iteration and treat the algorithms in Section IV-A as the inner loop iteration.Take utility function (9)for example.Let τdenote the counter of outer loop iteration and de ?ne the utility function at the τ-th outer iteration as
U i (p i )=p i +
η(τ)
1?α
(1?p i )1?α,(36)with η(0)=e ?ξ.Denote the equilibrium of the game with utility (36)by p (τ).To cancel the effect of neglecting (1?p i )α?1in (8),we do the outer iteration
η(τ+1)=(1?p i (τ))α?1e ?ξ.
(37)
(a)Idle sense (b)Game model
Fig.1.The evolution of channel access probability of idle sense and gradient play of the one-signal game with utility function (9)in a network of 20nodes.
At equilibrium,all nodes have the same access probability,
denoted as p (τ).By (37),we obtain
p (τ+1)=1?
|N |+α?1
(1?p (τ))α?1e ?ξ.
(38)
Let M (p )be the mapping de ?ned by (38).By mean value theorem,it is easy to see
|M (p 1)?M (p 2)|≤
e
?ξ
|N |+
α?1
(α?1)(1?ω)α?1
|N |+α?1?1
|N |+α?1
|p 1?p 2|(39)
Thus,if e ?
ξ
|N |+α?1
(α?1)(1?ω)α?1
|N |+α?1
?1
|N |+α?1
<1,M (p )is a contraction mapping [19]and (38)converges to the unique ?xed point of M (p ),which is the desired operating point.From (39),we can see that a larger αindicates a smaller outer loop convergence rate,while a larger αresults a greater inner loop convergence rate as suggested in Theorem 13.Therefore,there exists an optimal αto achieve the least overall convergence rate.In practice,outer loop iteration can be executed without waiting for the convergence of the inner loop iteration.
V.E XPERIMENTAL R ESULTS
In this section,we run some numerical experiments to compare the performance of different medium access proto-cols.The system parameters are those speci ?ed in the IEEE 802.11b standard with DSSS PHY layer [20],summarized in Table I.The RTS/CTS mechanism is disabled.We consider a single-cell network with perfect wireless channel,i.e.,there is no corrupted frame.In all simulations,the initial channel access probability is set to be 2/33,which corresponds to CW min =32in 802.11b DCF.For our game based protocols,we set ntrans =5and β=0.8.Throughput and fairness are obtained after 106transmissions.A.One-signal Game
We consider the one-signal game with utility function (9)derived in Section III-B1,and compare the performance of the
TABLE I
P ARAMETERS IN SIMULATIONS
Slot Time (T SLOT )20μs
SIFS 10μs DIFS 50μs Basic Rate 1Mbps Data Rate 11Mbps Propagation Delay 1μs
PHY Header 192bits MAC Header 272bits
ACK 112bits
Packet Payload (s d )12000bits
MAC based on this game with that of idle sense protocol in [9].In (9),we choose ξ=0.1622and α=2.The parameters in idle sense are set as those in [9].
Figure 1compares the evolution of channel access proba-bility of idle sense and gradient paly (23)of the one-signal game in a network of 20nodes,where for the gradient play ξ=0.1622,α=2and the stepsize is chosen to be i (t )=0.02.We see even with perfect knowledge of expected number of idle slots,idle sense oscillates around the optimal value.On the other hand,game model achieves a smoother dynamic in both cases with perfect signal and estimated signal.Both algorithms have roughly the same convergence rate.We can clearly see the geometric convergence rate predicted by Theorem 13.The equilibrium by our method is close to the optimal value but not equal due to the approximation in (8).Figure 2compares the throughput of idle sense,the game based design,and DCF with the same parameters as used in Figure 1.We use estimated signals in idle sense and the game based design.When the number of nodes in the network is small,idle sense achieves the highest throughput.Game based design performs worse in this case because the approximation used in (8)is not accurate when the number of nodes is small.The performance of the game based design can be improved by using equilibrium selection algorithm.As the number of users increases,both idle sense and the game based design perform fairly close to the optimal throughput.They achieve a much higher throughput than DCF.This also indicates that
Fig.2.The throughput comparison between idle sense and the MAC based on one-signal game with utility function(9)in a network of20nodes. when the number of users is large,equilibrium selection is not necessary as the achieved throughput by the game based design is already very close to the optimal throughput. Figure3compares the short-term fairness of different pro-tocols using Jain fairness index[21]for normalized window sizes that are multiples of the number of wireless nodes.All parameters are the same as those used in Figure1.We see that both idle sense and the game based design provide much better short-term fairness than802.11b as in both protocols wireless nodes have roughly the same contention window size.
B.N-signal Game
Next,we compare P-MAC protocol proposed in[10]with the MAC based on the N-signal game with utility function (17)and price function(18)derived in Section III-B1.In(17), we chooseξ=0.1622andα=2.The parameters in P-MAC are set as those in[10].
Figure4compares the dynamics of P-MAC and the MAC based on N-signal game in a network of25nodes and two traf?c classes with|f1|=10,|f2|=15and weightsφ1= 1,φ2=0.5.The N-signal game uses gradient play,with
the stepsize i(t)=0.05.The initial value of window size is chosen to be CW min plus a random number between0 and10.We see P-MAC does not converge because it uses open loop control,which agrees with the observation in[11]. On the other hand,the game based design converges to the equilibrium only after10iterations with perfect contention measure signals.Even with estimated signals,the game based design converges to a neighborhood of the equilibrium after 20iterations.In Figure4,we also show the optimal channel access probability that achieves the maximum throughput.The equilibrium of class1is less than the optimal value,while the equilibrium of class2is greater than the optimal value.This is because we use the approximation(13).As will be shown later,this approximation does not affect the throughput and fairness too much when the number of users is large. Figure5compares the throughput of P-MAC and the MAC based on N-signal game.We use estimated signals in both protocols.The number of nodes in two traf?c classes are K3
Fig.3.The fairness comparison between idle sense and the MAC based on one-signal game with utility function(9)in a network of20nodes.
and 2K3 ,respectively,K=1,...,50.When the number of nodes in the network is small,P-MAC achieves the highest throughput.The game based design performs worse in this case because of the approximation used in(13).As the number of users increases,both P-MAC and the game based design perform fairly close to the optimal throughput.They achieve a much higher throughput than DCF.
Figure6compares the short-term fairness of different protocols using Jain fairness index[21].All parameters are the same as those used in Figure4.We see that both P-MAC and the game based design provide much better fairness than802.11b as802.11b does not differentiate different traf?c classes.
To show that the game based design is well-behaved in the presence of traf?c?uctuations,we consider a network with a variable number of nodes,as shown in Figure7.At?rst, |f1|=10and|f2|=15.After300iterations,5class-1and5 class-2traf?c nodes enter the network.After600iterations,5 class-1and5class-2traf?c nodes leave the network.P-MAC still does not converge.The game based design responses to traf?c?uctuation very fast.With estimated contention measurement signals,the game based design oscillates around the equilibrium.
C.Equilibrium Selection
Finally,we check the equilibrium selection algorithm de-scribed in Section IV-D.We consider a network of5nodes. The gradient play for the game with utility function(9)is simulated,whereξ=0.1622and the stepsize i(t)=0.02. We assume perfect contention measure signals and we decide that the inner loop convergence is attained if p(t+1)?p(t) 2≤3×10?4.Figure8compares the evolution of channel access probability with differentαvalues for(9).We see that the inner loop convergence rate increases by increasingα, while the outer loop convergence rate decreases by increasing α.
(a)P-MAC (b)Game model
Fig.4.The dynamics of P-MAC and the MAC based on N -signal game with utility function (17)and price function (18)in a network of 25nodes and two traf ?c classes.We choose ξ=0.1622and α=2in (17).
VI.C ONCLUSIONS
We have generalized the random access game model,and shown that it provides a general framework for designing contention based medium access control.Several examples have been given on how to design random access games from reverse-engineering and forward-engineering.We have shown that the given examples attain a unique equilibrium provided the corresponding conditions are satis ?ed,and established the convergence of various dynamic algorithms to the equilibrium.Simulation results have shown that the game model based protocols achieve superior performance over the standard IEEE 802.11DCF,and comparable performance as existing protocols with the best performance in literature.
A PPENDIX A:P ROOF OF T HEOREM 13Proof:By equation (23),we have
p (t +1)?p ? 22
≤X i ∈N
??p i (t )+ (t )(U i (p i (t ))?C i (p (t )))?p ?i
??2
≤ p (t )?p ? 22+2 (t )X i
(p i (t )?p ?i )`U i (p i (t ))?C i (p (t ))′+ 2(t )X i
`U i (p i (t ))?C i (p (t ))
′2
(a )
≤ p (t )?p ? 22+2 (t )X i
(p i (t )?p ?i )(U i (p i (t ))?U i (p ?
i ))?2 (t )
X
i
(p i (t )?p ?i )(C i (p (t ))?C i (p ?
))
+ 2
(t )
X i
`U i (p i (t ))?C i (p (t ))′2
,(40)
where we have used C i (p (t ))to denote C i (q i (p (t ))).In (a),
we use the fact that U i (p ?i )=C i (p ?
)at the nontrivial Nash equilibrium.By mean value theorem,we ?nd
X
i
(p i (t )?
p ?i )`U
i (p i (t ))
?
U i (p ?i )
′
=
X
i
U i (?p i )(p i (t )?p ?i )2≤?μ p (t )?p ? 2
2,
(41)
Fig.5.The throughput comparison between P-MAC and the MAC based
on N -signal game with utility function (17)and price function (18).
where ?p i =γp i (t )+(1?γ)p ?i ,0≤γ≤1.De ?ne a scalar
function f (p )=(p (t )?p ?)T
C (p ).By mean value theorem,we have
f (p (t ))?f (p ?)=(p (t )?p ?)T J C (?p )(p (t )?p ?)
≥λmin (J C ) p (t )?p ? 22.
(42)
We also have
X i
`U i (p i (t ))?C i (p (t ))
′2
=X i
`U i (p i (t ))?U i (p ?i )+C i (p ?
)?C i (p (t ))
′2
≤2X i
(U i (p i (t ))?U i (p ?i ))2+2X i
(C i (p (t ))?C i (p ?))
2(a )
≤2χ2
p (t )?
p ? 22
+2
X i
“
J C i (?p i )(p (t )?p ?
)”2
≤2χ2 p (t )?p ? 22+2
X
i max j
?
??J C ij (?p i )???
2
!
p (t )?p ? 22
≤2(χ2
+|N |M ) p (t )?
p ? 22,
(43)
Fig.6.The fairness comparison between P-MAC and the MAC based on
N -signal game with utility function (17)and price function (18).
where (a )comes from mean value theorem.Substituting (41)-(43)into (40),we obtain
p (t +1)?p ? 22
≤“1?2 (t )“μ+λmin (J C )? (t )`χ2+|N |M ′”” p (t )?p ? 22.
(44)
Therefore,if μ+λmin (J C )>0and (t )<
μ+λmin (J C
)χ2+|N |M ,
p (t )
converges to p ?geometrically.
A PPENDIX B:P ROOF OF T HEOREM 15
Proof:We show this by induction.The proof basically follows that of Theorem 13.For brevity,we omit several immediate steps.Suppose that
p (τ+1)?p ? 22≤γ p (τ)?p ? 2
2,?τ∈{0,...,t ?1},(45)
where 0<γ<1is a constant.When τ=t ,by equation (31),
p (t +1)?p ? 22
≤X i ∈N
???p i (t )+ “U i (p i (t ))?C i “p (τi (t ))””?p ?i ???
2≤ p (t )?p ? 22+2 X
i
(p i (t )?p ?i )`U i (p i (t ))?U i (p ?
i )′?2
X
i
(p i (t )?
p ?i )
“C i (p (τi
(t )))?C i (p ?
)
”
+
2X i
“U
i (p i (t ))?C i (p (τi
(t )))”2.(46)
By mean value theorem,we have
f (p (τi (t )))?f (p ?)
=(p (t )?p ?)T
J C
(?p )
p (τi (t ))?p ?
≥? J C (?p ) 1 p (t )?p ? 2 p (τi (t ))?p ? 2≥?M 1 p (t )?p ? 2 p (τi (t ))?p ? 2.
(47)
Note that
p (τi (t ))?p ? 22= j ∈N
p j (τi j (t ))?p ?j 2≤ j ∈N
p (τi j
(t ))?p ? 2≤
j ∈N
γτi
j (t )?t p (t )?p ? 2
≤
|N |γ
B p (t )?p ? 2
.(48)
Similar to (44),we obtain
p (t +1)?p ? 2
2
≤ p (t )?p ? 2
2
1?2 μ?M 1
s
|N |γB + …χ2+M 2
|N |2
γB
?!!.Therefore,if there exists >0and 0<γ<1such that (32)
holds,the induction hypothesis is true for τ=t .
A PPENDIX C:P ROOF OF T HEOREM 16Proof:By following (40),we obtain
p (t +1)?p ? 22
≤ p (t )?p ? 22+ 2(t )
X i
`U i (p i (t ))?C i (p (t ))?ˉw
i (t )′2
+2 (t )
X
i
(p i (t )?
p ?i )
`U i (p i (t ))?C i (p (t )?ˉw i (t ))′
≤γ p (t )?p ? 22+4 ω
X
i
|ˉw i (t )?ˉw i |+2 2
X
i
(ˉw i (t )?ˉw i )2,
(49)
where γ=1?2 (μ+λmin (J C )? (χ2+4M ))and <
μ+λmin (J C )
χ2+4|N |M .By assumption lim t →∞ˉw
i (t )=ˉw i ,for any δ>0,there exists a t 0such that if t ≥t 0|ˉw i (t )?ˉw i |<δ,?i .Applying (49)recursively,we obtain
p (t +1)?p ? 22≤γ
t ?t 0
p (t 0)?
p ? 22
+4 ω|N |δ
t ?t 0
X
τ=0
γτ+2 |N |δ
2
t ?t 0X
τ=0
γ2τ
≤γt ?t 0 p (t 0)?p ? 22+
4 ω|N |δ
1?γ+2 |N |δ2
1?γ2
.
(50)
By taking δ→0and t →∞,we obtain lim sup t →∞ p (t )?
p ? 22=0.Therefore,p (t )converges to p ?
.
A PPENDIX D:P ROOF OF T HEOREM 17
Proof:By following (40),we obtain
E ? p (t +1)?p ? 22
ˉ
≤ p (t )?p ? 22+ 2
(t )X i
`U i
(p i (t ))?C i (p (t ))??w i (t )′2+2 (t )
X
i
(p i (t )?
p ?i
)`U
i (p i (t ))?C i (p (t )??w i (t ))
′≤ p (t )?p ? 22? (t )κ p (t )?p ? 22+2 2
(t )E (
X
i
?w 2
i (t )
)
?2 (t )E (
X
i
(p i (t )?p ?i )?w
i (t ))
≤ p (t )?
p ? 22? (t )κ p (t )?p ? 22+2 2
(t )|N |B,
(51)
(a)P-MAC(b)Game model
Fig.7.The dynamics of P-MAC and the MAC based on N-signal game with utility function(17)and price function(18)in the presence of traf?c?uctuations in a network with two traf?c classes.
where
2(μ+λmin(J C)? (t)(χ2+4|N|M))>κ>0.(52)
From(34),?t0,κsuch that for all t≥t0,(52)holds.Taking
expectation both sides of(51)over F t and applying the
resulting equation recursively,
E ?
p(t+1)?p? 22
ˉ
≤E ?
p(t0)?p? 22
ˉ
?κ
t
X
t=t0
(t)E
?
p(t)?p? 22
ˉ
+2|N|B
t
X
t=t0
2(t),
(53)
from
which we get
∞
t=t0
(t)E{ p(t)?p? 22}<∞.Since
∞
t=0 (t)=∞and E{ p(t)?p? 22}≥0,p(t)converges
to p?with probability1.
A PPENDIX E:P ROOF OF T HEOREM18
Proof:By following(49),we obtain
p(t+1)?p? 22
≤ p(t)?p? 22+ 2(t)
X
i `
U i(p i(t))?C i(p(t))??w i(t)
′2
+2 (t)
X
i (p i(t)?p?i)
`
U i(p i(t))?C i(p(t)??w i(t))
′
≤γ p(t)?p? 22?2
X
i (p i(t)?p?i)?w i(t)+2 2
X
i
?w2i(t),
(54)
whereγis de?ned after(49).Applying(54)recursively,we obtain
p(t+1)?p? 22≤γt p(0)?p? 22+2 2
t
X
τ=0
γt?τ
X
i
?w2i(τ)
?2
t
X
τ=0
γt?τ
X
i
(p i(τ)?p?i)?w i(τ).
(55)
Fig.8.The dynamics of the game with utility function(9)using equilibrium
selection in a network of5nodes.Differentαvalues for(9)are compared.
As E{w i(t)}=0and E{
i
?w2i(τ)}≤B,by using[22,
Lemma2],there exists a constant D(B, )>0such that
lim inf
t→∞
2 2
t
X
τ=0
γt?τ
X
i
?w2i(τ)
?2
t
X
τ=0
γt?τ
X
i
(p i(τ)?p?i)?w i(τ)
!
≤D(B, ).
(56)
Therefore,we get(35).
R EFERENCES
[1]L.Chen,S.H.Low,and J.C.Doyle,“Random access game and medium
access control design,”Mar.2006.https://www.wendangku.net/doc/f712697189.html,/～chen/
papers/ramac.pdf,Caltech CDS,Tech.Rep.
[2]——,“Contention control:A game-theoretic approach,”in Proc.IEEE
CDC,Dec.2007,pp.3428–3434.
[3]Y.Jin and G.Kesidis,“Equilibria of a noncooperative game for
heterogeneous users of an Aloha networks,”IEEE Commun.Lett.,vol.6,
no.7,pp.282–284,July2002.
[4] A.B.MacKenzie and S.B.Wicker,“Stability of multipacket slotted
Aloha with sel?sh users and perfect information,”in Proc.IEEE
Infocom,Apr.2003,pp.1583–1590.
[5]V.S.Borkar and A.A.Kherani,“Random access in wireless ad hoc
networks as a distributed game,”in Proc.WiOpt,Mar.2004.
[6]ˇCagalj,S.Ganeriwal,I.Aad,and J.P.Hubaux,“On sel?sh behavior
in CSMA/CA networks,”in Proc.IEEE Infocom,Mar.2005,pp.2513–2524.
[7]J.W.Lee,M.Chiang,and R.A.Calderbank,“Utility-optimal random-
access protocol,”IEEE Trans.Wireless Commun.,vol.6,no.7,pp.
2741–2751,July2007.
[8]J.W.Lee,A.Tang,J.Huang,M.Chiang,and A.R.Calderbank,
“Reverse-engineering MAC:A non-cooperative game model,”IEEE J.
Select.Areas Commun.,vol.25,no.6,pp.1135–1147,Aug.2007. [9]M.Heusse,F.Rousseau,R.Guillier,and A.Dula,“Idle sense:An
optimal access method for high throughput and fairness in rate diverse wireless LANs,”in Proc.ACM Sigcomm,Aug.2005,pp.121–132. [10] D.Qiao and K.G.Shin,“Achieving ef?cient channel utilization and
weighted fairness for data communications in IEEE802.11WLAN under the DCF,”in Proc.IWQoS,May2002.
[11] C.Hu and J.C.Hou,“A novel approach to contention control in IEEE
802.11e-operated WLANs,”in Proc.IEEE Infocom,May2007,pp.
1190–1198.
[12] D.Fudenburg and J.Tirole,Game Theory.MIT Press,1991.
[13]T.Cui,L.Chen,S.H.Low,and J.C.Doyle,“Game-theoretic framework
for medium access control,”Aug.2007.https://www.wendangku.net/doc/f712697189.html,/～taocui/rag.pdf,Caltech CDS,Tech.Rep.
[14] D.M.Topkis,“Equilibrium points in nonzero-sum n-person submodular
games,”SIAM J.Contr.and Optim.,vol.17,no.6,pp.773–787,1979.
[15]L.Chen,T.Cui,S.H.Low,and J.C.Doyle,“A game-theoretic model
for medium access control,”in Proc.International Wireless Internet Conference(WICON),Oct.2007.
[16]S.D.Flam,“Equilibrium,evolutionary stability and gradient dynamics,”
International Game Theory Review,vol.4,no.4,pp.357–370,Dec.
2002.
[17]R.A.Horn and C.R.Johnson,Matrix Analysis.Cambridge University
Press,1985.
[18]https://www.wendangku.net/doc/f712697189.html, and V.Anantharam,“Utility based rate control in the internet
for elastic traf?c,”IEEE/ACM https://www.wendangku.net/doc/f712697189.html,working,vol.10,no.2,pp.
271–286,Apr2002.
[19]R.Abraham,J.E.Marsden,and T.Ratiu,Manifolds,Tensors,Analysis,
and Applications,2nd ed.Springer-Verlag,1988.
[20]“Wireless LAN media access control(MAC)and physical layer(PHY)
speci?cations,”IEEE Standard802.11,June1999.
[21]R.Jain,D.Chiu,and W.Hawe,“A quantitative measure of fairness
and discrimination for resource allocation in shared computer systems,”
DEC Research Report TR-301,Sept.1984.
[22] D.P.Bertsekas and J.N.Tsitsiklis,“Gradient convergence in gradient
methods with errors,”SIAM J.Optim.,vol.10,no.3,pp.627–642,May
1999.
Tao Cui(S’04)received the M.Sc.degree in the
Department of Electrical and Computer Engineering,
University of Alberta,Edmonton,AB,Canada,in
2005,and the M.S.degree from the Department
of Electrical Engineering,Caltech,Pasadena,USA,
in2006.He is currently working toward the Ph.D.
degree at the Department of Electrical Engineering,
Caltech.His research interests are in the interactions
between networking theory,communication theory,
and information theory.
Mr.Cui received the Best Paper Award at the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS)in2007and the Second Place in the ACM Student Research Competition at the2007Richard Tapia Celebration of Diversity in Computing Conference.Mr.Cui was a recipient of postgraduate scholarships from the Alberta Ingenuity Fund and the Alberta Informatics Circle of Research
Excellence.
Lijun Chen(S’05-M’07)received his B.S.from
University of Science and Technology of China,
M.S.from Institute of Theoretical Physics,Chi-
nese Academy of Sciences and from University of
Maryland at College Park,and Ph.D.from Caltech.
He is currently a Research Scientist in the Control
&Dynamical Systems Department at Caltech.His
research interests are in communication networks,
network economics and online market,and opti-
mization,game theory and their engineering applica-
tion.He was a co-recipient of the Best Paper Award at the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS)in
2007.
Steven H.Low(F’08)received his B.S.from
Cornell University,and PhD from Berkeley,both
in electrical engineering.He is a Professor of the
Computer Science and Electrical Engineering De-
partments at Caltech.He was with AT&T Bell
Laboratories,Murray Hill,from1992to1996,the
University of Melbourne,Australia from1996to
2000,and was a Senior Fellow of the University of
Melbourne from2000to2004.He was a co-recipient
of the IEEE William R.Bennett Prize Paper Award
in1997and the1996R&D100Award.He was on the editorial board of IEEE/ACM Transactions on Networking from1997to 2006and on that of Computer Networks Journal from2003to2005.He is on the editorial boards of ACM Computing Surveys,NOW Foundations and Trends in Networking.He is a Senior Editor of the IEEE Journal on Selected Areas in Communications and a Co-Editor of Springer Book Series on Optimization and Control of Communication Systems:Theory and Applications.He is a member of the Networking and Information Technology Technical Advisory Group for the US President’s Council of Advisors on Science and Technology(PCAST).