喬　宏,張大方,謝　鯤,何施茗,張　繼

(1.　湖南大學(xué)信息科學(xué)與工程學(xué)院,湖南長沙410082;2.長沙理工大學(xué)計算機與通信學(xué)院,湖南長沙410014)

?

多射頻無線mesh網(wǎng)中的聯(lián)合協(xié)作路由與信道分配算法

喬宏1,張大方1,謝鯤1,何施茗2,張繼1

(1.湖南大學(xué)信息科學(xué)與工程學(xué)院,湖南長沙410082;2.長沙理工大學(xué)計算機與通信學(xué)院,湖南長沙410014)

現(xiàn)有的協(xié)作路由算法沒有考慮多射頻無線mesh網(wǎng)中的信道分配問題.為了給多并發(fā)業(yè)務(wù)流提供更優(yōu)質(zhì)的網(wǎng)絡(luò)服務(wù),本文結(jié)合多射頻多信道技術(shù)和協(xié)作通信技術(shù)來降低同信道干擾并獲得協(xié)作分集增益.基于協(xié)作通信模塊虛擬化的方法,本文將聯(lián)合協(xié)作路由和信道分配問題簡化為聯(lián)合直接路由和信道分配問題,將其建模為一個混合整數(shù)線性規(guī)劃問題,并證明該問題為NP-hard問題.為了解決該問題,提出了一種寬松的聯(lián)合協(xié)作路由選擇和信道分配算法(Loose Joint Cooperative Routing and Channel Assignment algorithm,L-JCRCA).仿真實驗結(jié)果表明,L-JCRCA可以有效提升網(wǎng)絡(luò)整體吞吐量.

無線mesh網(wǎng);協(xié)作路由;信道分配

1　引言

作為一種克服信道衰落的有效方法,協(xié)作通信技術(shù)通過將多用戶環(huán)境下的單天線用戶組成虛擬的MIMO (Multiple-Input Multiple-Output)系統(tǒng)來取得空間分集增益.協(xié)作路由則是將物理層協(xié)作通信技術(shù)和網(wǎng)絡(luò)層路由選擇結(jié)合起來的跨層路由方案,它通過選擇合適的協(xié)作中繼結(jié)點參與路由中的某一跳或某幾跳傳輸,提高無線傳輸?shù)娜萘炕蚪档蛡鬏數(shù)哪芎?為無線用戶提供更好的網(wǎng)絡(luò)服務(wù).

相關(guān)的研究表明,相對于傳統(tǒng)路由,協(xié)作路由在增強無線網(wǎng)絡(luò)性能方面具有諸多優(yōu)勢.但是,這些研究大多數(shù)是在沒有考慮無線傳輸干擾下獲得.實際上,由于信道競爭,無線網(wǎng)絡(luò)存在的同信道干擾會造成數(shù)據(jù)的沖突和重傳,嚴重影響網(wǎng)絡(luò)性能.由于協(xié)作結(jié)點的參與,協(xié)作通信在帶來分集增益的同時會增加額外的同信道干擾,導(dǎo)致了現(xiàn)有的協(xié)作路由算法很難在多跳無線網(wǎng)絡(luò)中得到良好性能[1].而多射頻多信道技術(shù)可以降低同信道干擾,將兩種技術(shù)相結(jié)合可以在充分利用協(xié)作通信分集增益的同時,降低無線傳輸?shù)耐诺栏蓴_,有效提升網(wǎng)絡(luò)整體吞吐量.

