姜海龍

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

?

移動(dòng)Ad Hoc網(wǎng)絡(luò)中一種基于多路徑路由協(xié)議的QoS保障算法

姜海龍

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

摘要：移動(dòng)Ad Hoc網(wǎng)絡(luò)快速發(fā)展的同時(shí)，其中的服務(wù)質(zhì)量(QoS)保障問題也日漸突出。設(shè)計(jì)了一種適用于移動(dòng)Ad Hoc網(wǎng)絡(luò)中多路徑路由協(xié)議的路徑選擇和帶寬分配算法，選擇適合業(yè)務(wù)傳輸?shù)穆窂?，并合理分配帶寬，?shí)現(xiàn)QoS保障。計(jì)算機(jī)仿真表明，該算法能夠適應(yīng)移動(dòng)Ad Hoc網(wǎng)絡(luò)的動(dòng)態(tài)性、不穩(wěn)定性，有效地實(shí)現(xiàn)QoS保障，改善網(wǎng)絡(luò)整體性能。

關(guān)鍵詞：移動(dòng)Ad Hoc網(wǎng)絡(luò)；服務(wù)質(zhì)量；線性規(guī)劃

0引言

移動(dòng)Ad Hoc網(wǎng)絡(luò)是一種無中心、自組織、高動(dòng)態(tài)的無線網(wǎng)絡(luò)，目前廣泛應(yīng)用于軍事、工業(yè)、商業(yè)等領(lǐng)域。但是由于其存在帶寬資源受限、鏈路質(zhì)量不穩(wěn)定、網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化等特點(diǎn)[1]，移動(dòng)Ad Hoc網(wǎng)絡(luò)對(duì)服務(wù)質(zhì)量(QoS)要求較高的業(yè)務(wù)支持較差。

當(dāng)前移動(dòng)Ad Hoc網(wǎng)絡(luò)中的QoS保障機(jī)制尚處于研究階段。本文從網(wǎng)絡(luò)層路由協(xié)議出發(fā)，提出一種適用于多路徑路由協(xié)議的路徑選擇算法和帶寬分配算法，通過合理選擇傳輸路徑并且合理分配帶寬，盡可能提高傳輸帶寬，降低傳輸時(shí)延和丟包率，提高傳輸業(yè)務(wù)的QoS。

1問題建模

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

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

為了簡(jiǎn)化問題，假設(shè)多路徑路由協(xié)議已具備保證建立路徑時(shí)延滿足業(yè)務(wù)的最大時(shí)延要求Dmax的機(jī)制。這里僅需要考慮路徑的瓶頸帶寬和平均丟包率參數(shù)。僅選擇其中一條路徑傳輸業(yè)務(wù)可能無法保障業(yè)務(wù)的所有QoS要求得到滿足，因此需要采用分流傳輸和分集傳輸機(jī)制以滿足業(yè)務(wù)的QoS要求。通過分流傳輸可以擴(kuò)展可用帶寬資源，通過分集傳輸(在不同路徑上傳輸相同的冗余分組)可以提高容錯(cuò)率。這里用于分流傳輸?shù)穆窂绞褂眉螾a表示，用于分集傳輸?shù)穆窂绞褂眉螾b表示。

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

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

即任一用于分流傳輸?shù)穆窂降钠骄鶃G包率應(yīng)小于等于業(yè)務(wù)的最大丟包率要求。所有用于分集傳輸?shù)穆窂降目偲骄鶃G包率(所有分集傳輸路徑平均丟包率的乘積)應(yīng)小于等于業(yè)務(wù)的最大丟包率要求。

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

即任一傳輸業(yè)務(wù)的路徑應(yīng)滿足業(yè)務(wù)的最大時(shí)延要求。假設(shè)路由協(xié)議具備該機(jī)制，下文不再考慮。

用Ci表示業(yè)務(wù)在路徑Pi上傳輸?shù)拇鷥r(jià)，定義如下：

(1)

Ci反映了對(duì)應(yīng)路徑Pi的帶寬利用率。Ci越小，說明路徑Pi負(fù)載越小，傳輸性能越好。Ci越大，則說明路徑Pi負(fù)載越大，傳輸性能越差。

業(yè)務(wù)在所有選擇的路徑上傳輸?shù)目偞鷥r(jià)定義為：

(2)

(3)

約束條件為：

(4)

該優(yōu)化問題形似線性規(guī)劃問題，但其中包含較多的未知量，并非標(biāo)準(zhǔn)線性規(guī)劃問題。為了簡(jiǎn)化問題，采用的方法是通過一定原則確定其中部分未知量的值，將問題轉(zhuǎn)化為標(biāo)準(zhǔn)的線性規(guī)劃問題，然后再參照標(biāo)準(zhǔn)線性規(guī)劃問題的解法求解。

2求解過程

為了簡(jiǎn)化優(yōu)化問題，減少未知量，首先需要確定集合Pa和Pb包含的元素。

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

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

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

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

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

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

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

(5)

得到滿足。

當(dāng)Pb=?時(shí)，即不存在分集傳輸路徑。優(yōu)化目標(biāo)函數(shù)簡(jiǎn)化為：

(6)

設(shè)Pa元素個(gè)數(shù)為n，約束條件簡(jiǎn)化為：

(7)

這樣優(yōu)化問題被簡(jiǎn)化為標(biāo)準(zhǔn)線性規(guī)劃問題。

將約束條件轉(zhuǎn)化為標(biāo)準(zhǔn)型，得到：

(8)

將標(biāo)準(zhǔn)型約束條件轉(zhuǎn)化為規(guī)范型，存在以下2種情況。

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

(9)

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

