《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 一種密度預(yù)測與服務(wù)分級的MAC退避算法
一種密度預(yù)測與服務(wù)分級的MAC退避算法
來源：電子技術(shù)應(yīng)用2013年第10期
蘇海武, 程良倫, 高 銳, 蘇新凌, 孫志敬
廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院， 廣東 廣州 510006
摘要： 為了提高重負(fù)載的中高速無線傳感器網(wǎng)絡(luò)性能，深入研究競爭型MAC協(xié)議的退避算法，基于PTTL退避算法提出一種密度預(yù)測及服務(wù)分級的MAC退避算法。該算法對網(wǎng)絡(luò)鄰近節(jié)點(diǎn)數(shù)目進(jìn)行加權(quán)遞推平滑預(yù)測，實(shí)現(xiàn)競爭窗口自適應(yīng)節(jié)點(diǎn)密度的目的；引入服務(wù)分級意識，賦予服務(wù)級別高或數(shù)據(jù)積壓或跳數(shù)多的節(jié)點(diǎn)優(yōu)先發(fā)送權(quán),滿足關(guān)鍵數(shù)據(jù)多跳傳輸實(shí)時(shí)性要求。NS2仿真結(jié)果表明：本DPSC退避算法在節(jié)點(diǎn)高密度與高負(fù)載環(huán)境下網(wǎng)絡(luò)性能優(yōu)于其他三種算法，其平均時(shí)延比PTTL算法降低10%，吞吐量提高15%，平均能耗下降5%。
中圖分類號: TP393
文獻(xiàn)標(biāo)識碼: A
文章編號： 0258-7998(2013)10-0112-04
A backoff algorithm of MAC protocol with density prediction and service classification
Su Haiwu, Cheng Lianglun, Gao Rui, Su Xinling, Sun Zhijing
Faculty of Automation，Guangdong University of Technology，Guangzhou 510006, China
Abstract： In order to improve the performance in high-speed sensor networks which traffic load is high, study backoff algorithm of competitive MAC protocol, and propose a backoff algorithm of MAC protocol with density prediction and service classification which is based on PTTL. The protocol forecasts the number of neighboring nodes by weighted recursive smoothing, to achieve the purpose of the competition window adaptive node density; introducing awareness of the service classification, and giving the right of send priority to the nodes that are the high level of service, or data backlog or multi-hop, to meet the real-time requirements of critical data multi-hop transmission. The NS2 simulation results show that: the network performance of DPSC backoff algorithm in the nodes of high-density and high-load environment is superior to the other three algorithms. The average delay was 10% lower than the PTTL algorithm, throughput increased by 15%, and the average energy consumption decreased by 5%.
Key words : high-speed sensor networks; backoff algorithm; density prediction; service classification; priority send

    中高速無線傳感器網(wǎng)絡(luò)[1]用于包括環(huán)境檢測、視頻多媒體等多種混合類型業(yè)務(wù)，網(wǎng)絡(luò)負(fù)載通常很大，區(qū)域節(jié)點(diǎn)密度差異大，區(qū)域負(fù)載波動(dòng)大。傳統(tǒng)無線傳感器網(wǎng)絡(luò)的MAC協(xié)議競爭窗口滑動(dòng)緩慢，對于負(fù)載波動(dòng)大的業(yè)務(wù)會(huì)造成過渡時(shí)間長以及資源浪費(fèi)等，不能滿足數(shù)據(jù)復(fù)雜的中高速無線傳感器網(wǎng)絡(luò)[2]。目前出現(xiàn)了針對無線傳感器網(wǎng)絡(luò)MAC協(xié)議的多種有效的退避算法,典型退避算法有： (1)二進(jìn)制指數(shù)退避算法BEB(Binary Exponential Backoff)[3] ,其特點(diǎn)是發(fā)生沖突時(shí)競爭窗口按二進(jìn)制指數(shù)增長，發(fā)送成功時(shí)則降至最小值。其缺點(diǎn)是總是有利于最近發(fā)送成功的節(jié)點(diǎn)而公平性差， 且隨著節(jié)點(diǎn)數(shù)增加而碰撞概率急劇增大， 造成網(wǎng)絡(luò)性能迅速下降。(2)倍數(shù)增加線性遞減退避算法MILD(Multiplicative Increase Linear Decrease)[4]，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較多時(shí)，MILD由于競爭窗口變化較平滑，其吞吐率性能略優(yōu)于BEB。但當(dāng)網(wǎng)絡(luò)有中等數(shù)目的節(jié)點(diǎn)時(shí)，則由于競爭窗口線性遞減而顯得縮小相對較慢，使節(jié)點(diǎn)競爭窗口值往往大于合理值。(3)CIMLD(Conic Increase Multiplicative Linear Decrease)算法[5]采用分段二次曲線計(jì)算倍乘退避因子來調(diào)節(jié)退避窗口，能夠在不同區(qū)域中以不同速率解決信道沖突，但流封鎖信道問題還沒有完全解決。(4)PTTL(Preferentially Transmitting and Different Traffic Levels)退避算法[6]根據(jù)網(wǎng)絡(luò)流量判定的級別來改變退避窗口大小，賦予轉(zhuǎn)發(fā)節(jié)點(diǎn)一定的信道接入優(yōu)勢來提高前傳效率而減少時(shí)延，但對網(wǎng)絡(luò)流量變化適應(yīng)性較弱。

    這些退避算法各具優(yōu)勢，但在負(fù)載波動(dòng)變化急劇、數(shù)據(jù)復(fù)雜的中高速無線傳感器網(wǎng)絡(luò)環(huán)境中，網(wǎng)絡(luò)性能則大幅下降。因此，本文在深入研究PTTL退避算法的基礎(chǔ)上，提出一種密度預(yù)測與服務(wù)分級的MAC退避算法DPSC(Density Prediction and Service Classification)，以達(dá)到提高網(wǎng)絡(luò)信道利用率與網(wǎng)絡(luò)吞吐量的目的。
