Abstract
As an appealing sensing paradigm, Mobile Crowd Sensing (MCS) provides a cost-efficient solution for large-scale urban sensing tasks. However, in practice, many MCS applications suffer from the failure of sensing task execution due to the randomness of participant behavior, lack of prior experience, and insufficient monetary rewards. To mitigate these impacts, we propose a novel "failure-aware" mobile crowd sensing framework. This two-stage approach includes an offline task allocation algorithm (FPSAll) and an online task transfer mechanism (FTASKTraf). By leveraging social relationships to facilitate task hand-offs, we significantly enhance task completion ratios. Extensive experiments on real-world datasets demonstrate the effectiveness of our proposed approaches.
Introduction
Mobile Crowd Sensing (MCS) leverages the ubiquity of smartphones to create massive, distributed sensor networks for monitoring urban environments, from air quality to traffic patterns. Despite its potential, the human element introduces significant volatility. Users often accept tasks but fail to complete them due to battery depletion, route changes, or competing priorities. Statistics from existing platforms indicate that task abandonment can reach as high as 164% relative to completed tasks.
Traditional research has focused primarily on the "pre-execution" phase, attempting to optimize initial task allocation based on historical user data. However, these systems often lack a recovery mechanism once a task is assigned. If the primary user drops out, the task fails. This paper addresses this gap by introducing a failure-aware system that recovers tasks in real-time through social-network-based transfers.
The Failure-Aware Framework
The proposed system operates in two distinct stages to ensure robustness against individual user failures.
1. Offline Task Allocation (FPSAll)
Rather than a standard "greedy" approach that assigns tasks to the most likely candidates—often leading to resource bottlenecks—we employ a nondeterministic algorithm called FPSAll. This method ranks tasks using a utility function that balances candidate scale, mean completion probability, and fitness entropy. Tasks are then allocated using "fitness proportionate selection," ensuring a balanced distribution across the global user pool and preserving a "safety net" of alternative users.
2. Online Task Transfer (FTASKTraf)
The "rescue" phase activates when a user realizes they cannot complete a task. Instead of the task being marked as a failure, it is transferred to a social acquaintance.
As shown in Figure 1, if user $u3$ is unable to reach location $t1$, the system evaluates potential successors like $u4$. The selection of a successor is based on Social Relation Strength (historical co-occurrence), Physical Distance, and Reputation.
Experimental Methodology
The framework was evaluated using the UCSD Wireless Topology Discovery (WTD) dataset, which tracks access point (AP) connections for campus users every 20 seconds. The authors filtered this data to focus on 68 mobile users and 124 APs with high-density records. Thirty days of data were utilized to train mobility profiles, which informed both the initial task allocation and the calculation of social relationship strengths.
Key Results and Social Insights
The experiments yielded several critical insights into the dynamics of failure-aware sensing:
- Algorithm Performance: FPSAll consistently outperformed baseline "RankAll" methods. By avoiding over-allocation to top-tier users, the system maintained higher flexibility, allowing it to tackle more tasks successfully even under strict resource constraints.
- The Social Incentive: A survey of 57 students revealed that 86.5% were willing to accept a "failed" task from an acquaintance. This suggests that social ties and friendship act as powerful, low-cost incentives that can supplement or even replace purely monetary rewards.
- Reward Distribution: The study also explored how rewards should be split between the initial executor and the "rescuer."
As illustrated in Figure 2, initial executors generally expect higher compensation (with 47.37% favoring the 7-10 USD range), while successors are more amenable to lower rewards (39.65% accepting 1-3 USD). This disparity allows for a sustainable incentive model where both parties benefit from a successful "rescue."
Conclusion and Future Directions
This research demonstrates that failure-aware MCS, supported by social-relationship-based transfers, can significantly improve task completion rates. By treating social acquaintances as a distributed safety net, the system mitigates the impact of unpredictable human behavior while preserving privacy through client-side transfers.
Future work will address the "cold start" problem for new users without established social profiles and investigate the battery and data overhead associated with continuous execution monitoring on mobile devices. Additionally, scaling the framework to urban-level populations with thousands of users remains a key challenge for real-world deployment.
Summary updated