Rodrigo Silva
email: rodrigo.silva@imt-atlantique.fr

Christophe Couturier
email: christophe.couturier@imt-atlantique.fr

Jean-Marie Bonnin
email: jean-marie.bonnin@irisa.fr

Thierry Ernst
email: thierry.ernst@yogoko.fr

A Heuristic Decision Maker Algorithm for Opportunistic Networking in C-ITS

Keywords: ISO TC 204, ETSI TC ITS, C-ITS, Decision Making, ACO, AD4ON

The number of connected devices is growing worldwide and connected and cooperative vehicles should be a major element of such ecosystem. However, for ubiquitous connectivity it is necessary to use various wireless technologies, such as vehicular WiFi (ITSG5, and DSRC), urban WiFi (e.g., 802.11 ac,g,n), 802.15.4, cellular (3G, 4G, and 5G under preparation). In such an heterogeneous access network environment, it is necessary to provide applications with transparent decision making mechanisms to manage the assignment of data flows over available networks. In this paper, we propose the Ant-based Decision Maker for Opportunistic Networking (AD4ON), a Decision Maker (DM) algorithm capable to manage multiple access networks simultaneously, attempting to choose the best access network for each data flow. Moreover, the AD4ON is capable to increase decision's stability, to reduce the ping-pong effect and to manage decisions flow by flow while maximizing flow's satisfaction.

INTRODUCTION

The number of connected devices is growing exponentially around the world. Connected Internet of Things (IoT) devices are expected to surge to 125 billion by 2030 [START_REF] Howell | Number of Connected IoT Devices Will Surge to 125 Billion by 2030[END_REF].

According to Gartner research company, connected cars will be a major element of the IoT (Gartner, 2018). Once vehicles are capable to exchange information with others devices and the infrastructure, they become cooperative and an ecosystem of applications and services can be developed around them.

In this context, users, devices and vehicles need to be connected anywhere, anytime with anything. Such an environment is characterized by its heterogeneity. Each service has specific communication requirements. There are a wide variety of mobile devices, each one with specific capabilities in terms of storage, processing and communication. Moreover, users can have specific preferences.

However, a single access technology to connect all these services and devices is impractical. For ubiquitous connectivity it is necessary to use heterogenous wireless technologies, such as vehicular WiFi (ITSG5, and DSRC), urban WiFi (e.g.,802.11 ac,g,n), 802.15.4 or cellular (3G, 4G, and future 5G) (ETSI, 2010;IEEE, 2006;[START_REF] Chakrabarti | IPv6 over Low-Power Wireless Personal Area Net-work (6LoWPAN) ESC Dispatch Code Points and Guidelines[END_REF]. Due to complementary characteristics of such networks, more connectivity opportunities are available. Mobile devices equipped with multiple communication capabilities can use opportunistically these multiple access technologies in order to maximize flows satisfaction (e.g., maximizing communication bandwidth, and/or reducing latency) and to satisfy communication requirements (e.g., security, monetary cost, traffic load balancing, and others).

In such an heterogeneous and dynamic access network environment, applications and services cannot take into account all technology particularities, unless they explicitly need it. It is preferable to provide applications with a communication architecture that hides the heterogeneity of underlying access technologies, providing seamless communications independently of radio access technology.

Standardization bodies have worked to establish an harmonized communication-centric architecture. International Organization for Standardization (ISO) and European Telecommunications Standards Institute (ETSI) proposed an ITS-S reference architecture (ISO, 2014), which is capable to manage heterogeneous wireless access technologies while hides to the application the underlying differences of access network.

In our previous work (Silva et al., 2017a), we pro-posed an architecture which is compatible with ISO and ETSI (ISO, 2014) standards and reserves space for a DM algorithm in charge of managing in real time the placement of applicative flows over available networks.

Based on our research, on ISO/ETSI standards and surveys, we identified some important properties for decision making in the vehicular environment that are not addressed by existing DM algorithms, like increase the stability of decisions to avoid the ping-pong effect, and avoid full recalculation when few network parameters change.

Therefore, to meet such properties, we propose in this paper the AD4ON, a DM algorithm capable to manage multiple access networks simultaneously, attempting to choose the best access network for each data flow. This algorithm is designed to increase decision's stability while maximize flow's satisfaction.

We performed simulations to compare the AD4ON algorithm with three other DM algorithms: the well-known Technique for Order Preference by Similarity to Ideal Solution (TOPSIS), a modified TOPSIS (mTOPSIS) and a commercial DM used in most of smartphones, in which decisions are based on predefined network priorities (e.g., connect to WiFi if available or to 3G/4G otherwise).

Simulations demonstrate that AD4ON algorithm outperforms the other algorithms, increasing the total flow satisfaction, increasing decision's stability and reducing the overall monetary cost.

The rest of this paper is organized as follows. Section 2 reviews some related work. Section 3 describes the needs for DM in vehicular environment. The AD4ON algorithm is described in Section 4. In section 5 we discuss about simulation results and Section 6 concludes the paper.

RELATED WORK

Several works have concentrated on decision making algorithms for multiple attributes problems. Most of them are based on well-known Multi-Attribute Decision Making (MADM) techniques like Simple Additive Weighting (SAW), Multiplicative Exponential Weighting (MEW) and, mainly TOPSIS [START_REF] Hwang | Multiple Attribute Decision Making: Methods and Applications A Stateof-the-Art Survey[END_REF].

In TOPSIS, decision calculations are based on a matrix where lines represent available networks and decision attributes are set on columns. A quadratic vector normalisation is applied on columns in order to homogenize the weight of each attribute. This results in a hight sensitivity to extreme values which leads to unstable decisions when a mobile approaches the limit of range of a given network (where the network can appear or disappear between two steps of calculations). To mitigate this so called rank reversal behaviour, authors of [START_REF] Senouci | Utility function-based TOPSIS for network interface selection in Heterogeneous Wireless Networks[END_REF] propose to replace the classical quadratic normalization by a new approach based on utility functions. This way, applications can present a specific utility function for each attribute. Simulations show that this approach eliminates the rank reversal and increases the ranking quality by fulfilling the application requirements. However, this paper considers all flows over only one access network at a time. We compared the AD4ON with a version of this approach (which we named mTOPSIS).

In [START_REF] Bouali | A Context-Aware User-Driven Framework for Network Selection in 5G Multi-RAT Environments[END_REF] authors develop a fuzzy MADM methodology to combine application Quality of Service (QoS) requirements with context components (e.g., monetary cost or network power consumption), in order to make context-aware network selection for each application. First they use Fuzzy Logic Controllers (FLC) that consider network parameters and application QoS requirements to determine the QoS suitability level of each network. Then, they use MADM SAW algorithm to combine the previous calculated QoS suitability level with context components. The network alternatives are ranked by their context suitability level. Finally, they choose the best network for each application, i.e., the network that maximizes the context suitability level. Since this paper consider the SAW MADM technique, it is susceptible to suffer from "ping-pong" effect [START_REF] Triantaphyllou | More Cases of Ranking Abnormalities when some MCDM Methods are used[END_REF].

Paper [START_REF] Zarin | A hybrid network selection scheme for heterogeneous wireless access network[END_REF] proposes an hybrid decision approach in which decision making is distributed between user devices and the Central Controller Network (CCN), a centralized controller in the network side. First of all, user devices scan available networks based on both the Received Signal Strength (RSS) and user mobility. For example, a mobile user with high speed does not consider networks with low coverage. If the received signal strength is higher than a predefined threshold, the device reports its input parameter (application bandwidth, user mobility and battery constraint) to the CCN. Thus, the CCN uses the MADM MEW algorithm to rank the networks and provides an associated set of networks for each application. This approach suffers from scalability issues. Due the growing number of user devices and their mobility, the amount of information exchanged between user devices and the CCN management overhead.

In paper [START_REF] Rayana | A Smart Management Framework for Multihomed Mobile Nodes and Mobile Routers[END_REF] authors describe a DM framework for network management, in which a combination of MADM SAW and Ant Colony Optimization (ACO) based algorithms is used to select access networks for each flow communication. First, the SAW algorithm calculates a utility score for each feasible flow -network solution. Such score indicates the matching degree between flow requirements and network characteristics. In a second step, the ACO-based algorithm adds the network costs (i.e., power consumption and network load) to the previous utility function in order to find solutions taking into account the whole system satisfaction. In this work, the decision stability is addressed by changing the weight of network costs so that currently enforced solutions are privileged. However, choosing the best weight is not a trivial task.

PROBLEM DESCRIPTION

Due to the dynamic environment of connected vehicles, we work on a DM mechanism for opportunistic networking in heterogeneous access network environment. In our previous work (Silva et al., 2017a), we proposed a DM architecture for opportunistic communication. This architecture is based on the ISO/ETSI ITS-S communication architecture due the latter's capability to manage heterogeneous access technology (ISO, 2014).

At the heart of this architecture, we need a DM algorithm to take smart and fine-grained decisions. In previous researches [START_REF] Silva | Opportunistic Networking for ITS[END_REF] we identified some properties for such DM mechanism in the vehicular environment. These properties are summed up bellow.

Expected properties

The DM algorithm should present the following properties. 1) It is necessary to manage decisions flow by flow, choosing the access network that better match the communication requirements for each flow. 2) It is necessary to manage multiple attributes from different actors (e.g., application requirements, user preferences, administrators and regulators rules). 3) The DM should manage multiple objectives simultaneously, which can be contradictory. For example, increase the communication QoS (data rate, latency) while reduce the overall monetary cost. 4) It is necessary to increase the stability of decisions, avoiding "ping-pong" effect. 5) Moreover, the DM algorithm should avoid full recalculation when only few network parameters change.

