PaperlayerView exact revision on arXiv

Source-linked AI summary

Providing Long-Term Participation Incentive in Participatory Sensing

Lin Gao, Fen Hou, Jianwei Huang

arXiv:1501.02480v2cs.GTcs.NI

TL;DR

Participatory sensing needs sustained user participation, but sensing costs and indirect participation costs can cause users to drop out. The paper models long-term participation in time-dependent, location-aware sensor selection and proposes Lyapunov-based online policies, including a truthful VCG auction under information asymmetry. The policies converge asymptotically to the optimal offline benchmark and outperform existing policies in user participation and social welfare.

  • Problem

    Users may incur direct and indirect costs in participatory sensing, while rarely selected users may drop out, threatening sufficient data collection and service quality.

  • Method

    The paper formulates sensor selection across future-information and current-information scenarios and proposes Lyapunov-based online policies, including a VCG auction under information asymmetry.

  • Results

    The policies converge asymptotically to the optimal offline benchmark and outperform existing policies in user participation and social welfare.

  • Takeaways & Limitations

    Long-term participation can be incorporated into sensor selection while retaining asymptotically optimal performance without future information, including under information asymmetry.

Abstract

from arXiv · show

Providing an adequate long-term participation incentive is important for a participatory sensing system to maintain enough number of active users (sensors), so as to collect a sufficient number of data samples and support a desired level of service quality. In this work, we consider the sensor selection problem in a general time-dependent and location-aware participatory sensing system, taking the long-term user participation incentive into explicit consideration. We study the problem systematically under different information scenarios, regarding both future information and current information (realization). In particular, we propose a Lyapunov-based VCG auction policy for the on-line sensor selection, which converges asymptotically to the optimal off-line benchmark performance, even with no future information and under (current) information asymmetry. Extensive numerical results show that our proposed policy outperforms the state-of-art policies in the literature, in terms of both user participation (e.g., reducing the user dropping probability by 25% to 90%) and social performance (e.g., increasing the social welfare by 15% to 80%).

I. INTRODUCTION

The paper formulates sensor selection for time-dependent, location-aware participatory sensing while explicitly modeling users’ long-term participation incentives. It develops policies across future-information and current-information scenarios, including asymptotically optimal online policies and strong empirical gains in participation and social welfare.

  • Background and Motivations: Users may incur indirect costs even when not sensing, so short-term compensation may not sustain participation or service quality.Rare selection can reduce users’ interest and lead them to drop out, limiting collected data.
  • Solutions and Contributions: The model jointly captures long-term participation incentive, time-dependent and location-aware sensing, and partially conflicting sensing activities.The paper describes this combination as a first systematic treatment of these features.
  • Solutions and Contributions: The paper studies complete, stochastic, and absent future information together with symmetric and asymmetric current information.It formulates offline benchmarks for complete or stochastic future information and online problems when future information is unavailable.
  • Solutions and Contributions: Lyapunov-based online policies converge asymptotically to the optimal offline benchmark, including under no future information and information asymmetry.Policy 2 uses a VCG auction under asymmetric information and matches Policy 1’s asymptotically optimal performance.
  • Solutions and Contributions: Compared with RADP-VPC, the policies reduce user dropping probability by 25% ∼50% and increase social welfare by 15% ∼40%.Compared with Greedy/Random, they reduce dropping by 70% ∼90% and increase social welfare by 65% ∼80%.

II. SYSTEM MODEL

The system models mobile users sensing changing regions over time, with selection determined by location, mobility, sensing value, and cost. It treats long-term participation as a constraint based on users’ allocation probabilities and dropping thresholds.

  • System Model: The service provider requests data in time slots and selects users according to factors including user locations and data values.Each user’s binary selection variables form per-slot and all-slot allocation vectors.
  • Mobile User Modeling: Each user’s sensing region varies across time as location and mobility change, and is represented by the grids within sensing range.A user outside the desirable sensing area has zero sensing coverage for that slot.
  • Mobile User Modeling: Selected users incur user- and time-dependent sensing costs from collecting, processing, and transmitting data.The model motivates short-term monetary or nonmonetary compensation for selected sensors.
  • Mobile User Modeling: Long-term participation reflects indirect costs incurred even when users are not selected for sensing.Examples include reporting location or mobility information and running sensing applications.
  • Mobile User Modeling: A user may drop out when the time-average probability of being selected falls below that user’s dropping threshold.Allocation probability is used as a representative indicator of long-term return on investment.

B. Service Provider Modeling

The service provider selects users to maximize sensing value while minimizing sensing cost, accounting for overlapping sensing regions and long-term participation constraints. Social welfare is defined as sensing value minus sensing cost.

  • Service Provider Modeling: The non-commercial service provider maximizes total sensing value minus total sensing cost subject to user participation constraints.The objective applies over the entire time period.
  • Service Provider Modeling: Total sensing cost is the sum of the sensing costs of selected users in each time slot.
  • Service Provider Modeling: Overlapping sensing regions prevent total sensing value from equaling the aggregate value of all selected users.Data collected simultaneously by multiple users generates value only once for the same grid.
  • Service Provider Modeling: When selected users’ sensing regions do not overlap, total sensing value equals the sum of their individual sensing values.
  • Service Provider Modeling: Social welfare in each slot is defined as total sensing value minus total sensing cost.The paper also defines overall social welfare across all time slots.

