无线Mesh网网关节点动态选举算法研究

邹蕾

（吉林警察学院 信息工程系，吉林 长春 130000）

无线Mesh网网关节点动态选举算法研究

邹蕾

（吉林警察学院 信息工程系，吉林 长春 130000）

本文对无线Mesh网络的网关节点选举进行了分析研究.通过对无线Mesh网络结构的研究提出一种网关节点选举算法.该算法采用路由的机制确定了寻径结果.整个过程由三个部分组成：可用网关节点的发现、最优网关的选举、网关的维护.实验表明该算法具有优化、简洁、快速收签以及灵活的特性.

无线Mesh网；Ad Hoc网络；路由协议；网关选取

1 引言

无线Mesh网是Ad Hoc网络的一种特殊形态，通过802.11、802.16、20.3G等技术组合成多跳无线链路的无线Mesh.无线Mesh可对系统大面积无限覆盖，并且无线Mesh网络也对无限系统提供了高的可靠性和大容量的带宽.未来无线Mesh是一种先进的无线技术.传统的网络和无线Mesh网络是完全不同的网络.Mesh网络的核心思想是:INTERNET的架构采用无线Mesh网络设计的，在INTERNET网络中，用户位置主要在网络边缘，网络连接方式采用节点和路由器相连接，如果不同节点在链路失败后，路由器会采用通过其他路由的去寻找新的替代路径.

Mesh终端的设备一般采用手机，电脑和PAD等.每个不同的终端进行相互访问和连接构成P2P网络.无线Mesh网作为一种新型宽带无线接入技术备受学术界关注，逐渐成为下一代WMN的核心.

WMN的核心技术提供给通过无线技术提供给用连接无线网络.移动终端用户接入无线接入服务，当移动终端节点通过无线Mesh网接入Internet时，在无线Mesh网中需要找到可用的无线网关节点为其提供接入Mesh网络的服务，所以如何选取网关节点一直是该领域研究的关键问题.

2 无线Mesh网网关节点动态选举算法的设计与实现

这里设计用于无线Mesh网的网关节点动态选举算法，主要是采用共同的思路——访问网关.提出一种优化的网关选取算法.

根据无线Mesh网的有关特性，将网关节点动态选举算法的过程应该分为三个阶段:(1)可用网关节点的发现.(2)最优网关的选举.(3)网关的维护.

2.1 可用网关节点的发现

2.1.1 算法需要维护的数据结构

1.算法的概念描述与定义

(1)协议图G(V1,PV,E1,PE):通过G(V1,E1)在路由协议中表达网络拓扑结构.其中，节点集合用V1表示，V1在网络中表示网络接入点，边集合用EI表示，EI是无线链路，在网络的实际应用中，链路，节点之间在不同的环境总会出现失效，所以为了满足实际的需求，在协议图G中给边，节点赋概率值，形成协议图G.

（1）路径的可靠度，在协议图G中，目的和源节点通常采用单路径传输，边与节点之间乘积定义为单路径可靠度.

(2)传输路径:目的，源点之间进行传输的通信链路.

(3)路由耗时:到达传输路径一共消耗的时间.每项指标相加得到最后的耗时时间.

(4)路径轨迹:网络传输中记录的节点序号.

(5)传输时间数组:在路径的传输过程中，开始从节点I出发，到节点J为止，然后通过节点J 进行转发，最后得到的时间.

2.节点的数据结构设计

表1 节点结构

根据无线Mesh网的特性和结构，在本算法中模拟一个无线Mesh网络的节点结构.假设节点是作用在一个30×30范围的区域以内,设定在这个区域内一共有10个网络节点（节点用字符0、1、2、3、4、5、6、7、8、9表示），其中有8个网络节点被设定为移动节点（移动节点用字符0、1、2、3、4、5、6、7表示）和2个网络节点被设定为网关节点（节点用字符8、9表示）.移动节点具有移动性，它是可以任意移动的，它的移动范围是在30×30范围的区域之内；网关节点不具有移动性，它是以固定位置与无线Mesh网络中的骨干网相连，为了区别网络中的每个节点.节点所具有的结构如表1所示.

(1)节点位置:由于在WMN中具有GPS独立定位功能的只有MESH网络.该定位系统的误差在1秒钟之内不超过10米.为了在本文设定的30×30范围的区域以内精确的表示出节点的位置，用两个变量表示每个节点的坐标位置.

