r\
`00
`ON
`on
`
`U“)
`
`Proceedings
`
`Second International Workshop, LoCA 2006
`Dublin, Ireland, May 2006
`
`@ Springer
`
`U Z.
`
`4
`
`APPLE EXHIBIT 1014
`Page 1 of 27
`
`

`

`Lecture Notes in Computer Science
`Commenced Publication in 1973
`Founding and Former Series Editors:
`Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
`
`3987
`
`Editorial Board
`
`David Hutchison
`Lancaster University, UK
`Takeo Kanade
`Carnegie Mellon University, Pittsburgh, PA, USA
`Josef Kittler
`University of Surrey, Guildford, UK
`Jon M. Kleinberg
`Cornell University, Ithaca, NY, USA
`Friedemann Mattern
`ETH Zurich, Switzerland
`John C. Mitchell
`Stanford University, CA, USA
`Moni Naor
`Weizmann Institute of Science, Rehovot, Israel
`Oscar Nierstrasz
`University of Bern, Switzerland
`C. Pandu Rangan
`Indian Institute of Technology, Madras, India
`Bernhard Steffen
`University of Dortmund, Germany
`Madhu Sudan
`Massachusetts Institute of Technology, MA, USA
`Demetri Terzopoulos
`University of California, Los Angeles, CA, USA
`Doug Tygar
`University of California, Berkeley, CA, USA
`Moshe Y. Vardi
`Rice University, Houston, TX, USA
`Gerhard Weikum
`Max-Planck Institute of Computer Science, Saarbruecken, Germany
`
`APPLE EXHIBIT 1014
`Page 2 of 27
`
`

`

`Mike Hazas John Krumm
`Thomas Strang (Eds.)
`
`Location- and
`Context-Awareness
`
`Second International Workshop, LoCA 2006
`Dublin, Ireland, May 10-11, 2006
`Proceedings
`
`1 3
`
`APPLE EXHIBIT 1014
`Page 3 of 27
`
`

`

`Volume Editors
`
`Mike Hazas
`Lancaster University
`Computing Department, Infolab
`South Drive, Lancaster, LA1 4WA, UK
`E-mail: hazas@comp.lancs.ac.uk
`
`John Krumm
`Microsoft Corporation
`One Microsoft Way, Redmond, WA 98052, USA
`E-mail: jckrumm@microsoft.com
`
`Thomas Strang
`Deutsches Zentrum für Luft- und Raumfahrt
`P.O. Box 1116, 82234 Wessling/Oberpfaffenhofen, Germany
`E-mail: Thomas.Strang@dlr.de
`
`Library of Congress Control Number: 2006924878
`
`CR Subject Classification (1998): H.3, H.4, C.2, H.5, K.8
`
`LNCS Sublibrary: SL 3 – Information Systems and Application, incl. Internet/Web
`and HCI
`
`ISSN
`ISBN-10
`ISBN-13
`
`0302-9743
`3-540-34150-1 Springer Berlin Heidelberg New York
`978-3-540-34150-5 Springer Berlin Heidelberg New York
`
`This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
`concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
`reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
`or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
`in its current version, and permission for use must always be obtained from Springer. Violations are liable
`to prosecution under the German Copyright Law.
`
`Springer is a part of Springer Science+Business Media
`
`springer.com
`
`© Springer-Verlag Berlin Heidelberg 2006
`Printed in Germany
`
`Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India
`Printed on acid-free paper
`SPIN: 11752967
`06/3142
`5 4 3 2 1 0
`
`APPLE EXHIBIT 1014
`Page 4 of 27
`
`

`

`
`
`Preface
`
`These proceedings contain the papers presented at the 2nd International Workshop on
`Location- and Context-Awareness in May of 2006. As computing moves increasingly
`into the everyday world, the importance of location and context knowledge grows.
`The range of contexts encountered while sitting at a desk working on a computer is
`very limited compared to the large variety of situations experienced away from the
`desktop. For computing to be relevant and useful in these situations, the computers
`must have knowledge of the user’s activity, resources, state of mind, and goals, i.e.,
`the user’s context, of which location is an important indicator. This workshop was
`intended to present research aimed at sensing, inferring, and using location and
`context data in ways that help the user.
`Our call for papers resulted in 74 submissions, each of which was assigned to
`members of our Program Committee. After reviews and email discussion, we selected
`18 papers for publication in these proceedings. Most of the accepted papers
`underwent a shepherding process by a reviewer or a member of the Program Comm-
`ittee to ensure that the reviewers’ comments were accounted for in the published
`version. We feel our selective review process and shepherding phase have resulted in
`a high-quality set of published papers.
`We extend a sincere “thank you” to all the authors who submitted papers, to our
`hard-working Program Committee, our thoughtful reviewers, and our conscientious
`shepherds.
`
`
`
`May 2006
`
`
` Mike Hazas and John Krumm, Program Co-chairs
` Thomas Strang, Workshop Chair
`
`
`
`
`
`APPLE EXHIBIT 1014
`Page 5 of 27
`
`

`

