基于多目標(biāo)拆分優(yōu)化思維的擁塞網(wǎng)絡(luò)數(shù)值調(diào)度方法*

陳鴻俊， 范太華， 穆　炯

(1. 西南科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 四川 綿陽 621010； 2. 四川水利職業(yè)技術(shù)學(xué)院 信息工程系， 成都 611231； 3. 四川農(nóng)業(yè)大學(xué) 信息工程學(xué)院， 四川 雅安 625014)

?

基于多目標(biāo)拆分優(yōu)化思維的擁塞網(wǎng)絡(luò)數(shù)值調(diào)度方法*

陳鴻俊1，2， 范太華1， 穆炯3

(1. 西南科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 四川 綿陽 621010； 2. 四川水利職業(yè)技術(shù)學(xué)院 信息工程系， 成都 611231； 3. 四川農(nóng)業(yè)大學(xué) 信息工程學(xué)院， 四川 雅安 625014)

針對網(wǎng)絡(luò)擁塞數(shù)值調(diào)度中存在的盲目性問題，提出了一種基于多目標(biāo)拆分優(yōu)化的網(wǎng)絡(luò)擁塞數(shù)值調(diào)度方法.將擁塞網(wǎng)絡(luò)的數(shù)值調(diào)度問題進行模型化表示，并將擁塞過程調(diào)度的最優(yōu)問題分解為多個目標(biāo)同時優(yōu)化問題：即信道最優(yōu)任務(wù)分配問題和路由擁塞調(diào)度問題.根據(jù)粒子群算法，對信道分配問題的最優(yōu)解進行計算，同時設(shè)計約束模型并利用遺傳算法求解擁塞調(diào)度問題，實現(xiàn)了在擁塞狀態(tài)下的網(wǎng)絡(luò)數(shù)值調(diào)度.結(jié)果表明，所提出算法獲得的擁塞調(diào)度方案具有較好的可執(zhí)行性.

網(wǎng)絡(luò)擁塞； 目標(biāo)拆分； 粒子群優(yōu)化； 遺傳算法； 數(shù)值調(diào)度； 信道分配； 網(wǎng)絡(luò)吞吐

隨著網(wǎng)絡(luò)計算的快速發(fā)展，網(wǎng)絡(luò)接入量逐漸呈現(xiàn)大數(shù)據(jù)的特點，當(dāng)前網(wǎng)絡(luò)受擁塞問題的影響越來越明顯[1].網(wǎng)絡(luò)接入量的不定和猛增給當(dāng)前計算機網(wǎng)絡(luò)信道容量帶來了較大的負(fù)荷壓力[2]，雖然網(wǎng)絡(luò)帶寬技術(shù)在不斷完善，但遠(yuǎn)遠(yuǎn)不能滿足網(wǎng)絡(luò)吞吐量巨大的需求給網(wǎng)絡(luò)任務(wù)的合理調(diào)度帶來的問題[3-4].

在網(wǎng)絡(luò)擁塞控制中，對數(shù)值的調(diào)度問題可以看成一個NP問題，針對這一問題，很多學(xué)者提出了不同的方法.文獻[5]結(jié)合粒子群優(yōu)化(PSO)方法對多種信息調(diào)度過程進行建模，以時間作為約束完成數(shù)據(jù)調(diào)度，由于網(wǎng)絡(luò)調(diào)度數(shù)據(jù)種類差別較大，數(shù)據(jù)的網(wǎng)絡(luò)接入時間和接入量存在較大的變化，所以PSO解決單一的NP問題存在較大的弊端；文獻[6]提出了一種改進PSO的網(wǎng)絡(luò)數(shù)據(jù)調(diào)度方法，雖然在原方法基礎(chǔ)上進行了必要的改進，但由于調(diào)度過程本身存在矛盾，導(dǎo)致應(yīng)用環(huán)境受限；文獻[7]突出了基于遺傳算法的網(wǎng)絡(luò)資源調(diào)度優(yōu)點，從鏈路調(diào)度與信道分配為目標(biāo)函數(shù)構(gòu)建標(biāo)準(zhǔn)，雖然已經(jīng)具備了一定的任務(wù)拆分理論模型，但是由于選取的約束目標(biāo)為硬件，導(dǎo)致應(yīng)用被大大限制.本文提出了一種基于多目標(biāo)拆分優(yōu)化思維的擁塞網(wǎng)絡(luò)數(shù)值調(diào)度方法，實現(xiàn)了在擁塞狀態(tài)下網(wǎng)絡(luò)數(shù)值調(diào)度.

