CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

On the Probability of Unsafe Disagreement in Group Formation Algorithms for Vehicular Ad Hoc Networks

Negin Fathollah Nejad Asl (Institutionen för data- och informationsteknik, Datorteknik (Chalmers)) ; Risat Mahmud Pathan (Institutionen för data- och informationsteknik, Datorteknik (Chalmers)) ; Johan Karlsson (Institutionen för data- och informationsteknik, Datorteknik (Chalmers))
Dependable Computing Conference (EDCC), 2015 Eleventh European p. 256-267. (2015)
[Konferensbidrag, refereegranskat]

We address the problem of group formation in automotive cooperative applications using wireless vehicle-to-vehicle communication. Group formation (GF) is an essential step in bootstrapping self-organizing distributed applications such as virtual traffic lights. We propose a synchronous GF algorithm and investigate its behaviour in the presence of an unbounded number of asymmetric communication failures (receive omissions). Given that GF is an agreement problem, we know from previous research that it is impossible to design a GF algorithm that can guarantee agreement on the group membership in the presence of an unbounded number of messages losses. Thus, under this assumption, disagreement is an unavoidable outcome of a GF algorithm. We consider two types of disagreement(failure modes): safe and unsafe disagreement. To reduce the probability of unsafe disagreement, our algorithm uses a localoracle to estimate the number of nodes that are attempting to participate in the GF process. (Such estimates can be provided by roadside sensors or local sensors in a vehicle such as cameras.)For the proposed algorithm, we show how the probability of unsafe and safe disagreement varies for different system settings as a function of the probability of message loss. We also show how these probabilities vary depending on the correctness of the local oracles. More specifically, our results show that unsafe disagreement occurs only if the local oracles underestimates the number of participating nodes.

Nyckelord: Algorithm design and analysis;Automobiles;Automotive engineering;Protocols;Vehicular ad hoc networks;Wireless communication;communication failures;consensus;distributed algorithms;network partitioning;probabilistic analysis



Denna post skapades 2016-01-21. Senast ändrad 2016-09-07.
CPL Pubid: 231100

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datorteknik (Chalmers)

Ämnesområden

Datorteknik

Chalmers infrastruktur