# QoS Aware Service Scheduling Scheme for VANETs

Authors: Ajay Guleria; Kuldip Singh; Narottam Chand
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

People immediately want to access the required data in vehicular ad hoc networks (VANETs). They provide the requests to road side unit (RSU) while travelling. The job of RSU is to handle various requests in such a way so that the service ratio and the quality of service (QoS) is optimized. In this paper we present a mechanism to achieve this goal. Our proposed algorithm considers both data size and deadline and optimizes uploading/downloading based on number of requests to be handled. It also deals with the impact of missed upload operations to achieve maximum optimization. The proposed scheme categorizes data into two classes to assign weight according to their effect on QoS and assigns priorities to upload and download requests while maintaining common queue for both upload and download requests. Simulation results corroborate that the proposed algorithm provides better service ratio and QoS than existing techniques.


---

## Body

## 1. Introduction

Vehicular ad hoc network (VANET) is emerging as very crucial technology due to rapid traffic increase and recent advances in wireless technology. People in vehicles may get security support, local news and advertisement, music, radio, video, and so forth [1–4]. Vehicles can obtain these data items from road side unit (RSU). Recently research is devoted to provide efficient access of data from RSU to vehicle or vice versa [5–8]. Federal Communications Commission (FCC) has allocated 5.850–5.925 GHz portion of the spectrum for intervehicle communication (IVC) and vehicle to roadside communication (VRC) [9, 10] in USA. Applications of VANET can be broadly classified into following categories:(i)
safety related applications: accident related alerts, red light warning, and so forth.(ii)
nonsafety related applications: downloading as well as uploading/surfing audio/video programs, digital maps, internet access, traffic information, weather reports, and other communication applications.Few of the major concerns for vehicular communication are high mobility, dynamically changing topology, sparsely located nodes, and critical communication duration [11–13]. So, data dissemination with good service ratio and quality of service is a major challenge. In this paper we performed the following tasks.(i)
Categorized data into two classes in order to assign weights such that it assigns highest priority to most urgent update request.(ii)
Proposed a method to assign uniform priorities to upload and download requests.(iii)
Proposed a new algorithm to increase service ratio and quality of download up to an optimum level.(iv)
Performed simulations which show that the proposed algorithm is better in terms of service ratio and quality of service than earlier existing approaches.Rest of the paper is organized as follows. Section2 discusses related work. Section 3 describes system model. Section 4 proposes a new scheduling scheme. Section 5 elaborates performance metrics to be used for evaluation of proposed system, simulation environment and results. Finally Section 6 is devoted to concluding remarks.


## 2. Related Work

Major research challenges in VANETs are introduced in [11–13]. High mobility of vehicles is the main challenge in VANETs which leads to short deadline to access data from RSU and causes highly dynamic topology. In case of vehicle-roadside data access there is more than one vehicle under coverage of one RSU. So multiple vehicles can send data upload and download requests to RSU. RSU needs to schedule these requests in such a way so as to improve service ratio and quality of service. Many broadcasting algorithms have been proposed to reduce the waiting time [14–16].In [17] Acharya and Muthukrishnan proposed a data scheduling algorithm called longest total stretched first (LTSF) which is based on a new metric called stretch, that is, service ratio of the response time of a request to its service time. LTSF optimizes stretch and maintains balance between worst case and average case but implementation of LTSF for large system is not practical because server needs to recalculate stretch for every pending request to find next data to be broadcasted. In [18] Xu et al. proposed online scheduling algorithm for time critical on demand data broadcast, but they assumed that data can only be updated by server; that is, vehicles can only download and it does not allow vehicles to update urgent data. Jiang and Vaidya [19] proposed periodic push based broadcast, which is not well suited to VANET applications.In [20] Zhang et al. first proposed D*S algorithm and further optimized downloading by using D*S/N and optimized uploading by using D*S/R while maintaining different queues for download and upload requests. It assigns different bandwidth to these queues and serves upload requests on basis of past service rate of data items. Scheduling in [20] randomly selects either upload or download queue. If download queue is selected, it can miss most urgent update, similarly if update queue is selected it can cause multiple download requests to drop.In [21] Fridman et al. have proposed a model which allocates resources based on input constraints and maximize the communication performance for MANET.In contrast to existing strategies, the proposed scheduling scheme maintains single queue for both upload and download requests. It gives more weightage to most urgent updates than downloads to improve quality of service, and more weightage to number of downloads than less urgent updates to improve service ratio, in dynamic fashion.


## 3. System Model

In VANETs, there are two communication entities: vehicles and road side unit (RSU). RSU acts as data manager or service provider while vehicles act as consumer/modifier of data.Each vehicle in VANET is equipped with on board unit (OBU) which is transceiver with computational power and omni directional antenna. RSU has transceiver, antenna, processor, and sensors. RSUs are generally placed at intersections to improve traffic at that intersection to reduce accidents. RSU manages all data and requests. Vehicles can request the desired data and can update the data. Upload and download compete for same bandwidth. In our model RSU maintains a single queue for upload/download requests. A typical scenario will look like as shown in Figure1.Figure 1
Typical VANET scenario.As shown in Figure1, many vehicles can send their request to RSU at a time. Let each request be submitted as<vehicle_id, data_id, current_position, average_speed, operation>vehicle_id: uniquely identifies the requesting vehicle,data_id: identification code of requested data on which operation is to be applied,current_position: each vehicle is assumed to have global positioning system (GPS) so it knows its current location,average_speed: average speed of vehicle,operation: either upload or download.Operation sequence of VANETs is summarized in Figure2.Figure 2
Steps involved in VANETs operation.


