ON
`l'x
`<1-
`
`Proceedings
`
`First international Workshop, LoCA 2005
`Oberpfaffenhofen, Germany, May 2005
`
`m m U 2_
`
`I
`
`Q Springer
`
`APPLE EXHIBIT 1013
`Page 1 of 63
`
`

`

`Lecture Notes in Computer Science
`Commenced Publication in 1973
`Founding and Former Series Editors:
`Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
`
`3479
`
`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
`New York University, NY, 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 1013
`Page 2 of 63
`
`

`

`Thomas Strang Claudia Linnhoff-Popien (Eds.)
`
`Location- and
`Context-Awareness
`
`First International Workshop, LoCA 2005
`Oberpfaffenhofen, Germany, May 12-13, 2005
`Proceedings
`
`1 3
`
`APPLE EXHIBIT 1013
`Page 3 of 63
`
`

`

`Volume Editors
`
`Thomas Strang
`German Aerospace Center (DLR), Institute of Communications and Navigation
`82234 Wessling/Oberpfaffenhofen, Germany
`E-mail: thomas.strang@dlr.de
`
`Claudia Linnhoff-Popien
`University of Munich (LMU), Mobile and Distributed Systems Group
`Oettingenstr. 67, 80538 Munich, Germany
`E-mail: linnhoff@ifi.lmu.de
`
`Library of Congress Control Number: 2005925756
`
`CR Subject Classification (1998): H.3, H.4, C.2, H.5, K.8
`
`ISSN
`ISBN-10
`ISBN-13
`
`0302-9743
`3-540-25896-5 Springer Berlin Heidelberg New York
`978-3-540-25896-4 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
`
`springeronline.com
`
`© Springer-Verlag Berlin Heidelberg 2005
`Printed in Germany
`
`Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India
`Printed on acid-free paper
`SPIN: 11426646
`06/3142
`5 4 3 2 1 0
`
`APPLE EXHIBIT 1013
`Page 4 of 63
`
`

`

`Preface
`
`Context-awareness is one of the drivers of the ubiquitous computing paradigm.
`Well-designed context modeling and context retrieval approaches are key pre-
`requisites in any context-aware system. Location is one of the primary aspects
`of all major context models — together with time, identity and activity. From
`the technical side, sensing, fusing and distributing location and other context
`information is as important as providing context-awareness to applications and
`services in pervasive systems.
`The material summarized in this volume was selected for the 1st International
`Workshop on Location- and Context-Awareness (LoCA 2005) held in coopera-
`tion with the 3rd International Conference on Pervasive Computing 2005. The
`workshop was organized by the Institute of Communications and Navigation of
`the German Aerospace Center (DLR) in Oberpfaffenhofen, and the Mobile and
`Distributed Systems Group of the University of Munich.
`During the workshop, novel positioning algorithms and location sensing tech-
`niques were discussed, comprising not only enhancements of singular systems,
`like positioning in GSM or WLAN, but also hybrid technologies, such as the
`integration of global satellite systems with inertial positioning. Furthermore, im-
`provements in sensor technology, as well as the integration and fusion of sensors,
`were addressed both on a theoretical and on an implementation level.
`Personal and confidential data, such as location data of users, have pro-
`found implications for personal information privacy. Thus privacy protection,
`privacy-oriented location-aware systems, and how privacy affects the feasibility
`and usefulness of systems were also addressed in the workshop.
`A total of 84 papers from 26 countries were submitted to LoCA 2005, from
`which 26 full and 7 short papers were selected for publication in the proceed-
`ings. The overall quality of the submissions was impressive, demonstrating the
`importance of this field. The Program Committee did an excellent job — all
`papers were reviewed by at least 3 referees, which left each member with up to
`18 papers to be reviewed within a very tight schedule.
`
`May 2005
`
`Thomas Strang
`Claudia Linnhoff-Popien
`
`APPLE EXHIBIT 1013
`Page 5 of 63
`
`

`

