LOCATION BASED SERVICE SYSTEM AND METHOD FOR PERFORMING INDOOR NAVIGATION

• US 20120072106A1
• Filed: 07/08/2011
• Published: 03/22/2012
• Est. Priority Date: 07/21/2010
• Status: Abandoned Application

• Current Assignee: Korea Advanced Institute of Science and Technology, Korea Trade Network
• Original Assignee: Korea Advanced Institute of Science and Technology, Korea Trade Network
• Inventors: HAN, Dong Soo, LEE, Min Kyu, CHANG, Lae Young, YANG, Hyun II, LEE, In Je, MIN, Cheol Hong, KIM, Dong Hee, LEE, Hwa Jin
• Application Number:
  US13/179,006
• Publication Number:
  US 20120072106A1
• Time in Patent Office: Days
• US Class Current: 701/410
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map

Abstract

Embodiments for performing an indoor navigation are disclosed. The location based service system includes: a plurality of access points installed in an indoor environment and configured to send Wi-Fi signals including access point identification information; a mobile terminal configured to receive a Wi-Fi signal from at least one of the access points and form a first Wi-Fi fingerprint based on the received Wi-Fi signal; and a navigation service server configured to construct a plurality of Wi-Fi radio maps based on a plurality of second Wi-Fi fingerprints acquired at locations of the indoor environment, select a Wi-Fi radio map for estimating a location of the mobile terminal among the plurality of Wi-Fi radio maps, estimate the location the mobile terminal by using a second Wi-Fi fingerprint corresponding to the first Wi-Fi fingerprint based on the selected Wi-Fi radio map, and form location information including the estimated location.

Claims

1. A location based service system, comprising:

a plurality of access points installed in an indoor environment and configured to send Wi-Fi signals including access point identification information;

a mobile terminal configured to receive a Wi-Fi signal from at least one of the access points and form a first Wi-Fi fingerprint based on the received Wi-Fi signal; and

a navigation service server in communication with the mobile terminal, the navigation service server being configured to construct a plurality of Wi-Fi radio maps based on a plurality of second Wi-Fi fingerprints acquired at locations of the indoor environment, select a Wi-Fi radio map for estimating a location of the mobile terminal among the plurality of Wi-Fi radio maps, estimate the location of the mobile terminal by using a second Wi-Fi fingerprint corresponding to the first Wi-Fi fingerprint based on the selected Wi-Fi radio map, and form location information including the estimated location,

wherein the first and second Wi-Fi fingerprints include received signal strength of the Wi-Fi signal and the access point identification information of the access point that sends the Wi-Fi signal.

2. The location based service system of claim 1, wherein the access point identification information includes a media access control address.

3. The location based service system of claim 1, wherein the mobile terminal includes:

a Wi-Fi fingerprint forming unit configured to form the first Wi-Fi fingerprint based on the received Wi-Fi signal; and

a first communication module configured to receive the Wi-Fi signal sent from the access point, and transmit the first Wi-Fi fingerprint to the navigation service server.

4. The location based service system of claim 1, wherein the navigation service server includes:

a navigation service constructing unit configured to construct the plurality of Wi-Fi radio maps corresponding to the plurality of second Wi-Fi fingerprints by the respective moving directions and speeds of the mobile terminal;

a database unit configured to store the plurality of Wi-Fi radio maps;

a location estimating unit configured to acquire a moving direction and speed of the mobile terminal, retrieve the database unit to select a Wi-Fi radio map corresponding to the acquired moving direction and speed, detect a second Wi-Fi fingerprint corresponding to the first Wi-Fi fingerprint from the selected Wi-Fi radio map, estimate a location of the detected second Wi-Fi fingerprint as the location of the mobile terminal, and form the location information including the estimated location; and

a second communication module configured to receive the first Wi-Fi fingerprint and transmit the location information to the mobile terminal.

5. The location based service system of claim 4, wherein the mobile terminal further includes:

a user input unit configured to receive input information for setting a final destination from a user;

a navigation executing unit configured to execute an indoor navigation for displaying current location information on a map corresponding to the indoor environment based on the location information, forming route information from a current location of the mobile terminal to the final destination based on the input information, and displaying the route information on the map; and

an output unit configured to output the indoor navigation executed by the navigation executing unit.

