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

程文靜

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

關鍵詞 傳感器網(wǎng)絡;時間一致性;網(wǎng)絡聚合

1網(wǎng)絡聚合模型

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

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

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

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

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

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

2基于一致性容差的網(wǎng)絡聚合方案

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

3實驗

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

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

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

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

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

4結束語

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

參考文獻

[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.