一種基于遺傳算法的拓撲匹配存儲方法

張澤月，羅俊波，楊 芳，孫 強，易顯富

（湖北醫(yī)藥學院 附屬十堰市太和醫(yī)院，湖北 十堰 442000）

傳統(tǒng)的互聯(lián)網(wǎng)在移動性支持方面存在先天性不足，其主要原因在于IP地址二義性問題。文獻[1-2]給出了已取得了階段性的成果，但需要完善的身份和位置標識映射方法。

在身份和位置標識分離網(wǎng)絡中，映射表項的數(shù)量非常大，需要研究映射的優(yōu)化存儲。分布式Hash表（DHT）常用來存儲大規(guī)模的數(shù)據(jù)。面Chord[3]是一種經(jīng)典的結(jié)構(gòu)化P2P網(wǎng)絡模型，其實現(xiàn)簡單，路由跳數(shù)比較高效，是備選方案之一。但是，Chord環(huán)方法其構(gòu)造的邏輯拓撲與物理網(wǎng)絡拓撲無關(guān)，導致實際的路由過程中存在“舍近求遠”的可能。由于查詢和定位在邏輯層與物理層上的性能差異，導致Chord資源定位的實際效率大大降低。

文中在對映射表項存儲方法進行研究的基礎上，提出了一種基于遺傳算法 （Genetic Algorithm，GA）[4]的 Chord方法（GA-Chord），用以存儲和查詢上述的身份和位置標識映射關(guān)系。其基本出發(fā)點是將在Chord環(huán)中查詢問題看成一個TSP問題，通過使用遺傳算法對該問題求解從而構(gòu)建Chord環(huán)，并對其路由跳數(shù)進行優(yōu)化。該模型實現(xiàn)簡單，路由表項的額外存儲開銷也很小，而且與同類Chord模型相比，GA-Chord在資源發(fā)現(xiàn)的平均路由跳數(shù)、延時方面都有很好的優(yōu)化。

1 相關(guān)研究

1.1 Chord的拓撲匹配方法

針對物理匹配問題的研究，主要形成了3種思路：1）基于拓撲的節(jié)點ID分配的優(yōu)化；2）基于鄰近路由的優(yōu)化；3）基于近鄰選擇的優(yōu)化。針對Chord模型，學者們也分別基于上述3種方法，對基本的Chord模型進行了改進。

文獻[4]提出了一種利用ASN（Autonomous System Number）解決 Chord拓撲失配問題的方法，部分解決了 Chord網(wǎng)絡的拓撲失配問題，但是這個方法的問題是如何獲得網(wǎng)絡節(jié)點的ASN。文獻[5]提出了通過在候選節(jié)點中選擇更近的節(jié)點來路由查詢請求，從而降低了查詢時延，但是其表項的發(fā)現(xiàn)過程中和路由表維護過程網(wǎng)絡帶來了較重的通信開銷。文獻[6]利用IPv6地址的層次結(jié)構(gòu)特性來產(chǎn)生節(jié)點ID，但是覆蓋網(wǎng)中兩個相近域內(nèi)的節(jié)點其距離可能很遠。文獻[7]提出了一種資源聚類的方法，就是提前對資源擁有節(jié)點進行分簇，地理位置接近的節(jié)點分為一簇，資源查詢時先判斷資源請求節(jié)點距離那個簇近。這種做法優(yōu)點是計算量較小，且可以將分簇操作放在節(jié)點加入時進行，選取節(jié)點時這需要比較一下資源請求節(jié)點屬于那個簇，從而降低了查詢時延，降低了節(jié)點的計算負擔。但是這種分簇的方法準確度不高，會丟失一些拓撲鄰近性，有時相鄰的節(jié)點分不到一個組中。

1.2 TSP問題及遺傳算法（Genetic Algorithm，GA）

TSP（Traveling Salesman Problem）問題，又被稱為中國郵遞員問題，是數(shù)學領域中的著名問題之一。TSP問題要求找到一條環(huán)路，走遍所有城市，但所有路徑最小。實際上，Chord環(huán)中的所有節(jié)點可以按ID形成一個閉合環(huán)的形式，另一方面是因為要解決的其實也是物理路徑問題。在1.1的現(xiàn)有算法分析中，其實質(zhì)都是最近鄰思想，即每次嘗試尋找的離自己最近的節(jié)點，缺乏對全局拓撲的考量，這種短視的方法很容易陷入一個較差的局部最優(yōu)解而不是全局最優(yōu)解。當對Chord環(huán)進行查詢時，實際上是對所有節(jié)點的一次遍歷。這和TSP問題很相似。因此，考慮從全局性的TSP問題入手，以期產(chǎn)生更好的效果。理論證明，最優(yōu)保留的遺傳算法可以找到TSP問題的全局最優(yōu)解，因此，選擇遺傳算法來解決Chord環(huán)的TSP問題。

遺傳算法的主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。它通過自然選擇中“優(yōu)勝劣汰”的策略在每次搜索中利用各種隨機的遺傳算子生成問題的一些新解，淘汰較差的解，保留較好的以及有希望的解，從而不斷對搜索空間中新的未知區(qū)域進行探索。它有效地利用了許多歷史信息，使得搜索每次都向著最好的方向前進。在實際的網(wǎng)絡中，同時由于網(wǎng)絡的通信效率以及計算成本等方面的限制，使得快速得到大規(guī)模節(jié)點的TSP最優(yōu)解變得很不現(xiàn)實。而遺傳算法作為啟發(fā)式算法，其本身追求的是在相對較低的計算成本下，找到好的或接近最優(yōu)解的解答，即滿意解。所以選擇遺傳算法的目的是希望通過其快速得出TSP的滿意解。

2GA-Chord算法

為了使GA－Chord能夠快速求解，筆者對所采用的遺傳算法進行了一定的簡化，并結(jié)合Chord特點做了相應調(diào)整。

2.1 GA-Chord算法描述

GA－Chord算法描述如下，設Chord環(huán)中存儲節(jié)點個數(shù)為n，種群規(guī)模為m。導入網(wǎng)絡節(jié)點拓撲，并通過節(jié)點廣播，得到各節(jié)點間的通信延遲（即節(jié)點間路徑長度），保存在距離矩陣dist[n][n]中，其中數(shù)組元素 dist[i][j]（i，j∈[0，n－1]）的值如式（1）所示，dist[i][j]表示從節(jié)點 i到 j的路徑距離。

1）編碼設計

采用整數(shù)編碼，首尾節(jié)點序號相同，且所有節(jié)點都要在編碼中。路徑表示（path representation）是表示旅程對應的基因編碼的最自然、最簡單的表示方法。 例如，旅程（5－1－7－8－9－4－6－2－10－3）可以直接表示為（5，1，7，8，9，4，6，2，10，3）?；诼窂奖硎镜木幋a方法，要求滿足TSP問題的任一城市有且僅有一次訪問的約束條件，即要求一個個體（即一條旅程）的染色體編碼中不容許有重復的基因碼。但是，在進行交叉、變異等操作之后所生成的個體一般不能滿足這個約束條件，需要對交叉、變異算子進行改進。

2）數(shù)據(jù)初始化

初始化種群及遺傳算法的各項參數(shù)，如迭代的最大值max，交叉概率、變異概率等。

3）進行迭代

當?shù)鷶?shù)等于max時，算法結(jié)束；否則一直循環(huán)執(zhí)行以下行為：

Step1計算適應度

其計算方法為：

其中fm，favg分別為當前代染色體的最小、平均路徑長度。

Step2執(zhí)行選擇操作

采用賭輪盤技術(shù)，選擇兩個基因進行后續(xù)操作。

Step3執(zhí)行交叉操作

文中使用部分匹配交叉 （PMX）[6]，該方法是 1985年，Goldberg針對TSP提出，它要求隨機選取兩個交叉點，以便確定一個匹配段，根據(jù)兩個父個體中兩個交叉點之間的中間段給出的映射關(guān)系生成兩個個體。

Step4執(zhí)行變異操作

在串中，隨機選擇兩點，再將這兩點內(nèi)的子串按反序插入到原位置中 。這種變異方法對于TSP問題，就調(diào)整前后引起的TSP圈的長度變化而言屬于最細微的調(diào)整，因而局部優(yōu)化的精度較高；但碼串絕對位置所呈現(xiàn)的“模式”變化較大，所需的計算也稍為復雜一點。

重復執(zhí)行上述步驟2～4，直到產(chǎn)生新的種群達到種群規(guī)模為止。

4）迭代完成

用best所記錄的路徑順序構(gòu)建Chord環(huán)，并實施基于前繼節(jié)點的跳數(shù)優(yōu)化策略。

2.2 基于前繼節(jié)點的路數(shù)優(yōu)化策略

單純物理拓撲上的匹配對Chord邏輯路由的跳數(shù)影響甚微，因此設計了一種稱為 “PO法”（Preceding Optimization，PO）的Chord路由跳數(shù)優(yōu)化方法，該法在前繼節(jié)點的路由表中加入本節(jié)點的存儲空間信息，用以增加Chord路由的靈活性，從而實現(xiàn)對跳數(shù)的優(yōu)化。本文稱此前繼節(jié)點捎帶記錄節(jié)點的存儲空間信息從而實現(xiàn)對跳數(shù)的優(yōu)化方法為PO法。

如圖1所示為一次簡單的Chord查詢過程，節(jié)點N0需要查找ID號為31的資源，需要經(jīng)過如圖1所示N0－N16－N24－N32的路由過程。分析圖1可以發(fā)現(xiàn)，如果知道后繼節(jié)點N32的存儲空間，那么N0就可以直接把資源31發(fā)送給N32。因此在PO法中，我們在生成Chord節(jié)點的路由表時，路由表添加每個后繼節(jié)點的同時記錄該后繼節(jié)點的存儲空間信息。如圖2所示，N0路由表中的“N32（8）”表示其后繼節(jié)點N32的存儲空間為8，那么資源號從25到32的資源都存儲在N32節(jié)點中。這樣前繼節(jié)點N0在查詢資源31的時候，就可以直接判斷出該資源是否屬于節(jié)點N32負責，從而優(yōu)化查詢過程。

圖1 一次Chord查詢過程Fig.1 Search in Chord

圖2 一次“PO法”查詢過程Fig.2 Search use PO once

2.3 GA-Chord算法實現(xiàn)

為了方便理解算法的具體實現(xiàn)，列出了算法流程偽代碼，詳細如下。

3 實驗仿真及性能分析

采用OPNET 8.1作為仿真平臺，生成了規(guī)模為1 024個節(jié)點的Chord環(huán)。同時選擇了Chord（記為Random-Chord）和劃分物理區(qū)域Chord（記為Zone-Chord）用來作為GA-Chord的實驗參照。仿真時間為3 h，數(shù)據(jù)包發(fā)送間隔為1 s，遺傳算法使用的種群規(guī)模為100。

3.1 仿真模型設計

在OPNET仿真實驗中，Chord環(huán)的節(jié)點分為兩種，構(gòu)造節(jié)點和普通節(jié)點。在路由模擬過程中，各個節(jié)點都會產(chǎn)生一個含有隨機資源號的數(shù)據(jù)包，按Chord路由規(guī)則繼續(xù)轉(zhuǎn)發(fā)，直到達到目的地為止，同時記錄相應數(shù)據(jù)。

3.2 性能分析

圖3 1024Chord環(huán)的平均延遲對比圖Fig.3 Average delay and probability distribute on 1024 Chord

圖4 1024Chord環(huán)的平均跳數(shù)對比圖Fig.4 Average hop and probability distribute on 1024 Chord

在延遲上，可以看出GA-Chord平均時延優(yōu)于劃分物理區(qū)域Chord和原始Chord，同時使用了PO法的原始Chord。因為跳數(shù)的降低，所以相應在延遲上也比原始Chord要短，但是這一延遲優(yōu)勢跟沒有使用PO法的GA-Chord相比還相差很遠。在跳數(shù)上，進行了“PO法”優(yōu)化的GA-Chord和原始Chord都體現(xiàn)出了較為明顯的優(yōu)勢。

4 結(jié) 論

本文通過引入全局性的TSP問題，并利用遺傳算法快速求得其近似最優(yōu)解，同時利用“PO法”，提出了一種的物理拓撲匹配的Chord構(gòu)建方法，該方法所需開銷小，仿真實驗證明了該模型的可行性。

[1]LUO Hong-bin，QIN Ya-juan.A DHT-based identifier-tolocator mapping approach for a scalable internet[J].IEEE Transactions on Parallel and Distributed Systems，2009，20（12）:1790-1802.

[2]Eriksson J.PeerNet:Pushing peer-to-peer down the stack[C]//Springer.Proc.of the Int’l Workshop on Peer-To-Peer Systems 2003，2003:268-277.

[3]肖卓程，荊金華.層次式Chord：物理拓撲感知的結(jié)構(gòu)化對等網(wǎng) [J].計算機科學，2006，33（7）:25－28.XIAO Zhuo-cheng，JING Jin-hua.Layered Chord:physical topology award structured P2P network [J].Computer Science，2006，33（7）：25-28.

[4]王小平，曹立明.遺傳算法－理論、應用與軟件實現(xiàn)[M].西安：西安交通大學出版社，2002.

[5]Stoica I，Morris R，Karger D，et al.A scalable peer-to-peer lookup service for internet applications[C]//ACM.Proceedings of SIGCOMM，New York， USA，2001:146-160.

[6]Xiong J，Zhang Y，Hong P，et al.IPv6 based topology-aware Chord [C]//IEEE Proceedings of the Joint International Conference on Autonomic and Autonomous Systems and International Conference on Networking and Services，2005:19-23.

[7]GUO Cheng-wei，YANG Shuai，YANG Huai-po.P4P Pastry：A novel P4P-based Pastry routing algorithm in peer to peer network[C]//2010 The 2nd IEEE International conference on ICIME，2010:209-213.