CN101552732B - 混合网格路由选择协议 - Google Patents

Abstract

本发明公开了一种在无线网格网中由源节点和目的节点之间的节点通过使用媒体访问控制地址在源节点和目的节点之间建立路由来选择路由的方法。还公开了节点使用媒体访问控制地址来选择路由以加入无线网格网中的多播组的一种方法。

Description

混合网格路由选择协议

本申请是2005年3月10日提交的中国专利申请No.200580048992.4的发明名称为“混合网格路由选择协议”的分案申请。

技术领域

本发明涉及一种用于自动拓扑学习和路径选择的路由选择机制。具体地，本发明涉及基于媒体访问控制地址在无线局域网格网中确定路由。

背景技术

无线局域网格网，也称为基于无线LAN的ad hoc网络，包括通过无线电链路互连并直接或间接地相互通信的两个或多个节点。该网络可以通过入口连接到互联网或其他网络。在无线局域网格网中，已经使用IP层路由选择协议来发现从源节点到目的节点的路由。IP层ad hoc路由选择协议基于IP地址。然而，诸如WLAN接入点之类的一些设备基于IEEE 802.11媒体访问控制(MAC)地址转发数据分组，并只操作于链路层(层2)。此外，因为数据分组不需要经过IP层(层3)，所以在层2转发数据通常比在IP层快。

Ad Hoc按需距离矢量(AODV)协议是一种操作于IP层的ad hoc路由选择协议。该协议可以支持单播和多播路由发现。路由是基于按需发现的。当源想要向目的节点发送分组时，如果源不具有到目的节点的路由并需要该路由，则源通过在网络上广播路由请求消息来发现到目的地的路由。该消息包括源节点和目的节点的IP地址以及其他必要信息。目的节点或具有到目的节点的有效路由的节点通过向源节点发送路由应答来应答此请求。路由请求和路由应答消息在用于转发和反向路径/路由的中间节点中的每一个中建立路由选择表。如果在给定的路由生命期内不使用该路由，则所建立的路由到期。按需路由选择减少了由于网络拓扑变化(例如，节点移动和故障)的失效路由的影响以及保持不用路由的需要。然而，因为源节点需要在能够发送数据之前建立路由，所以引入了路由发现延迟。源节点还需要在路由发现期间对数据进行缓冲。

目的序列距离矢量(DSDV)是针对无线局域网格网的先应式路由选择协议。网络中的节点交换路由选择控制消息，使得每个节点处的路由选择表都包括到无线局域网格网中的所有目的节点的信息。由中间节点沿着路径基于路由选择表将数据分组从源节点转发到目的节点。为了保持有效路径，并且避免由于链路/节点故障和网络拓扑变换而导致的路由选择环路，每个节点不仅周期地传输路由更新，而且在重要的新信息可用时立即广播该更新。虽然DSDV允许使用层2的MAC地址或层3的IP地址来转发分组，并且不存在路由发现延迟，但是因为遍布网络的路由选择消息广播，这导致了相对高的路由选择开销。尤其是在网络中的节点较快地移动以及网络拓扑结构频繁变化时，将网络容量的大部分用于保持路由选择信息是当前的。此外，由于处理和电池限制或其他原因，一些节点可能无法转发源自其他节点的数据分组。然而，上述协议假设每个节点都同意基于请求向其他节点转播数据分组，并且不考虑非转发节点。

在无线局域网格网中，两个或多个节点通过IEEE 802.11链路互连。每个节点都具有唯一的IEEE 802.11媒体访问控制(MAC)地址。当源节点向目的节点发送数据分组时，源节点需要知道从源节点到目的节点的路径/路由。

所需要的是基于目的MAC地址来发现并建立路径的路由选择机制。本发明所解决的问题是，在无线局域网格网中源节点如何基于目的节点的IEEE 802.11 MAC地址来发现并建立到目的节点的路径。

发明内容

无线LAN(WLAN)网格网包括通过IEEE 802.11链路互连的两个或多个节点。每个节点将参与针对自动拓扑学习和路径选择的路由选择协议。本发明提供了一种用于基于IEEE 802.11媒体访问控制(MAC)地址来发现路由的机制。该机制同时支持按需路由发现和先应式路由建立。该机制可以发现并建立路由以满足实时多媒体应用的服务质量(QoS)需求，并保持这种路由。此外，该机制支持非转发节点。

描述了一种在无线网格网中由源节点和目的节点之间的节点通过使用媒体访问控制地址在源节点和目的节点之间建立路由来选择路由的方法。还描述了节点用以通过使用媒体访问控制地址在所述节点和多播组之间建立路由来选择路由以加入无线网格网中的多播组的一种方法。在这两种情况中，可以通过使用按需路由选择或先应式路由选择来建立所建立的路由。尽管在无线局域网格网方面描述这里所描述的本发明时，但是在其中建立路由的网路并不局限于无线局域网格网，而可以是任何形式的无线网格网。具有代理服务器的接入点可以加入无线网格网。站点与接入点相关联，但站点并非无线网格网的成员，因此通过接入点发生与站点的通信，并且该通信对于所关联的站点是透明的。

附图说明

