PREPRINT
1
Energy-Aware Two-Sided Learning for Dynamic Matching Games in Mobile Crowdsensing
arXiv:2609.29880v1 [cs.NI] 24 Sep 2026
Sumedh J. Dongare, Student Member, IEEE, Anja Klein, Member, IEEE, and Andrea Ortiz, Member, IEEE
Abstract—Mobile crowdsensing (MCS) is a promising enabler of Sensing-as-a-Service (SaaS) for next generation networks (NGNs), where sensing, communication, and computing are jointly considered as on-demand services. In MCS, mobile units (MUs) collect and deliver sensing data to data requesters (DRs) via a mobile crowdsensing platform (MCSP) in exchange for monetary incentives. After sensing tasks are announced, MUs strategically select tasks to maximize their long-term utility while accounting for energy and time costs, whereas the MCSP assigns tasks to maximize its own service revenue and data quality. A fundamental challenge arises from the lack of prior knowledge of MUs’ sensing qualities and task efforts, as well as the energy limitations of battery-powered devices, which directly impacts service availability and reliability in SaaS for NGNs. To address these challenges, we formulate the interaction between MUs and the MCSP as a dynamic two-sided matching game under incomplete information, explicitly incorporating energy constraints. We propose Energyaware Two-Sided Learning (ETSL), a fully decentralized and lightweight learning framework in which MUs locally learn task proposal strategies, while the MCSP learns the data quality of participating MUs to devise task assignment strategy. ETSL jointly enables MUs’ energy-aware task proposals and MCSP’s adaptive task assignment, considering their individual preferences to maximize their net revenues. Simulation results demonstrate that ETSL significantly improves MU and MCSP profits and overall energy efficiency, highlighting its effectiveness as a scalable and sustainable SaaS solution for NGN. Index Terms—Dynamic matching games, Multi-armed Bandits, Q-Learning, Reinforcement Learning, Resource Allocation for Wireless Networks
I. Introduction
N
EXT generation wireless networks are envisioned to provide sensing-as-a-service (SaaS) as a native capability, complementing communication and computing to enable intelligent and context-aware applications [1]. S. J. Dongare and A. Klein are with the Communications Engineering Lab, Technical University of Darmstadt, Landgraf-Georg-Strasse 4, 64283 Darmstadt, Germany (e-mail: {s.dongare, a.klein}@nt.tudarmstadt.de). A. Ortiz is with the Institute of Telecommunications, Vienna University of Technology, Austria (e-mail: [email protected]). Corresponding author: Sumedh J. Dongare (e-mail: [email protected]). This work has been funded by the German Research Foundation (DFG) as a part of the project C1 and B3 within the Collaborative Research Center (CRC) 1053 - MAKI (Nr. 210487104) and has been supported by the German Federal Ministry of Research, Technology and Space (BMFTR) project Open6GHub+ under grant 16KIS2407, by DAAD with funds from BMFTR under grant 57817830, and by the LOEWE Center emergenCITY under grant LOEWE/1/12/519/03/05.001(0016)/72. The work of Andrea Ortiz was funded by the Vienna Science and Technology Fund WWTF under grant 10.47379/VRG23002.
To realize this vision, scalable sensing infrastructures are needed to provide measurement updates on demand and support distributed decision-making across heterogeneous sensing, communication, and computing resources. In this context, Mobile Crowdsensing (MCS) is a promising distributed sensing framework for SaaS, where mobile units (MUs), such as smartphones, vehicles, wearables, and other mobile IoT devices, are incentivized to collect and deliver sensing data through a mobile crowdsensing platform (MCSP) in exchange for monetary compensation [2]. Since MUs are autonomous, heterogeneous, and typically battery operated, MCS naturally introduces challenges related to incentive-, quality-, and energy-aware resource orchestration. An MCS system consists of three stakeholders, namely, a data requester (DR), a MCSP, and MUs. When the DR requires sensing data from a target area, it conveys this request to the MCSP and offers a payment for the requested sensing service. The MCSP converts the request into sensing tasks, publishes them to the available MUs, and uses part of the DR’s payment to recruit suitable participants. The MUs select tasks according to their own preferences and submit task proposals, including their desired payments, to the MCSP. In this framework, payments act as incentive signals that connect sensing demand from DRs with distributed sensing supply from the MUs. From the NGN perspective, the MCSP can be viewed as a platform-side orchestration entity, potentially implemented at the network edge or in the cloud, that coordinates task dissemination, sensing-result collection, participant selection, and quality-aware service provisioning. The MUs must carefully utilize their available energy while maximizing their individual utilities. As a result, the task proposal strategy of each MU depends on its preferences, task execution effort, expected payment, and current battery state. Similarly, the MCSP performs task assignments to proposing MUs in order to improve its service utility, revenue, and the overall quality of the sensing results. Therefore, MCS-based SaaS requires the joint design of participant-side energy-aware decisionmaking and platform-side service orchestration. The MCS system can be modeled as a two-sided matching game [3], since the MCSP and the MUs hold individual preferences over task assignments and task proposals, respectively. The solution to this game aims to find task-MU combinations that are mutually beneficial for the MCSP and the MUs. However, in contrast to
IoT layer
traditional two-sided matching games, the availability of the MUs changes over time depending on the amount of energy available in their batteries. This temporal variation transforms the problem into a more complex dynamic matching game [4]. Solving this dynamic matching game optimally would require complete information about the MCS system, including future task arrivals, the battery state of every MU over time, task execution efforts, and the preferences of both the MUs and the MCSP. Such information is generally unavailable in practical MCS systems. Even if complete information were available, the optimal solution would exhibit poor scalability, with complexity growing exponentially in the number of MUs, sensing tasks, and the considered time horizon. Thus, a key challenge is to design scalable and lightweight task proposal and task assignment algorithms under incomplete information and endogenous MU availability. In the literature, many works assume complete information about the MCS system and optimize task allocation for latency minimization [5], quality maximization [6], and coverage maximization [7]. The authors in [8] optimize task proposal strategies by considering the preferences of the MUs. However, the assumption of complete information limits the applicability of these approaches in realistic and dynamic MCS deployments. To address uncertainty, reinforcement learning has been applied to optimize task assignment [9] and task proposal [10], [11] strategies separately. Nevertheless, in practical MCS-based SaaS systems, task proposal and task assignment are tightly coupled and should be jointly considered. Our previous work [12] studied decentralized task proposal by the MUs and learning-based task assignment by the MCSP under incomplete information, assuming unlimited MU energy and persistent MU availability. In reality, the availability of mobile sensing resources is directly affected by their battery dynamics. This fundamentally changes the problem by introducing an intertemporal coupling between learning, energy consumption, and participant availability, making the approach in [12] inapplicable to realistic energy-constrained scenarios. In particular, endogenous MU availability requires each task proposal strategy to explicitly account for both the current battery state and the time-varying competition among MUs. Although previous works have contributed significantly to task proposal and task assignment in MCS, designing an efficient and scalable solution that jointly addresses incomplete information at the MCSP and at the MUs, while accounting for dynamic availability, remains an open problem. The main contributions of this work are as follows. • We propose a novel fully decentralized learning framework, termed Energy-aware Two-Sided Learning (ETSL), for dynamic two-sided matching in energyconstrained MCS. ETSL consists of two components: i) an Energy-aware Task Proposal algorithm (ETP), which enables each MU to locally learn a customized task proposal strategy, and ii) a Task Assignment
2
Resource orchestrator at the Edge
PREPRINT
MCSP Available tasks in time step
1
MU 1
2
MU
MU MU 2
Task proposal from MU
…
MU
MU
MU
Task acceptance from MCSP
Fig. 1. The considered MCS system with heterogeneous MUs proposing to perform the available task types and an MCSP responding to the proposals. Here, no response from the MCSP indicates proposal rejection.
algorithm, which enables the MCSP to learn the sensing quality of participating MUs over time and adapt its assignment decisions accordingly. Using the proposed ETSL, the task proposal problem of the MUs and task assignment problem of the MCSP is solved simultaneously. • We provide a convergence analysis of the proposed approach using the well-known alternating-freeze approach to demonstrate that the proposed ETSL solution converges to a stable solution which maximizes the individual utilities of the MUs as well as the MCSP. • Using complexity analysis, we show that ETSL is a lightweight and scalable mechanism for energy-, incentive-, and quality-aware sensing-resource orchestration in MCS-based SaaS systems for future NGNs. • Extensive simulations demonstrate that ETSL is scalable and achieves social welfare within 7.6% of the optimal value iteration benchmark. Moreover, its energy consumption converges to that of the benchmark, while collisions are reduced by at least 9.1% compared with the considered baselines. II. System model We consider an MCS system consisting of an MCSP as a sensing resource orchestrator deployed at the edge/cloud and a set KMU = {MUk }K k=1 of energy harvesting MUs, as depicted in Fig. 1. The MUs are modeled within the IoT layer with integrated sensing, communication, and computing resources (ISCC). Time is divided into discrete time steps of equal duration indexed by t ∈ {1, . . . , T }. In each time step t, the MCSP publishes N sensing tasks collected in a set At = {an,t }N n=1 . Every sensing task an,t is categorized into Z different task types denoted by Z = {z}Z z=1 . A task type z may represent, for example, temperature sensing, environmental sensing, or traffic monitoring tasks. All the tasks of the same type are collected in the set Az,t ⊆ At . Each task type z is characterized by the average size sz of the sensing result in bits. We assume that each published task an,t requires only one MU to complete it. The MCSP can publish multiple
PREPRINT
3
tasks of the same task type z if the DR requires multiple sensing samples. A. Mobile Units (MUs) In every time step t, MUk decides whether to perform its preferred task of type z in Az,t , or to remain idle to save its energy for potentially more rewarding future tasks. If it decides to perform a task, MUk sends a task z proposal Ok,t to the MCSP containing the task type z and the expected payment Pk,n,t for its successful completion. An MU can submit at most one proposal per time step. MUk calculates the desired payment Pk,n,t based on its z z effort Jk,t required to complete a task of type z. Jk,t is measured in monetary units and depends on the time τk,n,t and energy Ek,n,t required to complete the task as z Jk,t = ατk,n,t + βEk,n,t , where α and β are importance factors for time and energy efforts, respectively. The time comp sense comm τk,n,t is given by τk,n,t = τk,n,t + τk,n,t + τk,n,t , where comp sense comm τk,n,t , τk,n,t and τk,n,t are the sensing, computation sense and communication times, respectively. τk,n,t indicates the time required to sense and produce valid sensing data of size dz measured in bits. It is drawn from a random distribution with probability density function sense sense fτzk,n,t = E[τk,n,t ] of the sensing sense . The expected value τ̄ k,z time depends on the task type z and the capabilities of MUk . Each MU processes the sensing data to generate comp the sensing result [13]. The time τk,n,t required for the comp processing is calculated as τk,n,t = cz dz /fklocal , where cz is a random variable modeling the processing complexity of task type z and fklocal is the CPU frequency of MUk measured in Hz. After processing, the final sensing result rk,n,t , with size sz < dz bits, is transmitted back to comm the MCSP. The transmission time τk,n,t depends on the stochastic characteristics of the channel between MUk and MCSP. To perform a task, MUk spends energy Ek,n,t given by comp sense comm Ek,n,t = psense τk,n,t + pcomm τk,n,t + pcomp τk,n,t , where k k k comp comm pk is MUk ’s transmit power and pk is the power required to process task an,t . To perform the tasks, every MUk uses energy from its battery with capacity Bmax . The battery status bk,t in time step t is bk,t = min(bk,t−1 − h h Ek,n,t + Ek,t , Bmax ), where Ek,t is the amount of energy harvested by MU k. The utility or profit of MUk in time step t is MU z Uk,n,t = Pk,n,t − Jk,t .
(1)
The MUk must know the exact time and energy efforts it MU requires to perform task an,t to calculate Uk,n,t . However, given the random nature of τk,n,t and Ek,n,t , the MUs cannot know the exact efforts required before performing the task. Thus, MUk estimates the expected utility MU Ûk,z =
T ∑
1 MU E[Uk,n,t ], T t=1
(2)
where an,t ∈ Az,t . This estimate is then used to make a task proposal decision and to select the payment Pk,n,t . MU We define IkMU = {Ûk,z |z} as the MU-side information.
Note that IkMU is not available in advance at MUk and has to be learned over time by performing tasks. Based on its own estimates of IkMU , every MUk sends a proposal z Ok,t to the MCSP. B. Mobile Crowdsensing Platform The MCSP receives the set of task proposals Ot from all MUs for the available tasks in At and decides which MUk executes which task an,t . The task assignment decision is denoted by xk,n,t ∈ {0, 1}. xk,n,t = 1 means an,t is assigned to MUk , otherwise xk,n,t = 0. The MCSP can assign the task an,t to only ∑ one of the MUs proposing to that type of task, i.e., k xk,n,t ≤ 1 ∀n, t. The DR pays the MCSP for every executed task. The earning wz,t which the MCSP gets when an,t ∈ Az,t is performed by MUk depends on the task type z and the quality factor qk,n,t ∈ [0, 1] of the sensing result rk,n,t . qk,n,t is calculated using a quality function Qz as qk,n,t = Qz (rk,n,t ). These quality functions Qz could be, e.g., Peak Signal-to-Noise Ratio (PSNR) for images or accuracy of the temperature sensing. The MCSP and the DR make a contractual agreement on the calculation of MCSP’s earning wz,t = (1 + qk,n,t )wz ,
(3)
where wz is the minimum payment in monetary units the MCSP charges the DR for performing a task of type z. As the quality qk,n,t of the sensing result rk,n,t is unknown to the MCSP in advance, wz,t is also unknown. The utility MCSP of the MCSP when assigning MUk to an,t ∈ Az,t Uk,n,t is MCSP Uk,n,t = (wz,t − Pk,n,t ).
(4)
MCSP The MCSP can maximize its utility Uk,n,t by balancing
the quality of the sensing result of MUk and its payment. However, as the MCSP does not know the quality factor qk,n,t of the MU performing task an,t ∈ Az,t , it estimates the expected utility when assigning MUk to a task type z 1∑ MCSP E[Uk,n,t ]. T t=1 T
MCSP Ûk,z =
(5)
MCSP We define IzMCSP = {Ûk,z |k} as the MCSP-side information about the MUs. IzMCSP contains information about MCSP’s income and the payments for all MUs. IzMCSP is not readily available at the MCSP and is learned over time from experience gained from selecting MUs. The combination of MU-side and MCSP-side information, denoted by I = {IkMU , IzMCSP |k, z}, is the complete information and is unknown to the MUs and the MCSP in advance.
III. Dynamic Matching Game Formulation The considered MCS scenario is a two-sided market in which the MCSP orchestrates sensing resources to execute tasks and the MUs offer their sensing resources in exchange for a payment as incentives [14]. We assume that the MCSP and the MUs are rational and independent entities which take their own decisions based
PREPRINT
4
on their preferences. Since their preferences influence their respective utilities, we use matching theory [3], specifically dynamic matching theory, to analyze and solve the joint task proposal and task assignment problem. Matching theory aims to obtain a stable matching, i.e., to find task allocations where the MUs and the MCSP cannot improve their individual utilities by changing the assignment. However, due to the limited battery capacities of the MUs, their availability depends on the amount of energy available. This means the number of available MUs changes over time which makes the game dynamic and naturally hard to solve. The dynamic matching problem captures the key challenge in service orchestration, where sensing services must be allocated under uncertainty, energy constraints, and competition, while maintaining long-term system efficiency. We denote our dynamic matching game in time step t as Gt . The MUs’ preference ordering ⪰MU k,t ranks the task types z ∈ Z w.r.t. the achieved expected utility over the ′ remaining time horizon, i.e., z ⪰MU k,t z , iff, T T ∑ [ MU ] ∑ [ MU ] E Uk,n,t E Uk,m,t ′ | an,t ∈ Az,t ≥ ′ | am,t ∈ Az ′ ,t . t′ =t
t′ =t
(6) This means, MUk prefers task type z over z ′ if the utility of performing tasks of type z is higher than the utility of tasks of type z ′ considering the remaining time horizon. Similarly, the MCSP prefers MUs which yield the highest MCSP expected utility Ûk,z for each task type z, i.e., MCSP MCSP MUk ⪰MCSP MUl ⇐⇒ Ûk,z ≥ Ûl,z . z
(7)
As a result, for the assignment of a task of type z, the MCSP prefers MUk over MUl if MUk provides higher utility compared to MUl . This preference ranking can only be correctly determined with MCSP-side information I MCSP . The task proposal and task assignment game Gt in time MCSP ), step t is a tuple Gt = (KtMU , {MCSP}, At , ⪰MU k,t , ⪰z MU MU where Kt ⊆ K is a subset of total MUs available in time step t. MUk ∈ KtMU signals its willingness to participate in any task of type z by sending a task proposal z to the MCSP. Based on the proposals, the MCSP Ok,t . The performs the task assignment according to ⪰MCSP z task assignment decisions for all MUs and available tasks in t are collected in the matrix Xt . For two MUs, MUk and MUl , and two tasks, an,t and am,t in time step t. The pair (MUk , z ′ ) is called a blocking pair, if both, MUk and the MCSP can improve their utilities by deviating from the current assignment [15]. The existence of the blocking pair (MUk , z ′ ) causes the matching Xt to be unstable because MUk could switch to am,t ∈ Az′ ,t and both, the MUk and the task am,t would obtain a more efficient matching and therefore a higher utility. The assignment Xt is said to be dynamically stable if no such blocking pairs exist [15]. In MCS, this means that each MU is assigned to its most preferred task while the MCSP selects its most preferred MU for
each task. This assignment should maximize the individual utilities of the MUs and the MCSP, and consequently, the social welfare. The performance of the whole MCS system is directly affected due to collisions, i.e., the difference between the total number of proposing MUs and the number of assigned MUs for each task type. A dynamically stable solution does not have any collisions. IV. Energy-aware Two-Sided Learning Algorithm A. Overview To optimally solve the game G formulated in Sec. III, complete information I is required at the MUs as well as at the MCSP, which is unrealistic to assume. Considering every MUk can only learn its own MUside information IkMU and the MCSP only learns the MCSP-side information IzMCSP , in this section, we present the Energy-aware Two-Sided Learning (ETSL) algorithm which aims to maximize the MUs’ and MCSP’s utilities using this local information. ETSL consists, i) an Energyaware Task Proposal (ETP) algorithm, run locally by every MU, and ii) Two-Sided Learning: Task Assignment (TSLTA), run by the MCSP. ETP is a Q-learning based solution implemented at every MUk to find an efficient task proposal strategy that maximizes the total achieved utility over the time horizon. Each MUk considers the state Sk,t = ⟨bk,t ⟩, i.e., its battery and the action Ak,t = Z ∪ {−1}, where −1 is the idle action. The state space in this work is deliberately minimal, comprising of only the battery state of the respective MU. As we assume a quasi-static channel model and the task arrivals are i.i.d., the battery level constitutes a sufficient statistic for the task proposal decision, in the sense that no additional observable variable alters the transition probabilities or the expected reward. A richer state representation would therefore increase the dimensionality of the problem without improving the quality of the resulting policy. MU Every MUk receives instantaneous utility Rk,t = Uk,n,t as a reward. Using ETP, each MUk independently learns z the effort Jk,t required to perform task an,t of type z by proposing and performing tasks of different types. This is crucial in a scenario where the MUs have limited energy. Moreover, the task proposal decision at time step t not only impacts their performance, but also their ability to propose in the next time steps. The estimation of the z expected efforts Jˆk,t for MUk is only possible when it gets assigned to tasks of type z. ETP is summarized in Alg. 1. Every MUk starts by initializing all Q-values Q(Sk,t , Ak,t ) to zero for t = 1, for all states Sk,t , and actions Ak,t . For every task type z, each z MUk maintains an initial estimate of the task effort Jˆk,0 (line 1). In every time step t, MUk observes the current state bk,t (line 3). Due to the energy constraints, MUk collects all the feasible tasks in time step t into the set Afk,t , i.e., if the expected energy Ēk,n,t required to perform the task an,t ∈ Az,t is smaller than the battery state bk,t , then task type z is added to the set Afk,t (line 4). To balance
PREPRINT
5
Algorithm 1 Energy-aware Task Proposal (ETP) algorithm 1: Initialize Q(Sk,t , Ak,t ) = 0, for all states Sk,t ∈ Sk and actions Ak,t ∈ MU z Ak , Ũk,n,t , Jˆk,t
∀k ∈ K, z ∈ Z, t ∈ {1, . . . , T } and ϵ1 = ϵmax .
2: for t = 1, . . . , T do 3: Observe current available tasks and current state Sk,t = ⟨bk,t ⟩. 4: Obtain a feasible set Afk,t . 5: if η < ϵt where η ∼ U [0, 1] then 6: Randomly select a task type z ∈ Z from Afk,t . {Exploration} 7: else 8: Select Ak,t = arg maxA ∈Af Q(Sk,t , Ak,t ). {Exploitation} k,t k,t 9: end if 10: If Ak,t = −1, MUk stays idle. z 11: If Ak,t = z ∈ Z, select payment P̂k,z ← Peffort (Jˆk,t ). z 12: Send task proposal Ok,t . 13: Wait for the MCSP’s decision xk,n,t from TSLTA [12]. 14: if xk,n,t = 1 then 15: Perform the task an,t and transmit the result rk,n,t to MCSP. MU 16: Receive payment P̂k,z and observe Uk,n,t . MU z MU z 17: Update estimates Ũk,n,t and Jˆk,t based on Uk,n,t and Jk,t . 18: Update the Q(Sk,t , Ak,t ). {Q-learning update rule} 19: else MU MU z z 20: Ũk,n,t ← − Ũk,n,t−1 , Jˆk,t ← − Jˆk,t−1 . 21: end if 22: Update ϵt+1 = min{ϵmin , ϵt ∗ θ} 23: end for
are made in every time step t based on the proposals z Ok,t received from the MUs. The MCSP cannot observe MU battery dynamics and therefore cannot anticipate the long-term impact of its task assignment decisions on MU availability. Under this information structure, any MCSPside learning strategy is inherently myopic, making TSLTA from [12] an appropriate solution for instantaneous utility maximization. MCSP In TSLTA, the MCSP initializes the Ũk,n,t for all MUs MU and all task types. The set Kt of MUs is the action space for TSLTA. The MCSP may assign the task to a random MU proposing for the task an,t ∈ Az,t to improve MCSP its estimate of Ũk,n,t ; or, it may exploit the available knowledge to assign the task to MUs which maximize MCSP its estimated expected utility Ũk,n,t . To balance the exploration-exploitation, the MCSP uses ϵ-greedy action selection. The assignment decisions are sent back individually to each proposing MUk . After this, the assigned MUs perform the task and transmit the sensing result rk,n,t back to the MCSP. Using rk,n,t , the MCSP evaluates the MCSP quality of the result qk,n,t and observes the Uk,n,t . Then (U MCSP −Ũ MCSP )
exploration and exploitation of the Q-learning algorithm, MUk follows a decaying ϵ-greedy policy. With probability ϵt , MUk explores by randomly selecting a task type z from the feasible set Afk,t (line 6). With a probability 1 − ϵ, it exploits its current knowledge by selecting the task of type z from the feasible set Afk,t that maximizes MU the estimated expected utility Ũk,n,t , based on the Qvalues learned from previous time steps (line 8). If idle action Ak,t = −1 is selected, the MUk remains idle in time step t. If Ak,t = z ∈ Afk,t is selected, MUk calculates z the payment P̂k,z based on its estimated task effort Jˆk,t−1 z (line 11). MUk then sends a task proposal Ok,t , including the selected task type and payment, to the MCSP (line 12). The MCSP collects all incoming proposals and decides which MUs are assigned to the available tasks (line 13). If MUk is assigned to the task an,t , i.e. xk,n,t = 1, it proceeds to execute the task (line 14). If the task is successfully completed, MUk receives the payment P̂k,z and observes MU z the utility Uk,n,t as well as the exact task effort Jk,t (line MU 15). Uk,n,t is used to update the estimated expected utility (U MU −Ũ MU
)
MU MU MU Ũk,n,t as Ũk,n,t = Ũk,n,t−1 + k,n,t N zk,n,t−1 , where Nkz k represents the number of times MUk was assigned to a z task of type z (line 17). The effort estimate Jˆk,t is updated MU similarly (line 17). The achieved utility Uk,n,t is used as the reward to update the Q-value for the selected stateaction pair using the standard Q-learning update rule (line 18). If MUk is rejected by the MCSP, the estimated task efforts and utility remain unchanged (line 20). By learning the task efforts for the available task types and acceptance probabilities of the MCSP, every MU refines its task proposal strategy, improving its ability to balance energy constraints with maximizing utility. ETP uses the idle action smartly such that the MU can save its energy if it does not find a feasible task to propose. At the MCSP, the task assignment decisions xk,n,t
MCSP MCSP the MCSP updates Ũk,z,t = Ũk,z,t−1 + k,n,t N z k,n,t−1 , k z where Nk is the number of times MUk is assigned to task type z. With the help of ETP and TSLTA, we jointly optimize the MUs’ task proposals to maximize their utilities as well as MCSP’s task assignments to maximize the MCSP’s utility.
B. Convergence of ETSL Owing to the coupled, non-stationary nature of the twosided learning problem, we characterize convergence by conditioning on stationarity of one side at a time, following the standard alternating-freeze approach used in multiagent reinforcement learning analysis [16], [17]. Assumption 1 (Stationary MCSP policy): The MCSP’s assignment rule has converged to the greedy form MCSP , held fixed for t ≥ t0 . k ∗ (z, t) = arg maxk∈Pz,t Ũk,z,t−1 Proposition 1 (MU-side convergence): Under Assumption 1, the decision problem faced by MUk is a stationary MDP Mk = (Sk , Ak , Pk , Rk ) with Sk,t = ⟨bk,t ⟩. If (i) rewards Rk,t are bounded, (ii) the learning-rate schedule satisfies the Robbins-Monro conditions, and (iii) the exploration policy is greedy in the limit with infinite exploration (GLIE), then Q(Sk,t , Ak,t ) → Q∗ (Sk,t , Ak,t ) with probability 1. Proof: Under Assumption 1, the acceptance probability of MUk ’s proposals depends only on the competition from other MUs, so the transition kernel Pk (Sk,t+1 | Sk,t , Ak,t ) is stationary. The battery evolution depends on Ak,t only through the now stationary acceptance h probability, and Ek,n,t , Ek,t are themselves stationary. The result follows directly from the classical Q-learning convergence theorem [16], [17]. Assumption 2 (Approximately stationary aggregate proposal process): For each task type z, let Mz,t := |Pz,t | = ∑K k=1 1{Ak,t = z} denote the aggregate number of proposals received at time t. We assume that for t ≥ t0 , the dis-
PREPRINT
tribution of Mz,t is approximately stationary, even though individual MUs’ proposal decisions Ak,t may remain nonstationary due to ongoing battery-state fluctuations bk,t . Justification: Battery dynamics evolve independently across MUs, driven by independent energy-harvesting processes (see Sec. V). Even after Q(Sk,t , Ak,t ) has converged (Proposition 1), individual proposal sequences {Ak,t }t remain stochastic due to slow mixing of bk,t . However, since Mz,t aggregates K approximately independent indicator variables, a mean-field argument gives Mz,t a.s. −−→ ρ̄z as K → ∞, (8) K √ with fluctuations of order O(1/ K) by the law of large numbers. For large number of MUs used in the evaluation, this concentration is substantial, supporting the treatment of the competition landscape Mz,t , which determines the proposal pool Pz,t from which TSLTA selects as approximately stationary for t ≥ t0 , independent of MUspecific non-stationarity. Proposition 2 (MCSP-side convergence): Under Assumption 2, TSLTA reduces, independently for each task type z, to a stochastic multi-armed bandit problem over MCSP arms k ∈ Pz,t with stationary mean reward Uk,z . Given z bounded rewards and Nk → ∞ a.s. for all k, the estimate MCSP MCSP Ũk,z,t → Uk,z a.s., and the induced greedy policy MCSP converges to k ∗ (z) = arg maxk Uk,z . Proof: The assignment problem decouples across task types z. Within a fixed z, stationarity of ρk,z renders the proposal arrival process stationary, and the incremental update in (5) is exactly the sample-mean estimator, whose convergence follows from the strong law of large numbers and standard ϵ-greedy bandit results [18]. Remark: Propositions 1 and 2 characterize the fixed point each side converges to under stationarity of the other, because both sides learn simultaneously in practice, this is only approximately satisfied at finite t. The two MCSP updates operate on different effective timescales (Ũk,z,t updates once per assignment, while Q(Sk,t , Ak,t ) updates once per MU decision), which is consistent with the twotimescale stochastic approximation framework of [19]; we leave a full joint convergence proof to future work and instead provide extensive empirical evidence of stability in Sec. V. C. Complexity and overhead of ETSL ETP has linear complexity in the number of feasible actions, i.e., O(|Afk,t |) for each MU and its current battery state, with worst-case complexity of O(Z). Note that the Q-table grows with linear space complexity O(LZ) for a fixed number of battery levels L. Likewise, TSLTA has linear complexity in the number of proposals, i.e., O(|Ot |), with worst-case complexity of O(K) and space complexity of O(KZ). Note that for both, the MCSP and the MUs, the communication overhead required for matching is low. The MUs send task offers to the MCSP which contains only the task type and the payment information. The task acceptance and the task rejection messages which
6
TABLE I Simulation Parameters Sensing data size [13] Processed result size [13] sense [13] Sensing time τk,z comm [11] Communication time τk,z Local CPU frequency fklocal [20] Task processing complexity cz [13] MU battery capacity Bmax [21] h [21] Amount of energy harvested Ek,t
U [50, 100] Mbits U [10, 20] Mbits U [60, 180] ms U [0.125, 0.5] s U [1, 2] GHz U [200, 300] 100 units U [0, 15] units
the MCSP transmits back to the respective MUs are also very short. V. Numerical Evaluation For the evaluation, we consider 300 independent Monte Carlo iterations, each with T = 20000 time steps. In the baseline simulation, the number of available MUs is set to K = 100, and the number of available task types Z = 10. The number of available tasks per time step varies between [50, 100]. EH is modeled as a time correlated Markov chain with a harvesting (χ) and a non-harvesting (χ̄) state. The transition probabilities are P (χ|χ) = P (χ̄|χ̄) = 0.6 and P (χ|χ̄) = P (χ̄|χ) = 0.4 [21]. For the different analyses such as MU and task scalability as well as the sensitivity to EH dynamics and the battery capacities, the respective parameters are mentioned exclusively. Therefore, unless specified, the baseline scenario parameters are used in the analysis. The learning rate is α = 0.1, the discount factor is γ = 0.9, and the ϵ-greedy exploration parameters are ϵmax = 1, ϵmin = 0, and θ = 0.999. The number of state levels is set to L = 21. All learning benchmark algorithms use the learning parameters which are determined through independent hyperparameter optimization. The rest of the parameters along with their references are summarized in Table I. For comparison, centralized and decentralized state-ofthe-art benchmarks are used. The centralized approaches assume complete information I. Although such assumption makes them impossible to implement in real applications, they serve as theoretical baselines. Value Iteration (VI): This centralized dynamic programming-based approach computes the value of being in each battery state for each MU and identifies the optimal task proposal and task assignment strategies for MUs and MCSP to maximize their utilities using I. Gale-Shapley (GS) [3]: A centralized approach that provides a myopically stable solution to the dynamic task proposal and task assignment game by maximizing the individual utilities of the MUs and the MCSP in time step t by using I. For the decentralized benchmark algorithms, the MCSP uses the TSLTA algorithm for task assignment [12]. At the MUs’ side, we use: TSLTP [12]: Each MU adopts decentralized gradientbased multi-armed bandit algorithm to learn its task proposal strategy. TSLTP does not account for MU’s
PREPRINT
7
ETSL Energy consumption
3000 2500 2000 1750
0
5000
10000 15000 Time step t
4000
3000 2000 1000 0
0.3
0.2 5000
10000 15000 Time step t
3000 2000 1000
MU=100 MU=150 Number of MUs
(d) MU scalability analysis
0.2 0.1 0.0
0
5000
N=50
N=100 Number of tasks
N=150
(e) Task scalability analysis
10000 15000 Time step t
20000
(c) Competition analysis 3500
3000 2500
3000 2500 2000
2000
0 MU=50
20000
0.3
3500 Social Welfare
5000
4000
TSL
0.4
(b) Energy consumption analysis
5000 Social Welfare
Social Welfare
(a) System performance analysis
Epsilon Greedy 0.5
0
20000
GS
Social Welfare
Social Welfare
3500
DQN
Collision ratio
VI
0.4 0.6 0.8 Harvesting persistence p
(f) Sensitivity: EH dynamics
25
50
100 150 Battery capacity Bmax
200
(g) Sensitivity: battery capacity
Fig. 2. Performance comparison of the ETSL under different metrics and analyses.
energy constraints. Note that TSLTP and TSLTA together constitute the TSL. Deep-Q Network (DQN): A deep reinforcement learning baseline that operates on the same state, action, and reward spaces as the proposed ETP. DQN uses a neural network function approximator to estimate action-value functions. Epsilon-Greedy (EG): A lightweight baseline where each MU learns task utilities using a multi-armed bandit algorithm with a decaying ϵ-greedy exploration strategy and proposes tasks that maximize immediate expected profit. We use achieved social welfare as a comparison metric to evaluate system-level performance of all the benchmarks as shown in Fig.2a. The social welfare is the sum of the utilities of the MUs and the MCSP. VI and GS utilize the complete information I to obtain matching solutions. VI provides an upper bound by considering the impact of spending the energy resources on the future using dynamic programming, whereas, GS finds a myopically stable matching solution ignoring the consequences on the battery. Our ETSL algorithm performs only 7.6% lower than VI and outperforms GS by 13%. This is because the ETSL helps the MUs to consider the future consequences of their task proposal decisions on their battery state, while obtaining an efficient task acceptance strategy for the MCSP based on the proposals. By exploring the task types, the ETSL improves the estimate on task efforts and expected task rewards. ETSL learns the trends in the MU competition over time. The results show that the EG and the TSL achieve 52.5% and 64.9% lower social welfare than our proposed approach, respectively. Moreover, the performance of our proposed ETSL converges to that of the DQN because the considered state-action space of every MU is low-dimensional and discretized, for which tabular
Q-learning provides sample-efficient and stable learning. For a more complex scenario, DQN may exhibit better performance albeit at the cost of higher computational complexity. The EG ignores the collisions while learning the task proposal strategy and thus results in a poor performance. TSL ignores the energy consequences of the MUs and thus performs well as long as energy is available but then deteriorates over time. Fig. 2b shows the total energy consumed per number of completed tasks. Our proposed ETSL performs more tasks by smartly selecting tasks that offer higher utility while also allowing the MUs to stay idle when the available energy is scarce. This is directly reflected in the results where the ETSL consumes on average at least 45.9%, 42.9%, 16.7%, and 9.1% less energy than the EG, TSL, GS, and DQN algorithms respectively and converges to VI’s performance. In Fig. 2c, we compare the number of collisions per total number of task proposals, also known as the collision ratio. A lower collision ratio indicates that the MUs have learned about the competition and are able to make task proposal decisions efficiently. Collisions degrade the performance of the system as resources are wasted during a collision. Note that GS and VI do not have any collisions as they exploit the complete information I. Our proposed ETSL algorithm achieves at least 73.7%, 54.5%, and 9.1% lower collisions compared to the EG, TSL, and DQN. This is because our ETSL constantly updates the task type preferences based on the current battery state, current competition, and the learned acceptance mechanism of the MCSP. This helps the MUs to defer from proposing to some task types from which they are frequently rejected. Evidently, ETSL is able to reduce the collisions over time and moves towards more stable allocations which enhances the overall performance and reduces resource wastage. The
PREPRINT
8
5th–95th percentile confidence intervals in the plots above demonstrate the stability of ETSL’s performance. In Fig. 2d and 2e, we analyze how the benchmark algorithms scale with increasing number of MUs and increasing number of tasks, respectively. We observe that the ETSL exhibits better scalability characteristics by achieving only 7.8% lower social welfare than VI. Moreover, ETSL converges to DQN in all cases, depicting its superior performance with the advantage of lower complexity than the DQN. The other benchmark algorithms struggle to perform with higher number of MUs which increases the competition. Finally in Fig. 2fand Fig. 2g, we perform the sensitivity analysis for the EH process dynamics and the battery capacity of the MUs. In Fig.2f, we consider the probability of persistence, i.e., P (χ|χ) = P (χ̄|χ̄) between the range 0.3 to 0.9 in the steps of 0.1. As the persistence increases, the resulting Markov chain stays in the EH or non-EH state for a long time. This reduced the resulting energy harvesting probability and thus results in a lower performance. Here, the performance of the ETSL is consistent with the VI. Similarly, in Fig.2g, we vary the battery capacity of the MUs between [25, 200]. As the battery capacity increases, the MUs are able to store more energy and sustain longer in the environment for task proposals and executions. Here, the proposed ETSL algorithm shows promising performance across the battery capacities which demonstrates the superior performance of the proposed ETSL algorithm. VI. Conclusion This work addressed the joint task proposal and task assignment problem in MCS-based SaaS for NGNs by formulating it as a dynamic two-sided matching game under incomplete information, where unknown sensing quality, task effort, and the energy limitations of batterypowered MUs affect participant availability and sustainable sensing-resource orchestration. To tackle this challenge, we proposed ETSL, a fully decentralized and lowcomplexity learning framework that enables MUs to learn energy-aware task proposal strategies while allowing the MCSP to learn MU sensing quality for efficient task assignment. By explicitly incorporating energy constraints into the learning and matching process, ETSL supports sustainable system operation while accounting for the individual preferences and utilities of both MUs and the MCSP. Moreover, we use an alternating-freeze approach to show that the proposed ETSL solution converges to a stable matching solution. Simulation results confirm that ETSL outperforms state-of-the-art benchmark algorithms in terms of social welfare, energy efficiency, and collisions, while demonstrating its scalability and suitability for Sensing-as-a-Service in future NGNs. References [1] F. Dong, F. Liu, Y. Cui, S. Lu, and Y. Li, “Sensing as a service in 6g perceptive mobile networks: Architecture, advances, and the road ahead,” IEEE Network, vol. 38, no. 2, pp. 87–96, 2024.
[2] C.-L. Hu, K.-Y. Lin, and C. K. Chang, “Incentive Mechanism for Mobile Crowdsensing With Two-Stage Stackelberg Game,” IEEE Trans. on Services Comput., vol. 16, no. 3, pp. 1904–1918, 2023. [3] Y. Gu, W. Saad, M. Bennis, M. Debbah, and Z. Han, “Matching theory for future wireless networks: fundamentals and applications,” IEEE Commun. Mag., vol. 53, no. 5, pp. 52–59, May 2015. [4] S. V. Kadam and M. H. Kotowski, “Multiperiod matching,” International Economic Review, vol. 59, no. 4, pp. 1927–1947, 2018. [5] Y. Fu, Y. Zhang, Z. Shi, H. Wang, and Y. Liu, “Subband and sensing task allocation for next-generation mobile crowdsensing networks: An optimal framework,” in 2024 IEEE Wireless Commun. and Netw. Conf. (WCNC), 2024, pp. 1–6. [6] K. Liu, S. Peng, W. Gong, B. Zhang, and C. Li, “Hybrid userbased task assignment for mobile crowdsensing: Problem and algorithm,” IEEE IoT Journal, vol. 11, no. 11, pp. 19 589–19 601, 2024. [7] V. Sasireka and S. Ramachandran, “Hybrid optimized task scheduling with multi-objective framework for crowdsensing in mobile social networks,” Peer-to-Peer Netw. and Appli., vol. 17, no. 2, p. 722–738, 2024. [8] E. Wang, D. Luan, Y. Xu, Y. Yang, and J. Wu, “Distributed task selection for crowdsensing: A game-theoretical approach,” IEEE Trans. on Mobile Comput., pp. 1–16, 2024. [9] S. Dongare, A. Ortiz, and A. Klein, “Deep reinforcement learning for task allocation in energy harvesting mobile crowdsensing,” in IEEE Global Commun. Conf., 2022, pp. 269–274. [10] ——, “Federated deep reinforcement learning for task participation in mobile crowdsensing,” in IEEE Global Commun. Conf., 2023, pp. 4436–4441. [11] B. Simon, A. Ortiz, W. Saad, and A. Klein, “Decentralized online learning in task assignment games for mobile crowdsensing,” IEEE Trans. on Commun., vol. 72, no. 8, pp. 4945–4960, 2024. [12] S. Dongare, B. Simon, A. Ortiz, and A. Klein, “Two-sided learning: A techno-economic view of mobile crowdsensing under incomplete information,” in IEEE Int. Conf. on Commun. (ICC), 2024. [13] Y. Huang, H. Chen, G. Ma, K. Lin, Z. Ni, N. Yan, and Z. Wang, “OPAT: Optimized Allocation of Time-Dependent Tasks for Mobile Crowdsensing,” IEEE Trans. on Ind. Inform., vol. 18, no. 4, pp. 2476–2485, Jul. 2022. [14] L. S. Shapley and M. Shubik, “The Assignment Game I: The Core,” Int. J. Game Theory, vol. 1, no. 1, p. 111–130, Dec. 1971. [15] O. Semiari, W. Saad, M. Bennis, and B. Maham, “Caching meets millimeter wave communications for enhanced mobility management in 5g networks,” IEEE Transactions on Wireless Communications, vol. 17, no. 2, pp. 779–793, 2018. [16] C. J. Watkins and P. Dayan, “Q-learning,” Machine learning, vol. 8, no. 3-4, pp. 279–292, 1992. [17] T. Jaakkola, M. I. Jordan, and S. P. Singh, “Convergence of stochastic iterative dynamic programming algorithms,” Neural computation, vol. 6, no. 6, pp. 1185–1201, 1994. [18] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction. MIT press, 2018. [19] V. S. Borkar, “Stochastic approximation with two time scales,” Systems & Control Letters, vol. 29, no. 5, pp. 291–294, 1997. [20] T. Mahn and A. Klein, “A Global Orchestration Matching Framework for Energy-Efficient Multi-Access Edge Computing,” in Proc. of the IEEE Int. Conf. on Cloud Netw. (CloudNet), Cookeville, USA, Nov. 2021, pp. 11–18. [21] S. Dongare, A. Jovovic, W. de Sombre, A. Ortiz, and A. Klein, “Minimizing the age of incorrect information for status update systems with energy harvesting,” in IEEE Int. Conf. on Commun. (ICC), 2024, pp. 5323–5328.