未知拓撲無線自組網絡多節點干擾決策算法

顓孫少帥,楊俊安,劉輝,黃科舉

(1.國防科技大學電子對抗學院,230037,合肥; 2.安徽省電子制約技術重點實驗室,230037,合肥)

無線自組網技術具有去中心化、動態組網的特點,將該技術應用于戰場通信時,能夠突破地域的局限性,提高網絡連通的成功率、抗毀性和抗干擾能力[1-2]。在戰場環境下,為實現對目標網絡的有效干擾,需要采取一定的手段以實現通信拒止。

當前對無線自組網絡的干擾研究可歸納為以下兩個方面:①利用先驗信息有針對性的對網絡進行干擾;②利用強化學習不斷試錯的方法搜索最佳干擾策略。例如,已知網絡協議時,Amuru等人從MAC層角度出發,對數據流中不同的幀結構進行干擾,并指出干擾確認幀/非確認幀(Acknowledge/Not Acknowledge)所需的干擾能量最少但干擾效果最優[3]。Moon等人利用目標網絡協議漏洞提出一種洪泛攻擊方法[4]。劉書建等人對基于Zamp洪泛攻擊方法的可行性進行了分析研究[5]。Proano等人對網絡中傳輸的數據包進行分類處理,然后根據分析結果對其中“重要的”數據包進行干擾[6]。此外,已知目標網絡拓撲結構時,Sefair提出一種干擾網絡關鍵節點的方法,該方法迫使通信方采用更多跳進行通信,甚至無法有效通信[7]。Borrero在文獻[8]中指出,通過觀察網絡中數據流傳輸路徑,能夠獲取有關網絡拓撲結構的部分信息,進而使用該信息指導干擾決策。盡管上述方法能夠取得優異的干擾性能,但是在戰場環境下,網絡協議或拓撲結構等信息是無法獲得的,即研究的前提條件無法滿足;另一方面,強化學習無需環境信息的優勢使得其在機器人控制[9]、游戲設計[10]、深度學習[11]等領域得到充分利用。Amuru在文獻[12]中提出了一種未知拓撲無線自組網絡單節點干擾決策算法,通過不斷試錯的方式找到單個最佳干擾節點。Gai等人在文獻[13]中提出一種多智能體強化學習方法,但要求在學習過程中明確知道每個智能體對應的獎賞信息。然而在對目標網絡進行干擾時,需要對多個節點進行聯合干擾才能實現一定程度的通信拒止,并且干擾每個節點對應的獎賞信息也是未知的。

為解決上述問題,本文研究了未知拓撲無線自組網絡多節點干擾問題,提出了一種利用節點間相關性的干擾決策算法,算法根據每次干擾后外界反饋信息更新節點相關性矩陣,并利用該矩陣指導后續干擾節點的選擇,通過與環境反復交互的方式不斷完善相關性矩陣。此外,將戰場無線自組網絡建模為泊松點過程(Poisson Point Process,PPP)網絡,并在該網絡模型上進行算法性能的驗證實驗,實驗結果表明:對目標網絡進行多次干擾后,本文提出的算法同現有算法相比能夠阻斷更多的網絡流數,即在干擾性能和魯棒性能方面更優。

1 無線自組網絡

1.1 無線自組網絡的概念

無線自組網絡包括移動自組網絡(Mobile Ad-hoc Network,MANET)和傳感器自組網絡(Sensor Ad-hoc Network,SANET)兩種。移動自組網技術在美軍的主要通信裝備中普遍使用,典型的戰術自組網產品有:JNN-TE波形、彈藥數據鏈、無人機自組網[14]、衛星自組網等。無線自組網絡具有多種組網方式,如圖1所示,按照節點功能及結構層次可分為平面網絡結構和分級網絡結構。在兩種網絡結構中,平面網絡結構是最基本的網絡結構,同時也是分層網絡的重要組成部分,在平面網絡結構中,所有節點為對等結構,具有完全一致的功能特性,采用自組織協同算法形成網絡,故本文將其作為研究的重點。

(a)無線自組網絡平面網絡結構

(b)無線自組網絡分級網絡結構圖1 無線自組網絡拓撲結構

本文根據該結構的特點構造PPP網絡,PPP用以描述一定區域內節點個數服從泊松分布的網絡,確定節點個數后,所有節點以均勻分布的形式分布在該區域,當該區域足夠大以至于兩個通信設備之間受制于功率、協議等因素無法直接通信時,節點可根據分布式協議與周圍最近鄰的若干個節點相連接。假設指定區域內節點總數為50,節點連接度為5,圖2為根據該參數構造的PPP網絡。

