| dc.description.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 | en_US |
