Uber-like system
The goal of the project is to develop SETA (SElf-driving TAxi service), a peer-to-peer system of self-driving taxis for the citizens of a smart city.
(The self driving and pathfinding will not be implemented and substituded with a simple 10x10 matrix representing the smart-city and point to point distance calculation)
The smart city is divided into four districts. The citizens of the smart city use SETA to request a selfdriving taxi that takes them from their current position to a destination point. In SETA, the taxis of the smart city coordinate with each other to decide which taxi will handle each of such requests. Each taxi is also equipped with a sensor that periodically detects the air pollution level of the smart city. Moreover, every ride consumes the battery level of the taxi. When the residual battery level is too low, the taxi must go to the recharge station of the district in which it is positioned.
Periodically, the taxis have to communicate to a remote server called Administrator Server information about the air pollution levels, the number of completed 1rides, the number of kilometers driven, and the remaining battery level.
The SETA administrators (Administrator Client) are in charge ofmonitoring this information through the Administrator Server. Furthermore, through the Administrator Server it is also possible to dynamically register and remove taxis from the system.
The prject is composed of the following different applications:
A process that simulates the taxi service request generated by the citizens that myst be cinnybcated ti the fleet of self-driving taxis through MQTT.
The MQTT broker is used by SETA to communicate to the taxis and vice-versa. We will use Mosquito as our MQTT broker. https://mosquitto.org/
A specific self-driving taxi of the system. A taxi may termiante in an un-controlled way. Taxis clock are not synchronized.
REST server that receives statistics from the smart city taxis and dynamically adds/removes taxis from the network.
A client that queries the Adminsitrator Server to obtain informations about the statiscrs if the taxis and their rides.
The smart city is represented as a 10 × 10 grid, divided into four 5×5 districts. Each cell of the grid represents a square kilometer of the smart city.
At a specific time, each cell may contain an arbitrary number of taxis (i.e., 0, 1, more than 1). When a taxi is registered within SETA, it will be randomly placed at the recharge station cell of one of the districts.
The MQTT Broker on which SETA relies is online at the following address:
tcp://localhost:1883
SETA uses this broker to communicate the ride requests of the smart city citizens to the taxis. As it will be described in the next section, SETA uses a dedicated topic for the requests originating in each district of the smart city. SETA publishes on these topics, while the taxis subscribe to them in order to receive the ride requests.
SETA is a process that simulates the taxi service requests generated by the citizens of the smart city. Specifically, this process generates 2 new ride requests from the citizens every 5 seconds. Every ride request is characterized by: • ID • Starting Position • Destination Position Starting and destination points are expressed as the Cartesian coordinates of a smart city’s grid cell. Such coordinates must be randomly generated. Each ride’s starting and destination points may be located in the same district as well as in different districts. The starting and the destination point of a ride must be different.
To communicate the generated rides to the taxis of the smart city, SETA relies on the MQTT Broker presented in Section 3. Specifically, SETA assumes the role of publisher for the following four MQTT topics:
- seta/smartcity/rides/district1
- seta/smartcity/rides/district2
- seta/smartcity/rides/district3
- seta/smartcity/rides/district4
Whenever a new ride request with starting point included in the district i is generated, SETA publishes such a request on the following MQTT topic:
seta/smartcity/rides/district{i}
SETA will subscribe (not publishing) to other topics that will help its coordination with taxis in the system
Whenever a taxis start traveling, carring a specific ride, will communicate to SETA, in order to prevent SETA publishing again that specific ride.
seta/smartcity/traveling
Whenever a taxi terminate in an uncontrolled way, other taxis in the system will communicate to SETA the death of that specific taxi.
seta/smartcity/death
Whenever a taxi enters the smart-city or changes distrcit, it will communicate to SETA through this topics:
seta/smartcity/taxi/district1
seta/smartcity/taxi/district2
seta/smartcity/taxi/district3
seta/smartcity/taxi/district4
SETA will publish every ride request of that district on the district topic.
A ride request sent to the taxis may not find right away a taxi or a taxi may termiante in an un-controlled way during the trasveling process. To handle these limit cases SETA has 3 lists:
- Ride Request Sent Whenever a ride request is generated, it will be immediatly publish on the right topic, and it will be added to this list
- Ride in Travel Whenever a taxi starts traveling with a specific ride request, it will publish it on the correct topic and SETA will remove that ride request from the list Ride Request Sent and will add its id and the id of the ride request to the list.
- Ride Completed Whenever a taxi completes a ride, it will publish on the right topic its accomplishment, SETA will add its id and the ride's id to the list
If a taxi un-controlled termination is catched by the other taxis in the system and publish on the correct topic, SETA check if that taxi was traveling with a specific ride request, in that case will remove the ride from the Ride in Travel and will add it back to the list Ride Request Sent, ready to be published again.
Each taxi is responsible for:
- Coordinating itself with the other taxis by using gRPC to decide which taxi will take charge od each ride request generated by SETA.
- Accomplishing the rides it takes charge of: bring the citizen from the starting point to the destination point of the ride.
- Sending its local statistics to the Server Admin.
A Taxi is initialized by specifyng:
- ID
- listening port for the communication with the other taxis
- Administrator Server's address
- Battery level 100%
- A random (between 1 nad 10) logical increment (more on this in section Clock Syncronization and Lamport's Algoriothm)
Once it is launched, the Taxi will register itself to the system through the Administrator Server. If the are no taxis with the same ID and recevies, from Administrator Server:
- Starting position in the smart city (one of the 4 recharger stations)
- The list of the other **taxis already present in the smart city.
Once it receives this informations, it starts acquiring data from the pollution sensor.
Then, if there are other taxis in the smart city, the taxi presents itself, through the Greetings gRPC to the other taxis by sending them its position in the grid.
Finally, the taxi subscribes to the MQTT topic of its district and all the other additional topic described before. As it will be explained in Section Ride Management, the taxis of the smart city coordinate with each other to decide which taxi will handle each ride request.
When a Taxi takes charge of a ride, it simulates the delivery time with a Thread.sleep() of 5 seconds. A taxi may terminate in an un-controlled way during its traveling simulation; this exception will be explained in section Un-controlled Termination.
If the destination point of the ride is in another district compared to the one of the starting position, then the Taxi which accomplished the ride has to unsubscribe from the MQTT topic of the starting district. Then, it will subscribe to the MQTT topic of the destination district.
The taxis of each district must use a distributed and decentralized algorithm to decide who will take charge of each ride. The choosen algorith is: Ricart–Agrawala a mutual exclusion algorithm.
Specifically, each ride will be handled by the Taxi (located in the same district of the ride’s starting position) which meets the following criteria:
- the Taxi must not be already involved in another ride or a recharge process
- the Taxi must have the minimum distance from the starting point of the ride
- if more taxis meet the previous criteria, it must be chosen among them the Taxi with the highest battery level
- if more taxis meet the previous criteria, it must be chosen among them the Taxi with the lowest logical clock value
- if more taxis meet the previous criteria, it must be chosen among them the Taxi with the highest ID
To compute the distance between two points P1 = (x1, y1) e P2 = (x2, y2) of the smart city, you should use the following formula:
d(P1, P2) = sqrt((x1 -x2)^2 + (y2 - y1)^2)
If in a district there is no Taxi that is available to take charge of a ride, such a ride must not be discarded. SETA will manage this problem using multiple list of ride request sent, as presented in the section Ride Request Management.
Every 15 seconds, each Taxi has to compute and communicate to the administrator server the following local statistics (computed during this interval of 15 seconds):
- The number of kilometers traveled to accomplish the rides of the taxi.
- The number of rides accomplished by the taxi.
- The list of the averages of the pollution levels measurements. Once the local statistics have been computed, the *Taxié sends them to the Administrator Server associated with
- The ID of the Taxi.
- The timestamp in which the local statistics were computed.
- The current battery level of the Taxi.
A Taxi consumes 1% of its battery level for each kilometer traveled to accomplish a ride. For simplicity, it is assumed that the battery consumption is computed only at the end of each ride.
When the battery level of the Taxi is below 30%, the taxi must go to the recharge station of its district. A recharge station may be accessed only by a single taxi at a time. It is also possible to explicitly ask a Taxi to recharge its battery through a specific command (i.e., recharge) on the command line.
To coordinate the Taxi it has been implemented the distributed algorithm for mutual exclusion Ricart–Agrawala. (The same used for ride coordination)
The clocks of the Taxis are not synchronized and it has been implemented Lamport's Algorithm to enusre total order.
If a taxi takes part to the mutual exclusion algorithm in order to recharge its battery, it cannot accept any rides until the recharging process of its battery is completed. Moreover, when a taxi acquires rights to recharge its battery:
- it consumes 1% of its battery level for each kilometer traveled to reach the recharge station
- its position becomes the same as the cell of the recharge station of the district in which the taxi is currently positioned.
The recharging operation is simulated through a Thread.sleep() of 10 seconds.
It is assumed that each Taxi terminates only in a controlled way. Specifically, only when the message ”quit” is inserted into the command line of a taxi process, the taxi will leave the system. In both cases, to leave the system, a Taxi must follow the next steps:
- complete the possible ride it is involved in, sending to the Administrator Server the information described in Section sending information to the server.
- complete any battery recharge • notify the other taxis of the smart city • request the Administrator Server to leave the smart city.
Each taxi is equipped with a sensor that periodically detects the air pollution level of the smart city. Each pollution sensor periodically produces measurements of the level of fine particles in the air (PM10). Every single measurement is characterized by:
- PM10 value
- Timestamp of the measurement, expressed in milliseconds
The generation of such measurements is produced by a simulator. Each simulator assigns the number of seconds after midnight as the timestamp associated with a measurement. During the initialization step, each Taxi launches the simulator thread that will generate the measurements for the air pollution sensor. Each simulator is a thread that consists of an infinite loop that periodically generates (with a pre-defined frequency) the simulated measurements. Such measurements are added to a proper data structure. The interface (Buffer) of this data structure exposes two methods:
void add(Measurement m)
List <Measurement> readAllAndClean()
Note that each Taxi is equipped with a single sensor. The simulation thread uses the method addMeasurement to fill the data structure. Instead, the method readAllAndClean, must be used to obtain the measurements stored in the data structure. At the end of a read operation, readAllAndClean makes room for new measurements in the buffer. Process sensor data is processed through the sliding window technique. Bufffer of 8 measurements, with an overlap factor of 50%. When the dimension of the buffer is equal to 8 measurements, compute the average of these 8 measurements. A Taxi will send these averages to the Administrator Server with the other information about the ride it accomplished.
The Administrator Server collects the IDs of the taxis registered to the system, and also receives from the taxis their local statistics. This information will then be queried by the administrators of the system (Administrator Client). Thus, this server has to provide different REST interfaces for:
- managing the taxis network
- receiving the local statistics from the taxis
- enabling the administrators to execute the queries
The server has to store the following information for each taxi joining the smart city:
- ID
- IP address (localhost in this case)
- Port Number on which it is available to handle the communication with other taxis
Moreover, the server is in charge of assigning to each joining taxi a randomly chosen district of the smart city. A Taxi can be added to the network only if there are no other taxis with the same identifier. If the insertion succeeds, the Administrator Server returns to the Taxi
-
the starting position of the taxi in the smart city, i.e., the position of the recharge station of the randomly chosen district
-
the list of taxis already located in the smart city, specifying for each of them the related ID, IP address, and the port number for communication
Whenever a Taxi asks the Administrator Server to leave the system, the server has to remove it from the data structure representing the smart city.
The Administrator Server must provide an interface to receive the local statistics from the taxis of the smart city. These data have to be stored in proper data structures that will be used to perform subsequent analysis. Indeed, the taxis of the smart city could send their local statistics while the Administrator Client is requesting to the Administrator Server to perform some computations on such statistics.
When requested by the Administrator Client through the interface descripted in Section 7, the Administrator Server must be able to compute the following statistics:
- The list of the taxis currently located in the smart city
- The average of the last n local statistics of a given Taxi. In particular, it has to compute the average number of:
- travelled kilometers
- battery level
- pollution level
- number of accomplished rides
- The average of the previously introduced statistics provided by all the taxis and occurred from timestamps t1 and t2
The Administrator Client consists of a simple command-line interface that enables interacting with the REST interface provided by the Administrator Server. Hence, this application prints a straightforward menu to select one of the services offered by the administrator server and to enter possible required parameters.
- grandle 6.7
- Java version 1.8.0_332