1　擁塞狀態(tài)下調(diào)度數(shù)據(jù)的多目標(biāo)拆分

當(dāng)網(wǎng)絡(luò)發(fā)生擁塞時，其擁塞區(qū)域和路由區(qū)域會發(fā)生較為明顯的變化，這種變化會直接反應(yīng)到網(wǎng)絡(luò)的MAC層和應(yīng)用層.2個層級直接的關(guān)聯(lián)性為0，故對擁塞資源進行調(diào)度的目標(biāo)函數(shù)為

(1)

式中：U(r)為數(shù)據(jù)調(diào)度路徑最大承載量；e為網(wǎng)絡(luò)中的某個信道；E為常數(shù)；αe為寬帶空閑系數(shù)，αe越大表示網(wǎng)絡(luò)信道e上擁塞程度越嚴(yán)重.至此，對網(wǎng)絡(luò)擁塞控制的問題可以分解為這2個層次相關(guān)的子問題，其中MAC層的分配可以表示為

(2)

式中：c、γ、q為MAC層、應(yīng)用層及2層之間過渡時傳輸數(shù)據(jù)幀數(shù)；H為總傳輸數(shù)據(jù)幀數(shù).

應(yīng)用層上路由調(diào)度可以表示為

Subjectto(r，f)∈R

(3)

式中：fei為數(shù)據(jù)調(diào)度路徑數(shù)量；S為總路徑值；R為總傳輸數(shù)據(jù)隊列長度；r、f分別為MAC層、應(yīng)用層中傳輸數(shù)據(jù)隊列長度.這樣在擁塞過程中，數(shù)據(jù)調(diào)度的問題就自動轉(zhuǎn)換為2個子問題了.

2　信道最優(yōu)數(shù)據(jù)分配的求解過程

對擁塞狀態(tài)下數(shù)據(jù)調(diào)度過程進行最優(yōu)解計算，在任務(wù)完成分解的基礎(chǔ)上，可以對這2個相互獨立的子問題進行分別求解.

2.1信道數(shù)據(jù)分配過程的轉(zhuǎn)換

在信道數(shù)據(jù)調(diào)度的最優(yōu)解計算過程中，需要綜合考慮信道容量和噪聲因素的影響，故設(shè)計信道數(shù)據(jù)擁塞控制模型為

ce=blog(1+K)

(4)

式中：K和b為信道的容量參數(shù)和噪聲參數(shù)；ce為數(shù)據(jù)傳輸速率.不同信道e和e′的關(guān)聯(lián)度參數(shù)Iee′和分離度是可以通過計算得出的，例如，對于IEEE 802.11信道分離度和相關(guān)性如圖1所示，Ie1e1=1.0，Ie1e2=0.790 6，Ie1e3=0.526 7和Ie1e5=0.通過以上關(guān)系可以得出：信道擁塞條件下數(shù)據(jù)分配問題可以表示為

(5)

式中，Ke為信道e傳輸數(shù)據(jù)量.

圖1　802.11信道的分離度和相關(guān)性Fig.1　Resolution degree and dependency of 802.11 channel

2.2基于PSO算法的最優(yōu)解計算

結(jié)合粒子群(PSO)算法[8-10]可以對上文中轉(zhuǎn)換后的問題進行最優(yōu)解的計算.結(jié)合粒子群算法強大的尋優(yōu)能力，在信道數(shù)據(jù)最優(yōu)調(diào)度過程中，結(jié)合式(5)最優(yōu)解的計算過程如下：

1) 在信道數(shù)據(jù)分配過程中，初始化時用n代表信道中擁堵數(shù)據(jù)的級別，由m代表算法中的運算規(guī)模.

