基于有向非循环图成员关系的用于路径计算的控制集标识

技术领域

本公开一般涉及对具有大量网络设备的设备网络(例如，具有成千 (上万)个传感器设备的低功率损耗网络(LLN))中的网络设备之间的 时隙化信道跳跃(channelhopping)路由进行优化的路径计算元件 (PCE)。

背景技术

这部分描述了可以被采用的方法，但并不一定是此前已经被设想或采 用的方法。因此，除非明确指出，否则这部分所描述的任何方法均不是本 申请的权利要求的现有技术，并且这部分所描述的任何方法不因为被包括 在这部分中而被承认为现有技术。

低功率和损耗网络(LLN)允许大量(例如，成千上万)的资源受限 设备被互联以形成无线网状网。互联网工程任务组(IETF)已经提出了使 用基于IEEE802.15.4e的时隙化信道跳跃(TSCH)来提供IPv6路由的路 由协议(“6TiSCH”)。尽管诸如路径计算实体(PCE)之类的集中式实 体可以被用于小数目的不同网络设备之间的路由计算，但是PCE计算 TSCH调度的复杂度将网络中的网络设备的数目限制为少于一百(100)个 网络设备，或者更典型地不多于约三十(30)个网络设备，这是因为PCE 不能维持较大数目的网络设备之间的对等。因此，PCE不能计算包含较大 数目的网络设备的数据网络中的网络设备之间的6TiSCH路由。

附图说明

参考附图，其中具有相同参考数字标号的元素自始至终表示相似的元 素，并且其中：

图1根据示例性实施例示出具有用于将属于有向非循环图的网络设备 归类为属于用于生成网络内的经优化的路由的控制集(dominatingset)的 装置的示例性系统；

图2根据示例性实施例示出具有图1的网络内的经优化的路由的网络 设备的示例性控制集；

图3根据示例性实施例示出图1的网络设备或路径计算设备中的任何 一个的示例性实施方式；

图4根据示例性实施例示出图1的网络设备和路径计算设备的示例性 方法，该方法导致生成低功率损耗网络内的经优化的路由。

具体实施方式

概述

在一个实施例中，方法包括：路径计算设备接收来自成员网络设备的 设备信息，每一个成员网络设备属于到低功率损耗网络中的目的地的有向 非循环图；以及路径计算设备将属于有向非循环图的每一个成员网络设备 归类为属于用于生成不同于任何有向非循环图的经优化的路由的控制集， 该经优化的路由用于到达该控制集中的任何一个成员网络设备。

在另一实施例中，装置包括网络接口电路和处理器电路。网络接口电 路被配置为接收来自成员网络设备的设备信息，每一个成员网络设备属于 到低功率损耗网络中的目的地的有向非循环图。处理器电路被配置为将属 于有向非循环图的每一个成员网络设备归类为属于用于生成不同于任何有 向非循环图的经优化的路由的控制集，以到达该控制集中的任何一个成员 网络设备。

在另一实施例中，方法包括：低功率损耗网络中的网络设备加入到目 的地的有向非循环图；以及网络设备响应于加入有向非循环图，向路径计 算设备发送设备信息，使该路径计算设备能够将网络设备添加至用于由路 径计算设备生成用于到达低功率损耗网络中的任何一个网络设备的经优化 的路由的网络设备的控制集，该经优化的路由不同于任何有向非循环图。

详细描述

图1根据示例性实施例示出示例性系统10，该示例性系统10具有用 于将属于有向非循环图(DAG)16的网络设备14归类为属于用于生成网 络18内的经优化的路由(图2中的30)的控制集(图2中的28)。

