采用树形拓扑关系避免路由环路的方法

摘要

本发明提供一种采用树形拓扑关系避免路由环路的方法，建立了树形网络，向节点分配拓扑序号，在树形网络中创建分支拓扑序列信息以及在树形网络中避免路由环路的方法，该方法包括：源节点广播RREQ报文，收到该RREQ报文的节点查询所述分支拓扑序列信息；判断源节点是否为所述收到该RREQ报文的节点的祖先节点；如果否，则所述收到该RREQ报文的节点响应该RREQ报文；如果是，则所述收到该RREQ报文的节点不响应该RREQ报文。该方法通过分析节点之间的拓扑层次关系，阻止路由环路发生的可能性。

说明书

技术领域

本发明涉及一种无线传感器网络的路由方法。更具体地，本发明涉及一种采用树形拓扑关系避免路由环路的无线传感器网络路由方法。

背景技术

无线传感器网络(Wireless Sensor Networks，WSNs)技术是现代通信技术和计算机网络技术的重要组成部分，它是由分布在观测区域内的大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织网络。各传感器节点之间协同合作地感知物理世界的对象信息(如：温度、湿度、加速度、光强等)，并最终将数据信息汇聚、融合至服务器和观察者。

近年来，随着物联网的兴起和发展，无线传感器网络技术受到了更多的关注，其逐渐成为实现物理世界和信息世界相互融合的重要保障。与此同时，伴随无线传感器网络技术发展而产生的应用扩展也有着越来越广阔的空间和美好的前景。目前无线传感器网络技术已广泛应用于智能交通、智能电网、智能家居、工业控制、环境监测、医疗保健、军事等领域。

图1表示的是无线传感器网络的基本结构。无线传感器网络一般包括：传感节点(sensor节点)如W、X、Y、Z和汇聚节点(sink节点)，无线传感器网络通过sink节点接入服务器从而与各种网络交互。各传感节点(以下如无特指，统称为节点)之间协作地感知信息，通过多跳将信息汇聚至sink节点，再连接至服务器，经各种无线或有限网络供用户查询、配置和管理。

无线传感器网络一般拥有数量众多的节点设备，在许多情况下，每一个节点都需要配置全球唯一的IP地址，因此IPv6技术在无线传感器网络中有着重要的应用价值。但另一方面，无线传感器网络由于资源受限等原因，对于IPv6协议栈占用的资源(如128比特IPv6地址)不能很好的适应和满足，这尤其体现在路由协议的设计和实现上。

AODV(Ad hoc On-Demand Distance Vector Routing)路由协议是无线传感器网络中经典的按需路由协议之一，但是考虑到资源受限等因素，因此需要重新对AODV路由协议进行改进和优化。MSRP(Micro Sensor Router Protocol)协议按照上述思想对AODV协议进行了优化，分别精简了路由交互报文格式，使用64位(8字节)IPv6地址接口标识符即IPv6地址的后64位代替IPv6中的128位(16字节)地址，可以有效减少地址字段的长度，使得路由解析过程变得更加简单、有效，符合无线传感器网络能量、存储资源受限的要求，其中，1位就是1比特(bit)，8位就是1字节。此外，IEEE802.15.4协议规定两种地址格式，64位地址和16位地址。其中，采用64位地址能够保证地址的唯一性，能够实现节点地址的自动配置，而采用16位地址则需要网关分配，并且需要考虑地址重复检测、地址回收等问题，实现起来复杂，所以采用64位IPv6地址接口标识符符合IEEE 802.15.4标准对于地址字段的要求。以下分别为路由请求(RREQ)报文、路由回复(RREP)报文、路由错误(RERR)报文的格式：

RREQ报文格式

其中的类型为000，表示RREQ报文类型，跳数为RREQ报文携带的从源节点到当前节点的跳数；路由请求ID为RREQ消息的唯一标识；源地址为源节点的地址即发出RREQ报文的节点或者该节点的某个RFD(Reduced Function Device)节点的IEEE802.15.4定义的64比特(8字节)接口标识符；目的地址为目的节点的地址即接收RREQ请求路由节点的64比特(8字节)接口标识符；最小LQI：报文携带从RREQ源节点到当前节点的链路质量度量值的最小值。LQI(Link Quality Indicator)是符合IEEE802.15.4标准的一项对于无线传感器网络链路质量进行度量的参数。采用此字段可以在路由建立的过程中作为选路的依据，以此建立的路由能够保证较高的链路质量。RFD节点可以理解为没有路由功能，只能与其他节点通信的采集节点。

RREP报文格式

其中的类型为001，表示RREP报文类型；跳数为RREP报文携带的从源节点到当前节点的跳数；源地址为发起RREP的节点或该节点的某个RFD节点的IEEE802.15.4定义的64比特接口标识符；目的地址为接收RREP的节点即对应于RREQ发起节点的IEEE802.15.4定义的64比特接口标识符；最小LQI：报文携带从RREP源节点到当前节点的链路质量度量值的最小值。

RERR报文格式

类型：010，表示RERR报文类型；不可达地址的数目：某节点检测的失效邻居节点的个数；不可达目的地址：某节点检测的失效邻居节点的IEEE802.15.4定义的64比特接口标识符。不可达地址的数目决定不可达目的地址的个数，因此如果有更多不可达目的地址，则报文格式中可以携带更多的不可达目的地址。

其中MSRP协议建立路由的基本过程是，无路由的节点向邻居节点广播路由请求(RREQ)报文，并经过中间节点转发，当sink节点收到该路由请求报文时，就向发起路由请求(RREQ)报文的节点回复路由回复(RREP)报文，从而建立节点到sink节点的路由。

但是MSRP协议将所有的路由回复(RREP)报文交由sink节点处理的方式，不仅大大增加了sink节点的负载，也增加了节点建立路由的时延。因此现有技术又进一步采取中间节点回复RREP的方式解决sink节点负载过重和路由时延过大等缺陷，即如果中间节点的路由表中存在到达sink节点的可用路由时，由该中间节点直接回复RREP而不是向sink节点转发，而这样的方式又会不可避免的带来路由环路的新问题。

所谓路由环路就是，数据包在一系列节点之间不断传输却始终无法到达其预期目的节点的一种现象。当两个节点或多个节点的路由信息中存在错误地指向不可达目的节点的有效路径时，就可能发生路由环路。举例来说，假设网络中有节点A、B、C、E，初始路由是C→B→A和E→B→A。某一时刻，节点B链路出错，处于失效状态。在一次发送数据过程中，节点C发送给节点B的数据包全部收不到ACK回复，那么节点C就会判定自己到节点B的路由错误，因此开始广播RREQ重新寻找路由，这个RREQ被节点E所获取，因为节点E此时并不知道节点B不工作了，因此会回复RREP给节点C，重新建立的路由为C→E→B→A。但是，这条路由仍然包括已经不工作的节点B，实际仍是无效路由。随后，节点E在发送数据的过程中也发现有大量的包丢失，因此发起广播RREQ过程，此时节点C因为路由已经更新，节点B已经不再被节点C认为无效，所以当节点C收到节点E发来的RREQ后，向其回复RREP，从而使节点E具有新的路由即变成E→C→E→B→A，对于节点C向节点E提供的路由是否仍包括节点E本身，节点C在提供路由之前是无法判断的，因此这种过程会一直往复，导致用户的数据包不停在网络上循环发送，且跳数越来越大，造成网络资源的严重浪费。

发明内容

本发明目的在于提供一种采用树形拓扑关系避免路由环路的方法，避免在数据包传输过程中产生路由环路。

本发明的技术方案是：一种树形网络，包括一级节点，二级节点和三级节点，

所述一级节点为所述树形网络的根节点；

所述二级节点为所述一级节点的子节点，具有由所述一级节点分配的唯一拓扑序号；

所述三级节点为所述一级节点或所述二级节点的子树节点，每个三级节点具有由所述一级节点或所述二级节点分配的唯一拓扑序号；

一个或多个分支拓扑序列信息，每个分支拓扑序列信息以所述根节点的一个子树中各节点的拓扑序号的组合记录该子树中各节点的拓扑关系。

利用树形拓扑结构的描述可以构建网络中分层次的节点关系，适用于经常以广播形式发送报文的网络，为本发明中逐级分配节点的拓扑序号以及以树的形式精确记录分支拓扑序列信息提供前提。

本发明还提供一种在树形网络中创建分支拓扑序列信息的方法，包括：

步骤S1、在初始建立路由中分配拓扑序号并生成分支拓扑序列信息；

步骤S2、一级节点的子节点向其子树节点多播所述分支拓扑序列信息；

步骤S3、所述子树节点存储所述分支拓扑序列信息；

步骤S4、判断是否还存在未获得拓扑序号的节点，如果存在，进入步骤S5；

步骤S5、向所述未获得拓扑序号的节点补分配拓扑序号并更新分支拓扑序列信息，并返回步骤S3。

向网络中的节点分配数值型的拓扑序号，利用拓扑序号生成数值型分支拓扑序列信息，既能够体现节点间的拓扑层次关系也适合存储于报文中进行传输。

进一步地，根据权利要求2所述的一种在树形网络中创建分支拓扑序列信息的方法，步骤S1包括以下子步骤：

步骤S11、节点发送RREQ报文；

步骤S12、一级节点向其子节点回复RREP报文并分配拓扑序号；

步骤S13、二级节点向该二级节点的子节点回复RREP报文并分配拓扑序号，生成分支拓扑序列信息；

步骤S14、三级节点向其子节点回复RREP报文，完成初始建立路由。

优先利用现有技术中建立路由的过程进行拓扑序号的分配，使得拓扑序号的分配过程与现有技术的建立路由过程紧密结合，节省了节点能量。

进一步地，所述步骤S5包括以下子步骤：

步骤S51、所述未获得拓扑序号的节点发送分支拓扑序号请求报文；

