基于效用函數(shù)的C+W 網(wǎng)絡(luò)負(fù)載均衡研究

張 寶，向 陽，張 銳

（中國電信股份有限公司四川分公司無線網(wǎng)絡(luò)優(yōu)化中心，四川成都 610091）

0 引言

隨著無線寬帶業(yè)務(wù)的逐步成熟和應(yīng)用，用戶對網(wǎng)絡(luò)資源及服務(wù)質(zhì)量的需求日益增加，這就要求網(wǎng)絡(luò)運(yùn)營商必須有效地提高現(xiàn)有網(wǎng)絡(luò)資源的利用率，實(shí)現(xiàn)利益的最大化。負(fù)載均衡就是在這種背景下提出的一種能夠優(yōu)化網(wǎng)絡(luò)資源，實(shí)現(xiàn)CDMA與WIFI，WIFI與WIFI之間的自動(dòng)無縫切換，提高網(wǎng)絡(luò)性能的有效技術(shù)。在無線寬帶網(wǎng)絡(luò)中，C+W負(fù)載均衡技術(shù)的核心是使CDMA與WIFI共存的無線接入網(wǎng)絡(luò)成為一個(gè)具有網(wǎng)絡(luò)資源管理和網(wǎng)絡(luò)資源優(yōu)化的網(wǎng)絡(luò)。

針對負(fù)載均衡問題，文獻(xiàn)［1］提出了一種基于接入用戶數(shù)及無線網(wǎng)絡(luò)環(huán)境的門限切換方法。文獻(xiàn)［2］提出了基于博弈論的多主接入網(wǎng)絡(luò)負(fù)載均衡方法。

如何有效地分配有限的資源，從而最大限度地實(shí)現(xiàn)資源的潛在價(jià)值，這正是經(jīng)濟(jì)學(xué)研究得比較成熟的問題。本文針對CDMA 2000和WIFI混合組網(wǎng)下的負(fù)載均衡問題，將經(jīng)濟(jì)學(xué)中的博弈理論應(yīng)用到切換策略中，提出了一種基于博弈論的解決方案。

1 C+W網(wǎng)絡(luò)負(fù)載均衡和博弈論

1.1 C+W網(wǎng)絡(luò)負(fù)載均衡

C+W網(wǎng)絡(luò)是指一個(gè)移動(dòng)設(shè)備能夠同時(shí)連接到CDMA2000和WIFI 2個(gè)無線移動(dòng)網(wǎng)絡(luò)中進(jìn)行通信，如圖1所示。對于融合多個(gè)接入網(wǎng)絡(luò)的異構(gòu)系統(tǒng)，由于用戶對網(wǎng)絡(luò)的選擇會(huì)隨著時(shí)間地點(diǎn)的差異而不同，另外業(yè)務(wù)類型方面的考慮也會(huì)促使用戶自由選擇不同的網(wǎng)絡(luò)。這種選擇標(biāo)準(zhǔn)的多樣性通常使網(wǎng)絡(luò)選擇和帶寬分配有很大的隨機(jī)性。如何在多個(gè)網(wǎng)絡(luò)之間實(shí)現(xiàn)合理的資源分配，使之不至于使某一網(wǎng)絡(luò)超載，而另一網(wǎng)絡(luò)未能充分發(fā)揮處理能力的情況。負(fù)載均衡就是在這種背景下提出的一種策略或機(jī)制，它建立在網(wǎng)絡(luò)結(jié)構(gòu)之上，能以較低成本消除網(wǎng)絡(luò)瓶頸，有效解決網(wǎng)絡(luò)擁塞問題，提高網(wǎng)絡(luò)頻譜、信道資源的利用率，從而為用戶提供更好的服務(wù)。

圖1 C+W網(wǎng)絡(luò)覆蓋Fig.1 Network coverage of C+W

1.2 博弈論

