戴振華 王建新

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

1.前言

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

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

2.基于結構化的數據收集協(xié)議和算法

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

2.1 平坦型(Flat)網絡

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

2.2 層次型(Hierarchical)網絡

層次型結構通過在網絡里選舉某些節(jié)點作為簇頭或增加少數高能量的節(jié)點，把整個網絡自組織成不同的層次，增強了擴展性。

(1)基于簇結構的網絡

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

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

HEED的主要目標是通過高效成簇，將能耗均勻分布到整個網絡從而最大化網絡生命期。HEED的簇頭選擇主要依據主、次兩個參數。HEED的主要改進是：在簇頭選擇中考慮了節(jié)點的剩余能量，并以主從關系引入了多個約束條件作用于簇頭的選擇過程，HEED在簇頭選擇標準以及簇頭競爭機制上都與LEACH不同。實驗結果表明，HEED分簇速度更快，能產生更加分布均勻的簇頭、更合理的網絡拓撲。

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

(2)基于鏈式的網絡

基于鏈的數據收集協(xié)議將網絡中所有的節(jié)點構成一條鏈，并在鏈上選擇一個節(jié)點作為頭節(jié)點與sink節(jié)點直接通信，鏈兩端數據沿鏈傳輸到頭結點?；阪湹臄祿占瘏f(xié)議減小了分簇算法在簇重構過程中所產生的開銷，節(jié)點采用小功率與最近鄰居節(jié)點通信，從而降低了能量的消耗。比較典型的基于鏈的數據收集協(xié)議有：PEGASIS。

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

(3)基于樹結構的網絡

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

MAXLAT算法以一棵擁有最多子樹的生成樹為基礎，不斷轉移“瓶頸節(jié)點”的子樹到“非瓶頸節(jié)點”的子樹上去，以此減輕“瓶頸節(jié)點”的負載，使樹的生命周期最大化。節(jié)點負載均衡，生命周期最大化。網絡使用這種生成樹進行數據收集，不用頻繁地更換樹結構，節(jié)省相應的通信和計算費用。仿真試驗表明，算法能有效延長網絡生命周期。

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

(4)基于網格的網絡

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

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

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

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

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

4.1 存在移動觀測者的數據收集算法

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

4.2 基于移動Agent的數據收集算法

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

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

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

6.基于睡眠調度的數據收集協(xié)議和算法

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

7.結束語

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

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

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

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

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

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

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