面向802.11b非对称无线网络容量优化的部分重叠信道分配方案*

潘 晨，孙有铭 ， ， 段焱磊 ， 杨正举 ， 张玉立

（1.陆军工程大学 通信工程学院，江苏 南京 210000；2.中国人民解放军61062部队，北京 100089；3.中国人民解放军92247部队，云南 昆明 650000）

0 引 言

随着无线局域网（Wireless Local Area Network，WLAN）技术的日趋成熟，IEEE 802.11b已经成为WLAN的主流接入标准，其最高数据速率可达11 Mb/s，得到了广大设备生产厂家的支持。IEEE 802.11b中所规定的无线信道模型中共划分11条信道，每条信道带宽为22 MHz，相邻信道只有5 MHz带宽不重叠。因此，完全正交（信道不重叠）的信道最多只有3个，即信道1、6和11[1]。信道间有重叠的信道称为部分重叠信道（Partially Overlapped Channel，POC）。起初，802.11b无线网络中的信道资源分配问题主要聚焦在小规模无线网络，面临的最主要挑战来自于相邻链路间共信道干扰引起的网络容量恶化问题。随着网络规模增加和频谱资源稀缺问题日益凸显，相关研究者开始考虑为网络中的通信链路分配POC[2]。但是，如何有效抑制邻信道干扰（Adjacent Channel Interference）的影响成为POC分配方案的技术难点。802.11无线网络中的POC分配引起了学术界的广泛关注[1]。

Mishraa等人率先提出使用POC增加802.11无线网络容量[2-3]，并联合考虑相邻链路间的物理距离和信道间隔来分配POC，通过增加信道空间复用，显著提升了频谱利用率。但是，现有关于POC分配方案大多基于集中式优化方法，如图着色方法[3]，遗传算法[4]等。其中，Ding等人在文献[4]中提出利用加权干扰图来建模POC干扰。加权图中任意两条链路的权重为相互无干扰传输时的最小信道间隔，并分别设计了基于贪婪算法和遗传算法两种POC分配方案来最小化全网受干扰链路数量。Duarte等人在文献[5]中利用博弈论研究了802.11无线Mesh网络中的POC分配问题，将其建模为合作信道分配博弈，并能够获得近似最优解。合作博弈中需要大量的信息交互，为了减小优化中的信息交互量，Xu等人在文献[6]提出了一种面向802.11网络POC的非合作干扰消除博弈，并证明其为精确势能博弈，提出了一种无需信息交互同步对数学习方案，可渐近收敛到MAC层干扰博弈的最优解。值得注意的是，上述工作均面向干扰对称网络场景，并多基于无向加权干扰图（冲突图）进行信道资源分配优化，忽视了实际网络中由于各链路传输功率和接收机灵敏度等因素导致的干扰不对称性问题[7-8]。

为了刻画802.11非对称无线网络中不同链路间干扰模式的不对称性和异构性，文本将现有无向加权图模型扩展到有向加权图干扰模型；基于构建的有向加权图，以优化全网链路容量为目标，将网络中POC分配问题建模为局部互利博弈模型；每条链路均为博弈中参与者，效用函数设计为自身链路容量和潜在被干扰邻居链路的容量和；证明所提博弈模型为势能博弈，存在至少一个纯策略纳什均衡点，且满足最优纯策略纳什均衡为全网容量最优化的解；最后，设计了一个基于邻域合作的分布式多用户学习方案实现最优纳什均衡点的搜索。仿真表明，所提分布式学习方案可以近似收敛到最优解，相比于现有其他算法可以显著提高全网容量。

1 系统模型

1.1 有向加权干扰图

IEEE 802.11b无线网络中链路间干扰主要由链路间的物理距离和信道间隔决定。为了研究网络中链路间信道选择碰撞对网络吞吐量的影响，文献[2]定义了吞吐量归一化因子：