用yi統(tǒng)一表示所有的決策變量，即：

(10)

則目標(biāo)函數(shù)轉(zhuǎn)化為以下形式：

(11)

約束條件轉(zhuǎn)化為以下形式：

(12)

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

(13)

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

用yi統(tǒng)一表示所有的決策變量，即：

(14)

則目標(biāo)函數(shù)轉(zhuǎn)化為以下形式：

(15)

約束條件轉(zhuǎn)化為以下形式：

(16)

當(dāng)Pa≠?且Pb≠?時(shí)，即同時(shí)存在分流傳輸路徑和分集傳輸路徑，優(yōu)化目標(biāo)函數(shù)轉(zhuǎn)化為：

(17)

(18)

此時(shí)優(yōu)化問題已經(jīng)被簡(jiǎn)化為標(biāo)準(zhǔn)線性規(guī)劃問題。

將約束條件轉(zhuǎn)化為標(biāo)準(zhǔn)型，得到：

(19)

(20)

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

用yi統(tǒng)一表示所有的決策變量，即：

(21)

則目標(biāo)函數(shù)轉(zhuǎn)化為以下形式：

(22)

約束條件轉(zhuǎn)化為以下形式：

(23)

(24)

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

用yi統(tǒng)一表示所有的決策變量，即：

(25)

則目標(biāo)函數(shù)轉(zhuǎn)化為以下形式：

(26)

約束條件轉(zhuǎn)化為以下形式：

(27)

(28)

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

用yi統(tǒng)一表示所有的決策變量，即：

(29)

則目標(biāo)函數(shù)轉(zhuǎn)化為以下形式：

(30)

約束條件轉(zhuǎn)化為以下形式：

(31)

(32)

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

用yi統(tǒng)一表示所有的決策變量，即：

(33)

則目標(biāo)函數(shù)轉(zhuǎn)化為以下形式：

(34)

約束條件轉(zhuǎn)化為以下形式：

(35)

3仿真驗(yàn)證

下面通過計(jì)算機(jī)軟件仿真驗(yàn)證采用本文算法的多路徑路由協(xié)議的性能。這里使用OPNET Modeler軟件[3-5]。網(wǎng)絡(luò)場(chǎng)景設(shè)置為：范圍10 km×10 km，節(jié)點(diǎn)數(shù)25個(gè)，每個(gè)節(jié)點(diǎn)按隨機(jī)路徑點(diǎn)模型運(yùn)動(dòng)，網(wǎng)絡(luò)初始拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1　網(wǎng)絡(luò)初始拓?fù)浣Y(jié)構(gòu)

仿真統(tǒng)計(jì)不同節(jié)點(diǎn)移動(dòng)速度下，以及不同業(yè)務(wù)分組到達(dá)率下的網(wǎng)絡(luò)吞吐量、時(shí)延和丟包率。并以無QoS保障的動(dòng)態(tài)源路由協(xié)議(DSR)性能作參考。

從圖2～圖4的仿真結(jié)果可以看到，在不同節(jié)點(diǎn)移動(dòng)速度條件下，采用本文算法的多路徑路由協(xié)議的吞吐量、端到端時(shí)延、丟包率均優(yōu)于DSR協(xié)議。

圖2　節(jié)點(diǎn)移動(dòng)速度與吞吐量關(guān)系曲線

圖3　節(jié)點(diǎn)移動(dòng)速度與端到端時(shí)延關(guān)系曲線

圖4　節(jié)點(diǎn)移動(dòng)速度與丟包率關(guān)系曲線

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

從圖5～圖7仿真結(jié)果可以看到，在不同業(yè)務(wù)分組到達(dá)率條件下，采用本文算法的多路徑路由協(xié)議的吞吐量、端到端時(shí)延、丟包率均優(yōu)于DSR協(xié)議。

圖5　業(yè)務(wù)分組到達(dá)率與吞吐量關(guān)系曲線

圖6　業(yè)務(wù)分組到達(dá)率與端到端時(shí)延關(guān)系曲線

圖7　業(yè)務(wù)分組到達(dá)率與丟包率關(guān)系曲線

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

由于多路徑路由協(xié)議采用分集傳輸，容錯(cuò)率較高，因此在業(yè)務(wù)分組到達(dá)率較高的情況下，雖然網(wǎng)絡(luò)負(fù)荷加重，丟包率依然低于DSR協(xié)議。

4結(jié)束語

本文針對(duì)在移動(dòng)Ad Hoc網(wǎng)絡(luò)中實(shí)現(xiàn)傳輸業(yè)務(wù)QoS保障的問題，提出一種適用于多路徑路由協(xié)議的路徑選擇和帶寬分配算法，并通過計(jì)算機(jī)軟件仿真驗(yàn)證了算法的性能。下一步將更多考慮在實(shí)際應(yīng)用場(chǎng)景中改進(jìn)算法，提高算法的實(shí)用性。

參考文獻(xiàn)

[1]陳林星，曾曦，曹毅.移動(dòng)Ad Hoc網(wǎng)絡(luò)——自組織分組無線網(wǎng)絡(luò)技術(shù)[M].北京：電子工業(yè)出版社，2012.

[2]陳開周.最優(yōu)化計(jì)算方法[M].西安：西安電子科技大學(xué)出版社，1985.

[3]陳敏.OPNET網(wǎng)絡(luò)仿真[M].北京：清華大學(xué)出版社，2004.

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

[5]龍華.OPNET Modeler與網(wǎng)絡(luò)仿真[M].西安：西安電子科技大學(xué)出版社，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

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

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

DOI:10.16426/j.cnki.jcdzdk.2016.02.026