在无线网格网络中实现全部到全部通信的方法和装置

摘要

在无线网格网中，通过使用被路由穿过该网络的中继分组来执行全部到全部的通信。在至少一个实施例中，该中继分组包括对网格网中的所有节点可用的汇聚信息。

说明书

技术领域

本发明一般的涉及无线通信领域，并且更特别的，涉及无线网格网(meshnetwork)中使用的通信技术。

背景技术

无线网格网是由无线节点组成的网络，无线节点可以既作为独立的通信设备，又作为路由设备。也就是说，一个节点自身可以发送和接收信息，还可以为其他节点在适当方向传递信息。无线网格网中的每个节点都可以支持与该网络中的一些或所有其他节点的一条直接无线链路。在无线网格网中，可以存在要求该网络中的所有节点与该网络中的所有其他节点共享信息的功能。这就是通常所说的全部到全部(all-to-all)通信。在过去的一些网格网中，通过允许网络中的每个节点独立地向该网络中的所有其他节点发送信息或从该网络中的所有其他节点接收信息，来实现全部到全部的通信。这种技术是低效率的，尤其，他们通常为了路由的目的而需要执行大量的数据传输。在网格网中需要能够高效的实现全部到全部通信的技术和结构。

附图说明

图1是一个框图，描述了可以实现本发明的特征的示例无线网格网；

图2描述了根据本发明一个实施例的示例中继分组的内容；

图3、4和5是一个示例网格网的图，描述了根据本发明一个实施例的分布式分组路由方法的操作；

图6是一个流程图，描述了在根据本发明一个实施例的无线网格网的一个节点中处理中继分组的示例方法；

图7是一个框图，描述了根据本发明一个实施例的示例无线节点设备中的功能。

具体实施方式

下面将以举例说明的方式，结合附图对本发明所应用的特定实施例进行详细描述。这些实施例被充分描述，以使得本领域技术人员能够实现本发明。可以理解尽管本发明的各种实施例是不同的，它们不必互相排斥。例如，在不脱离本发明的精神和范围的情况下，这里对于一个实施例所描述的特定特征、结构或特性可以在其他实施例中实现。另外，可以理解，在不脱离本发明的精神和范围的情况下，每个公开的实施例中的单独的元件的位置或排列可以被修改。因此，以下的详细描述不是起限制作用，并且本发明的范围只是由适当解释的附加权利要求以及与这些权利要求的主题等同的全部范围来定义。在附图中，同样的附图标记指示几个附图中同样或相似的功能。

图1是一个框图，描述了可以实现本发明的特征的示例无线网格网10。如图所示，该网格网10包括多个无线节点12、14、16、18、20、22，它们能够通过一条直接无线链路或者一系列节点到节点的链路来互相通信。例如，节点18可以通过节点16、18之间的直接无线链路与节点16无线通信。节点20也可以与节点16通信，但是必须使用多跳节点到节点的链路(例如，一条链路是从节点20到节点22，另一条链路从节点22到节点16；一条链路从节点20到节点18，另一条链路从节点18到节点16；等等)。第一节点的直接无线通信范围内的节点可以称作第一节点的“邻居节点”。这样，参见图1，节点16、20和22是节点18的邻居节点，依此类推。可以通过探测和分析由其他节点发送的信标信号来跟踪一个特定节点的邻居节点。

在本发明的至少一个实施例中，在无线网络的无线接入点之间创建无线网格网，从而允许这些无线接入点互相无线通信。一个或多个无线接入点还可以连接到Internet、公共交换电话网(PSTN)、和/或一些其他外部网络。每个无线接入点可以服务其覆盖范围内的一个或多个无线客户。在一种可能的方式中，作为网格网，与一个无线接入点相关联的客户设备还能够与另一个通信。可以理解，可以替代地使用许多其他的网格网布置。

在一个无线网格网中，网络中的一个或多个功能可能要求该网络中的每个节点与该网络中的所有其他节点传递信息。例如，参见图1，节点12可以向节点14、16、18、20和22传递特定信息。节点14可以向节点12，16，18，20和22传递特定信息，等等。这里将其称为“全部到全部通信”。例如，可以在无线网格网中使用全部到全部通信来支持自配置功能。例如这种类型的信息可以包括节点位置信息、周围噪声信息、信道使用信息、接收信号强度、发送功率、流量特性、和/或其他类型的信息。在至少一个应用中，使用全部到全部通信来支持例如无线网格网中的信道选择功能。也就是说，网络中的每个节点可以向其他节点传送关于网络的多个可用频带中的每个的可用吞吐量的信息。之后该信息可以在网络中被用于在必要时作出信道适配决定。

