为了分组的无环路路由避开智能测量仪网络中的破损链路

摘要

本发明总体上涉及无线传感器网络中的分组路由，具体地涉及在具有破损链路的智能测量仪网络中路由分组。通过将传感器网络表示为DODAG，避开网络中的破损链路。与各节点关联的秩定义各节点相对于其它节点的位置，秩是真分数形式，各节点的秩绝不增大以能够进行无环路路由。

说明书

技术领域

本发明总体上涉及无线传感器网络中分组的路由，具体地，涉及在具有破损链路 的智能测量仪网络中路由分组。

背景技术

智能测量仪监控消费者对设施(例如，电、热、气和水)的使用。通常，智能测 量仪经由网络或系统网路与设施供应方进行通信，所述网络或系统网络或许可包括数 百万的智能测量仪。智能测量仪可打开或关闭设施，记录使用信息，检测服务断供， 未经授权的使用，控制设施消耗，管理支付。

智能测量仪必须可靠且安全地与设施供应方通信。可使用有线或无线网状网络。 已知多个协议，例如，用于光学通信的ANSI C12.18、ANSI C12.19和ANSI C12.21 以及IEEE 802.15.4、IEEE P1901.2和802.11。欧洲联盟使用IEC 61107和IEC 62056。 在日本，在推进智能测量以及公共设施和私人设施中涉及能量节约。

智能测量仪可经由一个或更多个集线器连接到设施供应方。集线器从智能测量仪 接收测量信息，并且将该信息转送到供应方，以控制或监控设施。集线器还可以出于 管理目的将控制分组发送到智能测量仪。

智能测量仪可装配有低功耗有损收发器(诸如，ZigBee无线电)，并且被部署在 相对大的几何区域(例如，整个国家)中。因此，智能测量仪和集线器形成大规模无 线网络，在该网络中，集线器维持网络。

在这种大规模无线网络中，数据分组必须通过多跳通信从源节点(源)中继到目 的节点(目的地)，除非源节点和目的节点是一跳邻居节点。因此，分组的最佳路由 是头等重要的，因为对于测量信息和控制分组发送二者而言，网络都需要高可靠性和 低延迟。

移动自组织网络(ad-hoc network)和无线传感器网络中的多种路由方法是已知 的。然而，大部分方法是针对相对小网络中的点对点通信设计的，因此并不适合其中 只有几个专用数据集线器的智能测量仪网络。

一种路由方法是低功耗有损网络的路由协议(RPL)，该协议是由互联网工程任 务组(IETF)开发的。RPL是针对大规模低功耗有损网络(诸如，智能测量仪网络) 设计的。

在RPL中，节点被组织成一个或更多个面向目的地的有向无环图(DODAG)。 在DODAG内，单个目的节点是DODAG的根，DODAG根节点(集线器)收集网络 中生成的信息，并且在必要时将信息路由到网络之外。RPL使用DODAG信息对象 (DIO)分组构造和维持DODAG，DIO分组指定由DODAG根处的策略构成并且受 该策略控制的必要参数。

“秩”是用于DODAG构造和维持的DIO分组中的参数之一。节点的秩定义该 节点关于DODAG根相对于其它节点的位置。各节点保持其自身的秩。在DODAG 中的所有节点中，DODAG根节点具有最低的秩。节点基于父子关系保持它们的秩， 在父子关系中，子节点必须具有严格大于其父节点的所有秩的秩。DODAG根节点没 有父节点。

节点可从同一DODAG内的邻居节点接收多个DIO分组。

为了加入DODAG，节点选择DIO分组发送器的子集作为其父节点，并且使用 目标(成本)函数确定其秩。在它的所有父节点之中，节点选择一个父节点作为它的 优选父节点，该优选父节点被用作沿着通向集线器的向上路线的下一跳节点。

假设智能测量仪不受能量限制。替代地，电测量仪具有硬件和通信能力限制，这 些限制主要是由成本其次是由功耗确定的。结果，就存储器大小、功耗和通信能力而 言，部署可显著变化。出于这个原因，RPL存储或非存储模式的使用是部署特定的。

当智能测量仪是存储器受限制的并且不能足够地存储支持逐跳路由所需的路由 表时，优选的是RPL非存储模式。如果节点能够存储此路由表，则使用存储模式会 造成降低的开销和路由修复延迟。然而，在高密度环境中，存储路线会具有挑战性。

因此，通过DIO分组中的操作模式(MOP)确定向下路线的RPL支持。MOP 是由DODAG根构成的，不能被其它节点改变。

MOP具有三个选择，使得RPL不能允许在存储模式下向下路由或者支持向下路 线或者在非存储模式下支持向下路线，在所述存储模式下，向下路线使用的是网络内 路由表，在所述非存储模式下，向下路线使用的是从DODAG根开始的源路由。

在PRL中关键的是有向无环结构。只要任何节点的秩严格大于其父节点的所有 秩，就保证无环结构。节点减小其秩是安全的，只要其新秩保持大于其父节点的所有 秩即可。然而，增大秩可造成DODAG内的路由环路。

在传统网络中，破损链路会造成环路。在检测到破损链路之后，节点可通告无限 大的秩。如果这个无限大的秩通告丢失，则其它节点接收不到该通告并且分组通过环 路无限地循环。

