at $l$). Since $\gamma$ follows $\pi$ with exactly one step delay, $\pi$ will never be able to
make up the difference! Hence, $m^*=\infty$.

To complete the proof, one needs to consider epochs $l^*$ such as:

\begin{eqnarray}
l^*&:=&\inf\{n\geq1: Q^\pi_{\pi^q_{n-1}}(n)>0,Q^\pi_{\pi^q_{n}}(n)>0,\nonumber\\
\end{eqnarray}

wherein the queue which $\pi$ decides to serve, unlike the case with $n^*$, is non-empty and hence,
slot $l^*$ is not wasted. Even in this case defining $\gamma$ as before produces a policy that does no worse
than $\pi$ in terms of total system backlog.

In the same manner, find such an $n^*$ (or $l^*$ as the case may be) for $\gamma$ and
refine this policy using the procedure described. Iterating this procedure, one ends up with a policy
say $\xi$, for which such an instant never exists, i.e., which never switches to a different queue when the incumbent is nonempty. This is by definition exhaustive. We have, thus, defined both queueing processes on some common probability space $\left(\Omega,\mathcal{F},\mathbb{P}\right)$ and for
every $\omega\in\Omega$, we have shown that

\begin{equation}
Q^\xi(t,\omega)\leq Q^\pi(t,\omega),~\forall~t\geq1,\nonumber
\end{equation}

which means that $\forall x\in\mathbb{R}$,

\begin{equation}
\mathbb{P}\{\omega:Q^\pi(t,\omega)>x\}\geq\mathbb{P}\{\omega:Q^\xi(t,\omega)>x\}.
\end{equation}

This coupling argument shows that

\begin{equation}
Q^\xi(t)\stackrel{st}{\leq} Q^\pi(t),~\forall~t\geq1.%\nonumber
\end{equation}

§.§ Proof of Prop. <ref>

To prove this we invoke Theorem (3.1) in <cit.> that proves the stability of certain exhaustive service policies with state dependent routing. We first require some more notation.

We denote by $S(t)$ the queue in service during slot $t$, and set $S(t)=0$ if the server is idling at some queue (which from Prop. <ref>, has to be empty) during some slot. We denote by $W_n$, the time taken by the server to begin the $n^{th}$ service. By this we mean the time taken by the server to find a non empty queue after serving some queue. So, if the incumbent is non empty, $W_n=0$ since the server simply begins serving the next packet in the queue served in the previous slot without switching away from it. Otherwise the server begins to search for a non empty queue to begin a busy period. Specifically, if $Q_{S(0)}(0)=0$, then $W_1$ is the time taken to find a non empty queue. During this period, the server may have visited several empty queues.

Assume the underlying probability space is denoted by $\left(\Omega,\mathcal{F},P\right)$

and let

\begin{equation}
\mathcal{F}_n:=\sigma\left(\bigg\{ \left[ Q_1(t),\cdots,~Q_N(t),~S(t)\right],~t\leq n\bigg\}\right),~n\geq0,\nonumber
\end{equation}

be the filtration describing the history of the system. Let $A_i[t]$ be the number of arrivals to queue $i$ until and including time $t$, and $A[t]=\sum_{i=1}^NA_i[t]$, the total number of arrivals to the system over the same duration.

The proof of Theorem (3.1) in <cit.> relies on two assumptions[Eqn. (2.3) and Eqn. (2.4) in <cit.>.] that we show are satisfied in our case. Firstly, that there exists $w>0$ such that

\begin{equation}
\mathbb{E}\left[W_1|\mathcal{F}_0\right]<w,~P-a.s.~\text{on}~\left\lbrace Q_{S(0)}=0\right\rbrace,
\label{eqnSLQunequalAssumption1}
\end{equation}

and secondly that there exists some $p>0$ such that

\begin{equation}
P\left(A(W_1)=0|\mathcal{F}_0\right)>p,~P-a.s.~\text{on}~\left\lbrace Q_{S(0)}=0,\sum_{i=1}^NX_i(0)>0\right\rbrace.
\label{eqnSLQunequalAssumption2}
\end{equation}

In other words, (<ref>) means that if the system starts out empty, the time taken to find a non empty queue under the policy being considered, should have a finite mean. (<ref>), on the other hand, refers to the fact that when the system starts off non empty and the server is at an empty queue at time $0$, the probability of $0$ arrivals in $W_1$ is positive.

First note that on $\{Q_{S(0)}=0\}$, $W_1\geq1$, and let $\lambda_{min}=\min_{1\leq i\leq N}\lambda_i$ be the smallest arrival rate which, by assumption is strictly positive. The first assumption is satisfied, since

\begin{eqnarray}
\mathbb{E}\left[W_1|\mathcal{F}_0\right]&=&\sum_{k=1}^\infty P\{W_1\geq k|\mathcal{F}_0\}\nonumber\\
&\stackrel{(*a)}{\leq}&\sum_{k=1}^\infty (1-\lambda_{S(k)})^k\nonumber\\
&\leq&\sum_{k=1}^\infty (1-\lambda_{min})^k\nonumber\\
\end{eqnarray}

Inequality $(*a)$ is true, since, for the walking time to be at least $k$, the $k^{th}$ polled queue, i.e., $S(k)$, must be empty. Since on $\{Q_{S(0)}=0\}$ the system also starts off empty, this probability is $(1-\lambda_{S(k)})^k$. To prove (<ref>), first define  $p_k=P\{W_1=k|\mathcal{F}_0\}$.

\begin{eqnarray*}
P\{A(W_1)|\mathcal{F}_0\}&=&\sum_{k=1}^\infty P\{A(k)=0|\mathcal{F}_0, W_1=k\} P\{W_1=k|\mathcal{F}_0\}\\
&=&\sum_{k=1}^\infty P\{A(k)=0|\mathcal{F}_0, W_1=k\} p_k.\\
&=&\sum_{k=1}^\infty \left(\sum_{i=1}^N\left(1-\lambda_i\right)^k\right) p_k.
\end{eqnarray*}

But on $\{X_{S(0)}=0\}$, $p_1>(1-\lambda_{min})~a.s.$ So,

\begin{eqnarray*}
&&+\sum_{k=2}^\infty \left(\sum_{i=1}^N\left(1-\lambda_i\right)^k\right) p_k\\
\end{eqnarray*}

With both (<ref>) and (<ref>) satisfied, we note that Theorem (3.1) in <cit.> is proved under a much more general model, where the behavior of the system is influenced by another process $U(t),t\geq0$, that takes values in some measurable space $\left(\mathbf{U},\mathcal{U}\right)$. Setting $\mathbf{U}=\mathbb{N}^N$ and $U(t)=V(t)$, the proof is complete.

§.§ LEQ in Symmetric Systems

Under symmetry (Eqn. (<ref>)), $\argmax{1\leq i\leq N}\lambda_iV_i(t)=\argmax{1\leq i\leq N}V_i(t)$ and the policy reduces to a cyclic exhaustive service policy, as can be seen from the following example.

Consider the scenario with 4 queues in the system and suppose that at the beginning of Queue $1$'s service, $\mathbf{V} = [0, v_2, v_3, v_4]$, with $v_2 > v_3 > v_4$. At the end of Queue $1$'s service, the vector changes to $\mathbf{V}' = [0, v_2', v_3', v_4']$, but the ordering is still preserved, i.e., $v'_2 > v'_3 > v'_4 > v'_1=0$. Hence, Queue 2 is chosen for service next. But at the end of queue 2's service, once again, we see that $v''_3 > v''_4 > v''_1$, as it was at the beginning of Queue 2's service, and Queue 3 is chosen, after which queue 4 is chosen followed by queue 1 and this process repeats. We see that under symmetry, LEQ induces a cyclic service system.  This policy is discussed in detail in Sec. <ref>.
where we will, in fact, show it to be mean delay optimal in symmetric systems. This also helps bolster our confidence in the LEQ policy itself. We now explore in greater detail the behavior of the LEQ policy in symmetric systems.

§.§ Proof of Thm. <ref>

In this section, we return to the system discussed Sec.<ref>, i.e., one that is not necessarily symmetric[Proving stability for this system obviously proves stability in the symmetric system.]. The analysis proceeds along the lines of the proof of the theorem in <cit.>. We will be looking at the system's state only at the epochs at which the server begins its visit to a queue.

With a slight abuse of notation, we define this system's state is by
$\mathbf{Q}(n)=\left[Q_1(n),~Q_2(n),\dots,Q_N(n)\right]^T,n\geq 1$ is the vector of queue lengths
at the $n^{th}$ switching instant (at which the server visits the $n^{th}$ queue), $I(n)$ is the identity
of the $n^{th}$ queue polled.
Clearly, $\mathbf{s}(n)\in\mathbb{N}^N\times I$, and
this process is embedded at the instants at which the server arrives at a queue.

Further, the number of arrivals to queue $k$ in $t$ time-slots is denoted by $A_k(t)$ and
the length of the $n^{th}$ busy period starting with $l$ packets by $G_n(l)$. Also,

\[
\begin{cases}
I(n)+1~~\text{if}~1\leq n\leq N-1\\
\end{cases}
\]

Consequently, when

* $j\neq I(n)$

\[
\begin{cases}
\end{cases}
\]

* $j=I(n)$

\begin{equation}
\end{equation}

The mean duration of a busy period, $\mathbb{E}B(I(n))$ of queue $I(n)$ beginning with one
packet is found by observing that

\begin{eqnarray*}
\hspace{-2.0cm}
\mathbb{E}B(I(n))&=&\left[1\times\lambda_{I(n)}+\{1+\mathbb{E}G_n(l)\}\{1-\lambda_{I(n)}\}\right].\nonumber\\
\Rightarrow\mathbb{E}B(I(n))&=&\frac{1}{1-\lambda_{I(n)}}.%\hspace{4.5cm}%\text{Therefore,}
\end{eqnarray*}

Hence, since $G_n(l)$ begins with $l$ packets instead of one,

\begin{eqnarray}
\hspace{-1.0cm}
\mathbb{E}G_n(l)&=&l\times\left[1\times\lambda_{I(n)}+\{1+\mathbb{E}G_n(l)\}\{1-\lambda_{I(n)}\}\right]\nonumber\\
&\Rightarrow &\mathbb{E}A_j\left(G_n(l)\right)=\frac{\lambda_j}{1-\lambda_{I(n)}}l~\forall j\neq I(n)\nonumber\\%\hspace{3.25cm}
&\Rightarrow &\mathbb{E}\sum_{j\neq I(n)}A_j\left(G_n(l)\right)=\frac{\rho-\lambda_{I(n)}}{1-\lambda_{I(n)}}l.%\hspace{4.75cm}
\label{expBusy}
\end{eqnarray}

We will now show that $\rho=\sum_{i=1}^N\lambda_i<1$ is a sufficient condition for stability.

Clearly, $\{\mathbf{Q}_n, n\geq 1\}$, is an irreducible DTMC. However,

it is not time homogeneous since, as (<ref>) shows, the transition
probabilities depend on the queue being served, i.e., on $I(n)$. Hence, as defined in
<cit.>, the system is said to be stable if the $N$ irreducible,
homogeneous DTMCs $\{\left[\mathbf{Q}(nN+k),k\right], n\geq 1, 1\leq k\leq N, i\in\{1,2\}\}$
are all ergodic.

Now, from the definition of $Q_j(n+1)$, we see that

\begin{eqnarray*}
\hspace{-1.5cm}
\mathbb{E}\left[\sum_{j=1}^NQ_j(n+1)|\mathbf{Q}(n)\right]&\leq &\sum_{j=1}^NQ_{j}(n)+\rho\\
&&~\text{where $h_{I(n)}=\frac{1}{1-\lambda_{I(n)}}$},%\hspace{-1.8cm}
\end{eqnarray*}

