Computer Science ›› 2018, Vol. 45 ›› Issue (4): 60-65.doi: 10.11896/j.issn.1002-137X.2018.04.008

Previous Articles     Next Articles

Edge Cloud Clustering Algorithm Based on Maximal Clique

ZHU Jin-bin, WU Ji-gang and SUI Xiu-feng   

  • Online:2018-04-15 Published:2018-05-11

Abstract: Effective combination of edge clouds can offer more powerful computing capacity,which is a promising research direction in cloud computing.It is a challenging work to select multiple edge clouds to combine,because a bad strategy will make a negative impact on the computational power of the obtained group.The problem is generally modeled as a resource topology graph in which cloud nodes are represented as vertices,and the links between nodes are represented as edges.The selection of edge cloud is equivalent to subgraph extraction of the resource topology graph,and this is a typical NP problem.The current minStar algorithm extracts the subgraph with the smallest communication delay between nodes,and then assigns the corresponding resources to the customer.It is a greedy strategy,resulting in local optimal and poor global performance.The proposed algorithm based on maximal clique divides maximal cliques into several smaller but complete subgraphs which do not overlap each other,then constructs resource block in unit of complete subgraph,and assigns the cloud resource in unit of resource block.Compared with minStar algorithm,simulation results show that the global maximum communication delay is reduced by 50% with the proposed algorithm.

Key words: Edge cloud,Cloud combination,Maximal clique,Resource block,Global optimization

[1] FOSTER I,ZHAO Y,RAICU I,et al.Cloud computing and grid computing 360-degree compared[C]∥Proceedings of the Grid Computing Environments Workshop.Piscataway,NJ:IEEE,2008:1-10.
[2] STANOEVSKA-SLABEVA K,WOZNIAK T.Grid and CloudComputing:Cloud Basics-An Introduction to Cloud Computing[M].Berlin:Springer,2010:47-61.
[3] ZHANG Q,CHENG L,BOUTABA R.Cloud Computing:State-of-the-Art and Research Challenges[J].Journal of Internet Services and Applications,2010,1(1):7-18.
[4] MARSTON S,LI Z,BANDYOPADHYAY S,et al.Cloud Computing—The Business Perspective[C]∥Proceedings of the 47th Hawaii International Conference on System Sciences.New York:ACM,2011:1-11.
[5] GIURGIU I,RIVA O,JURIC D,et al.Calling the Cloud:Enabling Mobile Phones as Interfaces to Cloud Applications[C]∥Proceedings of the 10th ACM/IFIP/USENIX International Conference on Middleware.New York:Springer,2009:83-102.
[6] SATYANARAYANAN M,BAHL P,CACERES R,et al.The Case for Vm-Based Cloudlets in Mobile Computing[J].IEEE Pervasive Computing,2009,8(4):14-23.
[7] VERBELEN T,SIMOENS P,DE TURCK F,et al.Cloudlets:Bringing the Cloud to the Mobile User[C]∥Proceedings of the third ACM Workshop on Mobile Cloud Computing and Ser-vices.New York:ACM,2012:29-36.
[8] PAL R,LIN S H,GOLUBCHIK L.The Cloudlet Bazaar Dynamic Markets for the Small Cloud[J/OL].[2017-05-25] .https://arxiv.org/pdf/1704.00845.pdf.
[9] LI C L,LIU Y P,LUO Y L.QoS-Based Resource Allocation Across Local and Public Cloud for Resource-Constrained Mobile Device[J].Transaction on Emerging Telecommunications Technologies,2016,28(5):e3126.
[10] FERREIRA L L,ALBANO M,DELSING J.QoS-as-a-Service in the Local Cloud[C]∥Proceedings of the 21st International Conference on Emerging Technologies and Factory Automation(ETFA’16).Piscataway,NJ:IEEE,2016.
[11] OTHMAN M,MADANI S A,KHAN S U.A Survey of Mobile Cloud Computing Application Models[J].IEEE Communications Surveys & Tutorials,2014,16(1):393-413.
[12] LIU W Q,CAO J N,QIU X J,et al.Improving Performance of Mobile Interactive Data-Streaming Applications With Multiple Cloudlets[C]∥Proceedings of IEEE International Conference on Cloud Computing Technology and Science.Piscataway,NJ:IEEE,2014:46-53.
[13] ALICHERRY M,LAKSHMAN T V.Network Aware Resource Allocation in Distributed Clouds[C]∥Proceedings of the 31st Annual IEEE International Conference on Computer Communications(IEEE INFOCOM 2012).Piscataway,NJ:IEEE,2012:963-971.
[14] GAO R F,WU J,LAM S K,et al.Reducing Access Latency in Virtual Machine Assignments[C]∥Proceedings of the 2nd International Conference on Data Science and Systems.Piscata-way,NJ:IEEE,2016:616-622.
[15] JIA M,LIANG W F,XU Z C,et al.Cloudlet Load Balancing in Wireless Metropolitan Area Networks[C]∥Proceedings of the 35st Annual IEEE International Conference on Computer Communications(IEEE INFOCOM 2016).Piscataway,NJ:IEEE,2016:1-9.
[16] YAO Y,CAO J,LI M L.Network-Aware Virtual Machine Allocation in Cloud Datacenter[C]∥Proceedings of the 13th IFIP International Conference on Network and Parallel Computing(NPC’13).Berlin:Springer,2013:71-82.
[17] SHIN J Y,WONG B,SIRER E G.Small-world datacenters[C]∥Proceedings of the 2nd ACM Symposium on Cloud Computing.New York:ACM,2011.
[18] CESELLI A,PREMOLI M,SECCI S.Mobile Edge Cloud Network Design Optimization[J].IEEE/ACM Transactions on Networking,2017,PP(99):1-14.
[19] BONOMI F,MILITO R,ZHU J,et al.Fog Computing and Its Role in the Internet of Things[C]∥Proceedings of the first Edition of the MCC Workshop on Mobile Cloud Computing(MCC’12).New York:ACM,2012:13-16.
[20] CHUN B G,IHM S,MANIATIS P,et al.CloneCloud:Elastic Execution Between Mobile Device and Cloud[C]∥Proceedings of the 6th Conference on Computer Systems.New York:ACM,2011:301-314.
[21] ZHANG W W,WEN Y G,WU D O.Collaborative Task Execution in Mobile Cloud Computing Under a Stochastic Wireless Channel[J].IEEE Transactions on Wireless Communications,2015,14(1):81-93.
[22] NIRJON S,LIU J,DEJEAN G,et al.COIN-GPS:Indoor Localization From Direct GPS Receiving[C]∥Proceedings of the 12th Annual International Conference on Mobile Systems,Applications and Services.New York:ACM,2014:301-314.
[23] CHOW R,JAKOBSSON M,MASUOKA R,et al.Authentication in the Clouds:A Framework and Its Application to Mobile Users[C]∥Proceedings of the 2010 ACM Workshop on Cloud Computing Security Workshop(CCSW’10).2010:1-6.
[24] TOMITA E,TANAKA A,TAKAHASHI H.The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments[J].Theoretical Computer Science,2006,363(1):28-42.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .