Online Scheduling and Routing with End-to-End Deadline Constraints in Multihop Wireless Networks

We consider scheduling deadline-constrained packets in multihop wireless networks. Packets with arbitrary deadlines and weights arrive at and are destined to different nodes. The goal is to design online admission, routing, and scheduling algorithms in order to maximize the cumulative weight of packets that reach their destinations within their deadlines. Under a general interference graph model of the wireless network, we provide online algorithms that are (gamma, R)-competitive, i.e., they achieve at least 1/gamma fraction of the value of the optimal offline algorithm, and do not exceed the capacity by more than a factor R >= 1. In particular, our algorithm can achieve gamma =O (psi* log(Delta rho L)/R) when RC = Omega(psi* log(Delta rho L)), where rho is the ratio of maximum weight to minimum weight of packets, L is the length of the longest route of packets, and C is the minimum link capacity or the number of channels. Here, Delta is the maximum degree and psi* is the local clique cover number of the interference graph. Our results translate directly to many networks of interest, for example, in one-hop interference networks,psi* = 2 and in the case of wired networks (no interference),psi* = 1. We further provide lower bounds that show that our results are asymptotically optimal in many settings. Finally, we present extensive simulations that show our algorithms provide significant improvement over the prior approaches.