遺傳算法在高負(fù)載XMPP中的路徑優(yōu)化應(yīng)用

陳雙喜 吳湘蓮 蔡向東 黨中華

(嘉興職業(yè)技術(shù)學(xué)院 信息技術(shù)分院，浙江 嘉興 314036）

XMPP(Extensible Messaging and Presence Protocol，可擴(kuò)展消息與存在協(xié)議)是目前主流的四種即時(shí)消息(IM：Instant Messaging)協(xié)議之一。它是一種基于XML的協(xié)議，繼承了XML靈活性和擴(kuò)展性。目前，XMPP采取Pastry算法進(jìn)行路徑優(yōu)化[1,2]。物聯(lián)網(wǎng)研究領(lǐng)域曾有提議，將XMPP作為物聯(lián)網(wǎng)通信標(biāo)準(zhǔn)[3]。但是礙于在高負(fù)載條件下 Pastry算法對(duì)消息傳輸沒有進(jìn)行延時(shí)控制，可能會(huì)導(dǎo)致垃圾信息充斥整個(gè)網(wǎng)絡(luò)，使得網(wǎng)絡(luò)性能下降。因此有必要對(duì)XMPP路徑優(yōu)化問題進(jìn)行探討。

遺傳算法（Genetic Algorithm）是一類借鑒生物界的進(jìn)化規(guī)律演化而來的隨機(jī)化搜索方法。它采用概率化的尋優(yōu)方法，能自動(dòng)獲取和優(yōu)化搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。目前，遺傳算法已被成功應(yīng)用到規(guī)劃、控制、設(shè)計(jì)等領(lǐng)域用來求解實(shí)際問題，并且展現(xiàn)出廣泛的應(yīng)用前景[4-6]。在XMPP網(wǎng)絡(luò)中，路徑選擇具有很強(qiáng)的隨機(jī)性和復(fù)雜性。高負(fù)載條件下，如果網(wǎng)絡(luò)能夠自動(dòng)優(yōu)化路徑，網(wǎng)絡(luò)的工作效率將得到提高。因此本文采用遺傳算法來嘗試解決XMPP在高負(fù)載條件下路徑優(yōu)化問題。

1 高負(fù)載路徑優(yōu)化問題

1.1 問題描述

高負(fù)載路徑優(yōu)化問題描述為：已知數(shù)據(jù)包在XMPP網(wǎng)絡(luò)中的起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)間傳送，求數(shù)據(jù)包從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑。其中最優(yōu)路徑需滿足以下條件：

（1）起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)不屬于同一條線路；

（2）從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑必須是連通的；

（3）從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑中不允許有回路。

實(shí)際應(yīng)用中的XMPP系統(tǒng)規(guī)模比較復(fù)雜[7]，我們?cè)谇蠼鈨?yōu)化路徑時(shí)需先對(duì)其進(jìn)行簡(jiǎn)化。

圖1 簡(jiǎn)化的XMPP系統(tǒng)結(jié)構(gòu)

在簡(jiǎn)化的XMPP系統(tǒng)結(jié)構(gòu)圖中，我們將XMPP網(wǎng)絡(luò)上的所有節(jié)點(diǎn)分為：服務(wù)器節(jié)點(diǎn)和終端節(jié)點(diǎn)。其定義如下：

定義1：完成XMPP數(shù)據(jù)轉(zhuǎn)送、備份、路徑選擇等處理操作的設(shè)備的稱為“服務(wù)器節(jié)點(diǎn)”。如圖1中的XMPP Server節(jié)點(diǎn)；

定義2：完成客戶端數(shù)據(jù)接收、發(fā)送、數(shù)據(jù)協(xié)議轉(zhuǎn)化等操作的節(jié)點(diǎn)稱為“終端節(jié)點(diǎn)”，如圖1中的End節(jié)點(diǎn)。

