英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
研究Ad-hoc路由策略负载
摘要：运用在有线网络中的路由算法最先对无线路由协议产生深远影响。当然，拓扑结构的变化和点对点控制消息的隐性约束所造成的负载，意味着大量花销都花费在“修复”上，以适应无线环境所造就的复杂情况和机遇。本文中，我们分析和比较最广泛使用的无线ad hoc网络（MANETs）路由协议。特别地，我们考虑协议的路由和控制负载，存储需求，和网络建设花销，来分析它们有多适合拥有有限资源的MANET节点。
关键词：Ad hoc网络，路由负载，路由协议。
I．介绍
缺少基础设施的无线通信因其部署灵活性和广泛的应用领域，在近十年中广受关注。这样的无线通信有很多应用，例如：灾难恢复、战地通信、聚会的社交网络互动等。这些都归类于无线ad hoc网络（MANETs）。一个MANET是由无需固定基建或中央控制的无线节点构成的。因此，MANET是缺乏基础设施或基础设施建设昂贵的情况下的极佳选择。例如，已经存在的基础设施可能在地震、海啸、恐怖袭击等灾难中毁坏。救援队伍可以通过建设快速MANET进行通信，而无需重建被毁坏的基础设施。
节点的无线电范围定义了它能够简单广播与邻居构建通信的邻域。当然，由于干扰和能耗的存在，不可能有很大的无线电通信范围。因此，节点需要有一个适中的范围和传输功率以构造一个多跳的网络。由于节点的移动，这个网络的几何结构时时变化。因一个无线电信道上通信的有限范围，节点位置超过范围就需要有中继节点作为路由节点。最终，移动和缺少基础设施的节点再加上资源约束（带宽和电池能量），这也使得这种网络中的路由问题更具挑战性。
MANET的标准分类方法是：先应式路由，即，想要维持需参与的每个节点的即时路由信息的一类路由[1]-[3]；反应式路由，即，仅在明确需要维持实际会话时收集需要的路由信息[4]-[9]。另有一些例外（如[10]），路由策略假设点对点通信，通过每个传递数据包至目标节点的节点发送给一个特定的邻居。如果邻居节点的身份和/或位置未知或不确定，洪泛被用来实现路由发现。路由的另一种方法是依靠无线设备的地理坐标（位置）（设备可以通过GPS获取它们的位置信息）。它们需要知道邻居节点和目标节点的位置以路由一个数据包，而不是在节点中维系详细的路由表。这一类路由策略被称为无记忆或无状态基于位置的路由[11]-[14].
本文的焦点：过去几十年中大量MANET路由协议被提出。我们以上述三类大致分类这些协议。本文的焦点在于从这些分类中选择最为领先（和广泛使用）的策略，分析其数据、控制、路由、和资源有限节点上的存储负载。因此，MANET路由的研究人员能够得到一个目前科研水平的大致描述，根据在现实生活中可能的应用选择合适的协议。
注意文献包含几篇综述MANET路由方面的[15]-[17]。本文的焦点在于从负载的角度选择出最为广泛使用的路由协议。在[18]中，根据性能分析了分层MANET协议路由负载。[19]做了相似的分析。[20]从优缺点展示了反应式、先应式、混合协议。较之而言，本文在真实环境下根据大量性能参数考虑了先应式、反应式和机遇位置的协议。
我们考虑无线节点构成的ad hoc网络。这种网络的拓扑结构由链路不确定性（环境变化影响下节点间链路的参与和不参与）。这些设备配备以低功率的收发器（电池供电）并，代表性地，具有有限的存储能力（同时包括蓄电能力）。因此，他们可能不能够处理有限条件下的同类路由负载。因此，我们分析和比较先应式、反应式、和基于位置的路由协议以决定其1）数据包负载，2）路由控制负载，3）路由负载，4）存储需求和5）网络构建花销以观察它们如何适应一个资源有限的环境。
我们的分析并给出了关于协议的性能在可扩展性方面的一个观点，即负载越高，协议的可扩展性越低。此外，更高的负载意味着更多的拥塞，反过来说，可能会引入进一步的延迟并影响吞吐量。事实上，消息触发频率可能会影响控制负载。更高的频率维持网络随着重要控制负载更新，频率越高还将额外增加。最后，这一负载造成的能耗增加，负载越高，能耗越高。
在高移动无线网络，MANET链接经常变化；因此，网络的收敛时间通常被定义为协议对于链路变化的反应时间。值得注意的是，变化的链路可能会影响一个节点子集的通信；因此，剩余节点可能需要更新它们的路由信息。一些路由协议可能只需要局部信息来更新链路变化导致的路由信息，而其他人可能需要全局信息。因此，我们可以说，协议的负载是与它的收敛时间有关的；负载越高，这段时间越长。因此，我们的开销分析也提供了一个关于分析协议因链路变化导致的反应时间的观点。
本文的概要：本文的其余部分组织如下：第二节定义了网络模型和无线设备的规范。第三节提出了先应式路由协议。第四节描述了反应式协议，和第五节说明了基于位置的协议。最终我们以结论性评论结束这份手稿。
II．网络模型和设备规范
形式上，MANET被描述为一个N个节点在二维或三维欧式空间构成的集合V。在基于位置的策略中，他假设每个节点都能感知其位置，表示为笛卡尔坐标(x, y)或(x, y, z)。我们假设节点的传输范围是相同的，为R。两个节点之间通信当且仅当其欧氏距离小于等于R。通信能力由相关节点之间的一条边界来表示。最终形成的图为G=(V, E)，为网络的拓扑结构。给定一个G和一对(i, j)，路由的问题是找到i和j之间的一条满足最小化一些目标函数的路径。
我们分析不同的协议来测试不同的负载，看它们是否适合资源有限的环境。为了定量评估，我们考虑无线自组网拥有低占用无线节点MSP430F5438（16位超低功耗单片机256KB闪存和16KB的RAM）和CC1101（低功耗500 kb/s数据速率的SUB-1-GHz射频收发器）来自于Texas Instruments。MSP430F5438每100单位花销6.10，CC1101每100单位花销3.5[21]。注意，我们选择第一节所述三类协议中最具代表性的协议。
III．先应式路由协议
在先应式路由协议中，节点在需要之前维持实时路由信息。这一策略帮助路由找到一条优秀的路径。目标序列距离矢量（DSDV）[3]和簇头网关交替路由（CGSR）[22]是先应式协议的例子。
A．DSDV
1）协议描述：DSDV是无线自组网中较早被提出的协议。它是基于传统的距离向量路由（分布式Bellman-Ford）。在距离矢量路由中，每个节点维护一个到每个目标节点的最佳路径（例如，跳数）路由表，这些路径经过下跳邻居节点构成。表在邻居间定期交流更新。然而，它因链路损坏而存在环和无穷计数的问题。在DSDV中，通过为每个路由入口设定序列号来防止环的产生。节点广播路由更新或任何重大变化。在路由表中的每一个入口包含目的地，到达它的下一跳邻居节点，所需跳数，目标节点所产生的序列号，安装时间（当入口被设置），和稳定的数据。安装时间用于删除陈旧的路由，即，在过去的几次更新期间没有更新的路由[3]。最后一个字段（稳定的数据）是用来确定路由的稳定性，即，路由被认为是稳定的之前不广播更新。这在抑制网络中波动方面有效。
如果看到一个“最近”的更新一个节点将更新一个入口，即，增加序列号（与最后一个相比）。在相同的序列号的情况下，使用较小成本度量的那个。节点移动时，链路可以动态有效或失效。当一个节点检测到链路的一个邻居节点已经失效，它会产生（对邻居的名义）infin;度量值奇数更新（链接失效事件）。这是唯一的情况下，另一个节点产生的序列号，而不是负责度量的节点更新。节点为自己生成的仅为偶数。在拓扑结构中，连接事件信号发生重大变化。因此，有2种方式的广播路由更新：一个是full dump，包含所有的路由信息，和另一个是incremental，只包含最后一个full dump后改变的信息。在有限容量的无线介质中，保持充分的full dump频率是可取的，特别是在低移动性环境。
节点需要确定一个稳定且准备出大更新的目标节点的入口。为此，使用settling time，这是第一次和最好的一次（最少的成本）接收到的目标节点的更新之间的时间差。最后一个存储时间，即，tl，是最新的度量。节点继续给每个目标节点计算average settling time ta。在接收到目标节点的第一次更新后，节点广播之前等待一段时间2ta。这条规则是不适用于链路断的情况，在这种情况下需要立即广播。
2）分析：让我们考虑一个N节点的网络，每一个节点d度（邻居节点数）。序列号S位。节点失效概率为f。网络直径D米。为了计算数据包负载，我们假设数据包形式如表I所示。目标节点和源节点的地址大小为2logN。序列号用完的时间是，其中dXf是每个节点时效链路的均值。因为阻尼波动，我们将图翻倍（使其翻倍从而节点有足够的时间找到去目标节点的最佳路由）获取一个最大延迟的估计值Tmax。序列号耗尽时间必须必最糟糕的延迟时间Tmax大。我们有
注意，由于阻尼波动，我们考虑。因此，序列号造成的负载是。数据包负载时。控制包负载的数据包类型如表II。最先两个字段要求的大小需求。Next hop和hop count需要位。Stable data的负载。因此，总full-dump包负载是。Incremental广播包含着目标节点的位置、序列号和hop count。因此，负载是。DSDV的路由负载是，因为它使用了最短路径路由算法。在最差的情况下，有链路断的可能；因此，每个节点的内存需求为。
数据包的每个字段由32位组成。在full dump的情况下，我们有目的地址和序列号，下一跳，和稳定的数据，每一个有32位。跳数需要8位[8]，但安装时间可能需16位。因此，完整的full dump数据包可以包含160位。如果我们有一个十节点的网络，那么每个节点的内存将是1600位，可以使用2K内存的设备，这将花费15美元。我们可以构建100节点的网络，每个16K内存，将花费400美元。
B．CGSR
1）协议描述：在分层网络结构中，节点被分成几个簇，每个簇度由簇头节点控制。节点可以属于多个簇，并作为簇之间的网关。这种分层结构可能有助于实现更好的信道接入，带宽分配和路由[22]。然而，它也可能导致接下来的次优路由。此外，MANET需要一个聪明的簇头选择程序。在CGSR中，一个簇头选择算法称为最小聚类变化（LCC）被提出，在最初，最低的ID或最高的节点度被用来选择簇头。之后，取代在有明显拓扑变化后使用重选程序，在LCC中，仅在两个簇头相互通信或一个节点移出所有簇头节点的范围时进行簇头重选。当需要路由数据包时，节点首先将其发送给相应的簇头，然后包从簇头到簇头通过网关到达目的节点。每个节点需要维护两个表，即，簇成员表和路由表。第一个记录每个节点的簇头（此表周期性地发送给邻居），第二个维护下一跳节点到达目的地的簇头（见表III）。
2）分析：让个节点成为簇头节点。CGSR使用DSDV作为簇头之间的路由方法；因此，数据包头形式是与DSDV相似的，除了加了一个字段给目标节点簇头。因此，数据包负载是。每一个节点维护两个表。一个表示簇成员表，为了网络中每个节点的保持目标节点簇头。这张表由节点周期性扩展。负载是。另一张表是路由表，每个节点，包含目的簇头和沿路径下跳节点的地址。因此，负载是。路由负载是，RM是簇常规成员的最大数。最终，每节点内存负载为。节点需要保持粗有记录以达到任意节点，当使用分簇时，我们将能够使用100个簇头节点来构建一个更大的网络。
IV．反应式或按需路由协议
这些协议不同于先应式协议节点维护路由的方法。反应性协议只有当它成为明确需要维持一个实际的会话才收集必要的路由信息。在一般情况下，路由进行两个步骤，即，路由发现和路由维护。动态源路由（DSR）[5]，Ad hoc按需距离矢量（AODV）[8]，临时按序路由算法（TORA）[23]、[7]，小Ad hoc路由协议（TARP）[24]，和基于关联性的路由（ABR）[25]是按需路由协议的例子。在下面的小节中，我们将简要介绍这些协议的前四种。
A．AODV
1）协议描述：AODV是DSDV的反应式版本，通过创建按需路由而不是像DSDV那样维系路由列表来最小化广播数量。使用目标节点序列号保持最新的路线，计算最佳路径的DV逻辑。当节点需要将数据包传送到目标节点，而缓存中没有到这个节点的路由时，发起路由发现过程。用于此目的的控制数据包是路由请求（RREQ）和路由应答（RREP）。其形式为。前两个属性代表源地址和序列号，后一个属性和源地址一起唯一标记了一个RREQ，接下来两个属性针对目标节点，HC是跳数计数。在接收到一个RREQ消息后，一个中继节点可能做如下动作：1）如果他是目标节点或有前往目标节点的路由入口在他的缓存里，而目标节点序列号又比RREQ中的大或相等，则发送一个单播，回复消息给源节点；或者2）如果已经收到过这个请求，则丢掉RREQ。否则，中继节点简单地增加跳数并重播RREQ。
RREP消息的形式是 。目标节点序列号比RREQ中的高，HC初始化为0。最后一个属性提供了路由建设所需要的最大期限。单播RREP被D沿着RREQ的路径送返给S。中继节点，在接收到RREP后，生成一个反转路径指向RREP来时的邻居。此外，它更新Dseq-num和超时信息。如果是第一次收到RREP，RREP被送还给生成RREQ的邻居节点。否则，随后的RREP被丢弃以抑制多路径，除非他它们带来更好的跳数D。因此，中继节点同时拥有去S和D的路由，这是该路由发现过程的一个副作用。最后，S收到RREP，这在第一轮时可能不是最佳；然而，最终，它将获得最优路径。路由请求终止计时器是用于清除S和D之间不在路径上的节点的反向路径入口。
AODV中的节点为在线的目标节点维护路由表入口。这些入口以的形式存在。下跳节
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[28814]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
