Document Type : Original Research Paper

Authors

Imam Khomeini International University, Qazvin, Iran

Abstract

This paper deals with the problem of user-server assignment in online social network systems. Online social network applications such as Facebook, Twitter, or Instagram are built on an infrastructure of servers that enables them to communicate with each other. A key factor that determines the facility of communication between the users and the servers is the Expected Transmission Time (ETT). A smart user-server assignment can avoid the low quality links and improve the communication between nodes and also save the valuable communication resources. Unfortunately, finding the optimal assignment turns out to be a NP-hard problem. This paper proposes the use of a heuristic algorithm named Centralized Simulated Annealing (CSA) to get a good near optimum solution for this problem. Simulation results of this investigation show that using a relatively small number of iterations, this approach achieves a very good performance improvement. On the other hand, the average number of iterations needed to achieve the near-optimal solution, will be slightly increased when the number of users in the network increase.

Keywords

[1] A. Lakshman, P. Malik, "Cassandra: A decentralized structured," ACM SIGOPS Oper. Syst. Rev., vol. 44, no. [Online]. Available: http://doi.acm.org/10.1145/, pp. 35–40, Apr. 2010.

[2] K. Lee, M. El-Sharkawi, "Fundamentals of simulated annealing in modern heuristic optimization techniques: Theory and applications to power sSystems," Wiley-IEEE Press, 2008, pp. 123 - 146.

[3] R. Michael Garey, S. David Johnson, "Computers and intractability: A guide to the theory of NP-completeness," New York, NY, USA: W. H. Freeman & Co, 1979. [4] B. W. Kernighan , S. Lin, "An efficient heuristic procedure for partitioning graphs," Bell Syst. Tech. J, vol. 49, no. 2, pp. 291– 307, 1970.

[5] C. M. Fiduccia, R. M. Mattheyses, "A linear-time heuristic for improving network partitions," in Proc. 19th Design Automation Conference, pp. 175-181, 1982.

[6] Z. Wu, R. Leahy, "An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation," IEEE Trans. Pattern Anal. Mach. Intell, vol. 15, no. 11, pp. 1101– 1113, Nov. 1993.

[7] J. Shi, J. Malik, "Normalized cuts and image segmentation," IEEE Trans. Pattern Anal. Mach. Intell, vol. 22, no. 8, pp. 888–905, Aug. 2000.

[8] I. S. Dhillon, Y. Guan, and B. Kulis, "Weighted graph cuts without eigenvectors a multilevel approach," IEEE Trans. Pattern Anal. Mach. Intell, vol. 29, no. 11, pp. 1944–1957, Nov. 2007.

[9] B. Schölkopf, A. Smola, and K.-R. Müller, "Nonlinear component analysis," Neural Comput, vol. 10, no. 5, pp. 1299-1319, 1998.

[10] C. H. Q. Ding, X. He, H. Zha, M. Gu, and H. D. Simon, "‘A minmax cut," in Proc. IEEEInt. Conf. Data Mining (ICDM), pp. 107– 114, Dec. 2001.

[11] H. S. Stone, "Multiprocessor scheduling with the aid of network flow algorithms," IEEE Trans. Softw. Eng, vol. SE-3, no. 1, pp. 85–93, Jan. 1977.

[12] G. Sabin, V. Sahasrabudhe, and P. Sadayappan, "On fairness in distributed job scheduling across multiple sites," in Proc. IEEE Int. Conf. Cluster comput, pp. 35–44, Sep. 2004.

[13] D. P. Vidyarthi, B. K. Sarker, A. K. Tripathi, and L. T. Yang, "Scheduling in distributed computing systems: Analysis, design and models," Berlon, Germany: Springer Publishing Company, Incorporated, 2008.

[14] Y. Jiang, Y. Zhou, and W. Wang, "Task allocation for undependable multiagent systems in social networks," IEEE Trans. Parallel Distrib. Syst., vol. 24, no. 8, pp. 1671–1681, Aug. 2013.

[15] Y. Jiang, J. Jiang, "Contextual resource negotiation-based task allocation and load balancing in complex software systems," IEEE Trans. Parallel Distrib. Syst., vol. 20, no. 5, pp. 641–653, May. 2009.

[16] D. S. J. D. Couto, "High-throughput routing for multi-hop wireless networks," Ph.D. dissertation, Dept. Elect. Eng. Comput. Sci., 2004.

[17] C. A. Chen, M. Won,R. Stoleru, and G. G. Xie, "Energy-Efficient Fault-Tolerant Data Storage and Processing in Mobile Cloud," IEEE Trans. on cloud computing, vol. 3, no. 1, pp. 28 - 41, January. 2015.

[18] S. Kirkpatrick, M. P. Vecchi, "Optimization by simmulated annealing," Science, vol. 220, no. 4598, pp. 671–680, 1983.

[19] D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, "Part I, graph partitioning," Elsevier Science B.V., vol. 37, no. 6, pp. 865–892, June. 1998.


LETTERS TO EDITOR

Journal of Electrical and Computer Engineering Innovations (JECEI) welcomes letters to the editor for the post-publication discussions and corrections which allows debate post publication on its site, through the Letters to Editor. Letters pertaining to manuscript published in JECEI should be sent to the editorial office of JECEI within three months of either online publication or before printed publication, except for critiques of original research. Following points are to be considering before sending the letters (comments) to the editor.


[1] Letters that include statements of statistics, facts, research, or theories should include appropriate references, although more than three are discouraged.

[2] Letters that are personal attacks on an author rather than thoughtful criticism of the author’s ideas will not be considered for publication.

[3] Letters can be no more than 300 words in length.

[4] Letter writers should include a statement at the beginning of the letter stating that it is being submitted either for publication or not.

[5] Anonymous letters will not be considered.

[6] Letter writers must include their city and state of residence or work.

[7] Letters will be edited for clarity and length.

CAPTCHA Image