0 引言

随着通信技术的迅猛发展，人们从过去追求人与人之间无缝的联系与沟通向人与物、物与物方向逐步发展。物联网以透彻感知、良好的扩展性成为继互联网之后全球信息产业的又一次科技与经济浪潮，对于加速整个社会信息化发展的进程，促进形成新的经济增长具有重要的作用^[1]。智能交通是战略性新兴产业中物联网和智能化汽车两大领域的重要交集，使用无线通信方式共享信息，实现汽车之间、汽车与建筑物或其他基础设施之间的信息交换，甚至可以帮助实现汽车与行人以及汽车与非机动车之间的“对话”，其应用研究将为人们呈现一个崭新的智能交通系统：在无需信号灯指引的情况下，汽车可以高速行驶，而且不会发生堵塞、事故等现象，人们可以享受更环保、更安全、更智能、更人性化的交通服务，颠覆人们对于传统“交通”的认识。公共交通网络是智能交通在现实生活中的一个重要应用领域。

和传统的物联网一样，公共交通网络的基础也是无线传感器网络(Wireless Sensor Network, WSN)，为车辆的感知、互连等提供基础支持，属于移动自组织网络(Mobile Ad Hoc NETwork, MANET)的范畴。但是和传统的WSN、MANET不同，由于在公共交通网络中车辆的行驶速度普遍较快，从而导致网络拓扑剧烈变化，而且在网络中作为节点的汽车通常处于网络的边缘地带，呈现稀疏分布现象，在该情况下，无法在源节点和目的节点之间建立端到端的传输路径，致使传统的WSN、MANET路由无法路由成功。延迟容忍网络(Delay and Tolerant Network, DTN)不要求网络具有全连通特性，以机会的方式进行消息的转发，可以很好地解决上述问题。将DTN技术加以扩展并在公共交通网络中进行应用，是对DTN在车载网上应用的扩展。但和传统车载网络不同的是，公共交通网络存在其自身独有的一些特点^[2-5]：网络覆盖面广; 节点运动具有规律性; 节点呈现稀疏性分布; 公共交通中的节点通常有足够的能量和存储能力，不会因为能量不足等原因退出服务。虽然现有许多DTN路由协议^[6-9]均能直接应用在公共交通网络上，但其设计没有考虑上述公共交通网络自身的特点，所以路由性能并不理想。

综上所述，虽然已有的DTN路由算法可以应用于公共交通网络，但是在缺乏公共交通网络自身特性的考虑条件下，不能将其路由性能发挥到极致。本文结合公共交通网络特点，提出一种适用于公共交通网络的路由算法TF，可以获得更优的路由性能。

1 TF路由策略

从交通业务角度可以将公共交通网络看成由以城市公交车、出租车为主的城市公共交通运输系统和以长途客车为主的市域交通系统。将参与公共交通的运输工具作为数据传输载体构建通信网络，不仅可以满足网络内各实体间的通信需求，同时还可以在交通工具所经过的道路范围内提供网络覆盖和相应的服务。

本算法充分考虑现有的城市交通网络结构，将整个路由策略拆分为基于固定运动路径分组的DTN路由算法和基于自由节点的DTN路由算法两个部分。其中基于固定运动路径分组的DTN路由算法充分考虑以公交车、地铁、电车等为主要公共传输工具的车辆运动的规律性以及节点的分布稀疏不均匀性，将网络中的节点按运动路径进行分组，并结合改进的概率路由算法，对组内和组间节点采用不同的方式进行消息的传递，从而达到提高投递率和降低传输时延的目的；基于自由节点的转发因子控制的DTN路由策略主要考虑到固定运动路径分组路由算法的缺点，利用城市中的出租车、行人等作为固定运动路径分组路由算法的补充，为其提供二次组网，从而使整个城市公共交通运输路由策略更符合真实城市网络，提高整个算法的性能。

1.1 基于固定运动路径分组的DTN路由策略

在公共交通运输网络中，公交车辆通常是在预先指定的线路上运动，在无特殊情况的前提下，其运动轨迹不会偏离既定的运动路径。依据这一特点，可将网络中的节点划分为若干个不同的分组，将同一分组中的节点看作一个整体，则消息的多个副本可以经过不同分组、不同路径进行传递，当消息到达目的节点所在的分组时，则不再进行组间传递，仅通过组内节点将消息传递至目的节点。