在至少本发明的一个方面，在无线网格网中通过一个单独的分组从节点到节点流过该网格网，并且在通过期间从每个节点汇聚需要的信息，来实现全部到全部的通信。这里将这个分组称为“中继”分组。每个接收到该中继分组的节点可以读取并存储该汇聚信息，以在执行一个或多个相应功能时使用(例如信道选择，等等)。如果需要，接收节点还可以更新中继分组中的任何对应于该节点的信息。然后接收节点可以将中继分组传送到网格网中的另一个节点，在那里上述过程可以重复。

图2描述了根据本发明的一个实施例的示例中继分组30的内容。如图所示，中继分组30可以包括：发布者标识符32、统一序列号34、汇聚信息36、以及路径信息38。发布者标识符32标识了网格网中最初发布中继分组30的节点，并且统一序列号34标识了中继分组30本身。如将更详细描述的，发布者标识符32和统一序列号34可以被用于防止或终止多个中继分组同时在一个网格网中循环的情况。汇聚信息36是从访问过的各个节点收集的信息，用于传递到网络中的其他节点。一个特定节点首次接收到中继分组30，该节点会将适当的信息输入该分组的汇聚信息部分36。之后，每次该节点接收到该中继分组30，如果需要，该节点都会更新该汇聚信息36。如前所述，汇聚信息部分36的内容将是特定于应用的。

当中继分组30在网格网中传播时，在分组30中为中继分组30访问的每个节点记录一个标识符，按照时间顺序。参见图2，该信息可以作为路径信息38被记录在中继分组30中。在中继分组30循环期间，例如，路径信息38可以被用于为分组30作出路由决定。如将更详细描述的，在某些情况下，可以从中继分组30中去掉路径信息38。可以理解图2的中继分组30只是根据本发明可使用的一种示例的可能的分组配置。可以选择性地采用许多其他中继分组格式。

在至少一个本发明的实施例中，无线网格网中的一个或多个无线节点可以被编程为如果自从该节点接收到一个中继分组开始已经经过了一段预定的时间，就发布一个新的中继分组。例如，这样做是为了保证一直有一个中继分组在循环。当发出了一个新的中继分组，该发布节点会将它的标识符(例如它的地址)插入新的中继分组中，作为发布者标识符。新中继分组的统一序列号可以被设置为当前的序列号加一。采用这种方法，可能出现一种情况，即多个中继分组在一个网格网中同时循环。应该避免这种情况。在至少一个本发明的实施例中，网格网的中继分组中的发布者标识符32和统一序列号34可以被用于防止或终止多个中继分组在该网络中的出现。

在一种方法中，网格网中的每个节点会记录它接收的第一个中继分组的发布者ID和统一序列号。以后每次该节点接收到中继分组，该节点会比较接收的分组信息与记录的发布者ID和统一序列号。如果接收的分组的序列号大于记录的序列号，该节点会记录新的分组的发布者ID和统一序列号，并转发该新的分组。如果接收的分组的序列号小于记录的序列号，该节点会丢弃新接收的分组。如果两个序列号相等，那么该节点会比较接收的中继分组的发布者ID和存储的发布者ID。如果接收的分组的发布者ID小于记录的发布者ID，那么该节点会记录新接收的分组的发布者ID和统一序列号，并转发该新分组。否则，该节点会丢弃接收的中继分组。这会防止两个被不同的节点给与相同的序列号的中继分组都在循环的情况的出现。

