基于蟻群優(yōu)化的移動P2P網(wǎng)絡(luò)路由選擇算法

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

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

基于蟻群優(yōu)化的移動P2P網(wǎng)絡(luò)路由選擇算法

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

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

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

移動P2P網(wǎng)絡(luò)；路由選擇；蟻群算法

1 引言

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

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

2 基于蟻群優(yōu)化算法的移動P2P路由選擇

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

2.1 蟻群優(yōu)化策略與網(wǎng)絡(luò)路由優(yōu)化算法的結(jié)合

螞蟻通過在其經(jīng)過的路徑上釋放揮發(fā)性信息素來實現(xiàn)食物源與蟻穴間的最短路徑規(guī)劃。將此特性應(yīng)用于網(wǎng)絡(luò)路由選擇，用信息素概率路由表替換網(wǎng)絡(luò)中每個節(jié)點的路由表，并在信息素表中，根據(jù)螞蟻行進途中釋放的信息素對其相應(yīng)條目進行更新。

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

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

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

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

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

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

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

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

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

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

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

2.3 移動P2P網(wǎng)絡(luò)路由選擇的工作原理

2.3.1 路由組建

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

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

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

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

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

2.3.2 路由維護

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

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

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

3 仿真實驗

3.1 仿真實驗環(huán)境

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

3.2 仿真實驗結(jié)果和分析

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

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

圖1 平均端到端時延仿真結(jié)果

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

圖2 分組傳遞率仿真結(jié)果

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

圖3 網(wǎng)絡(luò)生存時間仿真結(jié)果

4 結(jié)束語

針對移動P2P網(wǎng)絡(luò)的動態(tài)性和移動節(jié)點能量受限的特點，本文提出了一種基于蟻群優(yōu)化方法的移動P2P路由選擇算法。仿真實驗結(jié)果表明，相較于MPP的EDSR算法，在網(wǎng)絡(luò)中端到端的通信中，本文算法較好地降低了平均通信時延，相應(yīng)地提高了網(wǎng)絡(luò)的分組傳遞率，并獲得了更長的網(wǎng)絡(luò)生存時間。下一步將研究能夠提高路由容錯性的移動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-），女 ，廣 西 建 設(shè) 職 業(yè) 技 術(shù) 學院講師，主要研究方向為計算機網(wǎng)絡(luò)技術(shù)、圖像處理。

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

蘭世戰(zhàn)（1981-），男，中國移動通信集團廣西有限公司高級工程師，主要研究方向為移動通信技術(shù)、互聯(lián)網(wǎng)技術(shù)。

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

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

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

何昌智（1981-），男，億陽信通股份有限公司產(chǎn)品總監(jiān)，主要研究方向為移動互聯(lián)網(wǎng)及通信技術(shù)、運營商移動網(wǎng)絡(luò)IP技術(shù)。