基于延遲感知的WSN數據收集網絡結構優化設計

李妙祺　高曉陽　周蓓蓓

(甘肅農業大學工學院　甘肅 蘭州 730070)

?

基于延遲感知的WSN數據收集網絡結構優化設計

李妙祺高曉陽周蓓蓓

(甘肅農業大學工學院甘肅 蘭州 730070)

為了解決當前無線傳感器網絡(WSN)數據收集期間存在較大延遲與能耗等難題，設計基于延遲感知的無線傳感器數據收集網絡結構。引入樹形結構思想，并將WSN的傳感器節點分割為不同尺寸的多個單層簇，繼而構造了新的網絡結構，以改善其拓撲結構，使得簇頭以交錯方式完成數據通信，大幅度降低數據收集過程的延遲；隨后，建立WSN數據收集的延遲與能耗計算模型；再借助Top-Down技術，設計網絡結構的形成算法，通過最小化通信距離，優化了數據收集機制的能耗水平。實驗結果表明：與現有的WSN數據收集網絡結構相比，該網絡結構能夠有效降低WSN數據收集過程的延遲；且使得整個通信能耗維持在較低水平。

無線傳感器網絡數據收集網絡拓撲通信距離延遲感知能耗

0　引　言

在當前WSN應用中，其傳感器都是依賴電池供電，使得WSN節點的能量消耗問題成為一個難題[1,2]。對此，Yang等人[3]為了降低WSN節點的能耗與實現實時性，設計了基于空間聚類的WSN數據收集協議。實驗結果顯示該算法能夠顯著提高網絡生命周期，大幅度降低節點能耗。Bagci等人[4]設計了模糊能量感知不等聚類算法生成不同尺寸的簇，測試數據顯示算法穩定性最好，且能耗最低。但是簇數量是難以控制的，且在輸出數據時，當網內數據融合不產生任何數據減少時，此協議會引入額外的消耗與數據收集延遲。Gupta等人[5]提出了基于鏈的數據收集協議，仿真結果表明該協議可大幅度降低WSN通信能耗水平。但是該協議的頭節點是嚴重的瓶頸，其延遲較大[6]。任秀麗等人[7]提出一種移動基站的樹形無線傳感網絡數據收集方法，實驗數據表明其算法能夠顯著改善網絡通信性能。但是該方法在數據收集過程中的延遲較大。

為了解決WSN數據收集過程存在較大的延遲，本文提出Top-Down技術耦合延遲感知的無線傳感器數據收集網絡結構。利用樹形思想，并將WSN的傳感器節點分割為不同尺寸的多個單層簇，從而有效降低延遲；利用Top-Down技術，設計了本文網絡結構的形成算法，通過最小化通信距離，優化了數據收集機制的能耗水平。最后，通過實驗驗證了本文數據收集方法的延遲與能耗水平。

1　本文網絡結構設計

為了防止數據收集時間急劇增加，本文引入樹形思想[8]，設計了新的網絡結構。由于傳統的樹形結構可靠性不佳，為了增強本文網絡結構的穩定性，直接采用當前穩定性較好的改進胖樹形思想(見文獻[9])：對傳統胖樹形結構中的域完成定義和劃分, 通過為每個域內的第3層節點增加一些域內互聯節點進行互聯，最終生成域內互聯結構；并將該域內互聯結構改進胖樹結構，增強樹節點之間的連通性與容錯能力。同時為了保證本文網絡結構可提供最大的數據收集效率，令本文WSN網絡結構的節點總數為N=2p,p=1,2,…。在該網絡結構中，將WSN的傳感器節點分割為不同尺寸的多個單層簇，使得簇頭以交錯方式與數據融合中心通信。在這種結構下，若WSN網絡擁有N個節點，則將其分割成K個簇群：

(1)

mi=2mi-1mi=1

(2)

其中，mi為第i個簇中節點的最大數量；K為簇群數目。

再將式(2)簡化為：

mi=2i-1

(3)

聯合式(1)與式(3)，可得：

2K-1-1

(4)