6. The location based service system of claim 4, wherein the navigation service constructing unit is configured to:

construct the plurality of Wi-Fi radio maps based on the plurality of second Wi-Fi fingerprints;

partition an indoor navigation service target region into a plurality of regions for each of the Wi-Fi radio maps;

classify the plurality of second Wi-Fi fingerprints by the respective partition regions for each of the Wi-Fi radio maps; and

construct access point indexes for mapping the partition region to which each of the second Wi-Fi fingerprints belongs with the access point identification information of the access points which charge the partition region.

7. The location based service system of claim 6, wherein the Wi-Fi radio map includes at least one of a mobile Wi-Fi radio map reflecting a signal dragging phenomenon which occurs by the movement of the mobile terminal and a fixed Wi-Fi radio map which does not reflect the signal dragging phenomenon.

8. The location based service system of claim 6, wherein the navigation service constructing unit is further configured to construct the plurality of Wi-Fi radio maps by the respective moving directions and speeds of the mobile terminal.

9. The location based service system of claim 6, wherein the navigation service constructing unit is further configured to:

set an accuracy target value and a precision target value for estimating the location of the mobile terminal;

initialize the size of the partition regions for each of the Wi-Fi radio maps;

calculate accuracy and precision of a location estimation of the mobile terminal for the initialized size of the partition regions;

compare the calculated precision with the precision target value, if it is determined that the calculated precision does not satisfy the precision target value, ease and reset the accuracy target value and the precision target value;

if it is determined that the calculated precision satisfies the precision target value, compare the calculated accuracy with the accuracy target value, if it is determined that the calculated accuracy does not satisfy the accuracy target value, increase the size of the partition regions to a predetermined size;

if it is determined that the calculated accuracy satisfies the accuracy target value, set the size of the partition regions as the final size of the partition regions.

10. The location based service system of claim 6, wherein the navigation service constructing unit is configured to:

select second Wi-Fi fingerprints including the access point identification information of the same access points from the second Wi-Fi fingerprints included in the Wi-Fi radio map; and

detect a partition region that the selected second Wi-Fi fingerprints are gathered and construct connection information between the access point identification information of the access point and the detected partition region.

11. The location based service system of claim 6, wherein the location estimating unit is configured to:

acquire moving direction and speed information of the mobile terminal;

retrieve the database unit to select a Wi-Fi radio map corresponding to the acquired moving direction and speed information;

decide a partition region corresponding to the first Wi-Fi fingerprint based on the access point indexes;

calculate distances between the first Wi-Fi fingerprints and each of the second Wi-Fi fingerprints which belong to the decided partition region;

compare the distances to detect a second Wi-Fi fingerprint corresponding to the shortest distance as a Wi-Fi fingerprint which is closest to the first Wi-Fi fingerprint; and

estimate a location of the detected second Wi-Fi fingerprint as the location of the mobile terminal.

12. The location based service system of claim 11, wherein the location estimating unit is further configured to:

decide the decided partition region and regions which are close to the decided partition region, as a search region;

decide a gathering location of a second Wi-Fi fingerprint, which is closest to the first Wi-Fi fingerprint among the second Wi-Fi fingerprints of the search region, as an estimated location; and

determine whether a partition region corresponding to the estimated location is identical to the decided partition region, if it is determined that the partition region corresponding to the estimated location is not identical to the decided partition region, disregarding the estimated location.

13. The location based service system of claim 4, wherein the navigation service constructing unit is configured to:

construct the plurality of Wi-Fi radio maps based on the plurality of second Wi-Fi fingerprints; and

analyze the plurality of second Wi-Fi fingerprints for each of the Wi-Fi radio maps to assign an index key to each of the second Wi-Fi fingerprints.

14. The location based service system of claim 13, wherein the navigation service constructing unit is configured to:

detect signal strength of the Wi-Fi signal corresponding to each of the access points included in each of the second Wi-Fi fingerprints;

compare the detected signal strength to extract the predetermined number of access points in order of signal strength; and

assign the extracted access points as the index key to each of the second Wi-Fi fingerprints.

15. The location based service system of claim 14, wherein the location estimating unit is configured to:

acquire moving direction and speed information of the mobile terminal;

retrieve the database unit to select a Wi-Fi radio map corresponding to the acquired moving direction and speed information;