其中，S1和S2分别表示网络中链路1和链路2在单独通信且无干扰时的吞吐量，S*1和S*2表示两条链路同时传输的吞吐量。研究结果表明，吞吐量归一化因子η和物理距离呈现出二元门限效应。当物理距离小于某一阈值时，η近似为0.5，表明两条链路之间存在相互干扰；当物理距离超过某一阈值时，η增加到1，表明两条链路之间不存在相互干扰。

令a1和a2分别表示两条链路选择信道的编号，则两条链路的信道间隔表示为：

若两条链路选择的信道3和7，则δ=4。文献[2]的研究表明，吞吐量的门限阈值和链路间的信道距离存在内在关系。对于给定的传输速率，记有效传输距离为R。对于特定传输速率，不同信道间隔对应干扰距离为R1(δ)，如表1所示。以传输速率2 Mb/s为例，当δ=0时，即两条链路选择同一信道时，干扰距离为传输距离2倍，即RI(0)=2R；当δ=5时，即两条链路选择正交信道时，干扰距离为RI(5)=0，也就是说无论它们之间距离如何都不会产生互干扰；当δ从0增加到5时，相应的干扰距离单调减小。对于其他的传输速率，如5.5 Mb/s和11 Mb/s，干扰距离呈现同样的趋势，具体值略有差异。

表1 不同信道间隔条件下的干扰距离

文献[2]定义了加权干扰图来建模网中链路间物理距离和信道间隔的关系。加权图中的顶点指代对应的通信链路，两条链路间的权重l表明两条链路相互无干扰通信时分配信道的最小信道间隔。如图1中链路A和链路B间的权重为lAB=2，表明干扰距离RI(2)＜dAB、RI(1)≥dAB，其中dAB为链路A和链路B的物理距离。

图1 加权干扰模型

在多用户场景中，记链路A和链路B的信道间隔为δAB，链路A和链路B间的MAC层干扰为αAB：

式（3）可以等价为：

目前，现有的基于POC的资源分配方案大多都是面向基于对称干扰网络，即假设网络中任意两条链路A到链路B的无干扰最小信道间隔和链路B到链路A的无干扰最小信道间隔一致，即lAB=lBA。但实际网络中，由于链路间通信节点发射功率、接收机灵敏度以及接收滤波器等性能存在差异，链路间的相互影响通常呈现不对称性。因此，本文将传统的加权干扰图扩展到非对称加权干扰图，研究非对称Mesh网络中部分重叠信道资源分配问题。图2给出了有向加权干扰图，记链路A不影响链路B传输的最小信道间隔lA→B。类似地，链路B不影响链路A传输的最小信道间隔lB→A。通常，lB→A≠lA→B。链路A对链路B产生的MAC层干扰为 αA→B：

链路k的邻居链路分为以下两种：

第一，潜在干扰邻居链路。在有向加权图中与链路（节点）k存在边，并且边的方向由该链路（节点）指向节点k的链路（节点）。图2中，链路A的潜在干扰链路为C、B。

第二，潜在被干扰邻居链路。在有向加权图中与链路（节点）k存在边，且边的方向由节点k指向该节点。图2中，链路A的潜在被干扰链路为B。

图2 有向加权干扰模型

令链路k的潜在干扰链路集合和潜在被干扰链路集合分别为Ψk和Ψk-1，上述两个集合允许为空集。图1中，ΨA={B,C}，={B,C}。

非对称无线网络中链路A的归一化吞吐量与对称无线网络形式一致，但链路A的MAC层干扰为：

1.2 非正交信道选择优化问题建模

假设网络中的链路集合为Γ={1,2,3,…,K}，对于链路k∈{1,2,3,…,K}，其受到的MAC层干扰由它本身的信道选择和其他相邻链路的信道选择共同决定。令信道选择集合为Ξ={1,2,3,…,M}，假定链路k选择的接入信道为ak∈{1,2,3,…,M}，令sk表示与链路k产生接入干扰的链路数量：

类似地，网络中链路k的归一化吞吐量为：