在本文網絡結構中，每個簇群成員將獲得一個排名Rank∈[1,p]，則排名為T的節點會生成T-1條數據鏈，且每條數據鏈擁有T-1個節點。這些T-1個節點擁有不同的排名1,2,…,T-1，且會變成排名為T的節點的孩子節點。而排名為T的節點會生成一條數據鏈，使得該鏈中的節點的排名等級更高，而排名更高的節點會變成父節點。以簇頭為例，簇頭是整個WSN網絡中排名最高的節點。在所設計的網絡結構中，簇頭不是形成節點排名更高的數據鏈，而是形成與基站相通的數據鏈。根據這種邏輯，節點排名的分布見表1所示。

表1　本文網絡結構的簇成員的分布

在數據收集過程中，本文網絡結構中的第K簇用來連接數據融合中心。簇更小，則數據收集過程越短。因此，在第K個簇填滿之前，前K-1個簇已經完全被簇群成員填滿。以N=16為例，本文設計的網絡結構模型見圖1所示。依據圖1，整個時域劃分為持續時隙，則該模型需要5個時隙。

圖1　節點N=16的本文網絡結構

圖1中，BS為基站；CM為簇成員；CH為簇頭；T為節點排名；D為持續時隙；箭頭代表數據鏈。

引理1考慮含有N=2p,p=1,2,…個節點的網絡，其傳感器采集的數據包是高度相關的，因此節點可以通過數據/決策融合技術將所有接收到的數據包合成為單一的數據包。雖然采用了本文的網絡結構，但是排名為T≥2的節點i需要T-1個時隙來收集所有孩子節點的輸出數據。

證明由于該網絡結構含有N=2p,p=1,2,…個節點的網絡，對于排名T=2的節點，其需要用來收集來自所有孩子節點數據的時隙等于孩子節點數量，該值為1。故，當T=2時，該引理正確。對于排名T=n+1的節點i，其擁有n個直接相連的孩子節點，則其每個節點都擁有從1到n的不同排名。故它們需要0到n-1個時隙來收集所有孩子節點的數據，并外加一個時隙用來將收集數據廣播至節點i。所以，對于節點i，用來收集其孩子節點的輸出數據所需的最大時隙為T-1=n。證畢。

定理1考慮含有N=2p,p=1,2,…個節點的網絡，其傳感器采集的數據包是高度相關的，因此節點可以通過數據/決策融合技術將所有接收到的數據包合成為單一的數據包。則對于本文設計的網絡結構，基站從整個網絡收集數據所需的時隙t(N)為：

t(N)=log2N+1

(5)

證明對于含有N=2p,p=1,2,…個節點的網絡，根據本文網絡結構可知，簇頭是排名最高的節點：

Tmax=log2N+1

(6)

再根據引理1可知，對于排名為Tmax的簇頭，其用來收集所有孩子節點數據所需的時隙為：

t(N)=Tmax-1=log2N

(7)

因此，基站用于收集網絡數據所需的時隙數量等于簇頭收集其所有孩子節點數據的時隙：

t(N)=log2N+1

(8)

根據式(8)與圖1可知，本文的網絡結構是一個優化樹形結構：(1) 每個傳感器節點一次只能與一個節點完成通信；(2) 在每個節點處都可實現數據融合；(3) 該網絡由多個單層簇構成。

2　模型建立

2.1數據收集延遲

D(N)=ZK-1-1+N-ZK-1+1=N=D(N)max

(9)

一般而言，D(N)依賴于壓縮率r與第K個簇的尺寸。當第K-1個簇結束時，則第K個簇可與融合中心通信，使得D(N)為：

D(N)=「max{T′(2K-1-1),N-2K-1-1}?+

(10)

T′(2K-1-1)=T′(mK-1-1)

(11)

其中，「x?代表取大于x的最小整數；T′(2K-1-1)代表前K-1個簇收集數據所需的延遲。

2.2能量消耗

WSN節點能耗主要是由于其收發模塊引起的。WSN節點可以看出是有三個主要單元組建的裝置，分別是：微控制器單元MCU、收發器單元TCR以及傳感器電路板單元SB。則WSN網絡結構的能耗模型E為：