## 4. Proposed Scheme

The objective of the proposed method is to achieve maximum possible service ratio with optimum data quality. Based on the CPU scheduling criteria the requests can be scheduled in the following ways.(i)
FCFS (First Come First Serve). According to this sequence, requests are scheduled according to the sequence of their arrival. This approach is inappropriate for VANETs because it does not consider deadline constraint of requests.(ii)
SDF (Smallest Data size First). This scheme schedules the requests according to their size; that is, smallest data size request will be scheduled first.(iii)
EDF (Earliest Deadline First). This scheme schedules the requests according to their deadlines; that is, earliest deadline request will be processed first.Authors in [20] have proposed D*S algorithm, where D is the deadline and S is the size of data. In D*S scheduling algorithm, requests having smaller D*S value will be scheduled earlier than request having higher D*S value. Given two requests with same deadline, the one with smaller data size will be processed first. Given two requests for same data size, the one with earlier deadline should be served first.Further Zhang et al. proposedD*S/N algorithm to optimize downloading, where N is the number of download requests for same data items and D*S/R to optimize uploading, where R is service rate of same data item.Our proposed method modifiesD*S as D*S/(N*W) to assign priority to download request when no upload request exists for same data item and D*S/N*W2 to assign priority to upload requests where W is weight assigned to data items discussed later.


### 4.1. Parameters Used to Assign Priorities

The proposed method uses following parameters to assign priorities to various requests (see Table1).(i)
Data Size (S). It is size of data requested for upload or download. It can be in kilobytes (KBs) or megabytes (MBs).(ii)
Deadline (D). Each vehicle sends its current location and average speed along with request to RSU. RSU knows its coverage area so it can calculate how much time the vehicle will remain in its coverage area. Let it is denoted by TCLT.(iii)
Weight (W). This parameter is used to measure relative importance of various data items, for example, updates related to security must have more weightage than update requests related to nonsecurity data items.Table 1
Simulation parameters.
Parameter
Value
Simulation time
1000 s
RSU coverage area
200 m
Vehicle speed
30 km/hour
Item size
4 Mb, max
Item set size,N
10–50
Skew coefficient,θ
0.0–1.0
Arrival rate,λ
6–20


### 4.2. Assigning Weight to Various Data Items

RSU maintains various types of data items such as safety related data, for example, traffic congestion related data and traffic light alert; nonsafety related data, for example, advertisement of local hotels, tourist places, digital maps, and audio/video files. Safety related data must be updated within deadline even when there is no download request for this data item in current window. We call these data items highest update priority data (HUPD). Since missed update of audio/video does not significantly deteriorate the quality of data, we call these data items least update priority data (LUPD). We assign different weights to these data items belonging to these two categories. Let there bek data items D={d1,d2,d3,…,dk}, 0<k<∞. Let m out of k data items belong to HUPD such that m≤k  LUPD = D − HUPD. LUPD contains remaining k-m data items, so HUPD and LUPD are mutually exclusive.//Algorithm to assign weightN = total number of requests in windowforj=1 to k
do ifdj  ∈  HUPD
W(dj)=Nelse
W(dj)=1F[requesti]=1, S[requesti]=0


### 4.3. Assigning Priorities to Various Requests

Priority assigning algorithm uses following notations:(i)
Di: Deadline of requesti.(ii)
Si: Size of data item referred in requesti.(iii)
Wi: Weight of data item referred in requesti.(iv)
P(requesti): Priority assigned to requesti.(v)
Ni: Number of download requests for same data items requested in requesti.//Algorithm for assigning prioritiesfori=1 to 1
do ifrequesti is download request and no upload request exists for same data item in current window
thenP(requesti)=(Di*Si)/(Ni*Wi)else ifrequesti is upload request
if download request also exists for same data item
thenP(requesti)=(Di*Si)/Ni*Wi2else
P(requesti)=(Di*Si)/Wi2The smaller the value ofP(requesti) the higher will be the priority.Above algorithm steps are shown in Figure3.Figure 3
Priority Assigning Algorithm.Theorem 1.
The proposed priority assigning algorithm assigns highest priority to update requests of HUPD data items.Proof.
LetR1 request is for uploading HUPD data item d1. Then priority assigned to R1 will be as follows:
(1)PR1=D1*S1N1*W12,
where D1 is deadline of R1, S1 is size of data item requested in R1, N1 is number of download requests for d1, that is, data item requested in R1. W1=N, and N is window size.
LetR2 be request for downloading HUPD data item d2, then priority assigned to R2 will be as follows:
(2)PR2=D2*S2N2*W2,
where D2 is deadline of R2, S2 is size of data item requested in R2, N2 is number of download requests for d2, that is, data item requested in R2, W2=N, and N is window size.
In worst case there would be no download request ford1. Generally, deadlines should not vary by more than 1.5 times (e.g., minimum speed 60 km/hr. and maximum speed 90 km/hr.) and data item’s size related to HUPD will be small and can be assumed nearly equal so
(3)D1=1.5D2,S1≈S2
maximum value of N2 can be N-2. So, 1 would be as follows:
(4)P(R1)=1.5D2*S2N2
and 2 can be written as
(5)PR2=(D2*S2)(N2-2N).
Even for nominal window size 5,P(R1)<P(R2). Hence priority of R1 would be more than priority of R2. Similarly we can prove that priority of uploading HUPD data items will be more than uploading and downloading of LUPD data items.


