Multicast routing under quality of service constraints for vehicular ad hoc networks: mathematical formulation and a relax‐and‐fix heuristic

• Author: Cid C. de Souza,Tiago de A. Santos,Celso C. Ribeiro
• DOI: http://doi.org/10.1111/itor.12605
• Date: 01 July 2019
• Published date: 01 July 2019

Intl. Trans. in Op. Res. 26 (2019) 1339–1364

DOI: 10.1111/itor.12605

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Multicast routing under quality of service constraints

for vehicular ad hoc networks: mathematical formulation

and a relax-and-fix heuristic

Celso C. Ribeiroa, Tiago de A. Santosa,b,†and Cid C. de Souzac,∗

aInstitute of Computing, Universidade FederalFluminense, Niter ´

oi, RJ 24210-346, Brazil

bInstituto Federal de Educac¸˜

ao, Ciˆ

encia e Tecnologia Fluminense, Campos dos Goytacazes,RJ 28030-130, Brazil

cInstitute of Computing, University of Campinas (UNICAMP), Campinas, SP, Brazil

E-mail: celso@ic.uff.br [Ribeiro]; cid@ic.unicamp.br [de Souza]

Received 20 July2018; received in revised form 30 October 2018; accepted 31 October 2018

Abstract

In this paper, we investigate a multicast routing problem with quality of service constraints on ad hoc

vehicular networks.An integer programming formulation for the problemis proposed that forms the basis of

a relax-and-fix heuristic designed with the goal of producing feasible solutions of good quality. In addition,

preprocessing procedures relying on simple and constrained shortest paths are developed that reduce the

model size to the point of making it viable to compute. Computational experiments on benchmark instances

generated to mimic realistic settings are reported. The results highlight the effectiveness of the relax-and-fix

heuristic and the importance of the preprocessing routinesfor the computability of the proposed mathematical

model.

Keywords:multicast routing; quality of service; vehicular networks; ad hoc networks;integer programming; relax-and-fix;

heuristics

1. Introduction

Advances in wireless technologies have contributed to the emergence of mobile ad hoc networks

(MANETs). A MANET is an autoconfigured network consisting of a collection of wireless mobile

nodes independently linked one to another without the need of any infrastructure. Usually these

nodes are personal computer devices, small mobile devices, sensors, and cell phones, among others.

With the expansion of mobile technologies, the design of intelligent transport has attracted the

attention of many researchers and industries that aim to provide such types of technologies. Among

∗Corresponding author.

†Tiago de A. Santos passed away on 5 June 2018 at the time of writing of this article.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1340 C. C. Ribeiro et al. / Intl. Trans. in Op. Res. 26 (2019) 1339–1364

the most important intelligent transport systems are ad hoc vehicular networks or VANETs (Bitam

and Mellouk, 2013). A VANET is a type of MANET where nodes are vehicles. There are two types

of communication in VANETs: between vehicles (V2V—vehicleto vehicle) and between vehicles and

infrastructured nodes (V2I—vehicle to infrastructure), also called RSU (roadside unit). Karim (2008)

showed that VANETs are more suitable for vehicular communication because they have lower costs

of implementation and communication even in places where there is no infrastructure. In addition,

VANETs also have lower latency in data delivery when compared to other technologies such as

3G/4G networks and infostations.

One possible application of VANETs consists in assisting vehicles to communicateand coordinate

with each other, with the aim of avoiding any type of critical situation such as road accidents, traffic

jams, and poor roads, as well as other applications such as speed control, detailed information on

accidents for rescue teams, free passage of vehicles, and invisible obstacles. Another category of

applications is information and entertainment for passengers and drivers. These are called applica-

tions for the comfort of drivers and passengers, such as Internet access, chats and interactive games

between cars next to each other, free places for parking, and detailed information on fuel price,

among others.

In view of their high node mobility, the protocols of routing in vehicular ad hoc networks must

be properly adapted and offer optimized routing. According to Peterson and Davie (2012), in

a communication network there are three fundamental methods for data transmission: unicast,

broadcast, and multicast. The multicast routing strategy reduces the communication cost and

strongly explores the bandwidth and network resources, since the data packets can be transmitted

to all destinations (members of the multicast group) by a single transmission, while with the unicast

routing the source node sequentiallytransmits the same packet several times to different destinations

and with the broadcast routing the source node transmits to all nodes in the network, whether they

are interested or not in the message.

In a VANET, as well as in other types of networks, many applications have special requirements

in terms of network resources. The use of such special requirements is directly related to the quality

of service (QoS). According to Oliveira and Pardalos (2011), in many applications it is extremely

important to maintain high levels of service quality from the Web. For example, security-related

applications, such as crash warning messages, accidents, or poor track conditions, are sensitive to

delayed delivery of messages, as well as multimedia applications are sensitive to the bandwidth.

Among the most important requirements, we find the end-to-end delay, the jitter (i.e., the variation

in delay between messages with the same destination), the variation in delay between different

destinations, the bandwidth, the number of hops between the source and the destination, and the

duration of the connection.

In this work, we introduce an integer programming (IP) formulation for the multicast routing

problem with QoS constraints on VANETs and present a relax-and-fix heuristic for solving the

problem. Realistic test problems are generated and computational experiments are reported. This

article is organized as follows. In the next section, we present a review of the literature on the

problem of multicast routing with QoS constraints applied to VANETs. Section 3 introduces an

integer programming model forthe multicast routing problem with QoS constraints (MRPQOS)based

on a multicommodity flow formulation. We also describe how instances were generated to validate

the formulation, and reporton preliminary results obtained by a mathematical solver that computes

the model. Section 4 details preprocessing strategies for model reduction, i.e., procedures capable

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies