Wahabou Abdou

Christelle Bloch

Damien Charlet

Dominique Dhoutaut

François Spies

Designing Smart Adaptive Flooding in MANET using Evolutionary Algorithm

Keywords: MANET, VANET, Flooding, Broadcast Storm Problem, Evolutionary Algorithm

This paper deals with broadcasting security messages in mobile ad hoc networks (MANETs). Traditional broadcasting schemes tend to focus on usually high and homogeneous neighborhood densities environments. This paper presents a broadcasting protocol that locally and dynamically adapts its strategy to the widest range of neighborhood densities. The behavior of the protocol is tuned using various internal parameters. Multiple combinations of those parameters have been precomputed as optimal solutions for a range of neighborhood densities, and the most relevant one is dynamically chosen depending on the locally perceived environment. The combinations were determined by coupling an evolutionary algorithm and a network simulator (ns-2), using a statistically realistic radio-propagation model (Shadowing Pattern). This approach is compared with other probabilistic methods while broadcasting an emergency message in Vehicular Ad hoc Networks (VANETs) with variable and heterogeneous vehicle densities. In such a context, it is expected from the network to enable each of the nodes to receive the warning message. The results show that our protocol covers the whole network, whereas other methods only reach between 57% and 90% coverage.

Introduction

The broadcast is a regularly used mode of communication in Mobile Ad hoc Networks (MANETs). It is used by routing protocols for route discovery and maintenance. In such networks, a wide spread of packets is possible only if they are relayed by some nodes. However, nodes share the wireless channel and an inappropriate relay strategy can lead to a channel saturation or packets losses and prevent a wide dissemination. The diffusion scheme depends on the network density. Several broadcasting methods have been proposed for MANETs to optimize the channel use. Notably, probabilistic methods determine the probability P to retransmit a packet for every node, and each packet is retransmitted at most once per node. These solutions have reduced the number of redundant packets.

In general, existing solutions have not been designed for very low densities networks. This paper proposes to add new parameters to probabilistic broadcasting methods to adapt the diffusion strategy to various network densities. Accordingly, it expands the search space and the complexity of the problem. Therefore an evolutionary algorithm is used to determine the parameter combinations that best fit to various levels of the network density. A network simulator (ns-2) is used to assess the dissemination of packets using each parameter combination. The broadcast protocol resulting from this proposal is then compared to three other probabilistic methods. Initially, comparisons were made for networks with homogeneous densities, then for a heterogeneous network.

The remainder of this paper is organized as follows. Section 2 presents an overview of MANETs broadcasting methods. Section 3 describes the proposed broadcasting protocol which adapts its dissemination strategy to the network density. The experiments for both homogeneous and heterogeneous networks are outlined in Section 4. Section 5 presents concluding remarks and outlines future work.

Broadcasting methods in ad ho networks

Message broadcasting in MANETs consists in sending a packet from one node to every node within its transmission range. This kind of communication is a recurring task which is specially used by routing protocols for route discovery. It is worthy of note that in networks such as WiFi, a node cannot both send and receive packets at the same time. Such a situation would cause collisions and generate errors on both communications (transmission and reception). To reduce the risk of interference and thus optimize the use of the radio channel, several broadcasting methods have been proposed for MANETs and some of them are dedicated to delay tolerant networks.

Generic methods for MANETs

The broadcasting methods could be classified with respect to the nature of the algorithms: deterministic or non-deterministic.

Deterministic methods are methods whose behaviors are (quasi-)predictable, and whose decisions are not based on random variables1 . This group, gathers simple flooding, neighbor-knowledge approaches and multi-point relay methods.

Simple flooding: is obviously the simplest broadcasting strategy. Each node relays received packets exactly once. Duplicate messages are discarded. This method does not take into account the neighborhood density of nodes. In high density networks, the simple flooding wastes the bandwidth and may leads to network contention.

Neighbor knowledge-based methods: using "Hello" packets, nodes build a 1hop or 2-hop neighbors lists. These lists are suffixed to the broadcast packets so that the receiver (r) can compare the sender's list to its own list.This comparison determines the additional nodes that will receive the message if r forwards it. For static or low mobility networks, it is a fair method. But when the node's velocity is high, the information about the neighbors become quickly inaccurate. Alba et al. [1] have proposed an improvement of the knowledge-based methods. The authors used a cellular multi-objective genetic algorithm to find the values of the parameters that help to assess whether to forward a message.

Multi-point relay (MPR): it is a variation of knowledge-based techniques suggested by the Hypercom team of INRIA 2 lab. To reduce the number of redundant broadcasts of a packet in the network, each node chooses several nodes among its neighbors that will relay its communications. The selected nodes are called MPRs [START_REF] Nguyen | Analysis of mpr selection in the olsr protocol[END_REF]. When a node sends a packet on the radio channel, all its neighbors will receive it, but only the MPRs of the source node will relay the message. That means each node will have a list of all nodes that have chosen it as their "repeater" (MPRs selectors list). The MPRs are selected among the 1-hop neighbors so that they enable the node that has chosen them to reach all its 2-hop neighbors. The goal is to have the smallest list of MPRs in the network which optimizes communications. The MPRs require a bidirectional link.

Non-deterministic methods