圖2 PPP網絡示例圖

1.2 無線自組網絡干擾分析

圖論理論[15]常用于無線自組網絡分析,在網絡拓撲圖中,以節點表示通信設備,以邊表示設備之間存在通信,用兩節點間的最短路徑——流(flow)來模擬信息傳遞的過程。在衡量節點重要性程度時常使用中介中心性進行度量,根據Freeman的定義[16],中介中心性是指經過節點v的所有最短路徑的數量在網絡全部最短路徑總量中占的比例,計算方式如下

(1)

式中:σsd(v)表示節點s與d之間經過節點v的最短路徑數;σsd表示節點s與d之間的最短路徑數。

對網絡中介中心性最大的節點進行干擾的策略稱之為中介中心性(Betweenness Centrality Attacker,BCA)算法。此外,將最佳干擾策略簡稱為OA(Omniscient Attacker),該策略同中介中心性算法均利用網絡的先驗信息進行攻擊。將強化學習理論用于干擾節點選擇,主流算法有置信上界(Upper Confidence Bound Learning,UCB)算法[17]、利用-探索(Slotted Exploit Explore Learning,SEE)算法[12]、上下文情景(Contextual Bandit Learning)算法,本文將上述算法中性能較優的UCB和SEE作為比較算法。

為衡量各種干擾算法的優劣,可從以下兩個方面進行比較:①累積阻斷網絡流數。每次選擇若干節點進行干擾時,必然會阻斷網絡中的若干條網絡流,隨著干擾的進行,阻斷的網絡流數目越多,算法的干擾性能越好。②算法的魯棒性。無線自組網絡的規模是上下浮動的,并且其拓撲結構、網絡流數也是動態變化的,魯棒性強意味著對不同參數下的無線自組網絡均具有優異的干擾性能。

2 無線自組網絡干擾

2.1 節點相關性

在對目標網絡中的多個節點進行干擾時,往往能夠阻斷一定數目的網絡流,但由于干擾方不知道該網絡拓撲結構,無法對被干擾節點的重要性進行評估,進而在面對信度分配[18]問題時無從下手。例如,圖3是一個小型的網絡拓撲結構示意圖,并假設網絡中的數據流如表1所示,當同時干擾節點1和節點4時,共阻斷5條網絡流,兩節點分別貢獻1條和3條,并共同貢獻1條(flow2),只不過對于干擾方而言,在不具備額外信息的情況下,無法衡量節點1和節點4的重要性,只能將兩個節點同等對待,即各自貢獻2.5條。倘若被干擾的節點是1和節點2,此時共有3條網絡流被阻斷,可認為節點1和節點2各自貢獻1.5條。比較上述兩種情況可以看出,同時干擾節點1和節點4能夠阻斷更多的網絡流,即節點4與節點1之間的相關性更強,在執行網絡多節點干擾任務且已經確定干擾節點1時,更傾向于選擇干擾與該節點相關性更強的節點4而非節點2,定義1給出了節點相關性的概念與性質。因此,干擾方如何根據干擾過程中獲取的信息,充分挖掘網絡節點之間的相關性,對實現目標網絡干擾最大化至關重要。

圖3 小型網絡拓撲結構示意圖

表1 網絡流及流經路徑

定義1節點相關性 給定一個無向網絡拓撲圖G,節點nodep∈V={1,2,…,n},網絡中存在固定數目和路徑的網絡流,當同時從G中刪除任意兩個節點i和j時,i,j∈V,且i≠j,網絡流數目減少了d條,規定該條件下節點i與節點j的相關性為d/2。

性質1節點間的相關性與拓撲圖中網絡流狀態相關,網絡流狀態改變時,節點間的相關性也會相應的變化。

性質2多個節點之間也存在相關性,若同時從G中刪除節點i,節點j以及節點k,i,j,k∈V且i≠j≠k,網絡流數目減少e條,規定此時3個節點中任意兩個節點間的相關性為e/3。

性質3當多次從G中刪除節點i和j時,兩節點之間的相關性可通過對每次相關性求和取均值獲得。

網絡節點之間的相關性如下

(2)

在執行干擾任務前,將R(t)初始化為全0矩陣,元素值隨著干擾任務的進行不斷更新。假定rij(t),i,j∈V,t∈{1,2,…,T}表示第t次干擾時節點i與節點j之間的相關性,對于任意一次干擾,節點i與節點j之間的相關性是相同的,即rij(t)=rji(t),矩陣內元素的更新方式如下

(3)

