Operating a quantum network incurs high capital and operational expenditures, which are expected to be compensated by the high value of enabled quantum applications. However, existing mechanisms mainly focus on maximizing the entanglement distribution rate and neglect the cost incurred on users. This paper aims to address how to utilize quantum network resources in a cost-efficient manner while sustaining high-quantity and high-quality entanglement distribution. We first consider how to establish a steady stream of entanglements between remote nodes with the minimum cost. Utilizing a recent flow-based abstraction and a novel graph representation, we design an optimal algorithm for min-cost remote entanglement distribution. Next, we consider distributing entanglements with the highest fidelity subject to a cost bound and prove its NP-hardness. To explore the cost-fidelity trade-off due to swapping and purification, we propose an approximation scheme for maximizing fidelity while satisfying an arbitrary cost bound. Our algorithms provide rigorous tools for supporting high-performance quantum network applications with financial consideration and offer strong theoretical guarantees. Extensive simulation results validate the advantageous performance in cost efficiency and/or fidelity compared to existing solutions and heuristics.

Payment channel networks (PCNs) have been proposed to tackle the scalability issues in blockchains by enabling off-chain transaction settlement. However, the balance depletion problem caused by unidirectional transactions may jeopardize the payments in PCNs. Existing works address this problem by sending artificial payments to rebalance the payment channels. In this paper, we take advantage of a unique property in PCNs, where the payments of opposite directions between two users can cancel each other out, to mitigate this channel depletion problem. Specifically, we design BAR, a distributed balance-aware payment routing protocol, subject to fee-based conservation, timeliness, and feasibility constraints. Moreover, to ensure payment security, we modify the original Hashed Time-Lock Contract (HTLC) protocol to adapt it to BAR, such that BAR achieves efficiency and atomicity. Extensive simulations demonstrate that BAR outperforms the state-of-the-art algorithms Spider [1] and LND [2] in terms of success ratio and success volume.

Low Earth Orbit Satellite Networks (LSNs), as the new generation of backbone networks, can provide low-latency network connectivity anywhere on Earth. However, their dynamic topology and unpredictable global usage patterns hinder reliable communication, limiting their application in supporting real-time applications that require predictable performance. Specifically, the highly dynamic LSN may experience congestion and energy depletion due to uneven user demands and the periodic movement of satellites. In this paper, we design a Congestion and Energy-Aware pricing and resource Reservation algorithm, CEAR, which enables a LSN to reserve network resources for online arriving real-time communication requests, ensuring reliable communication to support performance-critical applications such as disaster monitoring and remote teleconferencing. To maintain the long-term performance of the network, the LSN operator sets resource prices for link bandwidth and satellite energy consumption across the network. The resource prices act as a proxy between the resource reservation decisions for each communication request and the operator’s objective to maximize throughput and network utility and/or to balance network-wide resource depletion. CEAR is guided by online competitive algorithm design and achieves a competitive social welfare. Extensive simulations using real-world LSN topology show that CEAR achieves high social welfare while maintaining low network-wide congestion and energy deficit.

Personalized federated learning (PFL) addresses the limitations of traditional federated learning (FL) in statistically heterogeneous scenarios, where diverse client data distributions reduce model applicability. However, many PFL methods compromise client privacy or depend on external client information. This paper proposes a novel PFL method that enhances privacy and autonomy by enabling each client to share only partial model components and adaptively optimize local aggregation weights to align with its local objective. This approach minimizes reliance on other clients' information while ensuring robust personalization. Comparative experiments on three real-world datasets against seven baseline methods demonstrate that our method achieves higher or comparable accuracies, validating its effectiveness in non-IID settings.

In the Internet of Things (IoT) field, where interconnected devices generate sensitive data, ensuring privacy is a major challenge. Federated Learning (FL) addresses this by allowing devices to collaboratively train a model without sharing their local data, improving privacy in IoT systems. While the traditional two-layer FL framework is commonly used, adopting a hierarchical client-edge-cloud architecture can significantly accelerate model training, especially in resource-constrained IoT networks. Hierarchical Federated Learning (HFL) offers significant advantages, yet concerns persist regarding potential privacy breaches from analyzing client or edge server data. To address these concerns, we propose PrivHFL, a privacy-preserving solution for HFL that leverages threshold homomorphic encryption. Security and performance analyses demonstrate that the proposed scheme is scalable, supporting larger FL scenarios, including diverse IoT environments, while ensuring data privacy. PrivHFL is resilient to collusion among nearly half of the clients and effectively handles client dropouts. Our approach achieves high accuracy in IID and non-IID scenarios, as demonstrated using the MNIST, CIFAR-10, and CIFAR-100 datasets. Additionally, we show that the added encryption overhead is reasonable, making our solution feasible for real-world IoT applications.

Payment Channel Networks (PCNs) offer an efficient off-chain alternative to the blockchain for transactions. Router nodes in PCNs facilitate transactions between non-adjacent nodes in exchange for a fee. PCN topology tends to be centralized, with a select number of routers known as hubs dominating all payment services. The fee-setting choices of hubs in order to maximize their revenue present fertile grounds for the study of PCN communications and economics. In this paper, we conduct a comprehensive analysis of the Hub Price-Setting (HPS) game. In particular, we define approximate Best Response strategies (ϵ-BR) as well as approximate Nash equilibria (ϵ-NE). We prove that for any ϵ > 0, an ϵ-BR always exists, and can be computed in polynomial time. We also prove that for some ϵ > 0, an ϵ-NE may not exist. We furthermore introduce the notion of conservative estimate and present a max-min approach to the HPS game. Extensive evaluation results demonstrate the power of our proposed approach.

Low Earth Orbit (LEO) Earth Observation (EO) satellites have changed the way we monitor Earth. Acting like moving cameras, EO satellites are formed in constellations with different missions and priorities, and capture vast data that needs to be transmitted to the ground for processing. However, EO satellites have very limited downlink communication capability, limited by transmission bandwidth, number and location of ground stations, and small transmission windows due to highvelocity satellite movement. To optimize resource utilization, EO constellations are expected to share communication spectrum and ground stations for maximum communication efficiency. In this paper, we investigate a new attack surface exposed by resource competition in$\mathbf{E O}$constellations, targeting the delay or drop of Earth monitoring data using legitimate EO services. Specifically, an attacker can inject high-priority requests to temporarily preempt low-priority data transmission windows. Furthermore, we show that by utilizing predictable satellite dynamics, an attacker can intelligently target critical data from low-priority satellites, either delaying its delivery or irreversibly dropping the data. We formulate two attacks, the data delay attack and the data overflow attack, design algorithms to assist attackers in devising attack strategies, and analyze their feasibility or optimality in typical scenarios. We then conduct trace-driven simulations using real-world satellite images and orbit data to evaluate the success probability of launching these attacks under realistic satellite communication settings. We also discuss possible defenses against these attacks.

Edge computing gained popularity for its promises of low latency and high-quality computing services to users. However, it has also introduced the challenge of mutual untrust between user and edge devices for service level agreement (SLA) compliance. This obstacle hampers wide adoption of edge computing, especially in pervasive edge computing (PEC) where edge devices can freely enter or exit the market, which makes verifying and enforcing SLAs significantly more challenging. In this paper, we propose a framework for verifying and enforcing SLAs in PEC, allowing a user to assess SLA compliance of an edge service and ensure correctness of the service results. Our solution, called VeriEdge, employs a verifiable delayed sampling approach to sample a small number of computation steps, and relies on randomly selected verifiers to verify correctness of the computation results. To make sure the verification process is non-manipulable, we employ verifiable random functions to post-select the verifier(s). A dispute protocol is designed to resolve disputes for potential misbehavior. Rigorous security analysis demonstrates that VeriEdge achieves a high probability of detecting SLA violation with a minimal overhead. Experimental results indicate that VeriEdge is lightweight, practical, and efficient.

Payment Channel Networks (PCNs) have been proposed as a second-layer solution to the scalability issue of blockchain-based cryptocurrencies, most developed systems still lack effective strategies for further scalability solutions. Virtual payment channel (VPC) has been proposed as an off-chain technique that avoids the involvement of intermediaries for payments in a PCN. However, there is no research on how to efficiently construct VPCs while considering the characteristics of the underlying PCN. To fill this void, this paper focuses on the VPC construction in a PCN. More specifically, we propose a metric, Capacity to the Number of Intermediaries Ratio (CNIR), to consider both the capacity of the constructed VPC and the collateral locked by the involved users. We first study the VPC construction problem for a single pair of users and design an efficient algorithm that achieves the optimal CNIR. Based on this, we propose Thor, a protocol that constructs a virtual payment channel network (VPCN) for multiple pairs. Evaluation results show that Thor can efficiently construct a VPCN and outperform baseline algorithms in terms of the CNIR.

Scalability is a critical challenge for blockchain-based cryptocurrencies. Payment channel networks (PCNs) have emerged as a promising solution for this challenge. However, channel balance depletion can significantly limit the capacity and usability of a PCN. Specifically, frequent transactions that result in unbalanced payment flows from two ends of a channel can quickly deplete the balance on one end, thus blocking future payments from that direction. In this paper, we propose Fence, an online balance-aware fee setting algorithm to prevent channel depletion and improve PCN sustainability and long-term throughput. In our algorithm, PCN routers set transaction fees based on the current balance and level of congestion on each channel, in order to incentivize payment senders to utilize paths with more balance and less congestion. Our algorithm is guided by online competitive algorithm design, and achieves an asymptotically tight competitive ratio with constant violation in a unidirectional PCN. We further prove that no online algorithm can achieve a finite competitive ratio in a general PCN. Extensive simulations under a real-world PCN topology show that Fence achieves high throughput and keeps network channels balanced, compared to state-of-the-art PCN routing algorithms.

Edge computing promises to bring low-latency and high-throughput computing, but the limited edge resources may cause frequent congestion and lead to unstable and unpredictable performance. To ensure performance guarantee, application owners can establish Service-Level Agreements (SLAs) with the edge provider for resource reservation or priority usage. But it is cost-inefficient for application owners to lease long-term SLAs based on peak demands, as demands can fluctuate, and the leased resources may be idle or underutilized at most times. This paper studies market mechanism design for short-term edge SLA leases, focusing on real-time big data applications with throughput and latency goals. Applications submit short-term SLA requests to serve users with guaranteed performance during peak hours. As SLA requests arrive over time, the edge provider dynamically provisions edge resources to fulfill the requests, while charging application owners based on the current demands. We design EA-Market, an online combinatorial auction mechanism that achieves a competitive social welfare, while guaranteeing truthfulness, budget balance, individual rationality, and computational efficiency. Notably, our mechanism enables each application owner to bid without knowledge of the edge infrastructure, and gives edge provider full control over resource provisioning to fulfill the requests. We perform theoretical analysis and simulations to evaluate the efficacy of our mechanism.

Edge computing enables great computation ability in close proximity to the mobile devices (MDs). The task execution delay and energy consumption of the MDs will be greatly reduced by designing efficient task offloading policies. However, designing efficient task offloading policies is hard due to stochastic task arrivals. We formulate the task offloading problem as a Constrained Markov Decision Process (CMDP). We first propose a deterministic task offloading policy combining the value iteration algorithm and the sub-gradient algorithm. We then prove the existence of optimal randomized task offloading policies. Based on this, we further propose an optimal randomized task offloading policy with a closed-form policy selection probability. Simulation results demonstrate the efficiency of our algorithm in achieving low delay.

Mobile crowdsourcing has become an efficient paradigm for performing large scale tasks. The incentive mechanism is important for the mobile crowdsourcing system to stimulate participants, and to achieve good service quality. In this paper, we focus on solving the insufficient participation problem for the budget constrained online crowdsourcing system. We present a two-tiered social crowdsourcing architecture, which can enable the selected registered users to recruit their social neighbors by diffusing the tasks to their social circles. We present three system models for two-tiered social crowdsourcing system based on the arrival modes of registered users and social neighbors: offline model, semi-online model, and full-online model. We consider the tasks are associated with different end times. We present an incentive mechanism for each of three system models. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed incentive mechanisms achieve computational efficiency, individual rationality, budget feasibility, cost truthfulness, and time truthfulness. We further show that our incentive mechanisms for semi-online model and full-online model can obtain averagely 51.1$\%$and 39.7$\%$value of approximate optimal untruthful offline algorithm, respectively.

