基于网络模体的空闲计算资源捕获算法

李丽庭， 朱 蓉， 林基明， 王俊义

(1.桂林电子科技大学 信息与通信学院,广西 桂林 541004；2.桂林电子科技大学 广西无线宽带通信与信号处理重点实验室,广西 桂林 541004)

随着无线通信技术和微处理器技术的发展，智能手机、平板电脑等移动设备急剧增加[1]，思科预测到2022年全球移动设备将超过120亿台[2]。然而，受物理尺寸以及电池技术限制，移动设备计算能力和电池容量有限，难以满足像虚拟现实(VR)等新型应用的快响应、高能耗执行需求[3-4]。高可靠和低时延通信问题是近年来无线通信研究的难点和热点[5]。设备到设备(device to device，简称D2D)技术的出现，使得设备可以直接在设备与设备间进行数据传输[6-7]，可减轻基站负载，有助于缓解网络拥塞[8-9]，受到学术界和工业界的广泛关注。然而，如何捕获系统可用计算资源(即空闲终端)，减少云端负载至关重要。

目前，已经有很多学术工作致力于复杂网络中信息的捕获。为揭示复杂系统的结构属性，文献[10]提出网络模体(network motif)的概念，即复杂网络的互联基元(网络子图)，其在网络中出现的次数远高于其他随机网络子图，即网络模体具有统计占优特性。目前，网络模体的检测、分析、统计等，已成为热门研究[11-13]。

已有的网络属性研究主要针对网络节点、链接关系或整个网络的基本信息，如平均度[14]、聚类系数[15]、平均最短距离[16]、间度[17]等，缺乏对网络模体结构测度量的分析。不同的网络，节点的连接关系不同，其网络模体结构也有显著差异[18]。近年来，有少部分研究将复杂网络与网络模体结合，对复杂网络的网络模体结构测度量进行分析。文献[19-21]主要针对生物网络，研究DNA中网络模体特点、方法、优缺点，并对网络模体的检测进行归纳。然而，上述文献未考虑普通复杂网络及网络中不同节点的结构属性。鉴于此，基于移动边缘计算(mobile edge computing，简称MEC)网络，考虑通信网络的资源利用率低下问题[22]，将计算卸载与网络模体结合，通过查找复杂网络中模体，同时计算模体的Z得分，判断模体在原网络中的重要性，并结合KM算法，提出一种基于网络模体的设备匹配资源搜索算法，以充分捕获系统空闲计算资源，提高系统资源利用率，减少边缘云端负载。最后，仿真结果表明，该算法能有效捕获空闲计算资源，提高空闲资源利用率。

1 网络模体概述

将网络模体简称为模体，并对其定义、网络架构特征进行描述。

1.1 模体定义及特征

1)模体定义。复杂网络的互联基元(网络子图)在网络中出现的次数远高于对应随机网络子图[10]。给定一个网络G={V,E}，节点个数|V|=N，则模体定义为一个二元组(B,A)，B为k×k模体邻接矩阵，A⊂{1,2,…,k}为锚定节点。k-模体可表示为

(1)

其中：v为节点向量；χA(v)为选择函数，表示从向量中取出锚定节点A；(v,χA(v))∈M(B,A)为模体实例。

2)模体特性。节点数量特征：模体是小型、紧凑的连接子图结构，其大小介于网络个体和社团之间，一般由少数几个节点连接构成[23]。结构特征：模体可以用来描述社团内部成员之间的基本连接模式，能够揭示大多数网络的基础信息结构和基本构成，对于一些特殊网络而言，甚至可以认为该网络是多种“模体”的扩展。统计特征：模体在实际网络中出现的次数一般大于在随机网络中出现的次数，一般要求(nM-nrand)>0.1nrand。

1.2 基于模体的测度量

模体网络的常用测度量包括模体频率、模体Z分数及模体导率。