2) 在均衡化過程中，由pi(i=1，2，…，m)代表每個粒子位置，由pg代表全局最優(yōu)位置，通過式(6)計算出相應(yīng)的Z矩陣，即

(6)

式中，o為粒子的飛行速度.

3) 在信道數(shù)據(jù)的均衡化過程中，需要結(jié)合適當(dāng)?shù)募s束條件，更新每個粒子pi(i=1，2，…，m)的位置，保證粒子的最優(yōu)化.在一定的約束條件下，pi代表無限靠近全局最優(yōu)位置.

4) 在均衡化過程中，判斷是否達到最優(yōu)信道數(shù)據(jù)調(diào)度均衡條件可以通過設(shè)定迭代次數(shù)完成.假如設(shè)定一個最大迭代次數(shù)，只要誤差滿足條件，則搜索停止，輸出最優(yōu)調(diào)度的結(jié)果；否則，繼續(xù)計算.

在信道數(shù)據(jù)調(diào)度的均衡化過程中，需要對調(diào)度的結(jié)果進行驗證，設(shè)定系數(shù)φe來測試信道調(diào)度結(jié)果的性能，信道e的驗證函數(shù)為

φe=∑Iee′/de′

(7)

式中，de′為與信道e′最近節(jié)點的距離.軟件算法的實現(xiàn)過程如下：

輸入：信道數(shù)據(jù)，信道種類，約束條件

輸出：最優(yōu)數(shù)據(jù)調(diào)度結(jié)果

PSO

{設(shè)定參數(shù)信息；

對種群進行最優(yōu)化設(shè)置；

設(shè)定式(5)的約束函數(shù)；

do

{粒子計算；

粒子和全局粒子最優(yōu)解比較；

更新位置；

進行調(diào)度；

判斷終止計算條件；

}

While(條件不滿足)

}

2.3路由數(shù)據(jù)調(diào)度問題的約束

由于路由數(shù)據(jù)的突變性，故對其約束過程較為復(fù)雜.可以將路由的數(shù)據(jù)任務(wù)調(diào)度問題視為一個特定約束下的最優(yōu)解計算問題，通過設(shè)定基礎(chǔ)的約束問題模型，結(jié)合特定的尋優(yōu)算法來求解路由數(shù)據(jù)最合理的調(diào)度方案，約束的過程可表示為

(8)

2.4基于遺傳算法的調(diào)度最優(yōu)解計算

在上述約束條件的基礎(chǔ)上，利用遺傳算法對調(diào)度過程進行最優(yōu)解計算，其中變異時間參數(shù)為

pri(t)=p(t)hi(t)+npi(t)

(9)

式中，hi(t)、p(t)和npi(t)均為遺傳算法中最優(yōu)解計算過程中的均衡調(diào)節(jié)參數(shù).定義響應(yīng)函數(shù)為

(10)

k=Tfmaxfmin/B

(11)

式中：T為遺傳算法下?lián)砣W(wǎng)絡(luò)數(shù)值調(diào)度的總時間；fmax、fmin分別為遺傳算法下?lián)砣W(wǎng)絡(luò)數(shù)值調(diào)度的極限頻率；B為遺傳算法下進行數(shù)據(jù)調(diào)度產(chǎn)生的最小總費用.

調(diào)度均衡性的目標(biāo)函數(shù)為

(12)

結(jié)合約束條件和目標(biāo)函數(shù)完成最優(yōu)解的計算，計算步驟如下：

輸入：信道數(shù)據(jù)，信道種類，約束條件

輸出：最優(yōu)數(shù)據(jù)調(diào)度結(jié)果

遺傳算法

{設(shè)定參數(shù)信息；

對遺傳算法進行最優(yōu)化設(shè)置；

設(shè)定式(8)的約束函數(shù)；

do

{變異時間參數(shù)計算；

最優(yōu)解比較；

目標(biāo)函數(shù)對比；

進行調(diào)度；

判斷終止計算條件；

}

While(條件不滿足)

}

3　實驗與分析

3.1收斂性分析

