基于機器學習的移動自組網MAC協議研究綜述

鄭博文，肖 卓，劉麗哲，梁 晨

(1.中國電子科技集團公司第五十四研究所，河北 石家莊 050081;2.中國人民解放軍96764部隊，河南 洛陽 471000)

0 引言

移動自組織網絡(MANET)是一個自組織、自管理的無線通信網絡，每個節點既充當主機又充當路由器，并轉發不在彼此傳輸范圍內的節點數據，其節點接入控制、資源分配等MAC協議設計較為復雜，也是MANET領域的研究重點之一。MANET的MAC協議主要解決隨機接入和資源分配問題，通常可以表述為最優化問題和馬爾科夫決策問題(Markov Decision Process,MDP)，傳統的MAC協議往往是對其中多個條件進行理想假設，不能很好地滿足實際網絡工作環境要求。當網絡節點移動快、無線電鏈路環境復雜以及傳輸帶寬增加壓力時，高效、穩健的MAC協議設計變得更加具有挑戰性。

機器學習是一門多學科交叉專業，涵蓋概率論、統計學和近似論等理論，可以在大量的經驗學習中自動優化或改進算法性能，目前機器學習在計算機視覺和自然語言處理等領域取得了重大突破。隨著機器學習技術的發展，網絡研究人員也開始認識到深度學習的力量和重要性，并在積極探索機器學習解決移動網絡領域特定問題的方法，例如，利用機器學習從復雜的數據中自動提取高級特征，用以指導網絡盡量尋求到最優解和最佳路徑，保證MAC協議的高效性和穩健性。

目前雖然有些文獻闡述了機器學習技術在無線網絡中的應用情況，但分散在不同的研究領域，且缺乏針對自組織網絡的研究綜述。本文在介紹機器學習技術基礎上，分析總結了機器學習用于解決MANET的MAC協議潛在前景和現有研究成果，對其中的關鍵技術以及未來研究方向進行了梳理歸納。

1 研究現狀

機器學習可大致分為三大類：監督學習、無監督學習和強化學習，分為學習階段和訓練階段。在訓練階段，機器根據訓練數據訓練學習模型；在測試階段，機器將訓練后的模型應用于預測。監督學習是從標記的數據中學習，主要解決分類和回歸問題，常用的監督學習算法包括神經網絡、判決樹、支持向量機及Logistic回歸等[1]。無監督學習是通過無標簽數據進行學習，主要解決聚類和降維問題，常用的無監督學習算法包括聚類算法、自動編碼器和自組織圖(Self-Organizing Map,SOM)等[1]。強化學習是以“試錯”方式進行學習，通過與環境進行交互獲得的回報指導行為，目標是獲得最大回報，主要解決復雜、多變量問題，常見模型是標準的MDP。

MDP可以表示為{S,A,Pa(·,·),Ra(·,·)}，其中S為狀態空間，A為動作空間，定義Pa(·,·)為狀態轉移概率函數，Ra(·,·)為回報函數。狀態轉移概率函數采用當前狀態s和可能的新狀態s′，并以動作a為條件輸出轉移到該新狀態的概率，如下所示：

Pa(s,s′)=Pr(St+1=s′|St=s,At=a)。

(1)

Ra(·,·)給出通過動作a從狀態s過渡到狀態s′之后直接獲得的獎勵，其定義為：

Ra(s,s′)=E[Rt+1|St=s,At=a]。

(2)

強化學習的目的是尋找策略函數π，最大化未來長期回報。策略函數是從感知到的環境狀態到處于這些狀態時要采取的動作的映射。評價策略好壞的值函數由式(3)給出：

(3)

式中，Rt為隨時間變化觀察到的收益，γ為比例參數，用于權衡未來收益的權重要小于當前收益。

深度學習是機器學習領域一個新的研究方向，是一種以人工神經網絡為架構，學習樣本數據的內在規律[2]，深度學習不是機器學習的單獨細分[3]，可以與監督學習、無監督學習和強化學習聯合使用，常見的深度學習框架包括深度神經網絡、卷積神經網絡和深度置信網絡等。

