# Diffusion Analysis and Incentive Method for Mobile Crowdsensing User Based on Knowledge Graph Reasoning

Authors: Jian Wang; Shanshan Cui; Guosheng Zhao; Zhongnan Zhao
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Aiming at the problem that the mobile crowdsensing (MCS) system relies on a specific platform with a large user group presupposed, this paper proposes a sensing user diffusion analysis and incentive method based on knowledge graph reasoning. We consider motivating users to participate under the constraint of limited budget so that the platform and users can get the most benefits. In this paper, we focus on socially aware users represented by self-organizing social networks, combine the knowledge graph to establish a knowledge graph for the crowdsensing system, use rules to derive user influence, and optimize user contributions. With the goal of maximizing social welfare, we propose a social awareness reverse auction (SARA) mechanism, in which the total contribution of users is the key to select winners, and the winners are paid based on critical prices. Through experimental simulations, we verify that SARA is close to the optimal social welfare under budget constraints.


---

## Body

## 1. Introduction

In recent years, mobile devices with various embedded sensors (such as smart phones and smart watches) have been everywhere, and vehicle-mounted and portable sensors (such as compass, accelerometer, GSP, and camera) have also appeared one after another. Mobile users carry their devices for extensive use in daily life, facilitating the information generation process. With the rapid development of various mobile sensing technologies, the human-centered mobile crowdsensing (MCS) system [1–3] has been developed. The mobile crowdsensing system has many applications in our daily life, covering many aspects, including medical care, environmental monitoring, intelligent transportation, and noise monitoring.Participating in crowdsensing tasks is an expensive process for users. On the one hand, it will consume the user's resources, such as computing power, storage memory, and battery. On the other hand, this process may require the user to submit personal sensitive information, thereby causing the user's privacy to be leaked. Therefore, if there is no satisfactory reward to compensate the user's participation fee, the user will not be willing to participate in the perception task. However, the crowdsensing system depends on the total user participation level and the individual contribution of each user. Therefore, in order to stimulate and recruit users who use mobile sensing devices to participate in sensing tasks, it is important and challenging to design an incentive mechanism to achieve sustainable profitability of service providers.There have been many studies on the incentive mechanism of mobile crowdsensing, but most of them assume that there are enough candidate users. However, this assumption may not be true in the real world. Especially mobile users may not even know it when the mobile crowdsensing app is just released to the public. In this case, the assumed large user pool no longer exists. Even if all candidate users are selected, the abovementioned worker selection method cannot achieve the high data quality of the mobile crowdsensing task. In this case, encouraging users to participate in sensing tasks cannot achieve good performance. Suppose that, after userui bids, he shares the sensing task T published by the platform with his friends and relatives through social networks. Among them, user uj who is interested in the sensing task and participates in the bid is a member of ui's recruitment target Ni. In this way, the task is spread out through ui, thereby expanding the set of sensing users. However, users will not spread freely. By analyzing the relationship between user ui and the recruited users, the social utility generated by user ui is obtained. Integrate user ui's personal contribution and its social utility to make a winning bid selection, and calculate the reward of ui based on the user's total contribution to complete the positive incentive.The popularity of mobile social networks (MSN) (such as Facebook, Twitter, and Foursquare) has created a new medium for information sharing and dissemination. Pilot studies on real-world datasets [4–6] prove that it is feasible to promote novel products or innovative ideas by considering the interdependent behaviors of mobile users from the social field and the influence propagation on social networks [7, 8]. Traditionally, the network effect means that if a user purchases a public product or service, the more relevant users are willing to accept the purchase of a public product or service. In the mobile crowdsensing service, the participation behavior of mobile users can be regarded as purchasing ““public goods,”“ which means that when users participate in sensing tasks, their related mobile users are more willing to participate, that is, users are easily influenced by acquaintances. Therefore, complex and interdependent user behaviors pose a major challenge to the operation of the crowdsensing platform. More importantly, network effects often exist in closely connected social relationships.As shown in Figure1, this paper attempts to recruit workers for MCS tasks in a novel way, using social networks as the recruitment platform and not relying on a specific MCS platform. First, we build a knowledge graph oriented to crowdsensing on the internal relationship of mobile users on MSN and conduct rule-based attribute inferences. Assuming the user pushes the task to their friends and the affected user accepts the task, the user can get a certain amount of extra rewards in return. The platform integrates user contributions and social effects to select winner users to maximize social welfare. Finally, the platform gives corresponding rewards, which are affected by the user's own social effects and contributions. The main contributions of this article are as follows:(i)
As far as we know, the introduction of knowledge graphs into the crowdsensing incentive mechanism is the first work. We build a knowledge graph of users' social relationships and rule to deduce the social influence between users, so as to obtain the social effects of users.(ii)
Incorporate the user's social network into the design of the incentive mechanism of mobile crowdsensing to encourage users to share recommendation behaviors, thereby promoting sensing tasks and obtaining more sensing users.(iii)
Design social awareness reverse auction (SARA) incentive method, select users based on the net contribution margin to reduce perceived data redundancy, and, at the same time, introduce users' social effects to optimize social welfare.(iv)
Through experimental verification, SARA satisfies user rationality, budget feasibility, and computational efficiency. And, it is better than the comparison algorithm and close to the optimal social welfare.Figure 1
Mobile crowdsensing system structure.


## 2. Related Work

With the continuous development of the application of the crowdsensing system, a series of incentive mechanisms have been proposed [9], mainly from two aspects. On the one hand, it aims to maximize the sensing quality of crowdsensing (such as coverage) under certain restricted conditions. Literature [10] proposed an incentive mechanism considering budget constraints. The maximum weighted coverage under different coverage requirements in crowdsensing is modeled as a reverse auction with limited budget, which is used to maximize the weighted coverage in mobile crowdsourcing. Zhou et al. [11] proposed an online mechanism design to motivate users to participate and assign location-aware tasks to dynamic arrival users subject to capacity constraints (restrictions on the degree of participation). Construct a natural incentive mechanism through multiple rounds of online auctions in the desired time domain. Peng et al. [12] incorporated the consideration of data quality into the design of crowdsensing incentive mechanism. The rewards of participants are determined according to the quality and contribution of users, so as to encourage rational participants to effectively perform crowdsensing tasks. Jiang et al. [13] proposed to introduce a new data layer between the sensing task and the user. Using the similarity of perception tasks and the heterogeneity of users, a joint task selection and user scheduling problem is established on the data layer to maximize the social welfare of the entire system. Jin et al. [14] proposed an incentive framework for Thanos based on reverse combinatorial auctions. Combining the key indicator of worker’s quality of information (QoI), authors design user selection and pricing algorithms for single task and multitask to maximize social welfare.On the other hand, it aims to minimize the cost to ensure a certain level of sensing data quality. Jin et al. [15] designed an incentive mechanism based on reverse combinatorial auctions to achieve low-cost completion of relatively high-quality perception tasks while meeting certain quality requirements for perception tasks. Xu et al. [16] designed two incentive mechanisms MCT-M and MCTTS bidding models. The neural network method is introduced to learn the similarity between users, and the clustering algorithm is used to cluster users without their knowledge. Assign tasks based on the similarity between users to ensure the quality of perceived data. Duan et al. [17] proposed a reward-based collaboration mechanism. If a sufficient number of participants are willing to collaborate, CSP assigns tasks to collaborators and shares the total reward.A common feature of the above mechanisms is that they are all proposed under the assumption that the number of participating users is sufficient. This is the essential difference from the mechanism mentioned in this paper. Some existing mechanisms propose to design incentive mechanisms based on social networks. Nie et al. [18] proposed to use a two-stage Stackelberg game to analyze the participation of mobile users and used reverse induction to analyze the optimal incentive mechanism of crowdsensing service providers. Zhao et al. [19] proposed a three-stage method for social sensing data distribution through D2D communication. This method selects initial seeds by fusing social networks and mobile networks and performs subsequent data forwarding by adapting to the user’s altruistic and selfish incentive constraints, while ensuring the authenticity of the user. Sun et al. [20] considered the social relationship of SU and designed a social awareness incentive mechanism (SAIM). However, it only selects users based on their bids and does not consider the amount of data contribution that users can provide. In the above research, the dissemination of crowdsensing tasks among friends was not introduced into the recruitment of crowdsensing workers. Long et al. [21] proposed a community discovery algorithm based on multidimensional social relationship characteristics. By calculating the minimum spanning tree, connection parameters, and community integration among mobile nodes, the behavior patterns of nodes are abstracted and identified. The matching degree between the sensing task and the characteristic value of the community behavior pattern is calculated, and the distribution of the task is completed by the central node of the community according to the matching degree. Wang et al. [22] proposed that a part of seed users should be selected by considering users’ social relationships and the differences (similarity) of trajectory prediction under the condition of constraining the number of seeds and the total number of workers. However, Wang et al. [22] did not consider the user's sensing quality into the incentive mechanism of crowdsensing and only analyzed the spread of users under social consciousness to select seed users. Although the method proposed in this paper also involves the influence propagation on social networks, it is different from the above research in the following aspects: (1) different optimization goals and constraints; (2) different worker selection algorithms; (3) different user influence reasoning models.In this paper, various types of relevant information are extracted from social networks to assist MCS in inferring expertise. We optimize user contributions based on the user's preference for different tasks and comprehensively consider the social influence between users. The winning bidder is selected based on the user's contribution, and the user's critical reward is paid within the budget constraint.


