Task Offloading in Wireless Powered Mobile Crowd Sensing: A Matching-Based Approach

Abstract

Mobile crowd sensing (MCS) is a new sensing paradigm that leverages participatory sensing data from mobile devices for accomplishing large-scale sensing tasks. Incentivizing device owners to contribute high-quality sensing data is a prerequisite for the success of MCS services. In this paper, we first propose a pre-contracting incentive mechanism that involves the participation of not only the device owners located in close proximity to Point of Interests (PoIs) but also the device owners that are going to pass through those locations. Furthermore, the quality of sensing data is guaranteed through the use of redundancy. In particular, sensing data from multiple device owners is processed and compared at an edge side (i.e., base station) so as to detect the measurement error at the proximity of data sources. Simulation results confirm that the proposed incentive mechanism is efficient in terms of improving the total utility.

1. Introduction

Crowd sensing refers to establishing a sensing network by utilizing existing mobile nodes, such as smart phones, unmanned aerial vehicles (UAV), etc., and publishing sensing tasks to individuals or groups in the network to complete, thereby helping data demand side to collect, analyze, and share information [1]. With the popularization of mobile nodes and the development of their on-board sensors, crowd sensing provides a new mode of perceiving the environment, collecting data, and providing information services. Traditional sensing methods, such as wireless sensor networks, are prone to limitations such as insufficient node coverage, high operating expenses, and lack of scalability. Crowd sensing, the combination of mobility and sensing ability of mobile nodes, can provide fine-grained information for public safety, environmental monitoring, medical care and social life. Crowd sensing has great advantages, such as flexibility, cost-efficiency, multi-source heterogeneity of sensing data, large-scale coverage, and high expansion. Due to these advantages, crowd sensing has received more and more attention, both from academy and industry.

The typical system architecture of crowd sensing includes three parts: sensing platform, task owners, and task participants (i.e., mobile nodes). The sensing platform in the cloud accepts service requests from task owners, assigns sensing tasks to participants, analyzes the collected sensing data, and performs other management functions. After receiving a task request, the task participants complete the sensing task, and then send back the data to the sensing platform, which processes the data and forwards the information to the task owner.

Crowd sensing can collect massive multi-dimensional heterogeneous data from various places, solve various large-scale data demand, and provide fine-grained and reliable data services. However, with the popularity of crowd sensing, several challenges remain to be addressed. Among them, the main obstacle that hinders the development of crowd sensing is that participants are not highly motivated, and the sensing platform cannot recruit enough participants to collect high-quality and reliable sensing data. Therefore, how to motivate more participants to join crowd sensing and provide sensing data with high reliability and validity is a key issue to promote its development.

Considering the opportunistic characteristics of the participants, the sensing platform attempts to recruit more participants with the least or affordable cost. For example, for location-sensitive data, the wider and more uniform the sources of sensing data, the higher the quality of the data. In this case, data from remote areas will be more valuable. The incentive mechanism of the sensing platform should be able to incentivize participants to provide high-quality data. In addition, participants are prone to cheat about data quality or personal information to get higher payment. Therefore, an efficient incentive mechanism is essential for ensuring the level of participation and the quality of completion.

2. Related Work

The incentive mechanisms for crowd sensing can be classified into four categories: monetary incentives, entertainment incentives, social incentives, and virtual incentives.

2.1. Monetary Incentives

Monetary incentives can be further divided into two classes: server-centric and user-centric. Both methods are based on micro-payments, namely, payment to reward participants’ sensing data. The server-centric approach requires the information of all participants in advance, such as quotation, data quality, etc., and then select a subset of participants with the smallest payment cost and the highest utility from all participants. This server-centric payment-reward method mainly uses game theory. Participant-centric compensation payment means that the sensing platform does not select participants based on all known participant information, but pays directly based on the data quality of each participant. In this case, no other participant information is needed as a reference. John et al. [2] conducted a two-day survey with 96 people and demonstrated that micro-payments can motivate more participants to complete the sensing task than the weighted lottery method. In [3], the authors used three attributes, i.e., sensing data volume, sensing data quality, and space–time coverage, as evaluation criteria and proposed an incentive mechanism to reward participants. Facilitated by the accurate traffic prediction [4], Gu et al. proposed a multi-agent reinforcement learning based task offloading for encouraging user participation in ultra-dense networks [5].

