KR100879725B1 - Method and apparatus for tree routing in wireless networks - Google Patents

Abstract

The disclosed method relates to a routing method and apparatus in a wireless network. The disclosed method comprises the steps of (a) determining whether the destination address of the frame matches the address of a neighbor node; (B) determining whether there is a neighbor node having a node corresponding to the destination address as a destination when the destination address of the frame does not match the address of the neighbor node; If there is a neighbor node having the destination address as a descendant, transmitting a frame to a selected neighbor node among the existing neighbor nodes. According to the present invention, routing can be efficiently performed with fewer hops, and there is an advantage of maximizing network performance while reducing communication costs.

Zigbee, routing, tree

Description

Method and Device for Tree Routing In Wireless Network

1 and 2 are schematic diagrams illustrating a Zigbee network environment to which addresses are assigned.

3 is a flow chart illustrating a conventional tree routing scheme.

4 is a block diagram showing a module configuration of a routing processing apparatus according to an embodiment of the present invention.

5 is a flow chart showing the overall flow of the tree routing method according to an embodiment of the present invention.

6 is a view comparing a frame transmission path according to a tree routing method according to an embodiment of the present invention and a frame transmission path according to a conventional tree routing method.

7 is a view illustrating a comparison between a frame transmission path using a tree routing scheme according to an embodiment of the present invention and a frame transmission path using a conventional tree routing scheme.

8 is a view for explaining a problem caused by the conventional neighbor node table maintenance method.

9 is a flowchart illustrating a flow of a neighbor node table maintenance method according to an embodiment of the present invention.

10 is a diagram illustrating neighbor node table states of nodes in which a neighbor node table is managed according to a preferred embodiment of the present invention.

The present invention relates to a method and apparatus for tree routing in a wireless network, and more particularly, to a method and apparatus for more efficiently performing tree routing in a ZigBee wireless network.

ZigBee is an international standard specification for low-speed short-range personal wireless communications aimed at low power and low cost, based on the IEEE 802.15.4 standard. ZigBee's features include low power consumption, low chip price, and high communication stability. It is one of the rapidly developing technologies.

Zigbee has standardized the network (NWK) layer, application support (APS) layer, security (security) and application (APL) as the upper layer above the physical layer and the MAC layer of the IEEE 802.15.4 standard. Zigbee's physical layer is a simple structure, and the MAC layer has been studied to minimize power consumption.

ZigBee is suitable for remote control, remote management, and remote monitoring, and will be useful for home automation, factory automation, and industrial automation.

In multi-hop networks such as ZigBee, tree routing is possible when address assignments are hierarchical. ZigBee allocates logically assigned 16-bit address information. Tree routing is performed by determining whether the destination address of a data frame exists in its own address block.

Tree routing does not consume additional resources, such as route tables, and can consist of simple algorithms. However, tree routing has a problem in that routing through multiple nodes is inefficient even when frame data can be simply transmitted.

To solve the shortest path problem that occurs in tree routing, a path search algorithm is provided. Path discovery routing is an on-demand routing protocol that finds a path at the point where frame data requires a path to be sent to its destination, and has the nature of distance vector routing where each node has the next path to its destination. have.

ZigBee coordinators and ZigBee routers, which have the capability of a router, have a route table that stores relationships between destinations and surrounding nodes. The route table manages destination address, route status, and next hop address information as field information.

This route search routing method has the advantage of finding the shortest path more efficiently. However, due to the large control and memory loads, it often affects network performance.

In the conventional ZigBee routing scheme, the above-described tree routing scheme and the path discovery routing scheme are complementary to each other, but the tree routing scheme has an inefficient aspect of transmitting a frame only to its own parent node or child node. As a result, there have been problems of affecting network performance due to the relatively large number of path search routing methods that should be avoided.

In order to solve the problems of the prior art as described above, the present invention proposes an improved tree routing method and apparatus in a wireless network that can be efficiently routed with fewer hops.

Another object of the present invention is to propose a tree routing method and apparatus in a wireless network capable of maximizing network performance while reducing communication costs.

It is still another object of the present invention to propose a tree routing method and apparatus in a wireless network that can minimize the use of relatively large resource-route routing through an improved tree routing scheme.

Other objects of the present invention may be derived by those skilled in the art through the following examples.