detect signal strength of the Wi-Fi signal by the respective access points included in the first Wi-Fi fingerprint;

compare the detected signal strength to extract the predetermined number of access points in order of signal strength;

detect a second Wi-Fi fingerprint to which the extracted access points are assigned as the index key from the selected Wi-Fi radio map; and

estimate a location of the detected second Wi-Fi fingerprint as the location of the mobile terminal.

16. The location based service system of claim 13, wherein the navigation service constructing unit is configured to:

detect signal strength of the Wi-Fi signal based on variance in the signal strength and a receiving probability of the Wi-Fi signal by the respective access points included in each of the plurality of second Wi-Fi fingerprints;

extract the predetermined number of access points in order of receiving probability for receiving the strongest Wi-Fi signal based on the detected signal strength, and variance and receiving probability for each of the plurality of second Wi-Fi fingerprints; and

assign the extracted access points to each of the second Wi-Fi fingerprints as the index key.

17. The location based service system of claim 16, wherein the location estimating unit is configured to:

acquire moving direction and speed information of the mobile terminal;

retrieve the database unit to select a Wi-Fi radio map corresponding to the acquired moving direction and speed information;

receive a plurality of first Wi-Fi fingerprints provided from the mobile terminal;

detect signal strength of the Wi-Fi signal based on variance of the signal strength and a receiving probability of the Wi-Fi signal by the respective access points for each of the first Wi-Fi fingerprints;

extract the predetermined number of access points in order of a receiving probability for receiving the strongest Wi-Fi signal based on the detected signal strength, and variance and receiving probability;

detect a second Wi-Fi fingerprint to which the extracted access points are assigned as the index key from the selected Wi-Fi radio map; and

estimate a location of the detected second Wi-Fi fingerprint as the location of the mobile terminal.

18. The location based service system of claim 4, wherein the navigation service constructing unit is configured to:

construct the plurality of Wi-Fi radio maps based on the plurality of second Wi-Fi fingerprints;

set a Wi-Fi fingerprint confusion area that a floor-level error occurs on the plurality of Wi-Fi radio maps.

19. The location based service system of claim 18, wherein the location estimating unit is configured to:

acquire moving direction and speed information of the mobile terminal;

retrieve the database unit to select a Wi-Fi radio map corresponding to the acquired moving direction and speed information;

estimate the location of the mobile terminal from the selected Wi-Fi radio map based on the first Wi-Fi fingerprint;

determine whether the estimated location is the Wi-Fi fingerprint confusion area, if it is determined that the estimated location is the Wi-Fi fingerprint confusion area, analyze the first Wi-Fi fingerprint to detect the number of access points included in the first Wi-Fi fingerprint;

compare the detected number of access points with a predetermined threshold, if it is determined that the detected number of access points is equal to or less than the predetermined threshold, perform a floor-level location correction based on the first Wi-Fi fingerprint; and

reestimate the location of the mobile terminal at the corrected floor-level location based on the first Wi-Fi fingerprint.

20. The location based service system of claim 19, wherein the location estimating unit is configured to perform the floor-level location correction of the estimated location in consideration of a set similarity between the first Wi-Fi fingerprint and each of the second Wi-Fi fingerprints corresponding to the Wi-Fi fingerprint confusion area by using Jaccard'"'"'s coefficient.

21. The location based service system of claim 1, wherein the mobile terminal is further configured to receive input information for setting a final destination from a user.

22. The location based service system of claim 21, wherein the navigation service server is further configured to:

assign fingerprint identification information to the second Wi-Fi fingerprints for each of the Wi-Fi radio maps;

estimate a current location of the mobile terminal, based on the Wi-Fi radio map for estimating a location of the mobile terminal among the plurality of Wi-Fi radio maps and the first Wi-Fi fingerprint; and

extract the fingerprint identification information of the second Wi-Fi fingerprints corresponding to an optimal route from the current location to the final destination based on the estimated current location and the input information to thereby form Wi-Fi fingerprint information.

23. The location based service system of claim 22, wherein the mobile terminal includes:

a Wi-Fi fingerprint forming unit configured to form the first Wi-Fi fingerprint based on the Wi-Fi signal;

a user input unit configured to receive the input information from the user;

a first communication module configured to receive the Wi-Fi signal sent from the at least one of the access points and the Wi-Fi fingerprint identification information, and transmit the first Wi-Fi fingerprint to the navigation service server;

a navigation executing unit configured to execute the indoor navigation based on the Wi-Fi fingerprint information; and

an output unit configured to output the indoor navigation executed at the navigation executing unit.

24. The location based service system of claim 22, wherein the navigation service server includes:

navigation service constructing unit configured to acquire the plurality of second Wi-Fi fingerprints based on moving directions and speeds of the mobile terminal, construct the plurality of Wi-Fi radio maps based on the plurality of second Wi-Fi fingerprints, and assign the Wi-Fi fingerprint identification information to the second Wi-Fi fingerprints for each of the Wi-Fi radio maps;

a database unit for storing the plurality of Wi-Fi radio maps and the Wi-Fi fingerprint identification information;

a location estimating unit configured to acquire moving direction and speed of the mobile terminal, retrieve the database unit to select a Wi-Fi radio map corresponding to the acquired moving direction and speed, estimate a current location of the mobile terminal from a second Wi-Fi fingerprint corresponding to the first Wi-Fi fingerprint based on the selected Wi-Fi radio map, and form the Wi-Fi fingerprint information based on the estimated current location and the input information; and

a second communication module configured to receive the first Wi-Fi fingerprint and the input information, and transmit the Wi-Fi fingerprint information to the mobile terminal.

25. The location based service system of claim 24, wherein the navigation service constructing unit is configured to:

partition an indoor navigation service target region into a plurality of regions for each of the Wi-Fi radio maps to which the Wi-Fi fingerprint identification information is assigned; and

index the plurality of second Wi-Fi fingerprints to the partition regions for each of Wi-Fi radio maps.

26. The location based service system of claim 25, wherein the fingerprint identification information includes identification information.

27. The location based service system of claim 25, wherein the location estimating unit is configured to:

acquire moving direction and speed information of the mobile terminal;

retrieve the database unit to select a Wi-Fi radio map corresponding to the acquired moving direction and speed information;

decide a partition region corresponding to the first Wi-Fi fingerprint;

calculate distances between the first Wi-Fi fingerprint and each of the second Wi-Fi fingerprints belonging to the decided partition region;

compare the calculated distances to detect a second Wi-Fi fingerprint corresponding to the shortest distance as a Wi-Fi fingerprint which is closest to the first Wi-Fi fingerprint; and

estimate a location of the detected second Wi-Fi fingerprint as the location of the mobile terminal.

28. The location based service system of claim 27, wherein the location estimating unit is further configured to:

decide the decided partition region and a region which is close to the decided partition region as a search region;

decide a gathering location of a second Wi-Fi fingerprint which is closest to the first Wi-Fi fingerprint among the second Wi-Fi fingerprints of the search region as an estimation location; and

determine whether a partition region corresponding to the estimation location is identical to the decided partition region, if it is determined that the partition region corresponding to the estimation location is not identical to the decided partition region, disregard the estimation location.

29. The location based service system of claim 25, wherein the location estimating unit is configured to:

detect the optimal route from the current location to the final destination based on the current location and the input information for selected Wi-Fi radio map;

detect partition regions corresponding to the optimal route;

extract Wi-Fi fingerprint identification information corresponding to the detected partition regions; and

form the Wi-Fi fingerprint information including second Wi-Fi fingerprints corresponding to the extracted Wi-Fi fingerprint identification information.

30. A method of performing an indoor navigation in a location based service system including a plurality of access points, which are installed in an indoor environment and configured to send Wi-Fi signals including access point identification information;

a mobile terminal and a navigation service server, the method comprising;

a) at the navigation service server, constructing a plurality of Wi-Fi radio maps based on a plurality of first Wi-Fi fingerprints acquired at a plurality of locations of the indoor environment;

b) at the mobile terminal, receiving a Wi-Fi signal from at least one of the access points and forming a second Wi-Fi fingerprint based on the received Wi-Fi signal;

c) at the navigation service server, selecting a Wi-Fi radio map for estimating a location of the mobile terminal among the plurality of Wi-Fi radio maps; and

d) at the navigation service server, estimating the location of the mobile terminal by using a first Wi-Fi fingerprint corresponding to the second Wi-Fi fingerprint based on the selected Wi-Fi radio map, and forming position information including the estimated location,

