Mean-Field Approximation based Scheduling for Broadcast Channels with Massive Receivers

Changkun Li*

\dagger

, , Wei Chen*

\dagger

, Senior Member, IEEE,
and Khaled B. Letaief

\ddagger

This work is supported in part by the National Key R

\&

D Program of China under Grant 2018YFB1801102, the National Natural Science Foundation of China under grant No. 61971264, and Beijing Natural Science Foundation under grant No. 4191001. * Department of Electronic Engineering, Tsinghua University, Beijing, CHINA, 100084

\dagger

Beijing National Research Center for Information Science and Technology (BNRist)

\ddagger

School of Engineering, Hong Kong University of Science and Technology, Hong Kong
Email: [email protected], [email protected], [email protected]

Abstract

The emerging Industrial Internet of Things (IIoT) is driving an ever increasing demand for providing low latency services to massive devices over wireless channels. As a result, how to assure the quality-of-service (QoS) for a large amount of mobile users is becoming a challenging issue in the envisioned sixth-generation (6G) network. In such networks, the delay-optimal wireless access will require a joint channel and queue aware scheduling, whose complexity increases exponentially with the number of users. In this paper, we adopt the mean field approximation to conceive a buffer-aware multi-user diversity or opportunistic access protocol, which serves all backlogged packets of a user if its channel gain is beyond a threshold. A theoretical analysis and numerical results will demonstrate that not only the cross-layer scheduling policy is of low complexity but is also asymptotically optimal for a huge number of devices.

I Introduction

With the development of the fifth-generation (5G) and future sixth-generation (6G) [1] wireless networks, the Industrial Internet of Things (IIoT) has emerged as an important class of applications. The emerging IIoT applications stimulated an ever-increasing demand to provide low latency services for massive devices [2]. However, the scarce spectrum resources and limited transmission power is a major challenge and is hindering the support of required quality of service (QoS) for massive users. How to efficiently utilize the limited resources to support QoS for massive users is becoming critical and has been gaining much attention in recent years.

In order to reduce the communication latency, a line of works focused on the design of efficient stochastic optimization based resources allocation schemes. In [3], a dynamic server allocation scheme for parallel queues with random varying connectivity was investigated. It was shown that the allocation policy which serves the longest queue first performs well in stabilizing the system. In [4], an optimal delay-power tradeoff was revealed in the case of asymptotically small delays with fading channels. In [5], a unified framework for queue-based transmission scheduling was proposed. The optimal scheduling policy was proved to have a threshold-based structure. Work [5] has been extended to different scenarios by works [6, 7, 8]. In [6] and [7], the optimal queue-aware scheduling policies under the multi-state fading channels and the Markov arriving process were investigated, respectively. In [8], a queue status based non-orthogonal multiple access was investigated to reduce the latency in multiple user access scenarios. This line of works focused on the queue status based resource allocation optimization to match the traffic dynamics of users, thereby achieving better performance than other allocation schemes. However, the complexity of this line of works increases exponentially with the number of users, leading to an intrinsic difficulty in analyzing and optimizing the queue status based resource allocation scheme. Motivated by this, this paper aims to apply a mean-field approximation method to analyze the queue status based resource allocation schemes with massive users.

In this paper, we consider a downlink wireless communication scenario, which includes a base station (BS) and a massive number of users where the BS transmits each user’s data packets through a common broadcast channel. To serve massive users with low implementation complexity, the BS applies the time division multiple access (TDMA) protocol. In the order to minimize the average total queueing latency, we derive an optimal channel resources allocation policy by analyzing established stochastic optimization problems. Under the optimal allocation policy, the BS serves the user with the best channel state first. Moreover, the optimal policy is based on the channel status and queue status of all the users. As a result, it is not a trivial work to exactly evaluate the optimal policy. To address this challenge, we propose a mean-field approximation method to approximately evaluate the performance of the optimal policy. When the user number becomes massive, all users’ influences on a certain user’s queue dynamic characteristics become certain. As a result, we can decompose the influences among each user. After decomposing the complex massive user system, we establish an equivalent one-dimensional single user queue model for each user to analyze the queueing latency. Numerical results will demonstrate that the proposed mean-field approximation method can well estimate the optimal policy’s delay performance.

II System Model

Refer to caption — Figure 1: The proposed system model.