## 3. User Social Relationship Reasoning

### 3.1. Construction of User Diffusion Based on Knowledge Graph

The knowledge graph oriented to crowdsensing is a network of relationships between users, tasks, geographic locations, and corresponding attributes. Users, tasks, and geographic locations as entities under the crowdsensing system are the most basic elements in the knowledge graph. The relationships describe the objective relationships between concepts, entities, and events, which exist between different entities. The entity relationships under this system include selection, recruitment, and location. The attribute refers to the specific attribute value under the entity, where user attributes include task tendency, common address, sensing time, and user bid price, and attributes of sensing task include task content, description, location, and time.Figure2 describes the user diffusion model of crowdsensing based on the knowledge graph. The model mainly includes three parts: data processing, the construction of ontology related to crowdsensing, and the generation of knowledge graphs of the crowdsensing system. The data source used is structured data, and the data is processed into a triple form to construct a resource description framework. At the same time, a top-down approach is used to construct ontology, which lays the foundation for information extraction. According to the resource description framework and ontology, entities related to crowdsensing and the relationships between entities are extracted. The model is a five-element crowdsensing knowledge base model that includes concepts, examples, relationships, attributes, and rules. The architecture of crowdsensing knowledge base contains three kinds of ontology: mobile node, task, and geographic location. The three entity types of ontology are mobile node, task, and geographic location. The mobile node in this paper is a node that carries sensors and can participate in sensing tasks, and users are a subclass of mobile nodes. The task is the sensing task issued by the platform, which is completed by the sensing user. Geographical location is a specific location where users perform tasks. The introduction and construction process of the basic elements of the crowdsensing user diffusion model based on the knowledge graph is mentioned above.Figure 2
Crowdsensing user diffusion model based on knowledge graph.


### 3.2. Relationship Inference Based on the Knowledge Graph

In the crowdsensing system, the user forwards the task and invites friends to participate in the sensing task. After the friend joins, it brings additional benefits to the user. Construct a knowledge graph oriented to the crowdsensing system for social network users and filter to obtain user attributes related to the system, mainly including {“location,” “interest type,” “execution time,” “willingness to participate”}. Set user’s interest task types including {“air quality,” “environmental monitoring,” “sports,” “movie,” “politics”}. Calculate the matching degree of the subusers recruited by the participating users with the system tasks and their willingness to participate, analyze the user's influence, and obtain the user's social benefits. The greater the user's influence is, the greater the social benefits the user brings.K=<concept,instance,relationship,attribute,rule>, where K is used to represent the knowledge group.Concept=concepti,i=1,…,n. This concept is a set of abstract ontology, such as mobile nodes, tasks, and geographic locations.Instance=instancei,i=1,…,m. This instance is a set of specific examples, such as user i and task t.Attribute=<instancei,propertiesij,valuej>. These attributes are a set of instance attribute values, such as task {<content: taking a photo> | <description: photo format description> | <location: perception location> | <time: task timeliness>}.Relationship=<concepti,relationcc,conceptj>|concepti,relationci,instancej|instancei,relationii,instancej. Relationship shows the relationship between instances, such as < user, choice, task>.Rule=rule|rule=<instancei,newrelationij,instancej>|<concepti,newrelationsij,instancej>|<instancei,propertiesij,newvaluej>based onK. This rule is used to derive new attributes and new relationships. The rule in this article derives new attributes as ure, inofluence, value.Relationship inference uses existing relationship instances to infer new relationships between instances. As shown in Figure3, assuming that the system has five tasks to be performed, Li Ming only recruited Zhang San to participate in the perception task by sharing the perception task. Their task tendencies were different. Zhang San chose the “air quality” task and Li Ming chose the “environmental monitoring” task. They were in the same location as the “park,” and their respective willingness to participate was also different. According to the knowledge graph to match tasks, Zhang San’s task matching degree was Ma = 1 and then Zhang San’s potential contribution was μ = 0.6. The influence (influencei, value) of users Ni is derived based on the attributes and task selection rules among users. In this article, influencei is the influence of the user Ni, and ait.Figure 3
Example of user influence derivation.When calculating the influence of a user, it is not enough to only consider the user entity connected to the user. The attribute characteristics of the user should also be taken into account. The matching degree between recruited subusers and system tasks has a direct impact on superior users.


### 3.3. Optimize Social Welfare

Based on the crowdsensing task specification and the attribute inference of the knowledge graph for crowdsensing, the following questions are raised. Given a taskT=τi,…,τm of a set of spatial units, a group of mobile users N=n1,n2,… on a social network have check-in data (including location) in the task space, and the user's task coverage is used to characterize the perceived quality vi=Coveredni. After the platform releases the task set T, sensing users who want to participate can increase their own social benefits by recruiting their friends to participate in the sensing task and further increase their probability of being selected and their reward after being selected. After the platform receives the user’s bid, it analyzes the user attribute inference generated by the knowledge graph, the user’s location, and the user’s bid, selects the winner user, and, after the platform receives the user’s sensing task data, pays the winner user the corresponding reward. Users who are not selected do not perform any tasks and are not paid. Based on the above theory, the relevant definitions are as follows.Definition 1 (user utility).
The utility of all useri∈Nis defined as(1)ui=pi−ci,i∈W,0,otherwise,where W is a set of winning users, ci is the true cost of user i, and pi is the remuneration obtained by user i.Definition 2 (platform utility).
Platform utility is defined as the total value that the platform can obtain minus the total cost of user sensing tasks. viis the narrow value that users bring to the platform through sensing tasks. Seiis the broad value that users bring to the platform through social relationships. Siis the total value that users bring to the platform, that is, the sum of narrow value and broad value:(2)u0=∑i∈Wvi−pi+Sei=∑i∈WSi−pi.Definition 3 (social welfare).
Social welfare is defined as the overall benefit of the crowdsensing ecosystem, that is, the sum of platform utility and user utility:(3)Sw=∑i∈WSi−bi.
In a real auction, the user's bidbi is equal to the user's real cost ci.
The single run auction (SRA) problem can be defined as in runr, and the platform hopes to maximize the objective function within a certain constraint. The problem in this article belongs to the SRA problem. The goal is to find the final winner user set to maximize social welfare. It can be expressed as(4)w∗=argmaxW∈N∑i∈WSi−bi,s.t.∑i∈Wpi≤B,where N is the set of users who compete to participate in the sensing task and W is the set of winner users. The constraint is that the sum of the rewards of all winner users does not exceed the platform budget B.
In this process, we consider that users who aim to maximize their own benefits will have strategic and selfish behaviors. Assuming that users are rational but selfish, their natural goal is to maximize their respective utility. They may choose to submit forged bids, which may increase their effectiveness. On the contrary, we value the overall benefits of the entire crowdsensing ecosystem and pursue the highest social welfare. For this reason, it is important to solicit real bids from users. We aim to design a dominant strategy mechanism in which each worker has a dominant strategy defined in Definition4 [23].Definition 4 (dominant strategy).
If and only if, for any other strategySti′and any strategy profile of other workers (denoted asSt−i), strategy Stiis the dominant strategy of worker i and satisfiesuiSti,St−i≥Sti′,St−i.
In the auction process of this article, each worker submits a bidΓi,bi to the platform, which includes the task set Γi and bid price bi that she is interested in. Because the worker is of strategic importance, she may announce that the bid deviates from the actual value. One of the goals of the incentive mechanism designed in this paper is to design the real mechanism defined in Definition 5.Definition 5 (authenticity of bid price).
The auction is real if and only if it is the main strategy for each workeri∈Nto bid for its true valueΓi,ci.
In addition to authenticity, another design goal is to ensure that each worker obtains nonnegative utility from participation. If the perception task submitted by the user is duplicated with the perception data that has been submitted, in order to avoid submitting redundant perception data, the perception platform will not pay for this part of the work, which may result in the user’s remuneration becoming lower than the user’s bid. To ensure the sensing user's personal benefits, the user will not participate in this perception task. This attribute is formally defined as personal rationality in Definition6.Definition 6 (user rationality).
The mechanism satisfies the user rationality if and only if each worker's reward is greater than the user's bid price, that is,i∈Nsatisfiesui≥0.


