樊玉瑩, 歸 琳, 宮 博

(上海交通大學(xué) 電子信息與電氣工程學(xué)院,上海 200240)

空間信息網(wǎng)絡(luò)中的資源映射與調(diào)度研究

樊玉瑩, 歸 琳, 宮 博

(上海交通大學(xué) 電子信息與電氣工程學(xué)院,上海 200240)

目前空間信息網(wǎng)絡(luò)中衛(wèi)星資源不盡相同,且衛(wèi)星節(jié)點(diǎn)的星間鏈路動(dòng)態(tài)變化,給資源映射造成困難,使得網(wǎng)絡(luò)資源利用不充分.如何實(shí)現(xiàn)空間資源利用的最大化,成為亟待解決的難題.為解決上述問(wèn)題,提供了一種方法:首先,將衛(wèi)星網(wǎng)絡(luò)可以提供的資源和任務(wù)指標(biāo)映射表達(dá)為多維矢量;再通過(guò)線性規(guī)劃,使資源矢量和任務(wù)矢量相匹配,從而使網(wǎng)絡(luò)資源能更充分地被利用.

空間信息網(wǎng)絡(luò); 資源映射; 資源調(diào)度

0 引 言

空間信息網(wǎng)絡(luò)是以空間平臺(tái)(包括同步衛(wèi)星或中、低軌道衛(wèi)星、平流層氣球和有人或無(wú)人駕駛飛機(jī)等)為載體,實(shí)時(shí)獲取、傳輸和處理空間信息的網(wǎng)絡(luò)系統(tǒng).其中,具有代表性的空間信息網(wǎng)絡(luò)建設(shè)實(shí)例包括:美國(guó)國(guó)家航空航天局(NASA)的空間傳感網(wǎng)、歐洲的哥白尼計(jì)劃、美國(guó)國(guó)家科學(xué)基金會(huì)(NSF)的國(guó)家生態(tài)觀測(cè)網(wǎng)絡(luò)以及俄聯(lián)邦航天計(jì)劃等[1-3].我國(guó)關(guān)于空間信息網(wǎng)絡(luò)的體系架構(gòu)已基本形成,以高軌衛(wèi)星(如中繼衛(wèi)星)為骨干,中/低軌衛(wèi)星和其他空天飛行器等作為用戶接入上述骨干網(wǎng),實(shí)現(xiàn)航天測(cè)控和應(yīng)急通信等空間任務(wù)的統(tǒng)一接入[4].以天基為主,地基為輔,實(shí)現(xiàn)以空間業(yè)務(wù)為驅(qū)動(dòng),對(duì)天地一體化資源的統(tǒng)一靈活管理、資源動(dòng)態(tài)共享與高效優(yōu)化調(diào)度[5](圖1).

圖1 空間信息網(wǎng)絡(luò)模型

目前國(guó)外很多機(jī)構(gòu)和組織都在持續(xù)、大力地開(kāi)展空間信息網(wǎng)絡(luò)相關(guān)技術(shù)的研究.國(guó)內(nèi)也有許多學(xué)者在該領(lǐng)域做了大量的研究工作,并取得了許多研究成果.然而,空間信息網(wǎng)絡(luò)是一個(gè)龐大而復(fù)雜的系統(tǒng),在資源映射和調(diào)度方面存在很多技術(shù)問(wèn)題有待進(jìn)一步解決.文獻(xiàn)[3]提出通過(guò)增強(qiáng)學(xué)習(xí)的方法實(shí)現(xiàn)在低地球軌道衛(wèi)星(LEO)網(wǎng)絡(luò)中的資源分配.文獻(xiàn)[6]提出在多媒體廣播業(yè)務(wù)中的包調(diào)度算法,來(lái)滿足不同的QoS需求.與這些文獻(xiàn)中的研究場(chǎng)景相比,空間信息網(wǎng)絡(luò)具有通信、計(jì)算、存儲(chǔ)等多維資源類型,其中通信還具有時(shí)域、頻域、空域等多種資源屬性,如果只是簡(jiǎn)單移植已有資源調(diào)度方法,運(yùn)算復(fù)雜度將會(huì)呈幾何倍數(shù)上升并消耗大量空間資源.

