用于网状网中的自适应无线路由选择协议的方法和系统

摘要

本发明公开了一种用于网状网中的自适应无线路由选择协议的方法和系统。在一个实施方式中，所述方法包括在网状网的多个节点之间对数据报进行路由选择。将更新消息路由选择到所述多个节点中的一个或者更多个，其中所述更新消息包括呼叫分组和更新分组。

说明书

技术领域

本发明的领域总体上涉及无线网络，并且更具体地涉及用于为无线网状网定制的自适应路由选择协议的方法和系统。

背景技术

随着计算机和无线通信技术近年来的不断发展，移动无线计算技术日益得到广泛的应用和实施。因不受线路的限制，携带移动计算设备的用户可就其方便地到处自由移动，并可能经常需要在没有固定基础设施的环境下进行彼此通信。在这种情况下，他们能够形成移动自组织网络(MANET)或者移动无线网状网。移动无线网状网是无线移动路由器(和相关主机)的自主系统，它能够在没有任何基础干线和基础设施的情况下随意移动并将其自身重新组织成任意网络。

近来，除了移动无线网状网以外，还出现了对固定无线网状网的引人注意的商业应用。这种应用的一个实施例是“社区无线网络”，其用于向以前没有宽带因特网接入的社区提供这种接入。在这些固定“社区无线网络”中，网络中的每个无线路由器不仅对附属用户提供因特网接入，还成为网络基础设施的一部分，并可将数据通过无线网状网路由到其目的地。可被路由的无线网状网非常灵活而且本身固有容错性。其简化了可视距离(line-of-sight)问题，并利用最少量的网络基础设施和互连成本扩展了网络的可达和覆盖范围。

还存在其中一些网状路由器是可移动的而其它网状路由器是不可移动的混合无线网状网。无论哪一种情况(不管是可移动的、固定的还是混合的)，无线网状网均具有一些显著的特征，如高度动态、自主、对等、多跳、通常具有有限带宽和计算能力等。无线网状网因下述两个原因而具有高度动态性：首先，路由器本身可移动(例如，在移动无线网状网或者混合无线网状网中)，这导致了快速拓扑变化；其次，即使路由器本身不动(例如，在固定无线网状网中)，无线电链路质量也会由于干扰、地理以及环境因素等而发生快速变化。为有线基础设施设计的传统路由选择协议(例如，OSPF和RIP)无法处理这种快速变化。另一方面，大部分自组织路由选择协议(例如，AODV)缺乏灵活适应无线电链路质量变化的能力。

发明内容

公开了一种用于网状网中的自适应无线路由选择协议的方法和系统。在一个实施方式中，所述方法包括在网状网中的多个节点之间对数据报进行路由选择。向所述多个节点中的一个或者更多个节点发送路由选择消息，其中路由选择消息包括呼叫分组(hello packet)和更新分组。

现在将参照附图更具体地描述并且在权利要求中指出上述和其它优选特征，包括单元的实现和合并的各种新颖详情。应当理解在此描述的具体方法和系统仅是以例示方式示出而非作为对本发明的限制。本领域的技术人员应当理解，在不脱离本发明的范围的情况下，在此描述的原理和特征可应用于大量各种实施方式中。

附图说明

包括在本说明书中并且作为本说明书的一部分的附图例示了本发明的当前优选实施方式，并且与上文提供的总体描述和下文给出的优选实施方式的详细描述一起用于对本发明的原理进行说明和讲解。

图1例示了根据本发明一个实施方式的示例性无线网状网的框图；

图2例示了根据本发明一个实施方式的示例性无线路由器的框图；

图3例示了根据本发明一个实施方式的以四字节报头开始的示例性自适应无线路由选择分组的图；

图4例示了根据本发明一个实施方式的自适应无线路由选择呼叫分组400的图；

图5例示了根据本发明一个实施方式的自适应无线路由选择更新分组的图；

图6例示了根据本发明一个实施方式的距离区条目(distance sectionentry)的格式的图；

图7例示了根据本发明一个实施方式的信使区条目(messengersection entry)的格式的图；

图8例示了根据本发明一个实施方式的示例性路由选择表的图；

图9例示了根据本发明一个实施方式的发送更新分组、立即触发更新分组以及正常触发更新分组的示例性处理的流程图；

图10例示了根据本发明一个实施方式的添加用于新发现的目的地的新路由选择条目的示例性处理的流程图；

图11例示了根据本发明一个实施方式的用于处理断开链路的示例性处理的流程图；

图12例示了根据本发明一个实施方式的局部修复处理的示例性流程图；

图13例示了根据本发明一个实施方式的用于更新分组处理的示例性处理的流程图；以及

图14例示了根据本发明一个实施方式的用于信使操作的示例性处理的流程图。

具体实施方式

公开了一种用于网状网中的自适应无线路由选择协议的方法和系统。在一个实施方式中，所述方法包括在网状网的多个节点之间对数据报进行路由选择。向所述多个节点中的一个或者更多个节点发送路由选择消息，其中所述路由选择消息包括呼叫分组和更新分组。

