Route selection in wireless 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.

1 . A method, said method comprising:
 receiving a route reply message responsive to a route request message from a first intermediate node in a wireless network, wherein a first intermediate node having a valid route responds to a route request message based on a condition of a flag in said route request message;   establishing communications between a source node and a destination node using said valid route;   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;   establishing communications between said source node and said destination node by replacing said valid route with said best route.   
     
     
         2 . The method according to  claim 1 , wherein said valid route is a temporary route and if said temporary route is said best route then said further route reply message serves as confirmation of use of said temporary route as said best route. 
     
     
         3 . The method according to  claim 1 , further comprising:
 setting said flag of a route request message by said source node; and   forwarding said route request message over said wireless network.   
     
     
         4 . The method according to  claim 1 , further comprising forwarding a maintenance route request message over said wireless network, wherein forwarding further comprises flooding said wireless network with said maintenance route request message in order to maintain said best route between said source node and said destination node and to adapt to changes in wireless network conditions. 
     
     
         5 . The method according to  claim 4 , further comprising receiving a response to said maintenance route request message as if it is said route request message. 
     
     
         6 . The method according to  claim 1 , wherein said valid route is a best route and further wherein said route reply message is a first route reply message. 
     
     
         7 . An apparatus, comprising:
 means for receiving a route reply message responsive to a route request message from a first intermediate node in a wireless network, wherein a first intermediate node having a valid route responds to a route request message based on a condition of a flag in said route request message;   means for establishing communications between a source node and a destination node using said valid route;   means for 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;   means for establishing communications between said source node and said destination node by replacing said valid route with said best route.   
     
     
         8 . The apparatus according to  claim 7 , wherein said valid route is a temporary route and if said temporary route is said best route then said further route reply message serves as confirmation of use of said temporary route as said best route. 
     
     
         9 . The apparatus according to  claim 7 , further comprising:
 means for setting said flag of a route request message by said source node; and   means for forwarding said route request message over said wireless network.   
     
     
         10 . The apparatus according to  claim 7 , further comprising means for forwarding a maintenance route request message over said wireless network, wherein said means for forwarding further comprises means for flooding said wireless network with said maintenance route request message in order to maintain said best route between said source node and said destination node and to adapt to changes in wireless network conditions. 
     
     
         11 . The apparatus according to  claim 10 , further comprising means for receiving a response to said maintenance route request message as if it is said route request message. 
     
     
         12 . The apparatus according to  claim 7 , wherein said valid route is a best route and further wherein said route reply message is a first route reply message. 
     
     
         13 . A method for discovering a route between a source node and a destination node in a 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 a 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;   receiving, by said first intermediate node, a further route reply message from said destination node, said further route reply message including a best route between said source node and said destination node based on cumulative metrics in route request messages received by said destination node; and   forwarding, by said first intermediate node, said further route reply message to said source node, wherein if said valid route between said source node and said destination node is not said best route between said source node and said destination node then said further route reply message serves to establish communications using said best route between said source node and said destination node upon receipt of said further route reply message by said source node.   
     
     
         14 . The method according to  claim 13 , further comprising:
 updating said route request message; and   re-flooding said wireless network with said updated route request message.   
     
     
         15 . The method according to  claim 14 , wherein said responding act thereby establishes communications between said source node and said destination node of said wireless network using said valid route as a temporary forward route. 
     
     
         16 . The method according to  claim 14 , wherein said updating act further comprises updating a metric in said route request message with a cumulative metric of said route between said source node and said destination node of said wireless network. 
     
     
         17 . The method according to  claim 13 , wherein said wireless network is a wireless mesh network. 
     
     
         18 . The method according to  claim 13 , wherein said route reply message of said responding act is unicast to said source node. 
     
     
         19 . The method according to  claim 13 , wherein an address of said destination node is one of an internet protocol address and a media access control address. 
     
     
         20 . The method according to  claim 13 , wherein said destination node includes destination nodes that are associated with one of a proxy and an access point. 
     
     
         21 . The method according to  claim 15 , wherein said temporary forward route between said source node and said destination node is available for transmission of data upon receipt of said route reply message by said source node. 
     
     
         22 . The method according to  claim 15 , wherein said temporary forward route between said source node and said destination node is a best route between said source node and said destination node and further wherein said route reply message is a first route reply message. 
     
     
         23 . The method according to  claim 13 , wherein if said valid route between said source node and said destination node is said best route between said source node and said destination node then said further route reply message serves as a confirmation. 
     
     
         24 . An apparatus for discovering a route between a source node and a destination node in a wireless network, comprising:
 means for receiving a route request message from 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 a 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;   means for receiving, by said first intermediate node, a further route reply message from said destination node, said further route reply message including a best route between said source node and said destination node based on cumulative metrics in route request messages received by said destination node; and   means for forwarding said further rote reply message to said source node, wherein if said valid route between said source node and said destination node is not said best route between said source node and said destination node then said further route reply message serves to establish communications using said best route between said source node and said destination node upon receipt of said further route reply message by said source node.   
     
     
         25 . The apparatus according to  claim 24 , further comprising:
 means for updating said route request message; and   means for re-flooding said wireless network with said updated route request message.   
     
     
         26 . The apparatus according to  claim 25 , wherein said means for responding thereby establishes communications between said source node and said destination node of said wireless network using said valid route as a temporary forward route. 
     
     
         27 . The apparatus according to  claim 25 , wherein said means for updating further comprises updating a metric in said route request message with a cumulative metric of said route between said source node and said destination node of said wireless network. 
     
     
         28 . The apparatus according to  claim 24 , wherein said wireless network is a wireless mesh network. 
     
     
         29 . The apparatus according to  claim 24 , wherein said route reply message of said means for responding is unicast to said source node. 
     
     
         30 . The apparatus according to  claim 24 , wherein an address of said destination node is one of an internet protocol address and a media access control address. 
     
     
         31 . The method according to  claim 24 , wherein said destination node includes destination nodes that are associated with one of a proxy and an access point. 
     
     
         32 . The method according to  claim 26 , wherein said temporary forward route between said source node and said destination node is available for transmission of data upon receipt of said route reply message by said source node. 
     
     
         33 . The method according to  claim 26 , wherein said temporary forward route is a best route between said source node and said destination node and further wherein said route reply message is a first route reply message. 
     
     
         34 . The method according to  claim 24 , wherein if said valid route between said source node and said destination node is said best route between said source node and said destination node then said further route reply message serves as a confirmation.