WSN中一種基于多sink的快速數(shù)據(jù)收集算法

鄭凱津

ZHENG Kaijin

天津市信息中心，天津 300201

1 引言

綜合了無線通信技術(shù)、傳感器技術(shù)、嵌入式計(jì)算技術(shù)和分布式信息處理技術(shù)的無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN），是目前國際上前沿?zé)狳c(diǎn)的研究領(lǐng)域。傳感器節(jié)點(diǎn)能夠協(xié)作地實(shí)時監(jiān)測、感知網(wǎng)絡(luò)區(qū)域內(nèi)各種信息，然后以多跳的方式將這些信息傳送給遠(yuǎn)方的基站（Sink）[1]。無線傳感器網(wǎng)絡(luò)在工作過程中，節(jié)點(diǎn)會不斷地感知到周邊環(huán)境的數(shù)據(jù)。而在無線傳感器網(wǎng)絡(luò)任何一個應(yīng)用中，用戶都需要獲取相應(yīng)的數(shù)據(jù)進(jìn)行處理。采集網(wǎng)絡(luò)中用戶需要的數(shù)據(jù)，就被稱為數(shù)據(jù)收集[2]。數(shù)據(jù)收集是無線傳感器網(wǎng)絡(luò)中最重要的操作之一，能否有效地采集到合適的數(shù)據(jù)，直接關(guān)系到應(yīng)用的效果。為了使網(wǎng)絡(luò)能長時間地工作，在進(jìn)行數(shù)據(jù)收集時必須有效地降低節(jié)點(diǎn)能耗以保存能量。此外，網(wǎng)絡(luò)還需要提供延遲保證和容錯性等能力以滿足用戶的需要。但是，受到節(jié)點(diǎn)有限的性能以及網(wǎng)絡(luò)動態(tài)性等因素的影響，目前已有的數(shù)據(jù)收集協(xié)議還無法有效應(yīng)用。因此，對網(wǎng)絡(luò)中的數(shù)據(jù)收集協(xié)議進(jìn)行研究，具有重要的理論意義和應(yīng)用價值。

2 相關(guān)工作

數(shù)據(jù)收集問題一直是WSN中的一大研究熱點(diǎn)。相繼有眾多的學(xué)者提出了一系列方法用于無線傳感網(wǎng)中數(shù)據(jù)收集的方法[3-13]，如潘文虎等[3]提出一種改進(jìn)的MWSF算法。該算法結(jié)合A*算法求解出移動Sink在傳感器節(jié)點(diǎn)之間移動的最短路徑，利用MWSF算法找到移動Sink所需訪問的下一個傳感器節(jié)點(diǎn)，并與單跳通信范圍內(nèi)的其他傳感器節(jié)點(diǎn)進(jìn)行通信，從而收集數(shù)據(jù)。仿真結(jié)果表明，該算法能降低數(shù)據(jù)溢出發(fā)生率，提高網(wǎng)絡(luò)的數(shù)據(jù)傳輸效率；袁凌云等[4]針對無線傳感器網(wǎng)絡(luò)應(yīng)用于突發(fā)事件監(jiān)測場景的能量消耗和網(wǎng)絡(luò)延遲問題，提出了基于移動Agent的無線傳感器網(wǎng)絡(luò)簇式數(shù)據(jù)收集算法。該算法基于事件嚴(yán)重程度來動態(tài)成簇，并由其決定簇的生命周期和覆蓋范圍。Sink和簇頭之間形成以Sink節(jié)點(diǎn)為簇頭的虛擬簇，提出了基于移動Agent遷移路徑規(guī)劃來完成對所有簇內(nèi)成員節(jié)點(diǎn)信息的收集。仿真結(jié)果表明，相對于C/S數(shù)據(jù)收集模型，該算法具有更好的節(jié)能效果，并能一定程度地減少網(wǎng)絡(luò)延遲，尤其適用于大規(guī)模無線傳感器網(wǎng)絡(luò)應(yīng)用；閆宇博等[5]針對不可靠低輪值無線傳感器網(wǎng)絡(luò)所具有的特性，綜合考慮了不可靠鏈路和低輪值的影響，給出了糾刪編碼在多條路徑上的分配策略，從而在保證能量效率和較高遞交率的前提下極大地減少了遞交時延。仿真分析表明提出的算法以遞交率輕微降低的代價獲取了遞交時延的顯著下降。

