一種解決Ad hoc網絡擁塞的優化算法

郭　晗,　范琳琳,　杜　潤

(長春工業大學 基礎科學學院， 吉林 長春　130012)

?

一種解決Ad hoc網絡擁塞的優化算法

郭晗,范琳琳,杜潤

(長春工業大學 基礎科學學院， 吉林 長春130012)

摘要：提出了一種基于網絡中信息流競爭的成本框架機制，利用鏈路中干擾的總成本對擁塞進行衡量，從而對擁塞問題進行分治處理，即將所要解決的問題分解為若干子問題，由此提出成本控制算法對擁塞問題進行優化。

關鍵詞：Ad hoc網絡； 路由協議； 競爭轉發； 自組織

0引言

Ad hoc網絡是一組帶有無線接收和發送裝置的移動節點組成的具有多跳、臨時性、自組織等特征的網絡系統。主要特點有無控制中心、節點移動、多跳無線連接，在軍事通信、災后緊急救援、傳感器網絡等環境中被廣泛應用。

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

1問題描述

在解決Ad hoc網絡中出現擁塞的情況時，假設在一定單位時間內的網絡狀態是穩定不變的[7-9]。用G=(WN，WL)來描述Ad hoc網絡的結構，用WN={1,2,…,N}表示無線節點的集合，WL={1,2,…,L}表示無線鏈路的集合。并假設無線鏈路l∈L的數據傳輸量為Ci，IS={1,2，…，S}是網絡中共享網絡資源的所有信息流的集合。若每個信息流s∈S都是由源節點s發出并經過無線鏈路集合L(s)∈L到達目的節點，則稱這種情況下的信息流為P2P，即節點到節點的多跳信息流，同時命名這條信息流在當前無線鏈路上的傳輸狀態為信息子流。S(i)={s∈S,i∈L(s)}是流經當前無線鏈路的信息子流的集合。為了更好地描述信息子流之間相互競爭的關系，文中提出了干擾集合的概念，即無線鏈路w的干擾集W是由能夠干擾信息子流，并且在無線鏈路w上進行傳輸的那些鏈路組成的集合。在信息子流相互競爭資源的過程中，某一特定時刻有且只有一個信息子流能夠占用鏈路w。因此，在無線鏈路上進行傳輸的所有信息流的累加容量不能高于鏈路l的信道容量。

結合信息流在傳輸過程中的競爭特點，將Ad hoc網絡的擁塞控制問題轉換為線性優化問題，此時的目標是使所有源節點的總效用最大化，即有如下表達：

(1)

2成本控制算法CCA

結合式(1)以及成熟的優化理論可以知道，源節點在進行數據發送的過程中存在一個唯一的最優解。文中的CCA算法把原有的問題分解成多個并行的，可以進行分布式解決的子問題，并對分解后的各子問題進行求解。

2.1基本算法描述及分析

在無線網絡中，每一個獨立的節點的接收功率會隨著路徑的改變而發生變化，即接收端與發送端之間的距離越遠，其接收功率就會變得越小，而理論上擁堵狀況也會逐漸降到最低。擁堵降到最低時也是傳輸數據最弱、最不可靠的時刻，因此,在設計算法時需要考慮如何平衡擁堵與接收功率之間的關系。現將式(1)進行拉格朗日描述，其對應的拉格朗日函數為：

(2)

式中:p----整個無線鏈路中的解決擁堵時的成本，調整算法中的p即可完成網絡擁堵的優化控制。

基于此，對CCA分析如下：

在理想情況下，Ad hoc網絡的網絡狀態是穩定不變的，只有在這種情況下CCA的優化能力才是最理想的，對于求解的結果才是最實用有效的，為了使實際情況盡可能接近理想狀況，在利用算法進行優化時要盡可能使其應用在最小的時間間隔內。與此同時,Ad hoc網絡的網絡狀態的變化是隨機、無序的，為此需要考察CCA適應網絡變化的能力。

在驗證過程中選取了現實中網絡運行時3個階段的網絡狀態，如圖1所示。

圖中包含了4個信息流f1、f2、f3、f4，且都經歷了3種網絡狀態，鏈路源節點和目的節點在圖中已經標記。假設信息的傳輸速率為0到600之間，鏈路4、5、8、10的網絡容量取為2 500，其他鏈路的容量則取為1 000進行實驗驗證。

圖1　網絡運行時狀態模擬圖

2.2實驗結果

在進行實驗1時，假設CCA算法的初始解為65，從而驗證CCA此時所具有的收斂性能。實驗結果見表1。

表1　實驗1的結果

在進行實驗2時，假設仍在迭代65次的前提下，網絡狀態會從階段1轉換至階段2，并且當迭代次數達到130次時，網絡狀態會從階段2轉換至階段3，同時與AIMD算法對同樣的數據進行比較，結果見表2。

為了充分體現CCA對網絡動態變化所對應的實時響應及其性能，從表2可以看出，CCA與AIMD兩種算法中，源節點的總效率函數的時間均值與全局效率函數的誤差對比，CCA算法的效率較高，誤差較小。

3結語

結合Ad hoc網絡的狀態多變以及其具有的多跳連接等特點，從信息流的成本控制角度出發，提出了成本控制算法CCA用以解決網絡擁堵控制，通過實驗表明，CCA算法的效率和誤差都較低，能夠有效提高網絡擁堵的控制效率。

參考文獻：

[1]李秀明.車載Ad hoc網絡中基于位置的路由協議研究[D]．重慶:重慶交通大學，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]郭浩洋.基于遺傳算法的網絡擁塞控制研究[D]．南昌：江西理工大學，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]常促宇，向勇，史美林.車載自組織網的現狀與發展[J]．通信學報，2007，28(11)：116-126.

[9]高偉峰.基于蟻群優化算法的Ad Hoc網絡路由協議研究[D]．北京：北京交通大學，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

作者簡介：郭晗(1979-)，女，漢族，吉林長春人，長春工業大學講師,碩士，主要從事計算機應用技術方向研究,E-mail:35550447@qq.com.

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

中圖分類號：TP 311

文獻標志碼：A

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