物聯(lián)網(wǎng)環(huán)境下海量多源異構(gòu)數(shù)據(jù)的存儲算法

侯戌非

(銅陵職業(yè)技術(shù)學(xué)院 信息工程系，安徽 銅陵 244000)

物聯(lián)網(wǎng)作為一種新型網(wǎng)絡(luò)，利用通信網(wǎng)絡(luò)的數(shù)據(jù)交互，可以實(shí)現(xiàn)智能識別、跟蹤和監(jiān)控，在制造業(yè)、工業(yè)和農(nóng)業(yè)等領(lǐng)域得到了廣泛應(yīng)用[1-2].物聯(lián)網(wǎng)環(huán)境下的數(shù)據(jù)具有多源異構(gòu)、規(guī)模大和冗余度高等特點(diǎn)，當(dāng)前物聯(lián)網(wǎng)信息服務(wù)系統(tǒng)在多維數(shù)據(jù)查詢和檢索等方面獲得一些研究成果，但處理海量多源異構(gòu)數(shù)據(jù)時(shí)，仍然存在存儲能耗大和耗時(shí)長等問題[3].在這種情況下，如何高效存儲這些海量多源異構(gòu)數(shù)據(jù)成為物聯(lián)網(wǎng)領(lǐng)域亟待解決的重點(diǎn)問題[4].

為了提高海量多源異構(gòu)數(shù)據(jù)存儲質(zhì)量，降低多源異構(gòu)數(shù)據(jù)存儲過程中系統(tǒng)的能量消耗，研究人員得出了一些研究成果.林志貴[5]提出一種新的蛇形時(shí)隙數(shù)據(jù)存儲算法，該算法先確定待存儲的數(shù)據(jù)優(yōu)先級，依據(jù)優(yōu)先級判斷存儲位置與查詢節(jié)點(diǎn)網(wǎng)格的距離，定義節(jié)點(diǎn)存儲閾值，確定數(shù)據(jù)存儲時(shí)隙分配，當(dāng)存儲節(jié)點(diǎn)均達(dá)到閾值時(shí)，將該數(shù)據(jù)劃分至與其相同優(yōu)先級的鄰域內(nèi).該算法可以解決網(wǎng)絡(luò)節(jié)點(diǎn)能量不均問題，但當(dāng)網(wǎng)絡(luò)中的數(shù)據(jù)具有多源和異構(gòu)特性，且數(shù)據(jù)量較大時(shí)，導(dǎo)致數(shù)據(jù)存儲時(shí)間響應(yīng)慢、占用內(nèi)存空間較大.錢偉強(qiáng)[6]提出一種基于調(diào)度機(jī)制的數(shù)據(jù)存儲算法，該算法利用周期性調(diào)度及梯度優(yōu)化形式，且考慮到多源異構(gòu)數(shù)據(jù)存儲中最小傳輸粒度特征，對數(shù)據(jù)存儲過程中的指紋梯度進(jìn)行優(yōu)化，并將其代入數(shù)據(jù)傳輸過程中，完成海量數(shù)據(jù)存儲.該算法存儲難以將重復(fù)的異構(gòu)數(shù)據(jù)濾除，且存儲過程中存在嚴(yán)重的負(fù)載不均衡問題.

在物聯(lián)網(wǎng)環(huán)境下，針對當(dāng)前海量多源異構(gòu)數(shù)據(jù)存儲方法存在的不足，提出一種基于多種群協(xié)同進(jìn)化的海量多源異構(gòu)數(shù)據(jù)存儲算法.采用該算法有效節(jié)約了系統(tǒng)在存儲處理海量多源異構(gòu)數(shù)據(jù)時(shí)的內(nèi)存空間，提高了負(fù)載均衡度.

1 基于多種群協(xié)同進(jìn)化的海量多源異構(gòu)數(shù)據(jù)存儲算法

1.1 構(gòu)建多源異構(gòu)數(shù)據(jù)存儲調(diào)度目標(biāo)函數(shù)

建立多源異構(gòu)數(shù)據(jù)副本模型，對網(wǎng)絡(luò)中重復(fù)的數(shù)據(jù)構(gòu)造數(shù)據(jù)指紋索引，搜索到重復(fù)的異構(gòu)數(shù)據(jù)用布隆過濾器將重復(fù)的異構(gòu)數(shù)據(jù)濾除，給出多源異構(gòu)數(shù)據(jù)存儲調(diào)度目標(biāo)函數(shù)，將濾除后的數(shù)據(jù)存儲任務(wù)調(diào)度問題抽象為最優(yōu)解問題.