式中:N表示節點j在本次任務以前被選中的次數。

該矩陣的使用方法如下:已知一個節點i被選中,那么觀察該矩陣第i行,將本行中最大元素對應的列的編號(假設為第j列)作為下一個被選中的節點,同時將該列元素值置零,防止再次被選中;繼續觀察該矩陣第j行,將最大元素對應的列的編號作為下一個被選中的節點并清空相應的列,以此類推,直至以序列的方式挑選出本次干擾的節點集合,最后將相關性矩陣恢復至節點選擇前狀態并用于內部元素的下一次更新。

在節點相關性矩陣中,每個元素表示兩個節點之間的相關性,如果采取貪婪選擇的方式,直接從相關性矩陣中選取值最大的元素對應的節點作為干擾節點,無法保證不同節點對之間的相關性最大,且本文的創新點在于構造節點相關性矩陣,并以此作為干擾節點選擇的依據。如何從相關性矩陣中選擇干擾效果更優的節點,有待于下一步深入研究。

2.2 獎賞依據

本文對未知拓撲結構的無線自組網絡中的多個節點施加干擾時,需要對選擇動作的干擾效果進行評估,即對干擾動作給予獎賞。根據掌握信息的不同,獎賞依據可分為有先驗信息情況下的獎賞和無先驗信息情況下的獎賞。對于前者,算法根據偵察獲得的ACK/NACK信息推測阻斷網絡流數[12],將網絡流減少數目直接作為干擾動作對應的獎賞值。對于后者,算法以干擾過后活躍節點的減少量作為獎賞依據。為了便于同現有算法作比較,本文以阻斷網絡流數作為獎賞依據。

2.3 采用節點相關性的無線自組網絡干擾決策算法

利用節點間的相關性選擇待干擾節點,需要解決兩個最根本的問題:一是干擾方如何具備目標網絡所有節點間的相關性信息;二是干擾方如何確定待干擾節點序列中第一個節點。對于第一個前提條件,可通過設置包含若干干擾次數的初始化階段來滿足,該階段內每次干擾時隨機選擇干擾節點,并根據網絡反饋結果對節點相關性矩陣進行更新,該矩陣可用于后續干擾節點選擇。第二個前提條件依然可通過上述初始化階段來滿足,統計初始化階段每個節點被選中的次數以及獲得的獎賞,根據UCB算法計算每個節點的重要性,將最重要的節點作為待干擾節點序列中的第一個節點。

結合節點相關性概念以及UCB算法,本文提出了一種相關置信上界(Correlation UCB,CUCB)算法來實現無線自組網絡多節點干擾策略選擇。下面為算法的詳細步驟,其中步驟2為初始化階段,步驟3為主循環階段。

步驟1初始化操作(以恒定流為例)。將網絡中節點總數賦值為L,生成全零向量F和P分別用于記錄每個節點獲得的累積獎賞和被選擇次數,構造全零矩陣R(t)統計節點間的相關性。

步驟2fort=1:L執行以下(1)～(3)步:

(1)從網絡中隨機選擇指定數目節點作為干擾動作a;

(2)執行干擾動作a,根據網絡流數目的變化情況更新F和P;

(3)根據式(3)對節點相關性矩陣R(t)的元素進行更新。

步驟3fort

(1)選擇能夠使下面公式最大化的節點

(4)

(2)以該節點作為起始節點,并根據相關性矩陣R(t)依次選擇出待干擾節點,即新的干擾動作a。

(3)執行干擾動作a,根據網絡流數目的變化情況更新F和P。

(4)根據式(3)對節點相關性矩陣R(t)的元素進行更新。

3 實驗仿真

根據無線自組網絡的特點,本文將構建的PPP網絡作為實驗對象,將聯合SEE算法(Joint SEE,JSEE)、最佳干擾策略、中介中心性算法、獨立SEE算法(Independent SEE,ISEE)、獨立UCB算法(Independent UCB,IUCB)等作為比較算法,分別從累積獎賞和魯棒性兩個方面衡量上述算法性能。

3.1 初始化階段對算法性能的影響

2.1節中明確指出,可通過初始化階段構造節點相關性矩陣,還可以根據該階段確定后續干擾時應首先干擾的節點,也就是說,初始化階段是本文提出算法的必要環節,該階段包含干擾次數的多少直接決定著算法的干擾性能。圖4給出了包含不同干擾次數的初始化階段對CUCB算法在累積獎賞方面的比較,總干擾次數為2 000次。

圖4 初始化階段干擾對本文算法學習結果的影響

