Theses Doctoral

Reliable Neighborcast Protocol for Vehicular Ad hoc Networks

Tientrakool, Patcharinee

This dissertation introduces a new communication paradigm, neighborcast, for vehicular ad hoc networks and proposes a new communication protocol, reliable neighborcast protocol (RNP), to implement the paradigm. Vehicular applications such as collision avoidance can benefit from allowing vehicles to communicate with their nearby vehicles in order to coordinate movements. Neighborcast is a new paradigm for communications between each vehicle and all nearby vehicles that are within a specified distance from it i.e., its neighbors. In neighborcast, each vehicle has its own set of vehicles with which it wants to communicate i.e., the set of its neighbors, which is different from that of other vehicles. Our proposed communication protocol, RNP, is aimed at providing reliable neighborcast communications. It provides guaranteed message delivery from each vehicle in a vehicular ad hoc network to all of its neighbors within a bounded delay, ensures that all the neighbors that receive the same messages sequence them in the same order and use each of them at the same time, and provides the neighbors the knowledge of whether all of the other neighbors have received the message or which neighbors are missing the message. The implementation of RNP is significantly different from reliable multicast/broadcast protocols. In a reliable multicast/broadcast protocol, all communicating vehicles are in one group. But in our RNP, the group size is constrained to limit the communication delay, so we cannot have all vehicles in one group. As a result, we organize vehicles into several overlapping groups and each vehicle may communicate in more than one overlapping group. RNP is created as an overlay protocol on top of overlapping broadcast groups that use a modified version of a recently invented reliable broadcast protocol, M-RBP, and transfers the guarantees provided by the modified M-RBP from the broadcast group level to the neighborhood level. RNP is composed of two parts. The first is the self-organizing protocol that organizes vehicles into overlapping broadcast groups that use the modified version of M-RBP. The self-organizing protocol ensures that each vehicle is always a member of at least one broadcast group containing itself and all of its neighbors. This way, it can reach all of its neighbors by transmitting messages in one broadcast group, resulting in the same message sequencing for all neighbors. The self-organizing protocol also limits the size of each broadcast group to limit the message delivery delay, limits the number of broadcast groups of which a vehicle is a member to limit the number of recovery messages, and moves the broadcast groups with the vehicles to limit the rate at which a vehicle changes groups. The second part of RNP is the mechanism that transfers the guarantees from M-RBP to provide the RNP guarantees. In this dissertation, we also show an example of using RNP in conjunction with sensors to avoid rear-end collisions. We propose a simple set of rules for using RNP with sensors to automatically maintain a safe following distance, provide warnings of emergency situations, and negotiate the safe deceleration rates among nearby communicating vehicles. We quantify the highway capacity improvement from using RNP and compare it with that of using sensors alone.


  • thumnail for Tientrakool_columbia_0054D_10264.pdf Tientrakool_columbia_0054D_10264.pdf application/pdf 4.58 MB Download File

More About This Work

Academic Units
Electrical Engineering
Thesis Advisors
Maxemchuk, Nicholas F.
Ph.D., Columbia University
Published Here
June 20, 2011