集中式无线局域网信道分配算法

李 科，张志飞

(北京交通大学计算机与信息技术学院，北京100044)

0 引言

基于IEEE 802.11协议的无线局域网 (wireless local area network，WLAN)的接入点 (access point，AP)信道默认设定为相同的固定值，在接入点密集部署情况下，相邻的接入点之间会形成极强的同频信号干扰，造成网络传输失败次数增多、整体吞吐量下降等问题。许多学者提出了大量关于信道调整的算法，这些算法从信道分配方式上大致分为2种:静态分配方式和动态分配方式。

静态分配算法中信道分配作为网络规划的一部分，AP位置分配和信道分配往往会综合进行考虑，静态分配算法分为以下2类。

(1)传统算法、Integer Linear Programming(ILP)算法、Priority-Map算法、Patching算法、Coverage-Oriented算法［1］;此类算法要求预置AP的位置，而无线局域网的特点就在于它提供了随时随地的快速部署、建立和撤销，所以灵活性方面的缺失极大影响了该信道调整算法的应用范围。

(2)DSATUR类算法［2］、CFAssign-RaC类算法［3］、Measurement-Based类算法［4］。此类算法不要求预置 AP的位置，但是在信息的搜集过程中需要AP之间大量的交换各自配置信息，增加了网络的指令开销，同时对AP节点造成很重的存储和计算负担。

动态调整方式是一种跟随网络状况及时调整信道的分配方式，具有对网络变化反馈快，可灵活分配等优点。典型算法如:LCCS 类算法［5］、MinMax 类算法［6］、Hminmax/Hsum 算法、Pick-Rand and Pick-First类算法［7，8］等。上述算法分别针对信道的负载情况、信道利用率、干扰量对信道进行了调整。

本论文所提出的算法是在集中式架构下，对AP的状态信息进行统一的搜集、存储和处理，实时地监控网络状态的变化，通过对信道的动态分配，最小化所有AP的邻居数目总和和所受干扰总和，同时实现信道之间的负载均衡。

1 信道调整算法

1.1 算法方案

网络整体采用集中式的无线局域网架构［9，10］，接入点(access point，AP)直接或通过二层 (三层交换机)与集中式设备 (AP controler，AC)相连，动态信道调整算法运行在AC上。AC与众多AP之间通过CAPWAP协议［11］进行通信，AC可以有效的对网络中各个AP的工作状态和调整结果进行监控，每经过一个信息搜集周期，便通过CAPWAP控制隧道，将信息搜集指令下发到各个AP，各个AP依次搜集自身的邻居信息 (邻居AP名称、接受功率)，将这些信息通过数据隧道上传给AC进行信息的汇总和整理，由AC构建相关数据结构来维护网络全局信息。

每经过一个信道调整周期或者当前网络状态 (网络拓扑结构、AP所受干扰等)发生变化时，AC便搜集和读取全局状态信息，执行信道调整算法，得出各个AP的信道调整决策，通过CAPWAP控制隧道将决策下发至相应AP，AP执行下发的决策，对自身信道进行调整。

1.2 算法步骤

如图1所示，各个AP将携带有自身信息的beacon帧在各信道上依次发出，同时在各信道上轮询侦听自己的周边网络状态，生成本AP在各个信道的邻居关系表，此表包含有:本AP的邻居都包括哪些AP以及本AP收到相邻AP发出的信号功率大小。AC搜集各个AP的邻居关系表，表中邻居数目是指该AP能够感知到多少AP，指示了该AP能够被多少AP所干扰，接受功率总和用来指示该AP受到相邻AP信号干扰的大小程度，这2项指标是进行动态信道调整的重要判据。

图1 算法步骤流程

算法运行需要下列参数:

初始信道CH_INIT:AP初始时设置的信道。

目标信道CH_AIM:AP节点将要调整至的信道。

信道标记FLAG:区分AP发出beacon帧时的信道为工作信道 (FLAG为1)还是检测信道 (FLAG为0)。

接受功率Pr:AP接收到相邻AP发出的Beacon帧的信号功率。

邻居数目NEI_NUM:根据监听到的Beacon帧来累计得到。

反向邻居数目REV_NEI_NUM:AC根据反向邻居表来计算得到。

接受功率总和SUM_PR:根据邻居关系表计算得到。

反向接受功率总和SUM_REV_PR:根据反向邻居关系表计算得到。

邻居数目阈值NEI_NUM_MAX:对所有AP的NEI_NUM取均值 (向下取整)得到。

接受功率总和阈值SUM_PR_MAX:对所有AP的SUM_PR取均值得到。

信道调整次数Ci:APi进行连续信道调整的次数。

信道调整次数阈值R:AP的信道调整次数Ci的阈值。

算法运行周期T:由整个网络的信息搜集、汇总、算法决策和执行耗时总和来确定。

