Mesh backhaul network planning

• US 7,688,762 B2
• Filed: 03/21/2007
• Issued: 03/30/2010
• Est. Priority Date: 03/21/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Douglas, Bretton, Hart, Brian
• Primary Examiner(s): Moe; Aung S
• Assistant Examiner(s): Rose; Kerri M
• Application Number:
  US11/688,982
• Publication Number:
  US 20080232256A1
• Time in Patent Office: 1,105 Days
• Field of Search: 370254-256, 370/310, 370/328, 370/329, 370/389, 370/400, 370/461, 370/462, 370229-232, 370/252, 370/253, 370/401, 370/412, 370/413, 370/415, 370/417, 455/422.1, 455/445, 455/446, 455450-4522
• US Class Current: 370/255
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04Q 3/66 Traffic distributors
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In an example embodiment, a number of contending nodes and colliding nodes for a plurality of links of a network is determined. The capacity of each of the plurality of links is determined. A sum of the traffic demand of each of the plurality of links divided the throughput of each of the plurality of links is used to form a cost function for the network. One, or more, of a group consisting of a plurality of frequency assignments, a plurality of transmit powers, and a plurality of clear channel assessment (CCA) values is searched to obtain a global minimum for the cost function. The frequency assignments, transmit powers, and/or CCA values providing the global minimum for the cost function are selected.

Claims

1. A method comprising:

determining, by a processor, a number of contending nodes and a number of colliding nodes for a plurality of links;

determining, using the processor, a capacity of each of the plurality of links;

summing, using the processor, traffic demand of each of the plurality of links divided by throughput of each of the plurality of links to form a cost function for a network;

searching, using the processor through one of a group consisting of a plurality of frequency assignments, a plurality of transmit powers, and a plurality of clear channel assessment levels to obtain a global minimum for the cost function;

wherein searching through the plurality of clear channel assessment levels further comprises;

calculating contentions and collisions, using the processor, based on transmit power, path loss and clear channel assessment for a plurality of clear channel assessment values between a minimum value and a maximum value; and

selecting, using the processor, a clear channel assessment value that minimizes the cost function;

wherein the access point to access point path losses are known.

2. A method according to claim 1, further comprising determining path loss, the determining path loss is based on one of a group consisting of a direct sequence spread spectrum a half-bandwidth orthogonal frequency division multiplexing mode, a quarter-bandwidth orthogonal frequency division multiplexing mode, and performing simultaneous link testing over pairs of nodes to determine which nodes contend and which nodes collide based on throughput and number of collisions.

3. A method according to claim 1, the searching through the plurality of frequencies comprises performing an initial search on a subset of solution indices based on a step size calculated by Total Number of Solutions divided by Initial Frequency Search Size.

4. A method according to claim 3, wherein the step size is calculated by Total Number of Solutions divided by (Initial Frequency Search Size+1) responsive to the step size being a power of a number of possible frequencies for each access point.

5. A method according to claim 3, performing the initial search further comprises performing for each member of the subset:

determine a solution index that is a product of step size and search index;

calculating a frequency allocation from the solution index;

calculate a fast evaluation metric using a threshold of maximum transmit minus the receive sensitivity; and

storing the frequency allocation and the fast evaluation metric.

6. A method according to claim 3, further comprising performing a final search, the final search, wherein the final frequency search uses a threshold for the fast evaluation metric that was determined in an initial power sweep.

7. A method according to claim 1, further comprising a coarse power search.

8. A method according to claim 7, further comprising a fine power search based on a small set of frequency combinations obtained during a final frequency search.

9. A method according to claim 1, the searching through the plurality of clear channel assessment levels further comprises:

generating traffic on the plurality of links;

increasing the traffic until mesh queues start to overload;

determine a capacity for a current clear channel assessment setting;

repeating the generating traffic, increasing traffic and determining the capacity for at least one other clear channel assessment setting; and

selecting the clear channel assessment setting that yields the highest throughput.

10. A method according to claim 1, further comprising:

switching to a common channel;

sending a beacon at minimum data rate and maximum transmit power;

selecting a minimum setting for receiver sensitivity;

selecting a minimum setting for clear channel assessment; and

logging the media access control address and received signal strength intensity of received beacons.

11. Logic encoded in one or more computer readable media for execution and when executed operable to:

summing throughput demand divided by throughput for a plurality of links with one of a group consisting of a first clear channel assessment value, a first frequency and a first transmit power to determine a first cost function;

summing throughput demand divided by throughput for the plurality of links with one of a group consisting of a second clear channel assessment value, a second frequency and a second transmit power to determine a second cost function;

