As wearables continue to gain widespread popularity, ensuring secure and convenient authentication becomes imperative to safeguard the data stored within these devices. However, existing wearable-based authentication solutions often rely on specialized and costly hardware, have limited applicability to specific scenarios, and are vulnerable to permanent biometrics leakages. To address these limitations, this paper explores the uniqueness of hand motions and subtle vibrations associated with face tapping. Specifically, we propose TapPass as a secure and convenient authentication solution that leverages face tapping signals captured via the Inertial Measurement Unit (IMU) in wrist-worn wearables for user authentication. To address significant interference from other body motions, we utilize the energy ratio and duration analysis of IMU measurements, followed by deep learning-based extraction of clean face tapping signals. Additionally, we explore the uniqueness of face tapping signals and extract effective features encompassing motion, vibration, and integral aspects. Based on these features, we generate cancelable biometrics leveraging a linear convolution-based approach, bestowing re-registration capabilities upon traditionally invariant biometrics. This solution effectively eliminates concerns surrounding permanent biometrics leakage and enables accurate authentication in both single-user and multi-user scenarios. Extensive experiments with 24 volunteers over three months demonstrate that TapPass achieves accurate authentication while effectively tackling major attacks and motion interference, all while maintaining user-friendliness.

Video analytics (VA) has become essential in applications, yet it poses significant challenges related to privacy preservation, network bandwidth, and computational resources. With the increasing deployment of high-definition cameras, privacy concerns and resource constraints are becoming critical barriers to the widespread adoption of VA systems. Existing privacy-preserving techniques are often static, inefficient, and fail to adapt to dynamic, real-time scenarios. In this paper, we propose Parachute, a dynamic, resource-aware and privacy-preserving video analytics system that adaptively switches between a local mode and a collaborative mode in response to traffic conditions. The system uses local reinforcement learning to enable each individual camera to operate independently, and switches to multi-agent reinforcement learning for coordinated optimization when local resources become limited. Experiments on real-world datasets demonstrate that Parachute effectively balances detection accuracy and privacy protection, outperforming baseline methods under bandwidth constraints.

Bandit with infinitely many arms (i.e.,X-armed bandit) is an important variant of multi-armed stochastic bandits, which is useful to model different networking problems under both wired and wireless settings, e.g., online caching, dynamic channel/power allocation, rate adaption. However, the problem becomes challenging when the characteristic of the networking setting is affected by the side information (i.e., context) and distributed behavior. In this paper, we identify and study a novel problem, decentralized contextualX-armed bandit, whereNagents collaboratively solve the problem within time spanT. The problem is nontrivial because the infinite arms challenge and statistical information consensus issue make our setting go beyond a simple combination ofX-armed bandits and multi-agent bandits. We develop a decentralized arm selection algorithm, called MACXUCB, by elaborating the contextual covering tree technique with a novelgossip communication protocol, which allows each agent to communicate efficiently with her neighbors. We prove that MACXUCB achieves a sublinear regret upper bound Õ(D1/2dX+2dY+4NdX+dY+1.5/dX+dY+2TdX+dY+1/dX+dY+2) given aggregation periodD, and the covering dimensionsdXanddYof arm and context spaces, which asymptomatically matches the lower bound Ω((DN)1/dX+dY+2TdX+dY+1/dX+dY+2) up to a time-dependent factor. Moreover, MACXUCB enjoys a sublinear communication complexity Õ(NDT0.5/(1–p)) when tuning parameterp∈ (0, 1/2). Finally, we carry out experiments to verify the performance of our MACXUCB. The results show the effectiveness and efficiency of our MACXUCB.

Swapping and purification are the two fundamental building blocks for high-fidelity entanglement distribution in multi-hop quantum networks. Unfortunately, it is still a mystery how they intertwine with each other to affect the fidelity and cost of end-to-end entanglements. Current scheduling algorithms consider this problem under relatively limited assumptions and a critical yet unjustified conjecture. In this work, we first consider more general assumptions with operation failures and, accordingly, extend a tree-based modeling for joint swapping and purification. Then, we analytically prove the previous conjecture that the optimal strategy underBinary systemis always to purify the entanglements before any swapping. This sheds light on the protocol and device design for quantum networks. We then further propose a tree-based algorithm, which can efficiently schedule swapping and purification along a path for bothBinaryandWerner systems. Extensive simulations of the proposed method against state-of-the-art solutions show that our method uses fewer entanglements to establish qualified end-to-end entanglements, and thus achieves higher network throughput.

Space-air-ground integrated networks can provide better connectivity and improved performance to ground users and thus have been well-recognized as the innovative trend for future 6G and beyond wireless systems. However, such heterogeneous and complex integrated communication systems also pose many new challenges for joint performance optimization. In this paper, we study the data delivery optimization problem in a space-air-ground network, where joint resource management decisions on user association, bandwidth allocation, cache placement, and high-altitude platform (HAP) location selection have to be optimized. To tackle this complex and challenging mixed integer programming optimization problem, we introduce a quantum-assisted method, named the Hybrid quantum-classical Benders’ Decomposition (HyBD) algorithm, which leverages the strengths of both quantum and classical computing. Experiments on the commercial quantum annealing machine demonstrate the effectiveness and robustness of the proposed HyBD method, with up to 64.3% improvement of iteration number and 82.8% improvement of average computation time over the classical Benders’ Decomposition algorithm on classical CPUs even at small scales, which demonstrates the quantum advantage.

In the era of 6G and beyond, space-aerial-terrestrial quantum networks (SATQNs) are poised to advance the development of a global-scale quantum Internet. These networks leverage free space optical satellite and aerial quantum networks to complement optical fiber-based terrestrial quantum networks to enable the distribution of high-fidelity quantum entanglement over long distances. However, establishing multi-hop end-to-end quantum entanglement remains highly challenging, not only due to time-varying link conditions and structural heterogeneity inherent in SATQNs, but also because noise in quantum channels and imperfections in quantum operations can degrade the quality of entanglement. To address this challenge, we formulate an optimization problem that maximizes SATQN throughput by jointly optimizing routing path selection and entanglement generation rates (PS-EGR) while ensuring high entanglement fidelity. The resulting problem is a mixed-integer linear programming (MILP) formulation, which is NP-hard. We propose a Benders’ decomposition (BD)-based approach to solve this problem efficiently. Specifically, the MILP is decomposed into a master problem for binary routing path selection and a subproblem for continuous entanglement generation rate optimization. Numerical results validate the effectiveness of the proposed PS-EGR scheme, offering critical insights into the optimization and deployment of SATQNs.

Incentivizing participation and coordinating decisions across hierarchical agents remain critical challenges in blockchain-enabled federated learning (FL) over edge clouds, especially when a coded FL is performed over a client-edge-cloud hierarchical system. This paper proposes a novel hybrid incentive framework that integrates multidimensional contract theory with reinforcement learning (RL)-based Stackelberg game modeling for such a system. Specifically, we design personalized contracts between edge servers and clients, addressing their heterogeneous data volume, privacy sensitivity, and computational capacity under incomplete information. Simultaneously, we model the task publisher's reward allocation to edge servers as a one-leader multi-follower Stackelberg game, where each follower acts based on local observations. A decentralized RL algorithm is proposed to learn optimal reward strategies without revealing other agents' private information, such as local data volume/quality. Simulations demonstrate that our method can converge to equilibrium and achieve effectiveness under incomplete information compared to baseline incentive schemes.

Swapping and purification are the two fundamental building blocks for multi-hop quantum networks. However, their interplay and its impact on end-to-end fidelity and cost are not yet fully explored. Existing scheduling algorithms address this problem under certain simplified assumptions and models that may not fully capture the complexities of real scenarios. In this work, we first consider more general assumptions that account for operation failures and extend a tree-based modeling approach for joint swapping and purification. Then, for the first time, we analytically prove the previous conjecture that the optimal strategy under Binary system is always to purify the entanglements before any swapping. This sheds light on the protocol and device design for entanglement distribution in quantum networks. We then further propose a tree-based algorithm, which can efficiently schedule swapping and purification along a path for both Binary and Werner systems. Extensive simulations have been conducted to evaluate the proposed method against the existing solutions, and the results show that our method uses fewer entanglements to establish qualified end-to-end entanglements and thus achieves higher network throughput.

Industrial Internet of Things (IIoT) is an emerging technology that digitizes industrial production and realizes Industry 4.0. However, it shows that IIoT is difficult to enable sophisticated downstream applications without eliciting all devices to achieve collaborative intelligence. Existing works on IIoT either require the consolidation of various IIoT devices’ data into a single centralized server which has potential privacy breach, or coordinate devices to learn a global model in privacy-preserving federated learning (FL) but assume data across devices has the sample feature space and neglect the heterogeneity of IIoT devices. In this article, we propose Meta-computing-driven vertical FL (VFL) algorithms to achieve collaborative intelligence in IIoT where heterogeneous devices have imperfect data with incomplete features. Specifically, we first provide the modeling of N devices’ VFL to collectively train the submodels and the common model. We present the computing graph to clearly indicate the gradient evaluation. To enable a fast convergence performance, we design a variance-reduced gradient estimator that can be seamlessly integrated into the basic VFL. Finally, we evaluate our proposed VFL by conducting experiments on the MNIST dataset regarding image recognition and the DAWM dataset for detecting anomalies in wafer manufacturing. The experimental results show that our VFL for IIoT is both effective and efficient.

Free weight training (FWT) is of utmost importance for physical well-being. The success of FWT depends largely on choosing the suitable workload, as improper selections can lead to suboptimal outcomes or injury. Current workload estimation approaches rely on manual recording and specialized equipment with limited feedback. Therefore, we introducePPGSpotter, a wearable PPG-based FWT monitoring system in a convenient, low-cost, and fine-grained manner. By characterizing the arterial geometry compressions caused by the deformation of distinct muscle groups,PPGSpottercan infer essential FWT factors such as current workload, repetitions, and exercise type and provide recommendations for workload adjustment. To remove pulse-related interference, we develop an arterial interference elimination approach based on adaptive filtering, effectively extracting the pure motion-derived signal (MDS). Furthermore, we explore 2D representations of MDS within the phase space to extract spatiotemporal information, enablingPPGSpotterto address the challenge of resisting sensor shifts. Finally, we leverage a multi-task CNN-based network and workload adjustment guidance to achieve personalized FWT monitoring. Extensive experiments with 15 participants confirm thatPPGSpottercan achieve promising workload estimation (0.59 kg RMSE), repetitions estimation (0.96 reps RMSE), and exercise type recognition (91.57% F1-score) while providing valid workload adjustment recommendations (0.22 kg RMSE).

Mobile edge computing (MEC) has revolutionized the way computational tasks are offloaded and latency is reduced by leveraging edge servers close to end devices. Efficient resource allocation and task offloading are crucial for enhancing system performance in MEC environments. Traditional reinforcement learning (RL) approaches have shown promise in optimizing resource allocation and task offloading problems. However, they often face challenges such as high computational complexity and the need for extensive training data. Quantum reinforcement learning (QRL) emerges as a promising solution to overcome these limitations by leveraging quantum computing principles to enhance efficiency and scalability. In this paper, we propose a hybrid quantum-classical non-sequential model for joint resource allocation and task offloading in MEC systems. Our model combines the advantages of RL in handling environmental dynamics and quantum computing in reducing adjustable parameters and accelerating the training process. Extensive experiments demonstrate that our proposed algorithm can achieve higher training and inference performance under various parameter settings compared to traditional RL models and previous QRL models.

Network function virtualization (NFV)-enabled space information network (SIN) has emerged as a promising method to facilitate global coverage and seamless service. This paper proposes a novel NFV-enabled SIN to provide end-to-end communication and computation services for ground users. Based on the multi-functional time expanded graph (MF-TEG), we jointly optimize the user association, virtual network function (VNF) deployment, and flow routing strategy (U-VNF-R) to maximize the total processed data received by users. The original problem is a mixed-integer linear program (MILP) that is intractable for classical computers. Inspired by quantum computing techniques, we propose a hybrid quantum-classical Benders’ decomposition (HQCBD) algorithm. Specifically, we convert the master problem of the Benders’ decomposition into the quadratic unconstrained binary optimization (QUBO) model and solve it with quantum computers. To further accelerate the optimization, we also design a multi-cut strategy based on the quantum advantages in parallel computing. Numerical results demonstrate the effectiveness and efficiency of the proposed algorithm and U-VNF-R scheme.

In the era of Internet of Things (IoT), multi-access edge computing (MEC)-enabled satellite-aerial-terrestrial integrated network (SATIN) has emerged as a promising technology to provide massive IoT devices with seamless and reliable communication and computation services. This paper investigates the cooperation of low Earth orbit (LEO) satellites, high altitude platforms (HAPs), and terrestrial base stations (BSs) to provide relaying and computation services for vastly distributed IoT devices. Considering the uncertainty in dynamic SATIN systems, we formulate a stochastic optimization problem to minimize the time-average expected service delay by jointly optimizing resource allocation and task offloading while satisfying the energy constraints. To solve the formulated problem, we first develop a Lyapunov-based online control algorithm to decompose it into multiple one-slot problems. Since each one-slot problem is a large-scale mixed-integer nonlinear program (MINLP) that is intractable for classical computers, we further propose novel hybrid quantum-classical generalized Benders’ decomposition (HQCGBD) algorithms to solve the problem efficiently by leveraging quantum advantages in parallel computing. Numerical results validate the effectiveness of the proposed MEC-enabled SATIN schemes.

Federated learning (FL)has achieved state-of-the-art performance in distributed machine learning with privacy preservation, which promotes AIoT. However, FL is restricted by the expensive communication cost due to exchanging a large number of model parameters and model updates (e.g., gradients) between the aggregator and participants in multiple rounds. This could be challenging in resource-constrained networks where devices are often resource-constrained in terms of computation and communication. Existing works mainly focus on improving communication efficiency from local training and model/gradient compression; nevertheless, studying communication efficiency for FL from the perspective of gradient estimation remains unexplored. In this paper, we bridge this gap by conducting a systematic study on gradient estimation for the communication-efficient FL. We propose a bandit-based gradient estimation-aware FL ($\mathtt{BGEFL }$) framework that can directly estimate participants’ gradients with limited bandit feedback (i.e., their local function values). We prove that$\mathtt{BGEFL }$enjoys an$\mathcal {O}(1)$communication complexity, that is a constant-size uplink communication in which each client uploads only one point’s feedback in the uplink. Moreover, our bandit-based gradient estimator is communication-efficient, unbiased, and stable. We prove theconvergenceperformance of$\mathtt{BGEFL }$for training strongly convex, general convex, and non-convex models. Finally, we evaluate our$\mathtt{BGEFL }$over several datasets and the experimental results demonstrate the effectiveness of$\mathtt{BGEFL }$.

Benders' decomposition (BD) algorithm constitutes a powerful mathematical programming method of solving mixed-integer linear programming (MILP) problems with a specific block structure. Nevertheless, BD still needs to solve an NP-hard quasi-integer programming master problem (MAP), which motivates us to harness the popular variational quantum algorithm (VQA) to assist BD. More specifically, we choose the popular quantum approximate optimization algorithm (QAOA) of the VQA family. We transfer the BD's MAP into a digital quantum circuit associated with a physically tangible problem-specific ansatz; and then solve it with the aid of a state-of-the-art digital quantum computer. Next, we evaluate the computational results and discuss the feasibility of the proposed algorithm. The hybrid approach advocated, which utilizes both classical and digital quantum computers, is capable of tackling many practical MILP problems in communication and networking, as demonstrated by a pair of case studies.

Numerous optimization scenarios such as industrial production planning, network communication routing, and logistic scheduling can be modeled as large-scale integer linear programming problems. However, due to the NP-Hardness of these problems, it is very challenging to optimally solve these problems in a short time on classical computers. Quantum computers have emerged as a new computing platform to provide new computing paradigms to tackle these problems. However, the scalability and efficiency of current quantum computers pose significant challenges in practical implementations of quantum optimization algorithms. In this paper, we propose a novel hybrid quantum-classical approach, termed Hybrid quantum-classical Dantzig-Wolfe Decomposition (HyDWD), aimed at solving these problems. In this framework, the subproblems can be solved in parallel on quantum computers. Our results demonstrate the benefits of integrating parallel quantum computing with the proposed hybrid quantum-classical framework via Dantzig-Wolfe decomposition, paving the way for advancements in optimization and decision-making processes.

Free weight training (FWT) is of utmost importance for physical well-being. However, the success of FWT depends on choosing the suitable workload, as improper selections can lead to suboptimal outcomes or injury. Current workload estimation approaches rely on manual recording and specialized equipment with limited feedback. Therefore, we introduce PPGSpotter, a novel PPG-based system for FWT monitoring in a convenient, low-cost, and fine-grained manner. By characterizing the arterial geometry compressions caused by the deformation of distinct muscle groups during various exercises and workloads in PPG signals, PPGSpotter can infer essential FWT factors such as workload, repetitions, and exercise type. To remove pulse-related interference that heavily contaminates PPG signals, we develop an arterial interference elimination approach based on adaptive filtering, effectively extracting the pure motion-derived signal (MDS). Furthermore, we explore 2D representations within the phase space of MDS to extract spatiotemporal information, enabling PPGSpotter to address the challenge of resisting sensor shifts. Finally, we leverage a multi-task CNN-based model with workload adjustment guidance to achieve personalized FWT monitoring. Extensive experiments with 15 participants confirm that PPGSpotter can achieve workload estimation (0.59 kg RMSE), repetitions estimation (0.96 reps RMSE), and exercise type recognition (91.57% F1-score) while providing valid workload adjustment recommendations.

Continuous blood pressure (BP) monitoring using wearable devices has received increasing attention due to its importance in diagnosing diseases. However, existing methods mainly measure BP intermittently, involve some form of user effort, and suffer from insufficient accuracy due to sensor properties. In order to overcome these limitations, we study the BP measurement technology based on heart sounds, and find that the time interval between the first and second heart sounds (TIFS) of bone-conducted heart sounds collected in the binaural canal is closely related to BP. Motivated by this, we propose HearBP, a novel BP monitoring system that utilizes inear microphones to collect bone-conducted heart sounds in the binaural canal. We first design a noise removing method based on U-net autoencoder-decoder to separate clean heart sounds from background noises. Then, we design a feature extraction method based on shannon energy and energy-entropy ratio to further mine the time domain and frequency domain features of heart sounds. In addition, combined with the principal component analysis algorithm, we achieve feature dimension reduction to extract the main features related to BP. Finally, we propose a network model based on dendritic neural regression to construct a mapping between the extracted features and BP. Extensive experiments with 41 participants show the average estimation error of 0.97mmHg and 1.61mmHg and the standard deviation error of 3.13mmHg and 3.56mmHg for diastolic pressure and systolic pressure, respectively. These errors are within the acceptable range specified by the FDA’s AAMI protocol.

Topology is one of the most critical properties of networks. Quantum networks, as a new type of network, have fundamentally different principles for establishing connections compared to classical networks, leading to distinct challenges in topology design. Finding the optimal topology for quantum networks to meet traffic demands is a crucial yet not fully understood problem. In this paper, we explore the topology design problem for quantum networks, considering both resource allocation and entanglement distribution. We propose and investigate both flow-based and path-based formulations, along with their associated solutions, aimed at minimizing the topology cost. For the path-based formulation, we also provide the first theoretical analysis of the cost associated with swapping strategies over a quantum path. Extensive simulations demonstrate that our enhanced path-based formulation is both efficient and effective.

In a blockchain-based federated learning (FL) framework, clients can contribute private data or computing resources to the overall FL training or mining task. To overcome the impractical assumption that participants will voluntarily join training or mining, it is crucial to design an incentive mechanism that motivates participants to achieve optimal training and mining outcomes. In this paper, we investigate the incentive mechanism design for a semi-asynchronous blockchain-based FL system. We model the resource pricing mechanism among clients and task publishers as a Stackelberg game, and prove the existence and uniqueness of a Nash equilibrium in such a game. We then propose an iterative algorithm based on the Alternating Direction Method of Multipliers (ADMM) to achieve the optimal strategies for each participant. Finally, our simulation results verify the convergence and efficiency of our proposed scheme.

Distributed learning-based high-dimensional temporal modeling for the Industrial Internet of Things (IIoT) has become a prevailing trend. However, traditional distributed learning inefficiently extracts information by straightforward architects, resulting in low modeling accuracy and high communication costs. We propose a distributed hierarchical temporal graph learning (DHTGL) approach. In terminal equipment, we construct an adaptive hierarchical dilation convolutional network to dynamically capture spatiotemporal features by adjusting the dilation factor at each layer. Next, we construct adaptive graphs according to the connection similarity between dimensions to capture implicit connections. In the edge device, we design a node-edge graph distance calculation based on Gromov-Wasserstein distance to group feature graphs and construct representative cluster feature graphs. Edge devices upload cluster feature graphs to reduce communication costs while minimizing information loss. In the central server, we incorporate graph attention networks into graph neural networks for edge updating in training models on clustered feature graphs. Experiments using public IIoT datasets and the self-built IIoT platform demonstrate the effectiveness of DHTGL in comparison with common distributed learning approaches. The results confirm that DHTGL consumes fewer communications while achieving higher accuracies.

In this paper, we reference the previous conference version and complete the grant number mentioned in the acknowledgments of the conference version.

Hierarchical federated learning has emerged as a pragmatic approach to addressing scalability, robustness, and privacy concerns within distributed machine learning, particularly in the context of edge computing. This hierarchical method involves grouping clients at the edge, where the constitution of client groups significantly impacts overall learning performance, influenced by both the benefits obtained and costs incurred during group operations (such as group formation and group training). This is especially true for edge and mobile devices, which are more sensitive to computation and communication overheads. The formation of groups is critical for group-based hierarchical federated learning but often neglected by researchers, especially in the realm of edge systems. In this paper, we present a comprehensive exploration of a group-based federated edge learning framework utilizing the hierarchical cloud-edge-client architecture and employing probabilistic group sampling. Our theoretical analysis of its convergence rate, considering the characteristics of client groups, reveals the pivotal role played by group heterogeneity in achieving convergence. Building on this insight, we introduce new methods for group formation and group sampling, aiming to mitigate data heterogeneity within groups and enhance the convergence and overall performance of federated learning. Our proposed methods are validated through extensive experiments, demonstrating their superiority over current algorithms in terms of prediction accuracy and training cost.

With the rapid development of mobile devices and the fast increase of sensitive data, secure and convenient mobile authentication technologies are desired. Except for traditional passwords, many mobile devices have biometric-based authentication methods (e.g., fingerprint, voiceprint, and face recognition), but they are vulnerable to spoofing attacks. To solve this problem, we study new biometric features which are based on the dental occlusion and find that the bone-conducted sound of dental occlusion collected in binaural canals contains unique features of individual bones and teeth. Motivated by this, we propose a novel authentication system, TeethPass$^+$, which uses earbuds to collect occlusal sounds in binaural canals to achieve authentication. Firstly, we design an event detection method based on spectrum variance to detect bone-conducted sounds. Then, we analyze the time-frequency domain of the sounds to filter out motion noises and extract unique features of users from four aspects: teeth structure, bone structure, occlusal location, and occlusal sound. Finally, we train a Triplet network to construct the user template, which is used to complete authentication. Through extensive experiments including 53 volunteers, the performance of TeethPass$^+$in different environments is verified. TeethPass$^+$achieves an accuracy of 98.6% and resists 99.7% of spoofing attacks.

Past tongue-jaw movement interaction systems typically require dedicated hardware and are uncomfortable to use, limiting their scalability and generalizability. This paper introducesCanalScan, the first system that recognizes tongue-jaw movements using commodity speakers and microphones mounted on ubiquitous off-the-shelf devices (e.g., smartphones). What inspires us is that tongue-jaw movements always cause ear canal deformations, and we find that for different tongue-jaw movements, dynamic features of ear canal deformations present unique patterns on acoustic reflections in the ear canal. Specifically,CanalScanfirst sends an acoustic signal to the ear canal, then parses the reflection signals for tongue-jaw movements recognition. To eliminate the impacts of body movements, we develop a body movement noise filtering method and a dynamic segmentation method to identify and separate the tongue-jaw movements-associated ear canal deformations from other types of body movements. We further propose a sensor position detection method and a data transformation mechanism to reduce the impacts of diversities in-ear canal shapes and relative positions between sensors and the ear canal.CanalScanexplores twelve unique and consistent features and applies a random forest classifier to distinguish tongue-jaw movements. Extensive experiments with twenty participants validate the generalizability, effectiveness, robustness, and high accuracy ofCanalScan.

Recent literature advances motion sensors mounted on smartphones and AR/VR headsets to speech eavesdropping due to their sensitivity to subtle vibrations. The popularity of motion sensors in earphones has fueled a rise in their sampling rate, which enables various enhanced features. This paper investigates a new threat of eavesdropping via motion sensors of earphones by developing EarSpy, which builds on our observation that the earphone's accelerometer can capture bone conduction vibrations (BCVs) and ear canal dynamic motions (ECDMs) associated with speaking; they enable EarSpy to derive unique information about the wearer's speech. Leveraging a study on the motion sensor measurements captured from earphones, EarSpy gains abilities to disentangle the wearer's live speech from interference caused by body motions and vibrations generated when the earphone's speaker plays audio. To enable user-independent attacks, EarSpy involves novel efforts, including a trajectory instability reduction method to calibrate the waveform of ECDMs and a data augmentation method to enrich the diversity of BCVs. Moreover, EarSpy explores effective representations from BCVs and ECDMs, and develops a neural network model with character-level and word-level speech recognition models to realize speech recognition. Extensive experiments involving 14 participants demonstrate that EarSpy reaches a promising recognition for the wearer's speech.

Federated Learning (FL)has achieved state-of-the-art performance in training a global model in a decentralized and privacy-preserving manner. Many recent works have demonstrated that incentive mechanism is of paramount importance for the success of FL. Existing incentives to FL either neglect communication efficiency, or consider communication efficiency but design the incentive mechanisms using non-cooperative games under complete information assumption, or study incentive mechanism under incomplete information but only apply to the sequential interaction setting. We shed light on this problem from the cooperative perspective and propose an incentive mechanism for communication-efficient FL based on the Nash bargaining theory. Specially, we formulate our incentive mechanism as a one-to-manyconcurrent bargaininggame among the aggregator and clients, and systematically analyze the Nash bargaining solution (NBS, game equilibrium) to design the incentive mechanism. It should be noted that the existingsequential bargainingis not suitable for incentivizing FL due to high (exponential) time complexity, which deteriorates the straggler problem in FL. Our formulated bargaining game is challenging due to the NP-hardness. We propose a probabilistic greedy-based client selection algorithm and derive an analytical payment solution as an approximate NBS. We prove the convergence guarantee of our incentive mechanism for communication-efficient FL. Finally, we conduct experiments over real-world datasets to evaluate the performance of our incentive mechanism.

With the ever-increasing demand for improving communication and independence for visually impaired people, automatic Braille recognition has gained increasing attention in facilitating Braille learning and reading. However, current approaches mainly require high-cost hardware, involve inconvenient operation, and disturb the normal touch function. In this paper, we proposeBrailleReaderas a low-cost and effortless Braille character recognition system without disturbing normal Braille touching. It exploits the wrist motion of Braille reading captured by the motion sensor available in the ubiquitous wrist-worn device to infer the encoded character information. To address the noise caused by other body and hand movements, we propose a novel noise cancellation method using the wavelet packet decomposition and reconstruction technique to separate clean wrist movement induced by the Braille dot. Moreover, we further explore the unique wrist movement pattern in three aspects to extract a novel and effective feature set. Based on this,BrailleReaderleverages a spiking neural network-based model to robustly recognize Braille characters across different people and different surface materials. Extensive experiments with 48 participants demonstrate thatBrailleReadercan perform accurate and robust recognition of 26 Braille characters.

Nowadays, mobile smart devices are widely used in daily life. It is increasingly important to prevent malicious users from accessing private data, thus a secure and convenient authentication method is urgently needed. Compared with common one-off authentication (e.g., password, face recognition, and fingerprint), continuous authentication can provide constant privacy protection. However, most studies are based on behavioral features and vulnerable to spoofing attacks. To solve this problem, we study the unique influence of sliding fingers on active vibration signals, and further propose an authentication system, FingerSlid, which uses vibration motors and accelerometers in mobile devices to sense biometric features of sliding fingers to achieve behavior-independent continuous authentication. First, we design two kinds of active vibration signals and propose a novel signal generation mechanism to improve the anti-attack ability of FingerSlid. Then, we extract different biometric features from the received two kinds of signals, and eliminate the influence of behavioral features in biometric features using a carefully designed Triplet network. Last, user authentication is performed by using the generated behavior-independent biometric features. FingerSlid is evaluated through a large number of experiments under different scenarios, and it achieves an average accuracy of 95.4% and can resist 99.5% of attacks.

Off-screen handwriting recognitionenriches the handwriting interaction paradigm for mobile devices. However, the existing approaches are only applicable to the specific environment and equipment conditions. In this paper, we proposeAcouWrite, a general, scalable and real-time handwriting recognition system based on active acoustic sensing. In detail, AcouWrite relies onactive acoustic sensingusing only a pair of microphones and speakers on the smartphone to capture real-time handwriting input. Particularly, we extract theshort-time dCIR (st-dCIR)to monitor the changes in the acoustic transmission channel resulting from finger movement. Technically, we use aCNN-GRUclassifier to complete the recognition task in AcouWrite. Moreover, we use data augmentation and spelling error correction methods to improve AcouWrite's robustness. To improve the generalization of our AcouWrite for new characters, we incorporate the transfer learning module into our AcouWrite. In various real-world environments, experiments demonstrate that AcouWrite achieves a mean recognition accuracy of 97.62%, a word accuracy (WA) of 96.4% and a character error rate (CER) of 1.5% for 100 common words, and an average response time of 94 milliseconds.

Bowel sound (BS) is an important physiological signal of the human body, which is also an objective reflection of gastrointestinal motility. However, BS has characteristics of weak signal, strong noise, and randomicity, which bring great challenges to the daily detection of BS. In this paper, we propose BSMonitor, the first BS monitoring system with strong noise-resistant capability via earphones. BSMonitor uses one earphone attached to the abdomen to collect BS signals and the other earphone worn in the ear to collect external noises and internal noises. After eliminating the noises through the Kalman filter and band-pass filter, the signal containing BS is separated via the empirical mode decomposition. Then BSMonitor extracts MFCC features of BS signals and applies a carefully-designed LSTM network to perform highly-accurate BS detection. Finally, an alert mechanism calculates the frequency and duration of detected BS and compares with the normal values to alert users. Furthermore, to increase the amount and diversity of training data, we introduce a data augmentation method, which can further improve the accuracy and generalization of BSMonitor. Through extensive experiments with 18 volunteers, we find that BSMonitor not only achieves high accuracy of BS detection but also has strong generalization across different users and environments. Particularly, BSMonitor achieves accuracy up to 98.73% and 94.56% in thebenchmark experimentsand thecross experiments, respectively.

The advancement of satellite-based quantum networks shows promise in transforming global communication infrastructure by establishing a secure and reliable quantum Internet. These networks use optical signals from satellites to ground stations to distribute high-fidelity quantum entanglements over long distances, overcoming the limitations of traditional terrestrial systems. However, the complexity of satellite-based entanglement distribution and terrestrial quantum swapping in the integrated network requires joint optimization with satellite assignment, resource allocation, and path selection. To address this challenge, we introduce a hybrid quantum-classical algorithm to solve the optimization problem by leveraging the strengths of both quantum and classical computing. The original problem is decomposed into a master problem and several subproblems using Dantzig-Wolfe decomposition and linearization techniques. Through experiments, this study demonstrates the effectiveness and reliability of the proposed methods in optimizing large-scale networks and managing qubit usage compared to the classical optimization techniques. The findings provide valuable insights for designing and implementing satellite-based entanglement distribution in quantum networks, paving the way for a secure global quantum communication infrastructure.

Deploying federated learning (FL) in edge clouds poses challenges, especially when multiple models are concurrently trained in resource-constrained edge environments. Existing research on federated edge learning has predominantly focused on client selection for training a single FL model, typically with a fixed learning topology. Preliminary experiments indicate that FL models with adaptable topologies exhibit lower learning costs compared to those with fixed topologies. This paper delves into the intricacies of jointly selecting participants and learning topologies for multiple FL models simultaneously trained in the edge cloud. The problem is formulated as an integer non-linear programming problem, aiming to minimize total learning costs associated with all FL models while adhering to edge resource constraints. To tackle this challenging optimization problem, we introduce a two-stage algorithm that decouples the original problem into two sub-problems and iteratively addresses them separately with efficient heuristics. Our method enhances resource competition and load balancing in edge clouds by allowing FL models to choose participants and learning topologies independently. Extensive experiments conducted with real-world networks and FL datasets affirm the better performance of our algorithm, demonstrating lower average total costs with up to 33.5% and 39.6% compared to previous methods designed for multi-model FL.

The 360-degree video streaming service provides a unique immersive viewing experience for users, who can freely change their Field-of-View (FoV) to view different portions of the videos. However, the demands for high throughput and low latency for 360-degree video pose substantial challenges to the current network infrastructure. Super Resolution (SR) is the procedure for reconstructing high-resolution images from low-resolution ones. Hence, caching video content on the network edge in advance, which is near end users, and applying the SR technique can significantly alleviate the transmission latency. In this article, we describeNOVA, an efficientNeural-OptimizedViewportAdaptive 360-degree video streaming system to improve the Quality of Experience (QoE) of users. In NOVA, we first design a foveated rendering SR approach to super-resolve video tiles utilizing computational resources at the edge. Subsequently, we present a meta-learning-based Multi-Agent Reinforcement Learning (MARL) algorithm to select SR depths and video tiles inside users’ viewports for agile video tile adaptation to optimize overall QoE under frequent network fluctuations. Finally, we implement the holistic prototype of NOVA and evaluate its performance on various real-world network datasets. Extensive experiments illustrate that compared to the state-of-the-art algorithms, NOVA improves average user-perceived QoE by up to 27%.

With the emergence and fast development of cloud computing and outsourced services, more and more companies start to use managed security service providers (MSSP) as their security service team. This approach can save the budget on maintaining its own security teams and depend on professional security persons to protect the company infrastructures and intellectual property. However, this approach also gives the MSSP opportunities to honor only a part of the security service level agreement. To prevent this from happening, researchers propose to use outsourced network testing to verify the execution of the security policies. During this procedure, the end customer has to design network testing traffic and provide it to the testers. Since the testing traffic is designed based on the security rules and selectors, external testers could derive the customer network security setup, and conduct subsequent attacks based on the learned knowledge. To protect the network security configuration secrecy in outsourced testing, in this paper we propose different methods to hide the accurate information. For Regex-based security selectors, we propose to introduce fake testing traffic to confuse the testers. For exact match and range based selectors, we propose to use NAT VM to hide the accurate information. We conduct simulation to show the protection effectiveness under different scenarios. We also discuss the advantages of our approaches and the potential challenges.

The scheduling problem for federated learning (FL) with multiple models in a distributed network is challenging, as it involves NP-hard mixed-integer nonlinear programming. Moreover, it requires optimal participant selection and learning rate determination among multiple FL models to avoid high training costs and resource competition. To overcome those chal-lenges, in literature the Benders' decomposition algorithm (BD) can deal with mixed integer problems, however, it still suffers from limited scalability. To address this issue, in this paper, we present the Hybrid Quantum-Classical Benders' Decomposition (HQCBD) algorithm, which combines the power of quantum and classical computing to solve the joint participant selection and learning scheduling problem in multi-model FL. HQCBD decomposes the optimization problem into a master problem with binary variables and small subproblems with continuous variables. This collaboration maximizes the potential of both quantum and classical computing, and optimizes the complex joint optimization problem. Simulation on the commercial D-Wave quantum annealing machine demonstrates the effectiveness and robustness of the proposed method, with up to 18% improvement of iterations and 81% improvement of computation time over BD algorithm on classical CPUs even at small scales.

Hierarchical federated learning has been studied as a more practical approach to federated learning in terms of scalability, robustness, and privacy protection, particularly in edge computing. To achieve these advantages, operations are typically conducted in a grouped manner at the edge, which means that the formation of client groups can affect the learning performance, such as the benefits gained and costs incurred by group operations. This is especially true for edge and mobile devices, which are more sensitive to computation and communication overheads. The formation of groups is critical for group-based federated edge learning but has not been studied in detail, and even been overlooked by researchers. In this paper, we consider a group-based federated edge learning framework that leverages the hierarchical cloud-edge-client architecture and probabilistic group sampling. We first theoretically analyze the convergence rate with respect to the characteristics of the client groups, and find that group heterogeneity plays an important role in the convergence. Then, on the basis of this key observation, we propose new group formation and group sampling methods to reduce data heterogeneity within groups and to boost the convergence and performance of federated learning. Finally, our extensive experiments show that our methods outperform current algorithms in terms of prediction accuracy and training cost.

Recent literature advances motion sensors mounted on smartphones and AR/VR headsets to speech eavesdropping due to their sensitivity to subtle vibrations. The popularity of motion sensors in earphones has fueled a rise in their sampling rate, which enables various enhanced features. This paper investigates a new threat of eavesdropping via motion sensors of earphones by developing EarSpy, which builds on our observation that the earphone’s accelerometer can capture bone conduction vibrations (BCVs) and ear canal dynamic motions (ECDMs) associated with speaking; they enable EarSpy to derive unique information about the wearer’s speech. Leveraging a study on the motion sensor measurements captured from earphones, EarSpy gains abilities to disentangle the wearer’s live speech from interference caused by body motions and vibrations generated when the earphone’s speaker plays audio. To enable user-independent attacks, EarSpy involves novel efforts, including a trajectory instability reduction method to calibrate the waveform of ECDMs and a data augmentation method to enrich the diversity of BCVs. Moreover, EarSpy explores effective representations from BCVs and ECDMs, and develops a convolutional neural model with Connectionist Temporal Classification (CTC) to realize accurate speech recognition. Extensive experiments involving 14 participants demonstrate that EarSpy reaches a promising recognition for the wearer’s speech.

With the development of society and the gradual increase of life pressure, the number of people engaged in mental work and working hours have increased significantly, resulting in more and more people in a state of fatigue. It not only reduces people’s work efficiency, but also causes health and safety related problems. The existing fatigue detection systems either have different shortcomings in diverse scenarios or are limited by proprietary equipment, which is difficult to be applied in real life. Motivated by this, we propose a multi-information fatigue detection system named WakeUp based on commercial smart speakers, which is the first to fuse physiological and behavioral information for fine-grained fatigue detection in a non-contact manner. We carefully design a method to simultaneously extract users’ physiological and behavioral information based on the MobileViT network and VMD decomposition algorithm respectively. Then, we design a multi-information fusion method based on the statistical features of these two kinds of information. In addition, we adopt an SVM classifier to achieve fine-grained fatigue level. Extensive experiments with 20 volunteers show that WakeUp can detect fatigue with an accuracy of 97.28%. Meanwhile, WakeUp can maintain stability and robustness under different experimental settings.

Internet of Underwater Things (IoUT) needs to maintain effective communication even under the circumstances of severe environments and limited energy. Named data networking (NDN), a future network architecture, is starting to be used for IoUT as an effective architecture implementation. Despite having a good performance of data transmission, Underwater named data networking (UNDN) nevertheless faces some security risks, such as Denial-of-Service (DoS) brought by interest flooding attacks (IFAs). This article proposes a novel DoS attack, Synergetic DoS (SDoS), which can cause hiding damages to router’s content store (CS), pending interest table (PIT), and forwarding information base (FIB). We not only study the basic synergetic attack model of SDoS but also analyze some possible attack variants. Simulation results illustrate that SDoS entirely invalidates the only IFA detection algorithm in UNDN. Compared to ordinary IFAs, SDoS attacks increase network traffic fourfold. Furthermore, we discover a unique infection problem in UNDN and propose a countermeasure named Trident, which has meticulously designed adaptive threshold,Double Trialfor attacker identification, and a self-proving mechanism based on leaky bucket. Experiment results demonstrate that Trident can detect and resist not only IFAs but also SDoS attacks effectively. Meanwhile, Trident also achieves good defense performance on the variants of SDoS and can take on burst traffic and network congestion robustly.

Internet of Things (IoT) gateways integrate various sensors and compute initial decisions before transmitting data to the cloud for further processing. As the functions they need to support become increasingly complex, gateways must upgrade their hardware. Network functions (NF) and video analytics (VAs) are two typical examples of hardware requirements: NFs need specialized hardware accelerators, while VAs need parallel processing power. However, gateways are typically constrained by factors, such as power, size, and cost, leading to a need to multiplex functions and minimize hardware overprovisioning. This article proposes a novel accelerator, the transmission-analytic processing unit (TAPU), which uses multi-image FPGA to accelerate VAs and NFs for IoT gateways. We preconfigure one image for VAs and one image for NFs, then multiplex the FPGA resources in the time dimension. The TAPU system design requires both hardware and software revisions. In the hardware design, we discuss our considerations on hardware choice and present a new abstraction of hardware functions to overcome the challenge of application development on different multi-image FPGAs. For the software, we develop a fully functional TAPU system to adapt to dynamic network and VAs workloads. Our evaluation shows that TAPU utilization can reach 92%, considerably increasing VAs and network processing throughput over the current approach. We further evaluate TAPU through two case studies that support a campus traffic monitoring system and an office surveillance system, demonstrating excellent performance improvement and low overhead.

Sign language is expressed by movements of the hands and facial expressions, which is mainly used by the deaf community. Although some gesture recognition methods are put forward, they possess different defects and are not applicable to deal with the sign language recognition (SLR) problem. In this article, we propose an end-to-end American SLR system with built-in speakers and microphones in smartphones, which enables SLR at both word level and sentence level. The high-level idea is to use the inaudible acoustic signal to estimate channel information and capture the sign language in real time. We use channel impulse response to represent each sign language gesture, which can realize finger-level recognition. We also pay attention to conversion movements between two words and treat them as an additional label when training the sentence-level classification model. We implement a prototype system and run a series of experiments that demonstrate the promising performance of our system. Experimental results show that our approach can achieve an accuracy of 97.2% at word-level recognition and word error rate of 0.9% at sentence-level recognition, respectively.

Deep learning (DL) technologies bring new threats to network security. Website fingerprinting attacks (WFA) using DL models can distinguish victim’s browsing activities protected by anonymity technologies. Unfortunately, traditional countermeasures (website fingerprinting defenses, WFD) fail to preserve privacy against DL models. In this paper, we apply adversarial example technology to implement new WFD with static analyzing (SA) and dynamic perturbation (DP) settings. Although DP setting is close to a real-world scenario, its supervisions are almost unavailable due to the uncertainty of upcoming traffics and the difficulty of dependency analysis over time. SA setting relaxes the real-time constraints in order to implement WFD under a supervised learning perspective. We propose Greedy Injection Attack (GIA), a novel adversarial method for WFD under SA setting based on zero-injection vulnerability test. Furthermore, Sniper is proposed to mitigate the computational cost by using a DL model to approximate zero-injection test. FCNSniper and RNNSniper are designed for SA and DP settings respectively. Experiments show that FCNSniper decreases classification accuracy of the state-of-the-art WFA model by 96.57% with only 2.29% bandwidth overhead. The learned knowledge can be efficiently transferred into RNNSniper. As an indirect adversarial example attack approach, FCNSniper can be well generalized to different target WFA models and datasets without suffering fatal failures from adversarial training.

Apache Spark as a popular in-memory data analytic framework has been employed by various applications—such as machine learning, graph computation, and scientific computing, which benefit from the long-running process (e.g., executor) programming model to avoid system I/O overhead. However, existing resource allocation strategies mainly rely on the peak demand, which are normally specified by users. Since the resource usages of long-running applications like iterative computation vary significantly over time, we find that peak demand based resource allocation policies lead to low cloud utilization in production environments. In this article, we present a utilization aware resource provisioning approach for iterative workloads on Apache Spark (i.e.,${iSpark}$). It can identify the causes of resource underutilization due to an inflexible resource policy, and elastically adjusts the allocated executors over time according to the real-time resource usage. In general, iterative applications require more computation resources at the beginning stage and their demands for resources diminish as more iterations are completed. iSpark aims to timely scale up or scale down the number of executors in order to fully utilize the allocated resources while taking the dominant factor into consideration. It further preempts the underutilized executors and preserves the cached intermediate data to ensure the data consistency. Testbed evaluations show that iSpark averagely improves the resource utilization of individual executors by 35.2% compared to vanilla Spark. At the same time, it increases the cluster utilization from 32.1% to 51.3% and effectively reduces the overall job completion time by 20.8% for a set of representative iterative applications. Furthermore, we have extended iSpark to multi-tenancy cloud environments. Specifically, iSpark characterizes a virtual node based on two real-time measured performance statistics: I/O rate and CPU steal time. Thus, we extend the two-dimensional resource constraints (i.e., CPU and MeM) in iSpark to three-dimensional resource constraints (i.e., CPU, MeM and I/O) in the cloud environment. We consider two representative interference scenarios in the cloud: stable interference and dynamic interference. Experimental results on virtual clusters with varying interferences show that iSpark with cloud extension improves the average job completion time by 68% compared to default Spark resource allocation policies.

Recent advances in deep neural networks have substantially improved the accuracy and speed of various intelligent applications. Nevertheless, one obstacle is that DNN inference imposes a heavy computation burden on end devices, but offloading inference tasks to the cloud causes a large volume of data transmission. Motivated by the fact that the data size of some intermediate DNN layers is significantly smaller than that of raw input data, we designed the DNN surgery, which allows partitioned DNN to be processed at both the edge and cloud while limiting the data transmission. The challenge is twofold: (1) Network dynamics substantially influence the performance of DNN partition, and (2) State-of-the-art DNNs are characterized by a directed acyclic graph rather than a chain, so that partition is incredibly complicated. To solve the issues, We design a Dynamic Adaptive DNN Surgery(DADS) scheme, which optimally partitions the DNN under different network conditions. We also study the partition problem under the cost-constrained system, where the resource of the cloud for inference is limited. Then, a real-world prototype based on the selif-driving car video dataset is implemented, showing that compared with current approaches, DNN surgery can improve latency up to 6.45 times and improve throughput up to 8.31 times. We further evaluate DNN surgery through two case studies where we use DNN surgery to support an indoor intrusion detection application and a campus traffic monitor application, and DNN surgery shows consistently high throughput and low latency.

The proliferation of Internet of Things (IoT) data and innovative mobile services has promoted an increasing need for low-latency access to resources such as data and computing services. Mobile edge computing has become an effective computing paradigm to meet the requirement for low-latency access by placing resources and dispatching tasks at the edge clouds near mobile users. The key challenge of such solution is how to efficiently place resources and dispatch tasks in the edge clouds to meet the QoS of mobile users or maximize the platform’s utility. In this article, we study the joint optimization problem of resource placement and task dispatching in mobile edge clouds across multiple timescales under the dynamic status of edge servers. We first propose a two-stage iterative algorithm to solve the joint optimization problem in different timescales, which can handle the varieties among the dynamic of edge resources and/or tasks. We then propose a reinforcement learning (RL) based algorithm which leverages the learning capability of Deep Deterministic Policy Gradient (DDPG) technique to tackle the network variation and dynamic as well. The results from our trace-driven simulations demonstrate that both proposed approaches can effectively place resources and dispatching tasks across two timescales to maximize the total utility of all scheduled tasks.

In recent years, edge computing has become an increasingly popular computing paradigm to enable real-time data processing and mobile intelligence. Edge computing allows computing at the edge of the network, where data is generated and distributed at the nearby edge servers to reduce the data access latency and improve data processing efficiency. One of the key challenges in data-intensive edge computing is how to place the data at the edge clouds effectively such that the access latency to the data is minimized. In this paper, we study such a data placement problem in edge computing while different data items have diverse popularity. We propose a popularity based placement method which maps both data items and edge servers to a virtual plane and places or retrieves data based on its virtual coordinate in the plane. We then further propose additional placement strategies to handle load balancing among edge servers via either offloading or data duplication. Simulation results show that our proposed strategies efficiently reduce the average path length of data access and the load-balancing strategies indeed provide an effective relief of storage pressures at certain overloaded servers.

Proper handwashing, having a crucial effect on reducing bacteria, serves as the cornerstone of hand hygiene. For elders with dementia, they suffer from a gradual loss of memory and difficulty coordinating handwashing steps. Proper assistance should be provided to them to ensure their hand hygiene adherence. Toward this end, we propose AWash, leveraging inertial measurement unit (IMU) readily available in most wrist-worn devices (e.g., smartwatches) to characterize handwashing actions and provide assistance. To monitor handwashing scenarios round-the-clock while achieving energy efficiency, we design methods that distinguish handwashing from other daily activities and dynamically adjust the sampling duty cycle. Upon detecting handwashing actions, we design several novel techniques to segment different handwashing actions and extract sensor-body inclination angles that handle particular interference of senile dementia patients. Moreover, a user-independent network model is built to recognize the handwashing actions of senile dementia patients without requiring their training data. Furthermore, we propose a transfer learning method that improves system performance. To meet users’ diverse needs, we use a state machine to make prompt decisions, supporting customized assistance. Extensive experiments on a prototype with eight older participants demonstrate that AWash can increase the user’s independence in the execution of handwashing.

Mobile devices are promising to apply two-factor authentication to improve system security. Existing solutions have certain limits of requiring extra user effort, which might seriously affect user experience and delay authentication time. In this paper, we propose PPGPass, a novel mobile two-factor authentication system, which leverages Photoplethysmography (PPG) sensors available in most wrist-worn wearables. PPGPass simultaneously performs a password/pattern/signature authentication and a physiological-based authentication. To realize both nonintrusive and secure, we design a two-stage algorithm to separate clean heartbeat signals from PPG signals contaminated by motion artifacts so that users do not have to deliberately keep their bodies still. In addition, to deal with noncancelable issues when biometrics are compromised, we design a repeatable and non-invertible method to generate cancelable feature templates as alternative credentials. We leverage the great power ofRandom ForestandSupport Vector Data Descriptionto detect adversaries and verify a user's identity. To the best of our knowledge, PPGPass is the first nonintrusive and secure mobile two-factor authentication based on PPG sensors. Extensive experiments demonstrate that PPGPass can achieve the false acceptance rate of 3.11% and the false recognition rate of 3.71%, which confirms its high effectiveness, security, and usability.

