一種基于QoS的無(wú)線Mesh網(wǎng)絡(luò)DSR路由優(yōu)化算法-基礎(chǔ)電子

精品文檔-下載后可編輯一種基于QoS的無(wú)線Mesh網(wǎng)絡(luò)DSR路由優(yōu)化算法-基礎(chǔ)電子1引言

無(wú)線Mesh網(wǎng)絡(luò)(WireleSSMeshNetwork，簡(jiǎn)稱WMN)是一種新型的寬帶無(wú)線網(wǎng)絡(luò)結(jié)構(gòu)，即一種高容量、高速率的分布式無(wú)線網(wǎng)絡(luò)，其網(wǎng)絡(luò)拓?fù)渑c移動(dòng)Adhoc網(wǎng)絡(luò)相似，但WMN的網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)性較弱，一般不使用電池作為動(dòng)力，拓?fù)渥兓^小。在單跳接入時(shí)，WMN看成是一種特殊的無(wú)線局域網(wǎng)(WirelessLicalAreaNetworks，簡(jiǎn)稱WLAN)。目前無(wú)線Mesh網(wǎng)絡(luò)已作為解決“一公里”的網(wǎng)絡(luò)接入問(wèn)題的解決方案寫(xiě)入IEEE標(biāo)準(zhǔn)。

無(wú)線Mesh接入網(wǎng)絡(luò)中，非常重要的問(wèn)題就是路由選擇其協(xié)議借鑒Adhoc網(wǎng)絡(luò)的路由協(xié)議，分為3種：種為先驗(yàn)式路由協(xié)議，也稱為表驅(qū)動(dòng)式路由協(xié)議(如DSDV、GSR、ZHLS等)；第二種為反應(yīng)式路由協(xié)議，也稱為源驅(qū)動(dòng)按需路由協(xié)議(如AODV、DSR、TCRA等)；第三種是前二者的混合．稱為混合式路由協(xié)議(如ZRP等)。

源驅(qū)動(dòng)按需路由協(xié)議中的動(dòng)態(tài)源路由協(xié)議(DvnmicSarleRouting,稱稱DSR)是一種按需路由協(xié)議，它允許節(jié)點(diǎn)動(dòng)態(tài)發(fā)現(xiàn)到目的節(jié)點(diǎn)的多跳路由。DSR協(xié)議具有支持單向鏈路，發(fā)現(xiàn)多條路由等優(yōu)點(diǎn)，但對(duì)路由需求反應(yīng)慢，這樣可能造成時(shí)延、網(wǎng)絡(luò)擁塞等故障，從而嚴(yán)重影響服務(wù)質(zhì)量(OualityofService，簡(jiǎn)稱QoS)。在優(yōu)化DSR協(xié)議的基礎(chǔ)上，對(duì)于多條可選擇的非相關(guān)路由應(yīng)用博弈論于各節(jié)點(diǎn)間的功率增益、源節(jié)點(diǎn)的發(fā)射功率、接收端(目的節(jié)點(diǎn)或目的網(wǎng)關(guān))的噪聲頻譜密度等，提出一種可有效提高數(shù)據(jù)效率，減少時(shí)延和網(wǎng)絡(luò)擁塞的新路由算法。

2基于博弈論的DSR路由優(yōu)化算法

以DSR協(xié)議為基礎(chǔ)，引入博弈論的思想，綜合多種影響網(wǎng)絡(luò)傳輸?shù)囊蛩貙?shí)現(xiàn)DSR路由優(yōu)化算法。

2．1無(wú)線Mesh網(wǎng)絡(luò)中的博弈論思想

博弈論應(yīng)用于無(wú)線Mesh網(wǎng)絡(luò)，包括以下幾個(gè)方面。

(1)參與者定義無(wú)線Mesh網(wǎng)絡(luò)中的源節(jié)點(diǎn)l是參與者，l為一個(gè)有限集合，l={l，2，3…k}。

(2)策略集合本算法假定在無(wú)線Mesh網(wǎng)絡(luò)中，每個(gè)源節(jié)點(diǎn)都要選擇一定路由才能到達(dá)目的節(jié)點(diǎn)(或目的網(wǎng)關(guān))，并且所選的路由策略盡可能保證源節(jié)點(diǎn)的吞吐量，盡可能減少時(shí)延和網(wǎng)絡(luò)擁塞等問(wèn)題，以及提高QoS，所以在無(wú)線Mesh網(wǎng)絡(luò)中源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)(或目的網(wǎng)關(guān)1的所有可能單跳或多跳路由策略就是Mesh博弈論的策略集合。

(3)贏得集合無(wú)線Mesh網(wǎng)絡(luò)中，算法設(shè)定任意一對(duì)節(jié)點(diǎn)間的功率增益、每個(gè)源節(jié)點(diǎn)的發(fā)射功率、接收端(目的節(jié)點(diǎn)或目的網(wǎng)關(guān))的噪聲頻譜密度等網(wǎng)絡(luò)必備因素。在此前提下，源節(jié)點(diǎn)根據(jù)一定的路由策略得到的符合完成吞吐量以及解決擁塞問(wèn)題的路由，即博弈論中的Nash均衡點(diǎn)。

2．2非相關(guān)路由的選擇標(biāo)準(zhǔn)

非相關(guān)路由數(shù)目的增加有利于源節(jié)點(diǎn)尋找到大吞吐量、小時(shí)延的路由。從而實(shí)現(xiàn)網(wǎng)絡(luò)傳輸，隨之選擇非相關(guān)路由成為問(wèn)題的關(guān)鍵。這里引用博弈論思想，由于備選的路由本身存在競(jìng)爭(zhēng)關(guān)系，因此是一個(gè)動(dòng)態(tài)博弈的過(guò)程。

在兩節(jié)點(diǎn)的并行鏈路拓?fù)淝闆r下，均衡的存在性和性可通過(guò)一定的弱凸條件得到。量化用戶i的延時(shí)函數(shù)為：

上述兩個(gè)假設(shè)保證Til(fl)是嚴(yán)格凸于fil的。只要保證這個(gè)模型是凸博弈，則它的均衡就存在。作為每條鏈路的響應(yīng)，化的問(wèn)題經(jīng)上述假設(shè)成為一個(gè)存在均衡解凸問(wèn)題。盡管如此，響應(yīng)的性并不能保證均衡點(diǎn)的性。當(dāng)鏈路占用函數(shù)為無(wú)窮大時(shí)．即當(dāng)發(fā)送的數(shù)據(jù)大小無(wú)法在一條鏈路上傳輸時(shí)，就無(wú)法通過(guò)上述兩個(gè)約束條件來(lái)尋找Nash均衡點(diǎn)，即尋找合適的路由進(jìn)行傳輸，這樣就引入均衡條件(3)：對(duì)于任何一個(gè)導(dǎo)致無(wú)限分配的流分配方案，至少可以找到一種將要傳輸通過(guò)更改流分配使其從無(wú)限代價(jià)轉(zhuǎn)化成有限代價(jià)，引入一個(gè)效用函數(shù)的方法來(lái)解決，該效用函數(shù)通常默認(rèn)是凸增的，也即當(dāng)業(yè)務(wù)流速率可能大于鏈路帶寬即有彈性需求時(shí)，其解決辦法就是增加鏈路分流超出固定需求的部分，而其代價(jià)就是使用該部分業(yè)務(wù)流。

對(duì)于無(wú)線Mesh網(wǎng)絡(luò)來(lái)說(shuō)，判斷是否存在均衡點(diǎn)的方法就是利用齊次嚴(yán)凸(DiagonalStrictConvexity，簡(jiǎn)稱DSC)，DSC是一種用來(lái)求解均衡的常用工具。

如果DSC系統(tǒng)存在矢量ρ，那么均衡就是的，也就是說(shuō)該g(fρ)Pseudo-Jacobian矩陣是正定的，則均衡是存在的。

由上述可知，當(dāng)業(yè)務(wù)流速率小于鏈路帶寬時(shí)，則依據(jù)均衡條件(1)和(2)，在延時(shí)和吞吐量等因素間的博弈中找到路由。而當(dāng)業(yè)務(wù)流速率可能大于鏈路帶寬，即有彈性需求時(shí)，則依據(jù)均衡條件(3)，將流分配延時(shí)加入博弈的因素中，在這幾種因素中進(jìn)行博弈，得到路由。

