logo资料库

移动众包系统中具有隐私保护的激励机制.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：1.51M 资料格式：pdf 举报 版权申诉
第1页 / 共15页
第2页 / 共15页
第3页 / 共15页
第4页 / 共15页
第5页 / 共15页
第6页 / 共15页
第7页 / 共15页
第8页 / 共15页
资料共15页，剩余部分请下载后查看
    An incentive mechanism with privacy protection in mobile crowdsourcing systems
    1 Introduction
    2 Related work
    2.1 On the aspect of incentive mechanisms
    2.2 On the aspect of auction algorithms
    2.3 On the aspect of incentive and punishment strategies
    3 The proposed incentive mechanism
    3.1 The design of privacy protection for mobile crowdsourcing systems
    3.2 Improved two-stage auction algorithm (ITA)
    3.3 Game theory based analysis for trust in mobile crowdsourcing systems
    3.4 Truthful online reputation updating algorithm (TORU)
    3.5 Properties of the proposed incentive mechanism
    4 Numerical simulations
    4.1 The efficiency of ITA
    4.2 The effectiveness of TORU
    5 Conclusion
    Acknowledgments
    References
    Computer Networks 102 (2016) 157–171 Contents lists available at ScienceDirect Computer Networks journal homepage: www.elsevier.com/locate/comnet An incentive mechanism with privacy protection in mobile R crowdsourcing systems ∗ b , c , , Guisheng Yin d , Xiangrong Tong a , Zhipeng Cai Yingjie Wang e Guanying Wu b , Yang Gao a , a School of Computer and Control Engineering, Yantai University, Yantai, 264005, China b College of Computer Science and Technology, Harbin Engineering University, Harbin, 150 0 01, China c Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA d School of Mathematics and Information Science, Yantai University, Yantai, 264005, China e China Japan Friendship Hospital, Beijing, 10 0 029, China a r t i c l e i n f o a b s t r a c t Article history: Received 16 January 2015 Revised 13 March 2016 Accepted 28 March 2016 Available online 1 April 2016 Keywords: Crowdsourcing Incentive mechanism Privacy Auction Reputation 1. Introduction In order to improve the efficiency and utility of mobile crowdsourcing systems, this paper proposes an incentive mechanism with privacy protection in mobile crowdsourcing systems. Combining the advan- tages of offline incentive mechanisms and online incentive mechanisms, this paper proposes an incen- tive mechanism that selects the worker candidates statically, and then dynamically selects winners after bidding. The proposed incentive mechanism includes two algorithms which are an improved two-stage auction algorithm (ITA) and a truthful online reputation updating algorithm (TORU). Through simulations, we verify the efficiency and effectiveness of the proposed incentive mechanism, which can solve the free- riding problem and improve the efficiency and utility of mobile crowdsourcing systems effectively. © 2016 Elsevier B.V. All rights reserved. The market of smartphones has proliferated rapidly in the re- cent years and continues to expand. Mobile crowdsourcing refers to crowdsourcing activities on smartphones or other mobile de- vices. Thanks to the improved, technological smartphone features, including reliable GPS, high resolution cameras, and continuously advanced software, mobile phone users can work on crowdsourc- ing tasks with ease [ 1 , 2 ]. Nowadays, these tasks involve more than simple site descriptions. Mobile crowdsourcing can be used to collect data either passively or actively. Users who have smart- phones equipped with GPS can be located to create movement profiles [3,4] . In active crowdsourcing, smartphone users upload data including restaurant photos, accurate addresses and busi- nesses (geocoding) or information about menus [5,6] . Meanwhile, mobile crowdsourcing can help with disaster rescue by coordinat- ing rescuers in real time and documenting damage situations. Data R Fully documented templates are available in the elsarticle package on CTAN . ∗ Corresponding author. E-mail addresses: towangyingjie@hotmail.com (Y. Wang), zcai@gsu.edu (Z. Cai), yinguisheng@hrbeu.edu.cn (G. Yin), togaoyang@163.com (Y. Gao), txr@ytu.edu.cn (X. Tong), wuguanying2008@163.com (G. Wu). http://dx.doi.org/10.1016/j.comnet.2016.03.016 1389-1286/© 2016 Elsevier B.V. All rights reserved. gathered via mobile crowdsourcing is up-to-date and accurate, and a large amount of data can be delivered very quickly [7] . A mobile crowdsourcing system is a new form of commer- cial crowdsourcing system. In traditional commercial crowdsourc- ing systems, such as Amazon Mechanical Turk [8] , an employer submits a task to the crowdsourcing platform and defines how much the workers will be paid per task and how the workers have to provide proof of a completed task. Random workers from the crowd choose to work on the task and submit the required proof to the crowdsourcing platform. The work proof is forwarded to the employer, who pays the worker if the task is completed success- fully. However, in mobile crowdsourcing, it is common that work- ers are coming and bidding for a specific task sequentially, and the decision on accepting or denying a worker’s bidding must be made by the platform instantly upon the user’s arrival. Therefore, com- pared with the traditional commercial crowdsourcing systems, mo- bile crowdsourcing systems need higher real-time performance. In addition, in order to obtain better benefit and effectiveness, there is a bidding process for workers in mobile crowdsourcing systems. Realizing the great potential of the mobile phone sensing, many researchers have developed numerous applications and systems, such as Sensorly [9] for making cellular/WiFi network coverage maps, VTrack [10] for providing traffic information. However, the existing mobile crowdsourcing systems face a serious practical
    158 Y. Wang et al. / Computer Networks 102 (2016) 157–171 Fig. 1. Traditional offline settings and online settings for incentive mechanisms. challenge: providing appropriate incentives for workers to partici- pate and well-perform in tasks. More concretely, a requester needs to establish sufficient rewards to attract workers’ contributions when workers do not solve tasks solely for altruistic motivations. For these reasons, designing an effective incentive mechanism to encourage workers’ contributions is crucial to maintain the perfor- mance of crowdsourcing systems. Therefore, how to maximize the social welfare is one of the most popular interests for mobile crowdsourcing systems. The es- tablishment of incentive mechanisms becomes the focus in the re- search of optimizing mobile crowdsourcing systems. Traditional in- centive mechanisms include two types which are offline settings and online settings. The mobile nature of these distributed compu- tation and sensing powers further complicates the incentive mech- anism design [11] . In a mobile crowdsoucing system, a task is de- scribed and posted by a requester together with the associated re- ward budget. If a worker is interested in a task, he will upload his bidding, i.e. , the solution (sensing time and sensing cost), to this requester [12] . According to this bidding, the requester can determine to accept this worker or reject this worker. The pioneer works mainly refer to the offline incentive mechanisms. The offline incentive mechanisms determine the winners in auction after all the participators upload their bidding [13] . These offline schemes assume that all the users present from the very beginning of one round of task distribution for bidding and cannot accept new bid- ding afterwards (shown in the left part of Fig. 1 ). In other words, the offline incentive mechanisms all fail in a more practical yet dynamic setting of mobile sensing. In order to resolve the prob- lems of offline incentive mechanisms, Zhang et al. [14] proposed an online incentive mechanism, which is shown in the right part of Fig. 1 . However, the online incentive mechanism fails to select the set of candidates from the workers’ reputation database, result- ing in inefficiency in the process of auction. Therefore, we combine offline settings and online settings to design incentive mechanism shown by Fig. 2 . In the proposed incentive mechanism, the plat- form determines the worker set that can be assigned the given task based on the offline incentive mechanism; then once the selected workers arrive, there are transactions between platform and work- ers based on the online incentive mechanism. In addition, we add the privacy protection for the participant workers. Therefore, the proposed incentive mechanism can overcome the disadvantages of offline incentive mechanism and online incentive mechanism, pro- tect workers’ privacy, and improve the efficiency of mobile crowd- sourcing system. Fig. 2. The processing procedure for the proposed incentive mechanism. In the process of an auction between workers and a platform, how to develop an auction algorithm is very important for improv- ing the efficiency of mobile crowdsourcing systems [15] . In addi- tion, there exists a lot of free-riding phenomena in complex net- works such as social networks, computer networks and so on. Un- fortunately, networks cannot automatically adjust the selections of nodes for trust strategies. The individuals in a network have the nature of selfishness, thus an individual prefers to select the strate- gies that can increase its benefit. The free-riders prefer to select a unreliable strategy as their first choice, resulting in the decrease of network benefit [16] . Therefore, how to establish an effective incentive mechanism to inspire the selection of reliable strategies is very important for complex networks. Mobile crowdsourcing systems are developed upon mobile social networks, and they are full of complexities, thus mobile crowdsourcing systems have the features of complex networks. Such features include a heavy tail in the degree distribu- tion, a high clustering coefficient, assortativity or disassortativity among vertices, community structure, and hierarchical structure. Therefore, for mobile crowdsourcing systems, the establishment of an incentive mechanism is also an important research focus.
    Y. Wang et al. / Computer Networks 102 (2016) 157–171 159 With the increase of network scale and number of mobile users, mobile crowdsourcing systems become more and more complex. Thus, an incentive mechanism needs to be established to adjust the benefit equilibrium between workers and a platform in mobile crowdsourcing systems, in order to solve the free-riding problem and promote the mobile crowdsourcing systems to develop steady [17,18] . According to the aforementioned reasons, this paper proposes an incentive mechanism with privacy protection in mobile crowd- sourcing systems. The contributions of this paper are summarized as follows: 1. Combining the advantages of offline incentive mechanisms and online incentive mechanisms, we propose an incentive mechanism that selects the worker candidates statically, and then dynamically selects winners after bidding. Under this incentive mechanism framework, a privacy protection is pro- posed in order to protect the privacy of workers. 2. We design an improved two-stage auction algorithm (ITA) to determine the winners in real-time for the platform, which can overcome the unfairness problem and encourage work- ers to arrive in time. 3. We propose a truthful online reputation updating algorithm (TORU) to update workers’ reputations, which can solve the free-riding problem in mobile crowdsourcing systems. 4. In order to verify the effectiveness of the proposed incentive mechanism, we compare the proposed incentive mechanism with some typical algorithms through simulations. The re- sults show the advantages and improvements of our algo- rithms. The rest of the paper is organized as follows. Section 2 presents the related works. Section 3 introduces the proposed incentive mechanism including ITA and TORU, and analyzes the properties of the proposed incentive mechanism. Section 4 illustrates the simu- lations, along with the parameter settings, followed by the result analysis and discussions. Finally, Section 5 concludes this paper. 2. Related work In mobile crowdsourcing systems, selfishness and privacy pro- tection problems have gained extensive attentions. Thus, how to establish effective incentive mechanisms is a challenging research focus in mobile crowdsourcing systems. Scholars have spent a lot of efforts on the selfishness and privacy protection problems. 2.1. On the aspect of incentive mechanisms Offline settings and online settings are the two typical schemes. Yang et al. [13] proposed an offline incentive mechanism us- ing a Stackelberg game, where the platform is the leader while the users are the followers. Two system models are considered: the platform-centric model where the platform provides a re- ward shared by the participating users, and the user-centric model where the users have more control over the payment they will re- ceive. The scheme of an offline incentive mechanism is shown in the left part of Fig. 1 . However, the offline incentive mechanisms assume that all the users will stay from the very beginning of one round of task distribution for bidding and cannot accept new bid- dings afterwards. In other words, the offline incentive mechanisms all fail in a more practical yet dynamic setting of mobile sensing [19,20] . Zhang et al. [14] proposed an online incentive mechanism. Two online incentive mechanisms based on online reverse auction are provided: threshold-based auction (TBA) and truthful online incen- tive mechanism (TOIM). However, the online incentive mechanisms fail to select the set of candidates from the workers’ reputation database, resulting in inefficiency in the process of an auction. 2.2. On the aspect of auction algorithms The two-stage auction algorithm is applied widely [21] . The process of a two-stage auction algorithm indicates that the first batch of users is rejected and used as the sample which enables making an informed decision on whether to accept the rest of the users. However, this method fails to guarantee the consumer sovereignty, since the first batch of users has no chance to win the auction no matter how low the cost is. This method automatically rejects the first batch of users, so that it encourages users to arrive late. In other words, the users who arrive early have no incentive to report their biddings, which may hinder the users’ competition or even result in task starvation [22] . In addition, Sodagari et al. [23] proposed the on cost-sharing mechanisms in cognitive radio networks. They casted the issues to submodular class of games and showed how a link can be established between the truthful auc- tioning mechanism and the cost-sharing algorithm. However, this approach failed to consider the real-time auction, thus it is not suitable for the online network environment. In [13] , an auction-based incentive mechanism was proposed. The authors utilized the announced total reward R (budget) and user i ’s sensing plan t i (user i ’s willingness on how long he wants to participate in the sensing task) to design a novel auction based on submodular function. In [24] , the authors designed incentive compatible some mechanisms that maximize a requester’s objec- tive under a budget. It is known as budget feasiblity where the mechanism must be designed so that the sum of its payments does not exceed the budget. Therefore, budget and sensing plan are two important factors for designing an effective auction algo- rithm in crowdsourcing systems, such as Amazon Mechanical Turk, a successful crowdsourcing system that performs under a bud- get. However, in the above mechanisms, the auction thresholds are static and cannot be changed dynamically, which induces the un- fair problem. 2.3. On the aspect of incentive and punishment strategies In order to solve the free-riding problem in mobile crowdsourc- ing systems, a lot of incentive and punishment strategies were pro- posed. Many of the incentive mechanisms on crowdsourcing web sites rely on monetary rewards in the form of micro-payments [25–27] . The platform pays workers in the form of cash upon the completion of a task. However, the current pricing schemes fail to solve the social dilemma existing between the workers and plat- form. Zhang et al. [12] proposed a novel class of incentive pro- tocols based on social norms which integrates reputation mech- anisms with the existing pricing schemes currently implemented on the crowdsourcing web sites. However, some potential trustful workers may be isolated because of the unique threshold in this incentive mechanism, so that generates unfair problem. In addition, according to privacy protection, researchers have highlighted security and privacy challenges. The typical proposal PEPSI [28] enable anonymous data collection from mobile users. PEPSI’s extension [29] , considered scenarios where external enti- ties query specific users sensing data and proposed a scheme to hide which user matches a query. Cristofaro et al. [30] proposed a privacy-enhanced participatory sensing infrastructure on the basis of PEPSI. In addition, Li et al. [31] proposed a privacy-aware in- centive scheme with a trustable third party (TTP), which can pro- tect users’ privacy. Wang et al. [32] proposed PEALS framework to support privacy-aware mobile crowdsourcing, which can help po- tential contributors assess the privacy and security risks they face
    160 Y. Wang et al. / Computer Networks 102 (2016) 157–171 Fig. 3. The structure of a mobile crowdsourcing system. with a mobile crowdsourcing system and make an informed de- cision about contributing. However, most of the proposals consid- ered the condition of offline mechanisms, so they fail to consider the real-time property according to the online mechanisms. Targeting on the above problems, this paper proposes an in- centive mechanism with privacy protection in mobile crowdsourc- ing systems. Combining the advantages of offline incentive mech- anisms and online incentive mechanisms, this paper proposes an incentive mechanism that selects the worker candidates statically, and then dynamically selects winners after bidding. Under this in- centive mechanism framework, a privacy protection protocol for mobile crowdsourcing systems is designed. In addition, we design an improved two-stage auction algorithm to determine the win- ners for the platform, which can overcome the unfairness prob- lem, and encourage workers to arrive in time. A truthful online reputation updating algorithm (TORU) is proposed to update work- ers’ reputations, which can solve the free-riding problem in mobile crowdsourcing systems. 3. The proposed incentive mechanism Similar to the work in [14] , our objective is to design an online incentive mechanism with the following four properties: In brief, it is common in practical mobile sensing that users are coming and bidding for a specific task sequentially, and the deci- sion on accepting or denying a worker’s bidding must be made by the platform instantly upon the worker’s arrival. Nevertheless, pio- neer works on incentive mechanism are static and offline, in which the concurrent presence of numerous smartphone candidates is re- quired. These offline schemes assume that all the workers will stay from the very beginning of one round of task distribution for bid- ding and cannot accept new biddings afterwards. In other words, the offline mechanisms all fail in a more practical yet dynamic set- ting of mobile phone sensing. In this paper, we combine offline incentive mechanism and on- line incentive mechanism to propose an incentive mechanism that selects the worker candidates statically, and then dynamically se- lects winners after bidding. Assuming the set of worker candidates = , where n expresses the total number of worker is C candidates. Therefore, zero arrival-departure is considered in this paper because of the dynamic auction process. There are three cases in one transaction between the platform and a worker: (1 , , 2 ..., ) n 1. The platform issues the task and budget B to worker i who . The platform rejects and sensing plan t i uploads bidding b i worker i because of discontent. 2. The platform issues the task and budget B to worker i who 1. Computational efficiency . An online mechanism is computa- is not interested in the task. tionally efficient if it has a polynomial time complexity. 2. Individual rationality . A user will get nonnegative utility upon completing a sensing task. 3. Profitability . The platform will get nonnegative utility at the 3. The platform issues the task and budget B to worker i who uploads bidding b i . The platform accepts worker i and gives the payment to worker i , then worker i uploads the sensing report. and sensing plan t i end of a sensing task. 4. Truthfulness . A mechanism is truthful, or incentive compat- ible, if a bidder cannot improve her utility by submitting a bidding price deviating from her true value in spite of oth- ers’ bidding prices. The mobile nature of these distributed computation and sens- ing powers further complicates the incentive mechanism design. Because the platform may reject the workers, it will inspire workers to upload appropriate values of bidding and sensing time. Therefore, in order to be the winner in the auction and obtain the reward, a worker will be inspired to perform well. The structure of this mobile crowdsourcing system is shown in Fig. 3 . In this paper, we divide the crowdsourcing process into 14 steps. Steps (6), (7) and (13) are the focus of this paper.
    Y. Wang et al. / Computer Networks 102 (2016) 157–171 161  = ϕ ϕ ϕ > ( ..., , 1 , 2 In this model, the platform announces a set ) m of tasks for the workers to select. According to the selected task, worker i has a contribution value v i 0 to the platform, and also , which is private and other workers do not has an associated cost c i know it. Worker i ’s bidding is represented by b i is the reserved price of the service worker i wants to sell. The sensing plan of worker i is represented by t i , which is the number of the time units during which worker i can provide the sensing service. Based on the special task, worker i first submits b i to the platform. Upon receiving the bidding and sensing plans from all the workers, the platform selects a subset of workers as winners W and determines the payment p i for each winning worker i . There- fore, the utility of worker i based on the submitted sensing plan is shown by Eq. (1) : , where b i and t i = u i − c i p i , 0 , ∈ if i W otherwise (1) ≥ 0, where t i = According to the reality, we define t i τ is the unit cost of workers, and 0 τ × t i , where 1. In addition, p i is determined by t i 0 repre- sents that worker i will not participate in this task. In this paper, = < we define c i τ < and the budget B , and B represents the budget for a specific task determined by the platform. τ , however, c i at the end of sens- ing task. Therefore, the real utility of worker i at the end of sensing task is derived by Eq. (2) : In Eq. (1) , c i will evolve with the change of sensing time t i is determined by the submitted t i and , = u i ∈ if i W otherwise − c i p i (2) , 0 = where c i represents the real associated cost that derived by c i τ × t i , indicates the real sensing time of work i . According and t i to the above analysis, p i is derived by Eq. (3) : = p i × B t i T (3) V B T (W ) − P (W ) λ + 1 where T indicates the maximal sensing time for this task, and we define = ¯u ≥ 1 . The utility of platform is defined by Eq. (4) : λ × log (W ) ∈ W i is the total benefit of the platform , and where V = (W ) P is the total payments for the workers . In addition, is the specific contribution value that worker i brings to the plat- v i form, and v i is evaluated through the sensing time submitted by worker i . The log term in Eq. (4) captures the platform’s marginal diminishing return on the selected workers, which conforms to the λ is a system parameter that usual economic assumption [14,33] . can control the gradient of the diminishing return, and = p i ∈ W i λ > (4) v i 1. A worker will be isolated by the platform and is forbidden to interact with requesters and participate in any task if his repu- tation is low. In this case, the social norm does not require the worker to do anything. On the contrary, the platform activates the worker by allowing him to participate in tasks if his reputation is high, and the social norm requires the worker to devote a high level of effort s in his transactions. 3.1. The design of privacy protection for mobile crowdsourcing systems In the process of sensing, some workers may want other worker’s bidding, sensing data and updated reputation to adjust their strategies in order to get more benefit. Even worse, there may be malicious attackers in the network. Once they obtain oth- ers’ private data, they attack the workers whose privacy leaked. In order to protect the privacy of workers who participates in the task, we design a privacy protection for mobile crowdsourcing sys- tems. In this paper, we divide privacy protection into three stages: uploading bidding stage, uploading sensing data stage and updating reputation stage. N, + In this privacy protection, we give the system initialization and cryptographic schemes. i) Considering the computation efficiency reasons, we apply time-lapse cryptography (TLC) service in our pri- vacy protection mechanism. TLC service not only has hiding prop- erty, but also blinding property [34] . At a given time T the ser- vice publishes a public key so that anyone can use it, even anony- mously. Senders encrypt their messages with this public key whose private key is not known to anyone, until a predefined and specific future time T at which point the private key is constructed and published. At or after that time, anyone can decrypt the ci- phertext using this private key. It will prevent workers from re- vealing committed subtask selections, and prevent platform from discarding received commitments, revealing committed subtask se- lections. Platform publishes a public key of a non-malleable en- cryption scheme, and sends the corresponding private key only when each stage ends. ii) In order to guarantee the security, we apply Blinded Nyberg-Rueppel signature scheme [18,35] . Apply- ing this scheme, signers do not need to verify the authenticity of them, and signee can obtain their information from all signers. The specific process is shown as follows. The signer randomly se- ∈ = lects k to signee; The signee ran- R Z q and sends r ∈ = , t 2 domly chooses t 1 and R Z q , computes R = + −1 mod q ) ) ( to the signer; The signer . Then, he sends r t t 3 r R = + 1 k ( and sends s to the signee; The signee x r computes s = + , and the pair ( R, S ) is the signature computes S s t 1 t 2 = for M . Finally, others check whether M to verify the correctness. mod q ) π ( −S y g mod p ) mod p ) mod p ) mod q ) , t 3 M r k ( g t 2 y t 1 g R R ( t 3 ( ( 1. Uploading bidding )) T ID K ppub ) ps i E T PK | (Cb i | (Eb i , Cb i sign i | | (b i t i , where rb i We assume that worker i is selected by the platform to par- ticipate in a task, and worker i is interested in this task. First of all, we define TID as the task identifier. We use TPK to represent the time-lapse encryption key. In the stage of uploading bidding, worker i generates a pseudonym ps i randomly. In order to upload his bidding without expos- ing his information to others, worker i encrypts his bidding, = sensing time and pseudonym as Eb i by plat- | . Then worker i makes a commit- form’s public key K ppub = ) is the bit string gen- ment Cb i T ID rb i erated randomly as the proof of correctness. Finally, worker = i signs the commitment and sends his bidding request Rb i (i, to the platform. Once the platform re- ceives worker i ’s bidding request Rb i , it will check this bid- | | passes the check, the platform returns a ding request. If Rb i = signed receipt P b i Cb i sign p [ i T ID ] to worker i . Otherwise, the platform discards Rb i . , the platform computes the auction re- When receiving Rb i sult of worker i and the random bit string rb i by applying the platform decryption key. Then the platform determines whether worker i is a winner and the corresponding pay- ment for worker i . If the platform rejects worker i ’s auc- | is set to 0. The platform will encrypt the information tion, p i = (p i ) i as Ew i . A com- K ipub = mitment Cw i is made by the platform, E T PK where rw i is also the bit string generated randomly as the proof of correctness. Finally, the platform signs the commit- = (Cw i , sign p ment and sends the decision P w i to worker i . Once worker i receives the decision from the plat- = form, he will return a signed receipt W w i T ID ] to the platform and begins his sensing work. by worker i ’s public key K ipub | (Ew i | (Cw i | [ P w i | rw i sign i ) T ID T ID )) 2. Uploading sensing data
    162 Y. Wang et al. / Computer Networks 102 (2016) 157–171 | (i In the stage of uploading sensing data, in order to upload his sensing data without exposing his information to others, = worker i sends his encrypted sensing data as Es i K ppub by using the platform’s public key K ppub ex- presses the sensing data of worker i . Then worker i makes a = commitment Cs i is also the bit string generated randomly as the proof of correctness. Fi- nally, worker i signs the commitment and sends his sens- = ing data Rs i to the platform. Once the platform receives worker i ’s sensing data, it returns a signed = receipt P s i ) s i , where s i , sign i Cs i | | Cs i sign p [ i 3. Updating reputation T ID ] to worker i . , where rs i | (Es i | (Cs i | rs i E T PK ) T ID T ID (i, )) ( ) i K ipub t+1 | r i In the stage of updating reputation, the platform returns the updated reputation to worker i through encrypting the in- = formation Er i by worker i ’s public key K ipub . t+1 indicates the updated reputation of worker i . The plat- r i = , where form makes a commitment Cr i rr i is also the bit string generated randomly as the proof of correctness. Finally, the platform signs the commitment = )) to and sends worker i ’s reputation P r i worker i . Once worker i receives the updated reputation = from the platform, he will return a signed receipt W p i sign i T ID ] to the platform. The reputation updating algo- rithm with incentive and punishment will be introduced in Subsection 3.4 . (Cr i , sign p | (Er i | (Cr i | [ P r i | rr i E T PK ) T ID T ID In this privacy protection mechanism, other workers cannot get any information about one’s bidding, sensing data and updating reputation. The privacy protection is designed under PKI infras- tructure which improves the security and time sensitivity further for private data. Therefore, this privacy protection mechanism is privacy-preserving for workers. 3.2. Improved two-stage auction algorithm (ITA) The improved two-stage auction algorithm corresponds to Step (6) and Step (7) shown in Fig. 3 . In Step (6) and Step (7), we de- sign an improved two-stage auction algorithm to determine the winners in real-time for the platform. We divide the auction stage into two stages. The first stage is the sample collection stage that establishes the base for the next stage. Different from the previ- ous solutions, the first batch of workers also have chance to win the auction in order to solve the unfairness problem. This design can encourage workers to arrive in time. The second stage is the competition stage that adjusts the bidding threshold in each trans- action dynamically based on the result from the sample collection stage. The specific process is shown as follows: 1. The platform announces budget B for a specific task and the maximal sensing time T , based on which by combining the κ for historic experience, the platform determines threshold the bidding. for stage 1 2. The platform determines marginal budget B be the payment sum  represents the winner set in stage 1. If the platform accepts worker j , otherwise, the plat- = based on T and B . Let P in stage 1, where b j t j form rejects worker j . The platform repeats this process in > stage 1 until P B . In addition, Eq. (5) expresses the value of B based on the multiple-stage sampling-accepting process [22] which determines the sample size dynamically: = B ≤ κ ,  p j (5) j∈ B ln T 2 be the limited time in stage 1. In addition, we define T Accordingly, the calculation method of the limited time in Table 1 An asymmetric game. X a, b c, c Y c, c a, b X Y stage 1, T , is derived by Eq. (6) : = T T 2 ln T (6) 3. After stage 1, the auction enters stage 2. We obtain the total benefit of the platform V ( M ) in stage 1, where M represents the set of winning workers during stage 1. In stage 2, with new arriving workers, we adjust the bidding threshold each time based on the marginal density. For new arriving worker i, v i = v i V is shown by Eq. (7) : − V (M) (7) M i where v i represents the marginal utility of platform, as well as the specific contribution value that worker i brings to the platform. Marginal utility is defined as: the marginal utility of a good or service is the gain from an increase, or loss from a decrease, in the consumption of that good or ser- vice. Economists sometimes speak of a law of diminishing marginal utility, meaning that the first unit of consump- tion of a good or service yields more utility than the sec- ond and subsequent units, with a continuing reduction for greater amounts. The marginal decision rule states that a good or service should be consumed at a quantity at which the marginal utility is equal to the marginal cost. In this paper, we utilize marginal utility to determine whether accept the worker. Therefore, the density of v i , which can reflect the in- marginal utility for worker i is p i ≤ p i , and creasing density or diminishing density. If b i , the platform accepts worker i , otherwise, it rejects worker i . Once a new worker arrives, the platform computes its marginal density each time, and compares its marginal density with the previous workers’ global result. This pro- cess is repeated until B . > ∈ W i p i ≥ V (W ) P(W ) v i p i ITA improves traditional two-stage auction by solving the un- fairness problem for earlier arriving workers and improve the effi- ciency of auction, which is summarized in Algorithm 1 . 3.3. Game theory based analysis for trust in mobile crowdsourcing systems In order to establish the reputation updating algorithm, we an- alyze the behavior of workers in mobile crowdsourcing systems firstly. In this subsection, we utilize the asymmetric game to an- alyze the relationship between workers’ sensing reports and the platform. Game theory is a study of strategic decision making. Specifically, it is the study of mathematical models of conflict and cooperation between intelligent rational decision-makers [36] . Asymmetric games are games where there are not identical strategy sets for both players. For instance, the ultimatum game and similarly the dictator game have different strategies for each player. It is possible, however, for a game to have identical strate- gies for both players, yet be asymmetric. For example, the game showed in Table 1 is asymmetric despite having identical strategy sets for both players (player X and player Y ), where a, b and c ex- press the payoffs.
    Y. Wang et al. / Computer Networks 102 (2016) 157–171 163 Algorithm 1 Improved two-stage auction algorithm (ITA) Input: n , B , T , κ Output: 8: 9: 7: ; ; if 10: + v j ; Winners 1: Stage 1: = ln T B 2: B 2 = ln T T 3: T = = = 2 ) (W 0 ; V 1 ; P 0 ; 4: j ≤ n and P ≤ B 5: while j do = = t j ; t j b j 6: b j ; ≤ κ then b j t j  ←  ; j ← × B ; t j p j ← + T P p j P ; ← (W (W ) ) V V 11: 12: end if ← + j j 13: 14: end while 15: Stage 2: ← (W ) 16: P ; P = 1 ; 17: i ≤ n and P 18: while i = = t i ; t i b i 19: b i ; = v i (W V i 20: ≥ V v i (W ) if P(W ) p i  ←  ← (W ) P ← (W ) V 24: 25: end if ← + 1 ; i i 26: 27: end while (W ) − V then ; i + ) (W ; p i + v i ) (W ; P V (W ) 1 ; 22: 23: 21: ) ≤ B do = ; p i × B ; t i T The interaction between a worker and a platform in a task, which is defined as a transaction , can be modeled as an asymmet- ric gift-giving game. From the aspect of the platform, it makes the payments for workers’ sensing work according to workers’ bidding and sensing plans. However, the platform gains different payoffs based on the different results about sensing reports. If a worker provides a truthful sensing report, the platform will gain a high payoff. If a worker is selfish, i.e. , the worker provides an distrustful report, the platform will gain a low payoff. . T rust, Distrust From the aspect of workers, because a worker receives the pay- ment in advance, he can strategically choose his action, i.e. , de- termines the level of effort devoted to this task. The quality of worker’s sensing report affects not only his own payoff, but also that of the platform. For simplicity, we define q i to be the quality type of worker i’s sensing report , which is chosen from a binary set = Q Trust indicates the quality of the sensing report is high, i.e. , rep- resents the level of confidence about the reliability and correctness of the reported sensing data. Distrust indicates the quality of the sensing report is low. In order to quantize the quality of a sensing report, we define q as the specific quality of the sensing report, ∈ where q [0, 1]. Because of the selfishness of workers, they may select to expend less cost and time for the task, so that they can α as the threshold for obtain more benefit. In this paper, we define quality of sensing report , so the quality types of worker i ’s sensing report are determined by Eq. (8) . The payoff matrix of one trans- Table 2 Payoff matrix of one transaction. Trust Distrust Select No select − p i v i /, 0 − c i −p i , p i , p i /, 0 action is illustrated in Table 2 , which is specified as follows: = q i T rust, Distrust, ≥ α i f q otherwise (8) In the condition that worker i is selected by the platform, if = T rust, q i for solving this task, and he can ob- worker i spends c i tain payment p i from the platform, thus the payoff of worker i is − c i . This part of task is solved by worker i and the platform p i receives a benefit of v i . If = q i worker i free-rides through taking the payment and consuming a low cost, which is approximated by 0 here, and the platform receives no benefit. Thus, in this condition, the payoff of worker i is p i . This part of task is not solved and remains open for future workers. , thus the payoff of the platform is v i , and the payoff of the platform is - p i − p i Distrust, In order to find evolutionary stable strategy, we give the defini- tion of Evolutionary Game Theory (EGT). EGT is the application of game theory to evolving populations of lifeforms in biology. EGT differs from classical game theory by focusing more on the dy- namics of strategy change as influenced not solely by the quality of the various competing strategies, but by the effect of the fre- quency with which those various competing strategies are found in the population [37,38] . In EGT, Evolutionary Stable Strategy (ESS) is a strategy which, if adopted by a population in a given environ- ment, cannot be invaded by any alternative strategy that is initially rare. That is to say, once the ESS is fixed, alternative strategies will be prevented by natural selection from invading successfully. An ESS is an equilibrium refinement of the Nash equilibrium [39] . Therefore, we need to find a stable strategy based on EGT, i.e. , ESS in EGT under this dynamic network environment [40] . In mobile crowdsourcing system, the strategies will change dynam- ically. With the evolution of mobile crowdsourcing system, there exists an ESS. Therefore, how to find the ESS is an important re- search content when we establish an effective incentive mecha- nism. Based on EGT, we explore the ESS in this paper. Now we consider ESS, i.e. , to find the Nash equilibrium strat- egy [41] . ESS is the functional balance with genuine stability and predictive capability in EGT. When we analyze the stability of the whole mobile crowdsourcing system based on EGT, we must first identify some parameters. In this paper, we first assume the to- tal number of the workers is fixed, x is defined as the propor- tion of the truthful workers in a mobile crowdsourcing system, and y is defined as the proportion of the distrustful workers in + a mobile crowdsourcing system, x is de- fined as the expected payoff who adopts the Trust strategy, U 2 is defined as the expected payoff who adopts the Distrust strategy, and U is defined as the average excepted payoff of all the work- = · p and ers. According to Table 1 , we can get U 1 = , are fixed payment and real cost where p and c U in a mobile crowdsourcing system. 1 . In addition, U 1 = , U 2 · U 1 + − c ) · U 2 · (p = y y x x y Therefore, based on the EGT, we can get the evolution models according to Trust strategy and Distrust strategy respectively, which are shown by Eqs. (9) and (10) : = dx dt = dy dt x − x ·U 1 U t − y ·U 2 U t y (9) (10)
    164 Y. Wang et al. / Computer Networks 102 (2016) 157–171 where t represents evolution generation, which means the times t means the updated time step, of transactions in this paper, and which is set as 1 in this paper. Eqs. (9) and (10) represent the evo- lutionary game model. They can reflect the dynamic changing of different types of individuals in a system, as well as deduce the final convergence status of this system. Therefore, we can utilize Eqs. (9) and (10) , i.e. , evolutionary game model, to discuss the dy- namic changing of different types of individuals and find the ESS. In order to get ESS, i.e. , find the Nash equilibrium point, it 0. Through computing = = dx = dt < 0, we can obtain that x 0 and F ( x ) F equilibrium point, i.e., Distrust strategy becomes the ESS. ) 0 and F ( x should satisfy F 0 is the Nash dx dt (x ) (x ) = = < Therefore, from the aspect of workers, Distrust strategy is a Nash equilibrium strategy, which results in the free-riding phe- nomenon. In the zero arrival-departure model, the payment is made before the task is done, and a worker always has the in- centive to take the payment and devote no efforts to accomplish the task, which is known as free-riding [42] . The definition of free- riding is that the inherent feature of an entity is to maximize its utility while minimizing the utilities of other entities, which leads to under-provision of goods or services, or when it leads to overuse or degradation of a common property resource. This feature makes selfish behavior to dominate the evolution direction of the whole system, which incurs the free-riding problem. It seriously influ- ences the overall balance and reduces the efficiency of a system [43–45] . 3.4. Truthful online reputation updating algorithm (TORU) In order to solve free-riding problem in mobile crowdsourcing systems, we propose a truthful online reputation updating algo- rithm (TORU) to control the gaming process by effective means to make Trust strategy to be the preferred strategy for workers. Therefore, we can ensure a system’s overall income to be optimal. In this paper, an effective incentive strategy when updating work- ers’ reputations is established. We design an updating method for a worker’s reputation according to the quality of its sensing report t to be the reputation of worker i in one transaction. We define r i t+1 to be the reputation of worker before sensing this task, and r i = i after completing this transaction. Assume R is a reputation set, where r max represents the maximal reputation. A high reputation relates to a worker’s good social status, which re- flects his good behavior on completing tasks in the past. The repu- tation of each worker is maintained by the platform. It is updated depending on the report of the requester about the outcome of the transaction. t ≥ θ , the θ , the platform does platform assigns this task to worker i . If r i not assign this task to worker i . Therefore, the update for the rep- utation of worker i after this transaction is derived by Eq. (11) : θ for a worker’s reputation. If r i There is a threshold , , , 2 1 0 r max t < ..., ⎧ ⎪ ⎨ t + ( r i min θ − 1 ⎪ ⎩ , , 0 t , r i t+1 = r i , 1 ) r max , = t ≥ θ i f q i T rust and r i = t > Distrust and r i i f q i = t = Distrust and r i i f q i θ t < i f r i However, the above method has a problem. In the above method, there is only one threshold for a worker’s reputation, θ . Under this condition, once a worker selects Distrust which is strategy once, he will never be selected by the platform forever, i.e. , be isolated all the time, which is unfair for the potential trustable workers. To solve this problem, we improve the above method to establish a more fair incentive mechanism. θ0 , θ1 , We define a set θ2 ..., , θ old set for different tasks, where 0 θ tation threshold in the system, i.e., a mapping θ responding reputation threshold, i.e., ϕ θ , 1 m . Therefore, Eq. (11) is improved by Eq. (12) : θm as the reputation thresh- represents the smallest repu- θ . There exists , 1 0 which means that each task has a cor- → →  − θ0 , ..., 2 → ≥ θ σ : θ m θ m , ..., → , ϕ ϕ 2 2 1  = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ t + ( r i min − 1 θ , k θ0 , θ0 , θ0 t , r i − 1 , t+1 = r i , 1 ) r max , = i f q i T rust and r i = Distrust, r i i f q i = Distrust, r i i f q i = Distrust, i f q i r i = Distrust, i f q i r i θ t < i f r i t ≥ θ θ t > θ t > t = θ t = θ k k k and k and k and k and θ θ θ θ θ0 > = θ0 θ0 > = θ0 k k k k (12) k k ϕ In the improved reputation updating process, we define a repu- tation threshold set to solve the problem such that only on a repu- tation threshold will incur the unfairness problem for the potential , the corresponding rep- truthful workers. According to the task = θ . In the case of q i utation threshold should be = = t = k k θ θ0 θ , and the case of q i and , we t+1 = 0 θ0 . This design not only punishes the distrustful work- set r i ers, but also gives a chance to them in order to incentive them to select good behavior in future. In this case, if the workers behave credibly next time, their reputations will be increased, otherwise, they will be rejected by the platform in future. Therefore, in order to obtain the maximal benefit in a long term, workers must select truthful behavior to be their preferred strategy, which makes Trust strategy become the ESS. t > Distrust, r i θ θ > and Distrust, r i k k θ In addition, the repetition attack may occur in process of crowdsourcing. Repetition attack is defined that an attacker needn’t decrypt a packet, he can simply re-send sensing data just as is at a later time. This may pollute the data sent by the original worker and cause a decrease in its reputation. According to this problem, we utilize time sensitivity to identify repetition attackers. In the stage of sensing data processing for worker i , platform will com- pare the data with previous data. If there exists identical data in = previous sensing data, platform will set q i Distrust. The design can recognize repetition attackers in crowdsourcing systems, and punish them on reputations. In order to solve the free-riding problem about the truthfulness of the worker’s sensing report, the proposed reputation updating algorithm inspires the workers to select Trust strategy. TORU is shown in Algorithm 2 . θ θ (11) 3.5. Properties of the proposed incentive mechanism 1 t + In this reputation updating process, if the quality of its sens- t ≥ θ , ing report is high, i.e. , the sensing result is trustable, and r i ≤ r max , the updated reputation adds 1 in the case of r i other- wise, the updated reputation should be r max . When the quality of its sensing report is low, i.e. , the sensing result is distrustful, we θ , the reputation of worker i is punished have two cases: if r i by the platform, which means r i the repu- tation of worker i is also punished by the platform, which means t+1 = θ , the platform does not assign this r i task to worker i, i.e. , worker i cannot participate in this task, so the reputation remains r i t = θ − 1 ; if r i 0 . Otherwise, if r i t+1 = t < t > t . θ , Lemma 1. The proposed incentive mechanism is computationally ef- ficient. Proof. Let the number of the workers be at most n . So in ITA, the while-loop is of O ( n ) time complexity at most. In GTRU, the time complexity is also O ( n ). Thus, the time complexity of the proposed incentive mechanism is O ( n ), i.e. , the proposed incentive mecha- nism can be computed in polynomial time. Lemma 2. The proposed incentive mechanism is individually rational. × B ≥ 1 in Eq. (2) , and cost = Proof. If worker i is a winner, he will receive payment p i paid by the platform. We have set t i T B T
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料