MANET的MAC協議的關鍵技術是設計高效穩健的多節點協商機制，實現各節點對空間、時間、頻率等有限資源的合理共享，以解決各節點的隨機接入和資源分配問題，保障多節點之間的穩定可靠通信。隨機接入和多址接入問題通常可以表述為MDP，而強化學習是解決MDP的有力方案。資源分配問題通常可以表述為最優化問題，鑒于機器學習的強大函數擬合能力[4]，機器學習被認為是解決該問題的主要手段之一。因此，學者們開始關注和研究機器學習技術在移動自組網的應用。ZHANG C等人[5]調研了深度學習在移動無線網絡中的研究情況，討論了幾種有助于將深度學習有效部署到移動系統上的技術和平臺，指出當前的挑戰和未來的研究方向。他指出，相對于傳統方法，采用深度學習解決移動網絡問題既有優勢，又有不足。

采用深度學習解決移動網絡問題的優勢主要有[5]：

① 深度學習可以從具有復雜結構和內部相關性的數據中自動提取高級特征；

② 移動網絡可以生成大量不同類型的數據，深度學習能夠處理大量數據，通過訓練防止模型過擬合；

③ 當前大多數移動系統都會生成未標記或半標記的數據，深度學習可以采用無監督的方式學習；

④ 深度神經網絡學習到的壓縮表示可以在不同任務之間共享；

⑤ 深度學習在處理幾何移動數據方面很有效[6]。

采用深度學習解決移動網絡問題的不足主要有[5]：

① 深度學習(包括深度強化學習)容易受到對抗性示例的影響[7-8]；

② 深度學習算法主要是黑盒子，解釋性很低；

③ 深度學習高度依賴數據；

④ 深度學習對計算的要求可能很高；

⑤ 深度神經網絡通常具有許多超參數，因此很難找到其最佳配置。

2 關鍵技術

本節討論一些使用機器學習來增強自組網MAC協議的工作，包括廣播調度問題[9-13]、自適應MAC協議[14-15](Self-Adapting MAC Layer,SAML)、多信道自組網MAC協議[16-19]和異構網絡動態頻譜共享問題[20-22]。SAML是指系統可以根據參數在MAC協議庫中自動選擇最合適的MAC協議，并進行MAC協議的切換。強化學習是通過對環境進行觀測，學習最優策略的方法，適合用于MAC協議選擇。多信道多址接入和異構網絡頻譜共享可以表述為MDP，采用深度強化學習模型(Deep Rein forcement Learning,DRL)能夠有效地解決該問題[16-17,22-23]。

2.1 基于機器學習的廣播調度問題

廣播調度問題(Broadcast Scheduling Problem，BSP)是移動自組網MAC協議設計中資源分配問題的一個代表，也是TDMA網絡研究的關鍵問題，其目的是找到一個最佳TDMA調度，為所有節點提供傳輸時隙和最大化系統吞吐量，同時最小化TDMA周期[9]。可描述如下：

(4)

由上述可知，廣播調度問題是NP問題，可以表述為非凸函數的最優化問題，傳統的方案是采用啟發式方法，具有一定的局限性。已有研究學者[9-13]使用神經網絡的變體解決廣播調度問題，包括結合Hopfield神經網絡和遺傳算法[10]的方法、結合順序頂點著色(SVC)和噪聲混沌神經網絡(NCNN)的方法[11]。文獻[12]和文獻[13]分別獨立采用結合模糊邏輯和Hopfield神經網絡的方法，解決BSP問題，其中文獻[12]采用的是單階段方法，一步解決了最小化時隙數量和最大化網絡信道利用率兩個目標；文獻[13]采用兩階段法，首先采用圖論著色算法，找到最小時隙數量，然后運用模糊Hopfield神經網絡最大化網絡信道利用率，文獻[13]方法的第2步可以看做是文獻[12]方法在f=2時的特例。研究結果表明采用機器學習方法能夠得到更優的結果。

文獻[12]和文獻[13]的具體解決方案如下：

用μxi表示時隙tx∈T分配給節點i的程度，最小化代價函數E表示如下：

(5)

式中，α和β為正系數，f為模糊化參數，diy=1表示節點i和節點y相連。等式中的第1項確保了每個節點至少發送1次；第2項確保了相距1跳和2跳的節點不能同時發送。仿真結果表明，基于模糊Hopfield神經網絡的BSP方法在平均時間延遲方面，既優于結合Hopfield神經網絡和遺傳算法的方法[10]，又優于結合順序頂點著色(SVC)和噪聲混沌神經網絡(NCNN)的方法[11]。

2.2 SAML

SHA M等人首次提出了SAML，SAML由可重配置MAC庫(Reconfigurable MAC Architecture,RMA)和MAC選擇器兩個主要組件組成，其中RMA用于在不同的MAC協議之間進行切換，MAC選擇器用于學習適合當前網絡條件下的MAC協議[14]。根據數據包間隔、接收信號強度指示、應用層QoS要求等指標，使用決策樹選擇最優MAC協議。SAML框架如圖1所示[14]。