1 PTTL退避算法介紹與分析
    PTTL退避算法主要思想是：流量分級與轉(zhuǎn)發(fā)優(yōu)先。即節(jié)點(diǎn)通過偵聽信道狀態(tài)來判斷當(dāng)前網(wǎng)絡(luò)流量級別，并對轉(zhuǎn)發(fā)節(jié)點(diǎn)賦予較小競爭窗口而增大其信道接入概率。PTTL退避算法描述如下：
    (1)空閑狀態(tài)，CW=max(CWmin,CW-i3)，其中i是連續(xù)偵聽到空閑時(shí)隙數(shù)，CWmin是窗口最小值。
    (2)發(fā)送成功，CW=max(CWmin,CW-s2)，其中s是連續(xù)成功競爭信道并發(fā)送報(bào)文成功次數(shù)。
    (3)發(fā)送失敗，競爭窗口CW為：
    CW=min(CWmax,CW*(C+1)),C≤CmaxCW=CWinit, C>Cmax　　
其中C是連續(xù)競爭信道失敗次數(shù)，Cmax是最大退避次數(shù)，CWmax是窗口最大值。
    (4)節(jié)點(diǎn)是轉(zhuǎn)發(fā)節(jié)點(diǎn)，則CW=CWmin。
    總的來說，PTTL退避算法簡便易行，在網(wǎng)絡(luò)負(fù)載較重的網(wǎng)絡(luò)環(huán)境中性能良好。但PTTL退避算法并沒有服務(wù)分級，即不同業(yè)務(wù)類型數(shù)據(jù)以相同的機(jī)會(huì)接入信道，造成關(guān)鍵數(shù)據(jù)延遲，不能反映實(shí)際需求。且節(jié)點(diǎn)是轉(zhuǎn)發(fā)節(jié)點(diǎn)，則CW將無條件降低到CWmin，雖然這樣能夠在一定程度上提高轉(zhuǎn)發(fā)能力并保證數(shù)據(jù)轉(zhuǎn)發(fā)優(yōu)先，但是當(dāng)網(wǎng)絡(luò)負(fù)載嚴(yán)重時(shí)，不區(qū)分服務(wù)類型的無條件降至最小值CWmin，會(huì)造成碰撞概率急劇增加，反而與盡快將數(shù)據(jù)發(fā)送出去的初衷相反。因此關(guān)鍵類型數(shù)據(jù)應(yīng)該具有接入信道優(yōu)先權(quán)，提高優(yōu)先級數(shù)據(jù)的傳輸率，減少關(guān)鍵類型數(shù)據(jù)時(shí)延來滿足應(yīng)用實(shí)時(shí)性需求。
