360° video streaming requires considerable bandwidth, and many techniques have been proposed to address this problem. One such technique is super-resolution, where the video is compressed at the server, and the client runs a deep learning model to enhance the video quality. However, most of today’s off-the-shelf mobile devices cannot support super-resolution for all tiles in real time. As a result, some tiles cannot be reconstructed to high resolution, significantly reducing users’ Quality of Experience (QoE). To address this problem, we utilize linear interpolation, which requires much less computational overhead. Through experiments, we observe that interpolation can achieve comparable quality, and even outperform super-resolution for some tiles with low spatial complexity. Building on this, we develop a 360° video streaming system that adaptively selects the most suitable downloading strategy, whether interpolation, super-resolution, or ABR at the appropriate bitrate, for each tile to maximize user QoE while considering network bandwidth limitations and the computational constraints of mobile devices. We formalize the 360° video streaming problem as an optimization problem and propose an efficient algorithm to solve it. Extensive evaluations using real user viewing data and 5G network traces demonstrate that our solution significantly outperforms existing techniques in terms of QoE under various scenarios.

Vehicles are equipped with various sensors such as LiDAR, which enable them to perceive the surrounding environment and enhance driver safety through advanced driver assistance systems. However, these sensors are limited by line-of-sight, preventing them from seeing beyond occlusions. One solution is to leverage the edge server which can collect and share perception data with other vehicles. Most existing research focuses on improve the performance of uploading perception data to the server, and the problem of perception dissemination remains largely unexplored, despite the challenges posed by the large volume of perception data and the limited wireless bandwidth. In this paper, we propose an edge-assisted relevance-aware perception dissemination system that collects perception data from multiple vehicles and selectively disseminates only the necessary data to appropriate vehicles. The necessity of dissem-ination is determined by evaluating the relevance of perception data, which quantifies the probability of potential collisions between corresponding objects. We then formulate and solve the relevance-aware perception dissemination problem whose goal is to maximize the relevance of disseminated data under bandwidth constraints. Extensive evaluation results demonstrate that our system can significantly enhance traffic safety while reducing the overall bandwidth consumption.

Camera sensors have been widely used to perceive the vehicle surrounding environments, understand the traffic condition, and then help avoid traffic accidents. Since most sensors are limited by line of sight, the perception data collected through individual vehicle can be uploaded and shared through the edge server. To reduce the bandwidth, storage and processing cost, we propose an edge-assisted camera selection system that only selects the necessary camera images to upload to the server. The selection is based on the camera metadata which describes the coverage of the cameras represented with GPS locations, orientations, and field of views. Different from existing work, our metadata based approach can detect and locate camera occlusions by leveraging LiDAR sensors, and then precisely and quickly calculate the real camera coverage and identify the coverage overlap. Based on the camera metadata, we study two camera selection problems, the Max-Coverage problem and the Min-Selection problem, and solve them with efficient algorithms. Moreover, we propose similarity based redundancy suppression techniques to further reduce the bandwidth consumption which becomes significant due to vehicle movements. Extensive evaluations demonstrate that the proposed algorithms can effectively select cameras to maximize coverage or minimize bandwidth consumption based on the application requirements.

Sleep apnea is a serious sleep disorder where patients have multiple extended pauses in breath during sleep. Although some portable or contactless sleep apnea detection systems have been proposed, none of them can achieve fine-grained sleep apnea detection without strict requirements on the device or environmental settings. To address this problem, we present DeepApnea, a deep learning based sleep apnea detection system that leverages patients' wrist movement data collected by smartwatches to identify different types of sleep apnea events (i.e., central apneas, obstructive apneas, and hypopneas). Through a clinical study, we identify some special characteristics associated with different types of sleep apnea captured by smartwatch. However, there are many technical challenges such as how to extract informative apnea features from the noisy data and how to leverage features extracted from the multi-axis sensing data. To address these challenges, we first propose signal pre-processing methods to filter the raw accelerometer (ACC) data, smoothing away noise while preserving the respiratory signal and potential features for identifying sleep apnea. Then, we design a deep learning architecture to extract features from three ACC axes collaboratively, where self attention and cross-axis correlation techniques are leveraged to improve the classification accuracy. We have implemented DeepApnea on smartwatches and performed a clinical study. Evaluation results demonstrate that DeepApnea can significantly outperform existing work on identifying different types of sleep apnea.

Tile-based streaming techniques have been widely used to save bandwidth in$360^{\circ }$video streaming. However, it is a challenge to determine the right tile size which directly affects the bandwidth usage. Moreover, downloading and processing many small tiles consume a large amount of energy on mobile devices. To solve this problem, we propose to encode the video by taking into account the viewing popularity, where the popularly viewed areas are encoded as macrotiles. We propose techniques for identifying and building macrotiles, and adjusting their sizes to take into account practical issues such as head movement randomness. In some cases, the user's viewing area may not be covered by the constructed macrotiles, and then the conventional tiling scheme is used. To support macrotile based$360^{\circ }$video streaming, the client selects the right tiles (a macrotile or a set of conventional tiles) with the right quality level to maximize the QoE under bandwidth constraint. We formulate this problem as an optimization problem which is NP-hard, and then propose a heuristic algorithm to solve it. Through extensive evaluations based on real head movement traces, we demonstrate that the proposed algorithm can significantly improve QoE, save bandwidth usage, and reduce energy consumption.

As Deep Neural Networks (DNNs) have been successfully applied to various fields, there is a tremendous demand for running DNNs on mobile devices. Although mobile GPU can be leveraged to improve performance, it consumes a large amount of energy. After a short period of time, the mobile device may become overheated and the processors are forced to reduce the clock speed, significantly reducing the processing speed. A different approach to support DNNs on mobile device is to leverage the Neural Processing Units (NPUs). Compared to GPU, NPU is much faster and more energy efficient, but with lower accuracy due to the use of low precision floating-point numbers. We propose to combine these two approaches to improve the performance of running DNNs on mobile devices by studying the thermal-aware scheduling problem, where the goal is to achieve a better tradeoff between processing time and accuracy while ensuring that the mobile device is not overheated. To solve the problem, we propose a heuristic-based scheduling algorithm to determine when to run DNNs on GPU and when to run DNNs on NPU based on the current states of the mobile device. The heuristic-based algorithm makes scheduling decisions greedily and ignores their future impacts. Thus, we propose a deep reinforcement learning based scheduling algorithm to further improve performance. Extensive evaluation results show that the proposed algorithms can significantly improve the performance of running DNNs on mobile devices while avoiding overheating.

Federated learning (FL) enables geographically dispersed edge devices (i.e., clients) to learn a global model without sharing the local datasets, where each client performs gradient descent with its local data and uploads the gradients to a central server to update the global model. However, FL faces massive communication overhead resulted from uploading the gradients in each training round. To address this problem, most existing research compresses the gradients with fixed and unified quantization for all the clients, which neither seeks adaptive quantization due to the varying gradient norms at different rounds, nor exploits the heterogeneity of the clients to accelerate FL. In this paper, we propose a novel adaptive and heterogeneous gradient quantization algorithm (AdaGQ) for FL to minimize the wall-clock training time from two aspects: i) adaptive quantization which exploits the change of gradient norm to adjust the quantization resolution in each training round; and ii) heterogeneous quantization which assigns lower quantization resolution to slow clients to align their training time with other clients to mitigate the communication bottleneck, and higher quantization resolution to fast clients to achieve a better communication efficiency and accuracy tradeoff. Evaluations based on various models and datasets validate the benefits of AdaGQ, reducing the total training time by up to 52.1% compared to baseline algorithms (e.g., FedAvg, QSGD).

Graphics processing units (GPUs) are the de facto standard for processing deep learning (DL) tasks. In large-scale GPU clusters, GPU failures are inevitable and may cause severe consequences. For example, GPU failures disrupt distributed training, crash inference services, and result in service level agreement violations. In this paper, we study the problem of predicting GPU failures using machine learning (ML) models to mitigate their damages.

As IoT devices are becoming widely deployed, there exist many threats to IoT-based systems due to their inherent vulnerabilities. One effective approach to improving IoT security is to deploy IoT honeypot systems, which can collect attack information and reveal the methods and strategies used by attackers. However, building high-interaction IoT honeypots is challenging due to the heterogeneity of IoT devices. Vulnerabilities in IoT devices typically depend on specific device types or firmware versions, which encourages attackers to perform pre-attack checks to gather device information before launching attacks. Moreover, conventional honeypots are easily detected because their replying logic differs from that of the IoT devices they try to mimic.To address these problems, we develop an adaptive high-interaction honeypot for IoT devices, called em HoneyIoT. We first build a real device based attack trace collection system to learn how attackers interact with IoT devices. We then model the attack behavior through markov decision process and leverage reinforcement learning techniques to learn the best responses to engage attackers based on the attack trace. We also use differential analysis techniques to mutate response values in some fields to generate high-fidelity responses.HoneyIoT has been deployed on the public Internet. Experimental results show that HoneyIoT can effectively bypass the pre-attack checks and mislead the attackers into uploading malware. Furthermore, HoneyIoT is covert against widely used reconnaissance and honeypot detection tools.

Many mobile applications have been developed to apply deep learning for video analytics. Although these advanced deep learning models can provide us with better results, they also suffer from the high computational overhead which means longer delay and more energy consumption when running on mobile devices. To address this issue, we propose a framework called FastVA, which supports deep learning video analytics through edge processing and Neural Processing Unit (NPU) in mobile. The major challenge is to determine when to offload the computation and when to use NPU. Based on the processing time and accuracy requirement of the mobile application, we study three problems: \textit{Max-Accuracy} where the goal is to maximize the accuracy under some time constraints, \textit{Max-Utility} where the goal is to maximize the utility which is a weighted function of processing time and accuracy, and \textit{Min-Energy} where the goal is to minimize the energy under some time and accuracy constraints. We formulate them as integer programming problems and propose heuristics based solutions. We have implemented FastVA on smartphones and demonstrated its effectiveness through extensive evaluations.

Numerous people are suffering from sleep-related problems. To diagnose them, a prerequisite is to divide the polysomnography (PSG) data into different sleep stages. Thus, sleep stage classification is an essential step, but collecting PSG data is expensive, time-consuming, and even belated. To address this issue, using accelerometers that are widely used in smartwatches is treated as an alternative way to monitor people’s sleep conditions. However, the flexibility of deep learning models by purely using wrist-worn accelerometer data for sleep stage classification has not been investigated by researchers. To explore the answer, in this paper, we design a novel axis-aware hybrid fusion-based deep learning model, named AccSleepNet, which takes the three axes’ accelerometer data as the input simultaneously. The designed axis-aware hybrid fusion mechanism prompts the model to learn the deep features from three axes collaboratively. Finally, a classification module takes the fused feature representations from three axes as input and outputs the predicted sleep stage. Experimental results on two public datasets demonstrate the effectiveness of the proposed AccSleepNet for the sleep stage classification task compared with state-of-the-art baselines. Moreover, an ablation study validates the necessity of leveraging three axes’ accelerometer data and the superiority of the designed axis-aware hybrid fusion mechanism1.

The ubiquity of mobile devices allows mobile users to participate in crowdsourcing anywhere, anytime. One potential application is to crowdsource photos/videos on demand to search for interested targets. Crowdsourced photos/videos have much better coverage compared to surveillance cameras, and thus help improve the effectiveness of target search. However, broadcasting the crowdsourcing task to all mobile users can significantly increase the cost in terms of resource and incentive budget. To reduce cost, the crowdsourcing server selects a subset of participating workers, and there are many challenges on worker selection. For example, due to occlusions in the photo/video scene, each worker only covers part of the area with certain probability. Due to the non-deterministic nature of this problem, we study two kinds of optimization problems: max-coverage which maximizes the probability of finding the target given a cost, and min-selection which minimizes the number of workers given the required probability of finding the target. Considering that workers may report exact locations or coarse-grained locations, we formalize four probability-based optimization problems for worker selection, and develop optimal or efficient approximation algorithms to solve them. The effectiveness of the proposed algorithms is evaluated and validated via extensive trace-driven simulations and a real-world demo.

Tile-based streaming has been widely used in 360° video streaming to adapt to varying network conditions. However, downloading and processing many small tiles consumes a large amount of energy on mobile devices. To address this issue, we propose techniques to encode video by considering the viewing popularity, where the tiles requested by users of similar interests are encoded as a large tile (called Ptile). When encoding Ptiles, we propose to further save energy by reducing the insignificant frames in each video segment, i.e., reducing the frame rate to save energy while satisfying some QoE constraint. Based on real video traces, we model the impact of video features (i.e., video bitrate, frame rate) and user behavior (i.e., view switching) on QoE, and model the impact of video features on power consumption. Based on the QoE model and the power model, we formulate the energy-efficient and QoE-aware 360° video streaming problem as an optimization problem, and propose a control theory based algorithm to solve it. Through extensive evaluations based on real traces, we demonstrate that the proposed algorithm can significantly reduce the energy consumption (49.7%) and improve the QoE (7.4%).

Deep Neural Network (DNN) is becoming adopted for video analytics on mobile devices. To reduce the delay of running DNNs, many mobile devices are equipped with Neural Processing Units (NPU). However, due to the resource limitations of NPU, these DNNs have to be compressed to increase the processing speed at the cost of accuracy. To address the low accuracy problem, we propose a Confidence Based Offloading (CBO) framework for deep learning video analytics. The major challenge is to determine when to return the NPU classification result based on the confidence level of running the DNN, and when to offload the video frames to the server for further processing to increase the accuracy. We first identify the problem of using existing confidence scores to make offloading decisions, and propose confidence score calibration techniques to improve the performance. Then, we formulate the CBO problem where the goal is to maximize accuracy under some time constraint, and propose an adaptive solution that determines which frames to offload at what resolution based on the confidence score and the network condition. Through real implementations and extensive evaluations, we demonstrate that the proposed solution can significantly outperform other approaches.

High quality video streaming for mobile devices implies high energy consumption due to the transmitted data and the variation of wireless signals. As an example, transmissions in mobile scenarios (e.g., inside a moving bus) consumes more energy for devices than when accessing from a static environment (e.g., at home). The QoE for the user does not substantially increase when watching high bitrate videos in a vibrating environment (i.e., a moving vehicle), as the context, in this case vehicle’s vibration, affects the perceived QoE. To address this problem, we propose to save energy by considering the context (environment) of video streaming. To model the impact of context, we exploit the embedded accelerometer in smartphones to record the vibration level during video streaming. Based on quality assessment experiments, we collect traces and model the impact of video bitrate and vibration level on QoE, and model the impact of video bitrate and signal strength on power consumption. Based on the QoE model and the power model, we formulate the context-aware and energy-aware video streaming problem as an optimization problem. We present an optimal algorithm which can maximize QoE and minimize energy. Since the optimal algorithm requires perfect knowledge of future tasks, we propose an online bitrate selection algorithm. To further improve the performance of the online algorithm, we propose a crowdsourcing based bitrate selection algorithm. Through real measurements and trace-driven simulations, we demonstrate that the proposed algorithms can significantly outperform existing approaches when considering both energy and QoE.

Location privacy has been one of the most important research areas over recent years, and many location Privacy Preserving Mechanisms (PPMs) have been proposed. Each PPM typically achieves certain tradeoffs between privacy protection and resource consumption, and no PPM performs perfectly in all cases. Instead of designing one PPM that works for all cases, this paper studies how to make the best use of multiple single PPMs for location privacy protection in different scenarios. In particular, we propose a general framework called SmartGuard, which dynamically selects the best privacy preservation strategy for a user based on her preferences and the current status of her mobile device. SmartGuard quantifies user privacy under various scenarios, models the effects of different PPMs on several key factors such as the remaining battery level and network bandwidth, and then recommends the best privacy strategy for the user. To illustrate how our SmartGuard works, we apply it to a specific scenario of LBSs and implement it on Android based phones. Evaluation results show that our solution outperforms existing PPMs under various scenarios.

Video analytics demand intensive computation resources, which means long processing delay when running on mobile devices. Although offloading computation to the cloud can partially solve the problem, transferring videos to the cloud introduces high transmission delay. With mobile edge computing, computation can be offloaded to the nearby edge servers to reduce the delay. However, the computation resources of the edge servers are usually limited and highly dynamic, and then server selection should be adaptive in order to improve the performance of video analytics. Also, frame resolution should be selected to achieve a better tradeoff between accuracy and frame processing rate. In this paper, we study the server resource-aware offloading problem for video analytics, where the goal is to maximize the utility which is a weighted function of accuracy and frame processing rate. The major challenge to solve this problem is the lack of server and network knowledge and the dynamic system environment. To overcome these challenges, we formulate the problem as a contextual Multi-armed Bandit problem, and propose a Bayesian Optimization based online learning algorithm to gradually learn the server status and the optimal solution, and make it adaptable for time-varying environments. Both theoretical analysis and evaluation results demonstrate the superior performance of our proposed algorithm.

Tile-based streaming techniques have been widely used to save bandwidth in 360° video streaming. However, it is a challenge to determine the right tile size which directly affects the bandwidth usage. To address this problem, we propose to encode the video by considering the viewing popularity, where the popularly viewed areas are encoded as macrotiles to save bandwidth. We propose techniques to identify and build macrotiles, and adjust their sizes considering practical issues such as head movement randomness. In some cases, a user's viewing area may not be covered by the constructed macrotiles, and then the conventional tiling scheme is used. To support popularity-aware 360° video streaming, the client selects the right tiles (a macrotile or a set of conventional tiles) with the right quality level to maximize the QoE under bandwidth constraint. We formulate this problem as an optimization problem which is NP-hard, and then propose a heuristic algorithm to solve it. Through extensive evaluations based on real traces, we demonstrate that the proposed algorithm can significantly improve the QoE and save the bandwidth usage.

Many Deep Neural Network (DNN) based applications have been developed and run on mobile devices. Although these advanced DNN models can provide better results, they also suffer from high computational overhead which means long delay and more energy consumption when running on mobile devices. To address these problems, many companies have developed dedicated Neural Processing Units (NPUs) for mobile devices, which can process AI features. Compared to CPU, NPU can run DNN models much faster, but with lower accuracy. To address this issue, we leverage model partition techniques to improve the performance of DNN models on mobile devices with NPU. The challenge is to determine which part of the DNN model should be run on CPU and which part to be run on NPU. Based on the delay and the accuracy requirements of the applications, we study two problems: Max-Accuracy where the goal is to maximize the accuracy under some time constraint, and Min-Time where the goal is to minimize the processing time while ensuring the accuracy is above a certain threshold. To solve these problems, we propose heuristic based algorithms which are simple but only search a small number of layer combinations (i.e., where to run which DNN model layers). To further improve the performance, we propose a Machine Learning based Model Partition (MLMP) algorithm. MLMP searches more layer combinations and considers both accuracy loss and processing time simultaneously. We also address many implementation issues to support model partition techniques on mobile devices with NPU. Experimental results show that MLMP outperforms the heuristic based algorithms and it can significantly improve the accuracy or reduce the processing time based on the application requirements.

The rapid progress of deep learning-based techniques such as Convolutional Neural Network (CNN) has enabled many emerging applications related to video analytics and running them on mobile devices can help improve our daily lives in many ways. However, there are many challenges for video analytics on mobile devices using multiple CNN models. CNN models are resource hungry, and each model requires a large amount of computational power and occupies a large portion of memory space. Although video processing can be offloaded to reduce the computation time, transmitting large amount of video data is time consuming. Thus, offloading is not always the best option. Moreover, different CNN models have different memory usage and processing time, making the scheduling problem more complex. As a result, besides deciding which task to be offloaded, we must decide which CNN model should reside in the memory and for how long, and which CNN model should be switched out due to memory constraint. In this paper, we propose resource aware scheduling algorithms to address these challenges. We identify the task scheduling problem for running multiple CNN models on mobile devices under resource constraints and formulate it as an integer programming problem. We propose resource-aware scheduling algorithms which combine offloading and local processing methods to minimize the completion time of video processing. We implement the proposed scheduling algorithms on Android-based smartphones and demonstrate its effectiveness through extensive experiments.

In mobile crowdsourcing, the accuracy of the collected data is usually hard to ensure. Researchers have proposed techniques to identify truth from noisy data by inferring and utilizing the reliability of mobile users, and allocate tasks to users with higher reliability. However, they neglect the fact that a user may only have expertise on some problems (in some domains), but not others, and hence causing two problems: low estimation accuracy in truth analysis and ineffective task allocation. To address these problems, we propose Expertise-aware Truth Analysis and Task Allocation (ETA2), which can effectively infer user expertise, and then estimate truth and allocate tasks based on the inferred expertise. ETA2relies on a novel semantic analysis method to identify the expertise, and an expertise-aware truth analysis method to find the truth. For expertise-aware task allocation in ETA2, we formalize and solve two problems based on the optimization objectives: max-qualitytask allocation which maximizes the probability fortasks to be allocated to users with high expertise and min-costtask allocation which minimizes the cost of task allocation while ensuring high-quality data are collected. Experimental results based on two real-world datasets and one synthetic dataset demonstrate that ETA2significantly outperforms existing solutions.

Distributed collaborative learning has enabled building machine learning models from distributed mobile users' data. It allows the server and users to collaboratively train a learning model where users only share model parameters with the server. To protect privacy, the server can use secure multiparty computation to learn the global model without revealing users' parameter updates in the clear. However this privacy preserving distributed learning opens the door to poisoning attacks, where malicious users poison their training data to maliciously influence the behavior of the global model. In this paper, we propose MLGuard, a privacy preserving distributed collaborative learning system with poisoning attack mitigation. MLGuard employs lightweight secret sharing scheme and a novel poisoning attack mitigation technique. We address several challenges such as preserving users' privacy, mitigating poisoning attacks, respecting resource constraints of mobile devices, and scaling to large number of users. Evaluation results demonstrate the effectiveness of MLGuard on building high accurate learning models with the existence of malicious users, while imposing minimal communication cost on mobile devices.

Many mobile applications have been developed to apply deep learning for video analytics. Although these advanced deep learning models can provide us with better results, they also suffer from the high computational overhead which means longer delay and more energy consumption when running on mobile devices. To address this issue, we propose a framework called FastVA, which supports deep learning video analytics through edge processing and Neural Processing Unit (NPU) in mobile. The major challenge is to determine when to offload the computation and when to use NPU. Based on the processing time and accuracy requirement of the mobile application, we study two problems: Max-Accuracy where the goal is to maximize the accuracy under some time constraints, and Max-Utility where the goal is to maximize the utility which is a weighted function of processing time and accuracy. We formulate them as integer programming problems and propose heuristics based solutions. We have implemented FastVA on smartphones and demonstrated its effectiveness through extensive evaluations.

With the proliferation of IoT cameras, it is possible to use crowdsourced videos to help find interested targets (e.g., crime suspect, lost child, lost vehicle) on demand. Due to the ubiquity of IoT cameras such as dash mounted and phone cameras, the crowdsourced videos have much better spatial coverage compared to only using surveillance cameras, and, thus, can significantly improve the effectiveness of target search. However, this may raise privacy concerns when workers (owners of IoT cameras) are provided with photos of the target. Also, the videos captured by the workers may be misused to track bystanders. To address this problem, we design and implement TargetFinder, a privacy preserving system for target search through IoT cameras. By exploiting homomorphic encryption techniques, the server can search for the target on encrypted information. We also propose techniques to allow the requester (e.g., the police) to receive images that include the target, while all other captured images of the bystanders are not revealed. Moreover, the target’s face image is not revealed to the server and the participating workers. Due to the high computation overhead of the cryptographic primitives, we develop optimization techniques in order to run our privacy preserving protocol on mobile devices. We also formulate and solve a worker selection problem to maximize the probability of finding the target under some budget constraint. A real-world demo and extensive evaluations demonstrate the effectiveness of TargetFinder.

