張美燕 蔡文郁 周麗萍

1 引言

近年來，隨著微機電一體化、短距離無線通信、互聯(lián)網(wǎng)絡(luò)等技術(shù)的迅速發(fā)展，一種全新的信息獲取和處理技術(shù) 無線傳感網(wǎng)（WSNs）應(yīng)運而生。無線傳感網(wǎng)是由大量無處不在的、具有無線通信與計算能力的微小傳感器節(jié)點構(gòu)成的自組織分布式多跳通信網(wǎng)絡(luò)系統(tǒng)，是能根據(jù)環(huán)境自主完成指定任務(wù)的“智能”協(xié)同系統(tǒng)[1,2]。無線傳感網(wǎng)實現(xiàn)了大量分布式時空數(shù)據(jù)的高保真采樣，但在一般應(yīng)用中傳感器節(jié)點的采樣頻率通常是固定的，而自適應(yīng)采樣技術(shù)的采樣頻率可根據(jù)被測對象的變化而變化，當(dāng)觀測對象變化趨勢慢時降低采樣頻率，當(dāng)觀測對象變化趨勢較快時提高采樣頻率。本文研究了一種基于聚類預(yù)測模型的無線傳感網(wǎng)自適應(yīng)采樣技術(shù)，所有的傳感器節(jié)點根據(jù)數(shù)據(jù)梯度關(guān)系劃分成多個聚類，算法選舉了各個聚類中的簇頭節(jié)點。簇頭節(jié)點根據(jù)感知數(shù)據(jù)的歷史模型和當(dāng)前采樣數(shù)據(jù)進(jìn)行判決，根據(jù)是否滿足采樣精度需求，進(jìn)而利用“乘增半減”的采樣頻率更新策略調(diào)整所有簇成員節(jié)點的采樣頻率。如果聚類內(nèi)傳感采樣數(shù)據(jù)的動態(tài)性比較低，則降低采樣頻率以減少冗余數(shù)據(jù)的產(chǎn)生與傳輸，如果傳感采樣數(shù)據(jù)的動態(tài)性比較高，則提高數(shù)據(jù)采樣頻率從而保證數(shù)據(jù)采樣質(zhì)量，由此實現(xiàn)網(wǎng)絡(luò)能率高效與數(shù)據(jù)采集質(zhì)量兩者之間的均衡性。

目前相關(guān)研究工作大概都基于如下假設(shè)：（1）在無線傳感網(wǎng)的實際應(yīng)用場景中，傳感器節(jié)點采集到的采樣數(shù)據(jù)通常是連續(xù)的，從總體上表現(xiàn)出一定的連續(xù)性和穩(wěn)定性；（2）受無線多跳通信不可靠、傳感器節(jié)點失效以及節(jié)點能量的限制，感知數(shù)據(jù)的獲取、處理與傳輸必然存在一定范圍的誤差值。因此，無線傳感網(wǎng)所獲取的數(shù)據(jù)集在時間域和空間域上都是無限的，實際上只能通過抽樣獲取所需的數(shù)據(jù)內(nèi)容，而且所獲得的數(shù)據(jù)并非實際的精確值，因此收集到的數(shù)據(jù)越多并不意味著結(jié)果越精確?；谏鲜鲞@種思想，有一些研究者開啟了無線傳感網(wǎng)中數(shù)據(jù)采樣優(yōu)化技術(shù)的研究。無線傳感網(wǎng)數(shù)據(jù)處理方法一般采用先進(jìn)行網(wǎng)內(nèi)數(shù)據(jù)處理然后再匯聚傳輸?shù)姆绞揭詼p少所需傳輸?shù)臄?shù)據(jù)量。目前網(wǎng)內(nèi)數(shù)據(jù)處理可分為數(shù)據(jù)近似代替（data approximation）和數(shù)據(jù)匯聚處理（data aggregation）兩種方法[3]：數(shù)據(jù)近似代替通過對感知數(shù)據(jù)進(jìn)行分布式建模，大量減少感知數(shù)據(jù)的傳輸量，從而延長網(wǎng)絡(luò)生存周期。數(shù)據(jù)近似代替方法可基于不同模型：概率模型[4]，時間序列分析模型[5]，數(shù)據(jù)挖掘模型[6]和數(shù)據(jù)壓縮模型[7]。數(shù)據(jù)匯聚處理使用AVG, TOP, COUNT, SUM等聚集函數(shù)來降低感知數(shù)據(jù)的傳輸量，但存在的最大問題是感知數(shù)據(jù)中大量的原始信息丟失，只能提供較為粗糙的統(tǒng)計結(jié)果量。

