戴振華 王建新

(1.中南大學(xué)信息科學(xué)與工程學(xué)院，湖南長沙410083；2.湖南科技學(xué)院，湖南永州425100)

1.前言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，簡稱WSN)綜合了傳感器技術(shù)、嵌入式計算技術(shù)、分布式信息處理技術(shù)和通信技術(shù)，能夠協(xié)作地實(shí)時監(jiān)測、感知和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境或監(jiān)測對象的信息，并對這些信息進(jìn)行處理，獲得詳盡準(zhǔn)確的信息，傳送到需要這些信息的用戶。

傳感器網(wǎng)絡(luò)技術(shù)將應(yīng)用于越來越多的領(lǐng)域，例如戰(zhàn)場監(jiān)視、醫(yī)療護(hù)理、污染監(jiān)測和目標(biāo)跟蹤等，在這些應(yīng)用中，基本的操作是數(shù)據(jù)收集。與傳統(tǒng)的有線網(wǎng)絡(luò)和無線網(wǎng)絡(luò)相比，傳感器網(wǎng)絡(luò)的數(shù)據(jù)收集面臨更多的技術(shù)難題：(1)能效問題，無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)具有通信和計算能力弱、電源能量有限且無法補(bǔ)充、易被損壞等特點(diǎn)；(2)存在相關(guān)數(shù)據(jù)收集和精確數(shù)據(jù)收集模式；(3)交互式數(shù)據(jù)收集，在某一特定時段，觀測者可能只對某一區(qū)域的某些類型的傳感器收集的數(shù)據(jù)感興趣，不必激活大量傳感器節(jié)點(diǎn)的數(shù)據(jù)收集；(4)自適應(yīng)性，傳感器網(wǎng)絡(luò)的拓?fù)淇赡苡捎诙喾N原因(節(jié)點(diǎn)失效、鏈路干擾等)而發(fā)生變化，這要求數(shù)據(jù)收集機(jī)制能夠適應(yīng)這些變化，具有動態(tài)的自適應(yīng)性?；趥鞲衅鲾?shù)據(jù)收集的這些特點(diǎn)，目前學(xué)者提出了一些傳感器網(wǎng)絡(luò)數(shù)據(jù)收集的算法，本文根據(jù)數(shù)據(jù)收集結(jié)構(gòu)、節(jié)點(diǎn)數(shù)據(jù)流量、移動性、功率控制和睡眠調(diào)度方面的不同，綜述了傳感器網(wǎng)絡(luò)數(shù)據(jù)收集的相關(guān)技術(shù)算法。

2.基于結(jié)構(gòu)化的數(shù)據(jù)收集協(xié)議和算法

WSN的網(wǎng)絡(luò)結(jié)構(gòu)是影響數(shù)據(jù)收集協(xié)議的一個重要因素，如果網(wǎng)絡(luò)區(qū)域很大，平坦型網(wǎng)絡(luò)消耗更少的能量，如果網(wǎng)絡(luò)規(guī)模小，層次型網(wǎng)絡(luò)消耗更少的能量。

2.1 平坦型(Flat)網(wǎng)絡(luò)

在平坦型網(wǎng)絡(luò)里，包含大量的靜態(tài)傳感器節(jié)點(diǎn)和一個sink，所有傳感器節(jié)點(diǎn)擁有同樣的能量，具有相同的角色，都能夠與sink通信。報文通過一跳或多跳轉(zhuǎn)發(fā)到sink，即所有數(shù)據(jù)流量都流向sink。因此，靠近sink的節(jié)點(diǎn)比處于網(wǎng)絡(luò)邊緣的節(jié)點(diǎn)消耗更多的能量，這種網(wǎng)絡(luò)結(jié)構(gòu)只適合于小規(guī)模的網(wǎng)絡(luò)。通常包括兩階段pull擴(kuò)散、一階段pull擴(kuò)散和push擴(kuò)散。

2.2 層次型(Hierarchical)網(wǎng)絡(luò)

層次型結(jié)構(gòu)通過在網(wǎng)絡(luò)里選舉某些節(jié)點(diǎn)作為簇頭或增加少數(shù)高能量的節(jié)點(diǎn)，把整個網(wǎng)絡(luò)自組織成不同的層次，增強(qiáng)了擴(kuò)展性。

(1)基于簇結(jié)構(gòu)的網(wǎng)絡(luò)

所謂分簇技術(shù)，就是將節(jié)點(diǎn)劃分成許多組，稱為簇(cluster)，每個簇都有一個簇頭和許多簇成員節(jié)點(diǎn)。分簇將網(wǎng)絡(luò)劃分為兩層結(jié)構(gòu)，簇頭節(jié)點(diǎn)形成高一層，成員節(jié)點(diǎn)形成低一層，成員節(jié)點(diǎn)將數(shù)據(jù)發(fā)送給各自的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)將數(shù)據(jù)融合后通過其它簇頭節(jié)點(diǎn)發(fā)送到基站(sink)。分簇技術(shù)是一種優(yōu)化能耗的拓?fù)淇刂萍夹g(shù)，能減少冗余數(shù)據(jù)量，延長網(wǎng)絡(luò)壽命，有效地進(jìn)行網(wǎng)內(nèi)數(shù)據(jù)融合，減少數(shù)據(jù)報告延遲和增強(qiáng)網(wǎng)絡(luò)的可擴(kuò)展性。由于簇頭節(jié)點(diǎn)經(jīng)常遠(yuǎn)距離傳輸數(shù)據(jù)，因此它們將消耗更多的能量。因此，網(wǎng)絡(luò)將定期地重新進(jìn)行分簇，選擇能量充裕的節(jié)點(diǎn)擔(dān)當(dāng)簇頭節(jié)點(diǎn)，從而將負(fù)載均勻地分布到所有節(jié)點(diǎn)上。分簇路由己經(jīng)成為傳感器網(wǎng)絡(luò)的熱門研究領(lǐng)域。近年來提出的較有代表性簇結(jié)構(gòu)的網(wǎng)絡(luò)協(xié)議主要有LEACH、HEED、CLUDDA。

LEACH是一個經(jīng)典的延長網(wǎng)絡(luò)壽命的聚類協(xié)議，它的基本思想是通過周期性等概率地隨機(jī)選擇簇頭，將整個網(wǎng)絡(luò)的能量負(fù)載平均分配到每個傳感器節(jié)點(diǎn)，在簇頭執(zhí)行數(shù)據(jù)聚合，從而達(dá)到降低網(wǎng)絡(luò)能耗的目的。盡管LEACH延長了系統(tǒng)生命期和數(shù)據(jù)的準(zhǔn)確性，但要求簇頭節(jié)點(diǎn)具有較大的通信能力，擴(kuò)展性差，不適合大規(guī)模的網(wǎng)絡(luò)，簇頭節(jié)點(diǎn)的能量消耗也很快，頻繁地選擇簇頭大大增加了網(wǎng)絡(luò)能耗。

HEED的主要目標(biāo)是通過高效成簇，將能耗均勻分布到整個網(wǎng)絡(luò)從而最大化網(wǎng)絡(luò)生命期。HEED的簇頭選擇主要依據(jù)主、次兩個參數(shù)。HEED的主要改進(jìn)是：在簇頭選擇中考慮了節(jié)點(diǎn)的剩余能量，并以主從關(guān)系引入了多個約束條件作用于簇頭的選擇過程，HEED在簇頭選擇標(biāo)準(zhǔn)以及簇頭競爭機(jī)制上都與LEACH不同。實(shí)驗(yàn)結(jié)果表明，HEED分簇速度更快，能產(chǎn)生更加分布均勻的簇頭、更合理的網(wǎng)絡(luò)拓?fù)洹?/p>

