傳感器網絡中基于一致性容差的聚合技術研究

程文靜

摘 要 在傳感器網絡中，通信成本占據了主導地位。因此，如何在滿足數據質量的前提下盡可能地減少數據傳輸是降低能耗的有效途徑。本文介紹了一種利用用戶對傳感器讀數變化的容忍度來減少“微變化”數據的傳輸，還可以在并非所有傳感器讀數都能在給定的時間限制內在網絡中傳播時保證一定的數據質量。

關鍵詞 傳感器網絡;時間一致性;網絡聚合

1網絡聚合模型

傳感器網絡中的查詢是連續的，會周期性地產生新的結果。初始時，基站接收一個查詢，然后轉發到最近的傳感器節點。此節點將負責將查詢分發到網絡上并收集結果。TAG[1]（TinyDB的聚合服務）在普通的SQL查詢中引入了新的子句EPOCH DURATION i。參數i是時間周期，它指定了用戶需要的新結果的到達速率。也就是說，對間隔每一個時間周期i，用戶都期望網絡對提出的連續查詢產生一個新的答案。而在本文介紹的基于時間的一致性容差的網絡聚合方案中，引入了VALUES WITHIN tct子句來表示一致性容忍度。

執行網絡聚合的方式取決于查詢的屬性和聚合謂詞。具體來說，group by查詢中的屬性列表將同一個屬性值的查詢結果分為一組。這些組的數目等于屬性列表不同值的個數。來自兩個不同傳感器的兩個讀數只有屬于同一組時才會被聚合。聚合函數決定了部分聚合的結構和部分聚合過程。例如，對于聚合函數SUM來說，傳感器生成的部分聚合只包括通過該傳感器轉發的所有讀數的總和。但是，如果聚合函數為AVERAGE，則每個路由傳感器生成的部分聚合包括所有的讀數之和讀數的個數。最終，根傳感器將使用總和和個數來計算每個組的平均值，然后將其轉發到基站以進行進一步的處理和轉發。

對于路由，我們使用一般的定向擴散方式，其目的是構建一棵路由樹，并在此過程中給其中每個傳感器指定一個父節點。例如傳感器c希望把一條消息廣播給全網，那么它先把這條消息發送給它的父節點，然后再繼續向下傳播。為了構建路由樹，需要為每個傳感器i分配一個級別Li和一個父節點Pi。在初始狀態下對于所有節點來說，Li=∞，Pi=0。啟動查詢的根節點會將自己的級別Lroot設置為0。各個節點通過交換查詢消息以構建路由樹。這樣的消息頭包含兩個字段：ids和Ls。ids是發送消息的源節點的標識符，Ls是該源節點的級別值（即Li）。當某個子節點接收到查詢消息且其當前級別為∞時，它會將收聽到的這個節點設置為其父節點，并將自己的級別設置為Ls+1。該過程將持續下去，直到網絡中的每個節點都收到查詢消息的副本，并被分配一個級別和一個父節點。

對于到達根節點只有單一路徑的路由樹來說，在節點上如何實現同步傳輸，對于高效的網絡聚合至關重要。父節點必須持續等待，直到聽到從其所有子節點報告的讀數后才能報告自己的讀數。因此，父節點p能夠將其子節點報告的部分聚集結果與其自身的讀數相結合。然后節點p可以發送一條消息，包含了在根植于p的子樹上采樣的所有值的部分聚合結果。

TAG中的同步是通過讓父節點在報告自己的讀數之前等待一定的時間間隔來完成的。具體來說，TAG將一個查詢周期細分為較短的時間片，時間片數等于路由樹的最大深度d，每個時間片的長度為（EPOCH DURATION）/d，其中EPOCH DURATION為一個周期的時長。在一個時間片內，父節點將處于活動狀態，并從其子節點接收消息。在下一個時間片內，其子節點將處于空閑狀態，而父節點仍處于活動狀態，并向其上一級節點傳輸部分聚合的結果。父傳感器將在隨后的時間片內（即當它完成接收和傳輸其子樹中的部分聚合數據后）會變進入空閑狀態。

本文介紹的方案可以和任何同步方法結合工作。在本文中，我們將使用TAG方法實現同步。此方法的優點是保證了查詢結果在每一個時間片內都能被傳遞，并且確保了每一個傳感器消耗最少能量。能夠實現消耗的能量最小化是因為每一個傳感器在一個周期中只需要在兩個時間片內處于活躍狀態：一是當它從其孩子接收信息時，二是當它向上一級節點傳送部分結果時，在其他時刻，該節點都處于空閑狀態。

