基于多目標拆分優化思維的擁塞網絡數值調度方法*

陳鴻俊， 范太華， 穆　炯

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

?

基于多目標拆分優化思維的擁塞網絡數值調度方法*

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

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

針對網絡擁塞數值調度中存在的盲目性問題，提出了一種基于多目標拆分優化的網絡擁塞數值調度方法.將擁塞網絡的數值調度問題進行模型化表示，并將擁塞過程調度的最優問題分解為多個目標同時優化問題：即信道最優任務分配問題和路由擁塞調度問題.根據粒子群算法，對信道分配問題的最優解進行計算，同時設計約束模型并利用遺傳算法求解擁塞調度問題，實現了在擁塞狀態下的網絡數值調度.結果表明，所提出算法獲得的擁塞調度方案具有較好的可執行性.

網絡擁塞； 目標拆分； 粒子群優化； 遺傳算法； 數值調度； 信道分配； 網絡吞吐

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

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

1　擁塞狀態下調度數據的多目標拆分

當網絡發生擁塞時，其擁塞區域和路由區域會發生較為明顯的變化，這種變化會直接反應到網絡的MAC層和應用層.2個層級直接的關聯性為0，故對擁塞資源進行調度的目標函數為

(1)

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

(2)

式中：c、γ、q為MAC層、應用層及2層之間過渡時傳輸數據幀數；H為總傳輸數據幀數.

應用層上路由調度可以表示為

Subjectto(r，f)∈R

(3)

式中：fei為數據調度路徑數量；S為總路徑值；R為總傳輸數據隊列長度；r、f分別為MAC層、應用層中傳輸數據隊列長度.這樣在擁塞過程中，數據調度的問題就自動轉換為2個子問題了.

2　信道最優數據分配的求解過程

對擁塞狀態下數據調度過程進行最優解計算，在任務完成分解的基礎上，可以對這2個相互獨立的子問題進行分別求解.

2.1信道數據分配過程的轉換

在信道數據調度的最優解計算過程中，需要綜合考慮信道容量和噪聲因素的影響，故設計信道數據擁塞控制模型為

ce=blog(1+K)

(4)

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

(5)

式中，Ke為信道e傳輸數據量.

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

2.2基于PSO算法的最優解計算

結合粒子群(PSO)算法[8-10]可以對上文中轉換后的問題進行最優解的計算.結合粒子群算法強大的尋優能力，在信道數據最優調度過程中，結合式(5)最優解的計算過程如下：

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

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

(6)

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

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

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

在信道數據調度的均衡化過程中，需要對調度的結果進行驗證，設定系數φe來測試信道調度結果的性能，信道e的驗證函數為

φe=∑Iee′/de′

(7)

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

輸入：信道數據，信道種類，約束條件

輸出：最優數據調度結果

PSO

{設定參數信息；

對種群進行最優化設置；

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

do

{粒子計算；

粒子和全局粒子最優解比較；

更新位置；

進行調度；

判斷終止計算條件；

}

While(條件不滿足)

}

2.3路由數據調度問題的約束

由于路由數據的突變性，故對其約束過程較為復雜.可以將路由的數據任務調度問題視為一個特定約束下的最優解計算問題，通過設定基礎的約束問題模型，結合特定的尋優算法來求解路由數據最合理的調度方案，約束的過程可表示為

(8)

2.4基于遺傳算法的調度最優解計算

在上述約束條件的基礎上，利用遺傳算法對調度過程進行最優解計算，其中變異時間參數為

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

(9)

式中，hi(t)、p(t)和npi(t)均為遺傳算法中最優解計算過程中的均衡調節參數.定義響應函數為

(10)

k=Tfmaxfmin/B

(11)

式中：T為遺傳算法下擁塞網絡數值調度的總時間；fmax、fmin分別為遺傳算法下擁塞網絡數值調度的極限頻率；B為遺傳算法下進行數據調度產生的最小總費用.

調度均衡性的目標函數為

(12)

結合約束條件和目標函數完成最優解的計算，計算步驟如下：

輸入：信道數據，信道種類，約束條件

輸出：最優數據調度結果

遺傳算法

{設定參數信息；

對遺傳算法進行最優化設置；

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

do

{變異時間參數計算；

最優解比較；

目標函數對比；

進行調度；

判斷終止計算條件；

}

While(條件不滿足)

}

3　實驗與分析

3.1收斂性分析

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

圖2　稀疏網絡下組播率的收斂性能Fig.2　Convergence performance of multicast rate under coefficient network

圖3　密集網絡下組播率的收斂性能Fig.3　Convergence performance of multicast rate under dense network

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

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

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

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

3.2性能分析

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

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

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

圖5　24信道下的網絡干擾比值Fig.5　Network interference value under channel

4　結　語

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

[1]馮琳函，錢志鴻，金冬成.增強型的無線mesh網絡信道分配方法 [J].通信學報，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]蘇丹，李章勇，章敬雪，等.基于轉發節點的無線體域網動態信道研究 [J].重慶郵電大學學報(自然科學版)，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]羅成，謝維信.傳感器網絡擁塞避免與控制的模糊AQM算法 [J].電子學報，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 網絡低干擾組播 [J].軟件學報，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的網絡擁塞控制機制研究 [J].河南理工大學學報(自然科學版)，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網絡擁塞控制研究 [J].計算機技術與發展，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]鄺祝芳，陳志剛.認知無線Mesh網絡中一種有效的多目標優化頻譜分配算法 [J].中南大學學報(自然科學版)，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]宮華，張彪，許可.并行機生產與成批配送協調調度問題的近似策略 [J].沈陽工業大學學報，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.)

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

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-)，男，四川成都人，講師，主要從事計算機軟件設計和數據處理等方面的研究.

10.7688/j.issn.1000-1646.2016.04.14

TP 393

A

1000-1646(2016)04-0440-05

*本文已于2016-05-12 14∶02在中國知網優先數字出版. 網絡出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20160512.1402.042.html