PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Share a file Manage my documents Convert Recover PDF Search Help Contact



42I20 IJAET0520965 v7 iss2 635 641 .pdf


Original filename: 42I20-IJAET0520965_v7_iss2_635-641.pdf
Author: IJAET

This PDF 1.5 document has been generated by Microsoft® Word 2013, and has been sent on pdf-archive.com on 04/07/2014 at 07:58, from IP address 117.211.x.x. The current document download page has been viewed 423 times.
File size: 448 KB (7 pages).
Privacy: public file




Download original PDF file









Document preview


International Journal of Advances in Engineering & Technology, May, 2014.
©IJAET
ISSN: 22311963

AN EFFICIENT TASK SCHEDULING ALGORITHM TO
OPTIMIZE RELIABILITY IN MOBILE COMPUTING
Faizul Navi Khan, Kapil Govil
Teerthanker Mahaveer University, Moradabad, U.P., India

ABSTRACT
Mobile computing can be describes as a way of transmission of data, via a computing device, without having a
wired connection. Mobile computing also includes a number of technologies and devices such as wireless
network, notebook, Smart phones, tablets and Personal Digital Assistant (PDAs) etc. Various applications are
running under the Mobile Computing domain can be accessible by the users regardless their locations to fulfill
their day to day business or personal needs. Multiple users send their requests from the different locations and
these requests execute on available resources and send back to their originating point in reliable manner. The
problem of task scheduling in Mobile Computing is always critical in order to execute a numbers of tasks on
different processors to achieve maximum level of optimization. Efficient task scheduling is always a main
concern to enhance the performance of application in Mobile Computing. In Mobile Computing multiple
processors are joined together that acts as single system and it handles the various tasks requests in such
environments. This research paper demonstrates the problem of task scheduling where numbers of tasks ‘m’ are
greater than the available processes ‘n’ (m>n) through a task scheduling algorithm that will provide optimal
solution in order to achieve optimal reliability to the task. The Scheduling algorithm describe in this research
paper is based on the consideration of processing reliability of the task to the processors.

KEYWORDS: Mobile Computing, Performance, Processing reliability, Task scheduling

I.

INTRODUCTION

Mobile computing is precisely to permit users and applications to be as effective as possible in this
environment of uncertain connectivity, without changes to the manner in which they operate. Mobile
data communication has become a very important and rapidly evolving technology as it allows users
to transmit data from remote locations to other remote or fixed locations. An application running
Mobile Computing network is accessible on every hosts and it looks like a combinations of multiple
tasks, these tasks executes on available processor in Mobile Computing in distributed manner. And
the tasks are processed and information is provided to the requester hosts in form of the output.
Different users have the different computing needs. In Mobile Computing multiple processors act as a
single system that parallel receives multiple requests and execute these requests within the available
resources. This research paper present the design of task scheduling algorithm that would solve task
scheduling problem in Mobile Computing where the number of tasks ‘m’ will execute on numbers of
processors ‘n’ (where m>n) in heterogeneous environment. Multiple tasks from the different mobile
host will come and arrange in an ordered queue and will execute in First In First Out (FIFO) order one
by one. In case the new task will come from the any of the mobile user in the queue, it will search for
available processor in Mobile Computing, if the processor is free then the task will be scheduled for
its execution otherwise the task will be arrange in waiting queue until the present assignment will be
completed. As given in Figure 1.

635

Vol. 7, Issue 2, pp. 635-641

International Journal of Advances in Engineering & Technology, May, 2014.
©IJAET
ISSN: 22311963

Figure 1: Tasks are waiting in queue to allocate in Mobile Computing Domain

This research paper discusses the problem of Mobile Computing, in such scenario where multiple
mobile host accessing application running in wireless network. An application can be consider as
multiple task and these tasks are arranged in an order queue and get scheduled to the available
processor in Mobile Computing. If number of tasks is greater than available processors, the same
numbers of task will be scheduled to available processors and the rest of the tasks will be in the
queued status until present allocation will execute and processors will be free. To avoid such situation
in the Mobile Computing, this research paper proposed a new task scheduling algorithm that will
ensure that all the tasks in queue will execute by achieving optimal reliability to the processor in
mobile computing. Some of the other related methods have been reported in the literature, such as
Routing Scheme [1], Reliability and Performance [2], Task allocation[3, 4], Task scheduling [5, 8, 9],
Task assignment [6], Reliable Distributed Grid Scheduler [7], Scheduling Manager for Mobile Cloud
[10], Enhancement of Performance of Distributed Computing System [11], Task allocation for
maximizing reliability [12, 13], Mobile Computing [14], Job Scheduling [15], resource allocation [16,
17, 18] Performance modeling and analysis [19], Energy-efficient deadline scheduling [20].This
research paper has considered an example of task scheduling problem in Mobile Computing and
introduce a new task scheduling algorithm with the help of Hungarian algorithm in order to get
maximum processing reliability in Mobile Computing, the scheduling algorithm would also be deal
with load balancing issues in the Mobile Computing so that performance of the Mobile Computing
can be enhanced by using the proper utilization processors.

