In chapter 3 of book Stochastic Network Optimization with Application to Communication and Queueing Systems, a 2-queue wireless downlink is considered. I put the description in this figure.
I understand how to retrieve the upper bound of $\lambda_1$ and $\lambda_2$ but not sure for that of $\lambda_1 + \lambda_2$ and really don't know about $\lambda_1 + \lambda_2/2$. I think as following:
$\lambda_1 + \lambda_2 \leq 1*(P[S_1=1,S_2=0] + P[S_1=1,S_2=1]) + (P[S_1=0,S_2=1] + P[S_1=0,S_2=2]) + 1.5(P[S_1=1,S_2=2])$
However, I am still not sure if this is correct. So my question is how to calculate the network capacity region as shown in the Fig.3b of the attached image?
The problem has two channels that vary independently over time with channel states $\{S_1(t)\}_{t=0}^{\infty}$ i.i.d. and $\{S_2(t)\}_{t=0}^{\infty}$ i.i.d. with \begin{align} &P[S_1(t)=0]=0.3, \quad P[S_1(t)=1]=0.7\\ &P[S_2(t)=0]=0.2, \quad P[S_2(t)=1]=0.5, \quad P[S_2(t)=2]=0.3 \end{align} Every step $t \in \{0, 1, 2, ...\}$ you observe $(S_1(t), S_2(t))$, which tells you the current state of both channels, and then choose to serve either channel 1 or channel 2. So the transmission variables on slot $t$ are $$ (b_1(t),b_2(t)) = \left\{ \begin{array}{ll} (S_1(t), 0) &\mbox{ if we serve channel 1 on slot $t$} \\ (0,S_2(t)) & \mbox{ if we serve channel 2 on slot $t$} \end{array} \right. \quad \quad (Eq. 1)$$
Let $\Lambda$ be the shaded region of Fig. 3.1. Let's show that the set of all expectations $E[(b_1(t),b_2(t))]$ that can be achieved on a particular slot $t$, considering all possible decision rules, does not depend on $t$, and is equal to the set $\Lambda$. The proof has an achievability part and a converse part.
Achievability:
Design stationary and randomized rules (so that under each rule, $\{(b_1(t), b_2(t))\}_{t=0}^{\infty}$ are just i.i.d. vectors) to achieve the corner points of $\Lambda$.
Rule 1 should achieve: $E[(b_1(t), b_2(t))] = (0.14, 1.10)$ for all $t$.
Rule 2 should achieve: $E[(b_1(t),b_2(t))] = (0.49, 0.75)$ for all $t$.
Rule 3 should achieve: $E[(b_1(t),b_2(t))] = (0.70, 0.33)$ for all $t$.
By taking probabilistic mixtures of these rules, we can design a rule to ensure $E[(b_1(t), b_2(t))]$ is any desired point on the Pareto boundary of $\Lambda$.
It is easy to design Rule 1: "Transmit on channel 2 whenever $S_2(t) \neq 0$, and otherwise transmit on channel 1." Rule 2 takes a bit more thought.
Converse:
Fix $t \in \{0, 1, 2, ...\}$ and let $(b_1(t), b_2(t))$ be decisions of any strategy that satisfies (Eq. 1). We want to show $E[(b_1(t),b_2(t))]\in \Lambda$. Recall that the expectation of a random vector is taken componentwise: $$ E[(b_1(t),b_2(t))] = (E[b_1(t)], E[b_2(t)]) $$ So we just show that $(E[b_1(t)], E[b_2(t)])$ satisfies the 6 linear inequality constraints that define the set $\Lambda$ in the figure. To do that, we show there are constants $c_1, c_2$ such that
1) $E[b_1(t)]\geq 0$.
2) $E[b_2(t)]\geq 0$.
3) $E[b_1(t)] \leq 0.7$.
4) $E[b_2(t)]\leq 1.10$.
5) $E[b_1(t)]+E[b_2(t)] \leq c_1$.
6) $2E[b_1(t)] + E[b_2(t)]\leq c_2$.
Inequalities 1-3 hold because, regardless of the decision rule, we have from (Eq. 1) that \begin{align} b_1(t) &\geq 0\\ b_2(t) &\geq 0\\ b_1(t) &\leq S_1(t) \end{align} So we take expectations of both sides to obtain Inequalities 1-3: \begin{align} E[b_1(t)]&\geq 0\\ E[b_2(t)]&\geq 0\\ E[b_1(t)]&\leq E[S_1(t)]=0.7 \end{align} Inequality 4 holds similarly (can you reprodce it?) Inequality 5 holds because from (Eq. 1) $$b_1(t)+b_2(t) \leq \max[S_1(t),S_2(t)]$$ and again we take expectations of both sides. Inequality 6 holds by a similar argument (can you reproduce it?)
If you want to directly connect this with the queueing you could, for $i \in \{1,2\}$: $$ Q_i(t+1) = \max[Q_i(t)-b_i(t),0] + a_i(t) \geq Q_i(t)-b_i(t)+a_i(t) \quad \forall t \in \{0, 1 ,2, ...\}$$ Thus $$Q_i(T)-Q_i(0) \geq \sum_{t=0}^{T-1}[a_i(t)-b_i(t)] \quad \forall T \in\{1, 2, 3, ...\}$$ Now take any service decision strategy. Assume $Q_1(0)=Q_2(0)=0$ for simplicity. We get for all positive integers $T$: \begin{align} 2Q_1(T)+Q_2(T) &\geq \sum_{t=0}^{T-1}\left[[2a_1(t)-2b_1(t)] + [a_2(t)-b_2(t)]\right]\\ &= \sum_{t=0}^{T-1}[(2a_1(t)+a_2(t)) - (2b_1(t)+b_2(t))] \end{align} Taking expectations and using $E[a_i(t)]=\lambda_i$ and $E[2b_1(t)+b_2(t)]\leq c_2$ gives $$ E[2Q_1(T)+Q_2(T)] \geq \sum_{t=0}^{T-1}[(2\lambda_1 + \lambda_2)-c_2] $$ Then $$ \frac{E[2Q_1(T)+Q_2(T)]}{T}\geq (2\lambda_1+\lambda_2) - c_2$$ If both queues are mean rate stable then the left-hand-side $\rightarrow 0$ as $T\rightarrow \infty$, which implies $2\lambda_1+\lambda_2 \leq c_2$. Therefore the inequality $2\lambda_1+\lambda_2\leq c_2$ is a necessary condition for both queues to be mean rate stable. If this condition is violated, it is impossible for any service strategy to stabilize both queues.