Abstract
Networking on white spaces (i.e., locally unused spectrum) relies on active monitoring of spectrum usage. Spectrum databases based on empirical radio propagation models are widely adopted but shown to be error-prone, since they do not account for built environments like trees and man-made buildings. As an economically viable option, crowd-sensed radio mapping acquires more accurate local spectrum data from mobile users and constructs radio maps using spatial models such as Kriging and Gaussian Process. Success of such crowd-sensing systems presumes some incentive mechanisms to attract user participation. In this work, we consider the scenario where the platform who constructs radio environment maps makes one-time offers to selected users, and collects data from those who accept the offers. We design pricing mechanisms based on expected utility (EU) maximization, where EU captures the tradeoff between radio mapping performance (location and data quality), crowd-sensing cost and uncertainty in offer outcomes (i.e., possible expiration and rejection). Specifically, we consider sequential offering, where one best price offer is sent to the best user in each round, and batched offering, where a batch of multiple offers are made in each round. For the later, we show that EU is submodular in the discrete domain, and propose a mechanism that first fixes the pricing rule and selects users based on Unconstrained Submodular Maximization (USM); it then compares different pricing rules to find the best batch of offers in each round. We show that USM-based user selection has provable performance guarantee. Proposed mechanisms are evaluated and compared against utility-maximization-based baseline mechanisms.
Introduction
Efficient management of wireless spectrum, particularly for "White Spaces" (locally unused frequencies), necessitates accurate Radio Environment Maps (REMs). Traditional maps utilizing static propagation models often fail to account for local environmental obstacles like buildings or vegetation. Crowd-sensing offers a dynamic alternative by leveraging mobile users to measure signal strength (RSSI) and transmit it to a central platform.
However, implementing such a system introduces significant challenges. Users incur costs related to battery consumption, CPU usage, and opportunity costs. Furthermore, the platform faces uncertainty regarding user acceptance of payment offers and the spatial correlation of the collected data. This paper addresses these challenges by modeling the platform's objective as an Expected Utility (EU) maximization problem.
Methodology
The proposed pricing mechanisms balance the value of information against payment costs and the probability of offer rejection or expiration.
Spatial Modeling and Information Value
The system employs Gaussian Processes (GP) to interpolate signal strengths across the target area. The value of a specific user's data is quantified through Mutual Information (MI), which measures the reduction in uncertainty about the rest of the map provided by that measurement. This spatial correlation is critical, as the marginal value of data decreases when measurements are taken in close proximity.
Pricing and Selection Strategies
Two primary approaches are introduced:
- Sequential Offering: The platform sends an optimized offer to the single highest-value user and waits for a response. While this maximizes utility, it introduces significant operational delays.
- Batched Offering: Multiple offers are sent simultaneously to a group of users.
A key theoretical contribution of this work is the proof that the Expected Utility function is submodular, exhibiting diminishing returns. This property allows the application of Unconstrained Submodular Maximization (USM) algorithms, which provide a provable 1/3-approximation guarantee with linear-time complexity.
Experimental Evaluation
The mechanisms were evaluated using simulated topologies consisting of 60 users randomly placed in a 6km x 6km area via a spatial Poisson process. Signal correlation was modeled using an exponential kernel with parameters derived from empirical studies. User costs were represented using Uniform and Truncated Normal distributions to account for varying levels of uncertainty.
Key Results
- Utility Gains: The proposed single-batch mechanism (SB-EU) outperformed baseline utility-maximization models by 8.5% to 40.5%.
- Operational Efficiency: The multi-batch approach achieved performance comparable to sequential offering but required only 2.5 rounds on average, significantly reducing latency.
- Robustness: The authors proved that performance degradation resulting from Monte-Carlo estimation of EU is bounded and grows only linearly with the number of users.
Conclusion
This research provides a robust framework for incentivizing participation in radio mapping through mathematically grounded pricing strategies. While the current model assumes relatively stationary users, future work will address high-mobility scenarios and mechanisms for ensuring data integrity against malicious reporting.
Summary updated