無線傳感器網(wǎng)絡中一種基于可靠性的數(shù)據(jù)收集算法

黃 媛

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

無線傳感器網(wǎng)絡中一種基于可靠性的數(shù)據(jù)收集算法

黃 媛1,2

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

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

無線傳感器網(wǎng)絡;數(shù)據(jù)收集;鏈路調度;功率分配;SINR約束;延時;可靠性

1 概述

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

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

2 相關工作

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

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

3 問題定義

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

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

表1 優(yōu)化問題相關符號的含義

4 啟發(fā)式算法

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

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

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

4.2 數(shù)據(jù)收集樹的構建

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

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

算法1LLHC算法

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

輸出數(shù)據(jù)收集樹T

對N中所有節(jié)點,將發(fā)射功率初始化為pmax;

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

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

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

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

4.3 鏈路調度和功率分配

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

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

其中,鏈路ms的發(fā)射機和接收機分別表示為mt和mr?？尚行跃仃嘑的第(i,j)個元素定義為:

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

在MWF算法中,首先針對數(shù)據(jù)收集樹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算法

輸入數(shù)據(jù)收集樹T;發(fā)射功率集合P;流量需求D

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

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

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

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

5 性能評估

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

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

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

圖1 數(shù)據(jù)收集所需時隙數(shù)量

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

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

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

圖2 節(jié)點的平均轉發(fā)流量和最大隊列長度對比

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

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

圖3 Sink部署于區(qū)域中央和隨機部署時的時隙數(shù)量

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

6 結束語

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

[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] 張希偉,戴海鵬,徐力杰,等.無線傳感器網(wǎng)絡中移動協(xié)助的數(shù)據(jù)收集策略[J].軟件學報,2013,24(2): 198-214.

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

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

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

[7] 譚金勇,楊中亮.基于多信道的快速數(shù)據(jù)收集MAC協(xié)議[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

黃 媛.無線傳感器網(wǎng)絡中一種基于可靠性的數(shù)據(jù)收集算法[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-),女,講師、碩士,主研方向:無線傳感器網(wǎng)絡,信息處理。

2014-03-13

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