Grefenstette Bias based genetic algorithm for multi-site offloading using docker container in edge computing

Abstract

Generally, several IoT (Internet of Things) applications employ cloud data centre for processing the data generated by edge devices like smartphones and tablets. Due to the increasing use of the IoT devices, the demand for higher computational and communication capabilities are also increasing. With the advent of Edge Computing and given the fact that computational capabilities are currently untapped, a part of the computational load can be offloaded to the edge nodes. In this paper, a Grefenstette bias based Genetic Algorithm for MultiSite Offloading (GGA-MSO) is proposed. This algorithm decides the schedule of the application that could be offloaded. The proposed algorithm provides a solution which has convergence in lesser time by employing diversification of initial population using the Grefenstette’s Bias method. Besides, the container based lightweight virtualization is analyzed for offloading code and data to the nearby devices. The evaluation of the proposed work on random graphs shows that the proposed method starts to converge with significantly lesser iterations than its counterpart with undiversified population. The test bed results on Single Board Computers (SBC) like Raspberry Pi setup indicates that by adapting container virtualization in the edge environment, the performance of the IoT devices is improved and the communication overhead is reduced.

Keywords

Internet of things (IoT)edge computing computation offloading application partitioning Docker container raspberry Pi

1 Introduction

Today’s world is filled with mobile devices, and are connected to the internet for creating smarter environment. Such devices are commonly referred to as Internet of Things (IoT). In the past decade, cloud computing technology helped to create a smarter environment by leveraging the processing and the storage needs of mobile devices. Augmented reality, natural language processing, gaming, face recognition and image processing are some typical IoT applications [1 –3]. These applications are computation intensive and devices are often resource constrained. In spite of many efforts like incorporating multi-core processors the resources requirement still continues to grow. Computation offloading as a framework is useful in such a scenario. It offloads the computationally intensive part to resource rich systems that are referred to as Mobile Cloud Computing (MCC) or cyber foraging or surrogate computing [4]. Several offloading cloud infrastructure frameworks [5, 6] have been proposed by researchers that use the cloud infrastructure for executing computation-intensive applications on mobile devices like smartphones.

However, with the unprecedented proliferation of IoT devices, cloud computing faced serious challenges in the areas of bandwidth requirement and latency response. Many IoT applications require a response time of a few milliseconds. In order to meet this requirement, a new technology called Edge or Fog or Cloudlet computing [7, 8] was introduced as a supplement to cloud computing technology. Edge computing is a technology that brings in the computation and storage capabilities proximate to the end devices, thereby addressing the bandwidth and latency response issues [9]. A roadside traffic unit may be an edge device wherein there is an edge between a vehicle’s OBU and cloud. Similarly, Cloudlet or Clonecloud acts as an edge between smartphones and cloud. The edge computing framework is in its infancy stage but it still offers many benefits. It offloads the computation intensive part to the edge or nearby devices [10, 11].

In a MCC offloading framework environment, the mobile devices are connected to a high performance server that supports efficient computation offloading. Most of the previous works done in the area; focus on finding an optimal partitioning solution for a single site offloading involving the end device and the cloud. However, the multisite offloading solution will be feasible for edge environments to share computation resources between the surrogates and may lead to significant improvement in terms of performance and energy consumption of mobile devices as shown in Fig. 1.

Fig.1

Offloading Scenarios.

Therefore, in this work multi-site offloading optimization strategy model is considered, and the decisions are made by analyzing parameters like bandwidth, surrogates speed, available memory, loads on the surrogates, and the amount of data exchanged between surrogates and mobile systems. Due to NP-complete decision nature of the problem, it is difficult to design the multisite offloading problem and solve it in polynomial time. In order to resolve this, a Genetic Algorithm (GA) based multisite application partitioning algorithm is proposed, which automatically decides the part of the application to be offloaded to a particular site. Besides most of the existing computational offloading mechanisms [12] depend on virtualization technologies like application level virtualization, hardware virtualization or code migration techniques [13 –15]. Adapting such techniques in an edge offloading environment is a cumbersome process because the edge or nearby surrogates are resource limited environments. An alternate lightweight virtualization called OS level virtualization like Docker container is used in this work for offloading the computation part to the nearby surrogates. Other such similar containers include LXC, Open VZ and Imctfy [16 –18].

The main contributions of this work are:

Offloading decision algorithm for edge environment using Grefenstette’s Bias in GA to achieve optimal partitioning and faster convergence

A test bed set-up to evaluate the offloading decisions by adopting Docker container virtualization