## 3.1. Construction of User Diffusion Based on Knowledge Graph

The knowledge graph oriented to crowdsensing is a network of relationships between users, tasks, geographic locations, and corresponding attributes. Users, tasks, and geographic locations as entities under the crowdsensing system are the most basic elements in the knowledge graph. The relationships describe the objective relationships between concepts, entities, and events, which exist between different entities. The entity relationships under this system include selection, recruitment, and location. The attribute refers to the specific attribute value under the entity, where user attributes include task tendency, common address, sensing time, and user bid price, and attributes of sensing task include task content, description, location, and time.Figure2 describes the user diffusion model of crowdsensing based on the knowledge graph. The model mainly includes three parts: data processing, the construction of ontology related to crowdsensing, and the generation of knowledge graphs of the crowdsensing system. The data source used is structured data, and the data is processed into a triple form to construct a resource description framework. At the same time, a top-down approach is used to construct ontology, which lays the foundation for information extraction. According to the resource description framework and ontology, entities related to crowdsensing and the relationships between entities are extracted. The model is a five-element crowdsensing knowledge base model that includes concepts, examples, relationships, attributes, and rules. The architecture of crowdsensing knowledge base contains three kinds of ontology: mobile node, task, and geographic location. The three entity types of ontology are mobile node, task, and geographic location. The mobile node in this paper is a node that carries sensors and can participate in sensing tasks, and users are a subclass of mobile nodes. The task is the sensing task issued by the platform, which is completed by the sensing user. Geographical location is a specific location where users perform tasks. The introduction and construction process of the basic elements of the crowdsensing user diffusion model based on the knowledge graph is mentioned above.Figure 2
Crowdsensing user diffusion model based on knowledge graph.


## 3.2. Relationship Inference Based on the Knowledge Graph

In the crowdsensing system, the user forwards the task and invites friends to participate in the sensing task. After the friend joins, it brings additional benefits to the user. Construct a knowledge graph oriented to the crowdsensing system for social network users and filter to obtain user attributes related to the system, mainly including {“location,” “interest type,” “execution time,” “willingness to participate”}. Set user’s interest task types including {“air quality,” “environmental monitoring,” “sports,” “movie,” “politics”}. Calculate the matching degree of the subusers recruited by the participating users with the system tasks and their willingness to participate, analyze the user's influence, and obtain the user's social benefits. The greater the user's influence is, the greater the social benefits the user brings.K=<concept,instance,relationship,attribute,rule>, where K is used to represent the knowledge group.Concept=concepti,i=1,…,n. This concept is a set of abstract ontology, such as mobile nodes, tasks, and geographic locations.Instance=instancei,i=1,…,m. This instance is a set of specific examples, such as user i and task t.Attribute=<instancei,propertiesij,valuej>. These attributes are a set of instance attribute values, such as task {<content: taking a photo> | <description: photo format description> | <location: perception location> | <time: task timeliness>}.Relationship=<concepti,relationcc,conceptj>|concepti,relationci,instancej|instancei,relationii,instancej. Relationship shows the relationship between instances, such as < user, choice, task>.Rule=rule|rule=<instancei,newrelationij,instancej>|<concepti,newrelationsij,instancej>|<instancei,propertiesij,newvaluej>based onK. This rule is used to derive new attributes and new relationships. The rule in this article derives new attributes as ure, inofluence, value.Relationship inference uses existing relationship instances to infer new relationships between instances. As shown in Figure3, assuming that the system has five tasks to be performed, Li Ming only recruited Zhang San to participate in the perception task by sharing the perception task. Their task tendencies were different. Zhang San chose the “air quality” task and Li Ming chose the “environmental monitoring” task. They were in the same location as the “park,” and their respective willingness to participate was also different. According to the knowledge graph to match tasks, Zhang San’s task matching degree was Ma = 1 and then Zhang San’s potential contribution was μ = 0.6. The influence (influencei, value) of users Ni is derived based on the attributes and task selection rules among users. In this article, influencei is the influence of the user Ni, and ait.Figure 3
Example of user influence derivation.When calculating the influence of a user, it is not enough to only consider the user entity connected to the user. The attribute characteristics of the user should also be taken into account. The matching degree between recruited subusers and system tasks has a direct impact on superior users.


## 3.3. Optimize Social Welfare

Based on the crowdsensing task specification and the attribute inference of the knowledge graph for crowdsensing, the following questions are raised. Given a taskT=τi,…,τm of a set of spatial units, a group of mobile users N=n1,n2,… on a social network have check-in data (including location) in the task space, and the user's task coverage is used to characterize the perceived quality vi=Coveredni. After the platform releases the task set T, sensing users who want to participate can increase their own social benefits by recruiting their friends to participate in the sensing task and further increase their probability of being selected and their reward after being selected. After the platform receives the user’s bid, it analyzes the user attribute inference generated by the knowledge graph, the user’s location, and the user’s bid, selects the winner user, and, after the platform receives the user’s sensing task data, pays the winner user the corresponding reward. Users who are not selected do not perform any tasks and are not paid. Based on the above theory, the relevant definitions are as follows.Definition 1 (user utility).
The utility of all useri∈Nis defined as(1)ui=pi−ci,i∈W,0,otherwise,where W is a set of winning users, ci is the true cost of user i, and pi is the remuneration obtained by user i.Definition 2 (platform utility).
Platform utility is defined as the total value that the platform can obtain minus the total cost of user sensing tasks. viis the narrow value that users bring to the platform through sensing tasks. Seiis the broad value that users bring to the platform through social relationships. Siis the total value that users bring to the platform, that is, the sum of narrow value and broad value:(2)u0=∑i∈Wvi−pi+Sei=∑i∈WSi−pi.Definition 3 (social welfare).
Social welfare is defined as the overall benefit of the crowdsensing ecosystem, that is, the sum of platform utility and user utility:(3)Sw=∑i∈WSi−bi.
In a real auction, the user's bidbi is equal to the user's real cost ci.
The single run auction (SRA) problem can be defined as in runr, and the platform hopes to maximize the objective function within a certain constraint. The problem in this article belongs to the SRA problem. The goal is to find the final winner user set to maximize social welfare. It can be expressed as(4)w∗=argmaxW∈N∑i∈WSi−bi,s.t.∑i∈Wpi≤B,where N is the set of users who compete to participate in the sensing task and W is the set of winner users. The constraint is that the sum of the rewards of all winner users does not exceed the platform budget B.
In this process, we consider that users who aim to maximize their own benefits will have strategic and selfish behaviors. Assuming that users are rational but selfish, their natural goal is to maximize their respective utility. They may choose to submit forged bids, which may increase their effectiveness. On the contrary, we value the overall benefits of the entire crowdsensing ecosystem and pursue the highest social welfare. For this reason, it is important to solicit real bids from users. We aim to design a dominant strategy mechanism in which each worker has a dominant strategy defined in Definition4 [23].Definition 4 (dominant strategy).
If and only if, for any other strategySti′and any strategy profile of other workers (denoted asSt−i), strategy Stiis the dominant strategy of worker i and satisfiesuiSti,St−i≥Sti′,St−i.
In the auction process of this article, each worker submits a bidΓi,bi to the platform, which includes the task set Γi and bid price bi that she is interested in. Because the worker is of strategic importance, she may announce that the bid deviates from the actual value. One of the goals of the incentive mechanism designed in this paper is to design the real mechanism defined in Definition 5.Definition 5 (authenticity of bid price).
The auction is real if and only if it is the main strategy for each workeri∈Nto bid for its true valueΓi,ci.
In addition to authenticity, another design goal is to ensure that each worker obtains nonnegative utility from participation. If the perception task submitted by the user is duplicated with the perception data that has been submitted, in order to avoid submitting redundant perception data, the perception platform will not pay for this part of the work, which may result in the user’s remuneration becoming lower than the user’s bid. To ensure the sensing user's personal benefits, the user will not participate in this perception task. This attribute is formally defined as personal rationality in Definition6.Definition 6 (user rationality).
The mechanism satisfies the user rationality if and only if each worker's reward is greater than the user's bid price, that is,i∈Nsatisfiesui≥0.


## 4. Incentive Method Based on the Diffusion of Social Users

In view of the user's social network check-in and influence inference based on the knowledge graph, this article proposes a user-oriented incentive method to make user selection, and the author can choose the user who is most beneficial to the platform. Here, the benefits that users bring to the platform through tasks are defined as the sum of the narrow value that users bring to the platform through sensing tasks and the generalized value that users bring to the platform through social relationships. The algorithm will continue to select and add new users until the budget reaches the limit.


### 4.1. Social User Influence Definition

When constructing a knowledge graph for social users to infer the user influence of a user under a specific task, it is not enough to only consider the user entity connected to the user. The user's attribute characteristics should also be taken into account. By extending the PageRank algorithm, a user influence analysis based on attribute characteristics is obtained. The similarity of the user's attribute characteristics shows that the user is willing to establish contact and interact with people with the same interests and hobbies. The higher the similarity of the user is, the greater the possibility of being influenced by the other party.The similarity of attribute characteristics between userViU and user VjUcan be regarded as the difference between two users for a certain attribute characteristic. If the distribution of two users on a certain attribute characteristic is very similar, the similarity will be greater. The similarity simij between user ViU and user VjU on the task attribute feature is defined as(5)simij=cosθ⟶i,θ⟶j,where θ⟶i is the task attribute vector of user ViU and θ⟶j is the task attribute vector of user VjU.Given the recruited user setNi of user entity ViU and the probability of user ViU sharing the sensing task to user, VjU∈Ni is expressed as TPij:(6)TPij=1Ni,where TP represents the relationship transition matrix, TPij is the normalized value, and Ni represents the number of users recruited by user ViU.According to the task attributes provided by the perception platform, the influence of userViU on user VjU is related to the similarity of attribute characteristics. The more similar the topic distribution of two social users, the greater the transition probability between users. The probability that user entity ViU spreads the sensing task and successfully recruits to user entity VjU is SPij:(7)SPij=TPij∗simij,where SP is the similarity transition matrix, which represents the probability of each user successfully recruiting related users.According to the given user entity relationship and the task attribute characteristics of the user entity, the relationship transition matrixTP is obtained, and the similarity transition matrix SP between users is obtained. The user influence analysis based on task attribute characteristics is defined as(8)R=ai,i∈N,R=α∗SP∗R+1−αE,where E is the probability matrix of randomly jumping to any user, E=1, and α are a parameter between 0 and 1 that controls the probability of teleportation, usually α=0.85.


### 4.2. Single-Task Budget Constraints’ User Choice

This paper considers the incentive mechanism of crowdsensing when perceiving users facing a single task under an ideal situation where user information is known. Through the analysis of user influence in Section4.1, the social benefits brought to the platform by users’ recruiting workers through social relationships are characterized as(9)Sei=∑j∈Niaivj,i∈W.According to the sensing information submitted by users and their social contributions, the social welfare created by useri is Swi=Si−bi.Definition 7 (submodule function).
Given functionΨ:2N⟶R, if, for any set∀X⊆Δ⊆N,∀χ∈N\Δ, there is(10)ΨX∪χ−ΨX≥ΨΔ∪χ−ΨΔ,then function Ψ is a submodular function.
Therefore, the social welfare function in definition three is a nonnegative submodule function. When there is only a single task, we only need to select the user with the largest social welfare created under the task in turn and calculate the rewards of the winner users in real time to meet the budget limits. If the user is ultimately not selected to participate in the perception task, thenpk=0, otherwise the reward is(11)pk=bk+Sw∗−Sw−k∗,where Sw∗ is the maximization of the objective function when user i is involved and Sw−k∗ is the maximization of the objective function when user i is not involved. They are defined as follows:(12)Sw∗=maxW∈N∑i∈WSi−bi,Sw−k∗=maxW∈N∑i∈WSi−bi,where N−k represents the user set that does not contain user k. Therefore, when facing a single task, we select the winning users based on the social welfare created by the users and pay compensation based on the difference in their contribution to complete the positive incentive.


### 4.3. User Selection Algorithm under Multitask Budget Constraints

Although the incentive mechanism based on a single task is easy to implement, there are serious problems in efficiency. When faced with multiple tasks issued by the platform, the computational efficiency is too high. In addition, in the process of calculating user compensation, it is necessary to repeatedly calculate the social welfare created by users, which is very expensive. Therefore, the problem of low efficiency makes this incentive mechanism unsuitable for adoption on large social networks. Therefore, this section proposes a social awareness incentive mechanism oriented to multitask greed, with the goal of maximizing system social welfare.First, some definitions are introduced to clarify in detail the social perception incentive mechanism of greed, including user selection rules and payment rules.Definition 8 (user contribution).
User contribution is defined as the sum of the total value of all tasks that user i can complete:(13)Vi=∑τ∈ΓiSiτ,where Γi is the set of tasks that the user can complete.Definition 9 (winner set contribution).
Given a group of winner users, denoted as W, the winner set contribution is the sum of the contributions of all the winner users:(14)MW=∑i∈WVi.Definition 10 (user edge contribution).
Given a group of winner user setW, the edge contribution of userk∉Wis the gain brought to the winner set contribution:(15)MkW=MW∪k−MW.
The marginal contribution of users is a key factor in the greedy society sensing and incentive mechanism. In the face of multitasking and multiuser, we propose a social awareness incentive mechanism based on greed in order to reduce the computational complexity. The platform selects a group of users to complete the sensing task. The goal is to maximize the social welfare of the system, which can be optimized as the following form:(16)w∗=argmaxW∈N∑i∈W∑τ∈ΓSiτ−∑i∈Wbi,=argmaxW∈N∑i∈WVi−∑i∈Wbi,s.t.∑i∈Wpi≤B.
The selection of users in SARA is based on the user's net contribution margin, and the ranking of the winner users is as follows:(17)MΩ1−bΩ1≥…≥MΩW−bΩW,where Ω1 is the user index ranked first among the winner users. In SARA, ωi is the user's net contribution margin and B is the budget constraint of the platform.
In order to calculate the remuneration paid to userJ, sort according to the net contribution margin of users in N−j+. In each repeated loop, find the user with the largest net contribution margin and update the remuneration of user j to maximize it by replacing. At least one user in N−j+ has been selected, making user j the winner user, where N−j+ represents the set of net contribution margin not less than zero and does not include user j. The users in H are sorted in the order of decreasing net contribution margin as follows:(18)M˜φ1−bφ1≥…M˜φn−bφn≥…,where φn is the index of the user at position n in the sequence and M˜φn=MH∪φn−MH.


### 4.4. Algorithm Validity Analysis