在下文的描述中，为了说明的目的，阐述了具体术语以提供对在此公开的各种创造性概念的全面理解。然而，本领域的技术人员应当明了，为了实施在此公开的所述各种创造性概念，这些具体细节并非是必需的。

以下针对无线网络和计算机系统介绍部分详细说明。这些无线网络描述和陈述是无线网络技术领域的技术人员最有效地向本领域的其他技术人员传达他们工作的实质所使用的手段。在此无线网络通常被认为是利用无线电波作为其载体在两个或者更多个计算机之间进行通信的系统。尽管并非必须如此，但在计算机系统之间所传送的信息通常采用分组形式。此外，为了通用目的，将分组的组成部分称为比特、值、元素(element)、码元(symbol)、字符、项、数字等。

然而，应当理解，所有这些和类似的术语都与适当物理量有关，并且仅是用于这些物理量的简便标签。除非在下文讨论中另外明确指出，否则应当理解利用诸如“路由器”或者“无线电”或者“频率”或者“信道”或者“干线”或者“分组”或者“通信”等的术语进行的所有描述和讨论都指的是网络或者类似通信系统中的组件以及动作和处理，所述网络或者类似通信系统用于将在计算机系统的寄存器和存储器或者其他此类信息存储装置、发送装置或者显示装置中表示为物理(电子)量的数据从一个计算机系统传送到另一计算机系统。

本发明还涉及用于执行此处的操作的装置。此装置可根据所需目的而具体构造，或者此装置可包括可选择激活或者通过存储在计算机中的计算机程序重新配置的通用计算机。这种计算机程序可存储在计算机可读存储介质中，所述计算机可读存储介质例如是但不限于任意类型的盘(包括软盘、光盘、CD-ROM以及磁光盘)、只读存储器、随机存取存储器、EPROM、EEPROM、磁卡或者光卡，或者适于存储电子指令并且可分别连接到计算机系统总线的任意类型的介质。

在此所提出的方法并非必然与任何具体计算机或者其他装置有关。各种通用系统可与根据本文教义的程序一起使用，或者可能便利的是构建更专用的装置以执行所需的方法步骤。各种所述系统所需的结构将从下文描述中显现。此外，未参照任何具体编程语言对本发明进行描述。应当理解各种编程语言均可用于实施在此描述的本发明的教义。

以下列表描述了在此使用的术语的简称和定义：

节点：根据在此描述的方法和系统实施自适应无线路由选择的路由器；

自适应无线路由选择接口：加入到运行自适应无线路由选择的无线网状网(wireless mesh)中的网络装置。一个节点可具有几个自适应无线路由选择接口。

非自适应无线路由选择接口：未加入到运行自适应无线路由选择的无线网状网中的网络装置。一个节点可以具有几个自适应无线路由选择接口。来自这些接口的路由选择信息可被插入自适应无线路由选择域中。

路由器ID：32位数字，其用于唯一标识无线网状网中的节点。一个可能的实施策略是使用属于该节点的自适应无线路由选择接口的最小IP地址。另一个可能的实施策略是使用为此目的配置的回送(loop-back)接口的IP地址。

目的地序号：源自各目的地节点并由各目的地节点保持的单调递增数字。其有助于识别新旧路由，从而避免循环。

链路：链路是易于彼此获悉信息(即，一个能从另一个接收通信量)的一对自适应无线路由选择接口(来自两个不同节点)。当一个节点的其中一个接口具有连到另一个节点的其中一个接口的链路时，认为该节点具有到达另一节点的链路。

用于自适应无线路由选择的本发明的方法和系统包括针对无线网状网设计的自适应、分布式、先应式(proactive)路由选择协议。图1例示了根据本发明一个实施方式的示例性无线网状网的框图。网状网100可以是无线网络的一部分(如邻域112)。根据一个实施方式，邻域112被划分成多个小区110，其中每个独立小区111包括一个或者更多个无线网状网100的用户120。邻域112的划分是一种逻辑划分，并且网络100中的小区之间的物理边界仅是代表逻辑网络操作。小区111可以包括或者不包括用户120，因为特殊小区可能处于恰巧没有用户位于其区域内的状态。

根据一个实施方式，用户120是被授权接入无线网络100的邻域112的计算机系统。用户120可以位于临近的家中、车内或者网络覆盖区域中的任意位置处。除了网状网外，应当理解采用本发明的各种教义的其它系统也可用于实践本发明的各个方面，并且同样认为其在本发明的整体范围之内。

六边形小区199中的每个小区111包括或固定或移动的网状路由器(如路由器/节点101-104)。网状路由器101与示例性用户120进行通信。用户120需要设置有用户帐户，以通过网状路由器101接入诸如网状网100的网状网。这些用户120可以包括无线个人数字助理(PDA)、无线局域网(LAN)路由器或者无线膝上型电脑。无线PDA可包括具有无线性能的掌上导航器(palm pilots)、黑莓(Blackberrys)或者其他具有无线性能的手持设备。无线路由器101可以包括能与网状路由器101进行通信的任何网络路由器。无线膝上型电脑可以包括具有无线性能的任何计算机系统。尽管描述了无线PDA、无线LAN路由器以及无线膝上型电脑，但也可将具有无线性能的任何其它装置视为用户。

网状路由器101还可用作到因特网的网关。根据一个实施方式，网状路由器/网关101具有至少一个网络接口，如经由通信链路(如以太网)与因特网连接的以太网控制器。在网状网中，可存在多个网关101。网关101允许网状路由器101接入因特网。

图1的网状网拓扑还可包括网络管理服务器160。网络管理服务器160可通过因特网连接到网关。根据一个实施方式，网络管理服务器160指定网状网中的所有网状路由器101的信道分配。

图2例示了根据本发明一个实施方式的示例性无线路由器200的框图。在图2中，无线路由器200允许用户建立它们自己的局域网。无线路由器200可以是诸如路由器101的Wi-Fi路由器。无线局域网路由器200具有与电源220、随机存取存储器(RAM)模块230、以太网控制器240以及802.11控制器250相连接的处理器210。以太网控制器240使处理器210可以与以太网适配器260进行通信。802.11控制器250使处理器210可以与802.11天线270进行通信。RAM模块230存储用于对去往和来自路由器200的分组进行路由选择的路由选择表231。

用于自适应无线路由选择的本发明的方法和系统是基于用户数据报协议(UDP)的。利用自适应无线路由选择的各路由器(如路由器101-104以及200)都具有基于(从IETF获得的)UDP端口号来发送并接收数据报的路由选择处理。向自适应无线路由选择端口发送供另一路由器的自适应无线路由选择处理所使用的全部通信。从自适应无线路由选择端口发送所有路由选择更新消息。存在两种不同的自适应无线路由选择分组类型：呼叫和更新。两种自适应无线路由选择分组都以标准4字节报头开始。

图3例示了根据本发明一个实施方式的以四字节报头300开始的示例性自适应无线路由选择分组的示图。报头300包括版本区310，该版本区310包括自适应无线路由选择版本号。类型区320表示自适应无线路由选择分组类型：呼叫或者更新。然而，在另选实施方式中也可以实现其它分组类型。报头300还包括可用于标志或者其他信息的未使用区。尽管描述了四字节报头300，但是在另选实施方式中也可使用其它大小的报头。

图4例示了根据本发明一个实施方式的自适应无线路由选择呼叫分组400的示图。呼叫分组400是自适应无线路由选择分组类型中的一种类型。为了建立并维护与相邻节点的关系，在所有自适应无线路由选择接口上定期发送呼叫分组400。呼叫分组400包括报头300，以及始发方路由器ID 410和始发方目的地序号420。始发方路由器ID 410是发起所述呼叫分组的节点的路由器ID。目的地序号420是发起所述呼叫分组的节点的最高目的地序号。另选实施方式被设计成呼叫分组400仅是用于建立和维护邻居关系的分组的一个实施方式。

图5例示了根据本发明一个实施方式的自适应无线路由选择更新分组500的示图。更新分组500是另一种自适应无线路由选择分组。更新分组400用于在动态变化的网络(如网络100)中维护路由选择表的一致性，每个节点(如路由器101)定期发送更新，并在可获得重要新信息时发送触发更新。根据一个实施方式，更新分组500包括报头300以及距离区510和信使区520。距离区长度511具有信使区长度512。

在距离区510中包含的信息反映了发送端看到的与网络100中的其它节点的互连拓扑。在距离区510可以存在多个距离区条目。距离区条目的数量等于(距离区的长度(字节)/距离区条目的长度(字节))。

图6例示了根据本发明一个实施方式的距离区条目600的格式的示图。距离区条目600包括目的地IP地址610、目的地网络掩码620、目的地路由器ID 630、目的地序号640以及量度(metric)650。目的地IP地址610可以是目的地节点或者附接到该目的地节点的IP网络/子网的路由器ID。目的地网络掩码620提供目的地IP地址的网络掩码。根据一个实施方式，该掩码为表示属于单个IP网络/子网的IP地址范围的32位数字。目的地路由器ID 630提供目的地节点的路由器ID。目的地序号640是目的地序号。量度650表示获得从所述节点到上述目的地的数据报的总成本。该量度是与为抵达目的地而经过的网络相关联的成本之和。

返回图5，信使区520包含一个或者多个由目的地路由器ID索引的固定长度信使。在信使区520中可存在多个信使区条目。信使区条目的数量等于(信使区的长度(字节)/信使区条目的长度(字节))。图7例示了根据本发明一个实施方式的信使区条目700的格式的示图。信使区条目700包括目的地路由器ID 710、目的地序号720、下一跳值730以及量度750。

目的地路由器ID字段710提供目的地节点的路由器ID。目的地序号字段720提供目的地序号。下一跳字段730用于指示谁应该关注该信使。如果下一跳字段730含有“0xffffffff”(即“255.255.255.255”)，则该信使被称为“局部广播(local broadcast)”信使，并且所有收到该信使的节点都将检查该信使并进行相应动作。否则，该信使被称为“单播”信使，并且只有其IP地址与包含在下一跳字段730中的IP地址相匹配的节点才能检查该信使并进行相应动作。量度字段740向该节点已知的目的地提供先前成本(或者距离)。仅当下一跳字段730包含“0xffffffff”(即“255.255.255.255”)时，才对该量度字段进行核查。

