间歇性连通网络数据传输与路由技术研究* 1

康宗绪，雷文虎，李广志，苏凌旭

(1.重庆金美通信有限责任公司,重庆 400030；2.中国人民解放军驻重庆气体压缩机厂军事代表室,重庆 400030)



间歇性连通网络数据传输与路由技术研究* 1

康宗绪1，雷文虎1，李广志2，苏凌旭1

(1.重庆金美通信有限责任公司,重庆 400030；2.中国人民解放军驻重庆气体压缩机厂军事代表室,重庆 400030)

摘要：移动网络需要适应各种复杂应用环境，在出现节点密度较低、移动性又高的场景时，稀疏的节点就难以保证网络拓扑的稳定性和全连通性。在这种不理想的网络环境中，传统的移动自组网路由协议会因为网络频繁中断、间歇性连接和较大的网络时延等条件限制，无法建立端到端稳定的路由路径而造成算法失效。针对移动网络间歇性连通的特性，结合DTN思想，充分利用节点间相遇的机会交互数据，借助代理节点来提高数据传输的成功率，最大化报文的传输可能性。

关键词：移动网络；容断网络；代理节点；机会网络

0引言

在移动ad hoc网络的实际应用中，常会出现因节点移动、障碍物反射、信号衰减等因素造成网络在某些时刻不连通情况。传统的移动ad hoc网络在传输数据之前，需要节点通过相应的路由算法建立源到目的节点之间的路径，然后将数据沿建好的路径传递给目的节点。在这种数据传输模式下，就要求网络在绝大部分时候处于连通状态，网络中节点之间至少存在一条端到端的路径。而在实际应用中，由于某些客观因素无法保证网络一直处于连通状态，网络可能被分割成若干个互不连通的子网[1]。当源节点和目的节点不在同一子网时，传统的移动ad hoc网络路由机制就无法建立路由来完成数据传输。

由于节点可以随机移动，当节点通过移动进入彼此的通信范围时，便可以完成数据的交互，这使得网络在不连通的条件下完成数据的交互成为可能。我们将这种利用节点移动创造的相遇机会来完成数据传递的网络，称为机会网络[2]。

如果能够解决在间歇性连通的网络上传递数据，在民用和军事领域都有很广泛的应用和研究价值。与传统无线网络相比，机会网络的拓扑动态变化更频繁，节点间没有稳定的传输路径，甚至可能在任意时刻都没有一条完整的传输路径，使得那些依赖于稳定传输路径的传统路由机制难以发挥作用。

1技术思路

本文所提出的路由思想与传统移动ad hoc所采用的表驱动路由或按需路由相比[3]，增加了对长时延容忍的考虑，提出了一种新的数据封装、数据缓存、数据包双重利用以及数据包缓存时间动态化等机制，同时强调了代理节点在网络中所起的作用。

代理节点的选择比较关键，其选择好坏可以影响消息的转发次数。代理节点的选择基于历史相遇记录的概率估计和节点的社会性两方面综合考虑得出。节点的社会性主要由节点相似性和局部介效中心性两部分组成。介数中心性是节点连接其他节点路径程度上的度量，具有较大介数中心性的节点在网络中的位置比较重要，有利它连接的节点之间的交互[4]。代理节点确定后，周期性广播最小Age的代理节点通告消息。

假设存在如图1所示的移动通信网络使用场景，各节点之间的有效通信距离有限。区域内的各个节点在运行过程中根据上述机制选举出一个代理节点(或称为中心节点/网关节点)。区域内的各个节点均知道代理节点是谁，并且知道本节点距离代理节点跳数(H)；代理节点知道到达区域内其他节点的显式路径。代理节点在被摧毁或者节点本身不足以提供代理节点功能之后，可以动态的选举出新的代理节点。

图1　网络拓扑示意

如果两点间可直接交互(如M3传递数据给M2)，就直接传送数据。如果不能直接交互(如M3传递数据给M5)，则将数据进行封装发送给代理节点，由代理节点负责转发。为了做到数据的可靠性传输，代理节点在收到数据后向源节点回传一个确认数据包，表明已经受理该数据，同时将该数据缓存起来，负责将其传送到目标节点。源节点接收到确认数据包后撤销对该数据的管理。目标节点接收到数据后向代理节点回传一个确认数据包，表明已经接收该数据。代理节点收到目标节点的确认数据包后撤销对该数据的管理。也就是说，数据包只在源节点和代理节点上进行缓存和管理，中间节点只负责传递。