步骤S52、根据分支拓扑序号请求报文所经过的节点记录当前的分支拓扑序列信息；

步骤S53、接收所述分支拓扑序号请求报文的节点判断自己是否具有分配拓扑序号的权限，如果是则进入步骤S54，如果否则进入步骤S56；

步骤S54、所述接收所述分支拓扑序号请求报文的节点判断自己是否具有分配拓扑序号的能力，如果是则进入步骤S55，如果否则进入步骤S56；

步骤S55、所述接收所述分支拓扑序号请求报文的节点向其子树节点发送携带有拓扑序号和分支拓扑序列信息的分支拓扑序号更新报文，进入步骤S57；

步骤S56、所述接收所述分支拓扑序号请求报文的节点转发所述分支拓扑序号请求报文，返回步骤S52；

步骤S57、所述未获得拓扑序号的节点获得所述拓扑序号。

在无法通过建立路由进行拓扑序号分配时，本发明设计了分支拓扑序号的分配过程，并将分配序号过程与更新分支拓扑序列信息同时通过同一报文完成，节省了链路中的传输数据量，提高了创建分支拓扑序列信息的效率。

进一步地，所述RREQ报文包括EN字段和RREQ序号字段，所述EN字段标识RREQ源节点是否拥有拓扑序号，所述RREQ序号字段用于存储RREQ报文源节点的拓扑序号；

所述RREP报文包括CN字段和分配拓扑序号字段，所述CN字段标识是否有权限分配拓扑序号并且是否有分配能力；所述分配拓扑序号字段用于存储分配的拓扑序号。

本发明只改变路由建立阶段的报文的格式使之既能够携带拓扑序号，分支拓扑序列信息，又能标识出报文发出节点的当前状态，使得报文传输数据信息的功能加强，并有利于接收节点根据发出节点的状态做出灵活的处理。

进一步地，所述分支拓扑序号请求报文和所述分支拓扑序号更新报文包括拓扑序列字段，所述拓扑序列字段用于存储当前的分支拓扑序列信息；

所述分支拓扑序号更新报文还包括节点序号字段，该节点序号字段用于存储所述分配的拓扑序号。

本发明增加了专门分配拓扑序号及传输分支拓扑序列信息的报文，并设置了相应的存储用字段，补充了利用路由建立的报文分配拓扑序号和生成分支拓扑序列信息的不完整，使得节点可以更有针对性地解析该专门性的报文中各字段的信息。

进一步地，步骤S2也利用所述分支拓扑序号更新报文多播所述分支拓扑序列信息。

利用分支拓扑序号，可以在路由建立阶段不额外增加新的报文种类而传递分支拓扑序列信息，节省节点能量，并有利于本发明技术方案扩展应用。

进一步地，如果接收所述分支拓扑序号请求报文或所述分支拓扑序号更新报文的节点再次收到重复的分支拓扑序号请求报文，则直接丢弃。

这样可以避免节点对重复的报文进行多次处理，节省了节点的能量，也减少了链路中冗余的数据量。

本发明提供的一种在树形网络中避免路由环路的方法包括：

源节点广播RREQ报文，收到该RREQ报文的节点查询所述分支拓扑序列信息；

判断源节点是否为所述收到该RREQ报文的节点的祖先节点；

如果否，则所述收到该RREQ报文的节点响应该RREQ报文；

如果是，则所述收到该RREQ报文的节点不响应该RREQ报文。

进一步地，所述响应该RREQ报文包括以下子步骤：

所述收到该RREQ报文的节点查询路由表是否有到目的节点的有效路由，如果有，则回复RREP报文；如果无，则转发该RREQ报文，并重复本步骤。

本发明的技术方案采用了创建分支拓扑序列信息来记录网络树形拓扑关系，在链路出错需重新建立路由时，可以根据分支拓扑序列信息分析出接收RREQ报文的节点与RREQ源节点之间的拓扑层次关系，并对其拥有的路由中依然会经过RREQ源节点的接收节点做出判断，然后令这样的接收节点不回复RREP报文，因此避免了源节点建立的路由具有路由环路的风险，减少了链路中的传输数据量，也节省了节点的能量。

附图说明

下面将参照附图并结合实施例对本发明进行具体说明。

图1为无线传感器网络的工作示意图；

图2为本发明优选实施例的网络结构示意图；

图3为本发明创建分支拓扑序列信息的基本方法流程图；

图4为本发明步骤S1的具体实施方式流程图；

图5为本发明步骤S3的具体实施方式流程图；

图6为本发明在树形网络中避免路由环路的方法流程图。

其中，图2中的实线表示网络拓扑结构，箭头表示数据汇聚的方向。

具体实施方式

本发明将网络以树形结构进行拓扑层次分配，将汇聚节点(sink节点)作为根节点，并将距离汇聚节点一跳的节点为根节点的子节点即根节点的下一层次节点；每个节点所引出的各分支都是该节点的子树，比如根节点的各个子节点分别引领各自的子树，距离根节点两跳及两跳以上的节点分别属于各个所述根节点的子节点的子树节点；上一跳节点是下一跳节点的父节点，一个节点的父节点及父节点以上层次的节点是该节点的祖先节点。通过这样的树形网络可以将节点之间传输数据的方式基于树形拓扑结构之中，为进一步描述拓扑层次关系提供了网络结构依据。

通过向节点分配唯一的拓扑序号，再通过所述拓扑序号记录树形网络中节点之间的拓扑关系，从而形成分支拓扑序列信息。当路由出错时，需要重建路由的源节点重新广播RREQ报文，收到RREQ报文的节点查询所述分支拓扑序列信息来比较自己与所述源节点之间的拓扑层次关系，从而确定处理所述RREQ报文的方式，这样就避免了不分辨拓扑关系而回复路由造成路由环路的风险。下面参照附图并借助本发明的实施例，对本发明的技术方案做详细描述。

在本发明中对路由建立过程所使用的RREQ报文、RREP报文进行了格式的改进。

RREQ报文增加了EN字段和RREQ序号字段，所述EN字段是由RREQ报文中的5位保留字段中启用了1位而得来，标识RREQ源节点是否拥有拓扑序号，报文中RREQ序号字段用于存储RREQ报文的源节点的拓扑序号。本发明中RREQ报文格式如下：

RREQ报文格式

具体地，类型为000，表示RREQ报文；EN为0则表示RREQ源节点无拓扑序号，为1表示RREQ源节点有拓扑序号；跳数，表示RREQ源节点到当前节点的跳数；源地址，即RREQ源节点的64比特IPv6地址接口标识符；目的地址，接收RREQ节点的64比特IPv6地址接口标识符；路由请求ID，标识RREQ报文的唯一性ID；最小LQI，从RREQ源节点到当前节点链路质量的最小值；RREQ序号存储RREQ源节点的拓扑序号。

RREP报文增加了CN字段和分配拓扑序号字段，所述CN字段由RREP报文中的5位保留字段中启用了2位而得来，标识是否有权限分配拓扑序号以及是否有分配能力；分配拓扑序号字段用于存储分配给RREP目的节点即RREQ源节点的拓扑序号。RREP的报文格式如下：

RREP报文格式

具体地，类型为001，表示RREP报文；CN，第一位表示RREP源节点是否有权限分配序号，0表示无权限，1表示有权限，第二位标识分配拓扑序号字段是否有效，也同时标识该RREP源节点是否有分配能力，0表示分配拓扑序号字段无效即该RREP源节点无分配能力，1表示分配拓扑序号字段有效即该RREP源节点有分配能力；跳数，表示RREP报文从RREP源节点到当前节点的跳数；源地址，RREP源节点即RREQ目的节点的64比特IPv6地址接口标识符；目的地址，接收RREP节点即RREQ源节点的64比特IPv6地址接口标识符；最小LQI，从RREP源节点到当前节点链路质量的最小值；分配拓扑序号，表示RREP源节点分配给RREP目的节点即RREQ源节点的拓扑序号。

在本发明中，将树形网络的所有节点划分为一级节点、二级节点和三级节点这三个等级，所述一级节点为所述树形网络的根节点；所述二级节点为所述一级节点的子节点，具有由所述一级节点分配的唯一拓扑序号；所述三级节点为所述一级节点或所述二级节点的子树节点，每个三级节点具有由所述一级节点或所述二级节点分配的唯一拓扑序号，也就是，网络中除一级节点和二级节点外，其余的节点被划分为三级节点，包括一级节点的子节点中除二级节点之外的节点和二级节点的子树节点。

一级节点按照一定的方法确定第一多个二级节点，具体见下文步骤S12的说明。一级节点还具有向二级节点、三级节点分配拓扑序号的权限和分配拓扑序号的能力。二级节点具有向其子树节点分配拓扑序号的权限和分配第二多个拓扑序号的能力。

所述第一多个和第二多个与设置的拓扑序号的位数和分配规则有关。例如，设置拓扑序号由8位(1字节)的二进制数值表示；拓扑序号的分配规则是：该8位二进制的拓扑序号被分为三个部分，第7位、第6至4位和第3至0位。当一级节点给二级节点分配时，第7位为0，且第3至0位也为0，仅变化第6至4位的值的拓扑序号，因此在本实施例中，所述第一多个至多为7个；当一级节点给三级节点分配时，从第7位为1，第6至4位、第3至0位都为0开始；当二级节点给其子树节点分配时，保持第7位、第6至4位数值分别与二级节点的拓扑序号相同位的值一致，仅变化第3至0位的值，因此在本实施例中，所述第二多个至多为15个。

