一种基于博弈论的无线Mesh网信道分配算法

2023.05.04

殷昌盛

摘要：为解决无线Mesh网络中的信道分配问题，提出了基于博弈论的信道分配（GBCA）算法。该算法将无线Mesh网中各节点的信道分配过程作为一个博弈过程，信道分配策略作为博弈者的策略选择，信噪比函数为博弈的效用函数。基于NS2的仿真结果表明该算法在吞吐量和丢包率方面都有较好的性能。

关键词：无线Mesh网；信道分配；博弈论

0引言

无线Mesh网（WMN，Wireless Mesh Network）是一种由Mesh路由器和Mesh终端组成的多跳无线网络，具有传输速率高、覆盖范围广和组网成本低等优点，是解决无线终端接入Internet的一种比较有竞争力的技术方案。多信道Mesh虽能提高无线Mesh网络容量，但合理的信道分配至关重要。

无线Mesh网作为一种可自组织和自管理的无线网络架构，其个节点节点可自行组网，并竞争接入信道。在这种网络中，节点具有一定的自私性，之间是相互竞争资源又相互依赖的关系，其正与博弈论的思想有着非常大的相似性。基于上述考虑，本文提出了一种基于博弈论的信道分配（Gamebased channel assignment，GBCA）算法。将无线Mesh网中各节点的信道分配过程作为一个博弈过程，信道分配策略作为博弈者的策略选择，信噪比函数为博弈的效用函数，通过最大化网络信噪比进行信道分配。

2系统模型构建

利用博弈论对无线Mesh网络进行研究，其中的关键是如何将博弈论引入到相应算法的设计与分析之中，找到算法的纳什均衡点。即无线Mesh网络中的频谱分配问题是各节点频谱选择的博弈过程，将所研究的问题抽象成博弈论问题模型。

2.1信道分配博弈模型

将无线Mesh网中各节点的信道分配过程作为一个博弈过程，信道分配策略作为博弈者的策略选择，信噪比函数为博弈的效用函数，通过最大化网络信噪比进行信道分配。

接收节点的信噪比（SINR）决定着该接收链路能否成功传输，从而影响网络性能，所以本文以最大化网络信噪比为目的进行信道分配。链路中节点j处信噪比可表示为：

而为使网络中总体干扰最小，只需要使每个节点所受到的干扰最小即可。同时，在无线WMNs中各节点在相同的信道上时，其干扰时相互的，这正与博弈论研究特征相符合。然而，由于Mesh网的网状特点，任何一个节点，或说是博弈者，其所选择的对于自身干扰最小的信道也许会对其邻近节点造成很大的干扰，从而与网络总体干扰最小化矛盾。因此，在确定博弈者的效用函数时，应该同时考虑被干扰与干扰联合最小化问题。所以，可以定义博弈者i的效用函数表达式为：

所以满足潜在博弈函数条件，所以本文的博弈模型总会收敛于一个纳什均衡。证毕。

2.3基本算法步骤

综合以上分析，我们可以得出该博弈算法是一个收敛的重复博弈。在每次博弈循环中，每个Mesh节点i根据ai来选择策略ua从而实现提高效用函数u（a）。如果可以因节点的策略的改变而提高，则节点策略改变，同时博弈过程进入新一轮循环。同时，为了防止博弈效用函数的震荡，规定同一时间内只允许一个节点改变，所有节点依次进行此操作从而达到NE。其基本算法步骤如下：

（1）初始化：随机为N个Mesh节点用户分配信道和发射功率。所有节点的策略组合即是整个网络的初始信道分配策略，可记为A0。

（2）迭代过程：节点用户按照接入网络的先后顺序依次进行博弈，即每个节点依次选择使得效用函数最大的策略，继而更新整个网络策略A*。

（3）终止过程：重复迭代过程，直至算法收敛。

3仿真与分析

使用NS-2 2.33仿真软件，基于802.11a/g的多接口无线Mesh网络进行了流量仿真实验。在收敛速率、网络吞吐量与丢包率等方面与RCA、J-CAR算法进行了比较与分析。

其中传播模型采用圆盘传播模型（two-ray ground模型），采用系统默认发送功率，因此其信号传输范围为125m，载波侦听范围为220m。同时，传输采用RTS/CTS四路握手机制。网络结构为设置为的网格状网络，m取值从2到6，节点间距离100m。每个节点拥有两个接口，可使用的正交信道数为2到8条。

图1描述了在不同网络规模的情况下4种算法的网络吞吐量、丢包率情况，可以看出：本文提出的GBCA算法吞吐量略高于RCA与J-CAR算法，而丢包率较低，这是因为J-CAR算法不能适应流量的变化，而RCA算法没有考虑干扰，它们的信道分配结果有可能会造成较大的干扰。

当网络吞吐量随着网络规模的变大有一定的增加，特别是网络规模较小时增幅较为明显；而当规模继续增大时，由于网关节点的容量限制，网络吞吐量增幅不明显；另一方面，网络规模较小时，GBCA算法的网络吞吐量高于GBCA-PA算法，这是因为GBCA算法没有考虑节点公平性，牺牲了部分远离网关节点的Mesh节点的流量业务需求；而网络规模增大时，改进算法吞吐率变大，优于基本算法，这是因为其通过功率控制减小了链路之间的干扰。

4结语

文章根据博弈论思想与Mesh网多信道分配的特点，将无线Mesh网中的多信道分配问题模型化为一个联合博弈（GBCA）。通过证明该模型为潜在博弈以及潜在函数的存在性，从理论上证明了算法的收敛性；给出了算法的具体实现，并通过NS-2软件对算法进行了网络仿真。仿真结果表明，利用博弈论设计一种效用函数来实现最大化网络信噪比，来解决无线Mesh网络中多信道分配是一种行之有效的方法。