基于压缩感知的空间信息网络拥塞监测

张 凌, 归 琳, 宫 博, 罗汉文

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

基于压缩感知的空间信息网络拥塞监测

张 凌, 归 琳, 宫 博, 罗汉文

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

在空间信息网络中,各卫星间是通过星间链路(Inter Satellite Links,ISLs)相连接的,其空间网络节点的处理能力和资源存储能力受限,网络拓扑具有高动态性,通信链路存在间歇性连接.这造成空间网络节点出现高排队时延的情况,导致网络拥塞甚至丢包,空间数据传输的可靠性下降.为了高效准确地实现网络拥塞监测,本文作者分析了空间信息网络的链路稀疏性,结合其传输方式,将链路状态检测建模为压缩感知问题,并以贪婪算法求解链路延时,进而定位拥塞链路.仿真结果证明,这种链路状态检测算法可以在较少的采样数据量的情况下,以较高的精度恢复链路延时.

拥塞监测; 压缩感知; 贪婪算法

0 引 言

空间信息网络是以空间平台为载体,实时获取、传输和处理空间信息的网络系统,除了给导航、定位、测控等重大应用提供服务,向下可支持对地观测的高动态、宽带实时传输,向上可支持深空探测的超远程、大延时可靠传输,近年来已经成为全球范围的研究热点.空间信息网具有覆盖面广、组网灵活、不受地理位置限制等突出优势.但是由于星载、机载网络设备体积小、质量轻,空间网络节点的处理能力和存储资源能力都很有限,再加上网络拓扑结构的动态变化以及通信链路的间歇性连接,导致出现报文必须在中间节点存储相当长时间(排队时延高)的情况,这就造成空间网络节点容易发生拥塞甚至丢包,严重降低了空间数据传输的可靠性.因此,拥塞监测问题已经成为空间信息网络的重要问题之一.

为了高效准确地实现网络监测,一些学者提出了基于压缩感知的链路检测方法,以降低网络链路的检测开销[1].文献[2]和[3]分别提出基于加性度量算法和网络编码的网络链路状况监测模型,文献[4]提出基于压缩感知的方法,检测链路的时延和丢包率.但是,由于空间信息网络存在链路延时长、网络拓扑结构动态变化等特点,如何将上述方法应用于空间信息网络中还存在着巨大的挑战.由此可见,设计一种高效、可靠的空间信息网络管控实现机制,是需要解决的一个重要问题.

本文作者为了高效准确地实现空间信息网络中的拥塞监测,根据空间信息网络的链路特性,分析了空间信息网络链路状态的稀疏特性,结合空间信息网络的传输方式,将链路状态检测建模为压缩感知问题,进而以Matlab为工具用正交匹配追踪算法对空间信息网络的排队延时进行恢复仿真,并对仿真结果做总体的分析得出结论.

1 稀疏性分析

为了更好地进行空间信息网链路监测,本节根据对空间信息网络中的链路特性研究,分析了链路排队延时的稀疏性,为压缩感知模型的引入奠定基础.

表1 空间信息网络链路时延 ms

实现空间信息网链路监测,最直接的手段是获取每个链路的时延情况,这不仅能提供拥塞发生的具体位置,还能描述拥塞的严重程度.由于空间信息网中,接入链路和星间链路存在差异性,本文作者对空间信息网络中的接入链路和星间链路特性进行了调研和分析.表1整理出空间信息网络链路延时状况.

从表1中可以看出,链路时延t由三部分构成,传输时延tr、传播时延tp以及排队时延tq,即:t=tr+tp+tq.假设T为各链路的时延矢量T=(t1,t2,…,tN),ti(i∈[1,N])为链路i的时延;Tr为各链路的传输时延矢量Tr=(tr1,tr2,…,trN),tri(i∈[1,N])为链路i的传输时延;Tp为各链路的传播时延矢量Tp=(tp1,tp2,…,tpN),tpi(i∈[1,N])为链路i的传播时延;Tq为各链路的排队时延矢量Tq=(tq1,tq2,…,tqN),tqi(i∈[1,N])为链路i的排队时延.从表1中可见,与传输时延和传播时延相比,排队时延是有量级上的差异的,由于仅发生在拥塞时会引发链路的不断重传从而导致较大的排队时延,则可以认为各链路的排队时延Tq=T-Tr-Tp可以构成稀疏矢量.对于Tr=(tr1,tr2,…,trN),其中的接入链路为100ms,星间链路是0.其传播时延矢量Tp=(tp1,tp2,…,tpN),各元素均为常数.

由于空间信息网络规模大、链路多,通过大量的延时数据采集确实能够准确地得到链路拥塞的具体位置,但是这种方法需求的数据量大、效率低.本研究基于排队延时矢量的稀疏性,考虑利用压缩感知的方法,减少需要采集的数据量.

2 模型建立

图1 网络模型

(1)

(2)

式中R是测量矩阵,其元素为1时,表示该元素所在行对应的路径经过所在列对应的链路.

推广到实际的大规模空间信息网络中,仍然可以用式(1)表达路径时延与链路时延的关系,并且式中各个量仍保持原有的物理意义:y是M维列向量,代表M条路径的时延;T是N维列向量,代表N条链路的时延,是整个网络的链路时延集合;R是M×N维矩阵,列数N是网络中的链路总数,其大小由网络规模决定,行数M是选中的采样路径数,M通常小于N,通过第三节的仿真实验中可以看出,行数的选取数量很大程度上取决于网络发生拥塞的稀疏性情况,矩阵元素的取值为1或0,取决于采样路径是否经过对应的链路.由于链路时延矢量可以表达为:T=Tr+Tp+Tq,而其中的排队时延矢量Tq存在稀疏性,因此采用压缩感知的方法[5]恢复各路径排队时延的过程如下:

步骤一:在空间信息网络中随机地选取M条采样路径,根据这些路径经过的链路得到测量矩阵RM×N.

步骤二:根据步骤一中选取的路径,分别测量这些路径的总时延得到路径时延矢量y;根据各链路的特性得到链路传输时延矢量Tr和链路传播时延矢量Tp.

步骤三:根据压缩感知模型y-RTr-RTp=RTq,采用恢复算法得到链路排队时延矢量Tq.

可以发现测量矩阵R是随机选定的,Tr和Tp是由空间信息网络自身决定的,实际要测的数据仅仅是路径时延矢量y,并且这些量往往很容易测得、数据量也不大.

3 仿真实验

本文作者以Matlab为工具进行仿真,模拟恢复空间信息网络中各链路排队时延的过程,通过三次仿真实验,对比恢复的准确度讨论空间信息网络的总链路数(测量矩阵R的列数N)、路径时延数据采集量(测量矩阵R的行数M)、链路排队时延稀疏度(链路排队时延矢量Tq的稀疏度K)对恢复性能产生的影响.各仿真实验的基本步骤如下:

步骤一:产生一个M×N的测量矩阵R,矩阵元素相互独立且服从等概的两点分布;

步骤二:产生一个N维列向量Tq,其稀疏度为K,非零元素位置随机;

步骤三:得到N维列向量Y=RTq;

在OMP算法中,以一个全零的列向量为起始(稀疏度为0),在每一次循环中将一个零元素变为非零元素(稀疏度加1),使得改变后的列向量左乘测量矩阵R后与目标列向量Y的欧氏距离达到最小,经过K次循环后恢复出稀疏度为K的列向量.

三次仿真实验如下:

仿真实验1:为了探究固定采样数据量在不同网络规模下的网络监测性能,保持发生拥塞的链路数,即链路延时矢量Tq的稀疏度K=2不变,在网络总链路数N=80,100,140,200的4种情况下,每种情况取采样路径数M=30,35,40,45,50(不随网络总链路数N改变)5个节点,各节点仿真8 000次,观察恢复准确度(Perror为恢复错误概率,它反映了恢复准确度,其值越大准确度越低)随采样路径数M变化而改变的情况.

图2 仿真实验1图

观察图2的各条曲线可以发现当稀疏度K和网络总链路数N不变时,恢复性能会随采样路径数M上升而增强.纵向比较各条曲线,可以发现当稀疏度K与采样路径数M不变时,恢复性能会随网络总链路数N上升而减弱.分析参数的物理意义可见,当网络规模、排队延时稀疏度不变,随着路径延时数据采样量的增加,监测网络拥塞的能力增强;当路径时延采样数据量、排队延时稀疏度不变,随着网络规模增大,监测网络拥塞的能力下降.

仿真实验2:为了探究在采样数据量随网络规模变化的情况下网络监测性能的情况,仍控制发生拥塞的链路数K=2不变,在网络总链路数N=80,100,140,200的4种情况下,每种情况取采样路径数与总链路数之比M/N=0.2,0.3,0.4,0.5,0.6(M随总链路数N发生变化)5个节点,各节点仿真8 000次,观察恢复准确度的变化情况.

