無線傳感器網絡中一種基于可靠性的數據收集算法

黃 媛

(1.西北大學信息科學與技術學院,西安710127;2.陜西省行政學院計算機應用系,西安710068)

無線傳感器網絡中一種基于可靠性的數據收集算法

黃 媛1,2

(1.西北大學信息科學與技術學院,西安710127;2.陜西省行政學院計算機應用系,西安710068)

為實現無線傳感器網絡數據的低延時、高可靠性收集,將數據收集時涉及到的收集樹構建、鏈路調度與功率分配聯合問題定義為一個使數據收集延時最小化的優化問題。將該問題分成2個子問題:低延時數據收集樹的構建和針對數據收集樹的鏈路調度與功率分配,并為每個子問題提供一種多項式啟發算法。仿真結果表明,與現有數據收集策略相比,該算法的數據收集延時明顯降低,且可靠性更高。

無線傳感器網絡;數據收集;鏈路調度;功率分配;SINR約束;延時;可靠性

1 概述

無線傳感器網絡[1](Wireless Sensor Network, WSN)是近年來受到國內外廣泛關注的研究熱點。無線傳感器網絡在工作過程中,節點會不斷地感知到周邊環境的數據,并通過無線天線將數據以多跳的方式發送給遠方的Sink節點(或稱為基站)進行處理,即數據收集[2]。數據收集是無線傳感器網絡中最重要的操作之一,能否有效地收集到合適的數據,直接關系到應用的效果。由于節點只有有限的能量以及有限的存儲、計算和通信能力,如何使網絡能長時間的工作并且在數據收集的過程中滿足應用的需求,以解決節點能量耗費不平衡、數據收集延遲過大等問題,是目前數據收集中面臨的主要挑戰。

本文在已有研究工作的基礎上,提出了一種兼顧時延和可靠性的數據收集算法。

2 相關工作

數據收集問題在無線傳感器網絡中已經被廣泛研究,相繼有眾多研究者提出了一系列有代表性的方案。文獻[3]研究了基于移動協助數據收集的無線傳感器網絡結構,分類總結了近年來提出的一些典型的基于移動收集者(MDC)的算法和協議,針對傳感器網絡中MDC的研究提出了亟待解決的問題,并展望了其未來的發展方向。文獻[4]為了提高數據收集可靠性和延長網絡生命周期,提出了基于多元簇首的分簇數據收集算法。算法將網絡劃分為大小相等的柵格,由每個柵格中的節點各自構成一個簇,根據節點失效概率從每個柵格中選出多個簇首,并由同一柵格中的多個簇首協作完成柵格中節點的數據收集任務。仿真結果表明,該算法具有較高的數據收集可靠性,并能夠顯著延長網絡生命周期。文獻[5]提出了一種能量均衡的基于連通支配集的分布式算法EBCDS來進行數據收集,通過選擇能量水平和度均比較大的節點組成連通支配集,支配集中的節點組成一個規模不大但具有較高能量水平的網絡骨干。網絡中的所有數據沿骨干在較小的尋路空間中轉發,能夠節省節點能量,使骨干節點不會因為能量不足而過早死亡。理論分析表明,EBCDS能以O(nlogn)的消息復雜度構造連通支配集,仿真實驗表明,EBCDS能有效節省節點能耗并延長網絡生命周期。

文獻[6]提出一種能量高效的數據收集算法(Energy-efficient Data Gathering Algorithm,EEDGA)。該算法利用移動代理模型在網絡中進行數據收集。首先EEDGA根據監測精度的要求控制活動節點的數量;然后通過求最小支配集得到具體的工作節點;最后利用蟻群算法規劃移動代理遷移的最優路線,移動代理以漸進方式收集活動節點的監測數據。文獻[7]提出一種基于多信道的快速數據收集MAC協議,結合多信道和時分多址復用消除節點間的干擾,在節點進行時槽分配時充分考慮節點半雙工通信方式和數據收集公平性,盡可能地在空間上實現信道的復用,提高數據傳輸的并行性。在時序調度過程中,引入網絡時延能耗平衡因子,實現不同應用場合對時延和能耗的平衡調節,增強協議的靈活性。仿真結果表明,該協議在大規模數據收集應用中具有高吞吐量、低時延的特性。

