基于離散粒子群的Web前端緩存協(xié)作任務(wù)優(yōu)化分配方法

周沭玲 侯海平

（1.合肥財經(jīng)職業(yè)學(xué)院人工智能學(xué)院，安徽合肥 230601；2.安徽財貿(mào)職業(yè)學(xué)院信息工程學(xué)院，安徽合肥 230061）

引言

大規(guī)模的冗余數(shù)據(jù)量，對網(wǎng)絡(luò)節(jié)點的緩存與協(xié)作帶來大量的資源損耗，這直接導(dǎo)致網(wǎng)絡(luò)傳輸效率低，網(wǎng)絡(luò)節(jié)點的平均時延久居不下等現(xiàn)象[1]。為從根本上解決網(wǎng)絡(luò)體系的通信安全問題，以信息為中心，探究Web 前端的緩存協(xié)作任務(wù)優(yōu)化分配策略。在現(xiàn)有的相關(guān)研究中，左亞兵在無線網(wǎng)絡(luò)的蜂窩架構(gòu)中，通過頻譜資源的限制與回程容量，設(shè)計一種異構(gòu)網(wǎng)絡(luò)，并在用戶位置分布中，通過請求內(nèi)容的偏好限制以及節(jié)點空間的存儲效率，建立一個有關(guān)于用戶關(guān)聯(lián)聯(lián)合優(yōu)化問題的數(shù)學(xué)模型，并最小化函數(shù)時延設(shè)計一種任務(wù)分配的改進策略[2]。張秋平通過移動邊緣計算的方式，改變通信設(shè)備的存儲與計算資源，以長距離傳輸和快速響應(yīng)為核心，解決有效資源和設(shè)備負載不均衡的問題[3]。面對多邊緣設(shè)備的協(xié)同合作問題，該方法可以提高任務(wù)緩存機制的聯(lián)合優(yōu)化，并基于偏好匹配算法，減少任務(wù)分配的整體執(zhí)行時間，從而降低了網(wǎng)絡(luò)時延。張歡以無線接入網(wǎng)絡(luò)的硬件設(shè)施為核心，設(shè)計一種邊緣緩存的用戶偏好預(yù)測與度量算法[4]。在網(wǎng)絡(luò)設(shè)備的拓撲關(guān)系中，結(jié)合不同基站的相關(guān)性，降低冗余文件的內(nèi)存，并利用強化學(xué)習(xí)策略優(yōu)化Q-learning 算法，提高前端緩存協(xié)作的效率，同時刪除任務(wù)分配的冗余數(shù)據(jù)。上述方法降低不同類型網(wǎng)絡(luò)任務(wù)分配或數(shù)據(jù)傳輸時的時延，但是由于Web 前端緩存任務(wù)中冗余數(shù)據(jù)較多，因此其在優(yōu)化Web 前端緩存協(xié)作任務(wù)分配效果方面存在一定的局限性。基于此，本文設(shè)計一種基于離散粒子群的Web前端緩存協(xié)作任務(wù)優(yōu)化分配方法。

1 Web前端緩存協(xié)作任務(wù)優(yōu)化分配方法設(shè)計

1.1 規(guī)劃Web前端緩存訪問路徑

網(wǎng)內(nèi)的緩存協(xié)作是Web 前端網(wǎng)絡(luò)與傳統(tǒng)網(wǎng)絡(luò)最大的不同之處，也是該網(wǎng)絡(luò)的重要特征。在提高數(shù)據(jù)傳輸效率，減少服務(wù)器負載的同時，該網(wǎng)絡(luò)任務(wù)的優(yōu)化分配方法還可以為用戶提供更好的體驗，并總結(jié)了網(wǎng)絡(luò)結(jié)構(gòu)[5]。Web前端網(wǎng)絡(luò)的內(nèi)容訪問路徑如圖1所示。

圖1 緩存訪問路徑

