楊業(yè)令，鐘 璐，楊國(guó)才

(1.重慶工程學(xué)院計(jì)算機(jī)與物聯(lián)網(wǎng)學(xué)院，重慶 400056；2.西南大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院，重慶 400715)

1 引言

隨著信息技術(shù)的高速發(fā)展，數(shù)據(jù)管理已經(jīng)進(jìn)入了云計(jì)算的時(shí)代，云計(jì)算逐漸成為了IT行業(yè)的新發(fā)展趨勢(shì)，已經(jīng)受到了學(xué)術(shù)與工業(yè)界的廣泛關(guān)注。作為一種新型技術(shù)，能夠引導(dǎo)大量新型互聯(lián)網(wǎng)信息技術(shù)的發(fā)展，在云計(jì)算環(huán)境下，用戶只需要把自身的數(shù)據(jù)存儲(chǔ)到云端中，不再需要將自身數(shù)據(jù)儲(chǔ)存在自己的計(jì)算機(jī)里。云服務(wù)提供者憑借虛擬化技術(shù)、分布式計(jì)算與調(diào)度模型等方法為用戶供給軟件接口，使用戶能夠不受時(shí)間與地點(diǎn)限制，隨意使用任何網(wǎng)絡(luò)終端來(lái)訪問自己的數(shù)據(jù)，而用戶的損耗只是需要對(duì)服務(wù)與資源支付費(fèi)用。

云計(jì)算是一種以數(shù)據(jù)中心為基礎(chǔ)服務(wù)的設(shè)施，向用戶供給所需求的不同種類的應(yīng)用服務(wù)模型。隨著企業(yè)與用戶需求的高速上升以及云服務(wù)上的高速發(fā)展，傳統(tǒng)的集中式數(shù)據(jù)中心或原來(lái)分散獨(dú)立的數(shù)據(jù)中心已經(jīng)不能支撐日新月異的業(yè)務(wù)應(yīng)用。同時(shí)在傳統(tǒng)的觀念內(nèi)，為了使數(shù)據(jù)中心中承載的業(yè)務(wù)應(yīng)用永不宕機(jī)，提升IT資源的使用率，使資源能夠按需獲取，基于多數(shù)據(jù)中心的分布式云架構(gòu)逐漸興起，這種架構(gòu)也屬于云計(jì)算環(huán)境中的一種。在云計(jì)算環(huán)境下，多數(shù)據(jù)中心的分布式云架構(gòu)內(nèi)儲(chǔ)存著大量的數(shù)據(jù)，其中較為常見的數(shù)據(jù)即雙通道數(shù)據(jù)，而在調(diào)度這種數(shù)據(jù)的時(shí)候，由于數(shù)據(jù)自身存在的特性，導(dǎo)致調(diào)度算法容易受到奇異性的影響，致使這種數(shù)據(jù)無(wú)法被調(diào)度或調(diào)度存在誤差的情況。

針對(duì)上述問題，提出一種云計(jì)算環(huán)境下的雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度模型，通過分析雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度問題，得到雙通道數(shù)據(jù)的特性，組建數(shù)據(jù)空間組織并放置空間索引，獲取云計(jì)算系統(tǒng)的雙通道數(shù)據(jù)，把數(shù)據(jù)調(diào)度任務(wù)分化成若多個(gè)子任務(wù)，同時(shí)計(jì)算出調(diào)度任務(wù)量，隨后對(duì)任務(wù)量的極大值進(jìn)行計(jì)算，以此得到代價(jià)函數(shù)與估計(jì)函數(shù)，構(gòu)建LOD(Level of Detail，層次細(xì)節(jié))模型，調(diào)整云計(jì)算系統(tǒng)的更新速度使其能夠與雙通道數(shù)據(jù)達(dá)到平衡，最后，根據(jù)上述流程組建雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度模型，依靠該模型對(duì)數(shù)據(jù)進(jìn)行調(diào)度。

2 雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度模型設(shè)計(jì)

2.1 問題模型

2.1.1 問題描述

云計(jì)算即以數(shù)據(jù)中心為基礎(chǔ)的服務(wù)設(shè)施，向用戶供給其需求的應(yīng)用。通常來(lái)說(shuō)，云計(jì)算系統(tǒng)即憑借多種分布式的數(shù)據(jù)中心形成的，而每個(gè)數(shù)據(jù)中心會(huì)依靠一百多種機(jī)架組成，所有機(jī)架一般會(huì)通過1～20個(gè)物理服務(wù)器構(gòu)成。用戶對(duì)云計(jì)算系統(tǒng)的資源申請(qǐng)[1]可能隨時(shí)出現(xiàn)，云計(jì)算環(huán)境下雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度算法的任務(wù)就是調(diào)度合適的數(shù)據(jù)種類，以降低虛擬機(jī)之間的通信費(fèi)用，提升用戶應(yīng)用的最大化資源利用率和性能。

較為常見的雙通道數(shù)據(jù)中心內(nèi)部結(jié)構(gòu)：最底層機(jī)架中安放物理機(jī)，所有機(jī)架中都會(huì)具有一臺(tái)頂部交換機(jī)，最底層就是與外界進(jìn)行交互的路由器，最底層和最頂層之間通常都會(huì)具有多層交換裝置。期望中的安放方式，就是把用戶請(qǐng)求的虛擬機(jī)都放置在同一個(gè)物理機(jī)或機(jī)架內(nèi)，但是同一種機(jī)架或物理機(jī)內(nèi)并沒有充足的資源來(lái)滿足用戶的要求，并且由于用戶隨時(shí)都會(huì)產(chǎn)生請(qǐng)求，或因?yàn)槿蝿?wù)完成而退出云計(jì)算系統(tǒng)，就會(huì)導(dǎo)致云計(jì)算系統(tǒng)出現(xiàn)多個(gè)資源碎片，因此用戶請(qǐng)求的虛擬機(jī)可能分布在多個(gè)機(jī)架或物理機(jī)內(nèi)，甚至也可能會(huì)分布在多種數(shù)據(jù)中心內(nèi)。

另外，因?yàn)樵朴?jì)算系統(tǒng)自身存在防災(zāi)與容錯(cuò)的需求，或是用戶本身提出將虛擬機(jī)安放在多種數(shù)據(jù)中心或機(jī)架與物理機(jī)內(nèi)的需求[2]，都可能會(huì)使用戶的虛擬機(jī)不能安放在同一坐標(biāo)處。比如，用戶能夠在指定的數(shù)據(jù)中心里放置一定數(shù)量的虛擬機(jī)，以此來(lái)達(dá)到容錯(cuò)的目的，或是云計(jì)算系統(tǒng)也需要對(duì)數(shù)據(jù)中心內(nèi)的虛擬機(jī)最少放置量進(jìn)行限制，以此來(lái)縮減數(shù)據(jù)中心的通信流量。相同的，在存在要求的狀態(tài)下，能夠?qū)λ袛?shù)據(jù)中心與機(jī)架放置虛擬機(jī)的總量進(jìn)行限制。

2.1.2 問題建模

設(shè)定R(t)表示第t個(gè)用戶的虛擬機(jī)[4]之間雙通道數(shù)據(jù)距離的最大值

(1)

那么以最小化用戶的虛擬機(jī)內(nèi)雙通道數(shù)據(jù)直徑之和，作為最優(yōu)化目標(biāo)

(2)

該最小化雙通道數(shù)據(jù)直徑之和的目標(biāo)適用于單數(shù)據(jù)中心與多數(shù)據(jù)中心的狀況。

2.2 數(shù)據(jù)空間組織構(gòu)建

數(shù)據(jù)空間組織即對(duì)雙通道的空間數(shù)據(jù)進(jìn)行合理的規(guī)劃，同時(shí)組建空間索引，以提升雙通道數(shù)據(jù)的檢索速度，云計(jì)算環(huán)境下雙通道數(shù)據(jù)對(duì)象數(shù)量巨大，架構(gòu)復(fù)雜，所以在進(jìn)行可視化設(shè)計(jì)中，需要對(duì)其進(jìn)行剪裁，也就是需要在所有數(shù)據(jù)內(nèi)選取那些符合條件的數(shù)據(jù)，數(shù)據(jù)的選取自然不能離開空間索引[5]的構(gòu)建?？臻g索引即憑借空間對(duì)象的坐標(biāo)與形狀，遵照一定順序進(jìn)行排列的一種數(shù)據(jù)架構(gòu)。其中具有空間對(duì)象的基礎(chǔ)信息，例如對(duì)象表示、最小外包矩形等。針對(duì)空間索引，主要存在網(wǎng)格索引、四叉樹等。

云計(jì)算環(huán)境下的雙通道空間數(shù)據(jù)的組織，主要是使用網(wǎng)格劃分的形式，但雙通道數(shù)據(jù)因?yàn)槠渥陨泶嬖诓灰?guī)則性，使用網(wǎng)格劃分的形式，就必然會(huì)在網(wǎng)格的邊緣處生成大量的分割。但由于雙通道數(shù)據(jù)分布的偶然性[6]，使得各層加點(diǎn)容易出現(xiàn)重疊，致使實(shí)際運(yùn)行數(shù)據(jù)查詢時(shí)，會(huì)出現(xiàn)多種分支查詢，極大程度的降低了查詢的效率，所以也不太適合隨機(jī)分布的雙通道數(shù)據(jù)。

四叉樹即基于空間劃分組織索引架構(gòu)的一種索引機(jī)制。在內(nèi)存里的層次樹狀架構(gòu)內(nèi)，其查詢速度較快。本文方法需要在云計(jì)算環(huán)境內(nèi)動(dòng)態(tài)調(diào)度雙通道數(shù)據(jù)模型，而從樹架構(gòu)的復(fù)雜度與查詢速度等方面考慮，本文使用四叉樹索引架構(gòu)對(duì)雙通道數(shù)據(jù)進(jìn)行查詢與抽取。

組建四叉樹索引的基礎(chǔ)理念即：把數(shù)據(jù)儲(chǔ)存到完全能夠包含它的最小矩形節(jié)點(diǎn)內(nèi)，以此，每個(gè)組織就能夠只在數(shù)內(nèi)儲(chǔ)存1次，免除了儲(chǔ)存空間的浪費(fèi)，四叉樹索引構(gòu)建流程如下所示：

1)運(yùn)算所有數(shù)據(jù)鏈表內(nèi)的最小外包矩形，同時(shí)將其當(dāng)做根節(jié)點(diǎn)的最小外包矩形。

2)遍歷數(shù)據(jù)鏈表內(nèi)所有的數(shù)據(jù)，把根節(jié)點(diǎn)當(dāng)做目前節(jié)點(diǎn)，檢測(cè)最小外包矩形與目前節(jié)點(diǎn)的子節(jié)點(diǎn)[7]拓?fù)潢P(guān)聯(lián)。假如最小外包矩形和子節(jié)點(diǎn)的邊界相交，就把最小外包矩形引入目前節(jié)點(diǎn)內(nèi)，假如最小外包矩形在某種子節(jié)點(diǎn)內(nèi)部，那么把該子節(jié)點(diǎn)當(dāng)做目前節(jié)點(diǎn)，隨后迭代計(jì)算2)，直至子節(jié)點(diǎn)的最小外包矩形不會(huì)超過100。

使用四叉樹理念對(duì)云計(jì)算環(huán)境下的雙通道數(shù)據(jù)構(gòu)建空間索引，能夠高效的視域體裁剪，減少后期調(diào)度的計(jì)算量，縮短數(shù)據(jù)抽取與數(shù)據(jù)緩存的時(shí)間。

2.3 分區(qū)計(jì)算雙通道數(shù)據(jù)調(diào)度任務(wù)量

憑借式(3)可以運(yùn)算雙通道數(shù)據(jù)的總調(diào)度任務(wù)量為。

(3)

(4)

式中：S代表調(diào)度任務(wù)流程內(nèi)的任務(wù)量極大值，憑借式(5)可以運(yùn)算其代價(jià)函數(shù)

(5)

把式(5)引入式(3)之后，可以得到以下結(jié)果，具體公式為

(6)

(7)

把是(7)引入調(diào)度任務(wù)量運(yùn)算公式內(nèi)，可以獲得以下結(jié)果

(8)

憑借式(9)，可以完成調(diào)度流程內(nèi)子任務(wù)量的運(yùn)算

(9)

根絕上述的計(jì)算流程，可以對(duì)云計(jì)算環(huán)境內(nèi)雙通道數(shù)據(jù)調(diào)度內(nèi)的子任務(wù)量進(jìn)行運(yùn)算，進(jìn)而為調(diào)度模型的構(gòu)建供給精確的數(shù)據(jù)依據(jù)。

2.4 雙通道數(shù)據(jù)調(diào)度平衡

