基于负载感知的网关选择的低成本的WMNs路由

沈宇春, 刘晓霞

(1. 呼和浩特职业学院 计算机信息学院，内蒙古 呼和浩特 010051;2. 四川水利职业技术学院 信息工程系,四川崇州 611231)

0 引 言

与多跳移动自组织网络(Multi-hop Mobile Ad-hoc Network, MANET)不同，无线网状网络 (Wireless Mesh Networks，WMNs)[1]具有相对静止结构和低移动特点，其是有线和无线网络的结合体。具体而言，WMNs以无线Mesh路由(MRs)为主干网，以移动点为用户终端。用户通过MRs转发消息，并利用网关(GWs)连通Internet。

在单一GWs的WMNs中，GW选择问题变得非常简单。确实，所有上行或下行流量均通过同一个GW连通Internet。因此，GW可能成为网络的瓶颈[2]。为了消除此问题，引用多个GWs分担负载，并提高网络性能。然而，只单方面地提高GWs数量并不一定能增加WMNs的容量。事实上，网络容量与网络连通率、GWs位置更相关。信号干扰和GWs的拥塞情况对WMNs性能也有消极的影响。为了改善WMNs的网络性能，研究人员采用了不同的方案策略[2-5]。

此外，WMNs的网络性能也受路由策略的影响。不同的路由指标，对路由有不同的影响。通常，良好的路由指标应不降低网络稳定性，同时，也隐含了Mesh网络特性。

网络稳定是多数网络的主要性能指标。当网络不稳定，重建路由的频率就会增加。这个增加是由于多条链路质量过低导致的，低质量的链路会导致路由翻转，最终降低网络性能。确实，不稳定(频繁地路由翻转)可能会导致传递失序、高扰动、数据包丢失、高时延。

为此，提出基于路径成本和概率-网关的WMNs路由PCPG。PCPG路由从路径成本和网关两个角度决策路由。首先，通过期望链路质量、干扰率计算路径成本，然后，再依据网关负载计算选择网关的概率，进而构建稳定路由。实验数据表明，提出的PCPG路由能够有效地控制时延、并提高了吞吐量。

1 PCPG路由

考虑多跳WMNs，将节点分为两类：MRs和GWs。MRs形成多跳无线主干网，完成用户与Internet间的流量传输。为了将流量传输至Internet，流量需通过网关传输。每个MR装备了多个无线接口，且每个接口上具有多个信道。假定MR的接口有多个不同的信道。

多跳WMNs由MRs和GWs构成，MRs构成主干网，且完成用户与Internet间的流量传输，而GWs连通Internet。整个WMNs要看成图G=(V,E)，其中V为节点集(MRs和GWs)，E为链路集。令ij表示两个MRs(υi、υj)间的链路，且υi、υj∈V。

PCPG路由从路由成本角度选择路由，并且路由成本包含了链路质量、干扰以及网关信息，有利于路由的稳定。

1.1 期望链路质量

期望链路质量(Expected Link Quality, ELQ)类似于ETX，但优于ETX。ETX是基于正向链路与反向链路具有相同的数据传递率，然而，实际上，正向链路与反向链路的传递率并不相同[6]。为此，本文引用的ELQ只包含正向链路的传递率。

为了更好地理解正向、反向链路以及ETX的问题，用图1进行举例说明。图1中的df、dr分别表示正、反链路的传递率。依据ETX的假设条件，正向链路A→B与反向链路B→A具有相同数据传递率。而实际上，通常是利用探测包ACKs估计、反向传递率，然而数据包尺寸远大于ACKs的尺寸。换而言之，探测包ACKs对低质量链路具有更强的鲁棒性。此外，由于反向链路dr只考虑了ACKs，它在估计链路质量方面上的重要性远低于df。

图1 正、反向链路质量

因此，本文不再引用ETX估计链路质量[7]，而是ELQ，其定义如下：

(1)

从式(1)可知，ELQ只考虑了正向链路的传递率。这有利用于快速测量链路质量。

1.2 干扰率IR

数据传输不仅受到链路质量的影响，同时，也受到同信道的干扰影响[8]。为此，引用干扰率(Interference Ratio, IR)。从节点S至节点R链路的IR可定义为：

(2)

其中PR(S)表示R接收的信号功率、N为背景噪声，ψ表示干扰节点R的节点集。PR(k)表示干扰节点k的干扰功率。

而Pmax表示接收节点可容忍的最大干扰，定义如式(3)：

(3)

其中T是信号功率阈值。当传输信号的SINR大于T，才认为此成功传输此信号。

最后，利用ELQ和IR估计链路成本(Link Cost，LC)。信道i上的链路l的链路质量LC可表示为[9]：

(4)

其中n表示共享同一信道i的一跳邻居数。

1.3 路径成本

接下来，计算路径成本。由第r个MR至第g个GW的路径pr→g的路径成本 (Path Cost，PC)PCr→g：

(5)

式(5)的右边有两项信息，都是与链路质量LC相关。若只用右边第二项，则不能充分反映路径质量。

