Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimal Time Slot Assignment for Mobile Ad Hoc Networks

  • Conference paper
Distributed Computing – IWDC 2005 (IWDC 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3741))

Included in the following conference series:

  • 586 Accesses

Abstract

We present a new approach to find a collision-free transmission schedule for mobile ad hoc networks (MANETs) in a TDM environment. A hexagonal cellular structure is overlaid on the MANET and then the actual demand for the number of slots in each cell is found out. We assume a 2-cell buffering in which the interference among different mobile nodes do not extend beyond cells more than distance 2 apart. Based on the instantaneous cell demands, we propose optimal slot assignment schemes for both homogeneous (all cells have the same demand) and non-homogeneous cell demands by a clever reuse of the time slots, without causing any interference. The proposed algorithms exploit the hexagonal symmetry of the cells requiring O(log logm + mD + n) time, where m is the number of mobile nodes in the ad hoc network, n and D being the number of cells and diameter of the cellular graph.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ghosh, S.C., Sinha, B.P., Das, N.: Channel Assignment using Genetic Algorithm based on Geometry Symmetry. IEEE Trans. Vehi. Tech. 52, 860–875 (2003)

    Article  Google Scholar 

  2. Ghosh, S.C., Sinha, B.P., Das, N.: A New Approach to Efficient Channel Assignment for Hexagonal Cellular Networks. Int. J. Found. Comp. Sci. 14, 439–463 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  3. Ghosh, S.C., Sinha, B.P., Das, N.: Coalesced CAP: An Efficient Approach to Frequency Assignment in Cellular Mobile Networks. In: Proc. Int. Conf. Adv. Comp. Comm., India, December 2004, pp. 338–347 (2004)

    Google Scholar 

  4. Zangl, J., Hagenauer, J.: Large Ad Hoc Sensor Networks with Position Estimation. In: Proc. 10th Aachen Symp. Signal Theory, Aachen, Germany (2001)

    Google Scholar 

  5. Liao, W.-H., Tseng, Y.-C., Sheu, J.-P.: GRID: A Fully Location-aware Routing Protocol for Mobile Ad Hoc Networks. In: Telecom. Systems, vol. 18, pp. 37–60. Kluwer Acad. Pub., Dordrecht (2001)

    Google Scholar 

  6. Sinha, K., Srimani, P.K.: Broadcast Algorithms for Mobile Ad Hoc Networks based on Depth-first Traversal. In: Proc. Int. Workshop Wireless Inf. Sys., Portugal, April 2004, pp. 170–177 (2004)

    Google Scholar 

  7. Sinha, K., Srimani, P.K.: Broadcast and Gossiping Algorithms for Mobile Ad Hoc Networks based on Breadth-first Traversal. In: Sen, A., Das, N., Das, S.K., Sinha, B.P. (eds.) IWDC 2004. LNCS, vol. 3326, pp. 459–470. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  8. Tseng, Y.-C., Hsieh, T.-Y.: Fully Power-aware and Location-aware Protocols for Wireless Multi-hop Ad Hoc Networks. In: Proc. IEEE Int. Conf. Comp. Comm. Networks (2002)

    Google Scholar 

  9. Capkun, S., Hamdi, M., Hubaux, J.P.: GPS-free Positioning in Mobile Ad-hoc Networks. In: Proc. 34’th Hawaii Int. Conf. System Sciences (HICSS) (January 2001)

    Google Scholar 

  10. Basagni, S., Bruschi, D., Chlamtac, I.: A Mobility Transparent Deterministic Broadcast Mechanism for Ad Hoc Networks. IEEE Trans. Networking 7, 799–807 (1999)

    Article  Google Scholar 

  11. Nakano, K., Olariu, S.: Randomized Initialization Protocols for Ad-hoc Networks. IEEE Trans. Parallel and Distributed Systems 11, 749–759 (2000)

    Article  Google Scholar 

  12. Nakano, K., Olariu, S.: Uniform Leader Election Protocols for Radio Networks. IEEE Trans. on Parallel and Distributed Systems 13(5), 516–526 (2002)

    Article  Google Scholar 

  13. Perumal, K., Patro, R.K., Mohan, B.: Neighbor based TDMA slot Assignment Algorithm for WSN. In: Proc. IEEE INFOCOM (2005)

    Google Scholar 

  14. Pittel, B., Weishaar, R.: On-line Coloring of Sparse Random Graphs and Random Trees. J. on Algorithms, 195–205 (1997)

    Google Scholar 

  15. van Hoesel, L.F.W., Nieberg, T., Kip, H.J., Havinga, P.J.M.: Advantages of a TDMA based, Energy-efficient, Self-organizing MAC Protocol for WSNs. In: Proc. IEEE Vehi. Tech. Conf., Italy (2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Honeywell Technology Solutions Lab, Bangalore, 560076, India

    Koushik Sinha

Authors
  1. Koushik Sinha
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, West Bengal, India

    Ajit Pal

  2. Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, Illinois

    Ajay D. Kshemkalyani

  3. Computer Science and Engineering Department, Indian Institute of Technology, 721 302, Kharagpur, WB, India

    Rajeev Kumar

  4. Department of Computer Science and Engineering, Indian Institute of Technology, 721 302, Kharagpur, India

    Arobinda Gupta

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Sinha, K. (2005). Optimal Time Slot Assignment for Mobile Ad Hoc Networks. In: Pal, A., Kshemkalyani, A.D., Kumar, R., Gupta, A. (eds) Distributed Computing – IWDC 2005. IWDC 2005. Lecture Notes in Computer Science, vol 3741. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11603771_28

Download citation

  • DOI: https://doi.org/10.1007/11603771_28

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-30959-8

  • Online ISBN: 978-3-540-32428-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation