陳昆儀，高 宏

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

0 引言

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

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

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

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

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

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

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

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

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

（2）對(duì)于一般的網(wǎng)絡(luò)拓?fù)洌辽傩枰?N個(gè)時(shí)間槽才能完成一個(gè)數(shù)據(jù)收集。文獻(xiàn)［5］中則提出了第一個(gè)在物理沖突模型下的數(shù)據(jù)收集算法。

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

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

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

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

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

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

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

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

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

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

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

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

上述所有算法都是集中式的。然而，集中式的算法很難在現(xiàn)實(shí)無(wú)線傳感器網(wǎng)絡(luò)中應(yīng)用。這是因?yàn)樵趯?shí)際應(yīng)用中，傳感器節(jié)點(diǎn)很容易出現(xiàn)故障，傳感器間的連接也非常不穩(wěn)定，這使得網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化，如果采用固定的聚集樹，則會(huì)有兩種可能：

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

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

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

4 結(jié)束語(yǔ)

研究者們?cè)跓o(wú)線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)收集調(diào)度問(wèn)題上已深耕多年，針對(duì)不同的優(yōu)化目標(biāo)提出了多種有效的算法。對(duì)于這些算法進(jìn)行了總結(jié)，對(duì)其優(yōu)缺點(diǎn)進(jìn)行了分析?？偠灾档蜁r(shí)延，減少能耗，提高網(wǎng)絡(luò)吞吐量依然是無(wú)線傳感器網(wǎng)絡(luò)中數(shù)據(jù)收集算法的核心優(yōu)化目標(biāo)。