Keywords

1 Introduction

Nowadays, the cities are becoming very large, with the number of urban residents expanding by nearly 60 million every year, and more than 60% of the world’s population expecting to be living in cities by 2050, leading to the emergence of some problems, namely pollution, waste and traffic. A Smart City [9] aims to make the citizens’ daily life more comfortable and convenient by using emergent technologies to provide accessibility to public information and services [2]. Particularly, citizens will get access to advanced facilities like smart transportation facilities, smart electricity systems and smart applications for governance.

In terms of traffic, the parking problem can be crucial for the improvement of the smart city concept, since 40% of the traffic in New York is generated by drivers trying to find a spot to park their cars [8]. In this way, a parking that uses advanced technologies to improve its management and the provided services can contribute for a reduction of the traffic [8]. Additionally, a best management of the available parking spots allows to achieve a better profit for the parking and best prices for the drivers.

On the other hand, smart parking systems are not easy to build due to their dynamic and sometimes chaotic environments. In fact, the system needs to be able to deal with a significant amount of drivers asking and receiving offers for parking spots, and at the same time, the parking needs to decide which requests will satisfy more. Due to its dynamics, large-scale and often chaotic nature, the use of distributed systems can be helpful, being easier to divide the entire complex process into simpler micro processes than having a single entity encharged by the entire process [15].

In particular, multi-agent systems (MAS) [10] offers an alternative way to design such systems by distributing the intelligence and control over a community of autonomous and cooperative agents that will cooperate to achieve their objectives. In the smart parking problem, the agents will represent the drivers of cars, bikes and trucks, and the parking spots available in the system. The use of MAS solutions provide scalability, i.e. the system continues operating under condition even with the increase of the number of agents, and flexibility, i.e. the system can be adapted for different use cases, such as a car parking, a bicycle parking or considering bike and cars at the same time.

Traditionally, the smart parking system is approached using a centralized monolithic solution, but recently the adoption of MAS is being reported in the literature (see for example, [5] and [16]). However, in these works, the negotiation among the agents follows a centralized approach, which simplifies its implementation but limits the use of the MAS potentialities. In fact, during the negotiation among the agents to find a consensus, each type of agent has its own objectives that usually are in conflict: drivers want to pay as less as possible and the parking spots want to receive as much as possible.

The huge number of agents interacting with each other may affect the negotiation strategy and consequently the system performance. The negotiation needs to be simple and fast enough and yet show a good balance for both the driver and the parking perspectives. Also, aiming to be competitive, the parking system needs to have the capability to understand the environment and adapts the prices depending of the amount of requests for parking spots and the amount of vehicles nearby.

The objective of this paper is to study negotiation protocols for consensus problems in smart parking systems. In particular, the Contract Net Protocol (CNP), the English auction and the Dutch auction strategies were implemented using the JADE agent-based framework under the agent-based smart parking system [3]. These strategies were implemented using the interaction protocols defined by the Foundation for Intelligent Physical Agents (FIPA) [1], and tested according to different scenarios. The evaluation has considered the level of satisfaction of the actors in the system, the scalability and the negotiation time.

The remainder of this paper is organized as follows. Section 2 overviews the agent-based architecture for the smart parking system and highlights the importance of negotiation protocols to address the consensus problems in such distributed systems. Section 3 analyses several existing negotiation protocols found in literature and Sect. 4 describes the implementation of three negotiation protocols using the JADE framework. Section 5 analyses the achieved experimental results under the smart parking context perspective, and finally, Sect. 6 rounds up the paper with the conclusions and points out the future work.

2 Multi-agent System Architecture for Smart Parking

In order to solve the smart-parking problem, an agent-based model was adopted due its capability to distributed intelligence and processing power, as well as the offered scalability. The system architecture establishes two types of agents: the driver agent representing the person that drives the vehicle and the spot agent representing a specific place to park a vehicle. In such agent-based cyber-physical system, the system components combine cyber and physical parts, e.g., a spot agent being the cyber part and the parking spot being the physical asset.

A parking spot can have different levels of granularity, i.e. can represent the entire car park, a floor of the park, a sector or only a single spot. The design of such feature can be performed by using the holonic principles [7], where holarchies can be used to organize the agents and the recursivity property can be explored, simplifying the design of such large-scale and complex parking systems. A useful example is given by a parking organized in sectors, where each sector comprises a set of spots. With this approach the sectors only negotiate with the inner spots to offer a parking spot to the driver, instead to have a completely flat negotiation among drivers and parking spots.

Figure 1 illustrates the use cases for the smart parking system, being possible to see the interactions among the system entities. In such model, it is possible to verify its flexibility since one driver can have and administrate more than one vehicle, which can be a car or a bike. Another feature of this model is the “admSpot” that represents the parking, which can create the desired number of spot agents, that will work separately. As a consequence, the system will be robust, preventing the system to break no mater how many agents fails, until all of them fails.

Fig. 1.
figure 1

Use cases for the smart parking system.

Full size image

The most important part of the system is related to the “Negotiate Parking Spot” case, involving the interaction between the spot and driver agents. This use case assumes a crucial importance because in MAS, the overall behaviour emerges from the interaction among individual agents, and in this case the negotiation is between two type of actors that presents different interests: driver agents want to get parking spots at the lowest prices and the spot agents wants to offer their services at the highest prices. For this purpose, a proper negotiation strategy should be adopted in order to maximize the efficiency of the MAS-based parking system.

In this work, three different negotiation protocols are studied, implemented and compared in order to evaluate which one better fits the smart parking requirements.

3 Analysis of Negotiation Protocols

In distributed systems, the cooperation assumes a crucial issue, being presented in different forms, like collaboration, negotiation and competition, depending of the objective of the participants in the cooperation schema. Since in the parking system, the driver and spot agents have opposite interests, the cooperation in such system will be in terms of a negotiation to find a consensus, pleasing both parts.

Negotiation can be defined as the effort made by two or more entities to achieve an agreement benefiting themselves [17]. The complexity of the negotiation is mainly dependent of the following parameters:

  • Goals: each entity (agent) or community of entities have specific goals, which cannot be compatible.

  • Dependencies of tasks: the execution of tasks is inter-related and in the negotiation process should be considered the dependencies and precedences between tasks.

  • Incomplete information: in some cases, it is necessary to negotiate without to know all information about one problem.

In the literature, several negotiation strategies can be found, namely the English auction, the Dutch auction and the CNP. These three mechanisms have different characteristics and the selection of the best one is dependent of the system requirements and application scenario. The next subsections will detail the principles of these three negotiation strategies and describe how they can be adopted in the smart parking problem.

3.1 Contract Net Protocol (CNP)

The CNP is a well-known negotiation protocol and widely used to implement the co-operation process [14]. Basically, this negotiation process works like a bidding process, where the agents exchange messages according to the pattern illustrated in Fig. 2.

Fig. 2.
figure 2

Interaction diagram for the Contract Net Protocol [1].

Full size image

Initially, the Initiator agent initiates the negotiation by announcing the auction to the Participant agents. This announcement message will contain the eligibility specifications that the participant agents will have to satisfy in order to participate in the auction, the specification of the task and the deadline to respond. When a participant agent receives an announcement message, it verifies if the required specifications can be satisfied by itself, and in affirmative case it sends a bid proposal indicating its capacities and conditions to participate in the auction. After receiving the replies, the Initiator evaluates all arrived bid proposals and decides which one is accepted according to its selection criteria. If none satisfies the Initiator, a new iteration will start with new specifications.

The CNP approach leads to sub-optimal solutions due to its spatial and temporal myopic. Spatial myopia means that the information of the state of others initiator agents is not used during the construction of a bid proposal, while the temporal myopia means that the information of sub-sequent tasks is not used either in the bidding or in the award selection [13]. As the communication process is slower than the computation process, the CNP intends to have reduced communication between the entities, modular and highly independent problems, and no centralized control. However, it presents a problem related to the renegotiation, which may occurs when a deviation occurs, e.g., the non-compliance of the specifications of the task by the awarded entity.

3.2 English Auction

The English auction tries to achieve the consensus between the agents by changing the price over each turn, starting with a bad price for the initiator until none of the participant agents accepts more changes in the price [11]. In this auction, the sequence of messages is represented in Fig. 3.

Fig. 3.
figure 3

Interaction diagram for the English auction [1].

Full size image

Simmilarly to the CNP schema, the Initiator agent initiates the negotiation by announcing the auction to the other agents, which contains the eligibility specifications, the task specification and the deadline to respond. In parallel, the Initiator sends an offer with the price to all participant agents. When an participant agent receives an auction announcement message, the requested specifications, and particularly the price, are verified, and if they can be satisfied a proposal is sent. Otherwise, the announcement is rejected.

If at least one agent accepts the offer, the previous process will be repeated until no agent accepts the new offer. The expectation is that the price can be improved with the new offer and one agent might accept the offer. After no agent agrees with the offer, the Initiator sends a message to the selected entity according to its selection criteria.

The main problem of this auction is the amount of messages exchanged, which means that the increase of the number of participants will significantly increase the number of messages and consequently require more time to achieve the consensus.

3.3 Dutch Auction

Similarly to the English auction, the Dutch auction tries to achieve the consensus between the agents by changing the price over each turn. But instead of starting with a bad price for itself, the initiator starts with a very good price, and iterativelly, the price will be decreased until some participant agent accepts it. The pattern for this auction is represented in Fig. 4.

Fig. 4.
figure 4

Interaction diagram for the dutch auction [1].

Full size image

Initially, the Initiator agent sends a message to the other agents announcing the start of the auction, which includes the eligibility specifications that the agents will have to satisfy to participate the auction and the deadline to respond. After, the Initiator agent sends an offer with the expected price to all participant agents, and waits that one participant accepts the price and makes a propose. When a participant agent receives an auction announcement message, it verifies if the required specifications can be satisfied by itself, and particularly the price, and in affirmative case, it will make a proposal with that price.

If some participant agent accepts the offer, the Initiator sends a message to the selected agent confirming the agreement. Otherwise, it means that the price is not good enough for the participant agents, so it repeats the procedure until one agent accepts the price, the price reaches a value that is not anymore interesting for the Initiator or the negotiation reaches the time limit.

3.4 Comparative Analysis

The English and the Dutch auctions are very similar, with both implementing an interactive process with the objective to get the best price over each interaction. However, the amount of exchanged messages can be a problem, especially for a large number of participants. If the system is not prepared to support a huge amount of communication at once, it may cause some agents to stop working. In contrast, the CNP mechanism consumes less resources and might be a good alternative protocol in scenarios where a large number of agents negotiate at the same time. However, the myopia is a problem exhibited by the CNP protocol. Aiming to overcome some CNP limitations, other approaches that extends its principles were proposed in the literature, namely the Extended Contract Net Protocol (ECNP) [6] and the B-Contract Net [12].

Since, the main objective of this paper is to test these negotiation strategies, it will be possible to verify if there is a significant difference between the performance achieved by the Dutch and the English auctions (i.e. price and distance), and also, to verify if the resources consumption is really needed for achieving better agreements in a fast way.

4 Implementation of the Negotiation Protocols

This section details the experimental tests developed to analyze the different negotiation protocols for the smart parking problem. The agent-based parking system, and particularly the three referred negotiation protocols, was implemented using the JADE framework [4]. JADE is an agent-base framework that facilitates the implementation, debugging and maintenance of agent-based solutions by offering services like the white and yellow pages and the sniffer agent. The agent-based model was developed by implementing the behaviour of the driver and spot agents, and the three described negotiation strategies following the Interaction Protocol Specifications defined by FIPA [1].

An important issue considered during the agents implementation was related to the mechanisms for the price generation, where the average price is selected randomly between 10 and 100. These values represent the highest price that a driver can pay for a spot and the lowest value the spot will accept.

4.1 Scenarios

The behaviour of each negotiation protocol was tested taking into consideration 9 scenarios build up the variation of the number of available parking spots and drivers, considering three sets: small (50), normal (175) and large (300). These scenarios, ranging from 50 drivers and 50 parking spots, to the 300 drivers and 300 parking spots, were experimentally tested 40 times each one.

Since the parking system is a dynamic system, it was considered that the parking spots are available from the beginning, but the driver agents are not created all at the same time, each one having a possibility of 10% to be created. The parking time can range from 1ms to 100 ms, and the searched area for parking by a driver is at maximum 50% of the whole parking.

The profile of the driver and spot agents follows one of three categories reflecting its role in the negotiation process:

  • Conservative, which in terms of the driver agent means that the maximum value that it is willing to pay is 40, and the increasing price step in each negotiation iteration is 5. For the spot agent, the minimal accepted price is 5% below the average price.

  • Moderate, which in terms of the driver agent means that the maximum value that it is willing to pay is 70, and the increasing price step in each negotiation iteration is 10. For the spot agent, the minimal accepted price is 10% below the average price.

  • Aggressive, which in terms of the driver agent means that the maximum value that it is willing to pay is 100, and the increasing price step in each negotiation iteration is 15. For the spot agent, the minimal accepted price is 15% below the average price.

The distribution of profiles in the agents follows a normal distribution, with the system having 30% of conservative agents, 40% of moderated agents and 30% of aggressive agents.

These simulations intends to get all the possible scenarios to see how the system will react with each one of the negotiation strategies. The covered scenarios are very embracing, allowing at the end to conclude about the best negotiation approaches for each scenario. However, an important remark should be considered: these scenarios consider that at the beginning, the parking is empty, with no cars at any parking spot. This means that a 24 h parking is not considered in this work.

4.2 Metrics

The metrics defined to evaluate the negotiation protocols are mainly related to the price paid by the driver to reserve a parking spot and the distance between the desired parking place and the parking spot got by the driver. The achieved results will be evaluated under these two parameters considering the previously described scenarios.

Additionally, the three negotiation strategies are also evaluated taking into consideration the number of messages exchanged during the negotiation process and the time required to conclude the negotiation.

5 Analysis of Experimental Results

This section analyses the results from the experimental testing of the three implemented negotiation protocols, namely the CNP, English auction and Dutch auction, considering the scenarios previously described. Initially, the average values for the price paid and the distance to the desired parking place are analyzed, and finally, other parameters are also compared, namely the number of exchanged messages and the negotiation time.

The agent-based smart parking was running in an Aspire F5-573G, Intel core i5 7200U, 8 GB RAM DDR4, SSD and NVIDEA GeForce 940MX with 2 GB RAM in a Windows 10.

Fig. 5.
figure 5

Results of the price paid by the driver for the three negotiation protocols.

Full size image

5.1 Analysis of the Price Paid by the Driver

The results for the price paid by the driver for the three negotiation protocols are illustrated in Fig. 5. The achieved results for the three strategies follow the same behaviour, with the price remaining stable between 50 and 175 parking spots in the system, and then drooping for scenarios considering more than 175 parking spots, which means that when the driver agents are competing for a limited amount of parking spots, the price they need to paid is slightly higher. In fact, since there is more options for the driver to choose the parking spot, the driver prefers the cheapest one (i.e. the selection function tries to minimize to price to pay), with the spot agents needing to reduce the proposal prices to remain competitive.

The price values for the CNP and English auction strategies seem to be dependent only from the number of the spot agents, while in the case of the Dutch auction, the values are dependent of the number of drivers and spot agents. The English auction reached the lowest prices from the three tested strategies. The price values reached for the CNP are approximately 2% worst, being similar for scenarios with a high number of parking spots. From the three negotiation protocols, the Dutch auction is clearly the one that presents the worst results.

5.2 Analysis of the Distance to the Desired Parking Place

