存储-携带-转发路由中基于消息优先级的缓存管理算法

林 勇，王玉珏，吴庆州

(1. 重庆电子工程职业学院，重庆 401331;2.南京理工大学，江苏 南京 210046)

0 引 言

近期，稀疏移动自组网(Sparsely Populated Mobile ad-hoc Network)受到研究人员的广泛关注[1-2]。稀疏移动自组网是典型的时滞容错网络(Delay Tolerant Networks, DTN)网络[3]。在稀疏移动自组网内，由于节点密度低，节点间的连接在多数时间内处于断裂状态。然而，由于节点的移动，两节点可能偶尔处于彼此的通信范围内，进而形成间歇性的连通。在这种情况下，节点间能够通信。由于是间歇性通信，常采用存储-携带-转发路由。利用节点机会性的连通机会，携带数据转发，完成消息的传输[4]。

在存储-携带-转发路由协议中，当节点接收或产生了消息，先将此消息缓存于缓冲区，并携带此信息进行移动，直到它遇到合适的节点。如果相遇了合适的节点，它就向此节点转发。为了提高将消息成功传输至目的节点的概率，也采用多复本路由策略[3]。蔓延路由就是典型的多复本路由[4]。

在蔓延路由策略中，携带消息的节点只要遇到另一节点，它就将自己的消息复本传输至该节点。如果节点的缓存区足够大的话，蔓延路由能够获取低的传输时延，但这也是建立在消耗大量缓存资源的基础上。一旦节点缓存区容量不足够大时，缓存区就会溢出。因此，必须采用有效的缓存管理策略[5-8]，进而防止溢出问题。

然而，用于传统通信网络的缓存管理策略并不适用于稀疏移动自组网[9-10]。此外，现存的缓存管理策略是基于所有节点均能直接相遇的假设。显然，在稀疏移动自组网内，节点无法与网络另一部分节点直接相遇。

因此，在真实环境中，考虑了部分节点可能无法直接相遇，丢弃部分消息复本是合理。因为，这些消息复本不能提高将消息传输至目的节点的概率。然而，当网络内只有一条消息复本时，若删除此消息复本，则此消息就无法传输至目的节点。具有消息复本数越小的消息，消息也就越稀罕。因此，越稀罕的消息，就应越谨慎删除此消息复本。

为此，本文面向稀疏移动自组网，并考虑到消息的复本数，提出基于消息优先级的缓存管理算法(Buffer Management Policy based on Message Priority, BMP-MP)。BMP-MP算法将网络内拥有复本消息数越少的消息，赋予高的优先级。而缓存区优先保存优先级高的消息。在消息未被传输至目的节点前，尽可能地不让消息从网络内消失。实验数据表明，提出的BMP-MP算法能够有效地降低未传递消息率和传输时延。

1 系统模型

假定网络内有N个节点，且引用节点集V。网络内任意两个节点的相遇服从泊松分布，且分布率为λ。具体而言，两个节点ϑ、ω(ϑ,ω∈V、ω)的相遇率表示为λϑ,ω。

此外，每个节点均有缓存区存储消息，且所有节点的缓存区尺寸均为B。假定每条消息尺寸为常数，且表示1/B。因此，每个节点的缓存区能存储B条消息。

假定在时刻t，网络内的消息集表示M(t)。而节点ϑ在时刻t拥有的消息集为Mϑ(t)⊆M(t)。网络内所产生的消息可表示为Mϑ(t)⊆M(t)。

2 BMP-MP算法

2.1 消息稀罕度

BMP-MP算法在缓存区管理时，考虑了消息稀罕性。为此，引用消息稀罕度变量。假定NC(m,t)表示在时刻t，网络内拥有消息m的复本数。NC(m,t)值越小，消息的稀罕度越高。当NC(m,t)=1，则表明网络内只含一条消息复本，那此类消息称为极稀消息。一旦删除极稀消息复本，网络内再也无此消息复本[9]，此消息将从网络内消失。因此，BMP-MP算法对极稀消息赋予最高的优先权。换而方言之，稀罕度越高，消息优先权越高。

此外，在执行BMP-MP算法时，无需准确地计算NC(m,t)值，只需要判断NC(m,t)是否等于1。原因在于：BMP-MP算法给消息设置优先级时，只考虑了NC(m,t)=1和NC(m,t)≥2两种情况。换而言之，当NC(m,t)不等于1，则NC(m,t)≥2。

因此，BMP-MP算法引用委派机制(Delegation Mechanism)判断NC(m,t)值。在拥有消息m复本的节点中，只有一个节点是委派者(Delegator)，而其他节点称为辅助节点(Auxiliary node)。当Delegator将消息复本转发至另一个节点，它就决定此接收节点是否能成为继承它，成为新一轮的Delegator。

为了能识别Delegator节点，引用一个布尔变量am∈{0,1}，并将am载入每条消息m的首部。如果am=1，则该节点成为Delegator节点，否则它就成为辅助节点。

一旦产生了消息，该消息的源节点就是此消息的Delegator节点。具体而言，源节点就拥有消息m的复本，且am=1。当Delegator节点转发消息，则将接收该消息节点设为Delegator节点，而自己成为辅助节点，即自己的am设为0。

2.2 邻近集

为了提高消息的传递率，引用邻近集变量。邻近集是基于消息的目的节点。具体而言，假定消息m的目的节点为dm。邻近集表示具有消息m的复本、且能与目的节点dm相遇的节点集。

具体而言，假定节点ϑ拥有消息m的复本，且NC(m,t)=1。消息m的传递成功率取决于节点ϑ是否能与目的节点dm相遇。因此，消息m的邻近集GH(m)定义如式(1)所示：

