A-A+

Indoor Localization

2012年12月29日 robotics 暂无评论 阅读 83,592 次
摘要:

Indoor localization refers to tracking objects in an indoor environment. This tracking can be either in 2‑dimensions, 3‑dimensions, or 2.5‑dimensions.

(Springer Free Artical)
Synonyms

Indoor location determination systems; Tracking; Reference, symbolic; Reference, coordinate based; Position, absolute; Position, relative; FCC 94-102; GPS; Time of flight; Arrival, Time of; Arrival, Angle of; Range Combining; Trilateration; Triangulation; Multilateration; Landmark proximity; WiMAX

Definition

Indoor localization refers to tracking objects in an indoor environment. This tracking can be either in 2‑dimensions, 3‑dimensions, or 2.5‑dimensions. 2.5‑dimensions refers to the case when the object position is tracked at discrete plans of the 3‑dimensional space, rather than the entire continuum of the 3‑dimensional space. For example, tracking a person in multiple 2‑dimensional floor-plans in a 3‑dimensional building can be considered a 2.5‑dimensional tracking.

An indoor location determination system can report the estimated location as a symbolic reference, for example, "the lounge", or as a coordinate-based reference. For the coordinate-based reference, the reported tracked‐object position can be either relative or absolute. Relative positioning refers to the case where the returned position is relative to a reference point, for example, the x and y coordinates of the position relative to the origin of the map. On the other hand, absolute positioning refers to the case when the returned position is in absolute coordinates, such as the longitude, altitude, and height coordinates.

An indoor location determination system can be centralized or distributed. In a centralized implementation, all the computations are implemented on a centralized server, relieving the computational load from the energy‐constrained mobile devices. For a distributed‐implementation, the location estimation is performed at the mobile devices. This allows better scalability for the system and, for human tracking, it allows better control over privacy.

Historical Background

Location determination systems have been an active research area for many years. Since the 1970's, the Global Positioning System (GPS) has been a well known and widely used location determination system. However, the GPS requires a line-of-sight to the satellites and, hence, is not suitable for high-accuracy indoor localization.

Wide-area cellular based systems have been active in developing location determination systems for locating cellular users motivated by the FCC 94‑102 order, mandating wireless E911. E911 refers to automatically locating cellular callers who dial the emergency 911 number equivalent to the wired 911 service.

A number of indoor location determination systems have been proposed over the years, including: infrared, ultrasonic, computer vision, and physical contact. All of these technologies share the requirement of specialized hardware, leading to more deployment and maintenance costs and poor scalability.

In the last few years, researchers have started looking at location determination systems that do not require any additional hardware. For example, in an 802.11 WLAN, the wireless card uses the signal strength returned form the access points to roam between different access points. This signal strength information is available to the application level. Therefore, a location determination system based on signal strength information in an 802.11 network, such as the Horus system [20], can be implemented without requiring any specialized hardware. This has the advantage of increasing the utility of the data network. A similar idea can be applied to FM radio signals to determine the location of an FM receiver [10] and also to Bluetooth networks [15].

Scientific Fundamentals

The basic idea used in a location determination system is to measure a physical quantity that is proportional to distance and use the measured value to estimate the distance to a reference point. This process is called ranging. Once the distance is known to one or more reference points, the position of the tracked object can be determined. This process is called range‐combining. All location determination systems use these two processes, ranging and range‐combining, either explicitly or implicitly. For example, in the GPS system, the reference points are the satellites and the physical quantity used is the time it takes the signal to travel from the satellite to the GPS receiver. The more time it takes the signal to travel from the satellite to the GPS receiver, the larger the distance between them.

Ranging Techniques

Examples of the signals that can be used in ranging include: Time-of-flight, Angle-of-arrival, and Signal‐strength.

Figure 1 The echoing technique for estimating the time of flight. p is the processing delay at the destination. The estimated time is

Time-of-flight based techniques depend on measuring the time the signal takes to travel from the transmitter to the receiver (called Time-of-Arrival or TOA), the difference of the arrival time at two or more receivers (called Time‐Difference-of-Arrival or TDOA), or the time it takes two different signals to reach the receiver from the same transmitter. For example, the system in [13] presented a location technique based on TOA obtained from Round-Trip-Time measurements (Fig. 1) at data link level of the 802.11 protocol. In their system, the sender sends a frame and includes the send timestamp, t 1, in it. As soon as the receiver gets the frame, it sends it back. When the sender gets the frame, it gets a timestamp of the receive time, t 2. The time difference between sending and receiving the frame, t 2 − t 1, is used as an estimate of the distance between the sender and receiver. Note that the processing time established at the receiver affects the accuracy of the estimated distance.