图8例示了根据本发明一个实施方式的示例性路由选择表800的示图。假设执行自适应无线路由选择的每个路由器(如路由器101和200)都具有路由选择表800。路由选择表800具有针对在整个利用自适应无线路由选择而运行的系统中可抵达的每个目的地的一个条目890。每个条目890至少包含下列信息：

●目的地IP地址810。将其称为“dst”。

●目的地IP地址的网络掩码820。将其称为“dst_mask”。

●目的地节点的路由器ID 830。将其称为“dst_router_id”。

●当前最高序号路由840。将其称为“hsq_route”。

●当前最小量度路由850。将其称为“lm_route”。

●指示在收到较高序号路由(量度低于无穷大(infinity))时是否需要向此目的地发送立即触发更新的标志860。将其称为“immediate_update_flag”。

●指示在下一定期更新以前是否需要通告该路由的标志870。将其称为“need_advert_flag”。

●信使相关信息880。

用于自适应无线路由选择的本发明的方法和系统在其路由选择条目890中为每个目的地保持两个路由，该两个路由可以相同也可以不同。一个被称为当前最高序号路由840，而另一个被称为当前最小量度路由850。二者都是包括下列三项的数据结构：

●与该路由相关联的目的地序号。将其称为“seqnum”。

●量度，其表示数据报从该路由器到上述目的地的总成本。将其称为“metric”。

●下一跳，其是沿去往所述目的地的路由的下一路由器的IP地址。

如果所述目的地在直连网络之一上，则不需要该项。将其称为“next_hop”。

根据本发明的一个实施方式，信使相关信息880包括下列信息：

●指示是否需要向该目的地发送信使的标志。将其称为“messenger_status_flag”。

●该信使的目的地序号。将其称为“messenger_dst_seqnum”。

●通过此节点将最后一条信使转发给所述目的地的时间。将其称为“last_messenger_time”。

●指示如果丢失了去往所述目的地的所有路由，是否应该尝试局部修复的标志。将其称为“local_repairable_flag”。

●自得知小于或者等于当前最小量度路由量度的量度后的时间。将其称为“local_repairable_time”。

●指示是否正在进行局部修复处理的标志。将其称为“local_repair_process_flag”。

●启动最后一次局部修复的时间。将其称为“local_repair_start_time”。仅当在“local_repair_process_flag”为“真”时才检查该项。

●表示局部修复处理状态的标志。将其称为“local_repair_state”。

网络100中的节点建立并维护相邻关系。在自适应无线路由选择中，各节点追踪(keep track of)与其相邻节点的连续连通性。例如在图1中，节点101追踪与相邻节点103的连通性。如果可利用任何合适的MAC层通知(如由IEEE 802.11提供的MAC层通知)来检测断链路，则用于自适应无线路由选择的本发明的方法和系统使用与第三层更新分组相结合的MAC层反馈来确定局部连通性。在一个实施方式中，不需要第三层呼叫分组。在一个实施方式中，当在所有自适应无线路由选择接口可获得重要新信息时，每个节点101-104定期发送更新分组并发送触发更新分组。这使得可动态发现相邻节点。

如果没有合适的MAC层通知可用时，用于自适应无线路由选择的本发明的方法和系统使用与第三层更新分组相结合的第三层呼叫分组来确定局部连通性。在这种情况，该节点定期(例如，按每500ms到1000ms的间隔)检查在最后间隔内是否已经发送了更新分组或者呼叫分组。如果没有，则在向其相邻接口通告了其存在的所有自适应无线路由选择接口上广播局部呼叫分组。如果超过设定间隔(例如，3000ms)节点还没有从相邻节点收到任何分组(呼叫分组或者更新分组)，则认为到任意已知相邻节点的链路丢失。当检测到通往相邻节点的断链路时，该节点进行如下处理。

在一个实施方式中，使用更新分组500来向相邻节点发送路由选择更新。如图5所述，在更新分组500中可以存在两个区：距离区510和信使区520。包含在距离区510中的信息反映了发送方看到的与网络100中的其它节点的互连拓扑。信使区520包含了在链路失效后向受影响的目的地节点传播的“信使”，以便对路由进行局部修复并且加速收敛。