1.1.1 节点分组划分

为了实现上述路由目标，节点分组的划分方式是其中的关键。本算法首先将网络中的所有节点依据其运动路径的不同划分为不同的分组；然后对同一分组的节点分配一个全局唯一且相同的组编号。简而言之，分组过程可以看作对网络中节点划分域的过程，而组编号相当于域名。

如图 1所示，依照节点运动分属的两条不同路径A′和B′，可将网络内节点分为两组。在对节点编号时，每一组的节点都携带本组路径的编号，以此保证网络中的所有节点均存在唯一对应的编号。当两节点相遇时，首先依照组编号进行节点区分，当组编号相同时，再按照分组内节点自身编号进行节点区分。即当两节点接触，且存在消息传输机会时，消息首先根据两节点的组编号判断节点是否处于同一分组，然后决定其应采取的路由策略。

1.1.2 组内消息的传递

从上文分析可知，网络中节点的分布存在稀疏不均匀现象，并且城市“摊大饼”的发展格局通常造成城市中心区域公交线路密集，而周边区域往往只有一条或较少几条公交线路的格局。因此，在对节点按照运动路径进行分组后，消息在组内节点之间的传递应考虑以下两种情况：

1)消息所处节点附近只存在同分组的节点；

2)消息的目的节点即为本组节点。

由于同组车辆均在同一条路径上运行，消息在组内传递时，只会沿路径方向进行，并且如果将两车接触的瞬时位置看作一个点，那么这两辆车在接触时只能是同向运动或反向运动两种情况。当接触组外节点时，将通过其他途径决策，并不对本组内传递产生影响。

当消息的目的节点为本组节点时，采用直接投递的方式将消息传递到目的节点。当且仅当消息到达目的节点所在分组之后且首次与反向运动的节点接触时，对该消息进行一次拷贝，并传递消息副本至所接触的节点。通过两节点相互间反向运动，使消息尽快到达目的节点。为了便于区分节点的运动方向，在节点中增加一个表示运动方向的参数，并规定某一运动方向时值为1，其反向为0。如图 2所示，当节点运动到路径两端时，通过对该参数重新赋值来表示节点运动方向的改变。这样在节点接触时，通过比较两节点该参数的值即可方便地判断节点运动方向的异同。图 3展示了消息的目的节点在本组内和本组外两种情况下本组内消息传递的方式。

1.1.3 组间消息的传递

由于在公共交通网络中，节点运动路径较为固定，这就使得通过历史接触概率对未来进行预测有了相对较高的准确性。同时，路径相交可能存在十字交叉和并行两种情况，如图 4所示，从而产生组间节点的接触机会。很显然，在图 4(b)中所示的情况下，产生接触的机会要多于图 4(a)，特别是当节点同向运动时，节点间每次接触时长也远高于图 4(a)所示情形。因此，如果单纯使用接触次数来评价节点间接触概率的大小，并不能真实反映出节点之间通信机会的多少。为了能有效通过历史接触时长来表征节点间接触概率的大小，将Huang等^[10]提出的改进概率路由算法运用到本场景中，以期在公共交通网络中获得更高的消息投递率。

1.1.4 算法流程

为了实现以上算法，分组后的节点参数如表 1所示，消息的参数如表 2所示，图 5表示节点在等待接触和当产生接触机会时判断对方节点分组的流程。节点在运动过程中始终处于“等待”状态，不断发送探测消息，并检测是否存在接触的可能。一旦收到对方节点发出的探测消息，则激活接触，获取对方节点groupID，并与自身groupID进行对比，确定本次接触属于组内接触还是组间接触，以便继续下一步流程。其中，“Delay”表示延时器，下同。

由于DTN具有链路中断特性，本算法中定义一切在非主动断开条件下产生的接触断开都属于接触中断。实际上在本算法中，只有组内接触传输完成后的断开是主动行为，其他包括接触检测发现的断开和组间接触最后的断开均属于接触中断。与主动断开接触不同，接触中断时可能存在部分预计传输的消息并未传输，或部分处理过程没有完成(如定时器)，所以需要存在一个中断状态以便程序对已经开始但未完成的工作进行复位处理。即将整个算法分为等待、组内传递、组间传递以及中断4个状态，当两个节点之间链路处于中断状态时，节点转入等待状态进行复位处理，以完成已经开始但未完成的消息传输。

