基于回歸的傳感器網絡數據抑制方案

(南京大學 計算機科學與技術系 軟件新技術國家重點實驗室，南京 210093)

摘 要：提出了三種基于回歸模型的數據抑制方案：其中兩種利用了無線傳感器網絡中數據的時序相關性；另一種利用了感知數據的時序—地理位置相關性。模擬實驗表明，相對于簡單的數據抑制方案，基于回歸的數據抑制方案的通信代價更低。

關鍵詞：無線傳感器網絡; 回歸; 數據抑制； 近似查詢

中圖分類號：TP393 文獻標志碼：A

文章編號：10013695(2009)01025303

Regressionbased data suppression schemes in wireless sensor network

CAO Xuecheng，BAI Wenyang

(National Key Laboratory for Novel Software Technology， Dept. of Computer Science Technology， Nanjing University， Nanjing 210093， China)

Abstract:This paper proposed three data suppression schemes based on regression model， among which two were based on temporal correlation of data from sensor nodes，and the other one was based on spatial correlation of nearby sensors. Simulation experimental results show that， as regard to the communication cost，the methods perform better than the traditional one does.

Key words:wireless sensor network; regression; data suppression; approximate query

無線傳感器網絡可以深入到一些極端環境中去，避免了由人工監測所帶來的高風險和高成本。然而，傳感器節點由電池提供能源，很多場合中難以更換電池。怎樣減少網絡的能量消耗是一個重要問題。而減少網絡中能量消耗的關鍵是減少網內的通信[1]。在一個有n個節點的無線傳感器網絡中，如果每一個傳感器節點均有感知數據要傳送到網外，那么節點傳輸數據的吞吐量與1/sqrt(n)成正比[2]。所以，直接將感知數據發送到網外的方法可擴展性差，不適用于大規模的傳感器網絡，應盡量在生成數據的節點周圍進行分析處理，僅將信息含量高的數據傳送到網外。

為了減少網內通信量，TinyDB采用了網內數據聚集的方法[3，4]。因為傳感器上的感知數據不是精確的數據，所以還可以利用近似查詢技術，包括窗口查詢、直方圖、隨機采樣、小波和基于模型的方法。文獻[5]指出傳感器網絡中的數據具有三種相關性：a) 不同屬性的數據之間具有相關性，如傳感器節點的電壓與溫度有關；b)感知數據在時間序列上具有相關性，5 s前的溫度和現在的溫度很可能相差不大；c)地理位置的相關性，相鄰近的傳感器可能有相似的數據。可以利用數據間的這些相關性減少傳輸到網外的數據量。BBQ的是一個模型驅動的感知數據管理系統[6]。BBQ中數據的收集工作分成兩步：a)使用TinyDB收集訓練數據集，并利用它訓練出一個多系數高斯模型；b)利用該多系數高斯模型指導傳感器網絡中的數據收集工作。模型驅動可以減少網內通信代價，但是，當前數據可能并不完全符合歷史數據模型，而且BBQ不能發現網內的異常事件。Conch是一種簡單的、基于時序相關性和地理相關性的數據抑制方案[7]，通過數據抑制來減少通信量。文獻[7]提出用回歸模型來對傳感器網絡中的感知數據建模，文中按固定頻率將模型系數傳輸到網外，而沒有采用數據抑制策略，在用戶可接收偏差下抑制感知數據或模型系數傳輸到網外。

回歸分析是研究變量對一些自變量依賴關系的一種統計分析方法。本文基于傳感器網絡中感知數據的時間、地理相關性，在節點上和簇集上建立了數據的回歸預測模型，并利用該回歸模型抑制傳輸到網外的數據量。

1 網絡模型和數據抑制

為了便于下文討論，本文基于以下假設：

a)傳感器網絡N被用來獲取網絡中的某現象的觀測值X。整個傳感器網絡由一個匯集點sink和多個傳感器節點{N1，N2，…，Nn}組成。其中Ni表示傳感器節點i。

b)所有傳感器節點的能量均是有限的。

c)每個節點按照指定的頻率f收集感知數據。

