from the Chinese Academy of Surveying and Mapping

Two New Algorithms for Indoor Wireless

Positioning System (WPS)

Yufei Wang Xiaodong Jia Chris Rizos

School of Surveying and Spatial Information Systems

University of New South Wales, Sydney, Australia

BIOGRAPHY

Chris Rizos is a Professor & Head of the School of Surveying & Spatial Information Systems (SIS), University of New South Wales (UNSW). He is president of Commission 4 'Positioning & Applications' of the International Association of Geodesy, a member of the Governing Board of the International GPS Service, and a member of the Australian GNSS Coordination Committee. Xiaodong Jia, PhD student in the School of Surveying and SIS, UNSW, under the supervision of Prof. Chris Rizos. He has a M.E. of Computer and Electrical & Telecommunication Engineering from the University of Wollongong (2002).His research interests include the integration of GPS technology with mobile communications and GPS signal propagation in difficult environments, such as under foliage, inside buildings, etc. Yufei Wang, PhD student in the School of Surveying and SIS, UNSW, under the supervision of Prof. Chris Rizos. He has a B.E. in Geodesy from the Wuhan Technical University of Surveying and Mapping (1992), M.E in GPS from the Chinese Academy of Surveying and Mapping (1997), and three years research experience in Internet GIS, distributed GIS, RS image compression, and database design at the National Engineering Research Center for Geo-informatics, Institute of Remote Sensing Applications, Chinese Academy of Sciences. His main research interests include LBS, integration of GPS&GIS&RS, Wireless Positioning, software development and methodology, distributed computing, GRID and AGENT computing, RS image DB and compression, Geospatial Information interoperability, etc. ABSTRACT

WPS is a 100% pure software-based indoor positioning system which uses the signal strength of WLAN (Wireless Local Area Networks) infrastructure transmission from/to WLAN access points to determine the position of the user equipped with mobile computing devices such as Personal Digital Assistants (PDA), laptop computers and so on.

In a previous paper(Wang, 2003),the authors gave a detailed description of their WPS system, including hardware, software and system architecture. Meanwhile, based on the WPS test bed, several basic experiments were conducted: (a) to determine the stability of the 2.4GHz WLAN infrastructure radio signal strength, (b) reliability experiment of the 2.4 GHz WLAN infrastructure radio Ssgnal, (c) verification of the empirical model and the effect of Geometry of Distribution (GOD), and (d) wall penetration loss experiment. From the results of these experiments and data analysis it was concluded that a wireless access point-based indoor positioning system is feasible. Experimental results show a positioning accuracy of 1-3m.

In order to improve the stability and reliability of the WPS system the authors propose two new methods. Thedifferential approach requires setting up a fixed differential correction base station in the same environment to compensate for the influence of susceptible radio frequency on the user device. In addition, from an analysis of positioning measurements, the authors determined that, to some extent, signal strength at one fixed position is having a trend of weakness, which means that the signal strength value always weakens when it is affected by a different environment factor. So, based on this observation, the authors propose a minimal signal strength value algorithm.

1. INTRODUCTION

An indoor Wireless Positioning System (WPS) or Wireless Access Point-based indoor positioning system is becoming an increasingly popular R&D focus with the availability of the IEEE 802.11 standard and the relatively low cost equipment (Seidel, 1992; Aguirre, 1994; Small, 2000; Bahl, 2003; Zhou, 2003). For example, since the authors published their first paper on a n indoor wireless positioning system (WPS) based on wireless local area network infrastructure (Wang, 2003), more than ten enquiries about the details of the system have been received from France, Germany, Korea, Malaysia, Portugal, Singapore, Spain, Thailand, and USA. Most questions were: What is the core of the development of the WPS? What is the architecture of the WPS system? What is the accuracy of indoor positioning? Is it possible to introduce a WPS into the location-based system? Someone even asked what analysis tools are used to process the collected data. In particular, PEDAGOG, a consultant company for US army training facilities, has even tried to put the WPS system into practice, for training purposes at Fort Polk in November 2003. In addition, the leader of VEST, a virtual environment project of the Escola Superior de Tecnologia de Setúbal

and an integrated system of 3D model virtual reality,community interaction, telecommunication and positioning system etc, also expressed great interest to adapt the WPS into VEST.

