ISSN: 2229-371X

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Computing the Signal Duration to Minimize Average Waiting Time using Round Robin Algorithm

Pratishtha Gupta *1, G.N Purohit2, Sweta Pandey 3
  1. Computer Science, Banasthali University, Jaipur, Rajasthan, India
  2. Mathematics & Statistics, Banasthali University, Jaipur, Rajasthan, India
  3. Information Technology, Banasthali University, Jaipur, Rajasthan,
Corresponding Author: Pratishtha Gupta, E-mail: pratishtha11@gmail.com
Related article at Pubmed, Scholar Google

Visit for more related articles at Journal of Global Research in Computer Sciences

Abstract

Real Time Traffic Signal Control System using CCTV cameras adjust dynamically the signal timings of the intersection points in response to variation in traffic load and system capacity. Round Robin Scheduling Algorithm has been suggested for computing the green signal time to release the computed traffic load with minimum average waiting time. This time can be used to logically regulate the traffic flow on the roads. Relationship has been analysed between minimum average waiting time and the quantum time allotted to each side of the intersection point to release the traffic load.

Keywords

Image processing, MATLAB simulation, Traffic load computation, Round Robin Scheduling

INTRODUCTION

Real time traffic signal control has become a challenging problem as well as the need of hour to make road traffic decent, safe, less time and fuel consuming. So, the problem constitutes of computing green signal time to automate traffic signal control at the junctions. In case of high density of vehicles, long queues and wide area being covered by vehicles which cannot be released in one go, switching of green signals on alternative routes must be stimulated.
Round Robin Scheduling is one of the oldest, simplest, fairest and most widely used scheduling algorithms, designed especially for time-sharing systems. Since logical regulation of traffic load at various sides of intersection point is a kind of time-sharing system, Round Robin Scheduling algorithm has been customized for this purpose. For different small unit of time, called timeslice or quantum alloted to release traffic load on each side of intersection point, average waiting time for the traffic is computed. Graphical relationship has been established between time quantum and average waiting time to find the time quantum for minimum average waiting time corresponding to different categories of traffic load.
This paper comprises of seven sections including the introduction which shows the goal of the paper. Section II presents the related work.the experimental environment and the algorithm used for the experiment.Section IV discusses the concepts of traffic categories used for the study. Section V discusses the proposed algorithm. Section VI describes the simulation experiment and results. Section VII draws the conclusion and finally the references and short biography of the authors is presented.

RELATED PAPER

Noon et al .[1] propose a new algorithm, called AN, based on a new approach called dynamic-time-quantum; the idea of this approach is to make the operating systems adjusts the time quantum according to the burst time of the set of waiting processes in the ready queue.
Jbira et al. [2] illustrate the extending of green phases for oversaturated input links, and also authorizes the calculation of optimal green durations proportionally to the real time queues sizes for other under-saturated input links. This leads to make the cycle time to be dynamic according to global traffic flow state and consequently allowing appropriate discharge of oversaturated intersections.
Rajput et al. [3] objective of this paper is to develop a new approach for round robin C P U scheduling algorithm which improves the performance of CPU in real time operating system. The proposed Priority based Round-Robin CPU Scheduling algorithm is based on the integration of round-robin and priority scheduling algorithm. It retains the advantage of round robin in reducing starvation and also integrates the advantage of priority scheduling.
Mustafa et al. [4] describe a method using integer programming has been proposed to solve equations that decide a value that is neither too large nor too small such that every process has reason able response time and the throughput of the system is not de creased due to unnecessarily context switches.
Ahad et al. [5] illustrates a process which divides the processes waiting in the ready queue in two categories. The processes in the first category are the one for which we will modify the time quantum and the processes in the second category will be processed as per the classical round robin algorithm. We have also compared our proposal with the classical round robin algorithm and the results are depicted in tabular form.
Siregar et al. [6] describes an approach to combine Round Robin with Genetic algorithm. In this approach, an individual is a quantum that will be iterated for achieving best quantum that will produce minimal average waiting time.
Yadav et al. [7] describes a new approach for round robin scheduling algorithm which helps to improve the efficiency of CPU and average waiting time.
Nayak et al. [8] present a new variant of RR scheduling algorithm known as Improved Round Robin (IRR) Scheduling algorithm, by arranging the processes according to their shortest burst time and assigning each of them with an optimal time quantum which is able to reduce all the above said disadvantages.
Singh et al. [9] objective of this paper is to develop a new approach for round robin scheduling which help to improve the CPU efficiency in real time and time sharing operating system.
Mohanty et al. [10] describe a new variant of Round Robin (RR) algorithm is proposed which is suitable for soft real time systems. RR algorithm performs optimally in timeshared systems, but it is not suitable for soft real time systems. Because it gives more number of context switches, larger waiting time and larger response time.
Jensen et al. [11] presented a preliminary overview into a significant research effort recently initiated within the Archons project. The goals of this work include further understanding the scheduling problem in the presence of user-defined value functions, determining the heuristics necessary to create attractable value function scheduler, understanding the sensitivity of such a scheduler to the parameters defined by its heuristics, and analyzing the decisions made by those heuristics.

EXPERIMENTAL ENVIRONMENT

