2024年4月26日发(作者：)

第３３卷第２期（下）　

２０１７年２月　

赤峰学院学报（自然科学版）　

Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈｉｆｅｎｇ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　

Ｖ０１．３３Ｎｏ．２　

Ｆｅｂ．２０１７　

无线Ｍｅｓｈ网网关节点动态选举算法研究　

邹　蕾　

（吉林警察学院

摘

信息工程系，吉林长春１３００００）　

要：本文对无线Ｍｅｓｈ网络的网关节点选举进行了分析研究．通过对无线Ｍｅｓｈ网络结构的研究提出一种网关节点选　

举算法．该算法采用路由的机制确定了寻径结果．整个过程由三个部分组成：可用网关节点的发现、最优网关的选举、网关的维　

护．实验表明该算法具有优化、简洁、快速收签以及灵活的特性．　

关键词：无线Ｍｅｓｈ网；Ａｄ　Ｈｏｃ网络；路由协议；网关选取　

中图分类号：ＴＰ３０１．６　文献标识码：Ａ　文章编号：１６７３—２６０Ｘ（２０１７）０２—００２２—０３　

１　引言　

１．算法的概念描述与定义　

（１）协议图ＧｆＶ１，ＰＶ，Ｅ１，ＰＥ）：通过Ｇ（Ｖ１，Ｅ１）在路由协　无线Ｍｅｓｈ网是Ａｄ　Ｈｏｃ网络的一种特殊形态，通过　

８０２．１　１、８０２．１６、２０．３Ｇ等技术组合成多跳无线链路的无线　

Ｍｅｓｈ．无线Ｍｅｓｈ可对系统大面积无限覆盖，并且无线Ｍｅｓｈ　

网络也对无限系统提供了高的可靠性和大容量的带宽．未来　

无线Ｍｅｓｈ是一种先进的无线技术．传统的网络和无线Ｍｅｓｈ　

网络是完全不同的网络．Ｍｅｓｈ网络的核心思想是：ＩＮＴＥＲ—　

ＮＥＴ的架构采用无线Ｍｅｓｈ网络设计的，在ＩＮＴＥＲＮＥＴ网络　

议中表达网络拓扑结构．其中，节点集合用ｖ１表示，ｖ１在网　

络中表示网络接入点，边集合用ＥＩ表示，ＥＩ是无线链路，在　

网络的实际应用中，链路，节点之间在不同的环境总会出现　

失效，所以为了满足实际的需求，在协议图Ｇ中给边，节点　

赋概率值，形成协议图Ｇ．　

（１）路径的可靠度，在协议图Ｇ中，目的和源节点通常　

采用单路径传输，边与节点之间乘积定义为单路径可靠度．　

（２）传输路径：目的，源点之间进行传输的通信链路．　

（３）路由耗时：到达传输路径一共消耗的时间．每项指标　

相加得到最后的耗时时间．　

（４）路径轨迹：网络传输中记录的节点序号．　

（５）传输时间数组：在路径的传输过程中，开始从节点Ｉ　

出发，到节点Ｊ为止，然后通过节点Ｊ进行转发，最后得到　

的时间．　

中，用户位置主要在网络边缘，网络连接方式采用节点和路　

由器相连接，如果不同节点在链路失败后，路由器会采用通　

过其他路由的去寻找新的替代路径．　

Ｍｅｓｈ终端的设备一般采用手机，电脑和ＰＡＤ等．每个　

不同的终端进行相互访问和连接构成Ｐ２Ｐ网络．无线Ｍｅｓｈ　

网作为一种新型宽带无线接人技术备受学术界关注，逐渐　

成为下一代ＷＭＮ的核心．　

ＷＭＮ的核心技术提供给通过无线技术提供给用连接　

无线网络．移动终端用户接入无线接入服务，当移动终端节　

点通过无线Ｍｅｓｈ网接入Ｉｎｔｅｍｅｔ时，在无线Ｍｅｓｈ网中需要　

２．节点的数据结构设计　

根据无线Ｍｅｓｈ网的特性和结构，在本算法中模拟一个　

无线Ｍｅｓｈ网络的节点结构．假设节点是作用在一个３０×３０　

范围的区域以内，设定在这个区域内一共有ｌＯ个网络节点　

找到可用的无线网关节点为其提供接人Ｍｅｓｈ网络的服务，　

所以如何选取网关节点一直是该领域研究的关键问题．　

２无线Ｍｅｓｈ网网关节点动态选举算法的设计与实现　

（节点用字符０、１、２、３、４、５、６、７、８、９表示），其中有８个网　

络节点被设定为移动节点（移动节点用字符０、１、２．３…４　５　

