無線傳感器網絡中數據收集算法研究綜述

陳昆儀，高 宏

（哈爾濱工業大學 計算學部，哈爾濱 150001）

0 引言

隨著WIFI、藍牙、LoRa、NBIoT 等無線通信技術的發展以及嵌入式系統、分布式計算系統的成熟，萬物互聯、智慧城市的愿景成為可能，使得物聯網（Internet-of-things）成為國內外關注的熱點。無線傳感器網絡是物聯網的重要組成部分，一個無線傳感器網絡往往由幾個到幾千個無線傳感器節點和一個或多個sink 節點構成，這些無線傳感器節點能夠從物理世界中采集溫度、濕度、照片等數據，并將這些數據通過無線傳輸以一跳或多跳的方式上傳到匯聚節點上。無線傳感器網絡在環境監測、軍事監測、交通監測以及結構健康監測等領域具有廣泛的發展和應用前景。

感知數據的采集與傳輸是無線傳感器網絡的基本任務，高效的數據收集一直是學術界與工業界關注的重點問題。受成本、電量和信道資源的限制，無線傳感器節點一般采用WiFi、藍牙等短距離通信技術，只能與鄰近的節點進行通信，一個感知數據包往往需要經過多次轉發才能到達匯聚節點。無線傳感器網絡中的數據收集，是指為每個節點安排合適的傳輸路徑以及傳輸時刻，保證數據包被sink 節點成功接收。

在無線傳感器網絡中，設計高效數據收集算法時需要考慮的重點在于：

（1）避免無線傳輸沖突，避免重傳。在無線傳感器網絡中收集數據時，為了提高數據傳輸效率，往往令網絡中的多個節點同時進行數據傳輸，無線信號之間不可避免地會相互疊加和干擾。當信號的信噪比小于一定的閾值時，接收節點就無法解析信號，造成丟包和重傳。因此，在設計數據傳輸算法時，關鍵在于保證同時進行的數據傳輸間不會相互沖突；

（2）節約能量，延長網絡壽命。在傳統有源網絡中，由于電池電量有限，數據收集算法中的一個重要目標就是最大化網絡的壽命；

（3）利用節點自身的計算功能，降低需要傳輸的數據量。由于傳感器節點的傳輸能耗遠大于其計算能耗，一個傳感器節點傳輸1 比特信息100 m 距離所需要的能量大約相當于執行3 000 條計算指令消耗的能量。因此，當計算任務已知時，可以采取“邊傳輸邊計算”的方式來降低數據量，進而提高傳輸效率。

1 傳統數據收集算法

在傳統有源網絡中，已經有一些數據收集算法被提出。如：文獻［1］證明了在協議沖突模型下，以最小化延時為目標的數據收集問題是NP-難的。為解決該問題，文獻［2］中對線型網絡、樹形網絡以及一般網絡的拓撲分布，給出了集中式的調度算法。文獻［3］以同時最小化數據傳輸的時間利用效率和能量利用效率為目標，在協議沖突模型下，給出了一個分布式數據收集算法。文獻［4］分別對樹形網絡和一般網絡，提出了分布式的數據收集算法，并證明：

（1）對于一個樹形網絡，至少需要max｛3nk -1，N｝個時間槽才能完成一次數據收集（nk是以sink的一跳鄰居為根的最大子樹中節點數量，N是網絡中節點數量）；

（2）對于一般的網絡拓撲，至少需要3N個時間槽才能完成一個數據收集。文獻［5］中則提出了第一個在物理沖突模型下的數據收集算法。

為了降低需要傳輸的數據量，進而提高效率，研究人員提出在節點內使用數據壓縮技術來解決此問題。數據壓縮技術可以分為無損壓縮的數據收集算法［6］和有損壓縮的數據收集算法［7］。現有的基于無損壓縮的數據收集算法，主要依賴壓縮感知技術。在壓縮感知理論下，當數據在某組基底下存在稀疏表達時，數據可以被有效地壓縮，并通過解最優化方程的方法，可將原始數據進行精確地恢復［8］。感知數據往往具有時間相關性和空間相關性，已經有大量的理論和實驗表明，感知數據在離散余弦變換、傅里葉變換及小波變換的基底下，存在稀疏表達［9］。文獻［6］是第一篇將壓縮感知技術應用到多跳有源網絡中數據收集問題的論文，文中給出的理論分析及實驗結果表明，在保證sink 端能夠對原始感知數據進行準確恢復的前提下，可以大大降低網絡整體數據傳輸量，且不會在節點端引入大量的計算代價或復雜的控制信息交換。此外，基于壓縮感知理論的數據收集算法可以使網絡中各節點的工作負載均衡，有效地延長了網絡壽命。為了進一步降低網絡中需要傳輸的數據量，文獻［10］提出了基于混合壓縮感知技術的數據收集算法Hybrid-CS，該算法中只在部分節點執行壓縮感知算法。即對于其中的每個節點vi，只有當其轉發的原始數據項量大于M -1 時（M為壓縮感知因子，取決與感知數據的稀疏性。），或是需要轉發的數據中包含壓縮感知向量時，才會執行壓縮感知算法；否則只轉發數據，不做任何壓縮處理。而在文獻［10］中，只是將Hybrid CS的調度問題形式化成一個優化問題，并提出了一個集中式的離線算法來解決這個問題。但由于離線的、集中式的數據收集算法魯棒性較差，并且需要匯聚節點不斷地與各個節點交換信息，因此不適合在現實無線傳感網中使用。文獻［11］中也提出了一個類似集中式的數據收集算法。該算法將壓縮感知技術與數據傳輸相結合，其目標是最小化總體的能量消耗。并且以兩個節點之間的能量消耗作為網絡中邊的權重，建立一棵以匯聚節點為根的數據收集樹，每個節點沿著樹上的路徑來完成數據傳輸。

