XMPP分布式數據的訪問路徑的遺傳算法研究

陳雙喜 沈權權 吳春民

(1.嘉興職業技術學院，浙江 嘉興 314036；2.浙江大學 計算機科學與技術學院，浙江 杭州310000)

0 引言

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

1 問題說明

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

圖1 基于XMPP的數據分布式存儲網絡拓撲圖

將訪問數據的網絡看成一個有向連通圖 G(V,E)，其中，V為節點集；E為鏈路集。節點集V包括：

(1)服務器節點S；

(2)用戶訪問節點C。

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

優化的目標是鏈路集E服務器負載均衡、網絡資源負載均衡。XMPP路徑優化服務器收集的信息存儲到以下矩陣中：

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

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

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

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

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

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

將路徑優化問題用上面的矩陣數學描述為如下雙目標優化問題：

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

要實現數據訪問的QoS，各用戶請求所消耗的網絡資源之和必須小于各條鏈路的網絡資源，所消耗的服務器資源之和必須小于各個服務器的資源，則約束條件表示為：

2 問題求解

從上述數學模型可知，問題為一個多目標多約束優化問題，運用遺傳算法求解該問題的過程如下：

(1)編碼

染色體編碼采用x=x1x2x3…xm的形式，基因xi表示用戶 i所選擇的服務器，因此一條染色體表示一種網絡路徑狀態。基因xi的可選值為服務器的數量，取0到n-1范圍內的任意整數。

(2)適應度函數

利用權重系數法，得到適應度的求解公式：

其中w1,w2分別表示兩個目標函數的權重，每一組權重對應一個解，調節權重值可以得到Pareto最優解集[7]。實際應用中需要根據網絡情況來選定一組權重值，從而獲得對應的解作為路徑優化的目標。

(3)群體設定

為了使得群體能夠覆蓋基因的所有可能取值，種群的規模H與數據庫服務器的數量n有關：

其中，α為種群規模系數，α>1。

(4)選擇

采用最優復制與比例選擇相結合的方法進行選擇操作。在每一代進化過程中，保留h個當前最優的個體不參與交叉、變異等遺傳操作，直接將它們復制到下一代群體中。

其余個體在下一代群體中生存的數目N計算如下：

其中，h為最優個體保留數量；Fr為個體r的適應度值。

(5)交叉

采用隨機取交叉點的方式，選取多個交叉點就行交叉操作。隨機交叉點的取值范圍為0到m-1。

(6)變異

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

(7)終止條件

在一定代數內沒有更優解出現時將自動終止，公式(7)作為解的終止條件函數。

算法的C#總體實現過程如下：

3 實驗模擬及結果

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

表1 網絡鏈路提供的網絡資源

設置遺傳算法的參數為：種群規模系數α=3；最優個體保留數量 h=1，交叉點數量CP=4；變異率 MRadom=0.03。 以模擬環境為基礎，用 C#編程，改變w1,w2的值，在迭代次數都小于60次的情況下收斂，表3為計算結果。

表3中列出5種權重條件下的各鏈路與服務器之間的關系。各服務器的利用率和各鏈路網絡資源的利用率，如圖2、圖3所示。

表2 用戶所需網絡資源和服務器資源

表3 在不同條件下的結果

圖3 網絡資源利用率

如圖2、圖3所示，當w1=0時（N2），網絡資源利用率高，利用率都超過60%，部分達到堵塞現象；當w2=0時（N1），服務器負載的變化很大，利用率超過 70%；當 w1=0.5，w2=0.5 時(N2)，數據庫服務器利用率集中在40%左右，網絡資源利用率在40%到60%左右；當w1，w2權重分配就行隨機發配時(N4，N5)，數據庫服務器和網絡資源利用率處在30%到70%之間。

4 總結

為了提高XMPP網絡分布式數據庫數據訪問效率必須進行路徑優化。本文從多目標優化角度運用遺傳算法處理這個問題，給出了滿足QoS多約束前提下的路徑優化的算法模型與實現過程。實驗結果表明本算法在不同權重系數下可以收斂于各個指標的最優值，實現路徑的多目標組合優化。有待研究的內容：

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

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

(3)建立物理實驗環境，就行實驗研究。

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

［2］黃劍.基于XMPP的端到端連接建立機制的研究與實現[D].國防科學技術大學，2009.

［3］張衛，張峻峰，羅長壽.XMPP應用于物聯網通訊協議的研究[J].中國農學通報，2012，28（09）：289-292.

［4］張麗，曲攀.自組織覆蓋網絡QoS組播動態路徑優化研究[J].計算機工程與應用，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］惠雯，尹浩，林闖，楊揚.內容分發網絡請求路徑研究[J].計算機科學，2012，2（12）：1-7.

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