当结合附图理解以下细节描述时，可以最好地理解本发明。附图包括下面简要描述的以下图示：

图1描述了示出以路由请求(RREQ)消息对网格网的泛洪以及反向路径建立的无线局域网格网。

图2描述了示出路由应答(RREP)消息的单播和前向路径建立的无线局域网格网。

图3A描述了示出用于到RANN消息发起者的路由的先应式建立的路由宣告(RANN)消息的泛洪的无线局域网格网。

图3B描述了示出源节点发送无偿RREP消息以建立到源节点的反向路由的无线局域网格网。

图4是示出了节点按需和先应式地建立路由，以及根据本发明的原理处理路由选择控制消息的方法的图示。

图5描述了具有多个关联站点的无线局域网格接入点。

图6是示出了根据本发明的无线局域网格接入点的示意图。

图7A示出了新节点以请求其加入多播组的路由请求(RREQ)消息对网格网的泛洪。

图7B描述了通过不同多播树成员发送回路由请求(RREQ)消息的发起者的路由应答(RREP)消息。

图7C示出了传输路由激活消息的路由请求(RREQ)消息的发起者。

图7D示出了已添加到多播组的新节点。

图8A示出了多播叶节点如何退出/离开多播组。

图8B示出了修剪之后的多播树。

图9A示出了具有断开链路的多播树。

图9B描述了下流节点尝试为断开的链路设置旁路。

图9C示出了下流节点从有资格的多播树成员处接收路由应答(RREP)消息。

图9D示出了下流节点激活新的链路。

图9E描述了为断开的链路设置旁路的新多播树。

具体实施方式

本发明执行层2的路由选择功能，因此可以基于IEEE 802.11MAC地址将分组从源节点传输并转发到目的节点。本发明同时支持按需路由选择和先应式路由选择。此外，一些节点只能发送或接收数据，但由于处理和电池限制或其他原因而不能转发源自其他节点的数据。本发明可以处理这些非转发节点。可以将本发明的路由选择机制用于客户端-服务器应用配置/拓扑、对等应用配置/拓扑、以及混合应用配置/拓扑。

混合网格按需路由选择与IP层路由选择协议AODV相似，都是基于路由请求和路由应答消息。对于层2的混合网络按需路由选择，当源节点想要向一些目的节点发送分组时，源节点检查其用于路由的路由选择表。如果存在有效路由，则源节点将分组转发给路由选择表中所指定的针对此目的节点的下一跳。如果不存在有效路由，则源节点通过广播路由请求(RREQ)消息发起路由发现。不同于AODV，RREQ消息包括具有序列号和可选的层3信息的发起者IEEE 802.11MAC地址(不是IP地址)，以及具有最新知道的目的序列号和针对此目的节点的可选层3信息的目的节点MAC地址(不是IP地址)。RREQ消息还包括消息ID、路由度量、使用期限(TTL)和路由生命期。在发起路由请求之前，RREQ消息将使自身序列号递增。

通过广播RREQ消息或诸如以下将要描述的RANN消息之类的其他网格路由选择控制消息，IEEE 802.11广播MAC地址可以用作所传输的网格路由选择控制消息的目的地址。可选方案是分配用于泛洪网格路由选择控制消息(网络路由选择控制组地址)的专用IEEE 802.11多播MAC地址。此地址指定了所有网格节点。网格节点接收指向此网格路由选择控制组地址的消息。非网格节点可以不接收指向此网格路由选择控制组地址的消息。

参照描述了无线局域网格网的图1，节点105是源节点，节点110是目的节点。所有的其他节点115是潜在的/可能的中间节点，它们是可以通过其在源节点105和目的节点110之间传递消息/分组/数据的节点。基于所选的路由/路径，确定用于从源节点向目的节点传输内容的特定单元的中间节点115的集合。源节点105和目的节点110带纹理或阴影，以便将它们与潜在的/可能的中间节点115区分开。应注意的是，在另一个实例中，现在(图1)作为源和目的节点的节点可以是此实例中的中间节点，而其他节点变成源和目的节点。在图1中，源节点105使用路由请求(RREQ)消息来泛洪无线局域网格网。基于该路由请求消息建立反向路径。

节点一旦接收到RREQ消息，则检查发起者地址和消息ED，以察看以前是否曾见过这个RREQ消息。如果这是第一RREQ消息，则节点通过增加从其接收RREQ消息的节点和该节点本身之间的链路成本来更新度量域，然后在它的路由选择表中建立到该发起者的反向路由。如果该节点是目的节点，或者如果节点具有到目的地的未到期的有效路由，并且该目的节点的序列号至少如RREQ消息中所表示的一样大，则该节点通过将路由应答(RREP)消息单播回发起者来进行响应。否则，该节点以新的度量传播RREQ消息。如果这不是第一RREQ消息，则该节点通过增加从其接收RREQ消息的节点和该节点之间的链路成本来更新到发起者的度量域。如果新度量小于在节点的路由选择表中所记录的度量，则该节点更新反向路由。否则，则丢弃该RREQ消息。如果该节点满足上述要求，则使用RREP消息来应答发起者。否则该节点以新的反向路由度量来传播RREQ消息。将反向路径/路由用于将RREP消息发送回RREQ消息的发起者以建立前向路径，此外还用于源节点和目的节点之间的双向通信。

