The facility location problem is the task of optimally placing a given number of facilities in a certain subset of the plane. In this thesis, we present various mathematical programming formulations of the planar facility location problem, where potential facility locations are not specified. We first consider mixed-integer programming formulations of the planar facility locations problems with squared Euclidean and rectangular distance metrics to solve this problem to provable optimality. We also investigate a heuristic approach to solving the problem by extending the $K$-means clustering algorithm and formulating the facility location problem as a variant of a semidefinite programming problem, leading to a relaxation algorithm. We present computational results for the mixed-integer formulations, as well as compare the objective values resulting from the relaxation algorithm and the modified $K$-means heuristic. In addition, we briefly discuss some of the practical issues related to the facility location model under the continuous customer distribution.

With the advance of location technologies, people can now determine their location in various ways, for instance, with GPS or based on nearby cellphone towers. These technologies have led to the introduction of location-based services, which allow people to get information relevant to their current location. Location privacy is of utmost concern for such location-based services, since knowing a person's location can reveal information about her activities or her interests. In this thesis, we first focus on location-based services that need to know only a person's location, but not her identity. We propose a solution using location cloaking based on k-anonymity, which requires neither a single trusted location broker, which is a central server that knows everybody's location, nor trust in all users of the system and that integrates nicely with existing infrastructures. We present two such protocols. The evaluation of our sample implementation demonstrates that one of the protocol is sufficiently fast to be practical, but the performance of the other protocol is not acceptable for its use in practice. In addition to the distributed k-anonymity protocol we then propose four protocols---Louis, Lester, Pierre and Wilfrid--- for a specific, identity required, location-based service: the nearby-friend application, where users (and their devices) can learn information about their friends' location if and only if their friends are actually nearby. Our solutions do not require any central trusted server or only require a semi-trusted third party that dose not learn any location information. Moreover, users of our protocol do not need to be members of the same cellphone provider, as in existing approaches. The evaluation on our implementation shows that all of the four protocols are efficient.

Recent technological advances in wireless communication and the pervasiveness of various wireless communication devices have offered novel and promising solutions to enable vehicles to communicate with each other, establishing a decentralized communication system. An emerging solution in this area is the Vehicular Ad Hoc Networks (VANETs), in which vehicles cooperate in receiving and delivering messages to each other. VANETs can provide a viable alternative in situations where existing infrastructure communication systems become overloaded, fail (due for instance to natural disaster), or inconvenient to use. Nevertheless, the success of VANETs revolves around a number of key elements, an important one of which is the way messages are routed between sources and destinations. Without an effective message routing strategy VANETs' success will continue to be limited. In order for messages to be routed to a destination effectively, the location of the destination must be determined. Since vehicles move in relatively fast and in a random manner, determining the location (hence the optimal message routing path) of (to) the destination vehicle constitutes a major challenge. Recent approaches for tackling this challenge have resulted in a number of Location Service Management Protocols. Though these protocols have demonstrated good potential, they still suffer from a number of impediments, including, signaling volume (particularly in large scale VANETs), inability to deal with network voids and inability to leverage locality for communication between the network nodes. In this thesis, a Region-based Location Service Management Protocol (RLSMP) is proposed. The protocol is a self-organizing framework that uses message aggregation and geographical clustering to minimize the volume of signalling overhead. To the best of my knowledge, RLSMP is the first protocol that uses message aggregation in both updating and querying, and as such it promises scalability, locality awareness, and fault tolerance. Location service management further addresses the issue of routing location updating and querying messages. Updating and querying messages should be exchanged between the network nodes and the location servers with minimum delay. This necessity introduces a persuasive need to support Quality of Service (QoS) routing in VANETs. To mitigate the QoS routing challenge in VANETs, the thesis proposes an Adaptive Message Routing (AMR) protocol that utilizes the network's local topology information in order to find the route with minimum end-to-end delay, while maintaining the required thresholds for connectivity probability and hop count. The QoS routing problem is formulated as a constrained optimization problem for which a genetic algorithm is proposed. The thesis presents experiments to validate the proposed protocol and test its performance under various network conditions.

