基于复杂网络的雾计算网络鲁棒性研究

李 治， 柳妍珠， 赵亚萌， 许海涛

(1. 北京科技大学 计算机与通信工程学院， 北京 100083； 2. 长城计算机软件与系统有限公司， 北京 100190；3. 中国科学院遥感与数字地球研究所， 北京 100101)

基于复杂网络的雾计算网络鲁棒性研究

李 治1， 柳妍珠2， 赵亚萌3， 许海涛1

(1. 北京科技大学 计算机与通信工程学院， 北京 100083； 2. 长城计算机软件与系统有限公司， 北京 100190；3. 中国科学院遥感与数字地球研究所， 北京 100101)

雾计算扩大了云计算的网络模式， 将网络服务由网络中心扩展到了网络边缘. 为研究雾计算网络的鲁棒性， 通过分析雾计算网络系统结构特征， 设计了基于复杂网络的BA无标度网络和ER随机网络混合模型， 并给出了相应的公式. 针对随机攻击和蓄意攻击两种情况， 对雾计算网络的平均路径长度以及平均度进行仿真实验. 实验结果表明， 当0

雾计算； 云计算； 复杂网络； 鲁棒性； 度分布

0 引 言

随着移动智能设备以及无线通信技术的发展， 我们已经进入到了一个全球互联的数字化信息社会新纪元. IDC的研究报告显示， 2016年全世界将有大约20亿， 超过全球人口总数1/4数量的用户通过移动设备访问互联网[1]. 移动智能终端的发展催生出大量的应用， 如社交网络、 导航系统、 物联网应用、 智能家居等， 它们的出现显著改变了人们的生活方式. 云计算为这些应用的数据处理提供了一个很好的解决方案. 然而， 随着越来越多的智能设备接入， 其产生的移动通信数据量成爆炸性增长， 这给网络环境和带宽带来了新的挑战. 一般而言， 云计算数据中心与移动设备之间的物理距离很远， 用户将海量数据发送至云端或者从云端返回数据给用户均需要耗费较长的时间. 因此， 从实时交互的角度出发， 把所有的原始数据发送到云数据中心进行处理并不是一种高效的选择. 为了解决云计算易延迟、 通信开销大等问题， 2012年思科提出了雾计算的概念[2]. 不同于云计算的集中式计算模式， 雾计算作为一种新型的分布式计算模式更符合互联网“去中心化”的特征： 用户数据无需上传到云中， 在本地智能设备中即可进行处理. 雾计算通过将性能相对较弱， 位置相对更为分散的各类计算资源进行集成， 将数据、 数据处理以及应用程序集中在网络的边缘设备中， 具有低延迟、 地理分布广泛、 位置感知、 适应移动性应用等特点[3-4]. 因此， 雾计算是解决连接互联网中设备数量不断增加问题的一种有效途径. 这种扩展的云计算网络模式无疑将推动物联网、 云计算等技术的高速发展. 然而雾计算网络的规划、 建设、 运营和管理均需要大量的科学理论、 模型和方法的支撑. 目前， 已有一些学者针对这种新型网络计算范式中体系结构[5]、 网络应用[6]、 系统安全[7]等方面开展了研究. 其中， 网络鲁棒性研究在雾计算网络实践上具有重要意义. 举例来说， 当雾计算通信网络节点发生故障时， 网络中的一些通信链路将可能发生中断， 进而诸如网络节点之间的最短路径、 链路负载、 拥塞发生条件等网络属性都将发生改变， 必然会影响整个网络数据的传输过程.

本文基于BA无标度网络[8]和ER随机网络[9]混合模型开展了雾计算网络演化过程的研究. 通过分析随机攻击、 蓄意攻击对雾计算网络结构的影响， 给出了较为精确的公式对其网络结构和功能的变化进行描述. 所提公式为分析雾计算网络鲁棒性提供了一个通用框架， 对保障数据安全， 构建抗随机攻击、 蓄意攻击的雾计算网络结构有着指导意义.

1 雾计算系统架构

作为一种云计算延伸的虚拟平台， 雾计算通常位于终端用户和云计算数据中心之间， 提供了一种低延迟、 低功效、 低网络数据流量的服务. 一般而言， 雾计算网络结构可以分成3层[10]， 如图 1 所示.

图 1 雾计算结构模型Fig.1 The fog computing architecture