文獻［7］提出了基于有損壓縮的數據收集算法，其基本想法是將感知數據序列看成時間序列，接著對這些時間序列做壓縮。例如：采用數值逼近理論，也就是用多項式函數來擬合感知數據，之后向sink 節點傳輸擬合多項式的參數而不是原始的感知數據；或者采用統計學的理論，用Piece-wise 常數近似方法或主成分分析方式來壓縮這些感知數據。

在實際的物聯網應用中，收集感知數據的目的是為了下一步的分析和決策，往往需要對感知數據提取特征。但在現有的近似數據收集算法中，只保證了原始傳感器數據和解壓后的數據的差距小于一個給定的閾值，并沒有保證基于原始感知數據提取的數據特征與從解壓縮數據提取出來的數據特征之間的差距，很有可能出現由于前面的有損壓縮給后續分析帶來極大的困難，甚至很可能由于關鍵信息被抹去，使得后續的分析無法進行。例如，在基于加速度數據的電梯異常檢測應用中，相比于正常運行的電梯，故障電梯的加速度會呈現出一些細小的波動。但如果采用近似數據收集的算法，這些細小的波動將會被移除，則無法從近似的感知數據中檢測到電梯故障，使之造成事故的發生。

2 以最小化信息年齡為目標的數據收集算法

文獻［12］中提出的信息年齡（Age of Information，AoI），是描述信息新鮮性度的量。在許多監測應用中，節點需要向感興趣的接收方（一般是匯聚節點）發送關于被監測對象當前狀態的數據，匯聚節點每收到一個監測對象的數據更新包，就對該對象當前的狀態做一次更新。對于一個監測對象i，AoI指的是當前時刻t與上一次匯聚節點接收到該監測對象感知數據采集時刻glast（t）的差值，即AoIi（t）＝ t -glast（t）。

近來年，以最小化AoI為目標的數據收集算法，在傳統有源網絡中已有許多相關研究結果被發表。在該領域，從環境中采集關于監測對象的數據，并生成數據更新包的節點被稱為源節點。大多數已有研究針對的均是單跳網絡，即網絡中的每個節點都可通過一跳傳輸，向匯聚節點發送數據。在此場景下，其研究的問題可以簡化成為每個源節點安排產生數據更新包的時刻，并且決定何時激活源節點和匯聚節點之間的邊，以進行數據傳輸。文獻［13］中證明：即使在單跳網絡中、在物理沖突模型下，以最小化AoI為目標的數據收集問題是NP-Hard 的。文獻［14］中，針對最小化峰值AoI和最小化均值AoI數據收集問題，提出了一個基于靜態調度原則的算法，并證明了當假定解空間為所有基于靜態調度原則算法的前提下，該調度算法可以實現峰值AoI最小化；對于均值AoI，該算法取得的均值AoI和最優的AoI的差距在一個常數因子之內。在單跳網絡中，除了數據收集問題，AoI最優化問題也在其它方向被研究，其中包括：數據包生成控制［12］、隊列控制［15］以及鏈路調度規則［14］等研究。

由于這些研究不需要考慮轉發問題，因此都不能直接被應用到多跳網絡中。而轉發正是多跳網絡中關鍵所在，也是其與單跳網絡的最大區別。在許多應用中（如：森林監測系統、地下管道監測系統等），大量的傳感器被分散地部署在廣闊空間中，使得很多節點與匯聚節點之間的距離很遠，在這樣的場景下，每個節點和匯聚節點之間都使用單跳傳輸的方式通信是不現實的，這會帶來極大的誤碼率和丟包率。

因此，研究者們開始在多跳的無源網絡中設計以最小化AoI為目標的數據收集算法。文獻［16］中關注了一個簡單的問題空間。假設網絡中的每條鏈路只能遵循某一個固定的概率分布函數被激活，該如何選擇最優的概率分布函數。在此設置下，文中推導出了最優的概率分布。文獻［17］中考慮的情景是：網絡中的節點被分割成固定的對，每一對中有一個發送者和一個接受者，發送者周期性地向接收者發送數據。文中研究是在吞吐量下界給定的約束下，如何最小化峰值AoI和均值AoI的問題，并給出了一個集中式的偽多項式時間復雜度算法。文獻［18］中考慮的場景是：網絡中的每個節點既是源節點又是監測者，即每個節點都在本地維護網內所有節點的AoI曲線。在此場景下，所有節點都會接收到來自其它節點的數據更新包。以此設定，作者推導出在協議沖突模型以及物理沖突模型下，峰值AoI和均值AoI的下界。

