李 迅,楊穩(wěn)競(jìng)

(國(guó)防科技大學(xué)機(jī)電工程與自動(dòng)化學(xué)院,長(zhǎng)沙 410073)

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

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

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

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

則推測(cè)誤差：

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

1 時(shí)間相關(guān)主動(dòng)緩沖隊(duì)列管理算法

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

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

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

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

(i＞=1,0≤wq≤1),L(i)為報(bào)文 i到達(dá)或離開(kāi)時(shí)緩沖隊(duì)列長(zhǎng)度,分別計(jì)算如下：

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

上式中,Pmax為一個(gè)相對(duì)較小的值,控制報(bào)文的丟棄概率。綜合緩沖隊(duì)列長(zhǎng)度和時(shí)間相關(guān)性,報(bào)文 i最終丟棄概率：

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

2 算法仿真驗(yàn)證

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

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

在圖 1中,節(jié)點(diǎn) 1～5周期性感知數(shù)據(jù),并將其發(fā)送到轉(zhuǎn)發(fā)節(jié)點(diǎn) 6,其數(shù)據(jù)產(chǎn)生周期 1ms,MAC層采用 TDMA算法,時(shí)槽分配周期 12 ms,每個(gè)時(shí)槽2 ms,每個(gè)時(shí)槽可以發(fā)送一個(gè)完整的報(bào)文,并且每個(gè)節(jié)點(diǎn)的報(bào)文長(zhǎng)度固定,每個(gè)節(jié)點(diǎn)發(fā)送 50個(gè)感知數(shù)據(jù)。節(jié)點(diǎn) 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,則時(shí)間相關(guān)區(qū)間分別為 [0.0,1.2)、[1.2,2.4)、[2.4,3.6)、[3.6,4.8)、[4.8,6.0)。節(jié)點(diǎn)探測(cè)到目標(biāo)的起始時(shí)間分別為：(t0+0)ms,(t0+1)ms,(t0+3)ms,(t0+6)ms,(t0+10)ms。圖 2和圖 3顯示了在此參數(shù)設(shè)置下的仿真結(jié)果。

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

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

圖3 實(shí)際隊(duì)列和平均隊(duì)列

3 結(jié)論

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn),由于連續(xù)的探測(cè)數(shù)據(jù)并進(jìn)行傳輸,使得同一節(jié)點(diǎn)或相近節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)存在時(shí)間上的相關(guān)性,數(shù)據(jù)之間時(shí)間相隔越小,數(shù)據(jù)的時(shí)間相關(guān)性越強(qiáng),信息冗余度越高,丟棄時(shí)間相關(guān)數(shù)據(jù),可以有效的降低節(jié)點(diǎn)對(duì)數(shù)據(jù)的緩沖延遲。TRED算法通過(guò)時(shí)間相關(guān)判定因子的引入,改進(jìn)了主動(dòng)隊(duì)列緩沖管理算法,在根據(jù)平均隊(duì)列長(zhǎng)度丟棄報(bào)文時(shí),強(qiáng)化丟棄時(shí)間相關(guān)的數(shù)據(jù)報(bào)文,這樣就能夠盡可能丟棄時(shí)間相關(guān)性越強(qiáng)的數(shù)據(jù),即信息冗余的數(shù)據(jù),保留匯聚節(jié)點(diǎn)進(jìn)行推斷時(shí)有用的數(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ú)線傳感器網(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è)計(jì)理論研究與應(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ī)動(dòng)目標(biāo)跟蹤的多模型算法[J].電子與信息學(xué)報(bào),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ú)線傳感器網(wǎng)絡(luò)簡(jiǎn)明教程[M].北京：清華大學(xué)出版社,2009.