WSN 中一種基于時(shí)空相關(guān)性的網(wǎng)內(nèi)數(shù)據(jù)聚合路由協(xié)議＊

陳雪寒，陳志剛，曾 鋒，吳 嘉

（中南大學(xué)軟件學(xué)院，湖南 長(zhǎng)沙410075）

1 引言

無線傳感器網(wǎng)絡(luò)WSN（Wireless Sensor Network）［1，2］是由空間分布的傳感器組成的，用于協(xié)同感知各種環(huán)境條件，廣泛應(yīng)用于環(huán)境監(jiān)測(cè)、國(guó)土安全、通訊、制造業(yè)等領(lǐng)域。無線傳感器網(wǎng)絡(luò)是數(shù)據(jù)驅(qū)動(dòng)的網(wǎng)絡(luò)，通常會(huì)產(chǎn)生大量的數(shù)據(jù)，數(shù)據(jù)在傳感器節(jié)點(diǎn)與sink節(jié)點(diǎn)之間多跳傳輸。鑒于傳感器節(jié)點(diǎn)能量的有限性，在數(shù)據(jù)傳輸過程中合理選擇傳感器節(jié)點(diǎn)與sink節(jié)點(diǎn)之間的數(shù)據(jù)傳送路徑將有助于降低節(jié)點(diǎn)能量消耗和延長(zhǎng)網(wǎng)絡(luò)壽命，這正是無線傳感器網(wǎng)絡(luò)路由協(xié)議面臨的問題。

在合理選擇傳送路徑之外，減少網(wǎng)絡(luò)中的冗余數(shù)據(jù)、降低傳送相同數(shù)據(jù)造成的能量開銷也是延長(zhǎng)網(wǎng)絡(luò)壽命的有效手段。由于網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的采集范圍重疊，鄰近的節(jié)點(diǎn)數(shù)據(jù)之間往往存在著空間相關(guān)性，并且同一個(gè)節(jié)點(diǎn)在一個(gè)時(shí)間序列內(nèi)采集到的數(shù)據(jù)往往存在著時(shí)間相關(guān)性［3］。因此，采集到的數(shù)據(jù)存在冗余，sink節(jié)點(diǎn)可能會(huì)多次接收到相同的數(shù)據(jù)。為減少冗余數(shù)據(jù)，出現(xiàn)了數(shù)據(jù)聚合技術(shù)［4］。通過數(shù)據(jù)聚合可以減少網(wǎng)絡(luò)中的冗余數(shù)據(jù)，減少通信負(fù)載，從而節(jié)約能量。

優(yōu)化的路由機(jī)制和有效的數(shù)據(jù)聚合策略是延長(zhǎng)無線傳感網(wǎng)絡(luò)壽命的兩個(gè)方面，兩者緊密結(jié)合將進(jìn)一步延長(zhǎng)提高網(wǎng)絡(luò)壽命。本文在對(duì)路由協(xié)議和數(shù)據(jù)聚合技術(shù)進(jìn)行結(jié)合研究的同時(shí)，還綜合考慮數(shù)據(jù)的時(shí)空相關(guān)性對(duì)網(wǎng)絡(luò)中的采集數(shù)據(jù)進(jìn)行管理。在分析數(shù)據(jù)聚合技術(shù)和時(shí)空相關(guān)性協(xié)議的基礎(chǔ)上，提出了一種基于時(shí)空相關(guān)性的網(wǎng)內(nèi)數(shù)據(jù)聚合路由算法ST－INDAR。在ST－INDAR 中，根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)感知數(shù)據(jù)的空間相關(guān)性將事件區(qū)域劃分為多個(gè)相關(guān)區(qū)域，每一個(gè)區(qū)域選取一個(gè)代表節(jié)點(diǎn)，并對(duì)代表節(jié)點(diǎn)采取輪換機(jī)制。相關(guān)區(qū)域的大小由事件中心與sink節(jié)點(diǎn)之間的距離來決定。根據(jù)數(shù)據(jù)之間的時(shí)間相關(guān)性對(duì)數(shù)據(jù)采取時(shí)間抑制，通過路由樹的建立和更新來提高網(wǎng)絡(luò)中數(shù)據(jù)聚合的幾率。相比較已有的路由算法，本文提出的ST－INDAR 算法不僅考慮了網(wǎng)絡(luò)中的總體通信負(fù)載，而且還綜合考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)能耗的均衡以及數(shù)據(jù)的有效性和準(zhǔn)確性。ST－INDAR算法在確保數(shù)據(jù)精確性的同時(shí)，增大了網(wǎng)絡(luò)中數(shù)據(jù)聚合的幾率，減少了網(wǎng)絡(luò)中的冗余數(shù)據(jù)量，降低了網(wǎng)絡(luò)中的能量消耗。

本文接下來的組織結(jié)構(gòu)如下：第2節(jié)是相關(guān)工作的介紹；第3節(jié)對(duì)本文所提出的基于時(shí)空相關(guān)性的網(wǎng)內(nèi)數(shù)據(jù)聚合路由算法ST－INDAR 進(jìn)行了描述；第4節(jié)是算法的性能評(píng)估；最后一節(jié)總結(jié)全文，并提出接下來的工作。

2 相關(guān)工作

