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

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

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)地修改競(jìng)爭(zhēng)窗口，減少碰撞概率與重發(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)競(jìng)爭(zhēng)窗口，從而有效地提高信道利用率，相對(duì)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)槊芏鹊投?jìng)爭(zhēng)信道的沖突少，數(shù)據(jù)發(fā)送成功率高，而DPSC算法卻因節(jié)點(diǎn)估算預(yù)測(cè)的周期偵聽(tīng)耗能略高。但高密度時(shí)DPSC算法因?yàn)楦鶕?jù)節(jié)點(diǎn)數(shù)目動(dòng)態(tài)地改變競(jìng)爭(zhēng)窗口而降低沖突概率，減少重傳次數(shù)，所以平均能耗明顯低于其他三種算法，相對(duì)于PTTL算法平均下降5%。

    本文退避算法DPSC通過(guò)二項(xiàng)分布概率模式對(duì)鄰近節(jié)點(diǎn)數(shù)目進(jìn)行最大似然估算并進(jìn)行加權(quán)遞推平滑預(yù)測(cè)，精準(zhǔn)地估算出鄰近節(jié)點(diǎn)數(shù)目，實(shí)現(xiàn)競(jìng)爭(zhēng)窗口自適應(yīng)節(jié)點(diǎn)密度的目的；根據(jù)服務(wù)分級(jí)思想，引入服務(wù)分級(jí)因子δ實(shí)現(xiàn)服務(wù)級(jí)別高的數(shù)據(jù)能優(yōu)先發(fā)送；引入負(fù)載分級(jí)因子κ表示負(fù)載級(jí)別并賦予數(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)一步的工作將采用無(wú)線傳感器硬件平臺(tái)CC2430對(duì)DPSC退避算法進(jìn)行實(shí)際性能測(cè)試。
參考文獻(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)先及流量分級(jí)的無(wú)線傳感器網(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.