CN102185749B - Method for avoiding routing loop by adopting tree topology relationship - Google Patents

Abstract

The invention provides a method for avoiding routing loops by adopting tree-shaped topological relationships, establishing a tree-shaped network, assigning topological serial numbers to nodes, creating branch topology sequence information in the tree-shaped network, and avoiding routing loops in the tree-shaped network The method comprises: a source node broadcasts a RREQ message, and the node receiving the RREQ message inquires about the branch topology sequence information; judging whether the source node is the ancestor node of the node receiving the RREQ message; if not , then the node receiving the RREQ message responds to the RREQ message; if yes, the node receiving the RREQ message does not respond to the RREQ message. This method prevents the possibility of routing loops by analyzing the topological hierarchical relationship between nodes.

Description

Method of Avoiding Routing Loop Using Tree Topology

technical field

The invention relates to a routing method for a wireless sensor network. More specifically, the present invention relates to a wireless sensor network routing method using a tree topology relationship to avoid routing loops.

Background technique

Wireless Sensor Networks (WSNs) technology is an important part of modern communication technology and computer network technology. It is composed of a large number of cheap micro-sensor nodes distributed in the observation area, and forms a multi-hop network through wireless communication. self-organizing network. The sensor nodes cooperate to perceive the object information in the physical world (such as: temperature, humidity, acceleration, light intensity, etc.), and finally gather and fuse the data information to the server and observer.

In recent years, with the rise and development of the Internet of Things, wireless sensor network technology has received more attention, and it has gradually become an important guarantee for the integration of the physical world and the information world. At the same time, with the development of wireless sensor network technology, the application expansion has more and more broad space and bright prospects. At present, wireless sensor network technology has been widely used in intelligent transportation, smart grid, smart home, industrial control, environmental monitoring, medical care, military and other fields.

What Fig. 1 shows is the basic structure of the wireless sensor network. A wireless sensor network generally includes: sensor nodes (sensor nodes) such as W, X, Y, and Z, and sink nodes (sink nodes). The wireless sensor network interacts with various networks by connecting to a server through the sink node. Each sensor node (hereinafter referred to as a node unless otherwise specified) cooperates to sense information, gathers the information to the sink node through multiple hops, and then connects to the server for users to query, configure and communicate via various wireless or limited networks manage.

Wireless sensor networks generally have a large number of node devices. In many cases, each node needs to be configured with a globally unique IP address. Therefore, IPv6 technology has important application value in wireless sensor networks. But on the other hand, due to resource constraints and other reasons, the wireless sensor network cannot adapt to and satisfy the resources occupied by the IPv6 protocol stack (such as 128-bit IPv6 address), which is especially reflected in the design and implementation of routing protocols.

AODV (Ad hoc On-Demand Distance Vector Routing) routing protocol is one of the classic on-demand routing protocols in wireless sensor networks, but considering resource constraints and other factors, it is necessary to improve and optimize the AODV routing protocol. The MSRP (Micro Sensor Router Protocol) protocol optimizes the AODV protocol according to the above ideas, simplifies the routing interaction message format, and uses a 64-bit (8-byte) IPv6 address interface identifier, that is, the last 64 bits of the IPv6 address to replace the IPv6 address. The 128-bit (16-byte) address can effectively reduce the length of the address field, making the routing analysis process simpler and more effective, and meets the requirements of wireless sensor network energy and storage resources. Among them, 1 bit is 1 bit ( bit), 8 bits is 1 byte. In addition, the IEEE802.15.4 protocol stipulates two address formats, 64-bit address and 16-bit address. Among them, the use of 64-bit addresses can ensure the uniqueness of the address and realize the automatic configuration of node addresses, while the use of 16-bit addresses requires gateway allocation, and issues such as address duplication detection and address recycling need to be considered, which is complicated to implement, so 64-bit addresses are used. The bit IPv6 address interface identifier conforms to the requirements of the IEEE 802.15.4 standard for address fields. The following are the formats of routing request (RREQ) packets, routing reply (RREP) packets, and routing error (RERR) packets:

RREQ message format

The type is 000, indicating the type of RREQ message, and the hop count is the hop count from the source node to the current node carried by the RREQ message; the routing request ID is the unique identifier of the RREQ message; the source address is the address of the source node to send the RREQ The node of the message or the 64-bit (8-byte) interface identifier defined by IEEE802.15.4 of a certain RFD (Reduced Function Device) node of the node; the destination address is the address of the destination node, that is, the 64-bit ( 8 bytes) interface identifier; minimum LQI: the message carries the minimum value of the link quality metric value from the RREQ source node to the current node. LQI (Link Quality Indicator) is a parameter that measures the link quality of wireless sensor networks in compliance with the IEEE802.15.4 standard. Using this field can be used as the basis for route selection during route establishment, and the route established in this way can guarantee high link quality. The RFD node can be understood as a collection node that has no routing function and can only communicate with other nodes.

RREP packet format

The type is 001, indicating the type of RREP message; the hop count is the hop count from the source node to the current node carried by the RREP message; the source address is the IEEE802.15.4 definition of the node that initiated the RREP or a certain RFD node of the node The 64-bit interface identifier; the destination address is the node receiving the RREP, which corresponds to the 64-bit interface identifier defined by IEEE802.15.4 of the RREQ initiating node; the minimum LQI: the message carries the link quality metric from the RREP source node to the current node The minimum value.

RERR message format

Type: 010, indicating the type of RERR message; the number of unreachable addresses: the number of failed neighbor nodes detected by a node; unreachable destination address: the 64-bit interface identifier defined by IEEE802.15.4 of the failed neighbor nodes detected by a node . The number of unreachable addresses determines the number of unreachable destination addresses, so if there are more unreachable destination addresses, more unreachable destination addresses can be carried in the packet format.

