We investigate the problem of target object information collection in multi-tagged RFID systems. Different from its single-tagged peers, the multi-tagged RFID scenario introduces three new challenges: 1) Tags on the same object carry the same information, so reusing single-tagged algorithms causes unnecessary redundancy; 2) The transition of objects from being tagged one to multiple tags leads to an upsurge in slot collisions; 3) Gathering information from more tags necessitates more downlink transmission, making it hard to limit broadcast information while ensuring time-efficient information collection. To tackle these technical challenges, we propose an efficient information collection algorithm, called Backtracking Collision Peeling (BCP), featuring three key techniques. First, BCP selects a single time slot (allowing even collision slots) for each target object to convey its information. This approach bypasses the need for a high-latency collision elimination process, thereby significantly reducing time overhead. Second, by exploiting dependencies among the selected slots, BCP recovers object information in complex collision slots using object information from already resolved slots, offering a novel and effective solution for handling signal collisions. Third, to minimize downlink transmission cost, BCP polls tags by transmitting only incremental changes between polling vectors, rather than the complete vectors. We further improve performance with E-BCP by enhancing the utilization of collision slots, thereby reducing the number of required polling rounds. Experiments show BCP and E-BCP outperform existing methods by at least$35\%$in aggregate execution time, while also exhibiting stronger stability and robustness.

Although Federated Learning (FL) can enable advanced autonomous driving via leveraging massive distributed data in vehicular networks, vehicle mobility causes frequent connection interruptions, hindering the FL process. In this paper, we propose a novelMobility-AwareVehicularFL(MAVFL) scheme, which can accelerate the training process in dynamic vehicular networks via adaptive vehicle selection and sparse training. Specifically, the MAVFL dynamically selects participating vehicles based on their locations and training loss. By incorporating adaptive model sparsification, the proposed scheme dynamically proceeds with sparse masks during vehicle local training, thereby reducing communication overhead while preserving model accuracy. We conduct a rigorous convergence analysis to uncover how vehicle mobility and model sparsification affect convergence rate. Furthermore, we formulate an optimization problem to accelerate the training process, which jointly optimizes vehicle selection, sparsification ratio, and bandwidth allocation to minimize training delay. To solve the problem, we employ the Lyapunov optimization method to decouple the long-term problem into a series of instantaneous subproblems. Next, a generalized Benders decomposition method structures the original problem into a master subproblem for vehicle selection and a primal subproblem for bandwidth allocation and sparsification ratio selection. The optimal solutions are derived via alternating iterations between these problems. Extensive simulation results based on the SUMO simulator demonstrate that the MAVFL accelerates model convergence by up to 14% and reduces communication overhead by up to 26% while preserving model accuracy, as compared to the state-of-the-art benchmarks.

Bloom filters (BF) are space-efficient probabilistic data structures for approximate membership testing. Boosted by the proliferation of machine learning, learned Bloom filters (LBF) were recently proposed by augmenting the canonical BFs with a learned oracle as a pre-filter, the size of which is crucial to the compactness of the overall system. In this paper, inspired by ensemble learning, we depart from the state-of-the-art single-oracle LBF structure by demonstrating that, by leveraging multiple learning oracles of smaller size and carefully optimizing the accompanied backup filters, we can significantly boost the performance of LBF under the same space budget. We then design and optimize ensemble learned Bloom filters for mutually independent and correlated learning oracles respectively. We also empirically demonstrate the performance improvement of our propositions under three practical data analysis tasks.

Mobile Edge Computing (MEC) revolutionizes real-time applications by extending cloud capabilities to network edges, enabling efficient computation offloading from mobile devices. In recent years, the location privacy concern within MEC offloading has been recognized, prompting the proposal of various methodologies to mitigate this concern. However, this paper demonstrates that the prevailing privacy protection methods exhibit vulnerabilities. First, we analyze the shortcomings of current methodologies through both system modeling and evaluation metrics. Then, we introduce a Learning-based Trajectory Reconstruction Attack (LTRA) to expose the weaknesses, achieving up to 91.2% reconstruction accuracy against the state-of-the-art protection method. Further, based onw-event differential privacy, we propose an ℓ-trajectory differentially private mechanism, i.e., OffloadingBD. Compared to the existing works, OffloadingBD provides more flexible and enhanced protection with sound privacy theoretical guarantee. Lastly, we conduct extensive experiments to evaluate LTRA and OffloadingBD. The experiment results show that LTRA has good generalization ability and OffloadingBD showcases a superior balance between privacy and utility compared with baselines.

Privacy-preserving vector mean estimation is a crucial primitive in federated analytics. Existing practices usually resort to Local Differentiated Privacy (LDP) mechanisms that inject random noise into users’ vectors when communicating with users and the central server. Due to the privacy-utility trade-off, the privacy budget has been widely recognized as the bottleneck resource that requires well-provisioning. In this paper, we explore the possibility of privacy budget recycling and propose a novelChainDPframework enabling users to carry out data aggregation sequentially to recycle the privacy budget. We establish a sequential game to model the user interactions in our framework. We theoretically show the mathematical nature of the sequential game, solve its Nash Equilibrium, and design an incentive mechanism with provable economic properties. To alleviate potential privacy collusion attacks, we further derive a differentially privacy-guaranteed protocol to avoid holistic exposure. Our numerical simulation validates the effectiveness of ChainDP, showing that it can significantly save privacy budget as well as lower estimation error compared to the traditional LDP mechanism.

We study the problem of target object information collection in multi-tagged COTS RFID systems. Unlike its singletagged peers, the multi-tagged COTS RFID scenario poses new challenges in devising information collection algorithms: 1) Tags attached to the same object carry identical information. Hence, reusing single-tagged information collection algorithms leads to unnecessary redundancy; 2) Multi-tagged RFID systems are often deployed in applications where tags are vulnerable to damage. Such faulty tags may severely degrade the performance of information collection; 3) Most state-of-the-art information collection algorithms rely heavily on the hashing operation that is not seamlessly supported by the C1G2 standard, rendering these solutions inefficient and impractical, especially in largescale RFID systems. To tackle these technical challenges, this paper makes three contributions. First, we develop an efficient and compact tag pseudo-ID design, enabling the reader to select a single tag from each target object to collect information with only one SELECT command. Second, we construct a robust faulthandling mechanism capable of recognizing faulty tags without executing the entire slot. Third, armed with the above two techniques, we develop a novel information collection algorithm by leveraging the functionality offered by C1G2 to optimize the information collection sequence, thus minimizing the overall execution time. Empirical experiments on a COTS RFID system prototype demonstrate that our algorithm outperforms the best existing solution by 35-50% on average.

In many real-life applications, wireless chargers are deployed outdoor or in public area or even unattended environment such as hotels, restaurants, retail stores. They are exposed to various risks and malicious attacks that may break them down and further incur significant cost (e.g., battery replacement and maintenance) or performance degradation. Hence, we consider the problem ofFault-tolerant wIreless chaRger placeMent (FIRM): given a set of wireless chargers and a set of tasks to be collaboratively conducted by a set of rechargeable devices, determining where to deploy the chargers to maximize the worst-cast overall task charging utility subject to the constraint that up to$\tau$chargers may break down. FIRM is a non-linear combinatorial two-level optimization problem. We first consider a relaxed version of FIRM (FIRM-R for short) corresponding to the inner optimization problem in FIRM. To address FIRM-R, we first propose an area discretization scheme to convert the infinite solution space into finite candidate positions. We then devise a power allocation method, based on which we prove that FIRM-R falls into the realm of maximizing a monotone submodular function under a uniform constraint. We then propose a constant-factor approximation algorithm to solve FIRM-R. Taking the above approximation algorithm as a subroutine, we further develop an approximation algorithm that solves FIRM with a constant-factor approximation ratio. Our extensive simulations and field experiments demonstrate that the overall charging utility of our proposed algorithm FIRM considering fault tolerance by greedy removal of$\tau$chargers outperforms the that of FIRM-R without considering fault tolerance by greedy removal of$\tau$chargers by at least 119.89%.

Recently emerged as a disruptive networking paradigm, quantum networks rely on the mysterious quantum entanglement to teleport qubits without physically transferring quantum particles. However, the state of quantum systems is extremely fragile due to environment noise. A promising technique to combat against quantum decoherence is entanglement purification. To fully exploit its benefit, two fundamental research questions need to be answered: (1) given an entanglement path, what is the optimal entanglement purification schedule? (2) how to compute min-cost end-to-end entanglement paths subject to fidelity constraint? In this paper, we give algorithmic solutions to both questions. For the first question, we develop an optimal entanglement purification scheduling algorithm for the singlehop case and analyze the PURIFY-AND-SWAP strategy in the multi-hop case by establishing the closed-form condition for its optimality. For the second question, we design a polynomialtime algorithm constructing an$\epsilon$-optimal fidelity-constrained path. The effectiveness of our algorithms are also numerically demonstrated by extensive simulations.

Heterogeneous information networks (HIN) have gained increasing popularity in recent years for capturing complex relations between diverse types of nodes. Meta-structures are proposed as a useful tool to identify the important patterns in HINs, but hand-crafted meta-structures pose significant challenges for scaling up, drawing wide research attention towards developing automatic search algorithms. Previous efforts primarily focused on searching for meta-structures with good empirical performance, overlooking the importance of human comprehensibility and generalizability. To address this challenge, we draw inspiration from the emergent reasoning abilities of large language models (LLMs). We propose ReStruct, a meta-structure search framework that integrates LLM reasoning into the evolutionary procedure. ReStruct uses a grammar translator to encode the meta-structures into natural language sentences, and leverages the reasoning power of LLMs to evaluate their semantic feasibility. Besides, ReStruct also employs performance-oriented evolutionary operations. These two competing forces allow ReStruct to jointly optimize the semantic explainability and empirical performance of meta-structures. Furthermore, ReStruct contains a differential LLM explainer to generate and refine natural language explanations for the discovered meta-structures by reasoning through the search history. Experiments on eight representative HIN datasets demonstrate that ReStruct achieves state-of-the-art performance in both recommendation and node classification tasks. Moreover, a survey study involving 73 graduate students shows that the discovered meta-structures and generated explanations by ReStruct are substantially more comprehensible. Our code and questionnaire are available at https://github.com/LinChen-65/ReStruct.

Entanglement purification is a fundamental operation to combat against quantum decoherence and improve the fidelity of the entanglement. When multiple rounds of entanglement purification are performed, the fidelity of the final entanglement depends on the way how we schedule entanglement purification operations at each round. In this paper, we formulate and analyze the optimal entanglement purification scheduling problem arising from this context. Our main results include an optimal link-level purification scheduling algorithm and a joint entanglement purification scheduling and routing algorithm to establish fidelity-guaranteed end-to-end entanglements with quasi-optimal throughput in quantum networks. Our algorithmic framework developed in this paper can serve as functional building blocks for entanglement provisioning to support high-fidelity quantum information transfer by exploiting the limited quantum resources in a cost-effective way in order to fully realize the unrivalled capabilities offered by quantum networks.

Edge computing has recently emerged as a promising paradigm to boost the performance of distributed learning by leveraging the distributed resources at edge nodes. Architecturally, the introduction of edge nodes adds an additional intermediate layer between the master and workers in the original distributed learning systems, potentially leading to more severe straggler effect. Recently, coding theory-based approaches have been proposed for stragglers mitigation in distributed learning, but the majority focus on the conventional workers-master architecture. In this paper, along a different line, we investigate the problem of mitigating the straggler effect in hierarchical distributed learning systems with an additional layer composed of edge nodes. Technically, we first derive the fundamental trade-off between the computational loads of workers and the stragglers tolerance. Then, we propose a hierarchical gradient coding framework, which provides better stragglers mitigation, to achieve the derived computational trade-off. To further improve the performance of our framework in heterogeneous scenarios, we formulate an optimization problem with the objective of minimizing the expected execution time for each iteration in the learning process. We develop an efficient algorithm to mathematically solve the problem by outputting the optimum strategy. Extensive simulation results demonstrate the superiority of our schemes compared with conventional solutions.

Deep learning classifiers are crucial in the age of artificial intelligence. The device-edge-based collaborative inference has been widely adopted as an efficient framework for promoting its applications in IoT and 5G/6G networks. However, it suffers from accuracy degradation under non-i.i.d. data distribution and privacy disclosure. For accuracy degradation, direct use of transfer learning and split learning is high cost and privacy issues remain. For privacy disclosure, cryptography-based approaches lead to a huge overhead. Other lightweight methods assume that the ground truth is non-sensitive and can be exposed. But for many applications, the ground truth is the user's crucial privacy-sensitive information. In this paper, we propose a framework of Roulette, which is a task-oriented semantic privacy-preserving collaborative inference framework for deep learning classifiers. More than input data, we treat the ground truth of the data as private information. We develop a novel paradigm of split learning where the back-end DNN is frozen and the front-end DNN is retrained to be both a feature extractor and an encryptor. Moreover, we provide a differential privacy guarantee and analyze the hardness of ground truth inference attacks. To validate the proposed Roulette, we conduct extensive performance evaluations using realistic datasets, which demonstrate that Roulette can effectively defend against various attacks and meanwhile achieve good model accuracy. In a situation where the non-i.i.d. is very severe, Roulette improves the inference accuracy by 21% averaged over benchmarks, while making the accuracy of discrimination attacks almost equivalent to random guessing.

We study the batch writing problem in RFID systems, where the reader seeks the most time-efficient way to write information into a given subset of tags. The problem is analogous to the multicast problem in classical networks, but one-to-many transmission is not supported in COTS RFID systems. Driven by the technical challenge, this paper addresses the problem of designing batch writing algorithms for COTS RFID systems. We make three contributions. Firstly, we establish the minimal execution time for any batch writing algorithm, thus setting the theoretical performance limit. Secondly, we quantitatively compare and gauge the existing propositions applicable to our problem. Thirdly, we develop a novel batch writing algorithm with minimal 25% performance gain over the best state-of-the-art solution. Our key technicalities are designing an encoding scheme allowing the reader to efficiently perform batch writing and optimizing the batch writing sequence to minimize the overall execution time. We also perform extensive experiments to demonstrate the effectiveness of our algorithm.

