网络服务选址问题研究

分类号学号M200973427学校代码10487密级硕士学位论文网络服务选址问题研究学位申请人：孙东方学科专业：管理科学与工程指导教师：杨超教授答辩日期：2011年12月26日AThesisSubmittedinPartialFulfillmentoftheRequirementsfortheMasterDegreeofManagementAResearchontheWebServiceLocationProblemCandidate:SunDongfangMajor:ManagementScienceandEngineeringSupervisor:Prof.YangChaoHuazhongUniversityofScienceandTechnologyWuhan,Hubei430074,P.R.ChinaDecember,2011独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在_____年解密后适用本授权书。不保密□。(请在以上方框内打“√”)学位论文作者签名：指导教师签名：日期：年月日日期：年月日本论文属于华中科技大学硕士学位论文I摘要随着互联网技术的发展，网络服务(WebService)整体响应时间(ResponseTime)中网络延时(NetworkLatency)所占比重越来越大。在网络服务应用范围不断扩大，人们对其响应时间要求却越来越高的情况下，如何对网络服务进行合理选址，从而降低总体响应时间,提高网络服务的服务水平显得尤为重要。本文重点从响应时间的角度对网络服务选址问题进行了研究，因为网络服务体系中响应时间是决定服务水平的关键因素。研究中应用选址问题的相关理论并结合网络服务自身特点，提出了基于时间满意度的多服务带容量限制的网络服务选址模型。本文模型在国外相关研究的基础上，分析了网络服务体系的自身特点，结合这些特点进行了模型改进：网络服务需求点(WebServiceRequester，WSR)只能选择一个网络服务提供商(WebServiceProvider，WSP)；增加了网络服务的容量约束；提出了“有效覆盖”的想法，强调了网络服务需求方可以根据自己的服务水平偏好自主选择网络服务。同时还将时间满意度引入目标函数，采用离散的时间满意度函数，与网络服务体系中的分级定价相关联，使得本文的模型不仅更好地贴合了实际应用，也具有了比较好的拓展性。本文问题时NP困难问题，因而采用贪婪算法思想求解，将问题划分为多个子问题后，根据子问题规模较小，使用了贪婪算法和动态规划法相结合的混合算法进行了求解，取得了比较好的求解效果。关键词：网络服务；响应时间；时间满意度；贪婪算法；动态规划华中科技大学硕士学位论文IIAbstractAlongwiththedevelopmentofInternetTechnology,networklatencyistakingupmoreandmoreproportionofoverallresponsetimeofwebservice.Andpeople’sdemandforresponsetimeisgettinghigherandhigherwhilewebapplicationsbasedonwebserviceisexpandingconstantlyintopeople’slifeandwork.Hence,it’sparticularlyimportanttolocatethewebserviceproperlysoastoreducetheoverallresponsetimeandimprovetheservicelevelofwebservice.Inanetworksystembasedonwebservice,theresponsetimeisthekeyfactortoimpacttheservicelevel.Sothispaperfocusedtoresearchthewebservicelocationproblemfromthepointofresponsetime.Giventhefeaturesofwebservice,abrandnewcapacity-constrainedmulti-servicewebservicelocationmodelbasedontimesatisfactionwasproposedbyapplyingtheclassiclocationtheory.Afterareviewofrelatedliterature,locationmodelsforwebserviceusedbeforewereimprovedwithananalysisonthefeaturesofwebservice.Firstly,webservicerequester(WSR)canonlygetwebservicefromonewebserviceprovider(WSR).Secondly,eachtypeofwebservicehasacapacityconstraint.Thirdly,ideaofeffectivecoveragewasputforwardsothattheWSRcanchoosetherightWSPaccordingtoWSR’sservicelevelpreference.Moreover,timesatisfactionwasintroducedintothefinalmodel,whichnotonlymakesthemodelclosetopracticalapplication,butalsogivesitbetterexpansibility.ThismodelisaNP-Hardproblem,sobyusingGreedyAlgorithm,thisproblemwasdividedintosomemuchsmallersub-problems.Finally,ahybridalgorithmcombiningtheGreedyAlgorithmandDynamicProgrammingwasusedtosolvetheproblem,andtheresultshowedgoodefficiencyandaccuracy.Keywords:WebService;ResponseTime;Time-satisfaction;GreedyAlgorithm;DynamicProgramming华中科技大学硕士学位论文III目录摘要.....................................................IAbstract..................................................II目录..................................................III1.绪论1.1.研究背景与意义.........................................11.2.国内外研究综述.........................................51.3.论文框架与研究内容.....................................92.一般选址问题相关理论综述2.1.一般选址问题介绍......................................112.2.基本覆盖选址问题及常用算法介绍........................132.3.覆盖选址问题中时间满意度的度量.........错误!未定义书签。3.WS选址问题及模型构建3.1.WS体系介绍...........................................183.2.WS选址问题基础模型....................................193.3.基于时间满意度的带容量限制多服务WS选址模型...........244.WS选址模型求解华中科技大学硕士学位论文IV4.1.模型分析及算法设计....................................324.2.算例验证..............................................384.3.结论..................................................425总结与展望5.1全文总结..............................................435.2研究展望..............................................44参考文献..................................................46附录2攻读学位期间参加的科研课题.........................50华中科技大学硕士学位论文11绪论1.1研究背景与意义1.1.1研究背景近年来，随着电子商务(E-commence)的迅速崛起和“云计算”(CloudComputing)概念的提出到开始逐步进入商务应用，基于网络的应用(Web-basedApplication)从集中式演变为分布式，从局部化演变为全球化，，使得需要强大处理能力的大规模的商务应用成为可能。WS(WebService，后面简称WS)不仅是一种创新的web应用模式，也是一个全新的分布式计算模型，是web上数据和信息集成的有效机制，从其诞生之日起就受到了业内人士的追捧，而各种各样的WS技术也层出不穷。表1.1：服务，数据来源于中国气象局~/WeatherWebService.asmx?disco/WeatherWebService.asmx?wsdlIP地址来源搜索WEB服务~/IpAddressSearchWebService.asmx?disco~/IpAddressSearchWebService.asmx?wsdlEmail电子邮件地址验证WEB服务~/ValidateEmailWebService.asmx?disco~/ValidateEmailWebService.asmx?wsdl中文简体字-繁体字转换WEB服务~/TraditionalSimplifiedWebService.asmx?disco~/TraditionalSimplifiedWebService.asmx?wsdl中文-英文双向翻译WEB服务~/TranslatorWebService.asmx?disco/TranslatorWebService.asmx?wsdl火车时刻表WEB服务~/TrainTimeWebService.asmx?disco~/TrainTimeWebService.asmx?wsdl中国股票行情数据WEB服务~/ChinaStockWebService.asmx?disco~/ChinaStockWebService.asmx?wsdl即时外汇汇率数据WEB服务~/ExchangeRateWe