楊中杰，王立中

(內(nèi)蒙古農(nóng)業(yè)大學(xué)計算機技術(shù)與信息管理系，內(nèi)蒙古 包頭 014109)

1 引言

存儲系統(tǒng)作為計算機應(yīng)用領(lǐng)域的重要組成部分，不僅與數(shù)據(jù)采集、預(yù)處理、處理、傳輸、轉(zhuǎn)換等環(huán)節(jié)密切相關(guān)，而且系統(tǒng)的處理過程也比較復(fù)雜，因此在協(xié)同操作過程中可能會發(fā)生數(shù)據(jù)交叉操作。如何在保證系統(tǒng)穩(wěn)定運行的同時，從根本上解決存儲系統(tǒng)的實時性問題，同時增加數(shù)據(jù)量和用戶，時延優(yōu)化逐漸成為計算機領(lǐng)域的研究熱點之一[1]。

趙晶等[2]提出了無線傳感器網(wǎng)絡(luò)多路徑傳輸時延優(yōu)化調(diào)度算法研究，基于傳感器網(wǎng)絡(luò)的多路徑傳輸形式，探索復(fù)制機制與重傳機制兩種路由容錯機制，并由此構(gòu)建出兩種多路徑傳輸資源優(yōu)化調(diào)度策略，實現(xiàn)數(shù)據(jù)成功傳輸?shù)耐瑫r降低傳輸時延；林兵等[3]根據(jù)混合云環(huán)境的數(shù)據(jù)布局特征與科學(xué)工作流數(shù)據(jù)之間的依賴關(guān)系，制定一種混合云環(huán)境下面向時延優(yōu)化的科學(xué)工作流數(shù)據(jù)布局策略，通過分析傳輸時延的影響因素，引入遺傳算法的變異算子與交叉算子，設(shè)計出自適應(yīng)離散粒子群算法，經(jīng)壓縮數(shù)據(jù)傳輸時延完成優(yōu)化處理。吳建明等[4]分析以單點數(shù)據(jù)采集為主的光伏發(fā)電遠程監(jiān)測系統(tǒng)，基于物聯(lián)網(wǎng)技術(shù)，對傳感器的原始數(shù)據(jù)進行區(qū)分量化融合處理，實時準(zhǔn)確地采集多通道數(shù)據(jù)，對數(shù)據(jù)采集輸出信道加以均衡控制，提高了診斷數(shù)據(jù)的準(zhǔn)確檢測和分析能力。

對此，本文構(gòu)建出一種關(guān)系化數(shù)據(jù)分塊存儲系統(tǒng)局部性時延優(yōu)化算法，在理論創(chuàng)新方面，建立了關(guān)系數(shù)據(jù)塊存儲系統(tǒng)中關(guān)系數(shù)據(jù)的鄰接關(guān)系，縮小了搜索范圍，簡化了計算過程和局部延遲優(yōu)化分析過程。

2 存儲系統(tǒng)關(guān)系化數(shù)據(jù)分塊方法

2.1 關(guān)系化數(shù)據(jù)分塊存儲系統(tǒng)結(jié)構(gòu)

關(guān)系數(shù)據(jù)塊存儲系統(tǒng)使用兩個SCSI(Small Computer System Interface)通道來完成與下一層的兩個分支的連接。統(tǒng)一存儲空間主要由虛擬設(shè)備驅(qū)動程序組成。作為系統(tǒng)的中間節(jié)點，每個單元控制器都有三個通道，一個是上行通道，另兩個是下行通道。SCSI從驅(qū)動程序和SCSI主驅(qū)動程序分別驅(qū)動上、下通道。系統(tǒng)的葉節(jié)點主要由磁盤結(jié)構(gòu)組成。為了充分發(fā)揮關(guān)系數(shù)據(jù)組織的結(jié)構(gòu)優(yōu)勢，最大限度地提高底層設(shè)備在數(shù)據(jù)傳輸中的并行性，并將其分塊存儲。如圖1所示，磁盤的編號順序是8個關(guān)系數(shù)據(jù)塊的存儲順序。通過分塊存儲，可以有效降低主機數(shù)據(jù)請求的影響，充分利用塊并行傳輸?shù)娜萘俊?/p>

圖1 關(guān)系化數(shù)據(jù)分塊存儲系統(tǒng)結(jié)構(gòu)示意圖

2.2 關(guān)系化數(shù)據(jù)分塊流程

2.2.1 關(guān)系化數(shù)據(jù)預(yù)處理

為了使數(shù)據(jù)滿足存儲要求，預(yù)處理可分為三個階段：關(guān)系數(shù)據(jù)鄰接關(guān)系的建立、數(shù)據(jù)法向量的預(yù)測和數(shù)據(jù)曲率的求解。在構(gòu)造關(guān)系數(shù)據(jù)的鄰接關(guān)系的過程中，通過尋找與當(dāng)前關(guān)系數(shù)據(jù)距離最短的K個數(shù)據(jù)來構(gòu)造K鄰域。當(dāng)關(guān)系數(shù)據(jù)量較大時，建立鄰接關(guān)系可以有效地減少搜索面積，簡化計算過程，降低計算量和復(fù)雜度，提高關(guān)系數(shù)據(jù)塊的存儲效率。關(guān)系化數(shù)據(jù)鄰域求解的具體過程描述如下：

1)利用數(shù)據(jù)個數(shù)總和、最小包圍盒體積以及鄰近數(shù)據(jù)個數(shù)[5-6]，計算柵格邊長，把最小包圍盒分成規(guī)格完全一樣的柵格；

2)根據(jù)非空柵格個數(shù)、柵格邊長以及數(shù)據(jù)個數(shù)總和，求解關(guān)系化數(shù)據(jù)與數(shù)據(jù)中心之間的距離均值。

3)依據(jù)解得的柵格邊長，再次劃分最小包圍盒為規(guī)格一致的柵格；

4)遍歷所有數(shù)據(jù)之后，把數(shù)據(jù)與柵格進行一一對應(yīng)地歸類；

5)基于柵格的位置坐標(biāo)，K鄰域搜索[7]關(guān)系化數(shù)據(jù)的附近柵格，實現(xiàn)關(guān)系化數(shù)據(jù)鄰域結(jié)構(gòu)構(gòu)建。

數(shù)據(jù)法矢預(yù)估階段的目的是提升關(guān)系化數(shù)據(jù)分塊的便捷度，利用最小二乘法，構(gòu)架下列數(shù)據(jù)法矢預(yù)估表達式

(1)

基于預(yù)估的數(shù)據(jù)法矢結(jié)果，進行數(shù)據(jù)曲率求解階段。假設(shè)數(shù)據(jù)曲面B=B(υ，?)，則該曲面的第一基本形式與第二基本形式可分別用下列各式描述

Ⅰ=Ευ2+2Fυ?+Γ?2

(2)

Ⅱ=Λυ2+2Μυ?+Ν?2

(3)

由上式推導(dǎo)得出數(shù)據(jù)曲率的計算公式，如下所示

(4)

2.2.2 關(guān)系化數(shù)據(jù)分塊存儲流程

假設(shè)W為預(yù)處理過的關(guān)系化數(shù)據(jù)集合，曲面集合B={b1，b2，…，bn}的組成部分是關(guān)系化數(shù)據(jù)集合W，曲面集合B的子集是H={h1，h2，…，hn}，其中，n表示構(gòu)成的曲面?zhèn)€數(shù)，當(dāng)關(guān)系化數(shù)據(jù)集合符合下列各式所示的約束條件時，關(guān)系化數(shù)據(jù)的正確數(shù)據(jù)分塊結(jié)果即為數(shù)據(jù)子集H

(5)

B(hi)=TRUE，ifandonlyΔ(γ(x′)，f(x′))≤ε

(6)

式中，第i個數(shù)據(jù)子集為hi，第j個數(shù)據(jù)子集為hj，當(dāng)兩子集為相鄰子集時用Nbr(hi，hj)表示，尺度函數(shù)為Δ(γ(x′)，f(x′))，表示函數(shù)γ(x′)與f(x′)之間的差值，數(shù)據(jù)曲面hi與hj的重疊部分用B(hi∩hj)表示，標(biāo)準(zhǔn)差值是ε。

利用上述方法分塊存儲關(guān)系化數(shù)據(jù)，能夠為存儲系統(tǒng)的網(wǎng)絡(luò)安全提供更有力的支撐。

3 存儲系統(tǒng)局部性時延優(yōu)化算法

假設(shè)關(guān)系化數(shù)據(jù)分塊存儲系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)用T表示，網(wǎng)絡(luò)主節(jié)點是S，分塊中的任意節(jié)點為t，則采用下列表達式界定從主節(jié)點到分塊節(jié)點的局部性時延

(7)

式中，與分塊節(jié)點t共享公共鏈路的損耗為Rkt，網(wǎng)絡(luò)結(jié)構(gòu)T中與節(jié)點t相鄰的節(jié)點是k，該節(jié)點的荷載為Ak。