在本发明的至少一个实施例中，采用分布式路由技术来路由该中继分组通过网络。也就是说，每个接收到中继分组的节点会基于预定的规则，来确定哪个节点将下一个接收该分组。在一种方法中，分布式路由技术会最终收敛到一条穿过该网格网的节点的单独的路径，该路径使得让该中继分组穿过该网络所需的时间最小化。然而，如果在该网络中发生了一个或多个改变(例如添加或去掉一个或多个节点)，在路由路径中必须做出相应的改变，即使已经发生了收敛。这些路径改变可以是自动发生的。在至少一个实施例中，当一个节点接收到该中继分组，该节点通过确定它的哪一个邻居节点最近最少(least recently)接收该中继分组，来选择下一个节点。如果自从该中继分组上一次被当前节点接收，一个新节点已经被添加到网格网中，并且该新节点是当前节点的一个邻居，那么当前节点会选择该新节点作为下一个节点。如果两个邻居节点都是“最近最少”接收者(例如两个新添加的节点)，那么在这两个平等节点之间随机选择。如果一个接收节点只有一个邻居节点，该接收节点会将该中继分组发送回它所来自的节点。如果遵守了上面的规则，中继分组最终会收敛到一条单独的重复路径。在一种方法中，如果相同路径在路径记录中被重复了两次或更多次，就认为该路径已经收敛了。这种方法通常会导致一条使中继分组穿过整个网格网所需的时间最小化或近似最小化的路径。

图3、4和5是一个示例网格网40的图，描述了上述分布式分组路由方法的操作。如图3所示，示例网格网40包括九个无线节点，42、44、46、48、50、52、54、56、58。42、44、46、48、50、52、54、56、58的每一个节点都由无线链路至少连接到一个邻居节点。这些无线链路在图3中用相应节点之间的直线来表示。在图3中，一个中继分组还没有开始流入该网格网40中。最终，网格网40中的42、44、46、48、50、52、54、56、58中的一个节点可以决定发布一个中继分组。如上所述，在一种可能的方法中，42、44、46、48、50、52、54、56、58中的一个或多个节点会被编程为当经过了一段预定时间而在该节点没有接收到一个中继分组时，发布一个中继分组。还可以替代地使用其他启动技术。

如图4所示，节点42启动一个中继分组的循环。这在图4和5中由节点42中的“1”来表示。由于节点42的邻居节点(即节点44、节点48和节点50)都还没有接收到一个中继分组，随机选择这三个邻居节点中的一个(即节点50)来接收新的中继分组。然后节点42将节点50添加到该中继分组的路径信息中，并将该分组发送到节点50。然后在节点50和每个后续节点(即节点58、52、46、44)重复该过程，直到该中继分组最终被返回到节点42。这时，节点42的最近最少访问的邻居节点是节点48(它还没有被访问)，那么节点48被选为下一个节点。现在参见图5，下一步中继分组被从节点48传递到节点54，然后从节点54到节点56。在节点56，中继分组最近最少访问的邻居节点是节点50。在节点50，中继分组最近最少访问的邻居节点是节点58，依此类推。从这点开始，如果该网络没有添加或去掉节点，该路径将保持一致。

当相同的路径在中继分组的路径信息部分重复了预定次数后(例如在一个实施例中是两次)，就认为该路由过程已经收敛了。当一个节点检测到路由已经收敛，那个节点可以停止写入中继分组的路径信息部分。相反，该节点可以将该路径记录到一个与该节点相关联的本地存储器。当网格网中的所有节点都在本地记录了该路径，路径信息可以从中继分组中删除，以减少网络开销。删除操作可以由一个已经在本地记录了该路径、并且注意到当接着再接收该中继分组、该分组内记录的路径信息没有改变的节点来执行。如果一个新节点被添加到该网格网，或者一个旧节点被去掉，对中继分组的路径信息的记录会再次重新开始。

图6是一个流程图，描述了在根据本发明的一个实施例的无线网格网的一个节点中处理中继分组的示例方法60。首先，该节点接收到中继分组(框62)。如果必要，该节点更新分组中与该节点相关的汇聚信息(框64)。这时该节点还可以使用分组中的汇聚信息来执行它期望的功能(或者将其存储以备后用)。如上所述，中继分组中的汇聚信息的类型依赖于期望的应用。然后该节点会从该中继分组或者本地存储器中读取路径信息(框66)。然后它会判断(1)刚刚将该分组发送给该主体节点的节点是否与之前将该中继分组发送给该主体节点的节点(也就是上次该主体节点接收该中继分组)相同，以及(2)自从上次该主体节点接收到中继分组，该主体节点的邻居是否改变了(框68)。为了判断前一节点是否改变了，该主体节点可以咨询路径信息。为了判断邻居节点是否改变了，主体节点可以比较当前的邻居节点集合与上次接收到中继分组时所存储的集合。

