capturepp点点通2004

Agent-basedformationofvirtualorganisationsTimothyJ.
Normana,*,AlunPreecea,StuartChalmersa,NicholasR.
Jenningsb,MichaelLuckb,VietD.
Dangb,ThucD.
Nguyenb,VikasDeorac,JianhuaShaoc,W.
AlexGrayc,NickJ.
FiddiancaDepartmentComputingScience,UniversityofAberdeen,Aberdeen,UKbSchoolofElectronicsandComputingScience,UniversityofSouthampton,Southampton,UKcDepartmentComputerScience,CardiffUniversity,Cardiff,UKAvailableonline12April2004AbstractVirtualorganisations(VOs)arecomposedofanumberofindividuals,departmentsororganisationseachofwhichhasarangeofcapabilitiesandresourcesattheirdisposal.
TheseVOsareformedsothatresourcesmaybepooledandservicescombinedwithaviewtoexploitingaperceivedmarketniche.
However,inthemoderncommercialenvironmentitisessentialtorespondrapidlytochangesinthemarkettoremaincompetitive.
Thus,thereisaneedforrobust,agile,exiblesystemstosupporttheprocessofVOmanagement.
WithintheCONOISE(www.
conoise.
org)project,agent-basedmodelsandtechniquesarebeingdevelopedfortheautomatedformationandmaintenanceofvirtualorganisations.
Inthispaperwefocusontheformer,namelyhowaneffectiveVOmaybeformedrapidlyforaspeciedpurpose.
q2004ElsevierB.
V.
Allrightsreserved.
Keywords:Virtualorganisations;Agents1.
IntroductionVirtualorganisations(VOs)arecomposedofanumberofsemi-independentautonomousentities(representingdifferentindividuals,departmentsandorganisations)eachofwhichhasarangeofproblemsolvingcapabilitiesandresourcesattheirdisposal.
Theseentitiesco-existandsometimescompetewithoneanotherinaubiquitousvirtualmarketplace.
Eachentityattemptstoattracttheattentionofpotentialcustomersbydescribingthecostandqualitiesofitsservices,withthegoalofsellingtheminawaythatmaximisestheirindividualgain.
Sometimes,however,oneormoreoftheentitiesmayrealisetherearepotentialbenetstobeobtainedfrompoolingresources:eitherwithacompetitor(toformacoalition)orwithanentitywithcomplementaryexpertise(toofferanewtypeofservice).
Whenthispotentialisrecognised,therelevantentitiesgothroughaprocessoftryingtoformanewVOtoexploittheperceivedniche.
Considertwoexamples.
First,supposethattworelativelysmallairlinecompanieswithcomplementaryroutesagreetocooperateandcoordinatetheirservicessothattheymayofferights,asacoalition,betweenawiderrangeofdestinations,withaviewtobecomingmorecompetitiveinthismarket.
Second,astreamedvideocontentproviderandahighbandwidthmobileserviceprovidermayagreetocollaborateinthedeliveryofsuchcontentasaservicetomobiledevices(thiscorrespondstoanewtypeofservice).
Giventheindependentnatureoftheentitiesinvolved,therearenumerousreasonswhytheformationofaVOmayfail.
Ifitsucceeds,however,thecollectionofindependententitieswillactasasingleconceptualunitinthecontextoftheproposedservice(theymaycontinuetoretaintheirindividualidentityoutsidethiscontext).
Inparticular,theparticipantsmustcooperateandcoordinatetheiractivitiesindeliveringtheservicesofthisnewlyformedorganisation—theparticipantsmusthavetheabilitytomanagetheVOeffectively.
Indynamicenvironments,however,thecontextmaychangeatanytime,suchthattheVOisnolongerviable.
Itwillthenneedtoeitherdisbandorre-arrangeitselfintoaneworganisationthatbettertstheprevailingcircumstances.
Thisautomatedformationandongoingmanagementofvirtualorganisationsinopenenvironmentsrepresentsamajorresearchchallenge.
Akeyobjectiveinputtingsuchorganisationstogetheristoensurethattheyarebothagile(abletoadapttochangingcircumstances)andresilient(abletoachievetheirobjectivesinadynamicanduncertainenvironment).
Insuchenvironments,theparticipants'behaviourwillbeinformedbyexploitinganumberof0950-7051/$-seefrontmatterq2004ElsevierB.
V.
Allrightsreserved.
doi:10.
1016/j.
knosys.
2004.
03.
005Knowledge-BasedSystems17(2004)103–111www.
elsevier.
com/locate/knosys*Correspondingauthor.
E-mailaddress:tnorman@csd.
abdn.
ac.
uk(T.
J.
Norman).
diverseformsofinformation—advertisements(capabilitiesandreputationsofindividualagents),meta-data(schemasandontologies)andinformationresources(databasesandknowledgebases).
ThenovelcontributionoftheCONOISEprojectistoprovideamodelofVOmanagementthatoperatesinarobustandresilientmannerincomplexelectroniccommercescenarios.
Inparticular,wefocusontherstelementofacompleteVOmanagementsystem:VOformation.
TheformationofavirtualorganisationwithintheCONOISEsystemisgroundedonthreekeytechnol-ogies:thedecision-makingmechanismofanindividualagent,anauctionmechanismfortheallocationofcontracts,andtherepresentationofservices.
Thecontributionofthispaperliesintheintegrationofthesetechnologiestoprovideasolutiontotheproblemofformingeffectivevirtualorganisationsincomplex,informationrichenvironments.
BeforetheCONOISEsolutiontoVOformationisdiscussedindetail(Section3),itisimportanttohaveabetterunderstandingoftheissuesthatmustbeconsideredindevelopingacomputationalmodelofVOformationandtopresentaspecicscenarioinwhichtheideaspresentedinthispapermaybegrounded(Section2).
FollowingthedetailonVOformation,wediscussavenuesforfuturedevelop-mentbyreturningtotheexampleintroducedinSection2andpresentourconclusionstothispaper(Section6).
2.
AVOformationscenarioInpresentinganoverallpictureoftheCONOISEVOmanagementprocess,wewilluseaspecicscenario.
Thisscenarioillustratesanumberofimportantcharacter-isticsthatmustbetakenintoaccountinthedevelopmentofaneffectiveVOmanagementsystem.
First,theremaybemultipleservicesavailablefromanumberofagentsrepresentingindependentorganisations.
Multipleagentsmayofferbroadlysimilarservices.
Theservicesthemselvesaredescribedbymultipleattributes;forexample,price,quality,anddeliverytime.
Theservicesavailablemaychangeovertime:newservicesmaybecomeavailable,oragentsmayalterthewayinwhichexistingservicesareoffered.
Servicesmaydifferintermsofthenumberandheterogeneityofthetasksinvolvedinthedeliveryoftheserviceandtheirdegreeofinterdependence,andthetypeandfrequencyofinteractionsbetweendifferentcustomerswhiletheserviceisbeingdelivered.
Theagentsinvolvedinthesystemmayalsoemploydifferentpoliciesfordealingwiththeuncertaintyinherentinsuchadomain;forexample,anagentmaygenerateslackresourcestolimitthepossibilityofalossinservicetothecustomer,oritmayemployrigorouscoordinationmechanismstoimprovesupplychainintegration.
Withtheseissuesinmind,considerthefollowingscenario.
AuserwantstopurchaseandreceiveamonthlymoviesubscriptionpackageonhisPDA/phone,andamonthlynewsservice.
TheuseralsowantsamonthlypackageforhisPDA/phonethatincludes30freetextmessagesandatleast50freeminutespermonth.
Thisisareasonablycomplexandrealisticsetofrequirementsthatincorporatesfourtypesofservice:movies,news,textmessagingandaphoneservice.
Withinthescenario,arequirementsagent(RA),representsthisuser.
Inadditiontotheagentrepresentingthecustomer'srequirements,thereareanumberofagentsrepresentingserviceproviders(SP1–SPn).
Theservicesthattheseagentsprovidearecapturedas'packages',whichmayrepresentquitecomplexoffers(seeSection3.
2).
SupposethatagentSP1offersanumberofpackagescontainingnewsandmoviesservices.
Thepackagesonoffermayinclude,forexample,newsandmoviesservicesforonemonthat30permonth,andthesameserviceforsixmonthsat25permonth.
PriortotheRAinitiatingtheprocessofVOformation,itisassumedthateachserviceprovideradvertisestheservicesthattheyoffer—e.
g.
moviesortextmessaging—toayellowpagesagent(YP).
ThisagentisconsultedbytheRAandaskedtorecommendagentsthathaveadvertisedtheabilitytodelivermovies,news,textmessagingorphoneservices.
Followingthereceiptofthisinformation,theRAwilldistributeacallforbidstofulllaspecicsetofrequirements(seeFig.
1).
Inthiscallforproposalstheunits—movies,news,textmessagingandphone—andthevaluesassociatedwillrepresentcomponentsinapackageandthevaluesandattributesofthatpackage.
Theserviceprovideragentsmustnowdecidewhetherandwhattobidinresponsetothiscall.
Supposethattherearefourserviceprovideragentscontactedinthisway—SP1–SP4—andthepackagesonofferarethoseillustratedinTable1.
NotethatSP3imposesafurtherconstraintonthepackagethatitoffers:boththeservicesstatedinthepackagemustbetakentogether.
Howthesepackagesareconstructedisnotspecied,butanindividualserviceprovidercouldhaveputapackagetogetherfromitsownresourcesorthroughtheformationofavirtualorganisation.
Fig.
1.
Theformationofavirtualorganisation.
T.
J.
Normanetal.
/Knowledge-BasedSystems17(2004)103–111104TheRAmust,oncethedeadlineforproposalstobesubmittedhaspassed,selectsomecombinationofservicesthatbestsuitstheneedsoftheuser.
AnappropriatecombinationofservicesgiventhesebidsistotakethemoviesserviceofferedbySP1(notethatthispackagemaybesplitintoitscomponentservices),thenewsserviceofferedbySP2andbothtextandphoneservicesofferedbySP3.
Althoughthephoneservicerequirementisnotmet,thisrepresentsthebestchoicegiventhecircumstances.
Thus,onceproposalacceptancesandrejectionsaresenttotheagentsthatsubmittedbids,avirtualorganisationisformedthatinvolvesRA,SP1,SP2andSP3.
WewillreturntothisscenariothroughoutSection3andthenagaininSection6whereVOmaintenanceisdiscussedastheprincipalfocusoffuturedevelopment.
However,atthispointwepresentthedetailoftheCONOISEVOformationmechanism.
3.
TheformationofavirtualorganisationAsdiscussedinSection1,thenoveltyofthisresearchliesinthetechnologiesbeingemployedinthemanagementofvirtualorganisationsandtheirintegrationinacoherentVOmanagementsystem.
Herewefocusontherstelementofthisintegratedsystem:theformationofaVO.
IndevelopingamodelofVOformation,thereareanumberofissuesthatmustbetakenintoaccountincluding:AnagentthatisconsideringwhethertooffertojoinaVOmustdeterminetheconditionsunderwhichitisprot-ableforittojoin(seeSection3.
1).
AnagentmustbeabletorecognisecircumstancesinwhichitshouldinitiateVOformation(seeSection3.
1).
TheagentthatinitiatestheVOformationprocessmust,givenanumberofoffers,determinethebestcombinationofbusinesspartners(seeSection3.
2).
Inthesupportofthesedecisions,richdescriptionsofservicequalityarerequiredtocapturetheextenttowhichservicesmeettheexpectationsofconsumers(seeSection3.
3).
3.
1.
DeterminingwhattoofferThepurposeofaserviceprovideragentistobeabletocreateabidinreplytoacallforservices,anddecidehowmuchresourceitcan,andmoreimportantly,howmuchresourceitwantstoprovideasabidfortheprocurementofthatservice.
Furthermore,anyagentmay,whenconsideringwhattooffer,takeontheroleoftheRAinFig.
1andissueacallforbidsifitidentiesashortfallinitsexistingresourcesavailable.
Eachagentmust,therefore,beabletoactasacontractorandsupplierinanygivensituation.
Togivesuchdual-purposefunctionality,wehavedesignedaConstraintSatisfactionProgram(CSP)thatmodelsthedecisionmakingprocesstheagentmusttakeinsuchscenarios.
Fig.
2showsonesuchscenario,wheretheagentactsasthesupplierandreceivesacallforbids.
Ithasthefollowingpossibleresponses:(i)Itcandecidenottobidfortheservice;(ii)Itcanbidusingjustitsownresources;(iii)ItcanprovideabidfromwithinanexistingVOcollaborationutilisingthecombinedVO'sresources;or(iv)ItidentiesaneedforextraresourcesnotavailablewithintheexistingVO.
Wecanseethatthelastoptionrepresentsthescenariowheretheagentbecomesthecontractor,anditselfbeginstheprocessofissuingacallforbidstootheragentsintheenvironment.
ThetechniqueusedtoprovidethedecisionmakingprocessisbasedonacumulativeschedulingCSP[6].
Usually,thisisdenedasthemaximumallowablelimitfromanite'pool'ofresourcethatcanbeusedcollectivelybytheagentsatanygiventime[1].
Wedeneourproblemdifferently;ratherthantheagentstakingresourcesfromacommunalresource,wehavetheagentscontributingtothecommunalpool,andwedeneaminimumallowablelimitsothatthesetofagentsmustprovidethisserviceatleastorabovetherequiredthresholdlimitovertherequiredtime.
Ifitisnotpossible,thenweusetheCSPtohighlightthedecitandcanthenlooktocontracting-outfortheprovisionofthisshortfall.
Toexplainourcumulativeschedulingbasedalgorithm,werstdenetheproblem.
GivenasetofnagentsinaVO,eachofwhomcanprovideaspecicniteamountofaresourceR;{R1…Rn};asetofstarttimesdescribingwhenTable1AnexamplesetofavailablepackagesServiceproviderMovies(permonth)News(no.
ofdailyupdates)Text(no.
offreemessages)Phone(no.
offreemin.
)SP11024SP272SP312030SP4530Fig.
2.
Theagentdecisionmakingprocess.
T.
J.
Normanetal.
/Knowledge-BasedSystems17(2004)103–111105theagentcanbeginprovidingeachoftheresources{S1…Sn}andasetofdurationsoverwhichtheresourceisavailable{D1…Dn}wecansay,foranagenti[{1…n};thatthefunctionditevaluatesto1ifthecurrenttimetiswithintheagent'sresourcestartandendtime(Si,t#SiDi;and0otherwise.
Then,anamountrofresourceRisavailableoveratimeperiod1…viff;t[{1…v}Pni1Ridit$r:Inotherwords,thetotalsumoftheresourceprovidedbythesetofagentswithindices{1…n}inaVOatanytimebetween1…tdoesnotfallbelowtheresourcelimitrspecied.
Usingthisrepresentationmeansthatwecanalsouseconstraintsontheagentresourcedomainstorepresentexistingcommit-mentsonthoseresources.
Inourscenario,thishelpsustomodelthedecisionmakingprocessastheagentcanlookattheexistingpartnersinitsVO,aswellasitsownresourcesandtheexistingcommitments,andseewhetheritcanaccommodatethenewallocationofresourcesaskedofit.
Asanexample,letuslookatanagenta1whoisinaVOwithtwootheragentsa2,a3.
Allcanprovideacertainamountofbandwidth(10,20and30units,respectively).
Agenta1isaskedtoprovideatotalbandwidthamountof40units(asdescribedinSection1)fromtime0to80,soitusestheknowledgeoftheamountofresourcescontributedfromtheotheragentsintheVO(alongwithitsown)toworkoutifthisispossible.
Fig.
3showsanexampleallocation.
Atotalrateof40unitsisprovidedbya3anda2between0and50,thenbya3anda1between50and80.
Wecanalsoaddconstraintsontheresourcesavailableforeachagentateachpointintimetorepresentcommitmentsunderothercontracts.
Ofcoursetherearemanypermutationsthatwecanhaveinthisresourceallocationprocess.
Whatwehavedescribedsofarshowswhattheagentcando,butwealsowanttobeabletomodelautilitythatallowstheagenttochoosebetweencompetingviableallocations(i.
e.
decidewhatitwantstodo).
Wehaveimplementedthisutilityusingconstraintreication,whereeachconstraintonthedomainoftheresourcehasanassociatedvalue,1or0,whichdependsonthesuccessorfailureoftheconstraint.
Forinstance,usingSICStusProlog1notation,X,Y–,BstatesthatifXislessthanY,thevariableBissetto1,otherwiseitissetto0.
Whentheagentstrytoprovideanewresourcewetakeintoaccountthecurrentcommitmentsoftheagents(alltheconstraintscurrentlypostedagainsttheresources)andwegetasetofreiedvaluesforeachcommitmentwhichwecanthenusetoseewhichconstraintsaresatisablealongsidethenewcallforbids,andwhichones'fail',andsohavea0valueintheirreication,thatis,theresourcescannotbeallocatedinthecurrentsituation.
Wecanalsohighlightwherethenewbidisfailingandidentifytheshortfall.
Usingthisinformation,wealsohaveabasisonwhichwecanlookatqualityandpricingmetrics(seeSection3.
3)forcommitmentsincomparisontothenewresourcebeingbidfor,andthisthereforeallowsustoprioritisethecommitmentswehaveagainstanynewonesthatmightarise.
Beforewediscussqualityissues,however,wewilladdresstheproblemofwhichofferstheagentinitiatingVOformationshouldaccepttocreatethebest,oratleastasatisfactory,VO.
3.
2.
DeterminingwhattoacceptSinceVOsdonothavearigidorganisationalframework,theselectionofpartnersisoneofthemostimportantactivitiesintheformationoftheVO([16]).
However,thereareseveralrequirementsthatneedtobemetbythisprocess:Themostsuitablesetofpartnersfromthosethatareavailableshouldbeselected.
Inthiscontext,mostsuitablemeanstheoneswithlowestpricebids.
Notethatthepriceheredoesnotjustmeanthemonetaryvalueofthebidsbutmaybeacombinedratingvalue,calculatedfrommonetaryvalueandotherattributesofthegoods/servicesofferedbythepartners(e.
g.
time).
Theselectionshouldoccurwithinacomputationallyreasonabletimeframesothatthemarketnichecanbeexploitedasitbecomesavailable.
ThepotentialpartnersshouldbeabletovarytheirbiddependingontheirinvolvementintheVO.
Thus,forexample,apartnermaybewillingtocompleteservicesmorecheaplyifithasahighdegreeofinvolvementintheVO(becausetheintrinsiccostscanbedepreciatedovermanyinstances).
Incontrast,ifapartnerhasacomparativelysmallinvolvementthentheunitcostmaybemuchhigher.
Giventheopennatureoftheenvironmentandthelackofapre-ordainedstructure,webelievethiscreationprocessisbestachievedusingsomeformofmarketplacestructure(auction).
Thisisbecausemarketsareahighlyeffectivestructureforallocatingresourcesinsituationsinwhichtherearemanyself-interestedandautonomousstake-holders.
Fig.
3.
Anexampleschedule.
1ThecumulativeschedulingalgorithmisimplementedusingthenitedomainconstraintlibraryinSICStus.
T.
J.
Normanetal.
/Knowledge-BasedSystems17(2004)103–111106Thereare,however,manydifferenttypesofauction(seeRef.
[24]foraclassication)butinthisworkitwasdecidedtoadoptacombinatorialauctionapproach.
Acombinatorialauctionisasophisticatedtypeofauctionwheremultipleunitsofmultiple(potentiallyinter-related)itemsaretradedsimultaneously.
Inacombinatorialauction,biddersmaybidforarbitrarycombinationsofitems.
Forexample,asinglebidmaybefor5movies,24newsupdates(perday)and20minofphoneatatotalpriceppermonth.
Amorecomplicatedbidmaybeforq1moviesandq2newsupdatesatprice30q13q2ifq1,10orq2,24;andatprice20q12q2ifq1$10andq2$24:ThisparticulartypeofauctionissuitableforthisproblembecausethedegreeofexibilityinexpressingoffersallowsthepotentialpartnerstovarytheirbiddependingontheirinvolvementintheVO.
However,themaindisadvantagesofcombinatorialauctionsstemfromthelackofacompactandexpressivebidrepresentationandefcientclearingalgorithmsfordeterminingtheprices,quantitiesandtradingpartnersasafunctionofthebidsmade.
Withoutsuchalgorithms,becauseofthecompu-tationalcomplexityoftheproblem,theremaybeunacceptabledelaysforauctionsthathaveonlyamediumnumberofparticipants.
Thus,intheCONOISEcontext,acompactandexpressivebidrepresentationlanguageandefcientclearingalgorithmsforcombinatorialauctionshavebeendeveloped[8].
Specically,wedevelopedabidpresentationlanguagewherethepriceofapackage,Pir1;…;rmisspeciedas:vit1;…;tmPmj1Pijrj;wherePjiisthepricefunctionofagentiforitemj;intheformofapiecewiselinearcurve(i.
efunction'sgraphiscomposedofmanysegments,eachofwhichislinear),tjisthesegmentnumberofPjithatrjbelongstoandviisafunctionthatexpressescorrelationsbetweenitemsinthesetofsegments.
Moreprecisely,eachpiece-wiselinearfunctionPjiiscomposedofNjilinearsegments,numberedfrom1toNji:Eachindividualsegmentwithsegmentnumberl;1#l#Nji;isdescribedbyastartingquantitysji;landanendingquantityeji;l;aunitpricepji;landaxedpricecji;l;withthemeaningthat:bidderiwantstotradeanyrunitsofitemj;sji;l#r#eji;lwiththepricePpji;lrcji;l:Notethatthesegmentsarenotrequiredtobecontinuous;thatis,sji;l12eji;lmaynotequal1.
Also,forconvenience,wecallsegmentnumber0thesegmentinwhichthestartingquantity,theendingquantity,theunitpriceandthexedpriceareallequalto0.
Thus,thenumberofsegmentsofPji;includingthisspecialsegment,willequalNji1:Thecorrelationfunctionvihasmanypotentialusesinreal-lifescenarios.
Forexample,supposebidderi;sellingthreeitems(movies,textmessagesandphonecalls),wantstoexpressthingslike"Iamwillingtosell100minofphonecallspermonthand50textmessagespermonthtogetherwithapriceP;butnotseparately".
Usingourcorrelationfunction,thiscanbeexpressedbyaddingsegmentst1andt2;whichcontainonly100and50,tothefunctionsP1iandP2i;respectively,thengivingvit1;t2;t3averysmallvalue,foreveryt3;andgivingP1i100andP2i50verybigvalues.
Thisway,theauctioneerwillneverchoosetobuy100minofphonecallsor50textmessagesseparately.
Thismeansofrepresentingbidsisnovelandsuperiortopopularbidrepresentations.
Comparedwithotherworkinthisarea[9,19]itismoreexpressiveasitallowsbidderstodetailthecorrelationbetweenseparateitems.
ComparedtoXORatomicpropositionpresentations,itisnearlyasexpressivebutmuchmorecompact.
Moreover,thiscaseisimportanttoconsiderbecausepiecewiselinearcurvesarecommonlyusedinindustrialtradingapplications[9]andanygeneralcurvecanbeapproximatedarbitrarilycloselybyafamilyofsuchfunctions[19].
Twosetsofclearingalgorithmshavebeendeveloped:onewithpolynomialcomplexityandhasbeenshowntoproduceasolutionthatiswithinaniteboundoftheoptimal[8],whiletheotherisnotpolynomialbutisguaranteedtoproducetheoptimalallocation[7].
Inparticular,theformerusesagreedyapproach,andhasarunningtimeofOn2;wherenisthenumberofbidders.
Thesolutionitproducesisshowntobewithinaniteboundoftheoptimal,whichisproportionaltonandKm21;wheremisthenumberofitemsandKisasmallconstant.
Ontheotherhand,thelatterisguaranteedtoproducetheoptimalallocation,andhasaworst-caserunningtimethatisproportionaltomnK01mn;whereK0istheupperboundonthenumberofsegmentsofPji:Asthesetwosetsofalgorithmsprovideatrade-offbetweenrunningtimeandoptimalityofsolution,theyprovidetheuserwithmoreexibility.
Incaseswheretherunningtimeismorecrucial,thepolynomialalgorithmswouldbemoreappropriate,whileincaseswhereoptimalityofthesolutionismoredesirable,theoptimalalgorithmswillbebettersuited.
3.
3.
ManagingqualityofdeliveryInthissectionwedescribetheroleoftheQualityAgent(QA)intheCONOISEsolutiontotheproblemofVOmanagement.
QAisresponsibleforcollectinginformationrelatedtothequalityoftheservicesofferedbySPs,andtosupplythisinformationtoRAforittouseintheprocessofformingaVO.
TheinformationaboutQualityofService(QoS)providesanotherbasisfornegotiation(inadditiontotheprice),andthusisimportanttotheprocessofVOformation.
ThereexistvariousinterpretationsofQoSintheliteratureandalargenumberofmethodshavebeenproposedformanagingQoSinmarketing,e-commerceandothersystems[2,13].
Whilesomequalities,suchasnetworktrafcandspeed,maybemonitoredautomatically,moresubjectivequalities,forexample,frequencyofnewsupdates,requireuserpreferenceinformation.
Existingmethodstypicallyinviteuserstorateaserviceinabsoluteterms,e.
g.
good,bador7outof10.
SuchqualityratingsmaynotbeverymeaningfulorcanevenbemisleadinginT.
J.
Normanetal.
/Knowledge-BasedSystems17(2004)103–111107somecases,becausethecontextwithinwhichtheratingsarederivedisnotknown.
InCONOISE,weattempttoaddresstheproblembyintroducingamodelforcollectingandmonitoringQoSrelativetospecicusersortypesofuser.
Thatis,weattempttocollectfromserviceusers(ortheiragents)QoSratingsaswellastheirexpectationsonQoS,sothatwecanmeasurehowwelladeliveredservicemeetsusers'expectations.
Morespecically,letSbeaserviceandq1;q2;…;qnbeasetofattributeswithwhichwewishtomonitorQoSforS.
WecollectthefollowingfromserviceusersforeachqiofS:kQEqi;QPqi;QRqilwhereQEqirepresentstheQoSthattheuserexpectsfromSwithrespecttoqi;QPqitheactualQoSofqiperceivedorexperiencedbytheuserafterusingS;andQRqitheratingthattheusergivestoSintermsofqi:Allthreevaluesarerepresentedbyrealnumbersintherange[0,1].
Forexample,thequalityofnewsupdatefrequencymayberatedbyauseraskQEfr0:65;QPfr0:76;QRfr0:85lindicatingthatanaboveaveragefrequencywasexpected(0.
65),theactualupdatedeliverywasmorefrequent(0.
76)and,consequently,thequalityofservicewasconsideredtobegood(0.
85).
TocombineQoSratingscollectedfromserviceusersintoanoverallassessmentofqualityforagivenserviceS;weperformtwocalculations:(i)combiningindividualratingsforeachqiofSintoanaggregaterating,and(ii)combiningtheratingsforindividualqi'sintoanoverallratingforS:Currently,wetreatallqualityattributestobeofequalimportanceand(ii)isderivedbyasimpleaverageoftheindividualratings.
Butitispossibletoconsideraweightedaveragesothatthefactthatsomeattributesaremoresignicantthantheothersmaybetakenintoaccount.
Thecombinationofindividualratingsdependsonthequalityassessmentrequest,R;receivedbytheQA.
IfRspeciesnoqualityexpectationonqi;thenQqiPkj1wjQRjqi:Thisisequivalenttothemajorityofexistingapproachestoqualitycalculation;theoverallratingforqiisaweightedsumofindividualratings,andtheweightsareusedtoallowfactorssuchastrusttobetakenintoaccount[25].
IfRspeciesaqualityexpectationEqia[0;1onqi:(thequalityexpectationonqiisa;thenQqiPmj1wjQR0jqiHere,QR0jqiisaratingwhosecorrespondingexpectationQE0jqiiscompatiblewithEqia:Inthispaper,weuseasimplecriterionfordeterminingwhetherthetwoarecompatible:QE0jqiandEqiaarecompatibleiflQE0jqi2al#d;wheredisaconstant.
However,morecomplexformsofcompatibilitytestarepossible,forexample,byspecifyingqualityexpectationsasrangesandbyallowingfuzzymatchingbetweenQE0jqiandEqia:Furtherdiscussionontheseissuesisbeyondthescopeofthispaper.
WenowillustrateourqualitymodelandassessmentbyconsideringthescenariogiveninSection2.
Supposethatwehavesixagents(A1–A6)whohaveusedthenewsservicesprovidedbySP1andSP2.
Eachagentisthenaskedtoratetheservicesintermsofnewsupdatefrequency.
Table2showstheratingscollected.
Inthisexample,theusersofSP1havehighexpectations,butdonotreceivewhattheyexpect.
UsersofSP2,ontheotherhand,donothavehighexpectationsbutaregenerallysatisedwiththeservice.
ItisthisdifferenceinexpectationthatQAexploitsinassessingQoSforservices.
SupposethatQAisaskedtoassessQoSforSP1andSP2intermsofnewsupdatefrequency(fr),givenEfrnotspecied,Efr0:5andEfr0:8;respectively.
Assumingthatwehaved0:1;theresultofcalculationis:(i)whenEfrnotspecied,QoSofSP1is0.
50andQoSofSP2is0.
63;(ii)whenEfr0:5;QoSofSP1is0.
60andQoSofSP2is0.
85;and(iii)whenEfr0:8;QoSofSP1is0.
50andQoSofSP2is0.
20.
ThequalityratingsforSP1andSP2can,therefore,varywithrespecttoexpectation.
Thisisincontrasttomoreconventionalapproachestoqualitycalculationthatdonotconsideruserexpectations(equivalenttoEqinotspecied),ourmethodgivesamoremeaningfulratingforaserviceonacase-by-casebasis.
Finally,itisworthmentioningthatalthoughQPqi;thequalityperceivedbytheuser,isnotusedinqualitycalculationatthemoment,itcanplayanimportantroleinderivingmoreaccuratequalityassessments.
Forexample,bymonitoringtherelationshipbetweenQRqiandlQEqi2QPqiloveraperiodoftimewithsufcientratingdata,wecandeterminewhetheraparticularagenthasbeen'harsh'inratingservices.
Byfactoringsuchknowledgeintoqualitycalculations,wecandelivermoreaccurateQoSassessmentfortheRAagent.
4.
VOmanagementandfutureresearchInthispaper,wehavefocussedourattentiononVOformation.
However,onceformed,aVOmustbemanagedeffectively,and,possibly,restructuredifnewopportunitiesareidentiedorproblemsencountered.
ReturningtothescenariointroducedinSection2,supposethatanewserviceprovider,SP5,enterstheenvironmentofferingatextmessagingservicewith200freemessagespermonth.
ThisopportunitymayhavebeenrecognisedbytheRAwhilemonitoringnewpackageadvertisements,orbySP5Table2AsetofexamplequalityratingscollectedforSP1andSP2AgentSP1SP2A1k0.
9,0.
7,0.
5lA2k0.
4,0.
4,0.
6lk0.
4,0.
5,0.
9lA3k0.
8,0.
6,0.
3lA4k0.
4,0.
5,0.
8lA5k0.
9,0.
7,0.
5lA6k0.
9,0.
7,0.
6lk0.
9,0.
4,0.
2lT.
J.
Normanetal.
/Knowledge-BasedSystems17(2004)103–111108approachingthemanageroftheexistingVO.
IfsuchanopportunityisrecognisedbyRAitmayconsiderre-nego-tiatingthecontractsthatbindthisVOtogether.
SupposethatRAattemptstore-negotiatewithSP3forjustphonecalls,andtakethetextmessagingserviceprovidedbySP5.
However,SP3'sdealhasaconstraintthatsaysbothphonecallsandtext-messagingservicesmustbetakentogetherasapackage.
RAmaythendecidetoseekanalternativeproviderofphonecalls(inthiscaseSP4).
(Theremay,ofcourse,bepenaltiestopayforwithdrawingfromthecontractwithSP3,andsuchfactorsmustbetakenintoaccountwhenRAconsidersrestructuringtheVO).
Asaresultofthisrestructuring,SP3ceasestobeamemberoftheVO,buttwonewsuppliers—SP4andSP5—becomeinvolved.
ItisnotonlyopportunitiesintheformofnewservicepackagesbecomingavailablethatthemanagerofaVO(inthisexampleRA)musttakeintoaccount;problemsmayoccurthatforcetherestructuringoftheVO;forexample,SP2maywithdrawitsnewsservice.
DuringthelifetimeofaVO,automatednegotiation2canbeusedtomaintainorextenditsformation.
Considertwopossiblesituations:whenaVO(composedofnagents{A1;A2…An}hasbeenformed,oneagentAidropsoutduetoaspecicreason(e.
g.
communicationfailureoritisnolongerinitsownselfinteresttobeinvolved).
Inthiscase,thecurrentVOshouldnotbedissolvedbecausetheremainingagentsarestillcommittedtotheiraimsandobjectives.
Therefore,anotheragentshouldbesummonedtoreplaceAi:Inthissituation,RAhastondthenewagentwithinminimumtimeandcost.
ThesecondsituationiswhenaVOhasbeenformedandisoperatingandanewrequirementisintroducedthatthecurrentVOisnotcapableofhandling.
InordertoenhancethecurrentfunctionalityoftheVO,oneormoreagentsneedtobeaddedtotheformation.
Again,thischangetotheformationoftheVOiscarriedoutviatheprocessofnegotiation.
Inmoredetail,intheCONOISEcontext,whenRAneedstondaparticularagentforaspecicrequirement,itrstrequeststhelistofcapableagentsfromtheyellowpagesagent(YP).
Fromthislist,RAthennegotiateswitheachoftheagentsinordertondthemostsuitablecandidate.
Tominimisethetimespentonthisprocess,wedecidedtodevelopanegotiationmodelthatpermitsmultiplecon-currentnegotiations[15].
Thisconcurrencyalsoenablestheagenttoexaminemorepotentialsolutionsinagiventimeperiodandwehaveshownempirically,thatthisleadstobetterdealsthaneithersinglepartnernegotiations[14].
Specically,thisnegotiationmodeladoptsaheuristicapproachinwhichnegotiationbehaviourisdeterminedbyanumberoftacticsdeterminedbydifferentenvironmentfactorsandbyastrategythatrealizesthisimportanceofthedifferenttactics(cf.
Ref.
[10]).
Themodelconsidersthesituationinwhichthereisoneagent(calledthebuyer)tryingtonegotiateaservicewithanumberofotheragents(calledthesellers).
Thebuyerusesanumberofconcurrentthreads,eachofwhichnegotiateswithaspecicsellerusingaspecicstrategy.
Duringthenegotiation,thebuyertriestocategorisethetypeofselleritisdealingwith.
Basedonthefeedbackfromthesethreads,thebuyermaychangeitsnegotiationstrategyforathread,accordingtothetypeofthecorrespondingseller.
Whenallthenegotiationsterminate,thebuyerselectsthesellerthathasproducedthehighestagreementvalueastheonethatitactuallyconrmsthedealwith.
Turningnowtofutureresearch,anareaofparticularinterestinthisprojectisthatoftrustandreputation.
Wheneverinteractionstakeplacebetweendifferentagents,trustinandreputationofagentaresignicant,especiallyinthecontextofvirtualorganisationsinwhichagentsmustrelyoneachothertoensurecoherentandeffectivebehaviour.
Thoughsomeworkhasbeendoneinthisarea,thefocusonVOshasbeenlimited,withthemajorityadoptingthestanceofassumingcompletetrust,andavoidingtheissue.
However,asdiscussedbyLucketal.
[12],questionsofdeceptionandfraudincommunicationandinteraction,ofassuranceandreputation,andofriskandcondence,arecritical,especiallywhereinteractionstakeplacewithnewpartners.
Infuturework,wewillseektounderstandtherequirementsfortrustandreputationandevaluateexistingmodelswithregardtoidentifyingthespecicneedsofVOs.
Amongthepotentialmechanismsfortrustandreputationarecentralisedrepu-tationsystemscurrentlyusedinthecontextofmarketplaces,andpersonalisedreputationsystemsinsocialnetworks,bothofwhichwillbeexplored.
5.
RelatedworkBecauseofthepotentialeconomicbenetsofVOs,thereisstartingtobeconsiderableresearchinthisarea[4,5,20,21].
Forexample,theNIIIP(NationalIndustrialInformationInfrastructureProtocols),3ProductionPlanningandManage-mentinanExtendedEnterprise(PRODNET)[3]andVirtualEnterpriseGenericApplications(VEGA*)[23]projectsareconcernedwiththedevelopmentofITand/orcooperationplatformsforVOs.
TheNIIIPprojectaimstobuildaninformationinfrastructure,whichsupportsthewholevirtualenterpriselife-cycle.
Specically,itaimstoprovidetechnicalfoundationsfortheimplementationofvirtualenterprises;toestablishanopen,standards-basedsoftwareinfrastructureprotocolthatintegratesheterogeneousanddistributedprocesses,data,andcomputingenvironmentsacrosstheUSmanufacturingbase;toimplementNIIIPfromemerging,existing,anddefactostandardsandsystemtechnologies;andtoaccelerateconsensusonstandardsthatpromotethedeploymentofVEs(NIIIP).
Theotherprojectshavesmallerscopes.
Specically,theVEGAprojectaimstoestablishaninformationinfrastructuretosupport2Aprocessbywhichajointdecisionisreachedbytwoormoreagents.
3http://www.
niiip.
org/.
T.
J.
Normanetal.
/Knowledge-BasedSystems17(2004)103–111109thetechnicalandbusinessoperationsofVEsusinggroup-waretoolsanddistributedarchitectures.
ThePRODNETprojectaimstoprovidefunctionalitiesrelatedtothecreationandmaintenancephases(searchandselectionofpartners,negotiation,contractsawarding,tenderpreparation).
TheaimoftheVEGA*projectistodevelopasoftwaresystemthatsupportssmallandmediumsizedenterprises(SMEs)tosetupandmanagevirtualenterprisesaseasilyandquicklyaspossible.
OtherprojectsaddressparticularaspectsinaspecicphaseoftheVOoperationprocess.
Forexample,MultiagentManufacturingAgileSchedulingSystemsforVirtualEnterprises(MASSYVE)[18]focusesonagilescheduling,X-CITTIC(PlanningandControlSystemforSemiconduc-torVirtualEnterprises)[22]concentratesonplanningandcontrollingandSTEPandtheVirtualEnterprise(SAVE)4focusesondatamodellingforVE.
Furthermore,earlierresearchinenterprise-widebusinessmanagementsystemshasfocussedonthemanagement(throughautomatednegotiation)ofbusinessprocesseswithinastaticorganisationalstructure—ADEPT[11]—andmodelsandtechniquesforinformationinterchange—KRAFT[17].
6.
ConclusionsAexiblemechanismfortheformationofVOshasbeenpresentedinthispaperthatcombinesconstraintsolving,marketclearingandqualitymodellingtechniques.
Thismodelhasanumberofsignicantadvantages.
First,throughqualitymodellingandtheuseofexpressiverepresentationsofservicepackages,theCONOISEsystemmaybedeployedinrealisticelectroniccommercescenarios.
Second,throughtheuseofstate-of-theartmarketclearingalgorithms,VOsformedbyCONOISEcanbeguaranteedtocontaintheoptimal(orveryclosetotheoptimal)setofagents.
Finally,takeninthecontextofthewiderVOmanagementprocesstheVOformationmechanismpresentedinthispaperrepresentsacriticalelementofaexibleandrobustsolutiontotheproblemofautomatingthemanagementofvirtualorganisations.
AcknowledgementsTheCONOISEprojectisfundedbyBTExact-BritishTelecom'sresearch,technologyandIToperationsbusiness.
References[1]P.
Baptiste,C.
L.
Pape,W.
Nuijten,Constraint-basedscheduling:applyingconstraintprogrammingtoschedulingproblems,In:InternationalSeriesinOperationsResearchandManagementScience,vol.
39,2001.
[2]M.
Burgess,W.
A.
Gray,N.
Fiddian,Establishingataxanomyofqualityforuseininformationltering,In:Proceedingsofthe1996JointInternationalConferenceandSymposiumonLogicProgram-ming,2002.
[3]L.
M.
Camarinha-Matos,H.
Afsarmanesh,in:A.
Molina,A.
Kusiak,J.
Sanchez(Eds.
),Virtualenterprises:lifecyclesupportingtoolsandtechnologies,HandbookofLifeCycleEngineering:Concepts,ModelsandTechnologies,AcademicPublishers,NewYork,1998,pp.
535–571.
[4]L.
M.
Camarinha-Matos,H.
Afsarmanesh(Eds.
),IFIPConferenceProceedings,vol.
153,AcademicPublishers,NewYork,1999.
[5]L.
M.
Camarinha-Matos,H.
Afsarmanesh,R.
J.
Rabelo(Eds.
),IFIPConferenceProceedings,vol.
184,AcademicPublishers,NewYork,2000.
[6]Y.
Caseau,F.
Laburthe,Cumulativeschedulingwithtaskintervals,In:Proceedingsofthe1996JointInternationalConferenceandSymposiumonLogicProgramming,1996,pp.
363–377.
[7]V.
D.
Dang,N.
R.
Jennings,Optimalclearingalgorithmsformulti-unitsingleitemandmulti-unitcombinatorialauctionswithdemand/supplyfunctionbidding,In:ProceedingsoftheFifthInternationalCon-ferenceonElectronicCommerce,2003,pp.
25–30.
[8]V.
D.
Dang,N.
R.
Jennings.
Polynomialalgorithmsforclearingmulti-unitsingle-itemandmulti-unitcombinatorialauctions.
ArticialIntelligence,2004(inpress).
[9]M.
Eso,S.
Ghosh,J.
Kalagnanam,L.
Ladanyi.
Bidevaluationinprocurementauctionswithpiece-wiselinearsupplycurves.
TechnicalReport,IBMResearchReportRC22219,2001.
[10]P.
Faratin.
Automatedservicenegotiationbetweenautonomouscomputationalagents.
PhDthesis,QueenMaryUniversityofLondon,2001.
[11]N.
R.
Jennings,P.
Faratin,T.
J.
Norman,P.
O'Brien,B.
Odgers,Autonomousagentsforbusinessprocessmanagement,InternationalJournalofAppliedArticialIntelligence14(2)(2000)145–189.
[12]M.
Luck,P.
McBurney,C.
Preist,Agenttechnology:enablingnextgenerationcomputing(aroadmapforagentbasedcomputing),AgentLink(2003).
[13]L.
Mui,A.
Halberstadt,M.
Mohtashemi,Notionsofreputationinmulti-agentsystems:areview,In:ProceedingsofFirstInternationalJointConferenceonAutonomousAgentsandMulti-AgentSystems,2002,pp.
280–287.
[14]T.
D.
Nguyen,N.
R.
Jennings,Concurrentbi-lateralnegotiationinagentsystems,In:ProceedingsoftheFourthDEXAWorkshoponE-Negotiations,2003.
[15]T.
D.
Nguyen,N.
R.
Jennings,Aheuristicmodelforconcurrentbi-lateralnegotiationsinincompleteinformationsettings,In:Proceed-ingsoftheEighteenthInternationalJointConferenceonArticialIntelligence,2003,pp.
1467–1469.
[16]S.
A.
Petersen,M.
Gruninger,Anagent-basedmodeltosupporttheformationofvirtualenterprises,In:InternationalICSCSymposiumonMobileAgentsandMulti-agentsinVirtualOrganisationsandE-Commerce,2000.
[17]A.
D.
Preece,K.
Hui,A.
Gray,P.
Marti,T.
Bench-Capon,D.
Jones,Z.
Cui,TheKRAFTarchitectureforknowledgefusionandtransformation,Knowledge-BasedSystems13(2-3)(2000)113–120.
[18]R.
J.
Rabelo,L.
M.
Camarinha-Matos,H.
Afsarmanesh,Multiagentperspectivestoagilescheduling,In:ProceedingsofIEEE/IFIPInternationalConferenceonBalancedAutomationSystems,1998.
[19]T.
Sandholm,S.
Suri,Marketclearability,In:ProceedingsofTheSeventeenthInternationalJointConferenceonArticialIntelligence,2001,pp.
1145–1151.
[20]P.
Sieber,J.
Griese(Eds.
),ProceedingsoftheFirstInternationalVoNetWorkshop,1998.
[21]P.
Sieber,J.
Griese(Eds.
),ProceedingsoftheSecondInternationalVoNetWorkshop,1999.
4http://www.
epmtech.
jotne.
com/newsletter/ew199/5.
html.
T.
J.
Normanetal.
/Knowledge-BasedSystems17(2004)103–111110[22]A.
L.
Soares,J.
P.
deSousa,A.
L.
Azevedo,J.
A.
Bastos.
Usinganinformalontologyinthedevelopmentofaplanningandcontrolsystem-thecaseofthevirtualenterprise.
TechnicalReport,INESCPorto.
,1996.
[23]B.
Suter,TheVEGA*cooperationplatform:providingrealsupportforvirtualenterprises,In:SieberandGriese,1999.
[24]P.
R.
Wurman,Dynamicpricinginthevirtualmarketplace,IEEEInternetComputing5(2)(2001)36–42.
[25]B.
Yu,M.
Singh,Anevidentialmodelofdistributedreputa-tionmanagement,In:ProceedingsofFirstInternationalJointConferenceonAutonomousAgentsandMulti-AgentSystems,2002,pp.
294–301.
T.
J.
Normanetal.
/Knowledge-BasedSystems17(2004)103–111111