無線傳感器網(wǎng)絡(luò)的主要功能是對(duì)周邊環(huán)境信息進(jìn)行采集和管理，并將感知到的數(shù)據(jù)發(fā)送到基站。由于其廣泛的應(yīng)用前景，現(xiàn)已成為當(dāng)前研究的熱點(diǎn)［5，6］。為了提高采集信息的準(zhǔn)確性，網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的密度越來越高，節(jié)點(diǎn)的采集范圍重疊。因此，網(wǎng)絡(luò)中存在著大量的冗余數(shù)據(jù)，這些冗余數(shù)據(jù)的傳送需要消耗大量的能量。為減少網(wǎng)絡(luò)中的冗余數(shù)據(jù)，降低網(wǎng)絡(luò)中的數(shù)據(jù)傳輸能耗，時(shí)空相關(guān)性協(xié)議以及網(wǎng)內(nèi)數(shù)據(jù)聚合技術(shù)被提出并應(yīng)用于許多WSN 協(xié)議的設(shè)計(jì)中。

（1）時(shí)空相關(guān)性協(xié)議。

數(shù)據(jù)之間的相關(guān)性主要有三種：時(shí)間相關(guān)性（Temporal Correlation）［7］、空 間 相 關(guān) 性（Spatial Correlation）［3，8，9］和 時(shí) 空 相 關(guān) 性（Spatio－temporal Correlation）［10］。目前已經(jīng)有很多針對(duì)數(shù)據(jù)相關(guān)性的研究。文獻(xiàn)［7］提出了一種以數(shù)據(jù)為中心的協(xié)議，利用節(jié)點(diǎn)連續(xù)觀測(cè)值之間的時(shí)間相關(guān)性來減少網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量，從而降低通信開銷。文獻(xiàn)［3］研究了需要傳送采集信息的傳感器節(jié)點(diǎn)的個(gè)數(shù)與事件信息可靠性之間的關(guān)系。文獻(xiàn)［8］利用數(shù)據(jù)的空間相關(guān)性提出了另外一種基于簇的算法EEDC （Energy－Efficient Data Collection framework）。在EEDC 算法中，節(jié)點(diǎn)連續(xù)地采集數(shù)據(jù)，將具有空間相關(guān)性數(shù)據(jù)的節(jié)點(diǎn)形成一個(gè)簇。算法要求網(wǎng)絡(luò)中的節(jié)點(diǎn)與sink節(jié)點(diǎn)或者數(shù)據(jù)中心節(jié)點(diǎn)可以直接通信，并且sink節(jié)點(diǎn)需要了解全局的網(wǎng)絡(luò)數(shù)據(jù)信息。文獻(xiàn)［9］通過動(dòng)態(tài)地調(diào)整相關(guān)區(qū)域的大小來實(shí)現(xiàn)所需的可靠性。簇頭節(jié)點(diǎn)將節(jié)點(diǎn)之間的能量水平和親密程度作為衡量標(biāo)準(zhǔn)來識(shí)別冗余以及關(guān)閉相關(guān)的活動(dòng)節(jié)點(diǎn)。文獻(xiàn)［10］利用數(shù)據(jù)的空間相關(guān)性將感知到同一事件的節(jié)點(diǎn)劃分為一個(gè)簇并將簇劃分為多個(gè)相關(guān)區(qū)域，并通過數(shù)據(jù)的時(shí)間相關(guān)性對(duì)數(shù)據(jù)采取時(shí)間抑制（Temporal Suppression）策略。每一個(gè)相關(guān)區(qū)域內(nèi)選取一個(gè)代表節(jié)點(diǎn)將采集到的數(shù)據(jù)發(fā)送到簇頭節(jié)點(diǎn)，然后由簇頭節(jié)點(diǎn)通過最短路徑將數(shù)據(jù)傳送至sink節(jié)點(diǎn)。

（2）網(wǎng)內(nèi)數(shù)據(jù)聚合。

由于節(jié)點(diǎn)數(shù)據(jù)之間的相關(guān)性，網(wǎng)內(nèi)數(shù)據(jù)聚合在能量受限的無線傳感器網(wǎng)絡(luò)中扮演著重要的角色，采用網(wǎng)內(nèi)數(shù)據(jù)聚合技術(shù)可以減少網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量，降低網(wǎng)絡(luò)的能量消耗。數(shù)據(jù)聚合的一個(gè)關(guān)鍵方面是確保節(jié)點(diǎn)數(shù)據(jù)傳輸之間的同步，主要有三種時(shí)機(jī)策略［11，12］：周期性簡(jiǎn)單聚合、周期性逐跳聚合和定期每跳調(diào)整聚合?，F(xiàn)有的網(wǎng)內(nèi)數(shù)據(jù)聚合技術(shù)主要包括基于樹的數(shù)據(jù)聚合技術(shù)［13］以及基于集群的數(shù)據(jù)聚合技術(shù)［14，15］。文獻(xiàn)［13］提出了一種最短路徑樹算法SPT（Shortest Path Tree），節(jié)點(diǎn)一旦感應(yīng)到事件發(fā)生，就將感應(yīng)數(shù)據(jù)沿著最短路徑傳送至sink節(jié)點(diǎn)，當(dāng)出現(xiàn)路由重疊時(shí)就進(jìn)行數(shù)據(jù)聚合。但是，最短路徑樹的維護(hù)需要消耗大量的能量。文獻(xiàn)［14］將檢測(cè)到同一事件發(fā)生的節(jié)點(diǎn)劃分為一個(gè)簇，簇頭節(jié)點(diǎn)融合簇內(nèi)所有節(jié)點(diǎn)數(shù)據(jù)后再將融合后的數(shù)據(jù)傳送至sink節(jié)點(diǎn)。文獻(xiàn)［15］在路由建立過程中綜合考慮網(wǎng)絡(luò)中已有的路由路徑以最大化重疊路由，增加數(shù)據(jù)聚合的幾率，從而減少網(wǎng)絡(luò)中的數(shù)據(jù)通信量，降低網(wǎng)絡(luò)的能耗。

盡管相比網(wǎng)絡(luò)中不采用數(shù)據(jù)聚合技術(shù)以及時(shí)空相關(guān)性協(xié)議的情況，上述的策略可以大大減少網(wǎng)絡(luò)中的數(shù)據(jù)通信量，降低網(wǎng)絡(luò)的能量消耗，提高網(wǎng)絡(luò)的性能，延長(zhǎng)網(wǎng)絡(luò)的壽命，但是都沒有綜合考慮網(wǎng)絡(luò)中節(jié)點(diǎn)能耗的均衡以及網(wǎng)絡(luò)的動(dòng)態(tài)性，并且也沒有考慮數(shù)據(jù)的有效性?；谝陨嫌懻?，本文研究無線傳感器網(wǎng)絡(luò)中基于網(wǎng)內(nèi)數(shù)據(jù)聚合的路由策略，結(jié)合數(shù)據(jù)的時(shí)空相關(guān)性提出了一種基于時(shí)空相關(guān)性的網(wǎng)內(nèi)數(shù)據(jù)聚合路由算法ST－INDAR，通過動(dòng)態(tài)分簇以及相關(guān)區(qū)域的動(dòng)態(tài)調(diào)整來適應(yīng)網(wǎng)絡(luò)的動(dòng)態(tài)性，通過路由樹的建立和更新來最大化數(shù)據(jù)聚合的幾率，通過數(shù)據(jù)聚合和數(shù)據(jù)相關(guān)性協(xié)議來減少網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量，從而降低網(wǎng)絡(luò)的通信開銷，通過相關(guān)區(qū)域代表節(jié)點(diǎn)和路由下一跳節(jié)點(diǎn)的選擇來均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗，通過時(shí)間抑制策略來確保數(shù)據(jù)的有效性。通過模擬仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性以及優(yōu)勢(shì)。

3 基于時(shí)空相關(guān)性的網(wǎng)內(nèi)數(shù)據(jù)聚合路由算法TS－INDAR

本節(jié)給出本文所涉及的時(shí)空相關(guān)模型并提出TS－INDAR算法，并對(duì)TS－INDAR 算法進(jìn)行詳 細(xì)的介紹。TS－INDAR算法的關(guān)鍵在于相關(guān)區(qū)域的劃分及動(dòng)態(tài)調(diào)整，以實(shí)現(xiàn)數(shù)據(jù)采集的準(zhǔn)確性和路由的建立，以最大化重疊路由，從而實(shí)現(xiàn)數(shù)據(jù)聚合的最大化，盡可能地降低網(wǎng)絡(luò)中的通信開銷。

3.1 空間相關(guān)性模型

地理位置鄰近的傳感器節(jié)點(diǎn)所采集到的數(shù)據(jù)之間具有一定的相似性。采集數(shù)據(jù)相似的節(jié)點(diǎn)之間的距離取決于應(yīng)用的需求和事件的特征。有些應(yīng)用比較重要并且對(duì)采集數(shù)據(jù)的精確度要求比較高，這就要求節(jié)點(diǎn)之間的距離較小，即要求相關(guān)區(qū)域較小。反之，相關(guān)區(qū)域可以更大一些。接下來給出相關(guān)區(qū)域的定義。

定義1（相關(guān)區(qū)域R（Correlation Region））本文定義相關(guān)區(qū)域?yàn)檫@樣一個(gè)區(qū)域：區(qū)域內(nèi)的節(jié)點(diǎn)所采集的數(shù)據(jù)具有極大的相似性，因此區(qū)域內(nèi)任何一個(gè)節(jié)點(diǎn)的數(shù)據(jù)就可以代表整個(gè)區(qū)域的信息。

3.2 時(shí)間相關(guān)性模型

傳感器節(jié)點(diǎn)采集數(shù)據(jù)通常是周期性的、連續(xù)的。由于物理現(xiàn)象的基本特征，傳感器節(jié)點(diǎn)連續(xù)感知的數(shù)據(jù)在短時(shí)期內(nèi)通常具有較大的相似性。在這種情況下，如果當(dāng)前讀數(shù)相對(duì)于最近的一次讀數(shù)在一個(gè)可接受的錯(cuò)誤閾內(nèi)，節(jié)點(diǎn)則不需要把每一次的數(shù)據(jù)都進(jìn)行傳送。sink節(jié)點(diǎn)可以假設(shè)性地認(rèn)為沒有匯報(bào)的數(shù)據(jù)與先前接收到的數(shù)據(jù)沒有任何變化。下面給出時(shí)間抑制的定義，與文獻(xiàn)［10］中一致。

定義2（時(shí)間抑制（Temporal Suppression））每一個(gè)源節(jié)點(diǎn)都記錄最近的一次讀數(shù)Rlater。若當(dāng)前讀數(shù)Rcurr是可以得到的，則將Rcurr和Rlater進(jìn)行比較。如果相對(duì)值大于給定的時(shí)間一致性容忍tct（Temporal Coherency Tolerance），即若（（｜（Rcurr－Rlater）｜）/Rlater）×100＞tct，則將當(dāng)前讀數(shù)傳送至sink節(jié)點(diǎn)，否則將不會(huì)被傳送至sink節(jié)點(diǎn)，即認(rèn)為是被抑制的。

