移动自组织网络中基于优化分簇的混合分层路由协议

移动自组织网络中基于优化分簇的混合分层路由协议

1节点网络的稳定性能移动自组织网络是一种高度动态的多段无线网络。在这种动态的无线网络中,由于网络拓扑结构的频繁变化和带宽有限,如何建立、维护和选择路由,提高网络的连通性和效率,最大限度地利用无线资源是根本问题。随着移动自组织网络研究的不断发展,人们提出了多种解决方案,主要基于按需(on-demand)和表驱动(table-driven)2种路由策略:按需路由策略不需要周期性地广播路由信息,仅在没有去往目的节点路由时进行路由发现,但路由发现引起的延时较大,适合规模较小、节点移动性较大的网络;表驱动路由策略需要周期性地交换路由信息以主动发现路由,其周期与节点的移动速度有关,需要消耗大量的网络带宽,因此适合节点移动性较小,源—目的通信对数目较大的网络。从网络逻辑视图这个角度来看,路由协议可以分为平面协议(flatprotocol)和分层协议(hierarchicalprotocol)2种。在平面路由协议[2~4]中,所有节点都处于同一平面上、每个节点的功能也都相同、采用单一的路由策略,容易实现。但是由于移动自组织网络的动态变化性,通信中节点可能会在某些时候移动或停止工作,从而频繁地导致路由失效,通信节点重新建立路径会带来较大的网络开销或较长的延时,因此缺乏可扩展性,限制了网络规模。分层路由[5~11]避免了以上平面路由的种种问题,在较大规模移动自组织网络中已经取得了很好的效果。在分层路由协议中,网络拓扑结构的细节通过节点的层层聚合被隐藏起来。分层路由主要有2个目的:一是通过减少参与路由计算的节点数目,减小路由表尺寸,降低交换路由信息所需的通信开销;二是基于某种分簇策略,选举产生一个较为稳定的子网络,减少拓扑结构变化对路由协议带来的影响,从而提高了网络的扩展性能。CBRP等在簇与簇之间和簇内节点都采用按需策略的路由协议,由路由发现引起的延时较长,在数据流量较小时,路由发现所消耗的网络带宽较小,但是在数据流量大到一定程度(特别是进行通信的节点较多的情况)时,路由发现所消耗的网络带宽将超过表驱动路由的控制开销,严重时将导致网络瘫痪。ZRP、ZHLS、SLURP等在簇与簇之间采用按需策略而簇内节点采用表驱动策略的混合型路由协议,它们的缺点同CBRP等完全采用按需策略的路由协议相同,在数据流量较大时,路由发现所消耗的网络带宽将非常大。HSR、CGSR等在簇与簇之间和簇内节点之间都采用表驱动策略的路由协议,路由发现引起的延时非常短,但是由于簇间和簇内都需要广播路由信息,网络的控制开销过大,而且由于所有数据分组的传输都要经过簇首节点,簇首节点的负担过重,因此这类完全采用表驱动策略的分层协议只适用于节点移动速度小或者基本静止的无线网络。另外,这些典型的分层路由协议一个共同的特点就是簇的尺寸过小——簇半径只有一跳,这样会导致大规模移动自组织网络中簇的数量较多、簇维护开销较大,而且节点容易在簇间漫游,从而导致路由频繁失效。在先前工作HCR中,所有节点形成一个由较大尺寸簇组成的簇状网络,路径选择时采用了混合路由策略以取得较好的网络性能。但是HCR并没有对分簇网络的稳定性能进行分析。与已有对分簇网络性能分析的研究工作大多注重对网络的负载平衡、覆盖度、维护开销、能量高效等因素的优化分析[12~16]不同,本文分析了分簇网络中簇的尺寸与节点移动速度、网络拓扑稳定性及相应控制开销的关系:簇半径越大,簇级拓扑结构越稳定,相应的控制开销也越大。针对分簇网络的这种簇内节点移动性快而簇与簇之间移动相对较慢的特点,本文首次提出了一种有效的基于优化分簇的混合路由(HOCR,hybridoptimalclusterrouting)协议。HOCR协议的主要思想是对移动自组织网络进行分簇,使得网络中存在簇(cluster)和簇内节点(node)2个层次:在簇间路由单位是簇,由于簇在网络间的移动要远小于节点的移动,因此为了减少路由发现延时,避免网络规模较大时过多的全网路由广播,采用表驱动路由方式;而在簇内路由单位是节点,为了适应节点的快速移动,采取按需路由策略。和已有的研究工作相比,本文具有下列创新之处:1)首次对分簇网络中不同尺寸簇的拓扑稳定特性及相应开销进行了理论分析,并结合无线网络路由的特点得出了适用于分层路由协议HOCR的最佳分簇策略;2)HOCR协议在移动自组分簇网络的不同层次上根据其各自的特点采用了相应适合的路由策略,从而具有可扩展性强、健壮性好、时延小和控制信息少的特点。2网络性能分析2.1簇内广播报文在分簇的拓扑管理机制下,网络被划分为簇(cluster)。簇由一些相互邻近的节点组成,它包括一个簇首节点,其余的是成员节点。簇首节点定期地发送簇内广播报文,簇内成员节点收到广播报文后会发送给簇首节点响应报文,从而实现簇的形成和维护。假设网络节点数为N,节点密度为ρ,节点发射半径为r,簇半径为R。为了简化理论分析,本节采用了固定速率运动模型,节点的移动速度设为V。对于簇半径为k的簇而言,簇首节点到簇内任何成员节点的距离最多为k跳,即簇半径R=kr。2个簇首节点间距离为d,如果d∈(R,2R],则两簇相邻,如果d>2R,则两簇相离。2.2打造2个簇首节点间的移动距离和距离分簇网络拓扑结构的稳定性表现为由于簇不断移动导致簇相邻关系变化的频繁程度。簇的移动是由簇首节点移动造成的,簇的移动速度等于簇首节点的移动速度。可以通过分析2个簇从开始相邻到相邻关系发生变化过程中簇首节点的移动距离之和来研究k-跳分簇网络中簇相邻关系的稳定性。两相邻簇不断地相对移动,当簇首节点间距离超过2R时,则两簇关系由相邻变为相离;当簇首节点间簇离小于R时,则两簇关系由相邻变为簇融合,其中一个簇首节点将放弃簇首身份成为普通节点。因此,簇相邻关系的变化根据两相邻簇的相对移动情况分为簇相离(clusterdeparture)和簇合并(clustermergence)2种情况。引理12个簇首节点各自沿任意方向以速度V直线运动可以看作一个簇首节点静止、另一个簇首节点沿任意方向以最高速度为2V,平均速度为2V/π的直线运动。证明设2个簇首节点A、B的移动速度分别为。以其中一个簇首节点A作为坐标原点,则另一簇首节点B在新坐标系的速度可以表示为向量的模表示坐标变换后簇首节点B的速度值:由式(1)可知当2个簇首节点运动方向相同时,簇首节点B速度取得最小值0;当运动方向相反(向量角相差π)时,簇首节点B速度取得最大值2V。新坐标系下簇首节点B的平均速度值为由于向量的向量角都是在区间[0,2π)内均匀分布并且它们的模相同,显然向量的向量角θB′同样在区间[0,2π)内均匀分布。证毕图1是经过坐标变换后2个相邻簇A、B最初相邻时的场景,簇首节点间距离为d,簇首节点A静止,而簇首节点B以速度移动,其中,θ∈[-π,π)。由于簇首节点A静止,相邻簇A和B从开始相邻到相邻关系发生变化过程中簇首节点的移动距离之和实际上就是簇首节点B的移动距离l。由图1可知,簇首节点B的移动距离l与两簇首节点距离d和节点B移动速度的向量角θ有关:定理1两簇在相邻关系发生变化过程中簇首节点移动的距离之和s的平均值与簇的半径成正比:E(s)=τkr,其中,τ为大于0的常数。证明由于任意2个相邻簇的簇首节点间的距离d在区间(R,2R]上均匀分布。由引理1可知,在新坐标系下s等于簇首节点B的移动距离l(d,θ),其中,变量θ在区间[-π,π)内均匀分布。因此可以得到s的平均值:令,则有:结合式(3)可以得到:其中,λ表示式(6)中2个二元函数积分之和,为一个小于5π/3的常量。由式(4)和式(7)可知两簇在相邻关系发生变化过程中簇首节点移动的距离之和的平均值E(s)与簇半径k成线性正比。证毕这里用簇邻居变化率(NCR)表示由于簇不断移动导致的簇相邻关系变化的频繁程度,其中,NCR=1/平均移动时间=平均移动速度/平均移动距离,由引理1和定理1可得由上述分析可知,分簇网络中簇半径越大,簇邻居变化率NCR越小,相应地,网络簇一级拓扑结构也就越稳定。2.3确保网络带宽的恢复簇控制开销强度Ostr是指网络中单个节点信号覆盖范围(半径为r的圆型区域)内的由一次簇维护过程产生的平均控制报文数,它反映了簇维护过程占用无线网络带宽的程度。簇维护引起的控制开销Oinner包括簇首节点的广播报文和成员节点的响应报文。对于k-跳分簇网络而言,Ni表示距离簇首节点i跳的成员节点数,距离簇首节点i跳的成员节点发送响应报文至其簇首节点的转发过程会引起i个控制报文,由此可以得到k-跳分簇网络中单个簇的一次维护开销:Oinner=簇内广播报文开销+成员节点响应报文开销由式(9)可以得到节点的平均簇内控制开销:从式(10)可以看出平均簇内控制开销与簇半径k成正相关关系。3基于优化小组的混合路由协议3.1打造网关节点和普通节点基于优化分簇的混合路由(HOCR)协议属于分层路由协议,其网络中的组织结构如图2所示。在协议中,网络被划分为多个比较稳定的簇,簇由一些相互临近的节点组成,它包括一个簇首节点,其余的是网关节点和普通节点。HOCR在簇一级路由时采用了表驱动的路由策略,而对簇内节点间通信采用了按需的路由策略。HOCR协议采用了部分源路由策略:它在簇与簇之间采用了源路由策略,这样路由发现工作由源节点所在簇的簇首节点完成,而路径上的其他簇首节点无需做任何工作,从而大大减轻了簇首节点的负担;对于簇内节点间通信,HOCR则采用了基于链路状态路由策略,因为它的主要应用场景是大规模网络,一般来说路径较长,这样做可以使数据分组的头部仅包含簇地址序列,避免了过低的分组净载荷率。HOCR协议主要包括簇的形成与维护和路由2部分。3.2簇内节点广播和beacon报文HOCR协议定义网络中的节点有4种状态:CH(簇首)、Gateway(网关)、Ordinary(普通)和Undecided。每个节点在初始化的时候状态都是“Undecided”,它必须确定自己的状态(CH、Ordinary或Gateway)。BEACON、BEACON响应(BEACONREPLY)、簇间BEACON(BEACONCL)是簇首节点用于维护簇内成员信息和全网拓扑结构信息的报文。在网络的初始化阶段,处于未知状态的节点通过不断地广播k-跳BEACON报文来选举簇首节点从而形成半径为k的簇——簇首节点到簇内任何成员节点的距离最多为k跳。簇的形成采用了最高节点度启发式算法:每个节点通过交互控制消息获悉邻居节点的数目,然后将自己的度数向邻居节点广播,该节点和其相邻节点中最大度的节点被选举为簇首节点(在度数相同时,则选择ID最小的节点作为簇首节点)。网络中从属于一个以上簇的成员节点为网关节点,它负责跨簇通信时数据分组的簇间转发工作。在簇形成以后,簇首节点通过定期地广播一个k-跳的BEACON报文,并接收簇内成员节点发送的BEACON响应报文,从而维护簇内成员信息;网络中簇首节点形成虚拟骨干网络,它们通过定期地向所有簇首节点广播簇间BEACON报文来掌握全网的拓扑结构(包括网络中簇的分布情况和各簇的成员节点信息)。另外当2个簇首节点侦听到对方进入自己的发射半径后(一个簇首节点接收到另一个簇首节点广播的k-跳BEACON报文),其中一个簇首节点必须放弃其簇首状态,从而完成簇的合并。为了减少网络中簇的数量,尽量避免簇首节点频繁更替,保障簇首节点的稳定性,HOCR规定:当一个簇首节点收到其他簇首节点广播的BEACON报文时,它并不是立即放弃其簇首状态,而是检查自己的成员节点的状态,只有当所有成员节点都为网关节点时它才放弃簇首状态,否则仍然保持其簇首状态。3.3按需路由策略下的数据转发当节点有数据要传递的时候,它必须建立一条到目的节点的路径,然后数据分组通过建立的路径被转发到目的节点。整个通信的过程如图3所示。HOCR协议中,通信过程中的路由分为2层——簇级和簇内节点级,簇内路由请求(RREQ)、簇内路由响应(RREP)、簇内路由出错(RERR)、簇间路由请求(RREQCL)、簇间路由响应(RREPCL)和簇间路由出错(RERRCL)是HOCR协议进行路由需要用到的报文。由图3可知,节点在发送数据时,它会先发送RREQCL分组给其所在的簇首节点,以获得从该节点到目的节点的簇级路径——簇链(CL);簇首节点在收到RREQCL分组后,通过RREPCL分组返回给源节点一个从源节点所在的簇到目的节点所在簇的簇地址列表;然后,源节点就可以根据收到的簇地址列表发送数据;数据分组会根据簇地址列表逐簇进行转发,直至到达目的节点所在簇;数据分组在沿途各个簇内的节点间进行转发时采用了按需路由策略,分组在各个簇内的节点级路径(ICR)则是由各自的网关节点建立,并根据簇内节点的移动情况动态变化的。为了减少簇首节点的负载,尽可能防止簇首节点成为瓶颈节点,HOCR设计簇首节点主要负责维护簇内和簇间的路由信息,而通过延迟响应簇内路由请求RREQ分组来尽可能避免参与数据分组转发工作。由于节点的移动,网络拓扑结构会发生变化,正在进行数据传输的路径可能被破坏,必须采取一些措施来对路径进行及时地本地修复,以尽可能小的代价保证节点间正常通信。簇首节点会不断地检测其相邻簇的变化情况,如果它检测到某个邻簇的簇首节点已经发生变更或该邻簇已经与自己所在簇变得相离,而且有数据要经该邻接簇转发至目的节点时,作为簇地址列表上的中间节点,首先它会重新计算一条从自己到目的节点的簇地址列表,把接收到的数据按照新的簇地址列表转发出去,同时它会把计算出的簇地址列表数据分组中的原簇地址列表中的有效部分(从源节点所在簇到自己所在簇部分)拼接成一条新的路径,通过RERRCL发送给源节点,以使其在以后的数据传输中使用正确的路径。HOCR支持节点簇间漫游(roam),簇首节点会通过周期性地广播BEACON分组来维护簇内成员节点信息,一旦它发现某一成员节点离开本簇,而且该节点又是某一正在进行数据通信的路径的目的节点,在侦听到该路径上的数据分组后,它会发送RERRCL分组给持有该数据分组的节点,使得该节点能够把数据分组成功地转发到漫游到其他簇的目的节点,并把RERRCL分组沿着反向路径转发给数据分组的源节点以通知其更新后的路径。3.4性侵节点补偿参数的确定为了提高协议性能和减少协议控制开销,从簇的尺寸和簇的形成策略上对HOCR的分簇算法进行了考虑。由于HOCR主要应用在大规模的adhoc网络中,如果簇的尺寸过小(簇的半径过小),则会使得簇的数量过多,路由开销和分组延时较大,而且节点容易在簇间漫游,从而导致路由频繁过时,无法适应大规模网络;簇的尺寸过大,则会导致簇内节点数过多,将会导致网络中簇维护开销过大、簇首节点负担过重,并且簇内路径长度增大使得网络局部负载增多,这些都会导致网络性能明显下降。因此,在分簇网络中一定存在一个最佳的簇尺寸Ropt使得网络性能最优。最佳簇尺寸是由下述因素决定的。1)簇间BEACON广播频率f,它反映了簇首节点为了维护簇级路径沿途各簇相邻关系而进行簇间BEACON广播的频度,值越小网络簇间控制开销越低,由文献可知,在保证通信可靠性的前提下,f值与对象平均移动速度成正比,而与对象平均移动距离成反比,即与NCR成正比:其中,δ为大于0的常数。2)簇数目NUMcluster,反映了网络中簇的数目及以簇为单位的簇级网络直径大小,并决定了簇级路径的平均长度。由于移动自组网拓扑动态变化,长路径发生中断的概率比短路径大,因此簇级路径应当尽可能短,即簇数目应尽可能小:其中,α为(0,1]区间内的常数,网络节点数为N,节点密度为ρ,节点发射半径为r。3)簇内控制开销强度Ostr-inner,它反映了簇内维护过程占用无线网络带宽的程度,是节点单位时间内的平均簇内控制开销,其值越小则网络中有效负载容量越高,由式(10)并结合文献可知上述因素中前2个因素的取值都是越小越好,它们决定了网络簇间控制开销Ointer:其中,ω表示大于0的常数。相应地,每个节点的平均簇间控制开销强度:结合式(13)和式(15)可知,HOCR协议中每个节点的控制开销强度Ostr如下:在式(16)中,对于任意网络而言,ρ、r、N、V都是固定不变的,HOCR协议通过选择使节点控制开销强度Ostr最小的k值作为簇尺寸Ropt,从而获得最大的网络性能。Ostr值最小时对应的簇尺寸作为成簇策略的重要参数。式(16)分成2部分,前半部分与簇尺寸k成正相关,k值越大,其值越大;后半部分与簇尺寸k成负相关,k值越大,其值越小。k取值范围为[1,n/2],结合式(16)的一阶求导取值情况分析,一定存在使得式(16)最小的最优簇尺寸k,由实际网络参数ρ、r、N、V的值决定。4结果与分析4.1实验平台架构本节通过仿真实验来比较HOCR与AODV、DSR(基于链路状态和源路由的按需平面路由协议)、ZRP(基于混合路由策略的分层路由协议,其中区域半径r为2跳)和CBRP(簇内和簇间均采用按需路由策略的分层路由协议)等4个代表性协议的性能。采用了NS2作为仿真实验平台,从网络的平均路由开销、数据报接收率、网络延时等方面对协议进行考察与分析。仿真实验中,200个节点被随机部署在2000m×2000m的区域内,网络中节点的发射半径为250m。节点的运动模型为randomwaypoint:最大移动速度为5m/s,节点最大停留时间为30s。流量模型采用CBR(固定比特率)模型,数据速率为4packet/s,数据负荷为512byte。实验中HOCR协议的簇内BEACON的广播周期设置为5s,簇间BEACON的广播周期设置为10s。4.2仿真实验仿真在仿真实验中,采用了2种仿真方案:一种方案是在相同的网络规模和网络负荷程度条件下,通过改变节点的移动速度,观察路由协议性能的变化;另一种方案是在相同的节点移动速度和相同的网络规模条件下,改变通信对数目,考察各路由协议在不同网络负荷下的适应性。对于本实验中的网络仿真场景而言,2000m×2000m区域内由发射半径为250m的节点形成的分簇网络中的簇数目不超过100,通过对式(16)进行二阶求导得到该高次方程的近似整数拐点为2,即为最优簇尺寸。因此仿真实验中HOCR中的簇形成策略采用最优值为2作为簇半径。在第一种仿真方案中对簇尺寸为1跳和3跳的HOCR协议(分别以HOCR-1和HOCR-3来表示)进行考察,以验证HOCR最优簇半径选取的正确性。4.2.1路由错误与网络多种设置本仿真的目的是比较协议HOCR、DSR、AODV、ZRP、CBRP对adhoc网络中节点移动的适应性。图4给出了节点以不同速度移动时各协议的平均路由开销。当节点移动较慢时,完全采用按需路由策略、没有额外控制包的CBRP和DSR的平均路由开销最小;簇内节点间采用了表驱动策略的ZRP需要定期地进行簇内路由信息广播,其平均路由开销稍大;HOCR由于需要进行定期簇内成员信息维护和簇间簇首节点间路由信息广播,其平均路由开销要比前3种协议大;AODV由于要频繁发送Hello包而开销最大。随着节点移动速度的加快,各协议路由开销都在增加,这是因为随着节点移动加快,路由失效会更加频繁,由此引起路由出错和修复过程都会产生控制开销。但是由于各协议的路由出错处理和修复机制不同,由此带来的路由开销增幅也不同:完全采用按需源路由策略的DSR、CBRP和在簇与簇之间采用按需源路由策略的ZRP增幅最大,都增加了15个分组的平均路由开销;AODV和HOCR则由于采用了本地修复策略,增加了不到10个分组的平均路由开销。图5给出了节点以不同速度移动时各协议平均端到端延迟情况。当节点移动速度较小时,采用链路状态路由策略的HOCR和AODV的平均延迟最小;对于在簇内节点间采用表驱动链路状态路由策略的ZRP,它由于通信路径上各簇内部的主动路由策略而平均延迟较小;而完全采用源路由策略的DSR和CBRP的平均延迟则偏大。随着节点移动速度加快,DSR、CBRP和ZRP的平均延迟迅速增加,而AODV和HOCR的平均延迟的增幅则较小。这是因为随着节点移动速度的加快,路由失效更加频繁。当路由失效时:DSR、CBRP和ZRP发送出错报文给源节点,由源节点重新发现路径,这样会产生大量路由开销、网络拥塞及很大的传输延迟,而且路由失效期间发送的数据分组因为找不到路径而被丢弃;AODV和HOCR采用了本地路由修复策略,持有数据分组的中间节点能够很快发现新的有效路由,继续进行数据分组传输,另外由于路由修复是在较小范围内进行的,由此产生的路由开销也不会太大。上面对节点以不同速度移动时各个协议的数据分组接收率的变化情况也作了分析,结果可以从图6中的实验数据得到验证。由图4、图5和图6可以看出:HOCR-1受节点移动速度影响最大,随着节点移动速度增大,HOCR-1的平均路由开销迅速增加、数据分组接收率急剧下降;HOCR和HOCR-3由于簇半径大而受节点移动速度影响小,但由于HOCR-3簇内路径长度相对节点移动速度过大,其平均端到端传输延迟要高于HOCR和HOCR-1。综合考虑,簇半径为2的HOCR的网络性能表现优于更小簇半径的HOCR-1和更大簇半径的HOCR-3。4.2.2通信对数对特征特性的影响本仿真的目的是比较协议HOCR、DSR、AODV、ZRP、CBRP对adhoc网络中不同网络负荷的适应性。图7给出了不同程度网络负荷下各路由协议的平均路由开销情况。AODV、DSR、CBRP和ZRP协议的平均路由开销都是随着网络中通信对数的增加而上升,而HOCR则是随着通信对数的增加先是大幅度下降,等下降到一定程度又略有上升。由图7可以看出,在网络中通信对数占节点总数的比例不超过15%时,HOCR平均路由开销一直高于其他3种协议,但是该比例超过15%以后,HOCR平均路由开销要低于其他3种协议。这主要是由于HOCR在簇一级采用了表驱动路由策略,它的簇间路由开销只跟网络中节点数有关,而与通信对数无关;而且由于HOCR中簇内路径由网关节点建立,随着通信对数的增加,簇内路径被大量复用,簇内路由开销与通信对数的比值下降。数据分组数增加而簇间路由开销不变、簇内路由开销缓慢增加,这些因素导致了HOCR的平均路由开销随着通信对数的增加而下降。AODV平均路由开销上升最快是由于它会周期性地重新发现通信中的路径。DSR、ZRP和CBRP采用源路由策略,路径不具备复用性,路径发现会引起全网广播,而且通信对数的增加会加剧网络拥塞现象。因此,随着通信对数的增加,D