一种多传感器网络数据收集协议的研究与设计

一种多传感器网络数据收集协议的研究与设计

数据收集是传感器网络最基本的应用，也是复杂应用的基础。在传感器网络中收集数据有两个非常重要的研究问题。其中之一是如何高效构建网络的拓扑结构，以及通过网络实现有效的能量路径。其次，基于有效的能量路径，如何确保网络的服务质量。有效的能量路径可以延长网络的生命周期，服务质量是传感器网络实际应用的基本要求。在现有的典型数据收集协议中,泛洪(flooding)协议实现简单,不需要为网络保持拓扑信息和实现复杂的路由发现算法,适用于健壮性要求高的场合,缺点是存在信息内爆(implosion)问题和部分数据重叠(overlap)现象.SPIN数据收集协议解决了扩散法存在的不足之处,缺点是在传输新数据过程中,直接向邻居节点广播ADV数据包,没有考虑其所有邻居节点由于自身能量的原因不愿意承担起转发新数据的功能,无法传输新数据而出现“数据盲点”.次优树数据收集协议将数据收集过程中的以数据为中心路由转化为最小Steiner树,树上每个中间节点都对收到的数据进行融合处理,减少了数据的传输量,节省网络的能量消耗,但它不适合大规模网络和数据相关性低的网络.平衡融合树(BATR)数据收集协议通过平衡网络内所有节点的能量消耗,延长了网络的生命周期,但由于簇头节点不监测数据,只对簇内数据进行处理,影响了数据的精确性,此协议不适合大规模网络.LEACH数据收集协议采用动态成簇算法平衡网络能量消耗、延长网络生命周期,且它的拓扑结构形成是完全分布式的,不需要全局的网络信息,缺陷是采用单跳路由,要求节点具有较大功率通信能力,扩展性差,也不适用于大规模网络.HEED数据收集协议与LEACH类似,但在簇头收集完数据后,簇头之间通过多跳方式与基站通信,但它没有考虑数据的区分服务.分析上述现有的数据收集协议,属于周期性数据收集的协议有LEACH,BATR,HEED,属于事件驱动数据收集的协议有Flooding,SPIN,次优树数据收集协议.无线传感器网络具有与应用高度相关的特性,如考虑煤矿井下采掘区的安全检测,适用其环境的传感器网络必须具备以下特性:一是网络规模大,网络需要覆盖整个采掘区和主要巷道;二是有实时性要求,当节点监测到某字段值(如瓦斯浓度)超过阈值时,必须以最快速度返回给观测者.通常情况下采取周期性数据收集模式,井下节点周期性地将监测数据返回给汇聚节点;但当节点监测到某字段值超过阈值时,则需要采取事件驱动数据收集模型,将数据迅速返回给汇聚节点.本文提出了一种具有区分服务功能、基于分簇结构的混合型数据收集协议(miscellaneousdatagatheringprotocolbasedonnodeclusteringinwirelesssensornetworks,MDGP),此协议同时包含了周期性数据收集、事件驱动数据收集方式,是一种混合型数据收集协议.MDGP构建高效的簇-树型网络拓扑结构,对数据流传输采用区分服务机制来满足服务质量,并在数据传输过程中进行高效的网内数据融合处理.1簇-树结构的描述本文假设N个传感器节点随机均匀部署在一个M×M的二维正方形区域A内,具有如下性质:1)传感器网络为高密度静态网络,节点部署后不再移动,但可扩充.所有传感器节点都被事先编排惟一的ID号,编号不妨为1,2,…,n,惟一的汇聚节点Sink编号为0,Sink节点位置任意,只要它能与至少一个传感器节点相互通信即可.2)所有节点不能获知其位置信息,因为这将增加成本和能耗开销.3)节点的初始能量可以异构且不能补充,这更接近真实的网络场景.4)各节点都有功率调节装置,即无线发射功率可控,能够根据接收者的距离远近来调节发射功率的大小.例如,BerkeleyMotes节点.每个节点均采用全向天线,各节点最大通信半径为R.5)网络中节点通过分布式成簇算法被划分成不同的簇,每个簇由一个簇头(clusterhead)节点和多个簇内成员节点(clustermember)组成;所有簇头节点形成以汇聚节点Sink为根的一棵数据汇集树(datagatheringtree),树上簇头节点负责数据融合操作和多跳路由转化.簇-树结构的数学描述如下:包含N个节点的平面无线传感器网络可抽象为一个连通图G=(V,E),V表示网络中节点集,E表示两个节点间的双向链路集,v0表示汇聚节点,|V|=N,设k为簇的个数,用Ci={vij}表示第i簇中的节点集合,其中vi0表示第i簇的簇头节点,vij表示普通节点.树型结构也可抽象为一个连通子图G′=(V′,E′),V′表示树上节点集,E′表示树上两个节点间的双向链路集.则整个簇-树结构满足以下条件:①k∑i=1Ci=n∑i=1kCi=n,所有节点都被划分在k个簇内;②|Ci∩Cj|=∅,任意两个簇之间没有交集;③|Ci|≥2,任意一个簇中的节点数目必须大于或等于2;④V′={vi0,i=1,2,…,k}∪{v0},树上节点由所有簇头节点和汇聚节点组成.在MDGP中,我们为传感器网络中的所有节点定义如下的数据结构,以维护节点的本地数据信息.typedefstruct{intID;*全网惟一的整数值标识*floatEr;*剩余能量值*floatEa;*所有邻居节点的平均剩余能量值*intd;*邻居节点个数,也称为度*charstate;*簇头或簇内成员*intlink;*上连指针*floatTiFusion;*簇内融合时延*}NodeLocalInfomationTable网络中每个节点ID用全网惟一的整数值标识,例如节点vi的ID值为i;Eir表示节点vi的剩余能量值(residualenergy);Eia表示节点vi的所有邻居节点的平均剩余能量值(averageresidualenergy);di表示节点的度(degree),即在vi通信半径圆盘内覆盖的节点个数,也称为该节点的邻居节点个数;state表示节点vi的状态,分簇完成后,节点的状态要么为簇头(取值为′H′),要么为簇内成员(取值为′M′);link表示上连指针,如果vi为簇头节点,则它指向所在汇集树中的父亲节点,如果vi为簇内成员节点,则它指向所属簇的簇头节点;TiFusion表示各簇头节点的簇内融合时延.2节点的重新分簇MDGP按“轮”(round)周期性运行,一轮包括簇的形成、汇集树的构造以及数据收集3个阶段.由于簇头节点比簇内成员节点消耗更多的能量,加上恶劣的环境监测也将造成不能预期的节点失效,周期性的重新分簇对于修复非连通区域以及在所有节点中平均分配能耗有非常重要的意义,当要监测的数据是动态的(如节点的剩余能量、节点度等),按轮重新分簇显得尤为重要.MDGP协议包含簇的形成、汇集树的构造以及数据收集3个过程,其间涵盖大量的消息传递,表1列出了为MDGP设计的所有报文格式及其描述,其中报文格式的第1项内容为报文的类别号,用以彼此区分报文,这些报文将在本文中反复出现.2.1树立节点为节点的seb报文文献中指出,以节点的剩余能量作为簇头竞争的惟一参数并不能有效地解决能量异构问题,该文提出了一种以邻居节点的平均剩余能量与节点本身的剩余能量的比值作为节点竞争簇头的参数的簇头产生算法,使簇分配更加均匀且延长了网络寿命.本文在此基础上提出了一种以邻居节点的平均剩余能量与节点本身的剩余能量的比值作为节点竞争簇头的主要参数,同时趋向于考虑“度”较高的节点作为簇头,从而产生簇头剩余能量较大、密度较高的簇,选举出具有较小数目的簇头覆盖集,进一步延长了整个网络的寿命.每轮开始时,首先进入邻居信息获取时段(neighbordiscoveryphase),用TNDP表示.在此期间每个节点以通信半径rc(为节点最大通信半径的一半,即rc=R2)广播SEB(sensorbroadcasting)报文.SEB报文包含该节点的剩余能量值,每个节点根据邻居节点发送的SEB报文内容计算并更新节点本地信息表中的Ea和d值.不妨任取一节点vi,vj为邻居,则Eia为Eia=1didi∑j=1Ejr.Eia=1di∑j=1diEjr.TNDP超时后,本轮进入簇头确定时段(headdecisionphase),用上述THDP表示.网络中的每个节点根据式(1)计算得到该节点发送取得簇头的申明报文CHB(clusterheadbroadcasting)的时刻t:t=(EiaEir×1di)×ΤΗDΡ‚(1)t=(EiaEir×1di)×THDP‚(1)这里,THDP是事先规定的簇头选择算法的持续时间值,Eir表示节点i的剩余能量.从式(1)可以看出,MDGP协议使用Eia?Eir作为节点竞争簇头的主要参数,使用节点的度di作为辅助参数,特别是对于一些位于监测边界的节点,由于这些节点的度趋近于1或2,势必增大了t的值,从而避免了其成为簇头.MDGP协议这样来产生簇头:节点按式(1)完成时刻t的计算后,如果没有收到任何邻居节点发出的CHB报文,则该节点向邻居节点广播CHB报文申明自己是簇头,如果该节点在t时刻前已经收到了某邻居节点广播的CHB报文,则该节点立刻放弃簇头竞争,然后每个节点根据自己的角色,修改节点本地信息表的state栏为′H′或′M′.簇头确定阶段THDP超时后,本轮进入节点归属时段(nodeattachmentphase),用TNAP表示.对非簇头节点而言,可能会收到几个来自不同簇头节点的CHB报文,节点向信号最强的簇头发送JOM报文,申请加入该簇.其中state栏为′M′的节点还需进一步更新link栏,使之指向所属簇头的ID.对簇头节点而言,接收来自其所有簇内成员节点的JOM报文.整个分簇的算法如图1所示:2.2簇内节点密度文献给出了覆盖比率和最少活动节点数量之间的关系式:k=-log(1-η)log(|A|+4√|A|rs|A|+4√|A|rs+πr2s)-‚(2)其中,η表示用户要求的覆盖率(所有活动节点覆盖的区域与整个监测区域A面积的比值),k表示最少的活动节点数量,rs表示节点的感知半径.簇内节点只与自己的簇头节点通信,它根据时隙表确定的顺序将监测到的数据发送给簇头节点.假设区域A内的节点密度为N?M2,簇半径为rc,则簇内的平均节点数为N×πrc2?M2,由于簇与簇之间存在交叠,因此簇内节点数m应小于N×πr2?M2,在节点密度很大的情形下,不仅数据冗余大,而且使得TDMA帧的时间较长,造成较大延迟.我们按式(2)选择出k个工作节点,由这些节点进行监测,其余节点进入睡眠状态,显然k值可远小于N×πrc2?M2.例如,文献指出,在200m×200m的区域均匀分布2000个节点,节点感知半径为rs=12m,簇半径即簇内通信半径rc=30m时,则每个簇中的平均节点数约为120,采用簇内覆盖思想后,若要求达到99%的覆盖率,每个簇只需要27个节点工作.则TDMA帧的持续时间可以缩短,也可降低数据延迟,大大减轻了簇头的负担.在MDGP中,每个簇头根据簇内活动节点的数目产生一个TDMA时隙表,簇头作为协调者调度簇内成员节点发送数据的时隙.簇头节点将包含时隙表的CBT报文(clusterheadbroadcastingtime-slot)通过广播方式发送给簇内成员节点.为了保证由所有簇头节点形成的子图是连通的,所有成为簇头的节点自行调整无线电发射功率,使簇间通信半径设置为R,即R=2rc,由于节点高密度部署,从上述簇生成算法的流程可知,覆盖区域A的所有以簇头为圆心、以rc为簇半径的圆盘相互交叠或至少相接,当簇头通信半径改为2rc时,由图论知识可以证得所有簇头节点形成的子图是连通的.2.3打造集群集相对独立的路由汇集树算法考虑到由以上方法构建的由所有簇头节点形成的子图是连通的,而构造路由汇集树实际上是构造以Sink为根、该子图的一棵生成树,生成树包含了网络所有的簇头且每个簇头只有一个父亲节点.我们用反向扩散法思想来构造路由汇集树:首先,Sink节点使用扩散法来发布SIB(sinkbroadcasting)报文,SIB报文内容包括round,fatherID,hop,TFusion和δ,其中round表示轮数,fatherID表示父节点的ID号,hop表示簇头节点到汇聚节点Sink的跳数,初始值为0,TFusion表示本轮的总控制融合时延,δ表示时延梯度值.构建汇集树的同时,通过级联时延方法解决了汇集树节点上数据融合的时间同步问题.级联时延是指在以汇聚节点为根、以簇头节点为中间节点的汇集树中,树上各中间节点根据其在树上的深度等待相应的融合时间后执行数据融合操作,即离根节点越近的中间节点等待的融合时延越大,反之,离根节点越远的中间节点等待的融合时延越小.因此在报文扩散的同时,每个中间节点必须根据本轮的总控制融合时延TFusion按梯度计算自己实际的融合时延TiFusion.为了控制扩散过程,SIB报文包含一个轮值round,round按轮递增1.各簇头节点接收到SIB报文后,节点先在报文缓中区中检查这个SIB报文的round值,如果发现己收到过此轮报文,则将它丢弃,如果是新报文,将fatherID值记入节点本地信息表的link,将跳数值增加1,即hop=hop+1,以此标记本节点在树上的深度,并向邻居转发SIB报文,然后,簇头节点根据自身所在汇集树上的深度计算簇内融合时延.计算融合时延的公式为ΤiFusion=ΤFusion-2(hop×δ).由所有的簇头节点构建路由汇集树的过程实际上是各簇头节点指向父亲节点的过程,对各簇头节点构建路由汇集树算法如图2所示:2.4紧急类别信息的融合路由汇集树结构建立以后,传感器网络就进入了稳定的数据传输阶段.簇成员节点将数据发送给各自的簇头节点,簇头节点将数据融合后,通过汇集树上其他的中间簇头节点发送到Sink节点.我们在MDGP数据收集协议中提出区分服务的思想,区分服务(differentiatedservice)是IEIF(internetengineeringtaskforce)在QoS领域所做的工作.本文在对传感器网络中数据进行网内数据融合的同时采取了区分服务机制.其思想是区分服务由充当路由的簇头节点提供,我们把服务类别分为两种:常规的和紧急的.大多数通信流量属于常规流量,但有一小部分分组属于紧急类别,紧急类别的分组应该可以直接通过汇集树而不需等待数据融合.实现这种策略的一种做法是,在簇头节点的输出路径上定义两个输出队列,一个用于紧急类别的分组,另一个用于常规分组,当一个分数到来时,根据它的类别排入相应的队列,除非紧急队列为空,否则总是紧急队列得到优先服务.传感器节点在监测到数据后,马上与关键字段设定的阈值进行对比,根据对比的结果确定数据的服务类型,将此服务类型填充在数据分组的“数据类型”域中,然后将数据分组发送给簇头节点;簇头节点根据服务类型来为其选择排入哪种服务队列中.MDGP具有区分服务机制的数据收集算法描述为,对簇内成员节点而言,由SIB报文唤醒后,节点开始采集监测数据,把监测数据与设定阈值进行比较,如果监测到的数据值没有超过阈值范围,则SED(SEnsordata)数据报文的immediatetype字段值为FALSE,表示常规数据;反之,则为TURE,表示紧急数据,需要尽快传送给汇聚节点,然后节点根据之前簇头节点广播的TDMA时隙按顺序将数据SED报文发送给簇头节点.对簇头节点而言,它接收到其簇内节点传送来的SED数据报文后,首先查看分组的数据类别字段,判断是否为紧急数据,如果是常规数据,则将其存储在缓冲区内,等待融合时延时间到后,将缓冲区内数据和自身监测到的数据进行数据融合,即更新SED数据报文的data内容、ID统一换成簇头的ID,并把融合后的数据报文发送到它在汇集树上的父节点;如果是紧急数据,则不等待融合直接将该数据分组发送到它在树上的父节点.簇头节点与簇内节点的数据收集和数据融合算法伪代码如图3所示:3mdgp与heed算法比较在NS2平台上我们对MDGP进行仿真测试,仿真场景1,2分别为1)100个无线传感器节点随机分布在100m×100m的平面监测区域,汇聚节点远离监测区域,位于坐标(50,120);2)400个无线传感器节点随机分布在200m×200m的平面监测区域,汇聚节点远离监测区域,位于坐标(100,225).场景1,2中所有节点都静止不动,且都能与汇聚节点通信.接收机电路和发射机电路每处理1b数据的功耗为Eelec=50nJ?b,发射放大器向单位面积发射1比特数据的功耗为εamp=100pJ?b?m2,簇头节点进行本地处理和数据融合时,每处理1b的数据需要的能量损耗为EFusion=5nJ?b,节点空闲时能耗Pidle=0W,节点睡眠时能耗Psleep=0W.对于两个实验场景,设定的仿真参数如表2所示:无线传感器网络中衡量网络数据收集协议性能的一个主要指标是网络的生命周期