陳園園,朱欣穎

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是集傳感器技術(shù)、嵌入式計(jì)算技術(shù)、分布式信息處理技術(shù)和無線通信技術(shù)為一體,由一系列帶有無線射頻發(fā)射模塊和數(shù)據(jù)感知模塊的無線傳感器節(jié)點(diǎn)組成的無線網(wǎng)絡(luò)系統(tǒng).無線傳感器網(wǎng)絡(luò)技術(shù)具有多學(xué)科融合的知識特點(diǎn),被廣泛的應(yīng)用在軍事、醫(yī)療等諸多領(lǐng)域.但在實(shí)際的應(yīng)用過程中,無線傳感器網(wǎng)絡(luò)的能量和帶寬有限,難以滿足數(shù)據(jù)傳輸?shù)男枨?有研究指出,數(shù)據(jù)通信的能耗遠(yuǎn)高于數(shù)據(jù)計(jì)算的能耗,數(shù)據(jù)傳輸消耗了總能量的70%[1].如果不對這些數(shù)據(jù)進(jìn)行處理,則網(wǎng)絡(luò)通信開銷巨大,將消耗大量的節(jié)點(diǎn)能量.如何有效地減少網(wǎng)絡(luò)內(nèi)部的數(shù)據(jù)量,從而降低網(wǎng)絡(luò)能量消耗是人們面臨的一個(gè)重要挑戰(zhàn).

為了適應(yīng)WSN的應(yīng)用而產(chǎn)生了數(shù)據(jù)融合技術(shù),它主要關(guān)注如何有效的對采集或接收到的其他傳感器節(jié)點(diǎn)發(fā)送的大量數(shù)據(jù)進(jìn)行融合處理,重點(diǎn)在于減少需要傳輸?shù)臄?shù)據(jù).在無線傳感器網(wǎng)絡(luò)中,數(shù)據(jù)融合技術(shù)利用節(jié)點(diǎn)的本地計(jì)算和存儲能力進(jìn)行數(shù)據(jù)融合,去除冗余信息,減少通信過程中的數(shù)據(jù)量.數(shù)據(jù)融合技術(shù)可以與傳感器網(wǎng)絡(luò)的多個(gè)協(xié)議層結(jié)合,已經(jīng)在目標(biāo)跟蹤、目標(biāo)自動(dòng)識別等領(lǐng)域得到了廣泛應(yīng)用.

目前,數(shù)據(jù)融合技術(shù)的多數(shù)研究主要集中在如何利用節(jié)點(diǎn)之間的時(shí)空相關(guān)性,來節(jié)省能量的傳輸數(shù)據(jù).文獻(xiàn)[2]提出了一種小波壓縮算法,該算法依據(jù)傳感數(shù)據(jù)的時(shí)間相關(guān)性和節(jié)點(diǎn)可用通信帶寬選擇待傳輸?shù)男〔ㄏ禂?shù)、確定量化位和編碼方法,能夠在允許的誤差范圍內(nèi)控制輸出的數(shù)據(jù)量.文獻(xiàn)[3]利用傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的空間相關(guān)性,用一部分節(jié)點(diǎn)的監(jiān)測值來推算另一部分節(jié)點(diǎn)的監(jiān)測值,通過相關(guān)節(jié)點(diǎn)的輪流工作和休眠來節(jié)省能量.文獻(xiàn)[4]基于小波變換提出了一種漸進(jìn)數(shù)據(jù)壓縮算法,根據(jù)感知數(shù)據(jù)的空間相關(guān)性來選擇傳送數(shù)據(jù)的傳感器節(jié)點(diǎn),使得漸進(jìn)傳送的數(shù)據(jù)單元能產(chǎn)生大的編碼增益,取得較高的壓縮效率,減少了網(wǎng)絡(luò)能耗.文獻(xiàn)[5]中提到感知數(shù)據(jù)在傳輸過程中基于層次簇的方法進(jìn)行數(shù)據(jù)壓縮,減少網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量,從而節(jié)省了能量.

