無線網(wǎng)狀網(wǎng)中多并發(fā)流路由結(jié)合調(diào)度的組合方案

黃啟嵩, 曹霑懋, 單志龍

(華南師范大學(xué)計(jì)算機(jī)學(xué)院， 廣州 510631)

無線網(wǎng)狀網(wǎng)(Wireless Mesh Networks,WMNs) 作為無線寬帶服務(wù)的技術(shù)，旨在提供無處不在的信息服務(wù)[1]. 由于移動(dòng)終端爆發(fā)式增長，多用戶同時(shí)發(fā)出傳輸請(qǐng)求是常態(tài)[2]. 如何有效利用資源以減少干擾成為提高系統(tǒng)傳輸性能的關(guān)鍵問題. 多并發(fā)流的問題是由多對(duì)傳輸請(qǐng)求這個(gè)共有現(xiàn)象抽象出的多路不同的源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)對(duì)之間的數(shù)據(jù)流并發(fā)的問題,要解決此問題，需為每路數(shù)據(jù)流分配鏈路以傳輸數(shù)據(jù). 若多路數(shù)據(jù)流之間的路徑?jīng)]有合理地協(xié)調(diào)調(diào)度，數(shù)據(jù)流所選取的路徑將可能交錯(cuò)在一起，產(chǎn)生節(jié)點(diǎn)負(fù)載不均衡現(xiàn)象[3]，從而導(dǎo)致請(qǐng)求的傳輸任務(wù)不能及時(shí)完成,以至于影響網(wǎng)絡(luò)性能，且造成無線網(wǎng)絡(luò)資源的浪費(fèi).

多并發(fā)流的問題，單獨(dú)考慮路由、信道分配或調(diào)度都被證明是NP-Complete的[4]. 對(duì)此問題，學(xué)者們從不同角度提出解決方案. 如：提出一種分布式聯(lián)合候選節(jié)點(diǎn)選擇和速率分配的多流機(jī)會(huì)路由算法，通過速率分配確定并發(fā)流下機(jī)會(huì)路由的候選節(jié)點(diǎn)[5]；提出一種寬松的聯(lián)合協(xié)作路由選擇和信道分配算法，解決多數(shù)據(jù)流下協(xié)作路由和信道分配[6]；提出一種分布式算法用以最小化信道的最大擁塞，解決了基于MIMO的多并發(fā)流的路由問題[7]；提出一種干擾感知的路由度量，該路由度量考慮了流內(nèi)和流間干擾以及鏈路速率，在多并發(fā)流的網(wǎng)絡(luò)下盡可能地選擇能夠并發(fā)且互不干擾的路徑[8]；進(jìn)一步提出了一種基于博弈論的干擾感知信道分配算法，公平地將網(wǎng)絡(luò)非重疊信道分配給接口，有利于增加多并發(fā)流條件下并發(fā)傳輸?shù)倪B接數(shù)量[9]；通過廣義Benders分解方法解決聯(lián)合信道分配、鏈路調(diào)度、路由和速率控制的問題，從而獲得多數(shù)據(jù)流下信道分配的最優(yōu)方案[4]；提出一種負(fù)載均衡鏈路層協(xié)議，該協(xié)議按干擾的大小進(jìn)行信道分配并基于霍夫曼樹按鏈路的負(fù)載進(jìn)行調(diào)度，實(shí)現(xiàn)了多數(shù)據(jù)流下節(jié)點(diǎn)接口間的負(fù)載平衡，但未能實(shí)現(xiàn)多數(shù)據(jù)流下節(jié)點(diǎn)間的負(fù)載平衡[10]；提出一種跨層聯(lián)合信道分配和路由算法，該算法在信道分配階段貪婪地選擇干擾最小的信道，并在路由階段提出一種結(jié)合了路徑剩余容量和預(yù)期傳輸時(shí)間的新路由參數(shù)[11]. 從資源利用角度，同時(shí)考慮多并發(fā)流的路由、信道分配和調(diào)度問題是一種有益的探索[12]. 然而，現(xiàn)有的解決方案大多針對(duì)多路數(shù)據(jù)流并發(fā)問題在路由、信道分配和調(diào)度等方面中的1個(gè)或者2個(gè)方面，并未能將這幾個(gè)方面有效結(jié)合起來.

基于這些研究的啟發(fā)，本文將路由、信道分配和調(diào)度結(jié)合起來，提出一種依托信道分層方法的組合式路由結(jié)合調(diào)度的方案，以期更有效地利用資源和提升傳輸性能.

1 模型及算法

1.1 圖模型

為了減少信道分配的復(fù)雜度，引入笛卡爾乘積(Cartesian Product of Graph,CPG)模型[13]，方便多并發(fā)流條件下路徑選擇判據(jù)的討論. 多并發(fā)流下的無線網(wǎng)狀網(wǎng)結(jié)構(gòu)可用Γ={G,I,Ω,ξ,{(si,di)}}來表示，其中：

(1)G=(V,E)為無向網(wǎng)狀圖，|V|代表節(jié)點(diǎn)數(shù)量，|E|代表邊的數(shù)量；

(2)I為G上節(jié)點(diǎn)之間的無線干擾關(guān)系；

(3)Ω={c1,c2,…,cq}為G上可用正交信道的集合，q為網(wǎng)絡(luò)中正交信道的數(shù)量；

(4)ξ為節(jié)點(diǎn)接口數(shù)量；

(5){(si,di)}(i=1,2,…,ρ)為多個(gè)源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)對(duì)的集合；

(6)Λ={i}={(si,di),zi}為列表{(si,di)}相對(duì)應(yīng)的傳輸請(qǐng)求隊(duì)列，zi(zi>0)為數(shù)據(jù)的大小.

在無線網(wǎng)狀網(wǎng)中，路由問題是為每一個(gè)傳輸請(qǐng)求確定一條從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑. 路徑可被視為一條包含了有限個(gè)首尾相接的連接構(gòu)成，可以用一個(gè)順序的節(jié)點(diǎn)序列表示. 信道分配是為所選擇的路徑上的每一條連接分配信道. 調(diào)度是將一個(gè)傳輸時(shí)隙分配給找到的路徑上的每一條連接. 從源節(jié)點(diǎn)開始，數(shù)據(jù)包被逐跳傳輸?shù)胶罄^節(jié)點(diǎn)，直到傳輸?shù)侥繕?biāo)節(jié)點(diǎn)為止.

根據(jù)正交信道的數(shù)量q，CPG模型將網(wǎng)狀網(wǎng)分為q個(gè)虛擬層，各層拓?fù)浣Y(jié)構(gòu)相同，所屬正交信道不同. 此時(shí)，一個(gè)多信道多接口節(jié)點(diǎn)因其參與通信的信道層，其身份轉(zhuǎn)化為信道差異的節(jié)點(diǎn)，本質(zhì)上還是該節(jié)點(diǎn)自身. 為每一條連接尋找可用信道時(shí)，只需逐層檢測當(dāng)前網(wǎng)絡(luò)層下的信道可用性. 若該連接在當(dāng)前網(wǎng)絡(luò)層下能滿足同一信道中的連接可共存條件[14](2個(gè)不同的發(fā)射節(jié)點(diǎn)間的距離不小于2跳；2個(gè)不同的接收節(jié)點(diǎn)間的距離不小于1跳；發(fā)射節(jié)點(diǎn)與接收節(jié)點(diǎn)間的距離大于1跳)，則當(dāng)前網(wǎng)絡(luò)層所屬的信道為該連接的可用信道.

1.2 路徑選擇判據(jù)

為解決路由問題，首先，需要根據(jù)當(dāng)前網(wǎng)狀網(wǎng)的拓?fù)湟约翱捎觅Y源找到幾條可選路徑；其次，基于路徑選擇判據(jù)，從可選路徑中選擇最合適的一條路徑. 盡管以跳數(shù)作為路由度量的最短路徑并不能獲得較好的網(wǎng)絡(luò)性能[15]，但在網(wǎng)絡(luò)資源充足的情況下，最短路徑由于其跳數(shù)小、占用資源少的特點(diǎn)仍為首選路徑. 另外，尋找其他路徑與最短路徑進(jìn)行比較，以找到最合適的路徑.

