A comparative study of two classical topology-transparent scheduling algorithms for multi-hop packet radio networks

摘要

The aim of topology-transparent scheduling algorithms for multi-hop wireless networks is to find a schedule for the nodes that does not need re-computation when the network topology changes. It caters to highly dynamic scenarios where topology changes occur faster than the speed at which schedule updates can be orchestrated. These algorithms normally take as input only global network parameters like the maximum number of nodes and the maximum degree of a node in the network, rather than the detailed topology of the network. In this paper, we study two classical topology-transparent scheduling algorithms: the algorithm due to Chlamtac and Faragó and the optimal algorithm due to Ju and Li. We provide qualitative comparison of the algorithms followed by numerical simulations to study their throughput characteristics which are also compared with those of multi-hop slotted-ALOHA and TDMA.