以上文獻(xiàn)提到的算法并不適用于節(jié)點(diǎn)監(jiān)測值直接不存在時(shí)空相關(guān)性或相關(guān)性不穩(wěn)定的情況,因此筆者提出一種新的算法:基于三次B樣條插值的擬合算法.該算法通過在傳感器節(jié)點(diǎn)上對采集的數(shù)據(jù)進(jìn)行模型擬合,來達(dá)到壓縮數(shù)據(jù),減少網(wǎng)絡(luò)中數(shù)據(jù)傳輸量,從而減少網(wǎng)絡(luò)數(shù)據(jù)傳輸能耗之目的.

1 模型建立

首先將傳感器節(jié)點(diǎn)的監(jiān)測數(shù)據(jù)組織成一個(gè)感知數(shù)據(jù)序列,然后在該感知數(shù)據(jù)序列上尋找具有最小數(shù)據(jù)傳輸比的擬合模型.

如圖1所示為基于擬合模型的算法流程圖.

第一步:數(shù)據(jù)集是由監(jiān)測區(qū)域的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)采集.

第二步:無線傳感器網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)數(shù)據(jù)緩存至本地節(jié)點(diǎn)的存儲器內(nèi).

第三步:當(dāng)存儲器內(nèi)的監(jiān)測數(shù)據(jù)集達(dá)到一個(gè)給定的閥值時(shí),依據(jù)樣條插值算法對數(shù)據(jù)進(jìn)行擬合處理.

第四步:找到一個(gè)最佳模型M,然后把模型M及其參數(shù)傳回給匯聚節(jié)點(diǎn).

圖1 基于擬合模型的算法流程圖

2 樣條方法

在遇到一組給定的離散有序樣本點(diǎn)時(shí),經(jīng)常用線段將它們光滑的連接起來進(jìn)行曲線擬合,WSN中的感知數(shù)據(jù)剛好符合這些特點(diǎn).曲線擬合的方法很多,其中B樣條曲線是連續(xù)的且不用通過每個(gè)樣本點(diǎn),比貝塞爾曲線更加光滑,另外B樣條函數(shù)在做曲線擬合的時(shí)候如果一個(gè)樣本點(diǎn)改變了,也僅僅影響到附近的一段曲線而不是整條曲線,比其他擬合方法更加有效[6].

樣條即一類分段(片)光滑并且在各段交接處也有一定光滑性的函數(shù),可克服高次多項(xiàng)式插值出現(xiàn)的振蕩現(xiàn)象,具有良好的數(shù)值穩(wěn)定性和收斂性.它既保持了多項(xiàng)式的簡單性質(zhì)和逼近的可行性,又在各段之間保持了相對獨(dú)立的局部性質(zhì).因此樣條是一類特別有效的逼近工具.設(shè)給定一組結(jié)點(diǎn):

又設(shè)分段函數(shù)S(x)滿足條件:

(1)在每個(gè)區(qū)間[xj,xj+1](j=0,…,N)上,S(x)為次數(shù)不超n的實(shí)系數(shù)代數(shù)多項(xiàng)式;

(2)S(x)在(-∞,+∞)上有直到n-1階的連續(xù)導(dǎo)數(shù).

則稱y=s(x)為n次樣條函數(shù).常把以(1)式為結(jié)點(diǎn)的n次樣條函數(shù)的總體記為Sn(x1,x2,…,xN-1,xN),x1,x2,…,xN-1,xN稱為樣條節(jié)點(diǎn).

B樣條曲線是由一組基函數(shù)和一些控制頂點(diǎn)定義.其中三次B樣條應(yīng)用最廣,三次B樣條的基函數(shù)可以表述為下列形式:

設(shè)有n+1個(gè)感知數(shù)據(jù)點(diǎn)p0,p1,…,pn,每四個(gè)相鄰的點(diǎn)可以構(gòu)造一段三次B樣條曲線,例如pi,pi+1,pi+2,pi+3這四個(gè)點(diǎn)決定的三次B樣條曲線的表達(dá)式為:

變換成矩陣形式為:

其中1≤i≤n-3,參數(shù)u∈[0,1]

這n-3段三次拋物線就光滑的拼接成了一條完整的三次B樣條曲線.

假設(shè){a=t0＜t1＜…＜tN=b}為N+1個(gè)節(jié)點(diǎn),令

再設(shè)以U為節(jié)點(diǎn)向量的參數(shù)三次B樣條曲線滿足容差要求,由于t0=a,tN=b,設(shè)r={r1,r2,…,rN-1},0＜ri＜1,i=1,2,…,N-1,那么,

整理得對角占優(yōu)的三對角線

將樣條節(jié)點(diǎn)的分布問題轉(zhuǎn)化為(5)式中三對角矩陣的構(gòu)造問題上來,顯然,如果r={r1,r2,…,rN-1}選擇得當(dāng),將其代入方程組(6)中很容易用追趕法求得內(nèi)節(jié)點(diǎn){t1,…,tN-1},容易看出,用參數(shù)的三次B樣條曲線插值能夠很好的逼近給定數(shù)據(jù)點(diǎn).

3 基于樣條的BFM算法

數(shù)據(jù)擬合被分為多項(xiàng)式插值和樣條插值[7],要擬合無線傳感器采集到的大量數(shù)據(jù),樣條插值比多項(xiàng)式插值的效果要好很多.

圖2 多項(xiàng)式插值與樣條插值擬合比較圖

圖3 B樣條曲線擬合模型圖

如圖2所示,取sin函數(shù)部分值為一觀測序列,分別用多項(xiàng)式和B樣條進(jìn)行擬合逼近,圖中藍(lán)色曲線為B樣條插值擬合結(jié)果,紅色曲線為分段多項(xiàng)式插值擬合結(jié)果,明顯看到紅色曲線有空隙而藍(lán)色幾乎看不到空隙,藍(lán)色的曲線比紅色曲線逼近程度要高,所以B樣條插值擬合效果更好.圖3顯示了B樣條曲線擬合模型,圖中繪出了各個(gè)控制點(diǎn),光滑的曲線就是由這些控制點(diǎn)形成的.

BFM算法設(shè)計(jì)思想:結(jié)合擬合模型算法,為使數(shù)據(jù)序列能夠得到更逼近的曲線擬合,筆者采用三次B樣條曲線擬合模型,在選取的數(shù)據(jù)序列上建立擬合模型,根據(jù)三次B樣條曲線的理論知識,筆者的數(shù)據(jù)序列上的每四個(gè)數(shù)據(jù)點(diǎn)都可以形成一段光滑的三次B樣條曲線,進(jìn)而擬合所有的數(shù)據(jù)點(diǎn),得到最佳擬合模型傳送給匯聚節(jié)點(diǎn),未被擬合的數(shù)據(jù)直接傳送給匯聚節(jié)點(diǎn).

基于樣條擬合模型BFM算法問題定義如下:

設(shè)傳感器節(jié)點(diǎn)采集的單一屬性數(shù)據(jù)量為N,屬性種類為k,則共有N×k個(gè)數(shù)據(jù)點(diǎn),選擇B樣條曲線擬合次數(shù)為三次,稱未被擬合的數(shù)據(jù)為奇異點(diǎn).

對長度為N的數(shù)據(jù)序列y1,y2,…,yN,每四個(gè)點(diǎn)yi,yi+1,yi+2,yi+3,i∈[1,N]決定一段三次B樣條曲線,根據(jù)前面三次樣條基函數(shù)表達(dá)式(2),則一段三次B樣條曲線的表達(dá)式為

根據(jù)系數(shù)矩陣可得

這N-2段三次樣條曲線就構(gòu)成了一段完整光滑的樣條曲線.被擬合的基函數(shù)數(shù)目為k.其中

最終擬合模型中的序列^y為原始序列y的近似序列,殘差平方和為

4 仿真結(jié)果與分析