`Organization
`
`Program Committee
`
`Alessandro Acquisti
`Victor Bahl
`Christian Becker
`Anind K. Dey
`Thomas Engel
`Dieter Fensel
`Jens Grossklags
`Mike Hazas
`Jeffrey Hightower
`Jadwiga Indulska
`John Krumm
`Axel K¨upper
`Gerard Lachapelle
`Marc Langheinrich
`Claudia Linnhoff-Popien
`Jussi Myllymaki
`Harlan Onsrud
`Aaron Quigley
`Kay R¨omer
`Albrecht Schmidt
`Stefan Schulz
`Frank Stajano
`Thomas Strang
`
`Carnegie Mellon University (USA)
`Microsoft Research (USA)
`University of Stuttgart (Germany)
`Carnegie Mellon University (USA)
`University of Luxemburg (Luxemburg)
`DERI (Austria/Ireland)
`University of California, Berkeley (USA)
`Lancaster University (UK)
`Intel Research Seattle (USA)
`University of Queensland (Australia)
`Microsoft Research (USA)
`University of Munich (Germany)
`University of Calgary (Canada)
`ETH Zurich (Switzerland)
`University of Munich (Germany)
`IBM Almaden Research Center (USA)
`University of Maine (USA)
`University College Dublin (Ireland)
`ETH Zurich (Switzerland)
`University of Munich (Germany)
`Carleton University (Canada)
`University of Cambridge (UK)
`German Aerospace Center (Germany)
`
`Additional Reviewers
`
`Henoc Agbota
`Michael Angermann
`Stavros Antifakos
`Trent Apted
`Martin Bauer
`Alastair Beresford
`Jan Beutel
`J¨urgen Bohn
`Thomas Buchholz
`Jim Campbell
`Nicolas Christin
`
`Lancaster University (UK)
`German Aerospace Center (Germany)
`ETH Zurich (Switzerland)
`National ICT Australia (Australia)
`University of Stuttgart (Germany)
`University of Cambridge (UK)
`ETH Zurich (Switzerland)
`ETH Zurich (Switzerland)
`University of Munich (Germany)
`University of Maine (USA)
`University of California, Berkeley (USA)
`
`APPLE EXHIBIT 1013
`Page 6 of 63
`
`

`

`VIII
`
`Organization
`
`Tobias Drosdol
`Dominique Dudkowski
`Frank D¨urr
`Stefan Dulman
`Babak Esfandiari
`Thomas Fritz
`Caroline Funk
`Eeva Hedefine
`Karen Henricksen
`Paul Holleis
`Jens Kammann
`Nicky Kern
`Mohamed Khedr
`Jacek Kopecky
`Matthias Kranz
`Michael Krause
`Reto Krummenacher
`Jonathan Lester
`Ning Luo
`Ted McFadden
`Oleg Mezentsev
`Daniela Nicklas
`Silvia Nittel
`Mark Petovello
`Carsten Pils
`Julian Randall
`Andrew Rice
`Patrick Robertson
`Ricky Robinson
`Enrico Rukzio
`Francois Scharffe
`Michael Schiffers
`John Schleppe
`Surendran Shanmugam
`Michael Stollberg
`Markus Strassberger
`Georg Treu
`Kristof Van Laerhoven
`Pablo Vidales
`Kerstin Zimmermann
`
`University of Stuttgart (Germany)
`University of Stuttgart (Germany)
`University of Stuttgart (Germany)
`University of Twente (The Netherlands)
`Carleton University (Canada)
`University of Munich (Germany)
`University of Munich (Germany)
`University of Maine (USA)
`DSTC Brisbane (Australia)
`University of Munich (Germany)
`German Aerospace Center (Germany)
`TU Darmstadt (Germany)
`Arab Academy for Science and Technology (Egypt)
`DERI Innsbruck (Austria)
`University of Munich (Germany)
`University of Munich (Germany)
`DERI Innsbruck (Austria)
`University of Washington (USA)
`University of Calgary (Canada)
`DSTC Brisbane (Australia)
`University of Calgary (Canada)
`University of Stuttgart (Germany)
`University of Maine (USA)
`University of Calgary (Canada)
`RWTH Aachen (Germany)
`ETH Zurich (Switzerland)
`University of Cambridge (UK)
`German Aerospace Center (Germany)
`University of Queensland (Australia)
`University of Munich (Germany)
`DERI Innsbruck (Austria)
`University of Munich (Germany)
`University of Calgary (Canada)
`University of Calgary (Canada)
`DERI Innsbruck (Austria)
`BMW Group (Germany)
`University of Munich (Germany)
`Lancaster University (UK)
`University of Cambridge (UK)
`DERI Innsbruck (Austria)
`
`APPLE EXHIBIT 1013
`Page 7 of 63
`
`

`

