Cost Optimization based Resource Allocation Scheme for Vehicular Cloud Networks

Published Online April 2020 in MECS

Several resource allocation schemes are developed based on the requirement needs of the cloud users. There are many crucial features needs to be considered for resource allocation in a cloud computing environment. Most of the resource allocation schemes are based on the cost and resource utilization. Reliable resource allocation schemes are designed by maintaining the all other constraints, it is necessary to minimize the cost of the resources and maximizing the reliability. It is hard to examine the attainment of reliability in a cloud computing environment [1].

Resource requirements of each user is different among set of users, the main objective of this resource allocation scheme is to divide the resources satisfactorily among different users based on the requirement. Dominant Resource with Bottlenecked Fairness (DRBF) is one method of resource allocation scheme which considers the trade off between the utilization of the resources and allocation off resources fairly among different users [2].

Resource allocation problems get more difficulty when inter cloud scenarios are considered. Distributed model is the inter cloud architecture, such model share their resources by co coordinating the different cloud users. Resilience, geographical coverage are the significant benefits of such model. It is necessary to develop the efficient resource allocation strategy for such inter cloud, as it is most challenging task in such scenario. Resource allocation by peer to peer method is one such mechanism in a intra cloud model [3]. To allocate the resources in cloud computing environment the resource allocation schemes are decomposed into sub problems. The different Infrastructure as Service (IaaS) providers compute strategy for efficient resource allocation under varying limitation and capacity of cloud resources so as to maximize the revenue of Iaas cloud providers. Two criteria, one as the profit and other as resource efficiency enables allocation enables the resource partion for IaaS provider [4].

There are several strategies are applied for efficient resource allocation in cloud computing, the component based resource allocation is one such strategy in achieving the efficient resource allocation. Such models are motivated from the Peer to Peer (p2p) scheme. Such schemes are helpful when more nodes are added to the cloud [5].

As the user requirements changes there is a need to develop resource allocation schemes which are more dynamic to allocate the resources. Certain situation arises even cloud resources are fall shortage, in such scenario more dynamic way of allocating of cloud resources are required. The scheduling and allocation strategy has to be adopted according with the time. Such situation demands to build more dynamic way of allocating the cloud resources [6].

Resource management and allocations are significant aspects of cloud computing. Many schemes are proposed over the time for resource allocation efficiently. However advances still can be made in the available approaches. Heuristic methods allocate the resources efficiently. Such model provides the proper utilization of computing resources. The Heuristic algorithm combine the divide and conquer approach which proven to be more efficient way of allocating the resources [7].

Based on nature of environment resource allocation techniques are developed. In VCN, services are obtained based on the vehicles requests and hence enabling the optimal resource allocation techniques are required. When set of vehicles makes a request for services, it is required to allocate the discovered resources in a optimal way. Varies techniques are developed for resource allocation in VCN environment based on Quality of Service (QoS), energy conservation, scalability, cost driven etc. The proposed technique considers cost driven mechanism to allocate the resources. The objective of our research work is to achieve the minimization in cost for resource allocation.

• II.    Related Works

Towards efficient resource allocation for heterogeneous workloads in IaaS clouds are presented in [9]. User requirement of resources changes based upon the jobs (tasks), for example more processing units are required for jobs which are very high computing. In such architectures resources are allocated based on the Skewness Avoidance Multi Resource Allocation (SAMR). When resource are different and the requirements which are diversified skewness factor specify the amount of skewness of different resources.

Resource allocation schemes are presented in [10]. The basic classification of resource allocation methods in cloud computing is presented. The disadvantage, advantage and important aspects of the each resource allocation scheme are tabulated. Cloud resource allocation methods are tabulated based on the approach of design, mode of processing, different function utility. A game theoretic method of fair resource allocation for cloud computing services is discussed in [11]. The problem of resource allocation is solved by a game theory approach. To resolve the optimization of independence a binary independent programming method is used.

A critical analysis of resource allocation in cloud computing is discussed in [12]. When jobs are submitted to the cloud each user requires the services of the cloud. In such scenario the resources are to be allocated in real time. The required services of the cloud has to be allocated efficiently to meet the requirements of the user. As the parameter of evaluation changes, allocation mechanism is also changes on different cloud layer. The cost, efficiency, customer satisfaction or it might be utility based allocation schemes are focusing.

