mr-mc无线传感器网络基于森林的数据收集研究-张伟平.pdf

《mr-mc无线传感器网络基于森林的数据收集研究-张伟平.pdf》由会员分享，可在线阅读，更多相关《mr-mc无线传感器网络基于森林的数据收集研究-张伟平.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第37卷第3期2016年3月通信学报Joumal on CommunieationsVjl 37 NO 3March 2016doi：1011959jissn1000436x2016051MRMC无线传感器网络基于森林的数据收集研究张伟平1，郭亚红2，王蒙1，一，倪林雨1,3李金宝1，3(1黑龙江大学计算机科学技术学院，黑龙江哈尔滨1 50080：2黑龙江大学信息科学与技术学院，黑龙江哈尔滨1 50080：3黑龙江省数据库与并行计算重点实验室，黑龙江哈尔滨150080)摘要：传感器网络的部署环境以及节点自身的限制，导致传感器节点很容易出现故障并且难以维护。在基于树的数据收集过程中，节点故障或者

2、链路拥塞会造成较高的通信时延，甚至数据丢失。针对该问题提出以森林作为路由结构进行数据收集的策略。首先提出一个建立森林的算法，然后以多棵树作为路由结构进行数据收集。理论分析和实验结果表明，提出的方法可以有效减少数据收集过程中的数据丢失，在有25个故障节点的情况下，3棵树的森林路由结构收集的数据量与基于连通支配集的路由树收集的数据量相比多55，并且能降低数据收集的延迟。关键词：无线传感器网络；路由树；数据收集；延迟中图分类号：TP212 文献标识码：AForest based data collection in MRMC wireless sensor networksZHANG Weipin9

3、1，GUO Yahon92，WANG Men913，NI Linyul3，LI Jinba013(1 School ofComputer Science and Technology，Heilongjiang University,Harbin 1 50080，China；2School ofInformation Science and Technology,Heilongjiang University,Harbin 150080，China；3Key Laboratory ofDatabase and Parallel Computing ofHeilongjiang Province，

4、Harbin 150080，China)Abstract：The limit of node itself and deployment environment of WSN result in the node was prone to failure and diffi-cult to maintainIn the treebased data collection process，the node failure or link congestion could result in higher cornmunication delay，or even data lossTo solve

5、 this problem，a strategy for data collection was proposed which used forestas the routing structureFirstly,an algorithm for the construction of forest was proposed，and then collect data throughtrees in the forestTheoretical analysis and simulation results show that，the method could reduce the loss o

6、f data in thedata collection process effectively，in the case of 25 fault nodes，the amount of data collected by forest routing structure of3 trees compared to the amount of data collected from the connected dominating set is more than 55，and reduce the la-tency of data collectionKey words：WSN，routing

7、 tree，data collection，latency引言近年来，无线传感器网络因其巨大的潜力被广泛应用于军事领域、环境监测、医疗和工农业等领域中。在这些应用中，大量的传感器节点监测周围的环境，并将感知的数据通过多跳路由传输到汇聚节点。作为无线传感器网络的主要功能之一，数据收集问题受到众多研究者的广泛关注。无线传感器网络通常部署在无人值守的野外环境中，网络中的传感器节点有可能因为出现故障收稿日期：20l 51030；修回日期：2016一叭-18通信作者：郭亚红，iblihUueducn基金项目：国家自然科学基金资助项目(No61370222，No61300225)；黑龙江省自然科学基金资助

8、项目(NoF201324)；黑龙江省高校科技创新团队建设计划基金资助项目(No201 3TD012)；哈尔滨市优秀学科带头人基金资助I页目(No20 1 5RAXXJ004)Foundation Items：The National Natural Science Foundation ofChina(No61370222，No61300225)，The Natural Science Foundation of Heilongjian2 Province(NoF201324)，Technology Innovation of Helongjiang Educational Committee