2.2. Entertainment Incentives

Entertainment incentives refer to the level rankings, task points, and inherent fun brought about by the games motivating participants to complete tasks. Similar to monetary incentives, entertainment incentives also bring satisfaction to participants and thus act as incentives [6,7,8]. Kawajiri et al. [9] adopted a game-incentive approach to encourage users to complete location-related sensing tasks oriented to data quality.

The rewards of data collection are converted into game points (coupon points); then, participants decide whether to participate in the sensing task. In their actual system, game points are determined based on a quality indicator. In different locations, according to the current data collection quality, different game points are allocated to motivate participants to collect data, and through different game points, participants are motivated to collect data at different locations. BudBurst [10] is a UCLA project for crowd-sensing to examine the motivational role of game mechanics in motivating users to collect data. BudBurst studies the effects of climate change on plants based on users’ observations of surrounding plants and records of observations, which are uploaded to a server. In [10], the authors introduced outdoor play activities to incentivize people to participate in the project. These game activities include accumulating points, leveling up, and recording outdoor observations. By recruiting 50 volunteers, the experiment was carried out for two weeks. The paper points out that this game incentive mechanism can promote user participation. In [11], Ueyama et al. adopted a ranking scheme and a badge scheme to motivate participation. This kind of payment and reward combined with the game mechanism can not only meet the financial needs of the participants, but also gain a sense of accomplishment in the game. Numerical results demonstrate that with the entertainment incentives, the participation probability increases from 53% to 73%. The entertainment incentive method integrates a series of game mode design and task reward and return strategies, integrates the habits and psychological effects of the participants, and organically integrates them into the crowd-sensing incentive mechanism, which can play a positive role in stimulating the participants. Nevertheless, the limitation of entertainment game incentives is that the combination of sensing tasks and game design is very dependent on the characteristics of sensing tasks and games, and not all sensing tasks can be simply gamified. Currently, location-related sensing tasks are easier to combine with recreational games.

2.3. Social Incentives

Social incentive refers to using the social relationship network formed by participants to motivate them to participate in sensing tasks. Social incentives are more focused on improving the quality of sensing tasks through the enthusiasm and initiative that participants bring to maintain their status, honor, etc. in the social network. In [12], the authors detect dishonest selfish participants by introducing existing social network information. Aiming at a special type of sensing network in crowd sensing, the opportunity sensing network, this paper establishes a trust system between participants through existing social networks to improve the existing incentive mechanism. Since there is no fixed sensing network infrastructure, sensing data needs to be passed between sensing nodes to the server. Considering the selfishness of sensing nodes, in order to reduce unnecessary energy and storage consumption, selfish sensing nodes will not share data with other nodes. Aiming at this situation, this paper employs the social network information to establish a trust relationship model between sensing nodes. The method can detect selfish nodes in time and improve the network information transfer rate. Luo et al. [13] proposed the Simple Endorsement Web (SEW) approach, a nepotism-based incentive mechanism, which ensures the credibility of the data quality of the participants by establishing the endorsement relationship between the participants. Nepotism means that when one of the individuals uploads untrustworthy data, this untrustworthy behavior will lead to implication or even punishment of other individuals within the nepotism.

2.4. Virtual Incentives

Different from direct remuneration payments, virtual incentives, such as flight points provided by airlines, can also act as incentives in crowd sensing. Participants can obtain other rewards by continuously accumulating points. In [14,15], the authors use virtual integral to solve the mobile monitoring problem of vehicle communication, and collect the scene of the traffic accident through the camera of mobile vehicles, so as to help the police locate the perpetrator or the suspect. The incentive mechanism encourages participants to use their own data traffic to upload data through virtual points, or share their own broadband resources to help other participants upload data. Different virtual points are assigned according to the utility generated by different data, such as different video resolutions. High-resolution videos can obtain high virtual points. Yu et al. [16] proposed a virtual integral-based data traffic crowd sensing system INDAPSON, which aims to incentivize users with excess data traffic to share their data to help users with insufficient traffic. The article points out that the existing traffic package business in the communication industry is fixed, but the consumption of each user is different every month, which results in a waste of data traffic. This article aims to encourage mobile users to share their traffic data with the others based on a virtual point system and a reputation-based adaptive pricing scheme (RAP). In summary, the virtual point incentive is different from the payment method. Participants cannot directly get paid, but virtual points can meet the psychological needs of participants in terms of self-value realization and vanity, play a guiding role for participants, and increase user stickiness. The virtual points method can be used to combine the payment and entertainment games to better motivate the participants.

3. System Model

The MCS system consists of multiple stakeholders: (i) mobile nodes (MNs), which are the providers of sensing data; (ii) a sensing platform which helps to recruit participants to perform sensing tasks; (iii) task owners who publish sensing tasks on the sensing platform. MNs receive monetary payment for contributing sensing data.

As shown in Figure 1, the steps involved in participant recruitment are summarized as follows:

Step 1: Task owners send task requests to the platform. The task request includes: (i) the PoIs, (iii) the desired sensing coverage, (ii) the tolerable latency, and (iv) the monetary budget for recruiting participants, etc.

Step 2: Upon receiving the task request, the sensing platform initiates participant recruitment by broadcasting task requests and notifying the corresponding monetary payment to potential participants.

Step 3: MNs claim for an interested sensing task and upload the sensing data back to the platform.

Step 4: The platform aggregates all sensing data and reports to the task requester.

Time is divided into multiple time slots. In one time slot, each task owner can publish one sensing task and the platform can recruit multiple MNs to meet the sensing coverage requirement of task owner, while each MN can perform at most one sensing task. Formally, the number of tasks is denoted by M, and the set of tasks is represented by $\mathbf{\tau }={\left\{{\tau }_i\right\}}_{i=1}^M$. Moreover, the number of MNs is denoted by N, and the set of MNs is represented by $\mathbf{\eta }={\left\{{\eta }_j\right\}}_{j=1}^N$.

After performing a sensing task, each MN uploads the sensing data back to the platform through a base station. The achievable data rate from MN j to the base station is given by ${\gamma }_j$ as follows:

$${\gamma }_j=Blog\left(1+\frac{p_j^{\mathrm{tra}}{h}_j}{N_0}\right)$$

(1)

where $h_j$ is the channel gain from MN j to the base station, $p_j^{\mathrm{tra}}$ is the transmit power of MN j, B is the bandwidth, $N_0$ is the noise at the base station.

Hence, the latency of uploading the sensing data to the base station is denoted by $L_{ij}^{\mathrm{tra}}$ as follows [17]:

$$L_{ij}^{\mathrm{tra}}=\frac{D_{ij}}{{\gamma }_j}=\frac{D_{ij}}{Blog\left(1+\frac{p_j^{\mathrm{tra}}{h}_j}{N_0}\right)}$$

(2)

where $D_{ij}$ is the sensing data size when MN j performs the sensing task of requester i.

The transmission energy consumption of MN j when performing the sensing task of requester i is given by $E_{ij}^{\mathrm{tra}}$ as follows:

$$E_{ij}^{\mathrm{tra}}=p_j^{\mathrm{tra}}{L}_{ij}^{\mathrm{tra}}=\frac{p_j^{\mathrm{tra}}{D}_{ij}}{Blog\left(1+\frac{p_j^{\mathrm{tra}}{h}_j}{N_0}\right)}$$

(3)

We assume that both the MNs and task owners are rational, in the sense that the MNs select to participate in sensing activities, aiming at maximizing its monetary benefit at the minimum cost of energy consumption; the sensing platform recruits MNs on behalf of task owners in order to maximize the sensing coverage under their budget constraints.

The utility of MN j achieved by accomplishing sensing task i is given by $u_{ij}$ as follows:

$$\begin{array}{c}\hfill u_{ij}=p{D}_{ij}-{\alpha }_j{E}_{ij}^{\mathrm{tra}}\end{array}$$

