無線傳感器網(wǎng)絡(luò)采樣與通信調(diào)度研究

1動態(tài)調(diào)度算法隨著通信技術(shù)、嵌入式技術(shù)和傳感器技術(shù)的快速發(fā)展和成熟，具有傳感器技術(shù)、計算和通信能力的微型傳感器在世界范圍內(nèi)出現(xiàn)。由這些微型傳感器構(gòu)成的無線傳感器網(wǎng)絡(luò)引起了人們的極大關(guān)注。這種傳感器網(wǎng)絡(luò)綜合了傳感器技術(shù)、嵌入式計算技術(shù)、分布式信息處理技術(shù)和通信技術(shù),能夠協(xié)作地實時監(jiān)測、感知和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境或監(jiān)測對象的信息,并對這些信息進行處理,獲得詳盡而準確的信息,傳送到需要這些信息的用戶。在網(wǎng)絡(luò)工作過程中節(jié)省能源,最大化網(wǎng)絡(luò)的生命周期,是無線傳感器網(wǎng)絡(luò)需要解決的重要問題。為了節(jié)省能源,需要研究如何盡量減少傳感器節(jié)點間的通信量,如何減少傳感器節(jié)點的監(jiān)聽時間,以及如何在滿足系統(tǒng)監(jiān)測精度的前提下最小化采樣次數(shù)。對某些特定區(qū)域或目標進行監(jiān)測是無線傳感器網(wǎng)絡(luò)的主要用途。在許多實際應(yīng)用中,例如監(jiān)測某區(qū)域內(nèi)的溫度、濕度和亮度等,被監(jiān)測區(qū)域要布置多個相同類型的傳感器節(jié)點。它們通過合作的方式來完成同一監(jiān)測任務(wù)。傳感器節(jié)點根據(jù)用戶的要求進行數(shù)據(jù)采樣并通過多跳方式把數(shù)據(jù)傳送給用戶。為了減少傳感器節(jié)點的能量消耗,在滿足用戶的精度要求的前提下,動態(tài)調(diào)整節(jié)點采樣的周期,并減少數(shù)據(jù)的傳輸數(shù)量,從而減少傳感器節(jié)點的能量消耗。本文提出了一種基于感知數(shù)據(jù)概率模型的采樣和通信的動態(tài)調(diào)度算法:每個傳感器節(jié)點根據(jù)感知數(shù)據(jù)的概率模型來確定自己的采樣和通信時機,最小化采樣頻率和通信量,減少傳感器節(jié)點的能量消耗,以延長傳感器網(wǎng)絡(luò)的生命期。這是一種分布式算法,適用于無線傳感器網(wǎng)絡(luò),采用了簡單的概率模型,資源需求量小,適合于在目前普遍使用的資源受限的傳感器節(jié)點上運行。2fps調(diào)度算法文獻提出了數(shù)據(jù)為中心的調(diào)度算法DCS(data-centricscheduling)。這個算法從無線通信的角度考慮能量節(jié)省問題,其核心思想是在保證無線AdHoc通信丟包率較低的情況下,盡量減少每個節(jié)點處于通信或者監(jiān)聽狀態(tài)的時間,以節(jié)省傳感器網(wǎng)絡(luò)的能量。在DCS算法中,每個節(jié)點根據(jù)歷史信息,動態(tài)地預(yù)測下一個數(shù)據(jù)包到來的時間。此外,每個節(jié)點還可以判斷這些數(shù)據(jù)包到達的頻率是否發(fā)生了變化,并對預(yù)測的下一個數(shù)據(jù)包到來的時間做動態(tài)調(diào)整。DCS算法的優(yōu)點在于考慮了數(shù)據(jù)包產(chǎn)生頻率的多樣性,并適合傳感器節(jié)點分布密度較大的監(jiān)測環(huán)境。文獻提出了FPS調(diào)度算法,該算法適應(yīng)于網(wǎng)絡(luò)中通信需求動態(tài)變化的特點。FPS算法適合于基于樹狀的拓撲結(jié)構(gòu),目的是調(diào)度每個節(jié)點收發(fā)信息的時間片,減少通信的沖突和丟包。文獻提出的算法使節(jié)點僅在被需要時才從睡眠狀態(tài)轉(zhuǎn)換到通信狀態(tài),以節(jié)省能量。文獻中提出了一種分布式節(jié)點調(diào)度協(xié)議LORD。該協(xié)議在保證無線傳感器網(wǎng)絡(luò)的覆蓋性和連通性基礎(chǔ)上,調(diào)度每個節(jié)點進入活動或者睡眠狀態(tài)。上述算法都沒有考慮數(shù)據(jù)本身的特性,沒有很好地解決能量節(jié)省問題。文獻提出一類預(yù)測查詢處理方法。這些方法考慮了感知數(shù)據(jù)本身的特性,試圖解決上述方法的問題。他們首先對傳感器網(wǎng)絡(luò)進行建模,然后根據(jù)概率模型進行未來感知數(shù)據(jù)的預(yù)測并進行查詢處理。但是,文獻提出的方法是集中式算法,需要把所有感知數(shù)據(jù)傳送到中心處理節(jié)點,要求大量的網(wǎng)絡(luò)通信,導(dǎo)致高能量消耗,僅適合與所有傳感器節(jié)點距離中心處理節(jié)點都很近的情況,不適合于一般的無線傳感器網(wǎng)絡(luò)。本文提出了一種基于感知數(shù)據(jù)概率模型的傳感器節(jié)點采樣和通信的分布式動態(tài)調(diào)度算法,既考慮了感知數(shù)據(jù)本身的特性,克服了文獻提出的方法的弱點,也克服了文獻提出的集中式方法存在的缺點。3基于簡單概率模型的采樣與通信規(guī)劃算法3.1k步預(yù)測和實時化采樣許多無線傳感器網(wǎng)絡(luò)的應(yīng)用采用基于“簇”的體系結(jié)構(gòu)。根據(jù)應(yīng)用的要求,對于一個監(jiān)測目標,傳感器網(wǎng)絡(luò)中一般具有多個傳感器節(jié)點對其進行監(jiān)測。這些節(jié)點構(gòu)成了一個“簇”,其中一個節(jié)點被選為簇頭(Clusterhead)。簇的成員節(jié)點在簇頭的調(diào)度下協(xié)同完成采樣和建模任務(wù)。由于傳感器節(jié)點可以使用的資源很有限,因此在節(jié)點上執(zhí)行的建模算法要盡量簡單,使用的內(nèi)存也要小。為此,使用了比較簡單的AR(P)模型進行感知數(shù)據(jù)建模。我們首先介紹感知數(shù)據(jù)建模的方法。由于傳感器節(jié)點采樣的數(shù)據(jù)是一個時間序列,可以使用概率模型來表示這個時間序列。由于傳感器節(jié)點的資源有限性,我們使用較容易在傳感器節(jié)點上實現(xiàn)的AR(P)模型來表示傳感器節(jié)點的采樣數(shù)據(jù)。AR(P)模型可以具有如下形式:Xt=φ1Xt-1+φ2Xt-2+…+φpXt-p+αt(t≥p),αt～NID(0,δ2tt2)(1)其中,Xt是在時刻t采樣得到的數(shù)據(jù),φ是回歸系數(shù),αt是白噪聲序列,服從標準正態(tài)分布。P階模型(記作AR(P))用前P個采樣數(shù)據(jù)的一個線性組合加上一個隨機白噪聲來預(yù)測時刻t的數(shù)據(jù)。AR(P)模型可以用于預(yù)測。例如,對于AR(1)模型,在時刻t,能以95%的置信度向前進行k步預(yù)測:Xt(k)±1.96δ2tt2(1+φ2112+φ4114+…+φ2(k?1)112(k-1))1/2其中,Xt(k)可以由公式(1)(令P=1)遞歸計算出來。使用P階AR(P)模型進行建模,簇內(nèi)的節(jié)點需要N個采樣值:X1,X2,…,XN,然后通過最小二乘法求出系數(shù)φ1,φ2,…,φP。令:Y=(XP+1,XP+2,?,XN)rθ=(φ1,φ2,?,φP)rA=????XP?X1XP+1?X2??XN?1?XN?P????rε=(αP+1,αP+2,?,αN)rY=(XΡ+1,XΡ+2,?,XΝ)rθ=(φ1,φ2,?,φΡ)rA=[XΡXΡ+1?XΝ-1???X1X2?XΝ-Ρ]rε=(αΡ+1,αΡ+2,?,αΝ)r則公式(1)能夠表示成Y=Aθ+ε,系數(shù)矩陣θ可以通過最小二乘法計算:θ=(ArA)-1ArY(2)把計算公式(2)的任務(wù)劃分為多個子任務(wù),每個節(jié)點執(zhí)行其中的一個。令A(yù)t=(Xt,Xt-1,…,Xt-p+1)r,表示截止到時刻t長度為p的采樣序列。注意到在時刻t+1,At+1=Push(Drop(At),Xt+1),即首先去掉At中最開始的采樣數(shù)據(jù)Xt-p+1,然后加入新的采樣數(shù)據(jù)Xt+1。于是矩陣A的轉(zhuǎn)制矩陣Ar可以表示成:Ar=(Ap,Ap+1,…,AN-1)。為了計算式(2),分別進行如下計算:ArA=∑k=pN?1AkArk(3)ArA=∑k=pΝ-1AkAkr(3)ArY=∑k=pN?1Xk+1Ak(4)ArY=∑k=pΝ-1Xk+1Ak(4)公式(3)和(4)將任務(wù)(2)中大的矩陣運算分解為長度為P的向量運算,而且不占用很大的存儲空間,在實際應(yīng)用中,P通常的取值不會很大,例如P=5就可以擬合很多實際的序列。為了保持傳感器網(wǎng)絡(luò)各節(jié)點的能量均衡,把上述計算任務(wù)按照簇中每個節(jié)點剩余能量的多少分成若干個子任務(wù)。每個節(jié)點所要完成的子任務(wù)包括:在任務(wù)規(guī)定的時間范圍內(nèi)進行采樣,對采樣數(shù)據(jù)計算公式(3)和(4)中的部分和,將上述兩個部分和返回簇頭,最后由簇頭節(jié)點完成公式(2)的計算。任務(wù)的劃分以及調(diào)度由簇頭節(jié)點來完成。由于AR(P)模型假設(shè)時間序列的均值為0,算法首先需要估計時間序列的均值。然后,每個節(jié)點把采樣值減去均值的估計值,進行0均值化處理。可以根據(jù)上述建模方法,給出感知數(shù)據(jù)的建模算法。在給出感知數(shù)據(jù)建模算法之前,首先給出算法中使用的符號。如下所示:M:一個cluster內(nèi)部參加計算的節(jié)點數(shù)目。Poweri:節(jié)點i剩余能量。N:采樣總數(shù)。Ni:分配給節(jié)點i采樣的個數(shù)。Li:指定節(jié)點i開始采樣的時間。μt:時刻t計算得到的樣本均值。Tm:Clusterhead節(jié)點計算初始均值所需的采樣時間。Xj:時刻j的采樣值。P:AR(P)模型的階數(shù)。ARAi:節(jié)點i計算的ArA部分值(公式3)。ARYi:節(jié)點i計算的ArY部分值(公式4)。Ai:節(jié)點i計算公式(3)和(4)中的向量Ak。Si:用于計算均值的各個節(jié)點采樣值的和。感知數(shù)據(jù)的建模算法定義如下:算法1分布式傳感器網(wǎng)內(nèi)建模算法輸入:N個采樣數(shù)據(jù)輸出:AR(P)模型的數(shù)矩陣θ,白噪聲序列的方差δ2在Clusterhead節(jié)點執(zhí)行如下計算:(1)μt=(∑t?Tm≤j≤tXj)/|{Xj|t?Tm<j<t}|(1)μt=(∑t-Τm≤j≤tXj)/|{Xj|t-Τm<j<t}|;//計算在時間段Tm內(nèi)采樣值的均值,初始化μt(2)Ni=Max(N*Poweri/∑j=1mPowerj,P+1)(2)Νi=Μax(Ν*Ρoweri/∑j=1mΡowerj,Ρ+1);//根據(jù)節(jié)點剩余能量分配要采樣數(shù)據(jù)的個數(shù),最少P+1個(3)Li=(∑j=1i?1Nj)?P+1(3)Li=(∑j=1i-1Νj)-Ρ+1,其中1<i≤m,L1=1;//計算每個節(jié)點開始采樣的時間(4)Clusterhead節(jié)點將上述步驟的結(jié)果通知給cluster內(nèi)部其他參與計算的節(jié)點;進入睡眠狀態(tài);(5)按照調(diào)度計劃,clusterhead在每個成員返回子任務(wù)的結(jié)果時轉(zhuǎn)入工作狀態(tài),接收結(jié)果。當所有子任務(wù)結(jié)束后,執(zhí)行如下計算:(6)ArA=∑i=1mARAi(6)ArA=∑i=1mARAi//計算公式(3)(7)ArY=∑i=1mARYi(7)ArY=∑i=1mARYi//計算公式(4)(8)θ=(ArA)?1ArY(9)μ=(∑i=1mSi)/N(8)θ=(ArA)-1ArY(9)μ=(∑i=1mSi)/Ν//根據(jù)其他節(jié)點返回的部分和計算均值(10)Clusterhead節(jié)點將參數(shù)θ通知給其他節(jié)點,并且接收從其他節(jié)點返回的殘差值ε2以及Poweri;(11)σ?2α=(∑i=1mε2i)/m(11)σ^2α=(∑i=1mε2i)/m//計算AR(P)模型中白噪聲序列的方差在Cluster成員節(jié)點:根據(jù)clusterhead節(jié)點的調(diào)度計劃,在時間區(qū)間ti=,節(jié)點i執(zhí)行如下的步驟:(1)計算分配給自己的建模子任務(wù):(2)將ARAi,ARYi和Si返回clusterhead節(jié)點。轉(zhuǎn)入睡眠狀態(tài);(3)根據(jù)調(diào)度計劃,在clusterhead發(fā)送參數(shù)矩陣的時候,喚醒;(4)計算并返回εi以及Poweri;εi=XLi+Ni?∑k=Li+Ni?1Li+Ni?pφkXkεi=XLi+Νi-∑k=Li+Νi-1Li+Νi-pφkXk3.2采樣和通信調(diào)度算法通過算法1,每個簇對所監(jiān)測目標的采樣數(shù)據(jù)建立了AR(P)模型。我們可以使用這個AR(P)模型以及用戶指定的精度,動態(tài)喚醒節(jié)點、執(zhí)行采樣以及傳送數(shù)據(jù),從而盡量減少能量的消耗。我們的采樣和調(diào)度算法的基本思想是:利用AR(P)模型的預(yù)測功能,根據(jù)歷史數(shù)據(jù)來預(yù)測將來的數(shù)據(jù)。同時,根據(jù)用戶的精度要求,動態(tài)調(diào)整采樣時間間隔。如果預(yù)測的值滿足精度要求,則不需要啟動傳感器節(jié)點進行實際采樣和數(shù)據(jù)傳送,適當延長節(jié)點的睡眠時間。如果預(yù)測值誤差超過了精度要求,則一方面要將真實的采樣和數(shù)據(jù)傳送,另一方面需要對AR(P)模型進行適當?shù)恼{(diào)整。對于AR(P)模型,在時刻t的l步前向預(yù)測值可以用以下公式計算:Xt(l)=∑k=1PφkXt(l?k)Xt(l)=∑k=1ΡφkXt(l-k)對應(yīng)的1-α置信區(qū)間可以為:Xt(l)±zα/2σα(1+G12+…+Gl-12)1/2(5)其中,Φ(zα/2=1?α/2)?Gj=∑i=1jφiGj?i?G0=1,ΦΦ(zα/2=1-α/2)?Gj=∑i=1jφiGj-i?G0=1,Φ為標準正態(tài)分布函數(shù),Gj稱為格林函數(shù)(GreenFunction)。在我們的采樣和通信調(diào)度算法中,當一個節(jié)點被喚醒后,它首先進行采樣,然后檢查使用公式(5)計算的預(yù)測值與當前采樣值的誤差,根據(jù)誤差決定下次采樣的時間、是否需要傳送數(shù)據(jù)以及模型調(diào)整等。下邊,我們給出采樣和時間調(diào)度算法。下面給出了算法中使用的符號的定義:T:初始的采樣周期。t0:節(jié)點開始采樣的時間。len:指定一個節(jié)點采樣的次數(shù)。t:當前的時間。T1:調(diào)整后的采樣周期。Xt:時刻t的預(yù)測值。xt:時刻t的采樣值。error_bound:誤差允許的閾值。n_error:系統(tǒng)制定的采樣周期內(nèi)誤差超出閾值的次數(shù)。算法2無線傳感器網(wǎng)絡(luò)采樣和通信調(diào)度算法4基于模型的調(diào)度策略主要從以下幾個方面考察上述算法在不同精度要求下的能量有效性:實際傳送的數(shù)據(jù)量以及節(jié)點處于工作狀態(tài)的時間。下面列出了模擬系統(tǒng)的主要參數(shù)配置:時間序列:生成的AR(3)和ARMA(4,3)序列,MOTE模擬生成的序列節(jié)點數(shù)目:30cluster數(shù)目:5節(jié)點實際傳送的數(shù)據(jù)量如圖1所示。從圖中可以看出,采用了滿足不同置信度的概率模型之后,需要傳送的數(shù)據(jù)量大大減少。圖中實時監(jiān)測表示不對數(shù)據(jù)進行建模,而是返回所有采樣的數(shù)據(jù)。對于采用預(yù)測模型的方法,隨著置信度的增加,由于預(yù)測數(shù)據(jù)與實際采樣數(shù)據(jù)的誤差增加,因此需要傳送的數(shù)據(jù)也隨之增加。但是,從圖1我們可以得出結(jié)論,在滿足應(yīng)用精度要求的基礎(chǔ)上,適當調(diào)整預(yù)測數(shù)據(jù)的置信度可以有效減少傳感器網(wǎng)絡(luò)中數(shù)據(jù)的傳輸量,從而有效減少網(wǎng)絡(luò)能量的開銷。節(jié)點消耗能量的工作狀態(tài)主要是通訊、采樣和計算。通過基于模型的調(diào)度策略,可以減少結(jié)點處于上述工作狀態(tài)的時間。圖2顯示了節(jié)點在不同置信度要求下,處于工作狀態(tài)的時間。為了進行統(tǒng)一的表示,節(jié)點的工作時間以采樣周期長度T為單位。從圖2可以看出,基于概率預(yù)測模型的調(diào)度策略有效地減少了節(jié)點的工作時間,因為在適