根據(jù)上述定義，路徑可以分為服務(wù)器節(jié)點(diǎn)到服務(wù)器節(jié)點(diǎn)、終端節(jié)點(diǎn)到服務(wù)器節(jié)點(diǎn)以及服務(wù)器節(jié)點(diǎn)到終端節(jié)點(diǎn)三類路徑。由于后兩類路徑不需要其它服務(wù)器節(jié)點(diǎn)進(jìn)行傳遞，其路徑的求解可以轉(zhuǎn)化為對(duì)第一類路徑的求解，因此在建立XMPP網(wǎng)絡(luò)路徑模型時(shí)只需考慮服務(wù)器節(jié)點(diǎn)與服務(wù)器節(jié)點(diǎn)間的最優(yōu)路徑。

1.2 簡(jiǎn)化的XMPP網(wǎng)絡(luò)模型

簡(jiǎn)化后的XMPP網(wǎng)絡(luò)模型用有權(quán)無向圖G=（V，E，C）來描述，其中：

（1）V是XMPP網(wǎng)絡(luò)中終端節(jié)點(diǎn)和服務(wù)器節(jié)點(diǎn)的集合。用一組從1開始的連續(xù)自然數(shù)逐條對(duì)XMPP網(wǎng)絡(luò)中的不同節(jié)點(diǎn)進(jìn)行編號(hào)，每個(gè)節(jié)點(diǎn)擁有唯一的編號(hào)。因此，V是由一組連續(xù)的自然數(shù)組成的集合；

（2）E 是圖中邊的集合，邊（i，j）表示節(jié)點(diǎn) i和 j之間存在線路；

（3）C=[Cij]是權(quán)值矩陣。 Cij表示邊（i，j）上的權(quán)值，即從節(jié)點(diǎn) i到節(jié)點(diǎn)j之間執(zhí)行效率。取值范圍為大于等于零。在實(shí)際的XMPP網(wǎng)絡(luò)模型中，邊上的權(quán)值取決于所有相鄰兩服務(wù)器節(jié)點(diǎn)的執(zhí)行效率。為零時(shí)表示斷路，權(quán)值越大，執(zhí)行效率越高；

（4）高效路徑的選擇依據(jù)C和E的值進(jìn)行判斷，權(quán)值越大，邊數(shù)越少，優(yōu)先選擇。

圖2是簡(jiǎn)化后的XMPP網(wǎng)絡(luò)模型圖：

圖2 簡(jiǎn)化XMPP網(wǎng)絡(luò)模型無向圖G

如上圖所示，從終端節(jié)點(diǎn)1到終端節(jié)點(diǎn)16，存在多條可選路徑。例如包括：（3，7，12，13）、（3，4，8，13）、（3，7，8，13）和（3，4，5，9，14，13）四條路徑，這四條路徑的權(quán)值和分別為：14(5+3+6)，16(2+4+10)，22(5+7+10)和 14(2+3+1+4+4)。 節(jié)點(diǎn)的個(gè)數(shù)分別為：4、4、4 和 6。 因此，第三條路徑為優(yōu)先選擇路徑。

2 優(yōu)化路徑的遺傳算法

基于遺傳算法的高負(fù)載XMPP優(yōu)化路徑主要求解流程如下：

（1）隨機(jī)產(chǎn)生初始種群，每個(gè)染色體采取實(shí)值編碼方式進(jìn)行編碼；（2）計(jì)算個(gè)體適應(yīng)度，判斷是否符合優(yōu)化標(biāo)準(zhǔn)；

（3）采用自適應(yīng)交叉，生產(chǎn)新的交叉染色體，選擇適應(yīng)度高的生成新個(gè)體；

（4）采用自適應(yīng)變異，產(chǎn)生新的變異染色體，選擇適應(yīng)度高的生成新個(gè)體。

2.1 染色體編碼

簡(jiǎn)化圖節(jié)點(diǎn)編號(hào)作為染色體的基因值。由圖2可以看出，簡(jiǎn)化圖并不是一個(gè)完全連通圖，圖中許多節(jié)點(diǎn)之間并不存在邊，如節(jié)點(diǎn)1和節(jié)點(diǎn)2。因此根據(jù)簡(jiǎn)化圖G,定義基因之間的約束關(guān)系如下：