Ei_SN=Ei_MCU+Ei_TCR+Ei_SB

(12)

Ei_TCR=Ei_TCR_RX+Ei_TCR_TX(di)

(13)

其中，Ei_MCU代表MCU的能耗；Ei_TCR為TCR的能耗；Ei_SB為SB的能耗；Ei_TCR_RX代表TCR在接收數據時的能耗；Ei_TCR_TX(di)代表TCR在傳輸距離為di時的能耗。

由于本文網絡結構有2K-1-1

(14)

對式(14)進行簡化，得到：

(15)

其中，C1為常量；di代表通信距離。

若路徑損耗指數為2，則Ei_TCR_TX(di)為：

(16)

其中，Ei_TCR_EC代表TCR的電路能耗；Ei_TCR_PA為TCR的功率放大能耗。

由于Ei_TCR_EC與Ei_TCR_PA均為常量，則式(15)可變為：

(17)

其中， C1、C2、C3均為常量。

3　本文網絡結構形成算法

Top-Down技術是一種集中式控制算法[10]。根據該技術可知，假設基站BS擁有WSN中所有傳感器的坐標，則基站會指示傳感器節點建立必要的數據鏈路，并形成相應的網絡結構。考慮含有N=2p,p=2,3,…個節點的網絡，則本文網絡結構的形成算法見圖2所示。具體步驟如下：

(3) 重復步驟(2)，直到b<2；并設置g=2。

(4) 當節點的連接度為N-g時，形成集合L；當連接度大于N-g時，形成集合U，從而使得集合L與U的節點數量相同。當集合L中的每個節點只與集合U中的單個節點相連時，則這兩個集合中節點的數據鏈會減少。當數據鏈減少時，設置g←g×2。

(5) 重復步驟(2)，直到g=N。

根據圖1可知，本文的網絡結構為樹形結構。在該結構中，一個孩子節點只與一個父節點相連。步驟(1)與步驟(2)會消除這些擁有相同連接度的節點之間的邊。因此，根據步驟(2)的輸出結果，一個孩子節點可與多個父節點相連。步驟(3)與步驟(4)通過消除孩子節點的多余邊緣，確保剩余邊緣總權重最小。步驟(4)處理后，一個孩子節點只與一個父節點相連。

圖2　基于Top-Down技術的本文網絡結構形成(N≥4)

為了具體解釋基于Top-Down技術的本文網絡結構形成過程，本文以N=8為例：

(4) 由于b=1<2，繼續執行算法，設置g=2。當節點連接度N-g=6時(如圖(d)中的A、H)，形成集合L；當連接度大于N-g時(如圖(d)中的B、G)，形成集合U。逐步減少集合L與集合U之間的節點連接，直到集合L中的節點只與集合U中的一個節點相連，從而使得總邊緣權重最小，見圖3(d)。并借助Munkres分配算法[12]來解決其中的權重匹配問題。設置g→2g=4。

(5) 由于g=4

(6) 當g=8=N時，該算法結束。此時形成的網絡是由連接度為Log2N=3的兩個相互相連的節點構成。在這兩個節點中，靠近基站的節點(如圖(f)中的B)會被擇取為簇頭，并直接與基站相連。此時，簇頭的連接度為Log2N+1=4。

圖3　N=8時的網絡結構形成(圓圈代表傳感器節點；矩形代表基站)

4　本文網絡結構的能耗優化

為了優化本文網絡結構的能耗，使得數據收集能耗水平維持在一個最低水平，則需要最小化該網絡結構的通信距離。優化步驟如下：

(1) 考慮含有2K-1-1

(2) 在集合S中擇取前k個元素，視為該網絡中的簇頭。

(3) 利用二進制整數規劃方法[13]來最小化簇頭之間與簇成員之間的通信距離：

(18)

(19)

(20)

(21)

其中，dij代表節點si、sj之間的距離；xij是用于顯示節點si、sj之間連接的坐標；mK代表第K個簇中節點的最大數量。