3 問題定義

考慮由一組靜態傳感器節點構成的一個傳感器網絡,表示為N。網絡中的Sink負責對來自其他節點的數據進行收集和處理。每個傳感器節點從P=集合中選擇一個發射功率進行無線通信。為了確保高可用性,鏈路接收端的SINR應該大于最小閾值λ。對任意2個節點i和j,當節點以pmax功率發射信號且無其他鏈路干擾,那么如果節點j的SINR大于λ,則從節點i到j存在一條有向鏈路。注意節點i和j的干擾和噪聲水平是不對稱的,所以鏈路(i,j)是有向的。本文使用集合L來表示網絡中所有的有向鏈路。此外,定義K為即使每個時隙只有一個鏈路處于傳輸活躍狀態,也足以將所有節點的報文傳輸給Sink的大量時隙。使用一個二元變量來表示鏈路(i,j)是否被安排在時間t內傳輸數據。如果,則表示在時隙t內,鏈路(i,j)是可以傳輸數據的活躍鏈路。有:

在上述定義中,式(2)和式(3)分別明確了所有節點的發射功率和流量需求范圍。式(6)～式(8)和式(11)分別是數據收集、鏈路調度和SINR閾值約束[8];式(9)和式(10)分別用于確定每條鏈路的接收功率和SINR。表1給出了相關標記法。當獲得最優解后,沒有活躍鏈路的時隙就被刪除,剩余時間隙形成時間幀。

表1 優化問題相關符號的含義

4 啟發式算法

在上文定義的優化問題中,當傳感器節點數量變多時,約束條件數量將呈指數上升,使得難以通過數學工具求得最優解。為了降低問題難度,將問題分為2個子問題:(1)構建一個低延時數據收集樹; (2)調度鏈路,并在每個時隙為活躍鏈路分配發射功率,于是當所有活躍鏈路的SINR大于λ時實現數據收集時間最小化。首先引入基于功率的增強型沖突圖,以降低這2個子問題的處理難度,然后為每個子問題提供一個啟發式算法。

4.1 基于功率的增強型沖突圖

文獻[9]討論了基于功率的沖突圖,在該圖中,已知任意功率分配方案后,如果2個頂點的對應鏈路在無線傳感器網絡中無法同時調度,則這2個頂點相連。該圖可以幫助調度數據收集樹的鏈路。然而,該圖沒有反映本文啟發式算法需要的鏈路流量負載。因此,針對數據收集問題對該圖進行拓展,形成基于功率的增強型沖突圖,將該圖定義為一個加權無向圖I=(V,E,W),其中,V是頂點結合;E是表示沖突關系的邊集合,W是所有頂點的權重集合。V中每個頂點關聯數據收集樹上的一個鏈路。頂點權重定義為關聯鏈路的剩余流量負載。對2個頂點,如果它們的關聯鏈路的流量負載為正,且無可行性功率分配方案使它們滿足最小SINR閾值,或者它們共享一個節點,則這2個頂點相連。對2條鏈路,如果它們在I上的關聯頂點相連,則這2條鏈路不相容。

4.2 數據收集樹的構建