由于無法提前預(yù)知主節(jié)點S到分塊節(jié)點t的實際路徑，計算量過于繁瑣，因此，導(dǎo)出局部性時延del(s，t)的上界Del(s，t)，簡化關(guān)系化數(shù)據(jù)分塊存儲系統(tǒng)中的局部性時延優(yōu)化分析過程，故得出下列表達式：

del(s，t)≤Del(s，t)=(Rd+r1L(s，t))(Am+c1W)

(8)

式中，Rd、Am分別表示存儲系統(tǒng)損耗與荷載，r1和c1分別表示節(jié)點之間的傳輸鏈路損耗與荷載。

在一個二維曼哈頓平面上建立關(guān)系化數(shù)據(jù)分塊存儲網(wǎng)絡(luò)結(jié)構(gòu)，整個網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖G=〈V，E〉的頂點集合屬于一個二維陣列，用V={v1，v2，…，vm}表示，相鄰頂點間的邊集合用E={e1，e2，…，em}表示。

如果存儲結(jié)構(gòu)T≤V為一個信號網(wǎng)引線端集合，通過在圖G上求解時延優(yōu)化的樹結(jié)構(gòu)，完成算法構(gòu)建，該樹連接結(jié)構(gòu)T的全部頂點，且存在局部性時延del(s，t)的最小值。

時延優(yōu)化算法的具體流程描述如下：

1)在圖G上架構(gòu)一個可以連接存儲結(jié)構(gòu)T中全部頂點的樹框架，根據(jù)局部性時延del(s，t)的上界Del(s，t)，極大程度最小化del(s，t)；

2)將結(jié)構(gòu)T含有的全部頂點設(shè)定成優(yōu)化算法的初始節(jié)點，當(dāng)前節(jié)點設(shè)定為正在分塊的節(jié)點vj∈V，當(dāng)算法開始運行時，當(dāng)前節(jié)點變?yōu)関i∈T；

3)假設(shè)當(dāng)前節(jié)點為vj∈V，該節(jié)點的坐標(biāo)是(xj，yj)，則與節(jié)點vj對應(yīng)的帶權(quán)重心Cj界定過程具體如下：

設(shè)定當(dāng)前節(jié)點集合R≤V，有vi∈R且i≠j

dij=(xj-xi)2+(yj-yi)2

(9)

(10)

(11)

(12)

式中，vj中帶權(quán)重心Cj的水平與垂直坐標(biāo)分別是xcj與ycj，權(quán)Dij的作用是令vj與vi節(jié)點帶權(quán)重心更接近，明確當(dāng)前節(jié)點方向[8]。

在構(gòu)建樹狀結(jié)構(gòu)的過程中，對每個步驟中的每個當(dāng)前節(jié)點進行處理，使節(jié)點在一個方向上增長一個線段，得到一個邊長e。一般來說，每個主節(jié)點S包括四個增長方向：上、下、左和右。如果節(jié)點沿著加權(quán)重心或主節(jié)點的生長方向生長，則可以減少局部延遲，因此，設(shè)置不同方向的不同權(quán)值。

4)假設(shè)當(dāng)前節(jié)點vj的帶權(quán)重心是Cj，節(jié)點鄰接邊是e，那么對應(yīng)于帶權(quán)重心Cj的權(quán)重表達式如下所示

wCj(e)=a1L(vj，Cj)

(13)

式中，L(vj，Cj)表示節(jié)點vj與帶權(quán)重心Cj間的最短距離，a1表示鄰接邊與帶權(quán)重心的方向關(guān)系，條件式如下所示

(14)

5)當(dāng)主節(jié)點S是存儲結(jié)構(gòu)中的關(guān)系化源點時，節(jié)點vj的鄰接邊是e，則對應(yīng)于主節(jié)點S的權(quán)值表達式如下所示

ws(e)=a2L(vj，s)

(15)

式中，L(vj，s)表示節(jié)點vj與主節(jié)點S間的最短距離，a2表示鄰接邊e與主節(jié)點S的方向關(guān)系，條件式如下所示

(16)

帶權(quán)重心與主節(jié)點的權(quán)值界定形式如圖2所示，在圖中用點O表示。

圖2 帶權(quán)重心與主節(jié)點的權(quán)值界定示意圖

根據(jù)式(11)，將上述兩個方向同時作為時延最小化指標(biāo)，采用合成方向界定相應(yīng)權(quán)值wcd，使時延最小化

wcd(∈)=g1wCj(e)+g2ws(e)

(17)