II.

NOTATIONS

p
t
n
m
PRM

III.

Processor
Task
Number of Processors
Number of Tasks
Processing Reliability Matrix

OBJECTIVE

The main objective of this research paper is to improve the performance by maximizing the overall
processing reliability for a Mobile Computing by introduce a new task scheduling algorithm to assign
the tasks on various processors with in heterogonous environment to enhance the performance of the
Mobile Computing. The nature of assignment of tasks to the processor is static. Task scheduling
algorithm will also ensure the processing of all the tasks within the application in optimal way. In this
paper performance is measured in term of processing reliability of the task that have to be get

636

Vol. 7, Issue 2, pp. 635-641

International Journal of Advances in Engineering & Technology, May, 2014.
©IJAET
ISSN: 22311963
processed on the processors of the environment with the achieving maximum level of processing
reliability in Mobile computing.

IV.

TECHNIQUE

This research paper has chosen the problem where a set P = {p1, p2, p3,………pn} of ‘n’ processors
with different processing speed and a set T = {t1, t2, t3,………tm} of ‘m’ tasks, where m>n in order to
evaluate optimal processing reliability in Mobile Computing. Processing reliability are known for all
tasks for every processor and will be arrange the processing reliability for each task for different
processor in a Processing Reliability Matrix (PRM) of order (n*m) and processing load (in terms of
reliability) will initialize to zero for all processors by 1. After that scheduling algorithm will search for
the maximum value by row (without repeating the column in the matrix), in result it would get the
tasks equal to number of processors available in the Mobile Computing and those task will get
scheduled. The process will repeat until number of tasks will remain lesser than the number of
processors available in the mobile computing. Once this condition will occur where the numbers of
processors are greater than the tasks waiting for the execution then will make slide change in the
technique. Instead of searching element with maximum value row wise, the search will be steer
column wise and that will make enable the final scheduling of remaining unallocated task in Mobile
Computing.

V.

ALGORITHM

1. Start Algorithm
2. Read the number of task in m
3. Read the number of processor in n
4. Store task and Processing Reliability into Matrix PRM (,) n x m of order
5. While (All task! = Assigned)
{
i.
Check if the matrix containing numbers of tasks are greater than or equal to numbers
of processors (m>=n) then go to step (ii) else step (iv)
ii.
Search maximum value row wise in the matrix
iii.
Check if the column is previously selected for maximum value then GO TO step – (ii)
to find next maximum value for the row else Goto step (vi) to assign eligible task.
iv.
Search the maximum value column wise in the matrix
v.
Check if the row is previously selected for maximum value then GO TO step – (iv) to
find next maximum value for the column else Goto step (vi) to assign eligible task.
vi.
Assign the eligible tasks to available processors
}
6. State the results
7. End of algorithm

VI.

IMPLEMENTATION

This research paper consider Mobile Computing Domain which consist a set P of 3 processors {p1, p2,
p3} with different processing speed, and a set T of 7 tasks {t1, t2, t3, t4, t5, t6, t7}. It is shown in the table
1. The processing reliability of each task varies for each processor in the domain, processing
reliability are also known and mentioned in the processing reliability matrix namely PRM of order 3 x
7.
Table 1: Processing Reliability Matrix

PTM[3][8]

637

p1
p2
p3

t1
0.999669
0.997854
0.998967

t2
0.999433
0.998780
0.999232

t3
0.998798
0.998955
0.987432

t4
0.999754
0.987432
0.999876

t5
0.998766
0.999578
0.999866

t6
0.998654
0.998643
0.998456

t7
0.999478
0.998903
0.999754

Vol. 7, Issue 2, pp. 635-641

International Journal of Advances in Engineering & Technology, May, 2014.
©IJAET
ISSN: 22311963
As per the new task allocation algorithm, the approach will consider the maximum value for each row
and will get the below stated results in Table 2.
Table 2: Selecting maximum value row wise

p1
p2
p3

PTM[3][8]

t4
0.999754

t5

t7

0.999578
0. 999754

Since there are only three rows in the matrix that will schedule three tasks to the processors and
scheduling table as mentioned in Table 3:
Table 3: Scheduling Table
Processor
Task
Processing
Reliability
p1
t4
0.999754
p2
t5
0.999578
p3
t7
0. 999754

Hence the total numbers of tasks are 4 and still are greater than available numbers of processors
(m>n), that will ensure repeat the same process and next three tasks will be scheduled again and now
scheduling table is mentioned in Table 4:
Table 4: Scheduling Table
Processor

