Arya K S, Dr. Murali P
Computer Science Engineering
Adi Shankara Institute of
Engineering and Technology, Kalady
Task scheduling plays a key role in cloud computing systems. Scheduling in
cloud is responsible for selection of best suitable resources for task
execution, by taking some static and dynamic parameters and restrictions of
tasks into consideration. The users perspective of efficient scheduling may be
based on parameters like task completion time or task execution cost etc. In
this paper we are performing comparative study of the different Task Scheduling
Keywords— Cloud Computing, Edge Computing,
Task Scheduling, Optimal Scheduling, Local Computing,
Mobile devices can provide
communication for us almost anywhere and anytime, which are becoming an
important part of people’s daily lives 1. With the development of mobile information technology, there are
some new applications emerging and attracting wide attentions, such as speech
recognizer, natural language translator, image processor, augmented reality.
These types of applications require a higher memory, battery energy, and
computing power than that cannot be acquired on the resource-constrained mobile
devices. As there are many limitations on communication facilities and hardware
resources in mobile devices, the gap between the need of performing complex
tasks and the limited resource in mobile devices is increasing everyday 2, 3.
Cloud Computing is an essential ingredient of advanced
computing systems. Computing concepts, technology and architectures have
developed and consolidated in the last decades. Many aspects are subject to
technological evolution and revolution. Cloud Computing is a computing
technology that is rapidly consolidating itself as the next step in the
development and deployment of increasing the number of distributed application.
To gain the maximum benefit from cloud computing, developers must design
mechanisms that optimize the use of architectural and deployment paradigms.
The goal of our work is
to compare different task scheduling mechanisms. In this paper we are considering “Local computing without task scheduling”, “Task scheduling
with randomly selected device”, “Cross entropy based optimization scheme”, “Multi
device task scheduling Strategy”
II COMPUTATION MODEL
Each mobile device i can execute its own task
locally. By using its own computational resources and processing power.
Suppose that a mobile device i (task owner) wishes to execute a
computation-intensive task while its computation resource is heavily occupied
by other applications currently. In this case, the mobile device i would publish the task to these
nearby mobile devices and requests for task offloading. If the mobile device j currently possesses a large
amount of idle computation resource, it will reply the request. Once the mobile
device i receives the reply message, the
task is offloaded to mobile device j through the wireless link 4.
III TASK SCHEDULING MECHANISM
There have been extensive studies on
the task scheduling mechanism for mobile edge computing. In this section we
look at some of them.
computing without task scheduling
Each mobile device chooses to execute
its task by itself. , the total overhead in this scenario is depends on
execution time and energy consumption. This scenario provides a baseline for
network performance across all mobile devices.
Task scheduling with randomly selected device
Each mobile device computes the execution time of the task
first. If the execution time is greater than the contact duration, the mobile device chooses to
offload its tasks to a randomly selected neighbour device without considering
the impact to other mobile devices. In this case, the total overhead of a
mobile device can be expressed. This scenario provides a baseline for the
performance of task scheduling schemes.
entropy based optimization scheme
We use the centralized
cross-entropy method to solve the task scheduling problem, which is a
stochastic search technique and has been proved to be effective in finding the
approximate optimal solution of the optimization problem 5. In this case, the
task scheduling strategy of each mobile device can be obtained as a result of
the optimization process which aims at maximizing the profit of the resource
device task scheduling Strategy for ad-hoc based computing
The model takes contact duration, opportunity consumption,
energy consumption, time latency, and monetary cost into account, aiming at
finding an optimal solution.
We consider the contact duration
of the mobile devices. Suppose that mobile devices i and j are two neighbour devices, and
they both maintain a uniform linear motion in the recent time period. The
relative movement speed between them is v,the relative distance between the mobile devices can be
obtained by measuring the signal strength.
FIGURE 1 Illustration of the
relative movement between mobile devices i and j.
The relative movement between
mobile devices i and j is shown in Fig. 1. Where R
is the maximum distance for the wireless link between
mobile devices i and j. suppose that mobile device i
in point A and mobile device j in point S at the initial time,
the distance between i and j is da. 1t time later, mobile device i
moved to point B relatively, the distance between i
and j is db. 21t time later, mobile device i moved to point C relatively, the
distance between i and j can be obtained by measuring the signal strength.
Then, the contact duration between mobile devices i and j is calculated. Task is offloaded
only if the contact duration is greater than the time required to perform the
To investigate the performance
of the overhead optimizing task scheduling mechanism, we consider to the mobile
edge computing scenario as that 50 mobile devices are randomly distributed
within an area of 1000m * 1000m, the mobility model of each mobile device is
the random way-point model with the speed of 10m/s. Each mobile device can
connect to the nearby devices within 200 meters via a Wi-Fi network.
task unsuccessfully completed
Unsuccessfully completed task is the task whose
execution time is longer than the time constraint of itself. We define the
number of unsuccessfully completed tasks as UN
In the local computing scheme, if there are too
many tasks to be executed, at some point some tasks should wait to be executed
and could not be completed in time due to the lack of computing resources.
Those mobile devices in task scheduling schemes can use the resources of the
neighbour resource-rich device, if there are too many tasks, they can offload
the tasks to their neighbours, and complete the tasks quickly.
the Multi device task scheduling Strategy for ad-hoc
based computing aims at reducing the overhead of mobile devices
and takes the contact duration, wireless accessing coordinating, and
computational resource allocating into consideration, the mobile devices in
this scheme can have a stable high-speed wireless channel to transmit the data
of the task, the mobile devices in this scheme can complete the task in time
and has a better performance in UN.
execution time of task
The local computing scheme has a much longer
execution time than that of task offloading schemes. In the task offloading
schemes, the scheme with a randomly selected mobile device has the longest execution
time, and the Multi device task scheduling Strategy for ad-hoc based
computing scheme has the shortest execution time. In a local computing scheme,
the execution time of a task is mainly the executing time. However, in the
mobile edge cloud computing schemes, the time consumption of a task mainly
includes the data transmitting time, and the task executing time in the neighbour
resource-rich device. In general, the task executing time in the resource-rich
device is smaller than the local executing time. Multi
device task scheduling Strategy for ad-hoc based computing
takes the contact duration into consideration and can optimize the wireless
transmission resources and computing resources at the same time, it has a
relatively shorter execution time for one task than other task offloading
overhead for mobile device
Local computing mechanism has the heaviest overhead, the overhead in
our task scheduling scheme is a slightly lighter than the overhead in the cross
entropy based scheme, and both the above two schemes have a lighter overhead
than that in the scheme of the randomly selected device. The reason is that
mobile devices in local computing scheme can not offload the tasks and have to
execute the tasks themselves. However, the mobile devices in task offloading
schemes can choose to execute the tasks locally or execute the tasks through
the resource-rich device. In general, executing the task through the resource-rich
device has a low overhead. In the scheme of the randomly selected device, the
mobile device regardless of the impact to others, which to a certain extent,
increase the overhead of themselves. The cross entropy based scheme take the
profit of the resource provider into first consideration, and the overhead of
the mobile device is a little higher than our proposed task scheduling
To solve the resource scarcity of mobile devices, we can utilize applications of
cloud computing. In order to provide low-latency and reduce backbone traffic,
“edge computing” platform is proposed. For better utilization of the
available edge devices, task that are needed to be perform is shared among edge
devices(Ad-hoc)depending upon their constraints such as resource power, energy,
Task scheduling mechanism minimize the overhead for
mobile devices. In Multi device task scheduling
Strategy for ad-hoc based computing Mobile device performs scheduling decisions locally
and take mobility into consideration, thereby reduce control and signalling
overhead, And No of unsuccessfully completed task, Average Execution time,
Average overhead on devices are comparatively low . Among the different task
scheduling mechanisms we consider Multi device task scheduling
Strategy provides the optimal task scheduling.
M. Satyanarayanan, ”Mobile
computing: The next decade,” SIGMOBILE Mob.
Comput. Commun. Rev., vol. 15, no. 2, pp. 2–10, Aug.
2011. Online . Available: http://doi.acm.org/10.1145/2016598.2016600
K. Kumar, J. Liu, Y.-H. Lu, and
B. Bhargava, ”A survey of computation offloading for mobile systems,” Mobile Netw. Appl., vol. 18, no. 1, pp. 129–140,
F. Liu et al., ”Gearing resource-poor mobile
devices with powerful clouds: Architectures, challenges, and applications,” IEEE Wireless Commun., vol. 20, no. 3, pp. 14–22,
formation of mobile cloud based on bidding incentives,” in Proc. IEEE 7th Int. Conf. Cloud Comput. (CLOUD), Jun. 2014, pp. 200–207.
R. Y. Rubinstein and D. P.
Kroese, The Cross-Entropy Method: A Unified
Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine
Tianze, L., Muqing, W., Min, Z.,
and Wenxing, L. (2017). An overhead-optimizing task
scheduling strategy for ad-hoc based
mobile edge computing