尽管RPL提供了解决环路的机制，但已知的是，该机制会造成甚至比路由环路 本身更大的问题。

因此，期望的是，提供一种用于具有破损链路的智能测量仪网络中的无环路路由 的秩计算方法。还期望的是，提供一种没有形成任何环路的本地DODAG修复方法。

发明内容

本发明的实施方式提供了一种用于节点的智能测量仪网络中的无环路路由的秩 计算方法。各节点具有即使检测到破损链路也绝不增大的秩。结果，本发明的秩计算 方法防止出现环路。

用本发明的秩计算方法，节点选择父节点，使得不形成环路。

描述了使用具有一个集线器的网络的实施方式。然而，实施方式可应用于具有多 个集线器的网络。

所述方法将秩定义为分子小于分母的真分数。所述方法在更新期间绝不增大节点 的秩，即使检测到破损链路。

本发明提供了一种在不造成环路的情况下修复本地面向目的地的有向无环图 (DODAG)的方法。修复基本上避开了破损链路。

修复方法应用于RPL的存储模式和非存储模式二者。基于本发明的秩计算方法， 节点可发现通向DODAG根的多个未破损路由链路。

附图说明

[图1]图1是通过本发明的实施方式避开的智能测量仪网络的一部分中的路由环 路的示意图；

[图2]图2是本发明的实施方式在其中进行操作的智能测量仪网络的示意图；

[图3A]图3A是根据本发明的实施方式的经修改DIO分组的格式的框图；

[图3B]图3B是根据本发明的实施方式的DODAG修复请求分组的格式的框图；

[图3C]图3C是根据本发明的实施方式的DODAG修复应答分组的格式的框图；

[图4]图4是根据本发明的实施方式的DODAG构造过程的流程图；

[图5]图5是根据本发明的实施方式的DODAG构造的示意图；

[图6A]图6A是根据本发明的实施方式的存储模式下的上行链路破损处理过程的 流程图；

[图6B]图6B是根据本发明的实施方式的非存储模式下的上行链路破损处理过程 的流程图；

[图7A]图7A是根据本发明的实施方式的存储模式下处理DODAG修复请求分组 的流程图；

[图7B]图7B是根据本发明的实施方式的非存储模式下处理DODAG修复请求分 组的流程图；

[图8A]图8A是根据本发明的实施方式的存储模式下处理DODAG修复应答分组 的流程图；

[图8B]图8B是根据本发明的实施方式的非存储模式下处理DODAG修复应答分 组的流程图；

[图9]图9是根据本发明的实施方式的本地DODAG修复的示意图；

[图10]图10是根据本发明的实施方式的避开破损链路的示意图。

具体实施方式

图1示出具有路由环路的智能测量仪网络的一部分。该部分具有节点1-7和集线 器C，这些节点具有关联的、用节点上方的斜体字示出的秩r。节点之间的链路用有 向边(箭头)表示。链路101通向优选的父节点，节点1和集线器之间的链路102 破损，链路103是通向因为破损链路而造成环路的优选的父节点的链路。

注意的是，这里，秩是整数。根据本发明的方法可以将整数变成在检测到破损链 路时大小绝不增大的真分数。

因为破损链路，节点1可通过通告无限大的秩来“影响(poison)”破损链路。 如果这个无限大的秩的通告丢失，则节点2和3接收不到该通告。结果，节点2仍然 以节点1作为它优选的父节点。接着，节点3通告它的秩具有3的值，节点1从节点 3接收通告，选择节点3作为其父节点，从而造成无限地通过节点1-3-2-1的环路。

本发明的目的是防止由于如图1中所示的破损链路造成网络中出现环路。

因此，采用本发明的秩计算方法，图1中的节点1没有选择节点2或节点3作为 其父节点。替代地，节点1选择节点4作为其父，使得没有造成环路。

图2示出在智能测量仪网络中使用本发明的实施方式用于无环路路由的节点的 智能测量仪网络，其中，节点绝不增大其秩。

该网络包括智能测量仪M和集线器C。节点通过有线或无线链路彼此连接。有 线链路可以是经由电力线。该方法可应用于任何已知的无线通信方法。

集线器与设施供应方P通信。节点和链路形成网状网络。各节点具有关联的秩r。

在智能测量仪网络中，各智能测量仪周期性收集顾客的信息并且将信息发送到一 个或更多个集线器。集线器负责接收信息并且将信息转送到供应方，以控制或监控智 能测量仪。信息以数据分组的形式传送，以下对此进行更详细的描述。

集线器还可出于管理目的将控制分组发送到智能测量仪。智能测量仪通常装配有 低功耗有损收发器(诸如，ZigBee无线电)并且部署在相对大的几何区域中。因此， 智能测量仪和集线器形成大规模网状无线网络，在该网络中，集线器维持整个网络。

在这样的大规模无线网络中，分组必须通过多跳通信从源节点(源)中继到目的 节点(目的地)，除非源和目的地是一跳邻居节点。对于测量和控制信息二者而言， 路由都需要高可靠性和低延迟。

在本发明的实施方式中，用面向目的地的有向无环图(DODAG)表示网络。在 DODAG中，智能测量仪用节点表示，测量仪之间的通信链路用有向边表示。节点(智 能测量仪)具有关联的秩r。

集线器是DODAG中的根。诸如i、j、k、l等斜体符号用于表示智能测量仪节点 的标识符(ID)并且C表示集线器的标识符。节点可用(例如)其IPv6地址来标识， 在网络中，IPv6地址是唯一的。

表1示出本发明的实施方式使用的节点i的状态参数。

[表1]

各智能测量仪节点i可保持父集P(i)中的多个父。对于各父节点p∈P(i)，节点 i还记录秩R(p)。在任意时间，节点i保持其父集P(i)，使得对于任何节点p∈P(i)， R(i)>R(p)。对于集线器节点C，P(C)一直为空，即，|P(C)|＝0。

分组类型

在低功耗有损网络(RPL)的路由协议下，定义多种类型的分组。

根据本发明的实施方式，DODAG信息对象(DIO)分组的格式被修改成适应真 分数秩定义。

如图3A至图3C中示出的，修改DIO分组，出于本地DODAG修复目的，定义 两个新的分组。新分组被定义为图3B的DODAG修复请求(DR-REQ)分组和图3C 的DODAG修复应答(DR-REP)分组。

如这里定义的，修复没有实际上物理地修复可以是暂态的或永久的破损链路。相 反，修复是DODAG上的实行体(performer)，使得避开破损链路。

在图3A中示出修改后的DIO分组。在DIO分组中，秩R从无符号整数(如现 有技术中的一样)被修改成通过一对无符号整数(m,n)定义的真分数，即，在 真分数中，分子小于分母。在DIO分组中增加代价c。代价c是从节点到DODAG根 的链路的最小代价。

图3B示出DR-REQ分组。DR-REQ分组包括ID-Q、R-Q、VN-Q、SN-Q、NL-Q 和其它选择。ID-Q是DR-REQ分组生成器的标识符，R-Q是DR-REQ分组生成器的 秩，VN-Q是DR-REQ分组生成器的DODAG版本号，SN-Q是DR-REQ分组生成器 的DODAG修复序号，NL-Q是DR-REQ分组历经的节点列表，NL-Q只在非存储模 式下存在。

图3C示出DR-REP分组。DR-REP分组包括ID-Q、R-P、c、VN-P、SN-Q、D、 R-Q、NL-Q和其它选择。ID-Q是DR-REQ分组生成器的标识符或DR-REP分组的目 的节点标识符，如果DR-REP分组向上行进，则R-P是DR-REP分组生成器的秩， 并且如果DR-REP分组向下行进，则R-P是发送节点的秩，c是从DR-REP分组发送 节点到DODAG根的链路的最小代价，VN-P是DR-REP分组生成器的DODAG版本 号，SN-Q是DR-REQ分组生成器的DODAG修复序号，D指示DR-REP分组行进方 向，R-Q是DR-REQ分组生成器的秩，NL-P是DR-REQ分组中的NL-Q和向上的 DR-REP分组历经的节点列表的组合。D、R-Q和NL-P只在非存储模式下存在。

秩定义和秩分割运算

对于节点i，秩R(i)被定义为真分数，使得R(i)＝m/n，其中，0≤m≤n，m和n是 整数并且0<n。节点i的秩被表示为R(i)＝(m,n)。

对于任何两个秩R(i)＝(m,n)和R(j)＝(p,q)，秩分割运算被定义为 sp(R(i),R(j))＝sp((m,n),(p,q))＝(m+p)/(n+q)。

分割运算sp(R(i),R(j))分割秩(m,n)和(p,q)，产生新的秩(m+p)/(n+q)。

如果m/n<p/q，则m/n<(m+p)/(n+q)<p/q。

也就是说，分割运算sp(R(i),R(j))产生秩R(i)和秩R(j)之间的新秩。如果该秩是可 约的，则通过将分子和分母都除以最大公约数来约分。

本发明的秩定义的优点是基于下面的实现。在任何两个真分数m/n和p/q之间存 在无限数量的真分数。通过利用真分数的这个特征，本发明的秩计算方法保证即使当 检测到破损链路时，节点的秩也绝不增大。也就是说，如果当前秩是(m,n)＝m/n，则 新秩是(p,q)＝p/q，并且p/q小于m/n。

如果真分数形式的秩不能增大，则可确保无环路路由。

初始地，对于集线器节点C，c(C)＝0，VN(C)＝δ>0，|P(C)|＝0并且秩R(C)可 以是使得R(C)<(1,1)的任何真分数。例如，使用R(C)＝(0,1)＝0/1。对于智能测量仪 节点i，c(i)＝∞，VN(i)＝0，T_p＝预定值，DR-SN(i)＝1，|P(i)|＝0并且秩R(i)可以是使 得R(C)<R(i)≤(1,1)的任何真分数。例如，使用R(i)＝(1,1)＝1/1。

DODAG构造

通过使用DIO分组构造DODAG。使用涓流式(trickle)定时器发送DIO分组。 涓流式定时使得有损共享介质(例如，低功耗有损网络)中的节点以能量有效率和可 扩展方式交换信息。以毫秒解决不一致性。当节点同意时，通信速率呈指数地减小， 使得节点以非常低的频率发送分组，例如，每消息发送几个分组。作为用分组淹没网 络的替代方式，发送刚刚足以维持一致性的少量分组。

