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 tradeoffs 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.

Additional Metadata
Keywords Deterministic, Directional antennae, Neighbor discovery, Randomized algorithms, Rotating, Sensor network
Journal Ad-Hoc and Sensor Wireless Networks
Du, J. (Jingzhe), Kranakis, E, Ponce, O.M. (Oscar Morales), & Rajsbaum, S. (Sergio). (2016). Neighbor discovery in a sensor network with directional antennae. Ad-Hoc and Sensor Wireless Networks, 30(3-4), 261–286.