路由算法移动多跳的AdHoc网络.doc

路由算法移动多跳的Ad-hoc网络Mesut Gunes, Otto Spaniol摘要： 移动Ad-hoc网络（MANET）是通过广播形式移动节点集合。这些网络有一个重要的优势，它们不需要任何现有的基础设施或中央管理。因此，移动Ad-hoc网络适合临时的通讯联系。但是这种灵活性是有代价的：由于频繁拓扑的变化，很难组织沟通。 本文提出了一种新的按需路由算法，移动多跳Ad-ho网络。该算法基于蚂蚁算法，是一类群体智能。蚂蚁算法尝试映射蚁群的解决问题的能力，来解决数学和工程问题。Ant-Colony-Based路由算法（ARA）具有高度灵活性，高效性，和可扩展性。该算法设计的主要目标是减少路由开销。此外，我们通过模拟结果比较ARA与其他路由协议，包括DSDV，AODV和DSR协议的性能。 关键词:Ad-hoc网络，移动自组网，路由 1.引言 一个移动多跳Ad-hoc网络（MANET）是一套移动节点广播和沟通不需要任何基础设施。这种网络非常灵活，适合多种应用，因为它们允许没有任何预先安装的基础设施（见图1）。由于无线接口传输距离有限，在大多数情况下的沟通，要通过中间层节点中继。因此，移动多跳Ad-hoc网络的每个节点也必须是一个路由器。除了灾难和军事应用领域，移动广告的部署，多媒体应用也是Ad-hoc网络另一个有趣的用途。然而，由于这种网络的性能 ，必须在应用之前得到充分完善。随着新兴的无线技术，如IEEE 802.11a和蓝牙技术，在移动通讯网络实现多媒体应用变得更为现实。找到之间沟通路线的点是移动的多跳Ad-hoc网络的主要问题。问题是通过节点进一步加剧了流动性。近年来提出了许多不同的方法来解决这一问题11，15，但是至今没有适用于所有情况的路由算法。其他方面的移动Ad-hoc网络，特别是节点的动态地址配置4，14，6也有很多人研究。图1：移动多跳Ad-hoc网络。节点 F 移动到节点 G附近本文提出了一个需特设的路由算法，该算法是基于群体智能的。蚂蚁算法是一种群体智能的一个子集，模仿蚂蚁通过合作来解决复杂的问题而不需要直接沟通的能力。这是蚁群算法的一种算法，在最近几年中解决了例如优化问题等问题。为了证明我们的算法是适用于移动多跳Ad-hoc网络，在ns-25有一些基于模拟结果的实施现况。本文的其余部分安排如下：第二节展望了现有的路由算法的移动通讯网络。在第三节,我们现在蚂蚁算法的基本知识。第四节更详细的讨论ARA路由算法的优势和存在的问题。随后,在第五部分提出了一些模拟结果显示性的方法,并将它与现有的路由算法比较。最后,在第六节进行了总结。2.相关工作 2.1目的节点序列距离矢量（DSDV）在传统的距离矢量路由，每个节点维护着节点vD到可能到达的邻居节点vj的距离d(i, j, D)，当一个节点需要选择它的一个直接邻居vj传递数据包,它选择其中最短距离。为了保持距离的时效性，每个节点向其路由表中所有的邻居定期广播。节点接收到来自邻居的广播消息，更新自己的路由表并应用于最短路径算法的算法中,比如Dijkstra算法。Destination-Sequenced的距离向量路由12，11（DSDV）适用于这个环境管理模式的移动Ad - hoc网络。在DSDV，例如当附近的一个节点发生变化，路由信息就会交换新信息。这个过程中产生相当大的开销的Ad-hoc网络。为了减少开销，提出了两种不同的解决方案：完全转储，和增量转储。完全转储包含整个节点的路由表。相反，一个增量转储包含自完全转储部分变化。DSDV通过一个序列号和每个路由表的入口避免循环。这使节点可以区分旧和新之间路由信息。一个节点以最高的序列号选择路由表入口。如果几个线路目的地相同，且以相同的顺序进行编号，则选定成本较低的路由表。2.2特设按需距离矢量协议（AODV协议）特设按需距离矢量协议10，11，13（路由协议）是移动Ad-hoc网络的另一种距离矢量路由。AODV是按需路由方法,即进行不定期的路由信息交换。这个协议包含两个阶段:1）路由发现，2）路由维护。一个节点若想与其他节点进行通讯，会首先从它自己的路由表中选择一条路径。如果找到一条路径则立即开始传递，否则该节点启动一个路由发现。该路由发现过程包括一个广播形式的路由请求消息（路由请求）。该路线发现过程由一个route-request消息(RREQ)发出。如果一个节点中包含一个有效的路径,它向路由请求回复route-reply(RREP)信息。此外,在其反路线进入路由表中建立了一个回复节点所需包含的地址,源节点，跳数的来源，以及下一跳的地址，即节点的地址收到的信息。它们永久相联，即反向路线进入的路线条目如果在规定生命周期内不使用将被删除。第二阶段的协议被称为路由维护。它是由源节点组成，其中可分为:（一）源节点启动一个新的路线源节点的探索过程,(二)目的地或中间节点移动路线的错误信息(如:RERR)被派往源节点。中间节点接收RERR更新路由表设置距离的目标。如果源节点接收到一个RERR路线将开始一项新的路由发现。为了防止全局广播， AODV协议介绍了本地连接的管理，通过包含一个节点的地址和其他信息的HELLO消息路由应答包进行定期交流。2.3动态源路由（DSR）源路由的基本思想是源节点包括将每个数据包的完整路由信息，例如：（vS,V1，V2， VD）发往到VD的数据包，经由V1，V2等。动态源路由7，8，11（DSR）为Ad-hoc网络提供了源路由选择的方法，主要问题是如何获取某一目的地的源路由。DSR使用两个阶段：1）路由发现，和2）路由维护。如果一个源节点vS没有到达指定目的地VD的路由线路，则向其邻居节点广播请求REEQ。该路由请求是一个小包,包含vS,vD，唯一的id RREQ_ID，和LSD（这是节点转交的路由请求清单）。中间节点接收RREQ之后添加到它的LSD，同时向其邻居广播地址,但不向发送RREQ的结点回复信息。如果目标节点VD接收路由要求获取其LSD，则创建一个含有LSD的路由响应RREP返回到源节点。图2显示的DSR路由发现阶段。图2：在DSR路由发现。目的地Vd通过RREP将最短路径返回给源节点。这里使用的度量是跃点的数量。该方法的第二阶段，路由维护。当一个节点vi发送数据包转发到节点 v 它预计将从 V 得到确认。如果在一个特定的时间内vi没有获得任何确认,它将会发送一个包含了该路线转发失败的路由错误信息RERR到源节点。随后,源节点在它的路由表寻找另一个替代路线或启动一个新的路由发现过程。 3.蚂蚁算法 蚂蚁算法是一种群体智能模型中通过合作来解决复杂任务的昆虫群行为。他们是多智能体系统代理表明个体的行为的蚂蚁。参见3，1获取更多信息。 3.1基本蚁群算法 蚁群算法的基本理念是取自蚂蚁的食物搜寻行为。当蚂蚁寻找食物的时候,他们就会从他们的巢走向食物。当一只蚂蚁到达十字路口,它必须决定如何采取下一步。蚂蚁根据沉积的信息素来决定选择那一条路径。信息素的浓度对路径的选择提供了指示。随着时间的推移, 由于信息的扩散效应浓度降低。 图3显示一个场景和两条线路。第一个蚂蚁随机选择一个分支。由于该路线较短，蚂蚁走该路径会第一个到达食物。途中回巢，蚂蚁又必须选择一个路径。过了一段时间较短路径的信息素浓度将高于较长的路径，因为蚂蚁使用较短的路径使信息素浓度增加的更快。因此，最终蚂蚁将只使用这条线路。 蚂蚁的这种行为可以用来在网络中寻找最短路径。特别是在动态的组成部分,该方法提供了高度变化的适应性, 尽管移动通讯网络拓扑结构中存在的这些网络连接是经常发生变化的。 图3：所有的蚂蚁在检索后都能找到最短路径 信息素是一种香豆素，蚂蚁可以识别这种味道。 3.2一个简单的蚂蚁算法 设G =（V，E）为与n =|V|连通的节点。简单的蚁群优化方式可以用来在图G上找到源节点Vs和目标节点Vd 之间的最短路径。节点的编号给出了路径的长度。变量i，J类（人工信息素），它在访问连接顶点vi和vj的边e(i,j) E时由蚂蚁分类。信息素浓度i,j 是使用这条边的表示（象征）。最初i，J对任意边e（1，j）是个常量。 一个蚂蚁位于结点i用结点vj的信息素浓度i,jNi去计算节点vj是下一个跳跃的机率。其中Ni是邻接于结点vi的所有结点的集合。一个结点vi等的过渡机率pi,j等一个蚂蚁访问过结点vi后选择访问结点vj的机率如下定义：在路线寻找的过程中，蚂蚁存放信息素。在算法的简单版本，蚂蚁存放不变的数量信息，对于边 e(vi, vj )当蚂蚁从节点vi移动到vj时，信息数量改变如下： i,j= i,j+ 就像真实的信息素浓度随时间下降，在这个简单的蚁群算法中描述为：i,j (t+):= (1 q)i,j (t), q (0, 1 （1）3.3为什么蚁群算法适用于Ad-hoc网络 简单的蚁群算法在上一节列举了很多原因说明为什么这种算法可以在移动多跳Ad - hoc网络中使用。下面我们讨论与Ad - hoc网络有关的一些重要性质。动态拓扑：在经典的路由算法多跳Ad - hoc网络中此项表现较差。蚂蚁算法基于自主代理模仿蚂蚁系统。这使得高适应当前的网络拓扑结构。 基本工作：与其他的路由方法相比，蚁群算法仅仅基于本地信息,即没有路由表或其他信息块已经被传送到其它节点的网络。链路质量：它将信息素浓度的概念整合到链路中,特别是引入了蒸发过程。这将有助于加强对链路质量的决策过程。重要的是该方法可以修改，以便节点也可以独立的操纵信息素浓度，例如如果一个节点检测到链路的性能变化。支持多路径：每个节点都有一个与所有邻居节点关联的路由表项，其中也包含信息素浓度。对于下一个节点选择决策规则是基于当前节点的信息素浓度。因此，这种方法支持多路径路由。4.蚂蚁路由算法的移动自组网 在这一节中，我们讨论适应于多跳Ad - hoc网络的简单蚂蚁算法，并描述蚁群路由算法（ARA）。路由算法类似于许多其他路由方法由三个阶段组成。4.1路由发现阶段 在路由发现阶段创建新路线。新路线的创建需要使用一个前驱蚂蚁（FANT）和一个蚂蚁（BANT）。AFANT是一个代理，建立了可以回到源节点的信息素轨道。类似的，BANT建立了信息素来源的轨道，即目标节点。FANT是一个有单独序列号的小包。节点能够区分基础序列号和重复的数据包源地址。 节点首次接到FANT时在其路由表创建一个记录。一个路由表项由三部分组成（目的地址，下一跳，信息素的值）。该节点FANT的源地址的作为目的地址,前一节点的地址作为下一跳,并利用FANT经过的跳数计算出信息值。然后节点将其FANT发送给邻居节点。利用唯一的序列号,复制并移动FANT。提取目的节点的FANT信息，创建一个BANT，并返回到源节点。该BANT的任务类似于FANT，即跟踪一个节点。当发送者接收到来目标节点的BANT，则该路径建立和数据包可以被发送。 图4：ARA中路径探索过程a)前驱蚂蚁F从Vs发送到目的节点Vd。前驱蚂蚁穿过其中节点，并初始化它们的路由表和其他节点信息素值。b)后继蚂蚁B与前驱蚂蚁执行相同任务。它从目标节点Vd发送到源节点Vs。图4显示了ARA路由发现阶段。图4 a）显示了信息素是如何返回到源节点Vs的过程。远期蚂蚁只创建一个信息素有望在节点6源节点，但有两个节点5追踪，通过节点3 a和节点4。图4 b）以蚂蚁为落后类似的情况。只创建一个信息素追踪到目标节点 v D在节点5和6两个节点的轨道。因此，多路径路由也支持ARA。 4.2路由维护 该路由算法的第二阶段称为路由维护。这一阶段在通信过程中负责维修线路。不需要为此创建任何特殊的数据包。一旦FANT和BANT为源和目的节点创建了信息素跟踪路径，则数据包可以用来维护道路。如生物系统，建立路径时信息素的初始值不是永远不变的。当一个节点Vi发送数据包到目的地Vd的邻居节点Vj，它增加了条目的信息素值 （Vd，Vj，），即这条道路到目的地是加强了的数据包。同样，下一跳Vj增加了条目信息素值 （vS , vi, ），即后继的路径源节点也得到加强。在真正的信息素蒸发过程以公式1为参考过程。4. 以下是基于图4的例子。下面你会看到节点5和6的路由表。 Dest. NodeNext HopPheromonevSvD.46.12.节点5的路由表 节点6的路由表Dest. NodeNext HopPheromonevSvD.57.34. 、现在，我们考虑两个节点的路由表后，节点5转发数据包到节点6。只有对目标节点Vd的进入改变了节点5的路由表。与节点6的路由表的变化类似，只有源节点Vs发生了改变。节点5与节点6的改变相同。我们进行模拟，其赋值为0.1。 节点5的路由表 节点6的路由表节点5的路由表Dest. NodeNext HopPheromonevSvD.46.12 + .Dest. NodeNext HopPheromonevSvD.57.3 + 4.、信息素值下降的时间间隔为=1秒。以（1-q）=0.1的速度成倍递减（见公式1）。两个节点路由表的增加过程如下： Dest. NodeNext HopPheromonevSvD.46.1 (1 q)(2 + ) (1 q).Dest. NodeNext HopPheromonevSvD.57.(3 + ) (1 q)4 (1 q).Dest. NodeNext HopPheromonevSvD.46.1 (1 q)(2 + ) (1 q).节点5的路由表（秒后） 节点6的路由表（秒后） 上述方法可能会导致不希望出现的循环。ARA通过在路由发现阶段使用循环这种非常简单的方法来防止死循环的出现。节点可以根据源地址和序列号识别数据包的重复收据。如果节点收到一个重复的数据包，它将设置 DUPLICATE_ERROR 标志，同时发送数据包返回到前驱的节点。前驱节点停用这个节点的链接，因此 ，这种数据包不能被发送到这个方向了。 4.3路由故障处理 ARA的第三和最后阶段处理特别节点移动造成的路由，这是移动Ad-hoc网络中常见的故障。正确的设置是在MAC层网络设置ARA的IE802.11。通过对MAC层失踪确认使得ARA不能接收到路线失败信息。如果一个节点接收到ROUTE_ERROR消息时，它首先通过设置信息素值为0来停用此链接。随后，在其路由表另一条节点搜索。如果有另一个目标，则通过该路径发送数据包路由。否则，该节点通知它的邻居，希望他们可以把数据包转发到目的地。无论是数据包可以运到目的地节点或回溯到源节点，如果数据包没有到达目的地，源节点发起一个新的路由发现过程。 4.4 ARA的性能 通过对9的分析，移动Ad-hoc网络应符合下列要求，ARA需要做到： 分布式操作：在ARA中，每个节点在其路由表中拥有一个信息素计数器i,j 用来连接节点Vi和Vj。当蚂蚁路线搜寻，检测链路故障时每个节点独立的控制信息素。 避免循环：路线唯一的序列号使得数据包传输过程避免了循环。 基础需求的操作：信息素计数器i,j使路线有操纵性。随着时间的推移，当蚂蚁不访问节点使对信息素减少量降到最低值。只能由发送者启动路由发现过程。睡眠周期运行：当节点的路由信息素值已经降到较低时，节点可以进入睡眠。除非数据包必须，其他的节点不会考虑这个节点。此外，ARA具有以下属性： 位置：路由表和节点的统计信息，不会传送到其他节点。 多路径：每个节点到达目的地可以有多条路径。例如，路线的选择取决于链接的环境质量。休眠模式：处于休眠模式的节点只处理传送给它的数据包，这样可以节省资源和电量。4.5 ARA的开销预期ARA的开销非常小，因为节点之间没有路由表的改变。不像其他的路由算法，FANT和BANT数据包不会传送多路由信息，只有一个唯一的序列号传输的路由数据包。大部分路线通过数据包进行维护。ARA只需要数据包中的IP头信息。 5仿真结果 5.1仿真环境 我们已经在2-5中应用了ARA。对于我们的结果， 我们假设50个移动节点通过IEEE 802.11沟通。节点在一个1500m300m的模拟仿真区域移动。模拟的时间是900秒。 节点的最大速度均为10m/s，并根据模型2随机流动。在这个模型中，节点在模拟领域随机选择一个点，并为下一步的行动分配一个介于0和最大速度之间的速度值。随后，节点以恒定的速度到达随机选择的点。在抵达终点节点后仍然有一段时间。随后，该节点重复选择一个新的终结点和新的速度操作。我们进行了7次暂停时间的不同的测试，分别为0，30，60，120，300，600和900秒。当暂停时间为0秒时，节点不断移动。相反，当暂停时间为900秒时节点不动。正如我们在引论部分提到，与其他类似的算法性能比较，下面我们主要在这些方面讨论ARA。 5.2比较与现有路由算法 为了得到一个更好的性能，我们将ARA与DSDV，AODV协议和DSR进行比较，在第二部分详细介绍了该部分内容。我们以恒定10比特速率（CBR）在UDP流量并行连接模拟得到以下数据。参数与2相同。 图5：作为暂停时间的函数的一小部分，比较了4个协议成功传递的数据包数量。模拟10 CBR的连接。 我们将首先讨论路由协议的强度。图5显示了传递率，即路由协议是否能够提供一定数量的正确数据包。 在暂停时间低的情况下，即频繁的移动和频繁的拓扑变化情况下，只有DSR和ARA能够提供超过95的数据包。DSR在非常高的动态显示出的最佳性能的情况活动性较差（最多300秒暂停时间）。ARA非常接近DSR。AODV路由协议和DSDV高流动性情况下表现不佳。他们只能提供600或更多秒的暂停时间。 图6 ARA的传递率，置信度为=0.05图7描述了图5中所提到的路由算法的开销。图表显示了路由提供一个数据比特位的一小部分。我们计算路由使用的位数，因为不同的协议产生了截然不同的开销。这里ARA显示出其优势。在非常高动态（0 - 100秒暂停时间的情况下），它产生最少的开销。按照暂停时间300 - 600秒，AODV协议与ARA非常相似， ARA和AODV协议是对DSR的模拟仿真。只有DSDV与其它三种情况有明显的差异。 图8显示的是置信区间为95%的ARA开销。所有情况的模拟的结果非常相近。这表明，ARA考虑了流动情景的路由开销。 我们现在比较以包的数量为基础的路由协议的开销。图9描述了必要的路由下数据包的数量。在高流动性的情况DSR和ARA产生最小的开销。DSR比ARA有更好的性能。这是