初始地，智能测量仪节点不发送DIO分组，因为DIO分组的一些字段只能被 DODAG根构造。通过向所有RPL节点发送链路本地多播来发送DIO分组。作为集 线器的DODAG根通过发送带有增加的DODAG版本号的DIO分组来发起新的 DODAG构造过程。

响应于接收DIO分组，节点只在以下条件之一成立时更新其状态：

(1)DIO分组中的DODAG版本号大于接收节点的DODAG版本号；

(2)DIO分组中的DODAG版本号等于接收节点的DODAG版本号并且DIO分 组中的秩低于接收节点的秩。

当节点的秩是初始的秩并且以上条件之一成立时，节点更新其状态参数。

如果节点更新其状态参数，则节点可构造和发送DIO分组以向集线器等“通告” 其新状态参数(诸如，DODAG版本号、秩、代价)。

智能测量仪不发送带有其初始秩的DIO分组。节点的秩严格大于其父节点的任 何秩。

当集线器发送带有更大DODAG版本号的DIO分组时，构造新DODAG。初始 地，集线器节点C发送带有比所有智能测量仪节点的版本号大的DODAG版本号的 DIO分组。因此，集线器节点C发送带有大于0的DODAG版本号的其初始DIO分 组，0是所有智能测量仪节点的初始DODAG版本号。

在接收到集线器发送的DIO分组时，集线器的邻居(即，第一跳邻居)更新它 们的状态参数，构造它们的DIO分组并且发送DIO分组，因为接收到的DIO分组具 有更大的DODAG版本号。

在接收到第一跳邻居发送的DIO分组时，第二跳邻居更新它们的状态参数，构 造它们的DIO分组并且发送DIO分组，因为接收到的DIO分组具有更大的DODAG 版本号。

这个DIO分组发送过程持续进行，直到网络中的所有智能测量仪节点接收到DIO 分组并且更新它们的状态参数。也就是说，完全构造了DODAG。

图4示出构造DODAG的方法，其中，节点j发送含有R(j)、c(j)和VN(j)的DIO 分组，节点i接收401DIO分组。R(i)、VN(i)、P(i)和p*(i)是节点i保持的状态参数。

在这个图和其它图中，可在如本领域已知的与存储器和输入/输出接口连接的处 理器中执行所述方法的步骤。处理器可以设置在集线器和智能测量仪中，用图中的任 何节点表示。

在接收到DIO分组时，节点i首先检查402接收到的DIO分组是否是不正确的 或者是否已经被接收。如果是，则节点i丢弃420DIO分组。如果不是，则节点i检 查403节点标识符j是否等于其自身的标识符i。如果是，则节点i丢弃DIO分组， 因为节点接收到自身发送的DIO分组。否则，前进至步骤404。

节点i检查404DIO分组中的DODAG版本号VN(j)是否大于其DAG版本号 VN(i)。如果是，则节点i将其状态参数初始化410为VN(i)＝VN(j)，P(i)＝{j}，p^*(i)＝j， R(i)＝sp((1,1),R(j))，c(i)＝c(j)+c(i,j)并且如果操作模式(MOP)是存储，则清除向下路 由表。然后，节点接着重置411其涓流式定时器以发送DIO分组并且当RPL支持向 下路由时还安排412目的地通告对象(DAO)分组发送。否则，前进至步骤405。

节点i检查405是否VN(j)＝VN(i)。如果不是，则它丢弃DIO分组。如果VN(j)＝ VN(i)并且如果406R(j)≥R(i)，则节点i丢弃DIO分组。如果VN(j)＝VN(i)并且 R(j)<R(i)，则节点i检查是否407接收到的DIO分组对其父集(优选的父节点)或秩 造成任何改变。如果不是，节点i丢弃DIO分组。如果是，节点i更新状态430。如 果节点j不在其父集中并且|P(i)|<T_p，则节点i将节点j添加到其父集中，使得 $P\left(i\right)=P\left(i\right)\cup \left\{j\right\},p^{*}\left(i\right)=\arg \underset{k\in P\left(i\right)}{\min }\{c(i,k)+c\left(k\right)\}.$如果有多个父节点具有相同的最小代价， 则节点i可随机地选取一个优选的父节点，并且c(i)＝c(p^*(i))+c(i,p^*(i))。接着，节点i 安排431DAO分组发送以反映新父节点j。如果节点j已经在P(i)中，则节点i进行 必要的更新，而不安排DAO分组发送。

图5示意性示出示例DODAG的构造。除了集线器节点C和测量仪节点1-6之外， 图5还示出DIO传播链路501、通向优选的父节点的链路502和通向父节点的链路 503。

初始地，节点1-6将它们的秩设置而成(1,1)，将DODAG版本号设置成0，并且 将父集设置为空。集线器节点C将它的秩设置成(0,1)，将DAG版本号设置成1，并 且将其父集设置为空。在这个示意图和其它示意图中，秩(m,n)被示出在节点的正上 方或正下方。

集线器节点C发送携带其DODAG版本号1的DIO分组和秩(0,1)。节点1、2 和3接收DIO分组。因为DIO分组中的DODAG版本号大于节点1、2和3的DODAG 版本号，所以节点1、2和3将它们的DODAG版本号更新成1，将秩更新成 sp((1,1),(0,1))＝(1,2)，并且选择C作为优选的父节点。