3.3 TS－INDAR算法的設(shè)計(jì)

本文所提出的TS－INDAR算法的主要目標(biāo)在于在確保數(shù)據(jù)精確性的前提下，最小化網(wǎng)絡(luò)中的通信負(fù)載，降低網(wǎng)絡(luò)中的通信開銷，并均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗。在TS－INDAR 算法中，利用節(jié)點(diǎn)數(shù)據(jù)之間的時(shí)空相關(guān)性減少網(wǎng)絡(luò)中的數(shù)據(jù)量，并在路由路徑建立的過程中綜合考慮已有的路由路徑，以最大化數(shù)據(jù)聚合的幾率，以進(jìn)一步減少網(wǎng)絡(luò)中的數(shù)據(jù)通信量，從而降低網(wǎng)絡(luò)通信開銷。通過代表節(jié)點(diǎn)和路由下一跳節(jié)點(diǎn)的動(dòng)態(tài)選擇以及相關(guān)區(qū)域大小的動(dòng)態(tài)調(diào)整來均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗。TS－INDAR將網(wǎng)絡(luò)中的節(jié)點(diǎn)分為以下五種角色：

（1）簇頭節(jié)點(diǎn)：每一個(gè)簇都有一個(gè)簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)用于收集和聚合簇內(nèi)所有節(jié)點(diǎn)的數(shù)據(jù)信息，最后將聚合后的數(shù)據(jù)通過多跳傳輸傳送至sink節(jié)點(diǎn)。

（2）代表節(jié)點(diǎn)：在每一個(gè)相關(guān)區(qū)域內(nèi)選取一個(gè)代表節(jié)點(diǎn)。根據(jù)相關(guān)區(qū)域的定義，區(qū)域內(nèi)任何一個(gè)節(jié)點(diǎn)的數(shù)據(jù)就可以代表整個(gè)區(qū)域的信息。代表節(jié)點(diǎn)將自身的數(shù)據(jù)和所接收到的數(shù)據(jù)進(jìn)行聚合，然后將聚合后的信息通過多跳傳輸至簇頭節(jié)點(diǎn)。

（3）中繼節(jié)點(diǎn)：將數(shù)據(jù)由簇頭節(jié)點(diǎn)傳輸至sink節(jié)點(diǎn)的中間節(jié)點(diǎn)。

（4）成員節(jié)點(diǎn)：普通節(jié)點(diǎn)，在一定情況下會(huì)成為代表節(jié)點(diǎn)。

（5）sink節(jié)點(diǎn)：用于接收網(wǎng)絡(luò)中的數(shù)據(jù)。

TS－INDAR 算 法 分 為 以 下 四 個(gè) 階 段：Hop 樹的建立；簇的形成和相關(guān)區(qū)域的劃分；路由的形成；Hop樹的更新以及數(shù)據(jù)傳輸。

3.3.1 Hop樹的建立

Hop樹建立階段的主要目標(biāo)在于建立一棵將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)與sink節(jié)點(diǎn)連接起來的樹。網(wǎng)絡(luò)中的節(jié)點(diǎn)與sink節(jié)點(diǎn)之間的距離根據(jù)Hop 數(shù)（跳數(shù)）來計(jì)算。Hop樹的建立通過洪泛的方式來實(shí)現(xiàn)，最終得到一棵如圖1 所示的最短路徑Hop樹。網(wǎng)絡(luò)中所有節(jié)點(diǎn)都保存了sink節(jié)點(diǎn)的位置信息（xs，ys）和其鄰居節(jié)點(diǎn)的位置信息（xn，yn）、源節(jié)點(diǎn)到達(dá)sink節(jié)點(diǎn)所需要的Hop數(shù)（HopToSink值）以及它的上一跳節(jié)點(diǎn)的ID。在圖1中，圓圈內(nèi)的數(shù)據(jù)表示該節(jié)點(diǎn)到達(dá)sink 節(jié)點(diǎn)所需要的最小Hop數(shù)。

Figure 1 Establishment of the Hop tree圖1 Hop樹的建立

3.3.2 簇的形成和相關(guān)區(qū)域的劃分

本文采用基于事件的分簇，即當(dāng)一個(gè)事件發(fā)生后，網(wǎng)絡(luò)中的一個(gè)或者多個(gè)節(jié)點(diǎn)將會(huì)監(jiān)測(cè)到事件的發(fā)生，這些監(jiān)測(cè)到同一事件的節(jié)點(diǎn)將會(huì)形成一個(gè)簇，在簇形成的同時(shí)會(huì)進(jìn)行簇頭節(jié)點(diǎn)的選擇。由于簇頭節(jié)點(diǎn)需要接收簇內(nèi)所有數(shù)據(jù)并將所接收到的數(shù)據(jù)與自己的數(shù)據(jù)進(jìn)行聚合，最后將聚合后的數(shù)據(jù)傳送至sink節(jié)點(diǎn)。因此，為了均衡節(jié)點(diǎn)的能耗以及確保數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性，本文結(jié)合節(jié)點(diǎn)的當(dāng)前剩余能量以及節(jié)點(diǎn)與sink節(jié)點(diǎn)之間的距離（HopTo－Sink值）來進(jìn)行簇頭節(jié)點(diǎn)的選擇。ID 值為i的傳感器節(jié)點(diǎn)被選取為簇C的簇頭節(jié)點(diǎn)應(yīng)滿足：

