A behavior-based incentive mechanism for crowd sensing with budget constraints

ABehavior-BasedIncentiveMechanismforCrowd

SensingwithBudgetConstraints

JiajunSunandHuadongMa

BeijingUniversityofPostsandTelecommunications,Beijing100876,China

Email:jiajunsun.bupt@gmail.com,mhd@bupt.edu.cn

Abstract—Crowdsensingisanewparadigmwhichleveragestheubiquityofsensor-equippedmobiledevicestocollectdata.Toachievegoodqualityforcrowdsensing,incentivemechanismsareindispensabletoattractmoreparticipants.Mostofexistingmech-anismsfocusontheexpectedutilitypriortosensing,ignoringtheriskoflowqualitysolutionandprivacyleakage.TraditionalincentivemechanismssuchastheVickrey-Clarke-Groves(VCG)mechanismanditsvariantsarenotapplicablehere.Inthispaper,toaddressthesechallenges,weproposeabehaviorbasedincentivemechanismforcrowdsensingapplicationswithbudgetconstraintsbyapplyingsequentialall-payauctionsinmobilesocialnetworks(MSNs),notonlytoconsidertheeffectsofextensiveuserparticipation,butalsotomaximizehighqualityofsensingdatasubmissionfortheplatform(crowdsensingorganizer)underthebudgetconstraints,whereusersarriveinasequentialorder.Throughanextensivesimulation,resultsindicatethatincentivemechanismsinourproposedframeworkoutperformexistingsolutions.

I.INTRODUCTION

Withtheincreasingubiquityofsensor-embeddedmobiledevices(e.g.,smartphones),mobilesocialnetworks(MSNs),whichintegratedatacollectiontechniquesandservicesintomanykindsofsocialnetworks[1]–[3],havereceivedcon-siderableresearcheffortsinrecentyearsduetotwochangesasfollows.First,theterminaldevicesforsocialnetworkapplicationschangefromPCstomobilephones.Second,theinteractivemodeextendsfromthevirtualspacetotherealphysicalworld.MSNsprovideanewopportunityforcrowdsensing,whichtakesadvantageofthepervasivemobiledevicestosolvecomplexsensingtasks.Atypicalexampleofcrowdsensingapplicationsistoprovidethesupportforgreentrafficbysensingandreportingtimelythemeasurementsabouttrafficflowsinsomeregion.Differentfromexistingcrowdsourcingsystems,crowdsensingexploitssensingandprocessingabilitiesofmobiledevicestoprovidesensingdatafromtherealphysicalworldtowardsaspecificgoaloraspartofasocialortechnicalexperiment[4]–[6].

ExtensiveuserparticipationandsubmissionqualityaretwocrucialfactorsdeterminingwhethercrowdsensingapplicationsinMSNscanachievegoodservicequality.Mostofthecurrentcrowdsensingapplicationsarebasedonacommonhypothesisthatallusersvoluntarilyparticipateinsubmittingthesensingdata.However,mobiledevicesarecontrolledbyrationalusers,inordertoconserveenergy,storageandcomputingresources,soselfishuserscouldbereluctanttoparticipateinsensingdataforcrowdsensingapplications.Thus,itisindispensable

toprovidesomeincentiveschemestostimulateselfishpartici-pantstocooperateinMSNs.Onlyahandfulofworks[7]–[10]focusonincentivemechanismforcrowdsensingapplications.Alloftheseworksapplyaregularauction(e.g.,areverseauction)onlyforoff-linecrowdsensingapplicationswiththeex-antepaymentcommonlyknownas“Freeriderproblem”.Thedatasubmissionqualityissuefromparticipantsisalsochallengingincrowdsensingapplications[11].Ifthesubmis-sionqualityofparticipantsisnotwellguaranteed,althoughtheextensiveuserparticipationoffersusefulinformation,theservicequalityfromparticipantsisfarfromsatisfactorytotherequestersofcrowdsensingapplications.Forexample,ontheonehand,thelimitofthecoverageconstraintmaymaketheparticipantswithhighqualitydatadropoutofcrowdsensingapplication[10];Ontheotherhand,traditionalincentivemech-anismssuchastheVickrey-Clarke-Groves(VCG)mechanismanditsvariantsalsowillmaketheparticipantswithhighertruevaluationbecomestarvedfrequentlytowin,therebydropoutofcrowdsensingapplications[12].Therefore,specialmechanismsmustbeincludedtohandlethesechallenges.Althoughbothextensiveuserparticipationandsubmissionqualityissueshavebeenidentifiedastwocrucialhumanfactorsforcrowdsensingapplications,manyrecentresearchworks[7]–[14]tendtoseparatelystudythemincrowdsensingapplications.Thereasonisthat,iftheextensiveuserpartici-pationandsubmissionqualityproblemsareaddressedatthesametimeforcrowdsensingapplications,theissuewouldbecomemorechallenging.Forexample,somesubmissionqualityenhancedtechniques[13],[14]stimulateparticipantstogeneratehighqualitysensingcontentstoachievegoodservicequality,buttheycouldmakesomeincentivestrategies,especiallythereputation-basedincentivestrategiesunderbud-getconstraints,hardtoimplementextensiveuserparticipationcoverageconstraintsforcrowdsensingapplications,sinceitisnotpracticaltoassumethattherequesterwillalwaysprovideanunlimitedbudgettoachievegoodservicequality.Therefore,howtosimultaneouslyaddressbothextensiveuserparticipationandsubmissionqualityissuesbecomesparticu-larlychallengingforcrowdsensingapplicationswithbudgetconstraints.