Task

p1

t4* t1

p2

t5* t3

p3

t7* t2

Processing
Reliability
0.999754 *
0.999669
0.999578 *
0.998955
0. 999754 *
0.999232

After repeating the same process of algorithm steps twice, still one task in the queue and gets remain
unscheduled, here numbers of processors are greater than number of task (one) (m<n), now the
element will be searched by column wise and that will ensure the last task will be allocated in the
domain and the final scheduling table will be as stated in Table 5:
Table 5: Scheduling Table
Processor
p1
p2
p3

VII.

Task
t4* t1* t6
t5* t3
t7* t2

Processing Reliability
0.998077
0.998533
0.999232

CONCLUSION

This research paper has considered m number of tasks needs to schedule to n number of processors
where m is always greater than n in Mobile Computing. This research paper solves the problem task
scheduling in such manner which would maximize the processing reliability of the task to the
processors in Mobile Computing. In this research paper performance is measured in terms of
processing reliability of the tasks that has been processed by the processor of the Mobile computing.
The result as stated below of the given example here.
Table 6: Final Scheduling Table
Processor
p1
p2
p3

Task
t4* t1* t6
t5* t3
t7* t2

Total Processing
Reliability

Processing Reliability
0.998077
0.998533
0.999232
0.995847

The final task scheduling as mentioned in Table 6 is shown in Figure2.

638

Vol. 7, Issue 2, pp. 635-641

International Journal of Advances in Engineering & Technology, May, 2014.
©IJAET
ISSN: 22311963

Figure 2: Final task assignment in Mobile Computing Domain

Graphical representation of stated outcome of the given input as mentioned in Figure 3:

Figure 3: Showing total processing reliability for various processors in mobile computing

The technique stated in pseudo code applied on several sets of input data and that verified the
objective of get maximum processing reliability for given tasks for their execution. The analysis of an
algorithm mainly focuses on time complexity. The time complexity of above mentioned algorithm is
O(m+n). By taking several input examples, the above algorithm returns results as mentioned in Table
3.
Table 4: Time Complexity
Number
of
Processors
(n)
3
3
3
3
3
4
4
4
4
4
5
5
5
5
5

VIII.

Number
of tasks
(m)
5
6
7
8
9
5
6
7
8
9
6
7
8
9
10

Complexity
of
algorithm
[5] O(mn2)
45
54
63
72
81
80
96
112
128
144
125
150
175
200
225

Complexity of
present
alogorithm
O(m+n)
8
9
10
11
12
9
10
11
12
13
11
12
13
14
15

FUTURE WORK

This research paper employed static task scheduling model to optimize reliability of the Mobile
computing. For future studies, dynamic task scheduling model can be designed for mobile computing
or distributed network. Other future work may include develop some other routing techniques or task

639

Vol. 7, Issue 2, pp. 635-641

International Journal of Advances in Engineering & Technology, May, 2014.
©IJAET
ISSN: 22311963
assignment model to optimize cost, time and reliability of the distributed computing or mobile
computing.