本實(shí)驗(yàn)仿真采用兩個(gè)數(shù)據(jù)集,其中一個(gè)數(shù)據(jù)集是英特爾伯克利實(shí)驗(yàn)室已采集的各屬性監(jiān)測值[8],是由54個(gè)mica2傳感器節(jié)點(diǎn)在36 d內(nèi)每31 s一次收集的監(jiān)測數(shù)據(jù),數(shù)據(jù)收集在Tiny DB網(wǎng)絡(luò)查詢處理系統(tǒng)中完成,系統(tǒng)是建立在Tiny OS平臺上,數(shù)據(jù)類型包含了溫度、濕度和光照電壓值.另一個(gè)是由韓伯電子開發(fā)的ZigbeX無線傳感器采集的真實(shí)數(shù)據(jù),該無線傳感器模塊內(nèi)含傳感器節(jié)點(diǎn)10個(gè),能夠獲得一個(gè)月內(nèi)所產(chǎn)生的監(jiān)測數(shù)據(jù),這些數(shù)據(jù)分別是對濕度、溫度和光照進(jìn)行的采樣.實(shí)時(shí)采樣的串口通信軟件參數(shù)設(shè)置為:端口連接COM3,波特率為57 600,數(shù)據(jù)位為8,停止位為1,數(shù)據(jù)緩存位置為D:CO MDATA,數(shù)據(jù)保存形式為十進(jìn)制.

有研究指出,無線傳感器網(wǎng)絡(luò)的監(jiān)測數(shù)據(jù)隨時(shí)間呈周期性連續(xù)變化,而且在許多應(yīng)用中的數(shù)據(jù)也有類似變化規(guī)律[9],為了減少數(shù)據(jù)冗余,減少數(shù)據(jù)傳輸能耗,筆者采用BFM算法最大限度的擬合監(jiān)測數(shù)據(jù)的這種變化趨勢.

WSN中的數(shù)據(jù)并不需要非常精確或者完備,只需它在一個(gè)允許的誤差范圍內(nèi)即可,因此,為降低網(wǎng)絡(luò)通信能耗可以在減少數(shù)據(jù)冗余和降低數(shù)據(jù)量的時(shí)候損失一些數(shù)據(jù)精度.

常用的數(shù)據(jù)壓縮算法性能指標(biāo)有:傳輸比(Transmission Ratio,TR)

其中,S(x)是壓縮后的數(shù)據(jù)序列,S原(x)是原始未被壓縮的數(shù)據(jù)序列.傳輸比與壓縮后數(shù)據(jù)成正比,傳輸比TR越小,壓縮后的數(shù)據(jù)越少,說明傳輸?shù)臄?shù)據(jù)量越小,則通信能量消耗就越小.

另一個(gè)性能指標(biāo)是殘差平方和(Sum of Squares for Error,SE)

其中,n代表輸入的數(shù)據(jù)序列長度,S(x)是壓縮后的數(shù)據(jù)序列,S原(x)是原始未被壓縮的數(shù)據(jù)序列.

用C++實(shí)現(xiàn)了三次B樣條自適應(yīng)算法,并在監(jiān)測數(shù)據(jù)集上對其性能進(jìn)行了測試.

表1和表2分別對用戶的誤差容忍度、節(jié)點(diǎn)的存儲容量等方面對節(jié)點(diǎn)的數(shù)據(jù)傳輸量進(jìn)行了對比.溫度的一般誤差容忍度是0.5,濕度的誤差容忍度是2%,根據(jù)節(jié)點(diǎn)的存儲能力,設(shè)定節(jié)點(diǎn)的存儲容量在200-500內(nèi)變動(dòng).從表1中可以看出整體的SE還是很小,隨著允許容錯(cuò)的增大,SE也變大了,因?yàn)樵试S的誤差范圍越大,能夠被擬合的數(shù)據(jù)相對就減少了,擬合數(shù)據(jù)與原始數(shù)據(jù)的方差會(huì)變大,那么殘差也會(huì)相應(yīng)的變大.在表2中顯示的一組溫度數(shù)據(jù)在不同節(jié)點(diǎn)容量下的SE,可以看出隨著節(jié)點(diǎn)容量的增多,SE也逐漸增大.

