Method for optimizing cell-site placement

• US 6,094,580 A
• Filed: 10/16/1997
• Issued: 07/25/2000
• Est. Priority Date: 10/16/1997
• Status: Expired due to Fees

• Current Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Original Assignee: Nortel Networks Corporation
• Inventors: Tseng, Stone, Sendonaris, Andrew, Yu, Chang, Lin, Sheng-Chou, Jain, Nikhil, Subramanian, Sairam, Landolsi, Mohamed, Veeravalli, Venugopal, Madhavapeddy, Seshu
• Primary Examiner(s): Urban, Edward F.
• Assistant Examiner(s): Nguyen, Thuan T.
• Application Number:
  US08/951,685
• Time in Patent Office: 1,013 Days
• Field of Search: 455/446, 455/448, 455/449, 455/453
• US Class Current: 455/446
• CPC Class Codes: H04W 16/18 Network planning tools

Abstract

Provided herein is a computer-implemented method for generating an optimized cellular-network cell-site plan for an area. A plurality of cellular-traffic demand nodes distributed across the area is provided. Each cellular-traffic demand node of the plurality of cellular-traffic demand nodes has an associated weighting characteristics set. The plurality of nodes are consolidated into a plurality of centroids. Each centroid represents a number of nodes that come within a traffic threshold. A potential cell site is positioned on each of the centroids. Each potential cell site has an associated base-transmitter-station parameter characteristics set. The demand node coverage of each potential cell site is determined with respect to a signal strength of the potential cell site. From the plurality of potential cell sites a minimized cell-site subset is selected while maintaining sufficient cellular service coverage of the plurality of demand nodes.

Claims

1. A computer-implemented method for generating an optimized cellular-network cell-site plan for an area, the method comprising the steps of:

providing a plurality of cellular-traffic demand nodes distributed across the area, each cellular-traffic demand node of the plurality of cellular-traffic demand nodes having an associated weighting characteristics set;

consolidating the plurality of nodes into a plurality of centroids such that each centroid represents a number of nodes that come within a traffic threshold;

positioning a potential cell site on each of the centroids, the potential cell site having an associated base-transmitter-station parameter characteristics set;

determining the demand node coverage of each potential cell site with respect to a signal strength of the potential cell site; and

selecting from the plurality of potential cell sites a minimized cell-site subset while maintaining sufficient cellular service coverage of the plurality of demand nodes.

2. The method for generating an optimized cellular-network cell-site plan of claim 1 wherein the weighting characteristics set has a demand node location element, an Erlang value element, and a terrain information element.

3. The method for generating an optimized cellular-network cell-site plan of claim 2 wherein the Erlang value element of each demand node is within a threshold Erlang limit.

4. The method for generating an optimized cellular-network cell-site plan of claim 1 wherein the step of providing demand nodes is performed by a uniform assumption method.

5. The method for generating an optimized cellular-network cell-site plan of claim 1 wherein the step of providing demand nodes is performed by a regression analysis method.

6. The method for generating an optimized cellular-network cell-site plan of claim 1 wherein the step of providing demand nodes is performed by a software generation method.

7. The method for generating an optimized cellular-network cell-site plan of claim 1 wherein the step of determining the coverage of each potential cell site is conducted using a link budget analysis.

8. The method for generating an optimized cellular-network cell-site plan of claim 1 wherein the step of determining the coverage of each potential cell site is a binary search algorithm deploying a coverage-versus-capacity algorithm such that potential cell-site coverage decreases with respect to demand node loadings are considered in the coverage determination.

9. The method for generating an optimized cellular-network cell-site plan of claim 1 wherein the step of selecting from the plurality of potential cell sites a minimized cell-site subset further comprises the steps of:

applying to the plurality of potential cell sites a linear program relaxation solution where the Linear Program objective function is;

##EQU31## where c_J is the cost of set J, x_J is "1" if set J is selected in the solution, otherwise x_J is "0" if not selected,

p_i is the penalty cost for not covering demand node i,

e_m is an m-vector of all 1'"'"'s,

a_ij is matrix element defined to be 1, 1/2, or 1/3 depending on whether the demand node i is covered by set J directly, through 2-way soft hand-off, or three-way soft hand-off, accordingly. a_ij is "0" if the demand node i is not covered by the set J,

