实时工业物联网的功率域非正交多址接入基站选址算法

孙 源，沈文建，倪朋勃，毛 敏，谢雅琪，徐朝农*

（1.中法渤海地质服务有限公司，天津 300450；2.中国石油大学（北京）信息科学与工程学院，北京 102249）

0 引言

在以油田为代表的大型工业生产现场，为了保证生产的安全顺利进行，常常需要在现场安装各种监控传感器。这些传感器监测生产数据，并实时传输给数据收集基站。通过对这些数据的处理，基站可以对危险情况加以判断并实时处理，以确保生产的安全顺利。

随着技术的不断进步，传感器的数目越来越多，密度越来越大，出现了所谓的超密超可靠低延迟通信（massive Ultra-Reliable Low-Latency Communication，mURLLC）场景［1-3］。在这种场景下，数据传输拥挤现象越来越明显，实时性能越来越难以保证。

在工业物联网（Internet of Thing，IoT）场景下，无线网络部分基本都为单跳网络，此时网络传输延迟基本为接入延迟，因此，对实时性能的优化基本都聚焦在接入延迟上。多用户复用技术可用于降低接入延迟，提高网络实时性［4-5］。除了传统的频分多路（Frequency Division Multiple Access，FDMA）、时分多路（Time Division Multiple Access，TDMA）、码分多路（Code Division Multiple Access，CDMA）、正交频分多路（Orthogonal Frequency Division Multiple Access，OFDMA）之外，基于串行干扰消除（Successive Interference Cancellation，SIC）技术［6-8］的功率域非正交多址接入（Power Domain NonOrthogonal Multiple Access，PD-NOMA）技术可以依赖接收功率的差异实现多用户复用。考虑到当前mURLLC场景下的实际需求，目前第三代合作伙伴计划（3rd Generation Partnership Project，3GPP）将其列为在物联网场景下的待选接入标准，因此研究在PD-NOMA 技术下如何降低接入延迟显然具有现实意义。大多数研究利用功率控制和用户调度来实现低延迟［9］。例如，文献［10］中通过联合优化用户调度和功率分配来解决基于k-SIC 的无线网络的最小平均接入延迟问题，提出了启发式算法，并证明其在2-SIC 和单位流量负载的情况下是最优的。文献［11］中将延迟最小化问题表述为混合整数非凸规划问题，该问题已被证明是NP-Hard。文献［12］中针对多载波场景，研究了上行PD-NOMA 下最大完成时间的最小化问题，证明该问题也是NP-Hard，并提出基于最短处理时间的启发式调度算法。除了调度式方法外，基于压缩感知的随机接入策略也可以达到降低接入延迟的目的［13］，但这种方法只适合于接入密度不大的场合。

传统的使用PD-NOMA 技术来降低接入延迟的方法基本都基于功率调节来实现。然而在工业物联网场景，尤其是一些电能获取困难的场景下，传感器端对功耗极为敏感，一般都存在发射功率受限的问题。这些低功耗的传感器端的发射功率往往是不可调节的，因此传统的PD-NOMA 调度方法并不适用这些场合。如何在严苛限制下实现接入延迟优化成为研究关键。事实上，对于PD-NOMA 技术而言，接收功率是决定能否实现多用户复用的关键因素：当多个传感器发射的信号在基站处的接收功率满足一定差异性条件时可以实现并行接入，有利于降低接入延迟，而且传输复用越多，平均接入延迟越小。因此，通过调节数据收集基站与各个待接入无线传感器的相对距离，也可以实现对接入延迟的优化。由于传感器的位置一般来说是固定的，因此对数据收集基站的合理选址就成为优化接入延迟的必然选择。本文针对工业物联网中接入延迟较大的问题，提出一种实时工业物联网的功率域非正交多址接入基站选址算法，该算法在工业场景下极具应用潜力。

需要注意的是，对于典型的工业物联网系统来说，系统级的延迟性能实际是接入延迟、基站转发延迟以及应用处理延迟等的总和，低的接入延迟是整个系统达到低延迟的基础，因而本文只关注接入延迟。

1 网络模型与问题描述

1.1 网络模型

