無線傳感器網(wǎng)絡(luò)節(jié)點基于時間相關(guān)性的緩沖管理算法

李 迅,楊穩(wěn)競

(國防科技大學(xué)機(jī)電工程與自動化學(xué)院,長沙 410073)

無線傳感器網(wǎng)絡(luò)[1-2]由大量的低成本的節(jié)點構(gòu)成,有著廣泛的應(yīng)用前景[3-4]。在無線傳感器網(wǎng)絡(luò)的應(yīng)用中,研究主要集中在節(jié)點協(xié)同[3,5]和能量節(jié)約[3]等關(guān)鍵技術(shù)上,但在一些應(yīng)用中,如活動目標(biāo)跟蹤[5],僅考慮這些方面是不夠的,還必須考慮感知數(shù)據(jù)的實時性。無線傳感器節(jié)點有一定的緩沖空間,可以處理短時間的數(shù)據(jù)傳輸過載。但節(jié)點主要采用低功耗單片機(jī)實現(xiàn),單片機(jī)資源有限,如 MICA系列節(jié)點采用了 ATMEL128L[6]AVR單片機(jī),其內(nèi)存只有有限的 4 kbyte,除數(shù)據(jù)緩沖外,還要分配一定的空間用于程序運(yùn)行,因此緩沖資源非常有限。緩沖資源的限制可能造成有用報文的丟失,產(chǎn)生一個極大的時延,即使數(shù)據(jù)沒有丟失,過多地緩沖一些冗余信息數(shù)據(jù),也會造成較大的時延。

信息傳輸延遲由單個節(jié)點的延遲累加構(gòu)成,單個子節(jié)點延遲主要由 MAC層的傳輸延遲和網(wǎng)絡(luò)層的緩沖延遲構(gòu)成,是動態(tài)變化的。無線傳感器網(wǎng)絡(luò)的 MAC協(xié)議分為低占空比協(xié)議、基于競爭的協(xié)議和基于時間表的協(xié)議。其中,基于時間表的協(xié)議采用TDMA技術(shù),如文獻(xiàn)[7]所述,文獻(xiàn)[7]采用分簇結(jié)構(gòu),簇頭為簇內(nèi)節(jié)點分配時槽,發(fā)射機(jī)和接收機(jī)嚴(yán)格遵守時隙的要求,避免在時間上互相重疊,從而避免沖突。對動態(tài)目標(biāo)跟蹤這類實時性要求較高的應(yīng)用,基于時間表的協(xié)議可以提供確定性的時延,是一種較好的選擇。MAC層采用基于時間表的協(xié)議,節(jié)點信息傳輸延遲的動態(tài)性由節(jié)點緩沖的動態(tài)性而體現(xiàn),尤其對實現(xiàn)轉(zhuǎn)發(fā)功能的節(jié)點,其緩沖的動態(tài)變化更加明顯。

傳輸延遲的影響在文獻(xiàn)[8]中進(jìn)行了詳細(xì)分析。該文獻(xiàn)從時空誤差的角度分析了分布式測量跟蹤系統(tǒng)中,由于時間傳輸延遲的存在,使得執(zhí)行節(jié)點獲得目標(biāo)的目標(biāo)信息產(chǎn)生滯后,而在對目標(biāo)當(dāng)前位置進(jìn)行推測時,由于時間延遲造成推測的空間誤差。假定平面坐標(biāo)系內(nèi)目標(biāo)在 t0時刻位置為 →r0,速度為→v0,信息傳輸延遲為 Tt,則執(zhí)行節(jié)點在 t=t0+Tt得到探測數(shù)據(jù),此時目標(biāo)已移動到位置 →r(t)：

執(zhí)行節(jié)點需要對 t時刻的目標(biāo)位置進(jìn)行推測,推測時取目標(biāo)運(yùn)動模型為 CV模型[9],則

則推測誤差：

從上面可以看到,時間延遲的存在和推測誤差的大小密切相關(guān),而且時間延遲的存在也造成了執(zhí)行節(jié)點不能及時響應(yīng),這就需要對延遲進(jìn)行控制。

1 時間相關(guān)主動緩沖隊列管理算法