針對(duì)目前空間信息網(wǎng)絡(luò)骨干網(wǎng)中星間鏈路接入功能與傳輸性能的動(dòng)態(tài)化、星上通信-計(jì)算-存儲(chǔ)-載荷能力差異化等特點(diǎn),本研究首先對(duì)空間信息網(wǎng)絡(luò)的多種資源和任務(wù)進(jìn)行多維度的統(tǒng)一化資源表征.在空間信息網(wǎng)絡(luò)資源虛擬化的基礎(chǔ)上,通過(guò)線性規(guī)劃,進(jìn)行空間業(yè)務(wù)和空間資源的匹配,為空間業(yè)務(wù)動(dòng)態(tài)構(gòu)建一個(gè)具有安全和性能保障的虛擬資源匹配方案[7].

本研究如下:首先,考慮到空間信息網(wǎng)絡(luò)的資源多樣性,將當(dāng)前任務(wù)表達(dá)為對(duì)傳輸資源、存儲(chǔ)資源、處理資源的需求矢量,同時(shí)將每顆衛(wèi)星能提供的資源表達(dá)為此時(shí)所具備的傳輸能力、存儲(chǔ)能力、處理能力的矢量.在每個(gè)時(shí)隙的開(kāi)始,所有衛(wèi)星節(jié)點(diǎn)向地面控制中心發(fā)送自己的資源矢量和任務(wù)矢量(屬于控制信息,可以通過(guò)S波段完成).地面控制中心針對(duì)當(dāng)前任務(wù),建立虛擬網(wǎng)絡(luò)模型,通過(guò)線性規(guī)劃,確定處理和傳輸?shù)拈L(zhǎng)度[8-9].

1 資源映射與調(diào)度方法

本小節(jié)將具體闡述資源映射與調(diào)度的方法.首先將節(jié)點(diǎn)資源和任務(wù)表達(dá)為多維矢量;再針對(duì)任務(wù)節(jié)點(diǎn),在底層網(wǎng)絡(luò)的基礎(chǔ)上建立虛擬網(wǎng)絡(luò),虛擬網(wǎng)絡(luò)到物理網(wǎng)絡(luò)的映射滿足不同資源的約束;最后根據(jù)任務(wù)矢量的要求,利用線性規(guī)劃,將任務(wù)和資源相匹配,確定處理和傳輸?shù)娜蝿?wù)長(zhǎng)度.

1.1 網(wǎng)絡(luò)模型

在空間信息骨干網(wǎng)絡(luò)中,物理網(wǎng)絡(luò)的狀況由衛(wèi)星節(jié)點(diǎn)可以提供的資源表示[10].空間信息網(wǎng)絡(luò)的星間鏈路與節(jié)點(diǎn)資源是動(dòng)態(tài)變化的,在當(dāng)前時(shí)隙,底層網(wǎng)絡(luò)可以建模為賦權(quán)無(wú)向圖Gs=(Es,Ls,Ds,Ms,Ts),其中Es代表衛(wèi)星節(jié)點(diǎn)的集合;Ls代表鏈路的集合;Ds表示節(jié)點(diǎn)可用的CPU資源總量集合;MS表示節(jié)點(diǎn)可用的存儲(chǔ)資源總量集合;Ts表示節(jié)點(diǎn)能夠傳輸?shù)淖畲笏俾始?S表示底層網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量.