The rest of the paper is organized as follows: Section 2 outlines the existing studies that are closely related with the present work. The preliminaries necessary for the offloading algorithm is discussed in section 3. Sections 4 and 5 present the proposed GGA-MSO algorithm and discuss the results obtained. The concluding chapter presents some useful insights on the topic and suggests possible future enhancements.

2 Related works

Many computation intensive applications are benefitted from computation offloading. Most of the articles produced on this subject focus on mobile applications and demonstrate better performance, efficient power consumption and minimization in execution time with the help of offloading. Some of such key articles and their details are tabulated in Table 1.

Table 1
Related works based on offloading

Ref. No Partitioning Category Optimization Strategy Granularity Application

[19] Dynamic Heuristic algorithm Task level Random graph

[13] Dynamic Lyapunov optimization Task level Word processing

[20] Dynamic Partitioning algorithm Method Mobile app, Bench image

[2] Dynamic EDP + Highest Response Ratio Next (HRRN) Method Face detection and Path finding

[3] Dynamic IPDC (Interior Penalty function with DC) Method Monte Carlo methods

[21] Static Mirror mechanism Entire app Virus scanning

[22] Dynamic Mixed Linear Programming Method Vehicles

[23] Static OMPSO (Optimized Multisite Particle Swarm Optimization) Task level JESS, DB

[24] Dynamic Decision making Method Real time surveillance

[25] Dynamic Decision making Method Android applications

[26] Dynamic Decision making Task level Intrusion detection system

[27] Dynamic Game theoretic Method Random Graph

[28] Dynamic Heuristic Code Gesture,traffic light

[29] Static Genetic algorithm Method Smart grids

[30] Dynamic Min-cut model Method FFT, encoded &decoded benchmark

[31] Dynamic Fuzzy based decision Making – Image and text editor

[32] Dynamic Distributed Execution Transformer (DiET) Method Scimark

[4] Dynamic (k+1) Partitioning using HELVM Class Video analytics

[33] Dynamic Decision making Method Java text editor

[34] Dynamic (K+1) Partitioning algorithm Component Language translation and character recognition

[35] Dynamic Min-cut based heuristic Class Image and text processing

Ref. No	Partitioning Category	Optimization Strategy	Granularity	Application
[19]	Dynamic	Heuristic algorithm	Task level	Random graph
[13]	Dynamic	Lyapunov optimization	Task level	Word processing
[20]	Dynamic	Partitioning algorithm	Method	Mobile app, Bench image
[2]	Dynamic	EDP + Highest Response Ratio Next (HRRN)	Method	Face detection and Path finding
[3]	Dynamic	IPDC (Interior Penalty function with DC)	Method	Monte Carlo methods
[21]	Static	Mirror mechanism	Entire app	Virus scanning
[22]	Dynamic	Mixed Linear Programming	Method	Vehicles
[23]	Static	OMPSO (Optimized Multisite Particle Swarm Optimization)	Task level	JESS, DB
[24]	Dynamic	Decision making	Method	Real time surveillance
[25]	Dynamic	Decision making	Method	Android applications
[26]	Dynamic	Decision making	Task level	Intrusion detection system
[27]	Dynamic	Game theoretic	Method	Random Graph
[28]	Dynamic	Heuristic	Code	Gesture,traffic light
[29]	Static	Genetic algorithm	Method	Smart grids
[30]	Dynamic	Min-cut model	Method	FFT, encoded &decoded benchmark
[31]	Dynamic	Fuzzy based decision Making	–	Image and text editor
[32]	Dynamic	Distributed Execution Transformer (DiET)	Method	Scimark
[4]	Dynamic	(k+1) Partitioning using HELVM	Class	Video analytics
[33]	Dynamic	Decision making	Method	Java text editor
[34]	Dynamic	(K+1) Partitioning algorithm	Component	Language translation and character recognition
[35]	Dynamic	Min-cut based heuristic	Class	Image and text processing

From the related studies, it transpires that many works focus on single site offloading, i.e. they execute either on a local device or a cloud data centre. Additionally, many offloading frameworks depend on system virtualization, application virtualization or code migration to execute the offloaded code on to the cloud server. These works are proposed for the MCC environment but they may not be suitable for the edge environment as the application’s part can also be offloaded to multiple devices, i.e. multisite offloading need to be considered. A few research works have focused on multisite offloading but still in its undeveloped stage. Considering all these, the proposed study uses GGA-MSO to perform multisite offloading and the results obtained are evaluated in an edge environment using a light weight virtualization technology called Docker container virtualization for offloading the computation intensive part to the nearby devices.