在無線傳感器網(wǎng)絡(luò)環(huán)境中,節(jié)點周期性的感知目標(biāo),感知信息存在時間上的相關(guān)性[10],時間接近的感知數(shù)據(jù),從信息角度看是冗余的。在緩沖隊列中,有選擇的丟棄冗余的信息,就能夠有效地避免丟棄有用的信息,降低有用信息的緩沖延遲時間。當(dāng)前的緩沖管理采用主動緩沖隊列管理,主動緩沖管理算法的研究基本集中在 RED[11]算法及其改進(jìn)上。RED算法根據(jù)平均隊列長度和預(yù)先設(shè)定的閥值以一定的概率主動丟棄分組,這就有效地避免了緩沖區(qū)滿的情況。在無線傳感器網(wǎng)絡(luò)條件下,單純以平均隊列長度來判定分組的丟棄,不能保證丟棄的是冗余數(shù)據(jù)。為解決這一問題,下面設(shè)計一個基于時間相關(guān)判定的主動隊列緩沖管理算法 -TRED(Time-based RED)。

無線傳感器網(wǎng)絡(luò)節(jié)點用時戳來標(biāo)識感知信息的時間[12]。記緩沖區(qū)中最后到達(dá)報文的時戳為 Tlast。推算允許最大延遲時間Tmax,到達(dá)數(shù)據(jù)時戳和 Tlast差如果超過 Tmax,則報文沒有意義。將 Tmax劃分為Γ(Γ≥1)級,[0,σ)、[σ,2σ)…[(Γ-1)σ,Γσ),報文i時戳為ti,Δti=|Tlast-ti|,則定義報文 i在時間度量上的丟棄概率如下：

從上述定義看,時間相關(guān)性越高的報文,報文的丟棄概率越高。

除了時間因素,緩沖管理還必須考慮數(shù)據(jù)緩沖情況。RED算法設(shè)定參數(shù) thmin、thmax分別代表總的緩沖隊列的最小和最大閥值。緩沖隊列的占用情況用平均隊列來表示,當(dāng)報文 i到達(dá)或離開時,平均隊列長度按下式計算：

(i＞=1,0≤wq≤1),L(i)為報文 i到達(dá)或離開時緩沖隊列長度,分別計算如下：

這里,P(i)為到達(dá)或離開的報文的長度,平均隊列長度、緩沖隊列長度和報文長度均按照字節(jié)為單位計算。報文 i丟棄概率如下：

上式中,Pmax為一個相對較小的值,控制報文的丟棄概率。綜合緩沖隊列長度和時間相關(guān)性,報文 i最終丟棄概率：

TRED算法可以實現(xiàn)基于時間和緩沖隊列長度判定的緩沖管理,時間相關(guān)因子的引入保證了時間相關(guān)性大的數(shù)據(jù)其丟棄概率要比時間相關(guān)性小的數(shù)據(jù)的丟棄概率高,即 ：?i,j,如果 Δti≤Δtj＜Tmax,在相同緩沖條件約束下,Pi≥Pj。

2 算法仿真驗證

仿真實驗假定 5個感知節(jié)點向一個轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù),拓?fù)浣Y(jié)構(gòu)如下圖。

圖1 仿真拓?fù)浣Y(jié)構(gòu)

在圖 1中,節(jié)點 1～5周期性感知數(shù)據(jù),并將其發(fā)送到轉(zhuǎn)發(fā)節(jié)點 6,其數(shù)據(jù)產(chǎn)生周期 1ms,MAC層采用 TDMA算法,時槽分配周期 12 ms,每個時槽2 ms,每個時槽可以發(fā)送一個完整的報文,并且每個節(jié)點的報文長度固定,每個節(jié)點發(fā)送 50個感知數(shù)據(jù)。節(jié)點 6數(shù)據(jù)緩沖 2 kbyte。緩沖管理采用 TRED算法,相關(guān)參數(shù)配置為：thmin=256 B,thmax=1 536 B,w=0.1,Pmax=0.8,Tmax=6ms,Γ=5,則時間相關(guān)區(qū)間分別為 [0.0,1.2)、[1.2,2.4)、[2.4,3.6)、[3.6,4.8)、[4.8,6.0)。節(jié)點探測到目標(biāo)的起始時間分別為：(t0+0)ms,(t0+1)ms,(t0+3)ms,(t0+6)ms,(t0+10)ms。圖 2和圖 3顯示了在此參數(shù)設(shè)置下的仿真結(jié)果。