With the emergence of more and more powerful chipsets and hardware and the rise of Artificial Intelligence of Things (AIoT), there is a growing trend for bringing Deep Neural Network (DNN) models to empower mobile and edge devices with intelligence such that they can support attractive AI applications in a real-time manner. To leverage heterogeneous computational resources (such as CPU, GPU, DSP, etc.) to effectively and efficiently support the concurrent inference of multiple DNN models on a mobile or edge device, we propose a novel online Co-Scheduling framework based on deep REinforcement Learning, called COSREL. COSREL has the following desirable features: 1) it achieves significant speedup over commonly-used methods by efficiently utilizing all the computational resources on heterogeneous hardware; 2) it leverages emerging Deep Reinforcement Learning (DRL) to make dynamic and wise online scheduling decisions based on system runtime state; 3) it is capable of making a good tradeoff among inference latency, throughput, and energy efficiency; and 4) it makes no changes to given DNN models, thus preserves their accuracies. To evaluate COSREL, we conduct extensive experiments on an off-the-shelf Android smartphone. The experimental results show that COSREL consistently outperforms other baselines in terms of throughput, latency, and energy efficiency.

Payment Channel Network (PCN) is an auspicious solution to the scalability issue of the blockchain, improving transaction throughput without relying on on-chain transactions. In a PCN, nodes can set prices for forwarding payments on behalf of other nodes, which motivates participation and improves network stability. Analyzing the price setting behaviors of PCN nodes plays a key role in understanding the economic properties of PCNs, but has been under-studied in the literature. In this paper, we apply equilibrium analysis to the price-setting game between two payment hubs in the PCN with limited channel capacities and partial overlap demand. We analyze existence of pure Nash Equilibriums (NEs) and bounds on the equilibrium revenue under various cases, and propose an algorithm to find all pure NEs. Using real data, we show bounds on the price of anarchy/stability and average transaction fee under realistic network conditions, and draw conclusions on the economic advantage of the PCN for making payment transfers by cryptocurrency users.

Payment channel networks (PCNs) are proposed to improve the cryptocurrency scalability by settling off-chain transactions. However, a significant barrier is that a PCN user must solicit sufficient capital owned by the counterparty on its channel (i.e., inbound liquidity) to receive payments. To alleviate this inbound liquidity problem, Channel Liquidity Marketplaces (CLMs), e.g., Bitcoin's Lightning Pool, have been introduced, such that users can buy and sell inbound liquidity by trading crypto capital commitment in PCNs. Existing CLMs lack good incentive mechanisms that can attract more user participation. To fulfill this void, we design Cumulonimbus, an incentive mechanism for trading crypto capital commitment, which satisfies truthfulness, individual rationality, budget balance, and computational efficiency. Particularly, Cumulonimbus considers two unique features of crypto capital commitment, referred to as demand indivisibility and supply divisibility. Extensive simulations demonstrate that Cumulonimbus achieves higher satisfaction ratio, liquidity utilization, and social welfare compared with a state-of-the-art CLM mechanism Lightning Pool [18].

Understanding sign gestures is an essential step to helping individuals with hearing impaired. The existing works can only identify a small set of gestures accurately and the accuracy rate drops sharply with an increasing number of gestures. Because there are two challenges—a large number of similar gestures in sign language and the various signing speed of different people. Based on commercial smart bracelets, this article proposes a large-vocabulary sign language recognition system (which we call L-sign). First, we propose an entropy-based forward and backward matching algorithm to segment each gesture signal. Second, we design a gesture recognizer including a candidate gesture generator and semantic-based voter. The candidate gesture generator is aimed at providing candidate gesture designs based on a 3-branch convolutional neural network. The purpose of a semantic-based voter is to select the target gesture from candidate gestures by scoring, where the semantic distances between the last gesture in the current sentence and any candidate gestures is calculated, and a multilayer k-means algorithm is proposed to obtain a multilayer sign word structure to complete the scores of candidate gestures. Lastly, we deployed L-sign on the MYO bracelet. For 200 commonly used Chinese sign gestures, the experimental results show that the average accuracy rate was greater than 90%.

The success of online shopping accelerates the development of express delivery business with economic and efficient service. Current express delivery systems usually deliver the packages in noncooperation mode and cannot jointly optimize the express fee and moving cost of users. This paper proposes the cooperative package assignment system by lumping packages at the same express station to share the express fee, and proposes a novel pricing structure to stimulate the express stations to join the system without revenue loss by introducing cooperation cost. We formulate thecooperative package assignment (CPA)problem with heterogeneous express stations for joint optimization of users’ express fee and moving cost. Then, an approximate algorithm,CPAA, is proposed for theCPAproblem based on the greedy approach using submodular function minimization. We show that the designed algorithm achieves computational efficiency and guaranteed approximation. Furthermore, we model the large-scaleCPAproblem asCPA-gameand present a game theoretic algorithm,CPAGA. We show thatCPA-gamehas at least oneNash Equilibrium, andCPAGAfinally converges to a pureNash Equilibrium. Through extensive simulations, we demonstrate thatCPAAandCPAGAshow great advantages in terms of comprehensive cost, which is 28.1% and 19.9% lower than that in noncooperation mode on average, respectively. Moreover,CPAGAshows great scalability and is more suitable for large-scale cooperative package assignment systems.

Crowdsourcing has become an effective tool to utilize human intelligence to perform tasks that are challenging for machines. Many truth discovery methods and incentive mechanisms for crowdsourcing have been proposed. However, most of them cannot deal with the crowdsourcing with copiers, who copy a part (or all) of data from other workers. This article aims at designing crowdsourcing incentive mechanism for truth discovery of textual answers with copiers. We formulate the problem of maximizing the social welfare such that all tasks can be completed with the least confidence for truth discovery and design an three-stage incentive mechanism. In contextual embedding and clustering stage, we construct and cluster the content vector representations of textual crowdsourced answers at the semantic level. In truth discovery stage, we estimate the truth for each task based on the dependence and accuracy of workers. In reverse auction stage, we design a greedy algorithm to select the winners and determine the payment. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality, truthfulness, and guaranteed approximation. Moreover, our truth discovery methods show prominent advantage in terms of precision when there are copiers in the crowdsourcing systems.

Payment channel networks (PCNs) are proposed to improve the cryptocurrency scalability by settling off-chain transactions. However, PCN introduces an undesirable assumption that a channel participant must stay online and be synchronized with the blockchain to defend against frauds. To alleviate this issue, watchtowers have been introduced, such that a hiring party can employ a watchtower to monitor the channel for fraud. However, a watchtower might profit from colluding with a cheating counterparty and fail to perform this job. Existing solutions either focus on heavy cryptographic techniques or require a large collateral. In this work, we leverage smart contracts through economic approaches to counter collusions for watchtowers in PCNs. This brings distrust between the watchtower and the counterparty, so that rational parties do not collude or cheat. We provide detailed analyses on the contracts and rigorously prove that the contracts are effective to counter collusions with minimal on-chain operations. In particular, a watchtower only needs to lock a small collateral, which incentivizes participation of watchtowers and users. We also provide an implementation of the contracts in Solidity and execute them on Ethereum to demonstrate the scalability and efficiency of the contracts.

In recent years, mobile crowdsensing has become an effective method for large-scale data collection. Incentive mechanism is fundamentally important for mobile crowdsensing systems. Many mobile crowdsensing systems expect to optimize multiple objectives simultaneously. Most of the existing works transform the multiobjective problem into a single objective problem through constraints or scalarization method. However, due to the uncertain importance (weights) of objectives and the instable quality of crowdsensed data, such transformation is usually unrealizable. In this article, we aim to optimize the worst performance of two objective functions in mobile crowdsensing in order to improve the system robustness. We model an auction-based biobjective robust mobile crowdsensing system, and design two independent objective functions to maximize the expected profit and coverage, respectively. We formulate the robust user selection (RUS) problem, and design an incentive mechanism, which utilizes the combination of binary search and greedy algorithm, to solve the RUS problem. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the designed incentive mechanisms satisfy desirable properties of computational efficiency, individual rationality, truthfulness, and constant approximation to the tightened RUS problem. Moreover, the proposed incentive mechanism can be easily extended to multiobjective robust mobile crowdsensing systems, and all desirable properties still hold. The simulation results reveal that our incentive mechanism achieves 11% improvement of the platform’s utility, compared with the greedy algorithm for biobjective mobile crowdsensing systems on average.

The development of Electric Vehicle (EV) helps to ease energy crises and deduce vehicle exhaust emissions. However, it also brings a great impact on both transportation networks and power grids. There are some serious impediments in terms of energy charging to the popularization of EV, such as high deployment cost of charging stations, low charging efficiency, and voltage deviation of power grid. To address these issues, we design a new EV charging system, which levers the bus network in urban areas through the integration of OnLine Electric Vehicle (OLEV) system and Microwave Power Transfer (MPT) system. We formulate the EV route scheduling problem based on this new charging system to maximize the total residual energy subject to all EVs can arrive to their destinations before deadlines. Then, we propose an approximation algorithm, RSA, to solve the route scheduling problem. To relieve the traffic congestion, we further formulate the conflict-free EV route scheduling problem, and use the matching based algorithm, FRSA, to find the EV route schedules with the maximal residual energy. Through the extensive simulations, we demonstrate that RSA and FRSA can increase the average residual energy by 67.66% and 50.36% compared with the solution without the designed wireless charging system, respectively. Moreover, RSA reduces 22.22% of travel time and outputs 77.23% of residual energy, and FRSA can obtain 83.51% residual energy with 3.62% of extra travel time of the corresponding optimal solutions on average, respectively.

Experience-driven networking has emerged as a new and highly effective approach for resource allocation in complex communication networks. Deep Reinforcement Learning (DRL) has been shown to be a useful technique for enabling experience-driven networking. In this paper, we focus on a practical and fundamental problem for experience-driven networking: when network configurations are changed, how to train a new DRL agent to effectively and quickly adapt to the new environment. We present an Actor-Critic-based Transfer learning framework for the Traffic Engineering (TE) problem using policy distillation, which we call ACT-TE. ACT-TE effectively and quickly trains a new DRL agent to solve the TE problem in a new network environment, using both old knowledge (i.e., distilled from the existing agent) and new experience (i.e., newly collected samples). We implement ACT-TE in ns-3, and compare it with commonly-used baselines using packet-level simulations on three representative network topologies: NSFNET, ARPANET and random topology. The extensive simulation results show that 1) The existing well-trained DRL agents do not work well in new network environments; 2) ACT-TE significantly outperforms both two straightforward methods (training from scratch and fine-tuning based on an existing DRL agent) and several widely-used traditional methods in terms of network utility, throughput and delay.

The past decade has witnessed an explosive growth in cryptocurrencies, but the blockchain-based cryptocurrencies have also raised many concerns, among which a crucial one is the scalability issue. Suffering from the large overhead of global consensus and security assurance, even the leading cryptocurrencies can only handle up to tens of transactions per second, which largely limits their applications in real-world scenarios. Among many proposals to improve the cryptocurrency scalability, one of the most promising and mature solutions is the payment channel network (PCN), which offers the off-chain settlement of transactions with minimal involvement of expensive blockchain operations. However, transaction failures may occur due to external attacks or unexpected conditions, e.g., an uncooperative user becoming unresponsive. In this paper, we present a distributed robust payment routing protocol RobustPay+to resist transaction failures, which achieves robustness, efficiency, distributedness and approximate optimization. Specifically, we investigate the problem of robust routing in PCNs from an optimization perspective, which is to find a pair of payment paths for a payment request, while minimizing the worst-case transaction fee, subject to the timeliness and feasibility constraints. We present a distributed 2-approximation algorithm for this problem. Moreover, we modify the original Hashed Time-lock Contract (HTLC) protocol and adapt it to the robust payment routing protocol to achieve robustness and efficiency. Extensive simulations demonstrate that RobustPay+significantly outperforms baseline algorithms in terms of the success ratio and the average accepted value.

Blockchain based applications benefit from decentralization, data privacy, and anonymity. However, they may suffer from inefficiency due to underlying blockchain. In this paper, we aim to address this limitation while still enjoying the privacy and anonymity. Taking the blockchain based crowdsourcing system as an example, we propose a new smart contract based cyber-insurance framework, which can greatly shorten the delay, and enable the workers to obtain the economic compensation for increased security risk caused by a conflict between the need to provide service quickly and delay in payment. We model the process of determining insurance premium and number of confirmations as a Stackelberg Game and prove the existence of Stackelberg Equilibria, at which the utility of the requester is maximized, and none of the workers can improve its utility by unilaterally deviating from its current strategy. The experimental results show that our framework can definitely improve the time efficiency of crowdsourcing. Particularly, it takes on average only 33% of the time required by the naive blockchain based crowdsouring solution for time-sensitive cases.

Edge computing is one of the revolutionary technologies that enable high-performance and low-latency modern applications, such as smart cities, connected vehicles, etc. Yet its adoption has been limited by factors including high cost of edge resources, heterogeneous and fluctuating demands, and lack of reliability. In this paper, we study resource provisioning in edge computing, taking into account these different factors. First, based on observations from real demand traces, we propose a time-varying stochastic model to capture the time-dependent and uncertain demand and network dynamics in an edge network. We then apply a novel robustness model that accounts for both expected and worst-case performance of a service. Based on these models, we formulate edge provisioning as a multi-stage stochastic optimization problem. The problem is NP-hard even in the deterministic case. Leveraging the multi-stage structure, we apply nested Benders decomposition to solve the problem. We also describe several efficiency enhancement techniques, including a novel technique for quickly solving the large number of decomposed subproblems. Finally, we present results from real dataset-based simulations, which demonstrate the advantages of the proposed models, algorithm and techniques.

Crowdsensing enables a wide range of data collection, where the data are usually tagged with private locations. Protecting users' location privacy has been a central issue. The study of various location perturbation techniques, e.g., k-anonymity, for location privacy has received widespread attention. Despite the huge promise and considerable attention, provable good algorithms considering the tradeoff between location privacy and location information quality from the optimization perspective in crowdsensing are lacking in the literature. In this article, we study two related optimization problems from two different perspectives. The first problem is to minimize the location quality degradation caused by the protection of users' location privacy. We present an efficient optimal algorithm OLoQ for this problem. The second problem is to maximize the number of protected users, subject to a location quality degradation constraint. To satisfy the different requirements of the platform, we consider two cases for this problem: 1) overlapping and 2) nonoverlapping perturbations. For the former case, we give an efficient optimal algorithm OPUMO. For the latter case, we first prove its NP-hardness. We then design a (1-E)-approximation algorithm NPUMNand a fast and effective heuristic algorithm HPUMN. Extensive simulations demonstrate that OLoQ, OPUMO, and HPUMNsignificantly outperform an existing algorithm.

Mobile crowd sensing emerges as a new paradigm which takes advantage of the pervasive sensor-embedded smartphones to collect data. Many incentive mechanisms for mobile crowd sensing have been proposed. However, none of them takes into consideration the cooperative compatibility of users for multiple cooperative tasks. In this paper, we design truthful incentive mechanisms to minimize the social cost such that each of the cooperative tasks can be completed by a group of compatible users. We study two bid models and formulate the Social Optimization Compatible User Selection (SOCUS) problem for each model. We also define three compatibility models and use real-life relationships from social networks to model the compatibility relationships. We design two incentive mechanisms, MCT - M and MCT - S, for the compatibility cases. Both of MCT - M and MCT - S consist of two steps: compatible user grouping and reverse auction. We further present a user grouping method through neural network model and clustering algorithm. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality, and truthfulness. Moreover, MCT - M can output the optimal solution. By using neural network and clustering algorithm for user grouping, the proposed incentive mechanisms can reduce the social cost and overpayment ratio further with less grouping time.

Incentive mechanisms have been commonly proposed to encourage people to participate in mobile crowdsensing (MCS). However, most of them set unchangeable rewards for sensing tasks, while the inherent inequality and on-demand feature of sensing tasks have been long ignored, especially for location-dependent sensing tasks (LDSTs). In this paper, we focus on location-dependent MCS systems and propose a demand-driven dynamic incentive mechanism that dynamically changes the rewards of sensing tasks at each sensing round in an on-demand way to balance their popularity. A demand indicator is introduced to characterize the demand of each sensing task by considering its deadline, completing progress, and number of potential participants. At each sensing round, we use the Analytic Hierarchy Process (AHP) to calculate the relative demands of all sensing tasks and then determine their rewards accordingly. Moreover, we consider two task selection problem with participatory users and opportunistic users, respectively, and prove that both of them are NP-hard. We propose an optimal dynamic programming based solution for participatory scenario and an optimal backtracking based solution for opportunistic scenario to help each user select tasks while maximizing its profit. Extensive experiments show that the demand-driven dynamic incentive mechanism outperforms existing incentive mechanisms.

Recent advances in security and cryptography have enabled new paradigms for secure networking in various scenarios. The payment channel network (PCN) is a notable example, which has emerged from the combination of the traditional credit network in economics and the latest blockchain technology. PCN provides a secure and efficient way for conducting payments, by addressing both the intrinsic financial risk of the credit network and the scalability issue of the blockchain. A crucial challenge in PCN is routing, i.e., to find a set of paths that fulfill a payment request. Due to the fully distributed and dynamic nature of PCN, existing routing algorithms utilize active probing to improve routing success probability. However, while the payment itself is privacy-preserving through existing protocols, the probing process can leak sensitive information including the location of the sender or the recipient. In this paper, we address the privacy of the users in the path probing process, filling in the last piece of the privacy puzzle in PCN. We propose P4PCN, a cryptographic protocol for anonymous active probing without knowing the identities or public keys of the intermediate nodes, while hiding the locations of sender and recipient as well as any path-related information. Our protocol is lightweight and scales with the number of hops a probe explores. We confirm its performance via real-world implementation and simulation experiments.

The past decade has seen vast research on the influence maximization problem in social networks: How to select a subset of individuals to become initial adopters, so that the word-of-mouth effect in the social network is maximized Approximation algorithms have been proposed for this NP-hard problem with knapsack or other constraints. To incentivize influencers to become initial adopters, Singer has initiated budget feasible mechanisms. In this paper, we generalize them to the budget feasible mechanism for k-topic influence maximization problem. We investigate this problem and propose KIMI. We rigorously prove that KIMI achieves 5e/(e-1) approximation and computational efficiency, individual rationality, truthfulness, budget feasibility. Extensive simulations demonstrate that KIMI significantly outperforms baseline methods.

Crowdsensing enables a wide range of data collection, where the data are usually tagged with private locations. Protecting users' location privacy has been a central issue. The study of various location perturbation techniques for protecting users' location privacy has received widespread attention. Despite the huge promise and considerable attention, the location perturbation operation causes inevitable location errors, which can diminish the location quality of the crowdsensing results. Provable good algorithms that consider location quality in privacy preserving crowdsensing from optimization perspectives are still lacking in the literature. In this paper, we investigate the problem of location quality optimization in privacy preserving crowdsensing, which is to minimize the location quality desegregation, while protecting all users' location privacy. We present an optimal algorithm OLQDM for this problem. Extensive simulations demonstrate that OLQDM significantly outperforms an existing algorithm in terms of the location quality and SSE.

Pervasive mobile devices and their advances in sensing and networking have led to an emerging mobile sensing paradigm. The diversity of mobile users and the openness of sensing systems raise several crucial concerns for users' privacy, data quantity, and quality. Although different aspects of these issues were addressed separately in existing researches, there is still a need to provide a holistic solution for secure and privacy-aware mobile sensing. In this paper, we propose a privacy-aware and trustworthy mobile sensing scheme with fair incentives. Leveraging group signature, (partial) blind signature, and limited number of pseudonyms technologies, our scheme enables well-behaved users to contribute their data anonymously, and prevents both greedy and malicious users from abusing the privacy protection. Moreover, we design a fair incentive scheme to stimulate users to contribute high-quality data, based on the data quality and the reputation feedback level. Security analysis demonstrates that our proposed scheme achieves the security goals. Extensive evaluation results are presented which demonstrate the effectiveness and efficiency of our scheme.

The past several years have witnessed an explosive growth in cryptocurrencies, but the blockchain-based cryptocurrencies have also raised many concerns, among which a crucial one is the scalability issue. Suffering from the large overhead of global consensus and security assurance, even the leading cryptocurrencies can only handle up to tens of transactions per second, which largely limits their applications in real-world scenarios. Among many proposals to improve the cryptocurrency scalability, one of the most promising and mature solutions is the payment channel network (PCN), which offers the off-chain settlement of transactions with minimal involvement of expensive blockchain operations. In this paper, we investigate the problem of payment routing in PCNs from an optimization perspective, which is to minimize the transaction fee of a payment path, subject to the timeliness and feasibility constraints. We present an optimal distributed algorithm CheaPay for this problem. Extensive simulations demonstrate that CheaPay significantly outperforms baseline algorithms in terms of the success ratio and the average accepted value.

The rapid proliferation of sensor-embedded devices has enabled the mobile crowdsensing (MCS), a new paradigm which effectively collects sensing data from pervasive users. In order to identify the true information from the noisy data submitted by unreliable users, truth discovery algorithms have been proposed for the MCS systems to aggregate data. However, the power of truth discovery algorithms will be undermined by the Sybil attack, in which an attacker can benefit from using multiple accounts. In addition, an MCS system will be jeopardized unless it is resistant to the Sybil attack. In this paper, we proposed a Sybil-resistant truth discovery framework for MCS, which ensures high accuracy under the Sybil attack. To diminish the impact of the Sybil attack, we design three account grouping methods for the framework, which are used in pair with a truth discovery algorithm. We evaluate the proposed framework through a real-world experiment. The results show that existing truth discovery algorithms are vulnerable to the Sybil attack, and the proposed framework can effectively diminish the impact of the Sybil attack.

Crowdsourcing has become an efficient paradigm for performing large scale tasks. Truth discovery and incentive mechanism are fundamentally important for the crowdsourcing system. Many truth discovery methods and incentive mechanisms for crowdsourcing have been proposed. However, most of them cannot be applied to dealing with the crowdsourcing with copiers. To address the issue, we formulate the problem of maximizing the social welfare such that all tasks can be completed with the least confidence for truth discovery. We design an incentive mechanism consisting of truth discovery stage and reverse auction stage. In truth discovery stage, we estimate the truth for each task based on both the dependence and accuracy of workers. In reverse auction stage, we design a greedy algorithm to select the winners and determine the payment. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality, truthfulness, and guaranteed approximation. Moreover, our truth discovery method shows prominent advantage in terms of precision when there are copiers in the crowdsourcing systems.

The past decade has witnessed an explosive growth in cryptocurrencies, but the blockchain-based cryptocurrencies have also raised many concerns, among which a crucial one is the scalability issue. Suffering from the large overhead of global consensus and security assurance, even the leading cryptocurrencies can only handle up to tens of transactions per second, which largely limits their applications in real-world scenarios. Among many proposals to improve the cryptocurrency scalability, one of the most promising and mature solutions is the payment channel network (PCN), which offers the off-chain settlement of transactions with minimal involvement of expensive blockchain operations. However, transaction failures may occur due to external attacks or unexpected conditions, e.g., an uncooperative user becoming unresponsive. In this paper, we present a distributed robust payment routing protocol RobustPay to resist transaction failures, which achieves robustness, efficiency and distributedness. Moreover, we modify the original HTLC protocol and adapt it to the robust payment routing protocol.

Advances in virtualization technologies and edge computing have inspired a new paradigm for Internet-of-Things (IoT) application development. By breaking a monolithic application into loosely coupled microservices, great gain can be achieved in performance, flexibility and robustness. In this paper, we study the important problem of load balancing across IoT microservice instances. A key difficulty in this problem is the interdependencies among microservices: the load on a successor microservice instance directly depends on the load distributed from its predecessor microservice instances. We propose a graph-based model for describing the load dependencies among microservices. Based on the model, we first propose a basic formulation for load balancing, which can be solved optimally in polynomial time. The basic model neglects the quality-of-service (QoS) of the IoT application. We then propose a QoS-aware load balancing model, based on a novel abstraction that captures a realization of the application's internal logic. The QoS-aware load balancing problem is NP-hard. We propose a fully polynomial-time approximation scheme for the QoS-aware problem. We show through simulation experiments that our proposed algorithm achieves enhanced QoS compared to heuristic solutions.

Mobile crowdsensing emerges as a new paradigm that takes advantage of pervasive sensor-embedded smartphones to collect sensory data. Many incentive mechanisms for mobile crowdsensing have been proposed. However, none of them takes into consideration the spatio-temporal tasks in mobile crowdsensing systems, where the sensing areas of tasks can have overlaps, and the collective sensing time for each task needs to meet the specified time duration. In this paper, we present two system models for location sensitive users and location insensitive users, respectively, and formulate the social optimization problem for each model. We design two reverse auction based truthful incentive mechanisms to minimize the social cost subject to the constraint that each of the spatio-temporal tasks can be completed with its collective sensing time no less than a minimum sensing time required by the platform. Through both theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality, truthfulness, and guaranteed approximation.

