視頻監(jiān)控系統(tǒng)中負(fù)載均衡算法的設(shè)計(jì)

,

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

隨著社會的進(jìn)步和人們安防意識的增強(qiáng)，網(wǎng)絡(luò)視頻監(jiān)控服務(wù)在各行各業(yè)中發(fā)揮著越來越重要的作用.由于視頻監(jiān)控系統(tǒng)規(guī)模的不斷擴(kuò)大，監(jiān)控點(diǎn)數(shù)量的快速增長和視頻質(zhì)量的逐步提高，傳統(tǒng)單一服務(wù)器的系統(tǒng)架構(gòu)已經(jīng)成為影響視頻監(jiān)控服務(wù)質(zhì)量的性能瓶頸[1].在這種情況下，不斷升級服務(wù)器配置并不是長久之計(jì).只有改變傳統(tǒng)架構(gòu)，將集群技術(shù)和負(fù)載均衡技術(shù)應(yīng)用到視頻監(jiān)控系統(tǒng)，才是解決瓶頸問題的有效措施.

集群和負(fù)載均衡技術(shù)可以有效避免單鏈路或單服務(wù)節(jié)點(diǎn)的工作瓶頸，合理使用硬件資源，使得整個(gè)系統(tǒng)的性能得到有效的提升[2].負(fù)載均衡算法作為負(fù)載均衡技術(shù)的核心，其性能的優(yōu)劣直接關(guān)系到負(fù)載能否均衡分發(fā)以及能否充分利用各個(gè)服務(wù)節(jié)點(diǎn)的處理資源[3].在分析常用負(fù)載均衡算法的基礎(chǔ)上，充分考慮視頻監(jiān)控系統(tǒng)自身的特點(diǎn)，將常用的動(dòng)態(tài)反饋負(fù)載均衡算法進(jìn)行改進(jìn)，使其可以更加合理的分配負(fù)載，提高視頻監(jiān)控系統(tǒng)的服務(wù)質(zhì)量.

1 負(fù)載均衡算法簡介

1.1 常用的負(fù)載均衡算法

按照分配策略，負(fù)載均衡算法主要分為兩大類：靜態(tài)均衡算法和動(dòng)態(tài)均衡算法[4].靜態(tài)算法不考慮節(jié)點(diǎn)實(shí)時(shí)變化的情況，而以固定的分配原則為依據(jù)，因此可能造成集群負(fù)載不均甚至單臺故障的情況.為了克服靜態(tài)算法的問題，動(dòng)態(tài)算法在系統(tǒng)運(yùn)行過程中實(shí)時(shí)考慮各個(gè)節(jié)點(diǎn)的負(fù)載情況，能夠?qū)⑷蝿?wù)進(jìn)行動(dòng)態(tài)分配.目前常用的負(fù)載均衡算法有以下幾種[5]：

1) 輪詢算法：將請求任務(wù)按順序依次分配給集群中的每臺服務(wù)器.它的優(yōu)點(diǎn)是簡單易實(shí)現(xiàn)，缺點(diǎn)是沒有考慮服務(wù)器節(jié)點(diǎn)之間處理能力的差異，無法充分利用節(jié)點(diǎn)資源.

2) 帶權(quán)重的輪詢算法：為每臺服務(wù)器增加一個(gè)權(quán)值來表示其處理能力，在分配任務(wù)的時(shí)候可根據(jù)權(quán)值的不同按比例分配相應(yīng)數(shù)目的任務(wù)，使得處理能力較強(qiáng)的服務(wù)器得以充分利用.但由于其沒有考慮服務(wù)器實(shí)時(shí)的負(fù)載變化，也可能導(dǎo)致集群負(fù)載分配的不均衡.

3) 最小連接數(shù)算法：在集群中維護(hù)一張表用以記錄當(dāng)前所有節(jié)點(diǎn)的連接數(shù)，當(dāng)新請求到來時(shí)將其分配給當(dāng)前連接數(shù)最少的節(jié)點(diǎn).它充分考慮當(dāng)前每臺服務(wù)器的連接情況，能把請求平滑分配到各個(gè)節(jié)點(diǎn).