优化目标是寻找最优的信道选择组合，使得网络中总容量最大化：

2 博弈建模与分析

2.1 博弈建模

分布式无线网络中，由于没有中心控制器，所有链路自发地选择接入信道。可将上述信道选择问题建模为一个非合作博弈，每一条链路都是博弈的参与者（Player）。

该非合作博弈可以表示为：

其中Γ为链路（参与者）集合，Ak代表链路k的信道选择策略空间。所有链路都可以选择网络中的信道，因此Ak=Ξ，表示链路k的效用函数为：

其中ak∈Ak代表当前链路k的信道选择，a-k代表其他链路的信道选择组合。对于给定的加权干扰图（如图1所示），网络的干扰呈现局部特性，即链路k只受到其在加权图中邻居链路的干扰。因此，本文中定义的博弈模型为加权的图（如图2所示）博弈。

由于传统博弈模型中，参与者的“完全利己主义式”策略选择可能会导致低效的均衡结果，即出现“公地悲剧”现象。受局部互利博弈[9]思想的启发，期望通过邻域间的互利策略选择来改善性能实现全局最优。定义网络中链路k的效用函数为：

定义的效用函数包含链路k的吞吐量和潜在被链路k干扰的链路的吞吐量之和。本文定义博弈模型与经典局部合作博弈不同之处在于缩小了节点的合作域。具体而言，经典局部合作博弈中任意节点k需要在其效用函数中考虑干扰图（冲突）中与它存在边的所有节点的效用；而本文定义的模型中只考虑了节点k的邻居集合中被其影响的邻居集合，缩小了合作域，为后续算法设计减小了邻域交互开销。基于上述效用函数，本文定义的博弈模型中每个参与者都将独立决策，最大化自身效用为：

2.2 纳什均衡分析

对于非合作博弈模型而言，纯策略纳什均衡是一类非常重要的均衡解概念，下面给出纯策略纳什均衡的定义。

定义1（纯策略纳什均衡，Pure Nash Equilibrium，PNE）：非合作博弈 G={Γ,(Ak)k∈Γ，{Uk}k∈Γ}，(Ak)k∈Γ=A1×A2×…×Ak中的任何一组策略 a*=(,,…,)∈(Ak)k∈Γ被称为PNE，如果满足式（16）的条件：

由PNE定义可知，PNE具有策略稳定性。当博弈处于PNE时，任何一个参与者都不能通过单方面策略改变获得效用提升。值得注意的是，对于任一非合作博弈而言，并非总是存在PNE。

定义2：精确势能博弈（Exact Potential Game）：如果存在势能函数Φ: A1×A2×…×Ak→R，对于任意的博弈参与者k和他的任意两个策略∈Ak，式（17）恒成立：

该类博弈被称为精确势能博弈。

由精确势能博弈的定义可知，任意博弈参与者单方面策略改变带来的效用函数值的变化与势能函数值的变化一致。

精确势能博弈具有如下两个非常重要的特性[10]：

（1）精确势能博弈至少存在一个PNE；

（2）势能函数Φ的全局最优解或者局部最优解是PNE。

定理1：基于有向加权图的POC信道选择博弈G是一个精确势能博弈，该博弈至少有一个纯策略纳什均衡点。

证明：构造如下势能函数：

链路k单方面改变信道选择策略，选择信道由ak切换到，其他链路保持信道选择策略不变。链路k效用函数变化可表示为：

相应地，势能函数的变化可表示为：

其中，Ψk∪表示有向图中与链路k存在边的链路集合，Ψk∪-表示图中与链路k仅存单向边，且方向由该链路指向链路k的链路集合，该集合中的链路不受链路k干扰。因此，有：

可进一步简化：

结合式（19）和式（22），可验证式（23）成立。

因此，所提的博弈模型为势能博弈，存在至少一个纯策略纳什均衡点，证毕。

