拓扑层次（共3篇）
拓扑层次 篇1
随着通信、信息、网络技术的高速发展与广泛应用,人们对通信网络的依赖愈加明显,随之而来的可靠性问题日益成为用户关注的焦点领域。现代通信网络是一个复杂系统,融合了多学科领域,因此对其可靠性的研究是一项系统工程。
从目前的公开文献来看,通信网络可靠性研究分布于网络应用的各个层次与领域,一般可对应于OIS(Open System Interconnect)系统模型的划分。同时,通信网络的复杂性、动态性、多态性等属性为可靠性评估与优化提出了新的挑战,导致了研究的视角与侧重点也不尽相同。拓扑结构是通信网络的核心特征,其依据拓扑来组织网络形态,进而体现通信网络系统的整体性。因此,对通信网络拓扑可靠性的研究处于整个通信网络可靠性研究的中心地位。
1 通信网络可靠性研究的层次体系
1.1 拓扑可靠性处于核心地位
如引言中所述,拓扑可靠性并不能完全表征整个通信网络的可靠性,其研究对象只关注于网络的拓扑结构,忽略了网络通信设备、路由策略、承载业务、管理效率等因素所带来的可靠性变化。拓扑层高于设备层,同时是路由层、业务层等高层可靠性的基础,在整个通信网络可靠性中处于承上启下的中间环节,其影响可见一斑。
通信网络可靠性可分层讨论,每层均应设计相应的指标与测度方法,以完成对通信网络可靠性的定量描述。因此,通信网络可靠性应具备一个同向、协调、完备的指标体系。在对目前文献梳理的基础之上,可得可靠性指标体系。同时,各文献对可靠性的理解与划分具有相互重叠性,而且关于同一类指标的描述也不尽相同,新的指标也不断被提出。
1.2 拓扑可靠性指标分析
在网络拓扑可靠性的指标描述上是想通的,即在抗毁性与生存性上具有广泛共识。同时可见,连通度是两者的指标与测度设计的基础因素。
(1)网络拓扑抗毁性。主要用于刻画在确定的网络组织结构(即网络拓扑)、预定的破坏(攻击)方案下,通信网络依然能够保持全网或部分连通(物理可达)的能力。在对实际网络进行拓扑抽象之后,抗毁性指要破坏(中断)部分网络节点连接需要移除(破坏)的最少网络节点或链路(边)的数目,从而表征出破坏整个或部分通信网络的困难程度。可见,抗毁性完全由网络拓扑结构所决定,是可靠性的一个确定型指标。
(2)网络拓扑生存性。生存性最显著的变化是引入了网络部件的失效(故障)概率,用于刻画在随机故障或蓄意破坏之下,保持通信网络整体或部分连通的概率。其建立在图论与概率论基础之上的可靠性分析,不仅受网络拓扑结构的影响,同时还依附于网络部件(设备)的故障概率与模式、网络维修与管理等因素,因此网络拓扑生存性是广义的拓扑层可靠性。
2 基于连通的通信网络拓扑可靠性测度
通信网络拓扑可靠性问题可抽象为图的可靠性问题,用图G(V,E)来描述拓扑结构。其中,V表示网络中节点的集合,例如用户终端、服务端、路由服务器等;E表示连接网络中节点的边(链路)集合。同时,本节主要讨论拓扑可靠性的非概率(静态)测度,即不考虑上层业务或下层设备影响,将问题视角完全限定在拓扑层面。
目前,关于拓扑可靠性的静态测度研究很多,可谓仁者见仁,测度设计的侧重点各不相同。例如:连通度(vertex connectivity)、坚韧度(toughness)、完整度(integrity)、粘连度(tenacity)、离散数(scattering number)、膨胀系数(expansion coefficient)等。其中,连通度是拓扑的基础指标,后续的测度均建立在对连通性的充分考虑的基础之上。因此,本节以连通度为重点展开讨论。
2.1 边连通度与节点连通度的定义
(1)边连通度。
记为L(G),其大小等于使网络成为不连通图所需去掉链路(边)的最少条数。它反映网络节点间的内聚程度,是网络可靠性的一个基本度量指标。例如:通过分析可知,所示的网络分割至少需要移除3条边,即边连通度L(G)=3。
(2)节点连通度。
也成为点连通度,记为K(G),其大小等于使网络成为不连通图所需去掉的节点的最少个数。同理,网络的连通度K(G)=2。从某种意义上讲,点连通度是比边连通度更重要的网络可靠性度量指标,这是因为在网络中去掉某个节点就意味着与之关联的所有链路将失去意义。
2.2 边连通度与节点连通度的算法
(1)算法的基本思想。
通常,要求给定网络G=(V,E)的边连通度,需要首先确定任意不同两点的链路割集。设vi和vj是的两个不同节点,所谓G的一个vi-vj链路割集是指这样的链路集合:若去掉其中所有链路,网络G将被分割成两个分支,一个包含节点vi;另一个包含节点vj。假设Lij是G中所有vi-vj链路割集中链路的最小数,则Lij就是切断vi和vj之间所有路由所需从G中删去的最小链路数,故网络G的边连通度L(G)可按(1)式计算:
与确定边连通度的方法类似,求给定网络G=(V,E)的节点连通度,则需要首先确定任两个不同节点间的节点割集。设vi和vj是的两个不同节点,G的一个vi-vj节点割集是指这样的一个节点集合:若去掉其中所有节点,网络G将被分割成分别包含节点vi和节点vj的两个分支。假设Kij是G中所有vi-vj节点割集中节点的最小数,则网络G的节点连通度K(G)可按(2)式计算:
(2)算法的基本步骤。
由图论中的Menger定理知,分离任意两点的最小链路数等于最小割的容量(每条弧的容量为1)。因此,通过改进网络最大流算法可以计算出分离任意两点的最小链路数。下文先给出计算分离网络任意两点的最小链路数的标号算法,然后给出计算网络边连通度和节点连通度的一般步骤。
1)计算任意两点的最小链路数的标号算法。
在网络G=(V,A,C)中,设容量集C中任一弧的容量cij均为1,vs和vt分别是G的发点和收点,Lst是切断vs与vt的最小链路割集的链路数(最小割量)。对网络最大流标号算法稍做改进,可得如下求Lst的标、号算法,标号过程:
①对所有(vi,vj),令fij=0。
②给发点vs以标号(o,∞)。
③选择一个已标号但未检查的顶点vi,对于vi的所有未给标号的邻接点vj按下列规则处理:(a)对边(vi,vj)∈E,若fij=0,则给vj标号;(b)对边(vj,vi)∈E,且fji=1,则给vj标号(vi,-)。
④重复③直到收点vt被标号或不再有顶点可标号时为止。
如若vt得到标号,则说明存在一条可增广链,转(第2步)调整过程。若vt未获得标号,标号过程已无法进行时,则算法结束,此时已得到分离vs和vt的最小链路割集的链路数Lst,其值为:
2)网络边连通度计算步骤。
由前所述,计算网络边连通度的算法思路是:先按标号算法求分离任两点的最小链路数,然后,再求所有这些数的最小数即可。但是,上述求Lst的算法是针对有向图给出的,而网络边连通度是针对无向图的,因此,算法需首先将原无向网络转换成等效的有向网络。具体计算步骤如下:
第1步:对给定网络G=(V,E),任选一对节点vs和vt,按下面的步骤求分离vs和vt的最小链路数Lst:
①首先将G=(V,E)转换成有向图G'=(V,A)。方法是:将链路集E中以vs为端点的链路转换成A中以vs为起点的到相应节点的有向链路,将E中以vt为端点的链路转换成A中从相应节点到节点s的有向链路,又将E中其他链路(vi,vj)v转换成A中2条有向链路(vi,vj)和(vj,vi)。
②用标号算法,求G'=(V,A)中分离vs与vt的最小链路数Lst。
第2步:对所有节点对(vi,vj),i
3)网络节点连通度计算步骤。
算法的思路是:将割点问题转换成割边问题,从而使求网络节点连通度的问题转换成求网络的边连通度问题。转换的方法是:在网络G=(V,E)中任选一对节点vs和vt,首先,类似于边连通度算法一样,将G=(V,E)转换成有向网络G'=(V,A),然后,再将G'=(V,A)构造另一个有向图,构图规则是:将V中除vs和vt外的每个节点vi拆成2个新的中的节点和,并用中的有向链路()将它们连接起来。将A中每一链路(vj,vi)换成中的链路(),并把vs标为,vt标为。
由构图规则可知,在新的网络中,从发点到收点的包含节点vi的一条路由,必定包含一个顶点拆成的两部分之间的那条弧。并且原图G的一对相邻点及其间的边(vi,vj)被转换成等效的由4个节点组成的“8”字形有向回路{}。因此,一个链路割集在切断中到的所有有向路由方面,与在原始无向图G中去掉vs-vt节点割集有相同作用,即G中Kst等于中。综上,可得网络节点连通度算法计算步骤如下。
第1步:对原网络G=(V,E)的任一节点对vs和vt,按上述规则构造新的有向网络,并用标号法求中分离和的最小链路数,即G中分离vs和vt的最小割点集点数Kst。
第2步:对所有节点i
3 结论
本文讨论了通信网络可靠性的层次划分与影响因素,针对性的分析了拓扑层可靠性的指标与测度,指出了“连通度”作为拓扑层可靠性基础测度,以及其对其它测度设计的重要性。同时,详细分析了节点连通度与边连通度的计算思想与算法步骤。最后,通过一个相对简单的算例演示了通过边与节点连通度计算来评价某一通信网络拓扑可靠性的主要流程。
摘要：梳理讨论了目前通信网络可靠性研究之间的层次关系,讨论了拓扑可靠性所处的地位、任务、指标等。其次,分析了拓扑可靠性的非概率测度,指出了连通度的核心作用。再次,研究了基于边连通度与节点连通度进行可靠性评价的思想与算法。最后,通过一个算例展示了通信网络拓扑可靠性评价的具体过程。
关键词：通信网路,可靠性,层次,测度
参考文献
[1]罗鹏程,金光,周经伦.通信网可靠性研究综述[J].小型微型计算机系统,2000,21(10):1073-1077.
[2]陈建国.通信网络拓扑抗毁性评估算法研究[J].通信系统与网络技术,2006,32(1):6-7.
[3]饶育萍,林竞羽,周东方.网络抗毁度和节点重要性评价方法[J].计算机工程,2009,35(6):14-16.
拓扑层次 篇2
无线传感器网络集成了传感器技术、嵌入式系统技术、微机电系统技术、分布式信息处理技术以及无线通信技术,有着不可估量的应用前景。无线传感器网络采用的传感器体积小、能量少、节点部署环境较差[1]。对于能量受限的无线传感器网络来说,在确保网络应用的前提下节约能量消耗是一个关键问题。通过拓扑控制技术生成优化的拓扑结构可以实现节约能源消耗。
1 LEACH算法的特点
LEACH算法自适应性好,容错性高,并且能够有效的延长网络的寿命[2]。但是这种算法也存在着自身的缺点:
(1)簇首节点分布不合理。由于簇首产生的随机性会导致整个网络分簇不均匀,致使部分簇首相距基站远近不一,从加重某些簇首节点的负担,降低网络负载平衡度。
(2)簇内节点分布不均匀。因为是随机性的产生簇首,所以就可能造成簇首负担的节点不均衡,网络拓扑结构分布不均匀使得簇首节点消耗能耗不一,造成网络能量负载不平衡,减少了网络生存时间。
(3)簇首选举中没有考虑节点的剩余能量,剩余能量少的节点一旦当选为簇首,会导致该簇失效,甚至网络瘫痪。
(4)簇内节点Hj直接把数据传输给簇首节点CHi,当两者之间的距离较远时,会加重簇内节点的能源消耗以及簇首节点的能源消耗。
2 系统模型
本文采用文献[3]中的无线通信能量消耗模型,节点发送l bit的数据所消耗的能量为ETx(l,d),由发射电路损耗和功率放大损耗两部分组成,即公式(1)所示:
Eelec表示发射电路和接收电路损耗的能量消耗,在该模型中两者取相同值,能量消耗值与消息长度l成正比。功率放大时的能量消耗与发射节点和接收节点之间的传输距离d有关。根据传输距离d与给定阈值d0之间的关系,发送节点选择不同的能量衰减模型计算发送数据所消耗的能量,即当传输距离小于d0时,采用自由空间模型,发送数据的能量消耗与距离的平方成正比关系;否则采用多路径衰减模型,与距离的四次方成正比关系,如公式(2)所示:
其中εfriss-amp、εtwo-ray-amp分别表示这两种模型功率放大所消耗的能量,d0=4πhrht/λ,ht和hr分别表示发射装置和接收装置的天线长度,λ表示标志信号波长。
接收装置每接收l bit数据的能量消耗为:
3 LEACH-EAM算法的实现
LEACH-EAM算法采用LEACH算法中轮次转换的方法,把每轮循环分为簇的建立阶段和稳定的数据通信阶段,如图1所示。
3.1 簇的建立阶段簇的建立阶段由簇首确定和簇的形成两个阶段组成。
3.1.1 簇首确定
在簇首选举上,算法采用基于节点密度争先的簇首选举以及允许已经充当过簇首的节点继续参加选举的方法。同时,引入节点当选簇首次数限制F(i)和能量限制Et(i)两个指标,避免节点频繁当选簇首或者剩余能量少节点当选簇首,造成节点加快死忙的问题。
簇首选举时节点生成介于0-1的随机数a,用a与簇首选举阀值T(Ni)进行比较(T(Ni)由公式(4)定义),a比T(Ni)小就具备当选簇首的先决条件。
在公式中:P是一个0-1间的实数,为网络中每轮节点成为簇首占所有节点的比例;r是当前轮数;G是在前r-1轮内未死忙节点集合,D(Ni)是节点密集度参数(由公式(5)定义)。
Nd(i)为节点i的存活邻居节点数。
公式(5)由LEACH算法公式修改而来,它与LEACH算法不同的是:(1)LEACH算法中禁止当选过簇首的节点再次参选,会从另一方面造成簇首节点分布在网络边缘,网络分簇不均匀,所以本算法的簇首选举阀值把限制当选过簇首的限制条件去掉,允许节点多次单选簇首;(2)增加密度集参数,由1-D2(Ni)可以看出,随着节点周围存活的节点数越多,1-D2(Ni)的值也就越大,节点当选簇首的概率也就会越高,节点周围存活的节点数越少,节点当选簇首的概率也就会越低。而且每个节点密度集也会随着时间的变化而发生改变。
算法在簇首选举的过程中还要衡量节点当选簇首次数限制F(i)和能量限制Et(i)两个指标,定义以下变量C(i),ei,Eavr。C(i)是节点在生命期内中当选簇首节点的统计次数,由节点通过累加得到,ei为节点剩余能量,由节点自己能量消耗情况得出,Eavr为全网存活节点的平均剩余能量,由Sink节点返回得出。其中
RMAX为系统设定的最大选举轮数,参数P为系统设定的最优簇首比例。节点只有在指标F(i),Et(i)都比实数1小的时候才具备当选簇首的前提条件。通过指标F(i)可以保证节点当选簇首的次数控制在一定的范围内,避免节点过早死忙。通过能量限制Et(i)保证当选簇首的节点剩余能量必须比全网存活节点的剩余能量大,避免剩余能量较少的节点担任簇首。
在簇首选举的过程中从节点密度集、节点当选簇首次数限制和能量限制等三个方面对LEACH算法进行改进,簇首的选举不再是单个节点的事情,而是周围节点的联合考虑。簇首选举流程图如图2所示。
3.1.2 簇的形成
一个节点成为候选簇首节点后,就向其邻居R范围内广播成为获胜簇首的消息,该消息包括节点的ID,剩余能量ei和坐标,等待节点的加入。非候选簇首节点收到簇首的广播消息后,则计算与每个候选簇首之间能量距离综合权值参数wji(wji由公式(8)给出),选择wji值大的簇首加入,如果存在与多个候选簇首节点的wji值相等,则选择距离短的簇首加入,并向该簇首发回确认消息,确认消息包含节点的ID,剩余能量ei和坐标[4]。
其中ej为非簇首节点的剩余能量,d(j,i)为非簇首节点Hj与簇首CHi之间的距离。
节点在簇首选举时间内如果没有收到来自候选簇首的消息,则该节点宣布成为簇首,并向其邻居R范围内广播当选簇首的消息,该消息包括节点的ID,剩余能量ei和自身的地理位置,等待节点的加入,只有与该节点相同的没有收到获胜簇首消息的节点才需要对这条消息响应,通过前面的能量距离综合权值参数wji方法选出剩余的簇首。
3.2 稳定的数据通信阶段
LEACH-EAM算法在稳定的数据通信阶段簇内数据传输采用多跳和单跳结合的方法。LEACH-EAM需要根据当前条件是否满足临界条件来决定簇内节点进行多跳或者多跳的数据传输。
3.2.1 临界条件
临界条件的确定参考文献[5]得出,在文献中通过参数Qcluster(公式(9))确定临界条件。
Qcluster为每个簇平均所占的面积。簇所覆盖面积大小决定了该分簇是采用多跳或者单跳的传输方式。当簇所占的面积满足大于Qcluster时,采用多跳的传输方式,反之则采用单跳。
3.2.2 多跳的实现方法
在实现多跳的数据传输过程中,簇首CHi先根据簇内成员节点的位置信息,采用最短路径算法Dijkstra计算连接边的权重意义上的最短路径得到CHi出发到所有簇内节点的路由路径树。根据公式(2)可计算连接边的权重Eelec+εfriss-ampd2,因为簇结构中传输距离较短的特性,所以衰减因子选择2。当最短路径计算完毕后,簇首CHi将路径树打包成消息广播给簇内节点[5]。簇内节点Hj接收到路径消息后,可从消息中得出自己的上一跳集合和下一跳集合。
4 算法仿真
4.1 仿真系统配置
仿真系统配置如下:传感器网络布置区域为100m×100m,随机分布的节点数为100个,基站位置固定在坐标(50,50)处,节点的传输距离为10m—50m,节点初始能量为2J,节点接收和发送电路消耗的能量Eelec为50Nj/bit,信号放大器的放大倍数为0.0013pJ/bit/m4,增量Δ为2,EDA为0.009J/bit/signal,节点充当簇首时间为100s[6]。
4.2 性能分析
为了评价算法对网络性能的影响,为了更好地衡量网络寿命、能量利用率和簇规模等几个指标,本仿真实验中测定了四个指标,分别为:簇规模、网络寿命、簇内节点分布、平均功耗。
4.2.1 簇规模
簇规模指标用来评价各簇节点数的平衡度。为比较LEACH-EAM算法在平衡各簇规模的作用,随机抽取了算法在运行过程中的分簇,如图3所示。可以看出LEACH-EAM结合节点剩余能量和节点密度选择簇首,相比LEACH算法和DBPC算法簇首节点分布比较均匀,而且都分别位于各簇的中央地带,较好地避免了簇首节点聚集或处于网络边缘的问题。
4.2.2 不同簇首比例网络寿命
图4为簇首比例P分别取0.04、0.05、0.1时,四种算法对网络寿命的影响。可以看出在3种不同簇首比例P下,因为LEACH—EAM算法在簇首选举阶段引入能量限制指标,避免剩余能量少节点当选簇首,在簇的形成阶段,非簇首节点计算与每个候选簇首之间能量、距离综合权值,并加入选择综合权值大的簇,簇内节点采用多跳与单跳相结合的方式进行数据传输,所以网络寿命最长,OBCP次之,LEACH的网络寿命最短。而且当P=0.04时,LEACH-EAM的网络存活时间最长。
4.2.3 簇内节点分布
簇内节点分布性能指标反映网络分簇情况是否均衡。如图5所示,可以看出LEACH-EAM各簇包含的节点数相对于LEACH、DBCP更加集中,从而进一步证明通过结合节点密度选举簇首可以更有效平衡各个簇的规模。
4.2.4 不同网络直径下的网络寿命、节点平均功耗
图6和图7分别表示在不同网络直径下的网络寿命和节点平均功耗的对比情况。从图中可以看出,随着网络直径的增加,簇内通信距离增大,造成簇内消耗的能量也增大,LEACH-EAM相对LEACH算法、DBCP算法节点平均功耗是最少,网络寿命最长。
5 结束语
本文LEACH算法进行深入研究,提出了LEACH-E-MA算法。通过簇首的确定、簇的形成两个阶段,簇内数据传输方式实现了改进算法,具备网络分簇情况均衡,节点的平均功耗少;网络的生存时间长的特点。
摘要：拓扑控制是无线传感器网络技术中的一个重要研究方向,良好的拓扑控制机制能够提高路由协议和MAC协议的效率,为数据融合、时间同步和目标定位等很多方面提供基础。本文在提出一种基于能量有效和多跳的层次型拓扑控制算法。算法在簇首选择阶段综合考虑节点剩余能量、节点密度、节点间距离,在非簇首节点加入簇阶段综合考虑节点间剩余能量及距离,数据传输阶段根据临界条件来决定簇内数据传输采用多跳或者单跳的数据传输的机制。通过仿真软件验证发现算法使得网络分簇情况更加均衡,节点的平均功耗更少,更合理,网络的生存时间更长。
关键词：能量有效,多跳,无线传感器网络,拓扑控制,仿真
参考文献
[1]孙利民,李建中,陈渝等.无线传感器[C].网络清华大学出版社,2005.5,89.107.
[2]乔俊峰,刘三阳,曹祥宇.无线传感器网络中基于节点密度的簇算法[J].计算机科学,2009,36(12):46-49.
[3]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless micro-sensor networks[C].Proceedings of t he33rd Annual Hawaii International Confer-ence on System Sciences,Maui,2007.3005-30l4.
[4]郝晓辰,翟明,刘彬,张增仁.负载均衡的无线传感器网络拓扑控制算法[J].计算机工程,2009,35(05):84-86.
[5]汤强.无线传感器网络层次拓扑控制算法研究.华中科技大学博士学位论文.2010.6.1.
拓扑层次 篇3
无线传感器网络是一种由大量微型移动传感器节点构成的网络, 能够协作地实施监测、感知和采集环境信息, 并对数据进行处理, 传送到监控中心, 可应用于布线和电源供给困难的区域、人员不能到达的区域和一些临时场合等。将无线传感器网络应用于井下的监测监控不仅可以与现有的工业以太网相互补充, 实现井下安全监测的无缝覆盖, 还可以跟随采掘面同步延伸, 减少了布线难度, 降低了成本, 提高数据的安全性和稳定性。
1 井下无线传感器网络结构的总体设计
近年来, 基于工业以太网的矿井综合监控系统已在煤矿获得广泛应用。在煤矿井下构建无线传感器网络并不是要替代原有的工业以太网络, 而是要形成工业以太网+无线传感器网络的混合控制的网络结构[2]。
根据煤矿的实际情况, 可以将煤矿分为开采区和巷道区, 巷道区又可以分为主巷道和支巷道。在各个主巷道区域, 地形比较开阔, 方便布线, 可以架设有线光纤骨干网, 采用有线监控分站的模式, 智能传感器将采集到的信息通过有线的方式接入光纤骨干网。在地形相对狭窄的支巷道和人员不易或不能到达的区域, 如采空区、井筒内、事故发生现场等, 构建无线传感器网络。利用无线传感器网络的自组织、多跳路由、动态拓扑等特点, 实现井下监测监控的无缝覆盖, 见图1。
无线传感器网络与光纤骨干网通过嵌入式综合接入网关 (Sink) 实现互联。光纤骨干网将无线传感器网络和有线传感器网络采集到的信息发送到地面监控中心, 地面监控中心根据收集到的信息对矿山生产进行实时监控, 随时注意矿井中各地段、区域的参数目标的变化情况, 对突发情况作出迅速的应急反应, 根据准确的定位技术, 向危险区域发出预警信号, 扼制超定员生产等。
2 井下无线传感器网络的拓扑控制
2.1 节点分类
无线传感器网络节点作为一种微型化的嵌入式系统, 构成了无线传感器网络的基础层支撑平台。由于煤矿井下环境恶劣, 要求井下所有传感器节点的设计都应满足本质安全特性。根据节点是否经常移动, 将传感器节点分为固定节点和移动节点。固定节点可以根据巷道的实际布局和需要以及监测工作面的变化进行部署, 并可根据监测面的实际情况随时进行增减, 用于采集巷道的瓦斯浓度, 转发处理其它节点的通信数据, 保持无线链路的畅通和传感器网络的健壮性, 因此在功耗和稳定性上着重考虑其稳定性。移动节点包括矿工随机携带的传感器、移动设备附带的传感器以及能够移动的救援机器人等。这些节点可由矿灯供电, 或者人为更换电源, 要求体积小、功耗小、集成度高。为了实现井下精确定位和有效监控, 要求所有节点都拥有能够确定身份的唯一的ID号码。
2.2 井下无线传感器网络的拓扑结构
煤矿井下需部署的网络规模较大, 拓扑动态变化, 因此必须采用聚类分层的网络结构, 如图2所示。网关节点一方面在逻辑上是以太网的1个节点, 与远程服务器进行通信, 接收以太网的数据包并予以处理;另一方面作为无线传感器网中最大的汇聚点 (一级簇首) , 完成对数据的解析、处理和转发, 从而实现与骨干网的互联。为了保证网内能耗均匀分布, 可根据实际情况设置多个网关节点[2]。
将传感器节点按照地理位置或节点的密集程度划分为多个簇群, 每个簇群由1个簇首和多个簇成员组成, 低一级网络的簇首是高一级网络中的簇内成员。簇首节点除负责完成数据转发外, 还需要完成数据融合和路由的选择, 以及网络中节点与簇的所属关系, 任务相对较重;簇内普通节点的功能比较简单, 负责收集数据, 与簇首节点通信。
设计对环境进行监测的无线传感器网络, 节点之间的通信和传感数据本身并不是非常重要, 而对数据进行分析, 使终端用户可以获取被监视环境的相关事件并通过一定的算法对环境变化进行预测才是最重要的[3]。因此对于这种拓扑结构, 簇首的选取至关重要。簇首一旦出现故障, 将直接导致该簇无法工作, 这在安全要求高的采掘现场是绝对不允许的。因此针对矿井实际生产情况, 大部分节点是静止的或安装在矿车设备上相对位移较小, 可按一定的间距在支巷道壁上或巷道拐弯处预先设置二级簇首, 由二级簇首负责与网关节点的通信, 位置固定的节点一般为二级簇首的簇成员。由于二级簇首节点任务较重, 能耗较高, 因此可以在重要的簇内增加冗余簇首节点。冗余簇首节点与簇首节点的特性相同, 作为特殊的簇内节点加入簇。该节点采用一定的无线网卡动态关闭机制, 即绝大部分时间处于休眠状态以节省能源。当簇首节点无法继续工作时, 该节点被激活并取代原先的簇首节点担当簇首对该簇进行维持, 并向网络发出报警信息, 通知监控端尽快更换该簇首节点, 并加入新的冗余簇首节点以解决工业现场对稳定性和安全性的要求[4]。另外位置固定的簇首节点也可作为锚节点使用, 完成网络未知节点的测量和定位。
三级簇首为移动节点。在矿井下, 移动节点多为矿井工作人员, 他们的位置是随机移动的, 而且通常会聚集在一起出入。在人员密集的地方如采掘工作面, 如果许多移动节点同时向二级簇首传输信息, 很容易造成冲突, 浪费能量。因此有必要在移动节点中选取1个簇首节点作为三级簇首, 负责为本簇内的移动节点分配时隙, 完成与二级簇首的通信。三级簇首节点可综合考虑节点剩余能量和与簇成员相对移动距离等因素动态选取[5,6]。
2.3 拓扑形成
采用固定簇首节点的策略, 首先人工配置好网关和具有固定位置的二级簇首节点和冗余簇首节点。所有具有固定位置的簇首节点具有相应的位置编码并在网关节点处记录。在传感器网络形成初始阶段, 事先已经确定好的二级簇首节点向周围广播自己的信息, 网络中其他的固定节点可根据接收信号的信噪比确定自己的簇首节点, 并申请加入该簇, 由簇首节点为其分配相应的工作时隙、休眠时间和扩频码。同时网关节点也接收到附近二级簇首节点发过来的广播信号, 并与能接收到信号的簇首建立通信路由。无法与网关节点直接建立通信路由的簇首节点可通过分析其他簇首节点发过来的广播信号, 选择合适的簇首作为自己的路由节点, 通过路由节点将本簇内的信息传送到网关节点。每个普通的节点1次只能选择1个二级簇首节点进行通信, 一旦选择好簇首节点后, 不再接收其他簇首节点的广播通告。普通节点之间不能互相通信, 只能与对应的簇首节点进行通信[7]。
移动节点在进入网关之前已经自动组成簇群。通常二级簇首周期性地转发数据, 不通信时处于休眠状态节约能量。一旦有移动的簇群进入控制区域, 由三级簇首负责唤醒二级簇首进行登记和注册。当二级簇首监测到三级簇首在规定的时间内没有与二级簇首联系时, 便认为移动簇群已经离开, 从自己的链接表删除即可。
2.4 移动节点的组簇及合并
这里默认每次下井时, 移动节点的能量都是一样的 (即要求每次下井前矿工的矿灯都充满电) 。移动节点的ID号根据矿工的工种和职务进行设置, 职务越高ID号越低, 首次组簇时默认ID号最低的为簇首, 工种一致的节点具有组成1个簇群的优先级, 每个簇群不超过25个移动节点。单个节点自己成簇, 自己即是簇首。当三级簇首的能量下降到自己担当簇首时能量的70%时, 可在簇群中挑选新的簇首, 挑选的依据是节点的剩余能量和ID号。新的簇首指定后, 旧簇首退出簇首状态, 成为普通节点, 由新的簇首发布广播消息, 通知簇群内节点和二级簇首。
因为节点是随机移动的, 因此在移动的过程中会出现一些节点离开簇群或有新的节点加入簇群;另外, 如果二级簇首监测到2个三级簇首位置接近, 可通知ID号低的簇首进行合并。合并流程如图3所示。这样离开簇群的个别节点也可以首先单独组簇, 然后再进行簇群合并, 从而简化通信协议。
3 结语
将无线传感器网络应用于矿井的安全监测监控, 有利于煤矿的安全生产和抢险救灾, 有着广阔的应用前景。针对煤矿井下的特殊的生产环境, 设计出工业以太网与无线传感器网络相结合的4层分簇链状网络拓扑结构, 为进一步的数据融合、人员定位和时间同步提供依据。
摘要：根据煤矿井下巷道的实际分布情况和井下矿工随机移动的工作特点, 提出一种与工业以太网相结合的4层分簇链状无线传感器网络拓扑结构, 具有较好的扩展性和可靠性。介绍了无线网络拓扑的形成以及移动节点的自动组簇、簇首的选择算法和簇群的合并算法, 为煤矿的安全监测和进一步的数据融合、人员定位提供依据。
关键词：煤矿,无线传感器网络,拓扑结构,移动节点
参考文献
[1]湛浩晏, 孙长嵩, 吴珊, 等.ZigBee技术在煤矿井下救援系统中的应用[J].计算机工程与应用, 2006, 42 (24) :181-183.
[2]江海峰, 甄阳清, 傅毅.矿井无线传感器网络的网关设计[J].计算机工程, 2009, 35 (3) :112-114.
[3]童敏明, 谢金成, 戴新联, 等.煤矿监测系统无线传感器网络的设计[J].煤矿安全, 2007, 38 (1) :5-8.
[4]胡海江, 张凤登.一种新的无线传感器网络分簇模型[J].传感技术学报, 2006, 19 (2) :477-480.
[5]Chatterjee, M., Das, S., &Turgut, D.WCA:A WeightedClustering Algorithm for Mobile Ad Hoc Networks.ClusterComputing 5, 2002:193-204.
[6]C.R Lin, MGerla.Adaptive Clustering for Mobile WirelessNetworks.IEEE J.on Selected Areas in Communications, 15, 7, 1997:1265-1275.
[7]黄瀛.基于无线传感器网络的煤矿安全无线与综合监控系统的研究[D].北京:北京交通大学, 2007.