式中，g1與g2為權(quán)重系數(shù)[9-10]，滿足下列等式

g1+g2=1

(18)

通過調(diào)節(jié)權(quán)重系數(shù)g1與g2，能夠改變帶權(quán)重心與主節(jié)點權(quán)值在合成方向權(quán)值中的貢獻，令時延優(yōu)化更加合理、有效。

4 時延優(yōu)化算法模擬分析

4.1 實驗環(huán)境

為提升實驗數(shù)據(jù)的可靠性與真實度，以Kaggle( https：//www.kaggle.com/datasets )中某遠程監(jiān)測系的實際應(yīng)用數(shù)據(jù)為數(shù)據(jù)來源。表1為算法實現(xiàn)與實驗相關(guān)軟硬件配置。

表1 開發(fā)平臺配置統(tǒng)計表

分別采用文獻[2]、[3]、[4]方法以及本文算法展開仿真，通過各算法的節(jié)點生命周期、系統(tǒng)生命周期、通信距離以及局部性時延等實驗數(shù)據(jù)，驗證本文算法的有效性與可行性。

4.2 算法仿真評估

圖3為各算法的節(jié)點生命周期實驗結(jié)果曲線。

圖3 節(jié)點生命周期誤差曲線圖

根據(jù)圖3中，三種算法節(jié)點生命周期樣本方差與存儲系統(tǒng)所含節(jié)點個數(shù)的關(guān)系變化曲線圖中，文獻[4]方法在四種算法中擁有最大的節(jié)點生命周期樣本方差，這說明該方法令系統(tǒng)中所有節(jié)點之間的能耗都呈不均衡狀態(tài)；而本文算法通過尋找到與當(dāng)前關(guān)系化數(shù)據(jù)距離最短的K個數(shù)據(jù)，架構(gòu)了數(shù)據(jù)間的鄰接關(guān)系，縮小了節(jié)點搜索區(qū)域，故節(jié)點生命周期樣本方差最小，具有較好的能量均衡性能。

圖4為各算法的系統(tǒng)生命周期實驗結(jié)果曲線。

圖4 系統(tǒng)生命周期曲線圖

通過整個系統(tǒng)生命周期與節(jié)點個數(shù)之間的關(guān)系變化曲線圖即圖4可以看出，文獻[2]方法的系統(tǒng)生命周期最長，而本文算法主要以時延作為研究側(cè)重點，故在節(jié)點個數(shù)為0-45時的系統(tǒng)生命周期較短，但在節(jié)點個數(shù)為50時，系統(tǒng)生命周期依舊產(chǎn)生上升趨勢。

以實驗主機為原點，進行通信距離測試，各算法的通信距離實驗結(jié)果如圖5所示。

圖5 通信距離曲線圖

由圖5可知，由于本文算法在優(yōu)化時延過程中，考慮到了存儲系統(tǒng)與傳輸鏈路的損耗與荷載，因此，相較于文獻[2]、[3]、[4]方法，具有更理想的通信效果。

將存儲系統(tǒng)分為六個存儲階段，在局部性時延方面測試四種算法，仿真結(jié)果如圖6所示。

圖6 局部性時延曲線圖

圖6表示各算法在存儲過程里需要的時隙數(shù)與節(jié)點個數(shù)之間的關(guān)系變化曲線圖，從圖中曲線趨勢可知，文獻[2]、[3]、[4]方法的時延隨著節(jié)點個數(shù)的不斷變大而呈現(xiàn)出線性增長走勢，而本文算法通過建立最小化局部性時延的樹結(jié)構(gòu)，達成了極大程度令時延最小化的目標(biāo)，取得了較好的時延優(yōu)化效果。

5 結(jié)論

1)在實驗條件允許的情況下，深入探討局部性時延優(yōu)化方向，以局部性時延作為優(yōu)化目標(biāo)，對關(guān)系化數(shù)據(jù)的分塊存儲系統(tǒng)展開研究，在節(jié)點個數(shù)為50時，系統(tǒng)生命周期依舊產(chǎn)生上升趨勢，

2)將節(jié)點生命周期、系統(tǒng)生命周期、通信距離以及局部性時延作為優(yōu)化切入點，改進存儲系統(tǒng)性能，實驗中的最大通信距離為69米。

3)個人實驗設(shè)備具有一定的局限性，勢必會影響到實驗效果，在今后的工作中，應(yīng)繼續(xù)積極探索更好、更有效的方法，通過融合多種算法，架構(gòu)更大型、更仿真的實驗環(huán)境來驗證算法性能，使優(yōu)化效果進一步完善