空间信息网络中的资源映射与调度研究

樊玉莹, 归 琳, 宫 博

(上海交通大学 电子信息与电气工程学院,上海 200240)

空间信息网络中的资源映射与调度研究

樊玉莹, 归 琳, 宫 博

(上海交通大学 电子信息与电气工程学院,上海 200240)

目前空间信息网络中卫星资源不尽相同,且卫星节点的星间链路动态变化,给资源映射造成困难,使得网络资源利用不充分.如何实现空间资源利用的最大化,成为亟待解决的难题.为解决上述问题,提供了一种方法:首先,将卫星网络可以提供的资源和任务指标映射表达为多维矢量;再通过线性规划,使资源矢量和任务矢量相匹配,从而使网络资源能更充分地被利用.

空间信息网络; 资源映射; 资源调度

0 引 言

空间信息网络是以空间平台(包括同步卫星或中、低轨道卫星、平流层气球和有人或无人驾驶飞机等)为载体,实时获取、传输和处理空间信息的网络系统.其中,具有代表性的空间信息网络建设实例包括:美国国家航空航天局(NASA)的空间传感网、欧洲的哥白尼计划、美国国家科学基金会(NSF)的国家生态观测网络以及俄联邦航天计划等[1-3].我国关于空间信息网络的体系架构已基本形成,以高轨卫星(如中继卫星)为骨干,中/低轨卫星和其他空天飞行器等作为用户接入上述骨干网,实现航天测控和应急通信等空间任务的统一接入[4].以天基为主,地基为辅,实现以空间业务为驱动,对天地一体化资源的统一灵活管理、资源动态共享与高效优化调度[5](图1).

图1 空间信息网络模型

目前国外很多机构和组织都在持续、大力地开展空间信息网络相关技术的研究.国内也有许多学者在该领域做了大量的研究工作,并取得了许多研究成果.然而,空间信息网络是一个庞大而复杂的系统,在资源映射和调度方面存在很多技术问题有待进一步解决.文献[3]提出通过增强学习的方法实现在低地球轨道卫星(LEO)网络中的资源分配.文献[6]提出在多媒体广播业务中的包调度算法,来满足不同的QoS需求.与这些文献中的研究场景相比,空间信息网络具有通信、计算、存储等多维资源类型,其中通信还具有时域、频域、空域等多种资源属性,如果只是简单移植已有资源调度方法,运算复杂度将会呈几何倍数上升并消耗大量空间资源.

针对目前空间信息网络骨干网中星间链路接入功能与传输性能的动态化、星上通信-计算-存储-载荷能力差异化等特点,本研究首先对空间信息网络的多种资源和任务进行多维度的统一化资源表征.在空间信息网络资源虚拟化的基础上,通过线性规划,进行空间业务和空间资源的匹配,为空间业务动态构建一个具有安全和性能保障的虚拟资源匹配方案[7].

本研究如下:首先,考虑到空间信息网络的资源多样性,将当前任务表达为对传输资源、存储资源、处理资源的需求矢量,同时将每颗卫星能提供的资源表达为此时所具备的传输能力、存储能力、处理能力的矢量.在每个时隙的开始,所有卫星节点向地面控制中心发送自己的资源矢量和任务矢量(属于控制信息,可以通过S波段完成).地面控制中心针对当前任务,建立虚拟网络模型,通过线性规划,确定处理和传输的长度[8-9].

1 资源映射与调度方法

本小节将具体阐述资源映射与调度的方法.首先将节点资源和任务表达为多维矢量;再针对任务节点,在底层网络的基础上建立虚拟网络,虚拟网络到物理网络的映射满足不同资源的约束;最后根据任务矢量的要求,利用线性规划,将任务和资源相匹配,确定处理和传输的任务长度.

1.1 网络模型