When facing a single task, we aim to design a mechanism that maximizes social welfare while ensuring authenticity. In this part, we prove that the proposed incentive method satisfies the authenticity of user bidding and user rationality. The authenticity of user bids means that the user's utility will not be improved by users’ submitting bids that deviate from their true cost prices. Before proving the authenticity, first rewrite the user's utility formula:(19)uk=pk−ck,=bk+Sw∗−Sw−k∗−ck.Lemma 1.
The incentive mechanism proposed is to satisfy the authenticity of user bidding.Proof.
When userk is honest, there is bk=ck; when user k is dishonest, namely, bk≠ck, there are the following two situations.(i)
Case 1 (bk>ck): in this case, we consider the following three cases.•
(a) Case 1.1： when the user is honest, userk is the winner; when the user submits bk>ck, user k is still the winner.In this case, when the user is honest, the user utility isuk=Sw∗−Sw−k∗, and when the user is dishonest, the user utility is u˜k=S˜w∗−S˜w−k∗+bk−ck. Since the user set of winners that does not include user k is constant regardless of whether user k is honest or not, so S˜w−k∗=S˜w−k∗, and uk−u˜k can be calculated as(20)uk−u˜k=Sw∗−S˜w∗−bk+ck,=∑i∈WSi−ci−∑i∈WSi−ci+ck−bk−bk+ck=0,where the utility gain of userk is 0, so the user's income cannot be improved in this case.•
(b) Case 1.2： When the user is honest, userk is the winner; when the user submits bk>ck, user k is not the winner. In this case, the user benefit when the user is dishonest, u˜k=0, and when the user is honest, the user benefit is(21)uk=pk−ck,=Sw∗−Sw−k∗+bk−ck,=Sw∗−Sw−k∗,≥0.Therefore,uk≥u˜k.•
(c) Case 1.3： when the user is honest, userk is not the winner; when the user submits bk>ck, user k is not the winner. In this case, k.(ii)
Case 2 (bk<ck): in this case, we consider the following three cases.•
(a) Case 2.1： when the user is honest, userk is the winner; when the user submits bk<ck, user k is still the winner. The proof of this case is the same as Case 1.1.•
(b) Case 2.2： when the user is honest, userk is not the winner; when the user submits bk<ck, user k is the winner. In this case,(22)u˜k=S˜w∗−S˜w−k∗+bk−ck,=S˜w∗−Sw∗+bk−ck,=∑i∈WSi−∑i∈W,i≠kci−bk+bk−ck,=∑i∈WSi−∑i∈Wci−Sw∗≤0,where∑i∈WSi−∑i∈Wci is the social welfare when the winner user set includes user k, which is obviously smaller than the optimal social welfare Sw∗ when user k is honest. In this case, user k's social benefits will not increase.•
(c) Case 2.3： when the user is honest, userk is not the winner; when the user submits bk<ck, user K is not the winner. In this case, uk=u˜k=0.Lemma 2.
This incentive mechanism satisfies user rationality.Proof.
Personal rationality means that the user's income cannot be negative. For users who are not selected, their income is zero; for the winner users who participate in the perception task, their income is(23)uk=pk−ck,=Sw∗−Sw−k∗≥0.
In summary, the incentive mechanism based on social relationships meets the authenticity of bidding and user rationality.
A greedy social awareness incentive mechanism is proposed for multitasking. Here, it will be proved that it satisfies user rationality, bid authenticity, and computational efficiency. Before the proof, first introduce some symbols and properties for convenience. (i)Ω• represents the function mapping of the user index when sorted in the descending order. (ii) Mnn=MWn−1∪Ωn−MWn−1 represents the marginal contribution value of Ωn.Lemma 3 (user rationality).
The proposed mechanism satisfies user rationality.Proof.
For then user in the formula, Mnn−bΩn≥Mφn−bφn is satisfied, so Mnn−Mφn−bφn≥bΩn. At the same time, there is pΩn≥Mnn−Mφn−bφn in the algorithm. So, the utility of each user is nonnegative, namely, pΩn≥bΩn. Therefore, the greedy social awareness incentive mechanism is rational for users.Lemma 4 (authenticity of bids).
The proposed mechanism satisfies the authenticity.Proof.
The auction mechanism is real, and if and only if the selection rules are monotonous, the reward for each winning user is a critical value. The monotonous selection rule is that when a user wins the task qualification with bi, he can still win the task qualification with a bid lower than bi. The compensation threshold means that when the user's bid is higher than this threshold, the user will not be selected.
Therefore, it is only necessary to prove that the user's selection rule is monotonous, and the reward of each winning user is a critical value, and then, it can be proved that the proposed incentive mechanism satisfies the authenticity.
Monotonic:user selection is monotonous.Proof.
When a user bids with a lower bid, the user's net contribution margin will increase so that the user advances in the ranking and has a greater chance of being selected as the winner. When a user wins by biddingbi, he can still win by bidding with a bid lower than bi. Therefore, the user's selection rule is monotonous.
Critical value of payment:the remuneration paid to each user is the critical value.Proof.
According to the payment rules,pΩn=maxωm≥0,B−∑j−1n−1pj≥0Mnm−M˜φm−bφm can be obtained. When bΩn>pΩn, there is bΩn>Mnm−M˜φm−bφm for all ωm≥0, namely, Mnm−bΩn<M˜φm−bφm. Ωn will be after m in the descending order of net contribution margin, that is, ωΩn<0; then, Ωn will not be selected as the winner user. Therefore, pΩn is the critical reward of user Ωn.
By proving the monotonicity of the user selection rules and the critical value of payment, it can be concluded that the proposed incentive mechanism satisfies the authenticity.Lemma 5 (computational efficiency).
The proposed multitask greedy incentive mechanism is computationally efficient.Proof.
The computational efficiency means that the user selection and payment rules of the proposed mechanism can be solved in polynomial time. Assuming that there areN sensing users, in user selection, the time it takes to find the user with the largest net contribution margin does not exceed ON+, and the time it takes to calculate each contribution margin does not exceed ON2, in each while loop (line 2–12 in Algorithm 1). When calculating user compensation, in the repeat loop (Lines 5–9 in Algorithm 1), the time spent calculating each contribution margin does not exceed ON2, and the time it takes to find the user with the largest net contribution margin does not exceed ON+.Algorithm 1:SARA greedy social awareness incentive.
(1)
W←∅,ph←0;(2)
whileωi≥0&&B≥0do(3)
j←argmaxh∈N+\WMhW−bh;(4)
Η←∅;(5)
repeat(6)
k←argmaxh∈N−j+\ΗMhW−bh;(7)
pj←maxpj,minMjΗ−MkΗ−bk,MjΗ;(8)
Η←Η∪k;(9)
untilN−j+\Η=∅;(10)
W←W∪j;(11)
B←B−pj;(12)
end while(13)
returnW,pj,∀j∈W;


## 4.1. Social User Influence Definition

When constructing a knowledge graph for social users to infer the user influence of a user under a specific task, it is not enough to only consider the user entity connected to the user. The user's attribute characteristics should also be taken into account. By extending the PageRank algorithm, a user influence analysis based on attribute characteristics is obtained. The similarity of the user's attribute characteristics shows that the user is willing to establish contact and interact with people with the same interests and hobbies. The higher the similarity of the user is, the greater the possibility of being influenced by the other party.The similarity of attribute characteristics between userViU and user VjUcan be regarded as the difference between two users for a certain attribute characteristic. If the distribution of two users on a certain attribute characteristic is very similar, the similarity will be greater. The similarity simij between user ViU and user VjU on the task attribute feature is defined as(5)simij=cosθ⟶i,θ⟶j,where θ⟶i is the task attribute vector of user ViU and θ⟶j is the task attribute vector of user VjU.Given the recruited user setNi of user entity ViU and the probability of user ViU sharing the sensing task to user, VjU∈Ni is expressed as TPij:(6)TPij=1Ni,where TP represents the relationship transition matrix, TPij is the normalized value, and Ni represents the number of users recruited by user ViU.According to the task attributes provided by the perception platform, the influence of userViU on user VjU is related to the similarity of attribute characteristics. The more similar the topic distribution of two social users, the greater the transition probability between users. The probability that user entity ViU spreads the sensing task and successfully recruits to user entity VjU is SPij:(7)SPij=TPij∗simij,where SP is the similarity transition matrix, which represents the probability of each user successfully recruiting related users.According to the given user entity relationship and the task attribute characteristics of the user entity, the relationship transition matrixTP is obtained, and the similarity transition matrix SP between users is obtained. The user influence analysis based on task attribute characteristics is defined as(8)R=ai,i∈N,R=α∗SP∗R+1−αE,where E is the probability matrix of randomly jumping to any user, E=1, and α are a parameter between 0 and 1 that controls the probability of teleportation, usually α=0.85.


## 4.2. Single-Task Budget Constraints’ User Choice

This paper considers the incentive mechanism of crowdsensing when perceiving users facing a single task under an ideal situation where user information is known. Through the analysis of user influence in Section4.1, the social benefits brought to the platform by users’ recruiting workers through social relationships are characterized as(9)Sei=∑j∈Niaivj,i∈W.According to the sensing information submitted by users and their social contributions, the social welfare created by useri is Swi=Si−bi.Definition 7 (submodule function).
Given functionΨ:2N⟶R, if, for any set∀X⊆Δ⊆N,∀χ∈N\Δ, there is(10)ΨX∪χ−ΨX≥ΨΔ∪χ−ΨΔ,then function Ψ is a submodular function.
Therefore, the social welfare function in definition three is a nonnegative submodule function. When there is only a single task, we only need to select the user with the largest social welfare created under the task in turn and calculate the rewards of the winner users in real time to meet the budget limits. If the user is ultimately not selected to participate in the perception task, thenpk=0, otherwise the reward is(11)pk=bk+Sw∗−Sw−k∗,where Sw∗ is the maximization of the objective function when user i is involved and Sw−k∗ is the maximization of the objective function when user i is not involved. They are defined as follows:(12)Sw∗=maxW∈N∑i∈WSi−bi,Sw−k∗=maxW∈N∑i∈WSi−bi,where N−k represents the user set that does not contain user k. Therefore, when facing a single task, we select the winning users based on the social welfare created by the users and pay compensation based on the difference in their contribution to complete the positive incentive.