而對于多射頻無線mesh網(wǎng)絡(luò)中的協(xié)作路由,需要同時考慮協(xié)作路由的選擇和信道分配問題.現(xiàn)有的協(xié)作路由算法沒有考慮結(jié)點射頻和信道數(shù)量限制下的信道分配問題[2～5],無法充分利用多射頻多信道的優(yōu)勢,而已有的信道分配算法主要是針對直接傳輸網(wǎng)絡(luò)[6,7],沒有考慮協(xié)作傳輸?shù)奶匦?無法直接擴展到協(xié)作傳輸網(wǎng)絡(luò).因此,為了給業(yè)務(wù)流提供更優(yōu)質(zhì)的網(wǎng)絡(luò)服務(wù),本文結(jié)合多射頻多信道技術(shù)和協(xié)作通信技術(shù)來降低同信道干擾并獲得協(xié)作分集增益.針對協(xié)作通信多對一的傳輸特性,本文提出了一種基于協(xié)作通信模塊虛擬化的方法,在此基礎(chǔ)上將聯(lián)合協(xié)作路由和信道分配問題JCRCA(Joint Cooperative Routing and Channel Assignment)簡化為聯(lián)合直接路由和信道分配問題,同時將該問題建模成一個混合整數(shù)線性規(guī)劃問題,并證明該問題是一個NP-hard問題.為了解決該問題,本文進一步提出了一種寬松的聯(lián)合協(xié)作路由選擇和信道分配算法L-JCRCA(Loose Joint Cooperative Routing and Channel Assignment algorithm).實驗結(jié)果表明,L-JCRCA可以有效提升網(wǎng)絡(luò)總吞吐量.

2　聯(lián)合協(xié)作路由和信道分配問題

多射頻無線mesh網(wǎng)中聯(lián)合協(xié)作路由和信道分配問題是如何為每條業(yè)務(wù)流確定最優(yōu)的協(xié)作路由和信道分配策略.如圖1,帶箭頭的線段組成的路徑表示業(yè)務(wù)流使用的轉(zhuǎn)發(fā)路徑,線段上的數(shù)字表示為鏈路分配的正交信道.

然而,現(xiàn)有的協(xié)作路由沒有考慮多射頻無線mesh網(wǎng)中的信道分配問題,而已有的信道分配方法主要是針對直接傳輸網(wǎng)絡(luò),沒有考慮協(xié)作傳輸?shù)奶匦?無法直接擴展到協(xié)作傳輸網(wǎng)絡(luò).此外,在多射頻多信道網(wǎng)絡(luò)中,聯(lián)合直接路由和信道分配問題已是一個NP-hard問題,如果再將協(xié)作結(jié)點的分配加入進去,問題將變得更為復(fù)雜.

本節(jié)針對協(xié)作通信多對一的傳輸特性,提出了一種協(xié)作通信模塊虛擬化方法,通過為每個協(xié)作通信模塊加入相應(yīng)的虛擬結(jié)點和虛擬鏈路,構(gòu)建新的基于協(xié)作傳輸?shù)木W(wǎng)絡(luò)拓撲圖,并在此基礎(chǔ)上將聯(lián)合協(xié)作路由和信道分配問題簡化為聯(lián)合直接路由和信道分配問題.同時,在路由約束和信道資源約束的條件下,將該問題建模成一個混合整數(shù)線性規(guī)劃問題.

2.1協(xié)作通信模塊虛擬化

在協(xié)作路由中,每個通信模塊是由三個相互連通的結(jié)點組成,每條業(yè)務(wù)流會使用一個或多個協(xié)作通信模塊來傳輸數(shù)據(jù).一個協(xié)作通信模塊在路由過程中可能發(fā)生的協(xié)作傳輸最多有三種.如圖2(a),A,B,C三個結(jié)點可以組成一個協(xié)作通信模塊,可能發(fā)生的協(xié)作傳輸有(A,B)->C,(A,C)->B以及(B,C)->A,為了將這些協(xié)作傳輸鏈路清晰地表示出來,我們提出一種協(xié)作通信模塊虛擬化的方法來構(gòu)建新的基于協(xié)作傳輸?shù)木W(wǎng)絡(luò)拓撲圖.如圖2(b),為A,B,C組成協(xié)作通信模塊增加(A,B),(A,C),(B,C)三個虛擬結(jié)點,(A,B)->C,(A,C)->B,(B,C)->A三條協(xié)作鏈路,以及A->(A,B),B->(A,B),B->(B,C),C->(B,C),A->(A,C),C->(A,C)六條超級鏈路.之所以稱其它六條邊為超級鏈路,是因為在協(xié)作傳輸中,這些鏈路的發(fā)送端和接收端可以看作是在同一時刻收到信號,它們的MAC (Media Access Control)層傳輸速率趨向于無窮大.為網(wǎng)絡(luò)中的每個可能的協(xié)作通信模塊增加虛擬結(jié)點和虛擬鏈路后,就可以構(gòu)建新的基于協(xié)作傳輸?shù)木W(wǎng)絡(luò)拓撲圖.在此基礎(chǔ)上,我們就可以按照選擇直接路由的方式來尋找協(xié)作路由,從而將聯(lián)合協(xié)作路由和信道分配的問題簡化為聯(lián)合傳統(tǒng)路由和信道分配問題.