與本文想法較為相近的有以下研究：文獻(xiàn)[8]提出傳感器節(jié)點的采樣時間間隔由Sink節(jié)點根據(jù)帶寬來分配，通過Kalman濾波預(yù)測下一時刻采樣值，如果預(yù)測值和真實值的誤差大于預(yù)設(shè)閾值，則根據(jù)當(dāng)前誤差調(diào)整采樣時間間隔，但該方法沒充分利用感知數(shù)據(jù)的相關(guān)性；文獻(xiàn)[9]提出了一種利用線性回歸模型來動態(tài)調(diào)整采樣頻率的策略，在單個傳感器節(jié)點上設(shè)置預(yù)測模型，根據(jù)實際采樣數(shù)據(jù)域期望值之間的差異大小來調(diào)整采樣頻率，但是該方法增加了節(jié)點之間的通信負(fù)荷；文獻(xiàn)[10]提出了一種根據(jù)數(shù)據(jù)空間相關(guān)性選擇聚集域中采樣節(jié)點的方法，數(shù)據(jù)相關(guān)性較強的節(jié)點中，只有遴選出的某些特殊節(jié)點需要采集感知數(shù)據(jù)，因此降低了數(shù)據(jù)間的冗余，但是該方法并未考慮時間域采樣頻率的調(diào)整；文獻(xiàn)[11]提出一種在Nyquist采樣頻率基礎(chǔ)上的時間域采樣頻率的跟隨調(diào)整，但是節(jié)點之間的額外通信所需耗費很多能量。文獻(xiàn)[12]提出了一種基于預(yù)測模型的無線傳感網(wǎng)內(nèi)數(shù)據(jù)糾錯方法，在時間域建立誤差模型，以提高感知數(shù)據(jù)的可靠性。針對以上算法的不足之處，本文引入時間域數(shù)據(jù)預(yù)測模型技術(shù)，從而在分布式聚類內(nèi)實現(xiàn)自適應(yīng)采樣，提高網(wǎng)絡(luò)能效水平。文獻(xiàn)[13]創(chuàng)新地將自適應(yīng)采樣的算法應(yīng)用于無線體感網(wǎng)（body sensor networks）中，考慮了無線體感網(wǎng)的特殊限制和需求。

2 預(yù)測模型匹配自適應(yīng)采樣算法

2.1 算法原理

本文所研究的基于感知數(shù)據(jù)預(yù)測模型的自適應(yīng)采樣技術(shù)中，首先將傳感器節(jié)點根據(jù)數(shù)據(jù)梯度關(guān)系劃分成多個聚類，各個聚類中的簇頭節(jié)點根據(jù)感知數(shù)據(jù)的歷史模型和當(dāng)前采樣數(shù)據(jù)的變化情況決定聚類內(nèi)所有成員節(jié)點的采樣頻率（即下一采樣時刻），只有當(dāng)真實值（以高頻率采樣的實測值為準(zhǔn)）與預(yù)測值的誤差大于預(yù)設(shè)閾值時，簇頭節(jié)點才提高節(jié)點采樣頻率，實現(xiàn)網(wǎng)絡(luò)能率高效及數(shù)據(jù)精度質(zhì)量之間的均衡。當(dāng)感知數(shù)據(jù)的動態(tài)性較高時，提高采樣頻率從而保證采樣質(zhì)量，當(dāng)感知數(shù)據(jù)的動態(tài)性較低時，根據(jù)數(shù)據(jù)歷史模型，僅發(fā)送那些必需發(fā)送的數(shù)據(jù)，降低采樣頻率以減少冗余數(shù)據(jù)的產(chǎn)生與傳輸。

