一种无线mesh网络下的可靠路由查询机制

倪仲余，黎忠文，董露阳

(1.西华大学 数学与计算机学院，四川 成都 610039;2.成都大学 计算机学院，四川 成都 610106)

0 引 言

无线mesh 网络(wireless mesh networks，WMNs)被广泛认为是解决“最后一公里”问题上非常合适的新型网络，它结合了WLAN 和ad hoc 网络的优势，采用多跳的路由转发方式来实现数据通信，是一种在传输上具有稳定、高容量以及高速率的分布式网络［1］.WMNs 的主要组成部分包括mesh 路由(mesh routers，MRs)和mesh 客户端(mesh clients，MCs).MRs 一般由处理能力较强的路由器来担任，它具有数据接收、转发和网关功能［2］.而MCs 同样也具有路由转发功能，但相比于MRs，其多接口性和处理能力MCs 则要弱很多，MCs 一般由手机、PDA、PC等设备组成.WMNs 的拓扑结构如图1 所示.

图1 WMNs 拓扑结构示意图

一般情况下，MRs 是静止且有持续的电源供应，通常把MR 之间通过无线方式连接形成的网络结构称为主干网［3］;MCs 则通过连接主干网的方式来完成所需要的信息服务.这相对于有线网络铺设线路长、难度大的缺点来说无疑是巨大的进步.

Chord 协议是对等覆盖网络(peer-to-peer，P2P)中应用非常广泛的算法［4］，其基于分布式哈希表的思路，把网络中的节点和信息资源哈希成惟一的节点标识ID，并按照从小到大以顺时针的方式进行排列成一个逻辑环.资源关键字KEY 则保存在大于或等于标识符ID 的第一个节点中，称为后继节点successor(K).Chord 采用贪婪查询方式对顺时针方向上架设在逻辑拓扑环的节点关键字KEY 进行资源查找和快速定位，从而完成数据通信.目前，对于Chord 算法的研究大多以降低查询跳数和时延为度量进行研究［5］，但这2 种方案在Chord 中都引入了泛洪机制，对网络开销造成一定的浪费［6］.此外，可通过对原始Chord 单路径的问题进行改进，采用并发方式的多路径查询策略，根据节点的响应时间选择相应的下一跳，从而减少查询时延和提高可靠性［7］，也可通过信誉度来选择更可靠的节点完成路由跳转和通信，并对节点信誉值的改变更新覆盖网络，从而提高节点对传输可靠度［8－10］.在此基础上，本研究对Chord 的高速率传输与可靠性2 个问题进行考量，设计了一种高效的多路径路由查询机制，同时，基于Chord 快速查找的优点，本研究对所架设的WMNs覆盖网络引入Chord 查询机制来完成资源的快速定位，通过添加反向查询和可靠多路径查询以应对节点失效或链路异常的问题，从而提高在节点失效或链路异常情况下的通信成功率.

1 网络结构模型

本研究将WMNs 网络中的MRs 和MCs 进行分层，将主干层的节点对应于WMNs 覆盖网络中的主干网MRs，叶子层由MCs 及其所连接的MR 组成.对于无论是主干层还是叶子层的节点都基于分布式哈希算法得到其所在空间环域的惟一标识.在Chord 环中的每个节点都会维持在一张路由表(Finger Table)，假设每个标识符大小为m 位，N 为Chord环中的节点个数，则其所在的环域规模大小为2 m，该环域中的节点能够维护数目为m 的路由表项［11］.Chord 中的节点在查找目的节点前首先会检查自身Finger 表是否有保存该资源的后继节点，有则取出数据资源并结束查找;若无，则跳转至Finger表中离标识符ID 最近的节点然后重复查找，直到取出数据资源后完成.由于原始Chord 协议是按顺时针方向的单向查询，当节点处于后半环时，查询效率不高.为了提高查询效率，本研究对Chord 协议进行优化，增加其逆时针方向的查询方法.令C.Finger［i］表示节点顺时针方向上第i 项后继节点，B.Finger［i］表示节点逆时针方向上的第i 项后继节点，则Chord 环的双向路由表项可表示为，

在所建立的WMNs 主干层和叶子层网络上，本研究对不同层次的网络节点分别采取不同的命名方式.由于主干网中的MRs 都是叶子层网络的环首节点并拥有优秀的处理能力，所以主干层中的MRs 除了要维护自身主干区域的路由表外，还需要维护与其相关的叶子节点的路由信息，故环首节点将维护2 个路由表.在对叶子层节点进行哈希分配资源标识的过程中，首先查看叶子节点属于哪一个叶子环，然后结合叶子节点的实际物理拓扑情况进行分配.对于叶子层上的节点，其所分配的标识符由2 部分组成:一部分通过对节点IP 地址前半部一定位数进行哈希分配得到，节点根据判断前半部的资源标识可以知道叶子节点从属于哪个主干节点;另一部分则是对IP 地址的后半部进行哈希分配得到，由这部分的标识符来判断节点属于哪个叶子层环域.对于2 个不同节点，通过这种分配方式的查看可以得出2个节点是否属于同一叶子环.图2 为分层Chord 简易模型.

图2 分层Chord 模型示意图

2 可靠路由查询与性能分析

2.1 可靠度描述

在WMNs 中，可把主干网的MRs 当成一个集合E，因为MR 具有稳定性和强大的处理能力，所以在网络中的节点只要考虑成功连接其中的一个MR 即可有效地完成路由通信.根据这个思路，本研究对呼叫节点连接到主干网中的任一MR 的可靠度做如下定义.

定义1 1/E 路径集合P(s，E):从呼叫节点s到接收节点集合E 的最小路径集合，表示为，

P(s，E)=∪{P(s，et)，et∈E}.

定义2 Rel1/E(s，E):呼叫节点s 连通到集合E中任一MR 的概率.

定理1 s 到et的2-路径最大可靠度小于或等于1/E 路径可靠度，当E=1 时等式成立［6］.

证明 当E =1 时，Rel1/E(s，E)与2-路径可靠度的接收节点和路径相同，所以等式成立.当E ＞1时，P(s，et)⊂P(s，E)，所以P(s，E)可以考虑更多的路径来计算可靠度，故P(s，E)可靠度更高.

证毕.

2.1.7 锌。2012年全市叶片锌平均含量为32.49 mg/kg(表1)，说明锌的含量在较适中的范围。锌在苹果营养生长和生殖生长中起到调节激素的作用，同时对花粉管生长起到重要作用，锌也能影响果树的抗冻性和花对霜冻的抵抗力。磷/锌比值应该是100或更低，高 pH、高磷酸盐、高有机质和低温均降低土壤锌的有效性。在缺乏时，叶片喷施螯合态锌最有效 。

定理2 假如可用度P(α)≥P(β)≥P(λ)，路径α 与β 相关链路数|α∩β| ＜|α∩λ|，|β| = |λ|，Relαβ=P(α)+P(β)，Relαλ=P(α)+P(λ)，则Relαβ＞Relαλ［11］.

证明 令|α| =p，|β| = |λ| =q，|α∩β| =i，|α∩λ| =j，则i ＜j.因为，0 ＜r ＜1，所以，ri＜rj，得出rp－i＜rp－j.又因为，

Relαλ=P(α)+P(λ)=rp+rq(1－rp－j)，所以，

证毕.

从定理2 可以知道，相同链路数的2 条路径相关性越低则越可靠.

2.2 路由集合选择

由定理1 与定理2 可知，在搭建的WMNs 覆盖网络中选择路径时，只需要考虑连接到主干网的任一MR 即可，同时在选择的路径集合中尽量选择相关链路最少的路径作为候选.根据这个条件，假设PN(s，E)表示s 节点到主干网络中任一MR 的含N条路径的集合，E 表示骨干节点的集合.在叶子层可能存在的节点异常情况下，通过使用可靠性路由查找完成对主干网络节点的可靠连接.路由集合选择的具体步骤如下:

2)假设L 为得到的路径总数，且li∈L，(i =1，2，…，N).计算在L 中含有N 条路径的组合数，每个组合对应一个查询路集.

3)利用式(3)，对每个组合中的N 条路径随机安排顺序，进行可靠度计算，

4)把可靠度最高的组合对应的查询路集作为可靠查找方案.

5)整理查询路集中的路径，将可用度最高的路径设置为第一路径lh.

6)对于余下的N-1 条路径，根据定理2 选出与路径lh链路相同且链路相关性|ln∩li|由小到大的路径进行排序.

2.3 路由查询方案

在路由查询过程中，每个节点通过保存的Finger 表信息来进行资源定位和路由跳转.采用双向的查询模式可以让节点根据资源标识在所处的环域中更快地获取.同时，对于节点异常或链路失效等情况将触发可靠度机制继续查询.由于主干网中MRs 具有强大的资源存储与处理能力，所以在查询过程只要能够成功地连接到主干网即可完成查询.本路由查询算法的具体步骤如下:

1)当网络中的节点s 请求呼叫查询时，首先判断所要查询的信息是否处于所属MR 中.

2)启用Chord 双向路由查询模式寻找所属MR，并确认是否成功收到应答消息，若成功转步骤3);否则转步骤5).

3)若查询资源处于所属MR，则取出资源，转步骤6);否则转步骤4).

4)在主干网络中利用Chord 双向路由查询定位存储该资源的MR，转步骤6).

5)触发可靠度多路径选择机制，进入主干网络.判断是否成功，是则转步骤8);否则转步骤7).

6)完成查找，不做任何更新.

7)查找失败，转步骤8).

8)更新网络.

2.4 性能分析

由于原始Chord 协议构建的逻辑环中未考虑到实际物理拓扑结构，造成网络中相邻的节点需要完成更多的路由跳转来实现通信，浪费不必要的开销.所以本研究通过改进的Chord 协议在所架设的WMNs 覆盖网络中考虑到实际的物理拓扑结构，将本地物理相近的节点保存到逻辑Chord 环的路由表中，避免相近节点在查询过程中出现绕路的情况.同时，基于原始Chord 只能在顺时针方向上对逻辑环中节点进行查找的不足，增加逆时针方向节点的查询策略，使得当查询节点处于后半环时也能完成快速地定位.这样的改进能很好地降低时间复杂度O(log2N)，在规模较大的网络具有更高效的数据传输.

在WMNs 中，节点的性能与处理能力影响着节点传输的成功率，节点的崩溃和链路异常等情况使得拥有单路径传输的Chord 协议无法完成可靠的路由跳转.在原始Chord 协议中添加可靠的多路径查询可以有效地弥补实时查询的缺点，而路径的相关性则能够优化可靠路集中路径顺序的排列，提高路集的可靠度，增加数据传输的成功率.所以改进的机制相比原始Chord 协议更具有优越性，能够很好地适用于WMNs 覆盖网络实现高效的数据传输.

3 结 论

将P2P 的查询模式应用于无线mesh 网络已经成为了一种趋势.本研究基于Chord 协议，设计了分层次和双向查找的模式，并针对无线mesh 网络节点、链路易失效的问题加入了可靠多路径查询方式，提高了节点的查询效率和查询可靠度.在下一步的研究工作中，如何有效地平衡网络查询过程中的QoS，从而使数据传输获得高效性和可靠性将是无线mesh 网络需要致力于解决的问题.

［1］Akyildiz I F，Wang X D.A survey on wireless mesh networks［J］.IEEE Radio Communications，2005，47(4):445－487.

［2］Wang X D，Lin A O.IEEE 802.11s wireless mesh networks:Framework and challenges［J］.Ad Hoc Networks，2008，6(6):970－984.

［3］Karrer R P，Botta A，Pescape A.High-speed backhaul networks:myth or reality?［J］.Computer Communications，2008，31(8):1540－1550.

［4］张震，王晓明.对等网中Chord 资源查找算法的研究［J］.计算机工程与应用，2006，41(11):147－153.

［5］龙建辉，陈靖，朱清超，等.LPDSR:基于Chord 算法的MANET 分级路由模型［J］.计算机工程与设计，2014，35(9):2981－2985.

［6］李文翔，沈元平，吴静，等.无线mesh 网中可靠SIP 呼叫连接的选路技术［J］.计算机科学，2011，38(4):130－132.

［7］宗平，徐鸽.基于DHT 的Chord 路由算法改进［J］.计算机技术与发展，2012，22(9):139－142.

［8］王宏林，朱艳琴.基于信任管理的对等网络路由选择［J］.计算机应用，2009，29(3):669－674.

［9］汪发宝.P2P 网络Chord 协议的分析与研究［D］.成都:西南交通大学，2010.

［10］Brito P H，de Lemos R，Rubira C M，et al，Architecting fault tolerance with exception handing:verification and validation［J］.Journal of Computer Science and Technology，2009，24(2):212－237.

［11］胡建军，王学毅，范彬.一种网路可靠性的多路径路由算法［J］.小型微型计算机系统，2014，35(8):1780－1783.