Towards Optimal Distributed Node Scheduling in a Multihop Wireless Network through Local Voting

摘要

In a multihop wireless network, it is crucial but challenging to scheduletransmissions in an efficient and fair manner. In this paper, a noveldistributed node scheduling algorithm, called Local Voting, is proposed. Thisalgorithm tries to semi-equalize the load (defined as the ratio of the queuelength over the number of allocated slots) through slot reallocation based onlocal information exchange. The algorithm stems from the finding that theshortest delivery time or delay is obtained when the load is semi-equalizedthroughout the network. In addition, we prove that, with Local Voting, thenetwork system converges asymptotically towards the optimal scheduling.Moreover, through extensive simulations, the performance of Local Voting isfurther investigated in comparison with several representative schedulingalgorithms from the literature. Simulation results show that the proposedalgorithm achieves better performance than the other distributed algorithms interms of average delay, maximum delay, and fairness. Despite being distributed,the performance of Local Voting is also found to be very close to a centralizedalgorithm that is deemed to have the optimal performance.