### Abstract

Random access has been studied for decades as a simple and practical wireless medium access control (MAC). Some of the recently developed distributed scheduling algorithms for throughput or utility maximization also take the form of random access, although extensive message passing among the nodes is required. In this paper, we would like to answer this question: is it possible to design a MAC algorithm that can achieve the optimal network utility without message passing? We provide the first positive answer to this question through a simple Aloha-type random access protocol. We prove the convergence of our algorithm for certain sufficient conditions on the system parameters, e.g., with a large enough user population. If each wireless node is capable of decoding the source MAC address of the transmitter from the interferring signal, then our algorithm indeed converges to the global optimal solution of the NUM problem. If such decoding is inaccurate, then the algorithm still converges, although optimality may not be always guaranteed. Proof of these surprisingly strong performance properties of our simple random access algorithm leverages the idea from distributed learning: each node can learn as much about the contention environment through the history of collision as through instantaneous but explicit message passing.

Original language | English (US) |
---|---|

Article number | 4801448 |

Pages (from-to) | 1073-1079 |

Number of pages | 7 |

Journal | IEEE Transactions on Wireless Communications |

Volume | 8 |

Issue number | 3 |

DOIs | |

State | Published - Mar 1 2009 |

### All Science Journal Classification (ASJC) codes

- Computer Science Applications
- Electrical and Electronic Engineering
- Applied Mathematics

### Keywords

- Message passing
- Network utility maximization
- Non-convex optimization
- Random access
- Wireless scheduling

## Fingerprint Dive into the research topics of 'Utility-optimal random access without message passing'. Together they form a unique fingerprint.

## Cite this

*IEEE Transactions on Wireless Communications*,

*8*(3), 1073-1079. [4801448]. https://doi.org/10.1109/TWC.2009.071446