在LLHC算法中,通過寬度優先(BFS)搜索算法遍歷整個網絡,為每個節點分配一個高度。遍歷時以Sink為起點,以使節點的高度等于節點到Sink的最短跳數。本文其余部分,詞匯“高度”和“層”可以互用。此外,為網絡構建一個基于功率的增強型沖突圖I。數據收集樹T在開始時為空。首先,高度為1的所有節點及其與Sink的有向鏈路被添加到T中。然后,每個下層節點被選為子樹的根。于是,由于BFS的遍歷特性,可知子樹的數量實現了最大化。按照節點高度的升序,將所有其他節點加到樹T中。高度為m的節點可以選擇m-1層任意節點作為母節點,前提是它們之間存在一條有向鏈路。如上文所述,可以實現最大子樹規模最小化且引入的新鏈路與T上大多數鏈路均兼容的節點應該被選為母節點。為母節點定義一個權重以反映這兩方面因素。對節點i的母節點候選節點j,其權重定義為節點j隸屬的子樹規模和T中與鏈路(i,j)不兼容的鏈路數量之和。權重最小的候選節點j′將被選為節點i的母節點,且鏈路(i,j′)被加到T中。重復這一步驟,直到所有節點屬于T。

每當有新節點加入到數據收集樹時,由于節點數量有限,因此算法肯定會終止。LLHC算法的偽代碼如下:

算法1LLHC算法

輸入傳感器節點集合N;有向鏈路集合L

輸出數據收集樹T

對N中所有節點,將發射功率初始化為pmax;

對N中所有節點,將母節點初始化為-1;

生成增強型功率(power)干擾矩陣I;

使用BFD算法遍歷整個網絡,獲得所有節點的層次level(i);

從算法中可以看出,它生成基于功率的增強型沖突圖和基于BFS算法遍歷所有節點的耗時分別為和。假設節點有M層,每層m的節點數量為nm,于是有n1+n2+…+nm=。在最壞情況下,m-1層的任意節點均可以是m層每個節點的母節點。于是,如果假設確定母節點候選節點的權重的耗時恒定,則將m層節點連接到樹T需要耗時O(nm-1·nm)。于是連接所有節點的時間為O(n1·n2+n2·n3+…+nM-1·nM)=。因此,LLHC算法的總體時間復雜度為:。

4.3 鏈路調度和功率分配

在用LLHC算法確定一個數據收集樹后,下一步就是為樹上的鏈路分配時隙和發射功率,以實現數據收集延時最小化。本文提出一種最大權重優先(MWF)算法進行鏈路的調度和發射功率的分配,在該算法中,鏈路的權重定義為該鏈路剩余流量負載和該鏈路在I上的關聯頂點的度兩者之和。

已知一組鏈路后,如何確定它們的發射機是否存在一種功率分配向量,以滿足所有鏈路的SINR約束,是一大難題。由于沖突干擾的累加性,即使這些鏈路在沖突圖上的關聯頂點互相獨立,也并不一定存在合適的功率分配方案。當鏈路數量較大時,野蠻搜索方法不具有可行性。對不存在共有節點的一組鏈路M,定義可行性矩陣如下:

其中,鏈路ms的發射機和接收機分別表示為mt和mr。可行性矩陣F的第(i,j)個元素定義為:

其中,g(jt,ir)表示鏈路j發射機到鏈路i接收機的信道增益;g(it,ir)是鏈路i的信道增益。

在MWF算法中,首先針對數據收集樹T,構建基于功率的增強型沖突圖I。然后,對T上的所有鏈路按照鏈路降序排列。分配一個新的時隙t,權重最大的鏈路m放入時隙t的活躍鏈路集合St。鏈路m的流量負載降1。檢查具有第2高權重的鏈路m′和St中其他鏈路的兼容性。如果鏈路m′與所有鏈路兼容,則對鏈路St∪m′構建可行性矩陣F。如果可以為F找到一個可行的功率分配方案,則將鏈路m′加入到St中,同時m′的流量負載降1。否則,檢查排序列表上的下一條鏈路。當具有剩余流量負載的所有鏈路一次檢查完畢后,時隙t的活躍鏈路集合t也最終確定。此后,相應更新沖突圖I。分配新的時隙t+1,重復這一步驟,直到T的所有鏈路的流量負載為0。

由于每個時隙中,至少一個鏈路被調度,而且總體流量負載有限,因此算法必然會終止。MWF算法的偽代碼如下:

算法2MWF算法