The results of the distance of the assigned parking spot to the desired parking place for the three negotiation protocols are illustrated in Fig. 6. The observation of these results shows a quite similar behaviour for the three strategies. This distance is mainly dependent of the variation of the number of the parking spots, being higher as higher is the number of parking spots. On the other hand, the distance almost does not change with the variation of the number of drivers in the system.

Fig. 6.
figure 6

Results of the distance to the desired parking place for the three negotiation protocols.

Full size image

The correlation between the number of parking spots and the distance values is quite surprising, but occurs because with more options to park the car, the probability to park far from the desired parking spot is higher (note that the decision function tries to minimize the price to be paid by the driver). However, if the decision function used in the negotiation strategy considers not the minimization of the price but instead the distance, the results are completely different, being less dependent of the number of drivers and parking spots, as well as are smaller for a higher number of parking spots, as illustrated in Fig. 7 for the CNP strategy.

Fig. 7.
figure 7

Results for the CNP negotiation strategy considering the minimization of the price or the minimization of the distance.

Full size image

5.3 Analysis of Operating Parameters

In addition to the analysis of the price and distance parameters, the average of some other parameters is also performed in this section, namely the amount of messages exchanged in each negotiation strategy, the difference between the highest and the lowest agreed prices and how long lasted the negotiation. The achieved results are summarized in Table 1, which also includes the average values for the distance between the desired parking place and the assigned parking spot and the price paid by the driver for the parking spot.

Table 1. Results related to the negotiation process for the three negotiation strategies.
Full size table

As observed, the number of exchanged messages between the agents during a negotiation process was significantly different between the CNP protocol and the English and the Dutch strategies, in favour of CNP. In fact, the number of exchanged messages in the CNP strategy is approximately only 17% of the number presented by the English auction and 43% of the value presented by the Dutch auction. Consequently, the CNP strategy presents the lowest average time to obtain a parking spot, as initially expected. Surprisingly, the number of exchanged messages in the Dutch auction is significantly lower than in the English auction, which occurs since the convergence point is much closer to the initial price value established by the Dutch strategy than in the English strategy (note that the starting point in the Dutch auction is 10, in the English auction is 100, and the convergence value is 14, as illustrated in Table 1).

In spite of presenting the lowest average price, the English auction has the highest difference between agreed prices (i.e. between the highest and lowest price for the several experimental scenarios), being the CNP the most deterministic negotiation strategy.

Summarizing, the English auction reached the best results regarding the agreed prices, but in opposite requires more resources to reach a solution for the negotiation process, expressed in the highest number of the exchanged messages and the requested time to conclude the negotiation. The option for one negotiation strategy may be dependent of the requirements, but the capability to conclude the negotiation faster can be in favour of the CNP strategy, since the difference in terms of price paid by the drivers is very reduced.

6 Conclusions and Future Work

This paper aims to analyze several negotiation strategies for consensus problems in smart parking systems, since the negotiation assumes a crucial issue in such distributed systems. For this purpose, the CNP, the English auction and the Dutch auction strategies were implemented using the JADE framework under the agent-based smart parking system, tested according to different scenarios and evaluated taking into consideration, among others, the level of satisfaction of the actors in the system, the scalability and the negotiation time.

The achieved results show that the Dutch auction strategy presents the worst results, the English auction reached the best results regarding the agreed prices, even with a slightly difference to the others, and the CNP requires much less resources to reach a solution for the negotiation process, expressed in the lowest number of the exchanged messages and the time to conclude the negotiation. In this way, it seems that the CNP protocol is the most suitable strategy to implement the negotiation process in smart parking systems, since it is able to conclude the negotiation faster and the difference in terms of price paid by the drivers is very reduced to the best one.

The future work will be devoted to testing the three negotiation strategies for the agent-based parking system designed by using the holonic principles, e.g., considering holarchies of drivers or spots, which may influence the performance of the negotiation process. Furthermore, comparisons should be made between this work and others approaches, like other branches of this work, which may reveals differents best approaches for differents scenarios. Also, the analysis of a 24 h parking scenario should be considered, discarding the initial results and running the systems for a longer period of time.