2 DPSC退避算法設(shè)計(jì)
    為了提高網(wǎng)絡(luò)負(fù)載重且負(fù)載波動(dòng)急劇的中高速無線傳感器網(wǎng)絡(luò)性能，基于PTTL退避算法提出密度預(yù)測與服務(wù)分級MAC退避算法DPSC。主要?jiǎng)?chuàng)新點(diǎn)如下：
    (1)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目進(jìn)行加權(quán)遞推平滑預(yù)測。節(jié)點(diǎn)密度與鄰近節(jié)點(diǎn)數(shù)目是一一映射關(guān)系，即某節(jié)點(diǎn)的鄰近節(jié)點(diǎn)越多，此節(jié)點(diǎn)區(qū)域的節(jié)點(diǎn)密度越大。假設(shè)網(wǎng)絡(luò)自適應(yīng)占空比p∈[0,1],即節(jié)點(diǎn)每周期處于活動(dòng)狀態(tài)概率為p。在每個(gè)估算周期i∈[1,n],利用競爭窗口來實(shí)現(xiàn)計(jì)算鄰近節(jié)點(diǎn)，且計(jì)算節(jié)點(diǎn)數(shù)是指除開周期1~i-1中已計(jì)算的所有醒來鄰近節(jié)點(diǎn)。在估算周期i中，詢問節(jié)點(diǎn)發(fā)送詢問包REQ。接收到詢問包REQ且未有回答的醒來節(jié)點(diǎn)時(shí),在M個(gè)時(shí)隙中隨機(jī)選擇一個(gè)時(shí)隙回復(fù)一個(gè)裝載唯一身份ID的回復(fù)包ANS。詢問節(jié)點(diǎn)在第i窗口成功收集分組Gi數(shù)目并記錄ID。由伯利努試驗(yàn)二項(xiàng)分布可知占空比為p、實(shí)際鄰近節(jié)點(diǎn)數(shù)目為N且發(fā)生k次的概率為:

  
3.1節(jié)點(diǎn)密度預(yù)測分析
    鄰近節(jié)點(diǎn)數(shù)目的最大似然估算值N*與節(jié)點(diǎn)占空比p有關(guān)，占空比p的大小決定N*的估算精確度。當(dāng)前網(wǎng)絡(luò)鄰居節(jié)點(diǎn)數(shù)Nc與平滑因子l、權(quán)重系數(shù)Cj相關(guān)，此處取l=5，C1=0.2，C2=0.4，C3=0.6，C4=0.8，C=1.0。其中相對誤差e=|Nc-N|/N，Nc是當(dāng)前鄰近節(jié)點(diǎn)數(shù)目加權(quán)遞推平滑預(yù)測值，N是當(dāng)前鄰近節(jié)點(diǎn)數(shù)目真實(shí)值。
    從圖2可知，鄰近節(jié)點(diǎn)數(shù)目越多，占空比p越大，則當(dāng)前鄰近節(jié)點(diǎn)數(shù)目加權(quán)遞推平滑預(yù)測值與真實(shí)值相對誤差e越小，即平滑預(yù)測值越接近真實(shí)值，估算精確度越高。同理，對于節(jié)點(diǎn)密度大的區(qū)域節(jié)點(diǎn)可以設(shè)置較低的占空比p進(jìn)行估算而得到可靠的鄰近節(jié)點(diǎn)數(shù)目估算值，且減少估算周期偵聽所消耗的能量。

3.2 系統(tǒng)時(shí)延分析
    從圖3可知，節(jié)點(diǎn)數(shù)目較少時(shí)各算法端到端時(shí)延基本相同，但節(jié)點(diǎn)數(shù)目較多時(shí)的時(shí)延相差甚遠(yuǎn)。DPSC算法時(shí)延增加速率最小，因?yàn)槟軌蚋鶕?jù)鄰近節(jié)目數(shù)目動(dòng)態(tài)地修改競爭窗口，減少碰撞概率與重發(fā)次數(shù)，從而減少端到端時(shí)延，能夠適應(yīng)不同節(jié)點(diǎn)數(shù)目的網(wǎng)絡(luò)環(huán)境。
