基于復雜網(wǎng)絡的霧計算網(wǎng)絡魯棒性研究

李 治， 柳妍珠， 趙亞萌， 許海濤

(1. 北京科技大學 計算機與通信工程學院， 北京 100083； 2. 長城計算機軟件與系統(tǒng)有限公司， 北京 100190；3. 中國科學院遙感與數(shù)字地球研究所， 北京 100101)

基于復雜網(wǎng)絡的霧計算網(wǎng)絡魯棒性研究

李 治1， 柳妍珠2， 趙亞萌3， 許海濤1

(1. 北京科技大學 計算機與通信工程學院， 北京 100083； 2. 長城計算機軟件與系統(tǒng)有限公司， 北京 100190；3. 中國科學院遙感與數(shù)字地球研究所， 北京 100101)

霧計算擴大了云計算的網(wǎng)絡模式， 將網(wǎng)絡服務由網(wǎng)絡中心擴展到了網(wǎng)絡邊緣. 為研究霧計算網(wǎng)絡的魯棒性， 通過分析霧計算網(wǎng)絡系統(tǒng)結構特征， 設計了基于復雜網(wǎng)絡的BA無標度網(wǎng)絡和ER隨機網(wǎng)絡混合模型， 并給出了相應的公式. 針對隨機攻擊和蓄意攻擊兩種情況， 對霧計算網(wǎng)絡的平均路徑長度以及平均度進行仿真實驗. 實驗結果表明， 當0

霧計算； 云計算； 復雜網(wǎng)絡； 魯棒性； 度分布

0 引 言

隨著移動智能設備以及無線通信技術的發(fā)展， 我們已經(jīng)進入到了一個全球互聯(lián)的數(shù)字化信息社會新紀元. IDC的研究報告顯示， 2016年全世界將有大約20億， 超過全球人口總數(shù)1/4數(shù)量的用戶通過移動設備訪問互聯(lián)網(wǎng)[1]. 移動智能終端的發(fā)展催生出大量的應用， 如社交網(wǎng)絡、 導航系統(tǒng)、 物聯(lián)網(wǎng)應用、 智能家居等， 它們的出現(xiàn)顯著改變了人們的生活方式. 云計算為這些應用的數(shù)據(jù)處理提供了一個很好的解決方案. 然而， 隨著越來越多的智能設備接入， 其產(chǎn)生的移動通信數(shù)據(jù)量成爆炸性增長， 這給網(wǎng)絡環(huán)境和帶寬帶來了新的挑戰(zhàn). 一般而言， 云計算數(shù)據(jù)中心與移動設備之間的物理距離很遠， 用戶將海量數(shù)據(jù)發(fā)送至云端或者從云端返回數(shù)據(jù)給用戶均需要耗費較長的時間. 因此， 從實時交互的角度出發(fā)， 把所有的原始數(shù)據(jù)發(fā)送到云數(shù)據(jù)中心進行處理并不是一種高效的選擇. 為了解決云計算易延遲、 通信開銷大等問題， 2012年思科提出了霧計算的概念[2]. 不同于云計算的集中式計算模式， 霧計算作為一種新型的分布式計算模式更符合互聯(lián)網(wǎng)“去中心化”的特征： 用戶數(shù)據(jù)無需上傳到云中， 在本地智能設備中即可進行處理. 霧計算通過將性能相對較弱， 位置相對更為分散的各類計算資源進行集成， 將數(shù)據(jù)、 數(shù)據(jù)處理以及應用程序集中在網(wǎng)絡的邊緣設備中， 具有低延遲、 地理分布廣泛、 位置感知、 適應移動性應用等特點[3-4]. 因此， 霧計算是解決連接互聯(lián)網(wǎng)中設備數(shù)量不斷增加問題的一種有效途徑. 這種擴展的云計算網(wǎng)絡模式無疑將推動物聯(lián)網(wǎng)、 云計算等技術的高速發(fā)展. 然而霧計算網(wǎng)絡的規(guī)劃、 建設、 運營和管理均需要大量的科學理論、 模型和方法的支撐. 目前， 已有一些學者針對這種新型網(wǎng)絡計算范式中體系結構[5]、 網(wǎng)絡應用[6]、 系統(tǒng)安全[7]等方面開展了研究. 其中， 網(wǎng)絡魯棒性研究在霧計算網(wǎng)絡實踐上具有重要意義. 舉例來說， 當霧計算通信網(wǎng)絡節(jié)點發(fā)生故障時， 網(wǎng)絡中的一些通信鏈路將可能發(fā)生中斷， 進而諸如網(wǎng)絡節(jié)點之間的最短路徑、 鏈路負載、 擁塞發(fā)生條件等網(wǎng)絡屬性都將發(fā)生改變， 必然會影響整個網(wǎng)絡數(shù)據(jù)的傳輸過程.

