QoS Aware Service Scheduling Scheme for VANETs

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.

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. Section 2 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 Figure 1.

Figure 1

Typical VANET scenario.

As shown in Figure 1, 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 Figure 2.

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. proposed $D * 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 modifies $D * 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 * W)}^{2}$ 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 Table 1). (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 $T_{CLT}$ .

(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 be k data items $D = {d_{1}, d_{2}, d_{3}, \dots, d_{k}}$ , $0 < k < \infty$ . Let m out of k data items belong to HUPD such that $m \leq k$ LUPD = D − HUPD. LUPD contains remaining $k - m$ data items, so HUPD and LUPD are mutually exclusive.

//Algorithm to assign weight

N = total number of requests in window

for $j = 1$ to k

do if $d_{j}$ ∈ HUPD

$W (d_{j}) = N$

else

$W (d_{j}) = 1$

$F [{request}_{i}] = 1$ , $S [{request}_{i}] = 0$

4.3. Assigning Priorities to Various Requests

Priority assigning algorithm uses following notations: (i)

$D_{i}$ : Deadline of ${request}_{i}$ .

(ii)

$S_{i}$ : Size of data item referred in ${request}_{i}$ .

(iii)

$W_{i}$ : Weight of data item referred in ${request}_{i}$ .

(iv)

$P ({request}_{i})$ : Priority assigned to ${request}_{i}$ .

(v)

$N_{i}$ : Number of download requests for same data items requested in ${request}_{i}$ .

//Algorithm for assigning priorities

for $i = 1$ to 1

do if ${request}_{i}$ is download request and no upload request exists for same data item in current window

then $P ({request}_{i}) = (D_{i} * S_{i}) / (N_{i} * W_{i})$

else if ${request}_{i}$ is upload request

if download request also exists for same data item

then $P ({request}_{i}) = (D_{i} * S_{i}) / {(N_{i} * W_{i})}^{2}$

else

$P ({request}_{i}) = (D_{i} * S_{i}) / W_{i}^{2}$

The smaller the value of $P ({request}_{i})$ the higher will be the priority.

Above algorithm steps are shown in Figure 3.

Figure 3

Priority Assigning Algorithm.

Theorem 1.

The proposed priority assigning algorithm assigns highest priority to update requests of HUPD data items.

Proof.

Let $R_{1}$ request is for uploading HUPD data item $d_{1}$ . Then priority assigned to $R_{1}$ will be as follows:

\begin{matrix} P (R_{1}) = \frac{(D_{1} * S_{1})}{{(N_{1} * W_{1})}^{2}}, \end{matrix}

(1)

where

D_{1}

is deadline of

R_{1}

S_{1}

is size of data item requested in

R_{1}

N_{1}

is number of download requests for

d_{1}

, that is, data item requested in

R_{1}

W_{1} = N

, and N is window size.

Let $R_{2}$ be request for downloading HUPD data item $d_{2}$ , then priority assigned to $R_{2}$ will be as follows:

\begin{matrix} P (R_{2}) = \frac{(D_{2} * S_{2})}{(N_{2} * W_{2})}, \end{matrix}

(2)

where

D_{2}

is deadline of

R_{2}

S_{2}

is size of data item requested in

R_{2}

N_{2}

is number of download requests for

d_{2}

, that is, data item requested in

R_{2}

W_{2} = N

, and N is window size.

In worst case there would be no download request for $d_{1}$ . 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

\begin{matrix} D_{1} = 1.5 D_{2}, S_{1} \approx S_{2} \end{matrix}

(3)

maximum value of

N_{2}

can be

N - 2

. So, 1 would be as follows:

\begin{matrix} P (R_{1}) = 1.5 D_{2} * \frac{S_{2}}{N^{2}} \end{matrix}

(4)

and 2 can be written as

\begin{matrix} P (R_{2}) = \frac{(D_{2} * S_{2})}{(N^{2} - 2 N)} . \end{matrix}

(5)

Even for nominal window size 5, $P (R_{1}) < P (R_{2})$ . Hence priority of $R_{1}$ would be more than priority of $R_{2}$ . 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.

$d_{i}$ : Data requested in ${request}_{i}$ that is, ith request; $0 < i \leq 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 \leq N$ .

$F [1, N]$ : Finish array, $F [i] = 0$ means ith request is unprocessed, $F [i] = 1$ means ith request is processed; $0 < i \leq N$ .

$S [1, N]$ : Success array $S [i] = 0$ means ith request is unsuccessful, $S [i] = 1$ means ith request is successful; $0 < i \leq N$ .

$D [1, N]$ : Deadline array; $0 < i \leq N$ .

$P [1 \dots N]$ : Priority generated by algorithm as discussed earlier.

$T_{j}$ : Actual transfer time of data requested in request that is, ${request}_{j}$ .

//Algorithm to process requests

for $i = 1$ to N

$F [i] = 0$ //initially each request is unprocessed

$S [i] = 0$ //initially each request is unsuccessful

${request}_{i} = {i | P [i]$ is minimum i.e., highest priority request and $F [i] \neq 1}$ ; $0 < i \leq N$

if ( $C [{request}_{i}] = = d$ )

then if ( $T_{CLT} \geq T_{d i}$ )

then broadcast $d_{i}$ and $F [{request}_{i}] = 1$ , $S [{request}_{i}] = 1$

else

$F [{request}_{i}] = 1$ , $S [{request}_{i}] = 0$

else if ( $T_{CLT} \geq T_{d i}$ )

then allocate channel to upload $d_{i}$ and

$F [{request}_{i}] = 1$ , $S [{request}_{i}] = 1$

else

$F [{request}_{i}] = 1$ , $S [{request}_{i}] = 0$

for $j = 1$ to N

do if (( $d_{j} = = d_{i}$ ) AND ( $C [j] = = C [{request}_{i}]$ ) AND ( $D [j] \geq T_{j}$ ))

then $F [j] = 1$ , $S [j] = 1$

if (( $d_{j} = = d_{i}$ ) AND ( $C [j] = = C [{request}_{i}]$ ) AND ( $D [j] < T_{j}$ ))

then $F [j] = 1$ , $S [j] = 0$

if ( $S [{request}_{i}] = = 1$ )

then for $j = 1$ to N

do if ( $F [j] = = 0$ ) then $D [j] = D [j] - T_{{request}_{i}}$

if ( $F [i] = = 1$ ) is true for some i repeat through step 2

Exit

Step 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] \geq T_{j}$ ), 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 $d_{i}$ is missed due to deadline not met, then out dated data will be served to the next downloading request for the data item $d_{i}$ . 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 a $200 \times 200$ m² 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 of Wifi Models and is accurately capable to test diverse protocols at application layer.