表1 一組溫度數(shù)據(jù)在不同容錯(cuò)下的SE

表2 一組溫度數(shù)據(jù)在不同節(jié)點(diǎn)容量下的SE

目前,在節(jié)點(diǎn)不具有時(shí)空相關(guān)性的情況下,一個(gè)傳統(tǒng)的檢測數(shù)據(jù)采集策略是加州大學(xué)伯克利分校的Tiny DB,該策略是向sink節(jié)點(diǎn)傳送所有監(jiān)測數(shù)據(jù).而筆者的策略是僅傳回一個(gè)最佳擬合模型M.

圖4中,顯示了Tiny DB策略和BFM算法在不同容錯(cuò)下的室內(nèi)、室外溫度數(shù)據(jù)傳輸率,橫坐標(biāo)代表允許的誤差,縱坐標(biāo)代表傳輸率.雖然筆者的算法丟失了部分精度,但是并不影響算法的性能.從圖中也很明顯的看到,BFM算法的傳輸率比Tiny DB策略高很多.

圖4 不同容錯(cuò)下數(shù)據(jù)傳輸比

5 結(jié)論

針對無線傳感器網(wǎng)絡(luò)能源有限且難以補(bǔ)充的特點(diǎn),提出了一種基于三次B樣條插值的BMF算法,該算法通過傳輸模型及其參數(shù)來代替?zhèn)鬏攲?shí)際的監(jiān)測值,以達(dá)到壓縮數(shù)據(jù),減少數(shù)據(jù)傳輸量的目的.且筆者給出的算法能夠保證在一定的誤差容忍范圍內(nèi)有可靠的置信度.由于該算法不依賴數(shù)據(jù)的時(shí)空相關(guān)性,因此在節(jié)點(diǎn)的監(jiān)測值之間不存在時(shí)間相關(guān)性或相關(guān)性較低時(shí),仍可以發(fā)揮原有的性能,使得該算法具有更廣闊的應(yīng)用范圍和空間.

參考文獻(xiàn):

[1]Kimura N,Latifi S.A survey on data compression in wireless sensor networks[J].Proc of the Int’l Conf on Information Technology:Coding and Computing.Piscataway:IEEE Press,2005(2):8-13.

[2]Chen Huamin,Li Jian,Mohapatra P.RACE:Time Series Compression with Rate Adaptivity and Error Bound for Sensor Networks[C]//Proc.of IEEE International Conference on Mobile Ad-hoc and Sensor Systems.[S.1.]:IEEE Press,2004.

[3]Q Cao,T Abdelzaher,T He,et al.Towards optimal sleep scheduling in sensor networks for rare event detection[C]//Information Processing in Sensor Networks,Los Angeles,USA,2005.

[4]周四望,林亞平,葉松濤,等.傳感器網(wǎng)絡(luò)中一種存儲有效的小波漸進(jìn)數(shù)據(jù)壓縮算法[J].計(jì)算機(jī)研究與發(fā)展,2009,46(12):2085-2092.

[5]賀智勇,龍陳鋒,王桐森,等.傳感器網(wǎng)絡(luò)中層次簇模型數(shù)據(jù)壓縮算法[J].計(jì)算機(jī)工程,2009,35(13):105-108.

[6]戴仕全.自適應(yīng)三次樣條插值逼近算法研究[D].大連:大連理工大學(xué),2008.

[7]李慶陽,王能超,易大義.數(shù)值分析[M].北京:清華大學(xué)出版社,2008:25-28.

[8]MaddenS.Intel Berkeley research lab data[EB/OL].(2003).http//berkeleyi.ntel-research.net/labdata.

[9]G Tolle,Sonoma redwoods data[OL],http//www.cs.berkeley.edu/～get/sonoma,2005.