Probabilistic methods: they aim to improve the simple flooding method. Upon the reception of a packet, the node forwards or discards it depending on a given probability p [3] [4] [START_REF] Abdalla | Performance evaluation based on simulation of improving dynamic probabilistic flooding in manets[END_REF]. A challenge is to set the value of P . Although Li et al. [START_REF] Li | Gossip-based ad hoc routing[END_REF] suggest that values between 0.6 and 0.8 are optimal, it is obvious that they are not optimal for all network densities. If P = 1, this method is equivalent to simple flooding.

Counter-based schemes: they require nodes to count the number of the redundant copies of a single message over a short period of time called Random Access Delay (RAD) [START_REF] Bani Yassein | New adaptive counter based broadcast using neighborhood information in manets[END_REF]. When the RAD expires, if the number of copies is less than a given threshold (c t ), the message is forwarded. Otherwise, it is dropped. This method implies additional latency.

Location-based methods: before relaying a message, the node evaluates the additional coverage area that will result from this retransmission. This technique does not consider whether nodes exist within that additional area or not. To evaluate the extra coverage area, the node can use the distance between itself and each node that has previously relayed the message (distance-based scheme) or the geographical coordinates (location-based scheme). In both distance-based and location-based schemes, a RAD is assigned before the message is relayed (if the additional coverage area is higher than a fixed threshold) or dropped.

Diffusion methods dedicated to delay tolerant networks

In a sparse environment, communications in VANETs behave like those studied by the Delay/Disruption Tolerant Network (DTN) community. Thus, flooding protocols developed for DTN might be used in VANETs. The epidemic routing [START_REF] Vahdat | Epidemic routing for partially-connected ad hoc networks[END_REF] scheme proposes that a node relays the message to all the nodes it crosses, which did not know about it. This is a monotone relay strategy. The PRoPHET protocol [START_REF] Lindgren | Probabilistic routing protocol for intermittently connected networks[END_REF] (Probabilistic Routing Protocol using History of Encounters and Transitivity) applies probabilistic routing instead of doing blind epidemic replication of bundles through the network. it uses a metric called 'delivery predictability' established at every node A for each known destination B.

-Because of the low reception rate found in such environments, most of these protocols schedule multiple transfer of the same message. The number of replica may range from one copy (e.g., direct transmission protocol [START_REF] Spyropoulos | Single-copy routing in intermittently connected mobile networks[END_REF]) to an infinite as in epidemic routing. As it has a direct impact on the network load, much effort has been undertaken to leverage the cost of forwarding by finding the most valuable tradeoff between cost and reliability [START_REF] Fall | DTN: an architectural retrospective. Selected Areas in Communications[END_REF]. It should be noted that most of the advanced scheme are tuned for sparse environments, and do not scale to be used in medium or high density environments.

3 A new neighborhood density-aware method

Challenges

One of the main challenges of broadcasting problems in wireless ad hoc networks is to reach the maximum number of nodes while avoiding useless repeats. Recent work in this field shows the need to reduce the number of relay nodes when the network density is high. However, as mentioned in Section 2, a part of those improvements is to the detriment of the delay, especially because a waiting time (RAD) is added. Another weakness of existing methods is the impracticability of their proposals in very sparse networks (i.e. the probability that a node has a neighbor is very low) and environments where the broadcast packets may be lost. Indeed, according to the WiFi standard, broadcast packets are not acknowledged. Thus, the source node cannot be sure that the packets are received. To solve this problem, it is necessary to retransmit packets more than once in certain cases. In our proposal, we suggest to improve the existing probabilistic methods by adding new parameters. We use the following four parameters to regulate broadcast in MANETs:

-The probability (P ) to relay a packet. Upon the reception of a packet, each node decides to forward or to drop it depending on the value of P . This is the main parameter of the probabilistic methods. -The number of times each packet will be repeated (N r). In the case of lowdensity mobile networks, a node may not have a neighbor in its coverage area when it forwards a packet. By repeating the packets more than once, this node increases its chance of being heard by another mobile node. This parameter can also be useful when the initial transmission is lost due to collisions or other phenomena related to radio propagation conditions. -The delay (Dr) between two successive repeats. Indeed, if a node has to repeat the packets several times, one must determine the frequency at which the redundant copies should be sent. Please note that in a dense network, low values of Dr could lead to the increase of the number of collisions. -The T T L (Time To Live). This parameter permits to confine the spread of messages in a given geographic area. It specifies the number of hops allowed to the packets.

The variation range of these parameters is given in Table 1.

Using these four parameters, the solutions are simulated using the Network Simulator 2 (ns-2) [12]. As the simulations are stochastic processes, each solution is evaluated by the simulator 500 times 3 to obtain statistically reliable results. ns-2 assesses the solutions using the four following criteria: -N C: the average number of collisions; -P T : the average propagation time (the time spent until all the nodes in the considered area receive the message); -R: the average number of retransmissions during the simulation.

Parameter P N r
-F R: the full reception ratio. It is the ratio between the number of successful simulations 4 and the total number of simulations (500 in our experiments).

Relying on these parameters and criteria, our method is based on three steps:

-Simulating ad hoc networks with different neighborhood densities to determine the appropriate values of P , N r, Dr and T T L in every context; -Enabling the nodes to determine their neighborhood density (without sending HELLO packets, or adding a waiting time);. -Making the nodes able to automatically change their broadcasting strategy by choosing the one that best suits the environment of each node.

The following subsections detail these three steps.

3 This value is determined empirically. It represents a good compromise between the result confidence interval and the simulation time 4 For each of the 500 simulations, if the channel is saturated, the number of collisions may prevent the message from being normally transmitted to all the nodes. In very low density networks, communications between nodes may also break or deteriorate gradually and prevent a complete reception by the nodes. In these cases, the simulation is stored as a failed simulation.

Setting broadcasting parameters for various densities

The variation ranges given in Table 1 result in a search space that contains 9.10 16 possible combinations. Running each combination requires from a dozen seconds up to a few minutes according to the considered neighborhood density. Simulating all possible cases with ns-2 would take a long time. That is why an evolutionary algorithm (EA), inspired by the theory of natural evolution, is used to assess a subset of interesting solutions. Figure 1 illustrates the three main modules of the proposed approach (an optimization engine, a network simulator and a log analyzer) and their interaction. Firstly, the EA randomly generates a set of n possible solutions called initial population. (In Figure 1 the "P 0 ?" condition is used to check if the current population is the initial one.) Each solution, i.e. a set of possible parameters, must be evaluated and fitness is assigned to it. In our case, the evaluation process is done in two steps: the first is performed by the "Network simulator" and "Log analyzer" modules; the second is assessed by the EA. Firstly, each set of parameters is transmitted to the network simulator. The latter integrates the received parameters into the simulation scripts. Thereafter, the simulations are run and some log files are built. These files describe the network behavior. The log files are passed on to the log analyzer that extracts the values of the objective functions. The calculated objective values are then conveyed to the optimization engine that ranks the solutions according to these values, using the concept of Pareto dominance. Pareto solutions are those for which improvement in one objective implies the worsening of at least one other objective. Four Pareto fronts are built (R 1 , R 2 , R 3 and R 4 . R 4 represents the dominated solution list). Thereafter two individuals (called parents) are selected for recombination.Each parent is chosen by two random selections. The Pareto front is first selected according to a computed probability. The probability to select each list both takes into account a priority level associated to each list's and the list length. This favours the best solutions while preventing the dominated solutions from having very low values of fitness, in order to preserve the diversity of the successive populations. Then an individual is randomly selected among the individuals belonging to this front, using equal probabilities for all these individuals. Each pair of selected parents is recombined using a simulated binary 10-point crossover (variables are first converted into binary strings). The k-point crossover operator was chosen because it is a classical method of recombination. The value of k was empirically tuned. Finally, a uniform mutation is applied: a gene is randomly chosen and the EA generates a new value for this variable with respect to its variation range. These operators permit to generate a list of offspring, whose fitness is again computed using ns-2 simulations. Each offspring replaces the first parent it dominates in the population list. If the offspring does not dominate any parent, it is not added to the list of individuals of the next generation. All these steps (evaluation, selection, crossover, mutation, replacement) are repeated until a given stop criterion is met. The EA finally returns an archive of R 1 built over generations. The evolutionary algorithm used is detailed in [START_REF] Abdou | Optimizing communications in vehicular ad hoc networks using evolutionary computation and simulation[END_REF] where we presented our first results in a smaller homogeneous network based on a less in depth search space.

Detection of the neighborhood density

Through communications in the network, each node builds a local view of its neighborhood. This view is mainly based on the number of different neighbors repeating the same packet. To this end, each node keeps a history of the number of neighbors it overhear repeating each packet. Whenever a node receives a packet for the first time, it saves the packet's identifier and set the number of sources for this packet to 1. This number is incremented each time a copy of this packet is received for the first time from a neighbor. This allows to observe the evolution of communications over time. It should be noted that multiple repetitions by a single source do not increment the number of sources. In order to both save the mobile nodes memory and keep information up-to-date, the packets sources history has limited size and older information are discarded.

The actual number of neighbors, denoted ngh is an average computed from the number of neighbors that sent the packets received in the recent history.

In this paper each node uses a simple and passive algorithm to evaluate the actual number of neighbors. As we focus on applications in which information messages are generated regularly, we can manage without active "hello" messages.

Choice of the dissemination strategy

For the implementation of the Smart-flooding, several density levels have been studied using the optimization approach described in Section 3.2. An average number of neighbors corresponds to every neighborhood density. For each density level a combination of input parameters (P , N r, Dr and T T L) is proposed by the optimization tool. The nodes have a matching table between the network density (number of neighbors) and the strategy to use (values of the input parameters). After each update of ngh, each node chooses the dissemination strategy which is the most appropriate for its environment.

However when the packet reception history is empty, the node has no information about the network density. Thus, it intends to send packets it should use a special strategy called "initialization strategy". The latter consists of:

1. sending the packet; 2. waiting for a time period t and then controlling the average number of neighbors (ngh) 3. adjusting the communication strategy based on ngh 4. waiting for a time period t then refining the dissemination strategy depending on the new value of ngh 4 Experiments

Validation of the EA

