郗劍亮，李金寶

（1.黑龍江大學 計算機科學技術(shù)學院，哈爾濱 150080；2.黑龍江省數(shù)據(jù)庫與并行計算重點實驗室，哈爾濱 150080）

0 引 言

近年來，隨著無線通信技術(shù)和移動計算技術(shù)的迅猛發(fā)展，使得具有大容量、高速率、覆蓋范圍廣的無線Mesh網(wǎng)絡在各個領域得到廣泛應用[1]。無線Mesh網(wǎng)絡又稱為無線網(wǎng)格網(wǎng)或者無線網(wǎng)狀網(wǎng)，它融合了無線局域網(wǎng)WLAN和Ad-Hoc網(wǎng)絡的優(yōu)勢，并且在大量部署方面花費成本較低，是無線接入Internet的一個理想解決方案。

無線Mesh網(wǎng)絡是由一些Mesh路由器和Mesh客戶端組成的多跳無線網(wǎng)絡，主要用于擴張Internet的覆蓋范圍，在網(wǎng)絡邊緣為用戶提供最后1km的接入服務。

在無線Mesh網(wǎng)絡中，通過給節(jié)點的Radio分配合適的信道，可以減小網(wǎng)絡通信沖突、降低數(shù)據(jù)傳輸時延，同時實現(xiàn)多對節(jié)點并行收發(fā)數(shù)據(jù)，從而提高網(wǎng)絡吞吐量。

1 相關工作

本文主要研究內(nèi)容為Multi-Radio Multi-Channel（MR-MC）無線Mesh網(wǎng)絡中的信道分配問題。目前針對無線網(wǎng)絡 Multi-Channel的研究，主要集中在MAC層協(xié)議（信道分配）、路由層協(xié)議、跨層協(xié)議和平臺設計上。

現(xiàn)在大多數(shù)無線傳感器節(jié)點配有一個半雙工的無線收發(fā)器即Single-Radio（SR），半雙工的無線收發(fā)器可以根據(jù)需要轉(zhuǎn)換收發(fā)頻率使節(jié)點處于不同的無線信道，但是在某一時刻該收發(fā)器只能使用一種頻率，而且頻率之間的轉(zhuǎn)換需要一定的時間。近期提出的SR-MC信道分配算法針對不同無線網(wǎng)絡的性能指標設計，如網(wǎng)絡吞吐量、時間延遲、公平性和能量有效等[2－3]。

隨著硬件成本的下降，Multi-Radio通信協(xié)議逐漸走入人們的視野?；贛ulti-Radio的通信協(xié)議在提高網(wǎng)絡吞吐量，減少傳輸時延和避免信道沖突等方面的性能均有進一步提高。以往的文章提出了一些對MR-MC的信道分配算法，其主要是對信道干擾、拓撲控制、鏈路容量、負載平衡等方面進行研究[4－5]。

2 系統(tǒng)模型和問題定義

2.1 系統(tǒng)模型

整個無線Mesh網(wǎng)絡定義為一個無向圖G＝（V，E），其中V＝｛v｜v是一個網(wǎng)絡中的節(jié)點｝，E＝｛l｜l＝（u，v），l是點u與點v之間的一條鏈路，u，v∈V｝。

每個節(jié)點ni有Kni個Radio，每個Radio都可以獨立于其它Radio并行收發(fā)數(shù)據(jù)，但是需要有足夠的正交信道，故用C＝｛c｜c是一條信道｝來表示一個正交信道的集合。

圖1是一個拓撲圖，圖2是圖1的沖突圖，圖中的節(jié)點對應于拓撲圖中的邊，在原圖中如果兩條鏈路之間存在有沖突則在沖突圖中對應的兩點之間存在有一條邊。在沖突圖中節(jié)點的度越大表明原圖中的鏈路越容易與其它鏈路發(fā)生沖突。

在無向圖G中如果兩個節(jié)點u，v在通信范圍之內(nèi)，則存在有一條邊l＝（u，v），l∈E。假設每個Radio的通信范圍都是一樣的，而且任意兩個節(jié)點進行通信需要分配相同的信道。若一個節(jié)點的可用Radio數(shù)為0的話，則稱這個節(jié)點是個飽和節(jié)點。

每次通信可分為T個時槽進行，Ls（l，t）＝1表示鏈路l在時槽t上被調(diào)度，為0則表示未被調(diào)度，其中T＝｛1，2，…，t｝，而且假設在整個網(wǎng)絡內(nèi)時槽之間是同步的。

