移動自組網中QoS多播路由的研究

郭慧（山西大學商務學院　信息學院，山西　太原 030031）

移動自組網中QoS多播路由的研究

郭慧
（山西大學商務學院信息學院，山西太原 030031）

深入研究移動自組網中的多播路由問題，提出一種適用于移動自組網的基于遺傳算法的QoS多播路由算法。通過引入探測時間限制，有效減少了路由結點和鏈路的尋找范圍，同時降低了選擇無效結點和鏈路的可能性。通過證明，該方法滿足帶寬、延遲、延遲抖動、剩余能量約束的要求。在此基礎上，提出了一種基于遺傳算法的QoS路由選擇優化算法。仿真試驗表明，該算法是可行的，且延時性要優于MAODV。

移動自組網；多播；遺傳算法；服務質量；路由算法

0　引言

移動自組網［1］（Mobile Ad Hoc Networks，MANET）是由移動通信主機臨時組成的無線多跳網絡。當任何一個移動主機加入或離開其他移動主機的通信范圍時，無線連接也會相應地形成或斷開。網絡中的任何一個節點既充當主機又充當路由器。無線網絡的拓撲結構也會隨機地發生變化。由于移動自組網的動態性，使得網絡中的多播路由成為一個具有挑戰性的問題［2］。

服務質量（Quality-of-Service，QoS）的基本功能是基于 QoS約束［3］，找到一個好的路由。QoS約束包括：端到端的延遲、帶寬保證、抖動、丟包率等。隨著移動自組網對數據傳輸穩定性要求的提高，提供QoS保證已經成為MANET網絡研究中的一個重要領域［4］。盡管多約束可以更準確地模仿網絡和應用，但是基于MANET網絡的QoS多播路由問題是一個多約束的 NP完全問題［5］。這就意味著移動自組網中QoS多播路由問題不能在合理的時間范疇內優化解決，這對于普通的應用主體，尤其是對延遲敏感的應用是非常關鍵的。遺傳算法是仿真生物遺傳學和自然選擇機理通過人工方式所構造的一種新型優化算法［6］，它能夠進行自適應群體尋優，并行搜索，產生最優解集，已廣泛應用于解決各種NP完全問題。本文提出了一種基于遺傳算法的多約束多播路由，達到按需優化的目的。

1　QoS多播路由問題及改進

QoS多播路由的約束有以下屬性：（1）可加性：total_metric=Σimetrici，即總度量=各節點度量的和，路徑延遲和跳數是這類屬性的代表。（2）凹性：min_metric= mini｛metrici｝，它可以表示為：最小的度量=各節點度量的最小值，帶寬和剩余能量是這類屬性的代表，它們可以描述成可用帶寬的最小值或路徑上所有的鏈接和結點的剩余能量。（3）乘性：mul_metric=∏imetrici，即復合度量=各節點度量的積，包傳送率是這類屬性的代表。

尋找多播路由可以表示為尋找一棵從根節點到一系列接收節點的樹。假定網絡可表示為一個帶權圖G= （V，E），V是點集，表示一系列移動主機，E是邊集，表示連接移動主機間的鏈路，連接節點u和v的邊e∈E，e也可以表示為（u，v），其中 u，v∈V。一棵樹的根節點是s，s∈V，必須滿足以下各種約束。

2　探測時間限制機制

多播樹新成員加入的主要過程如下。其中，每個節點的請求信息由 search.request，build.request，reply組成。鏈路e的帶寬、延遲、延遲抖動和剩余電池能量分別表示為B（e）、D（e）、J（e）和P（e）。

switch（請求信息）

case search.request（i）

if（節點i不在發送節點的鄰居節點列表中 and min｛P（e）｝＞P）then發送

search.request給網絡中的所有節點

if（r.packet［i］.b≥B and r.packet［i］.d≤D and r. packet［i］.j≤J）

then send build.request（）to next；

break

case build.request（B，D，J，P）

if（b（e）≥B and d（e）≤D and j（e）≤J and min ｛P（e）｝＞P）then

path.temp=r.packet［i］.path；

send build（B，D，J，P，path.temp）to next；

break

case reply（新加入節點 i的應答時間t）

if（t≤T）then

path.permanent=path.temp；

else刪除 path.temp

break

3　性能分析

3.1正確性

定理1采用探測時間限制機制構造的多播樹TM能滿足帶寬、延遲、延遲抖動、剩余能量約束的要求。

設在多播樹 TM中，L（s，v）表示從 s到 v的路徑，V表示 L（s，v）上的點集，t表示新加入節點到 s的應答時間。

證明定理1等價于：

（1）對于?L（s，v）?TM，有bandwidth（L（s，v））≥B；

（2）對于?L（s，v）?TM，delay（L（s，v））≤D，jitter（L （s，v））≤J；

（3）對于?L（s，v）?TM，有min P（u）＞P。

證明：

（1）根據探測時間限制機制，協議是依據（delay（L）=（delay（v0，*）+delay（vm，vn）≤D）∧（jitter（L）=（jitter （v0，*）+jitter（vm，vn）≤（J）∧bandwidth（v0，vn）≥B）∧（t≤T）來計算 delay和jitter。因此，對于?L（s，v）?TM，bandwidth（L（s，v））≥B。

（3）根據探測時間限制機制，當min｛P（e）｝＞P時，節點才發出加入請求，所以對于?L（s，v）?TM，有minP（u）＞P。

結合上述（1），（2），（3）的證明可知，依據探測時間限制機制所構造的多播樹必能滿足帶寬、延遲、延遲抖動和剩余能量的約束。

定理2根據探測時間限制機制所構造的多播樹TM搜索的可行路徑是沒有回路的。

證明在 r.packet路由表中只存在一個輸入端，一個或多個輸出端，從輸入端到輸出端的路徑是一種樹形結構，當新節點加入時，各節點間仍然構成一棵多播樹。樹是連通無回路的，所以TM搜索的可行路徑是沒有回路的。

3.2復雜性

定理3探測時間限制機制的時間復雜度是O （|N|2× |V|2）

證明：由于探測時間限制機制的計算復雜度由加入請求、加入和退出操作3部分組成，如果QoS的特征值是延遲、帶寬和剩余能量，則其復雜度是O （|V|×|E|× |V|），其中|V|是網絡節點數，|E|是網絡鏈路數，其復雜度記為O（|V|2）。對于一個具有|N|個成員的多播樹，其計算復雜度 O（|N|2×|V|2）。

4　遺傳算法在QoS多播路由中的應用

4.1優化目標

基于上述說明，QoS路由的優化目標就是在探測時間限制機制構造的多播樹中，選擇一條合適的路徑，使得：

（3）min｛B（e）｝＞B

（4）min｛P（e）｝＞P

優化的目標是希望找到一條路徑使得該路徑的延遲最小、抖動最小、可用帶寬最大、剩余電池能量最大。這幾個目標的優化中，找到最優解或次優解。采用改進的遺傳算法實現QoS路由問題。為此，構造目標函數F：

F=fc×fy×fx

fc是懲罰函數，用來懲罰不易解決的方案。

當σ＜0時，Δσ=1；當σ＞0時，Δσ=λ。

σ是懲罰度，通常 0.01＜σ＜0.5。當 fc=1時，尋找到的QoS路徑可行；當0≤fc＜1時，QoS路由不易尋找。

綜上，通過最大化適應度值，最小化延遲時間，最大化剩余電池能量，來選擇最好的路由。

4.2編碼機制

在遺傳算法中最重要的步驟就是制定編碼策略，本文采用二進制編碼，結合深度優先遍歷樹的每個節點，每個染色體的解由一個二進制串表示，每個染色體的長度都為圖中節點的個數 n，用 G（V，E）代表染色體的解s，設函數b（s，i）代表s的第i位。

如果 b（s，i）=1，則 vi∈V；

如果b（s，i）=0，則vi?V；

如果 vi∈V，vj∈V，且（vi，vj）∈E，則 eij∈E。

4.3選擇操作

本文中的遺傳算法采用賭輪選擇機制，將當前代的解群中適應度最高的兩個個體結構完整地復制到下一代群體中。若變異概率為 Pm∈（0，1），交叉概率 Pc∈（0，1），且在選擇前保留當前最優解的遺傳算法可收斂于全局最優解［8］。可知該遺傳算法可以收斂于全局最優解。

4.4交叉和變異操作

在遺傳算法中的交叉算子使用單點交叉算法，變異算子使用位變異算法，交叉概率為 Pc，變異概率為 Pm，交叉時隨機選定一個交叉點，對該點前或后的兩個個體的結構進行互換，生成兩個新個體，位變異算法中低能量節點被高能量節點所代替。

5　仿真與實驗

本實驗基于NS-2仿真工具，在仿真中，使100個節點隨機分布在1 000 m×1 000 m的矩形區域內，每個節點的接口帶寬為2 Mb/s，無線直接通信的距離為250 m，數據包大小為512 B，在實驗中指定一個節點為源節點，向其他節點發送數據，每次實驗執行 300 s，模擬結果為多次實驗的平均值。

組播自組網按需距離矢量路由協議MAODV（Multicast Adhoc On-demand Distance VectorRouting Protocol）是一種基于樹的組播路由協議，這種按需的路由技術有效地減輕了網絡信道中協議控制包的負載，提高了信道利用率［9］。將新算法與MAODV進行比較，結果如下。

隨著節點移動速度的提高，路由更新次數增多，網絡拓撲變化頻繁，分組轉發時間變長，端到端的平均延時也逐漸增大。仿真結果如圖1所示。

新算法的延時性要優于MAODV，因為新算法采用了探測時間限制機制，避免了無限路由的生成，縮小了QoS優化路由的范圍。

圖1　平均延時比較

6　結論

本文設計了一種基于遺傳算法的QoS多播路由，通過引入探測時間限制有效減少路由節點和鏈路的尋找范圍，同時降低了選擇無效節點和鏈路的可能性。這使得在利用遺傳算法對路由問題優化時，變為對多播約束樹的優化，優化目標是使得多播約束樹具有低延遲時間和高的剩余電池能量，采用基于樹結構的編碼機制，編碼和解碼過程易于實現。仿真結果表明，本方法是可行和有效的，且延時性要優于MAODV。

［1］SUZUKI H，KOYAMA A，Implementation and evaluation of a real object-oriented communication method for ad-hoc networks［C］.Proc.of 26th IEEE International Conference on Advanced Information Networking and Application（AINA 2012），2012：906-911.

［2］BIRADAR R C，MANVI S S.Neighbor supported reliable multipath multicast routing in MANETs［J］.Journal of Network and Computer Applications，2012，35（3）：1074-1085.

［3］VALLS M G，ALONSO A，ANTONIO J.A dual-band priority assignment algorithm for dynamic QoS resource management［J］.Future Generation Computer Systems，2012，28 （6）：902-912.

［4］SRIDHAR S，BASKARAN R，CHANDRASEKAR P.EnergysupportedAODV（EN-AODV）forQoSroutingin MANET［J］.Procedia-Social and Behavioral Sciences，2013，73（2）：294-301.

［5］倪云竹，李志蜀，劉一靜.基于蟻群遺傳算法的 QoS多播路由研究［J］.計算機應用研究，2011，28（10）：3865-3868.

［6］ONETY R E，TADEI R，NETO O M，et al.MultiobjectiveoptimizationofMPLS-IPnetworkswithavariable neighborhood genetic algorithm［J］.Applied Soft Computing，2013，13（11）：4403-4412.

［7］張毅，張秀梅，陳煒，等.移動自組織網絡中基于移動 A-gent的多約束 QoS多播路由算法［J］.信息與控制，2010，39（1）：47-53.

［8］Huang Jun，Liu Yanbing.MOEAQ：a QoS-aware multicast routing algorithm for MANET［J］.Expert Systems with Applications，2010，37（2）：1391-1399.

［9］樊彪，施榮華.基于移動Ad-Hoc無線網絡MAODV組播路由協議研究［J］.計算機工程與設計，2010，31（1）：48-51.

Research of QoS multicast routing in mobile Ad Hoc networks

Guo Hui
（Information Faculty，Business College of Shanxi University，Taiyuan 030031，China）

Though studying the multicast routing problem in mobile Ad Hoc networks，the paper proposed a QoS multicast routing algorithm based on genetic algorithm suitable mobile ad hoc networks.By limiting the detected-time，reduced the search scope of routing nodes and links，moreover，reduce the possibilities of selecting invalid nodes and links.The test provied that the method satisfies the requirements of bandwidth，delay，delay jitter，and residual energy constraint.Proposed a genetic algorithmbased optimization algorithm for QoS routing.Simulation result shows that the algorithm is feasible，and the latency is better than MAODV.

mobile Ad Hoc networks；multicast；genetic algorithm；ouality-of-service；routing algorithm

TP393.0

A

1674-7720（2015）05-0057-03

（2014-11-07）

郭慧（1980-），女，研究生，講師，主要研究方向：網絡及信息安全。