針對(duì)任務(wù)節(jié)點(diǎn)的虛擬網(wǎng)絡(luò),可以建模為賦權(quán)有向圖GI=(VI,ADI,AMI,ATI).其中,VI表示任務(wù)優(yōu)先級(jí)比當(dāng)前節(jié)點(diǎn)低的虛擬鄰居節(jié)點(diǎn)集合;ADI表示虛擬鄰居節(jié)點(diǎn)的有效CPU資源約束集合;AMI表示虛擬鄰居節(jié)點(diǎn)的有效存儲(chǔ)資源約束集合;ATI表示虛擬鄰居節(jié)點(diǎn)的有效接收速率約束集合;I表示虛擬網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量.Ts代表虛擬網(wǎng)絡(luò)請(qǐng)求的持續(xù)時(shí)間,在虛擬網(wǎng)運(yùn)行Ts后,底層網(wǎng)絡(luò)收回為任務(wù)分配的物理資源.假設(shè)節(jié)點(diǎn)1為任務(wù)節(jié)點(diǎn)建立虛擬網(wǎng)絡(luò),虛擬網(wǎng)絡(luò)到物理網(wǎng)絡(luò)的映射模型如圖2(a)所示,其中橢圓框表示節(jié)點(diǎn),連線表示兩節(jié)點(diǎn)為鄰居節(jié)點(diǎn),VDI、VMI、VTI是虛擬網(wǎng)絡(luò)節(jié)點(diǎn)可用的底層資源集合,分別代表CPU資源總量集合、存儲(chǔ)資源總量集合和最大傳輸速率集合.(VDI,VMI,VTI)到(Ds,Ms,Ts)的映射如圖2(b)所示.

圖2 資源映射模型

當(dāng)前衛(wèi)星節(jié)點(diǎn)的任務(wù)可以表達(dá)為完成該任務(wù)指標(biāo)的資源需求,并將具體分3個(gè)維度(L,Pr,R),其中L為任務(wù)的字節(jié)長(zhǎng)度,表示衛(wèi)星將要處理的任務(wù)大小;Pr為優(yōu)先級(jí),表示衛(wèi)星將要處理任務(wù)的重要程度,Pr值越小,優(yōu)先級(jí)越高,高優(yōu)先級(jí)任務(wù)可利用資源包括低優(yōu)先級(jí)任務(wù)資源和空資源;R為允許壓縮比,表示保證QoS最大的壓縮率.

1.2 調(diào)度模型

定義:

Com:表示節(jié)點(diǎn)O當(dāng)前時(shí)隙有效傳輸資源;

Li:表示每個(gè)虛擬鄰居節(jié)點(diǎn)的存儲(chǔ)和處理長(zhǎng)度總和,1≤i≤I;

Lo:表示當(dāng)前衛(wèi)星的傳輸和處理長(zhǎng)度總和.

假設(shè)網(wǎng)絡(luò)的狀態(tài)如下:

1)節(jié)點(diǎn)O為任務(wù)節(jié)點(diǎn),其任務(wù)為No_ass:(L,Pr,R),資源為No_sate:(Do,Mo,To);

2)在一個(gè)時(shí)隙內(nèi),節(jié)點(diǎn)的資源和星間鏈路不變.

虛擬網(wǎng)映射問(wèn)題可以定義為從虛擬網(wǎng)絡(luò)拓?fù)銰I到底層網(wǎng)絡(luò)拓?fù)銰s且滿足約束(ADI,AMI,ATI)的映射,約束的產(chǎn)生原因如下:

1)有效傳輸資源受O的最大傳輸速率及所有接收節(jié)點(diǎn)帶寬的限制;

2)虛擬鄰居節(jié)點(diǎn)的有效接收資源受當(dāng)前時(shí)隙O節(jié)點(diǎn)可用傳輸資源及節(jié)點(diǎn)本身接收能力的限制;

3)虛擬鄰居節(jié)點(diǎn)的有效存儲(chǔ)資源受本身的接收能力和存儲(chǔ)能力限制;

4)虛擬鄰居節(jié)點(diǎn)的有效處理資源受本身接收能力和處理能力的的限制.

約束條件的數(shù)學(xué)函數(shù)可以表示為:

Com=min{To,∑VTI},

(1)

ATI=min{VTI,Com},

(2)

AMI=min{TS×ATI,VMI},

(3)

ADI=min{TS×ATI,VDI}.

(4)

在上述網(wǎng)絡(luò)模型和映射協(xié)議的基礎(chǔ)上,具體的資源調(diào)度算法如下:

1)在時(shí)隙的開(kāi)始,所有衛(wèi)星節(jié)點(diǎn)向地面控制中心發(fā)送其任務(wù)情況和資源情況,地面控制中心通過(guò)查找任務(wù)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)及判斷優(yōu)先級(jí),構(gòu)建虛擬網(wǎng)絡(luò)拓?fù)?得到I個(gè)可利用鄰居節(jié)點(diǎn),用賦權(quán)有向圖GI=(VI,ADI,AMI,ATI)來(lái)表示.通過(guò)遍歷有向圖來(lái)完成每個(gè)虛擬節(jié)點(diǎn)的映射.

2)地面控制中心通過(guò)線性規(guī)劃,充分利用底層網(wǎng)絡(luò)的CPU資源和傳輸資源,使在當(dāng)前時(shí)隙內(nèi)任務(wù)的該變量最大.任務(wù)的改變量包括當(dāng)前衛(wèi)星的傳輸和處理長(zhǎng)度總和,加上每個(gè)鄰居衛(wèi)星的存儲(chǔ)和處理長(zhǎng)度總和.

所以線性規(guī)劃的目標(biāo)函數(shù)為:

(5)

其約束條件如下:

(6)

Li≤ADi+AMi,1≤i≤I,

(7)

(8)

在(6)式中,L×(1-R)為任務(wù)節(jié)點(diǎn)O壓縮處理掉的長(zhǎng)度,Com×TS為當(dāng)前時(shí)隙0可以傳輸?shù)拈L(zhǎng)度;(6)式表明,因?yàn)槿蝿?wù)節(jié)點(diǎn)的資源有限,Lo小于其壓縮處理的長(zhǎng)度及傳輸?shù)目傞L(zhǎng)度.在(7)式中,ADi、AMi分別為虛擬節(jié)點(diǎn)的有效處理和存儲(chǔ)能力;(7)式表明,因?yàn)楣?jié)點(diǎn)i受到虛擬網(wǎng)絡(luò)的約束,Li小于節(jié)點(diǎn)i有效處理和存儲(chǔ)的長(zhǎng)度.在(8)式中,L×R為O壓縮后的長(zhǎng)度;(8)式表明,所有虛擬鄰居節(jié)點(diǎn)的總處理和存儲(chǔ)長(zhǎng)度低于壓縮后的長(zhǎng)度和有效傳輸長(zhǎng)度的較小者.

2 舉 例

為了更好地闡述,本小節(jié)舉例說(shuō)明網(wǎng)絡(luò)的傳輸過(guò)程.

圖3 底層網(wǎng)絡(luò)拓?fù)鋱D

圖3展示了一個(gè)底層網(wǎng)絡(luò)拓?fù)?其中圓圈為衛(wèi)星節(jié)點(diǎn),連線表示兩個(gè)衛(wèi)星為鄰居節(jié)點(diǎn).假設(shè)B節(jié)點(diǎn)的任務(wù)為200 Mb的超清圖像傳輸,優(yōu)先級(jí)為最高優(yōu)先級(jí),且保證QoS最大壓縮率為70%.

在第一個(gè)時(shí)隙:所有衛(wèi)星節(jié)點(diǎn)向地面控制中心匯報(bào)其資源矢量及任務(wù)矢量.地面站計(jì)算各衛(wèi)星節(jié)點(diǎn)的鄰居節(jié)點(diǎn)及傳輸能力,然后調(diào)用算法完成任務(wù)的匹配.節(jié)點(diǎn)B先將200 Mb任務(wù)壓縮為140 Mb,將任務(wù)拆分發(fā)送給A、C節(jié)點(diǎn),A分60 Mb,C分80 Mb.時(shí)隙結(jié)束后網(wǎng)絡(luò)收回分配的資源.

