Route selection in wireless networks

• US 8,064,416 B2
• Filed: 11/09/2005
• Issued: 11/22/2011
• Est. Priority Date: 11/09/2005
• Status: Active Grant

• Current Assignee: InterDigital Patent Holdings, Inc. (InterDigital, Inc.)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: Liu, Hang
• Primary Examiner(s): Ho; Chuong T
• Application Number:
  US12/084,600
• Publication Number:
  US 20090135824A1
• Time in Patent Office: 2,204 Days
• Field of Search: 370/254, 370/338, 370/315, 370342-347, 370/401, 370/432
• US Class Current: 370/338
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A method and apparatus are described for locating a route between a source node and a destination node in an on-demand wireless network including flooding the wireless network with a route request message by the source node and receiving a route reply message responsive to the route request message from a first intermediate node having a valid route to the destination node, wherein the first intermediate node responds to the route request message based on a condition of a flag in the route request message. Also described are a method and apparatus for locating a route between a source node and a destination node in an on-demand wireless network including receiving a route request message from the source node and responding to the route request message with a route reply message by a first intermediate node having a valid route to the destination node, wherein the intermediate node responds to the route request message based on a condition of a flag in the route request message.

Claims

1. A method for locating a route between a source node and a destination node in an on-demand wireless network, said method comprising:

flooding said on-demand wireless network with a route request message by said source node;

receiving a route reply message to said route request message from a first intermediate node having a valid route to said destination node, wherein said first intermediate node responds to said route request message based on a condition of a flag in said route request message, and further wherein said first intermediate node resets said flag; and

receiving in unicast a further route reply message from said destination node, said further route reply message including a best route selected by said destination node based on cumulative metrics received in route request messages received by said destination node, wherein if a temporary route is said best route then said further route reply message serves as a confirmation and if said temporary route is not said best route then said further route reply message serves to establish said best route upon receipt of said further route reply message by said source node.

2. The method according to claim 1, wherein said receiving act thereby establishes a temporary route between said source node and said destination node of said wireless network.

3. The method according to claim 2, wherein said temporary route is available for transmission of data upon receipt of said route reply message by said source node.

4. The method according to claim 1, wherein said wireless network is a wireless mesh network.

5. The method according to claim 1, wherein said route reply message of said receiving act is unicast to said source node.

6. The method according to claim 1, wherein an address of said destination node is one of an internet protocol address and a media access control address.

7. The method according to claim 1, wherein said destination node includes destination nodes that are associated with one of a proxy and an access point.

8. The method according to claim 1, further comprising flooding said wireless network with a maintenance route request message in order to maintain a best metric route between nodes and to adapt to changes in network conditions.

9. The method according to claim 8, further comprising receiving a response to said maintenance route request message as if it is said route request message.

10. An apparatus for locating a route between a source node and a destination node in an on-demand wireless network, comprising:

means for flooding said on-demand wireless network with a route request message by said source node;

means for responding to said route request message with a route reply message by a first intermediate node having a valid route to said destination node, wherein said first intermediate node responds to said route request message based on a condition of a flag in said route request message, and further wherein said first intermediate node resets said flag; and

means for receiving in unicast a further route reply message from said destination node, said further route reply message based on cumulative metrics received in route request messages received by said destination node, wherein if a temporary route is said best route then said further route reply message serves as a confirmation and if said temporary forward route is not said best route then said further route reply message serves to establish said best route upon receipt of said further route reply message by said source node.

11. The apparatus according to claim 10, wherein said means for responding thereby establishes a temporary route between said source node and said destination node of said wireless network.

12. The apparatus according to claim 10, wherein said wireless network is a wireless mesh network.

13. The apparatus according to claim 10, wherein said route reply message of said means for receiving is unicast to said source node.

14. The apparatus according to claim 10, wherein an address of said destination node is one of an internet protocol address and a media access control address.