### 4.4. Algorithm to Process Requests from Service Queue

This algorithm uses the following notations.N: Number of requests in current window.di: Data requested in requesti that is, ith request; 0<i≤N.C[1,N]: Operation code array either C[i]=d or C[i]=u, d stands for download and u for upload; 0<i≤N.F[1,N]: Finish array, F[i]=0 means ith request is unprocessed, F[i]=1 means ith request is processed; 0<i≤N.S[1,N]: Success array S[i]=0 means ith request is unsuccessful, S[i]=1 means ith request is successful; 0<i≤N.D[1,N]: Deadline array; 0<i≤N.P[1⋯N]: Priority generated by algorithm as discussed earlier.Tj: Actual transfer time of data requested in request that is, requestj.//Algorithm to process requestsfori=1 to N
F[i]=0 //initially each request is unprocessedS[i]=0 //initially each request is unsuccessfulrequesti={i∣P[i] is minimum i.e., highest priority request and F[i]≠1}; 0<i≤Nif (C[requesti]==d)
then if (TCLT≥Tdi)
then broadcastdi and F[requesti]=1, S[requesti]=1else
F[requesti]=1, S[requesti]=0else if (TCLT≥Tdi)
then allocate channel to uploaddi andF[requesti]=1, S[requesti]=1else
F[requesti]=1, S[requesti]=0forj=1 to N
do if ((dj==di) AND (C[j]==C[requesti]) AND (D[j]≥Tj))
thenF[j]=1, S[j]=1if ((dj==di) AND (C[j]==C[requesti]) AND (Dj<Tj))
thenF[j]=1, S[j]=0if (S[requesti]==1)
then forj=1 to N
do if (F[j]==0) then D[j]=D[j]-Trequestiif (F[i]==1) is true for some i repeat through step 2ExitStep 1 marks each request as unsuccessful and unprocessed. Step 2 selects unprocessed highest priority request from queue, this step can be implemented by using min priority queue. If selected process is of download type then steps 3 and 4 process it; if its deadline is less than transfer time, then broadcast it and mark it as processed and successful else mark it as unsuccessful and processed. If selected process of step 2 is upload request then step 5 allocates channel to upload data requested if deadline is less than transfer time of requested data and mark it as processed and successful, if deadline cannot be met then mark it as unsuccessful and finished. If processed request was successful then step 6 marks request of same data and same operation with achievable deadline (i.e.,D[j]≥Tj), as successful and processed if deadline is not achievable mark it as processed and unsuccessful. Step 7 reduces deadline of unprocessed request by transfer time of currently processed request. Step 8 checks for unprocessed requests, if any existing process again repeats from step 2, else algorithm terminates with step 9.


## 4.1. Parameters Used to Assign Priorities

The proposed method uses following parameters to assign priorities to various requests (see Table1).(i)
Data Size (S). It is size of data requested for upload or download. It can be in kilobytes (KBs) or megabytes (MBs).(ii)
Deadline (D). Each vehicle sends its current location and average speed along with request to RSU. RSU knows its coverage area so it can calculate how much time the vehicle will remain in its coverage area. Let it is denoted by TCLT.(iii)
Weight (W). This parameter is used to measure relative importance of various data items, for example, updates related to security must have more weightage than update requests related to nonsecurity data items.Table 1
Simulation parameters.
Parameter
Value
Simulation time
1000 s
RSU coverage area
200 m
Vehicle speed
30 km/hour
Item size
4 Mb, max
Item set size,N
10–50
Skew coefficient,θ
0.0–1.0
Arrival rate,λ
6–20


## 4.2. Assigning Weight to Various Data Items

RSU maintains various types of data items such as safety related data, for example, traffic congestion related data and traffic light alert; nonsafety related data, for example, advertisement of local hotels, tourist places, digital maps, and audio/video files. Safety related data must be updated within deadline even when there is no download request for this data item in current window. We call these data items highest update priority data (HUPD). Since missed update of audio/video does not significantly deteriorate the quality of data, we call these data items least update priority data (LUPD). We assign different weights to these data items belonging to these two categories. Let there bek data items D={d1,d2,d3,…,dk}, 0<k<∞. Let m out of k data items belong to HUPD such that m≤k  LUPD = D − HUPD. LUPD contains remaining k-m data items, so HUPD and LUPD are mutually exclusive.//Algorithm to assign weightN = total number of requests in windowforj=1 to k
do ifdj  ∈  HUPD
W(dj)=Nelse
W(dj)=1F[requesti]=1, S[requesti]=0


## 4.3. Assigning Priorities to Various Requests