3 Problem formulation

3.1 System architecture

A decision algorithm is designed to schedule, the offloadable and non-off loadable components in an application such that the total energy consumption of the mobile device and execution time of an application is reduced. Certain components cannot be offloaded due to security issues or due to their interaction with the hardware devices like cameras, sensors and GPS and some components have to be executed locally or by the remote system.

Figure 2 shows the system flow of the proposed work. It can be seen that the application running on any mobile device can be modelled as Task Interaction Graph (TIG) with the help of a profiler (hardware and software tools) [36]. The TIG is formulated as a weighted graph as shown in Fig. 3. Each node in a graph represents the computational task and the edges represent the control dependences between the tasks. The weighted graph is fed as an input to the decision making engine that will decide which part of the application’s module has to be offloaded to which nearby device. Based on the decisions, the offloadable task and its data are sent as Docker images to the nearby devices by adopting Docker container virtualization.

Fig.2

Offloading Framework.

Fig.3

a) Comparison of Composite Cost of Different Model with 10 Modules and 8 Sites. b) Comparison of Composite Cost of the Proposed work with PSO.

3.2 Evaluation parameters for offloading

To guarantee that the offloading will be profitable, a suitable offloading optimization strategy is adopted for the reduction of execution time and power consumption. If T_d is the time taken by a task to transmit the data, T_S is the time taken by a task to execute on remote site and T_m is the time taken to execute on the mobile device then offloading will be beneficial if T_d + T_s > T_m. Similarly, for efficient energy consumption, the task can be offloaded if the energy required on mobile is greater than offloading, i.e. E_offload < E_Loc, where E_offload = E_Net + E_idle, E_Net – Energy required to transmit a data, E_idle – Energy required to be in idle till response from a server. The parameters that are essential to make the offloading decision are:

The execution time of task i on a mobile device j can be represented as shown in Equation (1) $T_{ij} = T_{CPUcycle} / {freq}_{i}$ (1)T_ij - Time is taken to execute the task i on device j

T_CPUcycle - Number of instructions

freq_j - represents the frequency at which device j run

By adopting Dynamic Voltage and Frequency Scaling (DVFS) [37, 38], an appropriate frequency can be used to balance the power consumption and reduction in execution time.

Similarly, memory availability, current CPU load and battery discharge are the other essential parameters to be considered while making a decision. To avoid the computational complexity for each vertex, a composite weight is assigned as expressed in Equation 2. Each vertex has multiple weights as ${CW}_{i}^{0}, {CW}_{i}^{1}, {CW}_{i}^{2}, {CW}_{i}^{3} \dots {CW}_{i}^{m},$ where ${CW}_{i}^{0}$ represents the composite weight of vertex V_i on site₀ $CW (V_{j}^{i}) = α_{1} T_{ij} + α_{2} {Mem}_{j} + α_{3} CPU_{load}_{j}$ (2)

To compute the communication cost, the edge weight can be denoted as $[{EW}_{v_{1} v_{2}}^{00},$ ${EW}_{v_{1} v_{2}}^{01}, \dots, {EW}_{v_{1} v_{2}}^{0 m}, {EW}_{v_{1} v_{2}}^{01}, {EW}_{v_{1} v_{2}}^{10}, \dots$ ${EW}_{v_{1} v_{2}}^{mm},]$ where ${EW}_{xy}^{ij}$ represent the communication cost when task i executes on site x and task j executes on site y. The edge weight can be computed as shown in Equation 3: ${EW}_{v_{i} v_{j}}^{xy} = \frac{data_i n_{ij}^{xy}}{B_{uplink}} + \frac{data_o {ut}_{ij}^{xy}}{B_{downlink}}, i \neq j .$ (3) $data_i n_{ij}^{xy}$ - represents data sent from task i on site x to task j on site y

B_link- Bandwidth

The energy consumption required to execute a task j on mobile device i can be represented as E_i,j as in Equation (4) $E_{i, j} = T_{i, j} * P_{cpu}$ (4)

P_cpu-Power required for executing single instruction cycle

With these input parameters the offloading algorithm aims at finding the optimal partitioning by minimizing the execution cost and the power consumption of a device and it formulated as, $min (W) = β_{1} * \frac{T}{T_{local}} + β_{2} * \frac{E}{E_{local}}$ (5) where T and E represents the execution time and energy consumption of an application during offloading and T_local & E_local represents the execution time and energy consumption of an application in the mobile device. If the weighted optimization model corresponds to the execution time then β₂ = 0 or for energy consumption model then β₁ = 0 or both to be considered then β₁ = 0.5 and β₂ = 0.5.

The optimization execution model (T) can be calculated as shown in Equation (6) by considering the composite weight and communication cost as,

$\begin{matrix} T & = & \sum_{i = 1}^{n} [(α_{i}^{s} * {CW}_{i}^{local} + (1 - a_{i}^{s}) * {CW}_{i}^{remote})] \\ + \sum_{i = 1}^{n} \sum_{j = 1}^{n} {EW}_{v_{i} v_{j}}^{xy} \end{matrix}$ (6)

Where $\begin{matrix} j \in adj (i), n - # of modules, x \neq y, and a_{i}^{s} = \\ {\begin{matrix} 1, s = local \\ 0, & s \in (s_{1}, s_{2}, \dots, s_{n}) \end{matrix} \end{matrix}$

Similarly the energy consumption model E can be calculated as shown in Equation (7) as,

$\begin{matrix} E & = & \sum_{i = 1}^{n} [(α_{i}^{s} * E_{i}^{local} + (1 - α_{i}^{s}) * E_{i}^{remote})] \\ + \sum_{i = 1}^{n} \sum_{j = 1}^{n} {TE}_{v_{i} v_{j} x \neq y}^{xy} \end{matrix}$ (7)

Where x ≠ y, j ∈ adj (i) and $α_{i}^{s} {\begin{matrix} 1, & s = local \\ 0, & s \in (s_{1}, s_{2}, \dots, s_{n}) \end{matrix}$

Where ${TE}_{v_{i} v_{j} x \neq y}^{xy}$ represent the transmission energy required when execution happens at different sites. In the proposed work the execution model is considered and results are discussed w.r.to that.

4 Proposed GGA-MSO algorithm

GGA-MSO is used to find the offloadable and non-off loadable components in an IoT application. In order to obtain an optimal solution, the characteristics and selection of genetic algorithm have to be fine-tuned and this is a difficult task. When using the genetic algorithm characteristics such as initial population, selection criteria, mutation probability, crossover probability, stopping criteria and fitness function are commonly addressed.

With the intent of meeting the requirements at hand, the proposed algorithm is divided into two phases as initialization and execution phases. During the initialization phase, the input values for the random graph and population generation will be carried out. In the execution phase, the genetic operators are applied after evaluating the fitness value. The overview of the proposed GGA-MSO is explained in algorithm 1.

4.1 Initialization phase

4.1.1 Random graph generation and the input data

The proposed work is evaluated using directed random graphs. The associated cost related with random graphs such as composite weight (CW (v)), bandwidth and adjacency matrix to show the relation between nodes is generated randomly.

Algorithm 1 - Overview of the Proposed Algorithm

ALGORITHM GENETIC (nos, nom, sop):

Input: nos, nom, sop

Output: Optimal partitioning cost.

iteration_count = 0

population = GENERATE-POPULATION(nos, nom, sop)

loop

fit = [0…population.length]

for i = 0 to population.length

fit [i] = FITNESS (individual, adjacency, cost, bandwidth)

new_population = SELECT (fit, population)

for x, y randomly chosen in new population CROSSOVER (x, y)

population = MUTATE (population, nos)

iteration_count = iterationcount+1

until iteration_count <threshold or global_fitness> = fitness_threshold

4.1.2 Initial population generation

The initial random population is an important characteristic because it is related to all the other parameters and operators, i.e. if the initial population of the genetic algorithm is diversified [39], then the algorithm has the best possibility of finding a global solution. In order to achieve this, the diversity can be done at the gene level, chromosome level or at the population level [40]. To determine the diversity, Grefenstette biased method is chosen. The bias measures suggested by Grefenstette to find the diversity at gene-level is expressed in Equation (8) as, $B (P) = \frac{1}{l . n} \sum_{j = 1}^{l} max {\sum_{i = 1}^{n} {NPop}_{ij}, \sum_{i = 1}^{n} (1 - {NPop}_{ij})}$ (8) where B(P) is the bias of the population P

l – chromosome’s length

n – Population Size, and NPop_ij is the normalized Jth-gene of the ith- chromosome. i.e., NPop_ij ∈ [0, 1].

In the proposed work, with the intent of ensuring the diversity a threshold value is taken. Whenever the diversity measure is less than or equal to the threshold value, then the population is considered as diversified. The criteria for choosing the threshold is stated as shown in Equation (9)

$B (P (t)) = \frac{1}{l . n} \sum_{j = 1}^{l} max {\sum_{i = 1}^{n} \frac{{Pop}_{ij}}{nos - 1}, \sum_{i = 1}^{n} (1 - \frac{{Pop}_{ij}}{nos - 1})}$ (9)

When the population is uniformly distributed, the above equation becomes

$\begin{matrix} \approx \frac{1}{l . n} \sum_{j = 1}^{i} {\frac{1}{(nos - 1)} \cdot \frac{(nos - 1) nos}{2} \cdot \frac{n}{nos}} \\ \approx \frac{n}{l . n} \sum_{j = i}^{l} = 1 {\frac{n}{2}} \\ \approx \frac{1}{2 . l} \sum_{j = i}^{l} 1 \\ \approx \frac{1}{2} \end{matrix}$

Where, Pop_ij denotes ith chromosome’s jth gene. Pop_ij ∈ [0, nos - 1]

nos: the number of sites

l: length of the chromosome.

n: population size.

The above result is an approximated value that is obtained by assuming that the number of sites is always a divisor of a number of chromosomes. However, this is not always true. Hence, the threshold value is taken as 0.5+ ∈. For example, if the size of the population is 8 then the number of sites is 4 and length of the chromosome is 8 4. An instance of the diversified population can be stated as, {(0,1,2,3) (1,2,3,0) (2,3,0,1) (3,0,1,2) (0,1,2,3) (1,2,3,0) (2,3,0,1) (3,0,1,2)} and the threshold for the population is obtained using Equation (9) as, $B (P) = \frac{1}{4 * 8} \sum_{j = 1}^{4} {\frac{1}{(4 - 1)} * \frac{(4 - 1) * 4}{2} * \frac{8}{4}} = 0.5$

In this way, the initial population is generated based on this diversified value. The time taken for generating the diversity in an initial population is negligible as the time expected in determining the diversity of initial population will be compensated with the number of iterations and the optimality of the solution.

4.2 Execution Phase

The fitness function for the population is calculated using Equation (6). At each step, the GGA-MSO algorithm tries to find a partitioning with a minimum composite weight than the previous iterations. Once the fitness functions are evaluated, the best chromosome is updated. The next set of the population is chosen by tournament selection method. During crossover, the selected chromosomes are combined to generate offspring. In the mutation step, the genes of the chromosomes are mutated using a predefined mutation rate of 0.2. The GGA-MSO is completed with predefined iterations or until it satisfies the prescribed threshold value.

5 Results and discussion

5.1 Random graph evaluation

Simulation experiments were done on random graphs with nodes as modules to evaluate the performance of the proposed GGA-MSO algorithm. The specification of the random graph and the parameters used are presented in Table 2. In order to ensure uniform results, each graph with different nodes such as 10, 50, 100, 200 are tested under two different sites, i.e. a graph with 10 nodes executes on 4 or 8 sites. At each step, the number of iterations is increased from 10 to 200 and a single iteration is run for an average of 20 runs. The following algorithms are compared with the proposed work to make an effective comparison:

Table 2
Specification of Random Graph and Parameters Used

Graph Vertex Site Parameter used Value

R1 10 4, 8 Composite Weight [1 to 200]

R2 50 4, 8 Bandwidth [1 to 200]

R3 100 4, 8

R4 200 4, 8

Graph	Vertex	Site	Parameter used	Value
R1	10	4, 8	Composite Weight	[1 to 200]
R2	50	4, 8	Bandwidth	[1 to 200]
R3	100	4, 8
R4	200	4, 8

Case 1: Exhaustive Search (ES)

Case 2: Application executes on local sites

Case 3: General Genetic Algorithm (GA)

Case 4: Proposed GGA-MSO algorithm

Case 5: Particle Swarm Optimization (PSO)

The obtained results are analyzed by varying the number of iterations, population size and bandwidth.

a. By Varying Iterations

Figure 3a shows that by diversifying the initial population, each iteration produces an optimal partitioning result when compared with the initial population that is not diversified. In most of the test cases, the proposed work starts to converge after 60th iteration onwards and produces optimal partitioning.

The results obtained are compared with the Exhaustive search (with all possible combinations). On an average, 95% accuracy is obtained using the proposed GGA-MSO method. Exhaustive search fails if the input size grows beyond ten modules as the number of iterations to be done is n^m (n - sites, m - modules). From the graph, it can be seen that the offloading will be beneficial than executing on a local device. From Fig. 3b the convergence rate of PSO is comparatively high compared to GA and GGA-MSO but it suffers from the fact that its exploration ability is not as high as Genetic and GGA-MSO because particles share information only with help of Global best value. It has a fast convergence towards local optimal solution but lacks in attaining global optimal solution. In Fig. 4, the results are normalized using the min-max normalization method and the results reveal that the proposed work starts to convergence earlier to find the global optimal solution when compared to the results that are not diversified.

Fig.4

Varying Iterations for Module 10, 50, 100 & 200 with 4 Sites.

b. By Varying Population Size and bandwidth Cost

Figure 5a presents the results obtained by changing the initial population size. It shows that the results are converged early to find the optimal solution when the size of the population increases. Figure 5b shows the results obtained by varying the bandwidth between the sites. It shows the results for the graph with 50 modules and 8 sites. When the bits transferred rate is lower, the composite cost increases. So it is better to offload whenever there is the availability of required bandwidth.

Fig.5

a) Varying Bandwidth Cost for 200 Modules on 8 Sites. b) Varying Bandwidth Cost 200 Modules on 8 Sites.