本文基于BA無標度網(wǎng)絡[8]和ER隨機網(wǎng)絡[9]混合模型開展了霧計算網(wǎng)絡演化過程的研究. 通過分析隨機攻擊、 蓄意攻擊對霧計算網(wǎng)絡結構的影響， 給出了較為精確的公式對其網(wǎng)絡結構和功能的變化進行描述. 所提公式為分析霧計算網(wǎng)絡魯棒性提供了一個通用框架， 對保障數(shù)據(jù)安全， 構建抗隨機攻擊、 蓄意攻擊的霧計算網(wǎng)絡結構有著指導意義.

1 霧計算系統(tǒng)架構

作為一種云計算延伸的虛擬平臺， 霧計算通常位于終端用戶和云計算數(shù)據(jù)中心之間， 提供了一種低延遲、 低功效、 低網(wǎng)絡數(shù)據(jù)流量的服務. 一般而言， 霧計算網(wǎng)絡結構可以分成3層[10]， 如圖 1 所示.

圖 1 霧計算結構模型Fig.1 The fog computing architecture

用戶層： 作為霧計算3層模型的最底層， 用戶層由數(shù)量眾多的智能終端與這些智能終端產(chǎn)生的海量數(shù)據(jù)所構成. 利用諸如WiFi， 藍牙等短距離通信方式， 霧計算用戶將智能終端與高層霧節(jié)點連接， 享受霧計算網(wǎng)絡提供的服務[11].

霧層： 位于網(wǎng)絡中間的霧層部署在地理上分散的霧服務器上， 為智能終端和云之間搭起了橋梁. 每個霧服務器是高度虛擬化的計算系統(tǒng)， 類似輕量級的云服務器. 通過配備大量的數(shù)據(jù)存儲， 計算和無線通信設備， 對用戶層上傳的數(shù)據(jù)進行智能化處理.

云層： 模型的最高層為云層. 由于霧設備的處理能力有限， 當有任務需要更多的計算資源時， 這些待處理的用戶數(shù)據(jù)將通過高速有線/無線網(wǎng)絡從霧層上傳至云層， 使用云計算提供更為豐富的資源和應用.

2 霧計算與云計算

霧計算通過部署在網(wǎng)絡的邊緣， 擴展了云計算的服務范圍. 雖然霧計算與云計算使用了許多相同或類似的資源(網(wǎng)絡、 計算和存儲)， 共享了許多相同的機制和屬性(虛擬化、 多租戶)， 但霧計算和云計算之間還是存在著一些本質(zhì)的差異[12]. 為了進一步展示霧計算網(wǎng)絡的演化， 我們需要分析一下霧計算與云計算之間的關系和區(qū)別.

表 1 列舉了霧計算和云計算在目標用戶、 工作環(huán)境與服務特征3個主要方面的對比. 云計算的服務對象一般是互聯(lián)網(wǎng)用戶， 多數(shù)情況下通過IP網(wǎng)絡以多跳的方式與用戶進行遠距離通信. 而霧計算主要服務于移動用戶， 每個霧服務器的覆蓋范圍有限(一般而言， 無線WiFi的通信距離是200 m)， 可與移動用戶進行單跳的直連. 在服務特征上， 霧計算與云計算也有著諸多的區(qū)別. 不同于云計算位于互聯(lián)網(wǎng)中集中式的管理模式， 霧計算位于本地網(wǎng)絡的邊緣， 并采用分散式/分級布署. 在服務能力上， 云計算為用戶提供充足、 可擴展的存儲能力和計算能力， 而霧計算采用有限的存儲、 計算能力， 為用戶提供本地化的信息和服務應用. 另一方面， 霧計算比云計算在延遲方面要求低很多， 且地理感知能力強， 支持移動性， 這就使得霧計算更適用于諸如緊急醫(yī)療服務、 視頻流、 游戲、 現(xiàn)實增強等場景.

表 1 霧計算與云計算的比較

3 霧計算網(wǎng)絡演化模型