2.2問題形式化描述

我們用G(V,E)表示一個無線mesh網(wǎng)拓撲圖,V表示結(jié)點集合,E表示鏈路集合;用C表示正交信道集合;用F表示業(yè)務(wù)流集合;用H(u)表示結(jié)點u∈V配置的射頻數(shù)量.利用2.1提出的協(xié)作通信模塊虛擬化方法,將相應(yīng)的虛擬結(jié)點和虛擬鏈路加入到拓撲圖中后,構(gòu)建新的基于協(xié)作傳輸?shù)木W(wǎng)絡(luò)拓撲圖G(V′,E′),V′=V∪Vs,E′=E∪Es,其中,Vs表示虛擬結(jié)點集合,Es表示虛擬鏈路集合.

在對JCRCA問題建模時,必須滿足以下路由約束和信道資源約束條件.

(1)業(yè)務(wù)流必須遵守流守衡定律.

(1)

其中,a(u,v,k,c)表示鏈路(u,v)在信道c上傳輸流k的速率,s(k)表示業(yè)務(wù)流k的源結(jié)點,d(k)表示業(yè)務(wù)流k的目的結(jié)點,r(k)表示業(yè)務(wù)流最終的轉(zhuǎn)發(fā)速率.該式表示業(yè)務(wù)流的源結(jié)點只有出境流量,目的結(jié)點只有入境流量,而在其它中間結(jié)點,入境流量必須等于出境流量.

(2)鏈路傳輸速率必須滿足同信道干擾限制,即鏈路(u,v)和其干擾范圍內(nèi)鏈路的使用率之和不超過1.

?c∈C,?(u,v)∈E′

(2)

I(u,v)表示鏈路(u,v)干擾范圍內(nèi)的鏈路集合,b(u,v)表示鏈路的傳輸速率,可以根據(jù)文獻[8]提出的AF-Rake方法計算得到;p(u,v)表示鏈路的傳輸成功率,在本文中每條鏈路的傳遞成功率是恒定的.

(3)只有為鏈路(u,v)分配了信道c,(u,v)才能使用信道c傳輸數(shù)據(jù).

(3)

L(u,v,c)表示鏈路(u,v)是否分配了信道c,L(u,v,c)=1表示鏈路(u,v)可以使用信道c,否則L(u,v,c)=0.

(4)如果鏈路(u,v)分配了信道c,則u和v的射頻都需要分配信道c.

N(u,c)≥L(u,v,c),?u∈V′,?c∈C

(4)

N(v,c)≥L(u,v,c),?v∈V′,?c∈C

(5)

(6)

N(u,c)表示結(jié)點u∈V是否分配了信道c,如果結(jié)點u分配了信道c,N(u,c)=1,否則N(u,c)=0;

(5)當(dāng)虛擬結(jié)點us的射頻分配了信道c時,它的組成結(jié)點的射頻也必須分配信道c.

N(u,c)≥N(us,c),?u∈M(us),?c∈C

(7)

M(us)表示虛擬結(jié)點us的組成結(jié)點集合.

(6)u分配信道的數(shù)量要不大于u所配置的射頻數(shù)量.

(8)

(9)

在給出約束條件和目標(biāo)函數(shù)后,聯(lián)合協(xié)作路由和信道分配問題可以形式化表示如下:

(10)

s.t.式(1),(2),(3),(4),(5),(6),(7),(8)

定理1公式(10)所定義的聯(lián)合協(xié)作路由和信道分配問題是一個NP-hard問題.

證明我們通過將式(10)所定義的聯(lián)合協(xié)作路由和信道分配問題轉(zhuǎn)化聯(lián)合直接路由和信道分配問題來進行證明.