Motivation

Existing algorithms in the literature do not meet all our identified needs and current commercial ones do not consider multiple attributes: they are usually based on static and predefined decisions.

A large number of research studies have concentrated on the development of DM algorithms based on MADM methods. Among these algorithms we can highlight the TOPSIS, which is the most used in the literature. Despite the MADM methods present advantages such as relative low computation complexity, this approach has some limitations. They require to make full recalculation even if only a given network parameter change and suffer from ranking abnormality (i.e. they are very sensitive to small changes of inputs).

Therefore we propose AD4ON, a DM algorithm able to manage multiple flows and multiple access networks simultaneously, attempting to choose the best access network for each data flow while increasing decision stability, reducing the ping-pong effect and managing decisions flow by flow to maximize flow requirements satisfaction. The AD4ON algorithm is explained in section 4.

THE AD4ON ALGORITHM

AD4ON is based on the ACO, a swarm intelligence class of algorithms based on the collective and cooperative behavior of ants, which are capable to find high-quality solutions for complex combinatorial optimization problems in a reasonable time.

The ACO algorithms present some properties that can be explored to meet our needs. For example, since ants drop pheromone based on the solution qualities, and decisions are driven by pheromone concentration, solutions are created smoothly over time. This tends to filter transient effects and thus offers a better stability. Moreover, since it is a memory-based algorithm (i.e. new solution can take into account previous status of the network environment), we can prevent full recalculation when only few network parameters change.

We modeled our flow to network assignment problem as a bipartite graph G(F, N, E), where F correspond to data flows, N correspond to available networks and E = { f : i → j | i ∈ F, j ∈ N}, i.e., E is the union between the sets F and N, if flows in F can be assigned to networks in N. The AD4ON takes into account requirements and preferences from different actors (e.g., applications, users, administrators and regulators), as well as information about access networks conditions (e.g., data rate, latency) in order to construct this graph.

Once the graph with all potential solutions is generated, the algorithm establishes the flow to network assignment as described in Algorithm 1.

• First, we set the values of parameters α, β and ρ that respectively determine the relative influence of the pheromone trail, the heuristic information and the evaporation coefficient of pheromone. We also initialize the "PS" and "FL" variables that will respectively store the non-dominated solutions and the list of flows (lines 1 -3). • The DM receives the graph G(F, N, E) that represents all possible solutions (line 4). graph G between current flow and potential networks (line 10). The probability (P i, j ) for an ant to choose the path i, j, i.e., the path between flow i and network j is given by Equation 1.

P i, j = [τ i j ] α [η i j ] β ∑ k ∈ V i [τ ik ] α [η ik ] β (1)
where τ i j is the amount of pheromone present between flow i and network j, V i is the set of available networks for the flow i, η i j is the heuristic information and it is given by Equation 2.

η i j = N ∑ n=1 (w n * uP n (i, j) ) (2)
where uP n (i, j) is the utility function of a given parameter n (e.g., data rate, latency, monetary cost) between the flow i and the network j, N is the number of decision parameters, and w n is the weight of each utility parameter function, such that ∑ w n = 1.

• In order to better meet flow requirements, a suitable utility function was defined for each parameter (i.e., uP n ), as shown on • Once an ant found a complete solution, i.e., an access network for each flow from the graph, such ant update the pheromone table (line 15). Besides the pheromone deposition, it is necessary to apply a pheromone evaporation rule. Such pheromone evaporation prevents the convergence of the ACO algorithm to a locally optimum solution while enables ants to "forget" low quality solutions. The pheromone update mechanism is given by Equation 3.

τ i, j (t + 1) = (1 -ρ)τ i, j (t) + m ∑ k=1 ∆τ k i, j (3)
where ρ is the pheromone evaporation rate (0 < ρ < 1), m is the number of ants and ∆τ k i, j is the amount of pheromone deposited by ant k on the edge i, j.

• After all ants have visited the graph G, we should evaluate the found solutions. In decision making, utility refers to the satisfaction that a solution provides to the decision maker. Therefore, we propose an utility function that calculates a score representing the matching degree of each solution in the current ant colony (line 16). The utility function is defined by Equation 4.

U = F ∑ f =1 η f (4)
where η f is the heuristic information between a given flow and its network solution. F is the number of flows in the graph G. • Each solution not dominated by both other solutions in the current colony and the non-dominated solutions already in the Pareto set PS, should be added to PS. And all solutions dominated by the added one should be eliminated from PS (line 17).

Then, the ants are scattered again though the existing flows in the graph G. And all process restart from the line 5, until a stop condition is satisfied.

EVALUATION OF THE AD4ON ALGORITHM

In order to test the AD4ON algorithm, we performed simulations and compared the results with three other DM algorithms: the traditional TOPSIS, a modified version of TOPSIS (mTOPSIS) like the one of [START_REF] Senouci | Utility function-based TOPSIS for network interface selection in Heterogeneous Wireless Networks[END_REF], and a version of current commercial DM (Commercial DM (CM)). To evaluate simulation results we defined some Key Performance Indicator (KPI).

Key Performance Evaluation

According to the literature, performances are usually evaluated using an objective function (utility or cost function) regardless of whether or not it satisfies the application needs (i.e. the higher is the utility value of a decision, the better the solution). However, this evaluation does not reflect the actual applications needs. For example, if we consider a flow, requiring 300 kbps of maximum bandwidth that is sent through a WiFi network called WiFi-1 that offers 1 Mbps of bandwidth; if another WiFi (WiFi-2) offering 2 Mbps of bandwidth appears and if we do not consider other parameters more than bandwidth, the decision maker based only on the objective function is supposed to move the flow over WiFi-2. However, both WiFi networks satisfy 100% of flow requirement and it would be better to maintain the flow through the WiFi-1, in order to avoid packet loss or increased latency due to the new network association.

Therefore, in order to compare the AD4ON algorithm with others, we consider three KPI:

• The flow satisfaction (FS): is the percentage of meeting flow requirements. We consider that a given flow is completely satisfied if all its requirements are 100% satisfied by the chosen network.

For example, a flow that requires a maximum data rate DR f low and a minimum latency sensibility L min is 100% satisfied by a network N, if such network is capable to supply the flow with a data rate DR net , such that DR net ≥ DR f low , and with a latency L net , such that L net ≤ L min . If the chosen network satisfy only the minimum value for all parameters required by a given flow, such a flow satisfaction will be the minimum one, i.e., 10% as considered in this work.

• The stability of decision (DS): frequent changes of network can increase the packet loss and the communication latency. Therefore, we aim to reduce the number of network switching. To calculate this indicator, we consider the average of network switching performed by each DM algorithm in all scenarios.

• Monetary utility (MU): we aim at finding solutions that offer the lowest monetary cost for users (i.e., higher monetary utility). We assume that the user informs the DM algorithm of the maximum price he or she is willing to pay for data communication. Based on this information, the DM can calculate a monetary utility as being the ratio between the communication cost and the maximum price the user is willing to pay.

