Patent US5987328A successfully refreshed from Google Patents.
US5987328A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and device for placement of transmitters in wireless networks
Assignee: University of Maryland, College Park
•
Filing: 1997-04-24
•
Granted: 1999-11-16
•
Expires: 2017-04-24
Abstract
Abstract From layout and attenuation data of an area and an initial guess, the placement and power levels of base stations and the resulting attenuation and base station ranges are calculated based on any chosen propagation model. A cost function is calculated which indicates the merit of the initial guess placement. The cost function is a function of the transmitter locations and power levels and can be calculated as a linear combination of the uncovered and interference areas. Other cost functions can also be considered. The cost function is optimized by one of several optimization methods to give the optimal base station placement. The optimization can be continuous or discrete. Continuous optimization methods include the modified steepest descent method and the downhill simplex method, while discrete optimization methods include the Hopfield neural network method. The optimization can be performed several times for different initial guess placements to achieve a global, rather than simply local, optimization. The entire optimization process is packaged in the form of an interactive software tool that permits the designer to steer and adjust the solution according to any criteria that the designer may choose.
Inventors
- 👤 Anthony Ephremides
- 👤 Dimitrios Stamatelos
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 15:24
CPC Classifications
H; H04; H04W; H04W16/00; H04W16/18; G; G06; G06F; G06F30/00; G06F2111/00; G06F2111/06
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
354 words
A method of placing a number N of transmitters in a service area which has unblocked points where the transmitters may be located and blocked points in which the transmitters may not be located, each of the transmitters having a power p i , i=1 to N, the method comprising: (a) providing a processor which comprises an input means for receiving an input from a user and an output means for displaying an output to the user; (b) inputting to the processor, by use of the input means, data comprising N, p i for i=1 to N, a blocked point location data set identifying locations of the blocked points, an attenuation data set identifying attenuation characteristics of both the blocked points and the unblocked points, and initial guess values for (x i , y i , p i ), i=1 to N, where (x i , y i ) are x and y coordinates for the ith transmitter and p i is the power of the ith transmitter; (c) calculating in the processor, in accordance with the data input in step (b), attenuation characteristics for each of the transmitters; (d) calculating in the processor, in accordance with the attenuation characteristics calculated in step (c), (i) a size U of an uncovered area in which signals from the transmitters could not reach if the transmitters were positioned at the initial guess values, (ii) a size I of an interference area in which interference among the signals from the transmitters would prevent service if the transmitters were positioned at the initial guess values, and (iii) a cost function F which is a function of (x i , y i , p i ), i=1, . . . N given by a linear combination of U and I; (e) by use of the processor, optimizing the cost function to produce an optimized set of transmitter locations and powers; (f) outputting to the user, by use of the output means, locations and powers of the transmitters which achieve the optimized cost function produced in step (e) and (g) placing the transmitters in the locations output in step (f).
Claim 2
Independent Claim
354 words
A method of placing a number N of transmitters in a service area which has unblocked points where the transmitters may be located and blocked points in which the transmitters may not be located, each of the transmitters having a power p i , i=1 to N, the method comprising: (a) providing a processor which comprises an input means for receiving an input from a user and an output means for displaying an output to the user; (b) inputting to the processor, by use of the input means, data comprising N, p i for i=1 to N, a blocked point location data set identifying locations of the blocked points, an attenuation data set identifying attenuation characteristics of both the blocked points and the unblocked points, and initial guess values for (x i , y i , p i ), i=1 to N, where (x i , y i ) are x and y coordinates for the ith transmitter and p i is the power of the ith transmitter; (c) calculating in the processor, in accordance with the data input in step (b), attenuation characteristics for each of the transmitters; (d) calculating in the processor, in accordance with the attenuation characteristics calculated in step (c), (i) a size U of an uncovered area in which signals from the transmitters could not reach if the transmitters were positioned at the initial guess values, (ii) a size I of an interference area in which interference among the signals from the transmitters would prevent service if the transmitters were positioned at the initial guess values, and (iii) a cost function F which is a function of (x i , y i , p i ), i=1, . . . N given by a linear combination of U and I; (e) by use of the processor, optimizing the cost function to produce an optimized set of transmitter locations and powers; (f) outputting to the user, by use of the output means, locations and powers of the transmitters which achieve the optimized cost function produced in step (e) and (g) placing the transmitters in the locations output in step (f).
Claim 3
Dependent Claim
28 words
A method as in claim 1, wherein, during step (e), x i , y i and p i are permitted to vary among a plurality of discrete values.
Claim 4
Dependent Claim
20 words
A method as in claim 2, wherein step (a) comprises configuring the processor to function as an artificial neural network.
Claim 5
Dependent Claim
20 words
A method as in claim 3, wherein step (e) comprises optimizing the cost function by a Hopfield neural network technique.
Claim 6
Dependent Claim
82 words
A method as in claim 4, wherein: x i is permitted to vary discretely among values 1, 2, 3, . . . X max ; y i is permitted to vary discretely among values 1, 2, 3, . . . Y max ; a number of the blocked points in the service area is |OB|; a number of possible values of p i is |P|; and the artificial neural network has a number of neurons equal to n=(X max Y max -|OB|)|P|.
Claim 7
Dependent Claim
20 words
A method as in claim 1, wherein, during step (e), x i and y i are permitted to vary continuously.
Claim 8
Dependent Claim
16 words
A method as in claim 6, wherein step (e) is performed by a steepest descent method.
Claim 9
Dependent Claim
15 words
A method as in claim 6, wherein step (e) is performed by a simplex method.
Claim 10
Dependent Claim
10 words
A method as in claim 1 wherein F=αU+(1-α)I, where αε[0,1].
Claim 11
Dependent Claim
11 words
A method as in claim 9, wherein the transmitters are omnidirectional.
Claim 12
Dependent Claim
46 words
A method as in claim 9, wherein: the transmitters are adaptive; the interference area is made up of a plurality of areas having sizes I i , i=1 to N, each of the plurality of areas having a probability of interference P i ; and ##EQU3##
Claim 13
Dependent Claim
101 words
A method as in claim 1, wherein: the processor further comprises storage means for storing blocked point data sets and attenuation data sets for a plurality of area layouts; and step (b) comprises: (i) prompting the user, by use of the output means, to make a selection of one of the plurality of area layouts; (ii) receiving from the user, by use of the input means, the selection made by the user; and (ii) loading, from the storage means, one of the blocked point data sets and one of the attenuation data sets corresponding to the selection made by the user.
Claim 14
Dependent Claim
72 words
A method as in claim 1, wherein step (e) comprises: (i) prompting the user, by use of the output means, to make a selection of one of a plurality of optimization methods; (ii) receiving from the user, by use of the input means, the selection made by the user; and (iii) optimizing the cost function by implementing in the processor the one of the plurality of optimization methods selected by the user.
Claim 15
Dependent Claim
100 words
A method as in claim 1, wherein step (b) comprises: (i) prompting the user, by use of the output means, to make a selection of whether the initial guess values are to be randomly generated or input by the user; (ii) receiving the selection from the user by use of the input means; (iii) if the user selects a random generation, randomly generating the initial guess values in the processor; and (iv) if the user selects input of the initial guess values by the user, receiving an input of the initial guess values from the user through the input means.
Claim 16
Dependent Claim
70 words
A method as in claim 1, wherein: step (b) comprises inputting multiple sets of the initial guess values; steps (e) and (f) are performed for each of the multiple sets of initial guess values to yield a plurality of optimizations; and step (g) comprises: (i) selecting one of the plurality of optimizations; and (ii) placing the transmitters in accordance with the one of the plurality of optimizations which is selected.
Claim 17
Dependent Claim
18 words
A method as in claim 1, wherein the output means comprises means for implementing a graphical user interface.
Claim 18
Dependent Claim
58 words
A method as in claim 16, further comprising (h) displaying to the user, with the output means, a graphical representation of at least one of (i) the attenuation characteristics calculated in step (c) and (ii) a further set of attenuation characteristics calculated in accordance with the locations and powers of the transmitters which are output in step (f).
Claim 19
Dependent Claim
50 words
A method as in claim 17, wherein, in step (h), said at least one of the attenuation characteristics and the further set of attenuation characteristics comprises a signal strength at each of the unblocked points, and the graphical representation indicates the signal strength at said each of the unblocked points.
Claim 20
Dependent Claim
49 words
A method as in claim 18, wherein: the means for implementing a graphical user interface comprises means for displaying a plurality of types of shading; and step (h) comprises indicating the signal strength at said each of the unblocked points by one of the plurality of types of shading.
Claim 21
Independent Claim
291 words
A device for determining locations of a number N of transmitters in a service area which has unblocked points where the transmitters may be located and blocked points in which the transmitters may not be located, each of the transmitters having a power p i , i=1 to N, the device comprising: input means for receiving an input of data comprising N, p i for i=1 to N, a blocked point location data set identifying locations of the blocked points, an attenuation data set identifying attenuation characteristics of both the blocked points and the unblocked points, and initial guess values for (x i , y i ), i=1 to N, where (x i , y i ) are x and y coordinates for an ith one of the transmitters; means for calculating, in accordance with the input of data received by the input means, attenuation characteristics for each of the transmitters; means for calculating, in accordance with the attenuation characteristics, (i) a size U of an uncovered area in which signals from the transmitters could not reach if the transmitters were positioned at the initial guess values, (ii) a size I of an interference area in which interference among the signals from the transmitters would prevent service if the transmitters were positioned at the initial guess values, and (iii) a cost function F which is a function of (x i , y i p i ) and given by a linear combination of U and I; optimizing means for optimizing the cost function to produce an optimal set of transmitter locations and powers; and output means for outputting to the user locations and powers of the transmitters which achieve the optimal value of the cost function produced by the optimizing means.
Claim 22
Independent Claim
291 words
A device for determining locations of a number N of transmitters in a service area which has unblocked points where the transmitters may be located and blocked points in which the transmitters may not be located, each of the transmitters having a power p i , i=1 to N, the device comprising: input means for receiving an input of data comprising N, p i for i=1 to N, a blocked point location data set identifying locations of the blocked points, an attenuation data set identifying attenuation characteristics of both the blocked points and the unblocked points, and initial guess values for (x i , y i ), i=1 to N, where (x i , y i ) are x and y coordinates for an ith one of the transmitters; means for calculating, in accordance with the input of data received by the input means, attenuation characteristics for each of the transmitters; means for calculating, in accordance with the attenuation characteristics, (i) a size U of an uncovered area in which signals from the transmitters could not reach if the transmitters were positioned at the initial guess values, (ii) a size I of an interference area in which interference among the signals from the transmitters would prevent service if the transmitters were positioned at the initial guess values, and (iii) a cost function F which is a function of (x i , y i p i ) and given by a linear combination of U and I; optimizing means for optimizing the cost function to produce an optimal set of transmitter locations and powers; and output means for outputting to the user locations and powers of the transmitters which achieve the optimal value of the cost function produced by the optimizing means.
Claim 23
Independent Claim
373 words
A method of placing a number N of transmitters in a service area which has unblocked points where the transmitters may be located and blocked points in which the transmitters may not be located, each of the transmitters having a power p i , i=1 to N, the method comprising: (a) providing a processor which comprises an input means for receiving an input from a user and an output means for displaying an output to the user; (b) inputting to the processor, by use of the input means, data comprising N, p i for i=1 to N, a blocked point location data set identifying locations of the blocked points, an attenuation data set identifying attenuation characteristics of both the blocked points and the unblocked points, and initial guess values for (x i , y i , p i ), i=1 to N, where (x i , y i ) are x and y coordinates for the ith transmitter and p i is the power of the ith transmitter; (c) calculating in the processor, in accordance with the data input in step (b), attenuation characteristics for each of the transmitters; (d) calculating in the processor, in accordance with the attenuation characteristics calculated in step (c), (i) a size U of an uncovered area in which signals from the transmitters could not reach if the transmitters were positioned at the initial guess values, (ii) a size I of an interference area in which interference among the signals from the transmitters would prevent service if the transmitters were positioned a the initial guess values, and (iii) a cost function F which is a function of (x i , y i , p i ), i=1, . . . N given by a linear combination of U and I; (e) by use of the processor, optimizing the cost function to produce an optimized set of transmitter locations and powers, wherein x i , y i , p i are permitted to vary among a plurality of discreet values; (f) outputting to the user, by use of the output means, locations and powers of the transmitters which achieve the optimized cost function produced in step (e); and (g) placing the transmitters in the locations output in step (f).
Claim 24
Independent Claim
373 words
A method of placing a number N of transmitters in a service area which has unblocked points where the transmitters may be located and blocked points in which the transmitters may not be located, each of the transmitters having a power p i , i=1 to N, the method comprising: (a) providing a processor which comprises an input means for receiving an input from a user and an output means for displaying an output to the user; (b) inputting to the processor, by use of the input means, data comprising N, p i for i=1 to N, a blocked point location data set identifying locations of the blocked points, an attenuation data set identifying attenuation characteristics of both the blocked points and the unblocked points, and initial guess values for (x i , y i , p i ), i=1 to N, where (x i , y i ) are x and y coordinates for the ith transmitter and p i is the power of the ith transmitter; (c) calculating in the processor, in accordance with the data input in step (b), attenuation characteristics for each of the transmitters; (d) calculating in the processor, in accordance with the attenuation characteristics calculated in step (c), (i) a size U of an uncovered area in which signals from the transmitters could not reach if the transmitters were positioned at the initial guess values, (ii) a size I of an interference area in which interference among the signals from the transmitters would prevent service if the transmitters were positioned a the initial guess values, and (iii) a cost function F which is a function of (x i , y i , p i ), i=1, . . . N given by a linear combination of U and I; (e) by use of the processor, optimizing the cost function to produce an optimized set of transmitter locations and powers, wherein x i , y i , p i are permitted to vary among a plurality of discreet values; (f) outputting to the user, by use of the output means, locations and powers of the transmitters which achieve the optimized cost function produced in step (e); and (g) placing the transmitters in the locations output in step (f).
References Cited (Backward Citations)
US4257123A
Cited
US5179722A
Cited
US5058200A
Cited
US5448766A
Cited
US5754739A
Cited
US5732358A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-15 | 2003-05-17 | 2003-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-15 | 2007-05-17 | 2007-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-15 | 2011-05-17 | 2011-11-16 | $7700.00 | Window Closed / Lapsed |