用新的DODAG版本号和秩，节点1、2和3发送其带有DODAG版本号1的 DIO分组和秩(1,2)。来自节点1、2和3的DIO分组被集线器C丢弃，因为分组中的 DODAG版本号等于集线器的DODAG版本号并且DIO分组中的秩大于集线器的秩。

节点1丢弃来自节点2的DIO分组，因为DIO分组中的DODAG版本号等于节 点1的DODAG版本号，DIO分组中的秩等于节点1的秩。类似地，节点2丢弃来 自节点1和3的DIO分组，节点3丢弃来自节点2的DIO分组。首先，节点4从节 点1接收DIO分组。

因为DIO分组中的DODAG版本号大于节点4的DODAG版本号，所以节点4 将它的DODAG版本号更新成1，将它的秩更新成sp((1,1),(1,2))＝(2,3)，并且选择节 点1作为优选的父节点。然后，节点4从节点2接收DIO分组。

因为DIO分组中的DODAG版本号等于节点4的DODAG版本号，DIO分组中 的秩小于节点的秩，所以节点4将节点2添加到其父集中。类似地，节点6从节点2 和3接收DIO分组，将它的DODAG版本号更新成1，将秩更新成sp((1,1),(1,2))＝(2,3)， 将节点2和3添加到它的父集中，并且选择节点3作为优选的父节点。节点5从节点 1、2和3接收DIO分组。

因为这些DIO分组中的DODAG版本号大于节点5的DODAG版本号，所以节 点5将它的DODAG版本号更新成1，将它的秩更新成sp((1,1),(1,2))＝(2,3)。然而， 节点5只选择节点2作为它的父节点和优选的父节点。节点4、5和6也发送它们的 DIO分组。

这些分组被它们的邻居丢弃，因为DIO分组中的DODAG版本号等于邻居的 DODAG版本号，并且节点4、5和6的秩不低于邻居的秩。

避开破损链路的本地DODAG修复

当向上线路破损时，通过本发明的实施方式避开破损链路。通过切换至另一个父 节点和/或发送DR-REQ分组来维持DODAG。DR-REQ分组生成器将DR-REQ分组 作为线路本地多播发送到所有RPL节点。

在接收到DR-REQ分组时，如果链路本地邻居没有通向集线器的链路，则它丢 弃DR-REQ分组。如果链路本地邻居是集线器或者具有通向集线器的链路并且其秩 低于DR-REQ分组中的秩，则这个邻居生成DR-REP分组。

如果链路本地邻居具有通向集线器的链路并且它的秩大于或等于DR-REQ分组 中的秩，则这个邻居将DR-REQ分组转送到它优选的父节点。

这个转送过程持续进行，直到DR-REQ分组到达作为集线器或者具有通向集线 器的链路并且其秩低于DR-REQ分组中的秩的节点。然后，生成DR-REP分组。因 为在所有节点之中集线器具有最低秩，所以至少由集线器响应DR-REQ分组。

在存储模式下，DR-REP分组生成器通过使用反向路由表将DR-REP分组发送到 DR-REQ分组生成器。在非存储模式下，DR-REP分组被转送直至集线器，集线器接 着通过使用源路由将DR-REP分组发送到DR-REQ分组生成器。

存储模式下避开破损链路的本地DODAG修复

图6A示出用于存储模式的向上链路破损避开过程。如果601节点i及其父节点 j之间的链路破损，则节点i从其父集P(i)中去除602节点j，使得P(i)＝{k|R(k)<R(i)， k∈P(i)/{j}}。如果603更新后的父集P(i)为空，则节点i发送DR-REQ分组以发现新 的父节点。

如果更新后的父集P(i)不为空，则节点i安排610无路径DAO分组发送。然后， 节点i检查611节点j是否是它优选的父节点p^*(i)，并且如果为真，则节点i选择新 优选的父节点p^*(i)，使得将c(i)更新为c(i)＝c(i,p^*(i))+ c(p^*(i))。

无论节点j是否是节点i优选的父节点，如果|P(i)|<T_p，节点i都可发送DR-REQ 分组以发现另外的父节点。

为了在存储模式下发送DR-REQ分组，节点i将其DR-SN(i)增加1并且设置ID-Q ＝i，R-Q＝R(i)，VN-Q＝VN(i)和SN-Q＝DR-SN(i)。

DR-REQ分组处理

图7A示出当节点i从节点j接收701DR-REQ分组时进行的处理。在图7A中， ID-Q、R-Q、VN-Q和SN-Q是DR-REQ分组中的参数，R(i)、VN(i)和P(i)是节点i 的状态参数。

如果702节点i已经接收到DR-REQ分组(如通过比较ID-Q和SN-Q确定的)， 则节点i丢弃711分组。否则，前进至步骤703。

如果703DR-REQ分组中的VN-Q不等于VN(i)，则节点i丢弃分组。否则，前进 至步骤704。

如果704DR-REQ分组是节点i的父节点之一发送的(即，j∈P(i))或者如果 DR-REQ分组是它的父节点生成的(即，ID-Q∈P(i))或者如果节点i是DR-REQ分 组生成器(即，ID-Q＝i)，则节点i丢弃分组。否则，前进至步骤705。

