# A Privacy-Preserving Incentive Mechanism for Participatory Sensing Systems

Authors: Xiaoguang Niu; Jiawei Wang; Qiongzan Ye; Yihao Zhang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

The proliferation of mobile devices has facilitated the prevalence of participatory sensing applications in which participants collect and share information in their environments. The design of a participatory sensing application confronts two challenges: “privacy” and “incentive” which are two conflicting objectives and deserve deeper attention. Inspired by physical currency circulation system, this paper introduces the notion of E-cent, an exchangeable unit bearer currency. Participants can use the E-cent to take part in tasks anonymously. By employing E-cent, we propose an E-cent-based privacy-preserving incentive mechanism, called EPPI. As a dynamic balance regulatory mechanism, EPPI can not only protect the privacy of participant, but also adjust the whole system to the ideal situation, under which the rated tasks can be finished at minimal cost. To the best of our knowledge, EPPI is the first attempt to build an incentive mechanism while maintaining the desired privacy in participatory sensing systems. Extensive simulation and analysis results show that EPPI can achieve high anonymity level and remarkable incentive effects.


---

## Body

## 1. Introduction

Mobile computing devices, such as smartphones, wearable devices, and tablet PCs, have become popular in our daily life. These devices have contributed to the advent of numerous participatory sensing systems (PSS) [1]. In a PSS, an application server stimulates a large number of participants to sense and transmit measurements of the variables of interest (e.g., images, videos, sounds, locations, trajectories) via the sensors in their devices to a data collection entity in charge of task monitoring or addressing a particular problem. Although deploying such application has enormous social and technical benefits, several participants’ privacy and participation concerns arise [2, 3].The design of a participatory sensing application confronts two challenges: “privacy” and “incentive.” On one hand, if multiple sensing reports are associated with a participant identity, the participant’s privacy information may leak, since the report is stamped with time and location [4]. Thus, the requirement of privacy in PSS is unlinkable between identities and sensing data. On the other hand, the number of participation times in PSS is the key to provide adequate level of service quality. Most of the mobile crowd sensing-based applications rely on voluntary participation. To complete a task with a mobile device, participants have to consume their own resources such as battery, storage, and network traffic. A user may not be interested in the task, unless he receives a satisfactory reward to compensate for his resource consumption and potential privacy breach. Therefore, incentive mechanisms have been proposed to attract adequate participants [5–7].Nevertheless, if the server provides full anonymity to participants for privacy-preserving consideration, it could be difficult to guarantee the trustworthiness of participants’ submitted data. PSS is vulnerable to false data submission. As the smartphone sensors are controlled by the contributors, it is easy for malicious adversaries to configure the devices to send false sensing data. Meanwhile, to reduce false data submission, reputation systems [8] have been widely used to encourage valid participation and punish misbehavior, where a participant’s behavior and identity are bound to a reputation account. However, as most of them require linking participants’ identities with their reports in order to provide rewards for participants, the server can easily infer the participants’ privacy just by analyzing the correlation between participants’ personal information (identity, reputation) and the sensing data in each report. Therefore, a privacy-preserving incentive mechanism is hard to design because “privacy” and “incentive” are two conflicting objectives.Inspired by physical currency circulation system, this paper firstly proposes a novel notion of E-cent which is an exchangeable and untraceable unit bearer currency. Participants in PSS can take part in tasks without leaking any individual’s privacy due to E-cents exchange. By using E-cent, we propose EPPI, an E-cent-based incentive mechanism to motivate users to participate in tasks. In EPPI, a bidding model is proposed to simulate and predict the bidding behavior of participants based on the expectancy theory of motivation in psychology defined by Vroom [9]. Then user selection strategy of the server is proposed to minimize tasks cost and assign tasks to selected users more averagely. It can be proved that EPPI can provide full anonymity to participants and dynamically adjust the budget to regulate the performance of task. To the best of our knowledge, our work is the first attempt to build an incentive mechanism while maintaining the desired privacy in PSS.To summarize, the contributions include the following.(i)
The notion of E-cent is proposed as a unit bearer currency for the PSS system. E-cent is exchangeable and untraceable. Participants can participate in tasks anonymously by using E-cents.(ii)
An E-cent-based privacy-preserving incentive mechanism called EPPI is designed with user bidding model based on the expectancy theory of motivation in psychology.(iii)
A user selection strategy is proposed to finish tasks at minimal cost and with balanced task assignment. EPPI can not only maintain the anonymity but also motivate users to participate in tasks.(iv)
Extensive simulations and analysis are conducted to demonstrate that EPPI can provide full anonymity to participants and achieve incentive objectives.The remainder of this paper is organized as follows. In Section2, we discuss related work. Section 3 describes E-cent system. Section 4 presents our proposed EPPI mechanism in detail. The performance of EPPI is evaluated in Section 5. Finally, we make a conclusion in Section 6.


## 2. Related Works

Many pieces of works have specially studied the incentive mechanism in participatory sensing [10–13]. Most of existing incentive mechanisms mainly focus on utility maximization and cost minimization of the server. In [14], Singer and Mittal proposed a pricing mechanism, which enables automating the process of pricing and allocating tasks for requesters in complex markets. In [15], Duan et al. considered different incentive mechanisms to motivate the collaboration of smartphone users on data acquisition and distributed computing. However, these incentive mechanisms only focus on the reward for good participants without taking the punishment for false data submission into account. In addition, different market-based incentive mechanisms are proposed [16–18]. In such incentive mechanisms, the users bidding model and game theory in economics are widely used. Lee and Baik [19] designed a dynamic pricing incentive for participatory sensing, where participants bid for the sensed data and the server selects users as participants to minimize and stabilize the incentive cost while maintaining adequate level of participants by preventing users from dropping out. But they do not take the balance of task assignment into consideration. One participant may win most of the tasks with lower price. In fact, tasks should be assigned to users as uniformly as possible, such that more users can participate in tasks. More importantly, none of these mechanisms can meet the high requirements of privacy and anonymity in participatory sensing, because in such incentive mechanisms the server needs to know user ID so as to give rewards to users, which will reveal the participants’ privacy. The mechanism in preliminary work [20] intends to incent people to move to the location as system needs. However, it cannot apply to most situations for the incentives are often too few for users. Most participatory users move according to the intended purpose, rather than depending on the incentive situation to determine the direction of the next movement [5, 7].Plenty of researches on privacy in PSS have been proposed. The majority of them focus on spatial and temporal cloaking techniques [21–23]. For instance, as the most popular technique [23], K-anonymity blurs a participant’s private information in a cloaked area or a cloaked time interval so that the sensitive information is indistinguishable from other k-1 participants. Nevertheless, these spatial and temporal cloaking techniques are not suitable to dealing with privacy problem in incentive mechanism. Another well-known technique to protect the anonymity and privacy of the participants is to adopt pseudonyms rather than the true name in every operation [24]. Nonetheless, analysis of the reported data and reporting pattern may disclose the participants’ important information such as residences [4].To solve the conflict between privacy and incentive, anonymous reputation architectures have been proposed. For instance, reputation value is used to measure the participation and reliability level of participants in [25], while pseudonyms are utilized to provide anonymity for participants in [26]. However, all of them are vulnerable to identity-based attacks since participants cannot control an arbitrary number of pseudonyms and hence the service provider can recognize the participants’ identity by analyzing their behaviors of data contribution and service accessing. Kinateder and Pearson [8] proposed a privacy-enhanced peer-to-peer reputation system, but unfortunately it cannot be adapted to participatory sensing systems, as both participants and the server are not trustworthy in PSS. IncogniSense [27] extends the idea of pseudonyms-based reputation, which focuses on periodic pseudonyms and transfer of reputation between pseudonyms and a trusted third party is supposed to be available to transfer the reputation score of users between consecutive pseudonyms. However, it introduces additional overhead for users to create pseudonyms; ARTSense [28] maintains the reputation anonymity properties and enforces reputation updates but does not consider the incentive requirement of the application server.


## 3. What is E-Cent?