Mobile crowd sensing is a new paradigm that enables smart mobile devices to collect and share various types of sensing data in urban environments. However, new challenges arise: one is how to evaluate the quality of data each mobile user potentially is capable of providing; another is how to allocate a satisfactory yet profitable amount of reward to mobile users in order to keep them participating in crowd sensing tasks. In this paper, we first introduce a mathematical model for characterizing quality of sensing data to be contributed by mobile users. Then, we present a utility function and formulate an optimization problem for the platform, who recruits participants to contribute sensing data, to maximize the amount of high quality sensing data under a limited task budget. We next present an effective and quality-aware incentive mechanism to solve this problem for online scenarios where participants may arrive or leave at any random time. Moreover, the proposed incentive mechanism allows the platform to provide selected participants with an extra bonus according to task completion level and their previous performance to motivate them further. We formally show the proposed mechanism has the desirable properties of truthfulness, individual rationality, budgetary feasibility, and computational efficiency. We compare the proposed scheme with existing methods via simulation using a real dataset. Extensive simulation results well justify the effectiveness and robustness of the proposed approach, e.g, compared with another online method “OMG”, the gap to the optimum for our proposed Online-QIM approach is reduce by 33.3 percent when budget B = 1000.

Location information of workers are usually required for optimal task allocation in mobile crowdsensing, which however raises severe concerns of location privacy leakage. Although many approaches have been proposed to protect the locations of users, the location protection for task allocation in mobile crowdsensing has not been well explored. In addition, to the best of our knowledge, none of existing privacy-preserving task allocation mechanisms can provide personalized location protection considering different protection demands of workers. In this paper, we propose a personalized privacy-preserving task allocation framework for mobile crowdsensing that can allocate tasks effectively while providing personalized location privacy protection. The basic idea is that each worker uploads the obfuscated distances and personal privacy level to the server instead of its true locations or distances to tasks. In particular, we propose a Probabilistic Winner Selection Mechanism (PWSM) to minimize the total travel distance with the obfuscated information from workers, by allocating each task to the worker who has the largest probability of being closest to it. Moreover, we propose a Vickrey Payment Determination Mechanism (VPDM) to determine the appropriate payment to each winner by considering its movement cost and privacy level, which satisfies the truthfulness, profitability, and probabilistic individual rationality. Extensive experiments on the real-world datasets demonstrate the effectiveness of the proposed mechanisms.

Ubiquitous mobile devices with rich sensors and advanced communication capabilities have given rise to mobile crowdsensing systems. The diverse reliabilities of mobile users and the openness of sensing paradigms raise concerns for data trustworthiness, user privacy, and incentive provision. Instead of considering these issues as isolated modules in most existing researches, we comprehensively capture both conflict and inner-relationship among them. In this paper, we propose a holistic solution for trustworthy and privacy-aware mobile crowdsensing with no need of a trusted third party. Specifically, leveraging cryptographic technologies, we devise a series of protocols to enable benign users to request tasks, contribute their data, and earn rewards anonymously without any data linkability. Meanwhile, an anonymous trust/reputation model is seamlessly integrated into our scheme, which acts as reference for our fair incentive design, and provides evidence to detect malicious users who degrade the data trustworthiness. Particularly, we first propose the idea of limiting the number of issued pseudonyms which serves to efficiently tackle the anonymity abuse issue. Security analysis demonstrates that our proposed scheme achieves stronger security with resilience against possible collusion attacks. Extensive simulations are presented which demonstrate the efficiency and practicality of our scheme.

The scarcity of spectrum channels resides in the limited bandwidth resource and the exploding demand from spectrum-based services and devices. To help ease this scarcity, the concept of cognitive radio networks (CRNs) is proposed, where licensed spectrum holders (primary users) may lease their channels to unlicensed users (secondary users). Many CRN auctions are thus designed to incentivize primary users (PUs) to share their idle channels with secondary users (SUs). Most of these auctions assume that a transmitting PU does not lease its channel to SUs; if it leases its channel to SUs, it does not transmit itself. To further utilize the resource, researchers have studied the scenario where a transmitting PU is allowed to lease its channels to SUs if the transmissions of the SUs do not undermine the transmission of the PU. However, the study assumes that there is only one PU who owns the licensed channels, whereas in practice, channels may be contributed by multiple PUs. This prevents the result of the study from being directly applied to the multi-PU scenario, as the potential competitions among the PUs are neglected. We extend the scenario to the CRN with multiple PUs and propose TDSA-PS as a Truthful Double Spectrum Auction with transmitting Primary users Sharing. We prove that TDSA-PS is truthful, individually rational, budget-balanced, and computationally efficient.

Although cryptocurrencies have witnessed explosive growth in the past year, they have also raised many concerns, among which a crucial one is the scalability issue of blockchain-based cryptocurrencies. Suffering from the large overhead of global consensus and security assurance, even leading cryptocurrencies can only handle up to tens of transactions per second, which largely limits their applications in real- world scenarios. Among many proposals to improve cryptocurrency scalability, one of the most promising and mature solutions is the payment channel network (PCN), which offers off-chain settlement of transactions with minimal involvement of expensive blockchain operations. In this paper, we investigate the problem of payment routing in PCN. We suggest crucial design goals in PCN routing, and propose a novel distributed dynamic routing mechanism called CoinExpress. Through extensive simulations, we have shown that our proposed mechanism is able to achieve outstanding payment acceptance ratio with low routing overhead.

With the rich sensing capacity and ubiquitous usage of smartphones, crowdsensing leveraging the power of the crowd of mobile users has become an effective technique to collect data for various sensing applications. Many incentive mechanisms have been proposed to encourage people to participate in crowdsensing. However, most of them set unchangeable rewards for sensing tasks, while the inherent inequality and on-demand feature of sensing tasks have been long ignored, especially for location-dependent sensing tasks. In this paper, we focus on location-dependent crowdsensing systems and propose a demand-based dynamic incentive mechanism that dynamically changes the rewards of sensing tasks at each sensing round in an on-demand way to balance their popularity. A demand indicator is introduced to characterize the demand of each sensing task by considering its deadline, completing progress, and number of potential participants. At each sensing round, we use the Analytic Hierarchy Process to calculate the relative demands of all sensing tasks and then determine their rewards accordingly. Moreover, we prove that the distributed task selection problem with time budget is NP-hard. We propose an optimal dynamic programming based solution and a greedy solution to help each user select tasks while maximizing its profit. Extensive experiments show that the demand-based dynamic incentive mechanism outperforms existing incentive mechanisms.

Crowdsensing leverages the rapid growth of sensor-embedded smartphones and human mobility for pervasive information collection. To incentivize smartphone users to participate in crowdsensing, many auction-based incentive mechanisms have been proposed for both offline and online scenarios. It has been demonstrated that the Sybil attack may undermine these mechanisms. In a Sybil attack, a user illegitimately pretends multiple identities to gain benefits. Sybil-proof incentive mechanisms have been proposed for the offline scenario. However, the problem of designing Sybil-proof online incentive mechanisms for crowdsensing is still open. Compared to the offline scenario, the online scenario provides users one more dimension of flexibility, i.e., active time, to conduct Sybil attacks, which makes this problem more challenging. In this paper, we design Sybil-proof online incentive mechanisms to deter the Sybil attack for crowdsensing. Depending on users' flexibility on performing their tasks, we investigate both single-minded and multi-minded cases and propose SOS and SOM, respectively. SOS achieves computational efficiency, individual rationality, truthfulness, and Sybil-proofness. SOM achieves individual rationality, truthfulness, and Sybil-proofness. Through extensive simulations, we evaluate the performance of SOS and SOM.

Modern communication networks have become very complicated and highly dynamic, which makes them hard to model, predict and control. In this paper, we develop a novel experience-driven approach that can learn to well control a communication network from its own experience rather than an accurate mathematical model, just as a human learns a new skill (such as driving, swimming, etc). Specifically, we, for the first time, propose to leverage emerging Deep Reinforcement Learning (DRL) for enabling model-free control in communication networks; and present a novel and highly effective DRL-based control framework, DRL-TE, for a fundamental networking problem: Traffic Engineering (TE). The proposed framework maximizes a widely-used utility function by jointly learning network environment and its dynamics, and making decisions under the guidance of powerful Deep Neural Networks (DNNs). We propose two new techniques, TE-aware exploration and actor-critic-based prioritized experience replay, to optimize the general DRL framework particularly for TE. To validate and evaluate the proposed framework, we implemented it in ns-3, and tested it comprehensively with both representative and randomly generated network topologies. Extensive packet-level simulation results show that 1) compared to several widely-used baseline methods, DRL-TE significantly reduces end-to-end delay and consistently improves the network utility, while offering better or comparable throughput; 2) DRL-TE is robust to network changes; and 3) DRL-TE consistently outperforms a state-of-the-art DRL method (for continuous control), Deep Deterministic Policy Gradient (DDPG), which, however, does not offer satisfying performance.

Mobile crowdsourcing has become an efficient paradigm for performing large scale tasks. The incentive mechanism is important for the mobile crowdsourcing system to stimulate participants, and to achieve good service quality. In this paper, we focus on solving the insufficient participation problem in the budget constrained online crowdsourcing system. We present a two-tiered social crowdsourcing architecture, which can enable the selected registered users to recruit their social neighbors by diffusing the tasks to their social circles. In the two-tiered social crowdsourcing system, the tasks are associated with different end times, and both the registered users and their social neighbors have different arrival/departure times. An online incentive mechanism, MTSC, which consists of two steps: Agent Selection and Online Reverse Auction, is proposed for this novel mobile crowdsourcing system. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed incentive mechanism achieves computational efficiency, individual rationality, budget feasibility, cost truthfulness, and time truthfulness.

With the rapid growth of smartphones, mobile crowdsensing emerges as a new paradigm which takes advantage of the pervasive sensor-embedded smartphones to collect data efficiently. Many auction-based incentive mechanisms have been proposed to stimulate smartphone users to participate in the mobile crowdsensing applications and systems. However, none of them has taken into consideration both the bid privacy of smartphone users and the social cost. In this paper, we design two frameworks for privacypreserving auction-based incentive mechanisms that also achieve approximate social cost minimization. In the former, each user submits a bid for a set of tasks it is willing to perform; in the latter, each user submits a bid for each task in its task set. Both frameworks select users based on platform-defined score functions. As examples, we propose two score functions, linear and log functions, to realize the two frameworks. We rigorously prove that both proposed frameworks achieve computational efficiency, individual rationality, truthfulness, differential privacy, and approximate social cost minimization. In addition, with log score function, the two frameworks are asymptotically optimal in terms of the social cost. Extensive simulations evaluate the performance of the two frameworks and demonstrate that our frameworks achieve bid-privacy preservation although sacrificing social cost.

Crowdsourcing is an emerging paradigm for spectrum access rule enforcement in dynamic spectrum sharing, which leverages a large number of mobile users to help monitoring and detecting spectrum violations and misuse. Its main advantages compared with traditional dedicated monitoring architecture includes enhanced coverage, effectiveness and lower costs. However, how to optimally assign mobile users to monitor the channel usage has not been studied in the crowdsourced setting. The main challenges are: the large number of channels to monitor while mobile users may not be available all the time, the need to consider monitoring costs and incentives, as well as the uncertainty of each channel's traffic patterns. In this paper, we tackle such challenges by formulating a stochastic optimization problem that optimizes the spectrum monitoring task for crowdsourced mobile users. We consider the availability pattern of the mobile users and we assume they are given payments as incentives for participating in monitoring. Simulations show that our method outperforms the risk-averse scenario and has a small gap with the solution under perfect information.