The Elitist Simulated Binary Evolutionary Algorithm (ESBEA) [START_REF] Abdou | Using an evolutionary algorithm to optimize the broadcasting methods in mobile ad hoc networks[END_REF] is used for the following experiments. ESBEA is first compared with three EAs found in literature: two well-known EAs (NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF] and SPEA2 [START_REF] Zitzler | Spea2: Improving the strength pareto evolutionary algorithm[END_REF]) and a more recent one (DECMOSA-SQP [START_REF] Zamuda | Differential evolution with self-adaptation and local search for constrained multiobjective optimization[END_REF]). The four algorithms are compared using the CEC 2009 competition procedure on two constrained multi-objective problems proposed in this competition (constrained problems 1 & 2) [START_REF] Zhang | Multiobjective optimization test instances for the cec 2009 special session and competition[END_REF]. As shown by the results presented in [START_REF] Abdou | Using an evolutionary algorithm to optimize the broadcasting methods in mobile ad hoc networks[END_REF], ESBEA provides positive gains for the comparison when using the Inverted Generational Distance (IGD) metrics recommended in CEC 2009 competition.

Experimental procedure

The proposed broadcasting protocol is compared with Simple Flooding (which is known as the reference method for broadcasting problems in MANETs) and two probabilistic methods with probability values respectively equal to 0.6 and 0.8. These four broadcasting methods are initially evaluated in homogeneous density networks. The simulated networks are Vehicular Ad hoc Networks (VANETs).

VANETs can enhance safety on the roads by communicating traffic information, accidents, bypass, etc. In the remainder of this section, we evaluate the behavior of the broadcasting methods when a vehicle sends a warning message. It is obvious that, under such circumstances, it is essential to spread the message as quickly as possible and most importantly, the message must reach as many vehicles as possible in the vicinity of the transmitter. The experiments were carried out using the ns-2 network simulator (ns-2.34). We had to be careful concerning the simulation models because the radio environment has a very strong impact on communications, especially in the very hostile VANET context. We chose to use the Shadowing Pattern [START_REF] Dhoutaut | Impact of radio propagation models in vehicular ad hoc networks simulations[END_REF] propagation model which is a realistic and probabilistic model based on outside monitored communications and it is well suited for our needs. It can produce particularly realistic statistical errors distributions, but it is still computationally easy enough to be carried out on medium to large simulations. Radio communications can be impacted among others by the topography, the buildings, the cars and vehicles passing by, the presence of trees, other radio communications, antenna design and even the weather. Shadowing Pattern does not aim at exhaustively simulating all the complex occurring phenomena. Instead it makes use of experimental calibration to exhibit a global statistical behavior much closer to reality than that of a more realistic but partial model.

-We conducted experiments and made use of Vanet Data Representation (VDR), a software we developed in order to make the analysis of the massive amount of real data collected easier. As shown on Figure 2, VDR displays on a single window various configurable metrics along with the context presented as a dynamic map and even video when available.

Tests in homogeneous networks

For experiments in a homogeneous context, we considered four levels of neighborhood densities. For each network, we built a chain topology that illustrates cars lined up on 10 km. We varied the distance between two consecutive vehicles to regulate the density as mentioned in Table 2. In medium density context, each message may be received by tenths of nodes. Low density topology is similar to a highway network: each vehicle is able to communicate regularly with a dozen peers, but more occasionally packets are received by vehicles up to a few thousand meters away (as observed in real experiments).

The fourth considered density level (very low-density network) represents a collection of vehicles in a rural area where traffic generally flows steadily. A vehicle might have no neighbor in its coverage area. To simulate such a sparse vehicule distribution, the Shadowing Pattern propagation model has been set so that it mimics the very intermittent presence of neighbors. Thus a given vehicle can communicate only periodically. For this density level the total of communicating periods is about 20% of the simulation time for each vehicle (during the remaining time, the vehicle is considered to be without any neighbor).

For these various density levels, the evolutionary algorithm returned a set of solutions (those in the first Pareto front) [START_REF] Abdou | Optimizing communications in vehicular ad hoc networks using evolutionary computation and simulation[END_REF]. We then sorted the best solutions in order to select the one that offered the best balance between the reachability and saturation of the channel. These results are presented in Table 3.

The average propagation time as well as the average number of collisions only concerns the runs of simulations that have covered the whole study area (among the 500 runs). For very low density networks, the simple flooding and the other probabilistic methods are not applicable. They have almost zero probability of spreading a message to all the nodes over a distance of 10km. Thus, figures 3 to 5 provide no result for those methods in very sparse networks.

Figure 3 compares the considered broadcasting methods with respect to the full reception ratio. That is the probability for those techniques to ensure a complete coverage of the study area. In high density networks, the four methods ensure complete coverage of the study area. However, when the network density decreases, the quality of results provided by the Simple flooding and two probabilistic methods degrade. In such networks, ensuring a wide dissemination of messages depends on the number of times the relays repeat the packets. When this number is low (equal to 1 for example), packet reception ratio decreases gradually as they propagate and communication eventually stops. This phenomenon is particularly noticeable for networks with very low density. These results show that when a vehicle has about 20% of chance to have a neighbor that receives its packets, the message must be repeated twenty times (see Table 3).

For full coverage in low-density or very low-density networks, Smart-flooding advocates to resend packets several times. The protocol assumes that collisions or distance between the source and the destination may cause an interruption of the broadcast. The message will reach all nodes after a new issue. The histogram in Figure 4 illustrates this by the relatively high propagation delay of the Smart-flooding in the low density levels. We conclude that the total coverage of the network is at the expense of dissemination speed. In dense or very dense environments, the propagation time of the different broadcasting methods are equivalent. This reflects the fact that in such cases, the first front of broadcast (N r = 1) enables the dissemination of the emergency message throughout the study area. As expected, the number of collisions decreases with network density (Figure 5). The difference between the four broadcasting methods is slight. Even when Smart-flooding repeats packets more than once, it regulates the broadcast using good P and Dr values.

