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

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

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

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

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

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

1 相關研究

1.1 Chord的拓撲匹配方法

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

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

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

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

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

2GA-Chord算法

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

2.1 GA-Chord算法描述

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

1）編碼設計

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

2）數據初始化

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

3）進行迭代

當迭代數等于max時，算法結束；否則一直循環執行以下行為：

Step1計算適應度

其計算方法為：

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

Step2執行選擇操作

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

Step3執行交叉操作

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

Step4執行變異操作

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

重復執行上述步驟2～4，直到產生新的種群達到種群規模為止。

4）迭代完成

用best所記錄的路徑順序構建Chord環，并實施基于前繼節點的跳數優化策略。

2.2 基于前繼節點的路數優化策略

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

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

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

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

2.3 GA-Chord算法實現

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

3 實驗仿真及性能分析

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

3.1 仿真模型設計

在OPNET仿真實驗中，Chord環的節點分為兩種，構造節點和普通節點。在路由模擬過程中，各個節點都會產生一個含有隨機資源號的數據包，按Chord路由規則繼續轉發，直到達到目的地為止，同時記錄相應數據。

3.2 性能分析

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

圖4 1024Chord環的平均跳數對比圖Fig.4 Average hop and probability distribute on 1024 Chord

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

4 結 論

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

[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：物理拓撲感知的結構化對等網 [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]王小平，曹立明.遺傳算法－理論、應用與軟件實現[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.