本文算法的主要原理如下：每個聚類內(nèi)的簇頭節(jié)點根據(jù)聚類內(nèi)成員節(jié)點的歷史數(shù)據(jù)建立一個預(yù)測模型，用預(yù)測模型估計的估計值來代替采樣數(shù)據(jù)，并用較低頻率的采樣數(shù)據(jù)來更新預(yù)測模型，如圖 1所示。

當(dāng)采樣數(shù)據(jù)與估計數(shù)據(jù)差較大時，逐步增大采樣頻率；否則，逐步降低采樣頻率。每個聚類內(nèi)簇頭節(jié)點的在線數(shù)據(jù)預(yù)測模型框架如圖2所示。通過歷史數(shù)據(jù)的模型特征提取建立預(yù)測樹，當(dāng)數(shù)據(jù)與預(yù)測模型不一致時進(jìn)行采樣頻率的更新調(diào)整。

圖 1 算法原理

圖 2 每個聚類內(nèi)集中式預(yù)測模型

但是預(yù)測模型與特定的應(yīng)用場景有著很強的相關(guān)性，而Weiner和Kalman濾波器等預(yù)測計算方法對傳感器節(jié)點而言過于復(fù)雜。本文中各個聚類中簇頭節(jié)點所采用的預(yù)測模型采用計算量較小的線性自回歸（Auto Regressive, AR）模型，并采用遞歸最小二乘（LS）估計方法進(jìn)行參數(shù)估計。如式（1）和式（2）所示：

其中 Xp[ n]是預(yù)測數(shù)據(jù)值，Xr[ n]是實測數(shù)據(jù)值，e[ n]是誤差值， ai[ n]是AR模型的各階系數(shù)。

2.2 數(shù)據(jù)相關(guān)性聚類機制

數(shù)據(jù)相關(guān)性聚類機制的主要思路是將數(shù)據(jù)相關(guān)度較強（體現(xiàn)為物理空間位置和數(shù)據(jù)均值較為接近）的傳感器節(jié)點歸在一個簇，每個聚類內(nèi)的傳感器節(jié)點進(jìn)行集中式的數(shù)據(jù)模型預(yù)測，簇頭節(jié)點負(fù)責(zé)維護(hù)每個聚類內(nèi)的數(shù)據(jù)預(yù)測模型，減低需傳輸?shù)娜哂鄶?shù)據(jù)，提高能量使用效率。每個傳感器節(jié)點成為簇頭節(jié)點的概率計算如下：節(jié)點以自身剩余能量和其一跳鄰居數(shù)（節(jié)點度數(shù)）的綜合權(quán)值作為最大概率值來實施簇頭節(jié)點的選舉，則最大概率值公式為

式（3）中p代表簇頭節(jié)點所占的比率， p ∈ （ 0,1]，實際上簇頭節(jié)點所占總節(jié)點數(shù)的上限比率一般設(shè)為20%，因此 p ∈ （ 0,0.2]; E （ i）是節(jié)點 Ni的剩余能量，Ni是節(jié)點 Ni的度數(shù)（包含自身）。

一旦傳感器節(jié)點被選舉為簇頭節(jié)點，立即在其一跳鄰居節(jié)點內(nèi)廣播簇頭標(biāo)志信息，誘導(dǎo)非簇頭節(jié)點加入自身簇。非簇頭節(jié)點選擇最優(yōu)簇頭節(jié)點的思想如下：選擇簇頭節(jié)點與簇成員節(jié)點之間數(shù)據(jù)梯度值最小的一跳鄰居簇頭作為簇頭節(jié)點。如圖3所示。

圖3 基于數(shù)據(jù)梯度的簇頭節(jié)點遴選示意圖

