WSN中一種基于多sink的快速數據收集算法

鄭凱津

ZHENG Kaijin

天津市信息中心，天津 300201

1 引言

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

2 相關工作

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

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

3 系統模型

本文研究的無線傳感器網絡數據收集問題限定于以下假設：

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

圖1 WSN網絡結構示意圖

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

（3）無線傳感器網絡中任意節點i的能耗可以表示為：Ei=Ei-MCU+Ei-TCR+Ei-SB。其中Ei-MCU表示節點i上微控制單元的能耗；Ei-SB表示節點i上中央處理器的計算能耗；Ei-TCR則表示節點i收發數據的通信能耗。Ei-TCR可以進一步表示為：Ei-TCR=Ei-TCR-RX+Ei-TCR-TX(di)。其中Ei-TCR-RX表示節點i接收數據的能耗；Ei-TCR-TX(di)表示節點i發送數據的能耗，它是一個關于距離di的函數，節點i發送的數據與接收節點的距離越大，能耗也越大。基于以上分析，對于一個擁有N個節點的傳感器網絡的總能耗可以表示為：

其中C1為常數，假設網絡中節點傳輸的路徑衰減因子為2，則有：

其中Ei-TCR-EC和Ei-TCR-PA分別表示節點i發送數據時的電子電路和功率放大所導致的能量消耗，它們是一個常數。因此，公式（2）可以表示為：

其中，C2和C3為常數。

4 快速數據收集算法

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

QDGA算法分成兩個階段：

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

（2）任務分發與數據收集階段。此過程中各個網格接收到相應數據收集子任務，并可根據自身的局部信息進行網格內的數據收集，動態調整數據收集路徑。該階段主要是利用局部信息有效避免節點失效引發的空洞等問題。

4.1 基站集中式計算階段

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

算法1網格粒度數據收集森林構造算法

輸入 數據收集任務Q和網絡的連接矩陣A。

輸出 收集森林 F={T1，T2，…}，每個Ti代表一棵以sink節點為根節點的網格粒度收集樹

（1）根據查詢條件構造出包含數據收集區域的網格集合SetI，收集范圍為整個網絡SetI=V

（2）構造數據收集森林

（3）全局分析

4.2 任務分發和數據收集階段

各個sink節點接收到以自己為根節點數據收集樹后進行收集任務的分發。該樹既可以作為數據收集任務下發的基礎也可以作為數據收集返回的基礎。

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

算法2收集任務分發算法

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

算法3網格間數據收集算法

當收集任務分發下去之后，將進行自己網格內部的數據收集。進行網格內數據收集時，每個網格中的節點數目相對較少，網格內的節點可以相對實時地保存網格內的節點信息和相應的鄰居信息，并可以根據局部的網絡結構優化選擇相應的時隙分配。發起網格內數據收集的節點，可以在以自己為根節點的BFS樹的基礎上，通過多信道時隙分配來進行網格內數據收集。網格內的節點數據收集時隙分配偽代碼描述見算法4。

算法4網格內數據收集算法

算法結束后，標記的最大值則為網格內數據收集最多時隙。各個節點按照時隙分配進行數據發送。網格內的數據收集時隙數目不會超過網格內的節點數目。時間消耗最多為O(N(i))。

在數據收集任務下發和數據收集的過程中，每個網格內的所有節點均能收到下行網格和上行網格的代表節點發送過來的任務消息和數據消息。只要網格內還存在未失效的節點，則不會影響該網格的數據收集的分發和收集執行。可以看出利用節點的冗余保證了數據收集處理不易受節點失效的影響。同時在這個過程中，如果按照原有方式出現了突發的空洞或者鏈路失效的問題，任務下發和數據返回可以自適應調整發送路徑。數據收集的路徑可以在收集過程中自適應生成，能有效地消除通信鏈路失效和節點移動的影響。并且在數據回收過程中保存了數據回收路徑，當最終返回到sink節點時這些信息可以為sink節點對基于網格的全局網絡結構維護提供依據，限于篇幅，該部分的內容在本文中不再闡述。

5 仿真實驗與分析

5.1 實驗設計

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

表1 實驗參數

另外，本文使用數據收集延遲來評價數據收集的效率。定義網絡的通信距離為：

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