There are many e-cash/e-coin solutions, why not use them directly? In this solution, E-cent is not dividable, and each one shall be a separate item such that the storage requirement is very high.A PSS consists of participants and an application server (hereafter referred to as the “server”), where participants sample the objects with their smartphones and send the samples to the application server. The server analyzes and processes the samples and then provides services to participants with them. After that, the server will generate feedback (either reward or penalty) for participants based on their report quality. Moreover, participants can buy services from the server with the reward which can be circulated between participants and the server. The server is considered to be honest-but-curious. That is to say, the server will fulfill its functions, but may attempt to associate a sensing report with a particular participant to reveal his privacy. However, participants are not trustworthy for submitting true sensing data.To achieve the goal of “participating and participation feedback without identity,” inspired by physical currency circulation system, we propose E-cent, a unit bearer digital currency which can circulate between the server and all participants. It is generated and authorized by the server with the public-key cryptographic primitives. On one hand, E-cent can be exchanged among participants such that the correlation between participant and E-cent is broken. If a participant submits an exchanged E-cent to the server, the server cannot identify the identity of the participant just based on the submitted E-cent. Hence, E-cent provides full anonymity for participants. On the other hand, the server can use E-cent as a reward to encourage participants to participate in tasks. To distinguish the authority of E-cent, we design two types of E-cent: (i) basic E-cent, which is designed for new participants. It cannot be used to purchase services, but can be used as pledge when sending reports; (ii) normal E-cent, which is designed to reward participants for contributing data. It can be used as pledge and to purchase services. Therefore, new participants are not able to enjoy the services on the server unless they participate in the sensing task.There are four operations about E-cent, as illustrated in Figure1. We now describe each of these operations in detail and the notations frequently used in this paper are listed in Notations.Figure 1
Operations of E-cent.(1) E-Cent Generation. When a new participant wants to participate in a task, he needs to send a request to the server to register. The server gives some basic E-cents (denoted as BC) to the new participant. For other cases, when a participant contributes sensing data to the server, the server will reward the participant with normal E-cents (denoted as C). The server will generate a nonrepetitive random number and sign it with the private key of server. The server saved a valid copy of E-cent; when the E-cent is used, the server will tab it as “used.”(2) E-Cent Exchange. The E-cent is required to be exchanged before use. Before exchanging, the participant Pi marks an E-cent with a secret number bi, which is randomly selected and only known to the participant, and then encrypts it with the server’s public key. A marked E-cent of Pi (denoted as MCi) is represented as(1)MCi=Ci∣bispub.Every time a participant marks an E-cent, he can choose a different secret numberb. Therefore, b cannot be used by the server to link E-cents with the participant.A special area called mix zone is open on the server to provide E-cent exchange service for all participants. Participants can log in mix zone with a pseudonym. Every time a participant logs in, he can choose a different pseudonym. The pseudonym list of online participants is open for all participants. A participant (via pseudonymPSi) can randomly select a participant (via pseudonym PSj) from the list for E-cent exchange. Note that this process does not go through the server and the server is blind to the selection of exchangers. Participant Pi sends his marked E-cent MCi to another participant Pj, and then Pj sends his E-cent MCj to Pi. To reduce the possibility of being identified by the server, every participant should exchange his E-cents with different participants at different time and exchange only one E-cent in any exchange process. After E-cent exchange, both participants need to renew the exchanged marked E-cent on server within a period TMaxR to avoid the loss caused by malicious participants.(3) E-Cent Renewal. For Pi, since MCj is encrypted, it cannot be used directly. Thus, the participant Pi needs to submit it to the server for renewal. After receiving a marked E-cent, the server will check the following.(a)
Whether the public-key encryption of the submitted marked E-centMCj is valid. If positive, the server extracts the original E-cent Cj and the secret number with its private key.(b)
Whether the private-key signature ofCj is valid.(c)
WhetherCj has not been used before.(d)
Whether server has received dispute arbitration ofCj.IfMCj pass all the above validations, the server will send a new E-cent Ci′ to Pi. Accordingly, the original E-cent Cj will be invalidated. Otherwise, the server is notified of the invalidation of MCj, and Pi will launch dispute arbitration to server to get the loss back.(4) Exchange Dispute Arbitration (EDA). In EDA, Pi is required to submit Ci and the secret number bi to the server to prove the ownership of marked E-cent MCi. After checking Ci and bi, the server will compensate Pi with a new E-cent Ci′′ and invalidate MCi and Cj′ which has been allocated to Pi’s exchanger Pj. Then the server will announce the information about this dispute arbitration to all participants.


## 4. EPPI: An E-Cent-Based Privacy-Preserving Incentive Mechanism

In this section, we propose an E-cent-based incentive mechanism called EPPI, which is a dynamic balance regulatory mechanism. It can not only protect the privacy of participants, but also adjust the total participatory sensing system to the ideal situation, under which the rated tasks will be finished with minimum cost. Definition of notations for the subregion and definition of notations for thejth user in the ith subregion are listed in the Notations.


### 4.1. System Architecture

In EPPI, the system first detects the sensing field and divides it intom regions of the same size, each of which corresponds to a task. Thus, the set of tasks can be represented as Γ={τ1,τ2,…,τm}. Total rewards of R are prepared for the m tasks. Each task τj∈Γ attracts at least n_j participants to ensure high trustworthiness of sensing data. The three purposes of the user incentive mechanism are (1) to finish the rated task; (2) to assign the task to the chosen users as fairly as possible to enable more users to participate in the task and prevent a few users from taking over all tasks with extremely low price; (3) to make the cost as low as possible. The importance of these three purposes decreases with order. When the three purposes of our system are achieved at the same time, we say that the ideal situation is reached. In fact, the ideal situation is a kind of Nash equilibrium in economics, which will be proved later. In game theory, the Nash equilibrium is a solution of a noncooperative game involving two or more players [29]. In EPPI, the server interacts with participants through a three-stage process in each task cycle.Stage 1.
If a user wants to take a task, he/she needs to register for the task by submitting some E-cents (more than a pledge threshold) to the server as pledge. The number of pledges depends on the quality of sending reports. If the participant wants to submit a high-quality report to obtain more rewards, he/she thus needs to pledge more E-cents. At the beginning of each task cycle, the server sends the information includingNi, Ni′, Ai,regi, Rij, Xi, and acti of the previous cycle to all the users. Each user chooses to participate or not independently considering their own privacy level and participation cost and then submit his bidding price profile to the server including participating or not, bidding unit price, and number of participation times.Stage 2.
The server will wait for a certain time to collect users’ quotes, and those users from whom the sever fails to collect the quotes within the stipulated time will be considered as unwilling participants. Based on the bidding situation analysis of historic cycle and the current cycle and the prediction of user behavior, the server will strategize to select participants to finish tasks and minimize the cost as well and then distribute the rated task to selected users. After that, each user will receive a feedback message from server to inform whether he/she can participate in this cycle and number of participation times if he/she can.Stage 3.
Selected users will collect sensing data and submit it to the server. These sensing data will be uniformly distributed in cycle. To guarantee the trustworthiness of received data, the server will check the legitimacy of data. After that, the server will pay the reward to user with E-cent or notify user of the illegality of data.Users can set up their privacy level and default unit price. They can use earned virtual currency to purchase a service the server provided.


### 4.2. Bidding Model

The users who intend to participate in the task will send a bidding (including the unit price and the maximum times they would like to join in this cycle) to the server.Psychologist Vroom [9] defines the motivation as a process governing choice among alternative forms of voluntary activities, a process controlled by the individual. Expectancy of motivation theory introduces that an individual will behave or act in a certain way which he has considered. It is the expectancy of result that motivates individuals to make their decision and control their behavior. The expectancy of motivation is(2)M=β·V·E·T,where β are the constant coefficient. M represents the power of stimulation, which means the strength of the internal potential to mobilize the enthusiasm of one person. V represent valence, a psychology concept, which means the actual value of the goal to oneself. One same goal may confer different valences to different people. In our mechanism, V=Rij·E is the expected value, which means the possibility of achieving the goal according to experience, which is negatively related to the user’s privacy. In our mechanism, E=1/Rij·T means the nonpersonal factors that can help individuals to achieve the goal. In our mechanism, T refers to the cost of the participants’ mobile phone for participating in one task.(3)T=wrnt·xrnt+wrp·xrp+wp·xp+wid·xid+wba·1xba+wo·xo,where xrnt, xrp, xp, xid, xba, and xo are defined in Notations and wrnt, wrp, wp, wid, wba, and wo are the corresponding constant coefficients.Correspondingly, the expectancy of motivation ofith user in ith subregion is(4)Mij=β·Rij·1Pij·T.IfMij≥Kij in a certain task cycle, the user will participate in the task in that cycle. Subsequently, the bidding price for that user is(5)p=C+KijMij·C,where Kij is the psychological threshold for users whether participating or not, Mij is the expectancy of motivation for the jth user in the ith subregion, and C is the jth user’s cost for one task.(6)C=xent+xpc+γ·t/xp,where t is the expected completion time of the task and γ is the constant coefficient.