15. The apparatus according to claim 10, wherein said destination node includes destination nodes that are associated with one of a proxy and an access point.

16. The apparatus according to claim 10, further comprising means for flooding said wireless network with a maintenance route request message in order to maintain a best metric route between nodes and to adapt to changes in network conditions.

17. The apparatus according to claim 16, further comprising means for receiving a response to said maintenance route request message as if it is said route request message.

18. The apparatus according to claim 10, wherein said temporary route is available for transmission of data upon receipt of said route reply message by said source node.

19. A method for locating a route between a source node and a destination node in an on-demand wireless network, said method comprising:

receiving a route request message from said source node;

responding to said route request message with a route reply message by a first intermediate node having a valid route to said destination node, wherein said first intermediate node responds to said route request message based on a condition of a flag in said route request message, and further wherein said first intermediate node resets said flag; and

receiving, by said first intermediate node, in unicast a further route reply message from said destination node, said further route reply message including a best route selected by said destination node based on cumulative metrics received in route request messages received by said destination node, wherein if a temporary route is said best route then said further route reply message serves as a confirmation and if said temporary route is not said best route then said further route reply message serves to establish said best route upon receipt of said further route reply message by said source node.

20. The method according to claim 19, further comprising:

updating said route request message; and

flooding said on-demand wireless network with said route request message.

21. The method according to claim 20, wherein said updating act further comprises updating said flag and updating a metric in said route request message with a cumulative metric of said route between said source node and said intermediate node.

22. The apparatus according to claim 20, wherein said means for updating further comprises means for updating said flag and means for updating a metric in said route request message with a cumulative metric of said route between said source node and said intermediate node.

23. The method according to claim 19, wherein said responding act thereby establishes a temporary route between said source node and said destination node of said on-demand wireless network.

24. The method according to claim 23, wherein said temporary route is available for transmission of data upon receipt of said route reply message by said source node.

25. The method according to claim 19, wherein said on-demand wireless network is a wireless mesh network.

26. The method according to claim 19, wherein said route reply message of said responding act is unicast to said source node.

27. The method according to claim 19, wherein an address of said destination node is one of an internet protocol address and a media access control address.

28. The method according to claim 19, wherein said destination node includes destination nodes that are associated with one of a proxy and an access point.

29. The method according to claim 19, further comprising responding to a maintenance route request message as if it is said route request message.

30. An apparatus for locating a route between a source node and a destination node in an on-demand wireless network, comprising:

means for receiving a route request message from said source node; and

means for responding to said route request message with a route reply message by a first intermediate node having a valid route to said destination node, wherein said first intermediate node responds to said route request message based on a condition of a flag in said route request message, and further wherein said first intermediate node resets said flag; and

means for receiving, by said first intermediate node, in unicast a further route reply message from said destination node, said further route reply message based on cumulative metrics received in route request messages received by said destination node, wherein if a temporary route is said best route then said further route reply message serves as a confirmation and if said temporary forward route is not said best route then said further route reply message serves to establish said best route upon receipt of said further route reply message by said source node.

31. The apparatus according to claim 30, further comprising:

means for updating said route request message; and

means for flooding said on-demand wireless network with said route request message.

32. The apparatus according to claim 30, wherein said means for responding thereby establishes a temporary route between said source node and said destination node of said on-demand wireless network.

33. The apparatus according to claim 32, wherein said temporary forward route is available for transmission of data frames upon receipt of said route reply message by said source node.

34. The apparatus according to claim 30, wherein said on-demand wireless network is a wireless mesh network.

35. The apparatus according to claim 30, wherein said route reply message of said means for responding is unicast to said source node.

36. The apparatus according to claim 30, wherein an address of said destination node is one of an internet protocol address and a media access control address.

37. The apparatus according to claim 30, wherein said destination node includes destination nodes that are associated with one of a proxy and an access point.

38. The apparatus according to claim 30, further comprising means for responding to a maintenance route request message as if it is said route request message.