In order to achieve the above object, according to an aspect of the present invention, determining whether the destination address of the frame matches the address of the neighbor node (a); (B) determining whether there is a neighbor node having a node corresponding to the destination address as a destination when the destination address of the frame does not match the address of the neighbor node; When there is a neighbor node having the destination address as a descendant, a tree routing method is provided in a wireless network, comprising the step (c) of transmitting a frame to a selected neighbor node among the existing neighbor nodes.

 Step (c) may include selecting a node having a deepest network depth among neighboring nodes having a node corresponding to the destination address as a descendant.

Whether there is a neighbor node having the destination address as a percentage is determined by the following equation.

Where AN is the address of the neighbor node, D is the destination address, and d is the network depth of the node.

On the other hand, the method of the present invention comprises the steps of determining whether the destination address is its descendant; If it is not its descendant, determining whether there is a neighbor node which is its ascendant among neighboring nodes; And transmitting a frame to a selected neighbor node among the neighbor nodes when there is a neighbor node that is an ascendant thereof.

The node to transmit a frame among neighbor nodes which is its ascendant may be a node having a lowest network depth.

Whether there is a neighbor node as its own ascendant may be determined by the following equation.

Where AN is the address of the neighboring node and α is its network address.

On the other hand, according to another aspect of the invention, the step of determining whether the destination address of the frame matches the address of the neighbor node (a); (B) determining whether the destination address is its descendant when the destination address of the frame does not match the address of the neighbor node; If the destination address is not its descendant, determining whether there is a neighbor node having as an ascendant a node corresponding to the destination address among neighboring nodes; (D) if a neighbor node having a node corresponding to the destination address exists as an incident, transmitting a frame to a selected neighbor node among the corresponding neighbor nodes; If there is no neighbor node having an node corresponding to the destination address as an ascendant, a tree routing method is provided, comprising (e) transmitting the frame to a parent node.

According to another aspect of the present invention, a combination of instructions for performing the above-described method is tangibly embodied, and a recording medium is provided which records a program readable by a digital data processing apparatus.

According to another aspect of the present invention, it is determined whether the destination address of the received frame matches the address of the neighbor node and whether the node corresponding to the destination address is a descendant of the neighbor node to transmit the frame to the neighbor node. A neighbor node transmission processor; A lower node transmission processor for determining whether a node corresponding to the destination address is its descendant and transmitting a frame to the selected descendant when there is no neighbor node that satisfies a condition; And when there is no node that satisfies the conditions of the neighbor node transmission processor and the lower node transmission processor, the neighbor node which transmits or satisfies a frame to a neighbor node having an node corresponding to the destination address as an ascendant among the neighbor nodes. There is provided a routing processing apparatus in a wireless network including an upper node transmission processing unit for transmitting a frame to its parent node when there is no.

Hereinafter, with reference to the accompanying drawings, a tree routing method and apparatus in a wireless network according to a preferred embodiment of the present invention will be described in detail.

In the present embodiment, a tree routing scheme in a wireless network using a Zigbee scheme is described as a main example, but the present invention is not limited to a Zigbee-based wireless network and may be applied to various types of multihop networks.

Prior to describing an embodiment of the present invention, address allocation in Zigbee will be described first.

1 and 2 are schematic diagrams illustrating a Zigbee network environment to which an address is assigned.

Zigbee can be implemented with lower power than Bluetooth. Wireless communication is suitable for home network based on control and sensor. It costs less than 1/2 of Bluetooth by minimizing the size of software and related components. Technology.

The ZigBee Network Standard Specification v0.85 [1] defines a cluster tree structure that aggregates all devices in a personal area network (PAN). All devices joining the cluster tree structure are assigned an address according to the tree structure. The assigned address will be used for routing in a Zigbee network environment.

For address assignment, the ZigBee coordinator defines two network parameters, Cm and Lm, taking into account the overall size of the network.

 Cm means the maximum number of child nodes that can be connected to a specific node, and Lm means the maximum level depth of the tree structure.