### 4.3. Participant Selection Strategy

The server’s strategy is to choose users to complete the rated tasks while minimizing the cost under the given budget and pay reward to them when they finish task according to the users’ bidding price. Specifically, the target area is divided intol subregions equally, and tasks are distributed to task cycles {t1,t2,…,tn,tn+1,…}. In each cycle of a subregion, Ni′ is the number of rated tasks that need to be completed. The symbol σi reflects the proportion of unqualified data and should meet the condition 0<σi<1. Each area possibly has certain number of bad data, so the actual number of rated tasks should have redundancy to keep the quality of task completion. For instance, the number of final rated tasks Ni=Ni′•(1+σi). The allocation of budget for the total target region uses budget pool, which receives the surplus budget from some subregions and distributes them into other subregions averagely if they need. The budget of the ith subregions is Ri.The server will calculate a unit price thresholdRij by predicting users’ behavior and a reasonable adjustment formula to choose the user who has a bidding price lower than the threshold. Hence, the total expense in the ith subregions Ri′ is(7)Ri′=∑k=1actipk·nk′≤∑j=1XiRij,where acti is the number of users in the activated users, pk is the final unit price for one task, and nk′ is the number of tasks assigned to the chosen user. It is necessary for server to predict user’s behavior to roughly estimate the number of participants. The prediction must refer to the statistic information of last several past cycles.Because too many factors will influence user’s decision, we now just make a reasonable simplified assumption that the relationship between unit price and number of participants obeys the normal distribution, which isFR^ij~N(μ,1). So, the probability density function is(8)fx=12πex-μ2/2.And distribution function is(9)FR^ij=12π∫∞R^ijex-μ2/2dx.The expectation of number of finished tasks in every cycle is(10)X^i=δ·FR^ij,where δ is the predefined constant. Now we hope the rated tasks all will be finished; that is,(11)X^i=Ni=δFR^ij=δ2π∫∞R^ijex-μ2/2dx≈δ·ΦR^ij-μ.Hence,R^ij can be worked out.However, only relying on the prediction of unit price (R^ij) is inaccurate and not persuasive. Any changes such as the sudden cutdown on budget and the movement of people will make the situation disobey the normal distribution temporarily. Therefore, the formula of the unit price should be a reasonable and adjustable definition.The price is determined by three factors:(1) the ratio of Ri and Ni is the average price in the subregion, which is called the basic price; (2)Pij is the user’s privacy level, while user can get more reward if he/she gives some extra privacy information like GPS location; (3)Ai is the adjustment coefficient which is influenced by statistic information of last cycle.(12)Rij=w0·RiNi+w1·Pij+w2·Ai(13)Ai=α·regi-actiregi·Ri-Ri′Ni,where w0,w1,w2, and α are coefficients; (regi-acti)/regi is the proportion of inactivated users accounts to the total users. If the proportion is large, that indicates that the total motivation of users is very low, and Ai should make the price adjust fast to improve users’ motivation in time. (Ri-Ri′)/Ni is the deviation of budget and expense. Ri′ is the final expense in the ith subregion:(14)Ri′=∑k=1actipk·nk′.Because the privacy level of user obeys the standard normal distribution,∑j=1Xiw1∙Pij. In addition, the budget Ri should be adjusted in each cycle:(15)Ritn=1+Nitn-1-∑j=1actin′Nitn-1·Ritn-1.The budget in subregion will be adjusted according to the completeness of tasks in last cycle. In fact, one method is to directly letRitn=R^ij∙Ni, but this result heavily relies on the accuracy of hypothesis and has little robustness towards various deviation and data change.Therefore, the budget will roundly adjust the unit price and the number of participants and finally reach the ideal condition.To achieve the target, we should define and optimize the coefficientα.The final unit price thresholdRij(tn) is(16)Rijtn=w0′·RitnNitn+w2′·αtn·regitn-1-actitn-1regitn-1·Ritn-1-Ri′tn-1Nitn.In formula (16), we temporarily ignore the privacy level because it can be added when the calculation is completed.According to the prediction of users and formula (11), we can get the number of rated tasks at tnth cycle:(17)Nitn≈δ·ΦR^ijtn-μ.Thus, the prediction of unit price threshold R^ij(tn) can be obtained. Furthermore, we deform formula (12) and substitute R^ij(tn) in it:(18)αtn=1w2′·R^ijtn-w0′·Ritn/Nitnregitn-1-actitn-1·regitn-1·NitnRitn-1-Ri′tn-1,where α is also influenced by historic values. And the value has fewer influential effect on α as the time is longer. We define the width of sliding window as follows:(19)αtn=∑k=1width-1α′tn-k·e-k2/2∑k=1width-1e-k2/2From formula (16) to formula (19) we can get the final unit price threshold Rij(tn). Then we propose a user selection algorithm for the server to select participated users. In this algorithm, the server distributes tasks to each user who has relatively low bidding price which does not exceed unit price threshold in each round. It guarantees that the rated tasks will be finished with minimum cost. In addition, the server will distribute tasks round by round. And in each round one user can receive only one task even if it has a very low bidding price, which makes task distribution more average and fair. As a result, more people can join in the task rather than a few users with extremely low price.The server will send feedback messageLij′=(Y/N,p,n′) to all users. The feedback message notifies user of whether he/she could participate in the mission. If yes, n′ tells them how many tasks he/she needs to finish.Computation Complexity Analysis. The time and space complexity of the calculation of Rij are O(n) obviously. In Algorithm 1, n tasks will be allocated to users who have price lower than Rij. The Merge sort over Lij has the time complexity of O(nlog2n) and the space complexity of O(1). The execution in each loop examines whether the necessary condition is satisfied. If not, the loop will break. This means that every task distribution operation may only run once at most. So, the time complexity is O(nlog2n). And the space complexity is O(n).Algorithm 1:User selection.
INPUT: set of user willingnessLi={Li1,Li2,Li3,…,Liacti}, Lij=(Y,p,n), Ni, Rij
PARAMETERS: flagf
OUTPUT: set of feedback informationLi′={Li1′,Li2′,Li3′,…,Liacti′}, Lij′=(Y,p,n′)
(
1
) sort the p of Lij in ascending order
(
2
) initialization: c=0 for j=1 to acti, Lij′=(N,p,0)
(
3
) while Ni>0   &&   f==1;
(
4
)   f=0; for j=1 to acto do
(
5
)   if p<=Rij   &&   Ni>0
(
6
)    if n′<n
(
7
)      f=1, n′=n+1, Lij1′=Y, Ni=Ni −1;
(
8
)    end;
(
9
)   else break;
(
10
)  end;
(
11
) end;
(
12
) return Li′;


### 4.4. Incentive Mechanism Analysis

