在等级网格网络中辅助故障恢复的故障和获得超时配置

摘要

用于在等级无线网格网络中提供高效的故障发现机制的方法、装置和系统。在一种实现方式中，本发明缓解了等级无线网格网络上的父和子节点之间的同步丢失的影响。在一种实现方式中，本发明采用配置方案从而父节点故障超时大于获得父节点的时间，从而缓解了在等级网格网络中的下游节点上的同步丢失的影响。

权利要求

1.一种用于缓解等级无线网格网络中的父和子节点之间的同步丢失的方法，该方法包括：在维护状态中监视来自父路由选择节点的安排消息，以便维护与所述父路由选择节点的同步；

在没能在故障时间间隔中从所述父路由选择节点接收到安排消息时，进入长度为获得时间间隔的同步状态，以尝试重新获得所述父路由选择节点；

如果所述父路由选择节点被重新获得，则进入所述维护状态，其中所述获得时间间隔小于所述故障时间间隔。

2.如权利要求1所述的方法，还包括

如果未重新获得所述父路由选择节点，则选择相邻路由选择节点作为试探性父路由选择节点；以及利用所述试探性父路由选择节点进入所述长度为获得时间间隔的同步状态。

3.如权利要求1所述的方法，其中所述同步状态包括发送至少一个请求到所述父路由选择节点；以及监视来自所述父路由选择节点的对所述请求的响应。

4.如权利要求1所述的方法，其中所述获得时间间隔小于等于所述故障时间间隔的一半。

5.如权利要求1所述的方法，其中所述维护状态还包括发送时隙安排消息到至少一个子路由选择节点。

6.如权利要求1所述的方法，其中所述维护状态还包括基于从所述父路由选择节点接收的所述安排消息中包含的信息计算数据时隙安排；以及根据所述数据时隙安排发送数据到所述父路由选择节点和接收来自所述父路由选择节点的数据。

7.如权利要求5所述的方法，其中所述维护状态还包括基于从所述父路由选择节点接收的所述安排消息中包含的信息计算数据时隙安排；以及根据所述数据时隙安排发送数据到所述父路由选择节点和接收来自所述父路由选择节点的数据。

8.如权利要求7所述的方法，其中所述维护状态还包括根据所述数据时隙安排发送数据到至少一个子节点和接收来自至少一个子节点的数据。

9.如权利要求1所述的方法，还包括发现相邻路由选择节点。

10.一种用于等级无线网格网络的无线路由选择节点，包括用于与父路由选择节点无线通信的装置；

用于执行维护状态的装置，所述执行维护状态包括监视来自父路由选择节点的安排消息，以便维护与所述父路由选择节点的同步；

同步装置，用于与选定的路由选择节点同步，从而尝试在获得时间间隔期间获得作为父路由选择节点的路由选择节点；

用于当在故障时间间隔之后检测到与父路由选择节点的同步丢失时触发所述同步装置的装置，其中所述获得时间间隔小于所述故障时间间隔。

11.如权利要求10所述的无线路由选择节点，还包括用于发现相邻无线路由选择节点的装置。

12.如权利要求10所述的无线路由选择节点，其中所述获得时间间隔小于等于所述故障时间间隔的一半。

13.如权利要求10所述的无线路由选择节点，其中所述维护状态还包括发送时隙安排消息到至少一个子路由选择节点。

14.如权利要求10所述的无线路由选择节点，其中所述维护状态还包括基于从所述父路由选择节点接收的所述时隙安排消息中包含的信息计算数据时隙安排；以及根据所述数据时隙安排发送数据到所述父路由选择节点和接收来自所述父路由选择节点的数据。

15.如权利要求13所述的无线路由选择节点，其中所述维护状态还包括基于从所述父路由选择节点接收的所述时隙安排消息中包含的信息计算数据时隙安排；以及根据所述数据时隙安排发送数据到所述父路由选择节点和接收来自所述父路由选择节点的数据。

16.如权利要求15所述的无线路由选择节点，其中所述维护状态还包括根据所述数据时隙安排发送数据到至少一个子节点和接收来自至少一个子节点的数据。

说明书

在等级网格网络中辅助故障恢复的故障和获得超时配置

技术领域

[0001] 本发明涉及无线网格(mesh)通信网络，更具体而言涉及辅助从等级(hierarchical)无线网格网络的路由选择节点故障中恢复的故障-获得超时机制
(failure-acquire timeout mechanism)。

背景技术

[0002] 无线网格通信网络一般由多个以对等方式操作以建立到彼此的通信路径以便向无线客户端或移动台提供网络接入的无线路由选择节点组成。一些无线网格网络本质上是等级的，其中路由选择节点将无线流量桥接到等级顶部的有线网络。无线网格路由选择节点可以是一个、两个或多个包括全向和/或定向天线的无线电系统，以及在同一网格等级但在多个信道上提供回程流量的系统。在单无线电系统中，无线电单元被用来充当到其客户端的接入点，并且充当到父路由选择节点的的回程单元。在双无线电系统中，一个无线电单元一般提供对无线客户端和子路由选择节点的接入点服务，而另一无线电单元被用作为到父路由选择节点的回程单元。多无线电设计一般将一个无线电单元专用于接入，一个或多个无线电单元提供回程，并且还可以将一个无线电单元专用于监视多个射频上的RF环境和其他条件。在某些无线网格网络中，回程无线电以自组织台模式操作，对父路由选择节点表现为对等节点。向客户端提供接入的网络中的那些无线电单元以接入点模式操作，向移动台提供无线连接。

[0003] 在利用多个定向天线或在多个信道上操作的无线网格网络中，回程上的路由选择节点必须协调无线电单元之间的通信。一种技术是使用多个回程无线电单元，每个定向天线和无线电单元工作于其上的信道对使用一个无线电单元。另一技术称为时隙法(slotting)，其中父和子在彼此商定的时刻协调相互发送。时隙是在其间安排父和子节点之间的发送的最小时间单元。

[0004] 在自动形成网络和父子关系的无线网格网络中，一种实现方式可以使用发现(discovery)来确定潜在的父节点集合。发现过程涉及扫描信道和天线对以找到合适的父节点。一种技术是通过在广播信道上发送联网分组(该分组随后被合适的父节点响应)来进行探测。在典型的有线网络中或在其中每个天线/信道对专用一个无线电单元的无线网络中，获得新父节点的时间一般很短。获得分组被发送，并且接收器在发送获得分组的介质上总是可用的，不管所述介质是局域网、无线信道，还是定向天线对。但是，在单个无线电单元支持多个定向天线和信道的情形下，以及对于节点不具有关于潜在父节点的信道天线对的安排的先验知识的情形，获得时间可能长得多。

[0005] 等级无线网格网络固有地创建了某种依赖关系。例如，给定路由选择节点及其子路由选择节点依赖于父路由选择节点来到达上游目的地。因此，与父节点相关联的故障事件一般将导致其子节点寻求重新获得其他父节点。在大多数系统中，子节点一般将停止服务于它们自己的子节点(父节点的孙子节点)，以便重新获得已有的父节点，或者获得新的父节点。在此期间，孙子节点也可以把这种缺乏服务视为故障事件，并因此寻求获得新父节点。假设故障发生在父和子节点之间，则与使故障事件沿等级传播相关联的开销和延迟是不希望的，并且这种情况可能延长无线网格从仅一个节点处的故障事件恢复所需的时间。

[0006] 鉴于上述原因，现有技术需要允许无线网格网络中的高效故障恢复机制的方法、装置和系统。本发明的实施例基本上满足了这一需要。

发明内容

[0007] 本发明的一个技术方案提供了一种用于缓解等级无线网格网络中的父和子节点之间的同步丢失的方法，该方法包括：在维护状态中监视来自父路由选择节点的安排消息，以便维护与所述父路由选择节点的同步；在没能在故障时间间隔中从所述父路由选择节点接收到安排消息时，进入长度为获得时间间隔的同步状态，以尝试重新获得所述父路由选择节点；如果所述父路由选择节点被重新获得，则进入所述维护状态，其中所述获得时间间隔小于所述故障时间间隔。

[0008] 本发明的另一技术方案提供了一种用于等级无线网格网络的无线路由选择节点，其包括：用于与父路由选择节点无线通信的装置；用于执行维护状态的装置，所述执行维护状态包括监视来自父路由选择节点的安排消息，以便维护与所述父路由选择节点的同步；同步装置，用于与选定的路由选择节点同步，从而尝试在获得时间间隔期间获得作为父路由选择节点的路由选择节点；用于当在故障时间间隔之后检测到与父路由选择节点的同步丢失时触发所述同步装置的装置，其中所述获得时间间隔小于所述故障时间间隔。

附图说明

[0009] 图1是示出了根据本发明实现方式的等级无线网格网络的功能框图。

[0010] 图2是示出了根据本发明一种实现方式的无线路由选择节点的逻辑配置的示意图。

[0011] 图3A是示出了根据无线网格网络的一种实现方式的由路由选择节点实现的状态和事件的状态图。

[0012] 图3B是示出了与图3A的状态图相关联的事件、过程描述和数据结构的图表。

[0013] 图4是示出了根据本发明一种实现方式的邻居状态机的操作的流程图。

[0014] 图5A是根据本发明一种实现方式的对邻居请求分组的处理的流程图。

[0015] 图5B是示出了根据本发明一种实现方式的用于添加和/或维护子路由选择节点的过程的流程图。

[0016] 图6A和6B一起提供了示出了根据本发明一种实现方式的处理邻居响应分组的流程图。

[0017] 图6C示出了根据本发明一种实现方式用于评估相邻条目的过程流。

[0018] 图7是示出了在SYNC状态期间的路由选择节点操作的流程图。

[0019] 图8是示出了根据无线网格网络的一种实现方式的周期间隔中的数据时隙和竞争时隙的示意图。

[0020] 图9是示出了根据本发明另一实现方式的等级无线网格网络的框图。

[0021] 图10A示出了图9所示的无线网格网络中的父路由选择节点的数据和竞争时隙安排。

[0022] 图10B示出了图9所示的无线网格网络中的子节点的数据和竞争时隙安排。

[0023] 图11A是根据本发明一种实现方式的用于同步经过无线网格网络中的路由选择节点的传输的方法的流程图设置。

[0024] 图11B是根据本发明一种实现方式的用于同步无线网格网络中的父和子节点之间的数据时隙阶段的传输的方法和流程图设置。

[0025] 图12是示出了根据本发明一种实现方式的数据时隙的元素的示意图。

[0026] 图13是示出了对数据时隙中的两个路由选择节点之间的数据传输的协调的示意图。

[0027] 图14示出了根据本发明一种实现方式的在无线网格网络的回程上传输的无线帧的帧布局。