which means that

\begin{eqnarray*}
\hspace{-2.0cm}
\mathbb{E}\left[\sum_{j=1}^NQ_{j}(n+2)|\mathbf{Q}(n)\right]&=&\mathbb{E}\left[\mathbb{E}\left[\sum_{j=1}^NQ_{j}(n+2)\mid\mathbf{Q}(n+1)\right]\mid\mathbf{Q}(n)\right]\nonumber\\
&\leq &\mathbb{E}\bigg[\sum_{j=1}^NQ_{j}(n+1)+\rho\\
&&-(1-\rho)h_{I(n+1)}Q_{I(n+1)}(n+1)\mid \mathbf{Q}(n)\bigg] \nonumber \\
&\leq &\mathbb{E}\bigg[\sum_{j=1}^NQ_{j}(n+1)\mid \mathbf{Q}(n)\bigg]+\rho\\
\end{eqnarray*}

Proceeding similarly, we get

\begin{eqnarray*}
\mathbb{E}\left[\sum_{j=1}^NQ_j(n+2N)\mid \mathbf{Q}(n)\right]&\leq&\sum_{j=1}^NQ_j(n)+2N\rho\nonumber\\
\end{eqnarray*}

\begin{eqnarray}
\Rightarrow\mathbb{E}\left[\sum_{j=1}^NQ_j(n+2N)-\sum_{j=1}^NQ_j(n)\mid \mathbf{Q}(n)\right]\leq 2N\rho\nonumber\\
\label{NslotDrift}
\end{eqnarray}

Clearly, the RHS of (<ref>) is at most $2N\rho$, and if for even one $1\leq k\leq 2N$ and
$\epsilon>0$, $Q_{I(n+k)}(n)>\frac{N\rho\epsilon}{(1-\rho)h(I(n+k))}$, then
$\mathbb{E}\left[\sum_{j=1}^NQ_j(n+2N)-\sum_{j=1}^NQ_j(n)\mid \mathbf{Q}(n)\right]<-\epsilon$. Hence, by the
Foster-Lyapunov criterion (<cit.>, Thm. 2.2.3), we see that
$\{\left[\mathbf{Q}(nN+k),k,i\right], n\geq 1\}$ is positive recurrent for every
$1\leq k\leq N$, and $i\in\{1,2\}$. Being irreducible DTMCs as well, it is also ergodic.

§.§ Formulating the MDP

* State Space: The state of the system at time $n\geq1$ is the vector

\begin{equation}
\end{equation}

So $s(n)\in\mathbb{N}\times\mathbb{N}^N\times\mathbb{N}^{N-1}\times I$.

* Action Space: The action space $\mathbb{A}=I$ for all states.

* Initial distribution on the State Space: We assume that the system begins empty and so, the initial
distribution $D$ is simply $\mathbb{I}\{s(0)\}$, where $s(0)=\left[q,\mathbf{V}(0),\mathbf{r}(0),i_0\right],$
is given and hence, known.

* History: Since the state is observable, the initial history is nothing but the initial state,
which is supplied as the initial information.

\begin{equation}
\end{equation}

At time $t$, the history provides the complete picture of successive observations and control actions
chosen so far; for $n\geq1$:

\begin{equation}
h_n=\left(s(0), a(0),\dots,s(n-1),a(n-1),s(n)\right),
\end{equation}

where the action taken at time $n$, $a(n)\in\mathbb{I},\forall n\geq0.$

* Policies: In general, a policy is a sequence of conditional distributions $\xi=\{\xi_n\}$ such that for each $n$, $\xi_n$ is a distribution on $\mathbb{A}$ given $h_n$. As mentioned before, we restrict attention to policies that serve any queue $j$ with $r_j(t)>0$ first and then return to serve the incumbent. As a consequence of Prop. <ref>, we also restrict to the case where if $q>0$ then we serve $i$ again.

* Transition Law: We denote the current action by $u_n$ and distinguish two cases:

* $r_i(n)\geq1$ for some $i\in I-{u_{n-1}}$. Then,
\begin{eqnarray}
\hspace{-1.00cm}
q_{u_n}(s(n),s(n+1))&=&\mathbb{I}_{\left\lbrace r_i(n+1)=r_i(n)-1\right\rbrace}\times\nonumber\\
&&\Pi_{j\neq i}\mathbb{I}_{\left\lbrace r_j(n+1)=r_j(n)\right\rbrace}\mathbb{I}_{\left\lbrace u_{t}=i\right\rbrace}\times\nonumber\\
\end{eqnarray}

\[
\hspace{-2.0cm}   {I}_{u_n}\{V_k(n),V_k(n+1)\}:=
\begin{cases}
1~\text{if}~V_k(n+1)=V_k(n)+1~\text{and}~k\neq u_n,\\
1~\text{if}~V_k(n+1)=V_k(n)=0~\text{and}~k=u_n,~\text{and }\\
\end{cases}
\]

\[
\hspace{-1.0cm}   q'_{u_n}(Q_k(n),Q_k(n+1)):=
\begin{cases}
\lambda~~~~~~\text{if}~Q_k(n+1)=Q_k(n)+1\\
~~~~~~~\text{OR, if}~Q_k(n+1)=(Q_k(n)-1)^++1\\~~~~~~~~\text{and }k=i,\\
~~~~~~~\text{OR, if}~Q_k(n+1)=(Q_k(n)-1)^++0\\~~~~~~~~\text{and }k=i,\\
\end{cases}
\]

* $\mathbf{r}(n)=\mathbf{0}$. Then,
\begin{eqnarray}
q_{u_n}(s(n),s(n+1))&=&\Pi_{j\in I}\mathbb{I}_{\left\lbrace r_j(n+1)=0\right\rbrace}\times\nonumber\\ &&\left(\Pi_{k=1}^N\mathbb{I}_{u_n}\{V_k(n),V_k(n+1)\}\right)\times\nonumber\\
\end{eqnarray}

\[
\hspace{-2.0cm}   {I}_{u_n}\{V_k(n),V_k(n+1)\}:=
\begin{cases}
1~\text{if}~V_k(n+1)=V_k(n)+1~\text{and}~k\neq u_n,\\
\end{cases}
\]

\[
\hspace{-1.0cm}   q'_{u_n}(Q_k(n),Q_k(n+1)):=
\begin{cases}
\lambda~~~~~~\text{if}~Q_k(n+1)=Q_k(n)+1~\text{and}~k\neq u_n,\\
~~~~~~~\text{OR, if}~Q_k(n+1)=(Q_k(n)-1)^++1\\~~~~~~~~\text{and }k=u_n,\\
1-\lambda~\text{if}~Q_k(n+1)=Q_k(n)+0~\text{and}~k\neq u_n,\\
~~~~~~~\text{OR, if}~Q_k(n+1)=(Q_k(n)-1)^++0\\~~~~~~~~\text{and }k=u_n,\\
\end{cases}
\]

* Single Stage Cost: This gives the expected cost over the current step when the current state and
action are known.

\begin{eqnarray}
\hspace{-1.00cm}
c(s(n),u_n)&=&\mathbb{E}\left[\sum_{i=1}^N Q_i(n)|s_n\right]\nonumber\\
&=&Q_{u_{n-1}}(n)+\lambda\sum_{j\neq u_{n-1}}V_j(n)+\sum_{i\in I}R_i(n),\hspace{0.9cm}
\end{eqnarray}

which is the expected sum of the current queue lengths conditioned on the current state.

Recall that the optimal cost (Eqn. (<ref>)) is given by

\begin{equation}
\end{equation}

It is to be noted that $J^*(s(0))$ on the R.H.S of (<ref>) exists for every initial state $s(0)$. Since arrivals are IID Bernoulli variables, the single stage cost can increase at most linearly with time, while the discount factor $\alpha^n$ decreases exponentially and dominates.

The Bellman Optimality equations <cit.> associated with this MDP formulation are as follows (recall from Eqn. (<ref>) that we denote $J^*(q; \mathbf{V}; \mathbf{r}; i)$ by $J_i^*(q; \mathbf{V}; \mathbf{r})$). When $\mathbf{r}=\mathbf{0}$,

\begin{eqnarray*}
J^*_i(q>0; \mathbf{V}; \mathbf{r}=\mathbf{0}) &=& q+\lambda \sum_{k \neq i} V_k + \alpha \mathbb{E} J^*_i\left(q-1+A; \right.\\
&& \left. V_i=0, \mathbf{V}_{-i}+\mathbf{1}; \mathbf{r}=\mathbf{0}\right), \\
J^*_i(q=0; \mathbf{V}; \mathbf{r}=\mathbf{0}) &=& \lambda \sum_{k \neq i} V_k +\alpha \min_{j \neq i} \mathbb{E} J^*_j\left(B(V_j);\right.\\
&& \left. V_j=0, \mathbf{V}_{-j}+\mathbf{1}; \mathbf{r}=\mathbf{0} \right),%\hspace{1.00cm}
\end{eqnarray*}

where $A$ is a generic Bernoulli($\lambda$) random variable,
$\mathbf{V}_{-i}=[V_1,\dots,V_{i-1},V_{i+1},\dots,V_N]$ and $\mathbf{1}\in\mathbb{R}^{(N-1)}$ is the
vector with 1's at all coordinates. Finally, if random variable $C$ is distributed
Binomial($V_j,\lambda$), $B(V_j)$ is a random variable whose distribution is the same as that of

If $r_j\geq1$ for some $j\in I-\{i\}$, the server first serves the $\sum_{j\neq i}r_j$ packets and then returns to queue $i$. Let $\tilde{R}=\sum_{j\neq i}r_j$, $L_{-i}=\sum_{j\neq i}V_j$, and $\tilde{L}_{-i}=\sum_{k=1}^{\tilde{R}}\alpha^{(\tilde{R}-k)}(L_{-i}+Nk)$. Clubbing all these $\tilde{R}$ slots, we get:

\begin{eqnarray}
J^*_i(q>0; \mathbf{V}; \mathbf{r}) &=& q\sum_{k=0}^{\tilde{R}-1}\alpha^k+\lambda\tilde{L}_{-i}+ \alpha^{\tilde{R}}\mathbb{E} J^*_i\left(q-1+\tilde{A};\right.\nonumber\\
&& \left. V_i=0, \mathbf{V}_{-i}+\tilde{R}\mathbf{1}; \mathbf{r}=\mathbf{0}\right) \nonumber\\%\hspace{4cm}
J^*_i(q=0;\mathbf{V};\mathbf{r}) &=& \lambda\tilde{L}_{-i}+\alpha^{\tilde{R}}\mathbb{E} J^*_j\left(\tilde{A}; V_j=0, \right.\nonumber\\
&& \left.\mathbf{V}_{-j}+\tilde{R}\mathbf{1};\mathbf{r}=\mathbf{0}\right),\hspace{0.75cm}
\label{eqnBellmanWhenRPositive}
\end{eqnarray}

where $\tilde{A}$ is a Binomial$\left(\tilde{R},\lambda\right)$ random variable and represents the number of arrivals over $\tilde{R}$ slots.

§.§ Proof of Thm. <ref>

Before we prove that cyclic exhaustive service solves the discounted cost MDP described in Sec. <ref>, we require an intermediate result on monotonicity of the optimal cost function.

§.§.§ Monotonicity of $J^*(\cdot)$

Consider, once again, the Bellman equations.