Lemma 1.
The system can reach the ideal condition.(1)
All rated tasks are finished.(2)
Tasks are distributed to participants as averagely as possible.(3)
The expense is minimum and lower than the budget.Proof.
In our mechanism, we have macroadjustment and microadjustment to make the system reach the ideal condition. In formula (15), we can change the budget of subregion Ri gradually to adjust the unit price Rij and number of participating users acti, which is called macroadjustment.
If some rated tasks did not finish (Ni>Xi), more users are needed in the next cycle; according to Ri(tn+1)>Ri(tn), the raise of budget increases the unit price Rij, and users’ motivation Mij will increase, which will lead to the raise of the number of activated users, and finally make Xi add to reach Ni. On the contrary, the proof is similar.
Microadjustment is the automatic balance mechanism inside a subregion in order to find the balance number of finished tasksXi under the current budget Ri.
If the number of finished tasks is decreasing,(Xi(tn-1)>Xi(tn)), Ai(tn+1)>Ai(tn), Rij(tn+1)>Rij(tn), the raise of unit price will increase the users’ motivation Mij and lead to the raise of Xi and finally make Xi reach the balanced value under the current budget. On the contrary, the proof is similar.
In conclusion, for (1) when the microadjustment and macroadjustment price threshold Rij, expense Ri′, and number of finished tasks Xi approach the balance value, the rated tasks are ensured to be all finished, because macroadjustment guarantees that the budget is enough to finish the rated tasks while microadjustment makes sure that the actual number of finished tasks reaches the balance value under this budget. For (2) and (3), due to the user selection algorithm, it is certain that tasks will be distributed to activated users averagely and the actual expense is the minimum in every cycle, because the algorithm chooses users in their price from the lowest one in loop, and in each loop a user can only have one task at most. So far, we achieved the three targets which have been mentioned in the beginning of this chapter.Lemma 2.
The ideal condition is the Nash equilibrium.Proof.
Under the ideal condition, for the subregioni, Xi=Ni, Ai=0, Rij=w0∗Ri/Ni+w1∗Pij, the rated tasks are all to be finished and the expense reaches minimum and is lower than budget. When each subregion reaches the ideal condition, the whole region reaches the ideal condition. When the ideal condition is reached, the Nash equilibrium is reached.
Under the ideal condition, any change of any side will not bring more benefit.
(1) To Any User. Increasing price will lower the chance to be chosen. Yet decreasing price will lead to fewer rewards. If p increases, p>Rij, which means the user cannot participate in any mission in this cycle. The benefit will become zero. If p reduce to p′, the user can take part in the task but gets less profit than before, because p′<p.
(2) To the Server. If unit price Rij increases, budget Ri and users’ participating motivation Mij will increase correspondingly. After all rated tasks having been finished, the rise of Rij only leads to unnecessary expense. On the contrary, the abatement of Rij will decrease Mij, which may make the rated tasks uncompleted.


## 4.1. System Architecture

In EPPI, the system first detects the sensing field and divides it intom regions of the same size, each of which corresponds to a task. Thus, the set of tasks can be represented as Γ={τ1,τ2,…,τm}. Total rewards of R are prepared for the m tasks. Each task τj∈Γ attracts at least n_j participants to ensure high trustworthiness of sensing data. The three purposes of the user incentive mechanism are (1) to finish the rated task; (2) to assign the task to the chosen users as fairly as possible to enable more users to participate in the task and prevent a few users from taking over all tasks with extremely low price; (3) to make the cost as low as possible. The importance of these three purposes decreases with order. When the three purposes of our system are achieved at the same time, we say that the ideal situation is reached. In fact, the ideal situation is a kind of Nash equilibrium in economics, which will be proved later. In game theory, the Nash equilibrium is a solution of a noncooperative game involving two or more players [29]. In EPPI, the server interacts with participants through a three-stage process in each task cycle.Stage 1.
If a user wants to take a task, he/she needs to register for the task by submitting some E-cents (more than a pledge threshold) to the server as pledge. The number of pledges depends on the quality of sending reports. If the participant wants to submit a high-quality report to obtain more rewards, he/she thus needs to pledge more E-cents. At the beginning of each task cycle, the server sends the information includingNi, Ni′, Ai,regi, Rij, Xi, and acti of the previous cycle to all the users. Each user chooses to participate or not independently considering their own privacy level and participation cost and then submit his bidding price profile to the server including participating or not, bidding unit price, and number of participation times.Stage 2.
The server will wait for a certain time to collect users’ quotes, and those users from whom the sever fails to collect the quotes within the stipulated time will be considered as unwilling participants. Based on the bidding situation analysis of historic cycle and the current cycle and the prediction of user behavior, the server will strategize to select participants to finish tasks and minimize the cost as well and then distribute the rated task to selected users. After that, each user will receive a feedback message from server to inform whether he/she can participate in this cycle and number of participation times if he/she can.Stage 3.
Selected users will collect sensing data and submit it to the server. These sensing data will be uniformly distributed in cycle. To guarantee the trustworthiness of received data, the server will check the legitimacy of data. After that, the server will pay the reward to user with E-cent or notify user of the illegality of data.Users can set up their privacy level and default unit price. They can use earned virtual currency to purchase a service the server provided.


## 4.2. Bidding Model

The users who intend to participate in the task will send a bidding (including the unit price and the maximum times they would like to join in this cycle) to the server.Psychologist Vroom [9] defines the motivation as a process governing choice among alternative forms of voluntary activities, a process controlled by the individual. Expectancy of motivation theory introduces that an individual will behave or act in a certain way which he has considered. It is the expectancy of result that motivates individuals to make their decision and control their behavior. The expectancy of motivation is(2)M=β·V·E·T,where β are the constant coefficient. M represents the power of stimulation, which means the strength of the internal potential to mobilize the enthusiasm of one person. V represent valence, a psychology concept, which means the actual value of the goal to oneself. One same goal may confer different valences to different people. In our mechanism, V=Rij·E is the expected value, which means the possibility of achieving the goal according to experience, which is negatively related to the user’s privacy. In our mechanism, E=1/Rij·T means the nonpersonal factors that can help individuals to achieve the goal. In our mechanism, T refers to the cost of the participants’ mobile phone for participating in one task.(3)T=wrnt·xrnt+wrp·xrp+wp·xp+wid·xid+wba·1xba+wo·xo,where xrnt, xrp, xp, xid, xba, and xo are defined in Notations and wrnt, wrp, wp, wid, wba, and wo are the corresponding constant coefficients.Correspondingly, the expectancy of motivation ofith user in ith subregion is(4)Mij=β·Rij·1Pij·T.IfMij≥Kij in a certain task cycle, the user will participate in the task in that cycle. Subsequently, the bidding price for that user is(5)p=C+KijMij·C,where Kij is the psychological threshold for users whether participating or not, Mij is the expectancy of motivation for the jth user in the ith subregion, and C is the jth user’s cost for one task.(6)C=xent+xpc+γ·t/xp,where t is the expected completion time of the task and γ is the constant coefficient.


## 4.3. Participant Selection Strategy