圖1 SAML架構Fig.1 Overview of SAML architecture

ZHANG M等人[15]針對無人機自組網，提出了一種可以在CSMA/CA和TDMA協議之間切換的容錯同步MAC協議(Fault-tolerant Synchronous-MAC,FS-MAC)。FS-MAC協議框架如圖2所示，它采用基于分布式Q學習的MAC交換方案，包含一個MAC預選擇操作和一個基于實用拜占庭容錯(PBFT)的共識決策程序，以產生MAC交換決策。通過MAC預選操作，每個無人機都可以準確評估其性能，并確定哪種MAC協議更合適。然后，借助基于PBFT的共識決策程序，所有無人機都可以實現容錯同步切換。

圖2 FS-MAC協議架構Fig.2 Overview of FS-MAC architecture

2.3 多信道自組網MAC協議

針對多信道TDMA的多址接入問題，NAPARSTEK O等人提出了一種基于深度多用戶強化學習的分布式動態頻譜訪問算法(Deep Q-learning for Spectrum Access,DQSA)[16-17]。DQSA的基本思想是，共享帶寬被分成K個正交信道，在每個時隙的起始，每個用戶選擇一個信道并以一定的傳輸概率發送一個分組；在每個時隙結束，已經發送了分組的用戶接收ACK信號。DQSA將信道選擇結果、信道容量和ACK觀測結果以熱獨編碼(One-Hot編碼)的方式作為深度神經網絡(Deep Q-Network,DQN)的輸入，DQN的輸出為Q值，即下一時隙的信道選擇結果，DQN模型如圖3所示[17]。

圖3 DQN模型Fig.3 Model of DQN

由于每個用戶的網絡狀態都是部分可觀察到的，并且動態狀態是非馬爾可夫的，且由多用戶操作確定，因此添加了一個長短期記憶網絡(Long Short Term Memory,LSTM)層，該層既保持了內部狀態，又隨著時間的推移匯總了觀察結果，確保了網絡能夠學習歷史經驗。考慮無論采取什么動作都不影響Q值的狀態存在，DQSA采用了Dueling DQN模型[18]。DQSA采用演員-評論家方法(Actor-Critic)，訓練兩個DQN網絡，DQN1用于選擇動作，DQN2用于估計Q值。DQSA采用Exp3策略[19]進行動作選取，如式(6)所示，可以看作是在softmax和ε-greedy策略之間的平衡，參數α很小，將其隨時間取為零，因此在選擇具有較高估計Q值的動作方面，該算法隨時間變得更加貪婪。

(6)

DQSA采用線下集中訓練，線上分布式執行的方式，仿真結果表明，DQSA在無先驗信息的情況下吞吐量顯著優于采用最優概率值的時隙化Aloha協議。

2.4 異構網絡動態頻譜共享問題

受頻譜資源所限，諸如WiFi、藍牙等多種無線通信技術使用相同的頻譜進行無線傳輸，從而導致異構無線通信網絡之間的干擾。為了避免這種干擾，往往需要大量的處理設備協調它們之間工作。針對異構網絡動態頻譜共享的問題，已有學者采用機器學習方法進行解決[20-22]。

(7)

圖4 深度神經網絡模型Fig.4 Model of deep neural network

針對有無ACK的情況，MENNES R等人提出了兩種Xf,n的表達方式。仿真結果表明，如果來自其他網絡的節點按照泊松分布發送數據，則能夠將沖突次數減少50%，當另一個網絡的節點遵循更周期性的流量模式時，可以減少15倍的沖突[20]。

針對異構網絡動態頻譜共享問題，美國國防高級研究計劃局(Defense Advanced Research Projects Agency,DARPA)主辦了為期3年的頻譜協作挑戰賽(Spectrum Collaboration Challenge,SC2)，該挑戰賽旨在尋找出一種協作式機器學習競爭方法以解決射頻頻譜的稀缺性問題，并且DARPA致力于研究滿足瞬時供需的快速動態頻譜共享方法。在參與SC2的過程中，YU Y等人獲得靈感，提出了基于深度強化學習模型(Deep Reinforcement Learning,DRL)的多址接入協議(Deep-reinforcement Learning Multiple Access,DLMA)[21]。