如圖1所示，在緩存訪問路徑上，在A1-An 之間存在n個相鄰的節(jié)點，可以設(shè)置節(jié)點的編號，并保證路徑中的其余節(jié)點均以1-n編碼。在上一條節(jié)點的轉(zhuǎn)發(fā)請求中，依次設(shè)置訪問權(quán)限，并將其添加到緩存訪問路徑中，添加節(jié)點為IN。連接訪問權(quán)限后，訪問路徑就會存在一個轉(zhuǎn)換機制[6-7]。在訪問機制以后的路徑，可以定義訪問路徑以外的所有節(jié)點請求，包括緩存內(nèi)容的對象節(jié)點。在緩存模型與緩存方案中，還存在一些系統(tǒng)緩存的優(yōu)化問題，包括系統(tǒng)建模的拓撲優(yōu)化與共享問題。在現(xiàn)有的拓撲結(jié)構(gòu)中，線性級聯(lián)結(jié)構(gòu)是一種以層次結(jié)構(gòu)與網(wǎng)狀結(jié)構(gòu)為核心的關(guān)聯(lián)性請求模型，各節(jié)點之間的協(xié)作關(guān)系十分簡單。而在這些陌生的拓撲模型中，對緩存節(jié)點的透明化管理是最重要的一部分。很多自主命名區(qū)域內(nèi)都與緩存應(yīng)用之間建立私有協(xié)議，緩存區(qū)域與應(yīng)用軟件之間沒有特殊的關(guān)聯(lián)，以至于緩存協(xié)作對上層的應(yīng)用軟件而言是一種屬性透明的基礎(chǔ)服務(wù)。在傳統(tǒng)的應(yīng)用中，緩存網(wǎng)絡(luò)是通過先驗協(xié)同運算得到的樹狀層次結(jié)構(gòu)，而在Web 前端的緩存網(wǎng)絡(luò)中，則以緩存節(jié)點為中心，呈現(xiàn)出一種抽象的泛化特征。緩存節(jié)點不再停留在一個固定的地區(qū)，以高度動態(tài)的網(wǎng)絡(luò)環(huán)境為中心，保持已有的應(yīng)用性，是整個緩存內(nèi)容的具象化產(chǎn)物[8]。在緩存內(nèi)容文件中，則會依據(jù)整個文件的操作速度，實現(xiàn)一種線性的結(jié)構(gòu)，將所有前端協(xié)作的內(nèi)容全部整合成大小不同的分塊，并在更加細粒度化的對象體系中，以不同的訪問頻率，實現(xiàn)文件傳輸操作。這樣一方面可以降低用戶的訪問時延，另一方面還可以優(yōu)化服務(wù)器負載，減少帶寬消耗。

1.2 基于離散粒子群建立任務(wù)優(yōu)化分配模型

為解決任務(wù)優(yōu)化分配的問題，可以使用離散粒子群優(yōu)化算法，確定模糊矩陣中粒子的最佳位置與速度。首先需要初始化粒子的初始位置與速度，設(shè)為(X0,V0)，其中X0表示粒子的初始位置，V0表示粒子的初始速度[9-10]。在不斷迭代的過程中，建立位置與速度的矩陣，矩陣中的元素需要滿足：

式中，(Xi,Vi)表示時間為i 時的位置與速度。計算粒子群的更新坐標(biāo)，檢測矩陣內(nèi)的粒子是否清零，若可以直接對矩陣進行歸一化計算，則直接負值清零，若不能歸一化計算，則需要通過最大數(shù)采樣法，將粒子更新位置的矩陣模糊化處理，得到位置的可行解[11-12]。離散空間的離子群優(yōu)化算法中，有關(guān)于離散變量的排列優(yōu)化方法是左右速度位置更新的最佳變量。在布爾運算中，將連續(xù)空間的修改方案作為算法運算的迭代結(jié)果。在分配模型中加入擾動因子，使其作為最大的參數(shù)，參與種群的多樣性，可以得到修改后的位置更新矩陣：

式中，Xm表示時間為m時的粒子位置最優(yōu)解；xnn表示在第n個最大采樣法中得到的第n個粒子的更新坐標(biāo)；x1i表示粒子i時的位置變動值。通過重復(fù)迭代的方式，可以求出離散粒子群算法的全局最優(yōu)解，并基于排序優(yōu)化問題，獲取替代向量以及離散矢量空間中的最優(yōu)參數(shù)。在慣性的部分添加代表社會認知的權(quán)重，可以及時增加粒子群的多樣性，避免參數(shù)過早地進入局部極值的收斂中[13]。當(dāng)粒子群的多樣性減少時，可以同步降低算法的收斂速度，并降低局部極值的解。通過線性階段的算法收斂與精度收斂，可以將兩個不同的概率作為粒子的相似性，自適應(yīng)調(diào)整后可以得到粒子的系數(shù)概率公式為：

式中，Pnm表示粒子相似性下的自適應(yīng)調(diào)整概率；Pi表示第j個粒子的種群大?。籇f表示粒子的總位數(shù)。通過粒子維度的大小，計算每個粒子的總位數(shù)，可以得到：