具体实施例基于使用作为DAG16的成员的网络设备14，使能对要被 路径计算元件(PCE)设备12用于生成低功率损耗网络18(其可包含成 千上万的网络设备14、20)中的经优化的时隙化信道映射路由30的网络 设备16的有效识别。在网络18中使用时隙化信道映射路由(例如，根据 6TiSCH)需要沿着该时隙化信道映射路由的所有网络设备14在多个不同 的频率信道上是时间同步的，以建立用于传输数据流的确定性网络。“确 定性网络”是可在需要网络资源的精确时间处保证网络资源(例如，数据 缓冲器、处理器容量、网络介质访问等等)的分配的数据网络。因此，所 标识的需要经由网络设备“B”14从网络设备“A”14发送至网络设备 “C”14的数据流的数据分组可以被分配有规定的6TiSCH时隙化信道映 射路由(或“路径”)，该路由具有这样的顺序：在时隙“t0”处网络设 备“A”在频率信道“10”上将数据分组发送至网络设备“B”，随后在时 隙“t1”处网络设备“B”在频率信道“3”上将数据分组发送至网络设备 “C”。术语“路径”被定义为由时隙序列同步的、沿着多跳路径映射的 频率信道的确定性序列，其中“时隙序列”可以包括一个或多个用于重传 尝试的重试缝隙(例如，每一跳对应于一个重试缝隙)，并且多调路径可 以根据不同的拓扑结构来实施，例如美国专利公告号No.2012/0300668中 所述的弧形链和帧复制。

从前述内容可以明显得知，计算确定性网络中的时隙化信道映射路由 30的相对复杂度对PCE设备12是不可伸缩的，特别是因为许多优化限制 (例如，延迟、吞吐量、最小误差率等等)可以导致NP完全问题(不确 定性的多项式时间)，该NP完全问题导致随着网络设备14、20的数量增 加，找到针对增加数量的受限路径的可接受方案的计算成本呈指数增长。

具体实施例基于将任何属于到规定目的地的有向非循环图16的成员 网络设备14归类为属于用于计算经优化的时隙化信道映射路由30的网络 设备的控制集(DS)28，使能对要被用于计算较低功率损耗网络18中的 经优化的时隙化信道映射路由30的网络设备的有效识别。“控制集”是 网络中被连接的网络设备的可识别集合，其中网络中的任何网络设备是控 制集的成员14，或经由数据链路22与控制集的成员14(即“成员网络设 备”)距离仅仅一跳的“叶子网络设备”20。本文(以及权利要求)中所 使用的术语“叶子网络设备”被定义为这样的网络设备：(1)附连到有 向循环图16的成员网络设备14；和(2)具有任何与之附连的“子”网络 设备。换句话说，如下面针对操作54所述的，在另一网络设备(例如， “Y”)附连到网络设备(例如，“X”)的情况下，网络设备“X的状态 可以从“叶子网络设备”改变为“成员网络设备”。因此，每一个叶子网 络设备20经由相应的数据链路22是一个或多个成员网络设备14的邻居， 并且每一个成员设备14可以提供到网络18中的任何其他网络设备14、20 的可达性。图1示出一般简化的用于与有向非循环图16通信的叶子网络 设备20的数据链路22：将很容易理解的是实际的数据链路22将在叶子网 络设备20和一个或多个成员网络设备14之间。

另外，具体实施例响应于创建或加入到目的地(例如，骨干路由器) 24的DAG16的任何网络设备14加入DAG16，使能网络设备14(例如， 经由有线数据链路32)向PCE设备12发送设备信息，该设备信息包括唯 一设备标识符和关于成员网络设备14所使用的用于连接网络18中的任何 其他网络设备14、20的任何数据链路22、26的设备链路信息。例如RFC 6550、美国公告号No.2012/0300668和/或美国专利号No.7,860,025中所 述，每一个网络设备14可以根据所规定的限制或参数独立决定创建和/或 加入有向非循环图(DAG)16，该限制或参数根据规定的参数使能对 DAG16的优化：根据规定的参数对DAG16的优化在RFC6550中也被称 作“目标函数”。由于成员网络设备14基于成员网络设备14之间的分布 式计算建立DAG16，对成员网络设备14和这些成员网络设备14所提供 的关联数据链路22、26的标识使能PCE12将每一个成员网络设备14归 类为属于用于生成经优化的路由30的控制集28。