（1）圖G中的邊的集合 E中任一邊（i，j），則定義基因 i與基因 j為一個(gè)基因?qū)?，?i，j>?；?qū)哂袑?duì)稱性，若存在基因?qū)?i，j>，則必存在基因?qū)?j，i>。

（2）圖G中頂點(diǎn)集合V的任一頂點(diǎn)i，能夠與其配對(duì)的所有基因的序列，稱為該節(jié)點(diǎn)的鄰接基因序列。如圖2中節(jié)點(diǎn)8存在<8，4>、<8，7>、<8，9> 和<8，13>四個(gè)基因?qū)Γ鋵?duì)應(yīng)的基因序列為{4，7，9，13}。

簡(jiǎn)化圖中節(jié)點(diǎn)的自然路徑作為染色體，并采用自然編碼的方式對(duì)染色體編碼。一條染色體是由某些基因組成的序列g(shù)eneSequence=（S1，S2，…，Sn），其中 Si∈V，（1≤i≤n），且滿足對(duì) j（1≤j≤n-1），均是一個(gè)基因?qū)?。如染色體：

1→3→7→12→13→16

該路徑中存在以下基因?qū)Γ?/p>

<1，3>，<3，7>，<7，12>，<12，13> 和 <13，16>。

由于路由路徑長度不一定完全相同，即不同染色體的長度并不完全相同，因此染色體長度為可變長度；另外，節(jié)點(diǎn)路徑中不存在回路，所以染色體長度不大于簡(jiǎn)化模型G中頂點(diǎn)的總數(shù)17。

2.2 種群產(chǎn)生

文中采用帶基因序列約束的方法來產(chǎn)生隨機(jī)的初始種群，圖2使用隨機(jī)選擇節(jié)點(diǎn)的方法產(chǎn)生初始種群時(shí)發(fā)現(xiàn)，其中絕大多數(shù)個(gè)體并不是一條可行路徑。其算法流程如下：

輸入源節(jié)點(diǎn)：S；目標(biāo)節(jié)點(diǎn)：O；節(jié)點(diǎn)數(shù)目：Num；總節(jié)點(diǎn)數(shù)：N，1≤S≤N，1≤O≤N

輸出染色體Gene=[Gene1,Gene2,… ,GeneNum]；

每個(gè)染色體Genei長度為Li,2≤Li≤N,1≤i≤Num

由基因?qū)Φ木哂袑?duì)稱性，上述算法通過數(shù)組機(jī)制解決路徑中的回路問題。

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

文中遺傳算法中的個(gè)體對(duì)應(yīng)于有權(quán)無向圖中求解的優(yōu)化路徑。節(jié)點(diǎn)總數(shù)越少、權(quán)值總和越大的優(yōu)化路徑認(rèn)為是較優(yōu)的個(gè)體，即權(quán)值節(jié)點(diǎn)比較大的路徑。因此，對(duì)于不同的個(gè)體設(shè)計(jì)如下適應(yīng)度函數(shù)：

F(i,j)=Cmax-Σe(i,j)/Σf(i,j)，

其中，Σf(i,j)表示路徑上的所經(jīng)過的節(jié)點(diǎn)數(shù)的總和，Σe(i,j)表示路徑上的所有權(quán)值的總和，Cmax=max(Σe(i,j)/Σf(i,j))+R，表示所有路徑中的最大權(quán)值節(jié)點(diǎn)比，其中隨機(jī)自然數(shù)R為修正因子。因此，路徑上經(jīng)過的節(jié)點(diǎn)數(shù)少，總權(quán)值越大，適應(yīng)函數(shù)的適應(yīng)值越大；反之，越小。

2.4 選擇操作

本文采用輪盤賭[8]選擇方法進(jìn)行個(gè)體選擇，個(gè)體適應(yīng)度越大，被選中的概率越大。即優(yōu)化路徑中經(jīng)過的節(jié)點(diǎn)少并且權(quán)值大。表1是采用輪盤賭選擇方法，修正因子R取值為10，得到的節(jié)點(diǎn)1到節(jié)點(diǎn)16的路徑，具體如表1所示：

表1 節(jié)點(diǎn)1到節(jié)點(diǎn)16輪盤賭選擇路徑