如果705节点i是集线器节点，也就是说，i＝C，则节点i接受DR-REQ分组， 通过设置ID-Q＝DR-REQ分组中的ID-Q，R-P＝R(C)，c＝c(C)，VN-P＝VN(C)，SN-Q ＝DR-REQ分组中的SN-Q，生成720DR-REP分组，并且经由下一跳节点j将DR-REP 分组发送到节点ID-Q。否则，前进至步骤706。

如果706父集P(i)为空，则节点i发送710它的DR-REQ分组并且丢弃711接收 到的DR-REQ分组。否则，前进至步骤707。

如果707R(i)<R-Q,，则节点i接受DR-REQ分组，并且通过设置ID-Q＝DR-REQ 分组中的ID-Q，R-P＝R(i)，c＝c(i)，VN-P＝VN(i)，SN-Q＝DR-REQ分组中的SN-Q， 生成720DR-REP分组，并且经由下一跳节点j将DR-REP分组发送到节点ID-Q。否 则，前进至步骤730。

如果R(i)≥R-Q,，则节点i将通向节点ID-Q的反向路由条目(ID-Q,SN-Q,R-Q,j) 记录730a到它的DODAG修复反向路由表中，并且将DR-REQ分组发送到它优选的 父节点p^*(i)。

以上分组转送过程持续进行，直到当接收节点没有父节点时丢弃711DR-REQ分 组，或者DR-REQ分组到达作为集线器或者具有秩R(k)<R-Q(其中，|P(k)|≠0)的节 点k。然后，节点k通过设置ID-Q＝ID-Q，R-P＝R(k)，c＝c(k)，VN-P＝VN(k)，SN-Q ＝DR-REQ分组中的SN-Q，生成720DR-REP分组，并且经由节点k从其接收DR-REQ 分组的下一跳节点将DR-REP分组发送到节点ID-Q。

DODAG修复分组反向路由表被初始地设置为空。当节点加入DODAG时，清除 这个表。

DR-REP分组处理

图8A示出当节点i从节点j接收801DR-REP分组时进行的处理。在图8A中， ID-Q、R-P、VN-P和SN-Q是DR-REP分组中的参数，R(i)、VN(i)、P(i)、p^*(i)、c(i) 和T_p是节点i的状态参数，R-Q是DR-REQ分组生成器的秩并且来自DODAG修复 反向路由表。

如果802VN-P≠VN(i)或者已经接收到DR-REP分组，则节点i丢弃811分组。 否则，前进至步骤803。

如果803ID-Q＝i，即，节点i是DR-REQ分组生成器并且节点j不在P(i)中，则 如果|P(i)|<T_p，则节点i将节点j添加810到P(i)中，使得P(i)＝{k|R(k)<R(i),k∈P(i)∪{j}} 并且将p^*(i)和c(i)更新为$p^{*}\left(i\right)=\arg \underset{k\in P\left(i\right)}{\min }\{c(i,k)+c\left(k\right)\},c\left(i\right)=c\left(p^{*}\left(i\right)\right)+c(i,p^{*}\left(i\right)).$

然后，当节点j被添加到节点i的父集中时，节点i安排DAO分组发送。如果 D-ID≠i，则前进至步骤804。

如果804节点i不在反向链路上，即，在它的DODAG修复分组反向路由表中 没有条目(ID-Q,SN-Q,R-Q,l)，则节点i丢弃811分组。否则，前进至步骤805。

如果805R(i)<R-Q，节点i通过设置R-P＝R(i)和c＝c(i)更新820DR-REP分组， 将DR-REP分组转送到下一跳节点l。在存储模式下，如果节点i在通过多个节点生 成的反向链路上，则出现这种情况。当节点i接收到第一DR-REP分组时，节点i减 小它的秩。因此，后续的DR-REP分组可携带大于R(i)的秩R-Q。如果节点i只在单 个反向链路上，则基于DR-REQ分组处理过程，R(i)≥R-Q必须为真。

如果805R(i)≥R-Q，则节点i检查806sp(R-Q,R-P)是否溢出。如果不是，则节 点i减小它的秩R(i)并且将它的父集P(i)更新830为R(i)＝sp(R-Q,R-P)，P(i)＝ {k|R(k)<R(i),k∈P(i)}。然后，节点i通过设置R-P＝R(i)和c＝c(i)更新831DR-REP 分组，将DR-REP分组转送到下一跳节点l，并且如果通过由于其秩减小而删除父节 点来改变它的父节点P(i)，则安排无路径DAO分组发送。

如果sp(R-Q,R-P)溢出，则如果sp(R-Q,R-P)是可约的，节点i首先对其进行简化。 如果没有大于1的公约数，则节点i发送807互联网控制消息协议(ICMP)错误分 组。

通过根据本发明的实施方式的秩分割运算的定义，容易表明，DR-REP分组中的 秩R-P实际上是从DR-REP分组生成器到DR-REP发送节点的链路上的节点的最大 秩。R-P一直小于R-Q。因此，当DR-REP分组到达DR-REQ分组生成器时，DR-REP 分组中的秩R-P必须小于R-Q，R-Q是DR-REQ分组生成器的秩。也就是说，秩沿 着从DE-REP分组生成器到DR-REQ分组生成器的链路单调地增大。这样进而保证 了秩沿着从集线器到任何智能测量仪节点的路由链路单调地增大。

在非存储模式下避开破损链路的本地DODAG修复

如图6B中所示，非存储模式下的向上链路破损处理过程与存储模式下的处理过 程类似。

