Modern smartphones and location-based services and apps are poised to transform our daily life. However, current smartphone-based localization solutions are limited mainly to outdoor, mostly missing practical, robust and accurate indoor location solutions. Despite significant efforts on indoor localization in both academia and industry in the past two decades, highly accurate and practical smartphone-based indoor localization remains an open problem. To enable indoor location-based services (ILBS), e.g., step-by-step navigation for the Blind and visually impaired, there are several stringent requirements: highly accurate (foot-level); no additional hardware components or extensions on users' smartphones; scalable to massive concurrent users. Current GPS, Radio RSS (e.g. Wi-Fi, Bluetooth, ZigBee), or Fingerprinting based solutions can only achieve meter-level or room-level accuracy. In this paper, we propose a practical and accurate solution that fills the long-lasting gap of smartphone-based fine-grained indoor localization. Specifically, we design and implement an indoor localization ecosystem Guoguo. Guoguo consists of an anchor network with a coordination protocol to transmit modulated localization beacons using high-band acoustic signals, a realtime processing app in a smartphone, and a backend server for indoor contexts and location-based services. We further propose approaches to improve its coverage, accuracy, and location update rate with low-power consumption. Our prototype shows centimeter-level localization accuracy in several typical indoor environments. Such precise indoor localization is expected to have high impact in the future ILBS and our daily activities.

Application services based on cloud computing infrastructure are proliferating over the Internet. In this paper, we investigate the problem of how to minimize cloud resource rental cost associated with hosting such cloud-based application services, while meeting the projected service demand. This problem arises when applications generate high volume of data that incurs significant cost on storage and transfer. As a result, an application service provider (ASP) needs to carefully evaluate various resource rental options before finalizing the application deployment. We choose Amazon EC2 marketplace as a case of study, and analyze the economical trade-off for on-demand resource rental strategies. Given fixed resource pricing, we first develop a deterministic model, using a mixed integer linear program, to facilitate resource rental decision making. Evaluation results show that our planning optimization model reduces resource rental cost by as much as 50 percent compared with a baseline strategy. Next, we further investigate planning solutions to resource market featuring time-varying pricing (Amazon Spot Instance Market). We perform time-series analysis over the spot price trace and examine its predictability using auto-regressive integrated moving-average (ARIMA). We also develop a stochastic planning model based on multistage recourse. By comparing these two approaches, we discover that spot price forecasting does not provide our planning model with a crystal ball due to the weak correlation of past and future price, and the stochastic planning model better hedges against resource pricing uncertainty than resource rental planning using forecast prices.

Location Based Service (LBS), although it greatly benefits the daily life of mobile device users, has introduced significant threats to privacy. In an LBS system, even under the protection of pseudonyms, users may become victims of inference attacks, where an adversary reveals a user's real identity and complete moving trajectory with the aid of side information, e.g., accidental identity disclosure through personal encounters. To enhance privacy protection for LBS users, a common approach is to include extra fake location information associated with different pseudonyms, known as dummy users, in normal location reports. Due to the high cost of dummy generation using resource constrained mobile devices, self-interested users may free-ride on others' efforts. The presence of such selfish behaviors may have an adverse effect on privacy protection. In this paper, we study the behaviors of self-interested users in the LBS system from a game-theoretic perspective. We model the distributed dummy user generation as Bayesian games in both static and timing-aware contexts, and analyze the existence and properties of the Bayesian Nash Equilibria for both models. Based on the analysis, we propose a strategy selection algorithm to help users achieve optimized payoffs. Leveraging a beta distribution generalized from real-world location privacy data traces, we perform simulations to assess the privacy protection effectiveness of our approach. The simulation results validate our theoretical analysis for the dummy user generation game models.

Since our daily activities are dominantly indoor, as smart phones emerge as the most popular personal computing companions, major IT companies recently launched aggressive investment on mobile indoor location services and positioning systems, e.g., on iOS or Android mobile devices. However, one major hurdle has not been conquered yet: smart phone-based high-resolution indoor localization. In this paper, we propose a practical solution for accurate ranging and localization based on acoustic communication between anchor nodes with speakers and the microphone on a smartphone. To identify different anchor nodes and enable time-of-arrival (TOA) ranging, we propose approaches for signal modulation, symbol detection and demodulation, synchronization and ranging. Experimental results show that the communication bit-error-rate and ranging accuracy is sufficient for our target applications. The preliminary results of localization demonstrate that our algorithm could achieve highaccuracy of 23cm in the offline mode with a promising potential for realtime smartphone-based indoor localization.

Using smartphones for accurate indoor localization opens a new frontier of mobile services, offering enormous opportunities to enhance users' experiences in indoor environments. Despite significant efforts on indoor localization in both academia and industry in the past two decades, highly accurate and practical smartphone-based indoor localization remains an open problem. To enable indoor location-based services (ILBS), there are several stringent requirements for an indoor localization system: highly accurate that can differentiate massive users' locations (foot-level); no additional hardware components or extensions on users' smartphones; scalable to massive concurrent users. Current GPS, Radio RSS (e.g. WiFi, Bluetooth, ZigBee), or Fingerprinting based solutions can only achieve meter-level or room-level accuracy. In this paper, we propose a practical and accurate solution that fills the long-lasting gap of smartphone-based indoor localization. Specifically, we design and implement an indoor localization ecosystem Guoguo. Guoguo consists of an anchor network with a coordination protocol to transmit modulated localization beacons using high-band acoustic signals, a realtime processing app in a smartphone, and a backend server for indoor contexts and location-based services. We further propose approaches to improve its coverage, accuracy, and location update rate with low-power consumption. Our prototype shows centimeter-level localization accuracy in an office and classroom environment. Such precise indoor localization is expected to have high impact in the future ILBS and our daily activities.

The RPL routing protocol published in RFC 6550 was designed for efficient and reliable data collection in low-power and lossy networks. Specifically, it constructs a Destination Oriented Directed Acyclic Graph (DODAG) for data forwarding. However, due to the uneven deployment of sensor nodes in large areas, and the heterogeneous traffic patterns in the network, some sensor nodes may have much heavier workload in terms of packets forwarded than others. Such unbalanced workload distribution will result in these sensor nodes quickly exhausting their energy, and therefore shorten the overall network lifetime. In this paper, we propose a load balanced routing protocol based on the RPL protocol, named LB-RPL, to achieve balanced workload distribution in the network. Targeted at the low-power and lossy network environments, LB-RPL detects workload imbalance in a distributed and non-intrusive fashion. In addition, it optimizes the data forwarding path by jointly considering both workload distribution and link-layer communication qualities. We demonstrate the performance superiority of our LB-RPL protocol over original RPL through extensive simulations.

In large-scale Wireless Sensor Networks (WSNs), leveraging data sinks' mobility for data gathering has drawn substantial interests in recent years. Current researches either focus on planning a mobile sink's moving trajectory in advance to achieve optimized network performance, or target at collecting a small portion of sensed data in the network. In many application scenarios, however, a mobile sink cannot move freely in the deployed area. Therefore, the precalculated trajectories may not be applicable. To avoid constant sink location update traffics when a sink's future locations cannot be scheduled in advance, we propose two energy-efficient proactive data reporting protocols, SinkTrail and SinkTrail-S, for mobile sink-based data collection. The proposed protocols feature low-complexity and reduced control overheads. Two unique aspects distinguish our approach from previous ones: 1) we allow sufficient flexibility in the movement of mobile sinks to dynamically adapt to various terrestrial changes; and 2) without requirements of GPS devices or predefined landmarks, SinkTrail establishes a logical coordinate system for routing and forwarding data packets, making it suitable for diverse application scenarios. We systematically analyze the impact of several design factors in the proposed algorithms. Both theoretical analysis and simulation results demonstrate that the proposed algorithms reduce control overheads and yield satisfactory performance in finding shorter routing paths.

The widely deployed electronic health (eHealth) systems changed people's daily life due to the extraordinary benefits, such as more efficiency, higher accuracy and broader availability. Patients in the eHealth network use their personal health records (PHRs) to communicate with their physicians and obtain medical services. As a matter of fact, patients who share the same diseases or symptoms want to communicate with each other not only for treatment, but also for psychological therapy. However, without sufficient knowledge of the authenticity of other patients' PHRs, patients are reluctant to share their medical information. On the other hand, patients would accept the patient-to-patient interaction only if their privacy issues of PHR are also well preserved. In this paper, we design a privacy-preserving user-centric private matching scheme from a social perspective in eHealth networks, where patients use verified PHR to find other patients who share the same situations and derive different user-centric results based on each one's own policy. In our scheme, the matching process guarantees both the verifiability and the privacy of patients' PHRs. Based on security and efficiency analysis, we show that our work satisfies both the privacy preservation and practicality requirements.

Absolute GPS-coordinates are typically inaccessible indoor. Pervasive smartphones offer new opportunities for relative indoor localization. The low-complexity and high-accuracy ranging under the communication-link is a crucial requirement for enabling location sensing in indoor environments. In this paper, we propose a Time-of-Arrival (TOA) estimation and communication scheme utilizing the ubiquitous speaker/microphone pair to achieve accurate ranging. To compensate for the performance loss caused by this simple device, an optimized TOA estimation method is proposed for enhanced ranging reliability and accuracy. To overcome the strong channel fading in acoustic communication, a dynamic demodulation method that jointly uses frequency and amplitude information has been proposed. Experimental results show that our proposed scheme can achieve near 8cm TOA ranging accuracy and 0.55% communication bit-error-rate (BER) with 70% probability.

Although online social networks reflect real world social relationships, in many cases, online data is too scarce or implicit to reveal a user's true willingness. This causes the Blind Spot problem in socially-rendered willingness inference systems. Blind spots are the undervalued online contacts in willingness inference because of insufficient explicit evidences. To the best of our knowledge, this is the first time to introduce and address the blind spot problem. In this paper, we propose a scheme to detect blind spots, by contradicting explicit evidences and implicit inferences. The proposed scheme uses interaction history as the explicit evidence, and social circles for implicit inference. Real world experiments and surveys demonstrate that our scheme can detect blind spots.

Privacy protection is of critical concern to Location-Based Service (LBS) users in mobile networks. Long-term pseudonyms, although appear to be anonymous, in fact empower third-party service providers to continuously track users' movements. Researchers have proposed the mix zone model to allow pseudonym changes in protected areas. In this paper, we investigate a new form of privacy attack to the LBS system that an adversary reveals a user's true identity and complete moving trajectory with the aid of side information. We propose a new metric to quantify the system's resilience to such attacks, and suggest using multiple mix zones to tackle this problem. A mathematical model is presented that treats the deployment of multiple mix zones as a cost constrained optimization problem. Furthermore, the influence of traffic density is also taken into account to enhance the protection effectiveness. The placement optimization problem is NP-hard. We therefore design two heuristic algorithms as practical and effective means to strategically select mix zone locations, and consequently reduce the privacy risks of mobile users trajectories. The effectiveness of our proposed solutions is demonstrated through extensive simulations on real-world mobile user data traces.

This paper studies the optimization problem of minimizing resource rental cost for running elastic applications in cloud while meeting application service requirements. Such a problem arises when excessive generated data incurs significant monetary cost on transfer and inventory in cloud. The goal of planning is to make resource rental decisions in response to varying application progress in the most cost-effective way. To address this problem, we first develop a Deterministic Resource Rental Planning (DRRP) model, using a mixed integer linear program, to generate optimal rental decisions given fixed cost parameters. Next, we systematically analyze the predictability of the time-varying spot instance prices in Amazon EC2 and find that the best achievable prediction is insufficient to provide a close approximation to the actual prices. This fact motivates us to propose a Stochastic Resource Rental Planning (SRRP) model that explicitly considers the price uncertainty in rental decision making. Using empirical spot price data sets and realistic cost parameters, we conduct simulations over a wide range of experimental scenarios. Results show that DRRP achieves as much as 50% cost reduction compared to the no-planning scheme. Moreover, SRRP consistently outperforms its DRRP counterpart in terms of cost saving, which demonstrates that SRRP is highly adaptive to the unpredictable nature of spot price in cloud resource market.

This paper addresses energy-efficient data gathering issues in wireless sensor networks (WSNs). Leveraging data correlation in densely-deployed sensor networks, we propose an Energy-aware Probability-based Clustering algorithm (EPC), featuring high scalability and flexibility particularly suitable for large-scale WSNs. Unlike most existing data gathering schemes that construct static routing structures or only consider spatial correlation among sensed data, EPC establishes energy-efficient routes on the fly during the data gathering process, and dynamically organizes sensor nodes into clusters based on a probability factor determined by both spatial and temporal data correlations. Redundant data transmissions are suppressed within a cluster and energy consumption is balanced to prolong network lifetime. To verify the effectiveness of EPC, extensive simulations are conducted on a network of 625 randomly deployed sensor nodes. Results show that EPC balances the energy consumption of the whole network and reduces up to 71% of the transmission costs with near negligible error rates for representative aggregation functions.

