尹鳳杰,彭永倩
(遼寧大學(xué) 信息學(xué)院,遼寧 沈陽 110036)
無線Mesh網(wǎng)絡(luò)是一種新型的多跳無線網(wǎng)絡(luò),具有組網(wǎng)靈活、網(wǎng)絡(luò)覆蓋率高等優(yōu)點(diǎn).為充分利用正交信道,提高網(wǎng)絡(luò)吞吐量和帶寬利用率,信道分配已成為無線Mesh網(wǎng)絡(luò)中的研究熱點(diǎn).根據(jù)802.11a和b/g的標(biāo)準(zhǔn),分別有12個(gè)和3個(gè)不重疊的正交信道可供使用[1],因此,對(duì)于一個(gè)接口來說,可以同時(shí)使用多個(gè)不重疊的信道.除此之外,還可讓一個(gè)節(jié)點(diǎn)配備多個(gè)接口,這就使得每個(gè)節(jié)點(diǎn)可同時(shí)使用多個(gè)互不重疊的正交信道,但節(jié)點(diǎn)間傳輸隊(duì)列過多,將存在信道間相互干擾與負(fù)載均衡問題.
在多接口多信道無線Mesh網(wǎng)絡(luò)中,信道數(shù)量可能多于節(jié)點(diǎn)接口數(shù)量.為了使網(wǎng)絡(luò)吞吐量達(dá)到最大,最佳的信道分配方式應(yīng)該是在干擾可控范圍內(nèi)允許有最大數(shù)量的并發(fā)傳輸存在,然而,這已經(jīng)被證明是一個(gè)NP(Non-deterministic Polynomial)問題[2].同時(shí),信道分配還可能會(huì)影響網(wǎng)絡(luò)的連通性[3],目前主要是通過使用專用信道和同步信道的分配方式來解決這個(gè)問題.但是,同步信道分配需要保持時(shí)間同步,當(dāng)傳錯(cuò)率較高且重傳機(jī)會(huì)有限時(shí),將會(huì)導(dǎo)致整體性能降低[4].
文獻(xiàn)[5]提出的BCMN/A協(xié)議用于簇內(nèi)廣播,并且對(duì)來自簇的每個(gè)數(shù)據(jù)返回ACK(Acknowledge Characte)確認(rèn),以便共同優(yōu)化生存時(shí)間和傳輸延遲,實(shí)驗(yàn)結(jié)果表明,該協(xié)議可以將網(wǎng)絡(luò)的生存時(shí)間提高8%以上,并且將網(wǎng)絡(luò)延遲降低25%以上.文獻(xiàn)[6]根據(jù)無線Mesh網(wǎng)絡(luò)特點(diǎn),提出一種基于AODV-MR的AODV-MRCR協(xié)議.該協(xié)議專門為網(wǎng)關(guān)流量保留一個(gè)信道列表,將網(wǎng)關(guān)流量和本地流量分開處理,因?yàn)榫W(wǎng)關(guān)流量具有較高的優(yōu)先級(jí),所以為它準(zhǔn)備較多信道.然而對(duì)于本地流量,只保留一個(gè)固定信道,當(dāng)本地流量較高時(shí),這種方法效果并不理想.為了進(jìn)一步提高效率,急需一種能夠均衡網(wǎng)關(guān)流量和本地流量的解決方案,因此,本文提出一種基于負(fù)載均衡的多接口多信道分配算法DACA-LB,該算法通過選擇干擾最小信道,動(dòng)態(tài)接口調(diào)整來平衡負(fù)載,有效降低了平均排隊(duì)延遲,實(shí)現(xiàn)負(fù)載均衡和網(wǎng)絡(luò)吞吐量最大化.
在無線Mesh網(wǎng)絡(luò)中影響多接口利用率的一個(gè)重要因素是切換問題[7],頻繁切換會(huì)導(dǎo)致信道利用率降低,而靜態(tài)配置會(huì)因流量動(dòng)態(tài)變化導(dǎo)致性能欠佳[8],本文綜合考慮二者的平衡問題,采用動(dòng)靜結(jié)合的方式設(shè)計(jì)DACA-LB框架結(jié)構(gòu),如圖1所示,該結(jié)構(gòu)主要由信道分配、靜態(tài)接口設(shè)置以及動(dòng)態(tài)自適應(yīng)接口調(diào)整3部分組成,其中每個(gè)接口都可以在接收模式與發(fā)送模式之間轉(zhuǎn)換.
圖1 DACA-LB算法框架圖
為確保網(wǎng)絡(luò)連通性[9],設(shè)置2個(gè)不同的接口總是分別處在接收模式和發(fā)送模式,本文統(tǒng)稱為靜態(tài)接口,它們將使用專用信道進(jìn)行傳輸,若傳輸隊(duì)列變化大于專用信道所能承受的范圍,則需要從預(yù)留出來的自適應(yīng)信道中選擇一條受干擾最小的信道進(jìn)行傳輸.在選擇工作信道之后,信道信息將廣播給所有鄰居節(jié)點(diǎn)[10].鄰居節(jié)點(diǎn)保存該信息記錄,并根據(jù)該條信息向鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)包.其中,專用信道是不會(huì)改變的,以確保鄰居節(jié)點(diǎn)之間的連通性.對(duì)于信道分配,須遵循2個(gè)原則:1)同一節(jié)點(diǎn)的接口應(yīng)盡量選擇不同信道,以避免互相干擾;2)在理想情況下,優(yōu)先選擇一個(gè)受干擾最小的信道[11].
除靜態(tài)接口外的其他接口,本文統(tǒng)稱為動(dòng)態(tài)自適應(yīng)接口,其在默認(rèn)狀態(tài)下將全部處于發(fā)送模式.隨著時(shí)間的變化,當(dāng)靜態(tài)接口負(fù)載達(dá)到一定閾值后,動(dòng)態(tài)自適應(yīng)接口將調(diào)整為接收模式或繼續(xù)保持發(fā)送模式,從而可以均衡接口之間的負(fù)載.
本文采用的干擾模型如圖2所示,其中Rd、Rtx、Rcsin分別表示發(fā)射機(jī)和接收機(jī)之間的距離、傳輸范圍以及干擾范圍,一般情況下干擾范圍比傳輸范圍大,本文假設(shè)干擾范圍以外的并發(fā)傳輸對(duì)目標(biāo)傳輸?shù)挠绊懯呛雎圆挥?jì)的.
圖2 干擾模型
圖2所示為節(jié)點(diǎn)A向節(jié)點(diǎn)B發(fā)送數(shù)據(jù)包時(shí),節(jié)點(diǎn)C會(huì)受到來自節(jié)點(diǎn)A的干擾,由于節(jié)點(diǎn)D處于節(jié)點(diǎn)B的干擾范圍內(nèi),因此,節(jié)點(diǎn)C和節(jié)點(diǎn)D應(yīng)該避免和節(jié)點(diǎn)A同時(shí)發(fā)送,這樣就可以消除隱藏終端問題.節(jié)點(diǎn)E在節(jié)點(diǎn)A和節(jié)點(diǎn)B的干擾范圍之外,所以節(jié)點(diǎn)E和節(jié)點(diǎn)A可以同時(shí)傳輸,避免暴露終端的問題.通常,干擾范圍內(nèi)的節(jié)點(diǎn)數(shù)量大于正交信道的數(shù)量,因此,在其干擾范圍內(nèi),可能找不到空閑信道.
默認(rèn)情況下,為靜態(tài)發(fā)送/接收接口設(shè)置專用傳輸信道,并為專用傳輸信道設(shè)置一個(gè)能夠承受的隊(duì)列數(shù)量動(dòng)態(tài)變化范圍R∈[2r-1,2r+1](r為常數(shù)且r≥1),當(dāng)隊(duì)列的數(shù)量變化超出范圍R,則隊(duì)列將切換信道.本文用Numq來表示當(dāng)前信道中的隊(duì)列數(shù)量,Numq越大,信道越繁忙,干擾可能就越多.當(dāng)隊(duì)列離開信道時(shí),信道負(fù)載變輕,Numq減1;當(dāng)有隊(duì)列加入當(dāng)前信道,則Numq加1.可以看出信道能夠承受的隊(duì)列數(shù)量動(dòng)態(tài)變化范圍R的中值為2r,若Numq變化大于2r,則節(jié)點(diǎn)切換信道.因此,應(yīng)根據(jù)動(dòng)態(tài)需求,將r設(shè)置為一個(gè)合適的值來控制信道的切換頻率,用于避免隊(duì)列調(diào)整過于頻繁.
當(dāng)一個(gè)節(jié)點(diǎn)需要切換到與其鄰居節(jié)點(diǎn)相同的信道時(shí),應(yīng)優(yōu)先選擇使用次數(shù)最少的信道.本節(jié)在監(jiān)聽各個(gè)接口無線網(wǎng)絡(luò)活動(dòng)的基礎(chǔ)上計(jì)算信道的狀態(tài),并通過公式(1)對(duì)信道的繁忙時(shí)間比P(ch)進(jìn)行計(jì)算[12].
(1)
其中,tactive表示在時(shí)間T內(nèi)信道ch的活動(dòng)時(shí)間.
(2)
假設(shè)2個(gè)接口之間有n條傳輸信道,給各信道編號(hào)為chj(j=1,2,…,n),且時(shí)間T內(nèi)各個(gè)信道的活動(dòng)時(shí)間用tactive(chj)表示,P(chj)則表示信道chj的繁忙時(shí)間比.N(chj)表示所有通過信道chj發(fā)送數(shù)據(jù)包的接口結(jié)合,且該集合內(nèi)的所有接口都處于干擾源的干擾范圍內(nèi).結(jié)合圖2所示,假設(shè)節(jié)點(diǎn)B、C的某個(gè)接口均通過信道ch發(fā)送數(shù)據(jù)包,且2個(gè)節(jié)點(diǎn)均處在節(jié)點(diǎn)A的干擾范圍內(nèi),所以有N(ch)={B、C}.圖3給出了信道分配的完整過程,每個(gè)接口選擇干擾最小的信道chmin傳輸數(shù)據(jù)包.
圖3 信道分配流程圖
對(duì)于靜態(tài)接口,本文采用專用信道來降低發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的協(xié)調(diào)復(fù)雜性,在確保網(wǎng)絡(luò)連通性的同時(shí)降低信道間的切換開銷.根據(jù)DACA-LB算法的框架結(jié)構(gòu),靜態(tài)接口應(yīng)根據(jù)從鄰居節(jié)點(diǎn)得到的發(fā)送(或接收)接口信息來使用信道,在此過程中,確認(rèn)發(fā)送/接收接口尤為關(guān)鍵,若默認(rèn)的發(fā)送/接收接口處理的數(shù)據(jù)包多于其他接口,不僅導(dǎo)致其他接口的利用率降低,而且吞吐量也會(huì)隨著沖突率的上升而下降.
節(jié)點(diǎn)可以通過交換接口信息,向它們的鄰居節(jié)點(diǎn)發(fā)送其選擇的信道列表[15],鄰居節(jié)點(diǎn)信息交換過程如圖4所示.通過與直接相連的鄰居節(jié)點(diǎn)交換接口信息,節(jié)點(diǎn)A首先收集單跳鄰居節(jié)點(diǎn)B至E的接口配置信息,節(jié)點(diǎn)B至E也會(huì)將收到的來自節(jié)點(diǎn)A的接口信息并轉(zhuǎn)發(fā)給其各自鄰居節(jié)點(diǎn),使得節(jié)點(diǎn)A在獲得其兩跳鄰居節(jié)點(diǎn)F至I接口信息的同時(shí),還可獲得三跳鄰居節(jié)點(diǎn)G至M接口信息,以此類推,獲得更多節(jié)點(diǎn)信息.
圖4 鄰居交換信息過程
動(dòng)態(tài)自適應(yīng)接口,可用作發(fā)送或接收接口,以平衡所有接口間的負(fù)載.如果源節(jié)點(diǎn)存在大量隊(duì)列等待發(fā)送,則需要更多的自適應(yīng)接口調(diào)整為發(fā)送接口,節(jié)點(diǎn)收集和聚合信息則需要更多的接收接口.本文通過監(jiān)聽無線網(wǎng)絡(luò)的活動(dòng)狀態(tài),周期性地從各個(gè)節(jié)點(diǎn)中收集CPU利用率、內(nèi)存利用率以及網(wǎng)絡(luò)利用率,并根據(jù)這些參數(shù)計(jì)算出接口的動(dòng)態(tài)閾值,依據(jù)閾值的大小均衡接口負(fù)載.本文定義使用接口i傳輸數(shù)據(jù)時(shí)的最大負(fù)載為Loadmax,接口i在為隊(duì)列q服務(wù)時(shí)的平均負(fù)載值可用公式(3)求得.
(3)
其中,Dataq表示接口要傳輸?shù)臄?shù)據(jù)大小,ts、tr分別表示數(shù)據(jù)發(fā)送時(shí)刻和接收時(shí)刻.
根據(jù)節(jié)點(diǎn)收集到的信息可得到接口i使用信道ch傳輸數(shù)據(jù)時(shí)能夠承擔(dān)的最大負(fù)載利用率MaxU,可用公式(4)求得.
MaxU=Max(Cq,Mq,Nq)
(4)
其中,Cq、Mq、Nq分別表示CPU利用率、內(nèi)存利用率和網(wǎng)絡(luò)利用率,規(guī)定三者取值為0~1之間.
由公式(3)和公式(4)可得接口i在為隊(duì)列q服務(wù)時(shí)能夠提供的最大負(fù)載Loadmax(i,q),可通過公式(5)計(jì)算.
(5)
假設(shè)最多只能有n個(gè)隊(duì)列同時(shí)在接口i上工作,則可以通過公式(6)估計(jì)接口i傳輸數(shù)據(jù)包時(shí)的最大負(fù)載Loadmax.
(6)
同時(shí)假設(shè)接口i中正在運(yùn)行的隊(duì)列有qk,qk+1,…,qn,根據(jù)公式(5)和公式(6)可以計(jì)算出下一時(shí)間段接口能夠承受的負(fù)載增量ΔLoad,其公式如下(7)所示.
(7)
根據(jù)公式(7)可以得出隊(duì)列qk+1的最大負(fù)載不能超過ΔLoad,則可以把ΔLoad看作一個(gè)閾值,如果Loadav(i,qn+1)>ΔLoad,就需要把一個(gè)動(dòng)態(tài)的接口調(diào)整為接收模式或繼續(xù)保持發(fā)送模式,借此來緩解當(dāng)前接口的流量負(fù)載,否則繼續(xù)使用當(dāng)前接口.
DACA-LB算法的總體實(shí)現(xiàn)流程如圖5所示,若節(jié)點(diǎn)A向節(jié)點(diǎn)B發(fā)送數(shù)據(jù),節(jié)點(diǎn)A中某一隊(duì)列進(jìn)入默認(rèn)發(fā)送接口后,將判斷隊(duì)列負(fù)載是否超過接口的閾值,若超過則任意選擇一個(gè)動(dòng)態(tài)自適應(yīng)接口傳輸此隊(duì)列(若為接收過程,則需要將接口調(diào)整為接收模式);若沒有超過閾值,則繼續(xù)使用當(dāng)前默認(rèn)發(fā)送接口.其次,根據(jù)2.2節(jié)中提到的方法判斷當(dāng)前隊(duì)列是否需要切換信道,若需切換,則選擇受干擾最小的信道;若無需切換,則保持當(dāng)前信道即可,并根據(jù)最后的接收節(jié)點(diǎn)情況選擇適合的接口,完成傳輸任務(wù).
圖5 DACA-LB協(xié)議整體流程圖
本文通過在Linux環(huán)境下使用NS2-35評(píng)估所提DACA-LB算法的整體性能,在此次仿真實(shí)驗(yàn)中除了增加MAC狀態(tài)統(tǒng)計(jì)模塊外,無需做其他修改,且當(dāng)接口在進(jìn)行信道切換時(shí),該接口不能發(fā)送或接收任何數(shù)據(jù)包.IEEE802.11a標(biāo)準(zhǔn)規(guī)定了12個(gè)可使用的不重疊信道,且在理論上它們之間不存在干擾,然而,由于技術(shù)的限制,在相鄰不重疊信道上工作的接口也可能相互干擾[16],因此本文將正交信道的數(shù)量設(shè)置為5到12.隨著仿真時(shí)間的增加,節(jié)點(diǎn)間的負(fù)載也在不斷增加,導(dǎo)致信道分配狀態(tài)不穩(wěn)定,為了更好地觀察各種算法的性能比較,將仿真時(shí)間設(shè)置為400 s.本實(shí)驗(yàn)中接口數(shù)設(shè)置為2~5之間,小于可用的正交信道數(shù)目,其中,所有接口的傳輸距離為250 m,載波監(jiān)聽范圍為500 m,其他仿真參數(shù)設(shè)置如表1所示.
表1 仿真參數(shù)設(shè)置
本文結(jié)合AODV路由協(xié)議從信道數(shù)量和接口數(shù)量方面對(duì)DACA-LB網(wǎng)絡(luò)吞吐量性能產(chǎn)生的影響進(jìn)行實(shí)驗(yàn)分析,并與現(xiàn)有協(xié)議進(jìn)行對(duì)比.分析圖6的實(shí)驗(yàn)結(jié)果可知,在接口數(shù)量不變的情況下,信道數(shù)量越多,其吞吐量增加越明顯,但其增長速度逐漸放緩,原因是鏈路層協(xié)議可以很好地利用信道資源,但是由于接口數(shù)量的限制,導(dǎo)致可使用的信道數(shù)量有限,所以增長速度變得緩慢.除此之外,信道數(shù)量增多將會(huì)產(chǎn)生更多的信道切換,從而導(dǎo)致更高的網(wǎng)絡(luò)開銷.對(duì)于接口數(shù)量而言,當(dāng)信道數(shù)量不變,隨著接口數(shù)量的增加,其吞吐量越高.由此可見,增加接口和信道數(shù)量均可提高網(wǎng)絡(luò)吞吐量.但是,若信道數(shù)量足夠多,卻沒有與之相匹配的接口數(shù)量,則不能提高吞吐量,反之亦然.
圖6 具有不同信道數(shù)和接口數(shù)的吞吐量變化
本文通過將DACA-LB算法與不同路由協(xié)議相結(jié)合,對(duì)其性能進(jìn)行評(píng)估,分別是:a)DACA-LB+AODV[17];b)DACA-LB+WCETT[18];c)AODV-MR,1種結(jié)合鏈路和路由協(xié)議的跨層解決方案.本次模擬實(shí)驗(yàn)設(shè)置在1 000×1 000 m2的區(qū)域中隨機(jī)分布100個(gè)節(jié)點(diǎn),所有節(jié)點(diǎn)均配備4個(gè)接口,且12個(gè)正交信道全部可用.
在所有節(jié)點(diǎn)中統(tǒng)一選擇源/目的對(duì),并將目的對(duì)的數(shù)量設(shè)置為50~500,以顯示不同流量負(fù)載下的性能.分析圖7的實(shí)驗(yàn)結(jié)果可知,DACA-LB+AODV與DACA-LB+WCETT的性能表現(xiàn)十分接近,AODV-MR性能表現(xiàn)最差.這是因?yàn)锳ODV-MR算法只是進(jìn)行簡單的信道分配,沒有考慮負(fù)載平衡問題,所以其性能較差.其次,可知DACA-LB+WECTT組合的吞吐量并沒有明顯高于DACA-LB+AODV組合的吞吐量,這是因?yàn)樵赪CETT路由協(xié)議中并沒有考慮信道分布和信道切換的開銷,除此之外,隨著網(wǎng)絡(luò)負(fù)載增加到一定數(shù)值,大多數(shù)信道和接口已經(jīng)被利用,二者的吞吐量趨于一致.
圖7 不同隨機(jī)源/目的對(duì)情況下的吞吐量變化
任意選擇網(wǎng)絡(luò)中5個(gè)節(jié)點(diǎn),將其設(shè)置為具有比其他節(jié)點(diǎn)較高流量負(fù)載的網(wǎng)關(guān),網(wǎng)絡(luò)中的其他節(jié)點(diǎn)將隨機(jī)選擇附近的網(wǎng)關(guān)接入互聯(lián)網(wǎng),圖8為3種算法隨著并發(fā)流數(shù)目的增加,網(wǎng)絡(luò)吞吐量變化的趨勢(shì)圖.分析可知,3種算法的吞吐量變化趨勢(shì)與圖7結(jié)果相似.由此得出結(jié)論,場(chǎng)景DACA-LB+AODV和DACA-LB+WCETT的性能相近,并且二者性能均優(yōu)于AODV-MR.當(dāng)并發(fā)流數(shù)量較少時(shí),三者性能相似,隨著流量的增加,DACA-LB 的負(fù)載均衡可以大幅度地提高整體性能.圖7與圖8的2種仿真實(shí)驗(yàn)結(jié)果表明,本文所提DACA-LB算法能夠動(dòng)態(tài)平衡流量負(fù)載,獲得較高的吞吐量,且能與現(xiàn)有的路由協(xié)議實(shí)現(xiàn)較好地結(jié)合.
圖8 5個(gè)網(wǎng)關(guān)情況下的吞吐量變化
除此之外,本文還通過網(wǎng)絡(luò)吞吐量和平均丟包率2種性能指標(biāo),將DACA-LB算法與ELIA和LBIA-OCA信道分配算法進(jìn)行對(duì)比分析[19],以驗(yàn)證所提算法的有效性.ELIA和LBIA-OCA算法均是通過選擇受干擾最小的信道進(jìn)行傳輸,同時(shí)考慮節(jié)點(diǎn)接口間的負(fù)載均衡,但執(zhí)行方式與本文所提算法不同.在此次對(duì)比實(shí)驗(yàn)中,將并發(fā)流數(shù)目范圍設(shè)置為4~22,報(bào)文發(fā)送速率為200 Kbps.隨著流量的增加,網(wǎng)絡(luò)吞吐量的變化如圖9所示.
圖9 不同信道分配算法下的吞吐量變化
分析圖9的實(shí)驗(yàn)結(jié)果可知,性能排序?yàn)椋篋ACA-LB最優(yōu),ELIA次之,LBIA-OCA最差.在3種算法中,網(wǎng)絡(luò)吞吐量隨著流量的增加幾乎呈線性上升趨勢(shì),但上升速度逐漸變緩,其中,DACA-LB和ELIA的性能均明顯優(yōu)于LBIA-OCA算法.當(dāng)網(wǎng)絡(luò)負(fù)載較輕,3種算法產(chǎn)生的網(wǎng)絡(luò)吞吐量幾乎相同,但在LBIA-OCA算法中,隨著流量的增加,為相鄰隊(duì)列分配相同信道的可能性隨之增加,進(jìn)而數(shù)據(jù)包在傳輸之前必須在緩沖隊(duì)列中等待較長時(shí)間,且可能發(fā)生更多回收,這就導(dǎo)致較差的網(wǎng)絡(luò)性能.由于DACA-LB算法考慮了節(jié)點(diǎn)接口間的負(fù)載均衡,使得網(wǎng)絡(luò)并沒有隨著負(fù)載的增加陷入瓶頸,而是繼續(xù)保持上升趨勢(shì).
分析圖9和圖10的實(shí)驗(yàn)結(jié)果可知,3種算法的平均丟包率與網(wǎng)絡(luò)吞吐量是成反比的,即丟包越多,網(wǎng)絡(luò)吞吐量越低.同時(shí),隨著并發(fā)流的增加,DACA-LB算法的丟包率明顯低于其他2種算法,表現(xiàn)出更佳的性能,這主要得益于DACA-LB算法充分利用信道和接口資源,降低了丟包率.
圖10 不同信道分配算法下的平均丟包率變化
本文提出一種基于負(fù)載均衡的多接口多信道分配算法DACA-LB,該算法通過平衡負(fù)載來使網(wǎng)絡(luò)吞吐量最大化,從而提高整體性能.通過動(dòng)態(tài)自適應(yīng)的接口分配方式,在保證用戶需求的基礎(chǔ)上,提高接口利用率,有效減少請(qǐng)求響應(yīng)時(shí)間;該算法部署在所有節(jié)點(diǎn)上,以分布式方式控制數(shù)據(jù)傳輸,且上行鏈路與下行鏈路數(shù)據(jù)均由高負(fù)載水平匯聚節(jié)點(diǎn)的無線接口來接收和發(fā)送.仿真結(jié)果表明,DACA-LB算法能夠在保證平均丟包率較小的情況下實(shí)現(xiàn)較大的吞吐量,提高網(wǎng)絡(luò)性能.但該算法目前只能在接口間平衡接收和發(fā)送流量的負(fù)載,如何平衡節(jié)點(diǎn)間的流量負(fù)載將作為下一步研究重點(diǎn).