一种在配用电无线自组织网中建立树形路由的方法

本发明涉及配用电领域，特别是指一种在配用电无线自组织网中建立树形路由的 方法。

传统无线网络路由协议，主要关心的是路由可用性。大多是以跳数、丢包率作为路 由判据，选择跳数最少的或丢包率最小的路径作为数据传输路径，但是并没有考虑链路干 扰和网络吞吐量等关键因素。并且不能很好地适应配用电业务场景。

如DSR、AODV、TBRPF等针对传统无线网络的设计的路由协议，主要关心的是路由可 用性。而配用电无线自组织网络对于传输链路的质量有这较高要求，需要提供高质量、高稳 定性的络接入服务。因此，在设计针对配用电无线自组织网络的路由协议时，应将链路质量 纳入路由度量的考虑范围，以便路由协议能选择传输质量最优的路径。同时，鉴于无线链路 的不可靠性，网络的路由协议应具有健壮性。当出现节点故障和路径失效时候，能尽快恢复 或者切换到其他路径上进行传输。

有鉴于此，本发明的目的在于提出一种具有健壮性，且出现节点故障和路径失效 时能尽快恢复或者切换到其他路径上进行传输的多射频多信道树形路由方法。

基于上述目的本发明提供的一种在配用电无线自组织网中建立树形路由的方法， 包括：

网关节点信号覆盖范围内的第一节点更新路由表，并进行本地广播，向邻居节点 发送路由请求；

所述邻居节点收到所述路由请求后，向所述第一节点发送路由应答消息；

所述第一节点收到所述路由应答消息后，计算经过所述邻居节点到达网关节点的 路径耗费值，并选择路径耗费值最低的节点为父节点，将对应的信道信息加入申请加入消 息包中，并向所述父节点发送所述申请加入消息包；

所述父节点收到所述申请加入消息包后，修改自身路由表，并为空闲的接口分配 所述申请加入消息包中携带的已选信道，并向所述第一节点发送接收加入消息包，同时以 网管节点为目的节点向上层发送通知上层加入消息包；

所述第一节点收到所述接收加入消息包后，更新自身路由表；

网关节点信号覆盖范围内其他节点按照上述过程建立路由，当任一节点接收到通 知上层加入消息包后，更新各自的路由表，如果所述任一节点不是网关节点，则继续发送通 知上层加入消息包，直到网管节点收到所述通知上层加入消息包。

进一步的，所述路由表包括目的节点和下一跳节点两部分信息。

进一步的，还包括：

所述邻居节点收到所述路由请求后，查自己的路由表中是否存在到达网关的路 由，如果存在到达网关的路由，则向所述第一节点发送路由应答消息，如果不存在到达网关 的路由，则不做任何处理。

进一步的，还包括：

如果所有所述的邻居节点都不存在到达网关的路由，则所述第一节点等待一个周 期后再次发送所述路由请求。

进一步的，所述路径耗费值的算法包括：

计算节点J使用各个信道的干扰概率，节点J即为第一节点，出节点J的使用信道 fm(m＝1,2,3……)的1、2、3跳邻居集合VJ,m，假设每个节点等概率向所有邻居发送数据，当i ∈Vj,m且i是J的1跳邻居时：

PJ,i,m＝1

其中PJ,i,m表示使用信道fm时，节点i对节点J产生干扰的概率；

当i∈VJ,m且i与J距离为2跳时，只有在i向J的邻居发送数据时或i向其他节点发送 数据的同时J要向i的邻居发送数据时才会产生干扰，此时有

其中Vt,m-khop表示距离节点t为k跳且有射频接口使用信道fm的邻居集合；|Vt,m-khop| 表示集合中元素的个数，式中加号左部代表i向J的邻居发送数据的概率，加号右部代表i向 其他节点发送数据的同时J要向i的邻居发送数据的概率；

当i∈VJ,m且J与i距离为3跳时，当且仅当J与i要发送数据的接收方是邻居时才会 产生干扰，此时有

根据干扰概率计算出节点J使用信道fm干扰节点的期望数值nJ,m

则节点J使用信道fm与邻居节点通信的期望传输时间ETTJ,m为

