無線傳感器網(wǎng)路徑時延區(qū)間估計算法研究＊

［黃河清］

1 引言

隨著各種通信技術(shù)和手段的發(fā)展，網(wǎng)絡(luò)正在從互聯(lián)網(wǎng)向所有機(jī)器和設(shè)備具有互聯(lián)能力的方向發(fā)展。傳感器網(wǎng)絡(luò)連接物聯(lián)網(wǎng)和物理世界，承擔(dān)收集和傳輸數(shù)據(jù)的任務(wù)。在無線傳感器網(wǎng)絡(luò)（WSN）中，強(qiáng)實時性的關(guān)鍵任務(wù)，如工業(yè)控制和智能交通，無線消息傳輸對實時性和可靠性提出了很高的要求。在多跳無線網(wǎng)絡(luò)中，實時路由的主要含義是在有限的時間內(nèi)將數(shù)據(jù)包從源節(jié)點路由到目的節(jié)點。實時路由的關(guān)鍵要素是消息的可靠和實時傳輸。然而，由于無線鏈路的時空動態(tài)和沿路徑的隊列變化特征等因素的影響，數(shù)據(jù)包跨路徑成功傳輸?shù)臅r間（即路徑延遲）是不確定的。路徑延遲的這種動態(tài)特性給實時路由的計算帶來了根本性的挑戰(zhàn)。

雖然在無線路由算法上已經(jīng)做了大量的研究工作，但基于吞吐量或能效，對高效實時路由的研究效果較差。盡管現(xiàn)有的無線路由研究結(jié)果增加了最小化平均路徑延遲的努力，但它們并不能保證一定的概率邊界。因此，如何在不確定和動態(tài)的鏈路環(huán)境下提高實時路由的效率是實時無線傳感器網(wǎng)絡(luò)研究的重要任務(wù)。為了在無線傳感器網(wǎng)絡(luò)中實現(xiàn)概率延遲邊界路由，我們提出了一種多時間尺度方法，該方法以自適應(yīng)延遲界限估計（ADBE，adaptive delay bound estimation）表示。通過準(zhǔn)確估計數(shù)據(jù)包時間的平均值和方差，并通過適應(yīng)快速變化的隊列，可以計算出路徑延遲的方差和平均值，以解決實時路由中動態(tài)和不確定的路徑延遲問題。利用上述路徑延遲計算結(jié)果，通過實驗評估了計算路徑延遲上限的方法，并比較了它們的效率和效果。

通過檢索無線傳感器網(wǎng)絡(luò)路由的現(xiàn)有研究文獻(xiàn)，雖然也考慮了路徑延遲要素，但大部分研究只努力最小化平均路徑延遲，而不考慮路徑延遲的概率特征，或者不對延遲概率邊界進(jìn)行分析。一些研究側(cè)重于轉(zhuǎn)發(fā)路徑上鏈路可靠性、時效性等QoS 因素的統(tǒng)一劃分，但缺乏網(wǎng)絡(luò)異構(gòu)性的引入。然而，在互聯(lián)網(wǎng)流量工程的應(yīng)用中已經(jīng)提出了自適應(yīng)時延邊界估計?？傊?，現(xiàn)有的研究大多只關(guān)注數(shù)據(jù)傳輸?shù)目煽啃裕狈崟r性研究。因此，對實時路由中的動態(tài)和不確定鏈路時延的研究還存在不足。

端到端時延在硬實時系統(tǒng)中有嚴(yán)格的要求，主要依靠物理層的調(diào)度工作來滿足實時性目標(biāo)。如I-EDF[1]、dual-Mode[2]，但這種方法對物理條件要求很高。在SPEED[3]的研究中，提出了轉(zhuǎn)發(fā)速度的概念，主要通過每一跳的轉(zhuǎn)發(fā)速度來保證端到端的通信時延，但SPEED 沒有考慮鏈路的質(zhì)量，不能保證可靠性。其他研究從分層網(wǎng)絡(luò)結(jié)構(gòu)的角度考慮實時。例如，文獻(xiàn)[4]通過調(diào)整非實時和實時數(shù)據(jù)占用的傳輸帶寬來最大化每個集群的吞吐量，但在效率方面存在明顯不足，難以滿足實時性要求。本文接下來介紹了自適應(yīng)路徑延遲邊界估計方法，提供實驗數(shù)據(jù)驗證結(jié)果，并對研究情況做一總結(jié)。

2 自適應(yīng)路徑延遲邊界估計

2.1 路徑延遲概率邊界計算

通過在實驗系統(tǒng)上測試驗證，我們發(fā)現(xiàn)：在大流量模式下，網(wǎng)絡(luò)中會出現(xiàn)嚴(yán)重的隊列擁塞，隊列溢出頻繁發(fā)生;在中等流量模式下，網(wǎng)絡(luò)的排隊程度適中，但很少發(fā)生隊列溢出[5];但在輕流量模式下，網(wǎng)絡(luò)中不存在排隊現(xiàn)象;基于以上條件假設(shè)，我們選取12 個節(jié)點作為業(yè)務(wù)數(shù)據(jù)源，1 個節(jié)點作為匯節(jié)點。在拓?fù)渲?，源?jié)點和接收器節(jié)點幾乎處于相反的位置，以創(chuàng)建多路由路徑。每個源節(jié)點每75 ms、400 ms 和1 000 ms 生成一個重、中、輕流量數(shù)據(jù)包。

