缓冲辅助中继网络中的缓冲资源分配方法

刘婷婷，陈开源，蒋诚智，余 雨，蒋 姝

（1.南京工程学院信息与通信工程学院，南京，211167；2.南京工程学院经济与管理学院，南京，211167）

引 言

近年来，由于智能终端的迅速发展，移动内容消费日趋增加，人们可以随时随地享受无线蜂窝网络带来的娱乐体验，但同时也给蜂窝网络带来了巨大的流量压力[1]。有证据表明，蜂窝网络中存在很多重复传输，比如热门视频，热点新闻短片等等。因此，有学者提出预先在网络边缘结点，比如移动手机终端，机顶盒，路由器等边缘存储设备中，存储热门视频的方式，缓解网络中，尤其是主干网中重复流量的问题[2‑3]。在之前的研究中，也证实了可以通过预存储热门视频或文件，有效降低网络流量，提高网络传输效率，同时也增加用户的满意度。

然而，由于边缘结点存储空间有限，或者缺乏足够的激励，网络的边缘结点并不愿意贡献出足够的存储空间。因此，只有部分文件或部分热门视频，被存储在边缘结点中，当这些没有被存储/没有被完整存储的文件被请求时，需要向远端的服务器提出请求。由服务器通过网络传输未被存储的部分。因为服务器一般都位于较远的地区，文件传输过程中，会经历较长的时延，若文件到达网络边缘，比如基站，先被放入边缘结点的存储空间，再从存储空间读取，分发给请求用户，将进一步增加时延，容易导致用户满意度进一步降低。然而，在边缘结点中，除了存储空间，还有缓冲空间。缓冲空间是一种造价相对较高的短暂记忆高性能存储器。为了提高用户的满意程度，已有一部分学者开始研究如何使用缓冲辅助中继方法来提高从远端服务器传输文件的性能[4‑5]。文献[4]提出了一种自适应链路选择的中继协议。为了避免数据丢失，在中继结点中配备了缓冲器，数据在被传输之前，在缓冲器中排队。笔者研究了时延约束和无时延约束两种条件下的链路选择方案。此外，还提出一种改进的链路选择协议，可以有效避免缓冲区溢出。文献[5]讨论了几种不同网络拓扑的缓冲辅助中继方案，包括单向单中继网络、单向多中继网络以及双向单中继网络。

上述论文主要是针对链路选择方案进行研究。然而，当到达数据流与离开数据流不平衡时，缓冲中容易产生数据积压，甚至数据溢出，也是影响缓冲辅助中继方法实现的重要因素之一。有必要对缓冲空间数据到达和离开与数据积压或缓冲区溢出关系进行研究。近年来，鞅理论是认为是分析数据积压/数据溢出的有效工具[6]。鞅理论适用范围较广，适于任何数据到达和离开过程，尤其对于有突发数据流的环境，能获得紧致的估计[7‑10]。文献[7]运用鞅理论研究了在高速铁路网络中，数据的传输时延界，并将理论推导出的时延界与真实数据对比，证明了鞅理论获得的时延界具有紧致性；文献[8]运用鞅理论分析了车辆网中，车辆之间数据传输的时延界，实验结果也证明了鞅理论获得的时延界与真实数据模拟的时延界是一致的。随着研究的发展，还有学者将鞅理论运用于优化问题，将鞅理论获得的时延界作为优化条件或目标，增强网络性能。文献[9]将鞅理论推导出的时延界作为限制条件，优化网络的能效；文献[10]将鞅理论推导的时延违反概率作为目标函数，建立优化问题，获得计算任务最佳分配方案。

缓冲空间作为影响边缘结点或中继结点工作性能的重要部件，边缘/中继结点只愿意贡献出有限的空间，用于缓冲辅助中继。需要在保证边缘/中继结点自有业务使用性能的前提下，对其贡献出的缓冲空间进行合理分配，以优化缓冲辅助中继的分发性能。因为边缘结点在缓冲辅助中继网络中有中继结点的功能，为了方便讨论，文中将不再区分边缘结点和中继结点，统一使用中继结点。本文将研究缓冲辅助网络中缓冲资源的最优分配方案。首先研究了在缓冲辅助中继网络中，为了保证中继结点自有业务使用性能，优化缓冲资源的方法；其次，使用鞅理论对中继结点缓冲空间内部的积压进行分析，确定缓冲区溢出概率与中继结点请求和输出参数的关系，并给出了能满足中继结点自有业务使用性能的缓冲区大小的表达式；接着，运用鞅理论，确定用户在中继结点处缓冲区溢出概率表达式，构建最小化所有用户缓冲区溢出概率和的优化问题，获得闭式解；最后，通过计算机仿真验证了中继结点贡献出的最大缓冲区比例与中继结点单位时间产生数据量的关系，用户分配到的最优缓冲区比例与用户距离中继结点的距离的关系，本文提出的最优缓冲区分配方法优于均匀分配方法。

