计算机科学 ›› 2015, Vol. 42 ›› Issue (7): 95-98.doi: 10.11896/j.issn.1002-137X.2015.07.020

• 2014’全国理论计算机科学年会 • 上一篇    下一篇

分布式交互应用中服务器放置问题的启发式算法

郑晶晶 张 晶 武继刚   

  1. 天津工业大学计算机科学与软件学院 天津300387
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受教育部高校博士点基金课题(20131201110002),国家自然科学基金天元青年基金(11326211)资助

Heuristic Algorithm for Server Placement in Distributed Interactive Applications

ZHENG Jing-jing ZHANG Jing WU Ji-gang   

  • Online:2018-11-14 Published:2018-11-14

摘要: 分布式交互应用是允许分散在不同地点的多个参与者能实时进行交互的网络系统,它的交互质量在很大程度上取决于网络延迟,而通过对服务器位置的合理布局可以降低网络延迟。因此,服务器放置是影响分布式交互应用的交互性能的关键因素。针对分布式交互应用中服务器放置问题,提出了模拟退火算法和禁忌搜索算法,并与已有的遗传算法进行了比较。通过实验可以看出,尽管在求得较好解的速度方面,遗传算法占据优势,但在求得解的质量方面,提出的模拟退火算法和禁忌搜索算法均优于遗传算法,在服务器数量相同的条件下,延迟平均降低了15.5%和15.2%,更加有效地提高了交互质量。

关键词: 分布式交互应用,服务器放置,遗传算法,模拟退火算法,禁忌搜索算法

Abstract: Distributed interactive applications(DIAs) are networked systems that allow multiple participants at different locations to interact with each other in real time.The interaction quality heavily depends on network latencies which can be reduced by reasonable distribution of location where the servers of the DIAs are placed.Thus,the placement of ser-vers is a key factor to the interactivity performance of DIAs.The simulated annealing algorithm and tabu search algorithm were used to solve the server placement problem in this paper.Then these two algorithms were compared with genetic algorithm.The experiment results show that the genetic algorithm is much faster in the speed of obtaining a better solution,but simulated annealing algorithm and tabu search algorithm outperform genetic algorithm in the quality of the solution and obtain average latency reduction of 15.5% and 15.2% respectively for the same number of server,which effectively improve the quality of the interaction.

Key words: Distributed interactive application,Server placement,Genetic algorithm,Simulated annealing algorithm,Tabu search algorithm

[1] Webb S D,Soh S,Lau W.Enhanced mirrored servers for network games[C]∥Proceedings of the 6th ACM SIGCOMM Workshop on Network and System Support for Games.2007:117-122
[2] Ahmad L,Boukerche A,Hamidi A A,et al.Web-based e-lear-ning in 3D large scale distributed interactive simulations using HLA/RTI[C]∥Proceedings of IEEE International Conference on IPDPS.2008:1-4
[3] Bouras C,Philopoulos A,Tsiatsos T.e-Learning through distributed virtual environments[J].Network and Computer Applications,2001,4(3):175-199
[4] Beigbeder T,Coughlan R,Lusher C,et al.The effects of loss and latency on user performance in unreal tournament[C]∥Proceedings of the 3rd Workshop on Network and System Support for Games.2004:144-151
[5] Delaney D,Ward T,McLoone S.On consistency and network latency in distributed interactive applications [J].A survey-Part I.Presence:Teleoperators & Virtual Environments,2006,5(2):218-234
[6] Briceno L D,Siegel H J,Maciejewski A A,et al.Robust resource allocation in a massive multiplayer online gaming environment[C]∥Proceedings of the 4th International Conference on Foundations of Digital Games.2009:232-239
[7] Cronin E,Filstrup B,Kurc A R.A distributed mutiplayer game server system[R].Technical report,University of Michigan,2001
[8] Jay C,Glencross M,Hubbold R.Modeling the effects of delayed haptic and visual feedback in a collaborative virtual environment[J].ACM Transaction on Computer-Human Interaction,2007,4(2):1-31
[9] Lee K-W,Ko B-J,Seraphin Calo.Adaptive server selection for large scale interactive online games[J].Computer Networks,2005,9(1):84-102
[10] Laoutaris N,Smaragdakis G,Oikonomou K.Distributed place-ment of service facilities in largescale networks[C]∥Procee-dings of IEEE nternational Conference on INFOCOM.2007:2144-2152(下转第121页)(上接第98页)
[11] Zhang Lu,Tang Xue-yan.Client assignment for improving interactivity in distributed interactive applications[C]∥Proceedings of IEEE international Conference on INFOCOM.2001:3227-3235
[12] Zhang Lu,Tang Xue-yan.The client assignment problem forcontinuous distributed interactive applications[C]∥Proceedings of IEEE Conference on ICDCS.2001:203-214
[13] Zhen Han-ying,Tang Xue-yan.An Enhanced Genetic Algorithm for Server Placement in Distributed Interactive Applications[C]∥Proceedings of IEEE Conference on Parallel and Distributed Systems.2012:596-603
[14] Gelfand S B,Mitter S K.Analysis of simulated anneling for optimization[J].Decision and Control,1985,4(1)
[15] Rolland E,Schilling D A,Current J R.An efficient tabu search procedure for the p-Median problem[J].European Journal of Operational Research,1997,96(2):329-342

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!