在路徑發(fā)現(xiàn)階段，對(duì)給定節(jié)點(diǎn)對(duì)(si,di)，先采用BFS算法找到一條(si,di)的最短路徑，確定其長度li，并將該最短路徑放入路由表中. 然后采用回溯法搜索可用路徑. 為了防止路徑長度過長，占用過多網(wǎng)絡(luò)資源，回溯法將路徑長度的限制參數(shù)δi作為約束條件. 路徑長度的限制參數(shù)δi的計(jì)算公式如下：

δi=li+α,

(1)

其中，α為常數(shù)參數(shù)，該參數(shù)值由實(shí)驗(yàn)者根據(jù)實(shí)驗(yàn)需要指定. 同時(shí)，為了避免無休止地搜索可用路徑，當(dāng)可用路徑的數(shù)量為3時(shí)終止，并將所搜索到的可用路徑放入路由表中.

經(jīng)過路由發(fā)現(xiàn)，(si,di)的路由表中將有4條可用路徑，包括最短路徑以及3條由回溯法發(fā)現(xiàn)的可用路徑. 在后續(xù)的路徑選擇階段，將從(si,di)的路由表中選出最合適的一條路徑. 為此，需要建立一個(gè)合適的路徑選擇判據(jù). 本文將節(jié)點(diǎn)的可用接口數(shù)量和可用信道數(shù)量定義為節(jié)點(diǎn)可用資源. 其中，節(jié)點(diǎn)的可用接口指的是節(jié)點(diǎn)未被占用的接口，節(jié)點(diǎn)的可用信道指的是與當(dāng)前已存在的信道分配不沖突的信道. 對(duì)于一條路徑，其可用資源主要體現(xiàn)在路徑上所有節(jié)點(diǎn)的可用資源. 一條路徑的可用資源越多，路徑上節(jié)點(diǎn)的可用資源越多，路徑上節(jié)點(diǎn)被占用的資源也就越少，則路徑上節(jié)點(diǎn)負(fù)載越輕. 因此，選用可用資源多的路徑，能夠有效地繞過節(jié)點(diǎn)過載的區(qū)域，智能地選擇負(fù)載較輕的節(jié)點(diǎn)，實(shí)現(xiàn)節(jié)點(diǎn)負(fù)載均衡，從而避免資源競爭現(xiàn)象，有效地利用網(wǎng)絡(luò)資源.

(2)

(3)

1.3 資源有效利用

同一時(shí)隙下，更多的激活連接可以傳輸更多的數(shù)據(jù)，實(shí)現(xiàn)網(wǎng)絡(luò)的高性能傳輸. 為了有效利用網(wǎng)絡(luò)資源，在每個(gè)正交信道下找到更多的激活連接，并將其組合到一起以形成更多的路徑[14]. 這種通過恰當(dāng)?shù)亟M合正交信道上的多條無干擾連接而形成的路徑，稱之為可兼容路徑. 可兼容路徑上的每一條連接恰當(dāng)?shù)剡x擇最合適的信道，以規(guī)避可能產(chǎn)生的無線干擾，使其不會(huì)與此前已有路徑占有的信道分配產(chǎn)生沖突. 在整個(gè)網(wǎng)狀網(wǎng)中，多條路徑只有滿足可兼容條件才能夠并發(fā)傳輸.

找到可兼容路徑最關(guān)鍵的一點(diǎn)是：路徑上的節(jié)點(diǎn)有可用接口且所有跳的鄰節(jié)點(diǎn)對(duì)有可用信道. 確定一個(gè)節(jié)點(diǎn)是否有可用接口并不難，困難的是確定鄰節(jié)點(diǎn)對(duì)的可用信道. 對(duì)于路徑上某跳的鄰節(jié)點(diǎn)對(duì)，即發(fā)射節(jié)點(diǎn)和接收節(jié)點(diǎn)，其可用信道為發(fā)射節(jié)點(diǎn)和接收節(jié)點(diǎn)的可用信道集合的交集. 只有當(dāng)發(fā)射節(jié)點(diǎn)和接收節(jié)點(diǎn)都工作在同一正交信道時(shí)，才能夠建立連接，并進(jìn)一步激活.

1.4 組合優(yōu)化調(diào)度