数据包在向代理节点转发的过程中，会在数据包中携带上所经过的节点。代理节点收到外来数据包时，从数据包中提取出显式路径保存到路由表中。当数据包需要从代理节点向普通节点转发时，利用路由表中的显式路径传递。

假设在图1中的M3需要向M5发送数据，但M3发现它无法与M5直接交互，此时M3将数据进行封装，设置源节点为M3，目标节点为Mc，距离代理节点跳数H=3，然后将数据包发送出去，该数据包可以被M2接收到。M2收到数据包后，发现该数据的目标节点为Mc，它将不再封装数据，只需要修改距离代理节点跳数H=2，然后转发出去。M1的处理方式与M2相同，它发送出去的数据即可被代理节点Mc接收到。当Mc收到M3的数据后，针对该数据生成一个确认数据包回传给M3，并进一步转发该数据。Mc发出的数据经过M4最终到达目标节点M5。M5收到数据之后，发现源节点是代理节点Mc，它需要针对该数据生成一个确认数据包回传给Mc。Mc在接收到确认数据包后，撤销对该数据的管理，本次通信结束。

从总体技术实现上可以看出，区域内存在两种类型的节点：普通节点和代理节点。普通节点上只需要保存距离代理节点跳数H，代理节点上需要保存其到达区域内各个节点的显式路径。

2跳数学习

在网络开通初期，各个节点不知道区域内的代理节点是谁，其距离代理节点跳数H为多少，在此通过被动学习方式来获取。在网络运行起来之后，就可以从接收到的数据包中提取最新的距离代理节点跳数并动态更新。

图2　跳数探测过程

如图2所示，由代理节点主动发出跳数探测数据包，各普通节点接收处理跳数探测数据包并判断是否继续向外转发。普通节点可以接收任何跳数的探测数据包，它选择跳数值最小的作为本节点距离代理节点跳数，将跳数值次之的作为备用跳数，然后将本节点距离代理节点跳数向外转发。

代理节点Mc发出一个跳数探测数据包，指示区域内的当前代理节点为Mc，距离代理节点跳数H=0，这个包可以同时被M1、M4、M6、M7接收到。当M1、M4、M6、M7收到跳数探测包后，记录区域内的当前代理节点为Mc，距离代理节点跳数H=1，同时继续向外发送一个跳数探测数据包。当M5接收到M4发出跳数探测数据包后，记录区域内的当前代理节点为Mc，距离代理节点跳数H=2。当M2接收到M1或M7发出的跳数探测数据包后，它只处理其中一个包而丢弃另外一个包，记录区域内的当前代理节点为Mc，距离代理节点跳数H=2。M3可能会收到M2或M7发出的跳数探测数据包，此时它记录区域内的当前代理节点为Mc，距离代理节点跳数H=2，同时把H=3作为其备用跳数。至此区域内所有节点均学习到了代理节点是谁及其距离代理节点跳数是多少。

3路由学习

在网络开通初期，代理节点不知道区域内存在哪些节点，更不知道其到各个节点的路径是什么，在此也通过被动学习方式来获取。在网络运行起来之后，就可以从接收到的数据包中提取显式路径并动态更新。

如图3所示，当普通节点学习到代理节点及距离代理节点跳数之后，主动生成一个路径探测数据包向代理节点发送，这个数据包根据携带的跳数选择下一跳并记录下经过的节点，当该数据包到达代理节点后，代理节点即可从数据包中将该显式路径提取出来并保存。如果此时恰好有数据需要向代理节点发送，就不用发送路径探测数据包了，因为它们都可以实现路径探测的功能。为了避免多个节点同时生成这种数据包导致信道抢占，对这种特殊数据包的产生采用一定的退避机制。

图3　代理节点显式路由生成

为了减少路径探测数据包的数量，限制跳数为1跳的节点不能发送该类数据包。如果有跳数大于1的节点的路径探测数据包经过了某个节点，该节点就不用再生成自己的路径探测数据包了，代理节点会从之前经过的那个路径探测数据包中提取到该节点的显式路径。图3中，M3发出的路径探测数据包可将M3、M2、M1到代理节点的显式路径全部带回去。