假設(shè)非簇頭節(jié)點CMi有4個簇頭節(jié)點（C H1,CH2, C H3, C H4）可供選擇，各個方向的數(shù)據(jù)梯度值如式（4）所示。這部分的研究可以參考作者已發(fā)表的會議論文[14]。

綜上所示，本文提出的聚類機制充分考慮了感知數(shù)據(jù)相關(guān)性以及傳感器節(jié)點空間位置，形成的簇分布能夠體現(xiàn)感知數(shù)據(jù)的空間關(guān)聯(lián)性。

2.3 數(shù)據(jù)預(yù)測模型及方法

根據(jù)平穩(wěn)數(shù)據(jù)預(yù)測精度和速度的需求，本文采用二階AR預(yù)測模型，預(yù)測值如式（6）如下：

其中 Xi為真實值，α和β為AR模型的參數(shù)，ei+1為預(yù)測誤差，X是W個歷史觀測數(shù)據(jù)的均值。對于給定的W個歷史數(shù)據(jù)，參數(shù)α和β可由樣本自相關(guān)函數(shù)計算得出。

而樣本自相關(guān)函數(shù)的計算可由式（8）得到：

可見，預(yù)測誤差可以由預(yù)測值和真實值之差得到：

本文中的數(shù)據(jù)預(yù)測模型沒有采用定期更新的機制，因為定期更新會引入不必要的更新次數(shù)，只有當(dāng)誤差大于一定閾值時才啟動重新計算二階AR系數(shù)的過程。AR模型參數(shù)估計采用了常用的Yule-Walker方程法[15]。

2.4 采樣頻率更新機制

采樣頻率的自適應(yīng)調(diào)整采用加增半減的方法來進(jìn)行調(diào)整：當(dāng)采樣誤差小于預(yù)設(shè)閾值時，減半聚類中各個傳感器的采樣頻率，否則增加采樣頻率，增加的步進(jìn)值為上限閾值和下限閾值的M分之一。最后限制調(diào)整過的采樣頻率在上限閾值和下限閾值范圍之內(nèi)。為了衡量誤差的精度，預(yù)測誤差采用了平均相對誤差 （Mean Relative Error, MRE）指標(biāo)來表征預(yù)測數(shù)據(jù)偏離實際數(shù)據(jù)的程度。

其中W為數(shù)據(jù)窗口長度，本文根據(jù)所采用數(shù)據(jù)集的采樣頻率屬性，各個參數(shù)值設(shè)置為

采樣頻率更新策略如表1所示。

表1 采樣頻率更新策略

2.5 頻率更新機制分析

采樣頻率的自適應(yīng)調(diào)整由各個聚類中的簇頭節(jié)點管理，簇頭節(jié)點在接收到采樣數(shù)據(jù)后將下一個采樣頻率附帶在確認(rèn)數(shù)據(jù)包中發(fā)送給各個簇成員節(jié)點。由于簇頭節(jié)點接收到感知數(shù)據(jù)后也會發(fā)送確認(rèn)數(shù)據(jù)包，因此采樣頻率的更新并不花費額外的通信負(fù)荷。各個聚類內(nèi)數(shù)據(jù)采集的頻率不一樣，但是簇頭節(jié)點可以通過模型預(yù)測的方法以統(tǒng)一的頻率將數(shù)據(jù)上傳到匯聚節(jié)點。

3 仿真

本文采用Berkeley大學(xué)的Intel實驗室[16]所做的真實采樣數(shù)據(jù)，這份數(shù)據(jù)來自于54個傳感器，有溫度、濕度、亮度以及電壓等讀數(shù)，大約每隔30 s從54個傳感器讀取一次數(shù)據(jù)，共有一個月的數(shù)據(jù)，本文仿真只采用了其中溫度值數(shù)據(jù)。本文定義了不同滑動窗口長度的數(shù)據(jù)序列相關(guān)性系數(shù)的量化公式：

