Novel communication primitives for vehicular ad-hoc networks

Lead Research Organisation: University of Liverpool
Department Name: Computer Science


In recent years wireless network technology has gained tremendous importance. It not only more and more replaces so far wired network installations but also opens new dimensions in the availability of high-bandwidth connections for mobile applications. In many application areas, the integration of wireless communication together with autonomous sensing devices leads to an improved quality of service due to the immediate availability of measurements and data about the current mode of operation.The goal of this proposal is identification and development of basic communication primitives in the context of vehicular ad-hoc networks (VANETs).Vehicular ad-hoc networks are to provide communication between vehicles as well as nearby roadside equipment in order to improve both safety and comfort for the individual traffic participants and to enhance the capabilities of existing traffic management infrastructure.Only recently, the scale of miniaturization has allowed for untethered micro sensors that can be deployed almost anywhere and measure various factors -- traffic flow, water level, number of people walking by, or temperature. As Nobel laureate Horst Stormer has put it, ''this is developing into something like a nervous system for the earth''. Before this vision comes to reality, though, many challenges have to be solved. While the necessary hardware (sensor and wireless devices) by now has developed to considerable maturity, the underlying basic communication primitives, as well as the general system infrastructure, is still in the process of being well understood. Many fundamental and challenging problems are to be considered,including:(i) How can vehicles, especially those whose tours cross only for a short period of time, reliably exchange information?(ii) How can a vehicle efficiently accumulate and aggregate the data gathered by itself or by other vehicles it has met such that it can be transferred to a central base station without wasting too much communication bandwidth?(iii) Which processes require a central coordination instance and which do not?Such basic questions of communication, data aggregation and distributability of operation, are the foundations of this proposal.In the course of this project it is expected that new theoretical insights are obtained for VANETs applications. We intend to identify and develop the basic communication primitives in the context of wireless ad-hoc networks. In particular, we aim at combining both short-range vehicle-to-vehicle or vehicle-to-roadside communication with long-range, but low-bandwidth, GPRS global Internet connection. Only recently, the cost of GPRS bandwidth has reached the level where permanent connections are viable for the general user. The availability of a low-cost (but low-bandwidth) Internet connection at every vehicle allows for effective coordination of the higher-bandwidth but very short-lived vehicle-to-vehicle or vehicle-to-roadside communications.

Planned Impact

There are four main groups of beneficiaries of the proposed research. An immediate beneficiary will be academic members of the University of Liverpool working in the areas related to the proposed research, and the visiting researcher Prof. Segal from Ben-Gurion University, Israel. The cooperation proposed in the project will assure knowledge transfer between different areas of computer science and engineering, such as ad-hoc networks (VANET in particular), computational geometry and optimization (Prof. Segal), distributed algorithms and network communication (Dr. Kowalski), mobile graph exploration, randomised communication protocols, scheduling and game theory (other consulted CTAG members). This process includes 10 months of on-place collaboration within the Department of Computer Science at the University of Liverpool, where Prof. Segal will be visiting. If successful, the collaboration will be continued in the future through electronic communication means and mutual visits. Community of VANET researchers will benefit from new algorithmic techniques delivered in this project and distributed via publications, lectures and web pages. If successful, we plan to continue working on research directions addressed in this proposal in larger consortium, preferably gathering academic institutions and companies across European Union. We believe that bringing together experts in different, still related, areas of computer science and engineering will result in novel techniques inspiring for researchers in VANET community. Computer Science and Engineering communities will benefit from new links established between different areas of Computer Science and Engineering. Researchers involved in the proposal will distribute the new ideas, obtained as a result of wide-area collaboration, within their own research communities. In a long perspective, we believe that the impact of this project on understanding VANET environment and on development of practical VANET services will be substantial. It is likely that newly developed algorithmic methods will be tested and verified by other researchers in network community, and further implemented as parts of more complex future large-scale VANET systems. Efficient VANET systems, when implemented, will influence not only comfort of drivers and passengers, by providing even more useful services than before, but will also improve safety, traffic throughput and latency, and thus also energy saving and environmental protection.


10 25 50
publication icon
Chlebus B (2012) Adversarial Queuing on the Multiple Access Channel in ACM Transactions on Algorithms

publication icon
Cholvi V (2010) Bounds on Stability and Latency in Wireless Communication in IEEE Communications Letters

publication icon
Georgiou C (2013) Asynchronous gossip in Journal of the ACM

publication icon
Khabbazian M (2014) Decomposing broadcast algorithms using abstract MAC layers in Ad Hoc Networks

publication icon
Kowalski D (2013) Scheduling problems in transportation networks of line topology in Optimization Letters

Description Vehicular Ad-hoc NETworks (VANETs) are to provide communication between vehicles, and nearby roadside equipment, in order to improve both safety and comfort for the individual traffic participants and to enhance the capabilities of existing traffic management infrastructure. The concept of VANET is in its early stage of development, and despite of many efforts no fully-functioning prototype has been successfully implemented and tested yet. This is because VANET is a complex hybrid ad hoc large-scale communication and sensor network, integrated with traffic network and services. This project focused on studying selected aspects of VANET from theoretical perspective, in order to deliver more efficient communication protocols that can be applied to VANET and to discover the impact of information gathered through VANET to traffic management.
The project appeared very productive in terms of research output, especially when considering its short duration: 1 paper was already published in a journal, 8 papers were published in conference proceedings, 1 paper has been accepted for publication and another 2 manuscripts are under review. All the venues are peer-reviewed, some of them are considered very prestigious in the field, for example ACM VANET, IEEE ICDCS, ACM PODC, EATCS ICALP, and Distributed Computing.
All aims of the project have been successfully fulfilled.
Objective 1. We introduced several wireless communication algorithms and studied their properties and efficiency in various models related to VANET. The obtained results include:
- maintaining connected communication structure by using provably small number of frequencies [TAPAS'11],
- maintaining cluster-based structure and communication in steady traffic conditions [VANET´11],
- simultaneous multicast and aggregation with small time overhead by using network coding [PODC'11].
We also studied safety and comfort aspects of protocols, with respect to individual and social gains. In the area of safety, we focused on fast multi-broadcast and gathering short messages in structured wireless environment, and on reliability [DISC'10]. Comfort aspects included routing [ICALP'11], network stability [IEEE ComLet'11] and group communication with various privacy levels [ICDCS'11]. Finally, we rigorously analysed the impact of information gathered through VANET to traffic maintenance, which occurred substantial even for simple road structures; this analysis was carried out with respect to various performance measures, including optimising individual delays, global time for maintaining a large traffic burst, and total fuel consumption (which is also related to the total CO2 emission) [Two submitted manuscripts].
Objective 2. Most of the abovementioned solutions were distributed or semi-distributed, as stated in the objective. Unlike centralised architectures and protocols, distributed and semi-distributed ones are less prone to system failures, caused by high mobility of users, communication and node failures and malicious attacks, and therefore more desirable in practise.
Objective 3. In order to foster closer links between our theoretical study and challenges coming from practical attempts of deployment of VANET, we discussed our results with experts from V-Sence project at U. Cyprus and from CarTel project at MIT. We plan to keep this collaboration active in the near future, and additionally to discuss newly obtained algorithmic techniques and limitations with research labs of motor companies working on some aspects of VANET. Finally, the project strengthened the collaboration between researchers working on VANET at the U. Liverpool and at Ben-Gurion University.
Exploitation Route To be further studied by research community and companies interested in development of VANET.
Sectors Digital/Communication/Information Technologies (including Software),Transport

Description VANET 
Organisation Ben-Gurion University of the Negev
Country Israel 
Sector Academic/University 
PI Contribution Joint collaboration with Prof. Michael Segal and Yair Allouche. Prof. Kowalski's grant was used for hosting Prof. Segal's and Allouche's research visits at the U. Liverpool.
Collaborator Contribution Joint collaboration with Prof. Michael Segal and Yair Allouche.
Impact Joint papers on VANET and car scheduling listed in the portfolio and follow up works.
Start Year 2009