Efficient scatternet forming

• US 20020044549A1
• Filed: 06/08/2001
• Published: 04/18/2002
• Est. Priority Date: 06/12/2000
• Status: Abandoned Application

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Gehrmann, Christian, Larsson, Tony, Rune, Johan, Johansson, Per
• Application Number:
  US09/876,087
• Publication Number:
  US 20020044549A1
• Time in Patent Office: Days
• US Class Current: 370/386
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 76/10 Connection setup
• CPC Class Codes: H04W 8/20 Transfer of user or subscriber data
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Two logically separated scatternets, the maximum connectivity scatternet (MCS) and the traffic scatternet (TS) are provided. An MCS maintains information about all nodes in the scatternet in order to facilitate a quick path establishment when a destination node is searched for. The MCS is maintained autonomously as new nodes arrive to the scatternet and other nodes leave the scatternet. A TS is established on a per session basis, primarily between two nodes in the scatternet. The TS is designed to achieve the best possible performance for the data flow between the involved nodes. When supported, in addition to establishing dedicated TS piconets and/or dedicated TS links, this may involve switching to the Bluetooth high speed mode on TS links. An overall scatternet may consist of one MCS and several TSs.

This application claims priority under 35 U.S.C. §119(e) to U.S. provisional application No. 60/210,908 filed Jun. 12, 2000, the entire disclosure of which is herein expressly incorporated by reference.

Claims

1. A method for routing information in an ad-hoc network, wherein the adhoc network includes a plurality of sub-networks, the method comprising the steps of:

forming another plurality of sub-networks using the nodes of the plurality of sub-networks, wherein a master of each of the another plurality of sub-networks includes information regarding each slave of its respective sub-network, wherein the another plurality of sub-networks is formed to minimize the number of connections between the another plurality of sub-networks, and whereby the another plurality of sub-networks form a maximum connectivity network;

sending information from a first node to a second node using the maximum connectivity network;

establishing a traffic network between the first node and the second node; and

moving the information sent between the first node and the second node from the maximum connectivity network to the established traffic network.

2. The method of claim 1, wherein the traffic network includes nodes of the maximum connectivity network.

3. The method of claim 1, wherein nodes which are members of the traffic network suspend participation in their respective one of the another plurality of sub-networks when participating in the traffic network.

4. The method of claim 1, wherein the traffic network includes more than one master node.

5. The method of claim 4, wherein each of the sub-networks in the plurality of sub-networks and the another plurality of sub-networks include only one master node for each sub-network.

6. The method of claim 1, wherein the traffic network operates according to a high-speed mode.

7. The method of claim 1, wherein the forming step comprises the steps of:

paging, from the first node, the master node with the highest number of slave nodes among all master nodes which are detected by the first node, wherein the master node is not a member of the same sub-network as the first node;

sending a request from the first node to the master node to become a member of the master node'"'"'s sub-network; and

joining the master node'"'"'s sub-network if the request is granted.

8. The method of claim 7, wherein if the request is not granted performing the steps of:

paging, from the first node, another master node with the next highest number of slave node'"'"'s among all master node'"'"'s which are detected by the first node;

sending a request from the first node to the another master node to become a member of the master node'"'"'s sub-network; and

joining the another master node'"'"'s sub-network if the request is granted.

9. The method of claim 7, wherein the first node is in an idle state.

10. The method of claim 7, further comprising the steps of:

paging, from the first node, a slave node with the highest identification number among all slave nodes which are detected by the first node, wherein the slave node is not a member of the same sub-network as the first node;

requesting the identification number of the slave node'"'"'s master node;

sending a request from the first node to the slave node'"'"'s master node to become a member of the sub-network of the slave node'"'"'s master node; and

joining the sub-network of the slave node'"'"'s master node if the request is granted.

11. The method of claim 1, wherein the forming step comprises the steps of:

sending a message from a slave node informing the slave node'"'"'s master node of the number of nodes connected in detected sub-networks and the identification number of the nodes in the detected sub-networks, wherein the slave node is not a member of the detected sub-network; and

paging, by the slave node, a node in the detected sub-networks if the slave node'"'"'s master node requests the slave node to perform the paging.

12. The method of claim 1, wherein the forming step comprises the steps of:

paging, from the first node, a master node, wherein the first node and the master node are not members of the same sub-networks and wherein the first node is a master node;

obtaining the addresses of all slave nodes of the paged master node; and

merging sub-networks if the first node can reach all of the slave nodes of the paged master node.

13. The method of claim 12, further comprising the steps of:

reporting to the first node from another node identification of all nodes which can be reached from the another node, wherein the first node and the another node are members of the same network and the first node is a master of the subnetwork; and

making the another node the master of the sub-network if the another node reaches more nodes than the first node.

14. The method of claim 1, wherein the step of establishing a traffic network comprises the steps of:

paging from the first node to the second node over the maximum connectivity network; and

initiating from the second node a scanning procedure for a first traffic network between the first node and second node, wherein information sent between the first node and the second node is moved to the traffic network if establishment of the traffic network is successful.

15. The method of claim 14, wherein if the traffic network establishment fails, performing the steps of:

searching for the second node in any established traffic network;

using one of the any established traffic networks to communicate information between the first node and the second node if the one of the any established traffic route networks has less intermediate nodes than the route over the maximum connectivity network.

16. The method of claim 15, wherein if the traffic network has more intermediate nodes than the route over the maximum connectivity network or if the second node is not found in any established traffic network, performing the steps of:

sending, from the second node to the first node, a list of candidate nodes including all intermediate nodes in the route over the maximum connectivity network;

adding in each master node along the route over the maximum connectivity network additional candidate nodes;

paging, from the first node, a first node in the list of candidate nodes, wherein the first node in the list of candidate nodes is the closest node in the list of candidate nodes to the second node;

setting up a connection between the first node and the first node in the list of candidate nodes if the first node in the list of candidate nodes responds to the page;

paging from the first node in the list of candidate nodes to the second node; and

establishing a traffic network to communicate information between the first node and the second node including the first node in the list of candidate nodes if the established traffic route network has less intermediate nodes than the route over the maximum connectivity network.

17. The method of claim 1, wherein the step of establishing a traffic network comprises the steps of:

selecting a first candidate node;

determining if the first candidate node can reach the first node or any other candidate nodes;

establish a candidate node rating if the candidate node can reach the first node or any other candidate nodes;

determining if the first candidate node is a member of more than a predetermined number of sub-networks; and

adding the first candidate node and the associated candidate node rating to a candidate node list if the first candidate node is a member of less than the predetermined number of sub-networks.

18. The method of claim 17, further comprising the steps of:

selecting a second candidate node;

determining if the second candidate node can reach the first node or any other candidate nodes;

establish a candidate node rating if the candidate node can reach the first node or any other candidate nodes;

determining if the second candidate node is a member of more than a predetermined number of sub-networks; and

adding the second candidate node and the associated candidate node rating to a candidate node list if the second candidate node is a member of less than the predetermined number of sub-networks.

19. The method of claim 1, wherein the step of establishing a traffic network comprises the steps of:

selecting in the first node a first candidate node;

including the first candidate node to a candidate node list; and

forwarding the candidate node list to a next node in a route in the maximum connectivity network between the first node and a second node.

20. The method of claim 19, further comprising the steps of:

determining in the next node whether a second candidate node which meets a predetermined criteria is connected in a same sub-network as the next node;

comparing the second candidate node with the first candidate node if the second candidate node which meets the predetermined criteria is connected in the same sub-network as the next node;

replacing the first candidate node with the second candidate node in the candidate node list if the second candidate node can reach the first node and the second node; and

forwarding the candidate node list to another next node in the route in the maximum connectivity network.

21. The method of claim 20, further comprising the steps of:

adding the second candidate node to the candidate node list if the second candidate node can reach the first candidate node and the second node.

22. The method of claim 20, further comprising the steps of:

selecting by the another candidate node an earliest candidate node in the list of candidate nodes that can be reached by the another candidate node;

determining if the another candidate node has a greater rating than a node which follows the earliest candidate node in the candidate node list; and

replacing the node which follows the earliest candidate node and all subsequently following candidate nodes with the another candidate node in the candidate node list if the another candidate node has a greater rating than the node which follows the earliest node.

23. The method of claim 22, further comprising the steps of:

determining the earliest node in the candidate node list which can be reached by the second node;