式（11）中 Cuv是窗口長度為W 的數(shù)據(jù)序列 Du和 Dv的相關(guān)性系數(shù)，E（Du）和Var（Du）分別表示數(shù)據(jù)序列Du的均值和均方差。Cuv∈[-1 , 1]，其中 Cuv=-1代表數(shù)據(jù)序列 Du和 Dv負(fù)相關(guān)，Cuv= 0 代表數(shù)據(jù)序列Du和 Dv不相關(guān)， Cuv= 1 代表數(shù)據(jù)序列 Du和 Dv正相關(guān)。以一天數(shù)據(jù)量為窗口長度（W=1100），節(jié)點1與節(jié)點2的相關(guān)性系數(shù)為0.9393，節(jié)點1與節(jié)點16的相關(guān)性系數(shù)為0.7199，節(jié)點1與節(jié)點2的相關(guān)性明顯高于節(jié)點1與節(jié)點16的相關(guān)性系數(shù)。

當(dāng)簇頭比例分別為 p =0.05和p= 0 .15時，數(shù)據(jù)相關(guān)性聚類結(jié)果如圖4所示，不同聚類采用不同形狀的節(jié)點集表示，其中標(biāo)志節(jié)點號的為每個簇相應(yīng)的簇頭節(jié)點。

如圖5所示，可以看到節(jié)點1在2004年3月1日～3月6日的溫度數(shù)據(jù)變化趨勢在時間維度上傳感器節(jié)點的數(shù)據(jù)呈現(xiàn)很強的重復(fù)性，因為在時間維度上可以利用各個聚類內(nèi)傳感器節(jié)點采樣頻率的自適應(yīng)調(diào)整進(jìn)行網(wǎng)絡(luò)能耗優(yōu)化。當(dāng)采樣頻率分別為=1次/10min = 0 .1 ×Hz時，節(jié)點2在2004年3月1日的實測數(shù)據(jù)、預(yù)測數(shù)據(jù)和估計誤差分別如圖6所示。

假設(shè)節(jié)點能耗主要考慮由采樣過程所產(chǎn)生，因此網(wǎng)絡(luò)整體能耗體現(xiàn)在傳感器數(shù)據(jù)的采樣頻率上，數(shù)據(jù)采樣頻率越高，網(wǎng)絡(luò)能耗越大。在平均相對誤差θMRE=5%和簇頭比例 p = 0 .2的條件下，利用數(shù)據(jù)相關(guān)性聚類機制獲得的聚類劃分結(jié)果為 9個聚類，每個時刻所有聚類的采樣頻率平均值如圖7所示。由圖7可以發(fā)現(xiàn)，相比固定采樣頻率方式（采樣頻率為Th =1次/1min =1 ×Hz），本文提出的

圖4 數(shù)據(jù)相關(guān)性聚類劃分結(jié)果

圖5 節(jié)點1在不同天的溫度數(shù)據(jù)變化趨勢

圖6 AR預(yù)測誤差分析

4 結(jié)束語

圖7 采樣頻率自適應(yīng)調(diào)整值

本文利用無線傳感網(wǎng)的數(shù)據(jù)空間相關(guān)性，提出了一種基于數(shù)據(jù)梯度的聚類機制，簇頭節(jié)點維護(hù)簇成員節(jié)點的數(shù)據(jù)時間域AR預(yù)測模型，在聚類范圍內(nèi)實施基于預(yù)測模型的采樣頻率自適應(yīng)調(diào)整算法。通過自適應(yīng)優(yōu)化調(diào)整采樣頻率，提高無線傳感網(wǎng)的能耗水平：如果感知數(shù)據(jù)的動態(tài)性較高，提高采樣頻率從而保證采樣數(shù)據(jù)質(zhì)量，如果感知數(shù)據(jù)的動態(tài)性較低，僅僅發(fā)送那些必需發(fā)送的數(shù)據(jù)，降低采樣頻率以減少冗余數(shù)據(jù)的產(chǎn)生與傳輸。本文屬于一種考慮空間相關(guān)性的時間域采樣頻率調(diào)整算法，由于綜合考慮了感知數(shù)據(jù)的時空聯(lián)合相關(guān)性等特點，因此在提高能耗水平方面具有較大優(yōu)勢。

