METHOD FOR POSITIONING MOBILE DEVICE IN WIRELESS WIDE AREA NETWORK

• US 20130329581A1
• Filed: 10/12/2012
• Published: 12/12/2013
• Est. Priority Date: 06/07/2012
• Status: Active Grant

• Current Assignee: Novatek Microelectronics Corporation (Novatek Microelectronics Corp Limited)
• Original Assignee: Novatek Microelectronics Corporation (Novatek Microelectronics Corp Limited)
• Inventors: Chen, Chien-Sheng, Lin, Yung-Chuan
• Granted Patent: US 8,942,172 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location
• CPC Class Codes: G06N 3/086 using evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A method for positioning a mobile device in a wireless wide area network (WWAN) is provided. The method includes determining three measurement circles according to coordinates of three base stations and respectively calculating radiuses of the three measurement circles and distances between the three base stations. The method uses genetic algorithm to derive the best solution of a plurality of variables of an object function and estimates the position of the mobile device according to the best solution. Accordingly, non-line-of-sight (NLOS) errors are reduced, and more accurate positioning can be provided.

Claims

1. A method for positioning a mobile device in a wireless wide area network comprising:

determining three measurement circles according to coordinates of three base stations, and respectively calculating radiuses of the three measurement circles and distances between the three base stations;

determining an object function, wherein the object function is expressed with a first variable, a second variable, a third variable, and a fourth variable;

respectively determining a first variable coding range, a second variable coding range and a third variable coding range according to the radiuses of the three measurement circles and the distances between the three base stations;

determining a fourth variable coding range;

coding the first variable coding range, the second variable coding range, the third variable coding range, and the fourth variable coding range;

selecting a plurality of combinations of the first variable, the second variable, the third variable, and the fourth variable respectively within the first variable coding range, the second variable coding range, the third variable coding range, and the fourth variable coding range as a parent population of the object function;

performing iterations of a genetic algorithm by using the parent population as a basis to derive a best solution of the first variable, the second variable, the third variable, and the fourth variable for the object function; and

converting the best solution of the first variable, the second variable and the third variable into a position of the mobile device according to the coordinates of three base stations to position the mobile device in the wireless wide area network.

2. The method for positioning the mobile device in the wireless wide area network as recited in claim 1, wherein steps of determining the three measurement circles according to the coordinates of three base stations comprise:

estimating distances from the mobile device to the three base stations by measuring signals between the mobile device and the three base stations; and

determining the three measurement circles by respectively using the coordinates of three base stations as centers of the three measurement circles and the estimated distances as the radiuses of the three measurement circles.

3. The method for positioning the mobile device in the wireless wide area network as recited in claim 1, wherein steps of determining the object function comprise:

determining a function f(v) according to the radiuses of the three measurement circles, coordinates of three interception points of the three measurement circles and the coordinates of three base stations; and

determining a constraint g(v) according to the radiuses of the three measurement circles and the distances between the three base stations;

wherein the first variable, the second variable, the third variable, and the fourth variable are respectively expressed with α

, β

, γ

, and λ

, while the object function is F(α

,β

,γ

,λ

)=f (v)+λ

×

g(v), and v=[α

β

γ

]^T.

4. The method for positioning the mobile device in the wireless wide area network as recited in claim 1, wherein the radiuses of the three measurement circles are r₁, r₂ and r₃ respectively, the distances between the three base stations are L₁₂, L₁₃ and L₂₃ respectively, the first variable coding range is α

_min to 1, the second variable coding range is β

_min to 1, and the third variable coding range is γ

_min to 1;

wherein [α

_min β

_min γ

_min]^T=[α

_1,min² α

_2,min² α

_3,min²]^T, α

_1,min is the larger of

5. The method for positioning the mobile device in the wireless wide area network as recited in claim 4, wherein steps of coding the first variable coding range, the second variable coding range, the third variable coding range, and the fourth variable coding range comprise:

expressing (2^M−

1) segments between α

_min to 1 with M bits;

expressing (2^N−

1) segments between β

_min to 1 with N bits;

expressing (2^O−

1) segments between γ

_min to 1 with O bits; and

expressing (2^P−

1) segments between λ

_min to λ

_max with P bits,

wherein the fourth variable coding range is λ

_min to λ

_max, and M, N, O, and P are positive integers.

6. The method for positioning the mobile device in the wireless wide area network as recited in claim 5, wherein M is equal to N and O, and P is greater than M, N and O.

7. The method for positioning the mobile device in the wireless wide area network as recited in claim 1, wherein steps of performing the iterations of the genetic algorithm by using the parent population as the basis comprise:

(a) performing one or more of a chromosome reproduction processing, a crossover processing and a mutation processing on the combinations in the parent population to generate a plurality of combinations of the first variable, the second variable, the third variable, and the fourth variable in a sub-population; and

(b) using the sub-population as a next generation of the parent population and repeating step (a) until a predetermined number of the iterations is achieved.

8. The method for positioning the mobile device in the wireless wide area network as recited in claim 7, wherein the reproduction processing comprises:

respectively substituting the combinations in the parent population into the object function to derive an operand value of each combination; and

replicating the combinations from the parent population as a portion of the combinations in the sub-population according to probabilities corresponding to the operand values of the combinations.

9. The method for positioning the mobile device in the wireless wide area network as recited in claim 8, wherein the combinations with smaller operand values have larger probabilities of being selected from the parent population to perform replication.

10. The method for positioning the mobile device in the wireless wide area network as recited in claim 7, wherein the crossover processing comprises:

randomly selecting two combinations from the combinations in the parent population, and interchanging the local codings within the two selected combinations to generate two combinations in the sub-population.

11. The method for positioning the mobile device in the wireless wide area network as recited in claim 7, wherein the mutation processing comprises:

randomly selecting at least one combination from the combinations with the parent population, and phase reversing at least one bit within the at least one combination to generate a combination in the sub-population.

12. A method for positioning a mobile device in a wireless wide area network (WWAN) comprising:

determining a plurality of measurement circles according to coordinates of a plurality of base stations, and respectively calculating radiuses of the plurality of measurement circles and distances between the plurality of base stations;

determining an object function, wherein the object function is expressed by a plurality of variables;

respectively determining a plurality of variable coding ranges according to the radius of the plurality of measurement circles and the distances between the plurality of base stations;

determining another variable coding range;

coding the plurality of variable coding ranges;

selecting a plurality of combinations of the plurality of variables respectively within the plurality of variable coding ranges as a parent population of the object function;

performing iterations of a genetic algorithm using the parent population as a basis to derive a best solution of the plurality of variables for the object function; and

converting the best solution of at least a part of the variables within the plurality of variables into a position of the mobile device according to the coordinates of the plurality of base stations to position the mobile device in the wireless wide area network.

13. The method for positioning the mobile device in the wireless wide area network as recited in claim 12, wherein steps of determining the plurality of measurement circles according to the coordinates of the plurality of base stations comprise:

estimating distances from the mobile device to the plurality of base stations by measuring signals between the mobile device and the plurality of base stations; and

determining the plurality of measurement circles by respectively using the coordinates of plurality of base stations as centers of the three measurement circles and the estimated distances as the radiuses of the three measurement circles.

14. The method for positioning the mobile device in the wireless wide area network as recited in claim 12, wherein steps of determining the object function comprise:

determining a function f(v) according to the radiuses of the plurality of measurement circles, and the coordinates of plurality of base stations and coordinates of a plurality of interception points of the plurality of measurement circles;

determining a constraint g(v) according to the radiuses of the plurality of measurement circles and the distances between the plurality of base stations; and

determining the object function according to the function f(v) and the constraint g(v).

15. The method for positioning the mobile device in the wireless wide area network as recited in claim 12, wherein steps of performing the iterations of the genetic algorithm using the parent population as the basis comprise:

(a) performing one or more of a chromosome reproduction processing, a crossover processing and a mutation processing on the combinations in the parent population to generate a plurality of combinations of the plurality of variables in a sub-population; and

(b) using the sub-population as a next generation of the parent population and repeating step (a) until a predetermined number of the iterations is achieved.

16. The method for positioning a mobile device in a wireless wide area network as recited in claim 15, wherein the reproduction processing comprises:

respectively substituting the combinations in the parent population into the object function to derive an operand value of each combination; and

replicating the combinations from the parent population as a portion of the combinations in the sub-population according to probabilities corresponding to the operand values of the combinations.

17. The method for positioning the mobile device in the wireless wide area network as recited in claim 16, wherein the combinations with smaller operand values have larger probabilities of being selected from the parent population to perform replication.

18. The method for positioning the mobile device in the wireless wide area network as recited in claim 15, wherein the crossover processing comprises:

randomly selecting two combinations from the combinations in the parent population, and interchanging local codings within the two selected combinations to generate two combinations in the sub-population.

19. The method for positioning the mobile device in the wireless wide area network as recited in claim 15, wherein the mutation processing comprises:

randomly selecting at least one combination from the combinations with the parent population, and phase reversing at least one bit within the at least one combination to generate a combination in the sub-population.