Inthispaper,toaddressthefore-mentionedchallenges,weproposeabehaviorbasedincentivemechanismforpracticalcrowdsensingapplicationswithbudgetconstraints.Specif-icallyspeaking,ourmaincontributionsaresummarizedasfollows:

978-1-4799-2003-7/14/$31.00 ©2014 IEEE

1314

IEEE ICC 2014 - Communication QoS, Reliability and Modeling Symposium

WeexploreabehaviorbasedincentivemechanismforcrowdsensingapplicationswithbudgetconstraintsinMSNs.Inordertosimultaneouslysatisfytherequire-mentsofbothextensiveuserparticipationandhighqualitysensingdatasubmission,wecombinetheall-payauctiontheoryandaproportionalshareallocationruletostimulatetheparticipantstogeneratehigheffortsandadequatecoverageconstraintstoachievethebetterservicefortherequesterofcrowdsensingapplicationswithbudgetconstraints.

•Wefocusonamorerealcrowdsensingscenariowhereparticipantsarriveonebyoneonlineinarandomorder.Wemodeltheissueasanonlinesequentialall-payauctioninwhichsensingdataaresubmittedsequentiallyandtheuserswiththehighqualitysensingdataareselectedasthewinners.Further,afterobservingprevioussubmissions,wederiveeveryuserbestresponseeffortbiddingfunctionforsequentialcrowdsensingapplicationswithbudgetconstraints,whichinfluencesuserparticipationandsens-ingdatasubmissionquality.

•Extensivesimulationsshowthatourproposedincentivemechanismoutperformstheexistingsolution.

Therestofthepaperisorganizedasfollows.InSectionII,webrieflydiscusstherelatedworkandmotivation.InSectionIII,wepresentoursystemmodel,relateddefinitionsandourdesigngoals.InSectionIV,wedesignabehaviorbasedincentivestrategyforsequentialcrowdsensinginMSNs,andpresenttheperformanceevaluationinV.Finally,SectionVIconcludesthepaper.

•

5HTXHVWHUV$SSOLFDWLRQ3ODWIRUP6HUYLFH3D\\PHQWV6HQVLQJ󰀃5HSRUWV7DVN󰀃'LVWULEXWLRQ󰀃3DUWLFLSDQWV$UHD󰀃RI󰀃,QWHUHVWFig.1.Ourcrowdsensingsystemframeworkwithall-payauctions.

II.BACKGROUNDANDRELATEDWORK

ExtensiveuserparticipationandsubmissionqualityissuesaretwocrucialhumanfactorsforcrowdsensingapplicationsinMSNs.Theauthorsof[15]proposedrecruitmentframeworkstoenabletheplatformtoidentifywell-suitedparticipantsforsensingdatacollections.However,theyonlyconsideredtheusers’selection,ratherthantheincentivemechanismdesign.Inrecentyears,mostofreportedstudieshavefocusedonhowtostimulateselfishparticipantstoenhanceuserparticipationlevels.Forinstance,theauthorsof[9],[10],[12],[16]exploredtheextensiveuserparticipationtoachieveagoodsensingserviceforcrowdsensingapplications.Obviously,itisnotpracticaltoassumethattherequesterintheirmechanismswillalwayshaveanunlimitedbudget.Theauthorsof[7],[17]–[19]designedanincentivemechanismtoenhanceuserparticipationlevelsunderabudgetconstraint.Althoughtheydesignedtruthfulmechanisms,whichoptimizedtheutilityfunctionoftheplatformunderafixedbudgetconstraint,toincentiveextensiveuserparticipation,theeffectsoftheonlinesequentialmanner,inwhichusersarrive,wereneglected.Inpractice,recently,thereareafewworksfocusingonbothbudgetconstraintsandtheonlinesequentialmannerofusers’arrivaltoenhanceuserparticipatinglevels.Forinstance,theauthorsof[20],[21]exploitedpostedpricemechanismsforstimulatingtheonlinearrivaluserparticipation.Theauthorsof[22]leveragedthresholdpricemechanismformaximizingthe