Wherein the basic process of MSRP protocol establishment routing is that the node without routing broadcasts the routing request (RREQ) message to the neighbor node, and forwards it through the intermediate node, when the sink node receives the routing request message, it will initiate the routing request (RREQ) message to the neighbor node The node of the RREQ) message replies with a route reply (RREP) message, thereby establishing a route from the node to the sink node.

However, the MSRP protocol hands over all routing reply (RREP) messages to the sink node for processing, which not only greatly increases the load of the sink node, but also increases the time delay for the node to establish a route. Therefore, the existing technology further adopts an intermediate node to reply RREP to solve defects such as sink node overload and excessive routing delay, that is, if there is an available route to the sink node in the routing table of the intermediate node, the intermediate node directly Reply to RREP instead of forwarding to the sink node, and this method will inevitably bring about new problems of routing loops.

The so-called routing loop is a phenomenon in which a data packet is continuously transmitted between a series of nodes but cannot reach its intended destination node. Routing loops may occur when the routing information of two or more nodes incorrectly points to an effective path that cannot reach the destination node. For example, suppose there are nodes A, B, C, and E in the network, and the initial routes are C→B→A and E→B→A. At a certain moment, the link of Node B has an error and is in a failure state. In the process of sending data once, all the data packets sent by node C to node B cannot receive ACK reply, then node C will judge that the route to node B is wrong, so it starts to broadcast RREQ to find the route again, this RREQ is taken by node E Obtained, because node E does not know that node B is not working at this time, so it will reply RREP to node C, and the re-established route is C→E→B→A. However, this route still includes Node B which is no longer working, and is actually still an invalid route. Subsequently, node E also found that a large number of packets were lost during the process of sending data, so it initiated the broadcast RREQ process. At this time, node C has updated the route, and node B is no longer considered invalid by node C, so when node C receives After the RREQ sent by node E, reply RREP to it, so that node E has a new route that becomes E→C→E→B→A, whether the route provided by node C to node E still includes node E itself, Node C cannot judge before providing the route, so this process will continue to repeat, causing the user's data packets to be sent cyclically on the network, and the number of hops is getting larger and larger, resulting in a serious waste of network resources.

Contents of the invention

The purpose of the present invention is to provide a method for avoiding routing loops by adopting a tree topology relationship, so as to avoid routing loops during data packet transmission.

The technical solution of the present invention is: a tree-shaped network, including a first-level node, a second-level node and a third-level node,

The first-level node is the root node of the tree network;

The second-level node is a child node of the first-level node, and has a unique topology number assigned by the first-level node;

The third-level node is a subtree node of the first-level node or the second-level node, and each third-level node has a unique topology number assigned by the first-level node or the second-level node;

One or more branch topology sequence information, each branch topology sequence information records the topological relationship of each node in a subtree of the root node in combination with the topology sequence numbers of each node in a subtree of the root node.

The hierarchical node relationship in the network can be constructed by using the description of the tree topology structure, which is suitable for the network that often sends messages in the form of broadcast, for the topology sequence number of the nodes assigned step by step in the present invention and the accurate record of the branch topology sequence in the form of a tree Prerequisites for providing information.

The present invention also provides a method for creating branch topology sequence information in a tree network, including:

Step S1, assigning a topology sequence number and generating branch topology sequence information during the initial routing establishment;

Step S2, the child node of the first-level node multicasts the branch topology sequence information to its subtree nodes;

Step S3, the subtree node stores the branch topology sequence information;

Step S4, judging whether there are nodes that have not obtained the topology serial number, and if so, proceed to step S5;

Step S5, assign topological serial numbers to the nodes that have not obtained topological serial numbers and update branch topology sequence information, and return to step S3.

Assign numerical topological serial numbers to nodes in the network, and use the topological serial numbers to generate numerical branch topology sequence information, which can not only reflect the topological hierarchical relationship between nodes, but also be suitable for storage in messages for transmission.

Further, according to a method for creating branch topology sequence information in a tree network according to claim 2, step S1 includes the following sub-steps:

Step S11, the node sends a RREQ message;

Step S12, the first-level node replies the RREP message to its child node and assigns a topology number;

Step S13, the secondary node replies the RREP message to the child node of the secondary node and assigns a topology sequence number to generate branch topology sequence information;

Step S14, the third-level node replies the RREP message to its child nodes, and completes the initial route establishment.

The process of establishing routes in the prior art is preferentially used to allocate the topology serial numbers, so that the process of assigning the topology serial numbers is closely combined with the process of establishing routes in the prior art, saving node energy.

Further, the step S5 includes the following sub-steps:

Step S51, the node that has not obtained the topology sequence number sends a branch topology sequence number request message;

Step S52, recording the current branch topology sequence information according to the nodes through which the branch topology sequence number request message passes;

Step S53, the node receiving the branch topology serial number request message judges whether it has the authority to assign a topology serial number, if yes, proceed to step S54, otherwise proceed to step S56;

Step S54, the node receiving the branch topology serial number request message judges whether it has the ability to allocate topology serial numbers, if yes, proceed to step S55, if not, proceed to step S56;

Step S55, the node receiving the branch topology sequence number request message sends a branch topology sequence number update message carrying the topology sequence number and branch topology sequence information to its subtree node, and enters step S57;

Step S56, the node receiving the branch topology serial number request message forwards the branch topology serial number request message, and returns to step S52;

Step S57, the node that has not obtained the topology sequence number obtains the topology sequence number.

When the topology sequence number cannot be assigned by establishing a route, the present invention designs the distribution process of the branch topology sequence number, and completes the process of assigning the sequence number and updating the branch topology sequence information through the same message at the same time, saving the amount of transmission data in the link. Improved efficiency in creating branch topology sequence information.

