陳昆儀，高 宏

（哈爾濱工業(yè)大學 計算學部，哈爾濱 150001）

0 引言

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

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

在無線傳感器網(wǎng)絡中，設計高效數(shù)據(jù)收集算法時需要考慮的重點在于：

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

（2）節(jié)約能量，延長網(wǎng)絡壽命。在傳統(tǒng)有源網(wǎng)絡中，由于電池電量有限，數(shù)據(jù)收集算法中的一個重要目標就是最大化網(wǎng)絡的壽命；

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

1 傳統(tǒng)數(shù)據(jù)收集算法

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

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

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

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

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

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

2 以最小化信息年齡為目標的數(shù)據(jù)收集算法

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

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

由于這些研究不需要考慮轉(zhuǎn)發(fā)問題，因此都不能直接被應用到多跳網(wǎng)絡中。而轉(zhuǎn)發(fā)正是多跳網(wǎng)絡中關鍵所在，也是其與單跳網(wǎng)絡的最大區(qū)別。在許多應用中（如：森林監(jiān)測系統(tǒng)、地下管道監(jiān)測系統(tǒng)等），大量的傳感器被分散地部署在廣闊空間中，使得很多節(jié)點與匯聚節(jié)點之間的距離很遠，在這樣的場景下，每個節(jié)點和匯聚節(jié)點之間都使用單跳傳輸?shù)姆绞酵ㄐ攀遣滑F(xiàn)實的，這會帶來極大的誤碼率和丟包率。

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

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

3 數(shù)據(jù)聚集算法

在一些無線傳感器網(wǎng)絡應用中，sink 所承擔的計算任務是已知的。在一些監(jiān)測系統(tǒng)中，用戶只關注感知數(shù)據(jù)的統(tǒng)計數(shù)據(jù)，如被監(jiān)測區(qū)域的平均溫度、加速度的最大值等等。

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

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

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

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

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

4 結束語

研究者們在無線傳感器網(wǎng)絡中的數(shù)據(jù)收集調(diào)度問題上已深耕多年，針對不同的優(yōu)化目標提出了多種有效的算法。對于這些算法進行了總結，對其優(yōu)缺點進行了分析?？偠灾?，降低時延，減少能耗，提高網(wǎng)絡吞吐量依然是無線傳感器網(wǎng)絡中數(shù)據(jù)收集算法的核心優(yōu)化目標。