A low-latency and reliable multihop D2D transmissions scheduling algorithm for guaranteed message dissemination

In critical alert services (e.g., a collision alert in a vehicular net-work) a message must reach all the recipients in a prespecified area within a maximum time, usually of few milliseconds, with guaranteed reliability. In this paper, we consider a Device-to-device (D2D)-enabled cellular network where User Equipments (UEs) use D2D transmissions to spread a message in their prox-imity, according to a centrally computed multihop schedule. Re-ception of D2D transmissions is probabilistic, with probabilities known a priori, e.g. based on the distance between two UEs. We want a given message to reach all the UEs in the network, within a maximum amount of time, with a pre-specified target proba-bility. We show that the problem of computing: a) the minimal set of UEs that should initially possess the message to be dissem-inated, and b) the schedule that achieves the above objectives, is integer-non-convex, hence too complex to be solved optimally, and we propose a polynomial heuristic based on iterative de-compositions, which always finds a feasible solution in negligible computation time. We analyze the performance of our scheme via simulation, showing that our centralized approach outper-forms distributed ones relying on node cooperation, is consider-ably faster and requires far fewer transmissions.