存儲在物聯(lián)網(wǎng)環(huán)境中的海量多源異構(gòu)數(shù)據(jù)Cs都會(huì)被分解，以數(shù)據(jù)塊的形式存儲在表格table中，表格table可以跨多個(gè)網(wǎng)絡(luò)服務(wù)器.設(shè)定由k個(gè)協(xié)調(diào)器構(gòu)成的節(jié)點(diǎn)矩陣集群中，F(xiàn)表示節(jié)點(diǎn)矩陣集群中存儲的某一個(gè)多源異構(gòu)文件，bs表示多源異構(gòu)數(shù)據(jù)集的大小，則F的大小為n×bs，F(xiàn)含有n×m個(gè)多源異構(gòu)數(shù)據(jù)塊存儲在協(xié)調(diào)器中，可將Fn×m矩陣表征為異構(gòu)數(shù)據(jù)文件的分塊，用{b11,…,bn1}表示原始數(shù)據(jù)文件F的數(shù)據(jù)塊，n表示文件的原始數(shù)據(jù)塊，則該多源異構(gòu)數(shù)據(jù)文件的副本可用矩陣Fn×(m-1)表示.

(1)

其中，bnm表示某一矩陣元素.當(dāng)節(jié)點(diǎn)矩陣集群獲得用戶上傳的海量多源異構(gòu)數(shù)據(jù)時(shí)，多源異構(gòu)數(shù)據(jù)塊b11存儲在表格table中，異構(gòu)數(shù)據(jù)b12將作為b11的副本，存儲在b11不同的備份服務(wù)器中，同樣b12為b11的副本，也存儲在與b12同類的機(jī)架，但是卻在不同的備份服務(wù)器中，假設(shè)m為異構(gòu)數(shù)據(jù)副本系數(shù)且滿足m>3，則其他的多源異構(gòu)數(shù)據(jù)塊會(huì)存儲至b11、b12和b13之外的備份服務(wù)器中.在數(shù)據(jù)存儲節(jié)點(diǎn)矩陣中設(shè)定MD5索引[7]，重復(fù)查找當(dāng)前內(nèi)存中重復(fù)的多源異構(gòu)數(shù)據(jù)，用布隆過濾器對這些重復(fù)數(shù)據(jù)過濾.

(2)

(3)

(4)

其中，nτ和mτ表示已覆蓋的異構(gòu)數(shù)據(jù)，τ∈u表示過濾強(qiáng)度.

設(shè)定多源異構(gòu)數(shù)據(jù)文件冗余率為r%，通過公式(2)對重復(fù)覆蓋的異構(gòu)數(shù)據(jù)進(jìn)行過濾，濾出的異構(gòu)數(shù)據(jù)塊大小為a，則濾出的多源異構(gòu)數(shù)據(jù)所占的內(nèi)存空間可利用下式表示.

(5)

假設(shè)，SUMOM表示物聯(lián)網(wǎng)環(huán)境下內(nèi)存存儲的海量多源異構(gòu)數(shù)據(jù)文件占有的內(nèi)存空間，通過重復(fù)覆蓋物聯(lián)網(wǎng)環(huán)境下內(nèi)存中存儲的多源異構(gòu)數(shù)據(jù)后，現(xiàn)有存儲的多源異構(gòu)數(shù)據(jù)文件所占有的內(nèi)存空間SUMMem可利用下式表示為

(6)

(7)

其中，p(bais)表示系統(tǒng)存儲區(qū)多源異構(gòu)數(shù)據(jù)可用概率，QoSa表示該異構(gòu)數(shù)據(jù)的可用性服務(wù)需求.

1.2 協(xié)同進(jìn)化算法求解存儲任務(wù)調(diào)度目標(biāo)函數(shù)

采用協(xié)同進(jìn)化算法求解公式(7)給出的目標(biāo)函數(shù)，依據(jù)目標(biāo)函數(shù)對數(shù)據(jù)存儲任務(wù)數(shù)量進(jìn)行編碼，通過多次迭代求解獲得最優(yōu)解，編碼過程如下.

編碼采用自然數(shù)和長度完成海量多源異構(gòu)數(shù)據(jù)存儲子任務(wù)量，根據(jù)維度可計(jì)算出需要處理的異構(gòu)數(shù)據(jù)存儲任務(wù)數(shù)量.協(xié)同進(jìn)化算法[9]種群進(jìn)化過程中的粒子編碼，主要針對待存儲異構(gòu)數(shù)據(jù)存儲任務(wù)數(shù)量，Pj(j=1,2,…,k)用于描述某個(gè)微粒群，該群中含有的粒子數(shù)量為Xi.