要實(shí)現(xiàn)網(wǎng)絡(luò)資源的最大化利用，需要在Γ中調(diào)度盡可能多的連接，也就是說最大化多并發(fā)流連接的數(shù)量[16]. 本節(jié)將結(jié)合路由、信道分配和調(diào)度，提出一種組合優(yōu)化調(diào)度方案(Combinatorial Optimization Scheduling Scheme,COSS).

組合優(yōu)化調(diào)度方案的具體流程見算法1.

算法1組合優(yōu)化調(diào)度方案

輸入：Γ,Λ.

forv=1 to |V| do

updatedv;

updatecv;

end for

fort=1 toTdo

fori=1 toρdo

forj=1 toLido

vsis the sender ofli,j;

vdis the receiver ofli,j;

if (cvs>0)∧(cvd>0)∧(cvs∩cvd≠?) then

select one channelckfromcvs∩cvd;

else {at least one condition is not satisfied}

cancel the channel assignment forli,k,k=1 toj;

break;

end if

end for

ifj==Lithen

end if

end for

end for

該方案的具體步驟如下：

(1)在調(diào)度前，收集網(wǎng)絡(luò)的全局信息，包括節(jié)點(diǎn)、傳輸請(qǐng)求和網(wǎng)絡(luò)拓?fù)涞? 基于全局信息，更新所有節(jié)點(diǎn)的狀態(tài)，對(duì)所有傳輸請(qǐng)求作出合理的全局規(guī)劃，也就是協(xié)調(diào)調(diào)度.

(2)在調(diào)度時(shí)，首先將T劃分為多個(gè)時(shí)隙ti(ti=1,2,…,T). 在每個(gè)時(shí)隙下，逐一檢查未加入的所有路徑是否為當(dāng)前時(shí)隙下的可兼容路徑. 若符合可兼容路徑條件，則將該路徑分配合適的信道和當(dāng)前時(shí)隙，并加入中. 反復(fù)檢查，直到所有路徑都加入到，算法結(jié)束.

(3)一條路徑是否為可兼容路徑，可根據(jù)該路徑上的所有連接是否有可用資源來判定. 若路徑上的所有連接都有可用資源，則該路徑在當(dāng)前時(shí)隙下為可兼容路徑. 若路徑上某一連接沒有可用資源，則該路徑在當(dāng)前時(shí)隙下為不可兼容路徑，該路徑所分配的信道將被釋放.

算法1將網(wǎng)絡(luò)拓?fù)涞母轮芷赥分為多個(gè)時(shí)隙，通過逐一遍歷所有路徑，為符合可兼容路徑條件的每條路徑上每一跳的鄰節(jié)點(diǎn)對(duì)分配無干擾的信道及時(shí)隙，使之成為可兼容路徑，并將路徑加入到可同時(shí)調(diào)度的路徑組中. 通過啟發(fā)式的方法找到每個(gè)時(shí)隙下盡可能多的可兼容路徑，實(shí)現(xiàn)所有可兼容路徑組合優(yōu)化調(diào)度，最大化同一時(shí)隙下可兼容路徑的數(shù)量. 而同一時(shí)隙下更多的可兼容路徑可傳輸更多數(shù)據(jù)，有效地提高了網(wǎng)絡(luò)資源的利用.

2 仿真實(shí)驗(yàn)

本文將分別在不同網(wǎng)絡(luò)資源配置、多種流量請(qǐng)求下進(jìn)行仿真實(shí)驗(yàn)，根據(jù)網(wǎng)絡(luò)最大吞吐量、平均端到端時(shí)延、傳輸時(shí)間3個(gè)性能參數(shù)評(píng)估本文的COSS算法性能. 更進(jìn)一步，選用AODV路由協(xié)議[17]與COSS算法做對(duì)比實(shí)驗(yàn).

2.1 仿真場景及評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)場景是在1 000 m*1 000 m的區(qū)域范圍內(nèi)隨機(jī)生成64個(gè)節(jié)點(diǎn)，如圖1所示. 在仿真參數(shù)設(shè)置上，每個(gè)節(jié)點(diǎn)的可用接口數(shù)目R{4,8,12,16,20}，網(wǎng)絡(luò)的可用正交信道數(shù)量C{8,16,32,64,128}，數(shù)據(jù)包大小為1 MB，每個(gè)傳輸請(qǐng)求的數(shù)據(jù)包數(shù)量為250個(gè)，鏈路容量為200 MB/s，時(shí)隙為5 ms，時(shí)間周期為0.5 s.

在性能指標(biāo)上，采用能夠反映網(wǎng)狀網(wǎng)性能的指標(biāo)：網(wǎng)絡(luò)最大吞吐量、平均端到端時(shí)延、傳輸時(shí)間. 這些指標(biāo)定義如下：

(1)網(wǎng)絡(luò)最大吞吐量：在某個(gè)單位時(shí)間內(nèi)目標(biāo)節(jié)點(diǎn)所接收的最大數(shù)據(jù)量.

(2)平均端到端時(shí)延：一個(gè)數(shù)據(jù)包從源節(jié)點(diǎn)傳輸至目標(biāo)節(jié)點(diǎn)所需的時(shí)間.

(3)傳輸時(shí)間：所有傳輸請(qǐng)求從開始發(fā)送數(shù)據(jù)到全部數(shù)據(jù)被接收所需的時(shí)間.

圖1 64節(jié)點(diǎn)隨機(jī)拓?fù)鋱DFigure 1 The 64-node random topology

2.2 性能比較

2.2.1 不同網(wǎng)絡(luò)資源配置下的性能 將傳輸請(qǐng)求節(jié)點(diǎn)對(duì)數(shù)量設(shè)置為80對(duì)，通過改變網(wǎng)絡(luò)資源配置(節(jié)點(diǎn)接口數(shù)量和正交信道數(shù)量)，分析算法在不同網(wǎng)絡(luò)資源配置下性能指標(biāo)的變化情況.

由圖2可知：(1)當(dāng)C=8時(shí)，隨著接口數(shù)量的增加，網(wǎng)絡(luò)最大吞吐量并未有顯著提升. 這表明了該例中限制網(wǎng)絡(luò)最大吞吐量的主導(dǎo)因素是信道數(shù)量. (2)當(dāng)C=16、C=32時(shí)，隨著接口數(shù)量的增加，網(wǎng)絡(luò)最大吞吐量快速提升，但明顯因信道數(shù)呈現(xiàn)頂板效應(yīng). 這表明了接口數(shù)量較少時(shí)，限制網(wǎng)絡(luò)最大吞吐量的主導(dǎo)因素為接口數(shù)量；而當(dāng)接口數(shù)量足夠多時(shí)，限制網(wǎng)絡(luò)最大吞吐量的主導(dǎo)因素變?yōu)樾诺罃?shù)量. (3)當(dāng)C=64、C=128時(shí)，網(wǎng)絡(luò)最大吞吐量的折線幾乎重疊在一起，隨著接口數(shù)量的增加而不斷提升. 這表明了當(dāng)R≤20、C=64/C=128時(shí)，信道數(shù)量已經(jīng)足夠多，網(wǎng)絡(luò)最大吞吐量不再顯著提升，此時(shí)限制網(wǎng)絡(luò)最大吞吐量的主導(dǎo)因素是接口數(shù)量.

圖2 不同接口數(shù)量、信道數(shù)量下的最大吞吐量變化Figure 2 The changes of maximum throughput with different numbers of radios and channels

由圖3可知：隨著網(wǎng)絡(luò)資源配置的增加，網(wǎng)絡(luò)平均端到端時(shí)延維持穩(wěn)定且較小，網(wǎng)絡(luò)資源配置的增加并不會(huì)對(duì)網(wǎng)絡(luò)平均端到端時(shí)延產(chǎn)生影響. 這是因?yàn)榻?jīng)過組合優(yōu)化調(diào)度，同一時(shí)隙下的可兼容路徑間互不干擾，不會(huì)產(chǎn)生數(shù)據(jù)包重傳、丟包和網(wǎng)絡(luò)延遲高等情況，因而在不同的網(wǎng)絡(luò)資源配置的條件下，網(wǎng)絡(luò)平均端到端時(shí)延較為穩(wěn)定且較小.

圖3 不同接口數(shù)量、信道數(shù)量下的平均端到端時(shí)延變化Figure 3 The changes of average end-to-end delay with diffe-rent numbers of radios and channels

