基于云霧協(xié)同的汽車(chē)健康監(jiān)測(cè)網(wǎng)絡(luò)傳輸資源分配算法研究

魏秀嶺　杜傳祥　呂建新

摘要：本文針對(duì)汽車(chē)健康狀態(tài)監(jiān)測(cè)需求出發(fā)，研究設(shè)計(jì)了云霧計(jì)算協(xié)同汽車(chē)健康監(jiān)測(cè)網(wǎng)絡(luò)系統(tǒng)，提出以蟻群算法為核心的數(shù)據(jù)傳輸路徑的分配。通過(guò)構(gòu)建模擬仿真環(huán)境進(jìn)行驗(yàn)證，表明該算法能適應(yīng)云霧系統(tǒng)網(wǎng)絡(luò)的路勁構(gòu)建的環(huán)境下的動(dòng)態(tài)特性;在運(yùn)算平均吞吐量以及響應(yīng)時(shí)間等方面與SPF最短路徑優(yōu)先算法、BF（Brute Force）暴風(fēng)算法進(jìn)行對(duì)比，其更加適合于云霧協(xié)同的網(wǎng)絡(luò)傳輸環(huán)境使用。

關(guān)鍵詞：云霧協(xié)同;蟻群算法;資源分配

中圖分類號(hào)：U491 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2019）05-0132-02

0 引言

隨著經(jīng)濟(jì)的高速發(fā)展與人民生活水平不斷提升，汽車(chē)保有量呈現(xiàn)幾何級(jí)數(shù)的增加。同時(shí)，汽車(chē)在使用過(guò)程中受外界是行駛環(huán)境、汽車(chē)本身設(shè)計(jì)與構(gòu)造、老化與磨損等諸多因素的影響產(chǎn)生故障在所難免[1]，給人們的生產(chǎn)生活的出行安全帶來(lái)了嚴(yán)重的影響。傳統(tǒng)的汽車(chē)健康狀態(tài)研究已經(jīng)不能滿足當(dāng)前汽車(chē)安全運(yùn)用要求，而且在研究深度和內(nèi)容上也應(yīng)有所改變。

同時(shí)，隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的發(fā)展，使得物聯(lián)網(wǎng)技術(shù)的不斷升級(jí)，在這樣的大趨勢(shì)下，人們對(duì)數(shù)據(jù)信息提取與處理、智能優(yōu)化和實(shí)時(shí)決策等很多方面有了新的要求，傳統(tǒng)的并行技術(shù)等已不能為滿足人類日益增長(zhǎng)的發(fā)展需要。云計(jì)算、霧計(jì)算等產(chǎn)生以及應(yīng)用，正是契合了這種需求，云霧協(xié)同作為一種新型的并行計(jì)算技術(shù)也出現(xiàn)在網(wǎng)絡(luò)上，使得物聯(lián)網(wǎng)技術(shù)逐步被應(yīng)用至汽車(chē)健康狀態(tài)進(jìn)行監(jiān)測(cè)提供了發(fā)展與應(yīng)用的契機(jī)。

1 云霧計(jì)算協(xié)同汽車(chē)健康監(jiān)測(cè)網(wǎng)絡(luò)系統(tǒng)的構(gòu)建

云計(jì)算（Cloud Computing），是指通過(guò)互聯(lián)網(wǎng)連接共享基礎(chǔ)架構(gòu)的超級(jí)計(jì)算模式，通過(guò)互聯(lián)網(wǎng)為用戶提供各種存儲(chǔ)和計(jì)算資源。然而，云計(jì)算無(wú)法滿足位置感知、低延時(shí)、移動(dòng)性支持、地理分布等[2]。而霧計(jì)算的提出彌補(bǔ)了云計(jì)算的不足，它采用分布式的架構(gòu)的網(wǎng)絡(luò)邊緣計(jì)算，在網(wǎng)絡(luò)邊緣設(shè)備中實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)、數(shù)據(jù)處理和應(yīng)用服務(wù)。云計(jì)算的這依賴于服務(wù)器，而霧計(jì)算中主要依賴本地設(shè)備實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)。根據(jù)霧計(jì)算智能前端化思想，構(gòu)建云霧計(jì)算協(xié)同汽車(chē)網(wǎng)絡(luò)系統(tǒng)。分為三個(gè)層次的結(jié)構(gòu)：

