Neighbor Discovery in a Sensor Network with Directional Antennae
Jingzhe Du, Evangelos Kranakis, Oscar Morales Ponce and Sergio Rajsbaum
Consider a network of n directional antennae in the plane. We consider the problem of efficient neighbor discovery in a (synchronous) network of sensors employing directional antennae. In this setting sensors send messages and listen for messages by directing their antennae towards a specific direction (which is not necessarily known in advance). In our model the directional antennae can be rotated by the sensors as required so as to discover all neighbors in their vicinity. In this paper we will limit ourselves to the (D, D) communication profile whereby sensors employ directional antennae with identical transmission/reception beam widths. Our methodology is based on techniques for symmetry breaking so as to enable sender/receiver communication. We provide 1) deterministic algorithms that introduce delay in the rotation of the antennae and exploit knowledge of the existence of a vertex coloring of the network, and 2) randomized algorithms that require knowledge only of an upper bound on the size of the network so as to accomplish neighbor discovery. In both instances we study trade offs on the efficiency of the algorithms proposed. Through experimentation, we also show that the algorithms achieve desirable neighbor discovery delays and the randomized algorithms perform better in the simulation.
Keywords: Deterministic, randomized algorithms, neighbor discovery, rotating directional antennae, sensor network.