基于有限优先权的无线Mesh网络信道分配算法

张挺葛志辉2

(1.广西大学计算机与电子信息学院, 广西南宁530004;2.广西高校并行与分布式计算技术重点实验室, 广西南宁530004)

无线Mesh网络(wireless mesh network, WMN)是一种具有多跳、自组织、自愈等特点的新型无线网络[1-3]，是下一代互联网的重要组成部分。但是，在WMN网络中，随着网络节点数量的不断增多，使得网络的规模越来越大，对网络的服务质量也提出了越来越高的要求。高效、合理地分配网络资源成为WMN研究领域的重点问题之一。

众所周知，信道是无线网络的重要资源之一。随着网络节点的不断增加，信道资源紧缺的现象日趋严重，信道资源的有限性已成为严重影响网络性能的主要因素。因此，如何合理地分配信道，改善传输效率和服务网络传输需求的质量，进而提高网络的吞吐量，是WMN研究的关键问题[4]。

文献[5]提出一种动态的信道分配算法，把信道资源看作是一个信道频谱池，根据用户对信道的需求来调整策略。文献[6]提出一种分布式信道分配算法，首先估计链路的负载，然后确定高负载链路拥有优先分配信道的权利。文献[7]提出一种分簇式的负载感知信道分配算法，定期在簇间交换信息，从而实现自适应的信道分配。文献[8]以非合作方式分配信道资源，通过群体智能方法实现网络节点的均衡负载。文献[9]和文献[10]通过优先考虑把更多的信道资源分配给负载量大的链路，提高关键链路承受流量负载的能力，进而实现各信道的负载均衡和整体网络性能的提高。文献[11]研究了涟漪效益对无线Mesh网路信息分配策略的影响和需解决的问题。文献[12]提出一种基于不完美信息博弈的多冲突域信道分配算法，可用于最大化无线网络的信道利用率。文献[13]、[14]通过构造基于0-1线性规划方法，提出一种面向多信道无线网络的资源优化模型和两步骤资源分配算法，以期解决无线Ad hoc网络中的信道冲突和干扰问题。文献[15]在保证节点之间连通性的前提下，为每个节点动态地分配固定信道，以此来减少干扰、提高传输效率。但是，以上文献提出的信道算法或策略都是从节点和链路角度出发，以保持节点间的连通性、减少信道冲突和干扰为目的，没有考虑根据业务的性质对业务进行区分，然后依据不同业务对信道资源的不同需求来进行信道分配。

从现有的技术发展趋势和应用层面来看，WMN网络已经从过去的数据服务业务拓展到VoIP、流媒体、语音等多种服务业务，扩大了业务的应用范围。但是，在实际的网络运行中，实时性比较强的业务(如视频、语言等业务)往往能够优先地获得信道资源，且资源占用率比较高，而数据业务优先获得信道资源的权限不高。在网络负载过重情况下，如果实时性业务过度地占用资源，势必会造成了数据业务长时间地处于等待状态。为此，为了保证不同业务之间占用信道资源的公平性，针对IEEE 802.11e EDAC协议没有考虑不同业务间的公平性的问题，本文提出一种有限优先权的WMN网络信道分配算法，通过适时限制实时性业务(如语音、视频等业务)占用信道资源的时间，使数据业务也有机会获得信道资源，从而提高WMN网络的系统效率和服务质量。

1 系统模型

1.1 模型建立

IEEE 802.11e EDCA协议提供了语音和多媒体等应用需要的服务质量和增强的网络性能，把现有网络中的业务划分为VoIP、视频、话音、数据等四个不同的用户优先级业务，本文把数据业务归为低优先级业务，其余三种业务归为高优先级业务，为研究方便，假设：

①如果系统服务台正忙，则规定到达系统的高优先级业务不能强占信道资源，只能等待系统服务。

②高优先级业务和低优先级业务到达系统的时间间隔均服从泊松分布。同时，系统为每类业务服务的时间均服从平均服务率μ的负指数分布。