We revisit the problem of missing tag identification in RFID networks by making three contributions. Firstly, we quantitatively compare and gauge the existing propositions spanning over a decade on missing tag identification. We show that the expected execution time of the best solution in the literature is$\Theta \left(N+\frac{(1-\alpha)^2(1-\delta)^2}{ \epsilon^2}\right)$, where$\delta$and$\epsilon$are parameters quantifying the required identification accuracy,$N$denotes the number of tags in the system, among which$\alpha N$tags are missing. Secondly, we analytically establish the expected execution time lower-bound foranymissing tag identification algorithm as$\Theta\left(\frac{N}{\log N}+\frac{(1-\delta)^2(1-\alpha)^2}{\epsilon^2 \log \frac{(1-\delta)(1-\alpha)}{\epsilon}}\right)$, thus setting the theoretical performance limit. Thirdly, we develop two novel missing tag identification algorithms with the expected execution time of$\Theta \left(\frac{\log\log N}{\log N}N+\frac{(1-\alpha)^2(1-\delta)^2}{ \epsilon^2}\right)$, reducing the time overhead by a factor of up to$\log N$over the best algorithm in the literature. The key technicality in our first algorithm is a novel data structure termed as collision-partition tree (CPT), built on a subset of bits in tag pseudo-IDs, leading to a more balanced tree structure and reducing the time complexity in parsing the entire tree. To further improve time efficiency, our second algorithm integrates multiple CPTs to form a collision-partition forest (CPF), reducing both the number of slots and the quantity of information broadcasting.

Industrial Wireless Sensor Networks (IWSNs) have been widely used in industrial applications that require highly reliable and real-time wireless transmission. A lot of works have been done to optimize the Relay Node Placement (RNP), which determines the underlying topology of IWSNs and hence impacts the network performance. However, existing RNP algorithms use a fixed communication radius to compute the deployment result at once offline, while ignoring that the radio environment may vary drastically across different locations, also known as radio irregularity. To address this limitation, we propose a Voronoi diagram and Q-learning based RNP (VQRNP) method in this article. Instead of using a fixed communication radius, VQRNP employs the Q-learning algorithm to dynamically update the radio environment of measured areas, uses a Voronoi diagram based method to estimate the radio environment of unmeasured areas, and proposes a coverage extension location selection algorithm to place RNs so as to extend the coverage of the deployed network based on the results estimated by Voronoi diagram based Graph Generating (VGG). In this way, the VQRPN method can adapt itself well to the variation of radio environment and largely speed up the deployment process. Extensive simulations verify that VQRNP significantly outperforms existing RNP algorithms in terms of reliability.

We formulate and analyze the following problem of scheduling dependent batching tasks on a common resource. Each task is associated with an execution time window. Some can be executed simultaneously in batch, while others need exclusively use of the resource. A task may depend on a set of tasks such that it becomes executable only if all its ancestor tasks are completed. We look for a task scheduling policy maximizing the system reward. We investigate both the offline and online settings by focusing on a typical scenario where the task dependency forms a tree or a forest. In both settings, we formally establish the hardness of the scheduling problem by showing that the offline scheduling is NP-hard and the online counterpart admits no scheduling policy with finite competitive ratio. We then develop approximation scheduling algorithms for both cases with deterministic worst-case performance guarantee in terms of system utility. We further conduct numeric experiments to evaluate our algorithms under a variety of parameter settings to demonstrate the effectiveness of our scheduling algorithms.

Understanding the impact of COVID-19 on urban life rhythms is crucial for accelerating the return-to-normal progress and envisioning more resilient and inclusive cities. While previous studies either depended on small-scale surveys or focused on the response to initial lockdowns, this paper uses large-scale location service data to systematically analyze the urban mobility behavior changes across three distinct phases of the pandemic, i.e., pre-pandemic, lockdown, and reopen. Our analyses reveal two typical patterns that govern the mobility behavior changes in most urban venues: daily life-centered urban venues go through smaller mobility drops during the lockdown and more rapid recovery after reopening, while work-centered urban venues suffer from more significant mobility drops that are likely to persist even after reopening. Such mobility behavior changes exert deeper impacts on the underlying social fabric, where the level of mobility reduction is positively correlated with the experienced segregation at that urban venue. Therefore, urban venues undergoing more mobility reduction are also more filled with people from homogeneous socio-demographic backgrounds. Moreover, mobility behavior changes display significant heterogeneity across geographical regions, which can be largely explained by the partisan inclination at the state level. Our study shows the vast potential of location service data in deriving a timely and comprehensive understanding of the social dynamic in urban space, which is valuable for informing the gradual transition back to the normal lifestyle in a “post-pandemic era”.

Privacy-preserving vector mean estimation is a crucial primitive in federated analytics. Existing practices usually resort to Local Differentiated Privacy (LDP) mechanisms that inject random noise into users' vectors when communicating with users and the central server. Due to the privacy-utility trade-off, the privacy budget has been widely recognized as the bottleneck resource that requires well provisioning. In this paper, we explore the possibility of privacy budget recycling and propose a novel Chained-DP framework enabling users to carry out data aggregation sequentially to recycle the privacy budget. We establish a sequential game to model the user interactions in our framework. We theoretically show the mathematical nature of the sequential game, solve its Nash Equilibrium, and design an incentive mechanism with provable economic properties. Our numerical simulation validates the effectiveness of Chained-DP, showing that it can significantly save privacy budget as well as lower estimation error compared to the traditional LDP mechanism.

Federated learning (FL) has recently emerged as a promising learning paradigm, that enables local gradient update and global model aggregation and synchronization. With the advantages of data privacy protection and communication overhead reduction, FL has been widely adopted in a multitude of edge intelligence and IoT applications. However, except the benefits, FL also suffers from stragglers effect and non-IID data, leading to unpredictable training delay and unstable convergence. Meanwhile, coding theory-based approaches have been proposed for stragglers mitigation in distributed computing, i.e., coded computing. Motivated by coded computing, there are several works introduce coding techniques into federated learning. In this paper, to further exploit the potential of coded federated learning, we propose HarFL, a stragglers resilient federated learning framework for non-IID data based on harmonic coding, which is suitable for general machine learning model with multivariate polynomial gradients and achieves a better stragglers mitigation than former coded federated learning schemes with the same coded computation redundancy. We first describe the basic harmonic coded federated learning framework with two phases: encoded data sharing and gradient results decoding. Moreover, we formulate an optimization problem aiming to maximize the successful probability of decoding, which is proved to be NP-hard. An efficient approximate algorithm with theoretical performance guarantee is also developed to mathematically solve the formulated problem. Finally, simulation results demonstrate the superiority of HarFL over several compared schemes.

This paper focuses on the fundamental problem of finding disjoint paths that are robust and resilient against channel instability while achieving optimal or near-optimal performance. We formulate and analyze the problem of finding k nodedisjoint paths resilient to c channel accidents in the sense that if any subset of up to c channels are inoperational, at least one path should still be able to deliver packets. We formulate two versions of the resilient multi-path optimization problem using two performance metrics, the sum of cost and the maximal cost of the k paths. Focusing on directed acyclic graphs, we develop approximation algorithms for both problems. We also develop adapted randomized rounding scheme to further trade off the time and space complexities of our approximation algorithm against the optimality guarantee.

The tremendous success of convolutional neural network (CNN) has made it ubiquitous in many fields of human endeavor. Many applications such as biomedical analysis and scientific data analysis involve analyzing volumetric data. This spawns huge demand for 3D-CNN. Although accelerators such as GPU may provide higher throughput on deep learning applications, they may not be available in all scenarios. CPU, especially many-core CPU with non-uniform memory access (NUMA) architecture, remains an attractive choice for deep learning inference in many scenarios. In this article, we propose a distributed inference solution for 3D-CNN that targets on the emerging ARM many-core CPU platform. A hierarchical partition approach is claimed to accelerate 3D-CNN inference by exploiting characteristics of memory and cache on ARM many-core CPU. Based on the hierarchical model partition approach, other optimization techniques such as NUMA-aware thread scheduling and optimization of 3D-img2row convolution are designed to exploit the potential of ARM many-core CPU for 3D-CNN. We evaluate our proposed inference solution with several classic 3D-CNNs: C3D, 3D-resnet34, 3D-resnet50, 3D-vgg11, and P3D. Our experimental results show that our solution can boost the performance of the 3D-CNN inference, and achieve much better scalability, with a negligible fluctuation in accuracy. When employing our 3D-CNN inference solution on ACL libraries, it can outperform naive ACL implementations by 11× to 50× on ARM many-core processor. When employing our 3D-CNN inference solution on NCNN libraries, it can outperform the naive NCNN implementations by 5.2× to 14.2× on ARM many-core processor.

Cloud service providers typically provide different types of virtual machines (VMs) to cloud users with various requirements. Thanks to its effectiveness and fairness,auctionhas been widely applied in this heterogeneous resource allocation. Recently, several strategy-proof combinatorial cloud auction mechanisms have been proposed. However, they fail to protect the bid privacy of users from being inferred from the auction results. In this article, we design adifferentially privatecombinatorial cloud auction mechanism (DPCA) to address this privacy issue. Technically, we employ the exponential mechanism to compute a clearing unit price vector with a probability proportional to the corresponding revenue. We further improve the mechanism to reduce the running time while maintaining high revenues, by computing a single clearing unit price, or a subgroup of clearing unit prices at a time, resulting in the improved mechanisms DPCA-S and its generalized version DPCA-M, respectively. We theoretically prove that our mechanisms can guarantee differential privacy, approximate truthfulness and high revenue. Extensive experimental results demonstrate that DPCA can generate near-optimal revenues at the price of relatively high time complexity, while the improved mechanisms achieve a tunable trade-off between auction revenue and running time.

Frame slotted Aloha (FSA) is the de facto MAC layer standard protocol in many ultra-low-power IoT applications, such as Radio Frequency Identification (RFID) and Machine to Machine (M2M) communications. As the age of information (AoI) is an emerging and critical metric for quantifying the freshness of the status update information collected in time-sensitive IoT applications, systematic analysis of AoI for FSA is called for. However, very limited work has been done on this topic despite its both theoretical and practical implications for the operation and optimization of FSA. To fill this void, this paper delivers a comprehensive analysis of AoI for four versions of FSA, namely synchronous and asynchronous FSA with and without retransmission. The core technique of our analysis is to model the AoI for FSA as Markov chains to derive statistics on the delay and inter-delivery time. Our central results consist of the lower bounds of AoI, the exact AoI expressions in the four FSA protocols and the optimum frame length for the AoI of FSA. Our analysis reveals the impact of the arrival rate and the protocol parameters on AoI, and also shows that the retransmission would improve AoI when the arrival rate is small.

With the advent of the COVID-19 pandemic, the shortage in medical resources became increasingly more evident. Therefore, efficient strategies for medical resource allocation are urgently needed. However, conventional rule-based methods employed by public health experts have limited capability in dealing with the complex and dynamic pandemic-spreading situation. In addition, model-based optimization methods such as dynamic programming (DP) fail to work since we cannot obtain a precise model in real-world situations most of the time. Model-free reinforcement learning (RL) is a powerful tool for decision-making; however, three key challenges exist in solving this problem via RL: (1) complex situations and countless choices for decision-making in the real world; (2) imperfect information due to the latency of pandemic spreading; and (3) limitations on conducting experiments in the real world since we cannot set up pandemic outbreaks arbitrarily. In this article, we propose a hierarchical RL framework with several specially designed components. We design a decomposed action space with a corresponding training algorithm to deal with the countless choices, ensuring efficient and real-time strategies. We design a recurrent neural network–based framework to utilize the imperfect information obtained from the environment. We also design a multi-agent voting method, which modifies the decision-making process considering the randomness during model training and, thus, improves the performance. We build a pandemic-spreading simulator based on real-world data, serving as the experimental platform. We then conduct extensive experiments. The results show that our method outperforms all baselines, which reduces infections and deaths by 14.25% on average without the multi-agent voting method and up to 15.44% with it.

Federated learning (FL) is a promising distributed framework for collaborative artificial intelligence model training while protecting user privacy. A bootstrapping component that has attracted significant research attention is the design of incentive mechanism to stimulate user collaboration in FL. The majority of works adopt a broker-centric approach to help the central operator to attract participants and further obtain a well-trained model. Few works consider forging participant-centric collaboration among participants to pursue an FL model for their common interests, which induces dramatic differences in incentive mechanism design from the broker-centric FL. To coordinate the selfish and heterogeneous participants, we propose a novel analytic framework for incentivizing effective and efficient collaborations for participant-centric FL. Specifically, we respectively propose two novel game models for contribution-oblivious FL (COFL) and contribution-aware FL (CAFL), where the latter one implements a minimum contribution threshold mechanism. We further analyze the uniqueness and existence for Nash equilibrium of both COFL and CAFL games and design efficient algorithms to achieve equilibrium solutions. Extensive performance evaluations show that there exists free-riding phenomenon in COFL, which can be greatly alleviated through the adoption of CAFL model with the optimized minimum threshold.

We investigate multiset membership lookup prob-lem, a pivotal functionality in many computing and networking paradigms. We devise compact data structures and lookup algorithms that are amendable for hardware implementation, while guaranteeing high lookup accuracy and supporting interactive query processing. We first propose multi-hash color table, a variant of Bloom filter, to encode subset IDs compactly and map the ID of an item to its subset ID. We further construct a more balanced data structure called balanced multi-hash color table to improve the compactness by integrating load balancing.