selecting one of a group consisting of the first clear channel assessment value, the first frequency and the first transmit power, the second clear channel assessment value, the second frequency and the second transmit power based on which of a group consisting of the first cost function and the second cost function has the lowest value and

searching through a plurality of clear channel assessment levels, the logic for searching through a plurality of clear channel assessment levels further comprises logic when executed operable to;

generating traffic on the plurality of links;

increasing the traffic until mesh queues start to overload;

determine a capacity for a current clear channel assessment setting;

repeating the generating traffic, increasing traffic and determining the capacity for at least one other clear channel assessment setting; and

selecting the clear channel assessment setting that yields the highest throughput.

12. The logic according to claim 11 further comprising logic when executed operable to determining path loss, the determining path loss is based on one of a group consisting of a direct sequence spread spectrum mode a group consisting of a half-bandwidth orthogonal frequency division multiplexing mode, a quarter-bandwidth orthogonal frequency division multiplexing mode, and performing simultaneous link testing over pairs of nodes to determine which nodes contend and which nodes collide based on throughput and number of collisions.

13. Logic according to claim 11, further comprising logic when executed operable to search through a plurality of frequencies by performing an initial search on a subset of solution indices based on a step size calculated by Total Number of Solutions divided by Initial Frequency Search Size.

14. Logic according to claim 13, further comprising logic when executed operable to:

determine a solution index that is a product of step size and search index;

calculate a frequency allocation from the solution index;

calculate a fast evaluation metric using a threshold of maximum power minus receiver sensitivity; and

store the frequency allocation and the fast evaluation metric.

15. Logic according to claim 11, further comprising logic when executed operable to perform a coarse power search, the coarse power search comprises one of a group consisting of determining a mean of a maximum and a minimum transmit power and subtracting receive sensitivity, determining mean pathloss of the plurality of links, determining median pathloss of the plurality of links, and calculating a combined metric for a plurality of power levels and determining a mean of transmit powers and frequencies that provide the ten best combined metrics.

16. Logic according to claim 11, further comprising:

logic when executed operable to search through a plurality of clear channel assessment levels, the logic to search the a plurality of clear channel assessment levels further comprising logic when executed operable to;

calculating contentions and collisions based on transmit power, path loss and clear channel assessment for a plurality of clear channel assessment values between a minimum value and a maximum value; and

selecting a clear channel assessment value that minimizes the cost function;

wherein the access point to access point path losses are known.

17. An apparatus, comprising:

means for determining a number of contending nodes and a number of colliding nodes for a plurality of links;

means for determining a capacity for each of the plurality of links;

means for summing traffic demand of each of the plurality of links divided by throughput of each of the plurality of links to form a cost function for a network; and

means for searching through one of a group consisting of a plurality of frequency assignments, a plurality of transmit powers and a plurality of clear channel assessment values to obtain a global minimum for the, cost function;

wherein the means for searching searches through a plurality of frequency assignments, a plurality of transmit powers and a plurality of clear channel assessment values to obtain the global minimum for the cost function.

18. A method comprising:

determining, using a processor, a number of contending nodes and a number of colliding nodes for a plurality of links;

determining, using the processor, a capacity of each of the plurality of links;

summing, using the processor, traffic demand of each of the plurality of links divided by throughput of each of the plurality of links to form a cost function for a network; and

searching, using the processor, through one of a group consisting of a plurality of frequency assignments, a plurality of transmit powers, and a plurality of clear channel assessment levels to obtain a global minimum for the cost function;

wherein searching through the plurality of clear channel assessment levels further comprises;

generating traffic on the plurality of links;

increasing the traffic until mesh queues start to overload;

determine a capacity for a current clear channel assessment setting;

repeating the generating traffic, increasing traffic and determining the capacity for at least one other clear channel assessment setting; and

selecting, by the processor, the clear channel assessment setting that yields the highest throughput.

19. A method comprising:

determining, using a processor, a number of contending nodes and a number of colliding nodes for a plurality of links;

determining, using the processor, a capacity of each of the plurality of links;

summing, using the processor, traffic demand of each of the plurality of links divided by throughput of each of the plurality of links to form a cost function for a network;

searching, using the processor, through one of a group consisting of a plurality of frequency assignments, a plurality of transmit powers, and a plurality of clear channel assessment levels to obtain a global minimum for the cost function;

switching to a common channel;

sending a beacon at minimum data rate and maximum transmit power;

selecting a minimum setting for receiver sensitivity;

selecting a minimum setting for clear channel assessment; and

logging the media access control address and received signal strength intensity of received beacons.