Fair spatial TDMA channel access protocols for multihop radio networks

Abstract

The issues of fairness are considered in designing time division multiple access (TDMA) channel access protocols for multihop radio networks. It is shown that there is a limitation as to how fair one can design a channel access protocol for a static multihop radio network. Several fairness measures which are functions of the channel access protocol and the network topology are proposed. It is shown that to find the optimal protocol with respect to any defined fairness measure is NP-hard. Criteria for designing a fair protocol which are independent of the network topology are introduced and their properties are proved. A lower upper bound of one of the measures is found. Two heuristic protocols are developed based on these criteria. Performance comparisons with existing protocols are given.