In order to improve the stability and reliability of the WPS,in this paper the authors introduce the differential approach, by setting up fixed differential correction base station in the same environment to compensate for the influence of susceptible RF on the user station. In addition,through the analysis of the signal strength, it is found that the signal strength of one fixed position is experiencing a trend of weakness. So based on this observation, the authors also propose a minimal signal strength value algorithm. This paper is organised as follows: Section 2reviews the previous work and basic experiments, Section 3 describes the differential theory and the algorithm,

Section 4 presents the differential experiments and data analysis, while Section 5 introduces the minimal signal strength value algorithm, and Section 6 concludes this paper.

2. PREVIOUS WORK AND BASIC EXPERIMENTS 2.1 Experimental Test Bed, WLAN Infrastructure and Hardware

A test bed was established on the top floor of the 6-storey Electrical Engineering Building at UNSW. The layout of this floor is shown in Figure 1. It has dimensions of 17.5m by 84m with about 40 different rooms, including classrooms, computer labs, offices, storerooms, tearoom and two long corridors.

Figure 1. Test bed for the Wireless Positioning System (WPS) with location of the WLAN access points (AP)

Figure 2. WPS hardware

Six WX-1590 SparkLAN 11 Mbps WLAN Wireless Multi-Mode Access Points (AP), operating as the wireless signal transmitters and base stations, were installed at the locations indicated by stars in Figure 1. The rovers were an Acer eXtensa 710T laptop computer (Windows 2000operating system) and a Compaq iPAQ 3970 (Pocket PC 2002 operating system) with Lucent Technology Wi-Fi Orinoco Wireless Golden Card (Figure 2). These wireless network cards can detect and synchronise the signal strength (SS ) from the six wireless Access Points. The 802.11 b (‘WiFi’) Telecommunication Protocol is used in this system.

2.2 Software Implementation

Generally speaking, the low-level, or core, of the WPS involves the development of a hardware driver for the Orinoco Wireless Gold Card interface, and then based on this, a series of signal detecting, positioning, coordinate

transformation and telecommunication algorithms need to be developed (although all of these are located in the Application Layer).

2.2.1 Core Architecture

As described above, the core part of WPS system is the wireless network card driver, for the Windows operating system, which has a 3-layer driver architecture (Figure 3)Moreover, every device is serviced by a chain of drivers typically called as a driver stack . Each driver in the stack isolates some hardware-dependent features from the drivers above it.

Unfortunately, in the Windows operating system, we cannot find the required functionality to extract the MAC address of the AP, Signal Strength (SS) information, Noise ,Signal-To-Noise Ratio (SNR), transmitter channel of AP,basic service set identifier (BSSID), etc., from the wireless network card. Hence it is necessary to extend the Windows’s Network Device interface Specification or NDIS to provide user applications with the ability of accessing particular information from the wireless network card. Therefore, in a real-time implementation, we adopted the DeviceIoControl , the WIN32 API provided by Windows OS, to detect the NDIS hardware sensor and read the feature values in NDIS wireless hardware storage.

AP1

AP2

AP3

AP4

AP5

AP6

Access Point Wireless Card iPAQ 3970

Figure 3: Core architecture of WPS

NDIS describes the interface by which one or more Network Interface Card (NIC) drivers communicate with one or more underlying network interface cards, overlying protocol drivers, and the operating system. NDIS also defines a fully abstracted environment for NIC driver development. For every external function that a NIC driver needs to perform, it can rely on NDIS routines to perform the operation. This includes the entire range of tasks performed by a NIC driver, from communicating with protocol drivers, to registering and intercepting NIC hardware interrupts, communicating with underlying NICs by manipulating registers, port I/O, and so forth. Therefore, NIC drivers can be written entirely in platform-independent high-level languages such as C. These drivers can then be recompiled with a system-compatible compiler to run in any NDIS environment.

NDIS on Windows 2000:To provide abstraction and portability at the level described above, Windows 2000 gives an NDIS export library referred to here as the NDIS library or NDIS. All interactions between the NIC driver and protocol drivers, NIC driver and the operating system, and NIC driver and the network adapters that it controls, are through calls to NDIS functions. NDIS is packaged in an export library as a set of functions, with emphasis on in-line macros for maximum performance. All NDIS drivers, including highest-level NDIS protocol drivers, intermediate NDIS drivers and NIC drivers, link with this library. When called, a NDIS function calls an associated function in a higher-level driver, an intermediate NDIS driver, a NIC driver, the operating system, or else performs an internal-to-NDIS local action.