(4)

where p is the monetary payment per unit sensing data, and ${\alpha }_j$ is the energy cost coefficient of MN j.

On the other hand, the utility of requester i achieved by assigning its sensing task to MN j is given by $v_{ij}$ as follows:

$$\begin{array}{c}\hfill v_{ij}={\beta }_i{C}_{ij}-p{D}_{ij}\end{array}$$

(5)

where $C_{ij}$ is the coverage increment if MN j is involved in accomplishing sensing task of requester i. An example of coverage increment is shown in Figure 2, and ${\beta }_i$ is a user-dependent coefficient that normalize the coverage increment to requester i’s willingness to pay. We assume that the coverage radius of each MN is r. When the sensing task is assigned to MN 1, 2, and 3, sequentially, the coverage increments of MN 1, 2, and 3 are represented by the area colored yellow, blue, and green, respectively.

4. Problem Formulation

An index $x_{ij}$ is used to denote the relation between the sensing task of requester i and MN j, where $x_{ij}=1$ represents that task i is assigned to MN j, while $x_{ij}=0$ represents that task i is not assigned to MN j.

We formulate a task assignment problem in order to maximize the system utility as follows:

$$\begin{array}{cc}\hfill \underset{\left\{x_{ij}\right\}}{max}& \sum _{i=1}^M\sum _{j=1}^N(u_{ij}+v_{ij})x_{ij}\hfill \\ \hfill =& \sum _{i=1}^M\sum _{j=1}^N({\beta }_i{C}_{ij}-{\alpha }_j{E}_{ij}^{\mathrm{tra}})x_{ij}\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \mathrm{C}1\sum _{i=1}^N{x}_{ij}\le 1,\forall j\in \{1,\dots ,N\}\hfill \\ \hfill & \mathrm{C}2\sum _{j=1}^N{u}_{ij}{x}_{ij}>0,\forall i\in \{1,\dots ,M\}\hfill \\ \hfill & \mathrm{C}2v_{ij}{x}_{ij}>0,\forall i\in \{1,\dots ,M\}\mathrm{and}\forall j\in \{1,\dots ,N\}\hfill \\ \hfill & \mathrm{C}4E_{ij}^{\mathrm{tra}}\le E_j^{\max },\forall i\in \{1,\dots ,M\}\mathrm{and}\forall j\in \{1,\dots ,N\}\hfill \\ \hfill & \mathrm{C}5\sum _{j=1}^{N}p{D}_{ij}{x}_{ij}\le P_i,\forall i\in \{1,\dots ,M\}\hfill \\ \hfill & \mathrm{C}6x_{ij}\in \{0,1\},\forall i\in \{1,\dots ,M\}\mathrm{and}\forall j\in \{1,\dots ,N\}\hfill \end{array}$$

(6)

Constraint C1 implies that each MN performs at most one sensing task in each time slot; Constraint C2 and C3 guarantee that the utility of each requester and MN should be positive; Constraint C4 guarantees that the energy consumption of MN j for accomplishing the sensing task of requester i should not be larger than a threshold value $E_j^{\max }$; Constraint C5 implies that the total amount of monetary payment should not be higher than requester i’s budget constraint: $P_i$. The optimization problem shown in Equation (6) is a binary linear programming problem (BLP) and is proved to be NP-hard.

5. Matching Theory Based Algorithm

Matching theory is a forceful tool to investigate the interactions between two sets of agents [18]. Each agent evaluates the others in the opposite set and sorts them in a descending order according to its preference.

Since agents make matching decisions by themselves interactively without requiring any centralized coordination, a matching-based protocol is generally scalable [19,20]. To achieve a distributed solution, we formulate the task offloading problem as a matching game between tasks and MNs. The tasks and MNs are considered as two disjointed sets to maximize the system utility while satisfying the energy consumption constraints of MNs and the monetary budget constrains of task owners.

As shown in Equation (5), the coverage increment and the consequent utility of requester i achieved by assigning its sensing task to MN j is strongly dependent on the dynamic formation of task–MN associations, which is termed externality in matching theory. A task has to keep changing its preference list in accordance with the dynamical formation of task–MN pairs, resulting in always-unstable matching, unless the externality is well addressed.

