Fast group communications in multihop wireless networks subject to physical interference

In this paper, we present short communication schedules for broadcast, data aggregation, data gathering, and gossiping in multihop wireless networks subject to physical interference. We assume that all communications proceed in synchronous time-slots, each node can transmit at most one packet of fixed size in each time-slot, and all nodes have fixed and equal transmission power. Under mild assumptions, all of our communication schedules for those four group communications have constant approximation bounds. These communication schedules are built upon a general technique which enables a unified graph-theoretic treatment of the communication scheduling subject to the physical interference constraint.