通过单播将RREP消息发送回RREQ消息的发起者，以建立前向路径。该RREP消息包括发起者MAC地址、目的MAC地址以及可选的目的层3信息、目的节点的序列号、度量、使用期限以及路由生命期。如果目的节点响应，则使用其当前序列号的最大值以及RREQ消息中的目的地序列号。度量的初始值为零。目的节点也设置了路由的生命期。如果中间节点响应，则使用其对目的序列号和度量的记录，以及基于路由表条目所计算的路由生命期。

参照描述了无线局域网格网的图2，节点205是源节点，节点210是目的节点。确定了针对特定源节点205和目的节点210的中间节点220的集合。对于源节点205和目的节点210之间的路由/路径，中间节点215不再是中间节点。通过从目的节点210到源节点205的单播RREP消息建立了前向路径。

RREP消息通过在路由请求广播期间所建立的反向路由进行单播。当中间节点接收到RREP消息时，中间节点通过增加从中接收RREP消息的节点和中间节点本身之间的链路成本来更新度量。中间节点在其路由选择表中建立前向路径，并将RREP消息转发给RREQ消息的发起者。如果节点接收到一个以上的RREP消息，则转发第一RREP消息。仅在新的RREP消息包括更大的目的序列号或具有更好度量的相同目的号时，该节点才更新路由选择表并转发新的RREP消息。否则，则丢弃新的RREP消息。图1和图2示出了RREQ消息泛洪网格网，以及通过单播RREP消息建立前向路径。发起者可以在接收到第一RREP消息时立即开始数据/分组传输，并且如果发现更好的路由，则可以稍后更新它的路由选择信息。

节点可以具有多个IEEE 802.11无线接口。节点具有唯一的节点标识符，即节点的IEEE 802.11 MAC地址，并且每个接口还具有其自身的IEEE 802.11 MAC地址。将节点的MAC地址用于RREQ和RREP消息以及下面所要描述的其他路由选择控制消息。当多接口节点广播RREQ消息时，该节点可以通过所有接口广播该RREQ消息。当多接口节点通过单播RREP消息来响应RREQ消息时，该节点向通过其接收相应RREQ消息的接口发送RREP消息。

路由选择表包括针对目的节点的条目。每个条目都包括目的MAC地址和它的可选层3信息(所支持的层3协议和地址，例如目的节点的IP地址)、目的序列号、下一跳MAC地址、到达下一跳的接口、上流节点列表和使用此路由的接口、状态和路由选择标记(例如，有效、无效)、到目的地的度量、以及路由生命期。每次使用路由时，更新该路由的生命期。如果在路由生命期内没有使用该路由，则该路由变成无效。在无效路由的删除定时器到期时，将删除该无效路由。发起者可以在接收到第一RREP消息时立即开始数据传输，并且如果发现更好的路由，则可以稍后对路由选择信息进行更新。当中间节点接收到数据分组时，该中间节点基于目的MAC地址来检查路由选择表。如果存在针对此目的地的有效条目，则中间节点将该分组转发到此路由选择条目中所指定的下一跳。在到达目的节点之前，这个过程将继续。

在按需路由选择中，只保持当前所使用的路由。这降低了路由选择开销。然而，因为源节点必须在可以发送数据之前建立路由，这导致了额外的延迟。源节点还需要在路由发现期间对数据进行缓冲。为了减少路由发现延迟，可以使用先应式路由选择。此外，在许多节点与特定节点通信的情况下，如果这些节点中的每一个都单独发现到这个特定节点的路由，则需要显著的控制业务量。例如，网格网中的许多节点通过将该网格网连接到互联网或其他网络的一个或多个入口节点来访问互联网或其他网络。希望的是，入口节点先应式地宣告在网格网中到它的路由。本发明将按需路由发现和先应式路由宣告结合。节点可以由网络管理员显性配置，或根据特定策略隐性确定在网格网中执行先应式路由选择。例如，一项策略是所有网格入口节点都应该执行先应式路由宣告。参照图3A，节点310通过周期性地广播未被请求的路由宣告(RANN)消息来宣告其自身，从而网格网中的其他节点315可以获悉到RANN消息发起者310的路由。换言之，发起RANN消息的节点使用未被请求的RANN消息来泛洪无线局域网格网，以便先应式地建立到其自身的路由。当多接口节点广播RANN消息时，该多接口节点可以通过其所有接口来广播该RANN消息。RANN消息包括具有目的序列号和可选的层3信息的发起者节点的IEEE 802.11MAC地址(不是IP地址)。RANN消息还包括路由度量、使用期限以及路由生命期。注意，不同于RREQ消息的是，RANN消息中的目的地址是RANN消息发起者的MAC地址，因为该RANN消息用于先应式地在网格网中建立到RANN消息发起者的路由。

