Scheduling Forwarding Nodes for Two-Hop Neighborhoods Broadcast in Wireless Ad Hoc Networks
Chen-guang Xu, Minhong Lin, Yinlong Xu · 2015
Abstract:- This paper aims at scheduling the forwarding nodes in one-hop neighborhoods and making the two hop neighbors receive the message as soon as possible, which is modeled as the Minimum Time-Slot Forwarding (MTSF) problem. We prove that MTSF is NP-hard in general graph and propose two approximation algorithms. Theoretical analysis and simulation results show that the average time slot needed for broadcasting is a linear of ln|P|, where P is the set of two hop neighbors of source node s. We also compare the performance with that of flooding, and the simulation results show that both of them perform better than flooding.