張 凌, 歸 琳, 宮 博, 羅漢文

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

基于壓縮感知的空間信息網(wǎng)絡(luò)擁塞監(jiān)測(cè)

張 凌, 歸 琳, 宮 博, 羅漢文

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

在空間信息網(wǎng)絡(luò)中,各衛(wèi)星間是通過(guò)星間鏈路(Inter Satellite Links,ISLs)相連接的,其空間網(wǎng)絡(luò)節(jié)點(diǎn)的處理能力和資源存儲(chǔ)能力受限,網(wǎng)絡(luò)拓?fù)渚哂懈邉?dòng)態(tài)性,通信鏈路存在間歇性連接.這造成空間網(wǎng)絡(luò)節(jié)點(diǎn)出現(xiàn)高排隊(duì)時(shí)延的情況,導(dǎo)致網(wǎng)絡(luò)擁塞甚至丟包,空間數(shù)據(jù)傳輸?shù)目煽啃韵陆?為了高效準(zhǔn)確地實(shí)現(xiàn)網(wǎng)絡(luò)擁塞監(jiān)測(cè),本文作者分析了空間信息網(wǎng)絡(luò)的鏈路稀疏性,結(jié)合其傳輸方式,將鏈路狀態(tài)檢測(cè)建模為壓縮感知問(wèn)題,并以貪婪算法求解鏈路延時(shí),進(jìn)而定位擁塞鏈路.仿真結(jié)果證明,這種鏈路狀態(tài)檢測(cè)算法可以在較少的采樣數(shù)據(jù)量的情況下,以較高的精度恢復(fù)鏈路延時(shí).

擁塞監(jiān)測(cè); 壓縮感知; 貪婪算法

0 引 言

空間信息網(wǎng)絡(luò)是以空間平臺(tái)為載體,實(shí)時(shí)獲取、傳輸和處理空間信息的網(wǎng)絡(luò)系統(tǒng),除了給導(dǎo)航、定位、測(cè)控等重大應(yīng)用提供服務(wù),向下可支持對(duì)地觀測(cè)的高動(dòng)態(tài)、寬帶實(shí)時(shí)傳輸,向上可支持深空探測(cè)的超遠(yuǎn)程、大延時(shí)可靠傳輸,近年來(lái)已經(jīng)成為全球范圍的研究熱點(diǎn).空間信息網(wǎng)具有覆蓋面廣、組網(wǎng)靈活、不受地理位置限制等突出優(yōu)勢(shì).但是由于星載、機(jī)載網(wǎng)絡(luò)設(shè)備體積小、質(zhì)量輕,空間網(wǎng)絡(luò)節(jié)點(diǎn)的處理能力和存儲(chǔ)資源能力都很有限,再加上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化以及通信鏈路的間歇性連接,導(dǎo)致出現(xiàn)報(bào)文必須在中間節(jié)點(diǎn)存儲(chǔ)相當(dāng)長(zhǎng)時(shí)間(排隊(duì)時(shí)延高)的情況,這就造成空間網(wǎng)絡(luò)節(jié)點(diǎn)容易發(fā)生擁塞甚至丟包,嚴(yán)重降低了空間數(shù)據(jù)傳輸?shù)目煽啃?因此,擁塞監(jiān)測(cè)問(wèn)題已經(jīng)成為空間信息網(wǎng)絡(luò)的重要問(wèn)題之一.

為了高效準(zhǔn)確地實(shí)現(xiàn)網(wǎng)絡(luò)監(jiān)測(cè),一些學(xué)者提出了基于壓縮感知的鏈路檢測(cè)方法,以降低網(wǎng)絡(luò)鏈路的檢測(cè)開(kāi)銷[1].文獻(xiàn)[2]和[3]分別提出基于加性度量算法和網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)鏈路狀況監(jiān)測(cè)模型,文獻(xiàn)[4]提出基于壓縮感知的方法,檢測(cè)鏈路的時(shí)延和丟包率.但是,由于空間信息網(wǎng)絡(luò)存在鏈路延時(shí)長(zhǎng)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化等特點(diǎn),如何將上述方法應(yīng)用于空間信息網(wǎng)絡(luò)中還存在著巨大的挑戰(zhàn).由此可見(jiàn),設(shè)計(jì)一種高效、可靠的空間信息網(wǎng)絡(luò)管控實(shí)現(xiàn)機(jī)制,是需要解決的一個(gè)重要問(wèn)題.

本文作者為了高效準(zhǔn)確地實(shí)現(xiàn)空間信息網(wǎng)絡(luò)中的擁塞監(jiān)測(cè),根據(jù)空間信息網(wǎng)絡(luò)的鏈路特性,分析了空間信息網(wǎng)絡(luò)鏈路狀態(tài)的稀疏特性,結(jié)合空間信息網(wǎng)絡(luò)的傳輸方式,將鏈路狀態(tài)檢測(cè)建模為壓縮感知問(wèn)題,進(jìn)而以Matlab為工具用正交匹配追蹤算法對(duì)空間信息網(wǎng)絡(luò)的排隊(duì)延時(shí)進(jìn)行恢復(fù)仿真,并對(duì)仿真結(jié)果做總體的分析得出結(jié)論.

1 稀疏性分析

為了更好地進(jìn)行空間信息網(wǎng)鏈路監(jiān)測(cè),本節(jié)根據(jù)對(duì)空間信息網(wǎng)絡(luò)中的鏈路特性研究,分析了鏈路排隊(duì)延時(shí)的稀疏性,為壓縮感知模型的引入奠定基礎(chǔ).

表1 空間信息網(wǎng)絡(luò)鏈路時(shí)延 ms

實(shí)現(xiàn)空間信息網(wǎng)鏈路監(jiān)測(cè),最直接的手段是獲取每個(gè)鏈路的時(shí)延情況,這不僅能提供擁塞發(fā)生的具體位置,還能描述擁塞的嚴(yán)重程度.由于空間信息網(wǎng)中,接入鏈路和星間鏈路存在差異性,本文作者對(duì)空間信息網(wǎng)絡(luò)中的接入鏈路和星間鏈路特性進(jìn)行了調(diào)研和分析.表1整理出空間信息網(wǎng)絡(luò)鏈路延時(shí)狀況.

從表1中可以看出,鏈路時(shí)延t由三部分構(gòu)成,傳輸時(shí)延tr、傳播時(shí)延tp以及排隊(duì)時(shí)延tq,即:t=tr+tp+tq.假設(shè)T為各鏈路的時(shí)延矢量T=(t1,t2,…,tN),ti(i∈[1,N])為鏈路i的時(shí)延;Tr為各鏈路的傳輸時(shí)延矢量Tr=(tr1,tr2,…,trN),tri(i∈[1,N])為鏈路i的傳輸時(shí)延;Tp為各鏈路的傳播時(shí)延矢量Tp=(tp1,tp2,…,tpN),tpi(i∈[1,N])為鏈路i的傳播時(shí)延;Tq為各鏈路的排隊(duì)時(shí)延矢量Tq=(tq1,tq2,…,tqN),tqi(i∈[1,N])為鏈路i的排隊(duì)時(shí)延.從表1中可見(jiàn),與傳輸時(shí)延和傳播時(shí)延相比,排隊(duì)時(shí)延是有量級(jí)上的差異的,由于僅發(fā)生在擁塞時(shí)會(huì)引發(fā)鏈路的不斷重傳從而導(dǎo)致較大的排隊(duì)時(shí)延,則可以認(rèn)為各鏈路的排隊(duì)時(shí)延Tq=T-Tr-Tp可以構(gòu)成稀疏矢量.對(duì)于Tr=(tr1,tr2,…,trN),其中的接入鏈路為100ms,星間鏈路是0.其傳播時(shí)延矢量Tp=(tp1,tp2,…,tpN),各元素均為常數(shù).

