前言:研究生第一个任务就是研读李建波和肖明军著的<容迟网络中的路由算法>,
以下是我前两章节的笔记(摘抄?)
还有部分内容出自:
2008_机会网络_熊永平
2009_机会型网络研究综述_胡四泉
2009_容迟网络路由算法_肖明军
2010_机会网络路由协议_任智
单跳网络
在传统无线局域网(WLAN)中,每个客户端均通过一条与固定的接入点(AP，Access Point)相连接的的无线链路来访问网络(星形网络)，用户如果要进行相互通信，必须首先要访问一个固定的接入点（AP），这种网络结构被称为单跳网络。单跳网络有很明显的缺点，就是健壮性不强，如果固定的AP发生故障，那么该网络中所有的无线设备都不能进行通信。
多跳网络
Mesh网络也称为多跳网络，它是一个动态的可以不断扩展的网络架构，并能有效地在无线设备之间传输。与单跳网络有很大不同的是，Mesh网络中任何无线设备节点都可以同时作为AP和路由器.这样设计的好处:如果最近的AP由于流量太大而拥塞的话，那么数据可以重新选择一个小流量路径进行传输.数据包根据网络的情况，从一个节点一次传送到多个节点，最终到达目的地，这样的访问方式就是多跳访问。
Mesh网络与传统的单跳无线网络有3个明显的优点：强壮性、高带宽和高利用率。
强壮性：由于Mesh网络中任何无线设备节点都可以同时作为AP和路由器，每个节点都可以与一个或多个对等节点直接进行通信，当某个AP发生故障并不会引起网络的瘫痪。而单跳网络如果固定的AP发生故障，那么该网络中的所有无线设备都不能进行通讯。
高带宽：从物理的角度而言，无线通讯意味着通讯距离越短，那么通讯的效果会越好，因为随着通讯距离的增长，无线信号不但会衰弱而且会相互干扰，从而降低数据通讯的效率。而Mesh网络中，是以一段段较短的无线网络连接代替了长距离的连接，从而保证数据可以以高速率在节点之间快速传递。
高利用率：在单跳网络中，一个固定的AP被多个设备共享使用，随着网络设备的增多，AP的通讯网络可利用率会大大下降。而在Mesh网络中，由于每个节点都是AP，根本不会发生此类问题，一旦某个AP可利用率下降，数据将会自动重新选择一个AP进行传输。
Ad Hoc网络
移动自组织(Ad Hoc)网络是一种多跳的临时性自治系统，源于ALOHA(美国建立)网络。ALOHA网络需要固定的基站，网络中的每个节点必须与其他所有节点直接连通才能相互通信，是一种单跳网络。发来发展处PR（Packet Radio）网络，才出现了真正意义上的多跳网络，网络中的各个节点不需要直接进行连接，能够在两个距离很远而无法直接通信的节点之前传送信息。PR网络被广泛的应用于军事领域，IEEE在开发802.11标准时，提出将PR网络改名为Ad Hoc网络。
自组织网络存在的问题：
1.节点移动、节点系数、射频关闭或障碍物造成信号衰减等多种原因都可能导致网络大多数时候不能连通。
2.传统的MANET（mobile Ad hoc network）在传输数据之前，需要预先建立通信端点之间的路由，这种工作模式隐含了一个重要的假设：网络大部分时候是连通的，任一节点对之间存在至少一条完整的端对端的通信路径。
什么是容迟网络？与机会网络有什么联系？
机会网络的许多概念来源于容迟网络（Delay Tolerant Network ，DTN）。容迟网络泛指部署在极端环境下由于节点的移动或则能量调度等原因而导致节点间只能间歇性进行通信甚至长时间处于中断状态的一种类网络。DTN一般由多个传统Internet类型的子网组成，不过子网之间的连接不是一直存在的，它们之间的连接有时是按照时间进行调度的，有时完全随机的。DTN的特点是网络时断时连，网络延迟通常比较大。网络拓扑经常发生变化。一般的DTN不一定是无线网络，也不一定是自组网络，因此机会型网络可以划分为DTN和MANET的子类。机会型网络与DTN要面对的主要问题是类似的，也即是网络时断时连，它们都采用的是存储转发的模式进行路由。
容迟网络的体系结构
通过对信息交换的抽象，引入了捆绑层（bundle layer），将容迟网络设计为一个位于不同网络之间协议栈之上的覆盖层网络，并在不同网络之间提供存储转发的网关功能。
通过在传输层和应用层之间添加一个捆绑层，DTN采用存储-携带-转发的消息交换机制。消息数据被封装在一个个的消息束中，束是长度可变的具有特定格式的基本数据单元，捆束层最终负责存储和转发所有的束。
捆绑层结构的主要特征如下：
1.可以划分不同区域并且通过网关来连接不同网络体系结构和协议栈的区域。
2.名称元组，形式为{区域名，实体名}，区域名是全球唯一的，实体名是区域内唯一的。
3.邮政投递式服务（postal-style delivery service）实现基于优先级的资源分配和消息传输机制。分别有三个优先级：Bulk、Normal和Expedited分别对应低，中，高优先级。
4.路由选择，DTN在路由和转发框架中被定义成一个多重图，即节点之间可能存在多条连接边。
5.可靠性和保管传输。保管传输是为了保持端到端连接状态，并应对高丢包率和资源缺乏而提出的概念。DTN将体系将节点分为持久的（persistent）和非持久的（non-persistent）两类，前者拥有足够资源，后者资源相对不足。DTN面临这很高的消息丢包率，需要确保那些不具备足够资源的节点不必去承担和维持端到端可靠性传输的任务，因此，一旦被保管的消息束被传递至下一个Persistent节点，源节点便不必继续维持该消息束的副本。
6.聚合层（convergence layer）。DTN体系结构由底层所提供的功能可能存在着显著的变化，例如可靠传输、流量控制、拥塞控制等。假设底层可以实现可靠传输则需要增加一个包含特定聚合层的协议栈来确保这些底层功能的实现。
7.时间同步（time synchronization）。DTN体系结构要求通信节点之间的时间同步。
8.流量控制(flow control)和拥塞控制(congestion control)。DTN体系结构中的流量控制是指限制DTN节点的发送速率以匹配下一跳节点的接收速率。流量控制决策必须在捆绑层内进行，尽管其可能需要下层传输层的支持。拥塞控制是指处理对DTN网关中持久存储资源的竞争。
9.安全。防止未经授权的应用程序利用网络资源，防止被授权应用程序访问比其自身等级跟高的服务。
LTP传输协议
LTP（Licklider transmission protocol）传输协议用来提供基于消息重传机制的可靠性保障，并且应对消息往返时间过长及连接频繁割裂等特征。LTP协议工作于数据链路层以上，捆绑层以下（传输层和网络层），覆盖于各种使用不同协议的区域之上，向上提供统一的接口。
TLP协议有几个特点：
1.数据块分为红部(red-part)和绿部(green-part)两部分。其中红部数据传输时必须使用确认和重传机制，这样就保证了红部数据的可靠传输，类似于TCP；而绿部数据的传输是尝试性地，因而没有采用这种可靠机制，类似于UDP。
2.LTP协议中的数据块是分段的。数据块中红部的最后一段是红部的结束部分（end of red-part,EORP）。当接受者收到这部分数据时，表示红部的传输已经结束，此时接受者必须向发送者发送一条确认信息，表明该部分数据已经全部收到。当发送者发送完这部分数据之后，会启动弄一个计时器，如果在限定时间内发送者没有收到接受者的确认信息，该红部数据就会被自动重传，这种机制确保了信息传输的可靠性。整个数据块的结束部分叫做EOB（end of block）。
3.TLP数据流是单向的，TLP的确认和重传报文并不直接附着在数据段之后，而是被封装在一个单独的数据段中。
4.推迟传输（deferred transmission）是LTP中一个重要的概念，TLP协议本身提供当前连接的状态，用以确认数据的可行。
5.LTP依赖于对报文到达目的节点时间的准确计算，这样做是为了确保能够在正确的时间实施报文重传。对于报文到达目的节点的时间，下界要比上界更严格。
6.当发送者收到红部数据丢失或损坏的信息时，就会启动重传机制。
7.LTP通过Authentucation和Cookie两种机制来解决安全性问题。Authentication机制可以确保数据段的真实性和完整性，Cookie机制则增加了LTP引擎遭受拒绝服务（Dos）攻击的难度。
什么是机会网络?
传统的MANET的研究对象是Mesh网，其基本假设是消息源和目标节点之间存在至少一条完整的连通路径。如果消息发送节点和接受节点是不连通的，那么某一时刻消息会被抛弃。与传统的MANET不同的是，在机会型网络中，不存在“消息源和目标节点之间存在至少一条完整的连通路径”这一假设，甚至在任何时间点都不存在这样一条路径。在实际的应用当中，无线自适应网络的拓扑结构可能随时发生改变，其连通性往往不能得到保证，信息源节点与目的节点之间不存在数据通路。在这种需求下，使得机会网络的有了“用武之地”。通信源和目标不存在数据通路，不意味着不能进行通信，由于节点的移动，两个节点相互进入通信范围而交换数据，机会网络就是利用这种节点对之间的逐跳转发将数据从源节点传输到目标节点。
从整体上来看机会型网络是稀疏部署的，但在局部可以是密集的，从而在局部可以形成传统的连通的自组网，称为连通岛（islands）或则云（clouds）。由于节点运动经常发生断连，这种连通岛在不断动态地形成、变化或则消失。这种结构是急剧动态演化的，移动设备之间的“相遇”也是不断变化的。按照这种观点，传统的互联网连接恰恰是一种特殊的“机会连接”情形。
机会网络是一种不需要源节点和目的节点之间存在完整链路，利用节点移动带来相遇机会实现网络通信的自组织网络。
机会网络是不要求网络的全连通，更适合实际的自组网需求，域间网关利用“存储-转发”的模式工作，当目标DNT（delay tolerant network）域的链路存在时转发消息，将消息存储在本地持久存储器中等待可用链路，机会网络可用看成是具有一般DTN网络特征的无线自组网。
机会网络研究的热点问题
目前，机会网络研究热点问题主要包括3个方面：机会转发机制、节点移动模型和基于机会通信的数据分发和检索等。
机会转发机制
机会网络不要求网络全连通，为了在不连通的网络中实现节点通信，机会网络中的路由机制以“存储-携带-转发”的模式工作，在这种模式中，当路由表中不存在去目标节点的下一跳节点时，将消息在当前节点上缓存，并随着当前节点的移动以等待合适的转发机会。针对每个消息确定最好的下一跳转发节点和选择合适的转发时机就成为设计高效机会网络路由协议的关键问题。
按照是否利用网络状况、规律、基础设施等知识来增进路由效率。可以将机会型路由算法分为两大类：不基于知识的路由（non-know ledge based routing）和基于知识的路由(knowledge based routing)。不基于知识的路由在设计消息传递策略时不包含对网络知识的提取和对传递的预测。基于知识的路由算法需要提取网络某些方面的特征对路由进行优化。
不基于知识的路由
基于复制的转发
该机制中，同意消息的多份拷贝被注入网络，当其中一个到达目标节点时，消息传输成功。其核心问题是确定优化的消息拷贝数和产生消息拷贝的方式。
直接传输（direct transmission,DT），源节点缓存消息直到遇到目标节点才转发。很显然，在机会型网络中，源节点与目的节点相遇的概率可能很低，甚至为零。这样的方式,网络开销最小，但传输时延大和传输成功率最低。
两跳中继多次复制（2-HOP）算法是利用源节点将消息拷贝给最先遇到的L个中继节点，源节点和L个中继节点只讲消息转发给目标节点，消息需要通过两跳到达目标节点。很显然，该协议比直接递交协议小号更多的带宽和存储空间，但是更有可能将消息传输到目的节点，能有效增加移动自组网的容量。
Binary Spray and Wait 在源节点指定消息允许的最大拷贝数为L，并使用基于二叉树的方法来产生L份拷贝，该机制由两个阶段组成：Spray阶段（喷洒报文），在遇到没有缓存该消息的中继节点时，将消息拷贝给节点，并将剩下的拷贝任务分成两半，由该邻居节点完成[（L-1）/ 2]，自身完成剩下的部分[（L-1）/ 2]，当节点剩下一份拷贝任务时，节点转入Wait阶段，每个节点值持有该报文的单一副本，这些节点仅仅是等待，直到遇到报文传输的目标阶段是，才将报文转发给该节点以完成该传输过程。
传染转发（epidemic forwarding, EF）机制中，每个节点维护一个消息队列，当两个节点相遇时，交换对方没有存储的消息。本质上是一种洪范算法，每个携带消息的节点都讲消息转发给所由遇到的邻居节点，如果网络带宽和缓存等资源足够，EF机制可以保证找到到达目标节点的最短路径，而由于实际网络节点宽带和缓存等资源有限，随着网络节点数的增大，其性能由于广播导致拥塞会急剧下降，相比前几种消息拷贝数固定的算法，EF机制可扩展性很差。
基于编码的转发
基于编码的路由协议的设计理念是在发送前将要发送的消息进行编码，变化为另一种形式——多个数据块，并将其他信息嵌入到被编码后的数据块中，使得接受者可以从一定数目的编码块中重构原始消息。基于编码的转发机制在网络拥塞或链路信号差导致丢包时具有很好的鲁棒性，而且传输的消息总数不会随着网络规模和节点密度而发生变化，可以很好地控制网络开销，具有良好的可扩展性。编码的目的是减少洪范的发生。
可擦除编码（erasure-coding , EC）的机会转发机制，源节点先将数据分成m个块,然后将这些数据块编码成k个小消息，目标节点只需要接收到k个消息中的任意[ m x (1 + ε ) ]个小消息就可以重建原始数据。ε 是由具体编码算法确定的小常数。该机制中源节点将编码后的小消息平均分配给k个相遇的中继节点，每个中继节点携带部分小消息直到遇到目标节点。
H-EC，每个编码后的小消息生成两个拷贝，当遇到邻居节点时，首先将消息的第一份拷贝传输给该节点，然后在该连接持续时间，将其他消息的第二份拷贝转发给该节点，通过充分利用每次连接机会取得更好的传输性能。
随机线性网络编码的机会转发机制，将不同消息源的消息映射到一个有限域形成一个信息向量，中间节点利用随机生成的编码向量将接受到的特定个数的消息线性编码成新向量，重新注入到网络中，当目标节点接受到足够消息向量时可以解码处原有消息。
基于知识的路由算法
基于知识的路由算法中，根据路由决策的制定提取网络信息。根据网络条件预测和选择中继节点，从而在最佳路径上转发消息。具体来说，不同类型的网络知识导致不同类型的路由算法。一个协议可能使用不同类型的网络参数中的一种或则多种。典型的网络参数有连接状态、传输成功率、节点相遇频率、控制节点运动规律。甚至基于网络踪迹抽象出来的网络模型也可以作为网络知识来辅助路由决策。
基于相遇预测的转发
在基于相遇预测的机会转发机制中，每个节点都维持一个与目标节点相遇的预测概率，可以通过节点的历史移动轨迹来预测该概率。
PROPHET（probabilistic routing protocol using history of encounterts and transitivity）综合了传染转发和基于相遇预测转发,与ZebraNet机制相似，每个节点估计到达其他节点的相遇概率，该节点相遇时升高，否则随着时间递减。而PROPHET中概率的更新使用了概率的传递性，即节点a有可能遇到节点b，而节点b有可能遇到节点c，则a可以成为目标节点c的消息转发节点。节点相遇时PROPHET将到达目标节点概率比自身高且对方没有缓存的消息传输给对方，降低了传染转发广播引起的拥塞导致的性能影响。
Spray and Focus(SF)，SF改进了Spray and Wait（SW）中的Wait阶段，下图对比了SW和SF两种转发机制的工作过程，其中，深色节点表示携带消息拷贝的节点，颜色越深，节点的效用值越大。Spray阶段将消息分发到L个不同的中继节点后，SW机制中L个不同的中继节点将等待直到遇到目标节点，而SF机制中，消息不断地从效用低的节点转发到效用高的节点，直到遇到目标节点。当节点效用值在网络分部适当时，SF机制可极大地提高传输性能。
基于节点主动运动的转发
在基于节点主动移动的转发机制中，部分特殊节点主动移动为其他普通节点提供通信服务。DataMULEs系统通过引入移动节点来实现稀疏传感器网络的数据收集。稀疏部署在观测场景中移动且具备通信功能的车辆或动物MULE节点，在移动过程中收集传感器数据，并以单跳或则多跳的方式将数据转发到接入骨干网的AP节点。
Message Ferrying（MF）使用Ferry节点主动移动实现稀疏MANET中的数据传输，Ferry节点是部署区域内的一个特殊节点，它按照预定义路径或则普通节点通信请求而规划处的路径来移动，源节点将数据装在到Ferry节点，Ferry节点在移动过程中将数据转发给附近的目标节点。
节点移动模型
节点移动模型描述了节点的移动模式,包括位置、速度等特征的变化，广泛应用于自组网协议性能的分析和评价，是自组织网络的基础研究之一。机会网络中的移动模型研究是以刻画节点相遇特征为核心的。这是因为在机会网络中的数据传输以来于节点移动带来的相遇机会，而节点的相遇概率和相遇问题分部是由节点的移动模型决定的。研究表明，传统网络的随机路点（way-point）运动模型并不适合机会型网络性质的描述和性能分析。当前无线王国研究者大多数基于模型或则仿真模型，由于无线信号在实际空间传播的复杂性以及缺乏对无线应用及用户行为的理解，这些模型往往具有很大的局限性，因此无线网络和移动计算的研究者很需要实际数据。不论是使用公开的踪迹数据集，还是采用研究者自己采集的私有数据集，目的都是为了理解网络特点和用户移动模式，为设计和优化算法提供支持。
独立同分部的理论移动模型
3个经典的独步同分布移动模型：Random Way Point（RWP），Random Walk（RW）和Random Direction（RD），在这些模型下相遇节点特征可用两个参数来刻画：相遇时间（meeting time，MT）和相遇间隔时间(inter meeting time，IMT)，MT是指两个节点从静止开始到第一次相遇（进入通信范围）经过的时间间隔，而IMT是指两个节点前后两次相遇的时间间隔。
基于统计的实际移动模型
通过分析文献中的数据集发现，实际节点的移动具有社区特征性节点相遇时间服从近似的幂律分布。
基于社区的移动模型
这是一个由人组成的机会网络节点移动实际表现出的社区特性，该模型下的节点并不是随机选取移动位置，而是考虑了3中情况来决策下一步移动位置：1）节点偏好，节点比其他节点更倾向于去网某个特定位置或遇到特定节点； 2）节点异构性：某些节点能够到达所有位置/遇到所有其他节点 3) 行为时变性:节点移动随着时间变化
基于机会通信的数据分发和检索
由于机会网络以”存储-携带-转发”模式传输数据，每个转发节点都会缓存转发的消息，这种特征使得内容存储称为机会网络的核心服务。机会网络将存储和路由机制结合在一起管理，支持基于内容的组网，即网络中消息的流动是由内容驱动，而不是以分组为单位。
基于机会通信的数据分发和检索使用基于内容的路由方式传输数据，消息的传输没有完全采用传统网络通信中根据分组目标地址进行转发的方式，这类面向特定应用的机会网络，充分利用了机会网络传输自包含的数据消息而不是传统的分组特性，减轻了传统网络中在不连通网络中通信端点交互过多的低效问题。
机会数据分发机制
在机会网络中的是维护及分发过程中，请求节点首先发布定于请求或兴趣消息，产生资源数据的节点将数据分发给感兴趣的节点。
机会数据检索机制
基于机会通信的数据检索过程由请求节点驱动，请求节点在网络内发布查询消息，存储对应数据的节点返回结果消息到请求节点。