博弈論（game theory）又稱對策論，是專門研究2個(gè)或2個(gè)以上利益有沖突的個(gè)體，在有相互作用的情況下，如何進(jìn)行各自優(yōu)化決策的理論。一般而言，經(jīng)典博弈論包括三要素:參與者（player）、策略（action）、收益（utility）。博弈論就是系統(tǒng)研究用合理方法定義的各種各樣的博弈問題，尋求各博弈方合理選擇策略的情況下博弈的解，也既是均衡。

2 基于博弈論的C+W網(wǎng)絡(luò)負(fù)載均衡

2.1 用博弈論分析C+W網(wǎng)絡(luò)負(fù)載均衡

用博弈理論研究C+W網(wǎng)絡(luò)負(fù)載均衡問題，即解決在CDMA2000和WIFI 2個(gè)無線移動(dòng)網(wǎng)絡(luò)共同存在的狀態(tài)下，如何通過制定合理的策略（博弈均衡解）使得系統(tǒng)總效用最大化的問題。

在C+W網(wǎng)絡(luò)中，不同的接入網(wǎng)絡(luò)構(gòu)成博弈中的“參與者”，不同的接入網(wǎng)絡(luò)選擇不同策略進(jìn)行網(wǎng)絡(luò)資源分配的過程就是“參與者”進(jìn)行博弈的過程。運(yùn)用博弈思想，不同網(wǎng)絡(luò)靈活調(diào)整網(wǎng)絡(luò)資源分配策略，在獲得最優(yōu)策略時(shí)，負(fù)載的均衡分布也使得系統(tǒng)中各網(wǎng)絡(luò)的資源得以均衡利用。微觀經(jīng)濟(jì)學(xué)理論證明:當(dāng)系統(tǒng)處于均衡狀態(tài)時(shí)，資源配置是最優(yōu)的，系統(tǒng)總效用最大。

2.2 博弈模型的建立與分析

設(shè)CDMA網(wǎng)絡(luò)以pc的單位網(wǎng)絡(luò)資源虛擬定價(jià)向用戶提供bc的帶寬，其支出的成本為Cc，同理WIFI網(wǎng)絡(luò)以pw的單位網(wǎng)絡(luò)資源虛擬定價(jià)向用戶提供bw的帶寬，其支出的成本為Cw，策略管理單元依據(jù)無線環(huán)境、業(yè)務(wù)類型、帶寬需求等條件來均衡各網(wǎng)絡(luò)之間的負(fù)載情況，由此，建立了如圖2所示的C+W網(wǎng)絡(luò)負(fù)載均衡模型。

圖2 C+W網(wǎng)絡(luò)中負(fù)載均衡模型Fig.2 System model for load balancing in C+W network

定義1 效用函數(shù)u是一個(gè)從策略集合S到實(shí)數(shù)集合R的一個(gè)映射，記為:u:S→R，如果對于所有x，y∈S，當(dāng)且僅當(dāng)u（x）≥u（y）時(shí)，策略x比策略 y的滿意度高［3］。

在博弈理論中，效用函數(shù)應(yīng)反映博弈者對選擇某一策略后所得到結(jié)果的滿意程度。在C+W網(wǎng)絡(luò)中，用戶的滿意程度應(yīng)根據(jù)數(shù)據(jù)業(yè)務(wù)的質(zhì)量來確定。因此，在無線網(wǎng)絡(luò)資源中，效用函數(shù)應(yīng)該用來評估用戶對網(wǎng)絡(luò)服務(wù)質(zhì)量的滿意度。