4业务转发

4.1源节点发向代理节点

源节点向代理节点转发的数据包采用探测转发的方式。在移动ad hoc网络中，由于一个节点发出的数据可以同时被多个节点接收到，因此需要对其进行控制，以免数据在无线网络中出现同一数据循环发送的现象，造成无线信道被抢占和电池能量的耗费。数据包中所携带的本节点距离代理节点跳数，正是为了实现这个目的。

当本节点距离代理节点跳数小于数据包中所携带的跳数时，节点才将该数据包转发出去，否则直接抛弃所接收的数据包。这种机制可以让数据以最短跳数方式到达代理节点。数据包到达代理节点后，代理节点会从数据包中提取出本次经过的显式路径，并将其作为最新路径保存下来，以供今后代理节点需要向源节点转发数据时使用。

从图4中可以看出，M3发送数据到Mc存在两条路线：M3→M7→c和M3→M2→M1→Mc。M3在封装数据包时，填写距离代理节点跳数H=2，发送出去的数据包会同时被M2和M7接收到。当M7接收到数据包后，发现自己距代理节点跳数为1，它会更改跳数H=1并将数据转发出去。当M2接收到数据包后，发现自己距离代理节点跳数也为2，它将直接丢弃该数据不再进行转发。这种机制使得数据传送选择M3→M7→Mc路线。

图4　源节点数据包探测转发

4.2代理节点确认反馈

代理节点向源节点传送的确认数据包，并标识该确认数据包是代理节点生成的。由于代理节点从接收到的源节点数据包内部提取出了数据包前向转发时所经过的各个节点，代理节点回传给源节点的确认数据包可以按照显式路径返回。

从图5可以看出，在代理节点Mc向源节点M3返回确认数据包时，存在两条路径：Mc→M1→M2→M3和Mc→M7→M3。Mc在封装确认数据包时填写返程路径为M7→M3，Mc发出的数据包会同时被M1、M4、M6和M7接收到。当M1、M4和M6接收到数据包后，发现自己不包含在显式路径中，就直接丢弃该数据包。当M7接收到数据包后，发现自己包含在显式路径中，它将数据包的显式路径中去掉自己，重新封装确认数据包填写返程路径为M3并发送出去。M3在接收到确认数据包后释放对原数据的管理。

图5　代理节点确认反馈

4.3代理节点发向目标节点

由于代理节点上有到区域内任何一个节点的显式路径，所以代理节点在封装数据时会将路径携带上，向目标节点发送的数据包将按照显式路径进行传递，该过程与代理节点发向源节点的传送方式相同。

4.4目标节点确认反馈

当目标节点接收到来自代理节点的数据包时，它需要向代理节点回传确认数据包，并标识该确认数据包是由目标节点生成的，传送过程与源节点发向代理节点的过程相同。这个确认数据包在带回确认消息的同时，也带回了从Mc到达目标节点的最新显式路径，Mc会将该显式路径更新到路由表中。

如图6所示，之所以采用这种处理机制，是因为虽然可以让M5知道数据是从Mc→M4→M5传递过来的，但是等到M5回传数据时，有可能由于M4已关机或者中间障碍物的阻挡或者受到电磁干扰等因素，回程路径已经不可达。而且采用显式路径返回与采用回程探测路径方式返回所占用的资源完全相同，还能获得最新可用路径。

图6　目标节点确认反馈

4.5数据中途截获

在无线链路上传输数据时，可能出现图7所示的情况：M3需要向M1发送数据，由于M3不能直接与M1交互，需要将数据进行封装发送给代理节点Mc，由Mc负责转发，但是向Mc转发的时候又会经过目标节点M1。这时就没有必要再传送到Mc节点去了，需要目标节点具备中途截获数据的功能。

图7　数据包中途截获

当节点接收到发往代理节点的前向转发数据包时，它需要查看封装的数据内容，判断目标节点是否为自己。如果不是自己，则继续向外转发；如果发现目标节点就是自己，说明数据已经到达目的端，它将该数据截获下来，然后生成一个确认数据包返回给源节点，并标识该确认数据包是由目标节点生成。图中的红色虚线表示是目标节点直接向源节点返回的确认数据包。

4.6缓存时间动态化