如图2所示，一级节点(sink节点)确定了其子节点中的节点A、B、C、D、E、F、G 7个节点为二级节点，分别向这7个二级节点分配以下拓扑序号：0 001 0000、0 010 0000、0 011 0000、0 100 0000、0 101 0000、0 110 0000、0 1110000(本说明书为了方便区分拓扑序号的三部分各自的变化而添加了空格，实际中拓扑序号各位之间无空格，以下同)；对于一级节点的其他子节点如H节点被划分为三级节点，一级节点向其分配的拓扑序号从1 000 0000开始；二级节点比如节点A向其子树节点分配的拓扑序号分别为：0 001 0001、0 0010 010、0 001 0011、0 001 0100、……、0 001 1110、0 001 1111，可见二级节点具有至多15个拓扑序号的分配能力。

分支拓扑序列信息是通过所述拓扑序号分别记录所述树形网络中根节点的各子树的拓扑关系。本发明中分支拓扑序列信息可以以树的存储方式表达，将节点的拓扑序号按照节点的拓扑层次排列，上下层次节点之间利用1字节的0即00000000分隔。

例如图2中一级节点的节点A子树的拓扑关系由分支拓扑序列信息记录，利用树的存储方式表达为：

00010000 00000000 00010001 00010010 00000000 00010100 00010011(本说明书为了方便区分分支拓扑序列信息中各拓扑序号而添加了空格，实际中各拓扑序号之间无空格，以下同)；

节点B子树的分支拓扑序列信息表达为：

00100000 00000000 00100001；

节点C子树的分支拓扑序列信息表达为：

00110000 00000000 00110001 00000000 00110010 00000000 00110011

如图3，本发明还提供一种在树形网络中创建分支拓扑序列信息的方法，包括：

步骤S1、在初始建立路由阶段分配拓扑序号，也就是，所有无路由的节点需初始建立到汇聚节点的路由，本发明利用建立路由的过程进行拓扑序号的分配并通过分配拓扑序号生成当前的分支拓扑序列信息。

步骤S2、一级节点的子节点向其子树节点多播所述分支拓扑序列信息。将一级节点的子树当前的分支拓扑序列信息多播给该子树中的节点，这样每个子树节点在经过步骤S3后可以掌握所在根节点子树的整体拓扑结构以及自身与其他该根节点子树中的节点之间的拓扑层次关系。

步骤S3、所述子树节点存储所述分支拓扑序列信息。

步骤S4、判断是否还存在未获得拓扑序号的节点，如果网络中还存在未获得拓扑序号的节点，则进入步骤S5。

由于在初始建立路由阶段，从汇聚节点开始，依次由上一层次节点向其下一层次节点回复RREP报文从而逐步使每个节点都建立到汇聚节点的路由。但由于三级节点的分布情况不同，三级节点不一定都可以在建立路由阶段获得拓扑序号。比如一级节点的子节点中除二级节点之外的节点，不具有分配拓扑序号的权限，这样的三级节点的子节点在建立路由时无法获得拓扑序号；比如二级节点只能分配第二多个拓扑序号的能力，对于超过该第二多个的二级节点的子节点在建立路由时也无法获得拓扑序号。而且如果网络中还具有更多向下层次的三级节点，也无法在其父节点向其建立路由时获得拓扑序号，因此，其中距离二级节点两跳或两跳以上的节点，都需要通过步骤S5获得拓扑序号。如图2所示，节点M收到节点I给予的路由回复后建立路由，但是节点I没有分配序号的权限，因此节点M在路由建立结束后未获得拓扑序号。所以步骤S1中生成的分支拓扑序列信息只能记录已获得拓扑序号的节点之间的拓扑层次关系。

步骤S5、向所述未获得拓扑序号的节点补分配拓扑序号并更新分支拓扑序列信息，并返回步骤S3。本发明增加了拓扑序号交互报文，通过拓扑序号交互报文，节点可以请求拓扑序号或者向其它节点分配拓扑序号，并传递更新的分支拓扑序列信息。拓扑序号交互报文的格式如下：

拓扑序号交互报文格式

其中，类型：011，表示分支拓扑序号交互报文；SN：00表示分支拓扑序号请求报文，01表示分支拓扑序号更新报文，10表示路由通告报文，11保留；S/D：表示本报文中的地址字段是源地址或目的地址，0表示源地址，1表示目的地址；跳数：表示分支拓扑序号交互报文从源节点到目的节点的最大跳数。序列长度：表示分支拓扑序列字段的长度，长度字段的数值为几就代表分支拓扑序列实际长度为几字节；地址：用于存储发出该报文的源节点的64比特IPv6地址接口标识符或接收该报文的目的节点的64比特IPv6地址接口标识符；分支拓扑序号交互报文ID：分支拓扑序号交互报文的唯一性标识；节点序号：表示被分配的分支拓扑序号或者源节点的拓扑序号；分支拓扑序列：用于存储分支拓扑序列信息。

其中跳数字段所设置的最大跳数可以帮助支路的节点判断是否需要继续转发该报文，也就是说，交互报文每经过一次转发跳数值就减1，当某节点收到该交互报文并将跳数减1后得0时，判断出自己就是网络树形拓扑层次的末端节点(即叶节点)，这样该节点不需要再试图向前转发该报文，而直接停止转发，从而节约了节点的能量。跳数字段的值可以根据网络的大小预先设定，也可以根据路由表中存储的跳数设定。

