海上自組網中基于偵聽的MAC協議退避算法

肖峰　竇崢

摘要 無人艇通常以編隊協同的方式進行作業，并通過自組網進行數據交換.因海浪等因素影響，海上自組網的信道傳輸損耗通常處于動態變化中，現有MAC協議的退避算法在動態海上環境下無法區分分組碰撞和分組丟失，會出現可靠性和穩定性下降的問題.為此，本文提出一種基于信道監聽的自適應最小競爭窗口退避算法，該算法通過感知鄰近競爭節點數目來估計信道狀態，降低信道沖突概率和重傳次數，提升了網絡整體的可靠性和穩定性.仿真結果表明，與經典BEB算法相比，改進算法的吞吐量和公平性分別最大提高28.67%和62.00%，端到端延時和丟包率分別最大降低2.84%和15.10%.關鍵詞 退避算法；海上通信；自組網；信道監聽；自適應；最小競爭窗口

中圖分類號TN929.5

文獻標志碼A

0 引言

海上自組網是海上通信網絡的一種組網形式.由于海面環境復雜、海面粗糙度多變以及天氣頻繁變化等因素[1-2]，海上通信網絡經常發生分組丟失和傳輸中斷[3-4].因此，如何提升海上自組網的穩定性和可靠性成為了一個不可忽視的問題.

在無線自組網中，媒體接入控制（Medium Access Control，MAC）層與網絡傳輸的穩定性和可靠性直接相關.與現有的無線移動自組網一樣，海上無線自組網的MAC層面臨的主要挑戰之一就是退避算法.作為協議體系中較為底層的算法，退避算法為網絡中的所有節點提供可靠的信道接入時機，在保證和平衡節點的數據傳輸速率、端到端時延、分組成功率和公平性上起到了至關重要的作用.但與現有無線自組網不同的是，海上無線自組網MAC層的退避算法必須能夠抵抗多樣的海上信道干擾和隨機變化的傳輸損耗對于網絡性能的影響[5-6].因此，對于海上自組網的MAC協議退避算法的研究是非常必要的.

針對海上自組網的MAC協議退避算法的研究進展緩慢，現有的海上網絡依舊使用無線移動自組網的退避算法.其中最為經典的是二進制指數退避（Binary Exponential Backoff，BEB）[7]算法，其對于競爭窗口的調整方法是指數增加、定值縮小.因BEB算法存在節點競爭不公平和吞吐量受限等缺陷，所以提出改進的退避算法[8-9]，大致可以分為兩種類型：基于競爭窗口變化方式的退避算法和基于網絡狀態估計的退避算法.

基于競爭窗口變化方式的退避算法的設計思路是更新競爭窗口的變化規則.目前大多改進算法屬于這一類，例如，旨在提升網絡收斂速度的指數增加指數減少（Exponential Increase Exponential Decrease，EIED）[10]的退避算法和能夠兼顧所有負載情況下網絡性能要求的乘性增加、乘性/線性減少（Multiplicative Increase Multiplicate/ Linear Decrease，MIMLD）[11]的退避算法等.這些算法機制簡單，沒有額外開銷，但是由于其僅通過信道競爭調整退避窗口，無法區分分組碰撞和丟失，且窗口變化的參數固定，無法針對海上動態信道環境進行自適應調整，其網絡性能仍存在很大的提升空間.

基于網絡狀態估計的退避算法的設計思路是讓節點通過信道信息估測網絡負載變化，對窗口變化因子進行自適應調整.例如，基于碰撞的自適應退避算法（Collision-Aware Backoff Mechanism，CABM）[12]通過統計固定周期內的發送失敗次數和發送總數來計算自己的碰撞概率，進而調整自身競爭窗口變化策略.該類算法相較于基于競爭窗口變化方式的算法，其理論性能更加優秀.但由于需要一定時間和周期采集計算網絡信息，該類算法收斂速度更慢，且會誤判海上信道的分組丟失為分組碰撞，錯誤估計網絡負載狀態，造成節點出現不必要的等待，導致網絡延遲增加，所以該類算法對變化迅速的海上環境適應性較差.

