Online Algorithm for Opportunistic Handling of Received Packets in Vehicular Networks

Ala Al-Fuqaha, Ammar Gharaibeh, Ihab Mohammed, Sayed Jahed Hussini, Abdallah Khreishah, Issa Khalil

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


In vehicular ad-hoc networks, due to high mobility, vehicles usually communicate for short periods of time with several neighboring vehicles and are required to process data fast; sometimes in the order of few milliseconds. This urgency of data processing is further heightened in safety-critical scenarios that involve many vehicles. Such scenarios require data to be prioritized and processed with minimum delay. While packet scheduling has been extensively studied, these studies focus on channel scheduling, our work focuses on processing received packets by a vehicle in dense scenarios. In this paper, we formulate the prioritized data processing problem as an integer linear program given a prior knowledge of the request sequence and prove that it is NP-complete. Due to the difficulty of predicting the traffic patterns and obtaining the request sequence in advance, we propose an online algorithm that does not require the prior knowledge of the request sequence and achieves an \mathcal {O}(1) competitive ratio. The proposed online algorithm strives to accept higher severity packets for processing in order to maximize the cumulative severity given vehicular communications/computation capacity constraints. Using real traffic traces, we evaluate the performance of the online algorithm against three online algorithms, in which two of them use an exponentially weighted moving average-based threshold while the other one accepts requests as capacity permits. Our evaluation shows that our algorithm achieves up to 492% more cumulative severity compared to the three other baseline algorithms.

Original languageEnglish (US)
Article number8316918
Pages (from-to)285-296
Number of pages12
JournalIEEE Transactions on Intelligent Transportation Systems
Issue number1
StatePublished - Jan 2019

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications


  • online algorithm
  • packet scheduling


Dive into the research topics of 'Online Algorithm for Opportunistic Handling of Received Packets in Vehicular Networks'. Together they form a unique fingerprint.

Cite this