1)模体频率。在统计上，模体具有统计占优特性，即模体在实际网络中出现的频率大于模体在对应随机网络中的频率。给定子图类型M，其在网络出现的频率为

(2)

其中，nM、nsub分别为子图类型M和同节点数子图在D2D通信网络中出现的次数。若M为网络的模体，则fM为模体频率。

2)模体P值。对于模体M，为保证其统计占优特性，其在实际网络中出现的次数应大于它在随机网络中出现的次数。文献[24]给出模体存在的条件，即模体在随机网络中出现的次数大于在实际网络中出现的次数的概率应小于一个阈值，定义此概率值为模体的P值。P值越小，说明该模体在网络中越重要。P值用来证明子图联通类型是否可作为网络模体。

3)模体Z分数。Z分数(Z-score)，也叫标准分数，其数学表达式为

(3)

考虑衡量模体在初始通信网络中的地位，将Z分数引入模体网络，分析模体类型在通信网络中的重要性。模体的Z分数表示为

(4)

1.3 相关工作

根据模体测度量性质，当前与模体有关的研究主要从模体的查找、统计特性和结构特性上进行分析。

在模体的查找研究方面，文献[25]总结了复杂网络中的主题查找算法，并概述各策略的区别和优势。文献[26]基于网络检测并行性，提出一种分布式控制策略，在整个计算过程中提供动态负载平衡以实现模体检测的近线性加速。在模体统计特征研究方面，模体的频率或次数常作为衡量标准。文献[27]计算了所有3节点模体的绝对频率，并以此对网络进行分类。文献[28]基于模体在实际网络和随机网络的出现频率，采用Z-SCORE模型，提出一种快速、高效、并行的算法，加快模体的统计速度。文献[24]验证了复杂网络中模体的存在性，并基于模体顶点度，通过引入模体边度，分析模体在网络中的重要性。在模体应用上，文献[29]基于模体，提出了一种新的D2D网络分析框架，研究了星形和链形2种模体对D2D网络性能的影响，并确定有效的内容传播策略，导出了模体的统计显著性、中断概率和设备平均吞吐量的封闭解析表达式。

基于上述文献，通过对模体频率、P值及Z分数进行分析，证明D2D网络中模体的存在性，并结合KM算法对网络空闲计算资源进行捕获。

2 模体网络构造及分析

2.1 D2D通信模型

支持D2D通信的单蜂窝网络架构如图1所示，主要包含基站、MEC服务器和设备集N。设备有2种状态，分别为空闲状态和工作状态，工作设备可将计算任务卸载到空闲移动设备和MEC。

将通信网络图示化G={V,E}，其中，V={v}表示系统的所有设备和基站，E={e}为工作设备所有卸载链路，|V|表示设备和基站个数。

图1将通信网映射到上方，其中绿色表示处于空闲状态的移动设备，定义为Nidle(Nidle⊆N)，红色为处于工作状态的移动设备，定义为Nact(Nact⊆N)。工作设备允许在D2D最大传输范围内向周边空闲设备卸载计算任务。图G是一个有向图，边的方向即数据卸载方向，如图2所示。

图1 支持D2D通信的蜂窝网络

图2 D2D通信网络连接图

针对D2D通信网络，移动设备可通过D2D链路将计算或存储需占用大量资源的应用卸载到邻近设备，D2D传输速率为

Rij=Blog2(1+pitγij)。

(5)

实际上，设备距离越远，D2D通信越不稳定，为了体现设备距离对用户卸载质量的影响，以连接质量表示用户进行D2D通信的好坏程度，链路传输质量定义为

(6)

其中：pij为链路中断概率；dmax为D2D通信的最大距离，满足dji=dij。

2.2 模体网络构造

本质上，模体为网络的局部连接模式。在D2D通信网络中，局部移动设备之间的相互通信构成整个网络的基本单元，使用模体作为新网络的节点，一方面，模体内部的信号流动可以直观映射整个网络；另一方面，模体内部聚合度高，模体网络能更直观地表现出区域设备的聚合度。

