Optimal broadcast scheduling method for VANETs: An adaptive discrete firefly approach

Abstract

Vehicular Adhoc Networks (VANET) are thought-about as a mainstay in Intelligent Transportation System (ITS). For an efficient vehicular Adhoc network, broadcasting i.e. sharing a safety related message across all vehicles and infrastructure throughout the network is pivotal. Hence an efficient TDMA based MAC protocol for VANETs would serve the purpose of broadcast scheduling. At the same time, high mobility, influential traffic density, and an altering network topology makes it strenuous to form an efficient broadcast schedule. In this paper an evolutionary approach has been chosen to solve the broadcast scheduling problem in VANETs. The paper focusses on identifying an optimal solution with minimal TDMA frames and increased transmissions. These two parameters are the converging factor for the evolutionary algorithms employed. The proposed approach uses an Adaptive Discrete Firefly Algorithm (ADFA) for solving the Broadcast Scheduling Problem (BSP). The results are compared with traditional evolutionary approaches such as Genetic Algorithm and Cuckoo search algorithm. A mathematical analysis to find the probability of achieving a time slot is done using Markov Chain analysis.

Keywords

VANET evolutionary algorithm genetic algorithm cuckoo search firefly algorithm MAC protocol

1 Introduction

The ever-increasing emergency situations on a road through the world is the motivation factor for the development of Intelligent Transportation Systems (ITS) and several other advanced applications to improve safety of the driver and passengers. Vehicular Ad-hoc NETwork (VANET) is a communication network in which vehicles are fitted with an On-Board Unit (OBU), a networking device enabling the possibility of creating such safety applications. In VANET communication happens between two vehicles called the Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I). Countries around the world are looking out for traffic and road safety innovations. [1]. VANETs are mediated as a subclass of MANETs on the grounds of similarities between them. Mobility and dynamic network topology make VANETs different from MANETs.

Safety, Civil Service, traffic management, and infotainment are four broad categories of VANET applications. Safety application include status messages about dangerous situations ahead, bad road conditions, bad weather, curve speed, emergency vehicle warning, lane change etc. It also includes applications which monitor driver’s physical behavior such as facial expression, blink rate, heart rate etc., are collected to predict any drowsiness or fatigue in the driver’s body. The Civil Service applications include police, ambulance, VIP travel, usage of virtual sirens, traffic signal preemption etc. Traffic management essentially focusses on reducing traffic congestion on the road by updating the local information, street maps, availability of information related to stores/fuel stations/ Chemists etc., on the route. Finally, the infotainment comprises of entertainment services to the passengers by providing in vehicle internet connectivity, sharing media across vehicles, advertisements, electronic toll etc. In all of these applications broadcasting time sensitive and emergency messages information to the entire vehicular network becomes a crucial component for the efficient functioning of the applications [2].

In a broadcasting setup there is no single sink/target vehicle like tradition VANET where it is usually V2V or V2I. Alternatively the messages are broadcasted from an individual source node to each and every vehicle in a particular geographic location. During a normal broadcasting due to the constrained radio communication a lot of the vehicles may not receive the broadcasted packets in a single hop. Consequently, for improving the packet delivery to all nodes the network architecture requires a multi hop communication to cover all vehicles in the network as shown in Fig. 1. The Medium Access Control (MAC) for VANET administers for the required broadcasting among the vehicles. VANET characteristics such as rapidly changing topology, high node mobility, and QoS makes it difficult to design MAC protocols. Broadcasting problems has been addressed through various MAC protocols like Time Divisible Multiple Access (TDMA), Space division Multiple Access (SDMA), and Code Division Multiple Access (CDMA) [3]. This article focusses on employing a TDMA based protocol for broadcasting safety messages in a Vehicular Adhoc Network. The proposed approach employs evolutionary algorithm for optimizing the time slot scheduling in a TDMA based MAC protocol. The Main Contributions in the work are 1) employing meta-heuristic algorithms for solving optimal broadcast scheduling problem in TDMA based VANETs and 2) To design an Adaptive Discrete Firefly Algorithm (ADFA) for reducing the number of time frames and increasing the transmissions in the network. The rest of the article is organized in the following manner. The Next Section is about the related works in similar domains, followed by the formulation of the Broadcast Scheduling Problem (BSP) in VANETs. Evolutionary Approach for solving BSP is given in the next section. Mathematical Analysis and Simulation results for the proposed work is portrayed in the following section followed by conclusion and future work.

Fig. 1

Four lane Road Traffic.

2 Related work