一个不同之处在于，在从父集P(i)去除节点j之后，如果P(i)不为空，则节点i 安排610'DAO分组发送来替代无路径DAO分组发送。

另一个不同之处在于，为了在非存储模式下发送DR-REQ分组，节点i将它的 DR-SN(i)增加1并且设置ID-Q＝i，R-Q＝R(i)，VN-Q＝VN(i)，SN-Q＝DR-SN(i)和NL-Q ＝{i}。

处理DR-REQ分组

图7B示出当节点i从节点j接收751DR-REQ分组时进行的处理。在图7B中， ID-Q、R-Q、VN-Q、SN-Q和NL-Q是DR-REQ分组中的参数，R(i)、VN(i)和P(i)是 接收节点i的状态参数。

如果752节点i已经接收到这个DR-REQ分组(如通过比较ID-Q和SN-Q确定 的)，则节点i丢弃711分组。否则，前进至步骤753。

如果753DR-REQ分组中的VN-Q不等于VN(i)，则节点i丢弃分组。否则，前进 至步骤754。

如果754DR-REQ分组是节点i的父节点中的一个发送的(即，j∈P(i))或者如 果DR-REQ分组是它的父节点生成的(即，ID-Q∈P(i))或者如果节点i是DR-REQ 分组生成器(即，ID-Q＝i)，则节点i丢弃分组。否则，前进至步骤755。

如果755节点i是集线器节点，即，i＝C，则节点i接受DR-REQ分组，通过 设置ID-Q＝DR-REQ分组中的ID-Q，R-P＝R(C)，c＝c(C)，VN-P＝VN(C)，SN-Q＝ DR-REQ分组中的SN-Q、D＝DOWN、R-Q＝DR-REQ分组中的R-Q、NL-P ＝NL-Q∪{C}，生成760DR-REP分组，并且经由NL-P使用源路由将DR-REP分组发 送到节点ID-Q。否则，前进至步骤756。

如果756节点i不是集线器并且它的父集P(i)为空，则节点i发送710DR-REQ 分组并且丢弃接收到的DR-REQ分组。否则，前进至步骤757。

如果757R(i)<R-Q,，则节点i接受DR-REQ分组，并且通过设置ID-Q＝DR-REQ 分组中的ID-Q、R-P＝R(i)、c＝c(i)、VN-P＝VN(i)、SN-Q＝DR-REQ分组中的SN-Q、 D＝UP、R-Q＝DR-REQ分组中的R-Q、NL-P＝NL-Q∪{i}生成759DR-REP分组， 并且将DR-REP分组转送到它的优选父节点p^*(i)。否则，前进至步骤758。

如果R(i)≥R-Q，则节点i通过将i插入758NL-Q中使得NL-Q＝NL-Q∪{i}来更 新DR-REQ分组，并且将DR-REQ分组转送到它的优选父节点p^*(i)。

以上分组转送过程持续进行，直到当接收节点没有父节点时丢弃DR-REQ分组 或者DR-REQ分组到达作为集线器或者具有秩R(k)<R-Q(其中，|P(k)|≠0)的节点k。 然后，节点k通过设置ID-Q＝DR-REQ分组中的ID-Q，R-P＝R(k)，c＝c(k)，VN-P＝ VN(k)，SN-Q＝DR-REQ分组中的SN-Q，D＝UP(如果k≠C)或者D＝DOWN(如 果k＝C)，R-Q＝DR-REQ分组中的R-Q，NL-P＝NL-Q∪{k}，生成DR-REP分组， 并且如果k≠C，则将DR-REP分组转送到它的优选父节点p^*(k)，如果k＝C，则经由 NL-P使用源路由将DR-REP分组向下发送到节点ID-Q。

DR-REP分组处理

节点i从节点j接收851DR-REP分组。在图8B中，ID-Q、R-P、VN-P、SN-Q、 D、R-Q和NL-P是DR-REP分组中的参数，R(i)、VN(i)、P(i)、p^*(i)、c(i)和T_p是节 点i的状态参数。

如果852VN-P≠VN(i)或者已经接收到DR-REP分组，则节点i丢弃811分组。 否则，前进至步骤853。

如果853D＝UP，则向上发送DR-REP分组，节点i检查860是否i＝C，即节 点i是否是集线器。如果是，则节点i通过改变D＝DOWN，R-P＝R(C)，c＝c(C)， NL-P＝NL-P∪{C}，更新861DR-REP分组，并且通过源路由经由NL-P将DR-REP 分组向下发送到节点ID-Q。

如果i≠C，即如果节点i不是集线器，并且870P(i)不为空，则节点i通过将i 插入872NL-P中使得NL-P＝NL-P∪{i}来更新DR-REP分组，并且将DR-REP分组 转送到父节点p^*(i)。

如果i≠C并且P(i)为空，则节点i丢弃811DR-REP分组并且发送871DR-REP 分组。

如果D≠UP，即D＝DOWN并且向下发送DR-REP分组，则前进至步骤854。