用户层： 作为雾计算3层模型的最底层， 用户层由数量众多的智能终端与这些智能终端产生的海量数据所构成. 利用诸如WiFi， 蓝牙等短距离通信方式， 雾计算用户将智能终端与高层雾节点连接， 享受雾计算网络提供的服务[11].

雾层： 位于网络中间的雾层部署在地理上分散的雾服务器上， 为智能终端和云之间搭起了桥梁. 每个雾服务器是高度虚拟化的计算系统， 类似轻量级的云服务器. 通过配备大量的数据存储， 计算和无线通信设备， 对用户层上传的数据进行智能化处理.

云层： 模型的最高层为云层. 由于雾设备的处理能力有限， 当有任务需要更多的计算资源时， 这些待处理的用户数据将通过高速有线/无线网络从雾层上传至云层， 使用云计算提供更为丰富的资源和应用.

2 雾计算与云计算

雾计算通过部署在网络的边缘， 扩展了云计算的服务范围. 虽然雾计算与云计算使用了许多相同或类似的资源(网络、 计算和存储)， 共享了许多相同的机制和属性(虚拟化、 多租户)， 但雾计算和云计算之间还是存在着一些本质的差异[12]. 为了进一步展示雾计算网络的演化， 我们需要分析一下雾计算与云计算之间的关系和区别.

表 1 列举了雾计算和云计算在目标用户、 工作环境与服务特征3个主要方面的对比. 云计算的服务对象一般是互联网用户， 多数情况下通过IP网络以多跳的方式与用户进行远距离通信. 而雾计算主要服务于移动用户， 每个雾服务器的覆盖范围有限(一般而言， 无线WiFi的通信距离是200 m)， 可与移动用户进行单跳的直连. 在服务特征上， 雾计算与云计算也有着诸多的区别. 不同于云计算位于互联网中集中式的管理模式， 雾计算位于本地网络的边缘， 并采用分散式/分级布署. 在服务能力上， 云计算为用户提供充足、 可扩展的存储能力和计算能力， 而雾计算采用有限的存储、 计算能力， 为用户提供本地化的信息和服务应用. 另一方面， 雾计算比云计算在延迟方面要求低很多， 且地理感知能力强， 支持移动性， 这就使得雾计算更适用于诸如紧急医疗服务、 视频流、 游戏、 现实增强等场景.

表 1 雾计算与云计算的比较

3 雾计算网络演化模型

作为一种新型网络服务模式， 针对雾计算网络演化的研究显得尤为重要： 一方面， 通过分析雾计算网络演化过程， 可以对可能出现的网络演化问题给出指导性的方案； 另一方面， 分析系统的鲁棒性， 可以对雾计算网络遭受攻击时网络的负载情况进行有效评估.

系统初始化： 假设该雾计算网络中含有雾节点的个数为m0， 且雾计算网络中的节点度数至少为1(即不存在孤立节点). 在t0时刻， 雾计算网络中增加一个度为m1的雾节点的概率为p1. 在经过t时刻后， 雾计算环境中将包含N=t+m0个雾节点和m0t+M0条边的网络， 其中M0是初始时刻t0时m0个节点之间存在的边数0

对于初始雾计算网络， 当时间t充分大时， 可以忽略初始网络中的M0条边， 并有m0+t0≈t. 假设时间t是连续的， 且节点的度可以是任意实数. 那么， 当以概率p1将一个度为m的新的雾节点加入到系统中时， 雾节点的i度ki改变的概率可以解释为雾节点i的度的变化率， 从而可以把网络演化近似转化为单个节点演化的平均场方程.

步骤1： 增加雾节点.

将第i个节点在t时刻加入到雾计算网络中， 网络的度变化率k(i,t)可以表示为

步骤2: 增加雾网络的通信链路.

假设在t时刻， 雾计算网络中增加一条边的概率为p2. 若新增边的一个节点从N个雾节点中选取， 选择另一个节点的概率为Πi. 那么k(i,t)的变化率方程为

步骤3: 删除雾节点.

当智能终端离开雾计算网络环境或能量耗尽脱离雾计算环境时， 雾计算网络会删除相应的节点. 假设在t时刻， 雾计算网络中删除一个度为m2的雾节点的概率为p3. 若删除的雾节点以概率Πi与网络中的m2个节点断开连接. 那么k(i,t)的变化率方程为

步骤4: 删雾计算通信链路.