`Table of Contents
`
`Keynote
`
`Location Awareness: Potential Benefits and Risks
`Vidal Ashkenazi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`1
`
`Context Information Management and Distribution
`
`Context Modelling and Management in Ambient-Aware Pervasive
`Environments
`Maria Strimpakou, Ioanna Roussaki, Carsten Pils,
`Michael Angermann, Patrick Robertson, Miltiades Anagnostou . . . . . .
`
`A Context Architecture for Service-Centric Systems
`Johanneke Siljee, Sven Vintges, Jos Nijhuis . . . . . . . . . . . . . . . . . . . . . . .
`
`Towards Realizing Global Scalability in Context-Aware Systems
`Thomas Buchholz, Claudia Linnhoff-Popien . . . . . . . . . . . . . . . . . . . . . . .
`
`Positioning Sensor Systems I
`
`Towards LuxTrace: Using Solar Cells to Measure Distance Indoors
`Julian Randall, Oliver Amft, Gerhard Tr¨oster . . . . . . . . . . . . . . . . . . . . .
`
`Three Step Bluetooth Positioning
`Alessandro Genco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`MoteTrack: A Robust, Decentralized Approach to RF-Based Location
`Tracking
`Konrad Lorincz, Matt Welsh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`Positioning Sensor Systems II
`
`Correcting GPS Readings from a Tracked Mobile Sensor
`Richard Milton, Anthony Steed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`Web-Enhanced GPS
`Ramaswamy Hariharan, John Krumm, Eric Horvitz . . . . . . . . . . . . . . . .
`
`2
`
`16
`
`26
`
`40
`
`52
`
`63
`
`83
`
`95
`
`APPLE EXHIBIT 1013
`Page 8 of 63
`
`

`

`X
`
`Table of Contents
`
`The COMPASS Location System
`Frank Kargl, Alexander Bernauer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
`
`The xPOI Concept
`Jens Kr¨osche, Susanne Boll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
`
`Positioning Sensor Systems III
`
`The GETA Sandals: A Footprint Location Tracking System
`Kenji Okuda, Shun-yuan Yeh, Chon-in Wu, Keng-hao Chang,
`Hao-hua Chu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
`
`Improving the Accuracy of Ultrasound–Based Localisation Systems
`Hubert Piontek, Matthias Seyffer, J¨org Kaiser . . . . . . . . . . . . . . . . . . . . . 132
`
`Position Estimation of Wireless Access Point Using Directional
`Antennas
`Hirokazu Satoh, Seigo Ito, Nobuo Kawaguchi . . . . . . . . . . . . . . . . . . . . . . 144
`
`From Location to Context
`
`Exploiting Multiple Radii to Learn Significant Locations
`Norio Toyama, Takashi Ota, Fumihiro Kato, Youichi Toyota,
`Takashi Hattori, Tatsuya Hagino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
`
`Modeling Cardinal Directional Relations Between Fuzzy Regions Based
`on Alpha-Morphology
`Haibin Sun, Wenhui Li . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
`
`Commonsense Spatial Reasoning for Context–Aware Pervasive Systems
`Stefania Bandini, Alessandro Mosca, Matteo Palmonari
`. . . . . . . . . . . . 180
`
`Contextually Aware Information Delivery in Pervasive Computing
`Environments
`Ian Millard, David De Roure, Nigel Shadbolt . . . . . . . . . . . . . . . . . . . . . . 189
`
`Bayesian Networks
`
`Classifying the Mobility of Users and the Popularity of Access Points
`Minkyong Kim, David Kotz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
`
`Prediction of Indoor Movements Using Bayesian Networks
`Jan Petzold, Andreas Pietzowski, Faruk Bagci, Wolfgang Trumler,
`Theo Ungerer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
`
`APPLE EXHIBIT 1013
`Page 9 of 63
`
`

`