wherein the first and second Wi-Fi fingerprints include received signal strength of the Wi-Fi signal and the access point identification information of the access point that sends the Wi-Fi signal.

31. The method of claim 30, wherein the access point identification information includes a media access control address.

32. The method of claim 30, wherein the Wi-Fi radio map includes at least one of a mobile Wi-Fi radio map reflecting a signal dragging phenomenon which occurs by the movement of the mobile terminal and a fixed Wi-Fi radio map which does not reflect the signal dragging phenomenon.

33. The method of claim 30, wherein the step a) comprises:

a1) constructing the plurality of Wi-Fi radio maps corresponding to the plurality of first Wi-Fi fingerprints in consideration of moving directions and speeds of the mobile terminal;

a2) partitioning an indoor navigation service target region into a plurality of regions for each of the Wi-Fi radio maps;

a3) classifying the plurality of first Wi-Fi fingerprints by the respective partition regions for each of the Wi-Fi radio maps; and

a4) constructing access point indexes for mapping a partition region to which each of the first Wi-Fi fingerprints belongs with the access point identification information of the access points which charge the partition region.

34. The method of claim 33, wherein the step a2) further comprises:

setting an accuracy target value and a precision target value for estimating the location of the mobile terminal;

initializing the size of the partition regions for each of the Wi-Fi radio maps;

calculating accuracy and precision of a location estimation of the mobile terminal for the initialized size of the partition regions;

comparing the calculated precision with the precision target value, if it is determined that the calculated precision does not satisfy the precision target value, ease and reset the accuracy target value and the precision target value;

if it is determined that the calculated precision satisfies the precision target value, comparing the calculated accuracy with the accuracy target value, if it is determined that the calculated accuracy does not satisfy the accuracy target value, increasing the size of the partition regions to a predetermined size;

if it is determined that the calculated accuracy satisfies the accuracy target value, setting the size of the partition regions as the final size of the partition regions.

35. The method of claim 33, wherein the step a4) comprises:

selecting first Wi-Fi fingerprints including the access point identification information of the same access points from the first Wi-Fi fingerprints included in the Wi-Fi radio map; and

detecting a partition region that the selected first Wi-Fi fingerprints are gathered and construct connection information between the access point identification information of the access point and the detected partition region.

36. The method of claim 30, wherein the step c) comprises:

acquiring moving direction and speed information of the mobile terminal;

selecting a Wi-Fi radio map corresponding to the acquired moving direction and speed information.

37. The method claim 33, wherein the step d) comprises:

deciding a partition region corresponding to the second Wi-Fi fingerprint based on the access point indexes;

calculating distances between the second Wi-Fi fingerprint and each of the first Wi-Fi fingerprints which belong to the decided partition region;

comparing the distances to detect a first Wi-Fi fingerprint corresponding to the shortest distance as a Wi-Fi fingerprint which is closest to the second Wi-Fi fingerprint;

estimating a location of the detected first Wi-Fi fingerprint as the location of the mobile terminal; and

forming location information including the estimated location.

38. The method of claim 37, wherein the step d) further comprises:

deciding the decided partition region and regions which are close to the decided partition region, as a search region;

deciding a gathering location of a first Wi-Fi fingerprint which is closest to the second Wi-Fi fingerprint among the first Wi-Fi fingerprints of the search region, as an estimated location; and

determining whether a partition region corresponding to the estimated location is identical to the decided partition region, if it is determined that the partition region corresponding to the estimated location is not identical to the decided partition region, disregarding the estimated location.

39. The method of claim 30, wherein the step a) comprises:

a1) constructing the plurality of Wi-Fi radio maps based on the plurality of first Wi-Fi fingerprints; and

a2) analyzing the plurality of first Wi-Fi fingerprints for each of the Wi-Fi radio maps to assign an index key to each of the first Wi-Fi fingerprints.

40. The method of claim 39, wherein the step a2) comprises:

detecting signal strength of the Wi-Fi signal corresponding to each of the access points included in each of the first Wi-Fi fingerprints;

comparing the detected signal strength to extract the predetermined number of access points in order of signal strength; and

assigning the extracted access points as the index key to each of the first Wi-Fi fingerprints.