Since the problem (6) is NP-hard and the utility of each task owner changes dynamically with the task–MN associations, we propose a matching-based algorithm based on [21] to solve the system utility optimization problem. The ultimate goal of the proposed algorithm is to derive a distributed, efficient, and stable solution.

5.1. Swap Matching

Definition 1.

For a matching $\mathbf{\omega }$ and task–MN pairs $({\eta }_m,{\tau }_i)$, $({\eta }_n,{\tau }_j)\in \mathbf{\omega }$, a swap is defined as ${\mathbf{\omega }}_{ij}^{mn}=\{\mathbf{\omega }\setminus ({\eta }_m,{\tau }_i),({\eta }_n,{\tau }_j)\}\cup \{({\eta }_m,{\tau }_j),({\eta }_n,{\tau }_i)\}$, such that

$$\begin{array}{cc}\hfill & u_{in}\ge u_{im}\mathit{and}{u}_{jm}\ge u_{jn}\hfill \\ \hfill & v_{in}\ge v_{jn}\mathit{and}{v}_{jm}\ge v_{im}\hfill \end{array}$$

(7)

To be specific, the notation ${\mathbf{\omega }}_{ij}^{mn}\succ \mathbf{\omega }$ implies that the swap is beneficial for all agents involved, i.e., $\{{\tau }_i,{\tau }_j,{\eta }_m,{\eta }_n\}$.

Definition 2.

A matching $\mathbf{\omega }$ is called two-side exchange stable if there is no agent can benefit from unilaterally swapping from its current pair.

Following the above definitions, a matching $\mathbf{\omega }$ is regarded as stable if for any pair $({\tau }_i,{\eta }_m)\in \mathbf{\omega }$ it is impossible to find a pair $({\tau }_j,{\eta }_n)\in \mathbf{\omega }$, such that exchanging partners will be beneficial for ${\tau }_i$, ${\tau }_j$, ${\eta }_m$, and ${\eta }_n$. In other words, a swap can only occur when it causes no decline of the utility for all of the agents involved. Furthermore, a two-side exchange stable matching is Pareto optimal, since in a two-side exchange stable matching it is impossible to make one agent better off by swapping from its current pair without making another agent worse off.

5.2. Algorithm

The stages involved in reaching a stable matching are shown in Algorithm 1.

In the initialization step, each MN is initially matched to a randomly selected task as long as all conditions in Equation (6) can be satisfied. Then, each task i sorts MN $j\in \{1,\dots ,M\}$ in a descending order according to its preference. The preference is calculated according to Equation (5) to reflect the utility of the task completion of a certain MN. In each iteration, task (${\tau }_i$) firstly inquires into its most preferred MN (${\eta }_n$) except for its current partner (${\eta }_m$), and whether or not the ${\tau }_i$ is better than its current partner. Supposing that the current partner of ${\eta }_n$ is ${\tau }_j$, if ${\mathbf{\omega }}_{ij}^{mn}\succ \mathbf{\omega }$ and all constraints shown in Equation (6) are satisfied, then the swap will occur. Otherwise, the swap should be declined. The matching process terminates when pairs can no longer benefit from the swap. It has been proven that the computation complexity of the swap-matching algorithm is $O(M\times N)$ [22].

Algorithm 1 The proposed matching algorithm.

