Decision Making Under Uncertainty using Learning and Game Theoretic Approaches in Mobile Crowdsensing

With the rapid growth of the Internet of Things (IoT) and the increasing number of smart sensing devices, modern communication systems enable the acquisition, transport, processing, and timely delivery of sensed information for various applications. Future wireless networks, e.g., 6G, are envisioned to provide Sensing-as-a-Service (SaaS) as a native capability complementing communication and computing to enable intelligent, context-aware applications such as Digital Twins (DTs), intelligent transport systems, Augmented Reality (AR) and Virtual Reality (VR), and smart cities. Realizing this vision requires a scalable, efficient sensing architecture that provides measurement updates on demand. Mobile Crowdsensing (MCS) is a promising architecture to this end, in which Mobile Units (MUs) such as smartphones, wearables, and smart sensors perform various sensing tasks to gather information for the Data Requesters (DRs) with the help of an MCS Platform (MCSP). Compared with wireless sensor networks, MCS offers better coverage due to MU mobility, lower infrastructural costs, and perform a larger variety of sensing tasks, making it attractive for different sensing and monitoring applications.

In MCS, the DRs incentivize the MCSPs and MUs to perform the sensing tasks and collect the sensed information, and determine the sensing task requirements. The MCSPs and MUs, on the other hand, are selfish decision making agents focused on their individual goals, making the design of sensing strategies for data acquisition challenging. This thesis identifies and addresses four fundamental challenges in designing an efficient MCS system. First, the agents lack complete non-causal information about the system dynamics, such as future task arrivals, participant availability, channel conditions, and sensing costs, forcing decisions under uncertainty; they start with incomplete information and must learn over time. Second, strategic interdependence and information asymmetries arise because each agent lacks information about the others’ strategies; e.g., the MCSPs do not know whether an MU will successfully perform a sensing task or the quality of the data it will provide, and the MUs are unaware of the MCSPs’ budget allocation and the offers made to other MUs. Third, the technical objectives of maximizing sensed data quality, coverage, and task completion are coupled with, and often conflict with, the economic objectives of maximizing revenue and ensuring cost-efficient operation. Fourth, as the agents adapt their action-selection policies to make better decisions over time, the learning environment becomes non-stationary, since multiple agents simultaneously adapt their strategies and the number of MUs, tasks, and decision variables can be very large. Additionally, the scalability of the learning approach is a further challenge. To address these challenges, this thesis studies MCS systems from three perspectives: the MCSP’s, the MU’s, and the joint perspective of MUs and MCSPs. The individual perspective shows how each agent learns to make decisions under uncertainty to achieve its goal, e.g., monetary or technical, while the joint perspective analyzes the interplay between the agents’ decision strategies in a realistic way. These perspectives are studied by modeling appropriate problems from the key decision maker’s perspective. The joint perspective is studied with both single-MCSP and multiple-MCSP scenarios to analyze the competition between the agents.

From the MCSP’s perspective, the task allocation problem is considered, in which a single MCSP, the only decision making agent, decides which energy harvesting MUs are suitable for different sensing tasks. The problem is formulated to maximize the average weighted number of completed tasks over a finite time horizon, where a weighting factor for each task type accounts for fairness in task execution. An optimal benchmark solution is first derived assuming perfect non-causal information about the channel coefficients, harvested energy, MU locations and trajectories, and the sensing tasks. To make efficient decisions when such information is unavailable in real-world MCS systems, a novel Deep-Q-Network-based algorithm is proposed. The proposed algorithm

outperforms state-of-the-art benchmark solutions by at least 12% in average weighted task completions while achieving 92.2% of the optimal solution’s performance.

From the MU’s perspective, the task participation problem is considered in a decentralized manner, in which the MUs use their individual preferences to decide whether to perform the sensing tasks. By choosing not to perform a task, the MUs save energy for a future, potentially more suitable sensing task; if they choose to perform one, they decide which of the available tasks to perform, while the MCSP incentivizes them through monetary compensation. The problem is formulated as a decentralized Markov game under incomplete information, in which both the MUs and the MCSP are selfish and maximize their individual goals, such as achieved income and completed tasks. To this problem, a novel, fully decentralized and scalable, Federated Deep Reinforcement Learning-based Proximal Policy Optimization (FDRL-PPO) algorithm is proposed and implemented at every MU, where federation allows the MUs to share their learned policies while maintaining competition to maximize individual goals. The approach is extensively validated using both synthetic and real-world data from a commercial MCS application, focusing on task completion, collisions, fairness in task execution, and energy consumption, and considering the impact of scalability, task load, task budgets, and MU join-ins and drop-outs. Simulation results show that the proposed solution outperforms state-of-the-art benchmark solutions by at least 9.2% in the average weighted number of completed tasks across different scenarios.

While the individual perspectives tackle incomplete information, scalability, and the techno-economic aspect of MCS, the challenge of strategic interdependence and information asymmetries between the agents persists. To address all of these challenges, a joint perspective is necessary that considers both MUs and MCSPs as selfish and independent decision making agents. For the joint perspective, we first consider a scenario with one MCSP and multiple MUs. The MUs devise task proposal strategies that maximize their individual profits, while the MCSP determines task assignment strategies from the proposals that maximize its own utility. The interaction is modeled as a

two-sided matching game. To solve this game, we propose a novel Two-Sided Learning (TSL) algorithm, consisting of the Two-Sided Learning Task Proposal (TSLTP) at the MUs and the Two-Sided Learning Task Assignment (TSLTA) at the MCSP. Accounting for the limited battery capacities of the MUs, the game evolves into a dynamic two-sided matching game in which MU availability depends on the energy in their batteries. This dynamic game is solved by the Energy-aware Two-Sided Learning (ETSL) approach, which comprises an Energy-aware Task Proposal algorithm (ETP) at every MU and TSLTA at the MCSP. The ETP balances the cost of using energy now for immediate profits against saving it for a potentially more profitable future task while considering competition with other MUs. ETSL achieves 92% of the social welfare of the value iteration algorithm, which assumes and uses complete information about the MCS system. ETSL outperforms the other benchmark algorithms by at least 13% in achieved social welfare.

For the joint perspective considering multiple MCSPs, they compete with each other to recruit MUs. Both, MCSPs and MUs, are selfish decision makers maximizing their individual revenues. The conflicting interests are captured by formulating the respective task proposal and task acceptance problem as a Matching game with Contracts (MWC). The MWC is reformulated as a level-one dynamic hypergame in which the unknown preferences of competing MCSPs are modeled as perceptions updated over time in a repeated matching game. To handle completely unknown preferences at both the MCSPs and the MUs, the novel and fully decentralized Perception-aware Combinatorial Multi-armed Bandit (PACMAB) is proposed, combining an Upper Confidence Bound (UCB) multi-armed bandit algorithm at every MCSP and a low complexity multi-armed bandit algorithm at every MU. Extensive simulations demonstrate that PACMAB outperforms the benchmark algorithms by at least 52.9%, 9.1%, and 43.9% in achieved social welfare, energy consumption, and task completion ratio over time.

For each perspective, the computational complexity of the proposed learning algorithms is analyzed. Overall, this thesis shows that decentralized, learning-based, and game-theoretic mechanisms can jointly reconcile the technical and economic objectives of MCS, even when the MCSPs and MUs act selfishly under incomplete information, thereby providing a foundation for a practical realization of sensing-as-a-service in future wireless networks.