其中代表期望传输次数，p代表链路丢包率；S代表数据包的长度，B_m代表信道f_m的带宽；

以每个邻居节点为父节点的路由耗费Path_ETTJ为

Path_ETTJ＝Path_ETTn+ETTJ,m

其中Path_ETTn代表节点n到网关节点的路由耗费。

进一步的，还包括：

查询邻居节点n的信道使用信息，判断其是否具有空闲射频接口，若有则对应的信 道可以从所有信道中选择，如果没有空闲接口，对应的信道只能从邻居节点已使用的信道 集合中选择。

进一步的，所述网关节点信号覆盖范围内其他节点按照上述过程建立路由包括：

网关节点信号覆盖范围内其他节点按照上述过程建立路由，先将源节点地址和所 选子节点信息加入路由表，且源节点为下一跳节点所选子节点为目的节点，如果所述任一 节点不是网关节点，则将消息中源地址改为本地地址，并继续发送通知上层加入消息包，直 到网管节点收到所述通知上层加入消息包。

进一步的，当网络中节点在进行路由查时，首先在本地路由表中查，本地路由 表中如果没有所目的节点，则节点直接将数据包转发给父节点，由父节点进行转发。

进一步的，还包括：

新加入节点在路由计算和信道选择之后，保留后备可达父节点的信息，然后向最 优父节点发送申请加入消息包，当父节点失效后，该节点可向后备父节点发送申请加入消 息包；

当网络中有节点失效时，其子节点首先判断是否有后备父节点，如果有则启动快 速路由恢复过程；如果没有则立即向下层子节点发送故障消息包，告知失效的父节点列表， 子节点开启快速路由修复过程。

从上面所述可以看出，本发明提供的在配用电无线自组织网中建立树形路由的方 法，包括网关节点信号覆盖范围内的节点更新路由表，并进行本地广播，向邻居节点发送路 由请求，邻居节点收到所述路由请求后，发送路由应答消息，节点收到所述路由应答消息 后，计算经过所述邻居节点到达网关节点的路径耗费值，并选择路径耗费值最低的节点为 父节点，将对应的信道信息加入申请加入消息包中，并向所述父节点发送所述申请加入消 息包；所述父节点收到所述申请加入消息包后，修改自身路由表，并为空闲的接口分配所述 申请加入消息包中携带的已选信道，同时以网管节点为目的节点向上层发送通知上层加入 消息包。本发明的路由的方法建立的路由具有健壮性，且出现节点故障和路径失效时能尽 快恢复或者切换到其他路径上进行传输。

图1为本发明在配用电无线自组织网中建立树形路由的方法的一个实施例的流程 图；

图2如为到达网关节点的路径耗费值的计算方法流程图；

图3为本发明的方法建立的树形路由中路由恢复过程示意图；

图4为路由修复示意图。

为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照 附图，对本发明进一步详细说明。

本发明实施例提供的一种在配用电无线自组织网中建立树形路由的方法，包括：

网关节点信号覆盖范围内的第一节点更新路由表，并进行本地广播，向邻居节点 发送路由请求；

所述邻居节点收到所述路由请求后，向所述第一节点发送路由应答消息；

所述第一节点收到所述路由应答消息后，计算经过所述邻居节点到达网关节点的 路径耗费值，并选择路径耗费值最低的节点为父节点，将对应的信道信息加入申请加入消 息包中，并向所述父节点发送所述申请加入消息包；

所述父节点收到所述申请加入消息包后，修改自身路由表，并为空闲的接口分配 所述申请加入消息包中携带的已选信道，并向所述第一节点发送接收加入消息包，同时以 网管节点为目的节点向上层发送通知上层加入消息包；

所述第一节点收到所述接收加入消息包后，更新自身路由表；

网关节点信号覆盖范围内其他节点按照上述过程建立路由，当任一节点接收到通 知上层加入消息包后，更新各自的路由表，如果所述任一节点不是网关节点，则继续发送通 知上层加入消息包，直到网管节点收到所述通知上层加入消息包。

本发明实施例提供的在配用电无线自组织网中建立树形路由的方法，考虑了链路 干扰和网络吞吐量等关键因素，且路由协议具有健壮性，路由协议能选择传输质量最优的 路径，当出现节点故障和路径失效时候，能尽快恢复或者切换到其他路径上进行传输。