当引入数据中途截获机制后，可能会出现图8所示的两种情况。情况一：M3需要向M7发送数据，当数据到达M2时，就可以被M7接收到并返回确认数据包，而M1也会继续将数据传送到Mc上去，并由Mc向M3返回确认数据包，同时Mc还会将数据再一次的向M7转发并要求M7返回确认数据包。情况二：M5需要向M6发送数据，M5不能直接与M6交互，当封装好的数据包传递到M4后，M4发出的数据包会同时被M6和Mc接收到，Mc会向M5回传确认数据包，M6也会向M5回传确认数据包，而且Mc还会向M6转发数据并要求M6返回确认数据包。

图8　缓存时间动态化

通过对上述过程分析，目标节点可能会两次收到同一个数据包，这可以在应用层通过数据内容过滤掉。源节点针对同一个数据包可能会接收到两个确认数据包。针对第二个现象，我们引入数据包缓存时间动态化的机制。

源节点对需要发送出去的数据包的缓存时间可以很长，在收到确认数据包之后才将主动清除缓存的数据包；代理节点对需要中转的数据包的缓存时间也可以很长，得到确认之后才主动删除缓存的数据包；目标节点将收到的数据包直接交给应用层处理，不需要进行缓存。源节点只要接收到该数据的确认数据包后就可以撤销对其的管理，而不管该确认数据包是由目标节点生成的还是由代理节点生成的。

4.7数据包多重利用

通过对上述思想及流程的分析，我们可以发现数据包可以归纳出两个功能：传递数据和探测路由。为了减少无线网络中发送的数据包的数量，需要将发送的数据充分的利用起来，在此提出两种应用模式。

(1)距离代理节点跳数和显式路径的探测

距离代理节点跳数和显式路径的探测，通过专门设计的两个TLV实现。

对于显式路径的探测，在普通节点发往代理节点的数据包中，封装一个显式路径TLV来实现显示路径的搜集。

对于距离代理节点跳数的探测，除了在网络开通初期发送出去的跳数探测数据包中封装距离跳数TLV之外，在代理节点发往普通节点的数据包中也封装一个距离跳数TLV进去。中间节点可以对距离跳数TLV进行动态调整，这样各节点收到数据包的同时也学习到了当前距离代理节点的最短跳数。距离代理节点跳数的动态调整过程通过图9的示例进行说明。

图9　距离跳数动态调整

如图9左边所示，假设代理节点Mc当前路由表中保存的到达M3显式路径为Mc→M1→M2→M3，而此时M2已经转移到了新的位置，使得M3距离代理节点跳数变成了2。Mc根据该显式路径封装数据包并设置距离代理节点跳数H=0，发出的数据包可以被M1和M2接收到。M1接收到该数据包后进行处理，它转发的数据包已经不能到达目标节点M3了。M2接收到该数据包后进行处理，它将距离跳数改为H=1，并将显示路径中的M1、M2去除，直接向M3转发。M3收到数据包后，通过跳数TLV即可学习到其最新距离跳数为2。

如图9右边所示，假设代理节点Mc当前路由表中保存的到达M5显式路径为Mc→M6→M7→M4→M5，而此时M4已经转移到了新的位置，使得M5距离代理节点跳数变成了2。Mc根据该显式路径封装数据包并设置距离代理节点跳数H=0，发出的数据包可以被M6和M4接收到。M4接收到该数据包后进行处理，将距离跳数改为H=1，并将显示路径中的M6、M7、M4去除，直接向M5转发。M6接收到该数据包后进行处理，将距离跳数改为H=1，并将显式路径中的M6去除，向M4和M7转发。M7接收到该数据包后进行处理，将距离跳数改为H=2，并将显式路径中的M7去除，它转发出来的数据将不能到达目标节点M5了。这样目标节点M5会收到M4发送过来的两条相同的数据包，但是距离代理节点跳数分别为2和3，M5会选择H=2作为自己的距离代理节点跳数。M5在返回确认数据包的时候就可以将最新的显式路径送回代理节点并更新。

(2)多数据包组合

在图10所示中，①为源节点向代理节点发送的数据包；②为代理节点发往目标节点的数据包；③为代理节点向源节点回传的确认数据包；④为目标节点向代理节点发送的确认数据包；⑤为代理节点向源节点发送的数据包；⑥为代理节点向目标节点发送的数据包。

图10　多数据包组合

