一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现方法

摘要

本发明公开了一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现方法，设计了以网关节点为簇头、网关MAC地址作为簇标识并添加在RANN帧和PREQ帧中实现普通节点的簇选择和簇分割；修改PREP帧和PERR帧的处理过程维护先验树形路由实现节点换簇时路由表和网关负载的平滑过渡；普通节点选择簇时综合考虑节点到网关的路径Metric和网关自身负载情况选择最佳的网关达到均衡网关负载的目的，负载大小是网关节点有线网卡的发送队列缓冲区长度占队列总长度的比例并添加在RANN帧中进行广播。本发明实现了基于动态分簇的多网关无线Mesh网和网关负载均衡，减小了网络开销并均衡了网关负载从而提升整个网络的性能。

权利要求

1.一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现方法，其特征在于，基于IEEE802.11s协议，以网关节点作为簇头、网关MAC地址作为簇标识划分簇，在RANN帧和PREQ帧中添加簇标识，实现普通节点的簇选择和簇之间的分割；限制RANN帧广播范围，减小网络开销和避免节点无效切换；修改PREP帧和PERR帧的处理函数，判断节点是否在先验树形路由中为叶子节点，规定只有叶子节点可以换簇，实现先验树形路由的维护，进而实现节点换簇时树形路由和网关负载的平滑过渡；普通节点选择簇时，综合考虑节点到网关的路径Metric和网关自身负载，选择最佳的网关实现网关负载均衡。

2.根据权利要求1所述的一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现方法，其特征在于：实现普通节点的簇选择和簇之间的分割，具体为：以网关节点作为簇头、网关MAC地址作为簇标识来区分不同的簇，普通节点通过网关节点发出的RANN帧中的簇标识即根节点地址选择簇，在PREQ帧中添加簇标识实现不同簇中的节点无法建立路由达到不同簇之间相互分割的效果。

3.根据权利要求1所述的一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现方法，其特征在于：限制RANN帧广播范围具体为：限制网关节点发出的RANN帧只能在本簇和邻簇边界节点进行广播。

4.根据权利要求1所述的一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现方法，其特征在于：修改PREP帧和PERR帧处理函数维护树形路由，具体为：在PREP帧处理过程中通过判断本节点是否为其它节点到网关节点路径的下一跳来统计自己的子节点数，子节点数为零则表明自己在先验树形路由中为叶子节点，规定只有叶子节点可以换簇，减小节点换簇时对同簇中其它节点的影响并限制了大量节点同时换簇，实现树形路由和网关负载的平滑变化，非叶子节点收到关于子节点的PERR帧时表明该子节点路径发生变化，此时将自己的子节点数减1。

5.根据权利要求1所述的一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现方法，其特征在于：簇选择算法：

普通节点在进行簇选择时综合考虑自身到各网关的路径Metric和网关负载情况，并预测换簇后网关的负载情况来决定选择哪个簇，保证节点能够以较优路由与外部网络通信并均衡网关负载，同时设置一个Meric差阈值限制节点换簇条件，防止节点“乒乓切换”。

说明书

一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现

方法

技术领域

[0001] 本发明涉及一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现方法，属于无线Mesh网通信技术。

背景技术

[0002] 无线Mesh网（WMN）在世界范围内的应用越来越广泛，而较好的网络性能是大规模应用的重要条件。

[0003] 目前基于IEEE802.11s协议的WMN大部分只有一个网关节点，而网关节点作为连接WMN与外部网络的关键节点，网络中大量向外网传输的业务都在此汇聚，因此网关节点很容易成为WMN与外界网络通信的瓶颈节点。在传统的多网关WMN中所有网络节点都在一个子网中，各节点与其它大量节点都需要交互信息，网络开销很大；而且由于节点分布和流量分布的随机性，通过各个网关向外网传输的流量也会有很大差异，造成信道资源浪费。所以动态分簇的多网关和网关负载均衡的实现能极大的提高WMN的网络性能。

发明内容

[0004] 本发明所要解决的技术问题是提供一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现方法，基于IEEE802.11s实现动态分簇的多网关无线Mesh网和网关负载均衡，从而提高网络性能。

[0005] 本发明为解决上述技术问题采用以下技术方案：本发明提供一种IEEE802.11s下基于动态分簇的多网关WMN负载均衡实现方法，基于IEEE802.11s协议，以网关节点作为簇头、网关MAC地址作为簇标识划分簇，在RANN帧和PREQ帧中添加簇标识，实现普通节点的簇选择和簇之间的分割；限制RANN帧广播范围，减小网络开销和避免节点无效切换；修改PREP帧和PERR帧的处理函数，判断节点是否在先验树形路由中为叶子节点，规定只有叶子节点可以换簇，实现先验树形路由的维护，进而实现节点换簇时树形路由和网关负载的平滑过渡；普通节点选择簇时，综合考虑节点到网关的Metric和网关自身负载，选择最佳的网关实现网关负载均衡。