1 系统模型

本文使用的系统模型如图1 所示，该系统由远端服务器，回程链路，基站，中继结点和多个用户组成。在中继结点覆盖范围内有N个用户，表示为Ui，i=1，…，N，这些用户均有文件传输需求。该网络使用缓冲辅助中继方法提高文件传输性能，具体是指中继结点将缓冲空间分成不等的N份，为N个网络用户传输文件使用。

图1 系统模型Fig.1 System model

1.1 中继结点能贡献出的缓冲区比例

在保证中继结点自有业务传输性能的前提下，其能够贡献出的缓冲区容量是有限的。下面根据中继结点对缓冲区溢出概率的要求，确定中继结点能贡献出的最大缓冲区的比例。

1.1.1 中继结点的数据到达模型

中继结点R由于自有业务传输性能要求，也要使用缓冲空间。所以中继结点在为周围用户提供缓冲辅助中继服务之前，根据数据到达模型和数据处理模型，需要预留出部分缓冲空间，供中继结点自有业务使用。中继结点在时间l产生的数据量为r(l)。r(l)服从马尔科夫调制开关过程，具有两个状态和表示没有数据到达，在这种状态下，r(l) =0。状态表示有数据到达，即r(l) ≠0。假设状态转移到状态的概率为pr，状态转移到状态的概率为qr，用转移矩阵表示为Π=在状态的稳态分布可以分别表示为在一段时间[v,u]内，中继结点累计到达数据量可表示为

式中：r(l)表示中继结点在时间l产生的数据量；R(v,u)表示中继结点在时间[v,u]内累计到达的数据量。

1.1.2 中继结点的数据处理模型

中继结点在时间k，处理结点内部产生的数据速率可以表示为常数c。在一段时间[v,u]内，累计处理的数据量C(v,u)可表示为

为使讨论有效，假设

式(3)表示，中继结点的数据处理速率大于数据到达速率的期望，同时小于数据到达速率的峰值。这种情况会在中继结点内部产生数据积压，引起缓冲区溢出。

1.1.3 中继结点缓冲区溢出概率

中继结点内部积压Qr定义为

式中：R(n)表示在时间[0,n]内累计到达的数据量；C表示在时间[0,n]内累计处理的数据量。从式(4)可以看出，缓冲中的积压值有随机的特性，很难给出确定的数值。因此，采用鞅理论，缓冲区溢出概率可表达为[11‑12]

式中：Qr表示中继结点自有业务产生的积压；α表示用于缓冲辅助中继使用的缓冲区比例，X表示缓冲结点的总缓冲区容量，αX表示中继结点贡献出的用于缓冲辅助中继的缓冲区大小，(1-α)X则表示中继结点留给自有业务使用的缓冲区大小，其中，0 ≤α≤0 表示中继结点贡献出的比例；根据鞅理论，E[hr(r( 0 ))]表示对hr(r(0))求期望，hr(r(0))表示r(0)的右特征向量，r(0)表示时间为0 时请求的初始数据量。Hr=min {hr(r(l))|r(l)-c>0,l≥ 0}，hr(r(l))表示r(l)的右特征向量=sup{θr>0:Kr(θr)≤Kc(θr)}，θr是一辅助变量的谱半。

若给定中继结点能够容忍的缓冲区溢出概率ξr，根据式(5)可得到中继结点贡献出的最大缓冲区比例为

1.2 用户在中继结点处缓冲区溢出概率

基于1.1 节的讨论，得到中继结点贡献给用户缓冲辅助中继的缓冲区大小为αX。假设用户Ui分配到的缓冲区大小为αi X,0 ≤αi≤α，且下面分析用户缓冲区溢出概率与缓冲区大小的关系。

1.2.1 用户的数据到达模型

假设用户Ui在时间l请求的数据量为ai(l)。ai(l)服从马尔科夫调制开关过程，具有两个状态和表示没有数据到达，即ai(l)=0，状态表示有数据到达，且ai(l)≠0。用户Ui的状态转移矩阵表示为两个状态的稳态分布可以表示为在一段时间[v,u]内，用户Ui累积到达中继结点的数据量Ai(v,u)可表示为