Further, the RREQ message includes an EN field and a RREQ sequence number field, the EN field identifies whether the RREQ source node has a topology sequence number, and the RREQ sequence number field is used to store the topology sequence number of the RREQ message source node;

The RREP message includes a CN field and an allocation topology number field. The CN field identifies whether the allocation topology number is authorized and whether there is an allocation capability; the allocation topology number field is used to store the allocated topology number.

The present invention only changes the format of the message in the routing establishment stage so that it can not only carry the topology sequence number and branch topology sequence information, but also identify the current state of the node sending the message, so that the function of message transmission data information is strengthened, and it is beneficial to The receiving node makes flexible processing according to the status of the sending node.

Further, the branch topology sequence number request message and the branch topology sequence number update message include a topology sequence field, and the topology sequence field is used to store current branch topology sequence information;

The branch topology sequence number update message further includes a node sequence number field, which is used to store the assigned topology sequence number.

The present invention adds a special message for assigning topology numbers and transmitting branch topology sequence information, sets corresponding storage fields, supplements the incomplete distribution of topology numbers and generation of branch topology sequence information for messages established by routing, and makes nodes The information of each field in the specialized message can be parsed more specifically.

Further, step S2 also uses the branch topology serial number update message to multicast the branch topology sequence information.

By using the branch topology sequence number, the branch topology sequence information can be transmitted without additionally adding new message types in the routing establishment stage, saving node energy and facilitating the extended application of the technical solution of the present invention.

Further, if the node receiving the branch topology sequence number request message or the branch topology sequence number update message receives a duplicate branch topology sequence number request message again, it will discard it directly.

In this way, the node can avoid multiple processing of repeated messages, save the energy of the node, and also reduce the amount of redundant data in the link.

A method for avoiding routing loops in a tree network provided by the present invention includes:

The source node broadcasts the RREQ message, and the node receiving the RREQ message queries the branch topology sequence information;

Determine whether the source node is the ancestor node of the node that received the RREQ message;

If not, the node that receives the RREQ message responds to the RREQ message;

If yes, the node that receives the RREQ message does not respond to the RREQ message.

Further, said responding to the RREQ message includes the following substeps:

The node that receives the RREQ message inquires whether there is an effective route to the destination node in the routing table, if yes, then replies the RREP message; if not, then forwards the RREQ message, and repeats this step.

The technical solution of the present invention uses the creation of branch topology sequence information to record the network tree topology relationship. When a link needs to re-establish a route when a link fails, the node that receives the RREQ message and the RREQ source node can be analyzed according to the branch topology sequence information. The topological hierarchical relationship of the route, and make a judgment on the receiving node that still passes the RREQ source node in the route it owns, and then make such a receiving node not reply the RREP message, thus avoiding the routing loop established by the source node risk, reduces the amount of transmitted data in the link, and saves the energy of the nodes.

Description of drawings

The present invention will be specifically described below with reference to the accompanying drawings and examples.

Figure 1 is a working schematic diagram of a wireless sensor network;

Fig. 2 is a schematic diagram of a network structure of a preferred embodiment of the present invention;

Fig. 3 is the flow chart of the basic method of creating branch topology sequence information in the present invention;

FIG. 4 is a flow chart of a specific embodiment of step S1 of the present invention;

Fig. 5 is the specific implementation flow chart of step S3 of the present invention;

FIG. 6 is a flow chart of the method for avoiding routing loops in a tree network according to the present invention.

Wherein, the solid line in FIG. 2 represents the network topology, and the arrow represents the direction of data aggregation.

Detailed ways

In the present invention, the network is distributed in a tree-like topology, the sink node is used as the root node, and the node that is one hop away from the sink node is the child node of the root node, that is, the next layer node of the root node; each Each branch derived from a node is a subtree of the node. For example, each child node of the root node leads its own subtree, and nodes that are two or more hops away from the root node belong to the child nodes of each root node. Subtree node; the previous hop node is the parent node of the next hop node, and the parent node of a node and the nodes above the parent node are the ancestor nodes of the node. Through such a tree-shaped network, the way of data transmission between nodes can be based on the tree-shaped topology, which provides a network structure basis for further describing the topological hierarchical relationship.

The branch topology sequence information is formed by allocating unique topological serial numbers to the nodes, and then recording the topological relationship between the nodes in the tree network through the topological serial numbers. When the route is wrong, the source node that needs to rebuild the route re-broadcasts the RREQ message, and the node that receives the RREQ message queries the branch topology sequence information to compare the topology hierarchy between itself and the source node, so as to determine the processing step. The RREQ message is used to avoid the risk of routing loops caused by replying to routes without distinguishing topology relationships. The technical solutions of the present invention will be described in detail below with reference to the accompanying drawings and with the help of embodiments of the present invention.

In the present invention, the format of the RREQ message and RREP message used in the routing establishment process is improved.

The RREQ message adds the EN field and the RREQ sequence number field. The EN field is obtained by enabling 1 bit in the 5-bit reserved field in the RREQ message, and identifies whether the RREQ source node has a topology sequence number. The RREQ sequence number in the message The field is used to store the topology number of the source node of the RREQ message. RREQ message format is as follows among the present invention:

RREQ message format

Specifically, if the type is 000, it means the RREQ message; if EN is 0, it means that the RREQ source node has no topology number, and if it is 1, it means that the RREQ source node has a topology number; the number of hops means the number of hops from the RREQ source node to the current node; the source address , that is, the 64-bit IPv6 address interface identifier of the RREQ source node; the destination address, the 64-bit IPv6 address interface identifier of the receiving RREQ node; the routing request ID, which identifies the unique ID of the RREQ message; the minimum LQI, from the RREQ source node to The minimum value of the link quality of the current node; the RREQ serial number stores the topology serial number of the RREQ source node.