当然，步骤S2也可以后于步骤S4、S5进行，即先判断是否存在未获得拓扑序号的节点，存在未获得拓扑序号的节点时先补分配拓扑序号并更新分支拓扑序列信息后，再执行步骤S2进行当前分支拓扑序列信息的多播。

进一步地，在步骤S2也可以利用多播分支拓扑序号更新报文的方式发送分支拓扑序列信息，比如图2中二级节点B启用分支拓扑序号交互报文，即类型字段置为011，并将SN字段置为01，表示分支拓扑序号更新报文；将生成的分支拓扑序列信息00100000 00000000 00100001存入分支拓扑序列字段，由于该分支拓扑序列信息为3字节，因此将代表3的二进制数值00000011存入序列长度字段；在S/D字段置0，表示地址字段为源地址；在地址字段存入该二级节点的64比特IPv6地址接口标识符；跳数置为1，这样在分支拓扑序号更新报文从二级节点B多播至其子节点时，跳数减1后得0，这样可以使二级节点B的子节点不再转发该报文。在本实施例中，节点B的子节点仅有节点K，因此节点B将携带分支拓扑序列信息00100000 00000000 00100001的分支拓扑序号更新报文发送给节点K。

如图4所示，步骤S1在初始建立路由阶段分配拓扑序号并生成分支拓扑序列信息还包括以下子步骤：

步骤S11、节点发送RREQ报文，其中RREQ报文中的EN字段置0，RREQ序号字段也置0，表示RREQ源节点无拓扑序号，且RREQ序号字段没有存储拓扑序号。

步骤S12、一级节点向其子节点回复RREP报文并通过RREP报文分配拓扑序号。其中，一级节点可以按照回复所述RREP报文的顺序确定二级节点比如将前第一多个RREP报文的目的节点作为二级节点，但不限于这种方式，也可以通过人为指定方式或以及一级节点发送控制包方式等。

优选地，如图2，拓扑序号用8位二进制数值表示，一级节点向前7个RREP报文的分配拓扑序号字段分别存入拓扑序号0 001 0000、0 010 0000、0 0110000、0 100 0000、0 101 0000、0 110 0000、0 111 0000，并将RREP报文的CN字段的第一位和第二位置1，表示一级节点既有权限分配拓扑序号，又有分配能力，RREP报文中的分配拓扑序号字段的值有效。分别接收前7个RREP报文的节点A、B、C、D、E、F、G成为二级节点，建立到一级节点的路由并将接收到的RREP报文中携带的拓扑序号记录为自己的拓扑序号，如节点A的拓扑序号为0 001 0000，节点B的拓扑序号为0 010 0000，节点C的拓扑序号为0 011 0000。

一级节点继续给其他子节点如图2中的节点H回复RREP报文并通过该RREP报文携带拓扑序号，并从1 000 0000开始分配。节点H属于三级节点，不具有向其子树节点分配拓扑序号的权限。

步骤S13、二级节点向其子节点回复RREP报文建立路由，将RREP报文中的CN字段的第一位置1，第二位置1，表示RREP源节点既具有分配权限，又具备分配能力，报文中分配拓扑序号字段的值有效，并将拓扑序号存入该RREP报文的分配拓扑序号字段。

如图2，二级节点A向其两个子节点I、J分别回复RREP报文，回复给节点I的RREP报文的分配拓扑序号字段为0 001 0001，回复给节点J的RREP报文的分配拓扑序号字段为0 001 0010；二级节点B向其子节点K回复的RREP报文的分配拓扑序号字段为0 010 0001；二级节点C向其子节点L回复的RREP报文的分配拓扑序号字段为0 011 0001。

并且，二级节点根据其各子节点发来的RREQ报文所记录的跳数和路径生成该二级节点、该二级节点的各子节点之间的分支拓扑序列信息。

需要指出的是，由于每个二级节点具有第二多个拓扑序号的分配能力，如果某个二级节点的子节点超过该第二多个，那么这时该二级节点已不再具有分配能力，这时二级节点所回复的RREP报文的CN字段的第一位置1，而第二位置0，表示该二级节点具有分配权限，但已无分配能力，该RREP报文中分配拓扑序号字段中的值无效，因此除第二多个之外的该二级节点的子节点无法通过RREP报文获得拓扑序号。另外，如果某个二级节点的子节点不足第二多个，则该二级节点在向其子节点全部回复分配有拓扑序号的RREP报文后，依然具有分配能力。

步骤S14、获得路由的三级节点如果接收到了该三级节点的子节点发来的RREQ请求建立路由，则该三级节点继续向其子节点回复RREP报文建立路由，但三级节点不具有分配拓扑序号的权限，所以由三级节点回复的RREP报文中的CN字段第一位和第二位都置0，表示该三级节点既无分配权限也无分配能力。并且，三级节点根据其各子节点发来的RREQ报文所记录的跳数和路径生成该三级节点及该三级节点的各子节点之间的分支拓扑序列信息。至此完成网络的初始路由建立过程。

