一種基于QoS的無線Mesh網(wǎng)絡DSR路由優(yōu)化算法

1、    一種基于QoS的無線Mesh網(wǎng)絡DSR路由優(yōu)化算法    一種基于QoS的無線Mesh網(wǎng)絡DSR路由優(yōu)化算法    類別：通信網(wǎng)絡      1 引言 無線Mesh網(wǎng)絡(WireleSS Mesh 電池作為動力，拓撲變化較小。在單跳接入時，WMN看成是一種特殊的無線局域網(wǎng)(Wireless Lical Area Networks，簡稱WLAN)。目前無線Mesh網(wǎng)絡已作為解決“最后一公里”的網(wǎng)絡接入問題的解決

2、方案寫入IEEE標準。 無線Mesh接入網(wǎng)絡中，非常重要的問題就是路由選擇其協(xié)議借鑒Ad hoc網(wǎng)絡的路由協(xié)議，分為3種：第一種為先驗式路由協(xié)議，也稱為表驅動式路由協(xié)議(如DSDV、GSR、ZHLS等)；第二種為反應式路由協(xié)議，也稱為源驅動按需路由協(xié)議(如AODV、DSR、TCRA等)；第三種是前二者的混合稱為混合式路由協(xié)議(如ZRP等)。 源驅動按需路由協(xié)議中的動態(tài)源路由協(xié)議(DvnmicSarle Routing,稱稱DSR)是一種按需路由協(xié)議，它允許節(jié)點動態(tài)發(fā)現(xiàn)到目的節(jié)點的多跳路由。DSR協(xié)議具有支持單向鏈路，發(fā)現(xiàn)多條路由等優(yōu)點，但對路由需求反應慢，這樣可能造成時延、網(wǎng)絡擁塞等故障，從而

3、嚴重影響服務質量(Ouality ofService，簡稱QoS)。在優(yōu)化DSR協(xié)議的基礎上，對于多條可選擇的非相關路由應用博弈論于各節(jié)點間的功率增益、源節(jié)點的發(fā)射功率、接收端(目的節(jié)點或目的網(wǎng)關)的噪聲頻譜密度等，提出一種可有效提高數(shù)據(jù)效率，減少時延和網(wǎng)絡擁塞的新路由算法。 2 基于博弈論的DSR路由優(yōu)化算法 以DSR協(xié)議為基礎，引入博弈論的思想，綜合多種影響網(wǎng)絡傳輸?shù)囊蛩貙崿F(xiàn)DSR路由優(yōu)化算法。 21 無線Mesh網(wǎng)絡中的博弈論思想 博弈論應用于無線Mesh網(wǎng)絡，包括以下幾個方面。 (1)參與者 定義無線Mesh網(wǎng)絡中的源節(jié)點l是參與者，l為一個有限集合，l=l，2，3k。 (2)策略集合

