Scheduling deadline-constrained packets in multi-hop networks has received increased attention recently. However, there is very limited work on this problem for wireless networks where links are subject to interference. The existing algorithms either provide approximation ratio guarantees, which diminish in quality as parameters of the network scale, or hold in an asymptotic regime when the time horizon, network bandwidth, and packet arrival rates are scaled to infinity, which limits their practicality. While attaining a constant approximation ratio has been shown to be impossible in the worst-case traffic setting, it is unclear if the same holds under stochastic traffic, in a non-asymptotic setting. In this work, we show that, in the stochastic traffic setting, a constant approximation ratio or near-optimal algorithms can be achieved. Specifically, we propose algorithms that attain$\Omega ((1-\epsilon )/\beta )$or$\Omega (1-\epsilon )$fraction of the optimal value, when the number of channels is$\mathrm{C}= \Omega ( \frac{\log (L/\epsilon )}{\epsilon ^{2}})$or$\mathrm{C}= \Omega (\frac{\chi ^{\star }\log (L/\epsilon )}{\epsilon ^{2}})$, respectively, where$L$is the maximum route length of packets,$\chi ^\star$is the fractional chromatic number of the network interference graph, and$\beta$is its interference degree. This marks the first near-optimal results under non-trivial traffic and bandwidth assumptions in a non-asymptotic regime.

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 ,\mathrm {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$\mathrm {R}\geq 1$. In particular, our algorithm can achieve$\gamma =O({\psi }^{\star } \log (\Delta \rho L)/\mathrm {R})$when$\mathrm {R}\mathrm {C} = \Omega ({\psi }^{\star } \log (\Delta \rho L))$, where$\rho $is the ratio of maximum weight to minimum weight of packets,Lis the length of the longest route of packets, and C is the minimum link capacity or the number of channels. Here,$\Delta $is themaximum degreeand$ {\psi }^{\star } $is thelocal clique cover numberof the interference graph. Our results translate directly to many networks of interest, for example, in one-hop interference networks,$ {\psi }^{\star } =2$, and in the case of wired networks (no interference),$ {\psi }^{\star } =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.

Scheduling deadline-constrained packets in multihop networks has received increased attention recently. However, there is very limited work on this problem for wireless networks where links are subject to interference. The existing algorithms either provide approximation ratio guarantees which diminish in quality as parameters of the network scale, or hold in an asymptotic regime when the time horizon, network bandwidth, and packet arrival rates are scaled to infinity, which limits their practicality. While attaining a constant approximation ratio has been shown to be impossible in the worst-case traffic setting, it is unclear if the same holds under stochastic traffic, in a non-asymptotic setting. In this work, we show that, in the stochastic traffic setting, constant approximation ratio or near-optimal algorithms can be achieved. Specifically, we propose algorithms that attain Ω((1 − ϵ)/β) or Ω(1 − ϵ) fraction of the optimal value, when the number of channels is ${\text{C}} = \Omega \left( {\frac{{\log (L/\varepsilon )}}{{{\varepsilon ^2}}}} \right)$ or ${\text{C}} = \Omega \left( {\frac{{{\chi ^ \star }\log (L/\varepsilon )}}{{{\varepsilon ^3}}}} \right)$respectively, where L is the maximum route length of packets, χ⋆is the fractional chromatic number of the network’s interference graph, and β is its interference degree. This marks the first near-optimal results under nontrivial traffic and bandwidth assumptions in a non-asymptotic regime.

Despite the rich literature on scheduling algorithms for wireless networks, algorithms that can provide deadline guarantees on packet delivery for general traffic and interference models are very limited. In this paper, we study the problem of scheduling real-time traffic under a conflict-graph interference model with unreliable links due to channel fading. Packets that are not successfully delivered within their deadlines are of no value. We consider traffic (packet arrival and deadline) and fading (link reliability) processes that evolve as an unknown finite-state Markov chain. The performance metric is efficiency ratio which is the fraction of packets of each link which are delivered within their deadlines compared to that under the optimal (unknown) policy. We first show a conversion result that shows classical non-real-time scheduling algorithms can be ported to the real-time setting and yield a constant efficiency ratio. In particular, Max-Weight Scheduling (MWS) yields an efficiency ratio of 1/2. We then propose randomized algorithms that achieve efficiency ratios strictly higher than 1/2, by carefully randomizing over the maximal schedules. Further, we propose low-complexity and myopic distributed randomized algorithms, and characterize their efficiency ratio. Simulation results are presented that verify that the randomized algorithms outperform classical ones such as MWS and GMS for scheduling real-time traffic over fading channels.

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 (γ, R)-competitive, i.e., they achieve at least 1/γ 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 γ = O(Ψ* log(ΔρL)/R) when RC = Ω(Ψ* log(ΔρL)), where ρ 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, Δ is the maximum degree and Ψ* 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, Ψ* = 2, and in the case of wired networks (no interference), Ψ* = 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.

Despite the rich literature on scheduling algorithms for wireless networks, algorithms that can provide deadline guarantees on packet delivery for general traffic and interference models are very limited. In this paper, we study the problem of scheduling real-time traffic under a conflict-graph interference model with unreliable links due to channel fading. Packets that are not successfully delivered within their deadlines are of no value. We consider traffic (packet arrival and deadline) and fading (link reliability) processes that evolve as an unknown finite-state Markov chain. The performance metric is efficiency ratio which is the fraction of packets of each link which are delivered within their deadlines compared to that under the optimal (unknown) policy. We first show a conversion result that shows classical non-real-time scheduling algorithms can be ported to the real-time setting and yield a constant efficiency ratio, in particular, Max-Weight Scheduling (MWS) yields an efficiency ratio of 1/2. We then propose randomized algorithms that achieve efficiency ratios strictly higher than 1/2, by carefully randomizing over the maximal schedules. We further propose low-complexity and myopic distributed randomized algorithms, and characterize their efficiency ratio. Simulation results are presented that verify that randomized algorithms outperform classical algorithms such as MWS and GMS.

In this paper, we consider the problem of scheduling real-time traffic in wireless networks under a conflict-graph interference model and single-hop traffic. The objective is to guarantee that at least a certain fraction of packets of each link are delivered within their deadlines, which is referred to as delivery ratio. This problem has been studied before under restrictive frame-based traffic models, or greedy maximal scheduling schemes like LDF (Largest-Deficit First) that can lead to poor delivery ratio for general traffic patterns. In this paper, we pursue a different approach through randomization over the choice of maximal links that can transmit at each time. We design randomized policies in collocated networks, multipartite networks, and general networks, that can achieve delivery ratios much higher than what is achievable by LDF. Further, our results apply to traffic (arrival and deadline) processes that evolve as positive recurrent Markov chains. Hence, this work is an improvement with respect to both efficiency and traffic assumptions compared to the past work. We further present extensive simulation results over various traffic patterns and interference graphs to illustrate the gains of our randomized policies over LDF variants.

In this paper we propose a topology control based approach for addressing the coverage problem in a planar region containing convex opaque obstacles. Such environments represent typical cases of realistic wireless sensor networks and Internet-of-Things deployments. Assuming the devices have the capability to modify their sensing ranges, our goal is to maximize the area covered by randomly dispersed sensors, while reducing their sensing energy consumption as much as possible despite the presence of convex obstacles. To address the former, we introduce a relevant framework capitalizing on the notion of the visibility polygon and propose two algorithms, a centralized (and a randomized version thereof) and a distributed one, which aim to maximize the ratio of covered area to consumed energy, while ensuring a minimum coverage percentage. Through analysis and simulation we demonstrate that the proposed schemes achieve energy efficient coverage, outperforming the plain assignment of maximum sensing range across the network.