Abderrezak Rachedi
email: rachedi@univ-mlv.fr

Hend Baklouti

Gaspard Monge

muDog: Smart Monitoring Mechanism for Wireless Sensor Networks based on IEEE 802.15.4 MAC

Keywords:

    muDog: Smart monitoring mechanism for wireless sensor networks based on IEEE 802.15.4 MAC

I. INTRODUCTION

Wireless Sensor Networks (WSNs) attract more and more researchers and industrialists because of their potential reliability, accuracy, flexibility, cheapness and easy deployment. In addition, the WSNs application is wide: natural environment monitoring (fire detection, pollution, earthquake, etc.), ecosystem tracking, healthcare, security (videosurveillance, objects tracking, etc.) and military (battlefield monitoring, objects localization, etc.).

One of the main constraints of these networks is energy limitation due to their small size and wire independance. This constraint must be taken into account in any protocol design and sensor network deployment. The energy limitation creates vulnerabilities that are exploited by attackers. There are two kinds of attacks: passive (like traffic analysis and selfish behavior) and active (like false routing information injection and impersonation). The impact of passive attacks on the network is not negligible compared to the impact of active attacks. Propose a solution to counter passive attacks is a real challenge.

In this work, we focus on passive attacks and propose a new analytical model in order to monitor and detect selfish behav-ior particularly non-cooperative nodes. The existing solution called Watchdog mechanism is proposed for Mobile Ad-hoc Networks (MANETs), but is not adapted to WSNs [START_REF] Marti | Mitigating routing misbehavior in mobile ad hoc networks[END_REF]. Our proposed solution called muDog is a monitoring mechanism based on MAC IEEE802.15.4 beacon-enabled technology and aims at improving the monitoring quality while minimizing the energy cost. The monitoring mechanism is a set of actions allowing specific sensor nodes to monitor the behavior of the other sensor nodes. This mechanism allows to evaluate monitored nodes and update the trust metrics. For example, muDog mechanism is able to detect the origin of packets loss at the routing nodes which do not cooperate and choose a selfish behavior. This malicious behavior consists in keeping their energy only for their own packets transmission in order to reduce the energy they consume when cooperating. The MAC IEEE802.15.4 beacon-enabled mode standard [2] is used to reduce the energy consumption in WSNs through a sleep/wakeup mechanism [START_REF] Keshavarzian | Wakeup Scheduling in Wireless Sensor Networks[END_REF]. As far as we know, there is no monitoring mechanism adapted to this standard. Therefore, the main goal of this work is to propose a new efficient and optimal analytical model allowing to monitor the network while minimizing the energy consumption. Moreover, the cost of the monitoring mechanism is analyzed in terms of energy consumption and the quality of detection is evaluated by using as metric the probability of monitor correct observation. The impact of nodes density, packets' size, network traffic load: saturated/unsaturated cases and distance between monitor and monitored nodes are taken into account in our evaluation. The obtained results illustrate that muDog is more efficient than Watchdog whatever the parameter is.

This paper is organized as follows: in section 2, we briefly present the MAC IEEE802.15.4 beacon-enabled mode standard and the summary of the existing works related to energy aware and monitoring mechanisms. Section 3 is dedicated to the proposed analytical model and muDog mechanism. The fourth section presents the obtained results and their analysis. Finally, section 5 concludes the paper and presents our future works.

II. RELATED WORK

In this section, we briefly present MAC IEEE802.15.4 beacon-enabled mode and the existing monitoring mechanisms.

A. MAC IEEE 802.15.4

The MAC IEEE802.15.4 has two working modes: nonbeacon-enabled mode and beacon-enabled mode [2]. The nonbeacon-enabled mode is based on non-slotted CSMA/CA and there is no time link between backoff period and beacon. In this mode the coordinator node always stays in active Idle listening. However, the beacon-enabled mode is based on slotted CSMA/CA and when the beacon starts each node launches its backoff period. The communication between nodes is controlled by the network coordinator which transmits beacons at regular intervals (Beacon Interval) in order to synchronize the sensors. The nodes use the sleep/wakeup mechanism: they have to wake up in order to receive the coordinator's beacon. The coordinator is in charge of the data routing in the network. When they receive a beacon all nodes know the superframe duration (coordinator's activity period) and the time when they can transmit data or sleep. The advantages of this mechanism are the possibility for the coordinator to communicate with all nodes in activity periods and the reduction of energy consumption when the coordinator and nodes are inactive. The structure of the superframe is presented in figure 1. It is composed of an active and an inactive period. The active period has 16 slots divided into 3 parts: beacon, CAP (Contention Access Period) and CFP (Contention Free Period). The beacon is transmitted at slot zero without using CSMA/CA and then the CAP period starts.

The size of both activity and inactivity periods is calculated according to the Beacon Order (BO) and the Superframe Order (SO). The following equations illustrate how to calculate the BI (Beacon Interval) and the SD (Superframe Duration).

BI = aBaseSlotDuration × aN umSuperf rameSlots × 2 BO ; SD = aBaseSlotDuration × aN umSuperf rameSlots × 2 SO
where aBaseSlotDuration is the symboles which form the superframe when SO = 0. aNumSuperframeSlots is the number of slots in the superframe.

The relation between BO and SO is: 0 ≤ SO ≤ BO ≤ 14. When the BO = 15 the network is in non-beacon-enabled mode.

The CFP uses the Scheduled TDMA mechanism like GTS (Guaranteed Timeslot) for the network traffic with QoS requirements.

There are three manners to send data in MAC IEEE802.15.4: direct transmission, indirect transmission and GTS transmission. In this work, we focus on the direct transmission.

B. Energy aware mechanisms

The MAC layer has an important role to reduce the energy consumption. It is divided into four classes [14]: the consumption related to control packets, collision, Idle listening and overhearing.

Several mechanisms are proposed to tackle the energy consumption problem in WSNs including the duty cycling [12]. This mechanism aims at saving energy by using sleep/wakeup technic which consists in activating the transmitter radio when the node has a packet to transmit and switch it off when there is no packet to transmit. The duty cycling needs cooperative nodes in order to coordinate the sleep/wakeup periods. This coordination is ensured by the sleep/wakeup scheduling distributed algorithm. The duty cycle in IEEE 802.15.4 is parametered by the cordinator which selects the SO and BO parameters. However, this mechanism reduces the bandwith and increases the delay. The study presented in [15] shows that the energy consumption decreases linearly with the size of received/transmitted packets. Unlike IEEE 802.11 in IEEE 802.15.4 the energy consumption at packet reception is more important than at the transmission packet. That's why in our proposed model, we focus on the overhearing time to evaluate the energy consumption at the monitor node.

There are three categories of sleep/wakeup protocols: the on demand protocol (the node wakes up only when another node wants to communicate with it), the scheduled Rendezvous protocol (the nodes wake up periodically at different moments in order to avoid a collision) and the asynchronous scheme protocol (each node wakes up independently without synchronisation needs).

Many MAC protocols based on CSMA and TDMA mechanims are proposed to save energy in WSNs like S-MAC, TRAMA and Z-MAC [14]. Suh et al. [START_REF] Suh | KO Design and implementation of enhanced IEEE 802.15.4 for supporting multimedia service in Wireless Sensor Networks[END_REF] proposed an enhancement of IEEE 802.15.4 called TEA-15.4 which consists in increasing the bandwidth and reducing the energy cost by adapting the Beacon Interval according to the kind of traffic. This solution is hybrid (beacon-enabled and beaconnon-enabled modes). However, its implementation is complex.

C. Monitoring mechanisms

The monitoring mechanism is defined as the set of actions that are useful to observe the nodes' behavior. The monitoring mechanism plays a major role in the evaluation of the nodes' reputation and in the updating of the nodes' trust level. It deals with some issues that have a negative impact, particularly on the monitoring mechanism, when a collision occurs at the monitor node during the monitoring process. This situation significantly increases the false positive rate. In fact, the presence of non-cooperative nodes can affect the network in a negative way.

Many research works were dealing with monitoring mechanisms in IEEE 802.11. Watchdog [START_REF] Marti | Mitigating routing misbehavior in mobile ad hoc networks[END_REF] is a monitoring mechanism based on packets' forwarding to detect the nonforwarding nodes. It takes into account the routing layer but does not consider the physical and MAC level's parameters. It consists in listening to the traffic between monitor node's neighbors and detecting if the monitored nodes forward the packets in routing operations. The monitor node does not check at the routing layer if the monitored node has correctly received the packet. Thus, the ratio of false positives (false alarms) is high. To reduce the ratio of false positives, we proposed in our previous work [START_REF] Rachedi | Toward a cross-layer monitoring process for mobile for mobile ad hoc networks[END_REF] the enhancement of the monitoring mechanism while taking into account the cases of monitor's misobservation related to monitor/monitored collision. The cross-layer approach is selected in order to increase the probability to have an accurate monitor's observation. However, this solution cannot be directly applied to WSNs and particularly the IEEE 802.15.4. As far as we know there is no work focusing on the monitoring mechanism in IEEE 802.15.4. That is why in this paper, we deal with the monitoring mechanism called muDog in order to detect the non-cooperative nodes in beacon-enabled IEEE 802.15.4.

III. MUDOG: MONITORING MODEL

The monitoring mechanism muDog has as objective the improvement of the monitor's observation quality with a minimum of energy consumption. The monitoring process in beacon-enabled IEEE 802.15.4 is activated only in CAP (Contention Access Period) period. That means that the monitor node wakes up to receive the beacon frame and to track the packets transmitted by the monitroed node in the CAP duration in order to evaluate the cooperative metric of this node. The main objective of muDog is to reduce the time of overhearing and then the energy consumption by launching a targeted monitoring. We explain the monitoring process of muDog by an example illustrated in figure 2. In this scenario, we have two connections {S 1 , R 1 } and {S 2 , R 2 }, coordinator node C its task is to route a packet from S 1 to R 1 and from S 2 to R 1 . The node S 1 plays the role of monitor node and its goal is to monitor the coordinator node C. The node C is classified as well-behaving node if it forwads all packets to nodes R 1 and R 2 otherwise it is classified as selfish node. Only nodes S 1 and S 2 can act as monitor nodes and they target the transmission of node C by the overhearing. The flowchart presented in figure 3 describes the muDog mechanism run by the monitor node. The node S 1 sends a packet P kt i to the node R 1 as illustrated in figure 2. When P kt i is received by the node C, then it transmits it to the receiver R 1 under the S 1 monitoring. Two kinds of transmission are possible with and without acknowledgement. Both transmissions are supported by our proposed monitoring mechanism. Let suppose the case of the transmission with acknowledgement. The node S 1 is able to check the good reception of P kt i by the coordinator C when it receives the ACK packet. This reception validates the first step of the monitoring process. The node S 1 acts as monitor node only if both conditions of step 2 in figure 3 are verified: LQI > LQI threshold and P w > P w threshold where LQI (Link Quality Indicator) and P w is the probability to have a monitor node's accurate observation (see below for more details). This step ensures the quality of the monitoring process. We know that in beacon-enabled mode the coordinator sends periodically a beacon frame to its neighbors in order to ensure the synchronization and to give them information related to the next transmission. The monitor node focuses on two important subfields in the beacon frame: Frame Pending (it is set to 1 if the coordinator has a packet to transmit) and Pending address Fields (address list of nodes to which the coordinator has packets to transmit). When these parameters are verified by S 1 that means that Frame Pending Subfield =1 and @R 1 ∈ {Pending address Fields}, then the monitoring process is launched (see step 3). After this step, the node S 1 starts to overhear the packets sent by the node C in order to check if the coordinator correctly forwards the packets particularly P kt i .

The challenge is that the monitor node S 1 cannot know when the targeted packet P kt i will be transmitted during the overhearing period. We know that the overhearing period has an important impact on the energy consumption that's why the proposed mechanism muDog tries to optimize the overhearing period while ensuring the quality of the observation. The maximum time of overhearing does not exceed the time dedicated to CAP (Toverhearing max = T CAP )

A. Evaluation of the monitor overhearing time

In order to evalaute the overhearing time of the monitor node, we distinguish two kinds of transmission with and without acknowledgement. In the case of transmission with acknowledgement, we present two situations: the optimistic and the realistic. The optimistic situation is when the coordinator sends the first monitored packet P kt i to the R 1 which means the monitor node S 1 can switch off the monitoring process just after the overhearing of P kt i . In this situation the overhearing time is equal to the one packet transaction time (T 1 P kt transac ) and it is given by the following equation:

T overhearing = T 1 P kt transac = T backof f (cw j ) + T DataReq +T Data + 2 * γ + 2 * ω + 2 * T Ack + 2 * T IF S (1)
where T backof f is the backoff time calculated according to CSMA/CA [2]. T Data is the time needed to transmit the data frame (Mac Payload Field) and its size cannot exceed aMaxMACPayloadSize. T DataReq is the transmission duration of the data command frame. γ is the Turn around time and presents the duration between the reception of data frame and the transmission of the ACK packet. ω is macAckWaitDuration and consists in the maximum duration necessary to receive the ACK packet after the data frame transmission. T Ack is the transmission time of the ACK packet. T IF S (IFS: InterFrame Space) is the time needed to separate two consecutive data frames.

The pessimistic or realistic situation is when the monitored packet P kt i transmitted after a certain number of packets with different source addresses (like S 2 in the example of figure 2). N P is the number of packets transmitted before P kt i then the time of overhearing will be crossed by N P + 1. In addition, the packet retransmission for any reason must be taken into account and it is limited to only three attempts. Therefore, the overhearing time in this case is calculated as follows:

T overhearing = (N P +1)×( 2 i=0 P i × i+1 j=1 T 1 P kt transac (cw j )) (2)
where P i is the probability to reach i th attempts and it is defined as follows:

P i = P succ (1 -P succ ) i if i = {0, 1} (1 -P succ ) 2 if i = 2
We based on Pollin et al. [START_REF] Pollin | Catthoor Performance Analysis of Slotted Carrier Sense IEEE 802.15.4 Medium Access Layer[END_REF] Markov model to evaluate the probability P succ in IEEE 802.15.4.

P succ = N φ(1 -φ) N -1 (1 -α)(1 -β) ( 3
)
where N is the number of nodes in the network, φ is the stationary probability of node when it attempts CCA (Clear Channel Assessment) for the first time during one slot. α and β are the probabilities to sense the channel busy for the first and the second CCA (in IEEE 802.15.4 the transmitter must sense twice the channel by using CCA). In order to calculate the probability φ, we distinguish two cases: the saturated and unsaturated network.

In the case of saturated network, the node always has a packet to transmit. φ ACK is calculated in the case of a transmission with acknowldgement as follows:

φ ACK = 1 -1 - β ACK (1 -β ACK )(2 -P col ) 1/N (4)
where P col is the probability of collision during the transmission period and it is calculated as follows:

P col = 1 - N φ ACK (1 -φ ACK ) N -1 1 -(1 -φ ACK ) N (5)
In the case of unsaturated network, the node does not always have a packet to transmit. We use the same model developped in [START_REF] Pollin | Catthoor Performance Analysis of Slotted Carrier Sense IEEE 802.15.4 Medium Access Layer[END_REF] which consists in adding the delays X 1 , X 2 and X 3 . X 1 is the delay added after each transmission attempt when the channel is sensed busy. X 2 is the delay added before the next periodic transmission in the case of a transmission failure. X 3 is the delay added after the next transmission in the case of a successful first transmission. So, this model is valid only in the case of acknowledgement transmission, because in the other transmission mode it is not possible for the sender to be sure that the packet is correctly received.

The probability that a collision (P c ) occurs because two nodes transmit at the same time is calculated as follows:

P c = 1 -(1 -φ) N -1 (6)
For more details you can refer to the work [START_REF] Pollin | Catthoor Performance Analysis of Slotted Carrier Sense IEEE 802.15.4 Medium Access Layer[END_REF].