[0028] 图15提供了根据本发明一种实现方式的消息路由选择头部的布局。

[0029] 图16是示出了根据本发明一种实现方式的节点故障和获得机制的操作的示意图。

具体实施方式

[0030] 为了说明的目的将本发明的实施例描述为在图1所示的等级无线网格网络中操作。但是，本发明可以在多种等级网格网络配置中操作。图1示出了根据本发明一种实现方式的无线网格网络。在一种实现方式中，无线网格网络包括无线网格控制系统20和多个路由选择节点。在一种实现方式中，在路由选择节点的网格网络上覆盖等级体系结构，以创建朝向叶子路由选择节点34的下游方向，和朝向根路由选择节点30的上游方向。例如，在图1所示的等级网格网络中，第一跳路由选择节点130是中间路由选择节点3 32的父节点。
此外，中间路由选择节点3 32是叶子路由选择节点5 34和中间路由选择节点6 32的父节点。在一种实现方式中，在无线客户端40之间或者在无线客户端40和网络50之间路由分组时使用该等级关系。如下所详述，该等级体系结构也用于同步父和子路由选择节点之间的传输。在图1所示的无线网格网络中，路由选择节点被布置在两个等级树结构中——一个的根节点是路由选择节点1，另一个根节点是路由选择节点2。当然，可以使用多种等级配置，包括更少或更多的等级树结构。此外，这种等级配置可以是动态的，因为路由选择节点之间的父和子关系可以依赖于诸如拥塞、节点故障等因素而改变。如下所详述，本发明的实现方式允许等级路由选择覆盖的自动配置。此外，本发明的一些实现方式适用于改变等级网格网络的状况，例如RF干扰、节点故障等。

[0031] 在一种实现方式中，网格网络一般包括在第一频带中操作的一个无线电单元，以及用于与其他路由选择节点通信从而实现无线骨干的相关联的无线通信功能，如下所详述。在一种实现方式中，全部路由选择节点或其一个子集还包括在第二非干扰频带中操作的额外无线电单元，和用于建立和维护与诸如无线客户端40等移动台的无线连接的其他无线通信功能。例如，在802.11无线网络中，无线路由选择节点的骨干无线电单元可以在5GHz频带上使用802.11a协议在彼此之间传输无线分组，而每个无线节点上的第二无线电单元可以在2.4GHz(802.11b/g)频带上与无线客户端交互。当然，该关系可以被颠倒，其中回程流量使用802.11b/g频带，客户端流量使用802.11频带。

[0032] 图1还示出了根据本发明的一种实现方式的路由选择节点之间的给定频带中的信道分配。在一种实现方式中，用于给定树和给定跳的路由选择节点被设置到相同信道。此外，在一种实现方式中，对于给定路由选择节点，用于上游数据传输的操作信道不同于用于下游数据传输的操作信道。例如，路由选择节点1和路由选择节点3之间的无线传输发生在信道1上，而路由选择节点3在信道2上与路由选择节点5和路由选择节点6通信。在一种实现方式中，分配给给定路由选择节点的上游和下游信道是非重叠信道，而在其他实现方式中它们是重叠信道。在一种实现方式中，路由选择节点之间的信道分配被静态配置。在其他实现方式中，操作信道可被动态分配。但是，这种信道分配方案不是本发明必需的。
在其他实现方式中，网格网络中的所有路由选择节点都在回程频带中的同一信道上操作。

[0033] 如下所详述，在一种实现方式中，网格网络中的每个路由选择节点都可操作来根据网格路由选择等级发送和接收来自其他路由选择节点的分组。在一种实现方式中，每个网格路由选择节点还可操作来建立和维护到一个或多个无线客户端设备40的无线连接。在一种实现方式中，每个网络控制系统20可以操作来监视每个无线客户端关联到哪个路由选择节点和将目的地为该无线客户端的分组路由到该客户端所关联的无线路由选择节点。

[0034] A.网格路由选择节点配置

[0035] 为了说明的目的，下面描述了根据本发明一种实现方式的网格路由选择节点的配置。也可以使用其他路由选择节点配置。图2是示出了根据本发明一种实现方式的逻辑和/或操作组件的示意图。图2所示的路由选择节点包括在第一频带中操作的无线骨干接口单元60和在第二频带中操作的WLAN接口单元80。具体而言，如图2所示，网格路由选择节点一般包括路由选择节点控制处理器70、无线骨干接口单元60和WLAN接口单元80。在一种实现方式中，路由选择节点控制处理器70、无线骨干接口单元60和WLAN接口单元80可操作地经由系统总线彼此连接。无线骨干接口单元60可操作来在路由选择节点控制处理器70控制下将无线帧传输到上游(父)和下游(子)路由选择节点，如下所详述。在一种实现方式中，WLAN接口单元80可操作来在路由选择节点控制处理器70的控制下传输去往和来自无线客户端40的无线分组。

[0036] 在一种实现方式中，无线骨干接口单元60包括第一和第二天线85和86、开关62、骨干无线电模块64，以及骨干MAC控制单元66。在使用单个全向天线的其他实现方式中，不需要开关62。骨干无线电模块64包括基于频率的调制/解调功能，用于在接收方向上解调射频信号和向骨干MAC控制单元66提供数字数据流，并且在发送方向上接收数字数据流和提供与数字数据流相对应的调频信号。在一个实施例中，无线电模块64是正交频分复用(OFDM)调制/解调单元。当然，可以使用其他调制和解调技术，例如跳频扩频(FHSS)或直接序列扩频(DSSS)。骨干MAC控制单元66实现数据链路层功能，例如在数字数据流中检测个体帧、对帧进行差错校验，等等。在一个实施例中，骨干MAC控制单元66实现802.11无线网络协议(这里使用的802.11一般指用于无线LAN的IEEE802.11标准及其所有修订)。在一个实施例中，这里描述的功能可以在无线网络接口芯片集(例如802.11网络接口芯片集)中实现。当然，本发明可以与任何合适的基于射频的无线网络协议一起使用。开关62在路由选择节点控制处理器70的控制下，在第一天线85和第二天线86之间切换。

[0037] WLAN接口单元80包括WLAN MAC控制单元82、WLAN无线电模块84和至少一个天线87。类似于骨干接口单元60，WLAN无线电模块84包括基于频率的调制/解调功能，用于在接收方向上解调射频信号和向WLAN MAC控制单元82提供数字数据流，并且在发送方向上接收数字数据流和提供对应于数字数据流的调频信号。在一个实施例中，WLAN无线电模块84是正交频分复用调制解调模块。在一个实施例中，无线电模块84以遵循IEEE 802.11a或802.11g协议并分别在5GHz或2.4GHz频带中操作的方式实现OFDM功能。WLAN无线电模块84还可以以遵循使用DSSS数据传输方案的802.11b协议的方式操作。但是，如上所述，在一种实现方式中，无线电模块84在其中操作的频带被配置为相对于骨干无线电模块64无干扰。但是，如上所述，在一种实现方式中，无线电模块84在其中操作的频带被配置为相对于骨干无线电模块64无干扰。WLANMAC控制单元82实现数据链路层功能，例如检测数字数据流中的个体帧、对帧进行差错校验等。在一个实施例中，WLAN MAC控制单元82实现
802.11无线网络协议。本发明中可以使用其他合适的协议。在一个实施例中，这里描述的功能可以实现在无线网络接口芯片集(例如802.11网络接口芯片集)中。此外，在一种实现方式中，WLAN接口单元80包括快路径和慢路径发送队列，以便允许高优先级流量(例如管理帧)比常规网络流量更好或更优先地接入通信介质。无线骨干接口单元60也可以具有类似的优先级功能。

[0038] 如上所述，在一种实现方式中，无线骨干接口单元60和WLAN接口单元80在不同频带中操作。例如，在一个实施例中，骨干无线电模块64以遵循IEEE 802.11a协议的方式实现OFDM编码方案，并从而在5GHz频带中操作。WLAN无线电模块84以遵循802.11b和/或802.11g协议的方式在2.4GHz频带中操作。对无线骨干流量和客户端流量使用不同频带确保了无线客户端流量基本不影响或干扰路由选择节点实现的无线骨干的操作。此外，对无线骨干和无线客户端流量使用不同频带辅助了使用信道选择算法来解决带内RF干扰，因为更多信道可供每种流量类型使用。当然，也可以使用其他方案，因为对无线骨干流量和客户端与路由选择节点之间的无线流量的频带的选择是工程选择方面的问题。在其他实现方式中，同一频带中的不同非重叠信道可被用于无线骨干流量和客户端流量。

[0039] 图2还示出了路由选择节点控制处理器70的逻辑配置。在一种实现方式中，路由选择节点控制处理器70一般指控制路由选择节点的操作的硬件模块(例如处理器、存储器)、软件模块(例如驱动器等)，和数据结构(例如帧缓冲器、队列等)。在一种实现方式中，路由选择节点控制处理器70一般包括处理器(例如中央处理单元(CPU)等)、存储器(例如RAM、EPROMS等)，和互连存储器、处理器和网络接口的系统总线。路由选择节点控制处理器70还可以包括用于实现这里描述的功能的操作系统和一个或多个软件模块和/或驱动器。如上所述，路由选择节点控制处理器70控制无线骨干接口单元60和WLAN接口单元80的操作，无线骨干接口单元60和WLAN接口单元80都可以驻留在可操作地连接到系统总线的网卡上。在一种实现方式中，路由选择节点控制处理器70可操作来控制无线骨干接口单元60的操作，以便将上行链路和下行链路传输与网格网络中的其他路由选择节点同步(见下面B部分)。如上所述，无线骨干接口单元60在接收方向上向路由选择节点控制处理器70提供在第一天线85或第二天线86处接收的无线帧。在一种实现方式中，标志检测器72可操作来检查从其他路由选择节点接收的无线帧，并且确定该无线帧应当沿无线骨干被转发还是应当经由WLAN接口单元80被转发到与当前路由选择节点相关联的无线客户端。响应于标志检测器72发送的控制信号，逻辑开关74将无线分组沿WLAN路径发送到WLAN接口单元80，或者沿无线骨干发送到上游队列77或下游队列78。如图2所示，路由选择节点控制处理器70还包括逻辑开关76，用于依赖于当前操作阶段或模式在上游发送和接收队列77与下游发送和接收队列78之间切换。例如，在父时隙期间从父路由选择节点接收的无线帧被在用于到子路由选择节点的发送的下游发送/接收队列78中缓冲，以便在合适的子时隙中被发送。相反，在下游阶段期间从子路由选择节点接收的无线帧被在父时隙队列77中缓冲，以便在上游阶段期间被发送到父路由选择节点。在一种实现方式中，路由选择节点控制处理器70为与当前节点关联的每个父和子路由选择节点维护独立的发送和接收队列。在发送方向上，逻辑开关76根据发送阶段和时隙安排在下游队列和上游队列之间切换。例如，在与父路由选择节点的上游发送数据时隙期间，逻辑开关76允许存储在上游发送/接收队列77上的无线帧经由天线85或86被发送到父路由选择节点。在子数据时隙期间，逻辑开关76允许存储在下游发送/接收队列78之一中的无线帧经由天线85或86被发送到相应的子路由选择节点。在一种实现方式中，上游队列77和下游队列78都可以包括独立的排队结构以实现多种目的。例如，路由选择节点控制处理器70可以被配置为包括用于上游队列77和下游队列78中每一个的快路径和慢路径。