由于空間信息網(wǎng)絡(luò)規(guī)模大、鏈路多,通過(guò)大量的延時(shí)數(shù)據(jù)采集確實(shí)能夠準(zhǔn)確地得到鏈路擁塞的具體位置,但是這種方法需求的數(shù)據(jù)量大、效率低.本研究基于排隊(duì)延時(shí)矢量的稀疏性,考慮利用壓縮感知的方法,減少需要采集的數(shù)據(jù)量.

2 模型建立

圖1 網(wǎng)絡(luò)模型

(1)

(2)

式中R是測(cè)量矩陣,其元素為1時(shí),表示該元素所在行對(duì)應(yīng)的路徑經(jīng)過(guò)所在列對(duì)應(yīng)的鏈路.

推廣到實(shí)際的大規(guī)?？臻g信息網(wǎng)絡(luò)中,仍然可以用式(1)表達(dá)路徑時(shí)延與鏈路時(shí)延的關(guān)系,并且式中各個(gè)量仍保持原有的物理意義:y是M維列向量,代表M條路徑的時(shí)延;T是N維列向量,代表N條鏈路的時(shí)延,是整個(gè)網(wǎng)絡(luò)的鏈路時(shí)延集合;R是M×N維矩陣,列數(shù)N是網(wǎng)絡(luò)中的鏈路總數(shù),其大小由網(wǎng)絡(luò)規(guī)模決定,行數(shù)M是選中的采樣路徑數(shù),M通常小于N,通過(guò)第三節(jié)的仿真實(shí)驗(yàn)中可以看出,行數(shù)的選取數(shù)量很大程度上取決于網(wǎng)絡(luò)發(fā)生擁塞的稀疏性情況,矩陣元素的取值為1或0,取決于采樣路徑是否經(jīng)過(guò)對(duì)應(yīng)的鏈路.由于鏈路時(shí)延矢量可以表達(dá)為:T=Tr+Tp+Tq,而其中的排隊(duì)時(shí)延矢量Tq存在稀疏性,因此采用壓縮感知的方法[5]恢復(fù)各路徑排隊(duì)時(shí)延的過(guò)程如下:

步驟一:在空間信息網(wǎng)絡(luò)中隨機(jī)地選取M條采樣路徑,根據(jù)這些路徑經(jīng)過(guò)的鏈路得到測(cè)量矩陣RM×N.

步驟二:根據(jù)步驟一中選取的路徑,分別測(cè)量這些路徑的總時(shí)延得到路徑時(shí)延矢量y;根據(jù)各鏈路的特性得到鏈路傳輸時(shí)延矢量Tr和鏈路傳播時(shí)延矢量Tp.

步驟三:根據(jù)壓縮感知模型y-RTr-RTp=RTq,采用恢復(fù)算法得到鏈路排隊(duì)時(shí)延矢量Tq.

可以發(fā)現(xiàn)測(cè)量矩陣R是隨機(jī)選定的,Tr和Tp是由空間信息網(wǎng)絡(luò)自身決定的,實(shí)際要測(cè)的數(shù)據(jù)僅僅是路徑時(shí)延矢量y,并且這些量往往很容易測(cè)得、數(shù)據(jù)量也不大.

3 仿真實(shí)驗(yàn)

本文作者以Matlab為工具進(jìn)行仿真,模擬恢復(fù)空間信息網(wǎng)絡(luò)中各鏈路排隊(duì)時(shí)延的過(guò)程,通過(guò)三次仿真實(shí)驗(yàn),對(duì)比恢復(fù)的準(zhǔn)確度討論空間信息網(wǎng)絡(luò)的總鏈路數(shù)(測(cè)量矩陣R的列數(shù)N)、路徑時(shí)延數(shù)據(jù)采集量(測(cè)量矩陣R的行數(shù)M)、鏈路排隊(duì)時(shí)延稀疏度(鏈路排隊(duì)時(shí)延矢量Tq的稀疏度K)對(duì)恢復(fù)性能產(chǎn)生的影響.各仿真實(shí)驗(yàn)的基本步驟如下:

步驟一:產(chǎn)生一個(gè)M×N的測(cè)量矩陣R,矩陣元素相互獨(dú)立且服從等概的兩點(diǎn)分布;

步驟二:產(chǎn)生一個(gè)N維列向量Tq,其稀疏度為K,非零元素位置隨機(jī);

步驟三:得到N維列向量Y=RTq;

在OMP算法中,以一個(gè)全零的列向量為起始(稀疏度為0),在每一次循環(huán)中將一個(gè)零元素變?yōu)榉橇阍?稀疏度加1),使得改變后的列向量左乘測(cè)量矩陣R后與目標(biāo)列向量Y的歐氏距離達(dá)到最小,經(jīng)過(guò)K次循環(huán)后恢復(fù)出稀疏度為K的列向量.

三次仿真實(shí)驗(yàn)如下:

仿真實(shí)驗(yàn)1:為了探究固定采樣數(shù)據(jù)量在不同網(wǎng)絡(luò)規(guī)模下的網(wǎng)絡(luò)監(jiān)測(cè)性能,保持發(fā)生擁塞的鏈路數(shù),即鏈路延時(shí)矢量Tq的稀疏度K=2不變,在網(wǎng)絡(luò)總鏈路數(shù)N=80,100,140,200的4種情況下,每種情況取采樣路徑數(shù)M=30,35,40,45,50(不隨網(wǎng)絡(luò)總鏈路數(shù)N改變)5個(gè)節(jié)點(diǎn),各節(jié)點(diǎn)仿真8 000次,觀察恢復(fù)準(zhǔn)確度(Perror為恢復(fù)錯(cuò)誤概率,它反映了恢復(fù)準(zhǔn)確度,其值越大準(zhǔn)確度越低)隨采樣路徑數(shù)M變化而改變的情況.

圖2 仿真實(shí)驗(yàn)1圖

觀察圖2的各條曲線可以發(fā)現(xiàn)當(dāng)稀疏度K和網(wǎng)絡(luò)總鏈路數(shù)N不變時(shí),恢復(fù)性能會(huì)隨采樣路徑數(shù)M上升而增強(qiáng).縱向比較各條曲線,可以發(fā)現(xiàn)當(dāng)稀疏度K與采樣路徑數(shù)M不變時(shí),恢復(fù)性能會(huì)隨網(wǎng)絡(luò)總鏈路數(shù)N上升而減弱.分析參數(shù)的物理意義可見(jiàn),當(dāng)網(wǎng)絡(luò)規(guī)模、排隊(duì)延時(shí)稀疏度不變,隨著路徑延時(shí)數(shù)據(jù)采樣量的增加,監(jiān)測(cè)網(wǎng)絡(luò)擁塞的能力增強(qiáng);當(dāng)路徑時(shí)延采樣數(shù)據(jù)量、排隊(duì)延時(shí)稀疏度不變,隨著網(wǎng)絡(luò)規(guī)模增大,監(jiān)測(cè)網(wǎng)絡(luò)擁塞的能力下降.

仿真實(shí)驗(yàn)2:為了探究在采樣數(shù)據(jù)量隨網(wǎng)絡(luò)規(guī)模變化的情況下網(wǎng)絡(luò)監(jiān)測(cè)性能的情況,仍控制發(fā)生擁塞的鏈路數(shù)K=2不變,在網(wǎng)絡(luò)總鏈路數(shù)N=80,100,140,200的4種情況下,每種情況取采樣路徑數(shù)與總鏈路數(shù)之比M/N=0.2,0.3,0.4,0.5,0.6(M隨總鏈路數(shù)N發(fā)生變化)5個(gè)節(jié)點(diǎn),各節(jié)點(diǎn)仿真8 000次,觀察恢復(fù)準(zhǔn)確度的變化情況.

圖3 仿真實(shí)驗(yàn)2圖