另外，陳濤等[6]針對傳統(tǒng)的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議大多受制于發(fā)生在基站周圍的熱點(diǎn)問題，提出了一種使用移動基站的數(shù)據(jù)收集方法。將數(shù)據(jù)收集問題轉(zhuǎn)化為支配集構(gòu)造和旅行商問題，并提出了一種分布式的支配集構(gòu)建算法，結(jié)合旅行商問題的近似算法生成基站的移動路線。仿真結(jié)果表明，所提出的方法減少了通信消耗，且能使負(fù)載均衡地分布；為了在無線傳感器網(wǎng)絡(luò)中降低能耗和最大化網(wǎng)絡(luò)生存期，楊靖等[7]提出一種能量高效的數(shù)據(jù)收集算法。該算法利用移動代理模型在網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)收集。首先，根據(jù)監(jiān)測精度的要求控制活動節(jié)點(diǎn)的數(shù)量；然后，通過求最小支配集得到具體的工作節(jié)點(diǎn)；最后，利用蟻群算法規(guī)劃移動代理遷移的最優(yōu)路線，移動代理以漸進(jìn)方式收集活動節(jié)點(diǎn)的監(jiān)測數(shù)據(jù)。仿真結(jié)果表明，與典型算法相比，該算法具有更低的能耗和更長的網(wǎng)絡(luò)生存期。本文在現(xiàn)有工作的基礎(chǔ)上，針對時間響應(yīng)和數(shù)據(jù)準(zhǔn)確度要求高的應(yīng)用，提出了一種快速數(shù)據(jù)收集方法，并通過仿真實(shí)驗(yàn)驗(yàn)證了本文方法的有效性。

3 系統(tǒng)模型

本文研究的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集問題限定于以下假設(shè)：

（1）無線傳感器網(wǎng)絡(luò)具有多個sink節(jié)點(diǎn)，節(jié)點(diǎn)部署后不再移動，在多sink節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)中有n個普通節(jié)點(diǎn)，有k個基站節(jié)點(diǎn)，網(wǎng)絡(luò)劃分為l個子網(wǎng)格。網(wǎng)絡(luò)中任意兩個sink節(jié)點(diǎn)之間可以互相直接通信，任意一個節(jié)點(diǎn)可以與其鄰居節(jié)點(diǎn)互相直接通信。每個節(jié)點(diǎn)在某一個時刻可以接收或發(fā)送數(shù)據(jù)，并且在同一個時刻只能接收到一個鄰居節(jié)點(diǎn)的消息，如果同一時刻兩個鄰居節(jié)點(diǎn)同時發(fā)送，將容易造成沖突。網(wǎng)絡(luò)模型如圖1所示。

圖1 WSN網(wǎng)絡(luò)結(jié)構(gòu)示意圖

（2）無線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)通過一個有向圖G={V，S，E}來表示。其中V代表l個網(wǎng)格組成的集合，S代表k個sink節(jié)點(diǎn)的集合，E?V×(V+S)代表邊的集合，邊eij=1表示網(wǎng)格Ci和網(wǎng)格Cj相鄰可以直接進(jìn)行通信，亦表明網(wǎng)格Ci中存在節(jié)點(diǎn)是網(wǎng)格Cj中節(jié)點(diǎn)的通信鄰居，反之eij=0。假設(shè)任意兩個網(wǎng)格i和 j之間的通信關(guān)系具有對稱性，即eij=eji。定義A為圖G的鄰接矩陣。該矩陣表示為下面的形式，該矩陣分為A1和A2兩部分，A1代表網(wǎng)格區(qū)域之間通信關(guān)系，A2代表網(wǎng)格與sink節(jié)點(diǎn)的通信關(guān)系。每個網(wǎng)格i對應(yīng)的度D(i)代表該網(wǎng)格的鄰居網(wǎng)格數(shù)目。N(i)代表該網(wǎng)格內(nèi)節(jié)點(diǎn)數(shù)。相鄰?fù)ㄐ啪W(wǎng)格之間的通信時間為τ。相鄰節(jié)點(diǎn)之間通信時間為t。數(shù)據(jù)收集響應(yīng)時間為ω。

（3）無線傳感器網(wǎng)絡(luò)中任意節(jié)點(diǎn)i的能耗可以表示為：Ei=Ei-MCU+Ei-TCR+Ei-SB。其中Ei-MCU表示節(jié)點(diǎn)i上微控制單元的能耗；Ei-SB表示節(jié)點(diǎn)i上中央處理器的計(jì)算能耗；Ei-TCR則表示節(jié)點(diǎn)i收發(fā)數(shù)據(jù)的通信能耗。Ei-TCR可以進(jìn)一步表示為：Ei-TCR=Ei-TCR-RX+Ei-TCR-TX(di)。其中Ei-TCR-RX表示節(jié)點(diǎn)i接收數(shù)據(jù)的能耗；Ei-TCR-TX(di)表示節(jié)點(diǎn)i發(fā)送數(shù)據(jù)的能耗，它是一個關(guān)于距離di的函數(shù)，節(jié)點(diǎn)i發(fā)送的數(shù)據(jù)與接收節(jié)點(diǎn)的距離越大，能耗也越大?；谝陨戏治觯瑢τ谝粋€擁有N個節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)的總能耗可以表示為：

其中C1為常數(shù)，假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)傳輸?shù)穆窂剿p因子為2，則有：

其中Ei-TCR-EC和Ei-TCR-PA分別表示節(jié)點(diǎn)i發(fā)送數(shù)據(jù)時的電子電路和功率放大所導(dǎo)致的能量消耗，它們是一個常數(shù)。因此，公式（2）可以表示為：

其中，C2和C3為常數(shù)。

4 快速數(shù)據(jù)收集算法

本文提出的快速數(shù)據(jù)收集算法（QDGA）是一種分層集中式與局部自適應(yīng)相結(jié)合的方法。首先充分利用sink節(jié)點(diǎn)的無需考慮能量消耗，并且通信能力和計(jì)算能力強(qiáng)的特點(diǎn)，集中式計(jì)算出全局最優(yōu)的粗粒度并行數(shù)據(jù)收集策略。同時為了使得數(shù)據(jù)收集的算法不受節(jié)點(diǎn)失效、局部通信鏈路失效的影響，在并行數(shù)據(jù)收集任務(wù)分發(fā)和數(shù)據(jù)收集過程中，有效利用局部信息進(jìn)行自適應(yīng)的調(diào)整，從而有效避免單個節(jié)點(diǎn)失效時數(shù)據(jù)收集失敗。一個數(shù)據(jù)收集任務(wù)進(jìn)行計(jì)算后從全局可以看成是一個基于網(wǎng)格的收集森林{T1，T2，…}，每個序列Ti代表了一條數(shù)據(jù)收集的分支樹，根節(jié)點(diǎn)為sink節(jié)點(diǎn)。而網(wǎng)格內(nèi)部數(shù)據(jù)收集任務(wù)由根據(jù)網(wǎng)格內(nèi)部的節(jié)點(diǎn)發(fā)起網(wǎng)格內(nèi)進(jìn)行響應(yīng)的數(shù)據(jù)收集。本文中涉及的是所有監(jiān)測區(qū)域的融合數(shù)據(jù)收集，原始數(shù)據(jù)收集在以后的工作中進(jìn)一步研究。

QDGA算法分成兩個階段：

（1）sink節(jié)點(diǎn)計(jì)算數(shù)據(jù)收集策略階段。sink節(jié)點(diǎn)接收到一個數(shù)據(jù)收集命令時，在保證數(shù)據(jù)收集的準(zhǔn)確性和完整性的前提下，盡可能地利用所有sink節(jié)點(diǎn)，計(jì)算出符合并行收集數(shù)據(jù)要求的策略，以加快數(shù)據(jù)收集的效率。在該階段的數(shù)據(jù)收集策略基于sink節(jié)點(diǎn)對全局網(wǎng)格信息進(jìn)行最優(yōu)分配，即該數(shù)據(jù)收集策略是基于網(wǎng)格粒度的。