在上述实施例中，所述路由表包括目的节点和下一跳节点两部分信息。

进一步的，还包括：所述邻居节点收到所述路由请求后，查自己的路由表中是否 存在到达网关的路由，如果存在到达网关的路由，则向所述第一节点发送路由应答消息，如 果不存在到达网关的路由，则不做任何处理。

作为本发明的一个实施例，还包括：

如果所有所述的邻居节点都不存在到达网关的路由，则所述第一节点等待一个周 期后再次发送所述路由请求。

在本发明的上述实施例中，所述路径耗费值的算法包括：

计算节点J使用各个信道的干扰概率，节点J即为第一节点，出节点J的使用信道 fm(m＝1,2,3……)的1、2、3跳邻居集合VJ,m，假设每个节点等概率向所有邻居发送数据，当i ∈Vj,m且i是J的1跳邻居时：

PJ,i,m＝1

其中PJ,i,m表示使用信道fm时，节点i对节点J产生干扰的概率；

当i∈VJ,m且i与J距离为2跳时，只有在i向J的邻居发送数据时或i向其他节点发送 数据的同时J要向i的邻居发送数据时才会产生干扰，此时有

其中Vt,m-khop表示距离节点t为k跳且有射频接口使用信道fm的邻居集合；|Vt,m-khop| 表示集合中元素的个数，式中加号左部代表i向J的邻居发送数据的概率，加号右部代表i向 其他节点发送数据的同时J要向i的邻居发送数据的概率；

当i∈VJ,m且J与i距离为3跳时，当且仅当J与i要发送数据的接收方是邻居时才会 产生干扰，此时有

根据干扰概率计算出节点J使用信道fm干扰节点的期望数值nJ,m

则节点J使用信道fm与邻居节点通信的期望传输时间ETTJ,m为

其中代表期望传输次数，p代表链路丢包率；S代表数据包的长度，B_m代表信道f_m的带宽；

以每个邻居节点为父节点的路由耗费Path_ETTJ为

Path_ETTJ＝Path_ETTn+ETTJ,m

其中Path_ETTn代表节点n到网关节点的路由耗费。需要说明的是，J节点是网管节 点范围内的任意一点，这里只是以一个节点举例来说明节点之间是如何建立路由的。

在本发明的一些实施例中，还包括：

查询邻居节点n的信道使用信息，判断其是否具有空闲射频接口，若有则对应的信 道可以从所有信道中选择，如果没有空闲接口，对应的信道只能从邻居节点已使用的信道 集合中选择。

在本发明的其他的一些实施例中，所述网关节点信号覆盖范围内其他节点按照上 述过程建立路由包括：

网关节点信号覆盖范围内其他节点按照上述过程建立路由，先将源节点地址和所 选子节点信息加入路由表，且源节点为下一跳节点所选子节点为目的节点，如果所述任一 节点不是网关节点，则将消息中源地址改为本地地址，并继续发送通知上层加入消息包，直 到网管节点收到所述通知上层加入消息包。

当网络中节点在进行路由查时，首先在本地路由表中查，本地路由表中如果 没有所目的节点，则节点直接将数据包转发给父节点，由父节点进行转发。

此外，还包括：新加入节点在路由计算和信道选择之后，保留后备可达父节点的信 息，然后向最优父节点发送申请加入消息包，当父节点失效后，该节点可向后备父节点发送 申请加入消息包；

当网络中有节点失效时，其子节点首先判断是否有后备父节点，如果有则启动快 速路由恢复过程；如果没有则立即向下层子节点发送故障消息包，告知失效的父节点列表， 子节点开启快速路由修复过程。

如图1所示，为本发明在配用电无线自组织网中建立树形路由的方法的一个实施 例的流程图。在实现本实施例技术方案的过程中，定义了6中消息包，如下表：

Request 路由请求消息包

Respond 路由应答消息包 包含本地节点到达网关节点的路由耗费

Join 申请加入消息包 包含所选信道信息

Accept 接收加入消息包 包含通过自己可到的网关节点信息以及信道信息

