天地融合网络中基于博弈论的分布式卸载算法研究

罗志勇，黄 澳，孙韶辉，辛 宁

(1.中山大学 电子与通信工程学院，广东 广州 518107;2.大唐移动通信设备有限公司，北京 100083;3.中国空间技术研究院通信与导航卫星总体部，北京 100094；4.国家航天局卫星通信系统创新中心，北京 100094)

0 引言

计算卸载策略一直是边缘计算技术(Mobile Edge Computing，MEC)推广应用过程中重要的研究内容[1-3]。一方面，通信技术的不断发展使得数据流量不断增加、业务需求不断提高[4]，而终端设备计算能力与能量储备却是有限的，难以满足业务在时延和能耗方面的需求。因此，在传统通信网络中终端设备通常将任务传输给远处的云计算中心进行处理[5]，在边缘网络中则是需要将任务卸载到边缘节点(Edge Computing Node,ECN)上[6]。另一方面，因为ECN具有轻量化特点，部署资源有限，同时移动设备进行卸载时自身也有能量资源消耗，所以也需要有合适的计算卸载策略来优化卸载过程。

Wu H等人[7]将响应时延作为主要研究对象，提出GAMEC策略进行卸载节点的选择决策。余翔等人[8]提出基于博弈论的功率分配算法，对功率和计算卸载进行联合优化，提高卸载性能。文献[9-10]基于联合思想，将计算卸载同计算资源分配联合为一个NP-hard优化问题，各自采用不同方法分两步进行了求解。

在具体的MEC网络中，ECN对部署资源的分配非常重要。尤其是当多设备同时卸载竞争资源时，通信信道被大量占用导致设备相互干扰加大，进而影响整体网络性能。

在天地融合网络这一应用场景下，由于星上资源的宝贵，这样的问题更加突出[11-12]。针对该问题，本文从文献[13]提出的地面基站内多终端设备博弈卸载模型中受到了启发，提出该场景下的博弈论卸载算法。经过有限次迭代达到非合作博弈下的“纳什均衡”，最终实现了该算法在天地融合网络中的运用和改进。

1 系统模型

1.1 通信卸载场景

在海洋、荒漠或战争、灾害等复杂地理环境中，地面蜂窝网络难以满足船只、UAV等终端的服务需求，移动终端可选卸载方式只有将任务卸载到部署了MEC服务的LEO卫星上进行处理，其卸载模型如图1所示。

图1 星-地卸载场景Fig.1 Satellite-Ground computing unload scene

该场景在复杂地理环境中有明确需求存在。但就现有技术水平而言，从地面将计算任务卸载到星上处理并不经济，难以在上述固定需求外开展大规模应用。

另一种考虑为由于卫星之间处理能力的不均等，使得处理能力弱的卫星有可能将任务卸载到能力强的卫星上，来减小开销的星间卸载场景。其卸载场景基本单元如图2所示。

图2 星间卸载模型基本单元Fig.2 Satellite-Satellite computing unload scene

该卸载场景需要卫星之间存在星间链并且具备交换通信能力。例如铱星星座中每颗卫星与同、异轨道面共4颗卫星构成星间链路[14]。在这个基本结构上延伸扩展形成一个庞大的卫星星座。设想星座中存在CPU频率高的高处理能力卫星，而周围卫星处理能力较弱。倘若卫星可通过一定的卸载策略进行决策判断，将任务卸载到能力强的卫星上进行处理，则此时利用卸载策略最小化卸载方开销，比星地卸载场景中节约地面终端资源的意义更大。

上述场景中，通信模型都为一个卫星边缘计算节点对应服务范围内多个终端设备。可建立数学模型并设定参数如下：

终端设备集P={1,2,3,…,N},每个设备都有不可分解的计算任务;

无线信道集C= {1,2,3,…,K},代表卫星提供K个可进行任务卸载的正交子信道;

决策集S={s1,s2,…,sn}，其中，有si代表终端设备i的决策情况。当si= 0时，代表任务本地计算；当si∈C时，代表任务将卸载到第si个信道上进行处理。

考虑到不同终端设备进行任务卸载时可能利用相同子信道导致相互干扰，根据Shann-Hartley定理可得到从终端n卸载任务到SEC服务器第k个信道的数据传输速率为：

(1)

式中，w为子信道带宽，w0代表传输过程中的噪声功率，qi代表终端i传输功率；gi,k为终端设备i在卫星信道k上的信道增益。

(2)

1.2 计算模型

