面向雷達(dá)組網(wǎng)的一種改進(jìn)多鏈路負(fù)載均衡算法

于 洋 饒 兵 陳 亮 宋建輝

(沈陽(yáng)理工大學(xué)信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110159)

0 引言

作為現(xiàn)代通信傳感器的雷達(dá)，其所需傳播的信息量很大，單一鏈路很難滿足大流量傳輸。因此，雷達(dá)數(shù)據(jù)傳輸過(guò)程中的多鏈路應(yīng)用已越來(lái)越受到人們的重視。研究表明，多鏈路聚合使得系統(tǒng)網(wǎng)絡(luò)傳輸率得到了較大的提高，很好地滿足了視頻傳輸?shù)男枰猍1]。在雷達(dá)組網(wǎng)中，各種干擾因素導(dǎo)致雷達(dá)網(wǎng)絡(luò)中各鏈路的網(wǎng)絡(luò)狀況差異很大，尤其是在混合網(wǎng)絡(luò)中[2]，無(wú)線網(wǎng)絡(luò)在受到干擾的情況下，性能相比其他鏈路有明顯下降。傳統(tǒng)鏈路聚合算法的不足在于沒有考慮鏈路間的差異情況，所以當(dāng)網(wǎng)絡(luò)中的某一鏈路性能明顯下降時(shí)，可能會(huì)影響整個(gè)網(wǎng)絡(luò)的傳輸性能。

本文將改進(jìn)的多鏈路負(fù)載均衡算法(covariance targetiteration algorithm based on public bidding algorithm，CIAP)[3]應(yīng)用于雷達(dá)組網(wǎng)中。該算法依賴網(wǎng)絡(luò)中所有鏈路的時(shí)延和剩余帶寬，對(duì)混合網(wǎng)絡(luò)中各鏈路時(shí)延和剩余帶寬進(jìn)行均衡，使得鏈路與無(wú)線鏈路達(dá)到最好的均衡效果，從而提高網(wǎng)絡(luò)的整體傳輸性能。

1 基于雷達(dá)組網(wǎng)的CIAP算法

1.1 被覆線與無(wú)線AP的拓?fù)浣Y(jié)構(gòu)

隨著無(wú)線通信技術(shù)的廣泛應(yīng)用，雷達(dá)組網(wǎng)通信采用無(wú)線與有線相結(jié)合的方式。本文中的無(wú)線傳輸方式采用無(wú)線訪問(wèn)節(jié)點(diǎn)(access point，AP);有線則采用被覆線，典型的無(wú)線AP與被覆線相結(jié)合的雷達(dá)組網(wǎng)數(shù)據(jù)傳輸網(wǎng)絡(luò)系統(tǒng)模型如圖1所示，它由任務(wù)隊(duì)列、調(diào)度器、可用帶寬監(jiān)測(cè)器和路由器組成。

圖1 雷達(dá)組網(wǎng)系統(tǒng)模型Fig.1 The system model of radar networking

面對(duì)復(fù)雜的任務(wù)隊(duì)列，如何使無(wú)線AP和被覆線在負(fù)載分配方面達(dá)到盡可能的均衡，將直接影響整個(gè)雷達(dá)網(wǎng)的數(shù)據(jù)傳輸效率。

1.2 多鏈路負(fù)載算法

網(wǎng)絡(luò)鏈路時(shí)延和剩余帶寬將直接影響網(wǎng)絡(luò)中數(shù)據(jù)的傳輸速率。本文應(yīng)用多鏈路負(fù)載算法對(duì)被覆線和無(wú)線AP的時(shí)延和剩余帶寬進(jìn)行均衡，以提高雷達(dá)網(wǎng)絡(luò)的通信效率。

協(xié)方差目標(biāo)優(yōu)化初始值定義為ε(ε＞0)，根據(jù)網(wǎng)絡(luò)鏈路上的連續(xù)通信圖譜以及網(wǎng)絡(luò)規(guī)模、用戶數(shù)量、負(fù)載平衡精度等因素確定ε。鏈路優(yōu)化的目標(biāo)就是使σk－ε＜0，從而達(dá)到多重鏈路時(shí)延和剩余帶寬的均衡，且?guī)捓寐首畲?。在?fù)載不平衡時(shí)，必有σk－ε≥0，此時(shí)，通過(guò)定義二次切割粒度經(jīng)驗(yàn)計(jì)算公式來(lái)優(yōu)化粒度選擇，提高負(fù)載平衡精度。

1.3 算法改進(jìn)

多鏈路負(fù)載均衡算法在優(yōu)化各鏈路負(fù)載時(shí)，把時(shí)延值最大和剩余帶寬最小的鏈路碎片空間分別再切割為m片，并應(yīng)用循環(huán)招標(biāo)算法(public bidding algorithm，PBA)將二次切割后的路由碎片映射到各個(gè)鏈路上。如果網(wǎng)絡(luò)中各鏈路的網(wǎng)絡(luò)狀態(tài)差異很大，優(yōu)化迭代次數(shù)就會(huì)增多，從而影響算法運(yùn)行效率。本文考慮到鏈路間的差異，在運(yùn)行迭代算法之前，先將鏈路間的時(shí)延和剩余帶寬差異控制在一定范圍內(nèi)。改進(jìn)CIAP算法的流程如圖2所示。

圖2 改進(jìn)CIAP算法流程圖Fig.2 The flowchart of improved CIAP algorithm

改進(jìn)CIAP算法描述如下：找出鏈路中剩余帶寬最大和剩余帶寬最小的鏈路，進(jìn)行差異互補(bǔ)調(diào)度，即均衡兩條鏈路的時(shí)延和剩余帶寬;重復(fù)該運(yùn)算，直到鏈路中剩余帶寬最大和剩余帶寬最小的差異控制在一定范圍為止;之后再進(jìn)行迭代運(yùn)算。

迭代的一次過(guò)程為：記錄路由表碎片映射到各個(gè)鏈路的時(shí)延和剩余帶寬值;當(dāng)鏈路間時(shí)延和剩余帶寬率不均衡即σk－ε≥0時(shí)，變尺度算法把時(shí)延值最大和剩余帶寬率最小的鏈路的路由碎片進(jìn)行二次切割，用循環(huán)招標(biāo)算法(PBA)[4－5]調(diào)度到各個(gè)鏈路上;若 k次迭代后時(shí)延和剩余帶寬率的協(xié)方差還未達(dá)到閾值，則繼續(xù)迭代。

2 仿真結(jié)果和性能分析

改進(jìn)CIAP算法的仿真參數(shù)如表1所示[6]。

表1 改進(jìn)CIAP算法仿真參數(shù)表Tab.1 Simulation parameters of improved CIAP algorithm

通過(guò)傳統(tǒng)鏈路聚合算法得到的各鏈路的時(shí)延情況和剩余帶寬情況如圖3所示。

圖3 傳統(tǒng)鏈路聚合算法下的鏈路情況Fig.3 The situation of the link with traditional link aggregation algorithm

經(jīng)改進(jìn)CIAP算法有限次迭代所得的各鏈路的時(shí)延情況和剩余帶寬情況如圖4所示。

圖4 改進(jìn)CIAP算法下的鏈路情況Fig.4 The situation of the link with improved CIAP algorithm

從圖4可以看出，經(jīng)改進(jìn)CIAP算法10次迭代后，混合鏈路的時(shí)延和剩余帶寬都能均衡到平均水平。

評(píng)價(jià)調(diào)度算法的性能主要表現(xiàn)在網(wǎng)絡(luò)的公平性和吞吐率方面。為此，引入公平性指數(shù)作為評(píng)價(jià)網(wǎng)絡(luò)公平性的指標(biāo)函數(shù)。公平性指數(shù)定義為：

F(t)=[∑Bi(t)]2/[n∑B2i(t)] (1)式中：Bi()t為鏈路i的帶寬;n為鏈路數(shù)。

公平性指數(shù)的取值范圍為[0，1]，該值達(dá)到1時(shí)最為公平[6]。

試驗(yàn)對(duì)比了傳統(tǒng)鏈路聚合算法和改進(jìn)CIAP算法在多鏈路傳輸下的公平性指數(shù)。結(jié)果表明，傳統(tǒng)鏈路聚合算法下網(wǎng)絡(luò)的公平性指數(shù)僅為0.089;而改進(jìn)CIAP算法下的網(wǎng)絡(luò)的公平性指數(shù)能達(dá)到0.5。

傳統(tǒng)鏈路聚合算法和改進(jìn)CIAP算法在多鏈路傳輸下的網(wǎng)絡(luò)吞吐率如圖5所示。

圖5 網(wǎng)絡(luò)吞吐率比較Fig.5 Comparison of network throughput

從圖5可以看出，傳統(tǒng)鏈路聚合算法下的網(wǎng)絡(luò)吞吐率大概為1 Mbit/s，而改進(jìn)CIAP算法的鏈路總的網(wǎng)絡(luò)吞吐率達(dá)到2 Mbit/s。

改進(jìn)CIAP算法和CIAP算法在不同剩余帶寬閾值下的迭代次數(shù)如表2所示。

表2 迭代次數(shù)對(duì)比結(jié)果Tab.2 The comparison of the numbers of iteration

從表2可以看出，改進(jìn)CIAP算法能降低算法的迭代次數(shù)，在改進(jìn)優(yōu)化效率方面有突出效果。隨著剩余帶寬閾值選取的降低，優(yōu)化效率將進(jìn)一步得到提高。

仿真結(jié)果表明，將改進(jìn)CIAP算法應(yīng)用在混合網(wǎng)絡(luò)多鏈路傳輸中，能很好地均衡各鏈路的時(shí)延和剩余帶寬，使各鏈路的時(shí)延和剩余帶寬都能維持到平均水平，并大幅度提高網(wǎng)絡(luò)的整體吞吐率。

3 結(jié)束語(yǔ)

針對(duì)雷達(dá)組網(wǎng)中鏈路間的性能差異影響網(wǎng)絡(luò)整體傳輸性能的問(wèn)題，本文將基于傳輸時(shí)延和剩余帶寬的多鏈路負(fù)載均衡算法應(yīng)用于雷達(dá)組網(wǎng)。該算法根據(jù)各鏈路的傳輸時(shí)延和剩余帶寬，采用誤差糾正學(xué)習(xí)方法實(shí)現(xiàn)整體網(wǎng)絡(luò)性能優(yōu)化，并均衡各個(gè)鏈路時(shí)延和剩余帶寬以及鏈路負(fù)載。

仿真結(jié)果表明，在實(shí)現(xiàn)多重鏈路流量負(fù)載均衡方面，多鏈路負(fù)載均衡算法比傳統(tǒng)鏈路聚合算法的效果更為顯著，在改善網(wǎng)絡(luò)吞吐率和公平性方面具有更好的性能。

[1]林科文，楊珉，毛迪林.基于多鏈路聚合的無(wú)線實(shí)時(shí)視頻傳輸系統(tǒng)[J].小型微型計(jì)算機(jī)系統(tǒng)，2011，32(5)：24 －30.

[2]李紅，沈未名.有線/無(wú)線混合網(wǎng)絡(luò)傳輸控制策略[J].計(jì)算機(jī)工程，2009，35(14)：111 －113.

[3]梁本來(lái)，秦勇，任新華，等.基于二元目標(biāo)優(yōu)化的多鏈路負(fù)載均衡算法 DBCTIA[J].計(jì)算機(jī)應(yīng)用，2009，29(3)：655 －657.

[4]Dinan E，Awduche D，Jabbari B.Analytical framework for dynamic traffic partitioning in MPLS network[C]//IEEE International Conference on Communications，New Orleans，Louisiana，IEEE，2000.

[5]Shaikh A，Rexford J，Shin K G.Evaluating the impact of stale link state on quality-of-service routing[J].IEEE/ACM Transactions on Networking，2001，9(2)：162 －176.

[6]曹野，方旭明.高吞吐率和高公平性混合傳感網(wǎng)絡(luò)[J].計(jì)算機(jī)應(yīng)用，2010，30(11)：3065 －3068.