Resource allocation scheme based on access control in cloud computing environment is presented in [13]. Based on the access control resource allocation schemes are described. Resource allocation mechanism which are based on the traditional approach does not consider the behavior of cloud user, such schemes are considered as the static way of approach. The basic idea of Resource Allocation Scheme Based on Access Control (RASBAC) approach is to introduce the trust behavior in process of authorization.

Performance analysis based resource allocation for green cloud computing is presented in [14]. The basic idea of this work is to allocate the resources based on the performance analysis. The optimal node is decided by the node performance. The node performance is based on different parameters such as the speed of CPU, remaining amount of memory, and the number of cores. Imperfect information dynamic stackelberg game based resource allocation using hidden markov for cloud computing is presented in [15]. The basic idea of Imperfect Information Stackelberg Game (IISG) using a Hidden Markov Model (HMM) in a cloud computing environment is to increase the profit for both the user and the supplier of the resource. The main contribution of the IISG is to select optimal bidding scheme based on the overall utility. The main contribution of resource allocation model to support for both the simultaneously allocation of the resource and to support multiple service provider.

Optimal resource allocation algorithm based on hybrid parallel differential scheduling is proposed in [16]. The basic idea of the algorithm is to classify the computing resources based on attributes. To classify the attributes of computing resources cluster analysis method of resource information flow is used. The strategy applied is the probability allocation method in order to equalize allocation of computing resources of cloud. This scheme has higher performance when job has shorer time execution time and overhead is lower. Loyalty based resource allocation mechanism in cloud computing is presented in [17]. The basic idea of the work is to introduce trust in the architecture. The trust model performs the evolution based on the real time condition and based on the evaluation allocates the resources. Trust model employs the feed back mechanism which assures the system stability and service effectively. A novel energy efficient resource allocation algorithm based on immune clonal optimization for green cloud computing is presented in [18]. The main contribution of improved clonal algorithm is to reduce the consumption of energy in cloud particularly in large scale cloud computing. The improved clonal selection algorithm also improves the make span. The make span refers as the total time taken by the task to complete on a resource.

SLA based resource provision is presented in [19]. The two important aspects of the Software as Service (SaaS) provider are to minimize the cost and to increase the customer level satisfaction. The provision algorithm handles the request of customer dynamically and also consider the profiles of the customer. The provision algorithm also improves the response time, one of the quality parameter. An online mechanism for resource allocation and pricing in clouds is presented in [20]. The basic mechanism of this approach is to allocate the Virtual Machines (VMs) only for the selected users and it also assures for the requested duration. This scheme does consider the real time changes and also mechanism doesn’t predict the future demands of the VMs.

Intelligent Transportation Systems does not properly utilize the computation resources of the vehicles. The Semi Markov Decision Process (SMDP) based resource allocation schemes are proposed for vehicular cloud computing [21]. The scheme is based on the iteration process, and optimization is formed based on certain state space, reward model, and probability of transaction. The SMDP scheme attain the significant performance only when the complexity is within the acceptable range. Resource allocation in cloud computing based on agent approach is proposed in [22]. Based on the demands of the user resources are allocated. The challenges occur for allocation in certain condition when the work load increases rapidly. In such workload condition it may fail and the user can’t get the VMs which are adopted for the tasks. Agent based approaches handles the work load and adopt balance condition load condition and also provides the flexibility.

Task scheduling and resource allocation in cloud computing environment is presented in [23]. In cloud computing allocation of computing resource is difficult tasks as each computer has varying capacity.The main contribution of the task oriented scheme is to allocate the resource based on rank allocated for each task. When conflicting weights in tasks are submitted the induced bias matrix is used to find out the elements which are inconsistency and to improve the consistency ratio. Priority aware VM allocation in cloud is discussed in [24]. The cloud computing based on the multi tenant architecture has varying application and have different priorities and requirements. In such cases the high priority data over the low priority is to be considered so that resource provisioning is achieved in efficient way. Priority Aware VM Allocation (PAVA) scheme allocates the application which has high priority. This approach also allocates the sufficient resources to the application which are consider to be high priority one.