以NS2為基礎(chǔ)構(gòu)建10×10的二維網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)[11-13]，在此結(jié)構(gòu)內(nèi)隨機布置30個節(jié)點來進行本文算法下收斂性的分析.其中，設(shè)定30個節(jié)點的初始功率為200 mW，在此基礎(chǔ)上獲取吞吐量與迭代次數(shù)的變化關(guān)系如圖2～3所示.其中，圖2和圖3中所有的仿真實驗條件和配置都相同，不同的是圖2中每兩個節(jié)點之間的距離為40～50 m，圖3為25～30 m.

圖2　稀疏網(wǎng)絡(luò)下組播率的收斂性能Fig.2　Convergence performance of multicast rate under coefficient network

圖3　密集網(wǎng)絡(luò)下組播率的收斂性能Fig.3　Convergence performance of multicast rate under dense network

分析圖2、3可知，雖然仿真實驗條件和配置都相同，但是在節(jié)點間距離不同的情況下，算法的收斂速度也不同，因為節(jié)點之間的距離會對信號質(zhì)量和干擾水平產(chǎn)生強烈影響.節(jié)點之間的距離小，接收從鄰近節(jié)點發(fā)射的信號質(zhì)量低，干擾水平也低，但是并不會對吞吐量產(chǎn)生很大影響，收斂曲線的變化不顯著.研究表明，拓?fù)浣Y(jié)構(gòu)和干擾算法的收斂速度不會對系統(tǒng)產(chǎn)生強烈影響，合理選擇初始值，并及時更新變量的步長，可以保證算法的收斂性.

為了進一步驗證改進數(shù)值調(diào)度方法的性能，在調(diào)度數(shù)據(jù)量一定的情況下，采用改進的數(shù)值調(diào)度方法與文獻[6]、[7]所用方法進行對比驗證，比較結(jié)果如圖4所示.

圖4　不同算法的調(diào)度時間對比圖Fig.4　Contrast in scheduling time of different algorithms

從圖4可以看出，在調(diào)度數(shù)據(jù)量一定的情況下，采用改進方法進行數(shù)值調(diào)度，其調(diào)度時間約為4 s；采用文獻[7]方法進行數(shù)值調(diào)度，其調(diào)度時間約為6.4 s；采用文獻[6]調(diào)度時間約為7.2 s.改進算法相比文獻[6]、文獻[7]方法均有一定的優(yōu)越性.

3.2性能分析

首先構(gòu)建Mesh無線網(wǎng)絡(luò)，在面積為2 000 m×2 000 m的區(qū)域內(nèi)隨機分布30和55個節(jié)點，分別建立了稀疏和高密集二維網(wǎng)格進行本文算法性能分析.設(shè)定傳播范圍和干擾范圍為100 m，將實驗中所有節(jié)點都在IEEE 802.11協(xié)議下運行[14-15]，將最初的傳輸功率設(shè)定為200 mW.在稀疏和高密集二維網(wǎng)格中，隨機選取40%的節(jié)點作為接收節(jié)點，隨機分配5%的節(jié)點作為網(wǎng)關(guān)節(jié)點.以干擾模型為依據(jù)進行分析，若對象i或?qū)ο骿位于公共信道進行通信，并且在x或y的干擾區(qū)間內(nèi)，則通信鏈路(i，j)和(x，y)為相互干擾關(guān)系.

本文采用網(wǎng)絡(luò)干擾比值對算法的性能進行評估.網(wǎng)絡(luò)干擾比值是指網(wǎng)絡(luò)干擾總體信道數(shù)量與網(wǎng)絡(luò)干擾潛在信道數(shù)量的比值，也等于信道分配后多信道網(wǎng)絡(luò)干擾數(shù)量與單信道網(wǎng)絡(luò)干擾數(shù)量的比值.

仿真實驗中，將每個網(wǎng)絡(luò)節(jié)點都配備2～12個設(shè)備，其中，在24個信道的稀疏和高密度網(wǎng)絡(luò)環(huán)境下，網(wǎng)絡(luò)干擾比值比較結(jié)果如圖5所示.由圖5a可知，與其它傳統(tǒng)算法相比，本文算法下網(wǎng)絡(luò)干擾比值最小，在24個信道和4個設(shè)備的配置環(huán)境下，本文算法、文獻[6]、[7]計算的網(wǎng)絡(luò)干擾比值分別為0.269，1.767，1.228，本文算法平均網(wǎng)絡(luò)干擾值相對文獻[6]、[7]分別降低了84.8%和78.1%.由圖5b可知，與稀疏網(wǎng)絡(luò)相比，高密度網(wǎng)絡(luò)環(huán)境下的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的節(jié)點數(shù)和鏈路數(shù)量增多.通過分析可知，本文算法網(wǎng)絡(luò)下計算的網(wǎng)絡(luò)干擾比值最小，在4個設(shè)備的配置環(huán)境下，與文獻[6]、[7]計算的網(wǎng)絡(luò)干擾比值相比降低了87.1%和80.6%.

圖5　24信道下的網(wǎng)絡(luò)干擾比值Fig.5　Network interference value under channel

4　結(jié)　語

本文提出了一種基于多目標(biāo)拆分優(yōu)化思維的擁塞網(wǎng)絡(luò)數(shù)值調(diào)度方法.首先將擁塞網(wǎng)絡(luò)的數(shù)值調(diào)度問題進行模型化表示，然后將擁塞過程調(diào)度的最優(yōu)問題分解為多個目標(biāo)同時優(yōu)化問題：信道最優(yōu)任務(wù)分配問題和路由擁塞調(diào)度問題，根據(jù)粒子群算法對信道分配問題的最優(yōu)解進行計算，同時設(shè)計約束模型，利用遺傳算法求解路由擁塞調(diào)度問題.但是實驗中存在調(diào)度時間過長的情況，是下一步需要解決的問題.

[1]馮琳函，錢志鴻，金冬成.增強型的無線mesh網(wǎng)絡(luò)信道分配方法 [J].通信學(xué)報，2012，33(10)：44-50.

(FENG Lin-han，QIAN Zhi-hong，JIN Dong-cheng.Research on enhanced channel assignment scheme in wireless mesh network [J].Journal on Communications，2012，33(10)：44-50.)

[2]Zeng G，Wang B，Ding Y，et al.Efficient multicast algorithms for multichannel wireless mesh networks [J].Parallel and Distributed Systems，IEEE Transactions，2012，21(1)：86-99.

[3]蘇丹，李章勇，章敬雪，等.基于轉(zhuǎn)發(fā)節(jié)點的無線體域網(wǎng)動態(tài)信道研究 [J].重慶郵電大學(xué)學(xué)報(自然科學(xué)版)，2015，27(2)：235-240.

(SU Dan，LI Zhang-yong，ZHANG Jing-xue，et al.Dynamic body communication channels base-relay nodes for wireless body area networks [J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)，2015，27(2)：235-240.)

[4]羅成，謝維信.傳感器網(wǎng)絡(luò)擁塞避免與控制的模糊AQM算法 [J].電子學(xué)報，2014，10(4)：679-684.

(LUO Cheng，XIE Wei-xin.Fuzzy AQM for congestion avoidance and control in sensor networks [J].Electronic Journals，2014，10(4)：679-684.)

[5]Cheng H，Xiong N，Vasilakos A V，et al.Nodes organization for channel assignment with topology pre-servation in multi-radio wireless mesh networks [J].Ad Hoc Networks，2012，10(5)：760-773.

[6]Peng Y，Yu Y，Guo L，et al.An efficient joint channel assignment and QoS routing protocol for IEEE 802.11 multi-radio multi-channel wireless mesh networks [J].Journal of Network and Computer Applications，2013，36(2)：843-857.

[7]Jahanshahi M，Dehghan M，Meybodi M R.On channel assignment and multicast routing in multi-channel multi-radio wireless mesh networks [J].International Journal of Ad Hoc & Ubiquitous Computing，2013，12(4)：225-244.

[8]肖春靜，劉明，龔海剛，等.無線 Mesh 網(wǎng)絡(luò)低干擾組播 [J].軟件學(xué)報，2013，24(6)：1295-1309.

(XIAO Chun-jing，LIU Ming，GONG Hai-gang，et al.Low-interference multicast in wireless Mesh networks [J].Journal of Software，2013，24(6)：1295-1309.)

[9]吳志強，吳艷潔.基于OpenFlow的網(wǎng)絡(luò)擁塞控制機制研究 [J].河南理工大學(xué)學(xué)報(自然科學(xué)版)，2015，34(4)：547-549.

(WU Zhi-qiang，WU Yan-jie.Study on network congestion control mechanism based on OpenFlow [J]Journal of Henan Polytechnic University(Natural Science)，2015，34(4)：547-549.)

[10]Condat L.A primal-dual splitting method for convex optimization involving lipschitzian，proximable and linear composite terms [J].Journal of Optimization Theory & Applications，2013，158(2)：460-479.

[11]孔金生，任平英.TCP網(wǎng)絡(luò)擁塞控制研究 [J].計算機技術(shù)與發(fā)展，2014，24(1)：43-46.

(KONG Jin-sheng，REN Ping-ying.Summary of TCP network congestion control research [J]Computer Technology and Development，2014，24(1)：43-46.)

[12]Karimi O B，Liu J，Li Z.Multicast with cooperative gateways in multi-channel wireless mesh networks [J].Ad Hoc Networks，2014，12(1)：170-180.

[13]Sarafrazi S，Nezamabadi P H，Saryazdi S.Disruption：a new operator in gravitational search algorithm [J].Scientia Iranica，2011，18(3)：539-548.

[14]鄺祝芳，陳志剛.認(rèn)知無線Mesh網(wǎng)絡(luò)中一種有效的多目標(biāo)優(yōu)化頻譜分配算法 [J].中南大學(xué)學(xué)報(自然科學(xué)版)，2013，44(6)：124-129.

(KUANG Zhu-fang，CHEN Zhi-gang.A effective multi-objective optimization spectrum allocation algorithm in cognitive wireless Mesh networks [J].Journal of Central South University (Science and Techno-logy)，2013，44(6)：124-129.)

[15]宮華，張彪，許可.并行機生產(chǎn)與成批配送協(xié)調(diào)調(diào)度問題的近似策略 [J].沈陽工業(yè)大學(xué)學(xué)報，2015，37(3)：324-328.

(GONG Hua，ZHANG Biao，XU Ke.Approximation strategy for coordinated scheduling problem in production and batch delivery of parallel machines [J].Journal of Shenyang University of Technology，2015，37(3)：324-328.)

(責(zé)任編輯：景勇英文審校：尹淑英)

Numerical scheduling method for network congestion based on multi-objective resolution optimization

CHEN Hong-jun1, 2, FAN Tai-hua1, MU Jiong3

(1. School of Computer Science and Technology, Southwest University of Science and Technology, Mianyang 621010, China; 2. Department of Information Engineering, Sichuan Water Conservancy Vocational College, Chengdu 611231, China; 3. College of Information Engineering, Sichuan Agricultural University, Ya’an 625014, China)

In order to solve the blindness problem existing in the numerical scheduling of network congestion, a numerical scheduling method for network congestion based on multi-objective resolution optimization was proposed. The modeling expression for the numerical scheduling problem of network congestion was carried out. In addition, the optimal problem of congestion process scheduling was decomposed into the multi-objective optimization problem at the same time, namely the optimal task allocation problem of channel and routing congestion scheduling problem. According to the particle swarm optimization (PSO) algorithm, the calculation for the optimal solution of channel allocation problem was performed. Meanwhile, the constraint model was designed, and the congestion scheduling problem was solved with the genetic algorithm (GA). Moreover, the numerical scheduling of network at the congestion state was realized. The results show that the congestion scheduling scheme in the proposed algorithm has good enforceability.

network congestion; target resolution; particle swarm optimization; genetic algorithm (GA); numerical scheduling; channel allocation; network throughput

2016-01-27.

四川省教育廳資助項目(14ZB0113，12ZB326).

陳鴻俊(1981-)，男，四川成都人，講師，主要從事計算機軟件設(shè)計和數(shù)據(jù)處理等方面的研究.

10.7688/j.issn.1000-1646.2016.04.14

TP 393

A

1000-1646(2016)04-0440-05

*本文已于2016-05-12 14∶02在中國知網(wǎng)優(yōu)先數(shù)字出版. 網(wǎng)絡(luò)出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20160512.1402.042.html