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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(\gamma ,\mathrm {R})$</tex-math> </inline-formula>-competitive, i.e., they achieve at least <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1/\gamma $</tex-math> </inline-formula> fraction of the value of the optimal offline algorithm, and do not exceed the capacity by more than a factor <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathrm {R}\geq 1$</tex-math> </inline-formula>. In particular, our algorithm can achieve <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\gamma =O({\psi }^{\star } \log (\Delta \rho L)/\mathrm {R})$</tex-math> </inline-formula> when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathrm {R}\mathrm {C} = \Omega ({\psi }^{\star } \log (\Delta \rho L))$</tex-math> </inline-formula>, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\rho $</tex-math> </inline-formula> is the ratio of maximum weight to minimum weight of packets, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</i> is the length of the longest route of packets, and C is the minimum link capacity or the number of channels. Here, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Delta $</tex-math> </inline-formula> is the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">maximum degree</i> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\psi }^{\star } $</tex-math> </inline-formula> is the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">local clique cover number</i> of the interference graph. Our results translate directly to many networks of interest, for example, in one-hop interference networks, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\psi }^{\star } =2$</tex-math> </inline-formula>, and in the case of wired networks (no interference), <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\psi }^{\star } =1$</tex-math> </inline-formula>. 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.