图3为有向图的所有三节点模体类型，也就是说，在有向网络拓扑中，3个节点之间可以形成13种不同的连通关系。模体节点越多，包含的信息量越大，其组成联通关系也越复杂，四节点模体的联通关系可达199种。

图3 三节点模体类型

考虑移动设备的计算能力受限，为保证计算任务的正常执行，假设单个空闲移动设备只能处理设备卸载任务的一半，即Fidle=0.5Ftask。满足要求的模体类型有M6、M8、M10、M12，如图4所示。

图4 D2D通信适用模体类型

M10类型模体适用于工作设备多于空闲设备且移动设备任务量较少，空闲设备计算资源足够支持多个设备进行应用卸载的场景。M12模体类型对D2D通信链路要求较高，容易因AB链路中断而卸载失败。在M6、M8模体类型下，针对网络突发情况，M6可通过空闲中继将应用卸载到中断设备。基于此，考虑本移动设备计算资源受限及系统稳定性，选取M6对网络进行分析。

不失一般性，采用全锚定节点，即对k-模体有A={1,2,…,k}。原网络图可转化为一个有权无向的模体网络图Gm=(Vm,Em)。其中，|Vm|=N为图Gm的节点集，Em为图Gm的边，从而定义模体邻接矩阵WM，

(7)

其中，M表示模体类型，即每个矩阵元素表示同时包含节点i和节点j的模体个数，此时WM为双向图。

3 基于模体的空闲计算资源捕获

基于D2D通信的计算卸载可以不经过基站直接进行数据交互，一方面降低了通信链路的堵塞，另一方面减少了云端计算资源的使用量。

考虑空闲移动设备的计算资源受限，空闲设备处理的任务量为0.5Ftask，其中Ftask为移动设备任务的计算量。结合通信链路的稳定性，假定在D2D通信链路中，设备i、j之间卸载中断概率为pij，不失一般性，假设所有链路的中断概率一致，中断概率重写为pout，此时，通信链路正常的概率为plink=1-pout。

基于M6模体类型对D2D网络的空闲计算资源进行配置。令设备i为工作设备，j、k为空闲设备，且3个设备之间的距离满足最大D2D通信距离，设备i向设备j、k卸载计算任务，若通信链路eij中断，则设备i可以通过链路eik、ekj将任务卸载到设备j。因此，考虑链路的中断概率，M6对应网络结构中空闲移动设备处理的任务量可分为以下3种情况：

1)网络链路均正常通信时，任务处理量为

(8)

2)只有2条链路正常通信，有一条D2D通信链路断开时，处理任务量为

(9)

3)2条D2D通信链路断开时，处理的任务量为

(10)

由式(8)～(10)可得到模体处理工作设备的卸载任务量

Fmoff=FTlink+FBlink+FSlink。

(11)

对于一对一连接的D2D设备对(一个空闲设备与一个工作设备连接)，其处理的任务量为

(12)

否则，空闲设备更愿意选择最大的偏好链路进数据处理，即

(13)

(14)

通过衡量模体链路质量以及用户的偏好，将模体与KM算法结合。当模体不存在时，考虑工作设备与空闲设备之间的通信，此时，采用KM算法对2种类型设备进行配对，工作设备与具体算法如下：

算法1基于模体的设备匹配资源搜索

输入：D2D网络邻接矩阵和模体的邻接矩阵B

输出：计算资源捕获S

1. 初始化捕获计算资源S=0，去掉空闲设备对；

2. 利用式(6)计算链路质量矩阵LW；

3. 找到空闲设备与工作设备的一对一联通对集合P，利用式(12)求出任务量S1，S=S+S1；

5. if |Cm≥1|

6. fori=1:|Cm|

8. if (Dout)v1(Dout)v2(Dout)v3