The RREP message adds a CN field and an allocation topology number field. The CN field is obtained by enabling 2 bits in the 5-bit reserved field in the RREP message. The topology sequence number field is used to store the topology sequence number assigned to the destination node of the RREP, that is, the source node of the RREQ. The format of the RREP message is as follows:

RREP packet format

Specifically, the type is 001, which means RREP message; CN, the first bit indicates whether the RREP source node has the right to assign the serial number, 0 means no authority, 1 means has the right, and the second bit indicates whether the allocation topology number field is valid, and at the same time Indicates whether the RREP source node has distribution capability. 0 indicates that the distribution topology sequence number field is invalid, that is, the RREP source node has no distribution capability; 1, that the distribution topology sequence number field is valid, that is, the RREP source node has distribution capability; The number of hops from the RREP source node to the current node; the source address, the 64-bit IPv6 address interface identifier of the RREP source node, that is, the RREQ destination node; the destination address, the 64-bit IPv6 address interface identifier of the receiving RREP node, that is, the RREQ source node; the minimum LQI , the minimum value of the link quality from the RREP source node to the current node; the assigned topology number indicates the topology number assigned by the RREP source node to the RREP destination node, that is, the RREQ source node.

In the present invention, all nodes of the tree-shaped network are divided into three grades of first-level nodes, second-level nodes and third-level nodes, the first-level nodes are the root nodes of the tree-shaped network; the second-level nodes It is a child node of the first-level node, and has a unique topological serial number assigned by the first-level node; the third-level node is a subtree node of the first-level node or the second-level node, and each third-level node It has a unique topological serial number assigned by the first-level node or the second-level node, that is, except for the first-level node and the second-level node, the remaining nodes in the network are divided into third-level nodes, including the children of the first-level node Nodes other than secondary nodes and subtree nodes of secondary nodes in the node.

The first-level node determines the first plurality of second-level nodes according to a certain method, see the description of step S12 below for details. The first-level nodes also have the authority to assign topological serial numbers to the second-level nodes and third-level nodes and the ability to assign topological serial numbers. The secondary node has the right to assign topological sequence numbers to its subtree nodes and the ability to assign a second plurality of topological sequence numbers.

The first multiple and the second multiple are related to the number of digits of the set topology serial number and the allocation rule. For example, set the topology serial number to be represented by an 8-bit (1 byte) binary value; the distribution rule of the topology serial number is: the 8-bit binary topology serial number is divided into three parts, the 7th bit, the 6th to 4th bits and the 3 to 0 digits. When the first-level node is assigned to the second-level node, the seventh bit is 0, and the third to zero bits are also 0, and only the topological sequence number of the value of the sixth to fourth bits is changed. Therefore, in this embodiment, the first There are at most 7 ones; when a first-level node is assigned to a third-level node, the seventh bit is 1, the sixth to fourth, and the third to 0th are all 0; when the second level node is assigned to its subtree When assigning nodes, keep the 7th, 6th to 4th digits respectively consistent with the values of the topological serial numbers of the secondary nodes, and only change the 3rd to 0th values, so in this embodiment, the second Multiple up to 15.

As shown in Figure 2, the first-level node (sink node) determines that seven nodes of its child nodes, A, B, C, D, E, F, and G, are second-level nodes, and the seven second-level nodes are respectively sent Assign the following topological serial numbers: 0 001 0000, 0 010 0000, 0 011 0000, 0 100 0000, 0 101 0000, 0 110 0000, 0 1110000 (this manual adds spaces for the convenience of distinguishing the changes of the three parts of the topological serial number, In practice, there are no spaces between the topological serial numbers, the same below); for other child nodes of the first-level nodes such as H nodes, they are divided into third-level nodes, and the topological serial numbers assigned to them by the first-level nodes start from 1 000 0000; the second-level nodes For example, the topological serial numbers assigned by node A to its subtree nodes are: 0 001 0001, 0 0010 010, 0 001 0011, 0 001 0100, ..., 0 001 1110, 0 001 1111. It can be seen that the secondary nodes have at most 15 The ability to assign topology numbers.

The branch topology sequence information is to respectively record the topology relationship of each subtree of the root node in the tree network through the topology sequence number. In the present invention, branch topological sequence information can be expressed in a tree storage manner, and the topological serial numbers of the nodes are arranged according to the topological levels of the nodes, and the nodes of the upper and lower levels are separated by 0 of 1 byte, that is, 00000000.

For example, the topological relationship of the node A subtree of the first-level node in Figure 2 is recorded by the branch topology sequence information, and expressed as:

00010000 00000000 00010001 00010010 00000000 00010100 00010011 (in this manual, spaces are added for the convenience of distinguishing each topology number in the branch topology sequence information. In practice, there are no spaces between each topology number, the same below);

The branch topology sequence information of node B subtree is expressed as:

00100000 00000000 00100001;

The branch topology sequence information of node C subtree is expressed as:

00110000 00000000 00110001 00000000 00110010 00000000 00110011

As shown in Figure 3, the present invention also provides a method for creating branch topology sequence information in a tree network, including:

Step S1, distribute the topology sequence number in the stage of initially establishing the route, that is, all nodes without routes need to initially establish the route to the aggregation node, the present invention uses the process of establishing the route to distribute the topology sequence number and generate the current branch by assigning the topology sequence number Topological sequence information.

Step S2, the child nodes of the primary node multicast the branch topology sequence information to their subtree nodes. Multicast the current branch topology sequence information of the subtree of the first-level node to the nodes in the subtree, so that each subtree node can grasp the overall topology structure of the root node subtree and the relationship between itself and other root nodes after step S3. The topological hierarchical relationship between nodes in the node subtree.

Step S3, the subtree node stores the branch topology sequence information.

Step S4 , judging whether there are nodes that have not obtained topological serial numbers, and if there are still nodes in the network that have not obtained topological serial numbers, go to step S5 .