如图1 所示，在工作区域内有n个单天线无线传感器用户S1，S2，…，Sn，每个传感器的发送功率均为P且保持不变。这n个传感器都有数据需要上传，它们的位置已知且固定。以工作区域中心为原点建立极坐标系，对于传感器Si，用二元组（xi，yi）来表示其位置；对于基站，则用（X，Y）来表示其位置；di表示基站到传感器Si的距离，则

根据工业防爆的要求，例如基站之类的大功率设备只能安装在离工作现场一定距离之外，本文限定基站只能安装在指定的工作区域D，如图1 所示。

图1 问题模型Fig.1 Model of problem

无线信号经过空间传输必定会发生衰减，本文用Gi表示用户的信道增益。对于工业场景，由于无线传感器和基站一般不存在移动性，因此可以认为信号衰减只与距离有关，对于无线传感器Si，当其距离基站的距离为di时，其信道增益为Gi=，接收功率rpi=pGi。其中：α代表信道衰减因子，其典型值区间为［2，4］；rpi代表基站处接收到的Si的信号功率。

由于工作在同频同时，功率域非正交多址接入会引入用户间的大的干扰，一般并不适合很大程度的用户复用；因此，本文考虑迭代式SIC 接收机［14］，即基站最多同时可解的用户无上限。在基站端，若用户想要被成功解码，则必须满足：

其中：I为其他用户对Si的干扰；n0代表高斯白噪声；γ为接收机的接收信噪比阈值，常见值在2 dB 以上，对确知的解码方式，其值是已知的。

在长期演进（Long Term Evolution，LTE）中，用户终端（User Equipment，UE）通过物理上行控制信道上报自己的数据传输请求，然后由基站根据传输请求决定调度策略，并在物理上行共享信道中进行上行数据传输。与LTE 一致，假设一个时帧由多个时槽组成。根据工业物联网的特点，为了保证传输公平性，每个无线传感器将在一个时帧内仅被调用一次，这样接入延迟就是时帧长度。可以明确的是：在最差的情况下，即每个时槽只被一个用户独占，也就是一个时帧最长不会超过n个时槽。

1.2 问题描述

基于1.1 节的网络模型，本文的目的为最小化平均接入延迟，采用的基本手段是通过利用PD-NOMA 的并行接入能力，让更多的无线传感器并行传输。具体的手段为联合数据收集基站的位置设置（X，Y）和传感器传输时刻配置｛Nij｝。

其中：式（4）中的Nij是调度决策，用于保证一个无线传感器在一帧里只能传输一次，Nij=1 表示无线传感器Si在时槽j时被调度传输；式（5）～（6）用于保证用户可以被SIC 接收机基站解码；式（7）为信道增益模型；式（8）则确保基站处于安全的安装位置。优化目标为最小化对应策略的帧长。显然，上述优化式的控制变量为基站的位置和调度决策。

2 问题求解

根据1.2 节，该问题是一个组合优化问题，因此寻找低复杂度的算法相对困难，需要设计启发式的搜索算法。有序合理的搜索会在很大程度上降低实际的复杂度，这就需要寻找一个合理的启发式策略［14］。本文的思路是：在可行区域内，选择出有限个相较于其他区域可支持更多的用户复用的候选区域；然后对每个候选区域，给出其最佳传输调度策略；最后通过简单比较得出帧长最短的调度策略所对应的候选区域，即为最佳基站位置。

2.1 基站候选区域寻找

根据文献［10，15］，上述问题很可能是一个NP 完全问题［14］，难以找到最优解；而其主要难点在于式（5），式（5）中的n0造成并行用户的接收功率不能成比例，会给后面的解析推导带来困难，这也是在定理1 中提出缩放的根本原因。为了能够快速求出一个近似解，本文并没有采用如文献［16］的搜索算法，而是按照定理1 中的条件对约束式（2）进行了适度的收紧。需要注意的是，这种收紧并不能保证得到最优解，而可能得到次优解；因此这个低复杂度的解法本质上是一个启发式算法［15］。在仿真实验结果可以看到，这种稍微的约束收紧对算法性能影响极其有限。