10. endif

11. endfor

12. else

13. 清除空闲设备之间的通信链路，构造二分图；基于LW使用KM算法对设备进行配对，更新S；

14. 遍历工作设备，将配置空闲设备大于1的工作设备链路清空，更新LW；

15. 计算网络节点出度入度Din、Dout；

16. if max(Dout)>0

17. 转到步骤2；

18. endif

19. endif

考虑D2D通信网络中用户卸载任务到空闲设备，同时单个空闲移动设备拥有的计算资源有限，无法满足工作设备任务对计算资源的需求，同时考虑卸载中断的可能性，选用M6模体类型构造模体网络，2个空闲设备包含的计算资源较多，应充分考虑用户的资源需求，以保证卸载的正常进行。

4 仿真结果及分析

为了验证模体，对模体Z分数、模体个数及P值进行分析。将基于模体的设备匹配资源搜索算法与K-means聚类算法、随机聚类算法及KM算法进行对比，凸显本算法对系统空闲计算资源的捕获能力，不失一般性，利用任务数衡量所捕获的计算资源大小。

为了保证参数的合理性，将具体仿真参数设置如下：小区覆盖半径为500 m[30]；系统设备数量为100～500，且服从泊松点分布；D2D最大通信距离为50 m[30]；链路中断概率pout=0.9[31]；模体P阈值取0.01[24]。

模体的P值通过对比模体在实际网络和随机网络中的频率，利用二者的概率对模体的存在性进行证明。表1为通信网络和随机网络中M6、M8和M9模体类型出现的频率及P值。从表1可看出，在D2D通信网络中，M6和M8模体类型出现的频率远大于其在随机网络中出现的频率。此外，2个类型模体的P值均为0，远小于阈值0.01，M6和M8对应的联通结构可作为D2D通信网络的模体。然而，M9在随机网络中出现的频率高于在通信网络中的频率，且P值为1，远大于其阈值0.01，所以不能作为D2D通信网络的模体。

表1 D2D通信网络和随机网络中三角形模体类型出现的频率和P值

不同模体类型在网络中出现的次数及频率均有所差异。图5为随机网络和MEC网络中模体个数与设备个数的关系变化曲线。从图5可看出，M8和M6类型模体在实际MEC网络出现次数均大于在随机网络中出现的次数，符合统计占优特性。

图5 随机网络和通信网络中模体次数

移动设备数量的增加使得模体数量也增加，但覆盖区域内移动设备密集化程度的提高，也大大增加了设备信息交互的机会，使得对应同阶子图数量也增加，从而导致2个类型网络模体的频率下降，如图6所示。

图6 随机网络和通信网络中模体次数

模体类型不同，其在网络中的地位也不同，图7为M8和M6类型模体的Z分数。从图7可看出，M6的地位优于M8，且随着设备数量的增加，模体的Z分数也增加，即大型网络中的模体比小型网络中的模体具有更高的Z分数。

利用D2D通信处理的任务大小衡量捕获的计算资源。空闲计算资源捕获如图8所示。从图8可看出，基于模体的设备匹配资源捕获算法优于其他3种算法。因为模体考虑了链路质量及中断概率，在计算资源配置时，优先配置处理偏好系数高的设备，同时在完成模体配置后利用KM算法进行匹配，以提高捕获资源量。

5 结束语

通过对当前关于模体研究文献的介绍，汇总了支持D2D通信的蜂窝网络中模体选取、检测的一些技巧，包括在结构上和统计上进行测试。在结构上，对模体Z得分及导率等进行评价，以判断选取的模体在原复杂网络中的重要性，并证明模体具有统计占优特性。在计算资源发掘上，将KM算法与模体结合，在提高信息捕获量的同时，抗干扰能力也优于传统的配对方法。在接下来的研究中，将把模体与计算资源配置结合，研究模体网络在多维云资源配置下的优越性。