Knowledge based resource allocation is presented in [25]. Implementing the effective software systems which implements the optimal allocation depends on the allocating computation resources based on the different requirements which holds to be the key parameter for successful implementation. Neural network based on the radial function methods are used in this implementation. To allocate the computation resources in a environment based on the multi tent architecture a mathematical model is constructed based on the noval approach. Neural networks based on the radial function is constructed to map the tasks into particular requirement of computational resource. Resource allocation based on the tier centric approach is presented in [26]. The main contribution of the analytics is to minimize the cloud subscription cost. The presented analytics data shows that cost of the services can be drastically reduced. The analytics is for both the medium and large scale enterprise environments. Profit maximization resource allocation in cloud computing is presented in [27]. The main objective of the flexible resource resource allocation mechanism is to maximize the profit for the cloud provider.

Many objective resource allocation in cloud computing data centers is presented in [28]. For efficient resource management several challenges are mentioned, there are many number of optimization criteria are formulated for the virtual Machine Placement (VMP) problem. For the VMP problem a noval approach is formulated. Many Objective Virtual Machine Placement (MaVMP) is formulated in this mechanism, and designed the algorithm which address the challenges and possible method of solutions to such problems.

Resource allocation based on preemptive method are presented in [29]. The main problem in the grid is to allocate the resources efficiently and to attain certain quality of service. The main objective of this approach is to adopt the grid agent which performs the job scheduling based on the immediate request and advance request. The basic idea is to achieve the minimization of the waiting time, maximize the resource utilization. Using this technique it is also possible to achieve the load balancing among the resources. An improved optimized resource allocation mechanism for web server grid is presented in [30]. In grid environment suitable resources are selected by the grid broker. The main objective of this approach is to develop the algorithm for jobs which are heterogeneous and each job has varies constraints. Waiting time and cost of the resource are the two metrics considered by this approach. The basic idea is to reduce the waiting time and to to select the lowest cost resources.

Improving resource allocation performance in mobile ad hoc grid with mobility prediction is presented in [31]. In such type of architecture the goal is to allocate the appropriate resources for the tasks. The overall performance of the system depends upon how well the resource allocation schemes are implemented. Node mobility is the one of the basic challenge in mobile ad hoc grid. Due to nodes mobility the topology changes dynamically. The main objective of resource allocation scheme is to increase the performance in mobile ad hoc network. Based on the mobility of the grid members resources are allocated to the nodes.

A Cluster based resource allocation architecture for mobile grid environments is discussed in [32]. Resource allocation is more challenge in environment which has the mobility of the nodes. Based on the availability of the resources, it is necessary to consider the mobility of the user. The main objective of the Cluster Based Resource Allocation Architecture (CBRA) is to schedule the operations and to monitor the resources. Resource allocation scheme to minimize communication cost in mobile ad hoc computational grids is presented in [33]. This scheme is based on the centralized method and main objective is to allocate the resources based on the mobility in the members. The basic idea is to classify the tasks and also dependency between tasks. This scheme exploits the cost of communication based on the task dependence.

Designing and analyzing resource allocation based on grouped grid nodes is presented in [34]. In non grouped model the CPU consumption of the supervising node increases as the number of nodes are also increases. The main objective of the grouped model is to reduce the CPU consumption. In this scheme the nodes of the grids are grouped based on the scales of the CPU. The basic idea is to form the different groups and the supervise node is to allocate the resources only in the same group. The grouped model can achieve higher performance compared to non grouped model. Adaptive resource allocation in Mobile Ad hoc computational grids is presented in [35]. In Mobile Ad hoc computational grids, two key parameters are the communication and execution cost. When tasks are residing at two separate nodes the cost of the communication induces by the data transfer. The nodes which are closely located and for those nodes interdependent tasks are allocated so that it is possible to reduce the communication cost. The main objective of the adaptive and distance based resource allocation scheme to avoid the multihop communication in which the tasks are dependent. The basic idea of this model is to reduce the communication cost.