Finally, we define a cost function that is the average of the three KPI (see Equation 5). In this way, the algorithm with the best performance is the one that finds solutions with lowest total cost (TC).

Total cost = N ∑ i=1 w (i) * (1 -KPI (i) ) (5)
where w (i) is the weight of KPI (i) , such that ∑ w i = 1.

Description of simulation scenarios

To implement the simulation scenarios, we consider a vehicle capable to connect with multiple access networks simultaneously, which is being driven in a zone covered by four access networks (two urban WiFi networks, one cellular network and one vehicular WiFi).

In each scenario, the vehicle moves along a route of 1000 meters long, while it experiences different flow demands and network conditions. Each access network is described by five parameters: data rate, latency, PDR, RSSI and monetary cost (i.e., the pricing for mobile data services).

For the sake of statistical analysis, each simulated scenario was executed 5 times. Indeed, due to the stochastic property of ACO algorithms, the results of AD4ON may vary between two executions of the same scenario.

We divided our simulation into two steps: 1) a first step composed by a simple scenario, which is based on real testbed; and 2) a second step composed by multiples scenarios commonly used by literature. In the following, we describe the simulation scenarios for each of these steps.

Simulation scenario for the first step

In the first step we defined the scenario 1, a simple scenario composed by one application (App1) with constant requirements and four access networks. The objective of this step is to show the output and the key performances for each DM algorithm separately, while the vehicle moves along the defined route. The application and network parameter values observed by the vehicle along this route are showed on Figure 2. They are taken from our database of real measurements on the field.

Simulation scenario for the second step

In the second step, we used scenarios commonly used by most of literature works, i.e., with input values randomly chosen from a range of predefined values. In this step, we defined 50 new scenarios. Each one involving four data flows (conversational, streaming, interactive and security) and four access networks (cellular, vehicular WiFi (ITS-G5), and two urban WiFi (802.11n)). Each data flow represents a given application with specific requirements in terms of data rate, latency and PDR.

The flows requirements and networks conditions are randomly generated using the range of values given in Table 1 andTable 2. The network priorities defined for the CM were based on the monetary cost of networks, i.e., free networks were privileged. Therefore, we defined the following descending priority's order: urban WiFi (WiFi 1 and WiFi 2), ITS-G5 and Cellular.

We performed simulation of the AD4ON with different parameter values (α, β, etc), and we chosed the values that gave better results for the simulated scenarios. Selected parameter values are showed on Table 3.

Simulation Results and Discussion

Simulation results are compared based on the previous defined KPIs and TC function. Depending on applications, the total cost evaluation based on the same weight may not be suitable in some cases. However, in this work we considered the same weight for all KPIs.

Results for the first step

Simulation results of the four algorithms on the scenario 1 (the one of the first simulation step) are showed on Figure 3. Figure 3 shows the network chosen for "App1" by each DM algorithm, while the vehicle moves along the route. As expected, the traditional TOPSIS present more ping-pong effect than the others, as we can observe on Figure 3a.

The KPI (FS, DS and MU), as well as the TC for each DM algorithm, are shown on Table 4.

This specific scenario favors the CM algorithm. The RSSI distribution along the route, as showed on Figure 2a, enables a smooth network switching, reducing the ping-pong effect. Moreover, the network parameters follow the RSSI distribution, i.e., good RSSI levels coincide with good values of DR, Latency and PDR. Therefore, in this specific scenario, the CM presents good performances.

The solutions found by the AD4ON present a flow satisfaction of 62.22% and a monetary utility of 73.76%. This means that, in average, the solution satisfied 62.22% of "App1" requirements and that for 73.76% of the time, the algorithm selected the access network with the lowest monetary cost. Since TOP-SIS tries to find the best utility regardless to pingpong effect, for these two KPI the AD4ON offers slightly lower performances than TOPSIS (around 1% difference), which occupies the first place for this specific scenario. However, such slight underperformance is compensated by AD4ON stability, i.e., avoiding ping-pong effects.

Concerning decision stability, the AD4ON is better than the others, performing 65% less network switching than TOPSIS and 50% less than mTOPSIS.