NDIS on Windows CE:The NDIS implementation on Windows CE 3.0 is a subset of the NDIS 4.0 implementation used on Windows 2000. The complete NDIS specification supports several types of network drivers, but Windows CE version 2.0 (and later) only support writing NDIS Mini-port drivers, not monolithic or full Network Interface Card (NIC) drivers. For NDIS Mini-port drivers, Windows CE is a source code compatible with Windows 2000, supporting identical NDIS APIs barring a few exceptions. Fortunately, NDIS 5 will support all 802.11 wireless object identifiers (OIDs) in CE’s next version, Windows https://www.sodocs.net/doc/6615144928.html,. So, at that time, it will become easier to extract the required information directly from the wireless network card.

2.2.2 Application Software Architecture

Apart from the extension of the functionality in the NDIS, the authors have developed a complete indoors WPS software package as well, including roving client side software for the iPAQ 3970 and Acer Laptop computer, and an indoor tracking-monitoring program on the server side. The WPS laptop version software was developed using Borland Delphi 7. The iPAQ version was developed using Embedded Visual C++ 3.0. In these experiments, the laptop was used as the roving client. Figure 5 shows the graphical user interface (GUI) of the application for the mobile client.

According to the system demands, and following the principle of Internet software, a three-tier design was implemented to demonstrate this WPS system (Figure 4): (1) wireless positioning and tracking client side, (2) tracking and monitoring server side, and (3) remote monitoring client side.

Figure 4: WPS application software architecture

User layer

Kernel layer

Hardware layer

AP AP

AP

Figure 5. Mobile client’s GUI interface for the laptop computer 3. THE DIFFERENTIAL PRINCIPLE

3.1 The Propagation Error of Indoor Wireless Waves

In an ideal environment if wireless radio waves are transmitted from a point, they spread and propagate as spherical wave fronts. The wave fronts travel in a direction perpendicular to the wave front, as shown in Figure 6.

Figure 6. Radio wave propagation However, in reality, whether indoors or outdoors, the mechanisms behind radio wave propagation are diverse and generally can be attributed to reflection, diffraction, and scattering (Blake, 1986; Durgin, 1998). At the same time, in an indoor environment, conditions are much more variable as the distance covered is much smaller, and the variability of the environment is much greater for a smaller range of transmitter and receiver separation distances. For example, the transmitted signal generally reaches the receiver via multiple paths, so multipath causes fluctuations in the received signal envelope and phase, and the signal components arriving from indirect and direct paths combine to produce a distorted version of the transmitted signal. Multipath within buildings is strongly influenced by the layout of the building, the construction materials, and the building type. Some artificial factors such as whether interior doors are open or closed inside the building; where antennas are mounted,how many people are in the building and so on, also influence multipath.

Based on this consideration, a differential method is proposed to mitigate the errors that are common to all receivers close together.3.2 The Differential Concept

The differential method has been applied to many navigation and positioning systems. It relies on the assumption that certain types of errors, which can degrade the performance and accuracy of a system, are common to all system components. If these errors can be calculated at a point, or those errors linearly correlated across different datasets, they can be eliminated or reduced by differencing (Grant et al, 1990). Hence the differential method involves the removal of correlated systematic errors between reference and roving components. Obviously, the main assumption behind differential techniques is that they improve the overall system performance. To be able to define errors in any navigation system, the correct value of the observation either must be known or be calculable. For example, the errors inherent in GPS are visible to the user only as an error in the position, or the position uncertainty. These can only be quantified if the user actually knows where he really is. Prior knowledge of the position will allow these errors to be identified, and also allow them to be defined and possibly mitigated.

It is therefore apparent that in a differential system at least one receiver or reference station must know where it is, i.e. at a known reference point. This may have an immediate cost implication.

3.3 System Design of Differential WPS

