For thousands of years, location information has been used for navigation. This has changed in the last century as advances in wireless communication and microelectronics have given birth to mobile computing devices. These devices enable their users to access sensing and computing capabilities from anywhere and at any time. An important consequence of such mobility is that the resource and information needs of wireless users are no longer fixed but vary with their changing location and, more generally, with their changing context. This has sparked a new generation of applications that employ location information to cater to the changing needs of mobile users. These applications, known as location-based services (LBS), are offered on top of wireless communication infrastructures to add value to existing services.

To enable and support the delivery of LBS, accurate, reliable, and realtime user location information is needed. This need has incited a new interest in positioning and tracking systems whose aim is to determine the physical coordinates of a wireless mobile device carried by a human user. The focus of this book is one class of positioning systems that employ radio signals from wireless local area networks (WLAN) for positioning. These systems are of special interest as they are able to provide high positioning accuracies in indoor and outdoor environments with minimal deployment and maintenance costs.

This book is divided into two parts. The first part focuses on topics related to the history and applications of positioning systems.

Chapter 3 detailed the fundamental techniques used in positioning. In this chapter, we review several examples of existing positioning systems that use these techniques. In particular, we focus on wireless positioning systems to motivate wireless local area network positioning. We discuss the Global Positioning System (Section 4.1) and cellular positioning (Section 4.2) as examples of positioning systems used in outdoor environments, and positioning based on ultrasound and infrared (Section 4.3) as examples of indoor positioning systems. We then proceed to motivate and describe positioning systems employing wireless local area networks (Section 4.4). Finally, we conclude the chapter by comparing the advantages offered by each system.

The Global Positioning System

Historical perspective

In 1957, the first artificial satellite known as Sputnik I was launched into the earth's orbit by the Soviet Union. Within days of the launch, scientists at Johns Hopkins University noted that they could determine the position of the satellite based on the Doppler shift associated with its radio transmissions. What was even more interesting was that if the position of the satellite were known, this Doppler shift could be used to determine the position of a satellite receiver on earth. This observation ushered in the development of global navigation satellite systems (GNSS).

The first operational satellite-based positioning system was Transit, also known as the Navy Navigation Satellite System (NAVSAT). This system was primarily used for military operations by the United States Navy.

In the previous chapters, we addressed the problem of position estimation given values of received signal strength (RSS). In this chapter, we focus on the architectural and system design aspects of a positioning solution.

We begin by outlining the five design issues that must be considered in WLAN positioning systems (Section 9.1). We then proceed to discuss architectural details of three functional modules of positioning systems, namely sensing, computation, and storage (Sections 9.2, 9.3, 9.4, and 9.5).

Design issues

Before proceeding to a discussion of the design of an RSS-based positioning system in detail, let us provide an overview of five key design challenges in these systems.

Limited communication bandwidth

Communication via wireless channels imposes severe limitations on the available band-width (5 and 11 Mbps for an IEEE 802.11b wirelessLAN[81]). This is due to the intensity drop as a function of the fourth power of the distance, the presence of obstructing objects (shadowing effects), and multipath fading [69]. As a result, RSS-based positioning systems must be designed in such a way as to minimize the number and frequency of wireless communications.

Distributed operation

Because communication is much more expensive than most processing operations, it is highly desirable for the processing to take place in a distributed manner to reduce traffic volume and energy costs [69]. Also, in large environments, access and anchor points are distributed over a large geographical area.

In the first part of this book, we motivated the need for accurate and cost-effective positioning systems that can enable the delivery of location-based services (LBS). Moreover, we suggested positioning based on wireless local area networks as a cost-effective and reliable solution for supporting such services in indoor environments. The second part of this book provides an in-depth treatment of the technical fundamentals of these systems. This chapter will begin by providing an overview of wireless local area networks (Section 5.1) and the radio features that can be used for positioning in these networks (Section 5.2). After motivating the use of received signal strength as the feature of choice for positioning, we proceed to describe the details of the experimental data set used for illustrating various concepts in this book (5.3). This is followed by a discussion of the spatial and temporal properties of received signal strength (Section 5.4), challenges in using this radio feature (Section 5.6), and techniques for modeling the relationship between received signal strength and position (Section 5.5).

Wireless local area networks

Wireless local area networks (WLANs) are radio-based communication network infrastructures based on the IEEE 802.11 family of standards. These networks operate in the unlicensed frequency bands [27], primarily employing the 2.4 GHz ISM band. As shown in Figure 5.1, WLANs use an architecture that relies on a set of base-stations for facilitating communication among the devices within the network, and between the network and the outside world (for example, the Internet).

The objective of a positioning system is to determine the position of a mobile device. This position, however, is not directly observable and must be determined based on some observable measurement. In the case of RSS-based positioning, this observable measurement is the received signal strength (RSS) at the mobile device. If the relationship between the RSS values and the position of mobile devices were known, the positioning problem would be trivial. However, as discussed in Chapter 5, this relationship is not deterministic in practice, but depends on the stochastic characteristics of the propagation environment. Consequently, the unknown position can only be estimated using RSS measurements. The focus of this chapter is the various estimation methods used to accomplish this task. In particular, this chapter focuses on memoryless estimators, which rely on an RSS measurement at a given time to compute the position estimate at that time. In other words, memoryless estimators do not consider the past history of user positions or RSS measurements during estimation.

We begin this chapter by developing a mathematical formulation of the memoryless positioning problem (Section 6.1) and show that this problem reduces to a density estimation problem. We next review two methods for density estimation based on the implicit training information provided in the radio map (Section 6.2). Using these density estimation techniques, we proceed to develop several position estimators (Sections 6.3 and 6.4). Finally, we conclude the chapter with the presentation of some experimental results (Section 6.5).

Positioning systems employ information from a large number of access points and anchor points distributed over large areas to locate a mobile device. In order to form a position estimate, the system must combine or fuse the information provided by these sources to make inferences regarding the location of a mobile device. Fusion of data from multiple sources is not a trivial task as redundancy and conflict among the information can significantly affect the accuracy and reliability of the final estimate. In the context of positioning, data fusion is especially challenging as the unreliable and time-varying nature of the radio-propagation channel means that erroneous and out-of-date information may be received from access and anchor points. In this Chapter, we focus on one data fusion challenge, namely sensor selection. In our context, sensor selection refers to selecting a subset of the available access and anchor points for positioning.

The rest of this chapter is organized as follows. We begin by motivating sensor selection for WLAN-based positioning (Section 8.1). We then proceed to discuss several methods for access point and anchor point selection (Sections 8.2 and 8.3). We conclude this chapter by illustrating the benefits of sensor selection using experimental data (Section 8.4).

Motivation

In WLAN-positioning, information from multiple anchor points and access points is fused to form a position estimate. Careful selection of the sensors that contribute to positioning can benefit RSS-based positioning in two ways.

Since the first WLAN-positioning system was introduced in 2000 [4], rapid advances in signal processing methods have been made in this area. A decade later, fundamental positioning techniques have matured significantly, allowing these systems to offer highly accurate positioning estimates with accuracies on the order of several meters in both indoor and outdoor environments.

The previous chapters have reviewed the fundamental techniques used in WLAN positioning. In this chapter, we look ahead to opportunities and challenges remaining to be addressed in this area.

Highlights

The focus of this book has been WLAN-based positioning. Chapters 1 to 4 discussed the history, applications, and various positioning systems to motivate these systems. In particular, the development of these systems is motivated by the need for accurate, reliable, and cost-efficient positioning solutions to enable the delivery of location-based services (LBS).

The second part of the book was dedicated to fundamental signal processing concepts in these systems. In Chapter 5, we saw that the unpredictability of radio signal features poses a significant challenge to the development of accurate and reliable WLAN systems. In Chapter 6, we discussed a number of non-parametric techniques that can be used to model these radio signals using training samples collected at a set of anchor points with known locations. In addition to their effectiveness as modeling tools, these nonparametric techniques also allowed the estimation of a measure of uncertainty associated with position estimates.