当节点315接收到RANN消息时，该节点通过增加从其接收RANN消息的节点和该节点本身之间的链路成本来更新到RANN消息的发起者的度量域。如果该节点在其路由选择表中不具有到此目的节点(即，RANN消息发起者310)的有效路由，则该节点在其路由选择表中创建到此目的节点的路由。该节点以新度量通过其接口中的一个或多个向相邻节点广播RANN消息。当该节点具有到此目的地的有效路由时，仅在RANN消息包括较大的目的序列号或具有更好的度量的相同目的序列号时，该节点才更新其路由选择表，并以新度量向相邻节点广播RANN消息。否则，则丢弃该RANN消息。按照这种方式，在网格网中建立到RANN消息发起者的路由。

参照图3B，当源节点305想要向目的节点310发送数据分组时，该节点可能已经从目的节点的路由宣告中获得到此目的节点310的前向路径。在这个实例中，该节点可以立即传输分组。然而，不存在从目的节点310到源节点305的反向路由也是可能的。如果需要双向通信，则源节点305可以通过中间节点320沿着由目的节点310的RANN消息所建立的前向路径，向节点310单播地发送无偿RREP消息。该RREP消息建立了到源节点305的反向路由。

一些节点想要只作为源节点或目的节点而加入无线局域网格网，即不转发源自其他节点的业务。节点可以由管理员配置为非转发节点，或基于特定策略被确定为非转发节点。例如，一个这样的政策是，如果节点的电池能量低于阈值，则该节点将变成非转发节点。非转发网格节点在其想要传输分组时发送RREQ消息。只有当该非转发节点是接收到的RREQ消息中的目的节点时，才应答路由请求消息。如果该非转发节点不是接收到的RREQ消息中的目的节点，不应答路由请求消息。非转发节点接收RANN消息，以获悉到RANN消息的发起者的路由。非转发节点发送RANN消息，使得可以先应式地建立指向该非转发节点的路由。然而，非转发网格节点不向相邻节点转发任何路由选择控制消息，包括RREQ、RREP和RANN消息。通过这样做，不存在将非转发节点作为中间节点的路由。

如果链路断开，则向活跃路径的受影响的源节点发送路由错误(RERR)消息。断开链路的上流节点，即靠近源的节点，发起RERR消息。在发送RERR消息之前，该节点还将损坏路由标记为无效，将损坏路由的度量设为无限大，并由于路由选择表中此链路故障而使不可到达的目的地的目的序列号递增。RERR消息包括由于此链路故障的所有不可到达的目的地、以及它们递增后的序列号的列表。该节点向其一个或多个上流相邻节点广播该RERR消息。对于多接口节点，通过具有使用此故障链路的路由的接口来发送RERR消息。当相邻节点从其下流节点接收到RERR消息时，相邻节点检查是否具有使用下流相邻节点至所列出目的地的路由。如果有，则将这些路由标记为无效，并将这些路由的度量设为无限大。然后将RERR消息传播给上流节点。当源节点接收到RERR消息时，源节点重新发起路由发现。如果节点接收到具有目的MAC地址的数据分组时(该MAC地址不具有活跃/有效路由)，则该节点创建针对目的节点的RERR消息，并将此RERR消息发送到上流相邻节点。

本地连接性管理由节点周期性地向相邻节点发送信标(HELLO消息)来实现。从相邻节点接收到信标的节点在其路由选择表中更新与该相邻节点关联的路由生命期。如果节点不能从相邻节点接收针对给定的Hello_life的信标，则到该相邻节点的链路断开，然后在路由选择表中更新针对此相邻节点的路由选择信息。

图4是示出了节点按需地和先应式地建立路由、以及根据本发明的原理处理路由选择控制消息的方法。在步骤402中，节点确定是否需要先应式路由发现。此信息可以由网络管理者显性配置，或者通过如上所述的策略隐性获得。如果需要先应式路由发现，则在步骤404中周期性地发送RANN消息。如果不需要先应式路由，则节点返回空闲状态。在步骤410中，当节点从上层应用中接收到新的数据分组时，该节点检查是否具有到目的节点的前向路径/路由(步骤412)。如果没有，则该节点通过发送RREQ消息来发起按需路由发现(步骤414)。该节点等待相应的RREP消息。一旦接收到RREP消息(步骤416)，则建立前向路由(步骤422)，并开始传输数据(步骤428)。如果RREQ消息丢失，则可以允许源节点重传该RREQ消息设定次数(步骤418)。如果在RREQ消息的最大重传次数之后仍然没有接收到RREP消息，则通过错误消息通知应用该目的节点不可到达(步骤420)。如果源节点具有前向路由，则源节点检查是否具有用于双向通信的反向路由(步骤424)。如果前向路由是通过目的节点的RANN广告所建立的，则可能不存在反向路由。在反向路由可用的单向通信或双向通信的情况下，源节点在步骤428中立即传输数据。在不具有反向路由的双向通信的情况下，源节点发送无偿RREP消息(步骤426)，以建立反向路由。一旦发送了无偿RREP消息，源节点则可以传输数据(步骤428)。

