基于壓縮感知的無線通信網拓撲推斷方法

邵 豪， 王倫文

(國防科技大學電子對抗學院，安徽 合肥 230037)

0 引言

網絡拓撲是網絡結構分析、網絡控制的基礎前提[1]。但通信非合作方以非授權接入的方式偵察、截獲無線電信號，難以通過傳統的拓撲發現技術獲得網絡拓撲[2-3]。由于電磁環境復雜化，從少量的觀測數據中推斷網絡拓撲存在著嚴峻的挑戰。從有限的節點時間序列中重建具有隨機過程的網絡仍是一個難題[4]。目前，壓縮感知已被用于耦合振蕩器網絡[5-6]、博弈游戲網絡[7]的拓撲推斷，但這兩種網絡節點動力學信息是提前已知的。文獻[8]利用大數定理估計疾病感染概率，構造壓縮感知模型推斷傳染病網絡鏈接信息。文獻[9]引入已知的輸入噪聲來降低觀測矩陣的相干性，推斷線性網絡拓撲結構。對壓縮信號重構的預測誤差異常分析，可準確推斷網絡中隱藏節點的存在[10]。

無線通信的非合作方，從第三方的角度出發，只截獲節點的無線電信號，獲取節點時間序列上的二進制信息(1：發出數據信號或確認信號；0：未發出信號)，且無任何先驗信息，這使得目前傳統拓撲發現方法和壓縮感知模型都無法適用。本文針對此問題，提出基于壓縮感知的無線通信網拓撲推斷方法。

1 鏈路識別技術與稀疏向量重構方法

1.1 基于信號時間接續關系的鏈路識別技術

分組交換網中，路由表存儲特定網絡地址的信息傳輸路徑[11]。如果偵察到帶有地址信息的信號，并從信號中恢復出物理地址，即源節點的MAC地址與目標節點的MAC地址，根據地址匹配，則可識別出對應鏈路[12]。信令信道和業務信道的分離，以及加密信息的傳輸使得地址的恢復困難重重。

本文通過網絡偵察，利用得到的數據信號與響應確認信號的時間接續關系，識別出對應鏈路。在無線通信網中，信息傳輸遵守相應的路由協議，且信道條件不如有線信道理想，對數據幀的響應頻繁，數據信號與響應信號間存在相應接續關系[3]，如圖1所示。通過時間接續關系推斷源節點與目標節點間的鏈接關系，對加密信號也可適用，更具有普適性。

圖1 數據信號與響應信號時間接續關系Fig.1 Time relationship between data and response signal

在圖1中，節點A、B之間發出數據信號和確認信號間有明顯的時間接續關系，認為此節點之間存在鏈接。但現實中，考慮到信道條件與信息傳輸頻度，觀測時間窗口內存在多個節點間信號的傳輸[13]，這對區分源節點與目標節點的一一對應關系提出了挑戰。

1.2 基于壓縮感知模型的稀疏信號重構方法

1.2.1壓縮感知模型

壓縮感知解決的是如何從向量X∈RN的線性測量Y中重建向量X的問題。

Y=φ·X

(1)

式(1)中，Y∈RM，φ是一個M×N的矩陣。壓縮感知的突出特點是，測量的數目可以比未知向量的分量的數目少得多，即M?N。由矩陣理論，φ是一個非滿秩矩陣，該方程是欠定的，因此很難求出對應解，無法重構向量X。但若向量X是k稀疏的(X中有k個非零值，k?N)，且矩陣φ滿足有限等距性(RIP)、低相干性[14]等條件，此時向量X就能夠被觀測值Y準確重構。

1.2.2稀疏向量重構方法

通過少量觀測數據，使用l0范數恢復原始向量X：

min‖Xo‖,s.t.Y=φ·X

(2)

但使用l0范數進行信號重構是NP難的。通常使用最小l1范數的優化問題進行重構:

min‖X1‖,s.t.Y=φ·X

(3)

使用l1范數優化，可以使用凸松弛算法、貪婪追蹤算法等求解原始向量X。在無線通信網的拓撲推斷中，k值是節點的度且是未知的，考慮到運算復雜度與算法精度，本文使用稀疏度自適應的匹配追蹤算法SAMP[15]進行重構。

2 基于壓縮感知的無線通信網拓撲推斷方法

2.1 節點狀態

