Privacy-Aware Service Subscription in People-Centric Sensing:A Combinatorial Auction Approach

Yuanyuan Xu,Shan Li and Yixuan Zhang

Abstract:With the emergence of ambient sensing technologies which combine mobile crowdsensing and Internet of Things,large amount of people-centric data can be obtained and utilized to build people-centric services.Note that the service quality is highly related to the privacy level of the data.In this paper,we investigate the problem of privacy-aware service subscription in people-centric sensing.An efficient resource allocation framework using a combinatorial auction(CA)model is provided.Specifically,the resource allocation problem that maximizes the social welfare in view of varying requirements of multiple users is formulated,and it is solved by a proposed computationally tractable solution algorithm.Furthermore,the prices of allocated resources that winners need to pay are figured out by a designed scheme.Numerical results demonstrate the effectiveness of the proposed scheme.

Keywords:Privacy-aware service subscription,combinatorial auction,winner determination.

1 Introduction

In recent years,various sensing technologies emerge covering mobile crowdsensing and Internet of things,which have been widely used for health care[Islam,Kwak,Kabir et al.(2015)],banking,cyber security,commerce,and transportation[Pham,Tsai,Nguyen et al.(2015)].These technologies enable sensing data sharing,and accordingly,large amount of people-centric sensing data can be collected.The collected data can be analyzed(e.g.,through machine learning algorithms)to build people-centric services for customers.However,the collection and analysis of raw data may pose a threat to people's privacy which is closely related to the provided service quality.For example,higher service quality can be achieved by disclosing more data of individuals[Zhang,Shi,Zhang et al.(2013)].The relation between the privacy level and the service quality is analyzed in Alsheikh et al.[Alsheikh,Niyato,Leong et al.(2017)].

In this paper,we investigate the problem of privacy-aware service subscription in peoplecentric sensing.That is,how to efficiently allocate the privacy-aware services to accommodate various demands of the crowdsensing users,while achieving high resource utilization and the capability of resource customization.Therefore,an efficient resource allocation mechanism needs to be designed to achieve these goals.

Also,it is worth noting that there are a variety of people-centric services,which are complementarities or substitutions for each other.Complementary services are associated services or concurrently required to satisfy the customers' needs,while substituted services are similar or comparable services that can be replaced with each other.Due to the complementarities or substitutions among various services,customers are not just interested in subscribing a particular type of service but sets of services(sometimes termed as bundles)[De Vries and Vohra(2003)].Accordingly,we use a combinatorial auction approach to perform service allocation.Auction-based mechanisms have been widely applied for resource allocation in different areas,e.g.,radio resource allocation[Wang,Xu,Song et al.(2015)],cloud resource allocation[Zaman and Grosu(2013);Zhang,Xie,Zhang et al.(2018);Zhang,Jiang,Li et al.(2016);Samimi,Teimouri and Mukhtar(2016)],and wireless virtualization[Cao,Lang,Li et al.(2015);Zhu and Hossain(2016);Zhu,Cheng,Chen et al.(2017)].

Specifically,for applying combinatorial auction for privacy-aware people-centric service allocation,the following issues need to be addressed,which are the design of combinatorial auction model,the formulation of the winner determination problem(WDP),its solution algorithm,and the design of an incentive compatible pricing scheme.The main contributions of this work that address these issues are listed as follows:

· A combinatorial auction model is designed for the service subscription problem,where one-sided auction is performed among one service provider and multiple users.

· A computationally efficient algorithm is proposed to determine the winners in the combinatorial auction.

· The prices of allocated services are figured out by a designed scheme.

The organization for the rest of this paper is as follows.System model and combinatorial auction model are presented in Section 2.In Section 3,the service allocation for peoplecentric services is investigated.The allocation problem is formulated and the corresponding solution algorithm and pricing scheme are presented.Numerical results are analyzed in Section 4.Section 5 concludes the paper.

2 System model and assumptions

The system model of people-centric service allocation is shown in Fig.1.Crowdsensing users sense and collect data through multiple devices,such as mobile devices,Internet of things gadgets and other devices.The raw data are sent to service provider.The service provider should pay the cost of the raw data to crowdsensing users and apply data analytics to build people-centric services.Then the service provider sends the advertisement of the peoplecentric services to customers,and customers bid for their required bundles of services.Finally,the service provider decides winner lists and final prices that customers should pay.The major entities involved in the people-centric services can be described as follow:

· Crowdsensing participants are the providers of raw sensing data.

· The service provider buys raw data from the crowdsensing users,which are used to build the people-centric services.

· Customers are the consumers of people-centric services,who buy services from the service provider.

Figure 1:System model of people-centric service allocation

Specifically,we consider one service provider providing a set of K services to N users,where K represents the number of service types which are classified by the functions of services,and each type of service owns Q service levels which are sorted by the corresponding privacy levels.

Moreover,we show the tradeoff between the service quality and the privacy level.The privacy level and the service quality are closely related.The higher the privacy level,the less true data the service provider can buy from crowdsensing participants,so the service provider will have a lower quality of service,and vice versa.A utility function u(·)can be used to measure the quality of service,given a privacy levelr,where r∈[0,1].There are three assumptions about the service quality.The first is that u(·)is nonnegative,because the service quality can only be zero or positive.Secondly,u(·)is inversely proportional to r.This is an empirical assumption,since the quality of data analytics degrades as the privacy level increases.The third assumption is that u(·)is convex and decreases at an increasing rate over r.According to these three assumptions,Dwork[Dwork(2008)]concluded that the relationship between the utility function of data u(·)and the privacy level r in people-centric services can be obtained as follows:

where α1,α2,and α3are the curve fitting parameters that can be obtained empirically.From(1),Dwork[Dwork(2008)]concluded that the quality of service is inversely proportional to the privacy level.The best fitting parameters,α1,α2,and α3,can be obtained by solving[Dwork(2008)]

whereBis the number of measurements in the experiment,while r(i)and τ(i)are the privacy level and the measured real-world service quality during the it?measurement,respectively.

2.1 The proposed combinatorial auction model

In the proposed combinatorial auction model,the service provider acts as the seller that maximizes her own prof it and tries to meet services requirements of customers who act as buyers.Also,the service provider acts as the auctioneer who collects bids,decides allocation lists,and figures out final prices.In general,an auction can be describe as follows:

· Bidding:According to his own valuation viof the services bundle,a bidder i places a bid bi.The valuation is the evaluation of the services bundle which the bidder i wants to bid,and this personal information can be private or public.Valuations for the same bundle may be varying with different bidders.

· Allocation:After bid collection from all the bidders,the auctioneer has to decide the service allocation among the bidders.A bidder who will be given his required service is a winner.

· Pricing:After winner determination or service allocation,the auctioneer has to figure out the price piwhich is the charge for each winner i.

In this paper,the proposed combinatorial auction is a single-seller multiple-buyer auction model,and the seller also acts as the auctioneer.In this model,the buyers place bids for their required services bundles,and bidders can only obtain resources from a single seller.We define bias the users' bids.Assume that the service provider hasKdifferent types of services,denoted as S1,S2,··,SK.Each service SihasQlevels of services,denoted as SSi1,SSi2,··,SSiQ,which are classified by the privacy levels of people-centric data.In addition,the service provider has a type of service,S0,which is the network bandwidth.We assume that S0also hasQlevels of varying network bandwidth that users can choose to support their required services.Each type of service Sihas two basic attributes which are computing capability Ciand running memory size Mi.Privacy level,computing capacity and memory size are all important factors related to the service quality.For example,the automated detection of cancer cells is a people-centric service that is used in the field of medical diagnosis.The characteristics and regularities of cancer cells are obtained by deep learning.The lower the privacy level,the more accurate the results of the data analysis.As we all know,data analysis(e.g.,through deep learning)requires high computing capacity and large memory size.In this case,users should choose suitable services to satisfy their needs.Bidders must convey their requirements and valuations clearly,and how to express the bids will be detailed in Section 3.1.

2.2 Utility functions and social welfare

1)Utility functions:In our combinatorial auction model,each bidder is assumed to be selfinterested who chooses a bidding strategy carefully to maximize his own utility with the knowledge of auction mechanism(i.e.,service allocation and pricing schemes).Specially,the utility of bidderiis defined as follows:

where uiis the utility of bidderi.The set U={u1,u2,··,ui}can be used to represent the utilities of all the bidders.

2)Social welfare:To perform auction on a service bundle,a single-item auction can be performed repeatedly for each included item.However,due to possible substituted or complementary services,the value of the bundle may be different from the sum of individual services' values.Therefore,a combinatorial auction is a better choice that allows the bidders to bid for combinations or bundles of people-centric services.If a bidderiwins,he can receive the required service bundle that has a value vi.In a combinatorial auction,multiple winning bidders exist.The social welfare can be expressed as the sum of valuations of all the winners.Specifically,it could be represented as:

whereVrepresents the social welfare.In our scheme,social efficiency can be achieved in combinatorial auction if all bidders place truthful bids.

3 Services allocation as a combinatorial auction

In this section,the above combinatorial auction model is used to perform service allocation.The bidding expressions of bidders,the WDP problem with its solution,and an incentive compatible pricing scheme are presented.

3.1 Bidding expressions

We consider the case that users convey their service demands in an explicit way in auctions for services allocation.Each user is assumed to be single-minded who submits a bid for only one bundle in each round.A useridemands particular services and needs related hardware support.In this case,the bid Biof userican be represented as:

where viis the useri's valuation to his required bundle.is a vector that represents the useri's demand on the jt?type of service,which can be further expressed as follows:

3.2 Problem formulation

We consider the case that the service provider is self-interested who wishes to maximize her prof it,with the following assumptions.

3.2.1 Assumption

In real world,each type of service has no preference over users and it can be allocated to every user.

However,these services are limited by the service provider's computing capacity and memory size.In the case of S0,it is limited by the provider's network bandwidth.

3.2.2 Assumption

Privacy level of each service is transparent.

With these assumptions,the WDP for services allocation can be formulated as:

where xiis a binary variable to represent whether useriis a winner.Mis the total memory of the service provider such as the cloud computing platforms.InC2,Crepresents the computing capacity of the service provider.In addition,Wis the maximum network bandwidth which the service provider can provide.The first constraint in the formulation(7)ensures that if the following users' requirements for services are beyond the total memory,they will be never allocated,unless in next auction round,because the auctions could run periodically.The second constraint ensures that the sum of the required computing capacity cannot exceed the total of computing capacityCof the service provider.The third and fourth constraints mean that the users' requirements of each type of services cannot be more than the maximum allocated memory and computing capacity for that service.The constraintC5ensures that all the network bandwidth required by all the users cannot exceedW.The constraintC6guarantees that a usericould only choose one service level SSjtfor each type of services Sj.The last two constraints represent whether the service or the bundle is allocated,where1represents that it is allocated and0vice versa.

3.3 Solution of WDP

The formulated problem is an NP-hard integer programming problem.With a sufficiently small problem scale or restricted allowable bid combinations,the optimal solution can be found by exhaustive search.However,considering the problem scale and the limited computation capability of the auctioneer in our case,a computationally efficient algorithm is needed to find approximate optimal solutions.Motivated by Sandholm[Sandholm(2000)],a greedy solution algorithm is proposed considering the “density” of bids.This greedy solution is shown in Algorithm 1:

A buyeri's bid density can be defined as.The greedy algorithm first queues the users according to their bid density,and then allocates their required bundles starting from the user with the largest bid density until the resources are exhausted.In this way,the winners are determined in a greedy way.

3.4 The VCG pricing scheme

Having the winners,we need to determine the final prices.A proper pricing scheme should be incentive compatible with which that all bidders can bid truthfully.The VCG scheme[Gao,Li,Pan et al.(2016)]generalizes a second-price auction model for multiple items,and achieves the incentive compatibility.However,the maximization of the seller's revenue is not considered in the VCG scheme.The resulting revenue is far from the optimal one in some cases.

To address this issue,we design a modified-VCG pricing scheme,where each resource has a minimum base price.If a userkis the one with the highest valuation when the winneriis not participated in the auction,the charged price for the useriis calculated as follows:

4 Performance evaluation

For numerical analysis,we consider users requesting 10 kinds of people-centric services from a service provider,and each type of service is divided into 10 service levels.The number of users varies from 100 to 350.For performance evaluations,we assume that the service provider is equipped with 1000GB memory,10000 MIPS computing capacity,and 1000Mbyte network bandwidth.The memory size and computing capacity for each type of service are randomly selected from[10,100]and[0,10],respectively,according to a uniform distribution.Similarly,the privacy level of each people-centric service is randomly set to a value from 0 to 1.The parameters,α1,α2,and α3,related to the function of service quality in Eq.(1)are set to 0.822,0.004,and 2.813,respectively.

For numerical analysis,three aspects of the performance for resource allocation are considered:total utility,resource utilization(i.e.,the proportion of allocated services),and user satisfaction(i.e.,the percentage of users who get the requested services).Also,four algorithms are compared,which are the proposed scheme(termed as “APProx”),the proposed scheme with group buying discounts(termed as “Approx-GB”)which gives a discount price if the number of users is larger than a threshold,a fixed allocation scheme(termed as “Fixed”)which allocates resources based on an existing contract,and a random allocation scheme(termed as “Rand”)that allocates resources randomly.

Fig.2 presents comparison of total utilities of these schemes.It can be seen that the proposed scheme and its group-buying-discounts version can achieve higher utilities than other algorithms.The “Fixed” scheme charges the winners with a market price.However,the priority and competitiveness of users are not considered in the fixed resource allocation resulting a lower utility value.The performance of the random allocation is not as good as the proposed ones due to the same reason.Comparison of average resource utilization of the four schemes is shown in Fig.3.The trends in the results are similar to those for the total utility.

Figure 2:Total utility with varying number of users

Figure 3:Resource utilization with varying number of users

Comparison of user satisfaction for explicit resource requests is presented in Fig.4.It can be seen that the user satisfaction ratios of all the four schemes decrease as the number of users increases.Among them,the proposed scheme can achieve higher satisfactions ratios than other three schemes.The reason is that the proposed scheme can choose the best combination from different resource combinations to accommodate the individual users'varying needs.

Figure 4:User satisfaction with varying number of users

5 Conclusion

In this paper,a combinatorial auction model has been used for efficient resource allocation to maximize social welfare in people-centric sensing.Specifically,a single-seller multiplebuyer auction model has been used,and a winner determination problem(WDP)has been formulated in view of different people-centric service requirements and priorities of users.To solve the formulated problem,a greedy algorithm has been proposed to determine the winners in this one-side auction.An incentive compatible pricing scheme has been designed considering the seller's revenue.Finally,simulations have been conducted to show the effectiveness of the proposed scheme.

Acknowledgement:This work was partially supported by National Natural Science Foundation of China under Grant No.61801167 and Natural Science Foundation of Jiangsu Province of China under Grant No.BK20160874.