如图5所示，步骤S4向所述未获得拓扑序号的节点补分配拓扑序号并更新分支拓扑序列信息还包括以下子步骤：

步骤S51、所述未获得拓扑序号的节点发送分支拓扑序号请求报文；

步骤S52、根据分支拓扑序号请求报文所经过的节点记录当前的分支拓扑序列信息；

步骤S53、接收所述分支拓扑序号请求报文的节点判断自己是否具有分配拓扑序号的权限，如果是则进入步骤S54，如果否则进入步骤S56；

步骤S54、所述接收所述分支拓扑序号请求报文的节点判断自己是否具有分配能力，如果是则进入步骤S55，如果否则进入步骤S56；

步骤S55、所述接收所述分支拓扑序号请求报文的节点向其子树节点发送携带有拓扑序号和分支拓扑序列信息的分支拓扑序号更新报文，进入步骤S57；

步骤S56、所述接收所述分支拓扑序号请求报文的节点转发所述分支拓扑序号请求报文，返回步骤S52；

步骤S57、所述未获得拓扑序号的节点获得所述拓扑序号。

例如，如图2所示，在路由建立过程中，由于节点N在路由建立中未被分配到拓扑序号。因此节点N执行步骤S5，首先执行步骤S51、节点N发送分支拓扑序号请求报文，该拓扑序号请求报文格式中，类型字段为011，SN字段置00，S/D字段置0，即地址字段为源地址，在地址字段写源节点即节点N的地址，节点序号字段、分支拓扑序列字段、序号长度字段均置0。该分支拓扑序号请求报文会经过节点J，在步骤S52中，该分支拓扑序号请求报文会记录当前的分支拓扑序列信息，比如当前的分支拓扑序列信息记录了节点A、I、J、的拓扑层次关系即00010000 00000000 00010001 00010010，并且记录节点N是节点J的下一层次节点。在步骤S53中，节点J判断出自己不具有分配权限，因此执行步骤S56将分支拓扑序号请求报文转发至节点A，节点A也执行步骤S52，记录当前的分支拓扑序列信息，比如当前的分支拓扑序列信息记录了节点A、I、J、M的拓扑层次关系即00010000 00000000 00010001 0001001000000000 00010100，并记录节点N所在的拓扑层次。节点A执行步骤S53，判断出自己具有分配权限，执行步骤S54，判断自己是否具有分配能力。

如果节点A分配的拓扑序号数量未达到第二多个，则此时节点A仍具有分配拓扑序号的能力，节点A执行步骤S55，节点A要分配拓扑序号0001 0011给节点N，启动分支拓扑序号更新报文，类型字段置011，SN字段置01，将拓扑序号0001 0011存入节点序号字段，将分支拓扑序号请求报文所记录的分支拓扑序列信息结合节点N的拓扑序号更新分支拓扑序列信息为：

00010000 00000000 00010001 00010010 00000000 00010100 00010011，并存入分支拓扑序列字段，由于该分支拓扑序列信息为7字节，因此将代表7的二进制数值00000111存入序列长度字段；在S/D字段置1，表示地址字段为目的节点地址即节点N的地址；在地址字段存入节点N的64比特IPv6地址接口标识符；跳数置为2，节点A向其子树的所有节点多播发送该分支拓扑序号更新报文。

如果节点A已经分配完第二多个拓扑序号，则此时节点A不具有分配能力，节点A执行步骤S56，继续向汇聚节点(sink节点)转发，sink节点经过步骤S53、S54的判断，具备分配权限和分配能力，因此由sink节点给节点N分配拓扑序号，并向节点A发送携带有拓扑序号和当前分支拓扑序列信息的分支拓扑序号更新报文，再由节点A向其子树的所有节点多播转发该分支拓扑序号更新报文。

步骤S57，节点N获得了拓扑序号00010011。

步骤S5中，节点A的子树的所有节点包括节点N在内，通过分支拓扑序号更新报文获得了最新的分支拓扑序列信息。因此均将其存储并更新为自己的分支拓扑序列信息。从而创建完毕节点A子树的分支拓扑序列信息。

进一步地，分支拓扑更新报文可以定时发送，从而保证子树节点能够实时获得最新的分支拓扑序列信息。

进一步地，如果接收所述分支拓扑序号请求报文或所述分支拓扑序号更新报文的节点再次收到重复的分支拓扑序号请求报文，则直接丢弃。由于发出分支拓扑序号交互报文时，可能会经过多条路径转发，因此接收该分支拓扑序号交互报文的节点可能会接收到多个重复的报文，为避免该节点重复处理同样的报文，该节点将再次收到的重复报文直接丢弃。

本发明增加了分支拓扑序号交互报文入口表来判断接收到的分支拓扑序号交互报文是否重复，该入口表格式为：

分支拓扑序号交互报文入口表

具体地，分支拓扑序号报文源地址：发起分支拓扑序号交互报文节点的64比特IPv6地址接口标识符；分支拓扑序号交互报文ID：用于存储分支拓扑序号交互报文中的分支拓扑序号交互报文ID字段的值；生存时间：该入口表项的生存时间。