REFERENCES
[1]. AShajin Nargunam, M. P. Sebastian, 2007, Hierarchical Multicast Routing Scheme for Mobile Ad Hoc
Network, Vol. 4873, pp 464-475
[2]. Daeyong Jung, SungHo Chin, KwangSik Chung, Taeweon Suh, HeonChang Yu, JoonMin Gil, 2010, An
Effective Job Replication Technique Based on Reliability and Performance in Mobile Grids, Lecture Notes
in Computer Science, Vol. 6104, 2010, 47-58
[3]. Faizul Navi Khan, Kapil Govil, 2013, Distributed Task Allocation Scheme for Performance Improvement
in Mobile Computing Network, International Journal of Trends in Computer Science, vol: 2 issue: 3, pp:
809-817
[4]. Faizul Navi Khan, Kapil Govil, 2013. Static Approach for Efficient Task Allocation in Distributed
Environment. International Journal of Computer Applications, Vol. 81, Issue 81, 19-22
[5]. Ilavarasan E, Manoharan R, 2010, High Performance and Energy Efficient Task Scheduling Algorithm for
Heterogeneous Mobile Computing System, International Journal of Computer Science & Information
Technology, Vol. 2, Issue 2, 10-27
[6]. Kapil Govil and Dr. Avanish Kumar. 2011. A modified and efficient algorithm for Static task assignment in
Distributed Processing Environment. International Journal of Computer Applications, Vol. 23, Number 8,
Article 1, 1–5, ISBN: 978-93-80752-82-3, ISSN: 0975 – 8887.
[7]. Kovvur Ram Mohan Rao, Ramachandram S, Vijaya Kumar Kadappa,Govardhan A, 2011, A Reliable
Distributed Grid Scheduler for Independent Tasks, IJCSI International Journal of Computer Science Issues,
Vol. 8, Issue 2, 296-301
[8]. Lei Liu, Chunlin Li, 2010, Mobile Grid Task Scheduling Considering Resource Reliability, Computer
Network and Multimedia Technology, ISBN:978-1-4244-5272-9, 1-4
[9]. Mohammad Abdollahi Azgomi, Reza Entezari-Maleki, 2010, Task scheduling modelling and reliability
evaluation of grid services using coloured Petri nets, Future Generation Computer Systems, Volume 26,
Issue 8, 1141–1150
[10]. Naif Aljabr, Fathy Eassa, 2013, Scheduling Manager for Mobile Cloud Using Multi-Agents, International
Journal of Computer and Information Technology, Vol. 02, Issue 3, 451-457
[11]. Pankaj Saxena, Kapil Govil, 2013. An Optimized Algorithm for Enhancement of Performance of
Distributed Computing System. International Journal of Computer Applications, Vol. 64, Issue 2, 37-42
[12]. Qin-Ma Kang, Hong He, Hui-Min Song, and Rong Den, 2010, Task allocation for maximizing reliability of
distributed computing systems using honeybee mating optimization”, Journal of Systems and Software,
Volume 83, Issue 11, 2165–2174
[13]. Rajesh D. Bharati, Vilas N. Jagtap, Omsagar C. Gupta, Shivanand S. Landge, 2013, Task Allocation for
Maximizing Reliability of Distributed Computing Systems using Dynamic Greedy Heuristic, International
Journal of Advanced Research in Computer and Communication Engineering, Vol. 2, Issue 3, pp 15541557
[14]. Raminder Kaur 2006. Introuduction to Mobile Computing. The Journal of Computer Science and
Information Tehcnology, Vol. 4, Issue 1, 83-27.
[15]. S.C Shah, S.H. Chauhdary, A.K. Bashir, M.S.Park, 2010, A Centralized Location-Based Job Scheduling
Algorithm for Inter-dependent Jobs in Mobile Ad Hoc Computational Grids, Journal of Applied Sciences,
Vol. 10, Issue 3, 174-181
[16]. Sayed Chhattan Shaha, Qurat-Ul-Ain Nizamanib, Sajjad Hussain Chauhdaryc, Myong-Soon Parkd, 2012,
An effective and robust two-phase resource allocation scheme for interdependent tasks in mobile ad hoc
computational Grids, Journal of Parallel and Distributed Computing, Vol. 72, Issue 12, 1664-1679
[17]. Sri Chusri Haryanti, Riri Fitri Sari, 2014, Reliability of Resource Allocation in Mobile Ad Hoc Grid with
Tasks Replication, Journal of Computers, Vol. 9, Issue 2, 328-336
[18]. Thenmozhi, S, A. Tamilarasi, P.T. Vanathi, 2012, A Fault Tolerant Resource Allocation Architecture for
Mobile Grid, Journal of Computer Science, Vol. 8, Issue 6, 978-982
[19]. Wei – Ming Lin. 2008. Performance modeling and analysis of correlated parallel computations. Elsevier
Inc. Vol. 34, Issue 9, 521 – 538
[20]. Yan Maa, b, Bin Gonga, Ryo Sugiharab, Rajesh Guptab, 2012, Energy-efficient deadline scheduling for
heterogeneous systems, Journal of Parallel and Distributed Computing, Vol. 72, Issue 12, 1725-1740.

640

Vol. 7, Issue 2, pp. 635-641

International Journal of Advances in Engineering & Technology, May, 2014.
©IJAET
ISSN: 22311963

AUTHORS BIOGRAPHY
Faizul Navi Khan completed his Master in Computer Application from M.D.
University Rohtak (Haryana) India in the year 2006, and currently pursuing Ph.D. in
Computer Application from Teerthanker Mahaveer University Moradabad, UP,
India. He has more than 7+ years of work experience in IT Industry. He is the author
of more than 10 research papers published in various journals and conference
proceedings.
Kapil Govil received his Ph.D. from Bundelkhand University, Jhansi, Uttar Pradesh,
India; He has more than 6+ years of work experience in R&D. He has been
contributed more than 50 technical research papers, published in various journals
and conference proceedings.

641

Vol. 7, Issue 2, pp. 635-641


Related documents


42i20 ijaet0520965 v7 iss2 635 641
13i17 ijaet1117303 v6 iss5 2064 2077
19i15 ijaet0715605 v6 iss3 1194to1198
16i18 ijaet0118653 v6 iss6 2455 2463
ijetr011814
21i15 ijaet0715613 v6 iss3 1205to1210


Related keywords