骨干辅铺助PD-NOMA网络延时受限最小上行功率调度问题的复杂性

中文题目：骨干辅铺助PD-NOMA网络延时受限最小上行功率调度问题的复杂性

论文题目：Complexity of Minimum Uplink Power Scheduling with Delay Bound for Backbone-assisted PD-NOMA Wireless Networks

录用期刊/会议：Computer Networks（CCF B JCR Q1）

原文链接：https://www.sciencedirect.com/science/article/abs/pii/S1389128622002870

作者列表：

1) 吴凡     （中国石油大学（北京） 信息科学与工程学院 计算机科学与技术 博20）

2) 徐朝农  （中国石油大学（北京） 信息科学与工程学院 ）

3) 朱宇彤  （杭州高等技术研究院 ）

4) 李超     （中国科学院计算技术研究所）

文章简介:

5G网络的高功耗问题已经成为困扰产业界的难题。尽管功率域非正交多路复用接入（Power-Domain Non-Orthogonal Multiple Access: PD-NOMA）技术有很高的频谱利用率而成为5G mMTC场景下的候选接入标准，但它具有功耗高的致命缺点。因此，降低PD-NOMA网络的功耗是其能否得到规模化应用的关键。

本文研究了在给定最大传输延迟的约束下，如何降低在骨干辅助PD-NOMA网络架构下的上行传输总功耗的问题。首先，我们抽象出了骨干辅助PD-NOMA解码器的解码特性（见图1），基于此对骨干辅助PD-NOMA下的可解码序列进行了定义。

图1 骨干辅助PD-NOMA的解码特性

从而建立了对所研究问题的最优化模型描述，具体如下：

其中，为用户调度策略，为功率分配策略，求出最优的联合用户调度和功率分配策略是本文的核心。

与传统的基于最优化的求解方法不同，我们力图通过证明问题的复杂性来洞悉问题的本质。我们创造性地基于三角划分问题提出一个原创性的复杂性证据，从理论上证明了问题的复杂性是NPC的。事实上，该问题的复杂性证据问题是前人所遗留的一个开放难题，一直未得到解决。本文所提出的复杂性证据不仅适合于本文，而且将之前遗留的开放难题全部作为特例而纳入本文的复杂性理论框架，从理论上彻底解决了PD-NOMA的调度复杂性证明难题。

进一步的，针对在实际应用中最为常用的只有一个基站的特例，我们理论上证明了该问题为P问题，并提出了一个复杂度为O（nlogn）的简单最优算法，极大简化了算法的实现复杂度，为低复杂度的PD-NOMA调度需求奠定了坚实的理论基础。

更进一步的，针对骨干辅助PD-NOMA网络的通例，通过如下三个准则：优先组配信道增益差异性大的用户传输、总体被解码能力弱的用户安排到低解码相、按解码相顺序以功耗最小为基准贪心选择解码基站，我们提出了一个O（nlogn）的低复杂度的启发策略，并且证明了启发式算法在单基站场景下就是最优算法。

图2为延迟上限对功率消耗的影响的实验结果，从图中可见，对于启发式式算法，当延迟上限值比较小时，其对功率消耗有着指数级的影响，但随着延迟上限值的进一步放宽，功率消耗不再受到影响。这个结论为用户合理设置传输时延要求提供了科学的指导。

图2 延迟上限对功率消耗的影响

图3揭示了所提出的启发式算法的性能。我们比较了启发式算法（为多基站场景而设计，但应用到单基站场景下）和模拟退火算法（可认为是在骨干辅助多基站场景下的最优算法）的功耗性能。图例中的Algorithm 3为启发式算法，SA为模拟退火算法。可以看到，启发式算法的性能非常接近理论最优值。这个结论表明，我们的算法不仅通信功耗性能极佳，而且极大地降低了低功耗的骨干辅助PD-NOMA解码器的算力需求。

图3 启发式算法在单基站场景下的功耗性能实验

通讯作者简介:

徐朝农，副教授

1998年本科毕业于合肥工业大学计算机学院，2001年硕士毕业于合肥工业大学计算机学院，2001-2004年在合肥工业大学计算机学院任教，2007年博士毕业于中国科学院计算技术研究所，2007-2009年在清华大学智能技术与系统国家重点实验室从事博士后研究，2009年11月于中国石油大学（北京）计算机系任讲师，2012年4月任硕士生导师，2012年6月任副教授，2017年12月任博士生导师。研究方向为无线通信与网络、智慧物联网、嵌入式系统。2015-2016在美国佛罗里达大学（访问教授：Prof. Yuguang Fang）做访问学者。

联系方式：Email: xuchaonong@cup.edu.cn