一種解決Ad hoc網(wǎng)絡(luò)擁塞的優(yōu)化算法

郭　晗,　范琳琳,　杜　潤(rùn)

(長(zhǎng)春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院， 吉林 長(zhǎng)春　130012)

?

一種解決Ad hoc網(wǎng)絡(luò)擁塞的優(yōu)化算法

郭晗,范琳琳,杜潤(rùn)

(長(zhǎng)春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院， 吉林 長(zhǎng)春130012)

摘要：提出了一種基于網(wǎng)絡(luò)中信息流競(jìng)爭(zhēng)的成本框架機(jī)制，利用鏈路中干擾的總成本對(duì)擁塞進(jìn)行衡量，從而對(duì)擁塞問(wèn)題進(jìn)行分治處理，即將所要解決的問(wèn)題分解為若干子問(wèn)題，由此提出成本控制算法對(duì)擁塞問(wèn)題進(jìn)行優(yōu)化。

關(guān)鍵詞：Ad hoc網(wǎng)絡(luò)； 路由協(xié)議； 競(jìng)爭(zhēng)轉(zhuǎn)發(fā)； 自組織

0引言

Ad hoc網(wǎng)絡(luò)是一組帶有無(wú)線接收和發(fā)送裝置的移動(dòng)節(jié)點(diǎn)組成的具有多跳、臨時(shí)性、自組織等特征的網(wǎng)絡(luò)系統(tǒng)。主要特點(diǎn)有無(wú)控制中心、節(jié)點(diǎn)移動(dòng)、多跳無(wú)線連接，在軍事通信、災(zāi)后緊急救援、傳感器網(wǎng)絡(luò)等環(huán)境中被廣泛應(yīng)用。

在互聯(lián)網(wǎng)領(lǐng)域，TCP擁塞控制算法[1-3]已經(jīng)比較成熟，能夠作為保證網(wǎng)絡(luò)性能穩(wěn)定的一種重要手段。但是傳統(tǒng)TCP的方法并不適合于Ad hoc網(wǎng)絡(luò)，所以當(dāng)網(wǎng)絡(luò)擁堵出現(xiàn)時(shí)會(huì)導(dǎo)致Ad hoc網(wǎng)絡(luò)的性能?chē)?yán)重下降。因此,學(xué)者們將優(yōu)化控制理論引入到Ad hoc擁塞控制當(dāng)中，在這個(gè)過(guò)程中產(chǎn)生了很多用于提高Ad hoc網(wǎng)絡(luò)性能的優(yōu)化算法。比如文獻(xiàn)[3]根據(jù)物理層的功率變化對(duì)擁塞控制的影響，提出了TCP Vegas和功率控制的聯(lián)合優(yōu)化算法[4-6]；文獻(xiàn)[4]根據(jù)MAC對(duì)擁塞控制的影響，提出了擁塞控制和MAC的聯(lián)合優(yōu)化算法。然而這些算法并沒(méi)有深入考慮Ad hoc網(wǎng)絡(luò)具有多跳無(wú)線連接的這一特點(diǎn)，因此用于解決Internet擁塞的優(yōu)秀算法并不能很好地適應(yīng)Ad hoc的多源信息流相互競(jìng)爭(zhēng)的特點(diǎn)。為了解決這種情況，文中構(gòu)建了一個(gè)基于鏈路干擾集合的成本框架機(jī)制來(lái)解決Ad hoc網(wǎng)絡(luò)中信息流相互競(jìng)爭(zhēng)的問(wèn)題，在框架中利用某一條信息鏈路的總成本來(lái)衡量本鏈路的擁塞程度，通過(guò)針對(duì)本鏈路成本的成本控制算法(Cost Control Algorithm， CCA)，將擁塞問(wèn)題分解為若干相對(duì)獨(dú)立的子問(wèn)題并加以解決。最終結(jié)合Ad hoc網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)特性驗(yàn)證CCA算法在網(wǎng)絡(luò)動(dòng)態(tài)變化的情況下對(duì)于優(yōu)化網(wǎng)絡(luò)擁塞的適應(yīng)性。實(shí)驗(yàn)結(jié)果表明，CCA算法的收斂性較好，對(duì)于網(wǎng)絡(luò)動(dòng)態(tài)變化的適應(yīng)性有較高的自適應(yīng)能力，從而使得Ad hoc網(wǎng)絡(luò)的性能得到了一定程度的提高。

1問(wèn)題描述