（1）上層為云計(jì)算中心，主要是由服務(wù)器和衛(wèi)星定位系統(tǒng)構(gòu)成。（2）中間層為霧層由汽車(chē)健康監(jiān)測(cè)網(wǎng)絡(luò)系統(tǒng)邊緣的霧服務(wù)器組成，以此實(shí)現(xiàn)提供數(shù)據(jù)緩存、本地化計(jì)算等功能，滿足了云霧計(jì)算協(xié)同的交互式汽車(chē)健康監(jiān)測(cè)網(wǎng)絡(luò)系統(tǒng)的高流量和低延遲的需求。（3）下層為傳感器和移動(dòng)終端層，由車(chē)與車(chē)、車(chē)與人、車(chē)與網(wǎng)絡(luò)、車(chē)與路測(cè)單元等構(gòu)成，實(shí)現(xiàn)汽車(chē)健康基礎(chǔ)數(shù)據(jù)的采集、處理與傳輸。

2 汽車(chē)健康監(jiān)測(cè)網(wǎng)絡(luò)傳輸路徑分配算法

2.1 蟻群算法的模型

蟻群算法（Ant Colony Optimization，ACO），是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法[3]。假設(shè)：初始時(shí)刻時(shí)，只螞蟻組成蟻群以為起始地點(diǎn)，為目標(biāo)地點(diǎn)，各條路徑上的信息素量相等，設(shè)τij（0）=C（C為常數(shù)），螞蟻（=1，2，3，…，m）根據(jù)各條路徑上的信息量濃度選擇路徑，α為信息素啟發(fā)系數(shù)，β為期望啟發(fā)系數(shù)。螞蟻從選擇的轉(zhuǎn)移概率為，其概率公式如（1）所示：

式中：--信息素?cái)?shù)量，為t時(shí)刻邊上信息素的強(qiáng)度;--啟發(fā)函數(shù)，，表示節(jié)點(diǎn)和節(jié)點(diǎn)間的距離。

2.2 信息素更新

在應(yīng)用蟻群算法過(guò)程中，為了使螞蟻運(yùn)動(dòng)不重復(fù)路徑，建立禁忌表tabu（k），將已通過(guò)的路徑加入至tabu（k）[4]。同時(shí)，為避免信息素含量過(guò)多影響啟發(fā)信息作用，完一步或完成對(duì)所有備選節(jié)點(diǎn)的遍歷后，對(duì)所經(jīng)過(guò)節(jié)點(diǎn)依照規(guī)則對(duì)路徑上信息素進(jìn)行更新。allowedk表示螞蟻可以選擇的下一個(gè)節(jié)點(diǎn)，尋找tabu（k）外的其他的最優(yōu)路徑，即allowedk={C-tabu（k）}，具體的更新規(guī)則如下：

（1）局部更新規(guī)則。當(dāng)一只螞蟻選擇一個(gè)節(jié)點(diǎn)走完徑路，依據(jù)公式（2）進(jìn)行局部更新，是初始信息素濃度值。

（2）全局更新規(guī)則。若第只螞蟻經(jīng)過(guò)后完成循環(huán)，依據(jù)公式（3）進(jìn)行全局信息素更新。為全局揮發(fā)因子，為路徑信息素增量，為全局最優(yōu)路徑：

2.3 算法工作步驟

（1）ACO算法初始化，設(shè)定、、ρ、Q、ω等參數(shù)，設(shè)置ACO算法最大迭代次數(shù)的結(jié)束條件，設(shè)置各個(gè)節(jié)點(diǎn)的信息素值。（2）對(duì)任務(wù)信息參數(shù)化以及計(jì)算狀態(tài)轉(zhuǎn)移頻率;（3）根據(jù)轉(zhuǎn)移概率矩陣，選擇第k只螞蟻并移動(dòng)L步，并計(jì)算概率選擇下一個(gè)節(jié)點(diǎn)。（4）進(jìn)行信息素局部更新，第k只螞蟻?zhàn)哌^(guò)信息素的值，研究k≧螞蟻總數(shù)與否。如果不滿足，返回步驟（3）。（5）依據(jù)第只螞蟻經(jīng)過(guò)后完成循環(huán)帶來(lái)的節(jié)點(diǎn)信息素，概率選擇下一跳節(jié)點(diǎn)，并按公式（3）進(jìn)行全局信息素更新。（6）在使用循跡信息素時(shí)，ACO算法至最大迭代次數(shù)則算法結(jié)束，任務(wù)分配完成，繼續(xù)進(jìn)行下一個(gè)任務(wù)。否則，清空tabu（k），跳至步驟（3）查找。（7）重復(fù)步驟（4）-（6），滿足預(yù)設(shè)迭代次數(shù)釋放資源，則得出路徑最優(yōu)解。

