移動自組網(wǎng)媒體接入控制協(xié)議自私行為優(yōu)化算法設計

高士娟 王喜軍 朱清超

摘 要：針對移動自組網(wǎng)媒體接入控制協(xié)議的自私行為處理機制中存在的靜態(tài)性、不公平性和復雜性等問題，提出一種自私行為優(yōu)化處理算法。首先，結(jié)合最優(yōu)化理論和反饋原理，利用歷史樣本推導最優(yōu)接入概率，實現(xiàn)參數(shù)的實時動態(tài)變化，改善靜態(tài)性;然后，設置所有節(jié)點特定時刻均采用最優(yōu)接入概率，改善網(wǎng)絡公平索引系數(shù);最后，采用線性迭代機制，避免算法復雜度的增加。在此基礎上，利用李雅普諾夫算法和全局穩(wěn)態(tài)點，理論上證明了所提算法的穩(wěn)定性和有效性。實驗結(jié)果表明，相比優(yōu)化前，所提算法自私節(jié)點數(shù)、時延分別降低了30%～50%、8～10ms，吞吐量、公平索引值分別提高了0.5Mb/s、0.05，控制開銷基本保持不變，自私行為處理機制的性能得到改善。

關鍵詞：自私行為;移動自組網(wǎng);媒體接入控制協(xié)議;穩(wěn)態(tài);李雅普諾夫算法

中圖分類號： TP393.04

文獻標志碼：A

Abstract： To address the problems like static nature， unfairness and complexity in Selfish Misbehavior （SM） processing mechanism of Medium Access Control （MAC） protocol of Mobile Ad Hoc NETwork （MANET）， an optimization algorithm for SM was proposed. By using optimization theory and feedback theory， the Optimal Access Probability （OAP） was conducted through the utilization of historical samples， realizing the dynamic change of parameters to improve static nature. Then， all nodes in the network were set to use the OAP at the given period， thus the fairness index of the network was promoted. Finally， linear iteration mechanism was adopted to avoid the increase of complexity. On basis of the above， stability and effectiveness of the proposed algorithm were proved theoretically by Lyapunov algorithm and global stable point. Experimental results show that， by the proposed algorithm， the number of SM decreases by 30%-50%， the end-to-end delay brings down 8-10ms， the throughput increases about 0.5Mb/s， the fairness index raises by 0.05， while the control overhead remains unchanged， all of which indicates that the performance of the SM processing mechanism has been improved.

Key words： selfish misbehavior; Mobile Ad Hoc NETwork （MANET）; Medium Access Control （MAC） protocol; stability state; Lyapunov algorithm

0 引言

移動自組網(wǎng)（Mobile Ad Hoc NETwork， MANET）以高度的自組織性、魯棒性和抗毀性，成為地震、極地考察等惡劣環(huán)境的首選通信方式之一。但MANET缺乏基礎設施等管理節(jié)點，若終端/節(jié)點修改信道參數(shù)、丟棄分組或切換休眠模式[1-2]，優(yōu)先接入信道，則違背了公平性原則，自私行為（Selfish Misbehavior， SM）產(chǎn)生。媒體接入控制（Media Access Control， MAC）協(xié)議中SM的影響尤為顯著，因為MAC協(xié)議控制分布式幀間隔、短時幀間隔、競爭窗口（Contention Window， CW）等參數(shù)，直接與信道交互，SM勢必降低鄰節(jié)點的接入概率，導致節(jié)點資源閑置，網(wǎng)絡吞吐量降低;且網(wǎng)絡層、傳輸層、應用層等上層協(xié)議依賴MAC協(xié)議性能，因而后者影響范圍更廣，因此MAC協(xié)議中SM行為的研究備受關注。