Based on the basic differential concept, we designed a differential WPS system (Figure 7). In contrast with the previous WPS, in the DWPS system we introduce a critical component – a desktop computer with wireless card, and the same software and hardware configuration used in the mobile receiver. This desktop computer,

receiving the real-time signal strength from the same access point, is called a reference station.

Naturally, the position of this reference station should be known. The differential formula involving one access point is:

mean desktop obs desktop desktop SS SS SS ???=Δ (1)desktop obs laptop laptop SS SS DSS Δ?=? (2)

where

desktop SS Δ

is the differential correction value of

the desktop or reference station,

obs desktop SS ? is the S S

observation value of the reference station, mean desktop SS ?is the known signal strength of this position relative to a fixed access point, laptop DSS is the applied measurements after differential correction between mobile and reference station, and obs laptop SS ? is the observation value of mobile station.

4. DIFFERENTIAL EXPERIMENTS AND DATA ANALYSIS

In order to test the validity of the differential method in the WPS system, a series of experiments including zero-baseline experiment, short-range, medium-range and long-range experiments have been carried out, and the corresponding results are presented in the following sub-sections.

4.1 Zero-Baseline Experiment

First, we conducted a simple but important zero-baseline wireless signal strength experiment to evaluate the effectiveness of the differential WPS algorithm,According to the differential theory, there is an

assumption that certain types of errors are common to all system components. On the other hand, from a zero-baseline experiment we also can test the consistency of hardware, such as the desktop computer with laptop computer, and the two different wireless network cards,because this is the hardware prerequisite to applying the differential algorithm in a positioning system.

Therefore in practice, we put the laptop computer and desktop computer together as close as possible, at the same time facing one access point (Figure 8). The laptop and desktop equipped with the same software and hardware are put together, and they receive the signal from the same access point. A long time data collection obtained 7013 records in 24 hrs.

Figure 8. Zero-baseline test of two wireless signal

strength receivers

Figure 9. Zero-baseline test result

Figure 10. Zero-baseline differential result

Mean (dBm)Std.Deviation

Desktop Station 60.84 2.05Laptop Station 60.91 1.78Laptop after D Correction 60.91 1.15

Table 1. The statistic result of Zero-baseline experiment

Access Point

AP 1

AP 2

AP 3

Mobile Wireless Receiver

Desktop Receiver &Reference Station

R2ref

R3ref

From Zero-baseline test result (See figure 9), different test result (See figure 10) and differential statistic result (See Table 1), it is shown that with the equations (1) and (2), more stable signal strength is observable after the differential process. The standard deviation has improved significantly from 1.78 to 1.15, which means the environment relativity is very tight under the zero-baseline condition. So, as suggested above, this forms the basis for introduction of differential method into indoor wireless positioning system. In addition, this also verifies the consistency of hardware equipment.

4.2 Short-Baseline (up to 5 metres) Experiment In the short-range experiment, a laptop computer and desktop computer were located at two different positions up to 5m apart. 12500 records were collected for the two computers. The results are presented in Figures 11, 12 and

Table 2.

Figure 11. Short-range-baseline test result

Figure 12. Short-baseline differential result

Mean (dBm)Std.Deviation

Desktop Station 51.64

1.79Laptop Station 46.31 1.92Laptop after D Correction 46.31 1.42Table

2. The statistic result of short-baseline experiment From the short-baseline test result (Figure 11), differential test result (Figure 12) and the differential statistic results

(Table 2), it can be concluded that differential method is very successful, because after differential corrections the signal strength standard deviation of the mobile receiver has reduced from 1.92m to 1.42m.

4. 3 Medium-Baseline (up to 10 metres) Experiment In the medium-baseline experiment, the distance between the laptop computer and desktop computer has been extended to 10 metres. After many hours data collection,2500 records were obtained and the results are presented in Figures 13, 14 and Table 3.

Figure 13. Medium-baseline test result

Figure 14. Medium-baseline differential result Mean (dBm)Std.Deviation

Desktop Station 51.66 1.66Laptop Station 62.67 2.57Laptop after D Correction 62.67 2.48

Table 3. the statistic result of middle-baseline experiment From the medium-baseline test results (Figure 13),differential test result (Figure 14) and the differential statistic results (Table 3), it is found that differential method shows less correlation across different datasets.The signal strength standard deviation of the mobile receiver only changed from 2.57m to 2.48m, which means the environment relativity of the two stations tends to become weak for distance of 10m or more.