然后，对任意一个无线传感器有序对，现在求其基站可解码区域。显然，如果有n个无线传感器，最多可以找到n(n-1)个基站可解码区域，这些基站可解码区域都是圆形。由于凸集间的交集仍是凸集，因此多个基站可解码区域相交形成的区域必定为凸区域，且凸区域最多不会超过n(n-1)个。相较于其他区域，基站位于这些区域时将会支持更多的传输复用（这些区域被称为基站候选区域），这就为下一步的实时调度策略留下了更大的优化空间。如图2 所示，该网络包含了3 个无线传感器S1、S2、S3和1 个NOMA 数据收集基站，通过画出6 个有序的节点对对应形成的基站可解码区域为（图2 中的白色区域）；求取这些区域的最小相交凸区域，从而得到了2 个基站候选区域 ：和（图2 中的深色区域）。

图2 基站可解码区域与基站候选区域示例Fig.2 Example of decodable area and candidate area of sink

2.2 寻找单个基站候选区域下的最短帧长

对于每个基站候选区域，为了使当把数据收集基站放在该区域时的帧长最短，可采用具体方法如下：对于每一个候选区域，建立一个生成图G=，它是一个顶点集为V={S1，S2，…，Sn}的有向无环图，其中n为无线传感器的个数。对于图中任意两个节点Si、Sk，若基站处于该候选区域内时对Si的接收功率rpi和对Sk的接收功率rpk满足rpirpk≥1+γ，则E中对应有一条由Si到Sk的有向边。进而，寻找最短帧长问题就等价于生成图的最小链划分问题。定理2 说明了它们之间的等价性。

定理2生成图上的每条有向链对应着一组可解码序列。

证明 由定理1 可知，若一组无线传感器的接收功率rp1，rp2，…，rpm满足rpirpi+1≥1+γ（i=1，2，…，m-1），此时所有传感器可在基站端同时解码。由生成图的构造过程可知，生成图中的每一条有向边（如SiSk），当基站处于候选区域内时都会满足rpirpk≥1+γ。因此对于生成图的任意一条有向链来说，由于传递性的原因，其上的所有无线传感器节点在基站处的接收功率一定满足定理1 的条件。从而，它们形成了一条可解码序列。证毕。

图3 生成图的有向链与可解码序列的对应Fig.3 Correspondence between directed chain of generation graph and decodable sequence

鉴于一条可解码序列将占用一个时槽，为了得到在确定基站位置下的最短调度，显然要寻找生成图的最小链划分。最短帧长则为最小链划分数。

定义1有向图的最小链划分。在有向无环图G中，选择若干条无公共点的有向链，使得这些链覆盖所有节点，且链的条数最小。

对于给定的有向图来说，最小链划分问题可通过Dilworth 定理求解，该算法的复杂度为O(|V||E|)。图4 给出了一个生成图的最小链划分，以及该链划分对应的调度策略。

图4 中，对于给定的有向无环图，通过Dilworth 定理找到其最小链划分：S1-S3-S6-S8、S4-S6-S9、S2-S5-S10，从而表示S1、S3、S6、S8可安排在同一个时槽发送，S4、S7、S9可安排在同一个时槽发送，S2、S5、S10可安排在同一个时槽发送，因此最小帧长为3。

图4 最小链划分及其对应的调度策略Fig.4 Minimum chain partitioning and corresponding scheduling strategy

2.3 算法描述

在2.2 节，当基站处于某个候选区域时，可以寻找到此情况下的最短调度策略。本节中，对于所有的候选区域的最短调度策略，通过直接比较它们的最短调度策略的帧长并选取帧长最小的调度策略就是最优的调度策略，其对应的基站候选区域即为最优基站位置。问题求解算法可描述如下。

对上述算法做简要描述：在初始化以后，算法2）～4）行求出所有的基站可解码区域；第5）行由基站可解码区域集得到基站候选区域集；第6）～7）行为每个基站候选区域建立生成图，并基于二部图匹配算法求出在该基站候选区域下的最优调度策略；第8）行在上述所有的生成策略中选择帧长最短的调度策略，该策略对应的基站候选区域则为基站的最优位置。

