基于信息年龄优化的多信道无线网络调度方法

王 恒 段思勰 谢 鑫②

①(重庆邮电大学工业物联网与网络化控制教育部重点实验室 重庆 400065)

②(重庆邮电大学通信与信息工程学院 重庆 400065)

1 引言

随着无线网络技术的发展，数据交付的及时性对一些实时性要求较高的应用显得尤为重要。例如，在自动驾驶场景中，及时地传输汽车的速度、位置信息对汽车行驶的安全问题十分关键[1]；化工生产场景中，实时的现场数据是安全生产的基本保障；环境监控场景中，环境温度、语音视频等一些数据交付的及时性直接影响用户是否能及时做出正确的决策[2]。因此，如何提高时间敏感类应用中数据交付的及时性，成为无线网络研究所面临的重要挑战。

信息年龄(Age of Information, AoI)是新近提出的一种评价数据及时性的度量标准，用以从目标节点的角度衡量数据的新鲜程度，表示为目标节点最新接收到的数据包自其生成以来所经过的时间[3]。相较于传统的衡量数据及时性度量标准，AoI的刻画更加全面。例如，时延是从数据包本身的角度出发，度量数据包从网络中一端发送到另一端的过程中经历的时间。而AoI的度量则除了数据包的时延部分，还包括了数据包在数据源由于没有及时被调度，以及在目标节点没有进行更新而带来的停留时间。因此，AoI的大小刻画了目标节点最近接收到的数据包的新鲜程度，通过对网络中的AoI进行优化，能够更好地满足网络对数据交付及时性的要求。

近年来，众多学者以AoI为优化目标，从不同队列模型、数据更新方式、链路调度等角度展开相关研究[3-10]。尤其是在多用户无线网络场景中，最小化平均AoI的链路调度问题受到了重点关注，主要集中于单信道无线网络系统进行研究[7-10]。而在现实中，多信道机制也是无线网络系统中广泛使用的通信技术。例如，以工业无线传感器网络为设计对象的工业无线网络标准技术(Wireless networks for Industrial Automation Process Automation,WIA-PA)、无线可寻址远程传感器高速通道的开放通信标准(Wireless Highway Addressable Remote Transducer, WirelessHART)等国际标准普遍采用了多信道通信技术，能够利用多条信道进行数据传输，有效提升无线网络的容量和性能[11]。由于多信道无线网络中存在信道冲突和链路冲突等问题，因此AoI链路调度策略的设计更加复杂。

面对这一挑战，本文基于存在信道冲突和链路冲突约束的多信道无线网络，综合运用李雅普诺夫偏移调度方法和Kuhn-Munkres(KM)匹配算法，提出最小化平均AoI的在线链路调度算法，有效地提高网络的实时性。

2 相关工作

AoI作为一种新的度量指标，最初由Kaul等人[3]引入，用以从目标节点的角度量化数据的新鲜度。自此以后，学术界结合不同的排队模型，从源更新频率、服务率等方向展开了AoI相关的理论研究；并且在无线网络场景中，综合考虑了信道状态、吞吐量、能量等因素，对优化AoI的调度方法进行了广泛而深入的研究。Kaul等人[3]结合排队论研究了AoI的计算和迭代过程，并在随机调度策略下给出了平均AoI与服务率、到达率间的解析式。Kam等人[4]探究了固定截止时间约束和随机指数截止时间约束下，服务率对平均AoI的影响。文献[5,6]在单源单目的地的边缘计算场景下，分析了不同计算模式下的AoI。而在无线网络的链路调度方面，文献[7]研究了周期性数据更新下逐时隙链路调度的问题，提出了随机、贪婪、李雅普诺夫优化、Whittle Index等策略进行链路调度以优化网络的平均AoI。文献[8]针对数据随机到达的场景，基于马尔可夫决策过程分别提出了离线和在线调度算法。文献[9]和文献[10]分别研究了在吞吐量约束和能量约束下的优化AoI的链路调度问题。