其中，HopToSink為傳感器節(jié)點(diǎn)i的HopToSink值，H為網(wǎng)絡(luò)中距離sink 節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)的HopToSink值，為節(jié)點(diǎn)i的當(dāng)前剩余能量，為網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)所能存儲(chǔ)的最大能量。由式（1）可知，每次都選取簇內(nèi)剩余能量較多并且離sink節(jié)點(diǎn)較近的節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)。

在簇形成以及簇頭節(jié)點(diǎn)選取后，開始對(duì)事件區(qū)域進(jìn)行相關(guān)區(qū)域的劃分。本文假設(shè)事件區(qū)域?yàn)橐粋€(gè)圓形（事件區(qū)域可以為任何形狀的區(qū)域），并將事件區(qū)域劃分為個(gè)相關(guān)區(qū)域，其中re為事件的最大感應(yīng)半徑，c為相關(guān)區(qū)域的大小。如圖2所示，事件區(qū)域被劃分為16個(gè)相關(guān)區(qū)域，每一個(gè)相關(guān)區(qū)域?qū)?yīng)一個(gè)坐標(biāo)。令事件中心的位置為（xe，ye），對(duì)應(yīng)每一個(gè)相關(guān)區(qū)域的坐標(biāo)(xnc，ync)就是該區(qū)域中心的坐標(biāo)，可以通過事件中心的坐標(biāo)計(jì)算得到。簇內(nèi)節(jié)點(diǎn)會(huì)根據(jù)Hop樹建立過程中所保存的相關(guān)位置信息自動(dòng)計(jì)算自己屬于哪一個(gè)相關(guān)區(qū)域。在相關(guān)區(qū)域的劃分結(jié)束之后，就開始執(zhí)行代表節(jié)點(diǎn)的選取，在本文中，每次都選取相關(guān)區(qū)域中剩余能量最多的節(jié)點(diǎn)擔(dān)任代表節(jié)點(diǎn)。為了均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗，代表節(jié)點(diǎn)會(huì)進(jìn)行周期性輪換。在代表節(jié)點(diǎn)選取結(jié)束之后，簇內(nèi)節(jié)點(diǎn)只有代表節(jié)點(diǎn)處于活動(dòng)狀態(tài)，將簇內(nèi)其他節(jié)點(diǎn)都轉(zhuǎn)換為休眠狀態(tài)。

Figure 2 Division of the event area圖2 事件區(qū)域的劃分

相關(guān)區(qū)域的大?。╟）可以根據(jù)事件的特征以及應(yīng)用的具體要求進(jìn)行相應(yīng)的調(diào)整。為了均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗，本文相關(guān)區(qū)域的大?。╟）根據(jù)事件區(qū)域中心與sink 節(jié)點(diǎn)之間的距離來決定。離sink節(jié)點(diǎn)較近的節(jié)點(diǎn)的能耗較大，故增大相關(guān)區(qū)域以節(jié)省能量消耗。離sink節(jié)點(diǎn)較遠(yuǎn)的相關(guān)區(qū)域的大小可以適當(dāng)減少，以提高監(jiān)測(cè)的精確性。令c∈［0，cmax］，則相關(guān)區(qū)域的大小可以通過式（2）進(jìn)行計(jì)算：

其中，Dmax為網(wǎng)絡(luò)中與sink節(jié)點(diǎn)最遠(yuǎn)的距離，d∈［0，Dmax］為事件區(qū)域中心與sink 節(jié)點(diǎn)之間的距離。由式（2）可知，當(dāng)d＝0時(shí)，c取得最大值cmax；當(dāng)d＝Dmax時(shí)，c取得最小值0。c隨著d的增大而減少。

為了確保網(wǎng)絡(luò)的正常通信以及能夠采用最短路徑。如圖3所示，相關(guān)區(qū)域達(dá)到最大時(shí)，通信半徑正好為兩個(gè)相關(guān)區(qū)域R1和R2所構(gòu)成的矩形的斜邊，因此有：。故相關(guān)區(qū)域的大小c應(yīng)滿足：。當(dāng)c＝0時(shí)，事件區(qū)域內(nèi)的節(jié)點(diǎn)都不具有空間相關(guān)性，每一個(gè)節(jié)點(diǎn)都是一個(gè)獨(dú)立的節(jié)點(diǎn)。

igure 3 Calculation of the upper bound of the relevant area圖3 相關(guān)區(qū)域大小上限計(jì)算

3.3.3 路由的形成與Hop樹的更新