為了保證路由的延遲概率在限定范圍內(nèi)，如何量化路徑上的延遲概率是一項重要的工作。如圖1 所示，在給定路徑P=v0,v1,...,vn,vn+1,中，假設(shè)在節(jié)點 vi（節(jié)點 0 到節(jié)點 n）呈現(xiàn)如下狀態(tài)：

圖1 路徑延遲構(gòu)成

其中，mi(t)表示 t 時間點隊列中的數(shù)據(jù)包編號；dP(t)表示路徑 P 在 t 時間點的當(dāng)前延遲。

將數(shù)據(jù)包傳輸?shù)?vn+1時，如果每個節(jié)點隊列中的數(shù)據(jù)包數(shù)量保持固定，則dP(t)是到達(dá)目標(biāo)節(jié)點vn+1的 v0數(shù)據(jù)包所經(jīng)歷的延遲。由此，節(jié)點vi將其隊列中的第 j 個數(shù)據(jù)包路由到節(jié)點vi+1所花費的時間可以表示為：

2.2 時延動態(tài)分布的關(guān)鍵問題

由于無線傳感器節(jié)點的資源限制，很難直接計算dP(t)的分布。另一種方法是對dP(t)進(jìn)行采樣，之后使用非參數(shù)方法（如P2 算法）來估計這些延遲樣本的延遲分位數(shù)，但非參數(shù)分位數(shù)估計通常收斂緩慢，可能需要數(shù)百個樣本?？梢园l(fā)現(xiàn)，路徑延遲在一定時間范圍內(nèi)波動，遠(yuǎn)小于非參數(shù)估計方法的窗口要求。這在上面的公式1 中可以看出，路徑延遲的分布隨轉(zhuǎn)發(fā)路徑上的隊列級別mi(t)（t 時間點隊列中的數(shù)據(jù)包數(shù)）而變化，并顯示出快速時變的特征。

仿真結(jié)果表明，非參數(shù)分位數(shù)估計收斂所需的樣本量比相干窗口高兩個數(shù)量級。因此，路徑延遲分布的快速變化特性使得非參數(shù)分位數(shù)估計難以滿足瞬時路徑延遲分位數(shù)估計的靈活性和精度要求。

為了準(zhǔn)確靈活地估計精確的路徑延遲分位數(shù)并降低計算復(fù)雜度，我們提出了一個上限邊界來識別概率路徑延遲，并利用延遲邊界進(jìn)行實時數(shù)據(jù)傳輸路徑的選擇。路徑延遲的上限可以通過切比雪夫neQuality 概率不等式推導(dǎo)出來，正確識別的延遲邊界可以達(dá)到比最大延遲小一個數(shù)量級，從而避免了對網(wǎng)絡(luò)實時容量的不利影響。

因此，我們需要設(shè)計一種更靈活、更準(zhǔn)確的機(jī)制來估計路徑延遲的均值和標(biāo)準(zhǔn)差，避免大多數(shù)概率不等式使用相應(yīng)的隨機(jī)變量計算方法的缺點。因為路徑延遲統(tǒng)計的準(zhǔn)確估計通常需要相當(dāng)大的樣本量，可以高達(dá)300 到600[6]，這明顯大于節(jié)點隊列級別的一致性窗口。

2.3 自適應(yīng)延遲邊界估算

為了應(yīng)對路徑延遲和統(tǒng)計分布變化帶來的挑戰(zhàn)，將路徑延遲變化因子分解為動態(tài)排隊和動態(tài)分組時間兩個類別。利用隊列和數(shù)據(jù)包時間的不同統(tǒng)計時間尺度，提出一種自適應(yīng)時延界限估計（ADBE）方法，該方法可以通過兩種方式準(zhǔn)確估計路徑時延的均值和方差：（1）在短時間尺度上適應(yīng)快速變化的隊列；（2）在長時間尺度上準(zhǔn)確估計數(shù)據(jù)包時間的均值和方差。

2.3.1 包轉(zhuǎn)發(fā)時間分布

經(jīng)過對實驗數(shù)據(jù)的詳細(xì)分析，我們發(fā)現(xiàn)瞬時數(shù)據(jù)包時間的分布具有良好的穩(wěn)定性，盡管在一定的網(wǎng)絡(luò)條件下瞬時數(shù)據(jù)包時間變化很快。通過分析數(shù)據(jù)包時間平穩(wěn)窗口的大小，如圖2 中的直方圖所示，可以得出結(jié)論，在時間序列的連續(xù)區(qū)間中，每個靜止窗口都是時間序列中最大的連續(xù)段。

