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

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

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