Tests in a heterogeneous network

The density of VANETs is not generally homogeneous. In a urban environment for example, the density is not the same at a downtown and on the outskirts of the city. The network topology depicted in Figure 7 is used to compare the four broadcasting methods. This network is composed of three main levels of density: low-density, medium-density and high density. The results of experiments in the heterogeneous network are shown in Figure 6. The warning message is sent by the rightmost node of Figure 7. The strategy used by Smart-flooding slightly slow down the spread of the message when it reaches the high density area to avoid a too high number of collisions. Collisions may prevent a wide dissemination of the message. Thus, Smart-flooding tolerates the first broadcasting front fail. It also allows nodes retransmit packets twice (N r = 2) in very dense environments. This redundancy allows wide dissemination of the message, even if it causes a slightly greater delay than the three other gossip methods (order of a few hundredths of seconds). Please note that this redundancy has no impact on the saturation of the channel since Smartflooding uses low probabilities for very high density network (see Table 3). This is also illustrated by a collision rate significantly lower than for other methods. When considering the third criterion of comparison, the simple flooding and the other two probabilistic methods do not provide full coverage of the network. Their coverage is between 57% and 90% whereas Smart-flooding covers the whole network. The purpose of this experiment was to evaluate the behavior of broadcasting protocols in a heterogeneous environment. The goal is to transmit the message quickly and to make it reach all nodes in the studied area. The slight difference of propagation time does not diminish the Smart-flooding results. The difference with the results of other protocols is only a few hundredths of seconds.

conclusion

A new broadcasting protocol for MANETs (Smart-flooding) is proposed in this paper. Its parameters are determined by an evolutionary algorithm. Smartflooding is compared to three other probabilistic methods on a sending emergency message problem in a VANET with low, medium and high densities. This comparative study shows that Smart-flooding covers the whole network while other methods have a lower coverage probability (from 57% to 90% coverage) for the same network. The average number of collisions and the average time of propagation remain almost equivalent for the four methods, except that the propagation time increases to about 14 seconds in very low-density. But in this case, Smart-flooding manages to spread the warning message to all nodes, while other methods fail. The two main prospects of this work are to extend this protocol to dynamic multi-radio networks, and integrate a criterion of minimizing energy consumption in order to define the best compromise between performance and longevity of the network.

Fig. 1 :

 1 Fig. 1: Flow chart of the optimization tool

Fig. 2 :

 2 Fig. 2: Vanet Data Representation (VDR) -a tool to analyse real world experiments and to calibrate the Shadowing Pattern radio propagation model

Fig. 4 :

 4 Fig. 4: Average propagation time

Fig. 5 :

 5 Fig. 5: Average number of collisions Fig. 6: Heterogeneous network results

Fig. 7 :

 7 Fig. 7: Heterogeneous network topology

Table 1 :

 1 Variation ranges of decision variables

		Dr (in seconds)	T T L
	Lower bound	0 1 0	10
	Upper bound	1 30 2	40

Table 2 :

 2 Network densities

	Density	Inter-	Number	Density P	N r Dr	(in	T T L
	level	vehicle	of nodes			seconds)
		distance		Very low 0.9999852 21.0 0.5588954 20.0
	High	25 m	400	Low	0.9158122 2.0 0.7285401 28.0
	Medium 75 m	134	Medium 0.7755884 1.0 1.5412072 26.0
	Low	200 m	50	High	0.3591064 2.0 0.6757185 18.0

Table 3 :

 3 Smart-flooding solutions

		100	P=0.6		14.153	P=0.6
			P=0.8			P=0.8
	Full reception ratio (%)	20 40 60 80	Simple Flooding Smart-flooding	Propagation time (s)	0.05 0.1 0.15	Simple Flooding Smart-flooding
		0			0
			H ig h -d e n s it y M e d iu m -d e n s it y L o w -d e n s it y V e r y -lo w -d e n s it y			H ig h -d e n s it y	M e d iu m -d e n s it y	L o w -d e n s it y	V e r y -lo w -d e n s it y
			Neighborhood density				Neighborhood density
			Fig. 3: Full Reception Ratio

This notion of determinism concerns only the decisions of the broadcast but not the channel access (layer

2) which may be based on random methods.

Acknowledgement

We thank Samuel Buendia for his participation in the project that led to the development of Vanet Data Representation (VDR) at the Computer Science Laboratory of the University of Franche-Comté.


Rohit Babbar

Ioannis Partalas

Eric Gaussier

Reza Amini

Maximum-margin Framework for Training Data Synchronization in Large-scale Hierarchical Classification

In the context of supervised learning, the training data for large-scale hierarchical classification consist of (i) a set of input-output pairs, and (ii) a hierarchy structure defining parent-child relation among class labels. It is often the case that the hierarchy structure given a-priori is not optimal for achieving high classification accuracy. This is especially true for web-taxonomies such as Yahoo! directory which consist of tens of thousand of classes. Furthermore, an important goal of hierarchy design is to render better navigability and browsing. In this work, we propose a maximum-margin framework for automatically adapting the given hierarchy by using the set of input-output pairs to yield a new hierarchy. The proposed method is not only theoretically justified but also provides a more principled approach for hierarchy flattening techniques proposed earlier, which are ad-hoc and empirical in nature. The empirical results on publicly available large-scale datasets demonstrate that classification with new hierarchy leads to better or comparable generalization performance than the hierarchy flattening techniques.