d)每個傳感器節點Ni都知道自己的位置〈xi，yi〉。節點之間、節點與sink節點之間保持時間同步。

e)傳感器節點的位置不會發生改變。Sink節點知道每個節點的位置（或假設可以通過其他定位協議獲得）。

f)用戶可接收的數據偏差為ε。

定義1 數據抑制方案是由數據抑制鏈構成的圖型結構。每一條抑制鏈均對應了一個數據更新點（updater）和一個數據觀察點（observer）。

更新節點與觀察節點之間同步地維護著一個變量X，Xt為t時刻更新點上產生的變量X的值，X∧t為t時刻觀察點認為X所具有的值。Sink節點是所有傳感器節點的直接或間接觀察點。Xt和X∧t間需要滿足一定的同步關系，其偏差需要在用戶指定的可接收偏差范圍ε內。

定義2 判定函數g(Xt，X∧t)是一個布爾函數，用于判斷X∧t與Xt之間的偏差是否在ε內，如式(1)所示。

g(Xt，X∧t)=1 如果|X∧t-Xt|≤ε0其他(1)

當g(Xt，X∧t)為真，表明Xt和X∧t滿足同步要求，更新點無須向觀察點發送額外的數據；g(Xt，X∧t)非真時，更新點要將最新狀態γ告訴觀察點。

定義3 為了保持更新點和觀察點數據同步要求，當判定函數不成立時，更新點根據Xt值產生最新狀態γ的方法叫做編碼函數fenc。γ的計算方法如式(2)所示。

γ=fenc(Xt，Xt-1，…，X1) 如果g(Xt，X∧t)非真

其他(2)

定義4 更新點從最新狀態信息γ中得到滿足同步關系的X∧t的函數稱為解碼函數fdec。X∧t的計算方法如式(3)所示。

X∧t=fdec(，X∧t-1，X∧t-2，…，X∧1) 如果γ=

fdec(γ，X∧t-1，X∧t-2，…，X∧1)其他(3)

2 基于時序相關性的數據抑制

無線傳感器網絡中的感知數據具有時序相關性。如果感知數據變化緩慢，則無須按很高的頻率來收集網絡中的感知數據。同樣，如果sink節點能夠很好地了解每個節點上感知數據與時間的相關性，也無須將所有感知數據傳輸到sink節點上。

歷史感知數據與時間之間有什么樣的相關性，以及判斷當前是否仍然保持這種相關性，是研究基于時序相關性數據抑制方案的關鍵問題。在簡單的基于時序相關性的數據抑制方案中，收到節點Ni傳出的最新狀態信息γ之前，sink節點認為Ni上的感知數據與上次感知數據的估計值相同[7]，即X∧t=fdec(，X∧t-1，X∧t-2，…，X∧1)=X∧t-1。這種簡單的時序相關性數據抑制方案在感知數據變化緩慢的條件下能工作得很好；但當感知數據變化快速且有規律時并不適用。為此，本文提出了兩種基于回歸的時序數據抑制方案。

設傳感器網絡N的拓撲結構如圖1所示。傳感器節點Ni在t時刻產生了感知數據Xt，i，sink節點對其觀測值為X∧t，i。由于傳感器節點上感知數據與其產生的時間是相關的，Ni用一組給定的基本函數{h1，i(t)，h2，i(t)， …，hk，i(t)}來擬合其感知數據{Xt-1，i，Xt-2，i， …，Xt-m，i}，也就是說尋找一個基本函數系數向量組ωi=(ω1，i，ω2，i，…，ωm，i)T使

X∧t，i=jωj，ihj，i(t)(4)

Sink節點保存了ωi的副本ω′i，即sink在沒有收到來自Ni的最新狀態信息γi時，會用ω′i估算Xt，i。而Ni用判定函數g(Xt，i，X∧t，i)判斷是否需要向sink發送γi

g(Xt，i，X∧t，i)=1如果|jω′j，ihj，i(t)-Xt，i|≤ε

0其他(5)