（2）任務(wù)分發(fā)與數(shù)據(jù)收集階段。此過程中各個網(wǎng)格接收到相應(yīng)數(shù)據(jù)收集子任務(wù)，并可根據(jù)自身的局部信息進(jìn)行網(wǎng)格內(nèi)的數(shù)據(jù)收集，動態(tài)調(diào)整數(shù)據(jù)收集路徑。該階段主要是利用局部信息有效避免節(jié)點(diǎn)失效引發(fā)的空洞等問題。

4.1 基站集中式計(jì)算階段

網(wǎng)絡(luò)中存在多個sink節(jié)點(diǎn)，數(shù)據(jù)收集任務(wù)可以劃分成若干個子任務(wù)，然后分發(fā)給各個sink節(jié)點(diǎn)進(jìn)行并行處理。首先是接收到收集任務(wù)的sink節(jié)點(diǎn)利用全局的信息構(gòu)建基于網(wǎng)格粒度的收集森林，森林的構(gòu)建遵循最小度的BFS算法。整個森林構(gòu)建過程時間復(fù)雜度為O(m)。

算法1網(wǎng)格粒度數(shù)據(jù)收集森林構(gòu)造算法

輸入 數(shù)據(jù)收集任務(wù)Q和網(wǎng)絡(luò)的連接矩陣A。

輸出 收集森林 F={T1，T2，…}，每個Ti代表一棵以sink節(jié)點(diǎn)為根節(jié)點(diǎn)的網(wǎng)格粒度收集樹

（1）根據(jù)查詢條件構(gòu)造出包含數(shù)據(jù)收集區(qū)域的網(wǎng)格集合SetI，收集范圍為整個網(wǎng)絡(luò)SetI=V

（2）構(gòu)造數(shù)據(jù)收集森林

（3）全局分析

4.2 任務(wù)分發(fā)和數(shù)據(jù)收集階段

各個sink節(jié)點(diǎn)接收到以自己為根節(jié)點(diǎn)數(shù)據(jù)收集樹后進(jìn)行收集任務(wù)的分發(fā)。該樹既可以作為數(shù)據(jù)收集任務(wù)下發(fā)的基礎(chǔ)也可以作為數(shù)據(jù)收集返回的基礎(chǔ)。

各個網(wǎng)格收到了相應(yīng)的分發(fā)任務(wù)就會根據(jù)消息進(jìn)行收集任務(wù)的分發(fā)，分發(fā)完成之后再進(jìn)行自己網(wǎng)格內(nèi)的數(shù)據(jù)收集。在整個數(shù)據(jù)收集任務(wù)下發(fā)過程中要經(jīng)過LEVEL層，LEVEL不會超過ln(m)，而每個網(wǎng)格的子網(wǎng)格的度不超過max(d(i))，因此下發(fā)的時間復(fù)雜度是O(ln(m)×max(d(i)))。數(shù)據(jù)收集任務(wù)分發(fā)偽代碼描述見算法2。

算法2收集任務(wù)分發(fā)算法

當(dāng)數(shù)據(jù)收集結(jié)果返回時，各個網(wǎng)格會收到孩子網(wǎng)格的融合數(shù)據(jù)結(jié)果，并進(jìn)一步進(jìn)行合并返回給父親網(wǎng)格，最終返回給sink節(jié)點(diǎn)。這個過程中的時間消耗與任務(wù)分發(fā)的時間消耗也是O(ln(m)×max(d(i)))。

算法3網(wǎng)格間數(shù)據(jù)收集算法