Federated learning (FL) has reshaped the learning paradigm by overcoming privacy concerns and siloed data. In FL, an aggregator schedules a set of mobile users (MUs) to collectively train a global model with their local datasets and subsequently aggregates their model updates. However, the users have many uncertainties like unstable network connections and volatile availability, which leads to the straggler problem and deteriorates the efficiency of the FL system. Besides, the issue of non-IID datasets hinders the convergence performance of the global model. To hurdle the user uncertainties, we associate a deadline with the decision in each round and partially collect MUs' updates after the deadline, which can be achieved by considering surplus budget constraints. Moreover, we introduce fairness constraints for the non-IID issue. We propose a deadline-aware task replication for surplus client scheduling policy, called FEDDATE-CS. FEDDATE-CS is developed based on a novel contextual-combinatorial multi-armed bandit (CCMAB) learning framework with fairness guarantee. We extend the hypercube-based CCMAB framework by integrating the Lyapunov queuing technique and rigorously prove that FEDDATE-CS achieves a sublinear regret bound and provides an$[\mathcal{O}(1/V),\mathcal{O}(V)]$regret-fairness tradeoff for any fairness control factor$V>0$. We conduct extensive evaluations to verify the significant superiority of FEDDATE-CS over benchmarks.

Fitness can help to strengthen muscles, increase resistance to diseases, and improve body shape. Nowadays, a great number of people choose to exercise at home/office rather than at the gym due to lack of time. However, it is difficult for them to get good fitness effects without professional guidance. Motivated by this, we propose the first personalized fitness monitoring system, HearFit$^+$, using smart speakers at home/office. We explore the feasibility of using acoustic sensing to monitor fitness. We design a fitness detection method based on Doppler shift and adopt the short time energy to segment fitness actions. Based on deep learning, HearFit$^+$can perform fitness classification and user identification at the same time. Combined with incremental learning, users can easily add new actions. We design 4 evaluation metrics (i.e., duration, intensity, continuity, and smoothness) to help users to improve fitness effects. Through extensive experiments including over 9,000 actions of 10 types of fitness from 12 volunteers, HearFit$^+$can achieve an average accuracy of 96.13% on fitness classification and 91% accuracy for user identification. All volunteers confirm that HearFit$^+$can help improve the fitness effect in various environments.

Network Function Virtualization (NFV) provides the possibility to implement complex network functions from dedicated hardware to software instances called Virtual Network Functions (VNF) by leveraging the virtualization technology. Service Function Chaining (SFC) is therefore defined as a chain-ordered set of placed VNFs that handles the traffic of the delivery and control of a specific application. Due to the advantages of flexibility, efficiency, scalability, and short deployment cycles, NFV has been widely recognized as the next-generation network service provisioning paradigm. In this paper, we study the problem of online SFC control across geo-distributed datacenters, which is to dynamically place required VNFs on datacenter nodes and find routing paths between each adjacent VNF pair for each NFV service flow that varies over time. To that end, we first formulate this problem as an offline optimization problem whose goal is to minimize the average delay such that each datacenter's average cost does not exceed a given expense value. Considering that the offline optimization requires complete offline network information which is difficult to obtain or predict in practice, we present an online SFC control framework without requiring any future information about the traffic demands. More specifically, we leverage the Lyapunov optimization technique to formulate the problem as a series of one-time slot offline optimization problems and then apply a primal-decomposition method to solve each one-time slot problem. Simulation results reveal that our proposed online SFC control framework can efficiently reduce long-term average delay while keeping datacenter's long-term average cost consumption low.

Driver drowsiness is a significant factor in road crashes. However, existing solutions for driver drowsiness detection have major drawbacks of requiring special hardware, constrained recording conditions, and cannot handle the asynchronous and contradictory nature of multiple indicators. In view of this, we propose FDWatch, a novel drowsiness detection system that exploits the low-cost Photoplethysmogram (PPG) sensor and motion sensor integrated into wrist-worn devices. We design a set of novel algorithms to extract multiple drowsiness-related indicators covering major categories of human factors. In particular, we demonstrate that commodity PPG sensors can be utilized to detect yawning behavior; it contributes as an important indicator for drowsiness detection. The core of FDWatch is based on the Dempster-Shafer evidence theory. It considers different indicators as evidence describing the state of the driver from different angles. To make the extracted indicators applicable to Dempster-Shafer evidence theory, we employ backpropagation neural networks to obtain the basic probability assignment. Moreover, we propose a similarity-distance-based method to handle evidence conflicts. Extensive experiments with real-road driving data show that FDWatch can accurately detect driver drowsiness with a missing alarm rate of 3.57% and a false alarm rate of 3.68%.

Sound-related respiratory symptoms are commonly observed in our daily lives. They are closely related to illnesses, infections, or allergies but ignored by the majority. Existing detection methods either depend on specific devices, which are inconvenient to wear, or are sensitive to noises and only work for indoor environment. Considering the lack of monitoring method for in-car environment, where there is high risk of spreading infectious diseases, we propose a smartphone-based system, named SymListener, to detect respiratory symptoms in driving environment. By continuously recording acoustic data through a built-in microphone, SymListener can detect the sounds of cough, sneeze, and sniffle. We design a modified ABSE-based method to remove the strong and changeable driving noises while saving energy of the smartphone. An LSTM network is adopted to classify the three types of symptoms according to the carefully designed acoustic features. We implement SymListener on different Android devices and evaluate its performance in real driving environment. The evaluation results show that SymListener can reliably detect target respiratory symptoms with an average accuracy of 92.19% and an average precision of 90.91%.

The efficacy of Network Function Virtualization (NFV) depends critically on (1) where the virtual network functions (VNFs) are placed and (2) how the traffic is routed. Unfortunately, these aspects are not easily optimized, especially under time-varying network states with different QoS requirements. Given the importance of NFV, many approaches have been proposed to solve the VNF placement and Service Function Chaining (SFC) routing problem. However, those prior approaches mainly assume that the network state is static and known, disregarding dynamic network variations. To bridge that gap, we leverage Markov Decision Process (MDP) to model the dynamic network state transitions. To jointly minimize the delay and cost of NFV providers and maximize the revenue, we first devise a customized Deep Reinforcement Learning (DRL) algorithm for the VNF placement problem. The algorithm uses the attention mechanism to ascertain smooth network behavior within the general framework of network utility maximization (NUM). We then propose attention mechanism-based DRL algorithm for the SFC routing problem, which is to find the path to deliver traffic for the VNFs placed on different nodes. The simulation results show that our proposed algorithms outperform the state-of-the-art algorithms in terms of network utility, delay, cost, and acceptance ratio.

Handwritten signature authentication is an important service to defend against fraudulent activities. Current automated solutions rely heavily on dedicated devices and require certain user efforts. In this work, we explore the feasibility of a new type of signature authentication system, SAP - Signature Authentication with PPG Sensor, which leverages Photoplethysmography (PPG) sensors in wrist-worn wearable devices. To make SAP non-intrusive and secure, we design effective algorithms to separate the signature signals from the heartbeat signals in the raw PPG signals. We implement a low-cost hardware prototype of SAP. Our preliminary experimental results show that SAP can achieve an average F1 score of up to 98%.

With the development of Security as a Service (SAAS), many companies outsource their network security functionality to security service providers. To guarantee the execution and quality of such services, a third party can help the end customer verify the enforcement of the security service level agreement (SSLA). Since individual testers often lack the capability and trustworthiness to attract many customers, a platform is needed to bridge the gap between the customers and the testers. In this paper, we investigate the incentivisation of outsourced network testing from the platform perspective. We first define the problem of cost/benefit model of the platform and identify the restriction factors. We describe multiple testing task assignment scenarios and prove that they are NP problems. Next we design heuristic algorithms for the problem. Our simulation results examine the performance of the heuristic approaches.

With the rapid development of mobile devices and the fast increase of sensitive data, secure and convenient mobile authentication technologies are desired. Except for traditional passwords, many mobile devices have biometric-based authentication methods (e.g., fingerprint, voiceprint, and face recognition), but they are vulnerable to spoofing attacks. To solve this problem, we study new biometric features which are based on the dental occlusion and find that the bone-conducted sound of dental occlusion collected in binaural canals contains unique features of individual bones and teeth. Motivated by this, we propose a novel authentication system, TeethPass, which uses earbuds to collect occlusal sounds in binaural canals to achieve authentication. We design an event detection method based on spectrum variance and double thresholds to detect bone-conducted sounds. Then, we analyze the time-frequency domain of the sounds to filter out motion noises and extract unique features of users from three aspects: bone structure, occlusal location, and occlusal sound. Finally, we design an incremental learning-based Siamese network to construct the classifier. Through extensive experiments including 22 participants, the performance of TeethPass in different environments is verified. TeethPass achieves an accuracy of 96.8% and resists nearly 99% of spoofing attacks.

Physical activity (PA) plays a crucial role in leading a healthy life without chronic diseases. Among various PAs, weight lifting, one of the essential stationary exercises, is an integral part of routine workout sessions. Being aware of the intensity of the performed exercise is also an essential factor in keeping track of the workout. Inspired by this, we propose a low-cost quantitative weight lifting assessment system, PaWLA, leveraging only a single Photoplethysmography (PPG) sensor. Particularly, we design PaWLA as a mobile weight recognition system that can classify the user’s lifted weight into its corresponding label based on PPG sensor readings from the wrist region. The changes in blood volume in the radial artery due to the strain of lifting the weight are exploited via PPG sensor readings in this work. We build our custom hardware prototype using COTS components to prove the system’s feasibility. Evaluation of the system with nine volunteers shows that PaWLA can achieve an average F1 score of up to 97.4%, proving the feasibility and efficiency of the proposed method.

Federated learning (FL) has been emerging as a new distributed machine learning paradigm recently. Although FL can protect the data privacy of participants by keeping their training data on local devices, there are recent works raising new privacy concerns especially when workers or the parameter server of FL are untrustworthy or malicious. One effective way to solve the problem is using hierarchical federated learning (HFL) where a few middle-layer aggregators (or called group leaders) are used to aggregate local model updates from workers and send group model updates to the parameter server. In this paper, we consider the participant selection problem of HFL in an edge cloud with multiple FL models, where each model needs to select one parameter server, a few group leaders and a certain amount of workers from edge servers to jointly perform HFL. We first formulate this problem as a non-linear integer programming, aiming to minimize the total learning cost of all models while satisfying the constrained edge resources. We then design a three-stage algorithm by decoupling the original problem into three sub-problems and solving them iteratively. Simulations with real-world datasets and FL models confirm that our proposed algorithm can efficiently reduce the average total learning cost in edge cloud compared with existing methods.

Handwritten signature authentication is a crucial service to defend against fraudulent activities. Existing automated solutions rely heavily on dedicated devices that are expensive and require different user efforts that affect the user experience. In this paper, we propose a new signature authentication system, PPGSign, which leverages Photoplethysmography (PPG) sensors in the existing wrist-worn wearable devices. The unique blood flow changes in the supplicant’s hand movement are exploited in this system to validate the signature. To make PPGSign nonintrusive and secure, we explore effective algorithms to separate the signature signals from the heartbeat signals in the raw PPG signals. We build a low-cost hardware prototype to verify our proposed method. Our experimental results show that PPGSign can achieve an average F1 score of up to 98%, which verifies the feasibility and efficiency of the proposed solution.

Mobile crowdsensing (MCS) enables a platform to recruit users to collectively perform sensing tasks from requesters. In order to maximize the completion qualities of tasks, an incentive mechanism should be well designed for the platform to incentivize high-quality users’ participation. The existing works largely adopt the Stackelberg game to model the strategic interactions in the incentive mechanism. However, there are practical issues that are less investigated in the context of the Stackelberg-based incentive mechanism. First, the platform has no knowledge about users’ sensing qualities beforehand due to their private information. Second, the platform needs users’ continuous participation in the long run, which results in fairness requirements. Third, it is also crucial to protect users’ privacy due to the potential privacy leakage concerns (e.g., sensing qualities) after completing tasks. In this article, we jointly address these issues and propose the three-stage Stackelberg-based incentive mechanism for the platform to recruit participants. In detail, we leverage combinatorial volatile multiarmed bandits (CVMABs) to elicit unknown users’ sensing qualities. We use the drift-plus-penalty (DPP) technique in Lyapunov optimization to handle the fairness requirements. We blur the quality feedback with tunable Laplacian noise such that the incentive mechanism protects locally differential privacy (LDP). Finally, we carry out experiments to evaluate our incentive mechanism. The numerical results show that our incentive mechanism achievessublinearregret performance to learn unknown quality with fairness and privacy guarantee.

The current Internet of Underwater Things (IoUT) for marine observations and emergency responses suffers from two critical issues: 1) energy efficient and 2) timely data collection. Autonomous underwater vehicles (AUVs), serving as tools for collecting and forwarding distributed data, can deal with the unbalanced power consumption in a traditional multihop underwater communication network. However, the low speed of the AUV has not been able to guarantee the timeliness of delay-sensitive data. In this article, we introduce a hybrid data collection scheme (HDCS), taking both real-time data collection and energy efficiency (EE) issues into consideration. All sensor nodes (SNs) are first clustered based on their locations in the network. We develop an analytic expression to describe the attenuation of Value of Information (VoI), involving the relationship between the importance degree and timeliness; initial VoI could be measured by historical data. The emergency can be recognized by the presented criterion, and the transmission mode of cluster heads (CHs) in the same layer is judged by CHs themselves according to VoI. The selected CHs shall transmit the urgent data via multihop routing to avoid over attenuation of VoI. The normal data are collected by AUVs visiting all remaining CHs, and the shortest trajectory is achieved by addressing a variation of the classic traveling salesman problem (TSP). Our simulation experiments show that this mechanism can effectively increase long-term VoI while significantly improving EE.

The ever-growing security issues in various scenarios create an urgent demand for a reliable and convenient identification system. Traditional identification systems request users to provide passwords, fingerprints, or other easily stolen information. Existing works show that everyone’s gait and respiration have unique characteristics and are difficult to imitate. But these works only use gait or respiration information to achieve identification, which leads to low accuracy or long identification time. And they have no strong anti-interference ability, which leads to the limitation in practical application. Toward this end, we propose a new system which uses both gait and respiratory biometric characteristics to achieve user identification using Wi-Fi (GRi-Fi) in the presence of interferences. In our system, we design a segmentation algorithm to segment gait and respiration data. And we design a weighted subcarrier screening method to improve the anti-interference ability. In order to shorten the identification time, we propose a feature integration method based on the weighted average. Finally, we use a deep learning method to identify users accurately. Experimental results show that GRi-Fi can identify the users identity with an average accuracy of 98.3% in noninterference environments. Even in the presence of multiple interferences, the average identification accuracy also reaches 91.2%. In future applications, our system can be applied to many fields of Internet of Things, such as smart home systems and clocking in at companies.

As large-scale data analytic becomes norm in various industries, using MapReduce frameworks to analyze ever-increasing volumes of data will keep growing. In turn, this trend drives up the intention to move MapReduce into multi-tenant clouds. However, the application performance of MapReduce can be significantly affected by the time-varying network bandwidth in a shared cluster. Although many recent studies improve MapReduce performance by dynamic scheduling to reduce the shuffle traffic, most of them do not consider the impact by widely existing hierarchical network architectures in data centers. In this article, we propose and design a hierarchical topology (Hit) aware MapReduce scheduler to minimize overall data traffic cost and hence to reduce job execution time. We first formulate the problem as a Topology Aware Assignment (TAA) optimization problem while considering dynamic computing and communication resources in the cloud with hierarchical network architecture. We further develop a synergistic strategy to solve the TAA problem by using the stable matching theory, which ensures the preference of both individual tasks and hosting machines. Finally, we implement the proposed scheduler as a pluggable module on Hadoop YARN and evaluate its performance by testbed experiments and simulations. The testbed experimental results show that Hit-scheduler can improve job completion time by 28 and 11 percent compared to Capacity Scheduler and Probabilistic Network-Aware scheduler, respectively. Our simulations further demonstrate that Hit-scheduler can reduce the traffic cost by 38 percent at most and the average shuffle flow traffic time by 32 percent compared to capacity scheduler. In this article, we have extended Hit-scheduler to a decentralized heuristic scheme to perform the policy-aware allocation in data center environments. Many existing centralized approximation approaches are too complex and infeasible to implement over a data center, which typically include large amounts of servers, containers, switches, and traffic flows. In the extension, we have designed a decentralized heuristic scheme to perform the Policy-Aware Task (PAT) allocation by using existing centralize algorithm to approximately maximize the total gained utility. Finally, the simulation based experimental results show that the proposed PAT policy reduces the communication cost by 33.6 percent compared with the default scheduler in data centers.

Major cloud service providers with well-equipped infrastructure, experienced machine learning (ML) expertise, and enriched training datasets are building ML-as-a-Service (MLaaS) systems, in which clients can query ML-based prediction services with their data. Instead of moving private data to the cloud, in this work, we design, implement, and evaluate a novel secure ML system to enable MLaaS on edge devices. To protect the proprietary ML models on edge devices from revealing to the clients while maintaining a real-time inference is challenging. Existing privacy-preserving ML techniques can hardly satisfy real-time requirements. In our solution, we employ a secure enclave (e.g., SGX) to offer security and provide better efficiency than cryptographic techniques. However, the enclave alone cannot achieve real-time capability due to its limited capacity. We observe that the ML model imposes a severe accuracy degradation when adding noise to a few model weights. Based on this, we design a suite of novel solutions to optimize the performance of secure enclave-based inference service at the edge by enclosing only$1\%$computation within secure enclaves. Our work can achieve up to a$7.8\times$increase in efficiency and a$27\times$reduction in memory usage compared to the state-of-the-art.

Nowadays, by integrating the smart devices carried by users with existing communication infrastructures to provide large-scale, fine-grained and complex sensing services, crowdsensing as a novel sensing paradigm has significantly enriched the applications of smart city and promoted the development of Internet of Things (IoT). However, privacy has become skyrocketing concern for crowdsensing and gravely affected the deployment of crowdsensing. In this article, we present a framework to make the tradeoff between minimizing data aggregation error and guaranteeing system stability by jointly considering the privacy of participants, the randomness of sensing task arrival and the cost of platform. We propose an online control mechanism by exploiting Lyapunov stochastic optimization technique. Additionally, considering that, in reality, it always takes different time for different tasks to make sensing decisions, we extend standard Lyapunov stochastic optimization technique to make separate decisions for different types of sensing tasks in consecutive time. Through rigorous theoretical analysis, we prove that our time-average data aggregation error is approximately optimal while still maintaining system stability. By carrying out extensive simulations, we demonstrate the superiority of our proposed mechanisms.

Bike Sharing Systems (BSSs) have emerged as an economical and eco-friendly solution to alleviate the last-mile problem in intelligent transport systems. As an exclusive route selection problem in BSSs, Bike Trip Planning (BTP) has a clear goal: to select the available routes with minimum time cost for bike users, while satisfying their basic needs, e.g., the bounded longest walking distance. In this paper, we propose a real-time Lyapunov-based Bike Trip Planning (LBTP) policy that considers the users’ waiting at stations, which has not been sufficiently studied in the literature. Both the total time cost and the service rate of all users are the core criteria of a BSS, so we make use of the Lyapunov optimization theory to make a tradeoff between them. Our policy can achieve self-organizing bike redistribution without extra redistribution budget required. The evaluation results show the superiority of our policy on the both system utility and user service rate compared with the existing BTP policies, and reveal the extra travel time fairness degree among different types of users under our policy.

Speeding is one of the biggest threatens to road safety. However, facilities like radar detector and speed camera are not deployed everywhere, as roads in some areas like campus and residential areas often lack these facilities. Several solutions either depend on pre-deployed infrastructures, or require additional devices, which motivate us to explore the practicability of using smartphones’ acoustic sensors to detect vehicle speed. In this paper, we propose a Hybrid Detection system for vehicle Speed (HDSpeed). We first investigate the relationship between acoustic pattern and vehicle speed. According to our findings on typical patterns of both electric vehicles (EVs) and gasoline vehicles (GVs), we separately extract different features from the acoustic signals of EVs and GVs. A CNN and an LSTMN are designed for training EV and GV models, respectively. Considering that applying neural networks obtains coarse-grained information like a speed section, we propose a detection method based on active acoustic sensing, in which method HDSpeed calculates the fine-grained speed by detecting the distance change between the smartphone and the passing vehicle. In addition, the previously detected speed section can eliminate interferences of surrounding moving objects. Through extensive experiments in real driving environments, HDSpeed achieves an average error of$2.17km/h$.

Driving safety has drawn much public attention in recent years due to the fast-growing number of cars. Smoking is one of the threats to driving safety but is often ignored by drivers. Existing works on smoking detection either work in contact manner or need additional devices. This motivates us to explore the practicability of using smartphones to detect smoking events in driving environment. In this paper, we propose a cigarette smoking detection system, named HearSmoking, which only uses acoustic sensors on smartphones to improve driving safety. After investigating typical smoking habits of drivers, including hand movement and chest fluctuation, we design an acoustic signal to be emitted by the speaker and received by the microphone. We calculate Relative Correlation Coefficient of received signals to obtain movement patterns of hands and chest. The processed data is sent into a trained Convolutional Neural Network for classification of hand movement. We also design a method to detect respiration at the same time. To improve system performance, we further analyse the periodicity of the composite smoking motion. Through extensive experiments in real driving environments, HearSmoking detects smoking events with an average total accuracy of 93.44 percent in real-time.

Hand hygiene has a significant impact on human health. Proper handwashing, having a crucial effect on reducing bacteria, serves as the cornerstone of hand hygiene. For the elder with dementia, they suffer from a gradual loss of memory and difficulty in coordinating steps in the execution of handwashing. Proper assistance should be provided to them to ensure their hand hygiene adherence. Toward this end, we propose AWash, leveraging only commodity IMU sensor mounted on most wrist-worn devices (e.g., smartwatches) to characterize hand motions and provide assistance accordingly. To handle particular interference of senile dementia patients in IMU sensor readings, we design a number of effective techniques to segment handwashing actions, transform sensory input to body coordinate system, and extract sensor-body inclination angles. A hybrid neural network model is used to enable AWash to generalize to new users without retraining or adaptation, avoiding the trouble of collecting behavior information of every user. To meet the diverse needs of users with various executive functioning, we use a state machine to make prompt decisions, which supports customized assistance. Extensive experiments on a prototype with eight older participants demonstrate that AWash can increase the user's independence in the execution of handwashing.

Human-machine interface based on tongue-jaw movements has recently become one of the major technological trends. However, existing schemes have several limitations, such as requiring dedicated hardware and are usually uncomfortable to wear. This paper presents CanalScan, a nonintrusive system for tongue-jaw movement recognition using only commodity speaker and microphone mounted on ubiquitous off-the-shelf devices (e.g., smartphones). The basic idea is to send an acoustic signal, then captures its reflections and derive unique patterns of ear canal deformation caused by tongue-jaw movements. A dynamic segmentation method with Support Vector Domain Description is used to segment tongue-jaw movements. To combat sensor position-sensitive deficiency and ear-canal-shape-sensitive deficiency in multi-path reflections, we first design algorithms to assist users in adjusting the acoustic sensors to the same valid zone. Then we propose a data transformation mechanism to reduce the impacts of diversities in ear canal shapes and relative positions between sensors and the ear canal. CanalScan explores twelve unique and consistent features and applies a Random Forest classifier to distinguish tongue-jaw movements. Extensive experiments with twenty participants demonstrate that CanalScan achieves promising recognition for six tongue-jaw movements, is robust against various usage scenarios, and can be generalized to new users without retraining and adaptation.

Fitness can help to strengthen muscles, increase resistance to diseases and improve body shape. Nowadays, more and more people tend to exercise at home/office, since they lack time to go to the dedicated gym. However, it is difficult for most of them to get good fitness effect due to the lack of professional guidance. Motivated by this, we propose HearFit, the first non-invasive fitness monitoring system based on commercial smart speakers for home/office environments. To achieve this, we turn smart speakers into active sonars. We design a fitness detection method based on Doppler shift and adopt the short time energy to segment fitness actions. We design a high-accuracy LSTM network to determine the type of fitness. Combined with incremental learning, users can easily add new actions. Finally, we evaluate the local (i.e., intensity and duration) and global (i.e., continuity and smoothness) fitness quality of users to help to improve fitness effect and prevent injury. Through extensive experiments including over 7,000 actions of 10 types of fitness with and without dumbbells from 12 participants, HearFit can detect fitness actions with an average accuracy of 96.13%, and give accurate statistics in various environments.

Edge computing has become an increasingly popular computing paradigm. Deploying edge clouds allows performing data-intensive computing at the edge of the network instead of a remote cloud to reduce data access latency and improve data processing efficiency. One of the key challenges in data-intensive edge computing is how to effectively place the data at the edge clouds such that the access latency to the data is minimized. In this paper, we study such a data placement problem in edge computing where different data items have diverse popularity. We first propose a data popularity based placement method when the data requests are unknown. It maps both data items and edge servers to a virtual plane and places data based on its virtual coordinate in the plane. We consider data popularity during both the mapping of data items to the plane and making the placement decision. We further propose an optimization-based placement strategy for the case when the data requests are known. By formulating an integer programming problem, our proposed solution aims to find the optimal placement decision. Simulation results show that both proposed strategies efficiently reduce the average latency of data access.