[0040] 如上所述，路由选择节点控制处理器70可操作来基于当前发送阶段(即父或子数据时隙)在第一天线85和第二天线86之间切换。在一种实现方式中，第一天线85可用于与父路由选择节点的数据传输，而第二天线86可用于与一个或多个子路由选择节点的传输。在一个实施例中，第一天线85和第二天线86是峰值增益依赖于父和子路由选择节点的位置而被定向的定向天线。例如，在一种实现方式中，第一天线85一般被定向在父路由选择节点的方向上。第二天线86定向在一个或多个子路由选择节点的总方向上。在一种实现方式中，下游定向天线的峰值增益和束宽对子路由选择节点之间的隔离施加了有效的限制。但是，在其他实现方式中，子和父路由选择节点不与特定天线相关联。如下所详述，用于与给定路由选择节点通信的天线可以在邻居发现和维护过程中被确定。天线85、86可以是任意适当的定向天线，例如平板式天线、八木天线、抛物面和碟形天线。在一个实施例中，天线的峰值增益以最大化所有方向上的覆盖的方式彼此偏离。

[0041] 在另一实现方式中，可以使用一种全向天线代替第一天线85和第二天线86。在一种这样的实现方式中，一个操作信道可被选择用于下游数据传输，而另一非重叠信道可被选择用于上游数据传输。路由选择节点控制处理器70通过根据这里描述的同步机制控制骨干无线电模块64在下游和上游信道之间切换而在上游和下游数据时隙阶段之间切换。当然，多个全向天线也可以结合空间天线模式分集方案一起使用，以减轻室内和室外系统中的多径影响。

[0042] 在一个实施例中，路由选择节点包括允许检测从相邻路由选择节点接收的信号的信号强度和其他属性的功能。例如，IEEE 802.11标准定义了RF能量被无线网络适配器或接口卡上的电路(例如芯片集)测量的机制。802.11协议规定了可选参数：接收信号强度指示符(RSSI)。该参数是在用于接收当前分组或帧的天线处观察到的能量的PHY层度量。在帧起始定界符(SFD)的开始和PLCP头部差错校验(HEC)的末尾之间测量RSSI。该数字值一般是允许范围为0-255(1字节值)的整数。一般地，802.11芯片集销售商选择不实际测量256个不同信号级别。因此，每个销售商的遵循802.11的适配器具有特定的最大RSSI值(”RSSI_Max”)。因此，特定销售商的无线网络适配器报告的RF能量级别的范围将在0和RSSI_Max之间。将给定销售商的芯片集报告的给定RSSI值解析为实际功率值(dBm)可以通过参考转换表来完成。此外，一些无线联网芯片集还在作为信噪比的SNR中报告接收信号强度而不是在作为信号功率的绝对估计值的RSSI中报告接收信号强度，或者除了在作为信号功率的绝对估计值的RSSI中报告接收信号强度之外还在作为信噪比的SNR中报告接收信号强度。很多芯片集包括允许确定与在无线网络接口上接收的分组相关联的信噪比(SNR)的功能和相应的API。如下所详述，检测到的信号属性信息可用于自动配置网格网络。

[0043] 根路由选择节点30和叶子路由选择节点34可以包括上述功能的子集，因为这些路由选择节点不具有父或子路由选择节点。例如，根路由选择节点30和叶子路由选择节点34都可被配置为包括单个定向或全向天线。例如开关62等其他功能可被省略。但是，在一种实现方式中，每个根或叶子路由选择节点可以包括上述所有主要物理功能，并且可被配置为(适当地)以根或叶子模式操作，其中下游/上游同步功能被禁用。在此情形下，叶子路由选择节点34例如在上游模式下操作，等待它们各自的数据时隙。一种配置机制辅助网格网络的重配置和扩展。例如，可以通过简单地在叶子路由选择节点的下游方向上添加额外的路由选择节点并重配置叶子路由选择节点来扩展无线网格网络。

[0044] 也可以使用其他配置。例如，无线路由选择节点可以包括多于两个定向天线。例如，每个骨干无线电接口可以可操作地连接到四个定向天线，这四个定向天线的峰值增益分别相对于彼此以90度定向。此外，如下所详述，每个路由选择节点还包括可操作来发现和维护与相邻路由选择节点有关的数据的邻居状态机。

[0045] B.邻居消息处理和路由选择配置

[0046] 下文描述了由无线网格中的节点实现的根据本发明一个实施例的路由选择配置机制。在一种实现方式中。无线网格网络中的每个节点实现用于发送和接收来自无线网格中的其他路由选择节点的邻居消息的邻居状态机。在一种实现方式中，邻居消息被每个路由选择节点用来自动配置和维护网格网络上的等级路由选择配置。对邻居消息的处理允许自动发现网格网络中的路由选择节点、辅助确定用于与相邻路由选择节点通信的优选天线，还允许故障检测以及其他无线网络条件和事件。在一种实现方式中，在每个节点上实现的邻居和路由管理功能负责以下一个或多个任务：1)发现相邻路由选择节点；2)维护作为试探性父路由选择节点的有吸引力的邻居路由选择节点的列表；3)选择邻居路由选择节点充当路由选择系统等级中的父路由选择节点；4)向相邻路由选择节点通报路由度量；5)维护不想要的邻居路由选择节点的列表。

[0047] 在一种实现方式中，邻居消息包含路由选择节点用来选择相邻路由选择节点和父路由选择节点的逻辑路径信息(例如到根的跳数、距离向量等)和物理路径信息(例如路由选择节点之间的接收分组的信噪比)。例如，在一种实现方式中，邻居请求分组可以包括以下一个或多个属性：1)类型标识符(请求或响应)；2)其父路由选择节点或所请求的父的MAC地址；3)与用于发送该请求的天线相对应的天线标识符(antUp)；4)与在其上发送请求的信道相对应的信道标识符；5)网络名称(可用于将路由选择节点在逻辑上分离为独立网格网络的可选参数)；和6)路由选择体系结构中的任意后代路由选择节点(例如子节点、孙子节点，等等)的MAC地址。此外，邻居响应分组可以包括以下一个或多个属性：1)类型标识符(请求或响应)；2)检测到的邻居请求分组的SNR(snrUp)；3)检测到的邻居请求分组的接收差错率；4)网格路由选择或路径信息；5)与在其上接收到邻居请求的天线相对应的天线标识符(antDown)；6)在其上接收到邻居请求的信道(chanUp)；7)要去往的潜在子的MAC地址；8)网络名称；9)在邻居请求中通报的发送天线标识符(antUp)；和10)在数据时隙安排模块中使用的数据时隙值(见下)。在一种实现方式中，数据时隙值可以包括1)指示在数据时隙之前的被子路由选择节点用来开始改变其配置以便在该时隙中操作(即改变信道、天线等)的时间量的“时隙前期时间”；2)指示在时隙末尾处未被使用的时隙空间的量的“时隙死区时间”；和3)时隙持续时间。此外，网格路由选择信息可以包括：1)到一个或更多个根AP的路由数量；和2)对于每个路由：a)到根路由选择节点的跳数，b)路由选择节点的未调整宽松度(ease)(见下)，和c)代表路由中的跳的MAC地址的距离向量。

[0048] 图3A和3B示出了根据本发明一种实现方式的与邻居状态机相关联的动作、协议事件和模块接口。如图3A所示，在给定路由选择节点上实现的邻居状态机可以处于以下五个状态之一：1)START，2)SEEK，3)SYNC，4)AUTH，和5)MAINT。START状态发生在路由选择节点被加电或被重启时。如图3A所示，在START状态下，adjNull功能重置各个定时器并进入SEEK状态。但是，如果路由选择节点是根路由选择节点(例如图1中的节点30)，则adjNull功能将邻居状态机设置为MAINT状态。

[0049] 在SEEK状态下，路由选择节点尝试恢复其邻居路由选择节点。在一种实现方式中，切换经过所有可用天线的路由选择节点扫描所有可用操作信道，广播邻居请求分组并侦听邻居请求分组。路由选择节点还填充包括表征它在SEEK状态期间发现的邻居路由选择节点的属性数据的相邻性数据结构。存储在相邻性数据结构中的所发现的数据可包括路由选择节点的MAC地址、结合从路由选择节点接收的分组检测到的信噪比，等等。如图3A和3B所示，在SEEK状态下，路由选择节点在一个频率信道中操作，直到adjTimerl2超时，然后切换到下一操作信道并广播额外的邻居请求分组以发现其他潜在邻居分组。在SEEK状态末尾(例如当adjTimerl1超时时)，路由选择节点评估它发现的邻居路由选择节点，以识别和哪个潜在父路由选择节点同步。如果它没识别出潜在父，则路由选择节点重新进入START状态。

[0050] SYNC状态用于与在SEEK状态期间选择的父路由选择节点同步。在一种实现方式中，路由选择节点发送请求目的地路由选择节点把它作为路由选择配置等级中的子路由选择节点的定向邻居请求分组。在一种实现方式中，路由选择节点连续发送这些定向邻居请求分组，直到同步定时器超时。在SEEK和SYNC状态下，邻居请求分组都被重复发送。在一种实现方式中，这是由于以下事实造成的：目标路由选择节点可以是服务子路由选择节点或者它们自己的父路由选择节点，因此可以在不同的操作信道上操作或者使用不定向到发送路由选择节点的天线。因此，发送路由选择节点基于以下假设发送多个邻居请求分组：邻居路由选择节点将最终检测到所有分组，并把(一个或多个)分组向上传递通过协议栈以供更高层处理。在一种实现方式中，如果路由选择节点没能与第一选定路由选择节点同步，则它把路由选择节点添加到黑名单(在一种实现方式中，通过设置相邻性数据结构中的标志)、从TP变量删除当前潜在父，并重新评估它发现的邻居以便选择另一试探性父(TP)。如图3A所示，如果路由选择节点没能识别出另一试探性父，则它重新进入START状态。在一种实现方式中，成功的同步使得路由选择节点进入AUTH状态。在一种实现方式中。将路由选择节点从SYNC状态拉出到AUTH状态中的事件是接收到定向时隙通知消息(见下)，该消息通知路由选择节点父路由选择节点试图与当前路由选择节点通信的时隙。但是，也可以使用其他发送安排算法，因此，其他消息可以把路由选择节点拉入AUTH状态。