CLUDDA是一種結(jié)合了成簇和定向擴(kuò)散的混合方法。主要分為兩個階段：興趣傳播和數(shù)據(jù)傳播，興趣消息里包含查詢定義，描述需要對數(shù)據(jù)執(zhí)行的操作。在興趣傳播階段，只有簇頭和sink執(zhí)行興趣分發(fā)任務(wù)，普通節(jié)點(diǎn)保持沉默，直到它能提供查詢請求的服務(wù)，在簇頭緩存查詢消息，列出需要聚合的不同數(shù)據(jù)成分。在數(shù)據(jù)傳播階段執(zhí)行分層聚合任務(wù)，聚合點(diǎn)是動態(tài)的，隨源節(jié)點(diǎn)位置的變化而變化，盡可能在靠近源節(jié)點(diǎn)的地方執(zhí)行數(shù)據(jù)聚合任務(wù)，任何具有查詢定義的簇頭或sink節(jié)點(diǎn)都可以選為聚合點(diǎn)。

(2)基于鏈?zhǔn)降木W(wǎng)絡(luò)

基于鏈的數(shù)據(jù)收集協(xié)議將網(wǎng)絡(luò)中所有的節(jié)點(diǎn)構(gòu)成一條鏈，并在鏈上選擇一個節(jié)點(diǎn)作為頭節(jié)點(diǎn)與sink節(jié)點(diǎn)直接通信，鏈兩端數(shù)據(jù)沿鏈傳輸?shù)筋^結(jié)點(diǎn)。基于鏈的數(shù)據(jù)收集協(xié)議減小了分簇算法在簇重構(gòu)過程中所產(chǎn)生的開銷，節(jié)點(diǎn)采用小功率與最近鄰居節(jié)點(diǎn)通信，從而降低了能量的消耗。比較典型的基于鏈的數(shù)據(jù)收集協(xié)議有：PEGASIS。

PEGASIS是在LEACH基礎(chǔ)上建立的一種鏈?zhǔn)降臄?shù)據(jù)收集協(xié)議。該協(xié)議假設(shè)所有節(jié)點(diǎn)都靜止，通過利用貪心算法，能夠以一種中心化的方式形成一條相鄰節(jié)點(diǎn)之間距離最短的鏈。

(3)基于樹結(jié)構(gòu)的網(wǎng)絡(luò)

基于樹的數(shù)據(jù)收集協(xié)議將在基于樹結(jié)構(gòu)的網(wǎng)絡(luò)里，傳感器節(jié)點(diǎn)被組織成一棵樹的結(jié)構(gòu)，非葉子節(jié)點(diǎn)可以執(zhí)行數(shù)據(jù)聚合，沿樹枝路徑把數(shù)據(jù)發(fā)送到根節(jié)點(diǎn)。由于樹結(jié)構(gòu)是支持網(wǎng)絡(luò)連通性的最小圖結(jié)構(gòu)，因此基于樹的數(shù)據(jù)收集協(xié)議能有效保證網(wǎng)絡(luò)的連通性和可靠性，具有保證QoS、容易實(shí)現(xiàn)高效的能量管理等優(yōu)點(diǎn)，是目前研究的熱點(diǎn)。比較典型的基于樹結(jié)構(gòu)的數(shù)據(jù)收集協(xié)議有：MAXLAT、PEDAP等。

MAXLAT算法以一棵擁有最多子樹的生成樹為基礎(chǔ)，不斷轉(zhuǎn)移“瓶頸節(jié)點(diǎn)”的子樹到“非瓶頸節(jié)點(diǎn)”的子樹上去，以此減輕“瓶頸節(jié)點(diǎn)”的負(fù)載，使樹的生命周期最大化。節(jié)點(diǎn)負(fù)載均衡，生命周期最大化。網(wǎng)絡(luò)使用這種生成樹進(jìn)行數(shù)據(jù)收集，不用頻繁地更換樹結(jié)構(gòu)，節(jié)省相應(yīng)的通信和計算費(fèi)用。仿真試驗(yàn)表明，算法能有效延長網(wǎng)絡(luò)生命周期。

PEDAP以兩個節(jié)點(diǎn)間通信代價作為權(quán)值構(gòu)造生成樹，能均衡網(wǎng)絡(luò)中總的能量耗費(fèi)，延長網(wǎng)絡(luò)中最后一個死亡節(jié)點(diǎn)的生命周期。但是沒有考慮節(jié)點(diǎn)剩余能量，容易使具有小能量的節(jié)點(diǎn)死亡。