C. Information Scenario

The paper distinguishes information scenarios by available future and current network information, using off-line optimization with complete or stochastic future information as benchmarks. With stochastic information, expected social welfare is optimized, and for sufficiently large sensing periods its benchmark approaches the complete-information benchmark.

  • Information scenarios: Future information is categorized as complete, stochastic, or unavailable, while current information is categorized as symmetric or asymmetric.The distinction depends on whether and how much the service provider knows about future network information and whether it observes users’ private current information.
  • Complete future information: With complete future information, the service provider jointly determines all time-slot sensor selections to maximize overall social welfare.The resulting off-line allocation explicitly specifies each user’s selection in every time slot and is formulated as binary integer programming.
  • Stochastic future information: With stochastic information only, the problem targets expected social welfare because explicit advance allocation is impossible without complete future information.The expected formulation uses allocation decisions indexed by each possible information realization and enforces binary selection and participation constraints.
  • Stochastic future information: The stochastic-information off-line formulation is an infinite-variable, non-convex, NP-hard integer program, although linear programming relaxation and classic methods can solve its relaxation.The continuous information realization θ creates infinitely many decision variables.
  • Benchmark relationship: As the total sensing period T becomes sufficiently large, the social welfare loss from lacking complete network information becomes negligible.Thus, the complete-information and stochastic-information optima serve as the same benchmark for later on-line policies.

IV. ON-LINE SENSOR SELECTION POLICY

The no-future-information policy uses virtual queues and Lyapunov drift-plus-penalty optimization to enforce long-term participation while optimizing expected social welfare. Its problem-specific queue construction and upper bound support queue stability and controllable asymptotic performance.

  • Policy setting: The on-line policy relies only on current network information and past selection history, without future information, and asymptotically converges to the future-information benchmark.This section assumes symmetric current information; asymmetric information is handled later.
  • Queue definition and dynamics: A virtual queue for each user represents additional sensor-selection slots needed to satisfy that user’s long-term participation constraint.Virtual requests arrive at rate Dn, and selecting the user creates queue departures through the allocation process.
  • Queue stability: Queue stability is equivalent to satisfying the user participation constraint because the arrival rate must not exceed the average departure rate.Ensuring rate stability of every associated virtual queue therefore guarantees participation constraints.
  • Joint optimization: The allocation rule minimizes a drift-plus-penalty expression combining Lyapunov drift with negative social welfare.The control parameter φ determines the tradeoff between objective optimality and queue backlog; a problem-specific upper bound is minimized instead of the quadratic expression directly.
  • Contributions: The paper’s contributions include explicitly linking virtual-queue stability to participation and deriving a problem-specific upper bound for drift-plus-penalty.The authors identify these elements as distinct from the standard Lyapunov framework.

B. On-line Allocation Policy

Policy 1 selects sensors online using current network information and virtual-queue backlogs, then updates those backlogs after each allocation. Lyapunov analysis shows asymptotic convergence to the stochastic-information welfare benchmark with a controllable error bound.

  • Policy design: Policy 1 minimizes the drift-plus-penalty upper bound in each time slot through an allocation rule followed by a queue-updating rule.Allocation uses current network information θ[t] and current queue backlogs qt; updates use the resulting allocation x†[t].
  • Operation: Policy 1 is initialized with queue state q0 and operates over successive time slots.Each slot applies the allocation procedure and updates the virtual queues.
  • Optimality: The policy’s social welfare converges asymptotically to the maximum stochastic-information benchmark with approximation error bound O(1/φ).The parameter φ controls the approximation-error tradeoff.
  • Participation tracking: The time-attenuated queue backlog approximates the gap between required allocation probability Dn and actual allocation probability through slot t.Because the backlog is bounded, this gap approaches zero as t →∞.

V. AUCTION-BASED ON-LINE SENSOR SELECTION POLICY

The auction-based policy addresses asymmetric current information, where users’ realized sensing costs are private and unavailable to the service provider. It therefore replaces direct use of those costs with bids in the allocation process.

  • Information asymmetry: Under asymmetric current information, each user’s realized sensing cost is private and cannot be observed by the service provider.This prevents direct implementation of the allocation rule used under information symmetry.
  • Auction policy: Policy 2 is an auction-based online sensor-selection policy for the information-asymmetry setting.The policy is initialized with µ0 and proceeds slot by slot.
  • Bids: The auction uses each user’s bid as the input representing that user’s private sensing cost.The allocation rule is therefore based on reported bids rather than an observable sensing-cost realization.

A. Auction Mechanism Design