## 4.3. User Selection Algorithm under Multitask Budget Constraints

Although the incentive mechanism based on a single task is easy to implement, there are serious problems in efficiency. When faced with multiple tasks issued by the platform, the computational efficiency is too high. In addition, in the process of calculating user compensation, it is necessary to repeatedly calculate the social welfare created by users, which is very expensive. Therefore, the problem of low efficiency makes this incentive mechanism unsuitable for adoption on large social networks. Therefore, this section proposes a social awareness incentive mechanism oriented to multitask greed, with the goal of maximizing system social welfare.First, some definitions are introduced to clarify in detail the social perception incentive mechanism of greed, including user selection rules and payment rules.Definition 8 (user contribution).
User contribution is defined as the sum of the total value of all tasks that user i can complete:(13)Vi=∑τ∈ΓiSiτ,where Γi is the set of tasks that the user can complete.Definition 9 (winner set contribution).
Given a group of winner users, denoted as W, the winner set contribution is the sum of the contributions of all the winner users:(14)MW=∑i∈WVi.Definition 10 (user edge contribution).
Given a group of winner user setW, the edge contribution of userk∉Wis the gain brought to the winner set contribution:(15)MkW=MW∪k−MW.
The marginal contribution of users is a key factor in the greedy society sensing and incentive mechanism. In the face of multitasking and multiuser, we propose a social awareness incentive mechanism based on greed in order to reduce the computational complexity. The platform selects a group of users to complete the sensing task. The goal is to maximize the social welfare of the system, which can be optimized as the following form:(16)w∗=argmaxW∈N∑i∈W∑τ∈ΓSiτ−∑i∈Wbi,=argmaxW∈N∑i∈WVi−∑i∈Wbi,s.t.∑i∈Wpi≤B.
The selection of users in SARA is based on the user's net contribution margin, and the ranking of the winner users is as follows:(17)MΩ1−bΩ1≥…≥MΩW−bΩW,where Ω1 is the user index ranked first among the winner users. In SARA, ωi is the user's net contribution margin and B is the budget constraint of the platform.
In order to calculate the remuneration paid to userJ, sort according to the net contribution margin of users in N−j+. In each repeated loop, find the user with the largest net contribution margin and update the remuneration of user j to maximize it by replacing. At least one user in N−j+ has been selected, making user j the winner user, where N−j+ represents the set of net contribution margin not less than zero and does not include user j. The users in H are sorted in the order of decreasing net contribution margin as follows:(18)M˜φ1−bφ1≥…M˜φn−bφn≥…,where φn is the index of the user at position n in the sequence and M˜φn=MH∪φn−MH.


## 4.4. Algorithm Validity Analysis

When facing a single task, we aim to design a mechanism that maximizes social welfare while ensuring authenticity. In this part, we prove that the proposed incentive method satisfies the authenticity of user bidding and user rationality. The authenticity of user bids means that the user's utility will not be improved by users’ submitting bids that deviate from their true cost prices. Before proving the authenticity, first rewrite the user's utility formula:(19)uk=pk−ck,=bk+Sw∗−Sw−k∗−ck.Lemma 1.
The incentive mechanism proposed is to satisfy the authenticity of user bidding.Proof.
When userk is honest, there is bk=ck; when user k is dishonest, namely, bk≠ck, there are the following two situations.(i)
Case 1 (bk>ck): in this case, we consider the following three cases.•
(a) Case 1.1： when the user is honest, userk is the winner; when the user submits bk>ck, user k is still the winner.In this case, when the user is honest, the user utility isuk=Sw∗−Sw−k∗, and when the user is dishonest, the user utility is u˜k=S˜w∗−S˜w−k∗+bk−ck. Since the user set of winners that does not include user k is constant regardless of whether user k is honest or not, so S˜w−k∗=S˜w−k∗, and uk−u˜k can be calculated as(20)uk−u˜k=Sw∗−S˜w∗−bk+ck,=∑i∈WSi−ci−∑i∈WSi−ci+ck−bk−bk+ck=0,where the utility gain of userk is 0, so the user's income cannot be improved in this case.•
(b) Case 1.2： When the user is honest, userk is the winner; when the user submits bk>ck, user k is not the winner. In this case, the user benefit when the user is dishonest, u˜k=0, and when the user is honest, the user benefit is(21)uk=pk−ck,=Sw∗−Sw−k∗+bk−ck,=Sw∗−Sw−k∗,≥0.Therefore,uk≥u˜k.•
(c) Case 1.3： when the user is honest, userk is not the winner; when the user submits bk>ck, user k is not the winner. In this case, k.(ii)
Case 2 (bk<ck): in this case, we consider the following three cases.•
(a) Case 2.1： when the user is honest, userk is the winner; when the user submits bk<ck, user k is still the winner. The proof of this case is the same as Case 1.1.•
(b) Case 2.2： when the user is honest, userk is not the winner; when the user submits bk<ck, user k is the winner. In this case,(22)u˜k=S˜w∗−S˜w−k∗+bk−ck,=S˜w∗−Sw∗+bk−ck,=∑i∈WSi−∑i∈W,i≠kci−bk+bk−ck,=∑i∈WSi−∑i∈Wci−Sw∗≤0,where∑i∈WSi−∑i∈Wci is the social welfare when the winner user set includes user k, which is obviously smaller than the optimal social welfare Sw∗ when user k is honest. In this case, user k's social benefits will not increase.•
(c) Case 2.3： when the user is honest, userk is not the winner; when the user submits bk<ck, user K is not the winner. In this case, uk=u˜k=0.Lemma 2.
This incentive mechanism satisfies user rationality.Proof.
Personal rationality means that the user's income cannot be negative. For users who are not selected, their income is zero; for the winner users who participate in the perception task, their income is(23)uk=pk−ck,=Sw∗−Sw−k∗≥0.
In summary, the incentive mechanism based on social relationships meets the authenticity of bidding and user rationality.
A greedy social awareness incentive mechanism is proposed for multitasking. Here, it will be proved that it satisfies user rationality, bid authenticity, and computational efficiency. Before the proof, first introduce some symbols and properties for convenience. (i)Ω• represents the function mapping of the user index when sorted in the descending order. (ii) Mnn=MWn−1∪Ωn−MWn−1 represents the marginal contribution value of Ωn.Lemma 3 (user rationality).
The proposed mechanism satisfies user rationality.Proof.
For then user in the formula, Mnn−bΩn≥Mφn−bφn is satisfied, so Mnn−Mφn−bφn≥bΩn. At the same time, there is pΩn≥Mnn−Mφn−bφn in the algorithm. So, the utility of each user is nonnegative, namely, pΩn≥bΩn. Therefore, the greedy social awareness incentive mechanism is rational for users.Lemma 4 (authenticity of bids).
The proposed mechanism satisfies the authenticity.Proof.
The auction mechanism is real, and if and only if the selection rules are monotonous, the reward for each winning user is a critical value. The monotonous selection rule is that when a user wins the task qualification with bi, he can still win the task qualification with a bid lower than bi. The compensation threshold means that when the user's bid is higher than this threshold, the user will not be selected.
Therefore, it is only necessary to prove that the user's selection rule is monotonous, and the reward of each winning user is a critical value, and then, it can be proved that the proposed incentive mechanism satisfies the authenticity.
Monotonic:user selection is monotonous.Proof.
When a user bids with a lower bid, the user's net contribution margin will increase so that the user advances in the ranking and has a greater chance of being selected as the winner. When a user wins by biddingbi, he can still win by bidding with a bid lower than bi. Therefore, the user's selection rule is monotonous.
Critical value of payment:the remuneration paid to each user is the critical value.Proof.
According to the payment rules,pΩn=maxωm≥0,B−∑j−1n−1pj≥0Mnm−M˜φm−bφm can be obtained. When bΩn>pΩn, there is bΩn>Mnm−M˜φm−bφm for all ωm≥0, namely, Mnm−bΩn<M˜φm−bφm. Ωn will be after m in the descending order of net contribution margin, that is, ωΩn<0; then, Ωn will not be selected as the winner user. Therefore, pΩn is the critical reward of user Ωn.
By proving the monotonicity of the user selection rules and the critical value of payment, it can be concluded that the proposed incentive mechanism satisfies the authenticity.Lemma 5 (computational efficiency).
The proposed multitask greedy incentive mechanism is computationally efficient.Proof.
The computational efficiency means that the user selection and payment rules of the proposed mechanism can be solved in polynomial time. Assuming that there areN sensing users, in user selection, the time it takes to find the user with the largest net contribution margin does not exceed ON+, and the time it takes to calculate each contribution margin does not exceed ON2, in each while loop (line 2–12 in Algorithm 1). When calculating user compensation, in the repeat loop (Lines 5–9 in Algorithm 1), the time spent calculating each contribution margin does not exceed ON2, and the time it takes to find the user with the largest net contribution margin does not exceed ON+.Algorithm 1:SARA greedy social awareness incentive.
(1)
W←∅,ph←0;(2)
whileωi≥0&&B≥0do(3)
j←argmaxh∈N+\WMhW−bh;(4)
Η←∅;(5)
repeat(6)
k←argmaxh∈N−j+\ΗMhW−bh;(7)
pj←maxpj,minMjΗ−MkΗ−bk,MjΗ;(8)
Η←Η∪k;(9)
untilN−j+\Η=∅;(10)
W←W∪j;(11)
B←B−pj;(12)
end while(13)
returnW,pj,∀j∈W;