9、(No2013TD012)，TheProgram for Group of Science Harbin Technological Innovation Found(No201 5RAXXJ004)20160511万方数据第3期 张伟平等：MRMC无线传感器网络基于森林的数据收集研究 41而导致无法正常工作，例如节点的电池能量耗尽、动物踩踏以及大雨雷电的破坏等。由于在无线传感器网络中进行数据收集通常使用树作为路由结构，因此，当网络中的某个节点出现故障时，以该节点为根的子树上的所有数据都将无法传输到汇聚节点。传感器节点使用无线信道进行通信，多条链路竞争通信资源有可能会导致传输失败。链路调度即为

10、每条链路分配指定的传输时槽进行通信，可以提高链路的并行性，有效降低数据收集延迟。目前的链路调度方案均假设在满足特定的干扰模型(协议干扰模型、物理干扰模型、信噪比模型等)下，每次链路调度都是成功的。然而在现实情况中，链路通常需要多次传输才能够成功，造成这种现象的原因有多种，例如链路可能会由比特误码率等原因拥塞。在以树作为路由结构的链路调度中，如果某条链路拥塞，那么该链路不会被调度直到下一个周期的调度时槽到达。此外，如果2个节点使用某个信道进行通信时出现拥塞，那么该信道在最近一段时间内都会处于拥塞状态。因此，如果链路的性能不稳定，那么数据收集的延迟将会受到很大影响。综合上述2个方面的分析，考虑节点

11、出现故障以及链路拥塞等原因，本文提出了一个新颖的基于协议干扰模型的以森林作为路由结构的数据收集策略。延迟的数据收集结构，文献8】和文献9以树作为路由结构，通过调度链路节约数据收集时间。针对收集决策信息问题，当时间不足以收集来自网络中的所有节点的决策时，文献10l考虑收集具有更高可靠性的决策。文献1 11针对城市建筑中使用的无线传感器网络设计跨层数据收集机制，通过在路径发现阶段使用数据转发提高数据传输速率、降低延迟。文献12综合考虑了数据收集的延迟和容量问题。此外，文献13】首次研究如何尽可能传输较少的数据，同时传输的数据满足所有应用的要求。文献14首次提出在大规模无线传感器网络中，通过压缩采样

12、理论收集数据，该方案能够降低整体通信负载且不会引入额外的计算。文献15分别研究了基于树和簇的数据收集和聚集协议。文献16分析了数据收集、聚集和选择的复杂度。文献17设计了一个自适应的数据收据近似算法。文献18提出了基于小波分段常值压缩的数据收集方法。文献191提出了一种分布式的高效节能的无线传感器网络数据收集协议。同上述工作不同，本文研究的问题是考虑网络中节点出现故障以及拥塞等情况，如何收集网络中尽可能多的数据，并且数据收集的延迟较低。针对该问题，本文提出以森林作为路由结构进行数据收集的策略，森林表示的是具有多棵路由树的拓扑结构。2相关工作 3建立路由结构对于不同的应用环境，无线传感器网络中数

13、据收集协议的设计目标也不尽相同，下面分别从容量和延迟等方面介绍数据收集协议的研究现状。文献26】研究了在不同类型的网络中数据收集容量的问题。其中，文献2】分析了在任意单radio、单信道无线传感器网络中的数据收集容量问题，该文献分别讨论了当通信模型采用磁盘图模型和一般图模型，干扰模型分别采用协议干扰模型以及物理干扰模型时数据收集容量的上下界。文献【3】和文献4】分别研究了在DRMC无线传感器网络和大规模概率无线传感器网络中的数据收集容量问题，并分别设计了快照数据收集算法以及连续数据收集算法。文献【5和文献【6】分别研究了随机网络和异步网络中的数据收集容量问题。文献712以缩短数据收集的延迟为目

