文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 0258-7998(2013)10-0112-04
中高速無(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)等,不能滿(mǎn)足數(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)滿(mǎn)足應(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í)延,滿(mǎn)足關(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.