Mechanism Design for Wireless Powered Spatial Crowdsourcing Networks
Yutao Jiao Ping Wang Dusit Niyato Bin Lin Dong In Kim
cs.GT cs.NI eess.SP



Mechanism Design for Wireless Powered Spatial Crowdsourcing Networks
    Yutao Jiao, Ping Wang, Dusit
Niyato, Bin Lin, and Dong In KimCopyright (c) 2019 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@ieee.org. 

Yutao Jiao and Dusit Niyato are with the School of Computer Science
and Engineering, Nanyang Technological University, Singapore. Ping
Wang is with the Lassonde School of Engineering, York University,
Canada. Bin Lin is with the College of Information Science and Technology,
Dalian Maritime University, China. Dong In Kim is with the School
of Information and Communication Engineering, Sungkyunkwan University,
Korea.
    version of December 30, 2023
=============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================


	Wireless power transfer (WPT) is a promising technology to prolong the lifetime of the sensors and communication devices, i.e., workers, in completing crowdsourcing tasks by providing continuous and cost-effective energy supplies. In this paper, we propose a wireless powered spatial crowdsourcing framework which consists of two mutually dependent phases: task allocation phase and data crowdsourcing phase. In the task allocation phase, we propose a Stackelberg game based mechanism for the spatial crowdsourcing platform to efficiently allocate spatial tasks and wireless charging power to each worker. In the data crowdsourcing phase, the workers may have an incentive to misreport its real working location to improve its utility, which causes adverse effects to the spatial crowdsourcing platform. To address this issue, we present three strategyproof deployment mechanisms for the spatial crowdsourcing platform to place a mobile base station, e.g., vehicle or robot, which is responsible for transferring the wireless power and collecting the crowdsourced data. As the benchmark, we first apply the classical median mechanism and evaluate its worst-case performance. Then, we design a conventional strategyproof deployment mechanism to improve the expected utility of the spatial crowdsourcing platform under the condition that the workers' locations follow a known geographical distribution. For a more general case with only the historical location data available, we propose a deep learning based strategyproof deployment mechanism to maximize the spatial crowdsourcing platform's utility. Extensive experimental results based on synthetic and real-world datasets reveal the effectiveness of the proposed framework in allocating tasks and charging power to workers while avoiding the dishonest worker's manipulation.



Spatial crowdsourcing, deep learning, wireless power transfer, facility
location, generalized median mechanism, automated mechanism design





§ INTRODUCTION


Crowdsourcing is becoming a popular paradigm which efficiently completes tasks and solves problems by aggregating information and intelligence from crowds. Integrated with advanced sensing and communication techniques, mobile devices can help complete diverse location-aware tasks, such as the large-scale data acquisition and analysis in real-time traffic monitoring[An example is the crowdsourcing-based traffic and navigation app “Waze” (<https://www.waze.com>).] or weather monitoring and forecasting <cit.> at different places. By focusing on the geospatial data, a new paradigm called spatial crowdsourcing (SC) <cit.> has received increasing attention in the last few years <cit.>. Typically, there are three entities in the SC system, including an online SC platform, requesters and workers. As a core component of the SC ecosystem, the SC platform is a broker which allows requesters to post tasks and recruits workers to complete them. Each employed worker then stays at or travels to its target task area to collect and transmit the requested data back. Since the relationship between the SC platform and the workers are incentive-driven, we study the interactions between them to understand and develop an effective mechanism to enable sustainable and efficient operations of the SC systems.

Most existing work assumes that there is always reliable communication infrastructure and enough energy available for workers to complete the data transmission. However, this assumption may not be realistic, especially when the workers have to perform tasks in remote areas without a wireless base station. Moreover, workers can be battery-powered wireless mobile devices. Their energy constraint limits the working time and ultimately affects the task completion. Fortunately, some studies <cit.> in wireless powered sensor networks have illustrated the feasibility of using wireless power transfer (WPT) <cit.> in sensing data collection to prolong the lifetime of sensors. Given this, we consider a paradigm called wireless powered spatial crowdsourcing where the SC platform deploys a mobile base station (BS), e.g., robots, drones or vehicles, to assist the data collection. The mobile BS serves as the infrastructure for communication and wireless power transfer. A typical scenario suitable for applying this paradigm is the information collection in an emergency rescue mission. The requester can be the relief headquarter which needs the SC platform to organize workers to continually transmit the live video or environmental monitoring data from the target task area, e.g., seismic site. These data and data analytics results will significantly help to increase the efficiency of succour. Meanwhile, those workers with battery-powered devices will need wireless charging due to the possible power outage.

To ensure successful and stable operations of the crowdsourcing system, designing an incentive mechanism that stimulates workers' participation and efficiently allocates tasks is essential. A number of studies have proposed mechanisms satisfying various requirements, such as profitability, strategyproofness, i.e., truthfulness, and individual rationality <cit.>. Nevertheless, in wireless powered spatial crowdsourcing networks, the reward offered by the SC platform to workers can be the wireless power supply, which is location-dependent. The major difference from those existing mechanisms, the incentive of which is based on the monetary reward[The monetary reward can be tokens, virtual money, reputation, etc.]. The difference introduces a few major issues for incentive mechanism design in wireless powered crowdsourcing networks, and the following questions have to be answered. First, what is the optimal total charging power supply for the SC platform to configure for maximizing its utility? The SC platform can encourage workers to transmit sensed data at a higher transmission rate, i.e., more collected data per unit time, but it is at the cost of a higher power supply. Second, how to allocate the tasks and charging power to workers which are spatially distributed in the target task area? The allocation is based on not only each worker's sensing cost but also the working location, which affects the communication cost and transferred power. Note that the workers' sensing cost and working location can be private information and unknown to the SC platform. Lastly, how to deploy the mobile BS taking the workers' strategic behaviours into account? Since the workers' working locations are private, workers need to report their locations before the mobile BS chooses the best location to deploy.

Under the assumption of rationality, a worker may dishonestly misreport its location to increase its utility while reducing the SC platform's utility. Figure <ref> shows such an example. In the task area, there are one dishonest worker at location L_A and two honest workers respectively at locations L_B and L_C. The SC platform would place the mobile BS at L_M for optimal utility if all the workers report true locations L_A,  L_B and L_C. However, the dishonest worker has the incentive to report a fake location L'_A, so that according to the reported locations L'_A,  L_B and L_C, the mobile BS will be deployed at L'_M. In this case, the dishonest worker at L_A can be closer to the mobile BS and then enjoy more transferred power from the mobile BS while consuming less power to transmit its sensed data. This inevitably increases other workers' and SC platform's energy consumption and damages their utility. Most current studies on incentive mechanisms for the crowdsourcing system have not addressed such issue yet.

In this paper, we propose a strategyproof and energy-efficient SC framework which jointly solves the problems of task and wireless charging power allocation as well as the truthful working location reporting. In the framework, there are two phases: task allocation phase and data crowdsourcing phase. In the task allocation phase, the SC platform determines and announces a fixed total charging power supply. Each worker interested in participating needs to choose and submits the preferred crowdsourcing plan, i.e., its data transmission rate to the SC platform. In return, they can obtain the corresponding portion of the supplied charging power from the SC platform. We use the Stackelberg game to model the interactions between workers and the SC platform, in which each worker's transmission rate and allocated power can be determined. In the data crowdsourcing phase, the mobile BS requests for workers' working locations. Based on the Moulin's generalization median rule <cit.>, we present three strategyproof mobile BS deployment mechanisms for the mobile BS to determine its service location. The first one is the classical median mechanism. The other two mechanisms are designed from the Bayesian viewpoint. One is a conventional mechanism which assumes that each worker's working location follows a priori known distribution. For more general scenarios with only historical working location data available, we resort to the advanced deep learning technique to develop another mechanism for higher robustness and larger utility. 


The major contributions of this paper can be summarized as follows: 
 
	
  * We propose a strategyproof and energy-efficient framework for implementing the wireless powered spatial crowdsourcing. The task allocation phase and the data crowdsourcing phase jointly coordinate the task/power allocation and the mobile BS deployment to maximize the SC platform's utility. 
	
  * We propose an incentive mechanism for the task and wireless power transfer allocation based on the Stackelberg game model in the task allocation phase. We prove that a unique Nash equilibrium exists among workers' strategies, i.e., the data transmission rates, and the Stackelberg equilibrium can be efficiently calculated to optimize the SC platform's utility. 
	
  * In the data crowdsourcing phase, we first present two strategyproof mobile BS deployment mechanisms to prevent the dishonest worker's manipulation while maximizing the SC platform's utility under different scenarios respectively with 1) no prior information 2) prior location distribution. Moreover, for the complex scenario with only historical working location data available, we utilize the deep learning technique and construct a novel deep neural network to design a strategyproof deployment mechanism.
	
  * Based on synthetic and real-world datasets, the experimental results illustrate the effectiveness of the proposed incentive mechanisms in assisting the SC platform in allocating the task and charging power efficiently.  In particular, the deep learning based mechanism shows significant improvement in performance and stability compared with the conventional mechanism. 
 

To the best of our knowledge, this is the first work that investigates the incentive mechanism design in wireless powered spatial crowdsourcing and, for the first time, the deep learning method to address the problem of potential working location misreporting in spatial crowdsourcing systems. 

The rest of the paper is organized as follows. In Section <ref>, we discuss the related work and motivations in detail. In Section <ref>, we describe the system model of wireless powered spatial crowdsourcing. Section <ref> proposes the task and charging power allocation mechanism. In Section <ref>, we present three mechanisms for strategyproof mobile BS deployment in the data crowdsourcing phase. In Section <ref>, we provide the experimental results. Finally, we conclude the paper in Section <ref>. 



§ RELATED WORK AND MOTIVATIONS


There have already been studies about the incentive mechanisms in crowdsourcing systems <cit.>. The authors in <cit.> proposed platform-centric and user-centric incentive mechanisms, respectively based on the Stackelberg game and the reverse auction. Each worker is free to determine its own strategy, i.e., working time or cost, for a reward. Some desirable economic properties, such as strategyproofness[We use “strategyproofness” and “truthfulness” interchangeably in this paper.] and individual rationality, are guaranteed in the auction. In <cit.>, the authors designed a reputation-based incentive mechanism and used the repeated gift-giving game in analyzing the interaction between task requesters and workers. 

 The authors in <cit.> made use of the historical data about the workers' visiting records to the task locations to investigate workers' skills. For crowdsourcing in wireless-powered task-oriented networks, a game-based distributive incentive mechanism was proposed in <cit.> for reducing energy consumption while ensuring task completion. Particularly, in <cit.>, the authors also used the energy as the reward and introduced an energy bank as the trusted medium of the energy service exchange to avoid using the unreliable and unspecific monetary reward among the workers. However, to the best of our knowledge, most of the existing studies on the crowdsourcing rely on the monetary transfer, i.e., payment, to guarantee the property of truthfulness in reporting private valuations. Moreover, none of the existing work has addressed the issue that a dishonest worker could possibly misreport its working location and manipulate the crowdsourcing system in the data crowdsourcing phase, which cannot be solved using monetary transfer. The study of approximate mechanism design without money was initialized in <cit.>, where the authors discussed the strategyproof single facility deployment mechanism in one-dimensional space. The authors in <cit.> designed two neural network structures, including MoulinNet and RegretNet, to solve the strategyproof multiple facilities location problem in one-dimensional space. Inspired by these works, we propose mobile BS deployment mechanisms for the SC system, which can achieve high utility while guaranteeing the strategyproofness without any money or reward transfer.



§ SYSTEM MODEL: WIRELESS POWERED SPATIAL CROWDSOURCING MARKET

Figure <ref> depicts the wireless powered spatial crowdsourcing system model where there are three entities, including the requesters, the SC platform residing in the cloud and the workers with mobile sensing devices. The workers can be human, unmanned vehicles or robots. Initially, the requesters publish spatial tasks with requirements, such as the target task area, the task duration, and the sensed data type. Then, the SC platform advertises the task information to workers on behalf of the requesters and collects the crowdsourced or sensed data. As shown in Fig. <ref>, we denote by 𝒩={1,…,N} the set of workers and denote by A_t the task area on a Cartesian coordinate plane. The worker i's working location L_i is described by a 2-tuple, i.e., L_i∈𝒩=(x_i,y_i). We use L_M=(x_M,y_M)∈A_t⊆ℝ^2 to represent the deployed mobile BS's service location projected on the XY-plane and use h to denote its height. We assume that each worker knows its preferred area to work, i.e., working area, such as the area near to its commuting route or around home <cit.>. In the task area, worker i has its own working area A_i and its working location L_i falls in this area, i.e., L_i∈A_i⊆A_t⊆ℝ^2. In this section, we first model the power cost of communication and sensing for the mobile BS and workers in the data crowdsourcing phase. Then, we elaborate on both the task allocation phase and the data crowdsourcing phase and present the problem formulations. 




 §.§ Power cost model




  §.§.§ Worker's power cost


We consider a frequency division duplexing (FDD) system where sufficient
channels are available to ensure interference-free transmission. Note
that with this assumption, we can better focus on the incentive mechanism
design between the SC platform and workers. Furthermore, we assume
that the communication channels are dominated by line-of-sight (LoS)
links. Given the mobile BS's service location L_M, we
can write the worker i's transmission rate according to Shannon's
formula as follows:

    r_i    =Blog_2(1+P_i^tδ/σ^2d_i^α)=Blog_2(1+P_i^tg/d_i^α)

where g=δ/σ^2 is the channel gain to noise ratio (CNR), δ represents the corresponding channel power gain at the reference distance of 1 meter, σ^2 is the noise power at the receiver mobile BS, B is the channel bandwidth, P_i^t is worker i's data transmission power, and α≥2 is the path-loss exponent. In addition, we define 

    d_i    =d_i(L_M)=d((x_i,y_i),(x_M,y_M))
        =√((x_i-x_M)^2+(y_i-y_M)^2+h^2)

as the Euclidean distance between the worker i and the mobile BS. Again, h is the height of the mobile BS. Hereby, we can derive the worker i's transmission power as

    P_i^t=(2^r_i/B-1)/gd_i^α.

Besides the power used to transmit data, for the worker i, we have the power cost function of data sensing P_i^s=b_ir_i where b_i is the energy cost per bit. Here, the power cost of data sensing is linear to the sampling rate <cit.>, i.e., the transmission rate. Therefore, the worker i's total power cost P_i can be expressed as follows:

    P_i    =P_i^t+P_i^s=(2^r_i/B-1)/gd_i^α+b_ir_i.





  §.§.§ Power cost of the mobile base station


The mobile BS consumes energy mainly for WPT to workers. If the charging power transferred to the worker i is P_i^c, the mobile BS at the service location has to consume power P_i^c' as follows <cit.>:

    P_i^c'    =P_i^cd_i^α/ηΓ=P_i^cd_i^ακ,

where κ=1/ηΓ, 0<η<1 denotes the receiver energy conversion efficiency, Γ denotes the combined antenna gain at the reference distance of 1 meter.



 §.§ Utility function in the wireless powered spatial crowdsourcingsystem


We define the utility of the crowdsourced data based on the transmission rate, which combines two common metrics, i.e., the data size and timeliness. For example, the requesters may perform the data analysis and prediction based on the real-time crowdsourced data. Higher data transmission rate means that the requesters can process more data during a unit time and yield more accurate prediction results. The utility of the crowdsourced data is equivalent to the utility of the SC task completion. The utility q of data collected from the SC task completion is calculated by

    q(𝐫)     =a_1log(1+∑_i∈𝒩log(1+a_2r_i)),