若双方节点groupID相同，则进入组内传递工作流程。如图 6的左分支所示，节点首先读取所有自身保存的消息，并依次判断消息的目的节点是否在本分组内。若目的节点在组内，则判断接触节点的运动方向是否与本节点相同以及消息是否已复制，根据判断结果决定是否进行消息的复制；若目的节点在组外，则通过判断copyCount参数是否达到阈值决定消息的复制或删除。在传输进行前，需要检测接触是否仍然建立，若接触断开，则结束传输，等待下一次接触机会。

若双方节点groupID不同，则进入组间传递工作流程。如图 6的右分支所示，组间传递开始时即设置定时器T，用于记录本次接触的时间，当接触断开时，计时器停止。该流程中节点首先获取对方节点p_list列表，取得列表长度len，并设置计数器i。由于所有节点中列表均按序排列，故表中数据条目均一一对应，此时只需将双方节点对应条目进行对比即可确定接触概率大的一方。通过循环对比得到所有分组概率大小关系，将概率小的一方到达该分组消息副本的isCopy参数置0，并传递至到达概率大的一方。在所有传递结束后，并不主动断开接触，而是等待节点运动被动的使接触断开。接触断开后，根据本次接触时长T，依据1.1.3节提出的路由算法重新计算p_list中对应条目的值并累计t_list。最后返回等待状态，等待下一次接触。

1.2 基于自由节点的DTN路由策略

在上一节讨论了公共交通中节点按照固定路径运动时的运动模式，并以此为依据，设计了一种基于节点分组的DTN路由算法。但即便如此，该算法在某些特殊情况下依然存在局限性。例如某些节点运动路径与其他节点路径仅存在交叉，甚至运动路径完全脱离其他节点孤立存在时，会造成组间节点间接触机会较少而无法获得更多通信机会，进而导致消息不能正常及时传递; 另一方面，公共交通网络中的节点并不只存在固定运动路径这一单一运动方式，若以出租车、公共自行车为代表的交通工具作为DTN节点，虽然也存在疏密性问题，但通常情况下可以认为它们在网络中的运动是随机的。因此，为了更好地与真实的公共交通相比，本节利用网络中的自由节点(随机运动的节点)作为补充节点进行二次组网，即在固定分组不易产生接触机会的节点进行消息携带的情况下，利用自由节点运动的随机性将消息进行复制并在自由节点间进行传递。通过这一机制，解决由于节点先天运动路径不佳而导致的接触机会少、消息传输不畅的问题。

为了尽快将自由节点携带的消息传输到目的节点或者目的分组，通过对传统路由方案分析得到：传染路由^[11]性能较好，但占用缓存过多，在缓存受限的情况下，其性能将受到很大影响。为了解决这一问题，Zhao等^[12]又提出了源喷射等待路由和二分喷射等待路由，但源喷射等待路由存在长时间喷射问题，最终导致时延过长。而二分喷射等待路由虽能很好地解决源喷射等待路由的缺点，但二分等待路由仍然存在以下问题：如果节点按二分等待路由的方式分配消息副本，则携带该副本的根节点会在很短的时间内将消息分散完毕，而且消息可能在较大范围网络的较小部分聚集，并不利于消息的扩散，导致整个网络性能的降低；另一方面，经过自由节点传递的消息，它们原先在分组节点中的传输可能性也有大小之分。因此设置一种动态的消息副本数控制方式是十分必要的。通过对消息副本数的控制，使其能根据消息自身位于当前节点的状态和消息自身可能在网络中的拷贝情况，动态决定在节点接触时消息的分发原则，使消息在能够保证投递率的前提下合理产生副本，避免因为副本数固定导致的副本浪费和资源占用过多的问题。

本节基于以上原因在喷射等待路由的基础上提出了基于转发因子控制的DTN路由策略。DTN为了更好地描述用于自由节点的路由算法，作出以下假设：