The address is assigned to all nodes, and the Zigbee coordinator assigns the address considering the likelihood that a lower node will be connected to each node. That is, when the Zigbee coordinator has an address of s, the ZigBee coordinator allocates the address of the first connected lower node to s + 1. The address of the second connected device is assigned to s + 1 + Cskip (d). The address of the next connected device is assigned as s + 1 + 2 * Cskip (d). That is, the address of the Cmth connected device is s + 1 + (Cm-1) * Cskip (d). Here, Cskip (d) may be expressed as Equation 1 below.

In Equation 1, the maximum number of lower devices having the Rm routing function is represented, and d is a network address.

Equation 1 above is an equation considering a case in which a lower device is connected to an end device which cannot be connected, and when not considering a case in which an end device to which such a lower device cannot be connected is connected, Cskip calculates as shown in Equation 2 below. May be

Where B _L is the address size of the entire network.

In the wireless network of the tree structure shown in FIGS. 1 and 2, the present specification defines a node located directly below a specific node as a child node, and defines a node located directly above the specific node as a parent node.

In addition, the term 'lower node' or 'Descendent' is used interchangeably for a node existing at a lower level of a specific node in the tree structure, and a parent node or an ascendant for a node existing at a higher level of a specific node. Will be used interchangeably.

In addition, a node that can transmit a frame at a time without passing through another node is defined as a neighbor node.

The ZigBee wireless network of the tree structure shown in FIGS. 1 and 2 is composed of a coordinator, a router, and an end device, and all ZigBee devices can join and leave the network.

In addition, ZigBee coordinators and routers have the ability to grant nodes that want to join the network, grant permission to nodes who want to leave the network, assign 16-bit network addresses, and manage the information of neighbor nodes. Provides additional.

Prior to describing the present invention, a conventional tree routing scheme will be described in more detail.

3 is a flowchart illustrating a conventional tree routing scheme.

Referring to FIG. 3, first, a unicast frame is received from an upper layer or a lower layer (step 300). Multicast frames may be received from an upper or lower layer, in which case multicasting is performed on the received frames.

When receiving a unicast frame, the received node analyzes the destination address information of the frame to determine whether it is the destination (step 302).

If it is the destination, the node receiving the frame forwards the frame to the higher layer (step 304).

If it is not the destination, it is searched whether there is a node in the neighbor node table that matches the destination address (step 306).

If there is a neighbor node in the neighbor node table that matches the destination address, the node receiving the frame directly transmits the frame to the neighbor node corresponding to the destination address (step 310). If there is a neighbor node that matches the destination address but the corresponding neighbor node is not in an on state, indirect transmission to the destination address may be performed.

If there is no neighbor node that matches the destination address in the neighbor node table, it is determined whether the destination is a descendant of the node receiving the frame (step 312).

Whether the destination is its descendant is determined by the following equation (3).

In Equation 3, α is the network address of the node itself receiving the frame, D is the network address of the destination, and d is its network level depth.

If the destination is a descendant of the node receiving the frame, the next hop address is calculated and the frame is transmitted to the calculated address (step 314). The next hop address N is calculated by the following equation (4).

N = α + 1 + C

Here, C is obtained by the following equation (5).

If the destination is not a descendant of the node that has received the frame, it transmits a frame to receive to its parent node.

In the conventional tree routing scheme as described above, when a node matching a destination address does not exist among its neighbor nodes, data is transmitted only to its own child node or a parent node, and thus the neighbor node information is not sufficiently utilized for routing. There was a problem with not being able to transmit the frame to the destination via many nodes.

4 is a block diagram illustrating a module configuration of a routing processing apparatus according to an embodiment of the present invention.

Referring to FIG. 4, a routing processing apparatus according to an embodiment of the present invention includes a neighbor node table 400, a neighbor node transmission processing unit 402, a child node transmission processing unit 404, and an upper node transmission processing unit 406. The neighbor node transmission processor 402 may include an address match determination unit 410 and a neighbor node dependency determination unit 412.

The neighbor node table 400 stores information about neighbor nodes. Here, the information of the neighbor node may include a PAN identifier, 16-bit and 64-bit address of its parent or child, type of device (coordinator, router, end device) and relationship information between itself and neighbor node. May optionally further include beacon orders, potential parent node information, and the like.

The embodiment of the present invention proposes a new scheme for maintenance of the neighbor node table, which will be described with reference to a separate drawing.

When the frame is received, the neighbor node transmission processor 402 determines whether the frame can be transmitted to a specific neighbor node among the neighbor nodes, and transmits the frame to the neighbor node.

The address match determination unit 410 of the neighbor node transmission processor 402 determines whether there is a neighbor node that matches the destination address of the frame among the neighbor nodes of the node that has received the frame. If there is a neighbor node that matches the destination address of the received frame, the neighbor node transmission processor 402 transmits the received frame to the neighbor node.

The neighbor node descendant determination unit 412 of the neighbor node transmission processor 402 determines whether the destination address is a descendant of a specific neighbor node among the neighbor nodes. Whether a node corresponding to the destination address is a descendant of a specific neighboring node is determined by Equation 6 below.

When there are a plurality of neighboring nodes that satisfy the condition of Equation 6, according to a preferred embodiment of the present invention, the neighboring node transmission processor 402 transmits the received frame to the neighboring node having the deepest network depth. The reason for transmitting the received frame to the neighbor node having the deepest network depth is to minimize the number of hops to the destination.

If there is no neighbor node that satisfies the condition of the neighbor node transmission processor, the frame received by the lower node transmission processor 404 is processed.

The lower node transmission processor 404 determines whether the destination address of the frame is its lower node, that is, the descendant. Whether the destination address is its descendant is determined by the above equation (3).

When the destination address of the frame is its descendant, the lower node transmission processor 404 sets the next hop address by using Equation 4 and transmits to the lower node corresponding to the set address.

If no node satisfies the condition of the neighbor node transmission processing unit 404 and the condition of the lower node transmission processing unit 404, the frame is processed by the higher node transmission processing unit 406.

The upper node transmission processing unit 406 determines whether there is a higher node of the neighbor nodes except for the parent node. Whether the parent node except the parent node exists in the neighbor node is determined by the following equation (7).

When there are a plurality of neighboring nodes satisfying Equation 7, the upper node transmitting processor 406 transmits a frame to one selected node among the corresponding neighboring nodes. At this time, according to the preferred embodiment of the present invention, the frame data is transmitted to the neighbor node having the lowest network depth among the corresponding neighbor nodes. However, the present invention is not limited thereto, and frame data may be transmitted to one of the neighbor nodes by various selection algorithms.

If there is no neighbor node that satisfies Equation 7, the upper node transmitter 406 transmits the frame data to the parent node of the node that receives the frame.

5 is a flowchart illustrating the overall flow of the tree routing method according to an embodiment of the present invention.

Referring to FIG. 5, first, unicast frame data is received from an upper layer or a lower layer (step 500). When broadcast frame data is received, a broadcast process may be performed.

The node receiving the frame data determines whether the destination address is its own address (step 502). If the destination address is itself, the frame is forwarded to a higher layer (step 504).

If the destination address is not itself, it is determined whether there is a neighbor node in the neighbor node table that matches the destination address (step 506). If there is a neighbor node that matches the destination address in the neighbor node table, the node receiving the frame transmits the frame to the neighbor node (step 510). In this case, when the power of the neighbor node is not on, the transmission may be indirectly performed to the destination address.

If there is no neighbor node that matches the destination address among the neighbor nodes, the node having the deepest network depth is searched among the neighbor nodes satisfying Equation 6 (step 512).

If there is a matching node, the node receiving the frame transmits the frame to the neighboring node (step 516).

If there is no matching node, the node receiving the frame determines whether the destination is its descendant (step 518).

If the destination is its descendant, the next hop address is set to the address calculated by Equation 4 (step 520).

If the destination is not its descendant, it is determined whether there is a node that satisfies Equation 7 (step 522). If there is a node that satisfies Equation 7, it is preferable to transmit a frame to the selected one of the nodes (step 524), and as described above, the node having the lowest network depth is selected.

If there is no node that satisfies Equation 7, the node receiving the frame forwards the frame to the parent node (step 526).

6 is a diagram illustrating a comparison between a frame transmission path using a conventional tree routing method and a frame transmission path using a tree routing method according to an embodiment of the present invention.

In FIG. 6, node 5 is a source node, node 611 is a destination node, a dotted line is a path according to a conventional tree routing method, and a solid line is a path of a tree routing method according to an embodiment of the present invention. In addition, parenthesis next to node 5 is node information of the neighbor node table of node 5.