式中ai(l)表示用户Ui在时间l请求的数据量。

1.2.2 用户的数据服务模型

中继结点贡献给用户Ui的有限的缓冲容量为αi X，用于缓冲从基站发送给用户的数据，再利用近距离优势，采用高速传输技术发送给用户，提高内容分发的效率。在时间l，从中继结点到用户的服务速率可表示为

式中：B为分配给每个用户的带宽为用户的接收功率为传输功率，di为中继结点到用户Ui的距离，g为路径损耗参数为噪声密度。在一段时间[v,u]内，中继结点传输给用户的数据量Si(v,u)表示为

式中si(l)表示在时间l，从中继结点到用户的服务数据量。为使讨论有效，假设

式(10)表示，中继结点传输给用户Ui的速率si大于用户Ui到达数据速率的期望E[ai(l)]，但小于用户Ui请求数据到达的峰值supai(l)。这种情况也会在中继结点内部产生积压，引起分配给用户Ui的缓冲区溢出。

1.2.3 用户的缓冲区溢出概率

使用鞅理论，用户Ui在中继结点内部的缓冲区溢出概率可写成

式中：Qi表示用户Ui产生的积压；αi X表示中继结点贡献给用户Ui的用于缓冲辅助中继的缓冲区大小。根据鞅理论，E[hi(ai(0))]表示对hi(ai(0))求期望，hi(ai(0))表示ai(0)的右特征向量，ai(0)表示时间为0 时请求的初始数据量。Hi=min {hi(ai(l))|ai(l)-si>0,l≥0}，hi(ai(l))表示ai(l)的右特 征 向 量 ，是 一 辅 助 变 量 ，其中，的谱半径，。

2 最优缓冲区资源分配方法

中继结点的缓冲区需要划分成不等的N份，为了获得最小的缓冲区溢出概率和，建立如下优化问题

式(13)表示根据中继结点保留的缓存空间求出的缓冲区溢出概率小于等于中继结点能够容忍的缓冲区溢出概率ξr；式(14)表示分给用户的缓冲区比例和不能超出中继结点分配给用户使用的缓冲区比例；式(15)约束了分配给用户的缓冲区比例值是非负值。对式(12)求一阶导数和二阶导数，可分别获得

从式(16,17)可看出，目标函数的一阶导数小于零，二阶导数大于零，这是一个典型的凸函数。建立拉格朗日方程和 Karush‑Kuhn‑Tucher (KKT)条件

式中：参数 {κ1,κ2,…,κN}和参数υ为拉格朗日乘子。KKT 条件中的第 3 个条件，即κiαi=0，可以得到当κi≠ 0 时，αi=0；或者当κi=0 时

式中υ是一变量。可通过调节υ的值，来满足限制条件因此，可以获得优化问题的解为

式中符号(∙)+表示：若括号内的数据比零小，则取零值；若括号内的数据比零大，则取该数值。

综上，本文提出的算法步骤如图2 所示。首先，根据鞅理论确定中继结点缓冲区溢出概率表达式；然后，根据中继结点能够容忍的缓冲区溢出概率值，求出中继结点能贡献出的最大缓冲区比例；接着，运用鞅理论，确定用户在中继结点内部的缓冲区溢出概率表达式；接着，建立最小化用户缓冲区溢出概率和的优化问题，受限于中继结点能贡献出的最大缓冲区比例和每个用户分配到的缓冲区比例必须为大于等于零的数；最后，运用拉格朗日方程和KTT 条件，求出缓冲区最优分配比例。

图2 本文提出的算法步骤Fig.2 Steps of the proposed algo‑rithm

3 仿真结果

本文提出的缓冲资源分配方法的数值仿真参数如表1 所示。

图3 给出了中继结点贡献出的最大缓冲区比例随着中继结点单位时间产生的数据量r的关系图。从图3 可以看出，随着中继结点单位时间产生数据量r不断增大，中继结点贡献出的最大缓冲区比例逐渐降低。这是因为随着中继结点单位时间产生的数据量增加，需要的缓冲空间也在逐渐增大。中继结点需要留一定的缓冲空间，以满足中继结点缓冲区溢出概率值。因此，剩余可贡献的缓冲空间就逐渐减少。此外，图中还对比了在不同中继结点服务速率的情况下，中继结点贡献出的最大缓冲区比例的区别。当中继结点服务速率为2.4 Mbit/s 的情况下，中继结点贡献出的最大缓冲区比例比中继结点服务速率为2.65 Mbit/s的情况下小，并且在中继结点单位时间产生的数据量大于4.5 Mbit/s 的时候，差距逐渐加大。这是由于中继结点服务速率减少，中继结点缓冲区积压将变多，为了满足同样的缓冲区溢出概率要求，中继结点需要保留更多的缓冲区空间，所以贡献出的缓冲区比例变小。

图4 给出了6 个用户，距离中继结点距离为20 m，用户的数据到达率分别为 4、4.2、4.4、4.6、4.8 和 5 Mbit/s。序号 1-6 分别代表用户1 到用户6。随着用户到达速率增加，而中继结点给用户的传输速率是一样的，那么用户在中继结点内部的积压值也会增加，为了获得较低的缓冲区溢出概率值，需要给到达速率较大的用户分配较大的缓冲区比例。从图4 可看出，用户6，即到达速率为5 Mbit/s 的用户，获得了最大的缓冲区比例，而到达速率最低的用户1，则被分配了最小的缓冲区比例。此外，图中还对比了中继结点数据到达速率不同时，用户分配的最优缓冲区比例的区别。可以看出，中继结点数据到达率较高时，即4.8 Mbit/s 时，分配给用户的最优缓冲区比例小于中继结点数据到达率为3 Mbit/s 时的最优缓冲区比例。这是因为当中继结点数据到达速率增大时，中继结点能贡献出的最大缓冲区比例降低，导致分配给每个用户的最优缓冲区比例也降低。

表1 系统仿真参数Table 1 System simulation parameters

图3 中继结点贡献出的最大缓冲区比例Fig.3 Maximum buffer ratio contributed by relay node

图4 用户分配到的最优缓冲区比例Fig.4 Optimal buffer ratio allocated by users

图5 给出了用户1 分配到的最优缓冲区比例随着中继结点单位时间产生的数据量r之间的关系。由图3 的讨论可知，中继结点贡献出的缓冲区大小随着中继结点单位时间产生的数据量逐步降低，因此分配给用户的缓冲区大小也逐步降低。由图5 可看出，用户1 分配到的最优缓冲区比例随着r变大而变小。此外，图中还对比了中继结点服务速率不同时，用户1 分配的最优缓冲区比例关系。在中继结点服务速率为2.65 Mbit/s 时，用户1 分配到的缓冲区比例大于服务速率为2.4 Mbit/s 时分配到的缓冲区比例，这与图3 的趋势一致。这是由于中继结点服务速率降低，中继结点能贡献的最大缓冲区比例下降，分配给用户1 的缓冲区比例也下降。

图6 给出了本文提出的最优分配法与均匀分配法的对比。本文提出的算法是以最小化缓冲区溢出概率和为目标设计的，这里使用简单的均分缓冲区方法作为对比方法。从图5 可以看出，使用本文提出的最优分配法，缓冲区溢出概率和在10-8量级，而均匀分配法则是在10-5量级，两者之间相差1 000 倍。此外，还可以看出，随着中继结点单位时间产生的数据量r增多，缓冲区溢出概率和增加了，这是因为r增多，中继结点贡献给用户使用的缓冲区变小了，用户在中继结点内部的溢出概率相应增加。均分缓冲区的方法只是简单的将缓冲区根据用户的个数进行均分，并未考虑用户由于距离中继结点远近，带来的传输速率差别，使得距离中继结点远的用户，在中继结点内部会产生积压，极易产生缓冲区溢出。而本文提出的算法是以最小化缓冲区溢出概率和为目标的，因此，最终给出的分配方案是考虑了用户距离中继结点的远近，距离中继结点较远的用户分配了较多的缓冲区，以减缓由于传输速率低带来的缓冲区积压问题，进一步降低了缓冲区溢出的概率。

图5 用户1 分配的最优缓冲区比例Fig.5 Optimal buffer ratio allocated by user 1

图6 最优分配方法与均匀分配方法的对比Fig.6 Comparison between optimal allocation method and uniform allocation method

4 结束语

本文针对缓冲辅助中继网络中，中继结点缓冲区资源的分配进行研究。首先根据中继结点的数据产生和服务模型，以及中继结点能容忍的缓冲区溢出概率值，给出了中继结点能贡献出的最大缓冲区比例。接着根据用户的数据产生和服务模型，给出了用户的缓冲区溢出概率值。构建最小化所有用户缓冲区溢出概率值之和的优化问题，获得分配给各个用户的最优缓冲区分配方法。从仿真结果可以看出，最优缓冲区分配方法与中继结点单位时间产生的数据量有关系，也与用户距离中继结点的距离有关，并且本文提出的最优缓冲区分配方法优于均匀分配方法。