1)经过自由节点传递的消息在分组节点中不易传递。所谓不易传递，是指消息所在节点及其分组内的其他节点，与其他分组节点有较少通信机会，或虽与其他分组节点存在通信机会，但双方节点到达消息目的节点及其分组的接触概率较低。

2)在自由节点中传递的消息终点是消息目的节点所在的分组。目的节点所在分组对于单一目的节点来说，在随机运动中的相遇可能性更高，同时组内节点运动路径相对固定，其传递更为准确。因此，当自由节点与消息目的节点所在分组中任意节点产生接触时，即将消息传送出去，完成消息在自由节点中的传输。

3)自由节点不产生消息，也不作为消息的目的节点。本路由策略中的自由节点是作为一类补充节点在网络中存在的，故算法并不考虑自由节点作为消息源节点和目的节点，这一情况将作为下一步研究内容。

为了实现消息副本的动态控制，本节将引入转发因子(Forward Factor)的概念。转发因子是用于表征节点中某一消息被转发到目的节点可能性大小的参量。转发因子随消息到达自由节点时产生，伴随消息整个传输过程，并随着消息生成副本而进行分裂。对于同一个节点来说，不同消息均有属于自身的转发因子，若对消息按转发因子进行排序，排在前方的消息表示当前节点对该消息有较高的到达目的节点的传输可能。

消息在自由节点传输的过程中，节点对自身到达消息目的节点的能力是以节点历史接触信息来衡量的。节点在运动中不断维护历史接触信息表，表内保存了当前节点与属于各分组的分组节点历史接触次数，如图 7(a)表示当前节点p分别到达按路径运动节点的分组1, 2, …, m的历史接触次数。节点同时另行维护一个信息表，用于保存当前节点与其他自由节点历史接触次数，如图 7(b)表示当前自由节点q分别到达其他自由节点a, b, …, n的历史接触次数。

当自由节点A与自由节点B接触时，即节点内携带的消息产生了传递机会。消息的传递采取副本复制的方式，节点将消息副本传递给接触节点的同时，也会将消息自身的转发因子进行重新分配。其分配原则基于双方节点与其他节点历史接触次数的统计，包括与各分组节点接触次数的确定性统计和与自由节点接触次数的估计性统计。确定性统计方式由式(1)决定：

