李志军,李培日,刘 丹
(吉林大学 通信工程学院,长春 130012)
混合WMN(Wireless Mesh Network)既具有基础设施Mesh网络的稳定性,又具有客户端Mesh网络的灵活性,结构更加完整、功能更加丰富且适应场景也更加广泛[1-2]。混合WMN中的移动性管理问题是网络成功部署需要考虑的关键性因素,无缝连接服务也是WMN研究的一个亟待解决的问题[3]。文献[4-12]对网络中的移动性管理方案分别进行相应的研究,优化了原网络性能。
IEEE在2011年9月提出的802.11s标准[13]中,给出了一种新型混合Mesh路由协议HWMP(Hybrid Wireless Mesh Protocol),对混合WMN中的节点进行路由管理。然而,HWMP协议对混合WMN中新增节点的域间移动性管理方案还存在一些不足,将节点的路由建立与代理更新消息进行全网广播会造成一定时延。针对上述延时问题,笔者在HWMP协议的基础上提出了一种改进型的移动性管理方案AHWMP(Advanced Hybrid Wireless Mesh Protocol),解决HWMP协议的域间移动性管理方案中全网广播PREQ(Path Request)消息和代理更新消息造成网络拥塞的问题,提高网络性能。
基于HWMP协议,AHWMP方案对原信息元素PREQ和PREP(Path Request)的帧结构进行了修改,并引入了ACK(Acknowledgement)与NACK(Negative Acknowledgement)两个信息元素接收和确认源消息。此外,该方案还对每个节点的路由表、邻居表也进行了修改。AHWMP的信息元素有5种:RANN(Root Announcement)、PREQ、PREP、ACK和NACK。
AHWMP中PREQ的帧结构如图1所示。规定新增Mesh客户端的路由信息存储在其邻近的Mesh客户端的路由表中,因此PREQ帧中不需要Proxied Source MAC Address字段,并增加了一个名为Level的字段存储先验模式中Root节点或转发节点的级别信息。
图1 PREQ帧结构
表1 Request Type字段含义
规定两种情况下可发送PREQ帧:寻找到达Mesh客户端的路由;请求与同类Mesh客户端之间的通信。因此,对于以上两种情况,增加Request Type字段表示PREQ的回复类型。该字段的字长为8 bit,字段类型含义如表1所示,其余字段功能与HWMP相同。
PREP的帧结构如图2所示,增加了Reply Type字段,其他字段与HWMP相同。
图2 PREP帧结构
ACK与NACK消息的帧结构与PREP的相同,只是将其中Reply Type字段的值分别设定为01、02,以确定应答消息的类型。
HWMP的路由表结构如图3所示。路由表新增Root_Ad字段,用于存储Root节点的地址;Root_Lev字段,用于存储Mesh客户端在树形拓扑中的级别信息;Child to parent sibling preq sent字段追踪当前发起请求的Mesh路由器的同类节点的数量;Preq_recvd字段明确来自Mesh客户端的PREQ请求是否被中间Mesh客户端收到;Is_mobile字段表示该Mesh客户端是否是移动节点,若是则置1。P_Forward chain字段表示此Mesh客户端是否为前向指针链的一部分,当其值为1时表示该节点是到达目的节点的前向指针链的一部分。
混合WMN中的每个Mesh节点都有一个用于追踪其邻居节点信息的邻居表,其结构如图4所示。这里在HWMP邻居表中增加了用于存储Root节点的地址和Mesh客户端在树拓扑中的级别信息的Nb_table_Root和Nb_table_lev字段(见图4)。
图3 路由表结构图
图4 邻居表结构图
新增字段Nb_relationship记录该Mesh客户端与其邻居Mesh客户端之间的关系,表2为该字段不同值的含义。
表2 neighbor relationship字段值含义
基于修改后的信息元素的帧结构与路由表,对混合WMN进行先验式拓扑建立并使用先验PREQ路由选择机制。
对于网络中的任一Mesh客户端,当其移动时,源Mesh客户端接入的MR(Mesh Router)称为OR(Original Router),目的MR称为DR(Destination Router)。当MC(Mesh Client)移动到DR的覆盖范围内时,MC与DR建立连接,当DR有到达MC的路由时更新原路由表,否则在其路由表中建立到达MC的路由信息。此时MC路由表中Is_mobile与Hop count字段值为1,之后MC对DR与OR的关系进行判定。AHWMP方案先验式管理算法具体步骤如下。
1)若DR是OR的子类节点,DR将向OR发送一条PREQ消息,OR接收到此条问询消息后返回一条ACK确认消息,建立双向路由,完成切换过程。
2)若DR是OR的同类节点,DR向Root节点发送PREQ消息,Root节点在接收到PREQ消息后返回一条PREP消息。中继MR根据其路由表信息向OR发送NACK消息断开原连接并向DR发送ACK消息,建立双向路由,完成切换过程。
3)若DR是OR的父类节点,DR会向其同类节点发送PREQ消息确认同类节点是否有到达MC的路径。若存在,则此同类节点会返回给DR一条ACK确认消息,包含由此同类节点指向DR方向的一条路径,即一个前向指针,Root节点根据此前向指针建立了一条下行路由,并完成切换过程;若不存在,则同类节点向DR发送否定消息NACK,DR在接收到NACK消息后向Root节点发送PREQ消息寻问Root节点是否有到达MC的路径,之后选路过程与步骤2)相同。
AHWMP方案的先验式管理算法如图5所示。
图5 先验式管理算法
采用Matlab与NS-3对于AHWMP方案进行性能仿真。WMN的网络拓扑由25个Mesh路由器节点组成,Mesh路由器以5×5格形均匀分布在1 000×1 000 m的区域内。Mesh客户端随机分布在这个区域内,且服从随机点分布模型。网络的根节点是Mesh路由器格型拓扑的中心节点,仿真使用CBR(Constant Bit Rate)业务流。
采用以下指标评价方案性能。
1)平均网络吞吐量。即单位时间成功到达目的节点的比特数,数学表达式为
(1)
其中∑R(d)为目的节点成功接收的数据包总数,Δt表示发送数据包与接收数据包之间的时间间隔。
2)平均路由开销。即网络中所有源节点为使数据包成功接收所发起的控制开销包的总数与所有目的节点成功接收的数据包总数的比值。
3)平均端到端时延。所有数据包从源节点到目的节点用的总时间与所有成功接收的数据包数量的比值,单位ms。数学表达式为
(2)
其中Dj为数据包j的端到端时延,N为目的节点成功接收的数据包数。
4)平均切换开销,即网络中所有移动节点移动性管理的切换成本平均开销。
目的Mesh路由器是源Mesh路由器的子节点时,切换开销
C1=2r
(3)
其中r表示每跳的时延。
目的Mesh路由器是源Mesh路由器的同类节点时,切换开销
C2=2αr+r
(4)
其中α为任意Mesh路由器到GW(Gate Way)的平均跳数。目的Mesh路由器是源Mesh路由器的父类节点时,切换开销
(5)
故切换开销
C3=2r+PNACK(2αr+r)
(6)
其中PNACK为收到NACK消息的概率。
综上,单位时间内AHWMP方案的平均切换开销为
(7)
其中l表示一个Mesh路由器的平均子节点数;n表示一个Mesh路由器的平均同类节点数;p表示一个Mesh路由器的平均父类点数;Mesh客户端在Mesh路由器范围内的等待时间服从λs的泊松分布。
在HWMP方案中,代理更新与代理确认开销
C4=2r
(8)
PREQ与PREP包寻路过程的开销为
C5=[2α+(1-Pd)(M+α)+2Pdα]r
(9)
其中Pd表示目的Mesh路由器有外部Mesh节点路由信息的概率。故HWMP方案的平均切换开销为
C=λs(C4+C5)
(10)
笔者分别从Mesh客户端的数量以及最大移动速度两方面,考虑HWMP方案与AHWMP方案对4个评价指标的影响,仿真结果如图6~图10所示。
3.2.1 不同Mesh客户端数量的影响
从图6可见,不同Mesh客户端数量下AHWMP方案的平均吞吐量明显优于HWMP方案的平均吞吐量。一方面,HWMP在切换时广播PREQ消息,并且进行代理更新与应答,因此会对网络造成一定的拥塞;另一方面,AHWMP对PREQ消息的发送有一定的限制条件,因此网络中PREQ消息的数量可被控制。此外,AHWMP不需代理更新与应答机制。随着网络中Mesh客户端数量的增加,网络需要不断的发送和接收PREQ消息,因此导致网络拥塞,吞吐量减少。
如图7所示,AHWMP方案的平均路由开销明显优于HWMP方案平均路由开销。在HWMP方案中,网络切换时既要发送PREQ消息又要接收PREP应答消息。同时,如果存在到达目的节点的路径,还需进行代理更新与应答,因此其网络的平均路由开销较高。
图6 不同Mesh客户端数量下的网络平均吞吐量 图7 不同Mesh客户端数量下的平均路由开销Fig.6 Comparison of average network throughput Fig.7 Comparison of average routing overhead
从图8、图9可见,不同Mesh客户端数量下,AHWMP方案的性能明显优于HWMP方案。在切换时,HWMP方案广播的PREQ消息造成拥塞,产生了网络切换时延,并且还需进行代理更新与应答,因此切换开销也较大。
图8 不同Mesh客户端数量下的平均端到端时延 图9 不同Mesh客户端数量下的平均切换开销Fig.8 Comparison of average end to end delay Fig.9 Comparison of average handoff cost
3.2.2 不同Mesh客户端移动速度的影响
在考虑Mesh客户端的移动性时,Mesh客户端的数量固定为40个,通过改变Mesh客户端的最大移动速度分析网络的性能,其仿真结果如图10所示。
图10 不同移动速度下的网络性能情况
从图10可见,随着Mesh客户端最大移动速度的增加,AHWMP的各项网络性能优于HWMP。因为随着移动速度的逐渐增加,网络中的路由中断与路由重连的次数也在增加,所以会发生丢包,路由开销也会增大。在移动性管理时,HWMP方案会发送大量的路由管理包而重新建立路由连接,这一过程会增加网络中数据包数量,因此其路由开销以及端到端时延等网络性能较差。而AHWMP对于路由管理包的发送具有一定限制,在一定程度上可降低网络中路由管理包的数量,网络拥塞较低,因此其网络性能较好。由于Mesh客户端的随机移动性,网络的拓扑会实时变化,而且在仿真时随机选择源和目的节点,因此随着Mesh客户端数量和移动速度的变化,仿真结果会不规则地波动。
笔者针对HWMP协议对于混合WMN中新增节点的域间移动性管理方案还存在的不足,提出改进型移动性管理方案-AHWMP方案,解决了HWMP协议域间移动性管理方案中全网广播PREQ消息和代理更新消息造成网络拥塞的问题。AHWMP方案改进了HWMP协议域间节点移动性管理的机制,提出HWMP协议主动路由模式下新增节点的路由更新算法,对于PREQ消息的发送做出一定的限制。仿真结果表明,与HWMP协议中的方案相比,AHWMP方案减少了全网路由更新数据包的数量,在网络平均吞吐量、网络平均端到端时延等方面具有更好的效果,在提高网络吞吐量的同时也有较低的切换开销。