陈启航，马大玮，张世伟，肖玲娜，李成俊

（中国人民解放军陆军工程大学通信士官学校，重庆 400035）

0 引言

机会网络是一种基于“存储—携带—转发”机制，通过中继节点携带消息副本，等待与消息目的节点建立连接的机会，实现消息可靠传输的一种自组织网络[1]。相较于移动自组网（Mobile Ad hoc Network，MANET）[2]，机会路由不受限于在节点间时刻维护一条稳定通信链路的条件，因此作为野生动物追踪[3]、灾害后通信[4]、战场通信[5]等挑战性环境中的可靠通信方案被广泛研究。

路由策略问题一直是机会网络的研究热点，较为经典的路由策略有传染病（Epidemic）[6]、喷射等待（Spray and Wait，SAW）[7]等。上述方案通过多消息副本泛洪的方式来增加目的节点接收到消息的概率，但如何实现消息副本的有效分配，仍然是机会网络领域中的一项研究热点问题。

本文提出了一种基于地理位置信息的机会网络消息副本分配方案（Geographic Location Message Copy Allocation，GLMCA）。本文的贡献有：

（1）GLMCA 利用有限的地理位置信息，根据消息副本分配算法，使有限的消息副本在网络中快速扩散，并能够有效减少消息转发的盲目性；

（2）提出在当节点仅能够获取自身路由信息时，通过周期性与事件性两种路由维护模式与邻居节点建立位置信息表；

（3）将GLMCA 与Epidemic 和SAW 协议进行比较，GLMCA 算法在短时间内（5 min 内）具有较高的投递率，在节点密度稀疏的情况下能发挥较好的性能。

在第1 节中，将介绍前期进行的相关工作；第2 节将对GLMCA 的算法流程及细节设计进行描述；第3 节通过MATLAB 仿真平台进行仿真分析；第4节进行总结。

1 相关工作

在机会路由中，消息的源节点通过生成大量的消息副本交与中继节点携带，以达到提升消息可靠性的目的，如Epidemic 策略中，消息源节点将消息副本交付给每一个能够接触到的中继节点。这种消息副本的分配方式在理论上来说，若不考虑缓存因素，能够在节点密度稀疏的场景下实现极高的消息交付率；但是在现实应用场景中，这种理想化的节点缓存环境难以实现[8]。为了避免无效消息副本盲目泛洪造成的通信资源浪费，学者提出了限制消息副本生成数量的消息分配策略，其中，较为经典的就是SAW 策略。在SAW 策略中，消息副本的分配分为喷射（Spray）和等待（Wait）两个阶段。在Spray 阶段中，消息源节点间将生成L份（L＞1）消息副本，并将消息副本分配给其接触到的其他节点；当在Spray 阶段中源节点未能将消息传递给目的节点，且所有接收到消息副本的中继节点和源节点内仅有一个消息副本时，进入Wait 阶段，此时含有消息副本的节点将不做任何操作，等待与目的节点接触的机会进行消息传输[9]。

随着卫星导航定位系统民用的广泛应用，用户能够通过手持终端（智能手机、智能手表、平板电脑等）或车载终端（车载导航系统）获取自身甚至其他节点的位置信息，在此基础上，基于地理位置信息辅助的移动自组网路由策略相继被提出，如位置辅助路由（Location Aided Routing，LAR）[10]、贪婪周边无状态路由（Greedy Perimeter Stateless Routing，GPSR）[11]等。许多学者尝试在机会网络的消息副本分配策略上引入地理位置信息，实现消息副本能够尽可能分配到更有机会与目的节点接触的高效节点，提升消息交付的成功率。在文献[12]中，作者将GPSR 策略与机会路由相融合，当消息在传输过程中遭遇路由空洞[13]时，作者认为按传统GPSR 通过“右手法则”重新选择的中继节点并不是最优的中继节点；因此在面临路由空洞时，距离目的节点直线距离最近的节点将保存消息等待与目的节点建立最短连接的机会。相较于传统GPSR 和机会路由策略，上述方案的提出虽然进行了一定程度的优化，但在挑战性环境下，消息源节点极有可能无法获得目的节点的地理位置信息或出现目的节点地理位置信息过期失效的情况，这种单消息副本转发的模式的性能会受到极大的限制。文献[14]提出了一种基于地理位置信息辅助的多副本SAW 策略，该策略在SAW 的Wait 阶段中加入消息转发机制，处于Wait 阶段的中继节点将与接触到的其他节点交换比较位置信息，中继节点将消息副本转发给不携带副本的高效节点，形成新的中继节点。这种副本转发策略使得消息副本不断向高效转发节点靠拢，避免了副本盲目分配至孤僻节点的问题，但也给高效节点增加了更多的消息负载。在文献[15]中，作者在源节点副本分配策略上参考I.CEpidemic[16]策略中根据邻居节点选择最大张角的知识，通过位置信息选择张角最大的两个邻居节点作为分配副本的中继节点。

