移動Ad Hoc網絡中一種基于多路徑路由協議的QoS保障算法

姜海龍

(中國電子科技集團公司第20研究所，西安 710068)

?

移動Ad Hoc網絡中一種基于多路徑路由協議的QoS保障算法

姜海龍

(中國電子科技集團公司第20研究所，西安 710068)

摘要：移動Ad Hoc網絡快速發展的同時，其中的服務質量(QoS)保障問題也日漸突出。設計了一種適用于移動Ad Hoc網絡中多路徑路由協議的路徑選擇和帶寬分配算法，選擇適合業務傳輸的路徑，并合理分配帶寬，實現QoS保障。計算機仿真表明，該算法能夠適應移動Ad Hoc網絡的動態性、不穩定性，有效地實現QoS保障，改善網絡整體性能。

關鍵詞：移動Ad Hoc網絡；服務質量；線性規劃

0引言

移動Ad Hoc網絡是一種無中心、自組織、高動態的無線網絡，目前廣泛應用于軍事、工業、商業等領域。但是由于其存在帶寬資源受限、鏈路質量不穩定、網絡拓撲動態變化等特點[1]，移動Ad Hoc網絡對服務質量(QoS)要求較高的業務支持較差。

當前移動Ad Hoc網絡中的QoS保障機制尚處于研究階段。本文從網絡層路由協議出發，提出一種適用于多路徑路由協議的路徑選擇算法和帶寬分配算法，通過合理選擇傳輸路徑并且合理分配帶寬，盡可能提高傳輸帶寬，降低傳輸時延和丟包率，提高傳輸業務的QoS。

1問題建模

假設已經利用某種多路徑路由協議在網絡中2點之間建立了多條鏈路不相交路徑。本文研究的重點在于如何從中選擇合適的傳輸路徑，及如何在選擇路徑上合理分配傳輸帶寬，以保障業務的帶寬、時延、丟包率等QoS要求得到滿足。

下面對上述問題進行建模。假設源目的節點之間建立了n條(n≥2)鏈路不相交路徑，表示為集合P={P1,P2,…,Pn}。其中任一條路徑Pi(1≤i≤n)均具備下列QoS參數：瓶頸帶寬Bi、總時延Di、總平均丟包率Li，表示為(Bi,Di,Li)。當前傳輸業務的QoS要求如下：最小帶寬要求λmin、最大時延要求Dmax、最大平均丟包率要求Lmax。

為了簡化問題，假設多路徑路由協議已具備保證建立路徑時延滿足業務的最大時延要求Dmax的機制。這里僅需要考慮路徑的瓶頸帶寬和平均丟包率參數。僅選擇其中一條路徑傳輸業務可能無法保障業務的所有QoS要求得到滿足，因此需要采用分流傳輸和分集傳輸機制以滿足業務的QoS要求。通過分流傳輸可以擴展可用帶寬資源，通過分集傳輸(在不同路徑上傳輸相同的冗余分組)可以提高容錯率。這里用于分流傳輸的路徑使用集合Pa表示，用于分集傳輸的路徑使用集合Pb表示。

即任一路徑上分配的分集帶寬(如果存在)與所有路徑分流帶寬的總和應大于等于業務的最小帶寬要求。

即任一路徑上分配的分流帶寬與分集帶寬(如果存在)的總和應小于等于該路徑的瓶頸帶寬。

即任一用于分流傳輸的路徑的平均丟包率應小于等于業務的最大丟包率要求。所有用于分集傳輸的路徑的總平均丟包率(所有分集傳輸路徑平均丟包率的乘積)應小于等于業務的最大丟包率要求。

(4) Di≤Djmax(?i滿足1≤i≤n且λi>0)

即任一傳輸業務的路徑應滿足業務的最大時延要求。假設路由協議具備該機制，下文不再考慮。

用Ci表示業務在路徑Pi上傳輸的代價，定義如下：

(1)