This paper investigates scheduling loosely coupled task-bundles in highly heterogeneous distributed systems. Two allocation quality metrics are used in pay-per-service distributed applications: efficiency in terms of social welfare, and fairness in terms of envy-freeness. The first contribution of this work is that we build a unified hypergraph scheduling model under which efficiency and fairness are compatible with each other. Second, in the scenario of budget-unawareness, we formulate a strategic algorithm design for distributed negotiations among autonomous self-interested computing peers and prove its convergence to complete local efficiency and envy-freeness. Third, we add budget limitation to the allocation problem and propose a class of hill-climbing heuristics in favor of different performance metrics. Finally we conduct extensive simulations to validate the performance of all the proposed algorithms. The results show that the decentralized hypergraph scheduling method is scalable, and yields desired allocation performance in various scenarios.

In Wireless Sensor Networks (WSN), data gathering using mobile sinks typically incurs constant propagation of sink location indication messages to guide the direction of data reporting. Such behavior is undesirable, especially when the sensor network scale increases, as frequent message flooding will cause serious congestion in network communication and significantly impair the sensor network lifetime. In this paper, we propose a proactive data reporting protocol, SinkTrail, which achieves energy efficient data forwarding to multiple mobile sinks, and effectively reduces the number of sink location broadcasting messages. SinkTrail is unique in two aspects: (1) it allows sufficient flexibility in the movement of mobile sinks to dynamically adapt to unknown terrestrial changes; and (2) without assistance of GPS or predefined landmarks, SinkTrail establishes a logical coordinate system for predicting and tracking mobile sinks' locations, thereby significantly saves energy consumed during the data reporting process. We systematically analyze the impact of several design factors in SinkTrail and explore potential design improvements. The simulation results demonstrate that SinkTrail outperforms the Frequent Flooding Method (FFM) in finding shorter routing path and consumes less energy during data gathering process.

In this paper, we propose an autonomic management framework (ASGrid) to address the requirements of emerging large-scale applications in hybrid grid and sensor network systems. To the best of our knowledge, we are the first who proposed the autonomic sensor grid system concept in a holistic manner targeted at non-trivial large applications. To bridge the gap between the physical world and the digital world and facilitate information analysis and decision making, ASGrid is designed to smooth the integration of sensor networks and grid systems and efficiently use both on demand. Under the blueprint of ASGrid, we present several building blocks that fulfill the following major features: (1) Self-configuration through content-based aggregation and associative rendezvous mechanisms; (2) Self-optimization through utility-based sensor selection and model-driven hierarchical sensing task scheduling; (3) Self-protection through ActiveKey dynamic key management and S3Trust trust management mechanisms. Experimental and simulation results on these aspects are presented.

This paper proposes a dynamic load balancing strategy called DLBEM based on maximum likelihood estimation methods for parallel and distributed applications. A mixture Gaussian model is employed to characterize workload in data- intensive applications. Using a small subset of workload information in systems, the DLBEM strategy reduces considerable communication overheads caused by workload information exchange and job migration. In the meantime, based on the Expectation-Maximization algorithm, DLBEM achieves near accurate estimation of the global system state with significantly less communication overheads and results in efficient workload balancing. Simulation results for some representative cases on a two-dimensional 16*16 grid demonstrate that DLBEM approach achieves even resource utilization and over 90% accuracy in the estimation of the global system state information with over 70% reduction on communication overheads compared to a baseline strategy.

This paper presents scheduling strategies for sensing workload in wireless sensor networks using Divisible Load Theory (DLT), which offers a tractable model and realistic approach to investigate optimal scheduling issues in distributed systems. Due to the limited energy resource it is desirable that a sensor network can complete tasks as fast as possible. Sensor nodes are coordinated to perform measuring, transmitting, and processing data. Two closely related network models are presented to illustrate how the workload is scheduled among sensor nodes so that the finish time is minimized. Closed-form solutions are derived to achieve the optimization if the source node satisfies certain utility rate, which is used to evaluate the informative ratio of sensory data. Furthermore, we present the energy model for sensor nodes in the multi-hop multi-source network topology. Finally, simulation results are presented to demonstrate the effects of different parameters such as the number of sensor nodes, measurement, communication, and processing speed on the finish time and energy consumption.