In the previous chapters, we discussed the history and application of modern positioning systems that enable the delivery of location-based services (LBS). In this chapter, we shift our attention to the fundamental positioning principles used in these systems. We begin this chapter by presenting the location stack, a model of location-aware systems, and identify the focus of this book (Section 3.1). We then proceed to discuss the most commonly used techniques for computing the position of mobile receivers. Similar to the techniques used in celestial navigation, modern positioning systems often employ a set of references with known locations for position computation. In this chapter, we discuss different positioning methods, differentiated by the type of references and signal measurements used (Sections 3.2 to 3.4). In addition to these techniques, which generally employ wireless signals, we will also briefly review dead reckoning (Section 3.6) and computer-based positioning (Section 3.7) methods. These two techniques employ modalities complementary to wireless measurements and as such provide a promising direction of development for hybrid positioning systems that employ multiple measurements to improve the accuracy and reliability of positioning. Finally, we conclude the chapter by discussing the advantages and disadvantages of each positioning method (Section 3.8).

The location stack

To position this book within the wealth of information available on positioning systems used in LBS, we review a model of location-aware systems proposed by Hightower et al. [35].

For thousands of years, the ability to explore the world has significantly impacted human civilization. Human explorations have enabled the interaction of cultures for the purposes of geographic expansion (for example, through war and colonization) and economic development through trade. These interactions have also played a pivotal role in an exchange of knowledge that has supported the advancement of science, the development of religion, and the flourishing of the arts throughout the world.

World exploration is largely enabled by the ability to control the movement of a vessel from one position to another. This process, known as navigation, requires the knowledge of the locations of the source and destination points. The process of determining the location of points in space is known as positioning. In this book, we use the terms location and position interchangeably to refer to the point in physical space occupied by a person or object.

Throughout history, various positioning methods have been developed including methods using the relation of a point to various reference points such as celestial bodies and the Earth's magnetic pole. More recently, the advent of wireless communications has led to the development of a number of additional positioning systems that enable not only navigation, but also the delivery of additional value-added services. The focus of this book is one such positioning method that employs wireless local area signals to determine the location of wireless devices.

Traditionally, the application scope of positioning systems was limited to target tracking and navigation in civilian and military applications. This has changed in past decades with the advent of mobile computing. In particular, the maturation of wireless communication and advances in microelectronics have given birth to mobile computing devices, such as laptops and smart phones, which are equipped with sensing and computing capabilities. The mobility of these computing devices in wireless networks means that users' communication, resource, and information needs now change with their physical location. More specifically, location information is now part of the context in which users access and consume wireless services. This, together with the availability of positioning information (for example, through the Global Positioning System), both necessitated and enabled the development of services that cater to the changing needs of mobile users [34]. This need has sparked a new generation of applications for positioning known as location-based services (LBS) or location-aware systems. Formally, LBS have been defined in many ways [24, 50, 80]. In this book, the term LBS is used to indicate services that use the position of a user to add value to a service [50].

In this chapter, we will discuss the economical and ethical implications of LBS. We begin with an assessment of the market potential for these services (Section 2.1). This is followed by a discussion of application areas where LBS services can be employed (Section 2.2). Finally, we discuss the ethical implications of LBS (Section 2.3).

This chapter describes DryadLINQ, a general-purpose system for large-scale data-parallel computing, and illustrates its use on a number of machine learning problems.

The main motivation behind the development of DryadLINQ was to make it easier for nonspecialists to write general-purpose, scalable programs that can operate on very large input datasets. In order to appeal to nonspecialists, we designed the programming interface to use a high level of abstraction that insulates the programmer from most of the detail and complexity of parallel and distributed execution. In order to support general-purpose computing, we embedded these high-level abstractions in .NET, giving developers access to full-featured programming languages with rich type systems and proven mechanisms (such as classes and libraries) for managing complex, long-lived, and geographically distributed software projects. In order to support scalability over very large data and compute clusters, the DryadLINQ compiler generates code for the Dryad runtime, a well-tested and highly efficient distributed execution engine.