The two classifications of MAC protocols are Contention-based and Contention-free. Every node shall compete with other nodes in the network in a contention-based situation to access the channel when it needs to transmit data. Contention-free protocols, however, expect a single node to access the channel at any given time and thus render it a collision-free process [1]. IEEE 802.11p [4] reflects a vehicle connectivity standard. IEEE 802.11p is a contention-based MAC protocol running on both Enhanced Distributed Channel Access (EDCA) and Carrier Sense Multiple Access with Collision Avoidance (CSMA / CA) access schemes. As it is a contention-based MAC, a broadcast function is not allowed without delay. In a System Free of Contention an innovative strategy for collision-free broadcasting and transmission without delay is implemented in [5]. It also uses Adaptive Broadcast Frame (ABF) which is further broken down into time slots. Each time a specific vehicle is allocated slot for collision-free transmission of safety messages. In [3] for VANETs, the authors have established a contention-free multichannel MAC protocol. Unlike DMMAC, VeMAC supports control channel (CCH) multi-hop broadcast service with a mechanism to prevent hidden terminal issues caused by the mobility of the vehicle.

[3] and [6] already have a fixed number of frames that do not fit well with VANET’s ever-changing, rapid topology. The number of frames either appears to be used sparsely or is not enough for the quantity needed. [3 and 7] decreases the risk of collision by designating separate time slots for vehicles traveling in the right and left directions and for RSUs. In [7] the length of the frame is dynamically multiplied or shortened as per the amount of traffic. It also uses a binary tree algorithm to decrease the chances of collisions during transmission [8]. Hybrid Efficient and Reliable MAC offers an infrastructure where vehicles can book a time slot during the contention-based reservation cycle or exchange a handshake WSA / RFS (WAVE Service Announcement / Service Request) 3-way. If a vehicle intends to use the service, the service provider must be given an RFS which will validate it with an ACK response. Upon receiving the ACK update, the nodes will exchange non-safety messages from the neighboring vehicles without any chance of collisions.

This paper considers VANET with TDMA, and pictures the topology as a line. Since it is regarded as a TDMA-based VANET it is important to allocate time slot schedule for increased transmission without collision. The question of broadcast scheduling is formulated using an evolutionary approach, taking into account the constraints of interference. The evolutionary approach would accomplish two things: a) Minimize the number of time frames, and b) Increasing the number of transmissions without interruption, i.e. increasing the network channel utilization factor. Several algorithms have already tackled the issue of broadcasting. Most broadcast scheduling issue works by planning a time slot schedule in which each node will be allocated one slot for transmission, and then re-formed depending on the node coordination. The broadcast scheduling problem has been shown to be NP complete [9, 10]. Evolutionary algorithms are seen in [9, 11] as being successful in solving problems such as routing protocols, topology management, broadcast scheduling. Evolutionary algorithms seem to have optimal solutions for NP - complete in most cases. Thus, an adaptive discrete firefly algorithm is implemented in the proposed approach, which is then tested with conventional evolutionary methods including the Genetic Algorithm (GA) and Cuckoo Search (CS).

3 Representation of VANET scheduler

The system model that was inspected includes a group of vehicles moving in both directions and a set of Road Side Units (RSU). Vehicle movement is divided into two categories, one from left to right and the other from right to left as shown in Fig. 2. In this proposition RSUs are known as non-directional immobile vehicles. The Vehicles communicate in the network through DSRC with a single transceiver that is embedded in a computer called the On-Board Unit (OBU) in the vehicle. The transceiver functions in seven different channels as stated earlier. Specifically, one channel for CCH which hosts safety messages with six other channels for SCH which houses miscellaneous services [19]. Global Positioning System (GPS) for location information and also for time synchronization with other vehicles and RSU is mounted in each and every car. Every vehicle’s MAC address is used to identify them inside the network. The vehicle network under study is considered to be a clustered network and the interval of synchronization between the cluster members and the head is 100 ms. In that 100 ms, 96 ms are the usage time and the remaining 4 ms is for the guard interval. This research focuses primarily on the control channel, as it carries critical and safety messages. As per the IEEE 802.11p / WAVE standard, this research uses a single transceiver too.

Fig. 2

Vehicle Directions.

The Channel is divided into time frames for a given slot composed mainly of fixed time length. The number of time slots per channel h_n is denoted by l_n, where n = 0, 1, 2 ... N. The Index is used to classify a particular slot on the channel. The channel is then split into three sets of time slots, ‘L’ for vehicles traveling in the left and ‘R’ for the right direction vehicles and ‘U’ for the RSUs. All the channels in the model are synchronized with slots, and they consist of time frames as shown in Fig. 3. Thus, at any given time, each node can determine its current slot index within the frame on any channel h_n, n = 0, 1, 2...N, and it can also determine whether it belongs to the setting of ‘L,’ ‘R,’ ‘U’ on channel c0.

Fig. 3

Time Frame for one synchronization interval.

In case of any signal failure in the GPS, the local GPS oscillator holds the synchronization with the nodes to a certain degree of precision. The specifics of such an occurrence and synchronization are beyond this paper’s reach.

The corresponding sets are prescribed for a given node a.

P(a) – One hop node neighbor on channel h₀, from which node a received packet on channel h₀ for slots l0 during the previous synchronization period

T(a) – The range of time slots in the channel that node a would avoid

VANET works as an undirected graph. G = (V, E), representing each single node as vertices V=1, 2,....., N. E represents the set of undirected edges symbolizing the total number of Vehicle Network transmissions. N denotes total vehicle number. Therefore, if an undirected edge e=(i, j) ∈ E remains in the network, two vehicles are in the contact range and are named out as one-hop apart. The second case is where (i,j) ∄ E, but a midway node k remains such that (i,k) ∈ E and (k, j), so the nodes i and j are considered two hop apart. Figure 4 is a sample vehicle network that is known as an undirected graph. Based on graph shown in Fig. 4 a collection of matrices for their use in evolutionary algorithms are created.

Fig. 4

A Sample Vehicular Network as an Undirected Graph.

$[RelM] = [\begin{matrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{matrix}]$

Here [RelM] represents the relation matrix for the graph depicted in Fig. 4. The Columns in the matrix represents the nodes in the network and the rows specify if there are any links in between the nodes. For example, the first row shows the connection information of Node A. Each cell representing a connection between two nodes receives a value of 1 and 0 if there is no connection. $[HopM] = [\begin{matrix} 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{matrix}]$

Hop Matrix [HopM] provides information about the hop for the network provided in Fig. 4. The one hop and two hop information among the nodes are defined in each row. $[SchM] = [\begin{matrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \end{matrix}]$

The Scheduler Matrix (SchM) is in the MxN matrix form where time frames are denoted by M and total number of nodes are represented with N. Each row and column correspond to time slot and node transmission.

4 Evolutionary approach for solving Broadcast Scheduling Problem (BSP) in vanet

The encouragement to use an evolutionary approach in VANET to solve BSP is based on its ability to solve traditional scheduling issues. Scheduling problems as stated in the problem of traveling salesman (TSP) [12], the scheduling of job shops [13] and the scheduling of flow shops [14] used an evolutionary approach to solving the common problems listed above. The findings of these literatures gave rise to a clear willingness to use an evolutionary method in VANET to solve BSP. This article proposes an Adaptive Discrete Firefly Algorithm (ADFA) which helps in achieving the optimal solution for a discrete multi objective scheduling problem.

A. Firefly Algorithm (FA)

Firefly Algorithm (FA) is a meta-heuristic algorithm developed according to Fireflies’ flashing actions. With the standard Firefly Algorithm, we implement an adaptive, discrete mechanism to compress time frames and boost the number of transmissions at almost the same time. According to [16] FA uses two essential assumptions as mentioned below The fireflies are considered unisex and drawn to one another regardless of their sex The attractiveness is determined by the brightness which is proportional to the fitness function.

4.1 Movement

Every firefly l moves towards a more attractive firefly k. Every firefly movement is determined by the $X_{k} = X_{k} + β_{o} e^{- γ r_{kl}^{2}} (X_{l} - X_{k}) + (rand - \frac{1}{2})$ (1)

4.2 Distance

The interval between every two fireflies is estimated by their cartesian distance. It is given below for two fireflies k and l at X_k and X_l $C_{kl} = | | X_{k} - X_{l} | | = \sqrt{\sum_{k = 1}^{d} {(X_{k, o} - X_{l, o})}^{2}}$ (2)

4.3 Attractiveness

One of the major aspects of firefly algorithm is the movement of firefly algorithms based on each other’s attractiveness. Each firefly has its own attractiveness. Lesser attractive fireflies move towards more attractive fireflies and this way the optimal solution is identified. A firefly’s attractivity is directly proportional to its light intensity. It is computed by using the following equation $β (r) = β_{o} e^{- γ r^{2}}$ (3)

5 Proposed adaptive discrete firefly algorithm (ADFA)

Firefly algorithm was initially designed to solve continuous optimization problems. For BSP problem the regular firefly algorithm cannot be used. Therefore, we use and engage Smallest Position Value (SPV) rule generated by Bean [17] to solve BSP which is a discrete problem of optimization. Upon turning it into a discrete solution, an adaptive module is proposed including a moderator and harmonizer to further reduce the time frames and increase transmissions for VANET based on TDMA.

5.1 Solution Representation for ADFA

The solution was defined in discrete process form. The population is generated with a random permutation of prime numbers, where the nodes are then placed with the hop matrix reference in the respective frames. This reduces the generation of infeasible solutions in binary representation. The SPV rule is being used to assign the fireflies’ continuous location values within the time frame in the slots. After the preparation of matrix which depicts the scheduler matrix, a moderator definition is implemented with the goal of increasing the number of transmissions between nodes within the frames obtained.

That solution’s representation consists of D dimensions, where D represents the number of nodes in the network. Any solution within the population can be described as ${Indv}_{i} = {N_{1}, \dots, N_{D}}$ where i represents the current solution and N represents the node number.

5.2 Population Initialization

The total population can be represented as ${Pop}_{t} = {{Indv}_{1}, \dots {indv}_{i}, \dots, {Indv}_{| pop |}}$ where t refers the iteration number, | | represents the cardinality. The representation of each individual can be generated using random numbers of prime numbers with varying magnitudes. The quality of random numbers is paramount for the results of any stochastic algorithm. After initialization of all individuals in the population, the individuals are then represented in the form of matrix for generating scheduler matrix as found in Algorithm 1

Algorithm 1 Pseudocode for Generating Scheduler Matrix
for eachIndv in Popdo
Initialize the 1st frame (F₁)
Insert the 1st node N₁ of Indv_i
for each node N -1 in Indv_ido
if (N_i ∉ F_n) then
Insert N_i in F_n
else
Insert F_n+1
end if
end for
Indv_i ← randperm (\|N\|)
end for

5.3 Light Intensity

The light intensity is an indicator of a firefly’s brightness. The Light Intensity value depends on the problem’s fitness function. Since the purpose of TDMA scheduling is to decrease the number of frames the fitness function will be based on channel utilization for the entire network and for a particular time slot. The channel utilization as mentioned in eq. 10 will be used to reduce the time frames if the utilization is less.

5.4 Distance

In general, the cartesian distance between two fireflies will be treated as the distance for continuous optimization problems. However, for discrete problems the distance between two fireflies is considered to be an existence of edge between two nodes. This information can be got from the Hop Matrix [HopM] for the assumed network

5.5 Attractiveness

Attractiveness is dependent on the light intensity which is related to the fitness function. For any two fireflies initially, the distance is calculated i.e. the existence of a link between two nodes. Consequently, the fitness function is used to identify the channel utilization variable and slots are assigned based on it. For example, if the channel utilization is less, then a node is assigned a slot, provided there is no interference from its neighbors. The Algorithm flow is mentioned in Algorithm 2.

5.6 Moderator (MD)

ADFA’s Moderator Step decreases the number of time slots by deciding the channel use for each node. σ_x is node x output in the current population, i.e. the total number of node x transmissions in the given time slot is defined using Equation (14). The moderator determines whether a node j transmits in any other time slot. In the time slot j if σ_x then that particular row is omitted. This process generates population with a minimum number of time slots, with the restriction that each node transmits at least once in that TDMA frame.

5.7 Harmonizer (HM)

The Step of the Harmonizer takes feedback from the moderator process. The harmonizer’s job is to increase the transmission number. The harmonizer takes the information from the hop matrix and identifies all possible time slots in the time slot as specified in Algorithm 2 without any intervention and breach in constraints and schedules.

5.8 Updating Solution

Each firefly uses permutation to evaluate and determine the objective value of the feature. The objective function of each firefly matches the particular firefly’s light intensity. Each firefly has its own attraction. Then the movement of firefly is calculated by Equation (4) and the fitness function is used to adjust the attractiveness. The above-mentioned steps are iterated till the max generation or the termination criterion is achieved.

Algorithm 2 Adaptive Discrete Firefly Algorithm
Objective Function f(x), x = (x_1, ... ... ... x_n)^T
Initialize n i.e. Total no. of nodes/fireflies
Population Initialization (Pop)
Pop_t ={ Indv₁, … indv_i, …, Indv_\|pop\| }
Light Intensity I_i at x_i is determined by f(x_i)
Define Light absorption coefficient γ determined byσ_x
Until max generation is reached
for i = 1:n
for j = 1:i
if (I_j > I_i)
Move firefly i towards j
end if
Attractiveness varies with distance
MD = Moderator (σ_x, Pop)
HM = Harmonizer([HopM], MD)
Evaluate fitness
Check for interference and assign available slot
Form new solutions and update light intensity
end for j
end for i
Rank the fireflies and identify the current best
end

6 Mathematical analysis

For proving the proposed approach mathematically, we have selected Markov chain problem which is known for solving occupancy problem as mentioned in [18]. The aim of this mathematical analysis is to determine the probability distribution of how each vehicle/node get distributed in the time slots given. Let’s start by specifying that n nodes are included in the time frame within the RSU coverage that contend for m slots. Let X_m be the number of active nodes which occupy slots of m time. Alternatively, we apply Markov Chain as shown in Fig. 5, with the following probabilities for transformation $P_{i, j} = {\begin{matrix} \frac{W (N, n, m)}{m^{n}} i = 0, 0 \leq N \leq n \\ \frac{W (N - i, n - i, n - i)}{(n - i)^{n - i}} 0 \leq i \leq n - 1, i \leq j \leq n \\ 1 i = N - n \end{matrix}$

Fig. 5

Markov Chain.

When n > m $W (N, n, m) = 0 m = n$ (4) $\begin{matrix} W (N, n, m) = ∁_{N}^{n} ∁_{N}^{m} M! \\ [{(m - N)}^{n - N} - \sum_{x = 1}^{\hat{N}} W (x; n - N, m - N)] 0 \leq m \leq n \end{matrix}$ (5)

Where $\hat{N} = \min (n - N, m - N)$

It is assumed that there are N nodes which needs to find a time slot m. Hence there are $∁_{N}^{n}$ ways for choosing those n contending nodes from the total available N nodes. Also, there are $∁_{N}^{m}$ ways for choosing N nodes to occupy the m time slots. For those M time frames there are M! distinct ways of permutation. Furthermore, there are n - N nodes to be distributed in the m - N time slots resulting in (m - N) ^n-N distinct ways. In order to make sure that there are exactly N nodes having a minimum of one time slot we make sure that patterns corresponding to at least one of the remaining m - N time slots should be subtracted. Hence, we do the recursive equation shown in Equation (5).

The average number of nodes that access a time slot m with M frames successfully is then given below $\bar{a} = \sum_{i = 0}^{n} {iP}_{1, i + 1}^{m}$ (6)

Finally, the following equation helps us to obtain an average normalized throughput for M time frames $θ_{n} = \frac{\bar{a}}{f_{M}}$ (7)

Where f_M is the length of the time frame M

Fig. 6 depicts the average number of nodes acquiring a time slot within M frames. In ADFA it is evident from the graph that all nodes obtain a time slot in a minimal number of frames when compared to the benchmarked approaches such as VeMAC, ADHOC, and TDMA-CCA. VeMAC tends to suffer when the contending nodes are greater than the available time slots. This scenario is handled in the proposed system by estimating the number of vehicles in the RSU coverage and either increase or decrease the frame length to cater to the needs of the nodes. Due to the same reason ADFA performs better in normalized throughput as seen in Fig. 7.

Fig. 6

Average number of nodes acquiring a time slot within n frames.

Fig. 7

Average Normalized Throughput.

7 Simulation results

The performance of the proposed approach was evaluated using a series of simulations in comparison with three competent and very efficient protocols. VeMAC [3], TDMA-CCA [19], and ADHOC [6] are the three protocols to which we would compare our proposed ADFA approach. The Simulation Parameters are given in Table 1.

Table 1
Simulation Parameters

Parameter Value

Direction/Lane 2

Transmission Range 200 m

Synchronization Interval 100 ms

Guard Interval 4 ms

Selection Rank based method

Crossover Two Point Crossover

Mutation Probability 0.3

Termination Hybrid Stopping criterion or 500 Generation

Parameter	Value
Direction/Lane	2
Transmission Range	200 m
Synchronization Interval	100 ms
Guard Interval	4 ms
Selection	Rank based method
Crossover	Two Point Crossover
Mutation Probability	0.3
Termination	Hybrid Stopping criterion or 500 Generation

The simulation was carried out in two phases. The first was the VANET simulation for which OpenStreet Map was used to get real time traffic data and it was imported in SUMO. The traffic models were generated in SUMO and given to MATLAB as connectivity Matrix. This connectivity Matrix is then used for identifying the optimal solution in the evolutionary optimization phase. The simulation architecture is given below in Fig. 8.

Fig. 8

Simulation Architecture for solving BSP in VANET.

Given the above consideration in section 3, a NxN symmetric communication matrix can be used to explain the vehicle adhoc network C = (c_ij), which is defined as given below $c_{ij} = {\begin{matrix} 1, if hosts i, j are one hop away \\ 0, otherwise \end{matrix}$ (8)

The matrix D = (d_ij) is obtained from matrix C and defined as compatibility matrix. $d_{ij} = {\begin{matrix} 1, if hosts i, j are one hop or two hop away \\ 0, otherwise \end{matrix}$ (9)

The defined solution should provide a TDMA frame for the scheduling problem which is conflict-free and satisfies the packet transmission constraints. It is therefore assumed that there are m time slots in each time frame and that a MxN binary matrix Y = (y_mj) is used to indicate a TDMA frame where each element is defined as below. $y_{mj} = {\begin{matrix} 1, if mth slot to be assigned to host j \\ 0, otherwise \end{matrix}$ (10)

For the entire vehicle adhoc network, the time slot utilization index ρ is provided with all these definitions. The following equation is determined for ρ $ρ = \frac{1}{M \times N} \sum_{m = 1}^{M} \sum_{j = 1}^{N} y_{mj}$ (11)

The goal of the equation is to find an optimum TDMA period with minimal frame length M and maximum slot utilization index ρ, which is said to be a issue for VANETs with Optimum Broadcast Scheduling (OBS). To be more precise, the problem with OBS could be defined as below

Truncate M and Improve ρ, depending on $\sum_{m = 1}^{M} y_{mj} ⩾ 1, \forall j$ (12) $\sum_{m = 1}^{M} \sum_{i = 1}^{N} \sum_{j = 1}^{N} y_{mi} y_{mj} d_{ij} = 0$ (13)

As stated earlier, in equation (11) the no transmission restriction is given. This equation makes sure that a minimum of one time slot for transmission is allocated for each vehicle in the network. The free constraint of conflict is given in equation (12). This equation guarantees that in specific time slots every two vehicle nodes away from which one hop and two hops are to be transmitted. For Vehicle Adhoc networks, the TDMA frame length depends on the network’s adaptive mobility, and is conceptually demanding due to its NP completeness, as stated in [20]. The maximum degree of a host G is used in the given network to find a tightly lower bound of the frame length M as shown below $M ⩾ G + 1$ (14)

The Utilization for a particular node is identified with the equation given below. $σ_{x} = \sum_{i = 1}^{| M |} [{SM}_{ix}]$ (15) $ρ_{x} = \frac{σ_{x}}{| M |}$ (16)

Several Vehicular networks were generated in random with variable degree and nodes to test the proposed approach. The algorithm was run for 100 times for each particular setting, with a population size of 50, maximum generation of 500 and the results average was reported in Tables 2, 3, and 4.

Table 2

Results from Genetic Algorithm (GA)

No. of Nodes	No. of Links	Average Degree	Average ND	Maximum ND	Minimum TDMA Frame Length	Average ρ	Average No. of Generations	Computation Time
15	25	3.3	4	6	7	0.219	30.6	0.8
30	60	4	4	8	9	0.199	95.1	1.05 min
50	100	4	6	8	9	0.173	157	5.42 min
100	200	4	7.5	10	10	0.159	421	36.28 min
100	300	6	7	8	9	0.116	422	36.21 min

Table 3

Results from Cuckoo Search (CS) Algorithm

No. of Nodes	No. of Links	Average Degree	Average ND	Maximum ND	Minimum TDMA Frame Length	Average ρ	Average No. of Generations	Computation Time
15	25	3.3	4	6	7	0.244	15.03	1.23 min
30	60	4	4	8	9	0.236	22.2	3.42 min
50	100	4	6	8	9	0.235	29.54	6.58 min
100	200	4	7.5	10	10	0.185	42.5	17.26 min
100	300	6	7	8	9	0.154	45.43	17.56 min
200	400	4	8	10	10	0.163	119	35.47 min
300	600	4	7	10	10	0.202	186	49.25 min
400	800	4	12	16	15	0.176	264	75.39 min
500	1000	4	9	14	14	0.132	312	89.41 min

Table 4

Results from Adaptive Discrete Firefly Algorithm (ADFA)

No. of Nodes	No. of Links	Average Degree	Average ND	Maximum ND	Minimum TDMA Frame Length	Average ρ	Average No. of Generations	Computation Time
15	25	3.3	4	6	7	0.279	3.9	0.51 s
30	60	4	4	8	9	0.256	4.85	6.5 s
50	100	4	6	8	9	0.241	6.08	11.5 s
100	200	4	7.5	10	10	0.203	15.7	1.11 min
100	300	6	7	8	9	0.163	18.47	1.26 min
200	400	4	8	10	10	0.195	28.9	8.52 min
300	600	4	7	10	10	0.228	51.6	16.5 min
400	800	4	12	16	15	0.194	59.42	50.6 min
500	1000	4	9	14	14	0.158	86.5	70.4 min

The number of nodes taken for simulation ranges from 15 to 100 for all three experiments. Table 2. depicts the results of Genetic Algorithm. As seen from Table 2, GA finishes with a decent number of generations and more number of transmissions. However, as the number of nodes and links increase GA takes about 36 mins for a 100-node network with 200 links. This could not be a very suitable solution for the problem. In Table 3 comparing the cuckoo search algorithm results with GA in Table 2 the number of generations is reduced along with an increase in average number of transmission for various number of nodes. Cuckoo search algorithm fares well in the number of generations and transmission, however running time for large networks is still on the higher side. From Table 2 and 3 it is evident that the Cuckoo search algorithm has increased channel use over a reduced number of generations. Table 4 displays average channel efficiency, average number of generations and computation duration of different vehicle networks using our proposed ADFA method. The time taken for a 100-node network in ADFA is 1.11 min when compared to the 17.26 min and 36.28 min for CS and GA respectively for the same network. It is evident that ADFA is the most efficient with respect to computation time Fig. 9 depicts the comparison of average time taken between GA, CS and ADFA. It is visible that ADFA outperforms in comparison with the other two algorithms. Cuckoo stands ahead with maximum computational time in all the instances except 100 instances dataset. The reason for high computational time is due to the function evaluation. In cuckoo, the functional evaluation of individuals happens twice whereas it is just once for every iteration in Firefly and GA. However, GA displays lesser time for small instances and it grows exponentially as the size of the nodes and links increases. It is also observed from Fig. 10 ADFA achieves the optimal solution in a much lesser generation than GA and CS.

Fig. 9

Comparison of computation time taken for identifying optimal solution.

Fig. 10

Average Generations taken for identifying optimal solution.

ADHOC MAC, IEEE 802.11p, TDMA-CCA, VeMAC are taken for benchmarking the results with evolutionary approaches for solving TDMA BSP. Figure 11 shows that ADFA is the most efficient of all the approaches with maximum channel utilization.

Fig. 11

Channel Utilization comparison with existing systems.

Figure 12, shows the comparison of GA, Cuckoo and ADFA in terms of fitness value. Fitness value is calculated with the number of frames and number of columns in the scheduler matrix along with the number of transmission lines in the scheduler matrix. Maximum number of transmissions in minimum number of frames holds maximum fitness value.

Fig. 12

Comparison of Fitness Value between GA, CS and ADFA.

A. Experiment Testing

We have considered a sample 30 node network as shown in Fig. 13a with 47 edges and with maximum node degree of 6. Hence as seen in Fig. 13b the optimal schedule is achieved using firefly algorithm in a minimal 7 frames and an increased transmission of 42 with a channel utilization index ρ of 0.2 for the network in consideration.

Fig. 13a

A Sample network with 30 nodes and 47 edges.

Fig. 13b

Optimal solution identified for the same network.

Table 5 showcases the results achieved at two instances. The first instance (#1) is with 30 nodes and 87 edges and the second instance (#2) is 40 nodes with 62 edges. The table portrays the results of time slots, channel utlization and computation time. The results are compared with ADHOC MAC [3], IEEE 802.11p [19], TDMA-CCA [19] and VeMAC [3].

Table 5

Comparison of GA, CS, ADFA with other competitive algorithms in terms of time slot |M|, channel utilization ρ and Computation Time

Instance	Parameter	AD-HOC MAC	IEEE 802.11p	TDMA-CCA	VeMAC	GA	CS	ADFA
#1	\|M\|	12	11	10	10	9	9	9
	ρ	0.023	0.041	0.141	0.121	0.198	0.236	0.258
	Computation Time	–	–	–	–	65 s	204 s	6.5 s
#2	\|M\|	10	9	9	9	8	8	8
	ρ	0.019	0.031	0.138	0.131	0.188	0.233	0.252
	Computation Time	–	–	–	–	58 s	198 s	6 s

8 Conclusion

The genetic algorithm, Cuckoo search and firefly algorithm were discussed to solve the broadcast scheduling problem in VANET. Compared with GA and CS, ADFA seems to be efficient than the other two competitiors. However the results have also shown that evolutionary approach seems to be slightly better that non-evolutionary approaches. However on employing an evolutionary approach for a dynamic Vehicular Adhoc Network brought about the decision of computation time in to the equation. The results again suggest that evolutionary algorithm for a medium sized network provides an optimal solution at a minimal computation time. The outcome validates the effectiveness and efficiency of ADFA for the broadcast scheduling problem in VANET. Further enhancement can be done to reduce computation time even for large networks.

References

Hadded

, Laouiti

, Muhlethaler

and Saidane

, An Infrastructure-Free SlotAssignmentAlgorithmfor Reliable Broadcast of Periodic Messages in Vehicular Ad Hoc Networks. 2016 IEEE 84Th Vehicular Technology Conference (VTC-Fall). (2016).

Awang

, Husain

, Kamel

and Aissa

, Routing in Vehicular Ad-hoc Networks: A Survey on Single- and Cross-Layer Design Techniques, and Perspectives, IEEE Access 5 (2017), 9497–9517.

Omar

, Zhuang

and Li

, VeMAC: A TDMA-Based MAC Protocol for Reliable Broadcast in VANETs, IEEE Transactions on Mobile Computing 12(9) (2013), 1724–1736.

802.11p-2010 - IEEE Standard for Information technology–Local and metropolitan area networks–Specific requirements–Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 6:Wireless Access in Vehicular Environments - IEEE Standard. (2017). Ieeexplore.ieee.org. Retrieved 28 November (2017).

, Ji

, Liu

and Wang

, A Dedicated Multi-Channel MAC Protocol Design for VANET with Adaptive Broadcasting, 2010 IEEE Wireless Communication and Networking Conference. (2010).

Borgonovo

, Capone

, Cesana

and Fratta

, ADHOC MAC: New MAC Architecture for Ad Hoc Networks Providing Efficient and Reliable Point-to-Point and Broadcast Services, Wireless Networks 10(4) (2004), 359–366.

, Weidong

, Pan

and Hongsong

, Adecentralized adaptive TDMA scheduling strategy for VANET, Wireless Communications and Networking Conference Workshops (WCNCW), 2013 IEEE. (2013).

Minh Dan

, Ngoc Dang

, Nguyen

, Htike

and Seon Hong

, HER-MAC: A Hybrid Efficient and Reliable MAC for Vehicular Ad hoc Networks, IEEE 28Th International Conference on Advanced Information Networking and Applications. (2014).

Arivudainambi

and Rekha

, An evolutionary algorithm for broadcast scheduling in wireless multihop networks, Wireless Networks 18(7) (2013), 787–798.

10.

Arivudainambi

and Rekha

, Memetic algorithm for minimum energy broadcast problem in wireless ad hoc networks, Swarm and Evolutionary Computation 12 (2013), 57–64.

11.

Reina

, Ruiz

, Ciobanu

, Toral

, Dorronsoro

and Dobre

, A Survey on the Application of Evolutionary Algorithms for Mobile Multihop Ad Hoc Network Optimization Problems, International Journal of Distributed Sensor Networks 12(2) (2016), 2082496.

12.

Potvin

J.-Y.

, Genetic algorithms for the traveling salesman problem, Annals of Operations Research 63(3) (1996), 337–370.

13.

Wang

and Zheng

, An effective hybrid optimization strategy for job-shop scheduling problems, Computers & Operations Research 28(6) (2001), 585–596.

14.

Iyer

and Saxena

, Improved genetic algorithm for the permutation flowshop scheduling problem, Computers & Operations Research 31(4) (2004), 593–606.

15.

Chakraborty

, Chakraborty

and Shiratori

, A heuristic algorithm for optimum transmission schedule in broadcast packet radio networks, Computer Communications 28(1) (2005), 74–85.

16.

C. Search and F. Algorithm, Studies in Computational Intelligence. (2014).

17.

Tasgetiren

, Chen

, Gencyilmaz

and Gattoufi

, Smallest Position Value Approach. In Differential Evolution: A Handbook for Global Permutation-Based Combinatorial Optimization (pp. 121–138). Springer Verlag. (2009).

18.

Wen

and Wang

, A recursive solution to an occupancy problem resulting from TDM radio communication application, Applied Mathematics And Computation 101(1) (1999), 1–3.

19.

Yang

, Liu

, Li

and Sun

, TDMA-Based Control Channel Access for IEEE 802.11p in VANETs, International Journal of Distributed Sensor Networks 10(8) (2014), 579791.

20.

Ephremides

and Truong

T.V.

, Scheduling broadcasts in multihop radio networks, IEEE Transactions on Communications 38(4) (1990), 456–460. doi: 10.1109/26.52656

21.

Hadded

, Muhlethaler

, Laouiti

and Saidane

, A Centralized TDMA based Scheduling Algorithm for Real-Time Communications in Vehicular Ad Hoc Networks. In 24th International Conference on Software, Telecommunications and Computer Networks (SoftCOM). Split, Croatia: IEEE. (2016).

Optimal broadcast scheduling method for VANETs: An adaptive discrete firefly approach

Abstract

Keywords

1 Introduction

3 Representation of VANET scheduler

4.1 Movement

5.1 Solution Representation for ADFA

5.2 Population Initialization

5.3 Light Intensity

5.4 Distance

5.5 Attractiveness

5.6 Moderator (MD)

5.7 Harmonizer (HM)

5.8 Updating Solution

6 Mathematical analysis

Table 1 Simulation Parameters Parameter Value Direction/Lane 2 Transmission Range 200 m Synchronization Interval 100 ms Guard Interval 4 ms Selection Rank based method Crossover Two Point Crossover Mutation Probability 0.3 Termination Hybrid Stopping criterion or 500 Generation

References

Table 1
Simulation Parameters

Parameter Value

Direction/Lane 2

Transmission Range 200 m

Synchronization Interval 100 ms

Guard Interval 4 ms

Selection Rank based method

Crossover Two Point Crossover

Mutation Probability 0.3

Termination Hybrid Stopping criterion or 500 Generation