Research Article
The Spinning Problem
@INPROCEEDINGS{10.4108/ICST.WIOPT2008.3216, author={Bogdan Munteanu and Richard Borie and Grzegorz Malewicz}, title={The Spinning Problem}, proceedings={1st Workshop on Wireless Multihop Communications in Networked Robotics}, publisher={IEEE}, proceedings_a={WMCNR}, year={2008}, month={8}, keywords={Application software Computer science Directional antennas Directive antennas Energy consumption Polynomials Spinning Transmitting antennas Wireless networks Wireless sensor networks}, doi={10.4108/ICST.WIOPT2008.3216} }- Bogdan Munteanu
Richard Borie
Grzegorz Malewicz
Year: 2008
The Spinning Problem
WMCNR
IEEE
DOI: 10.4108/ICST.WIOPT2008.3216
Abstract
Neighbor discovery in wireless networks with directional antennas is of crucial importance to many applications. In this paper we propose a variation of the classic neighbor discovery problem which we named the Spinning Problem. Here we are given an arbitrary number of devices on a plane. Each antenna starts spinning at a given rate and transmitting its location. The initial location and orientation are unknown. The goal is to find the rates that minimize the time for each device to find the location of every other device. We analyze a few particular cases of the problem. Specifically, we describe a polynomial time algorithm for 2 devices, and an exponential algorithm for n devices. It remains unknown whether there exists a polynomial time algorithm for an arbitrary number of antennas.