在空间信息骨干网络中,物理网络的状况由卫星节点可以提供的资源表示[10].空间信息网络的星间链路与节点资源是动态变化的,在当前时隙,底层网络可以建模为赋权无向图Gs=(Es,Ls,Ds,Ms,Ts),其中Es代表卫星节点的集合;Ls代表链路的集合;Ds表示节点可用的CPU资源总量集合;MS表示节点可用的存储资源总量集合;Ts表示节点能够传输的最大速率集合,S表示底层网络节点数量.

针对任务节点的虚拟网络,可以建模为赋权有向图GI=(VI,ADI,AMI,ATI).其中,VI表示任务优先级比当前节点低的虚拟邻居节点集合;ADI表示虚拟邻居节点的有效CPU资源约束集合;AMI表示虚拟邻居节点的有效存储资源约束集合;ATI表示虚拟邻居节点的有效接收速率约束集合;I表示虚拟网络节点数量.Ts代表虚拟网络请求的持续时间,在虚拟网运行Ts后,底层网络收回为任务分配的物理资源.假设节点1为任务节点建立虚拟网络,虚拟网络到物理网络的映射模型如图2(a)所示,其中椭圆框表示节点,连线表示两节点为邻居节点,VDI、VMI、VTI是虚拟网络节点可用的底层资源集合,分别代表CPU资源总量集合、存储资源总量集合和最大传输速率集合.(VDI,VMI,VTI)到(Ds,Ms,Ts)的映射如图2(b)所示.

图2 资源映射模型

当前卫星节点的任务可以表达为完成该任务指标的资源需求,并将具体分3个维度(L,Pr,R),其中L为任务的字节长度,表示卫星将要处理的任务大小;Pr为优先级,表示卫星将要处理任务的重要程度,Pr值越小,优先级越高,高优先级任务可利用资源包括低优先级任务资源和空资源;R为允许压缩比,表示保证QoS最大的压缩率.

1.2 调度模型

定义:

Com:表示节点O当前时隙有效传输资源;

Li:表示每个虚拟邻居节点的存储和处理长度总和,1≤i≤I;

Lo:表示当前卫星的传输和处理长度总和.

假设网络的状态如下:

1)节点O为任务节点,其任务为No_ass:(L,Pr,R),资源为No_sate:(Do,Mo,To);

2)在一个时隙内,节点的资源和星间链路不变.

虚拟网映射问题可以定义为从虚拟网络拓扑GI到底层网络拓扑Gs且满足约束(ADI,AMI,ATI)的映射,约束的产生原因如下:

1)有效传输资源受O的最大传输速率及所有接收节点带宽的限制;

2)虚拟邻居节点的有效接收资源受当前时隙O节点可用传输资源及节点本身接收能力的限制;

3)虚拟邻居节点的有效存储资源受本身的接收能力和存储能力限制;

4)虚拟邻居节点的有效处理资源受本身接收能力和处理能力的的限制.

约束条件的数学函数可以表示为:

Com=min{To,∑VTI},

(1)

ATI=min{VTI,Com},

(2)

AMI=min{TS×ATI,VMI},

(3)

ADI=min{TS×ATI,VDI}.

(4)

在上述网络模型和映射协议的基础上,具体的资源调度算法如下:

1)在时隙的开始,所有卫星节点向地面控制中心发送其任务情况和资源情况,地面控制中心通过查找任务节点的邻居节点及判断优先级,构建虚拟网络拓扑,得到I个可利用邻居节点,用赋权有向图GI=(VI,ADI,AMI,ATI)来表示.通过遍历有向图来完成每个虚拟节点的映射.

2)地面控制中心通过线性规划,充分利用底层网络的CPU资源和传输资源,使在当前时隙内任务的该变量最大.任务的改变量包括当前卫星的传输和处理长度总和,加上每个邻居卫星的存储和处理长度总和.

所以线性规划的目标函数为:

(5)

其约束条件如下:

(6)

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

(7)

(8)