Up-Add 通知上层加入消息包 包含所选子节点的信息

FAILUR 故障消息包 包含失效父节点列表

在上述定义的消息包的基础上，本实施例的技术方案包括：

步骤101：节点S按周期T进行本地广播，向邻居节点发出路由请求消息Request。

步骤102：节点S的邻居节点接收节点S发出的路由请求消息Request。

步骤103：节点S的邻居节点判断各自的路由表内是否有到达网管节点的路由，若 没有，则不进行任何处理；若有，则进入步骤104。

步骤104：接收到请求消息Request的节点S的邻居节点向节点S发送回应消息 Respond。

步骤105：判断节点S是否收到邻居节点发来的Respond消息，若没有收到邻居节点 发来的Respond消息，则返回步骤101，若收到邻居节点发来的Respond消息，则进入步骤 106。

步骤106：节点J收到邻居节点发来的Respond消息后，计算经过它们到达网关节点 的路径耗费值Path_ETTJ，选择耗费最低的节点(如节点B)为父节点，将对应的信道信息加 入Join消息包中，并向该节点B发送加入请求Join。

步骤107：节点B收到Join消息。

步骤108：节点B修改路由表，添加节点J为子节点，节点J既是目的节点又是下一跳 节点，并为空闲的接口分配Join中携带的已选信道。

步骤109：节点B向节点J发送Accept消息，并以网关节点为目的节点向上层发送 Up-Add消息。

步骤110：节点J接收到Accept消息。

步骤111：节点J将节点B的地址和网关节点地址添加到路由表中，且节点B为下一 跳节点，网关节点为目的节点。

步骤112：上层节点X收到Up-Add消息。

步骤113：上层节点X将源节点地址和所选子节点信息加入路由表，且源节点为下 一跳节点所选子节点为目的节点。

步骤114：上层节点X判断本地节点是否为网关节点，若是，则进入步骤115，否则进 入步骤116。

步骤115：节点S完成路由建立。

步骤116：上层节点X将消息中源地址改为本地地址，继续向网关节点发送Up-Add 消息，直到网关节点收到Up-Add消息。

这样就实现了节点J的路由建立，其他节点同时进行上述步骤的操作，周期性地发 送路由请求，直到收到能到达网关节点的邻居回应，建立路由并更新路由表；持续进行此过 程直到网络中所有节点都到了合适的父节点，建立了到达网关节点的路由。

网络中节点在进行路由查时，首先在本地路由表中查，本地路由表中如果没 有所目的节点，则节点直接将数据包转发给父节点，由父节点进行转发。

本发明实施例提供的在配用电无线自组织网中建立树形路由的方法，考虑了链路 干扰和网络吞吐量等关键因素，且路由协议具有健壮性，路由协议能选择传输质量最优的 路径，当出现节点故障和路径失效时候，能尽快恢复或者切换到其他路径上进行传输。

如图2所示，为到达网关节点的路径耗费值的计算方法流程图。包括：

步骤201：计算节点S使用各个信道的干扰概率；

步骤202：计算出节点S使用各个信道时干扰节点的期望数值。

步骤203：计算节点使用各个信道与各邻居节点通信的期望传输时间。

步骤204：计算以每个邻居节点为父节点的路由耗费。

具体的，路径耗费值的计算方法为：

首先计算节点J使用各个信道的干扰概率，出节点J的使用信道fm(m＝1,2, 3……)的1、2、3跳邻居集合VJ,m。假设每个节点等概率向所有邻居发送数据，当i∈Vj,m且i是 J的1跳邻居时：

PJ,i,m＝1

其中PJ,i,m表示使用信道fm时，节点i对节点J产生干扰的概率。

当i∈VJ,m且i与J距离为2跳时，只有在i向J的邻居发送数据时或i向其他节点发送 数据的同时J要向i的邻居发送数据时才会产生干扰，此时有

其中Vt,m-khop表示距离节点t为k跳且有射频接口使用信道fm的邻居集合；|Vt,m-khop| 表示集合中元素的个数。式中加号左部代表i向J的邻居发送数据的概率，加号右部代表i向 其他节点发送数据的同时J要向i的邻居发送数据的概率。