Since in the initial route establishment stage, starting from the aggregation node, the upper layer nodes reply RREP messages to the lower layer nodes in turn, so that each node gradually establishes a route to the aggregation node. However, due to the different distribution of the third-level nodes, the third-level nodes may not all be able to obtain the topology sequence number during the route establishment phase. For example, nodes other than the second-level nodes among the sub-nodes of the first-level nodes do not have the authority to assign topological serial numbers, and the sub-nodes of such third-level nodes cannot obtain the topological serial numbers when establishing routes; for example, the second-level nodes can only assign the first With the capability of two or more topological serial numbers, the child nodes of the secondary nodes exceeding the second multiple cannot obtain the topological serial numbers when establishing routes. Moreover, if there are more third-level nodes in the downward hierarchy in the network, it is impossible to obtain the topology number when its parent node establishes a route to it. Therefore, nodes that are two or more hops away from the second-level node need to pass Step S5 obtains the topology number. As shown in Figure 2, node M establishes a route after receiving the route reply from node I, but node I does not have the authority to assign serial numbers, so node M does not obtain the topology serial number after the route is established. Therefore, the branch topology sequence information generated in step S1 can only record the topological hierarchical relationship between the nodes that have obtained the topology sequence numbers.

Step S5, assign topological serial numbers to the nodes that have not obtained topological serial numbers and update branch topology sequence information, and return to step S3. The invention adds a topological serial number interactive message, through which a node can request a topological serial number or distribute a topological serial number to other nodes, and transmit updated branch topology serial information. The format of the topology sequence number interaction message is as follows:

Topology Sequence Number Interaction Message Format

Among them, Type: 011, indicates the branch topology sequence number interaction message; SN: 00 represents the branch topology sequence number request message, 01 represents the branch topology sequence number update message, 10 represents the route notification message, and 11 is reserved; S/D: represents the current The address field in the message is the source address or destination address, 0 means the source address, 1 means the destination address; hop count: indicates the maximum hop number of the branch topology sequence number interaction message from the source node to the destination node. Sequence length: Indicates the length of the branch topology sequence field, the value of the length field represents the actual length of the branch topology sequence in bytes; address: used to store the 64-bit IPv6 address interface identifier or The 64-bit IPv6 address interface identifier of the destination node receiving the message; the branch topology serial number interaction message ID: the unique identification of the branch topology serial number interaction message; the node serial number: indicating the assigned branch topology serial number or the topology of the source node Serial number; branch topology sequence: used to store branch topology sequence information.

Among them, the maximum hop count set by the hop count field can help the nodes of the branch to judge whether to continue forwarding the message. When the text and the hop count are reduced by 1 to get 0, it is judged that it is the end node (ie leaf node) of the network tree topology level, so that the node does not need to try to forward the message forward, but directly stops forwarding, thus Save the energy of the node. The value of the hop count field can be preset according to the size of the network, or can be set according to the hop count stored in the routing table.

Of course, step S2 can also be carried out after steps S4 and S5, that is, first determine whether there are nodes that have not obtained the topology number, and if there is a node that has not obtained the topology number, first assign the topology number and update the branch topology sequence information, and then execute the step S2 multicasts the current branch topology sequence information.

Further, in step S2, the branch topology sequence information can also be sent in the form of a multicast branch topology sequence number update message, for example, in Figure 2, the secondary node B enables the branch topology sequence number interaction message, that is, the type field is set to 011, and the The SN field is set to 01, indicating that the branch topology sequence number is updated; the generated branch topology sequence information 00100000 00000000 00100001 is stored in the branch topology sequence field. Since the branch topology sequence information is 3 bytes, it will represent the binary value of 3 00000011 Store in the sequence length field; set 0 in the S/D field, indicating that the address field is the source address; store the 64-bit IPv6 address interface identifier of the secondary node in the address field; set the hop count to 1, so that the branch topology sequence number When the update message is multicast from the secondary node B to its child nodes, the hop count is reduced by 1 to get 0, so that the child nodes of the secondary node B will no longer forward the message. In this embodiment, the only child node of node B is node K, so node B sends a branch topology sequence number update message carrying branch topology sequence information 00100000 00000000 00100001 to node K.

As shown in Figure 4, step S1 assigns the topology sequence number and generates the branch topology sequence information in the initial route establishment stage, which also includes the following sub-steps:

Step S11, the node sends a RREQ message, wherein the EN field in the RREQ message is set to 0, and the RREQ sequence number field is also set to 0, indicating that the source node of the RREQ has no topology sequence number, and the RREQ sequence number field does not store a topology sequence number.

Step S12, the first-level node replies the RREP message to its child nodes and distributes the topology sequence number through the RREP message. Among them, the first-level node can determine the second-level node according to the order in which the RREP message is replied. For example, the destination node of the first multiple RREP messages is used as the second-level node, but it is not limited to this method, and can also be manually specified. Or and the way the first-level node sends the control packet, etc.

Preferably, as shown in Figure 2, the topology sequence number is represented by an 8-bit binary value, and the topological sequence number fields of the first 7 RREP messages are stored in the topology sequence number 0 001 0000, 0 010 0000, 0 0110000, 0 100 0000 respectively . The value of the Allocation Topology Sequence Number field in is valid. The nodes A, B, C, D, E, F, and G that received the first 7 RREP messages respectively become the second-level nodes, establish routes to the first-level nodes, and record the topology sequence numbers carried in the received RREP messages as Its own topology number, such as the topology number of node A is 0 001 0000, the topology number of node B is 0 010 0000, and the topology number of node C is 0 011 0000.

The first-level node continues to reply RREP messages to other child nodes as shown in node H in Figure 2, and carries the topology sequence number through the RREP message, and starts to allocate from 1 000 0000. Node H is a third-level node and does not have the right to assign topological numbers to its subtree nodes.