The number of packets sent for each pending address is not specified in the IEEE 802.15.4 standard which makes the evaluation of N P number of packets to send before the monitored packet P kt i not easy. Then, we evaluate the N P min and the N P max in order to calculate the average number of N P (N P moy ). However, in the IEEE 802.15.4 standard the number of addresses pending cannot exceed 7 then the N P min = 6 (one packet to transmit for each address). In order to calculate the N P max , we evaluate the maximum packet number possible to transmit during one CAP and we obtain:

N P max = T CAP T 1P kt transac ( 7
)
where T 1P kt transac is the time transaction for one packet with minimum backoff value.

In the case of the transmission without acknowledgement that means that the turn around time and the macAckWaitDuration are required. Therefore, the equation to calculate the overhearing time in the optimal case is:

T overhearing = T 1 P kt transac = T backof f (cw j ) + T DataReq +T Data + 2 * T IF S (8)
In the realistic case, the equations 1 and 4 become as follows:

T noAck overhearing = N P moy (P 0 × T noAck transac (cw j )) (9)

B. Evaluation of the probability to have a monitor's accurate observation

The quality of the monitoring process consists in the accurate observation of the monitor node. We quote two main conditions to define the accurate observation of the monitor node: the monitored node successfully transmits the target packet (P cond1 ) and no collision occurs at the monitor node during the monitored node transmission (P cond2 ). Let P w represent the probability to have a monitor's correct observation and be calculated as follows:

P w = P cond1 × P cond2 ( 10
)
P cond1 is calculated according to the equation 3 proposed in the previous subsection. However, P cond2 depends on many parameters particularly the distance between the monitor and monitored nodes (d). The distance between monitor and monitored nodes has an impact on the monitor's vulnerable region (M vr(d)) which can affect the monitoring mechanism. This region only exists if the interference region of the monitor node is not covered by the carrier sense region of a monitored node ; we called it "the monitor vulnerable hidden region". If any node in this region starts to transmit, it disturbs the monitor node's observation. For more details about this region and how we can evaluate it, the reader can refer to our previous work [START_REF] Rachedi | Toward a cross-layer monitoring process for mobile for mobile ad hoc networks[END_REF]. Therefore, P cond2 equals one when no node in region M vr(d) transmits in a vulnerable time. This period depends on the transmission time T av of a packet: when a node B starts to transmit at t s , the vulnerable time interval is [t s -T av -1, t s + T av -1]. The nodes distribution is an important parameter, that's why we assume that the nodes are distributed within a topology which is a two-dimensional Poisson process with parameter λ (memoryless property of Poisson distribution). The nodes in region M vr(d) must remain silent during µ slots time where µ = (T av /σ). Region M rv(d) can be equal to zero when it is covered by the carrier sense of the monitored node. Otherwise,

P cond2 (d) (if d > Rs 1+ k √
TSNR ) is given by:

P cond2 (d) = 1 if d ≤ ϕ e -τ N h .µ Otherwise ( 11
)
where N h = λM vr(d) and ϕ = Rs 1+ k √ TSNR with R s is the Carrier sensing range and T SN R is the Threshold Signal to Noise Ratio. Now, we can calculate P w(d) as follows:

P w(d) = P succ if d ≤ ϕ P succ .e -τ N h .µ Otherwise (12)
IV. PERFORMANCE EVALUATION In order to evaluate muDog monitoring mechanism performances, we implement the proposed algorithm and the analytical model by using our own simulator. We evaluate the overhearing time of the monitor node with different network parameters such as: packet size and density of nodes. In addition, the probability of the monitor correct observation P w is evaluated and analyzed according diffrent paramters: traffic load, the density of nodes in the network and the distance between monitor and monitored nodes.

A. The overhearing time evaluation

Two cases have to be distinguished: the case of a saturated network and the case of a non-saturated network. The saturated case is divided into two cases: the acknowledged and nonacknowledged cases.

1) Impact of the number of packets (N P moy ) and the packet size: In order to determine the variation interval of N P moy , we have evaluated N P moy variation according to the x packets size in both cases: with and without any acknowledgement. This evaluation enables us to deduce the average number of packets that may be sent during CAP. The figure 4 shows that the overhearing time increases proportionally to the number of packets preceding the monitored packet and the greatest values are observed in the saturated case with acknowledgement because the packets are more often generated and the transactions are longer than in the non-saturated case. For each acknowledged transmission, the overhearing time remains inferior to the overhearing time in Watchdog. This is true for N P moy < 22 packets in a saturated case and N P moy < 26 packets in a non-saturated case. For instance, for N P moy = 20, the overhearing time is reduced by 9% in a saturated case and by 30% in a non-saturated network. For N P moy > 22 packets and N P moy > 26 packets respectively in a saturated and non-saturated network, the overhearing time equals the overhearing time observed with Watchdog. muDog is thus more performant than Watchdog when the queue contains less than 22 packets in a saturated network and less than 26 packets in a non-saturated network. In the case of a transmission without any acknowledgement, muDog is much more performant. Indeed, even when the queue contains the maximum number of packets (31), the overhearing time is reduced by 63%. The figure 5 shows the overhearing time according to the size of the packets in 6 different situations: in an optimal situation with and without any acknowledgement, in a realistic situation with a saturated network and an acknowledged transmission, with a non-acknowledged transmission, and with a non-saturated network. All these cases are then compared to the Watchdog (the CAP duration).

The overhearing time significantly decreases in the case of a non saturated network compared to a saturated network, although we introduced a delay X 1 = 100 slots. Indeed, in the case of a non saturated network, the packets are less often generated, and this reduces the probability φ. In the case of a non acknowledged transmission, the transaction duration is minimized, and this significantly reduces the overhearing time. muDog is quite performing in the cases of a non saturated network and of a non acknowledged transmission; it prevents the nodes from reaching Watchdog overhearing time for any packet size. With a value of x = 118 (maximum value), the overhearing time is reduced by 19% in a non saturated network and by 72% in the case of a non acknowledged transmission. However, in the case of saturated network, and with a great number of permanently generated packets, muDog is more efficient than Watchdog only for x < 92 bytes. Indeed, the small packets (for instance x = 20), the necessary overhearing time is of 0.265 s with muDog, whereas it is still fixed at 0.33 s with Watchdog, even for a small packet. muDog thus reduces the activity period of the monitor by 20%, which will consequently reduce the energy cost. 2) Impact of the nodes density: In order to study the impact of nodes density on the overhearing time, we varied the nodes density N from 2 to 50 nodes in the network and the obtained results are plotted in figure 6. The overhearing time obviously increases proportionally to the nodes density. However, muDog is much more performing in small saturated networks with less than 12 nodes (15 nodes in a non saturated network) than Watchdog. For a network composed of 5 nodes, the overhearing time is reduced by more than 50% (0.15 s) of the time given for Watchdog. In the case of great networks, it is important to have a great overhearing time (equal to CAP) in order to monitor a great number of nodes and thus a more intense traffic.

B. Evaluation of the probability to have an accurate observation P w

In this subsection, we evaluate the impact of the traffic charge, nodes density and distance between the monitoring and monitored nodes on the probability to make an accurate observation P w. In order to study the impact of the nodes density on the monitoring process, we have evaluated P w variation according to the nodes density for two network traffic loads 5pps and 15pps. The obtained results are plotted in figures 9(a) and 9(b). In both cases, the probability to have an accurate observation significantly decreases when the nodes density increases. Indeed, when the number of nodes increases, the probability to have a successful transmission decreases (because of the collisions) and thus the probability to have an accurate observation also decreases. The decrease is even more important in the case of a saturated network. The difference between both cases may reach 80%. The best values of P w are reached when the nodes density is small (between 2 and 10 nodes) and for short distances between the monitoring and monitored nodes (10m). In such cases, they vary between 0.2 and 0.98. When the distance and the traffic charge increase, P w decreases more. For instance, for N = 10, 15pps and d = 13m, the probability decreases by 11% in a non saturated network and by 13% in a saturated network. The worst situation occurs with a saturated network, when the nodes density is high (50 nodes) and when the traffic is quite important (15pps). P w is then equal to 0.1.

V. CONCLUSION

