基于壓縮感知的空間信息網絡擁塞監(jiān)測

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

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

基于壓縮感知的空間信息網絡擁塞監(jiān)測

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

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

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

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

0 引 言

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

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

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

1 稀疏性分析

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

表1 空間信息網絡鏈路時延 ms

實現(xiàn)空間信息網鏈路監(jiān)測,最直接的手段是獲取每個鏈路的時延情況,這不僅能提供擁塞發(fā)生的具體位置,還能描述擁塞的嚴重程度.由于空間信息網中,接入鏈路和星間鏈路存在差異性,本文作者對空間信息網絡中的接入鏈路和星間鏈路特性進行了調研和分析.表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中可見,與傳輸時延和傳播時延相比,排隊時延是有量級上的差異的,由于僅發(fā)生在擁塞時會引發(fā)鏈路的不斷重傳從而導致較大的排隊時延,則可以認為各鏈路的排隊時延Tq=T-Tr-Tp可以構成稀疏矢量.對于Tr=(tr1,tr2,…,trN),其中的接入鏈路為100ms,星間鏈路是0.其傳播時延矢量Tp=(tp1,tp2,…,tpN),各元素均為常數(shù).

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

2 模型建立

圖1 網絡模型

(1)

(2)

式中R是測量矩陣,其元素為1時,表示該元素所在行對應的路徑經過所在列對應的鏈路.

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

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

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

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

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

3 仿真實驗

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

步驟一:產生一個M×N的測量矩陣R,矩陣元素相互獨立且服從等概的兩點分布;

步驟二:產生一個N維列向量Tq,其稀疏度為K,非零元素位置隨機;

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

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

三次仿真實驗如下:

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

圖2 仿真實驗1圖

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

仿真實驗2:為了探究在采樣數(shù)據(jù)量隨網絡規(guī)模變化的情況下網絡監(jiān)測性能的情況,仍控制發(fā)生擁塞的鏈路數(shù)K=2不變,在網絡總鏈路數(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個節(jié)點,各節(jié)點仿真8 000次,觀察恢復準確度的變化情況.

圖3 仿真實驗2圖

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

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

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

圖4 仿真實驗3圖

4 結 論

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

[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(通信聯(lián)系人)

TN 927

A

1000-5137(2017)01-0093-05