The proliferation of Internet of Things (IoT) data and innovative mobile services has promoted an increasing need for low-latency access to resources such as data and computing services. Mobile edge computing has become an effective computing paradigm to meet the requirement for low-latency access by placing resources and dispatching tasks at the network edge near mobile users. The key challenge of such solution is how to efficiently place resources and dispatch tasks to meet the QoS of mobile users or maximize the platform’s utility. In this paper, we study the joint optimization problem of resource placement and task dispatching in mobile edge computing across multiple timescales under the dynamic status of edge servers. We first propose a two-stage iterative algorithm to solve the joint optimization problem in different timescales, which can handle the varieties among the dynamic of edge resources and/or tasks. We then propose a reinforcement learning (RL) based algorithm which leverages the learning capability of Deep Deterministic Policy Gradient (DDPG) technique to tackle the network variation and dynamic as well. The results from trace-driven simulations demonstrate that our proposed approaches can effectively place resources and dispatching tasks across two timescales to maximize the total utility of all scheduled tasks.

Vehicle to Vehicle (V2V) communication opens a new way to make vehicles directly communicate with each other, providing faster responses for time-sensitive tasks than cellular networks. Effective V2V routing protocols are essential yet challenging, as the high dynamic road environment makes communication easy to break. Many prediction methods proposed in the existing protocols to address this issue are either flawed or have a poor effect. In this paper, to cope with the two aspects of the problems that cause communication interrupt, i.e., link breaks and route quality degradation, we design an acceleration-based trajectory prediction algorithm to estimate the link lifetime, and a machine learning model to predict route quality. Based on the prediction algorithms, we propose PQR, a Prediction-supported Quality-aware Routing protocol, which can proactively switch to a better route before the current link breaks or the route quality degrades. Especially, considering the limitations of the current routing protocols, we elaborate a new hybrid routing protocol that integrates the topology-based method and location-based method to achieve instant communication. Simulation results show that PQR outperforms the existing protocols in Packet Delivery Ratio (PDR), Roundtrip Time (RTT), and Normalized Routing Overhead (NRO). Specifically, we have also implemented a vehicular testbed to demonstrate PQR’s real-world performance, and results show that PQR achieves almost no packet loss with latency less than 10ms during route handoff for topology change.

Arterial blood pressure (ABP) monitoring using wearables has emerged as a promising approach to empower users with self-monitoring for effective diagnosis and control of hypertension. However, existing schemes mainly monitor ABP at discrete time intervals, involve some form of user effort, have insufficient accuracy, and require collecting sufficient training data for model development. To tackle these problems, we propose Crisp-BP, a novel ABP monitoring system leveraging the PPG sensor available in commercial wrist-worn devices (e.g., smartwatches or fitness trackers). It enables continuous, accurate, user-independent ABP monitoring and requires no behavior changes during collecting PPG data. The basic idea is to illuminate a skin/tissue, measure the light absorption, and characterize ABP-related blood volume change in the artery. To obtain accurate measurements and relieve the pain of training data collection, we use an arterial pulse extraction method that removes interference caused by capillary pulses. Moreover, we design a contact pressure estimation method to combat the deficiency of PPG waveform being sensitive to the contact pressure between the sensor and the skin. In addition, we leverage the great power of Bidirectional Long Short Term Memory and design a hybrid neural network model to enable user-independent ABP monitoring, so that users do not have to provide training data for model development. Furthermore, we propose a transfer learning method that first extracts general knowledge from online PPG data, then use it to improve the learning of a new model on our target problem. Extensive experiments with 35 participants demonstrate that Crisp-BP obtains the average estimation error of 0.86 mmHg and 1.67 mmHg and the standard deviation error of 6.55 mmHg and 7.31 mmHg for diastolic pressure and systolic pressure, respectively. These errors are within the acceptable range regulated by the FDA's AAMI protocol, which allows average errors of up to 5 mmHg and a standard deviation of up to 8 mmHg. Our results demonstrate that Crisp-BP is promising for improving the diagnosis and control of hypertension as it provides continuousness, comfort, convenience, and accuracy.

With the rise of the Internet of Things (IoT), the number of mobile devices with sensing and computing capabilities increases dramatically, paving the way toward an emerging paradigm, i.e., crowdsensing that facilitates the interactions between humans and the surrounding physical world. Despite its superiority, particular attention is paid to be able to submit sensing data to the platform wherever possible to avoid leaking the sensitive information of participants and to incentivize them to improve sensing quality. In this article, we propose an incentive mechanism for participants, aiming to protect them from privacy leakage, ensure the availability of sensing data, and maximize the utilities of both platforms and participants by means of distributing different sensing tasks to different participants. More specifically, we formulate the interactions between platforms and participants as a multileader-multifollower Stackelberg game and derive the Stackelberg equilibrium (SE) of the game. Due to the difficulty to obtain the optimal strategy, a reinforcement learning algorithm, i.e., Q-learning is adopted to obtain the optimal sensing contributions of participants. In order to accelerate learning speed and reduce overestimation, a deep learning algorithm combined with Q-learning in a dueling network architecture, i.e., double deep Q network with dueling architecture (DDDQN) is proposed to obtain the optimal payment strategies of platforms. To evaluate the performance of our proposed mechanism, extensive simulations are conducted to show the superiority of our proposed mechanism compared with state-of-the-art approaches.

The safety of the elderly has attracted much attention nowadays. Among various daily activities, fall is one of the most dangerous events for the elderly, especially those who live alone. Most existing works on fall detection are based on wearable devices, which are inconvenient in using. Several solutions only use coarse-grained Wi-Fi signal information that contains many biases, and lack considerations on environmental changes. These situations motivate us to design a fine-grained and robust fall detection approach. In this article, we propose a fall detection system, called FallViewer, based on analyzing the channel state information (CSI) of Wi-Fi signals. To get fine-grained information, we propose phase and amplitude calibration methods for deviation correction. Then, an adjustment approach for antenna power is designed to eliminate the multipath interference. Furthermore, we apply a double sliding window to get a flexible threshold, which improves the robustness of FallViewer to various environments. Finally, FallViewer extracts features of the processed Wi-Fi signal and sends the features to a LibSVM for classification. Through experiments in different environments, FallViewer can detect fall events with an average accuracy of 95.8%, which indicates that FallViewer can work reliably and effectively.

Cloud radio access network (C-RAN) is a promising 5G network architecture by establishing baseband units (BBU) pools to perform baseband processing functionalities and deploying remote radio heads (RRHs) for wireless signal transmission and reception. Mobile-edge computing (MEC) offers a way to shorten the service delay by building small-scale cloud infrastructures at the network edge. By co-locating the BBU pool with edge cloud at the so-called BBU node, we can take full advantages of C-RAN and MEC for better spectrum utilization and delay-guaranteed services. In this article, we first study how to allocate each user's task to the BBU node and find the path from his/her accessing RRH node to the BBU node such that the maximum service delay among all the requests is minimized. We then consider this problem with survivability concerns, which is to use both primary and backup BBU nodes to issue the request such that the primary path and backup path are link disjoint. We analyze the complexities of these two problems and prove they are NP-hard in general. Subsequently, we devise a randomized approximation algorithm and an efficient heuristic to solve the considered problems, respectively. The simulation results show that the proposed algorithms outperform two benchmark heuristics in terms of acceptance ratio and maximum service delay.

Drowsy driving is one of the biggest threats to driving safety, which has drawn much public attention in recent years. Thus, a simple but robust system that can remind drivers of drowsiness levels with off-the-shelf devices (e.g., smartphones) is very necessary. With this motivation, we explore the feasibility of using acoustic sensors on smartphones to detect drowsy driving. Through analyzing real driving data to study characteristics of drowsy driving, we find some unique patterns of Doppler shift caused by three typical drowsy behaviours (i.e., nodding, yawning and operating steering wheel), among which operating steering wheels is also related to drowsiness levels. Then, a real-time Drowsy Driving Detection system named D3-Guard is proposed based on the acoustic sensing abilities of smartphones. We adopt several effective feature extraction methods, and carefully design a high-accuracy detector based on LSTM networks for the early detection of drowsy driving. Besides, measures to distinguish drowsiness levels are also introduced in the system by analyzing the data of operating steering wheel. Through extensive experiments with five drivers in real driving environments, D3-Guard detects drowsy driving actions with an average accuracy of 93.31%, as well as classifies drowsiness levels with an average accuracy of 86%.

Mobile Edge Computing (MEC) offers a way to shorten the cloud servicing delay by building the small-scale cloud infrastructures at the network edge, which are in close proximity to the end users. Moreover, Network Function Virtualization (NFV) has been an emerging technology that transforms from traditional dedicated hardware implementations to software instances running in a virtualized environment. In NFV, the requested service is implemented by a sequence of Virtual Network Functions (VNF) that can run on generic servers by leveraging the virtualization technology. Service Function Chaining (SFC) is defined as a chain-ordered set of placed VNFs that handles the traffic of the delivery and control of a specific application. NFV therefore allows to allocate network resources in a more scalable and elastic manner, offer a more efficient and agile management and operation mechanism for network functions and hence can largely reduce the overall costs in MEC. In this paper, we study the problem of how to place VNFs on edge and public clouds and route the traffic among adjacent VNF pairs, such that the maximum link load ratio is minimized and each user's requested delay is satisfied. We consider this problem for both totally ordered SFCs and partially ordered SFCs. We prove that this problem is NP-hard, even for the special case when only one VNF is requested. We subsequently propose an efficient randomized rounding approximation algorithm to solve this problem. Extensive simulation results show that the proposed approximation algorithm can achieve close-to-optimal performance in terms of acceptance ratio and maximum link load ratio.

Many deep learning applications deployed in dynamic environments change over time, in which the training models are supposed to be continuously updated with streaming data to guarantee better descriptions of data trends. However, most state-of-the-art learning frameworks support well inofflinetraining methods while omittingonline model updatingstrategies. In this work, we propose and implementiDlaLayer, a thin middleware layer on top of existing training frameworks that streamlines the support and implementation of online deep learning applications. In pursuit of good model quality and fast data incorporation, we design a Data Life Aware model updating strategy (DLA), which builds training data samples according to contributions of data from different life stages, and considers the training cost consumed in model updating. We evaluate iDlaLayer's performance through simulations and experiments based on TensorflowOnSpark with three representative online learning workloads. Our experimental results demonstrate that iDlaLayer reduces the overall elapsed time of ResNet, DeepFM and PageRank by 11.3, 28.2, and 15.2 percent compared to the periodic update strategy, respectively. It further achieves an average 20 percent decrease in training cost and brings about a 5 percent improvement in model quality against the traditional continuous training method.

Mobile Crowd Sensing (MCS) enables the platform to offer data-based service by incentivizing mobile users to perform sensing task and collecting sensing data from them. Most of the existing works on MCS only consider designing incentive mechanisms for a single MCS platform. In this paper, we study the incentive mechanism in MCS with multiple platforms under two scenarios: competitive platform and cooperative platform. We correspondingly propose new competitive and cooperative mechanisms for each scenario. In the competitive platform scenario, platforms decide their prices on rewards to attract more participants, while the users choose which platform to work for. We model such a competitive platform scenario as a two-stage Stackelberg game. In the cooperative platform scenario, platforms cooperate to share sensing data with each other. We model it as many-to-many bargaining. Moreover, we first prove the NP-hardness of exact bargaining and then propose heuristic bargaining. Finally, numerical results show that (1) platforms in the competitive platform scenario can guarantee their payoff by optimally pricing on rewards and participants can select the best platform to contribute; (2) platforms in the cooperative platform scenario can further improve their payoff by bargaining with other platforms for cooperatively sharing collected sensing data.

Micro finger gesture recognition is an emerging approach to realize more friendly interaction between human and smart devices, especially for small wearable devices, such as smartwatches and virtual reality glasses. This paper proposes airFinger, a novel solution utilizing NIR light sensing to realize both real-time gesture recognition and finger tracking aiming at micro finger gestures. Using a custom NIR-based sensor with novel algorithms to capture subtle finger movements, airFinger enables to detect a rich set of micro finger gestures and track finger movements in terms of scrolling direction, velocity, and displacement. Besides, airFinger is capable of effective noise mitigation, gesture segmentation, and reducing false recognition due to the unintentional actions of users. Extensive experimental results demonstrate that airFinger has robustness against individual diversity, gesture inconsistency, and many other impacts. The overall performance reaches an average accuracy as high as 98.72% over a set of 8 micro finger gestures among 10, 000 gesture samples collected from 10 volunteers.

Mobile devices are promising to apply two-factor authentication in order to improve system security and enhance user privacy-preserving. Existing solutions usually have certain limits of requiring some form of user effort, which might seriously affect user experience and delay authentication time. In this paper, we propose PPGPass, a novel mobile two-factor authentication system, which leverages Photoplethysmography (PPG) sensors in wrist-worn wearables to extract individual characteristics of PPG signals. In order to realize both nonintrusive and secure, we design a two-stage algorithm to separate clean heartbeat signals from PPG signals contaminated by motion artifacts, which allows verifying users without intentionally staying still during the process of authentication. In addition, to deal with non-cancelable issues when biometrics are compromised, we design a repeatable and non-invertible method to generate cancelable feature templates as alternative credentials, which enables to defense against man-in-the-middle attacks and replay attacks. To the best of our knowledge, PPGPass is the first nonintrusive and secure mobile two-factor authentication based on PPG sensors in wearables. We build a prototype of PPGPass and conduct the system with comprehensive experiments involving multiple participants. PPGPass can achieve an average F1 score of 95.3%, which confirms its high effectiveness, security, and usability.

Due to the harsh environment and energy limitation, maintaining efficient communication is crucial to the lifetime of Underwater Sensor Networks (UWSN). Named Data Networking (NDN), one of future network architectures, begins to be applied to UWSN. Although Underwater Named Data Networking (UNDN) performs well in data transmission, it still faces some security threats, such as the Denial-of-Service (DoS) attacks caused by Interest Flooding Attacks (IFAs). In this paper, we present a new type of DoS attacks, named as Synergetic Denial-of-Service (SDoS). Attackers synergize with each other, taking turns to reply to malicious interests as late as possible. SDoS attacks will damage the Pending Interest Table, Content Store, and Forwarding Information Base in routers with high concealment. Simulation results demonstrate that the SDoS attacks quadruple the increased network traffic compared with normal IFAs and the existing IFA detection algorithm in UNDN is completely invalid to SDoS attacks. In addition, we analyze the infection problem in UNDN and propose a defense method Trident based on carefully designed adaptive threshold, burst traffic detection, and attacker identification. Experiment results illustrate that Trident can effectively detect and resist both SDoS attacks and normal IFAs. Meanwhile, Trident can robustly undertake burst traffic and congestion.

Efficient and smart business processes are heavily dependent on the Internet of Things (IoT) networks, where end-to-end optimization is critical to the success of the whole ecosystem. These systems, including industrial, healthcare, and others, are large scale complex networks of heterogeneous devices. This introduces many security and access control challenges. Blockchain has emerged as an effective solution for addressing several such challenges. However, the basic algorithms used in the business blockchain are not feasible for large scale IoT systems. To make them scalable for IoT, the complex consensus-based security has to be downgraded. In this article, we propose a novel lightweight proof of block and trade (PoBT) consensus algorithm for IoT blockchain and its integration framework. This solution allows the validation of trades as well as blocks with reduced computation time. Also, we present a ledger distribution mechanism to decrease the memory requirements of IoT nodes. The analysis and evaluation of security aspects, computation time, memory, and bandwidth requirements show significant improvement in the performance of the overall system.

The Internet of Things has such a profound impact that we have witnessed crowdsensing has emerged as the most popular sensing paradigm where participants sense and aggregate data to the platform by smart devices. However, the participants may not be willing to involve in data sensing and aggregation if they are not sufficiently compensated or their personalized private information are disclosed. In order to overcome the above issues, this article proposes a payment-privacy protection level (PPL) game, where each participant submits his sensing data with a specified PPL while the platform chooses a corresponding payment to the participant. Additionally, we derive the Nash equilibrium point of the game. Considering that the payment-PPL model is unknown in practice, we employ a reinforcement learning technique, i.e., Q-learning to obtain the payment-PPL strategy in a dynamic payment-PPL game. We further use the deep Q network (DQN), which combines a deep-learning technique with Q-learning to accelerate the learning speed. Through extensive simulations, we verify that our proposed algorithm using DQN achieves superior performance in terms of utilities of both platform and participants and data aggregation accuracy compared with the one using Q-learning.

In this article, we propose points-of-interest (POI)-tagging App-assisted incentive mechanism (PTASIM), an incentive mechanism that explores the cooperation with POI-tagging App for mobile edge crowdsensing (MEC). PTASIM requests App to tag some edges to be POI, which further guides App users to perform tasks at that location. We further model the interactions of users, platform, and App by a three-stage decision process. App first determines the POI-tagging price to maximize its payoff. Platform and users subsequently decide how to determine tasks reward and select edges to be tagged, and how to select the best task to perform, respectively. We analyze the optimal solution in those stages. Specifically, we prove that greedy algorithm could provide the optimal solution for platform's payoff maximization in polynomial time. The numerical results show that: 1) the cooperation with App brings long-term and sufficient participation; and 2) the optimal strategies reduce platform's tasks cost as well as improve App's revenues.

Blockchain-based femtocell networks aim to build decentralized frameworks which enable easy deployment and low power consumption, thus they have been seen promising technologies to make up the coverage of cellular networks in the next generation communication system. This article aims to employ power control to support quality-of-service provisioning, especially the guarantee for the transmission rate of a macrocell user (MUE) and the time delay of femtocell users (FUEs) in two-tier femtocell networks, where the MUE and FUEs share the same communication channel. We formulate the interactions among the macrocell base station and FUEs as a Stackelberg game to maximize the utilities of MUE and FUEs by obtaining the optimal power allocation and pricing strategy. Considering the uncertainty of channel gain which is expressed as a function of transmission distance, we propose a worst-case method to transform the uncertain optimization problem into a deterministic one. We then design two algorithms by considering the dynamics of FUEs, i.e., FUEs may join and leave femtocells. Numerical results verify the convergence and superior performance of our proposed algorithms.

In memory data analytic frameworks like Apache Spark are employed by an increasing number of diverse applications-such as machine learning, graph computation, and scientific computing, which benefit from the long-running process (e.g. executor) programming model to avoid system I/O overhead. However, existing resource allocation strategies mainly rely on the peak demand normally specified by users. Since the resource usages of long-running applications like iterative computation vary significantly over time, we find that peak-demand-based resource allocation policies lead to low cloud utilization in production environments. In this paper, we present an elastic utilization aware executor provisioning approach for iterative workloads on Apache Spark (i.e., iSpark). It can identify the causes of resource underutilization due to an inflexible resource policy, and elastically adjusts the allocated executors over time according to the real-time resource usage. In general, iterative applications require more computation resources at the beginning stage and their demands for resources diminish as more iterations are completed. iSpark aims to timely scale up or scale down the number of executors in order to fully utilize the allocated resources while taking the dominant factor into consideration. It further preempts the underutilized executors and preserves the cached intermediate data to ensure the data consistency. Testbed evaluations show that iSpark averagely improves the resource utilization of individual executors by 35.2 % compared to vanilla Spark. At the same time, it increases the cluster utilization from 32.1% to 51.3% and effectively reduces the overall job completion time by 20.8% for a set of representative iterative applications.

Cloud manufacturing (CM) is an open and service-oriented platform that virtualizes distributed design, machining, and assembly resources together in order to provide a seamless, adaptive, and high quality transaction of manufacturing procedures. Despite the results in resource discovery and planning, the research in robustness and security of the systems falls behind in many aspects. The lack of such knowledge puts a serious challenge for the wide deployment and adoption of cloud manufacturing which is naturally connected to the Internet and exposed to cyber attacks. To bridge this gap, we study a specific type of equipment contention attack in cloud manufacturing. Through requesting extra shares of scarce resources, an attacker can gain advantage in competition with other users and reduce the efficiency of the overall system. We design a mechanism to mitigate such attacks through measuring the remaining machining capabilities in the cloud. The cloud administrator can control cost difference between the attacker and subsequent service requesters. Simulations of a mid-size city manufacturing cloud are conducted and the results show that our approach will incur low increases in cost for benign users while discouraging the equipment contention attacks.

Since the number of cars has grown rapidly in recent years, driving safety draws more and more public attention. Drowsy driving is one of the biggest threatens to driving safety. Therefore, a simple but robust system that can detect drowsy driving with commercial off-the-shelf devices (such as smart-phones) is very necessary. With this motivation, we explore the feasibility of purely using acoustic sensors embedded in smart-phones to detect drowsy driving. We first study characteristics of drowsy driving, and find some unique patterns of Doppler shift caused by three typical drowsy behaviors, i.e., nodding, yawning and operating steering wheel. We then validate our important findings through empirical analysis of the driving data collected from real driving environments. We further propose a real-time Drowsy Driving Detection system (D3-Guard) based on audio devices embedded in smartphones. In order to improve the performance of our system, we adopt an effective feature extraction method based on undersampling technique and FFT, and carefully design a high-accuracy detector based on LSTM networks for the early detection of drowsy driving. Through extensive experiments with 5 volunteer drivers in real driving environments, our system can distinguish drowsy driving actions with an average total accuracy of 93.31% in real-time. Over 80% drowsy driving actions can be detected within first 70% of action duration.

Machine learning (ML) has shown its impressive performance in the modern world, and many corporations leverage the technique of machine learning to improve their service quality, e.g., Facebook's DeepFace. Machine learning models with a collection of private data being processed by a training algorithm are deemed to be increasingly confidential. Confidential models are typically trained in a centralized cloud server but publicly accessible. ML-as-a-service (MLaaS) system is one of running examples, where users are allowed to access trained models and are charged on a pay-per-query basis.

Sign language is a natural and fully-formed communication method for deaf or hearing-impaired people. Unfortunately, most of the state-of-the-art sign recognition technologies are limited by either high energy consumption or expensive device costs and have a difficult time providing a real-time service in a daily-life environment. Inspired by previous works on motion detection with wearable devices, we propose Sign Speaker - a real-time, robust, and user-friendly American sign language recognition (ASLR) system with affordable and portable commodity mobile devices. SignSpeaker is deployed on a smartwatch along with a smartphone; the smartwatch collects the sign signals and the smartphone outputs translation through an inbuilt loudspeaker. We implement a prototype system and run a series of experiments that demonstrate the promising performance of our system. For example, the average translation time is approximately $1.1$ seconds for a sentence with eleven words. The average detection ratio and reliability of sign recognition are 99.2% and 99.5%, respectively. The average word error rate of continuous sentence recognition is 1.04% on average.

Internet of Things (IoT) and blockchain (BC) technologies have been dominating their respective research domains for some time. IoT offers automation at the finest level in different fields, while BC provides secure transaction processing for asset exchanges. The capability of IoT devices to generate transactions prompts their integration with BC as the next logical step. The biggest challenges in this integration are the scalability of ledger and rate of transaction execution in BC. On one hand, due to their large numbers, IoT devices will generate transactions at a rate which current block chain solutions cannot handle. On the other hand, implementing BC peers onto IoT devices is impossible due to resource constraints. This prohibits direct integration of both technologies in their current state. In this paper, we propose a solution to address these challenges by using a local peer network to bridge the gap. It restricts the number of transactions which enters the global BC by implementing a scalable local ledger, without compromising on the peer validation of transactions at local and global level. The testbed evaluations show significant reduction in the block weight and ledger size on global peers. The solution also indirectly improves the transaction processing rate of all peers due to load distribution.

Smart city is a key component in Internet of Things, so it has attracted much attention. The emergence of mobile crowd sensing (MCS) systems enables many smart city applications. In an MCS system, sensing tasks are allocated to a number of mobile users. As a result, the sensing related context of each mobile user plays a significant role on service quality. However, some important sensing context is ignored in the literature. This motivates us to propose a context-aware multiarmed bandit (C-MAB) incentive mechanism to facilitate quality-based worker selection in an MCS system. We evaluate a worker's service quality by its context (i.e., extrinsic ability and intrinsic ability) and cost. Based on our proposed C-MAB incentive mechanism and quality evaluation design, we develop a modified Thompson sampling worker selection (MTS-WS) algorithm to select workers in a reinforcement learning manner. MTS-WS is able to choose effective workers because it can maintain accurate worker quality information by updating evaluation parameters according to the status of task accomplishment. We theoretically prove that our C-MAB incentive mechanism is selection efficient, computationally efficient, individually rational, and truthful. Finally, we evaluate our MTS-WS algorithm on simulated and real-world datasets in comparison with some other classic algorithms. Our evaluation results demonstrate that MTS-WS achieves the highest cumulative utility of the requester and social welfare.

Mobile edge computing (MEC) offers a way to shorten the cloud servicing delay by building the small-scale cloud infrastructures, such as cloudlets at the network edge, which are in close proximity to end users. On one hand, it is energy consuming and costly to place each cloudlet on each access point (AP) to process the requested tasks. On the other hand, the service provider should provide delay-guaranteed service to end users, otherwise they may get revenue loss. In this paper, we first model how to calculate the task completion delay in MEC and mathematically analyze the energy consumption of different equipments in MEC. Subsequently, we study how to place cloudlets on the network and allocate each requested task to cloudlets and public cloud with the minimum total energy consumption without violating each task's delay requirement. We prove that this problem is NP-hard and propose a Benders decomposition-based algorithm to solve it. We also present a software-defined network (SDN)-based framework to deploy the proposed algorithm. Extensive simulations reveal that the proposed algorithm can achieve an (close-to-)optimal performance in terms of energy consumption and acceptance ratio compared with two benchmark heuristics.

