On Reduced-State Optimal Scheduling for Decentralized Medium Access Control of Wireless Data Collection Networks

Abstract

In the Internet of Things (IoT), devices such as sensors and actuators will almost invariably be connected to the Internet via wireless networks. The sensor and actuator devices in such systems will be resource challenged with constraints on the energy available to them, and on their computing, storage, and communication capabilities. Hence, the control strategies in such systems should be light-weight, and decentralised, requiring very little information exchange. With these observations in mind, the central theme of the work reported in this thesis is the development of wireless scheduling protocols, in a timeslotted setting, that require little state information and are amenable to decentralized implementation, while ensuring throughput optimality and even low mean packet delays in some cases. The thesis is divided into two parts. • In Part 1, – We study the problem of scheduling in collocated networks, wherein every node can listen to the transmissions of every other node. Motivated by a certain modification to the time slot structure that facilitates inferring activity on the channel, we derive a partial information framework within which we propose and analyse scheduling schemes. We then propose scheduling policies and analyse their stability and delay properties. – Next, we construct two completely decentralized protocols based on these results. Simulations show that the delay performance of the protocols is significantly better than that of existing protocols and, in fact, is very close to a centralized scheduler that has complete knowledge of the state of the system in every slot. This is important in light of the fact that our protocols are completely decentralized and also compute the schedule based on information gathered by the sensors only via sensing the channel for activity. – We also address the problem of short-term unfairness resulting from our low-delay scheduling policies and develop new policies to alleviate unfairness. We then propose modifications to our earlier protocols to handle alarm traffic (like uRLLC traffic being considered in the upcoming 5G standard) and show that the modified protocols provide low latency to such traffic, even in the presence of other data traffic in the system. part2 We move on to proposing reduced state scheduling policies for non-collocated networks. It should be noted that, while the scheduler that achieves minimum delay in collocated networks is known (in fact, it is not unique), such schedulers have been found for very few noncollocated networks. We begin by restricting our attention to a sub-class of scheduling policies, that take scheduling decisions based solely on the empty-nonempty status of the queues in the network. The state information for such networks is easy to disseminate (1 bit per queue) and hence makes them particularly suited to distributed implementation. – We begin by studying scheduling of transmissions on a class of networks called “path-graph networks.” These networks are characterized by interference graphs that are linear. We restrict ourselves to a further subclass of policies that are called Maximum Size Matching (MSM) policies and provide a complete characterization of the set of MSM policies for the case with N = 3 queues. As mentioned before, these policies do not require any information about the queues except their empty-nonempty status, which helps satisfy our reduced state space requirement. Our study has produced several interesting results about (in)stability and delay optimality. Specifically, we also show that the celebrated MaxWeight policy is not delay-optimal in such networks in a stochastic ordering sense (and hence, with respect to mean delay as well). – Continuing with path-graph networks, we later propose a “policy splicing” technique to combine policies for small networks to give rise to policies for larger networks. We use this technique to propose MSM scheduling policies for several such networks. We also provide an in-depth analysis of delay with MSM policies that culminates in a result which shows that there do not exist delay optimal MSM policies for such networks with N 4 queues. – Finally, we show how to extend our theory of MSM policies to schedule transmissions in a more general class of networks. We also propose and analyse multiple methods to further reduce the amount of state information (empty-nonempty statuses of the queues) that has to be exchanged across the network to make these protocols amenable to distributed implementation. Finally, we use this theory to propose a throughput optimal protocol wherein scheduling decisions are taken using only the information about activity on the channel (or lack thereof) that can be sensed by the nodes and study its stability performance in detail