With the proliferation of smart mobile devices (smart phone, tablet, and wearable), mobile crowdsensing becomes a powerful sensing and computation paradigm. It has been put into application in many fields, such as spectrum sensing, environmental monitoring, healthcare, and so on. Driven by promising incentives, the power of the crowd grants crowdsensing an advantage in mobilizing users who perform sensing tasks with the embedded sensors on the smart devices. Auction is one of the commonly adopted crowdsensing incentive mechanisms to incentivize users for participation. However, it does not consider the incentive for user solicitation, where in crowdsensing, such incentive would ease the tension when there is a lack of crowdsensing users. To deal with this issue, we aim to design an auction-based incentive tree to offer rewards to users for both participation and solicitation. Meanwhile, we want the incentive mechanism to be robust against dishonest behavior such as untruthful bidding and sybil attacks, to eliminate malicious price manipulations. We design RIT as a Robust Incentive Tree mechanism for mobile crowdsensing which combines the advantages of auctions and incentive trees. We prove that RIT is truthful and sybil-proof with probability at least H, for any given H ∈ (0, 1). We also prove that RIT satisfies individual rationality, computational efficiency, and solicitation incentive. Simulation results of RIT further confirm our analysis.

The rapid growth of sensor-embedded smartphones has led to a new data sensing and collecting paradigm, known as crowdsensing. Many auction-based incentive mechanisms have been proposed to stimulate smartphone users to participate in crowdsensing. However, none of them have taken into consideration the Sybil attack where a user illegitimately pretends multiple identities to gain benefits. This attack may undermine existing inventive mechanisms. To deter the Sybil attack, we design Sybil-proof auction-based incentive mechanisms for crowdsensing in this paper. We investigate both the single-minded and multi-minded cases and propose SPIM-S and SPIM-M, respectively. SPIM-S achieves computational efficiency, individual rationality, truthfulness, and Sybil-proofness. SPIM-M achieves individual rationality, truthfulness, and Sybil-proofness. We evaluate the performance and validate the desired properties of SPIM-S and SPIM-M through extensive simulations.

In this paper, we propose to leverage the emerging deep learning techniques for spatiotemporal modeling and prediction in cellular networks, based on big system data. First, we perform a preliminary analysis for a big dataset from China Mobile, and use traffic load as an example to show non-zero temporal autocorrelation and non-zero spatial correlation among neighboring Base Stations (BSs), which motivate us to discover both temporal and spatial dependencies in our study. Then we present a hybrid deep learning model for spatiotemporal prediction, which includes a novel autoencoder-based deep model for spatial modeling and Long Short-Term Memory units (LSTMs) for temporal modeling. The autoencoder-based model consists of a Global Stacked AutoEncoder (GSAE) and multiple Local SAEs (LSAEs), which can offer good representations for input data, reduced model size, and support for parallel and application-aware training. Moreover, we present a new algorithm for training the proposed spatial model. We conducted extensive experiments to evaluate the performance of the proposed model using the China Mobile dataset. The results show that the proposed deep model significantly improves prediction accuracy compared to two commonly used baseline methods, ARIMA and SVR. We also present some results to justify effectiveness of the autoencoder-based spatial model.

Crowdsensing is a sensing method which involves participants from general public to collect sensed data from their mobile devices, and also contribute and utilize a common database. To ensure a crowdsensing system to operate properly, there must be certain effective and efficient incentive mechanism to attract users and stimulate them to submit sensing data with high quality. Intuitively, the agreement on the qualities and payments in crowdsensing systems can be best modeled as a contract. However, none of existing incentive mechanisms consider data quality through effective contract design. In this paper, we design two quality-aware contract-based incentive mechanisms for crowdsensing, named QUAC-F and QUAC-I, under full information model and incomplete information model, respectively, which differ in the level of users' information known to the system. Both QUAC-F and QUAC-I are guaranteed to maximize the platform utility while satisfying individual rationality and incentive compatibility. We evaluate the performance of our designed mechanisms based on a real dataset.

Mobile crowd sensing emerges as a new paradigm which takes advantage of the pervasive sensor-embedded smartphones to collect data efficiently. Many incentive mechanisms for mobile crowd sensing have been proposed. However, none of them takes into consideration the cooperative compatibility of users for multiple cooperative tasks. In this paper, we design truthful incentive mechanisms to minimize the social cost such that each of the cooperative tasks can be completed by a group of compatible users. We consider that the mobile crowd sensing is launched in an online community. We study two bid models and formulated the Social Optimization Compatible User Selection (SOCUS) problem for each model. We also define three compatibility models and use real-life relationships from social networks to model the compatibility relationships. We design two reverse auction based incentive mechanisms, MCT-M and MCT-S. Both of them consist of two steps: compatible user grouping and reverse auction. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve computational efficiency, individual rationality and truthfulness. In addition, MCT-M can output the optimal solution.

Crowdsourcing has become an effective tool to utilize human intelligence to perform tasks that are challenging for machines. In the integrated crowdsourcing systems, the requesters are non- monopolistic and may show preferences over the workers. We are the first to design the incentive mechanisms, which consider the issue of stimulating the biased requesters in the competing crowdsourcing market. In this paper, we explore truthful task assignment mechanisms to maximize the total value of accomplished tasks for this new scenario. We present three models of crowdsourcing, which take the preferences of the requesters and the workload constraints of the workers into consideration. We design a task assignment mechanism, which follows the matching approach to solve the Valuation Maximizing Assignment (VMA) problem for each of the three models. Through both rigorous theoretical analyses and extensive simulations, we demonstrate that the proposed assignment mechanisms achieve computational efficiency, workload feasibility, preference (universal) truthfulness and constant approximation.

The proliferation of crowdsourcing brings both opportunities and challenges in various fields, such as environmental monitoring, healthcare, and so on. Often, the collaborative efforts from a large crowd of users are needed in order to complete crowdsourcing jobs. In recent years, the design of crowdsourcing incentive mechanisms has drawn much interest from the research community, where auction is one of the commonly adopted mechanisms. However, few of these auctions consider the robustness against false-name attacks (a.k.a. sybil attacks), where dishonest users generate fake identities to increase their utilities without devoting more efforts. To provide countermeasures against such attacks, we have designed a Truthful Auction with countermeasures against False-name Attacks (TAFA) as an auction-based incentive mechanism for crowdsourcing. We prove that TAFA is truthful, individually rational, budget-balanced, and computationally efficient. We also prove that TAFA provides countermeasures against false-name attacks, such that each user is better off not generating any false name. Extensive performance evaluations are conducted and the results further confirm our theoretical analysis.

A fundamental problem in cognitive radio networks (CRN) is the following capacity maximization in CRN (CM-CRN) problem: given a set of primary links with a common transmitter, together with a set of secondary links, select a maximum cardinality subset of the links that can concurrently transmit successfully under the constraint that all primary links are selected. This problem is intrinsically different from the well-known link scheduling (LS) problem in wireless mesh networks, which does not have the constraint to select all primary links. In this paper, we make both theoretical and practical contributions to the CM-CRN problem. To achieve deep theoretical understanding of the problem, we show that CM-CRN is NP-hard and design a polynomial time approximation algorithm with a constant approximation ratio. In addition, we extend the designed algorithm to find approximate solutions to two variations of CM-CRN, one with the objective of maximizing the number of selected secondary links and the other with multiple primary users. To achieve good performance in practice, we design a simple but effective heuristic algorithm based on a greedy strategy. We also design an optimal algorithm based on integer linear programming, which serves as a benchmark for evaluating the performance of the approximation algorithm and heuristic algorithm, for problem instances of small sizes. Extensive evaluations show that our proved constant ratio of the approximation algorithm is considerably conservative and our heuristic algorithm produces results that are very close to the optimal solution. Our approximation algorithm for CM-CRN is motivated by and can be viewed as a non-trivial extension of the elegant approximation algorithm for the LS problem by Wan et al. to CRNs.

We envision that in the near future, just as Infrastructure-as-a-Service, radios, and radio resources in a wireless network can also be provisioned as a service to mobile virtual network operators (MVNOs), which we refer to as Radio-as-a-Service (RaaS). A major obstacle for wide adoption of RaaS is the lack of incentives and fairness for allocating radio resources among MVNOs. In this paper, we present a novel auction-based model to enable fair pricing and fair resource allocation according to real-time needs of MVNOs for RaaS. Based on the proposed model, we study the auction mechanism design with the objective of maximizing social welfare. First, we present an integer linear programming and Vickrey-Clarke-Groves-based auction mechanism for obtaining optimal social welfare. To reduce time complexity, we present a polynomial-time greedy mechanism for the RaaS auction. Both methods have been formally shown to be truthful and individually rational. Extensive simulation results show that the proposed greedy auction mechanism can quickly produce close-to-optimal solutions. Furthermore, to prevent winning bidders from making 0 payment, we introduce reserve prices, and present auction mechanisms with reserve prices, which are shown to be truthful and individually rational too.

In this paper, we propose to learn Lifestyles of mobile users via mobile Phone Sensing (LIPS), and we develop a system and algorithms to realize this idea. First, we present the workflow and architecture of our system, LIPS. Combining both unsupervised and supervised learning, we propose a hybrid scheme for lifestyle learning, which consists of two parts: characterization and prediction. Specifically, we present a two-stage algorithm to characterize the lifestyle of a mobile user using Places of Interest (PoIs), which leverages two different algorithms for coarse-grained and fine-grained clustering in two stages respectively. Based on discovered PoIs, we present a method to build a model to predict his/her future activities using a supervised classification algorithm. In addition, we present an adaptive sampling algorithm for improving energy efficiency, which leverages both the discovered PoIs and the lifestyle model for adaptively controlling the sampling rate. We implemented the proposed system and algorithms based on the Android platform. We have validated and evaluated LIPS via extensive field tests carried out for over 1.5 months in 6 cities of USA. The experimental results show that LIPS can 1) well discover PoIs of mobile users, 2) precisely predict their future activities, and 3) achieve significant energy savings (compared to periodic sampling).

Spectrum auctions provide a platform for licensed spectrum users to share their underutilized spectrum with unlicensed users. Existing spectrum auctions either use the protocol interference model to characterize interference relationship as binary relationship, or do not allow the primary and secondary users to share channels simultaneously. To fill this void, we design SPA, a spectrum single-sided auction under the physical interference model, which considers the interference to be accumulative. We prove that SPA is truthful, individually rational, and computationally efficient. Results from extensive simulation studies demonstrate that, SPA achieves higher spectrum utilization and buyer satisfaction ratio, compared with an existing auction adapted for the physical interference model.

Limited research efforts have been made for Mobile CrowdSensing (MCS) to address quality of the recruited crowd, i.e., quality of services/data each individual mobile user and the whole crowd are potentially capable of providing, which is the main focus of the paper. Moreover, to improve flexibility and effectiveness, we consider fine-grained MCS, in which each sensing task is divided into multiple subtasks and a mobile user may make contributions to multiple subtasks. In this paper, we first introduce mathematical models for characterizing the quality of a recruited crowd for different sensing applications. Based on these models, we present a novel auction formulation for quality-aware and fine-grained MCS, which minimizes the expected expenditure subject to the quality requirement of each subtask. Then we discuss how to achieve the optimal expected expenditure, and present a practical incentive mechanism to solve the auction problem, which is shown to have the desirable properties of truthfulness, individual rationality and computational efficiency. We conducted trace-driven simulation using the mobility dataset of San Francisco taxies. Extensive simulation results show the proposed incentive mechanism achieves noticeable expenditure savings compared to two well-designed baseline methods, and moreover, it produces close-to-optimal solutions.

In cognitive radio networks (CRNs), dynamic spectrum access has been proposed to improve the spectrum utilization, but it also generates spectrum misuse problems. One common solution to these problems is to deploy monitors to detect misbehaviors on certain channel. However, in multi-channel CRNs, it is very costly to deploy monitors on every channel. With a limited number of monitors, we have to decide which channels to monitor. In addition, we need to determine how long to monitor each channel and in which order to monitor, because switching channels incurs costs. Moreover, the information about the misuse behavior is not available a priori. To answer those questions, we model the spectrum usage monitoring problem as an adversarial multi-armed bandit problem with switching costs and design two effective online algorithms, SpecWatch and SpecWatch+. In SpecWatch, we select strategies based on the monitoring history and repeat the same strategy for certain timeslots to reduce switching costs. We prove its expected weak regret, i.e., the performance difference between the solution of SpecWatch and optimal (fixed) solution, is O(T2/3), where T is the time horizon. Whereas, in SpecWatch+, we select strategies more strategically to improve the performance. We show its actual weak regret is O(T2/3) with probability 1-δ, for any δ e (0,1). Both algorithms are evaluated through extensive simulations.

Machine-to-Machine (M2M) mobile networks are distributed systems which include various actuators and sensors. In terms of the security of M2M mobile networks, one very significant issue is the security of Sensor Networks (SNs). Particularly, the security of transferring data from sensors to their destinations is very critical. In this paper, focusing on intrusion detection techniques, we propose an attack-defense game model to detect malicious nodes using a repeated game approach. In the proposed game model, attackers and defenders make different strategies to achieve optimal payoffs. The existences of pure nash equilibrium and mixed nash equilibrium are analyzed and proved. In the Intrusion Detection System (IDS), a game tree model is introduced to solve the error detection and missing detection problems. Simulation results present that the proposed model can reduce energy consumption by up to 50% compared with the All Monitor (AM) model, and improve the detection rate by up to 10-15% compared with the Cluster Head (CH) monitor model.

Smartphones are programmable and equipped with a set of cheap but powerful embedded sensors, such as accelerometer, digital compass, gyroscope, GPS, microphone, and camera. These sensors can collectively monitor a diverse range of human activities and the surrounding environment. Crowdsensing is a new paradigm which takes advantage of the pervasive smartphones to sense, collect, and analyze data beyond the scale of what was previously possible. With the crowdsensing system, a crowdsourcer can recruit smartphone users to provide sensing service. Existing crowdsensing applications and systems lack good incentive mechanisms that can attract more user participation. To address this issue, we design incentive mechanisms for crowdsensing. We consider two system models: the crowdsourcer-centric model where the crowdsourcer provides a reward shared by participating users, and the user-centric model where users have more control over the payment they will receive. For the crowdsourcer-centric model, we design an incentive mechanism using a Stackelberg game, where the crowdsourcer is the leader while the users are the followers. We show how to compute the unique Stackelberg Equilibrium, at which the utility of the crowdsourcer is maximized, and none of the users can improve its utility by unilaterally deviating from its current strategy. For the user-centric model, we design an auction-based incentive mechanism, which is computationally efficient, individually rational, profitable, and truthful. Through extensive simulations, we evaluate the performance and validate the theoretical properties of our incentive mechanisms.

In a mobile crowd sensing system, a smartphone undertakes many different sensing tasks that demand data from various sensors. In this paper, we consider the problem of scheduling different sensing tasks assigned to a smartphone with the objective of minimizing sensing energy consumption while ensuring Quality of SenSing (QoSS). First, we consider a simple case in which each sensing task only requests data from a single sensor. We formally define the corresponding problem as the Minimum Energy Single-sensor task Scheduling (MESS) problem and present a polynomial-time optimal algorithm to solve it. Furthermore, we address a more general case in which some sensing tasks request multiple sensors to report their measurements simultaneously. We present an Integer Linear Programming (ILP) formulation as well as an effective polynomial-time heuristic algorithm, for the corresponding Minimum Energy Multi-sensor task Scheduling (MEMS) problem. Extensive simulation results show that the proposed algorithms achieve over 79% energy savings on average compared to a widely-used baseline approach, and moreover, the proposed heuristic algorithm produces close-to-optimal solutions.

Crowdsourcing incentive mechanism design has raised numerous interests from research communities in recent years. While most research focuses on contribution-based payment allocation, a solid crowdsourcing incentive mechanism should encourage users to both devote efforts to complete the task and refer other users to join into participation. In this paper, we adopt a data structure called incentive tree which has a unique advantage in incentivizing participants for solicitation. Furthermore, we consider the crowdsourcing scenario where the contribution model is submodular and time-sensitive, which is more realistic compared to the linear summation model adopted by previous works. Under this model, we design a reward mechanism based on the incentive tree, and prove that this mechanism satisfies several economic properties such as continuing contribution incentive, continuing solicitation incentive, θ-reward proportional to contribution, early contribution incentive, and sybil-proofness. We implemented our incentive mechanism and conducted extensive performance evaluations. The evaluation results confirm our theoretical analysis.

We envision that in the near future, just as Infrastructure-as-a-Service (IaaS), radios and radio resources in a wireless network can also be provisioned as a service to Mobile Virtual Network Operators (MVNOs), which we refer to as Radio-as-a-Service (RaaS). In this paper, we present a novel auction-based model to enable fair pricing and fair resource allocation according to real-time needs of MVNOs for RaaS. Based on the proposed model, we study the auction mechanism design with the objective of maximizing social welfare. First, we present an Integer Linear Programming (ILP) based auction mechanism for obtaining optimal social welfare. To reduce time complexity, we present a polynomial-time greedy mechanism for the RaaS auction. Both methods have been formally shown to be truthful and individually rational. Extensive simulation results show that the proposed greedy auction mechanism can quickly produce close-to-optimal solutions.

Auction is an effective method of allocating scarce spectrum resources in cognitive radio networks, where the primary users are sellers and the secondary users are buyers. In order for the buyers and sellers to act honestly during the auction, truthfulness has been identified as an important property. Current research focuses on the truthfulness and spatial reusability by either assuming that a conflict graph is given under the protocol model, or assuming that the grouping result is given under the physical interference model without power control. To fill this void, we design a framework of truthful double auctions, named TSA, for spectrum sharing in cognitive radio networks. TSA finds a feasible grouping profile such that users in the same group can be assigned to the same channel while each gets a satisfactory SINR value by an appropriate transmitting power allocation. We prove that TSA guarantees all the desired economic properties: individual rationality, budget-balance, computational efficiency, and truthfulness. Extensive performance evaluation also supports our theoretic analysis.

With the prosperity of smart devices, crowdsourcing has emerged as a new computing/networking paradigm. Through the crowdsourcing platform, service requesters can buy service from service providers. An important component of crowdsourcing is its incentive mechanism. We study three models of crowdsourcing, which involve cooperation and competition among the service providers. Our simplest model generalizes the well-known user-centric model studied in a recent Mobicom paper. We design an incentive mechanism for each of the three models, and prove that these incentive mechanisms are individually rational, budget-balanced, computationally efficient, and truthful.

Crowdsourcing is an emerging paradigm where users can have their tasks completed by paying fees, or receive rewards for providing service. A critical problem that arises in current crowdsourcing mechanisms is how to ensure that users pay or receive what they deserve. Free-riding and false-reporting may make the system vulnerable to dishonest users. In this paper, we design schemes to tackle these problems, so that each individual in the system is better off being honest and each provider prefers completing the assigned task. We first design a mechanism EFF which eliminates dishonest behavior with the help from a trusted third party for arbitration. We then design another mechanism DFF which, without the help from any third party, discourages dishonest behavior. We also prove that DFF is semi-truthful, which discourages dishonest behavior such as free-riding and false-reporting when the rest of the individuals are honest, while guaranteeing transaction-wise budget-balance and computational efficiency. Performance evaluation shows that within our mechanisms, no user could have a utility gain by unilaterally being dishonest.

Mobile crowdsensing can enable numerous attractive novel sensing applications due to the prominent advantages such as wide spatiotemporal coverage, low cost, good scalability, pervasive application scenarios, etc. In mobile crowdsensing applications, incentive mechanisms are necessary to stimulate more potential smartphone users and to achieve good service quality. In this paper, we focus on exploring truthful incentive mechanisms for a novel and practical scenario where the tasks are time window dependent, and the platform has strong requirement of data integrity. We present a universal system model for this scenario based on reverse auction framework and formulate the problem as the Social Optimization User Selection (SOUS) problem. We design two incentive mechanisms, MST and MMT. In single time window case, we design an optimal algorithm based on dynamic programming to select users. Then we determine the payment for each user by VCG auction; while in multiple time window case, we show the general SOUS problem is NP-hard, and we design MMT based on greedy approach, which approximates the optimal solution within a factor of In|W| + 1, where |W| is the length of sensing time window defined by the platform. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve high computation efficiency, individual rationality and truthfulness.

Crowdsourcing is an emerging paradigm where users can pay for the services they need or receive rewards for providing services. One example in wireless networking is mobile crowdsourcing, which leverages a cloud computing platform for recruiting mobile users to collect data (such as photos, videos, mobile user activities, etc) for applications in various domains, such as environmental monitoring, social networking, healthcare, transportation, etc. However, a critical problem arises as how to ensure that users pay or receive what they deserve. Free-riding and false-reporting may make the system vulnerable to dishonest users. In this paper, we aim to design schemes to tackle these problems, so that each individual in the system is better off being honest. We first design a mechanism EFF which eliminates dishonest behavior with the help from a trusted third party for arbitration. We then design another mechanism DFF which, without the help from any third party, discourages free-riding and false-reporting. We prove that EFF eliminates the existence of free-riding and false-reporting, while guaranteeing truthfulness, individual rationality, budget-balance, and computational efficiency. We also prove that DFF is semi-truthful, which discourages dishonest behavior such as free-riding and false-reporting when the rest of the individuals are honest, while guaranteeing budget-balance and computational efficiency. Performance evaluation shows that within our mechanisms, no dishonest behavior could bring extra benefit for each individual.

Recent spectrum auction results have shown that the spectrum is usually sold at a very high unit price. Small network providers may not be able to afford it individually. Inspired by the group buying service on the Internet, group buying strategy has been introduced into the design for spectrum auctions to increase the buying power of small network providers as a whole. In this paper, we consider cognitive radio networks with multiple secondary networks, each of which consists of one secondary access point and a number of secondary users interested in accessing channels licensed to the primary user. We propose TRUBA, a truthful group buying-based auction to take advantage of the collective buying power of secondary users within each secondary network. We carefully design the budget extraction for each secondary access point within the secondary network to maximize the budget collected from the secondary users. In addition, we allow the primary user to assign its channels strategically so as to maximize its profit on each secondary network. These two features together make TRUBA significantly improve the system performance, compared to the existing group buying-based auction, in terms of the number of successful transactions (up to 105% in the evaluation results), the number of winning secondary users (up to 129%), the utility of secondary access points (up to 463%), and the utility of the primary user (up to 119%).

In a competitive environment, competing agents would maximize their ideas' influence for higher profits. For example, in an unsaturated market, when a new company participates in the market sharing competition, it would distribute free tryout or discount to several customers, let them adopt the product or service, and influence others to use this product as propagation goes. This situation can also be applied to other scenarios, such as spreading new ideas in online social networks, political elections, and so on. In this paper, we use a model called Dynamic Influence in Competitive Environments (DICE) to perform the influence propagation. We first prove that finding the optimal utility for the new agent is an NP-hard problem under DICE. Then, we provide an algorithm for these new companies, and prove that the algorithm has a (1/3 - ϵ/n)-approximation ratio to the maximum payoff value. Performance results show that our algorithm has a better performance compared to existing strategies in terms of maximizing the utility for new agents.

Auctions provide a platform for licensed spectrum users to trade their underutilized spectrum with unlicensed users. Existing spectrum auctions either do not apply to the scenarios where multiple sellers and buyers both make offers, or assume the knowledge of the users' valuation distribution for maximizing the profit of the auction. To fill this void, we design PROMISE, a framework for spectrum double auctions, which jointly considers spectrum reusability, truthfulness, and profit maximization without the distribution knowledge. We propose a novel technique, called cross extraction, to compute the bid representing a group of secondary users, who can share a common channel. We prove that PROMISE is computationally efficient, individual-rational, and truthful. In addition, PROMISE is guaranteed to achieve an approximate profit of the optimal auction.

Existing online social networks (OSNs) only allow a single user to restrict access to her/his data but cannot provide any mechanism to enforce privacy concerns over data associated with multiple users. This situation leaves privacy conflicts largely unresolved and leads to the potential disclosure of users' sensitive information. To address such an issue, a MultiParty Access Control (MPAC) model was recently proposed, including a systematic approach to identify and resolve privacy conflicts for collaborative data sharing in OSNs. In this paper, we take another step to further study the problem of analyzing the strategic behavior of rational controllers in multiparty access control, where each controller aims to maximize her/his own benefit by adjusting her/his privacy setting in collaborative data sharing in OSNs. We first formulate this problem as a multiparty control game and show the existence of unique Nash Equilibrium (NE) which is critical because at an NE, no controller has any incentive to change her/his privacy setting. We then present algorithms to compute the NE and prove that the system can converge to the NE in only a few iterations. A numerical analysis is also provided for different scenarios that illustrate the interplay of controllers in the multiparty control game. In addition, we conduct user studies of the multiparty control game to explore the gap between game theoretic approaches and real human behaviors.

A fundamental problem in survivable routing in wavelength division multiplexing (WDM) optical networks is the computation of a pair of link-disjoint (or node-disjoint) lightpaths connecting a source with a destination, subject to the wavelength continuity constraint. However, this problem is NP-hard when the underlying network topology is a general mesh network. As a result, heuristic algorithms and integer linear programming (ILP) formulations for solving this problem have been proposed. In this paper, we advocate the use of 2-edge connected (or 2-node connected) subgraphs of minimum isolated failure immune networks as the underlying topology for WDM optical networks. We present a polynomial-time algorithm for computing a pair of link-disjoint lightpaths with shortest total length in such networks. The running time of our algorithm is O(nW2), where n is the number of nodes, and W is the number of wavelengths per link. Numerical results are presented to demonstrate the effectiveness and scalability of our algorithm. Extension of our algorithm to the node-disjoint case is straightforward.

Tremendous efforts have been made to protect the location privacy of mobile users. Some of them, e.g., k-anonymity, require the participation of multiple mobile users to impede the adversary from tracing. These participating mobile users constitute an anonymity set. However, not all mobile users are seriously concerned about their location privacy. Therefore, to achieve k-anonymity, we need to provide incentives for mobile users to participate in the anonymity set. In this paper, we study the problem of incentive mechanism design for k-anonymity location privacy. We first consider the case where all mobile users have the same privacy degree requirement. We then study the case where the requirements are different. Finally, we consider a more challenging case where mobile users can cheat about not only their valuations but also their requirements. We design an auction-based incentive mechanism for each of these cases and prove that all the auctions are computational efficient, individually rational, budget-balanced, and truthful. We evaluate the performance of different auctions through extensive simulations.

Anypath routing has been proposed to improve the performance of unreliable wireless networks by exploiting the spatial diversity and broadcast nature of the wireless medium. Previous studies on anypath routing have concentrated on finding an anypath, which optimizes a single quality of service (QoS) parameter. In this paper, we study anypath routing subject to multiple constraints. We first prove that the problem is NP-hard when the number of constraints is larger than one. We then present a polynomial time K--approximation algorithm MAP, where K is the number of constraints. Our algorithm is as simple as Dijkstra's shortest path algorithm. Therefore, it is suitable for implementation in wireless routing protocols.

In this paper, we present a game-theoretic study of the problem of routing in networks with max-min fair congestion control at the link level. The problem is formulated as a noncooperative game, in which each user aims to maximize its own bandwidth by selecting its routing path. We first prove the existence of Nash equilibria. This is important, because at a Nash equilibrium (NE), no user has any incentive to change its routing strategy-leading to a stable state. In addition, we investigate how the selfish behavior of users may affect the performance of the network as a whole. We next introduce a novel concept of observed available bandwidth on each link. It allows a user to find a path with maximum bandwidth under max-min fair congestion control in polynomial time, when paths of other users are fixed. We then present a game-based algorithm to compute an NE and prove that by following the natural game course, the network converges to an NE. Extensive simulations show that the algorithm converges to an NE within 10 iterations and also achieves better fairness compared to other algorithms .

Jamming defense is an important yet challenging problem. In this paper, we study the jamming defense problem in the presence of a smart jammer, who can quickly learn the transmission power of the user and adaptively adjust its transmission power to maximize the damaging effect. We consider both the single-channel model and the multi-channel model. By modeling the problem as a Stackelberg game, we compute the optimal transmission power for the user to maximize its utility, in the presence of a smart jammer. For the single-channel model, we prove the existence and uniqueness of the Stackelberg Equilibrium (SE) by giving closed-form expressions for the SE strategies of both the user and the player. For the multi-channel model, we prove the existence of the SE. We design algorithms for computing the jammer's best response strategy and approximating the user's optimal strategy. Finally, we validate our theoretical analysis through extensive simulations.

Jamming defense is an important yet challenging problem. In this paper, we study the jamming defense problem in the presence of a smart jammer, who can quickly learn the transmission power of the user and adaptively adjust its transmission power to maximize the damaging effect. By modeling the problem as a Stackelberg game, we compute the optimal transmission power for the user to maximize its utility, in spite of the existence of the smart jammer. We prove that the smart jammer is not more damaging than a jammer without the intelligence, provided that the user plays its strategy corresponding to a Stackelberg equilibrium. This nice property is due to the user's ability to predict the jammer's behavior.

Auction theory has been applied to cooperative communications to either efficiently allocate resources or incentivize wireless devices to participate in cooperative communications. However, a common shortcoming of the existing studies is that the revenue generation is neglected. Revenue generation is the ultimate goal of commercial networks, e.g., WiMAX networks. In this paper, we study the problem of how to use auction mechanisms to allocate the relay nodes and charge the source nodes, such that the revenue of the seller, e.g., the base station, is maximized. We first propose a VCG-based auction mechanism, which can maximize the revenue while enforcing the truthfulness. To overcome the high time complexity of the VCG-based auction mechanism, we further design another truthful auction mechanism with low time complexity. Experiment results show that the suboptimal auction mechanism significantly reduces the time complexity without severely sacrificing the revenue.

Surveillance systems, such as sensor networks and surveillance camera networks, have been widely deployed to monitor events in many different scenarios. One common way to conserve resource (such as energy) usage is to have only a subset of devices activated at any give time. In this paper, we look at this classic problem from a new perspective: we do not try to cover all the event areas as usually studied, but aim to find the most valuable event areas among all the event areas (i.e., the ones leading to the most utility) to monitor, subject to resource constraints. This problem poses two major challenges. First, the utility brought by monitoring an event area is not known beforehand. Second, even if this information is known in advance, solving the problem of which event areas should be monitored to maximize the total utility, subject to resource constraints, is NP-hard. We formulate this problem as a novel programming system, called online integer linear programming, and present a polynomial time algorithm to solve this problem. For any given σ∈(0, 1), we prove a bound on the gap between the expected utility obtained by constantly using the global optimal strategy multiplied by σ and the expected utility obtained by following our algorithm.

In this paper, we study the influence of network entity load constraints on network resource allocation. We focus on the problem of allocating network resources to optimize the total utility of multiple users in a wireless network, taking into account four resource and social requirements: 1) user QoS rate constraints, 2) node max load constraints, 3) node load balance constraints, and 4) node-user load constraints. We formulate this problem as a programming system. In order to solve this programming system, we first propose an optimization framework, called α-approximation dual subgradient algorithm, which may be applicable for many networking optimization problems. Given an approximation/optimal algorithm for solving the subproblem at each iteration, the framework leads to a result that can provide the following bounds at each iteration: 1) the bounds on the Lagrangian multipliers; 2) the bound on the amount of feasibility violation of the generated primal solutions; and 3) the upper and lower bounds on the gap between the optimal solution and the generated primal solutions. Based on this framework, we then present a distributed iterative algorithm to solve the network resource allocation problem. At each iteration, we provide bounds on the amount of feasibility violation, the gap between our solution and the optimal solution, node queue lengths, user utility deficits, and node load violation ratios.

While tremendous efforts have been made on channel allocation problems in wireless networks, most of them are on cooperative networks with few exceptions [6, 8, 31, 32]. Among those works on non-cooperative networks, none of them considers the network with multiple collision domains. Instead, they all assume the single collision domain, where all transmissions interfere with each other if they are on the same channel. In this paper, we fill this void and generalize the channel allocation problem to non-cooperative multi-radio multi-channel wireless networks with multiple collision domains. We formulate the problem as a strategic game, called ChAlloc. We show that the ChAlloc game may result in an oscillation when there are no exogenous factors to influence players' strategies. To avoid this possible oscillation, we design a charging scheme to induce players to converge to a Nash Equilibrium (NE). We bound the convergence speed and prove that the system performance in an NE is at least (1 - r̅/h) of the system performance in an optimal solution, where r̅ is the maximum number of radios equipped on wireless devices and h is the number of available channels. In addition, we develop a localized algorithm for players to find an NE strategy. Finally, we evaluate our design through extensive experiments. The results validate our analysis of the possible oscillation in the ChAlloc game lacking the charging scheme, confirm the convergence of the ChAlloc game with the charging scheme, and verify our proof on the system performance compared to the upper bounds returned by an LP-based algorithm.

Mobile phone sensing is a new paradigm which takes advantage of the pervasive smartphones to collect and analyze data beyond the scale of what was previously possible. In a mobile phone sensing system, the platform recruits smartphone users to provide sensing service. Existing mobile phone sensing applications and systems lack good incentive mechanisms that can attract more user participation. To address this issue, we design incentive mechanisms for mobile phone sensing. We consider two system models: the platform-centric model where the platform provides a reward shared by participating users, and the user-centric model where users have more control over the payment they will receive. For the platform-centric model, we design an incentive mechanism using a Stackelberg game, where the platform is the leader while the users are the followers. We show how to compute the unique Stackelberg Equilibrium, at which the utility of the platform is maximized, and none of the users can improve its utility by unilaterally deviating from its current strategy. For the user-centric model, we design an auction-based incentive mechanism, which is computationally efficient, individually rational, profitable, and truthful. Through extensive simulations, we evaluate the performance and validate the theoretical properties of our incentive mechanisms.

Exploiting the nature of broadcast and the relaying capability of wireless devices, cooperative communication is becoming a promising technology to increase the channel capacity in wireless networks. In cooperative communication, the scheme for assigning relay nodes to users plays a critical role in the resulting channel capacity. A significant challenge is how to make the scheme robust to selfish and cheating behavior of users while guaranteeing the social optimal system capacity. In this paper, we design an integrated optimal marriage scheme called HERA for cooperative networks. To avoid system performance degradation due to the selfish relay selections by the source nodes, we propose a payment mechanism for charging the source nodes to induce them to converge to the optimal assignment. To prevent relay nodes from manipulating the marriage by reporting transmission power untruthfully, we propose a payment mechanism to pay them for providing relaying service. We also show that HERA is budget-balanced, meaning that the payment collected from source nodes is no smaller than the payment paid to relay nodes.

Delay constrained path selection is concerned with finding a source-to-destination path so that the delay of the path is within a given delay bound. When the network is modeled by a directed graph where the delay of a link is a random variable with a known mean and a known variance, the problem becomes that of computing a most probable delay constrained path. In this paper, we present a comprehensive theoretical study of this problem. First, we prove that the problem is NP-hard. Next, for the case where there exists a source-to-destination path with a delay mean no more than the given delay bound, we present a fully polynomial time approximation scheme. In other words, for any given constant ε such that 0 <; ε <; 1, our algorithm computes a path whose probability of satisfying the delay constraint is at least (1-ε) times the probability that the optimal path satisfies the delay constraint, with a time complexity bounded by a polynomial in the number of network nodes and 1/ε. Finally, for the case where any source-to-destination path has a delay mean larger than the given delay bound, we present a simple approximation algorithm with an approximation ratio bounded by the square root of the hop count of the optimal path.

In wireless sensor networks, relay node placement has been proposed to improve energy efficiency. In this paper, we study two-tiered constrained relay node placement problems, where the relay nodes can be placed only at some prespecified candidate locations. To meet the connectivity requirement, we study the connected single-cover problem where each sensor node is covered by a base station or a relay node (to which the sensor node can transmit data), and the relay nodes form a connected network with the base stations. To meet the survivability requirement, we study the 2-connected double-cover problem where each sensor node is covered by two base stations or relay nodes, and the relay nodes form a 2-connected network with the base stations. We study these problems under the assumption that R \ge 2r > 0, where R and r are the communication ranges of the relay nodes and the sensor nodes, respectively. We investigate the corresponding computational complexities, and propose novel polynomial time approximation algorithms for these problems. Specifically, for the connected single-cover problem, our algorithms have {\cal O}(1)-approximation ratios. For the 2-connected double-cover problem, our algorithms have {\cal O}(1)-approximation ratios for practical settings and {\cal O}(\ln n)-approximation ratios for arbitrary settings. Experimental results show that the number of relay nodes used by our algorithms is no more than twice of that used in an optimal solution.

The smart grid, perceived as the next generation power grid, uses two-way flow of electricity and information to create a widely distributed automated energy delivery network. By grouping distributed renewable energy generations and loads, a microgrid, which is seen as one of the cornerstones of the future smart grids, can disconnect from the macrogrid and function autonomously. This intentional islanding of generations and loads has the potential to provide a higher local reliability than that provided by the power system as a whole. One of the fundamental issues for a user in an islanded microgrid is how to find the one among the distributed renewable energy resources (DRERs) in a microgrid, which can supply the power most efficiently, effectively and reliably, as its power supply source. This problem is difficult since the power pattern of renewable resources, such as wind and solar, is variable and generally speaking is not easy to accurately predict. In order to solve this problem, we first propose a distributed DRER discovery approach to discover all the available DRERs within a microgrid. Furthermore, based on the online machine learning theory, we propose two distributed algorithms according to the information the user can obtain, in order to compute a good DRER access strategy, with no assumption on what distribution the power patterns of the DRERs follow. We prove that when the time horizon is sufficiently large, on average the upper bound on the gap between the expected profit obtained at each time slot by using the global optimal strategy and that by using our algorithms is arbitrarily small.