With the rapid increasing of smart phones and the advances of embedded sensing technologies, mobile crowd sensing (MCS) becomes an emerging sensing paradigm for large-scale sensing applications. One of the key challenges of large-scale mobile crowd sensing is how to effectively select the minimum set of participants from the huge user pool to perform the tasks and achieve a certain level of coverage while satisfying some constraints. This becomes more complex when the sensing tasks are dynamic (coming in real time) and heterogeneous (with different temporal and spacial coverage requirements). In this paper, we consider such a dynamic participant selection problem with heterogeneous sensing tasks which aims to minimize the sensing cost while maintaining certain level of probabilistic coverage. Both offline and online algorithms are proposed to solve the challenging problem. Extensive simulations over a real-life mobile dataset confirm the efficiency of the proposed algorithms.

Previous works on social network de-anonymization focus on designing accurate and efficient de-anonymization methods. We attempt to investigate the intrinsic relationship between the attacker’s knowledge and the expected de-anonymization gain. A common intuition is that more knowledge results in more successful de-anonymization. However, our analysis shows this is not necessarily true if the attacker uses the full background knowledge for de-anonymization. Our findings leave intriguing implications for the attacker to make better use of the background knowledge for de-anonymization and for the data owners to better measure the privacy risk when releasing their data to third parties.

The usage of hybrid energy supplied sensors in the Internet of Things has enabled longer lifetime of sensors and expanded scope of applications. These sensors can combine advantages of environmental energy harvesting techniques and wireless energy harvesting techniques. However, how to coordinate them is still a challenge and has not been studied extensively. In this article, we present a system based on mobile crowd wireless charging to manage energy of hybrid energy supplied sensors. When environmental energy is insufficient, the system will utilize smart devices carried by mobile users as chargers to provide wireless energy. We construct and study a W3W problem in the system: when to leverage mobile crowd wireless charging to support rechargeable sensors, where to perform wireless energy transfer, and whom to allocate and incentivize as chargers to maximize useful energy value over all sensors subject to a budget. In order to control the actual quality of wireless energy charging, we propose a design principle named task completion trustfulness. We consider offline and online conditions and design corresponding algorithms with incentive allocations. Extensive simulations are conducted to demonstrate the effectiveness of our algorithms, which also validates our theoretical results.

The tremendous growth of cloud computing and large-scale data analytics highlight the importance of reducing datacenter power consumption and environmental impact of brown energy. While many Internet service operators have at least partially powered their datacenters by green energy, it is challenging to effectively utilize green energy due to the intermittency of renewable sources, such as solar or wind. We find that the geographical diversity of internet-scale services can be carefully scheduled to improve the efficiency of applying green energy in datacenters. In this paper, we propose a holistic heterogeneity-aware cloud workload management approach, sCloud, that aims to maximize the system goodput in distributed self-sustainable datacenters. sCloud adaptively places the transactional workload to distributed datacenters, allocates the available resource to heterogeneous workloads in each datacenter, and migrates batch jobs across datacenters, while taking into account the green power availability and QoS requirements. We formulate the transactional workload placement as a constrained optimization problem that can be solved by nonlinear programming. Then, we propose a batch job migration algorithm to further improve the system goodput when the green power supply varies widely at different locations. Finally, we extend sCloud by integrating a flexible batch job manager to dynamically control the job execution progress without violating the deadlines. We have implemented sCloud in a university cloud testbed with real-world weather conditions and workload traces. Experimental results demonstrate sCloud can achieve near-to-optimal system performance while being resilient to dynamic power availability. sCloud with the flexible batch job management approach outperforms a heterogeneity-oblivious approach by 37 percent in improving system goodput and 33 percent in reducing QoS violations.

With the rapid increasing of the number of mobile devices and their embedded sensing technologies, mobile crowd sensing (MCS) has become an emerging modern sensing paradigm for performing large-scale urban sensing. One of the key challenges of large-scale mobile crowd sensing systems is how to effectively select the minimum set of appropriate participants from the huge user pool to perform the sensing tasks. The capability of a particular user for certain task depends on many factors, such as her moving pattern/behavior, device capability, sensor quality, or even uploading bandwidth. Many of these information of participants are unknown by the selection mechanism. Therefore, self-learning based approaches have been proposed to learn the users' capability for certain tasks via multiple trials and their online performances. In this paper, we first model the cumulative participant selection problem as a combinational multi-armed bandit problem and present an online selection algorithm which leverages the historical performing records of participants to learn the different capabilities (both sensing probability and time delay) of participants. Further, to consider the cost of switching participant for particular tasks, we then introduce the cumulative participant selection problem with switch costs and propose a corresponding online learning method. For both proposed learning algorithms, we provide regret analysis. In addition, extensive simulations with real-world mobile datasets are conducted for the evaluations of the proposed methods. Our simulation results confirm the effeteness of them.

Privacy-preserving data publishing has been a heated research topic in the last decade. Numerous ingenious attacks on users' privacy and defensive measures have been proposed for the sharing of various data, varying from relational data, social network data, spatiotemporal data, to images and videos. Speech data publishing, however, is still untouched in the literature. To fill this gap, we study the privacy risk in speech data publishing and explore the possibilities of performing data sanitization to achieve privacy protection while preserving data utility simultaneously. We formulate this optimization problem in a general fashion and present thorough quantifications of privacy and utility. We analyze the sophisticated impacts of possible sanitization methods on privacy and utility, and also design a novel method - key term perturbation for speech content sanitization. A heuristic algorithm is proposed to personalize the sanitization for speakers to restrict their privacy leak (p-leak limit) while minimizing the utility loss. The simulations of linkage attacks and sanitization on real datasets validate the necessity and feasibility of this work.

In mobile crowdsensing (MCS), to select the optimal set of participants for a particular sensing task, the cloud-based MCS platform requires mobile users to submit their bids and their sensing quality data. This can cause privacy breaches. One possible solution is to leverage secure sharing or bidding schemes to protect participants' personal information during selection. However, these schemes suffer from high overheads, poor scalability and more importantly, the group formation has never been studied. To address this issue and to enhance the protection of user privacy, we propose a set of novel privacy-preserving grouping methods, which place participants into small groups over hierarchical edge clouds. By doing this, not only can the participants be hidden in groups, but also the overall privacy-preserving participant selection becomes more scalable. The design goal to minimize the communication cost during secure sharing/bidding within groups, while satisfying each participant's requirement for privacy preservation. For different scenarios and optimization functions, we propose a set of grouping schemes to fulfill this goal. Extensive simulations over both synthetic and real-life datasets illustrate the efficiency of proposed mechanisms.

The recent proliferation of public hotspots has given rise to Wi-Fi advertising where venue owners promote their business by pushing advertisers' advertisements on their hotspots. However, a small business usually has insufficient budget to make a purchase for a whole webpage. Therefore, in this paper, we propose GAWA, a Group-buying based Auction mechanism for Wi-Fi Advertising among a venue owner, group leaders and advertisers, which is composed of three phases. More specifically, in the first phase, we propose an algorithm to decide a group bid for each group leader and winning advertisers for each group. In the second phase, the venue owner assigns venues to group leaders by a novel winning group leader determination algorithm. In the third phase, the mechanism determines how much each winning group leader should charge each advertiser in the winning group. We prove that GAWA is computationally efficient, and possesses excellent economic properties such as individual rationality, budget balance, and truthfulness. We evaluate the proposed algorithms using large-scale simulations, and demonstrate the effectiveness and efficiency of our design when comparing with the state-of-the-art approaches.

With the rapid increasing of smart phones and their embedded sensing technologies, mobile crowd sensing (MCS) becomes an emerging sensing paradigm for performing large-scale sensing tasks. One of the key challenges of large-scale mobile crowd sensing systems is how to effectively select the minimum set of appropriate participants from the huge user pool to perform the tasks. However, the capabilities of individual participants are usually unknown by the selection mechanism, which leads to the most challenging issue of participant selection. While online learning techniques can be used to learn the participant's capability, the diverse expertise of each individual makes a single capability metric is not sufficient. To address the multi-expertise of participants, in this paper we introduce a new self-learning architecture which leverages the historical performing records of participants to learn the different capabilities (both sensing probability and time delay) of participants. Formulating the participant selection problem as a combinational multi-armed bandit problem, we present an online participant selection algorithm with both performance guarantee and bounded regret. Extensive simulations with a real-world mobile dataset demonstrate the efficiency of the proposed solution.

Pedestrian dead reckoning enables pervasive indoor localization without a site survey on fingerprints or an intensive deployment of infrastructures. But accumulated errors in dead reckoning limit the spread of pervasive indoor location-based services. Existing landmark-based approaches mostly rely on resetting the user’s position with the landmark position only when the user is detected while on arrival at a landmark. However, such methods are still restricted by the specific movement patterns and sparse landmark distributions so that the opportunity for position calibration is limited. In this paper, an accurate peer-assisted localization system (calledSoundMark) on a smartphone with no prior infrastructure or fingerprinting is proposed. It calibrates mobile user’s dead reckoning position by leveraging the location constraints between another stationary user who arrives at a landmark. To detect whether a user arrives at a landmark, motion pattern is extracted by fusing the multiple sensors. Then, user activity in the landmark is decomposed to determine whether the user is stationary for performing audio ranging. Besides, SoundMark also applies a mobility-induced time-difference-of-arrival-based audio ranging to extract the location constraints between the peers for localization. SoundMark is implemented on the Android platform for evaluations. The results show that the accuracy of proposed peer-assisted localization is within 2.1 m at the percentage of 80%.

It is a significant challenge for device-to-device (D2D) networks to deliver mobile videos among mobile users due to the highly nondeterministic and intermittent connectivity. In this paper, we propose to integrate the random mobility of users in mobile opportunistic D2D networks with crowdsourcing to push mobile video Ads. Incentives are key to the success of video Ads push as it heavily depends on how actively mobile users participate in it. To stimulate users to perform mobile video Ads push tasks, we model the interaction between depositories and the Ad provider as a reverse auction. More specifically, we try to maximize the utility of Ad provider by selecting a subset of depositories before a specified deadline. We first propose an online auction (OA) algorithm, which runs efficiently in polynomial time, guarantees individual rationality, profitability. However, it does not guarantee truthfulness and thus limits its practicality. We then introduce two truthful OA algorithms, i.e., TOA and TOA-MM. We carry out trace-driven simulation to verify the three OA algorithms. The simulation results corroborate that the proposed algorithms have superior performance and efficiently stimulate mobile users to make contribution to video Ads push.

Mobile crowdsensing systems aim at providing various novel sensing applications by recruiting pervasive users with mobile devices, which are now equipped with enriched built-in sensors (e.g., GPS, microphone, camera, gyroscope, accelerometer, etc.). A key factor to enable such systems is substantial participation of large amount of mobile users. In this paper, we focus on the data collection in mobile opportunistic crowdsensing, where the data can be transferred between mobile users via opportunistic device-to-device communications. The goal is to deliver the sensed data from the collector to the corresponding requester, which can maximize the collector's rewards. Here, we assume that the data collection has time-sensitive characteristics, i.e., the reward is time-sensitive. We consider selfish mobile users with rational behaviors, and propose a credit-based incentive-aware mechanism to stimulate mobile users to participate in data collection for mobile opportunistic crowdsensing. Particularly, we propose an effective mechanism to define the expected rewards for the sensed data, and formulate the sensed data trading as a two-person cooperative game, whose solution is obtained through the Nash bargaining theory. Extensive simulations based on both synthetic and real-world mobility traces are conducted to validate the efficiency of our incentive-aware mechanisms.

Wireless energy harvesting is promising to be a new opportunity to prolong the lifetime of rechargeable sensors in the Internet of Things. However, how to recharge the sensors and manage charging energy is still a problem. Most existing methods are based on robots or vehicles carrying battery packs to charge sensors. They are vulnerable to the sensors distributed in complex terrain and have high hardware maintaining cost. To address this issue, we present crowd-charging (CC), a novel crowdsourcing-based wireless energy charging model for rechargeable sensors. It leverages smart devices carried by users as mobile crowd energy resources (chargers) to provide wireless energy to sensors. The challenge is how to incentivize and allocate mobile users to optimize the total charging quality of all the sensors. Besides monetary energy revenues, we design a bonus game to entertain participated users. We also propose three user allocation algorithms, CC algorithm (CCA), and two improved versions of CCA, i.e., CC and CC . The improved algorithms give great improvement for our model and they have different advantages suitable for different situations. We conduct extensive simulations and demonstrate the effectiveness of our algorithms with numerical results.

We consider a private data set composed of a set of individuals, and the data are outsourced to a remote cloud server. We revisit the classic query auditing problem in this outsourcing scenario; the cloud audits each newly arrived query on a single attribute, and the query is rejected if answering it compromises any individual's privacy. Various query auditing issues have been studied and addressed before. However, previous auditing schemes either have the difficulty of removing denial threats, or lack the analysis of utility (which is defined as the number of answered queries). In this paper, we study the auditing of a sequence of polynomial-time computable queries. Each query is of format f(X̃) a, where f is any polynomial function, X̃ is a subset of the private data set, and the answer is either “yes” or “no”. Existing methods cannot be applied directly to audit such a query, because it intermingles several types of functions (e.g., sum and max/min). Hence, we propose CASTLE, which is an inequality query auditing scheme that evaluates the risk of answering a query based on the query history and determines whether a newly arrived query should be answered correctly against a denial threat. Furthermore, to overcome the limitations of the existing query auditing mechanisms, which are of low utility, we relax CASTLE to increase the utility by returning answers with slight perturbations. We show that our method can be applied to audit intermingled equality queries with an extension. Experiments are conducted to evaluate the efficiency and effectiveness of our methods.

Today enterprises have massive stream data that require to be processed in real time due to data explosion in recent years. Spark Streaming as an emerging system is developed to process real time stream data analytics by using micro-batch approach. The unified programming model of Spark Steaming leads to some unique benefits over other traditional streaming systems, such as fast recovery from failures, better load balancing and resource usage. It treats the continuous stream as a series of micro-batches of data and continuously process these micro-batch jobs. However, efficient scheduling of micro-batch jobs to achieve high throughput and low latency is very challenging due to the complex data dependency and dynamism inherent in streaming workloads. In this paper, we propose A-scheduler, an adaptive scheduling approach that dynamically schedules parallel micro-batch jobs in Spark Streaming and automatically adjusts scheduling parameters to improve performance and resource efficiency. Specifically, A-scheduler dynamically schedules multiple jobs concurrently using different policies based on their data dependencies and automatically adjusts the level of job parallelism and resource shares among jobs based on workload properties. Furthermore, we integrate dynamic batching technique with A-Scheduler to further improve the overall performance of the customized Spark Streaming system. It relies on an expert fuzzy control mechanism to dynamically adjust the length of each batch interval in response to time-varying streaming workload and system processing rate. We implemented A-scheduler and evaluated it with a real-time security event processing workload. Our experimental results show that A-scheduler with dynamic batching can reduce end-to-end latency by 38 percent and meanwhile improve workload throughput and energy efficiency by 23 and 15 percent, respectively, compared to the default Spark Streaming scheduler.

A femtocell network which is supported by a macrocell base station and some femtocell base stations provides more reliable transmission, higher wireless capacity, and broader coverage. However, it may face eavesdropping risk, which provides an eavesdropper with a chance to overhear a macrocell user's confidential information. In this paper, we study a secrecy transmission problem for a downlink two-tier femtocell network with imperfect channel state information (CSI), where an eavesdropper wiretaps the legitimate macrocell user. More specifically, we aim to maximize the secrecy rate by jointly optimizing the power allocation and quality-of-service (QoS) requirement in terms of outage probability. We consider two types of CSI, i.e., instantaneous and statistic CSI, respectively, which can robustly guarantee the QoS of users in a complex communication environment. For the instantaneous CSI communication environment, where there exist estimated errors between instantaneous channel gains and their estimated values, we propose a novel conversion method to extract the approximate closed-form expressions of outage probability constraints. For the statistic CSI communication environment, where channel gains obey Rayleigh fading, we design a new method to obtain deterministic expressions by considering the expectations and variances of instantaneous channel gains. Then, the uncertainty and non-convexity of objective function are solved with the aid of variable substitution and Taylor expansion. Moreover, two iterative algorithms are proposed to derive the optimal transmission powers. Finally, we evaluate the proposed algorithms using large scale simulations, and present extensive evaluation results to demonstrate the effectiveness of our proposed algorithms.

While most existing indoor localization techniques are device-based, many emerging applications such as intruder detection and elderly monitoring drive the needs of device-free localization, in which the target can be localized without any device attached. Among the diverse techniques, received signal strength (RSS) fingerprint-based methods are popular because of the wide availability of RSS readings in most commodity hardware. However, current fingerprint-based systems suffer from high human labor cost to update the fingerprint database and low accuracy due to the large degree of RSS variations. In this paper, we propose a fingerprint-based device-free localization system named iUpdater to significantly reduce the labor cost and increase the accuracy. We present a novel self-augmented regularized singular value decomposition (RSVD) method integrating the sparse attribute with unique properties of the fingerprint database. iUpdater is able to accurately update the whole database with RSS measurements at a small number of reference locations, thus reducing the human labor cost. Furthermore, iUpdater observes that although the RSS readings vary a lot, the RSS differences between both the neighboring locations and adjacent wireless links are relatively stable. This unique observation is applied to overcome the short-term RSS variations to improve the localization accuracy. Extensive experiments in three different environments over 3 months demonstrate the effectiveness and robustness of iUpdater.

Mobile crowd sensing has become a promising paradigm for mobile users to collect information. Considering that the task information push is not free and there are many users who are not interested in the current task or provide noisy sensing data, one of the imminent problems is how to recommend high-quality and interested users in real time and steer participators to collect data with adequate budgets. However, it is difficult to predict the data quality and users' interest without the validity of real data. In this paper, we propose a user recommender system where the users' data qualities for sensing tasks are derived from historical statistical data to filter out the non-interested and malicious users in current task. The aim is to recruit a sub-group of participators for efficient crowd sensing, in order to maximize the platform utility. We show that our problem is NP-hard, and model the recruitment process as a sub-modular problem. Finally, an approximation algorithm is designed to guarantee the platform utility and participators' profits. We evaluate our algorithm on simulated data set and the results indicate that the platform utility and data quality improves significantly.

This paper explores the limits of acoustic ranging on smart phone in the scenario of device-free hand tracking. Tracking the hand is challenging since it requires continuously locating the moving hand in the air with fine resolution. Existing work on hand tracking relies on special hardware or requires users hold the mobile device. This paper presents EchoTrack, which continuously locates the hand by leveraging mobile audio hardware advances without special infrastructure supported. EchoTrack measures the distance from the hand to the speaker array embedded in smart phone via the chirp's Time of Flight (TOF). The speaker array and hand yield a unique triangle. The hand can be located with this triangular geometry. The trajectory accuracy can be improved with the method of Doppler shift compensation and trajectory correction (i.e., roughness penalty smoothing method). We implement a prototype on smart phone and the evaluation shows that EchoTrack can achieve tracking accuracy within about three centimeters of 76% and two centimeters of 48%.

Auction based participant selection has been widely used for mobile crowd sensing (MCS) to achieve user incentive and assignment optimization. However, mobile crowd sensing problems solved with auction-based approaches usually involve participants' privacy concerns because a participant's bids may contain her private information (such as location visiting patterns), and disclosure participants' bids may disclose their private information as well. In this paper, we study how to protect such bid privacy in a temporally and spatially dynamic MCS system. We assume that both sensing tasks and mobile participants have dynamic characteristics over spatial and temporal domains. Following the classical VCG auction, we carefully design a scalable grouping based privacy-preserving participant selection scheme, which leverages Lagrange polynomial interpolation to perturb participants' bids within groups. The proposed solution does not affect the operation of current MCS platform. Both theoretical analysis and real-life tracing data simulations verify the efficiency and security of the proposed solution.

In this paper, we address a critical task of dynamically detecting the simultaneous behavior of driving and texting using smartphone as the sensor. We propose, design, and implement TEXIVE which achieves the goal of detecting texting operations during driving utilizing irregularities and rich micro-movements of users. Without relying on any external infrastructures and additional devices, and no need to bring any modification to vehicles, TEXIVE is able to successfully detect dangerous operations with good sensitivity, specificity, and accuracy by leveraging the inertial sensors integrated in regular smartphones. To validate our approach, we conduct extensive experiments involving in a number of volunteers on various of vehicles and smartphones. Our evaluation results show that TEXIVE has a classification accuracy of 87.18%, and precision of 96.67%.

Visible light communication (VLC) has been shown to have several advantages over traditional wireless communication. In this paper, we envision an LED-light-to-smartphone VLC protocol for delivering messages to a group of randomly arriving smartphone receivers. Our goal is to increase the throughput for large message delivery, as well as to reduce the delay of message broadcast. Key challenges for implementing such a VLC message broadcast protocol are: 1) the imperfect synchronization among receivers and the transmitter; 2) the receivers' arbitrary arrival times; and 3) the diversity of receivers' smartphones (e.g., location, capability, and frame-rates). In this paper, we propose a new modulation scheme and design link-layer protocols for improving the network data rate. We carefully design and implement our protocol, Martian, which allows smooth communication from the LED lights to a group of smartphone embedded cameras. Across several phone models, Martian can achieve data rate of about 1.6 kb/s even with NLOS -light. It also has a stable and small delay for broadcasting messages to the randomly arriving receivers.

Visual crowdsensing is successfully applied in numerous application areas, yet little work has been done on measuring and improving the quality of worker contributed visual data. Rather than evaluating the visual quality based on traditional metrics such as resolution, we focus on data diversity, which is crucial for a broad stream of visual crowdsensing tasks. Two representative diversity-oriented task types are studied, namely static object imagery and evolving event photography. The former aims to collect multi-facet/ aspect yet low redundant data about a stationary object, while the latter wants to detect and collect details of key scenes throughout an event. We link these quality needs with data utility and propose a unified visual crowdsensing framework called UtiPay. Data utility is characterized by the macro and micro diversity needs: at the macro level, the pyramid-tree approach is proposed for multi-attribute-based data grouping; at the micro level, we use several strategies for intra-group data selection and worker contribution measurement. To study the impact of our proposed utility measurement approaches, we propose two utility-enhanced payment schemes as incentive mechanisms: Uti and Uti-Bid. Experiments over several user studies with a total of 43 subjects validate the performance of UtiPay for measuring and enhancing the data quality of visual crowdsensing tasks.

Many emerging applications driven the fast development of the device-free localization (DfL) technique, which does not require the target to carry any wireless devices. Most current DfL approaches have two main drawbacks in practical applications. First, as the pre-calibrated received signal strength (RSS) in each location (i.e., radio-map) of a specific area cannot be directly applied to the new areas, the manual calibration for different areas will lead to a high human effort cost. Second, a large number of RSS are needed to accurately localize the targets, thus causes a high communication cost and the areas variety will further exacerbate this problem. This paper proposes FitLoc, a fine-grained and low cost DfL approach that can localize multiple targets over various areas, especially in the outdoor environment and similar furnitured indoor environment. FitLoc unifies the radio-map over various areas through a rigorously designed transfer scheme, thus greatly reduces the human effort cost. Furthermore, benefiting from the compressive sensing theory, FitLoc collects a few RSS and performs a fine-grained localization, thus reduces the communication cost. Theoretical analyses validate the effectivity of the problem formulation and the bound of localization error is provided. Extensive experimental results illustrate the effectiveness and robustness of FitLoc.

Hand tracking systems are becoming increasingly popular as a fundamental HCI approach. The trajectory of moving hand can be estimated through smoothing the position coordinates collected from continuous localization. Therefore, hand localization is a key component of any hand tracking systems. This paper presents EchoLoc, which locates the human hand by leveraging the speaker array in Commercial Off-The-Shelf (COTS) devices (i.e., a smart phone plugged with a stereo speaker). EchoLoc measures the distance from the hand to the speaker array via the Time Of Flight (TOF) of the chirp. The speaker array and hand yield a unique triangle, therefore, the hand can be localized with triangular geometry. We prototype EchoLoc on iOS as an application, and find it is capable of localization with the average resolution within five centimeters of 73% and three centimeters of 48%.

Device-free localization (DfL) techniques, which can localize targets without carrying any wireless devices, have attracting an increasing attentions. Most current DfL approaches, however, have two main drawbacks hindering their practical applications. First, one needs to collect large number of measurements to achieve a high localization accuracy, inevitably causing a high deployment cost, and the areas variety will further exacerbate this problem. Second, as the pre-obtained Received Signal Strength (RSS) from each location (i.e., radio-map) in a specific area cannot be directly applied to new areas for localization, the calibration process of different areas will lead to the high human effort cost. In this paper, we propose, FitLoc, a fine-grained and low cost DfL approach that can localize multiple targets in various areas. By taking advantage of the compressive sensing (CS) theory, FitLoc decreases the deployment cost by collecting only a few of RSS measurements and performs a fine-grained localization. Further, FitLoc employs a rigorously designed transfer scheme to unify the radio-map over various areas, thus greatly reduces the human effort cost. Theoretical analysis about the effectivity of the problem formulation is provided. Extensive experimental results illustrate the effectiveness of FitLoc.

Sleep monitoring system helps to diagnose various health problems. Traditional solutions for sleep monitoring are usually invasive or limited to medical facilities. Radio Frequency (RF) based methods require specialized devices or dedicated wireless sensors. Recently, Wi-Fi based methods without any wearable or dedicated devices obtain more attention, however, they all assume that all the users are in a relatively quiet environment without moving targets. In this paper, we develop a system called Mo-Sleep, which adopts off-the-shelf Wi-Fi devices to continuously collect fine-grained wireless Channel State Information (CSI) in a room. We introduce a motion detection module in our system to identify whether the CSI information has been interfered by a moving target. We then use Principal Component Analysis (PCA) to obtain accurate breath signal. Our prototypic system demonstrates that the proposed scheme can not only remove interfered CSI, but also obtain real time breath rate every five seconds.

