Research Article
Reverse Engineering MAC
@INPROCEEDINGS{10.1109/WIOPT.2006.1666466, author={Ao Tang and Jang-Won Lee and Jianwei Huang and Mung Chiang and A. Robert Calderbank}, title={Reverse Engineering MAC}, proceedings={4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks}, publisher={IEEE}, proceedings_a={WIOPT}, year={2006}, month={8}, keywords={Wireless network Ad hoc network Medium access control Mathematical programming/optimization Network utility maximization Game theory Network control by pricing Reverse engineering.}, doi={10.1109/WIOPT.2006.1666466} }- Ao Tang
Jang-Won Lee
Jianwei Huang
Mung Chiang
A. Robert Calderbank
Year: 2006
Reverse Engineering MAC
WIOPT
IEEE
DOI: 10.1109/WIOPT.2006.1666466
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. The minimum amount of backoff aggressiveness needed for uniqueness of Nash equilibrium and convergence of the best response strategy are established as a function of user density. 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 completes the recent efforts in reverse engineering the main protocols in layers 2-4.
