CF1885A.Deterministic Scheduling for Extended Reality over 5G and Beyond

Background

Extended reality (XR) service is a promising application for future communications. In wireless communications, XR data are transmitted over radio between base stations and mobile terminals. A region is usually divided into multiple cells, each of which is equipped with a base station to serve users. One base station usually serves multiple users, and multiple base stations may serve one user at the same time.

Task

The task of this competition is to design a scheduling algorithm for XR service. By properly allocating radio resources, we want to maximize the number of XR data frames that are successfully transmitted. A diagram is provided below for illustration: The transmission of a data frame is failed when it cannot be completely transmitted during the permitted transmission time window.

Therefore, the objective of this task can be modeled as: $$ \mathcal{P}: \max \sum_j f_j \tag{1} $$ $$ f_j=\left\{\begin{array}{c} 1, g_j \geq T B S_j \\ 0, g_j \lt T B S_j \end{array}\right. \tag{2} $$ Here, $f_j$ represents the transmission result of the $j$-th frame: when the actual transmitted bits $g_j$ (computed via (5)) is not less than the size of the frame, i.e., $TBS_j$ (transport block size), the frame would be successfully transmitted so that $f_j=1$. Otherwise, $f_j=0$.

To achieve better user experience, scheduling algorithm should be proposed to efficiently assign the limited radio resources:

• Time domain resource, which is divided into several transmission time intervals (TTIs), each TTI corresponds to a transmission time of $0.5$ms.
• Frequency domain resource, which is divided into several resource block groups (Resource Block Group, RBG), each RBG corresponds to a transmission bandwidth of $5760$ kHz.
• Power domain resource: each cell has a fixed maximum transmission power to serve users.

Summarily, two optimization variables are introduced to represent the scheduling result: $$ b_{r n t}^{(k)} \in\{0,1\} \tag{3} $$ $$ p_{ {rnt }}^{(k)} \geq 0 , \quad \sum_r \sum_n p_{ {rnt }}^{(k)} \leq R, \quad \sum_n p_{ {rnt }}^{(k)} \leq 4 \tag{4} $$ Here, $b_{rnt}^{(k)}$ is a Boolean variable denoting whether the $r$-th RBG of cell $k$ is allocated to user $n$ at TTI $t$, and $p_{rnt}^{(k)}$ is a nonnegative continuous variable denoting the power allocated to user $n$ in the $r$-th RBG of cell $k$ at TTI $t$. For each TTI of each cell, the power range of each RBG is between $0$ and $4$, and the total power of all RBGs can not be larger than $R$.

When the radio resources are allocated to the users, the XR data transmission can be provided for them. Assume that the $j$-th frame belongs to the $n$-th user, the actual transmitted bits for the frame, i.e., $g_j$ can be given by:

g\_{j}= W\\times \\sum\_{t=t\_{0, j}}^{t\_{1, j}} \\sum\_k \\sum\_r b\_{r n t}^{(k)} \\times \\log \_2\\left(1+s\_{n t}^{(k)}\\right). \\tag{5} $$ Note that $W\times \mathrm{log}_2 (1+s_{nt}^{(k)} ) $ is the well-known Shannon formula, which represents the transmitted data volume, where $s_{nt}^{(k)}$ represents the transmission SINR (Signal-to-Interference-plus-Noise-Ratio) of user $n$ in cell $k$ at TTI $t$, and $W=192$ is the constant number of available frequency resounce elements of one RBG. $t_{0,j}$ and $t_{1,j}$ denote the start TTI and the end TTI of frame $j$, respectively. The physical meaning of Formula (5) is that the number of bits transmitted within the valid time period, $t_{0,j}\sim t_{1,j}$, will be counted as valid transmission bits for the $j$-th frame. Finally, we give the expression of SINR, which may be complicated but corresponds to the actual physical transmission: $$ s\_{nt}^{\\left( k \\right)} = {\\left( {\\prod\\limits\_{r,b\_{rnt}^{\\left( k \\right)} = 1} {s\_{rnt}^{\\left( k \\right)}} } \\right)^{\\frac{1}{{\\sum\\nolimits\_r {b\_{rnt}^{\\left( k \\right)}} }}}} \\tag{6} $$ $$ s\_{r n t}^{(k)}=\\frac{s\_{0, r n t}^{(k)} \\times p\_{r n t}^{(k)} \\times \\prod\_{m \\neq n} e^{d^{(k)}\_{mrn} \\times b\_{r m t}^{(k)}}}{1+\\sum\_{k^{\\prime} \\neq k, n^{\\prime} \\neq n} s\_{0, r n t}^{(k^{\\prime})} \\times p\_{r n^{\\prime} t}^{\\left(k^{\\prime}\\right)} \\times e^{-d^{(k^{\\prime})}\_{n^{\\prime}rn}}} \\tag{7}

Formula (6) shows the computation of user-level effective SINR: the transmission SINR of user $n$, i.e., $s_{nt}^{(k)}$, is the geometric mean of the SINRs of scheduled RBGs. Then, formula (7) shows the computation of RBG-level effective SINR. $s_{0,rnt}^{(k)}$ is a given constant denoting the initial SINR on RBG $r$ of cell $k$ at TTI $t$, which indicates the quality of the channel. Another given constant value $d^{(k)}_{mrn}$ represents the interference factor between user $m$ and user $n$ on RBG $r$, when user $m$ is scheduled on cell $k$. Note that $d^{(k)}_{mrn}=d^{(k)}_{nrm}\le 0$, which reveals that scheduling multiple users on the same RBG-TTI resource will cause a decrease in the SINR of each user.

To sum up, participants are required to find an efficient radio resource allocation, so that more XR data frames can be successfully transmitted.

背景

扩展现实（XR）服务是未来通信中极具前景的应用之一。在无线通信中，XR 数据通过基站与移动终端之间的无线信道进行传输。一个区域通常被划分为多个小区，每个小区配备一个基站为用户服务。一个基站通常同时为多个用户服务，而一个用户也可能同时由多个基站服务。

任务

本次竞赛的任务是为 XR 服务设计一种调度算法。通过合理分配无线资源，目标是最大化成功传输的 XR 数据帧数量。下图用于示意说明：当数据帧无法在允许的传输时间窗口内完成全部传输时，该次传输即视为失败。

因此，本任务的目标可建模为：

$$\mathcal{P}: \max \sum_j f_j \tag{1}$$

$$f_j=\left\{\begin{array}{c} 1, \; g_j \geq TBS_j \\ 0, \; g_j < TBS_j \end{array}\right. \tag{2}$$

其中，$f_j$ 表示第 $j$ 个数据帧的传输结果：当实际传输比特数 $g_j$（由式 (5) 计算得出）不小于该帧大小（即传输块大小 $TBS_j$）时，该帧被成功传输，故 $f_j = 1$；否则 $f_j = 0$。

为提升用户体验，需提出一种调度算法，以高效分配有限的无线资源：

• 时域资源：划分为若干传输时间间隔（TTI），每个 TTI 对应 $0.5$ ms 的传输时间；
• 频域资源：划分为若干资源块组（Resource Block Group, RBG），每个 RBG 对应 $5760$ kHz 的传输带宽；
• 功率域资源：每个小区具有固定的最大发射功率用于服务用户。

综上，引入两个优化变量来表示调度结果：

$$b_{rnt}^{(k)} \in \{0,1\} \tag{3}$$

$$p_{rnt}^{(k)} \geq 0 , \quad \sum_r \sum_n p_{rnt}^{(k)} \leq R, \quad \sum_n p_{rnt}^{(k)} \leq 4 \tag{4}$$

其中，$b_{rnt}^{(k)}$ 是一个布尔变量，表示在第 $t$ 个 TTI 内，第 $k$ 个小区的第 $r$ 个 RBG 是否分配给第 $n$ 个用户；$p_{rnt}^{(k)}$ 是一个非负连续变量，表示在第 $t$ 个 TTI 内，第 $k$ 个小区的第 $r$ 个 RBG 分配给第 $n$ 个用户的发射功率。对每个小区的每个 TTI，每个 RBG 的功率取值范围为 $[0, 4]$，且所有 RBG 的总功率之和不得超过 $R$。

当无线资源被分配给用户后，即可为其提供 XR 数据传输服务。假设第 $j$ 个数据帧属于第 $n$ 个用户，则该帧的实际传输比特数 $g_j$ 可表示为：

$$g_{j}= W\times \sum_{t=t_{0, j}}^{t_{1, j}} \sum_k \sum_r b_{r n t}^{(k)} \times \log_2\left(1+s_{n t}^{(k)}\right). \tag{5}$$

注意，$W\times \log_2 (1+s_{nt}^{(k)} ) $ 是经典的香农公式，表示传输的数据量，其中 $s_{nt}^{(k)}$ 表示第 $n$ 个用户在第 $k$ 个小区、第 $t$ 个 TTI 的传输 SINR（信号与干扰加噪声比），$W=192$ 是单个 RBG 所含可用频域资源单元（resource element）的固定数目。$t_{0,j}$ 和 $t_{1,j}$ 分别表示第 $j$ 个数据帧的起始 TTI 和终止 TTI。式 (5) 的物理含义是：在有效时间区间 $t_{0,j} \sim t_{1,j}$ 内传输的比特数，将被计入第 $j$ 个数据帧的有效传输比特数。

最后，给出 SINR 的表达式。该式虽较复杂，但符合实际物理传输过程：

$$s_{nt}^{\left( k \right)} = {\left( {\prod\limits_{r,\,b_{rnt}^{\left( k \right)} = 1} {s_{rnt}^{\left( k \right)}} } \right)^{\frac{1}{{\sum\nolimits_r {b_{rnt}^{\left( k \right)}} }}}} \tag{6}$$

$$s_{r n t}^{(k)}=\frac{s_{0, r n t}^{(k)} \times p_{r n t}^{(k)} \times \prod_{m \neq n} e^{d^{(k)}_{mrn} \times b_{r m t}^{(k)}}}{1+\sum_{k^{\prime} \neq k,\, n^{\prime} \neq n} s_{0, r n t}^{(k^{\prime})} \times p_{r n^{\prime} t}^{\left(k^{\prime}\right)} \times e^{-d^{(k^{\prime})}_{n^{\prime}rn}}} \tag{7}$$

式 (6) 给出用户级有效 SINR 的计算方法：用户 $n$ 的传输 SINR $s_{nt}^{(k)}$ 等于其被调度的所有 RBG 对应 SINR 的几何平均值。式 (7) 则给出 RBG 级有效 SINR 的计算方法。其中，$s_{0,rnt}^{(k)}$ 是一个给定常数，表示第 $k$ 个小区在第 $t$ 个 TTI 下第 $r$ 个 RBG 上的初始 SINR，反映信道质量；另一给定常数 $d^{(k)}_{mrn}$ 表示当用户 $m$ 被调度至第 $k$ 个小区时，其对用户 $n$ 在第 $r$ 个 RBG 上的干扰因子。注意 $d^{(k)}_{mrn}=d^{(k)}_{nrm}\le 0$，表明在同一 RBG-TTI 资源上调度多个用户，将导致各用户 SINR 下降。

综上，参赛者需寻找一种高效的无线资源分配方案，以使尽可能多的 XR 数据帧成功传输。

The input of a single test has $(4 + R \cdot K \cdot T + N \cdot R \cdot K + 1 + J)$ lines, which contains user number $N$, cell number $K$, TTI number $T$, RBG number $R$, initial SINRs $s_{0, r n t}^{(k)}$, interference factors $d_{mrn}$, frame number $J$ and information about $J$ frames.

The details are as follows:

• Line $1$: User number $N$, integer, $1 \leq N \leq 100$. Users are numbered from $0$ to $N - 1$.
• Line $2$: Cell number $K$, integer, $1 \leq K \leq 10$. Cells are numbered from $0$ to $K - 1$.
• Line $3$: TTI number $T$, integer, $1 \leq T \leq 1000$. TTIs are numbered from $0$ to $T - 1$.
• Line $4$: RBG number $R$, integer, $1 \leq R \leq 10$. RBGs are numbered from $0$ to $R - 1$.
• Line $5$ to $(4+R \cdot K\cdot T)$: Initial SINRs $s_{0, r n t}^{(k)}$, float, $0 \lt s_{0, r n t}^{(k)} \lt 10\,000$. Each line has $N$ elements, corresponding to $N$ users. $s_{0, r n t}^{(k)}$ is the $(n+1)$-th element of line $(5+r+k \cdot R+t \cdot K \cdot R)$.
• Line $(5+R \cdot K \cdot T)$ to $(4+R \cdot K \cdot T + N \cdot R \cdot K)$: Interference factors $d^{(k)}_{mrn}$, float, $-2 \leq d^{(k)}_{mrn} \leq 0$. Each line has $N$ elements, corresponding to $N$ users. $d^{(k)}_{mrn}$ is the $(n+1)$-th element of line $(5+R \cdot K \cdot T+m+r \cdot N + k \cdot R \cdot N)$.
• Line $(5+R \cdot K \cdot T + N \cdot R \cdot K)$: Frame number $J$, integer, $1 \leq J \leq 5000$.
• Last $J$ lines: Frame information. Each line contains $5$ integers corresponding to a frame, which are, in order: frame ID $j\in{0,\ldots,J-1}$ in increasing order, size $TBS_j$ ($0 \lt TBS_j \leq 100\,000$), user ID it belongs to, first TTI $t_{0,j} \in{0,\ldots,T-1}$, and number of TTIs $t_{d,j} \in \left[ {1,100} \right]$. Last TTI for frame $j$ can be found as $t_{1,j}=t_{0,j}+t_{d,j}-1$; it is guaranteed that $t_{1,j} \le T - 1$.

It is guaranteed that each user has at most one frame at each TTI.

单个测试用例的输入共包含 $(4 + R \cdot K \cdot T + N \cdot R \cdot K + 1 + J)$ 行，其中包含用户数 $N$、小区数 $K$、TTI 数 $T$、RBG 数 $R$、初始 SINR 值 $s_{0, r n t}^{(k)}$、干扰因子 $d_{mrn}$、帧数 $J$，以及关于 $J$ 个帧的信息。

具体格式如下：

• 第 $1$ 行：用户数 $N$，整数，满足 $1 \leq N \leq 100$。用户编号为 $0$ 至 $N - 1$。
• 第 $2$ 行：小区数 $K$，整数，满足 $1 \leq K \leq 10$。小区编号为 $0$ 至 $K - 1$。
• 第 $3$ 行：TTI 数 $T$，整数，满足 $1 \leq T \leq 1000$。TTI 编号为 $0$ 至 $T - 1$。
• 第 $4$ 行：RBG 数 $R$，整数，满足 $1 \leq R \leq 10$。RBG 编号为 $0$ 至 $R - 1$。
• 第 $5$ 行至第 $(4+R \cdot K\cdot T)$ 行：初始 SINR 值 $s_{0, r n t}^{(k)}$，浮点数，满足 $0 \lt s_{0, r n t}^{(k)} \lt 10\,000$。每行含 $N$ 个元素，分别对应 $N$ 个用户。$s_{0, r n t}^{(k)}$ 是第 $(5+r+k \cdot R+t \cdot K \cdot R)$ 行的第 $(n+1)$ 个元素。
• 第 $(5+R \cdot K \cdot T)$ 行至第 $(4+R \cdot K \cdot T + N \cdot R \cdot K)$ 行：干扰因子 $d^{(k)}_{mrn}$，浮点数，满足 $-2 \leq d^{(k)}_{mrn} \leq 0$。每行含 $N$ 个元素，分别对应 $N$ 个用户。$d^{(k)}_{mrn}$ 是第 $(5+R \cdot K \cdot T+m+r \cdot N + k \cdot R \cdot N)$ 行的第 $(n+1)$ 个元素。
• 第 $(5+R \cdot K \cdot T + N \cdot R \cdot K)$ 行：帧数 $J$，整数，满足 $1 \leq J \leq 5000$。
• 最后 $J$ 行：帧信息。每行含 $5$ 个整数，依次表示一个帧的以下属性：帧 ID $j\in{0,\ldots,J-1}$（按升序排列）、传输块大小 $TBS_j$（满足 $0 \lt TBS_j \leq 100\,000$）、所属用户 ID、起始 TTI $t_{0,j} \in{0,\ldots,T-1}$、TTI 数量 $t_{d,j} \in \left[ {1,100} \right]$。帧 $j$ 的终止 TTI 为 $t_{1,j}=t_{0,j}+t_{d,j}-1$；保证 $t_{1,j} \le T - 1$。

保证每个用户在每个 TTI 上至多拥有一个帧。

Output for a certain input is the optimization result of $p_{r n t}^{(k)}$ (float), which has $R \cdot K \cdot T$ lines. Each line has $N$ elements, corresponding to $N$ users. $p_{r n t}^{(k)}$ is the $(n+1)$-th element of line $(1+r+k \cdot R+t \cdot K \cdot R)$.

Note that the optimization result of $b_{r n t}^{(k)}$ does not need to be output, because $p_{r n t}^{(k)} \gt 0$ and $p_{r n t}^{(k)} = 0$ means $b_{r n t}^{(k)}=1$ and $b_{r n t}^{(k)} = 0$, respectively.

Please note that if the outputs do not meet the constraint (4), it will be judged as an incorrect answer and get score $0$. Besides, transmit on some TTIs out of time window is valid, but usually results in a lower score due to resources waste.

对于某一输入，输出为 $p_{r n t}^{(k)}$（浮点数）的优化结果，共 $R \cdot K \cdot T$ 行。每行包含 $N$ 个元素，分别对应 $N$ 个用户。$p_{r n t}^{(k)}$ 是第 $(1+r+k \cdot R+t \cdot K \cdot R)$ 行的第 $(n+1)$ 个元素。

注意：无需输出 $b_{r n t}^{(k)}$ 的优化结果，因为当 $p_{r n t}^{(k)} \gt 0$ 时，有 $b_{r n t}^{(k)}=1$；而当 $p_{r n t}^{(k)} = 0$ 时，有 $b_{r n t}^{(k)} = 0$。

请注意：若输出不满足约束条件 (4)，将被判为错误答案，得分为 $0$。此外，在时间窗口之外的某些 TTI 上进行传输是允许的，但通常会因资源浪费而导致得分降低。

Two sets of tests are prepared in this problem. For the duration of the competition, each submission is tested on the preliminary set of tests. When the competition is finished, for each contestant:

The jury takes the latest submission with non-zero score on preliminary tests;

This submission is tested on the final set of tests for the final rank;

The two sets of tests are generated from the same pool of data, based on the real word data.

本题准备了两组测试数据。在比赛期间，每次提交将仅在预测试数据集上进行测试。当比赛结束后，对每位参赛者：

• 评委会选取其在预测试数据集中得分非零的最新一次提交；
• 该提交将在最终测试数据集上进行测试，以确定最终排名；

这两组测试数据均基于真实世界数据，从同一数据池中生成。