Network aware resource allocation scheme for mobile ad hoc computational is presented in [36]. Dynamic communication environment and unreliable are the major characteristics mobile ad hoc computational grids. As the traffic load varies and each node in the network experience different connection. The task size, transmission power are some of the factors has to be consider along with connection quality which can provide the robust and effective resource allocation scheme. Two resource allocation schemes are proposed by this scheme. Energy efficiency and network connection are improved in the first resource scheme which exploits the transmission power control. Quality of connection and traffic loads are the parameter consider for the second resource allocation scheme. A resource allocation architecture with support for interactive sessions in utility grids is presented in [37]. Virtualization architecture is implemented in utility grids which allow the infrastructure sharing. In utility grids to support interactive sessions a resource allocation architecture is implemented in this scheme. Resource allocation system in a utility grid assigns computing node by considering the varies performance parameters.

Budget optimized network aware joint resource allocation in grids/clouds over optical networks is presented in [38]. For certain application to transmit large amount of data, guaranteed bandwidth in addition to the computing infrastructure is required. The basic idea of the this approach is to allocate the resources from perspective of the customer. This scheme proposes the linear programming based on the mixed integer and approaches are based on the heuristics method to solve the joint resource allocation problems which minimizes the customer rental cost. Based on this approaches possible to reduce the 30 percent rental cost of the customer. Modified round robin algorithm for resource allocation in cloud computing is presented in [39]. It is one of the simplest and oldest algorithm is used as scheduling algorithm. The algorithm is generally used for time sharing system. The basic idea in this type of algorithm is the time slice or quantum of time. Based on the interval of time slice the scheduler of the CPU allocate the process. Modified round robin technique is the one of the simplest method of achieving the optimal scheduling mode.

Non cooperative resource allocation scheme for data access in VANET cloud environment is presented in [40]. Stable communication and data access opportunities for the vehicles are provided by Road Side Unites (RSUs) which constructs the cloud computing environment. Due to the topology of the network changes frequently there is high transmission latency in VANET. The basic idea of the resource allocation based on the Gauss-Seidel iteration method is to data access the data which is investigated with the non cooperative approach.

• III.    Hungarian Model Based Resource Allocation in VCN

In this section, we describe about network environment, resources allocation mechanism based on cost optimization algorithm is presented.

• A.    Network environment

We consider three tier VCN architecture as depicted in figure 1. Vehicular Cloud (VC) is considered as tier-1, where the resources are shared among vehicles using vehicle-to-vehicle (V2V) communication only. Tier-2 consists of Infrastructure Cloud (IC) formed by Road Side Unit (RSU), where the vehicles have access to cloud services. Traditional Cloud (TC) exists in the internet domain. TC has many resources, which are accessed by vehicles. TC has spread over the large geographical area. Having defined a way to identify resource in the system, as depicted in the figure 1. Each module can be deployed independently in a distributed environment. Every component interacts with the other with a standard protocol. We will have a manager application running on a central server. It will communicate with agents running on virtual machines and other hardware (vehicle models through radio tower proxy) to receive requests and distribute them for processing. Response will be relayed back to requester. This server component will act as discovery and allocation manager. In the discovery phase, it will build the repository of all available computing resources.

• B.    Preliminaries

• •    Resource allocation: Is the process of optimally (efficiently) allocating the available resources to the requested application