根据决策的不同，任务处理类型可分为本地处理和卫星边缘节点处理两大类。

1.2.1 本地处理

本地处理对应终端设备决策si= 0的情况，即计算任务由终端本身处理而不卸载至MEC网络中。此时需知参数主要是终端CPU处理能力Fbs和能耗因数θn。

定义本地处理时延为任务所需CPU操作数和本地处理能力之比：

(3)

本地处理过程中的能耗即为任务所需CPU操作数、本地处理能力平方与能耗因数之积：

En=θn(Fbs)2an，

(4)

式中，能耗因数θn通常与芯片中开关电容元件数量等参数有关[17]。

综上所述，本地处理模型的计算开销函数即可表示为:

(5)

1.2.2 卫星边缘节点处理

卫星边缘节点处理对应终端设备决策si∈C的情况，即终端设备本地处理能力不足或者本地处理开销较大时，决定把计算任务卸载到卫星所提供的第si条子信道上进行处理。

整个计算卸载过程分为三部分：终端任务上传、边缘节点处理以及处理结果回传。倘若节点上部署的资源正在被其他终端设备调用，则还需等待资源释放的等待时延。

结合式(1)可定义上传时延、上传能耗、节点处理时延为：

(6)

Eup(n)=PnTup(n)，

(7)

(8)

综合式(6)～式(8)，考虑到已卸载终端数num和可能存在的排队时延Twait后，可得卫星边缘节点处理模型的开销函数表达式为：

(9)

1.3 卸载问题描述

考虑多用户对卫星边缘节点上部署资源的竞争，优化参数目标为综合考虑时延与能耗的总开销值。

用S-i={s1,…,si-1,si+1,…,sn}代表终端设备i以外所有终端设备的决策向量集。则对终端设备i来说，需要做出决策si以获取期望最小开销：

minCosti(si,S-i),∀i∈P,si∈{0∪C}，

(10)

从而获得能够使整个天地融合网络MEC系统卸载过程总体开销最小的解决策集S。

2 基于博弈论的计算卸载算法

2.1 博弈论基本思想

在有多个参与者的博弈过程中，各参与者都需要结合其他参与者的决策情况，在迭代中不断调整自身决策使自己尽可能获取更大增益/更小开销，经过有限次的迭代达到“纳什均衡”情况。在该情况下任何一个理智的决策者都不会再做出更新决策的选择，因为他已经获得了当前情况下的最大收益或最小开销。

因此，该思想适用于计算卸载中多终端非合作博弈场景[18]，分布式的卸载策略让每个节点可自行评估决策好坏并做出当前情况最优决策，完成卸载节点选择和任务卸载，从而使得MEC系统整体卸载开销最小。

2.2 算法实现

在MEC系统中，不同终端之间的非合作博弈是势博弈的一种，其特点是存在一个单调势函数。每次迭代中用户改变策略导致开销变化都能映射到势函数中，可证明经过有限次迭代，必能得到“纳什均衡”解[19]。

由此可设计博弈论卸载算法，具体要点如下：

① 初始化终端设备决策全为本地决策。

② 每个时隙下每个终端设备的工作有：

a. 计算已有决策对应开销值；

b. 评估所有可能的决策值，取当前情况下开销值最小决策为最优决策；

c. 比较已有决策与最优决策，若最优决策开销小于当前决策开销，代表终端设备决策可更新。

③ 下一个时隙，边缘服务器随机选择一个终端设备进行决策更新。重复迭代过程，直至当前时隙无可更新决策的终端设备，此时算法结束。

据此，可给出多用户博弈卸载策略如下:

算法 1:天地融合网络中博弈论卸载算法输入:N 个计算任务元组、噪声功率w0、各终端传输功率P与对应各信道上的增益g1初始化:可更新决策集不为空2对于每个用户从i = 1转到 N进行3初始化用户决策 si= 0, 计算本地处理开销 cost(i)=λtiTi+λeiEi4while当前可更新用户集不为空5 将更新决策用户集置空;6 对于每个用户从i = 1转到 N进行7 对于每个卫星子信道从l= 1 转到 K 进行8 获取该信道信干噪比,计算上传速率 Rup(n);9 计算该用户在该信道总体开销值 C(si,S-i);10 该用户最优决策开销值newsi(t) = min(C(si,S-i))11 if最优决策开销现有决策开销,then12 将更新请求与内容一并发送至 SEC 节点13 可更新决策用户集用户数 +1;14 边缘卫星MEC服务器在可更新决策用户集中随机选择一个,按内容更新决策与对应开销值15 对于每个用户从i = 1转到N进行16 if收到到更新指令,then17 下一时隙更新 si(t + 1) = newsi(t);18 else19 下一时隙不更新 si(t + 1) = si(t)。