3 實(shí)驗(yàn)仿真

為了驗(yàn)證蟻群算法在云霧計(jì)算協(xié)同汽車(chē)健康監(jiān)測(cè)網(wǎng)絡(luò)系統(tǒng)的傳輸路徑的優(yōu)化應(yīng)用，此次模擬仿真采用CloudSim[5]進(jìn)行，對(duì)蟻群算法結(jié)果進(jìn)行了分析，以檢查算法在云霧計(jì)算協(xié)同網(wǎng)格環(huán)境中的運(yùn)行情況。對(duì)蟻群算法的參數(shù)進(jìn)行設(shè)置，取值為=0.2，β=0.3，ρ= 0.7，ρmin=0.3，Q=100，ω=1.2。

為了驗(yàn)證ACO算法在云霧計(jì)算協(xié)同汽車(chē)健康監(jiān)測(cè)網(wǎng)絡(luò)系統(tǒng)的傳輸性能，與SPF最短路徑優(yōu)先算法、BF暴風(fēng)算法進(jìn)行了比較分析，ACO算法的平均吞吐量在參數(shù)逐漸增加的條件下效果較為明顯，能夠有效的動(dòng)態(tài)調(diào)整云霧協(xié)同網(wǎng)絡(luò)傳輸路徑選擇和云霧協(xié)同網(wǎng)絡(luò)傳輸環(huán)境下的效率，如圖1所示。同時(shí)，算法查詢響應(yīng)時(shí)間比較，ACO算法的時(shí)間延遲性最小，響應(yīng)速度與SPF最短路徑優(yōu)先算法、BF暴風(fēng)算法相比較高，SPF最短路徑優(yōu)先算法的分組路由的時(shí)間延遲最大，而B(niǎo)F算法的性能接近于ACO算法;因此，ACO算法在能夠迅速、準(zhǔn)確地訪問(wèn)云霧計(jì)算協(xié)同汽車(chē)健康監(jiān)測(cè)網(wǎng)絡(luò)系統(tǒng)所需訪問(wèn)的數(shù)據(jù)庫(kù)，同等條件下，傳輸速率與其他兩種算法快，有效實(shí)現(xiàn)減少和控制局部最優(yōu)解及收斂速度不穩(wěn)定問(wèn)題，如圖2所示。

實(shí)驗(yàn)結(jié)果表明，蟻群算法在云霧協(xié)同網(wǎng)絡(luò)的構(gòu)建具有功能，低執(zhí)行時(shí)間和成本，同時(shí)能讓系統(tǒng)負(fù)載始終保持一個(gè)均衡的狀態(tài)，能夠以更快的速度收斂到全局最優(yōu)解。

4 結(jié)語(yǔ)

本文提出將蟻群算法用于解決云霧協(xié)同網(wǎng)絡(luò)的汽車(chē)健康監(jiān)測(cè)資源分配問(wèn)題。針對(duì)云霧協(xié)同網(wǎng)絡(luò)傳輸環(huán)境特點(diǎn)態(tài)地搜尋并分配傳輸路徑。并使用CloudSim進(jìn)行仿真，結(jié)果表明ACO算法能夠有效地云霧協(xié)同網(wǎng)絡(luò)環(huán)境中傳輸路徑分配的工作，在平均吞吐量與查詢相應(yīng)時(shí)間等方面具有良好的表現(xiàn)，驗(yàn)證了ACO算法的在云霧協(xié)同網(wǎng)絡(luò)路徑傳輸?shù)挠行浴?/p>

參考文獻(xiàn)

[1] 宋留勇，王銳，周永旺，等.動(dòng)態(tài)城市交通網(wǎng)絡(luò)優(yōu)化模型研究及算法設(shè)計(jì)[J].測(cè)繪科學(xué)，2011，36（1）：134-136.

[2] 陳迎欣.基于改進(jìn)蟻群算法的車(chē)輛路徑優(yōu)化問(wèn)題研究[J].計(jì)算機(jī)應(yīng)用研究，2012，29（6）：2031-2034.

[3] 汪采萍.蟻群算法的應(yīng)用研究[D].合肥：合肥工業(yè)大學(xué)，2007.

[4] 左利云，曹志波.云計(jì)算中調(diào)度問(wèn)題研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2012（11）：4023-4027.

[5] 王詔遠(yuǎn)，李天瑞，易修文.基于MapReduce的蟻群優(yōu)化算法實(shí)現(xiàn)方法[J].計(jì)算機(jī)科學(xué)，2014，41（7）：261-265.