n is the number of demand nodes, and

m is the number of sets in the set covering problem;

the linear program objective function having the constraints;

##EQU32## where I_k is the collection of sets generated for the potential cell site k; and

applying a greedy algorithm with respect to a demand node weighting ratio and a stopping criteria.

10. The method for generating an optimized cellular-network cell-site plan of claim 9 wherein the step of selecting from the plurality of potential cell sites a minimized cell-site subset wherein the weighting ratio is:

##EQU33## where C_S is the cost of set S of the potential cell-sites, and ##EQU34## where;

t_i is the amount of cellular traffic (in Erlangs) on demand node i; and

a_i is 1, 1/2, or 1/3, depending on whether demand node i is covered by S directly, by two-way soft hand-off, or by three-way soft hand-off, respectively.

11. The method for generating an optimized cellular-network cell-site plan of claim 9 wherein the step of selecting from the plurality of potential cell sites a minimized cell-site subset wherein the weighting ratio is:

##EQU35## where C_S is the fiscal cost of set S of the potential cell-sites, and ##EQU36## where;

v_i is the square area (in square-kilometers) represented by the demand node i; and

a_i is 1, 1/2, or 1/3, depending on whether demand node i is covered by S directly, by two-way soft hand-off, or by three-way soft hand-off, respectively.

12. A computer-implemented method for generating an optimized cellular-network plan from a pre-existing cellular network having a plurality of pre-existing cell sites, the met hod comprising the steps of:

providing a plurality of cellular-traffic demand nodes distributed across the area, each cellular-traffic demand node of the plurality of cellular-traffic demand nodes having an associated weighting characteristics set, comprising information relating to either or both infrastructure costs and financial return;

positioning a potential cell site on each of the pre-existing cell sites, each of the potential cell sites having an associated base-transmitter-station parameter characteristics set;

determining the demand node coverage of each potential cell site with respect to a signal strength characteristic of the potential cell site; and

selecting from the plurality of potential cell sites a minimized cell-site subset with relation to at least the demand node coverage while maintaining sufficient cellular service coverage of the plurality of demand nodes.

13. The method for generating an optimized cellular-network cell-site plan of claim 12 wherein the weighting characteristics set has a demand node location element, an Erlang value element, and a terrain information element.

14. The method for generating an optimized cellular-network cell-site plan of claim 13 wherein the Erlang value element of each demand node is within a threshold Erlang limit.

15. The method for generating an optimized cellular-network cell-site plan of claim 12 wherein the step of providing demand nodes is performed by a uniform assumption method.

16. The method for generating an optimized cellular-network cell-site plan of claim 12 wherein the step of providing demand nodes is performed by a regression analysis method.

17. The method for generating an optimized cellular-network cell-site plan of claim 12 wherein the step of providing demand nodes is performed by a software generation method.

18. The method for generating an optimized cellular-network cell-site plan of claim 12 wherein the step of determining the coverage of each potential cell site is conducted using a link budget analysis.

19. The method for generating an optimized cellular-network cell-site plan of claim 12 wherein the step of determining the coverage of each potential cell site is a binary search algorithm deploying a coverage-versus-capacity algorithm such that potential cell-site coverage decreases with respect to demand node loadings are considered in the coverage determination.

20. The method for generating an optimized cellular-network cell-site plan of claim 12 wherein the step of selecting from the plurality of potential cell sites a minimized cell-site subset further comprises the steps of:

applying to the plurality of potential cell sites a linear program relaxation solution where the Linear Program objective function is;

##EQU37## where c_J is the cost of set J, x_J is "1" if set J is selected in the solution, otherwise x_J is "0" if not selected,

p_i is the penalty cost for not covering demand node i,

e_m is an m-vector of all 1'"'"'s,

a_ij is matrix element defined to be 1, 1/2, or 1/3 depending on whether the demand node i is covered by set J directly, through 2-way soft hand-off, or three-way soft hand-off, accordingly. a_ij is "0" if the demand node i is not covered by the set J,

n is the number of demand nodes, and

m is the number of sets in the set covering problem;

