基于节点行为的机会网络路由协议

孙建飞　高媛　王淑敏

摘 要：高移动性、频繁中断、稀疏链接、没有基础设施和有限的资源被认为是机会网络的特点。在这样的网络中路由是最大的挑战，在此提出了一个新的基于节点行为的机会网络路由协议（OPNB），用节点的行为信息预测节点在网络中的移动，为消息路由到目标节点发现和选择更好的下一跳节点。协议还集成了对接收消息的确认，有助于中间节点的缓存管理。通过与epidemic路由协议和Probabilistic路由协议比较，OPNB协议在消息的交付数量、开销比率、平均延迟和缓存时间方面的表现相当不错。

关键词：机会网络；路由协议；节点行为；消息确认

1 简介

存在着稀疏性链接和间歇性链接的网络被称为机会网络。在机会网络的节点通常是由人或车辆携带的移动设备。因此在某个时间段内它们存在某种移动方式。它们可能属于或放置在经常访问的社区。了解节点的运动，社区与社区成员可以帮助我们在网络中构造网络的结构，因为根据社会学的“相关互动”意味着生物体更容易与他们自己类型的生物而不是别的生物相互交流。文献[1]中依赖于网络的洪泛能力最终将消息交付给目标节点，但这样网络中就存在同一消息的许多副本。文献[2]中使用历史相遇和传递概率来分发消息，可用于快速有效的分发消息。PRoPHET使用FIFO作为缓存管理机制，可能致使中心节点丢包且没有包含任何的消息确认机制。

2 OPNB路由协议

协议分为3个阶段：初始化起始位置，信息产生和下一跳确定，信息确认。

2.1 初始化起始位置

每个节点有一个确定的位置可能访问频繁，其它位置访问较少。据此，节点的起始位置被分配为节点频繁访问的位置。在网络运作过程中，不同节点接触分享他们的起始位置。每个节点包含一个表存储网络中其他节点的初始位置。

2.2 信息的产生和下一跳的确定

分为两部分：⑴产生新信息和目标id，⑵是下一跳的选择，用到3个参数。

（1）节点的稳定性，有下面两种情况：

a、节点当前速度大于平均速度，如下：

Snew=Sold-Sold×Sint （1）

其中Sint 是初始化常量，属于（0，1]。如果稳定值已经为0，则不再减少。

b、节点当前速度小于平均速度，如下：

Snew=Sold+Sold×Sint （2）

（2）预测节点将来的运动方向。

（2.a）马尔科夫预测节点的下一位置：这个模型用过去的几个位置预测下一个位置。例如：如果节点过去的位置序列为

22→2→11→78→5→60→10→3→45→78→5→60→2→12→55→66→78→5→90→91→98→97→23→22→78→5→60→90

据规则为2的马尔科夫模型，节点的下一位置为60。

（2.b）预测运动方向：通过角度度量预测节点是接近还是远离目标节点。

（2.b.1）计算邻居与目标节点的位置：邻居的位置取决于笛卡尔平面的象限找到，如图1所示，所有向原点（目标节点）移动的节点被选择。以下方程用于转换：

X=（x-dd）×cos（α）-（y-yd）×sin（α）

Y=（x-dd）×sin（α）+（y-yd）×cos（α）

（2.b.2）检查邻居节点位置相对于方程y=+/-y的角度值：如图2所示，D代表目标节点、矢量代表节点的移动。

节点i的角度效用计算如下：

Angle_metric（i）=Aint×cos（anglei） （3）

其中，Aint是一个恒定的倍增因子，远离目标节点的节点的角度效用值为0，确保远离目标的节点不被选择。

（3）从SD线到邻居节点的垂直距离d：

综上，效用度量如下：

W（j）（j=1，2，3）分别代表上面3个参数的常量因子，V（j）（j=1，2，3）分别代表上面3个参数的值。邻居的效用值大于阈值T的节点作为消息的转发节点。

2.3 消息确认

确认机制据具有一定运动模式的节点很可能再次相遇，提出以下确认方案。一旦消息到达目标节点，目标节点将产生一个AckMsg消息，如表1所示。

目的节点用Binary Spray and Wait方式的确认。每当目的节点遇到存在于AckMsg中的副本，则从邻居中删除，更改AckMsg并传给该节点。修改后的AckMsg包含1/2的节点的ID数、一个新的生存时间。目标节点保持剩余的n/2的节点ID列表在修改后的AckMsg中。这个过程不断重复，直到AckMsg仅有一个节点的ID。

3 模拟实验与性能评价

OPNB使用ONE作为仿真工具。采用Custom Human Mobility model作为移动模型。节点被分为6组。节点的传输距离为10m，传输速度2Mbps。模拟范围为4500m× 3400m，模拟时间43000s。每隔25-35s产生一个500kb-1MB的新消息。参数和变量设置为：tin=50，m=100，z=10，Sint=0.2，Aint=10，W（1）=0.4，W（2）=0.4，W（3）=0.2。

在图3a-d是OPNB的性能与epidemic和PRoPHET路由协议的比较结果。如图3所示，可以看出OPNB比另外两种协议有更高的消息交付数。如图4所示，展示随节点数的增加开销在增加，这是因为节点现在有更多的邻居可以进行消息的分发，但开销比率小于另外两种协议，因为它采用了效用度量。如图5所示，显示OPNB的缓存延时最高，这是由于使用效用度量使消息选择了更好的转发节点。

在消息投递数量上OPNB比epidemic高15.04%，比PRoPHET高10.95%。epidemic的开销比率比OPNB多113.44%，PRoPHET的开销比率比OPNB多54.55%。平均缓存时间比epidemic多21.27%，比PRoPHET多13.62%。

4 结语

文中提出算法据节点行为和节点的稳定性选择最佳的下一跳。这种方式更适合于人的移动性场景。与epidemic和PRoPHET比较，OPNB的消息交付性能很显著，因为它选择了更好、更可靠的下一跳节点，OPNB的平均缓存时间明显高于另外两种协议。今后，OPNB协议会与网络编码相结合实现更好的路由性能。我们还计划研究OPNB的实际使用环境下的性能。

[参考文献]

[1]Amin Vahdat，David Becker.Epidemic routing for partially connected ad hoc networks[R].Technical Report CS-2000-06，Department of Computer Science，Duke University，2000.

[2]Anders Lindgren，Avri Doria，Olov Schelen.Probabilistic routing in intermittently connected networks[M].In Springer-Verlag Berlin Heidelberg 2004，239-254.