黄成兵

（阿坝师范学院计算机科学系 汶川 623002）

1 引言

移动互联网的发展和技术的进步，使得大量智能手持通信设备不断更新，也使得人们对通信质量和多样性的需求不断提升。从PC机诞生到可随身携带的移动终端设备，无不体现人们对通讯设备的迷恋和追求。通信设备的发展离不开基础通讯网络的发展和架构。抚今追昔，我们不难发现从开始发展到现在还在沿用的端到端网络至今天可无需依靠基础设施而自行构建的自组织网络，都是通信设备得以生存发展的前提条件。随着时代的变迁，人民生活水平的提高，传统网络已不能满足人们在特殊情况下的一些特殊需求，急需一种新的网络结构来弥补这些空缺。

机会网络［1］因为其节点的移动特性和稀疏特性，导致当节点射频关闭或者节点发射信号遇到障碍物时造成信号衰减会引起网络在多数时间内不能连通。因此，在这样复杂且多变的网络环境中，传统的无线自组织网络通信模式将不能有效运行。因为传统的自组织网络在数据转发之前，都需通过某种路由算法建立可通信链路，这些路由算法［2］包括：AODV（ad-hoc on-demand distance vec⁃tor），DSR（dynamic source routing），且信息转发到哪一个目标节点也将根据预先设计好的路由表进行选择。无线自组织网络的这一通信模式包含的一个重要假设是网络在大部分时间内是互联的，网络中任意两个节点之间都存在一条或多条通信链路。但在机会网络中，网络可能在某个特定时间段内会被分割成为互不连通的多个子区域，这就导致了源节点和目标节点之间由于不在一个连通区域内而不能实现直接通信。因此，机会网络中最大的挑战就是如何设计出一种应对这种复杂多变的网络路由算法。

在现实生活中由于人的活动都具有某些特定的规律，如每个人每天都会上班下班上学放学等，且这些人都会在某一个特定的区域内活动频繁，而在其他区域活动则相对较弱。因此有学者提出利用人活动的这一特性完成信息的传输，降低通信成本［3］。

2 相关工作

网络通信传输的根本问题是路由问题。由于机会网络链路间断特性，通信过程中往往出现源节点和目的节点之间不存在完整的通信链路从而需要不断寻找中间节点以建立传输链路。机会网络中的路由问题本质就是选择下一跳转发节点的决策问题，这与根据网络状态进行建立和维护路由的传统互联网络通信不同。研究人员利用节点移动这一特性提出了多种路由算法，如Epdemic［4］，PROPHET［5］，Spray and Wait［6］等算法。这些算法的核心思想都是基于将同一消息的多份副本放入网络中，若一个副本到达目的节点，那么这个消息传递成功。通过适当增加网络中消息副本的数量能提高消息的传输的成功率和降低传输延迟，但是消息副本数量过多又会造成节点会缓存溢出，使得节点能量过度消耗。因而有效地管理和控制消息副本数量对于提高消息传输成功率显得尤为重要。

BUBBLE算法［7］是由Pan Hui等提出的一种基于社区并适用于DTN网络的单拷贝路由算法，该算法以现实生活中真实移动轨迹为节点移动模型。首先计算出每个节点的活跃度，然后根据活跃度的大小选择进行消息转发的中继节点。该算法在网络系统和社区内依据活跃度进行排名并设计全局和社区排序表。消息进行传输的路由策略是首先由源节点将消息转发给全局中活跃度比自己大的节点，当消息被转发到与目的节点同属一个社区的中继节点时，中继节点根据社区活跃度排序表大小排名进行消息转发，直到消息到达目的节点为止。该算法充分利用人们之间的社会关系带来的通信机会进行消息转发，充分利用了活跃度高的节点与活跃度低的节点有较多的相遇机会这一特性。该算法是单拷贝策略，所以在有效控制网络中消息副本数目的同时，也增大了消息的传输延迟。

针对社区机会网络特性，本文提出一种基于Epdemic的改进算法。该算法首先计算在网络释放的信息副本数目，然后对节点缓存的副本进行管理，使得信息都不会因为缓存溢出而被丢弃。

3 基于Epdemic算法的消息缓存管理

3.1 社区机会网络移动模型的创建

多数的节点移动模型都基于以下两个假设：1）网络中的每个节点都能等概率的移动到任意位置；2）所有节点都具有相同的移动特性。但对基于事实的网络移动轨迹的大量研究证明，这两个假设在现实情况下是很难成立的［8］。为了使在仿真中具有社区特点的节点移动更接近真实，本文提出一个基于社区的节点移动模型［9］，该模型中节点的移动分为两个阶段：1）本地社区阶段；2）漫游阶段。两个阶段在节点移动的时候不断交替进行。该模型具体描述如下：

每个节点都隶属于一个本地社区Cl，节点在社区内采用经典的移动模型为Random Waypoint。

本地社区阶段（Local Community Epoch）：节点被限制在本地社区Cl内运动，其运动的时间长度为-Lr，节点此时所处的状态称为本地状态Sl。

漫游阶段（Roaming Epoch）：节点大部分时间在所属社区Cl内运动，有时可移动到其他社区，节点在Cl外运动时间预期为-Ll，节点此时所处的状态称为漫游状态Sr。

节点的移动形成了一个由本地社区阶段和漫游阶段组成的序列。

本地社区概率（Local Community Probability）：如果前一个阶段节点处于本地社区状态为Sl，则下一个阶段节点处于本地社区状态仍为Sl的概率为pl，处于漫游状态的概率为1-pl。

漫游概率（Local Community Probability）：如果前一个阶段节点处于漫游阶段，状态为漫游状态Sr，则下一个阶段节点仍处于漫游状态的概率为pr，处于本地社区进行移动的概率为1-pr。

此模型依据观察现实生活中各种真实的节点移动轨迹的移动特性，将上述具有社区特点的节点移动模型表述为两个状态的马尔科夫链，如图1所示。

据上述节点状态变化的马尔科夫链图，由马尔科夫链理论可得：

在任一给定阶段，节点处于本地状态的概率为

在任一给定阶段，节点处于漫游状态的概率为

以上述模型运行的节点往往具有本地特征，即他们的大部门时间都是在本地社区内，概率pl＞60%；有时节点也会离开本地社区到其它地区漫游，漫游的概率为pr。不同的节点可以有不同的参数值（pl，pr），这正符合节点在大范围内移动的特征变化模型。

图1 节点状态变化图

3.2 控制消息副本数量

使用Epdemic路由算法进行社区间消息传递的时候，将导致某一社区内消息副本数目过多，从而使得大量节点的缓存饱和。当节点接收到新的消息的时候，不得不将旧的消息丢弃，然而旧的消息可能还没有传输成功，这样就导致了Epdemic路由算法的性能下降。因此，合理控制网络中消息副本数目将有效改善消息的投递率。

论文［10］中已经提出在Random-Waypoint下，节点平均移动的相遇时间是EMrwp，计算公式如下：

在式（3）中，Tˉ为节点的平均移动时间，----Tstop为节点的平均暂停时间任意一个时刻的移动概率，vrwp是 Random-Way⁃point移动模型中节点的归一化速度，N表示节点的移动范围，K为节点的通信范围，Lˉ为节点一次移动的平均距离，在 N× N的正方形区域中Lˉ=0.5214 N 。节点在以Random-Waypoint模型移动时，每隔EMrwp时段就会有两个节点相遇，EMrwp值的大小决定了节点相遇是否频繁。

当假设节点能量不被完全消耗的情况下，Ep⁃demic路由算法的传输延迟在性能上接近理论最优值EMopt，计算公式如下：

式中C为常数，可取0.34，N为节点的移动范围，M为节点数量，V̂为节点的平均移动速度，K为节点的通信范围，网络中每个节点按最优路径到达目的节点的转发次数为D可用下式计算：

确定了转发次数就可以确定网络中每个数据副本总数为D。

3.3 管理缓存溢出

在节点内缓存空间是有限的，要想在有限的空间内接收新的信息，同时又要使旧的信息不因空间有限被删除，就要对当缓存发生溢出时采取合理的删除手段进行管理［11］。为此本文引入了一种具有退避机制的缓存管理办法。具体如下：

1）网络中每个节点维护一个字段，该字段用来存放阈值t。

2）阈值t是随机产生的，并且服从均匀分布，其值范围是（0，x）。其中x是参数，取值根据网络状况而定。

3）当某一通信节点缓存充满后，在时间t内，该节点将拒绝接收目标节点的数据分组，即在阈值时刻内令其他节点的数据分组退避。

4）当退避时间超过t后，无论节点缓存状态如何均接收数据分组，此时可能还会发生挤出事件。接收数据分组后，将退避时间设为零。

通过上述策略可以减小缓存溢出的频繁发生，尤其是路由采用洪泛算法情况下。

4 仿真和结果分析

4.1 仿真环境设置

本文采用仿真器ONE［12］对算法性能进行仿真，将其仿真结果和Epdemic算法、SA-Epdemic算法进行比较。由于本算法在网络运行初期要计算Pi值，所以仿真开始时先进行1000s的预热。社区布局为4*4的方式，在所有节点之间随机分布网络节点。为了使节点的移动模型更加接近于真实情况，本文参照SF［13］算法设置的仿真场景来模拟真实的网络移动轨迹。将网络中的节点分为两类，一类称为本地节点，数目占整个网络节点总数的80%，它们绝大部分时间在本地社区移动，其Pl在［0.8，0.95］之间取值，同时本地节点也会在网络中的其它社区漫游，其Pr在［0.1，0.2］之间取值；另一类称为漫游节点，数目占网络中节点总数的20%，此类节点经常在网络中其他社区漫游，其Pr的值分布在［0.3，0.4］之间，漫游节点大部分时间仍在本地社区内移动，其Pl在［0.7，0.8］之间取值。其它的主要仿真参数如表1所示。

表1 主要的仿真参数

4.2 实验结果及分析

4.2.1 消息数量和传输成功率的关系

由图2可以看出，随着消息数量的不断增多，使用Epdemic算法进行数据转发，消息的传输成功率下降的速度要快于B-Epdemic算法。B-Epdemic并没有对路由路由算法Epdemic本身做修改，而是根据节点的社区特性对消息进行一个有效的管理，从而提高了Epdemic算法在社区模型中消息的传输成功率。

图2 消息数量和传输成功率的关系

4.2.2 消息数量和路由开销的关系

由图3可以看出随着消息数量增多，路由开销都在下降，但是Epdemic算法的路由开销始终大于B-Epdemic，这不难解释。因为Epdemic算法是洪泛算法，不停的在传播消息，而B-Epdemic有所限制。因此从仿真开始到结束，Epdemic算法的路由开销一直大于B-Epdemic算法的开销。

图3 消息数量和路由开销的关系

4.2.3 消息数量和传输延迟的关系

由图4可以看出，随着消息数量的不断增多，两种算法的传输延迟都是不断增加，这是由于信息的增多，使得各个节点内部没有多余的存储空间，只能等待消息过期被删除才能接收新的消息。但B-Epdmeic算法的传输延迟明显要大于Epdemic，因为本身B-Epdemic对消息数量进行了限制，又有缓存溢出的管理，所以传输延迟会更大。

图4 消息数量和传输延迟的关系

5 结语

文中首先分析了当前机会网络的发展现状和几种经典路由算法，以及这些路由算法应用在社区机会网络中存在的相关问题。针对社区内节点移动特点和不足，提出B-Epdemic算法。该算法基于社区机会网络的消息缓存管理策略进行优化，能够使传输消息在的社区机会网络中以较高的传输成功率和较低的路由开销进行传输。实验结果表明B-Epdemic算法在较好的控制消息副本数量的同时减小了缓存溢出的发生。在允许较大延迟的情况下使得消息传输成功率、路由开销相比原Ep⁃demic算法都有显著提高。