\begin{eqnarray}
J^*_i(q>0; \mathbf{v}; \mathbf{r}=\mathbf{0})&=& q+\lambda \sum_{k \neq i} v_k + \alpha \mathbb{E} J^*_i\left( q-1+A; \right.\nonumber\\
&& \left. v_i=0, \mathbf{v}_{-i}+\mathbf{1}; \mathbf{r}=\mathbf{0} \right),\nonumber\\
J^*_i(q=0; \mathbf{v}; \mathbf{r}=\mathbf{0}) &=& \lambda \sum_{k \neq i} v_k + \alpha \min_{j \neq i} \mathbb{E} J^*_j \left(B(v_j); \right.\nonumber\\
&& \left. v_j=0, \mathbf{v}_{-j}+\mathbf{1}; \mathbf{r}=\mathbf{0} \right),
\label{jStarR0}
\end{eqnarray}

where, we recall that if random variable $C$ is distributed Binomial($v_j,\lambda$), $B(v_j)$ is a random variable whose distribution is the same as that of $(C-1)^++A$ and $A$ is a Bernoulli random variable with $\mathbb{E}A=\lambda$. We shall now prove that the optimal cost function is monotonically increasing in the first coordinate
when $\mathbf{r}=\mathbf{0}$ (this is really the only scenario where decisions might have to be taken).

When $\mathbf{r}=\mathbf{0}$, the optimal $\alpha-$discounted cost function, $J^*$ satisfies

\begin{equation}
J^*(q_1,\mathbf{v},\mathbf{0})\geq J^*(q_2,\mathbf{v},\mathbf{0}),~\forall q_1\geq q_2,~\text{and}~\mathbf{v}\in\mathbb{N}^N.
\end{equation}

Let $\mathbb{M}$ denote the set of all functions $g:\mathbb{S}\mapsto\mathbb{R}_+$.
Considering the R.H.S of equations(<ref>), we define the Dynamic Programming Operator $T:\mathbb{M}\mapsto\mathbb{M}$
as in <cit.> as follows. For any $g\in\mathbb{M}$,

\begin{eqnarray*}
(Tg)_i(q>0,\mathbf{v},\mathbf{r}) &=& q+\lambda \sum_{k \neq i} v_k + \alpha \mathbb{E} g_i\left(q-1+A;\right. \\
&& \left. v_i=0, \mathbf{v}_{-i}+\mathbf{1}; \mathbf{r}=\mathbf{0}\right),\nonumber\\
(Tg)_i(q=0,\mathbf{v},\mathbf{r}) &=& \lambda \sum_{k \neq i} v_k + \alpha \min_{j \neq i} \mathbb{E} g_j\left( B(v_j);\right.\\
&& \left. v_j=0, \mathbf{v}_{-j}+\mathbf{1}; \mathbf{r}=\mathbf{0} \right),
\end{eqnarray*}

Consider any $g\in\mathbb{M}$ that is increasing in $q$, i.e.,
$g(q+k,\mathbf{v},\mathbf{r})\geq g(q,\mathbf{v},\mathbf{r}),~\forall k\geq1$.

* $q\geq1$:

\begin{eqnarray}
\hspace{-1.50cm}
(Tg)_i(q+k,\mathbf{v},\mathbf{r}) &=& (q+k)+\lambda \sum_{k \neq i} v_k + \alpha \mathbb{E} g_i\bigg(q+k-1+A;\nonumber\\
&& v_i=0, \mathbf{v}_{-i}+\mathbf{1}; \mathbf{r}=\mathbf{0}\bigg),\nonumber\\
&\geq& q+\lambda \sum_{k \neq i} v_k + \alpha \mathbb{E} g_i\bigg(q-1+A; \nonumber\\
&& v_i=0, \mathbf{v}_{-i}+\mathbf{1}; \mathbf{r}=\mathbf{0}\bigg),\nonumber\\
&=& (Tg)_i(q,\mathbf{v},\mathbf{r}).\nonumber
\end{eqnarray}

This shows that the operator $T$ preserves monotonicity for $q\geq1$. Proposition 2.1 of <cit.>
shows that value iteration, starting from  any $g\in\mathbb{M}$, converges to the
fixed point of the operator $T$, namely $J^*$, which also resides in
$\mathbb{M}$. Hence, we see that $J^*$ is monotonically increasing in $q$ when $q\geq1$.

* $q=0$:
\begin{eqnarray}
\hspace{-1.50cm}
J^*_i(0; \mathbf{v}; \mathbf{r}=\mathbf{0}) &=& \lambda\sum_{k \neq i} v_k+\alpha\min_{j\neq i}\mathbb{E} J^*_j \bigg( B(v_j);v_j=0, \mathbf{v}_{-j}+\mathbf{1}; \mathbf{r}=\mathbf{0} \bigg),\nonumber\\
&\stackrel{\dagger}{=}& \lambda\sum_{k \neq i} v_k+\alpha\min_{j\in I}\mathbb{E} J^*_j \bigg( B(v_j);v_j=0, \mathbf{v}_{-j}+\mathbf{1}; \mathbf{r}=\mathbf{0} \bigg),\nonumber\\
&=& \lambda\sum_{k \neq i} v_k\nonumber\\
&& +\alpha\min\left\lbrace\min_{j\neq i}\mathbb{E} J^*_j \bigg( B(v_j);v_j=0, \mathbf{v}_{-j}+\mathbf{1}; \mathbf{r}=\mathbf{0} \bigg),\right.\nonumber\\
&& \left. \mathbb{E}J^*_i\bigg(A; v_i=0,\mathbf{v}_{-i}+\mathbf{1}; \mathbf{r}=\mathbf{0}\bigg)\right\rbrace,\nonumber\\
&\leq& 1+\lambda\sum_{k \neq i} v_k+\alpha\mathbb{E}J^*_i\bigg(A; v_i=0,\mathbf{v}_{-i}+\mathbf{1}; \mathbf{r}=\mathbf{0}\bigg),\nonumber\\
&=& J^*_i(1; \mathbf{v}; \mathbf{r}=\mathbf{0}).\nonumber
\end{eqnarray}

In equality $\dagger$ minimization over $I\setminus\{i\}$ is the same as minimization over all $I$, since attempting to schedule queue $i$ would result in slot wastage and idling, which, as Prop. <ref> shows is suboptimal and hence, will not result in a smaller cost.

§.§.§ Proof of Thm. <ref>

In this section, we use $\mathbf{r}_{-n}$ instead of $\mathbf{r}$ to explicitly show which queues' $r_j$'s are known to the server. So, $\mathbf{r}_{-n}$ includes $r_j~\forall j\neq n$. Let D be a $Bin(v_n-v_m-1,\lambda)$ random variable. Wherever it becomes necessary to clarify the measure with respect to (w.r.t) which the expectation is being computed, we shall use $\mathbb{E}_\mu$ to explicitly denote expectation w.r.t the probability mass function (p.m.f) $\mu$. Let $\nu_m$ denote the p.m.f of $B(v_m)$, $\nu_n$ that of $B(v_m)$ and $\mu$ that of $D$, i.e., $Bin(v_n-v_m-1,\lambda)$. Also, define $\chi\stackrel{\Delta}{=}\nu_m\ast \mu$ (here, $\ast$ denotes convolution) and $\beta\stackrel{\Delta}{=}\nu_m\times \mu$ (the product measure).
Now, with $v_n-v_m>0$, we can write:

\begin{eqnarray}
&& \mathbb{E}_{\nu_n} \bigg[ J^*_n\bigg( B(v_n);v_n=0, \mathbf{v}_{-n}+\mathbf{1}; \mathbf{r}_{-n}=\mathbf{0} \bigg)\bigg] \nonumber\\
&& ~~~~~ - \mathbb{E}_{\nu_m} \bigg[ J^*_m \bigg( B(v_m);\mathbf{v}_{-m}+\mathbf{1}; \mathbf{r}_{-m}=\mathbf{0} \bigg) \bigg] \nonumber\\
&&\stackrel{a}{\leq}\mathbb{E}_{\chi} \bigg[ J^*_n \bigg( B(v_m)+D;\mathbf{v}_{-n}+\mathbf{1}; \mathbf{r}_{-n}=\mathbf{0} \bigg)\bigg] \nonumber\\
&& ~~~~~ - \mathbb{E}_{\nu_m} \bigg[ J^*_m \bigg( B(v_m);\mathbf{v}_{-m}+\mathbf{1}; \mathbf{r}_{-m}=0 \bigg) \bigg]\\
&&= \mathbb{E}_{\beta} \bigg[ J^*_n \bigg( B(v_m)+D;\mathbf{v}_{-n}+\mathbf{1}; \mathbf{r}_{-n}=\mathbf{0} \bigg) \nonumber\\
&& ~~~~~ - J^*_m \bigg( B(v_m);\mathbf{v}_{-m}+\mathbf{1}; \mathbf{r}_{-m}=0 \bigg) \bigg]\\
&&\stackrel{\dag}{=} \sum_{r=1}^{v_n-v_m-1} P(r)~\mathbb{E} \bigg[ J^*_n \bigg( B(v_m)+r;\mathbf{v}_{-n}+\mathbf{1}; \mathbf{r}_{-n}=\mathbf{0} \bigg)\nonumber\\
&& ~~~~~ - J^*_m \bigg( B(v_m);\mathbf{v}_{-m}+\mathbf{1}; \mathbf{r}_{-m}=\mathbf{0} \bigg) \bigg| D=r \bigg]  \nonumber\\
&& ~~~~~ + P(0)~\mathbb{E} \bigg[ J^*_n \bigg( B(v_m);\mathbf{v}_{-n}+\mathbf{1}; \mathbf{r}_{-n}=\mathbf{0} \bigg) \nonumber\\
&& ~~~~~ - J^*_m \bigg( B(v_m);\mathbf{v}_{-m}+\mathbf{1}; \mathbf{r}_{-m}=\mathbf{0} \bigg) \bigg| D=0 \bigg]  \nonumber\\
&&\stackrel{b}{\leq} \sum_{r=1}^{v_n-v_m-1} P(r)~\mathbb{E} \bigg[ J^*_n \bigg( B(v_m)+r;\mathbf{v}_{-n}+\mathbf{1}; \mathbf{r}_{-n}=\mathbf{0} \bigg)\nonumber\\
&& ~~~~~ -J^*_m\bigg( B(v_m);\mathbf{v}_{-m}+\mathbf{1}; \mathbf{r}_{-m}=\mathbf{0} \bigg) \bigg| D=r \bigg]
\label{eqn:outline1}
\end{eqnarray}

Before we explain inequality $a$ we will require the following result.

\begin{equation}
B(v_n)\stackrel{st}{\leq}B(v_m)\ast D,
\end{equation}

where, as before, $st$ refers to stochastic ordering and $\ast$ denotes convolution.

Refer Sec. <ref>.

Since nondecreasing functions of stochastically ordered random variables are themselves stochastically ordered, inequality $a$ follows from Lem. <ref> and the monotonicity of $J^*$ in the first coordinate as proved in Lemma.<ref> in Sec. <ref>. In equality $\dag$, $P(r)= Pr\{D=r\}$, as mentioned before.

To explain inequality $b$ we use the following observation about the difference between the state in which our controlled Markov chain (CMC) actually is and what the decision maker knows about that state.

Note that

the lemma that follows is true for CMCs in general. Let $\mathcal{X}$ (a countable set) be the state space on which the CMC actually evolves. The MDP is then defined on the set of all probability mass functions, or p.m.fs on $\mathcal{X}$ denoted by $\mathcal{P}(\mathcal{X}):= \{\mathbf{p}:\forall x\in \mathcal{X},~0\leq p(x)\leq1, ~\text{and} \sum_{x\in\mathcal{X}} p(x)=1\}$. Let the action space be denoted by $\mathcal{A}$.