MATLAB MATLAB is a high level language that provides a highly interactive and user friendly environment to solve different classes of problems, the most prominent among them being Image Processing.
This is a vast collection of computational algorithms ranging from elementary function like sum, sine, cosine and complex arithmetic, to more sophisticated functions like matrix inverse, Matrix Eigen values, Bessel functions, and fast Fourier transforms.
Matlab has a great capability for graphing or plotting. Multiple graphs can be drawn in one window, the viewpoint for 3-D plots can be changed and axes can be controlled.

ROUND ROBIN SCHEDULING AND TRAFFIC LOAD CATEGORIES

Round Robin Scheduling

In round robin algorithm no process is allocated CPU for more than one time slice in a row. If the CPU process exceeds one time slice, the concern process will be preempted and put into the ready queue. The process is preempted after the first time quantum and the CPU is given to the next process which is in the ready queue (process B), similarly schedules all the proceses and completes the first cycle. In the second cycle same method is used to schedule the processes.

Traffic Load Categories

Intersection Point with four sides has been assumed for the study..
Three categories of traffic load have been proposed

1. SPARSE

Traffic load is light on all four sides of the intersection point.

2. DENSE

Traffic load is heavy on all four sides of the intersection point.

3. SPARSE -DENSE

Traffic Load is light on one or two sides of the intersection point while traffic load is heavy on other sides.
In each category, four processes with same processing time are taken with dynamic quantum time taken. And after that their average waiting time is calculated for each category.

PROPOSED ALGORITHM

Flow chart:

In the flowchart given in figure 1, procedure for computing the average waiting time for given traffic loads on all sides and the given quantum time is presented. Round Robin Scheduling Algorithm has been modified, where the traffic release from all sides are considered as different tasks, which are added into the queue and processing is applied till all the tasks are finished.

SIMULATION EXPERIMENT AND RESULTS

For different categories of traffic loads and different quantum times, average waiting time is calculated. From graphical analysis( figure 2, figure 3 and figure 4), quantum time is found for which minimum average waiting time is achieved(Table 1, Table 2 and Table 3).
image
image
image
image
image

EXPERIMENTAL RESULTS

Above experiments show the following results:
1. With the increase in traffic load, minimum waiting time increases.
2. Quantum Time for which the minimum waiting time is achieved depends on the the type of traffic load.
3. Quantum Time for minimum waiting time shifts to right with the increase in traffic load.
Hence, from the above graphical analysis, quantum time can be chosen so as to get the minimum waiting time.

CONCLUSION

A novel approach has been used in which round robin scheduling is applied to analyse the effect of type of traffic load on the quantum time to achieve the minimum waiting time. The three categories have been studied namely sparse, dense and combination of sparse and dense .In this by changing the timer, the average waiting time in each case has been calculated. Graphical Analysis prove that carefully chosen quantum time for traffic signal duration can lead average waiting to its minimum and can save the invaluable time and fuel of road users.

References

  1. Noon. A, Kalakech. A.” A New Round Robin Based Scheduling Algorithm for Operating Systems: Dynamic Quantum Using the Mean Average” , IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 3, No. 1, May 2011 ISSN (Online): 1694-0814
  2. Jbira.M, Ahmed.M. A Hybrid Modeling Approach for Traffic Light Control of Oversaturated Intersections”, International Journal of Research and Reviews in Computer Science (IJRRCS) Vol. 3, No. 1, February 2012, ISSN: 2079-2557)
  3. Rajput.I, Gupta.D.” A Priority based Round Robin CPU Scheduling Algorithm for Real Time Systems” (InternationalJournal of Innovations in Engineering and Technology (IJIET) Vol. 1)
  4. Mostafa.S, Hamad.S.” FINDING TIME QUANTUM OF ROUND ROBIN CPU SCHEDULING ALGORITHM IN GENERAL COMPUTING SYSTEMS USING INTEGER PROGRAMMING”( IJRRAS 5 (1) October 2010)
  5. Ahad.M,” Modifying Round Robin Algorithm for Process Scheduling using Dynamic Quantum Precision” (IJCA Special Issue on Issues and Challenges in Networking, Intelligence and Computing Technologies ICNICT (3):5-10, November 2012.)
  6. Siregar.M,” A New Approach to CPU Scheduling Algorithm Genetic Round Robin” (International Journal of Computer Applications 47(19):18-25, June 2012)
  7. Yadav.R, Mishra.A.” An Improved Round Robin Scheduling Algorithm for CPU scheduling” (international Journal on Computer Science and Engineering Vol. 02, No. 04, 2010, 1064-1066)
  8. Nayak.D, Malla.S,”Improved Round Robin Scheduling using Dynamic Time Quantum” (international Journal of Computer Applications (0975 –8887) Volume 38–No.5, January 2012)
  9. Singh. A, Goyal.P.” An Optimized Round Robin Scheduling Algorithm for CPU Scheduling” (International Journal on Computer Science and Engineering 01/2010)
  10. Mohanty.R, Patwari.K.” Priority Based Dynamic Round Robin Algorithm with Intelligent Time Slice for Soft Real Time Systems” (IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 2, No.2, February2011)
  11. Jensen.E, Locke.C.” A Time-Driven Scheduling Model for Real-Time Operating Systems” (http://users.soe.ucsc.edu/~sbrandt/courses/Winter00/290 S/jensen.pdf).