在本節中，將無線通信網絡拓撲推斷問題轉化為類似式(1)的向量重構問題。在φ滿足RIP特性的前提下，通過壓縮感知的重構算法重構向量X。

首先，在網絡通信范圍中部署相應探測終端，對網絡節點進行偵察，得到節點在時間序列上的狀態。節點i的狀態表示如下：

(4)

其次，通過一段時間的偵察，獲取網絡各節點在不同時刻的狀態。最后，依據1.1節介紹的基于時間接續關系信源與目標節點間的鏈路推斷，得到相應信源與目標節點的鏈接關系。

表1表示t1至t7時刻，某8節點網絡各節點狀態的時間序列。

表1 t1至t7時刻節點狀態

表1中，Si是節點2發出確認信號的狀態序列，S-i是其余節點發出數據信號的狀態序列。以狀態序列無法直接推斷拓撲結構，有三個原因：第一，在某個時間窗口內，不止一個節點發出數據信號和確認信號，此時難以區分信源與目標節點的一一對應關系；第二，節點未發出確認信號不等價于未接收到數據信號。例如在t2時刻，節點5，7發出數據信號，節點2未發出確認信號，這并不能表示節點5，7不是2節點的鄰居，因為節點2可能不是節點5，7信息傳輸時路由表中的下一跳節點。由此，對于節點.Si=0的時刻，S-i的狀態沒有任何意義，故只提取Si=1的時刻(表2)進行拓撲推斷。第三，即使S-i狀態組成一個滿秩矩陣，依舊無法準確判斷節點

鏈接情況。例如在表3中，無法確定在t2、t3時刻，節點1確認信號的來源。

表2 節點2 Si=1時刻，各節點狀態

表3 某4節點網絡各節點狀態

2.2 模型構建

網絡環境的動態變化，以及只能使用Si=1時刻狀態進行拓撲推斷，這要求本文算法盡可能使用少量的數據準確重構出各節點的連接情況。對于任意節點i，構建適用于通信網絡的框架模型如下：

(5)

將式(5)簡寫成：

Si=φi·Xi

(6)

式(6)中，Si是節點i在某時刻發出確認信號次數的集合向量且Si(t)≥1，φi是除節點i以外其余節點在對應時刻的狀態集合S-i，Xi是節點i與其余節點的連接關系，這類似于式(1)壓縮感知方程。對于無線通信網絡而言，短時間窗口保證φi滿足RIP性質[8]，且向量X大概率是稀疏的。但對于如圖2所示的星型拓撲結構，中心節點的X向量([1,1,1,1,1,1,1]T)是不稀疏的。通過重構中心節點的鄰居節點的X向量，反推中心節點的鏈接情況。通過對向量X的重構，得到節點i與其余節點的連接關系，遍歷所有節點i，推斷網絡拓撲結構。

圖2 星型拓撲結構Fig.2 Star topology

2.3 向量重構誤差分析與修正

在網絡學中，連接矩陣AN×N表示N節點網絡的拓撲結構：

(7)

式(7)中，定義向量Ai為節點i與其余節點的鏈接信息：

(8)

重構向量X后，以0作為ai,j的判決門限：

(9)

與線性網絡拓撲識別不同，在無線通信網絡中只能偵察節點是否發出確認信號，不能檢測出節點是否收到數據信號。因此模型中X向量經過SAMP重構后與實際鏈接情況存在誤差。例如，表1中的t1時刻，若節點2與3，5，7，8相連，則A2=[0,1,0,1,0,1,1]T。Si(t1)等于t1時刻節點2作為下一跳節點發出確認信號的次數，因此Si(t1)≠S-i(t1)×Ai。重構誤差來源于非合作方網絡偵察的局限，Si值無法表示收到信號的個數。為減小算法誤差，本文提出節點雙向匹配原則與篩選狀態迭代的方法。

考慮到通信網絡中節點傳輸信息是雙向的，現修改式(9)判決如下：

(10)

(11)

式(10)、式(11)中，對ai,j=1的判定更加嚴格，通過篩選再次迭代的方式，找到余下節點i余下的連接。將得到的新的X向量(xi,j=0/1)與φ相乘,得到向量Si′：

(12)

提取Si′(t)=0的時刻時，xi,j=0對應的節點狀態以及相應的xi,j，重新構成類似式(5)的壓縮感知框架。

(13)