1: Step 1: Initialization stage   2: The sensing platform broadcasts the task request of each task owner i to candidate MNs. Upon receiving the broadcast message, the MN replies with their current location.  3: The sensing platform initially matches each MN to a randomly selected task owner in the case that all conditions in Equation (6) are satisfied.   4: Each MN ranks the tasks in a utility descending order according to Equation (4).   5: Each MN whose current partner does not rank the first in its preference list is added to a set ${\mathbf{\eta }}^{\mathrm{unchecked}}(\subseteq \mathbf{\eta })$.   6: Step 2: Swap matching stage   7: Select a MN ${\eta }_m(\in {\mathbf{\eta }}^{\mathrm{unchecked}}$).   8: while there exists a requester that ranks higher than ${\eta }_m$’s current partner do   9:     Given the pair (${\eta }_m,{\tau }_i$), ${\eta }_m$ finds ${\tau }_j$ that ranks the first but has not rejected its proposal in its preference list. 10:     Let ${\mathbf{\eta }}_j^{\mathrm{matched}}(\subseteq \mathbf{\eta })$ denote the set of MNs that are currently matched to ${\tau }_j$. 11:     for each MN in ${\mathbf{\eta }}_j^{\mathrm{matched}}$ do 12:         Select the least-preferred MN ${\eta }_n(\in {\mathbf{\eta }}^{\mathrm{unchecked}}$). 13:         if ${\mathbf{\omega }}_{ij}^{mn}\succ \mathbf{\omega }$ and all conditions in Equation (6) are satisfied then 14:            Approve the swap operation: ${\mathbf{\omega }}_{ij}^{mn}\to \mathbf{\omega }$. 15:            Remove ${\eta }_m$ from ${\mathbf{\eta }}^{\mathrm{unchecked}}$. 16:            if the current partner of ${\eta }_n$ does not rank the first in its preference list then 17:                Add ${\eta }_n$ into ${\mathbf{\eta }}^{\mathrm{unchecked}}$. 18:            end if 19:         else 20:            Reject the swap operation. 21:         end if 22:     end for 23: end while 24: if no swap occurs then 25:     Remove ${\eta }_m$ from ${\mathbf{\eta }}^{\mathrm{unchecked}}$. 26: end if 27: Step 3: Final stage 28: while${\mathbf{\eta }}^{\mathrm{unchecked}}$ is non-empty do 29:     Go to Step 2. 30: end while

6. Numerical Analysis

We conducted our simulations by using Veins [23], an open source framework for wireless communication simulation in in-vehicle mobile environments. Veins is based on OMNeT++ and a road traffic simulator Simulation of Urban MObility (SUMO), which by default uses the Krauss mobility model.

Simulations are conducted to verify the efficiency of the proposed incentive mechanism. For simplicity, we consider three PoIs. In order to simulate unbalanced distribution of the users, we assume that the number of potential participants are 3, 9, and 27 at location 1, 2, and 3, respectively. Without loss of generality, w is set to one and the bid of each device owner is uniformly chosen from: [0, 1]. Reservation price is set to 0.5, which is the mean value of the users’ bid. The total budget is varied from 0 to 3. Each simulation is repeated 10,000 times. A fixed reward scheme is used for comparison.

Sensing coverage is calculated as the ratio of the number of PoIs with at least one participant to the number of targeted locations. As shown in Figure 3 and Figure 4, both the total payment and sensing coverage increase along with the increasing of the budget. When the fixed reward is set to 0.1 (lower than the sensing cost of most device owners), the reward is insufficient to incentivize enough MNs to complete sensing tasks; when the fixed reward is on the other hand set to 0.5, the total budget is insufficient to recruit enough participants to achieve full sensing coverage. As depicted in Figure 4, the proposed method achieves higher sensing coverage, compared to the fixed reward schemes.

According to the results depicted in Figure 5, the proposed incentive mechanism also achieves higher platform utility, compared to fixed reward schemes. This is also not surprising since the auction-based mechanism guarantees that all participants reveal their private cost information truthfully, hence the platform can extract more surplus from sensing participants by setting an appropriate amount of reward.

Figure 6 show the power consumption versus the monetary budget. As we can observe, the proposed algorithm outperforms the fixed one in terms of power consumption. This is because, in the proposed method, tasks rank the MNs based on the utility function that captures their power consumption. As a consequence, the proposed algorithm, by its nature, ensures that tasks will be assigned to MNs that consume low energy.

7. Conclusions

We presented a pre-contracting incentive mechanism that leverages the sensing capability of users in moving vehicles to collect sensing data in rural areas. We proposed an auction-based mechanism to determine the winners and corresponding rewards. According to the simulation results, it can be seen that the proposed incentive mechanism yields satisfactory performance in terms of sensing coverage and total utility under a budget constraint.