2基于一致性容差的網絡聚合方案

雖然現有技術在一定程度上實現了數據聚合，但是在大型的傳感器網絡中，大量節點周期性的發送數據仍然是一個巨大的能量消耗，會縮短傳感器網絡的壽命。但是在有些應用中，用戶并不需要掌握每一個傳感器每一次的具體讀數，只有當讀數變化超出一定的容忍范圍時，才需要獲取這個變化的數據?；谶@樣的情況，可以對常規的聚合方式進行改進，加入一個基于時間周期的數據一致性容差值來決定哪些數據需要經過路由樹轉發，以及如何合并或接收此轉發數據。方案在查詢規范中增加了一條新的SQL語句：VALUES WITHIN tct。參數tct被用戶用來指定查詢的時間一致性容差，它的值表示用戶能夠容忍的傳感器值讀數變化的程度。例如，如果用戶指定tct=10%，則只有在當前傳感器讀數和上一次報告的有效讀數相差在10%以上，傳感器網絡才會向其父節點報告。

3實驗

圖1顯示了在每一個查詢周期內兩個系統之間的比較，其中一個系統采用了時間一致性容差方案，另一個沒有。假設查詢的目的是獲取一棟樓中所有房間的總光照，查詢每30秒進行一次，并將結果按樓層進行分組，在此設置tct的值為10%，即傳感器只有在當前讀數和上一次報告的讀數之間差值在10%以上才需要向父節點再次報告讀數。該查詢語句如下：

在下圖中，圓表示節點，箭頭表示從子節點到父節點的數據流。沿著連接線的表表示從子節點傳送到父節點的值。連接到每個節點的方框表示節點上的當前狀態。此當前狀態包括其上一次報告的讀數、其當前采樣獲取的讀數和表示其子節點上次報告的數據的聚合結果的表組成。每個表下的成本號表示的是將此表從子節點發送到父節點的成本。成本被簡單的表示為表的大小，因為只是用它來說明相對成本。例如，成本為4的表a是成本為2的表b的兩倍大，因此傳遞a表數據的消息是傳遞b表消息的兩倍大，從而導致兩倍的傳輸成本。

圖1表示了一個系統執行上面查詢的一個查詢周期，首先忽略掉陰影標記，該圖表示的是沒有使用一致性容差方案的執行情況。其中每個讀數都是從子節點發送到父節點，發送每條消息的成本表示在了每個節點的左上角。在這個網絡中，向路由樹上發送讀數的總成本是14，或者說所有消息的大小之和是14。

考慮陰影標記的情況是使用了時間一致性容差方案。陰影部分表示的是不需要發送的消息部分，發送每條消息的成本由斜體字標識在了每個節點的右上角。例如，當節點4發送數據時，它首先檢查新讀數和舊數據的差值比例。由于新舊讀數相差不超過10%，因此不會向其父節點發送任何內容。在下一個時間片中，節點2和節點3將其讀數與上一個讀數進行比較。由于兩者相差超過10%，他們都將向父節點發送新的讀數，并替換舊的讀數。然后，節點1收集向它發來的所有讀數，并檢查自己的讀數，結果發現與其以前的讀數相差不超過10%。但是，由于節點1和節點2采樣的數據屬于同一個組，該組中節點2的值已經被發送到上一級。在這種情況下，為了確保該組中聚合值SUM的正確性，節點1必須將其新的讀數累加到節點2的讀數中。然后，節點1將所有這些新信息發送到基站以向用戶報告。因此，第二個方案的總消耗是8。

在這個例子中可以看到，即使在只有四個節點的情況下，也可以節省大量的能量。對節點讀數設置的10%的容差消除了來自節點4的整個傳輸。由于傳感器網絡的性質，能夠在數據傳輸上節省大量的總成本。此外，對于節點4的所有上級節點1和3來說，由于它們都保存了節點4的舊值，同樣不必再向上發送第3組的值。因此他們需要傳輸的信息量減少了，也節省了能源。

4結束語

以上的實驗充分說明，在網絡聚合中恰當地使用時間一致性容差方案可以有效地減少網絡的傳輸成本，同時還可以在用戶可以容忍的誤差范圍內盡可能地保證數據質量。由于在傳感器網絡中數據傳輸是能量消耗的最主要因素，因此該方案在節省網絡能耗和降低數據質量這兩者之間提供了一個較好的折中方案。

參考文獻

[1] Madden S， Franklin M J， Hellerstein J M，et al. TAG：a Tiny AGgregation service for ad-hoc sensor networks[J].Acm Sigops Operating Systems Review，2002，36（S1）：131-146.