In the IEEE 802.16j standard, the relay station has been introduced to increase the coverage and the throughput of WiMAX networks. The placement of the relay station plays a critical role in the system performance and therefore draws tremendous attention from the research community. In this paper, we study the relay station placement problem in the WiMAX network, with the cooperative communication as the relaying strategy. In particular, given a base station and a set of subscriber stations, we determine the location of a relay station, and the set of subscriber stations using the relay station. The objective is to minimize the maximum transmission power among all the subscriber stations while satisfying the data rate requirements of the subscriber stations. We develop a near-optimal algorithm to solve this problem and prove that the maximum transmission power computed by our algorithm is at most Popt+ ε, where Poptis the maximum transmission power in the optimal solution and ε >; 0 is an arbitrary constant. The experiments show that we can dramatically reduce the maximum transmission power by deploying the relay station according to our algorithm.

Anypath routing, a new routing paradigm, has been proposed to improve the performance of wireless networks by exploiting the spatial diversity and broadcast nature of the wireless medium. In this paper, we study the problem of finding an anypath subject to multiple (K) constraints, which has been proved to be NP-hard. We present a polynomial distributed K-approximation routing algorithm. Our algorithm is as simple as Bellman-Ford's shortest path algorithm. Extensive experiments show that our algorithm is very efficient and its result is as good as that obtained by the best centralized algorithm which requires the global information.

Cooperative communication has been proposed to increase the capacity of wireless networks. By exploiting a relay node, it achieves spatial diversity to cope with fading channel without requiring wireless nodes to be equipped with multiple antennas. However, the selection of relay nodes has a significant impact on the final capacity. In this paper, we study the problem of relay assignment in cooperative networks, where multiple source-destination transmission pairs share the same set of relay nodes. Specifically, we propose a system model where a relay node can be shared by multiple source-destination pairs and present a corresponding formulation for the capacity calculation. Our objective is to find a relay assignment to maximize the total capacity of the network. As the main contribution, we develop an optimal relay assignment algorithm to solve this problem in polynomial time. We also show that our algorithm has several attractive properties.

Opportunistic routing is proposed to improve the performance of wireless networks by exploiting the broadcast nature and spatial diversity of the wireless medium. In this paper, we study the problems of how to choose opportunistic route for each user to optimize the total utility or profit of multiple simultaneous users in a wireless mesh network (WMN) subject to node constraints. We formulate these two problems as two convex programming systems. By combining primal-dual and subgradient methods, we present a distributed iterative algorithm Consort (node-Constrained Opportunistic Routing). In each iteration, Consort updates Lagrange multipliers in a distributed manner according to the user and node behaviors obtained in the previous iteration, and then each user and each node individually adjusts its own behavior based on the updated Lagrange multipliers. We prove the convergence of this iterative algorithm, and provide bounds on the amount of feasibility violation and the gap between our solution and the optimal solution in each iteration.

The notion of probabilistic network has been used to characterize the unpredictable environment in wireless communication networks or other unstable networks. In this paper, we are interested in the problem of placing servers in probabilistic networks subject to budget constraint, so as to maximize the expected number of servable clients that can successfully connect to a server. We study this problem in both the single-hop model and the multi-hop model. We discuss the computational complexity of this problem and show that it is NP-hard under both models.We then develop efficient approximation algorithms, which produce solutions provably close to optimal. If the costs of candidate locations are uniform, when extra budget is available in the future, the progressive feature of our algorithms allows for placing additional servers instead of relocating all the servers, while retaining the guaranteed performance. Results of extensive experiments on different topologies confirm the performance of our algorithms compared to the optimal algorithm and other heuristic algorithms.

Recently Choi et al. designed the first practical wireless full-duplex system, which challenges the basic assumption in wireless communications that a radio cannot transmit and receive on the same frequency at the same time. Along this line, in this paper we study the cross-layer optimization for routing in full-duplex wireless networks, comprehensively considering various resource competitions and constraints. We first propose a collision-free full-duplex broadcast MAC and prove its necessary and sufficient conditions. We then focus on 1) the problem of how to choose routes to maximize the total profit of multiple users subject to node constraints, and 2) the problem of how to choose routes to minimize the network power consumption subject to the minimum user rate demands and node constraints. We formulate these two problems as convex programming systems. By combining Lagrangian decomposition and subgradient methods, we present distributed iterative algorithms to solve these two problems, which compute the optimized user information flow (i.e. user behavior) on the network layer and the optimized node broadcast rate (i.e. node behavior) on the MAC layer. Our algorithms allow each user and each node to adjust its own behavior individually in each iteration. We prove the convergence, and provide bounds on the amount of constraint violation, and the gap between the optimal solution and our solution in each iteration. Our work comprehensively considers various resource competitions and constraints, and provides a theoretical foundation for the future study on full-duplex wireless networks. To the best of our knowledge, this is the first work to study cross-layer optimization for full-duplex wireless networks.

Anypath routing is proposed to improve the performance of wireless networks by exploiting the spatial diversity and broadcast nature of the wireless medium. In this paper, we study anypath routing in wireless networks with directional antennas, and propose DART (Directional Anypath RouTing), a crosslayer design of MAC and routing layers. For the routing layer, we propose two shortest directional anypath routing algorithms based on two antenna models. Our routing algorithms are simple and fast, thus are suitable for implementation in practical protocols. For the MAC layer, we present a directional anycast MAC, which is an enhancement to the IEEE 802.11 MAC, making DART suitable for integration into current systems. Simulation results show that DART can significantly reduce the packet transmission delay.

On one hand, cooperative communication has been gaining more and more popularity since it has great potential to increase the capacity of wireless networks. On the other hand, the applications of cooperative communication technology are rarely seen in reality, even in some scenarios where the demands for bandwidth-hungry applications have pushed the system designers to develop innovative network solutions. A main obstacle lying between the potential capability of channel capacity improvement and the wide adoption of cooperative communication is the lack of incentives for the participating wireless nodes to serve as relay nodes. Hence, in this paper, we design TASC, an auction scheme for the cooperative communications, where wireless node can trade relay services. TASC makes an important contribution of maintaining truthfulness while fulfilling other design objectives. We show analytically that TASC is truthful and has polynomial time complexity. Extensive experiments show that TASC can achieve multiple economic properties without significant performance degradation compared with pure relay assignment algorithms.

In this paper, we study the problem of maximizing the number of concurrent requests and the problem of minimizing the number of time-slots needed to schedule all requests in wireless networks under the physical interference model. It has been proved that both problems are NP-complete. Thus either approximation algorithms with guaranteed approximation factors or effective heuristics with practically good performances are desirable. We focus on the latter and present simple and effective heuristic algorithms for these two problems. Extensive experiments show that our algorithm for the first problem outperforms the best approximation algorithm by 62%-72% on average, and our two algorithms for the second problem give the best results among existing algorithms.

The recently emerging WiMAX (IEEE 802.16) is a promising telecommunication technology to provide low-cost, high-speed and long-range wireless communications. To meet the growing demand for throughput, Relay Station is introduced by IEEE 802.16j to relay traffic for Subscriber Stations. By incorporating Cooperative Communications scheme in WiMAX, we can further improve the network capacity. In this paper, we study the Relay Station placement problem, which seeks to deploy a minimum number of Relay Stations to satisfy all data rate requests from Subscriber Stations via Cooperative Communications. We analyze the computational complexity of the problem and prove it to be NP- Complete. Then we present efficient algorithms with guaranteed approximation ratios. Extensive experiments show that the number of Relay Stations returned by our algorithms is close to those returned by optimal solution.

In this paper, we study the problem of routing in networks with max-min fair congestion control at the link level. The goal of each user is to maximize its own bandwidth by selecting its path. The problem is formulated as a non-cooperative game. We first prove the existence of Nash Equilibria. This is important, because at a Nash Equilibrium (NE), no user has the incentive to change its routing strategy. In addition, we investigate how the selfish behavior of the users may affect the performance of the network as a whole. We next introduce a novel concept of observed available bandwidth on each link. It allows a user to find a path with maximum bandwidth under max-min fair congestion control in polynomial time. We then present a game based algorithm to compute an NE and prove that by following the natural game course the network converges to an NE. Extensive experiments show that the network can converge to an NE in less than 10 iterations and also significantly improves the fairness compared with other algorithms. Our results have the implication for the future routing protocol design.

Anypath routing has been proposed to improve the performance of unreliable wireless networks by exploiting the spatial diversity and broadcast nature of the wireless medium. In this paper, we focus on anypath routing subject to K constraints, and present a polynomial time K-approximation algorithm. When K = 1, our algorithm is the optimal polynomial time algorithm for the corresponding problem. When K ≥ 2, the corresponding problem is NP-hard. We are the first to present an O(1)-approximation algorithm. Furthermore, our algorithm is as simple as Dijkstra's shortest path algorithm, and is therefore suitable for implementation in actual wireless routing protocols.

In a wireless sensor network, short range multihop transmissions are preferred to prolong the network lifetime due to super-linear nature of energy consumption with communication distance. It has been proposed to deploy some relay nodes such that the sensors can transmit the sensed data to a nearby relay node, which in turn delivers the data to the base stations. In general, the relay node placement problems aim to meet certain connectivity and/or survivability requirements of the network by deploying a minimum number of relay nodes. In this paper, we study two-tiered constrained relay node placement problems, where the relay nodes can only be placed at some pre-specified candidate locations. To meet the connectivity requirement, we study the connected single-cover problem where each sensor node is covered by a relay node (to whom the sensor node can transmit data), and the relay nodes form a connected network with the base stations. To meet the survivability requirement, we study the 2-connected double-cover problem where each sensor node is covered by at least two relay nodes, and the relay nodes form a 2-connected network with the base stations. We focus on the computational complexities of the problems, and propose novel polynomial time approximation algorithms for these problems. For the connected single-cover problem, our algorithms have O(1) approximation ratios. For the 2-connected double-cover problem, our algorithms have O(1) approximation ratios for practical settings and O(lnn) approximation ratios for arbitrary settings. Experimental results show that the number of relay nodes used by our algorithms is no more than twice of the number of relay nodes used in an optimal solution.

In wireless networks, mutual interference prevents wireless devices from correctly receiving packages from others and becomes one of the challenges in the design of protocols for wireless networks. Spatial-reuse time division multiple access (STDMA) has been used to cope with this problem. In this scheme, links are assigned to several time slots and in each slot all the links can transmit simultaneously. In this paper, we propose a greedy link scheduling algorithm to find a short schedule for a problem instance in the physical interference model. Our scheduling algorithm is inspired by the k-MAX-CUT algorithm. Experimental results show that our greedy algorithm can give a better schedule compared with the greedy algorithm, with an improvement about 20%-30% when the density of links is high.

Fault tolerance techniques have been widely used in wireless sensor networks. Base station placement to maximize the network lifetime has also been well studied. However, limited research has been done on the joint base station placement and fault-tolerant routing problem. To fill this void, we study this problem and present a fully polynomial time approximation scheme in this paper. Our scheme can compute a (1 - ¿)approximation with a running time bounded by a polynomial in 1/¿ and the input size of the instance. Despite our solution is presented for the model where the base station can be placed anywhere, however it can be easily extended to cases where forbidden areas are present or candidate locations for the base station are given. To the best of our knowledge, this paper is the first theoretical result on this problem.

In this paper, we study the problem of multi-path routing with bandwidth and delay constraints, which arises in applications for video delivery over bandwidth limited networks. Assume that each link in the network has a bandwidth and a delay. For a given source-destination pair and a bandwidth requirement, we want to find a set of source to destination paths such that the delay of the longest path is minimized while the aggregated bandwidth of the set of paths meets the bandwidth requirement. This problem is NP-hard, and the state of the art is a maximum flow based heuristic. We first construct a class of examples showing that the maximum flow based heuristic could have very bad performance. We then present a fully polynomial time approximation scheme that can compute a (1 + epsiv) -approximation with running time bounded by a polynomial in 1/epsiv and the input size of the instance. Given the NP-hardness of the problem, our approximation scheme is the best possible. We also present numerical results confirming the advantage of our scheme over the current state of the art.