41. The method of claim 39, wherein the step d) comprises:

detecting signal strength of the Wi-Fi signal by the respective access points included in the second Wi-Fi fingerprint;

comparing the detected signal strength to extract the predetermined number of access points in order of signal strength;

detecting a first Wi-Fi fingerprint to which the extracted access points are assigned as the index key from the selected Wi-Fi radio map; and

estimating a location of the detected first Wi-Fi fingerprint as the location of the mobile terminal.

42. The method of claim 30, wherein the step a) comprises:

detecting signal strength of the Wi-Fi signal based on variance in signal strength and a receiving probability of the Wi-Fi signal by the respective access points included in each of the plurality of first Wi-Fi fingerprints;

extracting the predetermined number of access points in order of a receiving probability of receiving the strongest Wi-Fi signal based on the detected signal strength, and variance and receiving probability for each of the plurality of second Wi-Fi fingerprints; and

assigning the extracted access points to each of the first Wi-Fi fingerprints as the index key.

43. The method of claim 42, wherein the step d) comprises:

receiving a plurality of second Wi-Fi fingerprints provided from the mobile terminal;

detecting signal strength of the Wi-Fi signal based on variance in signal strength and a receiving probability of the Wi-Fi signal by the respective access points for each of the second Wi-Fi fingerprints;

extracting the predetermined number of access points in order of a receiving probability of the strongest Wi-Fi signal based on the detected signal strength, and variance and receiving probability;

detecting a first Wi-Fi fingerprint to which the extracted access points are assigned as the index key from the selected Wi-Fi radio map; and

estimating a location of the detected first Wi-Fi fingerprint as the location of the mobile terminal.

44. The method of claim 30, wherein the step a) comprises:

constructing the plurality of Wi-Fi radio maps based on the plurality of first Wi-Fi fingerprints;

setting a Wi-Fi fingerprint confusion area that a floor-level error occurs on the plurality of Wi-Fi radio maps.

45. The method of claim 44, wherein the step d) comprises:

d1) estimating the location of the mobile terminal from the selected Wi-Fi radio map based on the second Wi-Fi fingerprint;

d2) determining whether the estimated location is the Wi-Fi fingerprint confusion area, if it is determined that the estimated location is the Wi-Fi fingerprint confusion area, analyzing the second Wi-Fi fingerprint to detect the number of access points included in the second Wi-Fi fingerprint;

d3) comparing the detected number of access points with a predetermined threshold, if it is determined that the detected number of the access points is equal to or less than the predetermined threshold, performing a floor-level location correction based on the second Wi-Fi fingerprint; and

d4) reestimating the location of the mobile terminal at the corrected floor-level location based on the second Wi-Fi fingerprint.

46. The method of claim 45, wherein the step d3) comprises:

performing the floor-level location correction of the estimated location in consideration of a set similarity between the second Wi-Fi fingerprint and each of the first Wi-Fi fingerprints corresponding to the Wi-Fi fingerprint confusion area by using Jaccard'"'"'s coefficient.

47. The method of claim 30, further comprising:

e) at the mobile terminal, executing the indoor navigation for displaying the current location information on a map corresponding to the indoor environment based on the location information and displaying route information from the current location to the final destination; and

f) at the mobile terminal, outputting the indoor navigation.

48. A method of performing an indoor navigation in a location based service system including a plurality of access points, which are installed in an indoor environment and configured to send Wi-Fi signals including access point identification information;

a mobile terminal and a navigation service server, the method comprising;

a) at the navigation service server, constructing a plurality of Wi-Fi radio maps based on a plurality of first Wi-Fi fingerprints acquired at a plurality of locations of the indoor environment;

b) assigning Wi-Fi fingerprint identification information to the first Wi-Fi fingerprints for each of the Wi-Fi radio maps;

c) at the mobile terminal, receiving a Wi-Fi signal from at least one of the access points and forming a second Wi-Fi fingerprint based on the received Wi-Fi signal;

d) at the navigation service server, estimating a location of the mobile terminal based on a Wi-Fi radio map for estimating the location of the mobile terminal among the plurality of the Wi-Fi radio maps and the second Wi-Fi fingerprint;

e) at the mobile terminal, receiving input information for setting a final destination from a user;