如果g(Xt，i，X∧t，i)為真，則Ni無須向sink節點發送最新狀態信息γi；否則，Ni重新計算出ωi，并將ωi作為最新狀態信息發送給sink節點，如式(6)所示。

通過選擇不同的基本函數組，本文給出了兩種基于回歸的時序數據抑制方案：

a)基于簡單線性回歸的時序數據抑制方案，基本函數組為{1，t}，即X∧t，i=ω1，i+ω2，i*t。b)基于二項回歸的時序數據抑制方案，基本函數為{1，t，t2}，即X∧t，i=ω0，i+ω1，i*t+ω2，i*t2。 3 基于時序—地理相關性的數據抑制

除了時序相關性外，傳感器網絡中產生的感知數據還具有地理相關性。相鄰的節點產生的感知數據一般來說比較相近。在簡單的地理相關數據抑制方案中，傳感器節點根據地理相關性劃分成多個簇，每個簇包含多個普通節點和一個簇頭節點。初始條件下，sink節點知道所有簇頭節點的感知數據值，并且知道其他普通節點與它們所屬簇的簇頭節點之間的數據之差。t時刻，在收到節點Ni傳出的最新狀態信息γi之前，sink節點認為Ni的簇頭節點和Ni上的感知數據差距保持不變；簇頭節點需要定時將最新狀態信息傳送給sink[8]。簡單地認為簇頭節點與普通節點之間感知數據差值不變的方案，適合整個簇內節點感知數據變化一致的情況，本文提出一種基于回歸的地理相關數據抑制方案，來描述簇內節點之間數據相關性。為了利用地理相關性，如圖2所示，本文將傳感器網絡中的節點劃分成多個簇。每個簇由多個相鄰的傳感器構成。其中一個稱為簇頭節點，剩下的稱為普通節點。每個簇頭節點均維護了該簇內其他節點的數據分布的模型。當模型改變時，簇頭節點將更新后的模型發送到sink節點。Sink節點上維護了所有簇的數據模型。

每個簇內，傳感器節點上產生的感知數據與該節點的位置和數據產生的時間是相關的。節點Ni（坐標〈xi，yi〉）t時刻產生的數據可用f(t，xi，yi)表示。t時刻，簇頭節點已經收到簇內其他普通節點前m個時間點的數據{f(t-1)，xi，yi)，f(t-2，xi，yi)，…，f(t-m，xi，yi)，…}。用一組給定的基本函數{h1(t，xi，yi)，h2(t，xi，yi)， …，hk(t，xi，yi)}來擬合f(t，xi，yi)。也就是說找到一個基本函數系數向量組ω=(ω1，ω2，…，ωm)T使

f^(t，xi，yi)=jωj×hj(t，xi，yi)(15)

Sink節點上保存著ω的副本。Ni將感知數據Xt發送到其簇頭節點上。簇頭節點用判定函數g(Xt，X∧t)判斷是否需要將其最新狀態γ傳遞到sink節點上，再根據f∧(t，xi，yi)對整個簇內最新感知數據的擬合程度好壞決定是否需要訓練出新的ω。如果需要重新訓練ω，將新訓練的也發送給sink。

g(X，X∧t)=1如果|f^(t，xi，yi)-f(t，xi，yi)|≤ε

0其他（16）

具體ω的求解過程與時序相關性抑制相似，這里不再贅述。本文將給定的基本函數定義為{1，t， x， y}，即f∧(t)=ω1+ω2*ti+ω3*xi+ω4*yi。

4 實驗

模擬實驗采用了IntelBerkeley Research的數據集，使用TOSSIM［11］模擬傳感器網絡。網絡中部署了54個傳感器節點，每隔一定時間收集一次光強、溫度、濕度和電壓信息（本文只利用了溫度信息）。

圖3是獲取的1號傳感器節點從2004228，18:00:00到2004229，6:00:00這12 h內溫度隨時間的變化數據，可以看出這段時間內溫度與時間基本上成線性變化。

圖4為鄰近的1號和2號傳感器在同一天(2004229)中溫度數據隨時間變化情況。可以看出兩個節點的感知數據具有一定的相關性。