`
`
`Program Committee
`
`Organization
`
` University of Washington and Intel Research
`Gaetano Borriello
` Seattle
` Carnegie Mellon University
`Anind Dey
`
` University of California, San Diego
`William Griswold
`Robert Harle
`
` University of Cambridge
` Intel Research Seattle
`Jeffrey Hightower
` Dartmouth College
`Minkyong Kim
`
` Johannes Kepler University of Linz
`Gabriele Kotsis
`
`Marc Langheinrich
` ETH Zurich
` Ludwig Maximilian University Munich
`Claudia Linnhoff-Popien
`
` University of Bristol
`Henk Muller
`
` IBM T.J. Watson Research Center
`Chandrasekhar Narayanaswami
` University of Maine
`Harlan Onsrud
`
` University of California, Irvine
`Donald Patterson
` Fraunhofer IPSI
`Thorsten Prante
`
`Aaron Quigley
`
` University College Dublin
`Bernt Schiele
`
` Darmstadt University of Technology
`Chris Schmandt
`
` MIT Media Lab
`Flavia Sparacino
` Sensing Places and MIT
`Thomas Strang
`
` German Aerospace Center and University of
` Innsbruck
`Yasuyuki Sumi
`
` Kyoto University
`Hiroyuki Tarumi
` Kagawa University
`Daniel Wilson
`
` Author
`
`Reviewers
`
`
`Ian Anderson
`
`Michael Beigl
`Alastair Beresford
`David Cottingham
`Florian Fuchs
`
`Caroline Funk
`
`Thomas Grill
`
`Tom Gross
`
`Sinem Guven
`
`Ismail Ibrahim
`
`Axel Küpper
`
`David Molyneaux
`Mandayam Raghunath
`
`
` University of Bristol
` University of Karlsruhe
` University of Cambridge
` University of Cambridge
` Siemens and Ludwig Maximilian University Munich
` Ludwig Maximilian University Munich
` Johannes Kepler University of Linz
` Bauhaus University Weimar
` Columbia University
` Johannes Kepler University of Linz
` Ludwig Maximilian University Munich
` Lancaster University
` IBM T.J. Watson Research Center
`
`APPLE EXHIBIT 1014
`Page 6 of 27
`
`

`

`VIII
`
`Organization
`
`Anand Ranganathan
`Wieland Schwinger
`Peter Tandler
`
`Georg Treu
`
`Diana Weiss
`
`
` IBM T.J. Watson Research Center
` Johannes Kepler University of Linz
` Fraunhofer IPSI
` Ludwig Maximilian University Munich
` Ludwig Maximilian University Munich
`
`Shepherds
`
`Alastair Beresford
`Gaetano Borriello
`Sinem Guven
`
`Robert Harle
`
`Mike Hazas
`
`Jeffrey Hightower
`Minkyong Kim
`
`Marc Langheinrich
`Henk Muller
`
`Aaron Quigley
`
`Flavia Sparacino
`Daniel Wilson
`
`
`University of Cambridge
`University of Washington and Intel Research Seattle
`Columbia University
`University of Cambridge
`Lancaster University
`Intel Research Seattle
`Dartmouth College
`ETH Zurich
`University of Bristol
`University College Dublin
`Sensing Places and MIT
`Author
`
`APPLE EXHIBIT 1014
`Page 7 of 27
`
`

