Wireless routing protocol for ad-hoc networks

• US 7,177,295 B1
• Filed: 03/08/2002
• Issued: 02/13/2007
• Est. Priority Date: 03/08/2002
• Status: Expired due to Fees

• Current Assignee: Scientific Research Corporation
• Original Assignee: Scientific Research Corporation
• Inventors: Oakes, Tracey, Sholander, Peter, Coccoli, Paul
• Primary Examiner(s): Ngo; Ricky Q.
• Assistant Examiner(s): Wong; Warner
• Application Number:
  US10/093,850
• Time in Patent Office: 1,803 Days
• Field of Search: None
• US Class Current: 370/338
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Method for selecting a route within a wireless ad-hoc routing protocol using a QoS metric. The method begins by dynamically defining a routing zone that encompasses at least two of the network nodes. A communications link is established between the source node and a destination node. If the destination node is within the routing zone of the source node, the route is determined by a proactive routing protocol. If, however, the destination node is outside the routing zone, the route is determined using a reactive routing protocol. A QoS metric for each route is calculated by combining the individual QoS metrics for each hop within the particular route. Finally, the route with the best QoS metric is selected to use as the communications link between the source node and the destination node.

Claims

1. A method for locating a route in an ad-hoc network, comprising:

providing a network comprising a plurality of network communication nodes;

dynamically defining a routing zone for each network communication node;

determining a number of border nodes within the routing zone;

if a destination node is within the routing zone, then establishing a communications link between a source node and the destination node using route information established using proactive routing protocol (PRP);

if the destination node is outside the routing zone, then bordercasting a route request to each of the border nodes and transmitting the route request from the border nodes to the destination node using a reactive routing protocol (RRP) based on changing dynamics of the ad-hoc network;

receiving a route reply from the destination node at one or more of the border nodes via a network layer or an application layer, the route reply comprising a hop count and a quality of service (QoS) metric for each hop count;

using the hop count and QoS metric for each hop count in the route reply to calculate a cumulative QoS metric for each route through the one or more of the border nodes; and

selecting at least one route from the source node to the destination node having the lowest cumulative QoS metric.

2. The method of claim 1, wherein dynamically defining the routing zone comprises:

selecting at least one source node from the plurality of communications nodes; and

establishing a zone radius around the source node.

3. The method of claim 2, wherein determining the border nodes comprises identifying each communication node whose minimum distance in hops from the source node is equal to the zone radius.

4. The method of claim 3, further comprising establishing a communications link between the source node and each node within the zone radius using a proactive routing protocol (PRP) by transmitting routing information from the source node to each node in the routing zone.

5. The method of claim 4, wherein the routing information is periodically transmitted at a predefined time interval.

6. The method of claim 5, wherein the predefined time interval is between 5 and 10 seconds.

7. The method of claim 4, wherein the routing information comprises:

a hop count from the communications node to the source node; and

a QoS metric for the route between the communications node and the source node.

8. The method of claim 1, wherein bordercasting the route request, comprises:

transmitting the route request to each border node in the routing zone.

9. The method of claim 1, wherein calculating a cumulative QoS metric comprises:

if the destination node is within the routing zone, then retrieving the QoS metric for the route,

otherwise, if the destination node is outside the routing zone, then

determining the number of communications nodes between the border node and the destination node; and

adding the QoS metric for the route between the border node and the destination node to the QoS metric for the route between the source node and the border node.

10. The method of claim 1, wherein the QoS metric is selected from the group consisting essentially of associativity, signal stability, error rate, power levels, including battery life, hop count, delay and bandwidth.

11. The method of claim 1, wherein selecting at least one route having the lowest cumulative QoS metric comprises the “

Shortest-Widest”

protocol, wherein the Shortest-Widest protocol comprises;

determining a lowest cumulative QoS metric;

determining if more than one route between the source node and a destination node has the lowest cumulative QoS metric with the same value;

selecting the route having the lowest cumulative QoS metric if only one route has the lowest cumulative QoS metric; and

selecting the route having the lowest cumulative hop count between the source node and the destination node, if the more than one route has the lowest cumulative QoS metric.

12. A method of determining an efficient route between a source node and a destination node in an ad-hoc network using a hybrid routing protocol, comprising:

providing a network comprising a plurality of network communication nodes, the plurality of network communications nodes comprising at least one source node and at least one destination node;

determining at least one communications route between the source node and the destination node using the hybrid routing protocol based on changing dynamics of the ad-hoc network;

calculating a quality of service (QoS) metric for each communications route between the source node and the destination node wherein the QoS metric for each communications route is based on QoS information received via a network layer or an application layer from one or more nodes associated with the communications route; and

selecting the communications route with the best QoS metric.

13. The method of claim 12, further comprising determining a routing zone around the source node.

14. The method of claim 13, further comprising:

determining whether the destination node lies within the routing zone.

15. The method of claim 13, wherein the hybrid protocol comprises:

a proactive routing protocol (PRP) used to establish routes to destination nodes within the routing zone; and

a reactive routing protocol (RRP) used to establish routes to destination nodes outside the routing zone.

16. The method of claim 15, further comprising:

transmitting a PRP packet from the source node to each neighboring node within the routing zone periodically at a predetermined time interval;

wherein the PRP packet comprises a QoS metric for the route between that neighboring node and the source node.

17. The method of claim 16, wherein the time interval is between 5 and 10 seconds.

18. The method of claim 15, wherein using the RRP to establish routes to destination nodes outside the routing zone comprises:

sending a route request to each border node within the routing zone,

wherein each border node broadcasts the route request to every node outside the routing zone.

19. The method of claim 15, further comprising:

receiving a route reply at a first border node from the destination node; and

transmitting the route reply from the first border node to the source node,

wherein the route reply includes a quality of service (QoS) metric for each route between the destination node and the border node.

20. The method of claim 13, wherein the routing zone includes a plurality of border nodes and wherein calculating a cumulative QoS metric comprises;

if the destination node is within the routing zone, then retrieving the QoS metric for the route; and

if the destination node is outside the routing zone,

determining a number of communications nodes between a first border node and the destination node; and

adding the QoS metric for the route between the first border node and the destination node to the QoS metric for the route between the source node and the first border node.

21. The method of claim 12, wherein the QoS metric is selected from the group consisting essentially of associativity, signal stability, error rate, power levels, including battery life, hop count, delay and bandwidth.

22. A system for determining a route between a source node and a destination node within an ad-hoc network, comprising:

a neighbor discovery protocol (NDP) operable for;

locating each node within one hop of every other node;

storing the results of the location of each node within one hop of every other node as a result of the NDP in a neighbor table;

a proactive routing protocol (PRP) operable for;

reading the results stored in the neighbor table and collecting routing information about the non-neighbor nodes in the routing zone around the source node;

establishing at least one proactive route between the source node and each node within the routing zone; and

calculating a cumulative quality of service (QoS) metric for each proactive route;

determining which proactive route to each node has the lowest QoS metric; and

storing the proactive routes and associated QoS metrics for the proactive routes between the source node and each node with the lowest QoS metric in a proactive routing table; and

determining which nodes within the routing zone are border nodes;

a reactive routing protocol (RRP) operable for

establishing a reactive route between at least one of the border nodes and the destination node based on changing dynamics of the ad-hoc network, wherein the destination node is outside the routing zone;

calculating a cumulative QoS metric for each reactive route wherein the QoS metric for each reactive route is based on QoS information received via a network layer or an application layer from one or more nodes associated with the reactive route;

and

a management process operable for;

retrieving the proactive routes and associated QoS metrics from the source node to the at least one of the border nodes from the proactive routing table; and

combining the QoS metric associated with the proactive route to a selected border node with the QoS metric associated with the reactive route from the selected border node to the destination node to create a cumulative QoS metric for each route from the source node to the destination node; and

selecting the route from the source node to the destination node that has the best cumulative QoS metric.

23. The system of claim 22, wherein the PRP is further operable to:

determine the hop count between the source node and each node within the routing zone; and

select the route having the lowest hop count between the source node and the destination node if there is more than one proactive route between the source node and the destination node.

24. The system of claim 23, wherein the RRP is further operable to determine the hop count between each border node and the destination node outside the routing zone.

25. The system of claim 22, wherein the management process is further operable for:

for each of the at least one border nodes;

combining the hop count of the proactive route between the source node and the border node with the hop count of the reactive route between the border node and the destination node to create a cumulative hop count between the source node and the destination node; and

selecting the route having the lowest hop count between the source node and destination node if there is more than one route between the source node and destination node.

26. The system of claim 25, wherein the PRP is further operable to monitor the proactive routes within the routing zone and RRP route requests and dynamically adjusting the size of the routing zone based on the proactive routes and the RRP route requests.

27. The system of claim 26, wherein the PRP is further operable for:

monitoring the proactive routes by causing the source node to repeatedly transmit route information packets to each node within the routing zone; and

for each node within the routing zone;

determining a liveliness of a connection between the source node and the node by determining whether the node generates at least k replies to n route information packets, wherein k and n are predetermined values; and

adding the node to the routing zone if the number of replies is greater than or equal to k and removing the node form the routing zone if the number of replies is less than k.

28. The system of claim 27, wherein the route information packets are transmitted periodically within a period between 5 and 10 seconds.

29. A method for locating a route in an ad-hoc network, comprising:

dynamically defining a routing zone for a source node, wherein the routing zone includes a plurality of border zones;

selecting a route between the source node and a destination node by;

determining whether the destination node is within the routing zone;

if the destination node is not within the routing zone, then bordercasting a route request to each of the border nodes requesting the border nodes transmit a route request message to the destination node using a reactive routing protocol (RRP) based on changing dynamics of the ad-hoc network;

for at least two of the border nodes;

receiving a route reply from the destination node, the route reply comprising a hop count and a quality of service (QoS) metric for each hop count for the route between the border node and the destination node;

determining a route between the source node and the border node using a proactive routing protocol (PRP); and

calculating a cumulative QoS metric for the route from the source node through the border node to the destination node wherein the QoS metric for the route is based on QoS information received via a network layer or an application layer from one or more nodes associated with the route;

comparing the cumulative QoS metrics for the routes from the source node through at least two border nodes to the destination; and

selecting the route having the lowest cumulative QoS metric.