Method and system for route selection and method for route reconstruction

• US 20050122955A1
• Filed: 05/10/2004
• Published: 06/09/2005
• Est. Priority Date: 12/05/2003
• Status: Abandoned Application

• Current Assignee: Institute For Information Industry
• Original Assignee: Institute For Information Industry
• Inventors: Lin, Hwa-Chun, Chu, Yung-Hwa
• Application Number:
  US10/842,108
• Publication Number:
  US 20050122955A1
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 92/02 Inter-networking arrangements

Abstract

A method and system for route selection and a method for route reconstruction. A mobile (or ad hoc) wireless network is divided into several clusters, each comprising a plurality of nodes. A source node in a cluster delivers a data packet to a destination node in accordance with a route table thereof if the destination node is located in the same cluster, and, if not, sends a route request packet to the destination node through a gateway node, determining a routing path to the destination node.

Claims

1. A method for route selection, applied in a multihop mobile (or ad hoc) wireless network, comprising the steps of:

creating a plurality of clusters, comprising at least a first cluster connected to a second cluster;

a source node located in the first cluster sending data packets;

the source node determining whether a destination node is in the first cluster according to a link state table of the source node;

the source node obtaining a first route according to a route table thereof if the destination node is in the first cluster, and delivering the data packets to the destination node through the first route;

the source node sending a route request packet to a first gateway node located in the first cluster according to a gateway table thereof if the destination node is not in the first cluster;

the first gateway node forwarding the route request packet to a second gateway in the second cluster;

the second gateway node obtaining a second route to the destination node according to a route table thereof if the destination node is in the second cluster;

the second gateway node forwarding the route request packet to the destination node;

the destination node returning a route reply packet to the source node; and

the source node delivering the data packets to the destination node through the second route.

2. The method as claimed in claim 1, wherein each node comprises a link state table, in which link states of all links within the same cluster are maintained.

3. The method as claimed in claim 1, wherein each node comprises a route table containing the shortest path from the node to each of other nodes within the same cluster.

4. The method as claimed in claim 1, wherein each node comprises a gateway table, in which gateway information of all gateway nodes within the same cluster is maintained.

5. The method as claimed in claim 1, wherein each node comprises a route cache, in which recent complete routes are stored.

6. The method as claimed in claim 1, wherein each cluster comprises a unique cluster ID.

7. The method as claimed in claim 1, wherein each node comprises a unique node ID.

8. The method as claimed in claim 1, wherein the source node delivers the route request packet to the second gateway node through a first gateway node in the first cluster.

9. The method as claimed in claim 8, wherein the first gateway node forwards the route request packet to the second gateway node according to a gateway table thereof.

10. The method as claimed in claim 1, wherein the second gateway node determines that the destination node is in the second cluster according to a link state table thereof.

11. The method as claimed in claim 1, wherein the step of obtaining the second route further comprises of receiving the route request packet at the destination node via the second route.

12. The method as claimed in claim 11, wherein the step of obtaining of the second route further comprises returning a route reply packet from the destination node to the source node through the second route.

13. A method for route reconstruction, determining a substitution path from a first node to a second node when a connection between the first and second nodes is broken while the first node is sending a data packet to the second node, comprising the steps of:

the first node determining whether a substitution path to the second node can be found according to a route table thereof;

the first node delivering the data packet to the destination if the substitution path is found;

adding routing information of the substitution path to a route error packet;

delivering the route error packet to the source node;

the first node sending a route error packet to the source node if the substitution path cannot be found; and

performing a route discovery process to find a new path to the destination node when the source node receives the route error packet.

14. A system for route selection, applied in a multihop mobile (or ad hoc) wireless network, comprising:

a first cluster, comprising a source node and at least a first gateway node, in which the source node sends data packets; and

a second cluster, connected to the first cluster, comprising a destination node and at least a second gateway node,

wherein the source node determines whether the destination node is located in the first cluster according to a link state table thereof, finds a first route according to a route table thereof if the destination node is located in the first cluster, delivers the data packets to the destination node through the first route, sends a route request packet to a first gateway node located in the first cluster according to a gateway table thereof if the destination node is not located in the first cluster, the first gateway node forwards the route request packet to the second gateway node in the second cluster according to the gateway table, and the second gateway node obtains a second route to the destination node according to a route table thereof if the destination node is located in the second cluster, the destination node returns a route reply packet to the source node, and the source node delivers the data packets to the destination node through the second route.

15. The system as claimed in claim 14, wherein each node comprises a link state table, in which link states of all links within the same cluster are maintained.

16. The system as claimed in claim 14, wherein each node comprises a route table, containing the shortest path from the node to each of other nodes within the same cluster.

17. The system as claimed in claim 14, wherein each node comprises a gateway table, in which gateway information of all gateway nodes within the same cluster are maintained.

18. The system as claimed in claim 14, wherein each node comprises a route cache, in which recent complete routes are stored.

19. The system as claimed in claim 14, wherein each cluster comprises a unique cluster ID.

20. The system as claimed in claim 14, wherein each node comprises a unique node ID.

21. The system as claimed in claim 14, wherein the source node delivers the route request packet to the second gateway node through a first gateway node in the first cluster.

22. The system as claimed in claim 21, wherein the first gateway node delivers the route request packet to the second gateway node according to a gateway table thereof.

23. The system as claimed in claim 14, wherein the second gateway node determines that the destination node is located in the second cluster according to a link state table thereof.

24. The system as claimed in claim 14, further comprising the destination node receiving the route request packet through the second route.

25. The system as claimed in claim 14, further comprising the destination node returning a route reply packet to the source node through the second route.