A Distributed Decoding Algorithm for 6G Internet-of-Things Networks

1.   引言

经过多年的研究和发展，第5代无线通信(5G)已经在全球范围内进行了标准化和商用^[1]。面向未来，第6代无线通信(6G)将会在5G的基础上，实现更低延时、更高速率、更大规模和更广的覆盖范围，以满足更丰富的应用需求。在未来移动通信的众多场景中，物联网(Internet-of-Things, IoT)是最为核心的一项应用^[2]。在6G IoT网络中，用户不仅仅局限于人，同样也包括了网络中的多种设备，它们同样可以通过网络传输数据而无需人-人或人-机交互。随着用户计算能力的提高和无线传感器技术的发展，物联网将广泛地应用于消费、商业、工业和基础设施等领域^[3,4]。

在IoT网络中，用户利用先进的无线传感器获取环境的某些信息，并通过网络无处不在地共享这些信息，从而根据环境变化做出相应的决策。例如，在智慧家庭中(smart home), IoT设备通过对多种信号进行检测来识别出环境中人的状态，从而为残障人士和老年人提供帮助；在未来交通系统包括交通管理、道路安全检测等应用中，IoT网络可以对车辆的位置和状态进行实时监测，从而在出现问题时及时发送预警^[5,6]。在这些IoT应用中，高精度的信息检测算法是保证网络有效传输信息的关键。鉴于此，本文将对IoT网络中的检测与译码问题进行研究。

不失一般性地，考虑在典型IoT应用场景中有一个移动的无线接入点(Access Point, AP)向各个用户广播消息。各个用户收到消息后，需要对消息进行译码并做出响应。针对这一场景，传统的传输机制通常假设网络中存在一中心处理单元，各用户将收到的消息通过上行链路发送给中心单元后由中心单元完成译码。之后中心处理单元再通过下行链路将译得的信息发送给各用户，从而用户可以根据译码得到的信息完成不同的应用。然而这样的处理方式并不适用于6G的IoT网络中。需要强调的是，在6G中的IoT网络中，通过无线连接的用户数量将是巨大的^[7]。在这样的大规模网络中，在中心单元执行译码往往需要很大的开销。举例来讲，如果一个用户距离中心单元很远时，要保证中心单元对信息的可靠接收往往需要用很高的发射功率，这将会在实际应用中为网络带来很大的负担。区别于传统的传输机制，一些改进的传输机制通过将部分用户作为中继节点，使得远处的用户依靠路由(routing)与中心单元进行通信。这种基于中继的传输机制可以有效地减少信息传输的功率开销。然而，由于网络的动态特性，用作中继节点的用户需要频繁地根据网络需要进行改变，从而实现复杂的网络调度。复杂的网络调度又势必增加网络的通信开销，并引入较高的传输时延。除此之外，当中心单元未能按预期工作时，整个IoT网络很有可能会发生故障，并导致严重的性能损失，甚至会危害安全性。为了解决这个问题，国内外学者提出了直接根据每个用户收到的消息进行译码的传输机制^[8,9]。然而，由于消息传输受信道衰落和噪声影响，译码的准确性往往无法保证。这促使我们设计一种新的具有良好可扩展性和高鲁棒性的IoT网络译码方法。

