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

侯戌非

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

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

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

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

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

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

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

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

(1)

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

(2)

(3)

(4)

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

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

(5)

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

(6)

(7)

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

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

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

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

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

(8)

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

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

(9)

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

(10)

(11)

(12)

(13)

完成協(xié)同進化算法個體評價后，采用優(yōu)勝閾值[10]確定種群的每個子群是否發(fā)生突變，并在突變后接收新微粒，該微粒可取代迭代前的微粒，將這個過程表征為

(14)

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

(15)

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

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

(16)

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

(17)

2 實驗結果與分析

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

圖1 不同傳輸速率下不同方法存儲時間響應測試

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

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

表1 不同算法負載均衡度對比

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

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

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

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

3 結論

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