In today’s society, more of the population is finding itself with multiple points of reference to what they consider as home. Anyone who finds they have more than one place that they feel tied to for one reason or another, considers the impact of these places on their identity. The scale of experience with the places where we live, visit and grow up influences the scale of impact upon our identity. Even a vacation or a visit to a certain place influences us, and thus also changes the place because we interact with it. I am showing, through sculptural and creative media, the layering effect of locational identity and the journeys we make to physically and conceptually link those identities.

The facility location problem is the task of optimally placing a given number of facilities in a certain subset of the plane. In this thesis, we present various mathematical programming formulations of the planar facility location problem, where potential facility locations are not specified. We first consider mixed-integer programming formulations of the planar facility locations problems with squared Euclidean and rectangular distance metrics to solve this problem to provable optimality. We also investigate a heuristic approach to solving the problem by extending the $K$-means clustering algorithm and formulating the facility location problem as a variant of a semidefinite programming problem, leading to a relaxation algorithm. We present computational results for the mixed-integer formulations, as well as compare the objective values resulting from the relaxation algorithm and the modified $K$-means heuristic. In addition, we briefly discuss some of the practical issues related to the facility location model under the continuous customer distribution.

With the advance of location technologies, people can now determine their location in various ways, for instance, with GPS or based on nearby cellphone towers. These technologies have led to the introduction of location-based services, which allow people to get information relevant to their current location. Location privacy is of utmost concern for such location-based services, since knowing a person's location can reveal information about her activities or her interests. In this thesis, we first focus on location-based services that need to know only a person's location, but not her identity. We propose a solution using location cloaking based on k-anonymity, which requires neither a single trusted location broker, which is a central server that knows everybody's location, nor trust in all users of the system and that integrates nicely with existing infrastructures. We present two such protocols. The evaluation of our sample implementation demonstrates that one of the protocol is sufficiently fast to be practical, but the performance of the other protocol is not acceptable for its use in practice. In addition to the distributed k-anonymity protocol we then propose four protocols---Louis, Lester, Pierre and Wilfrid--- for a specific, identity required, location-based service: the nearby-friend application, where users (and their devices) can learn information about their friends' location if and only if their friends are actually nearby. Our solutions do not require any central trusted server or only require a semi-trusted third party that dose not learn any location information. Moreover, users of our protocol do not need to be members of the same cellphone provider, as in existing approaches. The evaluation on our implementation shows that all of the four protocols are efficient.

Recent technological advances in wireless communication and the pervasiveness of various wireless communication devices have offered novel and promising solutions to enable vehicles to communicate with each other, establishing a decentralized communication system. An emerging solution in this area is the Vehicular Ad Hoc Networks (VANETs), in which vehicles cooperate in receiving and delivering messages to each other. VANETs can provide a viable alternative in situations where existing infrastructure communication systems become overloaded, fail (due for instance to natural disaster), or inconvenient to use. Nevertheless, the success of VANETs revolves around a number of key elements, an important one of which is the way messages are routed between sources and destinations. Without an effective message routing strategy VANETs' success will continue to be limited. In order for messages to be routed to a destination effectively, the location of the destination must be determined. Since vehicles move in relatively fast and in a random manner, determining the location (hence the optimal message routing path) of (to) the destination vehicle constitutes a major challenge. Recent approaches for tackling this challenge have resulted in a number of Location Service Management Protocols. Though these protocols have demonstrated good potential, they still suffer from a number of impediments, including, signaling volume (particularly in large scale VANETs), inability to deal with network voids and inability to leverage locality for communication between the network nodes. In this thesis, a Region-based Location Service Management Protocol (RLSMP) is proposed. The protocol is a self-organizing framework that uses message aggregation and geographical clustering to minimize the volume of signalling overhead. To the best of my knowledge, RLSMP is the first protocol that uses message aggregation in both updating and querying, and as such it promises scalability, locality awareness, and fault tolerance. Location service management further addresses the issue of routing location updating and querying messages. Updating and querying messages should be exchanged between the network nodes and the location servers with minimum delay. This necessity introduces a persuasive need to support Quality of Service (QoS) routing in VANETs. To mitigate the QoS routing challenge in VANETs, the thesis proposes an Adaptive Message Routing (AMR) protocol that utilizes the network's local topology information in order to find the route with minimum end-to-end delay, while maintaining the required thresholds for connectivity probability and hop count. The QoS routing problem is formulated as a constrained optimization problem for which a genetic algorithm is proposed. The thesis presents experiments to validate the proposed protocol and test its performance under various network conditions.