(2)网关标志位:网关标志位是用于节点是否是网关节点的.在无线Mesh网中，网关节点是以有线的方式与无线Mesh网的骨干网相连的，为了表示这个特殊的节点，用变量GW表示，当GW=1时证明该网络节点为网关节点.

3.路由请求消息列表

无线Mesh网中当移动节点为了寻找可用的网关节点而发起路由时，首先发送一个探测包，其中主要包括的就是RREQ（路由请求消息），该探测包的结构如表2所示:

表2 路由请求消息

(1)源节点标识符:源节点标识符由字符0～9表示，代表每个节点的名称.

(2)源节点地址:由节点位置（x，y）表示.

(3)网关节点标志:由于源节点要探测的是网关，由网关标志位（GW）表示.

(4)请求序列号:用于标识路由请求消息列表，由整数表示.

(5)发起的请求时间:源节点发起路由请求消息的起始时间.

4.路由表

无线Mesh网中每个节点的信息保存在路由表中，路由信息通过节点来保存.如果在路由器中发现新链路时，要把发现的新信息加入.通过路由算法实现分组发送找到路径.路由通过可节点的存储方式，可采用直接存储路由方式，路由表的结构如表3所示:

(1)源节点标识符:源节点标识符由字符0～9表示，代表每个节点的名称.

(2)源节点地址:由节点位置（x，y）表示.

(3)网关节点标志:由于源节点要探测的是网关，由网关标志位（GW）表示.

(4)请求序列号:用于标识路由请求消息列表，由整数表示.

(5)发起的请求时间:源节点发起路由请求消息的起始时间.

(6)终止请求时间:源节点发起路由请求后终止的时间.

(7)中间节点:每条路径中源节点与目标节点间接相连的节点，按顺序存储.

2.1.2 网关节点的发现过程

在本文中模拟10个节点的无线Mesh网络结构图1如下所示:

图1 模拟的无线Mesh网结构图

图2是自由无线Mesh网结构，用户节点，GW，SGW节点都是无线终端.在网关节点发现过程中，通过一个网关实现用户连接INTERNET网，若用户不在网关的范围内，网络会自动失效，客户需求重新选择一个网关连接INTERNET网.

在介绍移动节点探测之前先做如下假设:系统中各节点都执行同样的路由选择算法,初始化网络中各节点的路由表中路由大小初始值设为0.假设节点SRC_node为连接请求的源节点，连接请求的目的节点是网关.

第一阶段，SRC_node连接上网络.源节点SRC_node要向Internet发送数据时，它首先通过广播发送本地路由请求信息RREQ分组，每个节点发送RREQ分组都有一定的范围，这个范围由节点本身的探测器所决定，假定这个探测范围是一个定值，由表示.当SRC_node发送RREQ分组时后，在SRC_node节点为圆心以这个定值为半径的范围内，所有相邻节点都可以接到这个RREQ包.RREQ中包含以下信息:目标网关标志位等.

第二阶段，在探测距离范围内的相邻节点收到RREQ分组后，会选行判断自己的是不是网关节点，如果它不是网关节点，则会变成路径的中间节点，并且进行以下操作，通过轨迹数组记录节点标识；中间节点再重复第一阶段的内容以自己为圆心在探测范围内再次进行发送，查找网关节点.倘若在探测距离的范围内都没有其它的节点存在或RREQ这个消息丢失了，则源节点SRC_node没有发现到网关节点的路径，它会重新返回断开状态并重新发送路由请求信息.

第三阶段，当网关节点GW收到来自源节点SRC_node的RREQ分组后，根本自身的网关标志位GW进行判断，证明自己就是源节点想要找到的网关，实现就路由请求.

第四阶段，网关把相关信息进行封装，然后进行路由分组，主要包含，网关点地址，源序列号，路由耗时等.封装后，沿着原始传给源节点.

图2描述了上面讨论的路由发现的机制.

图2 路由发现机制

当路由器内部表发生改变，会及时把修改的状态通知相连接的路由器，保证了数据传输.如图3所示节点路由过程

图3 路由发现过程

2.2 最优网关的选举

通过上面的网关发现过程我们可以发现，源节点SRC_node收到从可用网关节点返回的RREP分组信息，即从当前的无线网络中找到可达的网关节点的路由信息，因为无线Mesh网络结构的复杂性以及网关节点可能会不止一个，所以在路由发现过程中所找到的可用路由信息和网关节点也可能会出现多个.由于网关的选举机制最终仅仅允许每个移动节点只能选择一个可用网关，所以就必须从这些可用的路由包中进行网关的选取.网关寻找过程中，节点收到从可用网关节点返回的应答信息RREP中查询到每个可用网关节点的参数信息，将这些参数信息按照在网关选取策略中占有的不同比例进行综合计算，并且最终算出一个计算结果，而这个计算结果就是这个可用网关节点的PRI（优先级）.公式如下所示:

公式中通过下面参数实现区分，选择路径指标:

1.路由大小:也是路径的长度，即路径的跳数，是路径上所经过各个节点的个数总和.源节点发起路由请求消息时，将路由大小=0，路由每经过一次，记录都写入路由记录中.进行累加.hop_percent是指路由大小在公式中所占的比例，本算法中hop_percent是给定的一个定值，hop_percent=10%.

2.可靠性:主要是了路由中链接依赖性，一般情况下网络链接失效较多，如果失效后，网络链接修复速度比较快.因为节点作用在无线Mesh网中具有移动性，该节点的可靠度也是未知的，所以在本文中出现的各个节点的可靠度被赋与一个随机值.stab_percent指路由可靠性在公式中所占的比例，本算法中stab_percent是给定的一个定值.stab_percent=40%.

3.带宽:指进行流通的链接容量.一般情况下，以太网链接中，10Mbps比64kbps更好.本文中出现的带宽bandwidth被赋与一个随机值.bandwidth_percent是指带宽在公式中所占的比例，本算法中bandwidth是给定的一个定值.bandwidth_percent=20%.

4.路由延迟:节点进行分组传输所花的时间.它由所决定，本文中的delay是一个随机值.delay_percent是路由延迟在公式中所占的比例，它是一个定值，delay_percent=10%.

5.等待队列（team）:指路径中正在等待的业务的数量.由网络状态所决定，所以本文中的team是一个随机值.team_percent是等待队列在公式中所占的比例，它是一个定值，team_percent=10%.

6.其它（other）:影响路由的其它因素，是一个随机值，other_percent是它在算法中的比例，是一个定值，other_percent=10%.

2.3 网关的维护

由于无线Mesh网中终端节点具有可移动性，所以网关节点路由中信息应进行及时的维护.

算法按照周期，发送一次探测包，查找是否有备用的网关节点，如果查找到可用的网关节点，那么重新执行网关节点的优化选取.否则重新进行可用网关的发现等全过程.

3 结束语

这种无线Mesh网的网关节点分成三个阶段:可用网关节点的发现、最优网关的选举以及网关节点的维护.可用网关节点的发现过程中实现了对网络结构中源移动节点对网关节点探测并发现的过程.最优网关的选举实现了从多个可用网关节点以及多条路径中优化选举出最适合的网关节点，并定期通过网关节点的维护实现路由表的更新.

总之，由于无线Mesh网络中节点的移动性以及链路的易受干扰性，使得数据易丢失，采用这种网关节点选举算法减少和克服这种缺点，是一种较好的解决办法.

〔1〕徐格，吴建平，徐明伟.高等计算机网络——体系结构、协议机制、算法设计与路由器技术[M].北京：机械工业出版社，2013.70-83.

〔2〕刘元安.未来移动通信系统概论[M].北京：北京邮电大学出版社，1999.

〔3〕Yigal Bejerano,Seung-Jae Han,Amit Kumar.Efficient load-balancing routing for wirelessmesh networks.Computer Networks.205.11-18.

〔4〕Ian F Akyildiz,Xudong Wang,Weilin Wang.Wireless mesh networks-a survey.Computer Networks.2015.1-9.

〔5〕Tsai-Wei Wu,Hung-Yun Hsieh.Interworking wireless mesh networks-Problems,performancecharacterization, and perspectives.JournalofParalleland Distributed Computing.2014.5-12.

TP301.6

A

1673-260X（2017）02-0022-03

2016-10-21

2016年度吉林省高校科学技术和人文社会科学研究规划项目（2016ZCY266）