We implement two applications, namely, ServerApp and ClientApp by extending Application class of ns-3 built-in API. The ClientApp requests various data items to the ServerApp. 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 using tagging facility of ns-3. Three classes, namely, DeadlineTag, OperationTag, and DataIdTag, where defined by extending Tag base class for deadline, operation and data ID parameters, respectively. The node of ns-3 is considered as the vehicle (client) with mobility capabilities. The clientApp is installed on all client nodes.

The ServerApp 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 the ServerApp is installed on it.

We define two helper classes, namely, ServerAppHelper and ClientAppHelper, 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 using NetDevice 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. The Attribute 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 and WIFI_PHY_STANDARD_80211_10MHZ is used to comply with IEEE 802.11 p/WAVE Standard. The SetAttribute of ClientAppHelper is used to set various elements such as MaxPackets, Interval and PacketSize.

The highway is created by using GridPositionAllocator 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-3 tracing facility with callbacks is used to calculate deadline and add various tags to packets by defining trace sources and trace sinks. Also, the logging facility is used to test and evaluate various results.

We also implemented FCFS, EDF, SDF, and $D * 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, where $IF = 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 taking $IF = 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.

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 taking $IF = 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 taking $IF = 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. Figure 5(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.

Case 2 (when IF is 0.6).

Figure 5(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. Figure 5(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 Figure 6(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.

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 taking $IF = 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. Figure 6(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).

Figure 7(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.

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 Figure 7(b).

Case 3 (when IF is 0.2).

Figure 7(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 $(D_{i} * S_{i}) / {(N_{i} * W_{i})}^{2}$ or $(D_{i} * S_{i}) / W_{i}^{2}$ depending upon whether download requests exist for same data item or not and to download requests by using formula $(D_{i} * S_{i}) / (N_{i} * W_{i})$ . 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.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

Yin

Elbatt

Yeung

Ryu

Habermas

Krishnan

Talty

Performance evaluation of safety applications over DSRC vehicular ad hoc networks

Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks (VANET '04)

October 2004

1 9

2-s2.0-14944347139

Yang

Liu

Zhao

Vaidya

N. H.

A vehicle-to-vehicle communication protocol for cooperative collision warning

Proceedings of 1st Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MOBIQUITOUS '04)

August 2004

114 123

2-s2.0-13244255377

Mak

T. K.

Laberteaux

K. P.

Sengupta

A multi-channel VANET providing concurrent safety and commercial services

Proceedings of the 2nd ACM International Workshop on Vehicular Ad Hoc Networks (VANET '05)

September 2005

1 9

2-s2.0-33745957362

Lee

S. B.

Pan

Park

J. S.

Gerla

Secure incentives for commercial ad dissemination in vehicular networks

Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '07)

2007

150 159

Bychkovsky

Hull

A measurement study of vehicular internet access using in situ Wi-Fi networks

Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (MobiCom '06)

2006

50 61

Hull

Bychkovsky

Zhang

Chen

Goraczko

CarTel: a distributed mobile sensor computing system

Proceedings of the 4th ACM International Conference on EmbeddedNetworked Sensor Systems (SENSYS '06)

2006

Boulder, Colo, USA

125 138

Ott

Kutscher

Drive-thru internet: IEEE 802.11b for 'automobile' users

Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '04)

March 2004

IEEE

362 373

2-s2.0-8344283536

10.1109/INFCOM.2004.1354509

Hadaller

Keshav

Brecht

Agarwal

Vehicular opportunistic communication under the microscope

Proceedings of the 5th International Conference on Mobile Systems, Applications and Services (MobiSys '07)

2007

206 219

IEEE Standard for Information Technology-Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment 6: Wireless Access in Vehicular Environments

IEEE Std. 802.11p-2010 (Amendment to IEEE Std. 802.11), 2007

10.

IEEE Std. 802.11e-2005

IEEE Standard for Information Technology-Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 8: Medium Access Control (MAC) Quality of Service Enhancements

Amendment to IEEE Std. 802.11, 1999 Edition (Reaff 2003), 2005

11.

Wong

K. D.

Tepe

Chen

Gerla

Inter-vehicular communications

IEEE Wireless Communications 2006 13 5 6 7

10.1109/wc-m.2006.250351

2-s2.0-33845596875

12.

Santos

R. A.

Edwards

Álvarez

Towards an inter-vehicle communication algorithm

Proceedings of the 3rd International Conference on Electrical and Electronics Engineering

September 2006

Veracruz, Mexico

1 4

10.1109/iceee.2006.251843

2-s2.0-42749099124

13.

Durresi

Barolli

Adaptive inter vehicle communications

International Journal of Wireless Information Networks 2006 13 2 151 159

10.1007/s10776-006-0030-5

2-s2.0-33744524842

14.

Tassiulas

Broadcast scheduling for information distribution

Proceedings of the 16th Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution (INFOCOM '97) 1997 1

Kobe, Japan

109 117

10.1109/INFCOM.1997.635120

15.

Aksoy

Franklin

R×W: a scheduling approach for large-scale on-demand data broadcast

IEEE/ACM Transactions on Networking 1999 7 6 846 860

10.1109/90.811450

2-s2.0-0033352389

16.

Gandhi

Khuller

Kim

Y.-A.

Wan

Y.-C.

Algorithms for minimizing response time in broadcast scheduling

Algorithmica 2004 38 4 597 608

10.1007/s00453-003-1058-x

MR2032527

2-s2.0-21044440288

17.

Acharya

Muthukrishnan

Scheduling on demand broadcasts: new metrics and algorithms

Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM '98)

October 1998

Dallas, Tex, USA

43 54

18.

Tang

Lee

W.-C.

Time-critical on-demand data broadcast: algorithms, analysis, and performance evaluation

IEEE Transactions on Parallel and Distributed Systems 2006 17 1 3 14

10.1109/tpds.2006.14

2-s2.0-31344449346

19.

Jiang

Vaidya

Scheduling data broadcast to ‘impatient’ users

Proceedings of the 1st ACM International Workshop on Data Engineering for Wireless and Mobile Access (MobiDe '99)

1999

52 59

10.1145/313300.313385

20.

Zhang

Zhao

Cao

Service scheduling of vehicle-roadside data access

Mobile Networks and Applications 2010 15 1 83 96

10.1007/s11036-009-0170-9

2-s2.0-76549097373

21.

Fridman

Weber

Graff

Breen

D. E.

Dandekar

K. R.

Kam

OMAN: a mobile ad hoc network design system

IEEE Transactions on Mobile Computing 2012 11 7 1179 1191

10.1109/tmc.2011.176

2-s2.0-84861453167

22.

http://www.nsnam.org/