Radio networks are a long-studied model for distributed system of devices which communicate wirelessly. When these devices are mobile or have limited capabilities, the system is often best modeled by the ad-hoc variant, in which the devices do not know the structure of the network. A large body of work has been devoted to designing algorithms for the ad-hoc model, particularly for fundamental communications tasks such as broadcasting. Most of these algorithms, however, assume that devices have some network knowledge (usually bounds on the number of nodes in the network @math , and the diameter @math ), which may not always be realistic in systems with weak devices or gradual deployment. Very little is known about what can be done when this information is not available. This is the issue we address in this work, by presenting the first broadcasting algorithms for networks in which nodes have no prior knowledge whatsoever. We demonstrate that lack of parameter knowledge can be overcome at only a small increase in running time. Specifically, we show that in networks without collision detection, broadcast can be achieved in @math time, almost reaching the @math lower bound. We also give an algorithm for directed networks with collision detection, which requires only @math time.
All of these results also , and algorithms that do not require such knowledge have been little studied. The closest analogue in the literature is the work of Jurdzinski and Stachowiak @cite_11 , who give algorithms for wake-up in single-hop radio networks (those in which the underlying graph is a clique, i.e. @math ) under a wide range of node knowledge assumptions. Their Use-Factorial-Representation algorithm is the most relevant; the running time is given as @math for high-probability wake-up with a global clock (a slightly stronger task than broadcasting) in single-hop networks, but a similar analysis as we present here would demonstrate that the algorithm also performs broadcasting in multi-hop networks in @math time.
@cite_11
1990661532
The unstructured multi-hop radio network model, with asynchronous wake-up, no collision detection and little knowledge on the network topology, is proposed for capturing the particularly harsh characteristics of initially deployed wireless adhoc and sensor networks. In this paper, assuming such a practical model, we study a fundamental problem of both theoretical and practical interests--the local broadcasting problem. Given a set of nodes V where each node wants to broadcast a message to all its neighbors that are within a certain local broadcasting range R, the problem is to schedule all these requests in the fewest timeslots. By adopting the physical interference mode land without any knowledge on neighborhood, we give a new randomized distributed approximation algorithm for the local broadcasting problem with approximation ratio O (log n) where nis the number of nodes. This distributed approximation algorithm improves the state-of-the-art result in [22] by a logarithmic factor.