一种控制消息广播与合并策略的低开销路由算法*

任 冬，陈民华，刘顺辉

(重庆邮电大学 a.通信与信息工程学院;b.移动通信技术重庆市重点实验室，重庆 400065)

0 引 言

机会网络[1-2]是一种源节点与目的节点之间没有完整的传输路径，利用节点移动带来的相遇机会来实现源节点与目的节点通信的移动自组织网络。机会社会网络[3]是一种节点设备由人类持有的特殊网络，这种通信方式可以摆脱固定基础设施的限制，为物联网(Internet of Things,IOT)[4]的研究提供理论基础。

由于机会社会网络链路不完整，与传统的无线自组织网络相比，机会社会网络的成功率较低、时延较大。为了提高消息成功率和减少消息传输时延来使其更好地适用于现实应用场景，目前国内外有很多关于基于社区的机会社会网络多副本消息传输机制的文献[5-10]。

基于社区的消息机会传输(Community based Message Opportunity Transmission,CMOT)路由算法[11]根据节点历史访问信息来对节点进行社区划分。该算法增加ACK机制虽然可以减少消息副本进行无效的转发，节省了网络资源，但是单独发送ACK控制消息会出现网络控制开销增大的问题。基于重叠社区的消息机会转发(Message Opportunistic Forwarding based on Overlapping Communities,MOFOC)路由算法[12]是一种基于重叠社区的多副本消息路由算法，在消息到达目的节点时，目的节点需要向全网泛洪一个ACK控制消息来删除网络中的该消息副本，但只让目的节点洪泛ACK控制消息会导致因网络中消息副本删除不及时而使得网络资源浪费的问题。

为解决上述CMOT算法和MOFOC算法中所存在的网络控制开销[13]增大和网络资源浪费的问题，本文提出了一种基于广播策略的机会社会网络低开销路由算法(Low Overhead Routing Algorithm for Opportunistic Social Networks based on Broadcast Strategy,LOBS)。

1 网络模型与问题描述

1.1 网络拓扑构建

在现实社会网络中，每个人不仅单一地属于某一个社区，而且可以是多个社区的成员。例如，学生在上课时间，教学楼是他们的活动社区；在吃饭时间，食堂是他们的活动社区；在休息时间，宿舍楼是他们的活动社区。因此，网络中的节点可以属于多个社区。本文基于上述网络特征，对机会社会网络建立基于重叠社区的网络模型并给出如下定义。

定义1 网络模型：将节点数为N、社区数为m的网络定义为

(1)

定义2 等待间隔时间：网络中节点与其他节点通信结束时到该节点下一次通信开始所等待的时间。

定义3 活跃社区：节点间通信比较频繁的社区，即在活跃社区中，节点间的等待间隔时间比较短。

定义4 活跃社区集：节点所属社区中所有活跃社区的集合组成活跃社区集，若节点只属于一个社区，则该社区为此节点的活跃社区集。

1.2 前提条件

假设1：网络中每个节点都知道自己当前所处的社区。

假设2：网络中不存在自私节点和恶意节点，消息在传输过程中只要满足转发条件，节点就对消息进行转发。

1.3 问题描述

问题1：现有多副本消息传输机制(例如CMOT算法、MOFOC算法)中，当目的节点成功收到数据消息时，目的节点会产生一个ACK确认消息并通过泛洪的方式来删除网络中该数据消息的副本。但是，在目的节点成功接收数据消息时刻，只有目的节点一个节点产生ACK确认消息，这会导致网络中数据消息副本因删除不及时而产生不必要的转发，浪费了网络资源。

问题2：现有多副本消息传输机制中，当节点成功接收消息时，需要单独泛洪一个ACK消息来消除网络中的数据消息副本数，这会导致网络的开销增大。

2 LOBS算法

为解决上节所述问题，笔者提出了一种基于广播策略的机会社会网络低开销路由算法——LOBS。该算法主要包含了ACK消息快速产生机制、控制消息合并机制两种新机制，能有效减少网络中数据消息副本不必要的转发次数，以此来减少网络资源的浪费，并且缩减节点交互过程中的控制消息，以此来减少网络开销。

2.1 ACK消息快速产生机制

