基于連通性的動態固定信道分配算法

尹鳳杰，梅丙乾，楊 暉，張 穎

(遼寧大學 信息學院，遼寧 沈陽 110036)

基于連通性的動態固定信道分配算法

尹鳳杰，梅丙乾，楊 暉，張 穎

(遼寧大學 信息學院，遼寧 沈陽 110036)

隨著跳數的增加，無線Mesh網絡的延遲開始增大，吞吐量開始降低，QoS難以得到保證.基于多信道多接口的信道分配策略可以很好地解決上述問題，但目前對多信道Mesh網絡的研究往往忽視了節點之間的連通性問題.在原有的寬帶優先搜索(BFS,Breadth First Search)算法的基礎上，針對動態固定信道分配(DFCA,Dynamic Fixed Channel Allocation) 算法進行研究，在保證連通性的前提下，為每個節點動態的分配固定信道，減少了鏈路之間干擾，提高了傳輸效率，同時考慮了新加入節點以及失效節點帶來的問題.仿真結果表明，在發送速率較大、數據流數較多的情況下，DFCA算法較傳統算法在吞吐量方面得到很大提高.

Mesh網絡；多信道；多接口；動態分配；固定信道

0 引言

無線Mesh網絡(WMN,Wireless Mesh Network)是一種新型的無線網絡技術，與傳統無線網絡相比，WMN具有組網靈活、覆蓋率高、容量大、前期投資少等諸多優點，近年來已成為研究的熱點.隨著WMN的研究與深入，其中的問題也慢慢暴露出來，最嚴重的問題是隨著跳數的增加，WMN的延遲開始增大，吞吐量開始降低，QoS也變得難以得到保證.同時隨著用戶對WMN傳輸數據量和傳輸業務多樣化需求的增大，現有的單信道單接口的結構已經滿足不了多業務的需求，而多信道多接口的無線Mesh網絡節點可以工作在相互之間并不干擾的正交信道上，極大地提高了WMN的傳輸速率和網絡的容量，較好地解決了無線網絡中存在的隱藏終端和暴露終端問題[1-2].

對于WMN制定合理的信道分配策略一直是多信道多接口WMN研究的重點，國內外學者做了很多研究工作.文獻[3]分析了多信道多接口技術近年來在無線傳感器網絡中的應用，得出結論利用該技術可以有效地減少干擾并降低信道沖突，增加網絡容量.文獻[4]提出一種為所有節點分配相同信道的方案(CCA)，這種方案沒有充分利用多信道的優勢，且帶來了很大的干擾.文獻[5]提出了一種差異信道的分配方案，為不同節點分配不同的信道，在一定程度上降低了信道之間的干擾，但是該方案中信道的分配是固定的，破壞了網絡的連通性.文獻[6]在車載自組織網絡中合理的實現了多接口多信道，提出了一種基于通信雙方車輛節點信道切換隊列的動態信道分配方法，較好地解決了車輛節點間通信信道的動態分配以及信道公平接入和分配不合理的問題，但該方案中沒有考慮信道的獨立性和干擾問題.文獻[7]提出一種最小干擾的信道分配策略(MICA)，該方法充分考慮流量、距離、接口數等因素確定節點的優先級，并以此來進行信道的分配.文獻[8]將最優信道帶寬調制與多信道多接口技術相結合提出分布式流量感知的信道帶寬調制，有效增加了頻譜使用效率并提高了網絡性能，但該方法并沒有考慮信道的優化問題.文獻[9]將多信道多接口應用到多播信道分配中，可以使無線Mesh網絡的干擾程度最小化，并最大化網絡吞吐量，但該算法沒有考慮在實際無線路由器中可能存在增加、刪除和移動以及多播成員可能自由地加入和離開多播組等動態情況，即沒有考慮信道重新分配問題.文獻[10]從多信道多接口無線Mesh網絡傳輸容量入手，提出拓撲可靠性約束下的邏輯拓撲設計方法，以拓撲可靠性及網絡路徑跳數為約束條件，以最大容量最小干擾為優化目標，進而得到優化的邏輯拓撲.

針對現有研究存在的問題，本文提出一種基于連通性的動態固定信道分配策略，為節點動態的分配固定信道，固定信道用于數據的接收，備用信道處于“待接收”狀態，隨時準備用于數據的接收，其余信道為可切換信道，用于數據的發送.同時這三種信道可以在一定條件下相互轉換，保障了網路連通性的前提下提高了網絡吞吐量，降低了信道之間的干擾，并優化了網絡信道的分配.