5.2 Test bed results for Docker container migration

In order to analyse the importance of Docker migration in an offloading framework, a test bed for video analytics application is created and the different scenarios are presented in Table 3. The offloaded application size is 22.1 MB and the input sample video (Frame size = 1280×720 and Bitrate = 2604kbps) size is 6.5 MB. The computation intensive part and its data are offloaded to edge & cloud and the results are analyzed using Docker containerization in an edge computing environment.

Table 3
Test bed for video analytics application

Scenarios Explanation

1-Edge Offloading the data and the application to the edge device and retrieving the results to the end device

2- Cloud Offloading the data and the application to the cloud device and retrieving the results to the end device

2-Edge &End Dividing the data into two parts and offloading a part and application to the edge and the other part to the end device.

2-Edge &Cloud Dividing the data into two parts and offloading one of the parts and application to the edge &the other to the cloud and retrieving the results to the end device

3-End, Edge &Cloud Dividing the data into three parts, executing one part in the end device and offloading two other parts and application to the edge &cloud and retrieving the results to the end device

Scenarios	Explanation
1-Edge	Offloading the data and the application to the edge device and retrieving the results to the end device
2- Cloud	Offloading the data and the application to the cloud device and retrieving the results to the end device
2-Edge &End	Dividing the data into two parts and offloading a part and application to the edge and the other part to the end device.
2-Edge &Cloud	Dividing the data into two parts and offloading one of the parts and application to the edge &the other to the cloud and retrieving the results to the end device
3-End, Edge &Cloud	Dividing the data into three parts, executing one part in the end device and offloading two other parts and application to the edge &cloud and retrieving the results to the end device

