Minimizing multiplayer interactive delay in multihop wireless networks

SUMMARY Minimizing the schedule frame length in spatial time division multiple access networks is essential in enhancing the performance of multiplayer interactive applications in multiple-group multicasting environments. In this paper, the joint link scheduling and multiple-group communication problem in such networks is referred to as a real-time multiple-group communication tree scheduling (RMGCTS) problem in which the objective is to minimize the total schedule frame length. It is shown that the RMGCTS problem can be represented as an integer linear programming problem. Two particular RMGCTS problems are considered, namely, back-to-back RMGCTS for applications with a receiving-jitter constraint, and general RMGCTS for applications with a delay constraint. Two heuristic algorithms, designated as back-to-back scheduling and level-by-level scheduling, are proposed to provide efficient solutions of the back-to-back and general RMGCTS problems by maximizing the spatial reuse capability within each time slot, thereby minimizing the schedule frame length. The simulation results show that the proposed schemes yield an effective reduction in the length of the multicast schedule frame compared to that obtained from existing tree-based or pure-color scheduling algorithms.