圖5展現了20 D內不同數據抑制方案耗費的網內消息量。可以看出：基于簡單線性回歸、二項回歸和多元線性回歸、簡單時序相關性數據抑制方案具有較好的效果。簡單線性回歸、二項回歸的時序數據抑制方案效果基本一致，均比簡單時序性數據抑制方案減少了6%左右的消息量；而基于多元線性回歸的地理位置相關性數據抑制方案則明顯好于簡單地理相關性數據抑制方案，減少了50%左右的消息量。原因為，實驗中溫度隨時間變化緩慢，而簡單地理位置相關性方案中，簇頭節點要一直將數據發送到sink節點上。如果在數據變化更快的環境中，基于回歸的數據抑制方案應該會有更好的效果。

圖6是采用簡單線性回歸數據抑制方案下，用戶指定可接受的查詢結果偏差范圍分別是0.05、0.1、0.2、0.5和1.0°，20 D中網內消息數變化情況。可以看出用戶指定的可接受偏差越大，網內消息數越少。

5 結束語

很多應用場景下，用戶只需要收集原始感知數據，直接執行“SELECT * FROM SENSORS”形式的連續查詢語句。數據抑制是支持在連續查詢時不用連續地報告網內感知數據的關鍵技術。本文提出利用傳感器網絡中感知數據的時間、地理相關性，在節點本身和節點簇集上建立感知數據的回歸預測模型，并利用該回歸模型抑制傳輸到sink點的數據量，提出了兩種基于數據時序相關性的回歸抑制方案和一種基于時序—地理位置相關性的回歸抑制方案。模擬實驗表明，相對于簡單地利用時間、地理相關性的數據抑制方案，基于回歸模型的數據抑制方案更能減少網內通信量。不同的時間段，感知數據的分布模型可能不同，筆者將繼續研究自適應的多模型數據抑制方案。



參考文獻：

［1］

李建中， 李金寶， 石勝飛.傳感器網絡及其數據管理的概念、問題與進展[J].軟件學報:2003，14(10):17171727.

［2］LI Jinyang，BLAKEC，COUTO D S J de，et al.Capacity of Ad hoc wireless networks[C]//Proc of the 7th ACM International Conference on Mobile Computing and Networking.New York:ACM，2001.

［3］MADDEN S，FRANKLIN M J，HELLERSTEIN J M，et al.TinyDB:an acqusitional query processing system for sensor networks[J].ACM Trans on Database Systems，2005，30(1):122173.

［4］MADDENS，FRANKLIN M J，HELLERSTEIN J M.The design of an acquisitional query processor for sensor networks[C]//Proc of ACM SIGMOD.New York:ACM，2003.

［5］DESHPANDE A，GUESTRIN C，WEI Hong，et al.Exploiting correlated attributes in acquisitional query processing[C]//Proc of the 21st International Conference on Data Engineering.Washington DC:IEEE Computer Society，2005.

［6］DESHPANDE A， GUESTRIN C，MADDEN S.Modeldriven data acquisition in sensor networks[C]//Proc of the 30th International Conference on Very Large Data Bases(VLDB).Toronto，PA:VLDB Endowment， 2005.

［7］GUESTRIN C，BODIK P，THIBAUX R，et al.Distributed regression: an efficient framework for modeling sensor network data[C]//Proc of Information Processing in Sensor Networks.New York:ACM， 2004.

［8］SILLBERSTEIN A，BRAYNARD R，FILPUS G，et al.Datadriven processing in sensor networks[C]//Proc of CIDR.2007.

［9］WEISBERG S.Applied linear regression[M].Hoboken:Wiley，2004.

［10］張勇，王國明，趙秀珍.應用線性回歸模型[M].北京:中國統計出版社， 1990.

［11］LEVIS P， LEE N， WELSH M，et al.TOSSIM:Accurate and scalable simulation of entire TinyOS applications[C]//Proc of the 1st ACM Conference on Embedded Networked Sensor Systems.New York: ACM， 2003.