當(dāng)收集任務(wù)分發(fā)下去之后，將進(jìn)行自己網(wǎng)格內(nèi)部的數(shù)據(jù)收集。進(jìn)行網(wǎng)格內(nèi)數(shù)據(jù)收集時，每個網(wǎng)格中的節(jié)點(diǎn)數(shù)目相對較少，網(wǎng)格內(nèi)的節(jié)點(diǎn)可以相對實(shí)時地保存網(wǎng)格內(nèi)的節(jié)點(diǎn)信息和相應(yīng)的鄰居信息，并可以根據(jù)局部的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化選擇相應(yīng)的時隙分配。發(fā)起網(wǎng)格內(nèi)數(shù)據(jù)收集的節(jié)點(diǎn)，可以在以自己為根節(jié)點(diǎn)的BFS樹的基礎(chǔ)上，通過多信道時隙分配來進(jìn)行網(wǎng)格內(nèi)數(shù)據(jù)收集。網(wǎng)格內(nèi)的節(jié)點(diǎn)數(shù)據(jù)收集時隙分配偽代碼描述見算法4。

算法4網(wǎng)格內(nèi)數(shù)據(jù)收集算法

算法結(jié)束后，標(biāo)記的最大值則為網(wǎng)格內(nèi)數(shù)據(jù)收集最多時隙。各個節(jié)點(diǎn)按照時隙分配進(jìn)行數(shù)據(jù)發(fā)送。網(wǎng)格內(nèi)的數(shù)據(jù)收集時隙數(shù)目不會超過網(wǎng)格內(nèi)的節(jié)點(diǎn)數(shù)目。時間消耗最多為O(N(i))。

在數(shù)據(jù)收集任務(wù)下發(fā)和數(shù)據(jù)收集的過程中，每個網(wǎng)格內(nèi)的所有節(jié)點(diǎn)均能收到下行網(wǎng)格和上行網(wǎng)格的代表節(jié)點(diǎn)發(fā)送過來的任務(wù)消息和數(shù)據(jù)消息。只要網(wǎng)格內(nèi)還存在未失效的節(jié)點(diǎn)，則不會影響該網(wǎng)格的數(shù)據(jù)收集的分發(fā)和收集執(zhí)行?？梢钥闯隼霉?jié)點(diǎn)的冗余保證了數(shù)據(jù)收集處理不易受節(jié)點(diǎn)失效的影響。同時在這個過程中，如果按照原有方式出現(xiàn)了突發(fā)的空洞或者鏈路失效的問題，任務(wù)下發(fā)和數(shù)據(jù)返回可以自適應(yīng)調(diào)整發(fā)送路徑。數(shù)據(jù)收集的路徑可以在收集過程中自適應(yīng)生成，能有效地消除通信鏈路失效和節(jié)點(diǎn)移動的影響。并且在數(shù)據(jù)回收過程中保存了數(shù)據(jù)回收路徑，當(dāng)最終返回到sink節(jié)點(diǎn)時這些信息可以為sink節(jié)點(diǎn)對基于網(wǎng)格的全局網(wǎng)絡(luò)結(jié)構(gòu)維護(hù)提供依據(jù)，限于篇幅，該部分的內(nèi)容在本文中不再闡述。

5 仿真實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)場景如下：N個傳感器節(jié)點(diǎn)被隨機(jī)分布M大小的監(jiān)測區(qū)域內(nèi)，N的個數(shù)在50到350之間取值；M的大小為（125 m，125 m）～（300 m，300 m）。節(jié)點(diǎn)間的同步通過物理層和數(shù)據(jù)鏈路層來實(shí)現(xiàn)。實(shí)驗(yàn)參數(shù)設(shè)置為：每個節(jié)點(diǎn)的初始能量為50 J；節(jié)點(diǎn)接收和發(fā)送單位數(shù)據(jù)的能耗都為50×10-6J/bit；節(jié)點(diǎn)上收發(fā)電路的能耗為50×10-6J/bit；節(jié)點(diǎn)成功發(fā)送一位數(shù)據(jù)通過1 m距離的能耗為100×10-9J/bit/m2；節(jié)點(diǎn)上計(jì)算能耗為 5×10-6J/bit；每個數(shù)據(jù)包的長度為1 024 bit；每個控制包的長度為64 bit，如表1所示。網(wǎng)絡(luò)的生命周期被定義為一個節(jié)點(diǎn)在耗光自身的能量前，已經(jīng)進(jìn)行的數(shù)據(jù)收集輪數(shù)。

表1 實(shí)驗(yàn)參數(shù)

