The impact of network topology on delay bound in wireless Ad Hoc networks

We consider single channel wireless networks with interference constraint among the links that can be activated simultaneously. The traffic flows are assumed to be single hop. Delay performance of the well known throughput optimal maximum weight link scheduling algorithm has been studied recently. In this paper, we study the relation between network topology and delay of maximum weight link scheduling algorithm. First, we consider 1-hop interference model. Under this interference model, an upper bound for the average delay of packets is derived analytically in terms of edge chromatic number of the network graph. Then the results have been extended to the case of general interference model. Under this model of interference, an upper bound for delay as a function of chromatic number of conflict graph is derived. Since chromatic number and edge chromatic number are network topology parameters, the results show that how the upper bound of delay is affected by network topology. Simulation results confirm our analytical relations.