作為一種新型網(wǎng)絡服務模式， 針對霧計算網(wǎng)絡演化的研究顯得尤為重要： 一方面， 通過分析霧計算網(wǎng)絡演化過程， 可以對可能出現(xiàn)的網(wǎng)絡演化問題給出指導性的方案； 另一方面， 分析系統(tǒng)的魯棒性， 可以對霧計算網(wǎng)絡遭受攻擊時網(wǎng)絡的負載情況進行有效評估.

系統(tǒng)初始化： 假設該霧計算網(wǎng)絡中含有霧節(jié)點的個數(shù)為m0， 且霧計算網(wǎng)絡中的節(jié)點度數(shù)至少為1(即不存在孤立節(jié)點). 在t0時刻， 霧計算網(wǎng)絡中增加一個度為m1的霧節(jié)點的概率為p1. 在經(jīng)過t時刻后， 霧計算環(huán)境中將包含N=t+m0個霧節(jié)點和m0t+M0條邊的網(wǎng)絡， 其中M0是初始時刻t0時m0個節(jié)點之間存在的邊數(shù)0

對于初始霧計算網(wǎng)絡， 當時間t充分大時， 可以忽略初始網(wǎng)絡中的M0條邊， 并有m0+t0≈t. 假設時間t是連續(xù)的， 且節(jié)點的度可以是任意實數(shù). 那么， 當以概率p1將一個度為m的新的霧節(jié)點加入到系統(tǒng)中時， 霧節(jié)點的i度ki改變的概率可以解釋為霧節(jié)點i的度的變化率， 從而可以把網(wǎng)絡演化近似轉(zhuǎn)化為單個節(jié)點演化的平均場方程.

步驟1： 增加霧節(jié)點.

將第i個節(jié)點在t時刻加入到霧計算網(wǎng)絡中， 網(wǎng)絡的度變化率k(i,t)可以表示為

步驟2: 增加霧網(wǎng)絡的通信鏈路.

假設在t時刻， 霧計算網(wǎng)絡中增加一條邊的概率為p2. 若新增邊的一個節(jié)點從N個霧節(jié)點中選取， 選擇另一個節(jié)點的概率為Πi. 那么k(i,t)的變化率方程為

步驟3: 刪除霧節(jié)點.

當智能終端離開霧計算網(wǎng)絡環(huán)境或能量耗盡脫離霧計算環(huán)境時， 霧計算網(wǎng)絡會刪除相應的節(jié)點. 假設在t時刻， 霧計算網(wǎng)絡中刪除一個度為m2的霧節(jié)點的概率為p3. 若刪除的霧節(jié)點以概率Πi與網(wǎng)絡中的m2個節(jié)點斷開連接. 那么k(i,t)的變化率方程為

步驟4: 刪霧計算通信鏈路.

在霧計算環(huán)境中， 由于能量或網(wǎng)絡帶寬等原因， 存在某2個霧節(jié)點取消通信的狀況. 假設在t時刻， 霧計算網(wǎng)絡中刪除一條邊的概率為p4. 若刪除邊的一個節(jié)點從N個霧節(jié)點中隨機選取， 選擇另一個節(jié)點的概率為Πi. 那么k(i,t)的變化率方程為

通過上述對霧計算網(wǎng)絡演化模型的分析， 顯然有：p1+p2+p3+p4=1. 通過對式(1)～式(4)求和， 可以得到基于復雜網(wǎng)絡的霧計算網(wǎng)絡演化模型的系統(tǒng)方程

(5)

令P(i,t)為t時刻霧節(jié)點i未被刪除， 即仍在霧計算網(wǎng)絡中的概率. 那么在t時刻霧計算網(wǎng)絡中的總度數(shù)K(t)可以表示為

此時， 霧計算網(wǎng)絡中的總數(shù)可以表示為N(t)=(1-p3)t. 因此我們有

P(i,t)的變化率為

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

式(10)左右兩邊乘以P(i,t)， 并對兩邊從0到t對i求積分， 得到