在步骤440中，当网格网中的节点接收到RANN消息，则设置/建立/恢复到RANN消息的发起者的路由(步骤424)。如果该节点为非转发节点(步骤444)，则不转发RANN消息(步骤448)。如果该节点是转发节点，则转发RAISIN消息(步骤446)。当节点在步骤450中接收到RREQ消息时，设置/建立/恢复反向路由(步骤452)。节点确定其是否为非转发节点(步骤454)。只有在该节点是RREQ消息中所指定的目的节点时(步骤460)，非转发节点才通过将RREP消息单播发送回RREQ消息的发起者来应答此RREQ消息(步骤462)。如果该节点并非目的节点，则非转发节点不转发RREQ消息(步骤464)，而是丢弃RREQ消息。对于转发节点，如果该节点是目的节点或者如果该节点具有到目的节点的有效路由(步骤456)，则该节点通过将路由应答(RREP)消息单播回RREQ消息的发起者来进行响应(步骤462)。否则传播RREQ消息(步骤458)。当节点在步骤470中接收到RREP消息，则设置/创建/恢复该路由(步骤472)。如果该节点是非转发节点或者该节点是此RREP消息的目的节点(步骤474)，则该节点不转发RREP消息(步骤478)。否则，则转发该RREP消息(步骤476)。当节点检测到链路故障或者当节点接收到RERR消息时(步骤480)，该节点去激活已损坏的路由(步骤482)。如果该节点是源节点(步骤484)，则该节点发现/获悉新的路由(步骤490)。否则，如果该节点不是非转发节点(步骤486)，则转发RERR消息(步骤488)。如果该节点是非转发节点，则该节点不转发RERR消息(步骤492)。

多个站点可以与WLAN中的接入点(AP)相关联。参照图5，节点505是加入网格网的AP。然而，站点510不是无线局域网格网525的一部分。站点510形成具有接入点505的基于基础结构的网络/子网。网格AP 505作为这些站点510的代理服务器，以及路由选择对于非网格站点510是透明的。当网格AP 505转发源自关联站点510的数据分组时，发现到目的节点的路由。网格AP 505还通过向RREQ消息发起者单播RREQ消息，来响应相关站点的RREQ消息。网格AP 505通过广播RANN消息，宣告到关联站点510的路由。可以使用单个RANN消息来宣告具有单独序列号的多个目的地址、可选层3信息、使用期限(TTL)、度量和路由生命期。每个目的地址与一站点相对应。

图6是示出了具有代理服务器600的网格接入点(图5中的节点/AP 505)的细节的方框图。具有代理服务器600的网格AP具有两个逻辑接口。一个是与关联站点通信的站点发送/接收(TX/RX)接口模块645，另一个是与网格网通信的网格网发送/接收(TX/RX)接口模块655。这两个逻辑接口可以使用两个操作于不同信道的物理IEEE802.11无线接口(每个物理接口与一个逻辑接口相对应)或使用单个IEEE 802.11无线接口来实现。站点关联控制模块650执行站点关联控制。网格路由选择模块605负责在网格网中路由数据。网格路由选择模块605包括网格路由发现单元610，用于发送路由请求以便发现到无线局域网格网中的目的节点的路由(执行按需路由选择)。网格路由选择模块605还包括网络路由宣告单元615，用于在网格网中发送RANN消息(执行先应式路由选择)。路由选择消息处理单元620对所接收到的路由选择控制消息进行处理，并应答/转发路由控制消息。如果检测到链路断开，则路由保持单元625保持路由，并产生路由错误消息。网格路由选择模块605还将路由选择表630保持在其高速缓存中。数据处理单元635基于该路由选择表来发送/接收/转发数据分组。网格路由选择模块605通过网格网TX/RX接口模块655与网格网相接口。站点代理服务器640桥接关联站点和网格网。站点代理服务器640将关联站点信息从关联控制模块650传递到路由选择模块605。站点代理服务器640与路由选择模块605相互作用以便针对关联站点执行路由选择和数据转发功能(例如在站点代理服务器640转发源自关联站点的数据分组时发现到目的节点的路由，响应关联站点的RREQ消息，以及通过在网格网中发起RANN消息来宣告到关联站点的路由)。

本发明支持多播和单播路由选择。由节点保持单独的多播路由选择表。与上述单播按需路由发现相似的是，多播按需发现基于路由请求和路由应答消息，这也与IP层路由选择协议AODV相似。节点能够随时动态地加入或离开多播组。每个多播组都具有多播组引导者(leader)。组引导者保持多播组序列号。在检测到多播组引导者故障的情况下，创建新的组引导者，从而不存在故障的中心点。

当节点想要加入多播组时，节点向所有网格节点广播RREQ消息。该RREQ消息包括发起者的MAC地址、当前序列号、可选层3信息(支持层3协议和地址，例如IP地址)、目的MAC地址(即，待加入的多播组地址)、组的最新获知的序列号、消息ID、度量、使用期限参数和加入标记。多播树的任何成员都可以响应RREQ消息，但只有多播树的成员可以进行响应。非成员节点(非多播树的成员)不响应RREQ消息，但是创建到发起者的路由/路径。然后，非成员节点向相邻节点转发该RREQ消息。下面将对此进行详细描述。发起者等待发现时间段的期限，以便接收应答或进行应答。如果没有应答，则发起者重传/重新广播消息ID增加1的RREQ消息。在接收到应答或已经超过重试限制之前，发起者继续这种方式。如果在最大重试次数之后没有接收到应答，则发起者可以变成新的多播组的多播组引导者。