(4)基于網(wǎng)格的網(wǎng)絡(luò)

在基于網(wǎng)格的聚合機(jī)制里，傳感器網(wǎng)絡(luò)的監(jiān)測環(huán)境被分割為一些網(wǎng)格或區(qū)域。在每一個網(wǎng)格或區(qū)域里選擇一個傳感器，賦予數(shù)據(jù)聚合者的角色，負(fù)責(zé)聚合網(wǎng)格里所有傳感器的數(shù)據(jù)并向sink通報關(guān)鍵信息。網(wǎng)格內(nèi)的傳感器之間不相互通信，直接向本網(wǎng)格的聚合者發(fā)送數(shù)據(jù)。類似于基于簇的數(shù)據(jù)聚合，但網(wǎng)格里的聚合者是固定的，基于網(wǎng)格的數(shù)據(jù)聚合適合于網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化或事件移動的環(huán)境。

3.基于流量優(yōu)化的數(shù)據(jù)收集協(xié)議和算法

目前很多研究者把傳感器網(wǎng)絡(luò)建模為一個有向圖，利用圖論和最優(yōu)化的相關(guān)知識研究傳感器網(wǎng)絡(luò)數(shù)據(jù)收集問題。假設(shè)傳感器網(wǎng)絡(luò)部署在某一區(qū)域，傳感器的位置已知，而且是固定的。一般用有向圖G=(V，E)建模，其中V是節(jié)點(diǎn)集，E是邊(無線鏈路)的集合。近年來提出的基于流量優(yōu)化的網(wǎng)絡(luò)協(xié)議主要有MLDA。

MLDA是一種用于解決傳感器網(wǎng)絡(luò)最大生命期數(shù)據(jù)收集問題的多項式時間次優(yōu)算法，其目標(biāo)是獲得一個最大生命期的數(shù)據(jù)收集調(diào)度。MLDA根據(jù)一階射頻模型建立了傳感器的能量模型，并假設(shè)系統(tǒng)完全連接，每一輪執(zhí)行一次數(shù)據(jù)收集，且每一個傳感器只產(chǎn)生一個數(shù)據(jù)報文，中間節(jié)點(diǎn)能夠把來自多個源的輸入報文聚合成一個簡單的輸出報文。MLDA里提出了一種構(gòu)造聚合樹的啟發(fā)式方法，在每一個數(shù)據(jù)收集輪次，根據(jù)容許流量生成一棵表示數(shù)據(jù)收集調(diào)度的有向樹，數(shù)據(jù)聚合發(fā)生在生成聚合樹之后。但是，在最壞情況下MLDA算法可擴(kuò)展性較差，不適應(yīng)大規(guī)模網(wǎng)絡(luò)的要求。

4.基于移動性的數(shù)據(jù)收集協(xié)議和算法

4.1 存在移動觀測者的數(shù)據(jù)收集算法

這一類網(wǎng)絡(luò)中引入一個或多個移動數(shù)據(jù)觀測者動態(tài)收集數(shù)據(jù)。移動數(shù)據(jù)觀測者可能是一個具有高功率收發(fā)器的移動機(jī)器人或車輛，可視為移動的sink。移動數(shù)據(jù)觀測者從基站開始巡游，穿越網(wǎng)絡(luò)，從附近節(jié)點(diǎn)收集感知數(shù)據(jù)，最后返回遠(yuǎn)程數(shù)據(jù)處理中心更新數(shù)據(jù)。通過利用移動性增強(qiáng)傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸性能，大大減少節(jié)點(diǎn)的能耗。

4.2 基于移動Agent的數(shù)據(jù)收集算法

移動Agent的作用非常類似于移動觀測者，只不過移動的是Agent程序而不是節(jié)點(diǎn)。移動Agent具有傳輸數(shù)據(jù)少、能耗低、可伸縮性好、可靠性高等優(yōu)點(diǎn)，適合于傳感器網(wǎng)絡(luò)數(shù)據(jù)收集應(yīng)用。