因?yàn)樵朴?jì)算系統(tǒng)更新的速度高于可預(yù)見數(shù)據(jù)的調(diào)度速度，嚴(yán)重干擾到調(diào)度的實(shí)時(shí)性與連貫性[10]，致使調(diào)度的停頓與延遲現(xiàn)象發(fā)生，所以保持?jǐn)?shù)據(jù)調(diào)度與云計(jì)算系統(tǒng)之間的動(dòng)態(tài)平衡對(duì)于數(shù)據(jù)調(diào)度的非常關(guān)鍵的。

在開始調(diào)度機(jī)制的同時(shí)，完全調(diào)入所有可預(yù)見的雙通道數(shù)據(jù)塊需要的時(shí)間是

TG=n1t1

(10)

式中：n1代表需要調(diào)度的雙通道數(shù)據(jù)塊數(shù)，t1代表調(diào)度一塊雙通道數(shù)據(jù)所消耗的時(shí)間。

在確保雙通道數(shù)據(jù)動(dòng)態(tài)平衡的前提下，數(shù)據(jù)調(diào)度的速率是1000/TG。調(diào)度一塊雙通道數(shù)據(jù)所需要消耗的時(shí)間能夠描述成

TR=N1T1

(11)

式中：N1代表需要調(diào)度的雙通道數(shù)據(jù)總量，T1代表調(diào)度一塊數(shù)據(jù)所消耗的時(shí)間。

對(duì)于數(shù)據(jù)調(diào)度來(lái)說(shuō)，理想的調(diào)度速度是1000/TR。在云計(jì)算系統(tǒng)更新速度達(dá)到24幀/s以上時(shí)，雙通道數(shù)據(jù)的實(shí)時(shí)調(diào)度才會(huì)較為通暢，所以，TR與TG需要同時(shí)小于1000/24m，才可以確保流暢的調(diào)度雙通道數(shù)據(jù)。而提升調(diào)度速度的方式存在兩種即：

1)在硬件方面需要充分使用CPU與GPU資源，免除在數(shù)據(jù)庫(kù)[11]內(nèi)進(jìn)行海量的計(jì)算，

2)在軟件方面，組建LOD模型。

LOD模型即指對(duì)同一環(huán)境內(nèi)的數(shù)據(jù)使用存在不同細(xì)節(jié)層次的一系列模型。構(gòu)建LOD模型可以有效縮減云計(jì)算系統(tǒng)數(shù)據(jù)庫(kù)內(nèi)多邊形的總量，進(jìn)而提升調(diào)度的速度。

當(dāng)前云計(jì)算系統(tǒng)的處理能夠能夠達(dá)到每秒處理100M的數(shù)據(jù)，其足以處理總量較大的雙通道數(shù)據(jù)。憑借云計(jì)算系統(tǒng)構(gòu)建時(shí)，會(huì)分塊的特性，使用LOD模型，即憑借雙通道數(shù)據(jù)塊距離視點(diǎn)的遠(yuǎn)近分化層次細(xì)節(jié)，每級(jí)以2的冪進(jìn)行精度遞減。這樣不僅運(yùn)算簡(jiǎn)單，還能夠充分利用云計(jì)算系統(tǒng)的組織方式，使數(shù)據(jù)調(diào)度的實(shí)現(xiàn)更加便捷。

2.5 雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度模型構(gòu)建

憑借上述對(duì)雙通道數(shù)據(jù)的處理，擬定動(dòng)態(tài)調(diào)度模型，其流程如圖1所示。

圖1 雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度流程

對(duì)于所有云計(jì)算環(huán)境下雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度單元，在高效時(shí)能夠分成多址協(xié)議下數(shù)據(jù)傳輸?shù)亩S平面調(diào)度離散采樣集合

P(ni)={pk|prkj=1，k=1，2，…，m}

(12)

節(jié)點(diǎn)鏈路[12]矩陣SN×L和節(jié)點(diǎn)時(shí)隙的雙通道數(shù)據(jù)包存在關(guān)聯(lián)，通過矩陣C描述前導(dǎo)時(shí)隙的雙通道數(shù)據(jù)調(diào)度空間矢量矩陣，C表示N×N的二維矩陣，在云計(jì)算網(wǎng)格內(nèi)兩條鄰節(jié)點(diǎn)的最大跳數(shù)是

(13)

針對(duì)距離是d，長(zhǎng)度是lb的網(wǎng)格節(jié)點(diǎn)，雙通道數(shù)據(jù)傳輸?shù)姆瞧娈惥仃嚌M足P∈Rn×n，R∈Rm×m與H∈Rm×n，云計(jì)算網(wǎng)格節(jié)點(diǎn)之間的多維性能能夠擬定成