The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

Mining operations can produce highly localized, low intensity earthquakes that are referred to as microseismic events. Monitoring of microseismic events is useful in predicting and comprehending hazards, and in evaluating the overall performance of a mine design. <p>A robust localization algorithm is used to estimate the source position of the microseismic event by selecting the hypothesized source location that maximizes an energy function generated from the sum of the time--aligned sensor signals. The accuracy of localization for the algorithm characterized by the variance depends in part upon the configuration of sensors. Two algorithms, MAXSRC and MINMAX, are presented that use the variance of localization error, in a particular direction, as a performance measure for a given sensor configuration.<p>The variance of localization error depends, in part, upon the energy spectral density of the microseismic event. The energy spectral density characterization of sensor signals received in two potash mines are presented and compared using two spectral estimation techniques: multitaper estimation and combined time and lag weighting. It is shown that the difference between the the two estimation techniques is negligible. However, the differences between the two mine characterizations, though not large, is significant. An example uses the characterized energy spectral densities to determine the variance of error for a single step localization algorithm.<p>The MAXSRC and MINMAX algorithms are explained. The MAXSRC sensor placement algorithm places a sensor as close as possible to the source position with the maximum variance. The MINMAX sensor placement algorithm minimizes the variance of the source position with the maximum variance after the sensor has been placed. The MAXSRC algorithm is simple and can be solved using an exhaustive search while the MINMAX algorithm uses a genetic algorithm to find a solution. These algorithms are then used in three examples, two of which are simple and synthetic. The other example is from Lanigan Potash Mine. The results show that both sensor placement algorithms produce similar results, with the MINMAX algorithm consistently doing better. The MAXSRC algorithm places a single sensor approximately 100 times faster than the MINMAX algorithm. The example shows that the MAXSRC algorithm has the potential to be an efficient and intuitively simple sensor placement algorithm for mine microseismic event monitoring. The MINMAX algorithm provides, at an increase in computational time, a more robust placement criterion which can be solved adequately using a genetic algorithm.

This thesis investigates the suitability of global navigation satellite system (GNSS) signals for cellular phone location. The requirement is to determine and report the location of a phone during an emergency call.<p> The thesis analyzes acquisition and tracking techniques suitable for very weak signals as received by a cellular phone indoors. The L1 and L5 signals from GPS satellites and the L1 signal from Galileo satellites are considered. It is shown that long integration times and coherent integration are required for the weakest expected signals. Long coherent integration times require a precise knowledge of the Doppler shift due to the range rate of the satellite. The tolerance to Doppler shift can be increased by using FFTs in the analysis of the data. Non-coherent averaging techniques improve the Doppler tolerance but compared to coherent averaging, the loss of signal to noise ratio is too large for the weakest signals.<p> Coherent averaging of the GPS L1 signal requires data removal that can be accomplished with assistance from the cellular network. The GPS L5 and Galileo L1 signals include a data-less or pilot channel. The GPS L5 pilot channel includes a 20 bit Neuman Hoffman code with a bit period of 1 ms. This code has to be acquired or removed before coherent averaging. Similarly the Galileo pilot channel includes a 25 bit short code.<p> Once code acquisition has been accomplished, it is necessary to track the signals from at least four satellites for long enough to compute a position estimate. A discussion of tracking techniques is included to show the signal to noise ratio limitations for adequate tracking accuracy.<p> The results show that GNSS signals are suitable for cellular phone location in a large number of situations. Increased receiver sensitivity would permit location in additional situations. In rural situations GNSS may be the only available option.