移動自組網(wǎng)中QoS多播路由的研究

郭慧（山西大學(xué)商務(wù)學(xué)院　信息學(xué)院，山西　太原 030031）

移動自組網(wǎng)中QoS多播路由的研究

郭慧
（山西大學(xué)商務(wù)學(xué)院信息學(xué)院，山西太原 030031）

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

移動自組網(wǎng)；多播；遺傳算法；服務(wù)質(zhì)量；路由算法

0　引言

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

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

1　QoS多播路由問題及改進

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

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

2　探測時間限制機制

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

switch（請求信息）

case search.request（i）

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

search.request給網(wǎng)絡(luò)中的所有節(jié)點

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（新加入節(jié)點 i的應(yīng)答時間t）

if（t≤T）then

path.permanent=path.temp；

else刪除 path.temp

break

3　性能分析

3.1正確性

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

設(shè)在多播樹 TM中，L（s，v）表示從 s到 v的路徑，V表示 L（s，v）上的點集，t表示新加入節(jié)點到 s的應(yīng)答時間。

證明定理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）根據(jù)探測時間限制機制，協(xié)議是依據(jù)（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）根據(jù)探測時間限制機制，當(dāng)min｛P（e）｝＞P時，節(jié)點才發(fā)出加入請求，所以對于?L（s，v）?TM，有minP（u）＞P。

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

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

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

3.2復(fù)雜性

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

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

4　遺傳算法在QoS多播路由中的應(yīng)用

4.1優(yōu)化目標

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

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

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

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

F=fc×fy×fx

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

當(dāng)σ＜0時，Δσ=1；當(dāng)σ＞0時，Δσ=λ。

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

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

4.2編碼機制

在遺傳算法中最重要的步驟就是制定編碼策略，本文采用二進制編碼，結(jié)合深度優(yōu)先遍歷樹的每個節(jié)點，每個染色體的解由一個二進制串表示，每個染色體的長度都為圖中節(jié)點的個數(shù) n，用 G（V，E）代表染色體的解s，設(shè)函數(shù)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選擇操作

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

4.4交叉和變異操作

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

5　仿真與實驗

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

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

隨著節(jié)點移動速度的提高，路由更新次數(shù)增多，網(wǎng)絡(luò)拓撲變化頻繁，分組轉(zhuǎn)發(fā)時間變長，端到端的平均延時也逐漸增大。仿真結(jié)果如圖1所示。

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

圖1　平均延時比較

6　結(jié)論

本文設(shè)計了一種基于遺傳算法的QoS多播路由，通過引入探測時間限制有效減少路由節(jié)點和鏈路的尋找范圍，同時降低了選擇無效節(jié)點和鏈路的可能性。這使得在利用遺傳算法對路由問題優(yōu)化時，變?yōu)閷Χ嗖ゼs束樹的優(yōu)化，優(yōu)化目標是使得多播約束樹具有低延遲時間和高的剩余電池能量，采用基于樹結(jié)構(gòu)的編碼機制，編碼和解碼過程易于實現(xiàn)。仿真結(jié)果表明，本方法是可行和有效的，且延時性要優(yōu)于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］.計算機應(yīng)用研究，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］張毅，張秀梅，陳煒，等.移動自組織網(wǎng)絡(luò)中基于移動 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無線網(wǎng)絡(luò)MAODV組播路由協(xié)議研究［J］.計算機工程與設(shè)計，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-），女，研究生，講師，主要研究方向：網(wǎng)絡(luò)及信息安全。