当邻居和前一节点都没有改变时(框68-N)，主体节点会根据所存储的路径信息来选择下一个节点(框70)。然后主体节点会将该中继分组发送到所选择的邻居节点(框72)。如果邻居或者前一节点改变了(框68-Y)，然后主体节点会通过确定最近最少接收到该中继分组的邻居节点来选择下一个接收该中继分组的节点(框74)。可以通过先确定主体节点的邻居节点，然后将它们与存储的路径信息比较，看哪个节点是最近最少出现的，来确定该节点。选择出下一个节点后，在本地和/或中继分组内更新路径信息(框76)。如果对中继分组内的路径信息的记录之前已经停止了(例如因为路由过程已经收敛)，那么在这点会重新开始这样的记录。主体节点会接着将中继分组发送到所选择的邻居节点(框72)。

图7是一个框图，描述了根据本发明的一个实施例的示例无线节点设备80内的功能。如图所示，该无线节点设备80可以包括以下的一个或多个：无线收发器82、分析器84、本地存储器86、汇聚信息更新器88、下一邻居确定单元90、路径信息更新器92、信号汇编单元94、以及分组终止单元96。该无线节点设备中还可以有其他的功能。无线收发器82适于支持与一个或多个远端无线实体(例如与无线网格网中的邻居节点设备)的无线链路。无线收发器82可以耦合到一个或多个天线98，以便于发送和接收无线信号。例如可使用的天线类型包括偶极子、补片(patch)、螺旋天线、天线阵列、和/或其他，包括上面天线的组合。

在节点设备80的操作期间，无线收发器82可能接收到一个正在相应的网格网中循环的中继分组。无线收发器82可以将接收的中继信号发送到分析器84，它对信号进行分析，以分离其中的不同的部分。来自中继分组的汇聚信息可以被传递至该信息所期望的相应应用(例如信道选择应用等等)，或者被存储以备后用。汇聚信息还可以被传递至汇聚信息更新器88，以进行更新。如果这是节点设备80第一次接收到该中继分组，汇聚信息更新器88会将适当的关于节点设备80的信息添加到汇聚信息。如果节点设备80过去已经接收到该中继分组，汇聚信息更新器88会更新对应于该节点设备80的汇聚信息部分(如果需要)。然后汇聚信息会被传递到信号汇编单元94。

分析器84可以将中继分组中的路径信息(若有的话)传递到用于确定下一个接收中继分组的节点的下一邻居确定单元90。下一邻居确定单元90还可以在其输入接收标识节点设备80的当前邻居节点的信息。如上所述，在某些情况下，中继分组中可以没有路径信息。在这些情况中，下一邻居确定单元可以咨询本地存储器86来获得路径信息。任意类型的存储器或存储设备都可以用于本地存储器86(例如一个或多个半导体存储器、一个或多个磁盘驱动器，等等)。下一邻居确定单元90可以首先判断刚刚发送中继分组到节点设备80的节点与上次收到该分组时发送该中继分组到节点设备80的节点是否相同。这个判断是通过分析存储的路径信息做出的。下一部居确定单元90还可以比较节点设备80的当前邻居节点列表和上次接收到中继分组时的当前邻居节点列表(例如它可以存储于存储器86中)。如果邻居节点没有改变并且前一节点相同，下一邻居确定单元90就选择节点设备80之前使用的相同的下一节点(如路径信息中所指示的)。如果一个或多个邻居节点改变了，或者前一节点不同了，下一邻居确定单元90会评估当前邻居节点，以指定最近最少接收中继分组的邻居节点。然后那个节点会被选为下一节点。如果只有一个邻居节点，那么下一邻居节点确定单元90就选择该节点作为下一节点。

下一节点被选出后，路径信息和所选的下一节点的标识可以被传递到路径信息更新器92，它会更新路径信息。路径信息更新器92还可以(可选的)更新存储于存储器86的路径信息。更新的路径信息然后会被传递到信号汇编单元94。

