机会网络中转发机制的研究

龚丁海

(1.广西师范大学 计算机科学与信息工程学院，广西 桂林 541004;2.河池学院 数学系，广西 宜州 546300)

机会网络中转发机制的研究

龚丁海1，2

(1.广西师范大学 计算机科学与信息工程学院，广西 桂林 541004;2.河池学院 数学系，广西 宜州 546300)

通过详细描述路由转发算法－传染转发算法的转发过程，分析此种算法存在的不足，提出一种基于转发度量的传染算法，并对该算法进行简要评价。

机会网路;转发机制;传染转发

传统的无线自组织网络中的路由协议通常隐含以下假设:即网络大部分时候是连通的，任一节点对之间存在至少一条完整的端到端的路由。机会网络［1－2］是利用节点移动带来的相遇机会实现通信的一种新型无线自组织网络模型，其目的是为了解决频繁间断网络中的数据通讯问题。在机会网络中，由于节点移动不可预测、稀疏、能量和存储受限等因素导致网络拓扑出现割裂，使源和目标节点位于不同的连通域，导致传统的无线自组网路由通信协议无法有效运行。机会网络中这种节点间接触率的不一致性，节点移动的随机性和网络信息的匮乏，导致通信必须依靠节点移动和多跳实现。因此，在机会网络的路由设计中，常采用“存储—携带—转发”模式。近几年来，很多学者对机会网络的转发机制做了大量的研究工作，并取得了一定的成果，其中，传染转发算法(Epidemic Forwarding，EF)［3］是比较经典的路由算法。本文主要对该算法进行评价分析，并针对传染转发算法存在的问题，提出一种基于转发度量的传染算法(Epidemic Based on Forwarding Metric，EFM)，最后对该算法进行简单的评价。

1 传染转发算法的转发机制

传染转发算法是为了解决部分连通的Ad hoc网络的路由通信而提出，其设计目的:(1)提高消息的投递率;(2)减少消息的传输延迟;(3)减少消息传递的总资源消耗［3］。为完成以上的设计目的，传染转发算法试图通过洪泛将消息转发给所有邻居节点，直到消息过期或最终到达目的节点。图1为消息源节点到目的节点的消息路由示意图。(a)图表示是在t1时刻，源节点S试图将消息m发送给目的节点D，但不存在连接的路径，S将消息m转发给在其直接传输范围内的邻居节点N1和N2;(b)图表示在某时刻t2＞t1，节点N2移动到节点N4的直接通信范围内，将消息m转发给节点N4，N4再将消息转发给在其通信范围内的目的节点D。

图1 源节点到目的节点传递消息示意图

传染转发算法的工作原理具体描述如下:网络中每个节点都有一个存储消息的缓存，每个消息有一个网络中唯一的标识ID，节点以该标识为索引建立一个哈希索引表。同时节点维持一个向量表SV(Summary Vector)，用于记录节点缓存中存储的消息。当节点i和节点j相遇时，其转发步骤如下:

Step1:节点i向节点j发送向量表SVi;

Step2:节点j收到i发送的SVi后，与SVj相比较，找出在SVi中有，而在SVj中没有的项，构成另一个向量SV1，向量SV1记录节点i缓存中有而节点j没有的消息，并将SV1发送给节点i;

Step3:节点i收到SV1后，将向量SVi中标识的消息逐条发送;

Step4:节点j收到i发送的消息，更新SVj

通过以上四个步骤完成了节点i向j的消息传送，图2为传染转发算法中消息转发的工作原理。同样，节点j也通过以上步骤向节点i完成消息的传送。当操作完成后，两个节点的缓存里有同样的消息。当碰到其他邻居节点时，继续重复以上步骤，直到消息过期(TTL过期或超出最大传递跳数)或消息到达目的节点。

图2 消息转发原理

2 传染转发算法的性能

传染转发算法的主要思想是“存储—携带—转发”，以洪泛的方式将消息转发给相遇的节点，以期望能有更多的节点参与消息的转发，最终以较高的成功传达率到达目的节点。在传染转发算法中，实际上隐含有一个条件，即越多的节点参与消息的转发，消息成功到达目的节点的可能性就越大。但以上隐含的条件忽略了一个事实，即并不是所有的节点，都是“好”的消息转发者，如源节点S，将消息转发给相遇节点A，但是节点A却很少与其他节点相遇，很少有机会将来自源节点的消息成功转发。这种情况下，源节点S到节点A的消息转发造成了网络带宽的浪费，消息副本的产生也提高了消息转发的成本。节点无限制的转发消息，使网络中存在大量的无用的消息副本，易造成网络拥塞。另外一种情况是，当节点的缓存空间有限时，由于消息的洪泛，易造成节点缓冲的溢出，节点就会选择将存储时间较长的消息删除。因此，在传染转发算法中，高传达率的条件是要求网络中的网络带宽和缓存等网络资源充足。而在机会网络中，实际网络节点带宽和缓存等资源是受限的，因此随着网络节点数的增大，其性能由于广播导致的拥塞会急剧下降［2］。

3 基于转发度量的传染算法

从上面分析可知，传染转发算法实际上是一种洪泛算法，存在一定的缺陷，当网络资源受限时，会由于无限制的洪泛，造成网络拥塞，大大影响该算法的性能。改善该算法性能的一个方法就是通过某种方法限制洪泛，减少消息转发过程中消息副本的数量。此外，网络中一个活跃的节点会经常与网络中其他节点相遇，也会不时地与目的节点相遇。因此，可根据这一特征设置一个转发度量，作为转发消息的依据，消息持有者只将消息转发给转发度量值比自己高的节点，限制网络中的洪泛。

3.1 基于转发度量的传染算法转发度量的估算

基于转发度量的传染算法在估算转发度量时，同时考虑节点与其他节点的接触率和与消息的目的节点最后相遇时间。设定时间窗口T，转发度量x定义如下:

其中α是权重常量(α∈［0，1］)，r为消息持有者与其他节点的接触率，即单位时间内，与其他节点的接触次数;t为当前时间减去节点与目的节点最近接触的时间，时间单位与窗口值T相同。α为零时，转发度量只考虑与目的节点最后相遇的时间;α为1时，转发度量只考虑节点与其他节点的接触率。

由公式(1)可知，当节点与其他节点的接触次数越多，且距离与目的节点最近相遇的时间越短，其转发度量越高，则会有更多的消息转发给该节点;当节点与其他节点长时间没有接触时，接触率降低，则转发度量值低，消息持有者不会将消息转发给转发度量值低于自己的节点。长时间没有与其他节点或目的节点接触的节点，其转发度量随时间不断下降，当持有消息时，会在偶尔的与其他节点相遇时，将消息转发给度量值高的节点。

3.2 基于转发度量的传染算法的转发步骤

初始化:任意节点i和j分配有转发度量值x，每个节点维持一个向量表SV，SV中含有该缓存区存储的消息及转发度量x。

假设节点i携带消息，目标节点为d，当节点i与j相遇时，i执行的消息转发流程如下:

Step1:向j发送目标节点为j的消息，记录其ID并将消息副本从缓存中删除。

Step2:与j交换消息向量表SV，挑选出符合xi＜xj的消息，将其ID汇总成一个向量表SV1向j发送。

Step3:节点j接收到SV1后，从SV1中删除其已经缓存消息对应的ID，并发回i。

Step4:节点i接收到j返回的SV1后，将SV1表中的消息按照xj从大到小排队，组成消息转发队列L。

Step5:若L为空，则转发结束，退出。否则取队首消息，将消息转发给j，并将其从L和缓存中删除，转Step5。

3.3 基于转发度量的传染算法的评价

基于转发度量的传染算法相对于传染转发算法，主要改进了消息无限制的洪泛，通过比较节点对某个消息的转发度量，选择是否进行消息转发，从而限制了消息无限制的转发，控制消息转发过程中消息副本的数量，减少了转发成本，即减少了网络消息副本的数量，避免了网络中由于消息广播而引起的网络拥塞。

4 结束语

机会网络是最近引起广泛关注的一种新兴无线自组网，由于其网络特性，传统无线自组网中的路由转发算法大多不适用于机会网络，其转发机制还有待进一步研究。传染转发算法是一种具有代表性的机会转发机制，本文提出的基于转发度量的传染算法改进了传染转发算法的性能，较好的解决了传染转发算法中存在的问题。

［1］Hunag C H，Lan K C，Tsai C Z.A survey of opportunistic networks［C］//Proceeding of the22nd International Conference on Advanced Information Networking and Applications.Ginowan:IEEE Press，2008:1 672 － 1 677.

［2］熊永平，孙利民，牛建伟，等.机会网络［J］.软件学报，2009，20(1):124 －137.

［3］Vahdat A，Becker D.Epidemic routing for partially connected ad hoc networks，CS－2000－06［R］.Durham Nc:Department of Computer Science，Duke University，2000.

Research on Forwarding Mechanism in Opportunistic Networks

GONG Ding-hai1，2
(1.School of Computer Science and Information Engineering，Guangxi Normal University，Guilin，Guangxi 541004;2.Department of Mathematics，Hechi University，Yizhou，Guangxi 546300，China)

This paper describes the forwarding process of a routing forwarding algorithm，epidemic forwarding algorithm in detail and analyzes its deficiency.Then it proposes a new epidemic algorithm that is based on forwarding metric，and briefly evaluates this algorithm.

opportunistic network;forwarding mechanism;epidemic forwarding

TP393.0

A

1672－9021(2011)02－0049－03

龚丁海(1979－)，男，湖南郴州人，河池学院数学系讲师，主要研究方向:计算机软件与理论。

2011－03－10

［责任编辑 刘景平］