給定一個協(xié)作傳輸網(wǎng)絡(luò)圖G=(V,E),通過2.1提出的協(xié)作模塊虛擬化的方法,為網(wǎng)絡(luò)中的每個可能的協(xié)作通信模塊增加虛擬結(jié)點和虛擬鏈路,就可將協(xié)作傳輸網(wǎng)絡(luò)重構(gòu)成直接傳輸網(wǎng)絡(luò)G′=(V′,E′),聯(lián)合協(xié)作路由和信道分配問題就簡化成聯(lián)合直接路由和信道分配問題.而文獻[9]將聯(lián)合直接路由和信道問題轉(zhuǎn)換成一個精確覆蓋問題,并證明了其是一個NP-hard問題,因此,聯(lián)合協(xié)作路由和信道分配是一個NP-hard問題.

所以,聯(lián)合協(xié)作路由和信道分配問題JCRCA的計算復(fù)雜度是指數(shù)級.而為了在多項式時間內(nèi)確定合理的協(xié)作路由和信道分配策略,我們進一步提出了一種寬松的聯(lián)合協(xié)作路由和信道分配算法L-JCRCA.

3　寬松的聯(lián)合協(xié)作路由和信道分配算法

L-JCRCA的基本思想是首先將JCRCA的混合整數(shù)線性規(guī)劃寬松為普通線性規(guī)劃,然后對其最優(yōu)的信道分配策略進行局部調(diào)整,使得所有結(jié)點分配到的信道數(shù)量都滿足射頻數(shù)量的限制條件的同時最大化網(wǎng)絡(luò)吞吐量.

3.1寬松的聯(lián)合協(xié)作路由和信道分配策略

首先,將JCRCA寬松為普通線性規(guī)劃.為了公平分配網(wǎng)絡(luò)資源,目標(biāo)函數(shù)式(9)保持不變.此外,流守恒定律式(1)必須得到滿足,鏈路傳輸速率必須遵守同信道干擾限制式(2),發(fā)生的變化主要是對結(jié)點射頻數(shù)量限制條件進行了寬松.

將傳輸?shù)臅r間延長至T個時槽,可以得到

≤H(v),?v∈E′

(11)

如果業(yè)務(wù)流傳輸長期處于穩(wěn)定狀態(tài),式(11)可以轉(zhuǎn)化成:

(12)

寬松后的線性規(guī)劃問題為:

s.t.式 (1),(2),(12)

(13)

通過廣播的方式,每個結(jié)點可以獲取整個網(wǎng)路的拓撲狀態(tài)信息,并在此基礎(chǔ)上為業(yè)務(wù)流選擇協(xié)作傳輸路由和為鏈路分配信道.具體而言,如果a(u,v,k,c)>0,就代表鏈路(u,v)使用信道c為傳輸流k的數(shù)據(jù).因此,通過a(u,v,k,c)的解就可以得到每條業(yè)務(wù)流的傳輸鏈路以及使用的正交信道,從而確定業(yè)務(wù)流的協(xié)作路由和信道分配方案.

但射頻限制條件式(12)并不是嚴格約束,可能會導(dǎo)致有些鏈路被分配的信道數(shù)量超過其可使用的射頻數(shù)量.因此,需要對式(12)確定的信道分配方案進行局部調(diào)整,使得所有鏈路被分配的信道數(shù)量符合射頻數(shù)量的限制要求.

此外,由于沒有嚴格的射頻數(shù)量限制的約束條件,式(13)比JCRCA的約束更加寬松,其確定的協(xié)作路由和信道分配方案的網(wǎng)絡(luò)吞吐量可以看作是JCRCA的上界(UP-JCRCA).

3.2信道分配策略調(diào)整

信道分配策略的調(diào)整主要是對超過結(jié)點射頻數(shù)量的正交信道進行合并.如圖3(a),u總共分配了1,2,3三個信道,而只配置了兩個射頻.因此,需要對它們的信道進行調(diào)整,調(diào)整的結(jié)果必須保證每個結(jié)點發(fā)出鏈路使用信道的總數(shù)量不超過結(jié)點配置的射頻數(shù)量.

