资源描述：
《kil-dissertation》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ThePennsylvaniaStateUniversityTheGraduateSchoolEFFICIENTWEBSERVICECOMPOSITION:FROMSIGNATURE-LEVELTOBEHAVIORALDESCRIPTION-LEVELADissertationinComputerScienceandEngineeringbyHyunyoungKil©2010HyunyoungKilSubmittedinPartialFul llmentoftheRequirementsfortheDegreeofDoctorofPhilo
2、sophyDecember2010ThedissertationofHyunyoungKilwasreviewedandapproved∗bythefollowing:DongwonLeeAssociateProfessorofInformationSciencesandTechnologyDissertationAdvisor,ChairofCommitteeSoundarKumaraProfessorofIndustrialEngineeringSwaratChaudhuriAssistantProfessorofComputerSci
3、enceandEngineeringAeJaYeeAssociateProfessorofMathematicsRajAcharyaProfessorofComputerScienceandEngineeringHeadoftheDepartmentofComputerScienceandEngineering∗Signaturesareon leintheGraduateSchool.AbstractWebservicesaresoftwaresystemsdesignedtosupportmachine-to-machineinter-
4、operationovertheWeb.Manyresearcheshavebeencarriedoutforwebservicestandards,andthesee ortshavesigni cantlyimprovedfunctionalitiesofServiceOrientedArchitecture(SOA)signi cantly.However,therestillremainanumberofresearchchallenges.Oneoftheremainingchallengesisthewebservicecomp
5、osition(WSC)problem,i.e.,whenasinglewebservicedoesnotsatisfyagivenrequire-ment,onewantstoautomaticallycombinewebservicestosatisfytherequiremententirely.Inthisdissertation,wetacklethisWSCprobleminthreelevels,i.e.,asignaturelevel,abehaviordescriptionlevelandaQoSdescriptionle
6、velbasedonwebservicedescriptions.First,forasignature-levelapproachwhereeachwebserviceisdescribedbyitssignatureinWSDL,we rstanalyzethetopologicallandscapeofawebservicenet-workformedbyreal-worldwebservices.WethenproposeaSAT-basedalgorithmbasedontheanalysis.Second,forwebservi
7、cesthatprovidebehavioraldescriptionsinadditiontosignatures,we rstde nearealisticmodelfortheWSCproblem,andinvestigatethecomputationalcomplexitiesforthecompositionofwebservicesonrestricted(i.e.,withfullobservation)andgeneralcases(i.e.,withpartialobservation).Wethenprovethatt
8、heWSCproblemwithfullobservationisEXP-hardandtheWSCproblemwithpartialobservationis2-EXP-ha
