From Worst-Case Gini Coefficient to Preemptive Multitasking: Consideration for Fairness and Efficiency in Intelligent Transportation Systems

Abstract

When a system is developed, the throughput of the system is usually placed above all other measures of success. The quantifiable fairness value of a population allows for the expression of the spread of a shared resource throughout the population to indicate the experience of individual actors. The issue of fairness was explored in three different areas: Vehicular Ad-hoc Networks (VANETs), Mixed-Criticality Systems, and Actuated Traffic Control Systems (ATCSs). VANETs rely on broadcasting packets for some safety applications. The Gini Coefficient (a sociological measure which quantifies the inequality of income distribution) is used to determine the inequality of packet broadcast delay in varying vehicle densities and while using different Medium Access Control (MAC) schemes. After a number of experiments, it was found that the fairness value would change depending on stochastic factors. Using the process of system identification, a Worst Case Gini Coefficient (WCGC) was identified and then derived for any bounded population. A comparison between the Gini and Jain measures was conducted. It was also found that fairness should not be the only metric used for determining the spread of a shared resource, as poor performance can show a high degree of fairness, as the lack of resources is seen as a fair distribution. Mixed-Criticality Systems are a type of embedded system which contains tasks and functions of different criticalities. While most research deals with ensuring reliability high-criticality tasks, there is little research into the reliability of non-critical tasks. Based on the field of telecommunications, a Grade of Service (GoS) metric was proposed for the execution performance of non-critical tasks. A target execution rate ε was also introduced to give the system designer control over the execution of non-critical tasks. Different scheduling algorithms were tested for the execution of non-critical tasks when a processor was over-utilised, leading to degraded performance. What performance power remained was spread between the tasks at the discretion of the scheduling algorithm. A fair algorithm which spreads task processing in a proportional manner was found to be the most effective. It was also shown that high system throughput can initially be seen as a positive factor, but when the fairness of these systems is examined, usually the high throughput of the majority of tasks is due to the starvation of a few. ATCSs are a method by which traffic signals are operated in an intelligent manner. The most prolific ATCSs remain unchanged since the advent of modern computing. Traditionally, the flow of traffic is based upon the flow of water within a pipe. In this thesis, a new paradigm for ATCSs is introduced where traffic is equated to a computer instruction, traffic queues to computer tasks, and traffic intersections to computer processors. With this new paradigm, the traffic problem can be reposed as a computing problem. A computer-systems approach was taken to develop a new ATCS which was compared to the status quo across four intersections. The ATCS, in any configuration, outperformed the status quo in speed, reducing delay, and fairness of the spread of delay across all vehicles. The issue of fairness was explored across different fields with common ties between them. Firstly, fairness should not be overlooked in a system - if system performance seems too good, fairness may dictate that a few costly actors are being starved for the increased performance of the many. Secondly, fairness should not be the primary measure for the success of a system. Chasing fairness will result in poor system performance, as a system which starves all tasks equally will still be seen as fair. This thesis provided three core contributions: A limit to Gini fairness (the worst case Gini coefficient) was identified, proven, and derived. A new quantifiable measure for the execution of non-critical tasks in mixed-criticality systems was developed. Finally, a new paradigm for traffic modelling was introduced which equated traffic to computer instructions - this lead to the development of an ATCS using computer scheduling algorithms to solve traffic problems in an efficient and fair manner.