基于上述研究，本文提出了一种基于地理位置信息的机会网络消息副本分配策略（GLMCA）。该策略的特点有：

（1）邻居节点间互相交换自身位置信息，源节点产生的消息副本能够按最短距离扩散至指定位置；

（2）限制源节点生成消息副本的数量；

（3）根据节点位置信息，按划分角度方向分配副本。

2 GLMCA 模型设计

假设在间歇性连接网络[17]中各节点能够获取到自身位置信息，当不考虑节点能量消耗及缓存资源时，GLMCA 策略将进行下述操作。

GLMCA 策略分为3 个阶段：邻接节点信息维护阶段、消息副本分配阶段和虚拟源节点消息转发阶段。各阶段间关系如图1 所示。

图1 GLMCA 阶段关系

2.1 邻接节点信息维护阶段

在邻接节点信息维护阶段中，网络中各节点与邻居节点交换控制信息记为控制消息（Control Message，CM），并根据接收到的控制信息在节点自身建立并维护一个邻接节点位置信息表。

如表1 所示，邻接节点位置信息表内包含有邻接节点的标识ID、X和Y坐标以及一个位置信息剩余保留时间记为TTL_g。当表内位置信息存储的时间到达TTL_g时，该条位置信息将被丢弃以减少冗余信息。

表1 邻接节点位置信息

邻接节点信息维护阶段的触发方式分为周期性触发和事件性触发两种模式，在不同触发模式下，具有不同的发送控制信息的节点与控制信息字段。

（1）周期性触发：该模式下，相邻的一跳节点间将交换控制信息CM_p，CM_p字段如图2所示。

图2 CM_ p 字段

接收到CM_p的节点根据字段内容更新维护邻接节点位置信息表。

与自组网协议中的路由收敛机制不同的是，CM_p属于弹性信息，即不需要对位置信息表进行实时的维护，不同节点可以根据自身能耗状态合理设置CM_p的发送周期。

（2）事件性触发：该模式下，虚拟源节点向相邻的一跳节点发送控制信息CM_i，CM_i字段如图3所示。

图3 CM_i 字段

CM_i信息中加入了一个征询信息，使节点在接收到CM_i时，将回复自身位置信息表信息。

2.2 消息副本分配阶段

当消息源节点产生消息时，源节点将在自身邻接节点位置信息表内检查是否存在目的节点的位置信息，若存在则将消息直接转发给目的节点，否则将生成N个消息副本，并按算法分配的方向矢量选择邻接节点作为转发的中继节点，如图4 所示。

图4 源节点副本分配流程

在这里本文加入了方向矢量的概念，如图5所示，方向矢量的作用是作为选择中继节点的一个指针，消息副本只会转发给方向矢量范围内的中继节点。

如图5 所示，消息源节点S 一跳通信范围内有A、B、C、D，4 个节点，当源节点需要转发消息副本时，则根据方向矢量V的方向，选择节点A 作为转发消息的中继节点。

方向矢量分配算法：假设消息节点位置坐标为(X0,Y0)，其周围n个邻接节点的坐标集为{(X1,Y1),(X2,Y2),…,(Xn,Yn)}，并根据式（1）得出矢量方向集合{V1,V2,…,Vn}，则有：

式中：Vi为第i个邻接节点的矢量方向；(Xi,Yi)为第i个邻接节点的位置坐标，i∈[1,n]。

记消息源节点生成N个副本，建立参考集合求得矢量方向距离集合{|V|}，取最大值|Vmax|对应的方向为参考方向，若存在多个最大值，则在其中随机选取一个为参考方向。根据式（2）得出矢量方向与参考方向夹角集合{∂1,∂2,…,∂n}，n为一跳内邻居节点数量。

式中：i∈[1,n]。

选择与参考集合中最为接近且差值在区间[-θ,θ]内的夹角的方向矢量为消息副本的转发方向。

如图6 所示，当消息源节点产生4个消息副本时，参考方向为一跳范围内最远距离节点的方向（图中为节点A 的方向），而后根据分配算法，将副本分配给节点A、B、C、E 作为中继节点。

图6 N=4 时算法演示

当中继节点接收到副本时，将进行以下判断：

（1）中继节点一跳内邻居节点是否存在消息目的节点；

（2）消息传递跳数是否达到传递阈值；

（3）矢量方向的差值区间内是否存在邻居节点。

