An Intelligent Scheme for Slot Reservation in Vehicular Ad Hoc Networks

Surjeet ,Priyanka Bhardwaj,Raghavendra Pal,Nishu Gupta

1 Department of Electronics and Communication Engineering,Bharati Vidyapeeth’s College of Engineering,New Delhi,India

2 Department of Electronics and Communication Engineering,ABES Engineering College,Ghaziabad,India

3 Department of Electronics Engineering,Sardar Vallabhbhai National Institute of Technology,Surat,India

4 Department of Electronics and Communication Engineering,Chandigarh University,Mohali,India

Abstract: Vehicular ad hoc network is a solution for increasing road traffic demand.Non-safety messages are sent during the service channel interval.The slots during which the messages are sent are not decided prior to the transmission.If the reservation of slots is done during the control channel interval,then the non-safety messages can be transmitted without any collision and thus the network performance can be improved.Further,to improve the network performance,the safety packets can be scheduled in the queue according to the time remaining for which sender and receiver are in the range of each other.This work proposes and evaluates the performance of safety message scheduling and infotainment message reservation through a MAC protocol SSIR-MAC to ensure network stability by transmitting beacons without any collision.The safety messages are queued according to their deadline and the slots for the transmission of non-safety packets are reserved during the control channel itself.Further,a hybrid queue is proposed to decrease the delay of enqueue and dequeue operations.Evaluation through extensive simulation results demonstrates the strength of SSIR-MAC.Comparisons are made with IEEE 802.11p standard and with two existing protocols which are relevant to the proposed work.

Keywords:channel switching;DSRC;IEEE 802.11p;ITS;MAC;safety;scheduling;VANET

I.INTRODUCTION

Increasing traffic on roads has made accidents and traffic jams more common.Researchers are looking for solutions other than constructing roads,highways and flyovers.Connecting vehicles with each other can be a solution to cater the needs of increasing traffic demand.Vehicular Ad hoc Network(VANET)connects vehicles moving on road to each other and with some infrastructure made up of roadside units(RSUs).The vehicles can communicate with each other and alert other vehicles in case of any emergency and thus can avoid road accidents.VANET has different characteristics than Mobile Ad hoc Network(MANET)such as frequently changing environment and high mobility of vehicles.Due to this reason,existing Physical(PHY)layer and Medium Access Control (MAC) layer parameters and protocols are not sufficient enough to take care of VANET communication.IEEE has defined IEEE 802.11p [1]standard that is a combination of IEEE 802.11a and IEEE 802.11e[2]standards.IEEE 802.11p is a standard for PHY and MAC layers that take care of the needs of vehicular communication considering its mobility and frequently changing environment.Messages in VANET are classified into two categories,one is safety messages,and another is non-safety messages.There are further some subcategories of both types of categories.The safety messages should be given priority over nonsafety messages.We attempt to analyse how reliable and time-bound dissemination of safety messages in multichannel VANET environment can be guaranteed.United States Federal Communication Commission(FCC) has allotted a 75 MHz bandwidth in 5.9 GHz band[1]for the VANET.It consists of seven channels of 10 MHz each and 5 MHz is reserved for guard band to avoid interference with nearby bands.One of these seven channels is called Control Channel (CCH) that is used for transmission of safety messages and other six are called Service Channels (SCHs) that are used to transmit non-safety messages.Since VANET is an ad hoc network,it does not have any centralized coordinator.Hence,there should be some mechanism that can control when to transmit safety messages and when to transmit non-safety messages.For this purpose,IEEE has defined IEEE 1609 standard to enable Wireless Access in Vehicular Environment (WAVE)[3].IEEE 1609.4 suggests a multichannel MAC mechanism that divides the network time into 100msec intervals called synchronization interval (SI).SI is further divided into two parts; one is Control Channel Interval (CCHI) and another is Service Channel Interval (SCHI).CCH is used during CCHI and SCHs are used during SCHI.CCH is also used to transmit beacons.Beacons are sent periodically by all the vehicles in the network so that each vehicle becomes aware of its neighbour vehicles and their characteristics such as position speed etc.The safety message should be given priority over non-safety messages.However,safety messages are further divided into subcategories.These subcategories should be given different priorities.Safety messages whose deadline is near should be given higher priority over other safety messages because if safety message is transmitted after the deadline,it may lose its significance.Further,the packets are scheduled in a linked list according to their priorities.The packets in the queue are rescheduled whenever a new packet arrives at the vehicle.This causes frequent scheduling of the queue.Due to this frequent rescheduling,queuing time is increased.However,this time can be reduced if an efficient data structure is used for the storage of queue.Hence a safety message scheduling and infotainment message reservation(SSIR-MAC)protocol that schedules the transmission of safety messages according to calculated priority is proposed to be designed in this article.It also takes care of the frequent scheduling problem by proposing an efficient data structure which reduces the enqueue and deque time of the packets.