5.2 實驗結果

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

第一組實驗：在傳感器節點個數固定為100個，監測區域大小M可變情況下的數據收集延遲和網絡生命周期比較。

圖2給出了不同M值下的數據收集的延遲比較結果。從中可以看到，隨著網絡監測區域的增加，不同方案的數據收集延遲都呈現增加的趨勢，從（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%。這主要是因為，在EEDGA中節點的數據包是逐跳傳輸的，隨著M的增大，當傳輸鏈路中的某一跳出現丟包現象或節點意外死亡時，在保證數據收集質量的前提下，會對整個網絡的傳輸延遲產生極大影響；而MLD通過建立最小生成樹的方式來為節點的數據包找到合適的傳輸路徑，在一定程度上降低了延遲，取得了比EEDGA更好的性能。而QDGA則將數據收集任務劃分成若干個并行任務，通過利用多個sink節點來構造具有最小度的網格粒度數據收集森林，從而加速了數據收集過程。

圖2 不同M下的數據收集延遲比較

圖3給出了不同M值下的數據收集的網絡生命周期比較結果。從中可以看到，隨著網絡監測區域的增加，不同方案的網絡生命周期都呈現下降的趨勢，從（125 m，125 m）到（300 m，300 m），EEDGA、MLD 和QDGA的生命周期分別下降了133輪、120輪和98輪。其中QDGA的表現要優于EEDGA和MLD。這主要是因為，EEDGA方案沒有考慮到監測區域大小變化對于節點間數據通信質量的影響，隨著M的增加，EEDGA需要額外消耗極大的能量來保證數據收集的可靠性，從而影響了網絡的壽命；而MLD方案在網絡規模不斷增大的情況下，如果傳感器節點的分布不統一或者不均勻，則構建最大生命周期樹的難度會呈指數級增加，從而極大消耗了節點的能量。

圖3 不同M下的數據收集網絡生命周期比較

第二組實驗：在監測區域大小M固定為（150 m，150 m），傳感器節點個數從50個增加到350個的數據收集延遲和網絡生命周期比較。

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

圖4 不同節點個數下的數據收集延遲比較

圖5給出了不同節點個數下的數據收集的網絡生命周期比較結果。可以看到，QDGA的生命周期要長于EEDGA和MLD。仔細分析其原因可知，這是由于EEDGA首先通過求最小支配集來確定工作節點的個數，這是一個k覆蓋問題，在大規模傳感器網絡中的求解復雜度高，另外采用蟻群算法來規劃數據收集的路線，算法的迭代次數過多，以上的操作都給節點造成了較大的能量開銷；而MLD通過迭代地降低瓶頸節點的負載來延長網絡生命周期，該問題是NP難問題，另外該算法的性能受到網絡初始拓撲的影響也較大。總的來說，相比于EEDGA和MLD而言，QDGA在數據收集應用中更為有效。另外隨著節點數目的增加，QDGA的表現更為穩定，不會出現生命周期大幅降低的情況。

圖5 不同節點個數下的數據收集網絡生命周期比較

6 結論和未來工作

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

[1]梁俊斌.無線傳感網中低能耗數據收集協議研究[D].長沙：中南大學，2010.

[2]朱永利，于永華，李麗芬.數據收集傳感器網絡的多模層次網絡構建[J].計算機工程，2011，37（2）：111-113.

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

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

[5]閆宇博，楊盤隆，張磊.基于低輪值不可靠無線傳感器網絡的數據收集加速機制研究[J].計算機研究與發展，2010，47（z2）：121-127.

[6]陳濤，郭得科，羅雪山，等.一種基于移動基站的無線傳感器網絡數據收集方法[J].國防科技大學學報，2011，33（2）：49-53.

[7]楊靖，徐邁，趙偉，等.傳感器網絡中一種能量高效的數據收集算法[J].系統工程與電子技術，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]李燕君，葉敬川，朱藝華.能量感知的傳感器網絡分布式時空相關數據收集方案[J].北京郵電大學學報，2011，34（53）：110-114.

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

[11]奎曉燕，張士庚，王建新.DSCAU：非均衡負載無線傳感器網絡的基于支配集的分簇數據收集算法[J].高技術通訊，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，Fahmy 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.