用U(u)表示從u發(fā)出的鏈路集合,假設(shè)我們選擇將U(u)中使用信道3的鏈路的信道變成2,鏈路(u,a)的的工作信道由1和3變?yōu)?和2,鏈路(u,d)的工作信道將由3變?yōu)?.這時,結(jié)點u所發(fā)出的鏈路已經(jīng)滿足射頻數(shù)量約束條件.同時,為了避免由此引起其它結(jié)點違反射頻數(shù)量約束條件,發(fā)生改變的鏈路的另一端結(jié)點所發(fā)出的鏈路也需要發(fā)生同樣的變化,例如,鏈路(a,v)的工作信道將變?yōu)?和2,鏈路(d,v)的工作信道會變?yōu)?和2,如圖3(b).最終所有的結(jié)點分配的信道數(shù)量都滿足了射頻數(shù)量的約束條件.當(dāng)網(wǎng)絡(luò)結(jié)點和信道數(shù)量較多時,可能需要通過多次這樣的調(diào)整才能完全滿足射頻數(shù)量的限制要求.為了保證虛擬結(jié)點和其組成的普通結(jié)點的信道分配保持同步,每當(dāng)虛擬結(jié)點的信道發(fā)生合并時,其組成的普通結(jié)點的信道也要相應(yīng)地進行類似的調(diào)整,反之亦然.

具體的調(diào)整過程如下:

步驟1選擇出境速率最大并且信道數(shù)量超過射頻數(shù)量的結(jié)點u.

步驟2從u的信道列表中,選擇兩個信道c1,c2進行合并.用?(u,c)表示Ec(u)中的鏈路在信道c上的使用率之和,即:

步驟3如果網(wǎng)絡(luò)中還有結(jié)點的信道數(shù)量超過射頻數(shù)量,重復(fù)步驟1、步驟2直至所有結(jié)點的信道數(shù)量符合限制要求.

最后,結(jié)合3.1和3.2描述的方法,我們確定最終的聯(lián)合協(xié)作路由和信道分配算法步驟如下:

步驟1根據(jù)網(wǎng)絡(luò)結(jié)點的廣播信息,獲取整個網(wǎng)絡(luò)的原始拓撲結(jié)構(gòu)和鏈路狀態(tài)信息.

步驟2根據(jù)2.1的方法構(gòu)建新的基于協(xié)作傳輸?shù)木W(wǎng)絡(luò)拓撲結(jié)構(gòu).

步驟3在新的網(wǎng)絡(luò)拓撲結(jié)構(gòu)基礎(chǔ)上,根據(jù)3.1的方法進行求解,初步確定業(yè)務(wù)流的協(xié)作傳輸路徑和傳輸路徑上鏈路的工作信道.

步驟4利用3.2的方法對步驟3的結(jié)果進行局部的信道調(diào)整,使得所有的結(jié)點分配到的信道數(shù)量都不超過其配置的射頻數(shù)量,并為業(yè)務(wù)流確定最終的協(xié)作路由和信道分配方案.

4　實驗

我們的實驗場景是在600m*600m的區(qū)域內(nèi)均勻地分布若干無線結(jié)點,每個結(jié)點的固定發(fā)送功率都設(shè)置為0.22W,每個信道的帶寬都為22MHZ,干擾距離和傳輸距離都為150m,路徑衰減指數(shù)為4,結(jié)點的噪音方差都為10-10W.

為了評估算法的性能,我們將從多個角度與以下三種算法得到的吞吐量進行對比:

(1)Uni-ETT:統(tǒng)一信道分配+最短期望傳輸時間路由;

(2)Ran-ETT:隨機信道分配+最短期望傳輸時間路由;

(3)Tra-ETT:傳統(tǒng)信道分配[10]+最短期望傳輸時間路由.此外,我們還將L-JCRCA與其上界UP-JCRCA進行對比.

4.1不同數(shù)量并發(fā)流下的吞吐量比較

