查看文章

We study the gossiping problem in directed ad-hoc radio networks. Our main result is a deterministic algorithm that solves this problem in an n-node network in time O(n ^4/3log⁴ n). The algorithm allows the labels (identifiers) of the nodes to be polynomially large in n, and is based on a novel way of using selective families. The previous best general (i.e., dependent only on n) deterministic upper bounds were O(n ^5/3log³ n) for networks with polynomially large node labels [1], and O(n ^3/2log² n) for networks with linearly large node labels [2,3,4].