当邻居节点内存在目的节点时，由中继节点将消息传输给目的节点，否则需要进行下两步判断。在这里提出了一个传递阈值的概念，当节点密度大时，随着跳数的增加，副本转发方向的误差将无限增大，因此需要设计一个传递阈值。本文假设阈值为3 跳，当副本转发超过3 跳且仍未交付给目的节点时，消息副本的第3 跳中继节点则转为虚拟源节点，进入虚拟源节点模式；若副本转发次数未超过传递阈值，中继节点需要判断在分配的方向差值区间内是否存在下一跳节点，若存在则向夹角最接近分配方向的节点转发消息，否则中继节点则转为虚拟源节点，进入虚拟源节点模式，流程如图7 所示。

图7 中继节点副本分配流程

2.3 虚拟源节点消息转发阶段

当进入虚拟源节点消息转发阶段时，虚拟源节点每当遇到新的邻居节点时，将按邻接节点信息维护阶段中事件性触发邻接节点维护模式。虚拟源节点将检查其邻居节点是否为消息的目的节点，若为目的节点则进行消息的发送，若不是目的节点，则检查其位置信息表内是否存在目的节点的位置信息，若存在，则将消息转发给邻居节点实现消息的传递，否则继续等待新的事件触发或者消息到达生存时间后被节点丢弃。

3 仿真分析

本文在MATLAB 平台上实现了GLMCA 算法的仿真，相较于其他仿真平台如NS、ONE 等，MATLAB 通过逐帧切换的方式能够更好地模拟网络中节点间拓扑变化，其仿真结果在相对意义上与其他仿真平台相同。仿真参数如表2 所示。

表2 仿真参数

当不考虑节点缓存和节点能量时，假设SAW和GLMCA 消息产生副本数为4，GLMCA 传递阈值为3，在不同节点密度下，对Epidemic、SAW 和GLMCA 3 种策略的消息投递率、平均时延和网络开销[18]进行仿真分析。

3.1 消息投递率

消息投递率是成功投递消息数和产生消息数的比值。消息投递率的仿真结果如图8 所示。

图8 消息投递率对比

如图8 所示，在短时间（5 min）内，机会路由消息投递率普遍不高，这是由于短时间内中继节点移动性受限，无法将消息迅速携带或者扩散，其中GLMCA 和SAW 算法在节点数量较低时相较于Epidemic 算法具有较好的消息投递率表现，尤其是当节点数量小于40 个时，CLMCA 算法的投递率比SAW 算法高了60%，比Epidemic 算法高了100%。当网络中节点数量在（0,180）区间内时，GLMCA算法的投递率一直高于其他两种算法，当节点数高于200 时，Epidemic 算法凭借消息副本无限制泛洪的优势，其消息投递率突变上升，此时GLMCA 算法投递率仍高于SAW 算法。

3.2 平均时延

平均时延是消息成功交付所需要时间的平均值。平均时延的仿真结果如图9 所示。

如图9 所示，由于节点移动性的限制，绝大部分消息的交付时间在1 s 左右，即源节点直接交付。这是由于在有限的时间内，消息的副本无法迅速扩散。其中，表现最为突出的算法为SAW 算法，然而由于该算法限制了消息副本的数量，使得其无法像Epidemic 算法那样随着节点密度的增高将消息副本快速在网络中扩散，当节点移动性低时，其副本转发模式的盲目性使得中继节点无法将副本快速携带“远离”源节点。而GLMCA 算法在消息副本转发的设计上，使得消息副本在中继节点中仍能够进行多次转发，并根据位置信息避免了消息副本转发的盲目性。

图9 平均时延对比

3.3 网络开销

网络开销是冗余消息副本数与成功投递消息数的比值，其仿真结果如图10 所示。

图10 网络开销对比

如图10 所示，当节点数较低时，3 种算法的网络开销相差不大。随着节点数量的增加，Epidemic算法开销逐渐上升，当节点数量为240 时，其开销是GLMCA 算法的1.82 倍。

由于限制了网络中消息副本泛洪的数量，GLMCA 算法和SAW 算法的网络开销较为稳定，并且由于GLMCA 算法的中继节点依旧能够进行有限次的消息副本转发，因此相较于SAW 算法，在短时间内将消息副本扩散的概率更大，而SAW 算法由于转发的盲目性以及中继节点无法转发消息副本的局限性，使得其平均开销低于GLMCA算法4.55%。

4 结语

本文提出了一种基于地理位置信息的机会网络消息副本分配策略（GLMCA），并按邻接信息维护模式、消息副本分配模式和虚拟源节点模式3 种模式对GLMCA 策略进行设计。根据设计，GLMCA 策略能够利用节点自身位置信息，将产生消息的副本按设计的消息副本分配算法短时间内扩散至网络中生成的虚拟源节点，虚拟源节点根据拓扑变化主动检测邻接节点位置信息，进一步扩大了对目的节点的检测范围。通过与经典机会路由策略Epidemic 和SAW 的仿真对比发现，GLMCA 算法在短时间内具有较好的消息投递率，当节点密度稀疏时，能够有效利用中继节点转发来提升通信可靠性，并在节点密度提升时，能够保持较低的网络开销。