Ci反映了對應路徑Pi的帶寬利用率。Ci越小，說明路徑Pi負載越小，傳輸性能越好。Ci越大，則說明路徑Pi負載越大，傳輸性能越差。

業務在所有選擇的路徑上傳輸的總代價定義為：

(2)

(3)

約束條件為：

(4)

該優化問題形似線性規劃問題，但其中包含較多的未知量，并非標準線性規劃問題。為了簡化問題，采用的方法是通過一定原則確定其中部分未知量的值，將問題轉化為標準的線性規劃問題，然后再參照標準線性規劃問題的解法求解。

2求解過程

為了簡化優化問題，減少未知量，首先需要確定集合Pa和Pb包含的元素。

按如下算法確定Pb包含的元素(Pc表示滿足Li≤Lmax的所有路徑的集合)：

(2) 如果Pb在P中的補集CPPb=?，Pb確定失敗，結束；否則從CPPb中選取Pi，滿足Li>Lmax且Li最小，更新Pb=Pb∪{Pi}，轉(3)。

(4) 如果Pb在P中的補集CPPb=?，Pb確定失敗，結束；否則從CPPb中選取Pi，滿足Bi≥λmin且Li最小，更新Pb=Pb∪{Pi}，轉(5)。

按如下算法確定Pa包含的元素：

(1) Pa=?。對于所有的Li(1≤i≤n)，如果不存在Li滿足Li≤Lmax，則Pa=?，結束；否則轉(2)。

(2) 如果Pa在P中的補集CPPa=?，Pa確定失敗，結束；否則從CPPa中選取Pi，滿足Li

這樣Pa和Pb包含元素得到確定，同時約束條件:

(5)

得到滿足。

當Pb=?時，即不存在分集傳輸路徑。優化目標函數簡化為：

(6)

設Pa元素個數為n，約束條件簡化為：

(7)

這樣優化問題被簡化為標準線性規劃問題。

將約束條件轉化為標準型，得到：

(8)

將標準型約束條件轉化為規范型，存在以下2種情況。

情況1：Bi1-λmin≥0，得到：

(9)

在這里，取基變量為λi1、xj(j=2,3,…,n+1)。

用yi統一表示所有的決策變量，即：

(10)

則目標函數轉化為以下形式：

(11)

約束條件轉化為以下形式：

(12)

情況2：Bi1-λmin<0，由于約束條件矩陣中找不到單位基，需要額外添加人工變量xn+2，得到：

(13)

在這里，取基變量為λi1、xj(j=3,4,…,n+2)。

用yi統一表示所有的決策變量，即：

(14)

則目標函數轉化為以下形式：

(15)

約束條件轉化為以下形式：

(16)

當Pa≠?且Pb≠?時，即同時存在分流傳輸路徑和分集傳輸路徑，優化目標函數轉化為：

(17)

(18)

此時優化問題已經被簡化為標準線性規劃問題。

將約束條件轉化為標準型，得到：

(19)

(20)

在這里，取基變量為λi1、xj(j=2,3,…,n1+n2+1+l)。

用yi統一表示所有的決策變量，即：

(21)

則目標函數轉化為以下形式：

(22)

約束條件轉化為以下形式：

(23)

(24)

在這里，取基變量為λi1、xj(j=3,4,…,n1+n2+2+l)。

用yi統一表示所有的決策變量，即：

(25)

則目標函數轉化為以下形式：

(26)

約束條件轉化為以下形式：

(27)

(28)

在這里，取基變量為λi1、xj(j=2,3,…,n2+1+l)。

用yi統一表示所有的決策變量，即：

(29)

則目標函數轉化為以下形式：

(30)

約束條件轉化為以下形式：

(31)

(32)

在這里，取基變量為λi1、xj(j=2,3+l,4+l,…,n2+2+l)。

用yi統一表示所有的決策變量，即：

(33)

則目標函數轉化為以下形式：

(34)

約束條件轉化為以下形式：

(35)

3仿真驗證