由圖4可知：隨著接口數(shù)量的增加，擁有更多信道數(shù)量的網(wǎng)絡(luò)的傳輸時(shí)間減少得更快. 這是因?yàn)镃OSS算法能夠有效地利用信道資源，最大化同一時(shí)隙下可兼容路徑的數(shù)量. 但是，對(duì)于給定的信道數(shù)量，當(dāng)接口數(shù)量超過某個(gè)閾值時(shí)，由于網(wǎng)絡(luò)中可用信道數(shù)量的限制，同一時(shí)隙下可兼容路徑的數(shù)量已達(dá)峰值，傳輸時(shí)間不再減少.

圖4 不同接口數(shù)量、信道數(shù)量下的傳輸時(shí)間變化Figure 4 The changes of transmission time with different numbers of radios and channels

2.2.2 多種流量請(qǐng)求下的性能 網(wǎng)絡(luò)資源配置分別設(shè)置為R=4∧C=8、R=12∧C=32、R=20∧C=128，通過改變節(jié)點(diǎn)對(duì)數(shù)量(從10對(duì)到160對(duì))，分析算法在不同節(jié)點(diǎn)對(duì)數(shù)量下性能指標(biāo)的變化.

由圖5可知：隨著節(jié)點(diǎn)對(duì)數(shù)量的增加，擁有更多網(wǎng)絡(luò)資源配置的網(wǎng)絡(luò)的最大吞吐量增加得更快. 這是因?yàn)榫W(wǎng)絡(luò)資源配置的提升能有效地提高網(wǎng)絡(luò)承載能力，使網(wǎng)絡(luò)在同一時(shí)隙下的可兼容路徑增多. 同時(shí)，網(wǎng)絡(luò)的最大吞吐量最終都趨于一個(gè)穩(wěn)定的值，這是因?yàn)楣?jié)點(diǎn)對(duì)數(shù)量已經(jīng)超過網(wǎng)絡(luò)承載能力，網(wǎng)絡(luò)同一時(shí)隙下可兼容路徑的數(shù)量已達(dá)峰值，故而網(wǎng)絡(luò)的最大吞吐量不再有顯著的提升.

圖5 不同節(jié)點(diǎn)對(duì)數(shù)量下最大吞吐量的變化Figure 5 The changes of maximum throughput with different numbers of pairs

由圖6可知：隨著節(jié)點(diǎn)對(duì)數(shù)量的增加，不同網(wǎng)絡(luò)資源配置下的平均端到端時(shí)延依舊保持穩(wěn)定. 這說明在多節(jié)點(diǎn)對(duì)數(shù)量下，COSS算法依舊能夠合理調(diào)度每個(gè)節(jié)點(diǎn)對(duì)，使其能夠在合適的時(shí)隙下無干擾地完成傳輸任務(wù). 這也同樣表明了COSS算法在高負(fù)載下能夠保持高資源利用率，使數(shù)據(jù)的傳輸保持穩(wěn)定.

圖6 不同節(jié)點(diǎn)對(duì)數(shù)量下平均端到端時(shí)延的變化Figure 6 The changes of average end-to-end delay with diffe-rent numbers of pairs

