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 [7] 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

FIGURE 8.2

Hybrid tree for fast enqueue and dequeue operations.

FIGURE 8.3

Enqueue time of linked list and hybrid tree.

FIGURE 8.4

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 [7].

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 [7]. 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 [7].

Other data structures which may perform well in comparison to the one proposed in the [7] can be ones which use the binary search tree for the storage of both priority types. The different static priority messages are arranged

FIGURE 8.5

Hybrid data structure consisting of linked lists for static as well as dynamic priorities.

FIGURE 8.6

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 [7]. 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 [7] 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.

Summary

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.

References

• 1. "IEEE Standard for Information Technology - Local and metropolitan area networks - Specific requirements—Part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications amendment 6: Wireless access in vehicular environments/' in IEEE Std 802.11p-2010, pp.1-51, July 2010, doi: 10.1109/IEEESTD.2010.5514475.
• 2. H. Lee, J. Lee, S. Kim, and K. Cho, "Implementation of IEEE 802.11a wireless LAN," 2008 Third International Conference on Convergence and Hybrid Information Technology, Busan, 2008, pp. 291-296.
• 3. A. Grilo and M. Nunes, "Performance evaluation of IEEE 802.lie," The 13th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, Pavilhao Altantico, Lisboa, Portugal, 2002, pp. 511-517, vol. 1.
• 4. N. Gupta, A. Prakash, and R. Tripathi, "Medium access control protocols for safety applications in vehicular ad-hoc network: A classification and comprehensive survey," Vehicular Communications, 2(4), (2015): 223-237. doi: 10.1016/j. vehcom.2015.10.001
• 5. Raghavendra Pal, Nishu Gupta, Arun Prakash, and Rajeev Tripathi, "Adaptive mobility and range based clustering dependent MAC protocol for vehicular ad- hoc networks," Wireless Personal Communications, Springer, 98 (2018): 1155-1170. doi: 10.1007/sll277-017-4913-9
• 6. B. J. Kenny, "Dedicated short-range communications (DSRC) standards in the United States," Proceedings of the IEEE, 99(7) (2011): pp. 1162-1182.
• 7. R. Pal, A. Prakash, R. Tripathi, and K. Naik, "Scheduling algorithm based on preemptive priority and hybrid data structure for cognitive radio technology with vehicular ad hoc network," IET Communications, 13(20) (2019): 3443-3451.
• 8. R. Pal, A. Prakash, R. Tripathi, and K. Naik, "Regional super cluster based optimum channel selection for CR-VANET," IEEE Transactions on Cognitive Communications and Networking, 6(2) (2020): 607-617. doi: 10.1109/TCCN.2019. 2960683
• 9. Raghavendra Pal, Arun Prakash, and Rajeev Tripathi, "Triggered CCHI multichannel MAC protocol for vehicular ad hoc networks," Vehicular Communications, Elsevier, 12 (2018): 14-22. doi: 10.1016/j.vehcom.2018.01.007
• 10. Raghavendra Pal, Arun Prakash, Rajeev Tripathi, and Dhananjay Singh, "Analytical model for clustered vehicular ad hoc network analysis," ICT Express, Elsevier, 4(3) (2018): 160-164. doi: 10.1016/j.icte.2018.01.001
• 11. Pant Varun Prakash, Saumya Tripathi, Raghavendra Pal, and Arun Prakash, "A slotted multichannel MAC protocol for fair resource allocation in VANET," IJMCMC, IGI global, 9(3) (2018): 45-59. doi: 10.4018/IJMCMC.2018070103
• 12. P. Singh, R. Pal, and N. Gupta, "Clustering based single-hop and multi-hop message dissemination evaluation under varying data rate in vehicular ad- hoc network," in Choudhary, R., Mandal, J., Auluck, N., and Nagarajaram, H. (eds) Advanced Computing and Communication Technologies. Advances in Intelligent Systems and Computing, vol 452. Springer, Singapore, 2016.

• 13. U. Prakash, R. Pal, and N. Gupta, "Performance evaluation of IEEE 802.11p by varying data rate and node density in vehicular ad hoc network," 2015 IEEE Students Conference on Engineering and Systems (SCES), Allahabad, 2015, pp. 1-5. doi: 10.1109/SCES.2015.7506457
• 14. В. B. Dubey, N. Chauha, N. Chand, and L. K. Awasthi, "Priority based efficient data scheduling technique for VANETs," Wireless Networks, 22(5) (2016): 1641-1657. doi: 10.1007/sll276-015-1051-8.