簇頭主要負責收集來自簇成員的數據；簇成員負責數據融合，且把信息廣播到融合中心。其中，簇頭的能耗是最高的。因此，在步驟(2)中，主要將剩余能量較高的節點視為簇頭。步驟(3)主要是最小簇頭之間與簇成員之間的通信距離。而式(19)是為了確保一個簇成員只與一個簇頭相連。式(20)、式(21)是為了確保第K個簇被簇成員填滿。

5　實驗仿真與分析

在Matlab工具中測試本文網絡結構的延遲與能耗水平。為了體現本文網絡結構的優異性，將當前性能較好的數據收集網絡結構視為對照組：文獻[14]基于最小生成樹MST的網絡結構、文獻[15]基于CTP的網絡結構。在實驗中，數據有N∈[2,98]個節點隨機分布在100×100m2的傳感區域內。傳感范圍中心為(50m,50m)。具體的參數見表2所示。

表2　仿真實驗參數設置

5.1數據收集延遲

圖4顯示的是本文數據收集網絡結構與對照組的延遲測試結果。從圖中可以看出，當節點數目增加時，這些WSN數據收集技術的延遲都在增大。當時，本文機制的數據收集延遲是最小的，增長幅度較小，在節點數量超過50時，其狀態比較平穩。主要原因是本文采用了樹形思想，并將WSN的傳感器節點分割為不同尺寸的多個單層簇；且優化了節點間的通信距離，使得簇頭以交錯方式完成數據傳輸通信。而文獻[14]與文獻[15]雖然也采用了樹形思想，并能最小化通信距離，可以降低網絡能耗；但是這些網絡結構是將節點分割成多層結構，造成其延遲較大。

圖4　不同數據收集網絡結構的延遲測試

5.2能耗水平

圖5　不同數據收集網絡結構的能耗測試

5.3網絡生命周期

圖6顯示的是本文數據收集網絡結構與對照組的延遲測試結果。根據圖中顯示，當節點數目增加時，三種網絡結構的網絡生存時間在減少。由于節點數目增加，能耗也在增大。文獻[15]的網絡性能較差，其生命周期較短。而本文網絡結構的存活時間最長。根據圖5可知，本文網絡結構的能耗水平維持在最低值，從而延長了網絡存活時間；而文獻[15]的能耗較大，故其壽命周期最短。

圖6　不同數據收集網絡結構的生命周期測試

6　結　語

為了降低數據收集過程的延遲，并優化網絡能耗水平，本文利用樹形結構思想，并將WSN的傳感器節點分割為不同尺寸的多個單層簇，繼而構造了新的網絡結構，使得簇頭以交錯方式完成數據通信，大幅度降低數據收集過程的延遲；隨后，建立了WSN數據收集的延遲與能耗計算模型；再借助Top-Down技術，設計了網絡結構的形成算法，通過最小化通信距離，優化了數據收集機制的能耗水平。實驗結果表明：本文網絡結構能夠有效降低WSN數據收集過程的延遲；且使得整個通信能耗維持在最低水平。

[1]RamM,KumarS.AnalyticalenergyconsumptionmodelforMACprotocolsinwirelesssensornetworks[C]//Proceedingsof2014InternationalConferenceonSignalProcessingandIntegratedNetworks,2014:444-447.

[2] 余歡,劉群.基于異構的無線傳感器網絡能量空洞緩解研究[J].計算機工程與設計,2014,35(7):2261-2266.

[3]YangZM,RenKJ,LiuC.EfficientdatacollectionwithspatialclusteringintimeconstraintWSNapplications[C]//Proceedingsof2012InternationalConferenceonPervasiveComputingandtheNetworkedWorld,2013:728-742.

[4]BagciH,YaziciA.Anenergyawarefuzzyapproachtounequalclusteringinwirelesssensornetworks[J].AppliedSoftComputing,2013,13(4):1741-1749.

[5]GuptaM,SaraswatL.EnergyawaredatacollectioninwirelesssensornetworkusingchainbasedPEGASIS[C]//ProceedingsofIEEEInternationalConferenceonRecentAdvancesandInnovationsinEngineering,2014:1-5.

