程文靜

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

關(guān)鍵詞 傳感器網(wǎng)絡(luò);時(shí)間一致性;網(wǎng)絡(luò)聚合

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

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

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

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

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

TAG中的同步是通過(guò)讓父節(jié)點(diǎn)在報(bào)告自己的讀數(shù)之前等待一定的時(shí)間間隔來(lái)完成的。具體來(lái)說(shuō)，TAG將一個(gè)查詢周期細(xì)分為較短的時(shí)間片，時(shí)間片數(shù)等于路由樹(shù)的最大深度d，每個(gè)時(shí)間片的長(zhǎng)度為（EPOCH DURATION）/d，其中EPOCH DURATION為一個(gè)周期的時(shí)長(zhǎng)。在一個(gè)時(shí)間片內(nèi)，父節(jié)點(diǎn)將處于活動(dòng)狀態(tài)，并從其子節(jié)點(diǎn)接收消息。在下一個(gè)時(shí)間片內(nèi)，其子節(jié)點(diǎn)將處于空閑狀態(tài)，而父節(jié)點(diǎn)仍處于活動(dòng)狀態(tài)，并向其上一級(jí)節(jié)點(diǎn)傳輸部分聚合的結(jié)果。父?jìng)鞲衅鲗⒃陔S后的時(shí)間片內(nèi)（即當(dāng)它完成接收和傳輸其子樹(shù)中的部分聚合數(shù)據(jù)后）會(huì)變進(jìn)入空閑狀態(tài)。

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

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

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

3實(shí)驗(yàn)

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

在下圖中，圓表示節(jié)點(diǎn)，箭頭表示從子節(jié)點(diǎn)到父節(jié)點(diǎn)的數(shù)據(jù)流。沿著連接線的表表示從子節(jié)點(diǎn)傳送到父節(jié)點(diǎn)的值。連接到每個(gè)節(jié)點(diǎn)的方框表示節(jié)點(diǎn)上的當(dāng)前狀態(tài)。此當(dāng)前狀態(tài)包括其上一次報(bào)告的讀數(shù)、其當(dāng)前采樣獲取的讀數(shù)和表示其子節(jié)點(diǎn)上次報(bào)告的數(shù)據(jù)的聚合結(jié)果的表組成。每個(gè)表下的成本號(hào)表示的是將此表從子節(jié)點(diǎn)發(fā)送到父節(jié)點(diǎn)的成本。成本被簡(jiǎn)單的表示為表的大小，因?yàn)橹皇怯盟鼇?lái)說(shuō)明相對(duì)成本。例如，成本為4的表a是成本為2的表b的兩倍大，因此傳遞a表數(shù)據(jù)的消息是傳遞b表消息的兩倍大，從而導(dǎo)致兩倍的傳輸成本。

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

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

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)

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