基于蟻群優化的移動P2P網絡路由選擇算法

馬麗芳 ，陳偉峰 ，蘭世戰 ，陸松 ，張玉蘭 ，莫曉斌 ，何昌智

（1．廣西建設職業技術學院，廣西 南寧 530003；2.中國移動通信集團廣西有限公司，廣西 南寧 530022；3．億陽信通股份有限公司，北京 100093）

基于蟻群優化的移動P2P網絡路由選擇算法

馬麗芳1，陳偉峰2，蘭世戰2，陸松2，張玉蘭2，莫曉斌2，何昌智3

（1．廣西建設職業技術學院，廣西 南寧 530003；2.中國移動通信集團廣西有限公司，廣西 南寧 530022；3．億陽信通股份有限公司，北京 100093）

因為移動P2P網絡具有動態性而且移動節點能量受限，提升移動P2P數據傳輸效率至關重要。利用蟻群優化算法，將螞蟻的信息素與節點的能量和通信帶寬結合起來，在蟻群選擇路徑時，減少其尋優路徑上的信息素濃度，根據概率路由表中信息素的濃度對路由選擇策略進行調整，避免網絡擁塞和個別節點能量消耗過快，提出了一種移動P2P網絡的多路徑路由選擇算法。實驗結果表明，與EDSR路由協議相比，提出的算法能夠降低節點的分組丟失率和端到端的平均時延，提高了網絡的生存周期。

移動P2P網絡；路由選擇；蟻群算法

1 引言

移動P2P網絡路由策略的優劣直接影響到系統的效率。目前，大多數文獻把在移動Ad Hoc網絡（MANET）上進行的P2P文件共享及數據分發等作為移動P2P問題來研究[2]。移動P2P網絡側重于在會話層提供面向應用的覆蓋層組網策略，移動P2P網絡可以把MANET作為其網絡層的組網方式。參考文獻[3]提出了在MANET環境下的基于P2P的數據共享方案ORION，它采取洪泛式P2P策略將路由信息轉發給鄰近節點，鄰近節點檢查是否命中，并選擇性地將其他節點的反饋消息向源節點轉發或緩存在本地文件路由表中。參考文獻[4]提出了一種移動P2P路由協議MPP，MPP利用EDSR路由協議完成覆蓋層的大部分功能，在應用層與網絡層之間加入移動節點的控制協議，負責協調它們之間的語義交互。參考文獻[5]提出了內容網絡驅動路由和網絡數據分發算法，建立內容網絡數據摘要，將數據分發到最合適的節點，根據內容摘要進行路由選擇。

在移動P2P網絡中，移動終端的能量供應等受到限制，這使得其在貢獻資源的同時必須考慮自身的能耗等因素，傳輸數據時，無線網絡的傳輸帶寬受到限制。本文利用蟻群優化算法，采用帶網絡權值的約束條件更新蟻群優化算法，從而改變信息素濃度增量，提出一種考慮帶寬限制和移動節點能量受限的路由選擇算法，以有效降低移動P2P網絡節點的分組丟失率和端到端的時延。

2 基于蟻群優化算法的移動P2P路由選擇

蟻群優化算法采用正反饋機制實現分布式全局優化，通過信息素的不斷積累和更新，最終收斂于最優路徑上[6,7]。在選擇移動P2P網絡路由時，不僅要考慮最優路徑，還要考慮最優路徑上傳輸帶寬的限制以及移動節點能量的限制，這樣可避免算法陷入局部最優解，從而使節點的能量消耗均衡。

2.1 蟻群優化策略與網絡路由優化算法的結合

螞蟻通過在其經過的路徑上釋放揮發性信息素來實現食物源與蟻穴間的最短路徑規劃。將此特性應用于網絡路由選擇，用信息素概率路由表替換網絡中每個節點的路由表，并在信息素表中，根據螞蟻行進途中釋放的信息素對其相應條目進行更新。

