  Low-latency provenance embedding methods have received traction in vehicular
networks for their ability to track the footprint of information flow. One such
known method is based on Bloom filters wherein the nodes that forward the
packets appropriately choose a certain number of hash functions to embed their
signatures in a shared space in the packet. Although Bloom filter methods can
achieve the required accuracy level in provenance recovery, they are known to
incur higher processing delay since higher number of hash functions are needed
to meet the accuracy level. Motivated by this behaviour, we identify a regime
of delay-constraints within which new provenance embedding methods must be
proposed as Bloom filter methods are no longer applicable. To fill this
research gap, we present network-coded edge embedding (NCEE) protocols that
facilitate low-latency routing of packets in vehicular network applications.
First, we show that the problem of designing provenance recovery methods for
the NCEE protocol is equivalent to the celebrated problem of compressed
sensing, however, with additional constraints of path formation on the
solution. Subsequently, we present a family of path-aware orthogonal matching
pursuit algorithms that jointly incorporates the sparsity and path constraints.
Through extensive simulation results, we show that our algorithms enjoy
low-complexity implementation, and also improve the path recovery performance
when compared to path-agnostic counterparts.