图3 仿真实验2图

纵向比较图3的各条曲线可以发现,当稀疏度K和采样路径数与总链路数之比M/N不变时,恢复性能会随网络总链路数N上升而急剧增强,发生恢复错误的概率甚至有数量级上的改善.对比仿真一,在仿真二中恢复性能反而随着网络规模的变大而增强了.更具体地说,如果将路径时延采样数据量随着网络规模的增大作相应的增加,监测网络拥塞位置的能力会随着网络规模的增大得到极大的提升.

仿真实验3:为了探究不同拥塞链路数量对网络拥塞监测性能的影响,控制网络总链路数N=200不变,分析拥塞链路数K=2,3,4的3种情况下恢复性能曲线的变化情况(每种情况取采样路径数M=30,40,50,60,70,80共6个节点,各节点仿真8 000次).

纵向比较图4的各条曲线可以发现,当网络总链路数N与采样路径数M不变时,恢复性能会随稀疏度K的上升而急剧下降.即便稀疏度只增加1,恢复错误的概率已经无法被接受.这也意味着在一定的网络规模下,随着链路排队延时稀疏度的增加(即便只增加了1),如果不增加路径时延采样的数据量,网络拥塞监测能力会受到毁灭性的打击.

图4 仿真实验3图

4 结 论

为了在节点资源有限、拓扑动态变化、通信链路间歇性连接的空间信息网络中高效准确地定位出网络中的拥塞链路并获取其排队时延,本文作者基于链路排队时延存在稀疏性这一特点,采用压缩感知的方法恢复链路时延.这种方法能在保持较高的恢复准确度的前提下,大量减少采样数据的需求量.更进一步地,作者通过三个仿真实验,得出了网络拥塞监测性能与网络规模、路径时延数据采集量、链路延时稀疏度间的一系列关系.

[1] Yu C K,Chen K C,Cheng S M.Cognitive radio network tomography [J].IEEE Transactions on Vehicular Technology,2010,59(4):1980-1997.

[2] Ni J,Xie H,Tatikonda S,et al.Efficient and dynamic routing topology inferencefrom end-to-end measurements [J].IEEE/ACM Transactions on Networking,2010,18(1):123-135.

[3] Qin P,Dai B,Huang B,et al.A survey on network tomography withnetwork coding [J].IEEE Communications Surveys & Tutorials,2014,16(4):1981-1995.

[4] Firooz M H,Roy S.Network tomography via compressed sensing [C].GLOBECOM.Global Communications Conference,Miami,2010.

[5] 戴琼海,付长军,季向阳.压缩感知研究 [J].计算机学报,2011,34(3):425-434.

Dai Q H,Fu C J,Ji X Y.Research on compressed sensing [J].Chinese Journal of Computers,2011,34(3):425-434.

[6] Tropp J A,Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit [J].IEEE Transactions on Information Theory,2007,53(12):4655-4666.

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

Space information network congestion monitoringbased on compressed sensing

Zhang Ling, Gui Lin, Gong Bo, Luo Hanwen

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

In space information network,satellites are connected through inter satellite links.High-queuing-delay,which is caused by the restriction of the spatial network node and the dynamic network topology as well as the intermittent connectivity of communication link,is often observed among spatial network node.It means that network congestion and even packet loss occurs and results in low reliability of data transmission.Aiming at realizing network congestion monitoring efficiently and accurately,this paper analyses the sparsity of links in space information network,and the link state detection is modeled as a compressed sensing problem.Based on greedy algorithm,the paper obtains the link delay and the location of congestion links.Numerical results show that the algorithm can recover the link delay with high accuracy in the case of less sample data.

congestion monitoring; compressed sensing; greedy algorithm

10.3969/J.ISSN.1000-5137.2017.01.016

2016-12-12

国家自然科学基金(61471236, 61420106008, 61671295)；111计划(B07022)；上海浦江人才计划(16PJD029)

张 凌(1994-),男,博士研究生,主要从事无线通信方面的研究．E-mail:zhangling_mz@163.com

导师简介: 归 琳(1975-),女,研究员,主要从事宽带无线通信、图像通信、网络技术方面的研究．E-mail:guilin@sjtu.edu.cn(通信联系人)

TN 927

A

1000-5137(2017)01-0093-05