根据一个实施方式，当可获得重要新信息时，每个节点定期发送更新分组500并发送触发更新分组。图9例示了根据本发明一个实施方式的发送更新分组、立即触发更新分组以及正常触发更新分组的示例性处理的流程图。例如，每15到30秒，各节点101-104对目的地序号进行递增(950)。定期更新分组携带所有可通告的可用路由选择信息。在一个实施方式中，对于路由选择表800中的每个路由选择条目890，如果可存在信使信息，则该信使信息都是可通告的。另一方面，只有在满足两个条件时距离信息才是可通告的。处理900针对目的地检查所述最高序号路由是否与最小量度路由相同(960)。如果不相同，则在不通告距离信息的情况下广播定期更新分组。如果两个路由相同，则处理900检查是否存在正在进行的局部修复处理(local_repair_process_flag的值为假)(970)。如果存在正在进行的局部修复处理，则在不通告距离信息的情况下广播定期更新分组。如果不存在正在进行的局部修复处理，则在通告距离信息的情况下，广播定期更新分组(990)。节点101-103向所有其自适应无线路由选择接口的相邻节点广播(多点广播)定期更新分组。

在定期更新之间，当可获得重要新信息时发送触发更新信息。与定期更新不同，触发更新只包含变更信息。为了减少触发更新分组的数量并最小化路由选择开销，定义了两种类型的触发更新：立即触发更新分组和正常触发更新分组。

当可获得的新信息重要且紧急时(910)使用立即触发更新分组(920)。在一个实施方式中，“重要且紧急的路由选择信息”通常与拓扑改变以后需要立即进行处理的再收敛相关。当满足下列条件中的至少一个时，节点使用立即触发更新920：

·检测到链路中断并且该链路中断导致该节点丢失其到至少一个目的地的路由。

·在从其相邻节点接收到更新或者呼叫分组时，节点获悉到全新节点或者目的地的路由(量度低于无穷大)。

·在从其相邻节点接收到更新分组时，节点获悉到目的地的较高序号路由(量度低于无穷大)并且与所述目的地相关联的路由选择条目的立即更新标志为真。

·在从其相邻节点接收到更新分组时，节点收到较高序号路由(量度等于无穷大)，该较高序号路由导致该节点丢失其到所述目的地的全部路由和/或触发了信使发起操作。

·在从其相邻节点接收到更新分组时，节点接收到一信使，其中节点能够直接答复该信使，或者将该信使转发到其去往该信使的目的地的下一跳。

·在找到去往受影响的目的地的新路由之前，局部修复定时器超时。

为了进一步降低路由选择开销，定义了两次更新之间的以毫秒计的最小时间间隔。在使用立即触发更新时，如果当前时间与最后更新之间的时间间隔小于该最小时间间隔，则延迟触发更新分组的建立和发送。该延迟时间可等于最小时间间隔减去以毫秒计的当前时间与最后更新时间的差而获得的差值。否则，立即建立并发送触发更新分组。

如果可获得的新信息虽重要但不紧急(930)，则使用正常触发更新分组940。在一个实施方式中，“重要但不紧急的路由选择信息”通常与非拓扑变更(例如，目的地序号和路由量度发生变化)后的再收敛相关。与拓扑变更后需要立即进行处理的再收敛不同，网络100中的节点已经具有路由并且能够适应于为了获得较优路由的逐步非拓扑变化，并且同时进一步减小了路由选择开销。在正常触发更新分组建立以后，如果在正常触发更新事件超时之前发生了任何定期更新或者立即触发更新，则可取消该(触发正常触发更新的)正常触发更新事件。否则，如果所述事件在正常触发更新时间间隔以后超时，则建立并发送触发更新分组。

在一个实施方式中，各节点保持用于其自身的目的地序号，该目的地序号在其发起的每个定期更新中被递增并且包括在节点自己的条目中。节点定期复制其他条目的目的地序号以及来自其路由选择表的触发更新。这样的效果是路由选择表条目或者通告条目中的序号字段反映了该条目的路由选择信息的新旧(或者新鲜度)。这有助于识别新旧路由，从而避免回送(loop back)状况。

利用目的地序号，如果遵循下列路由更新规则，则可在任何时刻都保证无环(loop-freedom)。

·节点总是更喜欢具有较高目的地序号的路由。

·如果序号相同，则量度较好的路由是优选的。

尽管这些规则提供了无环，但是它们在特定情况下也会导致路由波动。由于通过节点进行的路由选择信息的发送是异步事件，所以可以想到节点总是接连(经由不同的相邻节点)接收到去往具有较新的序号的同一目的地的两条路由，但总是首先得到具有较差量度的路由。如果不注意这点，则当每次接收到来自目的地的新序号时，将导致路由波动和新路由发送的持续突发。为了在任何时刻都保证无环并且同时避免不必要的路由波动，本发明的方法和系统在其路由条目中为每个目的地保留两个路由。一个路由被称为当前最高序号路由(称为“hsq_route”)，而另一个路由被称为当前最小量度路由(称为“lm_route”)。二者均为包括下列三项的数据结构：

●目的地序号(称为“seqnum”)

●量度(称为“metric”)

●下一跳(称为“next_hop”)

图10例示了根据本发明一个实施方式的针对新发现的目的地增加新路由条目的示例性处理的流程图。节点101从相邻节点103接收通往先前未知的目的地节点104的路由(量度低于无穷大)(1010)。节点101在其路由选择表中针对目的地节点104建立新的路由选择条目(1020)。在该新的路由选择条目中，将hsq_route设置为与lm_route相同，这意味着二者具有相同的seqnum、metric以及next_hop(其被设置为相邻节点103)。并且，触发了立即更新(1030)。

在从相邻节点103接收到通往已知目的地节点104的路由时，节点101根据针对目的地节点104的路由选择条目中的各种路由选择标志(例如immediate_update_flag)和在hsq_route、lm_route以及从相邻节点103获悉的路由(称为ad_route)之间的比较来对该通往已知目的地节点104的路由进行处理。根据所述更新规则，在同一路由选择条目中的hsq_route和lm_route可以不总是相同，但是如下关系一直成立：

i) hsq_route.seqnum＞＝lm_route.seqnum

ii)hsq_route.metric＞＝lm_route.metric

在一个实施方式中，针对特定目的地当hsq_route与lm_route不一样时，可将默认路由设置成仅使用lm_route来转发数据。为同一目的地保留两个无环路由是为了避免不必要的路由波动并且防止节点使用较差量度路由。然而，为同一目的地保留两个无环路由除了避免路由波动以外，还提供了如下优点：当发现lm_route断开时，如果仍然存在具有有限量度的hsq_route，则该节点可仅在内部将lm_route设置为hsq_route，从而避免触发立即更新，该立即更新可能启动涉及大量节点的再收敛。

与多路由相关的另一更新过程是直到针对特定目的地的hsq_route与lm_route相同时才通告关于该目的地的距离信息。虽然这是用于保证无环的最后措施，但其也能够及时地防止节点通告其已知路由的一部分，尤其是在如果不小心会引起拓扑变更的情况下。如果hsq_route与lm_route不相同，当满足以下条件中的至少一个时，可将它们设置得相同，从而使它们变得可通告：

1)发现lm_route断开。

2)当immediat_update_flag的值为真时，节点从其相邻节点接收到具有有限量度和比现有hsq_route的序号更高的目的地序号的路由。

3)当hsq_route的量度不是无穷大时，节点从其相邻节点接收到具有无穷大量度和比现有hsq_route的序号更低的目的地序号的路由。

4)当hsq_route的量度不是无穷大时，节点从其相邻节点接收到具有比现有hsq_route的序号更低的目的地序号的信使。

5)在从作为在lm_route中标识的下一跳的相邻节点接收到更新分组时，在lm_route的下一跳不变的情况下，节点发现lm_route的目的地序号将变得不小于hsq_route的序号或者lm_route的量度将变得比hsq_route的量度更差。

6)节点从其相邻节点接收到如下路由，该路由与现有hsq_route相比具有更高或者相等的序号，并且具有比lm_route的量度小的量度。

以上的前四个条件与拓扑变化有关。由于认为针对由拓扑变化引起的运营中断的快速恢复要比路由波动重要得多，因此不会延迟对由拓扑变化引起的再收敛很重要的更新。所述后两个条件确保在存在拓扑变化或者无拓扑变化的情况下，hsq_route与lm_route不相等的时段很短并且是瞬态的。由于每个节点在其具有更新的目的地序号要通告时会发送定期更新以及正常触发更新，因此只要满足以下两个条件，每个节点都可能在定期更新间隔期间从其全部相邻节点获悉具有相同目的地序号的路由通告并且收敛为正确且可通告的路由：

i)在发送期间没有丢失更新分组(通过利用定期更新可缓解偶然丢失更新分组的问题)

ii)正常触发更新间隔(默认等于2秒)远小于定期更新间隔(默认等于30秒)

在一个实施方式中，引入信使概念以在链路故障后加速收敛。在链路故障后利用信使进行的快速收敛处理期间存在双向“波”。第一波是在链路故障后由受影响节点(或者多个节点)发起的信使的前向波，该前向波向受影响的目的地传播。在接收到信使时，中间节点在满足特定条件时将该信使转发给在其lm_route中标识的下一跳，并且同时，将其相应路由条目的立即更新标志设置为真。一旦信使到达目的地或者具有较高目的地序号的节点，则触发立即更新。这启动了所述第二波，即携带最新路由选择信息的被触发更新的反向波，并且该反向波流向在链路故障后直接受影响或者已经转发了所述信使的任意节点。

在一个实施方式中，信使不是独立分组而是被嵌入更新分组的信使区的内部。通过对向不同目的地传播的信使进行分组并且将所述信使加载到用于向相邻节点发送路由选择信息的公共“渡船”(更新分组)上，自适应无线路由选择可充分利用无线网络的广播特性并且使得路由选择开销最小化。

在更新分组500的信使区520中的每个信使包含以下信息：目的地路由器ID 710、目的地序号720、下一跳IP地址730以及估计量度740。目的地路由器ID 710和目的地序号720用于表示信使去往的目的地和其信息的新鲜度。“下一跳”字段用于表示谁应该关心该信使。如果下一跳字段包含“0xffffffff”(即“255.255.255.255”)，则将该信使称为“局部广播”信使，并且接收到该信使的所有节点必须检查该信使的内容并且进行相应动作。否则，该信使被称为“单播”信使，并且只有其IP地址与包含在下一跳字段中的IP地址相匹配的节点才能检查该信使的内容并且进行相应动作。估计量度是到达该节点已知的目的地的在先量度(即，成本或者距离)。只有在下一跳字段包含“0xffffffff”(即“255.255.255.255”)时，才对该字段进行核查。