上述文献[7-10]均是在单信道网络场景中对AoI链路调度方法进行研究。而在多信道无线网络场景中，文献[12]考虑了能量收集的无线传感器网络，研究了最小化平均AoI的调度问题，开发了基于Whittle Index的低复杂度算法。文献[13]基于多信道网络场景，分别提出了最小化峰值AoI和平均AoI的调度策略。文献[14,15]考虑了多信道无线网络中的链路干扰约束，采用遍历的方式构造可行的调度集合，推导出最小化平均AoI的调度策略。文献[16]针对信道状态未知条件下的多信道网络链路调度问题进行了研究，并分别提出了基于虚拟队列的策略和Age-based策略。文献[17]考虑了非均匀状态更新的多信道传输问题，并分别在任意采样和随机采样两种更新方式下，将优化问题构造为马尔可夫决策过程，研究最小化平均AoI的调度策略。

以上多信道场景中AoI的相关研究均未对链路冲突和信道冲突进行综合考虑，而且现有的AoI的调度研究大多是在假设数据产生时间已知的情况下进行策略设计[7-17]，但在实际网络中，获取数据的产生状态需要消耗一定的网络资源。因此，在数据产生状态未知的情况下，针对多信道无线网络中可能同时存在的链路冲突和信道冲突问题，开发最小化系统平均AoI的调度方法是本文的研究重点。

3 系统模型

图1 网络拓扑

4 调度方法

在本文的优化问题中，需要逐时隙分配信道给不同链路进行数据传输以最小化网络中的平均AoI。首先，将AoI的优化问题构造为李雅普诺夫优化问题[18]，提出了Max-Weight调度策略来最小化系统的李雅普诺夫漂移。然后，针对多信道无线网络中存在的信道冲突问题，运用KM匹配算法求解最小偏移量的链路调度组合。

4.1 Max-Weight调度策略

所提方法使用Max-Weight调度策略逐时隙通过最小化李雅普诺夫漂移量来进行调度决策。在Max-Weight调度策略中，李雅普诺夫函数刻画了在单个时隙下整个网络中AoI平方的大小，其偏移量则表示随着时隙的增加，相邻时隙中AoI平方的变化趋势。因此运用Max-Weight调度策略通过优化下一时隙的AoI，能够有效优化网络中的平均AoI[18]。

图2 数据包更新时隙分析

4.2 信道冲突分析

在本文所考虑的网络中，节点和信道在数据传输过程中存在冲突，在冲突约束下合理地进行调度决策是调度方法需要考虑的重要问题。

由于网络中的可用信道数量M有限，因此调度决策需要满足约束

4.3 Kuhn-Munkres匹配算法

KM匹配算法用以求解带权二分图的最大权匹配问题。其中二分图为一种图论的模型，用于构建两个集合中各点间的边的权重关系。最大匹配为满足每个点最多和一个点匹配的条件下，使得匹配的边权值最大的匹配组合[19]。在本文的方法中，将权重函数值取反并令其定义为匹配的边权，在约束条件下通过KM匹配算法所得的最大权匹配即为最小的李雅普诺夫偏移量的链路调度组合。

首先，将多信道冲突和链路调度问题转换为二分图的最大匹配问题，能够满足约束式(11)、式(13)，即信道数量有限且一个信道只能和一条链路进行匹配的约束。但若直接构建源节点和信道间的二分图，则无法满足约束条件式(12)，该约束使得同一目标节点下只有一条链路可以被调度。

然后，针对约束条件式(12)，为了满足最小化李雅普诺夫偏移量的目标，同一目标节点b在信道j下只会选择最小的权重函数值Wb,j，即Wb,j=min{Wi,j|i ∈(lb−1+1, lb−1+2,..., lb)}。因此，需要构建目标节点和信道之间的二分图，其中目标节点与信道之间的边权定义为该目标节点和信道下不同源节点的最小权重函数值。在目标节点与信道之间进行最大匹配的情况下，会使得目标节点与信道间进行单一匹配，于是相同目标节点下只会存在单个源节点传输数据，从而满足约束条件式(12)。表1给出了KM匹配算法的具体流程。

表1 KM匹配算法执行过程

如前所述，所提方法使用Max-Weight调度策略并结合KM匹配算法，形成的最大匹配即为最小的李雅普诺夫偏移量的链路调度组合。Max-Weight调度策略基于李雅普诺夫优化，在信道约束条件下最小化李雅普诺夫偏移量Δ[A(t)]。通过数据产生概率和传输成功率对李雅普诺夫偏移量进行计算分析，得出不同源节点在不同信道下的权重函数，然后使用KM匹配算法获得最大权匹配，令匹配的链路组合的调度决策di,j=1。在复杂度方面，相较于遍历所有可行的链路调度组合的复杂度O(NM)，K M 匹配算法在递归过程中的算法复杂度为O(Ma)，从而其算法的总体时间复杂度为O(Ma2)。由此可见所提方法在优化网络中平均AoI的同时还能进一步降低复杂度。

