移动自组网络中的层次结构

移动自组网络中的层次结构

1建立新型网络模型移动集群网络（移动应用商店网络，简称manet）是一种不依赖固定基础设施的新型无线网络。与需要中心控制设备(如基站或访问服务点)的蜂窝移动通信网络和无线局域网相比,移动自组网络具有自组性、多跳性、无基础设施要求及易铺设等特点,可广泛用于军事战场信息系统建设、民用紧急救助以及其他需要临时建立网络的场合,如野外活动、体育竞赛、会议展览等。移动自组网络最初的结构是平面式的,即所有节点都是对等的,都肩负着终端与路由器两项功能,只有性能上的差异,没有功能上的不同。这种平面式结构的最大优点之一是,源节点与目的节点之间存在多条路径,因而可以通过多条传送业务流,减少拥塞,并消除可能的瓶颈问题。但是,由于移动自组网具有动态的拓扑(节点可能会引入或退出网络)、有限的带宽及采用电池供电等诸多特性,这种平面式结构在节点数目增多时的路由开销很大,因此可扩展性较差。解决这个问题的最主要方法就是采用适当的分簇算法构造分层的拓扑。相互邻近的一组节点构成一个簇,簇内的成员可分簇首、簇成员、网关三种。簇成员之间的通信通过簇首进行,簇之间的通信则经过网关转发。在移动自组网络中,基于簇的层次结构能够优化网络带宽的应用,提高共享信道的利用率,减少路由维护的代价以及提高应用的可扩展性,在路由、安全、网络管理及服务发现等方面具有重要的应用。2集群算法的测量标准和工具2.1多节点获得结构稳定性的标准化标准目前,衡量一个分簇算法的优劣主要有以下几个标准:簇结构的稳定性、簇首节点的数量、负载均衡度(LoadBalancingFactor)及节电能力等。(1)簇结构稳定性控制由于移动自组网节点的动态特性,簇结构经常会因节点的加入/离开、不同簇首相遇时的竞争而发生变化。一个相对稳定的簇结构能够有效地降低由于簇的重构而带来的通信与电能开销,因而维持簇结构的稳定具有重要的意义。簇结构的稳定性用节点状态(一般说来,节点状态有簇首、簇成员与未决(Undecided)三种)变化频率以及簇首节点变化频率度量,分别定义为单位时间内节点状态变化次数、簇首节点变化次数。变化次数越小,则簇的稳定性就越高。(2)高链路的利用率在链路容量许可的情况下,簇首节点数目少的算法能有效地提高链路的利用率。但是,由于节点资源限制,簇首不可能服务所有邻居节点,即簇成员的数量应有一定的限制,如蓝牙协议,其主从结构限制了每个主节点只能同时服务七个成员节点。(3)节点系统的动态均衡簇首的负载大小取决于其所支持的节点的多少。维护簇结构与簇间路由均需要消耗簇首一定的资源,因此不希望出现有的簇首过载、有的簇首却很轻闲的状况。但是,由于节点经常性地加入/离开,很难使系统一直维持在良好的负载均衡状态。为了量化簇首负载的均衡程度,文献提出了负载均衡度的概念:LBF=nc∑i(xi−u)2LBF=nc∑i(xi-u)2其中,xi为簇首节点i的成员节点数,u为簇首的平均邻居节点数量,u=(N-nc)/nc,N为网络中的节点数,nc为簇首节点的数量。该值越大,则表示负载均衡度越好。2.2glomosim、opnet与q智能化目前,用于分簇算法模拟的主要有以下这几种模拟器:ns-2、GlomoSim、OPNET和Qualnet。其中,ns-2与GlomoSim属免费软件,代码公开,对于有线以及无线网络上的TCP、路由、组播协议等能够提供有力的支持,因而在科学研究中得到广泛的应用。OPNET和Qualnet属商用软件,更适于开发实际的工程项目,但需付费使用。Qualnet中的一些模型甚至要求提供相关的(美)军方许可才可以使用。3添加适当控制信息现有分簇算法在分簇过程中大多显式地使用控制信息,即各节点通过周期性地交换控制信息来选择簇首,但也有些算法隐含地使用控制信息,即在正常的数据包中嵌入适当的控制信息。按照控制信息的使用方式,可将分簇算法分为主动分簇算法和被动分簇算法两类。3.1主动分簇算法所有主动分簇算法的共同特征是需要通过周期性地交换控制信息来选择簇首。按照选择簇首的标准,主动分簇算法又可分为最小ID或最大连接度相关算法、最小ID或最大连接度无关算法以及其它算法等三类。需要说明的是,这里的分类只是为了叙述方便,并无统一的标准。3.1.1基于最大连接度的最小id算法最小ID算法与最大连接度算法是最早提出的分簇算法。在最小ID算法中,每个节点拥有一个全网范围内唯一的标识(ID),并周期性地向其邻居节点(在其接收范围内的节点)广播其ID值。这样,每个节点就可以将自己的ID值与其直接邻居节点进行比较,如果发现自己为ID值最小的节点,则自动成为簇首节点。如果一个节点处于两个或多个簇首的发送范围之内,则称为网关节点。网关节点通常用于簇间的路由。最大连接度算法选择簇首的标准是连接度,也就是一个节点的直接邻居个数。与最小ID算法一样,每个节点周期性地向其直接邻居节点广播自己的连接度。这样,每个节点就可以将自己的连接度与直接邻居节点相互比较,如果发现自己的连接度最大,则自动成为簇首节点,其邻居节点成为簇成员节点。最小ID算法的主要优点是简单,主要缺点是ID较小的节点成为簇首的可能性要远高于其他节点。因此,算法在能源有限的移动自组网络中缺乏公平性。最大连接度算法的簇首数目较少,但算法对簇内节点数目没有限制,因而无法适用于某些对节点能力有限制的网络(如蓝牙协议,其主从结构限制了每个主节点最多只能同时服务七个成员节点)。对于其它没有节点限制的协议也有问题,当节点数目增多时,节点的吞吐量会降低。此外,对于环状拓扑,每个节点的度数均为2,还需要增加额外的规则保证算法的正确性。尽管这两种算法存在很多不足,它们仍然是后续各种分簇算法进行性能比较的对象。由于最小ID算法与最大连接度算法存在诸多不足,于是很快又出现了不少基于这两种算法的改进算法。LinandGerla提出了一种改进的最小ID算法,其簇生成过程与最小ID法完全相同,但在簇结构发生变化时,不再按照最小ID选择新簇首,而是将连接度最大的节点及其邻居仍留在原始簇中。基于权值的算法(DCA算法、WCA算法)也可看成是最小ID法的扩展。这种算法假设每个节点具有唯一的权值,选择邻居节点中权值最大的节点作为簇首节点。权值与节点连接度、标识等因素紧密相关(WCA算法还考虑了节点的移动速度、能耗以及簇成员限制等因素),虽然簇结构的稳定性有所提高,但每种因素在权值中所占的比重不确定,并且权值的计算和存储需要一定的代价。3.1.2基于稳定链路的分簇算法由于度量分簇算法的首要标准是簇结构的稳定性,而最小ID或最大连接度与簇结构的稳定性并无直接关系,因此一些分簇算法跳出了最小ID与最大连接度的圈囿,采用了完全不同的簇首选择标准。其中,最有代表性、同时也颇具发展前景的主要有:基于位置预测的算法、基于节点移动性的算法和基于链路稳定性的算法等。文献提出了一个基于移动位置预测的分簇算法-(pik,tik,dik)算法。该算法将一个MANET网络覆盖的地理区域划分为多个静态的虚簇,并假定区域中每个移动节点知道虚簇中心(VCC)的位置信息。虚簇可以包含一个实簇,也可以不包括。(pik,tik,dik)簇算法按照以下原则选择簇首:与同一个虚簇内的其它节点相比,节点移出当前所在虚簇的概率最小;节点与当前虚簇中心的距离最短。前一个条件是为了排除移动性强的节点作为簇首的可能,后一个条件是为了保证簇首改变时,簇覆盖的区域不会有大的变化。这里,pik表示第k个虚簇中的节点i,在距虚簇中心的距离为dik、停留时间为tik时的概率。如果k号虚簇中的节点i在tik≥tc(tc为与系统相关的一个常量)时满足pik=pmax,则该节点成为该虚簇的簇首节点。由于移动是引起簇首与簇成员关系变化的主要原因,因此Prithwish提出的MOBIC算法就将移动性(Mobility)作为分簇与簇首选举的一个重要因素。Prithwish依据以下假定提出了本地移动性度量标准:接收节点检测到的信号强度。通过接收到的邻居节点后续发送的包(如周期性的“Hello”报文),可获取当前节点与邻居节点间的相间移动性。初始时所有节点处于“未决”状态,每个节点周期性地在其Hello报文中广播其移动性度量值M,邻居节点接收到该值后将其存储在本地的邻居表中,并将自己的度量值与其进行比较。如果发现自己具有最小的度量值,则将状态设为簇首,否则为簇成员。如果一个节点是两个簇首的邻居,则该节点成为网关节点。文献提出了一种基于稳定链路的分簇算法。该算法用CSm,n-avg(SS)表示从节点m到n的平均信号强度,并使用自由空间传播模型(Freespacepropagationmodel)来预测接收到的信号强度(按以下Friis自由空间方程计算):Pr(d)=(PtGtG2r)/[(4π)2d2L]Ρr(d)=(ΡtGtGr2)/[(4π)2d2L]式中,Pr(d)是接收方功率;Gr是接收方天线增益;Pt是发送功率;Gt是发送方天线增益;L是系统损耗率;d是发送方到接收方的距离。该算法使用模糊理论将信号强度正规化为弱、中、强三个等级,尽可能地选取具有稳定链路的节点作为簇首。3.1.3基于模糊规则的分簇算法还有一些算法与上述两类算法有显著的区别。一是基于模糊规则的算法。该算法选择簇首的标准已经不是一个,而是多个,并且是开放的,可以任意增加所需要的标准。WCA算法也考虑了多个簇首选择标准,但将所有标准综合成一个权值,尽管基于模糊规则的算法显得更合理,但由于考虑的因素很多,无论是通信开销还是本地计算开销都高于一般的分簇算法。另一种比较特别的算法是k-跳分簇算法,其簇成员到簇首的距离最多为k-hop(这种簇也称k-cluster),而不是上述算法所采用的1-跳,这样就必须解决簇内通信的路由问题,而不能象其它分簇算法那样直接利用adhoc网络的广播特性。此外,还有一些针对特定网络环境的分簇算法,如针对存在单向链路的算法、针对节能要求的算法等。3.2ence:移动性信息更新的关键阶段到目前为止,大多数分簇算法都是通过模拟进行研究的,并且需要完全的邻居信息。由于移动自组网络无固定中心的特征,邻接信息只能通过交换beacon或hello信息收集。在这个“邻居学习”(Neighbor-Learning)过程中,一般都假定节点不移动。在周期性的邻居学习与分簇的初始阶段,“节点不移动”对于正确的收敛(Convergence)是很重要的。这种假定必须存在于邻接关系收集的整个阶段、分簇的初始阶段、重分簇阶段。如果发生了移动,我们可能必须在邻居学习阶段处理陈旧的邻居信息。并且,移动性导致邻接关系改变,继而可能触发整个网络的重新分簇。针对主动分簇算法存在的问题,文献提出了被动分簇的概念,不需要周期性的通信开销,也不需要节点不移动的假定。具体说来,被动分簇算法在簇的生成与维护过程中均不使用专用的控制信息,而是利用从正常数据包(如MAC帧)中获取的邻接信息,或者在数据包中嵌入适当的分簇状态信息。从数据包中获取的信息大多与基于权值的分簇算法相关。为了取得稳定的簇结构,被动分簇没有使用加权方式,而是使用了“先声明先赢”规则(FirstDeclarationWins):第一个发出数据包的节点成为簇首,并“统治”簇(簇首的邻接区域)中的其它节点。被动分簇算法的优点是不需要显式地使用控制信息,节省带宽资源,其分簇过程可以在没有收集到完整的邻居信息的情况下进行。当连接改变时,被动分簇不需要一个重构过程以满足某些分簇规则(如最小ID等)的要求。综上所述,被动分簇是一项极具发展前景的adhoc网络分层技术。4研究热点分析在移动自组网络中,基于簇的层次结构具有广泛的应用,是解决移动自组网络扩展性的最重要手段。以上我们介绍了当前典型的分簇算法的特征及其主要优缺点。从以上论述中我们可以看到:由于主动分簇算法使用显式的控制信息并能充分利用移动自组网的广播特性,因此受到广泛的研究。尽管被动分簇算法的研究相对较晚,但在某些具体的应用领域,却具有主动分簇算法难以替代的作用。由于移动自组网本身尚处在研究阶段,故有关分簇算法的研究也处在不断发展之中。未来分簇算法的研究热点应当集中在以下几个方面:(1)增加簇结构的稳定性。稳定的簇结构能够有效地增加节点收发报文的成功率,减少簇重构的几率,也有利于降低节点通信代价。(2)降低通信代价。由于移动自组网络的节点随机移动、带宽有限等特点,通信开销就成了一个不容忽视的重要因素。降低通信开销的一个重要手段是增加簇结构的稳定性,但被动分簇也许是一个更有效的手段。(3)充分结合组移动的特点。现有分簇算法大都是基于“节点运动是随机的,互不相关的”的假设设计的。但是,在真实场景中,却有大量的组移动现象,如战场上一组士兵受领任务(如排雷、捉俘)搜索指定区域,一群学生参观博物馆,多个不