Immune Genetic Whale Optimization Algorithm for Multi-Task Allocation in Mobile Crowdsensing Under Matching Willingness Rules

0
0
0

Introduction

Mobile Crowdsensing (MCS) has emerged as a promising paradigm for large-scale data collection, leveraging the widespread use of smart mobile devices. It enables cost-effective, flexible, and ubiquitous sensing in various applications, including traffic management, environmental monitoring, and public safety. A critical challenge in MCS is task allocation, where the platform must efficiently distribute tasks among participants while maximizing system performance and ensuring participant engagement.

Traditional MCS task allocation methods primarily focus on time constraints, ensuring that participants can complete tasks within specified deadlines. However, these approaches often neglect the mutual matching willingness between tasks and participants, leading to low task acceptance rates and suboptimal platform profits. In real-world scenarios, both the platform and participants are rational entities—the platform avoids assigning tasks to unsuitable participants, and participants may reject tasks that do not align with their preferences. Ignoring these factors results in inefficient resource utilization and reduced system stability.

To address these limitations, this paper introduces a novel task allocation algorithm called the Immune Genetic Whale Optimization Algorithm (IGWOA). IGWOA integrates the intelligent search mechanisms of the Whale Optimization Algorithm (WOA) with immune genetic principles, enhancing both global and local search capabilities. By incorporating task and participant preferences into the allocation model, IGWOA improves task acceptance rates, optimizes platform profits, and ensures fair participant engagement.

Problem Formulation

System Model

The MCS system consists of three main entities: task requesters, the MCS platform, and mobile participants. Task requesters submit task requirements to the platform, which then assigns these tasks to participants based on predefined constraints. Participants execute the tasks and receive compensation upon completion.

Each task is characterized by attributes such as location, validity period, required sensing duration, and importance level. Participants, on the other hand, provide information including their initial location, expected working duration, activity radius, reputation, social skills, task proficiency, device battery level, computational resources, and data transmission efficiency.

Constraints

The task allocation problem is subject to several constraints:

  1. Time Constraints: Participants must complete assigned tasks within their expected working duration, and tasks must be executed before their validity expires.
  2. Matching Willingness Constraints: The mutual preference between a task and participant must meet or exceed a platform-defined threshold. This ensures that tasks are assigned to participants who are both capable and willing to perform them.
  3. Task Assignment Constraints: Each task can be assigned to only one participant, and no participant can receive the same task more than once.

Objective

The primary objective is to maximize the platform’s profit, defined as the difference between the payment received from task requesters and the compensation paid to participants. The profit function considers the successful completion of tasks and the associated costs.

Matching Willingness and Task Reward Calculation

Matching Willingness

The mutual preference between a task and a participant, termed matching willingness, is computed based on two components:

  1. Task-to-Participant Preference: This evaluates how well a participant fits a task based on reputation, social skills, and task proficiency.
  2. Participant-to-Task Preference: This assesses a participant’s interest in a task based on distance, device battery level, and task importance.

The overall matching willingness is a weighted combination of these preferences. A higher value indicates a stronger alignment between task requirements and participant capabilities.

Task Reward Calculation

To ensure fairness among participants, the platform employs a Nash bargaining strategy to determine task rewards. The reward computation considers:

  1. Execution Cost: This includes resource consumption (e.g., computational power, data transmission efficiency) and labor costs (e.g., time and effort required to complete the task).
  2. Matching Willingness Impact: Participants with higher matching willingness receive lower cost adjustments, reflecting their willingness to accept the task.

The final reward is derived by balancing the platform’s payment from requesters and the participant’s execution cost, ensuring a fair distribution of profits.

Immune Genetic Whale Optimization Algorithm (IGWOA)

Algorithm Overview

IGWOA is designed to solve the MCS multi-task allocation problem under time and matching willingness constraints. It combines the strengths of WOA with immune genetic principles to enhance search efficiency and solution quality.

Key Components

  1. Whale Optimization Algorithm (WOA):
    • Search Prey Phase: Explores the solution space to identify potential task assignments. • Encircling Prey Phase: Focuses on refining solutions around promising candidates. • Bubble-Net Attacking Phase: Enhances local search to fine-tune solutions.
  2. Immune Genetic Enhancements:
    • Crossover Operation: Introduces diversity in task assignment strategies during the search phase. • Vaccination Operation: Injects high-quality solutions (vaccines) into the population to improve convergence. • Mutation Operation: Perturbs solutions in the bubble-net phase to escape local optima.

Algorithm Workflow

  1. Initialization: A population of task assignment solutions is generated using a random greedy strategy.
  2. Fitness Evaluation: Each solution is assessed based on platform profit, with higher profits indicating better solutions.
  3. Evolutionary Operations:
    • If the algorithm is in the global search phase (determined by a control parameter), crossover operations diversify the population. • If in the local search phase, vaccination and mutation operations refine solutions.
  4. Repair Mechanism: Invalid solutions (those violating constraints) are repaired to ensure feasibility.
  5. Termination: The algorithm iterates until convergence or a maximum number of iterations is reached, returning the best task assignment strategy.

Computational Complexity

IGWOA’s time complexity is primarily determined by the repair mechanism, which ensures solutions adhere to constraints. Given n tasks and m participants, the worst-case complexity is O(m×n), making it scalable for large-scale MCS scenarios.

Experimental Evaluation

Experimental Setup

Simulations were conducted using synthetic datasets to evaluate IGWOA’s performance under varying conditions. Key parameters included:

  • Participants: Ranging from 20 to 200.
  • Tasks: Ranging from 60 to 500.
  • Matching Willingness Threshold: Varied from 0.37 to 0.87.

Performance Metrics

  1. Platform Profit: Total revenue minus participant compensation.
  2. Task Allocation Rate: Percentage of successfully assigned tasks.
  3. Average Tasks per Participant: Measures participant engagement.
  4. Runtime: Computational efficiency of the algorithm.

Comparative Analysis

IGWOA was compared against five baseline algorithms:

  1. WMTA-GA: A genetic algorithm-based task allocation method.
  2. WOA: The standard Whale Optimization Algorithm.
  3. GA-SA: A hybrid genetic and simulated annealing approach.
  4. Random Allocation Algorithm (RAA): Assigns tasks randomly.
  5. Greedy Allocation Algorithm (GAA): Prioritizes high-profit assignments.

Results

  1. Platform Profit and Task Allocation Rate:
    • IGWOA consistently outperformed baseline methods across different participant and task scales. • As participant numbers increased, IGWOA achieved higher profits and allocation rates due to its ability to balance exploration and exploitation.
  2. Participant Engagement:
    • IGWOA assigned more tasks per participant compared to baselines, indicating better resource utilization.
  3. Runtime Efficiency:
    • IGWOA exhibited lower computational overhead than WMTA-GA and GA-SA, making it suitable for real-time applications.
  4. Impact of Matching Willingness Threshold:
    • Higher thresholds reduced the number of valid task-participant pairs, decreasing allocation rates. However, IGWOA maintained superior performance by adaptively adjusting its search strategy.

Model Validation

To validate the effectiveness of incorporating matching willingness rules, experiments compared two models:

  1. Time-Only Constrained Model: Considers only time constraints.
  2. Time + Matching Willingness Model: Integrates both constraints.

Results demonstrated that the latter model achieved higher average task and participant preferences, confirming that matching willingness rules enhance allocation stability and participant satisfaction.

Conclusion

This paper presented IGWOA, a novel task allocation algorithm for MCS systems that addresses the limitations of existing methods by incorporating time and matching willingness constraints. By integrating immune genetic principles into WOA, IGWOA enhances solution diversity, accelerates convergence, and improves local search capabilities.

Experimental results demonstrated IGWOA’s superiority in platform profit, task allocation rate, and participant engagement across various scenarios. Its computational efficiency further underscores its applicability to large-scale MCS deployments.

Future research directions include investigating the impact of social communities on task allocation and exploring dynamic matching willingness thresholds to adapt to real-time platform demands.

DOI: 10.19734/j.issn.1001-3695.2024.08.0321

Was this helpful?

0 / 0