14、标设计数据收集协议。其中，文献7考虑的是建立一个低在大多数的应用中，节点都是密集分布在监测区域内的，也即一个节点通常有多个邻居节点可以通信。为了避免由于信道竞争、节点故障等导致的大规模数据拥塞，本节提出建立多棵不相交的树形成森林进行数据收集。这里的不相交有2个方面的含义：1)网络中不存在某个节点在任意2棵路由树上使用除sink以外的相同节点作为父亲节点，即物理链路不相交；2)不存在某个节点在任意2棵树上使用相同的信道进行数据传输，也即逻辑链路不相交。因此，对于一个待发送数据的节点，当一棵路由树上的父亲节点出现故障时，可以经由其他路由树上的父亲节点将数据发送到sink。例如，给定拓扑结构如图1(

15、a)所示，图中的虚线表示节点之间可以进行通信。图l(b)和图1(c)是对图1(a)给出的网络拓扑使用算法1建立的2棵不相交的路由树。从万方数据通信学报 第37卷图1中可以看到，当节点1因为出现故障而无法通信时，节点6和7可以通过第2棵路由树上的节点2进行数据传输，避免了节点6、7、11和12的数据的丢失。早、，!；!I、象泉9 ：、，、，：、，。：、，。：警：霉暴，暴，罗 i、：rj、；，：；。，i(b)使用算法l建立的一棵树 (c)使用算法1建立的另一棵树图1 网络拓扑结构以及建立的2棵路由树31准备工作考虑一个由个传感器节点和一个汇聚节点sink组成的无线传感器网络，记为G=(K目，其中，

16、矿是网络中节点构成的集合，E是网络中所有可能的通信链路集合。假设sink具有相对强大的能力，不会出现故障或者拥塞。假设网络中的每个节点配备尺个radio(无线收发器)，并且网络有R个可利用的正交信道，记为Channel=C1，C2，CR。设厂和P分别表示节点配备radio的通信半径和干扰半径，在此假设所有radio具有相同的干扰半径和通信半径。设hop。表示节点v距离sink的最短跳数，H表示网络的高度，即网络中的节点距离sink的最大跳数。假设网络采用协议干扰模型，即2个节点可以成功通信当且仅当在接收节点的干扰范围内没有其他节点在同一时槽使用相同信道进行通信。设Pv=bl甜V，(“，v)E，

17、hop。P，则将节点y加入到集合影中。3)最后将前i-1个调度集合U s?的节点按IjP且怕一P川P，则将节点v加入到集合影中。算法2划分链路集合输入：x棵路由树互，互，巧输出：X棵树的4个链路子集合霹(1kX，1i企1)豇=1；21while kX do3) i=1；4) while iA do5) s?置为空集，按照Pro(v，k，f)的值将VU$中的节点降序排列；l(，61 for优先级最高的节点v do7) if节点v与集合s!中的任意节点,不冲突8)then将节点v加入到集合sj中；9) end for10) 按Pro(v，k，t)的值将U吖中节点v降lJ，序排列：11) for优先

18、级最高的节点v do121 if节点v与集合影中的任意节点,不冲突13)then将节点v加入到集合掰中；14) endfor15) f+；16) end while17)七+；18)end while42理论分析下面对本文提出的基于森林的数据收集策略进行理论分析，并举例子进行说明。定理1给定一个个节点组成的传感器网络，高度为H，可以建立x棵不相交的树，设在一次数据收集中节点出现故障的平均概率是口，那么Hsink平均可以收集到(1一a)fl一口工)i“个数据。证明 假设对于网络中的任意节点v发送的数据分组，该数据分组能够成功传输到下一跳当且仅当节点v未出现故障，并且节点v在X棵树上的父亲节点集合

19、至少有一个未出现故障，因此节点v将数据分组成功传输到下一跳的概率是(1一口)(1一矿)。由路由结构可知节点v到达sink的路径长度为hop。，万方数据第3期 张伟平等：MRMC无线传感器网络基于森林的数据收集研究 45因此节点V产生的数据分组成功传输到sink的概率为(1一叻(1一)慨。那么，数据分组到达sink的H平均概率为(1一a)0一口x)了，也即sink可以收集到H-N(1一口)(1一口x)2。个数据。以一个例子进行说明，假设网络中有100个节点，网络高度为12层，节点的平均故障概率口为005，每个节点传送一个数据分组的时间f为1个单位时间，节点传输数据失败，重传一个数据分组所需时间为