[0006] 上述方法具体包括如下步骤：（1）以网关节点作为簇头、网关MAC地址作为簇标识实现簇选择和簇分割在多网关WMN中，网关节点自动当选为簇头，网关MAC地址作为簇标识来区分不同的簇。
普通节点初始化为空簇，簇标识为全零地址，节点第一次收到某个网关节点发出的RANN帧时通过该RANN帧中的簇标识即根节点字段加入该簇，此后收到其它网关节点的RANN帧时运行簇选择算法决定是否换簇；在PREQ帧中添加簇标识，节点与任意节点通信时都会首先发送PREQ帧查找路径，所有节点收到PREQ帧时比对自己的簇标识和PREQ帧中的簇标识，相同则会进行下一步处理，不同则直接丢弃，这样不同簇中节点无法建立路由实现簇分割；
（2）限制RANN帧广播范围
为了避免节点换簇后无法建立到新网关的有效路径，限制网关节点发出的RANN帧只能在本簇和邻簇边界节点进行广播，简化网络结构，减小网络开销；
（3）修改PREP帧和PERR帧处理过程维护树形路由
在先验树形路由中，离网关节点即根节点越近的节点如果换簇会影响下面所有的子孙节点，同时如果大量节点同时换簇会造成簇的流量突变。为解决这两个问题，在PREP帧处理过程中判断本节点是否作为其它节点到网关节点路径的下一跳来统计自己的子节点数，子节点数为0表明自己在先验树形路由中为叶子节点，规定只有叶子节点可以换簇，这样可最大程度减小节点换簇时对同簇中其它节点的影响并限制了大量节点同时换簇，实现树形路由和网关负载的平滑变化，非叶子节点收到子节点的PERR帧时表明该子节点路径发生变化，此时将该节点从子节点MAC表中删除并将子结点数减1；
（4）簇选择算法，实现网关负载均衡
普通节点在进行簇选择时综合考虑自己到各网关的路径Metric和网关负载情况，并预测换簇后网关的负载情况来决定选择哪个簇，保证节点能够以较优路径与外部网络通信并均衡网关负载，同时设置一个Meric差阈值，只有节点到网关之间的路径Metric值的差距超过该阈值才有可能换簇，防止节点“乒乓切换”。

[0007] 本发明采用以上技术方案与现有技术相比，具有以下技术效果：1、提升网络性能：多网关负载均衡的实现，网络中节点与外部网络交换数据时能够选择较优的网关减小传输延时提高网络容量进而极大的提升为了网络性能；
2、减小网络开销：分簇的实现使得节点只需与同簇的节点交互信息，减小了整个网络的开销；
3、简单：该实现方法只需要对802.11s协议栈进行修改而不要添加特别的硬件和软件支持；
4、平台移植性好：本发明在Linux系统下进行开发，可以在PC、嵌入式等平台自由移植。

附图说明

[0008] 图1 为本发明中动态分簇的多网关无线Mesh网示例图。

[0009] 图2为在RANN帧中添加簇负载指数示意图。

[0010] 图3为普通节点对RANN帧接收处理示意图。

[0011] 图4为在PREQ帧中添加簇标识示意图。

[0012] 图5为实现树形路由维护的PREP帧处理流程图示意图。

[0013] 图6为簇选择算法流程图。

具体实施方式

[0014] 下面结合附图对本发明的技术方案做进一步的详细说明：如图1所示为一种IEEE802.11s协议下基于动态分簇的多网关无线Mesh网，包括多个网关节点MPP和若干个普通节点（MP），整个Mesh网络被划分为多个簇，网关节点作为簇头，同簇的节点可以直接通信，不同簇的节点必须通过网关节点进行通信，MP节点可以根据自身到网关的路径Metric和网关负载情况决定是否换簇实现动态分簇。

[0015] 如图1所示，网关节点MPP主要实现簇标识和负载指数的获取与传播：①簇标识和负载指数的获取：簇标识作为每个簇的标记必须具有唯一性，本发明中，网关节点将自己的MAC地址作为簇标识；普通节点与外部网络通过本簇网关节点进行通信，大量的数据流在网关节点处汇聚然后发往控制中心，本发明将网关节点的有线网卡发送队列缓冲区长度占队列总长度的比例作为负载指数用以表征网关当前负载情况。