在雾计算环境中， 由于能量或网络带宽等原因， 存在某2个雾节点取消通信的状况. 假设在t时刻， 雾计算网络中删除一条边的概率为p4. 若删除边的一个节点从N个雾节点中随机选取， 选择另一个节点的概率为Πi. 那么k(i,t)的变化率方程为

通过上述对雾计算网络演化模型的分析， 显然有：p1+p2+p3+p4=1. 通过对式(1)～式(4)求和， 可以得到基于复杂网络的雾计算网络演化模型的系统方程

(5)

令P(i,t)为t时刻雾节点i未被删除， 即仍在雾计算网络中的概率. 那么在t时刻雾计算网络中的总度数K(t)可以表示为

此时， 雾计算网络中的总数可以表示为N(t)=(1-p3)t. 因此我们有

P(i,t)的变化率为

由于P(t,t)=1，k(t,t)=m1， 利用差分求解可得出

式(10)左右两边乘以P(i,t)， 并对两边从0到t对i求积分， 得到

依据参考文献[13]中的解法， 方程(11)左边可以变化为

把方程(12)的展开式代入到式(6)～(11)， 令P(t,t)=1，k(t,t)=m1， 可得

从而有

将式(14)代到式(10)， 有

其中,

A=(m1p1+p2-m2p3-p4)(1+p3)·

由于P(t,t)=1，k(t,t)=m1， 当t→∞， 0

此时， 可以得到雾计算的度分布

P(k,t)=

因此， 通过分析可知， 当0

4 仿真实验

为了对本文提出的雾计算BA无标度网络和ER随机网络混合演化模型进行验证， 将针对该模型的演化过程以及雾计算网络的鲁棒性进行分析.

4.1 雾计算演化

首先， 根据雾计算演化模型的4个步骤对网络演化进行可视化实验. 针对初始状态为5个节点的随机化生成网络， 依据模型的4个网络演化步骤， 对不同的网络规模进行可视化数值模拟. 参数取值如下：p1=0,3,p2=0.2,p3=0.05,p4=0.2,m1=3,m2=3. 图 2 为雾计算网络节点从100增长到200时网络的节点分布情况.

图 2 雾计算网络演化过程Fig.2 The evolution of fog computing network

相应的网络的度分布以及度的概率分布在如图 3， 图 4 所示. 从图中可以看出， 随着网络节点数增大， 网络结构呈现出较高的复杂性， 并呈现出较高的无标度网络特性.

图 3 雾计算网络的度分布Fig.3 Degree distribution of fog computing network

图 4 雾计算网络的度的概率分布Fig.4 The probability of degree in fog computing network

4.2 雾计算鲁棒性仿真实验

网络鲁棒性是表现网络拓扑自组织能力的一个重要指标. 通过模拟随机节点攻击和蓄意节点攻击方式[14]， 分析了基于BA无标度网络和ER随机网络混合的雾计算网络拓扑结构的鲁棒性.

随机节点攻击： 随机选取雾计算中的一个节点进行攻击， 使得该节点失去所有的链接.

蓄意节点攻击： 寻找雾计算中一个度最大的节点进行攻击， 使得该节点失去所有的链接. 如果网络中存在多个度值最大的节点时， 随机地从这些节点中选择其中的一个节点进行攻击.

图 5 显示了不同的攻击方式和攻击概率下， 雾计算网络平均路径长度分布情况. 其中， 实验选取的雾计算网络的攻击概率Pattack={0.05,0.10,0.15,…,0.90,0.95,1.00}. 从图5可看出， 随着攻击概率的增加， 雾计算网络平均路径会越来越长. 当攻击概率增加到一个特定的程度时， 平均路径长度改变越来越小， 最终将趋于0. 随着攻击概率Pattack的增加， 相比随机攻击， 雾计算网络能更有效地抵御蓄意攻击.

图 6 展示了在不同的攻击方式和攻击概率下， 雾计算网络的平均度分布情况. 其中， 雾计算网络的攻击概率Pattack={0.05,0.10,0.15,…,0.90,0.95,1.00}. 由图可看出， 随着攻击概率的增加， 网络中平均度越来越小， 且蓄意攻击的平均度减少更为缓慢. 但平均度受到蓄意攻击的影响要比随机攻击更为严重.

图 5 随机攻击与蓄意攻击下不同p值的路径长度影响Fig.5 Average path length under random attack and intentional attack

图 6 随机攻击、 蓄意攻击下不同p值的雾计算网络平均度变化趋势Fig.6 Average degree distribution under random attack and intentional attack