E=[EG，ET，EW，EL]

(14)

使用時(shí)分多址協(xié)議進(jìn)行時(shí)隙均勻分配，在時(shí)隙均勻信道內(nèi)，信道利用率的描述式為

(15)

針對(duì)所有云計(jì)算環(huán)境下雙通道數(shù)據(jù)的調(diào)度單元，信道的利用率能夠描述成

(16)

在實(shí)現(xiàn)時(shí)隙的分配之后，在時(shí)間段T內(nèi)，進(jìn)行數(shù)據(jù)傳輸?shù)呢?fù)載均勻傳輸約束關(guān)系即

(17)

3 仿真證明

為了證明本文方法的有效性，需要對(duì)所提模型進(jìn)行驗(yàn)證，驗(yàn)證環(huán)境為：CPU設(shè)備4G內(nèi)存，100G自由空間硬盤，專用網(wǎng)卡2M，操作系統(tǒng)方面，憑借實(shí)現(xiàn)的需求，使用RedHatAS4。

實(shí)驗(yàn)流程，通過沒有使用調(diào)度模型與使用本文設(shè)計(jì)模型的情況下，云計(jì)算系統(tǒng)的雙通道數(shù)據(jù)平均吞吐率進(jìn)行實(shí)驗(yàn)，其結(jié)果進(jìn)行比對(duì)，其結(jié)果如圖2所示。

圖2 使用前后平均吞吐率中的對(duì)比

通過圖2能夠看出，在進(jìn)行雙通道數(shù)據(jù)調(diào)度的流程內(nèi)，網(wǎng)絡(luò)都會(huì)隨著數(shù)據(jù)量的提升，平均吞吐率也會(huì)出現(xiàn)上升，但是，使用所提調(diào)度模型下網(wǎng)絡(luò)吞吐效率要遠(yuǎn)遠(yuǎn)超過，同時(shí)其可以有效的確保動(dòng)態(tài)調(diào)度的調(diào)度時(shí)間與荷載負(fù)載率，其性能遠(yuǎn)超原始網(wǎng)絡(luò)。

為了進(jìn)一步證明所提模型的調(diào)度精確性，通過本文模型對(duì)一種，已知的雙通道調(diào)度數(shù)據(jù)進(jìn)行對(duì)比，其結(jié)果如圖3所示。

圖3 雙通道數(shù)據(jù)調(diào)度精確度

通過圖3能夠看出，本文所設(shè)計(jì)的模型調(diào)度的結(jié)果與已知調(diào)度結(jié)果相差不大，這是因?yàn)?，在本文所設(shè)計(jì)的雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度模型內(nèi)會(huì)增添，LOD模型，該模型能夠?qū)⑼粋€(gè)環(huán)境內(nèi)的數(shù)據(jù)，根據(jù)不同細(xì)節(jié)層次的模塊進(jìn)行統(tǒng)一平衡，使的調(diào)度模型，不會(huì)因?yàn)樵朴?jì)算系統(tǒng)更新速度過快，而導(dǎo)致數(shù)據(jù)調(diào)度出現(xiàn)停頓與延遲的情況。極大程度的提高的雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度模型的精度精確性。

4 結(jié)束語(yǔ)

為了提升云計(jì)算系統(tǒng)的進(jìn)程管理效率與負(fù)載均衡性，提出一種云計(jì)算環(huán)境下的雙通道數(shù)據(jù)動(dòng)態(tài)調(diào)度模型，通過數(shù)據(jù)空間組織與LOD模型，構(gòu)建模型，依靠該模型實(shí)現(xiàn)對(duì)數(shù)據(jù)的動(dòng)態(tài)調(diào)度。雖然所提模型在數(shù)據(jù)動(dòng)態(tài)調(diào)度中，取得了較為理想的結(jié)果，但由于所設(shè)計(jì)的模型主要針對(duì)雙通道數(shù)據(jù)種類，而數(shù)據(jù)的類型非常復(fù)雜，其中數(shù)據(jù)的種類也多種多樣，本文所設(shè)計(jì)的模型，并沒有在其它種類的數(shù)據(jù)中應(yīng)用過，因此下一步的研究即：將所提模型應(yīng)用在其它種類的數(shù)據(jù)內(nèi)，并更加數(shù)據(jù)類型實(shí)時(shí)調(diào)整與改進(jìn)模型的參數(shù)，使其能夠與多種類型的數(shù)據(jù)匹配。