圖2 包時間與靜止窗口分布圖

為了適應(yīng)無線傳感器網(wǎng)絡(luò)中嵌入式節(jié)點的存儲資源限制和實時傳輸要求，節(jié)點隊列的最大大小通常小于穩(wěn)定性窗口的大小。這意味著公式（1）中dji(t)的方差和平均值相同，表示為路徑延遲σ2(di(t)) 和平均路徑延遲μ(di(t))的總變化。

因此可以計算出平均路徑延遲：

2.3.2 包時間的非相關(guān)性

同一節(jié)點或不同節(jié)點的傳輸時間通常并不重要，對于給定的時間點，我們通過對沿路徑排隊的所有數(shù)據(jù)包的延遲方差求和，然后將總和的平方根作為標(biāo)準(zhǔn)偏差的等效值來計算從源節(jié)點到目標(biāo)節(jié)點的路徑延遲標(biāo)準(zhǔn)偏差。

對于圖 1 中的路徑 P，dP(t) 的標(biāo)準(zhǔn)偏差計算如下：

從上面的分析結(jié)果中，我們可以進(jìn)一步推斷出一個節(jié)點可以對不同數(shù)據(jù)包的下一跳做出很好的選擇。假設(shè)每個節(jié)點vi（i 從0 到n）具有Ni(t)可選的下一跳數(shù)，mki(t)表示在時間t 處路由到第k 個跳的數(shù)據(jù)包數(shù)，di,k(t)表示相應(yīng)的數(shù)據(jù)包時間。

沿路徑P 的延遲標(biāo)準(zhǔn)差和平均值可以根據(jù)公式（2）和（3）計算如下：

2.3.3 網(wǎng)絡(luò)排隊時間的短時穩(wěn)定性

這里，從vi到vn+1的延遲標(biāo)準(zhǔn)差和平均值分別用σ(diP(t)) 和μ(diP(t))表示。每個節(jié)點vi可以通過公式（4）計算從自身到vn+1的延遲的平均值和方差。方法是計算沿路徑P 的每個躍點的平均值和方差。這樣，我們得到以下結(jié)果。

通過允許vi+1連接σ2(diP(t))和μ(diP(t))來控制信令或數(shù)據(jù)傳輸，vi可以在τi的最短時間內(nèi)快速準(zhǔn)確地估計σ2(diP(t))和μ(diP(t))。

3 路徑概率延遲邊界實驗分析

根據(jù)上面提出的ADBE 算法估計路徑延遲均值和方差，節(jié)點的概率延遲邊界值由概率不等式得到。

在隨機(jī)變量 x 的條件下，如果下面條件滿足：

Pr{X ≥ f(x)} ≤ g(x),QqX=f (g-1(1-q))

則X 的q 分位數(shù)上的上限QqX=f (g-1(1-q))可以通過以下步驟計算出來，其中g(shù)-1是g 的反函數(shù)：

使g(x)=1-q

實驗采用選取12 個節(jié)點作為業(yè)務(wù)數(shù)據(jù)源，1 個節(jié)點作為匯節(jié)點。在拓?fù)渲校垂?jié)點和接收器節(jié)點幾乎處于相反的位置，以創(chuàng)建多路由路徑。每個源節(jié)點每 75 ms、400 ms和 1 000 ms 生成一個重、中、輕流量數(shù)據(jù)包。鏈路排隊變化的經(jīng)驗累積分布（cumulative distribution function，CDF）的實驗數(shù)據(jù)如圖3 所示，從圖3 可以看出，網(wǎng)絡(luò)隊列在幾個數(shù)據(jù)包間隔的時間尺度上相對穩(wěn)定，85%概率的鏈路排隊變化絕對值保持2 以下。

圖3 CDF 與排隊變化關(guān)系

基于上述分析，本算法具有相對穩(wěn)定的短期網(wǎng)絡(luò)排隊和快速信息擴(kuò)散，ADBE 方法能夠準(zhǔn)確、靈活地估計路徑延遲的均值和方差。

4 總結(jié)

由于無線傳感器網(wǎng)絡(luò)的動態(tài)性和不可靠性，端到端時延不確定，對實時路由的設(shè)計提出了嚴(yán)峻的挑戰(zhàn)。因此，考慮到鏈路質(zhì)量和鏈路時延，本文設(shè)計了一種新的路徑時延估計算法ADBE。針對路徑時延高度變化對路徑時延分位數(shù)分布式估計的挑戰(zhàn)，利用轉(zhuǎn)發(fā)可靠性來表示節(jié)點在給定時延閾值下成功轉(zhuǎn)發(fā)數(shù)據(jù)包到鄰居節(jié)點的概率，以保證路由的實時性和可靠性，并提供一定水平的QoS。當(dāng)鏈路質(zhì)量在環(huán)境中較差時，在滿足實時性要求的基礎(chǔ)上，通過權(quán)衡傳輸時延和傳輸可靠性，可以實現(xiàn)更高的傳輸成功率，實驗結(jié)果也證明了所提方法的優(yōu)點。