Mira Bou Farah

David Mercier
email: david.mercier@univ-artois.fr

Éric Lefèvre

François Delmotte

A high-level application using belief functions for exchanging and managing uncertain events on the road in vehicular ad-hoc networks

Keywords: Vehicular Ad-hoc Networks (VANET), Events on the road, Imperfect information exchange, Belief functions, Information fusion

This article introduces a high-level system using belief functions for exchanging and managing imperfect information about events on the road in vehicular ad-hoc networks. The main purpose of this application is to provide the most reliable information for the driver from multiple messages received informing the driver about events on the roads. This system and some variants are tested using a Matlab simulator. An implementation with Android smartphones using a Bluetooth technology to exchange the messages is also introduced.

Introduction

Cars are nowadays by far the most common means of transport. But this popularity leads to safety and environmental problems. Research is conducted in parallel in Europe [START_REF]European CAR 2 CAR Communication Consortium[END_REF][START_REF] Morsink | Development of a cooperative ADAS based on vehicle-to-vehicle communication[END_REF][START_REF] Reichardt | CarTALK 2000: safe and comfortable driving based upon inter-vehicle-communication[END_REF], in the USA [26] and in Japan [START_REF]ITS in Japan[END_REF] to develop Intelligent Transportation Systems (ITS) and to improve safety and driver comfort by in particular looking for the reduction of the number of undesirable events on the roads such as accidents and traffic jams.

Ad-hoc networks are wireless networks capable of organizing themselves without any infrastructure. Instead of communicating through a centralized access point, they are composed of wireless nodes communicating with each other to exchange information. In a mobility context, they are called MANET (Mobile Ad hoc Networks) [START_REF] Corson | Mobile ad hoc networking (MANET): routing protocol performance issues and evaluation considerations[END_REF][START_REF] Hong | Scalable routing protocols for mobile ad hoc networks xiaoyan[END_REF][START_REF] Royer | A review of current routing protocols for ad hoc mobile wireless networks[END_REF][START_REF] Boukerche | Performance comparison and analysis of ad hoc routing algorithms[END_REF].

Vehicular Ad-hoc Networks (VANET) are MANET networks applied to Inter-Vehicle Communication (IVC) where nodes are highly dynamic. Two main modes of communication are known in IVC: Vehicle to Infrastructure (V2I) and Vehicle to Vehicle (V2V). A V2V communication example is given by the VESPA system (Vehicular Event Sharing with a mobile P2P Architecture) [START_REF] Cenerario | Dissemination of information in inter-vehicle ad hoc networks[END_REF][START_REF] Defude | Data aggregation in VANETs: the VESPA approach[END_REF][START_REF] Delot | Estimating the relevance of information in inter-vehicle ad hoc networks[END_REF] which allows vehicles to share different types of information such as accidents or emergency brakings. It guides in particular drivers to find a parking place or to get traffic information. Another example is given by TrafficView [START_REF] Nadeem | TrafficView: Traffic data dissemination using car-to-car communication[END_REF] a road data dissemination system using V2V communication, allowing continuous exchange of position and speed information between vehicles to inform drivers about road situation (traffic, weather, quickest way, . . .).

One important component of V2V communication concerns the data transmission protocol, and currently no universal standard has emerged [START_REF] Delgrossi | Vehicle Safety Communications: Protocols, Security, and Privacy[END_REF]. Communications can be realized using DSRC (Dedicated Short-Range Communications), Wi-Fi (ad-hoc), Bluetooth, 3G or 4G cellular networks, SDARS (Satellite Digital Audio Radio Service), etc.

The present work concerns V2V communications, where information is decentralized and vehicles build their own information. It is focused on the high-level aspect of merging and organizing the messages received by a vehicle. To demonstrate the applicability of the proposed approach to real systems, a simple Bluetooth system is also developed and tested on-line. Extensions of this approach with other technologies, such as with Wi-Fi devices for instance, is beyond the scope of this paper.

In vehicular networks, the environment is very dynamic. Events on the road appears and disappears over time. Vehicles receive a large amount of information often uncertain, redundant or outdated. Then to manage the exchanges of such imperfect information between vehicles, a method is proposed in this article using the belief functions theory [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF][START_REF] Smets | The Transferable Belief Model[END_REF], belief functions constituting a rich and flexible framework to handle imprecise and uncertain information [START_REF] Delmotte | Target identification based on the transferable belief model interpretation of Dempster-Shafer model[END_REF][START_REF] Ristic | Belief function theory on the continuous space with an application to model based classification, International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems[END_REF].

Early work integrating belief functions has already been developed by Cherfaoui et al. in [START_REF] Cherfaoui | Distributed data fusion: application to confidence management in vehicular networks[END_REF]. It has been extended in [START_REF] Farah | Towards a robust exchange of imperfect information in inter-vehicle ad-hoc networks using belief functions[END_REF] where the authors propose a first model able to manage different events on the same segment of road, and a simple strategy for sending messages is exposed. Each vehicle can either send new messages created by the driver regarding events on the road or transfer messages received from other vehicles, each vehicle building its own map of the current situation without delivering to other vehicles its results of combination or deductions.

In this article, this previous model is deeply extended and tested using a Matlab simulator. A new mechanism to model the aging of a message is considered and compared with the first approach which is based on a discounting process considering that the information contained in a message decreases in reliability over time. The new one interprets the aging of a message as a reinforcement in the fact that the event has disappeared as do all events over time. Two strategies for sending messages are also studied: a first one where all messages are kept in vehicles data bases and all messages are exchanged, and a second approach aiming at saving bandwidth and spacing where only one merged message by event is retained in each vehicle. At last, an implementation of this model is realized using Android smartphones and Bluetooth connections to illustrate a simple concrete case of use and to demonstrate that smartphones can manage belief functions calculations.

This article is organized as follows. Basic concepts on belief functions are recalled in Section 2. A credal model for representing and managing imperfect information about events on the road is exposed in Section 3. It is simulated and tested in Section 4. Then, an example of implementation with Android smartphone application using Bluetooth transmissions is presented in Section 5. Finally, Section 6 concludes this paper and gives prospects.

Belief Functions: Basic Concepts

In this article, belief functions are handled with Smets' semantic approach: the Transferable Belief Model (TBM) [START_REF] Smets | The Transferable Belief Model[END_REF][START_REF] Smets | The Transferable Belief Model for quantified belief representation, handbook of defeasible reasoning and uncertainty management systems[END_REF], where belief functions are interpreted as weighted opinions with no underlying probabilistic measure.

Two levels are distinguished in the TBM:

the credal level, where available pieces of information are represented by belief functions, and manipulated; the pignistic or decision level, where belief functions are transformed into probability measures when a decision has to be made, and the expected utility is maximized.

Representing Information

Let us consider Ω = {ω 1 , ω 2 , ..., ω k }, called frame of discernment, a finite set of possible answers to a given question Q of interest.

A knowledge regarding the answer to question Q can be quantified by a basic belief assignment (BBA), also called a mass function, denoted by m and defined from 2 Ω (the set of all possible subsets of Ω) to [0, 1] such that the sum of all the masses is equal to 1:

A⊆Ω m(A) = 1 . (1)
Each mass m(A), with A ⊆ Ω, represents the part of belief allocated to the fact that the true answer to question Q belongs to A. In particular m(Ω) represents the degree of ignorance of the source which has provided the information m.

Each subset A of Ω such that m(A) > 0 is called a focal element of m.

A BBA m is said to be categorical if it has only one focal element A, which means that m(A) = 1. It is then denoted by m A . In particular m Ω represents the categorical BBA such that m(Ω) = 1 which corresponds to a state of total ignorance for the agent. BBA m Ω is also called the vacuous belief function.

A mass function m having less than two focal elements including Ω is called a simple mass function and verifies:

m(A) = 1 -ω m(Ω) = ω (2)
with A ⊂ Ω and ω ∈ [0, 1]. It can be conveniently noted A ω .

Manipulating Information

Discounting operation

When receiving a piece of information m, an agent may have some doubts regarding the reliability of the source which has provided this BBA. Such a metaknowledge can be taken into account by using the discounting operation [21, page 252] defined by:

α m(A) = (1 -α) m(A), ∀A ⊂ Ω, α m(Ω) = (1 -α) m(Ω) + α , (3)
or more simply:

α m = (1 -α) m(A) + α m Ω , (4)
where α ∈ [0, 1] is called the discount rate. Coefficient β = (1 -α) represents the degree of reliability regarding the information which have been provided [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF][START_REF] Mercier | Belief functions contextual discounting and canonical decompositions[END_REF].

Reinforcement operation

On the contrary, an agent may want to reinforce a BBA which seems to be too cautious in the sense that it is not specific enough. This operation can be realized using the following correction mechanism [START_REF] Mercier | Belief function correction mechanisms[END_REF]:

ν m = (1 -ν) m(A) + ν m tr , (5)
where ν ∈ [0, 1] is called the reinforcement rate, and m tr is the mass function m totally reinforced. Transformation m tr of m corresponds to the mass function expected by the agent when m has to be fully reinforced. Different possible choices are given in [START_REF] Mercier | Belief function correction mechanisms[END_REF].

In next Section 3.5 a reinforcement process is introduced with BBA m tr chosen equal to a particular m ωi with ω i ∈ Ω, which means that according to the reinforcement rate ν the agent has some reason to believe that ω i is the true value he/she searches.

Conjunctive rule of combination

Two mass functions m 1 and m 2 obtained from distinct and reliable sources, can be combined using the conjunctive rule of combination denoted by ∩ O and defined by:

m 1 ∩ Om 2 (A) = m 1 ∩ O2 (A) = B∩C=A m 1 (B) • m 2 (C) , ∀A ⊆ Ω . (6)
With this combination, masses are transferred to focal elements intersections.

Cautious rule of combination

If mass functions m 1 and m 2 are obtained from non-distinct reliable sources, they can be combined by using the cautious rule of combination [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF], denoted by ∧ O and defined as follows:

m Ω 1 ∧ O2 = ∩ O A⊂Ω A w Ω 1 (A)∧w Ω 2 (A) , (7)
where ∧ denotes the minimum operator, and w is the conjunctive weight function [START_REF] Smets | The Canonical Decomposition of a Weighted Belief[END_REF] defined by:

w(A) = A⊂B q(B) (-1) |B|-|A|+1 , ∀A ⊂ Ω . (8)
The cautious rule of combination is commutative, associative and idempotent (which means that: m ∧ Om = m).

Making a decision

At this level, the mass function m defined on Ω and representing the available information regarding the answer to question Q, and generally resulting in practice from a fusion process, is transformed into a probability measure with the pignistic transformation [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF] defined by:

BetP Ω ({ω}) = {A⊆Ω,ω∈A} m(A) |A| (1 -m(∅)) , ∀ω ∈ Ω. (9)

A credal model for representing and managing imperfect information about events

In this section, messages format and the different parts composing the proposed credal model allowing drivers to have a more reliable view of situations on the road based on exchanged messages are exposed.

Vehicles are assumed equipped with a Global Positioning System (GPS). Locations and dates of events are assumed to be automatically generated as soon as drivers need to send messages regarding events.

Exchanged messages format

Vehicles exchange messages about events on the road, each message giving information regarding one event.

A message M is represented as a 5-tuple (S, t, d, , m) described in Table 1. Mass function representing the confidence of S regarding the fact that the event is present

Each attribute x ∈ {S, t, d, , m} of a message M will be denoted by M.x:

-M.S designates the source of information which have perceived the event.

It is not necessarily the source which have transferred the message M . -M.t indicates the type t of the event reported by message M . Different types of events can be considered such as accident, parking place, trafficjam, fog blanket, animals on the road, etc. -M.d points out the date when M.S has created the message to inform about its presence. It is generally not the date at which message M has been received. -M. indicates the location of the event reported by message M .

-At last, M.m denotes the mass function m, held by vehicle source S, which is defined on the frame of discernment Ω = {∃, ∃} where:

-∃ stands for "the event, which is of type t, is present at time d at location ." and ∃ means "the event, which is of type t, is not present at time d at location ."

Sending process

Each vehicle manages an inner database composed of the messages it has either received or created. All the messages M j i concerning an event j are regrouped into a table denoted by M j .

Each time a vehicle can exchange messages with another vehicle, all the messages present in its database are exchanged.

Reception process

The reception of a message by a vehicle is realized sequentially by the procedure illustrated in Figure 1.

received message already received? update? known event?

initial inner database

M 1 M 1 1 M 1 2 . . . M 2 M 2 1 M 2 2 . . . . . . . . . M j . . . . . . . . . ← M j i M r . . . M j M j 1 M j 2 . . . . . . M r M 1 M 1 1 M 1 2 . . . M 2 M 2 1 M 2 2 . . . . . . M n M r M r non non oui M r.d≤M j i .d oui M r.d>M j i .d oui non
Fig. 1 Messages reception process.

Case of a message already received If the received message has been already received, it is ignored. Otherwise the message goes to the next test.

Case of an update

The same source may send a message and then send an update of this message, which means that it sends a new message corresponding to the same event to correct the information previously sent. Such an update example is illustrated in Figure 2, the date d 2 of the updated message is more recent than d 1 , locations 1 and 2 of the messages are neighbouring, mass functions m 1 and m 2 may be different or not.

Vehicule V 1 Vehicule V 2 a message M (V 1 , t, d 1 , 1 , m 1 ) an update of M (V 1 , t, d 2 , 2 , m 2 )
Fig. 2 Illustration of a message update example.

To determine an update, a threshold, denoted λ t and depending on the type t of the event, is used. It corresponds to the maximum value for a difference of location to consider that a message can be an update of another.

More precisely, the system will consider that a message M 1 is an update of a message M 2 if:

-M 1 .S = M 2 .S; -and ∆(M 1 . , M 2 . ) < λ t with ∆ a distance; -and M 1 .d > M 2 .d.
If a message present in the database is an update of the received message, the latter is ignored. If the received message is an update of a message present in the database, then it replaces it. Otherwise the message goes to the next test.

Grouping messages corresponding to the same event The received message has not been already received and is not an update of a message present in the database, it remains to look for the table M j in which to put it, in other words to look for which events j it corresponds to.

Let M be the set of all the messages M j i corresponding to an event j of the same type of the event associated with the received message M r and which is close in location, which means that M is composed of all the messages M j i verifying: M r.t = M j i .t and ∆(M r. , M j i . ) < λ t with ∆ a distance measure. If M contains at least one message, the received message M r is inserted into the same table of the message M j i present in M which is the nearest in location.

If M is empty, a new event j is created, its table M j containing only one message which is the received message M r.

Messages obsolescence

Over time, all messages stored in tables are not necessarily useful: some of them become obsolete. Then messages having a perception date too old are deleted.

The deletion is realized using a threshold, denoted Del t depending on the type t of the event.

So, in parallel with the other processes, each message M j i such that:

∆(now, M j i .d) > Del t , (10)
with ∆ a distance measure, is suppressed.

Data Fusion: giving an overview of the situation to the driver

From the database composed of the tables M j , themselves composed of messages M j i corresponding to a same event j, an overview of the existing events with their probabilities can be given to the driver, in the following manner:

-First, each mass function M j i .m is corrected with a correction rate equal to

∆(now,M j i .d) Delt
to take into account the aging of the message. The older the message, the more corrected it is. Two correction mechanisms can be used: the discounting operation (cf Equation (4)):

α j i M j i .m = (1-α j i ) M j i .m+ α j i m Ω
, where the correction rate α j i =

∆(now,M j i .d) Delt corresponds to a discounting rate. With this operation, over time α j i M j i .m tends to the total ignorance m Ω .

the reinforcement process (cf Equation ( 5)):

ν j i M j i .m = (1-ν j i ) M j i .m+ ν j i m ∃
, where the correction rate

ν j i = ∆(now,M j i .d) Delt
is a reinforcement rate. With this operation, over time ν j i M j i .m tends to m ∃ meaning that event j has disappeared. Let us recall that in both cases, messages are discarded as soon as ∆(now, M j i .d) > Del t (cf Equation ( 10)).

-Then, for each event j, corrected mass functions ( α j i M j i .m or ν j i M j i .m) are conjunctively combined using Equation ( 6).

-At last, pignistic probabilities regarding each event presence are obtained using Equation ( 9). These two methods are tested and compared in Section 4.3.1.

An overview of the whole proposed system is given in Figure 3.

Variant: exchanging and keeping only the fusion results in databases

In this section, a variant of the first method is presented to save bandwidth and limit the number of messages stored in databases. In this second model, only the fusion results are kept in databases and exchanged between vehicles.

Only the changes between these two models are exposed in the sequel.

Messages and databases

Each vehicle database contains only one message associated with each event.

A message M j associated with event j is a 5-tuple (S, t, d, , m) where:

-M j .S is the set of sources which have contributed to messages creation concerning the event j; -M j .t is the type of the event j; -M j .d is the date and time of the most recent message concerning the event j; -M j . is the set of locations of the event j; -M j .m is the mass function representing the confidence of sources M j .S regarding the fact that the event is present.

When possible, vehicles exchange their messages, each one being viewed as a synthesis of the information related to an event on the road.

Reception and fusion process

A received message M r concerning an event j already identified in the vehicle database (they are of the same type and close in location) is fused with message M j as follows:

-The new set of sources is equal to M j .S ∪ M r.S; -The date of M j becomes the most recent date among M j .d and M r.d; -The new mass function of M j is obtained as follows:

-The mass function of the message having the oldest date among M j and M r is corrected to take into consideration its aging (correction rate being equal to |∆(M r.d,M j .d)|

Delt

).