I（l）表示鏈路l的沖突值，與鏈路l在沖突圖中的度成正比。用一個鏈路信道分配矩陣（LCM）來記錄每條鏈路所分配的信道，其數(shù)值為二進制形式，1表示鏈路l分配了信道c，0表示未分配。Load（l，c）表示鏈路l在信道c上的負載，與鏈路l上的數(shù)據(jù)傳輸量成正比。Eload（l）表示鏈路l的期望負載值，這個值是動態(tài)變化的，每當鏈路l上有數(shù)據(jù)傳輸時，Eload（l）的值就會更新。其中：

信道負載矩陣（CLM）用來記錄每個節(jié)點上的信道負載，與鏈路的期望負載值Eload（l）相同，CLM的值也是隨著網(wǎng)絡動態(tài)改變的，則有：

2.2 問題定義

定義F＝｛fl｜fl為鏈路l上的流量｝，W＝｛wl｜wl為鏈路l的權(quán)值，0＜wl≤1｝。

本文的目標是最大化網(wǎng)絡吞吐量，即：

其中a，b，c是集合V中的元素，l是集合E中的元素。

式（4）將最大化網(wǎng)絡吞吐量的目標公式化，通過計算每條鏈路流量與其權(quán)值的積，然后依次相加，從而得到一個對整個網(wǎng)絡吞吐量的近似估計。約束條件（5）說明一條鏈路上的流量是恒定的。約束條件（6）說明整個網(wǎng)絡的流量是守恒的。約束條件（7）說明鏈路上的流量與期望負載之間存在有一定差距。

3 動態(tài)信道分配和鏈路調(diào)度算法

3.1 信道分配

本文提出的算法是一個在線啟發(fā)式算法（LDCA），為了適應網(wǎng)絡中鏈路負載的動態(tài)性，每間隔一定時間算法會自動對網(wǎng)絡重新進行一次信道分配。

算法1信道分配算法1 . 輸入：G ＝（V，E），Eload（l），I（l），K，C，CLM 2. 輸出：鏈路信道分配矩陣LCM 3 . 初始化：LCM＝0，E′＝E 4. 對E′中的鏈路按期望負載Eload（l）降序排列，如果負載相同則按鏈路沖突值I（l）降序排列5 . while E′非空6 . 取出E′中的第一條鏈路l＝（u，v），E′＝E′－｛l｝7. if節(jié)點u和節(jié)點v都未達到飽和狀態(tài)8. 從u，v兩個節(jié)點的空閑信道集合C中選一條公共空閑信道c分配給該鏈路9 . Cu＝Cu－｛c｝，Cv＝Cv－｛c｝10. Ku－－，Kv－－11. else if節(jié)點u和節(jié)點v中有一個節(jié)點達到飽和／／假設u節(jié)點飽和12. 選出CLM中節(jié)點u負載最小的信道c 13. if點v的空閑信道集合Cv中包含有此信道14. 把信道c分配給該鏈路15 . Cv＝Cv－｛c｝16. else選出CLM中u，v兩節(jié)點負載和最小的信道c分配給該鏈路17. end if 18. Kv－－19. else節(jié)點u和節(jié)點v都已達到飽和狀態(tài)的話20. 選出CLM中u，v兩節(jié)點負載和最小的信道c分配給該鏈路21 . LCMl，c＝122. end if 23.end while 24.Eload＝Eload＊α 25.CLM＝CLM＊β

3.2 鏈路調(diào)度

當算法1根據(jù)網(wǎng)絡動態(tài)需求進行信道分配之后，為了使網(wǎng)絡中的資源能夠有效利用，需要繼續(xù)進行鏈路調(diào)度算法。該鏈路調(diào)度算法運用了一種貪心的鏈路覆蓋策略，每次選擇調(diào)度個數(shù)最多且不相互沖突的鏈路，從而提高了網(wǎng)絡的吞吐量。

算法2鏈路調(diào)度算法1 . 輸入：G ＝（V，E），I（l），LCM 2. 輸出：鏈路調(diào)度結(jié)果LS 3. 初始化：E′＝E，時槽數(shù)t＝0，Ls（l，t）＝0，A＝空集，B＝空集4. 對E′中的鏈路按期望負載Eload（l）降序排列，如果負載相同則按鏈路沖突值I（l）降序排列5 . while E′非空6. A＝空集7. 取出E′中的第一條鏈路l，E′＝E′－｛l｝，A＝A∪｛l｝8 . for l′ ∈E′9 . if l′與A中的任一鏈路均不沖突10 . E′＝E′－｛l′｝，A＝A∪｛l′｝11. end if 12. end for 13 . for l′∈A 14 . Ls（l′，t）＝115. end for 16 . for l′∈B 17. if l′不與A中任一鏈路沖突18 . Ls（l′，t）＝119. end if 20. end for 21. B＝B∪A 22. t＋＋23.end while