因此，有向非循环图16的成员网络设备14表示覆盖链路层网状网络 的初步优化的拓扑结构(根据所规定的目标函数)，该链路层网状网络是 网络18中的网络设备14、20的总数的子集，其中成员网络设备14的总数 可以比叶子网络设备20的总数小一个或多个数量级。

因此，PCE设备12可以基于成员网络设备14的明显小得多的子集， 通过对低功率损耗网络18的进一步优化来生成经优化的路由30，以保证 由PCE设备12生成经优化的路由30的可伸缩性。如图1和图2所示，经 优化的路由30与DAG16不同，并且经优化的路由30使能网络设备14、 20在低功率损耗网络18内发送和接收数据流。来自低功率损耗网络18的 数据流还可以经由网络路由器设备36和广域网(例如，互联网)38被发 送至或发送自远程计算设备34。

图3是根据示例性实施例示出PCE设备12、网络设备14、20和/或路 由器设备24或36中的任何一个的示例性实施方式的图示。图3的装置 (例如，12、14、20、24和/或36)是这样的物理机器(即，硬件设备)： 其被配置用于经由数据网络18实现与其他物理机器的通信。在下面更加 详细地描述中，图3的装置(例如，12、14、20、24和/或36)可以包括 一个或多个网络接口电路40、一个或多个处理器电路42以及一个或多个 存储器电路44。

任何被公开的电路(包括网络接口电路40、处理器电路42、存储器 电路44及它们的关联组件)可以以多种方式来实现。被公开的电路的示 例性实施方式包括被实现在逻辑阵列(例如，可编程逻辑阵列(PLA)、 现场可编程门阵列(FPGA))中的硬件逻辑或者由掩膜编程集成电路 (例如，专用集成电路(ASIC))实现的硬件逻辑。这些电路中的任何一 个还可以使用基于软件的可执行资源来实现，该基于软件的可执行资源由 相应的内部处理器电路(例如，微处理器电路(未示出))执行，并且使 用一个或多个集成电路来实现，其中对存储在内部存储器电路(例如，在 存储器电路44中)中的可执行代码的执行导致实现处理器电路的(一个 或多个)集成电路将应用状态变量存储在处理器存储器中，从而创建执行 本文所述的电路的操作的可执行应用资源(例如，应用实例)。因此，本 说明书对术语“电路”的使用指的是使用一个或多个集成电路实现的并且 包括用于执行所述操作的逻辑的基于硬件的电路，或者包括(使用一个或 多个集成电路实现的)处理器电路的基于软件的电路，该处理器电路包括 保留部分的处理器存储器以用于存储由处理器电路执行可执行代码来改变 的应用状态数据和应用变量。存储器电路44可以例如使用非易失性存储 器(例如，可编程只读存储器(PROM)或EPROM))和/或易失性存储 器(例如，DRAM)等等来实现。

另外，任何对“输出消息”或“输出分组”(或诸如此类)的引用可 以基于创建采用数据结构形式的消息/分组并且将该数据结构存储在所公开 的装置中的非暂态有形存储器介质(例如，在传输缓冲器中)中来实现。 任何对“输出消息”或“输出分组”(或诸如此类)的引用还可以包括通 过通信介质(例如，依情况而定的有线或无线链路)电发送(例如，经由 依情况而定的有线电流或无线电场)存储在非暂态有形存储器介质中的消 息/分组至另一网络设备(依情况而定也可以使用光传输)。类似地，任何 对“接收消息”或“接收分组”(或诸如此类)的引用可以基于所公开的 装置检测通信介质上的消息/分组的电(或光)传输，并且将检测到的传输 存储为所公开的装置中的非暂态有形存储器介质中(例如，在接收缓冲器 中)的数据结构来实现。还应当注意的是存储器电路23可以由存储器电 路42动态地实现，例如基于处理器电路42执行的存储器地址分配和划分 来实现。