從圖4可以看出,當初始化階段的干擾次數設置為40次時,利用CUCB算法能夠獲得最大的累積獎賞,過小或過大的設置都會在一定程度上導致累積獎賞的降低,原因在于,較少次數的干擾,使得節點相關性矩陣不夠完整,未能對節點之間的相關性進行準確的衡量;而過多次數的干擾,盡管學習到了更加準確的相關性矩陣,但由于該階段隨機選擇節點的原因,使得干擾效果較差,進而導致累積獎賞偏低。鑒于SEE算法和UCB算法均包含初始化階段,且初始化階段內干擾次數設置與總節點數相同,為了便于同上述兩種算法相比較,本文算法初始化階段的干擾次數同樣設置與總節點數相同,即50次干擾。

3.2 對靜態拓撲和動態拓撲PPP網絡干擾

假定待干擾的PPP網絡中共50個節點,節點的連接度為5,對于靜態拓撲結構,網絡流流數為30條,源節點和目的節點固定不變,干擾方每次干擾5個節點;對于動態拓撲結構,網絡流流數介于[10,30]條,源節點和目的節點隨機選擇,干擾節點數依然為5個。圖5給出了6種算法在不同網絡流狀態下干擾性能比較。

(a)靜態拓撲恒定流PPP網絡5節點干擾

(b)動態拓撲隨機流PPP網絡5節點干擾圖5 對6種算法在不同網絡流狀態下的干擾性能比較

從圖5a可以看出,最佳干擾策略在累積阻斷的網絡流數目最多,CUCB算法累積阻斷的網絡流數僅次于最佳干擾策略,數目約為其89.6%,比JSEE算法高出27.1%。此外,所有算法的獎賞曲線在1 000次干擾后以不同斜率線性增長,線性增長表明每次干擾阻斷的網絡流數不再發生變化,即算法收斂到固定節點,不同斜率意味著算法每次干擾阻斷的網絡流數同樣有差異,斜率越高意味著阻斷的網絡流數越多。

從圖5b中可以看出,當目標網絡的拓撲結構動態變化時,幾種干擾算法的干擾性能均不理想,原因在于本文提出的算法與對比算法均為學習型算法,時刻變化的干擾對象不利于算法學習。但是,比較上述幾種學習型干擾算法可以發現,CUCB算法累積阻斷的網絡流數依然是最高的,表明本文算法干擾性能出眾。

3.3 對不同參數下的PPP網絡進行干擾

為了進一步驗證CUCB算法的魯棒性,圖6從不同節點連接度、不同網絡流數目、不同節點總數、不同干擾節點數等4個方面進行對比。

(a)不同節點連接度條件下

(b)不同網絡流數目條件下

(c)不同節點總數條件下

(d)不同干擾節點數條件圖6 6種算法對不同參數的PPP網絡的干擾性能比較

從圖6a～6d可以看出,同最佳干擾策略相比,CUCB算法累積阻斷的網絡流數仍有一定的差距,但同對比算法比較而言,阻斷的網絡流數始終是最多的,反映出本文算法的干擾性能和魯棒性能優于對比算法。

4 結 論

本文以干擾無線自組網絡中的多個節點作為研究對象,在充分挖掘節點相關性的基礎上結合現有UCB算法,提出了一種未知拓撲無線自組網絡多節點干擾決策算法——CUCB算法,該算法將戰場無線自組網建模為PPP網絡,通過對目標網絡中多個節點同時進行干擾實現通信拒止。文中從靜態拓撲恒定網絡流和動態拓撲隨機網絡流,以及不同網絡參數下的干擾效果驗證所提算法的干擾性能和魯棒性能。仿真結果表明,本文所提算法在累積獎賞方面均優于JSEE算法,且算法具有較強的魯棒性,對不同狀態的PPP網絡均具有優異的干擾效果。

參考文獻:

[1] 劉蔚,趙宇,陳銳. 無線Ad-hoc網絡中基于0-1優化的兩步驟資源分配算法 [J]. 計算機科學,2017,44(1): 103-108.

LIU Wei,ZHAO Yu,CHEN Rui. Zero-one integer programming based optimization model and two phase resource optimization algorithm for wireless Ad-hoc networks [J]. Computer Sciences,2017,44(1): 103-108.

[2] MUKHERJEE A,KESHARY V,PANDYA K. Flying Ad-hoc networks: a comprehensive survey [C]//3rd International Conference on Computer and Communication Technologies. Berlin,Germany: Springer,2016: 1254-1270.

