← 返回题目列表

Codeforces · 1885/A

A. 5G 及以上扩展现实的确定性调度

中文机器翻译题面 查看原题

背景

扩展现实 (XR) 服务是未来通信的一个有前景的应用。在无线通信中,XR 数据通过无线电在基站和移动终端之间传输。一个区域通常被划分为多个小区,每个小区配备一个基站为用户提供服务。一个基站通常为多个用户服务,多个基站也可以同时为一个用户服务。

任务

本次竞赛的任务是设计XR服务的调度算法。通过正确分配无线资源,我们希望最大限度地提高成功传输的 XR 数据帧的数量。如下图所示: 当数据帧在允许的传输时间窗口内无法完整传输时,则认为数据帧传输失败。

因此,该任务的目标可以建模为: $$$$$$ \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< T B S_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_{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} $$$$$$ 这里,$$$b_{rnt}^{(k)}$$$ 是一个布尔变量,表示单元 $$$k$$$ 的第 $$$r$$$ 个 RBG 是否在 TTI 分配给用户 $$$n$$$ $$$t$$$ 和 $$$p_{rnt}^{(k)}$$$ 是一个非负连续变量,表示在 TTI $$$t$$$ 在小区 $$$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 \mathrm{log}_2 (1+s_{nt}^{(k)} ) $$$ 是著名的香农公式,代表传输数据量,其中 $$$s_{nt}^{(k)}$$$ 代表用户 $$$n$$$ 在小区中的传输 SINR(信号与干扰加噪声比) $$$k$$$ 在 TTI $$$t$$$ 处,$$$W=192$$$ 是一个 RBG 的可用频率响应元素的常数。 $$$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$$$ 在 TTI $$$t$$$ 的 RBG $$$r$$$ 上的初始 SINR,它指示信道的质量。另一个给定常数值$$$d^{(k)}_{mrn}$$$表示当用户$$$m$$$被调度到小区$$$k$$$时,RBG $$$r$$$上用户$$$m$$$和用户$$$n$$$之间的干扰因子。注意$$$d^{(k)}_{mrn}=d^{(k)}_{nrm}\le 0$$$,这表明在同一RBG-TTI资源上调度多个用户将导致每个用户的SINR下降。

综上所述,参与者需要找到有效的无线资源分配,以便更多的XR数据帧能够成功传输。

输入

单次测试的输入有 $$$(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 < s_{0, r n t}^{(k)} < 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 < 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$$$。

输出

某个输入的输出是 $$$p_{r n t}^{(k)}$$$ (float) 的优化结果,其中有 $$$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)}>0$$$并且$$$p_{r n t}^{(k)} = 0$$$意味着$$$b_{r n t}^{(k)}=1$$$并且分别为$$$b_{r n t}^{(k)} = 0$$$。

请注意,如果输出不满足约束(4),则将被判定为错误答案并获得得分$$$0$$$。此外,在某些时间窗外的TTI上传输是有效的,但通常会因资源浪费而导致分数较低。

示例

输入 #1

2
2
2
1
1.3865 11.3865
1.3865 11.3865
2.3865 2.3865
2.3865 2.3865
0 -2
-2 0
0 -2
-2 0
2
0 250 0 0 2
1 25 1 0 2

输出 #1

0.000000 0.004950
0.000000 0.004950
0.245039 0.000000
0.245039 0.000000

注意

评分:
目标是最大化成功调度的帧的数量。当这些数字相等时,我们将比较谁使用的电量更少。为了实现这一点,$$$Score = X - 10^{-6}\times p$$$,其中$$$X$$$和$$$p$$$分别表示成功调度的帧数和用于传输的总功率。

提交的总分是每次测试的分数总和。

本题准备了两组测试。在比赛期间,每份提交的作品都会经过初步测试。比赛结束后,对于每位参赛者:

评审团采用初步测试非零分的最新提交材料;

此提交内容在最终排名的最终测试集上进行了测试;

两组测试是基于真实数据从同一数据池生成的。