where 𝐫=(r_1,r_2,…,r_N) is the transmission rate vector reported by workers, a_1 and a_2 are parameters. The inner logarithmic function reflects the SC platform’s diminishing return of the worker i's contribution, and the outer logarithmic function reflects the diminishing return of all participating workers' contributions <cit.>. In this paper, the mobile BS serves as a dedicated power transmitter which applies the directional beamforming technique <cit.>. Taking the power cost of WPT (<ref>) into consideration, the SC platform's utility function can be expressed as <cit.>

    u_m    =q(𝐫)-∑_i∈𝒩P_i^c'
        =a_1log(1+∑_i∈𝒩log(1+a_2r_i))-∑_i∈𝒩P_i^cd_i^ακ.

Similarly, we obtain the worker i's utility function as

    u_i    =P_i^c-P_i=P_i^c-(2^r_i/B-1)/gd_i^α-b_ir_i.





 §.§ The procedure of wireless powered spatial crowdsourcing


Note that we aim to maximize the SC platform's utility. Recalling the utility functions in (<ref>) and (<ref>), how to determine each worker's transmission rate and charging power as the reward and where to deploy the mobile BS are two critical issues for utility maximization. 



  §.§.§ Task allocation phase


Before the mobile BS departs to collect data and workers execute the assigned tasks, the SC platform announces a total charging power supply P_c (P_c=∑_j∈𝒩P_j^c) to assist workers in the data crowdsourcing. The charging power P_i^c transferred to worker i is proportional to its contribution (the data transmission rate), i.e., P_i^c=r_i/RP_c=r_i/∑_j∈𝒩r_jP_c. Based on the sensing tasks and the other workers' responses, each worker reports the preferred data rate r_i to maximize its own utility. In practice, the SC platform may serve as a relay to receive and broadcast the workers' responses. As workers have not determined the suitable working place and perform the allocated task, they are exposed to uncertainty of working location L_i and the mobile BS's service location L_M which are only known in the next data crowdsourcing phase. We assume that the workers are risk-averse, which means that they choose to minimize the uncertainty and avoid any possible loss in the future. This concept can be found in the well-known prospect theory <cit.>. A common example is that a majority of people prefer to deposit money at the bank for safekeeping and low return instead of buying financial products with a high risk of loss. Note that given the power supply and other workers' transmission rates, the worker i's utility function in (<ref>) is monotonically decreasing with d_i. Since the worker i knows its working area A_i and the task area A_t, it can obtain the maximum value of d_i, i.e., D_i=max_L_M∈A_t,L_i∈A_id_i. Therefore, if the worker i plans the transmission rate r_i for the worst case where D_i is its distance from the mobile BS, the worker i will achieve the utility which is not lower than the worst case in the data crowdsourcing phase. In addition, we use 𝐫_-i=(r_1,…,r_i-1,r_i+1,…,r_N) to denote the reported transmission rate vector for all workers except the worker i. Hereby, the worker i's utility function in the task allocation phase can be expressed as

    u̅_i(r_i,𝐫_-i,P_c)=r_i/∑_j∈𝒩r_jP_c-(2^r_i/B-1)/gD_i^α-b_ir_i.

The SC platform's utility in (<ref>) is rewritten as

    u̅_m    (P_c,𝐫)=a_1log(1+∑_i∈𝒩log(1+a_2r_i))
               -∑_i∈𝒩r_i/∑_j∈𝒩r_jP_cD_i^ακ.





  §.§.§ Data crowdsourcing phase


In the task allocation phase, the total charging power supply P_c, each worker's allocated charging power P_i^c and transmission rate r_i have been determined. Each worker decides the working location according to the task and its available working area. For example, if the task requires collecting data about road traffic condition, workers may choose the roadside or crossing. As our paper mainly focuses on establishing a spatial crowdsourcing market with wireless energy transfer and designing relevant trading mechanisms, how to choose a good working location is beyond our scope. Once working locations are decided, they will travel to the working locations and the SC platform sends out the mobile BS to serve the workers. However, the mobile BS has to know each worker's working location. Then, it can determine the service location L_M for maximizing the SC platform's utility. The worker i's and the SC platform's utility functions in the data crowdsourcing phase can be respectively expressed as

    û_i(L_M)=r_i/∑_j∈𝒩r_jP_c-(2^r_i/B-1)/gd_i^α(L_i,L_M)-b_ir_i

 and 

    û_m    (L_M)=a_1log(1+∑_i∈𝒩log(1+a_2r_i))
               -∑_i∈𝒩r_i/∑_j∈𝒩r_jP_cd_i^α(L_i,L_M)κ.

To make workers reveal their private working location L_i, the mobile BS organizes the following voting process on the spot. 


  * The mobile BS first broadcasts its deployment mechanism, i.e, the
mechanism or rule to place the mobile BS according to the locations
reported by workers, to the task area. 

  * Once receiving the notification about the deployment mechanism, each
worker sends its working location L_i to the mobile BS.

  * Based on the collected locations and the deployment mechanism, the
service location L_M is calculated for the mobile BS
to deploy.