Priority assigning algorithm uses following notations:(i)
Di: Deadline of requesti.(ii)
Si: Size of data item referred in requesti.(iii)
Wi: Weight of data item referred in requesti.(iv)
P(requesti): Priority assigned to requesti.(v)
Ni: Number of download requests for same data items requested in requesti.//Algorithm for assigning prioritiesfori=1 to 1
do ifrequesti is download request and no upload request exists for same data item in current window
thenP(requesti)=(Di*Si)/(Ni*Wi)else ifrequesti is upload request
if download request also exists for same data item
thenP(requesti)=(Di*Si)/Ni*Wi2else
P(requesti)=(Di*Si)/Wi2The smaller the value ofP(requesti) the higher will be the priority.Above algorithm steps are shown in Figure3.Figure 3
Priority Assigning Algorithm.Theorem 1.
The proposed priority assigning algorithm assigns highest priority to update requests of HUPD data items.Proof.
LetR1 request is for uploading HUPD data item d1. Then priority assigned to R1 will be as follows:
(1)PR1=D1*S1N1*W12,
where D1 is deadline of R1, S1 is size of data item requested in R1, N1 is number of download requests for d1, that is, data item requested in R1. W1=N, and N is window size.
LetR2 be request for downloading HUPD data item d2, then priority assigned to R2 will be as follows:
(2)PR2=D2*S2N2*W2,
where D2 is deadline of R2, S2 is size of data item requested in R2, N2 is number of download requests for d2, that is, data item requested in R2, W2=N, and N is window size.
In worst case there would be no download request ford1. Generally, deadlines should not vary by more than 1.5 times (e.g., minimum speed 60 km/hr. and maximum speed 90 km/hr.) and data item’s size related to HUPD will be small and can be assumed nearly equal so
(3)D1=1.5D2,S1≈S2
maximum value of N2 can be N-2. So, 1 would be as follows:
(4)P(R1)=1.5D2*S2N2
and 2 can be written as
(5)PR2=(D2*S2)(N2-2N).
Even for nominal window size 5,P(R1)<P(R2). Hence priority of R1 would be more than priority of R2. Similarly we can prove that priority of uploading HUPD data items will be more than uploading and downloading of LUPD data items.


## 4.4. Algorithm to Process Requests from Service Queue

This algorithm uses the following notations.N: Number of requests in current window.di: Data requested in requesti that is, ith request; 0<i≤N.C[1,N]: Operation code array either C[i]=d or C[i]=u, d stands for download and u for upload; 0<i≤N.F[1,N]: Finish array, F[i]=0 means ith request is unprocessed, F[i]=1 means ith request is processed; 0<i≤N.S[1,N]: Success array S[i]=0 means ith request is unsuccessful, S[i]=1 means ith request is successful; 0<i≤N.D[1,N]: Deadline array; 0<i≤N.P[1⋯N]: Priority generated by algorithm as discussed earlier.Tj: Actual transfer time of data requested in request that is, requestj.//Algorithm to process requestsfori=1 to N
F[i]=0 //initially each request is unprocessedS[i]=0 //initially each request is unsuccessfulrequesti={i∣P[i] is minimum i.e., highest priority request and F[i]≠1}; 0<i≤Nif (C[requesti]==d)
then if (TCLT≥Tdi)
then broadcastdi and F[requesti]=1, S[requesti]=1else
F[requesti]=1, S[requesti]=0else if (TCLT≥Tdi)
then allocate channel to uploaddi andF[requesti]=1, S[requesti]=1else
F[requesti]=1, S[requesti]=0forj=1 to N
do if ((dj==di) AND (C[j]==C[requesti]) AND (D[j]≥Tj))
thenF[j]=1, S[j]=1if ((dj==di) AND (C[j]==C[requesti]) AND (Dj<Tj))
thenF[j]=1, S[j]=0if (S[requesti]==1)
then forj=1 to N
do if (F[j]==0) then D[j]=D[j]-Trequestiif (F[i]==1) is true for some i repeat through step 2ExitStep 1 marks each request as unsuccessful and unprocessed. Step 2 selects unprocessed highest priority request from queue, this step can be implemented by using min priority queue. If selected process is of download type then steps 3 and 4 process it; if its deadline is less than transfer time, then broadcast it and mark it as processed and successful else mark it as unsuccessful and processed. If selected process of step 2 is upload request then step 5 allocates channel to upload data requested if deadline is less than transfer time of requested data and mark it as processed and successful, if deadline cannot be met then mark it as unsuccessful and finished. If processed request was successful then step 6 marks request of same data and same operation with achievable deadline (i.e.,D[j]≥Tj), as successful and processed if deadline is not achievable mark it as processed and unsuccessful. Step 7 reduces deadline of unprocessed request by transfer time of currently processed request. Step 8 checks for unprocessed requests, if any existing process again repeats from step 2, else algorithm terminates with step 9.


## 5. Simulation Environment and Results

We validate the performance analysis of proposed QoS aware service Scheduling (QASS) scheme by performing simulation experiments.


### 5.1. Performance Metrics

We use the following metrics for performance evaluation.(i)
Service Ratio (in Percent). Ratio of number of requests served by road side unit successfully to total number of requests submitted by vehicles to RSU. A better scheduling algorithm is characterized by high service ratio.(ii)
Data Quality. If upload request of some data item say di is missed due to deadline not met, then out dated data will be served to the next downloading request for the data item di. So quality of downloaded data items degrades. We use number of missed uploads to measure data quality. Higher the value of missed updates lower is the quality of data.


### 5.2. Experimental Setup