[0051] 在一种实现方式中，AUTH状态是可选的。AUTH状态用于从子路由选择节点的角度认证父路由选择节点的安全证明(例如数字签名、证书等)，以及从子路由选择节点的角度认证子路由选择节点的安全证明。如图3A所示，如果认证成功，则邻居状态机将试探性父设置成实际的父路由节点并进入MAINT状态。如果认证失败，则路由选择节点选择另一试探性父(如果可能的话)并尝试与选定的父同步。

[0052] 路由选择节点可以以各种方式从所发现的邻居中选择潜在的父。在一种实现方式中，依据策略选择试探性父路由选择节点。例如，可以基于以下因素之一或其组合来选择试探性父：1)到根路由选择节点的跳数，2)经过所有跳到根路由选择节点的信噪比(SNR)，等等。SNR提供了对经过每一跳的可能数据率的指示，而跳数提供了对传播和排队延迟(以及信道带宽消耗)的指示。如下所详述，在一种实现方式中，每个路由选择节点可以实现平衡这些因素以便从所发现的邻居中过滤和/或选择出试探性父。但是，路由选择节点选择父的具体方式对于本发明而言不是关键的。

[0053] B.1.邻居维护状态

[0054] 下文描述了根据本发明一种实现方式的MAINT状态的协议和操作。在MAINT状态中，路由选择节点为了发现相邻路由选择节点而继续广播邻居消息，并更新它的相邻性数据结构中与新发现的和已知的路由选择节点二者有关的条目。此外，在一种实现方式中，路由选择节点还发送定向邻居请求分组到其当前父路由选择节点以及先前发现的路由选择节点的选定子集。在一种实现方式中，路由选择节点使用从这些发现和维护操作获得的信息来确定是否继续与其当前父路由选择节点的操作。在一种实现方式中，只要满足某个标准(例如信号质量、路由度量等)，路由选择节点就保持其当前父路由选择节点。

[0055] 图4、5A、5B、6A和6B示出了当路由选择节点处于MAINT状态下时如何处理邻居分组。如图4A所示，在接收到邻居分组时，分组被检查以了解是否遵循一组协议规则(502)。如果邻居分组偏离协议规则，则它被丢弃并且计数器被递增(508)。在这些初始处理步骤之后，路由选择节点对消息的处理依赖于邻居消息是邻居请求还是邻居响应消息(506)。下面的B.2.部分提供了根据本发明一种实现方式的对邻居请求和响应消息的格式的描述。此外，使用与回程无线网络接口相关联的信号属性检测功能，路由选择节点还记录与所接收的邻居消息相对应的信噪比。如下所述，这些SNR被用于计算用于自动配置网格路由选择等级的各种路径度量。

[0056] 图5A和5B一起示出了根据一种实现方式的用于处理邻居请求消息的方法。如图5A所示，路由选择节点在处理邻居请求期间执行一系列检查。在一种实现方式中，路由选择节点检查其本地变量adjNeighState的状态(520)。如果该值是MAINT以外的任意值，则该分组被丢弃。然后，路由选择节点将在其上接收到分组的信道与本地变量adjDownChan相比较，以确定分组是否是在被分配给其子路由选择节点的信道上接收到的(522)。如果它们不同，则分组被丢弃。如图5A所示，分组的接收到的SNR被与常量adjMinNeighSNR相比较(524)。如果接收到的SNR小于该阈值，则路由选择节点递增计数器adjPoorNeighSNR并丢弃分组。使用邻居请求分组中的源MAC地址作为关键字，路由选择节点随后在其相邻性数据库中查找相应的相邻性条目(如果有的话)。如果条目存在，并且邻居的adjBlacklist变量被设置(526)，则路由选择节点递增计数器adjBlacklistPackets并丢弃分组。

[0057] 然后，路由选择节点将邻居请求中包含的父MAC地址与其本地MAC地址相比较。如果它们相同，则路由选择节点执行用于添加或维护作为子路由选择节点的请求路由选择节点的过程。如图5B所示，路由选择节点查找邻居请求的源MAC地址，以确定其相邻性数据结构中是否存在条目(550)。如果不存在用于子邻居的相邻性条目，则路由选择节点尝试使用源MAC地址作为关键字创建一个条目以及维护路由选择节点所必需的资源。如果存储器分配失败(554)，则路由选择节点递增计数器(adjInsufficientMemory)并丢弃分组(556)。此外，在一些实现方式中，路由选择节点可以包括限制它在任意给定时刻维护的子路由选择节点的数量的可配置参数。如果该阈值被满足，则路由选择节点丢弃邻居请求消息。

[0058] 然后，路由选择节点检查相应的相邻性数据结构条目中的变量adjChild，以确定它是否已被设置(558)。如果它未被设置，则该条目的adjChild变量被设置并且adjNewChild事件被发送到发送安排模块，以便将新子节点结合到数据时隙发送安排(见下)中(560)。在一种实现方式中，路由选择节点还重置被设置为在adjChildHold秒后到期的定时器(562)。如果定时器到期，则路由选择节点清除或重置adjChild变量，并发送子删除事件到发送安排模块以便从安排清除子。但是，如图5B所示，只要从子接收到邻居分组，定时器就被重置(562)。最后，路由选择节点把包含在邻居请求分组中的MAC地址集合拷贝到MAC地址的本地转发表中(564)。也可以使用其他实现方式。例如，发送安排模块可以被配置为周期性地轮询相邻性数据结构，以便确定否已添加或删除了任意子节点，并相应地调整其安排操作。

[0059] 返回图5A，如果邻居请求中的父MAC地址与路由选择节点的本地MAC地址不同，则路由选择节点随后确定是否存在用于发送请求的路由选择节点的条目。如果存在任何条目，则路由选择节点确定该条目中的adjChild变量是否已被设置(534)。如果是，则路由选择节点从该条目清除adjChild变量，并发送子删除事件到发送安排模块(536)。如图5A所示，路由选择节点增加计数器adjRxNeighReq(538)，邻居响应分组被生成和发送到发送器(540)。

[0060] 如上所述，邻居响应分组包括允许接收路由选择节点计算与对父路由选择节点的选择有关的各种路由度量的信息。例如，邻居响应分组包括路由选择节点在接收邻居响应分组期间检测到的信号的SNR(snrUp)。图6A和6B示出了用于处理邻居响应分组的过程流。在一种实现方式中，图6A和6B示出了由上述状态图中的NEIGHADD特征执行的过程。在该过程中，路由选择节点响应于接收到邻居响应分组而添加或更新相邻性数据结构中的条目。如图6A所示，路由选择节点对邻居响应分组执行一系列检查。例如，路由选择节点首先检查变量adjNeighState状态的状态(570)。如果它的值是MAINT或SEEK以外的任意值，则分组被丢弃。接下来，路由节点检查其自身的角色(572)。例如，如果当前路由选择节点是根节点，则丢弃邻居响应分组。另外，将分组的目的地MAC地址与当前路由选择节点的本地MAC地址相比较(574)，如果它们不同则分组被丢弃。

[0061] 然后，路由选择节点将对应于在邻居响应分组中通报的每个路由的跳数与AP_MAXHOPS阈值相比较(575)。如果任意跳数大于或等于AP_MAXHOPS阈值，则分组被丢弃。在一种实现方式中，路由选择节点随后检查以确定在其上接收到响应分组的接收天线和信道是否代表由当前路由选择节点(未示出)服务的集合；如果不是，则分组被丢弃。此外，路由选择节点将在其上接收到响应分组的接收天线和信道与用于发送相应的邻居请求分组的发送天线和信道(如在响应分组中标识的那样)(未示出)相比较，如果它们不同则丢弃分组。此外，路由选择节点随后扫描与在响应分组中通报的路由相对应的(一个或多个)距离向量(576)。如果在与响应(环路检测)中的路径相对应的任意距离向量中发现当前路由选择节点的本地MAC地址，则分组被丢弃以防止路由选择环路。

[0062] 然后，路由选择节点查找邻居响应分组的源MAC地址以获得相邻性数据结构中的相应条目(577)。如果该条目不存在，则分配一个条目和服务于相邻关系所必需的资源(578)。如果存储器分配失败(579)，则计数器adjInsufficientMemory被递增，并且分组被丢弃。如果分配成功，则条目中的所有管理变量都被初始化为0(580)。在一种实现方式中，路由选择节点随后计算linkSNR变量，并将它与阈值相比较(582)。在一种实现方式中，linkSNR被设置为1)snrDown(接收到的邻居响应分组的SNR)和2)snrUp+5(响应节点报告的并包含在接收到的邻居响应分组中的SNR值)中的较小者。如果linkSNR小于阈值adjMinNeighSNR(582)，则分组被丢弃并且计数器adjPoorNeighSnr被递增。如图6A所示，如果相邻性条目的adjBlacklist变量被设置(584)，则计数器adjBlacklistPackets被递增，并且分组被丢弃。

[0063] 如果邻居响应分组通过上述检查，则路由选择节点随后基于来自邻居响应分组的信息更新对应于发送路由选择节点的相邻性条目(585)。在一种实现方式中，更新相邻性条目包括设置变量adjChan、adjAnt、adjSNRUp、adjSNRDown、adjMACAddress、adjNumRoutes，并且对于每个识别出的路由设置adjUnadjustedEase(见下)、adjLinkSNR、adjVectors，如接收到的相邻性分组指示的那样。变量adjUpdated被设置为1，并且潜在父(PP)定时器被设置为常数adjCMaintTimer。潜在父定时器为与对父路由选择节点的选择有关的相邻性条目提供生存时间。如果PP定时器对于给定条目到期，则adjUpdated变量被重置为0，指示它不应被用于父选择。

[0064] 路由选择节点还更新为相邻性数据结构中的条目存储的smoothSNR值(590)。在一种实现方式中，对于相邻性数据结构中的每个条目存在一个smoothSNRs矩阵，其包括发送邻居请求的路由选择节点和发送邻居响应的路由选择节点之间的每个天线对的SNR值。在一种实现方式中，路由选择节点使用邻居响应消息中的天线标识符来确定更新smoothSNRs矩阵中的哪个值。在一种实现方式中，如果先前存储在条目中的信道(adjChan)不同于在其上接收到邻居响应分组的当前信道(586)，则路由选择节点清除smoothSNRs矩阵中的所有值(588)。在一种实现方式中，路由选择节点以以下方式计算smoothSNRs矩阵中给定条目的smoothSNR值：

