第 1 章 绪论
1.1 课题研究的背景和意义
随着通信技术的发展，许多自然界与社会中的实体都可以通过网络连接起来并进行通信，带动了网络技术的发展，同时也产生了一些新兴的网络，例如自组织网络(Ad Hoc)、无线传感器网络(WSN，Wireless Sensor Network)、物联网络(IOT，Internet Of Things)等等。在这些网络应用中，例如野生动植物跟踪网络、车辆广告播送网络以及移动社交网络等，具有某些显著的特征，这些特征包括对数据的实时性不高、节点与节点间的连接易于中断、网络延迟较大，此类网络被称为延迟容忍网络(DTN，Delay Tolerant Networks)。DTN 主要面临着网络延迟大、连接不稳定、数据传输率较高、差错率高等问题，但因其实用性，吸引了大量学者对其研究。
1.1 课题研究的背景和意义
随着通信技术的发展，许多自然界与社会中的实体都可以通过网络连接起来并进行通信，带动了网络技术的发展，同时也产生了一些新兴的网络，例如自组织网络(Ad Hoc)、无线传感器网络(WSN，Wireless Sensor Network)、物联网络(IOT，Internet Of Things)等等。在这些网络应用中，例如野生动植物跟踪网络、车辆广告播送网络以及移动社交网络等，具有某些显著的特征，这些特征包括对数据的实时性不高、节点与节点间的连接易于中断、网络延迟较大，此类网络被称为延迟容忍网络(DTN，Delay Tolerant Networks)。DTN 主要面临着网络延迟大、连接不稳定、数据传输率较高、差错率高等问题，但因其实用性，吸引了大量学者对其研究。
传统的 DTN 中节点位置一般随时间而变化，比如车载网络(VANET, Vehicular Ad Hoc NETwork )。然而在 DTN 中有一类特殊的网络结构，这种特殊形式的 DTN 的主要表现是网络中的大部分节点是静止的，或者是间歇性出现的。这种网络结构和传统的 DTN 性质不同，我们称其为多静态节点 DTN，多静态节点网络有很多的应用，如海域搜索场景中，海底探测的潜水机器人作为位置静态的节点间歇性地出现在水面上，而海面上的信息收集船作为移动的节点进行潜信息收集，整个网络就构成多静态节点的 DTN；再如大城市中病人就医的场景，病人和医院所处的位置不变，救护车将病人送往医院，在整个场景中，病人、医院、救护车之间的联系形成了网络结构，该网络中，病人、医院的原有位置不变，而救护车作为移动节点在病人和医院之间巡游，整个网络符合了多静态节点DTN 的特征；另外，在无线传感器网络中，由于节点本身能量有限、外界环境恶劣等特征，使得整个网络处于一种碎片状态，节点之间的通信存在的不可预期的延迟，整个网络状态符合的 DTN 的特征，在这种网络状态下使用移动节点为其他已知位置的静态节点补充能量，满足了多静态节点 DTN 的特点。上述三个应用的共同点是它们都是多静态节点的 DTN，而且在这种网络中存在可以移动的少数的节点，本文称这种可以移动的节点称为移动 Agent。移动 Agent 在应用当中有很多的功能，例如收集数据，补充能量或者分发数据等。在旅行商问题(TSP，Travelling Salesman Problem)[1]中，旅行商作为移动 Agent 巡游各个目的地，并在目的地决策前往下一个目的地的路径；上文的海域搜索网络中的船只也是一种移动 Agent 用于收集海底潜水机器人发送的数据。
..........................
..........................
1.2 延迟容忍网络和移动节点路径规划国内外研究现状
1.2.1 延迟容忍网络研究现状
延迟容忍网络(DTN)的概念源于星际网络(IPN，Interplanetary Networking)，这个网络主要用于火星太空飞船能够像在地球上那样传递数据[5]。在这样的环境下，研究人员要面对数十分钟的延迟并且受限的和不对称的带宽。Fall[6]通过强调当 IPN 和 DTN 描述地球和太空之间通信的场景所使用的方法一致，来将 IPN重命名为 DTN。经过多年的研究和发展，DTN 的体系结构和相应的协议逐步完善。由于 DTN 本身的特点——长延迟、数据包丢失严重、连接间歇、链路故障等基本特征，使得 TCP/IP 协议栈在这些受损甚至专有的情形下，比如加强代理效果，都不能解决掉最具有挑战性的环境问题，也不能创建出当前的安全协议。所以当前许多成熟的网络协议都不能直接使用在 DTN 这种特殊的网络中。
1.2.1 延迟容忍网络研究现状
延迟容忍网络(DTN)的概念源于星际网络(IPN，Interplanetary Networking)，这个网络主要用于火星太空飞船能够像在地球上那样传递数据[5]。在这样的环境下，研究人员要面对数十分钟的延迟并且受限的和不对称的带宽。Fall[6]通过强调当 IPN 和 DTN 描述地球和太空之间通信的场景所使用的方法一致，来将 IPN重命名为 DTN。经过多年的研究和发展，DTN 的体系结构和相应的协议逐步完善。由于 DTN 本身的特点——长延迟、数据包丢失严重、连接间歇、链路故障等基本特征，使得 TCP/IP 协议栈在这些受损甚至专有的情形下，比如加强代理效果，都不能解决掉最具有挑战性的环境问题，也不能创建出当前的安全协议。所以当前许多成熟的网络协议都不能直接使用在 DTN 这种特殊的网络中。
DTN 体系结构和协议的产生主要归功于 IRTF(Internet Research Task Force)的 DTN 研究小组(DTNRG)[7]。DTNRG 是一个开放的研究小组，它有来自很多国家和组织的成员，其中来自 CCSDS(Committee on Space Data Systems)的成员主要致力于太空通信研究。到目前为止，DTNRG 成员已经开发了很多开源和非开源的 DTN 网络协议，这些协议已经在实验室环境和真实世界中进行试验[8]。2004-2009 年，美国 DARPA 组织自助了一项延迟容忍网络的项目，该项目关注的场景时链路损耗很快，但通常是较短的终端，而不再是太空中的那种长时间的延迟。
国内 DTN 研究现状主要包括：陈曦[9]根据网络编码能够在苛刻的网络环境中充分利用网络带宽资源，进而增强 DTN 的容错性，提出了对 DTN 路由算法进行网络编码的研究。该文章针对 DTN 路由算法中存在较大网络开销的节点提出了基于解码预判的数据传输算法(HLDA)以及针对当前 DTN 路由算法数据传输的冗余开销提出了基于动态分段网络编码的高效路由算法(ERBNC)。赵红敏等[10]提出了一种基于节点密度、运动速度、生存期等因素的消息转发算法 Multi，进而充分利用了 DTN 中各个节点的资源，并克服了瘟疫路由算法、标记算法等不区分节点资源的缺点。邓广宏[11]等提出了一种 DTN 中基于生灭模型的节点运动模式检测方法，并将该方法应用到喷射路由(SWR)和随机网络编码路由(RNCR)上面，提高了 DTN 机会路由的投递率和投递延迟。
...............................
第 2 章 延迟容忍网络和移动节点路径规划概述
2.1 延迟容忍网络概述
TCP/IP 协议在互联网设备之间的互联通信方面取得了巨大的成功。然而，它是建立在一定的假设的基础上的，该假设包括有线连接、端到端的持续连接以及源节点和目的节点之间的低延迟等条件。
近年来，随着设备配备了无线接口，用户逐渐发现他们所处的网络环境不再是上述中的有线网络环境了。这些新环境包括各种各样的连接形式，包括全局的联通网络，比如蜂窝网络或者由独立移动设备形成的非连接网络。特别地，有智能手机组成的无线移动网络具有以下特征：
2.1 延迟容忍网络概述
TCP/IP 协议在互联网设备之间的互联通信方面取得了巨大的成功。然而，它是建立在一定的假设的基础上的，该假设包括有线连接、端到端的持续连接以及源节点和目的节点之间的低延迟等条件。
近年来，随着设备配备了无线接口，用户逐渐发现他们所处的网络环境不再是上述中的有线网络环境了。这些新环境包括各种各样的连接形式，包括全局的联通网络，比如蜂窝网络或者由独立移动设备形成的非连接网络。特别地，有智能手机组成的无线移动网络具有以下特征：
(1) 间歇性连接：由于设备的移动性，连接链路通常是瞬时或很短时间的联通。
(2) 较长或变化的延迟：节点之间的数据传输和节点的可变的排队延迟导致端到端的延迟，这种延迟会使得依赖于快速数据反馈的互联网协议和应用难以使用。
(3) 不对称的数据率：互联网支持中等双向数据率的不对称性，但是如果不对称性很大，那么传统的协议就难以胜任。
(4) 高错误率：链路上的位错误需要纠正(通过增加冗余和处理时间)或者重传机制来保证。对于一个给定的链路错误率，两跳之间的重传次数要比端到端之间的重传次数要少得多。
(2) 较长或变化的延迟：节点之间的数据传输和节点的可变的排队延迟导致端到端的延迟，这种延迟会使得依赖于快速数据反馈的互联网协议和应用难以使用。
(3) 不对称的数据率：互联网支持中等双向数据率的不对称性，但是如果不对称性很大，那么传统的协议就难以胜任。
(4) 高错误率：链路上的位错误需要纠正(通过增加冗余和处理时间)或者重传机制来保证。对于一个给定的链路错误率，两跳之间的重传次数要比端到端之间的重传次数要少得多。
延迟容忍网络(DTN)[21]又称分裂容迟网络(Disrupt Tolerant Network)，它是一类特殊的网络，在这种网络当中，节点到节点之间的通信路径通常很难建立，因为网络中的节点的位置是动态变化的，所以网络中的消息的传播具有很大的延迟，这使得传统的以太网上基于 TCP/IP 协议很难适用于此种网络。
.............................
2.2 移动节点路径规划方法概述
移动节点路径规划问题最早是由 Dentzig 和 Ramser 于 1959 年提出，该问题很快应用到了运筹学、应用数学、组合数学、物流科学等技术当中，并逐渐发展成为运筹学组合优化领域的热点问题。各种各样的实际问题对应的移动节点路径规划的解决办法也不尽相同，在众多的问题中的解决过程中使用了很多的基础算法，下面几个章节简要概述了常用的移动节点路径规划的算法。
2.2.1 动态规划算法
动态规划(dynamic programming)[23]是通过组合子问题的解来求解原问题的解，它主要应用于子问题重叠的情况。在子问题重叠的情况下，动态规划算法对每个子问题只求解一次，将其解保存起来，从而无需每次求解相同的子问题，于是就避免了不必要的计算过程，提高了效率。
动态规划算法一般用于求解最优化问题，其有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和重叠子问题性质。
(1) 最优子结构性质：是指源问题的最优解一定包含其子问题的最优解。
(2) 重叠子问题性质：是指原问题分解的子问题在递归算法求解时会计算多次，动态规划算法利用这个特征将已求解的子问题的解存储，以供以后相同的子问题调用。
2.2 移动节点路径规划方法概述
移动节点路径规划问题最早是由 Dentzig 和 Ramser 于 1959 年提出，该问题很快应用到了运筹学、应用数学、组合数学、物流科学等技术当中，并逐渐发展成为运筹学组合优化领域的热点问题。各种各样的实际问题对应的移动节点路径规划的解决办法也不尽相同，在众多的问题中的解决过程中使用了很多的基础算法，下面几个章节简要概述了常用的移动节点路径规划的算法。
2.2.1 动态规划算法
动态规划(dynamic programming)[23]是通过组合子问题的解来求解原问题的解，它主要应用于子问题重叠的情况。在子问题重叠的情况下，动态规划算法对每个子问题只求解一次，将其解保存起来，从而无需每次求解相同的子问题，于是就避免了不必要的计算过程，提高了效率。
动态规划算法一般用于求解最优化问题，其有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和重叠子问题性质。
(1) 最优子结构性质：是指源问题的最优解一定包含其子问题的最优解。
(2) 重叠子问题性质：是指原问题分解的子问题在递归算法求解时会计算多次，动态规划算法利用这个特征将已求解的子问题的解存储，以供以后相同的子问题调用。
一般而言，对于某个问题能否可以使用动态规划算法来解决，首先是要分析该问题是否符合动态规划的上述两个基本特征，然而在众多问题当中能够同时符合以上两种特征的问题很少。动态规划的最优子结构性质要求问题可以由大问题划分为小问题，而小问题同样是原问题的缩影，只有这样才能够使用动态规划思想中的迭代或递归求解步骤，在现实生活中的问题当中，这种形式的问题很多，例如背包问题，旅行商问题，矩阵相乘问题等等，这些问题都满足大问题中的小问题符合相同的模式，所以可以使用相同的求解方案进行迭代求解。重叠子问题的性质要求所要解决的原问题的子问题具有解的重叠部分，这一点在很多的问题中是很难达到的，例如在船只在收集潜水机器人收集信息的路径规划的问题中，船只在每次要离开当前节点前往下一个节点的决策和上次的决策是否有重叠部分是由探测的环境决定的，对于一种情况，潜水机器人每次出现的时间间隔并不是一个固定值，那么整个问题很难分析是否符合最优子结构，及重叠子问题的特征，这样就不能直接使用动态规划的思想解决。
...............................
...............................
第 3 章 多静态节点 DTN 中高效数据收集算法研究 ............................................. 14
3.1.1 问题描述.............................. 14
3.1.2 目标问题.............................. 14
第 4 章 多静态节点 DTN 中最优数据分发算法研究 ............................................. 27
4.1 问题描述..................................... 27
4.2 目标问题和相关问题..................................... 28
4.3 系统模型................................... 30
第 5 章 总结与展望.................................... 45
5.1 全文总结................................ 45
5.2 研究展望.................................... 45
第 4 章 多静态节点 DTN 中最优数据分发算法研究
4.1 问题描述
移动 Agent 在多静态 DTN 中的数据分发应用中充当着重要的角色。大城市中的救护车路径选择问题是多静态节点 DTN 网络的一个应用，在这种模型下，救护车就充当多个移动的 Agent，它们的任务是将病人运送到合适的医院进行治疗，本章题目中的数据只是一个抽象概念，在本场景中，数据代指病人。
4.1 问题描述
移动 Agent 在多静态 DTN 中的数据分发应用中充当着重要的角色。大城市中的救护车路径选择问题是多静态节点 DTN 网络的一个应用，在这种模型下，救护车就充当多个移动的 Agent，它们的任务是将病人运送到合适的医院进行治疗，本章题目中的数据只是一个抽象概念，在本场景中，数据代指病人。
在文章[43]中指出，在紧急治疗事件当中，除去救护车运送病人的时间，预约挂号也是一项影响治疗延迟的重要因素。当危急病人被送进医院，这个病人就会被分配给一个病床，并且有一个医生为他进行下一步的治疗。在中国和印度[44,45]，当没有足够的病床时，一些危急病人如果不能被妥善安排，他们就可能会死亡，这种现象也就导致了紧张的医患关系[46]。传统的局部病人-医院贪心分配算法会以先来先服务(First-Come-First-Serve)的方式把病人分配到时间延迟最短的医院。但是这种算法有严重的缺陷，例如，当一个危急病人来到医院，恰巧这个医院没有多余的病床，这是可能是因为有些病床已经被非危急的病人占用了，那么此种情况就强迫救护车将病人运送到下一个可用的更远的医院，这样就可能会产生致命的时间延迟[47]。上述情况主要源于非危急病人有较小的运送延迟或者他们在危急病人被送来之前就已经占用了宝贵的医疗资源。如果遇到危急病人数量暴增[48]的情况下，需求的医疗资源会远远多于医院已有的医疗资源。因此必须平衡每个病人的运送时间延迟并提前为危急病人预留一些医疗位置(比如病床)。
...............................
第 5 章 总结与展望
5.1 全文总结
参考文献（略）
第 5 章 总结与展望
5.1 全文总结
参考文献（略）