其中P=F/ΣF。選擇染色體過程中產(chǎn)生的隨機(jī)數(shù)P∈[0,1]，按如下方法確定染色體：

當(dāng) P∈[0,0.26]，則選擇染色體 3→7→12→13；

當(dāng) P∈[0.26,0.51]，則選擇染色體 3→4→8→13；

當(dāng) P∈[0.51,0.72]，則選擇染色體 3→7→8→13；

當(dāng) P∈[0.72,1.00]，則選擇染色體 3→4→5→9→14→13

2.5 交叉操作

本文采用帶基因序列限制的交叉算子，具體描述如下：

假設(shè)進(jìn)行交叉的父代個(gè)體P1、P2分別為：

P1：3→7→ |8→ 13

P2：3→4→ |5→ 9→14→ 13

首先隨機(jī)產(chǎn)生交叉位置 Location（1≤Location≤min（L1,L2）），其中L1和L2分別為P1和P2的染色體長度。假設(shè)Location=2，對(duì)染色體P1進(jìn)行交叉操作時(shí)先判斷處于交叉位置Location后的染色體 P2中的基因是否存在于處于交叉位置Location的基因序列中，如果存在，則進(jìn)行交叉；否則，依次向后尋找P2中的基因。同理，對(duì)染色體P2進(jìn)行同樣的交叉操作。若P1與P2均不能進(jìn)行交叉操作，則重新選擇一對(duì)染色體進(jìn)行交叉。P1和P2交叉后的結(jié)果為：

P1’： 3→ 7→ |5→ 13

P2’： 3→ 4→ |8→ 9→ 14→ 13

交叉后的染色體中可能存在斷路，如染色體P1’。因此交叉后，需對(duì)染色體進(jìn)行去環(huán)處理。

2.6 變異操作

本文采用對(duì)路徑中的子路徑進(jìn)行變異的方法。首先，隨機(jī)確定產(chǎn)生變異的起點(diǎn) S和終點(diǎn)T，然后通過調(diào)用產(chǎn)生初始種群算法，產(chǎn)生一條從S→T的路徑，再用該路徑替代原先路徑中S→T的路徑，作為變異后的新個(gè)體。

假設(shè)染色體為：3→ 4→ 8→ 9→ 14→ 13，不妨設(shè)變異起點(diǎn)為8，變異終點(diǎn)為9，通過調(diào)用產(chǎn)生初始種群算法產(chǎn)生一條8→9的路徑：

10

則變異后的結(jié)果為：

3→ 4→ 8→ 9→ 10→ 14→ 13

注意到產(chǎn)生變異后的新的染色體中可能存在環(huán)。因此，與交叉操作相同，變異后需對(duì)染色體進(jìn)行去環(huán)處理。

3 試驗(yàn)結(jié)果

假定初始種群大小為10，交叉概率為 PC=0.8，變異概率 Pm=0.01，進(jìn)化代數(shù)為10，節(jié)點(diǎn)1到節(jié)點(diǎn)16的前4條路徑，其中最優(yōu)路徑為3→7→8→13

表2 節(jié)點(diǎn)1到節(jié)點(diǎn)16的路徑列表

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

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

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

[4]Liu Junli,Chen Shuangxi,Mao Jie.Genetic algorithm study on the university course timetabling problem[C]//2012 IEEE International Conference on Cyber Technology in Automation,Control,andIntelligent Systems(CYBER).Bangkok,Thailand,2012:179-182.

[5]張華，王進(jìn)戈.機(jī)器人避開多隨機(jī)障礙物的路徑規(guī)劃遺傳算法[J].西華大學(xué)學(xué)報(bào)，2007，26(1)：56-58.

[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]龔正虎，黃劍，侯婕.基于XMPP的多跳TCP連接通信方案研究[J].北京工業(yè)大學(xué)學(xué)報(bào)，2008，34(Supp):32-35.

[8]梁宇宏，張欣.對(duì)遺傳算法的輪盤賭選擇方式的改進(jìn)[J].信息技術(shù)，2009，12(12):127-129.