在解決Ad hoc網(wǎng)絡(luò)中出現(xiàn)擁塞的情況時(shí)，假設(shè)在一定單位時(shí)間內(nèi)的網(wǎng)絡(luò)狀態(tài)是穩(wěn)定不變的[7-9]。用G=(WN，WL)來(lái)描述Ad hoc網(wǎng)絡(luò)的結(jié)構(gòu)，用WN={1,2,…,N}表示無(wú)線節(jié)點(diǎn)的集合，WL={1,2,…,L}表示無(wú)線鏈路的集合。并假設(shè)無(wú)線鏈路l∈L的數(shù)據(jù)傳輸量為Ci，IS={1,2，…，S}是網(wǎng)絡(luò)中共享網(wǎng)絡(luò)資源的所有信息流的集合。若每個(gè)信息流s∈S都是由源節(jié)點(diǎn)s發(fā)出并經(jīng)過(guò)無(wú)線鏈路集合L(s)∈L到達(dá)目的節(jié)點(diǎn)，則稱這種情況下的信息流為P2P，即節(jié)點(diǎn)到節(jié)點(diǎn)的多跳信息流，同時(shí)命名這條信息流在當(dāng)前無(wú)線鏈路上的傳輸狀態(tài)為信息子流。S(i)={s∈S,i∈L(s)}是流經(jīng)當(dāng)前無(wú)線鏈路的信息子流的集合。為了更好地描述信息子流之間相互競(jìng)爭(zhēng)的關(guān)系，文中提出了干擾集合的概念，即無(wú)線鏈路w的干擾集W是由能夠干擾信息子流，并且在無(wú)線鏈路w上進(jìn)行傳輸?shù)哪切╂溌方M成的集合。在信息子流相互競(jìng)爭(zhēng)資源的過(guò)程中，某一特定時(shí)刻有且只有一個(gè)信息子流能夠占用鏈路w。因此，在無(wú)線鏈路上進(jìn)行傳輸?shù)乃行畔⒘鞯睦奂尤萘坎荒芨哂阪溌穕的信道容量。

結(jié)合信息流在傳輸過(guò)程中的競(jìng)爭(zhēng)特點(diǎn)，將Ad hoc網(wǎng)絡(luò)的擁塞控制問(wèn)題轉(zhuǎn)換為線性優(yōu)化問(wèn)題，此時(shí)的目標(biāo)是使所有源節(jié)點(diǎn)的總效用最大化，即有如下表達(dá)：

(1)

2成本控制算法CCA

結(jié)合式(1)以及成熟的優(yōu)化理論可以知道，源節(jié)點(diǎn)在進(jìn)行數(shù)據(jù)發(fā)送的過(guò)程中存在一個(gè)唯一的最優(yōu)解。文中的CCA算法把原有的問(wèn)題分解成多個(gè)并行的，可以進(jìn)行分布式解決的子問(wèn)題，并對(duì)分解后的各子問(wèn)題進(jìn)行求解。

2.1基本算法描述及分析

在無(wú)線網(wǎng)絡(luò)中，每一個(gè)獨(dú)立的節(jié)點(diǎn)的接收功率會(huì)隨著路徑的改變而發(fā)生變化，即接收端與發(fā)送端之間的距離越遠(yuǎn)，其接收功率就會(huì)變得越小，而理論上擁堵?tīng)顩r也會(huì)逐漸降到最低。擁堵降到最低時(shí)也是傳輸數(shù)據(jù)最弱、最不可靠的時(shí)刻，因此,在設(shè)計(jì)算法時(shí)需要考慮如何平衡擁堵與接收功率之間的關(guān)系?，F(xiàn)將式(1)進(jìn)行拉格朗日描述，其對(duì)應(yīng)的拉格朗日函數(shù)為：

(2)

式中:p----整個(gè)無(wú)線鏈路中的解決擁堵時(shí)的成本，調(diào)整算法中的p即可完成網(wǎng)絡(luò)擁堵的優(yōu)化控制。

基于此，對(duì)CCA分析如下：

在理想情況下，Ad hoc網(wǎng)絡(luò)的網(wǎng)絡(luò)狀態(tài)是穩(wěn)定不變的，只有在這種情況下CCA的優(yōu)化能力才是最理想的，對(duì)于求解的結(jié)果才是最實(shí)用有效的，為了使實(shí)際情況盡可能接近理想狀況，在利用算法進(jìn)行優(yōu)化時(shí)要盡可能使其應(yīng)用在最小的時(shí)間間隔內(nèi)。與此同時(shí),Ad hoc網(wǎng)絡(luò)的網(wǎng)絡(luò)狀態(tài)的變化是隨機(jī)、無(wú)序的，為此需要考察CCA適應(yīng)網(wǎng)絡(luò)變化的能力。

在驗(yàn)證過(guò)程中選取了現(xiàn)實(shí)中網(wǎng)絡(luò)運(yùn)行時(shí)3個(gè)階段的網(wǎng)絡(luò)狀態(tài)，如圖1所示。

圖中包含了4個(gè)信息流f1、f2、f3、f4，且都經(jīng)歷了3種網(wǎng)絡(luò)狀態(tài)，鏈路源節(jié)點(diǎn)和目的節(jié)點(diǎn)在圖中已經(jīng)標(biāo)記。假設(shè)信息的傳輸速率為0到600之間，鏈路4、5、8、10的網(wǎng)絡(luò)容量取為2 500，其他鏈路的容量則取為1 000進(jìn)行實(shí)驗(yàn)驗(yàn)證。

圖1　網(wǎng)絡(luò)運(yùn)行時(shí)狀態(tài)模擬圖

2.2實(shí)驗(yàn)結(jié)果

在進(jìn)行實(shí)驗(yàn)1時(shí)，假設(shè)CCA算法的初始解為65，從而驗(yàn)證CCA此時(shí)所具有的收斂性能。實(shí)驗(yàn)結(jié)果見(jiàn)表1。

表1　實(shí)驗(yàn)1的結(jié)果

在進(jìn)行實(shí)驗(yàn)2時(shí)，假設(shè)仍在迭代65次的前提下，網(wǎng)絡(luò)狀態(tài)會(huì)從階段1轉(zhuǎn)換至階段2，并且當(dāng)?shù)螖?shù)達(dá)到130次時(shí)，網(wǎng)絡(luò)狀態(tài)會(huì)從階段2轉(zhuǎn)換至階段3，同時(shí)與AIMD算法對(duì)同樣的數(shù)據(jù)進(jìn)行比較，結(jié)果見(jiàn)表2。

為了充分體現(xiàn)CCA對(duì)網(wǎng)絡(luò)動(dòng)態(tài)變化所對(duì)應(yīng)的實(shí)時(shí)響應(yīng)及其性能，從表2可以看出，CCA與AIMD兩種算法中，源節(jié)點(diǎn)的總效率函數(shù)的時(shí)間均值與全局效率函數(shù)的誤差對(duì)比，CCA算法的效率較高，誤差較小。

3結(jié)語(yǔ)

結(jié)合Ad hoc網(wǎng)絡(luò)的狀態(tài)多變以及其具有的多跳連接等特點(diǎn)，從信息流的成本控制角度出發(fā)，提出了成本控制算法CCA用以解決網(wǎng)絡(luò)擁堵控制，通過(guò)實(shí)驗(yàn)表明，CCA算法的效率和誤差都較低，能夠有效提高網(wǎng)絡(luò)擁堵的控制效率。

參考文獻(xiàn)：

[1]李秀明.車(chē)載Ad hoc網(wǎng)絡(luò)中基于位置的路由協(xié)議研究[D]．重慶:重慶交通大學(xué)，2011.

[2]Yang Shuangmao, Guo Wei, Tang Wei. National key laboratory of science and technology on communications [J]． University of Electronic Science and Technology of China, Chengdu,2014,39(6):130-13.

[3]郭浩洋.基于遺傳算法的網(wǎng)絡(luò)擁塞控制研究[D]．南昌：江西理工大學(xué)，2013.

[4]H Zhai, Y Fang. Medium aeeess control protoeolsin mobile Ad Hoe neorks: problemsand solutions.[D]．Florid: Teehnieal Rort, University of Florid,2004.

[5]Anon. ADASE: Advanced driver assistance systems in europe[EB/OL]．(2009-10-20)[2016-01-11]. http://www.adase2.net.

[6]Anon. COMCAR: Communication and mobility by cellular advanced radio[EB/OL]．(2009-10-20)[2016-01-11]. http://www.comcar.de.

[7]Anon. DRiVE: Dynamic radio for IP-services in vehicular environments [EB/OL]．(2009-10-20)[2016-01-11]. http://www.ist-drive.org.

[8]常促宇，向勇，史美林.車(chē)載自組織網(wǎng)的現(xiàn)狀與發(fā)展[J]．通信學(xué)報(bào)，2007，28(11)：116-126.

[9]高偉峰.基于蟻群優(yōu)化算法的Ad Hoc網(wǎng)絡(luò)路由協(xié)議研究[D]．北京：北京交通大學(xué)，2014.

An optimization algorithm for solving the congestion of hoc Ad networks

GUO Han,FAN Linlin,DU Run

(School of Basic Sciences, Changchun University of Technology, Changchun 130012， China)

Abstract：A cost framework is put forward based on network information flow competition, and the total cost of link interference is used to evaluate the congestion. Consequently the congestion is classified into parts, and the cost control algorithm is applied to optimize the congestion.

Key words：Ad hoc network; routing protocol; competition forwarding; self-organization.

收稿日期：2016-01-11

作者簡(jiǎn)介：郭晗(1979-)，女，漢族，吉林長(zhǎng)春人，長(zhǎng)春工業(yè)大學(xué)講師,碩士，主要從事計(jì)算機(jī)應(yīng)用技術(shù)方向研究,E-mail:35550447@qq.com.

DOI:10.15923/j.cnki.cn22-1382/t.2016.2.19

中圖分類(lèi)號(hào)：TP 311

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-1374(2016)02-0200-03