节点设备80中可以包括分组终止单元96，以处理多个中继分组同时在网格网中循环的情况。分组终止单元96可以从分析器84接收最近接收的中继分组的统一序列号和发布者ID。然后分组终止单元96使用这个信息来判断当前的中继分组是否应该继续在网格网中循环，或者被终止。在至少一个实施例中，分组终止单元96可以比较最近接收的中继分组的序列号和所存储的首次接收的中继分组的序列号。如果当前分组的序列号大于记录的序列号，分组终止单元96可以记录新分组的发布者ID和统一序列号，并向信号汇编单元94指示当前中继分组将被转发。分组终止单元96还可以将当前中继分组的统一序列号和发布者ID传递给信号汇编单元，以将这些信息包括在要转发的分组中。另一方面，如果当前分组的序列号小于记录的序列号，分组终止单元96可以指示信号汇编单元94终止该分组(也就是不转发该分组)。如果两个序列号相等，那么分组终止单元96可以比较当前中继分组的发布者ID和存储的发布者ID。如果当前分组的发布者ID小于存储的发布者ID，那么分组终止单元96将记录当前分组的发布者ID和统一序列号，并向信号汇编单元94指示当前中继分组将被转发。否则，分组终止单元96会命令信号汇编单元94终止该分组。可以替代地使用其他分组终止策略。

信号汇编单元94适于汇编当前的中继分组，以发送到下一节点。信号汇编单元94可以提取更新的汇聚信息、更新的路径信息、统一序列号、以及发布者ID，并使用它们来以适当格式重新汇编中继分组。如上所述，在至少一个实施例中，分组终止单元96可以命令信号汇编单元94终止一个特定的分组，以防止多个中继分组在网格网中循环。如果之前已经停止了将路径信息写入中继分组，那么在重新汇编期间，信号汇编单元94不会把更新的路径信息添加到中继分组中。其他类型的信息也可以(或者替代地)添加到中继分组中。汇编过的中继分组接着被传递到无线收发器82，它将该分组发送到下一节点。

本发明的技术和结构可以用任意的各种不同形式来实现。例如，本发明的特征可以体现在用作无线网格网的一个节点的任何类型的部件、设备和系统中。例如，一些这样的部件、设备和系统包括无线接入点、蜂窝基站、蜂窝电话和其他手持无线通信器、具有无线能力的个人数字助理、膝上电脑、掌上电脑、以及具有无线能力的平板计算机、寻呼机、卫星通信器、具有无线能力的照相机、具有无线能力的音频/视频设备、无线网络接口卡(NIC)以及其他网络接口结构、集成电路、和/或其他。本发明的特征还可以体现为存储在机器可读介质上和/或其他格式中的指令和/或数据结构。可以采用的不同类型的机器可读介质的例子包括软盘、硬盘、光盘、压缩盘只读存储器(CD-ROM)、磁光盘、只读存储器(ROM)、随机访问存储器(RAM)、可擦除可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)、磁卡或光卡、闪存、和/或其他类型的适于存储电子指令或数据的介质。在至少一种形式中，本发明体现为一组在载波上调制的用于在传输介质上传输的指令。

应该理解这里的框图中所描述的单独的框本质上可以是功能性的，而不必对应于分立的硬件元件。例如，在至少一个实施例中，框图中的两个或更多个框是在单个(或多个)数字处理设备中的软件中实现的。例如数字处理设备可以包括通用微处理器、数字信号处理器(DSP)、精简指令集计算机(RISC)、复杂指令集计算机(CISC)、场可编程门阵列(FPGA)、专用集成电路(ASIC)、和/或其他，包括上述的组合。可以采用硬件、软件、固件、以及混合的实现方式。

在前面的详细描述中，为了把公开联为一个整体，在一个或多个单独的实施例中组合了本发明的各种特征。这种公开方法不能解释为意图反映所要求保护的发明需要比每个权利要求中所明确表述的特征更多的特征。而是如下面的权利要求所反映的，创造性的方面存在于每个公开的实施例的少于全部的特征中。

尽管这里结合特定的实施例对本发明进行了描述，本领域的技术人员可以理解，在不脱离本发明精神和范围的情况下，本发明可以进行各种修改和变型。这样的修改和变型都被认为处于本发明和附加的权利要求的范围中。