Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Ad hoc cloudlet based mobile gaming : progressive downloading and cooperative task allocation Chi, FangYuan 2015

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2015_november_chi_fangyuan.pdf [ 1.97MB ]
Metadata
JSON: 24-1.0167800.json
JSON-LD: 24-1.0167800-ld.json
RDF/XML (Pretty): 24-1.0167800-rdf.xml
RDF/JSON: 24-1.0167800-rdf.json
Turtle: 24-1.0167800-turtle.txt
N-Triples: 24-1.0167800-rdf-ntriples.txt
Original Record: 24-1.0167800-source.json
Full Text
24-1.0167800-fulltext.txt
Citation
24-1.0167800.ris

Full Text

Ad hoc Cloudlet Based Mobile Gaming:Progressive Downloading and CooperativeTask AllocationbyFangYuan ChiB.A.Sc., The University of British Columbia, 2012A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)October, 2015c© FangYuan Chi 2015AbstractAs the game industry matures, processing complex game logics in a timely manner is no longer aninsurmountable problem. Many researchers are now trying to find ways to optimize the gaming systemregarding the network usage, interactive latency, energy consumption, and local resource utilization.However, current cloud-based mobile gaming solutions are limited by their relatively high requirementson Internet resources. Also, they typically do not consider the geographical locations of nearby mobileusers and thus ignore the potential cooperation among them. Therefore, inspired by existing cloudcomputing techniques, as well as the concept of both cloudlet computing, and ad hoc mobile cloudcomputing, in this thesis, we introduce an ad hoc mobile cloud-cloudlet-cloud based three-tier approachto cooperative mobile gaming architecture. Two types of cooperation will be provided: cooperationwith and without the assistance from the cloudlet(s), which is defined by the way in which mobiledevices are connected to and interact with the cloud. In this thesis, two modules of the architecture areintroduced: 1) progressive game resources download, by which mobile users can adaptively downloadgaming resources from cloud servers or nearby mobile users according to their gaming progresses,and 2) ad hoc mobile cloud based cooperative task allocation, by which gaming components can beexecuted dynamically over local devices, nearby devices, stationary cloudlet(s), or cloud servers. Weformulate the mechanisms for both modules as optimization problems and propose several algorithmsfor both modules, which are later used for evaluation purposes. We carry out simulations based onreal mobility traces, and the results show that our system’s performance depends highly on the ad hocnetwork environments (the more concurrent and balanced connections within the ad hoc network, thelower the system resource usage). Also, regardless of the network environments, our system has lowersystem resource usage while utilizing resources of nearby devices, compared to the cloud-based gamingarchitecture. Moreover, our evaluation results show that by adding cloudlet(s) into our architecture, theiisystem performance is improved. Also, at the end of the thesis, we give a comprehensive analysis of thesystem.iiiPrefaceHereby, I declare that I am the first author of this thesis. Part of this thesis are based on works that havebeen published or submitted for publication. Related publications were done in collaboration with Dr.Xiaofei Wang, Ph.D. Candidate Wei Cai, and Prof. Victor C.M. Leung.In my research, I proposed a three-tier peer-assisted mobile gaming architecture, which integratesboth mobile devices in vicinity and the stationary cloudlet(s) as cooperative processing utilities. Back-ground of related topics are studied; system architecture, system performance, and system overhead arepresented, analyzed, and discussed. To be more specific, two modules are extensively studied: progres-sive downloading and cooperative task allocation, which are then modeled as optimization problems,with algorithms proposed. Also, simulations are carried out to evaluate the system performance andthe results are discussed. All publications were originally prepared by me and further revised by allco-authors. Publications accomplished are listed as follows:• Fangyuan Chi, Xiaofei Wang, Wei Cai, and Victor C.M. Leung, “Ad hoc cloudlet based coopera-tive cloud gaming,” accepted by IEEE Transactions on Cloud Computing, October 2015.• Fangyuan Chi, Xiaofei Wang, Wei Cai, and Victor C.M. Leung, “Ad hoc cloudlet based cooper-ative cloud gaming,” in Proceedings of IEEE 6th International Conference on Cloud ComputingTechnology and Science (CloudCom), Singapore, Dec. 15-18, 2014.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Abbreviation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Mobile Cloud Gaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.1 Video-based Cloud Gaming . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.2 File-based Cloud Gaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.3 Component-based Cloud Gaming . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Motivation and Research Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Related Work and Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.1 Cloudlet(s) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.2 Ad hoc Mobile Cloud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.3 Mobile Social Closeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3.4 Component-based Game Design . . . . . . . . . . . . . . . . . . . . . . . . . 9v1.3.5 Mobile Computation Offloading . . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Contribution of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.5 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.1 Feasibility and Game Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2 Application Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3 Architecture Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Progressive Downloading of Game Resources . . . . . . . . . . . . . . . . . . . . . . . . 223.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.3 Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 Cooperative Task Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.1.1 System Resource Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.1.2 Mobile Social Closeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.3 Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.3.1 System Resource Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.3.2 Mobile Social Closeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.1 System Workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.2 Comparison to Existing Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . 515.3 Overhead and Benefit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59vi6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62viiList of Tables3.1 Evaluation Setup Parameters: Progressive Downloading . . . . . . . . . . . . . . . . . 254.1 System Resource Usage Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.2 Examples of Game Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.3 Algorithm Complexity: Cooperative Task Allocation . . . . . . . . . . . . . . . . . . 404.4 Evaluation Setup Parameters: Cooperative Task Allocation . . . . . . . . . . . . . . . 48viiiList of Figures1.1 Component-based Programming For Game Applications . . . . . . . . . . . . . . . . 41.2 Component-based Game Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.1 Task Dependencies in Game Application . . . . . . . . . . . . . . . . . . . . . . . . . 162.2 Cooperation With and Without the Assistance From The Cloudlet(s) . . . . . . . . . . 183.1 Downloading Progress for Users with Different Game Progression . . . . . . . . . . . 263.2 Progressive Downloading With and Without the Assistance From The Cloudlet(s) . . . 273.3 Progressive Downloading with Map-Based Movement . . . . . . . . . . . . . . . . . 284.1 Pareto Front: A Set of Pareto Optimal Solutions to The System Resource Usage Problem 364.2 Interactive Latency and Energy Costs . . . . . . . . . . . . . . . . . . . . . . . . . . 364.3 Interactive Latency and Bandwidth Consumption . . . . . . . . . . . . . . . . . . . . 364.4 Energy Costs under Different Network Environments . . . . . . . . . . . . . . . . . . 434.5 CPU Utilization under Different Network Environments . . . . . . . . . . . . . . . . 444.6 Storage Utilization under Different Network Environments . . . . . . . . . . . . . . . 454.7 Energy Costs for Various Degree of Skewness and Density . . . . . . . . . . . . . . . 464.8 System Resource Usage With and Without The Assistance From The Cloudlet(s) . . . 474.9 Task Allocation with Mobile Social Closeness for Map-based Movement . . . . . . . . 495.1 System Resource Usage with Map-based Movement . . . . . . . . . . . . . . . . . . . 535.2 Energy Costs with Map-based Movement . . . . . . . . . . . . . . . . . . . . . . . . 545.3 Bandwidth Consumption with Map-based Movement . . . . . . . . . . . . . . . . . . 555.4 Interactive Latency with Map-based Movement . . . . . . . . . . . . . . . . . . . . . 56ix5.5 Overhead and Benefit of the System . . . . . . . . . . . . . . . . . . . . . . . . . . . 57xList of AbbreviationMCG Mobile Cloud GamingMCC Mobile Cloud ComputingQoE Quality of ExperienceQoS Quality of ServiceNPC Non-player CharacterLAN Local Area NetworkWAN Wide Area NetworkAP Access PointMANET Mobile Ad hoc NetworkD2D Device-to-DeviceAI Artificial IntelligenceCPU Central Processing UnitSRPG Strategic Role-playing GamesMMOG Massive Multiplayer Online GamesxiAcknowledgementsI would like to express my sincere gratitude to my advisor Prof. Victor C.M. Leung for his continuoussupport throughout my M.A.Sc study. His patient and immense knowledge guided me through theresearch work and in composing this thesis. I would also like to thank the rest of my thesis committeemembers, Dr. Krishnamurthy and Dr. Nasiopoulos for their encouragement and valuable comments.My sincere thanks goes to my co-authors, Dr. Xiaofei Wang and Ph.D candidate Wei Cai, for theirsupport, help, and precious advise in my search and published works. Also, I thank my fellow students,Ph.D candidate Chunsheng Zhu, Xiuhua Li, and Xiping Hu, for their advises and comments toward myresearch works.Last but not the least, I would like to thank my parents for supporting my search study and life ingeneral. Also, a special thanks to my friends (real game developers), who are able to give me advisesfrom industry’s perspective.xiiChapter 1IntroductionIn this chapter, background of mobile cloud gaming (MCG), and the challenges facing MCG are in-troduced. Motivated by these challenges, we are interested in a three-tier peer-assisted mobile gamingarchitecture, which integrates the ad hoc mobile cloud, stationary cloudlet(s), and the cloud. Thus, inthis chapter, we first introduce the concepts of cloudlet(s) and ad hoc mobile cloud computing, as wellas their applications. Then, we discuss at the end of this chapter the contribution and structure of thisthesis.1.1 Mobile Cloud GamingWith Internet connectivity, mobile games can be played virtually anywhere anytime, which providesa fresh user experience to game players. However, hardware constraints imposed by mobile devicessuch as limited processing capabilities, storage capacities, and relatively short battery lives compromisethe Quality of Experience (QoE) of the mobile gamers. To overcome these limitations, researchers havestarted to consider building game applications upon the concept of Mobile Cloud Computing (MCC) [1].This new gaming architecture, called Mobile Cloud Gaming (MCG) inherits both the advantages and thechallenges of MCC, e.g., unreliable network connectivity, limited network bandwidth, and unpredictablenetwork latency [2]. To explain future, there are three currently existing categories of MCG architecturein the industry and academia: video-based, file-based, and component-based. Each of them employsunique characteristics and challenges, which are discussed in the following sections.11.1.1 Video-based Cloud GamingVideo-based cloud gaming is the most popular and mature architecture in the market. It is also themost conventional one. Very similar to video on demand, video-based cloud gaming uses a thin-clientapproach which has the actual game stored, executed, and rendered by the cloud. Mobile device(s), inthis paradigm, acts merely as an input console, which captures and transmits user inputs to the cloud;receives, decodes, and finally displays the rendered game scenes. This type of cloud gaming is a veryhot topic in both industry and academia. For instance, companies such as Gaikai1 and OnLive2 arepioneers in providing cloud gaming services to end users, whereas authors in [3] have implemented anopen source video-based cloud gaming platform, with the intention to provide a platform for academicresearchers to better understand and evaluate the architecture. The video-based architecture makes thecapability of users’ end devices unimportant since it is the cloud that hosts the actual game, thus freesusers from upgrading their end devices. However, despite the advantages, limitations still exist. Forexample, computation-intensive tasks, combined with the need to render, encode, and transmit the gamescenes in near real-time to the currently connected players make the availability of both cloud servicesand the Internet the most crucial aspects in the design of this type of architecture. Also, the evalua-tion results in measurement studies [4], [5], and [6] indicate that the Quality of Service (QoS) of sucharchitecture depends on the processing and streaming capability of the cloud, as well as the network la-tency rendered by the user-cloud data transmission. Not to mention that it is very bandwidth and energyconsuming for transmitting game video in real-time.1.1.2 File-based Cloud GamingTo alleviate the high demand on Internet resources brought by video-based architecture, companies suchas Kalydo3, Approxy4, and SpawnApps5 have started to consider a new business model by providingfile-based cloud gaming services. Considering the ever-growing capacity of modern mobile devices, this1www.gaikai.com2www.onlive.com3www.kalydo.com4www.approxy.com5www.spawnapps.com2newly developed architecture takes a step back which has the game resources downloaded onto mobiledevices for local execution. To explain further, in file-based architecture, segmented game resources,including game data (e.g., textures, geometry, objects, and non-player character (NPC) metadata) andgame logic (e.g., game rules, scripts, rendering, and network access), are progressively downloaded ontomobile devices. Games are then executed on-device with only a fraction of the total game resourcesdownloaded (e.g., less than 5% of the game), while the downloading for the rest of the game resourcescontinues. Without the necessity to transmit video frames in real-time, this approach provides instantaccess to games and has less network bandwidth consumed as compared with the conventional video-based architecture. However, this approach does not utilize the computing resources in the cloud sincethe games are executed on-device, which means its QoE is still limited by resource constraints of mobiledevices.1.1.3 Component-based Cloud GamingA new architectural design pattern, component-based game architecture, is becoming popular and widelyadopted by game developers over the past years. In component-based architecture, game data is sep-arated from game code-base, and game logic is divided into self-contained, inter-dependent, reusable,as well as remote executable software components. Every object in the game (e.g., vehicles, bullets,etc.) is defined as a game entity. Every entity consists of one or more game components, which definethe behavior and functionalities of the entity. An example of this design pattern is illustrated in Figure1.1. In the example, the game application is constructed by four game components (Position, Render,Move, and Target), and two game entities (Player and Weapon). The functionalities of game entities aredefined by the game components, and the fact that some components co-exist in different game entities(e.g., both game entities named Player and Weapon have game components such as Position and Move)demonstrates the ability for the game components to be reused. Component-based architecture providesincreased system parallelism since it puts together relevant attributes and decouples the functionalitywhich operates on them. Computation task(s), in this design pattern, is defined as an individual functioncall for certain component(s). As the component(s) itself is stateless, it is the task/function parametersthat go into the component(s) which makes the task different from others.3Figure 1.1: Component-based Programming For Game ApplicationsFollowing this definition, a component-based cloud gaming architecture is proposed in [7], which isbased on the assumption that the game components could be executed either in the cloud or the mobiledevices, as determined by different network and execution environments. By monitoring in real-time theexecution environments of the mobile devices and the cloud, this architecture offers a cognitive solutionwhich dynamically partitions the game applications, with the design goal of achieving optimal compo-nent allocation and computation resource utilization of both mobile devices and the cloud. However,this architecture is challenged by the ability of real-time component migration between mobile devicesand the cloud, especially at the beginning of the game session when no game component exists in themobile devices. On the other side, the architecture proposed in [8] allows mobile game users to offloadcomputation-intensive calculation of rendering instructions to a system component called proxy client.This additional system component resides in the edge of the cloud, which is responsible for decouplingthe creation of rendering instructions from their execution and transmitting only the rendering instruc-tions to mobile devices. The evaluation results show that although the network bandwidth usage of thisarchitecture is reduced, the system performance depends highly on the cellular network connectivity,which may be intermittent and costly.1.2 Motivation and Research QuestionsAlthough above-mentioned approaches toward cloud gaming services seem promising, their perfor-mance still depends heavily on the network connectivity between end users’ mobile devices and thedistant cloud. Nevertheless, by enabling worldwide players to request services from the distant cloud4anytime and anywhere, cloud gaming services put a burden on cellular network as it likely to be over-loaded. To alleviate this, potential cooperation among nearby computing devices should be considered.More specifically, as mentioned in [9] resources of nearby mobile devices, namely, their processing aswell as storage capacities, could be pooled together over an ad hoc network to form an ad hoc mobilecloud. Then, users could play games in a cooperative manner, where computation tasks are processedcollaboratively on all neighboring mobile devices instead of solely on the centralized cloud. In addition,traditional cloud gaming architecture does not consider the possibility to deploy stationary cloudlet(s)[2] (i.e., a standalone processing unit that is deployed close to users) at places where users most likelyto play games. Indeed, since people often play games together in coffee shops and social gathering,the idea of enabling cooperation of nearby users and embedding cloudlet(s) at places such as Wi-FiAccess Points and routers to assist mobile users seems promising. Inspired by these ideas, in this thesis,we consider a three-tier peer-assisted approach which takes advantages from the ad hoc mobile cloud,the stationary cloudlet(s), and the centralized cloud. However, this ad hoc mobile cloud-cloudlet-cloudbased architecture has many practical challenges. For instance, it has been identified in [10] that the tasksuccess rate and execution speed of cloudlet computing depend on the cloudlet access probability. Also,in ad hoc mobile cloud based computing, both the connection probability, which is the probability forusers to connect as peers in the ad hoc mobile cloud; as well as the contact duration, which is the timeduration they spend being neighbors, are key dimensions for the computation success rate. Thus, users’behavior and their mobility patterns need to be taken into consideration in such architecture. Then, thequestion is could we apply the ad hoc mobile cloud-cloudlet-cloud architecture in the cloud gamingparadigm? Ideally, the answer is yes: 1) as measured in [11], game players tend to stay in the sameplace, e.g., public facilities, public transportation, and residential areas, for an extended period of timewhile playing games. Thus, with stationary cloudlet(s) deployed in such places, it is safe for us to as-sume that in the local level there is stable device-to-cloudlet connectivity; 2) as indicated in [12], mobilesocial closeness between users could be used as a predictor to users’ mobility patterns. Thus, we believethat by considering the mobile social closeness in the task offloading process, the computation successrate could be ensured. To put it together, aiming at reducing the cloud gaming traffic load for cellularlinks, we are interested in a component and ad hoc mobile cloud-cloudlet(s)-cloud based mobile gaming5architecture which takes users’ mobile social closeness into account.1.3 Related Work and PreliminaryBefore we discuss in detail the contribution of this thesis, related concepts such as cloudlet(s), ad hocmobile cloud, and mobile social closeness will be introduced in this section, as well as their applications.Also, we give an in-depth examination of the component-based design pattern, especially on how itworks in the targeted architecture. At the last, we introduce the currently existing computation offloadingarchitecture.1.3.1 Cloudlet(s)Cloudlet(s) has been introduced and studied in [2], [13] and [14]. As suggested in the literatures,cloudlet(s) is the middle layer of the three-tier network hierarchy (mobile device-cloudlet-cloud), whichis well-connected to both the mobile devices and the distant cloud via a high-speed local area network(LAN) and wide area network (WAN), respectively. Current studies suggest that cloudlet(s) could be in-tegrated with Wi-Fi Access Point (AP), which could be considered as a physical integration of Wi-Fi APand the cloudlet(s). The most well studied method used to deploy cloudlet(s) is hardware virtual machinetechnology [13], which has considerably low hardware and maintenance costs. The purpose/benefit ofbring the cloudlet(s) into the hierarchy is to provide low-latency computation and rich computationalresources. It is a trusted standalone processing unit, could be implemented at places that is closer tousers (as compared to the distant cloud), and often has strong computation power, which is available foruse by connected mobile devices. With the existence of the cloudlet(s), the connectivity between mobiledevices and the cloud could be conducted via the cloudlet(s). Also, mobile devices could offload partof the computation-intensive tasks to the cloudlet(s) instead of totally to the distant cloud, then, reliablecomputation could be carried out by the cloudlet(s) with reduced offloading latency and communicationcosts. Indeed, with physical proximity, one-hop network latency, and the high bandwidth of LAN, thecloudlet(s) could be considered as a complement to traditional cloud computing services, especially forrunning resource-intensive but latency-sensitive applications from mobile devices [14]. For example,6[15] argues that in cloud-based face recognition applications, having mobile devices to directly sendimages to the cloud could sometimes be costly in terms of processing latency, given the potentiallylarge latency of the mobile-cloud data transmission and the need for mobile devices to coordinate thecomputation partition among multiple cloud servers. Hence, it introduces a real-time face recognitionapplication using mobile-cloudlet-cloud architecture, where mobile devices are connected to the cloudvia a stationary cloudlet. Then, the cloudlet in the system is responsible for partitioning and coordinat-ing the computation tasks among itself and multiple cloud servers (basing on various processing timeof cloud servers and communication latency over different mobile-cloud server links) so that optimaloverall QoS could be achieved. It is shown in evaluation that the network response time is minimizedwith the assistance from the cloudlet, thereby achieving an improvement in face detection accuracy andperformance.1.3.2 Ad hoc Mobile CloudWith the increasing processing capacity of modern mobile devices, peer-assisted computing is an emerg-ing topic that is attracting growing attention in the research community. This paradigm regards usersin vicinity as an ad hoc mobile cloud, where neighboring mobile devices are able to utilize and shareresources over mobile ad hoc networks (MANET). Such mechanism provides an advantage of havingless offload latency and bandwidth consumption as compared to cloud computing, since mobile devicescould communicate with each other via device-to-device (D2D) connections [7]. Various applicationshave been proposed for taking consideration of user cooperation over the MANET, such as the ad-hocstreaming in [16], which allows mobile users to download the video package collaboratively. Each usersimultaneously connects to both the server via cellular networks and their ad hoc neighbours via D2Dconnectivity (e.g., Wi-Fi), thus can receive packets from both the server and ad hoc neighbours at thesame time. Other applications such as cooperative downloading [17] and ad-hoc caching [18] all usesimilar idea - to distribute computational tasks to members. In addition, research on integrating cellularand ad hoc networks to overcome the limitations of cellular networks (e.g., limited bandwidth) has beenpopular. As in [19], such hybrid network has been proposed to be used in multi-cast techniques wheremultiple multi-cast groups co-exist in the networks. This work considered using ad hoc multi-cast to7overcome the cellular network limitation. It focused on the scenarios in which the ad hoc network canonly accommodate part of the groups at the same time, and uses cellular network to accommodate theother. It proposed a group selection scheme that determines which groups should be selected to be runin the ad hoc mode (using ad hoc multi-cast) so that the workload on cellular networks is minimizedwhile the utilization of the ad hoc network is maximized. It is demonstrated by simulation-based eval-uation that by applying the proposed group selection scheme, the resources of ad hoc network can beeffectively utilized and the cellular traffic load is minimized. Consequently, we are interested in gamingover ad hoc network, which has not been exploited well. Once an ad hoc network is formed, users mayplay games irrespective of the places they are (e.g. public transports, restaurants) without the need for astructured network and incurring into any connectivity expenses. Actually, previous research work [20]has studied such game architecture. It has explored the possibility of deploying ad hoc mobile cloud-assisted multi-player cloud gaming, especially to utilize cooperative sharing mechanisms to optimizethe system. When multiple players in the same ad hoc mobile cloud are receiving similar video framesfrom the cloud server, the overlapped frames will be decoded and shared amongst each other, which re-duces the overall bandwidth consumption of the cloud gaming system. However, their proposed systemrequires a real-time encoding, sharing and decoding system, which introduces a new additional latencyfor users waiting to receive their video frames, thus will reduce the QoE. As gaming architecture’s as-sociated QoE are highly dependent on network latency, and for most of the users, the maximum amountof response delay they are willing to experience is 120ms, any additional delays should be avoided.Similarly, a gaming platform is proposed in [11], which enables interactive multi-player gaming withdistributed game operations amongst users. In this platform, data packets are overheard by all partici-pants, which result in unnecessary expenditure of battery energy of the recipients.1.3.3 Mobile Social ClosenessThe ad hoc mobile cloud could be considered as an opportunistic network, where the offloading oppor-tunity (the offloading opportunity depends on the connection probability and contact duration of mobiledevices) for such network is built on the connectivity opportunities of mobile devices, which is gener-ated by human mobilities when two or more mobile devices come into contact [12]. Thus, to be able to8integrate ad hoc mobile cloud based computing into our architecture, users’ mobility is one of the keyissues for us to consider. As identified in [12] and [21], the users’ mobility patterns are influenced by hu-man social structures since mobile devices are carried by humans. Authors of these works argue that byembedding human social structures in opportunistic networks, we could try and regulate the movementpatterns of user’s devices as the users’ movement is socially regulated in the real world. In these works,mobile social closeness between users (determined based on the amount of time and the frequency ofcommunication) is identified as the best indicator of social tie, which in turn indicates the connectionprobability and contact duration between them. Yet, before we consider this metric in the proposingsystem, we first look at existing research works that exploit the social closeness between users. In [22],a mobility model is proposed to be built upon social network theory. This model puts mobile devicesinto groups based on the social relationships between users. These groups are then mapped to topo-graphic spaces, with movement influenced by the strength of social tie. The evaluation shows that thismodel provides good approximation of real movements in terms of the distribution of contact duration,which fulfilled the design goal of such mobility model. In [23], a social closeness method is proposedto detect clone attacks in mobile health-care applications. In this work, a new metric, called communitybetweenness, is defined based on the contact duration or the contact frequency between users accordingto different application scenarios. The authors claim that this metric changes in value when the cloneattack is taken place, so that it could be used for clone attack detection. The evaluation results showthat this method can detect clone attacks efficiently, which indicates the feasibility of exploiting mobilesocial closeness in clone attack detection.1.3.4 Component-based Game DesignSeveral commercial game engines, such as Cryengine, Cocos2d, and Unreal, use component-basedgame design. After studying and analyzing the design pattern of these well-known game engines, in thissection, we give our own concept of the component-based game design model, as illustrated in Figure1.2. As indicated in [24], the main and basic game loop runs continuously during game-play and han-dles three major classes of tasks. The first class is input task, which is responsible for capturing userinput without blocking. The second class is update task, which responds to user commands, simulates9Figure 1.2: Component-based Game DesignPhysics and Artificial Intelligence (AI) behaviors, and updates the states of internal game entities. Thelast class is render task, which renders the game and provides feedback to players about the current gamestates through images and audio. At the first glance, it seemed reasonable to make the computation ofall game logics to be off-loadable. Yet, if we take a closer look at the game logics, we could find thatmaking the computation of all game logics to be off-loadable is sometimes non-beneficial for securityand performance reasons. For example, offloading the computation of user-specific data related logic toother devices increases the system security risk. In addition, there are chances that the resources neededto carry out the computation of some light-weighted game logic even be smaller than the computationpower needed for the offloading process. Thus, what we need is to make part of the computation off-loadable while keeping others locally executed. Actually, this approach has already been used by gamesin industry. For example, Titanfall (a well-developed Microsoft Xbox One game) offloads processing ofsome elements, such as Artificial Intelligence and physical computation to Microsoft’s cloud computingservices to optimize local graphical performance, and the rest of the logics are executed locally. Inspiredby these games, for the proposing system, we define high-level game logic components for each classof tasks and further categorize them into allocatable game logic components (i.e., the task for execut-ing such components could be dynamically distributed among users) and non-allocatable game logiccomponents (i.e., the task for executing such component could be executed by local device only). Morespecifically, non-allocatable game logic components generally have lower requirement in computation10resources and manage critical user-specific data, including: input capture, which is executed locally tocapture user inputs; user-specific game logic, which includes management of user statistics (i.e., userhealth, strength) and equipment (i.e., weapon and rare items); low level AI and low level render compo-nent, which simulates AI behaviors and performs render tasks respectively with small portion of centralprocessing unit (CPU) needed. In the contrary, allocatable game logic components include: physics,animation, high-level AI and high-level render.1.3.5 Mobile Computation OffloadingThe emergence of mobile cloud computing (MCC) provides opportunities for mobile applications toutilize computation resources of the cloud. Despite the previously mentioned constrains (i.e., unreliablenetwork connectivity, limited network bandwidth, and unpredictable network latency), the technique of-fered by MCC has been considered as a promising approach to make the batteries of mobile devices lastlonger. Such technique, called computation offloading, offloads energy-consuming computations to thecloud thus frees the mobile devices from heavy-computations. Many researches have proposed differentapproaches toward mobile computation offloading, and the core of such technique lies in deciding when,what, and how to offload the computation to the cloud [25]. An energy-aware computation-offloadingapproach has been proposed in [26], with the goal to maximize the energy saving. The system evaluatesin the runtime metrics such as the offloading costs of each method, the benefits of offloading, and thenetwork connectivity between mobile devices and the cloud in order to make optimal decisions on whichmethods should be offloaded to the cloud and which should be executed locally. Also, CloneCloud in[27] proposed a system, which dynamically partitions the application, and migrate part of the computa-tion from mobile devices to application clones (application level Virtual Machines) reside in the cloudfor execution. CloneCloud partitions the application in a way that optimizes application execution timeand energy used basing on computation and network environments. Likewise, ThinkAir in [28], an-other approach of method-level computation offloading has been proposed. The offloading decision inThinkAir is made based on environment parameters such as network quality and the offloading costs,which takes method execution time and energy conservation into consideration. These works demon-strate that the computation offloading could indeed be an efficient way to alleviate constrains in MCC.11Similar to techniques proposed in these works, our systems aims at improving the performance of mo-bile cloud gaming applications via computation offloading. To better evaluate the performance of oursystem, we compare our system performance with existing computation offloading architectures. Forsimplicity, we compare performance of our offloading policies in task allocation process against theoffloading policies in ThinkAir, and the results are discussed later in this thesis.1.4 Contribution of the ThesisThis thesis targets a component-based, yet cooperative mobile gaming architecture, using ad hoc mobilecloud-cloudlet-cloud approach. By utilizing both the resources from the ad hoc mobile cloud and thecloudlet(s), our architecture provides two types of cooperation in addition to the ability to offloads tasksto the cloud: cooperation with and without the assistance from the cloudlet(s), which is defined by theway in which mobile devices are connected to and interact with the cloud. To be more specific, oursystem allows users to share downloaded game resources with each other while taking different gameprogressions into account. In addition, our system enables computation tasks to be 1) dynamically dis-tributed amongst users within the ad hoc mobile cloud and the cloudlet(s); 2) offloaded to the centralizedcloud when the ad hoc mobile cloud and the cloudlet(s) lack the required processing power. Also, to en-sure the computation success rate, the closeness between users will be considered in the task allocationprocess.The intention of enabling user-level cooperation is to provide a new game-play experience withoptimized Quality of Service (QoS), in terms of reduced device-to-cloud bandwidth consumption, en-ergy consumption of mobile devices, and the interactive latency. As further explained in this thesis, thesethree optimization objectives are rather conflicting, meaning that they could not be achieved individuallywithout degrading the others. Thus, the system considers trade-offs when optimizing the performance:instead of simultaneously optimizing each objective, a set of weight factors is incorporated to reflect therelative importance of each objective. More specifically, for each hosted games, the weight factors areinitially assigned (by the system) to a default number, which is determined by several attributes of thegame. Then, these factors could be altered by users to better suit their preferred game-play experiences.12For instance, some users may care more about the interactive latency than the energy consumption. Inthis case, they could set the weight factors for the interactive latency higher than the energy consumptionaccordingly. The ultimate goal of the system is to provide a customized game-play experience. Fromtproposed respectively. Then, we used a simulation-based evaluation to demonstrate that the designgoal of our approach are met, which is to reduce data transmissions between the users and the clouddue to ad hoc mobile cloud and the cloudlet(s) collaborations; minimize redundant downloading fromthe cloud; minimize overall energy costs, bandwidth consumption, and interactive latency; and ahe sys-tem’s perspective, the benefit gained from user-level cooperation is the reduced overall device-to-clouddata transmission and the optimized QoS. On the other side, from user’s perspective, the benefit gainedfrom user-level cooperation is the opportunity to access pooled resources by acting as a contributor andconsumer at the same time, while having self-controlled and customized performance.In this thesis, we introduce schemes used to achieve the above mentioned design goal. First, boththe progressive downloading and cooperative task allocation processes are investigated and modeledas optimization problems, with heuristic algorithms lso to maximize the ad hoc mobile cloud resourceutilization.1.5 Structure of the ThesisIn the thesis, we give a high-level overview of the system architecture in Chapter 2; introduce theprogressive downloading and cooperative task allocation in Chapter 3 and 4, respectively; followed bya comprehensive system performance analysis in Chapter 5 and conclusion in Chapter 6.13Chapter 2System OverviewIn this chapter, we introduce the targeting game type for the system, investigate the potential applicationscenario, and give a high level overview of the system architecture.2.1 Feasibility and Game TypeThe proposing system targets component-based games, where the logics in game applications are de-composed into self-contained software components, and each execution for such components is definedas a computation task. While each task is considered as an independent unit of computation thus couldbe remotely executed in parallel, the bottleneck for distributing tasks to various devices for execution isthe inter-components dependencies. Actually, we are not the first to consider parallel programming ingame applications as Cascade in [29] and Intel in [30] both proposed architectures that run component-based game tasks in parallel, with respect of task dependencies. To be more specific, Cascade allowsprogrammers to explicitly express task dependencies in a task dependency graph, which is traversedin the run-time by its Job Manager when running task-scheduling schemes. The performance for suchapproach is evaluated by benchmarks, and the results indicate that by considering the interrelationshipsbetween components, the performance of parallel programming in games is improved (as compared toother distributed job processing algorithms) in terms of reduced execution time. On the other hand,Intel investigated the use of both synchronize and asynchronize task scheduling algorithms in paral-lel game engines, and further developed centralized game state manager that is used in distributedcomponent-based games, with different task data synchronization strategies. The works of Cascadeand Intel demonstrate the feasibility of decomposing games into components/tasks with dependencies.Although the differences between our system and Cascade/Intel are that our system assigns tasks to dif-14ferent mobile devices while Cascade/Intel assign tasks to threads running on multi-core machines, theconcept of task dependencies in game applications remain the same. As introduced in Cascade, tasksdependencies in game applications include data-flow dependencies, interactive dependencies (data shar-ing among tasks), and real-time dependencies (computation of such tasks need to be finished in timelymanner, for example, tasks which respond to gun firing). The performance bottleneck for distributedprocessing of tasks with dependencies lie in the latency incurred by data transmission when sending thetask over network, especially for tasks with interactive dependency. Likewise, the transmission delay fortasks with real-time dependencies is also a performance killer, especially when two adjacent tasks areassigned to different mobile devices. Hence, to ensure the performance of distributed task processingover ad hoc mobile network, it is inevitable for us to consider task dependencies in the task allocationprocess. For example, considering task dependencies, our task allocation algorithm could assign adja-cent tasks (a block of tasks) with large interactive dependencies to the same mobile device thus avoid thetransmission (synchronization) of dependency data. Similarly, our task allocation process could assigntasks with real-time dependencies to local device so that the task could be computed without interfer-ence from network delays. An detailed example is shown in Figure 2.1, the tasks that respond to a gunfiring action are delay sensitive, thus, they are assigned to local device for better performance; physictasks and artificial intelligence tasks have high interactive dependencies, thus, they are assigned to thesame mobile device for processing; the tasks for render screen changes could be distributed to differencemobile devices in the network since the game scene/map could be divided into pieces, which could berendered by different devices.However, the task allocation scheme proposed in this thesis does not consider the task dependenciesat this time. Thus, for current stage, our system is more appropriate to be used in games with highcomputation cost, yet low delay requirement and less real-time user interaction. One example of suchgame could be strategic role-playing games (SRPG, also known as tactical role-playing games), whereeach game player employs a number of avatars on the battlefield and the combat takes place on thebattlefield without screen changes. In SRPGs, game players take turns to attack each other dependingon the avatars’ statistics, capabilities, and current positions. Such game has high computation cost sinceit incorporates strategic game-play, i.e., tactical movement on an isometric grid and usually has complex15Figure 2.1: Task Dependencies in Game Applicationgame scene rendering. In the same time, it has low requirement on players’ responsiveness thereforeless latency-sensitive, since it does not have real-time user interactions as players only need to decidethe strategy to be used at each turn. Also, it does not have screen changes hence less real-time renderingtasks. Therefore, it would be a good candidate for the targeting game type. For similar reasons, otherstrategy games such as multi-player on-line chess would also be our targeting game type, with the benefitof enabling multi-player game-play. Also, the architecture allows progressive downloading of gameresources, which utilizes nearby computing devices and the cloud as potential downloading sources.This feature could be used in progressive games, i.e., mobile games that develop following specificdifficulty levels. On the contrary, the feasibility to run other games that is latency-sensitive and has real-time user interaction (i.e., First Person Shooting Games, i.e., Counter-Strike) with our system is yet tobe investigated at this time (without consideration of task dependencies), since delays imposed by taskdependencies might not be beneficial toward the game-play experience. As the ability for such game tobe decomposed and run in distributed manner remains unexplored, we consider enabling integration ofsuch game to our system as future work, with respect of task dependencies.162.2 Application ScenarioAs previously mentioned, the proposing system could be used in scenarios where people need to spendan extended period of time in a crowded environment (i.e., while spending time in coffee shop or takingpublic transit), for which a temporary mobile ad hoc network could be formed. This concept, definedas crowd gaming, has been studied in recent researches: authors in [11] and [31] investigated the pos-sibilities and probabilities for people playing games in public transport. They carried out measurementstudies to show that the average time people spend on one-way transportation is fairly long, and most ofthem are willing to play multi-player mobile games with random people in vicinity to kill time. Inspiredby those studies, we believe that with the idea of crowd gaming, combining with the targeting game type,the proposing system provides a promising way for mobile gamers to play cooperative games with min-imized cellular gaming traffic generated. Such application scenario would be summarized as: a groupof people is taking a subway and decide to play multi-player on-line chess together using the propos-ing system. Then, game tasks could be distributed among themselves instead of solely offloaded to thecloud. The benefits of using proposing system are twofold: 1) the device-to-cloud network connectiv-ity could be intermittent when people riding fast moving underground subways. The proposing systemminimizes the data transmission through the intermittent device-to-cloud network links thus ensures thecommunication and cooperativeness between gamers, while having the cloud as a backup processingunit; 2) the proposing system uses ad hoc mobile cloud to reduce cellular traffic generated while ensur-ing the overall system performance, which is considered a promising way to alleviate the likely to beoverloaded cellular traffic, as indicated by authors in [19] and [32].2.3 Architecture OverviewThe basic idea of the proposed architecture is to enable nearby users who are in possession of mobiledevices to play games in a cooperative manner, including progressive and collaborative game resourcesdownloading, and cooperative task allocation. In addition to obtain services from the distant cloud,stationary cloudlet(s) is considered as a supplementary alternative to request services from. Furthermore,instead of connecting to the cloud (over either a 3G/4G cellular connection or wireless network) and the17(a) Without Cloudlet(s)(b) With Cloudlet(s)Figure 2.2: Cooperation With and Without the Assistance From The Cloudlet(s)cloudlet(s), nearby users are able to utilize and share resources, including processing and storage, overan ad hoc mobile cloud. Then, two types of cooperation are provided: 1) for users who are out of thewireless range of the cloudlet(s), they will play games over ad hoc mobile cloud based cooperation; 2)along with the cooperation between peers within the ad hoc network, users who are within the wirelessrange of the cloudlet(s) will get assistance from the cloudlet(s).Users who are out of the wireless range of the cloudlet(s) connect to the cloud over cellular connec-18tion. Thus, in ad hoc mobile cloud based cooperation, two transmission schemes are being considered:1) transmissions within the ad hoc mobile cloud via Device-to-Device (D2D) connectivity; 2) trans-missions between users and the cloud over cellular network. This application scenario is illustrated inFigure 3 where the ad hoc mobile cloud is formed by seven users, each of them performs two actions si-multaneously: progressive downloading of segmented game resources and collaborative task allocation.In progressive downloading, users are assumed to hold some initial states of the game, and all game dataas well as game components are progressively downloaded onto their mobile devices. As only a smallnumber of game resources are required for users to start playing the game, the rest of the resources canbe acquired from either the cloud or the neighborhood ad hoc mobile cloud depending on the progressof the game. In the example, only users named David, Frank, and Alice are getting game resources fromthe cloud and other users are all getting resources from their neighbors. Also, our system prioritizes thead hoc mobile cloud when offloading the computation tasks, and only offloads to the cloud when thead hoc mobile cloud does not have the required capability. Upon receiving the task allocation requests,users could decide to either accept or reject the requests based on their current processing status. In theexample, four task allocation cases are included: 1) Alice does not have a local task so she can processthe task for Candy; 2) Grace has a task that cannot be handled by the ad hoc mobile cloud and henceoffloads her task to the cloud; 3) Frank is processing both his local task and the task offloaded by Bob;4) Elaine’s request to offload her task to David is rejected since David is busy processing his own task;thus Elaine offloads her task to the cloud.On the contrary, users who are within the wireless range of the cloudlet(s) connect to the cloudthrough the cloudlet(s) (similar to Wi-Fi hotspot). Thus, in ad hoc mobile cloud based cooperation withcloudlet(s), three transmission schemes are being considered: 1) transmissions within the ad hoc mobilecloud via D2D connectivity; 2) transmissions between users and the cloudlet(s) over Local Area Net-work (LAN); 3) transmissions between the cloudlet(s) and the cloud over Wide Area Network (WAN).This application scenario is illustrated in Figure 4. In addition to the ability for users to utilize and shareresources over the ad hoc mobile cloud, in this approach, the cloudlet(s) acts as a direct neighbor to userswithin its wireless range. As progressively downloaded games resources from the cloud go through thecloudlet(s), these game resources are cached in the cloudlet(s). Then, the cloudlet(s) could be consid-19ered as a great alternative to acquire the resources from. Moreover, if both the cloudlet(s) and the ad hocmobile cloud do not have the required resources, users could request for services from the cloud throughthe cloudlet(s). In the example, three progressive downloading cases are included: 1) players namedCandy, David, Elaine, and Frank are getting game resources from their ad hoc neighbors; 2) playernamed Bob is getting resources from the cloudlet; 3) player named Alice is requesting game resourcesfrom the cloud through the cloudlet. On another hand, the cloudlet(s) is also an effective alternative tooffload the tasks to. In the example, aside from being able to offload tasks to the ad hoc mobile cloud:1) both players named David and Elaine are offloading their tasks to the cloudlet; 2) Grace’s request tooffload her task to Frank is rejected, she then offloads her task to the cloud through the cloudlet.The core of this thesis is the progressive downloading and task allocation processes since they arethe determining factors for our system performance. The main focus of this thesis is the optimizationschemes for these two processes, for which aiming at optimizing the performance in terms of reducedbandwidth consumption, energy consumption, and interactive latency (the priority/weight of each op-timization objective is user-controlled). Given that these two processes depend on the speed of users’game progresses, a global knowledge of users’ game statuses should be maintained by each user andupdated in real-time. To achieve this, each user is required to periodically send a beacon so that all usersare aware of their one-hop neighbors and also their game statuses. Also, for simplicity, we allow onlyunicast transmissions within the ad hoc mobile cloud since offloading to the cloud and the cloudlet(s)uses one-to-one transmissions. Since each transmission scheme has its own characteristics in terms ofenergy costs, bandwidth consumption, and interactive latency, aiming at optimizing the system perfor-mance, it is critical for the system to determine to whom to map downloading requests and computationtasks to.Both mechanisms of progressive downloading and cooperative task allocation are introduced later inthe thesis as separate chapters, with specific focus on problem formulation, algorithms, and performanceevaluation for each of them. However, in this thesis, we present only the problem formulation andalgorithms used for ad hoc mobile cloud based cooperation, and the reason is explained as follows.First, we argue that the formulations for the two types of previously mentioned cooperation are thesame. In ad hoc mobile cloud based cooperation, the tasks are considered to be offloaded to either the20cloud or their ad-hoc neighbors, whereas in ad hoc mobile cloud based cooperation with cloudlet(s), thetasks are considered to be offloaded to either the cloudlet(s) or their ad-hoc neighbors. The mathematicalrepresentation of the tasks offloaded to (or the game resources acquired from) the cloud is the same ascompared to the tasks offloaded to the cloudlet(s) since: 1) cloudlet(s) is considered as the edge of thecloud, which carries out the communication between users and the cloud; 2) the cloudlet(s) connects tothe cloud over WAN network, and we assume the latency in WAN network to be small and the bandwidthto be large enough, thus its associated bandwidth consumption and interactive latency could be ignored;3) we also ignore the energy costs incurred by the cloudlet(s) since it is a stationary device. Then, it issafe for us to say that the formulations of these two types of the cooperation are the same. Second, thealgorithms used for ad hoc mobile cloud based cooperation with the assistance from the cloudlet(s) couldbe simplified to the algorithms used for the ad hoc mobile cloud based cooperation. In the simplifiedversion, the stationary cloudlet(s) is being considered as an ad hoc neighbor with powerful computationpotential and stable network connectivity. Hence, to avoid repetition of similar concepts, this thesis onlypresents the problem formulation and algorithms used for ad hoc mobile cloud cooperation.21Chapter 3Progressive Downloading of GameResourcesIn this section, the process of progressive downloading is discussed by first introducing the problemformulation and algorithms, followed by the simulation-based evaluation.3.1 Problem FormulationWe formulate the progressive downloading as an integer linear optimization problem, where discretetime is assumed. For each user, we denote game resources downloaded from the cloud as d3G/4Gi (t), andgame resources acquired from the ad hoc mobile cloud as dD2Di (t). Then, the overall downloading for aperiod of T time slots can be formulated as:N∑i=1t=T∑t=0d3G/4Gi (t)+dD2Di (t) (3.1)To achieve the maximized cooperation among users, we need to minimize the number of downloadedcontents from the cloud, which can be formulated as:Minimize:N∑i=1t=T∑t=0d3G/4Gi (t) (3.2)To be able to minimize the overall number of downloaded contents from the cloud, we need tomaximize the utilization of the ad hoc mobile cloud in real-time. Yet, this requires prior knowledge ofnetwork and users’ statuses, which is not included in the problem formulation. Bearing this in mind, weintroduce the algorithms in the following section.223.2 AlgorithmIn this section, we propose approximation algorithms for finding optimal solutions in the progressivedownloading process. Since computer games are delay-sensitive applications, finding the exact optimalsolution may not be feasible as it may take too long. Also, the downloading request for each user canbe considered as a sub-problem to a global optimization problem. Thus, for each sub-problem, wecan iterate through the feasible solutions and apply a heuristic algorithm to determine a near-optimalsolution, where the optimal solution is defined by having the minimal processing time. For this module,we consider two heuristic algorithms. The first one is called greedy local, which allows users to acquiregame resources from a neighbor with the minimal transmission speed. This algorithm is summarized inAlgorithm 1 where a user ui needs a game resource that is owned by a user u j, it will then estimate thetime for the owner to transmit the content. This time will be denoted as Ti j(t). Finally, it will retrieveits gaming progress speed, and decide whether to receive the content through the server or its neighborby comparing Ti j(t) and gi(t) : if Ti j(t) < gi(t), the user should be receiving the content through itsneighbor; otherwise, the content is downloaded from the cloud.Algorithm 1 Algorithm: Greedy Local1: U : Set of neighbours who has the required game piece2: D := /0, set of game pieces downloaded3: G := Downloaded game piece for current iteration4: g := Local game progress speed5: Tu := Transmission speed between user u and local user6: while U 6= /0 do7: choose u ∈U : Tu being minimal and less than g;8: if u 6= Null then9: G← downloadFromNeighbour(u);10: else11: G← DownloadFromCloud(G);12: end if13: D := D∪{G} ;14: end whileThen, a different strategy is used for which users are organized into clusters and can only acquiregame resources from users within the same cluster. Each user ui is associated with a weight, Gi, whichis the current game progress for ui. For each time interval, the K-Means algorithm for clustering is23Algorithm 2 Algorithm: Weighted K-Mean1: D := /0, set of game pieces downloaded2: W := Set of weighted users3: K := Set of user being center to each cluster4: G := Downloaded game piece for current iteration5: K← KMeanClustering(W );6: for i← 0 to N do7: if Wi ∈ K then8: G← downloadFromCloud(G);9: else10: G← downloadFromNeighbour();11: end if12: D := D∪{G} ;13: end forapplied to find the best K users who are responsible for downloading via cellular links. Other users willprimarily receive the required content from these K users. For the situation where user ui is no longersatisfied acquiring resource from its peers, it can decide to download contents via a cellular link on itsown. This algorithm is shown in Algorithm 2.Both algorithms have computational complexity of O(1), assuming the K-Means clustering algo-rithm is running on the cloud and therefore we ignore its associated complexity. These algorithms havedifferent advantages and disadvantages. The first algorithm allows each user to select neighbours freelyand distributes the downloading requests evenly within the ad hoc mobile cloud, whereas the secondalgorithm only allows users to acquire data from system determined users, which is not as fair as thefirst algorithm. However, the first algorithm has a higher requirement in terms of user reliability sinceall users are responsible for sharing their acquired data while the second algorithm allows users to onlyacquire contents from determined users. Also, the second algorithm works better when some of theusers have much faster game progress speed as compared to the rest of the users since the users who areresponsible for downloading via cellular links are determined according to their game speed.24Table 3.1: Evaluation Setup Parameters: Progressive DownloadingTarget Parameter Minimum MaximumBase Case Device(s), Cloud, and Cloudlet(s) 50 350User(s) / Device(s) Factors Game Progress Speed 1 10Network TopologyDensity 1 10Skewness 1 10Task Density 1 10Weight FactorsEnergy Costs 0 1Bandwidth Consumption 0 1Interactive Latency 0 13.3 EvaluationsSystem performance is evaluated by using a Java simulator, which assigns random attributes to parame-ters such as network and users’ status. Each of these parameters is randomly generated within a certainrange, which is specified using base cases and different factors. To give a comprehensive evaluationof the performance, we use two types of network topologies in the simulation, both trace-driven andrandomly generated. Details of how each parameter is generated are listed in Table 3.1.We first simulated our system using randomly generated network topologies. In the simulation, eachuser downloads a game resource depending on their game progress speed, which is the time slots intervalbetween each download. An example of the downloading progress for ten users is shown in Figure 3.1.In this example, game data are segmented into ten pieces and the downloading process is implementedusing Greedy Local. The simulation results in 3.1 show that users with faster game progression speedfinishes downloading before others.For ad hoc mobile cloud based cooperation, game resources can be acquired from either ad-hocneighbors or the cloud. Thus, we differentiate the downloaded game pieces via different network links.Figure 3.2a shows the total downloaded game data for all users. Game pieces downloaded directlyfrom the cloud (via cellular links) are colored in blue whereas pieces acquired from the ad hoc mobilecloud (via Device-to-Device (D2D) links) are colored in red. From the graph, we can see that at the250 10 20 30 40 50 60012345678910Download ProgressTime Slot  User: 1User: 2User: 3User: 4User: 5User: 6User: 7User: 8User: 9User: 10Figure 3.1: Downloading Progress for Users with Different Game Progressionbeginning of the game session, most of the game data are downloaded from the cloud; however, as thegame progresses, more and more game data are acquired through the ad hoc mobile cloud. Thus, totaldownloading traffic via cellular link is significantly reduced.The total downloading for ad hoc mobile cloud based cooperation with the assistance from thecloudlet(s) is shown in Figure 3.2b. Again game pieces downloaded directly from the cloud are coloredin blue whereas pieces acquired form the ad hoc mobile cloud are colored in red. Here we have an addi-tional downloading source, which is the cloudlet(s), and game pieces downloaded from the cloudlet(s)are colored in yellow. From the graph, we can see that as the game progresses, most of the gameresources are acquired from the cloudlet(s). This is because that all game pieces downloaded fromthe cloud are cached in the cloudlet(s), so that most of the users could acquire game pieces from thecloudlet(s) instead of their ad-hoc neighbors. This indicates that by adding the cloudlet(s), the down-loading performance is improved significantly.Actually, bring along the cloudlet(s) into our architecture has multiple advantages. For example,without the assistance from the cloudlet(s), users may only acquire game resources from either theirdirect neighbors or the cloud. The fact that it ignores the possible content sharing between multi-hop neighbors limits the efficiency of the content sharing. Alternatively, if the downloaded resources2610 20 30 40 50 60 700102030405060708090100Time SlotGame Data  From CloudFrom Ad hoc Mobile Cloud(a) Without Cloudlet(s)10 20 30 40 50 60 700102030405060708090100Time SlotGame Data  From CloudFrom CloudletFrom Ad hoc Mobile Cloud(b) With Cloudlet(s)Figure 3.2: Progressive Downloading With and Without the Assistance From The Cloudlet(s)are cached in the cloudlet(s), content sharing between multi-hop neighbors could be carried out bythe cloudlet(s), without multi-hop data transmission. Also, our system only enables content sharingbetween users who reside in the same ad hoc mobile cloud. As the ad hoc mobile cloud is actually anopportunistic network, the probability for which content sharing occurs depends on the time and users’27(a) A Instance of Network Topology0 100 200 300 400 500 600 7000500100015002000250030003500400045005000Time SlotGame Data  From CloudFrom Ad hoc Mobile Cloud(b) Total Downloading ProgressFigure 3.3: Progressive Downloading with Map-Based Movementphysical locations. On the contrary, the cloudlet(s) is considered to be a stable device as compared tomobile devices. It provides potential content sharing for users who have the same routine, but not residein the same ad hoc mobile cloud, i.e. people may visit the same coffee shop during different hours.To evaluate the effect of users’ mobility on our system performance, we simulated the progressive28downloading using a trace-driven network topology generator called ONE. In the simulation, map- basedmovement pattern is used, where users are located inside several street blocks initially and their move-ment patterns are according to the map of each block. An example of the network topology generatedbased on this movement pattern is shown in Figure 3.3a. Simulation Result for progressive download-ing under map-based movement topology is shown in Figure 3.3b. From this figure, we can see thatas the game progresses, more game data is acquired from the ad hoc mobile cloud and the total trafficvia the cellular network is reduced. This result shows that the algorithms proposed are logical and theprogressive downloading scheme is beneficial even with the effect of users’ mobility.The simulation results shown for progressive downloading with cloudlet(s), without cloudlet(s),are shown to be consistent with both randomly generated and map-based movement based networktopologies, which proves that the design goal for the progressive downloading is met and thereforeconcludes this chapter.29Chapter 4Cooperative Task AllocationIn this section, the process of cooperative task allocation is discussed following the same pattern as forthe progressive downloading. In the section, the cooperation policies with and without the considerationof mobile social closeness are considered, and are being formulated as separate problems. Also, theperformance is evaluated by using simulations.4.1 Problem FormulationThe task allocation mechanism could be considered as a multiple knapsack problem, where the mobiledevice is considered as a knapsack with a capacity determined by its central processing unit (CPU)processing power and storage capacity. The goal of this knapsack problem is to select N disjoint subsetsof tasks based on the network topology, as it can only be mapped to its initiator’s direct neighbours.Each subset of tasks can then be assigned to different mobile devices (where the assigned tasks wereinitiated by the device’s neighbours) whose CPU and storage capacity is no less than the total requiredCPU and storage capacity of tasks in the subset. In this mechanism, the mobile devices, the ad hocmobile cloud, and the computation tasks play important roles; we will first formulate them as follows:• We assume that the network is constituted by a set of users (devices) ω . In general, at time t, eachuser µi ∈ ω could be uniquely identified using the following attributes: 1) Storage Availability:ki, which is the memory space available; 2) CPU Availability: zi, which is the CPU resourcesavailable; 3) Energy Availability: bi, which is current battery Level; 4) Availability: Ai, which isthe availability to participate in the cooperation process; 5) Energy Consumption/unit time: ei;• At time t, user µi generates a computation task ni, which is assumed to be independent in terms of30execution sequence. Then, each task ni could be uniquely identified using the following attributes:1) Storage Consumption: si, which is the memory space required in order to compute the task;2) CPU Consumption: ci, which is the cpu resources required in order to compute the task; 3)Task Duration/deadline: di, which is the maximum time interval allowed for the task to be com-puted; 4) Size of data sent: xi, which is the size of the task parameters, including associated userinputs transmitted when offloading the task; 5) Size of data received: ri, which is the size of thecomputation results received by the task owner after the task is successfully computed; 6) Exe-cution Time: qi j, which is the duration spent by device µ j in computing task ni; 7) BandwidthConsumption: vi j, which is the bandwidth consumed by transmitting the task over the Network;and 8) Network Link Delay: li j• To model users in the ad hoc mobile cloud, we define an N by N neighbourhood matrix, X ,where each element represents relationships between two users. X [i, j] = 1 indicates that thereexists a direct communication between user ui and u j and they will be able to collaborate. Also,to enable tasks to be handled locally, X [i, i] should always be 1.With the formulation of the mobile devices, network, and the computation tasks, the next step isto formulate the cooperative task allocation process as an integer linear optimization problem. Theobjective of the optimization problem is defined as the system resource usage, which will be introducedin the following section.4.1.1 System Resource UsageModeling System Resource Usage FunctionThe design goal of the task allocation process is to minimize the expected system resource usage,which can be characterized by three main factors: the overall energy costs, bandwidth consumption,and the interactive latency. These three factors impact differently toward the user-perceived game-playexperiences, thus, we consider and formulate each of them individually.The energy costs for the task allocation process include both the energy used for task processing,as well as the energy costs incurred by transmitting tasks parameters and the computation results across31Table 4.1: System Resource Usage ParametersUsage Parameters Components Device-To-Device Device-To-CloudEnergy CostsTask Execution e jqi j ecqciTask Data Transmission hi j hciTask Results Transmission gi j gciBandwidth Consumption Bandwidth vi j vciInteractive LatencyExecution latency qi j qciTask Data Transmission xi/vi j xi/vciTask Results Transmission ri/vi j ri/vciLink Latency (One-way Transmission) li j lcithe network. To be more specific, for each task offloaded to device µ j, we define three components interms of energy costs, including the energy costs for executing task ni on device µ j, the energy costs fortransmitting task parameters to the device µ j, and the energy costs for receiving computed results fromthe device µ j. Terms used to represent each component are summarized in Table 4.1. Combining thesecomponents together, the usage factor of energy costs for offloading task ni to device µ j is defined as:Uei j = e j(t)qi j(t)+hi j(t)+gi j(t) (4.1)Similarly, the usage factor of energy costs for offloading task ni to the centralized cloud c is definedas:Ueci = ec(t)qci (t)+hci (t)+gci (t) (4.2)Then, the overall energy costs for the task allocation process fe could be defined as:fe =N∑i=1N∑j=1Fi j(t)Xi j(t)A j(t)Uei j +N∑i=1(1−N∑j=1Fi j(t)Xi j(t)A j(t))Ueci (4.3)where32Fi j(t) =1, If user i’s task is mapped to user j0, Otherwise(4.4)The first part of the formulation represents the energy costs generated by offloading tasks to the adhoc mobile cloud, whereas the second part of the formulation represents the alternative.Following the same pattern, we define the bandwidth consumption. We denote vi j and vci as thebandwidth consumption for the tasks offloaded to the ad hoc mobile cloud and the cloud respectively.The usage factor of bandwidth consumption for offloading task ni to device µ j in the ad hoc mobilecloud is defined as:Ubi j = vi j(t) (4.5)Similarly, the usage factor of bandwidth consumption for offloading task ni to the centralized cloudc is defined as:Ubci = vci (t) (4.6)Then, the bandwidth consumption for the task allocation process fb could be defined as:fb =N∑i=1N∑j=1Fi j(t)Xi j(t)A j(t)Ubi j +N∑i=1(1−N∑j=1Fi j(t)Xi j(t)A j(t))Ubci (4.7)Lastly, we define the interactive latency. The user perceived delay is not just the task processingtime but also includes the time it takes for data transfer across the network, which is determined by thebandwidth available in the network. Thus, we define three components for interactive latency, includingthe transmission latency for sending the task parameter to µ j, the transmission latency for receiving thecomputed results from µ j; as well as the execution time. The usage factor of interactive latency foroffloading task ni to device µ j in the ad hoc mobile cloud is defined as:Uli j = xi(t)/vi j(t)+ li j(t)+ ri(t)/vi j(t)+ li j(t)+qi j(t) (4.8)33Similarly, the usage factor of interactive latency for offloading task ni to the centralized cloud c isdefined as:Ulci = xi(t)/vci (t)+ lci (t)+ ri(t)/vci (t)+ lci (t)+qci (t) (4.9)Then, the interactive latency for task allocation fl could be defined as:fl =N∑i=1N∑j=1Fi j(t)Xi j(t)A j(t)Uli j +N∑i=1(1−N∑j=1Fi j(t)Xi j(t)A j(t))Ulci (4.10)Targeting at the minimized system resource usage, we want the energy costs, bandwidth consump-tion, and interactive latency to be minimized. Then, the system resource usage function could be consid-ered as multi-objective optimization which involves minimizing all three usage parameters, as presentedbelow:Minimize: ( fe, fb, fl) (4.11)Subject to:N∑i=1Fi j(t)∗Xi j ∗A j(t)∗ s j(t)≤ k j(t),∀ j, (4.12)N∑i=1Fi j(t)∗Xi j ∗A j(t)∗ c j(t)≤ z j(t),∀ j, (4.13)N∑j=1Fi j(t)∗Xi j ∗A j(t)≤ 1,∀i, (4.14)Fi j(t) ∈ {0,1} (4.15)Four constraints are defined in the formulation. The first (Equation 4.12) and the second (Equation4.13) are used to indicate that the overall CPU and storage consumption for the assigned tasks to eachuser is no more than the CPU and storage available for such user. The third constraint (Equation 4.14)is to assign no more than one task to each user, and the last (Equation 4.15) indicates that for Fi j(t) weonly accept solutions as 0 or 1 as defined earlier. However, it is not feasible for the system to solve thismulti-objective optimization problem in real-time, as it might take too long for the problem to be solved.34Table 4.2: Examples of Game ClassificationGame Application Computation Data Interaction ClassificationChess 0.9 0.1 0.4 Computation-IntensiveDiablo3 0.5 0.9 0.7 Data-IntensiveLoL 0.4 0.6 0.9 Interaction-IntensiveThus, it is important for us to simplify the problem formulation so that it could be solved in a timelymanner without any loss of generality.Solving System Resource Usage FunctionFor multi-objective optimization problems, the optimal solution that simultaneously optimizes eachobjective might not exist (or depending on the relationships between the objective functions). Hence,it is important to study the relationships between the objective functions in the problem before solvingany multi-objective optimization problem.To examine the relationships between the objective functions in the system resource usage function,simulation has been carried out by using a set of randomly generated parameters for the tasks, devices inthe network, and an instance of randomly generated network topology. Then, each objective function isevaluated by iterating through the possible task-device assignments and computes the solution for each.The solution space is shown in Figure 4.1. By analyzing the solution space, we find that three objectivefunctions are conflicting. They depend on and restrict each other mutually. To be more specific, as shownin Figure 4.2 and Figure 4.3, the interactive latency increases as energy costs increases, yet decreasesas the bandwidth increases. In this case, instead of a single solution that simultaneously optimizes eachobjective, there exists a set of Pareto optimal solutions, which are considered equally good. To solvesuch multi-objective problem, trade-offs need to be considered.To qualify the trade-offs, we incorporate a set of weight factors: {α,β ,δ}, where α +β + δ = 1,to reflect the relative importance of the energy costs, bandwidth consumption, and interactive latencyrespectively. These weight factors are pre-set by the system to default numbers (could be future adjustedby users to suit their own needs, with the constraint remaining α + β + δ = 1), which are adaptively351.551.61.651.71.751.8x 1049801000102010401060108011001120245250255260265270Energy CostsBandwidth ConsumptionInteractive LatencyFigure 4.1: Pareto Front: A Set of Pareto Optimal Solutions to The System Resource Usage ProblemFigure 4.2: Interactive Latency and Energy CostsFigure 4.3: Interactive Latency and Bandwidth Consumptiondetermined according to the computation cost of the game application, game data volume, as well as itsinteractive frequency (Computation, Data, and Interaction, where Computation ∈ [0,1], Data ∈ [0,1],36and Interaction ∈ [0,1]). Indeed, some games are interaction-intensive, while others being either data-intensive or computation-intensive. For instance, as shown in Table 4.2, games like Chess has high valueon computation cost, less of the interaction frequency and very little on game data volume; the famousMassive Multi-player On-line Game (MMOG) called Diablo3 has higher value on game data volumethan the interaction and the computation cost (note that the Computation, Data, and Interaction valuegiven in the examples are user-perceived, it does not have scientific meanings). Thus, for interaction-intensive game applications, it is reasonable to set the importance factor of the interactive latency δhigher than the energy costs and the bandwidth consumption; on the contrary, for computation-intensivegame applications, the importance factor of the energy costs α should be higher among the three ofthe factors; similarly, for data-intensive game applications, we need to set the importance factor of thebandwidth consumption β higher than the others as it needs more data exchanges. Then, integrating theweight factors, the system resource usage could be modeled as a single objective optimization problem,shown as below:Minimize:N∑i=1N∑j=1Fi j(t)Xi j(t)A j(t)(αUei j +βUbi j +δUli j)+N∑i=1(1−N∑j=1Fi j(t)Xi j(t)A j(t))(αUeci +βUbci +δUlci)(4.16)Subject to: (4.12),(4.13),(4.14),(4.15)Constrains listed above are the same as in the system resource usage function. By converting thesystem resource usage function to a single-objective function, the task allocation problem without mo-bile social closeness should be able to be solved in a timely manner. Then, in the following section, thetask allocation problem that considers the mobile social closeness will be explored.4.1.2 Mobile Social ClosenessIn the previous section, we introduced a model which maps each computation task to the candidate withminimal scalarized system resource usage. However, as mentioned earlier, the task success rate, which37is determined by the probability for offloaded tasks to be successfully computed and returned to thetask owner before the task deadline, depends on the mobility of users. The tasks that are not successfulreturned before the task deadline are regarded as failed, and therefore needed to be re-allocated, whichnegatively impacts the Quality of Service (QoS). Hence, we believe that the QoS could be ensuredby improving the task success rate. In this thesis, we consider the probability of failure,Ri j, in theprocess of offloading task ni to device µ j in the ad hoc mobile cloud, which is proposed to measurethe mobile social closeness between the users: high degree in mobile social closeness, low probabilityof failure. They are considered having an inversely proportional relationship (Ri j = k/closeness) sincethe probability for users with high degree of social closeness to get in contact with each other andstay within a short physical distance are higher than the alternative, thus lower probability of failure.Then, while constraints are remained the same, the task offloading process considering the probabilityof failure could be modeled as:Minimize:N∑i=1N∑j=1Fi j(t)Xi j(t)Ri j(t)A j(t)(αUei j +βUbi j +δUli j)+N∑i=1(1−N∑j=1Fi j(t)Xi j(t)A j(t))(αUeci +βUbci +δUlci)(4.17)Subject to: (4.12),(4.13),(4.14),(4.15)The probability of failure is only considered for the tasks offloaded to the ad hoc mobile cloud sincesteady device-to-cloud connectivity is assumed. Also, given the cloud is assumed to have unlimitedprocessing power, we assume the tasks being offloaded to the cloud could always be computed andsuccessfully returned to task owners.4.2 AlgorithmsIn this section, several heuristics algorithms for the task allocation process are presented, which couldbe applied under different network environment to gain better system performance. The basic structure38of the algorithm for this module is presented in Algorithm 3. Assuming there is a mapping M, whichrepresents the task-resource mapping within the ad hoc mobile cloud, and we have to specify a set oftasks initiated by users within the ad hoc mobile cloud and decide to which neighbor the task is allocatedso that the system resource usage could be minimized. We use several different strategies for choosingthe neighbor to offload the task, where they all have to meet one constraint, which is for the chosenneighbor to have sufficient computation potential for the task. For example, if user µi has a task ni andwants to map to its neighbor µ j, then user µ j must have k j ≥ sni (sni being the storage consumption oftask ni) and z j ≥ cni (cni being the storage consumption of task ni). If no valid neighbor is in the ad hocmobile cloud, the task is then offloaded to the cloud.Algorithm 3 Algorithm Frame for Task Allocation1: N := Set of Tasks2: M := /03: for i← 0 to Size(N) do4: choose{u ∈ neighbourO f (initiator(Ni))};5: if u 6= Null then6: M :=M∪{Ni,u} ;7: zu := zu− cNi ;8: ku := ku− sNi ;9: else10: Of f loadToCloud(Ni)11: end if12: end for• Random Mapping: Task requests are mapped to randomly chosen neighbors who have enoughprocessing and storage capabilities.• Greedy Local: Each potential task-resource mapping has its corresponding system resource us-age. We use Costi j to refer to the system resource usage for offloading task from user µi to µ j. Inthis strategy, each task is assigned to the available neighbor with minimum Costi,neighbor, thus, theglobally optimal solution can be achieved by making locally optimal choices.• Greedy Heuristic: In this strategy, each task is assigned to user µ j if it has the minimum addi-tional Costi, j based on its current mapping.39Table 4.3: Algorithm Complexity: Cooperative Task AllocationAlgorithm Computational Complexity Storage ComplexityRandom Mapping O(1) O(1)Greedy Local O(n) O(n)Greedy Heuristic O(n) O(n2)The computational and storage complexity for the above algorithms are listed in Table 4.3. In ouranalysis, we consider only the complexity for the neighbor selection process since steps for maintenanceare common for all algorithms.4.3 EvaluationsAs previously mentioned, the simulation assigns randomly generated parameters (within a specificrange) to users and the devices. To better test the system performance, the users’ CPU availabilityhas a range smaller than tasks’ CPU consumption, so that some tasks will have CPU consumptiongreater than processing capability of the ad hoc mobile cloud and hence will have to be offloaded tothe cloud. Details of how each parameter is generated are listed in Table 4.4. Again, in this section,performance for the task allocation process is evaluated using both randomly generated and trace-basednetwork topologies.4.3.1 System Resource UsageIn this section, the performance of task allocation process under both types of cooperation is evaluated(ad hoc mobile cloud based cooperation with and without the assistance from the cloudlet(s)), where theprevious introduced algorithms are used to implement the task allocation process, including the solutionto the optimization problem formulation (later referred to as optimal solutions), which is produced usingoptimization solver called Gurobi6, and their results are compared side by side. We included only the6http://www.gurobi.com/40CPU and storage consumed by computation tasks and ignored the resources used for carrying out eachalgorithm in the simulations. Also, for the simulation results shown below, we does not include the taskre-assignment and assume that each task offloaded could be successfully computed and returned beforeits associated deadline. We first evaluate the performance of the ad hoc mobile cloud based cooperation.The results and the analysis are listed as below:• Density: Figure 4.4a shows the overall energy costs incurred by different allocation algorithmsunder different network environments. The network topology is generated in response to differentdegrees of network density, where a topology with higher density indicates that there is moreDevice-to-device connectivity between users than a topology with lower density. These simulationresults show that the energy costs decrease as the network density increases for all the algorithms.This is because a higher degree in density means users have more connected neighbors, whichimplies that they have more external helpers so that more computation tasks can be offloaded tothe ad hoc mobile cloud, and the costs to offload tasks to the ad hoc mobile cloud are often smallerthan the alternative. Figure 4.5a and Figure 4.6a shows the idle storage and CPU capacity inpercentage with various degree in density. From both figures, we see that idle resources decreaseas density increases, which shows that our system gives better resource utilization. Also, weobserve that the greedy heuristic algorithm has lower energy costs in the beginning but convergeswith the greedy local algorithm as density level increases, which indicates that in a more connectednetwork, the greedy local algorithm has lower energy costs.• Skewness: In fact, to try to simulate the system and analyze the system performance in a real-world environment, we need to obtain a more realistic network topology, which follows the powerlaw. Thus, we used an algorithm proposed in [33] to generate such a network topology. Then, weobtained the energy costs under various degrees of skewness, where a high degree in skewnessmeans that the network is more unbalanced (i.e., only a small number of users are connected tomost other users while others are connected to only a few) than low degree. From the simulationresults shown in Figure 4.4b, we can see that with a higher degree in skewness, the overall energycosts increases. This is because with unbalanced network topology, most of the users have few41connected neighbors while only a small number of users have most of the connections. Sometimesusers with few neighbors will have to offload their computation tasks to the cloud; thus the energycosts are high. This indicates that with a more balanced network topology, the energy costsare minimized. Also, our system has better ad hoc mobile cloud utilization when the skewnessis minimal, as showed in Figure 4.5b and Figure 4.6b. We observe that the greedy heuristicalgorithm has higher energy costs in the beginning but lower costs as skewness level increasesas compared to the greedy local algorithm, which indicates that in a more balanced network, thegreedy local algorithm has lower energy costs.• Density and Skewness: A more extensive evaluation is done for the allocation process, takinginto account both skewness and density when generating the network topology. The simulationresults are shown in Figure 4.7, which evidently prove that an unbalanced and unconnected (i.e.,most users do not have connected neighbor) network topology causes higher energy costs.All simulation results presented above show that the system performance depends highly on the net-work environments, and more benefits are realized by the proposed scheme in a balanced and connectednetwork. However, regardless of the network environments, the algorithms we have proposed are shownto be near-optimal and hence are cost-efficient. More specifically, the greedy local algorithm performsbetter when the network topology is more connected and balanced. In contrast, for less dense and un-balanced network, the greedy heuristic algorithm would be more cost-efficient. Also, random mappingcould be considered as a good alternative when computation and storage capacities of mobile devicesare limited, since it has lower computational and storage complexity as indicated in Table 4.3.We then evaluated the performance for the task allocation process with the assistance from thecloudlet(s). The optimal solutions obtained for both types of network topology, as shown in Figure 4.8aand Figure 4.8b, are compared side by side. From the figures, we can see that with the assistance fromthe cloudlet(s), the system resource usage decreases as the network density increases, yet increases asthe network skewness increases. These simulation results are shown to be consistent with the resultsobtained for the ad hoc mobile cloud based cooperation. However, the system resource usage with thecloudlet(s) is much lower than without the cloudlet(s), which indicates that by adding the cloudlet(s)420 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1100120140160180200220240Energy CostsDensity  Greedy LocalRandom MappingGreedy HeuristicOptimal(a) Various Degrees of Density0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1406080100120140160180200220240Energy CostSkewness  Greedy LocalRandom MappingGreedy HeuristicOptimal(b) Various Degrees of SkewnessFigure 4.4: Energy Costs under Different Network Environmentsinto our architecture, the system performance is improved.43IDLE CPU (%)Density  0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 14550556065707580Greedy LocalRandom MappingGreedy HeuristicOptimal(a) Various Degrees of DensityIDLE CPU (%)Skewness  0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1354045505560Greedy LocalRandom MappingGreedy HeurisitcOptimal(b) Various Degrees of SkewnessFigure 4.5: CPU Utilization under Different Network Environments4.3.2 Mobile Social ClosenessTo show the effect of closeness in the task offloading process, the process of cooperative task allocationis simulated using real-world movement trace based network topology, where the offloading successrates for the task allocation process with and without the consideration of the mobile social closeness44IDLE STORAGE (%)Density  0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 16668707274767880828486Greedy LocalRandom MappingGreedy HeuristicOptimal(a) Various Degrees of DensityIDLE STORAGE (%)Skewness  0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 152545658606264666870Greedy LocalRandom MappingGreedy HeurisitcOptimal(b) Various Degrees of SkewnessFigure 4.6: Storage Utilization under Different Network Environmentsare evaluated. Here we define the closeness between users as the total contact time/simulation time andthe closeness distribution for map-based movement are shown in Figure 4.9a. In the simulation, wecompare the solutions to the problem formulation introduced for task allocation with and without thecloseness respectively. The probability of failure Ri j in task allocation with mobile social closeness is450 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1050100150200250300Energy CostsDensity  Skewness 0.1Skewness 0.3Skewness 0.5Skewness 0.7Skewness 0.9Figure 4.7: Energy Costs for Various Degree of Skewness and Densitydefined as a number inversely proportional to the closeness between user µi and µ j. In the evaluation,we regard each task that is assigned to ad-hoc neighbors, yet failed to return the computation resultswithin the task duration as failed. In Figure 4.9a, we show that the closeness distribution in map-basedmovement model follows the exponential distribution. Then, simulation result is shown in Figure 4.9b.From the result, we observe that by considering closeness in the task offloading process, the success rateis improved, which indicates that by considering the closeness the system performance will be improved.To summarize, the task allocation process is showed to be having a positive performance. Thesystem could be benefited from existence of the cloudlet(s), as well as considering the mobile socialcloseness in the offloading process.460.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 14.24.254.34.354.44.45x 106System Resource UsageDensity  With CloudletWithout Cloudlet(a) Various Degrees of Density0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 14.264.284.34.324.344.364.384.44.424.444.46x 106System Resource UsageSkewness  With CloudletWithout Cloudlet(b) Various Degrees of SkewnessFigure 4.8: System Resource Usage With and Without The Assistance From The Cloudlet(s)47Table 4.4: Evaluation Setup Parameters: Cooperative Task AllocationTarget Parameter Minimum MaximumBase Case Device(s), Cloud, and Cloudlet(s) 50 350Task(s) FactorsStorage Consumption 0.9 1.05CPU Consumption 0.9 1.05Task Duration (Deadline) 0.5 0.5Amount Of Data Sent 5 5Bandwidth Consumption 1 1Amount Of Data Received 5 5User(s) / Device(s) FactorsStorage Availability 1 1CPU Availability 1 1Energy Availability 0.5 0.5Energy Consumption (/ unit time) 0.5 0.5Game Progress Speed 1 10Cloudlet(s) FactorsStorage Availability 20 20CPU Availability 20 20Energy Availability 1 1Energy Consumption (/unit time) 0.1 0.1Local Level OffloadingShort On-Device Execution Time 0.5 0.5Long On-Device Execution Time 5 5Device-Device Data Transmission Costs 10 10Device-Cloudlet Data Transmission Costs 20 20Link Delay 1 2Device-Cloud OffloadingTask Execution Time 0.1 0.1Device-Cloud Data Transmission Costs 30 30Link Delay 10 20Network TopologyDensity 1 10Skewness 1 10Task Density 1 10Weight FactorsEnergy Costs 0 1Bandwidth Consumption 0 1Interactive Latency 0 148100 101 102 10310−410−310−210−1100ClosenessUser  Closeness Between Users(a) Closeness DistributionSuccess Rate (%)Task Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 19797.59898.59999.5Without closenessWith Closeness(b) Success Rate with/without ClosenessFigure 4.9: Task Allocation with Mobile Social Closeness for Map-based Movement49Chapter 5Performance AnalysisIn the previous chapters, the progressive downloading and cooperative task allocation processes areintroduced separately. Yet, in order to give an overall system analysis, we need to integrate these twoprocesses and see how they work together. In this chapter, we examine how the system works with thegame type integrating these two processes, compare the system performance with existing architectures,and discuss the system overhead.5.1 System WorkflowAs previously mentioned, in the targeted component-based game model, the behavior of game entitiesare defined by their registered game components. These components could be removed or added to theentity in the runtime, thus changes the behavior of the entity during game-play. Then, in component-based progressive games, the progressive downloading is a continuous process, yet works on demand:only a minimal proportion of the componentized game resources are needed for the users to get thegame up and running, while the rest of the resources are continuously downloaded to users’ mobiledevices during game-play. To be more specific, only the components needed for the current gameprogress are downloaded as a starting point for execution, while the rest is downloaded as requested(e.g., when reaching the new difficulty level in mobile games), with the components being added to theentities in the runtime. Both the cloudlet(s) and devices in ad hoc mobile cloud are considered to becomplementary downloading sources depending on their game progresses and resources owned. Similarconcept could be applied to the cooperative task allocation, since all users in the network downloadgame resources progressively, tasks could only be distributed to users (and the cloudlet(s)) who alreadyhave the associated game components downloaded for execution. To put it differently, in the proposed50architecture, both the downloading and task offloading requests could only be distributed to the adhoc neighbours who have faster game progresses, or the cloudlet(s) only if it has the requested gamecomponents, otherwise the requests should be delegated to the cloud. This is straight forward in theprogressive downloading process since it is the process itself that checks the users’ game progress todetermine the best downloading source. In the contrast, the task allocation process needs to be notifiedabout the users’ game progress. To do this, we could simply make the progressive downloading processto notify the cooperative task allocation process by setting the parameter A in the cooperative taskallocation, which is the indicator of users’ availability to indicate whether the certain ad hoc neighbourhas the required game resources.For example, when the local game reaches a new progress level, the progressive downloading pro-cess first determine the set of users in the ad hoc mobile cloud who have faster game progress than local,set them as potential downloading sources, and notify the task allocation processing by setting Ai = 1,which indicates that the components needed for local game progress is available at user µi. Then, theprogressive downloading and cooperative task allocation works in parallel and on demand until newdifficulty level is reached.5.2 Comparison to Existing ArchitecturesIn this section, we compare the performance of the task allocation process with 1) the conventionalcloud based architecture, where all computation tasks are offloaded to the cloud; 2) the mobile codeoffloading based architecture (ThinkAir) proposed in [28] where computation tasks are offloaded to thecloud according to its task offloading policy: computation tasks are offloaded to the cloud only if boththe task execution time and the energy consumed to carry out the computation will improve (reduce).To give a comprehensive comparison and analysis of the system performance, the effect of different on-device task duration on the system performance is evaluated by using real-world movement trace basednetwork topology. In the simulation, we consider task-reassignment, where each task that is allocatedto ad-hoc neighbors yet failed to return computation results before the task deadline are re-assigned.We then simulate the task allocation process with both short on-device task duration and long on-device51task duration for different task density (the probability of users having tasks to offload at each time slot).The results for system resource usage, energy costs, bandwidth consumption, and interactive latency pertask are compared with the previously mentioned existing architectures.The simulation results for short on-device task duration are shown in Figure 5.1a, Figure 5.2a, Fig-ure 5.3a, and Figure 5.4a respectively. From the figures we can see that the system resource usage,the energy costs, the bandwidth consumption, and the interactive latency incurred by our proposed al-gorithms increase as the task density increase yet at a decreasing rate. This is because: 1) at a highertask density, more tasks in percentage are offloaded to the cloud; 2) at a lower task density, more tasksin percentage are offloaded to the ad hoc mobile cloud, and therefore higher system resource usage,the energy costs, the bandwidth consumption, and the interactive latency (this phenomenon is furtherexplained in the next section). Also, we observe that our task allocation mechanism has lower systemresource usage, energy costs and interactive latency than both the conventional cloud based architectureand the ThinkAir. In our mechanism, we consider two types of bandwidth consumption, both device-to-device (for tasks offloaded to the ad hoc mobile cloud) and device-to-cloud (for tasks offloaded tothe cloud). From the result, we see that our mechanism has higher overall bandwidth consumption thanthe ThinkAir, yet lower device-to-cloud bandwidth consumption. This is because that in our mecha-nism, tasks are distributed within the ad hoc mobile cloud, which eaten up the device-to-device networkbandwidth. However, as the available device-to-device bandwidth is considered to be large and muchcheaper than as in the cellular networks, this result is acceptable.Then, the simulation results for long on-device task duration are shown in Figure 5.1b, Figure 5.2b,Figure 5.3b, and Figure 5.4b. From the figures, we can see that our mechanism has 1) lower interactivelatency than both the conventional cloud based architecture and the ThinkAir; 2) higher system resourceusage and energy costs. This is because in this scenario, the ThinkAir offload more tasks to the cloud,whereas our mechanism prioritizes the ad hoc mobile cloud in the offloading process, therefore higherenergy costs are incurred by our mechanism with longer on-device task duration. Also, although theoverall bandwidth consumption is higher than the ThinkAir, our mechanism has lower device-to-cloudbandwidth consumption due to ad hoc mobile cloud collaboration. As the design goal of our architectureis to utilize the resources of the ad hoc mobile cloud and the cloudlet(s) to achieve reduced data trans-52System Resource UsageTask Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 11.51.61.71.81.922.12.2x 106Greedy LocalRandom MappingGreedy HeuristicOptimalSolution From ThinkAirConventional Cloud Gaming(a) Short On-Device Execution TimeSystem Resource UsageTask Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 122.022.042.062.082.12.122.142.162.18x 106Greedy LocalRandom MappingGreedy HeuristicOptimalSolution From ThinkAirConventional Cloud Gaming(b) Long On-Device Execution TimeFigure 5.1: System Resource Usage with Map-based Movementmission between end users and the distant cloud, it is safe for as to say that the design goal is met. Also,from the results shown above, we observe that our proposed scheme performs better in the scenario withshort on-device task duration.53Energy CostsTask Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 13.844.24.44.64.855.25.45.6x 106Greedy LocalRandom MappingGreedy HeuristicOptimalSolution From ThinkAirConventional Cloud Gaming(a) Short On-Device Execution TimeEnergy CostsTask Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 14.9555.055.15.155.25.255.35.355.45.45x 106Greedy LocalRandom MappingGreedy HeuristicOptimalSolution From ThinkAirConventional Cloud Gaming(b) Long On-Device Execution TimeFigure 5.2: Energy Costs with Map-based Movement5.3 Overhead and BenefitAlthough the proposing three-tier architecture are shown to be beneficial in terms of reducing device-to-cloud cellular data transmission, enabling cloudlet(s) and ad hoc mobile cloud offloading brings ad-54Bandwidth ConsumptionTask Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 12426283032343638Greedy LocalRandom MappingGreedy HeuristicOptimal: overallSolution From ThinkAirConventional Cloud GamingOptimal: device−cloud(a) Short On-Device Execution TimeBandwidth ConsumptionTask Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 13535.53636.53737.538Greedy LocalRandom MappingGreedy HeuristicOptimal: overallSolution From ThinkAirConventional Cloud GamingOptimal: device−cloud(b) Long On-Device Execution TimeFigure 5.3: Bandwidth Consumption with Map-based Movementditional system usage, i.e., additional device-to-device bandwidth consumed for transmitting task pa-rameters, for the computation results to be returned, as well as the additional energy used to supportthe device-to-device transmission. Then, in order to give a comprehensive analysis of the system per-formance, it is important to show that the benefit realized by users outweigh this additional overhead.55Interactive LatencyTask Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 13.23.43.63.844.24.44.6x 104Greedy LocalRandom MappingGreedy HeuristicOptimalSolution From ThinkAirConventional Cloud Gaming(a) Short On-Device Execution TimeInteractive LatencyTask Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 14.24.254.34.354.44.454.54.55x 104Greedy LocalRandom MappingGreedy HeuristicOptimalSolution From ThinkAirConventional Cloud Gaming(b) Long On-Device Execution TimeFigure 5.4: Interactive Latency with Map-based MovementFigure 5.5a shows that the overall system resource usage per unit task measured in the cooperative taskallocation process. The simulation result (greedy local) shows that the usage/task increases as the taskdensity increases yet at a decreasing rate. To further understand the underlying reason for such phe-nomenon, we measure and show the system resource usage for the device-to-device and device-to-cloud56System Resource Usage/TaskTask Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1102103104105106107Greedy LocalLocal OverheadCloud OverheadConventional Cloud Gaming(a) System Resource Usage/Task in Cooperative Task AllocationTask (%)Task Density  0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10102030405060708090100Tasks Offloaded To Local DevicesTasks Offloaded To The Cloud(b) Tasks (%) being offloaded to the Ad hoc Mobile Cloud and the CloudFigure 5.5: Overhead and Benefit of the Systemtransmission separately, as well as the task in percentage that is offloaded to the cloud and the ad hocmobile cloud. The results are also shown in Figure 5.5a and Figure 5.5b, respectively.From Figure 5.5a, we see that the usage/task for device-to-cloud transmission increases at a de-creasing rate, while the usage/task for device-to-device transmission decreases at a decreasing rate. This57means that as task density increases, the tasks in percentage being offloaded to the cloud also increasesand the tasks in percentage being offloaded to the ad hoc mobile cloud decreases, which indicates that theresources of ad hoc mobile cloud are being efficiently utilized (This conclusion is also demonstrated inFigure 5.5b. However, the increasing/decreasing system resource usage for device-to-cloud/device-to-device transmission converges, which indicates that the resources in ad hoc mobile cloud are becomingfully utilized as the task density increases. The benefit of the system is the notably reduced systemresource usage incurred by the device-to-cloud transmission as compared to the conventional cloudgaming, while the system overhead being the additional usage incurred by the device-to-device trans-mission. Considering the system has a decreasing device-to-device usage as the task density increases,and the usage incurred by the device-to-device transmission is relatively small, along with the fact thatthe device-to-device transmission is often considered being fast and cheap [34], it is reasonable for usto conclude that this overhead is the acceptable performance trade-off.58Chapter 6Conclusion and Future Work6.1 ConclusionIn this thesis, we have proposed a three-tier peer-assisted mobile gaming architecture, which considersboth progressive and collaborative downloading of game resources as well as cooperative task pro-cessing. Instead of offloading purely to the cloud as in the conventional cloud gaming services, ourarchitecture offloads tasks to devices in vicinity, including devices in ad hoc mobile cloud (formed byusers) and nearby stationary cloudlet(s). Then, the cloud acts only as a backup processing utility whichis to be used when no local resources are available. By enabling user-level cooperation, we are aimingat improving the Quality of Service (QoS) and Quality of Experience (QoE) of the system, in terms ofreduced device-to-cloud data transmission, energy consumption, and interactive latency. However, asmentioned earlier in the thesis, these three objectives are conflicting, which means that they could notbe simultaneously achieved without degrading the others. Thus, in the optimization problem, we assigna weight factor to each objective to reflect its relative importance. These weight factors are pre-set bythe system and could be later altered by uses to suit their personal needs. By opening the weight factorsto users, the proposing system provides a customized game-play experience, while having improvedQoS and QoE. In this thesis, we have considered both the progressive downloading and cooperativetask allocation schemes as optimization problems and introduced them as separate chapters (Chapter3 and Chapter 4, respectively), including the problem modelling, algorithms, and the evaluations. Forboth schemes, we have carried out simulations to evaluate the performance using proposed algorithmsunder different network environment settings. The results show that our proposed algorithms have near-optimal performance. Also, different algorithms could be applied to obtain a better system performance,e.g., in a more balanced, connected network environment, the greedy local algorithm tends to minimize59the system resource usage. In a word, our proposed scheme minimizes the data transmissions betweenthe cloud and the users, and optimizes the local cooperations between the users in a best effort manner.Moreover, to give a comprehensive analysis of system performance, in Chapter 5, we have introducedthe integrated (progressive downloading and cooperative task allocation) system work-flow, explainedhow the system works with the targeting game model and game type, compared the system performancewith current existing architectures, and finally discussed the system overhead. Again, simulations areused to evaluate the performance. The results show that our proposed algorithms have lower systemresource usage with short on-device task duration as compared to those without our framework. Also,the benefits of the system out-weight the system overhead.6.2 Future WorkAs mentioned earlier in this thesis, the offloading process of the proposing system does not considertask dependencies. However, task dependencies are performance killers under some circumstances. Forexample, data dependencies have inevitable impact on bandwidth consumption, while real-time depen-dencies have impact on system responsiveness. Thus, as a future work, task dependencies should becarefully and heavily considered in the offloading process. Once the task dependencies are integrated,the proposing system could easily be used with broader game types, i.e., games with high computationcost and responsiveness (i.e., First Person Shooting Games), and will be more applicable to users. Onthe other hand, the proposing system could be improved in terms of system scalability, system overhead,and system openness. To be more specific, the scalability of proposing system is acceptable, since bothprogressive downloading and cooperative task allocation are decentralized decision-making processes.Yet, the system overhead need to be carefully managed. In fact, there are different types of overhead inthe system. First, enabling cloudlet(s) and ad hoc mobile offloading brings additional system usage, i.e.,additional device-to-device bandwidth and energy consumption. Second, the run-time overhead, whichis the overhead caused by membership (users’ game statuses) management and game state management.We have already demonstrated that the first type overhead could be out-weighted by the system bene-fit, yet, investigations into second type overhead are as needed. Therefore, efficient and decentralized60service discovery, device discovery, and membership management mechanisms should be carefully de-signed to ensure the scalability of the system, along with minimized system overhead, which will beconsidered as future works. To summarize, this thesis could be considered as a starting point for theproposing system, more works need to be done in order for the system to be complete.61Bibliography[1] H.T. Dinh, C. Lee, D. Niyato, and P. Wang, "A survey of mobile cloud computing: Architecture,applications, and approaches", in Wireless Communications and Mobile Computing, vol.13, no.18,pp. 1587-1611, 25 December 2013.[2] C. Zhu, V. C. M. Leung, X. Hu, L. Shu, and L. T. Yang, "A review of key issues that concern thefeasibility of mobile cloud computing", in IEEE International Conference on Cyber, Physical andSocial Computing P (IEEE CPSCom), Beijing, China, August 2013.[3] C. Huang, C. Hsu, Y. Chang, and K. Chen, "GamingAnywhere: An open cloud gaming system",in ACM Multimedia Systems Conference, Oslo, Norway, February/March 2013.[4] M. Claypool, D. Finkel, A. Grant, and M. Solano, "Thin to win? Network performance analysisof the onlive thin client game system", in 11th Annual Workshop on Network and Systems Supportfor Games (NetGames), Venice, Italy, November 2012.[5] R. Shea, J. Liu, E. Ngai, and Y. Cui, "Cloud gaming: architecture and performance", in IEEENetwork, vol. 27, no. 4. July-August 2013.[6] K. Chen, Y. Chang, P. Tseng, C. Huang, and C. Lei, "Measuring the latency of cloud gamingsystems", in 19th ACM international conference on Multimedia (MM ’11), Scottsdale, Arizona,USA, November-December 2011.[7] W. Cai and V. C.M. Leung, "Decomposed Cloud Games: Design Principles and Challenges”, inIEEE International Conference onMultimedia and Expo (ICME2014), Chengdu, China, July 2014.[8] D. Meilander, F. Glinka, S. Gorlatch, L. Lin, W. Zhang, and X. Liao, "Bringing Mobile Online62Games to Clouds", in IEEE INFOCOM Workshop on Mobile Cloud Computing, Toronto, Canada,April 2014.[9] F. Liu, P. Shu, H. Jin, L. Ding, J. Yu, D. Niu, and B. Li, "Gearing resource-poor mobile devices withpowerful clouds: architectures, challenges, and applications", in IEEE Wireless Communications,vol.20, no.3, pp.14-22, June 2013.[10] Y. Li and W. Wang, "The unheralded Power of Cloudlet Computing in the Vicinity of MobileDevices", in IEEE Global Communications Conference (Globecom’ 13), Atlanta, GA, USA, De-cember 2013.[11] S. Pushp, C. Liu, F. Liu, and J. Song, "Multi-Player Gaming in Public Transport Crowd: Op-portunities and Challenges", in IEEE World Forum on Internet of Things, Seoul, Korea, March2014.[12] S. Phithakkitnukoon and R. Dantu, "Mobile Social Closeness and Communication Patterns", inIEEE Consumer Communications and Networking Conference (CCNC), Las Vegas, NV, USA,January 2010.[13] M. Satyanarayanan; P. Bahl, R. Caceres, and N. Davies, "The Case for VM-Based Cloudlets inMobile Computing", in IEEE Pervasive Computing, vol.8, no.4, pp.14-23, October-December.2009[14] Y. Jararweh, L. Tawalbeh, F. Ababneh, and A. Khreishah. "Scalable Cloudlet-based Mobile Com-puting Model", in Procedia Computer Science, vol. 34, no. 0, pp.434-441, 2014[15] T. Soyata, R. Muraleedharan, C. Funai, K. Minseok, W. Heinzelman, "Cloud-Vision: Real-timeface recognition using a mobile-cloudlet-cloud acceleration architecture", in IEEE Symposium onComputers and Communications (ISCC), Cappadocia, Turkey, July 2012.[16] K. Lorenzo, L. Anh, and C. Blerim. "MicroCast: Cooperative Video Streaming on Smartphones”,in 10th International Conference on Mobile Systems, Applications, and Services, Low Wood Bay,Lake District, United Kingdom, June 2012.63[17] J. Wang, S. Wang, Y. Sun, W. Lu, and D. Wu, "An incentive mechanism for cooperative down-loading method in VANET”, in IEEE International Conference on Vehicular Electronics and Safety(ICVES), Dongguan, China, July 2013.[18] B. Yang, A.R. Hurson, and Y. Jiao, "On the Content Predictability of Cooperative Image Cachingin Ad Hoc Networks", in International Conference on Mobile Data Management, Nara, Japan,May 2006.[19] L. Lao and JH, Cui, "Reducing Multicast Traffic Load for Cellular Networks using Ad Hoc Net-works", in 2nd International Conference on Quality of Service in Heterogeneous Wired/WirelessNetworks, Lake Vista, FL, 2005[20] W. Cai, V. C.M. Leung, and L. Hu, "A Cloudlet-assisted Multiplayer Cloud Gaing System”, inACM Springer Mobile Networks and Applications (MONET), vol. 19, No.2, pp. 144-152, April2014.[21] M. Conti, S. Giordano, M. May, and A. Passarella, "From opportunistic networks to opportunisticcomputing", in IEEE Communications Magazine, vol.48, no.9, pp.126-139, September 2010.[22] M. Musolesi and C. Mascolo, "Designing mobility models based on social network theory", inACM SIGMOBILE Mobile Computing and Communication Review, vol.11, no.3, pp.59-70, July2007.[23] Y. Ren, Y. Chen, and M.C. Chuah, "Social Closeness Based Clone Attack Detection for Mo-bile Healthcare System",in IEEE International Conference on Mobile Adhoc and Sensor Systems(MASS), Las Vegas, NV, United States, October 2012.[24] M. Joselli, M. Zamith, J. Silva, L. Valente, E. Clua, B. Feijo, and R. C. P. Leal-Toledo, "An Ar-chitecture for Mobile Games with Cloud Computing Module”, in SBGames, Brazilian, November2012.[25] H.Flores, P.Hui, S.Tarkoma, Y.Li, S.Srirama, and R.Buyya, "Mobile Code Offloading: From Con-64cept to practice and Beyond", in IEEE Communications Magazine, Vol.53, no.3, pp.80-88, March2015.[26] E. Cuervo, A. Balasubramanian, D.K. Cho, A. Wolman, S. Saroiu, R. Chandra, and P. Bahi,"MAUI: Making Smartphones Last Longer with Code offloading", in 8th international conferenceon Mobile systems, Applications, and services, San Francisco, CA, USA, June 2010.[27] B.G. Chun, S. Ihm, P. Maniatis, M. Naik, and A. Patti, "CloneCloud: Elastic Execution betweenMobile Device and Cloud", in 6th conference on Computer Systems, Salzburg, Austria, April 2011.[28] S. Kosta, A. Aucinas, P. Hui, R. Mortier, and X. Zhang, "ThinkAir: Dynamic resource allocationand parallel execution in the cloud for mobile code offloading", in IEEE International Conferenceon Computer Communications, Orlando, Florida United States, March 2012.[29] A. Tagliasacchi, R. Dickie, A. Couture-Beil, M.J. Best, A. Fedorova, and A. Brownsword, "Cas-cade: A Parallel Programming Framework for Video Game Engines", in the Workshop on ParallelExecution of Sequential Programs on Multi-core Architectures (PESPMA), in conjunction withISCA, Beijing, China, 2008.[30] J. Andrews, “Designing the framework of a Parallel Game Engine”, Intel, January, 2015.[31] N. Zhang, Y. Lee, M. Radhakrishman, and R.K. Balan, "GameOn: p2p Gaming on Public Trans-port", in 13th Annual International Conference on Mobile Systems, Applications, and Services,Florence, Italy, May 2015.[32] B.Han, P.Hui, V.Kumar, M. Marathe, G.Pei and A. Srinivasan, "Cellular Traffic Offloading throughOpportunistic Communications: A Case Study", in 5th ACM workshop on Challenged Networks,Chicago, IL, USA, September 2010.[33] C.R. Palmer and J.G. Steffan, "Generating network topologies that obey power laws", inIEEE Global Telecommunications Conference (GLOBECOM ’00), San Francisco, United States,November/December 2000.65[34] Y. Li, L. Sun, and W. Wang,”Exploring Device-to-Device Communication for Mobile Cloud Com-puting”, in The IEEE International Conference on Communications (ICC ’14), Sydney, Australia,June, 201466

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0167800/manifest

Comment

Related Items