無線網(wǎng)絡(luò)中的信道分配和路由算法研究.pdf

1、無線mesh網(wǎng)絡(luò)由無線路由器和無線接入點(diǎn)通過多跳連接的方式組成，具有傳輸速率較高、覆蓋范圍較廣和組網(wǎng)成本較低等特點(diǎn)，是解決無線終端接入Internet的一種比較有競爭力的技術(shù)方案。無線鏈路的傳輸速率因鏈路干擾問題而降低，目前降低干擾的一種有效方法是采用正交信道傳輸數(shù)據(jù)，在802.11a/b/g等標(biāo)準(zhǔn)中定義了不同數(shù)目的正交信道，研究如何有效利用正交信道提高網(wǎng)絡(luò)吞吐率具有十分重要的意義。 本文基于IEEE 802.11 MAC協(xié)議，

2、圍繞如何提高無線mesh網(wǎng)絡(luò)吞吐率這一問題，開展了以下研究工作： 針對目前已有的集中式靜態(tài)信道分配算法在大規(guī)模無線mesh網(wǎng)絡(luò)中存在的可擴(kuò)放性問題，提出了基于鏈路負(fù)載信息的分布式信道分配算法——LLDCA算法。該算法通過分布式構(gòu)建鏈路沖突圖，使同一沖突域內(nèi)數(shù)據(jù)傳輸量較大的鏈路優(yōu)先選擇干擾程度較低的信道，互不干擾的鏈路間能夠并行選擇信道，從而較大降低了鏈路分配所需要的輪數(shù)。理論分析表明，對任意給定的正整數(shù)t，該算法在O(Log n

3、)+t+1輪內(nèi)結(jié)束的概率大于1-(D/D+1)<'t-1>，其中n為網(wǎng)絡(luò)中數(shù)據(jù)傳輸量大于O的鏈路數(shù)目，D為鏈路沖突圖的最大頂點(diǎn)度；各鏈路的消息復(fù)雜度為D(D)。模擬實(shí)驗(yàn)表明該分布式算法的性能與Raniwala等人提出的集中式分配算法的性能相當(dāng)，與Group CA算法相比較能夠?qū)⒕W(wǎng)絡(luò)吞吐率提升3倍左右。 針對目前缺少統(tǒng)一的靜態(tài)信道分配算法性能評價標(biāo)準(zhǔn)的問題，提出了基于“沖突鏈路帶寬占用率”的性能評價模型，通過計算同一沖突域中每條鏈

4、路所在信道的帶寬占用率，量化了信道分配結(jié)果對每條鏈路的影響，該模型能夠較好評價各種靜態(tài)信道分配算法的性能?；谠撛u價模型，提出了使用“網(wǎng)絡(luò)拓?fù)淇刂啤辈呗詢?yōu)化靜態(tài)信道分配的算法，根據(jù)“沖突鏈路帶寬占用率”的計算結(jié)果判斷是否使用當(dāng)前已有鏈路傳輸待分配鏈路的數(shù)據(jù)。模擬實(shí)驗(yàn)表明在網(wǎng)絡(luò)中同時存在數(shù)據(jù)傳輸量較大和較小的鏈路時，該方法能夠利用更多的正交信道，使網(wǎng)絡(luò)吞吐率在LLDCA算法的基礎(chǔ)上再提升10％以上。 針對混合式無線mesh網(wǎng)絡(luò)中因

5、少量節(jié)點(diǎn)在信道切換時存在較多沖突而影響傳輸速率的問題，提出了分布式信道切換序列生成算法——RCS算法。RCS算法采用隨機(jī)置換策略生成新的切換序列，從而較好的分散了節(jié)點(diǎn)間的傳輸沖突，均衡了各節(jié)點(diǎn)的有效傳輸帶寬。在RCS算法中，各網(wǎng)絡(luò)節(jié)點(diǎn)的信道切換序列獨(dú)立生成，有利于節(jié)點(diǎn)的動態(tài)加入和離開，其運(yùn)行時間與正交信道的數(shù)目成線性關(guān)系，保證了信道切換序列生成的實(shí)時性。仿真實(shí)驗(yàn)表明，在網(wǎng)絡(luò)負(fù)載程度達(dá)到75％以上時，該算法與當(dāng)前同類算法相比能夠?qū)⒕W(wǎng)絡(luò)節(jié)點(diǎn)

6、獲得的有效帶寬最小值提升30％以上，網(wǎng)絡(luò)總吞吐率提升5％～15％。針對目前基于混合式策略的信道分配算法未考慮各節(jié)點(diǎn)數(shù)據(jù)傳輸量差異從而導(dǎo)致信道負(fù)載不均的問題，提出了負(fù)載平衡的分布式信道分配算法——LBCA。通過分布式構(gòu)建節(jié)點(diǎn)局部沖突圖，使處于同一沖突域中數(shù)據(jù)傳輸量較多的節(jié)點(diǎn)優(yōu)先選擇負(fù)載較小的信道，從而較好平衡了各信道負(fù)載。模擬實(shí)驗(yàn)表明，在網(wǎng)絡(luò)負(fù)載程度達(dá)到80％以上時，對可用信道數(shù)目不大于6的網(wǎng)絡(luò)，LBCA算法獲得的網(wǎng)絡(luò)吞吐率與當(dāng)前相關(guān)算法

7、相比提升了10％以上。 針對當(dāng)前多信道路由度量標(biāo)準(zhǔn)在網(wǎng)絡(luò)中數(shù)據(jù)流的數(shù)量較少時，不能夠充分利用網(wǎng)絡(luò)的可選路徑和信道資源問題，提出了一種基于“跨層設(shè)計”的按需路由和信道分配算法。該算法綜合考慮路由問題與信道分配問題，首先利用目前已有的多信道路由度量標(biāo)準(zhǔn)使用按需路由策略尋找最小傳輸時延路徑，然后為該路徑上的相鄰鏈路盡量分配互不相同的信道，從而降低了路徑上相鄰鏈路間的干擾，提高了網(wǎng)絡(luò)吞吐率。模擬實(shí)驗(yàn)表明，在信道數(shù)目為12且“源節(jié)點(diǎn)”和“

8、目的節(jié)點(diǎn)”總數(shù)量占網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的比例小于50％時，該算法與當(dāng)前同類型算法相比，能夠?qū)⒕W(wǎng)絡(luò)吞吐率提升10％～20％。 針對當(dāng)前的無線mesh網(wǎng)絡(luò)結(jié)構(gòu)難以有效解決在網(wǎng)絡(luò)中存在大量網(wǎng)內(nèi)和網(wǎng)間數(shù)據(jù)流時的數(shù)據(jù)有效傳輸問題，提出了一種新型的混合式無線mesh網(wǎng)絡(luò)結(jié)構(gòu)。在該結(jié)構(gòu)中，根據(jù)節(jié)點(diǎn)距離固定網(wǎng)絡(luò)接入點(diǎn)的距離，將網(wǎng)絡(luò)劃分為靜態(tài)mesh區(qū)域和動態(tài)mesh區(qū)域；并基于該網(wǎng)絡(luò)結(jié)構(gòu)提出了一種新型的路由算法，采用將反應(yīng)式路由協(xié)議和先驗(yàn)式路由協(xié)議相結(jié)