然而，上面提到的研究中都存在明顯的缺陷。如：文獻［16］中，網絡中的每一條鏈路都會以一定的概率被激活，這個概率服從一個固定的概率分布函數。一個數據包在鏈路上被成功地傳遞，當且僅當在該鏈路被激活的時刻，所有與其產生沖突的鏈路都沒有被激活。因此，在節點密度較大的情況下，這個調度算法的效率會非常低下。而且，算法中每個節點到sink 節點的傳輸路徑都是固定的。當一個節點被損壞后，這些更新包都會丟失。文獻［17］則忽略了對數據包生成時刻的控制，而數據包的生成時刻直接影響著AoI的大小。文獻［18］考慮的是一個非常特殊的情形，而在大多數場景下，都認為網絡中的節點是源節點，而匯聚節點是唯一的監督者。

3 數據聚集算法

在一些無線傳感器網絡應用中，sink 所承擔的計算任務是已知的。在一些監測系統中，用戶只關注感知數據的統計數據，如被監測區域的平均溫度、加速度的最大值等等。

此外，由于存在原始感知數據的總量遠大于統計數據的量（如1 000 個溫度值的最大值只有一個），且傳感器節點的傳輸功耗遠高于其計算功耗（傳輸1 比特信息100 m 距離所需要的能量大約相當于執行3 000條計算指令消耗的能量［19］）的情況，研究者們提出了將數據收集與計算相融合的方法。即當節點收到來自其它節點的感知數據時，在節點內部進行聚集操作（如求平均值、最大值等），以此降低需要傳輸的數據量，進而降低傳輸延時與能耗。上述的處理過程，稱為數據聚集。在傳統的有源無線傳感器網絡中，最小化聚集延時調度（Minimum Latency Aggregation Scheduling，MLAS）是一個經典的問題，已經有大量的算法被提出。在有源網絡中，默認每個節點在任意時刻都有足夠的能量可用于數據傳輸。在此假設下，MLAS 問題已被證明是一個NP-難的問題［20］。文獻［20］中構造了一棵以sink 節點為根的最短路樹作為數據聚集樹，并給出了一個延時上界Δ -1 的集中式算法。文獻［21］中提出了一種基于平衡的最短路樹的算法，并證明該算法取得了更好的性能。文獻［22］提出了一種基于最小聯通支配集的數據聚集樹，做調度時采用最先適配（First-Fit）原則。在這個設置下，給出了一個延時上界為23R ＋Δ -18 的集中式算法，其中R表示網絡的寬度，即距離基站最遠的節點和sink 節點之間的跳數。文獻［22］提出了一個優化的最先適配原則，將時延的上界降到了16R ＋Δ -11。文獻［23］中提出了一個更先進的基于聯通支配聚集樹的調度算法，該算法延時的上界為

上述所有算法都是集中式的。然而，集中式的算法很難在現實無線傳感器網絡中應用。這是因為在實際應用中，傳感器節點很容易出現故障，傳感器間的連接也非常不穩定，這使得網絡的拓撲結構動態變化，如果采用固定的聚集樹，則會有兩種可能：

（1）假設所有數據聚集周期都使用同樣的聚集樹，由于網絡拓撲變化，樹上的鏈路發生斷裂，數據無法被成功地傳遞到sink 節點；

（2）如果在每一輪數據聚集前都將節點的拓撲信息傳遞到sink 節點，sink 節點執行數據收集算法，再將所有的傳輸調度方案傳遞到對應的各個節點。雖然這個方案是可行的，但效率非常低下。因為在每一輪數據聚集前，sink 節點都需要將調度信息發送給每一個節點，這些調度信息的傳輸會帶來大量附加的能量、時間和信道資源的開銷。文獻［24］提出了第一個分布式算法，并證明了算法聚集延時的上界為48R ＋6Δ ＋16。隨后，文獻［25］將此算法做了進一步改進。

在占空比傳感網中，每個節點按照一定的周期休眠或工作，MLAS 問題已在許多文獻中被研究。如：文獻［26］研究了在每個調度周期里，每個節點只工作在一個時間槽的情況，并提出了一個集中式的算法。文獻［27］中，假設每個節點在一個調度周期內有多個時間槽可用于工作，并提出了一個時延上界為（15R ＋Δ -3）×T的算法（T是一個聚集周期的時間長度）。文獻［28］提出了一個分布式算法，在此一個節點的所有鄰居都是其候選父節點。實驗結果表明，此算法優于前兩種算法。然而，由于無源網絡中的延時主要來自于無源節點能量的不足，因此這些算法都不能直接用于無源傳輸網絡。

4 結束語

研究者們在無線傳感器網絡中的數據收集調度問題上已深耕多年，針對不同的優化目標提出了多種有效的算法。對于這些算法進行了總結，對其優缺點進行了分析。總而言之，降低時延，減少能耗，提高網絡吞吐量依然是無線傳感器網絡中數據收集算法的核心優化目標。