由圖7可知：(1)當(dāng)網(wǎng)絡(luò)資源配置為R=4∧C=8時(shí)，隨著節(jié)點(diǎn)對(duì)數(shù)量的增加，網(wǎng)絡(luò)傳輸時(shí)間幾乎呈線性增長. 這是因?yàn)槭芟抻谟邢薜木W(wǎng)絡(luò)資源配置，同一個(gè)時(shí)隙下激活的可兼容路徑數(shù)量有限. 當(dāng)節(jié)點(diǎn)對(duì)數(shù)量增加時(shí)，超過網(wǎng)絡(luò)承載能力的這部分節(jié)點(diǎn)對(duì)將被分配到下個(gè)周期傳輸數(shù)據(jù)，從而使得傳輸時(shí)間增加. (2)當(dāng)網(wǎng)絡(luò)資源配置為R=12∧C=32時(shí)，傳輸時(shí)間呈階梯狀增加. 取其中一段階梯(傳輸請(qǐng)求的節(jié)點(diǎn)對(duì)數(shù)量從10對(duì)到40對(duì))為例：當(dāng)節(jié)點(diǎn)對(duì)數(shù)量從10對(duì)增加到30對(duì)時(shí)，網(wǎng)絡(luò)負(fù)載并未到達(dá)網(wǎng)絡(luò)承載能力的瓶頸，無需增加時(shí)間周期便能完成傳輸任務(wù)；當(dāng)節(jié)點(diǎn)對(duì)數(shù)量從30對(duì)增加到40對(duì)時(shí)，由于網(wǎng)絡(luò)負(fù)載已經(jīng)超過網(wǎng)絡(luò)承載能力的瓶頸，超出網(wǎng)絡(luò)承載能力的這部分節(jié)點(diǎn)對(duì)將被分配到下個(gè)周期傳輸數(shù)據(jù)，因而所需傳輸時(shí)間增加. (3)類似地，當(dāng)網(wǎng)絡(luò)資源配置為R=20∧C=128時(shí)，所需傳輸時(shí)間也呈階梯狀增加.

圖7 不同節(jié)點(diǎn)對(duì)數(shù)量下傳輸時(shí)間的變化Figure 7 The changes of transmission time with different mumbers of pairs

2.2.3 對(duì)比實(shí)驗(yàn) 在對(duì)比試驗(yàn)中，本文選用了AODV路由協(xié)議作為對(duì)比算法. AODV路由協(xié)議是一種按需的路由協(xié)議，允許節(jié)點(diǎn)迅速獲得到達(dá)目的地的路由，且并不需要維護(hù)超出自己輻射范圍的路由.

網(wǎng)絡(luò)資源配置分別設(shè)置為R=4∧C=8、R=12∧C=32、R=20∧C=128，通過改變節(jié)點(diǎn)對(duì)數(shù)量(從10對(duì)到160對(duì))，比較COSS算法與AODV路由協(xié)議在不同節(jié)點(diǎn)對(duì)數(shù)量下平均吞吐量的變化.

由圖8可知：在不同的網(wǎng)絡(luò)資源配置下，COSS算法的平均吞吐量均優(yōu)于AODV路由協(xié)議. 而且，隨著網(wǎng)絡(luò)資源配置的提升，COSS算法的性能優(yōu)勢(shì)愈加凸顯. 這是因?yàn)锳ODV路由協(xié)議在路由階段時(shí)選用跳數(shù)作為路徑選擇判據(jù)，并未能充分考慮網(wǎng)絡(luò)資源；而COSS算法在路由階段時(shí)選用了資源可獲得度作為路徑選擇判據(jù)，能夠智能選擇當(dāng)前網(wǎng)絡(luò)資源下最大可用資源的路徑，有效地減少了多對(duì)節(jié)點(diǎn)對(duì)路徑之間的節(jié)點(diǎn)交叉重復(fù)度，實(shí)現(xiàn)了節(jié)點(diǎn)負(fù)載均衡，從而提升了網(wǎng)絡(luò)性能.

圖8 2種算法的平均吞吐量比較Figure 8 The comparison of average throughput between two algorithms

3 結(jié)論

針對(duì)多并發(fā)流的問題，本文提出了一種結(jié)合路由、信道分配和調(diào)度的組合優(yōu)化調(diào)度方案，旨在最大化網(wǎng)絡(luò)資源的利用，減少多并發(fā)流下路徑間的無線干擾. 該方案首先基于已經(jīng)收集的全局信息，包括節(jié)點(diǎn)、傳輸請(qǐng)求和網(wǎng)絡(luò)拓?fù)涞龋瑸槎鄶?shù)據(jù)流協(xié)調(diào)建立資源可獲得度最大的路徑；然后，為這些路徑協(xié)調(diào)分配無干擾的信道，使之成為可兼容路徑；最后，組合優(yōu)化調(diào)度所有可兼容路徑，最大化同一時(shí)隙下可兼容路徑的數(shù)量. 實(shí)驗(yàn)表明：該方案在不同網(wǎng)絡(luò)資源配置、多種流量請(qǐng)求下均能取得較好的性能，并在吞吐量上優(yōu)于AODV路由協(xié)議.