Analyzing the total cost (calculated by Equation 5), we observe that the AD4ON outperforms the other algorithms, meaning that proposed solutions offer the best compromise between the three indicators.

Results for the second step

The results for the second step of the simulations are shown below. We only show the total cost for each flow, calculated as described by Equation 5. Figure 4 shows the total cost of solutions found by each DM algorithm. Analyzing this figure we observe that the CM has the worst performances. Since its solutions are based only on the RSSI, we observed that it frequently finds no feasible solution, i.e., it chooses network that has good RSSI, but does not meet the minimum flow requirements (e.g., in terms of PDR, DR or Latency). This behavior impacts negatively the KPI, and consequently increases the TC.

The AD4ON algorithm outperforms the other algorithms. It found better solutions for streaming, conversational and interactive flows in all simulated scenarios, as shown on Figures 4a, 4b, and4c. For the safety flow (Figure 4d), the AD4ON outperforms the others in most of scenarios, and in the worst case, presents the same quality as TOPSIS.

CONCLUSION

In this paper, we proposed the AD4ON, an ACObased DM algorithm to solve the problem of assigning multiple data flows over heterogeneous access networks in real time.

We compared the AD4ON algorithm with three others: the TOPSIS, a variation of TOPSIS and the one used in most of smartphones (CM). Simulations results have demonstrated that the AD4ON outperforms the other algorithms by increasing the total flow satisfaction, limiting the ping-pong effect and consequently increasing the decision stability. This shows that ACO algorithms are good candidates for the implementation of such decision algorithm in routers used to manage vehicular communications.

This work presents a reactive algorithm, (i.e. one that finds new solutions by reacting to the observation of network conditions). However, vehicles can move at high speed frequently changing network environment. Due to such highly dynamic mobility, it is desired a DM capable to make proactive decisions. Therefore, as future work we aim to enable the AD4ON to take into account the near future prediction of network environment in its decision process.

Figure 1 :

 1 Figure 1: Utility functions.

  • The ants are randomly scattered through the existing flows in the graph G.• Once the ants are distributed, they start to construct solutions by randomly exploring the graph.For each visited flow, ant chooses one network among all possible networks, i.e., a path in the

	Algorithm 1: ACO algorithm
	2 PS = null ;	// Initialize Pareto Set
		(PS) as empty
	3 FL ← list of flows
	4 G(F, N, E) ← "Rank Alternatives" module
	5 while stop condition do
	6	for k = 1 → NumberO f Ants do
		/* Construct a solution	*/
	7	Sort the flow list FL
	8	while remains not visited flow in FL do
	9	for each possible network for such
		f low do
	10	calculate the probability of
			choosing that network
			according to Equation 1
	11	end
	12	choose the network to be mapped
	13	end
	14	end
		/* Evaporation	*/
	15	apply the pheromone updating according to
		Equation 3
		/* Evaluation	*/
	16	Calculate the value of objective function
		for each solution in current ant population
		(Equation 4)
	17	Update the Pareto set solutions (PS)
	18 end
	19 Return the Pareto Set PS

1 Set values of ACO parameters (e.g., α, β and ρ)

Table 1 :

 1 Range of flow requirements

Table 2 :

 2 Range of Network Parameters

	Parameters	Cellular	ITS-G5	WiFi
	DR (Mbps)	0 .. 14	0 .. 22	0 .. 22
	Latency (ms) 0 .. 250	0 .. 200	0 .. 200
	PDR (%)	90 .. 100	80 .. 100	40 .. 100
	RSSI (dBm) -120 ..-65 -110 ..-45 -110 ..-45
	Cost ($/MB) 0.1 .. 0.4	0	0

Table 3 :

 3 AD4ON parameters

	Parameter Values	Description
	α	2.0	pheromone influence
	β	3.0	heuristic influence
	ρ	0.3	pheromone evaporation
	ants	10	number of ants
	iterations	50	stop condition (Algorithm 1)

Table 4 :

 4 Key performance results for scenario 1.

	KPI	TOPSIS mTOPSIS	CM	AD4ON
	FS (%)	63.79	63.78	59.79	62.22
	MU (%)	74.41	74.41	70.48	73.76
	DS (%)	6.67	33.34	46.67	66.67
	TC (%)	51.71	42.83	41.02	32.45