在網(wǎng)絡(luò)中均勻分布25個結(jié)點,每個結(jié)點都配置了2個射頻,每個射頻可以工作3個正交信道上.圖4(a)顯示了在不同數(shù)量的并發(fā)流下,網(wǎng)絡(luò)吞吐量的變化情況.從圖中可以看出,在不同數(shù)量并發(fā)流下,L-JCRCA比Uni-ETT的吞吐量要提高55%到110%,比Ran-ETT的吞吐量要提高65%到120%,比Tra-ETT的吞吐量要提高135%到190%.提高的主要原因有兩個,一是L-JCRCA采用了協(xié)作通信技術(shù),可以有效提高單條鏈路的傳輸速率;二是L-JCRCA平衡了協(xié)作通信的分集增益和同信道干擾.圖4(b) 顯示了L-JCRCA與 UP-JCRCA的比較結(jié)果.從圖中可以看出,L-JCRCA獲得的網(wǎng)絡(luò)吞吐量略小于UP-JCRCA,這是因為當(dāng)射頻數(shù)量與信道數(shù)量非常接近時,JCRCA為結(jié)點分配的信道數(shù)量基本上不會超過射頻數(shù)量,需要進行信道調(diào)整的結(jié)點數(shù)量比較少,調(diào)整幅度也會比較小,所以,L-JCRCA獲得的吞吐量與沒有考慮射頻數(shù)量限制的UP-JCRCA差距較小.

4.2不同信道數(shù)量下的吞吐量比較

在網(wǎng)絡(luò)中均勻部署25個結(jié)點,每個結(jié)點配置2個射頻,隨機選擇5條業(yè)務(wù)流的源結(jié)點和目的結(jié)點.圖5(a)顯示了在不同數(shù)量的可用正交信道下,網(wǎng)絡(luò)吞吐量的變化情況.從圖中可以看出,L-JCRCA比Uni-ETT的吞吐量要提高25%到115%,比Ran-ETT的吞吐量要提高25%到180%,比Tra-ETT的吞吐量要提高75%到280%.圖5(b)顯示了隨著信道數(shù)量的增加,L-JCRCA與UP-JCRCA的差距越來越大,這是因為可用正交信道數(shù)量越多,UP-JCRCA分配給每個結(jié)點的信道數(shù)量也會隨之增加,L-JCRCA需要對結(jié)點信道進行調(diào)整幅度也就越大,最終導(dǎo)致兩者之間的吞吐量差距越來越大,但還是比其它三種的吞吐量要高.

4.3不同結(jié)點密度下的吞吐量比較

網(wǎng)絡(luò)中的每個結(jié)點配置了2個射頻,每個射頻可以工作在3個正交信道上,隨機選擇5條業(yè)務(wù)流的源結(jié)點和目的結(jié)點.從圖6(a)中可以看出,網(wǎng)絡(luò)吞吐量會隨著結(jié)點數(shù)量的增加而逐步增加,L-JCRCA比Uni-ETT的吞吐量要提高10%到75%,比Ran-ETT的吞吐量要提高30%到95%,比Tra-ETT的吞吐量要提高35%到210%.從圖6(b)可以看出,隨著結(jié)點數(shù)量的增加,L-JCRCA與UP-JCRCA差距有所增加,這是因為隨著結(jié)點數(shù)量的增加,會有更多的結(jié)點參與傳輸,造成違反射頻數(shù)量限制的結(jié)點數(shù)量有所增加,L-JCRCA進行信道調(diào)整幅度會隨之增大,所以差距會有所擴大.

5　結(jié)論

為了給多條業(yè)務(wù)流提供最優(yōu)的網(wǎng)絡(luò)性能,本文同時利用多射頻多信道和協(xié)作通信兩者的技術(shù)優(yōu)勢,提出來一種協(xié)作通信模塊虛擬化的方法,在此基礎(chǔ)上將聯(lián)合協(xié)作路由和信道分配問題建模為一個混合整數(shù)線性規(guī)劃問題,并證明該問題為一NP-hard問題.為了解決該問題,本文進一步提出了一種寬松的聯(lián)合協(xié)作路由和信道分配算法L-JCRCA.實驗結(jié)果表明,L-JCRCA算法可以有效提升網(wǎng)絡(luò)的總吞吐量.

[1]ZHANG J,ZHANG Q.Cooperative routing in multi-source multi-destination multi-Hop wireless networks [A].MERRILL D. INFOCOM 2008—The 27th Conference on Computer Communications[C].Phoenix,AZ:IEEE Press,2008.2369-2377.

[2]XU H L,HUANG L S,QIAO C M,et al.Bandwidth-power aware cooperative multipath routing for wireless multimedia sensor networks[J].IEEE Transactions on Wireless Communications,2012,11(4):1532-1543.

[3]ZHANG X Y,SHIN K.G.Cooperation without synchronization:practical cooperative relaying for wireless networks[J].IEEE Transactions on Mobile Computing,2014,14(5):937-950.

