Abstract: For effective packets scheduling in inter-vehicular communication, we design a hybrid priority-queuing model with a view to the difference of delay-sensitivity and packet length of services. By studying the transmission delay of 5 schemes, we prove that the non-preemptive short-packet-first scheme results in the minimal overall delay. In our scheduling model, the preemptive scheme is adopted for delay-sensitive services and the non-preemptive short-packet-first scheme is adopted for non-delay-sensitive services. The results from simulation experiments in NS-2 verified the superiority of our model by such performance indices as packet delivery ratio and throughput.
INTRODUCTION
Inter-vehicular Communication (IVC) is valuable for such applications as driving safety, road information inquiry and mobile office. There are distinct differences among IVC services on data type, packet length and Qos constraints, so a scheduling method is needed to guarantee the effective packets transmission for each service. In this study, 5 priority-queuing schemes are proposed with a view to the different features of IVC services. By detailed analysis, the non-preemptive short-packet-first scheme is verified to result in the minimal delay. And a hybrid scheduling model is developed with different measures for delay-sensitive and non-delay-sensitive services.
RELATED WORKS
Research on scheduling for IVC: Most research works on packets scheduling in IVC focus on setting priority levels based on node speed, data type, message utility, duration of valid message (Bouassida and Shawky, 2010), node position (Mi et al., 2008), packet size, time threshold (Zhang et al., 2007) and packet delivery ratio (Liu et al., 2008). The First-Come-First-Serve (FCFS) strategy is adopted for packets with equal priority and no improvement is made toward the diversified features of services.
Research on priority-queuing model: A single-server priority-queuing model is adopted for scheduling. The measures for dealing with packets collision include preemptive and non-preemptive schemes. Most works yield waiting time, queue length (Kim and Chae, 2010), packet-dropping ratio (Zaborovsky et al., 2010), packet-blocking ratio (Awan and Fretwell, 2005). All these works have not taken more features of services into consideration. Further improvements include the preemptive, short-packet-first scheduling scheme (Liu et al., 2006; Li and Liu, 2005), which decrease the overall waiting time of packets by considering the difference of packets length. Present study explores transmission delays for all schemes with regards to the difference of packet length and delay-sensitivity and find out the optimal scheme.
DESIGN OF SCHEDULING MODEL
Queuing models for different services: The delay-sensitive services pose strict constraints on reliability and delay for message transmission, so they should be granted preemptive priority. And for minimizing the transmission delay of all services, it is necessary to consider the following 2 problems. One is whether preemptive or non-preemptive priority should be granted to a non-delay-sensitive service? The other is, for two colliding packets with equal importance, whether the longer or the shorter packet should be granted higher priority?
A single-server queuing model is built to deal with the above 2 problems. We assume that there exist 2 non-delay-sensitive services with equal importance, including data message AppS and multimedia message AppL. The packet length LenS of AppS is shorter than packet length LenL of AppL. The packet arrival for both of them can be described as Poisson process. Given arrival rate of Poisson flow for each service, i.e., λS and λL, the data rates are rateS = λS*LenS and rateL = λL*LenL respectively. In addition, the time for packets processing follows general distribution, so the basic queuing model is specified as M/G/1. All possible schemes are listed as follows:
| • | No distinction of priority (NonPr): AppS and AppL have the same priority level. This scheme is equivalent to FCFS strategy |
| • | Preemptive long packet first (PrmLF): AppL has preemptive priority over AppS. When AppS packet is being served, an incoming AppL packet will seize the service immediately and the AppS packet returns to the front of queue |
| • | Preemptive short packet first (PrmSF): This scheme is analogous to PrmLF, except that AppS has preemptive priority over AppL |
| • | Non-preemptive long packet first (NPrLF): AppL has non-preemptive priority over AppS. An incoming AppL packet will not be served until current processing for AppS packet is finished |
| • | Non-preemptive short packet first (NPrSF): This scheme is analogous to NPrLF, except that AppS has non-preemptive priority over AppL |
Basic conclusions on priority-queuing: Given mathematical expectation E (B) and 2nd order origin moment E (B2) of service time for a packet, we have traffic intensity ρ = λxE(B). The waiting time of a newly incoming packet Pkt is composed of 2 parts. One is the service time of E (L) packets in front of Pkt, the other is the residual service time E (R) of one packet that is being served with probability ρ. So the total waiting time is E (W) = E (L) E (B)+ρE (R). Combining little’s law E (L) = λE (W), we yield E (W) = ρE (R)/(1-ρ) (Adan and Resing, 2001) yield:
| (1) |
The average residual time E (Si)np for non-preemptive schemes is the sum of E (Bi) and E (Wi) (Adan and Resing (2001)), i.e.:
| (2) |
Likewise, the average residual time E(Si)p for preemptive schemes is:
| (3) |
Selection of the optimal scheme
Theorem 1: The delay of NPrSF is smaller than that of NPrLF, i.e.:
| (4) |
Proof: Let LenL = KxLenS, K>1. First, we get DelayNPrSF. Assume the priority level of short packet is 1 and that of long packet is 2. The expectations of their service time are E’(B1) = B0 and E’(B2) = KB0 and the 2nd order origin moments of their service time are E’(B12) = Y and E’(B22) = K2Y, besides, E’(R2) = KE’(R1) = KY/(2B0). From Eq. 1 and 2, we have:
And the delay of long packets is:
So the total delay of NPrSF is:
| (5) |
Second, assume the priority level of long packet is 1 and that of short packet is 2. In the same way we have:
| (6) |
Third, the difference of Eq. 6 and 5 is:
With enough processing capacity, the sum of traffic intensity should be less than 1, i.e., ρ = ρS+ρL = λSB0+ λLKB0<1<2, so Eq. 4 holds.
Theorem 2: The delay of NPrSF is smaller than that of NonPr, i.e.:
| (7) |
Proof: For NonPr, the total arrival rate is λ = λS+λL and the total service rate is ρ = ρS+ρL = λSB0+λLKB0. So the mathematical expectation of service time is E (B) = (λSB0+λLKB0)/(λS+λL) and the 2nd order origin moment of service time is E (B2) = (λSY+λLK2Y)/(λS+λL). By Eq. 1, E (R) = (λSY+λLK2Y)/(2B0(λS+λLK)). And we have:
| (8) |
Equation 7 holds by the following inequality:
Theorem 3: The delay of NPrSF is smaller than that of PrmSF and the delay of NPrLF is smaller than that of PrmLF, i.e.:
| (9) |
| (10) |
Proof: From Eq. 1 and 3, we have:
| (11) |
Equation 9 holds by the following difference:
Likewise, Eq. 10 holds.
According to the 3 theorems, the NPrSF scheme results in the minimal delay. In our hybrid scheduling model for IVC services, a queue is ready for each priority. The delay-sensitive services have preemptive priority over services of lower priority and the shorter non-delay-sensitive services have non-preemptive priority over longer non-delay-sensitive services.
SIMULATION AND EVALUATION
Settings of simulation experiment: By experiment in NS-2, we make comparison among aforementioned 5 schemes. The simulation scenario is shown in Fig. 1, mobile node N1 is equipped with 3 interfaces, it forwards AppL messages from N3 and AppS messages from N2 to N0, in addition, it sends driving alert messages App0 to N0 at the rate of rate0 = 200 Byte sec-1. App0 is delay-sensitive CBR traffic with Len0 = 200 Byte, AppS and AppL are non-delay-sensitive poisson traffics with LenS = 200 Byte and LenL = 800 Byte, respectively. The speed of each node is 15 m sec-1.
The link bandwidth for N3-N1, N2-N1 and N1-N0 are 10, 10 and 2 Mb sec-1, respectively and the capacities of the transmission queues in N2, N3 and N1 are 50000, 50000 and 5000 packets, respectively, so for the traffic settings in Table 1, there are abundant capacities for links N3-N1 and N2-N1 and all packets from N3 and N2 can arrive at N1. But some packets from N1 cannot be sent to N0.
The simulation lasts for 75 sec. Packets are generated during the first 50 sec and the last 25 sec is spent for the transmission of remaining packets in the sending queue of N1.
| Table 1: | Scenarios of traffic distribution |
| Fig. 1: | Simulation scenario |
| Fig. 2: | PDR of the 2nd priority service |
| Fig. 3: | PDR of the 3rd priority service |
The total traffic volume in simulation is 10 M Byte. Because the traffic volume of App0 is very small, we have 50*(rateS+rateL)~10x106 and reduce the equation to λS+4λL = 1000, with which we set traffic scenarios in Table 1. We select such performance metrics as Packet Delivery Ratio (PDR) and throughput for evaluating the performance of transmission in N1-N0.
Performance evaluation: According to the results, N0 gets App0 packets immediately with PDR 100% and gets other packets at the front of queue with some delay; however, the late-arriving packets with lower priority may stay at the queue for a long time or be discarded. The detailed results are shown in Fig. 2-4.
In Fig. 2, the PDRs of the 2nd priority traffic (Pri2 for short) in long-packet-first schemes are approximately 100%, because the queue buffer is large enough to hold them. However, PDRs of Pri2 in short-packet-first schemes begin to drop at S6, because the queue for short packets overflows at S6. And the PDR of NonPr scheme is the lowest with the combination of short packets and long packets.
In Fig. 3, the PDRs of the 3rd priority traffic (Pri3 for short) for NPrSF are higher than other schemes and the minimum comes at S5.
| Fig. 4: | Throughput for all services |
From S1 to S5, the effect of increasing Pri2-packets on Pri3-packets becomes more and more obvious, so PDRs of Pri3-packets keep dropping. However, from S6 to S9, the number of Pri3-packets to be transmitted keeps decreasing, so their PDRs keep increasing. For NPrLF, the curve of PDR is similar to that of NPrSF with a minimum at S4. PDR of NPrLF at each scenario is smaller than that of NPrSF, because in NPrSF, short Pri2-packets are sent faster and more Pri3-packets have chances to be sent. For PrmSF and PrmLF, PDRs of Pri3-packets are approximately 0, because most Pri3-packets are preempted without any chances to be sent.
As for the throughput shown in Fig. 4, it is observed that NprSF scheme can provide the best overall performance. Compared with traditional FCFS strategy, i.e., NonPr, NPrSF and NPrLF are obviously superior. However, throughputs of PrmSF and PrmLF are mostly composed of only Pri2-packets, so they are much smaller.
CONCLUSION
By analysis and simulation, we verify that NPrSF scheme can get over the drawback of transmission blocking of packets with lower priority in preemptive schemes and act as a substitution for traditional FCFS scheme. The increasing waiting packets in queue may lead to larger transmission delay and queue overflow, so in further studies, it is worthy to: (1) research on the prediction of queue overflow time and the model of dynamic queue buffer allocation and (2) research on the scheme of dynamic priority level tuning to balance the traffic volume of different services.