In this paper, we proposed an analytical model aiming at ensuring the efficient monitoring process called muDog while taking into account the energy constraints and the accuracy of the monitor's observation. In addition, the evaluation of the proposed monitoring mechanism is proposed and compared to the existing Watchdog mechanism by using different parameters and metrics. The impact of some parameters on the monitoring process like the distance between the monitor and monitored nodes, the time of overhearing (energy consumption), the network traffic load and the nodes density. The evaluations have shown that the transmission probability, the distance between the monitor and monitored nodes and the network traffic load have a negative impact on the monitoring process. However, the nodes density and the type of network (saturated or non saturated) seem to have a mostly negative impact on the observation accuracy. Moreover, the monitor node's accurate observation is thus possible in a small non saturated network with a short distance between the monitoring and the monitored nodes. The obtained results illustrate that muDog is more efficient than Watchdog whatever the parameter is.

In our future works, we plan to evaluate muDog by introducing different mobility models and by using a real test-bed.

Fig. 1 .

 1 Fig. 1. Superframe structure in IEEE802.15.4

Fig. 2 .

 2 Fig. 2. Scenario of monitoring mechanism

Fig. 3 .

 3 Fig. 3. The global flowchart of muDog

Fig. 4 .

 4 Fig. 4. T overhearing according to the average number of packets (N Pmoy)

Fig. 5 .

 5 Fig. 5. T overhearing according to the size of MACPayload

Fig. 6 .

 6 Fig. 6. T overhearing according to the nodes density

Fig. 7 .

 7 Fig. 7. P w versus nodes density with 5pps and 15 pps of traffic charge


Guillaume Blin
email: gblin@univ-mlv.fr

Romeo Rizzi
email: rrizzi@dimi.uniud.it

Stéphane Vialette
email: vialette@univ-mlv.fr

A faster algorithm for finding minimum Tucker submatrices

A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1s on each row are consecutive. Algorithmic issues of the C1P are central in computational molecular biology, in particular for physical mapping and ancestral genome reconstruction. In 1972, Tucker gave a characterization of matrices that have the C1P by a set of forbidden submatrices, and a substantial amount of research has been devoted to the problem of efficiently finding such a minimum size forbidden submatrix. This paper presents a new O(∆ 3 m 2 (m∆ + n 3 )) time algorithm for this particular task for a m × n binary matrix with at most ∆ 1-entries per row, thereby improving the O(∆ 3 m 2 (mn + n 3 )) time algorithm of Dom et al. [17].

Introduction

A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1s on each rows are consecutive. Both deciding if a given binary matrix has the C1P and finding the corresponding columns permutation can be done in linear time [9, 18, 19, 23-25, 28, 31]. The C1P of matrices has a long history and it plays an important role in combinatorial optimization, including application fields such as scheduling [START_REF] Bartholdi | Cyclic scheduling via integer programs with circular ones[END_REF][START_REF] Hassin | Approximation algorithms for hitting objects with straight lines[END_REF][START_REF] Hochbaum | Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms[END_REF][START_REF] Veinott | Optimal capacity scheduling[END_REF], information retrieval [START_REF] Kou | Polynomial complete consecutive information retrieval problems[END_REF], and railway optimization [START_REF] Mecke | Station location complexity and approximation[END_REF][START_REF] Mecke | Solving geometric covering problems by data reduction[END_REF][START_REF] Ruf | Set covering with almost consecutive ones property[END_REF] (see [START_REF] Dom | Algorithmic aspects of the consecutive-ones property[END_REF] for a recent survey). Furthermore, algorithmic aspects of the C1P turn out to be of particular importance for physical mapping [START_REF] Alizadeh | Physical mapping of chromosomes using unique probes[END_REF][START_REF] Christof | A branch-and-cut approach to physical mapping of chromosome by unique end-probes[END_REF][START_REF] Lu | A test for the consecutive ones property on noisy dataapplication to physical mapping and sequence assembly[END_REF] and ancestral genome reconstruction [START_REF] Adam | Common intervals and symmetric difference in a model-free phylogenomics, with an application to streptophyte evolution[END_REF][START_REF] Chauve | A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genome[END_REF]. (see also [10, 3-5, 14, 32] for other applications in computational molecular biology). Actually, our main motivation for studying algorithmic aspects of the C1P comes from minimal conflicting sets in binary matrices in the context of ancestral genome reconstruction [START_REF] Chauve | Minimal conflicting sets for the consecutive ones property in ancestral genome reconstruction[END_REF]. A minimal conflicting set of rows in a binary matrix is a set of rows R that does not have the C1P but such that any proper subset of R has the C1P (a similar definition applies for columns). The aim of this paper is to lay the foundations for efficiently computing minimal conflicting sets by presenting a new efficient algorithm for finding such a minimum size forbidden Tucker submatrix [START_REF] Blin | General framework for minimal conflicting set[END_REF].

Let us turn the C1P into an optimization problem. Recently, Dom et al. [START_REF] Dom | Approximation and fixedparameter algorithms for consecutive ones submatrix problems[END_REF] investigated natural problems arising when a matrix M does not have the C1P property (the C1P is indeed a desirable property than often leads to efficient algorithms):

-Min-COS-C ("Consecutive Ones Submatrix by Column Deletion")find a minimum-cardinality set of columns to delete such that the resulting matrix has the C1P. -Min-COS-R ("Consecutive Ones Submatrix by Row Deletion") -find a minimum-cardinality set of rows to delete such that the resulting matrix has the C1P. -Min-CO-1E ("Consecutive Ones by Flipping 1-Entries") -find a minimumcardinality set of 1-entries in the matrix that shall be flipped (that is, replaced by 0-entries) such that the resulting matrix has the C1P.

All these problems are NP-hard even for simple instances [START_REF] Hajiaghayi | A note on the consecutive ones submatrix problem[END_REF][START_REF] Tan | The consecutive ones submatrix problem for sparse matrices[END_REF], and hence Dom et al. have focussed on approximation and parameterized complexity issues. To this end, they have provided a technical solution based on efficiently detecting forbidden Tucker submatrices [START_REF] Tucker | A structure theorem for the consecutive 1s property[END_REF]. For the sake of presentation, let us introduce these forbidden submatrices by graphs.

Let M be a m × n binary matrix. Its corresponding vertex-colored bipartite graph G(M ) = (V M , E M ) is defined as follows: for every row (resp. column) of M there is a black (resp. white) vertex in V M , and there is an edge between a black vertex v i and a white vertex v j , i.e., an edge between the vertices that correspond to the i th row and the j th column of M , if and only of M [i, j] = 1. Equivalently, M is the reduced adjacency matrix of G(M ). See Figure 1 for an illustration. In the sequel, we shall speak indistinctly about binary matrices and their corresponding vertex-colored bipartite graphs. Recall now that an asteroidal triple, is an independent set of three vertices such that each pair is joined by a path that avoids the neighborhood of the third. Most of the interest in this definition stems from the following theorem.

Theorem 1 ([35], Theorem 6).

A binary matrix has the C1P if and only if its corresponding vertex-colored bipartite graph does not contain a white asteroidal triple.

Moreover, Tucker has characterized the binary matrices that have the C1P by a set of forbidden submatrices.

= {M I k , M II k , M III k , M IV , M V }) in a
given binary matrix. The general algorithm is as follows. For each white asteroidal triple u, v, w of G(M ), compute the sum of the lengths of three shortest paths connecting two by two u, v and w (each path has to avoid the closed neighborhood of the third vertex). Select an asteroidal triple u, v, w of G(M ) with minimum sum and return the rows and columns of M that correspond to the vertices that occur along the three shortest paths. The authors proved that the returned submatrix does contain a forbidden Tucker submatrix of T but which is not necessarily of minimum size (for M III k , M IV and M V ). Indeed, since the three shortest paths may share some vertices, the sum of the lengths of the three paths is not necessarily the number of vertices in the union of the three paths. However, Dom et al. showed that the returned submatrix contains at most three extra columns (resp. five extra rows) compared with a forbidden Tucker submatrix with minimum number of columns (resp. rows). To overcome this problem, they provided another algorithm devoted to M III k , M IV and M V submatrices. More precisely, they used the similarity between M III k and M I k to reduce the problem to a minimum-size hole search. For M IV and M V , they provided an exhaustive search. On the whole, Dom et al. provided an algorithm for finding a forbidden Tucker submatrix in a given matrix M (assuming M does not have the C1P) in O(∆ 3 m 2 n(m + n 2 )) time, where m is the number of rows of M , n is the number of columns of n, and ∆ is the maximum number of 1-entries in a row. More precisely, the authors provided a O(∆mn 2 + n 3 ) time algorithm for finding a

