Determining associations in a mesh network

• US 8,355,343 B2
• Filed: 01/11/2008
• Issued: 01/15/2013
• Est. Priority Date: 01/11/2008
• Status: Active Grant

• Current Assignee: Ruckus IP Holdings LLC
• Original Assignee: Ruckus Wireless, Inc. (CommScope Holding Company, Inc.)
• Inventors: Kish, William S.
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): Kang, Suk Jin
• Application Number:
  US12/008,715
• Publication Number:
  US 20090180396A1
• Time in Patent Office: 1,831 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

Determining associations in wireless mesh networks are provided. In a mesh network that includes a wired border node and multiple wireless nodes, each wireless node advertises a backhaul throughput approximating the throughput between that wireless node and the wired border node. Using the advertised backhaul throughput information and the stored local throughput information, a receiving node determines a node association from among various candidate nodes.

Claims

1. A method for determining associations in a mesh network, the method comprising:

storing information in memory of a first node concerning local throughputs in the mesh network, each local throughput approximating a throughput between the first node and a candidate node, wherein the mesh network includes a plurality of candidate nodes;

receiving at the first node information concerning backhaul throughput from one or more candidate nodes in the mesh network, each backhaul throughput approximating a throughput between one of the candidate nodes and a wired border node in the mesh network;

executing instructions stored in memory of the first node, wherein execution of the instructions by a processor of the first node determines an uplink throughput for each of the one or more candidate nodes in the mesh network, each uplink throughput being based on at least the stored local throughput associated with one of the candidate nodes and the backhaul throughput associated with the candidate node;

connecting the first node to a second node, the second node selected from the plurality of candidate nodes in the mesh network based on at least an uplink throughput determined for the second node;

receiving at the first node updated backhaul throughputs associated with each of the plurality of candidate nodes in the network;

executing instructions stored in memory of the first node, wherein execution of the instructions by the processor of the first node determines that an updated uplink throughput of a third node exceeds an updated uplink throughout of the second node by a threshold amount;

disconnecting the first node from the second node; and

connecting the first node to the third node based on the updated uplink throughput of the third node exceeding the updated uplink throughput of the second node by a threshold amount.

2. The method of claim 1, further comprising determining the local throughputs between the first node and the plurality of candidate nodes in the network, each local throughput being determined based on results of transmission attempts to one of the candidate nodes.

3. The method of claim 1, wherein storing information in memory comprises maintaining a data table including throughput information associated with the plurality of candidate nodes in the network, and sorting the data table by ranking the uplink throughputs associated with the plurality of candidate nodes in the network.

4. The method of claim 1, wherein the uplink throughput associated with the second node is the greatest uplink throughput among the uplink throughputs associated with the plurality of candidate nodes in the network.

5. The method of claim 1, wherein connecting the first node to the second node is further based on heuristics for determining whether or not to make the connection.

6. The method of claim 1, further comprising broadcasting the uplink throughput associated with the second node as the backhaul throughput of the first node, the broadcast being broadcast from the first node to other nodes in the network.

7. The method of claim 1, wherein determination of an uplink throughput of a candidate node is based on the formula 1/(I/local throughput +1/backhaul throughput), the local throughput and the backhaul throughput both being associated with the candidate node.

8. An apparatus for determining associations in a mesh network, the apparatus comprising:

a data table that stores estimated throughput information concerning a plurality of candidate nodes in the mesh network, the throughput information including;

local throughput information, each local throughput approximating a throughput between a first node and one of the candidate nodes, and

backhaul throughput information, each backhaul throughput approximating a throughput between one of the candidate nodes and a wired border node in the mesh network;

a processor that executes instructions stored in memory to;

determine an uplink throughput for each of one or more candidate nodes, each uplink throughput being based on at least the local throughput associated with one of the candidate nodes and the backhaul throughput associated with the candidate node as indicated by the data table, and

select a second node from the plurality of candidate nodes for establishing a wireless connection based on at least the uplink throughput determined for the second node; and

an antenna that;

wirelessly connects the first node to the identified second node,

receives updated backhaul throughputs associated with each of the plurality of candidate nodes in the network,

disconnects the first node from the second node, and

connects the first node to the third node based on an updated uplink throughput of a third node being determined to exceeding an updated uplink throughput of the second node by a threshold amount.

9. The apparatus of claim 8, wherein the antenna receives the estimated throughput information from the one or more of the plurality of candidate nodes in the network.

10. The apparatus of claim 8, wherein the data table stores updates concerning the estimated throughput information associated with the plurality of candidate nodes in the network.

11. The apparatus of claim 8, wherein the antenna broadcasts the estimated throughput to other nodes in the network.

12. A mesh network system comprising

a wired border node configured to act as a gateway between a wired network and a plurality of wireless nodes;

and

a first wireless node that;

stores information in memory concerning local throughputs, each local throughput approximating a throughput between the first wireless node and a candidate node, wherein the network includes a plurality of candidate nodes, the plurality of candidate nodes including the border node and one or more of the plurality of other wireless nodes,

receives backhaul throughputs from one or more candidate nodes, each backhaul throughput approximating a throughput between one of the candidate nodes and the wired border node,

determines an uplink throughput for each of the one or more candidate nodes, each uplink throughput based on at least the stored local throughout associated with the candidate node and the backhaul throughput received from the candidate node,

wirelessly connects to a selected candidate node based on at least the uplink throughput determined for the selected candidate node,

receives updated backhaul throughputs associated with each of the plurality of candidate nodes in the network,

disconnects from the second node, and

connects to a third node based on an updated uplink throughput of a third node being determined to exceed an updated uplink throughput of the second node by a threshold amount.

13. The mesh network system of claim 12, wherein the first wireless node is further configured to be able to connect to one candidate node at a time.

14. The mesh network system of claim 12, further comprising the plurality of other wireless nodes.

15. The mesh network system of claim 12, wherein a set of wireless nodes from the plurality of wireless nodes automatically connects to the wired border node.

16. A non-transitory computer-readable storage medium having embodied thereon a program, the program being executable by a computer processor to perform a method for determining associations in a wireless network comprising:

storing information concerning local throughputs, each local throughput approximating a throughput between a first node and a candidate node, wherein the network includes a plurality of candidate nodes;

receiving information concerning backhaul throughput from one or more candidate nodes in the network, each backhaul throughput approximating a throughput between one of the candidate nodes and a wired border node in the network;

determining an uplink throughput for each of the one or more candidate nodes in the network, each uplink throughput being based on at least the stored local throughput associated with one of the candidate nodes and the backhaul throughput associated with the candidate node;

selecting a second node from the plurality of candidate nodes in the network for establishing a wireless connection based on at least an uplink throughput determined for the second node,

receiving at the first node updated backhaul throughputs associated with each of the plurality of candidate nodes in the network;

determining that an updated uplink throughput of a third node exceeds an updated uplink throughout of the second node by a threshold amount;

deselecting the second node;

and selecting the third node for establishing a wireless connection based on the updated uplink throughput of the third node exceeding the updated uplink throughput of the second node by a threshold amount.