[0065] 1)参考每天线相邻性平滑SNR集合。如果相应天线的值是0，则计算出的adjlinkSNR(见上文)的1/2被存储在由天线索引的管理变量smoothSnrs中。

[0066] 2)否则，减去平滑天线值的1/32，并且linkSNR的1/32被添加到smoothSnrs值。

[0067] 但是，本领域技术人员将理解，上文仅示出了一种可能的实现方式，也可以使用用于平滑SNR值的其他算法。如下所详述，在实现方式中，smoothSNR值被用来选择父路由选择节点。

[0068] B.1.a.邻居评估(NEIGHE)

[0069] 本部分描述根据本发明一种可能实现方式的邻居评估——即NEIGHE过程。邻居评估可以在状态机中发生几次，例如当在SEEK状态中接收到事件adjTimerI1、在SYNC状态中接收到事件adjSeekFail、在AUTH状态接收到事件adjAuthFail，以及在MAINT状态中接收到事件adjTimerMN时。

[0070] 图6C示出了用于评估相邻性条目的根据本发明一种实现方式的过程流。在一种实现方式中，基于多个表征之一扫描和过滤相邻性数据结构(602)。在一种实现方式中，路由选择节点仅考虑adjBlacklist和adjChild变量未被设置的邻居路由选择节点。在MAINT状态下，任何未被更新的邻居(例如通过将adjUpdated变量设置为0而被表明)也被排除在考虑范围之外。

[0071] 在一种实现方式中，路由选择节点维护相邻性数据结构中的路由选择节点表，直到具有最佳adjUnadjustedEase值的adjMaxNeighs(604，606)。在一种实现方式中，adjUnadjustedEase(相邻性的宽松度)被如下计算：给定条目的smoothSNRs矩阵(见上文)中的最高SNR值被用来计算当前路由选择节点和与相邻性数据结构中的条目相关联的路由选择节点之间的链路的宽松度。在一种实现方式中。在一种实现方式中，路由选择节点计算与相邻性数据结构中的合格条目相对应的每个链路的adjUnadjustedEase值。在一种实现方式中，adjUnadjustedEase变量是从针对路由选择节点之间的链路确定的最高smoothSNR值计算出的量，其表征给定路由选择节点和根路由选择节点之间的路径中的链路的有效数据率。例如，显示出低SNR的链路可能由于不良的SNR本身或由于高差错率及其导致的重发造成的有效数据率而提供低数据率。此外，下表代表了用于基于给定链路的adjlinkSnr值计算它的adjUnadjustedEase变量的一种可能的实现方式：

[0072] SNR对adjUnadjustedEase表

[0073]smoothSNR＝＜20 2^linkSNR
smoothSNR＞20 2^20+(linkSNR-20)*300000

[0074] 但是，本领域技术人员将认识到，其他算法也可用来表征链路的宽松度/有效性。在上述实现方式中，所使用的算法反映了这样的设计选择，该设计选择在指示低于SNR值20时，差错率是确定(重发之后的)有效数据率的重要因素。如下所详述，adjUnadjustedEase变量被用于选择父路由选择节点。

[0075] 此外，给定路由选择节点和根路由选择节点之间的路径中的最受约束链路可能出现在路径中的任何地方。因此，将针对到发送邻居响应分组(见下文)的路由选择节点的链路计算出的adjUnadjustedEase值(604)与在邻居响应分组中报告的对应于每个路由的未调整宽松度相比较。在一种实现方式中，通过配置将根接入点报告的adjUnadjustedEase设置为大到足以确保它将大于任何计算出的值的值。以此方式，对应于路径中的最弱链路的adjUnadjustedEase值传播过整个路由选择节点等级。然后，对于每个条目中的每个路由(608，610)，两个adjUnadjustedEase值中的较小值(即链路或所报告的路由值)随后被除以(路由中的跳数+1)(612)。相邻性条目中的所有路由上的最小结果值被作为adjAdjustedEase存储在相邻性条目中。相应的非跳调整值被作为adjUnadjustedEase存储在相邻性条目中(614)。路由选择节点随后根据adjMaxNeighs邻居各自的adjAdjustedEase对adjMaxNeighs邻居排序，并且还把它们设置为邻居。在一种实现方式中，路由选择节点主动维护邻居路由选择节点集合、周期性地向它们发送单播邻居请求分组。路由选择节点还选择具有最高adjAdjustedEase值的邻居路由选择节点作为试探性父(616)。如果选定的试探性父与当前父不同，则路由选择节点递增计数器adjParentChanges。adjParentChange事件被发送到发送安排模块，并且状态被设置为SYNC。

[0076] 也可以使用其他实现方式。例如，当前父路由选择节点在邻居响应分组中报告的UnadjustedEase值可以在被上述过程使用之前被修改。例如，父路由选择节点所报告的每个路由的UnadjustedEase可以使用上述SNR对Ease算法的逆过程被转换回SNR值。所得到的SNR值可以被增加20％，然后被转换后未调整的宽松度值。例如，假设路由的unadjustedEase是256。这一个被转换成值为8的SNR。加上20％得到10，10可以被转换成值为2^10或1024的unadjustedEase。这种偏置机制可被用来防止路由选择节点在具有类似的路径属性的两个潜在父路由选择节点之间来回切换。

[0077] B.1.b.发送请求到下一邻居(TXNEXT)

[0078] 下文描述根据本发明一种实现方式的TXNext过程的操作。TXNext在接收到事件adjTimerMP时运行在MAINT状态下，并且在接收到事件adjTimerI2时运行在SEEK状态下。邻居列表被扫描(注意，在SEEK状态下不存在邻居)。每次接收到adjTimerMP，邻居列表都被扫描以确定从哪个邻居开始尝试肯定确认。只有未确认的邻居被发送请求。如下所示执行扫描：N0、N1、N0、N2、N0、N3、N0、N4、N0、N5、N0、N1，……，每接收到adjTimerMP扫描一个。
根据adjAdjustedEase(见上文)对邻居排序。因此，N0是最希望的节点(也就是父)，N1是下一最希望的，依此类推。在一种实现方式中，路由选择节点发送邻居请求分组到选定的邻居，直到接收到合适的确认，此时用于Nx的时隙被用于广播邻居发现。当向邻居发送时，请求分组被直接发送到邻居(即使用邻居的MAC地址)。如果所有邻居都已被确认，则以公平方式扫描天线和信道，并且邻居请求分组被发送到广播MAC地址。

[0079] B.2.邻居消息协议分组

[0080] 下文示出了根据本发明一种实现方式的邻居请求分组的格式。

[0081] 邻居请求分组

[0082] 字节类型和版本 /*请求响应类型和版本标识符*/

[0083] 6字节parent /*父路由选择节点的MAC地址*/

[0084] 字节antenna /*在其上发送请求的天线*/

[0085] 字节channel /*在其上发送请求的信道*/

[0086] 10字节netname /*网络标识符*/

[0087] 在所示实现方式中，版本被设置为0，类型被设置为1(指示邻居请求消息)，父被设置为父路由选择节点的MAC地址(如果路由选择节点没有父则被设置为0)。此外，下面根据本发明的一种实现方式示出了邻居请求分组的格式。下表描述了根据本发明一种实现方式的分组的字节中的值。

[0088] 邻居请求分组

[0089] 字节类型|版本

[0090] 字节snr； /*接收到的链路snr*/

[0091] 字节error； /*接收差错率*/

[0092] 字节numRoutes； /*keepalive中的路由数*/

[0093] 字节rxAntenna； /*在adj请求中接收到的天线*/

[0094] 字节channel； /*在adj请求中接收到的信道*/

[0095] 6字节child； /*针对其生成响应的子*/

[0096] 10字节netname； /*网络标识符*/

[0097] 字节txAntenna； /*用于adj请求的RX和TX天线*/

[0098] 2字节slotEarly； /*时隙前切换时间*/

[0099] 2字节slotDead； /*时隙末尾的死区时间*/

[0100] 2字节slotDuration；/*时隙持续时间*/

[0101] 后面跟着变量结构，每个路由对应一个变量结构：

[0102] 字节number of hops

[0103] 6字节RAP /*根路由选择节点的MAC地址*/

[0104] 6字节1st hop /*第一跳路由选择节点的MAC地址*/

[0105] 路由中的字节数 /*距离向量中的字节数*/

[0106] 距离向量 /*路由中的路由选择节点的MAC地址*/

[0107] B.3.常数、计数器和变量描述

[0108] 下表列出了对本发明一种实现方式使用的各种常数、计数器和变量的描述。

[0109]adjChildHoldExp 10秒
adjMaxNeighs 5
adjMinNeighSNR 12
adjTimerPPtExp 30分钟
adjTimerBlacklistExp 10分组
adjTimerI1Exp 880厘秒
adjTimerI2Exp 5厘秒
adjTimerMNExp 10秒
adjTimerMPExp 30厘秒
AP_REQUEST 1
AP_RESPONSE 2
AP_VERSION 1
AP_MAXHOPS 8

[0110] B.3.b变量和计数器

[0111]

[0112] B.3.c.因相邻性条目而定的变量和计数器

[0113]

[0114] B.3.d.事件

[0115]adjNull 旋转状态机的空事件
adjRxNeigh 接收邻居分组
adjSyncFail 同步失败
adjSyncSucc 同步成功
adjAuthFail 认证失败
adjAuthSucc 认证成功
adjQuit 退出
adjTimerI1 评估邻居和选择父
adjTimerI2 发送下一邻居请求分组
adjTimerMN 评估邻居，可能选择新父
adjTimerMP 在下一信道/天线上发送邻居请求
adjTimerBL 从黑名单移除相邻性
adjTimerPP 移除潜在父
adjNewChild 新子已被添加到子列表
adjChildDel 子已被从子列表移除
adjParentChange 向LLC指示发生了父改变

[0116] C.基于时隙的发送安排机制

[0117] 下面列举了由无线网格中的节点实现的基于时隙的发送安排机制。在一个方面中，每个节点实现包括固定的统一数量的时隙的周期间隔。在一种实现方式中，周期间隔可以包括数据时隙和竞争时隙。如图8所示，在一种实现方式中，周期间隔包括固定的统一数量的数据时隙，后面跟着固定的统一数量的竞争时隙。在所示实现方式中，存在11个数据时隙；但是，也可以使用其他配置。数据时隙是专用于父和子节点之间的流量的单向或双向流的时隙。如下所详述，在给定的数据时隙，路由选择节点只与一个其他路由选择节点(例如其父路由选择节点或选定的子路由选择节点)通信。此外，路由选择节点接收来自其父节点的指示父何时具有与其的依照安排的通信的时隙安排信息，然后使用该信息来安排其自己的子路由选择节点。在一种实现方式中，在每个周期间隔期间至少一次接收时隙安排信息，允许路由选择节点动态重配置它们的时隙安排，以便适于改变网格拓扑。

