Universal stability in multi-hop radio networks

Abstract We study stability of routing in multi-hop wireless networks in the framework of adversarial queueing. A routing algorithm consists of three components: a transmission policy to decide on immediate transmissions, a scheduling policy to select a packet to transmit, and a hearing control to coordinate transmissions with scheduling. We consider two kinds of hearing control: proactive and reactive. We compare these policies and show relationships between the wired-network adversarial model and the multi-hop radio network model. In particular, we introduce a family of scheduling policies that are universally stable when using reactive hearing control, and obtain some stability results by using regular transmission oracles. We also prove that networks in which there is at least one node with an out-degree greater than 1 are unstable when using reactive hearing control, but all directed acyclic networks are universally stable, regardless of their out-degree, if using proactive hearing control.