An Analysis of Generalized Slotted-Aloha Protocols

Aloha and its slotted variation are commonly deployed medium access control (MAC) protocols in environments where multiple transmitting devices compete for a medium, yet may have difficulty sensing each other's presence (the "hidden terminal problem''). Competing 802.11 gateways, as well as most modern digital cellular systems, like GSM, are examples. This paper models and evaluates the throughput that can be achieved in a system where nodes compete for bandwidth using a generalized version of slotted-Aloha protocols. The protocol is implemented as a two-state system, where the probability that a node transmits in a given slot depends on whether the node's prior transmission attempt was successful. Using Markov models, we evaluate the channel utilization and fairness of this class of protocols for a variety of node objectives, including maximizing aggregate throughput of the channel, each node selfishly maximizing its own throughput, and attacker nodes attempting to jam the channel. If all nodes are selfish and strategically attempt to maximize their own throughput, a situation similar to the traditional Prisoner's Dilemma arises. Our results reveal that under heavy loads, a greedy strategy reduces the utilization, and that attackers cannot do much better than attacking during randomly selected slots.

I. Introduction

In many communication networks, the communication medium is often shared by multiple users who must compete for access. In Ethernet [1], nodes use CSMA/CD [2], [3] as a MAC protocol. In order to reduce the probability of collisions, each node implements CSMA/CD, sensing the medium to ensure the medium is available prior to transmitting. However, for wireless ad hoc networks or sensor networks, carrier sensing may not be effective. This is because nodes may not be able to sense one another's presence, yet their transmissions may still interfere. Ad hoc networks, sensor networks, and competing “hotspot” 802.11 gateways are examples where this so-called “hidden terminal problem” occurs.