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

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

  
3.1節(jié)點密度預(yù)測分析
    鄰近節(jié)點數(shù)目的最大似然估算值N*與節(jié)點占空比p有關(guān)，占空比p的大小決定N*的估算精確度。當(dāng)前網(wǎng)絡(luò)鄰居節(jié)點數(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é)點數(shù)目加權(quán)遞推平滑預(yù)測值，N是當(dāng)前鄰近節(jié)點數(shù)目真實值。
    從圖2可知，鄰近節(jié)點數(shù)目越多，占空比p越大，則當(dāng)前鄰近節(jié)點數(shù)目加權(quán)遞推平滑預(yù)測值與真實值相對誤差e越小，即平滑預(yù)測值越接近真實值，估算精確度越高。同理，對于節(jié)點密度大的區(qū)域節(jié)點可以設(shè)置較低的占空比p進(jìn)行估算而得到可靠的鄰近節(jié)點數(shù)目估算值，且減少估算周期偵聽所消耗的能量。

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

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

    本文退避算法DPSC通過二項分布概率模式對鄰近節(jié)點數(shù)目進(jìn)行最大似然估算并進(jìn)行加權(quán)遞推平滑預(yù)測，精準(zhǔn)地估算出鄰近節(jié)點數(shù)目，實現(xiàn)競爭窗口自適應(yīng)節(jié)點密度的目的；根據(jù)服務(wù)分級思想，引入服務(wù)分級因子δ實現(xiàn)服務(wù)級別高的數(shù)據(jù)能優(yōu)先發(fā)送；引入負(fù)載分級因子κ表示負(fù)載級別并賦予數(shù)據(jù)積壓的節(jié)點優(yōu)先發(fā)送權(quán)；引入多跳傳發(fā)優(yōu)先因子μ實現(xiàn)數(shù)據(jù)前傳的連續(xù)性與減少時延，滿足關(guān)鍵數(shù)據(jù)多跳傳輸實時性要求。DPSC退避算法與其他三種算法在節(jié)點低密度與低負(fù)載情況下網(wǎng)絡(luò)性能差別不大，但在節(jié)點高密度與高負(fù)載情況下則表現(xiàn)出優(yōu)越的網(wǎng)絡(luò)性能。進(jìn)一步的工作將采用無線傳感器硬件平臺CC2430對DPSC退避算法進(jìn)行實際性能測試。
參考文獻(xiàn)
[1] 王越超，程良倫.中高速傳感器網(wǎng)絡(luò)中基于服務(wù)區(qū)分的QoS路由算法研究[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]. 小型微型計算機系統(tǒng), 2009，30(4):679-682.
[6] 余慶春，譚獅. 一種基于轉(zhuǎn)發(fā)優(yōu)先及流量分級的無線傳感器網(wǎng)絡(luò)退避算法[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.