目前MANET中MAC協(xié)議集中于分布式SM檢測和處理算法的研究，后者起步較晚，研究相對較少。就檢測算法而言，文獻[3]指出傳統(tǒng)DOMINO、CUSUM（CUmulative SUM）和SWN-CUSUM（Sliding Window Non-parameter CUSUM）等算法依賴接入點（Access Point， AP）的檢測功能，與MANET分布式、多跳特點不符。文獻[4]指出MANET中SM的研究應包含檢測和反饋機制，并提出一種集數(shù)據(jù)搜集、判決和處理于一體的SM檢測算法，但時延相對較高。文獻[5]指出MAC協(xié)議中基于載波監(jiān)聽多址接入沖突避免（Carrier Sense Multiple Access with Collision Detection， CSMA/CA）模式的分布式協(xié)調(diào)功能（Distributed Coordination Function， DCF）協(xié)議是MANET組網(wǎng)的重要組成部分，雖無法完全消除SM，但可最大限度降低SM對吞吐量的影響;并提出一種自由碰撞策略，改善了DCF協(xié)議的短期公平性，但與MANET分布式不符。就處理算法而言，其概念由Kyasanur等[6]首次提出，思想在于對判定為SM的節(jié)點降低其接入概率，并提出一種分布式協(xié)作處理機制[7]，奠定了SM處理算法的基調(diào);但適用范圍受限。文獻[8]針對SM導致的節(jié)點“餓死”現(xiàn)象，引入help標簽，使得普通節(jié)點多次嘗試請求發(fā)送（Request To Send， RTS）失敗后仍可接入信道，緩解了SM導致的吞吐量降級問題;但控制開銷已不容忽視。文獻[9]在前期研究基礎上，將SM分為丟棄型（Dumb）和智能型（Smart）兩類，并提出通過限定參數(shù)范圍實現(xiàn)分布式處理的思想。在此論文僅針對SM處理算法展開研究。

雖然SM處理機制取得了一定成果，但仍存在以下不足：一是靜態(tài)性問題，即處理算法僅增加SM節(jié)點的接入概率，而鄰節(jié)點自身參數(shù)未作調(diào)整，吞吐量并未得到根本改變，原因在于算法缺乏接入概率的預測功能，造成數(shù)據(jù)資源的浪費;二是公平性問題，即SM處理過程忽略了節(jié)點MAC協(xié)議信道接入的公平性，使得其他SM節(jié)點仍“有機可乘”;三是復雜度問題，即智能型SM處理復雜度較高。

針對上述不足，本文在不增加算法復雜度的基礎上，以改善靜態(tài)性和公平性為目標，將接入概率τ作為研究參數(shù)，針對DCF協(xié)議智能型SM，基于統(tǒng)計思想和最優(yōu)化理論，兼顧節(jié)點公平性，提出了一種本地參數(shù)可實時更改的SM優(yōu)化處理算法。該算法本質(zhì)為節(jié)點均以最優(yōu)接入概率接入信道時，可實現(xiàn)SM處理機制的優(yōu)化，并限制SM性能的提升。在此基礎上，基于李雅普諾夫理論證明了算法的穩(wěn)定性和有效性，并仿真驗證了優(yōu)化算法的公平性、吞吐量等性能。

1 SM優(yōu)化算法設計

本章基于最優(yōu)化理論提出一種SM優(yōu)化處理算法，使其兼顧兩個目標：一是執(zhí)行算法的節(jié)點τ收斂到最優(yōu)值τopt，即最優(yōu)化指標;二是SM節(jié)點吞吐量不高于普通節(jié)點，即公平性指標;三是為避免算法復雜度較高，應以多項式為主，盡量減少指數(shù)或?qū)?shù)形式。令連續(xù)兩個控制分組間隔時間為一步，算法原理為：當檢測到殘余SM時，鄰節(jié)點在下一步起始位置增加自身τi，阻止SM獲得更高接入概率和吞吐量。

不難看出，算法設計的關鍵在于如何保證普通節(jié)點τi收斂到τopt，且避免吞吐量失衡。為解決該問題，將τ離散化，于是迭代過程可視為離散時間系統(tǒng)，狀態(tài)空間為τ=[τ1，τ2，…，τn]，τi為節(jié)點i任意時隙內(nèi)分組發(fā)送概率，即：

2 穩(wěn)定性和有效性分析

基于算法設計目標，在此定量分析算法穩(wěn)定性和有效性，穩(wěn)定性確保節(jié)點收斂到最優(yōu)值，有效性衡量SM的抑制能力。

2.1 穩(wěn)定性分析

理論條件下，當所有節(jié)點均采用該算法時，網(wǎng)絡吞吐量趨于最優(yōu)值，即τi=τopt，i成立。

一般而言，任意τe∈[0，1]n，若滿足條件：1）ε>0，δ>0，對于t，‖τ（0）-τe‖<δ ‖τ（t）-τe‖<ε;2）給定τ（0）∈[0，1]n，limt→∞ τ（t）=τe，則稱τe為全局穩(wěn)態(tài)點。兩者可保證系統(tǒng)收斂到τe，與初始狀態(tài)無關，且最優(yōu)值唯一。

根據(jù)式（2）可知，存在需要確定參數(shù)γ取值的問題，且γ值越小，式（2）收斂越慢，反之亦成立。由Ziegler-Nichols法則[11]可知，γ取值為系統(tǒng)即將變?yōu)椴环€(wěn)定狀態(tài)時對應最大值γmax的一半，即γ=γmax/2。由于式（2）中gi（t）函數(shù)與Fi（t）相關，等價于γmax與Fi（t）密切相關。

