On Location Estimation Technique Based of the Time of Flight in Low-power Wireless Systems

10.1515/msr-2015-0009 MEASUREMENT SCIENCE REVIEW, Volume 15, No. 2, 2015 On Location Estimation Technique Based of the Time of Flight in Low-power Wireless Systems Miroslav Botta, Milan Simek, Ondrej Krajsa, Vladimir Cervenka, Tamas Pal Brno University of Technology, Faculty of Electrical Engineering and Communication, Department of Telecommunications [email protected].cz, [email protected].cz, [email protected].cz, cerv[email protected].cz, [email protected].cz This study deals with the distance estimation issue in low-power wireless systems being usually used for sensor networking and interconnecting the Internet of Things. There is an effort to locate or track these sensor entities for different needs the radio signal time of flight principle from the theoretical and practical side of application research is evaluated. Since these sensor devices are mainly targeted for low power consumption appliances, there is always need for optimization of any aspects needed for regular sensor operation. For the distance estimation we benefit from IEEE 802.15.4a technology, which offers the precise ranging capabilities. There is no need for additional hardware to be used for the ranging task and all fundamental measurements are acquired within the 15.4a standard compliant hardware in the real environment. The proposed work examines the problems and the solutions for implementation of distance estimation algorithms for WSN devices. The main contribution of the article is seen in this real testbed evaluation of the ranging technology. Keywords: Distance Estimation, IEEE 802.15.4a, Localization, ToF, UWB. 1. INTRODUCTION LOCALIZATION and tracking have many advantages and useful applications in the global point of view. By means of wireless sensor networks there is an effort to localize or track low power nodes usually composed of processor, some sensors and radio transceiver unit. In these days, the distance estimation functionality in small sized (indoor/outdoor) environments from a general viewpoint is a popular topic. It can be used for the various types of asset tracking, localization purposes and routing algorithms. Localization techniques require high efficient approach with respect to the equilibrium of the implementation price and the needed resources. The resources are defined by all hardware and processing time used for the purpose of the estimation which can be all suited at one node or at the whole distributed system. Mostly the distance estimation feature implemented in WSN (Wireless Sensor Network) is restricted by the resources, mainly by the low cost/computational hardware solutions. The different types of applications require different hardware capabilities and various wireless communication standards - some "over the counter" solutions, others still under development. Our point of view is aimed at the wireless standards based on the IEEE 802.15 family protocols. In this case the 15.4ahas interesting features by means of ranging, because it standardize basic techniques for distance estimation between two wireless nodes based on the radio signal time of flight. The rest of the paper is organized as follows: In the next section 2, there is a brief description of our other related work and also some additional research papers that are trying to describe and solve the proposed issue. Section 3 gives us an overview of the used standard IEEE 802.15.4awith respect to the ranging capability. Section 4 describes two fundamental methods used for the ToF (Time of Flight) based distance estimation. At the end of the work the main section 5 is about testbed evaluation of distance estimation based on the time of arrival, where the two-way ranging method is included. 2. RELATED WORK The proposed work was made as a part study of a study to realize possibilities and methods of distance estimation in wireless sensor networks. First, we conducted research of RSS (Received Signal Strength) based estimation methods in [1], respectively we evaluated the radio channel uncertainty for the ranging purposes. In this work the uncertainty of radio channel was evaluated with the special hardware for the precise measurements and also with the low cost wireless nodes. Our other related work [2] was established on the basis of previous research dealing with observed radio channel uncertainty using the dynamic calibration method, where we achieved relative estimation errors less than 10 % but with dense distribution of wireless nodes in the system. This article also extends research described in [3] for IEEE 802.15.4a PHY (Physical Layer) real evaluation using the new RF transceiver which is intended to widely utilize in wireless sensor networks and precise distance estimation. As an overview of RTLS (real time location systems) and an introduction to the distance estimation based within ToF the [4] and [5] have been used. In the [6] authors used two IEEE 802.15.4 compliant transceivers combined with dedicated FPGA (FieldProgrammable Gate Array) based controller for precise time measurements. One transceiver was used for distance measurement and the other for precise time synchronization. They achieved the 2.14 meter location estimation error in the area of 12x22 meters inside the building. There is also work [7] with a very similar theme as the one 58 MEASUREMENT SCIENCE REVIEW, Volume 15, No. 2, 2015 proposed in our article, where the authors achieved the average error of 1.2 meter in outer space. They were using own TDMA/CSMA hybrid access method instead of ALOHA. In these time slots they were pre-allocating resources needed for anchor searching and final ranging purposes. 3. BRIEF DESCRIPTION OF THE IEEE 802.15.4A-STD The IEEE 802.15.4a(IEEE Std 802.15.4a−2007) was developed by the IEEE 802.15 Low Rate Alternative PHY Task Group (TG4a working group) [8]. It is an amendment to the original IEEE 802.15.4 standard. The amendment brings the UWB (Ultra Wide Band) physical layer which provides ranging capability and communication with high throughput, scalability to data rates with robust performance and longer range than existing 802.15.4 compliant devices. It enhances the wireless communication medium to the UWB frequencies, another modulation methods and techniques for accessing the wireless medium. The 15.4aspecifies alternate physical layers which are UWB-PHY using DSSS (Direct Sequence Spread Spectrum) at frequencies shown in Figure 1 in socalled low band 3.1−5 GHz, high band 6 −10.6 GHz, sub-gigahertz 250 − 750 MHz and using the CSS (Chirp Spread Spectrum) at 2.4 GHz frequency band. 250 sub band 3244 3744 4244 4744 0 1 2 3 4 (1331) 5 6 6240 6740 7240 7740 8240 8740 9240 9740 7(1081) 8 9 10 11(1331) 12 13 14 15 (1355) 5949 10240 f [MHz] low band high band 750 1250 1750 2250 2750 channels of 802.15.4-2006 2405-2480 868/915 250 sub band 3244 3744 4244 4744 0 1 2 3 4 (1331) 5 6 6240 6740 7240 7740 8240 8740 9240 9740 7(1081) 8 9 10 11(1331) 12 13 14 15 (1355) 5949 10240 f [MHz] low band high band 750 1250 1750 2250 2750 channels of 802.15.4-2006 2405-2480 868/915 Fig. 1: The IEEE 802.15.4a-std bandwidth [3] 4. DISTANCE ESTIMATION Distance estimation solutions (localization systems) are supposed to be implemented in small sized, low power and low cost devices called tags. At the deployment stage, these tags will be attached to the monitored object (people or things), for tracking and controlling the life functions of people in a factory with high risk environment or in hospitals. Also the equipment tracking inside the buildings or warehouses is a possible application. Present localization systems suffer from many factors like the size of tags, accuracy, energy consumption and price. There is still place for the innovative solutions that can deal with all of these circumstances. This work examines distance estimation based on the time of flight principle. At small distances the electromagnetic waves travel only a few nanoseconds and within this time interval, we can estimate the distance between transmitter and receiver (one hop communication). This raises a question - Are there any low cost solutions for measuring such small times with sufficient precision? This subject will be experimentally acquired and also explained later in the paper. 4.1. Real Time Localization Systems Under the term real time localization system the compound of hardware and software entities with which can be continuously determined the location of given asset can be imagined. When the ToF approach is considered, the assumption of precise time measurement is an important factor. In the simplest scenario we can send the signal at time TSend and receive it at other side at time TReceive. From these values we can estimate the time of flight (ToF) as TReceive −TSend. Distance between two nodes then equals the ToF multiplied by the speed of light in air (298,925,574 m/s). In this case, there is the need for exact time synchronization with the same system timers between the two considered nodes. In wireless sensor network this is a hard task due to hardware and resource limitations. In the next section 4.2 there is a brief proposal of the methods initially published in [9] that can work without the exact time synchronization between the devices. 4.2. Ranging method The most fundamental method of ToF distance estimation is TWR (Two Way Ranging). An advantage of this method is that there is no need for time synchronization between the devices. A basic principle of TWR shown in Figure 2 uses only two messages for whole distance estimation process, but as it is described in [9] and also simulated in [10] it suffers from oscillator frequency drift on both sides of communication chain since the frequency drift introduces error in measurement of time events. It means that the single clock (tick) time can have different lengths on both sides and it is reflected in the variable packet process times and also in the captured precise time information. Even by using crystals with tolerance of 2 ppm, the distance estimation error is more than 1,5 meter. Improving this method with additional messages gives us the SDS-TWR (Symmetrical Double-Sided Two Way Ranging) method, which deals also with incompatibility between oscillator frequencies at the both sides. The principle of this method is also shown in Figure 2. The SDS-TWR method uses three types of message. The poll message initiated by the tag device (the asset) and then the response message sent by the anchor node (fixed with known position) follows. Both messages are intended for measuring the individual messaging timestamps. The last one is the final message sent by the tag node with embedded captured timestamps (with Poll message TX,Response message RX and predicted Final message TX timestamps). Timestamps marked as TSTand TSArepresent time information of a packet sent from the "tag" and "anchor", analogously the TRTand TRTrepresent receive times. The TRTDTshown in Figure 2 and expressed in Equations (1) and (2) is the time of round trip delay measured by the "tag". 59 MEASUREMENT SCIENCE REVIEW, Volume 15, No. 2, 2015 Final message Response message Poll message SPI-to-USB Adapter Ranging Tag Anchor T RTD T A RTD T A proc T T proc T T R T A R T A S T T S T AF R T TF S T Response message Poll message Tag Anchor T RTD T A proc T T R T A R T A S T T S T TWR SDS-TWR Fig. 2: Principle of fundamental two-way ranging and its improved symmetrical double-sided two way ranging method. TRTDT=TRA −TST+TSA −TRA+TRT −TSA(1) TRTDT=TRT −TST(2) The TRTDAexpressed in Equations (3) and (4) is the time of round trip delay measured by the "anchor". TRTDA=TRT −TSA+TSTF −TRT+TRAF −TSTF (3) TRTDA=TRAF −TSA(4) TprocA=TSA −TRA(5) TprocT=TSTF −TRT(6) Times needed for processing the ranging packet TprocAand TprocTincluded in Equations (5) and (6) has to be also extracted from the TRTDAand TRTDTvalues and divided by two, because the only one-way time of flight is desired. At the end the average value of TRTDAand TRTDThas to be computed. Using these information the "anchor" node can resolve the one way ToF (time of flight) between devices according to the Equation (7). ToF = (TRTDT −TprocA)+(TRTDA −TprocT) 2 2(7) 5. EVALUATION AND MEASUREMENT Two types of the UWB devices were needed for measurement. One that acted as "anchor" node, usually with fixed known position and the "tag" node which acted as a mobile node. The "tag" is driven by the ARM micro-controller that periodically initiates the message exchange for distance measurement. The "anchor" has the same functionality and hardware equipment as a "tag", but for our purposes the communication between radio chip and micro-controller was deactivated and the radio chip was directly connected to the computer via SPI (Serial Peripheral Interface) with SPI to USB converter. The "tag" every time initiates message exchange by polling the "anchor" node. For evaluation purpose the communication protocol is as simple as possible, where "tag" knows all of the "anchor" nodes, respectively their addresses, and every time it is trying to poll one of them, even when they are not in a range. The "anchor" nodes acts only as listeners to the "tag". Whole message exchange is shown in Figure 2. The beginning of the coordinate system is in the bottom of the floor plan shown in Figure 4, the 20 samples (whole SDS-TWR message exchange process) were measured at every point. 5.1. Line of sight (LOS) measurement Measurement was done in a hall (50 meters long) shown in Figure 5 with the office and laboratory entrances. Initial step for measurement was 0.5 meter and then 1 meter. Both devices were 1 meter high above the floor. At every point the 20 samples were measured. 0 2 4 6 8 10 12 14 16 18 0 0,5 1 1,5 2 2,5 3 04812 16 20 24 28 32 36 40 44 δrelat [%]→ δabs [m]→ dreal [m]→ Fig. 3: Graph of distance estimation accuracy in indoor environment with distance changed from 0 to 46 meters A graph in Figure 3 shows all of these measurements with line of sight (LOS) communication distance up to 46 meters inside the building. There is also a graph of the relative error (blue line) which reaches the maximum value of about 12%. In most cases the relative error in accuracy of measured distance is under 1%. This kind of distance estimation proves that it has enough precision for line of sight appliances where the accuracy is the main condition. 5.2. Non line of sight (NLOS) measurement The presented measurements were conducted inside the building with strong multipath environment as shown in Figure 4. For performance analysis of the SDS-TWR method the five reference positions (marked with numbers 32, 33, 34, 51, 53) inside the offices were used. Every measurement was carried out on the marked points (cross marker 1-12) suited in the 60 MEASUREMENT SCIENCE REVIEW, Volume 15, No. 2, 2015 hall between the offices, so we could evaluate different NLOS (non line-of-sight) multipath signal propagation. Fig. 4: Floorplan of measured environment 0,170 0,299 0,779 0,904 1,160 0,127 1,565 1,797 0,945 1,603 1,793 0,978 2,025 1,545 2,100 0,961 0,0 0,5 1,0 1,5 2,0 2,5 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 δabs [m]→ dreal [m]→ Fig. 5: Worst case of distance estimation measurement Figure 5 shows the worst case measurements in the whole area consolidated by all nodes, so we can see maximum possible error introduced in this environment using the UWB devices and then predict or deal with this occurrences. The graphs in Figure 6 introduce the detailed behavior of every node position shown in the floor-plan in Figure 4. Maximal range, where the distance could be estimated (without significant message loss) was between 13 and 19 meters in this kind of environment. The blue lines represent the absolute error of distance estimation (δabs) respectively the difference between the real and the estimated distance. All of the ranging errors have positive value. Red lines are showing the relative error (δrelat ), respectively the absolute error in proportion with real distance, which is the worst for the node with ID:32 and as we can see from the Figure 6, there was also the smallest achieved range, because of the dense occurrence of metal objects like whiteboards, desktop computers and server racks. 4 5 6 7 8 9 10 11 12 13 0 0.5 1 1.5 2 2.5 Node ID: 32 δ abs [m] → d real [m] → 4 6 8 10 12 14 16 18 0 0.5 1 1.5 2 2.5 Node ID: 33 δ abs [m] → d real [m] → 4 6 8 10 12 14 16 18 20 22 0 0.5 1 1.5 2 2.5 Node ID: 34 δ abs [m] → d real [m] → 4 6 8 10 12 14 16 18 0 0.5 1 1.5 2 2.5 Node ID: 51 δ abs [m] → d real [m] → 4 6 8 10 12 14 16 18 20 0 0.5 1 1.5 2 2.5 Node ID: 53 δ abs [m] → d real [m] → 4 5 6 7 8 9 10 11 12 13 0 5 10 15 20 25 δ relat [%] → 4 6 8 10 12 14 16 18 0 5 10 15 20 25 δ relat [%] → 4 6 8 10 12 14 16 18 20 22 0 5 10 15 20 25 δ relat [%] → 4 6 8 10 12 14 16 18 0 5 10 15 20 25 δ relat [%] → 4 6 8 10 12 14 16 18 20 0 5 10 15 20 25 δ relat [%] → Fig. 6: Graph of distance estimation accuracy in indoor environment according to the Figure 4 61 MEASUREMENT SCIENCE REVIEW, Volume 15, No. 2, 2015 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0 2 4 6 8 10 12 14 16 18 20 22 Probability [-]→ δrelat [%]→ NLOS LOS Fig. 7: Distribution of relative ranging error under LOS and NLOS conditions The Figure 7 shows distribution of the relative ranging error for LOS and NLOS conditions. This figure is clearly telling us that UWB ranging is far more suitable for open spaces, without any obstacles. High precision (1 % relative ranging error) can be achieved with ToF method (under LOS conditions), but on the other hand it is not suitable for short distances (less than 2 meters) as we can see in Figure 3. During experiment lot of electronic equipment and metal whiteboards were presented in surroundings, which the most likely caused the introduction of distance estimation error. Since the measurements were done in NLOS conditions and with different node distribution in area (Figure 4), various behavior and maximal communication range for all "anchor" nodes can be seen in the graphs. In comparison with the similar experiment published in [11], we observed notable ranging errors mainly in case the signal was passing through the many obstacles such as metal objects, walls etc. As it was already described in the subsection 4.2 a minimum of three messages are needed for SDSTWR distance estimation process. If there is any packet loss presented on the medium, the whole process has to be repeated. This limiting condition also determines the maximal possible reachable range between the devices. 6. CONCLUSION AND FUTURE WORK The methods for distance estimation that can be used in indoor environment are very up-to-date topics. They had a wide scope of the applications such as monitoring or surveillance of human beings or objects. The proposed testbed evaluation was mainly conducted for estimation of the properties and possibilities of precise indoor location system (distances up to 50 m). In this work we had evaluated the method using time of flight of UWB radio signal. In most cases the relative error in accuracy of measured distance in tested environment with strong NLOS conditions was under 15 %. This kind of distance estimation proves that it has enough precision for the applications where the accuracy is a main condition. Therefore, the SDS-TWR method respectively method based on the ToF results in significant improvements in distance estimation accuracy in comparison with others, for example RSSI based. We can conclude that distance estimation in NLOS conditions are highly dependent on the type and a number of obstacles in the way. Since the radio signal is reflected by the various types of surfaces in the objects, the important role in the process of distance estimation is the ability of the receiver to lock to the direct path signal rather than to the reflected signal. Future work will be aimed at the implementation of location and tracking algorithms that can improve accuracy using the ToF measurements. There will be also an effort to implement our algorithms proposed in [12] to place in energy efficiency and optimization of communication cost in the wireless system. 7. ACKNOWLEDGEMENT Research described in this paper was financed by the National Sustainability Program under grant LO1401. For the research, infrastructure of the SIX Center was used. REFERENCES [1] Moravek, P., Komosny, D., Simek, M., Jelinek, M., Girbau, D., Lazaro, A. (2013). Investigation of radio channel uncertainty in distance estimation in wireless sensor networks. Telecommunication Systems 52(3), 1549– 1558. [2] Botta, M., Simek, M. (2013). Adaptive Distance Estimation Based on RSSI in 802.15.4 Network. Radioengineering. 22(4), 1162–1168. [3] Simek, M., Botta, M., Mraz, L., Denkovski, D. (2013). Evaluation of phy layer throughput of ultra wide band ieee 802.15.4a technology. In: Telecommunications and Signal Processing (TSP), 2013 36th International Conference on. pp. 105–110. [4] Nanotron Technologies GmbH (2007). Real Time Location Systems (RTLS). [5] Gaffney, B. Considerations and challenges in real time locating systems design. [6] Cho, H., Jung, Y., Choi, H., Jang, H., Son, S., Baek, Y. (2008). Real time locating system for wireless networks using ieee 802.15.4 radio. In: Sensor, Mesh and Ad Hoc Communications and Networks, 2008. SECON ’08. 5th Annual IEEE Communications Society Conference on. pp. 578–580. [7] Jie, H., Qin, W., Fan, Y. (2009). A mass-target real time localization system. In: Wireless Communications Signal Processing, 2009. WCSP 2009. International Conference on. pp. 1–5. [8] IEEE working group (2003). IEEE 802.15 WPAN Low Rate Alternative PHY Task Group 4a (TG4a). 62 MEASUREMENT SCIENCE REVIEW, Volume 15, No. 2, 2015 [9] IEEE Std 802.15.4aTM-2007 (2007). Amendment 1: Add Alternate PHYs. In: Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (WPANs). p. 203. [10] Zhen, B., Li, H.-B., Kohno, R. (2006). Uwb ranging and crystal offset. In: Vehicular Technology Conference, 2006. VTC 2006-Spring. IEEE 63rd, Vol. 3. pp. 1445– 1449. [11] Ye, T., Walsh, M., Haigh, P., Barton, J., Mathewson, A., O’Flynn, B. (2011). Experimental impulse radio ieee 802.15.4a uwb based wireless sensor localization technology: Characterization, reliability and ranging. ISSC 2011, 22nd IET Irish Signals and Systems Conference, Dublin, Ireland. [12] Simek, M., Moravek, P., Komosny, D., Dusik, M. (2012). Distributed Recognition of Reference Nodes for Wireless Sensor Network Localization. Radioengineering. 10(4), 302–312. Received December 4, 2014. Accepted April 20, 2015. 63