`Table of Contents
`
`XI
`
`Geo Referenced Dynamic Bayesian Networks for User Positioning on
`Mobile Systems
`Boris Brandherm, Tim Schwartz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
`
`Issues and Requirements for Bayesian Approaches in Context Aware
`Systems
`Michael Angermann, Patrick Robertson, Thomas Strang . . . . . . . . . . . . 235
`
`Context Inference
`
`Context-Aware Collaborative Filtering System: Predicting the User’s
`Preference in the Ubiquitous Computing Environment
`Annie Chen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
`
`Mobile Context Inference Using Low-Cost Sensors
`Evan Welbourne, Jonathan Lester, Anthony LaMarca,
`Gaetano Borriello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
`
`Where am I: Recognizing On-body Positions of Wearable Sensors
`Kai Kunze, Paul Lukowicz, Holger Junker, Gerhard Tr¨oster . . . . . . . . . 264
`
`Privacy
`
`Context Obfuscation for Privacy via Ontological Descriptions
`Ryan Wishart, Karen Henricksen, Jadwiga Indulska . . . . . . . . . . . . . . . . 276
`
`Share the Secret: Enabling Location Privacy in Ubiquitous
`Environments
`C. Delakouridis, L. Kazatzopoulos, G.F. Marias, P. Georgiadis . . . . . . 289
`
`Filtering Location-Based Information Using Visibility
`Ashweeni Beeharee, Anthony Steed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
`
`Location- and Context-Aware Applications
`
`Introducing Context-Aware Features into Everyday Mobile Applications
`Mikko Perttunen, Jukka Riekki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
`
`Predicting Location-Dependent QoS for Wireless Networks
`Robert A. Malaney, Ernesto Exposito, Xun Wei, Dao Trong Nghia . . . 328
`
`Location-Based Services for Scientists in NRENs
`Stefan Winter, Thomas Engel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
`
`APPLE EXHIBIT 1013
`Page 10 of 63
`
`

`

`XII
`
`Table of Contents
`
`Hybrid Positioning and User Studies
`
`Towards Smart Surroundings: Enabling Techniques and Technologies
`for Localization
`Kavitha Muthukrishnan, Maria Lijding, Paul Havinga . . . . . . . . . . . . . . 350
`
`Proximation: Location-Awareness Through Sensed Proximity and GSM
`Estimation
`Aaron Quigley, David West . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
`
`Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
`
`APPLE EXHIBIT 1013
`Page 11 of 63
`
`

`

`
`
`Three Step Bluetooth Positioning
`
`Alessandro Genco
`
`University of Palermo, Department of Computer Engineering,
`Viale delle Scienze, edificio 6, 90128 Palermo, Italy
`genco@unipa.it
`
`Abstract. This paper discusses a three step procedure to perform high
`definition positioning by the use of low cost Bluetooth devices. The three steps
`are: Sampling, Deployment, and Real Time Positioning. A genetic algorithm is
`discussed for deployment optimization and a neural network for real time
`positioning. A case study, along with experiments and results, are finally
`discussed dealing with a castle in Sicily where many trials were carried out to
`the end of arranging a positioning system for context aware service provision to
`visitors.
`
`1 Introduction
`
`Many pervasive computing applications rely on real time location to start and manage
`interaction with people in a detected area. Time and space information are therefore
`basic elements in arranging mobile context aware services which take into account
`context factors such as who, why, where, when. Dealing with wide areas, multiple
`interaction devices, such as remote multi-displays, could be available in one service
`hall. In such cases a pervasive system can start interaction with who explicitly
`addresses a selected device by means of some manual action on a touch screen or a
`mouse, or by means of some voice sound. Nevertheless, there are some kinds of
`application, as for instance advertising messages, which require interaction to start
`autonomously. People who are around should be attracted by some customized
`message exactly arranged on his personal profile and current position in a display
`neighborhood.
`We may feel some worry in looking at a pervasive system as a big brother;
`however there is some convenience for us in customized services and furthermore,
`such an interaction modality could be the one preferred by people, because it does not
`require any manual action to be performed. Once preserved the not invasive
`requirement of pervasive applications, it is undoubted that system proactive behavior
`could be a general suitable approach to mobile human computer interaction.
`Besides the problem of selecting the nearest interaction device, position aware
`services may need to rely on position data which must be more accurate than simple
`location. There are several pervasive applications indeed, which require a maximum
`error in position coordinates to be kept very low, less than one meter for instance.
`This is the case of a security system, which is arranged to protect an area around a
`
`T. Strang and C. Linnhoff-Popien (Eds.): LoCA 2005, LNCS 3479, pp. 52 – 62, 2005.
`© Springer-Verlag Berlin Heidelberg 2005
`
`APPLE EXHIBIT 1013
`Page 12 of 63
`
`