通常情況下，用戶對某一網(wǎng)絡(luò)的需求情況直接反映了用戶對該網(wǎng)絡(luò)的滿意程度（用戶對網(wǎng)絡(luò)的滿意度越高，其對該網(wǎng)絡(luò)的需求也就越大），而用戶對網(wǎng)絡(luò)帶寬的需求情況與所有網(wǎng)絡(luò)能夠提供的帶寬、單位帶寬的定價(jià)、以及傳輸信息的誤碼率、信噪比等有關(guān)系。另外，單位網(wǎng)絡(luò)資源虛擬定價(jià)與“市場上”網(wǎng)絡(luò)提供方的競爭程度有密切關(guān)系。網(wǎng)絡(luò)提供方相互之間競爭得越激烈，單位帶寬的定價(jià)就會(huì)被壓得越低，而作為用戶方是從中收益的。用戶總是希望耗費(fèi)最少的代價(jià)獲得最大的效用。綜合上述分析，用戶對帶寬需求的效用函數(shù)應(yīng)滿足以下幾點(diǎn)性質(zhì)。

1）當(dāng)網(wǎng)絡(luò)所提供的帶寬一定時(shí)，效用函數(shù)應(yīng)該是價(jià)格的單調(diào)減函數(shù);

2）當(dāng)價(jià)格一定時(shí)，效用函數(shù)應(yīng)該是網(wǎng)絡(luò)所提供的帶寬的凸函數(shù);

3）當(dāng)單位網(wǎng)絡(luò)資源虛擬定價(jià)趨于0時(shí)，效用函數(shù)應(yīng)趨于無窮大;

4）當(dāng)網(wǎng)絡(luò)所提供帶寬接近0時(shí)，效用函數(shù)亦應(yīng)趨于0;

5）應(yīng)能描述無線環(huán)境（傳輸信息的誤碼率、信噪比、時(shí)延等）下，系統(tǒng)的服務(wù)質(zhì)量。

如上所述，為量化用戶對帶寬的需求，需要建立滿足上述性質(zhì)的效用函數(shù)。本節(jié)以N.Singh和X.Vives的壟斷市場中價(jià)格與產(chǎn)量之間均衡的效用函數(shù)為基礎(chǔ)，并對其進(jìn)行改進(jìn)得到一個(gè)新的、適用于C+W網(wǎng)絡(luò)的負(fù)載均衡效用函數(shù)。在引入新的效用函數(shù)之前，有必要先給出N.Singh和X.Vives的效用函數(shù)為［4］

（1）式中:n=1，2;qi為壟斷市場中博弈者i的產(chǎn)量;pi為博弈者 i的定價(jià);αi，βi為常數(shù)，且 αi，βi＞0;γ反映博弈者生產(chǎn)的產(chǎn)品之間的可替代性（即博弈者i的產(chǎn)品質(zhì)量或其所提供的服務(wù)與其他博弈者之間的差異性），γ∈（0，1.0）。相對其他效用函數(shù)，該二次效用函數(shù)具有以下優(yōu)點(diǎn)，首先，它是凸函數(shù)，因此可以描述用戶的滿意飽和度。凸效用函數(shù)在量化帶寬分配的用戶滿意度上得到了廣泛的應(yīng)用。其次，對該函數(shù)求導(dǎo)以后得到的用戶需求函數(shù)是線性的，從而降低分析難度。

該效用函數(shù)映射到無線數(shù)據(jù)通信系統(tǒng)，網(wǎng)絡(luò)所提供的帶寬即為壟斷市場中博弈者的產(chǎn)量，帶寬的虛擬定價(jià)即為博弈者的定價(jià)。博弈者生產(chǎn)的產(chǎn)品之間的可替代性，即為各網(wǎng)絡(luò)提供方之間競爭的激烈程度，因?yàn)楫?dāng)某一產(chǎn)品能夠被同類產(chǎn)品自由替換，說明他們提供的服務(wù)和功能是完全相似的，也就意味著競爭就越激烈。另外，用戶對帶寬需求的效用函數(shù)還應(yīng)該包含反映信道傳輸質(zhì)量的誤碼率、信噪比、時(shí)延等重要指標(biāo)。這里，我們引入頻譜傳輸效率α。在無線通信系統(tǒng)中，信息的傳輸效率跟信道的傳輸質(zhì)量有直接關(guān)系，而信道傳輸信息的誤碼率和信噪比是信道傳輸質(zhì)量的重要指標(biāo)。為不失一般性，這里考慮采用自適應(yīng)多階正交幅度調(diào)制（multiple quadrature amplitudemodulation，MQAM），系統(tǒng)所采用的信道為高斯噪聲信道。該環(huán)境下信道的比特誤碼率（BER）約為

