Tree-guided distributed link state routing method

• US 20070217346A1
• Filed: 03/16/2007
• Published: 09/20/2007
• Est. Priority Date: 03/16/2006
• Status: Active Grant

• Current Assignee: City College of New York, Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Jung, Jin-Sae, Lee, Myung-Jong, Zheng, Jianliang
• Granted Patent: US 8,638,695 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

A routing method of a wireless communication system is provided implementing advantageous features of both the tree routing and the link state routing. In the routing method, the system generates an adaptive tree table which defines a network in a tree structure of at least one branch with at least one node and each node generates a link state table which includes information on neighbor nodes, such that the packets are routed on the basis of the adaptive tree table and the link state table. Advantageous mechanisms of the tree routing and the link state routing are combined, thereby it is possible to eliminate most single point of failures of conventional tree routing and provide shorter paths compared with conventional tree routing.

Claims

1. A routing method of wireless communication network comprising a plurality of nodes, the method comprising:

generating an adaptive tree table which defines the network in a tree structure of at least one branch with at least one node;

generating, at each node, a link state table which comprises information on neighbor nodes;

routing packets on the basis of the adaptive tree table and the link state table.

2. The method of claim 1, wherein the step of generating the adaptive tree table comprises:

initializing the adaptive tree table;

determining whether the network changed; and

modifying the adaptive tree table if the network changed.

3. The method of claim 2, wherein the initializing of the adaptive tree table comprises:

associating the nodes with branches as at least one of a root, intermediate, and leaf bottom nodes; and

assigning addresses to the associated nodes.

4. The method of claim 3, wherein the associating of the nodes comprises considering capability of each node when deciding whether to accept another node as a child.

5. The method of claim 4, wherein the node capability is indicated by acceptance degree.

6. The method of claim 5, wherein the acceptance degree comprises at least one of an accept without reservation, an accept with reservation, an accept with reluctance, and a reject.

7. The method of claim 3, wherein the assigning of the addresses comprises:

determining if total number of the nodes of the network is equal to or less than total number of available addresses; and

allocating addresses to the nodes if the total number of the nodes is equal to or less than the total number of available addresses.

8. The method of claim 7, wherein the determining of the total number of the nodes comprises:

receiving, at each node, numbers of nodes of respective branches of the child node; and

calculating, at the root node, the total number of the nodes by summing the numbers of the nodes of the branches of the nodes below the root node.

9. The method of claim 1, wherein the generating of the link state table comprises:

exchanging link state information among neighbors within a number of hops; and

updating, at each node, the link state table on the basis of the link state information.

10. The method of claim 9, wherein the exchanged link state information comprises a beginning and an ending addresses of an address block assigned to the node, a tree level of the node in the adaptive tree table, and one-hop neighbors of the node.

11. The method of claim 9, wherein the link state table comprises a maximum-hop neighbor list and a connectivity matrix.

12. The method of claim 11, wherein the maximum-hop neighbor list comprises a beginning address of an address block owned by an nth node (begAddrn), an ending address of an address block owned by the nth node (endAddrn), a tree level of the nth node in the adaptive tree table (tree_leveln), and a number of hops to of the nth node (hopsn).

13. The method of claim 12, wherein the number of hops to the nth node (hopsn) is calculated using the connectivity matrix.