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

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

2、低了30%50%、810ms，吞吐量、公平索引值分別提高了0.5mb/s、0.05，控制開銷基本保持不變，自私行為處理機(jī)制的性能得到改善。關(guān)鍵詞：自私行為;移動(dòng)自組網(wǎng);媒體接入控制協(xié)議;穩(wěn)態(tài);李雅普諾夫算法中圖分類號(hào)： tp393.04文獻(xiàn)標(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 引言移動(dòng)自組網(wǎng)（mobile ad hoc network， manet）以高度的自組織性、魯棒性和抗毀性

7、，成為地震、極地考察等惡劣環(huán)境的首選通信方式之一。但manet缺乏基礎(chǔ)設(shè)施等管理節(jié)點(diǎn)，若終端/節(jié)點(diǎn)修改信道參數(shù)、丟棄分組或切換休眠模式1-2，優(yōu)先接入信道，則違背了公平性原則，自私行為（selfish misbehavior， sm）產(chǎn)生。媒體接入控制（media access control， mac）協(xié)議中sm的影響尤為顯著，因?yàn)閙ac協(xié)議控制分布式幀間隔、短時(shí)幀間隔、競爭窗口（contention window， cw）等參數(shù)，直接與信道交互，sm勢必降低鄰節(jié)點(diǎn)的接入概率，導(dǎo)致節(jié)點(diǎn)資源閑置，網(wǎng)絡(luò)吞吐量降低;且網(wǎng)絡(luò)層、傳輸層、應(yīng)用層等上層協(xié)議依賴mac協(xié)議性能，因而后者影響范圍更廣，因此m

8、ac協(xié)議中sm行為的研究備受關(guān)注。目前manet中mac協(xié)議集中于分布式sm檢測和處理算法的研究，后者起步較晚，研究相對(duì)較少。就檢測算法而言，文獻(xiàn)3指出傳統(tǒng)domino、cusum（cumulative sum）和swn-cusum（sliding window non-parameter cusum）等算法依賴接入點(diǎn)（access point， ap）的檢測功能，與manet分布式、多跳特點(diǎn)不符。文獻(xiàn)4指出manet中sm的研究應(yīng)包含檢測和反饋機(jī)制，并提出一種集數(shù)據(jù)搜集、判決和處理于一體的sm檢測算法，但時(shí)延相對(duì)較高。文獻(xiàn)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對(duì)吞吐量的影響;并提出一種自由碰撞策略，改善了dcf協(xié)議的短期公平性，但與manet分布式不符。就處理算法而言，其概念由kyasanur等6首次提出，思想在于對(duì)判定為sm的節(jié)點(diǎn)降低其接入概率，并提出一種分布式協(xié)作處理機(jī)制7，奠定了sm處理算法的基調(diào);但適用范圍受限。文獻(xiàn)8針對(duì)sm導(dǎo)致的節(jié)點(diǎn)“餓死”現(xiàn)象，引入help標(biāo)

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

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

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

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

14、原理可知，任意節(jié)點(diǎn)i執(zhí)行二進(jìn)制指數(shù)回退（binary exponential backoff， beb）算法時(shí)，節(jié)點(diǎn)吞吐量與bianchi公式12類似。但接入概率并非一成不變，其值隨sm波動(dòng)。令i為任意節(jié)點(diǎn)接入概率，對(duì)于n個(gè)信道競爭節(jié)點(diǎn)，吞吐量s（i）表示為：根據(jù)全局穩(wěn)態(tài)點(diǎn)定義可知，函數(shù)v和取值可保證系統(tǒng)趨于穩(wěn)定，且分析過程中假設(shè)節(jié)點(diǎn)包含sj相關(guān)信息。但由于manet節(jié)點(diǎn)移動(dòng)性，其值產(chǎn)生隨機(jī)波動(dòng)，系統(tǒng)以小概率事件偏離理論值。只要干擾受限，其值將趨于理論值，但必須滿足以下條件：1）存在兩類k函數(shù)1和2，使得|x|c時(shí)，1（|x|）v（x）2（|x|）;2）存在k函數(shù)3，使得|x|c時(shí)，v（x（t

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

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

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

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

19、接入控制協(xié)議吞吐量與公平性均衡設(shè)計(jì)j.計(jì)算機(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 朱清超，陳靖，龔水清，等.移動(dòng)自組網(wǎng)自私行為閉環(huán)懲罰模型設(shè)計(jì)j.計(jì)算機(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