重新重構向量X后，通過式(10)得到節點i與剩余節點的連接情況，再次通過篩選與迭代的方式，直至所有節點不存在Si′(t)=0時刻或到達迭代次數上限。此時，通過各個節點對應的向量X，得到所有節點與其余節點的連接情況，得到網絡拓撲圖。

2.4 算法步驟

步驟1 前期網絡偵察，獲取網絡節點狀態時間序列Si，初始化拓撲鏈接矩陣AN×N。

步驟2 根據Si構建對應的節點狀態矩陣φi，以及壓縮感知模型Si=φi·Xi；使用SAMP算法重構連接向量Xi，遍歷所有節點。

步驟3 判斷重構向量中元素xi,j>1,xj,i>1是否成立，若成立，鏈接矩陣AN×N中元素ai,j，aj,i與xi,jxj,i(i≠j)賦值為1；反之，賦值為0。

步驟4 將賦值后的Xi與狀態矩陣φi，得到Si′。判斷Si′中元素是否大于零，若都大于零，則算法結束，輸出拓撲鏈接矩陣AN×N。反之，提取Si′(t)=0的時刻，xi,j=0對應的節點狀態作為新的Si與φi，返回步驟2。當算法達到最大迭代次數后，亦終止輸出拓撲鏈接矩陣AN×N。

3 仿真與實驗分析

3.1 實驗環境與數據

為驗證本文算法的有效性，本文使用QualNet6.1軟件搭建無線通信網絡，網絡結構分別為Watts-Strogatz小世界網絡(WS)[16]、隨機圖網絡(ER)[17]、無標度網絡(BA)、Newman-Watts小世界網絡(NW)[18]。四種網絡結構的參數如表4所示。

表4 四種網絡參數性質

在四個網絡分別進行數據包傳輸，部分仿真參數選項如表5所示。

表5 部分網絡仿真參數選項

經過一段時間的網絡通信仿真，利用數據信號與確認信號的時間接續關系，記錄節點在每一個時間窗口(t1,t2…)的狀態，得到各節點在時間序列上的狀態集合后，利用本文提出的算法推斷無線通信網拓撲結構。

為衡量算法性能，定義拓撲推斷率的兩個指標：鏈路準確推斷率(REL)、未存在鏈路虛警率(RNC)。REL定義為準確推斷的鏈路數目占網絡總鏈路數目的比例。RNC定義為推斷到不存在的鏈路數目占未連接節點數的比例。

此外，為更進一步了解算法性能，改變相應參數，分別分析節點時間序列長度(狀態矩陣φi行列數目比，數目比越小，說明算法可以用更短的偵察時間獲取相應的拓撲結構，時效性越高)以及無線通信網絡的環境噪聲對拓撲推斷準確率的影響。

3.2 實驗結果與分析

3.2.1拓撲推斷率

使用本文提出的算法對仿真的通信網絡進行拓撲推斷，直至迭代收斂后，得到四種網絡中的拓撲推斷率指標REL和RNC?？紤]到最小二乘法也是解欠定方程的一種方法，使用最小二乘法對式(6)中非滿秩矩陣φi進行求逆(φi行列數比為0.75)，重構鏈接向量進行拓撲推斷。仿真建模10次以后取平均結果，兩種方法的拓撲推斷率隨迭代次數的變化如圖3所示，最終拓撲推斷率如表6所示。其中，CS代表本文算法，LS代表最小二乘法。

圖3 迭代次數對拓撲推斷率的影響Fig.3 Relation between iteration number and inference rate

表6 兩種算法收斂后的拓撲推斷率

Tab.6 Inference rate when converge algorithms

CS-RELCS-RNCLS-RELLS-RNCWS0.9700.0090.4360.045ER0.9510.0130.6910.027BA0.9640.0100.4410.029NW0.9580.0190.3780.049

圖3表示在每步迭代時，各算法對應的REL與RNC。推斷網絡鏈接時，本文采用雙向節點匹配的方式以降低重構誤差，在第一步迭代時部分正確的鏈接被過濾，使得初始REL不高，但其保證了很低的RNC。隨著迭代進行，REL上升迅速，RNC略微上升，基本不變，這是因為在本文算法中，不存在的鏈路的一旦被錯誤檢測，無法改變。經仿真實驗表明，迭代次數大于3以上，算法基本收斂，能有準確的拓撲推斷率。