TDOA systems use the principle that the transmitter location can be estimated by the intersection of the hyperbolae of a constant differential TOA of the signal at two or more pairs of base stations (Fig. 2). The idea here is that a message transmitted from the sender is received by three or more receivers. Instead of keeping track of the absolute TOA of the signal, TDOA-based systems keep track of the difference of reception times of the transmitted message at the different receivers. Given two receivers' locations and a known TDOA, the locus of the sender location is a hyperboloid. For more than two receivers, the intersection of the hyperbolae associated with the TDOA of each pair of receivers provides the final transmitter's location.

Figure 2 TDOA systems use the principle that the transmitter location can be estimated by intersection of the hyperbolae of the constant differential TOA of the signal at two or more pairs of base stations

Systems that use two different physical signals, e. g., the Cricket System [16], which uses ultrasound and RF signals, use one of the signals for synchronization and the other for the time estimation. The idea is that the speed of the ultrasonic signal is much lower than the speed of the RF signal. Therefore, when the sender transmits an RF signal followed by an ultrasound signal, the receiver can use the difference in time between the reception of the ultrasound signal and the RF signal as an estimate of the distance between the sender and the receiver since the time it takes the RF signal to reach the receiver is negligible compared to the time it takes the ultrasound signal to reach the same receiver.

Angle-of-arrival (AOA) based techniques use antenna arrays to estimate the angle of arrival of the signal from the transmitter. The idea is to measure the difference of arrival time of the signal at individual elements of the array and use the delay to estimate the AOA. Based on the estimated AOA of a signal at two or more reference points, the location of the desired unit can be determined as the intersection of a number of lines (Fig. 3).

Figure 3 Based on the estimated AOA of a signal at two or more reference points, the location of the desired unit can be determined

Signal‐strength based techniques, e. g., the Horus system, use the signal strength received from a reference point as an estimate of how close the reference point is. For outdoor environments, the relation between signal strength and distance can be approximated by a logarithmic function. However, for indoor environments, this relation is very complex due to multiple phenomena, such as the multi-path effect and signal diffraction, among others. Therefore, indoor location determination systems that use signal strength usually use a lookup table to store the relation between the signal strength and distance. This table has been called a "radio-map" in the literature.

An example of another possibility that implies an implicit measurement of a physical quantity is the Cell-ID based method. In Cell-ID based methods, e. g., RF-IDs, the location of the transmitter is taken to be the location of the nearest base station it is associated with.

Hybrid methods can be used that combine two or more of these techniques. For example, combining propagation time measurement with angle measurement to obtain the position estimate can be done by using only one reference point (Fig. 4).

Figure 4 Combining propagation time measurement with angle measurement to obtain the position estimate can be done by using only one reference point

To obtain these physical measurements, different underlying communication technologies can be used. This includes infrared, ultrasonic, radio frequency (RF), computer vision, and physical contact, among others.

Range Combining Techniques

Once the range information is gathered from a number of reference points, it needs to be combined to estimate the location. This process is called Range‐combining. Trilateration, triangulation, multilateration, and landmark‐proximity are the most common techniques for combining ranges.

Trilateration refers to locating a node by calculating the intersection of three circles (Fig. 5). Each circle is centered at a reference point with a radius equal to the estimated range between the reference point and the node. If the ranges contain errors, the intersection of the three circles may not be a single point.

Figure 5 Trilateration locates a node by calculating the intersection of three circles. If the ranges contain an error, the intersection of the three circles may not be a single point

Triangulation is used when the angle of the node, instead of the distance, is estimated, as in AOA methods. The nodes' positions are calculated in this case by using the trigonometry laws of sines and cosines. In this case, at least two angles are required.

In multilateration, the position is estimated from distances to three or more known nodes by minimizing the error between the estimated position and the actual position by solving a set of non-linear equations.

Proximity-based techniques are usually used when no range information is available. For example, the GPS-less system [6] employs a grid of beacon nodes with known locations; each unknown node sets its position to the centroid of the beacon locations it is connected to.

Key Applications

Indoor localization can be used in many applications, most notably in context-aware applications and enhancing network protocols.

Context-Aware Applications