-If M r.S ∩ M j .S = ∅ (before adding M r.S to M j .S), the new mass function of M j is obtained from the conjunctive rule of combination Equation ( 6) of the corrected mass functions of M j .m and M r.m. -Otherwise, the cautious rule, Equation [START_REF] Delgrossi | Vehicle Safety Communications: Protocols, Security, and Privacy[END_REF], is used to combine these two corrected mass functions.

If the event j is not already identified in the vehicle database, message M j is created with the attributes of M r: M j .S = {M r.S}, M j .t = M r.t, M j .d = M r.d, M j . = M r. and M j .m = M r.m.

A comparison of the model keeping all the messages and the second model keeping only the fused messages is realized in Section 4.3.2 with both discounting and reinforcement correction operations.

Experimental tests using Matlab simulations

Simulator

In order to test and compare the proposed methods, a simulator has been developed in Matlab such that different scenarios can be tested.

A scenario is built with the following components:

-A scenario time axis τ with start and end dates, and a sampling period ∆τ . -Type, location, start and end dates of each real event on the map.

-Attributes related to vehicles given by: -V : the number of vehicles.

-N etRange: the network range in meter allowing V2V communication.

-Speed: the average vehicle speed in km/h when no event is present on the road. -SDRate t : the slow-down rate, depending on event type, used to compute new vehicle speed when an event exists at its location at τ moment. In this case, new vehicle speed is equal to (1

-SDRate t ) • V it in km/h from τ to τ + 1.
-The following attributes to obtain the path of each vehicle:

• τ d : the moment τ of vehicle departure;

• d : the departure vehicle location;

• a : the arrival vehicle location.

At each τ moment, the following actions are realized:

each vehicle creates a message when an event is perceived; each vehicle denies an event present in vehicle database if the driver does not perceive it; each vehicle communicates its messages to neighboring vehicles in the network range N etRange.

Performance measure: Adequacy to the reality

The common purpose of the proposed models is to provide the most reliable information for the drivers. Thus performance rates of models are measured for each type t of event and for each vehicle v by the adequacy to the reality of the information given to the driver. Formally, at each time step τ , the set equal to the union of the events j present in the vehicle database and the existing events in the reality is considered and denoted by J v,τ t , and performance rates are computed for each type t of event and for each vehicle v at each time τ by:

P erf v,τ t = 1 - j∈J v,τ t BetP v,τ j ({∃}) -R τ j 2 | J τ,v t | , (11) where:
-R τ j = 1 if event j is present at time τ , 0 otherwise. -| J v,τ t |: number of events of type t present in vehicle v database or existing in the reality at time τ .

-BetP v,τ j : pignistic probability of vehicle v at time τ concerning the presence of the event j. If no message corresponding to event j is present in vehicle v database then Betp v,τ j ({∃}) = 0.

Experimentations

The methods exposed in Section 3 are tested and compared through different scenarios.

In all the scenarios exposed here, an accident starts at the beginning of the simulation and lasts 60 minutes, which means that it is present from τ = 0 to τ = 900 (∆τ = 4s).

The confidence of all created messages is equal to 0.6: the mass function of the messages created is either m({∃}) = 0.6, m(Ω) = 0.4 when vehicle confirms an event or m({ ∃}) = 0.6, m(Ω) = 0.4 when vehicle denies an event.

Comparing messages aging mechanisms: discounting and reinforcement

Two scenarios are presented to compare aging mechanisms using the method where all messages are kept in vehicles databases.

Scenario n o 1 In the first scenario, a vehicle v receives a message indicating the presence of the accident few minutes after its beginning. After a delay of Del t equal to 100 minutes, the message is suppressed from the vehicle database being considered as obsolete.

In the following, in each figure illustrating the adequacy to the reality of a vehicle, the messages added to the vehicle database or suppressed from the vehicle database are illustrated by the following symbols just above the time τ where they occur:

-+n[∃] which means that n new messages confirming the event are added to vehicle database; -+n[¬∃] which means that n new messages denying the event are added to vehicle database; --n[∃] which means that n messages confirming the event are deleted from vehicle database; --n[¬∃] which means that n messages denying the event are deleted from vehicle database.

A grey vertical line indicates the disappearance of the event.

Figure 4 illustrates the adequacy to the reality of vehicle v during this first scenario.

The discounting mechanism tends to the total ignorance while the reinforcement process tends to the negation of the event. Therefore, the discounting mechanism gives a better result (a better adequacy to the reality) while the accident has not disappeared (the accident disappearing after the grey vertical line). On the contrary, the reinforcement process which anticipates the disappearance provides better results after the disappearance.

Scenario n o 2 In this scenario, a vehicle v receives two messages confirming the accident, and two other messages denying the accident 10 minutes and 30 minutes after its disappearance. The adequacy to the reality of vehicle v is illustrated in Figure 5.

This scenario shows that after receiving messages denying the accident (from τ > 1050, 10 minutes and 30 minutes after the accident disappearance), adequacy tends quickly to 100% with the reinforcement process while it is not the case with the discounting process. Indeed the discounting process tends to transfer the masses to the ignorance giving a 50% bet for the existence and 50% to the non-existence of the event.

Comparing methods: keep all messages, keep fusion results or keep yes/no last message

Two scenarios are presented to compare the method keeping all the messages (first method) and the second method described in Section 3.6 which conserves and exchanges only the fused messages. Each method are tested using the discounting or the reinforcement process for messages agings.

Scenario n o 3 Three vehicles v1, v2 and v3 are considered in addition to a vehicle v.

This scenario proceeds as follows:

a vehicle v1 creates a message M 1 confirming the accident; vehicle v1 shares its message with vehicles v2 and v3; vehicle v2 creates a message M 2 confirming the accident; vehicle v2 shares its database with v; vehicle v3 creates a message M 3 confirming the accident; vehicle v3 shares its database with v.

The database of the vehicle v depends on the method used:

with the method where all messages are kept in vehicle database: vehicle v database contains M 1 and M 2, then M 1, M 2 and M 3; with the method where only a synthesis message is kept in vehicle database: vehicle v database contains the fusion result message received from v2 (fusion of M 1 and M 2), then at the reception of the fusion result contained in v3 (fusion of M 1 and M 3), v applies an aging mechanism to both fusion results and combine them using the cautious rule of combination and keep in its database only the final fusion result.

The adequacy to the reality of the vehicle v is illustrated in Figure 6.

The method where vehicle keeps all messages in its database gives better results: before accident disappearance, the discounting mechanism gives the best result; then, the reinforcement mechanism gives the best result. This is due to the following reasons:

the result of the conjunctive combination is higher than (or equal to) the result of the cautious conjunctive combination; discounting or reinforcing messages before combining them gives a higher result than combining messages before applying an aging mechanism. Scenario n o 4 In this scenario, previous methods are also compared with a very simple method called y/n last mess for short, where vehicles communicate simple messages telling yes or no an event exists; for each event, they keep in their databases only the last message. As all the drivers tell the truth (all the messages carry a true information), the last message is always the most recent true information.

In this scenario, a vehicle receives from distinct sources two messages confirming the accident, and two messages denying it after its disappearance.

Adequacy to the reality of the vehicle for each method is illustrated in Figure 7.

This scenario shows that after receiving messages denying the accident, the method where all messages are kept in vehicle database is still the best method when using reinforcement mechanism.

The result of the trivial method y/n last mess shows that this method does not allow predicting the accident disappearance, and gives a bad result after accident disappearance until the reception of a first message denying the event. It means that even in an ideal not-very-real situation where drivers tell always the truth and messages are always received, a simple solution is not so evident.

An example of implementation with Android smartphones using Bluetooth transmissions

The purpose of this section is to illustrate how the first model presented in Section 3 can be implemented in Android smartphones with Bluetooth connections to illustrate a simple concrete case of use and to demonstrate that smartphones can manage belief functions calculations.

The choice of the Bluetooth technology is purely a matter of programming convenience. Data appearing in the following figures have been obtained on foot. Indeed no real tests were possible by car (or only at very slow speed) due to the fact that, with the Bluetooth version used by the authors, connection times were too long to allow smartphones to exchange data with cars passing on opposite sides on the road. As pointed out in the introduction of the article, the choice of the transmission technology is out of the scope of this article, the work presented here only concerns the application layer.

The following paragraphs detail both functional and technical aspects in relation with the implementation of the application and its possible services.

Application User Interfaces

As illustrated in Figure 3, the driver represents the unique actor of the system. He/She might play both sender and receiver roles, messages being periodically propagated "broadcasted " to the drivers within neighborhood coverage.

Application User Interfaces are based on four main screens:

-Dashboard (Figure 8): summarizes the description of the current vehicle environment. It lists a set of events sorted by their distance to the vehicle (Figure 8(a)). In addition to the event type, each list element shows the distance which is the average of the distances of the messages composing this event, the orientation of the event which is also the average of messages orientations and its pignistic probability which is the result of the aggregation of all the messages describing the event (cf Section 3.5). The time displayed near an event is the age of the most recent message in the list of messages constituting this event. For example, from Figure 8(a), there is a traffic jam in front of the vehicle at about 113 meters with a probability .98, and the most recent message concerning this event was received 1mn and 41s ago. The dashboard event list is periodically updated, taking into account time, new location, and received messages. Besides, the user have the possibility to launch the update manually. A detailed event view is also available. For each event, the set of belonging messages is made accessible by a simple selection of an event from dashboard. For example, a pressure on the first event "Traffic jam" on the dashboard illustrated in Figure 8(a), gives the result illustrated in Figure 8(b) where messages corresponding to this event can be observed. For each message, the distance between the vehicle and the event, the age of the message and the value of the mass function are given. Each driver gives a simple mass function, then only masses on "yes, the event is present on the road at this time at my position" or "no it does not exist at this time at my position" are given (the complementary to one being given to Ω). -New event: accessible via the menu interface (Figure 9), the new event interface (Figure 10(a)) affords to drivers the possibility to point out and report a new message describing an event. Drivers choose first the type of the event, then the purpose of the message: "yes, the event is present on the road at this time at my position" or "no it does not exist at this time at my position", and finally their degree of belief (in yes or no, the com- Messages classification is based on the event type and proximity indicators like location and time. The accuracy of information stream exchanged throughout messages are assessed, aggregated and merged according to their respective mass. For example, if and event is described by two messages, the respective -Listening: the associated thread listen and waits for incoming connection.

Once the connection is established, the current state changes to receive state. -Receive: after state switching, a socket is created and the input stream is redirected. Then, binary data is read until the end of the stream. Binary data is converted to object messages. Next they are added to database.

-Send: Send state is used to propagate messages to neighboring smart phones. All non obsolete messages are sent to the connected devices.

Conclusion and future work

In this article, two models based on belief functions with two different message aging systems have been presented to manage uncertain messages informing drivers about events on the road in vehicular networks. A Matlab simulator has been developed to test them, and an implementation using Android smartphones have also been exposed to illustrate the feasibility of a concrete realization of these models. One way to improve the method consists in trying to determine the age of an event from the series of messages related to it. It has indeed been observed that ideally messages created at the end of an event or after its disappearance should be reinforced towards the non existence of the event while messages confirming an event and created before its end should be kept. The knowledge of the beginning and the end of an event may significantly improve the results.

Another improvement concerns the spatial aspect of an event. In the models presented in this article an event takes place at a location which is sufficient for an accident but maybe not for a traffic jam which may spread to a large area. Likewise an accident can cause a traffic jam so the relations between types of events may also been considered.

Fig. 3

 3 Fig.3General flowchart of the model. The internal system manages new messages, repeats messages which have still an interest, deletes useless one, and offers an overview at driver's request.

  (a) with a discounting correction (b) with a reinforcement correction (c) Discounting and reinforcement corrections on the same figure

Fig. 4

 4 Fig. 4 Adequacy to the reality of the information given to the driver with the first model (keeping all the messages) during scenario n o 1. Symbol +[∃] indicates the date of the arriving of a message which mentions the accident existence. Symbol -[∃] indicates the deletion of the message mentioning the existence of the accident. The grey vertical line corresponds to the disappearance of the accident. Accident starts at τ = 0.

Fig. 5

 5 Fig. 5 Adequacy to the reality of the information given to the driver with the first model (keeping all the messages) during scenario n o 2.

Fig. 6

 6 Fig. 6 Adequacy to the reality of the information contained in vehicle v for each method during scenario n o 3

Fig. 7

 7 Fig. 7 Adequacy to the reality of each method: Scenario n o 4

Fig. 8

 8 Fig. 8 Application dashboard.

Fig. 9

 9 Fig. 9 Application menu

( a )Fig. 10

 a10 Fig. 10 Other user interfaces

Fig. 11

 11 Fig. 11 Main application entities

Table 1

 1 Messages format Date and Time when S has detected the event Location where S has detected the event m

	Attribute Description
	S	Source which has perceived the event
	t	Type of the event
	d

Acknowledgements This work has been financed by the French region Nord-Pas de Calais under the project CISIT (Campus International pour la Sécurité et l'Intermodalité des Transports).

The authors are very grateful to the VESPA team, in particular Thierry Delot and Sylvain Lecomte from LAMIH Laboratory, Univ. of Valenciennes, for having helped them in their developments.

The authors would like to thank the anonymous reviewers for their valuable comments which have helped them to improve the clarity and the quality of this article.


Amel Ennaceur
email: amelnaceur@yahoo.fr

Zied Elouedi
email: zied.elouedi@gmx.fr

Eric Lefevre
email: eric.lefevre@univ-artois.fr

Multi-Criteria Decision Making Method with Belief Preference Relations

Keywords: Multi-criteria decision making, belief function theory, Belief pair-wise comparison, Uncertain preferences

In modeling Multi-Criteria Decision Making (MCDM) problem, we usually assume that the decision maker is able to elicitate his preferences with precision and without difficulty. However, in many situations, the expert is unable to provide his assessment with certainty or he is unwilling to quantify his preferences. To deal with such situations, a new MCDM model under uncertainty is introduced. In fact, we focus here on the problem of modeling expert opinions despite the presence of incompleteness and uncertainty in their preference assessments. Besides, our proposed solution suggests to model these preferences qualitatively rather than exact numbers. Therefore, we propose to incorporate belief preference relations into a MCDM method. The expert assessments are then formulated as a belief function problem since this theory is considered as a useful tool to model expert judgments.

Introduction

The Analytic Hierarchy Process (AHP) method 7 8 is amongst one of the most well known multi-criteria decision making (MCDM) methods and has been successfully applied to many practical problems. 6 29 Though its popularity and efficiency, this method is often criticized for its use of an unbalanced scale of estimations and its inability to adequately handle the uncertainty and imprecision associated with the mapping of the decision maker's perception to a crisp number. 1 2 Besides, in MCDM process, an expert may be uncertain about his level of preference due to incomplete information or knowledge, inherent complexity and uncertainty within the decision environment. Thus, in some cases, the decision maker cannot estimate his assessment with a numerical value. 1 To overcome these difficulties, several MCDM methods are combined within uncertain theories. In particular, the AHP is extended to a more realistic elicitation procedure. One of these extensions is the Fuzzy AHP appeared in [START_REF] Van Laarhoven | A fuzzy extension of Saaty's priority theory[END_REF] , which utilized triangular fuzzy numbers to model the pair-wise comparisons. Since then, several fuzzy AHP developments have been proposed. [START_REF] Lootsma | Fuzzy Logic for planning and Decision-Making[END_REF] Besides, probabilistic AHP methods are introduced in [START_REF] Basak | Probabilistic judgments specified partially in the Analytic Hierarchy Process[END_REF] , handling pairwise comparisons matrices based on probability theory, where each element of which is the prior probability. There are also other ways to solve AHP problems, such as referenced AHP. [START_REF] Schoner | Ambiguous criteria weights in AHP: consequences and solutions[END_REF] In particular in the belief function framework, Beynon et al. have proposed a method called the DS/AHP method [START_REF] Beynon | The Dempster-Shafer theory of evidence: An alternative approach to multicriteria decision modelling[END_REF] comparing not only singleton alternatives but also groups of alternatives. Besides, several works has been proposed by Utkin. 18 19 He has proposed a method for ranking of alternatives in the frameworks of AHP approach and belief function theory. The main feature of this approach is that it allows the expert to deal with comparisons of arbitrary subsets of alternatives and criteria. [START_REF] Utkin | The DS/AHP Method under Partial Information about Criteria and Alternatives By Several Levels of Criteria[END_REF] Additionally, Smarandache et al. [START_REF] Dezert | Multi-Criteria Decision Making based on DSmT-AHP[END_REF] have developed the DSmT/AHP which is based on the Dezert-Smarandache theory. [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion (Collected works)[END_REF] This method aimed at performing a similar purpose as DS/AHP that is to compare groups of alternatives. Besides, Ennaceur et al. [START_REF] Ennaceur | Handling Partial Preferences in the Belief AHP Method: Application to Life Cycle Assessment[END_REF] have proposed the belief AHP approach that compares groups of criteria to subsets of alternatives. Then, they model the causality relationship between these groups of alternatives and criteria. [START_REF] Ennaceur | Reasoning under uncertainty in the AHP method using the belief function theory[END_REF] With regard to these proposed methods, we can frequently find limits. Firstly, in some cases, the decision maker might be unwilling to provide all comparisons necessary to construct full comparison matrices. In addition, these approaches deal only with numerical values to translate the expert preferences into quantitative information.

To solve the problems presented above, and to facilitate the pair-wise comparison process, a new MCDM method under uncertainty is proposed that eliminates some of the drawbacks of the existing prioritization methods. The main objective of this paper is then to develop a new approach to tackle uncertainty and imprecision within the pair-wise comparison process, in particular, when the decision maker's judgments are represented as a qualitative assessment. A natural way to cope with uncertain judgments is to express the comparison ratios as a belief function, which incorporates the imperfection of the human thinking. Indeed, preferential assessments are used in order to express the decision maker's subjective assessments instead of using numerical values. With our method, the expert uses only preference relations. He does not require to complete all the comparison matrices, he can then derive priorities from incomplete set of judgments. Therefore, a new procedure is employed to derive crisp priorities from qualitative judgments, corresponding to each level.

In what follows, we first present some definitions needed for belief function context. Next, we describe some existing methods for constructing belief function from preference relations. Section 4 details our new MCDM method based on preferential assessment, and gives an example to show its application. Finally, section 5 concludes the paper.

Belief function theory

The belief function theory is appropriate to handle uncertainty in MCDM problems especially within approaches based on expert assessments. So, in this section, we briefly review the main concepts underlying the belief function theory as interpreted by the Transferable Belief Model (TBM). The latter is a useful model to represent quantified belief functions. Details can be found in. 3 17

Basic concepts

Let Θ be the frame of discernment representing a finite set of elementary hypotheses related to a problem domain. We denote by 2 Θ the set of all the subsets of Θ. [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] The impact of a piece of evidence on the different subsets of the frame of discernment Θ is represented by the so-called basic belief assignment (bba), called initially by Shafer, basic probability assignment:

3 A⊆Θ m(A) = 1. (1)
The value m(A), named a basic belief mass (bbm), represents the portion of belief committed exactly to the event A. The events having positive bbm's are called focal elements.

Let F(m) ⊆ 2 Θ be the set of focal elements of the bba m. Associated with m is the belief function is defined for A ⊆ Θ and A = ∅ as:

bel(A) = ∅ =B⊆A m(B) and bel(∅) = 0. (2)
The degree of belief bel(A) given to a subset A of the frame Θ is defined as the sum of all the basic belief masses given to subsets that support A without supporting its negation.

The plausibility function pl expresses the maximum amount of specific support that could be given to a proposition A in Θ. It measures the degree of belief committed to the propositions compatible with A. pl(A) is then obtained by summing the bbm's given to the subsets B such that

B ∩ A = ∅: 3 pl(A) = B∩A =∅ m(B), ∀A ⊆ Θ.
(3)

Combination

Handling information induced from different experts (information sources) requires an evidence gathering process in order to get the fused information. In the TBM, the basic belief assignments induced from distinct pieces of evidence can be combined using the conjunctive rule: [START_REF] Ph | The combination of evidence in the Transferable Belief Model[END_REF] (m

1 ∩ m 2 )(A) = B,C⊆Θ,B∩C=A m 1 (B)m 2 (C), ∀A ⊆ Θ. (4)
m 1 ∩ m 2 is the bba representing the combined impact of two pieces of evidence.

Decision making

The TBM considers that holding beliefs and making decision are distinct processes. Hence, it proposes a two level model:

• The credal level where beliefs are entertained and represented by belief functions.

• The pignistic level where beliefs are used to make decisions and represented by probability functions called the pignistic probabilities, denoted BetP: 4

BetP (A) = B⊆Θ |A ∩ B| |B| m(B) (1 -m(∅))
, ∀A ∈ Θ.

(5)

Uncertainty measures

In the case of the belief function framework, the bba is defined on an extension of the powerset: 2 Θ and not only on Θ. In the powerset, each element is not equivalent in terms of precision. Indeed,

θ i ⊂ Θ (i ∈ {1, 2}) is more precise than θ 1 ∪ θ 2 ⊆ Θ.
In order to try to quantify this imprecision, different uncertainty measures have been defined, such as 26 27 :

H(m) = A∈F (m) m(A) log 2 ( |A| m(A) ). (6)
The measure H is aimed at assessing the total uncertainty arising in a body of evidence due to both randomness (ignorance and inconsistency) and nonspecificity associated with a bba.

The measure of uncertainty H based on a noncomposite approach to total uncertainty, leads to a function that can be factored into the sum of Dubois and Prade's nonspecificity and an entropy-like measure associated with random sets that was previously studied by Nguyen. Under complete ignorance, H reduces to Hartley's information. [START_REF] Pal | Uncertainty measures for evidential reasoning II: A review[END_REF] Besides, when the bba concentrates only on singletons, this measure is equivalent to Shannon's probabilistic entropy. Besides, H has a unique maximum, in sharp contradistinction to the composite measures G 1 , G 2 (called global uncertainty measures [START_REF] Lamata | Measures of entropy in the theory of evidence[END_REF] ) and T (called total uncertainty 32 ). In addition, the measure H attains its global maximum when the bba distributes both randomness and nonspecificity uniformly over the largest possible set of focal elements.

Operations on the product space

In the previous subsections, we have presented the basic concepts of the belief function theory. These mechanisms are based on the assumption that bbas are defined on the same frame of discernment. However, this constraint limits the practical applications. Let us consider in what follows, a first frame Θ and a second frame Ω.

Cylindrical extension and projection

Cylindrical extension : allows to extend a set defined in low-dimensional domain into a higher-dimensional domain. Consider a subset A ⊆ Θ, the cylindrical extension of A to Θ × Ω is denoted A ↑Θ×Ω . It is obtained as:

A ↑Θ×Ω = A × Ω. (7)
Example: Let us consider Θ = {θ 1 , θ 2 }. We want to define θ 1 into the two-dimensional space Θ × Ω where Ω = {ω 1 , ω 2 }. Its cylindrical extension is computed as:

θ ↑Θ×Ω 1 = {(θ 1 , ω 1 ), (θ 1 , ω 2 )} .
Projection: is the opposite operation of cylindrical extension. It allows to reduce a set defined in a multi-dimensional domain to a set defined in a lower-dimensional domain. Let C be a subset of Θ×Ω. Projecting C on Ω, denoted C ↓Ω , means dropping extra coordinates.

It is obtained by:

C ↓Ω = {ω, ω ∈ Ω, C ∩ ω ↑Ω×Θ = ∅}. (8)
Example: Let us consider {(θ 1 , ω 1 ), (θ 2 , ω 1 )} defined on Θ × Ω. The projection of this set into Ω is equal to: {(θ 1 , ω 1 ), (θ 2 , ω 1 )} ↓Ω = ω 1 .

Vacuous Extension

This operation is useful, when the referential is changed by adding new variables. Thus, a marginal mass function m Θ defined on Θ will be expressed in the frame Θ × Ω as follows:

21 m Θ↑Θ×Ω (C) = m Θ (A) if C = A × Ω, A ⊆ Θ, 0 otherwise. ( 9
)
Example: Given the following bba defined on Θ = {θ 1 , θ 2 , θ 3 } as:

m Θ ({θ 1 }) = 0.5, m Θ ({θ 2 }) = 0.2 and m Θ ({Θ}) = 0.3. Let Ω = {ω 1 , ω 2 }.
The bba defined on Θ will be defined in a finer frame Θ×Ω using the vacuous extension as follows:

m Θ↑Θ×Ω ({(θ 1 , ω 1 ), (θ 1 , ω 2 )}) = 0.5 m Θ↑Θ×Ω ({(θ 2 , ω 1 ), (θ 2 , ω 2 )}) = 0.2 m Θ↑Θ×Ω (Θ × Ω) = 0.3

Marginalization

Given a mass distribution defined on the product space Θ × Ω, marginalization corresponds to mapping over a subset of the product space by dropping the extra coordinates. The new belief defined on Θ is obtained by [START_REF] Ph | Belief functions: the disjunctive rule of combination and the generalized bayesian theorem[END_REF] :

m Θ×Ω↓Θ (A) = {B⊆Θ×Ω|B ↓Θ =A)} m Θ×Ω (B), ∀A ⊆ Θ. (10)
B ↓Θ denotes the projection of B onto Θ.

Example: Let us consider the bba defined on Θ × Ω:

m Θ×Ω ({(θ 1 , ω 1 ), (θ 1 , ω 2 )}) = 0.5 m Θ×Ω ({(θ 2 , ω 1 ), (θ 2 , ω 2 )}) = 0.2 m Θ×Ω ({(θ 1 , ω 1 )}) = 0.3
Marginalizing m Θ×Ω on the coarser frame Θ m Θ×Ω↓Θ will lead to the following distribution:

m Θ×Ω↓Θ ({(θ 1 }) = 0.5 + 0.3 = 0.8 m Θ×Ω↓Θ ({(θ 2 }) = 0.2 2.5.4. Ballooning extension.
This operation is useful if an agent after conditioning realizes that the evidence he has considered as true was not and accordingly he would reconstruct the initial distribution. It can also be useful if beliefs are defined on a limited set and other alternatives were discovered afterwards. The agent should redistribute his beliefs to take them into account. Let m Θ [ω] represents your beliefs on Θ conditionnally on ω a subset of Ω. To get rid of conditioning, we have to compute its ballooning extension.

Conditional masses are transferred to C, the largest subset of Θ × Ω whose intersection with the vacuous extension of ω followed by a projection on Θ gives A:

(A ∩ ω ↑Θ×Ω ) ↓Θ = A. Thus, C = (A × ω ∪ Θ × ω)
where ω stands for the complement of ω.

Accordingly, the ballooning extension is defined as:

m Θ [ω] ⇑Θ×Ω (A × ω ∪ Θ × ω) = m Θ [ω](A), ∀A ⊆ Θ. (11)
Example:

Let us consider Θ = {θ 1 , θ 2 , θ 3 }, Ω = {ω 1 , ω 2 } and the conditional bba m Θ [ω 1 ](θ 1 ) = 0.6. Its corresponding basic belief mass on Θ × Ω is obtained by taking into consideration {(θ 1 , ω 1 )} and all the instances of Θ for the complement of ω 1 .

Hence,

m Θ [ω 1 ] ⇑Θ×Ω ({(θ 1 , ω 1 ), (θ 1 , ω 2 ), (θ 2 , ω 2 ), (θ 3 , ω 2 )}) = m Θ [ω 1 ](θ 1 ).

Belief function methods for generating belief function from preference relations

The problem of eliciting qualitatively expert opinions and generating basic belief assignments has been addressed by many researchers 20 23 24 25 . In this subsection, we introduce some existing methods and we provide an overview of our proposed approach.

Wong and Lingras' method

Wong and Lingras 25 proposed a method for generating belief functions from preference assessments. So, given a pair of propositions, experts may express which of the propositions is more likely to be true. Thus, they defined two binary relations preference and indifference ∼ defined on 2 Θ such as:

a b is equivalent to bel(a) > bel(b) (12) a ∼ b is equivalent to bel(a) = bel(b) (13)
where a, b ∈ 2 Θ . This approach is based on two steps. The first one consists in considering that all the propositions that appear in the preference relations are potential focal elements. However, some propositions are eliminated according to the following condition: if a ∼ b for some a ⊂ b, then a is not a focal element.

After that, the basic belief assignment is generated using the two presented Equations ( 12) and ( 13). This formulation has multiple belief functions that are consistent with the input qualitative information, and so their procedure only generates one of them.

It should be noted that Wong and Lingras' approach does not address the issue of inconsistency in the pair-wise comparisons. For example, the expert could specify the apparently inconsistent preference relationships: bel(a) > bel(b), bel(b) > bel(c), and bel(c) > bel(a).

Ben Yaghlane et al.'s method

Ben Yaghlane et al. proposed a method for generating optimized belief functions from qualitative preferences. [START_REF] Ben Yaghlane | Constructing belief functions from expert opinions[END_REF] The objective of this method is then to convert preference relations into constraints of an optimization problem whose resolution, according to some uncertainty measures (UM), allows the generation of the least informative or the most uncertain belief functions defined as follows:

a b ⇒ bel(a) -bel(b) ≥ ε (14) a ∼ b ⇒ |bel(a) -bel(b)| ≤ ε ( 15
)
where ε is considered to be the smallest gap that the expert may discern between the degrees of belief in two propositions a and b. Note that ε is a constant specified by the expert before beginning the optimization process.

Ben Yaghlane et al. proposed a method that requires that propositions be represented in terms of focal elements, and they assume that Θ (where Θ is the frame of discernment) should always be considered as a potential focal element. Then, a mono-objective technique was used to solve such constrained optimization problem:

M ax m U M (m) s.t. bel(a) -bel(b) ≥ ε bel(a) -bel(b) ≤ ε bel(a) -bel(b) ≥ -ε a∈F (m) m(a) = 1, m(a) ≥ 0, ∀a ⊆ Θ; m(∅) = 0 (16)
where the first, second and third constraints are derived from Equations ( 14) and ( 15), representing the quantitative constraints corresponding to the preference relations.

Furthermore, the proposed method addresses the problem of inconsistency. In fact, if the preference relations are consistent, then the optimization problem is feasible. Otherwise no solutions will be found. Thus, the expert may be guided to reformulate his preferences.

MCDM method based on belief preference relations

This section is dedicated to the presentation of our new MCDM under uncertainty. Indeed, we introduce the basic stages needed to ensure the ranking of alternatives in an uncertain environment based on the belief function framework. In this context, we introduce a new method inspired of the AHP approach. Our model has the same features as standard AHP such as hierarchical levels and pair-wise comparisons. At first, we will briefly describe Saaty's approach. Then, we will present the computational steps of our proposed model.

Aspects of analytic hierarchy process

The objective of this section is to introduce the main ideas behind the AHP approach, in order to better introduce our approach which is inspired of it. In fact, our method will be based primarily on hierarchical level and pair-wise comparisons.

The AHP approach is a decision-making technique developed by Saaty. 7 8 This method has the advantage of permitting a hierarchical structure of the criteria and alternatives, which provides users with a better focus on specific criteria and sub-criteria and alternatives when allocating the priorities. This step is important, because a different structure may lead to a different final ranking.

Once the hierarchy is built, the decision maker starts the prioritization procedure to determine the relative importance of the elements on each level of the hierarchy (criteria and alternatives). Elements of a problem on each level are paired (with respect to their upper level decision elements) and then compared. This method elicits preferences through pair-wise comparisons which are constructed from decision maker's answers. Indeed, the decision maker can use both objective information about the elements as well as subjective opinions about the elements relative meaning and importance. The responses to the pairwise comparison question use a nine-point scale [START_REF] Saaty | A scaling method for priorities in hierarchical structures[END_REF] , which translates the preferences of a decision maker into crisp numbers.

After filling all the pair-wise comparison matrices, the objective is then to find the weight of each criterion, or the score of each alternative by calculating the eigenvalue vector. With these values, the AHP method permits to compute a consistency ratio to check if the matrix is consistent or not. When the matrix is considered inconsistent, the entries that are given by the decision maker have to be revised until a satisfactory consistency ratio is obtained.

MCDM method using preferential assessments

A MCDM problem is defined as a set of alternatives Θ = {a 1 , . . . , a n }, a set of criteria Ω = {c 1 , . . . , c m }, a preferential assessment representing the performance of each alternative with respect to each criterion leading to the determination of a decision matrix for the alternatives, and a weighting vector representing the relative importance of the evaluation criteria with respect to the overall objective of the problem. With regard to this problem, a new MCDM method has been developed. It is inspired of standard AHP approach and the belief function framework.

Identification of the candidate alternatives and criteria

The ranking procedure starts at the determination of the criteria importance and alternative performance. As in [START_REF] Ennaceur | Handling Partial Preferences in the Belief AHP Method: Application to Life Cycle Assessment[END_REF] , let Ω = {c 1 , . . . , c m } be a set of criteria, we denote the set of all subsets of Ω by 2 Ω , and let C k be the short notation of a subset of Ω. Besides, in many complex problems decision makers are able to compare only subsets of criteria and cannot evaluate separate ones. To solve this problem, that means to reduce the number of criteria which decreases the number of comparisons, our method suggests to allow the expert to express his opinions on groups of criteria instead of single one. So, he chooses these subsets by assuming that criteria having the same degree of preference are grouped together. For instance, if an expert identifies a group of criteria, then we could suppose that all of them have the same importance. Thus, these groups of criteria can be defined as:

C k C j , ∀ k, j|C k , C j ∈ 2 Ω , C k ∩ C j = ∅ and j C j = Ω ( with C j exclusive). ( 17
)
Since we are not performing pair-wise comparisons of criteria but relating to groups of criteria, these sets should not consider a criterion in common, because if one criterion is included in two groups, then each group will give a different level of favorability.

For example, we consider a problem that involves four criteria: Ω = {Comfort (c 1 ), Style (c 2 ), Fuel (c 3 ), Quietness (c 4 )}. The expert can identify the following subsets {c 1 }, {c 4 }, and {c 2 , c 3 }. He assumed that the two criteria c 2 and c 3 have the same degree of importance. Therefore, they are grouped together.

Like the criterion level, we assume that there is a set of alternatives Θ = {a 1 , ..., a n } consisting of n elements. Denote the set of all subsets of Θ by 2 Θ , and let A k be a subset of A. At this level, our method suggests to not necessarily consider all of them but just to choose groups of those alternatives. One of the possible solutions of this task is to use the DS/AHP method. 13 14 Besides, we apply the same hypotheses assumed in DS/AHP to identify the subsets of alternatives. The decision maker compares not only a single one but also sets of alternatives between each other.

By comparing subsets of criteria and alternatives, we provide a major benefit to the expert. Our proposed approach reduces the number of comparisons, because instead of using single elements, we have used subsets. In fact, in some practical problems, it is easier for an expert to express his opinions and comparisons between subsets of criteria and not compulsory on singleton criterion. For example, for the fuel, we may get two subgroups: the first one containing both natural gas and gasoline criteria and the second one only singleton criterion which is diesel.

Pair-wise comparisons and preference elicitation

Once the sets of criteria and alternatives are defined, the expert tries to specify his preferences in order to obtain the criterion weights and the alternative performances in terms of each criterion. At this step, we propose to use the pair-wise comparison process.

Under this approach, a new elicitation procedure is introduced, since standard pairwise comparison does not handle the problem of uncertainty. Therefore, in the proposed methodology, the expert is allowed to use preference relations only. Thus to express his assessments, the decision maker has to express his opinions qualitatively, based on knowledge and experience that he provides in response to a given question rather than direct quantitative information. He only selects the related linguistic variable using preference modeling.

For instance, to determine the criteria weights, the preferences relation matrix is obtained (Table 1). (1) a preference relation iff

(c i c j ) ∧ ¬(c j c i ) (2) an indifference relation ∼ iff (c i c j ) ∧ (c j c i ) (3
) an unknown relation.

To complete the pair-wise matrix, the expert is not obliged to quantify his assessments and to fill all the pair-wise comparisons matrix. He is able to express his preferences freely.

To model the pair-wise comparison matrix, some priorities must be respected. We consider X, the pair-wise comparison matrix, is a k × k matrix in which k is the number of groups of elements (alternatives or criteria) being compared. Entries of X denote the preference relation between each pair of elements. The expert has to complete only the matrix without quantifying the diagonal and the reciprocal matrix.

Once the pair-wise comparison matrix is complete for both the criterion and the alternative levels, our objective is then to obtain the priority of each subset of element (alternatives or criteria). In fact, within our model, we propose to transform these preference relations into numerical values using the belief function theory. Besides, we try to closely imitate the expert reasoning without adding any additional information. Therefore, we suggest to apply Ben Yaghlane et al. model [START_REF] Ben Yaghlane | Constructing belief functions from expert opinions[END_REF] to convert the preference relations into constraints of an optimization problem whose resolution, according to some uncertainty measures (UM), allows the generation of the least informative or the most uncertain belief functions. It can then be determined by the resolution of an optimization problem as defined is the previous section (Equation 16).

Using the obtained pair-wise matrix, each preference relation is transformed into constraints of an optimization problem. For instance, if we use the preferences relation matrix relative to the criterion level we get:

M ax m H(m) = m({c 1 }) * log 2 (|c 1 |/m({c 1 })) + m({c 2 })log 2 (|c 2 |/m({c 2 })) +... + m({c m }) * log 2 (|c m |/m({c m })) + m(Ω) * log 2 (|Ω|/m(Ω)); s.t. bel({c 1 }) -bel({c 2 }) ≥ ε (c 1 is prefered to c 2 ) bel({c 1 }) -bel({c 2 }) ≥ -ε (c 1 is indifferent to c 2 ) bel({c 1 }) -bel({c 2 }) ≤ ε (c 1 is indifferent to c 2 ) ... ci∈F (m) m(c i ) = 1, m(A) ≥ 0, ∀A ⊆ Ω; m(∅) = 0. ( 18
)
We assume that ε = 0.01 and the uncertainty measures is H since it has a unique maximum as defined in Equation 6. In this paper the measure H is used since it takes into account the non-specificity and quantifies the conflict presented in the body of evidence (measure of total uncertainty). Among these measures, we decided to use H.

As a result, we assume that each subset is described by a basic belief assignment defined on the possible responses (m). Thus, the criterion bba is denoted by m Ω and the alternative bba by m Θ .

Furthermore, the proposed method addresses the problem of inconsistency. In fact, if the preference relations are consistent, then the optimization problem is feasible. Otherwise no solution will be found.

Updating the alternatives priorities

To update the alternatives priorities with respect to the criterion weight, we have to define a rule for combining them. On the one hand, we have bba concerning singleton and groups of criteria instead of single one. On the other hand, the sets of alternatives are compared pair-wise regarding a specific criterion. [START_REF] Ennaceur | Reasoning under uncertainty in the AHP method using the belief function theory[END_REF] Accordingly, and to more imitate the expert reasoning, we propose to represent the relationship between criteria alternative level. Unlike the criterion level, the expert tries to express his preferences over the sets of alternatives regarding each criterion and not regardless of the criteria. Besides, we indicate that to define the influences of the criteria on the evaluation of alternatives, we might use a conditional belief.

Given a pair-wise comparison matrix which compares the sets of alternatives according to a specific criterion, a conditional bba can be represented by: 28

m Θ [c j ](A k ) = w k , ∀A k ⊆ Θ and c j ∈ Ω (19)
where A k represents a subset of 2 Θ , w k is the bbm of the k th sets of alternatives regarding the criterion c j . m Θ [c j ](A k ) means that we know the belief about A k regarding c j . As indicated above, our objective through this step is to combine the obtained conditional belief with the importance of their respective criteria to measure their contribution. In this context, our major problem here is that we have priorities concerning criteria and groups of criteria that are defined on the frame of discernment Ω, whereas the sets of decision alternatives are generally defined on another frame Θ. In order to solve this problem, we propose to standardize our frame of discernment. First, at the criterion level, our objective is then to redefine the bba that represents criteria weights. Therefore, we may use the vacuous extension concept (Equation 9). [START_REF] Ph | Belief functions: the disjunctive rule of combination and the generalized bayesian theorem[END_REF] Indeed, we propose to extend this bba from Ω to Θ × Ω:

m Ω↑Θ×Ω (B) = m Ω (C i ) B = Θ × C i , C i ⊆ Ω. (20)
Second, at the alternative level, the idea was to use the deconditionalization process in order to transform the conditional belief into a new belief function. In this case, the ballooning extension concept (Equation 11) is applied:

21 m Θ [c j ] ⇑Θ×Ω (A k × c j ∪ Θ × cj ) = m Θ [c j ](A k ), ∀A k ⊆ Θ. (21)
Once the frame of discernment Θ × Ω is formalized, our approach proposes to combine the alternative priorities. In fact, we assume that each pair-wise comparison matrix is considered as a distinct source of evidence, which provides opinions towards the preferences of particular decision alternatives. Then, based on the belief function framework, we can apply the conjunctive rule of combination. The obtained bba represents the belief in groups of alternatives based on the combined evidence from the decisions matrices.

Finally, we might combine the obtained bba with the importance of their respective criteria to measure their contribution. That is, we will apply the conjunctive rule of combination and we get:

m Θ×Ω = ∩ j=1,...,m m Θ [c j ] ⇑Θ×Ω ∩ m Ω↑Θ×Ω . (22)
So, we obtain m Θ×Ω reflecting the importance of alternatives to the given criteria.

Decision making

To this end and after combining the resulting ballooning extension, a decision under uncertainty must be defined. In the sequel, the pignistic probabilities are used. However, our obtained beliefs are defined on the product space Θ × Ω. To solve this problem, we propose to marginalize this bba on Θ (frame of alternatives) by transferring each mass m Θ×Ω to its projection on Θ (Equation 8):

m Θ×Ω↓Θ (A j ) = {B⊆Θ×Ω|P roj(B↓Θ)=Aj )} m Θ×Ω (B), ∀A j ⊆ Θ. (23)
Finally, we can compute the pignistic probabilities to choose the best alternatives:

BetP (a j ) = Ai⊆Θ |a j ∩ A i | |A i | m Θ×Ω↓Θ (A i ) (1 -m Θ×Ω↓Θ (∅)) , ∀a j ∈ Θ. (24)

Example

In this section, we present an illustrative example showing that the proposed approach is a convenient tool for ranking alternatives in an uncertain environment based on belief assessments and qualitative evaluations.

We present an empirical study of purchasing a car. [START_REF] Ennaceur | Reasoning under uncertainty in the AHP method using the belief function theory[END_REF] In fact, selecting the best car from available alternatives is a classical and complex decision-making problem in which the overall performance of the alternatives needs to be evaluated with respect to each identified criteria. The reason why, subjective and qualitative assessments are often involved with regard to the criteria weight and alternatives score, resulting the use of the belief function framework to elicitate the decision maker preferences.

The first stage is the identification of the candidate criteria and alternatives. Our problem involves four criteria: Ω = {Comfort (c 1 ), Style (c 2 ), Fuel (c 3 ), Quietness (c 4 )}, and three selected alternatives: Θ = {Peugeot (p), Renault (r), Ford (f )}.

Along with our MCDM Method using preferential assessments, a judgment matrix based on the pair-wise comparison process using preference modeling defined in Table 2 was obtained as follows. So, given the necessary details of the criteria, the decision maker was asked to indicate his level of preference between them. Importantly, he was made aware that criteria that belongs to the same subset have the same importance.

} {c 4 } {c 2 , c 3 } {c 1 } - {c 4 } - - {c 2 , c 3 } - - -
From Table 2, we conclude that the decision maker has identified three subsets of criteria {c 1 }, {c 4 }, and {c 2 , c 3 }. For instance, expert may say that {c 1 } is evaluated to be more important than {c 4 } and {c 1 } is evaluated to be more preferred than {c 2 , c 3 }. Now, for deriving the weights of criteria, we apply our presented model. Therefore, we must transform these qualitative assessments into an optimization problem (Equation 16) and we get the following constraints:

(1) c 1 c 4 ⇔ bel({c 1 }) -bel({c 4 }) ≥ ε (2) c 1 (c 2 , c 3 ) ⇔ bel({c 1 }) -bel({c 2 , c 3 }) ≥ ε (3) c 4 (c 2 , c 3 ) ⇔ bel({c 4 }) -bel({c 2 , c 3 }) ≥ ε
Then, the obtained constraints are transformed into optimization problem in order to obtain the importance of criteria. We assume that ε = 0.01 and the uncertainty measure is H as defined in Equation 6.

M ax m H(m) = m({c 1 }) * log 2 (1/m({c 1 })) + m({c 4 })log 2 (1/m({c 4 })) +m({c 2 , c 3 }) * log 2 (2/m({c 2 , c 3 })) + m(Ω) * log 2 (4/m(Ω)); s.t. bel({c 1 }) -bel({c 4 }) ≥ ε bel({c 1 }) -bel({c 2 , c 3 }) ≥ ε bel({c 4 }) -bel({c 2 , c 3 }) ≥ ε ci∈F (m) m(c i ) = 1, m(A) ≥ 0, ∀A ⊆ Ω; m(∅) = 0. (25)
Finally, Table 3 represents the weighting vector (the result is obtained using Matlab toolbox). Similarly to the criterion level, the judgments between decision alternatives over different criteria are dealt within an identical manner. For example, to evaluate the alternatives according to the criterion c 1 , the expert is asked to evaluate the following subsets of alternatives: {p} and {p, r, f } (see Table 4). As similar process is repeated and a comparison judgment matrix in regard to each identified criterion was obtained (Table 5). After computing the belief functions for each set of alternatives with respect to each criterion, we must combine the weight of criteria and the alternatives priorities. Firstly, our presented approach proposes to standardize the criterion and the alternative frames of discernment. For the criterion level, we suggest to apply the extension procedure. Hence, Equation 20 is used and the resulting bba's are summarized in Table 6.

c 1 m Θ [c 1 ](.) c 2 m Θ [c 2 ](.) c 3 m Θ [c 3 ](.) c 4 m Θ [c 4 ] (
m Ω (.) m Ω↑Θ×Ω bbm m Ω ({c 1 }) {(p, c 1 ), (r, c 1 ), (f, c 1 )} 0.228 m Ω ({c 4 }) {(p, c 4 ), (r, c 4 ), (f, c 4 )} 0.218 m Ω ({c 2 , c 3 }) {(p, c 2 ), (r, c 2 ), (f, c 2 ), (p, c 3 ), (r, c 3 ), (f, c 3 )} 0.208 m Ω (Ω)
{(p, c 1 ), (r, c 1 ), (f, c 1 ), (p, c 2 ), (r, c 2 ), (f, c 2 ), (p, c 3 ), (r, c 3 ), (f, c 3 )} 0.346

After that, the next step concerns the alternative level. In fact, our method suggests to transform the conditional belief into joint distribution. For instance, if we present the priority matrix that evaluates the candidate subsets of alternatives regarding the criterion c 1 and by applying the ballooning extension using Equation 21. Let us consider for example, m Θ [c 1 ]({p}) its corresponding basic belief mass on Θ×Ω is obtained by {(p, c 1 )} and all the instances of Θ {(p, c 1 ), (p, c 2 ), (p, c 3 ), (p, c 4 )} for the complement of c 1 {(r, c 2 ), (r, c 3 ), (r, c 4 ), (f, c 2 ), (f, c 3 ), (f, c 4 )}. The following Table 7 is calculated.

m Θ [c 1 ](.) m Θ [c j ] ⇑Θ×Ω bbm m Θ [c 1 ]({p})
{(p, c 1 ), (p, c 2 ), (p, c 3 ), (p, c 4 ), (r, c 2 ), (r, c 3 ), (r, c 4 ), (f, c 2 ), (f, c 3 ), (f, c 4 )} 0.505 m Θ [c 1 ]({p, r, f }) {(p, c 1 ), (p, c 2 ), (p, c 3 ), (p, c 4 ), (r, c 1 ), (r, c 2 ), (r, c 3 ), (r, c 4 ), (f, c 1 ), (f, c 2 ), (f, c 3 ), (f, c 4 )} 0.495 Then, similar process is repeated for the rest of alternatives regarding each criterion. Finally, the obtained bba's m Ω↑Θ×Ω and m Θ [c j ] ⇑Θ×Ω can be directly combined using the conjunctive rule of combination to get the Table 8.

To choose the best alternatives, we must define our beliefs over the frame of alternatives. As a result, the obtained bba is marginalized on Θ using the Equation 23 (see Table 9).

We can now calculate the overall performance for each alternative and determine its corresponding ranking by computing the pignistic probabilities (Table 10).

As a consequence, the alternative "Peugeot" is the recommended car since it has the highest values. This research proposes that the difference between standard AHP method and the proposed approach are raised by a major factor. Our method can provide the decision maker to express his preferences with some uncertainty. In fact, our model allows the expert to use preferential assessments rather than deterministic value options in order to more imitate his reasoning. These evaluations are expressed using belief function framework.

For the sake of comparison, we have used belief AHP method to treat the same problem. [START_REF] Ennaceur | Reasoning under uncertainty in the AHP method using the belief function theory[END_REF] The same results were obtained as shown in Table 11. It is clear that "Peugeot" is the best choice. Belief AHP method and the approach developed have obtained the same best alternative. This would give the expert reasonable assurance in decision making. However in comparison with the Belief AHP method, the approach developed clearly has its advantages. In fact, our MCDM method is able to model uncertainty and imprecision associated with the pair-wise comparison process and it is able to quantify the criterion weights and the alternative scores without involving any numerical values to provide them.

Conclusion

In this paper, we have proposed a MCDM method in an environment characterized by the imperfection of the information. The belief function framework has been used for modeling the uncertainty related to the expert assessment and also to represent the decision maker preferences qualitatively without using any numerical values. The expert is then allowed to freely express his assessments using belief preferences relations only. Therefore, the originality of our model is its ability to express the expert opinions freely and based on incomplete ones. Also it can rank alternatives based on qualitative preferences only. On one hand, our proposed method models uncertainty by expressing the expert assessments using bba. On the other hand, it represents experts impression by comparing groups of criteria and alternatives instead of single ones.

  m Θ×Ω bbm {(p, c 1 ), (f, c 1 ), (r, c 1 )} 0.377 {(p, c 1 )} 0.225 {(p, c 4 ), (f, c 4 ), (r, c 4 )} 0.18 {(f, c 1 )} 0.005 {(p, c 2 ), (f, c 2 ), (r, c 2 ), (p, c 3 ), (f, c 3 ), (r, c 3 )} 0.003 {(r, c 2 ), (r, c 3 ), (f, c 2 ), (p, c 2

Table 1 .

 1 Preferences relation matrix.

		c 1	c 2	. . .	c m
	c 1	-P 12 . . . P 1m
	c 2	-	-	. . . P 2m
	. . .	-	-	-	. . .
	c m	-	-	-	-

In this table, P ij is a preference relations. It may be:

Table 2 .

 2 Preference relation matrix for criterion levelCriteria {c 1

Table 3 .

 3 The weights assigned to the subset of criteria In Table3, a new subset of criteria is appeared, this group Ω = {c 1 , c 2 , c 3 , c 4 } expresses then the part of ignorance.

	Criteria {c 1 }	{c 4 } {c 2 , c 3 }	Ω
	m Ω	0.228 0.218	0.208	0.346

Table 4 .

 4 Preferences relation matrix for alternative regarding c 1

	Criteria {p} {p, r, f }	bba
	{p}	-		0.505
	{p, r, f }	-	-	0.495

Table 5 .

 5 Priorities values

Table 6 .

 6 Vacuous extension of bba

Table 7 .

 7 Ballooning extension of conditional bba

Table 8 .

 8 The obtained bba: m Θ×Ω

Table 9 .

 9 The obtained bba: m Θ×Ω↓Θ

	m Θ×Ω↓Θ	bbm
	m Θ×Ω↓Θ ({p, r, f }) 0.66
	m Θ×Ω↓Θ ({p})	0.225
	m Θ×Ω↓Θ ({f })	0.005
	m Θ×Ω↓Θ (∅)	0.11

Table 10 .

 10 The Final ranking of alternative

	Alternatives {p}	{r}	{f }
	BetP	0.5 0.253 0.247
	Ranking	1	2	3

Table 11 .

 11 The Final ranking of alternative using belief AHP

	Alternatives	{p}	{r}	{f }
	BetP	0.567 0.213 0.220
	Ranking	1	3	2