The experiment is based on a200×200 m2 street intersection of one horizontal road and one vertical road where each two-way road has two lanes. One RSU server is put at the center of the junction. To generate the vehicle traffic, we randomly deploy 10 vehicles in each lane that makes a total of 40 vehicles. All vehicles move towards either end of the road. They are moving forward and backward during the simulation to have the continuous traffic flow in the intersection area. When one vehicle reaches the end of the road, which means the vehicle will move out of the RSU service area, its request not serviced will be dropped.We used ns-3 [22] network simulation platform to evaluate performance of the proposed algorithms. Although currently ns-3 does not support detailed VANETs simulation but it has excellent implementation ofWifi Models and is accurately capable to test diverse protocols at application layer.We implement two applications, namely,ServerApp andClientApp by extendingApplication class of ns-3 built-in API. TheClientApp requests various data items to theServerApp. It composes the request in form of packets by using data size, deadline, operation and data ID. Data size is the size of the packet. The deadline is calculated by current location, average speed and the coverage area of the RSU. The operation can by upload or download. The data ID is used to distinguish various data items. The deadline, operation and data ID values are added to the packet by usingtagging facility of ns-3. Three classes, namely,DeadlineTag,OperationTag, andDataIdTag, where defined by extendingTag base class for deadline, operation and data ID parameters, respectively. Thenode of ns-3 is considered as the vehicle (client) with mobility capabilities. TheclientApp is installed on all client nodes.TheServerApp performs all scheduling operations. It reads various parameters of incoming requests from clients and assigns weight and priority accordingly to each request. After user defined simulation time, it schedule all received requests according to the scheduling algorithm and responds to all clients. A stationary node is taken as RSU and theServerApp is installed on it.We define two helper classes, namely,ServerAppHelper andClientAppHelper, to facilitate easy configuration of the server application and the client application, respectively.The RSU node and the client nodes contain respective NICs (network interface cards) by usingNetDevice implementation of ns-3. Also, all nodes (RSU/server node, vehicles/client nodes) are configured with real IP addresses using IPv4 API of ns-3. TheAttribute facility of ns-3 is used to configure various components of the simulation. Such as,SetDeviceAttribute,SetChannelAttribute are used to configure DataRate of the devices and Delay of the channel, respectively. And,SetPropagationDelay,AddPropagationLoss methods are used to configure the wifi channel similar to real VANETs environment. At the physical layer,OfdmRate6Mbps andWIFI_PHY_STANDARD_80211_10MHZ is used to comply with IEEE 802.11 p/WAVE Standard. TheSetAttribute ofClientAppHelper is used to set various elements such asMaxPackets,Interval andPacketSize.The highway is created by usingGridPositionAllocator of ns-3 mobility component. The vehicles maintain distance of ten meters with each other and can move between user-defined initial and maximum range. The RSU is fixed at the specific location at the highway and it has fixed coverage area to serve the clients/vehicles.The ns-3tracing facility withcallbacks is used to calculate deadline and add various tags to packets by definingtrace sources andtrace sinks. Also, thelogging facility is used to test and evaluate various results.We also implemented FCFS, EDF, SDF, andD*S/N in ns-3 and compared these with proposed scheme using same data inputs.We measure performance of proposed algorithm under various scenarios based on a new metric called Impact Factor (IF) defined as:Impact Factor (IF) = Number of HUPD data items/total number of data items (NOD).Based upon value of impact factor there can be three possible cases. For evaluation of each scenario we used service ratio and data quality as metrics. We have taken Case 1, whereIF=0.8 that is, number of requests for emergent items is more, Case 2, where IF=0.6 showing scenario where requests for safety and nonsafety items is almost equal and, Case 3, where IF=0.2 and requests for nonsafety items are more. We studied the effect of arrival rate λ and data set size on service ratio and data quality.


### 5.3. Effect of Arrival Rate on Service Ratio

Case 1 (when IF is 0.8).
In this case most of the requested data items belong to HUPD. This case reflects the scenario where almost all requests are coming for high priority items that is, in such scenario, most of the requested data items belong to HUPD. We evaluated each of above mentioned algorithm in this scenario by takingIF=0.8. Arrival rate λ is varied from 6 to 20. Value of access pattern θ is set to 0.6. Figure 4(a) shows the effect of arrival rate on service ratio. The service ratio of all algorithms decreases as arrival rate increases. QASS has the highest service ratio as compared DSN and other basic scheduling schemes FCFS, EDF and SDF. For higher values of arrival rate QASS and DSN almost perform same. QASS performs better than others as it assigns higher priority weights for more emergent requests and here in this case 80% of the requests are in that category.Figure 4
Effect of arrival rate (λ) on service ratio in (a) Case 1, (b) Case 2, and (c) Case 3.
(a)
(b)
(c)Case 2 (when IF is 0.6).
This case reflects normal scenario where HUPD data is not referred so frequently that is, traffic density is normal and requests for safety or critical data are normal. We tested this case by takingIF=0.6. Arrival rate λ is varied from 6 to 20. Value of access pattern θ is set to 0.6. Figure 4(b) shows the performance of proposed algorithm along with others in that case.Case 3 (when IF is 0.2).
This case reflects the scenario where number of requests for critical or safety related data is least. We have simulated this case by takingIF=0.2. So here in this case only 20% of the total requests are assumed to be for HUPD data and 80% for nonsafety data. Service ratio against different values of arrival rate is observed. Figure 4(c) shows the service ratio of proposed algorithm along with others for Case 3. Service ratio of QASS is better than basic scheduling algorithms and similar to DSN. This is because it uses all parameters such as deadline, size and number of outstanding requests for scheduling information as is the case of DSN algorithm. Other methods that is, FCFS, EDF and SDF do not combine these parameters so do not perform as good as QASS and DSN.


### 5.4. Effect of Arrival Rate on Data Quality