## 5. Experimental Verification and Analysis

In this section, we introduce the baseline method used in the simulation as well as the simulation settings and results. First, compare SARA with the baseline to prove its competitiveness. Then, verify SARA's user rationality, budget feasibility, and authenticity of user bids.


### 5.1. Baseline Method and Simulation Settings

The goal of the method proposed in this paper is to maximize social welfare under budget constraints, so the baseline method should also meet the budget constraints. The first baseline method is a modified version of the QoI-SRC auction [14], which integrates budget constraints into the QoI-SRC winner determination problem. The QoI-SRC auction has proved to be close to the best social welfare, and the improved QoI-SRC auction is called the SRC auction. Another baseline method is OPT [24], which represents the estimated upper limit of the best solution to the SRA problem when the platform fully understands the user's real bid. Since calculating the best solution to the SRA problem is very time-consuming and cannot be calculated in a reasonable time as the problem size grows, we use the best upper limit instead of the best itself as the benchmark.Aiming at the impact of the number of users, budget, and number of tasks on social welfare, the experimental parameters are set in Table1 to simulate the SRA problem, and experimental observations are made. In setting I, the fixed number of tasks is 500, and the budget is set to 600 and 800. The number of users is used as an independent variable from 100 to 300. In setting II, the number of fixed tasks is set to 100 and 200. In this case, the budget is used as an independent variable from 100 to 500. In setting III, the fixed budget constraint is 200, and the user sets 100 and 200. The number of tasks is used as an independent variable from 100 to 500. Among them, the sensing data quality qi provided by the user, the sensing cost ci, the task quality requirement Qj, and the task set Γi selected by the user will be generated uniformly and randomly selected from the range given in Table 1. Among them, the maximum task set Γi that the user can perform is Γi tasks randomly selected from T.Table 1
Parameter settings.
qiciQjΓiNBTI[2, 4][4, 8][10, 13][20, 30][100, 300]600, 800500II[2, 4][4, 8][10, 13][20, 30]100, 200[100, 500]500III[2, 4][4, 8][10, 13][20, 30]100, 200200[100, 500]Table2 shows the experimental settings for user rationality, budget feasibility, and bid authenticity verification. Set the number of users, budget and tasks given in IV, and observe whether the user's income and expenditure under this setting meets the user's rationality. In setting V, given the number of users and the number of tasks, use the budget as an independent variable to observe whether the relationship between the true total expenditure and the budget meets the budget feasibility under this setting. In setting VI, given the number of users, budgets, and tasks, a winning user and a failed user are randomly selected on this basis, and the profitability of submitting different bids is observed, and the graph shows whether the bid authenticity is satisfied. The parameter settings in Tables 1 and 2 are not deliberately selected, so the experimental results will not be lost. And, in Tables 1 and 2, we only consider settings with continuous quality requirements.Table 2
Parameter settings.
qiciQjΓiNBTIV[2, 4][4, 8][10, 13][20, 30]5001000500V[2, 4][4, 8][10, 13][20, 30]300[0, 1000]500VI[ 2,4][4, 8][10, 13][20, 30]100500500


### 5.2. Simulation Results

The social welfare comparison of SARA, SRC, and OPT is shown in the figure. It can be observed that social welfare increases with the increase in the number of users when the budget is fixed, until the budget limit reaches the saturation level from Figure4. Among them, OPT is the best solution to the SRA problem. From Figure 4, it can be concluded that SARA is close to the best social welfare and far higher than the social welfare of the baseline SRC under the same number of users. SRC performed the worst among the three, mainly because it was over-reliant on the budget and was limited by the budget. Therefore, the social welfare generated by SRC in Figure 4 does not increase with the increase in the number of users. However, it can be clearly seen in Figure 5 that it is linearly increasing. However, the number of users does not affect it, mainly, because of its excessive dependence on budget costs.Figure 4
The impact of the number of users on social welfare.Figure 5
The impact of the budget on social welfare.In Figure5, it can be observed that social welfare increases with the increase of the budget when the number of users is fixed. When the number of users is 100 and the budget is 450, the social welfare of SARA and OPT tends to be stable. When the budget reaches 450 and the number of users is 200, the social welfare of SARA and OPT is still steadily increasing compared with the number of users of 100. SRC increases as the budget increases, but it is far lower than the social welfare of SARA and OPT. This is because SRC chooses to perceive users based on the initial marginal social welfare effectiveness to select new winners, rather than updating the effective marginal contribution in each iteration such as SARA.Figure6 shows that the social welfare of SARA, SRC, and OPT increases with the number of tasks. For SARA and OPT, the budget is sufficient under this setting, but SRC is growing slowly due to budget constraints. Among them, SARA produces social welfare after the number of tasks reaches 200 and gradually approaches the best social welfare of OPT. The main reason is that the set of tasks selected by users in SARA is large. In the case of a small number of tasks, users cannot meet their balance of expenditures. It can be seen that the current SARA is suitable for larger-scale problems.Figure 6
The impact of the number of tasks on social welfare.User rationality, as shown in Definition6, requires that the labor remuneration obtained by the user through the sensing task is greater than the user cost submitted by the user to ensure that the user's benefit is positive. The experiment is set to IV in Table 2, fixed number of users, budget, and number of tasks. For each winning user, the total cost and the reward he received are plotted in Figure 7. In Figure 7, the abscissa is the serial number of the user who won the bid, the plus sign represents the reward that the user receives after completing the sensing task, and the circle represents the user’s bid price. Obviously, the user’s reward is always greater than the corresponding total cost. It proves the user rationality of SARA.Figure 7
SARA user rationality test.Budget feasibility requires that the total expenditure paid by the platform to sensing users cannot exceed the platform's budget, and the task should be completed within the budget. The experiment is set to V in Table2. The number of users and the number of tasks are fixed, and the budget is used as an independent variable to vary from 0 to 1000 with a step length of 100. We observe the total expenditure of this mechanism under different budgets. For each fixed budget, we calculate the actual total payment of the requester and display the result in Figure 8. From Figure 8, we can understand that the total payment is close to the budget when the budget is small. Due to the limitation of the number of workers, the total payment will reach saturation level when the budget is large. Obviously, the total payment never exceeded the budget, which proved the budget feasibility of SARA.Figure 8
Budget feasibility verification.The authenticity of user bids, as shown in Definition5, requires that regardless of whether the winner submits a lower or higher bid than the actual bid, it will not increase its own profit, and the loser who submits lower than the real bid will not become a winning user. This means that the user's false bid will not change the user's own income. Given the parameter settings of VII in Table 2, fixed number of users, budget, and number of tasks, we randomly select winner with a true bid of 7 and loser with a true bid of 7 from the set of all workers and use the actual bids of the costs of winner and loser to understand how their utility changes. The cost authenticity test of winner and loser is shown in Figure 9. In these several situations, we can observe that when a worker bids for its true value, its utility is maximized. Regardless of whether the user is a winner or a loser, the user cannot increase its utility through dishonest bids, which proves the authenticity of SARA's bidding.Figure 9
Authenticity verification of SARA. (a) Cost authenticity of winner. (b) Cost authenticity of loser.
(a)(b)


