CaltechAUTHORS
  A Caltech Library Service

Reverse-Engineering MAC: A Non-Cooperative Game Model

Lee, Jang-Won and Tang, Ao and Huang, Jianwei and Chiang, Mung and Calderbank, A. Robert (2007) Reverse-Engineering MAC: A Non-Cooperative Game Model. IEEE Journal on Selected Areas in Communications, 25 (6). pp. 1135-1147. ISSN 0733-8716. https://resolver.caltech.edu/CaltechAUTHORS:LEEieeejsac07

[img]
Preview
PDF - Published Version
See Usage Policy.

564Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:LEEieeejsac07

Abstract

This paper reverse-engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse-engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. Then we establish the minimum amount of backoff aggressiveness needed, as a function of density of active users, for uniqueness of Nash equilibrium and convergence of the best response strategy. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse-engineering TCP and BGP, this paper further advances the recent efforts in reverse-engineering layers 2-4 protocols. In contrast to the TCP reverse-engineering results in earlier literature, MAC reverse-engineering highlights the non-cooperative nature of random access.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/JSAC.2007.070808 DOIArticle
http://ieeexplore.ieee.org/document/4278414/PublisherArticle
https://doi.org/10.1109/JSAC.2007.070808DOIUNSPECIFIED
https://doi.org/10.1109/JSAC.2007.070808DOIUNSPECIFIED
ORCID:
AuthorORCID
Tang, Ao0000-0001-6296-644X
Additional Information:© 2007 IEEE. Manuscript received July 1, 2006; revised February 15, 2007. This work was supported in part by NSF Grants CNS-0430487, CCF-0440443, CNS-0417607, CCF-0448012, and CNS-0427677. Parts of the results have been presented at IEEE INFOCOM 2006 and IEEE WiOpt 2006. We appreciate the helpful discussions with Steven Low and Lijun Chen at Caltech and Amir Hamed Mohsenian Rad from University of British Columbia.
Funders:
Funding AgencyGrant Number
NSFCNS-0430487
NSFCCF-0440443
NSFCNS-0417607
NSFCCF-0448012
NSFCNS-0427677
Subject Keywords:Wireless network, Ad hoc network, Medium access control, Mathematical programming/optimization, Network utility maximization, Game theory, Network control by pricing, Reverse-engineering
Issue or Number:6
Record Number:CaltechAUTHORS:LEEieeejsac07
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:LEEieeejsac07
Official Citation:J. w. Lee, A. Tang, J. Huang, M. Chiang and A. R. Calderbank, "Reverse-Engineering MAC: A Non-Cooperative Game Model," in IEEE Journal on Selected Areas in Communications, vol. 25, no. 6, pp. 1135-1147, August 2007. doi: 10.1109/JSAC.2007.070808 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4278414&isnumber=4278404
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:8647
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:02 Sep 2007
Last Modified:02 Oct 2019 23:53

Repository Staff Only: item control page