In wireless ad hoc networks, due to the interference between concurrent transmissions, the per-node capacity generally decreases with the increasing number of nodes in the network. Caching can help improve the network capacity, as it shortens the content transmission distance and reduces the communication interference. However, current researches on the capacity of wireless ad hoc networks with caching generally assume that content popularity follows a uniform distribution. They ignore the fact that contents in reality have skewed popularity, which may lead to totally different capacity results. In this paper, we evaluate how the distribution of the content popularity affects the per-node capacity, and derive different capacity scaling laws based on the skewness of the content popularity. Our results suggest that for wireless networks with caching, when contents have skewed popularity, increasing the number of nodes monotonically increases the per-node capacity.

Although streaming video at a higher bitrate (resolution) can lead to better Quality of Experience (QoE), a larger amount of data will have to be downloaded and processed on smartphones and thus consuming more energy. On a moving bus where the wireless signal is weak, more energy will have to be spent on maintaining high bitrate video streaming than at a static environment such as at home or a cafe where the wireless signal is strong. On the other hand, the user perceived QoE does not increase too much by watching high bitrate videos in a vibrating environment (i.e., a moving vehicle), because the perception of video quality is affected by the environment such as the vibration or shaking on a moving bus. To address this problem, we propose to save energy by considering the context (environment) of video streaming. To model the impact of context, we exploit the embedded sensors (e.g., accelerometer) in smartphones to record the vibration level during video streaming. Based on quality assessment experiments, we collect traces and model the impacts of video bitrate and vibration level on QoE, and model the impacts of video bitrate and signal strength on power consumption. Based on the QoE model and the power model, we formulate the energy-aware and context-aware video streaming problem as an optimization problem. We present an optimal algorithm which can maximize QoE and minimize energy. Since the optimal algorithm requires perfect knowledge of future tasks, we further propose an online bitrate selection algorithm. Through real measurements and trace-driven simulations, we demonstrate that the proposed algorithm can significantly outperform existing approaches when considering both energy and QoE.

Mobile Social Network (MSN), built on inter-connected mobile devices, enables the flexibility of information exchanges of individuals within a virtual community. MSN may be self-organized and/or infrastructure-less, and the communication links may frequently fluctuate. When link qualities degrade, it remains critical to maintain the connections of important social pairs when supporting all social pairs is impossible. To achieve this goal, we propose to proactively place some reliable links (e.g., satellite links or UAV links) into the underlying communication network, so as to improve the service quality of the important social pairs, referred to as the Maintaining Social Connections (MSC) problem. We formulate the MSC problem and prove it is NP-hard. As such, we first study a special case of MSC, which is submodular and solvable with high approximation-ratio. Since the general MSC problem is not submodular, we propose an efficient approximation algorithm. Specially, by carefully choosing two submodular functions to lower/upper bound the MSC problem, we are able to prove the high approximation ratio of the proposed algorithm using these selected submodular functions. We further develop evolutionary algorithms to iteratively adjust the link placement via different exploration strategies, which also yield guaranteed approximation-ratio. Extensive evaluations based on both synthetic and real-world social network traces demonstrate the effectiveness of our proposed algorithms.

Photo sharing on Online Social Networks (OSNs) has become one of the most popular social activities in our daily life. However, some associated friends or bystanders in the photos may not want to be viewed due to privacy concerns. In this paper, we propose the design, implementation and evaluation of HideMe, a framework to preserve the associated users’ privacy for online photo sharing. HideMe acts as a plugin to existing photo sharing OSNs, and it enables the following: a) extraction of factors when users upload their photos, b) associated friends in the uploaded photos are able to set their own privacy policies based on scenarios, instead of a photo-by-photo setting, c) any user in other friend’s uploaded photos could be hidden away from unwanted viewers based on one time policy generation. We also design a distance-based algorithm to identify and protect the privacy of bystanders. Moreover, HideMe not only protects users’ privacy but also reduces the system overhead by a carefully designed face matching algorithm. We have implemented a prototype of HideMe, and evaluation results have demonstrated its effectiveness and efficiency.

The energy consumed by video streaming includes the energy consumed for data transmission and CPU processing, which are both affected by the CPU frequency. High CPU frequency can reduce the data transmission time but it consumes more CPU energy. Low CPU frequency reduces the CPU energy but increases the data transmission time and then increases the energy consumption. In this paper, we aim to reduce the total energy of mobile video streaming by adaptively adjusting the CPU frequency. Based on real measurement results, we model the effects of CPU frequency on TCP throughput and system power. Based on these models, we propose an Energy-aware CPU Frequency Scaling (EFS) algorithm which selects the CPU frequency that can achieve a balance between saving the data transmission energy and CPU energy. Since the downloading schedule of existing video streaming apps is not optimized in terms of energy, we also propose a method to determine when and how much data to download. Through trace-driven simulations and real measurement, we demonstrate that the EFS algorithm can reduce 30 percent of energy for the Youtube app, and the combination of our download method and EFS algorithm can save 50 percent of energy than the default Youtube app.

To address the increase of multimedia traffic dominated by streaming videos, user equipment (UE) can collaboratively cache and share contents to alleviate the burden of base stations. Prior work on device-to-device (D2D) caching policies assumes perfect knowledge of the content popularity distribution. Since the content popularity distribution is usually unavailable in advance, a machine learning-based caching strategy that exploits the knowledge of content demand history would be highly promising. Thus, we design D2D caching strategies using multi-agent reinforcement learning in this paper. Specifically, we model the D2D caching problem as a multi-agent multi-armed bandit problem and use Q-learning to learn how to coordinate the caching decisions. The UEs can be independent learners (ILs) if they learn the Q-values of their own actions, and joint action learners (JALs) if they learn the Q-values of their own actions in conjunction with those of the other UEs. As the action space is very vast leading to high computational complexity, a modified combinatorial upper confidence bound algorithm is proposed to reduce the action space for both IL and JAL. The simulation results show that the proposed JAL-based caching scheme outperforms the IL-based caching scheme and other popular caching schemes in terms of average downloading latency and cache hit rate.

Modern mobile devices are equipped with multicore-based processors, which introduce new challenges on computation offloading. With the big.LITTLE architecture, instead of only deciding locally or remotely running a task in the traditional architecture, we have to consider how to exploit the new architecture to minimize energy while satisfying application completion time constraints. In this paper, we address the problem of energy-efficient computation offloading on multicore-based mobile devices running multiple applications. We first formalize the problem as a mixed-integer nonlinear programming problem that is NP-hard, and then propose a novel heuristic algorithm to jointly solve the offloading decision and task scheduling problems. The basic idea is to prioritize tasks from different applications to make sure that both application time constraints and task-dependency requirements are satisfied. To find a better schedule while reducing the schedule searching overhead, we propose a critical path based solution which recursively checks the tasks and moves tasks to the right CPU cores to save energy. Simulation and experimental results show that our offloading algorithm can significantly reduce the energy consumption of mobile devices while satisfying the application completion time constraints.

Computation offloading has been widely used to alleviate the performance and energy limitations of smartphones by sending computationally intensive applications to the cloud. However, mobile devices with poor cellular service quality may incur high communication latency and high energy consumption for offloading, which will reduce the benefits of computation offloading. In this paper, we propose a peer-assisted computation offloading (PACO) framework to address this problem. In PACO, a client experiencing poor service quality can choose a neighbor with better service quality to be the offloading proxy. Through peer to peer interface such as WiFi direct, the client can offload computation tasks to the proxy which further transmits them to the cloud server through cellular networks. We propose algorithms to decide which tasks should be offloaded to minimize the energy consumption. We have implemented PACO on Android and have implemented three computationally intensive applications to evaluate its performance. Experimental results and simulation results show that PACO makes it possible for users with poor cellular service quality to benefit from computation offloading and PACO significantly reduces the delay and energy consumption compared to existing schemes.

Cellular network enables pervasive data access, but it also increases the power consumption of smartphones due to the long tail problem, where the cellular interface has to stay in the high-power state for some time after each data transmission. To reduce the tail energy, data that will be used in the future can be prefetched. However, prefetching unnecessary data may waste energy, and this problem becomes worse when the network quality is poor. In this paper, we generalize and formulate the prefetch-based energy optimization problem, where the goal is to find a prefetching schedule that minimizes the energy consumption of the data transmissions under the current network condition. To solve this nonlinear optimization problem, we first propose a greedy algorithm, and then propose a discrete algorithm with better performance. We have implemented and evaluated the proposed algorithms in two apps: in-app advertising and mobile video streaming. Evaluation results show that the proposed algorithms can significantly reduce the energy consumption.

As a widely observable social effect, influence diffusion refers to a process where innovations, trends, awareness, etc. spread across the network via the social impact among individuals. Motivated by such social effect, the concept of influence maximization is coined, where the goal is to select a bounded number of the most influential nodes (seed nodes) from a social network so that they can jointly trigger the maximal influence diffusion. A rich body of research in this area is performed under statistical diffusion models with provable submodularity, which essentially simplifies the problem as the optimal result can be approximated by the simple greedy search. When the diffusion models are non-submodular, however, the research community mostly focuses on how to bound/approximate them by tractable submodular functions. In other words, there is still a lack of efficient methods that can directly resolve non-submodular influence maximization problems. In this regard, we fill the gap by proposing seed selection strategies using network graphical properties in a generalized non-submodular threshold-based model, called influence barricade model. Under this model, we first establish theories to reveal graphical conditions that ensure the network generated by node removals has the same optimal seed set as that in the original network. We then exploit these theoretical conditions to develop efficient algorithms by strategically removing less-important nodes and selecting seeds only in the remaining network. To the best of our knowledge, this is the first graph-based approach that directly tackles non-submodular influence maximization. Evaluations on both synthetic and real-world Facebook/Twitter datasets confirm the superior efficiency of the proposed algorithms, which are orders of magnitude faster than benchmarks for large networks.

Smart meters can record fine-grained power consumption data and provide such data to the power supplier through realtime communications. Although smart meters can make power management more efficient and fault-tolerant, they also pose bigger threats to user privacy. Data from smart meters contain fine-grained power consumption information of home appliances and thus can be used to infer the ON/OFF states of home appliances. This problem has received some attention in the literature, however, most of them focus on active power based attacks. This paper focuses on reactive power and demonstrates how attackers can exploit reactive power data to infer appliance usage information. Experiments on real residential smart meter data show that our proposed attack can identify the ON/OFF events of home appliance with high accuracy. To protect users against such attacks, a novel defense technique called Reactive Power Obfuscation (RPO) is proposed. RPO can mask the true reactive power demand from the smart meter by using a capacitor to store and provide reactive power in a controlled manner. We evaluate the performance of RPO based on real household power consumption data. Evaluation results show that the ON/OFF events of home appliances can hardly be revealed from reactive power data when RPO is applied.

Wearable devices such as smartwatches do not have enough power and computation capability to process computationally intensive tasks. One viable solution is to offload these tasks to the connected smartphone. Existing Android smartphones allocate CPU resources to a task according to its performance requirement, which is determined by the context of the task. However, due to lack of context information, smartphones cannot properly allocate resources to tasks offloaded from wearable devices. Allocating too few resources to urgent tasks (related to user interaction) may cause high interaction latency on wearable devices, while allocating too many resources to unimportant tasks (unrelated to user interaction) may lead to energy waste on the smartphone. To solve this problem, we propose a context-aware task offloading (CATO) framework, in which offloaded tasks can be properly executed on the smartphone or further offloaded to the cloud based on their context, aiming to achieve a balance between good user experience on wearable devices and energy saving on the smartphone. To validate our design, we have implemented CATO on the Android platform and developed two applications on top of it. Experimental results show that CATO can significantly reduce latency for urgent tasks and save energy for other unimportant tasks.

The energy consumed by video streaming includes the energy consumed for data transmission and CPU processing, which are both affected by the CPU frequency. High CPU frequency can reduce the data transmission time but it consumes more CPU energy. Low CPU frequency reduces the CPU energy but increases the data transmission time and then increases the energy consumption. In this paper, we aim to reduce the total energy of mobile video streaming by adaptively adjusting the CPU frequency. Based on real measurement results, we model the effects of CPU frequency on TCP throughput and system power. Based on these models, we propose an Energy-aware CPU Frequency Scaling (EFS) algorithm which selects the CPU frequency that can achieve a balance between saving the data transmission energy and CPU energy. Since the downloading schedule of existing video streaming apps is not optimized in terms of energy, we also propose a method to determine when and how much data to download. Through trace-driven simulations and real measurement, we demonstrate that the EFS algorithm can reduce 30% of energy for the Youtube app, and the combination of our download method and EFS algorithm can save 50% of energy than the default Youtube app.

Mobile crowdsourcing has received considerable attention as it enables people to collect and share large volume of data through their mobile devices. Since the accuracy of the collected data is usually hard to ensure, researchers have proposed techniques to identify truth from noisy data by inferring and utilizing the reliability of users, and allocate tasks to users with higher reliability. However, they neglect the fact that a user may only have expertise on some problems (in some domains), but not others. Neglecting this expertise diversity may cause two problems: low estimation accuracy in truth analysis and ineffective task allocation. To address these problems, we propose an Expertise-aware Truth Analysis and Task Allocation (ETA2) approach, which can effectively infer user expertise and then allocate tasks and estimate truth based on the inferred expertise. ETA2relies on a novel semantic analysis method to identify the expertise domains of the tasks and user expertise, an expertise-aware truth analysis solution to estimate truth and learn user expertise, and an expertise-aware task allocation method to maximize the probability that tasks are allocated to users with the right expertise while ensuring the work load does not exceed the processing capability at each user. Experimental results based on two real-world datasets demonstrate that ETA2significantly outperforms existing solutions.

Smartwatches are quickly gaining popularity, but their limited battery life remains an important factor that adversely affects user satisfaction. To provide full functionality, smartwatches are usually connected to phones via Bluetooth. However, the Bluetooth power characteristics and the energy impact of Bluetooth data traffic have been rarely studied. To address this issue, we first establish the Bluetooth power model based on extensive measurements and a thorough examination of the Bluetooth implementation on Android smartwatches. Then we perform the first in-depth investigation of the background data transfers on smartwatches, and find that they are prevalent and consume a large amount of energy. For example, our experiments show that the smartwatch's battery life can be reduced to one third (or even worse) due to background data transfers. Such high energy cost is caused by many unnecessary data transfers and the energy inefficiency attributed to the adverse interaction between the data transfer pattern (i.e., frequently transferring small data) and the Bluetooth energy characteristics (i.e., the tail effect). Based on the identified causes, we propose four energy optimization techniques, which are fast dormancy, phone-initiated polling, two-stage sensor processing, and context-aware pushing. The first one aims to reduce tail energy for delay-tolerant data transfers. The latter three are designed for specific applications which are responsible for most background data transfers. Evaluation results show that jointly using these techniques can save 70.6% of the Bluetooth energy.

In wireless ad hoc networks, due to the interference between concurrent transmissions, the per node capacity generally decreases with the increasing number of nodes in the network. Caching can help improve the network capacity, as it shortens the content transmission distance and reduces the communication interference. However, current researches on the capacity of wireless ad hoc networks with caching generally assume that content popularity follows uniform distribution. They ignore the fact that contents in reality have skewed popularity, which may lead to totally different capacity results. In this paper, we evaluate how the distribution of the content popularity affects the network capacity, and derive different capacity scaling laws based on the skewness of the content popularity. Our results suggest that for wireless networks with caching, when contents have skewed popularity, increasing the number of nodes monotonically increases the per node capacity.

Photos crowdsourced from mobile devices can be used in many applications such as disaster recovery to obtain information about a target area. However, such applications often have resource constraints in terms of bandwidth, storage, and processing capability, which limit the number of photos that can be crowdsourced. Thus, it is a challenge to use the limited resources to crowdsource photos that best cover the target area. In this paper, we leverage various geographical and geometrical information about photos, called metadata, to address this challenge. Metadata includes the location, orientation, field of view, and range of a camera. Based on metadata, we define photo utility to measure how well a target area is covered by a set of photos. We propose various techniques to analyze such coverage and calculate photo utility accurately and efficiently. We also study the problem of selecting photos with the largest utility under a resource budget, and propose an efficient algorithm that achieves constant approximation ratio. With our design, the crowdsourcing server can select photos based on metadata instead of real images, and thus use the limited resources to crowdsource the most useful photos. Both simulation and experimental results demonstrate the effectiveness of our design.

The exponential growth of mobile videos has enabled a variety of video crowdsourcing applications. However, existing crowdsourcing approaches require all video files to be uploaded, wasting a large amount of bandwidth since not all crowdsourced videos are useful. Moreover, it is difficult for applications to find desired videos based on user-generated annotations, which can be inaccurate or miss important information. To address these issues, we present VideoMec, a video crowdsourcing system that automatically generates video descriptions based on various geographical and geometrical information, called metadata, from multiple embedded sensors in off-the-shelf mobile devices. With VideoMec, only a small amount of metadata needs to be uploaded to the server, hence reducing the bandwidth and energy consumption of mobile devices. Based on the uploaded metadata, VideoMec supports comprehensive queries for applications to find and fetch desired videos. For time-sensitive applications, it may not be possible to upload all desired videos in time due to limited wireless bandwidth and large video files. Thus, we formalize two optimization problems and propose efficient algorithms to select the most important videos to upload under bandwidth and time constraints. We have implemented a prototype of VideoMec, evaluated its performance, and demonstrated its effectiveness based on real experiments.

Detecting daily activities is helpful for health care and clinical medicine. In this paper, we present ActDetector, a smartwatch based application which detects 8 common daily activities, including sitting, walking, running, going upstairs, going downstairs, eating, driving and sitting in a vehicle. By leveraging the built-in sensors on smartwatch, a multi-level classification system is proposed which considers both detection accuracy and energy efficiency. ActDetector is designed to work unobtrusively, no matter on which wrist the smartwatch is worn. We have implemented ActDetector on Sony Smartwatch 3 and evaluated its performance in real experiments involving 12 users. Experimental results show that ActDetector is energy efficient and can detect the daily activities with high accuracy.

In-app advertising provides a monetization solution for free apps, but also consumes lots of energy due to the long tail problem in cellular networks. To reduce the tail energy, we can predict the number of ads needed in the future and then prefetch those ads together instead of periodically. However, prefetching unnecessary ads may waste both energy and cellular bandwidth, and this problem becomes worse when the network quality is poor. In this paper, we propose network quality aware prefetching algorithms. First, we design a prediction algorithm which generates a set of prefetching options with various probabilities. Second, with these prefetching options, we propose two prefetching algorithms to reduce the energy consumption by considering the effect of network quality, where the energy-aware prefetching algorithm aims to minimize the energy consumption, and the energy-and-data aware prefetching algorithm considers the data usage to achieve a tradeoff between energy and data usage. Evaluation results show that, compared to traditional ways of fetching ads periodically, our energy-aware prefetching algorithm can save 80% of energy under various network quality, and our energy-and-data aware prefetching algorithm can achieve similar energy saving with less data usage.

It is critical to maintain the communication links between important social pairs. However, maintaining the social links between faraway nodes in wireless networks is extremely difficult. Although multi-hop transmission can be used, if two nodes in the routing path are out of the wireless transmission range, a network partition is possible. To address this problem, we adopt a cooperative amplify-and-forward strategy, where nodes (relays) cooperate to improve the signal strength at the destination. We formulate and study two optimization problems for maintaining the required link throughput: Min-Energy and Min-Relay, where the goal of Min-Energy is to minimize the power consumption of the relays, and the goal of Min-Relay is to minimize the number of active relays. Since the Min-Energy problem is a non-convex problem, we solve it based on an approximation technique and prove that our solution is a feasible, in fact optimal solution. We formulate the Min-Relay problem as an integer programming problem, and propose a polynomial-time algorithm which can select the minimum number of relays to maintain the social link. Evaluation results show that Min-Relay can significantly reduce the number of active relays compared to Min-Energy, while achieving comparable power consumption.

In cellular networks, due to many practical deployment issues, some areas have good wireless coverage while other areas may not. This results in significant throughput (service quality) difference between wireless carriers at some locations. We first analyze the factors that affect the service quality and then validate the existence of service quality difference between different carriers via extensive measurements. To deal with this problem, a mobile device (node) with low service quality can offload its data traffic to nearby nodes with better service quality through Device-to-Device interfaces, such as WiFi direct, to save energy and reduce delay. To achieve this goal, we propose a Quality-Aware Traffic Offloading (QATO) framework to offload network tasks to neighboring nodes with better service quality. QATO can identify neighbors with better service quality and motivate nodes to help each other using incentive schemes. To validate our design, we have implemented QATO on Android platform and have developed a web browser and a photo uploader on top of it. Experimental results show that QATO can significantly reduce energy and delay for both data downloading and uploading. Through trace-driven simulations, we also show that all users can benefit from data offloading in the long run.

In this paper, we investigate how to network smartphones for providing communications in disaster recovery. By bridging the gaps among different kinds of wireless networks, we have designed and implemented a system called TeamPhone, which provides smartphones the capabilities of communications in disaster recovery. Specifically, TeamPhone consists of two components: A messaging system and a self-rescue system. The messaging system integrates cellular networking, ad-hoc networking, and opportunistic networking seamlessly, and enables communications among rescue workers. The self-rescue system groups, schedules, and positions the smartphones of trapped survivors. Such a group of smartphones can cooperatively wake up and send out emergency messages in an energy-efficient manner with their location and position information so as to assist rescue operations. We have implemented TeamPhone as a prototype application on the Android platform and deployed it on off-the-shelf smartphones. Experimental results demonstrate that TeamPhone can properly fulfill communication requirements and greatly facilitate rescue operations in disaster recovery.

Today, many smartphone users are unaware of what applications (apps) they should stop using to prevent their battery from running out quickly. The problem is identifying such apps is hard due to the fact that there exist hundreds of thousands of apps and their impact on the battery is not well understood. We show via extensive measurement studies that the impact of an app on battery consumption depends on both environmental (wireless) factors and usage patterns. Based on this, we argue that there exists a critical need for a tool that allows a user to: 1) identify apps that are energy hungry and 2) understand why an app is consuming energy, on her phone. Toward addressing this need, we present TIDE, a tool to detect high energy apps on any particular smartphone. TIDE's key characteristic is that it accounts for usage-centric information while identifying energy hungry apps from among a multitude of apps that run simultaneously on a user's phone. Our evaluation of TIDE on a test bed of Android-based smartphones, using week-long smartphone usage traces from 17 real users, shows that TIDE correctly identifies over 94% of energy-hungry apps and has a false positive rate of <; 6%.

Community detection has received considerable attention because of its applications to many practical problems in mobile networks. However, when considering temporal information associated with a community (i.e., transient community), most existing community detection methods fail due to their aggregation of contact information into a single weighted or unweighted network. In this paper, we propose a contact-burst-based clustering method to detect transient communities by exploiting pairwise contact processes. In this method, we formulate each pairwise contact process as a regular appearance of contact bursts, during which most contacts between the pair of nodes happen. Based on this formulation, we detect transient communities by clustering the pairs of nodes with similar contact bursts. Since it is difficult to collect global contact information at individual nodes, we further propose a distributed method to detect transient communities. In addition to transient community detection, we also propose a new data forwarding strategy for delay tolerant networks, in which transient communities serve as the data forwarding unit. Evaluation results show that our strategy can achieve a much higher data delivery ratio than traditional community-based strategies with comparable network overhead.