II.RELATED WORK

A detailed survey of the existing literature related to the proposed work provides an insight of improvements in the dedicated short-range communications(DSRC) technology and continuous research enrichments being carried out by the researchers particularly towards protocol enhancement at the MAC layer.Authors in[4]present a clustering method AMRBC that uses the relative mobility for cluster formation and the distance of vehicles with each other to select the cluster head.It limits the number of vehicles inside the cluster so that higher contention does not occur inside the vehicle and clustering should maintain its value for which it is done.When the number of vehicles in the cluster increases from a particular number,the transmission range of vehicles decreases,and the clustering and cluster head selection process reinitiates.It further assigns priority to messages according to vehicle speed and different data rates are used for this purpose.[5]states that the performance of the legacy standardis affected by the inherent nature of CSMA,which is a contention-based channel access protocol.

Various research studies [6–11]discuss the importance of IEEE 1609.4 multichannel based MAC protocols.[12]shows the analytical modelling to a clustered scenario.It calculated the packet delivery ration(PDR)and delay for a general clustered scenario.This model can be extended for a particular clustering protocols to calculate the PDR and delay.[13]proposes a protocol that triggers CCHI whenever a safety message arrives,and after all the safety messages are transmitted,it switches to SCHI to transmit non-safety messages.This process reduces the time wasted during CCHI interval when there are no safety messages in the queue and CCHI is still going on.On the other hand,whenever a safety message arrives during SCHI interval,a control packet is sent to nearby vehicles that announce the start of CCHI.This process takes care of the requirements of both safety and non-safety messages.Multichannel operation in VANET and its components in the IEEE 1609.4 standard is shown in Figure 1.Authors in[14]show a good survey of existing clustering and other MAC protocols.In [15–18],the performance evaluation of clustering based single hop and multi hop message dissemination is done.[19–21]shows the performance evaluation of the IEEE 802.11p protocol standard by varying node density.

Figure 1.Multichannel operation in VANET and its components in the IEEE 1609.4 standard.

Algorithm 1.Beaconing process.1: Step 1 CCHI starts,n=1,N=number of vehicles in cluster 2: Step 2 Time division into‘N’mini slots 3: Step 3 Check if n>N.If yes,go to Step 6;If no,go to Step 4;4: Step 4 nth CM in sorted array transmits in nth slot according to eq(1)5: Step 5 Increment n by 1 and go to step 3 6: Step 6 Start delivery of the safety messages if there is any.

Authors in[21]allow the vehicles to reserve SCHs on the CCH for almost whole of the SI and enables simultaneous transmission on different SCHs.Congestion of CCH is reduced.RSUs broadcast the rendezvous information to OBUs.Multichannel hidden terminal problem is also reduced in this protocol.Considering non safety message transmission probability,average size of non safety message and number of vehicles,an analytical model is also developed.There are mainly four categories of multichannel MAC protocols to improve the safety message delivery.That are time-division multiple access(TDMA)based,non-TDMA based,asynchronous and synchronous MAC.The emergency messages are sent twice(one in SCHI and another in CCHI)in non-TDMA scheme for reliable delivery of safety messages[22–24]but in dense scenarios due to high congestion,it may lead to collision.The CCHI is dynamically varied in [25].It focused upon enhancing the service channel utilization to approximately 50%because of constant CCHI and SCHI ratio.Synchronous channel switching is known to pose harmful impact on the message delay and delivery ratio.The simulation studies [26–30]discuss the synchronization of the backoff process at the MAC layer caused due to the CCH/SCH switching operation.This result in an increased probability of collisions for beaconing messages transmitted on the control channels.[31]proposes Merging sub-networks which is a significant enhancement in the WAVE multichannel protocol.In [32],false alarm probability is evaluated according to spatial correlation among vehicles.In addition to this,power allocation to VSUs is optimized.Parametric transformation is used to solve the nonlinear and non convex optimization problem.In[33],LC-SA scheme,a control node reserves time slots for neighbouring nodes.It uses a scheme based on slotted aloha.One collided node in a time slot keeps using that slot for transmission while other nodes releases that slot so that no further collision occurs on that node.Authors in[34]use a TDMA based mechanism to reduce the collision in vehicular ad hoc networks.The frame length is adjusted based upon the current conditions of the environment.In[35],authors reduced CCH congestion by decreasing RSU dependency.It also increases safety and reliability of data packets along with fairness.Cluster head is used for major control and forwarding operations.A limit on the maximum number of cluster members is placed.It reduces collisions in the CCH thus increases the packet delivery.The service channel of each cluster is selected in such a way so that it is different from that of the neighbouring clusters.

From the above literature survey,the following points can be deduced.The beacons are transmitted after contention with other vehicles at the starting of the CCHI.It may cause the collision among the beacons of different vehicles.The non safety messages are transmitted in the SCHI using contention.It may also cause the collision of packets.Further,the packets are scheduled in a linked list according to their priorities.The packets in the queue are rescheduled whenever a new packet arrives at the vehicle.This causes frequent scheduling of the queue.Due to this frequent rescheduling,queuing time is increased.However,this time can be reduced if an efficient data structure is used for the storage of queue.In this work,the beacons are transmitted according to ids of the vehicles.It eliminates the possibility of collision among beacons.The slots for the transmission of non safety packets in the SCHI are reserved during CCHI.It eliminates the requirement of the contention for non safety packet transmission.Thus the possibility of collision is also eliminated.Further,a hybrid data structure is proposed which reduces the delay caused by the frequent rescheduling of queue.

III.SYSTEM MODEL AND PROBLEM STATEMENT

In the system model under consideration as shown in Figure 2,we focus on the MAC protocol.The vehicles are assumed to be equipped with a transceiver that works on IEEE 802.11p and IEEE 1609 Wireless Access in Vehicular Environment.Vehicles use DSRC band in 5.9 GHz band that contains seven channels.One is CCH and six are SCHs.The cluster of the vehicles is formed according to their relative mobility and the cluster head is selected according to the nearest distance from the centre of the cluster.When a vehicle wants to transmit a message to another vehicle,it first transmits it to a CH and then the CH transmits it to the intended receiver.We consider a 2-lane vehicular scenario and as a preliminary requirement for effective communication,the on-board unit(OBU)in each vehicle carries an IEEE 802.11p standard compliant radio device.Any event-driven message is ensured to be successfully delivered to all other nodes in its singlehop network range.Although the neighbouring nodes might in turn re-broadcast the safety message(thus enabling multi-hop dissemination),we focus our work on single-hop message broadcast.Since the transmission happens in the mobility dependent environment,exponential backoff mechanism is indispensable; as such,the messages are transmitted by using the adaptive contention window(CW)size.

Figure 2.Representation of clustered nodes in a VANET scenario.

Figure 3.Hybrid Queue.

In the IEEE 802.11p standard whose MAC mechanism follows the CSMA/CA approach,prioritised channel access is determined by the CW mechanism.In our approach,we have set the CW based on node mobility.Velocity of the vehicles is associated with the priority level that is assigned to access the channel.That means,higher is the velocity of the vehicle(and therefore the cluster to which it belongs),higher will be the priority it will gain over other vehicles which have comparatively lower mobility range.[14]discuss several CW based priority assignment schemes which reinforce the validity and genuineness of our proposed protocol.Cluster having highest node mobility is given highest priority(minimum CW size)as it will get minimum time to access the channel and broadcast its message.Likewise,based upon node mobility,different priority is assigned to different clusters.

Algorithm 2.Enqueuing a packet in hybrid queue.1: Step 1 If (Packet SP)then 2: If (QueueSP SP == Queue Packet == Null)then 3: Enter the packet at the root position of Queue SP 4: Else 5: Place the packet in corresponding tree according to total priority 6: End 7: Step 2 Else 8: Queue Next 9: Goto Step 1 10: End SP=QueueSP

The velocity range and the respective channel access priority are shown in Table 1.Each node adjusts the values of CWmin and CWmax.Higher is the speed range,higher will be the assigned priority and lower CW size.

Table 1.Assignment of adaptive contention window based on relative velocity.

Table 2.Simulation parameters.

IV.PROPOSED PROTOCOL

SSIR-MAC protocol is divided into 4 parts.The proposal requires a clustered vehicular environment.Clustering procedure is adopted from[4]as mentioned previously.Rest of the parts are described in the following subsections.First,beaconing is explained inside the cluster.It helps in stability of cluster since all the CMs and CH are aware of each other’s parameters such as speed,position etc.The beaconing process proposed in this work eliminates the collision probability of beacons.After beaconing,safety messages are transmitted.Prior to transmission of safety packets,these are scheduled in the hybrid tree for fast enque and deque operations.Further,after safety message transmission,the slots are reserved in SCHI for the transmission of non safety messages.Hence,this work explains the processes done during CCHI and SCHI for transmission of beacons,safety messages and non safety messages.

Algorithm 3.Dequeuing a packet in hybrid queue.SP ==Null)then 2: Return(No packet in queue)3: End 4: Step 2 If (Queue 1: Step 1 If(Queue SP! = Null ＆＆(Packet SP!=Null)then 5: Dequeue(Packet SP)6: Vacancy made by dequeuing of root packet will be filled by a packet having same SP and highest Total Priority 7: End 8: If (Queue SP==Null)then 9: Queue SP!=Null ＆＆ Packet Next 10: Go to Step 2 11: End SP==QueueSP

4.1 Beaconing

When the CCHI starts,all the vehicles start sending their beacons after contending with neighbouring vehicles through CSMA/CA channel access method.In this method of transmission,there is a possibility of beacon collision with other vehicles.To overcome this problem,in this work,the beacons are transmitted using vehicle ids.Since all the vehicles know the vehicle ids of the vehicles in the same cluster,it is easy to send the beacons without any contention among vehicles.All the vehicles arrange the vehicle ids of vehicles in the cluster in an array in ascending order.According to this array,a vehicle can know the transmission time according to eq.(1).

Here,Tbeaconis the time to transmit one beacon and the SIFS is short inter frame space time.nis the position of vehicle id in the shorted array.

At the start of CCHI,vehicle 1in the shorted array transmits its beacon.At this time all the other vehicles in the cluster are in receiving mode.Cluster Head(CH)receives the beacon and transmits it to the rest of the vehicles in the cluster i.e.cluster members(CMs).Vehicle 2 transmits at the time according to equation (1) and so on.This mechanism will help in eliminating the possibility of the collision of beacons during transmission and the network stability increases.The beaconing algorithm can be described as follows.

4.2 Safety Message Transmission

Safety messages are transmitted after all the beacons are successfully transmitted.Safety messages are given the priority over all the other messages.But even in the safety messages,there exist some priorities.The message whose deadline is close is given the higher priority because it may lose its significance if it is received after its deadline.The packet priority is determined by using the two types of priorities,one is static priority and one is dynamic priority.Static priority is the fixed priority that does not change according to the situation.This priority depends upon packet type.The static priority is divided intoSafetyhighandSafetylowpriorities.

Safetyhighare the messages that are extremely urgent,and their delayed transmission may cause an accident.These types of messages are needed to be provided the channel immediately and should not be delayed.Safetyloware the messages that are urgent,but their delayed transmission will not cause an accident.These types of messages are provided the channel immediately but not prior toSafetyhightype of messages.

The dynamic priority of the message depends upon three factors,the relative velocity between a transmitter and receiver(Vr),the transmission range of the vehicle(T)and the distance between transmitter and receiver (D).Dynamic priority can be calculated using the following eq.(2)

Hence,the priority of the message can be calculated as the multiplication of both the priorities such as

4.3 Hybrid Queuing for the Fast Enqueue and Dequeue Operations

The packet queue in each vehicle is needed to be rescheduled whenever a safety packet arrives in the queue.The new packet arriving at the vehicle will have to go all the way to its place according to its priority.This frequent rescheduling of queue may cause an additional delay.This delay can be minimized using various data structures.The queue at the vehicle is generally taken as a linked list.

It increases the enqueue and dequeue time for a packet in the queue.Since there are two types of priorities,static and dynamic,this classification of priority can be used in designing the hybrid queue.A linked list is created; each packet in the linked list has a different static priority.Each packet of different static priorities in the queue is the root node of a tree.This tree contains the packets of same static priorities but of different total priorities.When a packet arrives at a vehicle,it checks its SP to the SP of first element of the linked list.If the SP matches,the tree is then checked for the appropriate position of the packet according to its total priority.This reduces the enqueue and dequeue time of the packets.Every packet in queue has the addresses of every next packet to it in the queue.The hybrid queue is shown in the figure 3.

A packet having SP2 and DP3 will be searched in 9 steps in linked list but for searching in hybrid queue,it will take only three steps.Hene,the difference between two operations is 5 steps.This difference will increase when the number of packets is more.This queue can be designed for more number of SPs if there is any.

The priorities of messages are calculated each time a new safety packet is generated or when a safety packet is received.The queue at the vehicle is rescheduled at each time a new packet arrives at a vehicle.The safety packets are transmitted according to the queue using the CSMA/CA mechanism.

4.4 Reservation of SCHI Slots

Figure 4 shows the flow diagram of the reservation mechanism.When beacons and safety messages are successfully transmitted and there is still CCHI remaining,the reservation packets are transmitted on control channel so that the slots for the non-safety message transmission during SCHI can be reserved and the non-safety packets are transmitted in those slots.For this reason the scheme is called intelligent.The reservation packets are transmitted using CSMA/CA.Transmitter sends one control packet to the receiver indicating that it wants to send the nonsafety packet to the receiver during the SCHI.The receiver responds with another control packet indicatingthe channel and slot in which it wants to receive the non-safety packet during the SCHI.The first reservation packet that is received by the sender is awarded with the first slot of SCHI.The second reservation packet that is received by the sender is awarded with second slot if the same channel is decided by the receiver.If any other channel is decided by the receiver then the same slot can be awarded for the transmission.In the current underlying standard,during the CCHI all vehicles switch to CCH.This ensures that they are connected to each other and that they are ready to transmit/receive messages.During the SCHI,vehicles are free to tune to any of the six DSRC channels assigned to non-safety message transmission mode.Contrary to this,we do not switch to any specific channel and discard the synchronization process between SCHI and CCHI.Through analytical means,we calculate the total number of mini slots.Tbof safety message is given as

Figure 4.Flow diagram showing the reservation mechanism.

wheren=number of Bits andRb=Bit rate.

In the proposed protocol,the modulation technique adopted is Binary Phase Shift Keying(BPSK).Hence,n is taken to be 2.Therefore,

[26]states that 6 Mbps is prescribed as the data rate for DSRC safety applications,so we takeRbfor BPSK signal to be 6 Mbps.So,comes out to be 3 MHz.It is assumed that the bandwidth of the signaling overhead shall be about 0.5 MHz

Therefore,using equation(3),

Number of mini slots(N)is calculated as

Therefore,N is computed as

4.5 Transmission of Control Packets

When the SCHI starts,non-safety messages are transmitted according to their slots and channel ids.When all the vehicles which had reserved slot for the transmission of non safety messages have transmitted the packets and there are no more non safety packets left for the transmission,after waiting for some slots and not listening any activity on any channel,CH transmits a control packet that announces the end of the SCHI and starting of the guard interval following the CCHI.Figure 5 shows the timing diagram of proposed protocol.

Figure 5.Timing diagram of proposed protocol.

V.PERFORMANCE EVALUATION

In this section,we evaluate and compare the performance of proposed SSIR-MAC protocol with IEEE 802.11p standard and other two protocols with similar preposition.The motive behind such comparison is to analyse the stability of the cluster and the variation in the quality of service (QoS) metrics.These results strongly argue for an afterthought into the DCF of WAVE and re-model it to provide road safety.Performance of four main performance metrics in terms of delay,PDR,PLR and throughput are evaluated for SSIR-MAC.We implement the proposed protocol and perform simulations using network simulator (NS2),version 2.34.The real time scenario is generated using www.openstreetmap.org to produce vehicular mobility traces.The scenario contains two lanes,one in each direction.The channel is wireless channel.The channel environment is rapidly changing due to the speed of the neighboring vehicles.The propagation model used is Nakagami.The snapshot of scenario is shown in figure 6.The protocol is compared with (Li et al.,2015)since it is most relevant to the proposed work.

Figure 6.Snapshot of mobility trace under simulation.

Simulations were replicated for five runs and every time similar results were obtained with nominal deviation.The average of all the five runs has been calculated to be used for evaluation.Table 5 specifies the parameters used in the simulation.

Figures 7 to 14 evaluate and compare the performance of the proposed SSIR-MAC in terms of different QoS parameters.The results of this comparison justify the need to enhance the present standard in order to improve the DSRC services in VANET.

Figure 7.Average delay comparison between different protocols and SSIR-MAC for Dense Scenario.

Figure 7 and 8 show the average delay vs number of vehicles of dense and sparse scenarios respectively.As the number of nodes in the network increases,the delay increases for all the four protocols under discussion.But for SSIR-MAC,delay increases slightly.The delay in SSIR-MAC is much smaller in comparison to the other three existing protocols because of the scheduling of safety messages according to the deadline of the messages and the CCHI starts when there is no more non-safety messages are to be transmitted.This reduces a significant amount of time in transmission of safety messages which would have been wasted during the next CCHI interval.

Figure 8.Average delay comparison between different protocols and SSIR-MAC for Sparse Scenario.

Figure 9 and 10 show the PDR vs.number of vehicles for dense and sparse scenarios respectively.As the number of vehicles increases,the PDR decreases in the network because of higher vehicle density and the higher collision of packets.The PDR is highest in the SSIR-MAC because it transmits the safety message to receiver before the receiver goes out of the range of the transmitter.In addition to this,beacons are sent using their ids in increasing order inside a cluster.This provides stable clusters thus a stable network.The hybrid queue enables the fast enque and deque operations of the packets thus increasing packet delivery as well.

Figure 9.PDR comparison between different protocols and SSIR-MAC for Dense Scenario.

Figure 10.PDR comparison between different protocols and SSIR-MAC for Sparse Scenario.

Figure 11 and 12 show the graph of packet loss ratio(PLR)vs.number of vehicles for dense and sparse scenarios respectively.PLR increases in all the four protocols because of the same reason as stated for PDR.The PLR is lowest for SSIR-MAC and highest in the IEEE802.11p.

Figure 11.PLR comparison between different protocols and SSIR-MAC for Dense Scenario.

Figure 12.PLR comparison between different protocols and SSIR-MAC for Sparse Scenario.

Figure 13 and 14 show the throughput in the network vs.the number of nodes for sparse and dense scenario respectively.The throughput is the average information transmitted per second in the network.When number of nodes increases throughput also increases even when the PDR reduces.It is because the new nodes also transmit the packets.Hence even when the greater number of packets being dropped,Throughput increases.The throughput is highest in the SSIR-MAC protocol because it provides a stable network by ensuring the successful delivery of beacons thus ensuring the stability of the network.Further,the non-safety packets are transmitted after reservation of slots in the service channel interval.All this increases the network performance.

Figure 13.Throughput comparison between different protocols and SSIR-MAC for Dense Scenario.

Figure 14.Throughput comparison between different protocols and SSIR-MAC for Sparse Scenario.

VI.CONCLUSION

In this article,we proposed an algorithm that implements mobility-based clustering into the system initialisation step to optimise scheduling calculation.The problem of transmission of the safety packets after the deadline is considered in this work and the solution is prioritizing the safety packets according to the distance between transmitter and the receiver.Further,the problem of transmission of non-safety message randomly in the SCHI network is solved by reserving the slots for transmission of non-safety messages in SCHI during CCHI interval with the use of reservation packets.The SCHI also stops immediately when all the non-safety packets are transmitted in the SCHI interval and a control packet is sent by cluster head to its members that announce the end of the SCHI interval and start of the CCHI interval.