CSC560: Design and Analysis of Real Time Systems

Positioning objects has been an important topic since it is needed to locate people, guide them to a certain place, and assist companies and organizations with their assets management. These systems have been successfully used in many applications such as asset tracking and inventory management. Positioning indoors is increasingly becoming feasible both in terms of economic cost and technological possibilities. The vast increase of mobile devices has additionally created an increased need from the users - outdoor positioning is vastly becoming standardized on mobile devices through GPS, an indoor alternative is yet to become popular. Thus the field of indoor positioning is fairly non-mature field where exploratory studies are most commonly found.

In an outdoor environment, the Global Positioning System (GPS) works efficiently in positioning and targeting different types of entities. It has been used in many outdoor applications for localizing people, cars, as well as other objects. However, GPS lacks the same level of efficiency when used within indoor environments. This problem is due to the existence of obstacles that can weaken the signal of the GPS (e.g., building architecture, walls) where the existence of different equipment can cause a noise in the GPS transmitted signal. Pedersen [1] proposed a micro positioning strategy that should be implemented within the indoor environment in order to position and track objects. He stated that this strategy would work as a replacement for the GPS positioning system. In addition, Fhelelboom [2] found that a wireless local area network (WLAN) can be used within any indoor environment to position objects. An indoor positioning system (IPS) is a network of devices used to wirelessly locate objects or people inside a building. Positioning is an important problem to mobile robot. To measure an absolute position of a mobile robot, many methods using vision system or ultrasonic sensor system have been proposed. To use vision system huge calculation must be done in short time.

In this section, we focus on two types of positioning. The first type is positioning objects when there is an installed positioning system within the building and users are carrying tools such as RFID or any other equipment based on the wireless sensor network used in the system. We identify this type as a Fixed Indoor Positioning System. The second type is positioning users who have the equipment such as RFID when the building does not have the system installed within that giving environment. It is referenced as pedestrians positioning.

There are mainly four principles used in building positioning systems. These principles are Trilateration, Triangulation, Scene Analysis and Proximity [3]. The principle used can provide a faster calculation of the position. It can also provide a better accuracy depending on the system architecture too.

In Trilateration [4], we find the “x” and “y” coordinates of a point using the distance between this point and three other points with known coordinates. First, the three radiuses are computed. $$\begin{align} r_a^2 - r_b^2\\ r_a^2 - r_c^2 \end{align} $$ Then, using Equation (1 and 2) we subtract the radiuses to get the distance between each point and we simplify the equation in 2 to get the values of “x” and “y” of the required point.

The Triangulation principle [5] is similar to Trilateration, however, we use angles in order to get the distance d. Scene Analysis is another principle of positioning in which fingerprinting is used. A fingerprint is the signature that differentiates the scene from other ones. In other words, a fingerprint is the unique characteristic or collection of characteristics of the scene. It works by collecting some information from the scene and compare the collected information with the existing database match for each scene.

The proximity principle [6] is mainly used in Radio Frequency based systems. In this principle, we use a grid of antennas with fixed locations within the building. When a person carrying the mobile station is detected, the closest antenna is the one considered when calculating the object’s location. If the mobile is detected by more than one antenna, the antenna that receives the strongest signal is then considered when calculating the object’s location.

There are different attributes used to measure the location of an object. These attributes are either sent by the sensor or measured by the Base Station when the signal arrives. The attributes used are Received Signal Strength (RSS), Angle Of Arrival (AOA) and Time Of Arrival (TOA). All of the mentioned attributes are used by the Base Station to calculate the coordinates of the target object’s position. Moreover, selecting the attribute used within an indoor positioning system results in a different calculation of the position. These attributes have an effect on the resulting position calculation along with the type of wireless technology and the algorithm used within the system. TOA is the time taken by the signal to travel from the source sensor node to the Base Station. It is calculated by subtracting the time the signal left the source sensor node from the time the signal arrived at the Base Station. TDOA is Time Difference of Arrival. It is calculated by sending two types of signals. The difference between the Time of Arrival of the two signals is the TDOA. RSS is the Strength of the received signal. It is measured at the Base Station and used to calculate the coordinates. RSS can be affected by many factors such as obstacles and hindrances.

In this section we will discuss about the different indoor environments and the state of the art of indoor positioning systems. There are three technologies commonly used for fixed indoor location systems – infrared, ultrasonic, and RF. Infrared systems tend to rely on the user taking explicit actions to identify their presence; and RF-systems require sophisticated (and often cumbersome) aerials whereas ultrasonic offer a low cost solution which can operate without any user interaction. The disadvantages of an ultrasonic system are loss of signal due to obstruction; false signals due to reflections; and interference from high frequency sounds such as keys jangling, rustling paper etc.

These systems use infrared signals in order to transmit signals from sensor nodes to the Base Station (BS). One of the most well-known infrared positioning systems is the active badges developed by AT&T Cambridge. In this system, users carry an ID card equipped with infrared LED. The infrared LED sends a unique code every fifteen seconds. Furthermore, there are infrared sensors installed on a ceiling and if the IR badge is within six meters, the sensor is able to read the code. The BS receives the data from the IR sensors periodically. Finally, the BS is able to build a map of each badge location using the information retrieved from the sensors. Active Badges have mainly four commands, WITH, LOOK, NOTIFY, and HISTORY, each of which provides a different function. For example, WITH shows the badges that exists in the sensor area, LOOK is used to look for a badge by a sensor, NOTIFY is used to notify the BS when the badge is found and HISTORY shows the badges positions over a certain period of time.

