Efficient broadcasting in known topology radio networks with long-range interference
František Galčík, Leszek Antoni Gąsieniec, Andrzej Lingas · 2009
We study broadcasting (one-to-all communication) in known topology radio networks modeled by graphs, where the interference range of a node is likely to exceed its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge their transmissions disable recipience of one another. For a network G, we term the smallest integer d, s.t., for any interference edge e there exists a simple path formed of at most d transmission edges connecting the endpoints of e as its interference distance dI. In this model the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on limited number of transmissions at each node.