基于蚁群优化的移动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技术。