机会网络剩余路径投递时间估计方法性能分析*

王益亮，姜胜明，曹 军

(上海海事大学 信息工程学院，上海 201306)

机会网络剩余路径投递时间估计方法性能分析*

王益亮，姜胜明，曹 军

(上海海事大学 信息工程学院，上海 201306)

差分队列服务是一种以包为粒度的队列调度算法，其剩余路径投递时间估计方法的好坏，将显著影响其在机会网络这种链路连通性低、拓扑变化频繁环境下的性能。现有的剩余路径投递时间估计方法尚未验证其在机会网络中的性能。文章比较差分队列服务与最早截止期优先算法，通过仿真测试了一种基于历史信息有效性的剩余路径投递时间估计方法在机会网络场景中的性能。实验证明应用该方法能有效地提高传输成功率，也导致平均端到端时延的变化幅度更大。

差分队列服务；机会网络；剩余路径投递时间；最早截止期优先

0 引言

在机会网络中，为实现包粒度的服务质量，文献[1]提出差分队列服务(Differentiated Queueing Service, DQS)算法。DQS的设计基于以下前提：网络中的所有数据分组都来自于某种类型的应用，每种类型的应用都具有一个特定的最大端到端时延，即这种类型的应用中所有数据分组在链路上的最长生存时间，作为该数据分组的服务质量(Quality of Service, QoS)需求。所以，每当节点新收到一个数据分组，首先需要检查分组是否仍在其生存时间内，如果不在，节点可立即丢弃该数据分组，因为这个数据分组已经无法满足其自身的QoS需求，丢弃该分组可以节约网络资源。如果在，该算法就要估计该分组在剩余路径上的传播时延，即估计剩余路径投递时间，再结合数据分组自身生存时间的QoS需求，来决定该分组可容忍的最迟离开本节点的时间。然后该时间将被视为DQS调度算法所参考转发优先级的指标，根据最迟离开时刻从早到晚的原则将数据分组插入到队列中相应位置。

因此，剩余路径投递时间估计方法的性能状况对DQS有重要意义。文献[2]提出了几种应用于DQS的方法，却缺乏性能方面的验证，不能够准确衡量方法在机会网络环境中的性能表现。本文将文献[2]提出的方法应用于DQS，并对比改进后的最早截止期优先(Earliest Deadline First, EDF)算法进行仿真验证并分析其性能。

1 机会网络与场景设计简介

文献[3]中对机会网络给出了一个描述性的定义，认为机会网络是一种源节点和目的节点之间不需要存在完整链路，而是利用节点移动所带来的相遇机会实现通信的自组织网络。具体表现形式就是，机会网络中节点依靠移动形成通信机会逐跳地传输消息，以“存储-携带-转发”的路由模式实现节点间通信。

而当前在机会网络路由协议[4]方面的研究进展缓慢，本文将使用AODV路由协议：以节点移动性以及节点数量的变化来模拟链路连通性低、拓扑变化频繁的机会网络场景。以节点自身的队列存储数据包并携带数据包在移动中寻找下一跳的方式来模拟机会网络“存储-携带-转发”场景。以不同端到端时延的数据包来模拟机会网络中不同的应用业务类型。

2 相关方法与实现介绍

2.1 差分队列服务相关方法

2.1.1 基于半衰期的历史信息有效性计算方法

该方法是根据一条信息的登记时间计算其在当前时间的信息有效性，历史信息有效性是指在当前时间，一个历史信息用于预测或估计时所具有的有用价值。信息有效性的数值范围是(0,1)，自信息登记时刻起，其有效性每经过一个半衰期时间减半。

设网络场景的面积为r,单位：m2,网络节点的平均通信半径为l,单位:m,网络节点的平均移动速度为s,单位:m/s,网络系统中节点个数为n，半衰期时间λ的计算公式如下：

(1)

信息有效性v的计算公式如下：

(2)

其中，τn表示该信息的登记时间m距离当前时间tn的时长，即τn=tn-m。

在实现的过程中，网络节点记录当前时间与数据分组在源节点的生成时间之差，作为一个历史信息记录，即该节点与源节点间路径上的历史实际投递时间，从源节点到当前节点路径的相反方向定义为反向路径。那么当有数据分组经过该节点到达那个源节点时，此记录可作为该分组的一次剩余路径时间。

2.1.2 无需发送顺向探测包的剩余路径投递时间估计

(3)

其中，τd,j代表保存在该节点上的从反向路径d节点到本节点的第j个历史实际投递时间，vd,j代表反向路径历史实际投递时间τd,j根据2.1.1节方法所计算的信息有效性。

在实现过程中，数据分组需在头部携带两个字段：该数据分组的最大端到端时延与在源节点的生成时间。数据分组离开时间等于数据分组生成时间加上其最大端到端时延，并减去估计的剩余路径时间，由此，DQS判断数据分组的紧急程度考虑到了数据分组的端到端时延需求。节点依据数据分组的离开时间进入队列，使得紧急的数据分组排在队列前面，优先转发。