With the rapid increasing of smart phones and their embedded sensing technologies, mobile crowd sensing (MCS) becomes an emerging sensing paradigm for performing large-scale sensing tasks. One of the key challenges of large-scale mobile crowd sensing systems is how to effectively select the minimum set of participants from the huge user pool to perform the tasks and achieve certain level of coverage. In this paper, we introduce a new MCS architecture which leverages the cached sensing data to fulfill partial sensing tasks in order to reduce the size of selected participant set. We present a newly designed participant selection algorithm with caching and evaluate it via extensive simulations with a real-world mobile dataset.

Visible light communication (VLC) has been shown to have several advantages over traditional wireless communication. We envision a LED-to-smartphone VLC protocol for delivering messages to a group of unsynchronized mobile device receivers. We carefully design and implement our protocol, Martian, which allows smooth communication from the LED lights to a group of camera-enabled mobile devices. Across several phone models, Martian can achieve data rate of about 1.6kbps even with NLOS-light. Our intensive evaluations indicate that, the data rate reaches 4.2kbps on iPhone 6. This is a significant improvement compared with the 88bps data rate claimed by state-of-art design.

Device-to-device (D2D) is a new paradigm that enhances network performance by offering a wide variety of advantages over traditional cellular networks, e.g., efficient spectral usage and extended network coverage. Efficient data dissemination is indispensable for supporting many D2D applications such as content distribution and location-aware advertisement. In this work, we study the problem of multi-copy data dissemination with probabilistic delay constraint in mobile opportunistic D2D networks. We first formally formulate the problem and introduce a centralized heuristic algorithm which aims to discover a graph for multicasting, in order to meet delay constraint and achieve low communication cost. While the centralized solution can be adapted to a distributed implementation, it is inefficient in a mobile opportunistic D2D network, since it intends to apply a deterministic transmission strategy in a nondeterministic network by delivering all data packets via a predetermined route. Based on such observation, we develop a distributed online algorithm based on the optimal stopping strategy that makes an efficient decision on every transmission opportunity. Extensive simulations under real-world traces and random walk mobility model are carried out to learn the performance trend of the proposed schemes under various network settings.

One of the solutions to improve mobile Delay Tolerant Network (DTN) performance is to place additional stationary nodes, called throwboxes, to create a greater number of contact opportunities. In this paper, we study a key optimization problem in a time-evolving throwbox-assisted DTN: throwbox selection, to answer the questions such as “how many active throwboxes do I need?” and “which throwboxes should be activated?” We formally define two throwbox optimization problems: min-throwbox problem and k-throwbox problem for time-evolving DTNs modeled by weighted space-time graphs. We show that min-throwbox problem is NP-hard and propose a set of greedy algorithms which can efficiently provide quality solutions for both challenging problems.

Recent advances in ambient energy-harvesting wireless sensor networks (WSNs) technologies have made it possible to power the network by energy generated from the environment and thereby increase its lifetime. Various energy sources including light, vibration and heat can be harvested by sensor nodes. However, time-varying energy harvesting also bring new design challenging for WSNs. In this paper, we study a fault-tolerant topology design problem for an energy-harvesting heterogeneous WSN, where multiple supernodes with rich resources are used to improve the performance. We first model the network as a directed and weighted space-time graph in which both spacial and temporal information are preserved. We then define the fault-tolerant topology problem which aims to build a sparser time-varying structure from the original space-time graph while maintaining k-connectivity for the fault-tolerant purpose. Six different algorithms are proposed to solve the problem. Simulation results demonstrate that our proposed methods can save up to around 80% costs.

Mobile opportunistic networks (MONs) are intermittently connected networks, in which a multitude of mobile devices are carried by people and packets are delivered among devices via opportunistic communications. Routing in MONs is very challenging as it must handle network partitioning, long delays, and dynamic topology. Recently, new possibilities of social-based approaches which use social characteristics of mobile nodes to make forwarding decisions become a new trend in MONs. In this paper, we consider the location history with access patterns of a mobile user as its social features as well and propose several new geo-social metrics which reflect the location and social relationships among users. Several new routing algorithms are designed based on these new geo-social metrics to achieve efficient and stable routing in MONs. We evaluate them with a large-scale real-life mobile tracing dateset. Simulation results confirm the effectiveness of proposed geo-social methods.

With the rapid increasing of smart mobile devices and the advances of sensing technologies, mobile crowd sensing (MCS) becomes a new popular sensing paradigm, which enables a variety of large-scale sensing applications. One of the key challenges of large-scale mobile crowd sensing systems is how to effectively select appropriate participants from a huge user pool to perform various sensing tasks while satisfying certain constraints. This becomes more complex when the sensing tasks are dynamic (coming in real time) and heterogeneous (having different temporal and spacial requirements). In this paper, we consider such a dynamic participant recruitment problem with heterogeneous sensing tasks which aims to minimize the sensing cost while maintaining certain level of probabilistic coverage. Both offline and online algorithms are proposed to solve the challenging problem. Extensive simulations over a real-life mobile dataset confirm the efficiency of the proposed algorithms.

Recently a number of systems have been developed to implement and improve the visual communication over screen-camera links. In this paper we study an opposite problem: how to prevent unauthorized users from videotaping a video played on a screen, such as in a theater, while do not affect the viewing experience of legitimate audiences. We propose and develop a light-weight hardware-free system, called Kaleido, that ensures these properties by taking advantage of the limited disparities between the screen-eye channel and the screen-camera channel. Kaleido does not require any extra hardware and is purely based on re-encoding the original video frame into multiple frames used for displaying. We extensively test our system Kaleido using a variety of smartphone cameras. Our experiments confirm that Kaleido preserves the high-quality screen-eye channel while reducing the secondary screen-camera channel quality significantly.

Delay tolerant networks (DTNs) recently have drawn much attention from researchers due to their wide applications in various challenging environments. Previous DTN research mainly concentrates on information propagation and packet delivery. However, with possible participation of a large number of mobile devices, how to maintain efficient and dynamic topology becomes crucial. In this paper, we study the topology design problem in a predictable DTN where the time-evolving topology is known a priori or can be predicted. We model such a time-evolving network as a weighted directed space-time graph which includes both spacial and temporal information. Links inside the space-time graph are unreliable due to either the dynamic nature of wireless communications or the rough prediction of underlying human/device mobility. The purpose of our reliable topology design problem is to build a sparse structure from the original space-time graph such that (1) for any pair of devices, there is a space-time path connecting them with a reliability higher than the required threshold; (2) the total cost of the structure is minimized. Such an optimization problem is NP-hard, thus we propose several heuristics which can significantly reduce the total cost of the topology while maintain the “reliable” connectivity overtime. In this paper, we consider both unicast and broadcast reliability of a topology. Finally, extensive simulations are conducted on random DTNs, a synthetic space DTN, and a real-world DTN tracing data. Results demonstrate the efficiency of the proposed methods.

In mobile social delay tolerant networks, many human-carried mobile devices are moving around in a restricted physical space and occasional contact opportunities among these devices are used to deliver data. Routing design in mobile social delay tolerant networks has been a challenging task due to lack of instantaneous end-to-end paths, large transmission delays, and time-varying network topology. In this paper, aiming to precisely measure the social relationships between mobile nodes, we introduce two kinds of time-varying closeness, direct and indirect closeness, where the temporal constraint is considered. Then we propose both single-copy and multi-copy closeness-based routing schemes, which consider direct and indirect social relationships under temporal constraint. Extensive simulations on real-life data traces show the proposed schemes can achieve better performances than existing DTN routing methods.

Recent advances in Delay Tolerant Networks (DTNs) have overcome limitations in connectivity by relying on intermittent contacts between mobile nodes to deliver packets. However, lack of rich contact opportunities still causes poor delivery ratio and long delay of DTN routing. One of the solutions to improve mobile DTN performance is to place additional stationary nodes, called throwboxes, to create a greater number of contact opportunities. In this paper, we study a key optimization problem in a time-evolving throwbox-assisted DTN: k-throwbox placement problem, to answer "where should I put my k throwboxes to optimize the performance?". We model a time-evolving DTN as a weighted space-time graph which includes both spacial and temporal information. We prove that k-throwbox placement problem is NP-hard and propose a set of greedy algorithms which can efficiently provide quality solutions. One of the proposed algorithms can guarantee an (1 - 1/e) approximation for the k-throwbox placement problem. Simulation results based on random time-evolving DTNs and real life DTN traces demonstrate the efficiency of the proposed methods.

Recent advances in Delay Tolerant Networks (DTNs) allow delivering packets among mobile devices via opportunistic communications during intermittent contacts. However, the lack of rich contact opportunities still causes poor delivery ratio and long delay of DTN routing, especially for large-scale networks. Deployment of additional stationary throwboxes can create a greater number of contact opportunities, thus improve the performance of DTN routing. However, the locations of deployed throwboxes are critical to such improvement. In this paper, we investigate where to deploy throwboxes in a large-scale throwbox-assisted DTN. By leveraging the social properties discovered from real-life tracing data, we propose a set of social-based throwbox placement algorithms which smartly pick the location of each throwbox. Extensive simulations are conducted with a real-life wireless tracing dataset and a wide range of existing DTN routing methods. The results confirm the efficiency of the proposed methods.

Localization is one of the most fundamental problems in ocean sensor networks. Current localization algorithms mainly focus on how to localize as many sensors as possible given a set of mobile or static anchor nodes and distance measurements. In this paper, we consider the optimization problem, minimum cost localization problem in a 3D ocean sensor network, which aims to localize all underwater sensors using the minimum number of anchor nodes or the minimum travel distance of the ship which deploys and measures the anchors. Given the hardness of 3D localization, we propose a set of greedy methods to pick the anchor set and its visiting sequence. Aiming to minimize the localization errors, we also adopt a confidence-based approach for all proposed methods to deal with noisy ranging measurements and possible flip ambiguity. Our simulation results demonstrate the efficiency of all proposed methods.

We study how to achieve optimal network capacity in the most energy-efficient manner over a general large-scale wireless network, say, a multi-hop multi-radio multi-channel (MR-MC) network. We develop a multi-objective optimization framework for computing the resource allocation that leads to optimal network capacity with minimal energy consumption. Our framework is based on a linear programming multi-commodity flow (MCF) formulation augmented with scheduling constraints over multi-dimensional conflict graph (MDCG). The optimization problem however involves finding all independent sets (ISs), which is NP-hard in general. Novel delayed column generation (DCG) based algorithms are developed to effectively solve the optimization problem. The DCG-based algorithms have significant advantages of low computation overhead and achieving high energy efficiency, compared to the common heuristic algorithm that randomly searches a large number of ISs to use. Extensive numerical results demonstrate the energy efficiency improvement by the proposed energy-efficient optimization techniques, over a wide range of networking scenarios.

The smart grid introduces new privacy implications to individuals and their family due to the fine-grained usage data collection. For example, smart metering data could reveal highly accurate real-time home appliance energy load, which may be used to infer the human activities inside the houses. One effective way to hide actual appliance loads from the outsiders is Battery-based Load Hiding (BLH), in which a battery is installed for each household and smartly controlled to store and supply power to the appliances. Even though such technique has been demonstrated useful and can prevent certain types of attacks, none of existing BLH works can provide probably privacy-preserving mechanisms. In this paper, we investigate the privacy of smart meters via differential privacy. We first analyze the current existing BLH methods and show that they cannot guarantee differential privacy in the BLH problem. We then propose a novel randomized BLH algorithm which successfully assures differential privacy, and further propose the Multitasking-BLH-Exp3 algorithm which adaptively updates the BLH algorithm based on the context and the constraints. Results from extensive simulations show the efficiency and effectiveness of the proposed method over existing BLH methods.

With the increased popularity of smartphones, various security threats and privacy leakages targeting them are discovered and investigated. In this work, we present SilentSense, a framework to authenticate users silently and transparently by exploiting dynamics mined from the user touch behavior biometrics and the micro-movement of the device caused by user's screen-touch actions. We build a “touch-based biometrics” model of the owner by extracting some principle features, and then verify whether the current user is the owner or guest/attacker. When using the smartphone, some unique operating dynamics of the user is detected and learnt by collecting the sensor data and touch events silently. When users are mobile, the micro-movement of mobile devices caused by touch is suppressed by that due to the large scale user-movement which will render the touch-based biometrics ineffective. To address this, we integrate a movement-based biometrics for each user with previous touch-based biometrics. We conduct extensive evaluations of our approaches on the Android smartphone, we show that the user identification accuracy is over 99%.

In Vehicular Ad Hoc Networks (VANETs), moving vehicles are considered as mobile nodes in the network and they are connected to each other via wireless links when they are within the communication radius of each other. Efficient message delivery in VANETs is still a very challenging research issue. In this paper, a Q-learning based routing protocol (i.e., QGrid) is introduced to help to improve the message delivery from mobile vehicles to a specific location. QGrid considers both macroscopic and microscopic aspects when making the routing decision, while the traditional routing methods focus on computing meeting information between different vehicles. QGrid divides the region into different grids. The macroscopic aspect determines the optimal next-hop grid and the microscopic aspect determines the specific vehicle in the optimal next-hop grid to be selected as next-hop vehicle. QGrid computes the Q-values of different movements between neighboring grids for a given destination via Q-learning. Each vehicle stores Q-value table learned offline, then selects optimal next-hop grid by querying Q-value table. Inside the selected next-hop grid, we either greedily select the nearest neighboring vehicle to the destination or select the neighboring vehicle with highest probability of moving to the optimal next-hop grid predicted by the two-order Markov chain. The performance of QGrid is evaluated by using real life trajectory GPS data of Shanghai taxies. Simulation comparison among QGrid and other existing position-based routing protocols confirms the advantages of proposed QGrid routing protocol for VANETs.

Delay Tolerant Networks (DTNs) are intermittently connected networks, such as mobile social networks formed by human-carried mobile devices. Routing in such mobile social DTNs is very challenging as it must handle network partitioning, long delays, and dynamic topology. Recently, social-based approaches, which attempt to exploit social behaviors of DTN nodes to make better routing decision, have drawn tremendous interests in DTN routing design. In this paper, we propose a novel social-based routing approach for mobile social DTNs, where a new metric social energy is introduced to quantify the ability of a node to forward packets to others, inspired by general laws in particle physics. Social energy is generated via node encounters and shared by the communities of encountering nodes. Similar to the radiation of energy in physics, the social energy of any node decays over time. Our proposed Social Energy Based Routing (SEBAR) protocol considers social energy of encountering nodes and is in favor of the Dode with a higher social energy in its or the destination's social community. Our simulations with real-life wireless traces demonstrate the efficiency and effectiveness of SEBAR method by comparing It with several existing DTN routing schemes.

It is our great pleasure to welcome you to the 32nd IEEE International Performance, Computing, and Communications Conference (IPCCC 2013) on December 6 – 8, 2013 at Coronado Island Marriott Resort & Spa, San Diego, California. IPCCC is a premier venue of IEEE Computer Society for researchers from academia, government, and industry to present, explore and discuss latest research advances in the performance of computer and communication systems.

Recent advances in ambient energy-harvesting technologies have made it possible to power wireless sensor networks (WSNs) from the environment for long durations. However, the energy availability in an energy-harvesting WSN varies with time and thus may cause the network topology to evolve over time. In this paper, we study the topology design problem in a time-evolving and energy-harvesting WSN where the time-evolving topology and dynamic energy cost are known a priori or can be predicted. We model such a network as a node-weighted space-time graph which includes both spacial and temporal information. To reduce the cost of supporting time-evolving networks with limited harvesting energy sources, we propose a new efficient topology design problem which aims to put more sensors into sleep while still maintaining the network connectivity over time. We prove that the optimization problem of finding the optimal awake sensor set with the minimum total cost is NP-hard. Thus, we propose several topology design algorithms which can significantly reduce the total cost of topology while maintaining the connectivity over time. Simulation results from random time-evolving and energy-harvesting WSNs demonstrate the efficiency of the proposed methods.

In this work, we address a critical task of detecting the user behavior of driving and texting simultaneously using smartphones. We propose, design, and implement TEXIVE which achieves the goal of distinguishing drivers and passengers, and detecting texting operations during driving utilizing irregularities and rich micro-movements of users. Without relying on any external infrastructures and additional devices, and no need to bring any modification to vehicles, TEXIVE is able to successfully detect dangerous operations with good sensitivity, specificity and accuracy. We conduct experimental study of TEXIVE with the help of a number of volunteers using various vehicles and smartphones. Our results indicate that TEXIVE has a classification accuracy of 87.18%, and precision of 96.67%.

In this work, we present SilentSense, a framework to authenticate users silently and transparently by exploiting the user touch behavior biometrics and leveraging the integrated sensors to capture the micro-movement of the device caused by user's screen-touch actions. By tracking the fine-detailed touch actions of the user, we build a "touch-based biometrics" model of the owner by extracting some principle features, and then verify whether the current user is the owner or guest/attacker. When using the smartphone, the unique operating pattern of the user is detected and learnt by collecting the sensor data and touch events silently. When users are mobile, the micro-movement of mobile devices caused by touch is suppressed by that due to the large scale user-movement which will render the touch-based biometrics ineffective. To address this, we integrate a movement-based biometrics for each user with previous touch-based biometrics. We conduct extensive evaluations of our approaches on the Android smartphone, we show that the user identification accuracy is over 99%.

Information propagation in delay tolerant networks (DTN) is difficult due to the lack of continues connectivity. Most of previous work put their focus on the information propagation in static network. In this work, we examine two closely related problems on information propagation in predicable DTN. In particular, we assume that during a certain time period, the interacting process among nodes is known a priori or can be predicted. The first problem is to select a set of initial source nodes, subject to budget constraint, in order to maximize the total weight of nodes that receive the information at the final stage. This problem is well-known influence maximization problem which has been extensively studied for static networks. The second problem we want to study is minimum cost initial set problem, in this problem, we aim to select a set of source nodes with minimum cost such that all the other nodes can receive the information with high probability. We conduct extensive experiments using $10,000$ users from real contact trace.

Shortest path routing protocol intends to minimize the total delay between every pair of destination node and source node. However, it is also well-known that shortest path routing suffers from uneven distribution of traffic load, especially in dense wireless networks. Recently, several new routing protocols are proposed in order to balance traffic load among nodes in a network. One of them is circular sailing routing(CSR) [1], [2] which maps nodes on the surface of a sphere and select routes based on surface distances. CSR has been demonstrated with better load balance than shortest path routing via simulations. However, it is still open that what load distribution CSR can achieve. Therefore, in this paper, we theoretically analyze the traffic load distribution of CSR in a dense circular wireless network. Using the techniques developed by Hyytia and Virtamo [3], we are able to derive the traffic load of any point inside the network. We then conduct extensive simulations to verify our theoretical results with grid and random networks.

In delay tolerant networks (DTNs), the lack of continuous connectivity, network partitioning, and long delays make design of network protocols very challenging. Previous DTN research mainly focuses on routing and information propagation. However, with a large number of wireless devices' participation, it becomes crucial regarding how to maintain efficient and dynamic topology of the DTN. In this paper, we study the topology control problem in a predictable DTN, where the time-evolving network topology is known a priori or can be predicted. We first model such time-evolving network as a directed space-time graph that includes both spacial and temporal information. The aim of topology control is to build a sparse structure from the original space-time graph such that 1) the network is still connected over time and supports DTN routing between any two nodes; 2) the total cost of the structure is minimized. We prove that this problem is NP-hard, and propose two greedy-based methods that can significantly reduce the total cost of topology while maintaining the connectivity over time. We also introduce another version of the topology control problem by requiring that the least cost path for any two nodes in this constructed structure is still cost-efficient compared with the one in the original graph. Two greedy-based methods are provided for such a problem. Simulations have been conducted on both random DTN networks and real-world DTN tracing data. Results demonstrate the efficiency of the proposed methods.

With possible participation of a large number of wireless devices in delay tolerant networks (DTNs), how to maintain efficient and dynamic topology becomes crucial. In this paper, we study the topology design problem in a predictable DTN where the time-evolving network topology is known a priori or can be predicted. We model such network as a weighted space-time graph with both spacial and temporal information. Links inside the space-time graph are unreliable due to either the dynamic nature of wireless communications or the rough prediction of underlying human/device mobility. The aim of our topology design problem is to build a sparse space-time structure such that (1) for any pair of devices, there is a space-time path connecting them with the reliability larger than a required threshold; (2) the total cost of the structure is minimized. We first show that this problem is NP-hard, and then propose several heuristics which can significantly reduce the total cost of the topology while maintain the “reliable” connectivity over time.

Mobile Opportunistic Networks (MONs) are intermittently connected networks, such as pocket switched networks formed by human-carried mobile devices. Routing in MONs is very challenging as it must handle network partitioning, long delays, and dynamic topology. Flooding is a possible solution but with high costs. Most existing routing methods for MONs avoid the costly flooding by selecting one or multiple relays to deliver data during each encounter. How to pick the “good” relay from all encounters is a non-trivial task. To achieve efficient delivery of messages at low costs, in this paper, we propose a new group-based routing protocol in which the relay node is selected based on social group information obtained from historical encounters. We apply a simple formation method to build multi-level social groups, which summarizes the wide range of social relationships among all mobile participants. Our simulations demonstrate the efficiency and effectiveness of the proposed method by comparing it with several existing MON routing schemes.

Cooperative communication (CC) allows multiple nodes to simultaneously transmit the same packet to the receiver so that the combined signal at the receiver can be correctly decoded. Since the cooperative communication can reduce the transmission power and extend the transmission coverage, it has been considered in minimum energy routing protocols to reduce the total energy consumption. However, previous research on cooperative routing only focuses on minimizing the total energy consumption from the source node to the destination node, which may lead to the unbalanced energy distribution among nodes. In this paper, we aim to study the impact of cooperative routing on balancing the energy distribution among nodes. By introducing a new routing scheme which carefully selects cooperative relay nodes and assigns their transmission power, our cooperative routing method can balance the energy among neighboring nodes and maximize the remaining lifetime of the network. Simulation results demonstrate that the proposed cooperative routing algorithm significantly balances the energy distribution and prolongs the lifetime of the network.

Location privacy has been a serious concern for mobile users who use location-based services provided by the third-party provider via mobile networks. Recently, there have been tremendous efforts on developing new anonymity or obfuscation techniques to protect location privacy of mobile users. Though effective in certain scenarios, these existing techniques usually assume that a user has a constant privacy requirement along spatial and/or temporal dimensions, which may not be true in real-life scenarios. In this paper, we introduce a new location privacy problem: Location-aware Location Privacy Protection (L2P2) problem, where users can define dynamic and diverse privacy requirements for different locations. The goal of the L2P2 problem is to find the smallest cloaking area for each location request so that diverse privacy requirements over spatial and/or temporal dimensions are satisfied for each user. In this paper, we formalize two versions of the L2P2 problem, and propose several efficient heuristics to provide such location-aware location privacy protection for mobile users. Through multiple simulations on a large data set of trajectories for one thousand mobile users, we confirm the effectiveness and efficiency of the proposed L2P2 algorithms.

Mobile devices in delay tolerant networks (DTNs) are used and carried by people, whose behaviors could be described by social models. Understanding social behaviors and characteristics of mobile users can greatly help the routing decision in DTN routing protocols. However, to obtain the stable and accurate social characteristics in dynamic DTNs is very challenging. To achieve efficient delivery of messages at low costs, in this paper, we propose a novel enhanced social group-based routing protocol in which the relay node is selected based on multi-level cross-community social group information. We apply a simple group formation method with both historical encounters (social relationships in physical world)and social features of mobile users (social relationships in social world) and build multi-level cross-community social groups, which summarize the wide range of social relationships among all mobile participants. Our simulations over a real-life data set demonstrate the efficiency and effectiveness of the proposed method by comparing it with several existing DTN routing schemes.

Well known "hole" problem is hardly avoided in wireless sensor networks because of various actual geographical environments. Existing geographic routing protocols (such as GFG [1] and GPSR [2]) use perimeter routing strategies to find a detour path around the boundary of holes when they encounter the "local minimum" during greedy forwarding. However, this solution may lead to uneven energy consumption around the holes since it consumes more energy of the boundary sensors. It becomes more serious when holes appear in most of routing paths in a large scale sensor network. In this paper, we propose a novel distributed strategy to balance the traffic load on the boundary of holes by virtually changing the sizes of these holes. The proposed mechanism dynamically controls holes to expand and shrink circularly without changing the underlying forwarding strategy. Therefore, it can be applied to most of the existing geographic routing protocols which detour around holes. Simulation results show that our new strategy can effectively balance the load around holes thus prolong the network life of sensor networks when using with GPSR.

Efficient data delivery in vehicular ad hoc networks (VANETs) is still a challenging research issue. Position-based routing protocols have been proven to be more suitable for dynamic VANETs than traditional ad hoc routing protocols. However, position-based routing assumes that intermediate nodes can always be found to setup an end-to-end connection between the source and the destination, otherwise, it suffers from network partitions which are very common in VANETs and leads to poor performances. This paper addresses data delivery challenge in the possible disconnected VANETs by combining position-based forwarding strategy with store-carry-forward routing scheme from delay tolerant networks. The proposed routing method makes use of vehicle driving direction to determine whether holding or forwarding the packet. Experimental results show that the proposed mechanism outperforms existing position-based solutions in terms of packet delivery ratio.