2.3 贪心算法优化

根据现有算法1，在每一次迭代中MEC服务器在可更新的终端设备列表中随机选择一个终端设备进行决策更新，这样的随机选择策略充分体现了终端设备之间接入卸载的公平性。

但从开销角度来看，该选择策略并非最优。可引入贪心算法的思想，MEC服务器对可更新决策开销集UC进行排序，优先选择卸载后开销值大的用户进行任务卸载。将该算法中“在可更新终端设备集UD中随机选择一个终端设备进行更新”的随机选择策略替换为贪心选择策略。

3 仿真结果分析

以1.1节中星地卸载模型为例，一些基本参数设置如表1所示，在Matlab2020a平台上进行编程仿真测试。

表1 仿真参数指标

3.1 博弈论算法仿真结果

将程序结束后卸载方所有设备的总体开销值作为评判标准，把该算法与另外3种常见的计算卸载方案加以对比：

① 本地处理方案，只有本地处理决策。

② 忽略排队时延方案，只做出将任务卸载到边缘计算节点上的决策。

③ 不考虑排队时延方案，即该方案不能接受存在的排队时延。一旦边缘计算节点资源已被其他终端设备利用，终端设备就只会做出将任务放置在本地进行处理的决策。

图3展示了4种算法的卸载性能:本地处理算法和忽略排队时延算法因为决策的单一性，设备间相互干扰会很大，两者开销明显大于博弈论算法。而在博弈论卸载算法和不考虑排队时延算法二者中，后者因为算法本身选取策略稍弱，加之忽略了排队时延存在时可能有的增益，总体开销稍大。

图3 不同算法下的卸载开销Fig.3 Unloading loss of different algorithms

图4卫星支持的子信道数量增加实际增加了ECN上的通信资源，不同终端设备决策到相同信道上相互干扰的情况更少、竞争减小。因此博弈论、不考虑排队时延、忽略排队时延3种方案总开销都呈下降趋势。本地处理方案与其无关，总开销保持不变。

图4 子信道个数K对总体开销的影响Fig.4 Impact of subchannel number on overhead

图5表明终端设备数/待卸载任务数N的变化，一方面本身增加了网络中总的待处理任务量；另一方面在信道资源不变的情况下，有更多终端设备受到了其他设备的干扰。各方案总体开销值都在增加，尤其是忽略排队处理方案受到影响很大。

图5 待卸载任务数N对总体开销的影响Fig.5 Impact of device number on overhead

在这过程中博弈论算法总体开销最低，始终保持着较好表现。

3.2 贪心优化结果

根据2.3节中引入的贪心策略，优化MEC服务器选择更新策略后重新进行仿真，可得结果如图6和图7所示。

图6 贪心优化算法效果(K变化)Fig.6 Greedy strategy optimization effect(K changes)

图7 贪心优化算法效果(N变化)Fig.7 Greedy strategy optimization effect(N changes)

由图6与图7可得，优化后算术开销随参数N与K的变化趋势与原算法保持一致，但此时算法的损耗值在原算法基础上进一步减小。分析原因是优先选择了卸载后损耗大的终端设备进行任务卸载。根据ECN和移动终端处理能力之比，在终端设备之间相互干扰尚不严重的情况下，那些卸载到边缘节点上处理开销依旧大的任务，被放置在本地处理只会带来更大的时延与能耗。优先卸载处理它们，能有效解决这一问题。

4 结束语

本文针对天地融合移动边缘计算网络，研究其中各终端对边缘节点通信资源的竞争问题。针对终端计算任务不可分割的二进制卸载类型，提出该场景下基于博弈论的分布式卸载算法。在讨论适用场景、进行公式推导与计算模型的构建后，Matlab程序仿真结果表明该方法能有效减小卸载方的时延与能耗。贪心思想的引入改进了MEC服务器的选择更新策略，使得总体开销值进一步缩小。在实际意义上对天地融合网络时延方面的不足具有一定的弥补。

在后续工作中，将在此基础上尝试与排队论、强化学习等多种理论和方法结合，从模型与算法等角度进行进一步优化完善，适应规模更大、链路更复杂的天地融合网络，进一步提高卸载效率。