当节点从另一个节点(不是该组中的)接收到加入多播组的请求时，该节点更新度量域并将发起者的不活跃条目添加到其多播路由选择表中。多播路由选择表中的每个条目都具有指示链路活跃或不活跃的标记。对于多播组，将不通过不活跃链路转发/传输数据/分组。该节点还按照单播路由建立规则，在单播路由选择表中创建到发起者的反向路由/路径条目。

多播树包括作为多播组的成员的节点，以及针对多播组的转发节点。转发节点是作为多播树成员的节点，但并非多播组的成员。转发节点对于所接收到的数据/分组/内容起到了“通道”或“管道”的作用。转发节点不使用其所接收到的数据/分组/内容，并且对所接收到的数据/分组/内容不感兴趣。如果多播树所记录的序列号至少与RREQ消息中所携带的一样大，则多播树的任何成员都可以应答加入多播组的RREQ消息。多播组引导者总是响应加入该多播组的RREQ消息。响应加入多播组的RREQ消息的节点按照单播路由建立规则，在其路由选择表中建立了到发起者的单播反向路由。响应节点还在多播路由选择表中建立针对发起者的路由。将该路由标记为不活跃的。然后，响应节点将RREP消息单播回RREQ消息的发起者。当沿反向路径的节点接收到RREP消息时，该节点更新度量，并在其多播路由选择表中建立前向路径/路由。将在多播路由选择表中所建立的路径/路由标记为不活跃的。然后该节点将RREP消息转发到下一跳。

多播树中的每个节点具有多播路由选择表。多播路由选择表具有针对每个多播组的条目。多播路由选择表的条目包括多播组MAC地址、下一跳MAC地址、到下一跳的接口、多播组序列号、到多播组引导者的度量、标记(活跃/不活跃以及路由标记)以及路由生命期参数。每次使用/经过路由/路径时，更新路由生命期参数。如果在指定路由生命期内未使用该路由/路径，则该路由/路径变成无效。

加入多播组的RREQ消息的发起者可以从多播树的不同成员接收多个RREP消息。每个应答都表示到该多播组的潜在路由/路径。发起者追踪所接收到的应答，并等待路由发现周期/间隔的到期。然后，发起者选择具有最大多播组序列号以及具有到该多播组的最佳度量的路由。通过单播具有设置为加入下一跳的加入标记来多播激活(MACT)消息，发起者激活在路由发现周期/间隔到期时所选择的路由/路径。针对多播路由选择表中的所选路由/路径，发起者将活跃/不活跃标记设置为活跃的。因为沿着路径的每一跳都接收到MACT消息，所以该节点激活其多播路由选择表中的路由，以及如果该节点不是RREP消息的发起者，则将MACT消息转发到下一跳。在RREP消息的发起者接收到MACT消息之前，继续此过程。应注意的是，一个节点可以同时是两个多播组/树的成员。

图7A-7D示出了新节点“N”如何加入多播组。暗阴影节点是多播组的成员和多播树的成员。白色节点是并非多播树或多播组的成员的节点。节点“N”是想要加入多播组的新节点。以“F”作为标记的节点是前向节点。现在，参照图7A，节点“N”是想要加入多播组的新节点。节点“N”在尝试加入多播组时使用RREQ消息来泛洪网格网。在RREQ消息到达作为多播树的成员的节点之前，通过并非多播树的成员的节点来传输该RREQ消息。图7B描述了返回希望加入多播组的新节点的RREP消息。由不同多播树成员沿反向路径将该RREP消息发送回RREQ消息的发起者。图7C示出了传输路由激活消息(MACT)的RREQ消息的发起者。RREQ消息的发起者单播具有设置以激活到多播组的路由/路径的加入标记的MACT消息。图7D示出了已添加到多播组的新节点。已经将并非多播组或多播树成员的节点添加为转发节点，因而该节点变成多播树的成员。

如果作为多播组成员的节点想要退出/离开该组，则该节点使用设置为修剪的修剪标记来向下一跳单播MACT消息，并删除其多播路由选择表中到多播组的条目。一旦沿路径的下一节点接收到具有设置成修剪的修剪标记的MACT消息，则该节点删除针对向其传输MACT消息的节点的路由选择信息。如果接收具有设置成修剪的修剪标记的MACT消息的节点不是多播组的成员，并且该节点在删除掉希望放弃其在多播组中的成员资格的节点的情况下变成叶节点，然后将其自身从多播树剪除。叶节点通过向其下一跳单播具有设置成修剪的修剪标记的MACT消息，将其自身从多播树中修剪掉。如果接收到具有设置成修剪的修剪标记的MACT消息的节点是多播组的成员或者不是叶节点，则该节点不能修剪其本身。

图8A到图8B示出了节点“A”如何放弃其在多播树和组中的成员资格。暗阴影节点是多播组的成员以及多播树的成员。白色节点是并非多播树或多播组成员的节点。以“F”作标记的节点是转发节点。图8A示出了多播叶节点如果退出/离开多播组。节点“A”单播具有设置成修剪的修剪标记的MACT消息，以便放弃其在多播组和树中的成员资格。图8B示出了修剪后的多播树。在节点“A”从多播组和树中放弃其成员资格后，留下作为转发节点的节点“B”作为叶节点，从而该节点将其本身从多播树修修剪掉。