f) at the navigation service server, extracting the Wi-Fi fingerprint identification information of the first Wi-Fi fingerprints corresponding to an optimal route from the current location to final destination based on the estimated current location and the input information to thereby form the Wi-Fi fingerprint information; and

g) at the mobile terminal, executing an indoor navigation based on the Wi-Fi fingerprint information,

wherein the first and second Wi-Fi fingerprints include a received signal strength of the Wi-Fi signal and access point identification information of an access point that sends the Wi-Fi signal.

49. The method of claim 48, wherein the access point identification information includes a media access control address.

50. The method of claim 48, wherein the Wi-Fi fingerprint identification information includes identification information.

51. The method of claim 48, wherein the Wi-Fi radio map includes at least one of a mobile Wi-Fi radio map reflecting a signal dragging phenomenon which occurs by the movement of the mobile terminal and a fixed Wi-Fi radio map which does not reflect the signal dragging phenomenon.

52. The method of claim 48, wherein the step a) comprises:

acquiring the plurality of first Wi-Fi fingerprints based on moving directions and speeds of the mobile terminal; and

constructing the plurality of Wi-Fi radio maps based on the plurality of first Wi-Fi fingerprints by the respective moving directions and speeds.

53. The method of claim 48, wherein the step b) further comprises:

b1) partitioning an indoor navigation service target region into a plurality of regions for each of the Wi-Fi radio maps to which the Wi-Fi fingerprint identification information is assigned; and

b2) indexing the plurality of first Wi-Fi fingerprints to the partition regions for each of Wi-Fi radio maps.

54. The method of claim 53, wherein the step b1) further comprises:

setting an accuracy target value and a precision target value for estimating the location of the mobile terminal;

initializing the size of the partition regions for each of the Wi-Fi radio maps;

calculating accuracy and precision for estimating the location of the mobile terminal at the size of the corresponding partition regions;

comparing the calculated precision with the precision target value, if it is determined that the calculated precision does not satisfy the precision target value, easing and resetting the accuracy target value and the precision target value;

if it is determined that the calculated precision satisfies the precision target value, comparing the calculated accuracy with the accuracy target value, if it is determined that the calculated accuracy does not satisfy the accuracy target value, increasing the size of the partition regions into a predetermined size;

if it is determined that the calculated accuracy satisfies the accuracy target value, setting the size of the partition regions as a final size of the partition regions.

55. The method of claim 48, wherein the step d) comprises:

d1) acquiring moving direction and speed information of the mobile terminal;

d2) selecting a Wi-Fi radio map corresponding to the acquired moving direction and speed information among the plurality of Wi-Fi radio maps; and

d3) estimating a current location of the mobile terminal from the first Wi-Fi fingerprint corresponding to the second Wi-Fi fingerprint based on the selected Wi-Fi radio map.

56. The method of claim 55, wherein the step d3) comprises:

deciding a partition region corresponding to the second Wi-Fi fingerprint for the selected Wi-Fi radio map;

calculating distances between the second Wi-Fi fingerprint and each of the first Wi-Fi fingerprints belonging to the decided partition region;

comparing the calculated distances to detect a first Wi-Fi fingerprint corresponding to the shortest distance as a Wi-Fi fingerprint which is closest to the second Wi-Fi fingerprint; and

estimating a position of the detected first Wi-Fi fingerprint as the location of the mobile terminal.

57. The method of claim 56, wherein the step d3) further comprises:

deciding the decided partition region and a region which is close to the decided partition region as a search region;

deciding a gathering location of a first Wi-Fi fingerprint which is closest to the second Wi-Fi fingerprint among the first Wi-Fi fingerprints of the search region as an estimation location; and

determining whether a partition region corresponding to the estimation location is identical to the decided partition region, if it is determined that the partition region corresponding to the estimation location is not identical to the decided partition region, disregarding the estimation location.

58. The method of claim 55, wherein the step f) comprises:

detecting the optimal route from the current location to the final destination based on the current location and the input information for the selected Wi-Fi radio map;

detecting partition regions corresponding to the optimal route;

extracting Wi-Fi fingerprint identification information corresponding to the detected partition regions; and

forming the Wi-Fi fingerprint information including second Wi-Fi fingerprints corresponding to the extracted Wi-Fi fingerprint identification information.