The context of an application refers to the information that is part of its operating environment. Typically, this includes information such as location, activity of people, and the state of other devices. Algorithms and techniques that allow an application to be aware of the location of a device on a map of the environment are a prerequisite for many of these applications. Examples of location-aware applications [7,8,18] include location‐sensitive content delivery, where tailored information is sent to the user based on his current location, direction finding, asset tracking, teleporting, robotics, and emergency notification.

Asset Tracking

Location information can be used to track assets in indoor environments. For example, RF-IDs have been widely used for tracking assets in military and civilian applications. Note that the technologies that can be used for asset tracking can also be used for tracking humans, such as in [19].

Direction Finding

Another important application for indoor localization is to find the direction and route between two points. This is similar to the GPS-based navigation systems in cars today, however, it is applied to indoor environments. For example, in the Shopping Assistance system [3], the device can guide the shoppers through the store, provide details of items, help locate items, point out items on sale, do a comparative price analysis, and so forth. There is a privacy concern since the store maintains the customer profiles. As a consequence, customers are divided into two classes. The first class is the regular customers who shop anonymously without profiles in the store. The second class is the store customers who signed up with a store will get additional discounts in exchange for sacrificing their privacy.

Guided Tours

In guided tour applications, e. g., [2], information can be displayed on a device carried by a user based on the device's current location. The user can also leave comments on an interactive map. This kind of tailored information enhances the user experience.

Call Forwarding

In this application[17], based on the Active Badge System, the user location is tracked in a central server that is connected to the enterpriser phone system. Whenever a call arrives to a user who is not currently in his office, the call is automatically routed to the room the user is located based on his/her current location.

Teleporting

The Teleporting System [4], developed at the Olivetti Research Laboratory (ORL), is a tool for experiencing obile applications The system allows users to dynamically change the display device from which their currently running applications are accessible. It operates within the X Window System and allows users to interact with their existing X applications at any X display within a building. The process of controlling the interface to the teleporting system comes from the use of an automatically maintained database of the location of equipment and people within the building.

Robotics

Finding the location of robots in indoor environments is crucial in many applications. For example, the system in [11] uses radio frequency identification (RFID) for robot-assisted indoor navigation for the visually impaired. Robots equipped with RFIDs and laser range finders allow visually impaired individuals to navigate in unfamiliar indoor environments and interact with the robotic guide via speech, sound, and wearable keyboards.

Network Protocols Enhancements

The second class of applications for indoor location determination systems is enhancements for network protocols. This usually applies to sensor network applications for indoor environments. These enhancements include determining the location of an event, location-based routing, node identification, and node coverage.

Determining the Location of an Event

Determining the location of an event is an important service that is particularly important in indoor sensor networks [5]. In indoor sensor networks, it is always important to record the location of an event whenever the event occurs. This highlights the importance of indoor location determination systems in such applications.

Location-Based Routing

A number of location based routing protocols have been proposed for using the location information of the sender and receiver to achieve scalable routing protocols. For example, the GPSR protocol [9] exploits the correspondence between geographic position and connectivity in a wireless network by using the positions of nodes to make packet forwarding decisions compared to the standard routing protocols that use graph‐theoretic notions of shortest paths and transitive reachability in order to find routes. GPSR uses greedy forwarding to forward packets to nodes that are always progressively closer to the destination. In regions of the network where such a greedy path does not exist (i. e., the only path requires that one move temporarily farther away from the destination), GPSR recovers by forwarding in perimeter mode, in which a packet traverses successively closer faces of a planar subgraph of the full radio network connectivity graph until reaching a node closer to the destination where greedy forwarding resumes.

Node ID

The inspection of building structures, especially bridges, is currently made by visual inspection [12]. The few non-visual methodologies make use of wired sensor networks which are relatively expensive, vulnerable to damage, and time consuming to install. Recordings of structures during ambient vibrations and seismic disturbances are essential in determining the demand placed upon those structures. For structures in high seismic areas, information provided by monitoring structural responses will inevitably lead to a better scientific understanding of how structures behave in the nonlinear realm. Using structure monitoring sensor networks is vital in these environments. It is a challenge for such huge indoor sensor networks to determine the node IDs for a large number of randomly placed nodes. Location determination can be used as node identification in these environments where the node location is used as its ID.

Node Coverage

One of the fundamental issues that arises in sensor networks is coverage. Coverage can be considered as the measure of quality of service of a sensor network [14]. For example, in a fire detection sensor network scenario, one may ask how well the network can observe a given area and what the chances are that a fire starting in a specific location will be detected in a given time frame. Furthermore, coverage formulations can try to find weak points in a sensor field and suggest future deployment or reconfiguration schemes for improving the overall quality of service. For the coverage problem, knowing the nodes' locations is essential for protocols that address this problem.