We address the problem of persistent item tracking in large-scale data streams. A persistent item refers to the one that persists to occur in the stream over a long timespan. Tracking persistent items is an important and pivotal functionality for many networking and computing applications as persistent items, though not necessarily contributing significantly to the data volume, may convey valuable information on the data pattern about the stream. The state-of-the-art solutions of tracking persistent items require to know the monitoring time horizon to set the sampling rate. This limitation is further accentuated when we need to track the persistent items in recent w slots where w can be any value between 0 and T to support different monitoring granularity. Motivated by this limitation, we develop a persistent item tracking algorithm that can function without knowing the monitoring time horizon beforehand, and can thus track persistent items up to the current time t or within a certain time window at any moment. Our central technicality is adaptively reducing the sampling rate such that the total memory overhead can be limited while still meeting the target tracking accuracy. Through both theoretical and empirical analysis, we fully characterize the performance of our proposition.

We revisit the problem of missing tag identification in RFID networks by making three contributions. Firstly, we quantitatively compare and gauge the existing propositions spanning over a decade on missing tag identification. We show that the expected execution time of the best solution in the literature is $\Theta \left( {N + \frac{{{{(1 - \alpha )}^2}{{(1 - \delta )}^2}}}{{{\varepsilon ^2}}}} \right)$, where δ and ϵ are parameters quantifying the required identification accuracy, N denotes the number of tags in the system, among which αN tags are missing. Secondly, we analytically establish the expected execution time lower-bound for any missing tag identification algorithm as $\Theta \left( {\frac{N}{{\log N}} + \frac{{{{(1 - \delta )}^2}{{(1 - \alpha )}^2}}}{{{\varepsilon ^2}\log \frac{{(1 - \delta )(1 - \alpha )}}{\varepsilon }}}} \right)$, thus giving the theoretical performance limit. Thirdly, we develop a novel missing tag identification algorithm by leveraging a tree structure with the expected execution time of $\Theta \left( {\frac{{\log \log N}}{{\log N}}N + \frac{{{{(1 - \alpha )}^2}{{(1 - \delta )}^2}}}{{{\varepsilon ^2}}}} \right)$, reducing the time overhead by a factor of up to log N over the best algorithm in the literature. The key technicality in our design is a novel data structure termed as collision-partition tree (CPT), built on a subset of bits in tag pseudo-IDs, leading to more balanced tree structure and reducing the time complexity in parsing the entire tree.

We investigate the following batching task scheduling problem. There is a set of tasks to be executed on a number of machines. Some tasks can be executed simultaneously on a single machine, while others require exclusive use of an entire machine. The scheduler needs to find a schedule giving optimum system utility. We develop an algorithmic framework for this batching task scheduling by investigating four formulations of the problem, the bounded and unbounded batching, depending on whether the number of simultaneously executable tasks is bounded, the synchronous and asynchronous batching, depending on whether the batched tasks need to start synchronously. For each formulation, we develop our approximation algorithm whose approximation ratio outperforms the best existing result. We further perform numerical simulations in a wide variety of system settings to complement our theoretical analysis and demonstrate the effectiveness of our scheduling algorithms.

With increasing deployment of electric vehicles in urban mobility-on-demand systems, electric taxis (e-taxi) drivers need to compete with each other not only for passengers but also for limited charging points due to frequent and time-consuming charging activities. This paper focuses on two crucial research questions in this context: (1) What is the strategy of each e-taxi driver for charging and searching passengers in a non-cooperative environment, and what is the collective system outcome of competing e-taxis? (2) How can the mobility-on-demand service platforms (e.g., Uber and Lyft) push self-interested e-taxi drivers to improve the overall system efficiency. Technically, we study the non-cooperative mobility-on-demand system consisting of e-taxis from a game theoretic perspective. We formulate a mobility-on-demand system with competition among drivers as a stochastic game, analyze the Nash Equilibrium (NE) of the game, and design an approximation algorithm to obtain the NE. Moreover, we show that the NE is not necessarily efficient for the platform and propose a pricing scheme from the platform's perspective which induces the new NE to be efficient. We use a trace-driven simulation to evaluate the design based on datasets consisting of more than 7,000 fuel vehicles and nearly 700 e-taxis, 37 working charging stations, and more than 60,000 passenger trips per day. We show that, compared with the state-of-the-art which optimizes the system efficiency by coordinating e-taxis but is not an equilibrium, the NE achieves a system efficiency of merely 73.5% of that of the cooperative state-of-the-art, and the designed pricing scheme improves the price of anarchy to 95.5 %.

Abstract The diagnosability is one of the most important measures of the reliability of networks. Consider the setting where there are large-scale failures that disconnect the network and result in many components. Then, the diagnosability is closely related to the number of components. In this paper, we define and study the $\boldsymbol{g}$-component diagnosability of network $\boldsymbol{G}$, which is denoted by $\boldsymbol{ct_g(G)}$ and has not been addressed before. $\boldsymbol{ct_g(G)}$ is the maximum number of nodes in the faulty node set $\boldsymbol{F}$ of $\boldsymbol{G}$ such that $\boldsymbol{G-F}$ has at least $\boldsymbol{g}$ components and diagnosis model can identify all nodes in $\boldsymbol{F}$. Under PMC and MM$^*$ diagnosis models, we show that, in the hypercube $\boldsymbol{Q_n\ (n\geq 7)}$, $\boldsymbol{ct_{g+1}(Q_n)=-(1/2)g^2+(n-3/2)g+n}$ when $\boldsymbol{g\leq n-1}$. Moreover, we determine the $\boldsymbol{(n+1)}$-component diagnosability $\boldsymbol{ct_{n+1}(Q_n)=n^2/2+n/2-2}$ for $\boldsymbol{n\geq 7}$.

Missing item event detection is one of the most important radio-frequency identification (RFID)-enabled functions. Yet it is largely unaddressed how to fast and reliably detect missing item event in multitagged RFID systems where multiple tags are tagged on one item. The canonical methods can only solve tag-level detection problem where each item is associated with one tag, and applying them to detect the missing multitagged items would falsely alarm and is time inefficient. To bridge the gap, this article formulates and analyzes the missing multitagged item detection problem. Our key idea is to search the proper seeds so that the reader only needs to probe a subset of the tags each being selected from different items instead of the entire tag set for the missing item detection. By employing the computation-communication tradeoffs, we design two protocols named M2ID and M2ID+ that classifies the tags before the segmentation compared to the former to improve time efficiency. With the derived optimum parameters, our protocols can achieve up to$4\times$performance gain in terms of time efficiency compared with the state-of-the-art solution.

There is an increasing need for charging station recommendation to minimize the overall charging time for electric vehicles and balance load for the charging stations. To grant this need, we model the recommendation problem as a Markov Decision Process (MDP) problem. However, the traditional MDP model has the issue of ‘curse of dimensionality’. To address this issue, we propose an extension of MDP: multiple-phase MDP, in which the state transition of MDP is decomposing into several phases, so as to reduce the state space and state transition complexities. This is done by introducing two states other than the normal state defined in MDP: post decision state and intermediate decision state. Then, we propose an online learning based algorithm to solve the formulated multiple-phase MDP model. Thanks to the reduced complexities of the state space and state transition, the proposed online algorithm can converge fast. By comparing to other recommendation mechanisms, such as game theory based recommendation and Q-learning based recommendation, our simulation evaluation demonstrates that our proposition can bring good performance.

Given a dataset$\mathcal S$composed of$g$subsets with each data item belonging to one of them,multiset membership lookuptakes an item$e$as input and outputs a binary answer whether$e\in {\mathcal S}$and, in case of yes, the ID of the subset to which$e$belongs. Overlaid upon while more sophisticated than the canonical membership lookup, multiset membership lookup emerges as a pivotal functionality in many computing and networking paradigms. The quest to achieve high-speed, high-accuracy lookup with limited memory cost makes lookup algorithm design a challenging task, particularly when the data items arrive as a stream. In this paper, we devise compact data structures and lookup algorithms that are amendable for hardware implementation, while guaranteeing high lookup accuracy and supporting interactive query processing. We first proposemulti-hash color table, a variant of Bloom filter, to encode subset IDs compactly and map the ID of an item to its subset ID. We further construct a more balanced data structure calledbalanced multi-hash color tableto improve the compactness by integrating the state-of-the-art load balancing technique. We complete our work by addressing the case ofbatch arrivalsand design a batched recording algorithm optimizing the memory efficiency. We give both theoretical and empirical analysis to characterize and evaluate the performance of the proposed algorithms in terms of lookup accuracy, memory and access efficiency.

We study a class of generic charging path optimization problems arising from emerging networking applications, where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We show that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design quasi-polynomial-time algorithms achieving logarithmic approximation to the optimum charging path. Our approximation algorithms can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget.

We formulate and analyze a fundamental downlink transmission scheduling problem in a wireless communication system, composed of a base station and a set of users, each requesting a packet to be served within a time window. Some packets are requested by several users and can be served simultaneously due to the broadcast nature of the wireless medium. The base station can choose from a set of transmission strategies, e.g., in terms of combination of data rate and coding scheme, to serve the users. Each request can be served by a subset of transmission strategies. We seek a downlink transmission scheduling algorithm generating maximum aggregated system-wide utility. In this paper, we develop approximation algorithms for the formulated downlink transmission scheduling problem in both offline and online settings. We first establish the NP-hardness of the offline scheduling problem and the approximation hardness and bound of the online scheduling problem in non-preemptive and preemptive-restart models, respectively. We then design approximation algorithms and derive the approximation and competitive ratios of our online and offline scheduling algorithms. Numerical simulations are performed to further evaluate our algorithms in a wide range of network settings.

We formulate and analyze a generic task scheduling problem: a set of tasks need to be executed on a pool of continuous resource such as spectrum and memory, each requiring a certain amount of time and contiguous resource; some tasks can be executed simultaneously in batch by sharing the resource, while others requiring exclusive use of the resource. We seek an optimal resource allocation and the related scheduling policy maximizing the overall system utility. This problem, termed as the contiguous-resource batching task scheduling problem, arises in a variety of engineering fields, where communication and storage resources are potential bottlenecks and thus need to be carefully scheduled. Two motivating examples are the spectrum bonding problem in dynamic spectrum access systems and the dynamic storage allocation problem in computer systems. In this paper, we investigate both offline and online scheduling settings. We first establish the NP-hardness of the offline setting and the inapproximability of the online setting in its generic form. Given the theoretical performance limit, we then develop approximation algorithms with mathematically proven performance guarantee in terms of approximation and competitive ratios for the offline and online settings.

We formulate and investigate the problem of distributed channel rendezvous in collision-prone wireless networks. Existing researches on this topic are mainly devoted to designing channel hopping sequences, each pair of which can overlap on a common channel within bounded delay. However, this overlap-based canonical rendezvous design does not take into account channel collision, which may render existing rendezvous algorithms fail to achieve bounded delay in collision-prone environment. Motivated by this observation, we formulate and investigate the collision-aware channel rendezvous problem in a generic scenario, where a collision occurs if more than$C$packets overlap in time on a same channel. Our generic formulation allows to model both the baseline single packet reception model with$C=1$and the more sophisticated multiple packet reception model with$C > 1$. We further abstract the collision-aware rendezvous problem as the problem of constructing a robust rendezvous system. We establish the theoretical limit of the problem, guided by which we design a collision-resilient distributed rendezvous algorithm with truly bounded rendezvous delay. We then demonstrate the performance of our rendezvous algorithm both analytically and numerically.

We formulate and analyze a generic sequential resource access problem arising in a variety of engineering fields, where a user disposes a number of heterogeneous computing, communication, or storage resources, each characterized by the probability of successfully executing the user's task and the related access delay and cost, and seeks an optimal access strategy to maximize her utility within a given time horizon, defined as the expected reward minus the access cost. We develop an algorithmic framework on the (near-)optimal sequential resource access strategy. We first prove that the problem of finding an optimal strategy is NP-hard in general. Given the hardness result, we present a greedy strategy implementable in linear time, and establish the closed-form sufficient condition for its optimality. We then develop a series of polynomial-time approximation algorithms achieving (ϵ, δ)-optimality. The key components in our design include a pruning process eliminating dominated strategies, thus maintaining polynomial time and space overhead, and a comprehensive scheme allowing flexibly trading-off time and space overhead against performance guarantee.

Facing the outbreak of COVID-19, shortage in medical resources becomes increasingly outstanding. Therefore, efficient strategies for medical resource allocation are urgently called for. Reinforcement learning (RL) is powerful for decision making, but three key challenges exist in solving this problem via RL: (1) complex situation and countless choices for decision making in the real world; (2) only imperfect information are available due to the latency of pandemic spreading; (3) limitations on conducting experiments in real world since we cannot set pandemic outbreaks arbitrarily. In this paper, we propose a hierarchical reinforcement learning method with a corresponding training algorithm. We design a decomposed action space to deal with the countless choices to ensure efficient and real time strategies. We also design a recurrent neural network based framework to utilize the imperfect information obtained from the environment. We build a pandemic spreading simulator based on real world data, serving as the experimental platform. We conduct extensive experiments and the results show that our method outperforms all the baselines, which reduces infections and deaths by 14.25% on average.

Moving Target Defense (MTD) is a powerful weapon to mitigate cyber attacks by increasing the attacker's efforts and complexity in fulfilling its goal. One effective technique of MTD is to deploy diverse implementations and configurations to provide equivalent functionality so as to increase the network resilience. In this paper, we investigate the algorithmic aspect of employing diversity to cause the network to be the most resilient possible. Specifically, we study two algorithmic optimization problems of both theoretical and practical importance: (1) given the network topology, how to assign different variants to different network nodes so as to maximize the network resilience; (2) when the variant assignment is fixed, but the network topology is configurable, what is the optimal topology maximizing the network resilience. We mathematically formulate the problems of variant assignment and network topology configuration and develop efficient algorithms, which can serve as design guidelines in the deployment of diversity-based MTD techniques to enhance the security of the network.

Mobile-edge computing (MEC) has emerged as a promising supporting architecture providing a variety of resources to the network edge, thus acting as an enabler for edge intelligence services empowering massive mobile and Internet-of-Things (IoT) devices with artificial intelligence (AI) capability. With the assistance of edge servers, user equipments (UEs) are able to run deep neural network (DNN)-based AI applications, which are generally resource hungry and computation intensive such that an individual UE can hardly afford by itself in real time. However, the resources in each individual edge server are typically limited. Therefore, any resource optimization involving edge servers is by nature a resource-constrained optimization problem and needs to be tackled in such a realistic context. Motivated by this observation, we investigate the optimization problem of DNN partitioning (an emerging DNN offloading scheme) in a realistic multiuser resource-constrained condition that rarely considered in previous works. Despite the extremely large solution space, we reveal several properties of this specific optimization problem of joint multi-UE DNN partitioning and computational resource allocation. We propose an algorithm called iterative alternating optimization (IAO) that can achieve the optimal solution in polynomial time. In addition, we present a rigorous theoretic analysis of our algorithm in terms of time complexity and performance under realistic estimation error. Moreover, we build a prototype that implements our framework and conducts extensive experiments using realistic DNN models, whose results demonstrate its effectiveness and efficiency.

The explosive deployment of the Internet of Things (IoT) brings a massive number of light-weight and energy-limited IoT devices, challenging stable wireless access. Energy-efficient, Frame Slotted Aloha (FSA) recently emerged as a promising MAC protocol for large-scale IoT systems such as Machine to Machine (M2M) and Radio Frequency Identification (RFID). Yet the stability of FSA and how to stabilize it, despite of its fundamental importance on the effective operation in practical systems, have not been systematically addressed. In order to bridge this gap, we devote this paper to designing stable FSA-based access protocol (SFP) to stabilize IoT systems. We first design an additive active node population estimation scheme and use the estimate to set frame size and participation probability for throughput optimization. We then carry out theoretical analysis demonstrating the stability of SFP in the sense of geometric ergodicity of Markov chain derived from dynamics of the active node population and its estimate. Our central theoretical result is a set of closed-form conditions on the stability of SFP. We further conduct extensive simulations whose results confirm our theoretical analysis and demonstrate the effectiveness of SFP.

Facing the worldwide rapid spreading of COVID-19 pandemic, we need to understand its diffusion in the urban environments with heterogeneous population distribution and mobility. However, challenges exist in the choice of proper spatial resolution, integration of mobility data into epidemic modelling, as well as incorporation of unique characteristics of COVID-19.

Input is a significant problem for wearable devices, particularly for head-mounted virtual and augmented reality systems. Contemporary AR/VR systems use in-air gestures or handheld controllers for interactivity. However, mid-air handwriting provides a natural, subtle, and easy-to-use way to input commands and text. In this demo, we propose and investigate ViFin, a new technique for input commands and text entry which tracks continuous micro finger-level writing with a commodity smartwatch through vibrations. Inspired by the recurrent neural aligner and transfer learning, ViFin recognizes continuous finger writing and works across different users and achieves an accuracy of 90% and 91% for recognizing numbers and letters, respectively. Finally, a real-time writing system with two specific applications using AR smartglasses are implemented.

Smartwatches, which are small and portable, have become dominant devices in the wearable ecosystem. However, due to the limited size of the touch screens, smartwatches typically have a poor interactive experience for users. In our previous work [3, 4], we studied appropriating the human body as a surface to extend the input through tapping-induced vibrations. In this demo, we extend previously published research by presenting a brand-new product: a smartwatch that provides on-body tapping gestures recognition. We design eight tapping gestures for four applications on the new smartwatch: music players, shortcuts, cameras, and phone calls. In 2020, we collaborated with Mad Gaze [1] and launched this smartwatch on a crowdfunding platform. Our smartwatch has exceeded the crowdfunding target amount by 27 times.

With the rapid development of radio-frequency identification (RFID) technology, the ever-increasing research effort has been dedicated to devising various RFID-enabled services. The missing event detection, the functionality of detecting missing objects, is one of the most important services in many Internet-of-Things applications such as inventory management. Prior detection protocols only work in single-tagged RFID systems and would waste much time on repeated checks on one object in the emerging multitagged systems where each object is attached by multiple tags, leaving efficient detection in the new scenario unaddressed. To bridge the gap, this article is devoted to detecting missing multitagged objects. The key technicality is to build a filter from a subset of tags instead of whole in prior works to avoid repeated detections of one object and reduce detection time. Specifically, we first provide a basic solution based on the Bloom filter which can specify only tags in the chosen subset to participate in the final detection. To further improve time efficiency, we propose an advanced protocol that exploits tag ID knowledge and sparsity of slots mapped by only tags in the chosen subset to build a more compact compressive filter. Moreover, a composite vector is used to efficiently coordinate tags to report its presence. We conduct theoretical analysis on optimum protocol parameters and extensive simulations to verify the feasibility of the protocols. The results show that the advanced protocol achieves more than$2\times $performance gain in terms of time efficiency over the Bloom filter-based basic protocol.

Low-power wireless communication has been widely used in cyber-physical systems that require time-critical data delivery. Achieving this goal is challenging because of link burstiness and interference. Based on significant empirical evidence of 21 days and over 3.6 M packet transmissions per link, we propose both routing and scheduling algorithms that produce latency bounds of the real-time periodic streams and accounts for both link bursts and interference. The solution is achieved through the definition of a new metric B max that characterizes links by their maximum burst length, and by choosing a novel least-burst-route that minimizes the sum of worst-case burst lengths over all links in the route. With extensive data-driven analysis, we show that our algorithms outperform existing solutions by achieving accurate latency bound with much less energy consumption. In addition, a testbed evaluation consisting of 48 nodes spread across a floor of a building shows that we obtain 100% reliable packet delivery within derived latency bounds. We also demonstrate how performance deteriorates and discuss its implications for wireless networks with insufficient high-quality links.

With rapid development of radio frequency identification (RFID) technology, ever-increasing research effort has been dedicated to devising various RFID-enabled services. The missing tag identification, which is to identify all missing tags, is one of the most important services in many Internet-of-Things applications such as inventory management. Prior work on missing tag detection all rely on hash functions implemented at individual tags. However, in reality hash functions are not supported by commercial off-the-shelf (COTS) RFID tags. To bridge this gap between theory and practice, this paper is devoted to detecting missing tags with COTS Gen2 devices. We first introduce a point-to-multipoint protocol, named P2M that works in an analog frame slotted Aloha paradigm to interrogate tags and collect their electronic product codes (EPCs). A missing tag will be found if its EPC is not present in the collected ones. To reduce time cost of P2M resulted from tag response collisions, we further present a collision-free point-to-point protocol, named P2P that selectively specifies a tag to reply with its EPC in each slot. If the EPC is not received, this tag is regarded to be missing. We develop two bitmask selection methods to enable the selective query while reducing communication overhead. We implement P2M and P2P with COTS RFID devices and evaluate their performance under diverse settings.

Ever-increasing research efforts have been dedicated to radio frequency identification (RFID) systems, such as finding top-k, elephant groups, and missing-tag detection. While group labeling, which is how to tell tags their associated group data, is the common prerequisite in many RFID applications, its efficiency is not well optimized due to the transmission of useless data with only one seed used. In this paper, we introduce a unified protocol called GLMS which employs multiple seeds to construct a composite indicator vector (CIV), reducing the useless transmission. Technically, to address Seed Assignment Problem (SAP) arising during building CIV, we develop an approximation algorithm (AA) with a competitive ratio 0.632 by globally searching for the seed contributing to the most useful slot. We then further design two simplified algorithms through local searching, namely c-search-I and its enhanced version c-search-II, reducing the complexity by one order of magnitude while achieving comparable performance. We conduct extensive simulations to demonstrate the superiority of our approaches.

Map matching is important in many trajectory based applications like route optimization and traffic schedule, etc. As the widely used methods, Hidden Markov Model and its variants are well studied to provide accurate and efficient map matching service. However, HMM based methods fail to utilize the value of enormous trajectory big data, which are useful for the map matching task. Furthermore, with many following-up works, they are still easily influenced by the noisy records, which are very common in the real system. To solve these problems, we revisit the map matching task from the data perspective, and propose to utilize the great power of data to help solve these problems. We build a deep learning based model to utilize all the trajectory data for joint training and knowledge sharing. With the help of embedding techniques and sequence learning model with attention enhancement, our system does the map matching in the latent space, which is tolerant to the noise in the physical space. Extensive experiments demonstrate that our model outperforms the widely used HMM based methods more than 10% (absolute accuracy) and works robustly in the noisy settings in the meantime.

In this paper, we propose a truthful combinatorial auction for the joint radio and processing resource allocation problem in the context of a Cloud-based Radio Access Network (C-RAN). We formulate the auction as an Integer Linear Program (ILP), taking into accurate account interference constraints while leveraging radio resource reuse to generate an optimal revenue for the RAN operator. Then, we propose Truthful Greedy Approach (TGA), an effective and truthful heuristic that guarantees a close-to-optimum revenue compared to the one obtained with the ILP formulation. Extensive simulations, conducted in representative network scenarios, compare and evaluate our auction with state-of-the-art approaches from the literature, showing its effectiveness.

In decentralised cognitive radio (CR) networks, establishing communication sessions between a communicating pair requires them to meet each other on a common channel via a ‘rendezvous’ process. Devising distributed CR rendezvous protocol is a challenging task as cognitive nodes are not necessarily synchronised, and may have different perceptions of channel availability. In this study, the authors present M‐Rendezvous , an order‐optimal rendezvous protocol exploiting the performance gain brought by having multiple radios at cognitive nodes. As a distinguished feature, M‐Rendezvous is a unified rendezvous protocol that can operate in both homogenous case where both of the rendezvous nodes are equipped with only one radio or multiple radios, and heterogeneous case where one of the rendezvous nodes has single radio and the other has multiple radios. In both cases, by rigorous analysis, the authors demonstrate that M‐Rendezvous can guarantee rendezvous over every channel with bounded and order‐minimal delay even when rendezvous nodes have asynchronous clocks and asymmetrical channel perceptions.

Tag search, which is to find a particular set of tags in a radio frequency identification (RFID) system, is a key service in such important Internet-of-Things applications as inventory management. When the system scale is large with a massive number of tags, deterministic search can be prohibitively expensive, and probabilistic search has been advocated, seeking a balance between reliability and time efficiency. Given a failure probability$\frac {1}{\mathcal {O}(K)}$, where$K$is the number of tags, state-of-the-art solutions have achieved a time cost of$\mathcal {O}(K \log K)$through multi-round hashing and verification. Further improvement, however, faces a critical bottleneck of repetitively verifying each individual target tag in each round. In this paper, we present an efficient tree-based tag search (TTS) that approaches$\mathcal {O}(K)$through batched verification. The key novelty of TTS is to smartly hash multiple tags into each internal tree node and adaptively control the node degrees. It conducts bottom–up search to verify tags group by group with the number of groups decreasing rapidly. Furthermore, we design an enhanced tag search scheme, referred to as TTS+, to overcome the negative impact of asymmetric tag set sizes on time efficiency of TTS. TTS+ first rules out partial ineligible tags with a filtering vector and feeds the shrunk tag sets into TTS. We derive the optimal hash code length and node degrees in TTS to accommodate hash collisions and the optimal filtering vector size to minimize the time cost of TTS+. The superiority of TTS and TTS+ over the state-of-the-art solution is demonstrated through both theoretical analysis and extensive simulations. Specifically, as reliability demand on scales, the time efficiency of TTS+ reaches nearly 2 times at most that of TTS.

We revisit the opportunistic scheduling problem in which a server opportunistically serves multiple classes of users under time-varying multi-state Markovian channels. The aim of the server is to find an optimal policy minimizing the average waiting cost of those users. Mathematically, the problem can be recast to a restless multiarmed bandit one, and a pivot to solve restless bandit by the Whittle index approach is to establish indexability. Despite the theoretical and practical importance of the Whittle index policy, the indexability is still open for opportunistic scheduling in the heterogeneous multi-state channel case. To fill this gap, we mathematically identify a set of sufficient conditions on a channel state transition matrix under which the indexability is guaranteed and consequently, the Whittle index policy is feasible. Furthermore, we obtain the closed-form Whittle index by exploiting the structural property of the channel state transition matrix. For a generic channel state transition matrix, we propose an eigenvalue-arithmetic-mean scheme to obtain the corresponding approximate matrix which satisfies the sufficient conditions, and consequently can get an approximate Whittle index. This paper constitutes a small step toward solving the opportunistic scheduling problem in its generic form involving multi-state Markovian channels and multi-class users.

We consider the multichannel opportunistic access problem, in which a user decides, at each time slot, which channel to access among multiple Gilbert-Elliot channels in order to maximize his aggregated utility (e.g., the expected transmission throughput) given that the observation of channel state is error-prone. The problem can be cast into a restless multiarmed bandit problem which is proved to be PSPACE-Hard. An alternative approach, given the problem hardness, is to look for simple channel access policies. Whittle index policy is a very popular heuristic for restless bandits, which is provably optimal asymptotically and has good empirical performance. In the case of imperfect observation, the traditional approach of computing the Whittle index policy cannot be applied because the channel state belief evolution is no more linear, thus rendering the indexability of our problem open. In this paper, we mathematically establish the indexability and establish the closed-form Whittle-index, based on which index policy can be constructed. The major technique in our analysis is a fixed point based approach which enable us to divide the belief information space into a series of regions and then establish a set of periodic structures of the underlying nonlinear dynamic evolving system, based on which we devise the linearization scheme for each region to establish indexability and compute the Whittle index for each region.