图4根据示例性实施例示出图1和2的路径计算设备12和网络设备 14导致生成低功率损耗网络18内的经优化的路由30的示例性方法。针对 图1-4中的任意一者所述的操作可以被实施为存储在计算机或机器可读非 暂态有形存储介质(例如，软盘、硬盘、ROM、EEPROM、非易失性 RAM、CD-ROM等等)上的可执行代码，这些操作基于使用一个或多个 集成电路实施的处理器电路对代码的执行来完成；本文所述的操作还可以 被实施为可执行逻辑，其被编码在用于执行的一个或多个非暂态有形介质 (例如，可编程逻辑阵列或设备、现场可编程门阵列、可编程阵列逻辑、 专用集成电路等等)中。

此外，针对图1-4中的任意一者所述的操作可以以任意适当的顺序来 执行，或者至少部分操作被并行执行。对本文所述的操作的执行仅通过示 例的方式示出；由此，这些操作不一定需要被如本文所述的基于机器的硬 件组件来执行；相反，其他基于机器的硬件组件也可以被用于以任意适当 的顺序来执行所公开的操作，或并行执行至少部分操作。

现在参考图4的操作50，无线网状网18中的每一个网络设备14、20 的网络接口电路40可以建立一个或多个无线数据链路，如图1和2中所示 的22、26、和/或46。因此，每一个网络设备14、20具有到另一网络设备 的至少一个链路层连接以形成网状网络。

在操作52中，网络18中的网络设备的子集的处理器电路42可以例如 例如根据RFC6550和/或美国专利号No.7,860,025，例如基于交换邻居通 告消息来决定加入和/或创建有向非循环图16，其中这些网络设备中的一 个网络设备通告到目的地根24的可达性。如图1所示，加入朝向目的地 24的有向非循环图(DAG)16的每一个网络设备14可以根据规定的目标 函数选择性地选出它在有向非循环图16内的连接。

某些网络设备20的处理器电路42可以在操作54中决定附连至经由成 员网络设备14所提供的设备链路22与之距离一跳远的相邻成员网络设备 14。因此，在一个实施例中，每一个网络设备可以决定是否作为成员网络 设备14加入有向非循环图16，或者作为叶子网络设备20附连到相邻成员 网络设备14。

在操作54中，叶子网络设备20还可以检测它的状态(例如，执行操 作52)改变为成员网络设备14。例如，叶子网络设备“X”20可以例如， 通过输出如RFC6550所述的DODAG信息对象(DIO)对其已经加入的 DODAG16进行通告。响应于叶子网络设备“X”20检测到另一叶子网络 设备“Y”20已经与其附连以便于加入被通告的DODAG16(例如，基于 叶子网络设备“Y”20向网络设备“X”发送如RFC6550中的目的地通告 对象(DIO)以请求单播缝隙的调度)，网络设备“X”20可以检测到它 已经变成成员网络设备14，并且作为响应执行适当的成员网络设备操作， 如下所述。

例如，如果成员网络设备14检测到没有其他网络设备14、20与其附 连，那么它还可以检测到它的状态改变为叶子网络设备20。因此，“成员 网络设备”14或“叶子网络设备”20的名称可以基于DAG16的拓扑内的 网络设备的附连状态而改变。

如前所述，有向非循环图16的形成通常导致明显少得多的成员网络 设备14和较大数量的叶子网络设备20。

在操作56中，每一个成员网络设备14的处理器电路42可以(通过其 网络接口电路40)例如经由相应的DODAG16向PCE设备12(即，路径 计算设备12)发送设备信息。每一个成员网络设备14的处理器电路42可 以响应于加入DODAG16，和/或响应于所检测的邻居的改变，和/或响应 于链路质量(例如，链路22和/或26中的一者)的改变发送设备信息。示 例性设备信息可以包括设备唯一标识符(例如，MAC地址)、DODAG16 的标识符(例如，目的地根24的网络地址)和成员网络设备14的每一条 链路的设备链路信息。示例性设备链路信息可以包括相邻网络设备14或 20的设备标识符、对相邻网络设备类型的标识(即，相邻设备是成员网络 设备14还是叶子网络设备20)。示例性设备链路信息还可以包括链路质 量信息，例如RFC6551中所述的链路度量、ETX度量(所期望的传输次 数)、所接收的信号强度指示符(RSSI)、链路质量指示符(LQI)等等。