Step S13, the secondary node replies the RREP message to its child node to establish a route, and sets the first position of the CN field in the RREP message to 1, and the second position to 1, indicating that the RREP source node has both allocation authority and allocation capability, The value of the allocated topology sequence number field in the message is valid, and the topology sequence number is stored in the allocated topology sequence number field of the RREP message.

As shown in Figure 2, the secondary node A replies RREP messages to its two child nodes I and J respectively, the distribution topology sequence number field of the RREP message replying to node I is 0 001 0001, and the distribution of the RREP message replying to node J The topology sequence number field is 0 001 0010; the distribution topology sequence number field of the RREP message that the secondary node B replies to its child node K is 0 010 0001; the distribution topology sequence number of the RREP message that the secondary node C replies to its child node L The field is 0 011 0001.

Moreover, the secondary node generates branch topology sequence information between the secondary node and its child nodes according to the hop count and path recorded in the RREQ message sent by its child nodes.

It should be pointed out that since each secondary node has the ability to allocate a second number of topological serial numbers, if a child node of a certain secondary node exceeds the second multiple, then the secondary node no longer has the ability to allocate At this time, the first position of the CN field of the RREP message replied by the secondary node is 1, and the second position is 0, indicating that the secondary node has the allocation authority, but has no allocation ability, and the allocation topology in the RREP message The value in the sequence number field is invalid, so the child nodes of the secondary node except the second one cannot obtain the topology sequence number through the RREP message. In addition, if a secondary node has less than the second largest number of child nodes, the secondary node still has the allocation capability after replying to all its child nodes with RREP messages assigned topology numbers.

Step S14, if the third-level node that has obtained the route receives the RREQ request from the child node of the third-level node to establish the route, the third-level node will continue to reply the RREP message to its child node to establish the route, but the third-level node does not have The right to allocate topology serial numbers, so the first and second bits of the CN field in the RREP message replied by the third-level node are both set to 0, indicating that the third-level node has neither allocation authority nor allocation ability. Moreover, the third-level node generates branch topology sequence information between the third-level node and each child node of the third-level node according to the hop count and the path recorded in the RREQ message sent by each child node of the third-level node. So far, the initial route establishment process of the network is completed.

As shown in Figure 5, step S4 assigns a topological serial number to the node that has not obtained a topological serial number and updates branch topology sequence information also includes the following sub-steps:

Step S51, the node that has not obtained the topology sequence number sends a branch topology sequence number request message;

Step S52, recording the current branch topology sequence information according to the nodes through which the branch topology sequence number request message passes;

Step S53, the node receiving the branch topology serial number request message judges whether it has the authority to assign a topology serial number, if yes, proceed to step S54, otherwise proceed to step S56;

Step S54, the node receiving the branch topology sequence number request message judges whether it has the allocation capability, if yes, proceed to step S55, if not, proceed to step S56;

Step S55, the node receiving the branch topology sequence number request message sends a branch topology sequence number update message carrying the topology sequence number and branch topology sequence information to its subtree node, and enters step S57;

Step S56, the node receiving the branch topology serial number request message forwards the branch topology serial number request message, and returns to step S52;

Step S57, the node that has not obtained the topology sequence number obtains the topology sequence number.

For example, as shown in FIG. 2 , during the route establishment process, node N is not assigned a topology number during route establishment. Therefore, node N executes step S5, first executes step S51, and node N sends a branch topology sequence number request message. In the topology sequence number request message format, the type field is 011, the SN field is set to 00, and the S/D field is set to 0, which is the address The field is the source address, and the address of the source node, that is, node N, is written in the address field, and the node sequence number field, branch topology sequence field, and sequence number length field are all set to 0. The branch topology sequence number request message will pass through node J, and in step S52, the branch topology sequence number request message will record the current branch topology sequence information, such as the current branch topology sequence information records nodes A, I, J, The topological hierarchical relationship is 00010000 00000000 00010001 00010010, and it is recorded that node N is the next level node of node J. In step S53, node J judges that it does not have the allocation authority, so it executes step S56 to forward the branch topology sequence number request message to node A, and node A also executes step S52 to record the current branch topology sequence information, such as the current branch Topological sequence information records the topological hierarchical relationship of nodes A, I, J, and M, namely 00010000 00000000 00010001 0001001000000000 00010100, and records the topological hierarchy of node N. Node A executes step S53 to determine whether it has the allocation authority, and executes step S54 to determine whether it has the allocation ability.

If the number of topology serial numbers allocated by node A does not reach the second most, then node A still has the ability to allocate topology serial numbers at this time, node A executes step S55, node A will assign topology serial numbers 0001 0011 to node N, and start branch topology serial numbers Update the message, set the type field to 011, set the SN field to 01, store the topology sequence number 0001 0011 in the node sequence number field, and combine the branch topology sequence information recorded in the branch topology sequence number request message with the topology sequence number of node N to update the branch topology sequence information for:

00010000 00000000 00010001 00010010 00000000 00010100 00010011, and store it in the branch topology sequence field. Since the branch topology sequence information is 7 bytes, the binary value 00000111 representing 7 is stored in the sequence length field; set 1 in the S/D field, indicating The address field is the address of the destination node, that is, the address of node N; the 64-bit IPv6 address interface identifier of node N is stored in the address field; the hop count is set to 2, and node A multicasts the branch topology sequence number to all nodes of its subtree Update message.

If node A has allocated the second plurality of topology serial numbers, then node A does not have the ability to allocate at this time, node A executes step S56, and continues to forward to the sink node (sink node), and the sink node is judged by steps S53 and S54, and has Allocate permissions and capabilities, so the sink node assigns a topology number to node N, and sends a branch topology number update message carrying the topology number and the current branch topology sequence information to node A, and then node A sends a message to all its subtrees. The node multicasts and forwards the branch topology sequence number update message.