輸入數據收集樹T;發射功率集合P;流量需求D

輸出鏈路調度矩陣S,功率分配矩陣U

生成收集樹T的基于功率的增強型沖突圖I;

確定T上每條鏈路的流量負載;

為了分析MWF算法的時間復雜度,假設每個時隙內平均有u條鏈路被調度。在最壞情況下,排序鏈路列表中的前u條鏈路始終被選入活躍鏈路集合。然后對剩余的條鏈路中的每條鏈路,需要耗費O(u)時間來檢查鏈路是否與前u條鏈路兼容。如果兼容,還需再耗費O((u+1)3)的時間來檢查矩陣F的可行性,且計算n×n矩陣的特征值和特征向量需要時間O(n3)。否則,該鏈路不能加入活躍鏈路集合,進而檢查下一條剩余鏈路的兼容性。在最壞情況下,所有傳感器分散在一條直線上且Sink位于直線一端,于是數據收集樹也有一個直線拓撲結構。這種情況的流量負載之和為1)/2。因此,需要的時隙數量為。 MWF算法的總時間復雜度近似為:

5 性能評估

本節通過仿真實驗來評估LLHC和MWF算法的性能。首先研究不同節點密度和SINR閾值的情況下本文算法的有效性。然后考察數據收集負載在平均中繼流量和節點最大緩存長度2個方面的分布情況。其次研究Sink位置對數據收集延時的影響。為便于比較,同時部署了寬度優先搜索算法(BFS)和最大壽命樹算法(MLT),以生成數據收集樹;綜合調度和功率控制算法(ISPA)和增大需求貪婪調度(IDGS)算法[11]也被部署,以對數據收集樹上的鏈路進行調度。在仿真中,節點隨機分布于500 m× 500 m方形區域中。所有節點的最大發射功率為-10 dBm。此外,所有節點在5 MHz頻段上通信,加性高斯白噪聲的均值(AWGN)為-97 dBm。使用長距離路徑損耗模型作為傳播模型,其中,路徑損耗指數為3,Xδ的標準差為7 dB。除非另外指定,否則,SINR的最小閾值為10 dB且Sink部署于區域中央。所有結果運行100次取均值。

首先評估LLHC和MWF算法在數據收集所需的時隙數量方面的性能。傳感器節點的數量范圍為50～200,以25為步進量。仿真結果見圖1(a),在圖中,LLHC和MWF聯合運行,而BFS和MLT生成的收集樹分別由ISPA和IDGS鏈路調度算法進行調度。很顯然,相比其他各種算法的任意組合,本文算法的數據收集時間更低。此外,當節點密度較高時,本文算法的優勢更為明顯。例如,當部署200個節點時,本文算法結果分別比MLTIDGS和MLTISPA高出13%和28%。這表明本文收集樹構建和鏈路調度策略在降低數據收集延時方面的性能更低,同時可以保證較高的可靠性。請注意,數據收集樹相同時,IDGS考慮了鏈路的流量負載,因此IDGS在數據收集時需要的時隙數量低于ISPA。另一方面,由于不同的鏈路調度算法得出不同的鏈路調度結果,因此難以看出BFS或MLT在降低數據收集延時方面的性能是否更優。

現在研究SINR閾值約束不同時,本文算法需要多少時隙。節點數量固定為100,而最小SINR閾值范圍為0～30 dB,步進量為5 dB。圖1(b)給出了LLHC-MWF和其他各種算法組合的仿真結果。

圖1 數據收集所需時隙數量

很顯然,當最小SINR閾值上升時,所有算法的數據收集時間均會上升,原因是當鏈路對干擾的敏感性增加時,每個時隙內的鏈路調度數量下降。然而,在不同的最小SINR閾值條件下,本文算法的性能始終優于其他算法。此外,當最小SINR閾值相對嚴格時,本文算法的優勢更為明顯。尤其地,當SINR的閾值為20 dB時,本文算法所需時隙量分別比MLT-IDGS和BFSISPA算法少31個和46個時隙。另外觀察到,當SINR閾值超過20 dB時, LLHC-MWF相對其他算法的性能優勢有輕微下降。原因是當SINR閾值較大時,收集樹上大量鏈路不兼容,因此即使它們相對其他沒有入選收集樹的鏈路受到的干擾較少,但是仍然無法在同一時隙內調度。

