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

1、    移動自組網(wǎng)媒體接入控制協(xié)議自私行為優(yōu)化算法設(shè)計    高士娟 王喜軍 朱清超摘 要：針對移動自組網(wǎng)媒體接入控制協(xié)議的自私行為處理機制中存在的靜態(tài)性、不公平性和復(fù)雜性等問題，提出一種自私行為優(yōu)化處理算法。首先，結(jié)合最優(yōu)化理論和反饋原理，利用歷史樣本推導(dǎo)最優(yōu)接入概率，實現(xiàn)參數(shù)的實時動態(tài)變化，改善靜態(tài)性;然后，設(shè)置所有節(jié)點特定時刻均采用最優(yōu)接入概率，改善網(wǎng)絡(luò)公平索引系數(shù);最后，采用線性迭代機制，避免算法復(fù)雜度的增加。在此基礎(chǔ)上，利用李雅普諾夫算法和全局穩(wěn)態(tài)點，理論上證明了所提算法的穩(wěn)定性和有效性。實驗結(jié)果表明，相比優(yōu)化前，所提算法自私節(jié)點數(shù)、時延分別降

2、低了30%50%、810ms，吞吐量、公平索引值分別提高了0.5mb/s、0.05，控制開銷基本保持不變，自私行為處理機制的性能得到改善。關(guān)鍵詞：自私行為;移動自組網(wǎng);媒體接入控制協(xié)議;穩(wěn)態(tài);李雅普諾夫算法中圖分類號： tp393.04文獻標(biāo)志碼：aabstract： to address the problems like static nature， unfairness and complexity in selfish misbehavior （sm） processing mechanism of medium access control （mac） protocol of mob

3、ile 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， al

4、l 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 theor

5、etically 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 rem

6、ains 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 algorithm0 引言移動自組網(wǎng)（mobile ad hoc network， manet）以高度的自組織性、魯棒性和抗毀性

7、，成為地震、極地考察等惡劣環(huán)境的首選通信方式之一。但manet缺乏基礎(chǔ)設(shè)施等管理節(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é)點的接入概率，導(dǎo)致節(jié)點資源閑置，網(wǎng)絡(luò)吞吐量降低;且網(wǎng)絡(luò)層、傳輸層、應(yīng)用層等上層協(xié)議依賴mac協(xié)議性能，因而后者影響范圍更廣，因此m

8、ac協(xié)議中sm行為的研究備受關(guān)注。目前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的研究應(yīng)包含檢測和反饋機制，并提出一種集數(shù)據(jù)搜集、判決和處理于一體的sm檢測算法，但時延相對較高。文獻5指出mac協(xié)議中基于載波監(jiān)聽多址接入沖突避免（carrier sen

9、se 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導(dǎo)致的節(jié)點“餓死”現(xiàn)象，引入help標(biāo)

10、簽，使得普通節(jié)點多次嘗試請求發(fā)送（request to send， rts）失敗后仍可接入信道，緩解了sm導(dǎo)致的吞吐量降級問題;但控制開銷已不容忽視。文獻9在前期研究基礎(chǔ)上，將sm分為丟棄型（dumb）和智能型（smart）兩類，并提出通過限定參數(shù)范圍實現(xiàn)分布式處理的思想。在此論文僅針對sm處理算法展開研究。雖然sm處理機制取得了一定成果，但仍存在以下不足：一是靜態(tài)性問題，即處理算法僅增加sm節(jié)點的接入概率，而鄰節(jié)點自身參數(shù)未作調(diào)整，吞吐量并未得到根本改變，原因在于算法缺乏接入概率的預(yù)測功能，造成數(shù)據(jù)資源的浪費;二是公平性問題，即sm處理過程忽略了節(jié)點mac協(xié)議信道接入的公平性，使得其他sm節(jié)

11、點仍“有機可乘”;三是復(fù)雜度問題，即智能型sm處理復(fù)雜度較高。針對上述不足，本文在不增加算法復(fù)雜度的基礎(chǔ)上，以改善靜態(tài)性和公平性為目標(biāo)，將接入概率作為研究參數(shù)，針對dcf協(xié)議智能型sm，基于統(tǒng)計思想和最優(yōu)化理論，兼顧節(jié)點公平性，提出了一種本地參數(shù)可實時更改的sm優(yōu)化處理算法。該算法本質(zhì)為節(jié)點均以最優(yōu)接入概率接入信道時，可實現(xiàn)sm處理機制的優(yōu)化，并限制sm性能的提升。在此基礎(chǔ)上，基于李雅普諾夫理論證明了算法的穩(wěn)定性和有效性，并仿真驗證了優(yōu)化算法的公平性、吞吐量等性能。1 sm優(yōu)化算法設(shè)計本章基于最優(yōu)化理論提出一種sm優(yōu)化處理算法，使其兼顧兩個目標(biāo)：一是執(zhí)行算法的節(jié)點收斂到最優(yōu)值opt，即最優(yōu)化指