[1] Li J Z and Gao H. Survey on sensor network research[J].Journal of Computer Research and Development, 2008, 45（1）:1-15.

[2] 蔡文郁, 張美燕, 蔣一波. 基于時空聯(lián)合性的無線傳感網(wǎng)覆蓋采樣技術(shù)[J]. 傳感技術(shù)學(xué)報, 2013, 26（2）: 260-265.Cai Wen-yu, Zhang Mei-yan, and Jiang Yi-bo. Coverage sampling technology based on spatial temporal joint union for wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2013, 26（2）: 260-265.

[3] Deligiannakis A, Kotidis Y, and Roussopoulos N.Dissemination of compressed historical information in sensor networks[J]. The VLDB Journal, 2007, 16（4）: 439-461.

[4] Masoum A, Meratnia N, and Havinga P J M. An energy-efficient adaptive sampling scheme for wireless sensor networks[C]. The 8th IEEE International Conference on Intelligent Sensors, Sensor Networks and Information Processing, Melbourne, Australia, 2013: 231-236.

[5] Tulone D and Madden S. PAQ: time series forecasting for approximate query answering in sensor networks[C].Proceedings of the 3rd European conference for Wireless Sensor Networks （EWSN 2006）, Zurich, Swiss, 2006: 21-37.

[6] Sachidananda V, Khelil A, Noack D, et al.. Information quality aware co-design of sampling and transport in wireless sensor networks[C]. The 6th Joint IFIP Wireless and Mobile Networking Conference （WMNC 2013）, USA, 2013: 1-8.

[7] Zhou S W, Lin Y P, Zhang J M, et al.. A wavelet data compression algorithm using ring topology for wireless sensor networks[J]. Journal of Software, 2007, 18（3）: 669-680.

[8] Jain A and Chang E Y. Adaptive sampling for sensor networks[C]. Proceedings of the 1st International Workshop on Data Management for Sensor Networks （DMSN’04）,Toronto, Canada, 2004: 10-16.

[9] Li Jin-bao and Li Jian-zhong. Data sampling control,compression and query in sensor networks[J]. International Journal of Sensor Networks, 2007, 2（1）: 53-61.

[10] Aplippi C, Anastasi G, Francesco M D, et al.. An adaptive sampling algorithm for effective energy management in wireless sensor networks with energy-hungry sensors[J]. IEEE Transactions on Instrumentation and Measurement, 2010,59（2）: 335-344.

[11] Gedik B, Liu L, and Yu P S. ASAP: an adaptive sampling approach to data collection in sensor networks[J]. IEEE Transactions on Parallel Distributed Systems, 2007, 18（12）:1766-1783.

[12] Mukhopadhyay S, Schurgers C, Panigrahi D, et al..Model-based techniques for data reliability in wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2009,4（8）: 528-542.

[13] Qi Xin, Keally M, Zhou Gang, et al.. AdaSense: adapting sampling rates for activity recognition in body sensor networks[C]. IEEE 19th Real-Time and Embedded Technology and Applications Symposium （RTAS）,Philadelphia, USA, 2013: 163-172.

[14] Zhang Mei-yan, Cai Wen-yu, and Zhou Li-ping. A sensing data Ddriven clustering algorithm for adaptive sampling in wireless sensor networks[C]. 2012 International Applied Mechanics, Mechatronics Automation Synposium（IAMMAS2012）, Shenyang, China, 2012: 748-752.

[15] Da Silva S, Dias J Nior M and Lopes Junior V. Damage detection in a benchmark structure using AR-ARX models and statistical pattern recognition[J]. Journal of the Brazilian Society of Mechanical Sciences and Engineering, 2007, 29（2）:174-184.

[16] Samuel Madden: Intel Berkeley Research Lab[OL].http://www.intel-research.net/berkeley/index.asp. 2014.1.