20、12 f，并假设网络拓扑可以构造出包含3棵树的森林。那么，根据定理l中的公式N(1一口)(1一口T)了1 以3棵路由树收集数据时sink12可以收集到大约100(1005)(1一o053)2。95个数据分组，由于数据重传所产生的延迟为512t=-6个单位时间。而在以一棵树作为路由结构的数据收集中，sink可以成功接收到的数据分组个数为12100(I一005)(100511 2z 74，由于数据重传所产生的延迟为26x 12t=312个单位时间。5模拟实验与结果分析本文采用Microsoft Visual C+60编程环境模拟无线传感器网络，假设400个传感器节点均匀随机地分布在50 mx50

21、m的监测区域内，sink位于网络的中间位置，网络高度为12层，节点的通信半径和干扰半径均设置为5 m。假设传感器网络的MAC层使用TDMA协议工作，即时间可以划分成若干个时槽。节点每个可利用的信道都有相同的带宽，设为l。假设每个节点使用的任意2个不同的信道都是正交的，即每个节点在任意2个信道上的通信不存在干扰。设网络中节点出现故障的概率是5，sink收集数据的成功率为95，则根据定理l可以得到森林中需要构建的树的棵数为3。假设每个节点每次产生一个数据，该数据可以在一个时槽内成功传输对于数据收集，所有节点在指定时间的所有感知数据集合称为一个快照。收集一个快照的数据称为快照数据收集，收集多个连续快

22、照的问题称为连续数据收集，数据收集延迟的单位是时槽。下面分别进行节点的故障对收集到的数据量的影响实验以及链路拥塞对数据收集的延迟影响的实验。51数据收集量实验下面对快照数据的收集进行实验，在该实验中分别对比森林中包含2棵路由树和3棵路由树时整个网络的分组丢失率，并且将其与基于连通支配集(CDS)的路由树131进行对比。如图2所示为出现故障的节点个数对收集到的数据量的影响情况，其中，横坐标为出现故障的节点个数，在此设置为从0-25个，并且每隔5个做一次记录，这里的故障节点个数表示在一次数据收集过程中出现故障的节点个数，纵坐标表示收集到的数据个数。4035(30(冀25(鹫20羹105(5 10

23、15 20 25故障节点个数图2故障节点个数对数据收集量的影响从图2中可以看出，随着出现故障的节点个数的不断增多，基于连通支配集的路由树收集到的数据量明显减少，大约增加5个故障节点收集到的数据量降低60个左右。这是由于在一棵路由树上一个节点的故障不仅会导致自身数据丢失，还会导致其所有子孙节点的数据丢失。而2棵路由树和3棵路由树丢失的数据量较低，这是由于在以森林做路由结构的情况下，一个节点出现故障，其孩子节点可以转换到其他路由树上进行数据传输，从而保证未出现故障的节点在很大程度上有到达sink的路径。图3是连续数据收集中随着快照次数的增加sink收集到的数据量情况，也即收集到的数据个数随着网络使

24、用时间的变化趋势。如图3所示，横坐标表示在连续数据收集中执行的快照次数，纵坐标表示sink收集到的数据个数。以森林作为路由结构收集到的数据量明显高于基于CDS的路由树收集到的数据量，并且随着快照次数的增多，这种优势愈加明显，在进行40次快照后包含3棵树的森林仍旧可以收集一半的数据量。此外，在初始的快照收集中包含2棵树的森林和包含3棵树的森林收集万方数据通信学报 第37卷到的数据量相差无几，但随着快照次数的增多，包含3棵树的森林优势逐渐明显，并且趋于稳定。这是由于初始时出现故障的节点个数较少，这些故障节点的子孙节点数据可以经由第2棵树传输到sink，而不必使用第3棵树；当故障节点的个数随着快照次

25、数增加时，网络中的一些节点必需使用第3棵树才能够传输数据。一限照次数幽3快照次数刈敛据收集量的影响图4是节点出现故障的概率对收集的快照次数的影响实验。如图4所示，横坐标是在数据收集过程中节点出现故障的概率，纵坐标表示在连续数据收集中收集到200以上数据的快照次数，即收集到网络中一半节点感知数据的快照次数。随着节点故障概率的增加，收集200个以上数据的快照次数随之减小，但是包含3棵树森林的快照次数总是基于CDS路由树的快照次数的2倍左右。52数据收集延迟实验在链路拥塞的实验中，分别测试链路出现拥塞的概率以及拥塞的等待时间对数据收集的影响。拥塞的等待时间表示在一条链路出现拥塞后该链路在一段时间内会

26、一直处于拥塞状态，这段时间称为拥塞的等待时间。在实验中分别对采用TAG算法【20】形成的单棵路由树和包含3棵路由树的森林数据收集的延迟进行了测试。为了实验的公平性，在TAG路由树数据收集过程中，令网络中的每个节点仍有3个可以使用的正交信道进行通信。图5为链路出现拥塞的概率对数据收集延迟的影响。如图5所示，横坐标表示链路在每个调度时槽出现拥塞的平均概率为002，设置拥塞等待时间为3个时槽，纵坐标表示数据收集的延迟。即图中可以看到随着链路拥塞概率的增大，收集延迟也随之增加，而以森林作路由结构的延迟要小于TAG的路由结构。这是由于在基于森林的数据收集过程中，在某一时槽一条链路出现拥塞后，该链路的发送

27、节点在较短的时间内会以其他节点作为父亲节点重新传输失败的数据，降低了数据的等待时间。图6所示为链路拥塞的等待时间对数据收集延迟的影响，在此设置每个时槽链路出现拥塞的概率为005。横坐标为链路拥塞的等待时间，即08个时槽，纵坐标表示数据收集的延迟。从图6中可以看到，TAG路由树的数据收集延迟几乎与等待时间成正比，而基于森林的数据收集延迟随着拥塞等待时间的增加增长相对缓慢。在TAG路由树的数据收集过程中，假设一条链路拥塞，如果在下一个调度时槽仍处于拥塞等待状态，那么该链路的发送节点只能等待下一个调度时槽的到来。而以森林作为路由结构的数据收集过程中，该链路的发送节点可以使用其他路由树的链路进行数据传

28、输，而不必等待该链路恢复正常。链路拥塞概率目5链路拥雍概牢埘延迟的影口自万方数据第3期 张伟平等：MRMC无线传感器网络基于森林的数据收集研究 47至芝鞠剖丞董囊彝拥塞等待时问图6拥塞等待时间对收集延迟的影响6结束语在无线传感器网络中，基于TAG路由树的数据收集策略在节点出现故障时会造成较多的数据丢失，此外，节点的拥塞会造成较高的数据收集延迟。针对上述问题，本文提出建立森林作为收集网络中数据的路由结构，并且设计了基于森林的数据收集算法。理论分析和实验结果表明，在网络中节点出现故障概率较高或者拥塞严重的情况下，本文提出的方法能以较低的延迟收集到网络中的大部分数据。参考文献：【l】 李风保，李凌无

29、线传感器网络技术综述【J】仪器仪表学报，2005，26(8)：559561LI F B，LI LSurvey on wireless sensor network techniquesJChinese JournalofScientificlnstrument。2005，26(8)：559561【2】 CHEN S，HuANG M，TANG s，et a1Capacity of data collection inarbitrary wireless sensor networksfJl，Parallel and Distributed Systems，2012，23(1)：52-60【3】J

30、I S，LI YJIA XCapacity ofdualradio multi-channel wireless sensornetworks for continuous data collectionC门NFOCOM 20llProceedings IEEEc2011：10621070【4】JI S，BEwLH R CAI ZSnapshotcontinuous data collection capacityfor largescale probabilistic wireless sensor networksCINFOCOM，2012 Proceedings IEEEc2012：10

31、351043【5】c Hl!N S，WANG YLI M，et a1Data collection capacity of randomdeployed wireless sensor networksC1GIobal TelecommunicationsConference2009IEEEc2009：16【6 JI S，CAJ ZDistributed data collection and its capacity inasynchronous wireless sensor networksC1 脚OCOM， 2012Proceedings IEEEc2012：211321217 CHE

32、NG C TTSE C K，LAU F C MA delayaware data collectionnetwork structure for wirelessusor neworksJ1Sensors Journal，20ll，1 1(3)：6997108 INCEL O D，GHOSH A，KRJS矾AMACHARJ B，et a1Fast datacollection in treebased wireless sensor networksIJ IEEETransactions on Mobile Computing,2012，1l(1)：86999】 INCEL O D，GHOSH

33、 A，KRISHNAMACHA砌BSchedulingalgorithms for treebased data collection in wireless sensornetworksMTheoretical Aspects of Distributed Computing in SensorNetworksSpringer Berlin Heidelberg20ll：407埘5【10】SEKSAN L，ED峭肋J，COYLE0ptimizing the collection of localdecisions for timeconstrained distributed detecti

34、on in WSNsiCFINFOCOM,2013 Proceedings正EEc2013：1923193111】HUANG C，LIN T，CHEN L，et a1XD：a cross-layer designed datacollection mechanism for mission-critical、恻in urban buildingsfCInternational Conference on Mobile Data Management：SystemsServices and Middleware 2009f121 CHEN S，WANG YLI M，et a1Order-opti

35、mal data collection inwireless sensor networks：delay and capacityCl6th Annual IEEECommunications Society Conference onSensor,Mesh and Ad HocCommunications and Networks2009SECON09c2009：19f131 FANG)(GAO H，LI J，et a1Application-iware data collection iBWireless Sensor NetworksCNFOCOM，2013 Proceedings IE

36、EEc2013：1645一1653【14】LUO C，WU FSUN J，et a1Compressive data gathering for large-scale wireless sensor networksC厂111e l 5th Annual IntamationaIConference on Mobile Computing and Networking，ACM，c2009：145一156【l 5】WANG W，WANG B，LIU Z，et a1A cluster-based and treebased powerefficient data collection and a

37、ggregation protocol for wireless sensornetworksJInformationTechnology Journal，2011，10(3)：557-564【16】LI M，WANG Y，WANG Y Complexity ofdata collection，aggregation，and selection for wireless sensor networksJ1IEEE Transactions on，Computers，201l，60(3)：386399【17】WANG C，MA H，HE Yet a1Adaptive approximate da

38、ta collectionfor wireless sensor networksJIEEE Transactions onParallel andDistributed Systems，2012，23(6)：10041016【18】李杨，郭龙江，李金宝，等传感器网络基于小波分段常值压缩的数据收集研究【J】仪器仪表学报，2013，34(1)：119127LI Y：GU0 L J，LI J B，et a1Data collection using waveletsegmentconstant compression in wireless sensor networksJChinese Jour

39、naIofScientific Instrument，2013，34(1)：119一127【19】史久根，胡小博高效节能的无线传感器网络数据收集协议电子测量与仪器学报，2012，26(5)：437445，SHI J G HU X BEnergyefficient data gathering protocol for wirelesssensor networksJJournal ofElectronic Measurement and Instrument，2012，26(5)：43744520】MADDEN S，FRANKLIN M J，HELLERSTEIN J M，et a1Tag：a

40、 tinyaggregation service for ad hoe sensor networksJOSDi Conf,2002，36(1)：1-28作者简介：张伟平(1964)，女，黑龙江哈尔滨人，黑龙江大学工程师，主要研究方向为无线传感器网络。郭亚红(1972一)，女，黑龙江双鸭山人，黑龙江大学副教授，主要研究方向为无线传感器网络。王蒙(1989)，女，黑龙江牡丹江人，黑龙江大学硕士生，主要研究方向为无线传感器网络。倪林雨(1990)，男，黑龙江庆安人，黑龙江大学硕士生，主要研究方向为无线传感器网络。李金宝(1969)，男，黑龙江庆安人，博士，黑龙江大学教授，主要研究方向为无线传感器网络、数据库原理、移动计算和并行计算。20160518万方数据