在操作56中，每一个成员网络设备14的处理器电路42还可以转发叶 子网络设备20所使用的邻居链路46的链路信息，叶子网络设备20将与邻 居链路46相关联的链路质量信息发送至成员网络设备14以提供叶子网络 设备20的可达性。如下所述，在优化时隙化信道映射路由30期间，PCE 设备12可以例如，基于做出将叶子网络设备(图2中的14’)选择性地添 加至控制集28以便于填补控制集的网络设备14之间的间隙的决定来使用 邻居链路46的链路信息。

因此，成员网络设备14可以向同一RPL实例(如RFC6550所述)内 的所有邻居设备通告，无论这些邻居设备是否共享相同的DODAG标识符 (也就是说，无论邻居设备是否属于另一DODAG)。如下面针对操作62 所描述的，无论邻居设备是否共享相同的DODAG标识符，该邻居信息基 于将来自不同DAG16的成员网络设备14归类到相同的控制集28中，使 能跨越多个DAG16创建TSCH路由。

在操作60中，PCE设备12的网络接口电路40被配置用于经由数据链 路32和网关24接收操作56中的成员网络设备14发送的设备信息。如针 对操作56所述的，设备信息可以标识成员网络设备14、叶子网络设备20 和关联的数据链路22、26和46。PCE设备12的处理器电路42被配置为 在操作60中将每一个成员网络设备14归类为属于在操作62中被PCE设 备12的处理器电路42用于生成经优化的时隙化信道(TSCH)映射路由 30的控制集28。如图1和2所示，经优化的路由30不同于DAG16。

如操作60所示，PCE设备12的处理器电路42还被配置用于从控制集 28中排除被标识为不具有与之附连以到达网络18中的有向非循环图16的 任何子网络设备的任何网络设备，也就是叶子网络设备20。因此，PCE设 备12可以以可伸缩的方式，通过仅使用成员网络设备14而排除任何叶子 网络设备20来生成经优化的路由30。如操作62所示，PCE设备12可以 将来自不同的DODAG16(即具有不同目的地28的DAG)的成员网络设 备14归类(即，添加)到控制集28。因此，由PCE设备12生成的经优 化的路由30可以合并来自不同DODAG16的成员网络设备14。

PCE设备12的处理器电路42还可以被配置为响应于在操作64中检测 到控制集的网络设备14之间存在间隙，在操作66中将叶子网络设备(图 2中的14’)选择性地添加到控制集28。类似地，PCE设备12的处理器电 路42可以被配置为在操作68中从控制集28选择性地删除在任何经优化的 路由30中均未被使用的网络设备14。

在操作70中，每一个成员网络设备14可以接收来自PCE设备12的、 用于到达网络18中的控制集28(和附连的叶子网络设备20)的各个目的 地的一个或多个时隙化信道映射路由。因此，操作72中的每一个网络设 备14可以根据PCE设备12生成的TSCH路由30在低功率损耗网络18中 路由数据流量。

根据示例性实施例，PCE设备12可以基于根据网络设备的子集是有 向非循环图的成员网络设备仅将网络设备的子集归类为控制集来生成针对 具有成千上万个网络设备的低功率损耗网络的时隙化信道映射路由。对来 自有向非循环图的成员网络设备的使用和对叶子网络设备的谨慎排除使对 例如具有成千上万个网络设备的传感器网络之类的低功率损耗网络的优化 成为可能。

尽管已经结合目前被认为是用来实现所附权利要求规定的主题的最佳 模式对本公开的示例性实施例进行了描述，但是应当理解的是示例性实施 例仅仅是说明性的，并非限制所附权利要求规定的主题。