当i∈VJ,m且J与i距离为3跳时，当且仅当J与i要发送数据的接收方是邻居时才会 产生干扰，此时有

根据干扰模型，距离4跳以上的节点不会产生干扰。

然后根据干扰概率计算出节点J使用信道fm干扰节点的期望数值nJ,m

则节点J使用信道fm与邻居节点通信的期望传输时间ETTJ,m为

其中代表期望传输次数，p代表链路丢包率；S代表数据包的长度，B_m代表信道f_m的带宽。

综上，以每个邻居节点为父节点的路由耗费Path_ETTJ为

Path_ETTJ＝Path_ETTn+ETTJ,m

其中Path_ETTn代表节点n到网关节点的路由耗费，可由Respond消息包得到。

最小路由耗费即min{Path_ETTJ}。

如图3所示，为本发明的方法建立的树形路由中路由恢复过程示意图。包括：

当节点失效后，判断失效的子节点是否有后备父节点，若有后备父节点，则进入步 骤301，否则，进入步骤302。

步骤301：启动快速路由恢复过程。

步骤302：向下层子节点发送FAILURE消息，告知下层子节点失效的父节点列表，并 进一步判断下层子节点是否有后备父节点。

由于在路由发现阶段，新加入节点在路由计算和信道选择之后，保留后备可达父 节点的信息，然后向最优父节点发送Join消息，当父节点失效后，该节点可向后备父节点发 送Join消息。当网络中有节点失效时，其子节点首先判断是否有后备父节点，如果有则启动 快速路由恢复过程；如果没有则立即向下层子节点发送FAILURE消息，告知失效的父节点列 表(包括自己)，子节点开启快速路由修复过程(如子节点也没有后备父节点，将把自己加入 失效父节点列表，递归向子节点发送FAILURE消息)。

如图4所示，为路由修复示意图。当节点A失效后，由于节点A没有后备父节点，则节 点A向下层节点B发送FAILURE消息，由于下层节点B也没有后备父节点，这节点B向下层节点 C和D发送FAILURE消息，由于下层节点D具有后备父节点F，则下层节点D通过后备父节点F恢 复路由，同时节点D为节点B和节点C的后备父节点，节点B和节点C通过后备父节点D恢复路 由。

需要说明的是，本发明实施例中所有使用“第一”和“第二”的表述均是为了区分两 个相同名称非相同的实体或者非相同的参量，可见“第一”“第二”仅为了表述的方便，不应 理解为对本发明实施例的限定，后续实施例对此不再一一说明。

所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非 旨在暗示本公开的范围(包括权利要求)被限于这些例子；在本发明的思路下，以上实施例 或者不同实施例中的技术特征之间也可以进行组合，步骤可以以任意顺序实现，并存在如 上所述的本发明的不同方面的许多其它变化，为了简明它们没有在细节中提供。

另外，为简化说明和讨论，并且为了不会使本发明难以理解，在所提供的附图中可 以示出或可以不示出与集成电路(IC)芯片和其它部件的公知的电源/接地连接。此外，可以 以框图的形式示出装置，以便避免使本发明难以理解，并且这也考虑了以下事实，即关于这 些框图装置的实施方式的细节是高度取决于将要实施本发明的平台的(即，这些细节应当 完全处于本领域技术人员的理解范围内)。在阐述了具体细节(例如，电路)以描述本发明的 示例性实施例的情况下，对本领域技术人员来说显而易见的是，可以在没有这些具体细节 的情况下或者这些具体细节有变化的情况下实施本发明。因此，这些描述应被认为是说明 性的而不是限制性的。

尽管已经结合了本发明的具体实施例对本发明进行了描述，但是根据前面的描 述，这些实施例的很多替换、修改和变型对本领域普通技术人员来说将是显而易见的。例 如，其它存储器架构(例如，动态RAM(DRAM))可以使用所讨论的实施例。

本发明的实施例旨在涵盖落入所附权利要求的宽泛范围之内的所有这样的替换、 修改和变型。因此，凡在本发明的精神和原则之内，所做的任何省略、修改、等同替换、改进 等，均应包含在本发明的保护范围之内。