On end-to-end delay minimization in wireless networks under the physical interference model

Abstract—The problem of scheduling transmission in single hop and multi-hop wireless networks with arbitrary topology and physical interference model has been widely studied. However, the focus has been mainly on optimizing the efficiency in transmission parallelization through a minimum frame-length scheduling that, for a given set of traffic demands, provides the smallest number of time-slots for performing different sets of simultaneous and compatible (according to the interference model) transmissions. Unfortunately, this optimal resource reuse efficiency does not in general correspond to the best performance in terms of end-to- end packet delivery delay since multiple frames may be required to complete transfer from source to destination. In this paper we study the problem of minimizing the end-to-end delay in wireless network under Signal to Interference plus Noise Ratio (SINR) constraints, and propose two schemes. The first scheme extends the minimum frame-length approach and minimizes delay over multiple frames. The second scheme directly optimizes delay without the constraint of periodic framing. We propose novel mixed integer programming models for the two schemes and study their properties and complexity. Moreover, we present an efficient heuristic method that provides good quality solutions in short time.