A Research On The Web Service Location Problem

Along with the development of Internet Technology, network latency is taking up moreand more proportion of overall response time of web service. And people’s demand forresponse time is getting higher and higher while web applications based on web service isexpanding constantly into people’s life and work. Hence, it’s particularly important to locatethe web service properly so as to reduce the overall response time and improve the servicelevel of web service.In a network system based on web service, the response time is the key factor to impactthe service level. So this paper focused to research the web service location problem from thepoint of response time. Given the features of web service, a brand new capacity-constrainedmulti-service web service location model based on time satisfaction was proposed byapplying the classic location theory. After a review of related literature, location models forweb service used before were improved with an analysis on the features of web service.Firstly, web service requester (WSR) can only get web service from one web serviceprovider (WSR). Secondly, each type of web service has a capacity constraint. Thirdly, ideaof "effective coverage was put forward so that the WSR can choose the right WSP accordingto WSR’s service level preference. Moreover, time satisfaction was introduced in to the finalmodel, which not only makes the model close to practical application, but also gives it betterexpansibility. This model is a NP-Hard problem, so by using Greedy Algorithm, this problemwas divided into some much smaller sub-problems. Finally, a hybrid algorithm combiningthe Greedy Algorithm and Dynamic Programming was used to solve the problem, and theresult showed good efficiency and accuracy.