Photo crowdsourcing with smartphone has attracted considerable attention recently due to the prevalence of smartphones and the rich information provided by photos. In scenarios such as disaster recovery or battlefield, where the cellular network is partly damaged or severely overloaded, Disruption Tolerant Networks (DTNs) become the best way to deliver the crowdsourced photos. Since the bandwidth and storage resources in DTN are very limited and not enough to deliver all the crowdsourced photos, it is important to prioritize more valuable photos to use the limited resources. In this paper, we design a resource-aware photo crowdsourcing framework in DTN, which uses photo metadata including the smartphone's location, orientation, and other built-in camera's parameters, to estimate the value of photos. We propose a photo selection algorithm to maximize the value of photos delivered to the command center considering bandwidth and storage constraints. Both prototype implementation and trace-driven simulations demonstrate the effectiveness of our design.

Caching in wireless ad hoc networks can reduce network traffic and content access delay, as nodes can retrieve contents from near neighbors rather than the faraway server. However, the fundamental performance limits of caching in wireless ad hoc networks have rarely been studied in an analytical manner. In this paper, we study the fundamental property of wireless networks with caching, i.e., the scaling laws of the network capacity based on cache size of individual node, the total size of unique content and the number of nodes in the network. We present an upper bound on network capacity, and present an achievable capacity lower bound, where we propose a caching scheme to show what capacity can actually be achievable. Our results suggest that the capacity of wireless ad hoc networks with caching can remain constant even as the number of nodes in the network increases. We also present numerical results and demonstrate that our results are consistent with existing analytical results under extreme conditions where the node communication scenario matches theirs.

Although crowdsourcing can provide a large amount of information through mobile devices and mobile users, the information provided by them may be inaccurate. Various truth analysis techniques have been proposed to identify truth from the noisy data either in a heuristic manner or using statistical models. However, if the available data are limited or have large conflicts, it is difficult to identify the truth or ensure the data credibility (quality). In this paper, we address this problem by utilizing the communication networks to adaptively collect data from mobile users, especially when the existing data are not enough to ensure data credibility. Considering the requirement on data credibility and the constraint of network resources, we quantify the tradeoff between the enhanced data credibility and the increased network overhead, and propose resource-aware approaches for truth analysis. Specifically, we formalize two problems in resource-constrained mobile opportunistic networks: max-credibility which aims to maximize data credibility with some network overhead, and min-overhead which aims to achieve a specified data credibility while minimizing the network overhead. Simulation and experimental results demonstrate the effectiveness of the proposed solutions in terms of data credibility and network overhead.

In this paper, we investigate how to network smart-phones for providing communications in disaster recovery. By bridging the gaps among different kinds of wireless networks, we have designed and implemented a system called TeamPhone, which provides smartphones the capabilities of communications in disaster recovery. Specifically, TeamPhone consists of two components: a messaging system and a self-rescue system. The messaging system integrates cellular networking, ad-hoc networking and opportunistic networking seamlessly, and enables communications among rescue workers. The self-rescue system energy-efficiently groups the smartphones of trapped survivor and sends out emergency messages so as to assist rescue operations. We have implemented TeamPhone as a prototype application on the Android platform and deployed it on off-the-shelf smartphones. Experiment results show that TeamPhone can properly fulfill communication requirements and greatly facilitate rescue operations in disaster recovery.

We present a framework and a set of algorithms for determining faults in networks when large scale outages occur. The design principles of our algorithm, netCSI, are motivated by the fact that failures are geographically clustered in such cases. We address the challenge of determining faults with incomplete symptom information due to a limited number of reporting nodes. netCSI consists of two parts: a hypotheses generation algorithm, and a ranking algorithm. When constructing the hypothesis list of potential causes, we make novel use of positive and negative symptoms to improve the precision of the results. In addition, we propose pruning and thresholding along with a dynamic threshold value selector, to reduce the complexity of our algorithm. The ranking algorithm is based on conditional failure probability models that account for the geographic correlation of the network objects in clustered failures. We evaluate the performance of netCSI for networks with both random and realistic topologies. We compare the performance of netCSI with an existing fault diagnosis algorithm, MAX-COVERAGE, and demonstrate an average gain of 128 percent in accuracy for realistic topologies.

Mobile sensing relies on data contributed by users through their mobile device (e.g., smart phone) to obtain useful information about people and their surroundings. However, users may not want to contribute due to lack of incentives and concerns on possible privacy leakage. To effectively promote user participation, both incentive and privacy issues should be addressed. Although incentive and privacy have been addressed separately in mobile sensing, it is still an open problem to address them simultaneously. In this paper, we propose two credit-based privacy-aware incentive schemes for mobile sensing systems, where the focus is on privacy protection instead of on the design of incentive mechanisms. Our schemes enable mobile users to earn credits by contributing data without leaking which data they have contributed, and ensure that malicious users cannot abuse the system to earn unlimited credits. Specifically, the first scheme considers scenarios where an online trusted third party (TTP) is available, and relies on the TTP to protect user privacy and prevent abuse attacks. The second scheme considers scenarios where no online TTP is available. It applies blind signature, partially blind signature, and a novel extended Merkle tree technique to protect user privacy and prevent abuse attacks. Security analysis and cost evaluations show that our schemes are secure and efficient.

The emerging of mobile social networks opens opportunities for viral marketing. However, before fully utilizing mobile social networks as a platform for viral marketing, many challenges have to be addressed. In this paper, we address the problem of identifying a small number of individuals through whom the information can be diffused to the network as soon as possible, referred to as thediffusion minimizationproblem. Diffusion minimization under the probabilistic diffusion model can be formulated as an asymmetric$k$-center problem which is NP-hard, and the best known approximation algorithm for the asymmetric$k$-center problem has approximation ratio of$\log ^*n$and time complexity$O(n^5)$. Clearly, the performance and the time complexity of the approximation algorithm are not satisfiable in large-scale mobile social networks. To deal with this problem, we propose a community based algorithm and a distributed set-cover algorithm. The performance of the proposed algorithms is evaluated by extensive experiments on both synthetic networks and a real trace. The results show that the community based algorithm has the best performance in both synthetic networks and the real trace compared to existing algorithms, and the distributed set-cover algorithm outperforms the approximation algorithm in the real trace in terms of diffusion time.

Photos obtained via crowdsourcing can be used in many critical applications. Due to the limitations of communication bandwidth, storage, and processing capability, it is a challenge to transfer the huge amount of crowdsourced photos. To address this problem, we propose a framework, calledSmartPhoto, to quantify the quality (utility) of crowdsourced photos based on the accessible geographical and geometrical information (calledmetadata) including the smartphone's orientation, position, and all related parameters of the built-in camera. From the metadata, we can infer where and how the photo is taken, and then only transmit the most useful photos. Four optimization problems regarding the tradeoffs between photo utility and resource constraints, namely Max-Utility, online Max-Utility, Min-Selection, and Min-Selection with$k$-coverage, are studied. Efficient algorithms are proposed and their performance bounds are theoretically proved. We have implemented SmartPhoto in a testbed using Android based smartphones, and proposed techniques to improve the accuracy of the collected metadata by reducing sensor reading errors and solving object occlusion issues. Results based on real implementations and extensive simulations demonstrate the effectiveness of the proposed algorithms.

In cognitive radio networks, unlicensed users can use under-utilized licensed spectrum to achieve substantial performance improvement. To avoid interference with licensed users, unlicensed users must vacate the spectrum when it is accessed by licensed (primary) users. Since it takes some time for unlicensed users to switch to other available channels, the ongoing data transmissions may have to be interrupted and the transmission delay can be significantly increased. This makes it hard for cognitive radio networks to meet the delay constraints of many applications. In this paper, we develop caching techniques to address this problem. We formulate the cache placement problem in cognitive radio networks as an optimization problem, where the goal is to minimize the total cost, subject to some delay constraint, i.e., the data access delay can be statistically bounded. To solve this problem, we propose a cost-based approach to minimize the caching cost, and design a delay-based approach to satisfy the delay constraint. Then, we combine them and propose a distributed hybrid approach to minimize the caching cost subject to the delay constraint. Simulation results show that our approaches outperform existing caching solutions in terms of total cost and delay constraint, and the hybrid approach performs the best among the approaches satisfying the delay constraint.

The recent popularization of hand-held mobile devices, such as smartphones, enables the inter-connectivity among mobile users without the support of Internet infrastructure. When mobile users move and contact each other opportunistically, they form a delay tolerant network (DTN), which can be exploited to share data among them. Data replication is one of the common techniques for such data sharing. However, the unstable network topology and limited contact duration in DTNs make it difficult to directly apply traditional data replication schemes. In this paper, we recognize the deficiency of existing data replication schemes which treat the complete data item as the replication unit, and propose to replicate data at the packet level using erasure coding techniques. Our study consists of two cases based on the operating spectrum: unlicensed spectrum and licensed spectrum. For both cases, we analytically formulate the data replication problem as a mixed integer programming problem and propose a practical algorithm which operates in a fully distributed manner. Extensive simulations on both synthetic and realistic traces show that our scheme outperforms other existing replication schemes in terms of successful data retrieval probability in various scenarios.

This paper proposes SymDetector, a smartphone based application to unobtrusively detect the sound-related respiratory symptoms occurred in a user's daily life, including sneeze, cough, sniffle and throat clearing. SymDetector uses the built-in microphone on the smartphone to continuously monitor a user's acoustic data and uses multi-level processes to detect and classify the respiratory symptoms. Several practical issues are considered in developing SymDetector, such as users' privacy concerns about their acoustic data, resource constraints of the smartphone and different contexts of the smartphone. We have implemented SymDetector on Galaxy S3 and evaluated its performance in real experiments involving 16 users and 204 days. The experimental results show that SymDetector can detect these four types of respiratory symptoms with high accuracy under various conditions.

The ubiquity of mobile devices creates a rapidly growing market for mobile applications. Many of these applications involve complex processing tasks that are difficult to run on resource constrained mobile devices. This leads to the emergence of mobile cloud computing, in which cloud-based resources are used to enhance the computing capabilities of mobile devices. In this paper, we consider heterogeneous wireless networks in which multiple resource-rich computing nodes can be used as mobile clouds, and mobile devices can upload computation extensive tasks to these mobile clouds. The goal is to minimize the average task response time through determining whether to upload a task, and to which cloud the task should be uploaded. We formalize this task allocation problem, which is proved to be a NP-hard problem, and propose both offline centralized approach and online distributed approach to address this problem. Simulation results show that our approaches outperform others in terms of task response time in various scenarios.

Today, many smartphone users are unaware of what applications (apps) they should stop using to prevent their battery from running out quickly. The problem is identifying such apps is hard due to the fact that there exist hundreds of thousands of apps and their impact on the battery is not well understood. We show via extensive measurement studies that the impact of an app on battery consumption depends on both environmental (wireless) factors and usage patterns. Based on this, we argue that there exists a critical need for a tool that allows a user to (a) identify apps that are energy hungry, and (b) understand why an app is consuming energy, on her phone. Towards addressing this need, we present TIDE, a tool to detect high energy apps on any particular smartphone. TIDE's key characteristic is that it accounts for usage-centric information while identifying energy hungry apps from among a multitude of apps that run simultaneously on a user's phone. Our evaluation of TIDE on a testbed of Android-based smartphones, using weeklong smartphone usage traces from 17 real users, shows that TIDE correctly identifies over 94% of energy-hungry apps and has a false positive rate of <; 6%.

Computationally intensive applications may quickly drain mobile device batteries. One viable solution to address this problem utilizes computation offloading. The tradeoff is that computation offloading introduces additional communication, with a corresponding energy cost. Yet, previous research into computation offloading has failed to account for the special characteristics of cellular networks that impact mobile device energy consumption. In this paper, we aim to develop energy efficient computation offloading algorithms for cellular networks. We analyze the effects of the long tail problem on task offloading, formalize the computation offloading problem, and use Dijkstra's algorithm to find the optimal decision. Since this optimal solution relies on perfect knowledge of future tasks, we further propose an online algorithm for offloading. We have implemented this latter algorithm on Android-based smartphones. Both experimental results from this implementation and trace-driven simulation show that our algorithm can significantly reduce the energy of computation offloading in cellular networks.

Video streaming on smartphone consumes lots of energy. One common solution is to download and buffer future video data for playback so that the wireless interface can be turned off most of time and then save energy. However, this may waste energy and bandwidth if the user skips or quits before the end of the video. Using a small buffer can reduce the bandwidth wastage, but may consume more energy and introduce rebuffering delay. In this paper, we analyze the power consumption during video streaming considering user skip and early quit scenarios. We first propose an offline method to compute the minimum power consumption, and then introduce an online solution to save energy based on whether the user tends to watch video for a long time or tends to skip. We have implemented the online solution on Android based smartphones. Experimental results and trace-driven simulation results show that that our method can save energy while achieving a better tradeoff between delay and bandwidth compared to existing methods.

Privacy protection is critical for Location-Based Services (LBSs). In most previous solutions, users query service data from the untrusted LBS server when needed, and discard the data immediately after use. However, the data can be cached and reused to answer future queries. This prevents some queries from being sent to the LBS server and thus improves privacy. Although a few previous works recognize the usefulness of caching for better privacy, they use caching in a pretty straightforward way, and do not show the quantitative relation between caching and privacy. In this paper, we propose a caching-based solution to protect location privacy in LBSs, and rigorously explore how much caching can be used to improve privacy. Specifically, we propose an entropy-based privacy metric which for the first time incorporates the effect of caching on privacy. Then we design two novel caching-aware dummy selection algorithms which enhance location privacy through maximizing both the privacy of the current query and the dummies' contribution to cache. Evaluations show that our algorithms provide much better privacy than previous caching-oblivious and caching-aware solutions.

Human mobility prediction has received considerable attention because it helps addressing many practical problems in mobile networks. Most existing techniques focus on regular mobility prediction by studying the periodic mobility pattern of users. However, they fail to detect users' irregular mobility patterns, like attending a sporadic event. We address this problem by proposing techniques to predict event attendance based on the following basic idea: if a user is interested in events related to a topic, he may also attend future events related to this topic. In our solution, to learn how users are likely to attend the future events, three sets of features are identified by analyzing users' past activities, including semantic, temporal, and spatial features. Then, the supervised learning models are trained to predict event attendance based on the extracted features. To evaluate the performance of the proposed techniques, we collect a dataset based on Meet up that contains semantic descriptions of all events organized over a period of two years. Evaluation results show that the supervised classifiers built by all features outperform those built by individual features, and semantic features are more effective than temporal features and spatial features for predicting event attendance.

Vaccination is one of the most effective ways to protect people from being infected by infectious disease. However, it is often impractical to vaccinate all people in a community due to various resource constraints. Therefore, targeted vaccination, which vaccinates a small group of people, is an alternative approach to contain infectious disease spread. To achieve better performance in targeted vaccination, we collect student contact traces in a high school based on wireless sensors carried by students. With our wireless sensor system, we can record student contacts within the disease propagation distance, and then construct a disease propagation graph to model the infectious disease propagation. Based on this graph, we propose a metric called connectivity centrality to measure a node's importance during disease propagation and design centrality based algorithms for targeted vaccination. The proposed algorithms are evaluated and compared with other schemes based on our collected traces. Trace driven simulation results show that our algorithms can help to effectively contain infectious disease.

Opportunistic mobile networks consist of mobile devices which are intermittently connected via short-range radios. Forwarding in such networks relies on selecting relays to carry and deliver data to destinations upon opportunistic contacts. Due to the intermittent network connectivity, relays in current forwarding schemes are selected separately in a distributed manner. The contact capabilities of relays hence may overlap when they contact the same nodes and cause forwarding redundancy. This redundancy reduces the efficiency of resource utilization in the network, and may impair the forwarding performance if being unconsciously ignored. In this paper, based on investigation results on the characteristics of forwarding redundancy in realistic mobile networks, we propose methods to eliminate unnecessary forwarding redundancy and ensure efficient utilization of network resources. We first develop techniques to eliminate forwarding redundancy with global network information, and then improve these techniques to be operable in a fully distributed manner with limited network information. We furthermore propose adaptive forwarding strategy to intentionally control the amount of forwarding redundancy and satisfy the required forwarding performance with minimum cost. Extensive trace-driven evaluations show that our schemes effectively enhance forwarding performance with much lower cost.

Community detection is an important issue due to its wide use in designing network protocols such as data forwarding in Delay Tolerant Networks (DTN) and worm containment in Online Social Networks (OSN). However, most of the existing community detection algorithms focus on binary networks. Since most networks are naturally weighted such as DTN or OSN, in this article, we address the problems of community detection in weighted networks, exploit community for data forwarding in DTN and worm containment in OSN, and demonstrate how community can facilitate these network designs. Specifically, we propose a novel community detection algorithm, and introduce two metrics: intra-centrality and inter-centrality, to characterize nodes in communities, based on which we propose an efficient data forwarding algorithm for DTN and a worm containment strategy for OSN. Extensive trace-driven simulation results show that the proposed community detection algorithm, the data forwarding algorithm, and the worm containment strategy significantly outperform existing works.

We propose a greedy algorithm, Cluster-MAX-COVERAGE (CMC), to efficiently diagnose large-scale clustered failures. We primarily address the challenge of determining faults with incomplete symptoms. CMC makes novel use of both positive and negative symptoms to output a hypothesis list with a low number of false negatives and false positives quickly. CMC requires reports from about half as many nodes as other existing algorithms to determine failures with 100 percent accuracy. Moreover, CMC accomplishes this gain significantly faster (sometimes by two orders of magnitude) than an algorithm that matches its accuracy. When there are fewer positive and negative symptoms at a reporting node, CMC performs much better than existing algorithms. We also propose an adaptive algorithm called Adaptive-MAX-COVERAGE (AMC) that performs efficiently during both independent and clustered failures. During a series of failures that include both independent and clustered, AMC results in a reduced number of false negatives and false positives.

Smartphone based web browsing wastes a lot of power when downloading webpages due to the special characteristics of the wireless radio interface. In this paper, we identify these special characteristics, and address power consumption issues through two novel techniques. First, we reorganize the computation sequence of the web browser when loading a webpage, so that the web browser can first run the computations that will generate new data transmissions and retrieve these data from the web server. Then, the web browser can put the wireless radio interface into low power state, release the radio resource, and then run the remaining computations. Second, we introduce a practical data mining based method to predict the user reading time of webpages, based on which the smartphone can switch to low power state when the reading time is longer than a threshold. To demonstrate the effectiveness of our energy-aware approaches, we develop a testbed with Android phones on T-Mobile UMTS network. Experimental results show that our approach can reduce the power consumption of smartphone by more than 30 percent during web browsing. Moreover, our solution can further reduce the webpage loading time and increase the network capacity.

Mobile sensing relies on data contributed by users through their mobile device (e.g., smart phone) to obtain useful information about people and their surroundings. However, users may not want to contribute due to lack of incentives and concerns on possible privacy leakage. To effectively promote user participation, both incentive and privacy issues should be addressed. Existing work on privacy-aware incentive is limited to special scenario of mobile sensing where each sensing task needs only one data report from each user, and thus not appropriate for generic scenarios in which sensing tasks may require multiple reports from each user (e.g., in environmental monitoring applications). In this paper, we propose a privacy-aware incentive scheme for general mobile sensing, which allows each sensing task to collect one or multiple reports from each user as needed. Besides being more flexible in task management, our scheme has much lower computation and communication cost compared to the existing solution. Evaluations show that, when each node only contributes data for a small fraction of sensing tasks (e.g, due to the incapability or disqualification to generate sensing data for other tasks), our scheme runs at least one order of magnitude faster.

Mobile Social Network (MSN) with diverse connectivity characteristics is a combination of opportunistic network and mobile ad hoc network. Since the major difficulty of data forwarding is the opportunistic part, techniques designed for opportunistic networks are commonly used to forward data in MSNs. However, this may not be the best solution since they do not consider the ubiquitous existences of Transient Connected Components (TCCs), where nodes inside a TCC can reach each other by multi-hop wireless communications. In this paper, we first identify the existence of TCCs and analyze their properties based on five real traces. Then, we propose TCC-aware data forwarding strategies which exploit the special characteristics of TCCs to increase the contact opportunities and then improve the performance of data forwarding. Trace-driven simulations show that our TCC-aware data forwarding strategies outperform existing data forwarding strategies in terms of data delivery ratio and network overhead.

Opportunistic mobile networks consist of mobile devices which are intermittently connected via short-range radios. Forwarding in such networks relies on selecting relays to carry and deliver data to destinations upon opportunistic contacts. Due to the intermittent network connectivity, relays in current forwarding schemes are selected separately in a distributed manner. The contact capabilities of relays hence may overlap when they contact the same nodes and cause forwarding redundancy. This redundancy reduces the efficiency of resource utilization in the network, and may impair the forwarding performance if being ignored. In this paper, based on experimental investigations on the characteristics of forwarding redundancy in realistic mobile networks, we propose methods to eliminate unnecessary forwarding redundancy and ensure efficient utilization of network resources. We first develop techniques to eliminate forwarding redundancy with global network information, and then improve these techniques to be operable in a fully distributed manner with limited network information.

Cellular networks can provide pervasive data access for smartphones, but also consume lots of energy, because the cellular interface has to stay in high power state for a long time (called long tail problem) after a data transmission. In this paper, we propose to reduce the tail energy by aggregating the data traffic of multiple nodes using their P2P interfaces. This traffic aggregation problem is formalized as finding the best task schedule to minimize energy. We first propose an A* search algorithm, which can reduce the search space for finding the optimal schedule offline, and then introduce an online traffic aggregation algorithm. We have implemented the online traffic aggregation algorithm on Android smartphones, and have built a small testbed. Trace-driven simulations and Experimental results show that our traffic aggregation algorithm can significantly reduce the energy and delay.

The emerging of mobile social networks opens opportunities for viral marketing. However, before fully utilizing mobile social networks as a platform for viral marketing, many challenges have to be addressed. In this paper, we address the problem of identifying a small number of individuals through whom the information can be diffused to the network as soon as possible, referred to as the diffusion minimization problem. Diffusion minimization under the probabilistic diffusion model can be formulated as an asymmetric k-center problem which is NP-hard, and the best known approximation algorithm for the asymmetric k-center problem has approximation ratio of log*n and time complexity O(n5). Clearly, the performance and the time complexity of the approximation algorithm are not satisfiable in large-scale mobile social networks. To deal with this problem, we propose a community based algorithm and a distributed set-cover algorithm. The performance of the proposed algorithms is evaluated by extensive experiments on both synthetic networks and a real trace. The results show that the community based algorithm has the best performance in both synthetic networks and the real trace, and the distributed setcover algorithm outperforms the approximation algorithm in the real trace in terms of diffusion time.

Location-Based Service (LBS) has become a vital part of our daily life. While enjoying the convenience provided by LBS, users may lose privacy since the untrusted LBS server has all the information about users in LBS and it may track them in various ways or release their personal data to third parties. To address the privacy issue, we propose a Dummy-Location Selection (DLS) algorithm to achieve k-anonymity for users in LBS. Different from existing approaches, the DLS algorithm carefully selects dummy locations considering that side information may be exploited by adversaries. We first choose these dummy locations based on the entropy metric, and then propose an enhanced-DLS algorithm, to make sure that the selected dummy locations are spread as far as possible. Evaluation results show that the proposed DLS algorithm can significantly improve the privacy level in terms of entropy. The enhanced-DLS algorithm can enlarge the cloaking region while keeping similar privacy level as the DLS algorithm.