Case 1 (when IF is 0.8).
Quality of data is equally important as service ratio. Data quality is measured by number of missed updates for items. Lower the number of missed updates better is quality of data. In this case most of requests are for HUPD data and algorithm is optimized for high priority requests so numbers of missed updates are least in case of QASS. Figure5(a) illustrates that quality of data delivered in this case is significantly better than all other algorithms and also service ratio is better than FCFS, SDF, and EDF, and as good as DSN.Figure 5
Effect of arrival rate (λ) on data quality in (a) Case 1, (b) Case 2, and (c) Case 3.
(a)
(b)
(c)Case 2 (when IF is 0.6).
Figure5(b) shows that proposed algorithm provides better service ratio than FCFS, SDF and EDF and slightly better than DSN. Here also arrival rate λ is varied between 6 and 20 and θ is set to 0.6. Numbers of missed updates are again least in QASS and it increases as arrival rate increases.Case 3 (when IF is 0.2).
In this case most of requests are for non HUPD data items. But QASS does distinguish between upload and download requests and accordingly readjusts which is not the case in other algorithms, so numbers of missed updates are least in case of QASS. Figure5(c) illustrates that quality of data delivered in this case is significantly better than all other algorithms and also service ratio is better than FCFS, SDF, EDF, and DSN.


### 5.5. Effect of Data Set Size on Service Ratio

Case 1 (when IF is 0.8).
The data set size value is varied between 10 and 50. The corresponding service ratio is shown in Figure6(a). Maximum requests in this case belong to HUPD. The number requests increases in proportion to the increase number of items. We evaluated each of above mentioned algorithm in this scenario by taking IF=0.8. Arrival rate λ is assumed as 10. Value of access pattern θ is set to 0.6. The service ratio all algorithms decrease as we increase number of items at server. QASS has the highest service ratio as compared DSN and other basic scheduling schemes FCFS, EDF and SDF. QASS performs better than other as it assigns higher priority weights for more emergent requests and here in this case 80% of the requests are in that category.Figure 6
Effect of data set size (N) on service ratio in (a) Case 1, (b) Case 2, and (c) Case 3.
(a)
(b)
(c)Case 2 (when IF is 0.6).
This case reflects normal scenario where HUPD data is not referred so frequently that is, traffic density is normal and requests for safety or critical data are normal. We tested this case by takingIF=0.6. Data set size here also varied from 10 to 50. Value of access pattern θ is set to 0.6. Figure 6(b) shows the performance of proposed algorithm along with others in that case. Service ratio of all algorithms decreases marginally with increase in data set size. Decrease is lowest again in case of QASS.Case 3 (when IF is 0.2).
Here in this case only 20% of the total requests are assumed to be for HUPD data and 80% for nonsafety data. Service ratio against different values of data set size is observed. Figure6(c) shows the service ratio of proposed algorithm along with others for Case 3. Service ratio of QASS is better than basic scheduling algorithms and similar to DSN. This is because it uses all parameters such deadline, size and number of outstanding requests for scheduling information as is the case in DSN algorithm. Other methods that is, FCFS, EDF, and SDF do not combine these parameters so do not perform as well as QASS and DSN.


### 5.6. Effect of Data Set Size on Data Quality

Case 1 (when IF is 0.8).
Figure7(a) shows the quality of data as we increase data set size from 10 to 50. Arrival rate is set to 10 and access pattern value is taken 0.6. QASS has least number of missed updates so it performs significantly better than all other algorithms. When IF is taken as 0.8, concentration of HUPD requests is maximum and QASS prioritize these requests. So with increase in number of data set size, missed updates increase marginally.Figure 7
Effect of data size (N) on data quality in (a) Case 1, (b) Case 2, and (c) Case 3.
(a)
(b)
(c)Case 2 (when IF is 0.6).
When IF is taken 0.6 then HUPD requests presence is almost half of total requests. Accordingly QASS prioritizes only that much requests so number of missed updates in this case is more with increase in data set size. QASS performs better than its counterparts. Results are shown in Figure7(b).Case 3 (when IF is 0.2).
Figure7(c) shows the data quality of proposed algorithm along with others for Case 3. Requests for HUPD items in this case are only 20%. Most items are in LUPD group so algorithm very much works like DSN. Data quality of QASS is better than basic scheduling algorithms and similar to DSN. This is because QASS uses all parameters such deadline, size, and number of outstanding requests for scheduling information as is the case in DSN algorithm. Other methods, that is, FCFS, EDF, and SDF, do not combine these parameters and so do not perform as well as QASS and DSN.


## 5.1. Performance Metrics

We use the following metrics for performance evaluation.(i)
Service Ratio (in Percent). Ratio of number of requests served by road side unit successfully to total number of requests submitted by vehicles to RSU. A better scheduling algorithm is characterized by high service ratio.(ii)
Data Quality. If upload request of some data item say di is missed due to deadline not met, then out dated data will be served to the next downloading request for the data item di. So quality of downloaded data items degrades. We use number of missed uploads to measure data quality. Higher the value of missed updates lower is the quality of data.


## 5.2. Experimental Setup