$ \left\{ \begin{align} &{{\mu }_{A}}\text{=}{{{P}_{Ai}}}/{\sum\limits_{p=1}^{m}{{{P}_{Ap}}}}\;\\ &{{\mu }_{B}}\text{=}{{{P}_{Bi}}}/{\sum\limits_{p=1}^{m}{{{P}_{Bp}}}}\;\\ \end{align} \right. $

(1)

其中:P_Ai、P_Bi分别表示节点A、B与分组i的历史接触次数；$\sum\limits_{p=1}^{m}{{{P}_{Ap}}}$、$\sum\limits_{p=1}^{m}{{{P}_{Bp}}}$分别表示节点A、B各自分别到达所有分组的历史接触次数之和。

式(2)表示在决策历史接触次数对转发因子的影响时，自身节点与目的节点接触次数占总接触次数的比例。但在某些情况下，如网络刚刚开始运行时，自由节点并不一定与分组节点产生过接触，则通过式(1)无法直接求出μ_A和μ_B。此时，则需通过节点与其他自由节点的历史接触信息对接触次数统计值进行估计性计算。

$ \left\{ \begin{matrix} {{\mu }_{A}}\text{=}{\sum\limits_{j\in {{U}_{A}}}{{{Q}_{Aj}}}}/{\sum\limits_{q=a}^{n}{{{Q}_{Aq}}}}\;\\ {{\mu }_{B}}\text{=}{\sum\limits_{j\in {{U}_{B}}}{{{Q}_{Bj}}}}/{\sum\limits_{q=a}^{n}{{{Q}_{Bq}}}}\;\\ \end{matrix} \right. $

(2)

其中:U_A={k_n∈Q_A|k_n>k_B}表示节点A的信息表Q中大于节点A、B历史接触次数节点的集合，U_B同理；$\sum\limits_{q=a}^{n}{{{Q}_{Aq}}}$、$\sum\limits_{q=a}^{n}{{{Q}_{Bq}}}$分别表示节点A、B各自到达所有自由节点的历史接触次数之和。

获得接触次数统计值μ_A和μ_B之后，即可通过该值决定转发因子的分配。分配采取“多接触多配，少接触少配”的原则，依据统计值和式(3)对转发因子进行分配。转发因子η伴随消息传递，且η=η_A+η_B。若两节点接触时均携带有某一消息副本，则根据式(1)和式(2)对其转发因子进行重新分配而不进行消息传递。

$ \left\{ \begin{align} &{{\eta }_{A}}\text{=}{{\mu }_{A}}/\left({{\mu }_{A}}\text{+}{{\mu }_{B}} \right)\times \eta \\ &{{\eta }_{B}}\text{=}{{\eta }_{B}}/\left({{\mu }_{A}}\text{+}{{\mu }_{B}} \right)\times \eta \\ \end{align} \right. $

(3)

当消息进入自由节点时，其转发因子设定为1。在自由节点中经过不断传输及转发因子重新分配之后，虽然偶尔可能出现某一消息副本对应转发因子增大的情况，但从全局来看，转发因子随着消息副本的增多其每副本平均值是在不断下降的。而转发因子的大小表示了该消息副本到达目的分组的能力，当转发因子下降到某一水平时，即表示该消息副本在当前节点中到达目的分组的可能性变得微乎其微，不宜再继续喷洒了。在本算法中，将决定停止消息拷贝的转发因子大小定为截止阈值TH。当两节点接触，计算得出至少一方转发因子大小低于阈值TH时，消息不再拷贝，转为向因子较大一方直接传递。下面给出一个类比Spray And Wait(SAW)路由算法消息副本数的TH计算方法。假设在某一消息“喷洒”过程中设定TH的取值为a，若设计一特殊情况，每次节点接触导致消息二分恰好使其中某一消息副本携带的转发因子为阈值a，此时该消息副本不可能再生成新的副本，也不可能导致转发因子的继续降低。如图 8所示，在每一次分配转发因子时，由于总有一份消息副本的转发因子到达阈值状态，所以在下一时间的接触中，只会存在一份消息继续进行副本拷贝。如此往复，当K次消息副本拷贝过程进行完毕时，另一份消息副本的转发因子也恰好等于a，即1-Ka=a。如果参照Spray and Wait算法初始消息副本数L^[13]而得出本次消息“喷洒”过程应得的副本总数，即可计算出a的取值。例如在图 8中，经过“喷洒”而最终得到16份消息副本，若需获得同样数目的消息副本，可计算出阈值TH至多为0.062 5。

通过引入转发因子，可以使消息副本在产生和传递时更加合理，从而避免了消息的盲目性泛洪。根据节点历史接触情况对转发因子进行分配，使转发因子能够将较大比例保留在转发可能更大的消息中，从而在未来的接触中有更大的几率实现消息副本的产生或向目的节点传递。同时，通过这一机制可实现消息传递深度的增加，使处于二叉树更深度的节点有机会获得消息副本，即消息的覆盖范围增加。

2 TF路由策略实现

由于自由节点是在分组节点的基础上增加而成，所以对于整个网络来说，自由节点和分组节点是两类不同的节点，而消息在两类节点中是统一的。因此若要实现本章中所述的路由策略，需要在表 1的基础上增加用于记录转发因子的fwdFactor参数。对于自由节点，同样需要设置新的参数，如表 3所示。

与分组节点产生接触相同，自由节点在网络中也不断地发送探测消息，并接收其他节点的探测信息。如图 9所示，当产生接触机会时，首先判断对方节点属于自由节点还是分组节点，若属自由节点，则对node_list中对应条目值加1，并进入按转发因子传递流程；若属分组节点，则对line_list中对应条目值加1，并进入消息出组传递流程。

当自由节点与分组节点接触时，进入出组传递流程。图 9左分支描述了消息从分组节点传递到自由节点的整个过程。分组节点将自身保存的在本分组内存在时间大于节点内所有消息存在时间平均值的消息标记为待转消息，并依时长排序，通过自由节点进行传递。当所有消息传递完成或接触断开，结束本次传递。

图 9右分支描述了自由节点与自由节点接触时，依据转发因子进行消息传递的工作流程。两节点接触后，根据节点内携带消息的目的节点所在分组情况，依据line_list和node_list中保存的历史接触信息，根据式(2)、(3)分别计算μ_A、μ_B和η_A、η_B。在进行消息传递前，判断消息当前转发因子是否大于阈值TH：若大于等于阈值，则接触节点双方各获得一份消息副本，且各自副本携带对应的传递因子；若小于阈值，则消息仅由接触节点中μ值较大的一方携带，且传递因子的大小不变。当所有消息传递完成或接触断开，结束本次传递。

3 仿真验证

本文对所提出的基于公共交通移动模型的DTN路由算法(TF)进行了模拟仿真验证，采用的仿真软件为机会网络环境(Opportunistic Network Environment, ONE)，是专门为延迟容忍网络设计的仿真工具，仿真利用芬兰赫尔辛基市道路作为节点基本移动地图，其场景大小为4 500 m×3 400 m。限于地图大小，基于地图中道路信息，随机规划6条固定路径作为分组节点运动的依据，仿真中消息产生间隔设置为25~45 s，每个消息大小设置为500 KB~1 MB。其通信距离均设置为50 m。自由节点的数量为30个，自由节点移动速度5~18 m/s，截止阈值设置为0.08；分组节点的运动速度设置在3.7~13 m/s，分组节点分组情况如表 4(C表示相遇的不携带该消息副本的节点数目；D表示相遇的携带该消息副本的节点数目)，并在相同的参数条件下，将本文提出的TF算法与Prophet、Epidemic和SAW路由算法进行对比。

图 10对消息投递率、开销比和平均延迟三个指标依据时间长短绘制的仿真结果，图 11为不同缓存大小在进行30 000 s仿真后的结果。

图 10(a)显示，4种路由算法策略均随仿真时间的增加，投递率逐渐增加，最终均收敛于一个定值，且本文所提的TF路由策略投递率明显高于Epidemic、Prophet、SAW路由策略；图 10(b)显示，随着仿真时间的增加，Epidemic、Prophet开销增加明显，TF路由、SAW路由开销增加较为缓慢，但最终均收敛于定值，从仿真结果来看，TF路由在开销比上明显低于Epidemic、Prophet，略高于SAW路由策略。

图 11(a)显示随节点缓存的增加，4种路由策略投递率均逐步增加，最终收敛于一个定值，从图中可以看出，TF路由策略略高于Epidemic、Prophet路由，明显高于SWA路由策略；图 11(b)显示，随节点缓存的增加，TF、Epidemic、Prophet路由的平均延时未出现过大波动变化，均趋于一个定值，而SAW路由策略平均时延呈上升趋势。综上可以得出：TF路由的平均时延明显低于Epidemic、Prophet策略。因此在综合考虑投递率、开销比、平均延迟等参数的情况下，本文所提的TF策路由略有着较优的性能表现。

4 结语

随着物联网技术的飞速发展，智能交通成为一个具有巨大发展潜力的新兴领域。近年来，智能交通已经得到了学术界、商界以及政府部分的高度重视，相关的工业和技术已经提上制定日程。然而，针对不同的应用和不同的环境，仍有很多问题亟待解决。本文结合公共交通系统自身的一些特点，提出一种具有协作机制的路由策略：针对公共交通车辆沿固定路径规律性运动的特点，设计了一种基于节点运动路径分组的DTN路由策略；针对公共交通节点路径可能较为孤立或与其他分组节点接触机会较少的问题，通过在分组路由基础上增加自由节点，设计了一种基于转发因子控制的DTN路由策略作为基于节点运动路径分组的DTN路由策略的一种补充，从而使整个路由策略更符合真实的公共交通路由策略。通过仿真分析表明，随着仿真时间的增长，该路由算法相对于Epidemic、Prophet以及SAW路由策略可以进一步提高消息投递率且拥有更低的平均延迟。同时，若节点能提供较大的缓存空间，在同样缓存大小的条件下，该路由在投递率和平均延迟上也能表现出更优的性能。但是本协议不考虑自由节点作为消息源节点和目的节点，这一情况将作为下一步研究内容。