,,
(1.石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院,石家莊 050043;2.中北大學(xué) 電子與計算機科學(xué)技術(shù)學(xué)院,太原 030051)
隨著云計算的發(fā)展普及,云計算環(huán)境下動態(tài)數(shù)據(jù)越來越多,云計算下數(shù)據(jù)成為重要的信息資源。為了更好的利用這些資源,需要對云計算環(huán)境下動態(tài)數(shù)據(jù)進行聚集[1]。數(shù)據(jù)聚集是數(shù)據(jù)處理過程中的重要環(huán)節(jié),對數(shù)據(jù)時代有著不可替代的作用。動態(tài)數(shù)據(jù)指在系統(tǒng)應(yīng)用中隨時間變化而改變的數(shù)據(jù),如庫存數(shù)據(jù)等,動態(tài)數(shù)據(jù)的準備和系統(tǒng)切換的時間有直接關(guān)系[2]。由于動態(tài)數(shù)據(jù)的變化性,導(dǎo)致在數(shù)據(jù)聚集過程中,數(shù)據(jù)信息存在失真甚至丟失的問題,因此云計算環(huán)境下動態(tài)數(shù)據(jù)存儲首先需要解決數(shù)據(jù)可靠性問題[3]。由于動態(tài)數(shù)據(jù)所具有的獨特性特征,導(dǎo)致傳統(tǒng)的數(shù)據(jù)聚集算法難以滿足動態(tài)數(shù)據(jù)聚集要求。這種情況下,使云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法達到最優(yōu)效果,成為當(dāng)前迫切需要解決的重點問題[4]。而基于同態(tài)加密與改進ECC的云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法,通過使用同態(tài)加密與消息認證碼聚集密文與簽名;在此基礎(chǔ)上,對云計算中節(jié)點的動態(tài)數(shù)據(jù)進行提取,通過驗證消息的完整性、發(fā)送者的合法性以及識別惡意節(jié)點,從而完成動態(tài)數(shù)據(jù)的聚集[5],這種方法有效的保證了數(shù)據(jù)的準確性及可靠性,成為這一課題的主要研究內(nèi)容[6]。隨著信息化發(fā)展,互聯(lián)網(wǎng)的普及,動態(tài)數(shù)據(jù)聚集成為但僅社會研究的重點課題,隨著研究的不斷深入,產(chǎn)生了豐碩的研究成果[7]。
文獻[8]提出了一種基于線性時間概率計算算法的云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法。為解決動態(tài)數(shù)據(jù)中的冗余數(shù)據(jù),減少數(shù)據(jù)傳輸,提出數(shù)據(jù)聚集操作過程中,在動態(tài)數(shù)據(jù)中間節(jié)點對動態(tài)數(shù)據(jù)進行預(yù)處理,在此基礎(chǔ)上,針對云計算環(huán)境下動態(tài)數(shù)據(jù)聚集操作路徑復(fù)雜,且容易出現(xiàn)動態(tài)數(shù)據(jù)重復(fù)計數(shù)問題,提出通過對副本不敏感的概要結(jié)構(gòu)并優(yōu)化數(shù)據(jù)聚集算法特性,從而實現(xiàn)動態(tài)數(shù)據(jù)聚集算法。但這種算法難以保證數(shù)據(jù)的準確性。文獻[9]提出了一種半監(jiān)督空間化的動態(tài)數(shù)據(jù)聚集算法。針對傳統(tǒng)數(shù)據(jù)聚集算法存在的不足,引入具備半監(jiān)督學(xué)習(xí)能力的半監(jiān)督項對云計算環(huán)境下動態(tài)數(shù)據(jù)特征隸屬度矩陣進行增強,利用動態(tài)數(shù)據(jù)的聚類中心和中心鄰近的點組成數(shù)據(jù)空間,通過動態(tài)數(shù)據(jù)的樣本點與該空間的距離替代歐氏距離作為新的動態(tài)數(shù)據(jù)相似度度量標(biāo)準,并給出判斷聚類中心能否合并的閾值參數(shù),從而完成半監(jiān)督空間化的動態(tài)數(shù)據(jù)聚集算法,但這種算法復(fù)雜度較高,難以保證動態(tài)數(shù)據(jù)聚集前后的一致性。文獻[10]提出了一種基于物理干擾模型的動態(tài)數(shù)據(jù)聚集算法,通過構(gòu)造一棵根在頭節(jié)點的局部數(shù)據(jù)聚集樹,將整個云計算空間劃分為若干個邊長相等且只包含一個節(jié)點的正方形區(qū)域,最后對節(jié)點所在區(qū)域內(nèi)動態(tài)數(shù)據(jù)進行聚集,但這種方法存在聚集速度較慢的問題。
針對上述產(chǎn)生的問題,提出一種基于粒子群優(yōu)化算法的云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法,首先分析云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法數(shù)學(xué)模型,然后,提出通過粒子群優(yōu)化算法完成云計算環(huán)境下動態(tài)數(shù)據(jù)聚集。通過對云計算環(huán)境中的動態(tài)數(shù)據(jù)結(jié)構(gòu)模型進行分析,實現(xiàn)對數(shù)據(jù)的離散樣本頻譜特征的計算,從而完成云計算環(huán)境下動態(tài)數(shù)據(jù)聚集樣本的特征提取和信息模型構(gòu)建。通過混沌映射方法對其進行優(yōu)化,通過生成混沌序列,解決粒子群算法存在的收斂速度慢問題,通過粒子群優(yōu)化算法對云計算環(huán)境中動態(tài)數(shù)據(jù)的特征進行聚集,從而完成云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法。實驗結(jié)果表明,本文所提算法是一種穩(wěn)定、可靠的動態(tài)數(shù)據(jù)聚集算法,其在存儲空間和準確率上均有良好的性能體現(xiàn),為該領(lǐng)域的發(fā)展創(chuàng)造了條件。
最小覆蓋集查找算法中,每個云計算節(jié)點按照云計算環(huán)境下動態(tài)數(shù)據(jù)ID升序的順序從一跳鄰居節(jié)點集AL中挑選一個未被選取的云計算環(huán)境下動態(tài)數(shù)據(jù)節(jié)點,并對該數(shù)據(jù)節(jié)點所覆蓋的鄰居節(jié)點中包括的二跳鄰居節(jié)點集BL沒有被覆蓋節(jié)點個數(shù)進行判斷,比較二跳鄰居節(jié)點集BL沒有被覆蓋節(jié)點個數(shù)和AL中的其余節(jié)點個數(shù),尋求云計算下動態(tài)數(shù)據(jù)節(jié)點數(shù)量最多;在對網(wǎng)絡(luò)能量均衡問題進行考慮過程中,設(shè)定動態(tài)數(shù)據(jù)節(jié)點x的當(dāng)前剩余能量用Ex進行表示,加入最小覆蓋集的動態(tài)數(shù)據(jù)節(jié)點閾值利用Ethreshold進行表示,則有Ex>Ethreshold,只有當(dāng)數(shù)據(jù)節(jié)點同時滿足Ex>Ethreshold條件的同時動態(tài)數(shù)據(jù)節(jié)點數(shù)量最多,才可以加入云計算環(huán)境下動態(tài)數(shù)據(jù)的最小覆蓋集中,隨著時間的推移,Ethreshold閾值隨著云計算網(wǎng)絡(luò)能量的變化而動態(tài)的發(fā)生變化,從而適應(yīng)最小覆蓋集算法的需求,實現(xiàn)對云計算環(huán)境下動態(tài)數(shù)據(jù)最小覆蓋集的查找。
再次基礎(chǔ)上,對動態(tài)數(shù)據(jù)聚集樹進行構(gòu)造,在進行動態(tài)數(shù)據(jù)聚集樹構(gòu)造過程中,通過云計算環(huán)境下動態(tài)數(shù)據(jù)的最小覆蓋集查找方法,得到MCS,在此基礎(chǔ)上,向外廣播動態(tài)數(shù)據(jù)聚集樹,完成包含MCS的數(shù)據(jù)節(jié)點列表的動態(tài)數(shù)據(jù)信息ATC的構(gòu)建,當(dāng)動態(tài)數(shù)據(jù)節(jié)點收到ATC消息后,執(zhí)行最小覆蓋集轉(zhuǎn)發(fā)算法,其具體過程如下所述。
對云計算環(huán)境下動態(tài)數(shù)據(jù)節(jié)點接收ATC次數(shù)進行判斷,如果不是第1次接收ATC,則終止算法,如果是第1次接收ATC,則可以利用該云計算環(huán)境下動態(tài)數(shù)據(jù)節(jié)點的鄰居節(jié)點進行下一跳轉(zhuǎn)發(fā),并對該節(jié)點是否屬于MCS中的節(jié)點進行判定,如果不屬于MCS節(jié)點,則終止算法,否則,對該節(jié)點的MCS進行計算,繼續(xù)廣播,重復(fù)上述步驟,直至在云計算環(huán)境下動態(tài)數(shù)據(jù)的每個層都產(chǎn)生一個MCS,且以Sink為根的樹。MCS中的節(jié)點覆蓋次序與查找算法中依次加入的次序相同,也就是說覆蓋次序與覆蓋BL中數(shù)據(jù)節(jié)點數(shù)量相關(guān),在進行下一次對ATC的覆蓋前,需要在一段適合的時間后,從而避免多個節(jié)點同時覆蓋過程中存在相同MCS鄰居節(jié)點產(chǎn)生的碰撞;此外,當(dāng)動態(tài)數(shù)據(jù)節(jié)點收到來自上層節(jié)點的相同ATC信息,則選擇較早的覆蓋節(jié)點作為自己的下一跳轉(zhuǎn)發(fā)節(jié)點。
針對云計算環(huán)境下動態(tài)數(shù)據(jù)中間節(jié)點,利用讀向量相似性的方法去除其冗余和錯誤數(shù)據(jù)信息,通過讀向量的形式將正確的云計算環(huán)境下動態(tài)數(shù)據(jù)發(fā)送到下一個動態(tài)數(shù)據(jù)的中間節(jié)點,通過數(shù)據(jù)緩存窗口Δt內(nèi)的一系列讀數(shù)對云計算環(huán)境下動態(tài)數(shù)據(jù)節(jié)點Ni的讀向量進行描述,Ri={xi(t-Δt+1),xi(t-Δt+2),…,xi(t)}表示云計算環(huán)境下動態(tài)數(shù)據(jù)節(jié)點Ni的讀數(shù),其中,xi(t)表示動態(tài)數(shù)據(jù)節(jié)點Ni在t時刻的數(shù)據(jù)采樣值。節(jié)點Ni在緩存窗口Δt內(nèi)的讀數(shù)代表一個讀向量。
由于云計算環(huán)境下動態(tài)數(shù)據(jù)在正常情況下是漸變且有趨勢的,而錯誤數(shù)據(jù)信息會改變數(shù)據(jù)變化的趨勢,或當(dāng)前數(shù)據(jù)發(fā)生跳躍,為發(fā)現(xiàn)這種錯誤數(shù)據(jù)信息,通過讀向量相似系數(shù)ρ對動態(tài)數(shù)據(jù)進行判斷。
(1)
式中,E(X)表示讀向量的數(shù)學(xué)期望,E(X)表示讀向量的方差,ρXY∈[-1,1]。|ρXY|與XY之間誤差成反比關(guān)系,隨著|ρXY|的增大,誤差逐漸減小,冗余性提高;反之,則說明該讀取向量中存在錯誤信息。通過在數(shù)據(jù)聚集時設(shè)置一個云計算動態(tài)數(shù)據(jù)中間節(jié)點閾值θ,當(dāng)ρXY<θ時,認為該動態(tài)數(shù)據(jù)為錯誤數(shù)據(jù),將其放入錯誤數(shù)據(jù)集,在算法完成后,丟棄錯誤數(shù)據(jù)集;否則,將云計算數(shù)據(jù)放入冗余數(shù)據(jù)集,并求取冗余數(shù)據(jù)集的平均值,將結(jié)果發(fā)送到下一個動態(tài)數(shù)據(jù)聚集節(jié)點,反復(fù)上述操作,直到完成對所有云計算下數(shù)據(jù)聚集,從而實現(xiàn)云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法。
設(shè)待聚集的云計算環(huán)境下動態(tài)數(shù)據(jù)的樣本空間為X={x1,x2,…,xn},其中云計算環(huán)境下動態(tài)數(shù)據(jù)樣本xi=(xi1,xi2,…,xip)(i=1,2,…,n)表示P維特征空間RP中的一點。聚集問題可以表示成找到一個劃分C=(C1,C2,…,CK),滿足公式(2),并使得總的類間距離和最小。類間距離和用公式(3)進行計算。
(2)
(3)
在上述云計算環(huán)境下動態(tài)數(shù)據(jù)聚集模型的基礎(chǔ)上,提出通過粒子群優(yōu)化算法的云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法。
設(shè)定一個D維動態(tài)數(shù)據(jù)聚集搜索空間,存在一個由m個粒子組成的粒子群,每個云計算環(huán)境下動態(tài)數(shù)據(jù)信息特征矢量Ai對應(yīng)的函數(shù)可以表示成:
li(k)=(1-ρ)li(k-1)+γf(xi(k))
(4)
式中,fi表示Ai模因組適應(yīng)度函數(shù),xi(k)表示第i個粒子k時刻的全局優(yōu)化粒子權(quán)值。
設(shè)置門限值Nth,當(dāng)Neff xk+1=sin(a/xk),0<|xk|≤1 (5) 式中,xk表示云計算環(huán)境下第k個動態(tài)數(shù)據(jù)的慣性權(quán)重;a表示動態(tài)數(shù)據(jù)聚集中心的控制參量。 ∑τ=diag(max(σi-τ,0)) (6) 根據(jù)不同的動態(tài)數(shù)據(jù)聚集任務(wù),對適應(yīng)度函數(shù)內(nèi)權(quán)重進行調(diào)整,得到新的聚集權(quán)重系數(shù)可以表示為: (7) 式中,{α,β}表示云計算環(huán)境下動態(tài)數(shù)據(jù)聚集的分集聚斂目標(biāo)函數(shù),從而得到優(yōu)化的聚集目標(biāo)函數(shù)可以表示為: (8) 其中:粒子的位置對應(yīng)云計算環(huán)境下樣本數(shù)據(jù)的k個聚類中心。除了粒子位置外,對粒子的適應(yīng)度和速度進行編碼。由于樣本數(shù)據(jù)的屬性向量維數(shù)為d,則粒子的位置和速度為k×d維矩陣。 針對粒子群算法進行動態(tài)數(shù)據(jù)聚集存在的早熟并且收斂速度慢的問題,本文通過混沌映射方法對其進行優(yōu)化,混沌方法首先要生成混沌序列,混沌序列可以表示為: Zn+1=μZn(1-Zn) (9) 隨著粒子群的不斷進行迭代計算,當(dāng)其計算超過一定閾值,粒子群算法收斂速度開始下降,為了解決這一問題,利用生成的混沌序列來對全局最優(yōu)粒子進行擾動。將上述云計算下動態(tài)數(shù)據(jù)的m個粒子的每一維度在(0,1)范圍上一一映射,從而得到向量D=(d1,d2,…,dm)。其中,d1表示粒子第i維,其表達式可以表述為: di=(gbesti-a)/(b-a) (10) 式中,gbesti表示動態(tài)數(shù)據(jù)粒子中適應(yīng)度最高粒子的第i維;a和b分別表示動態(tài)數(shù)據(jù)粒子在任意維度中的取值下限和上限。 利用混沌擾動重新對云計算環(huán)境下動態(tài)數(shù)據(jù)進行迭代計算,得到新序列: Z1=(Z11,Z12,…,Z1m) (11) 將上式計算得到的新序列Z1當(dāng)成云計算環(huán)境下動態(tài)數(shù)據(jù)的新粒子,并進行適應(yīng)度計算,與之前搜索得到的最優(yōu)解適應(yīng)度相比,如果計算得到Z1適應(yīng)度更高,則可以說明Z1為當(dāng)前最優(yōu)解。 通過上述論述,在云計算環(huán)境下動態(tài)數(shù)據(jù)聚集表示一個任務(wù)調(diào)度策略,從而完成基于粒子群優(yōu)化算法的云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法。 為了證明本文提出的基于粒子群優(yōu)化算法的云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法的有效性和實用性,以Intel P4 2G處理器為硬件環(huán)境,MATLAB2008a為平臺,運用對比法將本文提出的基于粒子群優(yōu)化算法的云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法與文獻[8]和文獻[9]所提云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法進行比較,完成本次實驗。 1)對比3種云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法的復(fù)雜度; 2)改變云計算環(huán)境下動態(tài)數(shù)據(jù)大小,得到不同大小數(shù)據(jù)聚集時間對比; 3)對比各方法下不同大小動態(tài)數(shù)據(jù)聚集所占空間; 4)通過對比數(shù)據(jù)聚集后的原始性,比較3種云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法的可靠度,; 5)對3種云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法的能耗(焦)進行對比。 首先對比3種云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法的復(fù)雜度,設(shè)算法的復(fù)雜度單位為%,其計算方法如公式(12)所示。 (12) 式中,n表示算法的循環(huán)次數(shù),通過計算,得到3種算法的復(fù)雜度對比,對比結(jié)果如圖1所示。 圖1 3種算法的復(fù)雜度對比 通過圖1可以看出,本文所提算法的復(fù)雜度較文獻[8]和文獻[9]低,說明本文所提算法的復(fù)雜度較低,算法執(zhí)行較為簡單,且利于后續(xù)維護工作的開展。 表1是云計算環(huán)境下不同大小動態(tài)數(shù)據(jù)聚集時間(s)對比。通過改變云計算環(huán)境下動態(tài)數(shù)據(jù)大小,得到不同大小數(shù)據(jù)聚集時間對比。 表1 不同大小數(shù)據(jù)聚集時間對比 通過對表1的分析可知,本文采用粒子群優(yōu)化算法,改善粒子群算法進行數(shù)據(jù)聚集存在的收斂速度慢問題,提高了數(shù)據(jù)聚集時間,證明本文所提方法具有較好的可行性。表2是3種算法對不同動態(tài)數(shù)據(jù)進行數(shù)據(jù)聚集所占的空間(MB)對比,通過實驗不同大小動態(tài)數(shù)據(jù)聚集所占空間,完成該實驗。 表2 3種算法數(shù)據(jù)聚集所占存儲空間對比 通過表2可知,本文所提算法在進行數(shù)據(jù)聚集時,數(shù)據(jù)所占內(nèi)存變化較小,說明本文所提算法進行數(shù)據(jù)聚集,能夠較好的保證數(shù)據(jù)的原始性,也就是說,本文所提算法能夠較好的保證數(shù)據(jù)的準確性。 對比3種云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法的可靠度,設(shè)可靠度單位為%,通過對比數(shù)據(jù)聚集后的原始性,完成本次試驗。通過實驗,得到3種算法的可靠度對比,對比結(jié)果如圖2所示。 圖2 3種算法的可靠度對比 通過對上圖的分析可知,本文所提方法由于在進行云計算環(huán)境下數(shù)據(jù)聚集之前,首先構(gòu)建了數(shù)據(jù)聚集算法的數(shù)學(xué)模型,使本文所提云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法的可靠度與文獻[8]和文獻[9]所提算法可靠度相比,有了較大幅度提高,且本文所提算法的可靠度較穩(wěn)定。 最后對3種云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法的能耗(焦)進行對比,通過實驗,得到3種云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法的運行能耗對比,對比結(jié)果如圖3所示。 圖3 3種算法的運行能耗對比 通過圖3可知,本文所提算法的運行能耗較少,由于本文所提算法可靠度較為穩(wěn)定且進行數(shù)據(jù)聚集的時間較短。 綜上所述,本文所提云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法能夠有效提高數(shù)據(jù)聚集的可靠度,降低數(shù)據(jù)聚集時間及能耗,且數(shù)據(jù)聚集占用的內(nèi)存較少,數(shù)據(jù)聚集算法的復(fù)雜度較高,具有良好的使用價值。 隨著云計算的普及,云計算數(shù)據(jù)越來越多,對云計算環(huán)境下的數(shù)據(jù)進行聚集成為新的關(guān)注熱點。傳統(tǒng)的云環(huán)境下動態(tài)數(shù)據(jù)聚集算法由于其動態(tài)復(fù)雜度高,且收斂速度慢等問題,提出一種基于基于粒子群優(yōu)化算法的云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法。并通過實驗證明,所提方法能夠有效提高云計算環(huán)境下動態(tài)數(shù)據(jù)聚集算法的數(shù)據(jù)聚集時間較短,且其復(fù)雜度較低,是一種可靠、節(jié)能、穩(wěn)定的數(shù)據(jù)聚集算法,對云計算環(huán)境下動態(tài)數(shù)據(jù)管理起著積極作用。 [1] 林國勇,黃 帆.一種用于云計算的數(shù)據(jù)容災(zāi)分配算法的改進[J].科學(xué)技術(shù)與工程,2017,17(1):260-264. [2] 李曉峰.云平臺中大數(shù)據(jù)并行聚類方法優(yōu)化研究仿真[J].計算機仿真,2016,33(7):327-330. [3] 張 宇.基于極值特征的雷達偵察數(shù)據(jù)BIRCH聚類方法[J].電子設(shè)計工程,2016,24(9):15-18. [4] 解 鋒,葉曉慧.一種數(shù)據(jù)特征敏感的高效數(shù)據(jù)聚集編碼方案[J].計算機測量與控制,2016,24(3):179-182. [5] 龍 虎,張小梅.基于修正二階錐規(guī)劃模型的大數(shù)據(jù)聚類算法[J].科技通報,2016,32(8):168-171. [6] 周永正,張金良.聚集數(shù)據(jù)多元線性模型參數(shù)的多元聚集廣義嶺估計的相對效率[J].數(shù)學(xué)的實踐與認識,2016,46(9):149-155. [7] 范凌云,文國琴,張文濤.VANET中基于認知代理與回歸聚集的低延遲數(shù)據(jù)處理算法[J].計算機應(yīng)用研究,2016,33(6):1871-1876. [8] 應(yīng)可珍,鄔錦彬,戴國勇,等.一種基于線性時間概率計數(shù)算法的數(shù)據(jù)聚集技術(shù)[J].傳感技術(shù)學(xué)報,2015,28(1):99-106. [9] 于 平,王士同.半監(jiān)督空間化競爭聚集算法及其在圖像分割中的應(yīng)用[J].計算機工程,2015,41(2):234-241. [10] 劉文彬,劉紅冰,李香寶,等.基于物理干擾模型的無通信沖突的數(shù)據(jù)聚集調(diào)度算法[J].計算機應(yīng)用研究,2015,32(7):2092-2096.3 實驗及結(jié)果分析
3.1 實驗步驟
3.2 實驗結(jié)果分析
4 結(jié)束語