5 结 论

本文系统地介绍了雾计算网络的架构及特征. 通过建立BA无标度网络和ER随机网络混合模型， 分析了雾计算网络演化过程. 分析结果表明， 当p→0， 且p3足够小时， 雾计算网络退化为无标度网络， 服从幂律分布； 当p→1时， 雾计算网络服从指数分布， 近似于ER随机网络； 当0

[1]Framingham M. Worldwide Public Cloud Services Spending Forecast to Double by 2019, According to IDC[EB/OL]. 2016-01-12[2016-09-02]. https:∥www.idc.com/getdoc.jsp?containerId=prUS40960516.

[2]Bonomi F, Milito R, Zhu J, et al. Fog computing and its role in the internet of things[C]. Proceedings of the first edition of the MCC workshop on Mobile cloud computing, ACM, 2012: 13-16.

[3]Stojmenovic I, Wen S, Huang X, et al. An overview of Fog computing and its security issues[J]. Concurrency and Computation: Practice and Experience, 2016, 28(10): 2991-3005.

[4]Sarkar S, Misra S. Theoretical modelling of fog computing: a green computing paradigm to support IoT applications[J]. IET Networks, 2016, 5(2): 23-29.

[5]Mahmud R, Buyya R. Fog computing: a taxonomy, survey and future directions[J]. Arxiv Preprint: 1611.05539, 2016.

[6]Kitanov S, Janevski T. State of the art: Fog computing for 5G networks[C]. 24th Telecommunications Forum (TELFOR), IEEE, 2016: 1-4.

[7]Li Z, Zhou X, Liu Y, et al. A non-cooperative differential game-based security model in fog computing[J]. China Communications, 2017, 14(1): 180-189.

[8]Barabrisi A L. Scale-free networks: a decade and beyond[J]. Science, 2009, 325(5939): 412-413.

[9]Jeong H, Tombor B, Albert R, et al. The large-scale organization of metabolic networks[J]. Nature, 2000, 407(6804): 651-654.

[10]Bonomi F, Milito R, Natarajan P, et al. Fog computing: a platform for internet of things and analytics[M]. New York: Springer International Publishing, 2014.

[11]Aazam M, Huh E N. Fog computing and smart gateway based communication for cloud of things[C]. Future Internet of Things and Cloud (FiCloud), IEEE, 2014: 464-470.

[12]Firdhous M, Ghazali O, Hassan S. Fog computing: will it be the future of cloud computing?[C]. The Third International Conference on Informatics & Applications, Kuala Terengganu, 2014.

[13]Sarshar N, Roychowdhury V. Scale-free and stable structures in complex ad hoc networks[J]. Physical Review E, 2004, 69(2): 026101.

[14]张国华, 张建华, 杨京燕. 基于有向权重图和复杂网络理论的大型电力系统脆弱性评估[J]. 电力自动化设备, 2009, 29(4): 21-26. Zhang Guohua, Zhang Jianhua, Yang Jingyan. Vulnerability assessment of bulk power grid based on weighted directional graph and complex network theory[J]. Electric Power Automation Equipment, 2009, 29(4): 21-26.(in Chinese)

Research on Robustness Fog Computing Based on Complex Network

LI Zhi1, LIU Yan-zhu2, ZHAO Ya-meng3, XU Hai-tao1

(1. School of Computer and Communication Engineering,University of Science and Technology Beijing (USTB), Beijing 100083, China；2. Great Wall Computer Software and Systems Inc., Beijing 100190, China；3. Institute of Remote Sensing and Digital Earth Chinese Academy of Sciences, Beijing 100101, China)

Fog computing extended the cloud computing paradigm from the center of network to the edge. In order to study the robustness of fog computing, the structure characteristics of fog computing were analyzed. A hybrid BA and ER model based on complex network was proposed to improve the network performance of fog computing, and the corresponding formulas were given. The changes of average path length and average degree under the random attack and intentional attack were analyzed in the simulation experiment part. The experimental results show that while 0

fog computing; cloud computing; complex networks; robustness; degree distribution

2016-09-02

国家自然科学基金资助项目(61501026)； 中央高校基本科研业务资助项目(FRF-TP-15-032A1)

李 治(1987-)， 男， 博士生， 主要从事雾计算、 云计算安全的研究.

1673-3193(2017)02-0178-08

TP39

A

10.3969/j.issn.1673-3193.2017.02.015