Tradeoff between Energy-Efficiency and Timeliness of Neighbor Discovery in Self-Organizing Ad Hoc and Sensor Networks

Self-organizing ad hoc and sensor networks require the capability of nodes to discover other devices in their neighborhood. This operation must be performed rapidly and in a transparent way with respect to applications running in the network. Neighbor discovery consists of a set of procedures a node has to perform which involve the consumption of energy resources which are very scarce in most self-organizing ad hoc scenarios. In this paper an analytical framework based on Markov chains is introduced for the modeling of neighbor discovery. This framework allows us to evaluate the energy cost due to the hunting process and the probability that a timely discovery will occur. The above two performance measures clash with each other and thus an appropriate tradeoff is required. In this context, the proposed paradigm can be used for the performance evaluation and design of hunting processes.