ACK消息快速产生机制由以下三个子机制相互关联来实现：广播数据消息机制、跨层发送ACK消息机制和跨层删除缓存消息机制。其核心思想是，在不增加额外控制开销的前提下，不仅要保证消息到达成功率不受影响，同时还要加快ACK消息的产生，以此来快速删除网络中的消息副本，从而节省网络资源。

2.1.1 广播数据消息机制

携带消息节点与消息目的节点相遇时(最后一跳转发数据消息)，节点数据链路层由原来的单播方式变为采用广播的方式传输数据帧。此时，不仅目的节点可以成功接收到该消息，携带消息节点的邻居节点也可以接收到该消息。携带消息节点的邻居节点数据链路层收到广播数据帧时，对该数据帧进行解封，将解封之后的数据消息送到网络层，并跨层通知网络层该数据消息是通过广播方式传输的。网络层收到该数据消息时，判断该消息的目的地址是否与自身地址相等，若是，则表明自身是消息目的节点，接收此数据消息；若不是，则表明这是一个已到达目的节点的数据消息，节点从自身缓存中删除该数据消息副本，从而对缓存空间进行有效管理。同时邻居节点按照数据结构记录与数据消息相对应的ACK消息的信息(SourceAddress表示数据消息的源地址，DestAddress表示数据消息的目的地址，Identify表示数据消息的标识，TTL表示当前该数据消息所剩的生存时间)。当TTL=0时，表示该数据消息的生存时间到期，此时网络中该数据消息的副本会自动被节点删除，因此每个节点从ACK消息信息列表中删除该消息的信息记录；当TTL>0时，表示数据消息生存时间还没有到期，全网可能还有该消息的副本，此时节点通过泛洪的方式发送ACK消息信息列表来删除网络中的消息副本。

通过采用广播的方式进行最后一跳数据消息的传输来快速地产生ACK消息，其作用是为了更快地删除网络中的消息副本数，从而减少节点缓存空间的占用率以及减少网络中的数据消息副本不必要的转发次数。

由于无线网络中数据链路层对于广播消息不进行确认和重传，即接收节点对于广播消息不需要进行回复。广播数据消息机制中数据消息最后一跳采用广播方式传输，而由于数据链路层不对广播消息进行ACK帧确认，因此携带消息节点无法保证目的节点是否成功接收该数据消息。为了解决这个问题，笔者提出了跨层发送ACK消息机制。

2.1.2 跨层发送ACK消息机制

目的节点数据链路层收到了该数据消息的广播帧时，将该广播帧解封后送到网络层，若网络层发现该数据消息的目的地址与自身地址相同，则表明自身为消息目的节点，此时网络层跨层通知数据链路层向携带消息节点发送ACK帧。若携带消息节点收到ACK帧，则表示消息成功到达目的节点；若携带消息节点没有收到ACK帧，则表明目的节点没有成功接收消息，携带消息节点需要继续重传该数据消息。

由于单播数据帧的情况下，目的节点数据链路层需要对收到的数据帧回复ACK帧，因此跨层发送ACK消息机制中让目的节点收到广播数据帧后也回复ACK帧的方式并没有比原来单播数据帧的方式增加节点额外控制开销。

在广播数据消息机制中提到数据消息可以被携带消息节点的邻居节点接收到，但邻居节点(除目的节点外的邻居节点)并不是刚接收到该数据消息，节点网络层就将缓存中的此数据消息删除。原因在于数据消息广播传输时，目的节点有可能没有成功接收该数据消息，若没有成功接收，则携带消息节点的邻居节点不能删除缓存中的该数据消息，以此来保证消息的投递成功率；若成功接收，则直接删除缓存中的该数据消息。因此，携带消息节点的邻居节点何时在缓存中删除该数据消息便成为一个需要解决的问题。为了解决这个问题，笔者提出了跨层删除缓存消息机制。

2.1.3 跨层删除缓存消息机制

携带消息节点的邻居节点在接收到该数据消息之后，节点数据链路层继续监听携带消息节点是否发送了重传帧。若邻居节点的数据链路层在规定的重传时间内收到的帧数(重传帧和错帧)小于3，则认为该数据消息发送成功，数据链路层跨层通知网络层删除缓存中该数据消息，同时在ACK消息信息列表中记录相应的数据消息信息；否则不处理缓存中的该数据消息。

