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

2 基于博弈論的DSR路由優(yōu)化算法
以DSR協(xié)議為基礎，引入博弈論的思想，綜合多種影響網(wǎng)絡(luò )傳輸的因素實(shí)現DSR路由優(yōu)化算法。
2．1 無(wú)線(xiàn)Mesh網(wǎng)絡(luò )中的博弈論思想
博弈論應用于無(wú)線(xiàn)Mesh網(wǎng)絡(luò )，包括以下幾個(gè)方面。
(1)參與者 定義無(wú)線(xiàn)Mesh網(wǎng)絡(luò )中的源節點(diǎn)l是參與者，l為一個(gè)有限集合，l={l，2，3…k}。
(2)策略集合本算法假定在無(wú)線(xiàn)Mesh網(wǎng)絡(luò )中，每個(gè)源節點(diǎn)都要選擇一定路由才能到達目的節點(diǎn)(或目的網(wǎng)關(guān))，并且所選的路由策略盡可能保證源節點(diǎn)的最大吞吐量，盡可能減少時(shí)延和網(wǎng)絡(luò )擁塞等問(wèn)題，以及提高QoS，所以在無(wú)線(xiàn)Mesh網(wǎng)絡(luò )中源節點(diǎn)到達目的節點(diǎn)(或目的網(wǎng)關(guān)1的所有可能單跳或多跳路由策略就是Mesh博弈論的策略集合。
(3)贏(yíng)得集合無(wú)線(xiàn)Mesh網(wǎng)絡(luò )中，算法設定任意一對節點(diǎn)間的功率增益、每個(gè)源節點(diǎn)的發(fā)射功率、接收端(目的節點(diǎn)或目的網(wǎng)關(guān))的噪聲頻譜密度等網(wǎng)絡(luò )必備因素。在此前提下，源節點(diǎn)根據一定的路由策略得到的符合完成吞吐量以及解決擁塞問(wèn)題的路由，即博弈論中的Nash均衡點(diǎn)。
2．2 非相關(guān)路由的選擇標準
非相關(guān)路由數目的增加有利于源節點(diǎn)尋找到大吞吐量、小時(shí)延的路由。從而實(shí)現網(wǎng)絡(luò )傳輸，隨之選擇非相關(guān)路由成為問(wèn)題的關(guān)鍵。這里引用博弈論思想，由于備選的路由本身存在競爭關(guān)系，因此是一個(gè)動(dòng)態(tài)博弈的過(guò)程。
在兩節點(diǎn)的并行鏈路拓撲情況下，均衡的存在性和唯一性可通過(guò)一定的弱凸條件得到。量化用戶(hù)i的延時(shí)函數為：

式中，jil(fl)為節點(diǎn)i在鏈路l上的延時(shí)。
對于每個(gè)用戶(hù)來(lái)說(shuō)，其延時(shí)為經(jīng)過(guò)鏈路上的延時(shí)之和，每個(gè)鏈路占用率只與該鏈路上的業(yè)務(wù)流相關(guān)。假設鏈路的均衡條件：

(2)Til連續可微，嚴格遞增且是凸函數。為每單位流量。
該假設保都是凸函數，鏈路占用函數為：

式中：Cl為鏈路帶寬,fl為業(yè)務(wù)流速率。且flCl，否則Til(fl)趨近于無(wú)窮，從(1)式可知它包含無(wú)窮大值(到無(wú)窮大的過(guò)程是連續的)。
對于一個(gè)Nash均衡點(diǎn)．每個(gè)業(yè)務(wù)流分配都是對其他所有聯(lián)合流分布的一個(gè)最佳反應，則：

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

在這里，定義為流分配延時(shí)的加權和，并且

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

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