GH(m)={ϑ|λϑ,dm≥th,ϑ∈V}

(1)

其中λϑ,dm表示节点ϑ与目的节点dm相遇概率，而th表示相遇概率阈值[10]。

如果ϑ∈GH(m)拥有极稀消息m，当节点ϑ相遇其他节点时，它就更好地拥有消息m的复本。相反，若节点ϑ不在GH(m)内，但它拥有消息m的复本，在这种情况下，当节点ϑ相遇节点ω∈GH(m)，则节点ϑ就将消息复本传输至节点ω，然后节点ϑ就从缓存区内删除消息m的复本。

2.3 消息优先级

BMP-MP算法对缓存区管理时，考虑了消息优先级。为此，对缓存区内消息进行优先级进行设置。先定义亲近Λ变量。Λm(t)表示相遇目的节点dm的所有节点集，其定义如式(2)所示：

(2)

其中Sm(t)表示在时刻t，拥有消息m的节点集。

假定这有两条消息m1、m2，且NC(m1,t)≥2、NC(m2,t)≥2。如果Λm1(t)<Λm2(t)，则消息m1的优先级高于消息m2。这是基于一个事实：如果将具有小Λm(t)的消息丢弃，则增加了将此消息传递至目的节点概率。

总之，将稀罕消息设置最高的优先级。具体而言，节点ϑ将具有NC(m,t)=1、λϑ,dm>th的消息的优先级最高，它的目的节点能够频繁地相遇节点ϑ，如图1所示。次高优先级赋予具有NC(m,t)=1、λϑ,dm≤th的消息；依次是NC(m,t)≥2、λϑ,dm>th；NC(m,t)=1、λϑ,dm≤th。而具有NC(m,t)≥2、λϑ,dm≤th的消息的优先级设为最低。

图1 节点ϑ的优先级设置

2.4 缓存区管理

缓存区管理的目的在于防止缓存溢出。当接收消息或产生了新消息，就利用缓存区管理策略，进而预防溢出问题。

首先，考虑产生新消息情况。当节点ϑ持有|Mϑ(t)|=B条消息时，它产生了新消息mnew。在这种情况下，节点ϑ必须将新产生的消息mnew与原存储的消息Mϑ(t)进行优先级比较，并从Mϑ(t)∪mnew中选择优先级最低的消息，再丢弃此消息，进而防止缓存区溢出。

若没有产生新消息，而是接收了消息。假定节点ϑ、ω在时刻t相遇，并需要交流一些消息。图2显示了它们交互消息的过程。

图2 节点ϑ、ω间消息交互过程

一旦相遇节点ω，节点ϑ就从Mϑ(t)内选择消息Fϑ,ω，再将Fϑ,ω的ID号l(Fϑ,ω)传输至节点ω。消息Fϑ,ω的传输过程取决于路由策略。若是采用蔓延路由，则Fϑ,ω=Mϑ(t)。

当节点ω接收了l(Fϑ,ω)，先判断是否满足式(3)。如果满足，则即使节点ω接收Fϑ,ω内所有消息，也不会发生溢出。为此，为了能接收Fϑ,ω消息，节点ω就将l(Fϑ,ω)再发送至ϑ。

|Fϑ,ω∪Mϑ(t)|≤B

(3)

图3 消息Hω的选择

3 数值分析

3.1 仿真场景

利用Matlab软件建立仿真平台，并考虑随机场景。在随机场景中，利用随机图构建稀罕矩阵Λ。且节点数|V|=101，同时，节点能够相遇网络内一部分节点。而消息产生率为1。对于每条消息m，它的目的节点dm从网络内随机选择。

此外，为了更好地分析BMP-MP算法，选择基于丢弃最旧的(Drop Oldest, DO)[10]、基于驱除最先拥有(evict Most Founded First, MOFO)[11]、基于全局知识的丢失策略(Global Knowledge-based Drop-Loss, GBD-L)[9]和基于全局知识的时延策略(Global Knowledge-based Drop-delay, GBD-D)[9]缓存区管理策略作为参照，并分析它们未传递消息率和平均传输时延E[TD]。而TD表示从消息的产生至此消息被传输至目的节点所消耗的时间。未传递消息率是指未传递消息数与总的消息数之比。

3.2 未传递消息率

图4分析了未传递消息率随缓存区尺寸B的变化情况，其中“Proposal”表示本文提出的BMP-MP算法。从图4可知，在缓存区尺寸B的整个变化区间内，“Proposal”算法的未传递消息率低于现存算法。原因在于：给稀罕消息设置优先级，对缓存区的管理非常有效。此外，DO和GBD-L算法的未传递消息率小于MOFO算法。这主要是因为：在随机场景中，网络更接近于同构网络。

图4 未传递消息率

3.3 传输时延

图5 传输时延

图5显示了各算法的E[TD]随缓存区尺寸B的变化情况。从图5可知，“Proposal”算法的E[TD]小于GBD-L和GBD-D算法，这些数据说明， “Proposal”算法能够有效地降低传输时延。然而，“Proposal”算法的传输时延高于MOFO算法。注意图4，MOFO算法的未传递率很高，这也说明MOFO算法只将具有小时延的消息传输至它们的目的节点。

4 结 语

针对稀疏移动自组网的存储-携带-转发路由，提出基于消息优先级的缓存管理算法BMP-MP。BMP-MP算法给每条消息赋予不同的优先级，再依据优先级决定从缓冲区内删除的顺序。实验数据表明，提出的BMP-MP算法能够有效地降低未传递概率和传输时延。