5 仿真性能与分析

本文使用Matlab软件搭建仿真验证平台，分别在不同的数据包产生概率、信道传输成功率、源节点数量、目标节点数量和信道数量等网络参数设置下进行了仿真实验，验证算法的性能优劣。所用计算机的配置参数为：Intel(R) Core(TM) i5-8500双核处理器；3.0 GHz主频；16GB RAM；Windows10操作系统。

图3展示了几种算法下网络中的平均AoI随信道数量递增的变化趋势，其中传输成功概率和数据包产生概率在区间[0.2,1]不等，源节点数量N=100，目标节点数量为a=20。从图中可以看出随着信道数量的递增，网络中的平均AoI呈下降趋势。这是由于信道数量的增加，源节点被调度的机会更大，从而降低了其在目标节点处的AoI。

图3 不同信道数量下4种方法对比

图4 不同信道传输成功率和节点产生数据概率下对比

图4(a)展示了几种算法下网络中的平均AoI随着信道传输成功率基准值PB递增的变化趋势，不同信道传输成功率为PB减去一个[0,0.1]间的随机数，即Pi,j=PB−0.1×rand(1)。而数据包产生概率在区间[0.5,0.8]不等，源节点数量N=100，目标节点数量a=20，信道数量M=4。在传输成功率较小时，几种调度方法的性能差异也比较明显，随着PB的增加，贪婪调度策略和Age-based策略的优化性能逐步接近Max-Weight策略。这是因为Agebased策略和Max-Weight策略的制定均与信道传输成功率密切相关，随着PB的 增加，不同信道传输成功率的差异性逐渐减小，对这两种策略的影响逐渐减弱，因此，当PB接近1时，贪婪调度策略、Agebased策略和Max-Weight策略更有可能做出相似的调度决策，3种算法的性能基本相当。图4(b)给出了传输成功率在区间[0.5,0.8]不等，而数据产生概率为一个基准值αB减去一个[0,0.1]间的随机数，即αi=αB−0.1×rand(1)时，源节点的数据包产生概率对平均AoI的影响。可以看出随着数据产生概率的增加，平均AoI呈现出递减的趋势。这是因为频繁的数据产生可以保持源节点处数据的新鲜度，使得数据产生时间趋近于当前时间。

图5展示了几种算法下网络中的平均AoI随着源节点数量递增的变化趋势，其中源节点的传输成功概率和数据包产生概率在区间[0.2,1]，目标节点数量a=20，信道数量M=4。可以看出随着节点数量的递增，所有方法的AoI基本呈线性增长的趋势。这是由于随着源节点数量的增加，每个源节点被调度的机会相应变小。

考虑到算法的实用性，表2给出了使用Matlab软件进行仿真时，所提方法的平均执行时间。在不同节点规模下，其平均执行时间在1 ms以内，而在实际网络中，调度算法可运行于系统的管理器(如WIA-PA网络的网关设备和主控计算机)中，能够较好地满足工业无线网络的传输需求。

综上所述，相较于3种改进的对比策略，所提方法均表现出更好的优化性能。特别是在网络中的信道传输成功率和源节点数量相差较大时，所提方法由于对各种网络参数的综合考虑，其优化性能对比其他3种算法，有显著的提升。

6 结束语

图5 不同源节点数量下几种方法对比

表2 Max-Weight方法的平均执行时间(ms)

本文提出一种在考虑链路冲突约束的多信道无线网络中基于平均AoI优化的调度方法。本方法将平均AoI优化问题转换为李雅普诺夫优化问题，利用Max-Weight调度策略对李雅普诺夫偏移量进行优化，并结合KM匹配算法解决网络中的信道冲突问题。理论分析和仿真验证表明，该场景下Max-Weight调度策略优于改进的对比策略，能够有效优化网络中的平均AoI，提升网络数据传输的及时性。在未来的研究工作中，将考虑在多信道无线网络场景下，结合吞吐量、截止时间和能耗等因素对AoI进行联合优化，使之能够在提升数据传输的及时性的同时满足更多的应用需求。