通過目標(biāo)函數(shù)的部署，以及節(jié)點請求對象在任務(wù)優(yōu)化分配中的緩存需求，可以計算節(jié)點的位置路徑，得到替代節(jié)點的目標(biāo)函數(shù)為：

式中，F(xiàn)c表示節(jié)點路徑中替代節(jié)點的目標(biāo)函數(shù)；f(dc,ny)表示路徑與節(jié)點代價在物理意義上的最大差異。將該數(shù)據(jù)映射在區(qū)間內(nèi)，可以保證節(jié)點在每一個內(nèi)容中均可以以最小的緩存節(jié)點得到最大的響應(yīng)結(jié)果，此時需要滿足的約束條件為：

式中，U表示網(wǎng)絡(luò)節(jié)點的集合；dc和ny分別表示鏈路的容量與需求。根據(jù)以上目標(biāo)函數(shù)和約束條件，可以實現(xiàn)緩存協(xié)作任務(wù)的優(yōu)化分配。

1.3 設(shè)計緩存協(xié)作任務(wù)分配優(yōu)化算法

結(jié)合上文中的規(guī)劃的緩存訪問路徑，以及目標(biāo)函數(shù)和優(yōu)化條件，可以得到緩存協(xié)作任務(wù)分配優(yōu)化的算法流程，如圖2所示。

圖2 算法流程

結(jié)合圖2 中的流程圖可知，在優(yōu)化任務(wù)分配結(jié)果時，首先初始化處理所有系統(tǒng)中的任務(wù)，計算網(wǎng)絡(luò)節(jié)點的路徑，讀取Web 前端緩存協(xié)作的代價函數(shù)，并規(guī)劃緩存訪問路徑。當(dāng)路徑上存在非法訪問節(jié)點時，可以以節(jié)點數(shù)量為計算代價，將初始的內(nèi)容分配給一個具備初始價值的回轉(zhuǎn)緩存路徑，將上述興趣包中的內(nèi)容保存在節(jié)點命中信息中。在基于隱式協(xié)作策略的緩存任務(wù)中，以最新的緩存收益為核心，分配空閑節(jié)點中的非法訪問節(jié)點，并使用新的節(jié)點替換此類節(jié)點。此時的協(xié)作機制需要預(yù)先處理大量的訪問信息，在每一個節(jié)點的緩存狀態(tài)中，均選擇最佳的訪問節(jié)點，并通過計算得到內(nèi)容對象的最佳速度與位置。在這種機制中，獲取緩存節(jié)點的最優(yōu)路徑，并分解不同的內(nèi)容區(qū)塊[14]。若能夠獲取此類節(jié)點，則可以直接丟棄分解內(nèi)容，并獲取任務(wù)分配的優(yōu)化結(jié)果。但是若不能得到該類緩存節(jié)點，需要重新初始化任務(wù)參數(shù)，繼續(xù)迭代處理，直至最佳緩存節(jié)點被計算出來。此時得到的任務(wù)優(yōu)化分配方法，即為本文設(shè)計的基于離散粒子群算法的Web前端緩存協(xié)作任務(wù)優(yōu)化分配方法。

2 實驗研究

2.1 設(shè)置實驗環(huán)境與參數(shù)

以本文設(shè)計的基于離散粒子群算法的Web 前端緩存協(xié)作任務(wù)優(yōu)化分配方法為核心，以用戶偏好方法、多邊緣設(shè)備協(xié)作方法和Q-learning 方法為對比，設(shè)計對比實驗，以判斷所提方法是否更具優(yōu)越性。在Web 前端的緩存協(xié)作中，主要可以分為兩種拓撲類型，依據(jù)內(nèi)容分布以及緩存大小的不同，可以提前設(shè)置實驗環(huán)境與實驗參數(shù)，如表1所示。

表1 實驗參數(shù)

如表1 所示，在Web 前端的網(wǎng)絡(luò)環(huán)境中，生成40 個緩存節(jié)點，在這些緩存節(jié)點中，服務(wù)器的節(jié)點數(shù)量為3。同時建立兩類實驗機制作為背景環(huán)境，主要以內(nèi)容分布為主體，將其分為固定內(nèi)容與隨機內(nèi)容。每個源節(jié)點中設(shè)置20 000個單位的內(nèi)存，在不同的內(nèi)容單位間，受歡迎程度有很大差別，且基本服從Zipf 參數(shù)。在內(nèi)存分布固定的前提下，Web 前端的單節(jié)點緩存大小分別為50、100、150、200、250 MB，在內(nèi)容隨機分布的情況下，Web 前端的單節(jié)點緩存大小為100、200、300、400、500 MB，此時數(shù)據(jù)的傳輸效率分別為50 KB/ms和100 KB/ms。

