Tree-guided distributed link state routing method

• US 8,638,695 B2
• Filed: 03/16/2007
• Issued: 01/28/2014
• Est. Priority Date: 03/16/2006
• Status: Active Grant

• Current Assignee: City College of New York, Samsung Electronics Co. Ltd.
• Original Assignee: City College of New York, Samsung Electronics Co. Ltd.
• Inventors: Zheng, Jianliang, Lee, Myung-Jong, Jung, Jin-Sae
• Primary Examiner(s): Hamza, Faruk
• Assistant Examiner(s): GUADALUPE CRUZ, AIXA AMYR
• Application Number:
  US11/723,196
• Publication Number:
  US 20070217346A1
• Time in Patent Office: 2,510 Days
• Field of Search: None
• US Class Current: 370/256
• 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 a wireless communication network comprising a plurality of nodes, the method comprising:

generating, at each node, an adaptive tree table which defines the network in a tree structure comprising branches and the nodes;

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

routing packets, from a particular one of the nodes, on the basis of the particular node'"'"'s adaptive tree table and link state table, wherein;

each adaptive tree table identifies the number of descendent branches connected to the corresponding node, when a reported total number of nodes in the network is less than a total number of addresses available for assignment, and an address block assigned to each of the branches.

2. The method of claim 1, wherein generating each 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 initializing each adaptive tree table comprises:

associating the corresponding node and each of its descendent nodes with branches and identifying the corresponding node and each of its descendent nodes as a root node, an intermediate node, or a leaf bottom node; and

assigning addresses to the associated nodes.

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

5. The method of claim 4, wherein the node capability is indicated by an 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 assigning the addresses comprises:

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

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

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

receiving, at each node, the number of descendent nodes descending from each descendent branch; and

calculating, at the root node, the total number of nodes by summing the numbers of descendent nodes received by the root node.

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

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

updating 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 beginning and ending addresses of an address block assigned to the corresponding node, a tree level of the corresponding node in the corresponding adaptive tree table, and the identities of one-hop neighbors of the node.

11. The method of claim 9, wherein each 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 belonging to an nth node (begAddrn), an ending address of the address block belonging to the nth node (endAddrn), a tree level of the nth node in the corresponding adaptive tree table (tree_leveln), and the number of hops to the nth node (hopsn).

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

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

generating, at each node, a first table to define a direction a packet is to be relayed in the communication network;

indicating, by each node of the plurality of nodes, the number of addresses to be assigned;

deriving, in each node, next hop information from the node'"'"'s local link state table; and

routing packets, from a particular one of the nodes, based on the particular node'"'"'s defined packet direction and next hop information, wherein

each first table identifies the number of descendent branches connected to the corresponding node, when a reported total number of nodes in the network is less than a total number of addresses available for assignment, and an address block assigned to each of the branches.

15. The method of claim 14, wherein generating each first table comprises:

generating association requests to allow nodes to be added to an adaptive tree; and

assigning addresses to each of the added nodes.

16. The method of claim 14, wherein routing the packets comprises:

generating a shortest path between the particular node and another node based on the particular node'"'"'s first table and next hop information.

17. A routing method of a wireless communication device within a network of other wireless communication devices, the method comprising:

generating a table to define a direction a packet is to be from the wireless communication device;

indicating the number of addresses to be assigned;

generating a local link state table comprising next hop information; and

routing the packet from the wireless communication device to another wireless communication device based on the wireless communication device'"'"'s defined packet direction and next hop information, wherein

the table identifies the number of descendent branches connected to the wireless communication device, when a reported total number of nodes in the network is less than a total number of addresses available for assignment, and an address block assigned to each branch.