System and method for convergence and automatic disabling of access points in a wireless mesh network

• US 9,173,111 B2
• Filed: 12/28/2011
• Issued: 10/27/2015
• Est. Priority Date: 12/28/2011
• Status: Active Grant

• Current Assignee: Itron Networked Solutions, Inc. (Itron, Inc.)
• Original Assignee: Silver Spring Networks, Inc. (Itron, Inc.)
• Inventors: Pace, James, Van Greunen, Jana, Hughes, Sterling, Flammer, George H. III, San Filippo, William E. III
• Primary Examiner(s): Elallam, Ahmed
• Application Number:
  US13/339,071
• Publication Number:
  US 20130170335A1
• Time in Patent Office: 1,399 Days
• Field of Search: 370/229, 370/235, 370/237, 370/238, 370/241, 370/242, 370/243, 370/246, 370/252, 370/254, 370/255
• US Class Current: 1/1
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 76/10 Connection setup
• CPC Class Codes: H04W 76/30 Connection release
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/08 Access point devices

Abstract

One embodiment of the present disclosure sets forth a technique for convergence and automatic disabling of access points in a wireless mesh network. Specifically, an access point within a wireless mesh network computes one or more network metrics to determine whether the metrics are unfavorable or favorable. If the network metrics are favorable, then the access point disables the access point'"'"'s network connection. An access point turns the network connection back on based on whether a routing was lost for at least a preset amount of time, utilization of one or more neighboring access points is above a preset value, or one or more network metrics have degraded by a certain percentage value. One advantage of this approach is that cost savings may be achieved when the number of access points dynamically changes to accommodate varying communications conditions.

Claims

1. A computer-implemented method for connecting as an access point to a network, the method comprising:

determining that routing connectivity within the network has not been lost or has been lost for less than a predetermined amount of time;

selecting a first access point to query;

querying the first access point with respect to utilization;

determining that the utilization of the first access point is greater than a critical value, that the utilization of the first access point is greater than a predetermined limit that is less than the critical value, that the utilization of the first access point is greater than a predetermined percentage of the utilization of the network, or that another network metric has degraded by more than a predetermined amount;

determining a random delay period proportionate to a routing cost within the network;

waiting for the duration of the random delay period;

after the random delay period, determining that the utilization of the first access point remains greater than the critical value, that the utilization of the first access point remains greater than the predetermined limit, that the utilization of the first access point remains greater than the predetermined percentage of the utilization of the network, or that the another network metric remains degraded by more than the predetermined amount; and

in response, turning on a network connection to connect as an access point to the network.

2. The method of claim 1, wherein the another network metric is associated with a hop count between the first access point and a nearest neighbor access point.

3. The method of claim 1, wherein the another network metric is associated with a utilization value corresponding to the first access point.

4. The method of claim 1, wherein the another network metric is associated with an amount of data being forwarded to a server relative to a data transmission capability associated with the first access point.

5. The method of claim 1, wherein the another network metric comprises a routing metric.

6. The method of claim 1, wherein the network comprises a general packet radio service (GPRS) network.

7. A non-transitory computer-readable medium including instructions that, when executed by a processor included in a node, cause the processor to determine whether to connect as an access point to a network, by performing the steps of:

determining that routing connectivity within the network has not been lost or has been lost for less than a predetermined amount of time;

selecting a first access point to query;

querying the first access point with respect to utilization;

determining that the utilization of the first access point is greater than a critical value, that the utilization of the first access point is greater than a predetermined limit that is less than the critical value, that the utilization of the first access point is greater than a predetermined percentage of the utilization of the network, or that another network metric has degraded by more than a predetermined amount;

determining a random delay period proportionate to a routing cost within the network;

waiting for the duration of the random delay period;

after the random delay period, determining that the utilization of the first access point remains greater than the critical value, that the utilization of the first access point remains greater than the predetermined limit, that the utilization of the first access point remains greater than the predetermined percentage of the utilization of the network, or that the another network metric remains degraded by more than the predetermined amount; and

in response, turning on a network connection to connect as an access point to the network.

8. The non-transitory computer-readable medium of claim 7, wherein the another network metric is associated with a hop count between the first access point and a nearest neighbor access point.

9. The non-transitory computer-readable medium of claim 7, wherein the another network metric is associated with a utilization value corresponding to the first access point.

10. The non-transitory computer-readable medium of claim 7, wherein the another network metric is associated with an amount of data being forwarded to a server relative to a data transmission capability associated with the first access point.

11. The non-transitory computer-readable medium of claim 7, wherein the another network metric comprises a routing metric.