3.3 系統(tǒng)吞吐量分析
    從圖4可知，隨著節(jié)點(diǎn)密度增大吞吐量都有所下降，在節(jié)點(diǎn)數(shù)目小于10時(shí)吞吐量大致相同，之后出現(xiàn)大幅度差距。因?yàn)殡S著節(jié)點(diǎn)數(shù)目的增加,節(jié)點(diǎn)沖突概率將會(huì)增大，所以各種算法吞吐量都有所下降。其中DPSC算法下降速度最慢是由于鄰近節(jié)點(diǎn)數(shù)目能自適應(yīng)競爭窗口，從而有效地提高信道利用率，相對PTTL算法平均提高15%。其余三種算法都不太適應(yīng)于高節(jié)點(diǎn)密度的網(wǎng)絡(luò)環(huán)境，特別是BEB算法吞吐量下降最快。

3.4系統(tǒng)能耗分析
    從圖5可知，各退避算法成功發(fā)送每比特?cái)?shù)據(jù)的平均能耗隨著系統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目的增加而增加。在鄰近節(jié)點(diǎn)少的網(wǎng)絡(luò)系統(tǒng)中，其他三種算法能耗低于DPSC算法，因?yàn)槊芏鹊投偁幮诺赖臎_突少，數(shù)據(jù)發(fā)送成功率高，而DPSC算法卻因節(jié)點(diǎn)估算預(yù)測的周期偵聽耗能略高。但高密度時(shí)DPSC算法因?yàn)楦鶕?jù)節(jié)點(diǎn)數(shù)目動(dòng)態(tài)地改變競爭窗口而降低沖突概率，減少重傳次數(shù)，所以平均能耗明顯低于其他三種算法，相對于PTTL算法平均下降5%。

    本文退避算法DPSC通過二項(xiàng)分布概率模式對鄰近節(jié)點(diǎn)數(shù)目進(jìn)行最大似然估算并進(jìn)行加權(quán)遞推平滑預(yù)測，精準(zhǔn)地估算出鄰近節(jié)點(diǎn)數(shù)目，實(shí)現(xiàn)競爭窗口自適應(yīng)節(jié)點(diǎn)密度的目的；根據(jù)服務(wù)分級思想，引入服務(wù)分級因子δ實(shí)現(xiàn)服務(wù)級別高的數(shù)據(jù)能優(yōu)先發(fā)送；引入負(fù)載分級因子κ表示負(fù)載級別并賦予數(shù)據(jù)積壓的節(jié)點(diǎn)優(yōu)先發(fā)送權(quán)；引入多跳傳發(fā)優(yōu)先因子μ實(shí)現(xiàn)數(shù)據(jù)前傳的連續(xù)性與減少時(shí)延，滿足關(guān)鍵數(shù)據(jù)多跳傳輸實(shí)時(shí)性要求。DPSC退避算法與其他三種算法在節(jié)點(diǎn)低密度與低負(fù)載情況下網(wǎng)絡(luò)性能差別不大，但在節(jié)點(diǎn)高密度與高負(fù)載情況下則表現(xiàn)出優(yōu)越的網(wǎng)絡(luò)性能。進(jìn)一步的工作將采用無線傳感器硬件平臺CC2430對DPSC退避算法進(jìn)行實(shí)際性能測試。
參考文獻(xiàn)
[1] 王越超，程良倫.中高速傳感器網(wǎng)絡(luò)中基于服務(wù)區(qū)分的QoS路由算法研究[J].計(jì)算機(jī)應(yīng)用與軟件,2010(8):152-158.
[2] CHIA W C, CHEW L W, ANG L M, et al. Low memory image stitching and compression for WMSN using stripbased processing[J]. International journal of sensor network, 2012,11(1):22-32.
[3] PANTAZI A,ANTONAKOPOULOS T. Equilibrium point analysis of the binary exponential backoff algorithm[J].Computer Communications, 2001,24(18):1759-1768.
[4] Zhang Yi, PIUNOVSKIY A, AYESTA U,et al. Convergence of trajectories and optimal buffer sizing for MIMD congestion control[J]. Computer Communications, 2010,33(2):149-159.
[5] 奎曉燕，杜華坤. CIMLD:多跳Ad Hoc網(wǎng)絡(luò)中一種自適應(yīng)的MAC退避算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2009，30(4):679-682.
[6] 余慶春，譚獅. 一種基于轉(zhuǎn)發(fā)優(yōu)先及流量分級的無線傳感器網(wǎng)絡(luò)退避算法[J]. 計(jì)算機(jī)應(yīng)用研究，2012,29(5):1846-1849.
[7] CAMILLO A,NATI M, PETRIOLI C,et al. IRIS:Integrated data gathering and interest dissemination system for wireless sensor networks [J]. Ad Hoc Networks, 2011, 11(2):654-671.

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。