海上自組網(wǎng)中基于偵聽的MAC協(xié)議退避算法

肖峰　竇崢

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

中圖分類號TN929.5

文獻標志碼A

0 引言

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

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

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

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

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

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

1 系統(tǒng)模型

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

2.1 自組網(wǎng)MAC層傳輸過程建模

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

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

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

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

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

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

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

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

參考文獻 References

［1］張瑞杰，彭琳琳，付林罡，等.海上無人船自組網(wǎng)隨機接入仿真研究[J].遙測遙控，2020，41（5）：29-35ZHANG Ruijie，PENG Linlin，F(xiàn)U 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移動節(jié)點模型的海上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] 李瑞景.海上寬帶無線自組網(wǎng)多信道MAC協(xié)議研究[D].大連：大連海事大學，2019LI Ruijing.Study on the multi-channel MAC protocol of maritime broadband wireless ad hoc network[D].Dalian：Dalian Maritime University，2019

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

[7] 彭璟云.無線局域網(wǎng)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網(wǎng)絡MAC層協(xié)議研究及其算法改進[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] 陸毅.無人機集群自組網(wǎng)MAC協(xié)議研究[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] 沈亮.面向海上無線通信的信道估計算法研究與實現(xiàn)[D].西安：西安電子科技大學，2018

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

[15] 魏特，王文浩，陳軍，等.環(huán)境信息輔助的海上無線信道測量與建模[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