4、本算法假定在無線Mesh網(wǎng)絡中，每個源節(jié)點都要選擇一定路由才能到達目的節(jié)點(或目的網(wǎng)關)，并且所選的路由策略盡可能保證源節(jié)點的最大吞吐量，盡可能減少時延和網(wǎng)絡擁塞等問題，以及提高QoS，所以在無線Mesh網(wǎng)絡中源節(jié)點到達目的節(jié)點(或目的網(wǎng)關1的所有可能單跳或多跳路由策略就是Mesh博弈論的策略集合。 (3)贏得集合無線Mesh網(wǎng)絡中，算法設定任意一對節(jié)點間的功率增益、每個源節(jié)點的發(fā)射功率、接收端(目的節(jié)點或目的網(wǎng)關)的噪聲頻譜密度等網(wǎng)絡必備因素。在此前提下，源節(jié)點根據(jù)一定的路由策略得到的符合完成吞吐量以及解決擁塞問題的路由，即博弈論中的Nash均衡點。 22 非相關路由的選擇標準 非相關路由數(shù)

5、目的增加有利于源節(jié)點尋找到大吞吐量、小時延的路由。從而實現(xiàn)網(wǎng)絡傳輸，隨之選擇非相關路由成為問題的關鍵。這里引用博弈論思想，由于備選的路由本身存在競爭關系，因此是一個動態(tài)博弈的過程。 在兩節(jié)點的并行鏈路拓撲情況下，均衡的存在性和唯一性可通過一定的弱凸條件得到。量化用戶i的延時函數(shù)為： 上述兩個假設保證Til(fl)是嚴格凸于fil的。只要保證這個模型是凸博弈，則它的均衡就存在。作為每條鏈路的最佳響應，最優(yōu)化的問題經上述假設成為一個存在均衡解凸問題。盡管如此，最佳響應的唯一性并不能保證均衡點的唯一性。當鏈路占用函數(shù)為無窮大時即當發(fā)送的數(shù)據(jù)大小無法在一條鏈路上傳輸時，就無法通過上述兩個約束條件來尋找

6、Nash均衡點，即尋找最合適的路由進行傳輸，這樣就引入均衡條件(3)：對于任何一個導致無限分配的流分配方案，至少可以找到一種將要傳輸通過更改流分配使其從無限代價轉化成有限代價，引入一個效用函數(shù)的方法來解決，該效用函數(shù)通常默認是凸增的，也即當業(yè)務流速率可能大于鏈路帶寬即有彈性需求時，其解決辦法就是增加鏈路分流超出固定需求的部分，而其代價就是使用該部分業(yè)務流。 對于無線Mesh網(wǎng)絡來說，判斷是否存在均衡點的方法就是利用齊次嚴凸(Diagonal Strict Convexity，簡稱DSC)，DSC是一種用來求解唯一均衡的常用工具。 如果DSC系統(tǒng)存在矢量，那么均衡就是唯一的，也就是說該g(f )

7、Pseudo-Jacobian矩陣是正定的，則均衡是唯一存在的。 由上述可知，當業(yè)務流速率小于鏈路帶寬時，則依據(jù)均衡條件(1)和(2)，在延時和吞吐量等因素間的博弈中找到最佳路由。而當業(yè)務流速率可能大于鏈路帶寬，即有彈性需求時，則依據(jù)均衡條件(3)，將流分配延時加入博弈的因素中，在這幾種因素中進行博弈，得到最佳路由。 依照以上對于基于博弈論的DSR路由優(yōu)化算法的闡述，發(fā)現(xiàn)該算法在增加了源節(jié)點到目的節(jié)點的非相關路由之后，考慮業(yè)務流速率小于或大于鏈路帶寬這兩種情況，在眾多備選的路由中，綜合延時、網(wǎng)絡吞吐量等因素，在這些因素的相互博弈中尋找到最佳的傳輸路由，理論上可以達到預定的優(yōu)化效果。 3 協(xié)議仿

8、真與性能價 31 仿真環(huán)境設定 仿真時選擇Linux下的ns一2的23l版本，MAC層采用80211協(xié)議，仿真環(huán)境是1 000 m×1 000 m，隨機分布50個節(jié)點。節(jié)點0每隔005 s發(fā)送一個數(shù)據(jù)分組，目的節(jié)點是節(jié)點19，其他節(jié)點不發(fā)送數(shù)據(jù)。節(jié)點每次傳輸數(shù)據(jù)時，從自身的路由表中選取一條路由行傳輸。首先為節(jié)點1設定選取方向，沿著該方向以一定速度移動。當移動到邊界時，再隨機選取另一個方向，以相同的速度移動。節(jié)點在低于10 ms的速度下仿真和模擬，以節(jié)點移動30 m為限與原始DSR協(xié)議相對比。 32 仿真結果分析 為了準確有效地比較這兩種算法的優(yōu)劣，選定數(shù)據(jù)效率、總請求數(shù)目、總開銷(按

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