下面通過計算機軟件仿真驗證采用本文算法的多路徑路由協議的性能。這里使用OPNET Modeler軟件[3-5]。網絡場景設置為：范圍10 km×10 km，節點數25個，每個節點按隨機路徑點模型運動，網絡初始拓撲結構如圖1所示。

圖1　網絡初始拓撲結構

仿真統計不同節點移動速度下，以及不同業務分組到達率下的網絡吞吐量、時延和丟包率。并以無QoS保障的動態源路由協議(DSR)性能作參考。

從圖2～圖4的仿真結果可以看到，在不同節點移動速度條件下，采用本文算法的多路徑路由協議的吞吐量、端到端時延、丟包率均優于DSR協議。

圖2　節點移動速度與吞吐量關系曲線

圖3　節點移動速度與端到端時延關系曲線

圖4　節點移動速度與丟包率關系曲線

由于多路徑路由協議采用分流傳輸，能夠充分利用網絡帶寬資源，并且選擇的路徑丟包率較低，因此在節點移動速度較快的情況下，吞吐量下降程度低于DSR協議。多路徑路由協議選擇的路徑均滿足業務的時延要求，因此端到端時延低于DSR協議。由于多路徑路由協議采用分集傳輸，容錯率較高，因此在節點移動速度較快的情況下，雖然鏈路失效概率增加，丟包率依然低于DSR協議。

從圖5～圖7仿真結果可以看到，在不同業務分組到達率條件下，采用本文算法的多路徑路由協議的吞吐量、端到端時延、丟包率均優于DSR協議。

圖5　業務分組到達率與吞吐量關系曲線

圖6　業務分組到達率與端到端時延關系曲線

圖7　業務分組到達率與丟包率關系曲線

由于多路徑路由協議采用分流傳輸，帶寬資源較充足，在業務分組到達率較高的情況下，吞吐量高于DSR協議。多路徑路由協議選擇的路徑均滿足業務的時延要求，因此端到端時延低于DSR協議。

由于多路徑路由協議采用分集傳輸，容錯率較高，因此在業務分組到達率較高的情況下，雖然網絡負荷加重，丟包率依然低于DSR協議。

4結束語

本文針對在移動Ad Hoc網絡中實現傳輸業務QoS保障的問題，提出一種適用于多路徑路由協議的路徑選擇和帶寬分配算法，并通過計算機軟件仿真驗證了算法的性能。下一步將更多考慮在實際應用場景中改進算法，提高算法的實用性。

參考文獻

[1]陳林星，曾曦，曹毅.移動Ad Hoc網絡——自組織分組無線網絡技術[M].北京：電子工業出版社，2012.

[2]陳開周.最優化計算方法[M].西安：西安電子科技大學出版社，1985.

[3]陳敏.OPNET網絡仿真[M].北京：清華大學出版社，2004.

[4]王文博，張金文.OPNET Modeler與網絡仿真[M].北京：人民郵電出版社,2003.

[5]龍華.OPNET Modeler與網絡仿真[M].西安：西安電子科技大學出版社，2006.

An Algorithm of QoS Guarantees Based on Multipath Routing Protocol in Mobile Ad Hoc Network

JIANG Hai-long

(The 20th Research Institute of CETC，Xi'an 710068,China)

Abstract:With the rapid development of mobile Ad Hoc network (MANET)，quality of service (QoS) guarantee in MANET is becoming increasingly prominent.This paper designs routing selection and bandwidth allocation algorithm applicable to the multipath routing protocol in MANET.In this algorithm,the paths suiting for operation transmission are selected and bandwidth is allocated reasonably to realize the QoS guarantee.Computer simulation results show that the algorithm can adapt to the dynamics and instability of MANET,and realize QoS guarantees effectively,improve the overall performance of the networks.

Key words:mobile Ad Hoc network;quality of service;linear programming

收稿日期:2015-12-01

中圖分類號：TP393

文獻標識碼：A

文章編號：CN32-1413(2016)02-0105-07

DOI:10.16426/j.cnki.jcdzdk.2016.02.026