将节点第一次收到分支拓扑序号交互报文，它会把该报文的源地址和分支拓扑序号交互报文ID分别存入入口表中分支拓扑序号报文源地址字段和分支拓扑序号交互报文ID字段，当该节点再次收到一个分支拓扑序号交互报文时，会将这个报文的源地址和ID分别与所述入口表中已存储的源地址和ID进行比较，如果二者的源地址和ID分别一样，那么该节点不会再次处理这个报文，而是直接丢弃。

当网络运行稳定后，如果有新节点加入该网络，重复上述步骤S1至S5，但是，由于网络的不断变化，该新节点的邻居节点所维护的路由表中如果不存在有效路由，那么该新节点的RREQ报文需要经过多跳才能获得RREP报文的回复，在本发明中，为了保持与初始建立路由时的一致性，设计距离二级节点两跳以上的节点只能通过步骤S5的分支拓扑序号请求和更新报文获得拓扑序号，而不能通过二级节点回复RREP报文来获得拓扑序号，即使该二级节点还具有分配能力。具体地，如果为该新节点回复RREP报文的节点恰好是还具有分配能力的二级节点时，二级节点通过判断接收到的RREQ的跳数值是否大于1来决定回复的RREP报文是否携带要分配的拓扑序号，如果跳数值大于1，则二级节点将要回复的RREP报文中的CN字段第一位置1，而将第二位置0，从而把分配拓扑序号的过程放在后续的步骤S5执行。

在经过上述创建分支拓扑序列信息的过程，网络进入数据通信过程，在通信过程中，若有节点例如图2中的节点O发送数据包未收到回复，则说明节点O到汇聚节点的链路出错，需要该节点重新广播RREQ报文，重新建立路由。

为了避免路由环路，本发明还提供一种在树形网络中避免路由环路的方法，如图6所示，包括：

S601、源节点广播RREQ报文，收到该RREQ报文的节点查询所述分支拓扑序列信息；

例如，节点O发送RREQ报文并附带了源节点O所拥有的拓扑序号00110010，并且将RREQ报文中的EN字段置1，表示该源节点O具有拓扑序号。接收到RREQ报文的节点L、P各自查询自己所存储的分支拓扑序列信息，即节点C子树的分支拓扑序列信息：

00110000 00000000 00110001 00000000 00110010 00000000 00110011。

S602、比对源节点拓扑序号和接收到RREQ报文的节点自身的拓扑序号在分支拓扑序列信息中的拓扑层次关系，判断源节点是否为所述收到该RREQ报文的节点的祖先节点。

S603、如果否，则所述收到该RREQ报文的节点响应该RREQ报文，该收到RREQ报文的节点查询路由表是否有到目的节点即汇聚节点的有效路由，若有有效路由，则直接回复RREP报文。若无有效路由，则进一步向其父节点转发，并查询当前接收RREQ报文的节点路由表的有无有效路由，直到具有有效路由的节点回复RREP报文。

例如图2中，在节点L的拓扑序号0011 0001处于节点O的拓扑序号00110010的上一层次，因此节点O不是节点L的祖先节点，因此节点L在其路由表具有有效路由时，向节点O回复RREP报文建立路由，在不具有有效路由时，向更上一层次节点C转发，直到有节点回复RREP报文。

根据RREQ报文的EN字段值为1，该RREP报文只用来建立路由而不需要分配拓扑序号，因此，即使回复RREP报文的节点是具有分配拓扑序号权限和能力的二级节点甚至一级节点，该RREP报文中的CN字段第一位置1，第二位置0。从而避免了RREQ源节点在收到RREP报文时再解析该报文分配拓扑序号字段，从而节省了节点能量。

S604、如果是，则所述收到该RREQ报文的节点不响应该RREQ报文。

例如节点P的拓扑序号0011 0011处于节点O的拓扑序号0011 0010的下一层次，节点O是节点P的祖先节点，因此节点P不查询路由表，不予回复RREP报文。在本发明中，节点P继续转发该RREQ报文，由于节点O是节点P的下一跳节点，因此该RREQ报文被转发回节点O，节点O收到该RREQ报文会发现此报文源于自己，因此将此RREQ报文丢弃。从而避免了现有技术中节点P无法判断路由表中的路由依然是须经过节点O的路径而为节点O建立路由后出现的数据传输的路由环路问题。

另外，分支拓扑序号交互报文还包括路由通告报文，即SN字段为10。路由通告报文主要用于拓扑序号失效时的通告，也就是，一个节点如果退出了网络，那么已经分配给它的拓扑序号需要通告失效，并且回收其拓扑序号以便重新分配给其他新加入网络的节点，此时就需要用到路由通告报文。

应当理解，以上借助优选实施例对本发明的技术方案进行的详细说明是示意性的而非限制性的。本领域的普通技术人员在阅读本发明说明书的基础上可以对各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。本发明的保护范围仅由随附权利要求书限定。