Xi={ρj,xi1,…,xin},

(8)

其中，ρj表示Pj位置分量，xin用于描述微粒i在Pj處的位置分量，優(yōu)勝閾Iij表示i，j相應(yīng)的閾值.

Iij=[Iij,μij]={xij|lij≤xij≤μij,xij∈R},

(9)

其中，i表示微粒，j表示分量，Iij和μij分別用于描述閾值的上下界，在選取協(xié)同進(jìn)化算法的種群適應(yīng)度過程中，假設(shè)選取微粒i的閾值為Iij，該閾值Iij作用于μij，則可獲得以下規(guī)則

(10)

(11)

(12)

(13)

完成協(xié)同進(jìn)化算法個(gè)體評價(jià)后，采用優(yōu)勝閾值[10]確定種群的每個(gè)子群是否發(fā)生突變，并在突變后接收新微粒，該微?？扇〈暗奈⒘?，將這個(gè)過程表征為

(14)

假設(shè)，ETC表示海量多源異構(gòu)數(shù)據(jù)存儲子任務(wù)運(yùn)行時(shí)間，ETC(τ,η)表示數(shù)據(jù)存儲任務(wù)τ轉(zhuǎn)向環(huán)區(qū)域η上存儲數(shù)據(jù)消耗的時(shí)間，依據(jù)ETC即可在種群微粒解碼過程中，求解獲得完成數(shù)據(jù)存儲調(diào)度任務(wù)耗費(fèi)的時(shí)間，利用下式計(jì)算

(15)

全部的海量多源異構(gòu)數(shù)據(jù)存儲結(jié)束，即全部的網(wǎng)絡(luò)環(huán)區(qū)域均結(jié)束了各自的多源異構(gòu)數(shù)據(jù)存儲任務(wù)，此時(shí)可計(jì)算獲得全部海量多源異構(gòu)數(shù)據(jù)存儲所需時(shí)間，即

FTime(η)=maxETC(τ,η).

(16)

當(dāng)種群內(nèi)部所有微粒完成每次迭代后，會(huì)更新微粒當(dāng)前搜索信息，最后對微粒群編碼結(jié)果進(jìn)行離散化處理，即

(17)

2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文算法的有效性，仿真實(shí)驗(yàn)選擇在MATLAB環(huán)境下進(jìn)行，操作系統(tǒng)為CentOS6.5，Hadoop版本為2.6.0.為了評估所提基于協(xié)同進(jìn)化的數(shù)據(jù)存儲算法的存儲性能，將其與基于存儲閾值的數(shù)據(jù)存儲算法以及基于海量存儲云調(diào)度機(jī)制的數(shù)據(jù)存儲算法進(jìn)行仿真實(shí)驗(yàn)對比.物聯(lián)網(wǎng)仿真時(shí)間為32 h，海量多源異構(gòu)數(shù)據(jù)傳輸速率不低于4 M.不同傳輸速率下不同方法存儲時(shí)間響應(yīng)測試結(jié)果如圖1所示.

圖1 不同傳輸速率下不同方法存儲時(shí)間響應(yīng)測試

圖1表示在數(shù)據(jù)存儲節(jié)點(diǎn)功率不斷提升的情況下，基于多種群協(xié)同進(jìn)化的數(shù)據(jù)存儲算法與對比算法存儲時(shí)間響應(yīng)(ms)的仿真結(jié)果.由圖1可知，隨著數(shù)據(jù)存儲節(jié)點(diǎn)功率的不斷增加，基于協(xié)同進(jìn)化的數(shù)據(jù)存儲算法與其他對照組算法的存儲時(shí)間響應(yīng)都呈現(xiàn)擴(kuò)大的趨勢，與其他算法相比，基于協(xié)同進(jìn)化的數(shù)據(jù)存儲算法的數(shù)據(jù)存儲時(shí)間響應(yīng)延遲增加幅度較小，始終比其他兩種算法低.這是由于所提算法綜合考慮了物聯(lián)網(wǎng)環(huán)境下的海量多源異構(gòu)數(shù)據(jù)的存儲處理情況，可在數(shù)據(jù)存儲節(jié)點(diǎn)功率不斷增大的情況下，過濾出重復(fù)數(shù)據(jù)，具有更快的響應(yīng)速度.基于存儲閾值的數(shù)據(jù)存儲算法以設(shè)定的數(shù)據(jù)存儲閾值，決定是否執(zhí)行下一次數(shù)據(jù)分配，一旦網(wǎng)絡(luò)中的數(shù)據(jù)發(fā)生量突增情況，該算法無法動(dòng)態(tài)更新存儲閾值，導(dǎo)致數(shù)據(jù)存儲時(shí)間響應(yīng)慢.