每个Hello_mterval，多播树上的节点都必须接收来自每个相邻节点的传输。传输包括多播数据分组、RREQ消息、Hello消息、信标消息或组问候(GRPH)消息。由组引导者沿多播树周期性地发送GRPH消息。如果节点在HelloJlife内未能接收到来自多播树上的相邻节点的任何传输，则到此相邻节点的链路是断开的。当链路断开时，断开的节点下流(即，距离多播组管理者较远的节点)尝试修复该链路。实际上，这是为断开的链路设置旁路并产生回到多播树的可选路径的尝试。负责尝试修复断开的链路或通过发现可选路由来为断开的链路设置旁路的下流节点发送加入多播组的RREQ消息，该RREQ消息包括指示了发送节点与组引导者的度量的扩展字段。响应RREQ消息的节点必须是具有足够新鲜的序列号(这里的序列号至少与RREQ消息中所携带的多播组序列号一样大)的多播树的成员，并且到多播组管理者的度量必须好于RREQ消息中所指示的度量。在路由发现周期/间隔到期时，发起尝试为断开的链路设置旁路的RREQ消息的节点选择路由/路径，并单播具有设置为加入下一跳的加入标记的MACT消息，以便激活最新发现的路由。如果不能通过任何分支再次加入该树来修复多播树，那么负责为断开的链路设置旁路的下流节点变成新的多播树的新的多播组引导者。

图9A-9E示出了为断开的多播树链路设置旁路。图9A示出了具有断开的链路的多播树。在这个实例中，节点“A”和节点“B”之间的链路断开。图9B描述了下流节点(节点“A”)尝试通过发送请求加入多播组的RREQ消息来为断开的链路设置旁路。图9C示出了下流节点(节点“A”)从有资格的多播树成员处接收RREP消息。图9D示出了下流节点(节点“A”)使用具有设置成加入的加入标记的MACT消息来激活新的链路。图9E描述了为断开的链路设置了旁路的已修复的多播树。需要注意的是，断开的链路实际上并不是修复的，而是通过使用可用的路由发现机制来为其设置了旁路。

与单播相似，为了减少路由发现延迟，本发明支持先应式路由选择。本发明将按需路由发现和先应式路由宣告结合。对于多播，如果该节点是多播组引导者，则该节点可以由网络管理员显性配置，或根据特定策略隐性确定，以便在网格网中执行先应式路由选择。所配置的组引导者通过周期性地广播未经请求的路由宣告(RANN)消息来广告多播组，使得网格网中的其他节点能够获悉到多播组的路由。RANN消息包括具有组序列号和可选层3信息的多播组的IEEE 802.11MAC地址(不是IP地址)。RANN还包括路由度量、使用期限和路由生命期。

例如，对于多媒体和视频应用，支持WLAN网格网中的服务质量(QoS)是必要的。为了支持QoS，可以在已扩展的RREQ消息的可选字段中携带例如数据的最大延迟和最小带宽需求的QoS需求。为了响应或转发具有QoS扩展的RREQ消息，节点必须满足QoS限制。否则，则丢弃此QoS RREQ消息。在建立QoS路由之后，如果沿路径的任意节点检测到其不再满足所请求的QoS参数，则该节点向发起者发送RERR消息。RERR消息也可以携带诸如此链路的可用带宽和延迟参数之类的当前测量的QoS参数。发起者可以决定继续使用具有较低QoS的路由，或发现另一个路由。例如，RERR消息指示了链路上可用的当前带宽等于比发起者之前所请求的低的值。发起者可以减少其源速率，以满足当前可用的带宽或发现具有原始需要带宽的新路由。

可以理解的是，本发明可以实现为硬件、软件、固件、特定目的的处理器、或这几者的组合，例如移动终端内、接入点、或蜂窝网络。优选地，本发明实现为硬件和软件的组合。此外，软件优选地实现为切实体现在程序存储设备上的应用程序。应用程序可以上载到包括任意适当结构的机器，或者由包括任意适当结构的机器来执行。优选地，在计算机平台上实现该机器，计算机平台具有诸如一个或多个中央处理单元(CPU)、随机存取存储器(RAM)、以及输入/输出(I/O)接口之类的硬件。该计算机平台还包括操作系统和微指令代码。这里所描述的各种处理和功能可以是通过操作系统来执行的微指令代码的一部分或者应用程序的一部分(或这两者的组合)。此外，诸如附加数据存储设备和打印设备之类的各种其他外围设备可以连接到计算机平台。

还可以理解的是，因为附图中所描述的组成系统的组件和方法步骤中的一些优选地实现为软件，所以计算机组件(或处理步骤)之间的实际连接可以根据对本发明进行编程的方式而有所区别。在这里给出教导的情况下，相关领域的普通技术人员将能够设想这些以及相似的实现或本发明的构造。

Claims (14)

1.一种在无线网格网中通过节点来选择源节点和目的节点之间的路由的方法，所述方法包括：使用MAC地址建立所述在源节点和目的节点之间的路由；所选的在源节点和目的节点之间的路由基于混合网格按需路由选择和先应式网格路由选择，其中所述混合网格按需路由选择还包括：