Ultrasonic beacons are used more often than infrared technology. Ultrasonic systems provide more accurate positions for objects. Ultrasonic based systems are more accurate than Radio Frequency based systems as we will see in the discussion section. However, Ultrasonic systems need to have a fixed structure of the system. The Crickets system [8] developed by the Massachusetts Institute of Technology (MIT) is another well-known ultrasonic based indoor positioning system. The Cricket system has two types of nodes, beacons and listeners. Beacons’ locations are fixed and they are attached to the ceiling while the listeners are attached to the target objects and people. Beacons send periodic information to the BS containing its ID, range of coverage or physical space associated with it and its coordinates.

The mostly used wireless technology is Radio Frequency (RF). This is due to the low cost and the high range of coverage of the systems developed based on RF technology. Some RF based systems that are in the market are RADAR, Spot-On, LANDMARC, and UWB systems. LANDMARC system [9] is based on Radio Frequency signals and RFID tags. LANDMARC reduces the cost of using RFID readers by reducing the number of readers and using reference tags instead. These reference tags have a well-known location and they transmit to the readers the location of the target objects. LANDMARC is a very good system but its accuracy is 1-2 meters.

Pedestrian positioning, as mentioned earlier in the paper, happens when locating people who are carrying localization sensors while the building is not equipped with an indoor positioning system. In these types of systems Inertial Navigation Systems or dead reckoning are mostly used. Dead Reckoning is defined as navigation technique that starts from a well-known location. Then, adds the position changes in the coordinates of the starting point. It also adds the changes to the heading (direction), speed or distance. Moreover, Pedestrian Dead Reckoning (PDR) is defined as estimating the speed of movement and the heading or direction of movement.

An approach provided by Robertson [10], in which he suggests using foot mounted inertial sensors which provide the pedestrian dead reckoning. He provided a system called FootSlam. This system uses foot mounted Inertial Measurement Unit (IMU). Moreover, it builds a 2D map of the building without any prior knowledge of the structure of the building. The knowledge of all user intention helps with forming the map of the building and guiding the user through it. However, the more times places are visited within the building the better information or map built in regards of that place.

We notice that the active badge which is the only infrared based system provides an accuracy of centimeters which is better than many other systems. However, it only covers 5 m of range and its data rate or speed is 0.1 Hz. On the other hand, Ultrasound based indoor positioning systems provide an excellent accuracy compared to the other systems based on Radio Frequency.

This might be because of the structure of the ultrasound systems. However, ultrasound systems do not perform well when facing None Line of sight error. Active badges have the highest data rate of all systems while its cost is moderate since ultrasound needs a fixed structure within the building to operate efficiently. One can notice that the cost of Active badges is high because it is based on Infrared which is an expensive technology. We noticed Indoor Positioning is a huge area with many applications and many improvements to be carried. Researches within indoor positioning could be more useful if carried for pedestrians positioning since the accuracy reached is not as accurate as the accuracy reached in fixed indoor positioning.

[1] Solrun Furuholt Pedersen, ”Micro Positioning”. Master Thesis. ITEM NTNU, Jun 15, 2004.

[2] Fhelelboom, Zuher. "Equipment tracking and security systems for hospitals". Master Thesis Universiti Teknologi Malaysia. May, 2007.

[3] G. Mao, B. Fidan, and B. Anderson, “Wireless sensor network localization techniques,” Computer Networks, vol. 51, no. 10, pp. 2529– 2553,July, 2007

[4] D. Zhang, F. Xia, Z. Yang, L. Yao, W. Zhao, Localization Technologies for Indoor Human Tracking, in: The Fifth International Conference on Future Information Technology (FutureTech), Busan, Korea, 2010. pp. 1–6

[5] Isaac Amundson and Xenofon D. Koutsoukos, “A Survey on Localization for Mobile Wireless Sensor Networks”, R. Fuller and X.D.Koutsoukos (Eds.): MELT 2009, LNCS 5801, 2009, Pages: 235- 254

[6] C. di Flora, M. Ficco, S. Russo, and V. Vecchio, ”Indoor and outdoor location based services for portable wireless devices”, Proc. 25th IEEE International Conference on Distributed Computing Systems Workshops,2005.

[7]. Michael Popa, Junaid Ansari, Janne Riihij¨arvi, and Petri M¨ah¨onen. 2008. Combining Cricket System and Inertial Navigationfor Indoor Human Tracking. WCNC proceedings.

[8]. Priyantha, N. B; The cricket indoor location system: PhDThesis, Massachusetts Institute of Technology. 199 p, June2005

[9] Lionel M.NI, Yunhao Liu, Iu Cho Lau, Abhıshek P. Patil; LANDMARC: Indoor Location Sensing Using Active RFID

[10]. Robertson, P., Angermann, M, Krach, B., Simultaneous Localization and Mapping for Pedestrians using only Foot-Mounted Inertial Sensors. In Proc. UbiComp 2009, ACM (2009) 93-96.