為了解決當前自組網退避算法在海上信道性能表現不佳的問題，本文提出一種新的MAC的退避算法，為海上無人艇節點間提供可靠通信傳輸，其設計思路是通過偵聽機制對鄰近活躍節點數目進行感知，估計信道實際負載狀態，自適應調整競爭窗口，使其能夠在海上組網中保持良好的網絡性能.

1 系統模型

2 理論建模與ALBI退避算法設計由于海洋信道是快速隨機變化的，無法迅速適應海洋信道的網絡會因為信道沖突和重傳而導致網絡整體的可靠性和穩定性下降.本節首先利用數學建模分析最小沖突概率與鄰居節點數目關系，進而得到最佳競爭窗口的計算方法，最后提出基于偵聽機制的對數退避算法（Adaptive Logarithm Backoff based on Interception，ALBI）.

2.1 自組網MAC層傳輸過程建模

2.2 基于偵聽機制的對數自適應退避算法

3 仿真條件與性能分析為了驗證基于偵聽機制的自適應對數退避（ALBI）算法的有效性，本節利用OMNET++實現ALBI算法的仿真分析，并將其與其他現有的退避算法進行比較.

3.1 仿真場景與參數設計基于OMNET++建立的仿真網絡，場景模型參考圖1，該網絡是由n個移動節點（例如船只、艦艇等）組成的單跳網絡，隨機分布在400 m×300 m的區域中，節點的目標地址隨機選擇，仿真參數如表1所示，網絡仿真時間為300 s.

3.2 性能分析本小節主要將ALBI算法與傳統BEB[7]、EIED[10]、MIMLD[11]和CABM[12]算法進行比較分析，分別從網絡歸一化吞吐量、公平性、端到端時延和丟包率4個指標來評估算法性能.

通過對比網絡中不同競爭節點數目的情況，本文得到幾種退避算法的性能比較，如圖3—6所示.

從圖3可以看出：退避算法的網絡整體吞吐量在16個競爭節點時到達峰值，此時網絡負載飽和，之后增加的競爭節點會對吞吐量產生負面收益，其中CABM、EIED和BEB算法都隨著網絡節點數目的增加產生了明顯的下降趨勢，而MIMLD算法只是略有下降，基本保持穩定；ALBI算法吞吐量性能最好，在網絡負載最大、節點數目最多時，ALBI算法相比MIMLD、EIED、BEB和CABM算法吞吐量分別提高4.5%、13.72%、28.67%和52.89%.從圖4可以看出：所有算法的公平性指標在網絡競爭不激烈時都處于最佳狀態，隨著網絡中競爭節點的增多，公平性指標因為網絡負載的增大而降低，其中EIED、CABM和BEB算法的公平性在高負載下急劇下降，MIMLD算法公平性指標在高負載下略有下降，而ALBI算法的公平性基本不受影響.在網絡負載最大、節點數目最多時，ALBI算法相比MIMLD、CABM、BEB和EIED算法公平性分別提高7.82%、44.32%、62.00%和90.40%.

從圖5可以看出，端到端延時性能隨著節點數目的增加而下降，這是因為競爭節點數目的增加導致信道爭用時碰撞的概率增加，所以傳輸時延增加.在低負載時，ALBI算法的延時性能最佳，隨著節點數目增加，網絡負載進入飽和狀態，ALBI算法的延時性能逐漸下降，但與其他算法之間依舊存在性能優勢；在網絡負載最大時，ALBI算法相比于MIMLD、EIED、BEB和CABM算法端到端延時分別減少1.10%、2.60%、2.84%和4.72%.

從圖6可以看出：CABM算法的丟包率隨著節點數目增加，上升很快，其性能甚至劣于傳統的BEB算法；EIED丟包率基本保持穩定；ALBI和MIMLD丟包率基本不變，約等于0，但ALBI算法更接近于0.ALBI算法相比于MIMLD、EIED、BEB和CABM算法的丟包率分別減少0.29%、2.06%、15.10%和34.88%.綜上所述，基于碰撞情況估計信道競爭的CABM算法無法適應海上變化的信道環境，這主要是因為海上信道的傳輸損耗隨機變化，使得節點傳輸失敗的原因不僅僅是信道爭用失敗，也可能是節點之間因為信道傳輸損耗過高無法通信，但通過信道碰撞和信道占用情況預測下一時刻信道競爭態勢的方法無法區分二者；同時，由于信道傳輸損耗的隨機變化，不同時刻存在信道競爭的鄰居節點數目也會隨機發生改變，因此基于平均碰撞概率的信道情況分析方法無法根據過去的數據準確預測未來網絡競爭的隨機性的變化，所以CABM算法經常發生節點之間的信道碰撞和不必要的信道等待，導致該算法的穩定性和可靠性要遠低于預期，其性能表現甚至遠低于傳統的BEB算法.BEB、EIED和MIMLD等靜態競爭窗口調節因子的算法在海上自組網中的綜合性能要略優于CABM算法，但因為窗口調節因子固定，只能依賴過去分組競爭的成敗來調整現在的競爭窗口等缺陷.隨著網絡節點數增加，網絡負載增大，使用BEB、EIED和MIMLD等算法的網絡節點沖突加劇，其吞吐量、公平性和延時等性能都存在著不同程度的下降.其中，由于MIMLD算法采用門限窗口的機制，對于高負載和低負載網絡的競爭窗口采取不同的變化邏輯，所以其性能表現比較穩定，但仍與ALBI算法之間存在性能差距.相比于仿真測試的其他算法，ALBI算法的性能最為優秀.ALBI算法采用偵聽機制和自適應競爭窗口調整因子和最佳初始競爭窗口的設計，不再過分依賴過去的信道爭用情況來調整競爭窗口，而是根據鄰居節點數目來調整競爭窗口，使得競爭窗口維持在一個動態的合理的數值.ALBI算法雖然會略微增加網絡延時，但避免了因為分組碰撞而損失過多的網絡性能，并且改善了激烈信道競爭時節點發送成功后退避時間太短的缺陷，減少了不必要的信道碰撞和傳輸時間浪費，提升了網絡的公平性.同時，自適應競爭窗口調整因子可以促使競爭窗口快速收斂，使得網絡發生重構時，當前節點的競爭窗口可以迅速適應當前網絡的變化情況.對比仿真結果可以得出結論：ALBI算法是當前算法中最適合海上無線自組網的選擇.4 結束語本文提出一種高效可靠的海上網絡的競爭式MAC退避算法，該算法通過偵聽機制來收集鄰近活躍競爭節點信息，通過自適應競爭窗口調整因子和自適應最佳初始競爭窗口兩種機制，提高了網絡的綜合傳輸性能.OMNET++仿真結果表明，相較于已有算法，ALBI算法在高負載的海上網絡環境下能夠取得更好的性能.未來將會進一步研究基于ALBI的改進方法，在保證公平性的同時繼續提高算法的吞吐量、降低延時和丟包率.

參考文獻 References

［1］張瑞杰，彭琳琳，付林罡，等.海上無人船自組網隨機接入仿真研究[J].遙測遙控，2020，41（5）：29-35ZHANG Ruijie，PENG Linlin，FU Lingang，et al.Random access technique for unmanned surface vehicle ad-hoc network[J].Journal of Telemetry，Tracking and Command，2020，41（5）：29-35

[2] 石堯，李暉，杜文才，等.基于Ad Hoc移動節點模型的海上DTN建模與性能分析[J].計算機工程，2018，44（3）：82-86SHI Yao，LI Hui，DU Wencai，et al.Modeling and performance analysis of marine DTN based on ad hoc mobile nodes model[J].Computer Engineering，2018，44（3）：82-86

[3] Hosseini-Fahraji A，Zeng K，Yang Y，et al.A self-sustaining maritime mesh network[C]//2019 United States National Committee of URSI National Radio Science Meeting （USNC-URSI NRSM）.IEEE，2019：1-2

[4] Yau K L A，Syed A R，Hashim W，et al.Maritime networking：bringing Internet to the sea[J].IEEE Access，2019，7：48236-4825

[5] 李瑞景.海上寬帶無線自組網多信道MAC協議研究[D].大連：大連海事大學，2019LI Ruijing.Study on the multi-channel MAC protocol of maritime broadband wireless ad hoc network[D].Dalian：Dalian Maritime University，2019