③假设λ1和λ2分别为高优先级业务和低优先级业务的平均到达率，n为系统服务台数量，μ为系统的平均服务率，ρ1和ρ2分别为高优先级业务和低优先级业务的业务量。则系统的业务量为：

(1)

在WMN网络中，系统有多条信道，多个业务同时都在竞争分配多个信道，因此本文可以用排队论中的M/M/n/m排队系统为系统建模。假设每个网络节点都为高、低优先级业务维护相应的优先级队列，且这些队列都是通过优先级来竞争信道资源。又假设等待队列长度为k，业务加入队列的概率为αk(0<αk<1)，num为有限优先级参数，其值由信道资源被占用时间比来确定。本文采用了文献[16]提出的建模思路，构建了一个非强占有限优先权M/M/n/m模型。在该模型中，主要是根据num的值来动态调整低优先级业务的优先级别，以此来限制高优先级业务过度地占用信道，使低优先级业务也有机会占用信道资源，从而保证了高、低两种优先级业务的公平性。具体的做法是：当num≥1时，如果系统中有低优先级业务等待服务，那么在连续服务了num个高优先级业务后，将低优先级业务的优先级别设置为最高级，从而使低优先级业务获得了占用信道资源的机会。在该模型中，高优先级业务的平均排队等待时间Wq1和低优先级的平均排队等待时间业务Wq2的计算公式如下：

(2)

(3)

为了刻画高、低优先级业务之间占用信道的公平程度，本文用COTi(i=1，2)分别表示高优先级业务和低优先级业务在单位间隔时间Td内使用信道成功发送分组信息的情况。COTi的计算公式为：

(4)

其中，tb表示发送单位比特数据所需的时间，L(n)表示发送的第n个分组的长度。

为了记录每个优先级队列成功发送信息的情况，本文为每个优先级队列设置一个时间计算器Ci，其初值为0。每当各优先级队列成功发送一个分组信息，都要调用下面的公式来更新其计算器的值：

Ci=Ci+tb×L(n)。

(5)

本文用COTth,i(i=1，2)分别表示高优先级业务和低优先级业务获得的信道占用时间比阀值，不同优先级业务的信道占用时间比阀值COTth,i是不同的。COTth,i的计算公式如下：

(6)

在本文模型中，设置了一个共同的计时器Timer，初值为0。每当Timer的值Ttimer≥Td时，系统自动计算每个优先级队列的COTi。如果高优先级业务的COT1>COTth,1，则将低优先级队列的优先级设置为最高级，同时TTimer的值按以下公式调整：

(7)

其中，COTmax和COTmin是单位间隔时间Td内优先级队列的COTi的最大值和最小值，COTth max和COTth min是单位间隔时间Td内优先级业务的信道占用时间比阀值COTth,i的最大值和最小值。

利用式(4)～(6)，使得每隔一个单位间隔时间Td，低优先级队列都有机会将其优先级调整为最高级，进而获得占用信道的机会。这样就增加了低优先级队列占用信道的时间，降低了因超时而丢包的可能性，由此提高了低优先级队列业务占用信道的公平性。

1.2 公平系数

为了较好地反映不同优先级业务之间分配信道资源的公平性，本文采用了文献[17]、[18]定义的公平系数FI：

(8)

其中，SH、SL分别表示高优先级业务和低优先级业务的吞吐量，φH、φL分别表示高优先级业务和低优先级业务的权重值。

2 信道分配算法

本文提出的基于有限优先级的信道分配算法的设计思路是：在网络负载较大时，通过适时地提高低优先级业务的优先级，使其有机会获得信道资源，从而实现高、低优先级业务分配使用信道资源的公平性。具体的做法是：每隔一个单位间隔时间Td，都要动态地更新各个优先级业务的信道占用时间比COTi、信道占用时间比阀值COTth,i和计时器Timer，当高优先级业务的COT1>COTth,1时将低优先级队列的优先级设置为最高级，确保了低优先级业务有机会获得信道资源。算法主要的流程如图1所示。

3 实验与分析

使用NS2仿真平台对本文算法与IEEE 802.11e EDCA协议中提出的信道分配算法(简称EDCA算法)进行了性能实验对比分析。在仿真网络场景中，将网络的节点数配置为25，节点按5×5均匀网格矩阵结构排列，均匀分布在场景大小为1 000 m×1 000 m范围内。同时，在网络中设有两个网关节点，分别为节点8和节点16。仿真实验网络拓扑结构如图2所示。

在实验中，使用CBR模型来模拟高、低两种优先级业务，其中高优先级业务的分组大小为512 bits，其阀值COTth,i的初始值设置为0.4；低优先级业务的分组大小为256 bits，其阀值COTth,i的初始值设置为0.1。Td=10 s，权值α=0.4。

图1 基于有限优先级的信道分配算法流程Fig.1 Flow chart of channel allocation algorithm based on limited priority

图2 仿真实验网络拓扑结构Fig.2 Simulation experiment network topology

图3是本文算法与EDCA算法在不同业务情形下平均吞吐量的实验结果图。从实验结果可以看出，两种算法的平均吞吐量在负载小于0.07 Mbit/s时差别不大，但是随着负载的不断增大，两种算法的平均吞吐量的差异增大，尤其是低优先级业务时算法的平均吞吐量急剧降低。分析其原因，主要在于当网络负载较大时，本文算法适时地通过提高低优先级业务的优先权，限制了高优先级业务占用信道资源的优先权，增加了低优先级业务获得信道资源的几率，保证了高优先级业务和低优先级业务间的相对公平。实验结果也说明了在网络负载较大时，利用本文算法可以提高低优先级业务的吞吐量。

图4给出了本文算法与EDCA算法的系统平均吞吐量实验结果。从实验结果可以看出本文算法的系统平均吞吐量比EDCA算法有所提高。这是因为本文算法在网络负载较大时通过提高低优先级业务的优先权，增加了低优先级业务获得信道资源的占用率，降低了低优先级业务因分组超时产生的丢包率，一定程度上增加了系统总的吞吐量。

图3 两个算法各业务平均吞吐量对比
Fig.3 Average throughput comparison ofeach algorithm of two algorithms

图4 两个算法的系统平均吞吐量对比
Fig.4 System average throughputcomparison of two algorithms

图5 两个算法的公平系数FI对比Fig.5 Comparison of fairness coefficient FI of two algorithms

图5是公平系数FI的结算结果对比示意图，其计算公式如式(8)所示。FI越接近1，说明系统的公平性越好。从图5所示的计算结果来看，当业务负载趋近饱和时，本文算法的FI值波动比较小，基本维持在0.9～1，而EDCA算法的公平系数FI的值有些波动，且大多在0.8以下。计算结果说明了本文算法的公平性比IEEE 802.11e EDCA协议要好。这是因为本文算法比较全面考虑了高、低优先级业务之间的相对公平性，当网络负载较大时，通过提高低优先级业务的优先级，使得低优先级业务也能占用一定的信道资源，由此提高了低优先级业务占用信道资源的公平性，进而提高了网络的传输效率和资源利用率。

4 结语

本文利用排队论中的M/M/n/m排队建模对无线Mesh网络中不同业务的信道分配问题进行建模，并基于IEEE 802.11e EDCA协议，提出一种有限优先权的信道分配算法。该算法兼顾考虑了高优先级和低优先级两种不同业务的公平性，通过在网络负载较大时适时地将低优先级业务的优先级提高到最高级，限制高优先级业务过度地长期占用信道资源，使高、低优先级的业务都能够保持对信道资源的占用率。网络仿真实验结果表明，本文算法较好地解决了不同业务间占用信道资源的公平性问题，也解决了因高优先级业务过度占用信道资源造成了低优先级业务迟迟得不到服务的问题，提高了无线Mesh网络系统的传输效率和资源综合利用率。