As machine learning moves into the industrial mainstream and operates over diverse data types including documents, images, and graphs, it is increasingly appealing to move away from domain-specific languages like MATLAB and toward general-purpose languages that support rich types and standardized libraries. The examples in this chapter demonstrate that a general-purpose language such as C# supports effective, concise implementations of standard machine learning algorithms and that DryadLINQ efficiently scales these implementations to operate over hundreds of computers and very large datasets primarily limited by disk capacity.

Probabilistic graphical models are used in a wide range of machine learning applications. From reasoning about protein interactions (Jaimovich et al., 2006) to stereo vision (Sun, Shum, and Zheng, 2002), graphical models have facilitated the application of probabilistic methods to challenging machine learning problems. A core operation in probabilistic graphical models is inference – the process of computing the probability of an event given particular observations. Although inference is NP-complete in general, there are several popular approximate inference algorithms that typically perform well in practice. Unfortunately, the approximate inference algorithms are still computationally intensive and therefore can benefit from parallelization. In this chapter, we parallelize loopy belief propagation (or loopy BP in short), which is used in a wide range of ML applications (Jaimovich et al., 2006; Sun et al., 2002; Lan et al., 2006; Baron, Sarvotham, and Baraniuk, 2010; Singla and Domingos, 2008).

We begin by briefly reviewing the sequential BP algorithm as well as the necessary background in probabilistic graphical models. We then present a collection of parallel shared memory BP algorithms that demonstrate the importance of scheduling in parallel BP. Next, we develop the Splash BP algorithm, which combines new scheduling ideas to address the limitations of existing sequential BP algorithms and achieve theoretically optimal parallel performance. Finally, we present how to efficiently implement loopy BP algorithms in the distributed parallel setting by addressing the challenges of distributed state and load balancing.

In this chapter, we address distributed learning algorithms for statistical latent variable models, with a focus on topic models. Many high-dimensional datasets, such as text corpora and image databases, are too large to allow one to learn topic models on a single computer. Moreover, a growing number of applications require that inference be fast or in real time, motivating the exploration of parallel and distributed learning algorithms.

We begin by reviewing topic models such as Latent Dirichlet Allocation and Hierarchical Dirichlet Processes. We discuss parallel and distributed algorithms for learning these models and show that these algorithms can achieve substantial speedups without sacrificing model quality. Next we discuss practical guidelines for running our algorithms within various parallel computing frameworks and highlight complementary speedup techniques. Finally, we generalize our distributed approach to handle Bayesian networks.

Several of the results in this chapter have appeared in previous papers in the specific context of topic modeling. The goal of this chapter is to present a comprehensive overview of distributed inference algorithms and to extend the general ideas to a broader class of Bayesian networks.

Latent Variable Models

Latent variable models are a class of statistical models that explain observed data with latent (or hidden) variables. Topic models and hidden Markov models are two examples of such models, where the latent variables are the topic assignment variables and the hidden states, respectively. Given observed data, the goal is to perform Bayesian inference over the latent variables and use the learned model to make inferences or predictions.

Automatic speech recognition (ASR) allows multimedia contents to be transcribed from acoustic waveforms into word sequences. It is an exemplar of a class of machine learning applications where increasing compute capability is enabling new industries such as automatic speech analytics. Speech analytics help customer service call centers search through recorded content, track service quality, and provide early detection of service issues. Fast and efficient ASR enables economic employment of a plethora of text-based data analytics on multimedia contents, opening the door to many possibilities.

In this chapter, we describe our approach for scalable parallelization of the most challenging component of ASR: the speech inference engine. This component takes a sequence of audio features extracted from a speech waveform as input, compares them iteratively to a speech model, and produces the most likely interpretation of the speech waveform as a word sequence. The speech model is a database of acoustic characteristics, word pronunciations, and phrases from a particular language. Speech models for natural languages are represented with large irregular graphs consisting of millions of states and arcs. Referencing these models involves accessing an unpredictable data working set guided by “what was said” in the speech input. The inference process is highly challenging to parallelize efficiently.

We demonstrate that parallelizing an application is much more than recoding the program in another language. It requires careful consideration of data, task, and runtime concerns to successfully exploit the full parallelization potential of an application.