[0118] 对竞争时隙的使用是服务于几个目的的优化，如下所述；但是，对竞争时隙的使用是可选的。也就是说，对竞争时隙的使用可能增加延迟，因此，它们的使用取决于各种工程和性能考虑。首先，竞争时隙允许不能在周期间隔的数据时隙部分期间与其所有子通信的节点执行与它们的间接通信，从而确保所有父和子在每个周期间隔都被服务。其次，它们允许具有超量数据通信的节点提高周期间隔期间的吞吐量。第三，竞争时隙允许在每个周期间隔中在节点邻居之间发送管理或控制流量，同时仍服务于所有子和父节点。给定实现方式不需要包括竞争时隙，但是，这可能意味着不是所有的节点都将在每个周期间隔期间被服务。

[0119] C.1.时隙安排

[0120] 图9为了说明的目的示出了等级无线网格的一部分，其在相关部分包括等级中第一层的父节点P、作为父节点P的子节点的中间节点N1、N2、N3和N4，以及节点N1的子节点C1、C2、C3、C4和C5。每个节点及其(一个或多个)子节点通过独立于父节点安排子节点来避免永久安排锁。但是，在给定的周期间隔中安排的子节点数量和与父节点相关联的子节点的数量是互质的，以确保在父节点和给定子节点之间不存在环路(其中父节点每次应当服务于子节点时都会服务于它的父)。如果两个数没有公因子，则两个数互质。因此，4和3互质，虽然4不是质数。在一种实现方式中，例如，具有通报了四个子的父节点的节点将安排5个子，即使它只有4个子。互质数具有这样的特性，其确保在较大周期(两个互质数的乘积)内不存在内部周期。该特性确保了安排是公平的，并且在父节点循环经过周期间隔时没有子将被连续忽略。

[0121] 图10A和10B根据本发明的一种可能的实现方式示出了父节点P及其子节点N1如何安排它们各自的数据和竞争时隙。在每个时隙周期的开始处，给定节点确定它用于该周期的安排，并相应地安排其子和父时隙或天线。竞争时隙可被用来服务于丢失的子时隙、安排信道外邻居发现，和/或为具有超量数据的子增强传输。在一种实现方式中，在每个周期间隔的开始处，父节点安排周期间隔中的时隙，并向每个子节点传递时隙安排及其子节点的有效数量。每个子节点又使用该时隙安排信息来计算其自己的时隙安排。例如，如图10A所示，父节点P具有四个子节点而不具有父节点(例如它直接连接到无线网格控制系统
20)。因此，它在它的子节点N1-N4上平均分配可用数据时隙1-11。如图10A所示，在下一周期间隔期间，父节点P继续循环经过其子节点。如下所详述，父节点P将该时隙安排以及有效子节点数传递给子节点N1(及其其他子节点)。子节点N1使用该信息来创建其自己的时隙安排。如图10B所示，子节点N1在通过循环经过所有子节点所得到的数据时隙安排上重叠由其父节点传递给它的时隙安排，从而在第一周期的数据时隙中的时隙1、5、9期间安排与其父节点P的发送。在一种实现方式中，每个节点在它接收到时隙通知消息时重新计算它的时隙安排。

[0122] 在一个实施例中，从循环地址空间导出时隙号。该地址空间被允许所有时隙周期重复的数字定界，并且为了说明目的而被称为时隙史诗(epic)号。在一个实施例中，时隙号从0开始，并且范围是到基于周期间隔中的周期总数的倍数或诸如父节点被限定的子节点数等其他因素的定界时隙史诗号。在一种实现方式中，定界号是55440(11×10×9×8×7)。因此，时隙号55440是不被允许的；当时隙号到达史诗号时，它折返回时隙号0。

[0123] C.1.a.有效子节点数

[0124] 如上所述，基于每个节点实际具有的子数和它的父通报的有效子数，该节点计算有效子数以便计算时隙安排。如上所述，通过维护有效子数之间的互质关系来确保父节点和子节点之间的安排公平性。换言之，该互质关系防止当前节点的给定子路由选择节点重复使用其数据时隙与当前节点的父节点通信。在一种实现方式中，每个路由选择节点参考下表(或其他数据结构)来基于其父通报的有效子数及其实际子数来计算通报的有效子值。左手侧列对应于父节点的通报的有效子数，顶部一行是给定节点具有的实际子数，每个被索引的单元是节点应当作为其有效子通报的数量。

[0125]PEC\#C 1 2 3 4 5 6 7 8 9 10 11 12
1
2 2 3 3 5 5 7 7 7 7 7 7 7
3 2 3 4 4 5 7 7 8 10 10 10 10
4 3 3 4 4 5 7 7 9 9 9 9 9
5 2 2 3 5 6 6 7 8 9 9 9 9
6 5 5 5 5 6 7 7 7 7 7 7 7
7 2 2 3 4 5 7 8 8 9 10 10 10

[0126] 有人可能认为这里应跳到互质数“9”。但是，这将导致多于3个子节点在给定周期间隔中比其他节点被分配更少的数据时隙。

[0127]8 3 3 3 5 5 7 8 9 9 9 9 9
9 2 2 4 4 5 7 7 9 10 10 10 10
10 3 3 5 5 5 7 7 9 10 9 9 9

[0128] 有效子节点表

[0129] 如表所示，在一些情形下，有效子数大于实际子数。在此情形下，节点仍然根据有效子数计算数据时隙安排以便维护上述互质关系。在一种实现方式中，对应于“虚幻”子节点的数据时隙实质上是死时隙，因为实际上没有与之通信的子节点。在某些实现方式中，路由选择节点可以在虚幻数据时隙期间执行其他操作，例如扫描其覆盖区域来潜在地获得额外的子节点、广播邻居请求分组等。此外，在一些实现方式中，通过配置，路由选择节点被限制为获得不多于N个子节点，其中N是可配置参数(例如5、7等)。如果多于N个子节点被获得，则路由选择节点基于多种标准(例如相对信号强度、SNR等)丢弃一个。此外，当路由选择节点获得新子节点时，它在下一周期间隔开始处创建新时隙安排。

[0130] 这种方案也可以在某些情况下被优化。例如，如果节点的父(P)具有两个子节点，并且节点本身具有两个子(C1和C2)，则路由选择节点可以配置4个节点的周期，并且以如下方式安排数据时隙：P、C1、P、C2、P、C1、P、C2……否则，使用上述方案，可以以如下方式安排数据时隙：P C2 P C1 P X P C2 P C1 P X……其中X是死时隙。因此，上述方案可以代替上述质数关系来优化时隙安排机制的效率。

[0131] C.2.时隙安排操作

[0132] 在每个周期间隔，路由选择节点确定它用于该周期间隔的发送安排，并相应地安排其子和父时隙。在一种实现方式中，路由选择节点还可以在从父路由选择节点接收到时隙通知分组中的新信息时重新计算其发送安排。此外，在每个周期开始处可以确定以下变量：1)有效子数；和2)每个子节点使用的时隙。该信息在时隙通知分组或PDU中被发送到子节点。在一种实现方式中，路由选择节点上的时钟同步是通过父节点在时隙通知分组中向其子发送时间戳来完成的，如下所详述。子接收时隙通知分组，并标记它接收到分组的时间。计算作为发送分组和解调以及接收分组的时间的空中时间。接收时间和发送时间被比较，这两个时钟随后可被同步，如同被发送和接收分组的时间所调整一样。

[0133] 为了使无线网格高效操作，希望提供路由选择节点上的精确定时。在一种实现方式中，时隙通知分组包含时隙安排信息，其允许接收子节点计算时隙安排并维护与其父节点的定时同步。时隙通知分组包括高分辨率时间戳，其在一个实施例中是基于在IEEE802.11WLAN规范中实现的定时同步功能(TSF)定时器的，该定时器是64位高分辨率定时器。在一种实现方式中。时隙通知分组包括：1)分组被发送的TSF定时器时间，2)本地TSF对于时隙开始时间应读取的16位，3)子节点被允许用于数据传输的时间(以微秒为单位)，4)循环时隙号序列空间中的当前时隙号，5)与史诗时隙号“0”相关的子节点的有效子节点数和开始位置；6)与史诗时隙号“0”相关的子节点的实际子节点数和开始位置；以及
7)在其间发送时隙通知分组的迷你时隙号。时隙通知分组也可以包括其他信息，例如为子节点缓冲的数据量；分配给时隙的子数(1用于数据时隙，大于等于1的用于竞争时隙)；以及分配给下一时隙中的子节点的发送时间的微秒数。在一个实施例中，当路由选择节点发送时隙通知分组时，它将时隙通知分组与以下较小者一起排队：1)目的地为子节点的任意数据分组和2)在考虑到在前一时隙通知分组中分配给子节点的发送时间量的情况下，节点可以发送而不会超过数据时隙中的时间量的分组数。路由选择节点使用子节点响应于时隙通知分组发送的确认帧来开始发送任意被排队的数据帧。在一种实现方式中，父路由选择节点不需要在每个数据时隙处都发送时隙通知帧。在一种实现方式中，在以下情况下发送时隙通知帧：1)子节点已经请求了对数据的分配以便向父路由选择节点进行发送；2)父具有要向子节点发送的数据；或3)父路由选择节点应当发送时隙通知分组以使得子节点不会超时或丢失与父路由选择节点的同步。

[0134] 子路由选择节点可以发送时隙响应帧到它们各自的路由选择节点。在一个实施例中，子路由选择节点周期性地发送时隙响应帧到父节点作为到父节点的保活消息，并且只要子节点有大量数据要发送到其父路由选择节点，子节点就发送时隙响应帧。时隙响应帧可以包括以下信息：1)已排队数据的微秒数，和2)时隙数。在子节点打算与其父通信的时隙开始处，它选择定向到其父的天线。如果节点有数据要发送，则它将时隙响应帧与可以在该时隙中被发送的数据一起排队。使用迷你时隙来实现与同一时隙同步的同一物理扇区中的其他干扰节点之间的竞争，并且确保没有哪个路由选择节点总是赢得对数据时隙的访问权。然后，节点等待来自其父的时隙通知。在接收到通知时，节点将时隙通知信息拷贝到它的父邻接性中，并更新其时隙开始时间。路由选择节点还将其父邻接性标记为已被服务。

[0135] 图11A示出了用于由路由选择节点实现的数据发送过程和时隙安排的根据本发明一种实现方式的过程流。在每个周期间隔开始处，节点清除其邻接性数据结构中的所有标志(302)，并计算用于当前周期间隔的数据时隙安排(304)。然后，节点根据计算出的安排循环经过每个数据时隙(见图11B)(306)。在一种实现方式中，每个节点随后经历竞争时隙周期(312)。在所示实现方式中，每个节点扫描其相邻性数据结构以确定在数据时隙周期期间是否有任意子节点未被服务，并且在竞争时隙周期期间安排该子节点(308)。此外，路由选择节点扫描相邻性数据结构以确定它是否在数据时隙周期期间被它的父节点服务，并在合适的竞争时隙周期期间安排与其父的数据传输(310)。

[0136] 如图11A所示，在每个周期间隔之后，每个路由选择节点确定它是否从其父节点接收到时隙通知消息(320)。如果是，则路由选择节点重置re-sync计数器(322)。如果否，则路由选择节点递增re-sync计数器(324)。如果路由选择节点未在阈值(th1)数量的周期内接收到时隙通知消息(326)，则路由选择节点进入重同步状态以重新获得父节点(328)，如下所述。

[0137] B.2.a.数据时隙周期

[0138] 图11B示出了在周期间隔的数据时隙阶段期间，根据本发明一种实现方式的过程流。如上所述，给定节点可以在任意给定数据时隙期间与父节点或子节点通信。在一种实现方式中，当路由选择节点具有多于一个天线时，它选择与它将在下一数据时隙期间与之通信的路由选择节点相关联的天线(352)。如图11B所示，用于每个数据时隙的过程流的其余部分依赖于节点与父还是子节点通信(354)。在数据时隙的开始处，父节点发送时隙通知消息或帧，以标记数据时隙的开始(356)。在一种实现中，在数据时隙开始期间，父节点发送时隙通知帧(见上文)，该时隙通知帧是到在数据时隙中被安排的子节点的定向或单播分组。在竞争时隙期间(见下文)，时隙通知帧被广播。如上所述，时隙通知分组中的时隙安排信息允许子节点确定在哪些时隙中子应当尝试与父节点的数据传输。

[0139] 在一种实现方式中，在接收到时隙通知帧时(364)，子节点发送时隙确认到其父(365)。在接收到时隙通知帧时，子节点将时隙通知帧中的时隙安排信息拷贝到其父相邻性数据结构中，并更新其时隙开始时间(366)。在一种实现方式中，节点标记其父相邻性为已针对该周期间隔被服务过。在一种实现方式中，时隙通知确认可以包括子必须发送的数据量，通过扩展，值0指示流控制有效。在一种实现方式中，当节点总共有太多数据要发送到其父和子并且因此缺乏缓冲器空间时，数据流控制位被设置。路由选择节点不发送数据到在它们发送的时隙通知或确认分组中设置了该位的其他节点。

[0140] 如图11B所示，父节点使用时隙通知ACK来设置对应于其相邻性数据结构中的子节点的标志(360)。此外，对时隙通知ACK的接收还标记了在数据时隙期间发送已排队数据到子节点的开始(362、368)，如下所详述。在发送确认之后，在一种实现方式中，根据流控制约束，子节点还能够自由地进行到其父的发送。

[0141] 在一种实现方式中，路由选择节点可以确定其下一父数据时隙，以及用于其子路由选择节点的下一数据时隙，如下所述。令Sn为离循环时隙序列空间中的时隙0最后的路由选择节点的安排号。如果安排父，则这是时隙通知分组中的时隙号，否则它是被节点分配给子的时隙号(例如有效子数的时隙0、有效子数的时隙1，等等)。此外，令Cs为当前时隙号。路由选择节点随后计算Cc作为当前时隙周期号，如下所述：

