Search

We consider the problem of resource discovery in distributed systems. In particular we give an algorithm, such that each node in a network discovers the address of any other node in the network. We model the knowledge of the nodes as a virtual overlay network given by a directed graph such that complete knowledge of all nodes corresponds to a complete graph in the overlay network. Although there are several solutions for resource discovery, our solution is the first that achieves worst-case optimal work for each node, i.e. the number of addresses ( O ( n ) ) or bits ( O ( n log ⁡ n ) ) a node receives or sends coincides with the lower bound, while ensuring only a linear runtime ( O ( n ) ) on the number of rounds. [ABSTRACT FROM AUTHOR]

Abstract: We study the problem of greedy, single path data propagation in wireless sensor networks, aiming mainly to minimize the energy dissipation. In particular, we first mathematically analyze and experimentally evaluate the energy efficiency and latency of three characteristic protocols, each one selecting the next hop node with respect to a different criterion (minimum projection, minimum angle and minimum distance to the destination). Our analytic and simulation findings suggest that any single criterion does not simultaneously satisfy both energy efficiency and low latency. Towards parameterized energy–latency trade-offs we provide as well hybrid combinations of the two criteria (direction and proximity to the sink). Our hybrid protocols achieve significant performance gains and allow fine-tuning of desired performance. Also, they have nice energy balance properties, and can prolong the network lifetime. [Copyright &y& Elsevier]