李 科，張志飛

(北京交通大學計算機與信息技術(shù)學院，北京100044)

0 引言

基于IEEE 802.11協(xié)議的無線局域網(wǎng) (wireless local area network，WLAN)的接入點 (access point，AP)信道默認設定為相同的固定值，在接入點密集部署情況下，相鄰的接入點之間會形成極強的同頻信號干擾，造成網(wǎng)絡傳輸失敗次數(shù)增多、整體吞吐量下降等問題。許多學者提出了大量關(guān)于信道調(diào)整的算法，這些算法從信道分配方式上大致分為2種:靜態(tài)分配方式和動態(tài)分配方式。

靜態(tài)分配算法中信道分配作為網(wǎng)絡規(guī)劃的一部分，AP位置分配和信道分配往往會綜合進行考慮，靜態(tài)分配算法分為以下2類。

(1)傳統(tǒng)算法、Integer Linear Programming(ILP)算法、Priority-Map算法、Patching算法、Coverage-Oriented算法［1］;此類算法要求預置AP的位置，而無線局域網(wǎng)的特點就在于它提供了隨時隨地的快速部署、建立和撤銷，所以靈活性方面的缺失極大影響了該信道調(diào)整算法的應用范圍。

(2)DSATUR類算法［2］、CFAssign-RaC類算法［3］、Measurement-Based類算法［4］。此類算法不要求預置 AP的位置，但是在信息的搜集過程中需要AP之間大量的交換各自配置信息，增加了網(wǎng)絡的指令開銷，同時對AP節(jié)點造成很重的存儲和計算負擔。

動態(tài)調(diào)整方式是一種跟隨網(wǎng)絡狀況及時調(diào)整信道的分配方式，具有對網(wǎng)絡變化反饋快，可靈活分配等優(yōu)點。典型算法如:LCCS 類算法［5］、MinMax 類算法［6］、Hminmax/Hsum 算法、Pick-Rand and Pick-First類算法［7，8］等。上述算法分別針對信道的負載情況、信道利用率、干擾量對信道進行了調(diào)整。

本論文所提出的算法是在集中式架構(gòu)下，對AP的狀態(tài)信息進行統(tǒng)一的搜集、存儲和處理，實時地監(jiān)控網(wǎng)絡狀態(tài)的變化，通過對信道的動態(tài)分配，最小化所有AP的鄰居數(shù)目總和和所受干擾總和，同時實現(xiàn)信道之間的負載均衡。

1 信道調(diào)整算法

1.1 算法方案

網(wǎng)絡整體采用集中式的無線局域網(wǎng)架構(gòu)［9，10］，接入點(access point，AP)直接或通過二層 (三層交換機)與集中式設備 (AP controler，AC)相連，動態(tài)信道調(diào)整算法運行在AC上。AC與眾多AP之間通過CAPWAP協(xié)議［11］進行通信，AC可以有效的對網(wǎng)絡中各個AP的工作狀態(tài)和調(diào)整結(jié)果進行監(jiān)控，每經(jīng)過一個信息搜集周期，便通過CAPWAP控制隧道，將信息搜集指令下發(fā)到各個AP，各個AP依次搜集自身的鄰居信息 (鄰居AP名稱、接受功率)，將這些信息通過數(shù)據(jù)隧道上傳給AC進行信息的匯總和整理，由AC構(gòu)建相關(guān)數(shù)據(jù)結(jié)構(gòu)來維護網(wǎng)絡全局信息。

每經(jīng)過一個信道調(diào)整周期或者當前網(wǎng)絡狀態(tài) (網(wǎng)絡拓撲結(jié)構(gòu)、AP所受干擾等)發(fā)生變化時，AC便搜集和讀取全局狀態(tài)信息，執(zhí)行信道調(diào)整算法，得出各個AP的信道調(diào)整決策，通過CAPWAP控制隧道將決策下發(fā)至相應AP，AP執(zhí)行下發(fā)的決策，對自身信道進行調(diào)整。

1.2 算法步驟

如圖1所示，各個AP將攜帶有自身信息的beacon幀在各信道上依次發(fā)出，同時在各信道上輪詢偵聽自己的周邊網(wǎng)絡狀態(tài)，生成本AP在各個信道的鄰居關(guān)系表，此表包含有:本AP的鄰居都包括哪些AP以及本AP收到相鄰AP發(fā)出的信號功率大小。AC搜集各個AP的鄰居關(guān)系表，表中鄰居數(shù)目是指該AP能夠感知到多少AP，指示了該AP能夠被多少AP所干擾，接受功率總和用來指示該AP受到相鄰AP信號干擾的大小程度，這2項指標是進行動態(tài)信道調(diào)整的重要判據(jù)。