[0142] Cc＝Cs/(#每周期数据时隙+#每周期竞争时隙)

[0143] 路由选择节点可以如下计算Cd，即周期开始处的开始数据时隙号：

[0144] Cd＝Cc*(#每周期数据时隙)

[0145] 此外，令Cn等于父路由选择节点或子路由选择节点的周期号。当安排父时，Cn是父在时隙通知帧中通报的子数。对于子路由选择节点，Cn是通报给它们的有效子数。最后的周期安排(Ls)被如下计算：

[0146] Ls＝Cd-(Cd除以Cn所得的余数)

[0147] 于是在其中进行安排的下一时隙变为：

[0148] Ns＝Ls+Sn+Cn，如果(Ls+Sn)＜Cd；否则Ns＝Ls+Sn。

[0149] 因此，Ns是在其中安排节点(父或子)的下一数据时隙，Ns+Sn是下一周期中的数据时隙，Ns+2Sn是下一数据时隙，依此类推。当然，如果竞争时隙不被使用，则该安排算法应被相应地修改。

[0150] C.2.a.1.数据时隙的解剖

[0151] 图12和13示出了数据时隙的主要分量和解剖。在一种实现方式中，每个数据时隙足够大，以使得路由选择节点在前一数据时隙到期时将天线切换到父或子节点、发送或接收时隙通知帧和传输数据。在一种实现方式中，使用迷你时隙来管理给定区域或扇区中的路由选择节点上的干扰。在一种实现方式中，迷你时隙持续时间跨过发送时隙通知帧的时间加上将帧发送到可以接收帧的最大范围的传播延迟以及处理帧和延缓发送的时间量。在一种实现方式中，该时间被设置为20微秒，但是，也可以配置其他迷你时隙持续时间。路由选择节点在随机的基础上确定它在其间开始发送的迷你时隙。例如，路由选择节点可以采用随机数生成器来选择迷你时隙。迷你时隙可被用来打乱到被同步到同一时隙的扇区中的节点之间的时隙的访问，并且在一种实现方式中，意在确保没有哪个节点总是赢得对该数据时隙的访问。例如，使用迷你时隙允许给定路由选择节点顺从具有较早迷你时隙的另一节点。在包括全向天线的网络中，迷你时隙的数量大大增加，以便应对更大数量的潜在干扰者。父和子迷你时隙之间的延迟(在一种实现方式中，20微秒的延迟)在一些实现方式中被用来防止开始时间的意外交换。基于实验结果，在时隙开始时间观察到某些抖动。因此20微秒的延迟减小了交换的可能性。这种事件的成本不大：但是却是不希望的。但是，迷你时隙可与其他算法和过程一起使用。时隙末尾的时隙防护死区时间是为了防止时隙溢出。天线切换时间允许无线电单元被准备好用于新时隙中的接收和发送。该步骤在全向天线设置中仅是死区时间，因此可被设置为0。

[0152] 图13示出了根据本发明一种实现方式的在父和子之间的数据时隙内的数据传输。父和子节点通过发射RTS帧来覆盖它们的整个数据传输时间，RTS帧包括用于发送它们在数据时隙期间产生的所有分组的整个延迟。在数据时隙期间，数据分组的发送仅需要ACK。ACK被用来确定分组是否被成功发送到目的地路由选择节点。未被确认的分组被重新排队以供以后发送。

[0153] 子和父路由选择节点都被允许在时隙期间发送数据。但是，如果子和父节点都发送整个时隙的数据，则时隙将溢出。因此采用内时隙竞争模型，该模型包括传送要求和可用时隙时间的机制，以及决定分配多少带宽的策略。该机制允许子请求用于下一个之后的时隙的带宽(时隙确认分组中的字段requestedMicros)，并且父许可两个时隙以后的带宽(时隙通知分组中的字段PermittedMicros)(这些值分别存在于时隙确认和时隙通知分组中)。父路由选择节点进行包括诸如当前负载等因素的策略判决，尝试用单向流量打包时隙，并给予下载流量少许优先。父节点执行它视为合适的任何计算来确定向其子节点提供多少微秒。在没有802.11时隙通知ACK时，或者如果在最后时隙期间节点没有发送时隙通知分组到子，则节点假设子将发送多达默认量的数据到时隙中。节点使用诸如子节点想要发送多少流量、子有机会发送数据的最后时间等因子来确定子节点可以使用多少时隙。

[0154] 也可使用其他实现方式。例如，在另一实现方式中，父路由选择节点不需要在每个数据时隙中向子节点发送时隙通知分组。在一种实现方式中，所讨论的路由选择节点协议被配置为使得父路由选择节点以每秒一或两次的量级与每个子通信。这一般足以保持时钟同步。路由选择节点可以在周期性或半规则的基础上发送时隙通知分组，以确保时钟漂移不会变得显著，和/或确保子节点不会认为父节点已被禁用或丢失定时。路由选择节点还可以响应于对子节点已请求大于默认数据量的数据传输量的指示而发送时隙通知分组。

[0155] C.2.b.竞争时隙周期

[0156] 在使用竞争时隙的实施例中，在数据时隙周期的末尾，父节点扫描其相邻性数据结构以寻找不受重视的子(即在最后安排周期间隔中被分配较少数据时隙的子)，或者它在最后的数据时隙周期中没有与之通信的子。如果父发现它没有服务子节点，则它强迫自己依赖于节点在树中的级别而在竞争时隙12、13和14或15、16和17中的至少一个期间可用。在一种实现方式中，当级别除以2所得的余数是0时，父节点在竞争时隙12、13和14之一期间对子节点可用，或者在时隙15、16和17期间对子节点可用。在一种实现方式中，树中的级别被编号为开始于最高节点是0，接下来，等级中连接到最高节点的节点是1，依此类推。

[0157] 在数据时隙周期的末尾，子节点检查它们的父相邻性以确定它们是否在最后的数据时隙周期中被服务。如果它们没有，则它们进行检查父级别除以2所得的余数，如果这个量是0，则它们尝试在周期12、13和14(否则在时隙15、16和17)期间与它们的父通信。子可以选择在竞争周期期间安排自身与其父的通信，尤其是当它或它的父具有额外的数据要传递时。第一层节点(例如节点N1、N2)还可以使用时隙12、13和14，如果它们已经服务了它们的所有子，并且如果它们具有与父的额外数据传输或它们的父具有与它们的额外的数据传输。

[0158] 在一种实现方式中，希望在竞争时隙周期期间通信的父路由选择节点等待时隙的开始，并发出广播可用性通知。接收该通知的子节点确认它们的父，并传输可用数据。没有它们不重视的子和没有它们缺乏通信的父的节点可以自由地在竞争阶段尝试与子或父的额外的数据传输，或者尝试其他信道上的邻居发现和获得。

[0159] 在时隙周期的开始处，节点确定竞争时隙的部署。如果数据时隙被部署为父和子的集合都被服务，则节点可以选择使用所有竞争时隙用于发现。该判决是在时隙周期的开始处进行的。如果是这样，则所有竞争时隙都被使用并且那就是它们的安排。发现每n个时隙运行一次，其中n在一种可能的实现方式中是4。

[0160] 路由选择节点可以根据以下偏好使用其子竞争时隙。

[0161] 1.节点安排任意未被服务或不受重视的子。

[0162] 2.时隙被安排用于邻居获得和发现。

[0163] 2.BAP父节点和父的子节点的集合被集中，并且子竞争时隙被一个时隙接一个时隙地安排，以便服务于具有最大数据传输需求的节点。(在此情形下，时隙被当作竞争时隙，因此通知被广播。)

[0164] 4.以随机或轮换天线选择方式安排时隙作为竞争时隙。

[0165] 以如下优先级安排父竞争时隙：如果该时隙已被专用于邻居发现，则父时隙被用于该目的。否则，路由选择节点选择定向到其父的天线，并侦听时隙通知分组。在接收时，如果父没有要发送的数据，并且子没有要发送的数据，并且通知被多播，则通知被忽略。否则，子发送定向时隙通知确认，数据传输可以开始。

[0166] D.减轻同步丢失

[0167] 如上所述，路由选择节点在SYNC状态期间与父路由选择节点同步。在SYNC状态期间，路由选择节点选择定向到其父节点的天线，发送请求到该父节点，并监视时隙通知消息。在一种实现方式中，路由选择节点在SYNC状态下等待时隙通知消息直到4个周期间隔。此外，路由选择节点在此期间周期性地发送定向邻居请求分组到其父路由选择节点。如果在4个时隙周期之后路由选择节点未接收到时隙通知消息并获得其父路由选择节点，则它把该父放在黑名单中并选择另一试探性父。如上所述，如果路由选择节点识别出另一试探性父，则它重新进入SYNC状态。假设它获得父节点，则路由选择节点进入MAINT状态并重新创建其时隙安排。否则，路由选择节点进入START状态以收集额外的相邻性信息。

[0168] 给定的路由选择节点可能由于多种原因而丢失与其父节点的同步。例如，父路由选择节点可能得到或丢失了子节点，这导致父重新计算其时隙安排。新时隙安排可能妨碍子节点接收来自父的时隙通知消息。同步丢失的其他原因可能由父路由选择节点上的硬件故障引起，或者由于父节点不再提供服务引起。此外，诸如新的RF干扰源等环境改变也可能导致子路由选择节点丢失与其父节点的同步。

[0169] 在一种实现方式中，如果路由选择节点没有在8个周期间隔之后接收到时隙通知消息，则它检测到其父路由选择节点中的改变(例如节点故障)。在此期间，路由选择节点继续执行当前时隙安排并与其子节点通信，发送任何已排队数据并从子节点接收数据。但是，在8时隙时段的末尾处(见图11A，标号326)，路由选择节点选择定向到其父节点的天线并重新进入SYNC状态。如上所述，并且如图7所示，路由选择节点发送邻居请求分组到父路由选择节点(702)，并等待来自父路由选择节点的响应，在一种实现方式中，等待4个周期间隔(704，706)。如上所述，如果父路由选择节点没能响应，则路由选择节点将父列入黑名单(708)并选择用于尝试同步的另一试探性父(如果有的话)(710，712)。在SYNC状态期间，路由选择节点的子节点也检测到改变，因为它们不再从路由选择节点获得时隙通知消息。但是，与当前路由选择节点类似，子节点在重新进入SYNC状态之前等待8(Th1)个周期间隔。

[0170] 在路由选择节点进入SYNC状态之后，它要么重新获得其父路由选择节点(在此情形下它再次开始发送时隙通知消息到其(一个或多个)子节点)，要么寻求获得新父。在后一情形下，路由选择节点获得新父，并再次开始发送时隙通知分组到其(一个或多个)子节点。在此情形下，可能没有网格网络的进一步的干扰，除非时隙周期已改变。如果是这样，则子节点重复该过程，但是树的较低部分保持其初始形式，除非被指示进一步的拓扑改变，对拓扑改变的指示将基于相邻性协议而发生。

[0171] 图16示出了当路由选择节点检测到其父路由选择节点中的改变并最终进入SYNC状态时采取的动作的定时。具体而言，图16示出了丢失其父，没能成功获得父，没能获得第二父，但是最终对第三路由选择节点取得成功的路由选择节点。图16的的较低部分示出了这些动作对当前路由选择节点的子节点的影响。

[0172] 如上所示，通过将父故障超时(这里是8个周期间隔)配置为大于获得超时(这里是4个周期间隔)，同步丢失对整个网格网络的影响被减小或缓解。例如，如果路由选择节点重新获得其父节点，则等级网格的较低部分将保持在其当前状态，除非发生拓扑或数据时隙安排改变。例如，如果需要12个周期来使父节点超时，但是只需要4个周期来获得新父，则丢失其父节点但是重新获得该父节点或另一父节点的路由选择节点将丢失其(一个或多个)子节点。此外，本领域技术人员将意识到也可以使用其他实现方式。例如，可以相对于独立于周期间隔的定时器跟踪故障和获得超时。此外，故障和获得超时之间的2∶1比率是用于说明的。也可以采用其他比率。本领域普通技术人员将意识到故障和获得超时的绝对和相对配置取决于工程选择。

[0173] E.网格路由选择

[0174] 在一种实现方式中，网格网络控制系统20和每个路由选择节点包括支持网格网络路由选择操作的功能。在一种实现方式中，上行链路和下行链路信息被根据如下详述的另一发现过程动态配置。此外，本领域普通技术人员将理解，下面描述的路由选择算法意在说明本发明在一种可能的网格网络实现方式中的操作。因此，也可以使用其他路由选择算法和过程。

[0175] 在一种实现方式中，用定义等级网格网络配置的所有路由来配置网格网络控制系统20。在一种实现方式中，网格网络控制系统20针对每个等级树形成和发送包括路由选择信息的路由发现分组到给定树的每个分支上的叶子路由选择节点34。除了上述邻居发现过程以外，在路由发现分组穿过网格网络时，到叶子路由选择节点34的路径中的路由选择节点还可以学习它们各自的父和子路由选择节点的身份。例如，在一种实现方式中，路由发现分组包括包括到叶子路由选择节点34的消息路由选择头部204。在接收到路由发现分组时，路由选择节点1将它发送到在消息路由选择头部中标识的下一跳。当这些路由发现分组穿过路由选择节点的等级到叶子路由选择节点34时，路径中的路由选择节点记录消息路由选择头部中的信息。图14示出了在路由选择节点之间发送的无线帧的一些头部。图15示出了根据本发明一种实现方式的消息路由选择头部。如图14所示，在一种实现方式中，无线帧是包括封装了消息路由选择头部(MRH)204的802.11头部202的802.11帧。
其他头部可以包括802.3或随后一跳路由选择节点使用的其他链路层头部(如下所详述)以及IP头部208。

[0176] 以此方式，网格网络中的路由选择节点学习它们的父和子路由选择节点的地址，以及沿从跟路由选择节点30到叶子路由选择节点34的路径的路由和跳计数。路由发现分组的MRH中的信息允许路由选择节点在上行链路方向上正确地路由无线帧。以此方式使用路由发现分组回避了在每个路由选择节点处手工配置上行链路和下行链路MAC地址的需要。此外，网格网络控制系统20可以简单地通过形成定义所需路由的MRH并在路由发现分组中将它们发送到叶子路由选择节点34来动态重配置等级网格网络中的路由。在一种实现方式中，叶子路由选择节点34简单地丢弃路由发现分组。在另一实现方式中，当路由发现分组到达叶子路由选择节点34时，叶子路由选择节点34记录MRH信息、清除MRH，并将路由发现分组沿上行链路发送到网格网络控制系统20。当路由发现分组在上游方向上穿过网格网络时，每一跳处的路由选择节点将它们的MAC地址添加到MRH，并使用最低成本或其他路由选择算法将分组路由到上游路由选择节点。以此方式，网格网络控制系统20可以学习新路由，并可能通过在下游方向上发送路由发现分组来应用它们。

[0177] 如上所述，在一种实现方式中，在网格网络控制系统20处向路由选择节点等级发送或从路由选择节点等级接收的每个分组被封装以包含到目的地的路径的消息路由选择头部(MRH)。图15示出了根据本发明一种实现方式的消息路由选择头部。控制字中的“D”指示路由是从顶部还是底部读取的。在一种实现方式中，例如从无线客户端到网络50的上行链路路由选择是静态的并且基于路由选择节点在处理路由发现分组期间记录的消息路由选择头部信息。在一种实现方式中，接收无线帧的路由选择节点执行以下操作之一：1)如果MRH中标识的最后一个MAC跳是处理路由选择节点，则剥离802.11头部和消息路由选择头部并将分组传递到WLAN接口；和2)用MRH中的下一跳MAC地址更新802.11头部202中的目的地MAC地址，并将分组放在合适的上游或下游队列中以供后续发送。

[0178] 在一种实现方式中，网格网络控制系统20针对去往和来自网格网络中的等级树的所有分组添加和剥离消息路由选择头部。网格网络控制系统20还可操作来桥接从网格网络到网络50的无线流量。在一种实现方式中，网格网络控制系统20包括图形用户界面(GUI)，用于辅助网格组织、统计量收集和路由监视。此外，为了选择目的地为无线客户端40的无线帧的路由下行链路，网格网络控制系统20可操作来监视每个无线客户端与哪个路由选择节点相关联。在一种实现方式中，每个路由选择节点可被配置为在无线客户端与路由选择节点的接入点功能相关联之后发送诸如SNMP陷阱之类的通知到网格网络控制系统20。在另一种实现方式中，网格网络控制系统20可以检测穿过网格网络控制系统20的数据流中的新无线客户端MAC地址。此外，在一种实现方式中，从无线客户端40发出的所有无线客户端流量首先被沿上行链路发送到网格网络控制系统20，网格网络控制系统20可以在无线流量被沿下行链路发送回另一无线客户端之前对流量应用策略。最后，网格网络控制系统20可以包括辅助对路由选择节点处的WLAN接入点功能的管理和操作的接口和相关功能。

[0179] 参考特定实施例描述了本发明。但是，虽然上述实施例结合IEEE802.11网络协议进行操作，但是本发明可以与任何适当无线或有线网络协议一起使用。此外，虽然上述实施例包括单个网格网络控制系统20，但是本发明的其他实现方式可以把网格网络控制系统20的功能结合到用于每个等级树的独立设备中。此外，网格网络控制系统20的功能可以被集成到其他网络设备(例如根路由选择节点30)中。本领域普通技术人员将清楚其他实施例。因此本发明仅受限于所附权利要求的指示。