依照以上對(duì)于基于博弈論的DSR路由優(yōu)化算法的闡述，發(fā)現(xiàn)該算法在增加了源節(jié)點(diǎn)到目的節(jié)點(diǎn)的非相關(guān)路由之后，考慮業(yè)務(wù)流速率小于或大于鏈路帶寬這兩種情況，在眾多備選的路由中，綜合延時(shí)、網(wǎng)絡(luò)吞吐量等因素，在這些因素的相互博弈中尋找到的傳輸路由，理論上可以達(dá)到預(yù)定的優(yōu)化效果。

3協(xié)議仿真與性能*價(jià)

3．1仿真環(huán)境設(shè)定

仿真時(shí)選擇Linux下的ns一2的2．3l版本，MAC層采用802．11協(xié)議，仿真環(huán)境是1000m×1000m，隨機(jī)分布50個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)0每隔0．05s發(fā)送一個(gè)數(shù)據(jù)分組，目的節(jié)點(diǎn)是節(jié)點(diǎn)19，其他節(jié)點(diǎn)不發(fā)送數(shù)據(jù)。節(jié)點(diǎn)每次傳輸數(shù)據(jù)時(shí)，從自身的路由表中選取一條路由行傳輸。首先為節(jié)點(diǎn)1設(shè)定選取方向，沿著該方向以一定速度移動(dòng)。當(dāng)移動(dòng)到邊界時(shí)，再隨機(jī)選取另一個(gè)方向，以相同的速度移動(dòng)。節(jié)點(diǎn)在低于10m／s的速度下仿真和模擬，以節(jié)點(diǎn)移動(dòng)30m為限與原始DSR協(xié)議相對(duì)比。

3．2仿真結(jié)果分析

為了準(zhǔn)確有效地比較這兩種算法的優(yōu)劣，選定數(shù)據(jù)效率、總請(qǐng)求數(shù)目、總開(kāi)銷(xiāo)(按字節(jié))、總開(kāi)銷(xiāo)分組數(shù)、端到端時(shí)延作為*估標(biāo)準(zhǔn)。綜合多次的仿真實(shí)驗(yàn)數(shù)據(jù)后，得出仿真結(jié)果如圖l所示。從圖1(a)看出，優(yōu)化的與原始的算法在數(shù)據(jù)效率上都比較好，但是隨著節(jié)點(diǎn)移動(dòng)距離的增加，優(yōu)化后的算法更能體現(xiàn)數(shù)據(jù)效率上的優(yōu)勢(shì)，基本上都達(dá)到了95％以上的數(shù)據(jù)效率，具有很高的吞吐量。圖1(b)所示優(yōu)化后算法的請(qǐng)求數(shù)目明顯小于原始DSR算法，這表明當(dāng)使用的路由中斷時(shí)，它有備用路由可用，不需要重新發(fā)起路由發(fā)現(xiàn)過(guò)程，體現(xiàn)其穩(wěn)健性。由圖1(c)可以看出優(yōu)化的算法中以控制分組數(shù)的開(kāi)銷(xiāo)比原始DSR協(xié)議要小，雖然在路由發(fā)現(xiàn)過(guò)程中會(huì)回復(fù)更多的路由應(yīng)答，但是在節(jié)點(diǎn)移動(dòng)的過(guò)程中，由于備用路由的減少反而具有更小的開(kāi)銷(xiāo)分組數(shù)，并隨著節(jié)點(diǎn)移動(dòng)距離的增加會(huì)變得更加明顯。由圖1(d)明顯看到優(yōu)化的算法比原始DSR算法時(shí)延要小。隨著節(jié)點(diǎn)移動(dòng)距離的增加變得越來(lái)越明顯。這是因?yàn)槭紫壬倭寺酚砂l(fā)現(xiàn)過(guò)程，其次每發(fā)送分組時(shí)，節(jié)點(diǎn)會(huì)隨機(jī)選取一條路由，所以每條路由的負(fù)載不會(huì)很大，這就減少了排隊(duì)擁塞問(wèn)題，再次，即便當(dāng)業(yè)務(wù)流速率大于鏈路帶寬即有彈性需求時(shí)，則將流分配延時(shí)加入博弈的因素，在這幾種因素中進(jìn)行博弈，進(jìn)而得到路由進(jìn)行傳輸