The experiment is based on a200×200 m2 street intersection of one horizontal road and one vertical road where each two-way road has two lanes. One RSU server is put at the center of the junction. To generate the vehicle traffic, we randomly deploy 10 vehicles in each lane that makes a total of 40 vehicles. All vehicles move towards either end of the road. They are moving forward and backward during the simulation to have the continuous traffic flow in the intersection area. When one vehicle reaches the end of the road, which means the vehicle will move out of the RSU service area, its request not serviced will be dropped.We used ns-3 [22] network simulation platform to evaluate performance of the proposed algorithms. Although currently ns-3 does not support detailed VANETs simulation but it has excellent implementation ofWifi Models and is accurately capable to test diverse protocols at application layer.We implement two applications, namely,ServerApp andClientApp by extendingApplication class of ns-3 built-in API. TheClientApp requests various data items to theServerApp. It composes the request in form of packets by using data size, deadline, operation and data ID. Data size is the size of the packet. The deadline is calculated by current location, average speed and the coverage area of the RSU. The operation can by upload or download. The data ID is used to distinguish various data items. The deadline, operation and data ID values are added to the packet by usingtagging facility of ns-3. Three classes, namely,DeadlineTag,OperationTag, andDataIdTag, where defined by extendingTag base class for deadline, operation and data ID parameters, respectively. Thenode of ns-3 is considered as the vehicle (client) with mobility capabilities. TheclientApp is installed on all client nodes.TheServerApp performs all scheduling operations. It reads various parameters of incoming requests from clients and assigns weight and priority accordingly to each request. After user defined simulation time, it schedule all received requests according to the scheduling algorithm and responds to all clients. A stationary node is taken as RSU and theServerApp is installed on it.We define two helper classes, namely,ServerAppHelper andClientAppHelper, to facilitate easy configuration of the server application and the client application, respectively.The RSU node and the client nodes contain respective NICs (network interface cards) by usingNetDevice implementation of ns-3. Also, all nodes (RSU/server node, vehicles/client nodes) are configured with real IP addresses using IPv4 API of ns-3. TheAttribute facility of ns-3 is used to configure various components of the simulation. Such as,SetDeviceAttribute,SetChannelAttribute are used to configure DataRate of the devices and Delay of the channel, respectively. And,SetPropagationDelay,AddPropagationLoss methods are used to configure the wifi channel similar to real VANETs environment. At the physical layer,OfdmRate6Mbps andWIFI_PHY_STANDARD_80211_10MHZ is used to comply with IEEE 802.11 p/WAVE Standard. TheSetAttribute ofClientAppHelper is used to set various elements such asMaxPackets,Interval andPacketSize.The highway is created by usingGridPositionAllocator of ns-3 mobility component. The vehicles maintain distance of ten meters with each other and can move between user-defined initial and maximum range. The RSU is fixed at the specific location at the highway and it has fixed coverage area to serve the clients/vehicles.The ns-3tracing facility withcallbacks is used to calculate deadline and add various tags to packets by definingtrace sources andtrace sinks. Also, thelogging facility is used to test and evaluate various results.We also implemented FCFS, EDF, SDF, andD*S/N in ns-3 and compared these with proposed scheme using same data inputs.We measure performance of proposed algorithm under various scenarios based on a new metric called Impact Factor (IF) defined as:Impact Factor (IF) = Number of HUPD data items/total number of data items (NOD).Based upon value of impact factor there can be three possible cases. For evaluation of each scenario we used service ratio and data quality as metrics. We have taken Case 1, whereIF=0.8 that is, number of requests for emergent items is more, Case 2, where IF=0.6 showing scenario where requests for safety and nonsafety items is almost equal and, Case 3, where IF=0.2 and requests for nonsafety items are more. We studied the effect of arrival rate λ and data set size on service ratio and data quality.


## 5.3. Effect of Arrival Rate on Service Ratio

Case 1 (when IF is 0.8).
In this case most of the requested data items belong to HUPD. This case reflects the scenario where almost all requests are coming for high priority items that is, in such scenario, most of the requested data items belong to HUPD. We evaluated each of above mentioned algorithm in this scenario by takingIF=0.8. Arrival rate λ is varied from 6 to 20. Value of access pattern θ is set to 0.6. Figure 4(a) shows the effect of arrival rate on service ratio. The service ratio of all algorithms decreases as arrival rate increases. QASS has the highest service ratio as compared DSN and other basic scheduling schemes FCFS, EDF and SDF. For higher values of arrival rate QASS and DSN almost perform same. QASS performs better than others as it assigns higher priority weights for more emergent requests and here in this case 80% of the requests are in that category.Figure 4
Effect of arrival rate (λ) on service ratio in (a) Case 1, (b) Case 2, and (c) Case 3.
(a)
(b)
(c)Case 2 (when IF is 0.6).
This case reflects normal scenario where HUPD data is not referred so frequently that is, traffic density is normal and requests for safety or critical data are normal. We tested this case by takingIF=0.6. Arrival rate λ is varied from 6 to 20. Value of access pattern θ is set to 0.6. Figure 4(b) shows the performance of proposed algorithm along with others in that case.Case 3 (when IF is 0.2).
This case reflects the scenario where number of requests for critical or safety related data is least. We have simulated this case by takingIF=0.2. So here in this case only 20% of the total requests are assumed to be for HUPD data and 80% for nonsafety data. Service ratio against different values of arrival rate is observed. Figure 4(c) shows the service ratio of proposed algorithm along with others for Case 3. Service ratio of QASS is better than basic scheduling algorithms and similar to DSN. This is because it uses all parameters such as deadline, size and number of outstanding requests for scheduling information as is the case of DSN algorithm. Other methods that is, FCFS, EDF and SDF do not combine these parameters so do not perform as good as QASS and DSN.