如果854ID-Q＝i，即，节点i是DR-REQ分组生成器，如果节点j不在P(i)中并 且|P(i)|<T_p，则节点i将节点j添加840到P(i)中，使得P(i)＝{k|R(k)<R(i),k∈P(i)∪{j}} 并且将p^*(i)和c(i)更新为$p^{*}\left(i\right)=\arg \underset{k\in P\left(i\right)}{\min }\{c(i,k)+c\left(k\right)\},c\left(i\right)=c\left(p^{*}\left(i\right)\right)+c(i,p^{*}\left(i\right)).$然后， 如果节点j被添加到节点i的父集中，节点i安排841DAO分组发送。如果ID-Q≠i， 则前进至步骤855。

如果855节点i不在源路由链路上，也就是说，节点i不在NL-P中，则节点i 丢弃811分组。否则，前进至步骤856。

如果856R(i)<R-Q，则节点i通过设置R-P＝R(i)和c＝c(i)更新880DR-REP分 组，经由NL-P转送881DR-REP分组。否则，前进至步骤857。

节点i检查857sp(R-Q,R-P)是否溢出。如果不是，则节点i减小它的秩R(i)并且 将它的父集P(i)更新890为R(i)＝sp(R-Q,R-P)，P(i)＝{k|R(k)<R(i),k∈P(i)}。然后， 节点i通过设置R-P＝R(i)、c＝c(i)更新891DR-REP分组并且经由NL-P转送DR-REP 分组。此外，如果通过由于节点i的秩减小而删除父节点来改变它的父节点P(i)，则 节点i安排892DAO分组发送。

如果sp(R-Q,R-P)溢出，则节点i简化sp(R-Q,R-P)(如果它是可约的)。如果没 有大于1的公约数，则节点i发送858ICMP错误分组。

通过秩分割运算的定义，容易表明，向下DR-REP分组中的秩R-P是从集线器节 点到DR-REP发送节点的源路由链路上的节点的最大秩。R-P一直小于R-Q。

因此，当DR-REP分组到达DR-REQ分组生成器时，DR-REP分组中的秩R-P 必须小于R-Q，R-Q是DR-REQ分组生成器的秩。也就是说，从集线器到DR-REQ 分组生成器，秩单调地增大。这样进而保证了秩沿着从集线器到任何智能测量仪节点 的路由链路单调地增大。

避开破损链路的本地DODAG修复示例

图9示意性示出用于避开破损链路102的修复处理。除了集线器节点C和测量 仪节点1-6之外。图9还示出通向优选父节点的链路502、DR-REQ传播链路901、 DR-REP传播链路902、旧秩905和新秩906。

如果节点5和节点2之间的链路破损102，则节点5发送DR-REQ分组。节点4 和节点6接收这个分组。这两个节点都具有通向集线器的链路，但这两个节点的秩不 低于DR-REQ分组中的秩。因此，DR-REQ分组被分别转送到它们的优选父节点1 和3。

另外，节点4和节点6记录通向节点5的反向链路，使得节点可将今后的DR-REP 分组转送到节点5。节点1和3具有通向集线器的链路并且它们的秩低于DR-REQ分 组中的秩。因此，它们发送DR-REP分组。这个DR-REP分组发送过程沿着通向 DR-REQ分组生成器节点5的链路更新节点的秩。对于节点4和节点6，旧秩905是 (2,3)并且新秩906是(3,5)。节点5从节点4和节点6接收DR-REP分组，选择 节点6作为它的优选父节点。

图10示意性示出如何通过本发明的本地DODAG修复方法避开图1中的破损链 路102，因为真分数形式的秩绝不增大。插入框1010示出在修复处理期间使用的各 种分割(sp)运算。该图还示出DR-REP分组发送1001、DR-REQ分组发送1002和 节点1的通向其新的优选父节点的链路1003。

R(i)(i＝1、2、…、7)是节点i的秩。R(C)是集线器节点C的秩。节点1从它的 父集P(i)中去除节点C并且发送其中R-Q＝R(1)＝(1,2)的DR-REQ分组。节点2丢弃 DR-REQ分组，因为DR-REQ分组是由节点2的父节点发送的。节点3将DR-REQ 分组转送到节点2，因为DR-REQ分组中的R-Q小于它的秩R(3)。

然而，节点2丢弃通过节点3转送的DR-REQ分组，因为DR-REQ分组是节点 2的父节点生成的。节点4将DR-REQ分组转送到节点5，因为R-Q小于R(4)。类似 地，节点5将DR-REQ分组转送到节点6，节点6将DR-REQ分组转送到节点7，节 点7将DR-REQ分组转送到集线器，集线器生成其中R-P＝R(C)＝(0,1)的DR-REP 分组。

在接收到DR-REP分组时，节点7因为R(7)≥R-Q而将它的秩减小至R’(7)＝(1, 3)，设置R-P＝R’(7)，将DR-REP分组转送到节点6。类似地，节点6将它的秩减小 至R’(6)＝(2,5)，设置R-P＝R’(6)并且将DR-REP分组转送到节点5；节点5将它的 秩减小至R’(5)＝(3,7)，设置R-P＝R’(5)并且将DR-REP分组转送到节点4；节点4 将它的秩减小至R’(4)＝(4,9)，设置R-P＝R’(4)并且将DR-REP分组转送到节点1。 在从节点4接收到DR-REP分组时，节点1选择节点4作为它的优选父节点。

完成了节点1发起的本地DODAG修复过程。在本地DODAG修复之后，父子 关系是3→2→1→4→5→6→7→C。

[工业可应用性]

本发明的方法可应用于许多种类的领域。