In step S57, the node N obtains the topology number 00010011.

In step S5, all nodes in the subtree of node A including node N obtain the latest branch topology sequence information through the branch topology sequence number update message. Therefore, it is stored and updated as its own branch topology sequence information. Thus, the branch topology sequence information of the node A subtree is created.

Furthermore, the branch topology update message can be sent regularly, so as to ensure that the subtree nodes can obtain the latest branch topology sequence information in real time.

Further, if the node receiving the branch topology sequence number request message or the branch topology sequence number update message receives a duplicate branch topology sequence number request message again, it will discard it directly. Since the branch topology sequence number interaction message is sent, it may be forwarded through multiple paths, so the node receiving the branch topology sequence number interaction message may receive multiple duplicate messages. To avoid the node repeatedly processing the same message , the node directly discards the duplicate message received again.

The present invention adds a branch topology serial number interactive message entry table to judge whether the received branch topology serial number interactive message is repeated, and the entry table format is:

Branch Topology Sequence Number Interaction Message Entry Table

Specifically, the source address of the branch topology sequence number message: the 64-bit IPv6 address interface identifier of the node that initiates the branch topology sequence number interaction message; the branch topology sequence number interaction message ID: used to store the branch topology sequence number in the branch topology sequence number interaction message The value of the ID field of the interaction message; lifetime: the lifetime of the entry entry.

When the node receives the branch topology sequence number interaction message for the first time, it will store the source address of the message and the branch topology sequence number interaction message ID in the entry table respectively in the source address field of the branch topology sequence number message and the branch topology sequence number interaction Message ID field, when the node receives a branch topology sequence number interaction message again, it will compare the source address and ID of this message with the source address and ID stored in the entry table, if the two source address and ID are the same respectively, then the node will not process the message again, but discard it directly.

When the network is running stably, if a new node joins the network, repeat the above steps S1 to S5. The RREQ message of the node needs to go through multiple hops to obtain the reply of the RREP message. In the present invention, in order to maintain the consistency with the initial route establishment, the design distance from the node of the secondary node more than two hops can only pass through the branch of step S5 The topology sequence number is obtained through the topology sequence number request and update messages, but the topology sequence number cannot be obtained through the reply of the RREP message by the secondary node, even if the secondary node still has the allocation capability. Specifically, if the node that replies the RREP message for the new node happens to be a second-level node that still has the ability to allocate, the second-level node determines whether the returned RREP message carries The topology number to be assigned, if the hop value is greater than 1, the secondary node will set the first position of the CN field in the RREP message to be replied as 1, and set the second position to 0, so that the process of assigning the topology number is placed in the next step S5 executes.

After the above-mentioned process of creating branch topology sequence information, the network enters the data communication process. During the communication process, if a node such as node O in Figure 2 sends a data packet but does not receive a reply, it means that the link between node O and the sink node If an error occurs, the node needs to re-broadcast the RREQ message to re-establish the route.

In order to avoid routing loops, the present invention also provides a method for avoiding routing loops in a tree network, as shown in Figure 6, including:

S601. The source node broadcasts a RREQ message, and the node receiving the RREQ message queries the branch topology sequence information;

For example, node O sends a RREQ message and attaches the topology number 00110010 owned by the source node O, and sets the EN field in the RREQ message to 1, indicating that the source node O has a topology number. Nodes L and P receiving the RREQ message query their own stored branch topology sequence information, that is, the branch topology sequence information of the subtree of node C:

00110000 00000000 00110001 00000000 00110010 00000000 00110011.

S602. Compare the topology number of the source node with the topology hierarchy of the node receiving the RREQ message in the branch topology sequence information, and determine whether the source node is an ancestor node of the node receiving the RREQ message.

S603. If not, the node that received the RREQ message responds to the RREQ message, and the node that receives the RREQ message queries the routing table to see if there is an effective route to the destination node, that is, the sink node. If there is an effective route, Then reply the RREP message directly. If there is no effective route, then further forward to its parent node, and query whether there is an effective route in the routing table of the node currently receiving the RREQ message, until the node with an effective route replies to the RREP message.

For example, in Figure 2, the topology number 0011 0001 of node L is at the upper level of node O's topology number 00110010, so node O is not the ancestor node of node L, so node L sends to node O when its routing table has a valid route. Reply the RREP message to establish a route, and if there is no valid route, forward it to the node C at the higher level until a node replies with the RREP message.

According to the value of the EN field of the RREQ message is 1, the RREP message is only used to establish a route and does not need to assign a topology number. For a level node, the first position of the CN field in the RREP message is 1, and the second position is 0. Therefore, it is avoided that the RREQ source node parses the packet allocation topology sequence number field when receiving the RREP packet, thereby saving node energy.

S604. If yes, the node receiving the RREQ message does not respond to the RREQ message.

For example, the topology number 0011 0011 of node P is at the next level of the topology number 0011 0010 of node O, and node O is the ancestor node of node P, so node P does not query the routing table and does not reply RREP messages. In the present invention, the node P continues to forward the RREQ message. Since the node O is the next hop node of the node P, the RREQ message is forwarded back to the node O, and the node O will find the message when receiving the RREQ message It originates from itself, so the RREQ message is discarded. Thus avoiding the routing loop problem of data transmission that occurs after the node P cannot judge that the route in the routing table still needs to pass through the node O and establishes a route for the node O in the prior art.

In addition, the branch topology sequence number interaction message also includes a route notification message, that is, the SN field is 10. The route notification message is mainly used for notification when the topology number is invalid, that is, if a node exits the network, the topology number already assigned to it needs to be notified to be invalid, and its topology number should be reclaimed for redistribution to other newly joined networks. node, at this time, the route advertisement message is needed.

