Efficient Routing in Intermittently Connected
Mobile Networks: The Single-Copy Case
间歇性连接移动网络的效用路由：单拷贝情况
Thrasyvoulos Spyropoulos, Student Member, IEEE, Konstantinos Psounis, Member, IEEE, and Cauligi S. Raghavendra, Fellow, IEEE
Abstract—Intermittently connected mobile networks are wireless networks where most of the time there does not exist a complete path from the source to the destination. There are many real networks that follow this model, for example, wildlife tracking sensor networks, military networks, vehicular ad hoc networks (VANETs), etc. In this context, conventional routing schemes would fail, because they try to establish complete end-to-end paths, before any data is sent.
摘要—间歇性连接移动网络是大部分时间不存在从源到目的地的完整路径的无线网络。
有许多现实中的网络参照这种模式，例如：野生动物跟踪传感器网络、军事网络、车辆Ad Hoc 网络（VANETs）等。
在此情况下，传统路由方案将会失效，因为他们试图在数据发送前建立完整的端到端路径。
To deal with such networks researchers have suggested to use flooding-based routing schemes. 研究人员建议使用洪泛路由方案来处理此类网络。
While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention which can significantly degrade their performance. 洪泛方案有很高的提交概率，但资源大量损耗及遭受严重冲突使其性能下降明显。
With this in mind, we look into a number of “single-copy” routing schemes that use only one copy per message, and hence significantly reduce the resource requirements of flooding-based algorithms.对此我们研究了一些“单拷贝”路由方案，他们只使用每条信息的一个副本从而显著降低洪泛算法的资源要求。
We perform a detailed exploration of the single-copy routing space in order to identify efficient single-copy solutions that (i) can be employed when low resource usage is critical, and (ii) can help improve the design of general routing schemes that use multiple copies.我们对单拷贝路由空间进行详细的搜索以找出有效的解决方案使得(1)在资源使用率低时能被采用是关键的，(2)可帮助提高通用路由方案对使用多拷贝的设计。
We also propose a theoretical framework that we use to analyze the performance of all single-copy schemes presented, and to derive upper and lower bounds on the delay of any scheme.我们还提出了一个理论框架以用于对所有单拷贝路由方案表现的性能进行分析及推导出所有方案延迟的上界和下界。
Index Terms—Ad hoc networks, delay tolerant networks, intermittent connectivity, routing.
I.简介
INTERMITTENTLY connected mobile networks (ICMN) are mobile wireless networks where most of the time there does not exist a complete path from a source to a destination, or such a path is highly unstable and may change or break while being discovered. 间歇性连接移动网络是大部分时间不存在从源到目的地的完整路径的无线网络，这样的路径是极不稳定的且被发现是可能改变或被破坏。
There are many real networks that follow this model. 有许多现实中的
网络参照这种模式Examples include wildlife tracking and habitat monitoring sensor networks [1], military networks [2], vehicular ad hoc networks (VANETs) [3], pocket switched networks (PON) [4], networks for low-cost Internet provision to remote communities [5], etc. 例子包括野生动物及其栖息地监测传感器网络跟踪[1 ]，[2 ]军事网络，车辆ad hoc网（vanets）[ 3]，口袋交换网络（无源光网络）[ 4]，面向偏远地区提供的低成本因特网[ 5]等。
In these networks, intermittent connectivity might arise due to sparseness [5], [6], nodes powering down to conserve energy [1], high mobility [3], or even for covertness [2]. Intermittently connected mobile networks belong to the general category of Delay Tolerant Networks (DTN) [7], that is, networks where incurred delays can be very large and unpredictable. 在这些网络中，可能由于稀疏[5]，[6]，节点关闭以节约能源[1]，高流动性[3]，或甚至为隐蔽性[2]而出现间歇性连接。
间歇性连接移动网络属于一般类别的延迟容忍网络（DTN）[7]，也就是说，网络产生的延迟可能非常大及不可预测。
Conventional Internet routing protocols (e.g., RIP, OSPF) as well as ad hoc network routing schemes, such as DSR, AODV, etc. [8], assume that a complete path exists between a source and a destination, and try to discover minimum cost paths before any useful data is sent. 传统互联网路由协议（如RIP，OSPF）以及ad hoc网络路由方案，如DSR，AODV协议等[8]，认为源和目的地之间存在一个完整的路径，并尝试在任何有用的数据发送前发现最低成本路径。
Since no such end-to-end paths exists most of the time in ICMNs, such protocols would fail in this context. However, this does not mean that packets can never be delivered under intermittent connectivity. 由于在ICMNs中大部分时间都没有这样的端到端的路径存在，因此这些协议将失效。
但是，这并不意味着在间歇性连接下数据包无法被传送。
Over time, different links come up and down due to node mobility (or other reasons). If the sequence of connectivity graphs over a time interval are overlapped, then an end-to-end path might exist. 随着时间推移，不同链接由于节点移动（或其他原因）而上下。
如果连接图的序列在一个时间间隔重叠，端到端的路径便可能存在。
This implies that a message could be sent over an existing link, get buffered at the next hop until the next link in the path comes up, and so on and so forth, until it reaches its destination.这意味着一个消息可以被一个现有的连接发送，在下一跳得到缓冲知道路径中的下一跳出现，如此类推，直到它到达目的地。
This imposes a new model for routing. Routing here consists of a sequence of independent, local forwarding decisions, based on current connectivity information and predictions of future connectivity information.这里强制执行一个路由的新模式路由在这里组成一个独立的序列，本地转发决策，基于当前连接信息和预测未来连接信息。
Furthermore, node mobility often needs to be exploited in order to deliver a message to its destination, which is why this model is usually referred to as “mobility-assist ed routing” (other names include “encounter-based forwarding” and “store-carry-and-forward”). 此外，节点移动性往往需要被用于传送信息至它的目的地，这就是为什么这种模式通常被称为“移动辅助路由”（其他名称包括“遭遇转发”和“存储进行转发”）。
The idea is reminiscent of the work in [9]. However, mobility there is exploited in order to improve capacity, while here it is used to overcome the lack of end-to-end connectivity.此想法来源于工作[9]的启发。
但是，被用于提高性能的移动性，在这里被用于克服端到端连接的缺少。
Depending on the number of copies of a single message that may coexist in the network,
one can define two major cate gories of mobility-assisted routing schemes.根据但消息的副本可以在网络中并存，一份可以定义两种主要类别的移动辅助路由方案。
In single-copy schemes, there’s only one node in the network that carries a copy of the message at any given time.We call this node the “custodian” of the message. 单拷贝方案中，在任何特定的时间只有一个节点在网络中进行信息拷贝。
我们称此节点为信息的“托管人”。
When the current custodian forwards the copy to an appropriate next hop, this becomes the message’s new custodian, and so on and so forth until the message reaches its destination. On the other hand, multiple-copy (or multi-copy) routing schemes may generate multiple copies of the same message, which can be routed independently for increased robustness. 在当前的托管人转发副本到一个合适的下一跳时，这将成为消息的新托管人，依此类推直到消息到达它的目的地。
另一方面，（多拷贝）路由方案会产生相同信息的多拷贝，为提高稳定性而被独立发送。
The majority of routing schemes proposed for ICMNs are flooding-based, and, therefore, multi-copy in nature [1], [10], [11]. Despite their increased robustness and low delay, flooding-based protocols consume a high amount of energy, bandwidth, and memory space (all scarce resources for most low-cost wireless devices) [1], [10], [12].ICMNs提出的主要路由方案都是基于洪泛的，因此，本质上是多拷贝[1], [10], [11]，尽管他们提高了稳定性且降低了延时，但基于洪泛的协议会消耗大量能源，带宽和存储空间（都是大多数低成本无线设备的稀缺资源）[1], [10], [12]。
Further, under high traffic loads they suffer from severe contention and message drops that can significantly degrade their performance and scalability [12], [13]. These shortcomings often make such algorithms inappropriate for energy-constrained and band-width-constrained applications, which is commonly the case in wireless networks. 此外，在高流量负荷的情况下，他们遭受严重的争夺和消息下降，这会显著降低其性能和可扩展性[12][13]。
这些缺点往往使算法不适用于资源和带宽有限的应用，通常是无线网络的情况下。
Consequently, it is desirable to design efficient single-copy routing schemes for many resource-constrained ICMNs. Additionally, single-copy schemes constitute the building blocks of multi-copy schemes.因此，急需为许多资源有限的ICMNs设计出有效的单拷贝路由方案。
此外，单拷贝方案是构成多拷贝方案的基石。
In many multi-copy schemes a number of copies are generated, each of which is routed independently using a single-copy algorithm [12]. For this reason, it is important to have a good understanding of the tradeoffs involved in single-copy routing, in order to design efficient multi-copy schemes, as well.在许多多拷贝方案中有一些副本被生成，他们各自被使用单拷贝的算法[12]独立按路径发送。
出于这个原因，对单拷贝路由涉及的权衡有一个很好地理解是至关重要的，同时也是为了设计更有效的多拷贝方案。
With this in mind, we perform in this paper a thorough investigation of single-copy routing for intermittently connected mobile networks. (In [14] we study the same problem using multi-copy approaches.)We present a number of increasingly “smart”schemes, exposing their individual advantages and shortcomings, and demonstrate that competitive performance can often be achieved without the overhead and logistics of using redundant copies.考虑到这一点，我们为对间歇性连接移动网络的单拷贝路由文本进行了彻底调查。
（在[14]中我们使用多拷贝方法研究同样的问题。
）我们提出一些越来越“聪明”的方案，指出他们各自的优点与缺点，并表明竞争表现常可以在没有开销和使用冗余副本物流的情况下实现。
The champion algorithm of our study turns out to be one that combines the simplicity of a simple random policy, which is efficient in finding good leads towards the destination,with the sophistication of
utility-based policies that effic iently follow good leads. Finally, we propose an analytical framework to evaluate the performance of any routing scheme in the context of ICMN.冠军算法是我们结合了简单随机策略的简约性的研究成果之一，它能有效寻找到指向目的地的最好指引，基于实用性策略的改进可有效跟随好的指引。
最后，我们提出一个框架分析来评估在ICMN环境下所有路由方案的性能。
Using this framework we derive lower and upper bounds on the expected delay of any single-copy routing scheme (these are actually bounds for multi-copy schemes, as well). We also use our framework to analyze the expected delivery delay of all the single-copy algorithms presented.使用此框架我们可推导出所有单拷贝路由方案预期延时的上限和下限（这实际上也是多拷贝的界限）。
我们同样可以使用此框架来分析所有单拷贝算法显示的预期交付延时。
In the next section we go over some existing related work. Section III describes a number of single-copy routing algorithms, including our proposed solution and an optimal scheme. Then, in Section IV we present our analytical framework, and use it to evaluate the expected performance of the routing schemes presented. Section V provides simulation results where the performance of all the strategies is compared. Finally, Section VI concludes the paper and gives some directions for future work.在下一节中我们将重温现有的相关工作。
第三节描述了一些单拷贝路由算法，包括我们提出的解决方案和最优方案。
之后，在第四节将提出我们的框架分析，并使用它来评估路由方案所表现的预期性能。
第五节将提供所有策略性能比较的模拟结果。
最后，在第六节将总结全文并为今后的工作提供方向。
II. 相关工作及贡献
Although a large number of routing protocols for wireless ad hoc networks have been proposed [8], [15], traditional routing protocols are not appropriate for networks that are sparse and disconnected. The performance of such protocols would be poor even if the network was only “slightly” disconnected. 尽管已经提出了许多无线ad hoc网的路由协议，[8], [15],但传统路由协议并不适用于稀疏及不连续的网络。
即使网络只是“略有”不连续，这些协议的表现也很欠佳。
To see this, note that the expected throughput of reactive protocols is connected with the average path duration and the time to repair a broken path with the following relationship:[16]. Node mobility leads to frequent disconnections, reducing the average path duration significantly. 看到这一点，注意相关协议的预期吞吐量与平均路径持续时间和修复一条损坏的路径有如下关系：[16]。
节点的移动导致了频繁断开，明显减少了平均路径持续时间。
Consequently, in most cases (at least 2 the optimal delay) is expected to be larger than the path duration, which implies that the expected throughput will be close to zero. Proactive protocols, on the other hand, would declare lack of a path, or result into a deluge of topology updates. 因此，在大多数情况下（至少2个最佳延迟）预计将大于路径持续时间，这意味着，预计吞吐量将接近零。
另一方面，主动型协议，将声明缺少路径或导致拓扑更新泛滥的结果。
One approach to deal with very sparse networks or connectivity “disruptions” *2+ is to reinforce connectivity on demand, by bringing for example additional communication resources into the network when necessary (e.g., satellites, UAVs, etc.). 处理极稀疏网络或连接“中断”的一种方法是通过例如在必要时给网络增加通信资源(e.g., satellites, UAVs, etc.)。
Similarly,
one could force a number of specialized nodes (e.g., robots) to follow a given trajectory between disconnected parts of the network in order to bridge the gap [17], [18]. In yet other cases, connectivity might be predictable, even though it is intermittent (e.g., Inter-planetary networks, IPN [19]).同样地，有的将迫使一些专门的节点去遵照部分不连续网络间的既定轨迹为的是桥接间隙[17], [18]。
在其他情况下，连接也许是可预测的，即使它是间歇性的（例如，行星间的网络，IPN[19]）。
Traditional routing algorithms could then be adapted to compute shortest delivery time paths by taking into account future connectivity [5], [20]. Nevertheless, such approaches are orthogonal to our work;之后传统路由算法可被适用于计算考虑了未来连接的最短交付时间路径[5], [20]。
然而，这种方法与我们的工作相正交；our aim is to study what can be done when connectivity is neither enforced nor predictable, but rather opportunistic and subject to the statistics of the mobility model followed by nodes.我们的目标是研究在连接既不能执行也不能预见时能做什么，而不是投机取巧以及服从随后节点的移动型模型统计。
Despite a significant amount of work and consensus existing on the general DTN architecture [7], there has not been a similar focus and agreement on DTN routing algorithms, especially when it comes to networks with opportunistic connectivity.尽管有相当数量的工作和现有的一般DTN架构上的共识[7]，这里并没有形成一个类似的重点和DTN路由算法的一致，特别是当它变成随机连接的网络。
The simplest possible approach is to let the source or a moving relay node (DataMule) carry the message all the way to the destination (Direct Transmission) [6]. Although this scheme performs only one transmission, it is extremely slow [9]. A faster way to perform routing in ICMNs, called Epidemic Routing, is to flood the message throughout the network [11]. 最简单有效的方法是让资源或移动延时节点（DataMule）执行消息通过所有方式到达目的地（直接传输）[6]。
即使此方案只执行一个传输，它也是极其缓慢的[9]。
在ICMN 中有一个更快的方法执行路由，名为流行性路由，是消息在网络中泛滥[11]。
This scheme is guaranteed to find the shortest path when no contention exists for shared resources like wireless bandwidth and buffer space. Yet, it is extremely wasteful of such resources.此方案保证在例如无线带宽和缓存空间这样没有共享资源竞争的情况下找到最短路径。
然而，它对此类资源极其浪费。
What is worse, in realistic scenarios where bandwidth, memory space, or energy resources might be scarce, the performance of flooding degrades significantly *10+, *12+, *13+.更糟的是，在现实情况下带宽、存储空间或能量资源可能稀缺，洪泛的性能将会明显下降[10], [12], [13]。
A number of approaches have been taken to reduce the overhead and improve the performance of epidemic routing [1], [10], [13], [21]–[23]. In [21] the authors examine a number of different schemes to suppress redundant transmissions and clean up valuable buffer space after a message has been delivered with epidemic routing.一系列方法已经被用以减少开销及提高流行性路由的性能[1], [10], [13], [21]–[23]。
在[21]中作者研究了不同方案以抑制冗余的传输以及在流行性路由交付消息后清理宝贵的缓存空间。
In [13], [22] a message is forwarded to another node with some probability smaller than one (i.e., data i s “gossiped” instead of flooded). Finally, in *1+ a simple method to take advantage of the history of past encounters is implemented in order to make fewer and more “informed” forwarding decisions. The concept of history-based or utility-based routing is further elaborated in [10], [24].在[13], [22]中消息以小于1的概率转发到另一个节点（i.e., 数据是“闲聊”而不是洪泛）。
最后，在[1]中实施一个简单的方法来利用过去遭遇的历史是为了做越来越多的“通知”转发决策。
基于历史和基于实
用性的路由概念将在[10], [24]中进一步阐述。
Results from these studies indicate that using the age of last encounter with a node, when making a forwarding decision, results in superior performance than flooding. The concept of history-based routing has also been studied in the context of regular, connected wireless networks in [25].这些研究结果表明在使用一个节点的最后遭遇的年龄时，做出转发决定将产生比洪泛更优越的性能。
[25]中基于历史路由的概念同样在定期连接的无线网络中被研究。
Finally, it has also been proposed that Network Coding ideas could be useful to reduce the number of bytes transmitted [23]. Although all these schemes, if carefully tuned, can improve to an extent the performance of epidemic routing, they are still flooding-based in nature, and thus often exhibit the same shortcomings as flooding *14+.最后，网络编码的想法可被用于减少传送的字节数也已被提出[23]。
即使是这些方案，如果仔细调整同样可在一定程度上提高流行性路由的性能，他们仍然是基于洪泛的性质，因此常常表现出同洪泛一样的缺点[14]。
A different approach to significantly reduce the overhead of epidemic routing, while still maintaining good performance, is to distribute only a bounded number of copies [12], [21], [26], [27].有一个不同的方法能显著减少流行性路由开销，并仍保持良好的性能，就是只分发有限数量的副本[12], [21], [26], [27]。
In a manner similar to the 2-hop scheme of [9], a copy is handed over to a fixed number of relays, each of which can then deliver it only directly to the destination. Nevertheless, in many situations where node movement is strongly correlated or predominantly local, the performance of this scheme deteriorates [4], [14].与[9]中2-跳方案相似的方式，一个副本被移交到一个固定数量的中继器，之后其中每一个仅可提供它直接到目的地。
然而，在许多情况下节点的运动都有着密切联系或以当地为主，从而此方案的性能会恶化[4], [14]。
Despite the variety of existing approaches, the majority of them are multi-copy ones. Furthermore, the minority that deals with single-copy techniques only studies direct transmission [6] or some form of utility-based schemes in relatively different contexts [24], [25]. In this work, we perform a detailed inquiry into the problem space of single-copy routing, and show how to achieve competitive performance without using multiple copies. We look into how utility functions can be designed to fully take advantage of the “field”of past encounters, and propose a function that is shown to achieve up to an order of magnitude improvement in ICMNs over existing utility functions [25]. Finally, we propose a novel, hybrid routing scheme, which uses randomization when necessary to overcome some inherent shortcomings of utility-based forwarding.尽管现在有多种方法，但主要都是多拷贝的。
此外少数通过单拷贝技术处理的也只研究了直接传输[6]或在相对不同的环境下基于实用性方案的一些形式[24], [25]。
在这项工作中，我们在单拷贝路由的问题空间执行详细查询，并展示怎样在不使用多拷贝的情况下实现有竞争力的性能。
我们研究如何设计一个实用性函数来充分利用过去遭遇的“领域”，并提出一个函数展示在ICMNs中对现有功能性函数实现一个数量级的改善[25]。
最后，我们提出一种新型的、混合路由方案，用以在需要克服基于实用性转发的一些固有缺点时进行随机选择。
In the theory arena, a large body of work has recently emerged trying to analyze the trade-offs involved between the asymptotic capacity and the asymptotic delay of the 2-hop scheme proposed in [9], and related schemes exploiting mobility [27]–[30]. Although asymptotic
results provide valuable insight on the scalability of a given family of protocols, they often do not provide the necessary insight to design efficient and practical schemes. Furthermore, the majority of these works are concerned with delay in connected networks. In such networks, mobility is only used to reduce the number of transmissions. On the other hand, mobility in disconnected networks is an intrinsic component of the minimum delay. Furthermore, in connected networks the transmission range of each node has to scale with the number of nodes, in order to ensure connectivity, making all related analytical results strictly a function of the number of nodes [27], [28]. Here, we’re interested in a much wider range of connectivity scenarios, where transmission range, number of nodes, and network size are independent parameters, whose individual effect on performance our analytical framework aims at quantifying.在理论领域，最近出现了大量工作来试图分析涉及渐近能力、[9]提出的2-跳方案的渐近延时和利用流动性的相关方案[27]–[30]的权衡。
尽管渐近结果给给定家庭协议的可扩展性提供了宝贵的见解，但他们往往不能提供设计高效实用方案的必要见解。
此外，这些工作主要与连接网络的延时有关，流动性只用于减少传输次数。
另一方面，非连续网络的流动性是最小延时的内在组成部分。
此外，在连续网络中每个节点的传输范围必须与节点数成比例，为的是确保连续性，使所有相关分析结果严格遵照节点数的一个函数[27], [28]。
这里，我们对一个更广范围的连接方案抱有兴趣，其传输范围、节点数、网络规模都是独立的参数，他们独立作用于我们对量化进行框架分析的性能。
Also, in the context of disconnected networks, most existing analytical efforts concern the performance of epidemic routing or other multi-copy schemes [14], [21], [22], [26]. To the best of our knowledge, the only prior analytical work for single-copy schemes is on direct transmission [6] and some asymptotic results regarding utility-based schemes [25], [31]. Finally, in many existing studies, some parameters of the proposed model (e.g., node inter-meeting times) need to be acquired from simulation traces for each and every scenario [21], [22]. Here, we expand our framework from [32] to evaluate the delivery delay of all the single-copy algorithms examined, as well as to derive lower and upper bounds on the expected delay achievable by any scheme in ICMNs.此外，在非连续网络环境下，大量现有的分析工作与流行性路由的性能或多拷贝方案有关[14], [21], [22], [26]。
据我们所知，对单拷贝方案的事先分析工作仅仅是直接传输[6]和基于实用性方案的一些渐近结果[25], [31]。
最后，在许多现有的研究中，被提出的模型的一些参数（例如，节点间会议时间）在每一个情景都需要被模拟追踪获取[21], [22]。
这里，我们扩大我们的框架从[32]到评估所有单拷贝算法考察的延时交付，以及推导出使用ICMNs所有方案可实现的预期延时的上界和下界。
III. 单拷贝路由策略
In this section, we explore the problem space of single-copy routing in ICMNs. Our problem setup consists of a number of nodes moving independently according to some stochastic mobility model. Additionally, we assume that the network is disconnected at most times, and that transmissions are faster than the node movement (a reasonable assumption with modern wireless devices). Also, each node can maintain a timer for every other node in the network, which records the time elapsed since the two nodes last encountered each other (i.e., came within transmission range). These timers are similar to the age of last encounter in [25], and are
useful, because they contain indirect (relative) location information. However, note that not every routing scheme requires these timers. Also, we assume that this is the only information available to a node regarding the network (i.e., no explicit location info, etc.). Finally, we assume that nodes emit a beacon signal, possibly periodically, that advertises their presence. In practice, when another node senses this beacon, the two nodes establish a relationship (as for example in Bluetooth pairing [33]) by exchanging IDs and other relevant information like timer values. We refer to this as an “encounter ”.在此节，我们探索ICMNs中单拷贝路由的问题空间。
我们的问题设置由根据随机移动模型独立移动的一系列节点组成。
另外，我们假设网络在大部分时间不连续，以及传输比节点移动更快（对现代无线设备的一个合理假设）。
此外，每个节点可包含一个用于网络中其他节点的计时器，用于记录从两个节点最后一次相互遭遇（即传输范围内）后过去的时间。
这些计时器与[25]中最后遭遇年龄相似，且十分有效，因为它们包含间接（相对）位置信息。
但是，要注意到并非所有路由方案需要这些计时器。
此外，我们假设这是关于网络中唯一可用的节点信息（即没有明确的位置信息等）。
最后，我们假设节点发出一个信标信号，可能是定期的，以表明他们的存在。
实际上，当另一个节点感觉到这个信标，两个节点将通过交换ID和其他相关信息例如计时器值来建立关系（例如蓝牙配对[33]）。
我们称此为一次“遭遇”。
We will now look into a number of increasingly “smart”routing strategies. We believe that these are fairly representative of different approaches one might take for the problem in hand. Each routing algorithm decides under what circumstances a node, currently holding the single message copy, will hand it over to another node it encounters. The goal is that each forwarding step should, on the average, result in progress of the message towards its destination. (Due to space limitations, all the proofs for this section can be found in [34].)
现在我们将寻找一些越来越“聪明”的路由策略。
我们认为这些不同方法中的一个将承担手上的问题相当有代表性。
每个路由算法决定在什么情况下一个在目前持有单一消息副本的节点会将它转交给遭遇到的另一个节点。
目标是每次转发步骤将平均地导致消息进展指向其目的地（由于篇幅所限，本节中的所有论证可以在[34]中找到）。
Direct Transmission: The simplest possible routing scheme imaginable is the following: a node forwards a message to another node it encounters, only if is the message's destination. This scheme is trivial, but it has the advantage of performing only a single transmission per message. It has been considered in some previous work [6], [9], and its expected delivery delay is an upper bound on the expected delay of any routing scheme. It will therefore serve as our baseline.
直接传输：能想象得到的最简单可行的路由方案如下：一个节点转发消息给他遭遇到的另一个节点，仅当它是消息的目的地时。
这项方案是微不足道的，但它在每个消息只执行一次单一传输时有优势。
它已经在一些以前的工作中被考虑到[6], [9]，并且它的预期交付延时是所有路由方案预期延时的上界。
他将因此作为我们的基准。
Randomized Routing Algorithm:The first nontrivial routing algorithm that we will look at is a randomized forwarding algorithm, where the current message custodian hands over the message to another node it encounters with probability. Further, in order to avoid a message constantly jumping back and forth between two nodes within range, we assume that, when a node receives a message, it is not allowed to send the message back to the node it received it from, for a given amount of time (the two nodes are tagged as“coupled”[35] until a timer expires).
随机路由算法：第一个非平凡的路由算法，我们将看做是一项随机转发算法，当前消息保管人将消息移交给另一个它可能遭遇的节点。
此外，为了避免消息不断在两个节点间来回跳跃，我们假设，当节点接收到一条消息，它不允许在一个给定的时间将消息发回给让它收到消息的节点（两个节点被标记为“耦合”[35]直到计时器到期）。
Lemma 3.1: When all nodes move according to a stochastic mobility model whose expected meeting time is a concave function of distance, forwarding a message results in a reduction of the expected delivery time of the message to its destination.
引理3.1：当所有的节点根据随机移动模型移动，其预期会议时间将是凹函数距离，转发消息导致消息到达目的地的预期交付时间减少。
Lemma 3.1 states that even this simple routing strategy results in expected progress at each forwarding step (i.e., locally), for a number of mobility models (e.g., Random Walk, Random Way-point [8]). This result might be slightly counterintuitive, but can be explained by the fact that transmissions are faster than node movement. Nevertheless, this progress is marginal, especially when far from the destination.
引理3.1表明即使此简单路由策略在一些移动模型（例如，随机游走，随机航点[8]）的每一步转发取得预期进展（即本地）。
这一结果可能略有悖常理，但可以被传输比节点移动更快的事实解释。
然而，此进展是微小的，尤其是在远离目的地时。
Utility-Based Routing With 1-Hop Diffusion: Randomized Routing does not take advantage of the only information available to each node regarding the network, that is, the last encounter timers. Position information regarding different nodes gets indirectly logged in the last encounter timers, and gets diffused through the mobility process of other nodes. For many noncontrived (or nonadversarial) mobility models, it can be shown that a smaller timer value on average implies a smaller distance from the node in question. Therefore, we can define a utility function based on these timers, which indicates how “useful”a node might be in delivering a message to another node. A gradient-based scheme can then be used to deliver a message to its destination, as has been noted in [10], [25]. This scheme will try to maximize the utility function for this destination. 基于效用路由1-跳扩散：随机路由不利用仅可用于关于网络的每个节点的信息，也就是说，最后遭遇计时器。
关于不同节点的位置信息得到最后遭遇计时器的间接记录，并且在其他节点的流动进程中得到扩散。
对于许多非预见性（或非对抗性）移动模型，可以显示一个较小计时器的平均值意味着问题中节点的较小距离。
因此，我们可以定义一个基于这些计数器的实用性函数，这表明一个节点给另一个提供消息时多“有用”。
一个基于梯度的方案被用于传送消息至其目的地，已在[10], [25]被提出。
此方案将尽量使此目的地实用性函数最大化。
Definition 3.1 (Utility-Based Routing): Let denote the time elapsed since node last saw node . Let further each node maintain a utility function for all nodes, where is a monotonically decreasing function of the respective last en-counter timer , and , . Then, a node forwards to another node a message destined to a node , if and only if , where (utility threshold) is a parameter of the algorithm.
Lemma 3.2: Let all nodes move according to a stochastic mobility model for which ,( denotes the distance between two nodes). Let fur-ther a node carrying a message for a node encounter。
