Quick Enqueue and Dequeue Operations
As already mentioned, the packets in the queue are required to be frequently rearranged due to two reasons. First is the reception and generation of messages and the second is a change in the dynamic priority of the message due to its deadline. This frequent rescheduling of queues can cause additional delay to the messages. Researchers have paid little attention towards this area. Authors in  have proposed a hybrid data structure consisting of a linked list and several red-black search trees. The linked list contains the packets with different static priorities. Each node on the linked list acts as the root node of the red-black search tree. Each tree contains packets of the same static priority and different dynamic priorities, as shown in Figure 8.2.
Whenever a vehicle receives a packet for forwarding, it stores the packet in the hybrid tree. The linked list is first checked for similar static priority nodes in comparison to the packet. When it searches it, the correct position in the corresponding red-black search tree is identified according to its dynamic priority. The authors have compared the enqueue and dequeue times of the packets with the linked list. Figures 8.3 and 8.4 show the enqueue and dequeue times, respectively, for the linked list and hybrid tree.
As the number of pre-existing packets in the queue increases, the enqueue and dequeue times increase as well. However, the performance of the hybrid tree is much better in comparison to the linked list. It shows the effectiveness of the data structure in reducing the queuing delay.
This work motivates us to explore some other forms of data structures. They have combined the linked list and red-black search tree to form a hybrid data structure. Some other combinations can also be used for the reduction of enqueue and dequeue times. The first of these combinations is
Hybrid tree for fast enqueue and dequeue operations.
Enqueue time of linked list and hybrid tree.
Dequeue time of linked list and hybrid tree.
a hybrid of two linked lists, as shown in Figure 8.5. The first linked list contains the packets of different static priorities. Every other linked list contains the packets of the same static priorities but different dynamic priorities. If a packet is received by the vehicle, it will first search for the node in the first linked list which has a similar static priority as that of the packet. Then it will search the corresponding linked list which contains all the packets of the same static priority. It will go all the way to the position where the dynamic priority of the packet is lesser than the next packet and higher than the previous packet. This data structure will cause additional delays in comparison to the one proposed in .
The next possible data structure can be the combination of the linked list and the binary search tree and will be similar to the one shown in the . The only difference is that it uses the binary search tree instead of the red- black search tree, as shown in Figure 8.6. Since the red-black search tree is more efficient than the binary search tree, this data structure will have higher delays in comparison to .
Other data structures which may perform well in comparison to the one proposed in the  can be ones which use the binary search tree for the storage of both priority types. The different static priority messages are arranged
Hybrid data structure consisting of linked lists for static as well as dynamic priorities.
Data structure consisting of linked list and binary search trees.
in a binary search tree and each node of this binary search tree acts as the root for another tree which has packets of the same static priorities but different dynamic priorities. This data structure may or may not perform well in comparison to . It requires an analysis using any simulation tool or hardware. The most efficient data structure that has the highest chances of performing well in comparison to  is a combination of red-black search trees. One red-black search tree contains the packets of different static priorities. Every node in this tree acts as the root of another tree that contains packets of the same static priority but different dynamic priorities. There may be other data structures which can be used in the vehicular communication. Extensive research is required in this area.
This chapter presented the classification of messages in vehicular communication. It highlights the ways in which the priorities of different packets are defined. It talks about two types of priorities: One is a static priority, and another is a dynamic priority. Static priority is directly obtained by the message type. To calculate dynamic priority, some parameters are taken into account. These parameters are the speed of the vehicle, distance between the transmitting and receiving vehicle, message size, deadline of the message, etc. Further, it talks about the data structure in which the packets are scheduled. The frequent rescheduling of queues makes it necessary to develop an efficient data structure which allows fast enqueue and dequeue operations. Otherwise these operations can cause additional delays to packet transmission. The possible combination of various data structures is also described. Researchers can take it into account when designing more efficient data structures.