６、７表示）和２个网络节点被设定为网关节点（节点用字符　

８、９表示）．移动节点具有移动性，它是可以任意移动的，它的　

这里设计用于无线Ｍｅｓｈ网的网关节点动态选举算法，　

主要是采用共同的思路——访问网关．提出一种优化的网关　

选取算法．　

根据无线Ｍｅｓｈ网的有关特性，将网关节点动态选举算　

法的过程应该分为三个阶段：（Ｉ）可用网关节点的发现．ｆ２）最　

优网关的选举．（３）网关的维护．　

２．１可用网关节点的发现　

移动范围是在３０×３０范围的区域之内；网关节点不具有移动　

表１节点结构　

数据项名称　

节点位置ｘ，Ｙ）　

２．１．１算法需要维护的数据结构　

网关标志位（Ｇ　

收稿日期：２０１６～１０—２１　

基金项目：２０１６年度吉林省高校科学技术和人文社会科学研究规划项目（２０１６ＺＣＹ２６６）　

一

２２—　

性，它是以固定位置与无线Ｍｅｓｈ网络中的骨干网相连，为了　

区别网络中的每个节点．节点所具有的结构如表１所示．　

（１）节点位置：由于在ＷＭＮ中具有ＧＰＳ独立定位功能　

的只有ＭＥＳＨ网络．该定位系统的误差在１秒钟之内不超　

过１０米．为了在本文设定的３０×３０范围的区域以内精确　

的表示出节点的位置，用两个变量表示每个节点的坐标位　

置．　

（２）网关标志位：网关标志位是用于节点是否是网关节　

点的．在无线Ｍｅｓｈ网中，网关节点是以有线的方式与无线　

Ｍｅｓｈ网的骨干网相连的，为了表示这个特殊的节点，用变量　

ＧＷ表示，当ＧＷ＝Ｉ时证明该网络节点为网关节点．　

３．路由请求消息列表　

无线Ｍｅｓｈ网中当移动节点为了寻找可用的网关节点　

而发起路由时，首先发送一个探测包，其中主要包括的就是　

ＲＲＥＱ（路由请求消息），该探测包的结构如表２所示：　

表２路由请求消息　

数据项名称　

源节点标识符　

源节点地址　

网关节点标志　

请求序列号　

数据项名称　

发起的请求时间　

（１）源节点标识符：源节点标识符由字符０－９表示，代表　

每个节点的名称．　

（２）源节点地址：由节点位置（ｘ，ｙ）表示．　

（３）网关节点标志Ｉ由于源节点要探测的是网关，由网关　

标志位（Ｇｗ）表示．　

（４）请求序列号：用于标识路由请求消息列表，由整数表示．　

（５）发起的请求时间：源节点发起路由请求消息的起始　

时间．　

４．路由表　

无线Ｍｅｓｈ网中每个节点的信息保存在路由表中，路由　

信息通过节点来保存．如果在路由器中发现新链路时，要把　

发现的新信息加入．通过路由算法实现分组发送找到路径．　

路由通过可节点的存储方式，可采用直接存储路由方式，路　

由表的结构如表３所示：　

（１）源节点标识符：源节点标识符由字符０￣９表示，代表　

每个节点的名称．　

（２）源节点地址：由节点位置（ｘ，ｙ）表示．　

（３）网关节点标志：由于源节点要探测的是网关，由网关　

标志位（ＧＷ）表示．　

（４）请求序列号：用于标识路由请求消息列表，由整数表示．　

（５）发起的请求时间：源节点发起路由请求消息的起始　

时间．　

（６）终止请求时间：源节点发起路由请求后终止的时间．　

（７）中间节点：每条路径中源节点与目标节点间接相连　

的节点，按顺序存储．　

２．１．２网关节点的发现过程　

在本文中模拟１Ｏ个节点的无线Ｍｅｓｈ网络结构图１如　

下所示：　

ＳｕｐｅｒＧａｔｅｗａｙＮｏｄｅ　

图１模拟的无线Ｍｅｓｈ网结构图　

图２是自由无线Ｍｅｓｈ网结构，用户节点，ＧＷ，ＳＧＷ节　

点都是无线终端．在网关节点发现过程中，通过一个网关实　

现用户连接ＩＮＴＥＲＮＥＴ网，若用户不在网关的范围内，网络　

会自动失效，客户需求重新选择一个网关连接ＩＮＴＥＲＮＥＴ　

网．　

在介绍移动节点探测之前先做如下假设：系统中各节　

点都执行同样的路由选择算法，初始化网络中各节点的路由　

表中路由大小初始值设为０．假设节点ＳＲＣ＿ｎｏｄｅ为连接请　

求的源节点，连接请求的目的节点是网关．　

第一阶段，ＳＲＣ—ｎｏｄｅ连接上网络．源节点ＳＲＣ＿ｎｏｄｅ要　

向Ｉｎｔｅｍｅｔ发送数据时，它首先通过广播发送本地路由请求　

信息ＲＲＥＱ分组，每个节点发送ＲＲＥＱ分组都有一定的范　

围，这个范围由节点本身的探测器所决定，假定这个探测范　

围是一个定值，由表示．当ＳＲＣ＿ｎｏｄｅ发送ＲＲＥＱ分组时后，　

在ＳＲＣ—ｎｏｄｅ节点为圆心以这个定值为半径的范围内，所有　

相邻节点都可以接到这个ＲＲＥＱ包．ＲＲＥＱ中包含以下信　

息：目标网关标志位等．　

第二阶段，在探测距离范围内的相邻节点收到ＲＲＥＱ　

分组后，会选行判断自己的是不是网关节点，如果它不是网　

关节点，则会变成路径的中间节点，并且进行以下操作，通　

过轨迹数组记录节点标识；中间节点再重复第一阶段的内　

容以自己为圆心在探测范围内再次进行发送，查找网关节　

点．倘若在探测距离的范围内都没有其它的节点存在或　

ＲＲＥＱ这个消息丢失了，则源节点ＳＲＣ＿ｎｏｄｅ没有发现到网　

关节点的路径，它会重新返回断开状态并重新发送路由请　

求信息．　

第三阶段，当网关节点ＧＷ收到来自源节点ＳＲＣ—ｎｏｄｅ　

的ＲＲＥＱ分组后，根本自身的网关标志位ＧＷ进行判断，证　

明自己就是源节点想要找到的网关，实现就路由请求．　

第四阶段，网关把相关信息进行封装，然后进行路由分　

组，主要包含，网关点地址，源序列号，路由耗时等．封装后，　

沿着原始传给源节点．　

图２描述了上面讨论的路由发现的机制．　

一

２３—　

图２路由发现机制　

当路由器内部表发生改变，会及时把修改的状态通知　

相连接的路由器，保证了数据传输．如图３所示节点路由过　

程　

图３路由发现过程　

２．２最优网关的选举　

通过上面的网关发现过程我们可以发现，源节点　

ＳＲＣ　ｎｏｄｅ收到从可用网关节点返回的ＲＲＥＰ分组信息，即　

从当前的无线网络中找到可达的网关节点的路由信息，因　

为无线Ｍｅｓｈ网络结构的复杂性以及网关节点可能会不止　

一

个，所以在路由发现过程中所找到的可用路由信息和网　

关节点也可能会出现多个．由于网关的选举机制最终仅仅允　

许每个移动节点只能选择一个可用网关，所以就必须从这　

些可用的路由包中进行网关的选取．网关寻找过程中，节点　

收到从可用网关节点返回的应答信息ＲＲＥＰ中查询到每个　

可用网关节点的参数信息，将这些参数信息按照在网关选　

取策略中占有的不同比例进行综合计算，并且最终算出一　

个计算结果，而这个计算结果就是这个可用网关节点的ＰＲＩ　

（优先级）．公式如下所示：　

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

１．路由大小：也是路径的长度，即路径的跳数，是路径上　

所经过各个节点的个数总和．源节点发起路由请求消息时，　

将路由大小＝０，路由每经过一次，记录都写入路由记录中．　

进行累加．ｈｏｐ＿ｐｅｒｃｅｎｔ是指路由大小在公式中所占的比例，　

本算法中ｈｏｐ＿ｐｅｒｃｅｎｔ是给定的一个定值，ｈｏｐ＿ｐｅｒｃｅｎｔ＝１０％．　

２．可靠性：主要是了路由中链接依赖性，一般情况下网　

络链接失效较多，如果失效后，网络链接修复速度比较快．　

因为节点作用在无线Ｍｅｓｈ网中具有移动性，该节点的可靠　

度也是未知的，所以在本文中出现的各个节点的可靠度被　

赋与一个随机值．ｓｔａｂ＿ｐｅｒｃｅｎｔ指路由可靠性在公式中所占　

的比例，本算法中ｓｔａｂ＿ｐｅｒｃｅｎｔ是给定的一个定值．ｓｔａｂ

＿

ｐｅ卜　

ｃｅｎｔ＝４０％．　

３．带宽：指进行流通的链接容量．一般情况下，以太网链　

一

２４一　

接中，１０Ｍｂｐｓ比６４ｋｂｐｓ更好．本文中出现的带宽ｂａｎｄｗｉｄｔｈ　

被赋与一个随机值．ｂａｎｄｗｉｄｔｈ＿ｐｅｒｃｅｎｔ是指带宽在公式中所　

占的比例，本算法中ｂａｎｄｗｉｄｔｈ是给定的一个定值．ｂａｎｄ—　

ｗｉｄｔｈ

＿

ｐｅｒｃｅｎｔ＝２０％．　

４．路由延迟：节点进行分组传输所花的时间．它由所决　

定，本文中的ｄｅｌａｙ是一个随机值．ｄｅｌａｙ＿ｐｅｒｃｅｎｔ是路由延迟　

在公式中所占的比例，它是一个定值，ｄｅｌａｙ＿ｐｅｒｃｅｎｔ＝１０％．　

５．等待队列（ｔｅａｍ）：指路径中正在等待的业务的数量．由　

网络状态所决定，所以本文中的ｔｅａｍ是一个随机值．　

ｔｅａｍ

＿

ｐｅｒｃｅｎｔ是等待队列在公式中所占的比例，它是一个定　

值，ｔｅａｍ　ｐｅｒｃｅｎｔ＝１０％．　

６．其它ｏｔｈｅｒ）：影响路由的其它因素，是一个随机值，　

ｏｔｈｅｒ

＿

ｐｅｒｃｅｎｔ是它在算法中的比例，是一个定值，ｏｔｈｅｒ　ｐｅｒ—　

ｃｅｎｔ＝１０％．　

２．３网关的维护　

由于无线Ｍｅｓｈ网中终端节点具有可移动性，所以网关　

节点路由中信息应进行及时的维护．　

算法按照周期，发送一次探测包，查找是否有备用的网　

关节点，如果查找到可用的网关节点，那么重新执行网关节　

点的优化选取　否则重新进行可用网关的发现等全过程．　

３结束语　

这种无线Ｍｅｓｈ网的网关节点分成三个阶段：可用网关　

节点的发现、最优网关的选举以及网关节点的维护．可用网　

关节点的发现过程中实现了对网络结构中源移动节点对网　

关节点探测并发现的过程．最优网关的选举实现了从多个可　

用网关节点以及多条路径中优化选举出最适合的网关节　

点，并定期通过网关节点的维护实现路由表的更新．　

总之，由于无线Ｍｅｓｈ网络中节点的移动性以及链路的　

易受干扰性，使得数据易丢失，采用这种网关节点选举算法　

减少和克服这种缺点，是一种较好的解决办法．　

参考文献：　

（１］徐格，昊建平，徐明伟．高等计算机网络——体系结构、协　

议机制、算法设计与路由器技术［Ｍ】．北京：机械工业出版　

社．２０１３．７０—８３．　

［２］刘元安．未来移动通信系统概论【Ｍ】．北京：北京邮电大学　

出版社．１９９９．　

［３］ＹＪ【ｇａｌ　Ｂｅｊｅｒａｎｏ，Ｓｅｕｎｇ－ｊａｅ　Ｈａｎ，Ａｍｉｔ　Ｋｕｍａｒ．Ｅｆｆｉｃｉｅｎｔ　

ｌｏａｄ—ｂａｌａｎｃｉｎｇ　ｒｏｕｔｉｎｇ　ｆｏｒ　ｗｉｒｅｌｅｓｓ　ｍｅｓｈ　ｎｅｔｗｏｒｋｓ．　

Ｃｏｍｐｕｔｅｒ　Ｎｅｔｗｏｒｋｓ．２０５．１１—１８．　

［４］Ｉａｎ　Ｆ　Ａｋｙｉｌａｉｚ，Ｘｕｄｏｎｇ　Ｗａｎｇ，ＷｅＲｉｎ　Ｗａｎｇ．Ｗｉｒｅｌｅｓｓ　

ｍｅｓｈ　ｎｅｔｗｏｒｋｓ　—ａ　ｓｕｒｖｅｙ．Ｃｏｍｐｕｔｅｒ　Ｎｅｔｗｏｒｋｓ．　

２０１５．１—９．　

［Ｓ］Ｔｓ￣一Ｗｅｉ　Ｗｕ，Ｈｕｎｇ—Ｙｕｎ　Ｈｓｉｅｈ．Ｉｎｔｅｒｗｏｒｋｉｎｇ　ｗｉｒｅｌｅｓｓ　

ｍｅｓｈ　ｎｅｔｗｏｒｋｓ—Ｐｒｏｂｌｅｍｓ，ｐｅｒｆｏｒｍａｎｃｅ　ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ，　

ａｎｄ　ｐｅ￣ｐｅｃｉｆｖｅｓ．Ｊｏｕｒｎａｌ　ｏｆ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　

Ｃｏｍｐｕｔｉｎｇ．２０１４．５—１２．