ACK消息快速产生机制具体实现流程如图1所示。该机制实现了在不增加额外控制开销的前提下，不仅保证了消息到达成功率不受影响，同时还加快了ACK消息的产生，使得删除网络中的消息副本速度更快，减少了消息副本不必要的转发次数，从而节省了网络资源。

图1 ACK消息快速产生机制流程图

2.2 控制消息合并机制

现有基于社区的多副本消息传输机制中相遇节点的通信过程如图2所示。当前节点与相遇节点在收到对方的Hello消息后，双方会单独发送一个ACK信息列表(含有多个数据消息的ACK信息)消息和一个SV信息列表消息给对方，此交互过程存在冗余。为了减少网络控制开销，笔者提出了控制消息合并机制。

图2 相遇节点交互模型

该机制的思想是让ACK消息信息列表与SV信息列表进行融合传输，以此来减少控制消息数，从而减少控制开销。机制提出的依据是通过分析ACK消息信息列表可知其存储结构与SV信息列表相同，ACK消息信息列表存储结构如图2所示，SV列表包含源地址(SourceAddress)字段、目的地址(DestAddress)字段、消息标识(Identify)。如图3所示为改进的相遇节点通信过程，ACK消息信息列表与SV信息列表进行合并传输，这样节点在一次交互过程中节省了单独发送ACK列表消息所需的头部控制字段，从而减少了网络控制开销。图4所示为ACK列表与SV列表合并后的包格式信息。

图3 改进的相遇节点交互过程

图4 列表合并后的包格式信息

3 LOBS算法操作和性能分析

3.1 算法操作

LOBS算法的具体操作步骤如下：

Step1 节点A收到节点B的Hello消息时，则表示节点B与节点A相遇，此时节点B是节点A的邻居节点，节点A记录自身的等待间隔时间以及当前的社区号并更新自身所属的活跃社区集合。

Step2 若节点A的缓存中有消息目的节点是节点B的消息，则执行在不增加控制开销的前提下ACK消息快速产生机制，以广播的方式传输这些数据消息，同时更新自身的SVA列表。节点B收到这些数据消息时，更新自身的ACKB消息信息列表。

Step3 节点A采用控制消息合并机制向节点B发送SVA列表和ACKA消息信息列表。同时，节点A发送自身所属的活跃社区集合信息。

Step4 节点B收到节点A的ACKA消息信息列表后，更新自身的SVB列表，同时更新自身的ACKB消息信息列表。接着，根据节点A的SVA列表摘要信息和所属活跃社区集合信息，节点B向节点A发送自身SVB列表中没有而SVA列表中含有的摘要信息所对应的消息投递概率或者间接集合活跃度信息。

Step5 节点A收到节点B的投递概率列表信息和间接集合活跃度列表信息后，通过结合节点B所属的活跃社区集合，节点A将满足转发条件的数据消息转发给节点B。

Step6 节点B收到节点A转发的数据消息后，对数据消息进行存储、携带，同时更新自身的SVB列表。

以上是节点A收到节点B的Hello消息后，双方节点所执行的操作流程。同理，节点B收到节点A的Hello消息后，也执行相同的操作，以此来完成双方节点数据消息的转发。

3.2 性能分析

新机制采用ACK消息快速产生机制来快速产生ACK消息，从而有效地减少网络中的数据消息副本不必要的转发次数，节省了网络资源；采用控制消息合并机制来对控制消息进行合并，从而减少了消息交互过程中的控制开销。下面对新机制进行理论分析。

引理1：与现有的多副本消息传输机制相比，LOBS协议删除网络中的消息副本速度更快。

证明：假设网络中的节点数为N，每个节点的平均邻居节点数为m(m>1)，那么其中一个节点洪泛一个ACK消息时，假设ACK消息转发了norig次之后，全网络的节点都可以接收到该ACK消息，此时,

(2)

因此，可以求出ACK消息的转发次数

(3)

