A decentralized medium access protocol for real-time wireless Ad Hoc networks with unreliable transmissions

This paper proposes a feasibility-optimal decentralized algorithm for real-time wireless ad hoc networks, where a strict deadline is imposed for each packet. While centralized scheduling algorithms provide provably optimal theoretical guarantees, they may not be practical in many settings, such as industrial networked control systems. Therefore, it is of great importance to design an algorithm that achieves feasibility optimality in a decentralized manner. To design a decentralized algorithm, we leverage two widely-used functions of wireless devices: carrier sensing and backoff timers. Different from the conventional approach, the proposed algorithm utilizes a collision-free backoff scheme to enforce the transmission priority of different links. This design obviates the capacity loss due to collision with quantifiably small backoff overhead. The algorithm is fully decentralized in the sense that every link only needs to know its own priority, and links contend for priorities only through carrier sensing. We prove that the proposed algorithm is feasibility-optimal. NS-3 simulation results show that the proposed algorithm indeed performs as well as the feasibility-optimal centralized algorithm. Moreover, the results also show that the proposed algorithm converges to optimality very fast.