為了確保數(shù)據(jù)傳輸?shù)目煽啃砸约敖档途W(wǎng)絡(luò)的通信能耗，就需要找到一條合適的由簇頭節(jié)點(diǎn)到sink節(jié)點(diǎn)的路由路徑，此時(shí)路由的形成過程開始。在路由的建立過程中，由簇頭節(jié)點(diǎn)開始，每一次節(jié)點(diǎn)都會(huì)選擇最優(yōu)的鄰居節(jié)點(diǎn)作為自己的下一跳，同時(shí)廣播Hop樹更新信息用于Hop樹的更新，Hop樹的更新與Hop樹的建立過程類似。為了確保數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性，這里將最優(yōu)的鄰居節(jié)點(diǎn)定義為HopToSink值最小的鄰居節(jié)點(diǎn)，即選取最短路徑對(duì)數(shù)據(jù)進(jìn)行傳送。被選擇的節(jié)點(diǎn)就成為一個(gè)中繼節(jié)點(diǎn)，并將其HopToSink值設(shè)置為0，然后中繼節(jié)點(diǎn)繼續(xù)選擇下一跳節(jié)點(diǎn)并進(jìn)行Hop樹的更新過程直至到達(dá)sink節(jié)點(diǎn)。如圖4所示為第一個(gè)事件發(fā)生時(shí)所形成的路由，該路由為一條由簇頭節(jié)點(diǎn)到sink節(jié)點(diǎn)的最短路徑。在路由的形成過程中同時(shí)進(jìn)行了Hop樹的更新操作，更新后的Hop樹如圖5所示，此時(shí)圓圈內(nèi)的數(shù)字代表的是該節(jié)點(diǎn)與sink節(jié)點(diǎn)的距離和與網(wǎng)絡(luò)中已有路由路徑的距離之間的最小值。如圖6所示為當(dāng)同時(shí)有第二個(gè)事件發(fā)生時(shí)所形成的路由路徑，該路由路徑不再是由簇頭節(jié)點(diǎn)到sink節(jié)點(diǎn)的最短路徑，而是一條匯聚到網(wǎng)絡(luò)中已有路徑的路由。通過對(duì)網(wǎng)絡(luò)中已有路由路徑的綜合考慮，增大了網(wǎng)絡(luò)中的重疊路由，提高了網(wǎng)絡(luò)中數(shù)據(jù)聚合的幾率。

Figure 4 Routing of the first event圖4 第一個(gè)事件路由形成

Figure 5 Update of the Hop tree圖5 路由形成后Hop樹的更新

Figure 6 Routing of the second event圖6 第二個(gè)并發(fā)事件路由形成

3.3.4 數(shù)據(jù)傳輸

在TS－INDAR算法中，代表節(jié)點(diǎn)將代表相關(guān)區(qū)域的信息和接收到的其他代表節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行聚合之后，將聚合后的數(shù)據(jù)通過簇內(nèi)其他代表節(jié)點(diǎn)采用多跳的方式傳送至簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)在將接收到的來自多個(gè)代表節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行聚合之后，再將聚合后的信息按照已經(jīng)建立好的路由路徑通過中繼節(jié)點(diǎn)采用多跳的方式將數(shù)據(jù)傳送至sink 節(jié)點(diǎn)。代表節(jié)點(diǎn)在發(fā)送數(shù)據(jù)之前會(huì)計(jì)算當(dāng)前數(shù)據(jù)與最近一次數(shù)據(jù)的相對(duì)域，如果相對(duì)域大于所給定的時(shí)間一致性容忍tct，則將其進(jìn)行傳送；否則，該數(shù)據(jù)將被抑制，即不會(huì)被傳送至sink 節(jié)點(diǎn)。中繼節(jié)點(diǎn)在接收到多個(gè)數(shù)據(jù)包時(shí)，也會(huì)將這些數(shù)據(jù)進(jìn)行聚合之后再進(jìn)行傳送。經(jīng)過代表節(jié)點(diǎn)、簇頭節(jié)點(diǎn)和中繼節(jié)點(diǎn)三處的數(shù)據(jù)聚合以及相應(yīng)的時(shí)空相關(guān)性策略，大大地減少了網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量，降低了網(wǎng)絡(luò)的通信開銷。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)置

本文利用OMNeT＋＋4.2 仿真平臺(tái)對(duì)所提出的TS－INDAR算法進(jìn)行模擬仿真，并在仿真的基礎(chǔ)上對(duì)算法的有效性和性能進(jìn)行分析。在TSINDAR 的仿真過程中，sink節(jié)點(diǎn)位于監(jiān)測(cè)網(wǎng)絡(luò)區(qū)域的右上角，傳感器節(jié)點(diǎn)均勻地分布在整個(gè)監(jiān)測(cè)區(qū)域內(nèi)，網(wǎng)絡(luò)節(jié)點(diǎn)的密度用來計(jì)算，其中n為節(jié)點(diǎn)的個(gè)數(shù)，rc為傳輸半徑，S為感應(yīng)區(qū)域的面積。為保持節(jié)點(diǎn)的密度不變，傳感區(qū)域的大小應(yīng)該根據(jù)網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)目的不同而有所調(diào)整。將實(shí)驗(yàn)結(jié)果與文獻(xiàn)［15］中的DRINA（Data Routing for In－Network Aggregation）算 法 和 文 獻(xiàn)［10］中的EAST（Efficient Data Collection Aware of Spatio－Temporal Correlation）算 法 進(jìn) 行 對(duì) 比。相應(yīng)的參數(shù)值設(shè)定如表1所示。

Table 1 Simulation parameters表1 實(shí)驗(yàn)參數(shù)的設(shè)定

4.2 事件模型

在實(shí)驗(yàn)仿真過程中，所有事件發(fā)生的時(shí)間和位置都是隨機(jī)的。無論節(jié)點(diǎn)接收到多少個(gè)數(shù)據(jù)包，都將其聚合成一個(gè)固定長(zhǎng)度的包之后再進(jìn)行傳送，并采用周期性簡(jiǎn)單聚合［16］，即周期性接收和聚集信息。

本文采用的事件模型與文獻(xiàn)［10］中的事件模型一致，即采用一組收集自巴西亞馬遜雨林一周的環(huán)境溫度數(shù)據(jù)（攝氏度）［17］。事件區(qū)域內(nèi)坐標(biāo)為（x，y）的點(diǎn)A 處的溫度根據(jù)式子temperature＝TE－（DE×TD）來計(jì)算，其中TE為事件中心的溫度，DE為點(diǎn)A 到事件中心之間的Euclidean距離，TD為溫度降低率（℃/m）。