## 5.4. Effect of Arrival Rate on Data Quality

Case 1 (when IF is 0.8).
Quality of data is equally important as service ratio. Data quality is measured by number of missed updates for items. Lower the number of missed updates better is quality of data. In this case most of requests are for HUPD data and algorithm is optimized for high priority requests so numbers of missed updates are least in case of QASS. Figure5(a) illustrates that quality of data delivered in this case is significantly better than all other algorithms and also service ratio is better than FCFS, SDF, and EDF, and as good as DSN.Figure 5
Effect of arrival rate (λ) on data quality in (a) Case 1, (b) Case 2, and (c) Case 3.
(a)
(b)
(c)Case 2 (when IF is 0.6).
Figure5(b) shows that proposed algorithm provides better service ratio than FCFS, SDF and EDF and slightly better than DSN. Here also arrival rate λ is varied between 6 and 20 and θ is set to 0.6. Numbers of missed updates are again least in QASS and it increases as arrival rate increases.Case 3 (when IF is 0.2).
In this case most of requests are for non HUPD data items. But QASS does distinguish between upload and download requests and accordingly readjusts which is not the case in other algorithms, so numbers of missed updates are least in case of QASS. Figure5(c) illustrates that quality of data delivered in this case is significantly better than all other algorithms and also service ratio is better than FCFS, SDF, EDF, and DSN.


## 5.5. Effect of Data Set Size on Service Ratio

Case 1 (when IF is 0.8).
The data set size value is varied between 10 and 50. The corresponding service ratio is shown in Figure6(a). Maximum requests in this case belong to HUPD. The number requests increases in proportion to the increase number of items. We evaluated each of above mentioned algorithm in this scenario by taking IF=0.8. Arrival rate λ is assumed as 10. Value of access pattern θ is set to 0.6. The service ratio all algorithms decrease as we increase number of items at server. QASS has the highest service ratio as compared DSN and other basic scheduling schemes FCFS, EDF and SDF. QASS performs better than other as it assigns higher priority weights for more emergent requests and here in this case 80% of the requests are in that category.Figure 6
Effect of data set size (N) on service ratio in (a) Case 1, (b) Case 2, and (c) Case 3.
(a)
(b)
(c)Case 2 (when IF is 0.6).
This case reflects normal scenario where HUPD data is not referred so frequently that is, traffic density is normal and requests for safety or critical data are normal. We tested this case by takingIF=0.6. Data set size here also varied from 10 to 50. Value of access pattern θ is set to 0.6. Figure 6(b) shows the performance of proposed algorithm along with others in that case. Service ratio of all algorithms decreases marginally with increase in data set size. Decrease is lowest again in case of QASS.Case 3 (when IF is 0.2).
Here in this case only 20% of the total requests are assumed to be for HUPD data and 80% for nonsafety data. Service ratio against different values of data set size is observed. Figure6(c) shows the service ratio of proposed algorithm along with others for Case 3. Service ratio of QASS is better than basic scheduling algorithms and similar to DSN. This is because it uses all parameters such deadline, size and number of outstanding requests for scheduling information as is the case in DSN algorithm. Other methods that is, FCFS, EDF, and SDF do not combine these parameters so do not perform as well as QASS and DSN.


## 5.6. Effect of Data Set Size on Data Quality

Case 1 (when IF is 0.8).
Figure7(a) shows the quality of data as we increase data set size from 10 to 50. Arrival rate is set to 10 and access pattern value is taken 0.6. QASS has least number of missed updates so it performs significantly better than all other algorithms. When IF is taken as 0.8, concentration of HUPD requests is maximum and QASS prioritize these requests. So with increase in number of data set size, missed updates increase marginally.Figure 7
Effect of data size (N) on data quality in (a) Case 1, (b) Case 2, and (c) Case 3.
(a)
(b)
(c)Case 2 (when IF is 0.6).
When IF is taken 0.6 then HUPD requests presence is almost half of total requests. Accordingly QASS prioritizes only that much requests so number of missed updates in this case is more with increase in data set size. QASS performs better than its counterparts. Results are shown in Figure7(b).Case 3 (when IF is 0.2).
Figure7(c) shows the data quality of proposed algorithm along with others for Case 3. Requests for HUPD items in this case are only 20%. Most items are in LUPD group so algorithm very much works like DSN. Data quality of QASS is better than basic scheduling algorithms and similar to DSN. This is because QASS uses all parameters such deadline, size, and number of outstanding requests for scheduling information as is the case in DSN algorithm. Other methods, that is, FCFS, EDF, and SDF, do not combine these parameters and so do not perform as well as QASS and DSN.


## 6. Conclusion

In this paper we proposed a new data scheduling scheme for vehicular ad hoc networks. The proposed scheme first categorizes data items into two classes, that is, high update priority data and low update priority data. Different weights are assigned to these two classes such that more weightage is given to data items of class high update priority data. Both update and download requests are maintained in common queue. Priority assigning algorithm assigns priorities to upload requests by using formula(Di*Si)/Ni*Wi2 or (Di*Si)/Wi2 depending upon whether download requests exist for same data item or not and to download requests by using formula (Di*Si)/(Ni*Wi). RSU schedules these requests according to their priorities. Simulation result shows that the proposed algorithm provides better service ratio and data quality than earlier algorithms.



---

*Source: 282978-2015-05-19.xml*