Searching for a particular group of tags in an RFID system is a key service in such important Internet-of-Things applications as inventory management. When the system scale is large with a massive number of tags, deterministic search can be prohibitively expensive, and probabilistic search has been advocated, seeking a balance between reliability and time efficiency. Given a failure probability [1/(O(K))], where K is the number of tags, state-of-the-art solutions have achieved a time cost of O(K log K) through multi-round hashing and verification. Further improvement however faces a critical bottleneck of repetitively verifying each individual target tag in each round. In this paper, we present a novel Tree-based Tag Search (TTS) that approaches O (K) through batched verification. TTS smartly hashes multiple tags into each internal tree node and adaptively controls the node degrees. It conducts bottom-up search to verify tags group by group with the number of groups decreasing rapidly. We derive the optimal hash code length and node degrees to accommodate hash collisions, and demonstrate the superiority of TTS through both theoretical analysis and extensive simulations. In particular, we show that, with increasing reliability demand and system size, TTS achieves an even higher performance gain, making it a highly scalable solution.

With rapid development of radio frequency identification (RFID) technology, ever-increasing research effort has been dedicated to devising various RFID-enabled services. The key tag monitoring, which is to detect anomaly of key tags, is one of the most important services in such important Internet-of-Things applications as inventory management. Yet prior work assumes that all tags are armed with hashing functionality and a reader would report channel states in every slot, which is not supported by commercial off-the-shelf (COTS) RFID tags and readers. To bridge this gap, this paper is devoted to enabling key tag monitoring service with COTS devices. In particular, we introduce two anomaly monitoring protocols to detect whether there is any key tag absent from the system. The first protocol employs Q-query that works in an analog frame slotted Aloha paradigm to interrogate tags and collect tag IDs. An anomaly event will be found if at least one key tag ID is not present in the collected ones. To reduce time cost of the first protocol resulted from tag collisions, we present a collision-free method that uses select-query to specify a key tag to reply in each slot. Once there is no response in a slot, the specified key tag is regarded as a missing tag. We conduct experiments to evaluate two protocols.

Cognitive radio has been widely recognized as a promising solution to reliable and time-efficient wireless sensor networks. However, cognitive capability requires an extra energy consumption in spectrum sensing and spectrum access, which imposes a rather challenging problem to low cost sensors. This paper proposes a short preamble cognitive medium access control (SPC-MAC) protocol which supports reliable and fast spectrum access while addressing the energy conservation problem in cognitive radio sensor networks (CRSNs). The novelty of SPC-MAC lies in the combination of short preamble sampling (for supporting low duty cycling in CRSNs) and the opportunistic forwarding (for reliable and fast transmission). Because of the self-organizing nature, SPC-MAC does not require a common control channel. Extensive simulations demonstrate the advantage of SPC-MAC over existing works in terms of energy consumption and throughput.

Cooperative multicast has been demonstrated to achieve significant performance gain over the classic source-destination transmission paradigm by exploiting spatial diversity through the participation of multiple relay nodes. As a major technical challenge, the selection of relays for a multicast session has significant impact on the multicast performance. The challenge is even more pronounced when the number of channels is limited as the relay selection is in this context coupled with channel allocation. The goal of this paper is to design a fair multicast relay selection scheme with limited channel resources. Specifically, we establish an analytical framework for this joint relay selection and channel allocation problem and develop a lexicographic max-min multicast relay selection scheme. Our design consists of two technical steps. First, we consider the maximization of the minimal data rate. By decoupling relay selection and channel allocation, the problem is transformed to a max-min-max problem, which is difficult to solve. To make this problem tractable, we reformulate it as a convex optimization problem via relaxation and smoothing, and prove the asymptotic equivalence from a geometrical perspective. Second, we propose an adjustment algorithm based on the initial max-min solution, and prove that the proposed scheme achieves lexicographic optimality. Finally, our proposed algorithm is evaluated by simulation to show its superiority over the conventional schemes.

Spectrum aggregation (SA) across heterogeneous channels, including both dedicated and shared channels, provides the potential for improving spectrum utilization and fulfilling the requirement of broadband services. Heterogeneous SA brings new technical challenges on multisystem coexistence on shared channels and the resource allocation over heterogeneous channels. In this paper, we develop an analytical framework for heterogeneous SA from a queue stability perspective. To make all systems on the shared channels stable, we design a resource allocation algorithm for the coexistence of multiple systems. Specifically, we derive the closed-form modified water-filling power control for the single-pair case by Lyapunov optimization and prove that it achieves the queue stability for all systems. Based on the results, we propose a low-complexity suboptimal resource allocation algorithm for multipair SA, which is a NP-hard problem. We partition user pairs into groups by using graph coloring and allocate the shared channels to pair groups according to the maximal weight bipartite matching model. The simulation results verify the queue stability and show that the proposed schemes outperform the conventional schemes.

Database-driven spectrum access is regarded as an effective spectrum redistribution mechanism. However, dialoguing with the spectrum database requires both primary and secondary users to reveal their sensitive data to the spectrum database manager (SDM), leading to serious privacy concerns. In this paper, we show that the SDM can perform database operations (both updates and queries) without knowing any information about the users' sensitive inputs and the database contents, by combining garbled circuits and secret sharing. Our design uses data-oblivious sorting networks to leverage parallelism of query operations, yielding an efficient query algorithm. We further combine secure computations with authentication techniques to get a verification mechanism for correctness checking. As far as we know, our proposal is the first secure and verifiable database-driven spectrum sharing scheme protecting both primary users' (PUs') and secondary users' (SUs') privacies. Finally, we fully implement our system, and demonstrate that even on commodity PC, our implementation suffers mild performance overhead.

We investigate the opportunistic scheduling problem where a server opportunistically serves multiple classes of users under time varying multi-state Markovian channels. The aim of the server is to find an optimal policy minimizing the average waiting cost of users. Mathematically, the problem can be cast to a restless bandit one, and a pivot to solve restless bandit by index policy is to establish indexability. We mathematically propose a set of sufficient conditions on channel state transition matrix, and consequently, the index policy is feasible. Our work consists of a small step toward solving the opportunistic scheduling problem in its generic form involving multi- state Markovian channels and multi-class users.

We formulate and study a broadcast problem arising in multi-channel duty cycling wireless body area networks (WBANs), where the sink needs to broadcast the control message to all sensor nodes. The objective is to design robust multichannel wake-up schedule with minimum worst-case broadcast delay while guaranteeing the full broadcast diversity regardless of clock drifts and asymmetric duty cycles. To that end, we first derive the lower-bound of worst-case broadcast delay with full diversity of any broadcast protocol and then design a multichannel broadcast protocol (MCB) that satisfies the performance requirement for the latency and diversity. Finally, the simulation results demonstrate the capability of MCB of ensuring successful broadcast delivery on every channel within the theoretical worst-case broadcast delay, even under asymmetric duty cycles and any amount of clock drifts.

Ever-increasing research effort has been dedicated to multi-group radio frequency identification (RFID) systems where all tags are partitioned into multiple groups, such as group-level queries, and multi-group missing tag detection. However, it is assumed in the existing work that all tags know their individual group IDs, which thus leaves group labeling problem unaddressed. To tackle the under-investigated problem, this paper is devoted to devising an efficient group labeling protocol to inform each tag of its corresponding group ID fast and accurately. To this end, we employ multiple seeds to build a Composite Indicator Vector (CIV) indicating the assigned seed in each slot, which reduces transmissions of useless information and thus improves time efficiency. Specifically, we first theoretically show that the Seed Assignment Problem (SAP) arising in establishing the CIV is NP-hard and then develop a myopic approximation algorithm. Finally, the simulation results confirm the superiority of the proposed protocol over the state-of-the-art solution in terms of time efficiency.

Cooperative multicast has been demonstrated to achieve significant performance gain over the classic source-destination transmission paradigm by exploiting spatial diversity through the participation of multiple relay nodes. As a major technical challenge, the selection of relays for a multicast session has significant impact on the multicast performance. The challenge is even more pronounced when the number of channels are limited as the relay selection is in this context coupled with channel allocation. We establish an analytical framework for joint relay selection and channel allocation problem and develop a lexicographic max-min multicast relay selection scheme. Our design consists of two technical steps. 1) We consider the maximization of the minimal data rate. By decoupling relay selection and channel allocation, the problem is transformed to a max-min-max problem, which is difficult to solve. To make this problem tractable, we reformulate it as a convex optimization problem via relaxation and smoothing, and prove the asymptotic equivalence from a geometrical perspective. 2) We propose an adjustment algorithm based on the initial max-min solution, and prove that the proposed scheme achieves lexicographic optimality.

We formulate and study a broadcast problem arising in multichannel duty-cycling wireless body area networks (WBANs) which the sink needs to broadcast control information to all sensor nodes on or implanted in the human body. Despite its fundamental importance for the network configuration and secure key management, the multichannel broadcast problem is largely unaddressed in duty-cycling WBANs. In this paper, we devise novel 2-D scheduling specifying the rule of channel hopping and wake-up time slot selection, which achieves the order-minimal worst-case broadcast delay while guaranteeing the full broadcast diversity regardless of clock drifts and asymmetric duty cycles and channel perceptions. Specifically, we first employ the Chinese remainder theorem to design an effective multichannel broadcast (MCB) algorithm and further propose improved MCB that enhances the granularity of MCB in matching actual duty cycles and number of channels, reducing the theoretically worst-case broadcast delay of MCB by up to 75%. We demonstrate the performance of the proposed algorithms through theoretical analysis and extensive simulations.

We consider the channel access problem arising in opportunistic scheduling over fading channels, cognitive radio networks, and server scheduling. The multi-channel communication system consists of N channels. Each channel evolves as a time-nonhomogeneous multi-state Markov process. At each time instant, a user chooses M channels to transmit information, and obtains some reward, i.e., throughput, based on the states of the chosen channels. The objective is to design an access policy, i.e., which channels should be accessed at each time instant, such that the expected accumulated discounted reward is maximised over a finite or infinite horizon. The considered problem can be cast into a restless multi-armed bandit (RMAB) problem, which is PSPACE-hard, with the optimal policy usually intractable due to the exponential computation complexity. Hence, a natural alternative is to consider the easily implementable myopic policy that only maximises the immediate reward but ignores the impact of the current strategy on the future reward. In this paper, we perform an analytical study on the performance of the myopic policy for the considered RMAB problem, and establish a set of closed-form conditions to guarantee the optimality of the myopic policy.

Radio frequency identification technology has been widely used in missing tag detection to reduce and avoid inventory shrinkage. In this application, promptly finding out the missing event is of paramount importance. However, the existing missing tag detection protocols cannot efficiently handle the presence of a large number of unexpected tags whose IDs are not known to the reader, which shackles the time efficiency. To deal with the problem of detecting missing tags in the presence of unexpected tags, this paper introduces a two-phase Bloom filter-based missing tag detection (BMTD) protocol. The proposed BMTD exploits Bloom filter in sequence to first deactivate the unexpected tags and then test the membership of the expected tags, thus dampening the interference from the unexpected tags and considerably reducing the detection time. Moreover, the theoretical analysis of the protocol parameters is performed to minimize the detection time of the proposed BMTD and achieve the required reliability simultaneously. In addition, we derive a critical threshold on the unexpected tag size for the execution of first phase in BMTD. Extensive experiments are then conducted to evaluate the performance of the proposed BMTD. The results demonstrate that the proposed BMTD significantly outperforms the state-of-the-art solutions.

Frame Slotted Aloha (FSA) protocol has been widely applied in Radio Frequency Identification (RFID) systems as the de facto standard in tag identification. However, very limited work has been done on the stability of FSA despite its fundamental importance both on the theoretical characterization of FSA performance and its effective operation in practical systems. In order to bridge this gap, we devote this paper to investigating the stability properties of p-persistent FSA by focusing on two physical layer models of practical importance, the models with single packet reception and multipacket reception capabilities. Technically, we model the FSA system backlog as a Markov chain with its states being backlog size at the beginning of each frame. The objective is to analyze the ergodicity of the Markov chain and demonstrate its properties in different regions, particularly the instability region. By employing drift analysis, we obtain the closed-form conditions for the stability of FSA and show that the stability region is maximized when the frame length equals the number of packets to be sent in the single packet reception model and the upper bound of stability region is maximized when the ratio of the number of packets to be sent to frame length equals in an order of magnitude the maximum multipacket reception capacity in the multipacket reception model. Furthermore, to characterize system behavior in the instability region, we mathematically demonstrate the existence of transience of the backlog Markov chain. Finally, the analytical results are validated by the numerical experiments.

We formulate and study a missing tag detection problem arising in multiple-group, multiple-region radio frequency identification (RFID) systems, where a mobile reader needs to detect whether there is any missing event for each group of tags. The problem we tackle is to devise missing tag detection protocols with minimum execution time while guaranteeing the detection reliability requirement for each group. By leveraging the technique of Bloom filter, we develop a suite of three missing tag detection protocols, each decreasing the execution time compared to its predecessor by incorporating an improved version of the Bloom filter design and parameter tuning. By sequentially analyzing the developed protocols, we gradually iron out an optimum detection protocol that works in practice.

Neighbor discovery, one of the most fundamental bootstrapping networking primitives, is particularly challenging in decentralized wireless networks where devices have directional antennas. In this paper, we study the following fundamental problem, which we term oblivious neighbor discovery: How can neighbor nodes with heterogeneous antenna configurations discover each other within a bounded delay in a fully decentralised manner without any prior coordination or synchronisation? We establish a theoretical framework on the oblivious neighbor discovery and the performance bound of any neighbor discovery algorithm achieving oblivious discovery. Guided by the theoretical results, we then devise an oblivious neighbor discovery algorithm, which achieves guaranteed oblivious discovery with order-minimal worst case discovery delay in the asynchronous and heterogeneous environment. We further demonstrate how our algorithm can be configured to achieve a desired tradeoff between average and worst case performance.

In this paper, we construct an analytical design framework for energy efficient scheduling for delay-constrained spectrum aggregation (ESSA), where the practical hardware limitations on SA capability bring various technical challenges. Specifically, the conventional water-filling power control cannot be adopted over all the channels, and the delay-aware scheduling solution should interact with the channel allocation. To overcome these challenges, we design the ESSA scheduling scheme in two steps. First, with given rate vector and channel allocation, we minimize the total power consumption for SA, including both the transmit power as well as the circuit power. Due to the properties of delay-constrained SA, we divide the scheduled users into conforming and nonconforming user sets, and design their water-filling power allocation strategies differentially. Second, based on the differentiated water-filling power control, we optimize the channel allocation and rate control iteratively via Lyapunov optimization to minimize the power consumption with the average delay constraint. The proposed ESSA scheme is finally evaluated by simulation results.

We consider the channel access problem arising in opportunistic scheduling over fading channels, cognitive radio networks, and server scheduling. The multi-channel communication system consists of N channels. Each channel evolves as a time-nonhomogeneous multi-state Markov process. At each time instant, a user chooses M channels to transmit information. Some reward depending on the states of the chosen channels is obtained for each transmission. The objective is to design an access policy that maximizes the expected accumulated discounted reward over a finite or infinite horizon. The considered problem can be cast into a restless multi-armed bandit (RMAB) problem with PSPACE-hardness. A natural alternative is to consider the easily implementable myopic policy. In this paper, we perform an theoretical analysis on the considered RMAB problem, and establish a set of closed-form conditions to guarantee the optimality of the myopic policy.

Neighbor discovery, the process of discovering all neighbors in a device's communication range, is one of the bootstrapping networking primitives of paramount importance and is particularly challenging when devices have directional antennas instead of omni-directional ones. In this paper, we study the following fundamental problem which we term as oblivious neighbor discovery: How can neighbor nodes with heterogeneous antenna configurations and without clock synchronization discover each other within a bounded delay in a fully decentralised manner without any prior coordination? We first establish a theoretical framework on oblivious neighbor discovery and establish the performance bound of any neighbor discovery protocol achieving oblivious discovery. Guided by the theoretical results, we then design an oblivious neighbor discovery protocol and prove that it achieves guaranteed oblivious discovery with order-minimal worst-case discovery delay in the asynchronous and heterogeneous environment. We further demonstrate how our protocol can be configured to achieve a desired trade-off between average and worst-case performance.

We study a class of generic optimization problems on charger scheduling and charging path planing. These problems arise from emerging networking applications where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, and vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We prove that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design a quasi-polynomial time algorithm that achieves poly-logarithmic approximation to the optimum charging path. Our approximation algorithm can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget.

Truthful spectrum auctions make bidders reveal their true valuations for spectrum to maximize their utilities. However, disclosure of one's true value causes numerous security vulnerabilities. Moreover, as a distinguished property of spectrum auction compared to classical auctions, spectrum reutilisation requires that the bidder locations be disclosed to the auctioneer to run the auction. We investigate the impact of disclosing bidder locations and demonstrate that such disclosure can be exploited by a malicious auctioneer to gain extra profit and significantly degrade bidders' utility.

Due to perceived fairness and allocation efficiency, cloud auctions for resource allocation and pricing have recently attracted significant attention. As an important economic property, truthfulness makes bidders reveal their true valuations for cloud resources to maximize their utilities. However, disclosure of one's true value causes numerous security vulnerabilities. Therefore, privacy-preserving cloud auctions are called for to prevent such information leakage. In this paper, we demonstrate how to perform privacy-preserving auctions in clouds that do not leak any information other than the auction results to anyone. Specifically, we design a privacy-preserving cloud auction framework that addresses the challenges posed by the cloud auction context by leveraging the techniques in garbled circuits and homomorphic encryption. As foundations of our privacy preserving cloud auction framework, we develop data-oblivious cloud auction algorithm and basic operations (e.g., comparison, swapping etc.), such that the execution path does not depend on the input. In practical systems with a large number of users and constrained resources, we develop an improved version with a computational complexity of O(n log2 n) in the number of bidders n. We further fully implement our framework and theoretically and experimentally show that it preserves privacy by incurring only limited computation and communication overhead.

Tag population estimation has recently attracted significant research attention due to its paramount importance on a variety of radio-frequency identification (RFID) applications. However, most, if not all, of the existing estimation mechanisms are proposed for the static case where tag population remains constant during the estimation process, thus leaving the more challenging dynamic case unaddressed, despite the fundamental importance of the latter case on both the theoretical analysis and the practical application. In order to bridge this gap, we devote this paper to designing a generic framework of stable and accurate tag population estimation schemes based on the Kalman filter for both the static and dynamic RFID systems. Technically, we first model the dynamics of RFID systems as discrete stochastic processes and leverage the techniques in the extended Kalman filter and cumulative sum control chart to estimate tag population for both the static and dynamic systems. By employing the Lyapunov drift analysis, we mathematically characterize the performance of the proposed framework in terms of estimation accuracy and convergence speed by deriving the closed-form conditions on the design parameters under which our scheme can stabilize around the real population size with bounded relative estimation error that tends to zero with exponential convergence rate.

The new developments in cloud computing have introduced significant security challenges to guarantee the confidentiality, integrity, and availability of outsourced data. A service level agreement (SLA) is usually signed between the cloud provider (CP) and the customer. For redundancy purposes, it is important to verify the CP's compliance with data backup requirements in the SLA. There exist a number of security mechanisms to check the integrity and availability of outsourced data. This task can be performed by the customer or be delegated to an independent entity that we will refer to as the verifier. However, checking the availability of data introduces extra costs, which can discourage the customer of performing data verification too often. The interaction between the verifier and the CP can be captured using game theory in order to find an optimal data verification strategy. In this paper, we formulate this problem as a two player non-cooperative game. We consider the case in which each type of data is replicated a number of times, which can depend on a set of parameters including, among others, its size and sensitivity. We analyze the strategies of the CP and the verifier at the Nash equilibrium and derive the expected behavior of both the players. Finally, we validate our model numerically on a case study and explain how we evaluate the parameters in the model.

In wireless sensor networks, data harvesting using mobile data ferries has recently emerged as a promising alternative to the traditional multi-hop communication paradigm. The use of data ferries can significantly reduce energy consumption at sensor nodes and increase network lifetime. However, it usually incurs long data delivery latency as the data ferry needs to travel through the network to collect data, during which some delay-sensitive data may become obsolete. Therefore, it is important to optimize the trajectory of the data ferry with data delivery latency bound for this approach to be effective in practice. To address this problem, we formally define the time-constrained data harvesting problem, which seeks an optimal data harvesting path in a network to collect as much data as possible within a time duration. We then investigate the formulated data harvesting problem in the generic m-dimensional context, of which the cases of m=1, 2, 3 are particularly pertinent. We first characterize the performance bound given by the optimal data harvesting algorithm and show that the optimal algorithm significantly outperforms the random algorithm, especially when network scales. However, we mathematically prove that finding the optimal data harvesting path is NP-hard. We therefore devise an approximation algorithm and mathematically prove the output being a constant-factor approximation of the optimal solution. Our experimental results also demonstrate that our approximation algorithm significantly outperforms the random algorithm in a wide range of network settings.

Neighbor discovery is of paramount importance in mobile sensing applications and is particularly challenging if the operating frequencies of mobile devices span multiple channels. In this paper, we formulate the multi-channel neighbor discovery problem and establish a theoretical framework of it, under which we derive the performance bound of any neighbor discovery protocol guaranteeing discovery. We then develop a multi-channel discovery protocol that achieves guaranteed discovery with order-minimum worst-case discovery delay and fine-grained control of energy conservation levels.

Mobile data offloading is an emerging technology to avoid congestion in cellular networks and improve the level of user satisfaction. In this paper, we develop a distributed market framework to price the offloading service, and conduct a detailed analysis of the incentives for offloading service providers and conflicts arising from the interactions of different participators. Specifically, we formulate a multileader multifollower Stackelberg game (MLMF-SG) to model the interactions between the offloading service providers and the offloading service consumers in the considered market framework, and investigate the cases where the offloading capacity of APs is unlimited and limited, respectively. For the case without capacity limit, we decompose the followers' game of the MLMF-SG (FG-MLMF-SG) into a number of simple follower games (FGs), and prove the existence and uniqueness of the equilibrium of the FGs from which the existence and uniqueness of the FG-MLMF-SG also follows. For the leaders' game of the MLMF-SG, we also prove the existence and uniqueness of the equilibrium. For the case with capacity limit, by considering a symmetric strategy profile, we establish the existence and uniqueness of the equilibrium of the corresponding MLMF-SG, and present a distributed algorithm that allows the leaders to achieve the equilibrium. Finally, extensive numerical experiments demonstrate that the Stackelberg equilibrium is very close to the corresponding social optimum for both considered cases.

Recently, tremendous utilization of wireless networks has led to sever scarcity of radio spectrum resources. TV White Spaces (TVWSs) as novel bands enabling Cognitive Radio (CR) technology to improve spectrum resources utilization, have attracted significant standardisation efforts such as IEEE 802.11af, IEEE 802.16h and 802.22. As these heterogeneous networks may operate on the same channels of TVWSs, network coexistence problem cannot be avoided and is particularly challenging given the heterogeneous MAC/PHY layer protocols and operation parameters (e.g., tx power) employed in coexisting networks. In this paper, we develop a coexistence mechanism called ecological Species Competition based HEterogeneous networks coexistence MEchanism (SCHEME). Inspired by ecology based species competition model, SCHEME uses an ecological spectrum allocation method to assign available spectrums. Through both theoretical and simulation analysis, we demonstrate that SCHEME can achieve stable and fair spectrum allocation among coexisting networks.

Demand-Side Management (DSM) systems represent an efficient method to improve the performance of Smart Grid infrastructures by controlling users' power loads. In this paper, we focus our analysis on fully distributed DSM systems especially designed to reduce the peak demand of groups of residential users. In our proposed scheme, each appliance decides autonomously its scheduling using only limited information on the energy price fixed by the retailer, thus greatly reducing the system complexity as well as the need of information exchanges. We develop two schedule-selection policies based on the Proportional Imitation Rule, where at each iteration all appliances switch to a new schedule with a probability proportional to the cost difference between the actual and cheapest schedules of the previous iteration. We analyze the proposed learning methods based on realistic instances in several use-case scenarios, and show their effectiveness in terms of cost reductions (both local and system-wide) as well as convergence speed to stable and efficient system equilibria.

We develop a distributed market framework to price the offloading service, and conduct a detailed analysis of the incentives for offloading service providers and conflicts arising from the interactions of different participators. Specifically, we formulate a multi-leader multi-follower Stackelberg game (MLMF-SG) to model the interactions between the offloading service providers and the offloading service consumers in the considered market framework, and investigate the cases where the offloading capacity of APs is unlimited and limited, respectively. For the case without capacity limit, we decompose the followers' game of the MLMF-SG (FG-MLMF-SG) into a number of simple follower games (FGs), and prove the existence and uniqueness of the equilibrium of the FGs from which the existence and uniqueness of the FG-MLMF-SG also follows. For the leaders' game of the MLMF-SG, we also prove the existence and uniqueness of the equilibrium. For the case with capacity limit, by considering a symmetric strategy profile, we establish the existence and uniqueness of the equilibrium of the corresponding MLMF-SG, and present a distributed algorithm that allows the leaders to achieve the equilibrium. Finally, extensive numerical experiments demonstrate that the Stackelberg equilibrium is very close to the corresponding social optimum for both considered cases.

Neighbor discovery plays a crucial role in the formation of wireless sensor networks and mobile networks where the power of sensors (or mobile devices) is constrained. Due to the difficulty of clock synchronization, many asynchronous protocols based on wake-up scheduling have been developed over the years in order to enable timely neighbor discovery between neighboring sensors while saving energy. However, existing protocols are not fine-grained enough to support all heterogeneous battery duty cycles, which can lead to a more rapid deterioration of long-term battery health for those without support. Existing research can be broadly divided into two categories according to their neighbor-discovery techniques — the quorum based protocols and the co-primality based protocols. In this paper, we propose two neighbor discovery protocols, called Hedis and Todis, that optimize the duty cycle granularity of quorum and co-primality based protocols respectively, by enabling the finest-grained control of heterogeneous duty cycles. We compare the two optimal protocols via analytical and simulation results, which show that although the optimal co-primality based protocol (Todis) is simpler in its design, the optimal quorum based protocol (Hedis) has a better performance since it has a lower relative error rate and smaller discovery delay, while still allowing the sensor nodes to wake up at a more infrequent rate.

Truthful auctions make bidders reveal their true valuations for goods to maximize their utilities. Currently, almost all spectrum auction designs are required to be truthful. However, disclosure of one's true value causes numerous security vulnerabilities. Secure spectrum auctions are thus called for to address such information leakage. Previous secure auctions either did not achieve enough security, or were very slow due to heavy computation and communication overhead. In this paper, inspired by the idea of secret sharing, we design an information-theoretically secure framework (ITSEC) for truthful spectrum auctions. As a distinguished feature, ITSEC not only achieves information-theoretic security for spectrum auction protocols in the sense of cryptography, but also greatly reduces both computation and communication overhead by ensuring security without using any encryption/description algorithm. To our knowledge, ITSEC is the first information-theoretically secure framework for truthful spectrum auctions in the presence of semi-honest adversaries. We also design and implement circuits for both single-sided and double spectrum auctions under the ITSEC framework. Extensive experimental results demonstrate that ITSEC achieves comparable performance in terms of computation with respect to spectrum auction mechanisms without any security measure, and incurs only limited communication overhead.

Data harvesting using mobile data ferries has recently emerged as a promising alternative to the traditional multi-hop transmission paradigm. The use of data ferries can significantly reduce energy consumption at sensor nodes and increase network lifetime. However, it usually incurs longer data delivery latency as the data ferry needs to travel through the network to collect data, during which some delay-sensitive data may become obsolete. Therefore, optimizing the trajectory of the data ferry with data delivery latency bound is important for this approach to be effective in practice. To address this problem, we formally define the time-constrained data harvesting problem, which seeks an optimal data harvesting path in a network to collect as much data as possible within a time duration. We first characterise the performance bound given by the optimal data harvesting algorithm and show that the optimal algorithm significantly outperforms the random algorithm, especially when network scales. Motivated by the theoretical analysis and proving the NP-completeness of the time-constrained data harvesting problem, we then devise polynomial-time approximation schemes (PTAS) and mathematically prove the output being a constant-factor approximation of the optimal solution.

Frame Slotted Aloha (FSA) protocol has been widely applied in Radio Frequency Identification (RFID) systems as the defacto standard in tag identification. However, very limited work has been done on the stability of FSA despite its fundamental importance both on the theoretical characterisation of FSA performance and its effective operation in practical systems. In order to bridge this gap, we devote this paper to investigating the stability properties of FSA by focusing on two physical layer models of practical importance, the models with single packet reception and multipacket reception capabilities. Technically, we model the FSA system backlog as a Markov chain with its states being backlog size at the beginning of each frame. The objective is to analyze the ergodicity of the Markov chain and demonstrate its properties in different regions, particularly the instability region. By employing drift analysis, we obtain the closed-form conditions for the stability of FSA and show that the stability region is maximised when the frame length equals the backlog size in the single packet reception model and when the ratio of the backlog size to frame length equals in an order of magnitude the maximum multipacket reception capacity in the multipacket reception model. Furthermore, to characterise system behavior in the instability region, we mathematically demonstrate the existence of transience of the backlog Markov chain.

Recent advances in energy transfer technology is boosting the development of renewable sensor networks. To sustain such a network, a mobile robot travels from node to node to recharge each sensor before its battery runs out. Consider each node's recharge as a real-time task, the robot needs to serve these tasks by their deadlines. This represents a class of challenging mobility scheduling problems, where the nodes' deadlines and spatial distribution are often at odds with each other. In this paper, we focus on the scenario where nodes have heterogeneous energy consumption rates, and our goal is to maximize the percentage of nodes alive. We formulate this scheduling problem and prove its NP-completeness. To solve this problem, we propose a spatial dependent task scheduling algorithm, which quantifies the impact of scheduling proximate tasks on the other tasks. With extensive simulations, we reveal the trade-offs of existing solutions under a wide range of network scenarios. Our evaluation results show that our algorithms out-perform classical TSP scheduler by up to 10% and 85% in terms of coverage ratio and average tardiness, respectively.

Recent advances in energy transfer technology is boosting the development of renewable sensor networks. To sustain such a network, a mobile robot travels from node to node to recharge each sensor before its battery runs out. To solve this problem, we propose a spatial dependent task scheduling algorithm, which quantifies the impact of scheduling proximate tasks on the other tasks. Our evaluation results show that our algorithms out-perform classical TSP scheduler by up to10% and 85% in terms of coverage ratio and average tardiness, respectively.

The authors consider a cognitive radio network overlaying on top of a legacy primary network in which a secondary user is allowed to access primary channel by overhearing feedback signals over the primary channels. Each channel is assumed to be a two state Makovian process. Aiming at maximising the expected accumulated discounted network throughput, the considered sequential decision‐making problem can be cast into a restless multi‐armed bandit (RMAB) problem which is well‐known to be PSPACE‐hard, and thus a natural alternative approach is to seek a simple myopic policy. This study presents a theoretical study on the optimality of the proposed myopic policy for the special RMAB problem by considering four different cases: negatively correlated homogeneous channels, heterogeneous channels, positively correlated heterogeneous channels and negatively correlated heterogeneous channels. More specifically, the authors establish the closed‐form conditions to guarantee the optimality of the myopic policy for the four cases, respectively, which, combined with the case of positively correlated homogeneous channels, constitute a complete paradigm for the optimality of the myopic policy.

Two players wishing to communicate are placed each in a room with N telephones connecting the two rooms. The players do not know how the telephones are interconnected. In each round, each player picks up a phone and says “hello” until when they hear each other. The problem is to devise an algorithm minimising the delay to establish communication. The above problem, called the Telephone Coordination Game, also termed as the Telephone Problem, is of fundamental importance in distributed algorithm design. In this paper, we investigate a generalised version where among N telephones, only a subset can establish communication between the two players. We are interested in devising the deterministic strategy achieving bounded rendezvous delay and minimising the worst-case rendezvous delay. Specifically, we first establish the lower-bound of worst-case rendezvous delay. We then characterise the structure of the phone pick sequences that can guarantee rendezvous without any prior coordination. Assuming each player has a globally unique ID, we further devise a deterministic strategy that (1) guarantees rendezvous between the players regardless of their telephone labeling functions and their relative time difference and (2) approaches the performance bound within a constant factor proportional to the ID length.

The opportunistic utilization of third party WiFi access devices to offload customer traffic from the mobile network has recently gained momentum as a promising approach to increase the network capacity and simultaneously reduce the energy consumption of the radio access network (RAN) infrastructure. To foster the opportunistic utilization of unexploited Internet connections, we propose a new and open market where a mobile operator can lease the bandwidth made available by third parties (residential users or private companies) through their access points to increase dynamically (and adaptively) the network capacity. We formulate the offloading problem as a reverse auction considering the most general case of partial covering of the traffic to be offloaded. We discuss the conditions (i) to offload the maximum amount of data traffic according to the capacity made available by third party access devices, (ii) to foster the participation of access point owners (individual rationality), and (iii) to prevent market manipulation (incentive compatibility). Finally, we propose three alternative greedy algorithms that efficiently solve the offloading problem, even for large-size network scenarios.

Sensing falsification is a key security threat in cooperative spectrum sensing in cognitive radio networks. Intelligent malicious users (IMUs) adjust their malicious behaviors according to their objectives and the network's defense schemes. Without long-term collection of information on users' reputation, the existing schemes fail to thwart such malicious behaviors. In this paper, we construct a joint spectrum sensing and access framework to thwart the malicious behaviors of both rational and irrational IMUs. Lack of reputation information makes the malicious behavior resistance degrade performance since the honest users may be misjudged as IMUs. Based on the moral hazard principal-agent model, we design an incentive compatible mechanism to provide a moderate punishment to IMUs. Our findings show that neither spectrum sensing nor spectrum access alone can prevent malicious behaviors without any information on users' reputation. According to the different properties of malicious behavior resistance by spectrum sensing and spectrum access, we employ joint spectrum sensing and access to optimally prevent the IMUs sensing falsification. The proposed malicious behavior resistance mechanism is shown to achieve almost the same performance as the ideal case with truthful sensing.

Nowadays, the maintenance costs of wireless devices represent one of the main limitations to the deployment of wireless mesh networks (WMNs) as a means to provide Internet access in urban and rural areas. A promising solution to this issue is to let the WMN operator lease its available bandwidth to a subset of customers, forming a wireless mesh community network, in order to increase network coverage and the number of residential users it can serve. In this paper, we propose and analyze an innovative marketplace to allocate the available bandwidth of a WMN operator to those customers who are willing to pay the higher price for the requested bandwidth, which in turn can be subleased to other residential users. We formulate the allocation mechanism as a combinatorial truthful auction considering the key features of wireless multihop networks and further present a greedy algorithm that finds efficient and fair allocations even for large-scale, real scenarios while maintaining the truthfulness property. Numerical results show that the greedy algorithm represents an efficient, fair, and practical alternative to the combinatorial auction mechanism.

The timing channel is a logical communication channel in which information is encoded in the timing between events. Recently, the use of the timing channel has been proposed as a countermeasure to reactive jamming attacks performed by an energy-constrained malicious node. In fact, while a jammer is able to disrupt the information contained in the attacked packets, timing information cannot be jammed, and therefore, timing channels can be exploited to deliver information to the receiver even on a jammed channel. Since the nodes under attack and the jammer have conflicting interests, their interactions can be modeled by means of game theory. Accordingly, in this paper, a game-theoretic model of the interactions between nodes exploiting the timing channel to achieve resilience to jamming attacks and a jammer is derived and analyzed. More specifically, the Nash equilibrium is studied in terms of existence, uniqueness, and convergence under best response dynamics. Furthermore, the case in which the communication nodes set their strategy and the jammer reacts accordingly is modeled and analyzed as a Stackelberg game, by considering both perfect and imperfect knowledge of the jammer's utility function. Extensive numerical results are presented, showing the impact of network parameters on the system performance.

In this paper, we consider the probing order and stopping problem arising from the identification of spectrum holes in multi-channel cognitive radio networks, in which a secondary user (SU) seeks to maximize the probability of finding an available channel while minimizing the related probing cost within a long time horizon. This problem can be casted into a restless multi-armed bandit problem, which is proved to be PSPACE-hard. The key point of this problem is the trade-off between exploitation, in which the SU stops probing once an available channel is identified, and exploration, in which the SU continues to probe new channels even after identifying an available channel in order to learn the system state to reduce probing cost in the future. To strike a desirable balance between the two conflicting objectives, we develop a heuristic channel probing policy, termed the v-step lookahead policy, in which the SU makes its decision based on the prediction of system state within the future v steps, with v being a tunable parameter. We conduct an analytical study on the structure of the proposed v-step lookahead policy and demonstrate how the policy can be implemented with linear complexity with respect to the number of channels in the system via a detailed analysis on the 1-step lookahead policy. Numerical experiments between the v-step lookahead policy and myopic probing policy on two representative network scenarios demonstrate the effectiveness of the proposed v-step lookahead policy.

Decentralized cognitive radio networks (CRN) require efficient channel access protocols to enable cognitive secondary users (SUs) to access the primary channels in an opportunistic way without any coordination. In this paper, we develop a distributed retrospective spectrum access protocol that can orient the network towards a socially efficient and fair equilibrium state. With the developed protocol, each SU j chooses a channel to select based on the experienced payoff in past Hj periods. Each SU is thus supposed to be equipped with bounded memory and should make its decision based on only local observations. In that sense, the SUs behavioral rules are said to be payoff-based. The protocol also models a natural human decision making behavior of striking a balance between exploring a new choice and retrospectively exploiting past successful choices. With both analytical demonstration and numerical evaluation, we illustrate the two noteworthy features of our solution: (1) the entirely distributed implementation requiring only local observations and (2) the guaranteed statistical convergence to the equilibrium state within a bounded delay.

Opportunistic forwarding assisted by mobile relays is an effective way of improving network capacity and packet delivery ratio in delay tolerant networks (DTNs). However, such performance gain comes at the price of increased energy consumption due to the duplicated transmissions at relays. In this paper, we investigate how energy harvesting, a promising technique of enabling sustainable communications, can be exploited to improve the performance of opportunistic forwarding in mobile DTNs. Specifically, we formulate the problem using a Markov Decision Process (MDP) framework in which each source should strike a balance between exploitation, by forwarding the packet to the relay currently in contact, and exploration, by waiting for possible better relays in the future, given the harvested energy constraint. The formulated MDP having exponential complexity, we devise a heuristic relay-assisted opportunistic forwarding scheme, termed as adaptive M-step lookahead scheme, to alleviate the computation complexity, where M can be adjusted adaptively according to both the current energy and the energy that might be harvested in the future. Simulation results show that our proposed algorithm can use the harvested energy more efficiently, especially for the circumstance where the energy harvesting rate is low.

Mobile relay-assisted forwarding can improve the network capacity, but meanwhile increase the energy consumption. In this paper, we propose two distance-based energy-efficient opportunistic forwarding (DEEOF) schemes in mobile delay tolerant networks (DTNs). The proposed schemes strike a balance between energy consumption and network performance by maximizing the energy efficiency while maintaining a high packet delivery ratio from two different angles. Specifically, in the developed algorithms, we introduce the forwarding equivalent energy-efficiency distance (FEED) to quantify the transmission distances achieving the same energy efficiency at different time instances. The expected energy efficiency can thus be estimated based on the FEED. Furthermore, the distribution of the greatest forwarding energy efficiency in the predicted period is investigated to provide more accurate prediction for the energy efficiency. The forwarding decision in the algorithms is made by comparing the current energy efficiency and the estimated future expectation. The performance improvement of the proposed algorithms is also demonstrated by simulation, especially for systems where the source has very limited battery reserves.

Sensing falsification is a key security problem in cooperative spectrum sensing for cognitive radio networks. Most previous approaches assume that malicious users only cheat in their sensing reports following a predefined rule. However, some malicious users usually act intelligently to strategically adjust their malicious behavior according to their objectives and the network's defense schemes. The existing schemes cannot resist the malicious behaviors of intelligent malicious users (IMUs) without long-term collection of information on their reputation. In this paper, we construct a moral hazard principal-agent framework and design an incentive compatible mechanism to thwart the malicious behaviors of rational and irrational IMUs. We find that neither spectrum sensing nor spectrum access alone can prevent the malicious behavior without any information on users' reputation. According to the analysis of malicious behavior resistance methods, we propose a joint spectrum sensing and access mechanism to optimally prevent the IMUs from sensing falsification. Our evaluation results show that the proposed mechanism achieves almost the same performance as the ideal case with perfect sensing.

In cognitive radio (CR) networks, a pair of CR nodes have to ``rendezvous'' on a common channel for link establishment. Channel hopping (CH) protocols have been proposed for creating rendezvous over multiple channels to reduce the possibility of rendezvous failures caused by the detection of primary user signals. Rendezvous within a minimal bounded time over multiple channels is a challenging problem in heterogeneous CR networks where two CR nodes may have asynchronous clocks, different sensing capabilities, no common universal channel set, and heterogeneous channel index systems. In this paper, we present a systematic approach using group theory for designing CH protocols that guarantee the maximum number of rendezvous channels and the minimal time-to-rendezvous (TTR) in heterogeneous environments. We derive the minimum upper bound of TTR, and propose two types of rendezvous protocols that are independent of environmental heterogeneity. Analytical and simulation results show that these protocols are resistant to rendezvous failures under various network conditions.