采用ACK消息快速产生机制之后，假设ACK消息转发了nnew次之后，全网络的节点都可以接收到该ACK消息，此时，

(4)

因此，ACK消息的转发次数为

(5)

因此，

nnew

(6)

证毕。

引理2：与现有的多副本消息传输机制相比，LOBS协议的网络控制开销更低。

证明：假设网络中的节点数为N，每个节点除去发送SV列表、ACK列表消息之外的其他控制消息所消耗的能量总和为K，节点发送控制消息每比特需要的能耗为δ，SV列表一共有a比特，ACK列表一共有b比特，发送控制消息头部信息所需的能耗为β，因此网络整体控制开销为

Eorig=N(K+aδ+β+bδ+β)=N[K+(a+b)δ+2β] 。

(7)

采用控制消息合并机制之后，网路整体控制开销为

Enew=N[K+(a+b)δ+β] 。

(8)

因此，

Enew

(9)

证毕。

4 仿真分析

本文采用OPNET14.5网络仿真软件对LOBS算法的消息到达成功率、平均跳数、平均传输时延、归一化控制开销和网络吞吐量的网络性能进行仿真验证，并将仿真结果同CMOT算法和MOFOC算法的仿真结果进行对比分析。仿真参数设置见表1。

表1 仿真参数设置

4.1 消息到达成功率

消息到达成功率是指所有目的节点接收到的数据总量R与所有源节点产生的数据总数S的比值，计算公式为

η=R/S。

(10)

如图5所示，随着消息生存时间增大，消息到达成功率先增大后减小。消息到达成功率先增大的原因是由于节点的缓存空间足够，增大消息的生存时间，可以减少网络中因生存时间不足而被节点丢弃的消息个数；消息到达成功率后减小的原因是随着消息生存时间的增加，网络中的消息副本数增多，导致部分节点因缓存空间不足而删除缓存中的消息，从而造成消息到达成功率减小。从图中还可以看出，LOBS协议和MOFOC协议相较于CMOT协议的消息到达成功率更高，原因是LOBS协议和MOFOC协议是基于重叠社区划分节点社区归属，相比于单社区划分的CMOT协议，节点社区划分更合理，因此消息到达成功率更高。在消息生存时间150～300 s时，LOBS协议和MOFOC协议消息到达率相近。原因是LOBS和MOFOC协议社区划分机制都是基于重叠社区，在消息生存时间较小时，消息副本较少，节点缓存空间充足，所以两协议消息到达率相近。在消息生存时间300～400 s时，LOBS协议比MOFOC协议的消息到达成功率稍高，原因是LOBS协议采用ACK消息快速产生机制可以更快地删除网络中已到达目的节点的消息副本，从而快速清理了节点缓存空间，减少了节点因缓存不足而删除缓存消息的个数。

图5 消息到达成功率

4.2 平均跳数

平均跳数指数据消息成功传输到目的节点所需经过的平均节点个数，其计算公式为

(11)

式中：D表示数据消息到达目的节点的个数，Hopi表示第i个数据消息到达目的节点所经过的节点个数。

如图6所示，LOBS协议与MOFOC协议的平均跳数比COMT协议多，其原因是COMT协议在社区内传输消息时采用改进的PROPHET算法，只选择目的节点的一跳节点作为转发节点，因此减少了消息转发跳数。LOBS协议与MOFOC协议的平均跳数相近，原因是LOBS协议的控制消息合并机制节省了消息头部控制开销，但是对消息的转发跳数没有影响；ACK消息快速产生机制快速地删除了网络中无用消息副本传输数量，但是对于消息到达目的节点的转发跳数几乎没有影响。

图6 平均跳数

4.3 平均传输时延

平均传输时延表示数据消息成功传输到目的节点所需要的平均时间，其计算公式是

(12)

式中：D表示数据消息到达目的节点的个数,Ti表示第i个消息到达目的节点的时延。