[6] 陳零,王建新,張士庚,等.無線傳感器網絡中基于樹的能量高效分布式精確數據收集算法[J].電子學報,2013,41(9):1738-1743.

[7] 任秀麗,湯一波,劉珊珊.一種移動基站的樹形無線傳感網絡數據收集方法[J].小型微型計算機系統,2014,35(5):1022-1026.

[8]QiaoCF,YinSY,LingL,etal.CollectionTreeProtocolResearchforReliabilityofDataTransmission[J].AppliedMechanicsandMaterials,2013,380-384:2897-2900.

[9] 楊成.樹形網絡容錯及性能分析[D].成都:電子科技大學,2011:26-50.

[10]RothWJ,NachtigallP,MorrisRE,etal.Afamilyofzeoliteswithcontrolledporesizepreparedusingatop-downmethod[J].NatureChemistry,2013,5(7):628-633.

[11]ShapiroA,TekayaW,CostaJPD,etal.Riskneutralandriskadversestochasticdualdynamicprogrammingmethod[J].EuropeanJournalofOperationalResearch,2013,224(2):375-391.

[12]KuhnHW.TheHungarianmethodfortheassignmentproblem[J].NavalResearchLogistics,1955,2(1-2):83-97.

[13]KolaitisPG,PemaE,TanWC.Efficientqueryingofinconsistentdatabaseswithbinaryintegerprogramming[J].ProceedingsoftheVLDBEndowment,2013,6(6):397-408.

[14]ZhangMingcai,XueAnrong,WangWei.Unevenclusteringroutingalgorithmbasedonminimumspanningtree[J].JournalofComputerApplications,2012,32(3):787-790.

[15]GnawaliO,FonsecaR,JamiesonK,etal.CTP:Anefficient,robust,andreliablecollectiontreeprotocolforwirelesssensornetworks[J].ACMTransactionsonSensorNetworks,2013,10(1):739-751.

OPTIMISEDDESIGNOFWSNDATACOLLECTIONNETWORKSTRUCTUREBASEDONDELAYSAWARE

LiMiaoqiGaoXiaoyangZhouBeibei

(CollegeofEngineering,GansuAgriculturalUniversity,Lanzhou730070,Gansu,China)

Inordertosolvecurrentproblemssuchasbigdelayandenergyconsumptionduringdatacollectioninwirelesssensornetwork(WSN),inthispaperwedesignthedelayaware-basedwirelesssensorsdatacollectionnetworkstructure.WeintroducedtheideaoftreestructureanddividedthesensornodesofWSNintomultiplesingle-layerclusterswithdifferentsizes,followedbyconstructingnewnetworkstructuressoastoimproveitstopologicalstructureandtomaketheclustersfulfildatacommunicationinaninterleavedway,thissignificantlyreducedthedelayofdatacollectionprocess.Then,webuiltthedelayandenergyconsumptioncalculationmodeloftextWSNdatacollection,anddesignedtheformationalgorithmofthepresentednetworksstructurewiththehelpofTop-Downtechnology.Byminimisingthecommunicationdistanceweoptimisedtheenergyconsuminglevelofthedatacollectionmechanismasdiscussedinthepaper.ExperimentalresultsshowedthatcomparedwithexistingWSNdatacollectionnetworkstructure,theproposednetworkstructurecouldeffectivelyreducethedelayinWSNdatacollectionprocess,andwascapableofmaintainingtheenergyconsumptionofentirecommunicationatalowerlevel.

WirelesssensornetworkDatacollectionNetworktopologyCommunicationdistanceDelayawareEnergyconsuming

2015-05-26。國家自然科學基金項目(61164001)；甘肅省高等學校科研項目(1102-07)；甘肅省干旱生境作物學重點實驗室開放基金項目(1102-11)。李妙祺，講師，主研領域：網絡結構設計，檢測與控制技術。高曉陽，教授。周蓓蓓，工程師。

TP

ADOI:10.3969/j.issn.1000-386x.2016.10.028