The end devices chosen are Raspberry Pi2 and Raspberry Pi3, Intel i5 edge device and Amazon EC2 free-tier instance (t2.micro) as a cloud resource.

The results show server copy (offloading data and application as Docker image) power consumption, average power consumption after server copy and total execution time. Figure 6(b) represents the results of an application executed directly on the systems Pi2, Pi3, and intel_i5. Part of the video and video processing application is migrated as Docker image and the results in Fig. 6(a) show that 1-Edge prove to be a viable candidate for video analytics in terms of power and time. 1-Cloud is executed over the link (speed Test: ping = 38ms, download speed = 12.19 Mbps, upload Speed = 8.62 Mbps) and the results show the overall measure fails to overcome the performance of 1-Edge scenario.

Fig.6

(a, b) Results of Video Analytics (Object Detection) with & without Offloading.

All other variances, using end device as a part of the execution produces an acceptable result. Thus, in overall test beds, 1-Edge scenarios show reliable performance over the others. Thus, the use of Docker containerization as an offloading framework improves the lifetime of the end device and reduces the communication overhead that is created by system virtualization.

6 Conclusions and future enhancements

The present study deals with the crucial issue of offloading of applications over multiple sites. The measure of diversity plays a significant role in the proposed GGA-MSO algorithm that uses Grefenstette’s bias for strengthening the initial population. The proposed GGA-MSO algorithm is evaluated using random graphs with a different number of nodes and sites. The proposed work obtains a global optimal partitioning solution and the convergence rate is also faster. The results prove that the offloading is beneficial than executing on the local site. Additionally, this research work demonstrates the use of lightweight container technology in offloading frameworks by offloading the video analytics application and its data as a Docker image migration. The results show that the edge environment provides optimal results with regard to latency response than the cloud environment and it also reduces the overhead incurred by virtual machine migration and code migrations. As a future enhancement, a new algorithm which can facilitate in better exploration and has less time complexity has to be generated so that computation complexity will still get reduced.

