摘  要： 深入研究移動自組網中的多播路由問題，提出一種適用于移動自組網的基于遺傳算法的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 探測時間限制機制

　　采用探測時間限制機制建立路由，當建立一條新路由時，接收節點不在發送節點的鄰居節點列表中，發送節點發送一個路由請求包，該請求包包括請求的延遲抖動最大值、可用帶寬的最小值、剩余電池能量的最小值以及端到端的延遲最大值。當收到該請求包時，各接收節點對照自己和發送節點間的約束關系，判斷是否滿足，如果接收節點i滿足約束關系，主機i將在自己的路由表中添加一條臨時路由，并且再次向下一跳節點發送路由請求包。主機i將在T內保持探測狀態，T=2D-D（e），表示從發送節點s到接收節點i的總延遲。如果在T時間內s沒有收到來自i的回應，則臨時路由將被刪除。網絡中的多播路由探測時間限制機制采用連通性和狀態發現機制實現。因此，它增加了移動主機生成滿足約束條件路由的機率。

　　多播樹新成員加入的主要過程如下。其中，每個節點的請求信息由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）根據探測時間限制機制，協議是依據（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。

　　（2）根據探測時間限制機制，當且僅當delay（L（s，v））≤D且jitter（L（s，v））≤J時，節點才發出加入請求，新加入節點i的探測應答時間t≤T，其中T=2D- D（e）。這就保證了從節點s到i，再從i到s的總延遲時間2×delay（s，i）≤D（e）+T=2D，也即從源節點到目的節點的延遲時間小于延遲上限D。所以，對于L（s，v）TM，有L（s，v）必滿足延遲和延遲抖動的要求。

　　（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路由的優化目標就是在探測時間限制機制構造的多播樹中，選擇一條合適的路徑，使得：

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

　接收器到發射器距離為S[7]，則從發射器發送的每比特的能量消耗為Eelec+EampS2。假設每個發射器的發送功率相同，發送距離同為S，設節點的最大能量為Efull（n），節點消耗的能量為Econsume（n），則節點的剩余能量量化百分比為E（n）=[Efull（n）-Econsume（n）]/Efull（n）。多播樹的最大生命周期由一個帶有最低電池能量的節點n所限制。

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

　　4.2 編碼機制

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

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

　　如果b（s，i）=0，則viV；

　　如果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優化路由的范圍。

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. Energy supported AODV（EN-AODV） for QoS routing in 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. Multiobjective optimization of MPLS-IP networks with a variable neighborhood genetic algorithm[J]. Applied Soft Computing， 2013， 13（11）：4403-4412.

　　[7] 張毅，張秀梅，陳煒，等.移動自組織網絡中基于移動Agent的多約束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.