縱向比較圖3的各條曲線可以發(fā)現(xiàn),當(dāng)稀疏度K和采樣路徑數(shù)與總鏈路數(shù)之比M/N不變時(shí),恢復(fù)性能會(huì)隨網(wǎng)絡(luò)總鏈路數(shù)N上升而急劇增強(qiáng),發(fā)生恢復(fù)錯(cuò)誤的概率甚至有數(shù)量級(jí)上的改善.對(duì)比仿真一,在仿真二中恢復(fù)性能反而隨著網(wǎng)絡(luò)規(guī)模的變大而增強(qiáng)了.更具體地說(shuō),如果將路徑時(shí)延采樣數(shù)據(jù)量隨著網(wǎng)絡(luò)規(guī)模的增大作相應(yīng)的增加,監(jiān)測(cè)網(wǎng)絡(luò)擁塞位置的能力會(huì)隨著網(wǎng)絡(luò)規(guī)模的增大得到極大的提升.

仿真實(shí)驗(yàn)3:為了探究不同擁塞鏈路數(shù)量對(duì)網(wǎng)絡(luò)擁塞監(jiān)測(cè)性能的影響,控制網(wǎng)絡(luò)總鏈路數(shù)N=200不變,分析擁塞鏈路數(shù)K=2,3,4的3種情況下恢復(fù)性能曲線的變化情況(每種情況取采樣路徑數(shù)M=30,40,50,60,70,80共6個(gè)節(jié)點(diǎn),各節(jié)點(diǎn)仿真8 000次).

縱向比較圖4的各條曲線可以發(fā)現(xiàn),當(dāng)網(wǎng)絡(luò)總鏈路數(shù)N與采樣路徑數(shù)M不變時(shí),恢復(fù)性能會(huì)隨稀疏度K的上升而急劇下降.即便稀疏度只增加1,恢復(fù)錯(cuò)誤的概率已經(jīng)無(wú)法被接受.這也意味著在一定的網(wǎng)絡(luò)規(guī)模下,隨著鏈路排隊(duì)延時(shí)稀疏度的增加(即便只增加了1),如果不增加路徑時(shí)延采樣的數(shù)據(jù)量,網(wǎng)絡(luò)擁塞監(jiān)測(cè)能力會(huì)受到毀滅性的打擊.

圖4 仿真實(shí)驗(yàn)3圖

4 結(jié) 論

為了在節(jié)點(diǎn)資源有限、拓?fù)鋭?dòng)態(tài)變化、通信鏈路間歇性連接的空間信息網(wǎng)絡(luò)中高效準(zhǔn)確地定位出網(wǎng)絡(luò)中的擁塞鏈路并獲取其排隊(duì)時(shí)延,本文作者基于鏈路排隊(duì)時(shí)延存在稀疏性這一特點(diǎn),采用壓縮感知的方法恢復(fù)鏈路時(shí)延.這種方法能在保持較高的恢復(fù)準(zhǔn)確度的前提下,大量減少采樣數(shù)據(jù)的需求量.更進(jìn)一步地,作者通過(guò)三個(gè)仿真實(shí)驗(yàn),得出了網(wǎng)絡(luò)擁塞監(jiān)測(cè)性能與網(wǎng)絡(luò)規(guī)模、路徑時(shí)延數(shù)據(jù)采集量、鏈路延時(shí)稀疏度間的一系列關(guān)系.

[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] 戴瓊海,付長(zhǎng)軍,季向陽(yáng).壓縮感知研究 [J].計(jì)算機(jī)學(xué)報(bào),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.

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

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

國(guó)家自然科學(xué)基金(61471236, 61420106008, 61671295)；111計(jì)劃(B07022)；上海浦江人才計(jì)劃(16PJD029)

張 凌(1994-),男,博士研究生,主要從事無(wú)線通信方面的研究．E-mail:zhangling_mz@163.com

導(dǎo)師簡(jiǎn)介: 歸 琳(1975-),女,研究員,主要從事寬帶無(wú)線通信、圖像通信、網(wǎng)絡(luò)技術(shù)方面的研究．E-mail:guilin@sjtu.edu.cn(通信聯(lián)系人)

TN 927

A

1000-5137(2017)01-0093-05