在DLMA協議中，DRL模型的動作空間為{發送、等待}，觀測空間為{成功、沖突、空閑}，通過ACK信號確定觀測值zt∈{成功、沖突、空閑}，定義DRL代理在t+1時刻的狀態空間為ct+1≡(at,zt)，其中at∈{發送、等待}為DRL代理在t時刻的動作，定義在t+1時刻的環境狀態為之前M個時刻的集合，st+1≡{ct-M+2…,ct,ct+1}，DRL代理在t+1時刻的回報為rt+1∈{0(沖突或空閑),1(成功)}。YU Y等人通過深度神經網絡擬合出Q值(Q Neural Network，QNN)，QNN結構如圖5所示，并仿真了DLMA與其他TDMA和ALOHA共存時的異構網絡動態頻譜共享情況。DLMA節點在無先驗信息的情況下，通過對環境、自身行為以及所產生的回報的一系列學習，可學習最佳MAC策略，根據指定目標(最大吞吐量或比例公平)與TDMA和ALOHA節點和諧共存[21]。

圖5 DLMA協議的QNN模型Fig.5 Model QNN of protocol DLMA

YU Y等人在DLMA的基礎上，進一步研究，提出載波偵聽深度強化學習多址訪問協議(Carrier-Sense Deep-reinforcement Learning Multiple Access,CS-DLMA)[20]，仿真結果表明，CS-DLMA與TDMA，ALOHA和WiFi協議共存時，可以通過調整其自身的傳輸策略來達到α-公平性目標，當與WiFi共存時，CS-DLMA比其他CSMA協議(例如p-persistent CSMA)更具帕累托效率。

3 未來研究方向

盡管機器學習已用于解決移動自組網MAC協議的諸多問題，但許多問題仍懸而未決，仍需要進一步的研究工作。

(1) 工程實現

針對移動自組網MAC協議的諸多問題，采用機器學習算法得到了很好的效果，但是部分機器學習算法有較高的計算復雜度，因此如何設計硬件架構，高效地實現機器學習算法，滿足產品化要求，是未來需要研究解決的問題。

(2) 針對無線自組網設計的機器學習架構

現有機器學習架構在設計之初主要是用于圖像處理，如卷積神經網絡(Convolutional Neural Networks,CNN)和深度殘差網絡(Residual Network,ResNet)；或是自然語言處理，如循環神經網絡(Recurrent Neural Networks,RNN)，值得考慮針對無線自組網設計新的機器學習架構。

(3) 基于機器學習的多點交互機制學習

針對多信道自組網MAC協議和異構網絡動態頻譜共享問題，現有文獻通常僅利用了ACK信息，沒有考慮各個節點交互信息的情況。交互信息如何設計，能否通過機器學習算法自動學習需要交互的信息內容，都是值得研究的問題。FOERSTER J等人[23]首次通過深度學習方法研究了多智能體(Multi-Agent)之間的交互機制，將這種思想用在無線通信上，通過深度學習，讓多智能體自己學習通信協議是未來的研究方向。

(4) 基于多智能體強化學習的自組網協議

由于在無線自組網中，每個節點很難觀測全局狀態信息，這是部分可觀測馬爾科夫決策問題(Partially Observable Markov Decision Process,POMDP)，現有文獻通常通過采用集中調度或線下集中式學習線上分布式部署的方式回避該問題。因此，在部分可觀測的情況下，從每個節點角度來看，當其他節點積極探索狀態和操作空間以進行策略學習時，它觀察到的環境就會呈現出不穩定狀態，由于環境不穩定和局部可觀察性，使得學習變得極為困難，多智能體強化學習[24](Multi-Agent reinforcement learning,MARL)被認為是解決該問題的手段，研究基于多智能體強化學習的自組網協議是未來的研究方向。

4 結束語

隨著機器學習技術的不斷發展，以及其在移動自組網應用研究的不斷深入，基于機器學習的移動自組網MAC協議技術會越來越完善，有望大幅提升復雜環境下的移動自組網性能，進一步滿足其應用需求。本文詳細介紹了基于機器學習的自組網MAC協議研究的最新成果，包括廣播調度問題、SAML、多信道自組網MAC協議和異構網絡動態頻譜共享問題；展望了未來的研究方向，包括工程實現、針對無線自組網設計機器學習架構、基于機器學習的多點交互機制學習和基于多智能體強化學習的自組網協議。旨在為關注和研究該領域的初學者提供一些思路，啟發他們積極探索和挖掘該領域的技術潛力，推動移動自組網技術的發展。