`

`Table of Contents
`
`Location Sensing
`
`Particle Filters for Position Sensing with Asynchronous Ultrasonic
`Beacons
`Henk L. Muller, Michael McCarthy, Cliff Randell . . . . . . . . . . . . . . . . . .
`
`Cluster Tagging: Robust Fiducial Tracking for Smart Environments
`Robert Harle, Andy Hopper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`Automatic Mitigation of Sensor Variations for Signal Strength Based
`Location Systems
`Mikkel Baun Kjærgaard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`Mapping
`
`KOTOHIRAGU NAVIGATOR: An Open Experiment of Location-
`Aware Service for Popular Mobile Phones
`Hiroyuki Tarumi, Yuko Tsurumi, Kazuya Matsubara,
`Yusuke Hayashi, Yuki Mizukubo, Makoto Yoshida,
`Fusako Kusunoki
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`A Wearable Interface for Topological Mapping and Localization in
`Indoor Environments
`Grant Schindler, Christian Metzger, Thad Starner . . . . . . . . . . . . . . . . .
`
`Taking Location Modelling to New Levels: A Map Modelling Toolkit
`for Intelligent Environments
`Christoph Stahl, Jens Haupert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`1
`
`14
`
`30
`
`48
`
`64
`
`74
`
`Privacy and Access
`
`Harvesting of Location-Specific Information Through WiFi Networks
`Jong Hee Kang, Gaetano Borriello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`86
`
`Re-identifying Anonymous Nodes
`Stefan Schlott, Frank Kargl, Michael Weber . . . . . . . . . . . . . . . . . . . . . . . 103
`
`Anonymous User Tracking for Location-Based Community Services
`Peter Ruppel, Georg Treu, Axel K¨upper,
`Claudia Linnhoff-Popien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
`
`APPLE EXHIBIT 1014
`Page 8 of 27
`
`

`

`X
`
`Table of Contents
`
`Context Sensing
`
`Towards Personalized Mobile Interruptibility Estimation
`Nicky Kern, Bernt Schiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
`
`Unsupervised Discovery of Structure in Activity Data Using Multiple
`Eigenspaces
`Tˆam Hu`ynh, Bernt Schiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
`
`Toward Scalable Activity Recognition for Sensor Networks
`Christopher R. Wren, Emmanuel Munguia Tapia . . . . . . . . . . . . . . . . . . 168
`
`Social Context
`
`Nomatic: Location By, For, and Of Crowds
`Donald J. Patterson, Xianghua Ding, Nicholas Noack . . . . . . . . . . . . . . 186
`
`An Unsupervised Learning Paradigm for Peer-to-Peer Labeling and
`Naming of Locations and Contexts
`John A. Flanagan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
`
`Building Common Ground for Face to Face Interactions by Sharing
`Mobile Device Context
`Vassilis Kostakos, Eamonn O’Neill, Anuroop Shahi
`
`. . . . . . . . . . . . . . . . 222
`
`Representation and Programming
`
`Evaluating Performance in Continuous Context Recognition Using
`Event-Driven Error Characterisation
`Jamie A. Ward, Paul Lukowicz, Gerhard Tr¨oster . . . . . . . . . . . . . . . . . . 239
`
`Location-Based Context Retrieval and Filtering
`Carsten Pils, Ioanna Roussaki, Maria Strimpakou . . . . . . . . . . . . . . . . . . 256
`
`Scripting Your Home
`Mirko Knoll, Torben Weis, Andreas Ulbrich, Alexander Br¨andle . . . . . 274
`
`Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
`
`APPLE EXHIBIT 1014
`Page 9 of 27
`
`