Neighbor discovery is of paramount importance in mobile sensing applications that rely heavily on data timely collected and shared among nearby users. Guaranteed discovery with bounded latency and supporting heterogenous duty cycles to provide fine-grained control of energy conservation levels are among the most crucial requirements in the design of efficient neighbor discovery protocols. While simultaneously satisfying these two requirements is non-trivial, the situation is exacerbated if the operating frequencies of mobile devices span multiple channels and discovery occurs only if nodes switch to the same channel. In this paper, we formulate this problem as heterogeneous multi-channel neighbor discovery problem and establish a theoretical framework of the problem, under which we derive the performance bound of any neighbor discovery protocol. Based on the theoretical results, we then develop Mc-Dis (Multi-channel Discovery), a novel multi-channel discovery protocol that (1) achieves guaranteed discovery with order-minimal worst-case discovery delay and (2) supports almost all duty cycles to provide fine-grained control of energy conservation levels.

The widespread deployment of smart meters in the advanced metering infrastructure (AMI) raises privacy concerns. Analyzing the data collected from smart meters can expose habits and can be potentially used to predict consumers' behaviors. In this paper, we analyze the confidentiality of information in the AMI consisting of nodes with interdependent correlated security assets. On each node, the defender can choose one of several security modes available. We try to answer the following questions: 1) What is the expected behavior of a rational attacker?; 2) What is the optimal strategy of the defender?; and 3) Can we configure the security modes on each node to discourage the attacker from launching any attacks? In this paper, we formulate the problem as a noncooperative game and analyze the behavior of the attacker and the defender at the Nash equilibrium. The attacker chooses his targets in order to collect the maximum amount of data on consumers, and the defender chooses the encryption level of outbound data on each device in the AMI. Using our model, we derive the minimum defense resources required and the optimal strategy of the defender. Finally, we show how our framework can be applied in a real-world scenario via a case study.

The Radio Access Network (RAN) infrastructure represents the most critical part for capacity planning, which usually accounts for peak traffic conditions. A promising approach to increase the RAN capacity and simultaneously reduce its energy consumption is represented by the opportunistic utilization of third party Wi-Fi access devices. In order to foster the utilization of unexploited Internet connections, we propose a new and open market, where a mobile operator can lease the bandwidth made available by third parties (residential users or private companies) through their access points to increase the network capacity and save large amounts of energy. We formulate the offloading problem as a reverse auction considering the most general case of partial covering of the traffic to be offloaded. We discuss the conditions (i) to offload the maximum amount of data traffic according to the capacity of third party access devices, (ii) to foster the participation of access point owners (individual rationality), and (iii) to prevent market manipulation (incentive compatibility). Finally, we propose a greedy algorithm that solves the offloading problem in polynomial time, even for large-size network scenarios.

We consider the channel access problem in a multi-channel opportunistic communication system with imperfect channel sensing, where the state of each channel evolves as an independent and identically distributed Markov process. The considered problem can be cast into a restless multi-armed bandit (RMAB) problem that is of fundamental importance in decision theory. It is well-known that the optimal policy of RMAB problem is intractable for its exponential computation complexity. A natural alternative is to consider the easily implementable myopic policy that maximizes the immediate reward but ignores the impact of the current strategy on the future reward. In this paper, we perform an analytical study on the optimality of the myopic policy under imperfect sensing for the considered RMAB problem. Specifically, for a family of generic and practically important utility functions, we establish the closed-form conditions to guarantee the optimality of the myopic policy even under imperfect sensing. Despite our focus on the opportunistic channel access, the obtained results are generic in nature and are widely applicable in a wide range of engineering domains.

The practical hardware limitations bring technical challenges to cognitive radio, e.g. limited capability of spectrum sensing and certain frequency range of spectrum access. In this paper, we propose a rollout-based joint spectrum sensing and access policy incorporating the hardware limitations of both sensing capability and spectrum aggregation, in which the optimal policy is shown to be PSPACE-hard. Two heuristic policies are proposed to serve as base policies, based on which the developed rollout-based policy approximates the value function and determines the appropriate spectrum sensing and access actions. We establish mathematically that the rollout-based policy achieves better performance than the base policy. We also demonstrate that the low-complexity rollout-based policy leads to only slight performance loss compared with the optimal policy.

In this paper, we tackle the problem of opportunistic spectrum access in cognitive radio networks where a number of unlicensed Secondary Users (SU) operating on the standard CSMA/CA protocol access a number of frequency channels partially occupied by licensed Primary Users (PU). We apply evolutionary game theory to model the spectrum access problem and derive distributed mechanisms to converge to the Nash equilibrium. To this end, we combine a payoff computation methodology, relying on the estimation on the number of SUs on the same channel, with the channel access policy derived by the evolutionary game model. The conducted numerical analysis shows that a fast convergence is achieved and the proposed mechanisms are robust against errors in payoff computation.

In this study, the authors consider the restless multi-armed bandit problem, which is one of the most well-studied generalisations of the celebrated stochastic multi-armed bandit problem in decision theory. However, it is known to be PSPACE-Hard to approximate to any non-trivial factor. Thus, the optimality is very difficult to obtain because of its high complexity. A natural method is to obtain the greedy policy considering its stability and simplicity. However, the greedy policy will result in the optimality loss for its intrinsic myopic behaviour generally. In this study, by analysing one class of so-called standard reward function, the authors establish the closed-form condition about the discounted factor β such that the optimality of the greedy policy is guaranteed under the discounted expected reward criterion, especially, the condition β=1 indicating the optimality of the greedy policy under the average accumulative reward criterion. Thus, this kind of standard reward function can easily be used to judge the optimality of the greedy policy without any complicated calculation. Some examples in cognitive radio networks are presented to verify the effectiveness of the mathematical result in judging the optimality of the greedy policy.

We study the spectrum access problem in cognitive networks consisting of several frequency channels, each characterized by a channel availability probability due to the activity of the licensed primary users. The key challenge for the unlicensed secondary users to opportunistically access the unused spectrum of the primary users is to learn the channel availabilities and coordinate with others in order to choose the best channels for transmissions without collision in a distributed way. Moreover, due to the drastic cost of changing frequencies in current wireless devices (in terms of delay, packet loss and protocol overhead), an efficient channel access policy should avoid frequently channel switching, unless necessary. We address the spectrum access problem with channel switching cost by developing a block-based distributed channel access policy. Through mathematical analysis, we show that the proposed policy achieves logarithmic regret in spite of the channel switching cost. Extensive simulation studies show that the proposed policy outperforms the solutions in the literature.

Extensive research in recent years has shown the benefits of cooperative relaying in wireless networks, where nodes overhear and cooperatively forward packets transmitted between their neighbors. Most existing studies focus on physical-layer optimization of the effective channel capacity for a given transmitter-receiver link; however, the interaction among simultaneous flows between different endpoint pairs, and the conflicts arising from their competition for a shared pool of relay nodes, are not yet well understood. In this paper, we study a distributed pricing framework, where sources pay relay nodes to forward their packets, and the payment is shared equally whenever a packet is successfully relayed by several nodes at once. We formulate this scenario as a Stackelberg (leader-follower) game, in which sources set the payment rates they offer, and relay nodes respond by choosing the flows to cooperate with. We provide a systematic analysis of the fundamental structural properties of this generic model. We show that multiple follower equilibria exist in general due to the nonconcave nature of their game, yet only one equilibrium possesses certain continuity properties that further lead to a unique system equilibrium among the leaders. We further demonstrate that the resulting equilibria are reasonably efficient in several typical scenarios.

Extensive research in recent years has shown the benefits of cognitive radio technologies to improve the flexibility and efficiency of spectrum utilization. This new communication paradigm, however, requires a well-designed spectrum allocation mechanism. In this paper, we propose an auction framework for cognitive radio networks to allow unlicensed secondary users (SUs) to share the available spectrum of licensed primary users (PUs) fairly and efficiently, subject to the interference temperature constraint at each PU. To study the competition among SUs, we formulate a non-cooperative multiple-PU multiple-SU auction game and study the structure of the resulting equilibrium by solving a non-continuous two-dimensional optimization problem. A distributed algorithm is developed in which each SU updates its strategy based on local information to converge to the equilibrium. We then extend the proposed auction framework to the more challenging scenario with free spectrum bands. We develop an algorithm based on the no-regret learning to reach a correlated equilibrium of the auction game. The proposed algorithm, which can be implemented distributedly based on local observation, is especially suited in decentralized adaptive learning environments as cognitive radio networks. Finally, through numerical experiments, we demonstrate the effectiveness of the proposed auction framework in achieving high efficiency and fairness in spectrum allocation.

The proliferation of wireless access technologies offers users the possibility of choosing among multiple available wireless access networks to connect to. This paper focuses on such network selection problem in the context of IEEE 802.11 WLANs where several access points provide connection service to users. We formulate this problem as a non-cooperative game where each user tries to maximize its utility function, defined as the throughput reward minus the fee charged by the access point. We then conduct a systematic analysis on the formulated game and develop an access point selection algorithm based on no-regret learning to orient the system converges to an equilibrium state (correlated equilibrium). The proposed algorithm, which can be implemented distributedly based on local observation, is especially suited in decentralized adaptive learning environments as wireless access networks. Finally, the simulation results demonstrate the effectiveness of the proposed algorithm in achieving high system efficiency.

In this paper, we address the crucial issue of how to design efficient MAC protocols in autonomous wireless networks with selfish users. We model the wireless medium access control problem as a non-cooperative game in which the MAC protocol can be regarded as distributed strategy update scheme approaching the equilibrium point. Under such game theoretic framework, three MAC protocols, the aggressive, conservative and cheat-proof MAC protocol, are then proposed with tunable parameters allowing them to converge to the desired social optimal point. The first two MAC protocols require network participants to follow the rules, while the cheat-proof MAC protocol can survive the selfish environments where nodes are purely self-interested. Based on our game theoretic analysis, we provide a general methodology for designing efficient MAC protocols for autonomous wireless networks. We believe that the proposed methodology not only provides a general way of designing stable and controllable MAC protocols achieving high performance even in selfish environments, but also provides a general framework that can be extended to design efficient protocols in other non-cooperative environments.

Due to the dynamic, distributed, and heterogeneous nature of today's networks, intrusion detection systems (IDSs) have become a necessary addition to the security infrastructure and are widely deployed as a complementary line of defense to classical security approaches. In this paper, we address the intrusion detection problem in heterogeneous networks consisting of nodes with different noncorrelated security assets. In our study, two crucial questions are: What are the expected behaviors of rational attackers? What is the optimal strategy of the defenders (IDSs)? We answer the questions by formulating the network intrusion detection as a noncooperative game and performing an in-depth analysis on the Nash equilibrium and the engineering implications behind. Based on our game theoretical analysis, we derive the expected behaviors of rational attackers, the minimum monitor resource requirement, and the optimal strategy of the defenders. We then provide guidelines for IDS design and deployment. We also show how our game theoretical framework can be applied to configure the intrusion detection strategies in realistic scenarios via a case study. Finally, we evaluate the proposed game theoretical framework via simulations. The simulation results show both the correctness of the analytical results and the effectiveness of the proposed guidelines.

We present a game-theoretic study on the power and rate control problem in IEEE 802.11 WLANs where network participants choose appropriate transmission power and data rate to achieve maximum throughput with minimum energy consumption. In such game-theoretic study, the central issues are the existence, uniqueness of the Nash equilibrium (NE), the convergence to the NE and the system performance at the NE. We conduct our study for three specific games: the fixed-rate power control game GNPC, the fixed-power rate control game GNRCand the joint power rate control game GNJPRC. As main contributions, we establish the existence, uniqueness and convergence of the NE for the three games. In GNRCwhere the NE is inefficient, we provide pricing scheme to improve the efficiency. Based on our analysis on GNJPRC, we propose the joint power and rate control procedure to approach the NE which is proven to be social optimal. The procedure is distributed and simple to incorporate into the existing IEEE 802.11 MAC protocol.

We present a non-cooperative game-theoretical study of the power and rate control problem in IEEE 802.11 WLANs where network participants choose appropriate transmission power and data rate to achieve maximum throughput with minimum energy consumption. In such game-theoretical study, the central question is whether a Nash equilibrium (NE) exists, if so, whether the network operates efficiently at the NE. In this paper, we show the existence and uniqueness of the NE and the convergence to the NE under best response strategy. However, the unique NE is inefficient, i.e., neither social optimal nor Pareto optimal. Motivated by this fact, we propose both linear and non-linear pricing scheme to improve efficiency. We demonstrate that by wisely choosing the parameters, the game converges to an efficient NE. Finally, we examine the convergence to the NE under a practical rate update scheme: the subgradient rate update. Both analytical and numerical results show that the proposed rate control scheme can lead the network to the social optimal equilibrium.

In wireless mobile ad hoc networks where nodes are selfish and non-cooperative, a natural and crucial question is how well or how bad the MAC layer protocol IEEE 802.11 DCF performs. In this paper, we study this question by modeling the selfish MAC protocol as a non- cooperative repeated game where players follow the TIT- FOR-TAT (TFT) strategy which is regarded as the best strategy in such environments. We show for single-hop ad hoc networks the game admits a number of Nash Equilibria (NE). We then perform NE refinement to eliminate the inefficient NE and show that there exists one efficient NE maximizing both local and global payoff. We also propose an algorithm to approach the efficient NE. We then extend our efforts to multi-hop case by showing that the game converges to a NE which may not be globally optimal but quasi- optimal in the sense that the global payoff is only slightly less than the optimal case. As conclusion, we answer the posed question by showing that selfishness does not always lead to network collapse. On the contrary, it can help the network operate at a NE globally which is optimal or quasi-optimal under the condition that players are long-sighted and follow the TFT strategy.

In this paper, motivated by the need of a quantitative model for the power and rate control in IEEE 802.11 WLANs and the lack of related work in the literature, we address the problem by establishing a quantitative game theoretic framework. Our motivation of using game theoretic approach rather than global optimization approach is two-fold: 1) game theory is a powerful tool to model selfish behaviors and their impact on the system performance in distributed environments with self-interested players; 2) game theory can model the features or constraints of IEEE 802.11 WLANs such as lack of coordination and network feedback.