[3] AMURU S,BUEHRER R M. Optimal jamming using delayed learning [C]//Proceedings of 33rd Annual IEEE Military Communications Conference. Piscataway,NJ,USA: IEEE,2014: 1528-1533.

[4] MOON A H,IQBAL U,BASHIR A,et al. Simulating and analyzing RREQ flooding attack in wireless sensor networks [C]// International Conference on Electrical,Electronics,and Optimization Techniques. Piscataway,NJ,USA: IEEE,2016: 3374-3377.

[5] 劉書建,吳晟. 基于Zamp的Dos攻擊可行性分析與研究 [J]. 化工自動化及儀表,2016,43(7): 725-727.

LIU Shujian,WU Sheng. Analysis and study of Dos attack feasibility based on Zmap [J]. Control and Instruments in Chemical Industry,2016,43(7): 725-727.

[6] PROANO A,LAZOS L. Selective jamming attacks in wireless network [C]// 2010 IEEE International Conference on Communication. Piscataway,NJ,USA: IEEE,2010: 11412483.

[7] SEFAIR J A,SMITH J C. Dynamic shortest-path interdiction [J]. Networks,2016,68(4): 315-330.

[8] ALTNER D S,ERGUN O,UHAN N A. The maximum flow network interdiction problem: valid inequalities,integrality gaps,and approximability [J]. Operations Research Letters,2010,38(1): 33-38.

[9] 段勇,崔寶俠,徐心和. 多智能體強化學習及其在足球機器人角色分配中的應用 [J]. 控制理論與應用,2009,26(4): 371-376.

DUAN Yong,CUI Baoxia,XU Xinhe. Multi-agent reinforcement learning and its application to role assignment of robot soccer [J]. Control Theory & Application,2009,26(4): 371-376.

[10] 趙冬斌,邵坤,朱圓恒,等. 深度強化學習綜述: 兼論計算機圍棋的發展 [J]. 控制理論與應用,2016,33(6): 701-717.

ZHAO Dongbin,SHAO Kun,ZHU Yuanheng,et al. Review of deep reinforcement learning and discussion on the development of computer Go [J]. Control Theory & Applications,2016,33(6): 701-717.

[11] 丁樂樂. 基于深度學習和強化學習的車輛定位與識別 [D]. 成都: 電子科技大學,2016: 42-60.

[12] AMURU S,MICHAEL B R,VAN DER SCHAAR M. Blind network interdiction strategies: a learning approach [J]. IEEE Transactions on Cognitive Communications and Networking,2015,1(4): 435-449.

[13] GAI Y,KRISHNAMACHARI B,JAIN R. Combinatorial network optimization with unknown variables: multi-armed bandits with linear reward [J]. Networking IEEE/ACM Transaction on Networking,2012,20(5): 1466-1478.

[14] 張國峰. 無人機自組網路由協議研究 [D]. 沈陽: 沈陽工業大學,2017: 26-45.

[15] 蒲瀟. 戰術自組網網絡結構及分群算法研究 [D]. 大連: 大連理工大學,2009: 14-15.

[16] BRANDES U,BORGATTI S P,FREEMAN L C. Maintain the duality of closeness and betweenness centrality [J]. Social Networks,2016,44: 153-159.

[17] AUER P,CESA B N,FISCHER P. Finite-time analysis of the multi-armed bandit problem [J]. Machine Learning,2002,47(2/3): 2-13.

[18] 高陽,陳世福,陸鑫. 強化學習研究綜述 [J]. 自動化學報,2004,30(1): 86-100.

GAO Yang,CHWN Shifu,LU Xin. Research on reinforcement learning technology: a review [J]. Acta Automatica Sinica,2004,30(1): 86-100.

[本刊相關文獻鏈接]

顓孫少帥,楊俊安,劉輝,等.采用雙層強化學習的干擾決策算法.2018,52(2):63-69.[doi:10.7652/xjtuxb201802010]

李清偉,郭黎利.DS-CDMA系統多波形優化的多址干擾抑制方法.2017,51(10):94-99.[doi:10.7652/xjtuxb201710 016]

楊少奇,田波,周瑞釗.應用雙譜分析和分形維數的雷達欺騙干擾識別.2016,50(12):128-135.[doi:10.7652/xjtuxb2016 12020]

劉立,張衡陽,毛玉泉,等.變換域通信系統抗干擾編碼幅度譜成型算法.2017,51(2):91-96.[doi:10.7652/xjtuxb2017 02015]

孫黎,徐洪斌.協作式終端直通系統中星座旋轉輔助的干擾避免策略.2015,49(12):6-11.[doi:10.7652/xjtuxb201512 002]