WLAN分布式動態信道分配算法研究

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

關鍵詞：WLAN；動態信道分配；社區劃分

1 引言

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

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

2 復雜網絡社區劃分

2.1 相關研究

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

現在多數算法都是對無權網絡的研究，但是在眾多的網絡中，不只是二元體，除了有或無的特性，還包括記錄節點間相對關系的權重。對加權網絡的研究，對很多實際問題具有更現實的意義。本文中的無線局域網就可以抽象成一個加權網絡，權重為各AP節點間的RSSI強度。因為RSSI是一個負值，所以需要經過轉換，轉成正值。

2.2 模塊度指標Q

因為社區劃分的結束條件沒有明確規定，所以Newman等人經過研究提出了用來衡量網絡劃分質量的標準——模塊度Q[3]。

上式為加權網絡的Q函數計算公式，其中Si和Sj表示節點連接邊的權重和；W表示所有的邊的權重之和；Ci和Cj分別表示節點所在的社團，當i=j時，δ（Ci，Cj）=1，否則為0。Q是一個0～1之間的數，Q=0.3一般被認為是一個網絡具有明顯社團結構的下界。

2.3 Newman貪婪算法（CNM算法）

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

3 動態信道分配算法設計

結合CNM算法，將無線組網抽象成加權網絡，對其進行信道分配的算法設計如下：1）初始化AC中AP信息；2）構建AP鄰居拓撲關系；3）使用CNM算法對AP信息列表進行網絡劃分；4）對劃分結果中各子網分別使用DCA算法進行信道分配。

4 實驗結果

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

5 實驗結論

本文借鑒網絡科學中的社團劃分思想，采用CNM算法對AP實現分組，在組內進行動態信道分配。最后，進行了相關測試，通過測試的結果可以明顯地發現信道調整時間縮短。

[參考文獻]

[1]王靜.無線局域網的分布式自適應動態信道分配算法的研究.上海：上海交通大學，2008.

[2]劉發升，羅延榕.基于多種群遺傳算法的復雜網絡社區結構發現.計算機應用研究，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]汪小帆，劉亞冰.復雜網絡中的社團結構算法綜述.電子科技大學學報，2009，38（5）.

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