Let $\mu\in\mathcal{P}(\mathcal{X})$ be a probability mass function, or p.m.f, on $\mathcal{X}$ (this p.m.f can be degenerate, i.e., $1$ at some $x\in\mathcal{X}$ and $0$ elsewhere) and $\pi^*$ any stationary optimal policy (assuming one exists). Denote the action space when the state is $\mu$ by $A_\mu\subset\mathcal{A}$ and the state of the CMC at time $0$ by $X_0\in\mathcal{X}$. Finally, let $c:\mathcal{P}(\mathcal{X})\times\mathcal{A}\mapsto \mathbb{R}_+$ denote the single stage cost and $\mu_o=\mu$. Then[The discount factor is denoted by $\alpha$.],

\begin{eqnarray}
\mathbb{E}^{\pi^*}_{\mu}\bigg[\sum_{k=0}^\infty \alpha^k c(\mu_k,A_k)\bigg| X_0=x\bigg]\geq
\mathbb{E}^{\pi^*}_{\delta_x}\bigg[\sum_{k=0}^\infty  \alpha^k c(\mu_k,A_k)\bigg],
\label{eqnCondition2Know}
\end{eqnarray}

where $\mu_k\in\mathcal{P}(\mathcal{X}),~A_k\in A_{\mu_k},\text{ for all } k\geq0$.

Intuitively speaking, the L.H.S of (<ref>) is an expectation over the subset of sample paths over which $X_0=x$ and when decision-making entity (in our case, the centralized scheduler) begins with knowledge of some p.m.f $\mu$ over the state. Clearly, this does not mean that the entity knows that $X_0=x$. But the expectation on the R.H.S indicates that the scheduler begins knowing that $X_0=x$, hence the $\delta_x$ in the subscript. Obviously, the action taken by the decision-making entity when it has complete knowledge of the state (represented by $\delta_x$) cannot be worse than that taken when there is ambiguity about the state (represented by some p.m.f $\mu$ which might not be $\delta_x$). For details, refer Sec. <ref> in the Appendix.

In short, the lemma says that while transitioning from conditioning to knowledge, the optimal cost cannot increase.

Getting back to proving Eqn. (<ref>), Lem. <ref> immediately gives us inequality $c$ below, because $D=0$ essentially means that queue $n$'s distribution is $Bin(v_m,\lambda)$. Inequality $c$ is explained in more detail after (<ref>).

\begin{eqnarray}
&&\mathbb{E} \bigg[J^*_m \bigg( B(v_m);\mathbf{v}_{-m}+\mathbf{1}; \mathbf{r}_{-m}=\mathbf{0} \bigg) \bigg| D=0 \bigg]\nonumber\\
&\stackrel{c}{\geq}& \mathbb{E} \bigg[ J^*_m \bigg( B(v_m);\mathbf{v}_{-\{m,n\}}+\mathbf{1}, v_n=v_m+1; \mathbf{r}_{-m}=\mathbf{0} \bigg)\bigg]\nonumber\\
&\stackrel{d}{=}& \mathbb{E} \bigg[ J^*_n \bigg( B(v_m);\mathbf{v}_{-n}+\mathbf{1}; \mathbf{r}_{-n}=\mathbf{0} \bigg)\bigg]\nonumber\\
&\stackrel{e}{=}& \mathbb{E} \bigg[ J^*_n \bigg( B(v_m);\mathbf{v}_{-n}+\mathbf{1}; \mathbf{r}_{-n}=\mathbf{0}\bigg)\bigg| D=0\bigg].
\label{eqnUsingConditionToKnowForDEqualTo0}
\end{eqnarray}

When the scheduler knows that both queue $m$ and queue $n$ have the same number of packets, viz, $B(v_m)$, serving either queue gives the same expected cost, since both queues have statistically similar arrival processes. So, equality $d$ follows from the fact that two queues of length Bin$(v_m,\lambda)$, with equal arrival rates are stochastically indistinguishable. The R.H.S of equality $e$ is the expected cost of serving queue $n$, when the server knows that queue $m$ is distributed $Bin(v_m,\lambda)$ and the backlog of queue $m$ is actually a $Bin(v_m,\lambda)$ random variable, but that is exactly the R.H.S of equality $d$! Contrast this with the L.H.S of inequality $c$, where the server only knows that queue $n$ is distributed $Bin(v_n,\lambda)$, while conditioning on $D=0$ means that queue $n$ is actually distributed $Bin(v_m,\lambda)$. So,

\begin{eqnarray}
\hspace{-1.00cm}
&& \mathbb{E} \bigg[ J_n^* \bigg( B(v_m)+r;\mathbf{v}_{-n}+1; \mathbf{r}_{-n}=0 \bigg)\nonumber\\
&& ~~~~~ - J_m^* \bigg( B(v_m);\mathbf{v}_{-m}+1; \mathbf{r}_{-m}=0 \bigg) \bigg| D=0 \bigg]\leq0.
\label{eqnDEquals0}
\end{eqnarray}

Now, on to the R.H.S of inequality $b$. Invoking Lem. <ref> and noting that $r_n=r$ means the scheduler knows that queue $n$ has at least $r$ packets, we get

\begin{eqnarray}
&& \mathbb{E} \bigg[ J^*_m\bigg( B(v_m);\mathbf{v}_{-m}+\mathbf{1}; \mathbf{r}_{-m}=\mathbf{0} \bigg) \bigg| D=r \bigg] \nonumber\\
&\geq& \mathbb{E} \bigg[ J^*_m\bigg( B(v_m);\mathbf{v}_{-m}+\mathbf{1}; \mathbf{r}_{\{-m,n\}}=\mathbf{0}, r_n=r \bigg) \bigg] \nonumber \\
&\stackrel{f}{=}&\mathbb{E} \bigg[ J^*_n\bigg( B(v_m)+r; \mathbf{v}_{-n}+\mathbf{1}; \mathbf{r}_{-n}=\mathbf{0}\bigg)\bigg] \nonumber\\
&\stackrel{g}{=}&\mathbb{E} \bigg[ J^*_n\bigg( B(v_m)+r; \mathbf{v}_{-m}+\mathbf{1}; \mathbf{r}_{n}=\mathbf{0}\bigg)\bigg|D=r \bigg].
\end{eqnarray}

Equality $f$ is explained as follows. In the space of policies we are considering, a server always first serves all queues with positive $r$ and then returns to the incumbent. So, when it is known that $r_n=r$, the server will first serve the $r$ packets in queue $n$ and then return to queue $m$. But that will result in the same mean cost as serving queue $n$ exhaustively, when it is known that queue $n$'s backlog is distributed $\delta_r\ast Bin(v_m,\lambda)$. Equality $g$ uses the same logic as Equality $e$ in (<ref>).

\begin{align}
\mathbb{E} \bigg[ J_n^* \bigg( B(v_m)+r;\mathbf{v}_{-n}+1; \mathbf{r}_{-n}=0 \bigg) - J_m^* \bigg( B(v_m);\mathbf{v}_{-m}+1; \mathbf{r}_{-m}=0 \bigg) \bigg| D=r \bigg]\leq0, ~\forall 1\leq r\leq v_n-v_m.
\label{eqnDGreaterThan0}
\end{align}

From (<ref>) and (<ref>), the policy structure now follows.

§.§ Proof of Lem. <ref>

Given $k\geq1$ if $Z$ is a random variable with p.m.f Bin($k,\lambda$) we define $\tilde{B}(k)$ as the p.m.f of $(Z-1)^+$. Let $X_k~(k\geq1),$ and $Y_n~(n\geq1)$ be random variables with distributions $\tilde{B}(k)$, and Bin($n,\lambda$), respectively. In what follows, we will first show that

\begin{equation}
X_k+Y_n\stackrel{st}{\geq}X_{k+1}+Y_{n-1},~\forall k\geq1.
\label{eqnStochasticOrderPf1}
\end{equation}

Since the L.H.S of Eqn. <ref>, $X_k+Y_n\stackrel{d}{=}X_k+Y_1+Y_{n-1}$ (where $\stackrel{d}{=}$ denotes equality of distribution), it is sufficient to prove that

\begin{equation}
\label{eqnStochasticOrderPfEquivalent}
\end{equation}

We show this by proving that

\begin{equation}
P\{X_k+Y_1\leq l\}\leq P\{X_{k+1}\leq l-1\},~\forall l\in\{0,1,\dots,k\}.
\end{equation}

We consider several cases

* $l=0$

\begin{align}
P\{X_{k+1}\leq 0\}=(1-\lambda)^{k+1}+(k+1)(1-\lambda)^k\lambda
\end{align}

\begin{eqnarray}
P\{X_k+Y_1\leq 0\} &=& \left((1-\lambda)^{k}+k(1-\lambda)^{k-1}\lambda\right)(1-\lambda)\nonumber\\
&=& (1-\lambda)^k\left(1+(k-1)\lambda\right)\nonumber\\
&<& P\{X_{k+1}\leq 0\}.\nonumber
\end{eqnarray}

* $1\leq l\leq k-1$

\begin{align}
P\{X_{k+1}=l\}={k+1\choose l+1}  \lambda^{l+1}(1-\lambda)^{k-l},\nonumber
\end{align}

\begin{eqnarray}
P\{X_k+Y_1=l\} &=& {k\choose l+1}\lambda^{(l+1)}(1-\lambda)^{(k-l-1)}(1-\lambda)\nonumber\\
&& +{k\choose l}\lambda^l(1-\lambda)^{(k-l)}\lambda\nonumber\\
&=& \left({k\choose l+1}+{k\choose l}\right)\lambda^{l+1}(1-\lambda)^{(k-l)}\nonumber\\
&=& P\{X_{k+1}=l\}.\nonumber
\end{eqnarray}

Hence, in this case, $P\{X_{k+1}\leq l\}\geq P\{X_{k}+Y_1\leq l\}$.

* $l=k$

\begin{eqnarray}
&=& \lambda^{k+1}\nonumber\\
&=& P\{X_{k+1}=l\}.\hspace{2.6cm}\nonumber\\
\end{eqnarray}

Once again, $P\{X_{k+1}\leq k\}\geq P\{X_{k}+Y_1\leq k\}$.

This proves Eqn. <ref> and hence, Eqn. <ref>. By the same token, it is at once obvious that $X_k+Y_n\stackrel{st}{\geq}X_{k+1}+Y_{n-1}  \stackrel{st}{\geq}X_{k+2}+Y_{n-2} \dots \stackrel{st}{\geq}X_{k+n}$, which means that,

\begin{eqnarray}
\tilde{B}(k+n) &\stackrel{st}{\leq}& \tilde{B}(k)\ast Bin(n)\nonumber\\
\Rightarrow \tilde{B}(k+n)\ast Bin(1,\lambda) &\stackrel{st}{\leq}& \tilde{B}(k)\ast Bin(n)\ast Bin(1,\lambda)\nonumber\\
\Rightarrow B(k+n) &\stackrel{st}{\leq}& B(k)\ast\text{B}(n).
\label{eqnStochasticOrderingProofPMF}
\end{eqnarray}

Lem. <ref> follows by setting $v_m=k$ and $v_n=k+n$, in (<ref>).

§.§ Proof of Lem. <ref>

For every $a\in\mathcal{A}$ denote by $p_{a}(z,\nu)$ the stochastic transition kernel[Refer Chapter 4 of <cit.> for details.] from $\mathcal{P}(\mathcal{X})\times \mathcal{A}\mapsto \mathcal{P}(\mathcal{X})$. Such a kernel exists by Lem. 3.2 and Eqn. 3.7 in Chapter 4 of <cit.>. Now, observe that the R.H.S of <ref>

