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.

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.

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.

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.

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.

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.

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.

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.