M I k or M II k submatrix, a O(∆ 3 m 3 n + ∆ 2 m 2 n 2 ) time algorithm for finding a M III k submatrix, a O(∆ 3 m 2 n 3 ) time algorithm for finding a M IV submatrix, and a O(∆ 4 m 2 n) time algorithm for finding a M V submatrix. Dom et al. M I k and M II k O(∆mn 2 + n 3 ) M III k O(∆ 3 m 3 n + ∆ 2 m 2 n 2 ) M IV O(∆ 3 m 2 n 3 ) M V O(∆ 4 m 2 n) Total O(∆ 3 m 2 n(m + n 2 ))
The main contribution of this paper is a simple O(∆ 3 m 2 (m∆ + n 3 )) time algorithm for finding a minimum size forbidden Tucker submatrix. Our algorithm is based on shortest paths and two graph pruning techniques: clean and anticlean (to be defined in the next section). Graph pruning techniques were introduced by Conforti et al. [START_REF] Conforti | Structural properties and decomposition of linear balanced matrices[END_REF]. One has to note that graph pruning technique not always succeed in the detection of induced configurations. Indeed, in [START_REF] Bienstock | On the complexity of testing for odd holes and induced odd paths[END_REF], Bienstock gave negative results among which one can find an NP-completeness proof for the problem of deciding whether a graph contains an odd hole containing a given vertex. This negative result, which in attacking the perfect graph conjecture was useful in posing limits in what could have been a reasonable approach, also demonstrates that not everything can be done with the detection of induced configurations. We now focus on the bipartite graphs that represent Tucker configurations (see Figure 2). Define the guess(V ⊆ {x, y, z, A, B}) operation as follows: given a Tucker configuration T ∈ T , identifies by a brute-force algorithm all the vertices of V among the vertices of G(M ). In other words, the guess operation tries all possible matching between vertices labeled by x, y, z, A or B in T and vertices of G(M ). Of particular importance, guessed vertices will never be affected (i.e., deleted) by the clean and anticlean operations. Lemma 1. Let M be m × n binary matrix with at most ∆ 1-entries per row. One can find the smallest submatrix G(M I k ) in G(M ) in O(m 2 ∆ 3 (n+ ∆m)) time (if such a submatrix exists).

We apply Algorithm 1 to G(M ). Let us first prove that if G(M

I k ) occurs in G(M ), then Algorithm 1 finds it. Suppose G ′ = G(M I k ) occurs in G(M ).
Then among all the guessed 5-uplets x, y, z, A, B (Line 1), there should be at least one guess such that x, y, z, A, B are part of the vertices of G ′ . By definition, G ′ is a hole, and hence does not have a chord. Therefore, clean(x, A, B) preserves G ′ since, in G ′ , [START_REF] Adam | Common intervals and symmetric difference in a model-free phylogenomics, with an application to streptophyte evolution[END_REF] x is only connected to vertices A and B, (2) A is only connected to vertices x and y, and (3) B is only connected to x and z. Moreover, looking for a shortest path p in Algorithm 2 Find G(M II k ) in G(M ) Proof. 1: guess({x, y, z, A, B}) and add them to S 2: anticlean(A, B) 3: clean(x) 4: find a shortest path p in the pruned graph between y and z after having removed A and B 5: if p exists then 6:

Add the vertices of p to S 7:

return the induced subgraph G(M )[S] 8: end if the pruned graph between y and z after having removed A and B ensures the minimality of the returned graph which is indeed an hole.

The guessing can be done in O(m 2 ∆ 3 ) time. Indeed, once A has been identified, one can select x and y among the at most ∆ neighbors of A and then identify B and one of its at most ∆ neighbors as z such that x ∈ N (B) and z / ∈ {x, y}. For each such guessing, the cleaning of x, A, B can be done in O(∆ + m) time. Finally, one can find a shortest path between y and z by a breadth-first search in the pruned graph after having removed A and B which has at most m + n vertices and ∆m edges in O(n + ∆m) time. On the whole, Algorithm 1 is O(m 2 ∆ 3 (n + ∆m)) time.

⊓ ⊔ Lemma 2. Let M be a m × n binary matrix with at most ∆ 1-entries per row. One can find the smallest submatrix

G(M II k ) in G(M ) in O(m 2 ∆ 3 (n+ ∆m)) time (if such a submatrix exists).
We apply Algorithm 2 to G(M ). Let us first prove that if G(M II k ) occurs in G(M ), then Algorithm 2 finds it. Suppose G ′ = G(M II k ) occurs in G(M ). Then among all the guessed 5-uplets x, y, z, A, B in Line 1, there must be at least one guess such that x, y, z, A, B are indeed part of the vertices of G ′ . By definition, in G ′ , any unguessed white node is in the neighborhood of both A and B. Thus, anticlean(A, B) preserves G ′ since, in G ′ , (1) y which is the only white node not in the neighborhood of B has been guessed and (2) z which is the only white node not in the neighborhood of A has been guessed. Moreover, in G ′ , x should be only connected to A and B. Thus, clean(x) preserves G ′ . Finally, looking for a shortest path p in the pruned graph between y and z after having removed A and B ensures the minimality of the returned graph which is indeed G(M II k ).

The guessing can be done in O(m 2 ∆ 3 ) time. For each such guessing, the cleaning/anticleaning of x, A, B can be done in O(n+m) time. Finally,

Algorithm 3 Find G(M III k ) in G(M )
Proof. 1: guess({x, y, z, A}) and add them to S 2: anticlean(A) 3: clean(x) 4: find a shortest path p in the pruned graph between y and z after having removed A 5: if p exists then 6:

Add all the nodes of p to S 7:

return the induced subgraph G(M )[S] 8: end if one can find a shortest path between y and z by a breadth-first search in the pruned graph after having removed A and B which has at most ∆ + n vertices and ∆m edges in O(n + ∆m) time. On the whole, Algorithm 2 is O(m 2 ∆ 3 (n + ∆m)) time.

⊓ ⊔

If we compare Algorithm 1 and Algorithm 2, in both cases we are looking for a y -z shortest path in the pruned graph after having removed A and B. Moreover, if we refer to Figure 2, the final structural topology of the y -z path is similar in the M I k and M II k matrices. Therefore, one may reasonably think that the total number of path vertices should be equal in both cases. This is not true due to different pruning techniques: cleaning in Algorithm 1 versus cleaning/anticleaning in Algorithm 2. Lemma 3. Let M be a m × n binary matrix with at most ∆ 1-entries in each row. One can find the smallest G(M III k ) in G(M ) in O(m∆n 2 (n + ∆m)) time (if such a submatrix exists).

We apply Algorithm 3 to G(M ). Let us first prove that if G(M III k ) occurs in G(M ), then Algorithm 3 finds it. Suppose G ′ = G(M III k ) occurs in G(M ). Then among all the guessed 4-uplets x, y, z, A in Line 1, there must be at least one guess such that x, y, z, A are indeed part of the vertices of G ′ . By definition, in G ′ , any unguessed white node is in the neighborhood of A. Thus, anticlean(A) preserves G ′ since, in G ′ , y and z which are the only white nodes not in the neighborhood of A have been guessed. Moreover, in G ′ , x is only connected to A. Thus, clean(x) preserves G ′ . Finally, looking for a shortest path p in the pruned graph between y and z after having removed A ensures the minimality of the returned graph which is indeed G(M III k ).