本文基于文献[10]中提出的共识算法，提出了一种应用于功率受限的6G IoT网络中的分布式译码算法。共识算法起源于自动化理论和分布式计算领域^[11]，其在多智能体网络中的应用吸引了众多兴趣。共识方法通过在网络用户之间共享信息并迭代更新用户的“本地”度量从而使用户之间达成共识。其优点在于它可以有效避免每个网络中用户由于消息更新导致信息的重复计算，并且可以保证每个用户获得与中心单元相同的信息量。本文首先给出了系统模型，并根据系统模型设计了相应的中心化译码算法，作为后续分布式算法设计的基础。其次，通过对似然函数的分解和运算，介绍了一种现有的基于对数似然比共识的分布式译码算法^[12]。通过该算法，IoT网络中的每个用户均可以得到基于全部观测的信息，因此其译码性能可以达到中心化处理算法的性能。然而，该算法要求每个用户均完美获得网络的拓扑结构。但在实际IoT网络中，由于用户具有高动态特性，网络拓扑结构实时变化，很难满足上述假设。因此，受到图模型译码算法启发，本文设计了一种基于“外”信息的分布式译码方法，本方法可以有效克服网络拓扑结构未知的问题。最后，考虑实际IoT网络中的量化问题，对所提算法进行了改进，使其可以应用于实际系统中。

2.   系统模型

本文考虑一个一般化的IoT网络，其中有$K$个用户在网络中随机分布，每个用户均配置了适当的传感器可以接收AP广播的消息并进行简单的信号处理。由于AP的移动和噪声干扰导致接收信噪比(Signal-to-Noise Ratio, SNR)低，每个用户仅依靠单独的观测对AP广播的消息进行译码会导致较大的误差。假设在某一时刻，AP向网络广播了一则消息${x}$。不失一般性地，假设AP发出的消息可以表示为一个$J$维二进制矢量，即${x_i} \in \{ 0,1\} ,1 \le i \le J$。为便于算法推导，假设AP和用户的通信信道是无记忆的加性噪声信道，并且不同用户与AP之间的信道是独立的。则对于第$k$个用户，有

其中，${{z}_k}$为双边功率谱密度为${{V}_{{{z}_k}}}$的加性噪声。假设网络中存在一中心单元可以收集并整合所有用户接受到的消息，即${y} = {\left[ {{{y}_1},{{y}_2},\cdots,{{y}_K}} \right]^{\rm{T}}}$，则上述网络译码问题等效于最大似然估计，表示为

其中，$\Pr ({y}\left| {{x_i}} \right.)$表示联合似然函数，${\cal A}$为对应的取值集合。对中心式的处理算法而言，对广播消息${x}$的估计等效于对${x}$中各个元素进行判决。具体来说，判断第$i$个元素${x_i} = 0$或${x_i} = 1$可以通过式(3)关于${x_i}$的对数似然比(Log-Likelihood Ratio, LLR)得到

若${\gamma _i} < 0$，则判定${x_i}$是0，反之，则判定广播消息中${x_i} = 1$。另外，求取边缘似然函数$\Pr \left( {{{y}}\left| {{x_i}} \right.} \right)$可以通过许多现有算法，例如BCJR算法、消息传递算法等，在此不再赘述。在完成译码后，中心处理单元将译码结果反馈至各个用户。然而，当中心单元无法正常工作时，各个用户仅能依靠各自接收的消息进行译码，由此产生很大的译码误差，从而对整个IoT网络的正常工作构成巨大挑战。因此，本文将提出一种分布式的网络译码算法，该算法可以在中心单元失效时解决网络译码问题。

3.   分布式网络译码

分布式处理依赖于用户各自的本地处理和用户间的信息传递。利用适当的通信技术，在一定距离内的两个用户可以进行信息交换。一般而言，可以用一个如图1所示的“网络拓扑图”(network topology graph)来描述某一时刻IoT网络的通信链路。在图1中，每一个节点表示网络中的一个用户，当且仅当两个用户可以通信时，他们之间存在一条相互连接的边。为方便下文表述，在此定义可以与第$k$个节点通信的用户为第$k$个节点的邻居用户，则用${{\cal S}_k}$来表示第$k$个用户的所有邻居用户的集合。当所有用户的邻居用户集合${{\cal S}_k}$, $1 \le k \le K$均不为空时，则称“网络拓扑图”为连通的(connected)。

图  1  IoT网络拓扑结构

下载: 全尺寸图片 幻灯片

在某一时刻，当用户$k$收到来自AP广播并经过信道的消息${{y}_k}$后，可以得到“本地”(local)的似然函数$\Pr ({{y}_k}\left| {{x_i}} \right.)$；相应地，称由包含所有用户收到消息${y} = {\left[ {{{y}_1},{{y}_2},\cdots,{{y}_K}} \right]^{\rm{T}}}$得到的似然函数$\Pr ({y}\left| {x} \right.)$为“全局”(global)似然函数。考虑到各个用户收到的消息相互独立，“全局”似然函数$\Pr ({y}\left| {x} \right.)$可以因式分解为

进一步地，考虑到噪声的分布特性，$\Pr ({y}\left| {x} \right.)$可以进一步写为

根据式(7)，本文将$L({{y}_k},{{x}})$称为“本地”度量，用来表征第$k$个用户根据本地观测得到的度量值。进一步地，定义“全局”度量为

分布式协作译码问题本质上是要设计网络中的信息交换机制，使得每个用户都可以获得“全局”度量。关于这一问题最直接的思路是将每个用户得到“本地”度量发送给其他用户，但这一机制往往带来巨大的通信开销，可扩展性较差，特别当两个用户无法直接通信并需要通过其他用户进行中继的时候。因此，本文将采用共识算法，通过用户本地计算以及在邻居用户间建立通信链路，使得各个用户均可以获得“全局”度量$L\left( {{y},{x}} \right)$。此外由于共识算法仅依赖于邻居间的信息传输，其通信开销大大降低，可扩展性较强。图2给出了基于共识机制和基于非共识机制的分布式算法通信开销随用户数目的增长。在非共识算法中，每一个用户均需要与别的用户进行通信，其通信开销可以写为${\cal O}({N^2})$。对基于共识机制的分布式算法，其通信开销可以表示为${\cal O}({S_{{\rm{max}}}}N)$，其中${S_{{\rm{max}}}}$表示网络中所有用户具有的最大邻居个数。由图2可以看出，基于共识机制的分布式算法通信开销随用户数的增长速度远小于基于非共识机制的分布式算法。

图  2  基于共识机制和非共识机制的通信开销比较

下载: 全尺寸图片 幻灯片

3.1   传统共识算法

共识算法是一种并行处理算法，每个用户基于从邻居用户收到的信息迭代更新其“本地”度量。在第1次迭代时，第$k$个用户的“本地”度量初始化为${L_k}(0) = L({{y}_k},{{x}})$。则在第$n$次迭代时，其“本地”度量的更新可以表示为

其中，${L_k}(n - 1)$是第$k$个用户在第$n - 1$次迭代时求得的度量，$\xi $为更新的权重，$\left| {{{\cal S}_k}} \right|$为第$k$个用户的邻居个数。式(9)中的更新可以看作每个用户将其自己的信息与来自其他用户的信息进行融合的过程。文献[11]中研究了更新权重$\xi $的选择。一般来说，令更新权重等于拓扑图中用户最大邻居数分之一可以达到很好的性能。文献[13]证明了如果一个“网络拓扑图”是连通的，则当迭代次数$n$趋近于无穷时，“本地”度量一定收敛于“全局”度量的$K$分之一，即

在实际应用中，数次迭代往往已经可以保证足够的近似精度。在各个用户均得到“本地”度量${L_k}\left( n \right)$后，可以计算出“全局”度量$L\left( {{y},{x}} \right)$，从而可以在各个用户处计算出“全局”似然函数$\Pr ({y}\left| {x} \right.)$并进行译码。由“本地”度量的表达式可以看出，每个用户共享相同的待估计量${x}$。因此在迭代更新“本地”度量时，仅需要交换加性噪声的统计特性${{V}_{{{z}_k}}}$。然而，当噪声的统计特性比较复杂，例如噪声的统计特性随时间变化时，直接传递统计特性的能效性很低。因此接下来我们提出一种基于对数似然比更新的算法。

3.2   基于对数似然比的改进共识算法^[12]

由式(3)和式(7)可以看出，由于不同用户处得到的观测${{y}_k}$相互独立，“全局”似然函数$\Pr ({y}\left| {x} \right.)$也可以因式分解为$\Pr ({y}\left| {x} \right.) = \displaystyle\prod\nolimits_{k = 1}^K {\Pr ({{y}_k}\left| {x} \right.)}$。从而式(3)可以改写为

其中，$y_i^{(k)}$表示${{{y}}_k}$中的第$i$个元素。显然，与前述对“本地”和“全局”度量的定义相似，可以定义${\gamma _i}$为第$i$个符号的“全局”对数似然比，而$\gamma _i^{\left( k \right)}$为第$i$个符号的“本地”对数似然比，从而有${\gamma _i}{\rm{ = }}\displaystyle\sum\nolimits_{k = 1}^K {\gamma _i^{\left( k \right)}} $。在文献[12]提出了一种通过对在用户间传递“本地”对数似然比以达成共识的分布式译码算法。根据式(9)，用户$k$的“本地”对数似然比在第$n$次迭代时的更新可以表示为

其中，${\xi ^{(k,l)}}$表示第$k$个用户对来自第$l$个用户的“本地”对数似然比的权值。在此，可以看出虽然式(12)中给出的更新式可以有效地在各个用户获得“全局”对数似然比，但其权值的大小往往对整个网络的收敛性至关重要。理论上其权值的设置需要获悉整个网络拓扑结构和每个用户的邻居个数。然而，在面向6G的IoT网络中，网络的拓扑结构随着时间有着较快的变化，而且由于低传输延时的限制，每个网络用户往往难以获取整个网络的拓扑结构以及相邻的邻居个数。因此，文献[12]中提出的现有分布式译码算法并不适用于面向6G的高动态、低延时IoT网络。

3.3   基于和积算法的改进共识算法

接下来本文提出一种基于和积算法(Sum-Product Algorithm, SPA)的共识算法^[14]。回顾传统基于图模型的低密度奇偶校验(Low-Density Parity-Check, LDPC)码的译码算法^[15]，变量节点将“外”(extrinsic)信息发送到校验节点以更新相应的信息^[7]。上述过程类似于本文所考虑的网络译码问题。因此，本文拟将和积算法进行推广来解决网络译码问题。

具体来讲，将每个用户抽象为一种特殊类型的网络节点，该节点接收来自邻居用户发送的“外”信息并对自己的“本地”信息进行更新，并通过更新后的“本地”信息获得相应的“外”信息，并将得到的“外”信息送还给所有邻居用户，其具体结构如图3所示。

图  3  基于图模型的分布式译码算法

下载: 全尺寸图片 幻灯片

利用“外”信息更新规则，用户$k$在第$n$次迭代时对第$i$个元素的“本地”信息的更新可以表示为

其中，定义$\gamma _i^{\left( {k \to k} \right)}$为“内”(intrinsic)信息，表征用户$k$仅从本身观测获得的信息，定义$\gamma _i^{\left( {l \to k} \right)}\left( {n - 1} \right)$为在第$n - 1$次迭代时用户$l$传给用户$k$的“外”信息。同时，“外”信息的更新可以表示为

需要注意的是，“内”信息是完全基于本地观测得到的信息，在迭代过程中保持不变。但是，“外”信息在每次迭代中都会根据来自相邻用户的信息进行更新。经过数次迭代后，各用户即可达成共识，这与基于和积算法的常规译码算法相似。通过多次迭代，每个用户的“本地”信息将收敛到“全局”信息，从而使得各个用户都可以译出从AP发出的消息。将式(12)与式(14)相比较可知，基于和积算法的共识算法不需要掌握网络的动态结构，所有用户可以直接广播其信息，并根据收到的信息更新其“本地”信息。

为了控制用户间交互的信息量，可以通过数据压缩、高阶调制或者仅传递部分信息等方法来实现。然而，目前学术界对网络用户之间信息量的分析还没有确切结论，有待于进一步研究。

4.   仿真结果

本文考虑一个具有$K = 64$个用户的IoT网络，其中所有用户随机分布在面积为100×100 m²的2维平面内。任意两个用户的通信距离设为75 m，即当两个用户的距离小于等于75 m时可以通信。对于AP广播至用户的消息${x}$，本文假设其为二进制相位键控(Binary Phase Shift Keying, BPSK)信号，长度为$J = 100$。假设AP到用户的信道为独立的加性高斯白噪声(Additive White Gaussian Noise, AWGN)信道，其中白噪声功率谱密度为${N_0}$。为了更好地验证本文提出的算法的优势，对于中心式处理方法，假设从用户传至用户的通信链路是无噪的。另外，考虑将提出的基于和积算法的改进共识算法作为分布式处理方法。为了更好地模拟实际网络场景，考虑将网络节点之间的消息传输方式分为无损消息传递以及有损消息传递两种情况。对于无损消息传递，本文假设邻居用户可以完全准确地获取当前用户的“外”信息；对于有损消息传递，假设当前用户的“外”信息经过了$Q$ bit 进行量化处理、BPSK调制后经由AWGN信道传输至邻居用户。

图4中给出了不同迭代次数时6G IoT网络分布式译码算法的平均误码率(Bit-Error-Rate, BER)性能随AP-用户链路信噪比变化的曲线。在此，考虑无损消息传递，即用户间的通信链路假设为无噪。作为性能下界，采用中心化处理的集中式译码算法性能也被绘出。其中，仅有1次迭代时的分布式译码算法性能等效于各个用户依靠自己收到信号进行译码的结果。可以看出，此时各个用户无法译码出来自AP广播的消息，性能损失很大，造成IoT网络功能失效。但是，在3次迭代后，分布式译码算法的性能已经接近于性能下界。进一步增加迭代次数已无法带来明显的性能提升。

图  4  用户间无损消息传递时的分布式算法性能

下载: 全尺寸图片 幻灯片

图5中绘出了6G IoT网络中，用户之间有损消息传递时的平均误码率性能。不失一般性地，将AP-用户链路的信噪比设为10 dB，用户的“外”信息采用了Q=4 bit量化处理。为了表征用户之间通信链路的状态，定义用户之间信道的信噪比为${{E_{\rm{b}}}}/{N_0} = {{Q{E_{\rm{s}}}}/{{N_0}}}$，表征每一个LLR采用了$Q$ bit进行传输，其中${N_0}$为白噪声的功率谱密度，${E_{\rm{s}}}$为平均符号能量。 考虑用户间信息传输信噪比为0 dB, 5 dB, 10 dB和15 dB。同时，将中心化处理的集中式译码算法的对应结果作为性能下界。从图4可以看出，随信噪比增大，分布式译码算法的性能得到明显改善。此外，随迭代次数增加，分布式译码算法性能明显提升。在用户-用户链路信噪比为10 dB时，采用3, 4, 5次迭代的分布式译码算法性能与性能下界已经十分接近，验证了所提分布式译码算法在实际IoT网络中的有效性。

图  5  用户间有损消息传递时的分布式算法性能

下载: 全尺寸图片 幻灯片

5.   结论

在面向6G的物联网中，用户需要在链路中断(link failure)和中心单元无法正常工作的情况下有效处理信息并作出决策。本文针对以上问题，提出了一种分布式的译码算法。通过用户间的通信和“本地”信息处理，用户可以不依赖于中心单元完成译码。与中心式处理算法相比，分布式算法具有更好的可扩展性和鲁棒性。仿真结果表明，采用分布式译码算法可以获得与中心式算法几乎相同的译码性能，显示了所提算法在面向6G物联网应用中的巨大潜力。