Efficient group multicast node scheduling schemes in multi-hop wireless networks

STDMA networks provide an effective solution for enabling wireless devices to access network resources with fairness and efficiency. When multiple-group communications are implemented in such networks, the scheduling algorithm should generate appropriate schedule assignments for all the transmissions where the objective aims to reduce the schedule length. In this paper, the problem of producing an efficient schedule sequence for multiple-group communications over a STDMA node scheduling network is referred to as an integrated multiple-group communication and traffic-oriented node scheduling (IMCTNS) problem. It is shown that the IMCTNS problem can be formulated as an integer linear programming (ILP) problem. A polynomial-time centralized heuristic scheduling algorithm, designated as Broadcasting Level-by-Level Scheduling (B-LBLS), is proposed for determining the schedule sequence subject to transmission constraints. To enhance the spatial utilization efficiency within each time slot, an advanced version of B-LBLS, designated as Collision-Allowed Level-by-Level Scheduling (CA-LBLS), is proposed based on a modified graph-based interference model. It is shown that compared to existing TDMA- and STDMA-based algorithms, the proposed algorithms provide an effective reduction in the schedule frame length and a significant increase in the spatial utilization within each time slot.