接下來介紹γmax值的計算。直觀而言，系統(tǒng)經(jīng)過特定算法處理后，剩余SM數(shù)目nr相對較小。為簡化計算，且不失一般性，令nr=1，擴展到nr個節(jié)點時結(jié)論成立。由DCF原理可知，任意節(jié)點i執(zhí)行二進制指數(shù)回退（Binary Exponential Backoff， BEB）算法時，節(jié)點吞吐量與Bianchi公式[12]類似。但接入概率并非一成不變，其值隨SM波動。令τi為任意節(jié)點接入概率，對于N個信道競爭節(jié)點，吞吐量s（τi）表示為：

根據(jù)全局穩(wěn)態(tài)點定義可知，函數(shù)V和γ取值可保證系統(tǒng)趨于穩(wěn)定，且分析過程中假設節(jié)點包含sj相關信息。但由于MANET節(jié)點移動性，其值產(chǎn)生隨機波動，系統(tǒng)以小概率事件偏離理論值。只要干擾受限，其值將趨于理論值，但必須滿足以下條件：1）存在兩類K函數(shù)α1和α2，使得|x|≤c時，α1（|x|）≤V（x）≤α2（|x|）;2）存在K函數(shù)α3，使得|x|≤c時，V（x（t+1）-x（t））≤-α3（|x|）;3）對于系統(tǒng)節(jié)點接入概率τ，存在連續(xù)李亞普諾夫函數(shù);4）系統(tǒng)在干擾條件時為連續(xù)函數(shù)。根據(jù)算法模型，當α1=α2=‖τ-τopt‖∞時條件1）成立;當‖x‖∈[0，τopt/2]，即‖τ-τopt‖≤τopt/2時條件2）成立;函數(shù)V使條件3）成立;對于任意τi和ri，gi（t）使條件4）恒成立。綜上所述，新算法中參數(shù)γ、Fi（t）可使MANET系統(tǒng)趨于穩(wěn)態(tài)，吞吐量收斂到最優(yōu)值。

2.2 有效性分析

如前文所述，當所有節(jié)點采用新算法時，系統(tǒng)將收斂到穩(wěn)態(tài)，即節(jié)點接入概率為τi=τopt，吞吐量為si=sopt。在此定量分析任意節(jié)點不遵守算法時，吞吐量不超過sopt。對采用優(yōu)化處理算法的節(jié)點稱為普通節(jié)點，否則為SM。下面定量證明任意節(jié)點吞吐量不超過sopt。

2.3 復雜度分析

本文算法復雜度包括最優(yōu)接入概率和SM處理兩部分。前者對應復雜度為T1（n）≈O（n*n+n）=O（n2），后者對應復雜度為T2（n）≈O（n3*n）=O（n4），因此該算法對應復雜度為T（n）=T1（n）+T2（n）=O（n4），這與目前SM相關處理算法的復雜度基本相同，該值可用控制開銷/分組數(shù)描述。

3 性能仿真結(jié)果與分析

3.1 參數(shù)設置

假設節(jié)點為手持設備，對應中低速運動場景，速率限定為2m/s，頻率為300Mb/s，分組傳輸速率為11Mb/s。對于MANET而言，網(wǎng)絡層選擇動態(tài)源路由（Dynamic Source Route， DSR）協(xié)議[14]，應用層選擇恒定比特流（Constant Bit Rate， CBR），參數(shù)設置如表1所示。其他參數(shù)與IEEE文檔規(guī)范[15]保持一致，并利用軟件NS-2[16]對協(xié)議各項性能指標進行仿真。

3.2 性能指標

為了衡量改進算法的性能，分別對吞吐量、端到端時延、公平性指數(shù)和控制開銷等指標進行分析（使用awk工具分析），所有數(shù)據(jù)由NS-2中的trace文件獲得。

吞吐量是指單位時間內(nèi)成功傳輸?shù)谋忍財?shù)，端到端時延是指分組從源節(jié)點到目的節(jié)點成功傳輸所經(jīng)歷的時間（忽略傳播時延和排隊時延），兩者可衡量優(yōu)化算法改進的程度。前者由式（9）計算，值越大越好，后者由trace文件統(tǒng)計平均獲得，值越小越好。

4 結(jié)語

本文基于所有節(jié)點采用最優(yōu)接入概率的思想，緩解了SM處理機制存在的靜態(tài)性和公平性問題，理論和仿真驗證了算法的穩(wěn)定性、有效性和優(yōu)越性。但是仍存在以下幾個問題亟待解決：一是能耗問題，所提算法以計算資源、存儲資源換取性能優(yōu)化，不難理解其能耗必然增加，如何實現(xiàn)性能與能耗的均衡是必須考慮的問題;二是多點協(xié)同處理問題，該算法設計過程中未考慮節(jié)點之間的互操作，如何實現(xiàn)節(jié)點之間的協(xié)同處理是算法改進設計的難題;三是所提算法在維持算法復雜度的基礎上實現(xiàn)了公平性、吞吐量等性能的改善，但復雜度方面仍存在一定的改進空間，后期將繼續(xù)針對上述問題展開研究。

參考文獻 （References）

[1] 朱清超，陳靖，龔水清，等.移動自組網(wǎng)媒體接入控制協(xié)議吞吐量與公平性均衡設計[J].計算機應用，2015，35（11）：3275-3279，3311.（ZHU Q C， CHEN J， GONG S Q， et al. Design of medium access control protocol tradeoff between throughput and fairness in MANET [J]. Journal of Computer Applications， 2015， 35（11）： 3275-3279， 3311.）

[2] 朱清超，陳靖，龔水清，等.移動自組網(wǎng)自私行為閉環(huán)懲罰模型設計[J].計算機應用研究，2016，33（8）：2446-2450.（ZHU Q C， CHEN J， GONG S Q， et al. Design of closed-loop model on selfish behavior in MANET [J]. Application Research of Computers， 2016， 33（8）： 2446-2450.）

[3] GUANG L， ASSI C， BENSLIMANE A. MAC layer misbehavior in wireless networks： challenges and solutions [J]. IEEE Wireless Communications， 2008， 15（4）： 6-14.

[4] TARANNUM R， PANDEY Y. Detection and deletion of selfish MANET nodes a distributed approach [C]// Proceedings of the 2012 1st International Conference on Recent Advances in Information Technology. Piscataway， NJ： IEEE， 2012： 152-156.

[5] SANABRIA-RUSSO L， BARCELO J， BELLALTA B， et al. A high efficiency MAC protocol for WLANs： providing fairness in dense scenarios [J]. IEEE/ACM Transactions on Networking， 2017， 25（1）： 492-505.

[6] KYASANUR P， VAIDYA N H. Selfish MAC layer misbehavior in wireless networks [J]. IEEE Transactions on Mobile Computing， 2005， 5（4）： 502-516.

[7] KYASANUR P， VAIDYA N H. Detection and handling of MAC layer misbehavior in wireless networks [C]// Proceedings of 2003 International Conference on Dependable Systems and Networks. Piscataway， NJ： IEEE， 2003： 1-10.

[8] HUANG C， LEA C-T， WONG A K-S. Fairness enhancement for 802.11 MAC [C]// Proceedings of the 2010 International Conference on Access Networks， LNICST 37. Berlin： Springer， 2010： 25-39.

[9] LI M， SALINAS S， LI P， et al. MAC-layer selfish misbehavior in IEEE 802.11 Ad Hoc networks： detection and defense [J]. IEEE Transactions on Mobile Computing， 2015， 14（6）： 1203-1217.

[10] KONORSKI J. A game-theoretic study of CSMA/CA under a backoff attack [J]. IEEE/ACM Transactions on Networking， 2006， 14（6）： 1167-1178.

[11] FRANKLIN G F， POWELL J D ， WORKMAN M L. Digital Control of Dynamic Systems [M]. Reading， MA： Addison-Wesley， 1990： 192-196.

[12] 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.

[13] KALIL H K. Nonlinear Systems [M]. 3rd ed. New York： Macmillan， 2002： 174-180.

[14] MISTRY H P， MISTRY N H. A survey use of ACO on AODV & DSR routing protocols in MANET [C]// Proceedings of the 2015 International Conference on Innovations in Information Embedded and Communication System. Piscataway， NJ： IEEE， 2015： 1-6.

[15] EASTLAKE 3rd D E， ABLEY J. IANA considerations and IETF protocol and documentation usage for IEEE 802 parameters： RFC7042 [EB/OL]. [2018-09-26]. https：//tools.ietf.org/pdf/rfc7042.pdf.

[16] CHUNG J， CLAYPOOL M. NS by example [EB/OL].[2018-09-26]. http：//nile.wpi.edu/NS/.

[17] JAIN R K， CHIU D-M W， HAVE W R. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems： DEC-TR-301 [R]. Hudson， MA： Eastern Research Laboratory， 1984.