As depicted in Fig. 1, we consider a multi-user downlink wireless communication scenario, which is comprised of a BS and $N(\gg 1)$ users. The transmission power at the BS is set to a constant $\mathcal{P}$ to help reduce implementation complexity. At the BS, each user is allocated with a separate buffer to store the packets of independent identically distributed (i.i.d.) arrival processes. To serve the packets backlogged in the buffers, all users share a common broadcast channel to transmit their data packets. Moreover, a central scheduler is adopted to allocate the common channel resources based on the buffer states and channel states of each user.

II-A The Physical Layer

In this subsection, we present the physical layer of the downlink wireless system. In this downlink wireless system, time is denoted by $\tau$ . We divide time into slots. Each timeslot has a duration of $T$ seconds. The $t$ th timeslot denotes the time interval $[tT,(t+1)T]$ . Moreover, the bandwidth of the channel is denoted by $W$ . We consider a block fading channel model, which has been used to model the slowly varying flat-fading channel. Assume each user’s channel quality follows an i.i.d fading process with an i.i.d additive white Gaussian noise (AWGN). The channel gain of each user in each timeslot over a bandwidth $W$ does not change much. Let $h_{n}[t]$ and $\sigma^{2}$ denote the magnitude of channel gain of user $n$ in timeslot $t$ and the noise power at each user’s receiver, respectively.

To serve all the users through a common broadcast channel, a general superposition coding scheme can achieve good performance but with intolerably high complexity in analysis and implementation when $N\gg 1$ . To avoid tackling the high complexity of the superposition coding scheme, we apply a suboptimal time division multiple access (TDMA) protocol. Especially, it was shown in [9] that the TDMA achievable capacity region converges to the capacity region achieved by the superposition coding scheme as the power decreases. Under the TDMA protocol, the BS shall allocate all the transmission power $\mathcal{P}$ and bandwidth $W$ to one user at a time instant $\tau$ . Let $\mathds{1}_{n}(\tau)\in\{0,1\}$ denote a channel allocation policy as a time instant $\tau$ . Especially, $\mathds{1}_{n}(\tau)=1$ indicates that user $n$ is allowed to access the common channel at the time instant $\tau$ . If $\mathds{1}_{n}(\tau)=0$ , the user $n$ is not served at time instant $\tau$ . In particular, we have $\sum_{n=1}^{N}\mathds{1}_{n}(\tau)\leq 1$ . Let $R_{n}(\tau)$ denote the information rate of user $n$ at time instant $\tau$ . According to the channel capacity [10], we have

R_{n}(\tau)\leq\log(1+h_{n}^{2}[t]\mathds{1}_{n}(\tau)\rho),

(1)

where $\rho=\frac{\mathcal{P}}{\sigma^{2}}$ denotes the signal-to-noise ratio.

II-B Discrete-time Queue Model

We consider a discrete-time continuous-length queue model, which can be obtained by sampling the fluid model with sampling rate $1/T$ . Next, we present the variation of user $n$ ’s queue length in a timeslot. Assume that the arrival process of each user is i.i.d.. At the start of timeslot $t$ , $a_{n}[t]\in[A]$ ¹¹1In this paper, we denote by $[A]$ the set $\{0,1,...,A\}$ . packets arrive at user $n$ ’s buffer. Let the probability $\Pr\{a_{n}[t]=a\}$ be denoted by $\theta_{a}$ , where $a\in[A]$ and $\sum_{a=0}^{A}\theta_{a}=1$ . Without loss of generality, suppose that all packets are the same in size and each packet contains $L$ bits. As a result, the average number of bits arriving at each user’s buffer in a timeslot is given by

\lambda=L\sum_{a=0}^{A}a\theta_{a}.

(2)

Let $q_{n}[t]$ denote the number of bits remained in user $n$ ’s buffer by the end of the timeslot $t$ . The number of bits in user $n$ ’s buffer that are transmitted in timeslot $t$ is denoted by $s_{n}[t]$ . Since the number of bits in a user’s buffer cannot be negative, $s_{n}[t]$ shall satisfy that $s_{n}[t]\leq q_{n}[t-1]+a_{n}[t]L$ . By the end of timeslot $t$ , the number of bits remained in user $n$ ’s buffer, i.e. $q_{n}[t]$ , is updated as

q_{n}[t]=q_{n}[t-1]+a_{n}[t]L-s_{n}[t].

(3)

Let $S[t]=\sum_{n=1}^{N}s_{n}[t]$ denote the total number of bits transmitted in timeslot $t$ . According to the Nyquist’s theorem, the value of $S[t]$ is given by