另外，本文使用數(shù)據(jù)收集延遲來評價數(shù)據(jù)收集的效率。定義網(wǎng)絡(luò)的通信距離為：

其中，ui的取值為0或1，ui=1表示節(jié)點(diǎn)i是簇頭，ui=0表示節(jié)點(diǎn)i是簇成員；di_B表示簇頭與基站之間的距離；cij的取值為0或1，cij=1表示節(jié)點(diǎn)i和節(jié)點(diǎn) j之間存在數(shù)據(jù)鏈路，反之則不存在；dij表示節(jié)點(diǎn)i和節(jié)點(diǎn) j之間的地理距離，h表示路徑衰減因子，在模擬中取值h=2。網(wǎng)絡(luò)中所有節(jié)點(diǎn)通信距離越短，則數(shù)據(jù)收集延遲越低。

5.2 實(shí)驗(yàn)結(jié)果

為了測試本文提出方案的性能，以Matlab2009為工具進(jìn)行了仿真實(shí)驗(yàn)，將本文提出的快速數(shù)據(jù)收集算法QDGA與目前較為典型的MLD[7]方案和EEDGA[14]方案進(jìn)行了對比。分別做了兩組實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果取50次模擬的平均值。

第一組實(shí)驗(yàn)：在傳感器節(jié)點(diǎn)個數(shù)固定為100個，監(jiān)測區(qū)域大小M可變情況下的數(shù)據(jù)收集延遲和網(wǎng)絡(luò)生命周期比較。

圖2給出了不同M值下的數(shù)據(jù)收集的延遲比較結(jié)果。從中可以看到，隨著網(wǎng)絡(luò)監(jiān)測區(qū)域的增加，不同方案的數(shù)據(jù)收集延遲都呈現(xiàn)增加的趨勢，從（125 m，125 m）到（300 m，300 m），EEDGA、MLD和QDGA的延遲分別增加了22.1 s，17.6 s，10.8 s。其中QDGA的延遲最低，相比于EEDGA和MLD，QDGA的總延遲分別降低了24.8%和15.5%。這主要是因?yàn)?，在EEDGA中節(jié)點(diǎn)的數(shù)據(jù)包是逐跳傳輸?shù)模S著M的增大，當(dāng)傳輸鏈路中的某一跳出現(xiàn)丟包現(xiàn)象或節(jié)點(diǎn)意外死亡時，在保證數(shù)據(jù)收集質(zhì)量的前提下，會對整個網(wǎng)絡(luò)的傳輸延遲產(chǎn)生極大影響；而MLD通過建立最小生成樹的方式來為節(jié)點(diǎn)的數(shù)據(jù)包找到合適的傳輸路徑，在一定程度上降低了延遲，取得了比EEDGA更好的性能。而QDGA則將數(shù)據(jù)收集任務(wù)劃分成若干個并行任務(wù)，通過利用多個sink節(jié)點(diǎn)來構(gòu)造具有最小度的網(wǎng)格粒度數(shù)據(jù)收集森林，從而加速了數(shù)據(jù)收集過程。

圖2 不同M下的數(shù)據(jù)收集延遲比較

圖3給出了不同M值下的數(shù)據(jù)收集的網(wǎng)絡(luò)生命周期比較結(jié)果。從中可以看到，隨著網(wǎng)絡(luò)監(jiān)測區(qū)域的增加，不同方案的網(wǎng)絡(luò)生命周期都呈現(xiàn)下降的趨勢，從（125 m，125 m）到（300 m，300 m），EEDGA、MLD 和QDGA的生命周期分別下降了133輪、120輪和98輪。其中QDGA的表現(xiàn)要優(yōu)于EEDGA和MLD。這主要是因?yàn)椋珽EDGA方案沒有考慮到監(jiān)測區(qū)域大小變化對于節(jié)點(diǎn)間數(shù)據(jù)通信質(zhì)量的影響，隨著M的增加，EEDGA需要額外消耗極大的能量來保證數(shù)據(jù)收集的可靠性，從而影響了網(wǎng)絡(luò)的壽命；而MLD方案在網(wǎng)絡(luò)規(guī)模不斷增大的情況下，如果傳感器節(jié)點(diǎn)的分布不統(tǒng)一或者不均勻，則構(gòu)建最大生命周期樹的難度會呈指數(shù)級增加，從而極大消耗了節(jié)點(diǎn)的能量。