numberoftasksunderbudgetconstraintsandtaskcompletiondeadlines.However,theydidnotconsiderthesubmissionqualityissueofsensingdata.

Comparedwiththeextensiveuserparticipationissue,thereareonlyahandfulofresearchworks[13],[14]focusingonthesubmissionqualityissueforcrowdsensingapplicationsinMSNs.Theseworksstimulateparticipantstosubmithighqualitysensingdatatoachievegoodservicequality,butdonotsupporttheextensiveuserparticipationissue.Inourmecha-nisms,inordertosimultaneouslysatisfytherequirementsofbothextensiveuserparticipationandhighqualitysensingdatasubmission,wecombinetheall-payauctionmechanismandaproportionalshareallocationruletoachievethebetterserviceforcrowdsensingapplicationswithbudgetconstraints.Fur-thermore,weaccountfortheonlinearrivalofusersandmodeltheissueasanonlinesequentialall-payauction.Simulationsindicatethatourproposedincentivemechanismsoutperformexistingsolutions.

III.SYSTEMMODELANDPROBLEMFORMULATION

A.SystemModel

WeconsiderthefollowingcrowdsensingsystemmodelillustratedinFig.1.Thesystemconsistsofacrowdsensingapplicationplatform,towhicharequesterwithabudgetB>0postsacrowdsensingapplicationthatresidesinthecloudandconsistsofmultiplesensingservers,andmanymobiledeviceusers,whichareconnectedtothecloudbycellularnetworks(e.g.,GSM/3G/4G)orWiFiconnections.ThecrowdsensingapplicationfirstpublicizesasequentialsensingtaskinanAreaofInterest(AoI).AssumethatasetofusersU={u1,u2,···,un}areinterestedinthecrowdsensingtask.Moreformally,wemodeltheinteractiveprocessbetweentheplatformandusersasanonlineall-payauctionandareinterestedinonlinesettings,wheretheplethoraofuserswithdifferentpreferenceandskillabilityθ∈[θ,θ](θandθdenotetheleastskilledbehaviorabilityandthemostskilledbehaviorabilityrespectively)arriveandcompeteinacontestbytheireffortsinoneperiod.UserbehaviorabilitiesaredescribedbythedistributionfunctionΦ.Eachcompetingusercansubmit

1315

IEEE ICC 2014 - Communication QoS, Reliability and Modeling Symposium

onesolutionatmost.Theuserdeterminestheefforteofthesubmittedsolutionaccordingtoitspreferenceandskillability.TheplatformdeterminesthepaymentM1,M2,···,Mntothetopn(highest-ranked)submissionsinoneperiod(M1≥M󰀁2≥···≥ML=m>ML+1=···=Mn=

n

0,l=1Ml=B):theuserwiththebestsubmissionreceivesM1,thefirstrunner-upreceivesM2,andsoforth.Eachusersubmitshiseffortstotheplatform.Theplatformdeterminesthenumberofprizesandthesizeofprizestomaximizethetotaleffortsfromtheselectedusers.B.ProblemFormulation

Ourobjectiveistodesignmechanismsbasedonusers’behaviorabilitiestosimultaneouslysatisfytherequirementsofbothextensiveuserparticipationandhighqualitysensingdatasubmission.Considerarisk-neutralbudgetconstrainedall-payauctionswhoseutilityfunctionisU(e1,···,eL,B)=󰀁

j∈Aej−B,wheretheefforteifromusericanbecomputedaccordingtothemethodin[23].ThegoaloftheplatformistoselectasubsetAwiththesizeLthatmaximizesthetotaleffortsoftheusers.Autility-maximizingplatformshouldselectthenumberofprizesL,thetotalprizebudgetBandtheallocationofprizesM1+M2+···+ML=Bwhichmaximizestheplatform’sutilityU(e1,···,eL,B).Moregenerally,givenabudgetBandareservedeffortm,findingasubsetAtomaximizethecoverageissueofsensingdata,isequivalenttomaximizingthecoverageissueofutilities.

IV.OPTIMALMECHANISMDESIGNFORTHESENSING

CONTESTA.ThresholdEffortDecision

Inthissubsection,wefirstintroduceathresholdefforttoensuretheextensiveparticipation.Thenweapplyall-payauctiontoenhanceusers’submissionquality.Wenowturntothefollowingdefinitionofnondecreasingsubmodularfunctionsusedinourpricingmechanisms.

Definition1(SubmodularFunction):LetNbeafiniteset,afunctionU:2Ω→RissubmodularifU(S∪{i})−U(S)≥U(T∪{i})−U(T),∀S⊆T⊆Ω,whereRisthesetofreals.

Inageneralsubmodularmaximizationproblem,thegreedyapproachisanaturalfitduetoitsmonotonicitywhenusersaresortedaccordingtotheireffortsrelativetoincreasingmarginalcontributions.Thestandardgreedyapproachtoachievedesir-ableperformanceoftheonlinearrivalisviasampling:thefirstbatchofthecontestisrejectedandusedasasampletomakeaninformeddecisionontherestofthecontest.However,sinceusersknowingthefactthatthemechanismwillautomaticallyrejecttheirbidarereluctanttoworkontasks,therebydropoutofthecontest.

Tohandlethischallenge,weapplythefollowingmethod.Ateachstagetheproposedmechanismmaintainsaneffortthresholdwhichisusedtodecidewhethertoaccepttheusers’efforts.Theproposedmechanismdynamicallyincreasesthesamplesizeandupdatestheeffortthreshold,whileincreasingthebudgetitusesforallocation.Thereby,usersarenot

automaticallyrejectedduringthesampling.Attheendofeverytimestep,ourmechanismcalculatesaneffortthresholdforusersarrivingduringthenexttimestep.Sinceeachstagemaintainsacommoneffortthreshold,itisanaturaltointroduceaproportionalshareallocationruletoestimatethe

󰀂

effortthresholdfromeverysamplesetXandtheallocated

󰀂

stage-budgetB.Theeffortthreshold’calculationisillustratedinAlgorithm1.However,toenhancethesensingdataquality(users’efforts),weapplytheoptimalwinningparticipantnumberLandtheoptimalprizeamountsMi(i∈{1,···,L})tocalculatetheeffortthresholdofthenexttimestep.TheoptimalwinningparticipantnumberLandtheoptimalprizeamountsMi(i∈{1,···,L})canbecalculatedaccordingtothemethodin[24].Then,thesesampledusersaresortedaccordingtoincreasingmarginalcontributionsrelativetotheirprizeamounts.Thissortingimplies:

U1/M1≥U2/M2≥···≥UL/ML,

whereUidenotesUi|X󰀂i−1(=U(Xi−1∪{i})−U(Xi−1)),󰀂󰀂

Xi={1,2,···,i},andX0=∅.ThespecificaliterationprocessisillustratedinAlgorithm1toguaranteetheextensiveuserparticipation.

Algorithm1GetEffortThreshold

Input:SamplesetX,stagebudgetconstraintBOutput:Effortthresholde.

1:Computetheoptimalwinners’numberandtheoptimalprizeamountsMi(i∈{1,···,L});

2:Sorttheirmarginalutilityrelativetotheirprizeamounts,s.t.U1/M1≥U2/M2≥···≥UL/ML;setk=1;

󰀂󰀂

3:ThewinnersetA←∅;i←argmaxj∈X󰀂(Uj(A)/Mj);

󰀂󰀂

4:whilek≤LandMi≤UiB/U(A∪i)do

󰀂󰀂

5:A←A∪i;

󰀂

6:i←argmaxj∈X󰀂(Uj(A)/Mj);7:k←k+1;8:endwhile

󰀂󰀂

9:e←B/U(A);10:returne;

B.ComputingSequentialEfforts

Inthefollowingsubsection,duetospacelimitations,assum-ingthatthereservedvaluemiszero,i.e.,e0=0,wederivetheequilibriumeffortbiddingfunctionforsequentialall-payauctionarrivalusers.Forthepositivereservecase,e0>0,thesimilarresultscanalsobederived,whichwillbediscussedinourfuturework.

AssumethatPjisthecumulativedistributionfunctionofthej-thbesttypeoutofn−1users.Applyingbackwardinductioniterativelyforusern,n−1,···,i+1,wecanobtainthefollowingmaximizationproblemofthejustarrivaluseri:

max{V

ei

n󰀂j=i+1

󰀂

󰀂

󰀂

󰀂

Pj(ej=0)−

ei

θi}

s.t.ei≥eL−th(θL−th),

(1)

1316

IEEE ICC 2014 - Communication QoS, Reliability and Modeling Symposium

whereeL−th(θL−th)denotestheL-thlargesteffortbidsob-servedbyuseri.Besides,Visderivedasfollows:

󰀄󰀅n−1󰀃n−1

Φ(e)i(1−Φ(e))n−1−i.Pj(e)=

i

i=1

BÿB/2lB/2l-112qi=0qi0t=01t=12t=2B/2l-23(a)3t=4(b)ŵlogTŹ+1W 7Thus,theexpectedutilityVoftheuserofabilitytypeθ

L󰀁

biddingwithqualityeisV=Φj(e)(Ml−Ml+1).Therefore,inthefollowing,wederiveuseri’sbestresponseeffortbiddingfunctionbasedontheassumptionthatthebehav-iorabilitydistributionfunctionisΦ(x)=xc,where0←−

like[11],[25].Ifweletθi=[(1−dL−th)θL−th]di/dL−th,and−→

θi=[(1−d1−th)θ1−th]di/d1−th/c,givene1,e2,···,ei−1,useri’sbestresponseeffortbiddingfunctionisobtainedasfollows(thecompletecalculationprocessgivenintheAppendix):

Algorithm2TheBudgetedBehavior-basedincentivemecha-nismunderSequentialall-payauctions(BBS)

Input:BudgetconstraintB,sensingtaskdeadlinesT

󰀂

1:Initialize:quantiles{0,1,···,󰀒logT󰀓},BudgetB=2−(l+1)B,t=1,l=2󰀊logT󰀋;

2:foreveryquantilet=qj,j=l,l−1,···,1do

󰀂󰀂

3:Calculatee=GetEffortThreshold(X,2B);

󰀂󰀂

4:SetB=2B,thewinnersetA←∅;5:Withprobability1/3do:6:whileqjhisbehaviorabilitiesbyusing󰀁theexpression(2);󰀂

9:ifei≤e·Ui(A)≤B−j∈Aejthen10:ei=e,A=A∪{i};11:endif

󰀂󰀂

12:X=X∪{i};13:endfor14:endwhile15:Otherwisedo:16:forthefirstuseriarrivingbyqj+1do17:RunDynkin’salgorithmandofferBthewinner;18:endfor19:endfor

⎧⎪⎪⎪⎨⎪⎪⎪⎩

l=1

Fig.2.Illustrationofamulti-stagesampleprocesswithdeadlinesT.

󰀂

(a)BudgetBversusquantileqi;(b)Quantileqiversustimet.

Ourmechanism(seeAlgorithm2)iteratesoverqi∈{0,1,···,󰀒logT󰀓}andateverytimestepqiabudgetofB/2iisappliedtoallocatesensingtasks(illustratedinFig.2).Firstly,ourmechanismcomputesawinningsampleusersetbyapplyingtheall-payauctionsandthenobtainsathresholdpriceaccordingtoAlgorithm1.Inthesequel,aslongasthearrivalusereffortsfromhisbehaviorabilitiesareabovethethresholdeffortandthebudgethasnotbeenexhausted,thearrivinguserchoosestoperformdatasensing.Finally,ourmechanismallocatesitsentirebudgettotheuserthattheireffortsarebelowthethresholdefforts.Therandomizationaddressesextremecasesinwhichonlyasingleuserwiththestrongestbehaviorabilitiescancompletealargefractionofthecrowdsensingapplicationatthethresholdefforts.ThisistheresultthatanincentivecompatiblevariantofDynkin’scelebratedalgorithm[26]totheissueofhiringthebestsecretary,istailoredtooursetting.

V.PERFORMANCEEVALUATION

ToevaluatetheperformanceofourBBSmechanism,andexploretheeffectsofextensiveuserparticipationandhighqualitysensingdatasubmissionforrealcrowdsensingapplications,weimplementthemechanismbyapplyingthewell-knownManhattanmodelobtainedfromtheGoogleMap,whichisthesameas[27].A.ExperimentalSetup

Inthesimulation,thesensingrangeofeachmobilephoneissetto7meters.TheAoIobtainedfromtheGoogleMapislocatedatManhattan,NY,whichspansarangewithatotalwidthof0.41kmandarangefromwesttoeastwithatotallengthof1.27km.Datasensingareasizesaresetatrandom.Insummary,weused1887sensingdatapacketsfromdifferentlocationsvia200differentusers[27].Allmeasurementsareaveragedover30sensingtasks.Ourprimarygoalsaretoevaluatetheperformanceoftheonlinemechanismonrealeffortbidsaswellastotestusers’participatingresponsetodifferentmechanisms.

B.ThresholdEvolutionofDifferentMechanisms

TotesttheperformanceofourBBSmechanism,weusetheusers’effortbidsfromall-payauctionsandcompareourmechanismagainstseveralbenchmarks.Notethatinordertoshowhowmanyuserscanbeacceptedtoparticipateinthecrowdsensinggivenaspecifiedbudget,weonlyneedtocomputingthevaluesofusers’bestresponseeffortbiddingfunction,whichispracticallyobtainedaccordingtotheusers’arrivalsequence.WecompareourBBSmechanismagainsttwobenchmarks.Onehasfullknowledgeaboutusers’costs,and

0

{ej−th(θj−th)}j∈{1,2,···,L}V[θi(1−di)]1/di

ei=

←−

0≤θi<θi

−→←−

θi≤θi<θi−→

θi≤θi≤1

(2)

C.DesigningIncentiveMechanism

Givenadistributiononthearrivalofusers,wecaneasilycalculateeverytimestepts.t.theprobabilitythatauserarrivesbeforetis1/2i.AllofTtimestepsaredividedinto

󰀂

2iquantiles:{0,1,···,󰀒logT󰀓}.WeapplyXtodenotethesetofallwinningbidsuntilthetimestept.

1317

IEEE ICC 2014 - Communication QoS, Reliability and Modeling Symposium

10Proportional share allocationBBS2001801605000450040008Threshold efforts eTotal utility value140350030002500200015001000500Mean differenceBest possibleBest Incentive CompatibleWinner−Take−AllMultiple WinnersBBS65432100Proportional share allocationBBSParticipants612010080604Best possibleBest Incentive CompatibleWinner−Take−AllMultiple WinnersBBS2402000123Sample stage t45671000200400600Budget80010001200140000200400600800Budget1000120014001600180020005101520Effort bid253035404550(a)(b)(c)(d)

Fig.3.(a)Thethresholdeffortseversussamplestaget;(b)Effectsofuserparticipation;(c)Effectsofsubmissionquality;(d)Thedifferenceofsubmissionquality.

theotheristheGetEffortThresholdprocedureappliedoffline.Wesimulatethesealgorithmsondifferentbudgetstoexaminethechangeinthethresholdeffortsasthenumberofusersincreasesinthesample.Inallsimulations,weobservethatthethresholdeffortsconvergedquickly.Fig.3(a)showsthatthevalueofthethresholdeffortschangeswiththestageofthemechanism(thenumberofusersthatsubmittedtheireffortbids)onthelogarithmicscale.Aswecansee,thethresholdeffortsquicklystabilizeandremainalmostconstantthroughouttherunning.

C.EffectsofUserParticipation

Toexaminewhetherusersperformstrategicconsiderationsintheirprizingmechanisms,wecanobservethedistinctdifferencebetweentheplotsofthedifferenttotalefforts(bids)inFig.3(b)basedondifferentmechanisms.MostofusersintheWinner-Take-Allscheme,whereasinglewinnergetsallprizes,dropoutofthecontest,sincetheprobabilityofwinningthecrowdsensingcontestdecreasedwithnumberofparticipants.UsersintheMultiple-Winnersscheme,wheremultiplewinnersgetthesameprizes,exertlowereffortwhentherearelargernumberofparticipants.Inthereverseauction,biddersacceptedinthebestpossibleschemeincreasetheirbids.(Thefollowingdropsoffsinceweenforcethebudgetconstraint).Inthebestincentivecompatibleschemes,bidsarelowered,sinceusersbidsarerejected.Webelievethatthisisastrongsupportforpersistinginincentivecompatiblemechanisms,sincetheythinkthatthiswillincreasetheirprofit.Interestingly,ourBBSschemesolvesbothincentivecompatibilityandindividualrationalityproblems.D.EffectsofSubmissionQuality

Toexaminethequalityofsubmissionsensingdataquality,weplotthetotalutilityvalueasafunctionofdifferentbudgetsinFig.3(c).IntheWinner-Take-Allscheme,mostofusersdropoutofthecontest,sincetheprobabilityofwinningthecrowdsensingcontestdecreaseswiththenumberofparticipantsincreasing.Thus,thetotalutilityvaluewoulddecreasedfromitsmaximum.UsersintheMultiple-Winnersscheme,wheremultiplewinnersgetthesameprizes,exertlowereffortandobtainmoretotalutilityvalueswhentherearelargernumbersofparticipantsasmorebudgetsareprovided.Inthereverseauction,biddersacceptedinthebestpossibleschemeincreasedtheirbids.Inthefollowing,theydropoff

sinceweenforcedthebudgetconstraint.Inthebestincentivecompatibleschemes,bidsarelowered,sinceusersbidsarerejected.Webelievethatthisisastrongsupportforpersistinginincentivecompatiblemechanisms,sincetheythinkthatthiswillincreasetheirtotalutilities.Interestingly,ourBBSschemesolvesbothIRandICproblems,therefore,itensuresextensiveuserparticipationandhighqualitysensingdatasubmission,justasillustratedinFig.3(b)andFig.3(c).

Furthermore,wealsoquantifysubmissionqualitybycon-sideringusers’meandifferencesfromtrueon-sitedataovertheireffortbids.Fig.3(d)indicatesthatourBBSmechanismhasalowermeanerrorsthantheproportionalshareallocationrule.

VI.CONCLUSIONSANDFUTUREWORK

Inthispaper,wepresentabehaviorbasedincentivestrategytomotivateuserstoexertthemostsensingeffortaccordingtotheirbehaviorabilitiesandwillingnessforpracticalcrowdsensingapplications.Weassesstheparticipants’effortsac-cordingtotheircontextsituation(e.g.,sensinglocationandsensingtime).Webelievethatsequentialall-payauctionsinourproposedframeworkprovideagoodbasisforrealcrowdsensingapplications.FutureresearchcouldexpandonourBBSmechanismbystudyingtheeffectsofprivacyprotectiononparticipationlevelandsubmissionquality.Anaturalextensionofthisschememaybedesirabletohavesubmissionsprivacyprotectedandtohideuserexperienceleveloridentity.

ACKNOWLEDGMENT

ThisworkissupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.61332005,No.61272517,No.61133015,theFundsforCreativeResearchGroupsofChinaunderGrantNo.61121001,theSpecializedResearchFundfortheDoctoralProgramofHigherEducationunderGrantNo.20120005130002,andtheKeyTechnologiesR&DProgramofChinaunderGrantNo.2011BAC12B03.

REFERENCES

[1]C.C.AggarwalandT.Abdelzaher,“Integratingsensorsandsocial

networks,”inSocialNetworkDataAnalytics.Springer,2011,pp.379–412.

[2]D.Zhao,H.Ma,andL.Liu,“Energy-efficientopportunisticcoverage

forpeople-centricurbansensing,”WirelessNetworks,pp.1–16.

1318

IEEE ICC 2014 - Communication QoS, Reliability and Modeling Symposium

[3]J.Fan,J.Chen,Y.Du,W.Gao,J.Wu,andY.Sun,“Geocommunity-basedbroadcastingfordatadisseminationinmobilesocialnetworks,”IEEETransactionsonParallelandDistributedSystems,vol.24,no.4,pp.734–743,2013.

[4]M.-R.Ra,B.Liu,T.F.LaPorta,andR.Govindan,“Medusa:Apro-grammingframeworkforcrowd-sensingapplications,”inProceedingsofthe10thinternationalconferenceonMobilesystems,applications,andservices,2012,pp.337–350.

[5]D.Zhao,H.Ma,andS.Tang,“Coupon:cooperativelybuildingsensing

mapsinmobileopportunisticnetworks,”inProceedingsofIEEEMASS,2013,pp.295–303.

[6]H.Zhou,J.Chen,J.Fan,Y.Du,andS.K.Das,“Consub:Incentive-basedcontentsubscribinginselfishopportunisticmobilenetworks,”IEEEJournalonSelectedAreasinCommunications,no.99,pp.1–11,2013.

[7]D.Yang,G.Xue,X.Fang,andJ.Tang,“Crowdsourcingtosmartphones:

incentivemechanismdesignformobilephonesensing,”inProceedingsofACMMobiCom,2012,pp.173–184.

[8]J.-S.LeeandB.Hoh,“Sellyourexperiences:amarketmechanismbased

incentiveforparticipatorysensing,”inProceedingsofIEEEPerCom,2010,pp.60–68.

[9]L.Duan,T.Kubo,K.Sugiyama,J.Huang,T.Hasegawa,andJ.Walrand,

“Incentivemechanismsforsmartphonecollaborationindataacquisitionanddistributedcomputing,”inProceedingsofIEEEINFOCOM,2012,pp.1701–1709.

[10]L.G.Jaimes,I.Vergara-Laurens,andM.A.Labrador,“Alocation-based

incentivemechanismforparticipatorysensingsystemswithbudgetconstraints,”inProceedingsofIEEEPerCom,2012,pp.103–108.

[11]T.X.Liu,J.Yang,L.A.Adamic,andY.Chen,“Crowdsourcingwith

all-payauctions:Afieldexperimentontaskcn,”ProceedingsoftheAmericanSocietyforInformationScienceandTechnology,vol.48,no.1,pp.1–4,2011.

[12]J.-S.LeeandB.Hoh,“Dynamicpricingincentiveforparticipatory

sensing,”PervasiveandMobileComputing,vol.6,no.6,pp.693–708,2010.

[13]A.GhoshandP.McAfee,“Incentivizinghigh-qualityuser-generated

content,”inProceedingsofACMWWW,2011,pp.137–146.

[14]S.Ren,J.Park,andM.vanderSchaar,“Maximizingprofitonuser-generatedcontentplatformswithheterogeneousparticipants,”inPro-ceedingsofIEEEINFOCOM,2012,pp.612–620.

[15]S.Reddy,D.Estrin,andM.Srivastava,“Recruitmentframeworkforpar-ticipatorysensingdatacollections,”inPervasiveComputing.Springer,2010,pp.138–155.

[16]J.Sun,“Anincentiveschemebasedonheterogeneousbeliefvalues

forcrowdsensinginmobilesocialnetworks,”inProceedingsofIEEEGlobecom,2013,pp.1717–1722.

[17]N.Chen,N.Gravin,andP.Lu,“Ontheapproximabilityofbudget

feasiblemechanisms,”inProceedingsofACM-SIAM,2011,pp.685–699.

[18]Y.Singer,“Budgetfeasiblemechanisms,”inProceedingsofIEEEFOCS,

2010,pp.765–774.

[19]L.Tran-Thanh,S.Stein,A.Rogers,andN.R.Jennings,“Efficient

crowdsourcingofunknownexpertsusingmulti-armedbandits,”inEuropeanConferenceonArtificialIntelligence,2012,pp.768–773.[20]A.Badanidiyuru,R.Kleinberg,andY.Singer,“Learningonabudget:

Postedpricemechanismsforonlineprocurement,”inProceedingsofthe13thACMConferenceonElectronicCommerce,2012,pp.128–145.[21]J.SunandH.Ma,“Collection-behaviorbasedmulti-parameterposted

pricingmechanismforcrowdsensing,”inProceedingsofIEEEICC,2014.

[22]Y.SingerandM.Mittal,“Pricingmechanismsforcrowdsourcing

markets,”inProceedingsofACMWWW,2013,pp.1157–1166.

[23]X.OscarWang,W.Cheng,P.Mohapatra,andT.Abdelzaher,“Artsense:

anonymousreputationandtrustinparticipatorysensing,”inProceedingsofIEEEINFOCOM,2013,pp.2517–2525.

[24]N.ArchakandA.Sundararajan,“Optimaldesignofcrowdsourcing

contests.”inProceedingsofICIS,2009,p.200.

[25]A.SelaandE.Segev,“Multi-stagesequentialall-payauctions,”Ben-GurionUniversityoftheNegev,DepartmentofEconomics,Tech.Rep.,2012.

[26]E.B.Dynkin,“Theoptimumchoiceoftheinstantforstoppingamarkov

process,”inSovietMath.Dokl,vol.4,no.627-629,1963.

[27]X.Sheng,J.Tang,andW.Zhang,“Energy-efficientcollaborativesensing

withmobilephones,”inProceedingsofIEEEINFOCOM,2012,pp.1916–1924.

APPDENX

ProofofUseriBiddingFunction:

Applyingbackwardinductioniterativelyforusern,n−1,···,i+1,wecanobtainthefollowingmaximizationprob-lemofthejustarrivaluseri:

max{V

ei

n󰀂j=i+1

Pj(ej=0)−

ei

θi}

s.t.ei≥eL−th(θL−th),

(3)

whereeL−th(θL−th)denotestheL-thlargesteffortbidsob-servedbyuseri.Besides,Visderivedasfollows:

󰀄󰀅n−1󰀃n−1

Φ(e)i(1−Φ(e))n−1−i.Pj(e)=

i

i=1

Thus,theexpectedutilityVoftheuserofabilitytypeθ

L󰀁

Φj(e)ΔV(Ml,Ml+1),biddingwithqualityeisV=

whereΔV(Ml,Ml+1)=V(Ml)−V(Ml+1).

Therefore,inthefollowing,wederiveuseri’sbestresponseeffortbiddingfunctionbasedontheassumptionthatthebehaviorabilitydistributionfunctionisΦ(x)=xc,where0n󰀂

l=1

j=i+1

n−(n−(i+1))

eic(1−c)n−(n−(i+2))ic(1−c)][]=[e

VV

n−i

i1−(1−c)=[e]V

Pj(ej=0)

ic···[e]V

Sincetheconstraintisnotbinding,thefirst-ordercondition

w.r.t.eiisobtainedby:

ei−(1−c)n−i1

−=0.]

θiV

Thesecond-orderconditionisobtainedby:

[1−(1−c)n−i][−

n−iei1

{(1−c)n−i(1−(1−c)n−i)[]−(1−c)}<0VV

Thus,theinteriorsolutionisei(θi)=V[θi(1−

1

(1−c)n−i)](1−c)n−i.Letdi=(1−c)n−i.Theinte-1

riorsolutionisrewrittenasei(θi)=V[θi(1−di)]di.

←−

Therefore,ifweletθi=[(1−dL−th)θL−th]di/dL−th,and−→

θi=[(1−d1−th)θ1−th]di/d1−th/c,givene1,e2,···,ei−1,useri’sbestresponseeffortbiddingfunction,i.e.thepreviousexpression(2)holdsevidently.

1319