陳雙喜 沈權(quán)權(quán) 吳春民

(1.嘉興職業(yè)技術(shù)學(xué)院，浙江 嘉興 314036；2.浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州310000)

0 引言

XMPP(Extensible Messaging and Presence Protocol，可擴(kuò)展消息與存在協(xié)議)是一種基于XML的即時(shí)消息協(xié)議[1]。它繼承了XML靈活性和擴(kuò)展性，已經(jīng)應(yīng)用到其它非IM領(lǐng)域[2]。有學(xué)者提議XMPP作為物聯(lián)網(wǎng)領(lǐng)域的標(biāo)準(zhǔn)協(xié)議[3]。也有學(xué)者將其應(yīng)用到分布式數(shù)據(jù)存儲(chǔ)領(lǐng)域，將提供相同數(shù)據(jù)的服務(wù)器放在網(wǎng)絡(luò)中的不同位置，以減少網(wǎng)絡(luò)資源的消耗、提供數(shù)據(jù)的安全性和多用戶的QoS(Quality of Service)[4]。但是，在相同服務(wù)器資源和網(wǎng)絡(luò)資源下，不同的訪問(wèn)路徑將導(dǎo)致不同的網(wǎng)絡(luò)狀態(tài)，會(huì)出現(xiàn)服務(wù)器負(fù)載和網(wǎng)絡(luò)資源負(fù)載不平衡等問(wèn)題。因此有必要對(duì)訪問(wèn)路徑優(yōu)化問(wèn)題進(jìn)行探討。本文將對(duì)問(wèn)題就行分析，建立數(shù)學(xué)模型，利用遺傳算法就行求解。通過(guò)模擬實(shí)驗(yàn)網(wǎng)絡(luò)，構(gòu)建XMPP路徑優(yōu)化服務(wù)器，實(shí)驗(yàn)驗(yàn)證得出在雙目標(biāo)雙約束條件下的不同解[5-6]。

1 問(wèn)題說(shuō)明

基于XMPP的分布式數(shù)據(jù)的訪問(wèn)QoS路徑優(yōu)化的目標(biāo)是優(yōu)化網(wǎng)絡(luò)中數(shù)據(jù)流的傳輸路徑，實(shí)現(xiàn)服務(wù)器負(fù)載平衡以及網(wǎng)絡(luò)資源消耗平衡。由于各個(gè)數(shù)據(jù)流占用的服務(wù)器資源和網(wǎng)絡(luò)資源不同，本研究的問(wèn)題就是將網(wǎng)絡(luò)中數(shù)據(jù)流分別重定向到不同服務(wù)器的路徑優(yōu)化問(wèn)題[7]。此外，為了滿足網(wǎng)絡(luò)數(shù)據(jù)流的路徑優(yōu)化，需建立XMPP路徑優(yōu)化服務(wù)器。它將定時(shí)收集網(wǎng)絡(luò)相關(guān)信息，進(jìn)行分析處理后得出在不同約束下的最優(yōu)路徑。如圖1所示，模擬了基于XMPP的分布式數(shù)據(jù)的訪問(wèn)網(wǎng)絡(luò)的拓?fù)鋱D。其中包括30條鏈路 (E0～E29)，30個(gè)用戶節(jié)點(diǎn)(C0～C29)，4 個(gè)服務(wù)器節(jié)點(diǎn)(S0～S3)。

圖1 基于XMPP的數(shù)據(jù)分布式存儲(chǔ)網(wǎng)絡(luò)拓?fù)鋱D

將訪問(wèn)數(shù)據(jù)的網(wǎng)絡(luò)看成一個(gè)有向連通圖 G(V,E)，其中，V為節(jié)點(diǎn)集；E為鏈路集。節(jié)點(diǎn)集V包括：

(1)服務(wù)器節(jié)點(diǎn)S；

(2)用戶訪問(wèn)節(jié)點(diǎn)C。

假設(shè)G(V,E)中C,S和E的數(shù)量分別為m,n,l，用戶與各個(gè)服務(wù)器之間的鏈路都采用TCP/IP協(xié)議獲得訪問(wèn)路徑[8]，則每個(gè)用戶有n種可選鏈路，整個(gè)網(wǎng)絡(luò)就存在nm種可選狀態(tài)。這里求解的問(wèn)題就是從這些可選狀態(tài)中選取一種，以使網(wǎng)絡(luò)在滿足約束條件的情況下整體性能最優(yōu)，下面給出了它的問(wèn)題模型。

優(yōu)化的目標(biāo)是鏈路集E服務(wù)器負(fù)載均衡、網(wǎng)絡(luò)資源負(fù)載均衡。XMPP路徑優(yōu)化服務(wù)器收集的信息存儲(chǔ)到以下矩陣中：

(1)CR=[cri]m：用戶占用服務(wù)器資源矩陣，cri表示用戶 i占用的服務(wù)器資源；

(2)CB=[cbi]m：用戶占用網(wǎng)絡(luò)資源矩陣，cbi表示用戶 i占用的網(wǎng)絡(luò)資源；

(3)SR=[srj]m：服務(wù)器資源矩陣，srj表示服務(wù)器 j所能提供的最大服務(wù)器資源；

(4)EB=[ebk]m：網(wǎng)絡(luò)資源矩陣，ebk表示鏈路 k所能提供的最大網(wǎng)絡(luò)資源；

(5)p=[pi,j]m×n： 鏈路分布矩陣，pi,j表示用戶 i到服務(wù)器 j是否鏈接，若鏈接pi,j=1，若未鏈接pi,j=0；

(6)x=[xi]m：決策變量，xi表示用戶 i選擇的服務(wù)器。

將路徑優(yōu)化問(wèn)題用上面的矩陣數(shù)學(xué)描述為如下雙目標(biāo)優(yōu)化問(wèn)題：

公式(2)中，f1(x)表示各服務(wù)器利用率的最大值；f2(x)表示各鏈路網(wǎng)絡(luò)資源利用率的最大值。

要實(shí)現(xiàn)數(shù)據(jù)訪問(wèn)的QoS，各用戶請(qǐng)求所消耗的網(wǎng)絡(luò)資源之和必須小于各條鏈路的網(wǎng)絡(luò)資源，所消耗的服務(wù)器資源之和必須小于各個(gè)服務(wù)器的資源，則約束條件表示為：

2 問(wèn)題求解

從上述數(shù)學(xué)模型可知，問(wèn)題為一個(gè)多目標(biāo)多約束優(yōu)化問(wèn)題，運(yùn)用遺傳算法求解該問(wèn)題的過(guò)程如下：

(1)編碼

染色體編碼采用x=x1x2x3…xm的形式，基因xi表示用戶 i所選擇的服務(wù)器，因此一條染色體表示一種網(wǎng)絡(luò)路徑狀態(tài)?；騲i的可選值為服務(wù)器的數(shù)量，取0到n-1范圍內(nèi)的任意整數(shù)。

(2)適應(yīng)度函數(shù)

利用權(quán)重系數(shù)法，得到適應(yīng)度的求解公式：

其中w1,w2分別表示兩個(gè)目標(biāo)函數(shù)的權(quán)重，每一組權(quán)重對(duì)應(yīng)一個(gè)解，調(diào)節(jié)權(quán)重值可以得到Pareto最優(yōu)解集[7]。實(shí)際應(yīng)用中需要根據(jù)網(wǎng)絡(luò)情況來(lái)選定一組權(quán)重值，從而獲得對(duì)應(yīng)的解作為路徑優(yōu)化的目標(biāo)。

(3)群體設(shè)定

為了使得群體能夠覆蓋基因的所有可能取值，種群的規(guī)模H與數(shù)據(jù)庫(kù)服務(wù)器的數(shù)量n有關(guān)：

其中，α為種群規(guī)模系數(shù)，α>1。

(4)選擇

采用最優(yōu)復(fù)制與比例選擇相結(jié)合的方法進(jìn)行選擇操作。在每一代進(jìn)化過(guò)程中，保留h個(gè)當(dāng)前最優(yōu)的個(gè)體不參與交叉、變異等遺傳操作，直接將它們復(fù)制到下一代群體中。

其余個(gè)體在下一代群體中生存的數(shù)目N計(jì)算如下：

其中，h為最優(yōu)個(gè)體保留數(shù)量；Fr為個(gè)體r的適應(yīng)度值。

(5)交叉

采用隨機(jī)取交叉點(diǎn)的方式，選取多個(gè)交叉點(diǎn)就行交叉操作。隨機(jī)交叉點(diǎn)的取值范圍為0到m-1。

(6)變異

采用隨機(jī)取數(shù)的方式獲取變異點(diǎn)，取值范圍為0到m-1；在變異點(diǎn)處采用隨機(jī)取值的方式完成基因的變異。變異的基因值取值范圍為0到n-1。變異的概率為MRandom。

(7)終止條件

在一定代數(shù)內(nèi)沒(méi)有更優(yōu)解出現(xiàn)時(shí)將自動(dòng)終止，公式(7)作為解的終止條件函數(shù)。

算法的C#總體實(shí)現(xiàn)過(guò)程如下：

3 實(shí)驗(yàn)?zāi)M及結(jié)果

從圖1的模擬環(huán)境可知m=30,n=4,l=30。服務(wù)器S0～S3的資源矩陣SR=(30,20,40,30)，其他參數(shù)如表 1、表 2所示。

表1 網(wǎng)絡(luò)鏈路提供的網(wǎng)絡(luò)資源

設(shè)置遺傳算法的參數(shù)為：種群規(guī)模系數(shù)α=3；最優(yōu)個(gè)體保留數(shù)量 h=1，交叉點(diǎn)數(shù)量CP=4；變異率 MRadom=0.03。 以模擬環(huán)境為基礎(chǔ)，用 C#編程，改變w1,w2的值，在迭代次數(shù)都小于60次的情況下收斂，表3為計(jì)算結(jié)果。

表3中列出5種權(quán)重條件下的各鏈路與服務(wù)器之間的關(guān)系。各服務(wù)器的利用率和各鏈路網(wǎng)絡(luò)資源的利用率，如圖2、圖3所示。

表2 用戶所需網(wǎng)絡(luò)資源和服務(wù)器資源

表3 在不同條件下的結(jié)果

圖3 網(wǎng)絡(luò)資源利用率

如圖2、圖3所示，當(dāng)w1=0時(shí)（N2），網(wǎng)絡(luò)資源利用率高，利用率都超過(guò)60%，部分達(dá)到堵塞現(xiàn)象；當(dāng)w2=0時(shí)（N1），服務(wù)器負(fù)載的變化很大，利用率超過(guò) 70%；當(dāng) w1=0.5，w2=0.5 時(shí)(N2)，數(shù)據(jù)庫(kù)服務(wù)器利用率集中在40%左右，網(wǎng)絡(luò)資源利用率在40%到60%左右；當(dāng)w1，w2權(quán)重分配就行隨機(jī)發(fā)配時(shí)(N4，N5)，數(shù)據(jù)庫(kù)服務(wù)器和網(wǎng)絡(luò)資源利用率處在30%到70%之間。

4 總結(jié)

為了提高XMPP網(wǎng)絡(luò)分布式數(shù)據(jù)庫(kù)數(shù)據(jù)訪問(wèn)效率必須進(jìn)行路徑優(yōu)化。本文從多目標(biāo)優(yōu)化角度運(yùn)用遺傳算法處理這個(gè)問(wèn)題，給出了滿足QoS多約束前提下的路徑優(yōu)化的算法模型與實(shí)現(xiàn)過(guò)程。實(shí)驗(yàn)結(jié)果表明本算法在不同權(quán)重系數(shù)下可以收斂于各個(gè)指標(biāo)的最優(yōu)值，實(shí)現(xiàn)路徑的多目標(biāo)組合優(yōu)化。有待研究的內(nèi)容：

(1)如何提高算法的執(zhí)行效率。初步想法通過(guò)改變編碼方式（如格雷碼），研究執(zhí)行效率；

(2)引入更多約束條件，使之更符合實(shí)踐需求；

(3)建立物理實(shí)驗(yàn)環(huán)境，就行實(shí)驗(yàn)研究。

［1］P.Saint-Andre，Ed.Extensible Messaging and Presence Protocol(XMPP)：Core.http://www.faqs.org/rfcs/rfc3920.txt[OL].

［2］黃劍.基于XMPP的端到端連接建立機(jī)制的研究與實(shí)現(xiàn)[D].國(guó)防科學(xué)技術(shù)大學(xué)，2009.

［3］張衛(wèi)，張峻峰，羅長(zhǎng)壽.XMPP應(yīng)用于物聯(lián)網(wǎng)通訊協(xié)議的研究[J].中國(guó)農(nóng)學(xué)通報(bào)，2012，28（09）：289-292.

［4］張麗，曲攀.自組織覆蓋網(wǎng)絡(luò)QoS組播動(dòng)態(tài)路徑優(yōu)化研究[J].計(jì)算機(jī)工程與應(yīng)用，2013，3（24）：83-87.

［5］Liu Junli，Chen Shuangxi,Mao Jie.Genetic algorithm study on the university course timetabling problem[R].2012 IEEE International Conference on Cyber Technology in Automation，Control， andIntelligent Systems(CYBER).Bangkok,Thailand.2012：179-182.

［6］Chang Wook Ahn,R.S.Ramakrishna.A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations[J].IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION Jun，2002：566-579.

［7］惠雯，尹浩，林闖，楊揚(yáng).內(nèi)容分發(fā)網(wǎng)絡(luò)請(qǐng)求路徑研究[J].計(jì)算機(jī)科學(xué)，2012，2（12）：1-7.

［8］陶英華，韓英偉，劉劍.TCP/IP協(xié)議解析（上）[J].中國(guó)有線電視，2005，16（24）：1574-1577.