Bluetooth personal area network routing protocol optimization using connectivity metric

• US 20040264466A1
• Filed: 06/25/2003
• Published: 12/30/2004
• Est. Priority Date: 06/25/2003
• Status: Active Grant

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Nokia Corporation
• Inventors: Huang, Leping
• Granted Patent: US 7,706,282 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/127 based on intermediate node capabilities
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method is disclosed for routing data packets in a wireless network, preferably a Bluetooth™ network. The method includes estimating a link bandwidth of at least one network node, calculating a connectivity metric based on the estimated link bandwidth, distributing information concerning the calculated connectivity metric and, using the calculated connectivity metric, determining a route having a maximum link bandwidth and a minimum traffic load. Preferably, estimating uses a model of a Bluetooth network medium access control MAC algorithm. The connectivity metric is defined as a ratio of a maximum link bandwidth to the estimated link bandwidth, where the maximum link bandwidth is the link bandwidth between a Master node and a Slave node when there is only one Slave node connected to the Master node (i.e., when there is one Slave node in the piconet with the Master node).

Claims

1. A method for routing data packets in a wireless network, comprising:

estimating a link bandwidth of at least one network node;

calculating a connectivity metric based on the estimated link bandwidth;

distributing information concerning the calculated connectivity metric; and

using the calculated connectivity metric, determining a route having a maximum link bandwidth and a minimum traffic load.

2. A method as in claim 1, where estimating uses a model of a network medium access control MAC algorithm.

3. A method as in claim 1, where estimating uses a model of a Bluetooth network medium access control MAC algorithm.

4. A method as in claim 1, where said connectivity metric comprises a ratio of a maximum link bandwidth to the estimated link bandwidth, where the maximum link bandwidth is the link bandwidth between a Master node and a Slave node when there is only one Slave node connected to the Master node.

5. A method as in claim 4, where determining the route comprises:

calculating the connectivity metric of links along a plurality of routes;

determining a maximum connectivity metric value of each of the plurality of routes; and

selecting the route having the smallest connectivity metric value.

6. A method as in claim, 1, where estimating includes considering a node'"'"'s status and the number of the node'"'"'s Slaves.

7. A method as in claim 6, where considering a node'"'"'s status considers whether a node is a Master node, a Slave node, or a Participant in Multiple Piconet (PMP) node.

8. A method as in claim 7, where a maximum link bandwidth B₀ is the link bandwidth between the Master and Slave nodes, when there is only one Slave node present in a piconet, and where all piconets have the same value of B₀, where M_i is the number of Slave nodes in piconet i, and P_i is the number of piconets that a PMP node connects to, and where Bi is the link bandwidth of the Master-Slave link in piconet i.and where the connectivity metric B_i/B₀ is determined at least in accordance with:

9. A method as in claim 1, where distributing information concerning the calculated connectivity metric comprises inserting the value of the connectivity metric into a routing protocol packet in place of the value of a hop number.

10. A method as in claim 1, where distributing information concerning the calculated connectivity metric comprises inserting the value of the connectivity metric into a routing protocol packet in conjunction with the value of a hop number.

11. A computer program embodied on a computer readable medium and comprising computer program code segments for use by at least one data processor when implementing a routing protocol in a wireless network, comprising:

a first computer program code segment for estimating the link bandwidth of at least one network node;

a second computer program code segment for calculating a connectivity metric based on the estimated link bandwidth; and

a third computer program code segment that uses the calculated connectivity metric to determine a route having a maximum link bandwidth and a minimum traffic load.

12. A computer program as in claim 11, where said first computer program code segment uses a model of a network media access control algorithm.

13. A computer program as in claim 11, where said first computer program code segment uses a model of a Bluetooth network media access control algorithm.

14. A computer program as in claim 11, where said second computer program code segment calculates said connectivity metric to be a ratio of a maximum link bandwidth to the estimated link bandwidth, where the maximum link bandwidth is the link bandwidth between a Master node and a Slave node when there is only one Slave node in the network.

15. A computer program as in claim 14, where said third computer program code segment comprises computer program code for calculating the connectivity metric of links along a plurality of routes, for determining a maximum connectivity metric value of each of the plurality of routes and for selecting the route having the smallest connectivity metric value

16. A computer program as in claim 11, where said first computer program code segment considerers a node'"'"'s status and the number of the node'"'"'s Slaves when estimating the link bandwidth of the node.

17. A computer program as in claim 16, where considering a node'"'"'s status considers whether a node is a Master node, a Slave node, or a Participant in Multiple Piconet (PMP) node.

18. A computer program as in claim 11, where a maximum link bandwidth B₀ is the link bandwidth between the Master and Slave nodes, when there is only one Slave node present in a piconet, and where all piconets have the same value of B₀, where M_i is the number of Slave nodes in piconet i, and P_i is the number of piconets that a PMP node connects to, and where Bi is the link bandwidth of the Master-Slave link in piconet i, and where the connectivity metric B_i/B₀, is determined at least in accordance with:

19. A computer program as in claim 11, where the value of the connectivity metric is inserted into a routing protocol packet in place of the value of a hop number.

20. A computer program as in claim 11, where the value of the connectivity metric is inserted into a routing protocol packet in conjunction with the value of a hop number.

21. A computer program as in claim 11, further comprising a computer program code segment for receiving information concerning a calculated connectivity metric from at least one other network node.

22. A computer program as in claim 11, further comprising a computer program code segment for sending information concerning a calculated connectivity metric to at least one other network node.