图11例示了根据本发明一个实施方式的用于处理断开链路(brokenlink)的示例性处理1100的流程图。在一个实施方式中，通过无穷大的量度(即，大于最大允许量度的任意值)描述断开链路。当节点101检查到其通往相邻节点103的链路已断开时(通过第二层协议或者第三层协议)(1110)，该节点101检查其路由选择表中的每个路由选择条目并且向使用作为下一跳的相邻节点103的任意路由分配无穷大的量度(1120)。如果链路故障导致节点101仅丢失针对其具体目的地节点104的lm_route或者hsq_route而没有同时丢失两者(1130)，则可以对该链路故障进行内部处理(例如，如果lm_route断开而hsq_route未断开，则将lm_route设置为hsq_route(1140)并且由于节点101仍然具有通往目的地节点104的路由，所以不需要对外部进行立即更新。如果链路故障已经导致节点101丢失其通往具体目的地节点104的所有路由(1130)，则节点101将向其通往目的地节点104的路由分配更新的目的地序号(当前序号+1)(1150)(建立信息来描述断开链路是其中由除目的地节点以外的任意节点产生目的地序号的唯一情况)。节点101决定是否进行局部修复(1160)。如果答案为是，则节点101开始局部修复处理(1170)。否则，节点101通告其已经丢失其通往目的地节点104的所有路由(1180)。

在一个实施方式中，在节点丢失其通往具体目的地的所有路由时进行局部修复，而不是通告其已经丢失其通往所述目的地的所有路由(这样可能干扰所有其上游节点)，如果相应路由选择条目的局部可修复标志为真，则该节点可向所述目的地发送一局部广播信使，从而进行快速局部恢复。对用于维护局部可修复标志的逻辑进行如下概述。当对路由选择条目进行初始化时，将路由选择条目的局部可修复标志初始化为假。每当节点从除了其lm_route的当前下一跳以外的其它相邻节点接收到其序号大于或者等于所述lm_route的序号并且其量度小于或等于所述lm_route的量度的路由时，将局部可修复标志设置为真并将局部可修复时间设置为0。定期递增所述局部可修复时间(例如，在每个定期更新期间)。当局部可修复时间＞＝最大局部可修复(默认设置为2)*定期更新间隔时，则将局部可修复标志设置为假。

图12例示了根据本发明一个实施方式的局部修复处理1200的示例性流程图。当节点101丢失其通往具体目的地节点104的所有路由并且其局部可修复标志为真时，节点101将通过向其立即触发更新分组的信使区写入局部广播信使来启动局部修复处理(1210)。将该信使的目的地的IP地址设置为所述目的地节点104的IP地址(1220)。将信使的目的地序号设置为更新的目的地序号(1230)。将估计距离量度设置为无穷大，并且将信使的下一跳设置为“0xFFFFFFFF”(1240)。节点101将立即更新标志设置为真(1250)，将局部修复处理标志设置为真，将局部修复开始时间设置为当前时间，并将局部修复状态设置成显示无响应(1260)。节点101启动在设定时间回叫(call back)以检验局部修复进程的定时器(1270)。

在该节点开始局部修复处理以后，该节点侦听其相邻节点。在定时器超时以前，如果该节点从相邻节点接收到发往具有小于或者等于其在先lm_route.metric的估计量度的所述目的地的信使，则该节点将局部修复状态标志设置成表示响应被接受。在定时器超时的情况下，如果局部修复状态标志表示响应被接受，则节点101允许进行该局部修复处理。否则，节点101将通过将局部修复处理标志设置为假来放弃局部修复，并触发立即更新以通告其已经丢失其通往目的地节点104的所有路由。

对路由中的链路断开的局部修复有时导致通往所述目的地的路径长度增加。但是这只是临时的。当产生更大定期更新影响时，网络将收敛到恰当的最短路径。

当节点101丢失其通往具体目的地节点104的所有路由并且其局部可修复标志为假时，节点101广播立即触发更新分组500，表示“我丢失了通往目的地节点104的路由”。在一个实施方式中，该立即触发更新分组500在其距离区中包括多于一个的记录，并且如果自上一次更新以来，与除了目的地节点104以外的其它目的地相关的一些重要新路由选择信息已变得可用时，则立即触发更新分组500还可包括信使区520。节点101将与目的地节点104相关的其路由选择表条目590的立即更新标志设置为真。当节点101获悉通往目的地节点104的一新路由(具有较高目的地序号的路由)时，如果将立即更新标志设置为真，则节点101立即通知其相邻节点。

在从节点101接收到(报告了无穷大量度的)更新分组时，节点101的相邻节点会首先将它们自己的与目的地节点104相关的目的地序号与包含在来自节点101的更新分组中的目的地序号进行比较。如果节点101的相邻节点具有有限量度并且具有比更新分组携带的目的地序号更高的目的地序号，则节点101的相邻节点将lm_route设置为hsq_route(如果它们不相同)，并且发出关于其通往目的地节点104的路由的立即触发更新，通知节点101“你可以使用我”。由于节点喜欢具有较高目的地序号的路由，所以节点101将接受该新路由，并在立即更新标志为真时立即使用该新路由。如果节点101的相邻节点具有与由信使携带的目的地序号相等的目的地序号，则除非节点101是所述相邻节点的lm_route中的所述相邻节点的下一跳并且所述相邻节点的hsq_route与所述相邻节点的lm_route不相同，否则所述相邻节点将忽略此路由。如果节点101的相邻节点具有低于由更新分组携带的目的地序号的目的地序号，则存在如下两种情况：

1)如果此相邻节点使用节点101作为其lm_route中的其当前下一跳，并且该相邻节点的hsq_route或者与其lm_route相同，或者具有无穷大的量度，则该相邻节点将根据局部可修复标志的值来决定是开始局部修复处理还是通告“我丢失了我通往目的地节点104的路由”并进行相应动作。