第二時(shí)隙:所有衛(wèi)星節(jié)點(diǎn)向地面控制中心匯報(bào)其資源矢量及任務(wù)情況,比如此時(shí)A節(jié)點(diǎn)的任務(wù)是60 Mb,C是80 Mb.地面站計(jì)算各衛(wèi)星節(jié)點(diǎn)的鄰居節(jié)點(diǎn)及傳輸能力.將A、C節(jié)點(diǎn)的任務(wù)繼續(xù)拆分傳輸,直至任務(wù)到達(dá).

3 仿真及分析

本節(jié)中通過(guò)仿真證實(shí)所提出方法的有效性.在Matlab仿真實(shí)驗(yàn)環(huán)境下,首先設(shè)定衛(wèi)星節(jié)點(diǎn)數(shù)為10,隨機(jī)產(chǎn)生底層網(wǎng)絡(luò)且當(dāng)前底層網(wǎng)絡(luò)連接情況如圖4所示.其中,圓圈表示為衛(wèi)星節(jié)點(diǎn),連線表示兩衛(wèi)星節(jié)點(diǎn)為鄰居節(jié)點(diǎn).

圖4 底層網(wǎng)絡(luò)拓?fù)鋱D

表1給出了當(dāng)前時(shí)隙,所有衛(wèi)星節(jié)點(diǎn)的資源情況及任務(wù)的優(yōu)先級(jí).

表1 衛(wèi)星節(jié)點(diǎn)資源及任務(wù)優(yōu)先級(jí)

圖5 虛擬網(wǎng)絡(luò)模型

假設(shè)節(jié)點(diǎn)1為任務(wù)節(jié)點(diǎn),任務(wù)長(zhǎng)度為100 Mb,優(yōu)先級(jí)為1,且保證Qos最大壓縮率為70%,地面控制中心通過(guò)查找鄰居節(jié)點(diǎn)及任務(wù)優(yōu)先級(jí),發(fā)現(xiàn)2、8節(jié)點(diǎn)為虛擬鄰居節(jié)點(diǎn).在滿足映射約束的條件下,得到虛擬網(wǎng)絡(luò)模型,如圖5所示.圖5中方框表示為衛(wèi)星節(jié)點(diǎn).

通過(guò)調(diào)用上文中的算法,得到以下結(jié)果:Com的長(zhǎng)度為140 Mb,LO的長(zhǎng)度為100 Mb,L1的長(zhǎng)度為33 Mb,L2長(zhǎng)度為37 Mb.

可以看出,任務(wù)節(jié)點(diǎn)壓縮處理掉30 Mb,并將壓縮后的70 Mb傳送給虛擬鄰居節(jié)點(diǎn),節(jié)點(diǎn)2、8分別接收33 Mb和37 Mb.通過(guò)仿真,得到在此情況下,資源利用率較充分.

4 結(jié) 論

目前空間信息網(wǎng)絡(luò)的衛(wèi)星資源利用并不充分.本文在Matlab仿真環(huán)境下,把下一步可利用的衛(wèi)星資源和任務(wù)需求同時(shí)表達(dá)為多維矢量,按照任務(wù)構(gòu)建虛擬網(wǎng)絡(luò),通過(guò)線性規(guī)劃,將資源矢量和任務(wù)矢量相匹配.仿真結(jié)果表明,該算法可以有效地將任務(wù)需要的資源分配到鄰居衛(wèi)星上,得到各個(gè)衛(wèi)星存儲(chǔ)、處理和傳輸?shù)拈L(zhǎng)度.

[1] 楊紅俊.國(guó)外數(shù)據(jù)中繼衛(wèi)星系統(tǒng)最新發(fā)展及未來(lái)趨勢(shì) [J].電訊技術(shù),2016,56(1):109-116.

Yang H J.Latest development progress and trends of foreign data relay satellite systems [J].Telecommunication Engineering,2016,56(1):109-116.