[0016] ②簇标识和负载指数的传播：网关节点为了通知普通节点自己的簇标识和负载情况，需要周期性地广播自己的簇标识以及负载大小，本发明中选择RANN帧携带簇标识和负载指数进行广播。如图2所示，RANN帧主要包括MAC首部和HWMP路径选择帧两部分，本发明对HWMP路径选择帧中的RANN帧体进行修改，现有的RANN帧体并没有簇标识和负载指数数字段，但因为本发明中簇标识为网关节点的MAC地址即RANN帧中的根节点地址字段（在本发明后面所提的簇标识均为根节点地址，不再进行区分），为了实现广播簇标识和负载指数的功能，本发明只需在RANN帧体中添加负载指数字段，即可告知普通节点簇标识和网关负载大小。

[0017] 如图3所示，普通节点（MP）通过对RANN帧的接收处理实现加入簇、限制RANN帧广播范围、簇选择、簇分割与路由建立功能：①加入簇：普通节点刚加入网络时没有任何簇的信息，此时普通节点的簇标识为全零的MAC地址；如图3所示当节点收到第一个RANN帧时，发现自己的簇标识为全零则会加入该网关所在簇并更新自己的簇标识为RANN帧中的簇标识，至此普通节点则成功加入该簇完成簇标识的初始化；
②限制RANN帧广播范围：节点加入一个簇后，除了会收到自己所在簇的网关发出的RANN帧，还会收到其它簇的网关发出的RANN帧，如果不加以限制，每个网关发出的RANN帧会在整个网络所有簇中广播，节点就会收到所有网关发出的RANN帧，节点的处理量会增大，造成极大的网络开销，所以本发明中限制RANN帧只能在本簇和邻簇边界节点进行广播。如图3所示节点收到来自非本簇的RANN帧时，会判断是否需要换簇，如果换簇才会转发该RANN帧，否则直接丢弃该帧，这样就可以保证RANN帧只能在本簇和邻簇的边界节点广播。这样做主要有三个原因：一是限制RANN帧的的广播范围可以减小网络中的网络开销；二是为了避免节点进行无效的换簇，如果邻簇的非边界节点收到了RANN帧，并且选择换簇但该节点的实际地理位置并没有改变，所以作为非边界节点可能换簇后无法建立到新网关的有效路径而产生无效换簇问题；三是只有边界节点可以收到邻簇RANN帧的做法和只有叶子节点可以换簇类似这样可以有效避免大量节点同时换簇。

[0018] ③簇选择：普通节点完成簇的初始化后，会收到当前网关和邻簇网关的RANN帧，当节点收到邻簇网关发出的RANN时，需要运行簇选择算法来确定是否需要换簇以实现网关负载均衡。

[0019] ④簇分割与路由建立：本发明中通过分簇的方式实现多网关无线Mesh网，分簇本质上就是不同簇之间的MP节点只能通过网关节点即簇头进行通信，而不能建立路由直接通信。IEEE802.11s默认路由协议HWMP中规定任意两个节点建立路由均是通过PREQ/PREP机制完成：节点A想建立到节点B的路径，则节点A会广播PREQ帧，节点B收到该PREQ帧后根据Metric信息选择最佳路径回复PREP帧给A节点，节点A收到PREP帧后，A与B之间的双向路由就建立起来了。本发明中如图4所示，在PREQ帧中添加簇标识字段，任意节点收到PREQ帧后首先对比PREQ帧中的簇标识和自身的簇标识是否相同，不同则直接丢弃，这样不同簇之间的节点则无法建立路由，实现簇分割的目的，而同簇的节点可以通过PREQ/PREP机制正常建立路由。

[0020] 在如图1所示的多网关无线Mesh网中，由于普通节点第一次加入簇的随机性和节点流量的随机性可能造成各个网关负载不均衡，为实现网关负载均衡，普通节点应该可以根据当前网关和邻簇网关负载情况进行换簇。IEEE802.11s默认路由协议HWMP是一种混和路由协议，在存在根节点即发送RANN帧的网关节点时，会形成一个以网关节点为根节点的先验树形路由。节点换簇时会影响树形路由中自己的子节点，同时由于网关负载信息通知节点的非实时性可能造成大量节点同时换簇造成网络流量突变和节点的“乒乓切换”，本发明中设计了一种只允许叶子节点换簇的方式维护树形路由和减小流量突变的方法，该方法需要解决以下问题：1、如何判断自己是否为叶子节点
本发明中每个节点添加一个子节点数的统计量用来统计在先验树形路由中自己的的子节点数，该变量初始化为0，当该变量为零时表示该节点为叶子节点，否则为非叶子节点；
2、如何统计自己子节点数
在IEEE802.11s默认路由协议HWMP中，所有节点间的路由都是通过PREQ/PREP机制建立的。HWMP节点是一种混合路由协议，包含先验路由和按需路由，当网络中存在作为根节点的网关节点时，网关节点会发送RANN帧给普通节点，普通节点收到RANN帧后会发送PREQ帧给网关节点请求建立路由，网关节点收到PREQ帧后会恢复单播的PREP帧给该节点，普通节点收到该PREP帧就建立了该节点到网关节点的双向路由，所有普通节点与网关节点的先验路由共同组成了一个以网关节点为根节点的先验树形路由。在HWMP中规定发送PREQ的节点为源节点，与其建立路由的对端节点为目的节点。

[0021] 本发明中每个节点都有一个自己的子节点MAC表，如图5所示，节点收到一个PREP帧时判断是否来自网关节点，如果是说明该PREP帧是建立先验树形路由的先验PREP帧，此时判断该帧的源节点是否为该PREP帧转发路径的下一跳，是则表明源节点在先验树形路由中是自己的子节点，此时查看源节点是否在自己子节点MAC表中，如果不在将该节点的MAC地址加入子节点MAC表并将子节点数加1，此后进入PREP帧正常处理流程。

[0022] 3、子节点换簇时父节点如何感知HWMP协议中定义了PERR帧来广播失效节点的信息，当节点检测到自己路由表的某条路径中的下一跳节点失效如换簇或关闭时，会发送关于该节点的PERR帧，该帧为广播帧，网络中的其它节点都能收到，同时本发明中还设计了节点检测到自己到网关节点路径下一跳变化时，主动发送自己的PERR 帧。本发明中，当节点收到或发送关于某个节点的PERR帧时会检查自己的子节点MAC表判断该节点是否为自己的子节点，如果是会将该节点的MAC地址从子节点MAC表删除并将子节点数减1。

[0023] 解决上面三个问题就可以在实时变化的网络中判断自己是否为叶子节点，本发明中只有叶子节点可以换簇，动态换簇可以实现网关负载均衡，极大的提高网络性能。

[0024] IEEE802.11s默认路由协议HWMP使用空时度量值（Airtime Link Metric,ALM）作为反应链路状况好坏的变量。ALM可以反映网络的时延，但该变量只能反映节点到网关节点的路径好坏而不能反映网关自身的负载情况，本发明中选择网关节点有线网卡的发送队列缓冲区长度占发送队列总长度的比例作为负载指数表征网关负载大小并添加在RANN帧中。如图3所示，节点收到邻簇网关发出的RANN帧时会运行簇选择算法来决定是否需要换簇。

[0025] 本发明中的簇选择算法综合考虑网关负载大小和到节点到网关路径Metric大小并预测换簇后网关的负载大小来决定是否换簇，算法设置了负载大小阈值  ，负载小于该阈值说明网关负载较轻，网关与外部网络可以正常通信，超过该阈值时说明负载较大，可能会在网关处发生拥塞；设置Metric差阈值 ，只有到邻簇网关的Metric与到当前网关的Metric的差值大于 时，才选择可能换簇，防止因为Metric值在切换后的波动引起节点 “乒乓切换”的可能。除了考虑网关负载和Metric外，也要考虑当前节点到换簇前后的两个网关节点的路径问题。

[0026] 本发明中的簇选择算法流程如图6所示：节点收到邻簇的RANN帧后运行簇选择算法，首先判断本节点到当前网关的路径是否有效，如果失效则立马换簇；如果没有失效则判断自己是否为叶子节点，非叶子结点不能换簇；叶子节点判断当前网关的负载和邻簇网关的负载是否都在负载阈值内，如果不在则预测换簇后邻簇网关负载是否小于负载阈值，是则换簇，否则不换簇；如果两个网关负载均在负载阈值内，判断节点到邻簇网关的Metric小于到当前网关Metric是否超过Metric差阈值且换簇后邻簇网关负载是否在负载阈值内，满足这两个条件则换簇，否则不换簇。

[0027] 以上所述，仅为本发明中的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉该技术的人在本发明所揭露的技术范围内，可理解想到的变换或替换，都应涵盖在本发明的包含范围之内，因此，本发明的保护范围应该以权利要求书的保护范围为准。