中文题目：缓存辅助无线网络中结合索引编码的下行PD-NOMA传输时延优化

论文题目：Delay Minimization for Downlink PD-NOMA Transmission with Index Coding in Cache-Aided Wireless Networks

录用期刊/会议：EAI CollaborateCom 2024 - 20th EAI International Conference on Collaborative Computing: Networking, Applications and Worksharing (CCF C)

作者列表：

1) 吴    凡 中国石油大学（北京）人工智能学院 博 21

2) 马建豪 中国石油大学（北京）人工智能学院 计算机科学与技术专业 硕 20

3) 吕振杰 中国石油大学（北京）人工智能学院 计算机科学与技术专业 硕 22

4) 徐朝农 中国石油大学（北京）人工智能学院 计算机系教师

文章简介:

PD-NOMA作为一种支持多用户接入并提升频谱效率的有效技术，已引起了广泛关注。同时，无线缓存作为一项新兴技术，能够显著减少网络流量。我们还受到结合索引编码的PD-NOMA技术的启发，旨在进一步降低传输时延。因此，本文研究了下行PD-NOMA传输中结合索引编码的时延最小化问题。为此，我们将索引编码与PD-NOMA的分组调度联合建模，提出了相应的数学模型。由于该问题属于复杂的混合整数规划问题，我们设计了一种两阶段的解决策略。在第一阶段，我们用无向图描述用户的需求与缓存关系，最少的传输数据包数量可以近似等价于该图的团覆盖数。通过贪心算法找到最大团覆盖，对每个团的需求包进行XOR操作，生成索引编码包。在第二阶段，我们采用启发式策略对待传输的数据包进行调度，贪心利用PD-NOMA的传输能力，从而实现时延的最小化。

本文的主要内容如下：

（1）我们通过联合考虑索引编码和PD-NOMA的分组问题来构建该问题的数学模型。

（2）提供了该问题为NP完全问题的证明。

（3）提出了一种基于需求-缓存图最大团覆盖的两阶段启发式算法。

摘要:

功率域非正交多址接入（PD-NOMA）与索引编码因其支持大规模移动连接和减少网络流量的能力，得到了广泛关注。本文研究了具有缓存功能的下行PD-NOMA无线网络，并探讨了如何通过索引编码来最小化下行传输中的PD-NOMA网络传输时延。考虑到用户缓存的内容，我们构建了一个联合索引编码与分组调度的优化问题，旨在充分利用PD-NOMA和内容缓存的特性来最小化时延。随后，我们的原始证明表明，下行PD-NOMA传输的时延最小化问题是NP完全的。为此，提出了一个两阶段的启发式算法来解决该问题。在第一阶段，构建图来描述用户的需求与缓存关系，最少数据包的数量可以通过该图的团覆盖数进行近似。此外，针对每个团，通过对团内需求包进行XOR操作，形成索引编码包。在第二阶段，采用启发式策略对索引编码包进行调度，贪心地利用PD-NOMA的下行传输能力。基于仿真结果的分析表明，与几种基线方案相比，所提出的方法在缓存辅助无线网络中有效减少了传输时延。

设计与实现:

1、问题建模

我们考虑一个由单基站（BS）和n个用户设备（UE）组成的单跳、单信道无线网络，用户设备分别为u1, u2, ..., un。基站和用户设备均配备单天线。基站可以访问一个包含q个文件的数据库。因而，问题可以建模为

2、算法设计

为了解决上面的问题，我们提出了一种两阶段策略，并分别为索引编码和PD-NOMA中的分组与功率分配问题设计了启发式策略。

第一阶段为基于团覆盖的编码策略。显然，编码包的数量对传输时延有很大影响。通常，数据包越多，时延越大，反之亦然。因此，我们首先考虑如何通过索引编码减少数据包的数量，同时确保所有文件请求在一个帧内得到满足。因而算法设计如图1所示。

 

图1 基于团覆盖的启发式解码策略

第二阶段为PD-NOMA中的分组与功率分配策略。当所有编码包生成后，基站将基于PD-NOMA对其进行调度并分配传输功率。即使在给定待传输的数据包的情况下，最小化传输时延仍可能是一个困难的问题。因此，我们提出了一种启发式算法，先对数据包进行分组，然后分配传输功率。

图2 用于编码包分组的贪心算法

实验结果及分析:

我们考虑一个下行PD-NOMA无线网络，该网络由一个基站（BS）和若干配备k-SIC接收器和缓存的用户设备（UE）组成。这些UE均匀分布在半径为500米的圆形小区内。每个UE随机请求并缓存一定数量的文件。假设所有UE请求的文件都未缓存，并且每个UE请求的文件数量服从参数为λ的泊松分布。相关实验结果如下图3，图4。

图3与baseline1相比，所提出的算法和baseline2分别将帧长度减少了14.19%和12.60%。

 

 图3 不同γ和k值下的帧长度

图4 传输时延性能与每个用户设备平均请求文件数量的关系（n = 40）

图4，图5分析了问题规模对系统帧长度的影响。所研究问题的规模取决于基站服务的请求文件数量。与baseline2相比，当问题规模较大时，所提出的算法表现出更好的性能。

当n = 10时，所提出的算法和baseline1相较于baseline2，分别将帧长度减少了5.03%和4.9%。当n = 70时，这一比例分别上升至17.19%和13.91%。

 

图5 传输时延性能与用户设备数量的关系

结论:

本文研究了下行PD-NOMA传输中结合索引编码的传输时延最小化问题。我们通过联合考虑索引编码和PD-NOMA的分组调度，对该问题进行了建模。此外，为了深入了解问题结构，我们证明了问题的NP完全性。随后，我们提出了一个两阶段的启发式算法来解决该问题。索引编码包通过基于最大团覆盖的编码策略生成，并通过PD-NOMA中的贪心编码包分组和功率分配进行调度。仿真结果表明，结合索引编码的PD-NOMA方案具有显著优势。我们相信，随着更多低成本大容量存储设备的广泛应用，该方案将在未来得到广泛使用。

作者简介:

徐朝农，中国石油大学（北京）人工智能学院教师，主要研究领域为边缘智能、嵌入式系统、无线网络。