[2] NASA.Tracking and data relay satellite system [EB/OL].(2017-2-13)[2017-2-13]https://www.nasa.gov/content/tdrs-overview

[3] Mukherjee J,Ramamurthy B.Communication technologies and architectures for space network and interplanetary internet [J].IEEE Communications Surveys & Tutorials,2013,15(2):881-897.

[4] 黃惠明,寇保華.以中繼衛(wèi)星系統(tǒng)為骨干的空間傳輸網(wǎng)絡(luò)體系 [J].飛行器測(cè)控學(xué)報(bào),2015,34(5):395-401.

Huang H M,Kou B H.Architecture of space information transmission network using TDRSS as its backbone [J].Journal of Spacecraft TT & C Technology,2015,34(5):395-401.

[5] 黃惠明,常呈武.天地一體化天基骨干網(wǎng)絡(luò)體系架構(gòu)研究 [J].中國(guó)電子科學(xué)研究院學(xué)報(bào),2015,10(5):460-467.

Huang H M,Chang C W.Architecture Research on space-based backbone network of space-ground integrated networks [J].Journal of China Academy of Electronics and Information Technology,2015,10(5):460-467.

[6] 王沖,景寧,李軍,等.一種基于多Agent強(qiáng)化學(xué)習(xí)的多星協(xié)同任務(wù)規(guī)劃算法 [J].國(guó)防科技大學(xué)學(xué)報(bào),2011,33(1):53-58.

Wang C,Jing N,Li J,et al.An algorithm of cooperative multiple satellites mission planning based on multi-agent reinforcement learning [J].Journal of national university of Defense technology,2011,33(1):53-58.

[7] 張飛陽(yáng).虛擬網(wǎng)絡(luò)資源映射若干關(guān)鍵技術(shù)研究與驗(yàn)證 [D].南京:南京郵電大學(xué),2016.

[8] Houidi I,Louati W,Zeghlache D,et al.Adaptive virtual network provisioning [C].ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures,New York,2010.

[9] Inführ J,Günther R.Raidl.Introducing the virtual network mapping problem with delay,routing and location constraints [J].Lecture Notes in Computer Science,2011,6701(6):105-117.

[10] 趙俊濤,徐四委,高輝.基于物聯(lián)網(wǎng)的資源映射算法研究 [J].四川理工學(xué)院學(xué)報(bào)(自科版),2012,25(2):43-46.

Zhao J T,Xu S W,Gao H.Research on resources mapping algorithm based on the internet of things [J].Journal of Sichuan University of Science & Engineering:Natural Science Edition,2012,25(2):43-46.

(責(zé)任編輯：包震宇,郁 慧)

Research on resource mapping and scheduling inspatial information virtual networks

Fan Yuying, Gui Lin, Gong Bo

(School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China)

The satellite resources in spatial information virtual networks are different,and the inter-satellite links of satellite nodes change dynamically,which lead to insufficient use of network resources.The question how to maximize the usage of the space resources should be solved rapidly.In order to solve these problems,this paper provides a method to express the resources and tasks provided by the satellite networks as multidimensional vector,then we match the vector of resources and tasks by the linear programming,thus we make full use of the resourcesin the network.

spatial information networks; resource mapping; resource scheduling

10.3969/J.ISSN.1000-5137.2017.01.018

2016-11-29

國(guó)家科技支撐課題(2015BAD17B04)

樊玉瑩(1994-),女,碩士研究生,主要從事衛(wèi)星網(wǎng)絡(luò)方面的研究.E-mail:fairing@sjtu.edu.cn

導(dǎo)師簡(jiǎn)介: 歸 琳(1975-),女,教授,主要從事高速移動(dòng)通信,寬帶機(jī)動(dòng)通信網(wǎng)、柵格通信網(wǎng)和下一代數(shù)字電視廣播技術(shù)方面的研究.E-mail:guilin@sjtu.edu.cn (通信聯(lián)系人)

TN 929.5

A

1000-5137(2017)01-0104-06