The server’s strategy is to choose users to complete the rated tasks while minimizing the cost under the given budget and pay reward to them when they finish task according to the users’ bidding price. Specifically, the target area is divided intol subregions equally, and tasks are distributed to task cycles {t1,t2,…,tn,tn+1,…}. In each cycle of a subregion, Ni′ is the number of rated tasks that need to be completed. The symbol σi reflects the proportion of unqualified data and should meet the condition 0<σi<1. Each area possibly has certain number of bad data, so the actual number of rated tasks should have redundancy to keep the quality of task completion. For instance, the number of final rated tasks Ni=Ni′•(1+σi). The allocation of budget for the total target region uses budget pool, which receives the surplus budget from some subregions and distributes them into other subregions averagely if they need. The budget of the ith subregions is Ri.The server will calculate a unit price thresholdRij by predicting users’ behavior and a reasonable adjustment formula to choose the user who has a bidding price lower than the threshold. Hence, the total expense in the ith subregions Ri′ is(7)Ri′=∑k=1actipk·nk′≤∑j=1XiRij,where acti is the number of users in the activated users, pk is the final unit price for one task, and nk′ is the number of tasks assigned to the chosen user. It is necessary for server to predict user’s behavior to roughly estimate the number of participants. The prediction must refer to the statistic information of last several past cycles.Because too many factors will influence user’s decision, we now just make a reasonable simplified assumption that the relationship between unit price and number of participants obeys the normal distribution, which isFR^ij~N(μ,1). So, the probability density function is(8)fx=12πex-μ2/2.And distribution function is(9)FR^ij=12π∫∞R^ijex-μ2/2dx.The expectation of number of finished tasks in every cycle is(10)X^i=δ·FR^ij,where δ is the predefined constant. Now we hope the rated tasks all will be finished; that is,(11)X^i=Ni=δFR^ij=δ2π∫∞R^ijex-μ2/2dx≈δ·ΦR^ij-μ.Hence,R^ij can be worked out.However, only relying on the prediction of unit price (R^ij) is inaccurate and not persuasive. Any changes such as the sudden cutdown on budget and the movement of people will make the situation disobey the normal distribution temporarily. Therefore, the formula of the unit price should be a reasonable and adjustable definition.The price is determined by three factors:(1) the ratio of Ri and Ni is the average price in the subregion, which is called the basic price; (2)Pij is the user’s privacy level, while user can get more reward if he/she gives some extra privacy information like GPS location; (3)Ai is the adjustment coefficient which is influenced by statistic information of last cycle.(12)Rij=w0·RiNi+w1·Pij+w2·Ai(13)Ai=α·regi-actiregi·Ri-Ri′Ni,where w0,w1,w2, and α are coefficients; (regi-acti)/regi is the proportion of inactivated users accounts to the total users. If the proportion is large, that indicates that the total motivation of users is very low, and Ai should make the price adjust fast to improve users’ motivation in time. (Ri-Ri′)/Ni is the deviation of budget and expense. Ri′ is the final expense in the ith subregion:(14)Ri′=∑k=1actipk·nk′.Because the privacy level of user obeys the standard normal distribution,∑j=1Xiw1∙Pij. In addition, the budget Ri should be adjusted in each cycle:(15)Ritn=1+Nitn-1-∑j=1actin′Nitn-1·Ritn-1.The budget in subregion will be adjusted according to the completeness of tasks in last cycle. In fact, one method is to directly letRitn=R^ij∙Ni, but this result heavily relies on the accuracy of hypothesis and has little robustness towards various deviation and data change.Therefore, the budget will roundly adjust the unit price and the number of participants and finally reach the ideal condition.To achieve the target, we should define and optimize the coefficientα.The final unit price thresholdRij(tn) is(16)Rijtn=w0′·RitnNitn+w2′·αtn·regitn-1-actitn-1regitn-1·Ritn-1-Ri′tn-1Nitn.In formula (16), we temporarily ignore the privacy level because it can be added when the calculation is completed.According to the prediction of users and formula (11), we can get the number of rated tasks at tnth cycle:(17)Nitn≈δ·ΦR^ijtn-μ.Thus, the prediction of unit price threshold R^ij(tn) can be obtained. Furthermore, we deform formula (12) and substitute R^ij(tn) in it:(18)αtn=1w2′·R^ijtn-w0′·Ritn/Nitnregitn-1-actitn-1·regitn-1·NitnRitn-1-Ri′tn-1,where α is also influenced by historic values. And the value has fewer influential effect on α as the time is longer. We define the width of sliding window as follows:(19)αtn=∑k=1width-1α′tn-k·e-k2/2∑k=1width-1e-k2/2From formula (16) to formula (19) we can get the final unit price threshold Rij(tn). Then we propose a user selection algorithm for the server to select participated users. In this algorithm, the server distributes tasks to each user who has relatively low bidding price which does not exceed unit price threshold in each round. It guarantees that the rated tasks will be finished with minimum cost. In addition, the server will distribute tasks round by round. And in each round one user can receive only one task even if it has a very low bidding price, which makes task distribution more average and fair. As a result, more people can join in the task rather than a few users with extremely low price.The server will send feedback messageLij′=(Y/N,p,n′) to all users. The feedback message notifies user of whether he/she could participate in the mission. If yes, n′ tells them how many tasks he/she needs to finish.Computation Complexity Analysis. The time and space complexity of the calculation of Rij are O(n) obviously. In Algorithm 1, n tasks will be allocated to users who have price lower than Rij. The Merge sort over Lij has the time complexity of O(nlog2n) and the space complexity of O(1). The execution in each loop examines whether the necessary condition is satisfied. If not, the loop will break. This means that every task distribution operation may only run once at most. So, the time complexity is O(nlog2n). And the space complexity is O(n).Algorithm 1:User selection.
INPUT: set of user willingnessLi={Li1,Li2,Li3,…,Liacti}, Lij=(Y,p,n), Ni, Rij
PARAMETERS: flagf
OUTPUT: set of feedback informationLi′={Li1′,Li2′,Li3′,…,Liacti′}, Lij′=(Y,p,n′)
(
1
) sort the p of Lij in ascending order
(
2
) initialization: c=0 for j=1 to acti, Lij′=(N,p,0)
(
3
) while Ni>0   &&   f==1;
(
4
)   f=0; for j=1 to acto do
(
5
)   if p<=Rij   &&   Ni>0
(
6
)    if n′<n
(
7
)      f=1, n′=n+1, Lij1′=Y, Ni=Ni −1;
(
8
)    end;
(
9
)   else break;
(
10
)  end;
(
11
) end;
(
12
) return Li′;


## 4.4. Incentive Mechanism Analysis

Lemma 1.
The system can reach the ideal condition.(1)
All rated tasks are finished.(2)
Tasks are distributed to participants as averagely as possible.(3)
The expense is minimum and lower than the budget.Proof.
In our mechanism, we have macroadjustment and microadjustment to make the system reach the ideal condition. In formula (15), we can change the budget of subregion Ri gradually to adjust the unit price Rij and number of participating users acti, which is called macroadjustment.
If some rated tasks did not finish (Ni>Xi), more users are needed in the next cycle; according to Ri(tn+1)>Ri(tn), the raise of budget increases the unit price Rij, and users’ motivation Mij will increase, which will lead to the raise of the number of activated users, and finally make Xi add to reach Ni. On the contrary, the proof is similar.
Microadjustment is the automatic balance mechanism inside a subregion in order to find the balance number of finished tasksXi under the current budget Ri.
If the number of finished tasks is decreasing,(Xi(tn-1)>Xi(tn)), Ai(tn+1)>Ai(tn), Rij(tn+1)>Rij(tn), the raise of unit price will increase the users’ motivation Mij and lead to the raise of Xi and finally make Xi reach the balanced value under the current budget. On the contrary, the proof is similar.
In conclusion, for (1) when the microadjustment and macroadjustment price threshold Rij, expense Ri′, and number of finished tasks Xi approach the balance value, the rated tasks are ensured to be all finished, because macroadjustment guarantees that the budget is enough to finish the rated tasks while microadjustment makes sure that the actual number of finished tasks reaches the balance value under this budget. For (2) and (3), due to the user selection algorithm, it is certain that tasks will be distributed to activated users averagely and the actual expense is the minimum in every cycle, because the algorithm chooses users in their price from the lowest one in loop, and in each loop a user can only have one task at most. So far, we achieved the three targets which have been mentioned in the beginning of this chapter.Lemma 2.
The ideal condition is the Nash equilibrium.Proof.
Under the ideal condition, for the subregioni, Xi=Ni, Ai=0, Rij=w0∗Ri/Ni+w1∗Pij, the rated tasks are all to be finished and the expense reaches minimum and is lower than budget. When each subregion reaches the ideal condition, the whole region reaches the ideal condition. When the ideal condition is reached, the Nash equilibrium is reached.
Under the ideal condition, any change of any side will not bring more benefit.
(1) To Any User. Increasing price will lower the chance to be chosen. Yet decreasing price will lead to fewer rewards. If p increases, p>Rij, which means the user cannot participate in any mission in this cycle. The benefit will become zero. If p reduce to p′, the user can take part in the task but gets less profit than before, because p′<p.
(2) To the Server. If unit price Rij increases, budget Ri and users’ participating motivation Mij will increase correspondingly. After all rated tasks having been finished, the rise of Rij only leads to unnecessary expense. On the contrary, the abatement of Rij will decrease Mij, which may make the rated tasks uncompleted.


## 5.Performance Evaluation and Security Analysis

