天地一体化信息网络中一种混合存储管理策略
2015-06-23张更新
孔 博,张 威,张更新,胡 婧
(解放军理工大学通信工程学院,南京 210007)
专 题
天地一体化信息网络中一种混合存储管理策略
孔 博,张 威,张更新,胡 婧
(解放军理工大学通信工程学院,南京 210007)
分层自治域AS的提出解决了天地一体化信息网络因结构复杂、拓扑动态变化所带来的整网控制难题。针对AS组网特点及天地一体化信息网络内节点存储资源严重受限的问题,本文提出一种混合分布式存储管理策略。利用MDS编码产生冗余编码包,编码包存储过程分为AS间存储和AS内存储两部分。将AS间存储建模为最优数据分配问题,通过AS的可用性表征网络异构性,在AS间存储过程中,根据可用性向每个AS分发不同数量的编码包;在AS内部利用喷泉码对收到的编码包进行分布式存储。通过混合存储管理策略,将信息分散存储在整个天地一体化信息网络中,以期改善网络资源利用效率,同时提高数据存储可靠性。
天地一体化信息网络;分层自治域;分布式存储;异构网络;混合存储
0 引 言
纵观世界范围内,各类卫星通信系统的建设表现出各自为阵、独立建设的局面。各系统缺乏一般性、通用性和相互协作的能力,存在重复建设、“烟囱式”发展的不利局面,“天地一体化信息网络”概念的提出为解决上述问题提供了有效途径[1]。天地一体化信息网络是以多种空间平台为载体,实时获取、传输和处理空间信息的网络系统。作为国家重要基础设施,天地一体化信息网络在服务远洋航行、应急救援、航天测控等重大应用的同时,向下可支持高动态、宽带实时传输,向上可支持超远程、大时延可靠传输,从而将人类活动拓展至空间、远洋、乃至深空。相比传统卫星网络,天地一体化信息网络具有体系结构复杂、拓扑动态变化和自组织程度高等特征,某一局部范围内组网应用方式、拓扑结构的变化都会影响到全网的状态。结合未来天地一体化信息网络发展趋势,按照节点属性功能将整个网络划分为一系列由相似类型的节点组成的自治域[2],将高动态变化的天地一体化信息网络解耦和为局部具有弱动态性变化的准静态子网,从而将整网控制的问题简单化。
当前,空间信息系统所产生的数据信息呈指数级增长,根据 UCS Satellite database预测,到2020年,数据总量将是2010年数据总量的44倍[3,4]。而天地一体化信息网络节点资源严重受限,无法存储大量数据,当节点失效或传输节点双方长时间不可见时,会带来数据丢失问题。因此,如何有效的存储数据是天地一体化信息网络面临的一个巨大挑战。将存储技术和网络技术相结合,即“分布式存储”是一种行之有效的解决方案,它通过网络通信技术连接分散的存储节点,构建持久、高可用的冗余存储空间,存储海量数据[5]。数据冗余方法分为两类:基于复制冗余策略和基于网络编码冗余策略。复制冗余策略易于实现,但会消耗大量的存储空间,不适用于节点能量和存储能力有限,以及规模较大的网络。基于网络编码冗余策略由分布式纠删码冗余策略[6]发展而来的,在分布式纠删码(如Reed-Solomon码)冗余策略中,先将源文件进行分块编码,网络中单个存储节点只存储源文件的部分编码块,从而减少冗余存储开销,目的节点可通过接收一定数量的冗余数据来恢复原始数据。针对纠删码冗余存储修复失效节点时需下载全部原始数据,导致修复带宽过大的问题,Dimakis等人[7]将网络编码的思想引入节点修复过程,提出再生码[8]概念,优化了修复失效节点的带宽消耗。
本文以天地一体化信息网络信息存储为背景,以提高整网资源利用效率和信息存储可靠性为目标,根据AS组网特点,提出了一种混合分布式存储管理策略,利用MDS编码产生冗余编码包,编码包存储过程分为AS间存储和AS内存储两部分。将AS间存储建模为最优数据分配问题,通过AS的可用性表征网络异构性,在AS间存储过程中,根据可用性向每个AS分发不同数量的编码包;在AS内部利用喷泉码对收到的编码包进行分布式存储。通过混合存储管理策略,将信息分散存储在整个天地一体化信息网络中,以期改善网络资源利用效率,同时提高数据存储可靠性。
1 天地一体化信息网络分层自治域组网模型
如图1所示,天地一体化信息网络包含卫星、升空平台、传感器、用户等多种异构节点,其任务、功能、地位和分布空间具有明显的差异,同时,卫星的轨道运动、升空平台随气流的运动、多种用户终端的复杂运动、网络节点的增减等都会引起网络拓扑的动态变化,网络某一局部范围内组网应用方式、业务流量和流向、拓扑结构、信号传播环境等变化都会影响到全网的状态。如果对全网采用统一的网络管理与控制,将会使网络的运行效率极其低下,甚至因控制信息过多消耗带宽而难以正常运转。
图1 天地一体化信息网络组成
结合未来天地一体化信息网络中节点种类多、立体多层分布、异构特性明显、动态差异性大等特征,根据节点属性将天地一体化信息网络划分为一系列自治域,每个自治域内部通过中心节点进行独立的控制策略,不同自治域之间通过边界节点实现控制信息的交换,各自治域可根据需要再进行下一级子自治域的划分,从而构建分层自治域的组网结构。通过这种划分,将整体上是高动态变化的天地一体化信息网络解耦和为一个个局部具有弱动态性变化,由相似类型节点组成的准静态子网络,从而将整网控制的复杂问题简单化。如图2所示,将天地一体化信息网络划分为四个自治域,包括由各类卫星组成的AS-1,由高空平台站组成的AS-2,由低空飞机组成的AS-3以及地面各类节点组成的AS-4,各自治域又可划分为下一级子自治域(sub-AS)。通过将整个天地一体化信息网络进行分层处理,使网络各平台之间的相对运动引起的整体拓扑结构高动态变化去耦合为各自治域内部拓扑弱动态变化。部分自治域内的拓扑还有规律性、可预测性。各域之间的拓扑结构、路由关系和控制信息通过边界节点进行交换,并最终发送到地面运控中心站,地面运控中心站根据整个网络的拓扑结构和网络状态进行全网最优路由计算和选择,从而实现更加有效的网络管理和控制。
图2 天地一体化信息网络分层自治域划分
在前期工作中,团队针对天地一体化信息网络特点进行了自治域组网研究,同时对拓扑控制、时延优化、链路连通性等方面进行研究[23],本文考虑天地一体化信息网络内数据存储管理,不失一般性,我们将AS及sub-AS统称为AS。
2 混合存储管理策略
本节给出混合分布式存储方案。如图3所示,混合存储过程包括两部分:AS间信息存储和AS内信息存储。在AS间存储部分,每个AS作为一个整体,通过中心节点来接收信息。需要存储的源数据经过(n,k)MDS编码后生成n个编码包,根据网络异构性(通过不同AS间的可用性表征),给每个AS分配不同数量的编码包,从而改善网络存储可靠性,提高数据恢复概率,可以看出AS内信息存储等效为一个最优数据分配问题。中心节点每收到一个编码包,将其随机发送至域内某一节点进行存储,AS间编码包分配完成之后,网络进入AS内存储部分,AS内利用分布式喷泉编码技术,将收到的编码包在整个AS内进行冗余存储。AS间存储和AS内存储过程在下文进行具体说明。
图3 混合分布式存储过程
3 AS间信息存储
本节考虑AS间信息存储。首先将源文件分为k块,利用(n,k)MDS编码生成n个编码包,其中任意k个编码数据包可以恢复出源数据。根据每个AS可用性,分配不同数量的编码包,从而改善网络存储可靠性。首先对AS可用性即网络异构性进行说明,然后将AS间信息存储建模为一个整数规划问题,提出后续解决方案。
3.1 AS可用性表征
天地一体化信息网络包含多种异构节点,其任务、功能、分布空间具有明显的差异,根据节点属性将信息网络划分为一系列自治域AS,每个AS由相似类型节点组成准静态子网络。各平台路径损耗、覆盖区域、传播时延等方面存在明显差异,各因素对传输吞吐量会造成不同影响,由此组成的AS之间必然存在差异,整个网络体现出异构性。根据不同AS性能分配合理数量的编码包,对实现整个天地一体化信息网络负载均衡,改善网络存储可靠性及网络效率最大化具有促进作用。
综合考虑不同因素对AS性能影响,AS之间异构性通过可用性p来表征,拟考虑传播时延、传播损耗、多普勒频移、覆盖率对AS可用性的影响。AS-i的可用性表示为:
式中Delayi、Lossi、Doppleri、cov eragei分别表示传播时延、传播损耗、多普勒频移、覆盖率对该节点的影响,Wi(i=1,2,3,4)表示四个因素的权重系数,权重系数值越大,表明该权值所对应的因素对节点的可用性影响越大。
权重系数值及各影响因素值拟通过STK软件,通过多次仿真得到。思路如下:
(1)权重系数值由对应因素对传输吞吐量的影响来决定,分别仿真极限条件下吞吐量,通过多次仿真求平均值。
(2)每个因素对可用性的影响通过比较各种平台该因素对传输吞吐量的影响,通过多次仿真求平均值。
假设AS-i为由a个相似节点pij(j=1,2,…,a)组成的自治域,则AS-i的可用性为:
3.2 AS间信息存储过程
图4 AS间信息存储过程
AS间存储的目的是通过合理的数据包存储方式(w1,w2,…,ws),改善天地一体化信息网络存储可靠性,提高数据恢复概率。用ℑ(n,k,s)表示在n,k,s给定的条件下网络存储可靠性。则;
式中,r=(γ1,γ2,…,γs)∈Ω表示所有用户接入AS的集合,若用户可接入AS-i,则γi=1,反之则γi=0,i=1,2,…,s,用U表示可成功译码时的接入集
可以将AS间存储问题建模为如下的整数规划问题:
虽然该目标函数易于表述,但文献[9]证明求解该类规划问题是一个NP-hard问题。在下一步工作中,我们通过设计合适的启发式算法来求解。
4 AS内信息存储过程
本节以AS-i为例给出AS内数据分布式存储过程。在上节所述AS间存储过程中,中心节点每接收到一个编码包cj(j=1,2,…,wi),将其随机发送至域内某一节点,假设域内节点存储能力有限,只能存储一个编码包,因此不同的编码包发送至域内不同节点进行存储。中心节点分发编码包过程如图5所示。
图5 AS内中心节点分发编码包
在AS间存储过程完成后,即AS-i内中心节点完成编码包分发过程后,AS-i收到的wi个编码包分发至wi个不同的节点,此时进入AS内信息存储阶段。在AS内存储中,收到的wi个编码包相当于需要存储的原始数据包,为避免混淆,我们称之为数据包,并将此时存有数据包的节点称为数据节点,AS-i内共有wi个数据节点。AS模型如图6所示,假设AS-i由m个随机分布的同构节点组成(中心节点不参与AS内存储过程),每个节点根据其属性(例如MAC地址)被赋予一个唯一的ID,假设节点总数m远大于数据节点个数wi。每个节点具有相同的通信半径,记为d,处于通信半径之外的节点通过多跳连接通信。
图6 AS模型
拟利用喷泉码进行AS内数据存储,在喷泉码中,每个编码包由随机选取的原始数据包异或而成。在存储过程中,数据包利用随机漫步机制遍历AS内每个节点,每个节点根据喷泉码度分布函数选择一定数量的数据包异或并存储。当需要恢复原始数据时,中心节点可通过查询AS内若干个(k(1+ε),ε>0)节点,收集其编码包,译码恢复所有原始数据包。在编码阶段,每个数据包需要遍历AS内所有节点至少一次,可以通过预先设定数据包随机漫步步长实现[10]。
5 结 语
本文对天地一体化信息网络信息存储问题进行了研究。根据分层自治域组网特点,通过AS可用性表征整个网络异构性,提出了一种混合分布式存储策略,将整个信息存储过程分为AS间信息存储和AS内信息存储两部分,将AS间存储建模为整数规划问题,并在AS内存储过程中利用喷泉码提高译码概率。以期在改善网络资源利用效率的同时,提高网络数据存储可靠性。在下一步研究工作中,将对混合存储方案中各关键部分进行建模分析,包括AS可用性表征、设计AS间数据最优分配算法、AS内基于喷泉码的数据分布式存储仿真分析等。
[1] Miller L,Gorlick M,Wangerin D,etal.What’s coming on spacecraft:next-generation distributed satellite bus information systems[A].Aerospace Corporation[C]. 2012,22-27.
[2] 李飞龙,李广侠,李志强等.基于多层分簇的卫星导航系统拓扑结构设计[J].通信学报,35(10):2014,:31-41.
[3] Gengxin.Z,W.Zhang,H.Zhang,et al.A Novel Proposal of Architecture and Network Model for Space Communication Networks[C].IAF 65th International Astronautical Congress,2014:pp:1-7.
[4] 《中国电子科学研究院学报》编辑部.大数据时代[J].中国电子科学研究院学报,2013,8(1):27-31.
[5] Rhea S,Wells C,Eaton P,etal.Maintenance-free global data storage[J].IEEE Internet Comput,2001,:40-49.
[6] Weatherspoon H and Kubiaowicz J.Erasure coding vs. replication:A quantitative comparsion[J].In Proc.of IPTPS 02,Cambridge,Massachusetts,March 2002.
[7] Dimakis A G,Godfrey P B,Wainwright M,et al.Network coding for distributed storage systems[J].IEEE Trans Inf Theory,2010,56(9):4539-4551.
[8] Toni E,Codes Between MBR and MSR PointsWith Exact Repair Property[J].IEEE Transactions on Information Theory,2014,60(11):6993-7005.
[9] Derek L,Dimakis A G.Distributed Storage Allocations[J].IEEE Trans on Information Theory,2012,58(7):4733-4752.
[10]Cooper C,Frieze A.The cover time of random geometricgraphs[J].Random Structures and Algorithms,2011,38(3):324-349.
孔 博(1987—),男,陕西澄城人,博士生,主要研究方向为卫星通信,网络编码理论及其应用;
E-mail:kbvx_123@163.com
张 威(1987—),男,河南商丘人,博士生,主要研究方向为卫星通信,深空通信等;
张更新(1967—),男,浙江平湖人,教授,博士,博士生导师,研究方向为卫星通信,深空通信等;
胡 婧(1981—),女,湖北咸宁人,讲师,硕士,研究方向为卫星通信,信号处理等。
A Hybrid Storage M anagement Strategy for Space-Ground Integrated Information Network
KONG Bo,ZHANGWei,ZHANG Geng-xin,HU Jing
(College of Communication Engineering,PLA University of Science and Technology,Nanjing 210007,China)
Hierarchical autonomous system(AS)solves the problem of controlling the entire spaceground integrated information network(SGIIN)for whose high component complexity and dynamic.Aiming at the characteristics of the AS-oriented networking and the problem of storage resources of AS's node severely limited,we propose a hybrid storagemanagement strategy.The storage of encoded packets which are coded bymaximum distance separable(MDS)code includes two parts,namely,the intra-AS part and inter-ASpart.The intra-ASstorage ismodeled as an optimal data allocation problem,the heterogeneity is chartered by the availabilities among ASs,different number of packets are assigned to ASs according to its availability.Fountain codes is used to storage
packets distributed within AS.In order to improve the utilization efficiency of network resource and date storage reliability in expectation,information is scattered throughout the earth integrated information network through the hybrid storagemanagement strategy.
Earth Integrated Information Network;Autonomous System(AS);Distributed Storage;Heterogeneous Network;Hybrid Storage
TN393
A
1673-5692(2015)05-474-05
10.3969/j.issn.1673-5692.2015.05.005
2015-07-15
2015-09-20
国家自然科学基金资助项目(91338201,91438109,61401507)