Referring to FIG. 6, while the conventional tree routing method transmits through a total of eight hops to transmit a frame from node 5 to node 611, the tree routing method according to an embodiment of the present invention is used. Since node 610 is the node with the deepest network depth among nodes whose equations are destinations, the frame can be transmitted only through two hops by transmitting the frame to node 610.

FIG. 7 is a diagram illustrating another comparison of a frame transmission path according to a conventional tree routing method and a frame transmission path according to a tree routing method according to an embodiment of the present invention.

In FIG. 7, node 5 is a source node, node 0 is a destination node, a dotted line is a path according to a conventional tree routing method, and a solid line is a path of a tree routing method according to an embodiment of the present invention. In addition, the parenthesis next to node 5 and node 3 is node information of the neighbor node table of node 5 and node 3.

Referring to FIG. 7, the conventional tree routing scheme transmits through five hops to transmit a frame from node 5 to node 0, while in the routing scheme according to an embodiment of the present invention. A total of three hops by sending a frame directly to node 3, which is a neighbor of node 5, as an ascendant of node 5, and transmitting a frame directly to node 1, which is an ascendant of node 3, from node 3 Transmission takes place over the bay.

As described above with reference to FIGS. 6 and 7, the tree routing scheme according to an embodiment of the present invention enables efficient routing with fewer hops than the conventional tree routing scheme.

8 is a diagram illustrating a problem that occurs when the conventional neighbor node table maintenance method is used.

All nodes shown in FIG. 8 are nodes located at a distance capable of transmitting a frame at one time.

In Figure 8, the parenthesis next to the node is the number of the neighbor node managed in the neighbor node table of each node. Referring to FIG. 8, according to the conventional neighbor node table maintenance method, each node should have all the information of other nodes as neighbor node information, but nodes 1, 2, and 3 are all nodes in the vicinity. Only node 4 has the information of all neighbor nodes.

This is because the conventional neighbor table maintenance method does not add a node connected to the network later than itself to the neighbor table.

9 is a flowchart illustrating a flow of a neighbor node table maintenance method according to an embodiment of the present invention.

Referring to FIG. 9, first, a device newly joining a network transmits active scan request information for network participation (step 900). The active scan request information is information for searching for neighboring nodes.

The node receiving the active scan request information transmits beacon frame information containing its information to the new device (steps 902 and 904). 9 illustrates a case in which the coordinator and the router transmit beacon frame information.

Upon receiving the beacon frame information, the new device sends connection request information to the particular node (step 906). Here, the connection request information may include an address assignment request and a child node registration request. 9 illustrates a case where a connection request is made to a coordinator, the connection request may be transmitted to a neighbor router.

The node receiving the connection request transmits response information to the connection request including network address information and child node registration permission information (step 908).

After the connection request is complete, the new device broadcasts a node notification command (step 910). Here, the node notification command is information for requesting neighbor nodes to register themselves as neighbor nodes. Neighbors receive the node notification command to register the new device as a neighbor.

According to a preferred embodiment of the present invention, the radius of the node notification command is set to 1 to broadcast only to neighboring nodes.

Nodes participating in the Zigbee network can be managed as neighboring nodes later, according to the neighbor node table maintenance method as shown in FIG. 9. Accordingly, routing according to an embodiment of the present invention is further performed using the neighboring node information. It can be done more efficiently.

10 is a diagram illustrating neighbor node table states of nodes managed by a neighbor node table according to an exemplary embodiment of the present invention.

As illustrated in FIG. 10, nodes capable of transmitting a frame at one time manage information of all neighboring nodes as neighboring nodes. This is because it is possible for other nodes to register node 4 in the neighbor node table because node 4 requests to register itself as a neighbor node through a node notification command even if node 4 later joins the network.

As described above, according to the embodiment of the present invention, routing can be efficiently performed with a smaller number of hops, and there is an advantage of maximizing network performance while reducing communication costs.

In addition, according to an embodiment of the present invention, there is an advantage that can minimize the use of a path search routing that takes a relatively large resource through an improved tree routing scheme.

Claims (18)

