摘 要：本文介紹了一種無線局域網(wǎng)中分布式動態(tài)信道分配的算法。該算法是為了適應(yīng)組網(wǎng)發(fā)展，設(shè)計出的一種在分布式環(huán)境下運行的信道分配算法。由于無線技術(shù)的發(fā)展，同一網(wǎng)絡(luò)下會存在大量的無線接入點，傳統(tǒng)的信道分配算法在這時候就會突顯出時間復(fù)雜度高的問題。本文通過引入社區(qū)劃分的算法，將網(wǎng)絡(luò)進行分解，在各子網(wǎng)絡(luò)中進行信道分配，從其他的角度一定程度上解決了時間復(fù)雜度的問題。通過NS2模擬仿真，證實了該算法的可行性，可以明顯減少信道調(diào)整的時間。

關(guān)鍵詞：WLAN；動態(tài)信道分配；社區(qū)劃分

1 引言

隨著無線網(wǎng)絡(luò)技術(shù)的發(fā)展，無線局域網(wǎng)的應(yīng)用也獲得了長足的發(fā)展。但是無線局域網(wǎng)也有一定的局限性，其只能工作在2.4GHz和5GHz網(wǎng)絡(luò)，在2.4G網(wǎng)絡(luò)，只規(guī)劃了13條信道，而且考慮到信道之間的重疊，一般只選用1，6，11三條無重疊區(qū)域信道；而5GHz頻段則存在雷達信號，需要得到授權(quán)才能使用[1]。這就導(dǎo)致了信道資源就成為一種稀缺資源，怎樣優(yōu)化信道分配成為無線局域網(wǎng)發(fā)展的一個重大問題。

一些機構(gòu)提出了一些分布式算法來實現(xiàn)動態(tài)信道分配，但是其都是在AP端進行功能修改來實現(xiàn)算法。在實際組網(wǎng)中，一般采用AC+Fit AP的架構(gòu)。AP負(fù)責(zé)對時延敏感的數(shù)據(jù)的處理，而其他的功能都放在了AC來實現(xiàn)。增加AP的功能顯然與目前的架構(gòu)不一致。設(shè)計一種符合實際應(yīng)用的信道分配算法顯然具有十分重要的意義。通過對射頻管理中信道分配算法的分析，執(zhí)行一次信道分配的過程所需的時間復(fù)雜度為O（n3），其中n為網(wǎng)絡(luò)中AP的數(shù)量。借鑒社區(qū)劃分的方法，通過社區(qū)劃分減小組網(wǎng)規(guī)模，從而實現(xiàn)組間并行信道分配。這從另外的角度達到了降低時間復(fù)雜度的目的。

2 復(fù)雜網(wǎng)絡(luò)社區(qū)劃分

2.1 相關(guān)研究

復(fù)雜網(wǎng)絡(luò)社區(qū)的研究由來已久，近年來日益受到來自物理學(xué)和計算機科學(xué)領(lǐng)域的科研人員的廣泛關(guān)注。目前存在幾個代表性的算法，有Kernighan-Lin算法、基于Laplace圖特征的譜平分法、W-H算法、GN算法、Newman快速算法等[2]。

現(xiàn)在多數(shù)算法都是對無權(quán)網(wǎng)絡(luò)的研究，但是在眾多的網(wǎng)絡(luò)中，不只是二元體，除了有或無的特性，還包括記錄節(jié)點間相對關(guān)系的權(quán)重。對加權(quán)網(wǎng)絡(luò)的研究，對很多實際問題具有更現(xiàn)實的意義。本文中的無線局域網(wǎng)就可以抽象成一個加權(quán)網(wǎng)絡(luò)，權(quán)重為各AP節(jié)點間的RSSI強度。因為RSSI是一個負(fù)值，所以需要經(jīng)過轉(zhuǎn)換，轉(zhuǎn)成正值。

2.2 模塊度指標(biāo)Q

因為社區(qū)劃分的結(jié)束條件沒有明確規(guī)定，所以Newman等人經(jīng)過研究提出了用來衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)——模塊度Q[3]。

上式為加權(quán)網(wǎng)絡(luò)的Q函數(shù)計算公式，其中Si和Sj表示節(jié)點連接邊的權(quán)重和；W表示所有的邊的權(quán)重之和；Ci和Cj分別表示節(jié)點所在的社團，當(dāng)i=j時，δ（Ci，Cj）=1，否則為0。Q是一個0～1之間的數(shù)，Q=0.3一般被認(rèn)為是一個網(wǎng)絡(luò)具有明顯社團結(jié)構(gòu)的下界。

2.3 Newman貪婪算法（CNM算法）

CNM算法是對Newman快速算法的一些改進。Newman快速算法通過初始的連接矩陣來計算模塊度的增量△Qij，而CNM算法直接構(gòu)造一個模塊度的增量矩陣△Q，然后通過對它的更新來得到最大的一種社團結(jié)構(gòu)。其算法流程如下：1）初始化△Q矩陣，網(wǎng)絡(luò)中每個節(jié)點表示單獨的一個社團結(jié)構(gòu)。2）從△Q矩陣行中選出每行最大元素，構(gòu)成最大堆H。3）根據(jù)最大堆最大元素△Qij，合并相應(yīng)社團。更新△Q，最大堆H等。4）重復(fù)上述兩部，直到△Q矩陣中所有元素都是負(fù)值。

3 動態(tài)信道分配算法設(shè)計

結(jié)合CNM算法，將無線組網(wǎng)抽象成加權(quán)網(wǎng)絡(luò)，對其進行信道分配的算法設(shè)計如下：1）初始化AC中AP信息；2）構(gòu)建AP鄰居拓?fù)潢P(guān)系；3）使用CNM算法對AP信息列表進行網(wǎng)絡(luò)劃分；4）對劃分結(jié)果中各子網(wǎng)分別使用DCA算法進行信道分配。

4 實驗結(jié)果

本文實驗數(shù)據(jù)使用基于模塊度生成（Tunable Modularity Graph Generator）算法生成了10組數(shù)據(jù)，在NS2平臺上使用這十組數(shù)據(jù)分別對不使用社區(qū)劃分的算法和使用社區(qū)劃分的算法進行了測試，測試結(jié)果如下：

5 實驗結(jié)論

本文借鑒網(wǎng)絡(luò)科學(xué)中的社團劃分思想，采用CNM算法對AP實現(xiàn)分組，在組內(nèi)進行動態(tài)信道分配。最后，進行了相關(guān)測試，通過測試的結(jié)果可以明顯地發(fā)現(xiàn)信道調(diào)整時間縮短。

[參考文獻]

[1]王靜.無線局域網(wǎng)的分布式自適應(yīng)動態(tài)信道分配算法的研究.上海：上海交通大學(xué)，2008.

[2]劉發(fā)升，羅延榕.基于多種群遺傳算法的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn).計算機應(yīng)用研究，2012，29（4）.

[3]M E J Newman，Girvan M.Finding and evaluating community structure in networks[J].Physical Review E，2004，69（2）：026113.

[4]汪小帆，劉亞冰.復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)算法綜述.電子科技大學(xué)學(xué)報，2009，38（5）.

[5]M E J Newman.Analysis of weighted networks.Physical Review E，2004，70：056131.