\begin{eqnarray}
\hspace{-1.00cm}
\mathbb{E}^{\pi^*}_{\delta_x}\bigg[\sum_{k=0}^\infty \alpha^k c(\mu_k,A_k)\bigg] &=& c(\delta_x,\pi^*(\delta_x))\nonumber\\
&& +\alpha\int_{\mathcal{P}(\mathcal{X})}\left(\bigg[\mathbb{E}^{\pi^*}_{\nu} \sum_{k=1}^\infty \alpha^{k-1} c(\mu_k,A_k)\bigg]\right.\nonumber\\
&& ~~~~~\left.\times p_{\pi^*(\delta_x)}(\delta_x,d\nu)\right)\nonumber\\
&\stackrel{\#1}{\leq}& c(\delta_x,a)\nonumber\\
&& + \alpha\int_{\mathcal{P}(\mathcal{X})}\bigg[\mathbb{E}^{\pi^*}_{\nu} \sum_{k=1}^\infty \alpha^{k-1}c(\mu_k,A_k)\bigg]p_{a}(\delta_x,d\nu),\nonumber
\end{eqnarray}

for all $a\in A_\mu.$ Inequality $\#1$ follows from the fact that $\pi^*$ is an optimal policy. Hence, the L.H.S of <ref>,

\begin{eqnarray}
\hspace{-1.00cm}
\mathbb{E}^{\pi^*}_{\mu}\bigg[\sum_{k=0}^\infty \alpha^k c(x_k,A_k) \mid  X_0 = x\bigg] &\stackrel{\#2}{=}& c(\delta_x,\pi^*(\mu))\nonumber\\
&&+\alpha\int_{\mathcal{P}(\chi)} \left(\bigg[\mathbb{E}^{\pi^*}_{\nu} \sum_{k=1}^\infty \alpha^{k-1} c(\mu_k,A_k)\bigg]\right.\nonumber\\
&& ~~~~~ \left.\times p_{\pi^*(\mu)}(\delta_x,d\nu)\right)\nonumber\\
&\geq& \mathbb{E}^{\pi^*}_{\delta_x}\bigg[\sum_{k=0}^\infty \alpha^k c(\mu_k,A_k)\bigg].\nonumber
\end{eqnarray}

Note that in the first term of the R.H.S of equality $\#2$, because of the conditioning on $\{X_0=x\}$ the CMC is in state $\delta_x$ which becomes the first argument of $c(\cdot,\cdot)$ and the controller or decision maker is only told $\mu$, which becomes the second argument of $c(\cdot,\cdot)$.

§.§ Solving the Time-Average Cost MDP

We use the technique described in <cit.> to show that the SLQ policy is
optimal for the long term time-averaged cost criterion as well. We consider a sequence of discount
factors $\{\alpha_n\}\uparrow1$ and the corresponding discounted optimal policies. We begin with the
following result:

(<cit.>) Let $\{\alpha_n\}$ be a sequence of discount
factors increasing to 1, and let $\pi^*_n$
be the associated sequence of discounted optimal stationary policies. There exists a
subsequence $\{\alpha_{n_k}\}$ and a stationary policy $\pi^*$ that is a limit point of $\pi^*_{n_k}$.

The proof of Lemma <ref> can be found in <cit.>. In our
case, the assertion is easily seen to be true, since the SLQ policy is optimal for every
$\alpha\in(0,1)$. To invoke the theorem in <cit.>, we need to first show
that the conditions assumed therein are true. Towards this end let us first limit our MDP's state space to
$S'=\mathbb{N}\times\mathbb{N}^N\times\mathbb{N}^{N-1}\times I-S_0$, where,
$S_0=\{s\in\mathbb{N}\times\mathbb{N}^N\times\mathbb{N}^{N-1}\times I: v_i=v_j=0~\text{for some}~j\neq i~\text{or}~r_j\geq1~\text{for some}~j\in I\}$.
The set $S_0$ contains states where multiple coordinates of $\mathbf{V}(t)$ are zero and states with
$r_j\geq1$. The former class of states is not allowed, since there can be at most one transmitter
in any time slot. The latter are all transient states.
$S_0$ obviously contains the set of transient states induced by the policies under consideration, and needs
to be removed so that the resulting controlled DTMC, defined on $S'$, can be irreducible.

Now, the theorem in <cit.> makes assumptions, which in our case can be
restated as follows. For
any $\alpha\in(0,1)$, and state $(q,\mathbf{V},\mathbf{r},i)\in S'$,

* A: $J^*_i((q,\mathbf{V},\mathbf{r})<\infty$.

* B: Let[We define $\hat{\mathbf{e}}_k$ as the vector with 0's at all coordinates
except the $k^{th}$, which is equal to $1$.] $\mathbf{V}_0=\mathbf{1}-\hat{\mathbf{e}}_1$ and define
There exists $N>0$, s.t.

\begin{equation}
h_{i,\alpha}(q,\mathbf{V},\mathbf{r})\geq-N~\forall(q,\mathbf{V},\mathbf{r},i)\in S'.
\end{equation}

* C: For any given pair of states $(s,t)\in S'\times S'$, and action $a\in I$, let $P_{st}(a)$
denote the transition probability from state $s$ to state $t$ under action $a$ in the MDP (for further details, read Sec.<ref>). There exists $M_i(q,\mathbf{V},\mathbf{r})\geq0$, s.t.

\begin{equation}
h_{i,\alpha}(q,\mathbf{V},\mathbf{r})\leq M_i(q,\mathbf{V},\mathbf{r})~\forall(q,\mathbf{V},\mathbf{r},i)\in S',~\text{and}~\alpha\in(0,1),
\end{equation}

and, denoting by $M_t$ the R.H.S in the above equation for state $t\in S'$,

\begin{equation}
\sum_{t\in S'}M_tP_{st}(a)<\infty,~\forall s\in S'~\text{and}~a\in I.
\end{equation}

If the assumptions A, B and C hold, $\pi^*$ is optimal for the Averge Cost problem as well.

Theorem <ref> is proved in <cit.>. To see why A is true,
define $s(0)=\left[q,\mathbf{V},\mathbf{r},i\right]$ and consider

\begin{eqnarray}
\hspace{-0.20cm}
J^*_i(s(0)) &=& \min_{\pi}\mathbb{E}_{s(0)}^\pi\sum_{n=0}^\infty\alpha^n\left[Q_{u_{n-1}}(n)+\lambda\sum_{j\neq u_{n-1}}V_j(n)+\sum_{i\in I}R_i(n)\right]\nonumber\\
&\stackrel{e}{\leq}& \min_{\pi}\mathbb{E}_{s(0)}^\pi\sum_{n=0}^\infty\alpha^n \left[ \left(Q_{u_{n-1}}(0)+n\right)+\lambda\left(n+\sum_{j\neq u_{n-1}}V_j(0)\right)\right.\nonumber\\
&& ~~~~~~~~~~~~~ \left.+\left(n+\sum_{i\in I}R_i(0)\right)\right]\nonumber\\
&\stackrel{f}{\leq}& \min_{\pi}\mathbb{E}_{s(0)}^\pi\sum_{n=0}^\infty\alpha^n \left[ \left(Q(0)+n\right)+\lambda\left(n+\sum_{j\neq u_{n-1}}V_j(0)\right)\right.\nonumber\\
&& ~~~~~~~~~~~~~ \left.+\left(n+\sum_{i\in I}R_i(0)\right)\right]\nonumber\\
&\stackrel{\star}{<}& \infty,\nonumber
\end{eqnarray}

where inequality $e$ follows from the fact that over $n$ slots, the backlog of queue $u_{n-1}$ cannot
have increased to more than $n$ packets over its initial backlog, i.e., $Q_{u_{n-1}}(0)+n$. In
inequality $f$, $Q(0)=\max_{k\in I}Q_k(0)$. Finally, inequality $\star$ uses the fact that

\begin{equation}
\sum_{n=0}^\infty n\alpha^n<\infty,~\forall\alpha\in(0,1).
\end{equation}

In Lemma.<ref>, we have already proven that $J^*$ is increasing in its first coordinate.
Now, keeping the incumbent the same, suppose one of the coordinates of $\mathbf{V}$ is increased,

\begin{eqnarray}
\hspace{-0.50cm}
J^*_i(0;\mathbf{V};\mathbf{0})&=&\lambda\sum_{k\neq i}V_k+\alpha\min_{k\neq i}\mathbb{E}J^*_j\left(B(V_k);V_k=0,\mathbf{V}_{-k}+\mathbf{1};\mathbf{0}\right)\hspace{0.0cm}\nonumber\\
&\leq& \lambda (V_l+1)+\lambda\sum_{k\neq i,l}V_k+\alpha\min\left\lbrace\min_{k\neq i,l}\mathbb{E}J^*_j\left(B(V_k);\right.\right.\nonumber\\
&& \left. V_k=0,\mathbf{V}_{-k}+\mathbf{1}+\hat{\mathbf{e}}_l;\mathbf{0}\right),\nonumber\\
&& \left. J^*_l\left(B(V_l+1);V_l=0,\mathbf{V}_{-k}+\mathbf{1};\mathbf{0}\right)\right\rbrace\nonumber\\
&=& J^*_i(0;\mathbf{V}+\hat{\mathbf{e}}_l;\mathbf{0}).\hspace{0.0cm}
\label{eqnIncV}
\end{eqnarray}

A similar analysis proves that $J^*$ is increasing in the coordinates of $\mathbf{r}$ also. Finally,
starting with a different incumbent, since

\begin{equation}
J^*_l(0;\mathbf{V};\mathbf{0})=\lambda\sum_{k\neq l}V_k+\alpha\min_{k\neq l}\mathbb{E}J^*_j\left(B(V_k);V_k=0,\mathbf{V}_{-k}+\mathbf{1};\mathbf{0}\right),\\
\label{eqnVl}
\end{equation}

we see that if $V_l$ in the first equation of (<ref>) is equal to $V_i$ in (<ref>), then
$J^*_l(0;\mathbf{V};\mathbf{0})=J^*_i(0;\mathbf{V};\mathbf{0})$. This is achieved by
noting that all since arrivals are statistically identical and independent one can simply route the
packets of queue $l$ to queue $i$ and vice versa in every sample path. This doesn't change the statistics
of the system in any way and proves that

\begin{eqnarray}
J^*_i((q,\mathbf{V},\mathbf{r})-J^*_1((0,\mathbf{V}_0,\mathbf{0})=h_{i,\alpha}(q,\mathbf{V},\mathbf{r})\geq0~\forall i\in I.
\end{eqnarray}

Proving assumption C is nontrivial, and Prop. 5 (pp.629) in <cit.> gives a
sufficient condition for C to hold.
Assume that the MDP has a stationary policy $f$ that induces an irreducible, positive recurrent
Markov chain on the state space of the problem, viz, $S'$. Let $p_f(q,\mathbf{V},\mathbf{r},i)$ denote
the invariant distribution of the chain and let $c_f(q,\mathbf{V},\mathbf{r},i)$ denote the
non-negative cost in state $\mathbf{s}=\left[q;\mathbf{V};\mathbf{r};i\right]$. If

\begin{equation}
\sum_{\mathbf{s}}p_f(q,\mathbf{V},\mathbf{r},i)c_f(q,\mathbf{V},\mathbf{r},i)=\mathbb{E}\left[\tilde{Q}+\lambda\sum_{k\neq \tilde{i}}\tilde{V}_k+\sum_{l=1}^N\tilde{r}_l\right]<\infty
\label{eqnStatCostFinit}
\end{equation}

then assumption C is true. Here, $\tilde{Q},\tilde{\mathbf{V}},\tilde{\mathbf{r}}~\text{and}~\tilde{i}$
are the random variables with joint distribution $p_f$.
Notice, however, from (<ref>) that for all policies under consideration that are also

\begin{eqnarray}
\mathbb{E}\left[\tilde{Q}+\lambda\sum_{k\neq \tilde{i}}\tilde{V}_k+\sum_{l=1}^N\tilde{r}_l\right]
&=& \mathbb{E}\left[\mathbb{E}\left(\sum_{k=1}^NQ_k\bigg|\tilde{Q},\tilde{\mathbf{V}}\right)\right]\nonumber\\
&=& \mathbb{E}\sum_{k=1}^NQ_k,\hspace{2.1cm}
\end{eqnarray}

where $[Q_1,\dots,Q_N]$ is the stationary queue-length vector of the system. We have already shown that $\pi^*$ is stabilizing and know that the policy discussed in Sec. <ref>, $\pi'$, is also stabilizing from the discussion therein. So, we set $f\equiv \pi'$, since $\pi'$ is stationary and Markov, and observe that for any $\lambda\in[0,\frac{1}{N})$ queueing delay for such policies is finite. Using Little's law, we see that under $\pi'$,
$\mathbb{E}\sum_{k=1}^NQ_k=\sum_{k=1}^N\mathbb{E}Q_k<\infty$. Since $\pi'$ is stationary, this proves the claim and
establishes the fact that $\pi^*$ is optimal for the average cost criterion as well.

§.§ Proof of Prop. <ref>

Let $\mathbb{Z}_+$ denote the non negative integers. The proof uses a simple mean drift argument with a novel Lyapunov function. Define $L:\mathbb{Z}_+^{2N}\mapsto\mathbb{R}_+$ as

\begin{equation}
\label{eqnKlimitedLyapunovDef}
\end{equation}

Time Slot     $\mathbf{V}_{1}(\cdot)$     $\mathbf{V}_{2}(\cdot)$     $\mathbf{V}_{3}(\cdot)$     $\mathbf{V}_{4}(\cdot)$

(incumbent)                                                                        ($\argmax{i}V_i(t)=4$)

$t$     $[0,9,11,12]$     $[0,9,11,12]$     $[0,9,11,12]$     $[0,9,11,12]$

$t+1$     $[0,10,12,13]$     $[0,10,12,13]$     $[0,10,12,13]$     $[0,10,12,13]$

$t+2$     $[0,11,13,14]$     $[1^\ast,11,13,0]$     $[0,11,13,14]$     $[0,11,13,14]$

$t+3$     $[0,12,14,15]$     $[0,12,14,15]$     $[0,12,14,15]$     $[1^*,12,14,0]$ $\leftarrow$ Queue 4 nonempty

$t'$     $[0,11,13,14]$     $[0,11,13,14]$     $[0,11,13,14]$     $[1^*,11,13,0]$ $\leftarrow$ Queue 4 empty

Illustrating the three types of CCA errors and the resulting $V$-vector misalignment. The network here comprises 4 nodes and the 4 columns represent local copies of the $V$-vector (i.e., $\mathbf{V}_i(t)$ is the copy of the $V$-vector at Node $i$). In the situation considered here, Node 1 is the incumbent and $\argmax{1\leq i\leq4}V_i(t)=4$. The coordinate at which CCA error occurs is denoted by an asterisk ($\ast$). A red to blue transition implies the node detects (infers) a misalignment and also corrects it within the same time slot.

We will prove that a policy that is clearly suboptimal (refer Fig. <ref>), again, w.r.t. delay when compared to $\pi_K$ (meaning it idles more than $\pi_K$) is also stabilizing. This new policy, called Gated K Limited service(GKLS) policy and denoted by $\xi_K$, serves only those packets that were in the chosen queue at the beginning of service, for a maximum of $K$ slots. Also, once a queue is chosen for service, the server stays at it (idling, if necessary), for $K$ slots at the end of which $\argmax{1\leq i\leq N} \left(Q_i(t-V_i(t))+\lambda_i V_i(t)\right)$ is chosen for service for the next $K$ slots.

Illustrating the suboptimality of the Gated K Limited service policy ($\xi_K$).

For example, suppose $K=5$ and queue $3$ has been chosen for service. At the beginning of service, suppose $Q_3=2$ and over the course of the $5$ slots, it receives $4$ more packets. Then $\xi_K$ serves only the $2$ that were in Queue $3$ at the beginning of service, does not serve any of the $4$ new packets and idles for the remaining $K-2(=3)$ slots. This is clearly suboptimal compared to $\pi_K$ which would have served $5$ packets and left queue $3$ with just $1$ packet at the end of $K=5$ slots.

Suppose at time $t$, $\xi_K$ switches to queue $i$. For all other queues, after K slots, $V_l(t+K)=V_l(t)+K$, and $Q_l(t+K-V_l(t+K))=Q_l(t-V_l(t))$. Therefore, at the end of $K$ slots, the new state is $s(t+K)=[Q_1(t-V_1(t)),\dots, Q_{i-1}(t-V_{i-1}(t)), Q_i(t+K), Q_{i+1}(t-V_{i+1}(t)),\dots,Q_N(t-V_N(t)),V_1(t)+K,\dots,V_{i-1}(t)+K,0,V_{i+1}(t)+K,\dots,V_N(t)+K]$.

Invoking the linearity of conditional expectation, computing the expected conditional drift can be split into contributions by the queue chosen for service at time $t$, i.e., queue $i$, and that by the other queues. For simplicity we drop the time indices and denote $V_j(t)$ by $V_j$ for the remainder of the proof.

\begin{eqnarray}
&& \mathbb{E}\left[L(s(t+K))-L(s(t))|s(t)\right]\nonumber\\
&=& \mathbb{E}\bigg[Q^2_i(t+K)-\left(Q_i(t-V_i)+ \lambda_iV_i\right)^2- V_i\lambda_i(1-\lambda_i)\bigg|s(t)\bigg]+ \nonumber\\
&& \mathbb{E}\bigg[\sum_{j\neq i}\left(Q_j(t-V_j)+ \lambda_j\left(V_j+K\right)\right)^2+ \left(V_j+K\right)\lambda_j(1-\lambda_j)-\nonumber\\
&& \sum_{j\neq i}\left(\left(Q_j(t-V_j)+ \lambda_jV_j\right)^2+V_j\lambda_j(1-\lambda_j)\right)\bigg|s(t)\bigg]
\label{eqnKlimitedConditionalDriftContributions}
\end{eqnarray}

The contribution to $L(s(t+K))$ of all queues $j$ other than $i$ is

\begin{eqnarray}
&& \sum_{j\neq i}\left(Q_j(t-V_j)+\lambda_j\left(V_j+K\right)\right)^2+\left(V_j+K\right)\lambda_j(1-\lambda_j)\nonumber\\
&=& \sum_{j\neq i}\left(Q_j(t-V_j)+\lambda_jV_j\right)^2+2K\left(Q_j(t-V_j)+\lambda_jV_j\right)\lambda_j\nonumber\\
&& +K^2\lambda_j^2+ V_j\lambda_j(1-\lambda_j)+K\lambda_j(1-\lambda_j).
\label{eqnKlimitedLOftPlusKeveryoneElse}
\end{eqnarray}

Using (<ref>), the second term on the R.H.S of (<ref>) becomes

\begin{eqnarray}
&& \mathbb{E}\bigg[\sum_{j\neq i}\left(Q_j(t-V_j)+\lambda_j\left(V_j+K\right)\right)^2+\left(V_j+K\right)\lambda_j(1-\lambda_j)\nonumber\\
&& -\sum_{j\neq i}\left(Q_j(t-V_j)+\lambda_jV_j\right)^2+V_j\lambda_j(1-\lambda_j)\bigg|s(t)\bigg]\nonumber\\
&=& \mathbb{E}\bigg[2K\left(Q_j(t-V_j)+\lambda_jV_j\right)\lambda_j+K^2\lambda_j^2+K\lambda_j(1-\lambda_j)\bigg|s(t)\bigg] \hspace{0.0cm}\nonumber\\
&=& 2K\left(Q_j(t-V_j)+\lambda_jV_j\right)\lambda_j+K^2\lambda_j^2+K\lambda_j(1-\lambda_j),\hspace{0.0cm}
\label{eqnKlimitedContributionOfOthers}
\end{eqnarray}

where the last equality follows since the term inside the expectation is a function of $s(t)$. Proceeding to queue $i$, we see that

\begin{eqnarray}
\hspace{-1.00cm}
Q^2_i(t+K) &\stackrel{(*a)}{=}& \left(\left(Q_i(t-V_i)+A_i[t-V_i+1,t]-K\right)^++A_i[t+1,t+K]\right)^2,\nonumber\\
&\stackrel{(*b)}{\leq}& \left(Q_i(t-V_i)+A_i[t-V_i+1,t]\right)^2+K^2+\left(A_i[t+1,t+K]\right)^2\nonumber\\
&& -2\left(Q_i(t-V_i)+A_i[t-V_i,t]\right) (K-A_i[t+1,t+K]),
\label{eqnKLimitedQiSquare}
\end{eqnarray}

where, in equality $(*a)$, one first needs to note that queue $i$ has never been served since $t-V_i$. Also, $A_i[x,y]$ denotes the cumulative arrivals to queue $i$ over the time period $[x,y]$, and $A_i[x,x]$ is the arrival over the single slot $x$. Specifically, when the arrival process is Bernoulli, $A_i[x,y]$ has the distribution Binomial$(y-x+1,\lambda_i)$. Also, $(*b)$ follows from the fact that for any three nonnegative numbers $x,y~\text{and}~z$, $((x-y)^++z)^2\leq x^2+y^2+z^2-2x(y-z)$.
In what follows, we use the fact that if a random variable $X\sim$Binomial($m,p$), then $\mathbb{E}X^2=mp(1-p)+m^2p^2$.

\begin{eqnarray}
\hspace{-0.40cm}
\mathbb{E}\bigg[Q^2_i(t+K)\bigg|s(t)\bigg] &\leq& \mathbb{E}\bigg[\left(Q_i(t-V_i)+A_i[t-V_i+1,t]\right)^2+ K^2\nonumber\\
&& + \left(A_i[t+1,t+K]\right)^2- \nonumber\\
&& 2\bigg(\left(Q_i(t-V_i)+A_i[t-V_i+1,t]\right)\nonumber\\
&& \times \left(K-A_i[t+1,t+K]\right)\bigg)\bigg|s(t)\bigg]\nonumber\\
&\stackrel{(*c)}{=}& Q^2_i(t-V_i)+ 2\lambda_iV_iQ_i(t-V_i)+ V_i\lambda_i(1-\lambda_i)\nonumber\\
&& +V_i^2\lambda_i^2+K^2+ K\lambda_i(1-\lambda_i)+ K^2\lambda_i^2\nonumber\\
&& -2\left(Q_i(t-V_i)+\lambda_iV_i\right)K\left(1-\lambda_i\right).\nonumber
\end{eqnarray}

In $(*c)$, one needs to note that the arrivals that enter queue $i$ after the last time queue $i$ was served, viz., $A_i[t-V_i,t+K]$, are independent of $Q_i(t-V_i)$. With this, the contribution of queue $i$ to the expected drift (the first term on the R.H.S of (<ref>)) is

\begin{eqnarray}
&& \mathbb{E}\bigg[Q^2_i(t+K)-\left(Q_i(t-V_i)+\lambda_iV_i\right)^2-V_i\lambda_i(1-\lambda_i)\bigg|s(t)\bigg]\nonumber\\
&& \leq K^2+ K\lambda_i(1-\lambda_i)+ K^2\lambda_i^2\nonumber\\
&& +2K\lambda_i\left(Q_i(t-V_i)+\lambda_iV_i\right)-2K\left(Q_i(t-V_i)+\lambda_iV_i\right)
\label{eqnKlimitedContributionOfQueuei}
\end{eqnarray}

We are now in a position to compute the expected drift. Define $\epsilon:=\left(1-\sum_j\lambda_j\right)$, strictly positive, by assumption. Using (<ref>) and (<ref>) in (<ref>), we get

\begin{eqnarray}
\hspace{-0.25cm}
\mathbb{E}\left[L(s(t+K))-L(s(t))|s(t)\right]&\leq &\left(K(K-1)\sum_{j=1}^N\lambda_j^2+ K\sum_{j=1}^N\lambda_j+ K^2\right)\nonumber\\
&&-2K\left(Q_i(t-V_i)+ \lambda_iV_i\right)\left(1-\sum_{l=1}^N\lambda_l\right)\nonumber\\
&<& -\epsilon,\nonumber
\end{eqnarray}

\begin{equation}
\hspace{-0.25cm}
max_{i}\left(Q_i(t-V_i)+ \lambda_iV_i\right)>\frac{\left(K(K-1)\sum_{j=1}^N\lambda_j^2+ K\sum_{j=1}^N\lambda_j+ K^2\right)}{2K\epsilon}+ \frac{1}{2K},\nonumber%\hspace{9.25cm}
\end{equation}

Invoking the Foster Lyapunov theorem <cit.> we see that the DTMC $\{s(Kt),t\geq0\}$ is positive recurrent. To show that $s(t)$ is positive recurrent as well, we invoke the following lemma.

Let $\{X(t),t\geq0\}$ be an aperiodic and irreducible DTMC over a countable state space. Define $Y(t):=X(Kt),\forall t\geq0,$ for some positive integer $K$. If $Y(t)$ is positive recurrent, then so is $X(t)$.

Given any $j\in\mathbb{N}$, suppose the mean recurrence time of $j$ in $Y(t)$ is denoted by $\nu^{(K)}_j$, and in $X(t)$ by $\nu_j$. Clearly, starting from any state $j$, every time $X(Kt)$ hits $j$, so does $X(t)$. This means that $\nu^{(K)}_j\geq\nu_j$ and since $\nu^{(K)}_j<\infty$, so is $\nu_j$, showing that $X(t)$ is also positive recurrent.

Thus, $s(t)$ is also positive recurrent, and the proof of Prop. <ref> concludes.

§.§ Channel Errors and Fading

Until now, we have assumed that all transmission attempts succeed $w.p.1$. In this section, we consider a system similar to the one described in <cit.>. In addition to the system described in Sec. <ref>, we also specify that every transmission from queue $i$ succeeds with probability $p_i$ independent of all other transmissions. Specifically, fading or transmission errors are independent across time slots. This necessitates a revision of Eqn. <ref>, provided in Eqn. (<ref>) wherein the random variables $C_i(t)$, that represent the fade state of the channel between node $i$ and the receiver, are modelled as Bernoulli random variables i.i.d across time and independent across queues.

\begin{eqnarray}
\label{eqnQEvolution2WithFading}
\end{eqnarray}

The coefficient of $D_i(t)$ in (<ref>) is $-C_i(t)\in\{0,-1\}$, meaning Queue $i$'s transmissions are assumed to succeed whenever it is scheduled ($D_i(t)=1$) and its channel is ON ($C_i(t)=1$).

We assume the system only gets to know whether a transmission succeeded or not at the end of a slot and has no knowledge of the current channel state at the scheduling instants. Since each packet at Queue $i$ takes, on the average, $1/p_i$ slots to be transmitted (i.e., its service time is Geometric with mean $1/p_i$), the capacity region of such a system is given by

\begin{equation}
\Lambda:=\bigg\{\boldsymbol{\lambda}\in\mathbb{R}^N_+\bigg|\sum_{i=1}^N\frac{\lambda_i}{p_i}<1\bigg\},
\end{equation}

It can be shown that the proof of Prop. <ref> remains valid even when the service time of Queue $i$ is $B_i$ and $\sum_{i=1}^N\lambda_i\mathbb{E}B_i<1$. Setting $\mathbb{E}B_i=\frac{1}{p_i}$ we see that the LEQ policy, clearly, is still throughput optimal. Note that the LEQ scheduler does not need to know the fading probabilities $\{p_1,p_2,\cdots,p_N\}$ to stabilize the system.

§.§ Handling Alarm Traffic: The QZMAC$_a$ protocol

Alarm traffic is particularly important in in-network processing, wherein the data generated by the sensors is partially processed within the network before reaching the sink etc. <cit.>. This is done, as mentioned earlier, to detect abnormal behavior in the processes begin monitored by the WSN and when such conditions are detected, the network generates alarm packets.
To study the effects of applications generating alarm packets that need to be delivered with utmost priority, we first modify the system described in Sec. <ref>.

every picture/.style=line width=0.75pt

[very thick,black]    (181,111) – (391.26,111) ;

[very thick,black]    (391.26,111) – (391.26,213.35) ;

[very thick,black]    (181,213.35) – (391.26,213.35) ;

[very thick, fill=blue!60!white!40, draw=black]  (373.74,115.93) .. controls (380.26,115.88) and (385.58,121.12) .. (385.64,127.64) – (386.17,196.09) .. controls (386.22,202.6) and (380.98,207.93) .. (374.47,207.98) – (339.06,208.26) .. controls (332.55,208.31) and (327.22,203.07) .. (327.17,196.55) – (326.63,128.1) .. controls (326.58,121.58) and (331.82,116.26) .. (338.34,116.21) – cycle ;

[very thick, fill=blue!60!white!40, draw=black] (308.74,115.39) .. controls (315.26,115.34) and (320.58,120.58) .. (320.63,127.1) – (321.17,195.55) .. controls (321.22,202.07) and (315.98,207.39) .. (309.46,207.44) – (274.06,207.72) .. controls (267.54,207.77) and (262.22,202.53) .. (262.16,196.01) – (261.63,127.57) .. controls (261.58,121.05) and (266.82,115.72) .. (273.34,115.67) – cycle ;

[very thick, fill=blue!60!white!40, draw=black]  (242.73,115.86) .. controls (249.25,115.81) and (254.58,121.05) .. (254.63,127.57) – (255.16,196.01) .. controls (255.22,202.53) and (249.97,207.86) .. (243.46,207.91) – (208.05,208.19) .. controls (201.54,208.24) and (196.21,203) .. (196.16,196.48) – (195.62,128.03) .. controls (195.57,121.51) and (200.81,116.19) .. (207.33,116.14) – cycle ;

(106.25,85.13) .. controls (161.69,86.12) and (134.81,129.47) .. (179.87,132.28) ;
[shift=(181.26,132.35), rotate = 182.44] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(107.25,232.13) .. controls (162.69,233.12) and (136.79,189.24) .. (181.87,190.31) ;
[shift=(183.26,190.35), rotate = 182.44] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(105.25,158.13) – (174.25,158.13) ;
[shift=(176.25,158.13), rotate = 180] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(468,160) – (511.25,160.13) ;
[shift=(513.25,160.13), rotate = 180.17] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

[very thick,black]   (418,160) .. controls (418,146.19) and (429.19,135) .. (443,135) .. controls (456.81,135) and (468,146.19) .. (468,160) .. controls (468,173.81) and (456.81,185) .. (443,185) .. controls (429.19,185) and (418,173.81) .. (418,160) – cycle ;

(80.65,178.57) .. controls (80.64,176.6) and (82.22,175) .. (84.19,175) .. controls (86.16,175) and (87.77,176.6) .. (87.79,178.57) .. controls (87.81,180.54) and (86.23,182.13) .. (84.26,182.13) .. controls (82.29,182.13) and (80.67,180.54) .. (80.65,178.57) – cycle ;

(80.65,194.57) .. controls (80.64,192.6) and (82.22,191) .. (84.19,191) .. controls (86.16,191) and (87.77,192.6) .. (87.79,194.57) .. controls (87.81,196.54) and (86.23,198.13) .. (84.26,198.13) .. controls (82.29,198.13) and (80.67,196.54) .. (80.65,194.57) – cycle ;

(80.65,209.57) .. controls (80.64,207.6) and (82.22,206) .. (84.19,206) .. controls (86.16,206) and (87.77,207.6) .. (87.79,209.57) .. controls (87.81,211.54) and (86.23,213.13) .. (84.26,213.13) .. controls (82.29,213.13) and (80.67,211.54) .. (80.65,209.57) – cycle ;

(55,146.4) node [anchor=north west][inner sep=0.75pt]    $A_{2}( t)$;

(52,220.4) node [anchor=north west][inner sep=0.75pt]    $A_{N}( t)$;

(55,76.4) node [anchor=north west][inner sep=0.75pt]    $A_{1}( t)$;

(425,105.4) node [anchor=north west][inner sep=0.75pt]    $Geo^{[ X]} /D/1$;

Operation of the idealized full knowledge scheduler.

every picture/.style=line width=0.75pt

(169.51,122.96) – (325.5,122.96) ;

(326.5,121.96) – (326.5,181.91) ;

(171.19,181.91) – (327.18,181.91) ;

[very thick, fill=red!60!white!80, draw=black] (313.13,125.68) .. controls (317.62,125.64) and (321.29,129.25) .. (321.32,133.74) – (321.59,168.96) .. controls (321.63,173.46) and (318.01,177.12) .. (313.52,177.16) – (289.13,177.36) .. controls (284.64,177.39) and (280.97,173.78) .. (280.94,169.29) – (280.67,134.07) .. controls (280.63,129.58) and (284.24,125.91) .. (288.74,125.87) – cycle ;

(114.05,102.41) .. controls (154.97,103.16) and (135.44,135.58) .. (168.17,138) ;
[shift=(169.7,138.09), rotate = 182.48] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(110.79,204.48) .. controls (151.72,205.22) and (132.91,172.41) .. (165.66,172.87) ;
[shift=(167.19,172.91), rotate = 182.48] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(113.31,153.57) – (163.98,153.57) ;
[shift=(165.98,153.57), rotate = 180] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(342,149.42) – (450.31,217.36) ;
[shift=(452,218.42), rotate = 212.1] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(453.34,236.98) .. controls (453.34,226.55) and (461.64,218.09) .. (471.88,218.09) .. controls (482.13,218.09) and (490.43,226.55) .. (490.43,236.98) .. controls (490.43,247.41) and (482.13,255.87) .. (471.88,255.87) .. controls (461.64,255.87) and (453.34,247.41) .. (453.34,236.98) – cycle ;

(86.07,171.01) .. controls (86.05,169.52) and (87.22,168.31) .. (88.69,168.31) .. controls (90.15,168.31) and (91.34,169.52) .. (91.36,171.01) .. controls (91.37,172.49) and (90.2,173.7) .. (88.74,173.7) .. controls (87.28,173.7) and (86.08,172.49) .. (86.07,171.01) – cycle ;

(86.07,183.09) .. controls (86.05,181.61) and (87.22,180.4) .. (88.69,180.4) .. controls (90.15,180.4) and (91.34,181.61) .. (91.36,183.09) .. controls (91.37,184.58) and (90.2,185.79) .. (88.74,185.79) .. controls (87.28,185.79) and (86.08,184.58) .. (86.07,183.09) – cycle ;

(86.07,194.43) .. controls (86.05,192.94) and (87.22,191.73) .. (88.69,191.73) .. controls (90.15,191.73) and (91.34,192.94) .. (91.36,194.43) .. controls (91.37,195.92) and (90.2,197.12) .. (88.74,197.12) .. controls (87.28,197.12) and (86.08,195.92) .. (86.07,194.43) – cycle ;

(173.51,303.96) – (329.5,303.96) ;

(329.5,303.96) – (329.5,381.29) ;

(173.51,381.29) – (329.5,381.29) ;

[very thick, fill=blue!60!white!40, draw=black] (316.5,307.68) .. controls (321.34,307.64) and (325.29,311.53) .. (325.33,316.36) – (325.72,368.4) .. controls (325.76,373.24) and (321.87,377.19) .. (317.04,377.23) – (290.77,377.44) .. controls (285.94,377.48) and (281.99,373.59) .. (281.95,368.76) – (281.55,316.72) .. controls (281.52,311.88) and (285.41,307.93) .. (290.24,307.89) – cycle ;

[very thick, fill=blue!60!white!40, draw=black] (268.28,307.28) .. controls (273.11,307.24) and (277.06,311.12) .. (277.1,315.96) – (277.5,368) .. controls (277.54,372.83) and (273.65,376.78) .. (268.81,376.82) – (242.55,377.03) .. controls (237.71,377.07) and (233.76,373.18) .. (233.73,368.35) – (233.33,316.31) .. controls (233.29,311.48) and (237.18,307.53) .. (242.01,307.49) – cycle ;

[very thick, fill=blue!60!white!40, draw=black] (219.31,307.63) .. controls (224.14,307.59) and (228.09,311.47) .. (228.13,316.31) – (228.53,368.35) .. controls (228.57,373.18) and (224.68,377.13) .. (219.84,377.17) – (193.58,377.38) .. controls (188.75,377.42) and (184.8,373.54) .. (184.76,368.7) – (184.36,316.66) .. controls (184.32,311.83) and (188.21,307.88) .. (193.05,307.84) – cycle ;

(118.05,284.41) .. controls (158.97,285.16) and (139.44,317.58) .. (172.17,320) ;
[shift=(173.7,320.09), rotate = 182.48] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(118.79,395.48) .. controls (159.72,396.22) and (140.91,363.41) .. (173.66,363.87) ;
[shift=(175.19,363.91), rotate = 182.48] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(117.31,337.57) – (167.98,337.57) ;
[shift=(169.98,337.57), rotate = 180] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(99.07,355.01) .. controls (99.05,353.52) and (100.22,352.31) .. (101.69,352.31) .. controls (103.15,352.31) and (104.34,353.52) .. (104.36,355.01) .. controls (104.37,356.49) and (103.2,357.7) .. (101.74,357.7) .. controls (100.28,357.7) and (99.08,356.49) .. (99.07,355.01) – cycle ;

(99.07,367.09) .. controls (99.05,365.61) and (100.22,364.4) .. (101.69,364.4) .. controls (103.15,364.4) and (104.34,365.61) .. (104.36,367.09) .. controls (104.37,368.58) and (103.2,369.79) .. (101.74,369.79) .. controls (100.28,369.79) and (99.08,368.58) .. (99.07,367.09) – cycle ;

(99.07,378.43) .. controls (99.05,376.94) and (100.22,375.73) .. (101.69,375.73) .. controls (103.15,375.73) and (104.34,376.94) .. (104.36,378.43) .. controls (104.37,379.92) and (103.2,381.12) .. (101.74,381.12) .. controls (100.28,381.12) and (99.08,379.92) .. (99.07,378.43) – cycle ;

[very thick, fill=red!60!white!80, draw=black] (267.47,126) .. controls (271.96,125.97) and (275.63,129.58) .. (275.67,134.07) – (275.94,169.29) .. controls (275.97,173.78) and (272.36,177.45) .. (267.87,177.49) – (243.48,177.68) .. controls (238.99,177.72) and (235.32,174.11) .. (235.28,169.62) – (235.01,134.39) .. controls (234.98,129.9) and (238.59,126.23) .. (243.08,126.2) – cycle ;

[very thick, fill=red!60!white!80, draw=black] (219.82,126.33) .. controls (224.31,126.29) and (227.98,129.9) .. (228.01,134.39) – (228.28,169.62) .. controls (228.32,174.11) and (224.71,177.78) .. (220.22,177.81) – (195.82,178.01) .. controls (191.33,178.05) and (187.67,174.43) .. (187.63,169.94) – (187.36,134.72) .. controls (187.33,130.23) and (190.94,126.56) .. (195.43,126.52) – cycle ;

(344,343.42) – (449.46,255.7) ;
[shift=(451,254.42), rotate = 500.25] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(385,143.42) .. controls (361.12,159.34) and (332.29,312.88) .. (388.15,350.86) ;
[shift=(389,351.42), rotate = 212.99] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(490.43,236.98) – (541.11,236.98) ;
[shift=(543.11,236.98), rotate = 180] [color=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

(45.00,130.6) node [anchor=north west][inner sep=0.75pt]    $A^{( a)}_{2}(t)$;

(45.00,203.51) node [anchor=north west][inner sep=0.75pt]    $A_{N}(t)$;

(45.00,92.71) node [anchor=north west][inner sep=0.75pt]    $A^{( a)}_{1}(t)$;

(65.00,322.6) node [anchor=north west][inner sep=0.75pt]    $A_{2}(t)$;

(62.00,384.51) node [anchor=north west][inner sep=0.75pt]    $A_{N}(t)$;

(65.00,275.71) node [anchor=north west][inner sep=0.75pt]    $A_{1}(t)$;

(200,97.42) node [anchor=north west][inner sep=0.75pt]   [align=left] Alarm Packets;

(213,279.42) node [anchor=north west][inner sep=0.75pt]   [align=left] Data Packets;

(401,160.42) node [anchor=north west][inner sep=0.75pt]   [align=left] Higher Priority;

(435.5,306.42) node [anchor=north west][inner sep=0.75pt]   [align=left] Lower Priority;

(380,320.42) node [anchor=north west][inner sep=0.75pt]   [align=left] (Serve only if alarm queue is empty);

Operation of the idealized full knowledge scheduler with priority service for alarm packets. With alarm traffic, it becomes a priority queue. $A^{(a)}_i(t)$ is the alarm packet entering queue $i$ at time t.

Operation of the idealized full knowledge scheduler with priority service for alarm packets.

Instead of a single arrival stream, every queue now has two arrival streams. One carrying non alarm traffic (which we will call data traffic) and another carrying alarm packets. The Bernoulli $\lambda_i$ input process is split (in a memoryless manner) with a fraction $1-\alpha_i$ entering the data stream and a fraction $\alpha_i$ entering the alarm packet stream. Given that alarm packets are generated very rarely

$\alpha_i$ is much smaller than $1-\alpha_i$. In this case, we modify QZMAC as follows. We include an alarm minislot ($T_a$) at the beginning of every slot. Queues with alarm packets can use this slot to send out a high power jamming signal to inform the others that alarm packets are in the system. With this, we modify QZMAC to accommodate such traffic and call the resulting protocol QZMAC$_a$.
So, at the beginning of slot $t$

* The slot begins with the alarm minislot $T_a$. Every queue that has an alarm packet sends out a jam signal.

* If the queues do not sense any power in $T_a$, QZMAC$_a$ operates exactly like QZMAC in slot $t$.

* If the queues do sense power in $T_a$, normal operation according to QZMAC is suspended for slot $t$.

* All queues with alarm packets back off as usual over $\{T_a+T_p+1,\cdots,T_a+T_p+T_c\}$ and if a winner emerges, it transmits its alarm packet.

* If no winner emerges, the system still has alarm packets, which means the protocol goes into alarm mode in slot $t+1$ as well.

* This continues until there are no alarm packets left in the system.

§.§.§ Performance of QZMAC with Alarm Traffic

As can be seen from Fig. <ref>, when alarm traffic is light QZMAC$_a$ provides the same delay to alarm packets as the full knowledge scheduler (the plain red and plan blue curves overlap significantly). This is because alarm packets are given maximum priority in QZMAC$_a$. Queues with alarm packets contend for the channel and since their arrival rate ($\alpha_i\lambda_i$) is small, these packets essentially see a service time of 1 slot. Moreover, the delay to data traffic (blue-with-diamonds curve) is comparable to that without any alarm traffic (dashed green curve), i.e., plain QZMAC. However, if the alarm traffic load becomes significant compared to data traffic, the performance delivered to alarm packets (solid red curve at the bottom of Fig. <ref>) is not affected much due to priority queueing (this delay does show an increase near saturation from 1.005 slots to 1.357 slots, but this is still acceptable). However, the delay of data packets (blue-with-diamonds curve) degrades considerably and, as Fig. <ref> shows, is much worse than that of QZMAC without any alarm traffic (dashed green curve).

The curves in red are obtained by the full-knowledge scheduler with priorities (see Fig. <ref>).

Performance of QZMAC$_a$ with $\alpha_i=0.01$ for all $i$, i.e., 1$\%$ alarm traffic.

Performance of QZMAC$_a$ with $\alpha_i=0.33$ for all $i$, i.e., 33$\%$ alarm traffic.

Performance of QZMAC$_a$ with different alarm traffic arrival rates.

§.§ Effects of Nonidealities in Clear Channel Assessment

As mentioned earlier, in standard hypothesis testing parlance, the event when a CCA fails despite there being no activity on the channel is called a Fale Alarm, while the event when the CCA is successful even when a node in the network is transmitting is called a Miss. We denote the corresponding probabilities by $p_{FA}$ and $p_{miss}$ respectively. Our extensive experimentation, as described in Sec. <ref>, has revealed the following facts

* For networks with diameter up to $8$ meters, $p_{FA}\approx0$. This happens because the noise floor of modern sensors is low enough (-110 dBm for a 2MHz bandwidth) that no CCA failure triggers when the channel is free, and

* In any given time slot (not minislot), at most one CCA Miss occurs.

Therefore, going forward, our analysis will assume that only Miss events occur and at most one node's CCA can register a spurious failure in any time slot. Table <ref> illustrates the three types of misalignment that can occur. In the sequel, we will refer to them as M1, M2 and M3 errors. We now describe them in detail and explain how each type is resolved. Recall that the node currently transmitting is called the incumbent and in time slot $t$, $i^*=\argmax{i\in[N]}V_i(t).$

M1. This is the situation in slot $t+2$ in Table <ref>. The CCA of Node $j$ ($j\neq i^*$) succeeds, and it assumes that Node $i^*$ will now transmit. However, upon decoding the header, the node discovers that the incumbent is nonempty, infers that a CCA Miss has occurred and corrects its copy of the $\mathbf{V}$-vector.

M2. This is the situation in slot $t+3$ in Table <ref>. The $i^*$ Node assumes that the incumbent is empty and, being nonempty, begins transmitting. The transmissions from the two nodes now collide and further provisions are now required within QZMAC to extricate the network from this state. The subroutine discussed in Sec. <ref> is designed to accomplish this.

M3. This is the situation in slot $t'$ in Table <ref>. This case is similar to M2., but now, Node $i^*$ is empty. The node then decodes the header of the packet, detects the CCA miss and corrects its copy of the $\mathbf{V}$-vector.

We thus see that two of the three potential types of misalignment can be detected and rectified quite easily, while only one necessitates modification to QZMAC. In Sec. <ref> we discuss this modification. Furthermore, as the simulation results in Fig. <ref> show, even at a miss rate $p_{miss} = 3\times10^{-4},$ which is $100$ times larger than the measures miss probability, the largest increase in mean delay due to the modification is $1.5266$ slots ($\approx4.32\%$), which is quite minimal.

Comparing mean delay with and without CCA errors. We ran QZMAC for $5.25\times10^6$ slots with $K_t=5$ slots. The curve in red shows the performance of QZMAC with the RESET subroutine described in Sec. <ref>. Mean delay loss with due to imperfect CCA is at most $1.5266$ slots (occurring at $\lambda=0.0325$) even up to a CCA miss probability of $3\times10^{-4}$, which is quite negligible.