表6表示算法最終REL與RNC性能。本文算法模型在四個網絡中均有95%以上的鏈路推斷準確率，虛警率低于2%。相比最小二乘的方法，本文算法的推斷準確率高47.4%，虛警率低2.3%，證明本文算法是有效的。

3.2.2時間序列長度對拓撲推斷率的影響

在壓縮感知中，觀測矩陣行列數值比直接影響稀疏向量重構準確率[5]。通過改變式(5)中時間序列長度與節點總數的比值nt，即φi行列數之比(nt=m/N)，分析時間序列長度對拓撲推斷的影響。實驗結果如圖4所示。

圖4 時間序列長度對網絡拓撲推斷率的影響Fig.4 Relation between time series length and inference rate

圖4表示在各網絡中，拓撲成功推斷率與時間序列長度成正相關。這是因為較短的觀測時間內，某些鏈路并沒有發生信息傳輸，導致網絡鏈接的偵察數據不足，最終無法正確推斷部分未發生信息傳輸的鏈路。壓縮感知的重構算法，利用非滿秩矩陣恢復稀疏向量，保證了較小的nt能有較高推斷率。nt>40%的情況下，鏈接準確率能達到90%以上。較短的時間序列意味著利用較短時間的觀察就能準確地推斷拓撲結構信息，這為算法適應網絡變化提供了條件。

3.2.3噪聲干擾對拓撲推斷率的影響

環境噪聲不僅會提高無線通信網的丟包率，也會造成擁塞，從而影響節點狀態矩陣φi。例如，某時間窗口內，節點1，2之間傳輸信息。噪聲干擾后，節點2可能未接收到信號，從而未發出確認信號；也可能節點2擁塞，確認信息在下一時間窗口發出。噪聲干擾導致節點狀態矩陣存在誤差，從而影響拓撲推斷率。

為研究噪聲干擾對拓撲推斷率的影響，在無線通信網仿真中，加入不同信噪比的加性高斯白噪聲，獲取節點時間狀態序列后，利用本文算法與最小二乘算法進行拓撲推斷，以衡量噪聲干擾對推斷結果的影響。實驗結果如圖5所示。

圖5 噪聲干擾對網絡拓撲推斷率的影響Fig.5 Relation between noise and inference rate

圖5表示在各網絡中，拓撲成功推斷率與噪聲強度成負相關。當信噪較低時，網絡節點丟包率較高，擁塞嚴重。高節點丟包率導致節點無法收到數據信號，故不會發出確認信號，使得式(5)中部分Si(t)=1變成Si(t)=0。在本文算法中，只提取Si(t)=1構成節點狀態矩陣，進行連接向量重構，因此高丟包率會增加網絡偵察時間，有限的偵察時間會降低拓撲推斷準確率。擁塞導致在某個時間窗口內Si(t)=1發生在下一個時間窗口，導致節點狀態矩陣發生誤差，但本文通過雙向鏈路匹配的原則，控制狀態翻轉導致的單向鏈接推斷誤差。隨著信噪比的上升，丟包率與擁塞降低，拓撲成功推斷率上升。在瑞利衰落信道，信噪比為30 dB的高斯白噪聲的干擾下，本文算法的拓撲推斷平均率為90.75%以上。由表5可得，在無線通信網絡仿真中，我們考慮了雙徑損傷與瑞利衰落，信道條件較差，因此所需信噪比較高。在不同信噪比的情況下，本文算法較最小二乘法有更好的推斷率。這對算法在實際噪聲環境下應用提供了保證。

4 結論

本文提出了基于壓縮感知對非合作的無線通信網拓撲推斷方法，該方法將網絡拓撲識別轉變為壓縮感知模型與重構算法。利用數據信號與確認信號的時間接續關系，獲取節點狀態序列，再構造滿足壓縮感知方程，通過重構算法恢復鏈接向量，最后以節點雙向匹配原則與篩選狀態迭代法準確推斷網絡拓撲結構。仿真實驗表明，該方法能利用有限的數據量，準確推斷網絡拓撲結構，鏈接成功推斷率高于95%，虛警率低于2%，能夠適應環境噪聲的干擾，各項指標優于最小二乘法。但在通信網絡中，未發生信息傳輸的鏈路無法通過網絡偵察獲取鏈接信息，利用鏈路預測技術，可以預測得到完善的拓撲結構，降低所需信噪比條件，加大本文算法的適應性。因此，本文下一步考慮將本文算法與鏈路預測[18]相結合，進行網絡拓撲推斷。