2.2 最早截止期优先调度算法

EDF[5]是一种动态优先级调度算法，基本原理是：将所有的业务分成不同的流，依据数据包所属的业务类型，在每个数据包到达时间的基础上增加一个静态时间期限值，调度器则以此值作为依据，每次发送该值最小的数据包。业务流的优先级越高，相应的数据包的期限值越小，得到优先服务的概率也就越大。

在本实验中，所有数据分组都包含了其最大端到端时延要求，为体现公平性，同时根据文献[6]，对EDF进行有效的队列管理，对网络性能的提升具有相当大的作用。于是对EDF进行改进，添加了缓存准入控制，丢弃超出时延的分组，提高了网络利用率。

在实现的过程中，数据分组的本地存活时间为其端到端时延值的一半，这个本地存活时间即作为一个静态时间期限，数据分组离开时间等于当前时间加上本地存活时间。节点依据数据分组离开时间加入队列。

需要说明的是，这时数据分组的端到端时延值仅代表不同类型的业务流量，EDF并没有考虑数据分组的端到端时延需求，这也是与DQS相关方法差异明显的地方。

3 仿真和结果分析

3.1 仿真场景及参数

本文所有实验使用的仿真平台是SNT公司所开发的EXATA。通过考察传输成功率、平均传输时延来测试DQS与EDF在不同场景下的性能表现。其中，传输成功率按如下公式计算：

(4)

平均传输时延按下式计算：

(5)

本文分3个场景，场景基本参数如表1所示。

表1 场景基本参数

场景1：考察DQS与EDF在节点移动速度变化时，其速度与传输成功率和平均传输时延的关系。表2为节点移动速度变化参数表。

表2 节点移动速度变化参数表

场景2：考察DQS与EDF在节点数量变化时，其节点数量与传输成功率和平均传输时延的关系。节点数量变化参数如表3。

表3 节点数量变化参数表

场景3：考察DQS与EDF在节点发送不同端到端时延的数据包时，其端到端时延值与传输成功率和平均传输时延的关系。相关参数如表4所示。

表4 节点发送不同端到端时延的数据包参数表

3.2 仿真结果

如图1，在DQS与EDF策略下传输成功率都是先上升后下降的趋势，DQS的传输成功率相对于EDF略有提升，当节点移动速度为2 m/s～6 m/s时，传输成功率处于上升阶段，提升最为明显。当速度进一步增加时，网络动态性增强，拓扑剧烈变化，DQS性能下降明显，且性能优势不明显。但相对于EDF，DQS依然有良好的性能。

图1 移动速度与传输成功率的关系

如图2，DQS与EDF相比，DQS的平均传输时延变化范围要略大一些，并且在多数情况下略高于EDF。这是由于DQS考虑数据分组端到端的时延特征，能够对更紧急的数据分组提供优先级更高的服务，从而相对紧急程度较低的分组可在队列中停留更久一点。平均传输时延呈现出先增大再减小的特征，在速度较小时，节点通信机会少，随着速度的增加，通信机会增多，节点队列中缓存的数据分组数增大，使得队列时延增大，从而一定程度上增大了平均传输时延，但是速度进一步增大，拓扑变化剧烈，队列中的分组无法在短暂的通信时间内转发，使得大量分组未能被目的节点成功接收。

图2 移动速度与平均传输时延的关系

如图3，同样大小的场景，随着节点数量的增加节点密度自然会增大，此时网络中的传输成功率提高。DQS与EDF相比传输成功率略有提高，节点数由少到多，DQS优势呈上升趋势，在节点数为21个时，DQS与EDF相比优势最为明显。但是当节点个数更多时，DQS优势开始下降。最初节点数量较少时，节点相遇机会较少，无法满足数据分组的端到端时延需求。随着节点数量增多，通信质量得到改善，传输成功率持续提高，但是在节点密度较大时，无线信道冲突加剧。由于使用的是AODV路由协议，路由变动频繁，这时难以体现机会网络的场景。文献[7]指出，如果在节点间不依赖完整的传播路径，而是机会性地选择下一跳，能提升网络分组最终到达目标节点的概率。

图3 节点数量与传输成功率的关系

如图4，节点数量与平均传输时延的关系不是特别明显，总体而言，DQS平均传输时延的波动范围要大一些。结合图3，大致上，传输成功率提高的同时，平均传输时延也在增大。节点数量的增加增大了节点的相遇机会，提高了通信质量，队列利用率逐步提高，当节点较密集时，平均传输时延的增大幅度较小，而传输成功率增大幅度较大。

图4 节点数量与平均传输时延的关系