通过所述节点接收路由请求消息；

通过检查发起者地址和消息ID，以察看以前是否曾见过该路由请求消息，由接收路由请求消息的所述节点执行第一确定，确定所述路由请求消息是否是来自所述源节点的第一路由请求消息，

如果所述第一确定的结果为“是”，则

通过增加从其接收路由请求消息的节点和接收路由请求消息的所述节点本身之间的链路成本来更新所述路由请求消息中的度量，并在接收路由请求消息的所述节点的路由选择表中建立到所述源节点的反向路由；并且通过接收路由请求消息的所述节点执行第二确定，确定：a)接收路由请求消息的所述节点是否是所述目的节点，以及b)在所述路由选择表中，接收路由请求消息的所述节点是否具有到所述目的节点的有效未到期路由，且该目的节点的序列号至少如所述路由请求消息中所表示的一样大；

如果所述第二确定的结果为a)中的“是”或b)中的“是”，则向所述源节点单播路由应答消息；否则，以所更新的度量传播所述路由请求消息；

如果所述第一确定的结果为“否”，则通过增加从其接收路由请求消息的节点和接收路由请求消息的所述节点本身之间的链路成本来更新所述路由请求消息中到发起者的度量，并将所述路由选择表中的所述度量与所更新的度量进行比较；

如果所更新的度量小于在所述路由选择表中的度量，则更新所述反向路由；否则，则丢弃该所述路由请求消息。

2.如权利要求1所述的方法，还包括：支持非转发网格节点，其中所述非转发网格节点是源节点和目的节点之一。

3.如权利要求2所述的方法，其中，当所述非转发网格节点需要传送数据分组时，所述非转发网格节点传送路由请求消息。

4.如权利要求2所述的方法，其中，仅在所述非转发网格节点是所述目的节点时，所述非转发网格节点才对路由请求消息做出响应。

5.如权利要求2所述的方法，其中，如果所述非转发网格节点不是所述目的节点，则所述非转发网格节点不对路由请求消息做出响应。

6.如权利要求2所述的方法，其中，所述非转发网格节点接收路由宣告消息，以学习至所述路由宣告消息的发起者的所述路由。

7.如权利要求2所述的方法，其中，所述非转发网格节点不向相邻节点转发所接收的路由选择控制消息。

8.一种用于在无线网格网中通过节点来选择源节点和目的节点之间路由的设备，所述设备包括：用于使用MAC地址建立所述在源节点和目的节点之间的路由的装置；所选的在源节点和目的节点之间的路由基于混合网格按需路由选择和先应式网格路由选择，其中用于所述混合网格按需路由选择的装置还包括：

装置，用于通过所述节点接收路由请求消息；

装置，用于通过检查发起者地址和消息ID，以察看以前是否曾见过该路由请求消息，由接收路由请求消息的所述节点执行第一确定，确定所述路由请求消息是否是来自所述源节点的第一路由请求消息，

装置，用于如果所述第一确定的结果为“是”，则通过增加从其接收路由请求消息的节点和接收路由请求消息的所述节点本身之间的链路成本来更新所述路由请求消息中的度量，并在接收路由请求消息的所述节点的路由选择表中建立到所述源节点的反向路由；

装置，用于通过接收路由请求消息的所述节点执行第二确定，确定：a)接收路由请求消息的所述节点是否是所述目的节点，以及b)在所述路由选择表中，接收路由请求消息的所述节点是否具有到所述目的节点的有效未到期路由，且该目的节点的序列号至少如所述路由请求消息中所表示的一样大；

装置，用于如果所述第二确定的结果为a)中的“是”或b)中的“是”，则向所述源节点单播路由应答消息；

装置，用于如果所述第二确定的结果为a)和b)二者中的“否”，则以所更新的度量传播所述路由请求消息；

装置，用于如果所述第一确定的结果为“否”，则通过增加从其接收路由请求消息的节点和接收路由请求消息的所述节点本身之间的链路成本来更新所述路由请求消息中到发起者的度量，并将所述路由选择表中的所述度量与所更新的度量进行比较；

装置，用于如果所更新的度量小于在所述路由选择表中的度量，则更新所述反向路由；否则，则丢弃该所述路由请求消息。

9.如权利要求8所述的设备，还包括：装置，用于支持非转发网格节点，其中所述非转发网格节点是源节点和目的节点之一。

10.如权利要求9所述的设备，其中，当所述非转发网格节点需要传送数据分组时，所述非转发网格节点传送路由请求消息。

11.如权利要求9所述的设备，其中，仅在所述非转发网格节点是所述目的节点时，所述非转发网格节点才对路由请求消息做出响应。

12.如权利要求9所述的设备，其中，如果所述非转发网格节点不是所述目的节点，则所述非转发网格节点不对路由请求消息做出响应。

13.如权利要求9所述的设备，其中，所述非转发网格节点接收路由宣告消息，以学习至所述路由宣告消息的发起者的所述路由。

14.如权利要求9所述的设备，其中，所述非转发网格节点不向相邻节点转发所接收的路由选择控制消息。

Images