In this paper, we consider a participatory sensing system with a similar scenario as [5]. The system consists ofMax_user mobile participants and an application server. As shown in Figure 2, we assume that simulation scene is Information Department of Wuhan University whose length is 612 m from west to east, and 856 m from north to south. The field is divided into l regions. Correspondingly, the whole system is comprised of X periodic tasks, each of which corresponds to a region. Total rewards of R E-cents of budget are given out to all participants in each cycle. In the initial phase, participants are unequally distributed in the sensing field. We used the Pathway Mobility Model [30] with geographic restriction as mobility model of each participant. The speeds of participants are randomly distributed from 1 m/s to 5 m/s. The maximum residence time for each site is 30 seconds. Each participant’s task set includes all tasks within the range of 30 meters. In each participant’s trajectory, the tasks will be sensed in every 5 meters. If any task is within 30 m from the participant, it will be added to his task set. The budget is distributed uniformly to each subregion at the beginning. The attack probability of a malicious participant is defined as the probability of the malicious participant sending a false report. The privacy and incentive performance of EPPI are evaluated firstly. Then we analyze the security of the mechanism itself. The data is set to match the real-world cases approximately. In fact the preset values have little impact on the tendency of balance. We make a survey of 13 students in our lab to get the weight coefficient. As for the constant coefficient, we do several tests and choose an appropriate group. The default values of parameters in EPPI mechanism experiment environment are listed in Table 1.Table 1
Default parameter settings.
Parameter
Value
Number of participantsMax_user
1000
Number of subregionsl
9
Number of rated tasksXi
9
The budget for whole target regionR
2000
The weight coefficient for userswrnt,…,wof
0.2,0.3,0.1,0.3,0.1,0
The weight coefficient for price thresholdw1′,w2′,w3′
0.4,0.3,0.3
Constant parameterst, xent, xpc
20,0.01,0.001
Constant coefficientsβ, γ, δ, μ, σ
100,0.1,10,7
,
0.05Figure 2
Simulation scene.


### 5.1. Evaluation Metrics

(i)
Anonymity level is the probability that the server traces a participant.
(ii)
Incentive effect is the impact of different price threshold and privacy level on participants’ bidding price, the change of a particular user’s bidding price, the adjustment of price threshold, number of finished tasks and expense, the comparison of two methods to predict users’ behavior, and the motivation of a user in different cases.


### 5.2. Privacy Evaluation

Tracing attack takes place when the server distinguishes a participant from other participants by associating submitted reports with the participant. In this attack, the server needs to link a certain ratio of reports with a participant. If the server succeeds in tracing a participant, the server will be able to analyze and profile the participant’s location trace or at least reduce the anonymity level of the participant. We evaluate the anonymity level of a participant in terms of its resilience against tracing attacks by calculating tracing probability. Though the selection of exchanger is anonymous and random, the server can link an E-cent to a participant by randomly matching the exchange pair. Its difficulty depends on the number of online participants in the mix zone. When a participant wants to send a report, he/she needs to randomly selectyi E-cents from y E-cents of her/her own and submit them to the server as pledge. As long as one of the yi E-cents is linked to him/her, the server can link the report to the participant. Therefore, the probability that a report is linked with a participant can be calculated as follows:(20)Pa report is linked with a participantyi=∑j=1Cyyi∑C∈Θ1Cyyi1nC,where Θ represents the selected E-cent set and nC represents the number of online participants at the moment the E-cent C is exchanged.Figure3(a) shows the probability of the server identifying a participant through tracing attack under varying required pledge of one report when the ratio of traced reports is set to 0.2. We can observer that as the pledge increases, the participant is more likely to be traced. This is because if a participant submits more E-cents to the server as pledge, the server will have more alternative information to trace the participant. However, we notice that even though the pledge is set to the highest value, the tracing probability still maintains a very low value (less than 0.23). As the number of task cycles increases, more participants participate due to the incentive mechanism. That is why the tracing probability keeps decreasing as the number of cycles increases. Figure 3(b) shows the impact of traced report ratio on tracing probability when pledge is set to 20. Even though the ratio is set to 0.1, the tracing probability is less than 0.2. When the ratio is set to 0.3, the tracing probability approaches 0, which means that it is almost impossible for the server to trace a participant.Figure 3
Resilience against tracing attack.
(a)
Impact of required pledge
(b)
Impact of traced report ratio


### 5.3. Incentive Evaluation

Figure4 shows the influence of different price threshold and subregions on users. The parameters for users are initialized in the range randomly obeying the normal distribution. The users’ sensitivity of privacy leakage levels Pij is initialized in [1, 5], and level 5 represents the highest sensitivity of privacy leakage level. User’s psychological thresholds Kij are generated in range [0,50]. The remaining flow of user’s mobile x1 and the remaining power of user’s mobile x2 are represented in percentage. The performance of user’s mobile x3 and user’s idle degree x4 are restricted in (0, 0.5), while the balances in users’ accounts x5 are represented by the number in [0,10].Figure 4
The influence factor of bidding price.
(a)
Impact of budget on bidding price distribution
(b)
Impact of user privacy on bidding price
(c)
Changes of bidding price on a particular userFigure4(a) shows how users respond to different price threshold of last cycle which the server sends them. Three different budgets are chosen to evaluate the distribution of participants in various price thresholds. As the expected price adds, the number of participants increases. At the meanwhile, the number of users with lower price also increases. This is due to the expected increase in profits that will stimulate the users’ motivation to participate, which increases the number of participants and decreases price according to our theory.Figure4(b) exhibits the impact of different users with various sensitivity of privacy leakage levels on their price bidding. Data of the experiment reflect the strong relationship between user sensitivity of privacy leakage level and their bidding price as we expected in definition. Privacy level 1 is the lowest level and level 5 is the highest. In all participants, privacy level 1 is the majority and no users with level 5 take part in the project. According to the definition of user motivation, the sensitivity of privacy leakage level indicates user’s possibility of finishing task. The lower the sensitivity of privacy leakage level is, the more accurate the data the user will send is, and the chance to join the mission successfully is larger.Figure4(c) shows the bidding price of a particular user who would like to participate. The case starts with budget Ri=200. Because the motivation of user has the positive correlation with Rij, the change of Rij will lead to change in user’s motivation; furthermore, the bidding price will be influenced by motivation. In other words, the change of user’s motivation will finally reflect on the change of his/her bidding price and number of tasks he/she wants to participant in.Figure5 shows the change of unit price threshold and the result of user selection in a given subregion. Three cases are designed to test the performance of MPI mechanism. These cases start with different budgets: surplus budget Ri=50, excessive budget Ri=400, and approximate appropriate budget Ri=200. In Figure 5(a) the unit price threshold of server will be adjusted by Ai and Ri, which leads to the fluctuation of number of price thresholds Rij. And as expected, the unit price threshold will finally converge to the balanced value no matter what the initial condition is. The balanced value of Rij reflects the average cost of one task for users. Figure 5(b) is the result of user selection. Results of selection of three cycles (1st, 6th, and 9th) which start with surplus budget Ri=50 are exhibited. In each cycle, we calculate the budget to see the impact of budget on a number of participants.Figure 5
The adjustment of unit price and result of user selection.
(a)
Changes of unit price threshold
(b)
The result of user selectionWe evaluate our reward allocation scheme by comparing its incentive result with three representative allocation schemes [31]: grey prediction (GP), proportional allocation (PA), and random allocation (RA). Figure 6 shows the total number of received sensing reports using four schemes in different task cycles. In this figure, EPPI received more reports at all cycles, which means it achieves the best incentive effect among all allocation schemes. Compared with other schemes, EPPI considers the historical distribution of participants and models the problem specifically with logistic function. According to Figure 6, the number of reports increases gradually over time until a steady status is reached. As the expectation of Algorithm 1, in each cycle, participants with bidding price lower than the threshold were chosen in increasing order by price averagely, which makes sure that the total expense will be minimum. In addition, the average distribution of task achieves the second target of EPPI.Figure 6
Number of received sensing reports over time.Figure7 shows the result of two methods to predict users’ behavior which have been mentioned in Section 4.3. Two situations are designed to compare the methods, both of which have the same condition starting with excessive budget Ri=400. In addition, in order to the better evaluate the reaction of two methods to the external stimulation, the number of rated tasks doubled from 20 to 40 in the 4th cycle, and the number of registered users reduced by half in the 9th cycle. The data of normal distribution model is the result that only relies on the prediction of unit price calculated by normal distribution function. And the data of EPPI prediction model is the result using the optimized adjustment mechanism in EPPI. Obviously, normal distribution model is not accurate enough and the result is always a constant which cannot be adjusted to deal with different situation. Owing to the design of adjustment function against external changes, EPPI are much more robust than the normal distribution method. In conclusion, the optimization using formula (11) is necessary and reasonable.Figure 7
Prediction of users’ behavior with two methods.Figures8 and 9 exhibit the impact of budget and number of rated tasks on the final expense and number of finished tasks. Figure 8(a) shows the adjustment of expense Ri in the three cases which start with different budget. Figure 8(b) shows the adjustment of expense Ri starting with different number of rated tasks. Obviously, the expense has the positive correlation with Rij and Xi and will converge to the minimum balanced value as the cycle grows. According to the micro and macroadjustment, the price threshold will adjust and converge to a balance value to make the rated tasks all finished, no matter what the initial conditions are. Under this value the user selection algorithm will work out a plan which has the minimum expense.Figure 8
Changes of expense over time.
(a)
Impact of budget to expense
(b)
Impact of amount of rated tasks to expenseFigure 9
Adjustment of expense and number of finished tasks.
(a)
Impact of budget on number of finished tasks
(b)
Adjustment to number of finished tasksFigure9(a) exhibits the number of finished tasks adjustment for the different initial budget value. Figure 9(b) shows the impact of different number of rated tasks on the number of finished tasks. The primary object of EPPI is to finish all the rated tasks. The results of these cases all finally reached target owing to the adjustment mechanism. The amount of finished tasks converges to a balance value. And these balance values of Xi are converged to equal to the number of rated tasks. These results of experiments indicate the user incentive mechanism in EPPI is feasible and effective.Figure10 shows the reward payment of six participants. For good participants (GP), the more they participate in tasks, the more the E-cents they will obtain. For malicious participants (MLP) with different attack probabilities, E-cents of malicious participants who have higher attack probabilities drop down more quickly. But their E-cents are not always decreasing, because malicious participants may send correct reports to gain E-cent and then send false reports randomly, known as on-off attacks [24]. However, the E-cents of malicious participants still maintain a trend of decline and drop down to a very low level eventually. This is because the punishment has a larger influence on E-cents compared to reward.Figure 10
Reward payment based on participants’ behavior.


### 5.4. Security Analysis

Theorem 3.
The server cannot associate a sensing report with a particular participant.Proof.
No matter participants want to participate in a task or buy service from the server, they only need to submit E-cents and their participant IDs are never needed. Suppose that the server recorded the correlation between E-cents and participants when giving E-cents to participants. It implies that the server can associate a participant with its report by recognizing the pledge of the report. Nevertheless, since E-cent is bearer currency, a participant can exchange its E-cents with other participants in the mix zone before submitting them. Since the exchange of E-cent is random and anonymous, the original correlation between E-cents and participants will be broken. The server will not be able to recognize a participant with its submitted E-cents.Theorem 4.
Multiple reports sent by the same participant are not linkable.Proof.
Suppose that the server recorded the correlation between E-cents when giving E-cents to participants. It implies that the server knows which E-cents are sent to the same participant and thus can associate multiple reports with the same participant. But after a participant exchange its E-cents with others in the mix zone, the original correlation between E-cents will be broken. Moreover, every time a participant exchanges E-cents in mix zone, he/she can choose a different exchanger for each E-cent. Though one of exchangers is collusion attacker, the attacker can only collude with the server to recognize the participant once but cannot associate multiple reports with the same participant.
Malicious participants may try to exploit the flaw of E-cent operations to obtain additional unfair profits. The following theorems prove that EPPI is resilient against such malicious behaviors.Theorem 5.
A malicious participantPi cannot get an additional unfair E-cent by exchanging its fake E-cent MCi∗ with another participant Pj.Proof.
WhenPj delivered MCi∗ to the server for E-cent renewal, Pj would be informed that MCi∗ is fake. Though Pj has sent MCj to Pi during exchange, Pj still had the copy of MCj and knew the secret number bj in MCj. Therefore, Pj could prove the ownership of MCj by submitting Cj and bj to the server, while Pi could not. The server would compensate Pj with an E-cent after checking bj and Cj. The server also invalidated MCj and new E-cent given to Pj. Finally, Pi did not get any unfair E-cent from the case. Meanwhile, Pj did not suffer any loss.Theorem 6.
A greedy participantPi cannot get an additional unfair E-cent from its exchanger Pj by launching the dispute arbitration operation for its own marked E-cent and the renewal operation of the received marked E-cent.Proof.
WhenPi launched dispute arbitration and proved the ownership of MCi with Ci and bi, the server would announce the information to all participants. When Pj knows MCi is invalidated, Pj could also launch dispute arbitration to prove the ownership of MCj, which would invalidate Pi’s new E-cent Ci′ during the renewal operation and generate a new E-cent Ci′′ for Pj. Finally, Pi did not get any unfair E-cent from the case. Meanwhile, Pj did not suffer any loss.


## 5.1. Evaluation Metrics

(i)
Anonymity level is the probability that the server traces a participant.
(ii)
Incentive effect is the impact of different price threshold and privacy level on participants’ bidding price, the change of a particular user’s bidding price, the adjustment of price threshold, number of finished tasks and expense, the comparison of two methods to predict users’ behavior, and the motivation of a user in different cases.


## 5.2. Privacy Evaluation

Tracing attack takes place when the server distinguishes a participant from other participants by associating submitted reports with the participant. In this attack, the server needs to link a certain ratio of reports with a participant. If the server succeeds in tracing a participant, the server will be able to analyze and profile the participant’s location trace or at least reduce the anonymity level of the participant. We evaluate the anonymity level of a participant in terms of its resilience against tracing attacks by calculating tracing probability. Though the selection of exchanger is anonymous and random, the server can link an E-cent to a participant by randomly matching the exchange pair. Its difficulty depends on the number of online participants in the mix zone. When a participant wants to send a report, he/she needs to randomly selectyi E-cents from y E-cents of her/her own and submit them to the server as pledge. As long as one of the yi E-cents is linked to him/her, the server can link the report to the participant. Therefore, the probability that a report is linked with a participant can be calculated as follows:(20)Pa report is linked with a participantyi=∑j=1Cyyi∑C∈Θ1Cyyi1nC,where Θ represents the selected E-cent set and nC represents the number of online participants at the moment the E-cent C is exchanged.Figure3(a) shows the probability of the server identifying a participant through tracing attack under varying required pledge of one report when the ratio of traced reports is set to 0.2. We can observer that as the pledge increases, the participant is more likely to be traced. This is because if a participant submits more E-cents to the server as pledge, the server will have more alternative information to trace the participant. However, we notice that even though the pledge is set to the highest value, the tracing probability still maintains a very low value (less than 0.23). As the number of task cycles increases, more participants participate due to the incentive mechanism. That is why the tracing probability keeps decreasing as the number of cycles increases. Figure 3(b) shows the impact of traced report ratio on tracing probability when pledge is set to 20. Even though the ratio is set to 0.1, the tracing probability is less than 0.2. When the ratio is set to 0.3, the tracing probability approaches 0, which means that it is almost impossible for the server to trace a participant.Figure 3
Resilience against tracing attack.
(a)
Impact of required pledge
(b)
Impact of traced report ratio


## 5.3. Incentive Evaluation

Figure4 shows the influence of different price threshold and subregions on users. The parameters for users are initialized in the range randomly obeying the normal distribution. The users’ sensitivity of privacy leakage levels Pij is initialized in [1, 5], and level 5 represents the highest sensitivity of privacy leakage level. User’s psychological thresholds Kij are generated in range [0,50]. The remaining flow of user’s mobile x1 and the remaining power of user’s mobile x2 are represented in percentage. The performance of user’s mobile x3 and user’s idle degree x4 are restricted in (0, 0.5), while the balances in users’ accounts x5 are represented by the number in [0,10].Figure 4
The influence factor of bidding price.
(a)
Impact of budget on bidding price distribution
(b)
Impact of user privacy on bidding price
(c)
Changes of bidding price on a particular userFigure4(a) shows how users respond to different price threshold of last cycle which the server sends them. Three different budgets are chosen to evaluate the distribution of participants in various price thresholds. As the expected price adds, the number of participants increases. At the meanwhile, the number of users with lower price also increases. This is due to the expected increase in profits that will stimulate the users’ motivation to participate, which increases the number of participants and decreases price according to our theory.Figure4(b) exhibits the impact of different users with various sensitivity of privacy leakage levels on their price bidding. Data of the experiment reflect the strong relationship between user sensitivity of privacy leakage level and their bidding price as we expected in definition. Privacy level 1 is the lowest level and level 5 is the highest. In all participants, privacy level 1 is the majority and no users with level 5 take part in the project. According to the definition of user motivation, the sensitivity of privacy leakage level indicates user’s possibility of finishing task. The lower the sensitivity of privacy leakage level is, the more accurate the data the user will send is, and the chance to join the mission successfully is larger.Figure4(c) shows the bidding price of a particular user who would like to participate. The case starts with budget Ri=200. Because the motivation of user has the positive correlation with Rij, the change of Rij will lead to change in user’s motivation; furthermore, the bidding price will be influenced by motivation. In other words, the change of user’s motivation will finally reflect on the change of his/her bidding price and number of tasks he/she wants to participant in.Figure5 shows the change of unit price threshold and the result of user selection in a given subregion. Three cases are designed to test the performance of MPI mechanism. These cases start with different budgets: surplus budget Ri=50, excessive budget Ri=400, and approximate appropriate budget Ri=200. In Figure 5(a) the unit price threshold of server will be adjusted by Ai and Ri, which leads to the fluctuation of number of price thresholds Rij. And as expected, the unit price threshold will finally converge to the balanced value no matter what the initial condition is. The balanced value of Rij reflects the average cost of one task for users. Figure 5(b) is the result of user selection. Results of selection of three cycles (1st, 6th, and 9th) which start with surplus budget Ri=50 are exhibited. In each cycle, we calculate the budget to see the impact of budget on a number of participants.Figure 5
The adjustment of unit price and result of user selection.
(a)
Changes of unit price threshold
(b)
The result of user selectionWe evaluate our reward allocation scheme by comparing its incentive result with three representative allocation schemes [31]: grey prediction (GP), proportional allocation (PA), and random allocation (RA). Figure 6 shows the total number of received sensing reports using four schemes in different task cycles. In this figure, EPPI received more reports at all cycles, which means it achieves the best incentive effect among all allocation schemes. Compared with other schemes, EPPI considers the historical distribution of participants and models the problem specifically with logistic function. According to Figure 6, the number of reports increases gradually over time until a steady status is reached. As the expectation of Algorithm 1, in each cycle, participants with bidding price lower than the threshold were chosen in increasing order by price averagely, which makes sure that the total expense will be minimum. In addition, the average distribution of task achieves the second target of EPPI.Figure 6
Number of received sensing reports over time.Figure7 shows the result of two methods to predict users’ behavior which have been mentioned in Section 4.3. Two situations are designed to compare the methods, both of which have the same condition starting with excessive budget Ri=400. In addition, in order to the better evaluate the reaction of two methods to the external stimulation, the number of rated tasks doubled from 20 to 40 in the 4th cycle, and the number of registered users reduced by half in the 9th cycle. The data of normal distribution model is the result that only relies on the prediction of unit price calculated by normal distribution function. And the data of EPPI prediction model is the result using the optimized adjustment mechanism in EPPI. Obviously, normal distribution model is not accurate enough and the result is always a constant which cannot be adjusted to deal with different situation. Owing to the design of adjustment function against external changes, EPPI are much more robust than the normal distribution method. In conclusion, the optimization using formula (11) is necessary and reasonable.Figure 7
Prediction of users’ behavior with two methods.Figures8 and 9 exhibit the impact of budget and number of rated tasks on the final expense and number of finished tasks. Figure 8(a) shows the adjustment of expense Ri in the three cases which start with different budget. Figure 8(b) shows the adjustment of expense Ri starting with different number of rated tasks. Obviously, the expense has the positive correlation with Rij and Xi and will converge to the minimum balanced value as the cycle grows. According to the micro and macroadjustment, the price threshold will adjust and converge to a balance value to make the rated tasks all finished, no matter what the initial conditions are. Under this value the user selection algorithm will work out a plan which has the minimum expense.Figure 8
Changes of expense over time.
(a)
Impact of budget to expense
(b)
Impact of amount of rated tasks to expenseFigure 9
Adjustment of expense and number of finished tasks.
(a)
Impact of budget on number of finished tasks
(b)
Adjustment to number of finished tasksFigure9(a) exhibits the number of finished tasks adjustment for the different initial budget value. Figure 9(b) shows the impact of different number of rated tasks on the number of finished tasks. The primary object of EPPI is to finish all the rated tasks. The results of these cases all finally reached target owing to the adjustment mechanism. The amount of finished tasks converges to a balance value. And these balance values of Xi are converged to equal to the number of rated tasks. These results of experiments indicate the user incentive mechanism in EPPI is feasible and effective.Figure10 shows the reward payment of six participants. For good participants (GP), the more they participate in tasks, the more the E-cents they will obtain. For malicious participants (MLP) with different attack probabilities, E-cents of malicious participants who have higher attack probabilities drop down more quickly. But their E-cents are not always decreasing, because malicious participants may send correct reports to gain E-cent and then send false reports randomly, known as on-off attacks [24]. However, the E-cents of malicious participants still maintain a trend of decline and drop down to a very low level eventually. This is because the punishment has a larger influence on E-cents compared to reward.Figure 10
Reward payment based on participants’ behavior.


## 5.4. Security Analysis

Theorem 3.
The server cannot associate a sensing report with a particular participant.Proof.
No matter participants want to participate in a task or buy service from the server, they only need to submit E-cents and their participant IDs are never needed. Suppose that the server recorded the correlation between E-cents and participants when giving E-cents to participants. It implies that the server can associate a participant with its report by recognizing the pledge of the report. Nevertheless, since E-cent is bearer currency, a participant can exchange its E-cents with other participants in the mix zone before submitting them. Since the exchange of E-cent is random and anonymous, the original correlation between E-cents and participants will be broken. The server will not be able to recognize a participant with its submitted E-cents.Theorem 4.
Multiple reports sent by the same participant are not linkable.Proof.
Suppose that the server recorded the correlation between E-cents when giving E-cents to participants. It implies that the server knows which E-cents are sent to the same participant and thus can associate multiple reports with the same participant. But after a participant exchange its E-cents with others in the mix zone, the original correlation between E-cents will be broken. Moreover, every time a participant exchanges E-cents in mix zone, he/she can choose a different exchanger for each E-cent. Though one of exchangers is collusion attacker, the attacker can only collude with the server to recognize the participant once but cannot associate multiple reports with the same participant.
Malicious participants may try to exploit the flaw of E-cent operations to obtain additional unfair profits. The following theorems prove that EPPI is resilient against such malicious behaviors.Theorem 5.
A malicious participantPi cannot get an additional unfair E-cent by exchanging its fake E-cent MCi∗ with another participant Pj.Proof.
WhenPj delivered MCi∗ to the server for E-cent renewal, Pj would be informed that MCi∗ is fake. Though Pj has sent MCj to Pi during exchange, Pj still had the copy of MCj and knew the secret number bj in MCj. Therefore, Pj could prove the ownership of MCj by submitting Cj and bj to the server, while Pi could not. The server would compensate Pj with an E-cent after checking bj and Cj. The server also invalidated MCj and new E-cent given to Pj. Finally, Pi did not get any unfair E-cent from the case. Meanwhile, Pj did not suffer any loss.Theorem 6.
A greedy participantPi cannot get an additional unfair E-cent from its exchanger Pj by launching the dispute arbitration operation for its own marked E-cent and the renewal operation of the received marked E-cent.Proof.
WhenPi launched dispute arbitration and proved the ownership of MCi with Ci and bi, the server would announce the information to all participants. When Pj knows MCi is invalidated, Pj could also launch dispute arbitration to prove the ownership of MCj, which would invalidate Pi’s new E-cent Ci′ during the renewal operation and generate a new E-cent Ci′′ for Pj. Finally, Pi did not get any unfair E-cent from the case. Meanwhile, Pj did not suffer any loss.


## 6. Conclusions

This paper firstly proposed a unit bearer exchangeable digital currency called E-cent and a corresponding incentive mechanism EPPI to achieve privacy preservation and incentive enhancement simultaneously for participatory sensing systems. E-cent is exchangeable and can be utilized to participate in tasks anonymously by participants. EPPI is an E-cent-based user incentive mechanism, which uses theory in economics and psychology. It can dynamically adjust the budget to regulate the number of completed tasks to reach the amount of rated tasks. It can not only protect the privacy of participant, but also adjust the distribution of tasks to participants averagely as well as adjust the cost to minimum. Extensive simulation results and theoretical analysis have shown that EPPI is substantially resilient against different kinds of attacks and achieves both anonymity and incentive requirement simultaneously.



---

*Source: 2593537-2018-01-16.xml*