Policy 2 combines a reverse VCG auction with regulation-factor updates to incentivize participation while selecting sensors. It is truthful for myopic users and achieves the same asymptotically optimal social welfare as Policy 1, but not for non-myopic users.

  • Auction mechanism: The reverse VCG auction treats the service provider as buyer and users as sellers, addressing credible cost disclosure in each time slot.The mechanism includes allocation and payment rules, plus regulation-factor updates enforcing user participation constraints.
  • Auction mechanism: Allocation maximizes regulated social welfare using sensing costs adjusted by each user’s bid and regulation factor.The allocation vector records the selected users in each time slot.
  • Auction mechanism: Selected users receive a payment combining standard VCG terms with compensation for user cost regulation; unselected users receive zero.The payment rule distinguishes selection outcomes and includes a final regulation-compensation term.
  • Auction mechanism: The regulation-factor updating rule matches Policy 1, so truthful users obtain the same allocation and performance.The updating rule uses the regulation factor associated with each user and slot.
  • Truthfulness and Optimality: Policy 2 is truthful and achieves the same asymptotically optimal social welfare as Policy 1.Truthfulness is established in Theorem 2, while Theorem 3 derives optimality from truthfulness and identical allocation and updating rules.
  • Truthfulness and Optimality: Truthfulness holds only for myopic users; non-myopic users may misreport costs to increase future payments through larger regulation factors.The paper leaves the non-myopic-user model for future work.

VI. SIMULATIONS

The simulations use a 10km×10km virtual city divided into 2500 grids, with users moving under a random-walk model and sensing regions represented by variable-radius disks. Outcomes are measured over 10,000 time slots.

  • Simulation setup: The simulated city spans 10km×10km and contains 2500 square grids, each measuring 200m × 200m.The application is evaluated in a middle-scale virtual city.
  • Simulation setup: Users move randomly between grids, while each sensing region is modeled as a disk with radius randomly selected from 400m to 800m.Movement follows a random-walk model, with each user jumping to another grid according to a probability distribution.
  • Simulation setup: The simulations run for 10,000 time slots to obtain stable outcomes under the evaluated policies.The sensing-region model and simulation duration are specified as part of the experimental setup.

A. Simulation Scenarios

The simulations compare sensing environments with different spatial data-value distributions: a uniform no-hotspot setting and a one-hotspot setting with higher values near the hotspot center.

  • Simulation Scenarios: Scenario (a) has no hotspot, so all grids have similar importance and data values follow an i.i.d. distribution.This scenario represents spatially uniform sensing value.
  • Simulation Scenarios: Scenario (b) has one hotspot, with central grids assigned larger data values than grids farther away.Scenarios with multiple hotspots are described as intermediate cases between these two settings.

B. Performance Comparisons

The proposed Lyapunov-based policy retains more users and achieves social welfare close to the optimal benchmark across both scenarios. It outperforms RADP-VPC, random, and greedy selection in participation and welfare, while incentive costs reflect scenario-dependent dropping probabilities.

  • Dropping Probability: More than 70% of users drop under greedy or random selection in scenario (a), versus more than 90% in scenario (b); the proposed policy retains all users.RADP-VPC with α = 1 loses around 25% in scenario (a) and more than 50% in scenario (b).
  • Overall Comparison: The incentive cost is approximately 6% in scenario (a) and 8% in scenario (b), with the higher cost attributed to higher dropping probability.Scenario (b) has a higher benchmark welfare because the same sensing value can potentially be collected by fewer users.
  • Social Welfare: The Lyapunov-based policy converges asymptotically to the optimal benchmark, with approximation errors of 1%–3% in scenario (a) and 1.5%–4.5% in scenario (b).The error bound is controllable through φ.
  • Social Welfare: 15%–50% welfare gaps separate RADP-VPC from the proposed policy in scenario (a), increasing to 40%–75% in scenario (b).RADP-VPC performs worse in scenario (b) because of its higher dropping probability.
  • Social Welfare: Random and greedy policies have welfare gaps larger than 60% in scenario (a) and 85% in scenario (b) relative to the proposed policy.Neither policy considers long-term participation incentive, and users therefore drop quickly.

C. Impact of Participatory Constraint

The participatory constraint changes both the attainable social welfare and how welfare responds to the number of users and dropping thresholds. Under stringent constraints, incentive costs can make additional users reduce welfare, while the proposed policy converges asymptotically to the maximum-welfare benchmark.

  • The proposed policy converges asymptotically to the maximum social welfare benchmark.
  • Without a participatory constraint, allocation probability decreases as sensing cost and the number of participating users increase.Users are selected each slot according to realized costs, and users never drop.
  • When Dn ≤0.35, maximum social welfare increases with the number of users, with faster growth at smaller dropping thresholds.
  • When Dn ≥0.4, maximum social welfare first increases and then decreases as the number of users grows.
  • A larger dropping threshold lowers social welfare because retaining users requires more incentive cost, with greater degradation for more users.
Loading 1501.02480v2…