基于位置信息的移动P2P路由发现策略

张尊国

（中国移动通信集团广西有限公司，南宁 530022）

移动自组网（MANET）是有移动的可以互相通信的主机组成的无线网络。在MANET里，网络本身在路由和传输算法上都是以P2P方式实现。基于MANET和P2P的这些特点，提出了在移动自组网上建立一个灵活的、可扩展的移动P2P系统。MP2P网络的拓扑结构是动态改变的，网络中的节点可以任意地移动。移动P2P网络路由协议受到节点移动性、节点本身能量、无线链路的带宽的限制，移动P2P路由策略的优劣直接影响到系统的效率。

由于基于位置的路由协议不用维持端到端的路径，只要保持目的节点的最新位置信息就能完成数据转发任务，因此比传统的路由协议更具有优越性，它们有更高的分组传送率、低的路由开销和可扩展性等，能适用于各种规模的MP2P。

1 LAR 路由协议

LAR(Location Aided Routing)路由协议通过使用节点位置信息来降低路由请求开销以改善MP2P网络路由协议的性能。位置信息可由全球定位系统(GPS)来提供，GPS提供的位置坐标可能和节点真实坐标间有些误差，但假定是精确的。如果节点S需要寻找一条到节点D的路由，假设节点S知道节点D在t0时刻的位置L（Xd，Yd），及平均移动速度v，当前时刻为t1，那么从节点S的角度来看， 在t1时刻节点D的位置应该是位于以D（Xd，Yd）为圆点， 半径为v(t1- t0)的圆内，并称这个圆为D的期望区域。

图1 搜索域和期望域

2 ELAR(Enhanced LAR)路由协议

LAR协议通过目的节点的位置信息确定请求区域以降低路由请求开销，当不知道目的节点位置时，则在整个网络范围内广播转发，就会降低整个网络内广播分组的数量， 降低了网络的通信负载， 以提高网络的性能。另外，由于路由请求分组内包含中间节点的位置信息，目的节点可利用这一信息对已获得的路径进行进一步优化以提高网络性能。

2.1 基于距离的位置路由算法

用图G=(N，E)表示一个移动P2P网络，其中N是网络中所有节点的有限集合， E是连接两个可直接通信节点的边集，在图中采用分层的体系结构，节点分为两类：簇头节点(CH)和成员节点(MN)。成员节点和簇头直接通信，簇头之间通过多跳方式通信。

2.2 路由发现

当NS想发送数据分组到ND，首先执行LAR协议，如果在Request zone内路由发现不成功， NS不进行简单的洪泛机制，而是在Request zone之外触发新的路由发现：

（1）NS首先在Request zone之外广播位置请求(LREQ，Location Request) 询问ND的地理位置。一旦收到LREQ，簇头节点在其位置数据表中查询ND。如果找到，节点就将带有IC值的位置应答(LREP，Location Reply)返回至NS，否则将返回位置错误(LERR，Location Error) 。

（2）如果NS收到LERR，表明不存在此ND，路由发现过程结束。如果是LREP，NS取出ND的位置信息和IC值，并发送路由请求(RREQ)。初始时，RREQ中的PrePos是NS的位置信息，随着路由发现的进行，PrePos就是NI的位置信息。转发算法过程如下：中间节点NI收到路由请求分组RREQ，首先查看SeqN序列号，判断是否重复接受，若为重复节点，直接丢弃。若是第一次接受的节点，判断是不是目的节点，是则返回RREP分组，源节点NS收到RREP，得知路由已经建好，可以进行数据传输。

（3）NI收到RREQ ，在确认自己不是ND后，会先检查IC值，看ND的位置信息是否能继续用于路由发现。如果IC值不同，说明位置信息已经过时，这时NI就会在本地发起路由搜索。NI将缓存此RREQ并广播LREQ。在收到LREP后检查相关距离。否则，将直接开始检查相关距离。

图2 中间节点转发流程图

（4）在相关距离检查期间，NI比较自己到ND的距离和其NP到ND的距离，若满足：

NI才能转发，否则RREQ将被NI丢弃。这里D (NI，ND)表示NI和ND之间的几何距离，δ和是常量系数。通过设置δ和可以自适应地调整相关距离的检测，即调整转发条件。

（5）当一个己经建立的路径由于节点移动导致路径中断时，中断链路上游节点发送RREQ分组进行局部路由中断修复。如果中断链路上游节点在一定时间内没有收到目的节点回复的RREP分组，则中断节点发送RERR分组给源节点，由源节点判断是否重新发起路由发现过程。由于禁止中间节点直接回复RREP分组，只允许目的节点回复RREP分组，因此可保证中断节点到目的节点之间修复路径的稳定性。

3 性能评估

3.1 仿真实验环境

实验平台为Pentium Ⅳ CPU 3.0 GHz、512 MB RAM的PC机，利用Windows XP操作系统下基于Cygwin的平台，仿真软件为NS2.30，基本场景模拟了50个移动节点随机分布在1000 m×1000 m的区域内。节点随机选择移动方向并作连续移动，最大移动速度从5 m/s逐步递增到50 m/s，步长为5 m/s。随机的选择源节点和目的节点，链路带宽为10 kbit/s，节点的传输半径为250 m。调整节点的位置更新周期为2 s，距离更新门限DUT=100 m，δ=1，=0。每次实验的仿真时间为600 s。IC初始值设置为0。

3.2 性能参数

仿真主要根据下面两个指标来进行性能度量：

(1) 分组投递率：应用层信宿接收的分组数与信源发送的分组数之比，反映了网络传输的可靠性，投递率越高，可靠性越大。

（2）路由控制开销：网络内所有节点发出的控制分组总和与目的节点收到的全部数据分组的比值。本文算法中控制分组包括位置控制分组（LREQ，LREP）以及路由控制分组（RREQ，RREP，LERR）。

3.3 实验结果分析

通过变化节点的移动最大移动速度分别是0 m/s，5 m/s，10 m/s，15 m/s，20 m/s，25 m/s，30 m/s，35 m/s，40 m/s，45 m/s，50 m/s。我们将本章提出的ELAR算法与基于MPP模型的EDSR路由算法进行实验对比，考察网络分组投递率、路由控制开销的变化情况。

图 3 分组投递率

图3表示移动速度不同情况下的分组投递率结果，表明随着移动速度的增加，节点的位置变化加剧，节点间的连接变得更加脆弱，由此导致分组投递率下降。从图中可以看出本文提出的ELAR算法优于EDSR路由算法，这是由于EDSR缺乏对目的节点位置信息的定位，采用整个网络的泛洪路由，缺乏目的节点的位置指导，降低了寻路的成功率，影响了投递率。本文算法把路由发现过程与节点的位置信息联系起来，使请求区域的确定更加准确，缩小了广播区域，同时利用簇头节点维护位置信息，通过设置距离更新门限，把节点位置信息不准确性的影响降到最低，选择Qpath值小的进行簇路由选择，因此路由的稳定性高，从而获得比较好的分组投递率。

图4 路由控制开销

图4表示路由控制开销和节点运动速度的关系，随着节点移动性增强，路由控制开销都有所增加。当节点的移动速度小于20 m/s的时候，位置比较稳定，ELAR协议的控制分组数目包括位置控制分组（LREQ，LREP）以及路由控制分组（RREQ，RREP，LERR）两部分比EDSR路由协议控制分组多，从而影响了其控制开销。但随着节点移动速度的增强，EDSR的路由开销增长速度高于本文的算法，节点移动速度增强，链路断裂的可能性增强，EDSR协议要不断的进行泛洪路由发现策略，产生更多的路由分组，极大的增加路由负载。ELAR协议位置控制分组保证了节点的位置信息准确性，减少路由分组的请求数量。当节点的移动速度大于20 m/s的时候，本文算法更适合移动P2P网络。

4 总结

本章基于位置辅助的路由协议（LAR），提出了一种带路径优化的增强型（ELAR）协议。通过在每个路由请求分组中携带源端点及每个中间节点的位置信息，使节点获得其它节点的位置便于其缩小路由请求区域。当在位置辅助路由协议路由发现失败时避免采用全网洪泛机制，采用基于距离的位置路由改进算法，设置距离更新门限来达到节点位置信息实时性与更新负载的平衡。实验结果表明对于移动P2P网络有较低的分组投递率和有较好的路由控制开销。

[1] 郑少仁，王海涛等. Ad Hoc网络技术[M]. 北京：人民邮电出版社，2005.

[2] 陈贵海, 等. 对等网络：结构、应用与设计[M]. 北京：清华大学出版社，2007.

[3] 欧中洪, 宋美娜, 战晓苏, 宋俊德. 移动对等网络关键技术研究[J]. 软件学报, 19(1):126-140.