（2）式中:γ為接收者的信噪比（SNR）;α為頻譜效率［4］。為保證信息的傳輸質(zhì)量，通常情況下BER要控制在一定的范圍，信道的信噪比γ（SNR）是用戶已知的。因此，網(wǎng)絡(luò)i的頻譜傳輸效率為

經(jīng)過上述轉(zhuǎn)換，將N.Singh和X.Vives提出的效用函數(shù)改寫為（4）式，該效用函數(shù)既完全符合上述效用函數(shù)的性質(zhì)，又可以很好地表示用戶的滿意度。

（4）式中:αc，αw分別為CDMA網(wǎng)絡(luò)與WIFI網(wǎng)絡(luò)的頻譜傳輸效率;βc，βw分別為反映 CDMA網(wǎng)絡(luò)與WIFI網(wǎng)絡(luò)的時(shí)延參數(shù);參數(shù) λ是 CDMA網(wǎng)絡(luò)與WIFI網(wǎng)絡(luò)之間在不同業(yè)務(wù)類型下的可替換性，定義λ∈（－1.0，1.0）。

同理可得，WIFI網(wǎng)絡(luò)的帶寬需求Rw（p）。

在模型中，某一網(wǎng)絡(luò)i的收入Ei=pibi，成本Ci（b）=ciαibi。其中，ci為單位成本支出;αi為網(wǎng)絡(luò)i的頻譜傳輸效率;bi為用戶對網(wǎng)絡(luò)的需求Rc（p）。因此，網(wǎng)絡(luò)i的收益函數(shù)表示為

（6）式中，Ri（p）為網(wǎng)絡(luò)i的帶寬需求。

對于同時(shí)擁有CDMA網(wǎng)絡(luò)和WIFI網(wǎng)絡(luò)運(yùn)營商而言，追求的是2個(gè)網(wǎng)絡(luò)的收益和Ptot，其中Ptot為

（7）式中:Pc為CDMA網(wǎng)絡(luò)收益，Pw為WIFI網(wǎng)絡(luò)收益。

對博弈模型的求解過程就是求Nash均衡解的過程。Nash均衡策略［6］是指:無論其他參與者如何改變策略，該參與者的效益不可能再增加。本文通過對CDMA網(wǎng)絡(luò)的最佳響應(yīng)函數(shù)求解，可得Nash均衡解，即CDMA網(wǎng)絡(luò)在獲得最大收益時(shí)的單位網(wǎng)絡(luò)資源虛擬定價(jià)，同理可獲得WIFI網(wǎng)絡(luò)在獲得最大收益時(shí)的單位網(wǎng)絡(luò)資源虛擬定價(jià)。

由用戶獲得最佳滿意度時(shí)，帶寬需求與網(wǎng)絡(luò)資源虛擬定價(jià)之間的關(guān)系，可得最佳帶寬分配方案為

通過求解得

（10）式中:A=4βcβw－λ2;B=βw－λ2。同理可得。

由此可見，當(dāng)獲知網(wǎng)絡(luò)的比特誤碼率、信噪比、網(wǎng)絡(luò)時(shí)延、業(yè)務(wù)類型及成本后，即可得出網(wǎng)絡(luò)帶寬的最佳分配策略。

對于同時(shí)擁有CDMA網(wǎng)絡(luò)和WIFI網(wǎng)絡(luò)運(yùn)營商而言，追求的是2個(gè)網(wǎng)絡(luò)的利益和最大化。因此，可通過上述方法求得的解，即使網(wǎng)絡(luò)整體最優(yōu)的解，從而保證網(wǎng)絡(luò)整體利益最大化。

3 C+W網(wǎng)絡(luò)負(fù)載均衡實(shí)現(xiàn)流程

C+W網(wǎng)絡(luò)的負(fù)載均衡具體實(shí)現(xiàn)流程如圖3所示。首先由用戶提交接入申請，在接受到申請以后判斷無線環(huán)境中是否存在多個(gè)接入網(wǎng)絡(luò)，該判斷存在4種情況:1）僅有CDMA接入網(wǎng)絡(luò)，則進(jìn)行C網(wǎng)的單一網(wǎng)絡(luò)接入認(rèn)證并接入CDMA網(wǎng)絡(luò);2）僅有WIFI接入網(wǎng)絡(luò)，則進(jìn)行W網(wǎng)的接入認(rèn)證并接入WIFI網(wǎng)絡(luò);3）無可用接入網(wǎng)絡(luò)，給出提示信息;4）CDMA網(wǎng)絡(luò)與WIFI網(wǎng)絡(luò)均可接入，此時(shí)由無線上網(wǎng)終端獲取信噪比、誤碼率、業(yè)務(wù)類型等重要關(guān)鍵指標(biāo)，依據(jù)上述指標(biāo)采用博弈負(fù)載均衡算法制定出最優(yōu)帶寬資源分配方案，最終選擇最優(yōu)策略的接入網(wǎng)進(jìn)行認(rèn)證并接入。上述流程完成了單一用戶的接入，當(dāng)有后續(xù)用戶接入時(shí)，無線環(huán)境及帶寬可用資源已發(fā)生變化，系統(tǒng)將在不中斷已接入用戶服務(wù)的基礎(chǔ)上依據(jù)上述流程，選擇最大化當(dāng)前效用的最優(yōu)策略接入。依據(jù)上述流程，實(shí)現(xiàn)了C+W網(wǎng)絡(luò)的帶寬資源的高效利用，提升了用戶感知度，進(jìn)而實(shí)現(xiàn)了網(wǎng)絡(luò)運(yùn)營商的利益最大化。

圖3 C+W網(wǎng)絡(luò)負(fù)載均衡實(shí)現(xiàn)流程圖Fig.3 Flow chart of C+W network load balancing

4 仿真結(jié)果及分析

仿真中，參數(shù)設(shè)置如下:高斯信道中比特誤碼率BER在0.000 1～0.001之間，信噪比（SNR）γ在10～20 dB之間，網(wǎng)絡(luò)時(shí)延β在10～100 ms之間，CDMA網(wǎng)絡(luò)與WIFI網(wǎng)絡(luò)之間在不同業(yè)務(wù)類型下的可替換性λ∈（－1.0，1.0）。

圖4描述了頻譜的傳輸效率與誤碼率及信噪比之間的關(guān)系。誤碼率不變的情況下，當(dāng)信噪比提高時(shí)，信道的傳輸效率隨之增加，反之，當(dāng)信噪比一定的情況下，當(dāng)誤碼率減小時(shí)，信道的傳輸效率將有所下降，這是由于信息傳輸?shù)挠行院涂煽啃允敲芙y(tǒng)一的，因此通常需要根據(jù)實(shí)際業(yè)務(wù)需求有所側(cè)重。觀察到，當(dāng)誤碼率增大到一定范圍后，傳輸效率提高的速度有所下降，這說明當(dāng)信道誤碼率增大到一定程度后，對于提升信道傳輸效率的影響將隨之減弱，而隨著信噪比的增大，信息傳輸效率提升的速度也隨之加快，因此，可以在滿足一定可靠性指標(biāo)下，盡量通過增加信道的信噪比提高消息的傳輸速度。

圖5為運(yùn)營商總體網(wǎng)絡(luò)收益與帶寬分配策略關(guān)系圖，其中縱坐標(biāo)Total U為C+W網(wǎng)絡(luò)整體收益。從圖5中可以看出，在無線環(huán)境一定的情況下，特定的帶寬分配方案能夠給C+W網(wǎng)絡(luò)帶來最大收益，即我們追求的最佳策略。對于單獨(dú)的CDMA網(wǎng)絡(luò)或者WIFI網(wǎng)絡(luò)而言，單網(wǎng)最優(yōu)點(diǎn)保證了該網(wǎng)絡(luò)在此刻獲得最大的收益，但對于同時(shí)擁有CDMA網(wǎng)絡(luò)與WIFI網(wǎng)絡(luò)的運(yùn)營商而言，則不能滿足總體最優(yōu)。在整體最優(yōu)點(diǎn)則保證了網(wǎng)絡(luò)整體收益的最大值，這也是負(fù)載均衡的最佳帶寬分配方案點(diǎn)。對于單個(gè)網(wǎng)絡(luò)都是“理性”的，它會(huì)主動(dòng)追求自身最大收益而忽略整體收益，這種適合于非合作的競爭，作為同時(shí)擁有2個(gè)網(wǎng)絡(luò)的運(yùn)營商而言，可以通過建立一個(gè)“長效機(jī)制”共同合作來獲得C+W整體網(wǎng)絡(luò)的最大收益。

5 結(jié)論

負(fù)載均衡對于提高網(wǎng)絡(luò)性能，保證業(yè)務(wù)QoS，提升用戶感知度是非常重要的。本文利用博弈模型解決了C+W網(wǎng)絡(luò)的負(fù)載均衡問題，梳理了負(fù)載均衡實(shí)現(xiàn)的流程，實(shí)現(xiàn)了網(wǎng)絡(luò)資源的合理利用。仿真結(jié)果表明，在無線環(huán)境一定的情況下，某一特定的帶寬分配方案能夠給C+W網(wǎng)絡(luò)帶來最大收益。

［1］LIU J，JIN X，WANG Y.Agent-based load balancing on homogeneous minigrids:macroscopic modeling and characterization［J］.IEEE Transactions on Parallel and Distributed Systems，2005，16（7）:586-598.

［2］陳前斌，張寶，唐倫，等.基于 Stackelberg博弈論的Multi-Homing負(fù)載均衡研究［J］.計(jì)算機(jī)科學(xué)，2009，36（5）:76-78.

CHEN Qian-bin，ZHANG Bao，TANG Lun，et al.Research on load balancing Based on Stackelberg game theory for Multi-Homing in Heterogeneous Wireless Networks［J］.COMPUTER SCIENCE 2009，36（5）:76-78.

［3］ 約翰·納什.納什博弈論論文集［M］.張良橋，王曉剛，譯.北京:首都經(jīng)濟(jì)貿(mào)易大學(xué)出版社，2000.

NASH John Jr.ESSAYSON GAME THEORY by JOHN F NASH JR［M］.ZHANG Liang-qiao，WANG Xiaogang，translation.Beijing:Capital University of Economics＆ Business Press，2000.

［4］SINGH N，VIVES X.Price and quantity competition in a differentiated duopoly［J］.RAND JEconomics，1984，15（4）:546-554.

［5］ NIYATO D，HOSSAIN E.A Game-Theoretic Approach to Competitive Spectrum Sharing in Cognitive Radio Networks［C］//IEEE.IEEE Wireless Communications and Networking Conference.Hong Kong:IEEE Press，2007:11-15.

［6］NIYATO Dusit，HOSSAIN Ekram.Competitive pricing for spectrum sharing in cognitive radio networks:dynamic game，inefficiency of Nash equilibrium，and collusion［J］.IEEE Select Areas Common，2008，26（1）:192-202.