圖1 算法步驟流程

算法運行需要下列參數(shù):

初始信道CH_INIT:AP初始時設置的信道。

目標信道CH_AIM:AP節(jié)點將要調(diào)整至的信道。

信道標記FLAG:區(qū)分AP發(fā)出beacon幀時的信道為工作信道 (FLAG為1)還是檢測信道 (FLAG為0)。

接受功率Pr:AP接收到相鄰AP發(fā)出的Beacon幀的信號功率。

鄰居數(shù)目NEI_NUM:根據(jù)監(jiān)聽到的Beacon幀來累計得到。

反向鄰居數(shù)目REV_NEI_NUM:AC根據(jù)反向鄰居表來計算得到。

接受功率總和SUM_PR:根據(jù)鄰居關(guān)系表計算得到。

反向接受功率總和SUM_REV_PR:根據(jù)反向鄰居關(guān)系表計算得到。

鄰居數(shù)目閾值NEI_NUM_MAX:對所有AP的NEI_NUM取均值 (向下取整)得到。

接受功率總和閾值SUM_PR_MAX:對所有AP的SUM_PR取均值得到。

信道調(diào)整次數(shù)Ci:APi進行連續(xù)信道調(diào)整的次數(shù)。

信道調(diào)整次數(shù)閾值R:AP的信道調(diào)整次數(shù)Ci的閾值。

算法運行周期T:由整個網(wǎng)絡的信息搜集、匯總、算法決策和執(zhí)行耗時總和來確定。

算法運行過程如下:

(1)一個新的信道調(diào)整周期T開始。

(2)設共有n個 AP節(jié)點，依次編號為 AP0，AP1，……，APn－1。對每個APi執(zhí)行 (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發(fā)出的信標幀，若信號強度達到接受功率閾值，則NEI_NUM加1，此時AP在beacon幀中可以獲取鄰居AP的MAC地址、信噪比、接收信號強度等相關(guān)信息，由beacon幀中的信道標記FLAG可判斷當前鄰居為實際鄰居或是潛在鄰居。這樣依次遍歷所有的信道，然后再返回自己當前的工作信道，繼續(xù)為STA繼續(xù)正常通信服務，這樣APi可以在對自身通信業(yè)務影響極其微小的情況下，搜集到所有信道的鄰居信息。

(4)信道偵聽周期結(jié)束后，所有AP將自身在各個可行信道的鄰居信息通過CAPWAP數(shù)據(jù)隧道上傳到AC處進行匯總。

(5)AC搜集到所有AP的鄰居信息后，建立全局鄰居關(guān)系表，并由此計算得出反向鄰居關(guān)系表，反向鄰居表提供該AP被哪些AP識別為鄰居以及對反向鄰居AP所造成的干擾大小。

(6)對各AP節(jié)點，按照優(yōu)先對所受干擾量大的AP進行調(diào)整的原則，以鄰居數(shù)目為依據(jù)，對AP在工作信道中鄰居數(shù)目NEI_NUM由大到小進行排序，依次加入信道調(diào)整列表，執(zhí)行 (7)-(10)，執(zhí)行完畢后，轉(zhuǎn) (11)。

(7)若C＞R，則表明當前AP已經(jīng)達到調(diào)整次數(shù)閾值，因此將之列入信道保持組，在信道保持期間不再對其進行信道調(diào)整，超出保持時間后，重新參加信道調(diào)整，轉(zhuǎn)(6);若C ＜=R，轉(zhuǎn) (8)。

(8)①若NEI_NUM ＜NEI_NUM_MAX，表明APi在當前信道所受相鄰AP干擾相對較小，暫時不需要對其進行信道調(diào)整;轉(zhuǎn) (6);②若NEI_NUM ＞=NEI_NUM_MAX，則表明APi在當前信道所受相鄰AP干擾過大，需要對其進行信道調(diào)整。

(9)首先確定當前AP的目標信道列表，再依次對個目標信道是否適合切換進行判定，若適合，將之確定為切換信道，進行信道的切換，對其余目標信道則不再進行判定。

目標信道的選擇標準:選取在所有信道中存在的實際鄰居數(shù)目最少的信道，當2個信道鄰居數(shù)目相等時，對節(jié)點在該信道能接收到的實際信號總功率進行由小到大排序，根據(jù)排序的結(jié)果，將之添加入目標信道列表。

目標信道是否適合切換的判定原則 (需同時滿足下面兩條):①AP在工作信道的鄰居數(shù)目減去目標信道的鄰居數(shù)目 ＞=AP在目標信道的反向鄰居數(shù)目減去在工作信道的反向鄰居數(shù)目。意即AP所受干擾AP減少的數(shù)量必須大于受AP所干擾的AP增加的數(shù)量，這樣從總體上減少相互干擾的AP的數(shù)量。②AP在工作信道的干擾總量減去目標信道的干擾總量 ＞=AP在目標信道的反向干擾總量減去在工作信道的反向鄰居干擾總量。意即AP所受干擾功率減少的總量必須大于受AP所干擾的功率減少的總量，這樣從總體上減少AP間的功率干擾總量。

(10)若本次對當前AP進行了信道調(diào)整，AP信道調(diào)整成功后，知會AC，AC根據(jù)調(diào)整的結(jié)果對鄰居關(guān)系列表和反向鄰居關(guān)系列表中涉及到AP信道變動的標志位予以更新，對Ci加1;轉(zhuǎn) (6)。

(11)本次調(diào)整周期完畢。

(12)等待時間T后本次AP上報的信息與上一周期有變化或者當網(wǎng)絡信息發(fā)生改變 (如有新的AP加入、現(xiàn)有AP出現(xiàn)設備故障)的時候，AC啟動新的算法調(diào)整周期。

2 仿真實驗

2.1 實驗參數(shù)設置

AP的發(fā)射功率和信號接受門限值等參數(shù)，若不進行設置，NS2會使用默認的參數(shù)值，這些值在ns-default.tcl文件中有定義，ns2將之初始化為:CPThresh為 10倍，RXThresh為3.652e-10W，Pt為0.28183815W。

傳輸模型、物理層、MAC層協(xié)議、接口隊列、鏈路層、天線類型等參數(shù)，由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

其它諸如信道調(diào)整周期、鄰居數(shù)目、采用信道、接受功率等參數(shù)，在信道調(diào)整算法代碼中初始化，部分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 實驗結(jié)果

圓圈表示AP的無線傳輸范圍，初始狀態(tài)所有AP均采用channel 1，經(jīng)過全局信息搜集和處理后，AC可以獲取整體網(wǎng)絡狀態(tài)，對AP進行動態(tài)的信道分配。

實驗1:

如圖2所示，算法動態(tài)的調(diào)整了AP2和AP3至channel6和channel11，AP2和AP3的信道調(diào)整減小了相鄰AP信號競爭和干擾的存在，3個信道的AP數(shù)量均為1，實現(xiàn)了AP在信道間的均衡分布。

如圖3所示，算法動態(tài)的調(diào)整了AP2和AP3至channel6和channel11，AP2和AP3的信道調(diào)整減小了相鄰AP信號競爭和干擾的存在，3個信道的AP數(shù)量分別為:2、1和1，實現(xiàn)了AP在信道間的均衡分布。

圖2 動態(tài)信道調(diào)整仿真效果

實驗2:

圖3 動態(tài)信道調(diào)整仿真效果

如圖4所示，算法對新加入的AP進行了動態(tài)的調(diào)整，上述AP的信道調(diào)整減小了相鄰AP間同頻信號競爭和干擾的存在，3個信道的AP數(shù)量均為3，實現(xiàn)了AP在信道間的均衡分布。

實驗3:

在實驗2調(diào)整結(jié)束的基礎上新增加5個AP，與原有4個AP呈三行三列排布。

圖4 動態(tài)信道調(diào)整仿真效果

3 結(jié)束語

本文研究了WLAN密集部署下的AP間干擾問題，在研究各類算法的基礎上，給出了一種集中式WLAN架構(gòu)下的動態(tài)信道分配算法，該算法可以減輕AP的存儲和計算負擔，算法運行之前無需預知AP的位置，可根據(jù)網(wǎng)絡狀況變化及時進行信道調(diào)整，在減少AP間干擾的同時，實現(xiàn)了基于AP數(shù)量的信道間負載均衡，NS2仿真結(jié)果表明該算法是簡單有效的。但是實際應用中需要考慮的因素會更多一些，例如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協(xié)議的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網(wǎng)絡MAC分割方案的設計與實現(xiàn) ［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體系結(jié)構(gòu)通信協(xié)議［J］.計算機工程，2008，34(22):115-117.］