deleting all nodes following the earliest node which can be reached by the second node from the candidate node list; and

determining if the remaining path of nodes in the candidate node list between the first node and the second node is better than the path in the maximum connectivity network between the first node and the second node.

24. The method of claim 19, further comprising the steps of:

sending from the second node a page and synchronization message to a preceding node in the candidate node list;

entering a paging phase with the preceding node if the preceding node responds to the second node with a confirmation of a scheduled page time contained in the page and synchronization message.

25. The method of claim 1, wherein the step of establishing a traffic network between the first node and the second node comprises the steps of:

determining whether the first node has information regarding other nodes of the maximum connectivity network that the first node can reach.

26. The method of claim 26, wherein other nodes of the maximum connectivity network can be reached by the first node if the other nodes are within radio range of the first node.

27. The method of claim 25, wherein the determining step is performed for each node of the maximum connectivity network.

28. The method of claim 25, wherein if it is determined that the first node does not have information regarding other nodes of the maximum connectivity network that the first node can reach then performing the steps of:

broadcasting a first message from the first node and the second node, wherein the message includes information regarding a time and frequency at which a second message will be transmitted by the first and the second nodes;

returning, in response to receipt of the second message, a third message to the first node; and

determining whether there is a node which can be reached directly from the first and second nodes.

29. The method of claim 28, wherein if it is determined that there is not a node which can be reached by both the first and second node, performing the steps of:

instructing, by the first node, another first node to broadcast another first message which includes information regarding a time and frequency at which another second message will be transmitted by the another first node, wherein the another first node is the farthest node which can be reached directly from the first node; and

instructing, by the first node, another second node to broadcast another first message which includes information regarding a time and frequency at which another second message will be transmitted by the another second node, wherein the another second node is the farthest node which can be reached directly from the second node.

30. The method of claim 29, wherein if it is determined that there is a node which can be reached directly by both the another first node and the another second node, then calculating a metric for a traffic network between the first node and the second node, wherein the traffic network includes the node which can be reached directly by both the another first node and the another second node, the another first node and the another second node.

31. A method for forming a plurality of sub-networks in an ad-hoc network comprising the steps of:

paging, from a first node, a master node with the highest number of slave nodes among all master nodes which are detected by the first node, wherein the master node is not a member of the same sub-network as the first node;

sending a request from the first node to the master node to become a member of the master node'"'"'s sub-network; and

joining the master node'"'"'s sub-network if the request is granted.

32. The method of claim 31, wherein if the request is not granted performing the steps of:

paging, from the first node, another master node with the next highest number of slave node'"'"'s among all master node'"'"'s which are detected by the first node;

sending a request from the first node to the another master node to become a member of the master node'"'"'s sub-network; and

joining the another master node'"'"'s sub-network if the request is granted.

33. The method of claim 31, wherein the first node is in an idle state.

34. The method of claim 31, further comprising the steps of:

paging, from the first node, a slave node with the highest identification number among all slave nodes which are detected by the first node, wherein the slave node is not a member of the same sub-network as the first node;

requesting the identification number of the slave node'"'"'s master node;

sending a request from the first node to the slave node'"'"'s master node to become a member of the sub-network of the slave node'"'"'s master node; and

joining the sub-network of the slave node'"'"'s master node if the request is granted.

37. The method of claim 36, further comprising the steps of:

reporting to the first node from another node identification of all nodes which can be reached from the another node, wherein the first node and the another node are members of the same network and the first node is a master of the subnetwork; and

making the another node the master of the sub-network if the another node reaches more nodes than the first node.

39. The method of claim 38, wherein if the traffic route network establishment fails, performing the steps of:

searching for the destination node in any established traffic route network;

using one of the any established traffic route networks to communicate information between the source node and the destination node if the one of the any established traffic route networks has less intermediate nodes than the route over the ad-hoc network.

40. The method of claim 39, wherein if the traffic route network has more intermediate nodes than the route over the ad-hoc network or if the destination node is not found in any established traffic route network, performing the steps of:

sending, from the destination node to the source node, a list of candidate nodes including all intermediate nodes in the route over the ad-hoc network;

adding in each master node along the route over the ad-hoc network additional candidate nodes;

