自组织基本路由协议及混合型路由协议技术

　　自组网的路由技术主要是设计能自适应网络拓扑动态变化的分布式路由协议，并避免产生路由环路，尽可能减小路由开销，具有一定的可扩展性，使网络节点能根据网络情况的变化，具各分布式管理的路由功能。自组织网络是一个多跳的临时性的自治系统，在这种环境中，由于结点的无线通信覆盖范围的有限性，两个无法直接通信的移动结点可以借助其他结点进行分组转发来进行数据通信。自组网结点之间是通过多跳数据转发机制进行数据交换，需要按路由协议进行分组转发决策。

　　IETF于1996年成立了自组网工作小组（MANET WG），其核心任务就是研究自组网环境下基于IP协议的路由协议规范和接口设计。

　　目前MANET WG已经提出了许多协议草案，比如DSR、AODV、TORA、ZRP等。这些自组网路由协议根据不同的角度可以进行不同的分类。按路由发现的策略划分，可以分为主动式路由协议、被动式路由协议和混合型路由协议。自组织网络主要有以下路由协议。

　　研究基于分布式算法，具有网络自组织和自设置功能的自组织基本路由协议，主要有两类：表驱动路由协议（主动式路由协议）和按需路由协议（反应式路由协议），如图所示。主动式路由协议尽力维护网络中每个节点至所有其他节点的一致的最新路由信息，并要求网络中的每个节点都建立和维护一个或多个存储路由信息的表格。在网络拓扑变化时周期性地广播路由更新信息。这样减少了获得路由的时延，但是需要花费较大的开销保持路由更新。按需路由协议只有在源节点需要时才建立路由，节点不需要花费代价来维护无用的路由信息，节省了一定的网络资源，但是路由发现过程时延比较大。

　 自组织网络路由协议按驱动模式的分类

　　迄今为止，已提出的主动式协议主要有WRP、DSDV等。下面简单介绍这两种协议。

　　（1）WRP协议

　　无线路由协议（wireless routmg protocol，WRP）是一个基于距离矢量的协议，其路由算法是对路径发现算法PFA的改进。它利用去往目标结点的路径长度和相应路径到倒数第二跳结点信息加速路由协议收敛速度，改善路由环路问题。WRP对PFAD的改进之处在于当结点i监测到与邻居结点j的链路发生变化时，i会检查所有邻居结点关于倒数第二跳信息的一致性，而PFA只会检查结点j关于倒数第二跳结点信息的一致性。这种改进可以进一步地减少出现路由环路的次数，加快算法的收敛速度。WRP协议的主要思想如下：

　　每个结点维护四张表，即距离表、路由表、链路费用表和消息重发表，并通过UPDATE消息通告给邻居结点。

　　设结点为i，信宿结点为j，结点i的邻居结点为k。

　　①距离表。距离表包括k的通告的相关内容有经过k到j的路由的距离Dijk的前趋结点Piik。

　　②路由表。每个表项包括信宿结点地址、到信宿的距离Dij、到j的最短路由j的前趋结点Pij、i的下一跳（后继）Sij等。

　　③链路费用表。通过结点乃的链路费用和从上一次收到无误消息后所经过

　　的时间。

　　④消息重发表。可包括多个重发表项，每个表项包括更新消息的序号、重发计数、ACK标志（是否发过相应的ACK）、更新消息列表。

　　WRP通过发送ACK实现可靠传输，结点通过接收ACK和其他消息来测试其邻居结点的存在性。如果结点没有发现数据分组，则周期性地发HELLO消息来得到与邻居结点的连通性消息。如果在一定的时间内收不到某邻居结点的任何消息，则认为与邻居结点的链路出现了故障；当有新的邻居结点时，把自己的路由表通告给新的结点。当结点收到一个更新消息后，采用路由发现算法进行路由表的更新，并克服“计数到无穷”问题。WRP对路由发现算法进行了改进，其独特性表现如下。

　　①距离表更新。对每一个更新消息（如k的通告），结点i检测其所有邻居结点{B∈Ni|b≠k}，凡是经过b结点到j且包括有花结点的路由，距离值需要重新计算为Dibj＝Dikj＋Dij，路由前趋更新为Pijb＝Pkj。