对每个候选位置计算调度策略的时间复杂度是O（nE），其中E为生成图的边数，由于候选位置个数不超过n(n-1)个，所以算法的复杂度为O（n3E）。

需要说明的是，如果基站可解码区域集为空，则表示传感器之间无法利用PD-NOMA。此时，基站只要能保证和每个传感器能通信即可，此时实时性最强的传输方案就是TDMA。

3 实验与结果分析

在100 m × 100 m 的正方形工作区域内随机放置一定数量（10 到30 不等，具体数量根据实验设置）的无线传感器节点，传感器的发送功率设为2 dBm，通信带宽为180 kHz。接收机噪声为加性高斯白噪声，其功率谱密度为-169 dBm/Hz，因此噪声的平均功率为-117 dBm，不再考虑其他干扰源。接收机解码阈值范围设为［3，6］ dB。信道衰减因子为［2，4］。基站允许的建造区域是一个400 m × 400 m 的正方形区域，其中心点与工作区域的中心点重合。每次实验重复算法100 次。

实验1 研究平均帧长度和信道衰减因子、解码阈值的关系。实验1 的结果见图5，可以看出平均帧长度随着信道衰减因子的增加而呈近似线性的减小。这是因为功信道衰减因子增加时，接收到的用户之间的功率差也会增大；因此两个用户的可解码区域面积增加，圆形区域之间交叉的可能性也增加，从而导致生成图中出现更多的边，使得帧长减小。

图5 平均帧长度和衰减因子与解码阈值的关系Fig.5 Relationship between average frame length，decay factor and decoding threshold

实验2 研究平均帧长度和传感器数目（用户数）的关系。图6 比较了不同用户数下的算法性能。参数设置如下：传感器数目为［10，30］，功率衰减因子为2，所有用户随机分布。事实上，实验所得到的最短帧长度与用户数的比值基本上是固定的，换句话说，每个用户的延迟基本上不受用户数的影响。这可以从一定程度上说明调度策略已经非常接近最优，没有进一步优化的空间了。从图6 也可以看出平均帧长度随着解码阈值的增加而呈近似线性的减小，其原因与实验1 是类似的。

图6 平均帧长度与传感器数量的关系Fig.6 Relationship between average frame length and number of sensors

实验3 研究平均帧长度和拓扑方式的关系。实验3 进一步探讨了传感器的位置分布对帧长度的影响，实验结果见图7。除了随机布设之外，本文还设计了几种不同的传感器位置分布。图例中的n是用户数，3×10 表示用户按等间隔排列为3 行和10 列，以此类推。显然，不同的传感器布设方式对于平均帧长度是有影响的；并且当用户以等间隔的线性排列时，最小帧长度比在随机布设的情况下短；此外，在该等间隔线性排列下，基站的最优位置是在线性排列的两端附近。造成此现象的原因是：当基站处于线性排列的两端时，基站接收到的无线传感器的接收功率与其他拓扑相比差异更为显著，传感器传输之间的组合灵活性大幅增加。因此本文算法可以更灵活地组合不同的传输，从而带来更低的延迟性能。

图7 平均帧长度和传感器布设方式的关系Fig.7 Relationship between average frame length and layout of sensors

以随机拓扑为代表，由图7 可知，当解码阈值为2，n为30 时，最少需要11 个时槽（因为高斯白噪声的方差是随机的，因此会出现不为整数的情况），也就是说，接入延迟降低为TDMA 时的36.7%；n为20 时，最少需要7 个时槽，接入延迟降低为TDMA 时的35%，接入延迟性能显著提升。

4 结语

PD-NOMA 技术支持多路并行接入，因此对于工业物联网应用的延迟性能有重大影响，可能会成为未来工业物联网的物理层标准。在此技术平台下，针对接入延迟最小化进行了研究，提出了基于基站选址方法来降低接入延迟。该方法能够应用在很多实际场合，具有现实的意义。随着未来第五代移动通信技术（5th Generation mobile communication technology，5G）R17 标准的不断发展和mURLLC 应用场景的不断发掘，对于低延迟的需求以及相应的技术和算法必将越来越迫切，必将是未来的研究重点之一。