Introduction

Large-scale web taxonomies, e.g. the Open Directory Project (ODP), consist of millions of websites, distributed among hundreds of thousand classes which are arranged in a tree hierarchy. For example, ODP has around 5 million websites and the hierarchy contains over 1 million classes. Due to the ever-increasing scale of data from various sources on the web, there is a definite requirement to partially or fully eliminate the manual effort involved in managing such taxonomies. In this context, large-scale hierarchical classification systems aim to automatically classify documents to target classes using also the hierarchical information. The main challenge in large-scale hierarchical classification is to exploit the hierarchical structure to design a scalable classification system which has acceptable prediction accuracy as well as training and prediction speed. In order to evaluate the current state of art in this domain, open challenges such as the Pascal Large Scale Hierarchical Text Classification (LSHTC)1 have been organized.

Most approaches exploit the hierarchy structure to design appropriate loss functions for classification and use it to apply the divide-and-conquer paradigm to keep the scale of the classification problem manageable. However, the taxonomy structure given a-priori as part of the training data may not be best suited to yield high classification accuracy due to the following reasons:

1. Large-scale web taxonomies are designed with an intent of better userexperience and navigability, and not for the goal of classification. 2. Taxonomy design is subject to certain degree of arbitrariness based on personal choices and preferences of the editors. 3. The large-scale nature of such taxonomies poses difficulties in manually designing good taxonomies for classification.

In the recent work by [START_REF] Dekel | Distribution-calibrated hierarchical classification[END_REF] on relatively smaller taxonomies, the impact of arbitrariness on loss-function design is minimized by appropriately calibrating the edge distance between the true and predicted class. In similar spirit of taxonomy adaptation, approaches based on flattening the hierarchy such as [START_REF] Malik | Improving hierarchical svms by hierarchy flattening and lazy classification[END_REF][START_REF] Wang | Flatten hierarchies for large-scale hierarchical text categorization[END_REF], have been proposed in LSHTC for large-scale settings which lead to improvement in classification accuracy as compared to using the original hierarchy. The motivation for these hierarchy flattening approaches is to minimize the error propagation due to a longer cascade from the root to leaves. Hierarchy flattening approaches remove entire levels in the hierarchy by replacing all the parents in that level by its children. This is illustrated in Figure 1 where the first and the third levels of the hierarchy are removed. Such approaches based on flattening entire levels suffer from the following drawbacks:

-These are based on ad-hoc heuristics and a-priori it is not clear which levels in the hierarchy should be flattened. This is crucial for hierarchies such as Yahoo! Directory which have more than 10 levels. -Excessive flattening leads to increase in training and prediction speed, both of these factors adversely impact applicability of the resulting hierarchical classifiers in many scenarios of practical importance.

In order to tackle the incompatibility of the given hierarchy structure among target classes and the set of input-output pairs in large-scale hierarchical classification, we propose a principled strategy for adapting the hierarchy to better suit the classification problem at hand.

Our Contributions

In this work, we present a margin-based framework for choosing the most appropriate candidate nodes for replacement by their children nodes rather than all the nodes in a level. The proposed approach for taxonomy adaptation is based on well-founded theoretical results for generalization error analysis of marginbased classifiers deployed in a tree-based top down cascade [START_REF] Gao | Discriminative learning of relaxed hierarchy for large-scale visual recognition[END_REF]. The replacement is performed only for those classes which are more likely to be confused with other classes at the same level in the hierarchy. We exploit the margin information obtained at optimality while training the one-vs-rest classifiers to determine the extent of confusion for each candidate class. This approach can be seen as synchronization of the two components of training data, taxonomy information on one hand and the set of input-output pairs on the other hand.

The proposed method is based on a more principled approach for node replacement as compared to ad-hoc methods based on flattening entire layers. As a result, our method is easily applicable to taxonomy structures in which the cascade length is arbitrarily long. Another advantage of our approach is that by choosing the most relevant candidates for replacement, it limits the extent of flattening and maintains the over-all hierarchical structure.

Other Related Work

Some of the earlier studies on exploiting hierarchy among target classes for the purpose of text classification, such as [START_REF] Cai | Hierarchical document categorization with support vector machines[END_REF][START_REF] Dekel | Large margin hierarchical classification[END_REF], in which the number of target classes were limited to a few hundreds. However, the work by [START_REF] Liu | Support vector machines classification with a very large-scale taxonomy[END_REF] is among the pioneering in hierarchical classification towards addressing Web-scale directories such as Yahoo! directory consisting of over 100,000 target classes. The authors analyze the performance with respect to accuracy and training time complexity for flat and hierarchical classification. More recently, prevention of error propagation by applying Refined Experts trained on a validation set was proposed in [START_REF] Bennett | Refined experts: improving classification in large taxonomies[END_REF]. In this approach, bottom-up information propagation is performed by utilizing the output of the lower level classifiers in order to improve classification at top level. Deep Classification [START_REF] Xue | Deep classification in large-scale text hierarchies[END_REF] proposes to first identify a much smaller subset of target classes. Prediction of a test instance is then performed by re-training Naive Bayes classifier on the subset of target classes identified from the first step.

