鄭博文,肖 卓,劉麗哲,梁 晨
(1.中國電子科技集團公司第五十四研究所,河北 石家莊 050081;2.中國人民解放軍96764部隊,河南 洛陽 471000)
移動自組織網(wǎng)絡(luò)(MANET)是一個自組織、自管理的無線通信網(wǎng)絡(luò),每個節(jié)點既充當(dāng)主機又充當(dāng)路由器,并轉(zhuǎn)發(fā)不在彼此傳輸范圍內(nèi)的節(jié)點數(shù)據(jù),其節(jié)點接入控制、資源分配等MAC協(xié)議設(shè)計較為復(fù)雜,也是MANET領(lǐng)域的研究重點之一。MANET的MAC協(xié)議主要解決隨機接入和資源分配問題,通常可以表述為最優(yōu)化問題和馬爾科夫決策問題(Markov Decision Process,MDP),傳統(tǒng)的MAC協(xié)議往往是對其中多個條件進行理想假設(shè),不能很好地滿足實際網(wǎng)絡(luò)工作環(huán)境要求。當(dāng)網(wǎng)絡(luò)節(jié)點移動快、無線電鏈路環(huán)境復(fù)雜以及傳輸帶寬增加壓力時,高效、穩(wěn)健的MAC協(xié)議設(shè)計變得更加具有挑戰(zhàn)性。
機器學(xué)習(xí)是一門多學(xué)科交叉專業(yè),涵蓋概率論、統(tǒng)計學(xué)和近似論等理論,可以在大量的經(jīng)驗學(xué)習(xí)中自動優(yōu)化或改進算法性能,目前機器學(xué)習(xí)在計算機視覺和自然語言處理等領(lǐng)域取得了重大突破。隨著機器學(xué)習(xí)技術(shù)的發(fā)展,網(wǎng)絡(luò)研究人員也開始認識到深度學(xué)習(xí)的力量和重要性,并在積極探索機器學(xué)習(xí)解決移動網(wǎng)絡(luò)領(lǐng)域特定問題的方法,例如,利用機器學(xué)習(xí)從復(fù)雜的數(shù)據(jù)中自動提取高級特征,用以指導(dǎo)網(wǎng)絡(luò)盡量尋求到最優(yōu)解和最佳路徑,保證MAC協(xié)議的高效性和穩(wěn)健性。
目前雖然有些文獻闡述了機器學(xué)習(xí)技術(shù)在無線網(wǎng)絡(luò)中的應(yīng)用情況,但分散在不同的研究領(lǐng)域,且缺乏針對自組織網(wǎng)絡(luò)的研究綜述。本文在介紹機器學(xué)習(xí)技術(shù)基礎(chǔ)上,分析總結(jié)了機器學(xué)習(xí)用于解決MANET的MAC協(xié)議潛在前景和現(xiàn)有研究成果,對其中的關(guān)鍵技術(shù)以及未來研究方向進行了梳理歸納。
機器學(xué)習(xí)可大致分為三大類:監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)和強化學(xué)習(xí),分為學(xué)習(xí)階段和訓(xùn)練階段。在訓(xùn)練階段,機器根據(jù)訓(xùn)練數(shù)據(jù)訓(xùn)練學(xué)習(xí)模型;在測試階段,機器將訓(xùn)練后的模型應(yīng)用于預(yù)測。監(jiān)督學(xué)習(xí)是從標(biāo)記的數(shù)據(jù)中學(xué)習(xí),主要解決分類和回歸問題,常用的監(jiān)督學(xué)習(xí)算法包括神經(jīng)網(wǎng)絡(luò)、判決樹、支持向量機及Logistic回歸等[1]。無監(jiān)督學(xué)習(xí)是通過無標(biāo)簽數(shù)據(jù)進行學(xué)習(xí),主要解決聚類和降維問題,常用的無監(jiān)督學(xué)習(xí)算法包括聚類算法、自動編碼器和自組織圖(Self-Organizing Map,SOM)等[1]。強化學(xué)習(xí)是以“試錯”方式進行學(xué)習(xí),通過與環(huán)境進行交互獲得的回報指導(dǎo)行為,目標(biāo)是獲得最大回報,主要解決復(fù)雜、多變量問題,常見模型是標(biāo)準的MDP。
MDP可以表示為{S,A,Pa(·,·),Ra(·,·)},其中S為狀態(tài)空間,A為動作空間,定義Pa(·,·)為狀態(tài)轉(zhuǎn)移概率函數(shù),Ra(·,·)為回報函數(shù)。狀態(tài)轉(zhuǎn)移概率函數(shù)采用當(dāng)前狀態(tài)s和可能的新狀態(tài)s′,并以動作a為條件輸出轉(zhuǎn)移到該新狀態(tài)的概率,如下所示:
Pa(s,s′)=Pr(St+1=s′|St=s,At=a)。
(1)
Ra(·,·)給出通過動作a從狀態(tài)s過渡到狀態(tài)s′之后直接獲得的獎勵,其定義為:
Ra(s,s′)=E[Rt+1|St=s,At=a]。
(2)
強化學(xué)習(xí)的目的是尋找策略函數(shù)π,最大化未來長期回報。策略函數(shù)是從感知到的環(huán)境狀態(tài)到處于這些狀態(tài)時要采取的動作的映射。評價策略好壞的值函數(shù)由式(3)給出:
(3)
式中,Rt為隨時間變化觀察到的收益,γ為比例參數(shù),用于權(quán)衡未來收益的權(quán)重要小于當(dāng)前收益。
深度學(xué)習(xí)是機器學(xué)習(xí)領(lǐng)域一個新的研究方向,是一種以人工神經(jīng)網(wǎng)絡(luò)為架構(gòu),學(xué)習(xí)樣本數(shù)據(jù)的內(nèi)在規(guī)律[2],深度學(xué)習(xí)不是機器學(xué)習(xí)的單獨細分[3],可以與監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)和強化學(xué)習(xí)聯(lián)合使用,常見的深度學(xué)習(xí)框架包括深度神經(jīng)網(wǎng)絡(luò)、卷積神經(jīng)網(wǎng)絡(luò)和深度置信網(wǎng)絡(luò)等。
MANET的MAC協(xié)議的關(guān)鍵技術(shù)是設(shè)計高效穩(wěn)健的多節(jié)點協(xié)商機制,實現(xiàn)各節(jié)點對空間、時間、頻率等有限資源的合理共享,以解決各節(jié)點的隨機接入和資源分配問題,保障多節(jié)點之間的穩(wěn)定可靠通信。隨機接入和多址接入問題通常可以表述為MDP,而強化學(xué)習(xí)是解決MDP的有力方案。資源分配問題通常可以表述為最優(yōu)化問題,鑒于機器學(xué)習(xí)的強大函數(shù)擬合能力[4],機器學(xué)習(xí)被認為是解決該問題的主要手段之一。因此,學(xué)者們開始關(guān)注和研究機器學(xué)習(xí)技術(shù)在移動自組網(wǎng)的應(yīng)用。ZHANG C等人[5]調(diào)研了深度學(xué)習(xí)在移動無線網(wǎng)絡(luò)中的研究情況,討論了幾種有助于將深度學(xué)習(xí)有效部署到移動系統(tǒng)上的技術(shù)和平臺,指出當(dāng)前的挑戰(zhàn)和未來的研究方向。他指出,相對于傳統(tǒng)方法,采用深度學(xué)習(xí)解決移動網(wǎng)絡(luò)問題既有優(yōu)勢,又有不足。
采用深度學(xué)習(xí)解決移動網(wǎng)絡(luò)問題的優(yōu)勢主要有[5]:
① 深度學(xué)習(xí)可以從具有復(fù)雜結(jié)構(gòu)和內(nèi)部相關(guān)性的數(shù)據(jù)中自動提取高級特征;
② 移動網(wǎng)絡(luò)可以生成大量不同類型的數(shù)據(jù),深度學(xué)習(xí)能夠處理大量數(shù)據(jù),通過訓(xùn)練防止模型過擬合;
③ 當(dāng)前大多數(shù)移動系統(tǒng)都會生成未標(biāo)記或半標(biāo)記的數(shù)據(jù),深度學(xué)習(xí)可以采用無監(jiān)督的方式學(xué)習(xí);
④ 深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)到的壓縮表示可以在不同任務(wù)之間共享;
⑤ 深度學(xué)習(xí)在處理幾何移動數(shù)據(jù)方面很有效[6]。
采用深度學(xué)習(xí)解決移動網(wǎng)絡(luò)問題的不足主要有[5]:
① 深度學(xué)習(xí)(包括深度強化學(xué)習(xí))容易受到對抗性示例的影響[7-8];
② 深度學(xué)習(xí)算法主要是黑盒子,解釋性很低;
③ 深度學(xué)習(xí)高度依賴數(shù)據(jù);
④ 深度學(xué)習(xí)對計算的要求可能很高;
⑤ 深度神經(jīng)網(wǎng)絡(luò)通常具有許多超參數(shù),因此很難找到其最佳配置。
本節(jié)討論一些使用機器學(xué)習(xí)來增強自組網(wǎng)MAC協(xié)議的工作,包括廣播調(diào)度問題[9-13]、自適應(yīng)MAC協(xié)議[14-15](Self-Adapting MAC Layer,SAML)、多信道自組網(wǎng)MAC協(xié)議[16-19]和異構(gòu)網(wǎng)絡(luò)動態(tài)頻譜共享問題[20-22]。SAML是指系統(tǒng)可以根據(jù)參數(shù)在MAC協(xié)議庫中自動選擇最合適的MAC協(xié)議,并進行MAC協(xié)議的切換。強化學(xué)習(xí)是通過對環(huán)境進行觀測,學(xué)習(xí)最優(yōu)策略的方法,適合用于MAC協(xié)議選擇。多信道多址接入和異構(gòu)網(wǎng)絡(luò)頻譜共享可以表述為MDP,采用深度強化學(xué)習(xí)模型(Deep Rein forcement Learning,DRL)能夠有效地解決該問題[16-17,22-23]。
廣播調(diào)度問題(Broadcast Scheduling Problem,BSP)是移動自組網(wǎng)MAC協(xié)議設(shè)計中資源分配問題的一個代表,也是TDMA網(wǎng)絡(luò)研究的關(guān)鍵問題,其目的是找到一個最佳TDMA調(diào)度,為所有節(jié)點提供傳輸時隙和最大化系統(tǒng)吞吐量,同時最小化TDMA周期[9]??擅枋鋈缦拢?/p>
(4)
由上述可知,廣播調(diào)度問題是NP問題,可以表述為非凸函數(shù)的最優(yōu)化問題,傳統(tǒng)的方案是采用啟發(fā)式方法,具有一定的局限性。已有研究學(xué)者[9-13]使用神經(jīng)網(wǎng)絡(luò)的變體解決廣播調(diào)度問題,包括結(jié)合Hopfield神經(jīng)網(wǎng)絡(luò)和遺傳算法[10]的方法、結(jié)合順序頂點著色(SVC)和噪聲混沌神經(jīng)網(wǎng)絡(luò)(NCNN)的方法[11]。文獻[12]和文獻[13]分別獨立采用結(jié)合模糊邏輯和Hopfield神經(jīng)網(wǎng)絡(luò)的方法,解決BSP問題,其中文獻[12]采用的是單階段方法,一步解決了最小化時隙數(shù)量和最大化網(wǎng)絡(luò)信道利用率兩個目標(biāo);文獻[13]采用兩階段法,首先采用圖論著色算法,找到最小時隙數(shù)量,然后運用模糊Hopfield神經(jīng)網(wǎng)絡(luò)最大化網(wǎng)絡(luò)信道利用率,文獻[13]方法的第2步可以看做是文獻[12]方法在f=2時的特例。研究結(jié)果表明采用機器學(xué)習(xí)方法能夠得到更優(yōu)的結(jié)果。
文獻[12]和文獻[13]的具體解決方案如下:
用μxi表示時隙tx∈T分配給節(jié)點i的程度,最小化代價函數(shù)E表示如下:
(5)
式中,α和β為正系數(shù),f為模糊化參數(shù),diy=1表示節(jié)點i和節(jié)點y相連。等式中的第1項確保了每個節(jié)點至少發(fā)送1次;第2項確保了相距1跳和2跳的節(jié)點不能同時發(fā)送。仿真結(jié)果表明,基于模糊Hopfield神經(jīng)網(wǎng)絡(luò)的BSP方法在平均時間延遲方面,既優(yōu)于結(jié)合Hopfield神經(jīng)網(wǎng)絡(luò)和遺傳算法的方法[10],又優(yōu)于結(jié)合順序頂點著色(SVC)和噪聲混沌神經(jīng)網(wǎng)絡(luò)(NCNN)的方法[11]。
SHA M等人首次提出了SAML,SAML由可重配置MAC庫(Reconfigurable MAC Architecture,RMA)和MAC選擇器兩個主要組件組成,其中RMA用于在不同的MAC協(xié)議之間進行切換,MAC選擇器用于學(xué)習(xí)適合當(dāng)前網(wǎng)絡(luò)條件下的MAC協(xié)議[14]。根據(jù)數(shù)據(jù)包間隔、接收信號強度指示、應(yīng)用層QoS要求等指標(biāo),使用決策樹選擇最優(yōu)MAC協(xié)議。SAML框架如圖1所示[14]。
圖1 SAML架構(gòu)Fig.1 Overview of SAML architecture
ZHANG M等人[15]針對無人機自組網(wǎng),提出了一種可以在CSMA/CA和TDMA協(xié)議之間切換的容錯同步MAC協(xié)議(Fault-tolerant Synchronous-MAC,FS-MAC)。FS-MAC協(xié)議框架如圖2所示,它采用基于分布式Q學(xué)習(xí)的MAC交換方案,包含一個MAC預(yù)選擇操作和一個基于實用拜占庭容錯(PBFT)的共識決策程序,以產(chǎn)生MAC交換決策。通過MAC預(yù)選操作,每個無人機都可以準確評估其性能,并確定哪種MAC協(xié)議更合適。然后,借助基于PBFT的共識決策程序,所有無人機都可以實現(xiàn)容錯同步切換。
圖2 FS-MAC協(xié)議架構(gòu)Fig.2 Overview of FS-MAC architecture
針對多信道TDMA的多址接入問題,NAPARSTEK O等人提出了一種基于深度多用戶強化學(xué)習(xí)的分布式動態(tài)頻譜訪問算法(Deep Q-learning for Spectrum Access,DQSA)[16-17]。DQSA的基本思想是,共享帶寬被分成K個正交信道,在每個時隙的起始,每個用戶選擇一個信道并以一定的傳輸概率發(fā)送一個分組;在每個時隙結(jié)束,已經(jīng)發(fā)送了分組的用戶接收ACK信號。DQSA將信道選擇結(jié)果、信道容量和ACK觀測結(jié)果以熱獨編碼(One-Hot編碼)的方式作為深度神經(jīng)網(wǎng)絡(luò)(Deep Q-Network,DQN)的輸入,DQN的輸出為Q值,即下一時隙的信道選擇結(jié)果,DQN模型如圖3所示[17]。
圖3 DQN模型Fig.3 Model of DQN
由于每個用戶的網(wǎng)絡(luò)狀態(tài)都是部分可觀察到的,并且動態(tài)狀態(tài)是非馬爾可夫的,且由多用戶操作確定,因此添加了一個長短期記憶網(wǎng)絡(luò)(Long Short Term Memory,LSTM)層,該層既保持了內(nèi)部狀態(tài),又隨著時間的推移匯總了觀察結(jié)果,確保了網(wǎng)絡(luò)能夠?qū)W習(xí)歷史經(jīng)驗??紤]無論采取什么動作都不影響Q值的狀態(tài)存在,DQSA采用了Dueling DQN模型[18]。DQSA采用演員-評論家方法(Actor-Critic),訓(xùn)練兩個DQN網(wǎng)絡(luò),DQN1用于選擇動作,DQN2用于估計Q值。DQSA采用Exp3策略[19]進行動作選取,如式(6)所示,可以看作是在softmax和ε-greedy策略之間的平衡,參數(shù)α很小,將其隨時間取為零,因此在選擇具有較高估計Q值的動作方面,該算法隨時間變得更加貪婪。
(6)
DQSA采用線下集中訓(xùn)練,線上分布式執(zhí)行的方式,仿真結(jié)果表明,DQSA在無先驗信息的情況下吞吐量顯著優(yōu)于采用最優(yōu)概率值的時隙化Aloha協(xié)議。
受頻譜資源所限,諸如WiFi、藍牙等多種無線通信技術(shù)使用相同的頻譜進行無線傳輸,從而導(dǎo)致異構(gòu)無線通信網(wǎng)絡(luò)之間的干擾。為了避免這種干擾,往往需要大量的處理設(shè)備協(xié)調(diào)它們之間工作。針對異構(gòu)網(wǎng)絡(luò)動態(tài)頻譜共享的問題,已有學(xué)者采用機器學(xué)習(xí)方法進行解決[20-22]。
(7)
圖4 深度神經(jīng)網(wǎng)絡(luò)模型Fig.4 Model of deep neural network
針對有無ACK的情況,MENNES R等人提出了兩種Xf,n的表達方式。仿真結(jié)果表明,如果來自其他網(wǎng)絡(luò)的節(jié)點按照泊松分布發(fā)送數(shù)據(jù),則能夠?qū)_突次數(shù)減少50%,當(dāng)另一個網(wǎng)絡(luò)的節(jié)點遵循更周期性的流量模式時,可以減少15倍的沖突[20]。
針對異構(gòu)網(wǎng)絡(luò)動態(tài)頻譜共享問題,美國國防高級研究計劃局(Defense Advanced Research Projects Agency,DARPA)主辦了為期3年的頻譜協(xié)作挑戰(zhàn)賽(Spectrum Collaboration Challenge,SC2),該挑戰(zhàn)賽旨在尋找出一種協(xié)作式機器學(xué)習(xí)競爭方法以解決射頻頻譜的稀缺性問題,并且DARPA致力于研究滿足瞬時供需的快速動態(tài)頻譜共享方法。在參與SC2的過程中,YU Y等人獲得靈感,提出了基于深度強化學(xué)習(xí)模型(Deep Reinforcement Learning,DRL)的多址接入?yún)f(xié)議(Deep-reinforcement Learning Multiple Access,DLMA)[21]。
在DLMA協(xié)議中,DRL模型的動作空間為{發(fā)送、等待},觀測空間為{成功、沖突、空閑},通過ACK信號確定觀測值zt∈{成功、沖突、空閑},定義DRL代理在t+1時刻的狀態(tài)空間為ct+1≡(at,zt),其中at∈{發(fā)送、等待}為DRL代理在t時刻的動作,定義在t+1時刻的環(huán)境狀態(tài)為之前M個時刻的集合,st+1≡{ct-M+2…,ct,ct+1},DRL代理在t+1時刻的回報為rt+1∈{0(沖突或空閑),1(成功)}。YU Y等人通過深度神經(jīng)網(wǎng)絡(luò)擬合出Q值(Q Neural Network,QNN),QNN結(jié)構(gòu)如圖5所示,并仿真了DLMA與其他TDMA和ALOHA共存時的異構(gòu)網(wǎng)絡(luò)動態(tài)頻譜共享情況。DLMA節(jié)點在無先驗信息的情況下,通過對環(huán)境、自身行為以及所產(chǎn)生的回報的一系列學(xué)習(xí),可學(xué)習(xí)最佳MAC策略,根據(jù)指定目標(biāo)(最大吞吐量或比例公平)與TDMA和ALOHA節(jié)點和諧共存[21]。
圖5 DLMA協(xié)議的QNN模型Fig.5 Model QNN of protocol DLMA
YU Y等人在DLMA的基礎(chǔ)上,進一步研究,提出載波偵聽深度強化學(xué)習(xí)多址訪問協(xié)議(Carrier-Sense Deep-reinforcement Learning Multiple Access,CS-DLMA)[20],仿真結(jié)果表明,CS-DLMA與TDMA,ALOHA和WiFi協(xié)議共存時,可以通過調(diào)整其自身的傳輸策略來達到α-公平性目標(biāo),當(dāng)與WiFi共存時,CS-DLMA比其他CSMA協(xié)議(例如p-persistent CSMA)更具帕累托效率。
盡管機器學(xué)習(xí)已用于解決移動自組網(wǎng)MAC協(xié)議的諸多問題,但許多問題仍懸而未決,仍需要進一步的研究工作。
(1) 工程實現(xiàn)
針對移動自組網(wǎng)MAC協(xié)議的諸多問題,采用機器學(xué)習(xí)算法得到了很好的效果,但是部分機器學(xué)習(xí)算法有較高的計算復(fù)雜度,因此如何設(shè)計硬件架構(gòu),高效地實現(xiàn)機器學(xué)習(xí)算法,滿足產(chǎn)品化要求,是未來需要研究解決的問題。
(2) 針對無線自組網(wǎng)設(shè)計的機器學(xué)習(xí)架構(gòu)
現(xiàn)有機器學(xué)習(xí)架構(gòu)在設(shè)計之初主要是用于圖像處理,如卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Networks,CNN)和深度殘差網(wǎng)絡(luò)(Residual Network,ResNet);或是自然語言處理,如循環(huán)神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Networks,RNN),值得考慮針對無線自組網(wǎng)設(shè)計新的機器學(xué)習(xí)架構(gòu)。
(3) 基于機器學(xué)習(xí)的多點交互機制學(xué)習(xí)
針對多信道自組網(wǎng)MAC協(xié)議和異構(gòu)網(wǎng)絡(luò)動態(tài)頻譜共享問題,現(xiàn)有文獻通常僅利用了ACK信息,沒有考慮各個節(jié)點交互信息的情況。交互信息如何設(shè)計,能否通過機器學(xué)習(xí)算法自動學(xué)習(xí)需要交互的信息內(nèi)容,都是值得研究的問題。FOERSTER J等人[23]首次通過深度學(xué)習(xí)方法研究了多智能體(Multi-Agent)之間的交互機制,將這種思想用在無線通信上,通過深度學(xué)習(xí),讓多智能體自己學(xué)習(xí)通信協(xié)議是未來的研究方向。
(4) 基于多智能體強化學(xué)習(xí)的自組網(wǎng)協(xié)議
由于在無線自組網(wǎng)中,每個節(jié)點很難觀測全局狀態(tài)信息,這是部分可觀測馬爾科夫決策問題(Partially Observable Markov Decision Process,POMDP),現(xiàn)有文獻通常通過采用集中調(diào)度或線下集中式學(xué)習(xí)線上分布式部署的方式回避該問題。因此,在部分可觀測的情況下,從每個節(jié)點角度來看,當(dāng)其他節(jié)點積極探索狀態(tài)和操作空間以進行策略學(xué)習(xí)時,它觀察到的環(huán)境就會呈現(xiàn)出不穩(wěn)定狀態(tài),由于環(huán)境不穩(wěn)定和局部可觀察性,使得學(xué)習(xí)變得極為困難,多智能體強化學(xué)習(xí)[24](Multi-Agent reinforcement learning,MARL)被認為是解決該問題的手段,研究基于多智能體強化學(xué)習(xí)的自組網(wǎng)協(xié)議是未來的研究方向。
隨著機器學(xué)習(xí)技術(shù)的不斷發(fā)展,以及其在移動自組網(wǎng)應(yīng)用研究的不斷深入,基于機器學(xué)習(xí)的移動自組網(wǎng)MAC協(xié)議技術(shù)會越來越完善,有望大幅提升復(fù)雜環(huán)境下的移動自組網(wǎng)性能,進一步滿足其應(yīng)用需求。本文詳細介紹了基于機器學(xué)習(xí)的自組網(wǎng)MAC協(xié)議研究的最新成果,包括廣播調(diào)度問題、SAML、多信道自組網(wǎng)MAC協(xié)議和異構(gòu)網(wǎng)絡(luò)動態(tài)頻譜共享問題;展望了未來的研究方向,包括工程實現(xiàn)、針對無線自組網(wǎng)設(shè)計機器學(xué)習(xí)架構(gòu)、基于機器學(xué)習(xí)的多點交互機制學(xué)習(xí)和基于多智能體強化學(xué)習(xí)的自組網(wǎng)協(xié)議。旨在為關(guān)注和研究該領(lǐng)域的初學(xué)者提供一些思路,啟發(fā)他們積極探索和挖掘該領(lǐng)域的技術(shù)潛力,推動移動自組網(wǎng)技術(shù)的發(fā)展。