Future Directions

New different technologies, e. g., WiMax, are being developed that will allow larger transmission ranges and more accurate measurements of the physical quantities. This should allow more accurate and ubiquitous localization. As more accurate localization techniques are being introduces, a new set of applications are emerging to take advantage of these localization capabilities, including GPS-less city wide localization [1].

Cross References

Recommended Reading

  • 1. http://www.skyhookwireless.com/
  • 2. Abowd, G.D., Atkeson, C.G., Hong, J., Long, S., Kooper, R., Pinkerton, M.: Cyberguide: A mobile context-aware tour guide. Wireless Networks 3(5), 421-433 (1997)
  • 3. Asthana, A., Cravatts, M., Krzyzanowski, P.: An indoor wireless system for personalized shopping assistance. In: IEEE Workshop on Mobile Computing Systems and Applications, pp. 69-74. Santa Cruz, California (1994)
  • 4. Bennett, F., Richardson, T., Harter, A.: Teleporting - making applications mobile. In: IEEE Workshop on Mobile Computing Systems and Applications, pp. 82-84. Santa Cruz, California (1994)
  • 5. Brooks, A., Makarenko, A., Kaupp, T., Williams, S., Durrant-Whyte, H.: Implementation of an indoor active sensor network. In: Int. Symp. on Exp. Robotics, Singapore (2004)
  • 6. Bulusu, N., Heidemann, J., Estrin, D.: GPS-less Low-cost Outdoor Localization for Very Small Devices. In: IEEE Personal Communications (2000)
  • 7. Chen, G., Kotz, D.: A survey of context-aware mobile computing research. Technical Report Dartmouth Computer Science Technical Report TR2000-381 (2000)
  • 8. Gellersen, H.-W., Schmidt, A., Beigl, M.: Adding some smartness to devices and everyday things. In: IEEE Workshop on Mobile Computing Systems and Applications, pp. 3-10. December (2000)
  • 9. Karp, B., Kung, H.T.: Greedy perimeter stateless routing for wireless networks. In: Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), pp. 243-254: Boston, MA (2004)
  • 10. Krumm, J., Cermak, G., Horvitz, E.: Rightspot: A novel sense of location for a smart personal object. In: Fifth International Conference on Ubiquitous Computing, October (2003)
  • 11. Kulyukin, V., Gharpure, C., Nicholson, J., Pavithran, S.: RFID in robot-assisted indoor navigation for the visually impaired. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2004, pp. 1979-1984. (2004)
  • 12. Lynch, J.P., Kiremidjian, A.S., Law, K.H., Kenny, T., Carryer, E.: Issues in wireless structural damage monitoring technologies. In: 3rd World Conference on Structural Control (WCSC), Como, Italy (2002)
  • 13. Sebastiano, C., Ciurana, M., Barcelo,F.: Indoor tracking in wlan location with toa measurements. In: MobiWac 2006 (2006)
  • 14. Meguerdichian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.B.: Coverage problems in wireless ad-hoc sensor networks. In: INFOCOM, pp. 1380-1387 (2001)
  • 15. Peddemors, A.J.H., Lankhorst, M.M., de Heer, J.: Presence, Location, and Instant Messaging in a Context-Aware Application Framework. Proc. of the Intl. Conf. on Mobile Data Management (MDM) 2574, 325-330
  • 16. Priyantha, N.B., Chakraborty, A., Balakrishnan, H.: The cricket location-support system. In: 6th ACM MOBICOM, Boston, MA, August (2000)
  • 17. Want, R., Hopper, A., Falcão, V., Gibbons, J.: The active badge location system. ACM Transactions on Information Systems 10(1), 91-102 (1992)
  • 18. Want, R., Schilit, B.: Expanding the horizons of location-aware computing. IEEE Computer 34(8), 31-34 (2001)
  • 19. Want, R., Schilit, B.N., Adams, N.I., Gold, R., Petersen, K., Goldberg, D., Ellis, J.R., Weiser, M.: An overview of the parctab ubiquitous computing experiment. IEEE Personal Communications 2(6), 28-43 (1995)
  • 20. Youssef, M., Agrawala, A.: The Horus WLAN Location Determination System. In: Third International Conference on Mobile Systems, Applications, and Services (MobiSys 2005), June (2005)
标签:

给我留言

Copyright © ExBot易科机器人实验室 保留所有权利.   Theme   Robin modified by poyoten

用户登录

分享到: