网格环境中信任-激励相容的资源分配机制

ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],Vol.17,No.11,November2006,pp.2245−2254:[phone]©2006byJournalofSoftware.Allrightsreserved.-∗+,,,,(,100083)AResourceAllocationMechanismProvidingTrustandIncentiveinGridZHANGYu+,LINLi,HUAIJin-Peng,LIXian-Xian,ZHONGLiang(DepartmentofComputerScienceandTechnology,BeiHangUniversity,Beijing100083,China)+Correspondingauthor:Phn:[phone],Fax:[phone],E-mail:[e-mail],(11):2245−2254.:Ingridenvironment,wheneveryparticipatingnodetriestomaximizeitsownutility,theoverallutilityofthecollaborationdrops.Intheworstcasescenario,gridresourcesareeasilydepletedduetoselfishuserstakingfreerideswithoutofferinganysharingresource.Certainresourcemanagementschemehastobeimplementedongridsystemstoensurethemworkingproperlyandtoachievebetterscalability.Inthispaper,therelationshipofresourcesincentiveandallocationinthegridisdiscussed.Ingridcomputing,theevaluationofsharedresourceisthekeytoallocateandmanagethem.Toaddresstheissue,thepricestrategyofsellersandanadaptivetrust-incentivecompatibleresourceallocationmechanismATIM(adaptivetrust-incentivecompatibleresourceallocation)arepresentedtoensurethebalanceofsupplyanddemand,promotetheuserstosharevaluableresource,andmaximizeresourceutility.Intendingforasecurecollaborativeenvironment,theframeworkconsidersthefactorsoftrustandeconomytoensurethesteadydevelopmentofgridresourcemarket.ThisapproachisalsoevaluatedbycomprehensiveexperimentsinCROWN(Chinaresearchanddevelopmentenvironmentoverwider-areanetwork).Keywords:resourceallocation;incentive;trust;pricestrategy;CROWN(Chinaresearchanddevelopmentenvironmentoverwider-areanetwork):,,.,.,,.,-.,,,.,-ATIM(adaptivetrust-incentivecompatibleresourceallocation),,∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.90412011();theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2005AA119010((863));theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.2005CB321803((973))Received2006-06-08;Accepted2006-08-072246JournalofSoftwareVol.17,No.11,November2006,.CROWN(Chinaresearchanddevelopmentenvironmentoverwider-areanetwork)ATIM.:;;;;CROWN(Chinaresearchanddevelopmentenvironmentoverwider-areanetwork):TP393:A,,CPU,.,.,.,.2004OSDI(operatingsystemsdesignandimplementation),CPU“tragedyofthecommons”[1].,,.,,,,.,.,[2−5],.,.,,,.,[1,6,7],,.,,.,.,,,-(adaptivetrust-incentivecompatibleresourceallocation,ATIM),.,,.,-ATIM,,,.,CROWN(Chinaresearchanddevelopmentenvironmentoverwider-areanetwork)ATIM,.1,.[2−5],[3,4]([2][5]),[4],,.,.,,.,.Buyya[8,9],.,Buyya,.,,,[1,6,7].Chun[1]-(auction-biding),,,.Feldman[6],(bestresponse).,,.,,.:-2247ATIM,,“”.,-,,.,,,.2CROWNCROWN.,Grid,P2P[10−12].CROWN1.,(sink),(backbone).,,P2P,.,.0.80.5sksjClubkClubjciChildlayerSinklayerFig.1Thetwo-tierarchitectureofresourcemanagement12.1.,ci,i∈{1,…,q},q∈ℕ.2.2.(),sj,j∈{1,…,p},p∈ℕ.,.Club.,Club.2.3.Club≙(num,S,D,E,P).num∈ℕClub;S,D,E,PClub.2.4(TRUST).[13],Club,Club,.:(1):Clubjci,sj.,Clubjci(h),ci,dtj,i=1−λh,λ.(2):ClubkClubj,sk.,Clubkm,n(ClubkClubj),ClubkClubj:−=−else,0if,1),(,nmnmrtnmjkλ.(3),ClubkClubjcit.jkrtijikdt,)1(1,,−−=2248JournalofSoftwareVol.17,No.11,November2006,,,.,1,sjci0.8,sksj0.5,sksjci1−(1−0.8)0.55=0.55.3ATIM.2,p∈ℕ(pClub),Club;q∈ℕ,.,,,.,,[14].,,-,:(1),,;(2),;(3),;(4).,.,,,.spsj……cqci…c2c1…s1Fig.2Consumersbiddingandprovidersallocation23.1,,.,.,.,,.Club,:3.1.E(P*)=0,Club,P*.P=P+δ(D−S)[15,16],δε,3.,D−S0,;,,|D−S|.,(tatonnement)[15,16],Tatonnement.3T,T,.;(|D−S|ε).,.,,|D−S|ε,:|D−S|εPublishingP,Collectingbids,computingDk++InitializingthenexttimestepsT:PriceP,adjustmentratioδ,terminalparameterε,iterationroundsk=0YNε=|D−S|NTatonnementprocessδ=δ/2NYYP=P+δ(D−S)0k1AllocatingresourceFig.3Thetatonnementprocessofpriceadjustment3Tatonnement:-2249(1),,D≫S;(2),D≫S,.,.3.21,.Table1Theallocationstrategyofresourceproviders1PolicyConditionModeTIM|D−S|εMaximizingprofitwhilesatisfyingtheexecutiondeadlineofjobsGreedyD≫SFocusingontheprofitofexecutingtheunitlengthjobATIMSwitchingbetweenTIMandGreedyaccordingtosupplyanddemand1.TIM(|D−S|ε),TIM:,,.,,,,.3.2.bid=(nlow,l,pl,dl,t,φ),,nlow,l,pldl(penaltyline)(deadline),t,φ.,4,dlplφξ=−.x(≥nlow),xl,lplx−,,−×−plxltξφt,()(),2.4.Timeξ(penaltyrate)dlplMaxvaluePaymentvalueφFig.4Theprovider’sutilityforexecutingabid4q,,U,:),...,,(21qjjjxxx)(ijx3.3.sjq(),...,,21qjjjxxx.)(,−×−=∑jiijjiijiiijijplxltxUξφ(0,)ijjxS∈().,2250JournalofSoftwareVol.17,No.11,November2006j,.TIM),...,,(21qjjjxxx()iijjigxx=≤∑S,MAU(maximizingaggregateutility),:,jjiiijjkkktlStlξξjjS,;jD.)(,)(s.t.)(max∑=≤iijijjijijxxgSxgxU3.1.sjPj,sjci,ijk()jx∗=∑,()ijx∗MAU.,.3.1,,TIM,,(),,,.2.GreedyTIM,.,,,≪jSiinlow∑≪Sj≪3.1.,Greedy,(,jDtlφ×),.Greedy,.3.ATIMTIMGreedy:,,TIM;Greedy.,-ATIM.5,kthresholdEthreshold,TIMGreedy.IteratePTIMpolicyGreedypolicy|D−