[6] 張鍵.海上寬帶無線自組網MAC協議設計與實現[D].大連：大連海事大學，2019ZHANG Jian.Design and implementation of MAC protocol for maritime broadband wireless ad hoc network[D].Dalian：Dalian Maritime University，2019

[7] 彭璟云.無線局域網MAC層BEB退避算法研究[D].昆明：昆明理工大學，2018PENG Jingyun.Research on BEB backoff algorithm in MAC layer of WLAN[D].Kunming：Kunming University of Science and Technology，2018

[8] 余小龍.Ad Hoc網絡MAC層協議研究及其算法改進[D].成都：電子科技大學，2017YU Xiaolong.Research on ad hoc network MAC layer protocol and related algorithm improvement[D].Chengdu：University of Electronic Science and Technology of China，2017

[9] 陸毅.無人機集群自組網MAC協議研究[D].桂林：桂林電子科技大學，2020LU Yi.Research on MAC protocol of UAV cluster ad hoc network[D].Guilin：Guilin University of Electronic Technology，2020

[10] Song N O，Kwak B J，Song J，et al.Enhancement of IEEE 802.11 distributed coordination function with exponential increase exponential decrease backoff algorithm[C]//The 57th IEEE Semiannual Vehicular Technology Conference.Jeju，Korea （South）.IEEE，2003：2775-2778

[11] Pang Q X，Liew S C，Lee J Y B，et al.Performance evaluation of an adaptive backoff scheme for WLAN[J].Wireless Communications and Mobile Computing，2004，4（8）：867-879

[12] Chan Y C，Liao M C，Chu C H.A collision-aware backoff mechanism for IEEE 802.11 WLANs[C]//2009 IEEE International Conference on Intelligent Computing and Intelligent Systems.IEEE，2009，3：284-288

[13] Timmins I J，OYoung S.Marine communications channel modeling using the finite-difference time domain method[J].IEEE Transactions on Vehicular Technology，2009，58（6）：2626-2637

[14] 沈亮.面向海上無線通信的信道估計算法研究與實現[D].西安：西安電子科技大學，2018

SHEN Liang.Research and implementation of channel estimation algorithms for maritime wireless communication systems[D].Xian：Xidian University，2018

[15] 魏特，王文浩，陳軍，等.環境信息輔助的海上無線信道測量與建模[J].清華大學學報（自然科學版），2021，61（9）：1002-1007WEI Te，WANG Wenhao，CHEN Jun，et al.Environmental information-aided maritime wireless channel measurement and modelling[J].Journal of Tsinghua University（Science and Technology），2021，61（9）：1002-1007

[16] 戴德君.有關海浪波面高度分布的幾個問題[D].青島：中國海洋大學，2000DAI Dejun.Some problems about the height distribution of sea waves[D].Qingdao：Ocean University of China，2000

[17] Bianchi G.Performance analysis of the IEEE 802.11 distributed coordination function[J].IEEE Journal on Selected Areas in Communications，2000，18（3）：535-547

[18] Bianchi G，Tinnirello I.Remarks on IEEE 802.11 DCF performance analysis[J].IEEE Communications Letters，2005，9（8）：765-767

MAC protocol backoff algorithm based on interception in maritime ad hoc networks

XIAO Feng DOU Zheng

1College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001

Abstract Unmanned Surface Vehicles （USVs） usually operate in coordinated formation and exchange data through wireless ad hoc networks due to mission requirements，and the channel transmission loss of maritime ad hoc networks is usually in a dynamic state owing to the influence of ocean waves.However，the existing backoff algorithm of MAC protocol in ad hoc networks cannot distinguish between packet collision and packet loss in a dynamic maritime environment，resulting in the decline of reliability and stability.Here，we propose an adaptive minimum contention window backoff algorithm based on channel monitoring.The algorithm estimates the channel state by sensing the number of adjacent contention nodes，reduces the channel collision probability and retransmission times，thus improves the reliability and stability of the network as a whole.Simulation results show that compared with classical BEB algorithm，the proposed backoff algorithm increases the throughput and fairness by 28.67% and 62.00%，respectively，and reduces the end-to-end delay and packet loss rate by 2.84% and 15.10%，respectively.

Key words backoff algorithm;maritime communication;ad hoc network;channel monitoring;adaptive;minimum competition window