Motivated by medium access control for resource-challenged wireless Internet of Things (IoT), we consider the problem of queue scheduling with reduced queue state information. In particular, we consider a time-slotted scheduling model with $N$ sensor nodes, with pair-wise dependence, such that Nodes $i$ and $i + 1,~0 < i < N$ cannot transmit together. We develop new throughput-optimal scheduling policies requiring only the empty-nonempty state of each queue that we term Queue Nonemptiness-Based (QNB) policies. We propose a Policy Splicing technique to combine scheduling policies for small networks in order to construct throughput-optimal policies for larger networks, some of which also aim for low delay. For $N = 3,$ there exists a sum-queue length optimal QNB scheduling policy. We show, however, that for $N > 4,$ there is no QNB policy that is sum-queue length optimal over all arrival rate vectors in the capacity region. We then extend our results to a more general class of interference constraints that we call cluster-of-cliques (CoC) conflict graphs. We consider two types of CoC networks, namely, Linear Arrays of Cliques (LAoC) and Star-of-Cliques (SoC) networks. We develop QNB policies for these classes of networks, study their stability and delay properties, and propose and analyze techniques to reduce the amount of state information to be disseminated across the network for scheduling. In the SoC setting, we propose a throughput-optimal policy that only uses information that nodes in the network can glean by sensing activity (or lack thereof) on the channel. Our throughput-optimality results rely on two new arguments: a Lyapunov drift lemma specially adapted to policies that are queue length-agnostic, and a priority queueing analysis for showing strong stability.

Motivated by medium access control for resource-challenged wireless sensor networks whose main purpose is data collection, we consider the problem of queue scheduling with reduced queue state information. In particular, we consider a model with N sensor nodes, with pair-wise dependence, such that nodes i and i+1, 1 ≤ i ≤ N-1 cannot transmit together. For N=3, 4, and 5, we develop new throughput-optimal scheduling policies requiring only the empty-nonempty state of each queue, and also revisit previously proposed policies to rigorously establish their throughput-and delay-optimality. For N=3, there exists a sum-queue length optimal scheduling policy that requires only the empty-nonempty state of each queue. We show, however, that for N ≥ 4, there is no scheduling policy that uses only the empty-nonempty states of the queues and is sum-queue length optimal uniformly over all arrival rate vectors. We then extend our results to a more general class of interference constraints, namely, a star of cliques. Our throughput-optimality results rely on two new arguments: a Lyapunov drift lemma specially adapted to policies that are queue length-agnostic, and a priority queueing analysis for showing strong stability. Our study throws up some counterintuitive conclusions: 1) knowledge of queue length information is not necessary to achieve optimal throughput/delay performance for a large class of interference networks, 2) it is possible to perform throughput-optimal scheduling by merely knowing whether queues in the network are empty or not, and 3) it is also possible to be throughput-optimal by not always scheduling the maximum possible number of nonempty queues. We also show the results of numerical experiments on the performance of queue length agnostic scheduling vs. queue length aware scheduling, on several interference networks.

We consider the Medium Access Control (MAC) problem in resource-constrained ad-hoc wireless networks typical of the Internet of Things (IoT). Due to the delay-sensitive nature of emerging IoT applications, there has been increasing interest in developing medium access control (TDMA) protocols in a slotted framework. The design of such MAC protocols must keep in mind the need for contention access at light traffic, and scheduled access in heavy traffic (leading to the long-standing interest in hybrid, adaptive MACs. In this paper, we consider the collocated node setting and require that each node acts autonomously only on the basis of locally available information. We propose EZMAC, a simple extension of ZMAC, and QZMAC which is designed using motivations from our extensions of certain delay-optimality and throughput-optimality theory from the literature. Practical implementation issues are outlined. Finally, we show, through simulations, that both protocols achieve mean delays much lower than those achieved by ZMAC and indeed, QZMAC provides mean delays very close to the minimum achievable in this setting, i.e., that of the centralized complete knowledge scheduler.