Footnotes

Acknowledgments

The authors wish to express their sincere thanks to the Department of Science & Technology, New Delhi, India project-ID:SR/FST/ETI-371/2014) and SASTRA University, Thanjavur, India for extending the infrastructural support to carry out this work.

References

Ahmed

, Gani

, Sookhak

, Hamid

S.H.A.

and Xia

, Application optimization in mobile cloud computing: Motivation, taxonomies, and open challenges, J Netw Comput Appl 52 (2015), 52–68.

Qian

and Andresen

, Jade: Reducing energy consumption of android app, 3(3) (2015), 150–158.

Zhang

, et al., Energy-latency trade-off for energy-aware offloading in mobile edge computing networks, IEEE Internet Things J 4662(c) (2017), 1–13.

, Yang

and Zhang

, An effective offloading middleware for pervasive services on mobile devices, Pervasive Mob Comput 3(4) (2007), 362–385.

Kumar

, Liu

, Lu

Y.H.

and Bhargava

, A survey of computation offloading for mobile systems, Mob Networks Appl 18(1) (2013), 129–140.

Khan

M.A.

, A survey of computation offloading strategies for performance improvement of applications running on mobile devices, J Netw Comput Appl 56 (2015), 28–40.

Dolui

, Comparison of Edge Computing Implementations: Fog Computing, Cloudlet and Mobile Edge Computing, IEEE Glob Internet Things Summit, 2017, pp. 1–6.

Cuervo

, et al., MAUI: Making smartphones last longer with code offload,’, 10 17 (2010), 49–62.

Varghese

, Wang

, Barbhuiya

, Kilpatrick

and Nikolopoulos

D.S.

, Challenges and Opportunities in Edge Computing, Proc - 2016 IEEE Int Conf Smart Cloud, SmartCloud 2016, 2016, pp. 20–26.

10.

Bonomi

, Milito

, Natarajan

and Zhu

, Fog Computing: A Plat- form for Internet of Things and Analytics, in Big Data and Internet of Things: A Roadmap for Smart Environments, vol. 546, 2014, pp 169–186.

11.

Chiang

and Zhang

, Fog and IoT: An overview of research opportunities, IEEE Internet Things J 3(6) (2016), 854–864.

12.

Yousafzai

, Gani

, Md Noor

, Naveed

, Ahmad

R.W.

and Chang

, Computational offloading mechanism for native and android runtime based mobile applications, J Syst Softw 121 (2016), 28–39.

13.

Mao

, Zhang

and Letaief

K.B.

, Dynamic computation offloading for mobile-edge computing with energy harvesting devices, IEEE J Sel Areas Commun 34(12) (2016), 3590–3605.

14.

Binkert

, et al., The gem5 simulator, ACM SIGARCH Comput Archit News 39(2) (2011), 1.

15.

Shuja

, Gani

, Naveed

, Ahmed

and Hsu

C.H.

, Case of ARM emulation optimization for offloading mechanisms in Mobile Cloud Computing, Futur Gener Comput Syst 76 (2017), 407–417.

16.

Celesti

, Mulfari

, Fazio

, Villari

and Puliafito

, Exploring container virtualization in IoT clouds, IEEE Int Conf Smart Comput (SMARTCOMP), , no. Lxc, 2016.

17.

Krylovskiy

, Fit

and Augustin

, Internet of Things Gateways Meet Linux Containers: Performance Evaluation and Discussion, in IEEE 2nd World Forum Internet Things (WF-IoT), 2015, pp. 222–227.

18.

Ismail

B.I.

, et al., Evaluation of Docker as Edge Computing Platform, in IEEE Conference Open Syst (ICOS), 2015, pp. 130–135.

19.

Md Enzai

N.I.

and Tang

, A heuristic algorithm for multi-site computation offloading in mobile cloud computing, Procedia Comput Sci 80 (2016), 1232–1241.

20.

Rego

P.A.L.

, Costa

P.B.

, Coutinho

E.F.

, Rocha

L.S.

, Trinta

F.A.M.

and Souza

J.N.D.

, Performing computation offloading on multiple platforms, Comput Commun 105 (2017), 1–13.

21.

Zhao

, Xu

, Chi

, Zhu

and Cao

, Mirroring smartphones for good: A feasibility study, Lect Notes Inst Comput Sci Soc Telecommun Eng LNICST 73 LNICST(Vm) (2012), 26–38.

22.

Wang

, Lei

, Zhang

, Hsu

C.H.

and Yang