[4]XU Z C,LIANG W F.Collusion-resistant repeated double auctions for relay assignment in cooperative networks[J].IEEE Transactions on Wireless Communications,2014,13(3):1196-1207.

[5]YANG S S,SHENG Z G,MCCANN J A,et al.Distributed stochastic cross-layer optimization for multi-hop wireless networks with cooperative communications[J].IEEE Transactions on Mobile Computing,2013,13(10):2269-2282.

[6]杜振國,洪佩琳,周武旸，等.多射頻無線Mesh網(wǎng)中的接口分域信道分配[J].電子學(xué)報,2011,39(3):723-726.

DU Z G,HONG P L,Zhou W Y,et al.ICCA:Interface-clustered channel assignment in multi-radio wireless mesh network[J].Acta Electronica Sinica,2011,39(3):723-726.(in Chinese)

[7]DHANANJAY A,ZHANG H,LI J Y,et al.Practical,distributed channel assignment and routing in dual-radio mesh Networks[J].ACM SIGCOMM Computer Communication Review,2009,39(4):99-110.

[8]ZHU Y,ZHENG H T.Understanding the impact of interference on collaborative relays[J].IEEE Transactions on Mobile Computing,2008,7(6):724-736.

[9]MUMEY B,TANG J,JUDSON I R,et al.On routing and channel selection in cognitive radio mesh networks[J].IEEE Transactions on Vehicular Technology,2012,61(9):4118-4128.

[10]SUBRAMANIAN A P,GUPTA H,DAS S R,et al.Minimum interference channel assignment in multi-radio wireless mesh networks[J].IEEE Transactions on Mobile Computing,2008,7(12):1459-1473.

喬宏男，1984年生，湖南岳陽人.湖南大學(xué)博士生，主要研究方向為無線Mesh網(wǎng)、協(xié)作路由.

E-mail:hqiao@ hnu.edu.cn

張大方男，1959年生，上海人，湖南大學(xué)教授、博士生導(dǎo)師，主要研究方向為可信系統(tǒng)與網(wǎng)絡(luò)、軟件容錯.E-mail:dfzhang@ hnu.edu.cn

謝鯤女，1978年生，湖南黔陽人，湖南大學(xué)副教授，博士生導(dǎo)師，主要研究方向為分布式計算、協(xié)作路由.

E-mail: xiekun@ hnu.edu.cn

何施茗女，1986年生，湖南永州人，博士，長沙理工大學(xué)講師，主要研究方向為機會路由．

E-mail:heshiming-hsm@163.com

張繼男，1984年生，湖南長沙人，湖南大學(xué)博士生，主要研究方向為協(xié)作路由．

E-mail:tosky1984@163.com

Joint Cooperative Routing and Channel Assignment in Multi-radio Wireless Mesh Network

QIAO Hong1,ZHANG Da-fang1,XIE Kun1,HE Shi-ming2,ZHANG Ji1

(1.SchoolofInformationScienceandEngineering,HunanUniversity,Changsha,Hunan410082,China;2.SchoolofComputerandCommunicationEngineering,ChangshaUniversityofScienceandTechnology,Changsha,Hunan410004,China)

The existing cooperative routing algorithms ignored channel assignment issue in multi-radio wireless mess network.To provide high performance service for concurrent flows,this paper combined both multi-radio multi-channel technique and cooperative communication technique to reduce co-channel interference and obtain cooperative diversity gain.Based on virtualized representation method for the cooperative communication module,this paper simplified the problem of joint cooperative routing and channel assignment to the problem of joint direct routing and channel assignment,and modeled the problem as a mixed integer linear programming,and proved it NP hard.In order to solve the problem,this paper further proposed a loose joint cooperative routing and channel assignment algorithm (L-JCRCA).The simulation results show that L-JCRCA can promote network throughput effectively.

wireless mesh network;cooperative routing;channel assignment

2014-12-11;修回日期:2015-05-05;責(zé)任編輯：梅志強

國家973重點基礎(chǔ)發(fā)展計劃(No.2012CB315805);國家自然科學(xué)基金(No.61173167，No.61472130)

TP393

A

0372-2112 (2016)06-1400-06