ABSTRACT Privacy issues have been a serious concern for 802.11 Wireless LAN users. Prior research on privacy issues usually focuses on pseudonym techniques, where the unique, consistent explicit identifiers such as MAC addresses from the users can be frequently changed, and thus it is challenging to track users through those always changing identifiers. However, recent research done by Pang et al. (Pang et al. Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, 1997; 99–110) has demonstrated that pseudonyms are not adequate to protect user privacy. The key idea of Pang et al.'s method is to locate implicit identifiers (e.g., IP addresses and port numbers a user frequently visits), build user behavior patterns based on these implicit identifiers, and then apply classification techniques to identify users. In this paper, we first propose a new 802.11 user identification approach through enhanced feature selection and generation for building more accurate user behavior patterns. Our simulation results on 9.27 GB SIGCOMM 2004 wireless data sets demonstrate that our method can achieve better classification rates compared with Pang et al.'s method. Then, we further study how to provide user anonymity, even if implicit identifiers based identification is applied, by introducing a set of 802.11 user anonymization approaches based on bogus traffic injection. We propose eight different methods to artificially generate bogus data and inject them into original traffic, and thus users' behavior patterns are disturbed. Our simulation results on the same SIGCOMM 2004 data sets demonstrate that our anonymization methods can efficiently decrease user identification rates and hence improve user anonymity. Copyright © 2011 John Wiley & Sons, Ltd.

Data collection is a fundamental function provided by wireless sensor networks. How to efficiently collect sensing data from all sensor nodes is critical to the performance of sensor networks. In this paper, we aim to understand the theoretical limits of data collection in a TDMA-based sensor network in terms of possible and achievable maximum capacity. Previously, the study of data collection capacity has concentrated on large-scale random networks. However, in most of the practical sensor applications, the sensor network is not uniformly deployed and the number of sensors may not be as huge as in theory. Therefore, it is necessary to study the capacity of data collection in an arbitrary network. In this paper, we first derive the upper and lower bounds for data collection capacity in arbitrary networks under protocol interference and disk graph models. We show that a simple BFS tree-based method can lead to order-optimal performance for any arbitrary sensor networks. We then study the capacity bounds of data collection under a general graph model, where two nearby nodes may be unable to communicate due to barriers or path fading, and discuss performance implications. Finally, we provide discussions on the design of data collection under a physical interference model or a Gaussian channel model.

Cooperative communication (CC) exploits space diversity through allowing multiple nodes cooperatively relay signals to the receiver so that the combined signal at the receiver can be correctly decoded. Since CC can reduce the transmission power and extend the transmission coverage, it has been considered in topology control protocols [1], [2]. However, prior research on topology control with CC only focuses on maintaining the network connectivity, minimizing the transmission power of each node, whereas ignores the energy efficiency of paths in constructed topologies. This may cause inefficient routes and hurt the overall network performance in cooperative ad hoc networks. In this paper, to address this problem, we introduce a new topology control problem: energy-efficient topology control problem with cooperative communication, and propose two topology control algorithms to build cooperative energy spanners in which the energy efficiency of individual paths are guaranteed. Both proposed algorithms can be performed in distributed and localized fashion while maintaining the globally efficient paths. Simulation results confirm the nice performance of all proposed algorithms.

Cooperative communication (CC) allows multiple nodes to simultaneously transmit the same packet to the receiver so that the combined signal at the receiver can be correctly decoded. Since CC can reduce the transmission power and extend the transmission coverage, it has been considered in topology control protocols. However, prior research on topology control with CC only focuses on maintaining the network connectivity, minimizing the transmission power of each node, whereas ignores the energy-efficiency of paths in constructed topologies. This may cause inefficient routes and hurt the overall network performance. In this paper, to address this problem, we introduce a new topology control problem: energy-efficient topology control problem with cooperative communication, and propose two topology control algorithms to build cooperative energy spanners in which the energy efficiency of individual paths are guaranteed. Simulation results confirm the nice performance of the proposed algorithms.

In delay tolerant networks (DTNs), the lack of continuous connectivity, network partitioning, and long delays make design of network protocols very challenging. Previous DTN research mainly focuses on routing and information propagation. However, with large number of wireless devices' participation, how to maintain efficient and dynamic topology of the DTN becomes crucial. In this paper, we study the topology control problem in a predictable DTN where the time-evolving network topology is known a priori or can be predicted. We first model such time-evolving network as a directed space-time graph which includes both spacial and temporal information. The aim of topology control is to build a sparse structure from the original space-time graph such that (1) the network is still connected over time and supports DTN routing between any two nodes; (2) the total cost of the structure is minimized. We prove that this problem is NP-hard, and then propose two greedy-based methods which can significant reduce the total cost of topology while maintain the connectivity over time. Finally, we illustrate how the proposed methods can work for undirected DTNs. Simulations have been conducted on both random DTN networks and real-world DTN tracing data. Results demonstrate the efficiency of the proposed topology control methods.

Three dimensional (3D) wireless sensor networks have attracted a lot of attention due to its great potential usages in both commercial and civilian applications. Topology control in 3D sensor networks has been studied recently. Different 3D geometric topologies were proposed to be the underlying network topologies to achieve the sparseness of the communication networks. However, most of the proposed 3D topologies cannot bound the node degree, i.e., some nodes may need to maintain large number of neighbors in the constructed topologies, which is not energy efficient and may lead to large interference. In this paper, we extend several existing 3D topologies to a set of new 3D topologies with bounded node degree. We provide theoretical analysis on their power efficiency and node degree and also simulation evaluations over random 3D sensor networks. The simulation results confirm nice performance of these proposed 3D topologies.

Processing the gathered information efficiently is a key functionality for wireless sensor networks. In this paper, we study the time complexity, message complexity (number of messages used by all nodes), and energy cost complexity (total energy used by all nodes for transmitting messages) of some tasks, such as data collection (collecting raw data of all nodes to a sink), data aggregation (computing the aggregated value of data of all nodes), and queries for a multihop wireless sensor network of n nodes. We first present a lower bound on the complexity for the optimal methods, and then, for most of the tasks studied in this paper, we provide an (asymptotically matching) upper bound on the complexity by presenting efficient distributed algorithms to solve these problems.

A number of energy-aware routing protocols were proposed to seek the energy efficiency of routes in multihop wireless networks. Among them, several geographical localized routing protocols were proposed to help making smarter routing decision using only local information and reduce the routing overhead. However, all proposed localized routing methods cannot guarantee the energy efficiency of their routes. In this paper, we first give a simple localized routing algorithm, called Localized Energy-Aware Restricted Neighborhood routing (LEARN), which can guarantee the energy efficiency of its route if it can find the route successfully. We then theoretically study its critical transmission radius in random networks which can guarantee that LEARN routing finds a route for any source and destination pairs asymptotically almost surely. We also extend the proposed routing into three-dimensional (3D) networks and derive its critical transmission radius in 3D random networks. Simulation results confirm our theoretical analysis of LEARN routing and demonstrate its energy efficiency in large scale random networks.

In this paper, we study the cost efficient topology design (CETD) problem in a predictable delay tolerant networks (DTN) where the time-evolving network topology is known a priori or can be predicted. We model such time-evolving network as a weighted space-time graph which includes both spacial and temporal information. The aim of CETD is to build a sparse structure from the original space-time graph such that (1) the network is still connected over time between any two nodes, (2) the cost of the least cost path for any two nodes in this constructed structure is at most δ times of that in the original graph, i.e., cost efficient DTN routing is possible between any two nodes; and (3) the total cost of the structure is minimized. We first show that classic topology control methods for static graph do not work for this new problem and then propose three efficient topology control methods which can significantly reduce the total cost of topology while maintain the connectivity and cost-efficiency over time. Extensive simulations have been conducted on random DTN networks and results demonstrate the efficiency of the proposed methods.

Privacy issues have been a serious concern for 802.11 Wireless LAN users. As demonstrated by Pang et al. and Xu et al., applying pseudonym techniques does not completely protect users' privacy. In particular, users' identities can be disclosed through implicit identifiers such as the IP addresses and port numbers users often access. In this paper, we study how to improve user anonymity even if implicit identifiers based identification is applied. The basic idea of our approach is to artificially generate bogus data and inject them into original traffic, and thus users' behavior patterns are disturbed. Specifically, we propose eight different methods to generate bogus data, where each of them applies different algorithms and metrics to generate bogus packets. Our simulation results with SIGCOMM 2004 wireless trace demonstrate that our anonymization methods can decrease user identification rates, and hence improve user anonymity.

How to efficiently collect sensing data from all sensor nodes is critical to the performance of wireless sensor networks. In this paper, we aim to understand the theoretical limitations of data collection in terms of possible and achievable maximum capacity. Previously, the study of data collection capacity has only concentrated on large-scale random networks. However, in most of practical sensor applications, the sensor network is not deployed uniformly and the number of sensors may not be as huge as in theory. Therefore, it is necessary to study the capacity of data collection in an arbitrary network. In this paper, we derive the upper and constructive lower bounds for data collection capacity in arbitrary networks. The proposed data collection method can lead to order-optimal performance for any arbitrary sensor networks. We also examine the design of data collection under a general graph model and discuss performance implications.

Localization is a fundamental problem in wireless sensor networks. Current localization algorithms mainly focus on checking the localizability of a network and/or how to localize as many nodes as possible given a static set of anchor nodes and distance measurements. In this paper, we study a new optimization problem, minimum cost localization problem, which aims to localize all sensors in a network using the minimum number (or total cost) of anchor nodes given the distance measurements. We show this problem is very challenging and then present a set of greedy algorithms using both trilateration and local sweep operations to address the problem. Extensive simulations have been conducted and demonstrate the efficiency of our algorithms.

The wireless multihop to an access point model appears to be a promising component of future network architectures, including multihop cellular networks and wireless access networks at the edges of mesh networks. Sophisticated software radios and core network protocols are being developed to support the integration of heterogeneous air interfaces within these access networks. A key challenge is managing diverse resources at access points (e.g., 3G, WiFi or WiMax) while discovering efficient multi-hop paths from a source to an access point based on selection criteria specified by various applications or necessitated by network resource constraints. We propose a new routing protocol that integrates multiple metrics to calculate path cost based on diverse selection criteria. In addition, a hybrid proactive/reactive anycast routing paradigm is applied to guide the discovery of an access point among multiple available access points. The result is an integrated, flexible protocol for route discovery and access point discovery. Simulation analysis shows that our approach outperforms single-metric routing protocols while supporting flexible service criteria, including load balancing at access points.

Data collection is one of the most important functions provided by wireless sensor networks. Here, we study the theoretical limitations of data collection and data aggregation in terms of delay and capacity for a wireless sensor network where n sensors are randomly deployed. We consider two different communication scenarios (with or without aggregation) under physical interference model. For each scenario, we first propose a new collection method and analyze its performance in terms of delay and capacity, then theoretically prove that our method can achieve the optimal order. Particularly, the capacity of data collection is in order of Θ(W) where W is the fixed data-rate on individual links. If each sensor can aggregate its receiving packets into a single packet to send, the capacity of data collection increases to Θ((n/log n) W).

To provide user privacy, several anonymization techniques (e.g., pseudonyms applied to MAC addresses) have been proposed in 802.11 networks. However, recent research done by Pang et al. has demonstrated that pseudonyms are not adequate to protect user privacy. The key idea of Pang et al.'s method is to locate implicit identifiers (e.g., IP addresses and port numbers a user frequently visits), build user profiles based on these implicit identifiers in the training data sets, and then apply classification techniques to identify unlabeled (testing) users. Our method proposed in this paper partly focuses on building user profiles. Compared with the method proposed by Pang et al. in, we propose a novel approach to selecting and generating features, which is critical to build user profiles. The feature selection and generation procedure can be dynamically controlled through setting a few important parameters. We did a series of simulations using 9.27 GB SIGCOMM 2004 wireless data sets, and our simulation results demonstrate better classification rates compared with Pang et al.'s method.

Data collection is one of the most important functions provided by wireless sensor networks. In this paper, we study theoretical limitations of data collection and data aggregation in terms of delay and capacity for a wireless sensor network where n sensors are randomly deployed. We consider different communication scenarios (single sink or multiple sinks, regularly-deployed or randomly-deployed sinks, with or without aggregation) under protocol interference model. For each scenario, we first propose a new collection/aggregation method and analyze its performance in terms of delay and capacity, then theoretically prove that our method can achieve the optimal order (i.e., its performance is within a constant factor of the optimal). Particularly, with a single sink, the capacity of data collection is in order of Theta(W) where W is the fixed data-rate on individual links. With k sinks, the capacity of data collection is increased to Theta(kW) when k=O(n/log n) or Theta(n/log n) when k=Omega(n/log n). If each sensor can aggregate its receiving packets into a single packet to send, the capacity of data collection with a single sink is also increased to Theta(n/log nW).

Topology control protocol aims to efficiently adjust the network topology of wireless networks in a self-adaptive fashion to improve the performance and scalability of networks. This is especially essential to large-scale multihop wireless networks (e.g., wireless sensor networks). Fault-tolerant topology control has been studied recently. In order to achieve both sparseness (i.e., the number of links is linear with the number of nodes) and fault tolerance (i.e., can survive certain level of node/link failures), different geometric topologies were proposed and used as the underlying network topologies for wireless networks. However, most of the existing topology control algorithms can only be applied to two-dimensional (2D) networks where all nodes are distributed in a 2D plane. In practice, wireless networks may be deployed in three-dimensional (3D) space, such as under water wireless sensor networks in ocean or mobile ad hoc networks among space shuttles in space. This article seeks to investigate self-organizing fault-tolerant topology control protocols for large-scale 3D wireless networks. Our new protocols not only guarantee k -connectivity of the network, but also ensure the bounded node degree and constant power stretch factor even under k −1 node failures. All of our proposed protocols are localized algorithms, which only use one-hop neighbor information and constant messages with small time complexity. Thus, it is easy to update the topology efficiently and self-adaptively for large-scale dynamic networks. Our simulation confirms our theoretical proofs for all proposed 3D topologies.

Energy efficient routing and power control techniques in wireless ad hoc networks have drawn considerable research interests recently. In this paper, we address the problem of energy efficient reliable routing for wireless ad hoc networks in the presence of unreliable communication links or devices or lossy wireless link layers by integrating the power control techniques into the energy efficient routing. We consider both the case when the link layer implements a perfect reliability and the case when the reliability is implemented through the transport layer, e.g., TCP. We study the energy efficient unicast and multicast when the links are unreliable. Subsequently, we study how to perform power control (thus, controlling the reliability of each communication link) such that the unicast routings use the least power when the communication links are unreliable, while the power used by multicast is close to optimum. Extensive simulations have been conducted to study the power consumption, the end-to-end delay, and the network throughput of our proposed protocols compared with existing protocols.

The calculation of path cost is a critical component of route discovery for network routing. The criteria used to represent path cost guides resource consumption in the network. In this paper, we describe our approach, a set of protocols based on our Multiple Metrics Routing Protocol (MMRP) for integrating hop count, energy consumption, and traffic load into the path cost calculation for ad hoc or multihop-cellular networks. Our initial aim is to select among multiple disjoint routes in order to maintain a low path cost, in terms of energy consumption and delay, without depleting resources at popular intermediate nodes. One extension of MMRP removes the constraint that only disjoint paths are considered and enables discovery of more optimal routes. A second extension includes adaptive adjustment of cost metrics to support device classification (e.g., energy capacity, bandwidth) in heterogeneous networks. We illustrate our approach with a simple example, followed by extensive simulation analysis. Results indicate that proper combination of multiple metrics for calculating path costs results in improved performance and lower overall system resource consumption as compared to AODV or energy efficient routing protocols.

Although most existing wireless systems and protocols are based on two-dimensional design, in reality, a variety of networks operate in three-dimensions. The design of protocols for 3D networks is surprisingly more difficult than the design of those for 2D networks. In this paper, we investigate how to design load balancing routing for 3D networks. Most current wireless routing protocols are based on Shortest Path Routing (SPR), where packets are delivered along the shortest route from a source to a destination. However, under uniform communication, shortest path routing suffers from uneven load distribution in the network, such as crowed center effect where the center nodes have more load than the nodes in the periphery. Aim to balance the load, we propose a novel 3D routing method, called 3D Circular Sailing Routing (CSR), which maps the 3D network onto a sphere and routes the packets based on the spherical distance on the sphere. We describe two mapping methods for CSR and then provide theoretical proofs of their competitiveness compared to SPR. For both proposed methods, we conduct simulations to study their performance in grid and random networks.

Routing in wireless networks has been heavily studied in the last decade and numerous routing protocols were proposed in literature. Most of the existing routing protocols are based on shortest path routing. Shortest path routing enjoys minimizing the total delay, but may lead uneven distribution of traffic load in a network. For example, wireless nodes in the center of a network usually have heavier traffic load since most of the shortest routes go through the center. To solve this problem, Popa et al. (2007) recently proposed a novel routing method, called curveball routing (CBR), which can balance the traffic load and vanish the crowded center effect. In CBR, nodes are mapped on a sphere and packets are routed on those virtual coordinates on the sphere. While CBR achieves better load balancing for the network, it also uses longer routes than the shortest paths. This can be treated as the cost of load balancing. In this paper, we focus on studying this cost of load balancing for curveball routing. Specifically, we theoretically prove that for any network, the distance traveled by the packets using CBR is no more than a small constant factor of the minimum (the distance of the shortest path). The constant factor, we called stretch factor, is only depended on the ratio between the size of the network and the radius of the sphere used in CBR. We then conduct extensive simulations to evaluate the stretch factor and load distribution of CBR and compare them with the shortest path routing in both grid and random networks. We also study the trade-off between stretch factor and load balancing.

In this paper, we investigate secure intra and inter group information sharing in a network consisting of multiple node groups. We develop a mechanism for the establishment and maintenance of multicast structures, which enables flexible topology changes and efficient information distribution. We develop a key distribution and update method for secure information sharing in the same group and among different groups. It adopts polynomials to support the distribution of personal key shares and employs LKH (logical key hierarchy) to achieve efficient key refreshment. We also investigate the overhead and safety of the proposed mechanism and demonstrate its advantages over previous approaches.

The wireless multihop to an access point model appears to be a promising component of future network architectures, including multihop cellular networks and wireless access networks at the edges of mesh networks. Sophisticated software radios and core network protocols are being developed to support the integration of heterogeneous access networks. A challenge is managing diverse resources at access points (e.g., 3G, WiFi or WiMax), as well as the distributed interference among the mobiles within a heterogeneous access network. We propose the use of a new anycasting protocol to guide access point discovery and path selection for balancing access point resource and routing packets to access points (APs). In addition, a hybrid proactive/reactive approach is used to reduce overhead of AP discovery. We use theoretical analysis and extensive simulations, to study the tradeoff of our hybrid anycasting protocol. The simulation study indicates that the use of the hybrid anycasting protocol for AP discovery, load balancing and routing, results in consistent performance improvements.

Fault tolerant topology control in wireless networks has been studied recently. In order to achieve both sparseness (i.e., the number of links is linear with the number of nodes) and fault tolerance (i.e., can survive certain level of node/link failures), different geometric topologies were proposed and used as the underlying network topologies for wireless networks. However, most of the existing topology control algorithms can only be applied to 2-dimensional (2D) networks where all nodes are distributed in a 2D plane. In practice, wireless networks may be deployed in 3-dimensional (3D) space, such as underwater wireless sensor networks in ocean or ad hoc networks in space. This paper seeks to investigate efficient fault tolerant topology control protocols for 3D wireless networks. Our new protocols not only guarantee the kappa-connectivity of the network, but also ensure the bounded node degree and constant power stretch factor. All of our proposed protocols are localized algorithms, which only use one-hop neighbor information and constant messages with small time complexity. Our simulation confirms our theoretical proofs for all proposed 3D topologies.

Routing in wireless networks has been heavily studied in the last decade and numerous routing protocols were proposed in literature. The packets usually follow the shortest paths between sources and destinations in routing protocols to achieve smallest traveled distance. However, this leads to the uneven distribution of traffic load in a network. For example, wireless nodes in the center of the network will have heavier traffic since most of the shortest routes go through them. In this paper, we first describe a novel routing method, called circular sailing routing (CSR), which can distribute the traffic more evenly in the network. The proposed method first maps the network onto a sphere via a simple stereographic projection, and then the route decision is made by the distance on the sphere instead of the Euclidean distance in the plane. We theoretically prove that for a network the distance traveled by the packets using CSR is no more than a small constant factor of the minimum (the distance of the shortest path). We then extend CSR to a localized version, Localized CSR, by modifying the greedy routing without any additional communication overhead. Finally, we further propose CSR protocols for 3D networks where nodes are distributed in a 3D space instead of a 2D plane. For all proposed methods, we conduct simulations to study their performances and compare them with global shortest path routing or greedy routing.

To preserve network connectivity is an important issue especially in wireless sensor network, where wireless links are easy to be disturbed and tiny sensors are even easy to fail accidently. Therefore, it is necessary to design a fault-tolerant network. A feasible method is to construct a k-vertex connected topology. In this paper, we consider k-connectivity of wireless network and propose a simple global algorithm (GAFTk) which preserves the network k-connectivity and reduces the maximal transmission power (TP). The average degree expectation of the topology generated by GAFTkis O(k2). Based on GAFTk, we propose a simple local algorithm (LAFTk) which preserves k-vertex connectivity while maintaining bi-directionality of the network. Simulation results show that GAFT/LAFT have better performance than other current fault-tolerant protocols.

Conventionally, most network protocols assume that the network entities who participate in the network activities will always behave as instructed. However, in practice, most network entities are selfish: they will try to maximize their own benefits instead of altruistically contributing to the network by following the prescribed protocols. Thus, new protocols should be designed for the non-cooperative network that is composed of selfish entities. In this paper, we specifically show how to design truthful multicast protocols for non-cooperative networks such that these selfish entities will follow the protocols out of their own interests. By assuming that every entity has a fixed cost for a specific multicast, we give a general framework to decide whether it is possible and how, if possible, to transform an existing multicast protocol to a truthful multicast protocol by designing a proper payment protocol. We then show how the payments to those relay entities are shared fairly among all receivers so that it encourages collaboration among receivers. As running examples, we show how to design truthful multicast protocols for several multicast structures that are currently used in practice.

Wireless sensor networks have been widely used in many surveillance applications. Due to the importance of sensor nodes in such applications, certain level of protection need to be provided to them. We study the self protection problem for static wireless sensor networks in this paper. Self protection problem focuses on using sensor nodes to provide protection to themselves instead of the target objects or certain target area, so that the sensor nodes can resist the attacks targeting on them directly. A wireless sensor network is p-self-protected, if at any moment, for any wireless sensor (active or non-active), there are at least p active sensors that can monitor it. The problem finding minimum p-self-protection is NP-complete, and no efficient self protection algorithms have been proposed. In this paper, we provide efficient centralized and distributed algorithms with constant approximation ratio for minimum p-self-protection problem in sensor networks with either homogeneous or heterogeneous sensing radius. In addition, we design efficient distributed algorithms to not only achieve p-self-protection but also maintain the connectivity of all active sensors. Our simulation confirms the performances of proposed algorithms.

We study efficient interference-aware joint routing and TDMA link scheduling for a multihop wireless network to maximize its throughput. Efficient link scheduling can greatly reduce the interference effect of close-by transmissions. Unlike the previous studies that often assume a unit disk graph model, we assume that different terminals could have different transmission ranges and interference ranges. In our model, a communication link may not exist due to barriers or is not used by a predetermined routing protocol. Using a mathematical formulation, we develop interference aware joint routing and TDMA link schedulings that optimize the networking throughput subject to various constraints. Our linear programming formulation will find a flow routing whose achieved throughput (or fairness) is at least a constant fraction of the optimum. Then, by assuming known link capacities and link traffic loads, we study link scheduling under the RTS/CTS interference model and the protocol interference model with fixed transmission power. For both models, we present both efficient centralized and distributed algorithms that use time slots within a constant factor of the optimum. We also present efficient distributed algorithms whose performances are still comparable with optimum, but with much less communications. Our theoretical results are corroborated by extensive simulation studies.

Wireless sensor networks have been widely used in many surveillance applications. Due to the importance of sensor nodes in such applications, certain level of protection needs to be provided to them. We study the self protection problem for static wireless sensor networks in this paper. Self protection problem focuses on using sensor nodes to provide protection to themselves instead of the target objects or certain target area, so that the sensor nodes can resist the attacks targeting on them directly. A wireless sensor network is p-self-protected, if for any wireless sensor there are at least p active sensors that can monitor it. The problem finding minimum p-self-protection is NP-complete and no efficient self protection algorithms have been proposed. In this paper, we provide efficient centralized and distributed algorithms with constant approximation ratio for minimum p-self-protection problem. In addition, we design efficient distributed algorithms to not only achieve p-self-protection but also maintain the connectivity of all active sensors. Our simulation confirms the performances of proposed algorithms.

We address the problem of gateway placement for throughput optimization in multi-hop wireless mesh networks. Assume that each mesh node in the mesh network has a traffic demand. Given the number of gateways need to be deployed (denoted by k) and the interference model in the network, we study where to place exactly k gateways in the mesh network such that the total throughput is maximized while it also ensures a certain fairness among all mesh nodes. We propose a novel grid-based gateway deployment method using a cross-layer throughput optimization. Our proposed method can also be extended to work with multi-channel and multi-radio mesh networks. Simulation result demonstrates that our method can effectively exploit the resources available and perform much better than random and fixed deployment methods.