4. 4 Long-Baseline (up to 15 metres) Experiment As before, we extend the distance between laptop computer and desktop computer to 15m, and we collected 3600 records. The results are presented in Figures 15, 16

and Table 4.

Figure 15

. Long-baseline test result

Figure 16. Long -baseline differential result

Mean (dBm)Std.Deviation

Desktop Station 57.66 1.33Laptop Station 55.700.87Laptop after D Correction 55.70 1.66

Table 4. The statistic results of long-baseline experiment In long-baseline experiment, the differential statistic result (Table 4) has totally failed. After differential correction the standard deviation of the mobile receiver did not reduce, on the contrary, it increased. Of course, this result happened by accident, but in some sense, it really proved

that the two receivers are located in two completely different environments.

5. SIGNAL STRENGTH MINIMAL VALUE ALGORITHM

There is no doubt that the true value of signal strength will provide an accurate position. However, in real time and realistic environments, the true values are not

available most of the time. From the static experiment it is found that signal strength is likely to be weakened by a non-ideal environment. That means some difficult environment will easily cause signal attenuation. Figure 17 shows the likelihood of signal attenuation. It is believed that the strongest signal strength at one position will be closer to the true value of that point.

So based on

this reasoning a signal strength minimal value (or strongest value of signal strength) algorithm is proposed. In practice we use a “windows” method to select the minimal value. That is, a group of signal strength values at different positioning waypoints is collected, and then the minimal value (or strongest value)of signal strength is used as the true signal strength value of that point in the positioning. For example, at a positioning waypoint, we use 1Hz-sampling rate to collect signal strength for 5 seconds to get 5 values, and then select the minimal value as the applied measurement values for that point. This method is indicated in Figure 18.

Figure 18 Windows method to select the minimal value every 5 records (one waypoint).6. CONCLUDING REMARKS

By use of the differential WPS, from the results of the experiments, it can be concluded that using a fixed wireless radio base station in the same environment as that of the access point, remedies to some extent the diversification of wireless radio propagations such as reflection, diffraction, and scattering of radio frequency waves of different and complicated environmental factors.

Figure 17. Static experiment of signal strength

Especially, in the short (up to 5 metres) and medium (up to 10 metres) baseline experiments, the correlation between rover station and fixed base station is much shorter and therefore, the differential corrections can improve the stability and continuity of wireless RF measurements in these two cases. However, if the distance is longer than 15m, the measurements between rover and base station are totally dissimilar rendering the differential algorithms ineffective.

The signal strength minimal value algorithm is based on a group of measurements in a static experiment. In practice, we use a “windows” method to choose the minimal signal strength. Consequently, it can mitigate the disturbance factor as well.

As a final note, differential and signal strength minimal value algorithms are entirely different, but both attempt to remove the influence of outside effects. So, in practice, we can combine these two algorithms with the empirical model to obtain a more robust real-time indoor position. REFERENCES

Aguirre S, Loew LH, Yeh L (1994) Radio propagation into buildings at 912, 1920, and 5990 MHz, Proceedings of 3rd IEEE International Conference on Universal & Personal Communication (ICUPC), Sept.1994 San Diego CA USA 129-134.

Bahl P, Padmanabhan VN (2000) RADAR: an in-building RF-based user location and tracking system, Proceedings of the IEEE Infocom, Tel-Aviv, Israel, Mar.2000 775-784. Bahl P, Padmanabhan VN, Balachandran A (2003) a software system for locating mobile users: design, evaluation and lessons, Microsoft Research.

Zhou Z (2003) ReLocMan: software-based mobile location management framework for indoor wireless computing environments.Blake LV (1986) Radar Range-Performance Analysis, Artech House Norwood MA USA 45-70.

Devasirvatham DMJ, Krain MJ, Rappaport TS, Banerjee C (1994) Radio propagation measurement at 850 MHz, 1.7 GHz, 4 GHz inside two dissimilar office building, IEEE Electronics Letters 26(7): 140-144.

Grant DB, Rizos C, Stolz A (1990), Dealing with GPS BIAS: Some Theoretical And Software Considerations, UNISURV S-38, 1990 Report from School of Surveying UNSW, Australia.

Durgin G, Rappaport TS, Xu H (1998) Measurements and models for radio path loss and penetration loss in and around homes and trees at 5.85 GHz, IEEE Transactions on Communications, 46(11): 1484-1496.

Hjelm J (2002), C reating location services for the wireless web, Wiley, NEWYORK USA, 15-40.

Parsons JD, Gardiner JG (1989) Mobile Communication Systems, Halsted Press, NEWYORK USA.

Seidel SY, Rappaport TS (1992) 914 MHz path loss prediction models for indoor wireless communications in multi-floored buildings, IEEE Transactions on Antennas and Propagation, 40: 207-217.

Small J, Smailagic A, Siewiorek DP (2000) Determining user location for context aware computing through the use of a wireless LAN infrastructure, Project Aura Report, Carnegie Mellon University, (h t t p://w w https://www.sodocs.net/doc/6615144928.html,/~aura/publications.html).

Wang Y, Jia X, Lee HK (2003), an indoor wireless positioning system (WPS) based on wireless local area network infrastructure, SatNAV 2003 Conference, Melbourne, Australia.

新八年级下册英语课文语法填空和短文改错

一、 HanselandGretel______(live)nearaforestwithhisfatherandstepmother.Oneyear,theweather______(be)sodry thatnofood_____(grow).Thewifetoldherhusbandthatunlesshe________(leave)hischildren______(die)inthe forest,thewholefamilywoulddie.Gretel_________(hear)thattheirstepmotherplanned________(kill)herandh erbrother.ButHanselhadaplan________(save)himselfandhissister.Hewenttogetsomewhitestonesbeforehew enttobedthatnight.Thenextday,thewife_________(send)thechildrentotheforest.Hansel___________(drop)t https://www.sodocs.net/doc/6615144928.html,terthatnight,they________(see)thestonesbecauseoftheshiningmoon.Thestones__ ace)forthisistheHimalayas.TheHimalayasrunalongthe______________(southwest)partofChina.Ofallthem ountains,Qomolangma________(rise)thehighestandis____________(famous).Itis8,844.43metershighands oisverydangerous________(climb).Thickcloudscoverthetopandsnow__________(fall)veryhard.Evenmore serious_______(difficulty)includefreezingweatherconditionsandheavystorms.Itisalsoveryhard_____(take) inairasyougetnearthetop. Thefirstpeople_____(reach)thetopwereTenzingNorgayandEdmundHillaryonMay29,1953.ThefirstChi neseteam__(do)soinI960,whilethefirstwoman_____(succeed)wasJunkoTabeifromJapanin1975. Whydosomanyclimbersrisktheir_____(life)?Oneofthemain_______(reason)isbecausepeoplewant______(c hallenge)themselvesinthefaceofdifficulties. Thespiritoftheseclimbers_____(show)usthatweshouldnevergiveup____(try)toachieveourdreams.Itals

中国文化常识-中国传统艺术I 中国民乐与戏剧(英文讲授中国文化)Chinese Folk Music and Local Operas

Folk Music 中国民乐 Beijing Opera 京剧 Local Operas 地方戏 Outline ?China, a nation of long history with profound culture, ?inherited and developed a great variety of traditional art forms which suit both refined and popular tastes 雅俗共赏. ?From the melodious and pleasant folk music to the elaborate and touching local dramas, ?from the simple but elegant inkwash painting(水墨画) to the flexible and powerful calligraphy, ?one can always discern the light of sparkling wisdom. ?Traditional Chinese arts have tremendously impressed the world. ?Chinese folk music, with strong nationalistic features, is a treasure of Chinese culture. ?As early as the primitive times, Chinese people began to use musical instruments, ?which evolved today into four main types categorized by the way they are played 吹拉弹打.materials they are made of （丝竹管弦）. stringed instrument 丝：弦乐器 wind instrument 竹：管乐器 ?吹：The first type is wind instrument 管乐器, as show in xiao （a vertical bamboo flute ）箫，flute 笛子, suona horn 唢呐, etc. ?拉：The second type is string instrument 弦乐器, represented by urheen 二胡, jinghu 京胡（a two-string musical instrument similar to urheen ）, banhu fiddle 板胡, etc.