下面研究在不同算法生成的數據收集樹上,節點需要轉發的流量。仿真結果見圖2(a),節點數量范圍為50～200。可以發現,LLHC的平均轉發流量低于BFS算法,但高于MLT算法。原因是LLHC與BFC算法不同,LLHC算法在構建收集樹時考慮了子樹的規模,因此流量負載在網絡上分布的更均衡。當節點密度增大時,MLT算法的平均轉發流量基本不變,原因是在樹的每一層,該算法均努力實現鏈路最大流量負載最小化。然而,如圖1所示,該算法完成一輪數據收集所需時間要長于LLHC算法。這表明在轉發負載和數據收集延時之間需要進行折衷。

本文還研究了數據收集期間,每個節點的最大隊列長度,以確定節點的最小緩存量。仿真結果見圖2(b)。

圖2 節點的平均轉發流量和最大隊列長度對比

很顯然,LLHC和MWF算法的最大隊列長度遠小于基于BFS的數據收集策略。此外,當節點密度上升時,本文算法的最大隊列長度緩慢上升。如果區域內有200個節點,則LLHC-MWF的最大隊列長度為13,只是BFS策略的1/3。假設報文大小為1KB,則本文算法所需緩存量小于20 KB,基本在大多數在用傳感器節點的承受范圍內。基于MLT的數據收集策略的最大隊列長度低于5,且與節點密度無關,具體原因與上文討論的每個節點的平均轉發流量類似。同時也可以發現,如果數據收集樹相同,則IDGS需要的緩存量低于ISPA。這是因為IDGS在每個時隙內的平均鏈路調度量高于ISPA(圖1)。

另外,本文還研究了Sink位置對數據收集延時的影響。共進行了2組實驗:一組中的Sink隨機部署;另一組位于區域中央。仿真結果見圖3,圖中CS和RS分別表示中央部署Sink和隨機部署Sink。很顯然,如果Sink隨機部署,則各種數據收集策略需要的時間均會上升。原因是如果Sink在網絡邊緣區域,則只有少部分節點可以將數據直接傳輸給Sink,使之成為數據收集的瓶頸。然而,與其他算法相比,本文算法仍然明顯降低了數據收集延時。

圖3 Sink部署于區域中央和隨機部署時的時隙數量

最后,考慮到在本文方案中,每個節點可以以較低頻率廣播固定功率的信標消息,其他節點通過測量信標消息的接收功率就可以確定以該節點為起點的鏈路的信道增益。然后,該信道增益信息將被發往Sink。最后,只需在Sink上周期性運行LLHC和MWF算法,并將獲得的采集樹、鏈路調度和功率分配輸出給所有節點即可實現可靠的數據收集,避免了由于鏈路失效所導致的節點多次數據轉發和冗余傳輸問題,從而節省了節點能量。總的來說,本文算法通過鏈路調度和功率分配的聯合優化,在保證數據收集可靠性的前提下,可以實現整個網絡的能量有效性,進而延長網絡壽命。

6 結束語

本文研究了無線傳感器網絡中基于收集樹的數據收集問題,通過構建合適的數據收集樹、調度收集樹上的鏈路、在每個時隙內為活躍鏈路分配功率,以較低的時延和較高的可靠性,實現傳感器的數據收集任務。將該問題分為2個子問題,并為每個子問題提供一個啟發式算法。仿真實驗結果表明,該算法在不同的節點密度和最小SINR閾值條件下,不論Sink位于何處,均可以明顯降低數據收集延時。同時,通過使用本文算法,流量負載在網絡上的分布更為均勻,網絡壽命也更長。本文下一步工作的重點是研究機會移動傳感器網絡中基于壓縮感知的可靠數據收集方案。