Problem Setup

In single-label multi-class hierarchical classification, the training data can be represented by a set of input-output pairs S = {(x (i) , y (i) )} N i=1 and hierarchical structure among target classes G. In the context of text classification, x (i) ∈ X denotes the vector representation of document i in the input space X ⊆ R d . Assuming that there are K classes denoted by the set Y = {1 . . . K}, the label y (i) ∈ Y represents the class associated with the instance x (i) . The hierarchy in the form of rooted tree is given by G = (V, E) where V ⊇ Y denotes the set of nodes of G, and E denotes the set of edges with parent-to-child orientation. Let v 0 ∈ V denote the root node of the hierarchy tree. In this setup, the leaves of the tree which form the set of target classes, which is given by Y = {u ∈ V : ∄v ∈ V, (u, v) ∈ E}. Since the class hierarchy represents a transition from general to specialization of a concept as one traverses from root towards leaves, the documents which belong a particular leaf node also belong to all the nodes on the path from the root to that lead node.

In the above setup, given a new test instance x, the goal is to predict the class y. This is done by making a sequence of predictions iteratively in a top-down fashion starting from the root until a leaf node is reached. At each non-leaf node v ∈ V, a score f c (x) ∈ R is computed for each child c and the child c with the maximum score is predicted i.e. c = argmax

c:(v,c)∈E f c (x).
In addition to being highly accurate for prediction, we also focus on prediction speed, which are two seemingly contradicting design requirements for a machine learning algorithm.

The motivation of approaches based on layer flattening such as [START_REF] Malik | Improving hierarchical svms by hierarchy flattening and lazy classification[END_REF][START_REF] Wang | Flatten hierarchies for large-scale hierarchical text categorization[END_REF] illustrated in Figure 1 is that by reducing the length of the cascade, the extent of propagation error can be reduced. However, these approaches lead to multiple folds increase in training time as shown in [START_REF] Wang | Flatten hierarchies for large-scale hierarchical text categorization[END_REF]. Prediction speed also suffers by employing excessive flattening as studied in the work by [START_REF] Liu | Support vector machines classification with a very large-scale taxonomy[END_REF] showing that the space complexity of a flat classifier is much higher than a hierarchical model. Moreover, for predicting an unseen test instance in a K class problem, one needs to evaluate O(K) classifiers in flat classification as against O(log K) classifiers in a top-down manner. In order to achieve a better trade-off among various metrics of interest in large-scale hierarchical classification, we next propose a technique for hierarchy adaptation which not only provides comparable or better performance to level flattening techniques but also maintains the overall hierarchical structure to enjoy faster training and prediction speed.

Taxonomy Adaptation in Large-scale Hierarchical Classification

In this section, we propose a principled approach to adapt the taxonomy given a-priori as part of the training data by using the input-output pairs to output a taxonomy which leads to better accuracy. For our analysis, we focus on L2-regularized L2-loss linear Support Vector Machine (SVM), wherein the decision function f c (x) is modeled as a linear classifier such that f c (x) = w T c x. To learn an SVM-based discriminative classifier for node v, we solve the following optimization problem for each child c of v

f * c = min wc   1 2 w c T w c + C {i:y (i) ∈Lv} (max(0, 1 -sgn(y (i) • L c )w c T x (i) )) 2   (1)
where L v denotes the set of leaves in the subtree rooted at node v and C denotes the parameter for mis-classification penalty. We focus on one-vs-rest technique to tackle the multi-class nature of the classification problem of identifying the most relevant child c of parent node v and hence y i and L c are related such that sgn(y

(i) • L c ) = +1 if y (i) ∈ L c -1 otherwise

Margin-based approach to Taxonomy Adaptation

We derive our intuition from the recently proposed result 2 on the generalization error of maximum-margin classifiers deployed in the tree structure which can be stated as follows:

Theorem 1. [START_REF] Gao | Discriminative learning of relaxed hierarchy for large-scale visual recognition[END_REF] Let m random input-output pairs are correctly classified using G containing |V| decision nodes with margins {γ j , ∀j ∈ G}, then the generalization error, with probability greater than 1 -δ, is less than

130R 2 m (D ′ log(4em)log(4m) + |V|log(2m) -log( 2 δ ))
where

D ′ = |V| j 1 γ 2 j
and R is the radius of the ball containing the distribution's support.

Though the above result is stated for the separable case, it indicates that in order to achieve better generalizability, one needs to decrease the quantity D ′ . Clearly, this quantity can be reduced if one removes those nodes from the tree which correspond to lower margin. The decision nodes with lower margin correspond to those classification problems which are relatively harder as compared to those nodes at which higher margin can be achieved. This is illustrated in Figure 2, in which not all nodes at a layer are replaced by their children but only those for which the margin is among the lowest. This strategy essentially lead to reducing the effective VC dimension or the Rademacher complexity of the overall hierarchical classifier and leading to a reduction in the generalization error in accordance with the Theorem 1.

