《网络服务选址问题研究.pdf》由会员分享，可在线阅读，更多相关《网络服务选址问题研究.pdf（57页珍藏版）》请在金锄头文库上搜索。
1、分 类分 类 号号 学号学号 M200973427 学校代码学校代码 1 0 4 8 7 密级密级 硕士学位论文硕士学位论文 网络服务网络服务选址问题研究选址问题研究 学位申 请人学位申 请人 ： 孙东方孙东方 学 科 专 业学 科 专 业 ： 管理科学与工程管理科学与工程 指 导 教 师指 导 教 师 ： 杨超杨超 教授教授 答 辩 日 期答 辩 日 期 ： 2011 年年 12 月月 26 日日 A Thesis Submitted in Partial Fulfillment of the Requirements for the Master Degree of Management
2、A Research on the Web Service Location Problem Candidate : Sun Dongfang Major : Management Science and Engineering Supervisor : Prof. Yang Chao Huazhong University of Science and Technology Wuhan, Hubei 430074, P. R. China December, 2011 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明
3、引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密，在_年解密后适用本授权书。 不保密。 (请在
4、以上方框内打“”) 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本论文属 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 I 摘摘 要要 随着互联网技术的发展，网络服务(Web Service)整体响应时间(Response Time) 中网络延时(Network Latency)所占比重越来越大。在网络服务应用范围不断扩大，人 们对其响应时间要求却越来越高的情况下，如何对网络服务进行合理选址，从而降 低总体响应时间,提高网络服务的服务水平显得尤为重要。 本文重点从响应时间的角度对网络服务选址问题进行了研究，因为网络服务体 系中响应时间是
5、决定服务水平的关键因素。研究中应用选址问题的相关理论并结合 网络服务自身特点，提出了基于时间满意度的多服务带容量限制的网络服务选址模 型。本文模型在国外相关研究的基础上，分析了网络服务体系的自身特点，结合这 些特点进行了模型改进：网络服务需求点(Web Service Requester，WSR)只能选择一 个网络服务提供商(Web Service Provider，WSP)；增加了网络服务的容量约束；提出 了“有效覆盖”的想法，强调了网络服务需求方可以根据自己的服务水平偏好自主 选择网络服务。同时还将时间满意度引入目标函数，采用离散的时间满意度函数， 与网络服务体系中的分级定价相关联，使得本
6、文的模型不仅更好地贴合了实际应用， 也具有了比较好的拓展性。本文问题时 NP 困难问题，因而采用贪婪算法思想求解， 将问题划分为多个子问题后，根据子问题规模较小，使用了贪婪算法和动态规划法 相结合的混合算法进行了求解，取得了比较好的求解效果。 关键词关键词：网络服务；响应时间；时间满意度；贪婪算法；动态规划 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 II Abstract Along with the development of Internet Technology, network latency is taking up more and more pro
7、portion of overall response time of web service. And peoples demand for response time is getting higher and higher while web applications based on web service is expanding constantly into peoples life and work. Hence, its particularly important to locate the web service properly so as to reduce the
8、overall response time and improve the service level of web service. In a network system based on web service, the response time is the key factor to impact the service level. So this paper focused to research the web service location problem from the point of response time. Given the features of web
9、 service, a brand new capacity-constrained multi-service web service location model based on time satisfaction was proposed by applying the classic location theory. After a review of related literature, location models for web service used before were improved with an analysis on the features of web
10、 service. Firstly, web service requester (WSR) can only get web service from one web service provider (WSR). Secondly, each type of web service has a capacity constraint. Thirdly, idea of “effective coverage was put forward so that the WSR can choose the right WSP according to WSRs service level pre
11、ference. Moreover, time satisfaction was introduced in to the final model, which not only makes the model close to practical application, but also gives it better expansibility. This model is a NP-Hard problem, so by using Greedy Algorithm, this problem was divided into some much smaller sub-problem
12、s. Finally, a hybrid algorithm combining the Greedy Algorithm and Dynamic Programming was used to solve the problem, and the result showed good efficiency and accuracy. Keywords: Web Service; Response Time; Time-satisfaction; Greedy Algorithm; Dynamic Programming 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文
13、III 目目 录录 摘摘 要要 I I AbstractAbstract IIII 目目 录录 IIIIII 1.1. 绪论绪论 1.1. 研究背景与意义 . 1 1.2. 国内外研究综述 . 5 1.3. 论文框架与研究内容 . 9 2.2. 一般选址问题相关理论综述一般选址问题相关理论综述 2.1. 一般选址问题介绍 11 2.2. 基本覆盖选址问题及常用算法介绍 13 2.3. 覆盖选址问题中时间满意度的度量 . 错误错误! !未定义书签。未定义书签。 3.3. WSWS 选址问题及模型构建选址问题及模型构建 3.1. WS 体系介绍 . 18 3.2. WS 选址问题基础模型 19 3
14、.3. 基于时间满意度的带容量限制多服务 WS 选址模型 . 24 4.4. WSWS 选址模型求解选址模型求解 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 IV 4.1. 模型分析及算法设计 32 4.2. 算例验证 38 4.3. 结论 42 5 5 总结与展望总结与展望 5.1 全文总结 43 5.2 研究展望 44 参考文献参考文献 4646 附录附录 2 2 攻读学位期间参加的科研课题攻读学位期间参加的科研课题 5050 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 1 1 绪论绪论 1.1 研究背景与意义研究背景与意义 1.1.
15、1 研究背景研究背景 近年来，随着电子商务(E-commence)的迅速崛起和“云计算”(Cloud Computing) 概念的提出到开始逐步进入商务应用，基于网络的应用(Web-based Application) 从集 中式演变为分布式，从局部化演变为全球化， ，使得需要强大处理能力的大规模的商 务应用成为可能。WS(Web Service，后面简称 WS)不仅是一种创新的 web 应用模式， 也是一个全新的分布式计算模型，是 web 上数据和信息集成的有效机制，从其诞生 之日起就受到了业内人士的追捧，而各种各样的 WS 技术也层出不穷。 表表 1.1： 网站网站提供的部分提供的部分 w
16、eb service 服务名称服务名称 服务发现服务发现 服务描述服务描述 天气预报 Web 服务，数据来源于中国气象局 /WeatherWebService.asmx?disco /WeatherWebService.asmx?wsdl IP 地址来源搜索 WEB 服务 /IpAddressSearchWebService.as mx?disco /IpAddressSearchWebService.as mx?wsdl Email 电子邮件地址验证 WEB 服务 /ValidateEmailWebService.asmx ?disco /ValidateEmailWebService.asm x?wsdl 中文简体字 繁体字转换 WEB 服务 /TraditionalSimplifiedWebServic e.asmx?disco /TraditionalSimp