　　②路由表更新。当邻居P→J路由不包括i，且是邻居结点中到j的最短路由，则结点i选择邻居p作为其到j的下一跳结点，即更新Sij＝p。

   （2）DSDV协议

　　目的序列距离矢量协议DSDV（destinatiON sequenced distance vector，DSDV）是一种基于Bellman_ord算法的主动路由协议。它被认为是最早的自组网路由协议。它的主要特点是采用了序列号机制来区分路由的新旧程度，防止可能产生的路由环路。它的缺点是不适应变化速度快的自组网，不支持单向信道。DSDV的主要设计思想如下：

　　①路由表结构。每个结点维护一个路由表，每个路由表项包括：信宿地址、到达信宿的度量值（如跳数）、信宿相关的序列号（由信宿发出）。

　　该序列号用以识别路由的新旧，作为路由更新和分组转发的依据。

　　②信息通告。各结点周期性地向邻居结点通告其当前的路由表，而不是才用洪泛法向网络中的所有结点进行通告。这相当于各结点对收到的其他结点的信息进行处理后再进行广播通告，从而可大大减少通告的信息量。

　　为了进一步减少路由信息的传输开销，DSDV中使用了两类更新报文。

　　（a）完全转存（full damp）。该报文包括了结点当前路由表的所有表项，可能需要多个NPDU进行传输，占用的传输容量大。这种报文仅仅在结点频繁移动的情况下使用。

　　（b）递增更新（incremental update）。该报文包括上一次“完全转存”报文传输以后发生了变化的表项。结点根据每个路由表项变化的程度决定是否进行“递增更新”报文的发送。例如，当到达信宿的度量值变化时，可认为需要对相应的表项进行“递增更新”了。

　　③链路断。如果在相当长的一段时间内不能收到邻居结点的广播消息，可推断出链路断；同时，MAC层实体也可检测到。

　　（a）在DSDV中，断的链路度量值＝∞。

　　（b）结点检测路由表，下一跳经过该链路的路由表项的度量值标记为∞，并分配一个新的序列号。这种情况下的序列号为奇数，以区别于信宿发出的更新报文。

　　（c）度量值为∞的表项的变化程度足以触发“递增更新”报文的立即发送。

　　经过上述过程，在较短的时间内，该链路的变化将通告到网络的各个结点。

　　④路由选择准则与波动抑制。

　　DSDV中路由选择的准则为：序列号新或度量值小。

　　DSDV中路由的选择考虑到下述事实：结点的路由信息通告是异步事件，结点可能先接收到度量值大的路由信息，更新路由的下一跳；当收到新的度量值小的路由信息时，即使信宿结点没有移动，通过路由选择算法也会改变路由的下一跳结点。这种现象导致需要通告的路由表项的频繁波动。

　　DSDV采取的办法是维护两张表：一是转发表；二是广播表。两张表的操作规则有所区分。广播表以信宿地址为关键字，表项中设置一个“平均通告时间间隔”字段，该字段是对该表项过去通告时间间隔的加权平均，最近通告的时间加杈大。当收到一个新的网络变化通告时，查询广播表的相应表项的“平均通告时间间隔”字段，决定是否进行通告广播。需要注意的是，当接收到度量为∞的通告时，不延迟，立即进行广播。WRP和DSDV的比较如表1所示。

　　表1  主动路曲协议的比较

　　目前，提交到IETF MANET组的路由协议及其他研究人员提出的路由协议，大都是基于信源按需建立的特征。这种特征成为自组织网络路由协议设计的一种趋势。

　　迄今为止，已提出的按需路由协议（on demand）主要有源动态路由协议（dynamlc source routmg，DSR）、按需距离矢量协议（Ad Hoc on demand distancevector，AODV）等。下面简要介绍这两种协议。

　　（1）DSR协议

　　DSR协议是最早采用按需路由思想的路由协议。它包括路由发现和路由维护两个过程。它的主要特点是使用了源路由机制进行分组转发。这种机制最初是IEEE 802.5协议用于在网桥互联的多个令牌环网中的结点寻找路由。DSR协议借鉴了这种机制，并加人了按需思想而形成。它的优点在于中间结点不用维护去往全网所有结点的路由信息，而且可以避免出现路由环路。它的缺点是每个数据分组都携带了路径信息，造成协议开销较大，而且也不适合网络直径大的自组网，网络可扩展性不强。

