Transmission scheduling based on a new conflict graph model for multicast in multihop wireless networks

In multicast applications, the end-to-end delay from the source to a group member is determined by the multicast tree topology and the waiting time at each relay node. This paper addresses when the multicast tree is given how to schedule wireless nodes for transmission so that network delay is minimized. We first model the conflict relation among wireless transmissions in a conflict graph, and then we compute a transmission schedule based on an Integer Linear Programming (ILP) model. Since solving ILP problem is NP-hard, a heuristic is designed to solve the ILP problem. The resulting schedule is conflict-free, which is guaranteed by the feasibility of the ILP model. Simulation results show significant reduction of delay when compared with a First Come First Serve (FCFS) scheduling policy.