2)否则，此相邻节点如同认为其仍然具有通往目的地节点104的至少一条路由那样，沿着与目的地节点104相关的其lm_route的方向发送单播信使。

在任何一种情况下，节点101的该相邻节点在接收到来自节点101的“我丢失了我到目的地节点104的路由”的更新分组时，通过将其立即更新标志设置为真来进行记录。当所述相邻节点获悉到目的地节点104的新路由(具有较高目的地序号和有限量度的路由)时，所述相邻节点立即通知节点101。

在接收到信使时，中间节点首先检查其本身是否是信使的目的地。如果是，则该节点在其现有序号不大于由信使携带的序号的情况下，将其序号加2，并且随后广播关于其自身的立即路由选择更新。如果该节点不是所述目的地，则该节点将检查其hsq_route是否具有有限量度和比所述信使的序号更高的目的地序号。如果是这样，则该节点将lm_route设置为hsq_route并且广播关于其通往目的地节点104的较新路由的立即更新。如果并非如此，则该节点将其立即更新标志设置为真，并且如果满足以下两个条件，则向其通往目的地节点104的lm_route的下一跳转发信使：

i)节点认为其仍然具有一通往目的地节点104的路由(具有有限量度)。

ii)该信使是局部广播信使，或者如果该信使是单播信使，则该节点是在该信使的“下一跳”字段中识别出的节点。

如果没有满足上述两个条件的至少一个，则该信使被“放弃”。

三个因素对于该方法的效率和可扩展性做出主要贡献：

1)针对链路故障后的路由恢复，方向波方法比现有技术的扩散式(flooding)方法更有效。因为信使利用通过底层先应式路由选择协议发现并维护的路由，并且仅朝向目的地前进，因此与沿所有方向前进并可能影响整个网络的“扩散式”相比，产生少得多的路由选择开销。

2)收敛是相对局部的。以较慢的速度通过较大的更新对路径进行局部修补。在一个实施方式中，在链路断开后，只对直接受影响的节点和在去往所述目的地的信使的路由上的节点进行立即更新，所有其它节点将忽略它或者以慢得多的节奏对它们的相邻节点进行更新。该局部修复方法进一步使所述收敛局部化并且减少了路由选择开销。

3)通过将向不同方向传播的信使分组为更新分组，即用于发送路由选择信息的公共载体，可进一步减少路由选择负担并且极大改善可扩展性。

假设有两条从移动节点101到目的地移动节点104的路径。一条路径的跳数为3，并且99％的时间可用。另一条的跳数为2并且只有20％的时间可用。如果使用跳数作为量度，则所有的通信量将都被路由到第二条路径，因为第二条路径具有较小的跳数。但是实际上，第一条路径在可靠性和性能(即吞吐量)方面更好，因此更适合于应用。通过该简单示例，很明显在选择路由时还应该考虑路径质量和路径容量。在一个实施方式中，一种可以实现这一点的方式为采用如下组合量度：

metric(u，v)＝C1/link-quality(u，v)+C2/link-capacity(u，v)+C3*1    (1)

其中metric(u，v)是用于节点u与v之间的无线链路的链路量度，link-quality(u，v)表示该链路的质量(或者鲁棒性)，link-capacity(u，v)表示该链路的可用带宽。此外，在式(1)中，C1、C2和C3是用于调整各个因数的权重的常量。

在网络拓扑的保密性很重要的情况下，可以应用常规的密码技术(如通过PGP加密的或者通过某些共享密钥加密的自适应无线路由选择控制通信消息的交换)来确保只有被授权的人员才能读取以及解释该控制通信。此外还使用消息认证来防止恶意或者故障节点注入无效控制通信量并且危及网络整体的安全。

已经公开了一种用于网状网中的自适应无线路由选择协议的方法和系统。尽管已经针对具体实施例和子系统描述了本发明的方法和系统，但本领域的技术人员应当明了本发明不限于这些具体实施例或者子系统，而是还可扩展到其它实施方式。