`

`
`
`Three Step Bluetooth Positioning
`
`53
`
`precious artifact. There are also some cases which require additional position data,
`like the human body compass angle. People who are looking at an object, as for
`instance visitors who are looking at an artifact, or factory operators who are checking
`some manufacturing process could be provided with context aware information which
`take into account who is looking at what.
`The above two basic positioning elements are to be used in conjunction with a
`higher level point of view to allow a system to arrange those services someone may
`expect in a given reality [1], [2], [3].
`
`2 Why Bluetooth
`
`We used Bluetooth (IEEE802.15.1) in our positioning experiments because of two
`main reasons. One is that Bluetooth technology is widely implemented in
`cellular/smart phones, thus being something quite chip and wearable, and therefore
`very easy to own. The other reason is that the Bluetooth (BT) technology embedded
`in cellular phones, allows distances to be estimated by link quality values within a BT
`covered area which we can suppose to be a 30~40 m. circle approximately. We have
`also to mention some problems encountered in using cellular embedded Bluetooth
`devices which mostly deal with BT service implementation by different brand
`factories. In many cases we had to deal with compatibility problems or service
`restrictions.
`However, given the Bluetooth amazing commercial success, we can hope in near
`future to deal with standardized Bluetooth services.
`Actually, WiFi (IEEE802.11x) can also be used for positioning, as well as any
`other RF communication
`technology which provides
`link quality values.
`Nevertheless, most of positioning problems which come from link quality measure
`unreliability, can be discussed with similar considerations for a class of technologies.
`Therefore, apart some different featuring specifications, discussions on Bluetooth can
`be considered as representative of a group of communication technologies which are
`capable of providing positioning information.
`
`
`Fig. 1. An Iso-LQ curve
`
`
`
`
`
`
`
`APPLE EXHIBIT 1013
`Page 13 of 63
`
`

`

`54
`
`A. Genco
`
`An actual problem of positioning by RF communication technologies comes from
`estimating distances on link quality measurements, which are affected by a high
`degree of uncertainty. Measured RF link quality equal values actually draw a region
`which is very unlikely to be a circle because of obstacles and noises. Therefore,
`position estimation by triangulation, even performed on more than three reference
`nodes, cannot be accurate. An irregular-shaped region around a RF terminal (Fig. 1) is
`a more realistic case to be tackled by means of methods which are capable of dealing
`with uncertainty and site depending solutions.
`Distance estimation between a mobile device and a number of reference devices
`whose location is known is a research topic of several approaches [4]. Some
`contributions can be found in literature with the end of arranging solutions to be free
`from site noises.
`Among these, ActiveBats [5] and Cricket [6] are based on ultrasound time-of-flight
`lateration, with an accuracy of few cm or less. The time-of-flight method estimates
`distance between a moving object and a fixed point by measuring the time a signal
`takes to travel from the object and the fixed point at a known speed. This method
`could be a good one because time of flight and distance have a reliable relationship.
`The actual problem is in clock accuracy requirement. A 1 μs error in timing leads to a
`300 m error in distance estimation.
`The Ascension Technology MotionStar system [7] is based on magnetic sensors
`moving in a magnetic field around their source. This system provides a very high
`accuracy but needs very expensive hardware.
`RX power level positioning method is quite similar to TOA positioning. Both
`methods locate mobile devices on the intersection of three (or more) circles. The
`circles radius is evaluated on the measured strength of received signals, thus assuming
`a direct relationship between signal strength and distance which unfortunately, as said
`above, can be affected by obstacles and noises.
`The Angle Of Arrival (AOA) method processes the direction of a received signal.
`Position is estimated by triangulation when two reference devices at least measure the
`signal angle of arrival from a mobile device [8]. This method obviously requires some
`expensive hardware to evaluate angles of arrival.
`The Cell Identity (CI) method looks at the network as divided into cells, each cell
`being the radio coverage area of a single reference device. A mobile device connected
`to a given reference device is assumed to be inside its cell. Cells overlapping and
`connectivity-induced geometric constraints can improve accuracy [8]. One more time,
`as mentioned above, radio coverage cannot be assumed to be a circle and therefore
`accuracy cannot be high.
`
`3 Bluetooth Positioning
`
`Hallberg et al. [9] developed two different methods based on BT Received Signal
`Strength Indicator (RSSI) values: the direct method, which requires a BT device to be
`programmed, and the indirect method, without any programming being needed. The
`
`
`
`APPLE EXHIBIT 1013
`Page 14 of 63
`
`