5.基于功率控制的數(shù)據(jù)收集協(xié)議和算法

所謂功率控制，就是為傳感器節(jié)點(diǎn)選擇合適的發(fā)射功率。希臘佩特雷大學(xué)(University of Patras)的Kirousis等人將其簡化為發(fā)射范圍分配問題，詳細(xì)討論了該問題的計算復(fù)雜性，證明了功率控制在二維和三維情況下是NP難的。比較典型的功率控制協(xié)議有：TCMNC、TOED、BDL等。功率控制能通過有效降低節(jié)點(diǎn)的發(fā)射功率來延長網(wǎng)絡(luò)的生命周期和調(diào)節(jié)傳輸延遲，但卻沒有很好地考慮空閑偵聽時的能量消耗和覆蓋冗余，在節(jié)點(diǎn)密集網(wǎng)絡(luò)效果不佳。

6.基于睡眠調(diào)度的數(shù)據(jù)收集協(xié)議和算法

所謂睡眠調(diào)度，就是控制傳感器節(jié)點(diǎn)在工作狀態(tài)和睡眠狀態(tài)之間的轉(zhuǎn)換，從而延長網(wǎng)絡(luò)的生命期。根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)間的協(xié)作關(guān)系，比較典型的睡眠調(diào)度協(xié)議有：MLDS、MEC、AELT等。睡眠調(diào)度能使冗余節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)，大幅度地降低網(wǎng)絡(luò)的能量消耗和競爭信道沖突，這對于節(jié)點(diǎn)密集型和事件驅(qū)動型的網(wǎng)絡(luò)十分有效。但它需要在保證網(wǎng)絡(luò)覆蓋的情況下構(gòu)造最優(yōu)的連通支配集，這也一個NP完全的問題。而且，由于節(jié)點(diǎn)存儲能力有限，當(dāng)數(shù)據(jù)采樣率高于節(jié)點(diǎn)喚醒率時，緩沖區(qū)溢出會導(dǎo)致數(shù)據(jù)丟失并重傳，數(shù)據(jù)傳輸延遲很難保證。

7.結(jié)束語

無線傳感器網(wǎng)絡(luò)是信息感知和采集的一場革命，將給人類的生活和生產(chǎn)帶來深遠(yuǎn)影響。無線傳感器網(wǎng)絡(luò)的廣泛使用是一種必然趨勢，將為人類社會帶來極大的變革。目前國內(nèi)外已經(jīng)提出了很多出色的研究方向，但是該領(lǐng)域還是存在許多問題與挑戰(zhàn)，尤其是無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)收集問題，將需要提出更為安全高效的數(shù)據(jù)收集算法。

[1] 解文斌，鮮明，包衛(wèi)東，陳永光.無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集研究[J].計算機(jī)科學(xué)，2008，(8)：35-41.

[2] 周新蓮，吳敏，徐建波.BPEC：無線傳感器網(wǎng)絡(luò)中一種能量感知的分布式分簇算法[J].計算機(jī)研究與發(fā)展，2009，(5)：723-730.

[3] 陳貴海，李成法，葉懋，吳杰.EECS：一種無線傳感器網(wǎng)絡(luò)中節(jié)能的聚類方案[J].計算機(jī)科學(xué)與探索，2007，(1)：170-179.

[4] 龔波，徐建波.無線傳感器網(wǎng)絡(luò)中的新型數(shù)據(jù)收集協(xié)議[J].計算機(jī)工程與應(yīng)用，2009，(6)：113-116.

[5] 余勇昌，韋崗.無線傳感器網(wǎng)絡(luò)中能耗均衡的數(shù)據(jù)收集算法[J].通信技術(shù)，2008，(2)：92-96.

[6] 徐建波，李仁發(fā).無線傳感器網(wǎng)絡(luò)中一種新型的混合型數(shù)據(jù)收集協(xié)議[J].計算機(jī)研究與發(fā)展，2008，(2)：254-260.