It should be understood that the above detailed description of the technical solution of the present invention with the aid of preferred embodiments is illustrative rather than restrictive. Those skilled in the art can modify the technical solutions recorded in each embodiment on the basis of reading the description of the present invention, or perform equivalent replacements for some of the technical features; and these modifications or replacements do not make the corresponding technical solutions Essentially deviate from the spirit and scope of the technical solutions of the various embodiments of the present invention. The scope of protection of the present invention is limited only by the appended claims.

Claims (9)

1. a method that creates branch's topological sequences information in tree network system, is characterized in that,

Described tree network system comprises one-level node, two-level node and three grades of nodes,

The root node that described one-level node is described tree network;

Described two-level node is the child node of described one-level node, has the unique topological sequence number of being distributed by described one-level node;

The subtree node that described three grades of nodes are described one-level node or described two-level node, each three grades of nodes have the unique topological sequence number of being distributed by described one-level node or described two-level node;

One or more branches topological sequences information, each branch topological sequences information records the topological relation of each node in this subtree with the combination of the topological sequence number of each node in a subtree of described root node;

The concrete steps that create branch's topological sequences information comprise:

Step S1, in initially setting up route, distribute topological sequence number and generate branch's topological sequences information;

The child node of step S2, one-level node is to branch's topological sequences information described in its subtree node multicast;

Step S3, described subtree node are stored described branch topological sequences information;

Step S4, judge whether also to exist the node that does not obtain topological sequence number, if existed, enter step S5, if there is no, finish;

Step S5, distribute topological sequence number and upgrade branch's topological sequences information to the described node that does not obtain topological sequence number, and return to step S3.

2. a kind of method that creates branch's topological sequences information in tree network system according to claim 1, is characterized in that, step S1 comprises following sub-step:

Step S11, node send RREQ message;

Step S12, one-level node are replied RREP message and distribute topological sequence number to its child node;

Step S13, two-level node are replied RREP message and distribute topological sequence number to the child node of this two-level node, generate branch's topological sequences information;

Step S14, three grades of nodes are replied RREP message to its child node, complete and initially set up route.

3. a kind of method that creates branch's topological sequences information in tree network system according to claim 1, is characterized in that, described step S5 comprises following sub-step:

Step S51, the described node that does not obtain topological sequence number send branch's topology sequence number request message;

Step S52, branch topology sequence number request message the current branch's topological sequences information of nodes records of process;

Step S53, the node that receives described branch topology sequence number request message judges the authority oneself whether with the topological sequence number of distribution, if yes then enter step S54, if otherwise enter step S56;

The node of step S54, the described branch of described reception topology sequence number request message judges oneself whether to have the ability of distributing topological sequence number, if yes then enter step S55, if otherwise enter step S56;

The node of step S55, the described branch of described reception topology sequence number request message sends the branch's topology sequence number renewal message that carries topological sequence number and branch's topological sequences information to its subtree node, enter step S57;

The node of step S56, the described branch of described reception topology sequence number request message forwards described branch topology sequence number request message, returns to step S52;

Step S57, the described node that does not obtain topological sequence number obtain described topological sequence number.

4. a kind of method that creates branch's topological sequences information in tree network system according to claim 2, is characterized in that,

Described RREQ message comprises EN field and RREQ sequence number field, and whether described EN field identification RREQ source node has topological sequence number, the topological sequence number of described RREQ sequence number field for storing RREQ message source node;

Described RREP message comprises CN field and the topological sequence number field of distribution, and whether described CN field identification has right assignment topology sequence number and whether have distribution capability; The topological sequence number field of described distribution is for the topological sequence number of memory allocation.

5. a kind of method that creates branch's topological sequences information in tree network system according to claim 3, is characterized in that,

Described branch topology sequence number request message and described branch topology sequence number are upgraded message and are comprised topological sequences field, and described topological sequences field is for storing current branch's topological sequences information;

Described branch topology sequence number is upgraded message and is also comprised node ID field, and this node ID field is for storing the topological sequence number of described distribution.

6. a kind of method that creates branch's topological sequences information in tree network system according to claim 5, is characterized in that,

Step S2 also utilizes described branch topology sequence number to upgrade branch's topological sequences information described in message multicast.

7. a kind of method that creates branch's topological sequences information in tree network system according to claim 4, is characterized in that,

Again receive branch's topology sequence number request message of repetition if receive the node of described branch topology sequence number request message or described branch topology sequence number renewal message, directly abandon.

8. a method of avoiding route loop in tree network system, is characterized in that,

Described tree network system comprises one-level node, two-level node and three grades of nodes,

The root node that described one-level node is described tree network;

Described two-level node is the child node of described one-level node, has the unique topological sequence number of being distributed by described one-level node;

The subtree node that described three grades of nodes are described one-level node or described two-level node, each three grades of nodes have the unique topological sequence number of being distributed by described one-level node or described two-level node;

One or more branches topological sequences information, each branch topological sequences information records the topological relation of each node in this subtree with the combination of the topological sequence number of each node in a subtree of described root node;

Avoid the concrete steps of route loop to comprise:

Source node broadcast RREQ message, receives branch's topological sequences information described in the querying node of this RREQ message;

Judge that source node receives the ancestor node of the node of this RREQ message described in being whether;

If not, receive that the node of this RREQ message responds this RREQ message described in;

If so, receive that the node of this RREQ message does not respond this RREQ message described in.

9. a kind of method of avoiding route loop according to claim 8, is characterized in that, this RREQ message of described response comprises following sub-step:

Whether the described querying node routing table of receiving this RREQ message has the effective routing to destination node, if had, replys RREP message; If nothing, forwards this RREQ message, the duplicate step of laying equal stress on.