Radio map construction method

1. A radio map construction method performed by a radio map construction apparatus, the method comprising:

modeling an internal structure of a building, in which a radio map is to be constructed, by a topology according to a hidden Markov model (HMM), wherein the topology represents each location in the building as a state and a geographic accessibility between locations as a transition, the modeling including collecting a fingerprint sequence through a designated application of the portable terminal;

(a) generating a plurality of chromosomes including a set of pairs of fingerprints labeled with addresses of residences within the building and locations selected within regions of the addresses;

(b) generating a first temporary radio map by using the pairs of the chromosomes;

(c) performing placement of fingerprint sequences collected by using the first temporary radio map;

(d) evaluating the placement of the fingerprint sequences by using a loss function to accumulate a penalty for a corresponding temporary radio map, whenever a labeling distance accompanied with a change from one fingerprint to another fingerprint in placements of the fingerprint sequences is determined to be equal to or greater than a maximum movable distance associated with a mobility of a user of the application of the portable terminal; and

(e) repeating of steps (b) through (d) for at least one other generated temporary radio map and selecting an actual radio map for construction from among the first and at least one other generated temporary radio map based on using the loss function of each of the first and the at least one other generated temporary radio map to determine a radio map having a best placement as the actual radio map.

2. The method of claim 1 , wherein when at least the step (a) is performed at first to configure a first generation, the selected locations are randomly selected within a region of a corresponding address; and

the steps (b) to (d) are performed sequentially on each of a plurality of chromosomes.

3. The method of claim 2 , wherein the step (d) evaluates the placement of the fingerprint sequences on the basis of the first temporary radio map generated by using a loss function reflecting a mobility of a user in the fingerprint sequences.

4. The method of claim 3 , wherein the radio map construction method includes:

filtering a portion of the plurality of chromosomes according to a result of the evaluation in the step (d) to configure a next generation including the filtered portion of the chromosomes and new chromosomes; and

repeatedly performing the steps (b) to (d).

5. The method of claim 4 , wherein the radio map construction method includes:

terminating a repetitive performance of the steps (b) to (d) through generation evolution when no more gain exists as a result of the evaluation using the loss function as compared with a previous generation.

6. The method of claim 1 , wherein the first temporary radio map is generated through a process of generating a fingerprint corresponding to each location in the building using sets of the pairs and through an interpolation technique.

7. The method of claim 1 , before the step (a), further comprising:

collecting fingerprints corresponding to a specified address through a designated application; and

classifying the address-labeled fingerprints via the collecting according to addresses,

wherein the designated application is a payment application or a resource usage metering application.

8. The method of claim 7 , further comprising:

clustering the fingerprints collected in correspondence with the designated address into a plurality of groups and determining a fingerprint to be labeled with the address using the fingerprints of the clustered group.

9. The method of claim 7 , further comprising:

collecting a fingerprint sequence including fingerprints and a series of collection times using the designated application before the step (a).

10. The method of claim 7 , wherein the collecting of the fingerprints corresponding to the designated address includes

correcting fingerprints including pairs of signal strengths and one or more wireless AP identifiers collected by the designated application for a predetermined time before, after, or before and after an occurrence time of a transaction through the designated application.

11. The method of claim 7 , wherein the steps (a) to (d) are performed on fingerprints of addresses classified as a commercial area.

12. The method of claim 11 , wherein when an address of the classified addresses is a residential area, a radio map of the residential area is further constructed through an interpolation technique for fingerprints corresponding to the address of the residential area.