S[t]=W\int_{tT}^{(t+1)T}\sum_{n\in\mathcal{N}(\tau)}\log\bigg{(}1+h^{2}_{n}[t]\mathds{1}_{n}(\tau)\rho\bigg{)}{\rm d}\tau.

(4)

III Delay-Optimal Scheduling with Massive Users

In this section, we aim to derive an optimal scheduling policy to minimize the average total queueing latency in the aforementioned downlink wireless system.

In each timeslot $t$ , the BS dynamically adjust the power allocated to each user based on each user’s queue state and channel state. A power allocation policy in timeslot $t$ can be given by $\{\mathds{1}_{n}(\tau),n\in\{1,2,...,N\},\tau\in[tT,(t+1)T\}$ .Based on the power allocation policy, each user’s queue length updates as Eq. (3). According to little’s law, we can formulate a following optimization problem to minimize the average total queueing delay, which is given by


$\displaystyle\min$	$\displaystyle\quad\frac{1}{\lambda}\sum_{i=1}^{N}\mathbb{E}\{q_{n}[t]\},$	(5a)
$\displaystyle s.t.$	$\displaystyle\quad\sum_{n\in\mathcal{N}(\tau)}\mathds{1}_{n}(\tau)\leq 1,\forall\tau\geq 0,$	(5b)

where $\mathbb{E}\{\cdot\}$ denotes the expectation operator.

However, it is a non-trivial work to solve the optimization problem (5). The intrinsic high complexity of optimization problem (5) is due to we aim to minimize the average queueing delay in a infinite time horizon by determining the power allocated at each time instant $\tau$ . To overcome the difficulty in solving the optimization problem (5), we aim to convert Problem (5) into an equivalent optimization problem, which is given in the following theorem.

Theorem 1: The optimization problem (5) is is asymptotically equivalent to the following optimization problem as $N\to\infty$ .


$\displaystyle\max$	$\displaystyle~{}S[t]=W\int_{tT}^{(t+1)T}\sum_{n\in\mathcal{N}(\tau)}\log\bigg{(}1+h^{2}_{n}[t]\mathds{1}_{n}(\tau)\rho\bigg{)}{\rm d}\tau,$	(6a)
$\displaystyle s.t.$	$\displaystyle\sum_{n\in\mathcal{N}(\tau)}\mathds{1}_{n}(\tau)\leq 1,\forall\tau\in[tT,(t+1)].$	(6b)

Proof:

Due to space limitations, we mainly present the main idea of the proof. We first present an equivalent expression of the objective function Eq. (5a). Let $Q[t]=\sum_{n=1}^{N}(q_{n}[t-1]+a_{n}[t]L)$ denote the total number of bit that can be transmitted in timeslot $t$ . According to Eq. (3), Eq. (5a) is equivalent to

\begin{split}&\frac{1}{\lambda}\sum_{n=1}^{N}\mathbb{E}\{q_{n}[t]\}=\frac{1}{\lambda}\sum_{n=1}^{N}\mathbb{E}\{q_{n}[t-1]\}\\ &=\frac{1}{\lambda}\mathbb{E}\{Q[t]-\sum_{n=1}^{N}a_{n}[t]L\}=\frac{1}{\lambda}\mathbb{E}\{Q[t]\}-N.\end{split}

(7)

As a result, we shall minimize $\mathbb{E}\{Q[t]\}$ . For a policy that does not maximize $S[t]$ in some timeslots, we prove that their exists a new policy can achieve lower or equal $Q[t]$ for all $t$ . The main idea of the proof is completed. ∎

Let the optimal channel allocation scheme at time $\tau$ be denoted by $\{\mathds{1}^{*}_{n}(\tau)\}$ , which is given in the following theorem.

Theorem 2: One of the optimal channel allocation scheme at time $\tau$ is given by

\mathds{1}^{*}_{n}(\tau)=\left\{\begin{split}&1,~{}n=\arg\max_{n\in\mathcal{N}(\tau)}h_{n}[t],\\ &0,~{}\text{otherwise}.\end{split}\right.

(8)

Proof:

We denote by

\bar{R}(T_{1})=\frac{1}{T_{1}}\int_{tT}^{tT+T_{1}}\sum_{n=1}^{|\mathcal{N}(\tau)|}\log_{2}\left(1+h_{n}^{2}[t]\mathds{1}_{n}(\tau)\rho\right){\rm d}\tau

(9)

the average information rate over time interval $[tT,tT+T_{1}]$ . It is obvious that we shall maximize $\bar{R}(T)$ to minimize (6a). It can be verified that the solution $\{\mathds{1}^{*}_{n}(\tau)\}$ given by Theorem 2 can minimize $\bar{R}(T_{1})$ for all $T_{1}\in[0,T]$ . The proof is completed. ∎

According to Theorem 2, the BS shall serve each user from the user with the best channel state to the user with the worst channel state in each timeslot. The corresponding optimal scheduling policy is referred to as a good-channel-first-serve (GCFS) policy.

Next, we derive $s_{n}[t]$ under the GCFS policy. Let $\{n_{1},n_{2},...,n_{M}\}$ denote the set of users whose buffer is not empty in timeslot $t$ just after the arrival process, i.e., $q_{n_{m}}[t-1]+a_{n_{m}}[t]L>0$ for $1\leq m\leq M$ . The number $M$ is the number of users who need service in timeslot $t$ . Without loss of generality, suppose that $h_{n_{1}}[t]\geq...\geq h_{n_{M}}[t]$ . Let

v_{n_{m}}[t]=\frac{q_{n_{m}}[t-1]+a_{n_{m}}[t]L}{\log(1+h^{2}_{n_{m}}[t]\rho)}

(10)

denote the number of channel symbols used to clear user $n_{m}$ ’s buffer. Under the GCFS policy, $s_{n}[t]$ is then given by the following corollary.

Corollary 1: There exits a threshold $\iota$ given by

\iota=\mathop{\arg\max}_{m_{t}}\sum_{m=1}^{m_{t}}v_{n_{m}}[t]\leq WT,1\leq m_{t}\leq M.

(11)

For users in set $\{n_{1},...,n_{\iota}\}$ , $s_{n_{m}}[t]=q_{n_{m}}[t-1]+a_{n_{m}}[t]L$ . For user $n_{\iota+1}$ ,

s_{n_{\iota+1}}[t]=\Big{(}WT-\sum_{m=0}^{\iota}v_{n_{m}}[t]\Big{)}\log\Big{(}1+h^{2}_{n_{\iota+1}}[t]\rho\Big{)}.

(12)

Finally, for users in set $\{n_{\iota+2},...,n_{M}\}$ , $s_{n_{m}}[t]=0$ .

Proof:

The proof is omitted due to space limitations. ∎

According to Corollary 1, the first $\iota$ users in set $\{n_{1},...,n_{M}\}$ will surely get their data buffer cleared by the end of timeslot $t$ .

IV Mean-Field Approximation based
Delay Analysis

In this section, we aim to analyze the delay performance of the GCFS policy. Under the GCFS policy, a discrete-time continuous-state $N$ -dimensional Markov chain $\{q_{n}[t],1\leq n\leq N,t\geq 0\}$ is induced. Due to the curse of dimensionality, it is hard to analyze the performance of the GCFS policy by deriving the stationary distribution of the Markov chain when $N\gg 1$ . To evaluate the delay performance of the GCFS policy, we apply a mean-field approximation method introduced in [11].

IV-A Mean-Field Approximation and Threshold-based policy

In this section, we aim to analyze the delay performance of the GCFS policy via a mean-field approximation method. Let $g(q_{1},q_{2},...,q_{N})$ denote the stationary probability density function (PDF) of the Markov chain $\{q_{n}[t],1\leq n\leq N,t\geq 0\}$ . According to the mean field approximation, we have

g(q_{1},q_{2},...,q_{N})\approx\Pi_{n=1}^{N}g_{n}(q_{n}),

(13)

when $N\to\infty$ . This is due to that all users’ impacts on a single user become certain when $N\to\infty$ . In other words, the dependence among users vanishes in this downlink system as $N\to\infty$ . Besides, since all users’ arrival process and channel quality are i.i.d., the PDFs $g_{1}(q_{1}),...,g_{N}(q_{N})$ shall be identical. As a result, variables $q_{n}[t],1\leq n\leq N$ are i.i.d. when the induced Markov chain is stationary. According to the law of large numbers, we have

\begin{split}\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^{N}q_{n}[t]=\mathbb{E}\{q_{n}[t]\}={q}.\end{split}

(14)

Similarly, we have $\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^{N}a_{n}[t]L=\lambda$ . That is to say that the average queue length and the average number of arriving bits in a timeslot are two constant when $N\to\infty$ . The average number bits served in a timeslot, i.e., $\frac{1}{N}\sum_{n=0}^{N}s_{n}[t]$ shall also be constant that equals to $\lambda$ . As a result, we have

\lim_{N\to\infty}\frac{1}{N}\sum_{n=0}^{N}s_{n}[t]=\lambda.

(15)

Under the GCFS policy, there exist a threshold $h_{\text{th}}$ on the channel gain that a user will get served when his channel gain is greater than $h_{\text{th}}$ . Let $f(h)$ be the PDF of the channel gain $h_{n}[t]$ . The cumulative distribution function of $h_{n}[t]$ is denoted by $F(x)$ , where $F(x)=\int_{0}^{x}f(h)dh$ . Set $G(x)=1-F(x)$ . According to $h_{\text{th}}$ , each user has the same probability $p=G(h_{\text{th}})$ to get served. As a result, there are about $Np$ users get served. Let $n_{1},...,n_{Np}$ denote the $Np$ users where $h_{n_{1}}[t]\geq...\geq h_{n_{Np}}[t]$ . According to Corollary 1, the first $Np-1$ users will get their buffer cleared and the last user’s bits are partially served. As a result, the total number of bits served in a timeslot is given by

\sum_{n=0}^{N}s_{n}[t]=s_{Np}[t]+\sum_{m=1}^{Np-1}(q_{n_{m}}[t-1]+a_{n_{m}}[t]L),

(16)

According to Eqs. (14) and (15), we have

\begin{split}&\lim_{N\to\infty}\frac{1}{N}\Big{(}s_{Np}[t]+\sum_{m=1}^{Np-1}(q_{n_{m}}[t-1]+a_{n_{m}}[t]L)\Big{)}\\ =&\lim_{N\to\infty}\frac{1}{N}\sum_{m=1}^{Np-1}(q_{n_{m}}[t-1]+a_{n_{m}}[t]L)=p({q}+\lambda)=\lambda.\end{split}

(17)

Eq. (17) indicates that $p$ and $h_{\text{th}}$ is a constant. As a result, a threshold-based policy which serves all backlogged packets of users whose channel gains are beyond $h_{\text{th}}$ can approximately achieves the minimum queueing latency, which has a lower complexity when compared with the GCFS policy. Besides, by Eq. (17), the average queue delay of each user is given by

D=\frac{{q}}{\lambda}=\frac{1}{p}-1.

(18)

Next, we aim to establish a self-consistent equation to derive the unknown threshold $h_{\text{th}}$ and constant $p$ . Based on the channel threshold $h_{\text{th}}$ , the most average number of bits that can be transmitted in each timeslot can be computed as

\Phi(h_{\text{th}})=\frac{\displaystyle WT\int_{h_{\text{th}}}^{\infty}f(h)log(1+h^{2}\rho){\rm d}h}{G(h_{\text{th}})}.

(19)

Let $h_{u}=\sup\{h|G(h)>0\}$ . The feasible region of $h_{\text{th}}$ is given by $[0,h_{u})$ . The property of function $\Phi(h_{\text{th}})$ is presented in the following lemma.

Lemma 1: $\Phi(h_{\text{th}})$ is non-decreasing in $h_{\text{th}}$ .

Proof:

We derive the derivative of the function $\Phi(h_{\text{th}})$ , which is given by

\Phi^{\prime}(h_{\text{th}})=\frac{\displaystyle WTf(h_{\text{th}})\int_{h_{\text{th}}}^{\infty}f(h)\big{(}\log(1+h^{2}\rho)-\log(1+h_{\text{th}}^{2}\rho)\big{)}{\rm d}h}{G^{2}(h_{\text{th}})}.

(20)

Since

\int_{h_{\text{th}}}^{\infty}f(h)\big{(}\log(1+h^{2}\rho)-\log(1+h_{\text{th}}^{2}\rho)\big{)}{\rm d}h\geq 0,

(21)

we have $\Phi^{\prime}(h_{\text{th}})\geq 0$ . As a result, $\Phi(h_{\text{th}})$ is a non-decreasing function of the threshold $h_{\text{th}}$ . ∎

According to Lemma 1, the supremum of $\Phi(h_{\text{th}})$ is given by

\Phi_{\sup}=\lim_{h_{\text{th}}\to h_{u}}\Phi(h_{\text{th}})=WT\log(1+h_{u}^{2}\rho).

(22)

The minimum of $\Phi(h_{\text{th}})$ is $\Phi(0)$ . In order to keep this queueing system stable, the average number of bits transmitted in each timeslot shall equal the average number of bits arriving in each timeslot. As a result, we have

\Phi(h_{\text{th}})=N\lambda.

(23)

Eq. (23) is the self-consistent equation we want to establish. By solving Eq. (23), we can obtain the unknown threshold $h_{\text{th}}$ and the unknown constant $p$ . In particular, when $\Phi_{\sup}<N\lambda$ , this queueing system is unstable. More transmission power shall be applied in this case to enhance the service capability of the system. When $\Phi(0)>N\lambda$ , we can reduce the transmission power to make full use of the spectrum resources. Since $\Phi(h_{\text{th}})$ is a non-decreasing function, we can apply Algorithm 1 to derive the threshold $h_{\text{th}}$ .

Algorithm 1 The Algorithm to obtain the unknown channel quality threshold

h_{\text{th}}

N,\lambda,\rho,f(h),G(x),h_{u},\epsilon

h_{\text{th}}

3:if

\Phi(0)\geq N\lambda

then

4: return 0

5:end if

6:if

\Phi_{sup}\leq N\lambda

then

7: return

h_{u}

8:end if

h_{l}\leftarrow 0

h_{r}\leftarrow h_{u}

h_{\text{th}}\leftarrow\frac{1}{2}(h_{l}+h_{r})

10:while

|\Phi(h_{\text{th}})-N\lambda|>\epsilon

11: if

\Phi(h_{\text{th}})>N\lambda

then

12:

h_{r}=h_{\text{th}}

13: else

14:

h_{l}=h_{\text{th}}

15: end if

16:

h_{\text{th}}\leftarrow\frac{1}{2}(h_{l}+h_{r})

17:end while

IV-B Equivalent Single User Queue via Decomposition

In this subsection, we aim to approximate the stationary distribution of the each user’s queue length based on the mean filed approximation results in the last subsection.

Eq. (13) indicates that the dependence among users vanishes as $N\to\infty$ . As a result, we can decompose the complex massive user downlink system into multiple equivalent single user systems. Eq. (17) indicates we can ignore the user whose bits are partially served. As a result, in each single user system, all packets in a user’s buffer are approximately either all transmitted with probability $p$ or all remained in the buffer with probability $1-p$ in each timeslot. Let $\tilde{q}[t]$ denote the number of packets that remain in the buffer of user $n$ by the end of timeslot $t$ . According to the arrival process $a_{n}[t]$ , we can construct a discrete-time discrete-state Markov chain $\{\tilde{q}[t],t\geq 0\}$ to model the queue length dynamics of each single user system, which is illustrated in Fig. 2. Let $P_{i,j}=\Pr\{\tilde{q}[t+1]=j|\tilde{q}[t]=i\}$ be the one-step transition probability of this new Markov chain, which is given in the following lemma.

Lemma 2: The one-step transition probability of the new Markov chain is given by

P_{i,j}=\left\{\begin{split}&\theta_{0}+\bar{\theta}_{0}p,i=j=0,\\ &\theta_{0}\bar{p},\qquad\;i=j>0,\\ &\theta_{a}\bar{p},\qquad\;i-j=a,0<a\leq A,\\ &p,\qquad\quad\;i>0,j=0,\\ &0,\qquad\quad\;\text{otherwise},\end{split}\right.

(24)

where $\bar{\theta}_{0}=1-\theta_{0}$ and $\bar{p}=1-p$ .

Proof:

The proof is omitted due to space limitations. ∎

Let $\pi_{i}$ denote the steady-state probability of state $\tilde{q}[t]=i$ of the discrete-time discrete-state Markov chain $\{\tilde{q}[t],t\geq 0\}$ . According to Lemma 2, we have

\sum_{j=i+A}^{\infty}\pi_{j}p=\sum_{j=0}^{A-1}\sum_{k=A-j}^{A}\pi_{i+j}\theta_{k}\bar{p},i\geq 0.

(25)

It should be noted that Eq. (25) is the local balance equation of the new discrete-time discrete-state Markov chain. Let $\chi_{i}=\sum_{j=i}^{\infty}\pi_{j}$ . As a result, we have

\pi_{i}=\chi_{i}-\chi_{i+1}.

(26)

By submitting Eq. (26) into Eq. (25), we have

\chi_{i+A}c_{A}-\sum_{j=0}^{A-1}\chi_{i+j}c_{j}=0,i\geq 0,

(27)

where $c_{A}=p+\bar{\theta}_{0}\bar{p}$ , and $c_{j}=\theta_{A-j}\bar{p}$ for $j\in[A-1]$ . Eq. (27) is a linear difference equation. To solve Eq. (27), $A$ boundary conditions are needed, which are given in the following lemma.

Lemma 3: The $A$ boundary conditions of the linear difference Eq. (27) are given by

\left\{\begin{split}&\chi_{0}=1,\\ &\chi_{i}=\frac{\displaystyle\chi_{0}\sum_{k=i}^{A}\theta_{k}\bar{p}+\sum_{j=1}^{i-1}\chi_{j}\theta_{i-j}\bar{p}}{p+\bar{\theta}_{0}\bar{p}},1\leq i\leq A-1.\end{split}\right.

(28)

Proof:

The proof is omitted due to space limitations. ∎

Next, we aim to solve the linear difference Eq. (27) with $A$ boundary conditions by the unilateral $z$ -transforms. Let $\tilde{\pi}(z)$ and $\tilde{\chi}(z)$ denote the unilateral $z$ -transforms of sequences $\{\pi_{i}\}$ and $\{\chi_{i}\}$ , respectively. The unilateral $z$ -transform of Eq. (27) is given in the following theorem.

Theorem 3: The unilateral $z$ -transform of the linear difference Eq. (27) is given by

\tilde{\chi}(z)=\frac{\displaystyle\sum_{j=0}^{A-1}\chi_{j}\bigg{(}\sum_{k=j+1}^{A-1}c_{k}z^{A-k}-c_{A}z^{j}\bigg{)}}{\displaystyle\sum_{j=0}^{A-1}c_{j}z^{A-j}-c_{A}}.

(29)

Proof:

The proof is omitted due to space limitations. ∎

Similar to Theorem 3, we can derive the unilateral $z$ -transform of Eq. (26). By deriving the unilateral $z$ -transform of Eq. (26), we can obtain

\tilde{\pi}(z)=\frac{(z-1)\tilde{\chi}(z)+1}{z}.

(30)

We omit the derivation of Eq. (30) due to space limitations. Let $\mathcal{Z}^{-1}(\cdot)$ denote the inverse unilateral $z$ -transform operator. The steady-state probability of the discrete-state Markov chain is then given by

\pi_{i}=\mathcal{Z}^{-1}(\tilde{\pi}(z)).

(31)

In particular, when $A=1$ , the steady-state probabilities $\{\pi_{i}\}$ are given in the following corollary.

Corollary 2: When $A=1$ , the steady-state probabilities $\{\pi_{i}\}$ are given by

\begin{split}&\pi_{0}=\frac{p}{p\theta_{0}+\theta_{1}},\\ &\pi_{i}=\pi_{0}(1-\pi_{0})^{i},i\leq 1.\end{split}

(32)

Proof:

The proof is omitted due to space limitations. ∎

V Numerical Result

In this section, numerical results are presented to demonstrate the theoretical analysis. In the simulations, the number of users and the maximum number of packets arriving at each user’s buffer are set to $N=10^{5}$ and $A=1$ , respectively. The length of a packet is set to $L=1$ . The bandwidth and the time interval of a slot are set to $W=1$ and $T=10^{3}$ , respectively. The noise power at each user’s receiver is set to $\sigma^{2}=10^{-12}$ . Assume that the magnitude of user $n$ ’s channel gain, i.e., $h_{n}[t]$ is a Rayleigh random variable, which has a density distribution $f(h)=he^{\frac{-h^{2}}{2}}$ . In each timeslot, the packet arrival of each user’s buffer follows a Bernoulli arrival process with parameter $\theta_{1}$ . The BS allocates channel symbols according to Theorem 1. Each user’s buffer evolves according to Eq. (3) with each simulation running over $10^{5}$ timeslots. The simulation results and the results derived by the mean-field approximation are presented in the following figures.

Fig. 3 present the delay performance of the GCFS policy under different arrival rates $\theta_{1}$ . In Fig. 3, the average packet delay approximated by the mean-field approximation method and the average bit delay derived through simulation are denoted by solid lines and marks ‘o’, respectively. From Fig. 3, it can be seen that the average bit delay under the GCFS policy can be well approximated by the average packet delay derived through the mean-field approximation method proposed in this paper. Fig. 3 also presents the basic tradeoffs between the queueing delay and the power consumption. When more transmission power is applied, the queueing delay decreases.

Fig. 4 present the probability distribution of the number of packets in one user’s buffer under different transmission powers $\mathcal{P}$ . In Fig. 4, the arrival rate and the time interval of a slot are set to $\theta_{1}=0.6$ and $T=2\times 10^{3}$ , respectively. The probability distributions of the number of packets in one user’s buffer derived by mean-field approximation and simulation are denoted by solid lines and marks ‘o’, respectively. From Fig. 4, it can be seen that the probability distributions of the number of packets in one user’s buffer derived by the mean-field approximation and simulation match well. This demonstrates that the established discrete-state Markov chain depicted in Fig. 2 well reflects the dynamic characteristics of each user’s queue length.

VI Conclusion

In this paper, we have investigated the problem of queueing delay minimization in a downlink communication scenario with massive receivers. To minimize the average total queueing delay, we have derived the optimal scheduling policy, referred to as the GCFS policy, by analyzing the established stochastic optimization problem. Furthermore, to overcome the difficulty in analyzing the performance of the GCFS policy due to the massive users, we have applied a mean-field approximation method. We have obtained a threshold-based policy with lower complexity which can approximately achieve minimum delay. Moreover, we have shown that the complex downlink system with massive users can be decomposed into massive single-user scenarios. Besides, we have established a Markov chain model for the equivalent single-user scenario to analyze the stationary distribution of each user’s queue length. Numerical results have demonstrated that the average queueing delay under the GCFS policy can be well evaluated by the mean-field approximation method.

References

[1] K. B. Letaief, W. Chen, Y. Shi, J. Zhang, and Y. A. Zhang, “The roadmap to 6G: AI empowered wireless networks,” IEEE Communications Magazine, vol. 57, no. 8, pp. 84–90, Aug. 2019.
[2] W. Saad, M. Bennis, and M. Chen, “A vision of 6g wireless systems: Applications, trends, technologies, and open research problems,” IEEE Network, vol. 34, no. 3, pp. 134–142, May/Jun. 2020.
[3] L. Tassiulas and A. Ephremides, “Dynamic server allocation to parallel queues with randomly varying connectivity,” IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466–478, Mar. 1993.
[4] R. A. Berry, “Optimal power-delay tradeoffs in fading channels-small-delay asymptotics,” IEEE Transactions on Information Theory, vol. 59, no. 6, pp. 3939–3952, Jun. 2013.
[5] W. Chen, Z. Cao, and K. B. Letaief, “Optimal delay-power tradeoff in wireless transmission with fixed modulation,” in 2007 International Workshop on Cross Layer Design, Sept. 2007, pp. 60–64.
[6] J. Liu, W. Chen, and K. B. Letaief, “Delay optimal scheduling for arq-aided power-constrained packet transmission over multi-state fading channels,” IEEE Transactions on Wireless Communications, vol. 16, no. 11, pp. 7123–7137, Nov. 2017.
[7] X. Zhao, W. Chen, J. Lee, and N. B. Shroff, “Delay-optimal and energy-efficient communications with markovian arrivals,” IEEE Transactions on Communications, vol. 68, no. 3, pp. 1508–1523, Mar. 2020.
[8] X. Zhao and W. Chen, “Non-orthogonal multiple access for delay-sensitive communications: A cross-layer approach,” IEEE Transactions on Communications, vol. 67, no. 7, pp. 5053–5068, Jul. 2019.
[9] G. Caire, D. Tuninetti, and S. Verdu, “Suboptimality of tdma in the low-power regime,” IEEE Transactions on Information Theory, vol. 50, no. 4, pp. 608–620, Apr. 2004.
[10] T. M. Cover and J. A. Thomas, Elements of Information Theory, 1991.
[11] P. M. Chaikin and T. C. Lubensky, Principles of Condensed Matter Physics. Cambridge University Press, 1995.

Mean-Field Approximation based Scheduling for Broadcast Channels with Massive Receivers

Abstract

I Introduction

II System Model

II-A The Physical Layer

II-B Discrete-time Queue Model

III Delay-Optimal Scheduling with Massive Users

Proof:

Proof:

Proof:

IV Mean-Field Approximation based Delay Analysis

IV-A Mean-Field Approximation and Threshold-based policy

Proof:

IV-B Equivalent Single User Queue via Decomposition

Proof:

Proof:

Proof:

Proof:

V Numerical Result

VI Conclusion

References

IV Mean-Field Approximation based
Delay Analysis