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

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

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

?

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

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

(1.湖南大學(xué)信息科學(xué)與工程學(xué)院,湖南長(zhǎng)沙410082;2.長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信學(xué)院,湖南長(zhǎng)沙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é)作路由和信道分配問題簡(jiǎn)化為聯(lián)合直接路由和信道分配問題,將其建模為一個(gè)混合整數(shù)線性規(guī)劃問題,并證明該問題為NP-hard問題.為了解決該問題,提出了一種寬松的聯(lián)合協(xié)作路由選擇和信道分配算法(Loose Joint Cooperative Routing and Channel Assignment algorithm,L-JCRCA).仿真實(shí)驗(yàn)結(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é)點(diǎn)參與路由中的某一跳或某幾跳傳輸,提高無線傳輸?shù)娜萘炕蚪档蛡鬏數(shù)哪芎?為無線用戶提供更好的網(wǎng)絡(luò)服務(wù).

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

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

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

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

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

2.2問題形式化描述

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

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

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

(1)

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

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

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

(2)

I(u,v)表示鏈路(u,v)干擾范圍內(nèi)的鏈路集合,b(u,v)表示鏈路的傳輸速率,可以根據(jù)文獻(xiàn)[8]提出的AF-Rake方法計(jì)算得到;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é)點(diǎn)u∈V是否分配了信道c,如果結(jié)點(diǎn)u分配了信道c,N(u,c)=1,否則N(u,c)=0;

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

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

(7)

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

(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é)作路由和信道分配問題是一個(gè)NP-hard問題.

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

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

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

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

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

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

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

將傳輸?shù)臅r(shí)間延長(zhǎng)至T個(gè)時(shí)槽,可以得到

≤H(v),?v∈E′

(11)

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

(12)

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

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

(13)

通過廣播的方式,每個(gè)結(jié)點(diǎn)可以獲取整個(gè)網(wǎng)路的拓?fù)錉顟B(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)并不是嚴(yán)格約束,可能會(huì)導(dǎo)致有些鏈路被分配的信道數(shù)量超過其可使用的射頻數(shù)量.因此,需要對(duì)式(12)確定的信道分配方案進(jìn)行局部調(diào)整,使得所有鏈路被分配的信道數(shù)量符合射頻數(shù)量的限制要求.

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

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

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

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

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

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

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

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

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

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

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

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

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

4　實(shí)驗(yàn)

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

為了評(píng)估算法的性能,我們將從多個(gè)角度與以下三種算法得到的吞吐量進(jìn)行對(duì)比:

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

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

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

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

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

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

在網(wǎng)絡(luò)中均勻部署25個(gè)結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)配置2個(gè)射頻,隨機(jī)選擇5條業(yè)務(wù)流的源結(jié)點(diǎn)和目的結(jié)點(diǎn).圖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的差距越來越大,這是因?yàn)榭捎谜恍诺罃?shù)量越多,UP-JCRCA分配給每個(gè)結(jié)點(diǎn)的信道數(shù)量也會(huì)隨之增加,L-JCRCA需要對(duì)結(jié)點(diǎn)信道進(jìn)行調(diào)整幅度也就越大,最終導(dǎo)致兩者之間的吞吐量差距越來越大,但還是比其它三種的吞吐量要高.

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

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

5　結(jié)論

為了給多條業(yè)務(wù)流提供最優(yōu)的網(wǎng)絡(luò)性能,本文同時(shí)利用多射頻多信道和協(xié)作通信兩者的技術(shù)優(yōu)勢(shì),提出來一種協(xié)作通信模塊虛擬化的方法,在此基礎(chǔ)上將聯(lián)合協(xié)作路由和信道分配問題建模為一個(gè)混合整數(shù)線性規(guī)劃問題,并證明該問題為一NP-hard問題.為了解決該問題,本文進(jìn)一步提出了一種寬松的聯(lián)合協(xié)作路由和信道分配算法L-JCRCA.實(shí)驗(yàn)結(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é)報(bào),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é)博士生，主要研究方向?yàn)闊o線Mesh網(wǎng)、協(xié)作路由.

E-mail:hqiao@ hnu.edu.cn

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

謝鯤女，1978年生，湖南黔陽人，湖南大學(xué)副教授，博士生導(dǎo)師，主要研究方向?yàn)榉植际接?jì)算、協(xié)作路由.

E-mail: xiekun@ hnu.edu.cn

何施茗女，1986年生，湖南永州人，博士，長(zhǎng)沙理工大學(xué)講師，主要研究方向?yàn)闄C(jī)會(huì)路由．

E-mail:heshiming-hsm@163.com

張繼男，1984年生，湖南長(zhǎng)沙人，湖南大學(xué)博士生，主要研究方向?yàn)閰f(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é)任編輯：梅志強(qiáng)

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

TP393

A

0372-2112 (2016)06-1400-06