`

`Automatic Mitigation of Sensor Variations for
`Signal Strength Based Location Systems
`
`Mikkel Baun Kjærgaard
`
`Department of Computer Science, University of Aarhus,
`IT-parken, Aabogade 34, DK-8200 Aarhus N, Denmark
`mikkelbk@daimi.au.dk
`
`Abstract. In the area of pervasive computing a key concept is context-
`awareness. One type of context information is location information of
`wireless network clients. Research in indoor localization of wireless net-
`work clients based on signal strength is receiving a lot of attention. How-
`ever, not much of this research is directed towards handling the issue of
`adapting a signal strength based indoor localization system to the hard-
`ware and software of a specific wireless network client, be it a tag, PDA
`or laptop. Therefore current indoor localization systems need to be man-
`ually adapted to work optimally with specific hardware and software. A
`second problem is that for a specific hardware there will be more than
`one driver available and they will have different properties when used for
`localization. Therefore the contribution of this paper is twofold. First,
`an automatic system for evaluating the fitness of a specific combination
`of hardware and software is proposed. Second, an automatic system for
`adapting an indoor localization system based on signal strength to the
`specific hardware and software of a wireless network client is proposed.
`The two contributions can then be used together to either classify a spe-
`cific hardware and software as unusable for localization or to classify
`them as usable and then adapt them to the signal strength based indoor
`localization system.
`
`1 Introduction
`
`In the area of pervasive computing a key concept is context-awareness. One type
`of context information is location information of wireless network clients. Such
`information can be used to implement a long range of location based services.
`Examples of applications are speedier assistance for security personnel, health-
`care professionals or others in emergency situations and adaptive applications
`that align themselves to the context of the user. The implementation of speedier
`assistance could, for example, come in the form of a tag with an alarm but-
`ton that, when pressed, alerts nearby persons to come to assistance. The alarm
`delivered to the people nearby would contain information on where in the phys-
`ical environment the alarm was raised and by whom. Applications that adapt
`themselves to the context they are in are receiving a lot of attention in the area
`of pervasive computing, where they can solve a number of problems. One type
`of context information is location which can be used in its simplest form to
`implement new services optimized based on the location information.
`
`M. Hazas, J. Krumm, and T. Strang (Eds.): LoCA 2006, LNCS 3987, pp. 30–47, 2006.
`c(cid:4) Springer-Verlag Berlin Heidelberg 2006
`
`APPLE EXHIBIT 1014
`Page 10 of 27
`
`

`

`Automatic Mitigation of Sensor Variations
`
`31
`
`Small-scale
`
`Table 1. Signal strength variations
`
`Spatial
`around
`Movement
`one wavelength
`
`Temporal
`Transient effects
`
`Large-scale
`
`Normal movement
`
`Prolonging effects
`
`Sensor
`Different examples of
`the same WRC com-
`bination
`Different WRC com-
`binations
`
`One type of indoor location system, which can be used to support the above
`scenarios, is systems based on signal strength measurements from an off-the-shelf
`802.11 wideband radio client (WRC). The WRC can be in the form of either a
`tag, phone, PDA or laptop. Such systems need to address several ways in which
`the signal strength can vary. The variations can be grouped into large and small-
`scale spatial, temporal, and sensor variations as shown in Table 1. The spatial
`variations can be observed when a WRC is moved. Large-scale spatial variations
`are what makes localization possible, because the signal strength depends on
`how the signals propagate. The small-scale spatial variations are the variations
`that can be observed when moving a WRC as little as one wave length. The
`temporal variations are the variations that can be observed over time when a
`WRC is kept at a static position. The large-scale temporal variations are the
`prolonged effects observed over larger periods of time; an example is the differ-
`ence between day and night where during daytime the signal strength is more
`affected by people moving around and the use of different WRCs. The small-
`scale temporal variations are the variations implied by quick transient effects
`such as a person walking close to a WRC. The sensor variations are the varia-
`tions between different WRCs. Large-scale variations are the variations between
`radios, antennas, firmware, and software drivers from different manufactures.
`Small-scale variations are the variations between examples of the same radio,
`antenna, firmware, and software drivers from the same manufacture. The chosen
`groupings are based on the results in [1, 2].
`Most systems based on signal strength measurements from off-the-shelf 802.11
`wideband radio clients do not address the above variations explicitly, with [1]
`and [2] as exceptions. Especially the handling of sensor variations has not been
`given much attention. Therefore current location systems have to be manually
`adapted by the provider of the location system for each new type of WRC to
`work at its best. This is not optimal considering the great number of combina-
`tions of antennas, firmware, and software drivers for each radio. To the users
`the large-scale sensor variation poses another problem, because the different im-
`plementations of firmware and software drivers have different properties with
`respect to localization. To the users it would therefore be of help if the system
`could automatically evaluate if the firmware and software drivers installed could
`be used for localization.
`The contribution of this paper is twofold. To solve the problem of large-scale
`sensor variations, an automatic system is proposed for adapting an indoor localiza-
`tion system based on signal strength to the specific antenna, radio, firmware, and
`
`APPLE EXHIBIT 1014
`Page 11 of 27
`
`

`