算法运行过程如下:

(1)一个新的信道调整周期T开始。

(2)设共有n个 AP节点，依次编号为 AP0，AP1，……，APn－1。对每个APi执行 (3)-(4)操作。

(3)APi首先初始化 NEI_NUM=0，REV_NEI_NUM=0，SUM_PR=0，SUM_REV_PR=0。然后依次在Channel1、Channel6、Channel11这3个频谱互不交叠的信道上广播携带有自身信息的beacon帧，并在beacon帧中对当前信道是工作信道还是检测信道予以标记，在切换至下一信道进行beacon帧广播之前，APi在当前信道上进行邻居信息的侦听，接收其它AP发出的信标帧，若信号强度达到接受功率阈值，则NEI_NUM加1，此时AP在beacon帧中可以获取邻居AP的MAC地址、信噪比、接收信号强度等相关信息，由beacon帧中的信道标记FLAG可判断当前邻居为实际邻居或是潜在邻居。这样依次遍历所有的信道，然后再返回自己当前的工作信道，继续为STA继续正常通信服务，这样APi可以在对自身通信业务影响极其微小的情况下，搜集到所有信道的邻居信息。

(4)信道侦听周期结束后，所有AP将自身在各个可行信道的邻居信息通过CAPWAP数据隧道上传到AC处进行汇总。

(5)AC搜集到所有AP的邻居信息后，建立全局邻居关系表，并由此计算得出反向邻居关系表，反向邻居表提供该AP被哪些AP识别为邻居以及对反向邻居AP所造成的干扰大小。

(6)对各AP节点，按照优先对所受干扰量大的AP进行调整的原则，以邻居数目为依据，对AP在工作信道中邻居数目NEI_NUM由大到小进行排序，依次加入信道调整列表，执行 (7)-(10)，执行完毕后，转 (11)。

(7)若C＞R，则表明当前AP已经达到调整次数阈值，因此将之列入信道保持组，在信道保持期间不再对其进行信道调整，超出保持时间后，重新参加信道调整，转(6);若C ＜=R，转 (8)。

(8)①若NEI_NUM ＜NEI_NUM_MAX，表明APi在当前信道所受相邻AP干扰相对较小，暂时不需要对其进行信道调整;转 (6);②若NEI_NUM ＞=NEI_NUM_MAX，则表明APi在当前信道所受相邻AP干扰过大，需要对其进行信道调整。

(9)首先确定当前AP的目标信道列表，再依次对个目标信道是否适合切换进行判定，若适合，将之确定为切换信道，进行信道的切换，对其余目标信道则不再进行判定。

目标信道的选择标准:选取在所有信道中存在的实际邻居数目最少的信道，当2个信道邻居数目相等时，对节点在该信道能接收到的实际信号总功率进行由小到大排序，根据排序的结果，将之添加入目标信道列表。

目标信道是否适合切换的判定原则 (需同时满足下面两条):①AP在工作信道的邻居数目减去目标信道的邻居数目 ＞=AP在目标信道的反向邻居数目减去在工作信道的反向邻居数目。意即AP所受干扰AP减少的数量必须大于受AP所干扰的AP增加的数量，这样从总体上减少相互干扰的AP的数量。②AP在工作信道的干扰总量减去目标信道的干扰总量 ＞=AP在目标信道的反向干扰总量减去在工作信道的反向邻居干扰总量。意即AP所受干扰功率减少的总量必须大于受AP所干扰的功率减少的总量，这样从总体上减少AP间的功率干扰总量。

(10)若本次对当前AP进行了信道调整，AP信道调整成功后，知会AC，AC根据调整的结果对邻居关系列表和反向邻居关系列表中涉及到AP信道变动的标志位予以更新，对Ci加1;转 (6)。

(11)本次调整周期完毕。

(12)等待时间T后本次AP上报的信息与上一周期有变化或者当网络信息发生改变 (如有新的AP加入、现有AP出现设备故障)的时候，AC启动新的算法调整周期。

2 仿真实验

2.1 实验参数设置

AP的发射功率和信号接受门限值等参数，若不进行设置，NS2会使用默认的参数值，这些值在ns-default.tcl文件中有定义，ns2将之初始化为:CPThresh为 10倍，RXThresh为3.652e-10W，Pt为0.28183815W。

传输模型、物理层、MAC层协议、接口队列、链路层、天线类型等参数，由TCL脚本进行设置，部分TCL代码如下:

set val(chan) Channel/WirelessChannel

set val(prop) Propagation/TwoRayGround

set val(netif) Phy/WirelessPhy

set val(mac) Mac/802_11

set val(ifq) Queue/DropTail

set val(ll) LL

set val(ant) Antenna/OmniAntenna

set val(ifqlen) 50

set val(rp) DumbAgent

其它诸如信道调整周期、邻居数目、采用信道、接受功率等参数，在信道调整算法代码中初始化，部分C++代码如下:

T=60;CH_INIT=1;CH_AIM=1;NEI_NUM=0;REV_NEI_NUM=0;SUM_PR=0;REV_SUM_PR=0;

2.2 实验结果

圆圈表示AP的无线传输范围，初始状态所有AP均采用channel 1，经过全局信息搜集和处理后，AC可以获取整体网络状态，对AP进行动态的信道分配。

实验1:

如图2所示，算法动态的调整了AP2和AP3至channel6和channel11，AP2和AP3的信道调整减小了相邻AP信号竞争和干扰的存在，3个信道的AP数量均为1，实现了AP在信道间的均衡分布。

如图3所示，算法动态的调整了AP2和AP3至channel6和channel11，AP2和AP3的信道调整减小了相邻AP信号竞争和干扰的存在，3个信道的AP数量分别为:2、1和1，实现了AP在信道间的均衡分布。

图2 动态信道调整仿真效果

实验2:

图3 动态信道调整仿真效果

如图4所示，算法对新加入的AP进行了动态的调整，上述AP的信道调整减小了相邻AP间同频信号竞争和干扰的存在，3个信道的AP数量均为3，实现了AP在信道间的均衡分布。

实验3:

在实验2调整结束的基础上新增加5个AP，与原有4个AP呈三行三列排布。

图4 动态信道调整仿真效果

3 结束语

本文研究了WLAN密集部署下的AP间干扰问题，在研究各类算法的基础上，给出了一种集中式WLAN架构下的动态信道分配算法，该算法可以减轻AP的存储和计算负担，算法运行之前无需预知AP的位置，可根据网络状况变化及时进行信道调整，在减少AP间干扰的同时，实现了基于AP数量的信道间负载均衡，NS2仿真结果表明该算法是简单有效的。但是实际应用中需要考虑的因素会更多一些，例如STA与AP之间的干扰、不属于同一AC管理的AP造成的干扰、周边其他电子设备造成的干扰等不可预知因素，这些问题还有待于进一步的研究和解决。

［1］Eisenblatter A，Geerdes H F，Siomina I.Integrated access point placement and channel assignment forwireless LANs in an indoor office environment［C］//Symposium on a World of Wireless，Mobile and Multimedia Networks，2007.

［2］Riihijarvi J，Petrova M，Mahonen P，et al.Performance evaluation of automatic channel assignment mechanism for IEEE 802.11 based on graph coloring［C］//Proc 17th Annual IEEE International Symposium on Personal，Indoor and Mobile Radio Communications，2006:1-5.

［3］Mishra A，Brik V，Banerjee S，et al.A client-driven approach for channelmanagement in wireless LANs［C］//Proc 25th IEEE International Conference on Computer Communications，2006.

［4］Chen JK，Veciana G D，Rappaport T S.Improved measurementbased frequency allocation algorithms for wireless networks［C］//GLOBECOM，2007.

［5］Achanta M.Method and apparatus for least congested channel scan for wireless access points［P］.USA:20060072602，2006.

［6］Yu M，Luo H，Leung K K.A dynamic radio resourcemanagement technique formultiple APs in WLANs［C］//IEEE Trans Wireless Commun，2006.

［7］Akl R，Arepally A.Dynamic channel assignment in IEEE 802.11 Networks［C］//Proc IEEE International Conference on Portable Information Devices，2007.

［8］Haidar M，Akl R，Al-Rizzo H，et al.Channel assignmentand load distribution in a power-managed WLAN ［C］//18th Annual IEEE International Symposium on Personal，Indoor and Mobile Radio Communications，2007.

［9］WEIKejun，ZHAO Yang，HOU Ziqiang.RRM analysis ofWLAN based on IEEE 802.11 protocol［J］.Telecommunications Science，2006，22(8):11-13(in Chinese).［魏克军，赵洋，侯自强.基于lEEE 802.11协议的WLAN无线资源管理浅析［J］.电信科学，2006，22(8):11-13.

［10］FEILan，PAN Chunjian，TAN Hongyan.Design and realization of split-mac scheme in cent-centralized WLAN network［J］.Computer Engineering，2007，33(19):112-114(in Chinese).［费岚，潘春建，谭红艳.集中式WLAN网络MAC分割方案的设计与实现 ［J］.计算机工程，2007，33(19):112-114.］

［11］XIANGWang，WANG Zhiwei，GAO Chuanshan.Communication protocol of centralized WLAN architecture［J］.Computer Engineering，2008，34(22):115-117(in Chinese).［向望，王志伟，高传善.集中式WLAN体系结构通信协议［J］.计算机工程，2008，34(22):115-117.］