4 實驗結(jié)果與分析

用模擬實驗來評估本文提出的在線啟發(fā)式信道分配算法LDCA。通過與靜態(tài)信道分配算法（SCA）和動態(tài)信道分配算法（DCA）相比較，證明了LDCA算法的優(yōu)越性以及考慮網(wǎng)絡流量動態(tài)變化的重要性。

由圖3可見，SCA算法與DCA算法傳輸時延隨著網(wǎng)絡流量的增加而增加，LDCA算法則是先減小后增加，且LDCA算法和DCA算法的傳輸時延明顯小于SCA算法。這是因為LDCA算法能夠動態(tài)適應網(wǎng)絡中鏈路需求的變化，從而減少了傳輸時延。

由圖4可見，LDCA算法不存在沖突，因為該算法已經(jīng)在信道分配和鏈路調(diào)度過程中避免了沖突。DCA算法通過控制信道進行數(shù)據(jù)信道的分配，有可能存在隱終端問題導致沖突，但是發(fā)生概率較低。SCA算法是在數(shù)據(jù)開始傳輸之前根據(jù)網(wǎng)絡拓撲靜態(tài)對鏈路進行信道分配，分配之后不能根據(jù)網(wǎng)絡的現(xiàn)有狀況進行調(diào)整，所以沖突概率較高。

圖6 網(wǎng)絡吞吐量與節(jié)點個數(shù)的關系Fig.6 Relationship between the network throughput and the number of nodes

在圖5的實驗中采用網(wǎng)格狀拓撲結(jié)構(gòu)，主要反映了Radio和信道數(shù)量與網(wǎng)絡吞吐量之間的關系。隨著Radio個數(shù)和信道個數(shù)的增加，網(wǎng)絡的吞吐量呈增長趨勢，其中LDCA算法的網(wǎng)絡吞吐量增長比較明顯。在節(jié)點個數(shù)固定的情況下，增加Radio和信道數(shù)量，能夠提高網(wǎng)絡并行傳輸數(shù)據(jù)的能力，進而增加網(wǎng)絡吞吐量。

圖6的實驗拓撲結(jié)構(gòu)為范圍固定的隨機拓撲結(jié)構(gòu)，模擬了網(wǎng)絡中節(jié)點密度對網(wǎng)絡吞吐量的影響。由圖6可見，隨著節(jié)點個數(shù)的增加，LDCA、DCA和SCA算法的網(wǎng)絡吞吐量都有相應的提高。這是因為在一定通信范圍內(nèi)，如果網(wǎng)絡中節(jié)點個數(shù)增加，可用鏈路數(shù)量也會相應增長，從而使得網(wǎng)絡吞吐量提高。

5 結(jié) 論

本文重點研究了多Radio多信道無線Mesh網(wǎng)絡中的信道分配問題，針對這個NP難問題，文章將抽象的變量轉(zhuǎn)化為具體的網(wǎng)絡模型，隨后提出了一種基于鏈路權(quán)值優(yōu)先的在線啟發(fā)式信道分配算法LDCA。該算法在信道分配階段采用了啟發(fā)式的思想，能夠動態(tài)適應鏈路需求，提高系統(tǒng)容量；在鏈路調(diào)度階段采用分時的策略，將沖突的可能性降到最低。最后通過模擬實驗與分析，得出LDCA算法可以顯著減少網(wǎng)絡傳輸時延，增加網(wǎng)絡吞吐量，同時降低網(wǎng)絡中的沖突。

[1]李建中，李金寶，石勝飛.傳感器網(wǎng)絡及其數(shù)據(jù)管理的概念、問題與進展 [J].軟件學報，2003，14（10）：1717-1727.

[2]G.Zhou，C.Huang，T.Yan，et al.MMSN：multifrequency media access control for wireless sensor networks[A].INFOCOM 2006.25th IEEE International Conference on Computer Communications [C].Proceedings，2006：1-13.

[3]Yafeng Wu，J.A.Stankovic，Tian He，et al.Realistic and efficient multi-channel communications in wireless sensor networks[A].INFOCOM 2008.The 27th Conference on Computer Communications [C].IEEE，2008：1193-1201.

[4]Hua Yu，Mohapatra P.，Xin Liu.Dynamic channel assignment and link scheduling in multi-radio multi-channel wireless mesh networks[A].Mobile and Ubiquitous Systems：Networking ＆Services，2007.MobiQ-uitous 2007.Fourth Annual International Conference on[C].2007：1-8.

[5]Krishna Ramachandran，Irfan Sheriff，ElizabethM Belding.A multi-radio 802.11mesh network architecture[J].Mobile Networks and Applications，2008，13（4）：132-146.