郗劍亮，李金寶

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

0 引 言

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

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

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

1 相關(guān)工作

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

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

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

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

2.1 系統(tǒng)模型

整個無線Mesh網(wǎng)絡(luò)定義為一個無向圖G＝（V，E），其中V＝｛v｜v是一個網(wǎng)絡(luò)中的節(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é)點對應(yīng)于拓撲圖中的邊，在原圖中如果兩條鏈路之間存在有沖突則在沖突圖中對應(yīng)的兩點之間存在有一條邊。在沖突圖中節(jié)點的度越大表明原圖中的鏈路越容易與其它鏈路發(fā)生沖突。

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

每次通信可分為T個時槽進行，Ls（l，t）＝1表示鏈路l在時槽t上被調(diào)度，為0則表示未被調(diào)度，其中T＝｛1，2，…，t｝，而且假設(shè)在整個網(wǎng)絡(luò)內(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)絡(luò)動態(tài)改變的，則有：

2.2 問題定義

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

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

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

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

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

3.1 信道分配

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

算法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é)點達到飽和／／假設(shè)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)絡(luò)動態(tài)需求進行信道分配之后，為了使網(wǎng)絡(luò)中的資源能夠有效利用，需要繼續(xù)進行鏈路調(diào)度算法。該鏈路調(diào)度算法運用了一種貪心的鏈路覆蓋策略，每次選擇調(diào)度個數(shù)最多且不相互沖突的鏈路，從而提高了網(wǎng)絡(luò)的吞吐量。

算法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)絡(luò)流量動態(tài)變化的重要性。

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

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

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

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

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

5 結(jié) 論

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

[1]李建中，李金寶，石勝飛.傳感器網(wǎng)絡(luò)及其數(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.