依據(jù)參考文獻[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無標度網(wǎng)絡和ER隨機網(wǎng)絡混合演化模型進行驗證， 將針對該模型的演化過程以及霧計算網(wǎng)絡的魯棒性進行分析.

4.1 霧計算演化

首先， 根據(jù)霧計算演化模型的4個步驟對網(wǎng)絡演化進行可視化實驗. 針對初始狀態(tài)為5個節(jié)點的隨機化生成網(wǎng)絡， 依據(jù)模型的4個網(wǎng)絡演化步驟， 對不同的網(wǎng)絡規(guī)模進行可視化數(shù)值模擬. 參數(shù)取值如下：p1=0,3,p2=0.2,p3=0.05,p4=0.2,m1=3,m2=3. 圖 2 為霧計算網(wǎng)絡節(jié)點從100增長到200時網(wǎng)絡的節(jié)點分布情況.

圖 2 霧計算網(wǎng)絡演化過程Fig.2 The evolution of fog computing network

相應的網(wǎng)絡的度分布以及度的概率分布在如圖 3， 圖 4 所示. 從圖中可以看出， 隨著網(wǎng)絡節(jié)點數(shù)增大， 網(wǎng)絡結構呈現(xiàn)出較高的復雜性， 并呈現(xiàn)出較高的無標度網(wǎng)絡特性.

圖 3 霧計算網(wǎng)絡的度分布Fig.3 Degree distribution of fog computing network

圖 4 霧計算網(wǎng)絡的度的概率分布Fig.4 The probability of degree in fog computing network

4.2 霧計算魯棒性仿真實驗

網(wǎng)絡魯棒性是表現(xiàn)網(wǎng)絡拓撲自組織能力的一個重要指標. 通過模擬隨機節(jié)點攻擊和蓄意節(jié)點攻擊方式[14]， 分析了基于BA無標度網(wǎng)絡和ER隨機網(wǎng)絡混合的霧計算網(wǎng)絡拓撲結構的魯棒性.

隨機節(jié)點攻擊： 隨機選取霧計算中的一個節(jié)點進行攻擊， 使得該節(jié)點失去所有的鏈接.

蓄意節(jié)點攻擊： 尋找霧計算中一個度最大的節(jié)點進行攻擊， 使得該節(jié)點失去所有的鏈接. 如果網(wǎng)絡中存在多個度值最大的節(jié)點時， 隨機地從這些節(jié)點中選擇其中的一個節(jié)點進行攻擊.

圖 5 顯示了不同的攻擊方式和攻擊概率下， 霧計算網(wǎng)絡平均路徑長度分布情況. 其中， 實驗選取的霧計算網(wǎng)絡的攻擊概率Pattack={0.05,0.10,0.15,…,0.90,0.95,1.00}. 從圖5可看出， 隨著攻擊概率的增加， 霧計算網(wǎng)絡平均路徑會越來越長. 當攻擊概率增加到一個特定的程度時， 平均路徑長度改變越來越小， 最終將趨于0. 隨著攻擊概率Pattack的增加， 相比隨機攻擊， 霧計算網(wǎng)絡能更有效地抵御蓄意攻擊.

圖 6 展示了在不同的攻擊方式和攻擊概率下， 霧計算網(wǎng)絡的平均度分布情況. 其中， 霧計算網(wǎng)絡的攻擊概率Pattack={0.05,0.10,0.15,…,0.90,0.95,1.00}. 由圖可看出， 隨著攻擊概率的增加， 網(wǎng)絡中平均度越來越小， 且蓄意攻擊的平均度減少更為緩慢. 但平均度受到蓄意攻擊的影響要比隨機攻擊更為嚴重.

圖 5 隨機攻擊與蓄意攻擊下不同p值的路徑長度影響Fig.5 Average path length under random attack and intentional attack

圖 6 隨機攻擊、 蓄意攻擊下不同p值的霧計算網(wǎng)絡平均度變化趨勢Fig.6 Average degree distribution under random attack and intentional attack

5 結 論

本文系統(tǒng)地介紹了霧計算網(wǎng)絡的架構及特征. 通過建立BA無標度網(wǎng)絡和ER隨機網(wǎng)絡混合模型， 分析了霧計算網(wǎng)絡演化過程. 分析結果表明， 當p→0， 且p3足夠小時， 霧計算網(wǎng)絡退化為無標度網(wǎng)絡， 服從冪律分布； 當p→1時， 霧計算網(wǎng)絡服從指數(shù)分布， 近似于ER隨機網(wǎng)絡； 當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]張國華, 張建華, 楊京燕. 基于有向權重圖和復雜網(wǎng)絡理論的大型電力系統(tǒng)脆弱性評估[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)； 中央高?；究蒲袠I(yè)務資助項目(FRF-TP-15-032A1)

李 治(1987-)， 男， 博士生， 主要從事霧計算、 云計算安全的研究.

1673-3193(2017)02-0178-08

TP39

A

10.3969/j.issn.1673-3193.2017.02.015