Abstract
We present several distributed CDMA/OVSF code assignment algorithms for wireless ad hoc networks modelled by unit disk graph (UDG). We first give a distributed code assignment whose total throughput is within a constant factor of the optimum. Then we give a distributed method such that the minimum rate achieved is within a constant factor of the optimum. A distributed method that can approximate both the minimum rate and total throughput is also presented. All our methods use only O(n) total messages (each with O(log n) bits) for an ad hoc wireless network of n nodes modelled by UDG.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cǎlinescu, G.: Computing 2-hop neighborhoods in ad hoc wireless networks (2003) AdHocNow
Chlamtac, I., Farago, A.: Making transmission schedules immune to topology changes in multi-hop packet radio networks. IEEE/ACM Transactions on Networking 2(1), 23–29 (1994)
Chlamtac, I., Kutten, S.: A spatial reuse TDMA/FDMA for mobile multihop radio nertworks. In: IEEE INFOCOM, pp. 389–394 (1985)
Garcia-Luna-Aceves, J., Raju, J.: Distributed assignment of codes for multihop packet-radio networks. In: IEEE MILCOM, vol. 1, pp. 450–454 (1997)
Goldberg, A., Rao, S.: Flows in undirected unit capacity networks. Tech. Rep. 97-103, NEC Research Institute, Inc. (1997)
Graf, A., Stumpf, M., Weisenfels, G.: On coloring unit disk graphs. Algorithmica 20(3), 277–293 (1998)
Hu, L.: Distributed code assignments for CDMA packet radio networks. IEEE/ACM Transactions on Networking 1, 668 (1993)
Krumke, S., Marathe, M., Ravi, S.: Models and approximation algorithms for channel assignment in radio networks. Wireless Networks 7, 567–574 (2001)
Li, X.-Y., Wang, Y.: Simple heuristics and PTASs for intersection graphs in wireless ad hoc networks. In: ACM DialM (workshop of ACM MobiCom) (2002)
McDiarmid, C., Reed, B.: Colouring proximity graphs in the plane. Discrete. Mathematics 199, 123–137 (1999)
Nelson, R., Kleinrock, L.: Spatial-TDMA: A collision-free multihop channel access protocol. IEEE Transactions on Communications 33(9), 934–944 (1985)
Ramanathan, S., Lloyd, E.: Scheduling algorithms for multi-hop radio networks. IEEE/ACM Transactions on Networking 1, 166–172 (1993)
Sen, A., Huson, M.L.: A new model for scheduling packet radio networks. ACM/Baltzer Journal Wireless Networks 3, 71–82 (1997)
Sen, A., Malesinska, E.: Approximation algorithms for radio network scheduling. In: Allerton Conf. on Comm., Contr. and Comp., pp. 573–582 (1997)
Stevens, D., Ammar, M.: Evaluation of slot allocation strategies for TDMA protocols in packet radio networks. In: IEEE MILCOM, pp. 835–839 (1990)
Wan, P.-J., Li, X.-Y., Frider, O.: OVSF-CDMA code assignment for wireless ad hoc networks. In: ACM DialM (workshop of ACM MobiCom) (2004)
Wang, Y., Li, X.-Y.: Geometric spanners for wireless ad hoc networks. In: Proc. of 22nd IEEE ICDCS (2002)
Li, X.-Y., Wan, P.-J., Song, W.-Z.: Theoretically Good Distributed CDMA/OVSF Code Assignment for Wireless Ad Hoc Networks. Tech Report, IIT (2004), http://www.cs.iit.edu/~xli/publications-select.htm
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, XY., Wan, PJ. (2005). Theoretically Good Distributed CDMA/OVSF Code Assignment for Wireless Ad Hoc Networks. In: Wang, L. (eds) Computing and Combinatorics. COCOON 2005. Lecture Notes in Computer Science, vol 3595. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11533719_15
Download citation
DOI: https://doi.org/10.1007/11533719_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28061-3
Online ISBN: 978-3-540-31806-4
eBook Packages: Computer ScienceComputer Science (R0)