如图7所示，随着消息生存时间增大，消息平均传输时延先增大后减小。消息平均传输时延先增大的原因是节点在缓存空间足够的情况下，消息生存时间越大，投递率低的消息在缓存中生存的时间也就越久；后减小的原因是网络中部分节点缓存空间不足，节点需要删除缓存中投递率低的消息来释放缓存空间，从而导致平均传输时延减小。从图中可以看出，LOBS协议和MOFOC协议相较于CMOT协议的平均传输时延较小，原因是：LOBS协议和MOFOC协议是基于重叠社区划分节点社区归属，节点社区划分更合理；CMOT协议在社区内采用改进的PROPHET算法来限制消息副本数量，这会导致消息时延增加。在消息生存时间300 s之前LOBS和MOFOC平均时延相近的原因是由于节点的缓存空间足够，消息到达环境相同，故两种算法在生存时间较短时平均传输时延基本一致。在300 s后LOBS协议比MOFOC协议平均传输时延大的原因是采用ACK消息快速产生机制快速地清理了节点缓存中已到达目的节点的消息副本，减少了节点因缓存不足而删除缓存中投递率低的消息数，从而投递率较低的消息得到转发，而这些投递率较低的消息传输时延也比较大，因此增加了平均传输时延。

图7 平均传输时延

4.4 归一化控制开销

归一化控制开销指网络中节点发送的控制消息总比特数与控制消息和到达目的节点数据消息总比特数的比值，其值越大表示网络开销也越大，计算公式是

C=MC/(MC+MD) 。

(13)

式中：MC表示网络中控制消息总比特数，MD表示网络中到达目的节点数据消息总比特数。

如图8所示，随着消息生存时间增大，归一化控制开销先减少后增大。归一化控制开销先减少的原因是消息生存时间增大会提高消息到达成功率，从而增加了网络中到达目的节点的数据消息总数，而节点的控制消息总数只与节点间的相遇次数有关，与消息生存时间无关，因此在消息生存时间增大的过程中，归一化控制开销在不断减小；后增大的原因是消息生存时间在300～400 s的时候，网络中部分节点缓存空间不足，导致消息到达成功率降低，从而使得归一化控制开销增大。从图中可以看出，与CMOT协议和MOFOC协议相比，LOBS协议的归一化控制开销更低，主要原因是：在不增加控制开销的前提下ACK消息快速产生机制可以快速地删除网络中无用消息副本传输数量，减少了无用消息副本的转发次数，从而减少了控制消息总比特数，因此降低了网络控制开销；控制消息合并机制减少了控制消息总数，节省了消息头部控制开销，从而降低了网络控制开销。

图8 归一化控制开销

4.5 网络吞吐量

网络吞吐量指单位时间内网络中成功传输数据消息的比特数，其计算公式为

Throughput=P/(Tend-Tstart) 。

(14)

式中：P表示数据消息到达目的节点的总比特数，Tstart表示网络仿真开始时间，Tend表示网络仿真结束时间。

如图9所示，随着消息生存时间增大，网络吞吐量先增大后减小。吞吐量先增大的原因是消息生存时间增大，成功传输到目的节点的数据消息就增多，从而使得网络吞吐量增大；后减小的原因是网络中部分节点缓存空间不足，导致节点因释放缓存空间而删除缓存消息，从而成功传输到目的节点的数据消息数就会减少。从图中可以看出，LOBS协议的网络吞吐量高于CMOT协议和MOFOC协议，主要原因是LOBS协议采用在不增加控制开销的前提下ACK消息快速产生机制可以更加快速地删除网络中已到达目的节点的消息副本，从而快速地清理了节点缓存空间，减少了节点因缓存不足而删除缓存消息的个数，从而成功传输到目的节点的消息数就增多。

图9 网络吞吐量

5 结束语

本文针对现有机会社会网络多副本消息传输机制中网络控制开销较大和网络资源浪费的问题，提出了一种基于广播策略的机会社会网络低开销路由算法。该算法由ACK消息快速产生机制和控制消息合并机制两种新机制组成。通过采用ACK消息快速产生机制来快速删除网络中已到达消息目的节点的消息副本，减少此类消息不必要的转发次数，使网络中投递率较低的消息也得到有效转发，从而节省了网络资源；采用控制消息合并机制缩减了消息交互过程中的控制开销，网络性能得到有效提升。

由于机会社会网络中消息到达成功率仍较低，因此，今后的工作是对机会社会网络的路由转发策略进行研究。