12、標(biāo);二是sm節(jié)點吞吐量不高于普通節(jié)點，即公平性指標(biāo);三是為避免算法復(fù)雜度較高，應(yīng)以多項式為主，盡量減少指數(shù)或?qū)?shù)形式。令連續(xù)兩個控制分組間隔時間為一步，算法原理為：當(dāng)檢測到殘余sm時，鄰節(jié)點在下一步起始位置增加自身i，阻止sm獲得更高接入概率和吞吐量。不難看出，算法設(shè)計的關(guān)鍵在于如何保證普通節(jié)點i收斂到opt，且避免吞吐量失衡。為解決該問題，將離散化，于是迭代過程可視為離散時間系統(tǒng)，狀態(tài)空間為=1，2，n，i為節(jié)點i任意時隙內(nèi)分組發(fā)送概率，即：2 穩(wěn)定性和有效性分析基于算法設(shè)計目標(biāo)，在此定量分析算法穩(wěn)定性和有效性，穩(wěn)定性確保節(jié)點收斂到最優(yōu)值，有效性衡量sm的抑制能力。2.1 穩(wěn)定性分析理論條件

13、下，當(dāng)所有節(jié)點均采用該算法時，網(wǎng)絡(luò)吞吐量趨于最優(yōu)值，即i=opt，i成立。一般而言，任意e0，1n，若滿足條件：1）>0，>0，對于t，（0）-e根據(jù)式（2）可知，存在需要確定參數(shù)取值的問題，且值越小，式（2）收斂越慢，反之亦成立。由ziegler-nichols法則11可知，取值為系統(tǒng)即將變?yōu)椴环€(wěn)定狀態(tài)時對應(yīng)最大值max的一半，即=max/2。由于式（2）中g(shù)i（t）函數(shù)與fi（t）相關(guān)，等價于max與fi（t）密切相關(guān)。接下來介紹max值的計算。直觀而言，系統(tǒng)經(jīng)過特定算法處理后，剩余sm數(shù)目nr相對較小。為簡化計算，且不失一般性，令nr=1，擴展到nr個節(jié)點時結(jié)論成立。由dcf

14、原理可知，任意節(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)定，且分析過程中假設(shè)節(jié)點包含sj相關(guān)信息。但由于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

15、+1）-x（t）-3（|x|）;3）對于系統(tǒng)節(jié)點接入概率，存在連續(xù)李亞普諾夫函數(shù);4）系統(tǒng)在干擾條件時為連續(xù)函數(shù)。根據(jù)算法模型，當(dāng)1=2=-opt時條件1）成立;當(dāng)x0，opt/2，即-optopt/2時條件2）成立;函數(shù)v使條件3）成立;對于任意i和ri，gi（t）使條件4）恒成立。綜上所述，新算法中參數(shù)、fi（t）可使manet系統(tǒng)趨于穩(wěn)態(tài)，吞吐量收斂到最優(yōu)值。2.2 有效性分析如前文所述，當(dāng)所有節(jié)點采用新算法時，系統(tǒng)將收斂到穩(wěn)態(tài)，即節(jié)點接入概率為i=opt，吞吐量為si=sopt。在此定量分析任意節(jié)點不遵守算法時，吞吐量不超過sopt。對采用優(yōu)化處理算法的節(jié)點稱為普通節(jié)點，否則為sm。下

16、面定量證明任意節(jié)點吞吐量不超過sopt。2.3 復(fù)雜度分析本文算法復(fù)雜度包括最優(yōu)接入概率和sm處理兩部分。前者對應(yīng)復(fù)雜度為t1（n）o（n*n+n）=o（n2），后者對應(yīng)復(fù)雜度為t2（n）o（n3*n）=o（n4），因此該算法對應(yīng)復(fù)雜度為t（n）=t1（n）+t2（n）=o（n4），這與目前sm相關(guān)處理算法的復(fù)雜度基本相同，該值可用控制開銷/分組數(shù)描述。3 性能仿真結(jié)果與分析3.1 參數(shù)設(shè)置假設(shè)節(jié)點為手持設(shè)備，對應(yīng)中低速運動場景，速率限定為2m/s，頻率為300mb/s，分組傳輸速率為11mb/s。對于manet而言，網(wǎng)絡(luò)層選擇動態(tài)源路由（dynamic source route， dsr）協(xié)

17、議14，應(yīng)用層選擇恒定比特流（constant bit rate， cbr），參數(shù)設(shè)置如表1所示。其他參數(shù)與ieee文檔規(guī)范15保持一致，并利用軟件ns-216對協(xié)議各項性能指標(biāo)進行仿真。3.2 性能指標(biāo)為了衡量改進算法的性能，分別對吞吐量、端到端時延、公平性指數(shù)和控制開銷等指標(biāo)進行分析（使用awk工具分析），所有數(shù)據(jù)由ns-2中的trace文件獲得。吞吐量是指單位時間內(nèi)成功傳輸?shù)谋忍財?shù)，端到端時延是指分組從源節(jié)點到目的節(jié)點成功傳輸所經(jīng)歷的時間（忽略傳播時延和排隊時延），兩者可衡量優(yōu)化算法改進的程度。前者由式（9）計算，值越大越好，后者由trace文件統(tǒng)計平均獲得，值越小越好。4 結(jié)語本文基于

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

19、接入控制協(xié)議吞吐量與公平性均衡設(shè)計j.計算機應(yīng)用，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)懲罰模型設(shè)計j.計算機應(yīng)用研究，2016，33（8）：2

20、446-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， 20

21、08， 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 h

22、igh 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

23、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 co

24、nference 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

25、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 are