`32
`
`M.B. Kjærgaard
`
`software driver of a WRC. To solve the problem of evaluating different sensors, an
`automatic system for evaluating the fitness of a specific combination of antenna,
`radio, firmware, and software driver is proposed. The two contributions can then
`be used together to either classify a combination of antenna, radio, firmware, and
`software drivers as unusable for localization or to classify them as usable and then
`adapt them to the signal strength based indoor localization system.
`The methods proposed for providing automatic classification and adaptation
`are presented in Section 2. The results of applying these methods to 14 com-
`binations of antennas, radios, firmware, and software are given in Section 3.
`Afterwards the results are discussed in Section 4 and finally conclusions are
`given in Section 5.
`
`1.1 Related Work
`
`Research in the area of indoor location systems, as surveyed in [3, 4], spans a wide
`range of technologies (wideband radio, ultra-wideband radio, infrared,...), pro-
`tocols (IEEE 802.11,802.15.1,...), and algorithm types (least squares, bayesian,
`hidden markov models, ...). Using these elements the systems estimate the loca-
`tion of wireless entities based on different types of measurements such as time,
`signal strength, and angles. Systems based on off-the-shelf 802.11 wideband ra-
`dio clients using signal strength measurements have received a lot of attention.
`One of the first systems was RADAR [5], that applied different deterministic
`mathematical models to calculate the position in coordinates of a WRC. The
`mathematical models used had to be calibrated for each site where the systems
`had to be used. In comparison to RADAR, later systems have used probabilistic
`models instead of mathematical models. This is because a good mathematical
`model which can model the volatile radio environment has not been found. As
`in the case of the mathematical models in RADAR, the probabilistic models
`should also be calibrated for each site. Examples of such systems determining
`the coordinates of a WRC are published in [2, 6,7 , 8] and systems determining
`the logical position or cell of a WRC are published in [1, 9, 10]1. Commercial
`positioning systems also exist such as Ekahau [11] and PanGo [12]. In the fol-
`lowing, related work is presented with respect to how the systems address the
`signal strength variations introduced above.
`Small-scale spatial variations are addressed by most systems using a method
`to constrain how the location estimate can evolve from estimate to estimate.
`The method used for the system in [7] is to average the newest estimate with
`previous estimates. In [1, 6, 8, 13] more advanced methods based on constraining
`the estimates using physical properties are proposed. The constraints include
`both the layout of the physical environment and the likely speed by which a
`WRC can move. One way these constraints can be incorporated in a probabilis-
`tic model is to use a Hidden Markov Model to encode the constraints with. In [2]
`another method is proposed which in the case of movement triggers a perturba-
`tion technique that addresses the small-scale variations. In [14] a graph-inspired
`
`1
`
`The system in [9] uses the signal to noise ratio instead of the signal strength.
`
`APPLE EXHIBIT 1014
`Page 12 of 27
`
`

`

`Automatic Mitigation of Sensor Variations
`
`33
`
`solution is presented which weights measurements based on the physical dis-
`tance between location estimates. Large-scale spatial variations are, as stated in
`the introduction, the variation which makes indoor location system using signal
`strength possible. The different methods for inferring the location are a too ex-
`tensive area to cover here in detail. Some examples of different types of systems
`were given above.
`Small-scale temporal variations can be addressed using several techniques.
`The first concerns how the probabilistic model is build from the calibration
`measurements. Here several options exist: the histogram method [6, 7, 8], the
`Gaussian kernel method [7], and the single Gaussian distribution [1]. The sec-
`ond technique is to include several continuous measurements in the set of mea-
`surements used for estimating the location. By including more measurements
`quick transient effects can be overcome. This can be done as in [1, 7], where
`the measurements are used as independent measurements or as in [2], where a
`time-averaging technique is used together with a technique which addresses the
`correlation of the measurements. Large-scale temporal variations have been ad-
`dressed in [14] based on extra measurements between base stations, which were
`used to determine the most appropriate radio map. In [1]a meth od is proposed
`were a linear mapping between the WRC measurements and the radio map is
`used. The parameters of this mapping can then be fitted to the characteristics
`of the current environment which addresses the large-scale temporal variations.
`Small-scale sensor variations have not been explicitly addressed in earlier
`research. One reason for this is that the small variations between examples of-
`ten are difficult to measure, because of the other variations overshadowing it.
`Therefore there exist no general techniques, but possibly the techniques for the
`large-scale sensor variations could be applied. For large-scale sensor variations
`[1] proposed applying the same linear approximation as in the case of large-
`scale temporal variations. They propose three different methods for finding the
`two parameters in the linear approximation. The first method is a manual one,
`where a WRC has to be taken to a couple of known locations to collect mea-
`surements. For finding the parameters they propose to use the method of least
`squares. The second method is a quasi-automatic one where a WRC has to
`be taken to a couple of locations to collect measurements. For finding the pa-
`rameters they propose using the confidence value produced when doing Markov
`localization on the data and then find the parameters that maximize this value.
`The third is an automatic one requiring no user intervention. Here they pro-
`pose using an expectation-maximation algorithm combined with a window of
`recent measurements. For the manual method they have published results which
`show a gain in accuracy for three cards; for the quasi-automatic method it is
`stated that the performance is comparable to that of the manual method, and
`for the automatic one it is stated that it does not work as well as the two other
`techniques.
`The methods proposed in this paper to solve the problem of large-scale sensor
`variations are a more elegant and complete solution than the method proposed
`in [1]. It is more elegant, because it uses the same type of estimation technique
`
`APPLE EXHIBIT 1014
`Page 13 of 27
`
`

`

`34
`
`M.B. Kjærgaard
`
`for both the manual, quasi-automatic, and automatic case. It is more complete,
`because it can recognize WRCs that cannot be used for localization. Also it has
`been shown to work on a larger set of WRC combinations with different radios,
`antennas, firmware, and software drivers.
`
`2 Methods for Classification and Normalization
`
`A cell based indoor localization system, such as the ones proposed in [1, 9, 10],
`should estimate the probability of a WRC being in each of the cells which the
`system covers. A cell is here normally a room or part of a room in larger rooms
`or a section of a hallway. Formally a set S = {s1,...,sn} is a finite set of states
`∗ is the state of the WRC that
`where each state corresponds to a cell. The state s
`should be located. The location estimate of the WRC can then be denoted by a
`probability vector π with each entry of the vector denoting the probability that
`∗ = si).
`the WRC is in this particular state πi = P (s
`To solve the localization problem the vector π has to be estimated, which is
`addressed by infrastructure-based localization using two types of measurements.
`First, there are the measurements M = {m1,...,ms} reported by the WRC, which
`is to be located. Second, there is a set C = {c1,...,ct} of calibration measurements
`collected prior to the launch of the location service. Each measurement is defined
`as M = V × B where B = {b1,...,bk} is the set of base stations and V =
`{0,...,255} is the set of signal strength values for 802.11 WRCs. The calibration
`measurements are collected to overcome the difficulties in localizing clients in
`the volatile indoor radio environment.
`The estimation of the vector π based on the two types of measurements can
`be divided into three sub-problems. The first problem is the normalization prob-
`lem, which adresses how WRC-dependent measurements are transformed into
`normalized measurements. The reason the measurements need to be normalized
`is that otherwise they cannot be combined with the calibration measurements
`which have most often not been collected by the same WRC. The next problem,
`state estimation, is how the normalized measurements are transformed into a
`location estimate. The last problem, tracking, is how the physical layout of the
`site and prior estimates can be used to enrich the location estimate. In respect to
`these problems, it is the problem of normalization made in an automatic fashion
`that this paper addresses. For evaluating the proposed methods in the context
`of a localization system an implementation based on the ideas in [1] without
`tracking is used.
`In the following sections methods are proposed for solving the problem of au-
`tomatic normalization (Section 2.3-2.6) and the problem of classifying the fitness
`of a WRC for localization automatically (Section 2.2). The solutions are stated
`in the context of indoor localization system using signal strength measurements
`from off-the-shelf 802.11 wideband radio clients. However, the solutions could be
`applied to other types of radio clients which can measure signal strength values.
`
`APPLE EXHIBIT 1014
`Page 14 of 27
`
`

`

`Automatic Mitigation of Sensor Variations
`
`35
`
`2.1 Automatic Still Period Analyzer
`
`In the proposed methods an analyzer, called an automatic still period analyzer, is
`used to divide measurements into groups of measurements from single locations.
`The idea behind the analyzer is that, if we can estimate if a WRC is still or
`moving, we can place a group of still measurements in one location. One thing
`to note here is that localization cannot be used to infer this information, because
`the parameters for adapting the WRC to the localization system have not yet
`been found. The still versus moving estimator applied is based on the idea in
`[6] of using the variations in the signal strength to infer moving versus still
`situations. To do this, the sample variation is calculated for the signal strength
`measurements in a window of 20 seconds. The estimation is then based on having
`training data from which distributions of the likelihood of the WRC being still or
`moving at different levels of variations is constructed. To make a stable estimate
`from the calculated variations and likelihood distributions a Hidden Markov
`Model (HMM) is applied as estimator with the parameters proposed in [6]. To
`evaluate the implemented estimator two walks were collected with the lengths of
`44 minutes and 27 minutes, respectively, where the person collecting the walks
`marked in the data when he was still or moving. These two walks were then used
`in a simulation, where one was used as training data to construct the likelihood
`distributions and the other as test data. The results were that 91% of the time
`the estimator made the correct inference and with a small number of wrong
`transitions between still and moving because of the HMM as experienced in [6].
`However, the estimator performs even better when only looking at still periods,
`because the errors experienced are often that the estimator infers moving when
`the person is actually still.
`The estimator used here differs in two ways with respect to the method pro-
`posed in [6]. First, weighted sample variations for all base stations in range are
`used instead of the sample variation for the strongest base station. This was cho-
`sen because our experiments showed this to be more stable. Second, the Gaussian
`kernel method is used instead of the histogram method to construct the likeli-
`hood distributions. One thing to note is that the estimator does not work as
`well with WRC combinations, which cache measurements or have a low update
`frequency.
`
`2.2 Fitness Classifier
`
`Methods for classifying the fitness of a single combination of antenna, radio,
`firmware, and software drivers for localization are presented. To make such a
`classifier, it first has to be defined what makes a combination fit or unfit. A
`good combination has some of the following characteristics: the radio has high
`sensitivity so that it can see many bases, has no artificial limits in the signal
`strength values, does not cache the signal strength values, and has a high update
`frequency.2 On the other hand, a bad combination has low sensitivity, limits the
`2
`
`Pure technical constraints, such as cards that can not return signal strength values,
`are not addressed in this paper.
`
`APPLE EXHIBIT 1014
`Page 15 of 27
`
`

`

`Netgear MA521
`Netgear WG511T
`Orinoco Silver Card
`
`36
`
`M.B. Kjærgaard
`
`100
`
`90
`
`80
`
`70
`
`60
`
`50
`
`40
`
`Signal Strength
`
`Netgear MA521
`Netgear WG511T
`Orinoco Silver Card
`
`100
`
`90
`
`80
`
`70
`
`60
`
`50
`
`40
`
`Signal Strength
`
`30
`
`0
`
`10
`
`20
`
`30
`
`Time / s
`
`40
`
`50
`
`60
`
`30
`
`0
`
`10
`
`20
`
`30
`
`Time / s
`
`40
`
`50
`
`60
`
`Fig. 1. Plots of signal strength measurements from different cards and base stations
`at the same location
`
`signal strength values, the signal strength values reported do not represent the
`signal strength but some other measurements, such as the link quality, caches
`the measurements, and has a low update frequency.
`To illustrate the effects of good and bad combinations on data collected from
`several WRCs, Figure 1 shows signal strength measurements for different WRCs
`taken at the same location and at the same time, but for two different 802.11
`base stations. On the first graph the effect of caching or low update rate for the
`Netgear WG511T card can be seen, because the signal strength only changes
`every five seconds. By comparing the two graphs, the effect of signal strength
`values not corresponding to the actual signal strength can be seen for the Netgear
`MA521 card. This is evident form the fact that the signal strength values for
`the Netgear MA521 card does not change when the values reported by the other
`cards change for specific base stations.
`In the following it is assumed that, for evaluating the fitness of a WRC com-
`bination, five minutes of measurements are available. The measurements should
`be taken in an area where at least three base stations are in range at all times.
`The measurements should be taken over five minutes and the WRC combination
`should be placed at four different locations for around 30-60 seconds. Of course,
`the techniques could be applied without these requirements. The system could,
`for instance, collect measurements until it had inferred that the WRC combina-
`tion had been placed at four locations. Then it would of course depend on the
`use of the WRC combination when enough measurements have been collected.
`To automatically evaluate the fitness of a specific combination, methods for
`finding the individual faults are proposed. For caching or low update frequency
`a method using a naive Bayesian estimator [15] based on the autocorrelation
`coefficient is