The guessing can be done in O(m∆n 2 ) time. Indeed, once A has been identified, one can select x among the at most ∆ neighbors of A and then identify y and z among the n white nodes such that x = y = z. We are now ready to state the main result of this paper (Table 1 compares our results with Dom et al. [START_REF] Dom | Approximation and fixedparameter algorithms for consecutive ones submatrix problems[END_REF].). Theorem 3. Let M be a m × n binary matrix with at most ∆ 1-entries per row that does not have the C1P. A minimum size forbidden Tucker submatrix that occurs in M can be found in O(∆ 3 m 2 (m∆ + n 3 )) time.

O(∆mn 2 + n 3 ) O(m 2 ∆ 3 (n + ∆m)) MIII k O(∆ 3 m 3 n + ∆ 2 m 2 n 2 ) O(m∆n 2 (n + ∆m)) MIV O(∆ 3 m 2 n 3 ) MV O(∆ 4 m 2 n) Overall O(∆ 3 m 2 (mn + n 3 )) O(∆ 3 m 2 (m∆ + n 3 ))

Matrices with unbounded ∆

As mentioned in [START_REF] Dom | Approximation and fixedparameter algorithms for consecutive ones submatrix problems[END_REF], a natural question would be to investigate the complexity of the problem when the number of 1s per row is unbounded. One can thus distinguish two subcases: the maximum number of 1s per column is bounded (say by C) or not. Due to space constraint, the two following results are given without proof.

Fig. 1 .

 1 Fig. 1. A binary matrix and its corresponding vertex-colored bipartite graph.

Fig. 2 .

 2 Fig.2. Forbidden Tucker submatrices represented as vertex-colored bipartite graphs[START_REF] Tucker | A structure theorem for the consecutive 1s property[END_REF]. Black and white vertices correspond to rows and columns, respectively.

Algorithm 1

 1 Find G(M I k ) in G(M ) Proof. 1: guess({x, y, z, A, B}) and add them to S 2: clean(x, A, B) 3: find a shortest path p in the pruned graph between y and z after having removed A and B 4: if p exists then 5: Add the vertices of p to S 6: return the induced subgraph G(M )[S] 7: end if 2 Fast detection of minimum size forbidden Tucker submatrices Let us introduce the clean and anticlean cleaning operations. Let M be a binary matrix and G(M ) = (V M , E M ) be the corresponding vertexcolored bipartite graph. For any node v of G(M ), clean(v) results in the graph where any neighbor of v has been deleted, i.e., G(M )[V M \ N (v)]. For any node v of G(M ), anticlean(v) results in the graph where any node that does not belong to the same partition nor the neighborhood of v has been deleted, i.e., G(M )[V M \ {u : u ∈ N (v) and color(u) = color(v)}].

  ⊓ ⊔Considering G(M IV ) and G(M V ), a simple brute-force search yield the following Lemma 4 ([17], Proposition 5.3). Let M be a m × n binary matrix with at most ∆ 1-entries per row. One can find the smallestG(M IV ) (resp. G(M V )) in G(M ) in O(∆ 3 m 2 n 3 ) (resp. O(∆ 4 m 2 n) time) if it exists.

Theorem 4 .

 4 Let M be a m × n binary matrix with at most C 1-entries per column. A minimum size forbidden Tucker submatrix that occurs in M can be found in O(C 2 n 3 (m + C 2 n)) time.Theorem 5. Let M be m × n binary matrix. A minimum size forbidden Tucker submatrix that occurs in M can be found in O(n 4 m 4 ) time.

Table 1 .

 1 Comparing our results with Dom et al.[START_REF] Dom | Approximation and fixedparameter algorithms for consecutive ones submatrix problems[END_REF].For each such guessing, the cleaning/anticleaning of x, A can be done in O(n + m) time. Finally, one can find a shortest path between y and z by a breadth-first search in the pruned graph after having removed A which has at most ∆ + n vertices and ∆m edges in O(n + ∆m) time. On the whole, Algorithm 3 is O(m∆n 2 (n + ∆m)) time.


Nadia Haddadou

Abderrezak Rachedi

Yacine Ghamri-Doudane

Gaspard Monge

Advanced Diffusion of Classified Data in Vehicular Sensor Networks

Keywords: Vehicular Sensor Networks, Data Dissemination, Performance Evaluation

In this paper, we propose a new distributed protocol called ADCD to manage information harvesting, and distribution in Vehicular Sensor Networks (VSN). The concept of ADCD is based on the characterization of sensed information (i.e. its importance, location and time of collection) and the diffusion of this information accordingly. Furthermore, ADCD uses an adaptive broadcasting strategy to avoid the submersion of users with messages for which they have no interests. Thanks to this adaptive broadcasting strategy, ADCD limits the generated overhead avoiding network congestions as well as the long latency to deliver the harvested information, which are the main limits of other existing protocols. Moreover, it is designed to be flexible regarding the use of roadside units or not, which is not the case of other schemes in the literature. To reaches its objectives, ADCD operations are divided into three steps: (i) classification of data and the identification of their target area of diffusion, (ii) data-centric election of the set of broadcasters for avoiding the broadcasting redundancy, and (iii) iterative process for data dispatching in a targeted area. Performance evaluation shows that the ADCD protocol allows mitigating the information redundancy and its delivery with an adequate latency while making the reception of interesting data for the drivers (related to their location) more adapted. Moreover, the ADCD protocol reduces the overhead by 90% compared to the classical broadcast and an adapted version of MobEyes [4]. The ADCD overhead is kept stable whatever the vehicular density.

I. INTRODUCTION

ehicular sensor networks have been widely investigated during the last few years as they offer applications for road safety and driver's/passenger's comfort. They are considered as the most effective and cheapest way to avoid congestion on the roads leading to minimizing the consumption of fuel, and the time spent on the road. They also have fewer operational limitations (memory, processing, energy…) than basic Wireless Sensor Networks (WSN). However, their large amount of generated information and the frequent topology changes (density, topology, neighboring nodes…) make the existing solutions in the WSN field ineffective for this new kind of networks.

The main issues in VSN reside in the data harvesting and dissemination in such a large scale network, characterized by the frequent topology changes and network partitioning. In this paper we will focus on the data harvesting and distribution based on targeting the concerned nodes, i.e. the nodes that should receive the information and can be interested by its content according to their geo-location and the specificities (importance, location and time of collection) of the harvested data.

Our main motivation in this work comes from the fact that the congestion and the redundancy induced in order to ensure the reception of relevant messages by the concerned nodes, is an important drawback of previous works. Thus, we propose a new protocol for Advanced Diffusion of Classified Data (ADCD). ADCD targets the receptors to avoid both redundancy and network congestion. This is performed by inserting intelligence in the diffusion process. Therefore, ADCD differentiates the sensed data according to their relevance and period of validity, in order to better predict its importance for the other nodes in the network. Once the first step achieved, the collector node customize the diffusion by electing a number of broadcasters from its neighborhood according to the importance of the message, while reducing the redundancy by binding the election process to different criteria (node density, node positions). Finally, the third step consists on verify whether the limits of the broadcasting of a message, in terms of targeted broadcasting area and content validity in time, had been reached or not. By doing so, we show in this paper that the overhead/redundancy induced by ADCD is lower than the one induced by other existing schemes while the reception probability by concerned nodes is maintained high.

The remainder of this paper is organized as follows: Section II presents and summarizes the main related works. Section III focuses on the description of the proposed Advanced Diffusion Protocol of Classified Data (ADCD) protocol. Then, Section IV presents the performance evaluation of ADCD and compares it to two other existing protocols: classical broadcast and an adapted version of the MobEyes [START_REF] Lee | MobEyes: Smart Mobs for Urban Monitoring with a Vehicular Sensor Network[END_REF] protocols. Finally, Section V draws our conclusions and future works.

II. RELATED WORK

Many studies have recently been realized in the field of vehicular sensor networks. Among the main topics addressed by the research community in this domain, we find: data harvesting and data diffusion. In the following, we explain the limitation of the related literature. These limitations had motivated our current work.

A. Data Harvesting

Data harvesting is considered as the first step of most of VSN applications. The aim of data harvesting in VSNs is to V facilitate the two following steps in the VSN traditional lifecycle: i.e. data search and data dissemination.

The main data harvesting approach proposed in the literature is the DataTaxis [START_REF] Lee | Bioinspired Multi-Agent Data Harvesting in a Proactive Urban Monitoring Environment[END_REF] algorithm. This algorithm is inspired from the behavior of insects during their search for food. In Data Taxis, this behavior is thus adapted to vehicles allowing to effectively cover a large area and to harvest the maximum amount of data. This is realized by placing a large number of agents in concentrated information areas. This is performed by the use of stigmergy, a communication mechanism used by insects such as ants. The redundancy of collected data is decreases. This idea is difficult to adapt to insure safety applications with time constraints, due to the important mobility of VSNs. Indeed, in the case of safety applications, it is difficult to forecast where the events will happen. So, it is difficult to predict where the data harvesting agents need to be placed unless a large number of agents is used. In the latter case the data harvesting scheme will be very complex to deploy.

B. Data Diffusion

Defining a data sharing strategy depends on the type of application that uses this data as well as the required quality of service by this application. Among the existing works, two methods are frequently used. The first one consists in an immediate sending of the harvested data to support real-time applications. The inconvenience of such a method is the important redundancy that is induced and the risk of network congestion. The second method performs first data processing, and vehicles only exchange summaries at regular periods of time [START_REF] Lee | Efficient Data Harvesting in Mobile Sensor Platforms[END_REF]. The goal of this method is to reduce the amount of exchanged information on the network to avoid any congestion. However, the deployment for real-time applications is impossible and an incomplete data diffusion is probable [START_REF] Lee | MobEyes: Smart Mobs for Urban Monitoring with a Vehicular Sensor Network[END_REF]. We position ourselves in the middle of these two ideas, the pre-processing made in ADCD avoid sending messages repeatedly and limits the rebroadcasting using different concepts to ensure good latency and reception ratio.

To perform a dissemination that takes into account the importance degree of each individual data, a classification between different kinds of messages, according to their quality of service requirements in terms of delay and throughput, is established. The first class concerns emergency messages, like accidents notifications. These messages are small and need to be transmitted with a high propagation velocity to insure a real time service [1] [START_REF] Torrentmoreno | Broadcast Reception Rates and Effects of Priority Access in 802.11Based Vehicular AdHoc Networks[END_REF]. For other situations, particularly the less urgent ones, a warning message is used to catch the driver's attention. These messages concerns for instance Driver Assistance Applications. The last type is used to develop collaborative driving; where drivers share information about the density and the average speed of vehicles within the road allowing reducing the risk of traffic jams. Warning messages are less important than the emergency one but a higher rate is required for them. However, how to introduce this classification in the dissemination phase remains vague. That is why ADCD protocol classifies the information before their diffusion in the network and specifies the corresponding diffusion strategy to each one within the broadcasted message. This is made so as to guarantee that the diffused messages will be received by a maximum number of concerned nodes.

Another futuristic application of interest to VSNs is the content sharing as proposed in [START_REF] Gerla | Vehicular networks and the future of the mobile internet[END_REF]. The technology used for that is the peer to peer technology which remains innovative for this kind of networks. Its content will include delaysensitive and delay-tolerant data. These two concepts are also taken into account in our proposed protocol ADCD through the delay "Mode" parameter. In addition, content sharing applications among vehicles needs an efficient distribution mechanism.

The approach proposed in [START_REF] Bai | Exploiting the Wisdom of the Crowd: Localized, Distributed Information-Centric VANETs[END_REF] differs from previous ones which use classic criteria for data classification. The authors develop generic network architecture to support futuristic VSN applications on focusing on the space, time and user interest related to information during its distribution. The paper assumes different kind of applications, such as safety applications, location-based services, city wide alerts and interactive services with their spatial, temporal and interest scope which define the area and time of deployment, followed by the type of targeted receiving vehicles. The realization of these applications supposes the use of roadside units which limits the deployment of such applications. Furthermore, there is no specific distribution protocol proposed in this paper. Although our protocol, ADCD, shares the same philosophy about the data's classification, it proposes a new adapted strategy for data dissemination which takes full advantage from the data classification.

Another very interesting approach for data diffusion in VSNs is the Smart Mobs for Urban Monitoring with a Vehicular Sensor Network, MobEyes [START_REF] Lee | MobEyes: Smart Mobs for Urban Monitoring with a Vehicular Sensor Network[END_REF]. MobEyes ensures a proactive urban monitoring by taking advantage vehicles mobility. The exchanged messages can include 2 to 10 minutes of summaries regarding the captured data. This method, target a specific surveillance application where data are harvested, by police officers. A bloom filter is applied to retrieve the missing information tightly linked to this avoiding redundancy. However, MobEyes is proposed for specific application and its generalization is not straightforward. That is why, we propose a new protocol ADCD with more parameters which make it more general and thus it can be applied to different applications.

C. Discussion

Future application constraints for VSNs are tightened, with more requirements for network performance. As explained above, existing solutions cannot always meet their needs. A new vision has to be established to respond to the remains interrogations such as the dilemma of receiving or not information according to its pertinence and the delivery time required for its reception while avoiding overhead.

Our concept fits the identified constraints thanks to the data characterization and the corresponding enhanced diffusion.

III. ADVANCED DIFFUSION OF CLASSIFIED DATA

In this section, we describe our proposed protocol called Advanced Diffusion of Classified Date (ADCD). Its aim is to empower safety applications in vehicular sensor networks. For more robustness, the protocol is agnostic on the existence of roadside units. It just supposes that a minimum number of vehicles are equipped with sensors and communication capabilities, accepting to collaborate with other vehicles for safety information distribution. This protocol allows a regular harvesting along with smart information sharing between vehicles to avoid any risk of congestion or starvation in isolated areas.

We consider that each vehicle has to receive all emergency and local information messages available within a certain perimeter and under a corresponding time of validity. This is realized with the aim of keeping it continuously aware of current traffic conditions without flooding inappropriately other areas with information of non-interest them. Our approach is generic enough to make it possible to do that but also to distribute information on the entire network is possible if needed.

ADCD is based on three main parts: (i) harvesting and data classification, (ii) election of broadcaster, and data sharing, and (iii) iterative rebroadcast with corresponding scope.

A. Data Harvesting

A vehicle equipped with different types of sensors can collect several kinds of data. To illustrate our approach, we take the following message/data classes of interest: accident, traffic jam, landslide, risk of slipping, car crash, roadwork, vehicles number, failure of a traffic light, road's density. We consider that each piece of information depends on the region where it was collected. This way, its diffusion is only useful in its surroundings during a fixed period of time to avoid the transmission of old information.

In order to carry out this concept, we characterize information with two parameters: class and mode. A class represents the importance level of information; it is used to define the broadcasting area within the VSN. The mode is a value in a scale representing the period of validity of the data.

ADCD defines an interval [∂ min , ∂ max ] for the classes and modes. The most urgent messages and the longest in validity are characterized as class ∂ max . A piece of information is represented by Cxy, where x represents the class and y the mode.

The vehicles concerned by particular information are those belonging to the targeted broadcast area and for which we advocate interest in receiving this information. In order to target these vehicles during the transmission, we attribute a diffusion perimeter, as a square centered upon with the coordinates of the collected data. The length of each square's side corresponds to the class of data. Table 1 gives an example of how ADCD can be used for a traffic safety application. In this example five classes are defined. For each class, a square is associated for each one defining its targeted diffusion area (200*200m², 300*300m², 400*400m², 600*600m² and 800*800m² to the first, second, third, fourth and fifth class, respectively). Hence, in this example, a road density message should not exceed the perimeter of 200*200 m².

The same principle was followed to define the period's validity corresponding to the mode of the data.

Information

B. Data Sharing

Each vehicle cooperates in the network by sending its collected data to the other vehicles. To avoid redundancy, the information is shared only if it meets the following conditions: -The vehicle has recently collected the data.

-The vehicle can resend the same data only if the previous message regarding it has reached its time validity and the information is always valid.

-None of the vehicle's neighbors already distributed this information (i.e. a message from a neighbor containing the information to share hadn't been received earlier).

If the conditions are met, the vehicle waits for a random time (backoff), bounded by the importance of the information. This mechanism aims at avoiding the simultaneous sending leading to redundancy and resource wastage.

Our concept of class and mode allows broadcasting harvested information by the vehicles according to their coordinates and date of collection. Each message will contain both values in its header.

To share information among vehicles in VSNs a basic and straightforward approach is to use classical broadcast (i.e. flooding). This will ensure the reception of the message by all the members but inevitably causes what we call a broadcast storm [START_REF] Ni | The broadcast storm problem in a mobile ad hoc network[END_REF]. We decide to proceed differently. First, we choose a single hop broadcast, the message is received by all the direct neighbors of the source. Then, the continuation of the rebroadcasting procedure depends on the class and mode associated to the message (i.e. the data).

The source vehicle is also in charge of the election of the nodes among its neighbors to rebroadcast the message. The list of elected vehicles is thus inserted in the message, so that only these vehicles are authorized to rebroadcast the message. Thus allows avoiding broadcasting redundancy at the reception. The number of broadcaster nodes to elect depends on the information class. For the example depicted in Table 1, we can have for instance three configurations. One is for class 1 where a simple single hop broadcast is sufficient while respecting the perimeter of 200*200 m². The second, for classes 2 and 3, where the source selects three broadcaster nodes to cover the larger area covered (300*300 m² and 400*400m², respectively). This can be implemented by choosing the node with the largest number of neighbors, and then we choose two other nodes with a wide coverage located at almost 120 ° and -120 ° from the current source node. Similarly, the same method can be applied to classes 4 and 5 where four broadcaster nodes and an angle of 90° are used.

Figure 2, represents an example of use of the election algorithm for class 3 of depicted application example, in which the number of broadcaster is fixed to three. As we can see below, the first elected node is the neighbor with the highest density. Then, the two other elected nodes are chosen according to their rotation angle relatively to the previous elect and their density. The election algorithm has as an input the number of broadcaster nodes we would like to have, and as an output their coordinates. It is depicted in Figure 3.

C. Iterative Rebroadcasting

At the reception of a message, the vehicle checks the validity of the information in time and space. This is performed according to the mode and class associated to the data in the message. If the information crossed the boundaries of its targeted area or the time validity is passed, the receiving node deletes it.

Otherwise, the receiving node consumes the information and verifies if it is elected as a broadcaster for it or not. If so, it broadcasts the message while safeguarding its characteristics, such as: class, mode, collection date and collection location coordinates. Using this evaluation scenario, ADCD is compared to two other diffusion algorithms. The first one is the classical broadcast where each receiving node performs one rebroadcast for message. The second one is adapted diffusion MobEyes, where a node transmits a message each 12 seconds containing a maximum of 5 received or harvested summaries. To increase the effectiveness of its sharing information, we set the k-hop to 3. We consider a message as redundant if the 5 summaries contained in it had been already received by the node, or if they exceed their interest perimeter or time validity.

For clarity, we measure the performance on a simple application, with different messages depicted in Table 1; their class and mode belong to the interval [1, 5]. In our simulation, a new message (i.e. a harvested data) is generated each 5 seconds and can be harvested (i.e. sensed) by at least one node. The events happen with certain probabilities according to their class, the probabilities of harvesting are 0.60, 0.20, 0.10, 0.05, 0.05 to the first, second, third, fourth and fifth class, respectively.

We select two performance metrics for our evaluation: -The percentage of useful reception according to the target diffusion area. -The overhead induced by each scheme. The sensitivity of these two metrics regarding the vehicular density is also analyzed.

A. Effectiveness of the target diffusion

A message loses its relevance after a period of time which differs according to its content. In Figure 5, we represent the percentage of received messages by the concerned nodes as a function of time. We remark that ADCD quickly informs all concerned nodes compared to classical broadcast or adapted MobEyes. In terms of promptness, ADCD gives better results than both concurrent protocols. In addition, it reaches 100% of concerned nodes in the cases of class 1, 2 and 3 in less than 0.5 s. However, in the cases of class 4 and 5 the concerned nodes receive more than 60% of messages after 0.1s. We also note that extending the broadcasting time doesn't allow improving this percentage. The explanation of this difference among the different classes is mainly due to the size of the targeted area. The latter is more important in the case of classes 4 and 5. Classical broadcast reaches 75% reception ration on average (i.e. no differentiation between classes), which corresponds to 76%, 80%, 84%, 31% and 36% for the first, second, third, fourth and fifth class, respectively. MobEyes, however, requires more time to distribute its messages due to its design features, which also leads to a low percentage of informed vehicles.

B. Overhead

Each message transmitted to a node that is not concerned by it or after the expiry of its validity period is uninteresting and considered as overhead. Figure 6, shows the important gap between the overhead generated by the three algorithms. We remark that ADCD provides less overhead compared to the broadcast and adapted MobEyes protocols. These results are mainly due to the target diffusion using the concept of class and period of validity according to the type of information. Moreover, ADCD allows deleting useless messages where the validity is expired and preventing their rebroadcast. In addition, the selection of the broadcaster nodes based on the election process allows to significantly reducing the redundancy. Vehicle density impact In order to evaluate the impact of the vehicle nodes density on the ADCD performance, we varied the number of nodes from 100 to 300. The obtained results are plotted in Figure 7, which illustrates the average percentage of concerned nodes' received messages according to the nodes' density. We remark that, even if the nodes density increases the percentage of concerned nodes remains stable greater than 90% in the case of ADCD. However, in the case of both protocols (Broadcast and adapted MobEyes) with 100 nodes, the percentage of concerned nodes cannot reach 50% and 40% in the case of Broadcast and MobEyes respectively. When the nodes' density increases the Broadcast and MobEyes' concerned nodes cannot exceed 75% and 58% respectively. These results confirm the efficiency of ADCD for the target diffusion even with a small density which can limit the possibilities of rebroadcast in a large area. 8 shows the overhead according to the nodes density. We remark the linear increasing of the ADCD overhead compared to the exponential of Broadcast and MobEyes. An important overhead, causes the congestion of a network with the impossibility of inject new messages. This can have very serious consequences on safety application for the VSNs. In our case, it was impossible to push simulations with larger density because of the overhead. The main objective of our study was to develop a new protocol to ensure a tradeoff between the reception gain of a data and the latency since it is harvested. This needs to be performed while avoiding redundancy and the implied network congestions. Our protocol called ADCD, for Advanced Diffusion of Classified Data, achieves this goal by characterizing the data to be diffused (distributed area range, validity period) and using an adapted broadcasting strategy. Our performance evaluation showed that ADCD allow reducing the overhead by up to 90% while compared to other existing protocols. This is performed while keeping the stability and reactivity of ADCD at an acceptable level for VSN applications. Our future works include the adaptation of ADCD to different traffic environments (sub-urban, rural, highways …). Taking into account security concerns, such as confidentiality and message integrity, represent another important field of investigation.

Figure 1 :

 1 Figure 1: Sending diagram

Figure 2 :

 2 Figure 2: Example of election process for three broadcasters to elect

Figure 3 :

 3 Figure 3: Election algorithm

Figure 4 : 2 :

 42 Figure 4: Message consumption and rebroadcasting

Figure 5 :

 5 Figure 5: Reception rate according to the thresholds

Figure 6 :

 6 Figure 6: Overhead generated by 300 nodes

Figure 7 :

 7 Figure 7: Percentage of reception with 100, 200 and 300 nodes

Figure

  Figure8shows the overhead according to the nodes density. We remark the linear increasing of the ADCD overhead compared to the exponential of Broadcast and MobEyes. An important overhead, causes the congestion of a network with the impossibility of inject new messages. This can have very serious consequences on safety application for the VSNs. In our case, it was impossible to push simulations with larger density because of the overhead.

Figure 8 :

 8 Figure 8: The overhead generated by 100, 200 and 300 nodes

Table 1 :

 1 Information characteristics of shared data

	Class	Mode