[1] Daflapurkar M P M,Patil B P.Performance Evaluation of WSNParametersUsingReinforcementLearning:A Survey[J].Performance Evaluation,2013,1(9):1360-1365.

[2] Liu Xiang,Jun Luo,Rosenberg C.Compressed Data Aggregation:Energy-efficientandHigh-fidelityData Collection[J].IEEE/ACM Transactions on Networking, 2013,21(6):1722-1735.

[3] 張希偉,戴海鵬,徐力杰,等.無線傳感器網絡中移動協助的數據收集策略[J].軟件學報,2013,24(2): 198-214.

[4] 胡升澤,包衛東,王 博,等.無線傳感器網絡基于多元簇首的分簇數據收集算法[J].電子與信息學報, 2014,36(2):403-408.

[5] 奎曉燕,杜華坤,梁俊斌.無線傳感器網絡中一種能量均衡的基于連通支配集的數據收集算法[J].電子學報,2013,41(8):1521-1528

[6] 楊 靖,徐 邁,趙 偉,等.傳感器網絡中一種能量高效的數據收集算法[J].系統工程與電子技術, 2011,33(3):650-653

[7] 譚金勇,楊中亮.基于多信道的快速數據收集MAC協議[J].計算機工程,2013,39(12):107-110.

[8] Andrews M,Dinitz M.Maximizing Capacity in Arbitrary Wireless Networks in the SINR Model:Complexity and Game Theory[C]//Proceedings of IEEE INFOCOM’09. [S.1.]:IEEE Press,2009:1332-1340.

[9] Behzad A,Rubin I.Optimum Integrated Link Scheduling and Power Control for Multihop Wireless Networks[J]. IEEE Transactions on Vehicular Technology,2011,56(1): 194-205.

[10] Incel O D,Ghosh A,Krishnamachari B,et al.Fast Data Collection in Tree-based Wireless Sensor Networks[J]. IEEE Transactions on Mobile Computing,2012,11(1): 86-99.

[11] Fu L,Liew S C,Huang J.Joint Power Control and Link SchedulinginWirelessNetworksforThroughput Optimization[C]//Proceedings of ICC’08.[S.1.]: IEEE Press,2008:3066-3072.

編輯 索書志

A Data Collection Algorithm Based on Reliability in Wireless Sensor Network

HUANG Yuan1,2
(1.School of Information Science and Technology,Northwest University,Xi’an 710127,China; (2.Department of Computer Application,Shaanxi Academy of Governance,Xi’an 710068,China)

To achieve low-latency,high-reliability data gathering in Wireless Sensor Network(WSN),this paper formulates the joint problem of tree construction,link scheduling and power assignment for data gathering into an optimization problem,with the objective of minimizing data gathering latency.It divides the problem into two sub problems:construction of a low-latency data gathering tree,jointly link scheduling and power assignment for the data gathering tree.This paper proposes a polynomial heuristic algorithm for each sub problem and conducts extensive simulations.Simulation results show that the proposed algorithm achieves much lower data gathering latency than existing data gathering strategies while guaranteeing high reliability.

Wireless Sensor Network(WSN);data collection;link scheduling;power assignment;SINR constraint; delay;reliability

黃 媛.無線傳感器網絡中一種基于可靠性的數據收集算法[J].計算機工程,2015,41(2):85-90,95.

英文引用格式:Huang Yuan.A Data Collection Algorithm Based on Reliability in Wireless Sensor Network[J]. Computer Engineering,2015,41(2):85-90,95.

1000-3428(2015)02-0085-06

:A

:TP393

10.3969/j.issn.1000-3428.2015.02.017

黃 媛(1979-),女,講師、碩士,主研方向:無線傳感器網絡,信息處理。

2014-03-13

:2014-04-09E-mail:484895081@qq.com