, Offloading mobile data traffic for QoS-aware service provision in vehicular cyber-physical systems, Futur Gener Comput Syst 61(2016) (2016), 118–127.

23.

Goudarzi

, Zamani

and Haghighat

S.A.T.

, A fast hybrid multi-site computation offloading for mobile cloud computing, J Netw Comput Appl 80(2016) (2017), 219–231.

24.

Nimmagadda

, Kumar

, Lu

and Lee

C.S.G.

, Real-Time Moving Object Recognition and Tracking Using Computation Offloading, Proc IEEE/RSJ Int Conf Intell Robot Syst, 2010, pp. 2449–2455.

25.

Kemp

, Palmer

, Kielmann

and Bal

, Cuckoo: A Computation Offloading Framework for Smartphones, 2012, pp. 59–79.

26.

Loukas

, Yoon

, Sakellari

, Vuong

and Heartfield

, Computation offloading of a vehicle’s continuous intrusion detection workload for energy efficiency and performance, Simul Model Pract Theory 73 (2017), 83–94.

27.

Guo

and Liu

, Collaborative computation offloading for multi-access edge computing over fiber-wireless networks, IEEE Trans Veh Technol 9545(c) (2018), 1–13.

28.

Ashok

, Steenkiste

and Bai

, Vehicular cloud computing through dynamic computation offloading, Comput Commun 120(December) (2018), 125–137.

29.

Riyahi

, Kuchaki

, Motevalli

and Hashemi

, A new genetic algorithm to optimize mobile data offloading in smart grids, 2013, pp. 1–14.

30.

Wang

and Li

, Parametric analysis for adaptive computation offloading, SIGPLAN Not 39(6) (2004), 119–130.

31.

X.G.X.

, Nahrstedt

, Messer

, Greenberg

and Milojicic

, Adaptive offloading inference for delivering applications in pervasive computing environments, Proc First IEEE Int Conf Pervasive Comput Commun 2003 (PerCom 2003), 2003, p. 107.

32.

Rim

, Kim

and Han

, Transparent method offloading for slim execution, Wirel Pervasive Comput 2006 1st Int Symp, 2006, pp. 1–6.

33.

Huerta-Canepa

and Lee

, An adaptable application offloading scheme based on application behavior, Proc - Int Conf Adv Inf Netw Appl AINA, 2008, pp. 387–392.

34.

Yang

, Ou

and Chen

H.H.

, On effective offloading services for resource-constrained mobile devices running heavier mobile internet applications, IEEE Commun Mag 46(1) (2008), 56–63.

35.

Messer

, et al., Towards a distributed platform for resource-constrained devices, Proc 22nd Int Conf Distrib Comput Syst, 2002, pp. 43–51.

36.

Ali

F.A.

, Simoens

, Verbelen

, Demeester

and Dhoedt

, Mobile device power models for energy efficient dynamic offloading at runtime, J Syst Softw 113 (2016), 173–187.

37.

Gerards

M.E.T.

and Kuper

, Optimal DPM and DVFS for frame-based real-time systems, ACM Trans Archit Code Optim 9(4) (2013), 1–23.

38.

Rizvandi

N.B.

, Taheri

and Zomaya

A.Y.

, Some Observations on Optimal Frequency Selection in DVFS – based Energy Consumption Minimization, 2006, pp. 1–28.

39.

Burke

E.K.

, Gustafson

and Kendall

, Diversity in genetic programming: An analysis of measures and correlation with fitness, IEEE Trans Evol Comput 8(1) (2004), 47–62.

40.

Diaz-Gomez

and Hougen

, Initial Population for Genetic Algorithms: A Metric Approach, Proc 2007 Int Conf Genet Evol Methods, 2007, pp. 43–49.

Grefenstette Bias based genetic algorithm for multi-site offloading using docker container in edge computing

Abstract

Keywords

1 Introduction

3.1 System architecture

4.1 Initialization phase

4.1.1 Random graph generation and the input data

4.1.2 Initial population generation

5 Results and discussion

5.1 Random graph evaluation

Table 2 Specification of Random Graph and Parameters Used Graph Vertex Site Parameter used Value R1 10 4, 8 Composite Weight [1 to 200] R2 50 4, 8 Bandwidth [1 to 200] R3 100 4, 8 R4 200 4, 8

Footnotes

Acknowledgments

References

Table 2
Specification of Random Graph and Parameters Used

Graph Vertex Site Parameter used Value

R1 10 4, 8 Composite Weight [1 to 200]

R2 50 4, 8 Bandwidth [1 to 200]

R3 100 4, 8

R4 200 4, 8