Minimization of radio resource usage in multi-hop networks with multiple routings

• US 20040156345A1
• Filed: 10/10/2003
• Published: 08/12/2004
• Est. Priority Date: 02/12/2003
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Steer, David, Teo, Koon Hoo, Smith, Adrian
• Granted Patent: US 8,149,707 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 84/22 with access to wired networks

Abstract

Packets in a multi-hop wireless network are routed based on the available link throughputs, network node congestion and the connectivity of the network in a manner that minimizes the use of radio resources and minimizes delay for packets in multi-hop system. The routing method also avoids congestion in the access network, especially near the network access points as provided by network access nodes. Each wireless network node maintains a link table for storing link conditions and associated route costs. Packets are routed according to the low cost route. Subsequent wireless network nodes evaluate whether a lower cost route is available and, if so, route the data packet according to the lower cost route. Every wireless network node transmits the data packet, a specified route and a time stamp indicated a time of the last data entry in the link table that was used to calculate the low cost route.

Claims

1. A method for creating a network information table for a network node, comprising:

determining link conditions including transmission rate, efficiency, and node delay;

updating the network information table with the determined link conditions and with a time stamp;

receiving and adding link condition information from neighboring wireless network nodes linked nodes for the link conditions, and adding a received corresponding time stamp for when the link conditions were determined; and

transmitting the network information table to the neighboring wireless network nodes.

2. The method of claim 1 further including selecting a route for a data packet wherein the route has a link cost that is lower than any other route based on information in the information table.

3. The method of claim 2 further including forwarding the data packet onto a first link to a first hop corresponding to the selected route.

4. The method of claim 3 further including transmitting route information with the data packet.

5. The method of claim 4 wherein the route information is placed in an appended header.

6. The method of claim 4 further including transmitting a time stamp corresponding to the route information.

7. The method of claim 6 wherein the time stamp is placed in an appended header.

8. A method for selecting a route in a multi-hop network for a data packet at a node communicating with a wireless network node device, the method comprising:

generating a network information table at the source node, the network information table including link information on one or more links from the source node to a destination node, the link information on the one or more links including the linked nodes, transmission rate between the nodes, efficiency of the link, a node delay, and a time that the link information was determined;

calculating a cost of available routes for the data packet from the source node to the destination node, the cost calculated by summing the quotient of the packet size and the transmission rate multiplied by the efficiency of the link;

determining a lowest cost route based upon the calculation of cost of available routes;

storing a time the lowest cost route was determined;

transmitting the data packet and information regarding the lowest cost route; and

transmitting data including the time the lowest cost route was determined.

9. The method of claim 8 wherein the data is transmitted onto a first link of the determined lowest cost route.

10. The method of claim 9 wherein the lowest cost route and the time the lowest cost route are transmitted as a part of a header of the data packet.

11. The method of claim 9 wherein the lowest cost route and the time the lowest cost route are transmitted as a part of an appended header of the data packet.

12. The method of claim 9 wherein the lowest cost route and the time the lowest cost route are transmitted as a part of a dedicated signal for transporting route and time stamp information.

13. A method at an intermediate node for rerouting a data packet received from a source node to a destination node, the data packet including route and time stamp information, the method comprising:

providing a network information table at the intermediate node, the network information table including link information on one or more links from the intermediate node to the destination node, the link information on the one or more links including the linked nodes, transmission rate between the nodes, efficiency of the link, a queue delay, and a time that the link information was determined;

calculating a cost of new routes for the data packet from the intermediate node to the destination node, the cost calculated by summing the quotient of the packet size and the transmission rate multiplied by the efficiency of the link;

determining if any new route has a lower cost than an original route;

determining whether the intermediate node has more recent network information than that used to determine the original route in the source node; and

if the intermediate node has more recent network information, transmitting the data packet along the new lowest cost route.

14. The method of claim 13 further comprising transmitting a new lowest cost routing information along with the data packet.

15. The method of claim 13 further comprising transmitting a time of the new lowest cost routing data.

16. A method for routing a data packet through a distributed wireless access system wherein the routing minimizes the usage of radio resources, minimizes packet delay, compensates for congestion, and adapts to changes in the network configuration, comprising:

maintaining a routing information table in each node;

determining available links for routing the data packet from a source node to a destination node;

determining a cost associated with each link;

choosing a route for the data packet based on a cost function using data from the routing information table;

updating the route at each intermediate node of the route for the data packet using the routing information table at the intermediate node to determine a cost function for each available route and choosing a lowest cost route from the intermediate node to the destination node.

17. A node for routing data packets in a multi-hop wireless network, comprising:

memory for storing computer instructions defining routine operational logic of the wireless network node and for storing computer instructions defining route selection logic for evaluating network information including at least one of route efficiency, link cost, delay interference and a time stamp of the network information and further defining logic selecting a low cost route for transporting a data packet based on network information and the time stamp; and

a processor coupled to receive the computer instructions over a bus, the processor for executing the computer instructions to prompt the wireless network node to operate according to the logic defined by the computer instructions.

18. The wireless network node of claim 17 wherein the computer instructions further define logic for generating a link table for storing the route selection logic.

19. The wireless network node of claim 17 wherein the computer instructions further define logic for updating the link table based upon at least one of known link conditions or received link conditions.

20. The wireless network node of claim 17 wherein the computer instructions further define logic for determining, based upon the time stamp, whether to re-route a received data packet based upon a determination that route information received with the data packet is older (and less current) that route information stored within the wireless network node.