圖3 不同M下的數(shù)據(jù)收集網(wǎng)絡(luò)生命周期比較

第二組實(shí)驗(yàn)：在監(jiān)測區(qū)域大小M固定為（150 m，150 m），傳感器節(jié)點(diǎn)個數(shù)從50個增加到350個的數(shù)據(jù)收集延遲和網(wǎng)絡(luò)生命周期比較。

圖4給出了不同節(jié)點(diǎn)個數(shù)下的數(shù)據(jù)收集的延遲比較結(jié)果。從中可以看到，隨著傳感器節(jié)點(diǎn)個數(shù)的增加，不同方案的數(shù)據(jù)收集延遲都呈現(xiàn)增加的趨勢，從（125 m，125 m）到（300 m，300 m），QDGA的數(shù)據(jù)收集延遲始終要低于EEDGA和MLD。仔細(xì)分析其原因可知，這主要是因?yàn)?，EEDGA中的節(jié)點(diǎn)通過僅僅和距離它最近的鄰居建立連接來降低總的通信距離，這種策略僅當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)較少時是有效的；MLD則在建模時考慮了節(jié)點(diǎn)個數(shù)可變情況下的收集延遲，通過可靠路徑選擇來規(guī)避節(jié)點(diǎn)個數(shù)增加所導(dǎo)致的收集延遲增大問題；而QDGA基于多sink節(jié)點(diǎn)對監(jiān)測區(qū)域進(jìn)行網(wǎng)格粒度的劃分，避免了數(shù)據(jù)收集過程隨著傳感器節(jié)點(diǎn)個數(shù)增加而導(dǎo)致的多跳傳輸。另外，QDGA可以相對實(shí)時地保存網(wǎng)格內(nèi)的節(jié)點(diǎn)信息和相應(yīng)地鄰居信息，并通過多信道時隙的最優(yōu)分配來進(jìn)行網(wǎng)格內(nèi)數(shù)據(jù)收集，因此數(shù)據(jù)收集延遲相對較低，取得了比其他兩種方法更好的性能。

圖4 不同節(jié)點(diǎn)個數(shù)下的數(shù)據(jù)收集延遲比較

圖5給出了不同節(jié)點(diǎn)個數(shù)下的數(shù)據(jù)收集的網(wǎng)絡(luò)生命周期比較結(jié)果?？梢钥吹?，QDGA的生命周期要長于EEDGA和MLD。仔細(xì)分析其原因可知，這是由于EEDGA首先通過求最小支配集來確定工作節(jié)點(diǎn)的個數(shù)，這是一個k覆蓋問題，在大規(guī)模傳感器網(wǎng)絡(luò)中的求解復(fù)雜度高，另外采用蟻群算法來規(guī)劃數(shù)據(jù)收集的路線，算法的迭代次數(shù)過多，以上的操作都給節(jié)點(diǎn)造成了較大的能量開銷；而MLD通過迭代地降低瓶頸節(jié)點(diǎn)的負(fù)載來延長網(wǎng)絡(luò)生命周期，該問題是NP難問題，另外該算法的性能受到網(wǎng)絡(luò)初始拓?fù)涞挠绊懸草^大?？偟膩碚f，相比于EEDGA和MLD而言，QDGA在數(shù)據(jù)收集應(yīng)用中更為有效。另外隨著節(jié)點(diǎn)數(shù)目的增加，QDGA的表現(xiàn)更為穩(wěn)定，不會出現(xiàn)生命周期大幅降低的情況。

圖5 不同節(jié)點(diǎn)個數(shù)下的數(shù)據(jù)收集網(wǎng)絡(luò)生命周期比較

6 結(jié)論和未來工作