2.2 選取專屬緩存節(jié)點

以內(nèi)容的固定與隨機為分區(qū)，驗證20個緩存網(wǎng)絡(luò)節(jié)點的權(quán)重，得到的結(jié)果如圖3所示。

圖3 緩存節(jié)點權(quán)重

通過圖3所示的權(quán)重結(jié)果可以得知，在內(nèi)容固定分布與內(nèi)容隨機分布兩種優(yōu)化分配方法中，40 個緩存節(jié)點的權(quán)重指標(biāo)存在較大差異。大多數(shù)網(wǎng)絡(luò)節(jié)點的權(quán)重均不超過0.03，當(dāng)內(nèi)容分布固定時，權(quán)重指標(biāo)大于0.03的網(wǎng)絡(luò)節(jié)點ID分別為10、13、22、33、36，當(dāng)內(nèi)容分布隨機時，權(quán)重指標(biāo)大于0.03的網(wǎng)絡(luò)節(jié)點ID分別為10、18、22、33、36。在這兩類不同的計算機環(huán)境下，存在四個同樣權(quán)重指標(biāo)較大且重合的網(wǎng)絡(luò)節(jié)點ID，分別為10、22、33、36，因此，可以在網(wǎng)絡(luò)路由器中選擇這些網(wǎng)絡(luò)節(jié)點作為專屬緩存節(jié)點。

2.3 不同網(wǎng)絡(luò)節(jié)點平均時延測試

本實驗選擇平均網(wǎng)絡(luò)時延，作為網(wǎng)絡(luò)節(jié)點在Web 前端緩存協(xié)作任務(wù)優(yōu)化分配的測試指標(biāo)，用戶在各專屬緩存節(jié)點上所用到的時延越長，則該節(jié)點的性能越好。對比四種任務(wù)優(yōu)化分配算法的不同網(wǎng)絡(luò)節(jié)點平均時延，得到如圖4所示的測試結(jié)果。

圖4 平均時延測試

由圖4可知，隨著任務(wù)量的增加，四種任務(wù)分配優(yōu)化算法的平均時延均以不同的比例逐漸增加。在緩存節(jié)點10中，離散粒子群算法在任務(wù)量為1時的平均時延為2 ms，在任務(wù)量為8 000 MB時的平均時延為6 ms。用戶偏好方法的平均時延由5 ms提升為15 ms，多邊緣任務(wù)協(xié)作算法的平均時延由1 MB時的5 ms提升為8 000 MB時的12 ms，Q-learning算法的平均時延則由10 ms變?yōu)?4 ms。在以上四組數(shù)據(jù)中，離散粒子群算法在任意任務(wù)量中的平均時延均小于其他三種算法。在緩存節(jié)點ID為22和33時，離散粒子群算法的平均時延同樣遠小于其他三種算法。只有在緩存節(jié)點ID為36中，當(dāng)任務(wù)量為1 MB-2 000 MB時，離散粒子群算法的平均時延為4 ms-5 ms，略大于用戶偏好方法的3 ms-5 ms。其他任務(wù)量下，離散粒子群算法的平均時延均小于其他三種算法。通過以上數(shù)據(jù)可知，本文設(shè)計的基于離散粒子群算法的Web前端緩存協(xié)作任務(wù)優(yōu)化分配方法在四種對比算法中平均時延最小，性能最佳。由此可見，本文的設(shè)計實現(xiàn)了優(yōu)化目標(biāo)。

3 結(jié)束語

本文設(shè)計一種基于離散粒子群的Web 前端緩存協(xié)作任務(wù)優(yōu)化分配方法。在合適的信息節(jié)點上部署足夠的信息，通過降低緩存開銷，設(shè)計路徑訪問代價的替換優(yōu)化算法，在目標(biāo)函數(shù)與約束條件的作用下，完成任務(wù)優(yōu)化的分配。并設(shè)計相應(yīng)的算法流程，實現(xiàn)用戶網(wǎng)絡(luò)任務(wù)分配的優(yōu)化。實驗結(jié)果表明，該方法的網(wǎng)絡(luò)平均時延更低，可見本文的優(yōu)化分配實現(xiàn)了設(shè)計目標(biāo)，能夠在一定程度上降低緩存協(xié)作的時延。