Bluetooth personal area network routing protocol optimization using connectivity metric

• US 7,706,282 B2
• Filed: 06/25/2003
• Issued: 04/27/2010
• Est. Priority Date: 06/25/2003
• Status: Expired due to Fees

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Spyder Navigations LLC (Intellectual Ventures LLC)
• Inventors: Huang, Leping
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): NG, CHRISTINE Y
• Application Number:
  US10/606,437
• Publication Number:
  US 20040264466A1
• Time in Patent Office: 2,498 Days
• Field of Search: 370/238, 370/254, 370/255, 370/338, 370/351, 370/400, 370/401
• US Class Current: 370/238
• 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 of selecting a route for communicating information in a communication network, the method comprising:

receiving a connectivity metric for each of a plurality of links defining each of a plurality of routes that connect a start node with an end node, each link of the plurality of links including a first node and a second node, wherein the first node is a first type of node selected from a first master node, a first slave node, and a first multiple network participant node, wherein the second node is a second type of node selected from a second master node, a second slave node, and a second multiple network participant node, and further wherein the received connectivity metric for a link of the plurality of links is determined based on the first type of node and the second type of node;

determining a total connectivity metric for each of the plurality of routes based on the received connectivity metric for each of the plurality of links defining each of the plurality of routes; and

selecting a route in a communication network for communicating information between the start node and the end node from the plurality of routes based on the determined total connectivity metric.

2. The method of claim 1 wherein, if the first node is the first master node in a sub-network of the communication network and the second node is the second slave node in the sub-network, the connectivity metric is a number of slave nodes in the sub-network.

3. The method of claim 1 wherein, if the second node is the second master node in a sub-network of the communication network and the first node is the first slave node in the sub-network, the connectivity metric is a number of slave nodes in the sub-network.

4. The method of claim 1 wherein the first multiple network participant node comprises a first master multiple network participant node and a first slave multiple network participant node wherein the first master multiple network participant node participates in a sub-network of the communication network as a master node, and further wherein the first slave multiple network participant node does not participate in the communication network as a master node.

5. The method of claim 4 wherein, if the first node is the first slave multiple network participant node between a first sub-network and a second sub-network and the second node is the second master node in the second sub-network, the received connectivity metric is calculated at least in part by solving P_i*MAX(M_i, M_j) where P_i is a number of master nodes that the first node connects to in the communication network, M_i is a first number of slave nodes in the first sub-network, and M_j is a second number of slave nodes in the second sub-network.

6. The method of claim 4 wherein, if the first node is the first master multiple network participant node and the first node participates as a master node in a first sub-network and the second node is the second master node in a second sub-network, the received connectivity metric is calculated at least in part by solving MAX(M_k+1, M_i) where M_k is a first number of slave nodes in the first sub-network, and M_i is a second number of slave nodes in the second sub-network.

7. The method of claim 4 wherein, if the first node is the first slave multiple network participant node between a first sub-network and a second sub-network and the second node is the second master node in the second sub-network, the received connectivity metric is calculated at least in part by solving

8. The method of claim 7 further comprising estimating the first estimated bandwidth and estimating the second estimated bandwidth.

9. The method of claim 8 wherein estimating the first estimated bandwidth comprises use of a model of a network medium access control algorithm.

10. The method of claim 8 wherein estimating the first estimated bandwidth comprises use of a model of a Bluetooth network medium access control algorithm.

11. The method of claim 4 wherein, if the first node is the first master multiple network participant node and the first node participates as a master node in a first sub-network and the second node is the second master node in a second sub-network, the received connectivity metric is calculated at least in part by solving

12. The method of claim 1 wherein determining the total connectivity metric of a route of the plurality of routes comprises identifying a maximum connectivity metric of the plurality of links defining the route.

13. The method of claim 1 further comprising communicating the received connectivity metric to a node of the communication network.

14. The method of claim 13 wherein communicating the received connectivity metric comprises inserting the calculated connectivity metric into a routing protocol packet.

15. The method of claim 14 wherein the received connectivity metric is inserted into the routing protocol packet in place of a hop number.

16. The method of claim 1, wherein the connectivity metric for each of the plurality of links is based on a ratio of a maximum link bandwidth to an estimated link bandwidth, wherein the maximum link bandwidth is a link bandwidth between a master node and a slave node when there is only one slave node connected to the master node., and wherein the estimated link bandwidth is an estimate of a current bandwidth capacity of a respective link of the plurality of links.

17. A computer-readable medium including computer-readable instructions that, upon execution by a processor, cause the processor to select a route for communicating information in a communication network, the instructions configured to cause a computing device to:

receive a connectivity metric for each of a plurality of links defining each of a plurality of routes that connect a start node with an end node, each link of the plurality of links including a first node and a second node, wherein the first node is a first type of node selected from a first master node, a first slave node, and a first multiple network participant node, wherein the second node is a second type of node selected from a second master node, a second slave node, and a second multiple network participant node, and further wherein the received connectivity metric for a link of the plurality of links is determined based on the first type of node and the second type of node;

determine a total connectivity metric for each of the plurality of routes based on the received connectivity metric for each of the plurality of links defining each of the plurality of routes; and

select a route in a communication network for communicating information between the start node and the end node from the plurality of routes based on the determined total connectivity metric.

18. The computer-readable medium of claim 17 wherein, if the first node is the first master node in a sub-network of the communication network and the second node is the second slave node in the sub-network, the connectivity metric is a number of slave nodes in the sub-network.

19. The computer-readable medium of claim 17 wherein, if the second node is the second master node in a sub-network of the communication network and the first node is the first slave node in the sub-network, the connectivity metric is a number of slave nodes in the sub-network.

20. The computer-readable medium of claim 17 wherein the first multiple network participant node comprises a first master multiple network participant node and a first slave multiple network participant node wherein the first master multiple network participant node participates in a sub-network of the communication network as a master node, and further wherein the first slave multiple network participant node does not participate in the communication network as a master node.

21. The computer-readable medium of claim 20 wherein, if the first node is the first slave multiple network participant node between a first sub-network and a second sub-network and the second node is the second master node in the second sub-network, the received connectivity metric is calculated at least in part by solving P_i*MAX(M_i, M_j) where P_i is a number of master nodes that the first node connects to in the communication network, M_i is a first number of slave nodes in the first sub-network, and M_j is a second number of slave nodes in the second sub-network.

22. The computer-readable medium of claim 20 wherein, if the first node is the first master multiple network participant node and the first node participates as a master node in a first sub-network and the second node is the second master node in a second sub-network, the received connectivity metric is calculated at least in part by solving MAX(M_k+1, M_i) where M_k is a first number of slave nodes in the first sub-network, and M_i is a second number of slave nodes in the second sub-network.

23. The computer-readable medium of claim 20 wherein, if the first node is the first slave multiple network participant node between a first sub-network and a second sub-network and the second node is the second master node in the second sub-network, the received connectivity metric is calculated at least in part by solving

24. The computer-readable medium of claim 17 wherein determining the total connectivity metric of a route of the plurality of routes comprises identifying a maximum connectivity metric of the plurality of links defining the route.

25. The computer-readable medium of claim 17, wherein the connectivity metric for each of the plurality of links is based on a ratio of a maximum link bandwidth to an estimated link bandwidth, wherein the maximum link bandwidth is a link bandwidth between a master node and a slave node when there is only one slave node connected to the master node, and wherein the estimated link bandwidth is an estimate of a current bandwidth capacity of a respective link of the plurality of links.

26. A device for selecting a route for communicating information in a communication network, the device comprising:

a data processor, the data processor configured to

receive a connectivity metric for each of a plurality of links defining each of a plurality of routes that connect a start node with an end node, each link of the plurality of links including a first node and a second node, wherein the first node is a first type of node selected from a first master node, a first slave node, and a first multiple network participant node, wherein the second node is a second type of node selected from a second master node, a second slave node, and a second multiple network participant node, and further wherein the received connectivity metric for a link of the plurality of links is determined based on the first type of node and the second type of node;

determine a total connectivity metric for each of the plurality of routes based on the received connectivity metric for each of the plurality of links defining each of the plurality of routes; and

select a route in a communication network for communicating information between the start node and the end node from the plurality of routes based on the determined total connectivity metric; and

a communication interface, the communication interface configured to communicate the information to a communication network based on the selected route.

27. The device of claim 26 wherein, if the first node is the first master node in a sub-network of the communication network and the second node is the second slave node in the sub-network, the connectivity metric is a number of slave nodes in the sub-network.

28. The device of claim 26 wherein the first multiple network participant node comprises a first master multiple network participant node and a first slave multiple network participant node wherein the first master multiple network participant node participates in a sub-network of the communication network as a master node, and further wherein the first slave multiple network participant node does not participate in the communication network as a master node.

29. The device of claim 28 wherein, if the first node is the first slave multiple network participant node between a first sub-network and a second sub-network and the second node is the second master node in the second sub-network, the received connectivity metric is calculated at least in part by solving P_i*MAX(M_i, M_j) where P_i is a number of master nodes that the first node connects to in the communication network, M_i is a first number of slave nodes in the first sub-network, and M_i is a second number of slave nodes in the second sub-network.

30. The device of claim 28 wherein, if the first node is the first master multiple network participant node and the first node participates as a master node in a first sub-network and the second node is the second master node in a second sub-network, the received connectivity metric is calculated at least in part by solving MAX(M_k+1, M_i) where M_k is a first number of slave nodes in the first sub-network, and M_i is a second number of slave nodes in the second sub-network.

31. The device of claim 28 wherein, if the first node is the first slave multiple network participant node between a first sub-network and a second sub-network and the second node is the second master node in the second sub-network, the received connectivity metric is calculated at least in part by solving

32. The device of claim 26 wherein determining the total connectivity metric of a route of the plurality of routes comprises identifying a maximum connectivity metric of the plurality of links defining the route.

33. The device of claim 26, wherein the connectivity metric for each of the plurality of links is based on a ratio of a maximum link bandwidth to an estimated link bandwidth, wherein the maximum link bandwidth is a link bandwidth between a master node and a slave node when there is only one slave node connected to the master node, and wherein the estimated link bandwidth is an estimate of a current bandwidth capacity of a respective link of the plurality of links.