本文針對時間響應(yīng)和數(shù)據(jù)準(zhǔn)確度要求高的應(yīng)用，提出了一種快速數(shù)據(jù)收集算法。該算法中基站節(jié)點(diǎn)利用自己已知的全局信息和計(jì)算能力計(jì)算出數(shù)據(jù)收集網(wǎng)格粒度最優(yōu)的數(shù)據(jù)收集策略。網(wǎng)格內(nèi)的普通節(jié)點(diǎn)可以根據(jù)自己的鄰居信息進(jìn)行網(wǎng)格內(nèi)的數(shù)據(jù)收集和計(jì)算，通過實(shí)驗(yàn)表明該方法相對非并行處理的數(shù)據(jù)收集策略在保證網(wǎng)絡(luò)生命周期的前提下，能夠減少時間延遲以及提高數(shù)據(jù)收集的準(zhǔn)確率。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性。下一步研究工作的重點(diǎn)在于：（1）基于壓縮感知理論，研究無線傳感網(wǎng)中的數(shù)據(jù)收集可靠性問題；（2）基于壓縮感知理論，研究無線傳感網(wǎng)中的數(shù)據(jù)融合時間選擇問題。

[1]梁俊斌.無線傳感網(wǎng)中低能耗數(shù)據(jù)收集協(xié)議研究[D].長沙：中南大學(xué)，2010.

[2]朱永利，于永華，李麗芬.數(shù)據(jù)收集傳感器網(wǎng)絡(luò)的多模層次網(wǎng)絡(luò)構(gòu)建[J].計(jì)算機(jī)工程，2011，37（2）：111-113.

[3]潘文虎，張瑞華.WSN中基于移動sink的高效數(shù)據(jù)收集算法[J].計(jì)算機(jī)工程，2011，37（18）：94-96.

[4]袁凌云，王興超，徐天偉.基于移動Agent和WSN的突發(fā)事件場景數(shù)據(jù)收集算法研究[J].電子與信息學(xué)報(bào)，2010，32（8）：1974-1979.

[5]閆宇博，楊盤隆，張磊.基于低輪值不可靠無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)收集加速機(jī)制研究[J].計(jì)算機(jī)研究與發(fā)展，2010，47（z2）：121-127.

[6]陳濤，郭得科，羅雪山，等.一種基于移動基站的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集方法[J].國防科技大學(xué)學(xué)報(bào)，2011，33（2）：49-53.

[7]楊靖，徐邁，趙偉，等.傳感器網(wǎng)絡(luò)中一種能量高效的數(shù)據(jù)收集算法[J].系統(tǒng)工程與電子技術(shù)，2011，33（3）：650-653.

[8]Kuhn H W.The Hungarian method for the assignment problem[J].Naval Res Logistics，2005，52（1）：7-21.

[9]李燕君，葉敬川，朱藝華.能量感知的傳感器網(wǎng)絡(luò)分布式時空相關(guān)數(shù)據(jù)收集方案[J].北京郵電大學(xué)學(xué)報(bào)，2011，34（53）：110-114.

[10]張龍妹，史浩山，楊俊剛，等.一種適用于WMSNs的多信道快速數(shù)據(jù)收集算法[J].西北工業(yè)大學(xué)學(xué)報(bào)，2011，29（3）：380-383.

[11]奎曉燕，張士庚，王建新.DSCAU：非均衡負(fù)載無線傳感器網(wǎng)絡(luò)的基于支配集的分簇?cái)?shù)據(jù)收集算法[J].高技術(shù)通訊，2012，22（9）：918-924.

[12]Cheng Jie，Jiang Hongbo，Ma Xiaoqiang，et al.Efficient data collection with sampling in WSNs：making use of matrix completion techniques[C]//Global Telecommunications Conference（GLOBECOM 2010），2010：1-5.

[13]Chou Chun Tung，Rana R，Hu Wen.Energy efficient information collection in wireless sensor networks using adaptive compressive sensing[C]//2009 IEEE 34th Conference on Local Computer Networks（LCN2009），2009：443-450.

[14]Wu Yan，F(xiàn)ahmy S.On the construction of a maximumlifetime data gathering tree in sensor networks：NP-completeness and approximation algorithm[C]//Proc of The IEEE 27th Conference on Computer Communications（INFOCOM2008），2008：356-360.