針對不同數(shù)據(jù)存儲算法對其負(fù)載均衡度進(jìn)行對比，各個(gè)數(shù)據(jù)存儲任務(wù)上的負(fù)載大小之和與總負(fù)載之比為負(fù)載均衡度(%).對比結(jié)果如表1所示，U、X、K分別表示基于協(xié)同進(jìn)化的數(shù)據(jù)存儲算法、基于存儲閾值的數(shù)據(jù)存儲算法以及基于海量存儲云調(diào)度機(jī)制的數(shù)據(jù)存儲算法.

表1 不同算法負(fù)載均衡度對比

分析表1可知，隨著多源異構(gòu)數(shù)據(jù)量的不斷增加，3種算法相應(yīng)的數(shù)據(jù)存儲負(fù)載均衡度均呈上升趨勢，當(dāng)數(shù)據(jù)量為200 MB時(shí)，所提算法負(fù)載均衡度為42.58%，基于存儲閾值的數(shù)據(jù)存儲算法的負(fù)載均衡度為25.58%，基于海量存儲云調(diào)度機(jī)制的數(shù)據(jù)存儲算法的負(fù)載均衡度34.36%，所提算法相比兩種算法分別提升了7%和8.22%.基于海量存儲云調(diào)度機(jī)制的數(shù)據(jù)存儲算法僅考慮到多源異構(gòu)數(shù)據(jù)存儲中最小傳輸粒度特征，沒有考慮到重復(fù)的冗余數(shù)據(jù)對數(shù)據(jù)存儲過程的影響，導(dǎo)致數(shù)據(jù)存儲負(fù)載均衡度較低.

通過實(shí)驗(yàn)，獲得不同存儲算法占有的空間內(nèi)存(KB)對比結(jié)果，如表2所示.U、X和K分別表示基于協(xié)同進(jìn)化的數(shù)據(jù)存儲算法、基于存儲閾值的數(shù)據(jù)存儲算法以及基于海量存儲云調(diào)度機(jī)制的數(shù)據(jù)存儲算法.

表2 不同算法存儲占用的空間內(nèi)存對比

分析表2可以看出，本文所提基于協(xié)同進(jìn)化的數(shù)據(jù)存儲算法在不同數(shù)據(jù)大小下，占用的空間內(nèi)存相比其他兩種算法較小，主要原因在于文中所提算法為了有效提升海量多源異構(gòu)數(shù)據(jù)存儲精度，采用協(xié)同進(jìn)化算法，針對需要完成的多源異構(gòu)數(shù)據(jù)任務(wù)數(shù)量進(jìn)行粒子編碼，通過多次迭代獲取最優(yōu)數(shù)據(jù)存儲任務(wù)調(diào)度方案，使得所提算法擁有更好的負(fù)載均衡度.

3 結(jié)論

物聯(lián)網(wǎng)環(huán)境下存在數(shù)據(jù)的多源、異構(gòu)、冗余度高等特性，在此背景下，現(xiàn)行數(shù)據(jù)存儲算法在進(jìn)行數(shù)據(jù)存儲過程中有占用內(nèi)存空間大、負(fù)載不均衡、時(shí)間響應(yīng)慢等不足.針對這些不足，提出一種基于協(xié)同進(jìn)化的海量多源異構(gòu)數(shù)據(jù)存儲算法.將海量多源異構(gòu)數(shù)據(jù)存儲任務(wù)調(diào)度問題抽象為最優(yōu)解問題，采用協(xié)同進(jìn)化算法對微粒群進(jìn)行迭代搜索，以最終獲得的最優(yōu)調(diào)度方案完成海量多源異構(gòu)數(shù)據(jù)存儲.經(jīng)過實(shí)驗(yàn)驗(yàn)證，所提算法相比當(dāng)前數(shù)據(jù)存儲算法，在存儲和處理海量多源異構(gòu)數(shù)據(jù)時(shí)，響應(yīng)速度更快，有效節(jié)省了系統(tǒng)的內(nèi)存空間，提高了負(fù)載均衡度.