　　该协议的路由发现过程如下：

　　①RREQ分组。结点有分组要发时，动态地广播“路由请求分组”RREQ。RREQ分组应包括信宿、请求分组发送结点地址、本分组ID、路由记录。{请求分组发送结点地址＋本分组ID}用于唯一地识别RREQ，以便于RREQ的接收处理，这里称为RREQ标识。路由记录将积累地记下RREQ分组逐跳传播时所顺序经过的结点地址，从而完成路由发现的功能。

　　②结点对RREQ分组的处理。

　　（a）如果在最近收到的f历史RREQ列表”中已存在，则丢弃该RREQ分组，不作进一步的处理；

　　（b）如果“路由记录”中包括本结点，则丢弃该RREQ分组，不作进一步的处理；

　　（c）如果本结点就是RREQ指定的信宿，发送“路由回答分组”RREP，否则将本结点的地点添加到“路由记录”的后面，重新广播更新后的RREQ分组。

　　③信宿的路由回答RREP。RREP包含有由信宿接收到RREQ分组的路由记录。RREP的目的是如何把这个路由记录告诉给信源。先假设网络中所有的链路是双向的。如果信宿到信源的“反向路由”存在，则RREP分组沿“反向路由”点到点传输到信源；如果信宿到信源的“反向路由”不存在，则按RREQ中的“路由记录”（前向路由）进行反向传送。

　　④存在单向链路。信宿执行与信源相同的反向路由发现过程，所不同的是信宿RREQ分组稍带传送RREP分组。

　　按需路由协议中，没有周期性的网络测试过程，各结点需要执行路由维护进程，动态地监视活动路由的运行情况。该协议的路由维护过程如下：

　　①“逐跳MAC确认”的网络。这种网络中，链路的故障或变化由MAC层通告，结点将发送“路由错误分组”RRER到信源；信源结点将删除该路由，重新进行路由发现。

　　②“逐跳MAC不确认”的网络。这种情况下，可利用无线传输的空间广播性，实现等效的“被动ACK”。当结点A转发分组到下一跳B时，B到C的分组转发可被A监听到。

　　③利用“端到端确认”的路由维护。端到端的确认（如TCP层的确认机制）也可以实现路由维护，信源端将检测到并发起新的路由请求。

　　（2）AODV协议

　　AODV协议是在DSDV协议基础上，结合类似DSR中的按需路由机制进行改进后提出的。不同之处在于AODV采用了逐跳转发分组方式，而DSR是源路由方式。因此，AODV在每个中间结点隐式保存了路由请求和回答的结果，而DSR将结果显示保存在路由请求和路由回答分组中。此外，AODV的另一个显著特点是它加人了组播路由协议扩展，并支持QoS。它的缺点是不支持单向信道，原因是AODV协议基于双向信道的假设工作，路由回答分组直接沿着路由请求的反方向回到源结点。AODV与DSR的路由发现有所不同，该协议的路由发现过程如下：

　　①RREQ分组。结点在需要（没有到信宿的活动路由）时，向其邻居广播RREQ分组用于路由发现。RREQ分组包括信源地址、信源序列号、广播ID、信宿地址、信宿序列号、跳计数。

　　（a）（信源地址＋广播ID）唯一地标识了一个RREQ分组；

　　（b）信源序列号由信源结点维护，用于表示“到信源的反向路由”的新旧；

　　（c）信宿序列号表示信源可接受的“到信宿的前向路由”的新旧，等于过去接收到的有关信宿的最大序列号。可见，结点需要为每一个信宿维护一个信宿序列号；

　　（d）RREQ的跳计数＝0。

　　②对RREQ的处理。接收到RREQ的结点的处理方法为：创建一个表项，先不分配有效的序列号，用于记录反向路径。如果在“路由发现定时”内已收到一个具有相同标识的RREQ分组，则抛弃该分组，不作任何的处理，否则对该表项进行更新如下：

　　（a）信源序列号＝RREQ分组的信源序列号；

　　（b）下一跳结点＝广播RREQ的邻居；

　　（c）跳数＝RREQ分组的“跳计数”字段值；