圖2 不同時間區(qū)域丟棄比率

不同節(jié)點產(chǎn)生的探測數(shù)據(jù)在到達(dá)轉(zhuǎn)發(fā)節(jié)點時,其數(shù)據(jù)可以歸于不同的時間相關(guān)區(qū)間。從仿真結(jié)果圖 2可以看出,時間區(qū)間[0.0,1.2)的報文丟棄最多,而[4.8,6.0)區(qū)間在這一情況下報文沒有丟棄。這一結(jié)果體現(xiàn)了在丟棄概率計算過程時間相關(guān)判定因子的作用。圖 3給出了時間緩沖隊列和平均隊列的變化,可以看出平均隊列對實際緩沖隊列進(jìn)行了平滑。

圖3 實際隊列和平均隊列

3 結(jié)論

無線傳感器網(wǎng)絡(luò)節(jié)點,由于連續(xù)的探測數(shù)據(jù)并進(jìn)行傳輸,使得同一節(jié)點或相近節(jié)點產(chǎn)生的數(shù)據(jù)存在時間上的相關(guān)性,數(shù)據(jù)之間時間相隔越小,數(shù)據(jù)的時間相關(guān)性越強(qiáng),信息冗余度越高,丟棄時間相關(guān)數(shù)據(jù),可以有效的降低節(jié)點對數(shù)據(jù)的緩沖延遲。TRED算法通過時間相關(guān)判定因子的引入,改進(jìn)了主動隊列緩沖管理算法,在根據(jù)平均隊列長度丟棄報文時,強(qiáng)化丟棄時間相關(guān)的數(shù)據(jù)報文,這樣就能夠盡可能丟棄時間相關(guān)性越強(qiáng)的數(shù)據(jù),即信息冗余的數(shù)據(jù),保留匯聚節(jié)點進(jìn)行推斷時有用的數(shù)據(jù)信息,提高了推斷的準(zhǔn)確性。

[1]Akyidiz I F,Su W,Sankasubramaniam Y,et al.Wireless Sensor Networks：A Survey[J].Computer Networks,2002,38：393-422.

[2]孫立民,李健中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社,2005.

[3]ZHAO F,Shin J,Reich J.Information-D riven Dynamic Sensor Collaboration for Tracking Application[J].IEEE Signal Processing Magazine,2002,19(2)：61-62.

[4]Wai-Leong Yeow,Chen-Khong Tham,Wai-ChoongWong.Energy Efficient Multiple Target Tracking Wireless Sensor Networks[J].IEEE Transactions on Vehicular Technology,2007,56(2)：918-928.

[5]王永才.傳感器網(wǎng)絡(luò)目標(biāo)跟蹤系統(tǒng)協(xié)同設(shè)計理論研究與應(yīng)用[D].清華大學(xué),2006.

[6]Atmel,8-bit Microcontroller with 128K Bytes In-System Programmable Flash ATmega128/ATmega128L Preliminary[M].Rev 2467J-AVR-12/03.

[7]Arisha K A,Youssef M A,Younis M F.Energy-Aware TDMABASED MAC for Sensor Networks[C]//Proc IEEE Workshop on Integrated Management of Power Aware Communication,Computing and Networking,New York,2002.

[8]Technical report,Sensitivity of Track Accuracy to Navigation,Sensor,and Time Errors Within a Distributed System[R].Joint Single Integrated Air Picture System Engineering Organization Analysis Branch.2004,7.2.6.3_TR(4-002)_1.0_JSSEO_040407.

[9]范小軍,劉鋒.一種新的機(jī)動目標(biāo)跟蹤的多模型算法[J].電子與信息學(xué)報,2007,29(3)：532-535.

[10]Vuran C,Akan B,Akyildiz F.Spatio-Temporal Correlation：Theory and Applications for Wireless Sensor Networks[J].Computer Networks,2004,45：245-259.

[11]Lin D,Morris R.Dynam ics of Random Early Detection[J].In Proc of SIGCOMM,Cabbesm France,1997,137-145.

[12]崔遜學(xué),左從菊.無線傳感器網(wǎng)絡(luò)簡明教程[M].北京：清華大學(xué)出版社,2009.