如图5，文献[8]通过理论推导和实验证明了当允许网络节点移动时，在增加数据分组传输时延的前提下，可以提高整个网络中的传输成功率。当数据分组平均端到端时延值为50 ms～200 ms时，其传输成功率显著提高；当数据分组平均端到端时延值继续增大，其传输成功率提升幅度减小；数据分组平均端到端时延值为300 ms时，DQS相对于EDF取得最大优势。当数据分组的平均端到端时延较小时，大量的分组因无法满足其平均端到端时延需求而被中间节点丢弃，随着数据分组平均端到端时延值增大，丢弃量下降，队列利用率提高，提高了传输成功率。但是，不断加大数据分组的平均端到端时延对传输成功率的提升作用，也会随着网络瓶颈的到来而受限。

图5 平均端到端时延与传输成功率的关系

如图6，增大数据分组的平均端到端时延，有更多的数据分组不再因其最大生存时间到期而被丢弃，会继续等待转发机会，因此网络的平均传输时延增大了。DQS与EDF相比，其平均传输时延普遍较大，平均传输时延范围要更大一些。DQS考虑到数据分组的端到端时延需求，对更紧急的数据分组提供更优先的服务，比如，尽管有的数据分组其端到端时延值较小，但是其剩余路径时间短，DQS并不一定为其提供优先服务，可能使其在队列中停留更久一点，以便为更紧急的数据分组提供服务，因此，DQS提高了传输成功率，也一定程度上增大了平均传输时延。

图6 平均端到端时延与平均传输时延的关系

4 结论

通过仿真实验，应用了基于半衰期的历史信息有效性计算方法与无需发送顺向探测包的剩余路径投递时间估计方法的DQS，对比改进后的EDF，传输成功率有效提高，传输时延变化范围更大，并有增大传输时延的趋势。

本实验中，由于使用的是AODV路由协议，使得难以高效适应机会网络场景，DQS性能受到一定影响。实验中半衰期值是由场景全局参数计算得来，总体而言，有良好的表现，但是在仿真过程中发现场景中的节点时而密集在一起，时而分散造成链路断开，使得基于全局参数计算的半衰期值不能很好地体现场景的这种变化。所以，为进一步提高DQS性能与精确度，一个可以基于场景自适应的半衰期时间获取方式应是一个改进的方向。

[1] Jiang Shengming. Granular differentiated queueing services for QoS: structure and cost model[J]. Acm Sigcomm Computer Communication Review, 2005, 35(2):13-22.

[2] 钱彦臻，姜胜明，杨方，等.一种用于差分队列服务系统的剩余路径投递时间估计方法：中国， 10242993.2[P].2016-09-28.

[3] 熊永平，孙利民，牛建伟，等. 机会网络[J]. 软件学报,2009, 20(1):124-137.

[4] 任智，黄勇，陈建斌．机会网络路由协议[J]．计算机应用，2010, 30(3):723-728.

[5] GUERIN R, PERIS V. Quality-of-service in packet networks: basic mechanisms and directions [J]. Computer Networks, 1999, 31(3): 169-189.

[6] GEORGIADIS L, GUÉRIN R, PAREKH A. Optimal multiplexing on a single link: delay and buffer requirements[J]. IEEE Transactions on Information Theory, 1997, 43(5):1518-1535.

[7] PELUSI L, PASSARELLA A, CONTI M. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[J].Communications Magazine, 2006,44(11):134-141.

[8] GROSSGLAUSER M, TSE D N C. Mobility increases the capacity of ad hoc wireless networks[J]. Proceedings of IEEE INFOCOM, 2001, 3(4): 477-486.

The performance analysis of the estimating of the journey time over theremaining path in opportunistic network

Wang Yiliang, Jiang Shengming, Cao Jun

(School of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

Differentiated Queueing Service (DQS) is a kind of packet-granulared queue scheduling algorithm, how good of its way to estimate the journey time over the remaining path will have a significant impact in the opportunistic network in which the network communication opportunity is very scarce. The existing way to estimate the journey time over the remaining path has not tested the performance in opportunistic network. In this paper, by comparing DQS with the Earliest Deadline First (EDF), and test the performance of a way to estimate the journey time over the remaining path based on value of history information in the scene of opportunistic network. It is proved that the way can remarkably improve the delivery ratio meanwhile make the average delivery delay more volatile or larger.

Differentiated Queueing Service(DQS); opportunistic network; the journey time over the remaining path; Earliest Deadline First (EDF)

国家自然科学基金(61472237)

TP393

A

10.19358/j.issn.1674- 7720.2017.15.019

王益亮，姜胜明，曹军.机会网络剩余路径投递时间估计方法性能分析[J].微型机与应用，2017,36(15)：65-68，72.

2017-02-08)

王益亮(1992-)，男，硕士研究生，主要研究方向：无线网络协议。

姜胜明(1964-)，男，博士，教授，主要研究方向：通信网络结构、协议和算法等。

曹军(1990-)，男，硕士研究生，主要研究方向：通信网络结构。