World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

SCHEDULING SENSORS BY TILING LATTICES

    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

    • Q. Li and D. Rus, IEEE Transactions on Computers 55(2), 214 (2006), DOI: 10.1109/TC.2006.47. ISIGoogle 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
    • B. Sundararaman, U. Buy and A. D. Kshemkalyani, Ad-Hoc Networks 3(3), 281 (2005). Crossref, ISIGoogle 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
    • G. Wang and N. Ansari, IEEE J. Selected Areas in Communications 15(2), 250 (1997), DOI: 10.1109/49.552074. Crossref, ISIGoogle Scholar
    • H. Shi and L. Wang, Neural Netw. 18(5-6), 765 (2005), DOI: 10.1016/j.neunet.2005.06.013. Crossref, ISIGoogle Scholar
    • S. Ramanathan and E. L. Lloyd, ACM SIGCOMM Computer Communication Review 22(4), 211 (1992), DOI: 10.1145/144191.144283. CrossrefGoogle 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 ) . CrossrefGoogle Scholar
    • D. Beauquier and M. Nivat, Discrete Comput. Geom. 6(6), 575 (1991), DOI: 10.1007/BF02574705. Crossref, ISIGoogle Scholar
    • H. A. G. Wijshoff and J. van Leeuwen, Inform. and Control 62(1), 1 (1984), DOI: 10.1016/S0019-9958(84)80007-8. CrossrefGoogle Scholar
    • I. Gambini and L. Vuillon, Theor. Inform. Appl. 41(2), 147 (2007), DOI: 10.1051/ita:2007012. Crossref, ISIGoogle 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 Scholar
    • F. 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