Technique for establishing a mesh network
In order to establish a mesh network, an electronic device may iteratively identify one or more mesh-network nodes and may determine associated duty-cycle ratios based on communication with the one or more mesh-network nodes. In particular, the electronic device may select candidate mesh-network nodes based on estimated throughput metrics of their communication with a root device in the mesh network. Then, for each of the candidate mesh-network nodes, the electronic device may associate with a given candidate mesh-network node, and may measure the throughput of the given candidate mesh-network node during a time interval by communicating packets. Based on comparisons of the measured throughputs, the electronic device may identify the one or more mesh-network nodes in the candidate mesh-network nodes and may determine the associated duty-cycle ratios. Subsequently, the electronic device communicates information with the root device via the one or more mesh-network nodes based on the duty-cycle ratios.
1. An electronic device, comprising:
an interface circuit configured to communicate with two or more electronic devices, wherein the electronic device is configured to:
select candidate mesh-network nodes to a root device in a mesh network;
measure throughputs of the candidate mesh-network nodes by providing, to one or more output nodes of the electronic device, packets intended for the candidate mesh-network nodes, and receiving, from one or more input nodes of the electronic device, acknowledgments from the candidate mesh-network nodes, wherein a throughput of a given candidate mesh-network node in the candidate mesh-network nodes comprises a data rate for successful communication;
identify one or more mesh-network nodes in the candidate mesh-network nodes and determine associated communication duty-cycle ratios based on the measured throughputs, wherein a communication duty-cycle ratio of a given mesh-network node in the one or more mesh-network nodes specifies an amount of communication that occurs via the given mesh-network node in the mesh network relative to an amount of communication that occurs via a remainder of the one or more mesh-network nodes in the mesh network; and
provide, to the one or more output nodes, information intended for the root device via the one or more mesh-network nodes based on the communication duty-cycle ratios, wherein the one or more mesh-network nodes comprise a dynamically determined communication path in the mesh network.
2. The electronic device of claim 1 , wherein the candidate mesh-network nodes are selected based on estimated throughputs; and
wherein an estimated throughput metric of a given candidate mesh-network node is based on one of: a received signal strength indication, airtime usage by the given candidate mesh-network node, and an advertised throughput associated with the given candidate mesh-network node.
3. The electronic device of claim 2 , wherein at least one of the airtime usage and the advertised throughput are included in beacons communicated in the mesh network.
4. The electronic device of claim 1 , wherein the candidate mesh-network nodes are selected based on estimated throughputs; and
wherein an estimated throughput metric of a given candidate mesh-network node corresponds to a throughput between the given candidate mesh-network node and the root device in the mesh network and a throughput metric between the given candidate mesh-network node and the electronic device.
5. The electronic device of claim 1 , wherein the measured throughput comprises an uplink throughput.
6. The electronic device of claim 1 , wherein the measured throughput corresponds to one hop in the mesh network.
7. The electronic device of claim 1 , wherein the throughputs of the candidate mesh-network nodes are measured in a round-robin fashion.
8. The electronic device of claim 1 , wherein, when a measured throughput of a candidate mesh-network node exceeds the other measured throughputs by a predefined value, the one or more mesh-network nodes comprise the candidate mesh-network node and the associated communication duty-cycle ratio is one hundred percent.
9. The electronic device of claim 1 , wherein, when maximum measured throughputs, which are associated with at least two candidate mesh-network nodes, are within a predefined value of each other, the one or more mesh-network nodes comprise at least the two candidate mesh-network nodes and the associated communication duty-cycle ratios are based on ratios of the measured throughputs of at least the two candidate mesh-network nodes.
10. An electronic device, comprising:
an interface circuit configured to communicate with two or more electronic devices, wherein the electronic device is configured to:
select candidate mesh-network nodes to a root device in a mesh network;
measure throughputs of the candidate mesh-network nodes by providing, to one or more output nodes of the electronic device, packets intended for the candidate mesh-network nodes, and receiving, from one or more input nodes of the electronic device, acknowledgments from the candidate mesh-network nodes;
identify one or more mesh-network nodes in the candidate mesh-network nodes and determine associated communication duty-cycle ratios based on the measured throughputs; and
provide, to the one or more output nodes, information intended for the root device via the one or more mesh-network nodes based on the communication duty-cycle ratios, wherein the one or more mesh-network nodes comprise a dynamically determined communication path in the mesh network, wherein the operations of measuring, identifying, determining and communicating are repeated until a convergence criterion is achieved.
11. The electronic device of claim 1 , wherein the one or more mesh-network nodes are identified and the communication duty-cycle ratios are determined using Bayesian analysis.
12. The electronic device of claim 1 , wherein the electronic device and the two or more electronic devices comprise access points.
13. The electronic device of claim 1 , wherein the electronic device further comprises an antenna coupled to the interface circuit.
14. A non-transitory computer-readable storage medium for use in conjunction with an electronic device, the computer-readable storage medium storing a program module that, when executed by the electronic device, causes the electronic device to:
select candidate mesh-network nodes to a root device in a mesh network;
measure throughputs of the candidate mesh-network nodes by providing, to one or more output nodes of the electronic device, packets intended for the candidate mesh-network nodes, and receiving, from one or more input nodes of the electronic device, acknowledgments from the candidate mesh-network nodes, wherein a throughput of a given candidate mesh-network node in the candidate mesh-network nodes comprises a data rate for successful communication;
identify one or more mesh-network nodes in the candidate mesh-network nodes and determine associated communication duty-cycle ratios based on the measured throughputs, wherein a communication duty-cycle ratio of a given mesh-network node in the one or more mesh-network nodes specifies an amount of communication that occurs via the given mesh-network node in the mesh network relative to an amount of communication that occurs via a remainder of the one or more mesh-network nodes in the mesh network; and
provide, to the one or more output nodes, information intended for the root device via the one or more mesh-network nodes based on the communication duty-cycle ratios, wherein the one or more mesh-network nodes comprise a dynamically determined communication path in the mesh network.
15. The computer-readable storage medium of claim 14 , wherein the candidate mesh-network nodes are selected based on estimated throughputs; and
wherein an estimated throughput metric of a given candidate mesh-network node is based on one of: a received signal strength indication, airtime usage by the given candidate mesh-network node, and an advertised throughput associated with the given candidate mesh-network node.
16. The computer-readable storage medium of claim 14 , wherein, when a measured throughput of a candidate mesh-network node exceeds the other measured throughputs by a predefined value, the one or more mesh-network nodes comprise the candidate mesh-network node and the associated communication duty-cycle ratio is one hundred percent.
17. The computer-readable storage medium of claim 14 , wherein, when maximum measured throughputs, which are associated with at least two candidate mesh-network nodes, are within a predefined value of each other, the one or more mesh-network nodes comprise at least the two candidate mesh-network nodes and the associated communication duty-cycle ratios are based on ratios of the measured throughputs of at least the two candidate mesh-network nodes.
18. The computer-readable storage medium of claim 14 , wherein the operations of measuring, identifying, determining and communicating are repeated until a convergence criterion is achieved.
19. The computer-readable storage medium of claim 14 , wherein the one or more mesh-network nodes are identified and the communication duty-cycle ratios are determined using Bayesian analysis.
20. A method for establishing a mesh network, wherein the method comprises:
by an electronic device:
selecting candidate mesh-network nodes to a root device in the mesh network;
measuring throughputs of the candidate mesh-network nodes by providing, to one or more output nodes of the electronic device, packets intended for the candidate mesh-network nodes, and receiving, from one or more input nodes of the electronic device, acknowledgments from the candidate mesh-network nodes, wherein a throughput of a given candidate mesh-network node in the candidate mesh-network nodes comprises a data rate for successful communication;
identifying one or more mesh-network nodes in the candidate mesh-network nodes and determine associated communication duty-cycle ratios based on the measured throughputs, wherein a communication duty-cycle ratio of a given mesh-network node in the one or more mesh-network nodes specifies an amount of communication that occurs via the given mesh-network node in the mesh network relative to an amount of communication that occurs via a remainder of the one or more mesh-network nodes in the mesh network; and
providing, to the one or more output nodes, information intended for the root device via the one or more mesh-network nodes based on the communication duty-cycle ratios, wherein the one or more mesh-network nodes comprise a dynamically determined communication path in the mesh network.
21. The method of claim 20 , wherein the candidate mesh-network nodes are selected based on estimated throughputs; and
wherein an estimated throughput metric of a given candidate mesh-network node is based on one of: a received signal strength indication, airtime usage by the given candidate mesh-network node, and an advertised throughput associated with the given candidate mesh-network node.
22. The method of claim 20 , wherein the candidate mesh-network nodes are selected based on estimated throughputs; and
wherein an estimated throughput metric of a given candidate mesh-network node corresponds to a throughput between the given candidate mesh-network node and the root device in the mesh network and a throughput metric between the given candidate mesh-network node and the electronic device.