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

黃 媛

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

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

黃 媛1,2

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

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

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

1 概述

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

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

2 相關(guān)工作

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

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

3 問題定義

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

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

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

4 啟發(fā)式算法

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

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

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

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

在LLHC算法中,通過寬度優(yōu)先(BFS)搜索算法遍歷整個網(wǎng)絡(luò),為每個節(jié)點分配一個高度。遍歷時以Sink為起點,以使節(jié)點的高度等于節(jié)點到Sink的最短跳數(shù)。本文其余部分,詞匯“高度”和“層”可以互用。此外,為網(wǎng)絡(luò)構(gòu)建一個基于功率的增強型沖突圖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é)點應(yīng)該被選為母節(jié)點。為母節(jié)點定義一個權(quán)重以反映這兩方面因素。對節(jié)點i的母節(jié)點候選節(jié)點j,其權(quán)重定義為節(jié)點j隸屬的子樹規(guī)模和T中與鏈路(i,j)不兼容的鏈路數(shù)量之和。權(quán)重最小的候選節(jié)點j′將被選為節(jié)點i的母節(jié)點,且鏈路(i,j′)被加到T中。重復(fù)這一步驟,直到所有節(jié)點屬于T。

每當(dāng)有新節(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)絡(luò),獲得所有節(jié)點的層次level(i);

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

4.3 鏈路調(diào)度和功率分配

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

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

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

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

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

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

算法2MWF算法

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

輸出鏈路調(diào)度矩陣S,功率分配矩陣U

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

確定T上每條鏈路的流量負(fù)載;

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

5 性能評估

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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

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

[6] 楊 靖,徐 邁,趙 偉,等.傳感器網(wǎng)絡(luò)中一種能量高效的數(shù)據(jù)收集算法[J].系統(tǒng)工程與電子技術(shù), 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)絡(luò)中一種基于可靠性的數(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)絡(luò),信息處理。

2014-03-13

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