Since we deal with the non-separable case, we need to remove those nodes for which the inverse of the margin and empirical error are jointly maximum. This quantity is captured for each decision node c ∈ {V/v 0 } by the optimal value obtained from the objective function value f * c as given in Equation 1. For each parent node v ∈ V, we consider the respective value of f * c ∀c ∈ V, (v, c) ∈ E for each child c of v. The values f * c are sorted in decreasing order, which represents the preferential ordering of the nodes to be considered for flattening. Top rranked nodes are flattened for which f * c is among the highest, where r is chosen based on the distribution of these values. Typically, the value f * c is larger for a node which has more documents assigned to the leaves of the sub-tree rooted at that node, node sizes are taken into account in choosing the top r candidate nodes for replacement. Once the difference between the f * c values of the current 2 The theorem can be found in the supplementary material of [START_REF] Gao | Discriminative learning of relaxed hierarchy for large-scale visual recognition[END_REF].

and next candidate child node is more than the previous difference, the flattening procedure for the current parent node is stopped. This process is repeated for all the parent nodes in the hierarchy irrespective of the length of the cascade. The algorithmic depiction of the procedure is shown in Algorithm 1. Note that the value of parameter C does not significantly affect the ordering of the nodes pruned by the proposed algorithm. Since the algorithm maintains the overall hierarchy structure, it benefits from the properties of low space complexity and faster prediction, as we demonstrate in the next section. It was also observed that the resulting hierarchy after applying the transformation as given by the algorithm leads to more balanced classification problems at various levels.

Algorithm 1 The proposed comparative evaluation procedure.

Require: a hierarchy G, input-output set S Train L2-regularized,L2-loss SVM in a top-down manner gap ← 0 for v ∈ V do Sort the child nodes in decreasing order of f * c taking into account the class sizes Flatten 1st and 2nd ranked child nodes, say c1 and c2 gap We compare four strategies to evaluate their impact on classification accuracy : (i) Fully Hierarchical (FH) technique which uses the original hierarchy, (ii) Top Level Flattening (TLF) by removing the first layer, (iii) Multiple Level Flattening by removing first and third levels (MLF) as proposed in [START_REF] Malik | Improving hierarchical svms by hierarchy flattening and lazy classification[END_REF][START_REF] Wang | Flatten hierarchies for large-scale hierarchical text categorization[END_REF] and (iv) the proposed Margin-based strategy for Taxonomy Adaptation (MTA). We do not compare with our previous work on adaptive classifier selection in large-scale hierarchical classification [START_REF] Partalas | Adaptive classifier selection in large-scale hierarchical classification[END_REF], since the accuracy results using that approach were marginally better than FH method. We use Liblinear to train the models for L2-regularized L2-loss support vector classification. In order to maintain consistency, the value of the penalty parameter C was fixed to 1, for all the four methods.

= f * c 1 -f * c 2 cprev ← c2 ⊲ Set the previous flattened node to c2 for c ∈ V -{c1, c2}, (v, c) ∈ E do if f * cprev -f * c < gap then Flatten c gap ← f * cprev -f * c cprev ← c ⊲ Set
As shown in Figure 3, the proposed method MTA achieves comparable or better accuracy as compared to the entire layer flattening techniques, MLF and TLF. The s-test [START_REF] Yang | A re-examination of text categorization methods[END_REF] (p < 0.001) showed statistical differences of MTA over FH and TLF. Table 2 presents the comparison on DMOZ-1 dataset for training time (including re-training), model sizes and prediction speed. Clearly, since the proposed MTA method preserves the overall hierarchical structure of the taxonomy it achieves better values for these metrics of practical significance.

Conclusion

We presented a principled method for automatically adapting the given hierarchy of classes, in large scale hierarchical classification, to output a new hierarchy which leads to better generalization. The proposed approach is backed by wellfounded theoretical insights and exploits the margin information to identify those decision nodes in the hierarchy which correspond to relatively harder classification problems and removing those nodes to minimize the impact of propagation of error. Not only does it lead to comparable or better accuracy, but enjoys favourable training and prediction speed. This approach can be viewed as an instance of a more general paradigm of making the two parts of the input in a supervised learning problem more compatible.

Fig. 1 .

 1 Fig. 1. Flattening the first and the third levels (right) of the original hierarchy (left).

Fig. 2 .

 2 Fig. 2. Partial flattening (right) of the original hierarchy (left) for the proposed method.

Fig. 3 .

 3 Fig. 3. Accuracy Comparison.PropertiesMLF MTA Tr. Time (in hours) 6.3 3.2 Tr. Model Size (in GB) 7.8 4.2 Pred. Time (in mins) 55 17

Table 1 .

 1 Dataset Properties

	4 Experiments and Results
	We use the publicly available DMOZ
	data set(excluding the validation set)
	from the LSHTC 2010 (DMOZ-1) and a subset of DMOZ from the LSHTC 2011 (DMOZ-2). The datasets, after having been pre-processed by stemming and stopword removal, appear in the LibSVM for-	Properties Tr. Set Size Feature Set Size Target Classes Test Set Size	DMOZ-1 DMOZ-2 93,805 36,834 347,255 155,641 12,294 3,672 34,880 36,834
	mat. Table 1 presents the numeric val-
	ues corresponding to the important
	properties of the dataset.

Table 2 .

 2 Comparison of MLF and MTA Training Time, Model size on hard-disk and Prediction Time for the DMOZ-1 dataset

http://lshtc.iit.demokritos.gr/

Acknowledgments

This work was partly supported by the French National Research Agency (ANR), Class-Y project (ANR-10-BLAN-0211), and by the European Commission (EC), BioASQ project (FP7/2007-2013, ICT-2011.4.4(d)). The views expressed by the authors in this paper represent their own.