定理1表明，本文定义的基于有向加权图的POC信道选择博弈G是一个精确势能博弈，同时相应的势能函数为：

其物理意义为全网链路归一化容量和。

根据精确势能博弈性质可知，势能函数Φ(a1,a2,…,aK)的全局最优或者局部最优为PNE。

由于该博弈中可能存在多个纳什均衡点，下面简要分析系统处于纳什均衡的最差性能界。系统状态处于纳什均衡时，根据均衡的定义，对于Mesh网中的任一链路k∈Γ都满足不等式：

链路k的吞吐和承受的MAC层干扰水平的关系由式（10）给出。对于加权有向图，sk≤|Ψk|，其中|·|表示集合元素个数。因此，对于任意网络拓扑，式（26）、式（27）恒成立：

代入式（25）可得：

势能函数Φ在均衡状态下满足：

3 分布式学习算法

目前，有很多学习算法可以用来进行势能博弈均衡点的搜索，如最佳响应动态（Best Response Dynamic，BR）、空间自适应行动（Spatial Adaptive Play，SAP）和虚拟行动（Fictitious Play）等。但是，这些算法并不都能确保收敛到最优的PNE。本节中，基于SAP算法设计了一种基于有向加权图的多链路并发学习机制（Multi-Link Concurrent Learning，MLCL）来收敛到最优PNE。同时，相比于SAP的每次迭代过程只允许单个用户学习，所提算法在每次迭代过程中同时选择多个图中不相邻的链路进行策略更新，可以明显加快学习收敛速度。具体而言，MLCL在每次迭代中首先随机选择一条更新策略的链路，并将其状态标注为“更新”状态，然后将其邻居链路状态标记为“不更新”状态，再将其邻居链路的邻居链路中未被标记的链路标记为“不更新”，在剩余未被标记状态的链路中重复上述操作，直到所有链路都被标记状态。在第m次迭代中，令ΛAk(m)表示链路k的动作选择概率分布，其中qakk(m)∈ΛAk(m)表示第m次迭代时选择动作ak的概率。选中更新的链路根据Boltzmann-Gibbs准则进行动作选择概率的更新：

第2步：随机选中一个更新链路，标记状态为“更新”，将其邻居链路标记为“不更新”；然后将其邻居链路的邻居链路中未被标记的链路标记为“不更新”，最后在剩余未被标记状态的链路中重复上述操作，直到所有链路都被标记状态。

第3步：标记为更新状态的链路按照动作概率分布ΛAk(m)随机进行动作选择，然后按照式（30）中规则进行动作选择概率更新。

第4步：更新m=m+1，转到第2步，直到m=mmax停止。

定理2：如果所提MLCL算法中学习参数β足够大，MLCL能够以近似1的概率最优化网络容量。

证明：文献[9]中定理4证明，SAP算法在学习参数足够大的条件下能够以近似1的概率收敛到势能函数的全局最优点。在所提学习算法MLCL中，每次迭代选择的链路都是有向加权图中的非邻居链路。因此，同时更新链路的动作策略更新并不会影响相互的效用。所以，MLCL并不改变SAP算法的收敛特性，可以满足在学习参数β足够大的条件下，以近似1的概率最大化势能函数。在本文定义的博弈模型中，势能函数Φ(a1,a2,…,aK)等于全网链路容量和，等价于以近似1的概率最优化网络容量。证毕。

其中，β表示学习速率，满足β＞0，物理含义表示学习过程中博弈参与者的理性水平。

算法1：基于邻域合作学习的MLCL算法

第1步：设置最大迭代次数为mmax。在迭代次数m=0时，初始化所有链路的信道选择概率为等概率分布，

4 仿真分析

考虑基于IEEE 802.11b的无线接入网，信道传输速率均为2 Mb/s，采用表1中参数。考虑干扰的非对称性，网络中存在两种不同的传输链路，即传输距离分别为R=100 m和R=150 m。研究规则网状网和随机网络两种不同网络拓扑结构条件下的算法性能，选取的对比算法包括穷搜算法、BR算法以及SAP算法。

4.1 规则网状网

网络中干扰图为标准网状结构，如图3所示，每行每列均分布L条链路，具有不同传输距离的两种链路交替分布，相邻链路间距离为d=100 m，网络中共L2条链路。图4给出了L=4时各种算法的性能图，图中的最优解曲线（标识为Optimal solution）是通过穷搜法得到的。同时，它分别考虑了两种不同信道使用场景：一是重叠信道场景，即11个信道均可使用；二是完全正交信道场景，即仅使用完全正交的信道，即集合中标号1、6、11信道。图4所提出的MLCL算法在小规模网络条件下可以快速收敛到最优解。由于一次迭代过程允许多个链路同时更新动作，相比于SAP算法收敛速度更快。传统BR算法的收敛速度较快，容易陷入局部最优，相比于MLCL和SAP的算法性能较低。此外，使用非重叠信道的方案可以明显获得比重叠信道更高的网络吞吐。在当前非对称干扰网络仿真中，使用非重叠信道的MLCL可以比使用重叠信道的BR和SAP方案全网性能提升114%。

图3 规则网状网

图5 给出了提出的MLCL中部分链路信道更新策略图。可见，链路1、2、4和5迅速收敛到稳定状态，链路3的策略选择存在震荡，原因在于这几个震荡状态对应的效用值一样，其中任意一个信道都是最优策略，MLCL以近概率1收敛到其中一个最优的PNE。图6研究了正则网络条件下，链路间距离对于网络性能的影响，分别设置链路距离d=100 m、70 m、50 m。随着链路距离的减小，网络中局部干扰加剧，MLCL收敛时对应的网络归一化吞吐量明显下降。d=50 m时，全网归一化吞吐相比d=100 m时对应值下降了约73%。

参考文献[6]，定义归一化容量增益（Normalized Capacity Gain）为：

其中TPOC表示使用POC的全网归一化吞吐，TNOC表示使用正交信道的全网归一化吞吐。图7研究了干扰非对程正则网络条件下，固定相邻链路间距离为d=100 m，调整网络中的链路数量，使用POC获得的性能增益。由图7可见，非对称干扰条件下使用POC可以明显改善全网性能。

图4 学习算法收敛（L=4，d=100 m）

图5 部分链路的信道选择策略学习更新

4.2 随机网络

下面研究非对称干扰图为随机干扰网络下的算法性能对比。设置边长为(L-1)×d的正方形区域内随机布设K=L2条链路，其中前述两种类型的链路数量均为K/2，固定d=100 m。图8中给出了随机生成500次非对称干扰网络，给出了平均归一化容量随学习算法迭代次数的变化曲线。可见，在给定的网络场景下，SAP算法和所提出的MLCL算法性能优于BR算法；BR算法的收敛速率是三种算法中最快的，而MLCL算法的收敛速率优于SAP算法，原因在于一次迭代中允许多个用户同时更新策略，加快了算法的收敛速度。

图6 不同链路间距下MCLC学习收敛曲线（L=4）

图7 规则网状网使用非正交信道增益（d=100 m）

图8 随机网络下学习算法收敛图（K=16）

5 结 语

面向802.11b非对称无线网络，提出了一种基于博弈学习POC分配方案优化全网容量。基于有向加权干扰图，将面向无线网络容量最优化的POC分配方案建模为局部互利博弈模型，网络中的每条链路是博弈的参与者，且效用函数设计为自身链路容量和潜在被干扰邻居链路的容量和。证明所提博弈模型为势能博弈，存在至少一个纯策略纳什均衡点，同时最优纯策略纳什均衡为全网容量最优化的解。同时，设计了一个基于邻域合作的分布式学习方案，实现了最优纳什均衡点的搜索实现全网容量最优化。仿真表明，所提分布式学习方案可以近似收敛到最优解，相比于现有其他算法可以显著优化全网容量。