• •    CPU utilization: Utilization of the CPU while allocating the resources. It is expressed in

  percentage

  • •    Resource allocation delay: It is time taken by the system to allocate the available resources.

  • •    Error rate: To allocate the right resources for the first time.

  • C. Computation Model

  Consider there are x physical servers available in a cloud group and each is denoted as y, where 1≤ y≤ x: Suppose z kinds of resources are available resources, for each physical server y can be described as a total capacity i.e. C^(y) = C 1 ^(y); C 2 ^(y), Cz^(y) and each kind of resource are denoted as j, where j € 1, 2, 3, 4. The task i submitted by vehicle is denoted as ji, where i €1, 2, 3, 4...u. A various types of VM are predefined by the cloud and type of resource is enclosed by the vector Ri = R i1 ; R i2 ; R i3 ; R i4, R i k respectively. Let R be resource request be an UxZ dimensional matrix whose rows indicate the VM type of each vehicle requires and column specifies the amount of various resources given by equation (1)

  
  

  R =

  
  

  f R 1

  R 2

  
  

  I ^R z )

  
  

  R 11 R 12    R 1

  R 21 R 22   R

  
  

  1 z

  
  

  2 z

  
  

  ^R u 1 ^R u 2 ^R u

  
  

  D. Resource Allocation Mechanism

  
  

  Resources management and allocations are the key mechanisms in vehicular cloud, due to high mobility of vehicles which varies continuously hence it is difficult to allocate resource and utilization of allocated resources

  
  

  efficiently. Consider Ra resources available, Rr resources required, Rt resources are available at time t and Rat denotes resources available in time t, R rt specifies resources require in time t. So we can formulate resource allocation method and possible is given in this time of interval and to allocate the resources. Let R rt be an resource request at time t by an activity of r. Let N be a set of activities, then resource required in schedule time t is given by Rat - Rrt ≥ 0, 0 ≤ t≤ T. In this interval it is possible to allocate the resource. Set of activities N

  
  

required to schedule in time t is given by

En ~ r=1 RRtr

Fig.1. Vehicular Cloud Network Environment

Resource Assignment Problem

Consider there are n resources and n no. of vehicles is accessible services of the resources requests to the cloud over period of time are different. If the cost of allocating j^th resource to the i^th vehicles is denoted as C ij , then payoff cost matrix is given by table 1.

Table 1. Payoff Cost Matrix

	1	2		J		n
1	C11	C12		C2J	..	C1n
				..
n	Cn1	Cn2		Cn3	..	Cnn

Algorithm 1 Proposed Resource Allocation

The algorithm is used to find the minimum cost in resources allocation problem that involve the assigning the resources to set of vehicles. This is done by organizing our resources in to matrix form with resources as rows and vehicles as the column. For each row of the matrix, find the minimum element and subtract it from every element in its row. The objective is to assign resources to vehicles in such a way that the total cost of assignment is minimum.

if Resource cost matrix balanced then

Find a row value and minimum column value end if Number of zero lines = number of row then Optimal resource allocation is done end else if modify the matrix table then

• a.    Find a minimum uncovered number and subtract to uncover from each number in the matrix;

• b.    To find number at intersections point and add to it minimum value;

• c.    Cover all zero but not at intersections lines and carry this process until the required condition is satisfied.

end else

Make balanced matrix by adding constant value to Row/column end

• IV. Simulation

This section presents, performance metrics, simulation procedure, simulation parameters.

• A.    Performance Metrics

Some of the performance metrics evaluated are processing time, service provider response time, and successful resource allocation.

• •    Processing time: It is defined as the time required to process, to identify density of vehicles, check resources of each cloud. It is measured in seconds.

• •    Service provider response time: It is the total time taken by the service provider to process the requests of vehicles in particular time window. It is measured in seconds.

• •    Successful resource allocation: It is process of assigning and managing number of resources effectively. It is expressed in percentage.

• •    Total no. of resource allocated: It is defined as the total number of resources that are allocated to a requested vehicles by the service provider.

• •    Service provider quality: It is defined as the number of services is served to the total number requisition sent. It expressed in percentage.

• B.    Simulation Procedure

Simulation procedure for the proposed resource allocation scheme is as follows:

• •   Begin

• •    Create virtual machine (or server) farm with

different configurations (CPU size, clock speed, RAM and Storage).

• •    Create vehicle objects.

• •    Build an agent on virtual machine and vehicle to interact with controller.

• •    Assign dummy IP address to each virtual machine and vehicle.

• •    Create controller software to interact with agent on virtual machine and vehicle.

• •    Configure list of IP addresses to discover in controller. Vehicle makes a request to the controller for resource allocation

• •    Agent responds with resource configuration of the virtual machine.

• •    Controller stores discovered information in repository for allocation.

• •    Controller also stores task performance details to refine discovery schedule.

• •    Controller assigns vehicle’s request to available resource (virtual machine).

• •    Virtual machine executes the task and responds back to the vehicle.