　　（d）设置表项的“过时定时器”。

　　如果该结点是信宿，结点的路由表中有到信宿的活动表项，且表项的信宿的序列号大于RREQ中的信宿序列号（新），则该结点将产生“路由回答分组”RREP，并发送到信源，否则更新RREQ分组，并广播更新后的RREQ分组。

　　（a）信宿序列号＝本结点收到的该信宿相关的最大序列号；

　　（b）跳计数加1。

　　③RREP的产生。产生RREP的条件如上所述。RREP分组各字段设置如下。

　　信宿结点产生的RREP：

　　（a）如果收到的相应RREQ的信宿序列号与信宿维护的当前序列号相等，则信宿将自己维护的序列号加1，否则不变；

　　（b）信宿序列号＝信宿维护的序列号；

　　（c）跳计数＝0；

　　（d）定时器值。

　　中间结点产生的RREP：

　　（a）本结点所获得的该信宿的最大序列号；

　　（b）跳计数＝本结点到信宿的跳数；

　　（c）更新本结点维护的“前向路由表项”的下一跳和“反向路由表项”的前一跳。

　　④对RREP的处理。结点对接收到的RREP的处理方法为：如果没有与RREP分组中的信宿相匹配的表项，则先创建一个“前向路表”的空表项，否则满足如下条件对已有表项进行更新：

　　（a）现有表项的信宿序列号小于RREP分组中的信宿序列号；

　　（b）现有的表项没有激活；

　　（c）信宿序列号相同，但RREP分组的“跳计数”值小于表项相对应的值；通过更新或创建，产生一个新的前向路径；

　　（d）下一跳＝广播RREP的邻居结点；

　　（e）信宿序列号＝RREP中的信宿序列号；

　　（f）跳计数加1。

　　按照上述的过程，任何转发RREP的结点，都记录了到信宿的下一跳，当RREP到达信源时，结点地址匹配，不再转发RREP，信源到信宿的前向路径已建立起来了。信源可以沿这条前向路径进行分组传输。

　　该协议的路由维护过程如下：

　　①与活动路由无关的结点移动，并不影响信源到信宿的寻径。

　　②如果信源结点移动导致路由不可用，则由信源重新发起路由发现的过程。

　　③当信宿结点或活动路由的中间结点移动，导致链路中断，则链路的“上游结点”主动发送一个RREP，该RREP的信宿序列号大于其所获取的信宿序列号，跳计数的值设为∞，并传播到所有的活动邻居。该过程重复，直至所有的相关信源结点被通告到。信源结点如果需要，可重发起路由发现过程。

　　AODV与DSR的比较：

　　①DSR使用源路由技术进行路由发现，AODV通过“路由请求分组”洪泛进行路由发现，DSR在一次路由发现过程中结点获取的路由信息远远多于AODV。从这个角度看，AODV进行“路由发现”可能更频繁，所带来的开销比较大。

　　②DSR在一次路由发现过程中或获取到多个替代的路由，而AODV只响应一个路由，后续的在定时内的申请被丢弃。

　　上述的表驱动路由协议和按需路由协议统称为平面型路由协议，还有一类路由协议混合了二者优点，称为层次性路由协议或混合型路由协议。在平面型路由协议中，所有节点功能都是对等的；在层次型路由协议中，各层次由若干个节点组成，在层次内的节点之间采用表驱动路由算法，在各层次间采用按需路由算法，代表性的协议有区域路由协议（zone routing protocol，ZRP）。ZRP协议是第一个利用分级结构混合使用按需和主动路由策略的自组网路由协议。ZRP中，分级被称作域（zone）。域形成算法较为简单，它是通过一个重要的协议参数－区域半径，指定每个结点维护的区域大小，即所有距离不超过区域半径的结点都属于该区域。一个结点可能同时属于多个区域。为了综合利用按需路由和主动路由的各自优点，ZRP规定每个结点采用DVA主动路由协议维护去往区域内结点的路由，采用类似DSR协议中的按需路由机制寻找去往区域外结点的路由。ZRP协议的性能很大程度上由区域半径参数决定。通常，小的区域半径适合在移动速度较快的结点组成的密集网络中使用；大的区域半径适合在移动速度慢的结点组成的稀疏网络中使用。