## 5.1. Baseline Method and Simulation Settings

The goal of the method proposed in this paper is to maximize social welfare under budget constraints, so the baseline method should also meet the budget constraints. The first baseline method is a modified version of the QoI-SRC auction [14], which integrates budget constraints into the QoI-SRC winner determination problem. The QoI-SRC auction has proved to be close to the best social welfare, and the improved QoI-SRC auction is called the SRC auction. Another baseline method is OPT [24], which represents the estimated upper limit of the best solution to the SRA problem when the platform fully understands the user's real bid. Since calculating the best solution to the SRA problem is very time-consuming and cannot be calculated in a reasonable time as the problem size grows, we use the best upper limit instead of the best itself as the benchmark.Aiming at the impact of the number of users, budget, and number of tasks on social welfare, the experimental parameters are set in Table1 to simulate the SRA problem, and experimental observations are made. In setting I, the fixed number of tasks is 500, and the budget is set to 600 and 800. The number of users is used as an independent variable from 100 to 300. In setting II, the number of fixed tasks is set to 100 and 200. In this case, the budget is used as an independent variable from 100 to 500. In setting III, the fixed budget constraint is 200, and the user sets 100 and 200. The number of tasks is used as an independent variable from 100 to 500. Among them, the sensing data quality qi provided by the user, the sensing cost ci, the task quality requirement Qj, and the task set Γi selected by the user will be generated uniformly and randomly selected from the range given in Table 1. Among them, the maximum task set Γi that the user can perform is Γi tasks randomly selected from T.Table 1
Parameter settings.
qiciQjΓiNBTI[2, 4][4, 8][10, 13][20, 30][100, 300]600, 800500II[2, 4][4, 8][10, 13][20, 30]100, 200[100, 500]500III[2, 4][4, 8][10, 13][20, 30]100, 200200[100, 500]Table2 shows the experimental settings for user rationality, budget feasibility, and bid authenticity verification. Set the number of users, budget and tasks given in IV, and observe whether the user's income and expenditure under this setting meets the user's rationality. In setting V, given the number of users and the number of tasks, use the budget as an independent variable to observe whether the relationship between the true total expenditure and the budget meets the budget feasibility under this setting. In setting VI, given the number of users, budgets, and tasks, a winning user and a failed user are randomly selected on this basis, and the profitability of submitting different bids is observed, and the graph shows whether the bid authenticity is satisfied. The parameter settings in Tables 1 and 2 are not deliberately selected, so the experimental results will not be lost. And, in Tables 1 and 2, we only consider settings with continuous quality requirements.Table 2
Parameter settings.
qiciQjΓiNBTIV[2, 4][4, 8][10, 13][20, 30]5001000500V[2, 4][4, 8][10, 13][20, 30]300[0, 1000]500VI[ 2,4][4, 8][10, 13][20, 30]100500500


## 5.2. Simulation Results

The social welfare comparison of SARA, SRC, and OPT is shown in the figure. It can be observed that social welfare increases with the increase in the number of users when the budget is fixed, until the budget limit reaches the saturation level from Figure4. Among them, OPT is the best solution to the SRA problem. From Figure 4, it can be concluded that SARA is close to the best social welfare and far higher than the social welfare of the baseline SRC under the same number of users. SRC performed the worst among the three, mainly because it was over-reliant on the budget and was limited by the budget. Therefore, the social welfare generated by SRC in Figure 4 does not increase with the increase in the number of users. However, it can be clearly seen in Figure 5 that it is linearly increasing. However, the number of users does not affect it, mainly, because of its excessive dependence on budget costs.Figure 4
The impact of the number of users on social welfare.Figure 5
The impact of the budget on social welfare.In Figure5, it can be observed that social welfare increases with the increase of the budget when the number of users is fixed. When the number of users is 100 and the budget is 450, the social welfare of SARA and OPT tends to be stable. When the budget reaches 450 and the number of users is 200, the social welfare of SARA and OPT is still steadily increasing compared with the number of users of 100. SRC increases as the budget increases, but it is far lower than the social welfare of SARA and OPT. This is because SRC chooses to perceive users based on the initial marginal social welfare effectiveness to select new winners, rather than updating the effective marginal contribution in each iteration such as SARA.Figure6 shows that the social welfare of SARA, SRC, and OPT increases with the number of tasks. For SARA and OPT, the budget is sufficient under this setting, but SRC is growing slowly due to budget constraints. Among them, SARA produces social welfare after the number of tasks reaches 200 and gradually approaches the best social welfare of OPT. The main reason is that the set of tasks selected by users in SARA is large. In the case of a small number of tasks, users cannot meet their balance of expenditures. It can be seen that the current SARA is suitable for larger-scale problems.Figure 6
The impact of the number of tasks on social welfare.User rationality, as shown in Definition6, requires that the labor remuneration obtained by the user through the sensing task is greater than the user cost submitted by the user to ensure that the user's benefit is positive. The experiment is set to IV in Table 2, fixed number of users, budget, and number of tasks. For each winning user, the total cost and the reward he received are plotted in Figure 7. In Figure 7, the abscissa is the serial number of the user who won the bid, the plus sign represents the reward that the user receives after completing the sensing task, and the circle represents the user’s bid price. Obviously, the user’s reward is always greater than the corresponding total cost. It proves the user rationality of SARA.Figure 7
SARA user rationality test.Budget feasibility requires that the total expenditure paid by the platform to sensing users cannot exceed the platform's budget, and the task should be completed within the budget. The experiment is set to V in Table2. The number of users and the number of tasks are fixed, and the budget is used as an independent variable to vary from 0 to 1000 with a step length of 100. We observe the total expenditure of this mechanism under different budgets. For each fixed budget, we calculate the actual total payment of the requester and display the result in Figure 8. From Figure 8, we can understand that the total payment is close to the budget when the budget is small. Due to the limitation of the number of workers, the total payment will reach saturation level when the budget is large. Obviously, the total payment never exceeded the budget, which proved the budget feasibility of SARA.Figure 8
Budget feasibility verification.The authenticity of user bids, as shown in Definition5, requires that regardless of whether the winner submits a lower or higher bid than the actual bid, it will not increase its own profit, and the loser who submits lower than the real bid will not become a winning user. This means that the user's false bid will not change the user's own income. Given the parameter settings of VII in Table 2, fixed number of users, budget, and number of tasks, we randomly select winner with a true bid of 7 and loser with a true bid of 7 from the set of all workers and use the actual bids of the costs of winner and loser to understand how their utility changes. The cost authenticity test of winner and loser is shown in Figure 9. In these several situations, we can observe that when a worker bids for its true value, its utility is maximized. Regardless of whether the user is a winner or a loser, the user cannot increase its utility through dishonest bids, which proves the authenticity of SARA's bidding.Figure 9
Authenticity verification of SARA. (a) Cost authenticity of winner. (b) Cost authenticity of loser.
(a)(b)


## 6. Conclusion

In this paper, an incentive method called SARA is proposed, which is a social awareness incentive mechanism of MCS system based on reverse auction. Different from the traditional MCS platform recruiting sensing users, social networks are used as the recruitment platform. The sensing task is diffused in the social network through the initial user, and the knowledge graph is used to comprehensively analyze the user's potential value and influence to obtain the user's social benefits. The user's social benefits and actual sensing data are taken as the overall contribution of the sensing users, and the sensing users with the greatest social welfare are selected as the winner users. Comparing the method proposed in this article with the existing literature and the optimal task-solving method, experiments show that, under the influence of various factors, the social welfare of SASR is much higher than that of SRC and close to the social welfare of OPT. At the same time, it proved that SASR satisfies the requirements of dominant strategy, user's personal rationality, bid authenticity, and computational efficiency.In the future work, the application of crowdsensing under the knowledge map will be further explored. Use the complex semantic associations between entities provided by the knowledge graph to recommend matching perception tasks for perception users. This has the effect of improving the performance indicators of crowdsensing. In addition, we only considered the uniform distribution of the cost of the sensing task and the user bid in the comparison with other solutions in the simulation process. Later, a comparative analysis under normal distribution and exponential distribution will be introduced.



---

*Source: 6697862-2021-05-08.xml*