12. The non-transitory computer-readable medium of claim 7, wherein the network comprises a general packet radio service (GPRS) network.

13. A network node, comprising:

a processor configured to determine connect as an access point to a network by performing the steps of;

determining that routing connectivity within the network has not been lost or has been lost for less than a predetermined amount of time;

selecting a first access point to query;

querying the first access point with respect to utilization;

determining that the utilization of the first access point is greater than a critical value, that the utilization of the first access point is greater than a predetermined limit that is less than the critical value, that the utilization of the first access point is greater than a predetermined percentage of the utilization of the network, or that another network metric has degraded by more than a predetermined amount;

determining a random delay period proportionate to a routing cost within the network;

waiting for the duration of the random delay period;

after the random delay period, determining that the utilization of the first access point remains greater than the critical value, that the utilization of the first access point remains greater than the predetermined limit, that the utilization of the first access point remains greater than the predetermined percentage of the utilization of the network, or that the another network metric remains degraded by more than the predetermined amount; and

in response, turning on a network connection to connect as an access point to the network.

14. The computing device of claim 13, wherein the network comprises a general packet radio service (GPRS) network.

15. A non-transitory computer-readable medium including instructions that, when executed by a processor included in a first access point, cause the processor to disconnect the first access point from a network, by performing the steps of:

computing a routing cost within the network;

determining that the routing cost is favorable;

computing a hop count associated with the first access point;

determining that the hop count is favorable;

computing a traffic utilization value associated with the first access point;

querying another access point to determine a traffic utilization value associated with the another access point;

determining that the traffic utilization associated with the first access point is favorable based on the traffic utilization value associated with first access point and the traffic utilization value associated with the another access point;

determining a random delay period proportionate to the routing cost;

waiting for the duration of the random delay period;

after the random delay period, determining that the routing cost is still favorable, that the hop count is still favorable, and that the traffic utilization associated with the first access point is still favorable; and

turning off a connection to disconnect the first access point from the network.

16. The non-transitory computer-readable medium of claim 15, wherein computing the routing cost comprises measuring the routing cost from one or more nodes corresponding to the first access point to one or more other access points.

17. The non-transitory computer-readable medium of claim 16, wherein determining that the routing cost is favorable comprises determining that the routing cost from the one or more nodes corresponding to the first access point to the one or more other access points is less than a preset value.

18. The non-transitory computer-readable medium of claim 15, wherein computing the hop count comprises measuring a value based on a hop count from the first access point to a nearest neighbor access point a hop count from the first access pint to a farthest corresponding node.

19. The non-transitory computer-readable medium of claim 18, wherein determining that the hop count is favorable comprises determining that the value is less than a preset value.

20. The non-transitory computer-readable medium of claim 15, wherein computing a traffic utilization value associated with the first access point comprises computing an amount of data being forwarded to a server relative to a data transmission capacity associated with the first access point.

21. The non-transitory computer-readable medium of claim 20, wherein determining that the determining that the traffic utilization associated with the first access point is favorable comprises comparing the traffic utilization value associated with the first access point with the traffic utilization value associated with the another access point according to a weighted function.

22. A computer-implemented method for disconnecting a first access point from a network, the method comprising:

computing a routing cost within the network;

determining that the routing cost is favorable;

computing a hop count associated with the first access point;

determining that the hop count is favorable;

computing a traffic utilization value associated with the first access point;

querying another access point to determine a traffic utilization value associated with the another access point;

determining that the traffic utilization associated with the first access point is favorable based on the traffic utilization value associated with first access point and the traffic utilization value associated with the another access point;

determining a random delay period proportionate to the routing cost;

waiting for the duration of the random delay period;

after the random delay period, determining that the routing cost is still favorable, that the hop count is still favorable, and that the traffic utilization associated with the first access point is still favorable; and

turning off a connection to disconnect the first access point from the network.

23. A network node, comprising:

a processor configured to determine whether to disconnect as first access point from a network by performing the steps of;

computing a routing cost within the network;

determining that the routing cost is favorable;

computing a hop count associated with the first access point;

determining that the hop count is favorable;

computing a traffic utilization value associated with the first access point;

querying another access point to determine a traffic utilization value associated with the another access point;

determining that the traffic utilization associated with the first access point is favorable based on the traffic utilization value associated with first access point and the traffic utilization value associated with the another access point;

determining a random delay period proportionate to the routing cost;

waiting for the duration of the random delay period;

after the random delay period, determining that the routing cost is still favorable, that the hop count is still favorable, and that the traffic utilization associated with the first access point is still favorable; and

turning off a connection to disconnect the first access point from the network.