在(6)式中,L×(1-R)为任务节点O压缩处理掉的长度,Com×TS为当前时隙0可以传输的长度;(6)式表明,因为任务节点的资源有限,Lo小于其压缩处理的长度及传输的总长度.在(7)式中,ADi、AMi分别为虚拟节点的有效处理和存储能力;(7)式表明,因为节点i受到虚拟网络的约束,Li小于节点i有效处理和存储的长度.在(8)式中,L×R为O压缩后的长度;(8)式表明,所有虚拟邻居节点的总处理和存储长度低于压缩后的长度和有效传输长度的较小者.

2 举 例

为了更好地阐述,本小节举例说明网络的传输过程.

图3 底层网络拓扑图

图3展示了一个底层网络拓扑,其中圆圈为卫星节点,连线表示两个卫星为邻居节点.假设B节点的任务为200 Mb的超清图像传输,优先级为最高优先级,且保证QoS最大压缩率为70%.

在第一个时隙:所有卫星节点向地面控制中心汇报其资源矢量及任务矢量.地面站计算各卫星节点的邻居节点及传输能力,然后调用算法完成任务的匹配.节点B先将200 Mb任务压缩为140 Mb,将任务拆分发送给A、C节点,A分60 Mb,C分80 Mb.时隙结束后网络收回分配的资源.

第二时隙:所有卫星节点向地面控制中心汇报其资源矢量及任务情况,比如此时A节点的任务是60 Mb,C是80 Mb.地面站计算各卫星节点的邻居节点及传输能力.将A、C节点的任务继续拆分传输,直至任务到达.

3 仿真及分析

本节中通过仿真证实所提出方法的有效性.在Matlab仿真实验环境下,首先设定卫星节点数为10,随机产生底层网络且当前底层网络连接情况如图4所示.其中,圆圈表示为卫星节点,连线表示两卫星节点为邻居节点.

图4 底层网络拓扑图

表1给出了当前时隙,所有卫星节点的资源情况及任务的优先级.

表1 卫星节点资源及任务优先级

图5 虚拟网络模型

假设节点1为任务节点,任务长度为100 Mb,优先级为1,且保证Qos最大压缩率为70%,地面控制中心通过查找邻居节点及任务优先级,发现2、8节点为虚拟邻居节点.在满足映射约束的条件下,得到虚拟网络模型,如图5所示.图5中方框表示为卫星节点.

通过调用上文中的算法,得到以下结果:Com的长度为140 Mb,LO的长度为100 Mb,L1的长度为33 Mb,L2长度为37 Mb.

可以看出,任务节点压缩处理掉30 Mb,并将压缩后的70 Mb传送给虚拟邻居节点,节点2、8分别接收33 Mb和37 Mb.通过仿真,得到在此情况下,资源利用率较充分.

4 结 论

目前空间信息网络的卫星资源利用并不充分.本文在Matlab仿真环境下,把下一步可利用的卫星资源和任务需求同时表达为多维矢量,按照任务构建虚拟网络,通过线性规划,将资源矢量和任务矢量相匹配.仿真结果表明,该算法可以有效地将任务需要的资源分配到邻居卫星上,得到各个卫星存储、处理和传输的长度.

[1] 杨红俊.国外数据中继卫星系统最新发展及未来趋势 [J].电讯技术,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] 黄惠明,寇保华.以中继卫星系统为骨干的空间传输网络体系 [J].飞行器测控学报,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] 黄惠明,常呈武.天地一体化天基骨干网络体系架构研究 [J].中国电子科学研究院学报,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强化学习的多星协同任务规划算法 [J].国防科技大学学报,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] 张飞阳.虚拟网络资源映射若干关键技术研究与验证 [D].南京:南京邮电大学,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] 赵俊涛,徐四委,高辉.基于物联网的资源映射算法研究 [J].四川理工学院学报(自科版),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.

(责任编辑：包震宇,郁 慧)

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-),女,硕士研究生,主要从事卫星网络方面的研究.E-mail:fairing@sjtu.edu.cn

导师简介: 归 琳(1975-),女,教授,主要从事高速移动通信,宽带机动通信网、栅格通信网和下一代数字电视广播技术方面的研究.E-mail:guilin@sjtu.edu.cn (通信联系人)

TN 929.5

A

1000-5137(2017)01-0104-06