图2 路径成本示意图

1.4 网关选择

在WMNs中，数据流是通过网关GWs流入Internet。因此，网关传输数据时的稳定性对整个数据流传输的流畅性起着关键的作用[8]。为此，需要选择最合适的GW。本文选择基于概率策略去选择GWs。

假定每个GW先广播网关通告消息(Gateways Advertisement Messages, GWADV)。GWADV的消息格式如表1所示。

表1 GWADV格式

其中idM为消息的id，而idG为广播GWADV的身份。Iface为接口，Load表示其负载。

(6)

其中ρ为控制参数，且ρ∈[0,1]。而I为布尔变量，如果网关g的负载最低，其值为1，否则为零。

(7)

其中G表示节点i连通的网关集。而g′为网关集内的一个网关。hopg表示节点i离网关g的跳数。

为了更好地理解网关的选择过程，用图3示例说明[12]。如图4所示，三个网关G1、G2、G3；三个中间MRs R1、R2、 R3；两个源节点S1、S2。假定S1离G1、G2、G3的跳数分别为2、2、3。而S2离G1、G2、G3的跳数分别为5、3、2。

图3 网关选择示意图

首先，每个网关周期地向MRs发送GWADV消息。一旦接收到GWADV消息，S1和S2就利用式(6)计算与之连通的网关的概率。即S1选择G1、G2、G3的概率分别为0.37、0.37、0.25(如表2的第一行)。而S2选择G1、G2、G3的概率分别为0.19、0.32、0.48(如表2的第二行)。

表2 S1选择网关的概率

表3 S2选择网关的概率

观察到，S1和S2在所有时刻(t=0,t=3,t=5,t=6)并没有选择同一个网关。因此，源节点并没有总是选择最低负载网关。

2 系统仿真

2.1 仿真场景

利用NS-2仿真器建立仿真平台，进而分析PCPG协议的性能[13]。在1000 m×1000 m区域内部署18个节点，其中15个MRs、3个GWs，并且每个节点有4个接口。同时，引用基于802.11b的MAC层协议，数据传输率为11 Mbps。流量类型为CBR，尺寸为1000 bytes。每次实验独立仿真50次，取平均值作为最终实验数据。

PCPG路由是通过路径成本和基于概率的网关选择策略发现路由。为了更好地分析PCPG路由性能，选择基于ETX、NG、LG、IR的路由进行比较，且分别在仿真图中标记为ETX、NG、LG、IR。基于ETX路由是选择具有最小ETX的路由传输数据，而基于IR路由是选择最小IR路由传输数据。基于NG路由是选择最短路径传输数据，而基于LG路由是选择具有最小LG的路径传输数据。同时，选择网络吞吐量、平均端到端传输时延、平均数据包丢失率作为性能指标。

2.2 仿真结果及分析

首先，分析数据传输时延，实验数据如图4所示。从图4可知，提出的PCPG路由具有最低时延特性。原因在于：PCPG协议在选择路由时，充分考虑了链路质量， 同时也考虑了网关负载，这利用于稳定路由。从图4可知，当数据率为1500kb/s时，PCPG路由的时延比基于ETX、NG、LG、IR路由时延分别降低了近52%、58%、46%、13%。

图4 端到端传输时延随数据率的变化曲线

基于NG和ETX路由是仅通过跳数、探测包的丢失率选择路由，这不利用于选择稳定路由，加大了传输时延。而基于LG路由是只通过GW负载决策路由、而基于IR路由是通过干扰率决策路由，这种单一度量策略，可能会形成低干扰、高负载GW或者低负载、高干扰路由，这都不利于路由的连通性，也必然增加了传输时延。

接下来，分析PCPG路由的吞吐量，实验数据如图5所示。从图5可知，相比于基于ETX、NG、LG、IR路由，PCPG路由具有最大的吞吐量，原因在于：PCPG所决策的路由较稳定，并且在选择网关，充分考虑了网关的负载，这利用于提高吞吐量。例如，当数据率为3000 kb/s时, 与基于ETX、NG、LG、IR路由相比， 吞吐量分别下降近26%、13%、33%、10%。

最后，分析了数据包丢失率随数据率的性能影响，实验数据如图6所示。从图6可知，PCPG路由的数据包丢失率最低。当数据率为2500kb/s时，PCPG路由时延分别比基于ETX、LG、NG、IR路由下降了25%、10%、35%、17%。此外，从图7可知，数据包丢失率随数据率的增加而上升，原因在于数据率的增加，加大网络负载，降低了数据包丢失率。

图6 数据包丢失率随数据率的变化曲线

3 结 语

针对无线Mesh网络WMNs的路由问题，提出基于路径成本和概率-网关的WMNs路由PCPG。PCPG路由从期望链路质量、干扰率以及网关负载方面决策路由，进而构建稳定、强健路由。实验数据表明，与传统的WMNs路由相比，提出的PCPG路由能够有效地提高吞吐量，缩短传输时延。