4) 最快響應(yīng)速度算法：與最小連接數(shù)算法相似，但其記錄的是每個(gè)節(jié)點(diǎn)請求連接的響應(yīng)時(shí)間，并將新請求分配到響應(yīng)時(shí)間最短的服務(wù)器上，使請求能最快獲得處理.

5) 哈希表算法：利用特定的哈希函數(shù)將請求分配到某個(gè)服務(wù)節(jié)點(diǎn).哈希是一種靜態(tài)映射算法，哈希函數(shù)的選取關(guān)系到負(fù)載是否能夠均衡的分布.該算法的缺點(diǎn)是不利于集群系統(tǒng)的伸縮.

1.2 周期性動(dòng)態(tài)反饋負(fù)載均衡算法

基于周期性動(dòng)態(tài)反饋的負(fù)載均衡算法是目前中小型應(yīng)用系統(tǒng)中普遍常用的負(fù)載均衡策略[6].該算法的主要工作流程是，各節(jié)點(diǎn)服務(wù)器周期性向負(fù)載均衡器反饋其實(shí)時(shí)負(fù)載情況，負(fù)載均衡器依據(jù)實(shí)時(shí)負(fù)載將各節(jié)點(diǎn)進(jìn)行隊(duì)列劃分，一般分為輕載、適載、重載三種隊(duì)列，并在各隊(duì)列中將節(jié)點(diǎn)按權(quán)值進(jìn)行排序.當(dāng)新請求到來時(shí)，將其優(yōu)先分配到輕載隊(duì)列中權(quán)值較大的節(jié)點(diǎn)上進(jìn)行處理.同時(shí)，負(fù)載均衡器與節(jié)點(diǎn)之間周期性的交互可以檢測節(jié)點(diǎn)是否處于正常服務(wù)狀態(tài)，避免請求到單點(diǎn)失效的節(jié)點(diǎn).

周期性動(dòng)態(tài)反饋負(fù)載均衡算法汲取了常見算法的優(yōu)勢，但還是存在一些不足：

1) 在節(jié)點(diǎn)負(fù)載量收集的周期內(nèi)，如果出現(xiàn)短時(shí)大量突發(fā)請求，可能出現(xiàn)某輕載節(jié)點(diǎn)實(shí)際上已轉(zhuǎn)變?yōu)橹剌d節(jié)點(diǎn)，而隊(duì)列卻未重新劃分的情況.

2) 在輕載隊(duì)列中使用加權(quán)輪詢算法來分配任務(wù)，只考慮到節(jié)點(diǎn)服務(wù)器本身的性能，沒有根據(jù)節(jié)點(diǎn)實(shí)時(shí)負(fù)載情況進(jìn)行調(diào)整，可能出現(xiàn)負(fù)載分配不均的情況.

3) 將周期性動(dòng)態(tài)反饋算法應(yīng)用到視頻監(jiān)控系統(tǒng)時(shí)，還需要考慮視頻監(jiān)控系統(tǒng)本身的特點(diǎn)和工作流程，不能夠直接套用.

2 系統(tǒng)模型

視頻監(jiān)控系統(tǒng)集群架構(gòu)如圖1所示.系統(tǒng)包含客戶端、設(shè)備端、節(jié)點(diǎn)服務(wù)器集群和負(fù)載均衡器四個(gè)部分.系統(tǒng)工作時(shí)，負(fù)載均衡器接收客戶端的視頻請求，依據(jù)負(fù)載均衡算法將請求合理地分發(fā)到集群中的服務(wù)器節(jié)點(diǎn)，然后節(jié)點(diǎn)向設(shè)備請求視頻，并接收設(shè)備端上傳的實(shí)時(shí)視頻數(shù)據(jù)流，最后轉(zhuǎn)發(fā)給發(fā)起請求的客戶端.為簡化分析，系統(tǒng)模型中不考慮視頻存儲和轉(zhuǎn)碼問題.當(dāng)有多個(gè)客戶端并發(fā)請求同一臺設(shè)備的實(shí)時(shí)視頻時(shí)，節(jié)點(diǎn)服務(wù)器只與該設(shè)備建立單路連接來接收視頻流，進(jìn)行拷貝后再轉(zhuǎn)發(fā)給請求該設(shè)備的所有用戶[7].這樣能夠消除設(shè)備端處理性能受限和上傳帶寬不足的問題，提高系統(tǒng)整體的服務(wù)質(zhì)量和資源利用率.

圖1 視頻監(jiān)控系統(tǒng)集群架構(gòu)

也就是說，如果客戶端請求的設(shè)備已在上傳視頻流，那之后所有對該設(shè)備的請求需要分配給已接收該設(shè)備視頻流的節(jié)點(diǎn).因此，如果請求同一臺設(shè)備的用戶過多，將造成該服務(wù)節(jié)點(diǎn)負(fù)載過大，影響服務(wù)質(zhì)量.

3 改進(jìn)的動(dòng)態(tài)反饋負(fù)載均衡算法

3.1 改進(jìn)策略

針對上述提出的種種問題，將動(dòng)態(tài)反饋負(fù)載均衡算法進(jìn)行了改進(jìn)，下面將從任務(wù)分類策略、加權(quán)最少任務(wù)均衡策略、節(jié)點(diǎn)協(xié)同工作策略和節(jié)點(diǎn)主動(dòng)通知策略等四個(gè)方面對改進(jìn)的算法進(jìn)行詳細(xì)說明：

1) 任務(wù)分類策略：根據(jù)請求的設(shè)備是否已上傳視頻流，負(fù)載均衡器將接收到的任務(wù)請求進(jìn)行分類，并選取不同的均衡策略.如果設(shè)備未在上傳，則選用加權(quán)最少任務(wù)策略，優(yōu)先在輕載隊(duì)列中分配該任務(wù)；否則，選用節(jié)點(diǎn)協(xié)同工作策略進(jìn)行分配.

2) 加權(quán)最少任務(wù)均衡策略：負(fù)載均衡器在系統(tǒng)運(yùn)行時(shí)維護(hù)一張數(shù)據(jù)表，表中記錄當(dāng)前每個(gè)節(jié)點(diǎn)的任務(wù)處理數(shù).在分配任務(wù)時(shí)，應(yīng)盡可能選擇當(dāng)前任務(wù)數(shù)最少的服務(wù)器節(jié)點(diǎn).但考慮到每臺服務(wù)器的硬件配置不一致，還需要使用相應(yīng)的權(quán)值來表示其處理能力.假設(shè)集群節(jié)點(diǎn)數(shù)為n，當(dāng)且僅當(dāng)節(jié)點(diǎn)k滿足

T(k)/W(k)=min{T(i)/W(i)} (i=0,1,…,n-1)

(1)

時(shí)，節(jié)點(diǎn)k被調(diào)用.式(1)中：T為節(jié)點(diǎn)當(dāng)前任務(wù)數(shù)；W為節(jié)點(diǎn)權(quán)值.

3) 節(jié)點(diǎn)協(xié)同工作策略：如上所述，當(dāng)有多個(gè)用戶對同一設(shè)備視頻進(jìn)行請求時(shí)，所有任務(wù)需要分配到已經(jīng)在接收該設(shè)備視頻流的服務(wù)器節(jié)點(diǎn)以提高系統(tǒng)的資源利用率.不過隨著任務(wù)數(shù)的不斷增加，該節(jié)點(diǎn)也將可能面臨負(fù)載過重的問題.我們使用協(xié)同工作的方法來解決這個(gè)問題.

當(dāng)原節(jié)點(diǎn)已不是輕載節(jié)點(diǎn)，則從當(dāng)前輕載隊(duì)列中分配另一臺服務(wù)器進(jìn)行協(xié)同工作.節(jié)點(diǎn)之間以級聯(lián)的方式進(jìn)行協(xié)同，即原節(jié)點(diǎn)從設(shè)備獲取視頻流，拷貝并轉(zhuǎn)發(fā)給協(xié)作節(jié)點(diǎn)，協(xié)作節(jié)點(diǎn)接收后再轉(zhuǎn)發(fā)給客戶端.在原節(jié)點(diǎn)退回輕載隊(duì)列之前，請求都能由協(xié)作節(jié)點(diǎn)進(jìn)行處理.若任務(wù)的數(shù)量繼續(xù)增加，使得協(xié)同工作的輕載節(jié)點(diǎn)也面臨過載，則繼續(xù)從輕載隊(duì)列中分配節(jié)點(diǎn)，以多層級聯(lián)的方式進(jìn)行協(xié)同工作.

4) 節(jié)點(diǎn)主動(dòng)通知策略：在負(fù)載均衡器收集各節(jié)點(diǎn)實(shí)時(shí)負(fù)載量的周期內(nèi)，如果出現(xiàn)大量突發(fā)請求，特別是對同一設(shè)備視頻集中請求的情況，將可能使得原輕載節(jié)點(diǎn)迅速轉(zhuǎn)換為適載節(jié)點(diǎn)，甚至重載節(jié)點(diǎn).在這種情況下，為了避免過載，節(jié)點(diǎn)服務(wù)器主動(dòng)通知負(fù)載均衡器，告知其負(fù)載量的變化，以便其重新劃分隊(duì)列.

3.2 算法參數(shù)

3.2.1 節(jié)點(diǎn)服務(wù)器實(shí)時(shí)負(fù)載量

負(fù)載量是服務(wù)器實(shí)際負(fù)載情況的體現(xiàn).影響服務(wù)器實(shí)時(shí)性能的指標(biāo)有很多，一般選用CPU、內(nèi)存、帶寬和磁盤I/O占用4個(gè)指標(biāo).通過CPU使用率和CPU個(gè)數(shù)的乘積ICPU、內(nèi)存使用率IMEM、網(wǎng)絡(luò)帶寬使用率IBW、磁盤I/O占用率IDISK等參數(shù)來計(jì)算節(jié)點(diǎn)實(shí)時(shí)負(fù)載量為

L(i)=R1×ICPU+R2×IMEM+R3×IBW+R4×IDISK

(2)

式中Ri(i=1，2，3，4)為各參數(shù)的權(quán)值，∑Ri=1.參數(shù)對性能的影響越大，其權(quán)值也越大.考慮到視頻流數(shù)據(jù)傳輸過程對服務(wù)器CPU性能和網(wǎng)絡(luò)帶寬的要求較高，可設(shè)置權(quán)值為{0.4，0.1，0.4，0.1}，實(shí)際操作中可以對Ri不斷修正以達(dá)到最合適的比例.

3.2.2 節(jié)點(diǎn)服務(wù)器最大負(fù)載量

最大負(fù)載量用來描述服務(wù)器的處理能力，與節(jié)點(diǎn)本身的硬件配置相關(guān).一般通過處理器主頻和個(gè)數(shù)的乘積、內(nèi)存大小、最大帶寬和最大磁盤容量等4個(gè)指標(biāo)來評價(jià)最大負(fù)載量.

由于不同指標(biāo)具有不同的量綱和量綱單位，如果直接用原始數(shù)據(jù)進(jìn)行分析，將無法得到準(zhǔn)確的結(jié)果，因此需要先對原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理.最常用的標(biāo)準(zhǔn)化方法是Z-score方法，公式如下：

MAXI*=(MAXI-μ)/σ

(3)

式中：MAXI*為標(biāo)準(zhǔn)化后的參數(shù)數(shù)據(jù)；MAXI為原參數(shù)數(shù)據(jù)；μ為數(shù)據(jù)均值；σ為數(shù)據(jù)標(biāo)準(zhǔn)差.標(biāo)準(zhǔn)化處理之后，再計(jì)算最大負(fù)載量，公式如下：

(4)

式中：MAXL為節(jié)點(diǎn)最大負(fù)載量；MAXI*為參數(shù)的標(biāo)準(zhǔn)化數(shù)據(jù)；Ri(i=1，2，3，4)為各參數(shù)的權(quán)值，∑Ri=1.

3.2.3 節(jié)點(diǎn)服務(wù)器隊(duì)列劃分

根據(jù)實(shí)時(shí)負(fù)載量對節(jié)點(diǎn)進(jìn)行劃分，分為輕載、適載和重載三種隊(duì)列.如果節(jié)點(diǎn)負(fù)載量L<0.6，說明該服務(wù)器負(fù)載較輕，還有足夠的服務(wù)處理能力；當(dāng)0.60.9，說明服務(wù)器負(fù)載過重，無法再處理新的任務(wù).

3.2.4 節(jié)點(diǎn)服務(wù)器權(quán)值

根據(jù)節(jié)點(diǎn)最大負(fù)載量計(jì)算權(quán)值，公式如下：

W(i)=(MAXL*(i))/(∑MAXL*(i))

(5)

式中：W為節(jié)點(diǎn)權(quán)值；MAXL*為節(jié)點(diǎn)最大負(fù)載量.

3.3 算法描述

改進(jìn)的動(dòng)態(tài)反饋負(fù)載均衡算法流程如圖2所示，具體步驟描述如下：

1) 節(jié)點(diǎn)服務(wù)器檢測自身的硬件數(shù)據(jù)，發(fā)送至負(fù)載均衡器，負(fù)載均衡器計(jì)算出各節(jié)點(diǎn)權(quán)值.

2) 節(jié)點(diǎn)服務(wù)器周期性計(jì)算自身的實(shí)時(shí)負(fù)載量，發(fā)送到負(fù)載均衡器.負(fù)載均衡器根據(jù)實(shí)時(shí)負(fù)載量，將節(jié)點(diǎn)劃分到輕載、適載或重載三種隊(duì)列.

3) 在負(fù)載收集周期內(nèi)，節(jié)點(diǎn)服務(wù)器一旦發(fā)現(xiàn)自身負(fù)載過重，則主動(dòng)發(fā)送實(shí)時(shí)負(fù)載量給負(fù)載均衡器，然后負(fù)載均衡器重新為其劃分隊(duì)列.

4) 是否有視頻請求到來.是，轉(zhuǎn)到5)；否，繼續(xù)等待并周期性收集節(jié)點(diǎn)負(fù)載情況.

5) 判斷請求的設(shè)備是否已上傳視頻流數(shù)據(jù).否，則使用加權(quán)最少任務(wù)策略，優(yōu)先在輕載隊(duì)列中分配任務(wù)；是，則使用節(jié)點(diǎn)協(xié)同工作策略進(jìn)行分配，轉(zhuǎn)到6).

6) 判斷已接收該設(shè)備數(shù)據(jù)流的節(jié)點(diǎn)是否是輕載節(jié)點(diǎn).是，則調(diào)用該節(jié)點(diǎn)；否，則根據(jù)加權(quán)最少任務(wù)策略在輕載隊(duì)列中分配新節(jié)點(diǎn)與原節(jié)點(diǎn)進(jìn)行協(xié)同工作.

4 算法性能測試與分析

在局域網(wǎng)內(nèi)搭建視頻監(jiān)控系統(tǒng)測試平臺，包括3臺性能不一的節(jié)點(diǎn)服務(wù)器和1臺負(fù)載均衡器，服務(wù)器配置如表1所示.

圖2 改進(jìn)的動(dòng)態(tài)反饋負(fù)載均衡算法流程圖

表1 測試服務(wù)器配置

進(jìn)行測試時(shí)，先在平臺中模擬100臺監(jiān)控設(shè)備，再使用測試軟件LoadRunner在10 min之內(nèi)向設(shè)備隨機(jī)發(fā)送1 000個(gè)視頻監(jiān)控請求.且規(guī)定請求的100臺設(shè)備中有10臺是熱門設(shè)備，被請求的概率是其余設(shè)備的10倍.測試時(shí)，實(shí)時(shí)負(fù)載量參數(shù)權(quán)值設(shè)置為{0.4，0.1，0.4，0.1}.在測試過程中，觀察3臺節(jié)點(diǎn)服務(wù)器分別在原算法和改進(jìn)算法的情況下CPU占用率和帶寬使用率的變化.

圖3(a，c)顯示了使用原動(dòng)態(tài)反饋算法時(shí)各節(jié)點(diǎn)CPU占用率和帶寬的變化，圖3(b，d)顯示了使用改進(jìn)的動(dòng)態(tài)反饋算法時(shí)各節(jié)點(diǎn)CPU占用率和帶寬的變化.由圖3中曲線的變化情況可知：在模擬大量用戶請求的過程中，使用改進(jìn)前的算法，由于沒有引入節(jié)點(diǎn)協(xié)作等策略，各節(jié)點(diǎn)對資源的利用率較不平衡，性能高的節(jié)點(diǎn)比起性能低的分配到更多的負(fù)載.而使用改進(jìn)后的負(fù)載均衡算法，各節(jié)點(diǎn)資源利用率較為平衡，證明了改進(jìn)策略能夠有效改善負(fù)載的均衡分配.

圖3 測試中各節(jié)點(diǎn)資源利用率變化

5 結(jié) 論

改進(jìn)后的周期性動(dòng)態(tài)反饋負(fù)載均衡算法，既能保留原始算法的優(yōu)點(diǎn)，也能適應(yīng)視頻監(jiān)控系統(tǒng)的自身特點(diǎn)和工作流程.引入的任務(wù)分類策略、加權(quán)最少任務(wù)均衡策略、節(jié)點(diǎn)協(xié)同工作策略和節(jié)點(diǎn)主動(dòng)反饋策略等改進(jìn)方案，可以更好的將請求任務(wù)分配到最合適的服務(wù)器節(jié)點(diǎn).測試結(jié)果證明了該算法可以達(dá)到良好的負(fù)載均衡效果.

參考文獻(xiàn)：

[1] 胡麗聰，徐雅靜，徐惠民．基于動(dòng)態(tài)反饋的一致性哈希負(fù)載均衡算法[J]．微電子學(xué)與計(jì)算機(jī)，2012，29(1)：177-180．

[2] 郭波，汪大洋．流媒體負(fù)載均衡技術(shù)在江蘇電力視頻會議中的應(yīng)用[J]．電力信息與通信技術(shù)，2013，11(12)：111-115．

[3] 夏三波．SIP服務(wù)器集群系統(tǒng)的負(fù)載均衡技術(shù)研究[D]．武漢：華中科技大學(xué)，2012．

[4] 童瑞霞．基于動(dòng)態(tài)反饋機(jī)制的集群負(fù)載均衡算法研究[D]．武漢：武漢理工大學(xué)，2011．

[5] 李坤，王百杰．服務(wù)器集群負(fù)載均衡技術(shù)研究及算法比較[J]．計(jì)算機(jī)與現(xiàn)代化，2009，8：7-15．

[6] 劉恩海，李偉，張素琪，等．集群文件服務(wù)系統(tǒng)中的負(fù)載均衡算法的研究[J]．計(jì)算機(jī)工程與設(shè)計(jì)，2013，34(8)：2754-2758．

[7] 王文革，鄭三立，王文彬，等．流媒體技術(shù)在變電站遙視系統(tǒng)中的研究與實(shí)現(xiàn)[J]．中國電力，2010，43(7)：77-80．

[8] 楊建鋒，孟利民．視頻監(jiān)控系統(tǒng)中實(shí)時(shí)流媒體傳輸控制方法的設(shè)計(jì)[J]．浙江工業(yè)大學(xué)學(xué)報(bào)，2012，40(4)：454-457．

[9] 李曉波，孟利民．H.264多媒體數(shù)據(jù)在嵌入式系統(tǒng)中的存儲機(jī)制的設(shè)計(jì)[J]．浙江工業(yè)大學(xué)學(xué)報(bào)，2012，40(4)：437-440．

[10] 周曉，邊裕挺，李杰．基于android智能終端的wsn監(jiān)控系統(tǒng)[J]．浙江工業(yè)大學(xué)學(xué)報(bào)，2013，41(5)：558-561．

[11] DHAGE S N， MESHRAM B B． A survey on load balancing techniques in video on demand system[J]． Advances in Computational Research，2012，4(1)：61-65．

[12] DUSIT N， CHUTIMET S． Load balancing algorithms for internet video and audio server[C]//9th ieee international conference on networks． Bangkok： IEEE，2001：76-80．

[13] ZHANG Xing-ming， ZHAN Shao-xin． One load balancing solution for mobile video surveillance system[C]//International conference on computer science and service system． Nanjing： IEEE，2012：757-750．

[14] CHANDRA P K， SAHOO B． Performance analysis of load balancing algorithms for cluster of video on demand servers[C]//International Advance Conputing Conference． Patiala： IEEE， 2009：408-412．

[15] WU Chao， XIN Ming-jun． A cluster-based load-balancing mechanism for video surveillance system[C]//International Conference on Computer Application and System Modeling． Nanjing： IEEE，2010：40-43．