paging, from the source node, a first node in the list of candidate nodes, wherein the first node is the closest node in the list of candidate nodes to the destination node;

setting up a connection between the source node and the first node if the first node responds to the page;

paging from the first node to the destination node; and

establishing a traffic route network to communicate information between the source node and the destination node including the first node if the established traffic route network has less intermediate nodes than the route over the ad-hoc network.

35. A method for forming a plurality of sub-networks in an ad-hoc network comprising the steps of:

sending a message from a slave node informing the slave node'"'"'s master node of the number of nodes connected in detected sub-networks and the identification number of the nodes in the detected sub-networks, wherein the slave node is not a member of the detected sub-network; and

paging, by the slave node, a node in the detected sub-networks if the slave node'"'"'s master node requests the slave node to perform the paging.

36. A method for forming a plurality of sub-networks in an ad-hoc network comprising the steps of:

paging, from a first node, a master node, wherein the first node and the master node are not members of the same sub-networks and wherein the first node is a master node;

obtaining the addresses of all slave nodes of the paged master node; and

merging sub-networks if the first node can reach all of the slave nodes of the paged master node.

38. A method for establishing a traffic route network in an ad-hoc network including a plurality of sub-networks, the method comprising the steps of:

paging from a source node to a destination node over the ad-hoc network;

initiating from the destination node a scanning procedure for a first traffic route network between the source node and destination node; and

using the traffic route network to communicate information between the source node and the destination node if the traffic route network establishment is successful.

41. A method for establishing a traffic route network in an ad-hoc network including a plurality of sub-networks, the method comprising the steps of:

selecting a first candidate node;

determining if the first candidate node can reach a source node or any other candidate nodes;

establish a candidate node rating if the candidate node can reach the source node or any other candidate nodes;

determining if the first candidate node is a member of more than a predetermined number of sub-networks; and

adding the first candidate node and the associated candidate node rating to a candidate node list if the first candidate node is a member of less than the predetermined number of sub-networks.

42. The method of claim 41, further comprising the steps of:

selecting a second candidate node;

determining if the second candidate node can reach a source node or any other candidate nodes;

establish a candidate node rating if the candidate node can reach the source node or any other candidate nodes;

determining if the second candidate node is a member of more than a predetermined number of sub-networks; and

adding the second candidate node and the associated candidate node rating to a candidate node list if the second candidate node is a member of less than the predetermined number of sub-networks.

43. A method for establishing a traffic route network in an ad-hoc network including a plurality of sub-networks, the method comprising the steps of:

selecting in a source node a first candidate node;

including the first candidate node to a candidate node list; and

forwarding the candidate node list to a next node in a route in the ad-hoc network between the source node and a destination node.

44. The method of claim 43, further comprising the steps of:

determining in the next node whether a second candidate node which meets a predetermined criteria is connected in a same sub-network as the next node;

comparing the second candidate node with the first candidate node if the second node which meets the predetermined criteria is connected in the same subnetwork as the next node;

replacing the first candidate node with the second candidate node in the candidate node list if the second candidate node can reach the source node and the destination node; and

forwarding the candidate node list to another next node in the route in the ad-hoc network.

45. The method of claim 44, further comprising the steps of:

adding the second candidate node to the candidate node list if the second candidate node can reach the first candidate node and the destination node.

46. The method of claim 44, further comprising the steps of:

selecting by the another candidate node an earliest candidate node in the list of candidate nodes that can be reached by the another candidate node;

determining if the another candidate node has a greater rating than a node which follows the earliest candidate node in the candidate node list; and

replacing the node which follows the earliest candidate node and all subsequently following candidate nodes with the another candidate node in the candidate node list if the another candidate node has a greater rating than the node which follows the earliest node.

47. The method of claim 46, further comprising the steps of:

determining the earliest node in the candidate node list which can be reached by the destination node;

deleting all nodes following the earliest node which can be reached by the destination node from the candidate node list; and

determining if the remaining path of nodes in the candidate node list between the source node and the destination node is better than the path in the adhoc network between the source node and the destination node.

48. The method of claim 43, further comprising the steps of:

sending from a destination node a page and synchronization message to a preceding node in the candidate node list;

entering a paging phase with the preceding node if the preceding node responds to the destination node with a confirmation of a scheduled page time contained in the page and synchronization message.