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

樊玉瑩, 歸 琳, 宮 博

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

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

樊玉瑩, 歸 琳, 宮 博

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

圖2 資源映射模型

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

1.2 調(diào)度模型

定義:

Com:表示節(jié)點O當前時隙有效傳輸資源;

Li:表示每個虛擬鄰居節(jié)點的存儲和處理長度總和,1≤i≤I;

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

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

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

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

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

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

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

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

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

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

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

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

(5)

其約束條件如下:

(6)

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

(7)

(8)

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

2 舉 例

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

圖3 底層網(wǎng)絡(luò)拓撲圖

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

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

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

3 仿真及分析

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

圖4 底層網(wǎng)絡(luò)拓撲圖

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

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

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

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

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

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

4 結(jié) 論

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

[1] 楊紅俊.國外數(shù)據(jù)中繼衛(wèi)星系統(tǒng)最新發(fā)展及未來趨勢 [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].飛行器測控學(xué)報,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].中國電子科學(xué)研究院學(xué)報,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強化學(xué)習(xí)的多星協(xié)同任務(wù)規(guī)劃算法 [J].國防科技大學(xué)學(xué)報,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] 張飛陽.虛擬網(wǎng)絡(luò)資源映射若干關(guān)鍵技術(shù)研究與驗證 [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é)報(自科版),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

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

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

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

TN 929.5

A

1000-5137(2017)01-0104-06