基于粒子群的tcp非凸優(yōu)化速率控制算法
唐美芹1，關(guān)新平2
（1、魯東大學(xué)數(shù)學(xué)與信息學(xué)院，山東煙臺264025;2燕山大學(xué)電氣工程學(xué)院，河北秦皇島066004）
摘 要：為了有效地解決網(wǎng)絡(luò)中擁基問題，針對實(shí)際網(wǎng)絡(luò)中存在非彈性流的情況，考慮了網(wǎng)絡(luò)中非凸優(yōu)化速率控制問題。基于****化用戶效用函數(shù)框架，去掉了以往研究中對效用函數(shù)的嚴(yán)格假設(shè)，利用粒子群方法設(shè)計了分布式速率控制算法。算法中鏈路從網(wǎng)絡(luò)獲知擁塞鏈路的條數(shù)，用戶根據(jù)對應(yīng)的效用函數(shù)和擁塞反饋信息調(diào)整自身速率。仿真結(jié)果表明，算法可以很快地收斂到****速率。
關(guān)鍵詞：擁塞控制；速率控制；效用函數(shù)；非凸優(yōu)化；粒子群方法
中圖分類號：tp 27 文獻(xiàn)標(biāo)識碼a
1引 言
隨著通信網(wǎng)絡(luò)中用戶數(shù)量的增長和滿足不同qos業(yè)務(wù)種類的增加，源分配制度成為網(wǎng)絡(luò)控制算法中研究的熱點(diǎn)。從1998年開始，“經(jīng)濟(jì)模型”已經(jīng)被廣泛應(yīng)用到網(wǎng)絡(luò)資源管理研究中在以往的基于效用函數(shù)模型的網(wǎng)絡(luò)速率分配問題中，大部分研究都是假設(shè)通信流為彈性的，其對應(yīng)的效用函數(shù)是凹的。在實(shí)際網(wǎng)絡(luò)中，存在非彈性流，對應(yīng)模型的目標(biāo)函數(shù)或約束往往是非凹的，使得****化問題交得難以解決。因此設(shè)計一種好的速率分配算法來更好地處理非凹效用函數(shù)對應(yīng)的速率問題十分必要。文獻(xiàn)[6]針對s型函數(shù)提出了一種分布式、子啟發(fā)式算法，稱為“自調(diào)節(jié)”啟發(fā)式算法，此算法可以解決s型函數(shù)所對應(yīng)的鏈路擁塞問題，可以在漸近的情況下得到****速率分配�；趯ε挤植际剿惴ㄊ諗康饺值�****化條件在文獻(xiàn)[7]中提出。當(dāng)用戶的效用函數(shù)是非凸的時候，通過調(diào)整鏈路容量保證對偶分布式算法的全局收斂性。本文針對實(shí)際網(wǎng)絡(luò)中存在非凹效用函數(shù)的情形，去掉對效用函數(shù)的嚴(yán)格假設(shè)，在對偶溝的存在情況下，應(yīng)用粒子群方法直接解決非凸優(yōu)化速率控制算法。
2速率****化算法
1)系統(tǒng)描述考慮通信網(wǎng)絡(luò)系統(tǒng)中有￡條鏈路和s個用戶，每條鏈路都有固定的容量為cl，單位是bit/s，此系統(tǒng)的效用函數(shù)為us(xs)。每條鏈路上有s(l)個用戶。網(wǎng)絡(luò)效用****化(num)是根據(jù)鏈路的線性流約束，對于源速率x，使得網(wǎng)絡(luò)的整體效用∑sus(xs)達(dá)到****化的問題，模型如下：
效用函數(shù)****化框架中對效用函數(shù)和流做了嚴(yán)格假設(shè)，使得問題(1)變得非常簡單但同時也限制了它的應(yīng)用性。特別是，效用函數(shù)總是被假設(shè)為遞增嚴(yán)格光滑函數(shù)，網(wǎng)絡(luò)效用****化問題就是凸優(yōu)化問題，因此全局****值可以很容易求得，然而實(shí)際網(wǎng)絡(luò)對應(yīng)的效用函數(shù)往往不是凹的。
2)粒子群方法介紹 粒子群方法i8i是一種基于群體智能的新型演化計算技術(shù)，其基本思想來源于對鳥群簡化社會模型的研究及行為模擬，可以用來解決非線性、非連續(xù)性以及非凸性問題，它已經(jīng)在許多復(fù)雜的****化問題上有廣泛的應(yīng)用，如用在電力系統(tǒng)優(yōu)化中的配電網(wǎng)擴(kuò)展規(guī)劃、檢修計劃、機(jī)組組合等領(lǐng)域，通訊領(lǐng)域中的路由選擇及移動通信基站布置優(yōu)化、天線陣列控制等領(lǐng)域，并且已經(jīng)取得了很好的效果。
粒子群方法還被用于神經(jīng)網(wǎng)絡(luò)進(jìn)化、電路設(shè)計、數(shù)字濾波器設(shè)計等方面。它是由kenndey和eerhart等人于1995年開發(fā)的一種演化計算技術(shù)，其基本思想來源于對鳥群簡化社會模型的研究及行為模擬。粒子群算法與其他演化算法的相似之處，也是根據(jù)對環(huán)境的適應(yīng)度將群體中的個體移動到好的區(qū)；不同之處在于它不像其他演他算法那樣對個體是用演化算子，而是將每個個體看作尋優(yōu)空間中的一個沒有質(zhì)量沒有體積的粒子，在搜索空間中以一定的速度飛行，通過對環(huán)境的學(xué)習(xí)與適應(yīng)，根據(jù)個體與群體的飛行經(jīng)驗的綜合分析結(jié)果來動態(tài)調(diào)整飛行速度。
在整個尋優(yōu)過程中，每個粒子的適應(yīng)值( fitness value)取決于所選擇的優(yōu)化函數(shù)值，并且每個粒子都有以下幾類信息：粒子當(dāng)前所處位置；到目前為止由自己發(fā)現(xiàn)的****位置（pbest），以信息視為粒子的自身飛行經(jīng)驗；到目前為止整個群體中所有粒子發(fā)現(xiàn)的****位置（gbest）（gbest是pbest中的****值），這可視為粒子群的同伴共享飛行經(jīng)驗。方向和運(yùn)動速度加以影響，很好地協(xié)調(diào)了粒子自身運(yùn)動和群體運(yùn)動之間的關(guān)系。
|