令t時刻路徑(i,j)上的信息素路由為τij(t)，該變量的迭代計算式必須包含新信息素路由的增加和當前信息素路由的消除。設螞蟻在t時刻選擇路由 (i,j)的轉移概率為pij(t)，與[τij(t)]α正相關，其中，α 為路由相對重要性，其值越大，表征螞蟻將選擇信息素路由較大的路徑。當螞蟻k位于節點i時，以allowedi作為可供選擇的鄰居節點的集合，并依照如下規則進行下一節點的選取。

通過式（2）對每一條路徑上的信息素軌跡進行更新：

其中，ρ為信息素的殘留系數，位于[0,1]之間。1-ρ為信息素軌跡揮發率，Δτij(t,t+1)則為t至t+1時刻間信息素濃度的增加量。

其中，m表示 t時刻處于節點 i的螞蟻的總數，Δτijk(t,t+1)表示第k只螞蟻在時刻t到時刻t+1之間釋放的信息素變化量，其值由式（4）決定：

其中，Q是常數，表示螞蟻所釋放的信息素總量，dij表示路徑（i,j）上的時延。可以看出，信息素濃度增量根據鏈路上的狀態動態變動，時延與信息素增量成反比，時延小，信息素濃度增量大，螞蟻能夠準確選擇時延比較短的路徑。

2.2 移動P2P路由選擇算法模型

移動P2P網絡路由可以表示為G=(V,U)加權圖，其中，V是圖G中所有變換節點的集合，U為圖G中所有雙向通信鏈路相聯節點的集合，每個節點的有效到達距離相等，將任意兩個存在鏈路的節點 i、節點 j表示為（i,j）∈U，即節點i和節點j之間存在連接，且節點j是節點i的鄰近節點。

剩余能量的選擇概率為p(Ej)=Ej/Ej_max，其中，Ej是節點j的剩余能量，Ej_max為節點j的初始能量。標記m個節點鏈路帶寬分別為B1,B2,…,Bi,…，Bm；若節點j是處在節點 i的螞蟻選擇到目的節點的下一跳節點，則帶寬選擇概率為：

其中，allowedi是螞蟻k在節點i時可供選擇的鄰居節點的集合，B(v)是可供選擇的鄰近節點的帶寬。函數P(j)按式（6）計算：

其中，λ1為傳輸帶寬的權值，λ2是移動節點能量的權值，λ1+λ2=1。根據式（4）和式（6），信息素濃度的增量為：

式（7）說明螞蟻在尋找最短路徑的同時受到傳輸帶寬和節點能量的限制，在其收斂于最優解的同時，平衡了數據的傳播速度和節點能耗，使得最優路徑上節點的能耗相對平均，減少了時延，最大限度地延長了整個網絡的生命周期。

2.3 移動P2P網絡路由選擇的工作原理

2.3.1 路由組建

路由組建采用按需路由的方式，繼承自AODV，使用節點序列號避免環路產生。每個節點對應某個單調遞增序列號，通過自身進行維護，并為路由表中每個目的節點維護1個最大的已知序列號，稱為目的節點序列號，它提供了一種機制用來確定兩兩不同節點對同一目的節點產生的路由條目間信息的相對新鮮度。其值越大，表征路由信息較新，能較好地反映當前網絡的拓撲情況。當源節點S要與目的節點D進行數據傳輸時，首先通過自身信息路由概率表查詢是否有與之對應的目的節點的路由項，若有，則以式（1）中概率最大的信息素進行數據的傳輸；否則，該節點就會將要發送的數據分組保存在緩存中，生成前向螞蟻Fant，廣播給周圍環境節點。

當中間節點i接收到一個新的Fant時，若該節點包含到目的節點的路由時，則向源節點回復Bant，并在式（2）中，對中間節點概率路由表中的信息素值進行相應的修改，從而建立一條正向路由，傳遞分組數據。反之，則通過路由記錄查詢是否有來自同一源節點的路由項：若不含有，表征該節點是首次接收源地址的Fant分組，并在路由表中記錄目的節點及下一跳地址等相關信息，建立反向路由，將Fant的源地址及上游節點分別作為節點i的目的地址及下一跳地址，根據式（2）調整路由表中的概率值，繼續向鄰居節點廣播Fant分組。若有，需將該Fant的源節點的序列號以及節點i上的目的節點序列號進行對比分析。

·若Fant序列號較大，表明該請求消息較新，利用Fant的源節點序列號值對節點i到源節點的目的節點序列號值進行更新，以此建立反向路由，根據式（2）進行迭代更新，調整概率路由表概率，向周圍節點廣播Fant分組。

· 若Fant序列號較小，該請求消息陳舊，直接舍棄。

·若Fant序列號與目的節點序列號相同，表明具有相同的Fant分組。而在一次路由請求過程中，應盡可能發現多條從源節點至目的節點的路徑，減輕因在網絡中尋找路由時間延長、頻次高等不利因素的負擔，并防止中間節點丟棄Fant的復制，則需進行如下判斷：若 Fant分組滿足 Fant_Hops＜Dst_Hops，建立反向路由；若 Fant_Hops＞Dst_Hops，直接舍棄。其中，Fant_Hops為Fant經歷的跳數，Dst_Hops為路由表中該節點至源節點擁有的多條有效路徑中的最大跳數。當Fant到達目的節點，其目的節點地址與節點i的地址一樣時，該節點會丟棄Fant而生成與之對應的后向螞蟻Bant，并以反向路由對源節點進行回復。在反向路徑中，節點接收到Bant后，建立正向路由，并對目的節點的信息素進行更新以及對路由表概率進行相應調整。而當源節點接收到 Bant時，直接丟棄 Bant。

2.3.2 路由維護

在移動P2P網絡中，對于一個節點來說，因為節點離開、網絡擁塞或者數據分組沖突導致的鏈路斷開是非常普遍的。節點之間利用本地廣播的hello分組信息提供連接信息，節點j到相鄰節點i的時延dij周期性更新。

使用hello消息來監視活動中到達下一跳節點的鏈路狀態，當發現網絡鏈路失效時，將刪除路由表中與之對應的條目，并對源節點的數據流進行緩存，找尋概率路由表中是否包含到目的節點的替代路徑：若有，則選擇信息素概率較大的路徑進行跳轉；否則，刪除鏈路中該節點路由條目，并向源節點發送一條鏈路錯誤的error消息。若路徑未全部中斷，則無需重新對源節點進行路由組建。

蟻群優化算法建立在按需路由選擇的基礎上，結合蟻群算法快速收斂的特點可以找到最優路徑，在路由請求中采用了備選路徑，可以減少鏈路斷開后節點發起請求的頻度，減小時延，提高傳遞率。

3 仿真實驗

3.1 仿真實驗環境

實驗平臺為PentiumⅣCPU 3 GHz/512 MB RAM的PC機，利用Window XP操作系統下基于Cygwin的平臺，仿真軟件為NS2.30，基本場景模擬了隨機分布在1 000 m×1 000 m區域內的50個移動無線節點，無線節點的覆蓋半徑為 250 m，根據移動無線模型（random waypoint model），應用程序流量模型是CBR，仿真無線通信采用512 byte的定長數據分組，無線節點移動的最大速度為72 km/h，仿真時間為900 s，MAC層采用IEEE 802.11標準，通信方式為全雙工，隊列采用 DropTail方式，利用參考文獻[8]的能量消耗模型計算節點的剩余能量。路由決策參數取值如下[8-11]：α=0.8，λ1=0.3，λ2=0.7，ρ=0.5，Q=10，τij(t)=0。

3.2 仿真實驗結果和分析

通過變化節點的停留時間 0 s、100 s、200 s、300 s、400 s、500 s、600 s，將本文提出的算法與基于MPP模型的EDSR路由算法[4]進行實驗對比，考察網絡數據分組傳遞率、平均端到端時延和網絡生存時間的變化情況。其中，網絡生存時間為從仿真開始至第1個網絡節點剩余能量為零。在運動模型中，停留時間越短，表明移動節點運動越劇烈，網絡拓撲變化越快，當停留時間為零時，說明節點一直在運動。

圖1給出了兩種算法在不同停留時間下的平均時延的仿真實驗結果。因為本文的算法考慮了選擇時延小的路徑進行信息素的更新，時延較短的路由自動匹配選擇，動態對多條路徑間實現負載均衡，且路由修復重發時延大大減少了。而EDSR只選擇跳數最短的路徑，較容易發生擁塞，所以本文提出的算法比EDSR路由算法的平均時延小。

圖1 平均端到端時延仿真結果

圖2給出了兩種算法在不同停留時間下的分組傳遞成功率的仿真實驗結果。當停留時間增長時，兩種算法的分組傳遞率都增大。但是，本文的算法采用多條備用信息素路徑，選路的時候（特別是停留時間小于200 s時）同時考慮到鏈路帶寬限制，所以本文算法獲得了較高的分組傳遞率。而ESDR算法在停留時間小于200 s時，鏈路斷開的幾率增大，導致分組丟失較頻繁。但當停留時間在200～300 s時，本文算法的分組傳輸率低于ESDR算法，因為本文算法平衡了數據的傳播速度和節點能耗，使得最優路徑上節點的能耗相對平均，減少了時延，最大限度地延長了整個網絡的生命周期，即優先考慮平均端到端時延小和節點的能量消耗平衡，而稍微犧牲分組傳輸率性能。ESDR算法則優先考慮分組傳輸率性能，增加了平均端到端時延。

圖2 分組傳遞率仿真結果

圖3的結果表明，與EDSR路由算法相比，本文的算法在利用蟻群優化算法選擇路徑包含了節點剩余能量的影響，針對每個參與路由選擇節點的能量消耗進行平衡，從而延長了移動P2P網絡路由的生存時間。

圖3 網絡生存時間仿真結果

4 結束語

針對移動P2P網絡的動態性和移動節點能量受限的特點，本文提出了一種基于蟻群優化方法的移動P2P路由選擇算法。仿真實驗結果表明，相較于MPP的EDSR算法，在網絡中端到端的通信中，本文算法較好地降低了平均通信時延，相應地提高了網絡的分組傳遞率，并獲得了更長的網絡生存時間。下一步將研究能夠提高路由容錯性的移動P2P路由選擇算法。

[1]KALOGERAKI V.Mobile peer-to-peer computing:challenges,metrics and applications[C]//6th International Conference on Mobile Data Management,May 9-13,2005,Ayia Napa,Cyprus.New York:ACM Press,2005:331-332

[2]OU Z H,SONG M N,ZHAN X S,et al.Research on mobile peer network key technology[J].Journal of Software,2008,19(1):126-140.

[3]KLEMM A,LINDEMANN C,WALDHORST O P.A special-purpose peer-to-peer file sharing system for mobile Ad Hoc networks[C]//IEEE 58th Vehicular Technology Conference,October 6-9,2003,Orlando,Florida,USA.New Jersey:IEEE Press,2003:2758-2763.

[4]SCHOLLMEIER R,GRUBER I,NIETHAMMER F.Protocol for peer-to-peer networking in mobile environments[C]//12th InternationalConferenceon ComputerCommunicationsand Networks,Oct 20-22,2003,Dallas,TX,USA.New Jersey:IEEE Press,2003:121-127.

[5]REPANTIS T,KALOGERAKI V.Data dissemination in mobile peer-to-peer networks[C]//6th International Conference on Mobile Data Management,May 9-13,2005,Ayia Napa,Cyprus.New York:ACM Press,2005:211-219.

[6]HEISSENBTTEL M,BRAUN T.Ants-based routing in large scale mobile Ad Hoc networks[C]//13th ITG/GI-Fachtagung Kommunikation Inverteilten System (KiVS 2003),February 25-28,2003,Leipzig,Germany.[S.1.:s.n.],2003:181-190.

[7]WANG Y,XIE J Y.An adaptive ant colony optimization algorithm and simulation[J].Journal of System Simulation,2002,14(1):31-33.

[8]JOSEPH M S,KUMAR M,SHEN H,et al.Energy efficient data retrieval and caching in mobile peer-to-peer networks[C]//3rd IEEE International Conference on Pervasive Computing and Communications Workshops,March 8-12,2005,Kauai Island,HI,USA.New Jersey:IEEE Press,2005:50-54.

[9]MAMEI M.Creating overlay data structures with the TOTA middle-ware to support content-based routing in mobile P2P networks [C]//InternationalWorkshop on Hot Topics in Peer-to-Peer Systems,Oct 8,2004,Volendam,Netherlands.New York:Springer,2004:74-79.

[10]OBERENDER J O,ANDERSEN F U,MEER H D,et al.Enabling mobile peer-to-peer networking[C]//1st International Workshop of the EURO-NGI Network of Excellence Wireless Systems and Mobility in Next Generation Internet,June 7-9,2005,Dagstuhl Castle,Germany.New York:Springer,2005:219-234.

[11]WEI D,MILENKOVIC O.Subspace pursuit for compressive sensing:closing the gap between performance and complexity[J].IEEE Transactionson Information Theory,2009,55(5):2230-2249．

Routing selection algorithm based on ant colony optimization in mobile P2P network

MA Lifang1,CHEN Weifeng2,LAN Shizhan2,LU Song2,ZHANG Yulan2,MO Xiaobin2,HE Changzhi3
1.Guangxi Polytechnic of Construction,Nanning 530003,China 2.China Mobile Group Guangxi Co.,Ltd.,Nanning 530022,China 3.BOCO Inter-Telecom Corporation,Beijing 100093,China

For the dynamic of P2P network and the limited energy of the mobile node,enhancing the mobile P2P data transmission efficiency is essential.By using ant colony optimization algorithm the ant pheromones were combined with the node energy and communication bandwidth.When ACO selected the path,the concentration of the pheromone on its optimization path was reduced.The routing selection strategy was adaptively adjusted by the pheromone density of routing probability table in order to avoid network congestion and excessive energy consumption of individual nodes.A multipath routing selection algorithm in mobile P2P network was proposed.Experiment results show that the proposed algorithm can reduce packet loss rate and the average delay compared with EDSR routing protocol,prolonging the lifecycle of the whole network.

mobile P2P network,routing selection,ant colony algorithm

TP39

A

10.11959/j.issn.1000-0801.2016207

2016-05-03；

2016-07-14

馬 麗 芳 （1980-），女 ，廣 西 建 設 職 業 技 術 學院講師，主要研究方向為計算機網絡技術、圖像處理。

陳偉峰（1976-），男，中國移動通信集團廣西有限公司支援專家，思科認證互聯網專家（CCIE），主要研究方向為互聯網技術和IP網絡技術。

蘭世戰（1981-），男，中國移動通信集團廣西有限公司高級工程師，主要研究方向為移動通信技術、互聯網技術。

陸松（1979-），男，中國移動通信集團廣西有限公司高級工程師，主要研究方向為移動通信技術、互聯網技術。

張玉蘭（1973-），女，中國移動通信集團廣西有限公司高級工程師，主要研究方向為移動通信技術、互聯網技術。

莫曉斌（1971-），男，中國移動通信集團廣西有限公司高級工程師，主要研究方向為移動通信技術、互聯網技術。

何昌智（1981-），男，億陽信通股份有限公司產品總監，主要研究方向為移動互聯網及通信技術、運營商移動網絡IP技術。