Determining whether the destination address of the frame matches the address of the neighbor node (a); (B) determining whether there is a neighbor node having a node corresponding to the destination address as a destination when the destination address of the frame does not match the address of the neighbor node; (C) transmitting a frame to a selected neighbor node among existing neighbor nodes when there is a neighbor node having the destination address as a descendant, and tree routing of the device participating in the tree structure in the wireless network. Way. The method of claim 1, Step (c) includes selecting a node having a deepest network depth among neighboring nodes having a node corresponding to the destination address as a descendant, and tree routing of a device participating in a tree structure in a wireless network. Way. The method of claim 1, A method of tree routing in a device participating in a tree structure in a wireless network, characterized in that the existence of a neighbor node having the destination address as a percentage is determined by the following equation;

In the above equation, AN is an address of a neighbor node, D is a destination address, d is a network depth of a node, and Cskip (d-1) is defined as follows.

In the above equation, Cm is the maximum number of child nodes that can be connected to a specific node, Lm is the maximum level depth of the tree structure, Rm is the maximum number of lower devices with a routing function, d is a network address . The method of claim 1, After step (b), if there is no neighbor node having the destination address as a descendant, determining whether the destination address is its descendant; If it is not its descendant, determining whether there is a neighbor node which is its ascendant among neighboring nodes; And And transmitting a frame to a selected one of the neighboring nodes when the neighboring node that is an ascendant of the neighboring node exists. The method of claim 4, wherein The node which transmits the frame among neighbor nodes which is its ascendant is a node having the lowest network depth. The method of claim 4, wherein A method of tree routing in a device participating in a tree structure in a wireless network, characterized in that it is determined by the following equation whether the neighbor node as its own ascendant exists;

Where AN is the address of the neighboring node and α is its network address. Determining whether the destination address of the frame matches the address of the neighbor node (a); (B) determining whether the destination address is its descendant when the destination address of the frame does not match the address of the neighbor node; (C) determining whether there is a neighbor node which is an ascendant among neighbor nodes except the parent node, if it is not its descendant; (D) transmitting a frame to a selected neighbor node among neighbor nodes when there is a neighbor node that is an ascendant thereof; And (e) transmitting the frame to a parent node when there is no neighbor node that is its ascendant except a parent node. . The method of claim 7, wherein A method of tree routing in a device participating in a tree structure in a wireless network, characterized in that it is determined by the following equation whether the neighbor node as its own ascendant exists;

Where AN is the address of the neighboring node and α is its network address. The method of claim 7, wherein The node which transmits the frame among neighbor nodes which is its ascendant is a node having the lowest network depth. The method of claim 7, wherein Between step (a) and step (b), Determining whether a neighboring node having a node corresponding to the destination address as a destination exists; And If there is a neighbor node having the destination address as a descendant, transmitting a frame to a selected neighbor node among the existing neighbor nodes, further comprising: a tree routing method of a device participating in a tree structure in a wireless network. The method of claim 10, A method of tree routing in a device participating in a tree structure in a wireless network, characterized in that it is determined by the following equation whether there is a neighbor node having the destination address as a descendant;

Where AN is the address of the neighbor node, D is the destination address, and d is the network depth of the node. The method of claim 10, And selecting a node having a deepest network depth among neighboring nodes having a node corresponding to the destination address as a descendant. The method according to any one of claims 1 to 12, And broadcasting a node notification command frame in which a participating node requests to register itself as a neighbor node when joining a network. delete delete A neighbor node transmission processor for determining whether the destination address of the received frame matches the address of the neighbor node and whether the node corresponding to the destination address is a descendant of the neighbor node to transmit the frame to the neighbor node; A lower node transmission processor for determining whether a node corresponding to the destination address is its descendant and transmitting a frame to the selected descendant when there is no neighbor node that satisfies a condition; And When there is no node that satisfies the condition of the neighbor node transmission processor and the lower node transmission processor, when there is no neighbor node that transmits or satisfies a frame to the neighboring node which is its ascendant except the parent node among the neighbor nodes. And a higher node transmission processor for transmitting the frame to its parent node. The method of claim 16, If there are a plurality of neighboring nodes having a node corresponding to the destination address as a destination, the neighboring node transmitting processor selects the neighboring node having the deepest network depth and transmits the frame. Device. The method of claim 16, The upper node transmitting processor selects a neighbor node having the lowest network depth among neighbor nodes as its ascendant, and transmits a frame.

Images