基于延迟感知的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