4.3 性能分析

（1）相關(guān)區(qū)域的大小。相關(guān)區(qū)域的大小直接影響著網(wǎng)絡(luò)的能耗，即相關(guān)區(qū)域內(nèi)節(jié)點(diǎn)的能耗與相關(guān)區(qū)域的大小成負(fù)相關(guān)。在多跳無線傳感器網(wǎng)絡(luò)中，近sink的節(jié)點(diǎn)由于需要承擔(dān)更多的通信負(fù)載能耗較多，而遠(yuǎn)sink的節(jié)點(diǎn)能耗較少。因此，為了均衡網(wǎng)絡(luò)中的能量消耗，本文根據(jù)事件區(qū)域中心與sink節(jié)點(diǎn)之間的距離來決定相關(guān)區(qū)域的大小，并給出了式（2）用于計(jì)算相關(guān)區(qū)域的大小。在仿真實(shí)驗(yàn)過程中，將相應(yīng)的數(shù)據(jù)代入式（2）可得：

Figure 7 Relationship between the correlation region c and the distance from event area centre to sink nodes圖7 相關(guān)區(qū)域大小c與事件區(qū)域中心到sink節(jié)點(diǎn)距離的關(guān)系

（2）數(shù)據(jù)精確度。是指觀測(cè)值相比原始數(shù)據(jù)的精確性。由于TS－INDAR 相比較EAST 算法和DRINA 算法減少了網(wǎng)絡(luò)中傳送至sink節(jié)點(diǎn)的數(shù)據(jù)量，因此TS－INDAR 的數(shù)據(jù)精確度要低于EAST 算法和DRINA 算法。圖8 顯示了當(dāng)時(shí)間一致性容忍tct＝0時(shí)數(shù)據(jù)精確度與相關(guān)區(qū)域大小c之間的關(guān)系。由圖8可以看出，隨著相關(guān)區(qū)域的增大，數(shù)據(jù)的精確度降低。原因在于相關(guān)區(qū)域越大，網(wǎng)絡(luò)中的代表節(jié)點(diǎn)越少，傳送至sink節(jié)點(diǎn)的數(shù)據(jù)量越少，從而導(dǎo)致數(shù)據(jù)精確度降低。由圖7可以得到。由圖8 可 知，雖然TS－INDAR的數(shù)據(jù)精確度要低于EAST 算法和DRINA算法，但是在相關(guān)區(qū)域大小的可取范圍內(nèi)，數(shù)據(jù)的精確度至少可以保證在99.35%以上。

Figure 8 Relationship between data accuracy and the correlation region c圖8 數(shù)據(jù)精確度與相關(guān)區(qū)域c的關(guān)系

在仿真實(shí)驗(yàn)過程中，三個(gè)并發(fā)事件的事件區(qū)域中心（事件的發(fā)生位置是隨機(jī)的）與sink節(jié)點(diǎn)的距離分別為113.62m、578.43m、923.51m。由此通過計(jì)算可以得到相對(duì)應(yīng)的相關(guān)區(qū)域的大小分別為31.67m、14.87m、2.40m。圖9顯示了仿真實(shí)驗(yàn)過程中針對(duì)這三個(gè)并發(fā)事件sink節(jié)點(diǎn)所接到的的數(shù)據(jù)精確度與時(shí)間一致性容忍tct之間的關(guān)系。由圖9可以看出，雖然TS－INDAR 的數(shù)據(jù)精確度要低于EAST 算法和DRINA 算法，當(dāng)時(shí)間一致性容忍tct＝0 時(shí)，網(wǎng)絡(luò)中數(shù)據(jù)的精確度可以達(dá)到99.82%，并隨著tct的增大，數(shù)據(jù)的精確度降低。當(dāng)滿足tct≤2時(shí)，網(wǎng)絡(luò)中數(shù)據(jù)的精確度可以達(dá)到99.5%以上。

（3）能量消耗。由于無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)能量受限的特點(diǎn)，能量消耗是衡量路由協(xié)議性能的一個(gè)重要指標(biāo)。圖10 顯示了在給定并發(fā)事件數(shù)為3、時(shí)間一致性容忍tct＝1的情況下網(wǎng)絡(luò)中的能量消耗與事件持續(xù)時(shí)間之間的關(guān)系。由圖10可知，TS－INDAR的能耗相對(duì)于DRINA 降低了25%，相對(duì)于EAST 降低了12.6%。原因在于當(dāng)并發(fā)事件數(shù)增多時(shí)，每一個(gè)事件區(qū)域都形成一個(gè)簇，簇內(nèi)節(jié)點(diǎn)感知到的數(shù)據(jù)通過網(wǎng)絡(luò)中的中繼節(jié)點(diǎn)傳送至sink節(jié)點(diǎn)，TS－INDAR 算法通過網(wǎng)內(nèi)數(shù)據(jù)聚合和時(shí)空相關(guān)性協(xié)議減少了網(wǎng)絡(luò)中的數(shù)據(jù)通信量，從而降低了網(wǎng)絡(luò)中的通信開銷。

Figure 9 Relationship between data accuracy and tct圖9 網(wǎng)絡(luò)數(shù)據(jù)精確度與時(shí)間一致性容忍tct的關(guān)系

Figure 10 Relationship between energy consumption and event duration圖10 能量消耗與事件持續(xù)時(shí)間的關(guān)系

