一種基于遺傳算法的拓?fù)淦ヅ浯鎯Ψ椒?/h1>
2011-06-05 11:01:54張澤月羅俊波易顯富
電子設(shè)計工程 2011年21期
張澤月，羅俊波，楊 芳，孫 強(qiáng)，易顯富
（湖北醫(yī)藥學(xué)院 附屬十堰市太和醫(yī)院，湖北 十堰 442000）
傳統(tǒng)的互聯(lián)網(wǎng)在移動性支持方面存在先天性不足，其主要原因在于IP地址二義性問題。文獻(xiàn)[1-2]給出了已取得了階段性的成果，但需要完善的身份和位置標(biāo)識映射方法。
在身份和位置標(biāo)識分離網(wǎng)絡(luò)中，映射表項的數(shù)量非常大，需要研究映射的優(yōu)化存儲。分布式Hash表（DHT）常用來存儲大規(guī)模的數(shù)據(jù)。面Chord[3]是一種經(jīng)典的結(jié)構(gòu)化P2P網(wǎng)絡(luò)模型，其實現(xiàn)簡單，路由跳數(shù)比較高效，是備選方案之一。但是，Chord環(huán)方法其構(gòu)造的邏輯拓?fù)渑c物理網(wǎng)絡(luò)拓?fù)錈o關(guān)，導(dǎo)致實際的路由過程中存在“舍近求遠(yuǎn)”的可能。由于查詢和定位在邏輯層與物理層上的性能差異，導(dǎo)致Chord資源定位的實際效率大大降低。
文中在對映射表項存儲方法進(jìn)行研究的基礎(chǔ)上，提出了一種基于遺傳算法 （Genetic Algorithm，GA）[4]的 Chord方法（GA-Chord），用以存儲和查詢上述的身份和位置標(biāo)識映射關(guān)系。其基本出發(fā)點是將在Chord環(huán)中查詢問題看成一個TSP問題，通過使用遺傳算法對該問題求解從而構(gòu)建Chord環(huán)，并對其路由跳數(shù)進(jìn)行優(yōu)化。該模型實現(xiàn)簡單，路由表項的額外存儲開銷也很小，而且與同類Chord模型相比，GA-Chord在資源發(fā)現(xiàn)的平均路由跳數(shù)、延時方面都有很好的優(yōu)化。
1 相關(guān)研究
1.1 Chord的拓?fù)淦ヅ浞椒?/h3>
針對物理匹配問題的研究，主要形成了3種思路：1）基于拓?fù)涞墓?jié)點ID分配的優(yōu)化；2）基于鄰近路由的優(yōu)化；3）基于近鄰選擇的優(yōu)化。針對Chord模型，學(xué)者們也分別基于上述3種方法，對基本的Chord模型進(jìn)行了改進(jìn)。
文獻(xiàn)[4]提出了一種利用ASN（Autonomous System Number）解決 Chord拓?fù)涫鋯栴}的方法，部分解決了 Chord網(wǎng)絡(luò)的拓?fù)涫鋯栴}，但是這個方法的問題是如何獲得網(wǎng)絡(luò)節(jié)點的ASN。文獻(xiàn)[5]提出了通過在候選節(jié)點中選擇更近的節(jié)點來路由查詢請求，從而降低了查詢時延，但是其表項的發(fā)現(xiàn)過程中和路由表維護(hù)過程網(wǎng)絡(luò)帶來了較重的通信開銷。文獻(xiàn)[6]利用IPv6地址的層次結(jié)構(gòu)特性來產(chǎn)生節(jié)點ID，但是覆蓋網(wǎng)中兩個相近域內(nèi)的節(jié)點其距離可能很遠(yuǎn)。文獻(xiàn)[7]提出了一種資源聚類的方法，就是提前對資源擁有節(jié)點進(jìn)行分簇，地理位置接近的節(jié)點分為一簇，資源查詢時先判斷資源請求節(jié)點距離那個簇近。這種做法優(yōu)點是計算量較小，且可以將分簇操作放在節(jié)點加入時進(jìn)行，選取節(jié)點時這需要比較一下資源請求節(jié)點屬于那個簇，從而降低了查詢時延，降低了節(jié)點的計算負(fù)擔(dān)。但是這種分簇的方法準(zhǔn)確度不高，會丟失一些拓?fù)溧徑裕袝r相鄰的節(jié)點分不到一個組中。
1.2 TSP問題及遺傳算法（Genetic Algorithm，GA）
TSP（Traveling Salesman Problem）問題，又被稱為中國郵遞員問題，是數(shù)學(xué)領(lǐng)域中的著名問題之一。TSP問題要求找到一條環(huán)路，走遍所有城市，但所有路徑最小。實際上，Chord環(huán)中的所有節(jié)點可以按ID形成一個閉合環(huán)的形式，另一方面是因為要解決的其實也是物理路徑問題。在1.1的現(xiàn)有算法分析中，其實質(zhì)都是最近鄰思想，即每次嘗試尋找的離自己最近的節(jié)點，缺乏對全局拓?fù)涞目剂?，這種短視的方法很容易陷入一個較差的局部最優(yōu)解而不是全局最優(yōu)解。當(dāng)對Chord環(huán)進(jìn)行查詢時，實際上是對所有節(jié)點的一次遍歷。這和TSP問題很相似。因此，考慮從全局性的TSP問題入手，以期產(chǎn)生更好的效果。理論證明，最優(yōu)保留的遺傳算法可以找到TSP問題的全局最優(yōu)解，因此，選擇遺傳算法來解決Chord環(huán)的TSP問題。
遺傳算法的主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。它通過自然選擇中“優(yōu)勝劣汰”的策略在每次搜索中利用各種隨機(jī)的遺傳算子生成問題的一些新解，淘汰較差的解，保留較好的以及有希望的解，從而不斷對搜索空間中新的未知區(qū)域進(jìn)行探索。它有效地利用了許多歷史信息，使得搜索每次都向著最好的方向前進(jìn)。在實際的網(wǎng)絡(luò)中，同時由于網(wǎng)絡(luò)的通信效率以及計算成本等方面的限制，使得快速得到大規(guī)模節(jié)點的TSP最優(yōu)解變得很不現(xiàn)實。而遺傳算法作為啟發(fā)式算法，其本身追求的是在相對較低的計算成本下，找到好的或接近最優(yōu)解的解答，即滿意解。所以選擇遺傳算法的目的是希望通過其快速得出TSP的滿意解。
2GA-Chord算法
為了使GA－Chord能夠快速求解，筆者對所采用的遺傳算法進(jìn)行了一定的簡化，并結(jié)合Chord特點做了相應(yīng)調(diào)整。
2.1 GA-Chord算法描述
GA－Chord算法描述如下，設(shè)Chord環(huán)中存儲節(jié)點個數(shù)為n，種群規(guī)模為m。導(dǎo)入網(wǎng)絡(luò)節(jié)點拓?fù)?，并通過節(jié)點廣播，得到各節(jié)點間的通信延遲（即節(jié)點間路徑長度），保存在距離矩陣dist[n][n]中，其中數(shù)組元素 dist[i][j]（i，j∈[0，n－1]）的值如式（1）所示，dist[i][j]表示從節(jié)點 i到 j的路徑距離。
1）編碼設(shè)計
采用整數(shù)編碼，首尾節(jié)點序號相同，且所有節(jié)點都要在編碼中。路徑表示（path representation）是表示旅程對應(yīng)的基因編碼的最自然、最簡單的表示方法。 例如，旅程（5－1－7－8－9－4－6－2－10－3）可以直接表示為（5，1，7，8，9，4，6，2，10，3）?；诼窂奖硎镜木幋a方法，要求滿足TSP問題的任一城市有且僅有一次訪問的約束條件，即要求一個個體（即一條旅程）的染色體編碼中不容許有重復(fù)的基因碼。但是，在進(jìn)行交叉、變異等操作之后所生成的個體一般不能滿足這個約束條件，需要對交叉、變異算子進(jìn)行改進(jìn)。
2）數(shù)據(jù)初始化
初始化種群及遺傳算法的各項參數(shù)，如迭代的最大值max，交叉概率、變異概率等。
3）進(jìn)行迭代
當(dāng)?shù)鷶?shù)等于max時，算法結(jié)束；否則一直循環(huán)執(zhí)行以下行為：
Step1計算適應(yīng)度
其計算方法為：
其中fm，favg分別為當(dāng)前代染色體的最小、平均路徑長度。
Step2執(zhí)行選擇操作
采用賭輪盤技術(shù)，選擇兩個基因進(jìn)行后續(xù)操作。
Step3執(zhí)行交叉操作
文中使用部分匹配交叉 （PMX）[6]，該方法是 1985年，Goldberg針對TSP提出，它要求隨機(jī)選取兩個交叉點，以便確定一個匹配段，根據(jù)兩個父個體中兩個交叉點之間的中間段給出的映射關(guān)系生成兩個個體。
Step4執(zhí)行變異操作
在串中，隨機(jī)選擇兩點，再將這兩點內(nèi)的子串按反序插入到原位置中 。這種變異方法對于TSP問題，就調(diào)整前后引起的TSP圈的長度變化而言屬于最細(xì)微的調(diào)整，因而局部優(yōu)化的精度較高；但碼串絕對位置所呈現(xiàn)的“模式”變化較大，所需的計算也稍為復(fù)雜一點。
重復(fù)執(zhí)行上述步驟2～4，直到產(chǎn)生新的種群達(dá)到種群規(guī)模為止。
4）迭代完成
用best所記錄的路徑順序構(gòu)建Chord環(huán)，并實施基于前繼節(jié)點的跳數(shù)優(yōu)化策略。
2.2 基于前繼節(jié)點的路數(shù)優(yōu)化策略
單純物理拓?fù)渖系钠ヅ鋵hord邏輯路由的跳數(shù)影響甚微，因此設(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負(fù)責(zé)，從而優(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)，列出了算法流程偽代碼，詳細(xì)如下。
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 仿真模型設(shè)計
在OPNET仿真實驗中，Chord環(huán)的節(jié)點分為兩種，構(gòu)造節(jié)點和普通節(jié)點。在路由模擬過程中，各個節(jié)點都會產(chǎn)生一個含有隨機(jī)資源號的數(shù)據(jù)包，按Chord路由規(guī)則繼續(xù)轉(zhuǎn)發(fā)，直到達(dá)到目的地為止，同時記錄相應(yīng)數(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ù)的降低，所以相應(yīng)在延遲上也比原始Chord要短，但是這一延遲優(yōu)勢跟沒有使用PO法的GA-Chord相比還相差很遠(yuǎn)。在跳數(shù)上，進(jìn)行了“PO法”優(yōu)化的GA-Chord和原始Chord都體現(xiàn)出了較為明顯的優(yōu)勢。
4 結(jié) 論
本文通過引入全局性的TSP問題，并利用遺傳算法快速求得其近似最優(yōu)解，同時利用“PO法”，提出了一種的物理拓?fù)淦ヅ涞腃hord構(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：物理拓?fù)涓兄慕Y(jié)構(gòu)化對等網(wǎng) [J].計算機(jī)科學(xué)，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]王小平，曹立明.遺傳算法－理論、應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，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.
猜你喜歡
基于OSPF特殊區(qū)域和LSA的教學(xué)設(shè)計與實踐湖北第二師范學(xué)院學(xué)報(2020年2期)2020-06-05 02:18:30 探究路由與環(huán)路的問題網(wǎng)絡(luò)安全和信息化(2018年3期)2018-11-07 03:02:44 組播狀態(tài)異常導(dǎo)致故障網(wǎng)絡(luò)安全和信息化(2017年11期)2017-11-07 09:03:22 基于RSSI比例系數(shù)跳數(shù)加權(quán)的DV Hop定位算法科技風(fēng)(2017年10期)2017-05-30 07:10:36 跳數(shù)和跳距修正的距離向量跳段定位改進(jìn)算法現(xiàn)代電子技術(shù)(2017年7期)2017-04-14 19:31:22 經(jīng)典路由協(xié)議在戰(zhàn)場環(huán)境下的仿真與評測電腦知識與技術(shù)(2016年7期)2016-05-19 14:00:19 水下無線傳感網(wǎng)絡(luò)路由性能參數(shù)研究科技資訊(2014年26期)2014-12-03 10:56:56 基于新路由表的雙向搜索chord路由算法計算機(jī)工程與應(yīng)用(2014年23期)2014-08-03 15:23:18 PRIME和G3-PLC路由機(jī)制對比電測與儀表(2014年16期)2014-04-22 05:20:30 WSN中基于等高度路由的源位置隱私保護(hù)計算機(jī)工程(2014年6期)2014-02-28 01:25:54
張澤月，羅俊波，楊 芳，孫 強(qiáng)，易顯富
（湖北醫(yī)藥學(xué)院 附屬十堰市太和醫(yī)院，湖北 十堰 442000）
傳統(tǒng)的互聯(lián)網(wǎng)在移動性支持方面存在先天性不足，其主要原因在于IP地址二義性問題。文獻(xiàn)[1-2]給出了已取得了階段性的成果，但需要完善的身份和位置標(biāo)識映射方法。
在身份和位置標(biāo)識分離網(wǎng)絡(luò)中，映射表項的數(shù)量非常大，需要研究映射的優(yōu)化存儲。分布式Hash表（DHT）常用來存儲大規(guī)模的數(shù)據(jù)。面Chord[3]是一種經(jīng)典的結(jié)構(gòu)化P2P網(wǎng)絡(luò)模型，其實現(xiàn)簡單，路由跳數(shù)比較高效，是備選方案之一。但是，Chord環(huán)方法其構(gòu)造的邏輯拓?fù)渑c物理網(wǎng)絡(luò)拓?fù)錈o關(guān)，導(dǎo)致實際的路由過程中存在“舍近求遠(yuǎn)”的可能。由于查詢和定位在邏輯層與物理層上的性能差異，導(dǎo)致Chord資源定位的實際效率大大降低。
文中在對映射表項存儲方法進(jìn)行研究的基礎(chǔ)上，提出了一種基于遺傳算法 （Genetic Algorithm，GA）[4]的 Chord方法（GA-Chord），用以存儲和查詢上述的身份和位置標(biāo)識映射關(guān)系。其基本出發(fā)點是將在Chord環(huán)中查詢問題看成一個TSP問題，通過使用遺傳算法對該問題求解從而構(gòu)建Chord環(huán)，并對其路由跳數(shù)進(jìn)行優(yōu)化。該模型實現(xiàn)簡單，路由表項的額外存儲開銷也很小，而且與同類Chord模型相比，GA-Chord在資源發(fā)現(xiàn)的平均路由跳數(shù)、延時方面都有很好的優(yōu)化。
1 相關(guān)研究
1.1 Chord的拓?fù)淦ヅ浞椒?/h3>
針對物理匹配問題的研究，主要形成了3種思路：1）基于拓?fù)涞墓?jié)點ID分配的優(yōu)化；2）基于鄰近路由的優(yōu)化；3）基于近鄰選擇的優(yōu)化。針對Chord模型，學(xué)者們也分別基于上述3種方法，對基本的Chord模型進(jìn)行了改進(jìn)。
文獻(xiàn)[4]提出了一種利用ASN（Autonomous System Number）解決 Chord拓?fù)涫鋯栴}的方法，部分解決了 Chord網(wǎng)絡(luò)的拓?fù)涫鋯栴}，但是這個方法的問題是如何獲得網(wǎng)絡(luò)節(jié)點的ASN。文獻(xiàn)[5]提出了通過在候選節(jié)點中選擇更近的節(jié)點來路由查詢請求，從而降低了查詢時延，但是其表項的發(fā)現(xiàn)過程中和路由表維護(hù)過程網(wǎng)絡(luò)帶來了較重的通信開銷。文獻(xiàn)[6]利用IPv6地址的層次結(jié)構(gòu)特性來產(chǎn)生節(jié)點ID，但是覆蓋網(wǎng)中兩個相近域內(nèi)的節(jié)點其距離可能很遠(yuǎn)。文獻(xiàn)[7]提出了一種資源聚類的方法，就是提前對資源擁有節(jié)點進(jìn)行分簇，地理位置接近的節(jié)點分為一簇，資源查詢時先判斷資源請求節(jié)點距離那個簇近。這種做法優(yōu)點是計算量較小，且可以將分簇操作放在節(jié)點加入時進(jìn)行，選取節(jié)點時這需要比較一下資源請求節(jié)點屬于那個簇，從而降低了查詢時延，降低了節(jié)點的計算負(fù)擔(dān)。但是這種分簇的方法準(zhǔn)確度不高，會丟失一些拓?fù)溧徑裕袝r相鄰的節(jié)點分不到一個組中。
1.2 TSP問題及遺傳算法（Genetic Algorithm，GA）
TSP（Traveling Salesman Problem）問題，又被稱為中國郵遞員問題，是數(shù)學(xué)領(lǐng)域中的著名問題之一。TSP問題要求找到一條環(huán)路，走遍所有城市，但所有路徑最小。實際上，Chord環(huán)中的所有節(jié)點可以按ID形成一個閉合環(huán)的形式，另一方面是因為要解決的其實也是物理路徑問題。在1.1的現(xiàn)有算法分析中，其實質(zhì)都是最近鄰思想，即每次嘗試尋找的離自己最近的節(jié)點，缺乏對全局拓?fù)涞目剂?，這種短視的方法很容易陷入一個較差的局部最優(yōu)解而不是全局最優(yōu)解。當(dāng)對Chord環(huán)進(jìn)行查詢時，實際上是對所有節(jié)點的一次遍歷。這和TSP問題很相似。因此，考慮從全局性的TSP問題入手，以期產(chǎn)生更好的效果。理論證明，最優(yōu)保留的遺傳算法可以找到TSP問題的全局最優(yōu)解，因此，選擇遺傳算法來解決Chord環(huán)的TSP問題。
遺傳算法的主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。它通過自然選擇中“優(yōu)勝劣汰”的策略在每次搜索中利用各種隨機(jī)的遺傳算子生成問題的一些新解，淘汰較差的解，保留較好的以及有希望的解，從而不斷對搜索空間中新的未知區(qū)域進(jìn)行探索。它有效地利用了許多歷史信息，使得搜索每次都向著最好的方向前進(jìn)。在實際的網(wǎng)絡(luò)中，同時由于網(wǎng)絡(luò)的通信效率以及計算成本等方面的限制，使得快速得到大規(guī)模節(jié)點的TSP最優(yōu)解變得很不現(xiàn)實。而遺傳算法作為啟發(fā)式算法，其本身追求的是在相對較低的計算成本下，找到好的或接近最優(yōu)解的解答，即滿意解。所以選擇遺傳算法的目的是希望通過其快速得出TSP的滿意解。
2GA-Chord算法
為了使GA－Chord能夠快速求解，筆者對所采用的遺傳算法進(jìn)行了一定的簡化，并結(jié)合Chord特點做了相應(yīng)調(diào)整。
2.1 GA-Chord算法描述
GA－Chord算法描述如下，設(shè)Chord環(huán)中存儲節(jié)點個數(shù)為n，種群規(guī)模為m。導(dǎo)入網(wǎng)絡(luò)節(jié)點拓?fù)?，并通過節(jié)點廣播，得到各節(jié)點間的通信延遲（即節(jié)點間路徑長度），保存在距離矩陣dist[n][n]中，其中數(shù)組元素 dist[i][j]（i，j∈[0，n－1]）的值如式（1）所示，dist[i][j]表示從節(jié)點 i到 j的路徑距離。
1）編碼設(shè)計
采用整數(shù)編碼，首尾節(jié)點序號相同，且所有節(jié)點都要在編碼中。路徑表示（path representation）是表示旅程對應(yīng)的基因編碼的最自然、最簡單的表示方法。 例如，旅程（5－1－7－8－9－4－6－2－10－3）可以直接表示為（5，1，7，8，9，4，6，2，10，3）?；诼窂奖硎镜木幋a方法，要求滿足TSP問題的任一城市有且僅有一次訪問的約束條件，即要求一個個體（即一條旅程）的染色體編碼中不容許有重復(fù)的基因碼。但是，在進(jìn)行交叉、變異等操作之后所生成的個體一般不能滿足這個約束條件，需要對交叉、變異算子進(jìn)行改進(jìn)。
2）數(shù)據(jù)初始化
初始化種群及遺傳算法的各項參數(shù)，如迭代的最大值max，交叉概率、變異概率等。
3）進(jìn)行迭代
當(dāng)?shù)鷶?shù)等于max時，算法結(jié)束；否則一直循環(huán)執(zhí)行以下行為：
Step1計算適應(yīng)度
其計算方法為：
其中fm，favg分別為當(dāng)前代染色體的最小、平均路徑長度。
Step2執(zhí)行選擇操作
采用賭輪盤技術(shù)，選擇兩個基因進(jìn)行后續(xù)操作。
Step3執(zhí)行交叉操作
文中使用部分匹配交叉 （PMX）[6]，該方法是 1985年，Goldberg針對TSP提出，它要求隨機(jī)選取兩個交叉點，以便確定一個匹配段，根據(jù)兩個父個體中兩個交叉點之間的中間段給出的映射關(guān)系生成兩個個體。
Step4執(zhí)行變異操作
在串中，隨機(jī)選擇兩點，再將這兩點內(nèi)的子串按反序插入到原位置中 。這種變異方法對于TSP問題，就調(diào)整前后引起的TSP圈的長度變化而言屬于最細(xì)微的調(diào)整，因而局部優(yōu)化的精度較高；但碼串絕對位置所呈現(xiàn)的“模式”變化較大，所需的計算也稍為復(fù)雜一點。
重復(fù)執(zhí)行上述步驟2～4，直到產(chǎn)生新的種群達(dá)到種群規(guī)模為止。
4）迭代完成
用best所記錄的路徑順序構(gòu)建Chord環(huán)，并實施基于前繼節(jié)點的跳數(shù)優(yōu)化策略。
2.2 基于前繼節(jié)點的路數(shù)優(yōu)化策略
單純物理拓?fù)渖系钠ヅ鋵hord邏輯路由的跳數(shù)影響甚微，因此設(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負(fù)責(zé)，從而優(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)，列出了算法流程偽代碼，詳細(xì)如下。
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 仿真模型設(shè)計
在OPNET仿真實驗中，Chord環(huán)的節(jié)點分為兩種，構(gòu)造節(jié)點和普通節(jié)點。在路由模擬過程中，各個節(jié)點都會產(chǎn)生一個含有隨機(jī)資源號的數(shù)據(jù)包，按Chord路由規(guī)則繼續(xù)轉(zhuǎn)發(fā)，直到達(dá)到目的地為止，同時記錄相應(yīng)數(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ù)的降低，所以相應(yīng)在延遲上也比原始Chord要短，但是這一延遲優(yōu)勢跟沒有使用PO法的GA-Chord相比還相差很遠(yuǎn)。在跳數(shù)上，進(jìn)行了“PO法”優(yōu)化的GA-Chord和原始Chord都體現(xiàn)出了較為明顯的優(yōu)勢。
4 結(jié) 論
本文通過引入全局性的TSP問題，并利用遺傳算法快速求得其近似最優(yōu)解，同時利用“PO法”，提出了一種的物理拓?fù)淦ヅ涞腃hord構(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：物理拓?fù)涓兄慕Y(jié)構(gòu)化對等網(wǎng) [J].計算機(jī)科學(xué)，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]王小平，曹立明.遺傳算法－理論、應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，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.
猜你喜歡
湖北第二師范學(xué)院學(xué)報(2020年2期)2020-06-05 02:18:30
網(wǎng)絡(luò)安全和信息化(2018年3期)2018-11-07 03:02:44
網(wǎng)絡(luò)安全和信息化(2017年11期)2017-11-07 09:03:22
科技風(fēng)(2017年10期)2017-05-30 07:10:36
現(xiàn)代電子技術(shù)(2017年7期)2017-04-14 19:31:22
電腦知識與技術(shù)(2016年7期)2016-05-19 14:00:19
科技資訊(2014年26期)2014-12-03 10:56:56
計算機(jī)工程與應(yīng)用(2014年23期)2014-08-03 15:23:18
電測與儀表(2014年16期)2014-04-22 05:20:30
計算機(jī)工程(2014年6期)2014-02-28 01:25:54