the linear program objective function having the constraints;

##EQU38## where I_k is the collection of sets generated for the potential cell site k; and

applying a greedy algorithm with respect to a demand node weighting ratio and a stopping criteria.

21. The method for generating an optimized cellular-network cell-site plan of claim 20 wherein the step of selecting from the plurality of potential cell sites a minimized cell-site subset wherein the weighting ratio is:

##EQU39## where C_S is the cost of set S of the potential cell-sites, and ##EQU40## where;

t_i is the amount of cellular traffic (in Erlangs) on demand node i; and

a_i is 1, 1/2, or 1/3, depending on whether demand node i is covered by S directly, by two-way soft hand-off, or by three-way soft hand-off, respectively.

22. The method for generating an optimized cellular-network cell-site plan of claim 20 wherein the step of selecting from the plurality of potential cell sites a minimized cell-site subset wherein the weighting ratio is:

##EQU41## where C_S is the cost of set S of the potential cell-sites, and ##EQU42## where;

v_i is the square area (in kilometers) represented by the demand node i; and

a_i is 1, 1/2, or 1/3, depending on whether demand node i is covered by S directly, by two-way soft hand-off, or by three-way soft hand-off, respectively.

23. A computer-implemented method for accounting for interference in a non-deployed cellular network having a plurality of potential cell sites, the method comprising the steps of:

determining the interference from a first mobile user distant from an edge of a current cell according to the algorithm;

##EQU43## where;

##EQU44## determining the interference from the first mobile user adjacent to the edge of the current cell according to the algorithm;

##EQU45## where;

##EQU46## and determining the interference from at least the first and a second a mobile belonging to the current cell according to the algorithm;

##EQU47## where;

c is the average number of users that belong to the current cell, I_ext is the interference caused from mobiles outside the current cell,

N_O is the white noise spectral height,

W is the bandwidth of the signal,

R_b is the data rate (in bps),

ρ

_v is the voice activity factor, and ##EQU48## where, m.sub.ε

and (σ

.sub.ε

)² are the mean and variance of the required E_b /I_O.

24. A computer-implemented method for optimizing coverage of a plurality of demand nodes by a cellular network having a set of potential cell sites, the method comprising the steps of

applying to the set of potential cell sites a linear program relaxation algorithm where the Linear Program objective function is:

##EQU49## where c_J is the cost of set J, x_J is "1" if set J is selected in the solution, otherwise x_J is "0" if not selected,

p_i is the penalty cost for not covering demand node i,

e_m is an m-vector of all 1'"'"'s,

a_ij is matrix element defined to be 1, 1/2, or 1/3 depending on whether the demand node i is covered by set J directly, through 2-way soft hand-off, or three-way soft hand-off, accordingly. a_ij is "0" if the demand node i is not covered by the set J,

n is the number of demand nodes, and

m is the number of sets in the set covering problem;

the linear program objective function having the constraints;

##EQU50## where I_k is the collection of sets generated for the potential cell site k, and

applying a greedy algorithm with respect to a demand node weighting ratio and a stopping criteria.

25. The method for optimizing coverage of a plurality of demand nodes of a cellular network having a set of potential cell sites of claim 24 wherein the step of selecting from the plurality of potential cell sites a minimized cell-site subset wherein the weighting ratio is:

##EQU51## where;

C_S is the fiscal cost of the plurality of potential cell-sites set S, and ##EQU52## where;

t_i is the amount of cellular traffic (in Erlangs) on demand node i; and

a_i is 1, 1/2, or 1/3, depending on whether demand node i is covered by S directly, by two-way soft hand-off, or by three-way soft hand-off, respectively.

26. The method for optimizing coverage of a plurality of demand nodes of a cellular network having a set of potential cell sites of claim 24 wherein the step of selecting from the plurality of potential cell sites a minimized cell-site subset wherein the weighting ratio is:

##EQU53## where C_S is the fiscal cost of the plurality of potential cell-sites set S, and ##EQU54## where;

v_i is the square area (in square-kilometers) represented by the demand node i; and

a_i is 1, 1/2, or 1/3, depending on whether demand node i is covered by S directly, by two-way soft hand-off, or by three-way soft hand-off, respectively.