5 結(jié)束語

本文以降低網(wǎng)絡(luò)中冗余數(shù)據(jù)量為目的，研究了無線傳感器網(wǎng)絡(luò)中局域數(shù)據(jù)聚合的路由協(xié)議以及時(shí)空相關(guān)性協(xié)議。提出了一種基于時(shí)空相關(guān)性的數(shù)據(jù)聚合路由協(xié)議TS－INDAR，其主要包括四個(gè)過程：Hop 樹的形成；簇的形成和相關(guān)區(qū)域的劃分；路由的形成；Hop樹的更新和數(shù)據(jù)傳輸。通過動(dòng)態(tài)分簇來適應(yīng)網(wǎng)絡(luò)的動(dòng)態(tài)性，通過路由樹的建立和更新來最大化數(shù)據(jù)聚合的幾率，通過數(shù)據(jù)聚合和數(shù)據(jù)相關(guān)性協(xié)議來減少網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量，從而降低網(wǎng)絡(luò)的通信開銷，通過相關(guān)區(qū)域代表節(jié)點(diǎn)和路由下一跳節(jié)點(diǎn)的選擇以及相關(guān)區(qū)域的動(dòng)態(tài)調(diào)整來均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗。仿真結(jié)果顯示，TS－INDAR 協(xié)議能夠在確保數(shù)據(jù)較高精確度的前提下，減少網(wǎng)絡(luò)中的數(shù)據(jù)通信量，降低網(wǎng)絡(luò)通信開銷。下一步的工作計(jì)劃是研究如何針對(duì)網(wǎng)絡(luò)中不同區(qū)域的能耗情況來調(diào)整相關(guān)區(qū)域的大小，使得網(wǎng)絡(luò)中的節(jié)點(diǎn)能耗能夠得到均衡以及網(wǎng)絡(luò)性能的最大化。

［1］ Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless sensor networks：A survey［J］.Computer nNetworks，2002，38（4）：393－422.

［2］ Anastasi G，Conti M，Di Francesco M，et al.Energy conservation in wireless sensor networks：A survey［J］.Ad Hoc Networks，2009，7（3）：537－568.

［3］ Akyildiz I F，Vuran M C，Akan O B.On exploiting spatial and temporal correlation in wireless sensor networks［C］//Proc of WiOpt，2004：71－80.

［4］ Nakamura E F，Loureiro A A F，F(xiàn)rery A C.Information fusion for wireless sensor networks：Methods，models，and classifications［J］.ACM Computing Surveys（CSUR），2007，39（3）：9.

［5］ Li Jian－zhong，Gao Hong.Survey on sensor network research［J］.Journal of Computer Research and Development，2008，45（1）：1－15.（in Chinese）

［6］ Ye F，Luo H，Cheng J，et al.A two－tier data dissemination model for large－scale wireless sensor networks［C］∥Proc of the 8th Annual International Conference on Mobile Computing and Networking，2002：148－159.

［7］ Vuran M C，Akan?B，Akyildiz I F.Spatio－temporal correlation：Theory and applications for wireless sensor networks［J］.Computer Networks，2004，45（3）：245－259.

［8］ Liu C，Wu K，Pei J.An energy－efficient data collection framework for wireless sensor networks by exploiting spatiotemporal correlation［J］.IEEE Transactions on Parallel and Distributed Systems，2007，18（7）：1010－1023.

［9］ Shah G A，Bozyigit M.Exploiting energy－aware spatial correlation in wireless sensor networks［C］∥Proc of the 2nd International Conference on Communication Systems Software and Middleware，2007：1－6.

［10］ Villas L A，Boukerche A，Guidoni D L，et al.An energy－aware spatio－temporal correlation mechanism to perform efficient data collection in wireless sensor networks［J］.Computer Communications，2013，36（9）：1054－1066.

［11］ Hu F，Cao X，May C.Optimized scheduling for data aggregation in wireless sensor networks［C］∥Proc of IEEE International Conference on Information Technology：Coding and Computing，2005：557－561.

［12］ Solis I，Obraczka K.The impact of timing in data aggregation for sensor networks［C］∥Proc of 2004IEEE International Conference on Communications，2004：3640－3645.

［13］ Krishnamachari B，Estrin D，Wicker S B.The impact of data aggregation in wireless sensor networks［C］∥Proc of the 22nd International Conference Distributed Computing Systems（ICDCSW ’02），2002：575－578.

［14］ Nakamura E F，de Oliveira H A B F，Pontello L F，et al.On demand role assignment for event－detection in sensor networks［C］∥Proc of IEEE 11th Sympium on Computers and Comm，2006：941－947.

［15］ Villas L A，Boukerche A，Ramos H S，et al.DRINA：A lightweight and reliable routing approach for in－network aggregation in wireless sensor networks［J］.IEEE Transactions on Computers，2013，62（4）：676－689.

［16］ Younis O，Krunz M，Ramasubramanina S.Node clustering in wireless sensor networks：Recent developments and deployment challenges［J］.IEEE Network，2006，20（3）：20－25.

［17］ Horacio.Data collected of Amazon forest in Brazil［EB/OL］.［2011－05－17］.http：www.destination360.com/southamerica/brazil/amazon.

附中文參考文獻(xiàn)：

［5］ 李建中，高宏.無線傳感器網(wǎng)絡(luò)的研究進(jìn)展［J］.計(jì)算機(jī)研究與發(fā)展，2008，45：1－15.