Let 𝖬 denote the applied deployment mechanism which takes the workers' reported working location vector 𝐋=(L_1,…,L_i,…,L_N) as input and outputs the mobile BS's service location L_M, i.e., L_M=𝖬(𝐋). During the above voting process, a worker i may have an incentive to improve its own utility in (<ref>) by misreporting its true working location L_i. To make the location voting process robust and implementable, our designed mobile BS deployment mechanism should have the property of strategyproofness (truthfulness), which is defined as follows: 

	(Strategyproofness) Regardless of other workers' reported locations, a worker i cannot increase the utility by misreporting its working location L_i. Formally, given a deployment mechanism 𝖬 and a misreported location L'_i, we have 

    û_i(𝖬((L_i,𝐋_-i)))≥û_i(𝖬((L'_i,𝐋_-i))) ∀ L_i'≠ L_i

where 𝐋_-i is the vector containing all workers' working
locations except the worker i's.




  §.§.§ Mutual Dependence


The task allocation phase and the data crowdsourcing phase are mutually dependent. On the one hand, each worker's transmission rate in data crowdsourcing is determined from the task allocation phase. On the other hand, a prerequisite of the successful charging power allocation is to guarantee that the data crowdsourcing phase cannot be strategically manipulated. The untruthful or dishonest worker may overestimate its risk preference, i.e., the maximum distance D_i, due to its deliberate manipulation. Both the two phases affect the efficient use of the power as well as all the participants' utilities. 



§ TASK AND WIRELESS TRANSFERRED POWER ALLOCATION MECHANISM


We utilize the Stackelberg game approach <cit.> to analyze the model introduced in the task allocation phase (Section <ref>). There are two levels in the Stackelberg game. In the first (upper) level, the SC platform acts as the leader which strategizes and announces the total charging power supply P_c. In the second (lower) level, each worker is the follower which determines the strategy, i.e., the preferred transmission rate r, to maximize its utility. Mathematically, the SC platform chooses the strategy P_c by solving the following optimization problem:

    (P1) max_P_c≥0u̅_m(P_c,𝐫).

Meanwhile, the worker i makes the decision on its reported r_i
to solve the following problem:

    (P2) max_r_i≥0u̅_i(r_i,𝐫_-i,P_c).

The objective of the Stackelberg game is to find the Stackelberg
Equilibrium (SE). We next introduce the concept of the SE for our
proposed model.

	(Stackelberg Equilibrium) Let P̃_c be a solution for Problem P1 and 𝐫̃ be a solution for Problem P2 of the workers. Then, a point (P̃_c,𝐫̃) is the SE for the proposed Stackelberg game if it satisfies the following conditions:

    u̅_m(P̃_c,𝐫̃)≥u̅_m(P_c,𝐫̃),


    u̅_i(r̃_i,𝐫̃_-i,P̃_c)≥u̅_i(r_i,𝐫̃_-i,P̃_c),

for any (P_c,𝐫) with P_c≥0 and 𝐫≽0.


In general, the first step to obtain the SE is to find the perfect Nash Equilibrium (NE) <cit.> for the non-cooperative transmission Rate Determination Game (RDG) in the lower level. Then, we can optimize the strategy of the SC platform at the upper level. Given a fixed P_c, the NE is defined as a set of strategies 𝐫^ne=(r_1^ne,…,r_N^ne) that no worker can improve utility by unilaterally changing its own strategy while other workers' strategies are kept unchanged. Since workers are rational and not willing to provide service for a negative utility, they shall set r_i=0 if u̅_i(r_i,𝐫_-i,P_c)≤0. To analyze the NE, we introduce the concept of the concave game and the theorem about the existence and uniqueness of NE in the concave game. 

	(Concave game <cit.>) A game is called concave if each worker i chooses a strategy r_i to maximize utility u̅_i, where u̅_i is concave in r_i. 


	(<cit.>) Concave games have (possibly multiple) Nash Equilibrium. Define N× N matrix function 𝐇 in which 𝐇_ij=∂^2u̅_i/∂ r_i∂ r_j,i,j∈𝒩. Let  If 𝐇+𝐇^T is strictly negative definite, then the Nash equilibrium is unique.


Hereby, we calculate the first-order and second-order derivatives of the worker i's utility function u̅_i(r_i,𝐫_-i,P_c) with respect to r_i as follows: 

    ∂u̅_i/∂ r_i=P_c∑_k∈𝒩_-ir_k/(∑_j∈𝒩r_j)^2-D_i^αln2/B2^r_i/B-b_i,


    ∂^2u̅_i/∂ r_i^2=-2P_c∑_k∈𝒩_-ir_k/(∑_k∈𝒩r_k)^3-D_i^αln^22/B^22^r_i/B.

Since ∂^2u̅_i/∂ r_i^2<0, u̅_i(r_i,𝐫_-i,P_c) is a strictly concave function with respect to r_i. Then, the non-cooperative RDG is a concave game and the NE exists when ∑_j∈𝒩_-ir_j>0. Otherwise the worker i's best strategy does not exist. Given any P_c>0 and any strategy profile 𝐫_-i (∑_j∈𝒩_-ir_j>0), the worker i's best response strategy γ_i exists and is unique. To prove the uniqueness of the NE, we also calculate the second-order mixed partial derivative of u̅_i for i∈𝒩 with respect to r_j∈𝒩_-i as follows: 

    ∂^2u̅_i/∂ r_j^2=2r_i/(∑_j∈𝒩r_j)^3P_c,  ∂^2u̅_i/∂ r_i∂ r_j=r_i-∑_k∈𝒩_-ir_k/(∑_k∈𝒩r_k)^3P_c,

where ∂^2u̅_i/∂ r_j^2≥0 and ∂^2u̅_i/∂ r_i∂ r_j≤0 if r_i≤∑_k∈𝒩_-ir_k, ∀ i∈𝒩. Then, we have the specific expression of the matrix function 𝐇 defined in Theorem <ref>. Furthermore, the matrix function 𝐇+𝐇^T can be decomposed into a sum of several N× N matrix functions:
𝐇+𝐇^T=𝐔+𝐕+∑_k∈𝒩𝐂^k,
where 𝐔_ij=
0     i≠ j
∂^2u̅_i/∂ R_i^2    i=j, 𝐕_ij=∑_k∈𝒩∂^2u̅_k/∂ r_i∂ r_j
and 𝐂_ij^k=0     i=k or j=k

-∂^2u̅_k/∂ r_i∂ r_j    otherwise. Let 𝐈 denote the sum of 𝐂_ij^k over 𝒩,
i.e., 𝐈=∑_k∈𝒩𝐂^k. Since ∂^2u̅_i/∂ r_i^2<0
and ∂^2u̅_i/∂ r_i∂ r_j≤0 , if r_i≤∑_k∈𝒩_-ir_k, ∀ i∈𝒩, we can find that 𝐔 is strictly negative definite, and 𝐕 and 𝐈 are negative semi-definite. Thus, 𝐇+𝐇^T is proved to be strictly negative definite which shows the NE in the RDG is unique. In other words, once the SC platform decides a strategy P_c, the workers' strategies, i.e., the transmission rates, will be uniquely determined. We then can use the iterative best response <cit.> to find the SE point P̃_c in the first level, i.e., the optimal strategy of P_c.



§ MOBILE BS DEPLOYMENT MECHANISMS IN DATA CROWDSOURCING PHASE 


Given the SE points (P̃_c,𝐫̃) calculated from the task allocation phase, we use 𝒩̂={1,…,N̂} (break ties randomly) to represent the set of employed workers whose transmission rate r̃_i>0. Hence, the specific problems for the SC platform in the data crowdsourcing phase is

    max_L_M∈A_tû_m(L_M)     =a_1log(1+∑_i∈𝒩log(1+a_2r̃_i))
              -∑_i∈𝒩̂r̃_i/∑_j∈𝒩̂r̃_jP̃_̃c̃d_i^α(L_i,L_M)κ.

Based on workers' reported working locations, the SC platform decides the mobile BS's location to maximize its utility. For simplicity, we write the equivalent problems as follows:

    min_L_M∈A_tl̂_m(L_M)     =∑_i∈𝒩̂r̃_i/∑_j∈𝒩r̃_jP̃_̃c̃d_i^α(L_i,L_M)κ,

where l̂_m(L_M) is the crowdsourcing cost of SC platform. Minimizing the SC platform's crowdsourcing cost is equivalent to maximizing its utility. Similarly, the worker i's utility and crowdsourcing cost can be respectively expressed as 

    û_i(L_M)     =r̃_i/∑_j∈𝒩̂r̃_jP̃_̃c̃-(2^r̃_i/B-1)/gd_i^α(L_i,L_M)-b_ir̃_i,
    l̂_i(L_M)     =(2^r̃_i/B-1)/gd_i^α(L_i,L_M).


To address the mobile BS's location problem introduced in Section <ref>, we first present the classical median mechanism and analyze its worst-case performance. Then, we propose a conventional mechanism to improve the utility of the SC platform in expectation. For more general scenarios and achieving better performance, we also propose a deep learning based strategyproof mechanism. The design rationale of the deep neural network is the Moulin's generalized median mechanism.



 §.§ Conventional strategyproof mechanism under Bayesian settings 


We first introduce an important concept of 2-dimensional single-peaked preference for the discussed problem.


	(2-dimensional single-peaked preference <cit.>) Let 𝐋_M be the set of possible mobile BS's service locations output by the deployment mechanism 𝖬 on the XY-plane where X and Y are respectively a one-dimensional axis. The worker i’s preference for the mobile BS's location is 2-dimensional single-peaked with respect to (X,Y) if 1) there is a single most-preferred location outcome L̃_i^M∈𝐋_M, and 2) for any two outcomes L'_M,L”_M∈𝐋_M, L'_M≽_iL”_M whenever L”_M<_ρL'_M<_ρL̃_i^M or L̃_i^M<_ρL'_M<_ρL”_M for ∀ρ∈{X,Y}, i.e., both X and Y axes. 


In the above definition, L'_M≽_iL”_M means that L'_M is preferred by worker i to L”_M. “<_ρ” is a strict ordering by worker i on the dimension ρ. An explanation of this condition is that L'_M is preferred by worker i to L”_M as long as L'_M is nearer to its most-preferred location L̃_i^M on each dimension. 



	In the data crowdsourcing phase, the worker's preference for the mobile BS's service location is 2-dimensional single-peaked.


We first expand the worker i's crowdsourcing cost function given in (<ref>) as l̂_i(L_M)=l̂_i(x_M,y_M)=(2^r̃_i/B-1)/g((x_i-x_M)^2+(y_i-y_M)^2+h^2)^α/2. We can then show that l̂_i is convex with respect to (x_M,y_M) and there is a unique optimal solution L̃_i^M=(x_i,y_i) to minimizing the cost. In other words, the worker i's most preferred mobile BS's service location is its working location, i.e., L̃_i^M=L_i=(x_i,y_i), which satisfies the first condition in Definition <ref>. In the task area A_t, we randomly choose two locations L'_M=(x'_M,y'_M), L”_M=(x”_M,y”_M)∈A_t. Note that the convexity of l̂_i guarantees the convexity on one dimension if fixing the variable on the other dimension is fixed. L”_M<_XL'_M<_XL̃_i^M implies that l̂_i((x_i,y))<l̂_i((x'_M,y))<l̂_i((x”_M,y)) for any y on axis Y and then |x_i-x'_M|<|x_i-x”_M|. We can have the similar implication from L”_M<_YL'_M<_YL̃_i^M. If L”_M<_XL'_M<_XL̃_i^M and L”_M<_YL'_M<_YL̃_i^M are both satisfied, we can have (x_i-x'_M)^2+(y_i-y'_M)^2<(x_i-x”_M)^2+(y_i-y”_M)^2 and thus l̂_i(L'_M)=l̂_i((x'_M,y'_M))<l̂_i(L”_M)=l̂_i((x”_M,y”_M)). Therefore, the worker i prefers L'_M to L”_M, i.e., L'_M≽_iL”_M, which proves the condition 2 in Definition <ref> and completes the proof.



(Moulin's one-dimensional
generalized median mechanism <cit.>) A mechanism 𝖬
for single-peaked preferences in a one-dimensional space is strategyproof
and anonymous if and only if there exist N̂+1 constants τ_1,…,τ_N̂+1∈ℝ∪(-∞,+∞)
such that: 

    𝖬(𝐋^M)=median(L̃_1^M,…,L̃_N^M,τ_1,…,τ_N+1)

where 
An outcome
rule 𝖬 is anonymous, if for any permutation T'
of T, we have 𝖬(T')=𝖬(T)
for all T.



(Multi-dimensional
generalized median mechanism <cit.>) A mechanism for
multi-dimensional single-peaked preferences in a multi-dimensional
space is strategyproof and anonymous if and only if it is an m-dimensional
generalized median mechanism, which straightforwardly applies the
one-dimensional generalized median mechanism on each of the m dimensions.




A straightforward benchmark mechanism is the median mechanism <cit.>, as shown in Algorithm <ref>. We simply name it as MED mechanism, i.e., 𝖬_MED. This algorithm directly computes the median of workers' reported locations as the mobile BS's service location. Apparently, it is a special case of the multi-dimensional generalized median mechanism, so it is strategyproof. We next analyze its performance by comparing it with the optimal mechanism 𝖬_OPT which achieves the maximum utility of the SC platform without considering incentive constraints. Let r̃_max and r̃_min respectively denote the maximum and the minimum transmission rate among workers, i.e., r̃_max=max(𝐫̃),r̃_min=min(𝐫̃). 



	The benchmark MED mechanism 𝖬_MED has an approximation ratio its worst-case performance for minimizing the SC platform's crowdsourcing cost can guarantee l̂_m(𝖬_MED(L))≤2^α/2N̂^α/2-1r̃_max/r̃_minl̂_m(𝖬_OPT(L)).


We expand the SC platform's utility function in (<ref>)
as follows:

    l̂_m((x_M,y_M))
        =P̃_cκ/∑_j∈𝒩̂r̃_j∑_i∈𝒩̂(r̃_i^2/α(x_i-x_M)^2+(y_i-y_M)^2+h^2)^α/2.

Let x_med,x and y_med,y respectively denote the median and mean of 𝐱=(x_1,…,x_N̂) and 𝐲=(y_1,…,y_N̂). Also, we use (x_opt,y_opt) to denote the optimal solution to maximizing the utility function in (<ref>), i.e., 𝖬_OPT(L)=(x_opt,y_opt). We also note that the optimal solution to minimizing the ∑_i∈𝒩̂r̃_i^2/α((x_i-x_M)^2+(y_i-y_M)^2+h^2) is (x^*,y^*) where x^*=∑_i∈𝒩̂r̃_i^2/αx_i/∑_i∈𝒩̂r̃_i^2/α and y^*=∑_i∈𝒩̂r̃_i^2/αy_i/∑_i∈𝒩̂r̃_i^2/α. As r̃_min≤r̃_i, we have

    r̃_min^2/α∑_i∈𝒩̂((x_i-x)^2+(y_i-y)^2+h^2)
       ≤∑_i∈𝒩̂r̃_i^2/α((x_i-x^*)^2+(y_i-y^*)^2+h^2).

According to <cit.>, we have ∑_i∈𝒩̂(x_i-x_med)^2≤2∑_i∈𝒩̂(x_i-x)^2 and ∑_i∈𝒩̂(y_i-y_med)^2≤2∑_i∈𝒩̂(y_i-y)^2. Then, we can verify that 

    r̃_min^2/α∑_i∈𝒩̂((x_i-x_med)^2+(y_i-y_med)^2+h^2)
       ≤2r̃_min^2/α∑_i∈𝒩̂((x_i-x)^2+(y_i-y)^2+h^2),
       r̃_min(∑_i∈𝒩̂((x_i-x_med)^2+(y_i-y_med)^2+h^2))^α/2
       ≤2^α/2r̃_min(∑_i∈𝒩̂((x_i-x)^2+(y_i-y)^2+h^2))^α/2
       ≤2^α/2r̃_min(∑_i∈𝒩̂((x_i-x^*)^2+(y_i-y^*)^2+h^2))^α/2
       ≤2^α/2(∑_i∈𝒩̂r̃_i^2/α((x_i-x^*)^2+(y_i-y^*)^2+h^2))^α/2.

Since α≥2, we can prove that

    r̃_min∑_i∈𝒩̂((x_i-x_med)^2+(y_i-y_med)^2+h^2)^α/2
    ≤r̃_min(∑_i∈𝒩̂((x_i-x_med)^2+(y_i-y_med)^2+h^2))^α/2.

Hence, based on Theorem 1 in <cit.> and the fact that r̃_i≤r̃_max and α/2≥1, we can obtain

    2^α/2(∑_i∈𝒩̂r̃_i^2/α((x_i-x^*)^2+(y_i-y^*)^2+h^2))^α/2
       ≤2^α/2(∑_i∈𝒩̂r̃_i^2/α((x_i-x_opt)^2+(y_i-y_opt)^2+h^2))^α/2
       ≤2^α/2r̃_max(∑_i∈𝒩̂((x_i-x_opt)^2+(y_i-y_opt)^2+h^2))^α/2
       ≤2^α/2N̂^α/2-1r̃_max∑_i∈𝒩̂((x_i-x_opt)^2+(y_i-y_opt)^2+h^2)^α/2.

Combining the above inequalities, we have

    P̃_cκ/∑_j∈𝒩̂r̃_j∑_i∈𝒩̂((x_i-x_med)^2+(y_i-y_med)^2+h^2)^α/2


    ≤2^α/2N̂^α/2-1r̃_max/r̃_minP̃_cκ/∑_j∈𝒩̂r̃_j
           ∑_i∈𝒩̂((x_i-x_opt)^2+(y_i-y_opt)^2+h^2)^α/2.

Finally, we can conclude that l̂_m(𝖬_MED(L))≤2^α/2N̂^α/2-1r̃_max/r̃_minl̂_m(𝖬_OPT(L)).





However, we find that the MED mechanism can be arbitrarily inefficient, especially when the wireless channel path-loss and the number of workers are large. Thanks to the workers' historical location data kept by the SC platform, it is possible to design mechanisms that achieve higher utility in expectation. Each worker's location (x_i,y_i) follows a distribution whose joint continuous probability density function (PDF) is 𝒫_i on its working area A_i, i.e., (x_i,y_i)∼𝒫_i for i=1,…,N̂. With a slight abuse of notation, let the probability density function of 𝒫_i at a pair of real numbers (x_i,y_i) be 𝒫_i(x_i,y_i). Under the Bayesian setting, we propose an enhanced median-single-constant (MSC) mechanism (shown in Algorithm <ref>) where we add a single constant point (x_c,y_c) in the original set of input locations and then run the median mechanism on the new set. According to Theorems <ref> and <ref>, the MSC mechanism is equivalent to respectively setting one constant on each dimension at a fixed value while setting the half of the other constants at the positive infinity and the remaining half at the negative infinity. Hence, its design rationale follows the multi-dimensional generalized median mechanism and is strategyproof. We obtain vectors 𝐱=(x_1,…,x_N̂) and 𝐲=(y_1,…,y_N̂) from 𝐋=((x_1,y_1),…,(x_i,y_i),…,(x_N̂,y_N̂)). Let (x_med,y_med)=𝖬_MED(𝐋) and (x_msc,y_msc)=𝖬_MSC(𝐋) respectively be the outcome from the MED mechanism and the MSC mechanism. Next, we analyze their expected performance.

With 𝔼[·] denoting the expectation, for the SC platform's
crowdsourcing cost l̂_m in (<ref>),
we compute

    𝔼_(x_i,y_i)∼𝒫^i, i∈𝒩̂[l̂_m(𝖬_MED(𝐋))]
        =∬_(x_1,y_1)∈A_1⋯∬_(x_N̂,y_N̂)∈A_N̂l̂_m(𝖬_MED(𝐋))
           𝒫_1(x_1,y_1)⋯𝒫_N(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂.

For ease of the analysis, we assume that all workers are independently and identically distributed following the same continuous PDF 𝒫 on the domain A in the rest of the subsection. In order to simplify the operation with symmetry, we first define and investigate l̂_m(𝖬_MED(𝐋)) by setting each worker's transmission rate r̃_i=1. As the PDF is continuous, we consider only the case where x_1,…,x_N̂,y_1,…,y_N̂ are all different. When x_1,…,x_N̂,y_1,…,y_N̂ are all different, to sort x_1,…,x_N̂ and y_1,…,y_N̂ in ascending order, we have (N̂!)^2 possibilities. Hence, it follows that 

    𝔼_(x_i,y_i)∼𝒫, i∈𝒩̂[l̂_m(𝖬_MED(𝐋))]
       =∬_(x_1,y_1)∈A⋯∬_(x_N̂,y_N̂)∈Al̂_m(𝖬_MED(𝐋))
       𝒫(x_1,y_1)⋯𝒫(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂
        =(N̂!)^2∬_l
    (x_1,y_1),…,(x_N̂,y_N̂)∈A
    
    x_1<⋯<x_N̂
    
    y_1<⋯<y_N̂l̂_m(𝖬_MED(𝐋))
                  𝒫(x_1,y_1)⋯𝒫(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂.

Given x_1<x_2<⋯<x_N̂ and y_1<y_2<⋯<y_N̂, we can have 𝖬_MED(𝐋)=(x_N̂/2+x_N̂/2+1/2,y_N̂/2+y_N̂/2+1/2) for even N̂ and 𝖬_MED(𝐋)=(x_N̂+1/2,y_N̂+1/2) for odd N̂ according to the MED mechanism (Algorithm <ref>). After substituting the expression of 𝖬_MED(𝐋) into equation (<ref>), we can combine equations (<ref>) and (<ref>) to obtain 

    𝔼_(x_i,y_i)∼𝒫, i∈𝒩̂[l̂_m(𝖬_MED(𝐋))]
        =
    (N̂!)^2∬_l
    (x_1,y_1),…,(x_N̂,y_N̂)∈A
    
    x_1<⋯<x_N̂
    
    y_1<⋯<y_N̂l̂_m((x_N̂/2+x_N̂/2+1/2,y_N̂/2+y_N̂/2+1/2))
                 𝒫(x_1,y_1)⋯𝒫(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂,
                                                                                                             for even N̂,
    
    (N̂!)^2∬_l
    (x_1,y_1),…,(x_N̂,y_N̂)∈A
    
    x_1<⋯<x_N̂
    
    y_1<⋯<y_N̂l̂_m((x_N̂+1/2,y_N̂+1/2))
                𝒫(x_1,y_1)⋯𝒫(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂,
                                                                                                            for odd N̂.

Then, considering the symmetry of each worker, we can use (<ref>) to obtain the simplified expression of (<ref>) as follows:

    𝔼_(x_i,y_i)∼𝒫, i∈𝒩̂[l̂_m(𝖬_MED(𝐋))]
        =1/N̂∑_j∈𝒩̂r̃_j𝔼_(x_i,y_i)∼𝒫, i∈𝒩̂[l̂_m(𝖬_MED(𝐋))].
 

For the MSC mechanism, we study its performance in a similar way as above and address the problem of how to calculate the constant point (x_c,y_c) by leveraging the known distribution 𝒫. Due to the symmetry and the limited space, the following analysis just shows cases where x_1<x_2<⋯<x_N̂, y_1<y_2<⋯<y_N̂, N̂ is odd and the x_c is smaller than x_N̂-1/2, i.e., x_c≤ x_N̂-1/2. It can be extended for other cases where N is even and x_c is more general. 

1) Case 1: When x_c<x_N̂-1/2 and y_c<y_N̂-1/2,
then 𝖬_MSC(𝐋)=(x_N̂-1/2+x_N̂+1/2/2,y_N̂-1/2+y_N̂+1/2/2)
and

    𝔼_(x_i,y_i)∼𝒫, i∈𝒩̂[l̂_m(𝖬_MSC(𝐋))]
        =∬_l
    (x_1,y_1),…,(x_N̂,y_N̂)∈A
    
    x_N̂-3/2<x_c<x_N̂-1/2
    
    y_N̂-3/2<y_c<y_N̂-1/2l̂_m((x_N̂-1/2+x_N̂+1/2/2,y_N̂-1/2+y_N̂+1/2/2))
       𝒫(x_1,y_1)⋯𝒫(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂((N̂-1/2)^2-2) terms+⋯+
       ∬_l
    (x_1,y_1),…,(x_N̂,y_N̂)∈A
    
    x_c<x_1
    
    y_c<y_1l̂_m((x_N̂-1/2+x_N̂+1/2/2,y_N̂-1/2+y_N̂+1/2/2))
       𝒫(x_1,y_1)⋯𝒫(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂.


2) Case 2: When x_c<x_N̂-1/2 and y_N̂-1/2<y_c<y_N̂+3/2,
then 𝖬_MSC(𝐋)=(x_N̂-1/2+x_N̂+1/2/2,y_c+y_N̂+1/2/2)
and


    𝔼_(x_i,y_i)∼𝒫, i∈𝒩̂[l̂_m(𝖬_MSC(𝐋))]
        =∬_l
    (x_1,y_1),…,(x_N,y_N)∈A
    
    x_N̂-3/2<x_c<x_N̂-1/2
    
    y_N̂-1/2<y_c<y_N̂+3/2l̂_m((x_N̂-1/2+x_N̂+1/2/2,y_c+y_N̂+1/2/2))
       𝒫(x_1,y_1)⋯𝒫(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂(N̂-3) terms+⋯+
       ∬_l
    (x_1,y_1),…,(x_N̂,y_N̂)∈A
    
    x_c<x_1
    
    y_N̂+1/2<y_c<y_N̂+3/2l̂_m((x_N̂-1/2+x_N̂+1/2/2,y_c+y_N̂+1/2/2))
       𝒫(x_1,y_1)⋯𝒫(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂.


3) Case 3: When x_c<x_N̂-1/2 and y_N̂+3/2<y_c,
then 𝖬_MSC(𝐋)=(x_N̂-1/2+x_N̂+1/2/2,y_N̂+1/2+y_N̂+3/2/2)
and


    𝔼_(x_i,y_i)∼𝒫, i∈𝒩̂[l̂_m(𝖬_MSC(𝐋))]
        =∬_l
    (x_1,y_1),…,(x_N̂,y_N̂)∈A
    
    x_N̂-3/2<x_c<x_N̂-1/2
    
    y_N̂+3/2<y_c<y_N̂+5/2l̂_m((x_N̂-1/2+x_N̂+1/2/2,y_N̂+1/2+y_N̂+3/2/2))
       𝒫(x_1,y_1)⋯𝒫(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂((N̂-1/2)^2-2) terms+⋯+
       ∬_l
    (x_1,y_1),…,(x_N̂,y_N̂)∈A
    
    x_c<x_1
    
    y_N̂<y_cl̂_m((x_N̂-1/2+x_N̂+1/2/2,y_N̂+1/2+y_N̂+3/2/2))
       𝒫(x_1,y_1)⋯𝒫(x_N̂,y_N̂) dx_1⋯dx_N̂dy_1⋯dy_N̂.


There are totally ((N̂+1)!)^2 terms similar to (<ref>) to compute the expected utility achieved by the MSC mechanism, which is challenging especially when N̂ is large. Next, we would like to present a special case to show the possibility and feasibility to maximize the expected utility through optimizing (x_c,y_c). In the special case, we assume that each worker's location follows the bivariate uniform distribution, i.e., 𝒫^u= 1,     (x,y)∈A=[0,1]^2,
 0,     otherwise, and the path-loss α is 2. Then, by substituting these parameters into (<ref>)-(<ref>) and using mathematical induction, we first obtain the expected utility generated by the MED mechanism as 

    𝔼_(x_i,y_i)∼𝒫^u, i∈𝒩̂[l̂_m(𝖬_MED(𝐋))]
        =P̃_cκ((N-1)(N+4)/6(N+1)(N+2)+h^2),     for even N̂,
    P̃_cκ((N-1)(N+3)/6N(N+2)+h^2),     for odd N̂.

For the MSC mechanism, we analyze a situation where there are three employed workers, i.e., N̂=3. The same way of the analysis can be applied to any number of employed workers. Based on the analysis above, we can calculate the expected utility achieved by the MSC mechanism as follows:

    𝔼_(x_i,y_i)∼𝒫, i∈{1,2,3}[û_m(𝖬_MSC(𝐋))]
        =P̃_cκ(192-x_c^4+y_c^4/4+x_c^3+y_c^3/2-x_c^2+y_c^2/4+3/20+h^2).

Then, the expected utility achieved by the MED mechanism is 

    𝔼_(x_i,y_i)∼𝒫, i∈{1,2,3}[û_m(𝖬_MED(𝐋))]=P̃_cκ(2/15+h^2).

The minimum value of 192 in equation (<ref>) is 19/160 achieved at x_c=y_c=0.5, which is smaller than 2/15. Hence, we can find a constant point (x_c,y_c) that enables the MSC mechanism to achieve lower expected crowdsourcing cost than that of the benchmark MED mechanism. This also indicates the possibility of improving and extending the MSC mechanism for more general scenarios.



 §.§ Deep learning based mobile BS deployment mechanism  


Clearly, above conventional mechanisms, including the MED and MSC mechanism, have several non-negligible limitations: 


  * It is intractable to manually optimize the MSC mechanism in realistic
environments where path-loss exponent α is not necessarily
2 and the number of employed workers N̂ may be much larger
than 3. 

  * Each worker's working location distribution can be different and correlated.
Despite the location distribution can be inferred from historical
data, its accurate type is not always known or even there is no corresponding
closed-form expression for us to proceed with the theoretical analysis.

  * In the MSC mechanism, only a single constant point is optimized while
the generalized median mechanism implies that more constant points
can be used to improve the expected performance. 

To overcome the above limitations, we develop a deep learning based mechanism named the MDL mechanism. The MDL mechanism provides an efficient model-free method to simultaneously exploit the data and optimize the complicated objective utility function while satisfying the incentive constraints. In the construction of the deep neural network, we use an equivalent definition (Theorem <ref>) of the one-dimensional generalized median mechanism (Theorem <ref>). 

(<cit.>)
A mechanism 𝖬 is a strategyproof and anonymous generalized
median mechanism on one dimensional space if there exist 2^N̂
points {ζ_𝒯} _𝒯⊆𝒩̂
in [ζ_∅,ζ_𝒩̂], such that 1)
𝒯⊆𝒯'⊆𝒩̂ implies
ζ_𝒯≤ζ_𝒯' and 2) for all 𝐱∈ℝ^N̂,
𝖬(𝐱)=max_𝒯⊆𝒩̂min{ζ_𝒯, x_i:i∈𝒯}.


According to Theorem <ref>,
we develop a two-dimensional strategyproof mechanisms by directly
applying Theorem <ref> in each dimension.
We adopt the data preprocessing method in <cit.>. The
collected location data 𝐱=(x_1,…,x_N̂) and
𝐲=(y_1,…,y_N̂) in ascending order, i.e.,
x_π_x(1)≤ x_π_x(2)≤⋯≤ x_π_x(N̂)
and y_π_y(1)≤ y_π_y(2)≤⋯≤ y_π_y(N̂)
where π_x(j) and π_y(j) respectively represent the worker
ID at the jth place on X and Y axes. Usually, we normalize all
input data into [0,1] in the experiments. We define two sets 𝒯_x(j)={π_x(1),π_x(2),…,π_x(j)}
and 𝒯_y(j)={π_y(1),π_y(2),…,π_y(j)}
where j∈𝒩̂. We also establish a monotonically
increasing mapping μ(𝒯) to transform the set 𝒯
to the N̂-length binary vector 𝐳=(z_1,…,z_N̂)
where z_i=1 if i∈𝒯 and z_i=-1 if i∉𝒯.
Thus, if 𝐳=μ(𝒯)=(z_1,…,z_N̂),
𝐳'=μ(𝒯')=(z'_1,…,z'_N̂) and
𝒯⊆𝒯', we can have z_i≤ z'_i,∀ i∈𝒩̂. 

The first condition in Theorem <ref> actually requires a monotonically increasing mapping from a set 𝒯 to a constant value ζ_𝒯. As μ(𝒯) has already mapped the set 𝒯 to a vector 𝐳, we construct a five-layer neural network ν_𝐰,𝐛 (shown in Fig. <ref>) to approximate a monotonically increasing function, i.e., ν_𝐰,𝐛(μ(𝒯))=ν_𝐰,𝐛(𝐳)=ζ_𝒯.
The increasing monotonicity here means ν_𝐰,𝐛(𝐳)=ζ_𝒯≤ν_𝐰,𝐛(𝐳')=ζ_𝒯'
if z_i≤ z'_i,∀ i∈𝒩̂. The monotonic
neural network function ν_𝐰,𝐛 is described by

    ν_𝐰,𝐛(μ(𝒯))     =ν_𝐰,𝐛(𝐳)
        =max_j∈[J]min_k∈[K]{s(b_jk2+e^𝐰_jk2s(e^𝐰_j1𝐳^T+𝐛_j1))},

where J and K are positive integral hyperparameters that affect the accuracy and complexity of the neural network, 𝐳^T is the transpose of 𝐳, 𝐰_j1∈ℝ^K×N̂, 𝐛_j1∈ℝ^K×1 are parameters in the first hidden layer, and 𝐰_jk2∈ℝ^1× K, b_jk2∈ℝ are the parameters in the second hidden layer. The exponential operations in (<ref>) are used to guarantee that the weights of the input vector 𝐳, i.e., e^𝐰_j1 and e^𝐰_jk2, are always positive. We use a shifted log-sigmoid function s(t)=log(1/1+e^-t)+1 as the activation function which also well restricts the output range. The max-min neural network in Fig. <ref> is monotonically increasing as it follows the characterizations of the monotonic network in <cit.>. 

Next, based on the second condition in Theorem <ref>, we construct the complete deep neural network f_𝐰,𝐛 by integrating the monotonic network ν_𝐰,𝐛 with the max and min functions. Finally, the neural network function f_𝐰,𝐛 of the MDL mechanism is

    f_𝐰,𝐛(μ_x,μ_y,𝐱,𝐲)     =(x_M,y_M)
        =(max_i∈𝒩̂{min{ν_𝐰,𝐛^x(μ(𝒯_x(i))),x_π_x(i)}} ,
       max_j∈𝒩̂{min{ν_𝐰,𝐛^y(μ(𝒯_y(j)),y_π_y(i)}} ).

According to Theorems <ref> and <ref>, the MDL mechanism is strategyproof. Note that the objective function in (<ref>) is convex with respect to L_M=(x_M,y_M). Hence, for each data sample (𝐱,𝐲), we can efficiently compute the optimal solution L_M^*=(x_M^*,y_M^*) to minimize the SC platform's crowdsourcing cost in (<ref>) without considering strategyproofness and then use it as the label. In the training process, we adopt the mean squared error (MSE) to evaluate the training loss and optimize the deep neural network parameters. Given a set of G data samples 𝒢={(𝐱,𝐲)^1,…,(𝐱,𝐲)^G} and corresponding labels 𝐋_M^*={(x_M^*,y_M^*)^1,…,(x_M^*,y_M^*)^G}, the loss can be calculated by 

    loss     =1/G∑_j=1^G(l̂_m(𝖬_MDL((𝐱,𝐲)^j);(𝐱,𝐲)^j)
        -l̂_m((x_M^*,y_M^*)^j;(𝐱,𝐲)^j))^2,

where 𝖬_MDL((𝐱,𝐲)^j) is the mobile BS's location output by the MDL mechanism when the input is the jth data sample (𝐱,𝐲)^j,j∈{1,…,G}. 



§ EXPERIMENTAL RESULTS AND DISCUSSIONS 


In this section, we conduct simulations based on real data to evaluate the performance of our proposed framework and strategyproof deployment mechanisms. Unless otherwise stated, the simulation configuration is set as follows. We consider a [0,200]×[0,200] square-meter area as the SC task area A_t. The number of registered workers is set at N=40. We set the height of the mobile BS h=10 m, e.g., a drone, the channel gain to noise ratio g=90 dB, the bandwidth of each subchannel B=60 MHz, the data utility parameters a_1=10^4, a_2=200, the energy conversion efficiency η=0.6, the antenna gain Γ=-30 dB, and the path-loss exponent α=2 <cit.>. The sensing energy cost per bit b_i is generated from the uniform distribution on [10^-4,1.1×10^-4]. Each measurement is averaged over more than 100 instances. 

To illustrate the practical use of our proposed algorithms, we use a real-world dataset from NYC MTA Real-Time Data Feeds[ https://datamine.mta.info/]. The dataset has more than 2 million mobility traces, i.e. the GPS location records, of 95 workers located in New York City over a period of one month. It is reasonable that a worker usually estimates the working area according to its past experience. Therefore, the historical GPS records help us to calculate the worker's working area A_i and maximum distance D_i. For better performance of neural network processing, we first normalize the dataset to the range [0,1] and respectively prepare 24,000 samples (training dataset) for MDL model training and 6,000 samples (testing dataset) for testing and performance evaluation. Each data sample contains the workers' locations at one time slot. We randomly choose 100 samples to provide a brief overview of the prepared dataset, as shown in Fig. <ref>. Each worker's maximum distance D_i is also calculated according to the dataset. We use the Pytorch deep learning library to implement the MDL mechanism with K=8, J=8. We use the ADAM optimizer with a learning rate of 0.005 and mini-batch of 200 when training the MDL model. All the experiments were run on a workstation with a GTX1080Ti GPU. 




Figure <ref> demonstrates the impact of the number of registered workers N on the SC platform's utility, the average worker's utility and the number of employed workers in the task allocation phase. When the number of registered workers increases, the SC platform's utility and the number of employed workers gradually increase but with a diminishing return. These reflect that when more workers are employed, the SC platform has to consume more charging power for the same marginal utility. By contrast, the average worker's utility decreases with the increase of registered workers because of the more competition among workers. Next, we present simulation results for the data crowdsourcing phase. 

Figure <ref> depicts the performance of the proposed truthful MSC mechanism in the special case as discussed in Section <ref>. As a priori information, the workers' locations are i.i.d. uniformly distributed over the SC task area. Thus, the added single constant point (x_c,y_c) is set at the expected location (100,100) due to the symmetry and the analysis presented in Section <ref>. The optimal solution without considering the incentive constraints is also calculated for comparison, which is denoted as the OPT algorithm. Obviously, the performance of the MSC mechanism is better (with lower crowdsourcing cost) than that of the MED mechanism when N̂=3, which is consistent with the theoretical analysis. For N̂>3, the MSC mechanism still outperforms the MED mechanism but is always inferior to the OPT mechanism because of the sacrifice for guaranteeing the strategyproofness. 

To illustrate the performance of our proposed mechanisms in minimizing the SC data crowdsourcing cost l̂_m, we use the average performance ratio ω^avg and the worst-case performance ratio ω^wst as the evaluation metrics. In our experiment, they are measured based on the prepared test dataset. The average performance ratio is defined as the ratio of the average data crowdsourcing cost achieved by the proposed mechanism over the average crowdsourcing cost achieved by the OPT mechanism. The worst-case performance ratio is defined as the highest ratio of the data crowdsourcing cost achieved by the proposed mechanism over the crowdsourcing cost achieved by the OPT mechanism. Formally, given the test dataset of G_test data samples 𝒢_test={(𝐱,𝐲)^1,…,(𝐱,𝐲)^G_test}, we take the MED mechanism for example and have ω_MED^avg=1/G_test∑_(𝐱,𝐲)^j∈𝒢_testl̂_m(𝖬_MED((𝐱,𝐲)^j);(𝐱,𝐲)^j)/1/G_test∑_(𝐱,𝐲)^j∈𝒢_testl̂_m(𝖬_OPT((𝐱,𝐲)^j);(𝐱,𝐲)^j)
and ω_MED^wst=max_(𝐱,𝐲)^j∈𝒢_testl̂_m(𝖬_MED((𝐱,𝐲)^j);(𝐱,𝐲)^j)/l̂_m(𝖬_OPT((𝐱,𝐲)^j);(𝐱,𝐲)^j). A lower ratio means a better performance. 






In Fig. <ref>, the number of employed workers N̂ is fixed to be 30 and we investigate the performance of the MED mechanism and the MDL mechanism with the varied path–loss exponent. We find that when the radio environment gets worse (a larger path–loss exponent α), the average and worst-case performance ratios of both the MED and the MDL mechanism grow at different rates. In Fig. <ref>, we fix the path-loss exponent α at 2.4 and study the impact of the different number of employed workers on the performance ratios of each proposed mechanism. Figure <ref> illustrates that the increasing number of employed workers has an implicit impact on the performances of both proposed mechanisms. The main reason is that each worker's location distribution in the mobility dataset is different. Otherwise, if each worker's location follows the i.i.d distribution, more employed workers mean more reported data which makes the hidden distribution more certain and at least makes the average performance ratio of the MED mechanism decline. This phenomenon can be seen in Fig. <ref>. Therefore, the impact of the number of employed workers is closely related to the characteristic of the used dataset. In summary, compared with the MED mechanism, the deep learning based mechanism, i.e., the MDL mechanism, shows two clear advantages in the considered complicated scenario. The first advantage is noticeable stability. In Fig. <ref>, it can be observed that the worst performance ratio of the MED mechanism increases exponentially with the increasing path-loss exponent, while the MDL mechanism shows an approximately linear increasing trend. The second advantage is the significant performance improvement. As illustrated in Fig. <ref>, the MDL mechanism achieves at least 5.19% (18.39%) reduction in average (worst-case) performance ratio compared to the MED mechanism.





§ CONCLUSION


In this paper, we have proposed a wireless powered spatial crowdsourcing framework composed of two phases. In the task allocation phase, we have proven that the proposed Stackelberg game based incentive mechanism can help the SC platform efficiently allocate the tasks and the wireless charging power. For the deployment of the mobile BS in the data crowdsourcing phase, we have adopted the classical strategyproof median mechanism. We have also designed a conventional strategyproof mechanism and a deep learning based strategyproof mechanism from a Bayesian point of view. Besides avoiding the dishonest worker's manipulation, extensive experimental results based on synthetic and real-world datasets demonstrate the effectiveness of the proposed framework in allocating tasks and charging power to workers. It is worth noting that, in this paper, we use the data transmission rate as a general metric to evaluate the data utility. In future work, we will take other specific data attributes into consideration, such as the location and timeliness. For the time-varying scenario, we can also develop a dynamical deployment mechanism using deep reinforcement learning. 

IEEEtran