Energy aware routing protocols are consistently cited as efficient solutions for ad hoc and sensor networks routing and data management. However, there is not a consistent approach to define the energy related cost metrics that are used to guide the routing protocol performance. This paper provides a survey and analysis of energy related metrics used for ad hoc routing. First, the most common energy efficient routing protocols are classified into four categories based on the energy cost metrics employed. Then, the results of our simulation-based analysis are presented. We conducted a complete set of simulations to compare and contrast the performance of various energy-related metrics. Our analysis provides a comparison of the performance of energy cost metrics used within AODV-based ad hoc routing protocols.

Topology control in wireless ad hoc and sensor networks has been heavily studied recently. Different geometric topologies were proposed to be the underlying network topologies to achieve the sparseness of the communication networks or to guarantee the package delivery of specific routing methods. However, most of the proposed topology control algorithms were only applied to 2D networks where all nodes are distributed in a 2D plane. In practice, the ad hoc and sensor networks are often deployed in 3D space, such as notebooks in a multi-floor building and sensor nodes in a forest. This paper seeks to investigate power efficient topology control protocols for 3D ad hoc and sensor networks. In our new protocols, we extend several 2D geometric topologies to 3D case, and propose some new 3D Yao-based topologies. We also prove several properties (e.g., bounded degree and constant power stretch factor) for them in 3D space. The simulation confirms our theoretical proofs for these proposed 3D topologies.

We propose novel solutions for unicast routing in wireless networks consisted of selfish terminals: in order to alleviate the inevitable over-payment problem (and thus economic inefficiency) of the VCG (Vickrey-Clark-Groves) mechanism, we design a mechanism that results in Nash equilibria rather than the traditional strate-gyproofness (using weakly dominant strategy). In addition, we systematically study the unicast routing system in which both the relay terminals and the service requestor (either the source or the destination nodes or both) could be selfish. To the best of our knowledge, this is the first paper that presents social efficient unicast routing systems with proved performance guarantee. Thus, we call the proposed systems: Optimal Unicast Routing Systems (OURS).Our main contributions of OURS are as follows. (1) For the principal model where the service requestor is not selfish, we propose a mechanism that provably creates incentives for intermediate terminals to cooperate in forwarding packets for others. Our mechanism substantially reduces the overpayment by using Nash equilibrium solutions as opposed to strategyproof solutions. We then study a more realistic case where the service requestor can act selfishly. (2) We first show that if we insist on the requirement of strategyproofness for the relay terminals, then no system can guarantee that the central authority can retrieve at least 1overn of the total payment. (3) We then present a strategyproof unicast system that collects 1over2n of the total payment, which is thus asymptotically optimum. (4) By only requiring Nash Equilibrium solutions, we propose a system that creates incentives for the service requestor and intermediate terminals to correctly follow the prescribed protocol. More importantly, the central authority can retrieve at least half the total payment. We verify the economic efficiency of our systems through simulations that are based on very realistic terminal distributions.

We study efficient link scheduling for a multihop wireless network to maximize its throughput. Efficient link scheduling can greatly reduce the interference effect of close-by transmissions. Unlike the previous studies that often assume a unit disk graph model, we assume that different terminals could have different transmission ranges and different interference ranges. In our model, it is also possible that a communication link may not exist due to barriers or is not used by a predetermined routing protocol, while the transmission of a node always result interference to all non-intended receivers within its interference range. Using a mathematical formulation, we develop synchronized TDMA link schedulings that optimize the networking throughput. Specifically, by assuming known link capacities and link traffic loads, we study link scheduling under the RTS/CTS interference model and the protocol interference model with fixed transmission power. For both models, we present both efficient centralized and distributed algorithms that use time slots within a constant factor of the optimum. We also present efficient distributed algorithms whose performances are still comparable with optimum, but with much less communications. Our theoretical results are corroborated by extensive simulation studies.

In this paper, we address the problem of energy efficient localized routing in wireless ad hoc networks. Numerous energy aware routing protocols were proposed to seek the power efficiency of routes. Among them, several geographical localized routing protocols were proposed to help making smarter routing decision using only local information and reduce the routing overhead. However, most of the proposed localized routing methods cannot theoretically guarantee the power efficiency of their routes. In this paper, we give the first localized routing algorithm, called localized energy aware restricted neighborhood routing (LEARN), which can guarantee the power efficiency of its route asymptotically almost sure. Given destination node t, an intermediate node v will only select a certain neighbor v such thatvutles alpha for a parameter alphan= radicbetalnl/pin for some beta > pi/alpha, our LEARN routing protocol will find the route for any pair of nodes asymptotically almost sure. When the transmission range rn= radicbetalnl/pin for some beta < pi/alpha, the LEARN routing protocol will not be able to find the route for any pair of nodes asymptotically almost sure. We also conducted simulations to study the performance of LEARN and compare it with a typical localized routing protocol (GPSR) and a global ad hoc routing protocol (DSR)

This article studies topology control in heterogeneous wireless sensor networks, where different wireless sensors may have different maximum transmission ranges and two nodes can communicate directly with each other if and only if they are within the maximum transmission range of each other. We present several localized topology control strategies in which every wireless sensor maintains logical communication links to only a selected small subset of its physical neighbors using information of sensors within its local neighborhood in a heterogeneous network environment. We prove that the global logical network topologies formed by these locally selected links are sparse and/or power efficient and our methods are communication efficient. Here a structure is power efficient if the total power consumption of the least cost path connecting any two nodes in it is no more than a small constant factor of that in the original heterogeneous communication network. By utilizing the wireless broadcast channel capability, and assuming that a message sent by a sensor node will be received by all sensors within its transmission region with at most a constant number of transmissions, we prove that all our methods use at most O(n) total messages, where each message has O (log n ) bits. We also conduct extensive simulations to study the practical performance of our methods.

Backbone has been used extensively in various aspects (e.g., routing, route maintenance, broadcast, scheduling) for wireless ad hoc or sensor networks recently. Previous methods are mostly designed to minimize the size of the backbone. However, in many applications, it is desirable to construct a backbone with small cost when each wireless node has a cost of being in the backbone. In this paper, we first show that previous methods specifically designed to minimize the backbone size may produce a backbone with large cost. Then, an efficient distributed method to construct a weighted backbone with low cost is proposed. We prove that the total cost of the constructed backbone is within a small constant factor of the optimum for homogeneous networks when either the nodes' costs are smooth (i.e., the maximum ratio of costs of adjacent nodes is bounded) or the network maximum node degree is bounded. We also show that, with a small modification, the backbone is efficient for unicast: the total cost (or hop) of the least cost (or hop) path connecting any two nodes using backbone is no more than three (or four) times the least cost (or hop) path in the original communication graph. Our theoretical. results are corroborated by our simulation studies. Finally, we discuss several possible ad hoc network applications of our proposed backbone formation algorithms.

Wireless hybrid networks combine the characteristics of both cellular and mobile ad hoc networks. In wireless hybrid networks, it is often assumed that each individual mobile node faithfully follows the prescribed protocols without any deviation. However, these mobile devices, when owned by individual users, will likely do what is the most beneficial to their owners, i.e., act "selfishly". Therefore, an algorithm or protocol intended for selfish wireless devices must be designed. In this paper, we specifically study how to design routing protocols in wireless hybrid networks with selfish nodes. We first present a VCG-based routing protocol for hybrid networks, and show it is truthful but could be expensive. Then we modify the VCG-based routing protocol to make it more efficient for hybrid networks in term of total payment. However, we prove that nodes could lie up their costs in the modified method. Moreover, we propose a novel routing protocol based on first-price path auctions [N. Immorlica et al, 2005], which can achieve a Nash equilibrium with low total payment.

Topology control in wireless ad hoc networks has been heavily studied recently. Different geometric topologies were proposed to be used as the underlying network topologies, in order to achieve the sparseness of the communication network or to guarantee the package delivery of specific routing methods. However, most of the proposed topology control algorithms were applied for all nodes in the networks at the initial network startup stage, and the constructed topologies were kept being maintained thereafter. The overhead of topology control at each node at any time is notable, and this affects the performance of the network and wastes energy for each wireless node. This paper seeks to investigate the practices of efficient on-demand topology control protocol for wireless ad hoc networks. In our new protocol, we only apply the specific topology control technique where and when the wireless node needs it. Our simulation confirms that our scheme has better performance than several existing methods.

Conventionally, most network protocols assume that the network entities that participate in the network activities will always behave as instructed. However, in practice, most network entities will try to maximize their own benefits instead of altruistically contribute to the network by following the prescribed protocols, which is known as selfish. Thus, new protocols should be designed for the non-cooperative network, which is composed of selfish entities. In this paper, we specifically show how to design strategyproof multicast protocols for non-cooperative networks such that these selfish entities will follow the protocols out of their own interests. By assuming that a group of receivers is willing to pay to receive the multicast service, we specifically give a general framework to decide whether it is possible, and how if possible to transform an existing multicast protocol to a strategyproof multicast protocol. We then show how the payments to those relay entities are shared fairly among all receivers so that it encourages collaboration among receivers. As a running example, we show how to design the strategyproof multicast protocol for the currently used core-based multicast structure. We also conduct extensive simulations to study the relations between payment and cost of the multicast structure.

Backbone has been used extensively in various aspects (e.g., routing, route maintenance, broadcast, scheduling) for wireless networks. Previous methods are mostly designed to minimize the backbone size. However, in many applications, it is desirable to construct a backbone with small cost when each wireless node has a cost of being in the backbone. In this paper, we first show that previous methods specifically designed to minimize the backbone size may produce a backbone with a large cost. We then propose an efficient distributed method to construct a weighted sparse backbone with low cost. We prove that the total cost of the constructed backbone is within a small constant factor of the optimum for homogeneous networks when either the nodes' costs are smooth or the network maximum node degree is bounded. We also show that with a small modification the constructed backbone is efficient for unicast: the total cost (or hop) of the least cost (or hop) path connecting any two nodes using backbone is no more than 3 (or 4) times of the least cost (or hop) path in the original communication graph. As a side product, we give an efficient overlay based multicast structure whose total cost is no more than 10 times of the minimum when the network is modeled by UDG. Our theoretical results are corroborated by our simulation studies.

We propose a new localized structure, namely, Incident MST and RNG Graph (IMRG), for topology control and broadcasting in wireless ad hoc networks. In the construction algorithm, each node first builds a modified relative neighborhood graph (RNG'), and then informs its one-hop neighbors its incident edges in RNG'. Each node then collects all its one-hop neighbors and the two-hop neighbors who have RNG edges to some of its one-hop neighbors, and builds an Euclidean minimum spanning tree of these nodes. Each node u keeps an edge uv only if uv is in the constructed minimum spanning tree. We analytically prove that the node degree of the IMRG is at most 6, it is connected and planar, and more importantly, the total edge length of the IMRG is within a constant factor of that of the minimum spanning tree. To the best of our knowledge, this is the first algorithm that can construct a structure with all these properties using small communication messages (at most 13n total messages, each with O(logn) bits) and small computation cost, where n is the number of wireless nodes. Test results are corroborated in the simulation study.

This work addresses the problem of scattemet formation for single-hop Bluetooth based personal area and ad hoc networks, with minimal communication overhead. Recent scatternet formation schemes by Li, Stojmenovic and Wang [Ref. 1] are position based and were applied for multihop networks. These schemes are localized and can construct degree limited and connected piconets, without parking any node. In this article we apply their methods to single-hop networks, by showing that position information is then not needed. Each node can simply select a virtual position, and communicate it to all neighbors in the neighbor discovery phase. Nodes then act according to the scheme in [X.Y. Li et al., 2004] using such virtual positions instead of real ones. In addition, we use Delaunay triangulation instead of partial Delauliay triangulation proposed in [X.Y. Li et al., 2004], since each node has all the information needed. Finally, we design experiments to study both the properties of formatted scatternets (such as number of piconets) and the performances of different localized routing methods on them. The experiments confirm good functionality of created Bluetooth networks in addition to their fast creation and straightforward maintenance.

We study topology control in heterogeneous wireless ad hoc networks, where mobile hosts may have different maximum transmission powers and two nodes are connected if they are within the maximum transmission range of each other. We present several strategies so that all wireless nodes self-maintain sparse and power efficient topologies in heterogeneous network environments with low communication cost. The first structure is sparse and can be used for broadcasting. The second structure keeps the minimum power consumption path, and the third structure is a length and power spanner with a bounded degree. Both the second and third structures are power efficient and can be used for unicast. Here a structure is power efficient if the total power consumption of the least cost path connecting any two nodes in it is no more than a small constant factor of that in the original heterogeneous communication graph. All our methods use at most O(n) total messages, where each message has O(logn) bits.

In wireless networks, it is often assumed that each individual wireless terminal will faithfully follow the prescribed protocols without any deviation-- except, perhaps, for a few faulty or malicious ones. Wireless terminals, when owned by individual users, will likely do what is the most beneficial to their owners, i.e., act "selfishly". Therefore, an algorithm or protocol intended for selfish wireless networks must be designed.In this paper, we specifically study how to conduct efficient multicast routing in selfish wireless networks. We assume that each wireless terminal or communication link will incur a cost when it transits some data. Traditionally, the VCG mechanism has been the only method to design protocols so that each selfish agent will follow the protocols for its own interest to maximize its benefit. The main contributions of this paper are two-folds. First, for each of the widely used multicast structures, we show that the VCG based mechanism does not guarantee that the selfish terminals will follow the protocol. Second, we design the first multicast protocols without using VCG mechanism such that each agent maximizes its profit when it truthfully reports its cost.Extensive simulations are conducted to study the practical performances of the proposed protocols regarding the actual network cost and total payment.

Abstract. Topology control in wireless ad hoc networks is to select a subgraph of the communication graph (when all nodes use their maximum transmission range) with some properties for energy conservation. In this paper, we propose two novel localized topology control methods for homogeneous wireless ad hoc networks. Our first method constructs a structure with the following attractive properties: power efficient, bounded node degree, and planar. Its power stretch factor is at most ρ = 11−(2 sin π k)β, and each node only has to maintain at most k + 5 neighbors where the integer k> 6 is an adjustable parameter, and β is a real constant between 2 and 5 depending on the wireless transmission environment. It can be constructed and maintained locally and dynamically. Moreover, by assuming that the node ID and its position can be represented in O(log n) bits each for a wireless network of n nodes, we show that the structure can be constructed using at most 24n messages, where each message is O(log n) bits. Our second method improves the degree bound to k, relaxes the theoretical power spanning ratio to ρ =

We address the problem of localized scatternet formation for multihop Bluetooth-based personal area ad hoc networks. Nodes are assumed to know their positions and are able to establish connections with any of their neighboring nodes, located within their transmission radius, in the neighbor discovery phase. The next phase of the proposed formation algorithm is optional and can be applied to construct a sparse geometric structure in a localized manner. We propose here a new sparse planar structure, namely, partial Delaunay triangulation (PDT), which can be constructed locally and is denser than other known localized planar structures. In the next mandatory phase, the degree of each node is limited to seven by applying the Yao structure, and the master-slave relations in piconets are formed in created subgraphs. This phase consists of several iterations. In each iteration, undecided nodes with higher keys than any of their undecided neighbors apply the Yao structure to bound the degrees, decide master-slave relations on the remaining edges, and inform all neighbors about either deleting edges or master-slave decisions. To the best of our knowledge, our schemes are the first schemes that construct degree limited (a node has at most seven slaves) and connected piconets in multihop networks, without parking any node. The creation and maintenance require small overhead in addition to maintaining accurate location information for one-hop neighbors. The experiments confirm good functionality of created Bluetooth networks in addition to their fast creation and straightforward maintenance.

We propose a family of structures, namely, k-localized minimum spanning tree (LMST/sub k/) for topology control and broadcasting in wireless ad hoc networks. We give an efficient localized method to construct LMST/sub k/ using only O(n) messages under the local-broadcast communication model, i.e., the signal sent by each node would be received by all nodes within the node's transmission range. We also analytically prove that the node degree of the structure LMST/sub k/ is at most 6, LMST/sub k/ is connected and planar and, more importantly, the total edge length of the LMST/sub k/ is within a constant factor of that of the minimum spanning tree when k/spl ges/2 (called low weighted hereafter). We then propose another low weighted structure, called Incident MST and RNG Graph (IMRG), that can be locally constructed using at most 13n messages under the local broadcast communication model. Test results are corroborated in the simulation study. We study the performance of our structures in terms of the total power consumption for broadcasting, the maximum node power needed to maintain the network connectivity. We theoretically prove that our structures are asymptotically the best possible for broadcasting among all locally constructed structures. Our simulations show that our new structures outperform previous locally constructed structures in terms of broadcasting and power assignment for connectivity.

Abstract We consider a large‐scale of wirelessad hocnetworks whose nodes are distributed randomly in a two‐dimensional region Ω (more specifically, a unit square). Givennwireless nodesV, each with transmission rangern, the wireless networks are often modeled by graphG(V,rn) in which two nodes are connected if and only if their Euclidean distance is no more thanrn. We first consider how to relate the transmission range with the number of nodes in a fixed area such that the resulted network can sustainkfault nodes in its neighborhood with high probability when all nodes have the same transmission range. We show that, for a unit‐area square region Ω, the probability that the networkG(V,rn) isk‐connected is at least${\rm e}^{-{\rm e}^{-\alpha}}$ when the transmission radiusrnsatisfies$n \pi r_n^2 \ge {\rm ln}\ n \,+ (2k - 3) {\rm ln}\, {\rm ln}\, n - 2 \,{\rm ln}(k - 1)! + 2 \alpha \ {\rm for} \, k >\,1$ andnsufficiently large. This result also applies to mobile networks when the moving of wireless nodes always generates randomly distributed positions. We also conduct extensive simulations to study the practical transmission range to achieve certain probability the network beingk‐connectivity, when the number of nodesnis not large enough. The relation between the minimum node degree and the connectivity of graphG(V,r) is also studied. Setting the transmission range of all nodes tornguarantees thek‐connectivity with high probability, but some nodes may have excessive number of neighbours in the graphG(V,rn). We then present a localized method to construct a subgraph of the network topologyG(V,rn) such that the resulting subgraph is stillk‐connected but with much fewer communication links maintained. We show that the constructed topology has onlyO(k · n) links and is a length spanner. Here a graphH ⊆ Gis spanner for graphG, if for any two nodes, the length of the shortest path connecting them inHis no more than a small constant factor of the length of the shortest path connecting them inG. Finally, we conduct some simulations to study the practical transmission range to achieve certain probability ofk‐connected whennis not large enough. Copyright © 2004 John Wiley & Sons, Ltd.

We show that given a set of randomly distributed wireless nodes with density n, when the transmission range r/sub n/ of wireless nodes satisfies /spl pi/r/sup 2//sub n/ /spl ges/ 3[(log n+c(n))/n], the localized Delaunay triangulation (LDel) [Xiang-Yang Li, G. Calinescu, and Peng-Jun Wan, 2002] is the same as the Delaunay triangulation with high probability, where c(n) /spl rarr/ /spl infin/ as n goes infinity. Our experiments show that the delivery rates of existing localized Delaunay triangulation is used instead of several previously proposed topologies, and the localized routing protocol based on Delaunay triangulation works well in practice.

We consider a large-scale of wireless ad hoc networks whose nodes are distributed randomly in a two-dimensional region /spl Omega/. Given n wireless nodes V, each with transmission range r/sub n/, the wireless networks are often modeled by graph G(V, r/sub n/) in which two nodes are connected if their Euclidean distance is no more than r/sub n/. We show that, for a unit-area square region /spl Omega/, the probability G(V, r/sub n/) being k-connected is at least (e/sup -e/)/sup -/spl sigma// when n/spl pi/(r/sup 2/)/sub n/ /spl ges/ ln n + (2k - 3) ln ln n - 2 ln (k - 1)! + 2/spl sigma/ for k > 1 and n sufficiently large. This result also applies to mobile networks when the moving of wireless nodes always generates randomly and uniformly distributed positions. We also conduct extensive simulations to study the practical transmission range to achieve certain probability of k-connectivity when n is not large enough. The relation between the minimum node degree and the connectivity of graph G(V, r) is also studied.

This paper investigate fault tolerance for wireless ad hoc networks. We consider a large-scale of wireless networks whose nodes are distributed randomly in a unit-area square region. Given n wireless nodes V, each with transmission range rn, the wireless networks are often modeled by graph G(V,rn) in which two nodes are connected if their Euclidean distance is no more than rn.We first consider how the transmission range is related with the number of nodes in a fixed area such that the resulted network can sustain k fault nodes with high probability. We show that, for a unit-area square region, the probability that the network G(V,rn) is (k+1)-connected is at least e-e-α when the transmission radius rn satisfies n π rn2 ≥ ln n + (2k-1) ln ln n -2ln k! + 2α for k>0 and n sufficiently large. This result also applies to mobile networks when the moving of wireless nodes always generates randomly distributed positions. Our simulations show that n should be larger than 500 if k=2 or 3 and α = log n and n should be larger than 2500 if k=2 or 3 and α = log log n.We then present a localized method to control the network topology given a (k+1)-faults tolerant deployment G(V,rn) of wireless nodes such that the resulting topology is still (k+1)-faults tolerant but with O(kn) communication links maintained. We show that the constructed topology is also a length spanner. Here a subgraph H is spanner of graph G, if for any two nodes, the length of the shortest path connecting them in H is no more than a small constant factor of the length of the shortest path connecting them in G.Finally, we conduct some simulations to study the practical transmission range to achieve certain probability of k-connected when n is not large enough.

We propose a new geometric spanner for static wireless ad hoc networks, which can be constructed efficiently in a localized manner. It integrates the connected dominating set and the local Delaunay graph to form a backbone of the wireless network. Priori arts showed that both structures can be constructed locally with bounded communication costs. This new spanner has these following attractive properties: 1) the backbone is a planar graph, 2) the node degree of the backbone is bounded from above by a positive constant, 3) it is a spanner for both hops and length, 4) it can be constructed locally and is easy to maintain when the nodes move around, and 5) moreover, the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance.

Several localized routing protocols guarantee the delivery of the packets when the underlying network topology is a planar graph. Typically, relative neighborhood graph (RING) or Gabriel graph (GG) is used as such planar structure. However, it is well-known that the spanning ratios of these two graphs are not bounded by any constant (even for uniform randomly distributed points). Bose et al. (1999) recently developed a localized routing protocol that guarantees that the distance traveled by the packets is within a constant factor of the minimum if Delaunay triangulation of all wireless nodes is used, in addition, to guarantee the delivery of the packets. However, it is expensive to construct the Delaunay triangulation in a distributed manner. Given a set of wireless nodes, we model the network as a unit-disk graph (UDG), in which a link uv exists only if the distance /spl par/uv/spl par/ is at most the maximum transmission range. In this paper, we present a novel localized networking protocol that constructs a planar 2 5-spanner of UDG, called the localized Delaunay triangulation (LDEL), as network topology. It contains all edges that are both in the unit-disk graph and the Delaunay triangulation of all nodes. The total communication cost of our networking protocol is O(n log n) bits, which is within a constant factor of the optimum to construct any structure in a distributed manner. Our experiments show that the delivery rates of some of the existing localized routing protocols are increased when localized Delaunay triangulation is used instead of several previously proposed topologies. Our simulations also show that the traveled distance of the packets is significantly less when the FACE routing algorithm is applied on LDEL, rather than applied on GG.

Secure and efficient communication among a set of mobile nodes is one of the most important aspects in ad-hoc wireless networks. To ensure the security, several cryptography protocols must be implemented. Due to the resource scarcity in wireless networks, the protocols must be communication efficient and need as less computational power as possible. To secure the group broadcasting in wireless networks, often a group key is needed so that efficient conventional encryption, such as DES and AES, can be used. Several group key management protocols have been proposed. However, not all of them are communication efficient when applied to wireless ad-hoc networks. In this paper, we propose a key agreement protocol that is communication efficient by using connected dominating set concept to set up subgroups among all wireless nodes. We also show how to manage the group efficiently in a mobile environment.

We propose a new geometric spanner, for wireless ad hoc networks, which can be constructed efficiently in a distributed manner. It combines the connected dominating set and the local Delaunay graph to form the backbone of a wireless network. This new spanner has the following attractive properties: (1) the backbone is a planar graph; (2) the node degree of the backbone is bounded from above by a positive constant; (3) it is a spanner both for hops and length; moreover, we show that, given any two nodes u and /spl upsi/, there is a path connecting them in the backbone such that its length is no more than 6 times that of the shortest path and the number of links is no more than 3 times that of the shortest path; (4) it can be constructed locally and is easy to maintain when the nodes move around; and (5) we show that the computation cost of each node is at most O(d log d), where d is its l-hop neighbors in the original unit disk graph, and the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance.

Due to the limited resources available in the wireless ad hoc networking nodes, the scalability is crucial for network operations. One effective approach is to maintain only a sparse spanner of a linear number of links while still preseving the power-efficient route for any pair of nodes. For any spanner G, its power stretch factor is defined as the maximum ratio of the minimum power needed to support any link in this spanner to the least necessary. In this paper, we first consider several well-known proximity graphs including the relative neighborhood graph, Gabriel graph and Yao graph. These graphs are sparse and can be constructed locally in an efficient way. We show that the power stretch factor of the Gabriel graph is always one, and the power stretch factor of the Yao graph is bounded by a constant while the power stretch factor of the relative neighborhood graph could be as large as the network size minus one. Notice that all of these graphs do not have constant degrees. We further propose another sparse spanner that has both constant degree and constant power stretch factor. An efficient local algorithm is presented for the construction of this spanner.