Maximizing Coverage Quality with Budget Constrained in Mobile Crowd-Sensing Network for Environmental Monitoring Applications

Jiaoyan Chen, Jingsen YangSensors 2019 · DOI

TL;DR

This paper tackles the challenge of maximizing environmental monitoring coverage in mobile crowd-sensing networks under a strict budget. They propose a greedy algorithm that efficiently selects participants based on their "coverage per reward" to achieve the best possible data collection within financial constraints, outperforming existing methods.

What Problem Does This Paper Address?

Mobile crowd-sensing networks (MCSNs) leverage the sensing capabilities of everyday smart devices (like smartphones) carried by people to gather data about their environment. This is incredibly useful for applications like monitoring air quality, noise levels, or traffic conditions over large areas. However, a key challenge arises when trying to get comprehensive data from a specific "critical region" (e.g., a city) with a limited budget. Participants aren't free; they incur costs (time, effort, data usage) and expect rewards for their participation. The problem is how to select the right participants to cover the most important areas of the region without exceeding the allocated budget. Simply selecting all available participants isn't feasible due to cost, and selecting randomly might miss crucial areas or waste money on redundant coverage.

Methods

The authors introduce a novel approach to address the "Maximizing Coverage with Limited Budget" (MCLB) problem. Their method involves two main steps:

  1. Region Partitioning and Sampling Point Selection: They first divide the large critical region into smaller, manageable sub-regions. Within each sub-region, they select a single "sampling point" (typically the centroid of a smaller rectangle) whose data is representative of the entire sub-region. This simplifies the problem from covering a continuous area to covering a discrete set of points.
  2. Greedy Participant Selection: Once sampling points are defined, the core of their solution is a greedy algorithm. This algorithm iteratively selects participants based on their "coverage per reward" ratio. This metric quantifies how much coverage a participant provides for each unit of reward they demand. The algorithm prioritizes participants who offer the most coverage for the least cost, ensuring efficient use of the budget. It continues selecting participants until the budget is exhausted, all sampling points are covered, or no more suitable participants can be found.

Datasets

Not discussed in the paper. The authors use simulated data for their experiments.

Key Insights and Ideas

  • Coverage per Reward is Key: The central idea that "coverage per reward" is the most effective metric for budget-constrained participant selection is a crucial insight. It shifts the focus from simply maximizing coverage or minimizing cost independently to finding the optimal balance.
  • Hierarchical Coverage Simplifies the Problem: Dividing a large region into smaller, representative sampling points is an effective strategy to make the coverage problem tractable. This avoids the complexity of continuous area coverage.
  • Greedy Approach Sufficiency: The paper demonstrates that a greedy approach, while not always guaranteeing the absolute optimal solution for NP-hard problems, can provide a highly effective and efficient solution for this specific MCLB problem, outperforming more complex or brute-force methods.
  • Budget Thresholds Matter: The simulations highlight that there's a budget threshold beyond which additional budget doesn't significantly increase coverage, as most participants might already be selected.

Key Results

The paper's greedy algorithm was evaluated through extensive simulations and compared against an existing scheme (Zhang et al. [55]).

  • Outperforms Existing Scheme: The proposed greedy algorithm consistently achieved higher coverage quality (W) for a given budget compared to the existing method.
  • Budget Sensitivity: Coverage quality increases with the budget, but the rate of increase slows down as the budget grows, indicating diminishing returns.
  • Sampling Point Impact: Increasing the number of sampling points (m) decreases coverage quality, as expected, because more ground needs to be covered with the same resources.
  • Sensor Radius Impact: A larger sensor coverage radius (rs) generally leads to higher coverage quality, as participants can cover more sampling points.
  • Participant Number Impact: Increasing the number of participants (n) improves coverage quality, as it provides more options for the greedy algorithm to select cost-efficient participants.

Limitations and Future Work

  • NP-Completeness: The authors acknowledge that the MCLB problem is NP-hard, meaning finding the absolute optimal solution can be computationally very expensive for large-scale scenarios. Their greedy algorithm offers a practical approximation.
  • Participant Reward Assumption: The paper assumes participants propose their rewards. Future work could explore more sophisticated incentive mechanisms or dynamic reward adjustments.
  • Uniform Sampling Point Contribution: The current model assumes all sampling points have equal importance. In real-world scenarios, some areas might be more critical than others, requiring a weighted coverage approach.
  • Dynamic Environment: The model primarily focuses on static sampling points and participant paths. Future work could consider dynamic changes in participant availability or environmental conditions.
  • Partitioning Strategy: While the paper mentions partitioning large regions, the optimal strategy for dividing regions based on geographical characteristics or pollution sources could be further explored.

Summary updated

Abstract

The Mobile Crowd-sensing Network is a novel cyber-physical-social network which has received great attention recently and can be used as a powerful tool to monitor the phenomenon of the field of interest. Due to the limited budget, how to choose appropriate participants to maximize the coverage quality is one of the most important issues when the mobile crowd-sensing network applies to practical application, such as air quality monitoring. In this paper, given the number of available participants, the traverse path and the reward of each participant, we investigate the problem of how to choose suitable participants to monitor an environment of a critical region by a crowd-sensing network, while the total rewards for all selected participants is not larger than the limited budget. In our solution, we first divide a big critical region such as a city into smaller regions of different size, and select some sampling points in the smaller region; the collected data of those sampling points represents the collected data of the whole smaller region. Then, we design a greedy algorithm to select participants to cover the maximum sampling points while the total rewards of selected participants does not exceed the limited budget. Finally, we evaluate the validity and efficiency of the proposed algorithm by conducting extensive simulations. The simulation results show that the greedy algorithm outperforms an existing scheme.
BibTeX
@inproceedings{chen2019maximizing,
  author = {Jiaoyan Chen and Jingsen Yang},
  title = {{Maximizing Coverage Quality with Budget Constrained in Mobile Crowd-Sensing Network for Environmental Monitoring Applications}},
  booktitle = {Sensors},
  year = {2019},
  doi = {10.3390/s19102399},
}
Figure