1 WMN干擾模型及圖論模型

1.1 干擾模型

在WMN中由于復雜的無線環境，信道之間的相互干擾十分嚴重，網絡的傳輸速率往往只能發揮其最大帶寬的一部分.此外，WMN中的流量走向具有很大的不確定性，在某一階段很容易出現某個或某些節點負載過重的問題，形成網絡的瓶頸.

WMN中存在各種類型的干擾，根據業務流的不同可劃分為流內干擾和流間干擾[11]，本文重點對流內干擾和流間干擾進行研究.

流內干擾(Inter Interference)是指在同一流的傳輸路徑上傳輸的數據如果工作在同一信道上則由于相互競爭而會產生干擾.流間干擾(Intra Interference)是指不同流的傳輸路徑如果和相鄰傳輸路徑工作在同一信道上則兩者之間會產生影響.

由于WMN的環境較為復雜，對每個節點的SINR計算也是一個復雜和龐大的工程，同時由于背景噪聲的不斷變化，每個節點的SINR也處在動態變化之中，尤其是對于臨界值的情況很難進行準確的處理，所以在研究中通常不采用物理干擾模型，而是采用協議干擾模型.

假設一個WMN由N個節點組成，現進行如下定義：

ni：WMN中的第i個節點，且1≤i≤N.

di,j：節點i和節點j之間的距離.

Rt：節點的傳輸距離，是兩個節點在沒有干擾的情況下能夠通信的最大距離.

Ri：節點的干擾距離，是對其他節點帶來干擾的有效距離，通常是Rt的2.2倍，默認所有節點的Rt、Ri都是一樣的.

Ci：節點i可用的信道.

CUi：節點i正在使用的信道.

則節點j能夠接收到節點i發送的數據需要滿足以下條件：

di,j≤Rt，即兩個節點之間的距離小于節點的傳輸距離.

?k∈Ck,k∈Ci且k∈Cj，即兩個節點之間存在相同的信道

?/m≠i,j,CUm=CUi且CUm=CUj，dm,j≤Ri，即不存在節點m，使得m正在使用和i，j相同的信道，且m，j之間的距離小于干擾距離.也就是只有m正在使用和i，j相同的信道且m，j之間的距離小于干擾距離時，m才會對j產生干擾.

協議干擾模型其實就是一種邏輯的是非關系[12]，只要滿足上述三個條件節點j能夠接收到節點i發送的數據.由于WMN中節點弱移動性的特點，兩個節點之間的距離一般是固定的，可能對其產生干擾的節點在不在其干擾范圍內也是確定的，在進行算法研究時只需重點考慮信道問題即可，很適合WMN信道干擾問題的研究，如無特殊說明 則本文采用的是協議干擾模型.

1.2 圖論模型

采用圖論方式為WMN建立模型，通常認為所有節點都處在同一平面上，且各節點的傳輸距離Rt和干擾距離Ri都是相同的.

假設WMN中有m個可用的正交信道c={1,2,3,4…m}；Ii是節點i處的接口數，且1≤Ii≤m,如果兩個節點在彼此的傳輸距離內，將信道分配給各個節點形成鏈路以后所有節點和鏈路就構成了網絡拓撲G=(V,E)，其中V表示節點，E表示分配給節點之間的鏈路，這樣就構成了連接圖，連接圖很好地表明了節點和信道之間的關系，但是節點之間的鏈路是否產生干擾不易從連接圖上看出，如圖1就是一個連接圖.

在連接圖的基礎上，可以得到WMN的沖突圖G′=(V′,E′)，其中V′表示節點之間的鏈路，如果兩條鏈路之間存在干擾，則代表兩條鏈路之間存在一條邊，這些邊組成集合E′.

假設圖1連接圖中的沖突域為2跳范圍，則可以得到圖2的沖突圖.

沖突圖很好地表明了鏈路之間的干擾關系，很適合WMN信道干擾的研究，結合協議干擾模型，本文采用上述假設，認為沖突域為2跳范圍.

2 動態固定信道分配算法

2.1 BFS信道分配算法

當一個多接口多信道的節點A需要通信時，它的鄰居節點至少要感知到節點A的一個信道才能正常通信，尤其是對于節點A是新加入節點的情況下.目前國內外研究的重點往往在于人為的將信道分配給兩個節點，而兩個節點之間如果彼此無法感知到對方的話是無法正常進行信道分配的.

對此文獻[13]提出一種基于感知的信道分配算法，為每一個節點分配兩種接口，一個用于固定信道傳輸，其余的用于可切換信道傳輸，節點對數據的接收是通過固定信道完成的， 具體內容如下：

每個節點維護一個鄰居表和信道使用表，鄰居表用以記錄鄰居節點固定信道的使用情況，信道使用表記錄2跳以內鄰居各個信道使用數量的情況，同時每個信道維護一個如圖3所示的包隊列.

圖1 連接圖

圖2 沖突圖

圖3 包隊列

每個節點定期的向鄰居節點發送一個Hello包，由于使用多信道，在某個信道上發送的Hello包只會被正在使用該信道的節點接收到，所以節點需要在每一個可用信道上發送Hello包.Hello包包含了節點固定信道的使用情況和節點當前的鄰居表，當一個節點收到鄰居節點發送的Hello包時，節點根據包中鄰居節點固定信道使用情況來更新自己的鄰居表和信道使用表.當一個新的節點加入時，它不會和其他節點進行通信，直到這個節點在每一個信道上發送了自己Hello包.一個節點A將數據包發送給鄰居節點B的具體流程如下：

1)節點A查詢并更新自己的鄰居表，找到節點B的固定信道使用情況.

2)若找到節點B的固定信道信息則將數據加入到節點B正在使用的固定信道的隊列上等待傳輸.

3)若查找不到節點B的固定信道使用情況則進行等待，若超過設定的閾值則停止本次發送，同時將該數據在隊列上清除.若在閾值范圍內收到來自節點B的Hello包則進行步驟(2).

4)進行數據的發送，如果數據發送成功則結束本次數據傳輸，將數據從隊列上清除；如果數據發送失敗則進行步驟(1)，直至超時；超時則停止本次發送，同時將該數據在隊列上清除.

以上算法適合于網絡流量比較均衡的情況，但是WMN中存在著中心流量的情況，即某一時刻流量集中流向某個節點或某一時刻流量從某個節點流出，如圖4所示當某個節點流量集中流出時，該算法可以充分發揮多信道的優勢.假設節點A為中心節點，節點B、C、D、E為鄰居節點，節點A、B、C、D、E的固定信道分別為信道a、b、c、d、e，流量是從中心節點流向鄰居節點，則根據上述算法，節點A分別使用信道b、c、d、e同時發送數據，極大地提高了傳輸速率.然而當流量集中流向中心節點時，如圖5所示，根據上述算法節點B、C、D、E都使用信道a傳輸數據，相當于是單信道傳輸，并沒有發揮多信道的優勢，基于上述原因，本文提出動態固定信道的信道分配算法DFCA(Dynamic Fixed Channel Allocation Algorithm).

圖4 流量從中心節點流出

圖5 流量從中心節點流入

2.2 DFCA信道分配算法

在原來的信道分配算法中，每個節點只有一個固定信道，其他節點如果需要向該節點傳輸數據則使用該節點的固定信道進行傳輸，當多個節點需要和該節點進行通信時則需要競爭使用信道.本文為節點動態的配置固定信道，設置多個固定信道和一個備用的信道，為節點配備信道的具體算法如下：

1)節點在發送Hello包之前先檢查自己備用信道使用情況，并查詢自己的信道使用表.如果備用信道正在被使用，則在信道使用表中挑選一個使用數量最少的信道作為自己新的備用信道，原來的備用信道轉換為固定信道；如果檢查到自己的固定信道存在空閑的情況，將這些信道以及備用信道的使用數進行比較，挑選一個數值最小的作為備用信道，其余信道成為普通的可切換信道，以上信息都會被加入到Hello包中發送出去.

2)如果增加的固定信道數量達到一定的閾值則不再進行增加，同時在固定信道中選擇使用數量最少的信道作為備用信道.

圖6 DFCA節點分配信道算法流程圖

3)節點收到鄰居節點發送的Hello包以后，根據包中鄰居節點固定信道的使用情況進行查詢，并根據其中的信息更新自己的鄰居表以及自己的信道使用表.具體算法流程圖如圖6所示：

需要特別說明的是節點所有的信道都是空閑即沒有進行數據傳輸時候的情況，假設現在某個節點A有一個固定信道正在通信，備用信道空閑，現在數據傳輸完畢，則在這兩個信道當中選擇一個信道使用數量少的作為備用信道，這時候節點A的Hello表中只存在一個信道就是節點A的備用信道，而沒有任何的固定信道.

同時節點所維護的包隊列的結構也發生了相應的改變.當節點正在進行通信，且節點的固定信道數量并未達到閾值時的包隊列如圖7所示，當節點沒有進行通信時的包隊列如圖8所示，當節點的固定信道達到一定閾值時的包隊列如圖9所示.

當兩個節點之間需要通信，例如節點A向節點B發送數據時，節點A會選擇使用節點B的備用信道進行數據傳輸，具體過程如下：

1)節點A查詢并更新自己的鄰居表，找到節點B的備用信道使用情況.

2)若找到節點B的備用信道信息則將數據加入到節點B正在使用的備用信道的隊列上等待傳輸.

3)若查找不到節點B的備用信道使用情況則進行等待，若超過設定的閾值則停止本次發送，同時將該數據在隊列上清除.若在閾值范圍內收到來自節點B的Hello包則進行步驟(2).

圖7 包隊列情況1

圖8 包隊列情況2

圖9 包隊列情況3

4)進行數據的發送，如果數據發送成功則結束本次數據傳輸，將數據從隊列上清除；如果數據發送失敗則進行步驟(1)，直至超時；超時則停止本次發送，同時將該數據在隊列上清除.

具體算法流程圖10所示：

此時節點B由于備用信道被使用，則會將備用信道轉為固定信道，同時查詢自己的信道使用表，挑選信道使用數最少的信道作為自己新的備用信道直到固定信道數達到一定的閾值，當固定信道數量達到閾值時，從固定信道中挑選信道使用數量最少的做為備用信道.

圖10 節點間通信算法流程圖

圖11 新節點加入算法流程圖

當一個新的節點加入到WMN中時，由于該節點并未指定備用信道，Hello包中的信息為空，其余節點無法發現該節點，更無法與之通信.則該節點在發送自己的Hello包之前先進行監聽，如果在閾值范圍內接收到了來自鄰居的Hello包，則說明是加入已有的WMN，節點會根據收到的Hello包建立起自己的鄰居表和信道使用表，再根據信道使用表的情況進行備用信道的選擇，最后發送自己Hello包加入到網絡當中；如果在閾值范圍內沒有收到任何鄰居節點的Hello包，則說明這是一個全新的WMN，這個節點不必等到收到鄰居節點的Hello包即開始定期廣播自己的Hello包，同時隨機選擇一個信道作為自己初始的備用信道.具體算法流程圖如圖11所示：

當一個舊的節點離開或者失效時，這個節點已經不參與WMN的傳輸，但是該節點還是存在于鄰居節點的鄰居表中.為了解決節點失效的問題，各個節點再發送自己的Hello包時加入一個時間戳，節點設置一個自己的鄰居節點最大存活時間.當節點收到鄰居節點發送的Hello包時就更新存活時間，同時在更新自己的鄰居表時檢查鄰居節點的時間戳，如果超過了最大存活時間則認為該節點已經失效了，將該節點從鄰居表中刪除，再更新自己的鄰居表和信道使用表.具體算法流程圖如12所示.

圖12 節點失效處理流程圖

3 仿真與性能分析

仿真實驗場景設置為1 000 m×1 000 m的范圍內隨機分配50個Mesh節點，所有節點物理層采用IEEE 802.11a協議標準.對于DFCA算法，每個節點配置有3個射頻接口，采用CBR流量模式，分別測試在發送速率、數據流數不同時與BFS算法及經典的DCA算法的比較.

圖13表示CBR發送速率與吞吐量的關系，其中橫坐標表示CBR的發送速率，縱坐標表示WMN的吞吐量.通過對比可以看出，當發送速率較小時，DCA、BFS和DFCA算法并無太大區別，當發送速率稍微有所提升時，DCA的吞吐量立刻出現明顯的衰退，當發送速率提升至7MBPS時，BFS也開始出現衰退的現象而DFCA算法則直到9MBPS時才會衰退，DFCA在高速率傳輸時的吞吐量大約比BFS多15%左右.

圖13 CBR發送速率與吞吐量的關系

圖14 CBR數據流數與吞吐量的關系

圖14表示CBR數據流數與吞吐量的關系，其中橫坐標表示CBR的數據流數，縱坐標表示WMN的吞吐量.通過對比可以看出，當WMN中的數據流較少時，三種分配算法的吞吐量并無太大差別，但是隨著數據流數的增加，DCA算法和BSF算法的吞吐量開始出現衰退，而且BFS算法的衰退程度要明顯大于DCA算法，這是因為BFS算法是基于連通性的，當數據流數增大時，中心節點的問題變得突出，吞吐量受到嚴重限制.而DFCA算法雖然也存在中心節點的問題，但由于其采用了動態固定信道的分配策略，其受影響程度遠遠小于BFS算法.

4 結論

本文在BFS算法的基礎上提出DFCA算法，該算法采用動態固定信道的策略來進行信道的分配，在不改變WMN連通性的前提下靈活動態的分配節點的固定信道，使得節點可以同時使用不同的信道進行數據的接收，很好的解決了中心節點的問題.仿真實驗可以看出DFCA算法性能要優于BFS算法和DCA算法，尤其是節點發送速率變大，數據流數增多的情況下.

[1] So J,Vaidya N.Multi-channel MAC for ad hoc networks:handling multi-channel hidden terminals using a single transceiver[C].ACM International Symposium on Mobile Ad Hoc Networking and Computing，2004:222-233.

[2] 任遠,董淑福,王耀國.數據鏈中隱藏終端問題的幾種解決方法[J].通信技術，2009,20(5):54-56

[3] Wu Y S,Mihaela Cardei.Multi-channel and cognitive radio approaches for wireless sensor networks[J].Computer Communications,2016，94(94):30-45.

[4] Draves R,Padhye J,Zill B.Routing in multi-radio,multi-hop wireless mesh netws[C].Proceedings of the 10th annual international conference on Mobile computing and networking,2004:114-128.

[5] Marina M K,Das S R,Subramanian A P.A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[J].Computer Networks,2010,54(2):241-256.

[6] 張民,德敏,金康.一種多接口多信道VANET動態信道分配算法研究[J].計算機應用研究,2014,31(5):1516-1519.

[7] Subramanian A,Gupta H,Das S R.Minimum interference channel assignment in multi-radio wireless mesh networks[J].IEEE Transactions on Mobile Computing,2008,7(12):1459-1473.

[8] 李禮,張春元.多接口多信道無線網狀網中流量感知的信道帶寬調制算法[J].電子學報,2010,38(4).

[9] 邱振謀,姚國祥,官全龍,等.多信道無線 Mesh網絡的多播信道分配算法[J].計算機工程,2011,37(6):107-109.

[10] 包學才,戴伏生,韓衛占.多接口多信道無線Mesh網絡的邏輯拓撲設計[J].小型微型計算機系統,2015,36(6):1249-1254.

[11] Sandeep Kour Ahuja.Algorithms for routing and channel assignment in wireless infrastructure networks[D].The university of Arizona.2010.04.

[12] GuPta P,Kumar P.The capacity of wireless networks[J].IEEE Transactions on Information Theory，2010,46(2):388-404.

[13] Kyasanur P,Vaidya N H.Routing and link-layer protocols for multi-channel multi-interface Ad Hoc wireless networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2010,10(1):31-43.

(責任編輯鄭綏乾)

DynamicFixedChannelAllocationAlgorithmBasedonConnectivity

YIN Feng-jie,MEI Bing-qian,YANG Hui,ZHANG Ying

(SchoolofInformation,LiaoningUniversity,Shenyang110036,China)

With the increase of hop,delay of WMN began to increase,throughput began to reduce,and the QoS is also difficult to guarantee.In numerous solutions to solve these problems,the channel allocation strategy based on multi-channel multi-interface technology can well solve the interference and the transmission rate problems in traditional WMN.But at present the study of multi-channel WMN tend to ignore the premise of mutual communication between nodes-connectivity.On the basis of the original breadth first search(BFS) algorithm,this paper put forward the dynamic fixed channel allocation(DFCA) algorithm.On the premise of guarantee connectivity,the algorithm allocated fixed channel for each node dynamically,reduced the interference between links,and improved the transmission efficiency.The condition which nodes are new or failure was also considered.Simulation results demonstrate that the algorithm of DFCA can improve the throughput than traditional algorithms in the case of large sending rate and more data flow.

Mesh network;multi-channel;multi-interface;dynamic allocation;fixed channel

TP 393

A

1000-5846(2017)04-0294-08

2017-09-01

遼寧省教育廳科學研究一般項目資助(項目編號：L2015204)

尹鳳杰(1965-)，女，博士，教授，從事無線網絡和通信網絡優化控制研究；梅丙乾，男，碩士研究生；楊暉，女，碩士，副教授；張穎，女，碩士，講師.