可以看出，③和⑤、④和⑥的传送方式一致，如果它们发送的间隔很短，那么它们走的路径是完全相同的，因此为了减少无线网络中传递数据包的数量，可以将这样的数据包组合成一个数据包进行传递。也就是说，源节点和目标节点相同的数据在短时间内所经过的路径是相同的，可以将短时间内两个或多个这样的数据包组合成一个数据包进行转发，可以有效节省链路开销，提供数据传送效率。

5结语

本文利用选举出的代理节点来实现间歇性连通网络中的消息摆渡，提升稀疏环境下网络的数据传输的性能和扩展性。数据源在首次发送数据报文时采用了探测发送机制，其本质还是泛洪，利用跳数和携带显示路径等机制来限制洪泛的范围。基于泛洪的路由算法具有较好健壮性和较低的数据传输时延等特点，但该算法在数据传输过程中也会消耗较多能量，占用较多的带宽资源和存储空间。如果网络规模较大或者节点的存储空间或带宽有限时，本算法就会呈现出不足的一面来。在未来的工作中，我们会考虑引入跨层机制[5]、增强对邻居信息的感知等手段来减少首次报文投递的盲目性，并进一步减少报文传输开销。

参考文献：

[1]钱雁斌,陈性元,杜学绘等. 无线多跳空间网络间歇连通性问题研究[J]. 计算机科学,2009,36(11):52-55.

QIAN Yan-bin,CHEN Xing-yuan,DU Xue-hui,et al. Research on Intermittent Connectivity for Wireless Multiple-hop Space Network [J]. Computer Science,2009,36(11):52-55.

[2]杨勇. 基于地理位置信息的机会网络路由算法研究[D]. 重庆：重庆邮电大学,2013.

YANG Yong. A Study on Location-based Routing Algorithms for Opportunistic Networks. Chongqing University of Posts and Telecommunications, 2013.

[3]沈亮光,汪学明. 移动 Ad hoc 网络ZRP 路由协议的仿真分析[J].通信技术,2013, 46(08):71-73.SHENG Liang-guang, WANG Xue-ming. Simulation Analysis of ZRP Routing Protocol in Mobile Ad hoc Network[J]. Communications Technology,2013,46(08):71-73.

[4]Newman M E J. A Measure of Betweenness Centrality based on Random Walks[J]. Social Networks, 2005,27(5):39-54.

[5]LIU C, WU J. On Multicopy Opportunistic Forwarding Protocols in Nondeterministic Delay Tolerant Networks[J]．IEEE Transactions On Parallel and Dislributed Systems,2012,23(6):1121-1128．

Service Transfer and Routing Algorithm for Intermittent Connectivity Network

KANG Zong-xu1, LEI Wen-hu1，LI Guang-zhi2,SU Ling-xu1

(1.Chongqing Jinmei Communication Co.,Ltd., Chongqing 400030, China；2.PLA Military Representative Office Posted in Chongqing Gas Compressor Co., Ltd., Chongqing 400030,China)

Abstract：Mobile network is required to adapt various complex application environments. In the scene of low node density and high mobility, it is difficult for the sparse node to guarantee the stability and full connectivity of network topology. In such a non-ideal network environment, traditional routing algorithm, for frequent network interruption, intermittent connection and fairly large network delay, could not establish a stable end-to-end routing path and finally would cease to be effective. In view of the intermittent connection for mobile network, and in combination with DTN ideology, the proposed algorithm could catch the opportunity for nodes to meet each other and effectively implement message interaction and by depending on the agent node, improve the success rate of message transmission and provide reliable message delivery.

Key words：mobile networks；disruption tolerant networks(DTN)；agent node；opportunistic networks

doi:10.3969/j.issn.1002-0802.2016.05.016

* 收稿日期：2015-12-12；修回日期：2016-03-25Received date:2015-12-12；Revised date：2016-03-25

中图分类号：TP393.0

文献标志码：A

文章编号：1002-0802(2016)05-0593-06

作者简介：

康宗绪(1972—)，男，硕士，高级工程师，主要研究方向为计算机网络及通信技术；

雷文虎(1980—)，男，硕士，工程师，主要研究方向为计算机网络技术；

李广志(1978—)，男，学士，工程师，主要研究方向为网络通信技术；

苏凌旭(1977—)，男，硕士，工程师，主要研究方向为通信协议处理。