`

`
`
`Three Step Bluetooth Positioning
`
`55
`
`first one gives a good accuracy by programmable hardware. The second one is
`cheaper, but its accuracy is very poor, with a worst-case error of 10 meters.
`SpotOn [10] and MSR RADAR [11] are based on RF signal power level
`measurement. They process the RSSI (Received Signal Strength Information) value to
`give an accuracy of 3-4 meters or more.
`The BT Local Positioning Application (BLPA) [12] uses RSSI values to feed an
`extended Kalman filter for distance estimation. A good accuracy is achieved only by
`theoretical RSSI values, while unreliability of actual values gives unreliable distance
`estimation. The BT Indoor Positioning System (BIPS) [13] is designed for tracking
`mobile devices in motion inside a building. The BIPS main task is real-time tracking
`of visitors in a building. This led researchers to deal mainly with timing and device
`discovering, thus achieving an accuracy of 10 meters.
`Finally, Michael Spratt [14] proposed the Positioning by Diffusion method based
`on information transferred across short-range wireless links. Distance estimation is
`achieved by geometric or numeric calculations.
`
`4 Three Step BT Positioning
`
`BT devices measure RX power level by using both RSSI and Link Quality (LQ)
`parameters. These are implemented in the BT module and can be read through HCI
`(Host Controller Interface) commands [15]. LQ is a quite reliable parameter for
`distance estimation, differently RSSI only allows to know whether a device is in a
`given base station power range or not [16]. The use of LQ is recommended by the BT
`standard specifications, so it is available on most commercial devices. LQ represents
`the quality of a link in a range from 0 to 255, and a correlation can be assumed
`between distances and LQ values. We know LQ values are not reliable in measuring
`distances. Therefore, we need to avoid geometrical concerns and let a BT positioning
`system to take advantage from LQ values to be processed according to their site
`depending specificity. Here we discuss a three step procedure which turned out to be
`capable of providing high definition positioning by the use of low cost BT devices.
`The three steps are: site LQ sampling, BT base station deployment, and finally, real
`time positioning.
`
`4.1 Positioning Step 1: Site Sampling
`
`The end of this step is to collected a first sample of LQ measures to allow us to attach
`a set of LQ ranges to each cell. A range is a set of three values: the lowest, the highest
`and the mean value of all LQ values measured in a cell from a given BT base station
`in one point.
`The site we investigated is the Manfredi’s Castle in Mussomeli - Italy (Fig. 2a),
`whose map is sketched in Fig. 2b. We split the tourist area in a number of cells, which
`are rooms, roads, and areas around artifacts. There are two cell types: cells that
`represent rooms, parts of large rooms, or parts of roads; and cells which represent
`sub-areas around columns, portals, or other artifacts. We assumed an irregular
`
`
`
`
`APPLE EXHIBIT 1013
`Page 15 of 63
`
`

`

`56
`
`A. Genco
`
`Fig. 2a. Manfredi’s Castle in Mussomeli (Italy)
`
`
`
`1. External wall door
`2. Stable
`3. Castle entrance
`4. Courtyard
`5. Big arc
`6. Vestibule
`7. Gothic portal
`8. Barons Hall
`9. Destroyed bodies
`10. Three women room
`11. Chimney hall1
`12. Cross vault halls
`13. Semicircular Turret
`14. Maid lodging
`15. Male
`16. Chapel
`17. Polygonal external wall
`18. External wall stable
`19. Hayloft
`20. Defense fencing
`21. Double lancet windows
`
`
`Fig. 2b. Castle map
`
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1013
`Page 16 of 63
`
`

`

`
`
`Three Step Bluetooth Positioning
`
`57
`
`
`
`Fig. 3. Cells layout
`
`
`
`quadrilateral shape for the first kind of cell, a width (typically a diagonal), and a
`maximum error of 1 meter. Differently, we assumed a circular shape for the second
`type, a diameter of 2 meters, and a maximum error of 0.5 meters.
`Fig. 3 sketches the cells layout. Blue points are centers of circular cells; red points
`are places where Bluetooth base stations (BT-BS) are allowed to be put.
`The analysis of this first set of measures suggested us some considerations. One is
`that is very hard to find any correlation between obstacles and link quality. Some
`walls turned out to stop BT coverage; other walls seemed to be glass or air. Only very
`deep walls or floors turned out to completely stop BT coverage. For instance, BT-
`BS’s which were placed in lower floor areas, did not read any LQ value from mobile
`terminals (BT-MT) moving on higher floor areas, and vice-versa.
`Mainly due to the end of dealing with indoor and outdoor areas separately, we
`decided to split the site area in two sub-areas (green dotted line in Fig. 3). The results
`of these measurements are in a matrix whose generic (i,j) element contains a LQ
`values range measured from the BT-BS at the ith position to the BT-MT moving
`within the jth cell. A range can also be read as an estimation of the maximum
`theoretical accuracy in a cell (8 LQ units in a 2 m. cell cannot give an accuracy
`greater than 2/8 m.). A generic (i,j) range set to [0,0] tells us that the BT-BS placed at
`the ith position cannot detect any BT-MT in the jth cell. Table 1 shows part of the
`output file, where rows are for NS possible stations, and columns are for NA areas.
`
`
`
`
`
`APPLE EXHIBIT 1013
`Page 17 of 63
`
`

`

`58
`
`A. Genco
`
`(cid:3)
`(cid:20)(cid:3)
`(cid:21)(cid:3)
`(cid:29)(cid:3)
`(cid:49)(cid:54)(cid:16)(cid:20)(cid:3)
`(cid:49)(cid:54)(cid:3)
`
`(cid:20)(cid:3)
`(cid:19)(cid:15)(cid:19)(cid:3)
`(cid:19)(cid:15)(cid:19)(cid:3)
`(cid:171)(cid:3)
`(cid:21)(cid:20)(cid:19)(cid:15)(cid:21)(cid:20)(cid:21)(cid:3)
`(cid:21)(cid:23)(cid:19)(cid:15)(cid:21)(cid:24)(cid:19)(cid:3)
`
`Table 1. LQ Ranges
`
`(cid:21)(cid:3)
`(cid:20)(cid:25)(cid:19)(cid:15)(cid:20)(cid:25)(cid:24)(cid:3)
`(cid:20)(cid:27)(cid:19)(cid:15)(cid:20)(cid:27)(cid:27)(cid:3)
`(cid:171)(cid:3)
`(cid:20)(cid:28)(cid:19)(cid:15)(cid:21)(cid:19)(cid:24)(cid:3)
`(cid:20)(cid:27)(cid:20)(cid:15)(cid:20)(cid:27)(cid:24)(cid:3)
`
`(cid:171)(cid:3)
`(cid:171)(cid:3)
`(cid:171)(cid:3)
`(cid:171)(cid:3)
`(cid:171)(cid:3)
`(cid:171)(cid:3)
`
`(cid:49)(cid:36)(cid:16)(cid:20)(cid:3)
`(cid:20)(cid:25)(cid:20)(cid:15)(cid:20)(cid:27)(cid:24)(cid:3)
`(cid:20)(cid:28)(cid:24)(cid:15)(cid:21)(cid:22)(cid:19)(cid:3)
`(cid:171)(cid:3)
`(cid:19)(cid:15)(cid:19)(cid:3)
`(cid:19)(cid:15)(cid:19)(cid:3)
`
`(cid:49)(cid:36)(cid:3)
`(cid:20)(cid:25)(cid:22)(cid:15)(cid:20)(cid:26)(cid:24)(cid:3)
`(cid:21)(cid:19)(cid:20)(cid:15)(cid:21)(cid:24)(cid:24)(cid:3)
`(cid:171)(cid:3)
`(cid:20)(cid:23)(cid:24)(cid:15)(cid:20)(cid:24)(cid:25)(cid:3)
`(cid:19)(cid:15)(cid:19)(cid:3)
`
`4.2 Positioning Step 2: BT Base Station Deployment
`
`Several BT positioning experiments were carried out according to different
`positioning methods, namely triangulation [16], fuzzy logic [17] and neural network.
`A common result of these experiments is that positioning accuracy can be heavily
`affected by erroneous arrangements of the available base stations. Actually, we are
`unlikely to be allowed to put a base station in the middle of a room, for instance, and
`further constraints may come when dealing with a heritage site; base stations should
`be invisible and only selected places are available. Therefore, a relevant step in
`arranging a BT positioning system should be to optimize BT-BS deployment in a
`subset of places which are the only ones permitted by site specific constraints. The
`problem can be enounced in the following terms: given the total number of places
`where a base station can be put, select a minimal subset which allows the system to
`evaluate the position of a BT mobile terminal in any part of the site, with the highest
`accuracy degree.
`Many optimization methods can be used to this end; we used a genetic algorithm
`because of its easy scalability. Each possible deployment is represented by an
`individual chromosome of a population. A chromosome has as many genes as places
`where BT-BS can be put. Each gene represents a possible BT-BS position, which can
`be set either to true if a BT-BS is placed in that position, or to false.
`
`f
`
`t
`
`f
`
`f
`
`f
`
`t
`
`f
`t
`-
`-
`-
`-
`t
`f
`t
`Fig. 4. Deployment Chromosome
`
`f
`
`t
`
`t
`
`f
`
`t
`
`f
`
`An acceptable solution has to return a deployment layout whose coverage is unique
`for all areas, also achieving a required accuracy.
`An optimal solution maximizes coverage quality, and minimizes the number of
`BT-BS required. The quality index of each station-area couple (s,a) is defined by the
`ratio (1) with na being the number of sub-areas to be singled out by positioning.
`−
`+
`
`a
`
`nL
`
`Q
`inf
`
`]
`
`,
`as
`
`1
`
`
`
`
`
`
`
`(1)
`
`[
`
`LQ
`sup
`
`=
`
`q
`
`,
`as
`
`
`
`
`
`APPLE EXHIBIT 1013
`Page 18 of 63
`
`

`

`
`
`Three Step Bluetooth Positioning
`
`59
`
`Each deployment chromosome includes a number of BT-BS, along with their qs,a
`value. The chromosome quality takes into account all qs,a values, which represent the
`contribution of each BT-BS s to the whole chromosome quality.
`
`4.2.1 Some Genetic Algorithm Details
`We start generating a population of 50 chromosomes and assigning each gene a
`probability p to be included in a chromosome. Each chromosome is checked for
`acceptability and fitness value.
`Once the initial population is generated, evolution starts. A maximum of 10
`chromosomes are killed each step (20% of population) depending on age. Each
`chromosome has a percentage probability to die which is equal to its age. So, if a
`chromosome is 20, it has a 20% probability to die. A constant number of surviving
`chromosomes are then coupled to generate new chromosomes thus replacing the
`killed ones. Coupling is performed according to a one-point-crossover and alternating
`gene exchange (one time the initial part and one time the final part). The evolution
`steps are repeated 1000 times.
`A best solution is detected at each evolution step,