SCHEDULING SENSORS BY TILING LATTICES
Abstract
Suppose that wirelessly communicating sensors are placed in a regular fashion on the points of a lattice. Common communication protocols allow the sensors to broadcast messages at arbitrary times, which can lead to problems should two sensors broadcast at the same time. It is shown that one can exploit a tiling of the lattice to derive a deterministic periodic schedule for the broadcast communication of sensors that is guaranteed to be collision-free. The proposed schedule is shown to be optimal in the number of time slots.
References
- IEEE Transactions on Computers 55(2), 214 (2006), DOI: 10.1109/TC.2006.47. ISI, Google Scholar
S. PalChaudhuri , A. K. Saha and D. B. Johnson , Adaptive clock synchronization in sensor networks, Proc. of the 3rd International Symposium on Information Processing in Sensor Networks (2004) pp. 340–348. Google Scholar- Ad-Hoc Networks 3(3), 281 (2005). Crossref, ISI, Google Scholar
-
J. Schiller , Mobile Communications , 2nd edn. ( Addison Wesley , 2003 ) . Google Scholar - S. T. McCormick. Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem. Technical report SOL 81-22, Department of Operations Research, Stanford University, 1981 . Google Scholar
E. L. Lloyd and S. Ramanathan , On the complexity of distance-2 coloring, Fourth Intl. Conf. on Computing and Information (1992) pp. 71–74. Google Scholar- IEEE J. Selected Areas in Communications 15(2), 250 (1997), DOI: 10.1109/49.552074. Crossref, ISI, Google Scholar
- Neural Netw. 18(5-6), 765 (2005), DOI: 10.1016/j.neunet.2005.06.013. Crossref, ISI, Google Scholar
- ACM SIGCOMM Computer Communication Review 22(4), 211 (1992), DOI: 10.1145/144191.144283. Crossref, Google Scholar
-
B. Grünbaum and G. C. Shephard , Tilings and Patterns ( W. H. Freeman and Company , 1987 ) . Google Scholar -
S. K. Stein and S. Szabó , Number 25 in The Carus Mathematical Monographs ,Algebra and Tiling – Homomorphism in the service of Geometry ( The Mathematical Association of America , 1994 ) . Google Scholar -
S. W. Golomb , Polyominoes , 2nd edn. ( Princeton University Press , Princeton, NJ , 1994 ) . Crossref, Google Scholar - Discrete Comput. Geom. 6(6), 575 (1991), DOI: 10.1007/BF02574705. Crossref, ISI, Google Scholar
- Inform. and Control 62(1), 1 (1984), DOI: 10.1016/S0019-9958(84)80007-8. Crossref, Google Scholar
- Theor. Inform. Appl. 41(2), 147 (2007), DOI: 10.1051/ita:2007012. Crossref, ISI, Google Scholar
M. Szegedy , Algorithms to tile the infinite grid with finite clusters, Proc. 39th Annual Symposium on Foundations of Computer Science (FOCS '98) (1998) pp. 137–147. Google ScholarF. Ellen , S. Subramanian and J. L. Welch , Maintaining information about nearby processors in a mobile environment, Proc. Intl. Conf. on Distributed Computing and Networking (ICDCN) (2006) pp. 193–202. Google Scholar-
S. Viqar and J. L. Welch , Deterministic collision-free communication despite continuous motion , Proc. 5th Intl. Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors) . Google Scholar


