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

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

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

遺傳算法（Genetic Algorithm）是一類借鑒生物界的進化規(guī)律演化而來的隨機化搜索方法。它采用概率化的尋優(yōu)方法，能自動獲取和優(yōu)化搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。目前，遺傳算法已被成功應(yīng)用到規(guī)劃、控制、設(shè)計等領(lǐng)域用來求解實際問題，并且展現(xiàn)出廣泛的應(yīng)用前景[4-6]。在XMPP網(wǎng)絡(luò)中，路徑選擇具有很強的隨機性和復(fù)雜性。高負(fù)載條件下，如果網(wǎng)絡(luò)能夠自動優(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é)點和目標(biāo)節(jié)點間傳送，求數(shù)據(jù)包從起始節(jié)點到目標(biāo)節(jié)點的最優(yōu)路徑。其中最優(yōu)路徑需滿足以下條件：

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

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

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

實際應(yīng)用中的XMPP系統(tǒng)規(guī)模比較復(fù)雜[7]，我們在求解優(yōu)化路徑時需先對其進行簡化。

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

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

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

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

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

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

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

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

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

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

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

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

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

如上圖所示，從終端節(jié)點1到終端節(jié)點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é)點的個數(shù)分別為：4、4、4 和 6。 因此，第三條路徑為優(yōu)先選擇路徑。

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

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

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

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

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

2.1 染色體編碼

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

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

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

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

1→3→7→12→13→16

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

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

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

2.2 種群產(chǎn)生

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

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

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

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

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

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

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

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

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

2.4 選擇操作

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

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

其中P=F/ΣF。選擇染色體過程中產(chǎn)生的隨機數(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è)進行交叉的父代個體P1、P2分別為：

P1：3→7→ |8→ 13

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

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

P1’： 3→ 7→ |5→ 13

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

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

2.6 變異操作

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

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

10

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

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

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

3 試驗結(jié)果

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

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

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

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

[3]張衛(wèi)，張峻峰，羅長壽.XMPP應(yīng)用于物聯(lián)網(wǎng)通訊協(xié)議的研究[J].中國農(nóng)學(xué)通報，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]張華，王進戈.機器人避開多隨機障礙物的路徑規(guī)劃遺傳算法[J].西華大學(xué)學(xué)報，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é)報，2008，34(Supp):32-35.

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