• C.    Simulation Parameters

  50 VMs on 25 physical machines, 100 requests per second (Mix of complexity-from simple to medium going into highly complex, resource consuming computation task), Measured for 10 minutes or 10 iteration, Configuration of the host system : Intel Core i3-5010U, 2.1 GHz, RAM - 4GB DDRR3

• V. Result Analysis

This section presents the results obtained during simulation process. The simulation performed using JAVA programming language.

We compare the results of the cost optimization with the generic algorithm [41] that uses a combination of best fit and first fit techniques for resource allocation in VCN. In VCN it is critical that right resource is available to process any request with least possible latency. Requester (a vehicle or other part of vehicle cloud) expects in time data to perform critical decisions and as the entire cloud configuration changes in a split second, data becomes stale within milliseconds of it being collected. As the network scales, to cater to increasing number of vehicle requests for up to date information, capacity of computing resources needs to adjust dynamically to handle massive influx of computing requests. Service provider response time versus resource request time is shown in figure 2. From the graph, we observe that same number of requests can be sent over different resource request time and these requests are handled by service provider with different response time.

optimization technique. This is the result of better fitment analysis using mutation data to improve resource identification.

Fig.2. Service provider response time vs. Resource request time

Fig.5. Service provider vs. Number of resource allocated

Fig.3. Service provider vs Number of resource allocated

Fig.6. Average resource allocation delay vs No. of iteration

Figurer 3 illustrates the number of resource allocated based on request to the service provider, which allocates the number of resources and it is varying with number of times requested resources for different time window.

Fig.4. Successful resource allocation vs. Service provider response time

The graph for percentage of successful resource allocation versus request processing time is shown in figure 4. From the graph, we observe that the percentage of requested resources and successful resource allocation for different time window.

Figure 5 depicts the total number of resources allocated versus service provider response time. Total number of resources allocated is varied with the service provider response time

As evidenced from figure 6 generic algorithm is slightly faster in allocating resources compared to cost

Fig.7. Average CPU utilization vs. No. of Iteration

Figure 7 represents the average CPU utilization in resources. Efficiency of generic algorithm comes at a cost. Technique being complex, relative to cost optimization algorithm, doesn’t balance load on computational resources uniformly. VMs behave in somewhat erratic fashion compared to harmonious consistency found in cost optimization technique. Generic algorithm responds faster in allocating resources for computation requests in VCN. However, this efficiency comes at a cost as this technique is more complex compared to cost optimization.

Figure 8 shows the average memory utilization in resources. It puts load on the system and doesn’t balance load on virtual resources for uniform distribution. Cost optimization technique performs consistently, although slightly slower.

Figure 9 represents the resource utilization of the host where algorithms are executed to allocate VMs to handle vehicle requests. This shows a direct reference to algorithm complexity

Fig.8. Average memory utilization vs. No. of Iteration

based resource allocation scheme is proposed and implemented. The proposed work is simulated for processing time, number of resource allocation, successful resource allocation to validate its performance. The proposed work is compared with generic algorithm. The performance analysis shows that cost optimization technique performs consistently although slightly slower. The proposed resource allocation scheme minimizes the cost for the cloud users (in these case vehicles). There are many Quality of Service (QoS) parameters can be considered for resource allocation in VCN such as processing time, reduction of the cost, optimal utilization of resources. We proposed customer driven mechanism which considers the minimization of the cost for cloud users. Future extension of this work is to validate the simulation results on real time environment.

Both algorithms are designed to handle error (due to re- source unavailability, network error or other unknown failures). In case of failure, to allocate right resource the first time, algorithm retries to correct itself. Figure 10 shows the error rate for first try, plotted for 10 iterations.

Fig.9. CPU utilization of the hosting algorithm

■Proposedcost optimizationmethod

Fig.10. Error rate vs No. of iteration

VI. Conclusion

Efficient resource allocation schemes in VCN environment results in significant reduction of the cost. Resource allocation mechanism in VCN demands the optimal solution. In VCN environment where multiple vehicles make a request for services, the resources over cloud has to be dynamically allocated in accordance with minimization of cost. In this paper cost optimization