The opening of under-utilized spectrum creates an opportunity for unlicensed users to achieve substantial performance improvement through cognitive radio techniques. In cognitive radio ad-hoc networks, with node mobility and low node density, the network topology is highly dynamic and end-to-end connection is hard to maintain. We propose data replication techniques to address these problems and improve data access performance in such intermittently connected cognitive radio network. Although data replication has been extensively studied in traditional disruption tolerant networks, existing techniques cannot be directly applied here since they do not consider the effects of primary user appearance on data replication. In this paper, we formulate spectrum-aware data replication as an optimization problem which tries to maximize the average data retrieval probability, subject to storage and time constraints. Since the problem is hard to solve based on mixed integer programming, we further design a distributed replication scheme based on the metric of replication benefit. Extensive simulations based on synthetic and realistic traces show that our scheme outperforms existing schemes in terms of data retrieval probability in various scenarios.

In cognitive radio networks, unlicensed users can use under-utilized licensed spectrum to achieve substantial performance improvement. To avoid interference with licensed users, unlicensed users must vacate the spectrum when it is accessed by licensed (primary) users. Since it takes some time for unlicensed users to switch to other available channels, the ongoing data transmissions may have to be interrupted and the transmission delay can be significantly increased. This makes it hard for cognitive radio networks to meet the delay constraints of many applications. To the best of our knowledge, we are the first to use caching techniques to address this problem. We formulate the cache placement problem in cognitive radio networks as an optimization problem, where the goal is to minimize the total cost, subject to some delay constraint, i.e., the data access delay can be statistically bounded. To solve this problem, we propose three approaches: cost-based, delay-based, and hybrid. Simulation results show that our approaches outperform existing caching solutions in terms of total cost and delay constraint, and the hybrid approach performs the best among the approaches satisfying the delay constraint.

In mobile opportunistic networks, most existing research focuses on how to choose appropriate relays to carry and forward data. Although relay selection is an important issue, other issues such as finding content from people with the right expertise are also very important since the ultimate goal of using mobile opportunistic network is to provide the right content to mobile users (nodes). In this paper, we study expertise-based data access in content-centric mobile opportunistic networks, where the objective is to minimize the average query delay given a sequence of queries considering node expertise, node queuing delay and communication delay. To solve this problem, we propose various query forwarding approaches under deterministic and probabilistic expertise models. Specifically, we propose centralized approaches to assign queries based on a modified Dijkstra's shortest path algorithm and distributed approaches in which query forwarding is based on a utility metric. Extensive simulations on both synthetic and realistic traces demonstrate that our solutions outperform existing approaches.

Photos obtained via crowdsourcing can be used in many critical applications. Due to the limitations of communication bandwidth, storage and processing capability, it is a challenge to transfer the huge amount of crowdsourced photos. To address this problem, we propose a framework, called SmartPhoto, to quantify the quality (utility) of crowdsourced photos based on the accessible geographical and geometrical information (called metadata) including the smartphone's orientation, position and all related parameters of the built-in camera. From the metadata, we can infer where and how the photo is taken, and then only transmit the most useful photos. Three optimization problems regarding the tradeoffs between photo utility and resource constraints, namely the Max-Utility problem, the online Max-Utility problem and the Min-Selection problem, are studied. Efficient algorithms are proposed and their performance bounds are theoretically proved. We have implemented SmartPhoto in a testbed using Android based smartphones, and proposed techniques to improve the accuracy of the collected metadata by reducing sensor reading errors and solving object occlusion issues. Results based on real implementations and extensive simulations demonstrate the effectiveness of the proposed algorithms.

In cellular networks, due to practical deployment issues, some areas have good wireless coverage while others may not. This results in significant throughput (service quality) difference between wireless carriers at some locations. Through extensive measurements, we have validated the existence of such service quality difference. Then, through peer to peer interfaces such as WiFi direct, a mobile device (node) with low service quality can offload its data traffic to nodes with better service quality, to save energy and reduce delay. To achieve this goal, we propose a Quality-Aware Traffic Offloading (QATO) framework to offload network tasks to neighboring nodes with better service quality. QATO can identify neighbors with better service quality and provide incentive mechanisms to motivate nodes to help each other. To validate our design, we have implemented QATO on Android platform and have developed a web browser and a photo uploader on top of it. Experimental results show that QATO can significantly reduce energy and delay for both data downloading and uploading. Through trace-driven simulations, we also show that all users can benefit from data offloading in the long run.

Mobile social networks have emerged as a new frontier in the mobile computing research society, and the commonly used social structure (i.e., community) has been exploited to facilitate the design of network protocols and applications, such as data forwarding and worm containment. However, community based approaches may not be accurate when applied for predicting node contacts and may separate two frequently contacted nodes into different communities. In this paper, to address these problems, we propose skeleton, a tree structure specially designed for organizing network nodes, as the underlying structure in mobile social networks. We address the challenges on how to uncover skeleton from network, how to adapt skeleton with dynamic network and how to leverage skeleton for network protocol designs. Skeleton is constructed based on best friendship and skeleton construction is simple and efficient (e.g., less computational complexity than community detection). Algorithms are also designed to adapt skeleton construction to dynamic network. Moreover, a data forwarding algorithm and a worm containment strategy are designed based on skeleton. Trace-driven simulation results show that the skeleton based data forwarding algorithm and worm containment strategy outperform existing schemes based on community.

The proliferation and ever-increasing capabilities of mobile devices such as smart phones give rise to a variety of mobile sensing applications. This paper studies how an untrusted aggregator in mobile sensing can periodically obtain desired statistics over the data contributed by multiple mobile users, without compromising the privacy of each user. Although there are some existing works in this area, they either require bidirectional communications between the aggregator and mobile users in every aggregation period, or have high-computation overhead and cannot support large plaintext spaces. Also, they do not consider the Min aggregate, which is quite useful in mobile sensing. To address these problems, we propose an efficient protocol to obtain the Sum aggregate, which employs an additive homomorphic encryption and a novel key management technique to support large plaintext space. We also extend the sum aggregation protocol to obtain the Min aggregate of time-series data. To deal with dynamic joins and leaves of mobile users, we propose a scheme that utilizes the redundancy in security to reduce the communication cost for each join and leave. Evaluations show that our protocols are orders of magnitude faster than existing solutions, and it has much lower communication overhead.

Disruption tolerant networks (DTNs) are characterized by low node density, unpredictable node mobility, and lack of global network information. Most of current research efforts in DTNs focus on data forwarding, but only limited work has been done on providing efficient data access to mobile users. In this paper, we propose a novel approach to support cooperative caching in DTNs, which enables the sharing and coordination of cached data among multiple nodes and reduces data access delay. Our basic idea is to intentionally cache data at a set of network central locations (NCLs), which can be easily accessed by other nodes in the network. We propose an efficient scheme that ensures appropriate NCL selection based on a probabilistic selection metric and coordinates multiple caching nodes to optimize the tradeoff between data accessibility and caching overhead. Extensive trace-driven simulations show that our approach significantly improves data access performance compared to existing schemes.

The opening of under-utilized spectrum creates the opportunity of substantial performance improvement through cognitive radio techniques. However, the real network performance may be limited since unlicensed users must vacate and switch to other available spectrum if the current spectrum is reclaimed by the licensed (primary) users. During spectrum switching, network partitions may occur since multiple links may be affected if they use the channel reclaimed by the primary users. In this paper, we address this problem through robust topology control, where channels are assigned to minimize channel interference while maintaining network connectivity when primary users appear. The problem is proved to be NP-hard and a sufficient condition for a robust channel assignment is derived. To solve this problem, we first propose centralized algorithms which can reduce the channel interference while satisfying the robustness constraints. Moreover, we derive its performance bound on channel interference and its computational overhead through theoretical analysis. Then, we propose distributed algorithms based on channel hopping techniques, and prove their correctness. Simulation results show that our solutions outperform existing interference-aware approaches substantially when primary users appear and achieve similar performance at other times.

Cellular networks (e.g., 3G) are currently facing severe traffic overload problems caused by excessive traffic demands. Offloading part of the cellular traffic through other forms of networks, such as Delay Tolerant Networks (DTNs) and WiFi hotspots, is a promising solution. However, since these networks can only provide intermittent connectivity to mobile users, utilizing them for cellular traffic offloading may result in a nonnegligible delay. As the delay increases, the users' satisfaction decreases. In this paper, we investigate the tradeoff between the amount of traffic being offloaded and the users' satisfaction. We provide a novel incentive framework to motivate users to leverage their delay tolerance for cellular traffic offloading. To minimize the incentive cost given an offloading target, users with high delay tolerance and large offloading potential should be prioritized for traffic offloading. To effectively capture the dynamic characteristics of users' delay tolerance, our incentive framework is based on reverse auction to let users proactively express their delay tolerance by submitting bids. We further illustrate how to predict the offloading potential of the users by using stochastic analysis for both DTN and WiFi cases. Extensive trace-driven simulations verify the efficiency of our incentive framework for cellular traffic offloading.

Backup paths are widely used in IP networks to protect IP links from failures. However, existing solutions such as the commonly used independent model and Shared Risk Link Group (SRLG) model do not accurately reflect the correlation between IP link failures, and thus may not choose reliable backup paths. We propose a cross-layer approach for minimizing routing disruption caused by IP link failures. We develop a probabilistically correlated failure (PCF) model to quantify the impact of IP link failure on the reliability of backup paths. With the PCF model, we propose an algorithm to choose multiple reliable backup paths to protect each IP link. When an IP link fails, its traffic is split onto multiple backup paths to ensure that the rerouted traffic load on each IP link does not exceed the usable bandwidth. We evaluate our approach using real ISP networks with both optical and IP layer topologies. Experimental results show that two backup paths are adequate for protecting a logical link. Compared with existing works, the backup paths selected by our approach are at least 18 percent more reliable and the routing disruption is reduced by at least 22 percent. Unlike prior works, the proposed approach prevents the rerouted traffic from interfering with normal traffic.

Many practical problems in mobile social networks such as routing, community detection, and social behavior analysis, rely on accurate user contact detection. The frequently used method for detecting user contact is through Bluetooth on smartphones. However, Bluetooth scans consume lots of power. Although increasing the scan duty cycle can reduce the power consumption, it also reduces the accuracy of contact detection. In this paper, we address this problem based on the observation that user contact changes (i.e., starts and ends of user contacts) are mainly caused by user movement. Since most smartphones have accelerometers, we can use them to detect user movement with much less energy and then start Bluetooth scans to detect user contacts. By conducting experiments on smartphones, we discover three relationships between user movement and user contact changes. According to these relationships, we propose a Mobility-Assisted User Contact detection algorithm (MAUC), which triggers Bluetooth scans only when user movements have a high possibility to cause contact changes. Moreover, we propose energy-aware MAUC (E-MAUC) to further reduce energy consumption during Bluetooth discovery, while keeping the same detection accuracy as MAUC. Via trace driven simulations, we show that MAUC can reduce the number of Bluetooth scans by half while maintaining similar contact detection rates compared to existing algorithms, and E-MAUC can further reduce the energy consumption by 45% compared to MAUC.

Smartphone based web browsing wastes a lot of power when downloading webpages due to the special characteristics of the 3G radio interface. In this paper, we identify these special characteristics, and address power consumption issues through two novel techniques. First, we reorganize the computation sequence of the web browser when loading a webpage, so that the web browser can first run the computations that will generate new data transmissions and retrieve these data from the web server. Then, the web browser can put the 3G radio interface into low power state, release the radio resource, and then run the remaining computations. Second, we introduce a practical data mining based method to predict the user reading time of webpages, based on which the smartphone can switch to low power state when the reading time is longer than a threshold. To demonstrate the effectiveness of our energy-aware approaches, we develop a testbed with Android phones on T-Mobile UMTS network. Experimental results show that our approach can reduce the power consumption of smartphone by more than 30% during web browsing, and reduce the webpage loading time by 17%.

Community has received considerable attention because of its application to many practical problems in mobile networks. However, when considering temporal information associated with community (i.e., transient community), most existing community detection methods fail due to their aggregation of the contact information into a single weighted or unweighted network. In this paper, we propose a contact-burst-based clustering method to detect transient communities by exploiting the pairwise contact processes. In this method, we formulate each pairwise contact process as regular appearance of contact bursts, during which most contacts between the pair of nodes happen. Based on such formulation, we detect transient communities by clustering the pairs of nodes with similar contact bursts together. We also propose a new data forwarding strategy for delay tolerant networks in which transient communities serve as the data forwarding unit. Evaluation results show that our strategy can achieve much higher data delivery ratio than traditional community-based strategies with comparable network overhead.

Mobile sensing exploits data contributed by mobile users (e.g., via their smart phones) to make sophisticated inferences about people and their surrounding and thus can be applied to environmental monitoring, traffic monitoring and healthcare. However, the large-scale deployment of mobile sensing applications is hindered by the lack of incentives for users to participate and the concerns on possible privacy leakage. Although incentive and privacy have been addressed separately in mobile sensing, it is still an open problem to address them simultaneously. In this paper, we propose two privacy-aware incentive schemes for mobile sensing to promote user participation. These schemes allow each mobile user to earn credits by contributing data without leaking which data it has contributed, and at the same time ensure that dishonest users cannot abuse the system to earn unlimited amount of credits. The first scheme considers scenarios where a trusted third party (TTP) is available. It relies on the TTP to protect user privacy, and thus has very low computation and storage cost at each mobile user. The second scheme removes the assumption of TTP and applies blind signature and commitment techniques to protect user privacy.

Community detection is an important issue due to its wide use in designing network protocols such as data forwarding in Delay Tolerant Networks (DTN) and worm containment in Online Social Networks (OSN). However, most of the existing community detection algorithms focus on binary networks. Since most networks are weighted such as social networks, DTN or OSN, in this paper, we address the problems of community detection in weighted networks and exploit community for data forwarding in DTN and worm containment in OSN. We propose a novel community detection algorithm, and then introduce two metrics called intra-centrality and inter-centrality, to characterize nodes in communities. Based on these metrics, we propose an efficient data forwarding algorithm for DTN and an efficient worm containment strategy for OSN. Extensive trace-driven simulation results show that the data forwarding algorithm and the worm containment strategy significantly outperform existing works.

Continuously monitoring link performance is important to network diagnosis. In this paper, we address the problem of minimizing the probing cost and achieving identifiability in probe-based network link monitoring. Given a set of links to monitor, our objective is to select the minimum number of probing paths that can uniquely determine all identifiable links and cover all unidentifiable links. We propose an algorithm based on a linear system model to find out all irreducible sets of probing paths that can uniquely determine an identifiable link, and we extend the bipartite model to reflect the relationship between a set of probing paths and an identifiable link. Since our optimization problem is NP-hard, we propose a heuristic-based algorithm to greedily select probing paths. Our method eliminates two types of redundant probing paths, i.e., those that can be replaced by others and those without any contribution to achieving identifiability. Simulations based on real network topologies show that our approach can achieve identifiability with very low probing cost. Compared with prior work, our method is more general and has better performance.

Disruption Tolerant Networks (DTNs) utilize the mobility of nodes and the opportunistic contacts among nodes for data communications. Due to the limitation in network resources such as contact opportunity and buffer space, DTNs are vulnerable to flood attacks in which attackers send as many packets or packet replicas as possible to the network, in order to deplete or overuse the limited network resources. In this paper, we employ rate limiting to defend against flood attacks in DTNs, such that each node has a limit over the number of packets that it can generate in each time interval and a limit over the number of replicas that it can generate for each packet. We propose a distributed scheme to detect if a node has violated its rate limits. To address the challenge that it is difficult to count all the packets or replicas sent by a node due to lack of communication infrastructure, our detection adopts claim-carry-and-check: each node itself counts the number of packets or replicas that it has sent and claims the count to other nodes; the receiving nodes carry the claims when they move, and cross-check if their carried claims are inconsistent when they contact. The claim structure uses the pigeonhole principle to guarantee that an attacker will make inconsistent claims which may lead to detection. We provide rigorous analysis on the probability of detection, and evaluate the effectiveness and efficiency of our scheme with extensive trace-driven simulations.

Unpredictable node mobility, low node density, and lack of global information make it challenging to achieve effective data forwarding in Delay-Tolerant Networks (DTNs). Most of the current data forwarding schemes choose the nodes with the best cumulative capability of contacting others as relays to carry and forward data, but these nodes may not be the best relay choices within a short time period due to the heterogeneity of transient node contact characteristics. In this paper, we propose a novel approach to improve the performance of data forwarding with a short time constraint in DTNs by exploiting the transient social contact patterns. These patterns represent the transient characteristics of contact distribution, network connectivity and social community structure in DTNs, and we provide analytical formulations on these patterns based on experimental studies of realistic DTN traces. We then propose appropriate forwarding metrics based on these patterns to improve the effectiveness of data forwarding. When applied to various data forwarding strategies, our proposed forwarding metrics achieve much better performance compared to existing schemes with similar forwarding cost.

Today's location-sensitive service relies on user's mobile device to determine the current location. This allows malicious users to access a restricted resource or provide bogus alibis by cheating on their locations. To address this issue, we propose A Privacy-Preserving LocAtion proof Updating System (APPLAUS) in which colocated Bluetooth enabled mobile devices mutually generate location proofs and send updates to a location proof server. Periodically changed pseudonyms are used by the mobile devices to protect source location privacy from each other, and from the untrusted location proof server. We also develop user-centric location privacy model in which individual users evaluate their location privacy levels and decide whether and when to accept the location proof requests. In order to defend against colluding attacks, we also present betweenness ranking-based and correlation clustering-based approaches for outlier detection. APPLAUS can be implemented with existing network infrastructure, and can be easily deployed in Bluetooth enabled mobile devices with little computation or power cost. Extensive experimental results show that APPLAUS can effectively provide location proofs, significantly preserve the source location privacy, and effectively detect colluding attacks.

Camera sensors are different from traditional scalar sensors, as cameras at different positions can form very different views of the object. However, traditional coverage model does not consider this intrinsic property of camera sensors. To address this issue, a novel model called full-view coverage is proposed. It uses the angle between the object's facing direction and the camera's viewing direction to measure the quality of coverage. An object is full-view covered if there is always a camera to cover it no matter which direction it faces and the camera's viewing direction is sufficiently close to the object's facing direction. An efficient method is proposed for full-view coverage detection in any given camera sensor networks, and a sufficient condition on the sensor density needed for full-view coverage in a random uniform deployment is derived. In addition, the article shows a necessary and sufficient condition on the sensor density for full-view coverage in a triangular lattice-based deployment. Based on the full-view coverage model, the article further studies the barrier coverage problem. Existing weak and strong barrier coverage models are extended by considering direction issues in camera sensor networks. With these new models, weak/strong barrier coverage verification problems are introduced, and new detection methods are proposed and evaluated.

For sensor networks deployed to monitor and report real events, event source anonymity is an attractive and critical security property, which unfortunately is also very difficult and expensive to achieve. This is not only because adversaries may attack against sensor source privacy through traffic analysis, but also because sensor networks are very limited in resources. As such, a practical trade-off between security and performance is desirable. In this article, for the first time we propose the notion of statistically strong source anonymity , under a challenging attack model where a global attacker is able to monitor the traffic in the entire network. We propose a scheme called FitProbRate , which realizes statistically strong source anonymity for sensor networks. We demonstrate the robustness of our scheme under various statistical tests that might be employed by the attacker to detect real events. Our analysis and simulation results show that our scheme, besides providing source anonymity, can significantly reduce real event reporting latency compared to two baseline schemes. However, the degree of source anonymity in the FitProbRate scheme might decrease as real message rate increases. We propose a dynamic mean scheme which has better performance under high real message rates. Simulation results show that the dynamic mean scheme is capable of increasing the attacker's false positive rate and decreasing the attacker's Bayesian detection rate significantly even under high-rate continuous real messages.

In this paper, we propose an algorithm to efficiently diagnose large-scale clustered failures. The algorithm, Cluster-MAX-COVERAGE (CMC), is based on greedy approach. We address the challenge of determining faults with incomplete symptoms. CMC makes novel use of both positive and negative symptoms to output a hypothesis list with a low number of false negatives and false positives quickly. CMC requires reports from about half as many nodes as other existing algorithms to determine failures with 100% accuracy. Moreover, CMC accomplishes this gain significantly faster (sometimes by two orders of magnitude) than an algorithm that matches its accuracy. Furthermore, we propose an adaptive algorithm called Adaptive-MAX-COVERAGE (AMC) that performs efficiently during both kinds of failures, i.e., independent and clustered. During a series of failues that include both independent and clustered, AMC results in a reduced number of false negatives and false positives.

Backup paths are widely used to protect IP links from failures. Existing solutions such as the commonly used independent and Shared Risk Link Group models do not accurately reflect the correlation between IP link failures, and thus may not choose reliable backup paths. We propose a cross-layer approach for IP link protection. We develop a correlated failure probability (CFP) model to quantify the impact of an IP link failure on the reliability of backup paths. With the CFP model, we propose two algorithms for selecting backup paths. The first algorithm focuses on choosing the backup paths with minimum failure probability. The second algorithm further considers the bandwidth constraint and aims at minimizing the traffic disruption caused by failures. It also ensures that the rerouted traffic load on each IP link does not exceed the usable bandwidth to avoid interfering with the normal traffic. Simulations based on real ISP networks show that our approach can choose backup paths that are more reliable and achieve better protection.

Opportunistic mobile networks consist of personal mobile devices which are intermittently connected with each other. Data access can be provided to these devices via cooperative caching without support from the cellular network infrastructure, but only limited research has been done on maintaining the freshness of cached data which may be refreshed periodically and is subject to expiration. In this paper, we propose a scheme to efficiently maintain cache freshness. Our basic idea is to let each caching node be only responsible for refreshing a specific set of caching nodes, so as to maintain cache freshness in a distributed and hierarchical manner. Probabilistic replication methods are also proposed to analytically ensure that the freshness requirements of cached data are satisfied. Extensive trace driven simulations show that our scheme significantly improves cache freshness, and hence ensures the validity of data access provided to mobile users.

Quickly recovering IP networks from failures is critical to enhancing Internet robustness and availability. Due to their serious impact on network routing, large-scale failures have received increasing attention in recent years. We propose an approach called Reactive Two-phase Rerouting (RTR) for intra-domain routing to quickly recover from large-scale failures with the shortest recovery paths. To recover a failed routing path, RTR first forwards packets around the failure area to collect information on failures. Then, in the second phase, RTR calculates a new shortest path and forwards packets along it through source routing. RTR can deal with large-scale failures associated with areas of any shape and location, and is free of permanent loops. For any failure area, the recovery paths provided by RTR are guaranteed to be the shortest. Extensive simulations based on ISP topologies show that RTR can find the shortest recovery paths for more than 98.6% of failed routing paths with reachable destinations. Compared with prior works, RTR achieves better performance for recoverable failed routing paths and uses much less network resources for irrecoverable failed routing paths.

The proliferation and ever-increasing capabilities of mobile devices such as smart phones give rise to a variety of mobile sensing applications. This paper studies how an untrusted aggregator in mobile sensing can periodically obtain desired statistics over the data contributed by multiple mobile users, without compromising the privacy of each user. Although there are some existing works in this area, they either require bidirectional communications between the aggregator and mobile users in every aggregation period, or has high computation overhead and cannot support large plaintext spaces. Also, they do not consider the Min aggregate which is quite useful in mobile sensing. To address these problems, we propose an efficient protocol to obtain the Sum aggregate, which employs an additive homomorphic encryption and a novel key management technique to support large plaintext space. We also extend the sum aggregation protocol to obtain the Min aggregate of time-series data. Evaluations show that our protocols are orders of magnitude faster than existing solutions.

In many surveillance scenarios, there are some known critical locations where the events of concern are expected to occur. A common goal in such applications is to use sensors to monitor these critical locations with sufficient quality of surveillance within a designated period. However, with limited sensing resources, the coverage and lifetime requirement may not be satisfied at the same time. Thus, sometimes the sensor needs to reduce its duty cycle in order to satisfy the stringent lifetime constraint. In this paper, we model the critical location coverage problem using a point coverage model with the objective of scheduling sensors to maximize the event detection probability while meeting the network lifetime requirement. We show that this problem is NP-hard and propose a distributed algorithm with a provable approximation ratio of 0.5. Extensive simulations show that the proposed distributed algorithm outperforms the extensions of several state-of-the-art schemes with a significant margin while preserving the network lifetime requirement.

The opening of under-utilized spectrum creates the opportunity of substantial performance improvement through cognitive radio techniques. However, the real network performance may be limited since unlicensed users must vacate and switch to other available spectrum if the current spectrum is reclaimed by the licensed (primary) users. During the spectrum switching time, network partitions may occur since multiple links may be affected if they all operate on the channel reclaimed by the primary users. In this paper, we address this problem through robust topology control, where channels are assigned to minimize channel interference while maintaining network connectivity when primary users appear. To solve this NP-hard problem, we propose both centralized and distributed algorithms. Simulation results show that our solutions outperform existing interference-aware approaches substantially when primary users appear and achieve similar performance at other times.

We consider the problem of diffusing cached content in an intermittently connected mobile network, starting from a given initial configuration to a desirable goal state where all nodes interested in particular contents have a copy of their desired contents. The goal is to minimize the time taken for the diffusion process to terminate at a goal state. Due to bandwidth and storage constraints, whenever two nodes encounter each other, they must decide which content if any to transfer to each other. While most prior work on this topic has focused on practically realizable heuristics for this problem, we take a more formal approach. Our main contribution is to show that, assuming global state information is available, this problem can be formulated as a stochastic shortest path problem, which is a kind of Markov decision process (MDP). Using this formulation, we numerically explore some small-scale examples for which we are able to obtain the optimal solution. The results show that the optimal diffusion strategy is very much a function of the underlying encounter graph.

In disruption tolerant networks (DTNs), selfish or malicious nodes may drop received packets. Such routing misbehavior reduces the packet delivery ratio and wastes system resources such as power and bandwidth. Although techniques have been proposed to mitigate routing misbehavior in mobile ad hoc networks, they cannot be directly applied to DTNs because of the intermittent connectivity between nodes. To address the problem, we propose a distributed scheme to detect packet dropping in DTNs. In our scheme, a node is required to keep a few signed contact records of its previous contacts, based on which the next contacted node can detect if the node has dropped any packet. Since misbehaving nodes may misreport their contact records to avoid being detected, a small part of each contact record is disseminated to a certain number of witness nodes, which can collect appropriate contact records and detect the misbehaving nodes. We also propose a scheme to mitigate routing misbehavior by limiting the number of packets forwarded to the misbehaving nodes. Trace-driven simulations show that our solutions are efficient and can effectively mitigate routing misbehavior.

Node mobility and end-to-end disconnections in disruption-tolerant networks (DTNs) greatly impair the effectiveness of data forwarding. Although social-based approaches can address the problem, most existing solutions only focus on forwarding data to a single destination. In this paper, we study multicast with single and multiple data items in DTNs from a social network perspective, develop analytical models for multicast relay selection, and furthermore investigate the essential difference between multicast and unicast in DTNs. The proposed approach selects relays according to their capabilities, measured by social-based metrics, for forwarding data to the destinations. The design of social-based metrics exploits social network concepts such as node centrality and social community, and the selected relays ensure achieving the required data delivery ratio within the given time constraint. Extensive trace-driven simulations show that the proposed approach has similar data delivery ratio and delay to that of Epidemic routing, but significantly reduces data forwarding cost, measured by the number of relays used.

In mobile ad hoc networks (MANETs), nodes move freely and link/node failures are common, which leads to frequent network partitions. When a network partition occurs, mobile nodes in one partition are not able to access data hosted by nodes in other partitions, and hence significantly degrade the performance of data access. To deal with this problem, we apply data replication techniques. Existing data replication solutions in both wired or wireless networks aim at either reducing the query delay or improving the data availability, but not both. As both metrics are important for mobile nodes, we propose schemes to balance the trade-offs between data availability and query delay under different system settings and requirements. Extensive simulation results show that the proposed schemes can achieve a balance between these two metrics and provide satisfying system performance.

Although 3G networks have been largely deployed to cope with the increasing demand of wireless data services, little is known on how these networks are used from the network perspective. In this paper, we present analysis of data services based on a nation-wide 3G network trace collected from one of the largest cellular network service providers in North America. Our work differentiates from previous studies by examining data service usage and mobility patterns from various dimensions including application breakdown, user roles, device types and diurnal characteristics. We also look into various access issues such as termination failures and frequent registrations to better understand how the network performs. Our results are important for cellular network operators and protocol designers to improve data service performance and user satisfaction.

Disruption Tolerant Networks (DTNs) are characterized by the low node density, unpredictable node mobility and lack of global network information. Most of current research efforts in DTNs focus on data forwarding, but only limited work has been done on providing effective data access to mobile users. In this paper, we propose a novel approach to support cooperative caching in DTNs, which enables the sharing and coordination of cached data among multiple nodes and reduces data access delay. Our basic idea is to intentionally cache data at a set of Network Central Locations (NCLs), which can be easily accessed by other nodes in the network. We propose an effective scheme which ensures appropriate NCL selection based on a probabilistic selection metric, and coordinate multiple caching nodes to optimize trade off between data accessibility and caching overhead. Extensive trace-driven simulations show that our scheme significantly improves data access performance compared to existing schemes.

Smart phone is becoming a key element in providing greater user access to the mobile Internet. Many complex applications, which are used to be only on PCs, have been developed and run on smart phones. These applications extend the functionalities of smart phones and make them more convenient for users to be connected. However, they also greatly increase the power consumption of smart phones and many users are frustrated with the long delay of web browsing when using smart phones. In this paper, we have discovered that the key reason of the long delay and high power consumption in web browsing is not due to the bandwidth limitation most of time in 3G networks. The local computation limitation at the smart phone is the real bottleneck for opening most web pages. To address this issue, we propose an architecture, called Virtual-Machine based Proxy (VMP), to shift the computing from smart phones to the VMP. To illustrate the feasibility of deploying the proposed VMP system in 3G networks, we have built a prototype using Xen virtual machines and Android Phones with T-Mobile UMTS network. Experimental results show that compared to normal smart phone browser, our VMP approach reduces the delay by more than 80% and reduces the power consumption during web browsing by more than 45%.

3G networks are currently facing severe traffic overload problems caused by excessive demands of mobile users. Offloading part of the 3G traffic through other forms of networks, such as Delay Tolerant Networks (DTNs), WiFi hotspots, and Femtocells, is a promising solution. However, since these networks can only provide intermittent and opportunistic connectivity to mobile users, utilizing them for 3G traffic offloading may result in a non-negligible delay. As the delay increases, the users' satisfaction decreases. In this paper, we investigate the tradeoff between the amount of traffic being offloaded and the users' satisfaction. We provide a novel incentive framework to motivate users to leverage their delay tolerance for 3G traffic offloading. To minimize the incentive cost given an offloading target, users with high delay tolerance and large offloading potential should be prioritized for traffic offloading. To effectively capture the dynamic characteristics of users' delay tolerance, our incentive framework is based on reverse auction to let users proactively express their delay tolerance by submitting bids. We further take DTN as a case study to illustrate how to predict the offloading potential of the users by using stochastic analysis. Extensive trace-driven simulations verify the efficiency of our incentive framework for 3G traffic offloading.

The recent popularization of hand-held mobile devices, such as smartphones, enables the inter-connectivity among mobile users without the support of Internet infrastructure. When mobile users move and contact each other opportunistically, they form a Delay Tolerant Network (DTN), which can be exploited to share data among them. Data replication is one of the common techniques for such data sharing. However, the unstable network topology and limited contact duration in DTNs make it difficult to directly apply traditional data replication schemes. Although there are a few existing studies on data replication in DTNs, they generally ignore the contact duration limits. In this paper, we recognize the deficiency of existing data replication schemes which treat the complete data item as the replication unit, and propose to replicate data at the packet level. We analytically formulate the contact duration aware data replication problem and give a centralized solution to better utilize the limited storage buffers and the contact opportunities. We further propose a practical contact Duration Aware Replication Algorithm (DARA) which operates in a fully distributed manner and reduces the computational complexity. Extensive simulations on both synthetic and realistic traces show that our distributed scheme achieves close-to-optimal performance, and outperforms other existing replication schemes.

Data dissemination is useful for many applications of Disruption Tolerant Networks (DTNs). Current data dissemination schemes are generally network-centric ignoring user interests. In this paper, we propose a novel approach for user-centric data dissemination in DTNs, which considers satisfying user interests and maximizes the cost-effectiveness of data dissemination. Our approach is based on a social centrality metric, which considers the social contact patterns and interests of mobile users simultaneously, and thus ensures effective relay selection. The performance of our approach is evaluated from both theoretical and experimental perspectives. By formal analysis, we show the lower bound on the cost-effectiveness of data dissemination, and analytically investigate the tradeoff between the effectiveness of relay selection and the overhead of maintaining network information. By trace-driven simulations, we show that our approach achieves better cost-effectiveness than existing data dissemination schemes.

