The One-Sender-Multiple-Receiver Technique and Downlink Packet Schedulingby Simultaneous Multiple Packet Transmission

Abstract

In this paper, we consider using simultaneous Multiple Packet Transmission (MPT) to improve the downlink performance of wireless  networks. With MPT, the sender can send two compatible packets simultaneously to two distinct receivers and can double the throughput in the ideal case. We formalize the problem of finding a schedule to send out buffered packets in minimum time as finding a maximum  matching  problem  in a graph.  Since  maximum  matching  algorithms  are  relatively complex  and  may not meet  the timing requirements of real-time  applications, we give a fast approximation algorithm that is capable of finding a matching  at least  3/4 of the size  of a maximum  matching  in OðjEjÞ time, where  jEj is the number of edges in the graph.  We also  give analytical bounds for maximum allowable arrival rate,  which measures the speedup of the downlink after enhanced with MPT, and our results show that the maximum  arrival rate  increases significantly even  with a very small compatibility probability. We also  use  an approximate analytical model and simulations to study the average packet delay, and our results show that packet delay can be greatly reduced even  with a very small compatibility probability