Camera sensors are different from traditional scalar sensors as different cameras from different positions can form distinct views of the object. However, traditional disk sensing model does not consider this intrinsic property of camera sensors. To this end, we propose a novel model called full-view coverage. An object is considered to be full-view covered if for any direction from 0 to 2π (object's facing direction), there is always a sensor such that the object is within the sensor's range and more importantly the sensor's viewing direction is sufficiently close to the object's facing direction. With this model, we propose an efficient method for full-view coverage detection in any given camera sensor networks. We also derive a sufficient condition on the sensor density needed for full-view coverage in a random uniform deployment. Finally, we show a necessary and sufficient condition on the sensor density for full-view coverage in a triangular lattice based deployment.

In directional sensor networks, sensors can steer around to serve multiple target points. Most previous works assume there are always enough deployed sensors so that all target points can be served simultaneously. However, this assumption may not hold when the mission requirement changes or when more target points need to be served. Since it is not always practical to deploy new sensors, we propose to reconfigure the network by letting existing sensors steer and serve the targets periodically. As a result, targets may not be served continuously, and the service delay affects the quality of service. One important problem is how to choose the optimal set of targets to serve by each sensor such that the maximum service delay is minimized. We first show that this problem is NP-complete, and then we propose a centralized protocol whose performance is bounded by a logarithm factor of the optimal solution. We also propose a distributed protocol which achieves the same performance as the centralized protocol. Finally, we extend the optimization model and the protocols by considering the rotation delay, which is critical for some applications but ignored by previous work.

Today's location-sensitive service relies on user's mobile device to determine its location and send the location to the application. This approach allows the user to cheat by having his device transmit a fake location, which might enable the user to access a restricted resource erroneously or provide bogus alibis. To address this issue, we propose A Privacy-Preserving LocAtion proof Updating System (APPLAUS) in which co-located Bluetooth enabled mobile devices mutually generate location proofs, and update to a location proof server. Periodically changed pseudonyms are used by the mobile devices to protect source location privacy from each other, and from the untrusted location proof server. We also develop user-centric location privacy model in which individual users evaluate their location privacy levels in real-time and decide whether and when to accept a location proof exchange request based on their location privacy levels. APPLAUS can be implemented with the existing network infrastructure and the current mobile devices, and can be easily deployed in Bluetooth enabled mobile devices with little computation or power cost. Extensive experimental results show that our scheme, besides providing location proofs effectively, can significantly preserve the source location privacy.

Data access is an important issue in Delay Tolerant Networks (DTNs), and a common technique to improve the performance of data access is cooperative caching. However, due to the unpredictable node mobility in DTNs, traditional caching schemes cannot be directly applied. In this paper, we propose DAC, a novel caching protocol adaptive to the challenging environment of DTNs. Specifically, we exploit the social community structure to combat the unstable network topology in DTNs. We propose a new centrality metric to evaluate the caching capability of each node within a community, and solutions based on this metric are proposed to determine where to cache. More importantly, we consider the impact of the contact duration limitation on cooperative caching, which has been ignored by the existing works. We prove that the marginal caching benefit that a node can provide diminishes when more data is cached. We derive an adaptive caching bound for each mobile node according to its specific contact patterns with others, to limit the amount of data it caches. In this way, both the storage space and the contact opportunities are better utilized. To mitigate the coupon collector's problem, network coding techniques are used to further improve the caching efficiency. Extensive trace-driven simulations show that our cooperative caching protocol can significantly improve the performance of data access in DTNs.

This paper aims at achieving optimal rate allocation for data aggregation in wireless sensor networks. We first formulate this rate allocation problem as a network utility maximization problem. Due to its non-convexity, we take a couple of variable substitutions on the original problem and transform it into an approximate problem, which is convex. We then apply duality theory to decompose this approximate problem into a rate control subproblem and a scheduling subproblem. Based on this decomposition, a distributed algorithm for joint rate control and scheduling is designed, and proved to approach arbitrarily close to the optimum of the approximate problem. Finally, we show that our approximate solution can achieve near-optimal performance through both theoretical analysis and simulations.

Barrier coverage has attracted much attention in the past few years. However, most of the previous works focused on traditional scalar sensors. We propose to study barrier coverage in camera sensor networks. One fundamental difference between camera and scalar sensor is that cameras from different positions can form quite different views of the object. As a result, simply combining the sensing range of the cameras across the field does not necessarily form an effective camera barrier since the face image (or the interested aspect) of the object may be missed. To address this problem, we use the angle between the object's facing direction and the camera's viewing direction to measure the quality of sensing. An object is full-view covered if there is always a camera to cover it no matter which direction it faces and the camera's viewing direction is sufficiently close to the object's facing direction. We study the problem of constructing a camera barrier, which is essentially a connected zone across the monitored field such that every point within this zone is full-view covered. We propose a novel method to select camera sensors from an arbitrary deployment to form a camera barrier, and present redundancy reduction techniques to effectively reduce the number of cameras used. We also present techniques to deploy cameras for barrier coverage in a deterministic environment, and analyze and optimize the number of cameras required for this specific deployment under various parameters.

In this paper we present a framework and a set of algorithms for determining faults in networks when large scale outages occur. The design principles of our algorithm, netCSI, are motivated by the fact that failures are geographically clustered in such cases. We address the challenge of determining faults with incomplete symptom information due to a limited number of reporting nodes in the network. netCSI consists of two parts: hypotheses generation algorithm, and ranking algorithm. When constructing the hypotheses list of potential causes, we make novel use of the positive and negative symptoms to improve the precision of the results. The ranking algorithm is based on conditional failure probability models that account for the geographic correlation of the network objects in clustered failures. We evaluate the performance of netCSI for networks with both random and realistic topologies. We compare the performance of netCSI with an existing fault diagnosis algorithm, MAX-COVERAGE, and achieve an average gain of 128\% in accuracy for realistic topologies.

Mission-driven sensor networks usually have special lifetime requirements. However, the density of the sensors may not be large enough to satisfy the coverage requirement while meeting the lifetime constraint at the same time. Sometimes, coverage has to be traded for network lifetime. In this paper, we study how to schedule sensors to maximize their coverage during a specified network lifetime. Unlike sensor deployment, where the goal is to maximize the spatial coverage, our objective is to maximize the spatial-temporal coverage by scheduling sensors' activity after they have been deployed. Since the optimization problem is NP-hard, we first present a centralized heuristic whose approximation factor is proved to be 1/2, and then, propose a distributed parallel optimization protocol (POP). In POP, nodes optimize their schedules on their own but converge to local optimality without conflict with one another. Theoretical and simulation results show that POP substantially outperforms other schemes in terms of network lifetime, coverage redundancy, convergence time, and event detection probability.

Continuously monitoring the link performance is important to network diagnosis. Recently, active probes sent between end systems are widely used to monitor the link performance. In this paper, we address the problem of minimizing the probing cost and achieving identifiability in link monitoring. Given a set of links to monitor, our objective is to select as few probing paths as possible to cover all of them, and the selected probing paths can uniquely identify all identifiable links being monitored. We propose an algorithm based on the linear system model to find out all sets of probing paths that can uniquely identify an identifiable link. We extend the bipartite model to reflect the relation between a set of probing paths and the link that can be uniquely identified. Through the extended bipartite model, our optimization problem is transformed into the classic set cover problem, which is NP-hard. Therefore, we propose a heuristic based algorithm to greedily select the probing paths. Our method eliminates two types of redundant probing paths, i.e., those that can be replaced by others and those that cannot be used to achieving identifiability. Simulations based on real network topologies show that our approach can achieve identifiability with very low probing cost. Compared with prior work, our method is more general and has better performance.

Effective data forwarding in Delay Tolerant Networks (DTNs) is challenging, due to the low node density, unpredictable node mobility and lack of global information in such networks. Most of the current data forwarding schemes choose the nodes with the best cumulative capability of contacting others as relays to carry and forward data, but these nodes may not be the best relay choices within a short time period, due to the heterogeneity of the transient node contact patterns. In this paper, we propose a novel approach to improve the performance of data forwarding in DTNs by exploiting the transient node contact patterns. We formulate the transient node contact patterns based on experimental studies of realistic DTN traces, and propose appropriate forwarding metrics based on these patterns to improve the effectiveness of data forwarding decision. When applied to various data forwarding strategies, our proposed forwarding metrics achieve much better performance compared to existing schemes with similar forwarding cost.

Existing routing algorithms for Delay Tolerant Networks(DTNs) assume that nodes are willing to forward packets for others. In the real world, however, most people are socially selfish; i.e., they are willing to forward packets for nodes with whom they have social ties but not others, and such willingness varies with the strength of the social tie. Following the philosophy of design for user, we propose a Social Selfishness Aware Routing (SSAR) algorithm to allow user selfishness and provide better routing performance in an efficient way. To select a forwarding node, SSAR considers both users' willingness to forward and their contact opportunity, resulting in a better forwarding strategy than purely contact-based approaches. Moreover, SSAR formulates the data forwarding process as a Multiple Knapsack Problem with Assignment Restrictions (MKPAR) to satisfy user demands for selfishness and performance. Trace-driven simulations show that SSAR allows users to maintain selfishness and achieves better routing performance with low transmission cost.

Self-monitoring the sensor statuses such as liveness, node density and residue energy is critical for maintaining the normal operation of the sensor network. When building the monitoring architecture, most existing work focuses on minimizing the number of monitoring nodes. However, with less monitoring points, the false alarm rate may increase as a consequence. In this paper, we study the fundamental tradeoff between the number of monitoring nodes and the false alarm rate in the wireless sensor networks. Specifically, we propose fully distributed monitoring algorithms, to build up a poller-pollee based architecture with the objective to minimize the number of overall pollers while bounding the false alarm rate. Based on the established monitoring architecture, we further explore the hop-by-hop aggregation opportunity along the multihop path from the polee to the poller, with the objective to minimize the monitoring overhead. We show that the optimal aggregation path problem is NP-hard and propose an opportunistic greedy algorithm, which achieves an approximation ratio of 5/4. As far as we know, this is the first proved constant approximation ratio applied to the aggregation path selection schemes over the wireless sensor networks.

Recent popularization of personal hand-held mobile devices makes it important to characterize the mobility pattern of mobile device users, so as to accurately predict user mobility in the future. Currently, the user mobility pattern is mostly characterized at a coarse-grained level, in the form of transition among wireless Access Points (APs). There is limited research effort on the fine-grained characterization of geographical user movement. In this paper, we present a novel approach to characterize the steady-state and transient-state user mobility behaviors at a fine-grained level, based on the Hidden Markov Model (HMM) formulation of user mobility. By applying our approach on both realistic mobility traces and synthetic mobility scenarios, we show that our approach is effective in characterizing user mobility pattern and making accurate mobility prediction. We also experimentally demonstrate that fine-grained user mobility knowledge is more effective to improve the performance of a variety of mobile computing applications.

Some recent studies have shown that cooperative cache can improve the system performance in wireless P2P networks such as ad hoc networks and mesh networks. However, all these studies are at a very high level, leaving many design and implementation issues unanswered. In this paper, we present our design and implementation of cooperative cache in wireless P2P networks, and propose solutions to find the best place to cache the data. We propose a novel asymmetric cooperative cache approach, where the data requests are transmitted to the cache layer on every node, but the data replies are only transmitted to the cache layer at the intermediate nodes that need to cache the data. This solution not only reduces the overhead of copying data between the user space and the kernel space, it also allows data pipelines to reduce the end-to-end delay. We also study the effects of different MAC layers, such as 802.11-based ad hoc networks and multi-interface-multichannel-based mesh networks, on the performance of cooperative cache. Our results show that the asymmetric approach outperforms the symmetric approach in traditional 802.11-based ad hoc networks by removing most of the processing overhead. In mesh networks, the asymmetric approach can significantly reduce the data access delay compared to the symmetric approach due to data pipelines.

Exploiting the multirate capability in mobile ad hoc networks (MANETs) is more complex than in single-hop WLANs because of the rate-distance and rate-hop count tradeoffs. This paper proposes path-centric on-demand rate adaptation for MANETs (PRAM) protocol. A unique feature that sets PRAM apart from most of previous studies is its path-centric approach. While others focus on finding the best data rate for each link and offering a routing path as a collection of links at their best rates, PRAM finds the best data rate for a source-destination pair and then, dynamically adapts it based on path lifetime and other factors. Another distinctive feature of PRAM is that it can be seamlessly incorporated with an on-demand routing protocol. Extensive performance study based on NS-2 has demonstrated that PRAM achieves as much as 71.7% higher packet delivery ratio than fixed-rate cases (6~54 Mbps) and as much as 43.2% higher than the multihop version of the well- known ARF mechanism in a wide range of network scenarios. It is also shown that PRAM is capable of using a mixture of data rates in an adaptive manner.

Content sharing through vehicle-to-vehicle communication can help people find their interested content on the road. In VANETs, due to limited contact duration and unreliable wireless connection, a vehicle can get the useful data only when it meets another vehicle and the encountered vehicle has the exactly matched data. However, the probability of such case is very low. To improve the performance of content sharing in intermittently connected VANETs, we propose a novel P2P content sharing scheme called Roadcast. Roadcast ensures popular data is more likely to be shared with other vehicles so that the overall query delay and the query hit ratio can be improved. Roadcast consists of two components called popularity aware content retrieval and popularity aware data replacement. The popularity aware content retrieval scheme makes use of information retrieval (IR) techniques to find the most relevant and popular data towards user's query. The popularity aware data replacement algorithm ensures that the density of different data is proportional to their popularity in the system steady state, which firmly obeys the optimal "square-root" replication rule. Results based on real city map and real traffic model show that Roadcast outperforms other content sharing schemes in VANETs.

In this paper, we describe oCast, an energy-optimal multicast routing protocol for wireless sensor networks. The general minimum-energy multicast problem is NP-hard. Intermittent connectivity that results from duty-cycling further complicates the problem. Nevertheless, we present both a centralized and distributed algorithm that are provably optimal when the number of destinations is small. This model is motivated by scenarios where sensors report to a small number of base stations or where data needs to be replicated on a small number of other nodes. We further propose an extended version of oCast, called Delay Bounded oCast (DB-oCast), which can discover optimal multicast trees under a predefined delay bound. Finally, we demonstrate the advantages of our schemes through both theoretical analysis and simulations.

In this paper, we study sensor enabled landmine networks by formulating a minimum-cost mine selection problem. The problem arises in a target defence scenario, where the objective is to destroy the intruding targets using the minimum-cost pre-deployed mines. Due to the problem complexity, we first transform it using a novel bucket-tub model, and then propose several approximation algorithms. Among them, it is shown that the layering algorithm can achieve an approximation ratio of alpha ldr f, where alpha ges 1 is the tunable relaxation factor and f is the maximum number of mines that a target is associated with, and that the greedy algorithm has an approximation ratio of SigmajRj, where Rjis the coefficient in the related integer program. We also present a localized greedy algorithm which is shown to produce the same solution set as the global greedy algorithm. Theoretical analysis and extensive simulations demonstrate the effectiveness of the proposed algorithms.

For sensor networks deployed in unattended, harsh environments, the knowledge of sensor statuses such as liveness, node density and residue energy, is critical for maintaining the normal operation of the network. In this paper, we propose a poller-pollee based architecture to monitor the sensor status, focusing on two important issues: false alarm and energy efficiency. To reduce the false alarm rate, each pollee is monitored by multiple pollers. However, this approach will increase the power and bandwidth consumption. To address this issue, we propose a novel solution where the monitored sensor sends the status reports to different pollers in a round robin manner. In this way, bandwidth and power can be saved, and the false alarm rate can be reduced. We further propose a simple randomized algorithm to select the optimal number of pollers to stochastically minimize the expected total energy consumption due to monitoring. Theoretical analyses and simulations are used to demonstrate the effectiveness of the proposed techniques.

The IP multimedia subsystem (IMS) is being deployed in the third generation (3G) networks since it supports many kinds of multimedia services. However, the security of IMS networks has not been fully examined. This paper presents a novel DoS attack against IMS. By congesting the presence service, a core service of IMS, a malicious attack can cause chained automatic reaction of the system, thus blocking all the services of IMS. Because of the low-volume nature of this attack, an attacker only needs to control several clients to paralyze an IMS network supporting one million users. To address this DoS attack, we propose an online early defense mechanism, which aims to first detect the attack, then identify the malicious clients, and finally block them. We formulate this problem as a change-point detection problem, and solve it based on the non-parametric GRSh test. Through trace-driven experiments, we demonstrate that our defense mechanism can throttle this DoS attack within a short defense time window while generating few false alarms.

Recently, cellular phone networks have begun allowing third-party applications to run over certain open-API phone operating systems such as Windows Mobile, Iphone and Google's Android platform. However, with this increased openness, the fear of rogue programs written to propagate from one phone to another becomes ever more real. This paper proposes a counter-mechanism to contain the propagation of a mobile worm at the earliest stage by patching an optimal set of selected phones. The counter-mechanism continually extracts a social relationship graph between mobile phones via an analysis of the network traffic. As people are more likely to open and download content that they receive from friends, this social relationship graph is representative of the most likely propagation path of a mobile worm. The counter mechanism partitions the social relationship graph via two different algorithms, balanced and clustered partitioning and selects an optimal set of phones to be patched first as those which have the capability to infect the most number of other phones. The performance of these partitioning algorithms is compared against a benchmark random partitioning scheme. Through extensive trace-driven experiments using real IP packet traces from one of the largest cellular networks in the US, we demonstrate the efficacy of our proposed counter-mechanism in containing a mobile worm.

To disseminate content with content-based routing (CBR), the routing paths of subscription and publication cannot be determined a priori and have to be computed hop-by-hop, which brings in scalability and robustness challenges in large scale mobile ad hoc networks (MANETs). In this paper, we propose a novel two-tier content-based routing protocol called CLONE (Community and Location aware content based routing). In CLONE, we map the human community structure of social networks to MANETs. The whole network can be self-organized into communities based on the interest locality, so that most subscriptions inside a community can be served in an intra-community fashion, reducing the communication overhead and the response delay. Community construction is self-organized and completely distributed. Analytical and simulation results demonstrate the effectiveness of CLONE in large-scale MANETs.

Node mobility and end-to-end disconnections in Delay Tolerant Networks (DTNs) greatly impair the effectiveness of data dissemination. Although social-based approaches can be used to address the problem, most existing solutions only focus on forwarding data to a single destination. In this paper, we are the first to study multicast in DTNs from the social network perspective. We study multicast in DTNs with single and multiple data items, investigate the essential difference between multicast and unicast in DTNs, and formulate relay selections for multicast as a unified knapsack problem by exploiting node centrality and social community structures. Extensive trace-driven simulations show that our approach has similar delivery ratio and delay to the Epidemic routing, but can significantly reduce the data forwarding cost measured by the number of relays used.

Source location privacy is an important issue in sensor network monitoring applications. It is difficult to be addressed by traditional security mechanisms, because an external attacker may perform simple traffic analysis to trace back to the event source. Solutions such as flooding or using dummy messages have the drawback of introducing a large amount of message overhead. In this paper, we avoid using network-wide dummy messages by utilizing beacons at the MAC layer. Beacons are sent out regularly, which essentially forms a constant-rate of dummy messages. Using beacons to replace the dummy messages may increase the delivery delay of event information because beacons are only sent out at the predefined beacon interval, but this latency can be controlled. To do this, we propose a cross- layer solution in which the event information is first propagated several hops through a MAC-layer beacon. Then, it is propagated at the routing layer to the destination to avoid further beacon delays. Simulation results show that our cross-layer solutions can maintain low message overhead and high privacy, while controlling delay.

The demand for efficient data dissemination/access techniques to find relevant data from within a sensor network has led to the development of data-centric sensor (DCS) networks, where the sensor data instead of sensor nodes are named based on attributes such as event type or geographic location. However, saving data inside a network also creates security problems due to the lack of tamper resistance of the sensor nodes and the unattended nature of the sensor network. For example, an attacker may simply locate and compromise the node storing the event of his interest. To address these security problems, we present pDCS, a privacy-enhanced DCS network which offers different levels of data privacy based on different cryptographic keys. pDCS also includes an efficient key management scheme to facilitate the management of multiple types of keys used in the system. In addition, we propose several query optimization techniques based on Euclidean Steiner tree and keyed bloom filter (KBF) to minimize the query overhead while preserving query privacy. Finally, detailed analysis and simulations show that the KBF scheme can significantly reduce the message overhead with the same level of query delay and maintain a very high level of query privacy.

The widespread acceptance of RFID tags in inventory control applications has allowed the development of increasingly complex and useful inventory management techniques. This paper approaches the problem of real-time inventory querying in a large warehouse. We use a combination of powered, wireless- capable active RFID tags and a mobile RFID reader to design a querying system that uses both a mesh network formed with the active RFID tags and the mobile reader to balance query latency and total network lifetime. We implemented and simulated our system on Crossbow MicaZ motes and a custom robot platform. Our results show that our hybrid algorithm balances query latency and network lifetime more effectively than mesh network- only and mobile reader-only algorithms. In particular, we see network power consumption reduction of up to 60% and a 15% reduction in total distance travelled by the mobile reader. We conclude that introducing a mobile reader to active tag networks allows the design of flexible network algorithms that can reduce the impact of battery life on the network.

Some recent studies have shown that cooperative cache can improve the system performance in wireless P2P networks such as ad hoc networks and mesh networks. However, all these studies are at a very high level, leaving many design and implementation issues unanswered. In this paper, we present our design and implementation of cooperative cache in wireless P2P networks. We propose a novel asymmetric cooperative cache approach, where the data requests are transmitted to the cache layer on every node, but the data replies are only transmitted to the cache layer at the intermediate nodes that need to cache the data. This solution not only reduces the overhead of copying data between the user space and the kernel space, it also allows data pipelines to reduce the end-to-end delay. We also study the effects of different MAC layers such as 802.11 based ad hoc networks and multi-interface multi-channel based mesh networks, on the performance of cooperative cache. Our results show that the asymmetric approach outperforms the symmetric approach in traditional 802.11 based ad hoc networks by removing most of the processing overhead. In mesh networks, the asymmetric approach can significantly reduce the data access delay compared to the symmetric approach due to data pipelines.

To prolong the lifetime of sensor networks, various scheduling schemes have been designed to reduce the number of active sensors. However, some scheduling strategies, such as partial coverage scheduling and target coverage scheduling, may result in disconnected network topologies, due to the low density of the active nodes. In such cases, traditional routing algorithms cannot be applied, and the shortest path discovered by these algorithms may not have the minimum packet delivery latency. In this paper, we address the problem of finding minimum latency routes in intermittently connected sensor networks by proposing an on-demand minimum latency (ODML) routing algorithm. Since on-demand routing algorithm does not work well when the source and destination frequently communicate with each other, we propose two proactive minimum latency routing algorithms: optimal-PML and quick-PML. Theoretical analysis and simulation results show that (1) ODML can effectively identify minimum latency routes which have much smaller latency than the shortest path, and (2) optimal-PML can minimize the routing message overhead and quick-PML can significantly reduce the route acquisition delay.

For sensor networks deployed to monitor and report real events, event source anonymity is an attractive and critical security property, which unfortunately is also very difficult and expensive to achieve. This is not only because adversaries may attack against sensor source privacy through traffic analysis, but also because sensor networks are very limited in resources. As such, a practical tradeoff between security and performance is desirable. In this paper, for the first time we propose the notion of statistically strong source anonymity, under a challenging attack model where a global attacker is able to monitor the traffic in the entire network. We propose a scheme called FitProbRate, which realizes statistically strong source anonymity for sensor networks. We also demonstrate the robustness of our scheme under various statistical tests that might be employed by the attacker to detect real events. Our analysis and simulation results show that our scheme, besides providing source anonymity, can significantly reduce real event reporting latency compared to two baseline schemes.

Today vehicle theft rate is very high, thus tracking/alarming systems are being deployed with an increasingly popularity. These systems however bear some limitations such as high cost, high false-alarm rate, and easy to be disabled. This paper describes the design, implementation and evaluation of a Sensor-network-based Vehicle Anti-Theft System (SVATS) to address these limitations. In this system, the sensors in the vehicles that are parked within the same parking area first form a sensor network, then monitor and identify possible vehicle thefts by detecting unauthorized vehicle movement. When an unauthorized movement is detected, an alert will be reported to a base station in the parking area, which sends warning messages to the security office. This paper focuses on the technical issues specific to the system such as topology management, theft detection, and intra-vehicle networking.

Because of cost and resource constraints, sensor nodes do not have a complicated hardware architecture or operating system to protect program safety. Hence, the notorious buffer-overflow vulnerability that has caused numerous Internet worm attacks could also be exploited to attack sensor networks. We call the malicious code that exploits a buffer-overflow vulnerability in a sensor program sensor worm. Clearly, sensor worm will be a serious threat, if not the most dangerous one, when an attacker could simply send a single packet to compromise the entire sensor network. Despite its importance, so far little work has been focused on sensor worms.

In vehicular Ad-hoc networks (VANETs), vehicles can gain short connections to the Internet by using wireless access points (AP). A significant part of the connection time is the time required for acquiring an IP address via dynamic host configuration protocol (DHCP). Depending on a vehicle's speed and the AP coverage area, DHCP can consume up to 100 percent of a vehicle's available connection time. We propose the IP Passing Protocol to reduce the overhead of obtaining an IP address to under one-tenth of a second. This is done without modifying either DHCP or AP software. We explore scalable implementations and describe the dynamics of the IP Passing Protocol. We also show our protocol will significantly improve efficiency, reduce latency, and increase vehicle connectivity.

Significant progress has been made to achieve video streaming over wireless ad hoc networks. However, there is not much work on providing security. Is existing security solution good enough for securing video streaming over ad hoc networks? In this paper, we discover a cross-layer dropping attack against video streaming. We first identify a general IP layer dropping attack and then reveal its destructive impact by leveraging the application layer information (e.g., video streaming). Through simulations, we quantify the impact of this attack as a function of several performance parameters such as delivery ratio, hop number and the number of attackers. The surprising result with this attack is that with a 94% delivery ratio, the receiver still cannot watch the video! We also propose several possible solutions to address the dropping attacks. Due to the unique characteristics of this attack, as long as malicious nodes exist, the network will suffer from this dropping attack.

Sensors deployed to monitor the surrounding environment report such information as event type, location, and time when a real event of interest is detected. An adversary may identify the real event source through eavesdropping and traffic analysis. Previous work has studied the source location privacy problem under a local adversary model. In this work, we aim to provide a stronger notion: event source unobservability, which promises that a global adversary cannot know whether a real event has ever occurred even if he is capable of collecting and analyzing all the messages in the network at all the time. Clearly, event source unobservability is a desirable and critical security property for event monitoring applications, but unfortunately it is also very difficult and expensive to achieve for resource-constrained sensor network.

Hop-by-hop data aggregation is a very important technique for reducing the communication overhead and energy expenditure of sensor nodes during the process of data collection in a sensor network. However, because individual sensor readings are lost in the per-hop aggregation process, compromised nodes in the network may forge false values as the aggregation results of other nodes, tricking the base station into accepting spurious aggregation results. Here a fundamental challenge is how can the base station obtain a good approximation of the fusion result when a fraction of sensor nodes are compromised? To answer this challenge, we propose SDAP, a Secure Hop-by-hop Data Aggregation Protocol for sensor networks. SDAP is a general-purpose secure data aggregation protocol applicable to multiple aggregation functions. The design of SDAP is based on the principles of divide-and-conquer and commit-and-attest . First, SDAP uses a novel probabilistic grouping technique to dynamically partition the nodes in a tree topology into multiple logical groups (subtrees) of similar sizes. A commitment-based hop-by-hop aggregation is performed in each group to generate a group aggregate. The base station then identifies the suspicious groups based on the set of group aggregates. Finally, each group under suspect participates in an attestation process to prove the correctness of its group aggregate. The aggregate by the base station is calculated over all the group aggregates that are either normal or have passed the attestation procedure. Extensive analysis and simulations show that SDAP can achieve the level of efficiency close to an ordinary hop-by-hop aggregation protocol while providing high assurance on the trustworthiness of the aggregation result. Last, prototype implementation on top of TinyOS shows that our scheme is practical on current generation sensor nodes such as Mica2 motes.

Data generated in wireless sensor networks may not all be alike: some data may be more important than others and hence may have different delivery requirements. In this paper, we address differentiated data delivery in the presence of congestion in wireless sensor networks. We propose a class of algorithms that enforce differentiated routing based on the congested areas of a network and data priority. The basic protocol, called congestion-aware routing (CAR), discovers the congested zone of the network that exists between high-priority data sources and the data sink and, using simple forwarding rules, dedicates this portion of the network to forwarding primarily high-priority traffic. Since CAR requires some overhead for establishing the high-priority routing zone, it is unsuitable for highly mobile data sources. To accommodate these, we define MAC-enhanced CAR (MCAR), which includes MAC-layer enhancements and a protocol for forming high-priority paths on the fly for each burst of data. MCAR effectively handles the mobility of high-priority data sources, at the expense of degrading the performance of low-priority traffic. We present extensive simulation results for CAR and MCAR, and an implementation of MCAR on a 48-node testbed.

Mobile sinks are needed in many sensor network applications for efficient data collection, data querying, localized sensor reprogramming, identifying, and revoking compromised sensors, and other network maintenance. Employing mobile sinks however raises a new security challenge: if a mobile sink is given too many privileges, it will become very attractive for attack and compromise. Using a compromised mobile sink, an adversary may easily bring down or even take over the sensor network. Thus, security mechanisms that can tolerate mobile sink compromises are essential. In this article, based on the principle of least privilege , we first propose an efficient scheme to restrict the privilege of a mobile sink without impeding its ability to carry out any authorized operations for an assigned task. In addition, we present an extension to allow conditional trajectory change due to unexpected events. To further reduce the possible damage caused by a compromised mobile sink, we propose efficient message forwarding schemes for deleting the privilege assigned to a compromised mobile sink immediately after its compromise has been detected. Through detailed analysis, simulation, and real implementation, we show that our schemes are secure and efficient, and are highly practical for sensor networks consisting of the current generation of sensors.

The demand for efficient data dissemination/access techniques to find the relevant data from within a sensor network has led to the development of data-centric sensor networks (DCS), where the sensor data as contrast to sensor nodes are named based on attributes such as event type or geographic location. However, saving data inside a network also creates security problems due to the lack of tamper-resistance of the sensor nodes and the unattended nature of the sensor network. For example, an attacker may simply locate and compromise the node storing the event of his interest. To address these security problems, we present pDCS, a privacy-enhanced DCS network which offers different levels of data privacy based on different cryptographic keys. In addition, we propose several query optimization techniques based on Euclidean Steiner Tree and Keyed Bloom Filter to minimize the query overhead while providing certain query privacy. Finally, detailed analysis and simulations show that the Keyed Bloom Filter scheme can significantly reduce the message overhead with the same level of query delay and maintain a very high level of query privacy.

Node compromise is a serious security threat that hinders the successful deployment of large-scale wireless sensor networks. A node compromise often consists of three stages: physically obtaining and compromising the sensors, redeploying the compromised sensors, and compromised nodes launching attacks after their rejoining the network. By far, all the proposed compromise detection schemes address this problem at the third stage. In this paper, we make the first attempt to detect node compromise at the second stage. Our motivation is that for some applications an attacker may not be able to precisely deploy the compromised sensors back into their original positions. Thus, the detection of location change will become an indication of a potential node compromise. We name this node redeployment detection problem. We propose two approaches to detect node redeployment, based on the change of node neighborship and the change of measured distances between nodes, respectively. Our simulation study shows that both schemes can detect node redeployment effectively (with low false positive rate and high detection rate).

Mobile sensors are useful in many environments because they can move to increase the sensing coverage. In this paper, we present a mobile sensor prototype in which the Mica2 sensor node is used to control the movement of the robot built with commercial off-the-shelf (COTS) components. We use a sensor relocation application to demonstrate the feasibility of our design. In the sensor relocation application, after a sensor node failure creates a coverage hole, a mobile sensor node is relocated to cover the hole in a timely and energy-efficient way. We present a distributed sensor relocation algorithm and provide novel solutions to implement this algorithm in our mobile sensor platform. Experimental results show that our relocation algorithm can reduce the sensor relocation time and balance the energy consumption of the mobile nodes.

A prerequisite for secure communications between two sensor nodes is that these nodes exclusively share a pairwise key. Although numerous pairwise key establishment (PKE) schemes have been proposed in recent years, most of them have no guarantee for direct key establishment, no resilience to a large number of node compromises, no resilience to dynamic network topology, or high overhead. To address these limitations, we propose a novel random perturbation-based (RPB) scheme in this paper. The scheme guarantees that any two nodes can directly establish a pairwise key without exposing any secret to other nodes. Even after a large number of nodes have been compromised, the pairwise keys shared by non-compromised nodes remain highly secure. Moreover, the scheme adapts to changes in network topology and incurs low computation and communication overhead. To the best of our knowledge, the RPB scheme is the only one that provides all these salient features without relying on public key cryptography. Through prototype-based evaluation, we show that the RPB scheme is highly efficient and practical for current generation of sensor nodes. In particular, to support a sensor network with up to 216 nodes, establishing a pairwise key of 80 bits between any two 8-bit, 7.37-MHz MICA2 motes only requires about 0.13 second of CPU time, 0.33 KB RAM space, and 15 KB ROM space per node.

Mobile sensors are useful in many environments because they can move to increase the sensing coverage. In this paper, we present a mobile sensor prototype in which the Mica2 sensor node is used to control the movement of the robot built with commercial off-the-shelf (COTS) components. We use a sensor relocation application to demonstrate the feasibility of our design. In the sensor relocation application, after a sensor node failure creates a coverage hole, a mobile sensor node is relocated to cover the hole in a timely and energy-efficient way.

Sensors that operate in an unattended, harsh or hostile environment are vulnerable to compromises because their low costs preclude the use of expensive tamper-resistant hardware. Thus, an adversary may reprogram them with malicious code to launch various insider attacks. Based on verifying the genuineness of the running program, we propose two distributed software-based attestation schemes that are well tailored for sensor networks. These schemes are based on a pseudorandom noise generation mechanism and a lightweight block-based pseudorandom memory traversal algorithm. Each node is loaded with pseudorandom noise in its empty program memory before deployment, and later on multiple neighbors of a suspicious node collaborate to verify the integrity of the code running on this node in a distributed manner. Our analysis and simulation show that these schemes achieve high detection rate even when multiple compromised neighbors collude in an attestation process.

Many applications that make use of sensor networks require secure communication. Because asymmetric-key solutions are difficult to implement in such a resource-constrained environment, symmetric-key methods coupled with a priori key distribution schemes have been proposed to achieve the goals of data secrecy and integrity. These approaches typically assume that all nodes are similar in terms of capabilities and, hence, deploy the same number of keys in all sensors in a network to provide the aforementioned protections. In this paper, we demonstrate that a probabilistic unbalanced distribution of keys throughout the network that leverages the existence of a small percentage of more capable sensor nodes can not only provide an equal level of security, but also reduce the consequences of node compromise. To fully characterize the effects of the unbalanced key management system, we design, implement, and measure the performance of a complementary suite of key establishment protocols known as LIGER. Using their predeployed keys, nodes operating in isolation from external networks can securely and efficiently establish keys with each other. Should resources such as a backhaul link to a key distribution center (KDC) become available, networks implementing LIGER automatically incorporate and benefit from such facilities. Detailed experiments demonstrate that the unbalanced distribution in combination with the multimodal LIGER suite offers a robust and practical solution to the security needs in sensor networks

Constructing a sensor network with a mix of mobile and static sensors can achieve a balance between sensor coverage and sensor cost. In this paper, we design two bidding protocols to guide the movement of mobile sensors in such sensor networks to increase the coverage to a desirable level. In the protocols, static sensors detect coverage holes locally by using Voronoi diagrams and bid mobile sensors to move. Mobile sensors accept the highest bids and heal the largest holes. Simulation results show that our protocols achieve suitable trade-off between coverage and sensor cost

In wireless sensor networks, sensor nodes are capable of not only measuring real world phenomena, but also storing, processing, and transferring these measurements. Many techniques have been proposed for disseminating sensing data. However, most of them are not efficient in the scenarios where a huge amount of sensing data are generated, but only a small portion of them are queried. In this paper, we first propose an index-based data dissemination scheme to address the problem. With this scheme, sensing data are collected, processed, and stored at the nodes close to the detecting nodes, and the location information of these storing nodes is pushed to some index nodes, which act as the rendezvous points for sinks and sources. To address the issues of fault tolerance and load balance, we extend the scheme with an adaptive ring-based index (ARI) technique in which the index nodes for one event type form a ring surrounding the location which is determined by the event type, and the ring can be dynamically reconfigured. Considering that frequently updating or querying index nodes may cause high overhead, we also propose a lazy index updating (LIU) mechanism and a lazy index querying (LIQ) mechanism to reduce the overhead. Analysis and simulations are conducted to evaluate the performance of the proposed scheme. The results show that the proposed scheme outperforms the external storage-based scheme, the DCS scheme, and the local storage-based schemes with flood-response style. The results also show that using ARI can tolerate clustering failures and achieve load balance and using LIU (LIQ) can further improve the system performance. is pushed to some index nodes,

Abstract — Many applications that make use of sensor networks require secure communication. Because asymmetric-key solutions are difficult to implement in such a resource-constrained environment, symmetric-key methods coupled with a priori key distribution schemes have been proposed to achieve the goals of data secrecy and integrity. These approaches typically assume that all sensors are similar in terms of capabilities, and hence deploy the same number of keys in all sensors in a network to provide the aforementioned protections. In this paper we demonstrate that a probabilistic unbalanced distribution of keys throughout the network that leverages the existence of a small percentage of more capable sensor nodes can not only provide an equal level of security but also reduce the consequences of node compromise. We demonstrate the effectiveness of this approach on small networks using a variety of trust models and then demonstrate the application of this method to very large systems. The approach and analysis presented in this paper can be applied to all protocols that use probabilistic keys including those that employ broadcast mechanisms, hash functions or polynomials for the generation of keys.

Abstract — Multi-hop data delivery through vehicular ad hoc networks is complicated by the fact that vehicular networks are highly mobile and frequently disconnected. To address this issue, we adopt the idea of carry and forward, where a moving vehicle carries the packet until a new vehicle moves into its vicinity and forwards the packet. Different from existing carry and forward solutions, we make use of the predicable vehicle mobility, which is limited by the traffic pattern and the road layout. Based on the existing traffic pattern, a vehicle can find the next road to forward the packet to reduce the delay. We propose several vehicle-assisted data delivery (VADD) protocols to forward the packet to the best road with the lowest data delivery delay. Experimental results are used to evaluate the proposed solutions. Results show that the proposed VADD protocols outperform existing solutions in terms of packet delivery ratio, data packet delay and protocol overhead. Among the proposed VADD protocols, the Hybrid Probe (H-VADD) protocol has much better performance.

Hop-by-hop data aggregation is a very important technique for reducing the communication overhead and energy expenditure of sensor nodes during the process of data collection in a sensor network. However, because individual sensor readings are lost in the per-hop aggregation process, compromised nodes in the network may forge false values as the aggregation results of other nodes, tricking the base station into accepting spurious aggregation results. Here a fundamental challenge is: how can the base station obtain a good approximation of the fusion result when a fraction of sensor nodes are compromised.To answer this challenge, we propose SDAP, a Secure Hop-by-hop Data Aggregation Protocol for sensor networks. The design of SDAP is based on the principles of divide-and-conquer and commit-and-attest. First, SDAP uses a novel probabilistic grouping technique to dynamically partition the nodes in a tree topology into multiple logical groups (subtrees) of similar sizes. A commitment-based hop-by-hop aggregation is performed in each group to generate a group aggregate. The base station then identifies the suspicious groups based on the set of group aggregates. Finally, each group under suspect participates in an attestation process to prove the correctness of its group aggregate. Our analysis and simulations show that SDAP can achieve the level of efficiency close to an ordinary hop-by-hop aggregation protocol while providing certain assurance on the trustworthiness of the aggregation result. Moreover, SDAP is a general-purpose secure aggregation protocol applicable to multiple aggregation functions.

The majority of security schemes available for sensor networks assume deployment in areas without access to a wired infrastructure. More specifically, nodes in these networks are unable to leverage key distribution centers (KDCs) to assist them with key management. In networks with a heterogeneous mix of nodes, however, it is not unrealistic to assume that some more powerful nodes have at least intermittent contact with a backbone network. For instance, an air-deployed battlefield network may have to operate securely for some time until uplinked friendly forces move through the area. We therefore propose LIGER, a hybrid key management scheme for heterogeneous sensor networks that allows systems to operate in both the presence and absence of a KDC. Specifically, when no KDC is available, nodes communicate securely with each other based upon a probabilistic unbalanced method of key management. The ability to access a KDC allows nodes to probabilistically authenticate neighboring devices with which they are communicating. We also demonstrate that this scheme is robust to the compromise of both low and high capability nodes and that the same keys can be used for both modes of operation. Detailed experiments and simulations are used to show that LIGER is a highly practical solution for the current generation of sensors and the unbalanced approach can significantly reduce network initialization time.

Secure data dissemination in wireless ad hoc and sensor networks has recently received a great deal of attention. A variety of protocols have been proposed in order to ensure secure data delivery across these systems; however, the majority of these schemes assume the presence of public or pre-established symmetric keys. Accordingly, the cost of key management has not been incorporated into secure routing mechanisms in this setting. This paper considers the expenses incurred by sensor networks implementing secure routing schemes on top of probabilistic symmetric key management schemes. Specifically, we examine the overhead observed from proactive and reactive key establishment mechanisms for networks using a balanced method of key management. Through extensive simulation, we quantify more realistic costs for the application of secure hop-by-hop routing in sensor networks

Unlike conventional range queries, a range-monitoring query is a continuous query. It requires retrieving mobile objects inside a user-defined region and providing continuous updates as the objects move into and out of the region. In this paper, we present an efficient technique for real-time processing of such queries. In our approach, each mobile object is associated with a resident domain, and when an object moves, it monitors its spatial relationship with its resident domain and the monitoring areas inside it. An object reports its location to the server when it crosses over some query boundary or moves out of its resident domain. In the first case, the server updates the affected query results accordingly, while in the second case, the server determines a new resident domain for the object. This distributive approach achieves an accurate and real-time monitoring effect with minimal mobile communication and server processing costs. Our approach also allows a mobile object to negotiate a resident domain based on its computing capability. By having a larger resident domain, a more capable object has less of a chance of moving out of it and having to request a new one. As a result, both communication and server processing costs are reduced. Our comprehensive performance study shows that the proposed technique can be highly scalable in supporting location-based services in a wireless environment that consists of a large number of mobile devices.

Abstract-Adequate coverage is very important for sensor networks to fulfill the issued sensing tasks. In many working environments, it is necessary to make use of mobile sensors, which can move to the correct places to provide the required coverage. In this paper, we study the problem of placing mobile sensors to get high coverage. Based on Voronoi diagrams, we design two sets of distributed protocols for controlling the movement of sensors, one favoring communication and one favoring movement. In each set of protocols, we use Voronoi diagrams to detect coverage holes and use one of three algorithms to calculate the target locations of sensors it holes exist. Simulation results show the effectiveness of our protocols and give insight on choosing protocols and calculation algorithms under different application requirements and working conditions.

Most researches in ad hoc networks focus on routing and not much work has been done on data access. A common technique used to improve the performance of data access is caching. Cooperative caching, which allows the sharing and coordination of cached data among multiple nodes, can further explore the potential of the caching techniques. Due to mobility and resource constraints of ad hoc networks, cooperative caching techniques designed for wired networks may not be applicable to ad hoc networks. In this paper, we design and evaluate cooperative caching techniques to efficiently support data access in ad hoc networks. We first propose two schemes: CacheData, which caches the data, and CachePath, which caches the data path. After analyzing the performance of those two schemes, we propose a hybrid approach (HybridCache), which can further improve the performance by taking advantage of CacheData and CachePath while avoiding their weaknesses. Cache replacement policies are also studied to further improve the performance. Simulation results show that the proposed schemes can significantly reduce the query delay and message complexity when compared to other caching schemes.

It is well known that IEEE 802.11 provides a physical layer multirate capability and, hence, MAC layer mechanisms are needed to exploit this capability. Several solutions have been proposed to achieve this goal. However, these solutions only consider how to exploit good channel quality for the direct link between the sender and the receiver. Since IEEE 802.11 supports multiple transmission rates in response to different channel conditions, data packets may be delivered faster through a relay node than through the direct link if the direct link has low quality and low rate. In this paper, we propose a novel MAC layer relay-enabled distributed coordination function (DCF) protocol, called rDCF, to further exploit the physical layer multirate capability. We design a protocol to assist the sender, the relay node, and the receiver to reach an agreement on which data rate to use and whether to transmit the data through a relay node. Considering various issues, such as, bandwidth utilization, channel errors, and security, we propose techniques to further improve the performance of rDCF. Simulation results show that rDCF can significantly reduce the packet delay, improve the system throughput, and alleviate the impact of channel errors on fairness

In peer-to-peer networks, indices are used to map data id to nodes that host the data. The performance of data access can be improved by actively pushing indices to interested nodes. This paper proposes the Dynamic-tree based Update Propagation (DUP) scheme, which builds the update propagation tree to facilitate the propagation of indices. Because the update propagation tree only involves nodes that are essential for update propagation, the overhead of DUP is very small and the query latency is significantly reduced.

To achieve high throughput in wireless networks, smart forwarding and processing of packets in access routers are critical for overcoming the effects of the wireless links. However, these services cannot be provided if data sessions are protected using end-to-end encryption as with IPsec, because the information needed by these algorithms resides inside the portion of the packet that is encrypted, and can therefore not be used by the access routers. A previously proposed protocol, called multi-layered IPsec (ML-IPsec) modifies IPsec in a way so that certain portions of the datagram may be exposed to intermediate network elements, enabling these elements to provide performance enhancements. In this paper we extend ML-IPsec to deal with mobility and make it suitable for wireless networks. We define and present performance measurements of an efficient key distribution protocol to enable fast ML-IPsec session initialization, and two mobility protocols that are compatible with mobile IP and maintain ML-IPsec sessions. Our measurements show that, depending on the mobility protocol chosen, integrated mobile IP/ML-IPsec handoffs result in a pause of 56-105 milliseconds, of which only 31-85 milliseconds may be attributed to ML-IPsec. Further, we provide detailed discussion and performance measurements of our ML-IPsec implementation. We find the resulting protocol only marginally reduces throughput compared to scenarios in which IPsec is used (4%), and when coupled with SNOOP, greatly increases throughput over scenarios using standard TCP over IPsec (165% on average).

Recently there has been a great deal of research on using mobility in sensor networks to assist in the initial deployment of nodes. Mobile sensors are useful in this environment because they can move to locations that meet sensing coverage requirements. This paper explores the motion capability to relocate sensors to deal with sensor failure or respond to new events. We define the problem of sensor relocation and propose a two-phase sensor relocation solution: redundant sensors are first identified and then relocated to the target location. We propose a Grid-Quorum solution to quickly locate the closest redundant sensor with low message complexity, and propose to use cascaded movement to relocate the redundant sensor in a timely, efficient and balanced way. Simulation results verify that the proposed solution outperforms others in terms of relocation time, total energy consumption, and minimum remaining energy.

When a sensor network is deployed in hostile environments, the adversary may compromise some sensor nodes, and use the compromised nodes to inject false sensing reports or modify the reports sent by other nodes. In order to defend against the attacks with low cost, researchers have proposed symmetric group key-based en-route filtering schemes, such as SEF [F. Ye et al., March 2004] and I-LHAP [S. Zhu et al., 2004]. However, if the adversary has compromised a large number of nodes, many group keys can be captured, and the filtering schemes may become ineffective or even useless. To deal with node compromise, the compromised nodes should be identified and the innocent nodes should update their group keys. Some existing intruder identification schemes can be used to identify the compromised nodes, but most existing group rekeying schemes are not suitable for sensor networks since they have large overhead and are not scalable. To address the problem, we propose a family of predistribution and local collaboration-based group rekeying (PCGR) schemes. These schemes are designed based on the ideas that future group keys can be preloaded to the sensor nodes before deployment, and neighbors can collaborate to protect and appropriately use the preloaded keys. Extensive analyses and simulations are conducted to evaluate the proposed schemes, and the results show that the proposed schemes can achieve a good level of security, outperform most previous group rekeying schemes, and significantly improve the effectiveness of filtering false data.

It is well known that IEEE 802.11 provides a physical layer multi-rate capability, and hence MAC layer mechanisms are needed to exploit this capability. Several solutions have been proposed to achieve this goal. However, these solutions only consider how to exploit good channel quality for the direct link between the sender and the receiver. Since IEEE 802.11 supports multiple transmission rates in response to different channel conditions, data packets may be delivered faster through a relay node than through the direct link if the direct link has low quality and low rate. In this paper, we propose a novel MAC layer relay-enabled distributed coordination function (DCF) protocol, called rDCF, to further exploit the physical layer multi-rate capability. We design a protocol to assist the sender, the relay node and the receiver to reach an agreement on which data rate to use and whether to transmit the data through a relay node. Considering various issues such as bandwidth utilization and channel errors, we propose techniques to further improve the performance of rDCF. Simulation results show that rDCF can significantly improve the system performance when the channel quality of the direct link is poor.

The existing time synchronization schemes in sensor networks were not designed with security in mind, thus leaving them vulnerable to security attacks. In this paper, we first identify various attacks that are effective to several representative time synchronization schemes, and then focus on a specific type of attack called delay attack, which cannot be addressed by cryptographic techniques. Next we propose two approaches to detect and accommodate the delay attack. Our first approach uses the generalized extreme studentized deviate (GESD) algorithm to detect multiple outliers introduced by the compromised nodes; our second approach uses a threshold derived using a time transformation technique to filter out the outliers. Finally we show the effectiveness of these two schemes through extensive simulations

Mobile sinks are needed in many sensor network applications for efficient data collection, data querying, localized sensor reprogramming, identifying and revoking compromised sensors, and other network maintenance. Employing mobile sinks however raises a new security challenge: if a mobile sink is given too many privileges, it will become very attractive for attack and compromise. Using a compromised mobile sink, an adversary may easily bring down or even take over the sensor network. Thus, security mechanisms that can tolerate mobile sink compromises are essential. In this paper, based on the principle of least privilege, we first propose several efficient schemes to restrict the privilege of a mobile sink without impeding its capability of carrying out any authorized operations for an assigned task. To further reduce the possible damages caused by a compromised mobile sink, we then propose efficient message forwarding schemes for depriving the privilege assigned to a compromised mobile sink immediately after its compromise has been detected. Through detailed analysis and simulations, we show that our schemes are secure and efficient, and are highly practical for sensor networks consisting of the current generation of sensors.

Caching techniques can be used to reduce bandwidth consumption and data access delay in wireless ad hoc networks. When cache is used, cache consistency issues must be addressed. To maintain strong cache consistency in some strategic scenarios (e.g., battle fields), the invalidation-based approach is preferred due to its low overhead. However, this approach may suffer from some security attacks. For example, a malicious node (intruder) may drop, insert or modify invalidation messages to mislead the receivers to use stale data or unnecessarily invalidate the data that is still valid. In this paper, we propose a solution based on the IR-based cache invalidation strategy to prevent intruders from dropping or modifying the invalidation messages. Although digital signatures can be used to protect IRs, it has significantly high overhead in terms of computation and bandwidth consumption. To address this problem, we propose a family of randomized grouping based schemes for intrusion detection and damage recovery. Extensive analysis and simulations are used to evaluate the proposed schemes. The results show that our solution can achieve a good level of security with low overhead.

Reducing the power consumption of the wireless network interface (WNl) is an effective way to prolong the battery lifetime of the mobile terminal. It takes some time for the WNI to transit from the power-saving mode to the active mode. This transition delay and the error-prone wireless link bring many challenges for designing power-aware and QoS-aware service models. In this paper, we present a novel power-conserving service model for streaming applications over wireless networks. At the base station side, a new scheduling algorithm, called rate-based bulk scheduling (RBS), is designed to decide which flow should be served at which time. The mobile terminal relies on a proxy to buffer data so that the WNI can sleep for a long time period to save power. To deal with channel errors, a novel adaptive technique is presented to adjust the sleep time of the WNI according to the channel condition. Through analysis, we prove that RBS can provide delay guarantee and it is more power efficient than other rate-based fair queuing algorithms. We use audio-on-demand as a case study to evaluate the performance of RBS. Experimental results show that RBS achieves excellent QoS provision for each flow and significantly reduces the power consumption.

A set of enhancements to the IEEE 802.11 standard, viz. the IEEE 802.11e have been proposed to meet the increasing demand for quality of service. The standard provides a means for service differentiation by using multiple traffic categories at each node, where each traffic category has its own individual parameters such as priority, inter-frame space and contention window size. After each successful transmission, the contention window size is decreased based on a static equation, which may result in poor channel utilization and a decrease on the system throughput. In this paper, we propose a new protocol, called enhanced distributed coordination function with dual-measurement (EDCF-DM), to address this issue. EDCF-DM is based on the idea of reducing the number of idle slots by dynamically varying the contention window size according to the current traffic state of the traffic categories at each node. Meanwhile, it carefully adapts the contention window size based on the network condition of the system to avoid incurring extra collisions. Extensive simulations are performed to evaluate the proposed protocol. Simulation results demonstrate that EDCF-DM provides a good service differentiation and outperforms the standard 802.11e in terms of channel utilization, throughput and packet delay.

Sensor deployment is an important issue in designing sensor networks. We design and evaluate distributed self-deployment protocols for mobile sensors. After discovering a coverage hole, the proposed protocols calculate the target positions of the sensors where they should move. We use Voronoi diagrams to discover the coverage holes and design three movement-assisted sensor deployment protocols, VEC (vector-based), VOR (Voronoi-based), and minimax based on the principle of moving sensors from densely deployed areas to sparsely deployed areas. Simulation results show that our protocols can provide high coverage within a short deploying time and limited movement.

Most researches in ad hoc networks focus on routing, and not much work has been done on data access. A common technique used to improve the performance of data access is caching. Cooperative caching, which allows the sharing and coordination of cached data among multiple nodes, can further explore the potential of the caching techniques. Due to mobility and resource constraints of ad hoc networks, cooperative caching techniques designed for wired network may not be applicable to ad hoc networks. In this paper, we design and evaluate cooperative caching techniques to efficiently support data access in ad hoc networks. We first propose two schemes: cachedata which caches the data, and cachepath which caches the data path. After analyzing the performance of those two schemes, we propose a hybrid approach (hybridcache) which can further improve the performance by taking advantage of cachedata and cachepath while avoiding their weaknesses. Simulation results show that the proposed schemes can significantly reduce the query delay and message complexity when compared to other caching schemes.

Sensor nodes have limited sensing range and are not very reliable. To obtain accurate sensing data, many sensor nodes should he deployed and then the collaboration among them becomes an important issue. In W. Zhang and G. Cao, a tree-based approach has been proposed to facilitate sensor nodes collaborating in detecting and tracking a mobile target. As the target moves, many nodes in the tree may become faraway from the root of the tree, and hence a large amount of energy may be wasted for them to send their sensing data to the root. We address the tree reconfiguration problem. We formalize it as finding a min-cost convoy tree sequence, and solve it by proposing an optimized complete reconfiguration scheme and an optimized interception-based reconfiguration scheme. Analysis and simulation are conducted to compare the proposed schemes with each other and with other reconfiguration schemes. The results show that the proposed schemes are more energy efficient than others.

The fair queuing model has been widely used to provide QoS for flows sharing a wireless channel. In fluid fair queuing, a flow cannot reclaim its service loss due to absence. As a result, fair queuing models that emulate fluid fair queuing cannot provide good service differentiation under bursty data traffic. On the other hand, strict priority queuing (SPQ) can provide good service differentiation at the cost of QoS provision. To achieve both service differentiation and QoS provision, we propose a new service model called absence compensation fair queuing. The basic idea is to allow a flow to get compensation of its service loss due to absence. Since the proposed service model is based on fair queuing, QoS provision is guaranteed. We first verify these properties by analysis, and then evaluate the performance compared to weighted fair queuing (WFQ) and SPQ. Simulation results show that our service model can provide much better service differentiation than WFQ, and outperforms SPQ in terms of QoS provision.

Many studies show that the wireless network interface (WNI) accounts for a significant part of the power consumed by mobile terminals. Thus, putting the WNI into sleep when it is idle is an effective technique to save power. To support streaming applications, existing techniques cannot put the WNI into sleep due to strict delay requirements. We present a novel power-aware and QoS-aware service model over wireless networks. In the proposed model, mobile terminals use proxies to buffer data so that the WNIs can sleep for a long time period. To achieve power-aware communication while satisfying the delay requirement of each flow, a scheduling scheme, called priority-based bulk scheduling (PBS), is designed to decide which flow should be served at which time. Through analysis, we prove that the PBS service model can provide delay assurance and achieve power efficiency. We use audio-on-demand and Web access as case studies to evaluate the performance of the PBS service model. Experimental results show that PBS achieves excellent QoS provision for each flow and significantly reduces the power consumption.

In wireless sensor networks, efficiently disseminating data from a dynamic source to multiple mobile sinks is important for applications such as mobile target detection and tracking. A tree-based multicasting scheme can be used. However, due to the short communication range of each sensor node and the frequent movement of sources and sinks, a sink may fail to receive data due to broken paths, and the tree should frequently be reconfigured to reconnect sources and sinks. To address the problem, we propose a dynamic proxy tree-based framework. A big challenge in implementing the framework is how to reconfigure the proxy tree efficiently as sources and sinks change. We model the problem as on-line construction of a minimum Steiner tree in a Euclidean plane, and propose centralized schemes to solve it. Considering the strict energy constraints in wireless sensor networks, we further propose two distributed on-line schemes, a shortest path-based (SP) scheme and a spanning range-based (SR) scheme. Extensive simulations are conducted to evaluate the schemes. The results show that the distributed schemes have similar performance to the centralized ones, and among the distributed schemes, SR outperforms SP.

Internet-based mobile ad hoc network (IMANET) combines a mobile ad hoc network (MANET) and the Internet to provide universal information accessibility. Although caching frequently accessed data items in mobile terminals (MTs) improves the communication performance in an IMANET, it brings a critical design issue when data items are updated. We analyze several push and pull-based cache invalidation strategies for IMANETS. A global positioning system (GPS) based connectivity estimation (GPSCE) scheme is first proposed to assess the connectivity of an MT for supporting any cache invalidation mechanism. Then, we propose a pull-based approach, called aggregate cache based on demand (ACOD) scheme, to find the queried data items efficiently. In addition, we modify two push-based cache invalidation strategies, proposed for cellular networks, to work in IMANETs. These are a modified timestamp (MTS) scheme, and an MTS with updated invalidation report (MTS+UIR) scheme. Simulation results indicate that our proposed strategy provides high throughput, low query latency, and low communication overhead, and thus, is a viable approach for implementation in IMANETS.

To provide satisfactory coverage is very important in many sensor network applications such as military surveillance. In order to obtain the required coverage in harsh environments, mobile sensors are helpful since they can move to cover the area not reachable by static sensors. Previous work on mobile sensor deployment is based on a round by round process, where sensors move iteratively until the maximum coverage is reached. Although these solutions can deploy mobile sensors in a distributed way, the mobile sensors may move in a zig-zag way and waste a lot of energy compared to moving directly to the final location. To address this problem, we propose a proxy-based sensor deployment protocol. Instead of moving iteratively, sensors calculate their target locations based on a distributed iterative algorithm, move logically, and exchange new logical locations with their new logical neighbors. Actual movement only occurs when sensors determine their final locations. Simulation results show that the proposed protocol can significantly reduce the energy consumption compared to previous work, while maintaining similar coverage.

We consider in this paper how to leverage heterogeneous mobile computing capability for efficient processing of real-time range-monitoring queries. In our environment, each mobile object is associated with a resident domain and when an object moves, it monitors its spatial relationship with its resident domain and the monitoring areas inside it. An object reports its location to server whenever its movement affects any query results (i.e., crossing any query boundaries) or it moves out of its resident domain. In the first case, the server updates the affected query results accordingly while in the second case, the server determines a new resident domain for the object. This distributive approach is able to provide accurate query results and real-time monitoring updates with minimal location update and server processing costs. In addition, the new scheme allows a mobile object to negotiate a resident domain based on its computing capability. Thus, a more capable object can have a larger resident domain reducing its chance of having to request a new resident domain because of moving out of it. This feature makes the new approach highly adaptive to the heterogeneity of mobile objects. In our performance study, we compare it with an existing approach using simulation. The study shows that the new technique is many times better in reducing mobile communication and server processing costs.

Prefetching has been widely used to improve system performance in mobile environments. Since prefetching also consumes system resources such as bandwidth and power, it is important to consider the system overhead when designing a prefetching scheme. This paper proposes a cache-miss-initiated prefetch (CMIP) scheme to address this issue. The CMIP scheme relies on two prefetch sets: the always-prefetch set and the miss-prefetch set. The always-prefetch set consists of data that should always be prefetched if possible. The miss-prefetch set consists of data that are closely related to the cache-missed data item. When a cache miss happens, instead of sending an uplink request to ask for the cache-missed data item only, the client also requests for the data items which are within the miss-prefetch set. This reduces not only future cache misses but also the number of uplink requests. Note that the client can ask for several data items in one uplink request with little additional cost. We propose novel algorithms to mine the association rules and use them to construct the two prefetch sets. Simulation results show that our CMIP scheme can greatly improve the system performance in terms of improved cache hit ratio, reduced uplink requests, and negligible additional traffic.

In mobile ad hoc networks, nodes move freely and link/node failures are common. This leads to frequent network partitions, which may significantly degrade the performance of data access in ad hoc networks. When the network partition occurs, mobile nodes in one network are not able to access data hosted by nodes in other networks. In this paper, we deal with this problem by applying data replication techniques. Existing data replication solutions in both wired or wireless networks aim at either reducing the query delay or improving the data accessibility. As both metrics are important for mobile nodes, we propose schemes to balance the tradeoffs between data accessibility and query delay under different system settings and requirements. Simulation results show that the proposed schemes can achieve a balance between these two metrics and provide satisfying system performance.

Most of the prefetch techniques used in the current cache management schemes do not consider power constraints of the mobile clients and other factors such as the size of the data items, the data access rate, and the data update rate. In this paper, we address these issues by proposing a power-aware prefetch scheme, called adaptive value-based prefetch (AVP) scheme. The AVP scheme defines a value function which can optimize the prefetch cost to achieve better performance. Also, AVP dynamically adjusts the number of prefetches to get better tradeoff between performance and power. As stretch is widely adopted as a performance metric for variable-size data requests, we show by analysis that the proposed approach can indeed achieve the optimal performance in terms of stretch when power consumption is considered. Simulation results demonstrate that our algorithm significantly outperforms existing prefetching algorithms under various scenarios.

Most existing work on sensor networks concentrates on finding efficient ways to forward data from the information source to the data centers, and not much work has been done on collecting local data and generating the data report. This paper studies this issue by proposing techniques to detect and track a mobile target. We introduce the concept of dynamic convoy tree-based collaboration, and formalize it as a multiple objective optimization problem which needs to find a convoy tree sequence with high tree coverage and low energy consumption. We propose an optimal solution which achieves 100% coverage and minimizes the energy consumption under certain ideal situations. Considering the real constraints of a sensor network, we propose several practical implementations: the conservative scheme and the prediction-based scheme for tree expansion and pruning; the sequential and the localized reconfiguration schemes for tree reconfiguration. Extensive experiments are conducted to compare the practical implementations and the optimal solution. The results show that the prediction-based scheme outperforms the conservative scheme and it can achieve similar coverage and energy consumption to the optimal solution. The experiments also show that the localized reconfiguration scheme outperforms the sequential reconfiguration scheme when the node density is high, and the trend is reversed when the node density is low.

Abstract We propose a unified framework consisting of a differential bandwidth reservation (DBR) algorithm and a Quality of Service (QoS)‐aware admission control scheme to provide QoS guarantees to on‐going connections in cellular networks. The differential bandwidth reservation policy uses a sector of cells in making the bandwidth reservation for accepting a new call. Based on the distance of the target cells in the sectors, two different bandwidth reservation policies are applied to optimize the connection dropping rate (CDR), while maintaining a competitive connection blocking rate (CBR). In addition, two possible mobile terminal (MT) movements are analyzed using the DBR mechanism. In the first case, no knowledge of an MT's moving path is assumed to be known, while in the second case, prior knowledge of a user profile is used in bandwidth reservation, and it is called user profile‐based DBR (UPDBR) algorithm. Using the DBR scheme, we propose an admission control algorithm that uses varying number of cells in a sector to meet admission decisions. Extensive simulation is performed to evaluate our methodology. Comparison of the proposed scheme with two prior schemes shows that our approach is not only capable of providing better QoS guarantees, but is also flexible in terms of using varying number of cells in satisfying the high‐level QoS requirements. Copyright © 2004 John Wiley & Sons, Ltd.

Internet based mobile ad hoc network (IMANET) is an emerging technique that combines a wired network (e.g. Internet) and a mobile ad hoc network (manet) for developing a ubiquitous communication infrastructure. However, imanet has several limitations to fulfill users' demands to access various kinds of information such as limited accessibility to the wired Internet, insufficient wireless bandwidth, and longer message latency. In this paper, we address the issues involved in information search and access in IMANET. A broadcast based simple search (SS) algorithm and an aggregate caching mechanism are proposed for improving the information accessibility and reducing average communication latency in imanet. As part of the aggregate cache, a cache admission control policy and a cache replacement policy, called time and distance sensitive (TDS) replacement, are developed to reduce the cache miss ratio and improve the information accessibility. We evaluate the impact of caching, cache management, and access points, which are connected to the Internet, through extensive simulation. The simulation results indicate that the proposed aggregate cache can significantly improve an imanet performance in terms of throughput and average number of hops to access data. In particular, with aggregate caching, more than 200% improvement in throughput is achieved compared to the imanet with no cache case, when the access pattern follows a Zipf distribution.

It is well known that IEEE 802.11 provides a physical layer multirate capability. In this paper, we propose a novel MAC layer relay-enabled point coordination function (PCF) protocol, called rPCF, to exploit this capability. With multiple data rates in response to different channel conditions, if the direct link has low data rate, data packets may be delivered faster through a relay node. To enable MAC layer relay, the access point needs to collect information about the channel conditions, and notify mobile nodes which data rate to use and whether to use a relay node. We design protocols to achieve this goal and refine these protocols to minimize the control overhead. Simulation results show that rPCF can significantly improve the system performance in terms of system throughput and transmission delay with a very small control overhead.

In some harsh environments, manually deploying sensors is impossible. Alternative methods may lead to imprecise placement resulting in coverage holes. To provide the required high coverage in these situations, we propose to deploy sensor networks composed of a mixture of mobile and static sensors in which mobile sensors can move from dense areas to sparse areas to improve the overall coverage. This paper presents a bidding protocol to assist the movement of mobile sensors. In the protocol, static sensors detect coverage holes locally by using Voronoi diagrams, and bid for mobile sensors based on the size of the detected hole. Mobile sensors choose coverage holes to heal based on the bid. Simulation results show that our algorithm provides suitable tradeoff between coverage and sensor cost.

In current sensor networks, sensor nodes are capable of not only measuring real world phenomena, but also storing, processing and transferring these measurements. Many data dissemination techniques have been proposed for sensor networks. However, these techniques may not work well in a large scale sensor network where a huge amount of sensing data are generated, but only a small portion of them are queried. In this paper, we propose an index-based data dissemination scheme to address the problem. This scheme is based on the idea that sensing data are collected, processed and stored at the nodes close to the detecting nodes, and the location information of these storing nodes is pushed to some index nodes, which act as the rendezvous points for sinks and sources. We further extend the scheme with an adaptive ring-based index (ARI) technique, in which the index nodes for one event type form a ring surrounding the location which is determined by the event type, and the ring can be dynamically reconfigured for fault tolerance and load balance. Analysis and simulations are conducted to evaluate the performance of the proposed index-based scheme. The results show that the index-based scheme outperforms the external storage-based scheme, the DCS scheme, and the local storage-based schemes with flood-response style. The results also show that using ARI can tolerate clustering failures and achieve load balance.

Caching frequently accessed data items on the client side is an effective technique for improving performance in a mobile environment. Classical cache invalidation strategies are not suitable for mobile environments due to frequent disconnections and mobility of the clients. One attractive cache invalidation technique is based on invalidation reports (IRs). However, the IR-based cache invalidation solution has two major drawbacks, which have not been addressed in previous research. First, there is a long query latency associated with this solution since a client cannot answer the query until the next IR interval. Second, when the server updates a hot data item, all clients have to query the server and get the data from the server separately, which wastes a large amount of bandwidth. In this paper, we propose an IR-based cache invalidation algorithm, which can significantly reduce the query latency and efficiently utilize the broadcast bandwidth. Detailed analytical analysis and simulation experiments are carried out to evaluate the proposed methodology. Compared to previous IR-based schemes, our scheme can significantly improve the throughput and reduce the query latency, the number of uplink request, and the broadcast bandwidth requirements.

Bluetooth is a new short-range radio technology to form a small wireless system. In most of the current Bluetooth products, the master polls the slaves in a round robin manner and it may waste a significant amount of power. We propose an adaptive power conserving scheme to address this problem. The proposed solution schedules each flow based on its predictive rate and achieves power optimization based on a low-power mode existing in Bluetooth standard. Unlike other research work related to low-power, we also consider QoS of each flow. Theoretical analyses verify that our scheme can achieve throughput guarantees, delay guarantees, and fairness guarantees. Simulation results demonstrate that our scheme can save a significant amount of power compared to the round robin scheme and it shows that there exists a tradeoff between power and delay under various traffic models.

Most of the prefetch techniques used in the current cache management schemes do not consider the power constraints of the mobile clients and other factors such as the size of the data items, the data access rate, and the data update rate. We address these issues by proposing a power-aware prefetch scheme, called the value-based adaptive prefetch (VAP) scheme. The VAP scheme defines a value function which can optimize the prefetch cost to achieve better performance. Also, VAP dynamically adjusts the number of prefetches based on the current energy level to prolong the system running time. As stretch is widely adopted as a performance metric for variable-size data requests, we show by analysis that the proposed algorithm can indeed achieve the optimal performance in terms of stretch when power consumption is considered. Simulation results demonstrate that our algorithm significantly outperforms existing prefetching algorithms under various scenarios.

Bluetooth is a promising technology aimed at supporting short-range wireless communication. To achieve the advantage of simplicity and low-power, the master/slave model is used. However, this model has some drawbacks since no direct link exists between any two slaves in a piconet. Consequently, slave-to-slave communications must go through the master, and the master has to use extra bandwidth to forward the packets exchanged between slaves. We propose a time-slot leasing (TSL) and an enhanced TSL (ETSL) approach to address these drawbacks. Simulation results demonstrate that the TSL approach, especially the ETSL approach, can significantly improve the system performance compared to the standard master/slave model.

We propose an admission control scheme to guarantee a certain level of QoS to on-going connections in cellular networks. This admission control scheme is based on a differential bandwidth reservation policy that uses a sector of cells in making bandwidth reservation for accepting the new call. The sector of cells, which are located along the way to which the MT might move, is further divided into two regions depending on whether they have an immediate impact on the handoff or not. Two different bandwidth reservation policies are applied to cells in the two regions to optimize the connection dropping rate (CDR) while maximizing the connection blocking rate (CBR). In contrast to most prior policies, the proposed admission control scheme uses the varying number of cells in the sector to make the admission decision. Depending on the currently measured average CDR of the cells in the sector and the current cell where a new connection is generated, the number of cells involved in admission control can be changed dynamically to satisfy the target QoS (CDR) parameter. Simulation results indicate that our admission control policy guarantees the required CDR over the entire workload, while maintaining a competitive CBR. Comparison of the proposed scheme with two prior schemes shows that our approach is not only capable of providing better QoS guarantees, but also is more flexible in terms of using varying number of cells in satisfying a certain QoS requirement.

Recent work has shown that invalidation report (IR)-based cache management is an attractive approach for mobile environments. However, the IR-based cache invalidation solution has some limitations, such as long query delay, low bandwidth utilization, and it is not suitable for applications where data change frequently. In this paper, we propose a proactive cache management scheme to address these issues. Instead of passively waiting, the clients intelligently prefetch the data that are most likely used in the future. Based on a novel prefetch-access ratio concept, the proposed scheme can dynamically optimize performance or power based on the available resources and the performance requirements. To deal with frequently updated data, different techniques (indexing and caching) are applied to handle different components of the data based on their update frequency. Detailed simulation experiments are carried out to evaluate the proposed methodology. Compared to previous schemes, our solution not only improves the cache hit ratio, the throughput, and the bandwidth utilization, but also reduces the query delay and the power consumption.

In order to effectively utilize the broadcast bandwidth, it is necessary to have efficient on-line scheduling algorithms that can balance individual and overall performance and can scale in terms of database sizes and client populations. Moreover, the scheduling algorithm should be applicable to a heterogeneous environment where data items have different sizes. We address these issues in this paper. As stretch is widely adopted as a performance metric for variable-size data requests, we propose a broadcast scheduling algorithm to optimize the system performance in terms of stretch. We show by analysis that the proposed algorithm can indeed achieve the optimal performance in terms of stretch. Moreover, the proposed scheduling algorithm has very low decision overhead, which makes it a practical solution for on-demand broadcast scheduling. Simulation results demonstrate that our algorithm significantly outperforms existing scheduling algorithms under various scenarios.

Caching frequently accessed data items on the client side is an effective technique to improve the performance of data dissemination in mobile environments. Classical cache invalidation strategies are not suitable for mobile environments due to the disconnection and mobility of the mobile clients. One attractive cache invalidation technique is based on invalidation reports (IRs). However, IR-based approach suffers from long query latency and it cannot efficiently utilize the broadcast bandwidth. In this paper, we propose techniques to address these problems. We first extend the UIR-based approach to reduce the query latency. Then, we propose techniques to efficiently utilize the broadcast bandwidth based on counters associated with each data item. Novel techniques are designed to maintain the accuracy of the counter in case of server failures, client failures, and disconnections. Extensive simulations are provided and used to evaluate the proposed methodology. Compared to previous IR-based algorithms, the proposed solution can significantly reduce the query latency, improve the bandwidth utilization, and effectively deal with disconnections and failures.

It is a challenge to support QoS using limited frequency spectrum. In the literature, two orthogonal approaches are used to address the bandwidth utilization issue and the QoS provision issue; that is, channel allocation schemes have been proposed to improve bandwidth efficiency, whereas handoff management schemes, based on bandwidth reservation, have been proposed to guarantee a low connection dropping rate. However, little effort has been taken to address both issues together. We integrate distributed channel allocation and adaptive handoff management to provide QoS guarantees and efficiently utilize the bandwidth. Extensive simulations are provided and used to justify the analysis. Compared to previous schemes, the proposed scheme can improve the bandwidth utilization while providing QoS guarantees.

The need for mobility support on existing networks led to the formulation of the mobile IP protocol, which can provide seamless connectivity between fixed and mobile nodes. However, the inherent drawbacks of the protocol led to route optimization proposals of which one was accepted by the IETF. While attempting to solve the triangle routing problem, the adopted route optimization places extra constraints on the network nodes. This work is motivated by the need to find an alternative solution that would effectively solve the triangle routing problem without sacrificing performance, transparency, and simplicity. The proposed solution is an agent-based route optimization, which moves the tasks of maintaining and updating binding caches and encapsulating messages away from individual correspondent nodes to the correspondent agents. We setup a simulation environment to evaluate the proposed methodology. Simulation results show that the proposed protocol outperforms the existing protocols in terms of system message complexity, protocol simplicity, and scalability.

Mobile computing raises many new issues such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. Coordinated checkpointing is an attractive approach for transparently adding fault tolerance to distributed applications since it avoids domino effects and minimizes the stable storage requirement. However, it suffers from high overhead associated with the checkpointing process in mobile computing systems. Two approaches have been used to reduce the overhead: First is to minimize the number of synchronization messages and the number of checkpoints; the other is to make the checkpointing process nonblocking. These two approaches were orthogonal previously until the Prakash-Singhal algorithm combined them. However, we found that this algorithm may result in an inconsistency in some situations and we proved that there does not exist a nonblocking algorithm which forces only a minimum number of processes to take their checkpoints. In this paper; we introduce the concept of "mutable checkpoint," which is neither a tentative checkpoint nor a permanent checkpoint, to design efficient checkpointing algorithms for mobile computing systems. Mutable checkpoints can be saved anywhere, e.g., the main memory or local disk of MHs. In this way, taking a mutable checkpoint avoids the overhead of transferring large amounts of data to the stable storage at MSSs over the wireless network. We present techniques to minimize the number of mutable checkpoints. Simulation results show that the overhead of taking mutable checkpoints is negligible. Based on mutable checkpoints, our nonblocking algorithm avoids the avalanche effect and forces only a minimum number of processes to take their checkpoints on the stable storage.

The performance of a mutual exclusion algorithm is measured by the number of messages exchanged per critical section execution and the delay between successive executions of the critical section. There is a message complexity and synchronization delay trade-off in mutual exclusion algorithms. The Lamport algorithm (1978) and the Ricart-Agrawal algorithm (1981) both have a synchronization delay of T (T is the average message delay), but their message complexity is O(N). Maekawa's algorithm reduces the message complexity to O(/spl radic/N); however, it increases the synchronization delay to 2T. After Maekawa's algorithm (1985), many quorum-based mutual exclusion algorithms have been proposed to reduce the message complexity or the increase the resiliency to site and communication link failures. Since these algorithms are Maekawa-type algorithms, they also suffer from the long synchronization delay. We propose a delay-optimal quorum-based mutual exclusion algorithm which reduces the synchronization delay to T and still has a low message complexity of O(K) (K is the size of the quorum which can be as low as log N). A correctness proof and a detailed performance analysis are provided.

Caching frequently accessed data items on the client side is an effective technique to improve performance in a mobile environment. Classical cache invalidation strategies are not suitable for mobile environments due to the disconnection and mobility of the mobile clients. One attractive cache invalidation technique is based on invalidation reports (IRs). However, the IR-based cache invalidation solution has two major drawbacks, which have not been addressed is previous research. First, there is a long query latency associated with this solution since a client cannot answer the query until the next IR interval. Second, when the server updates a hot data item, all clients have to query the server and get the data from the server separately, which wastes a large amount of bandwidth. In this paper, we propose an IR-based cache invalidation algorithm which can significantly reduce the query latency and efficiently utilize the broadcast bandwidth. Detailed simulation experiments are carried out to evaluate the proposed methodology. Compared to previous IR-based schemes, our scheme can significantly improve the throughput and reduce the query latency, the number of uplink request, and the broadcast bandwidth requirements.

The efficient transmission of constant quality compressed video streams is complicated by the burstiness (both short term and long term) that video compression standards such as MPEG introduce. Most of the techniques in the literature are concentrated on stored video traffic smoothing or real-time video traffic smoothing. However there is a growing number of live video applications, such as videocasts of courses or television news, where many clients may be willing to tolerate a playback delay of several seconds or minutes in exchange for a smaller throughput requirement. Bandwidth smoothing for these live video applications is referred to as online smoothing. In order to measure the effectiveness of online video smoothing methods, in this paper, we first propose a benchmark algorithm which provides the upper bound on some of the smoothness parameters in the smoothing results. Based on this algorithm, we found that significant discrepancy exists between the results produced by the existing online smoothing methods and the upper bound. With this observation, we then focus on devising algorithms which improve the smoothing results.

Distributed channel allocation algorithms have received considerable attention due to their high reliability, and scalability. However, in these algorithms, a borrower needs to consult with its interference neighbors in order to borrow a channel. Thus, a borrower fails to borrow channels when it cannot communicate with anyone of its interference neighbors. In real-life networks, under heavy traffic load, a cell has a large probability to experience an intermittent network congestion or even a communication link failure. In these algorithms, since a cell has to consult with a large number of interference neighbors to borrow a channel. The failure rate will be much higher under heavy traffic load. In this paper, we first propose a fault-tolerant channel acquisition algorithm which tolerates communication link failures and node (MH or MSS) failures. Then, we present a channel selection algorithm and integrate it into the distributed acquisition algorithm. Simulation results show that our algorithm significantly reduces the failure rate under network congestion, communication link failures, and node failures compared to non-fault-tolerant channel allocation algorithms.

There are two approaches to design a distributed channel allocation algorithm: Search and Update. The update approach has shorter acquisition delay and lower call blocking rate, but higher message complexity. On the other hand, the search approach has lower message complexity, but longer acquisition delay and higher call blocking rate. In this paper, we propose a novel distributed acquisition algorithm, which has similar message complexity as the search approach and similar acquisition delay as the update approach. Also, we propose a channel selection algorithm, which has low call blocking rate and low intra-handoff overhead. By integrating the channel selection algorithm into our channel acquisition algorithm, we get a complete distributed channel allocation algorithm. By keeping the borrowed channels, our channel allocation algorithm adapts to the network traffic; i.e., free channels are transferred to hot cells to achieve load balance. Simulation results show that our algorithm significantly outperforms the search approach and the update approach in terms of call blocking rate, message complexity, and acquisition delay.

No abstract available.

No abstract available.

There are two approaches to design a distributed channel allocation algorithms: search and update. The update approach has shorter acquisition delay and lower call blocking rate, but higher message complexity. On the other hand, the search approach has lower message complexity, but longer acquisition delay and higher call blocking rate. In this paper we first propose a novel distributed acquisition algorithm, which has similar message complexity as the search approach and similar acquisition delay as the update approach. Then, we present a channel selection algorithm and integrate it into our distributed acquisition algorithm. By a rigorous analysis in terms of delay and message complexity, we show that our channel acquisition algorithm performs significantly better than the update approach (Dong and Lai 1997) and the search approach (Prakash et al. 1995). Detailed simulation experiments are carried out in order to evaluate our proposed methodology. The performance of our algorithm is compared with those of the geometric strategy (Baiocchi et al. 1995), the search approach, and the update approach. Simulation results show that our algorithm outperforms all other approaches in terms of call blocking probability under uniform as well as non-uniform traffic.

Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. We introduce the concept of mutable checkpoint, which is neither a tentative checkpoint nor a permanent checkpoint. Mutable checkpoints can be saved anywhere; e.g., the memory or local disk of MHs. In this way, taking a mutable checkpoint avoids the overhead of transferring a large amount of data to the stable storage in MSS over the wireless network. Based on mutable checkpoints, our non-blocking algorithm avoids the avalanche effect, minimizes the number of synchronization messages and forces only a minimum number of processes to take their checkpoints on the stable storage.

The performance of a mutual exclusion algorithm is measured by the number of messages exchanged per critical section execution and the delay between successive executions of the critical section. There is a message complexity and synchronization delay trade-off in mutual exclusion algorithms. Lamport's (1978) algorithm and Ricart and Agrawal's (1981) algorithm both have a synchronization delay of T, but their message complexity is O(N). Maekawa's (1985) algorithm reduces message complexity to O(/spl radic/N); however, it increases the synchronization delay to 2T. After Maekawa's algorithm, many quorum-based mutual exclusion algorithms have been proposed to reduce message complexity or increase the resiliency to site and communication link failures. Since these algorithms are Maekawa-type algorithms, they also suffer from long synchronization delay 2T. We propose a delay-optimal quorum-based mutual exclusion algorithm which reduces the synchronization delay to T and still has the low message complexity O(K) (K is the size of the quorum, which can be as low as log N). A correctness proof and detailed performance analysis are provided.

Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. R. Prakash and M. Singhal (1996) proposed the first coordinated checkpointing algorithm for mobile computing systems. However we showed that their algorithm may result in an inconsistency. In this paper, we prove a more general result about coordinated checkpointing: there does not exist a non-blocking algorithm that forces only a minimum number of processes to take their checkpoints. Based on the proof, we propose an efficient algorithm for mobile computing systems, which forces only a minimum number of processes to take checkpoints and dramatically reduces the blocking time during the checkpointing process. Correctness proofs and performance analysis of the algorithm are provided.

Coordinated checkpointing simplifies failure recovery and eliminates domino effects in case of failures by preserving a consistent global checkpoint on stable storage. However, the approach suffers from high overhead associated with the checkpointing process. Two approaches are used to reduce the overhead: first is to minimize the number of synchronization messages and the number of checkpoints, the other is to make the checkpointing process nonblocking. These two approaches were orthogonal in previous years until the Prakash-Singhal algorithm combined them. In other words, the Prakash-Singhal algorithm forces only a minimum number of processes to take checkpoints and it does not block the underlying computation. However, we found two problems in this algorithm. In this paper, we identify these problems and prove a more general result: there does not exist a nonblocking algorithm that forces only a minimum number of processes to take their checkpoints. Based on this general result, we propose an efficient algorithm that neither forces all processes to take checkpoints nor blocks the underlying computation during checkpointing. Also, we point out future research directions in designing coordinated checkpointing algorithms for distributed computing systems.