Roberto Battiti
Abstract
In the Code Division Multiple Access (CDMA) framework, collisions that can occur in wireless networks are eliminated by assigning orthogonal codes to stations, a problem equivalent to that of coloring graphs associated to the physical network. In this paper we present new upper and lower bounds for two versions of the problem (hidden and primary collision avoidance – HP-CA – or hidden collision avoidance only – H-CA). In particular, optimal assignments for special topologies and heuristics for general topologies are proposed. The schemes show better average results with respect to existing alternatives. Furthermore, the gaps between the upper bound given by the heuristic solution, the lower bound obtained from the maximum-clique problem, and the optimal solution obtained by branch and bound are investigated in the different settings. A scaling law is then proposed to explain the relations between the number of codes needed in Euclidean networks with different station densities and connection distances. The substantial difference between the two versions HP-CA and H-CA of the problem is investigated by studying the probabilistic distribution of connections as a function of the distance, and the asymptotic size of the maximum cliques.
- 1 N. Abrahmson, The ALOHA system Another alternative for computer communications, in: Proc. of FJCC (1970) pp. 281-285.Google Scholar
- 2 R. Battiti and M. Protasi, Reactive local search for the maximum clique problem, Technical Report TR-95-052, ICSI, Berkeley, CA (1995).Google Scholar
- 3 M. Bellare, O. Goldreich and M. Sudan, Free bits, PCPs and nonapproximability. Toward tight results, in: Proc. 36th Ann. Symp. on Foundations of Computer Science (IEEE Computer Society, Los Alamitos, CA, 1995) pp. 422431. Google Scholar
- 4 A.A. Bertossi and M.A. Bonuccelli, Code assignment for hidden terminal interference avoidance in multihop packet radio networks, IEEE Transactions on Networking 3(4) (1995) 441449. Google Scholar
- 5 D. Br~laz, New methods to color the vertices of a graph, Communications of the ACM 22 (1979) 251256. Google Scholar
- 6 I. Chlamtac and S. Kutten, On broadcasting in radio networks Problem analysis and protocol design, IEEE Transactions on Communications (December 1985).Google Scholar
- 7 I. Chlamtac and S. Kutten, A spatial reuse TDMA/FDMA for mobile multi-hop radio networks, in: Proc. of IEEE INFOCOM (March 1985).Google Scholar
- 8 I. Chlamtac and S.S. Pinter, Distributed nodes organization algorithm for channel access in a multihop dynamic radio network, IEEE Transactions on Computers 36 (1987) 728737. Google Scholar
- 9 I. Cidon and M. Sidi, Distributed assignment algorithms for multihop packet radio networks, IEEE Transactions on Computers 38 (1989) 13531361. Google Scholar
- 10 D. Johnson and M. Trick (eds.), Cliques, Coloring, and Satisfiability:Second DIMACS Implementation Challenge,DIMACSSeriesin Discrete Mathematics and Theoretical Computer Science, in press.Google Scholar
- 11 L. Hu, Distributed code assignments for CDMA packet radio networks, IEEE Transactions on Networking 1(6) (1993) 668677. Google Scholar
- 12 S.M. Korman, The graph-coloring problem, in: Combinatorial Optimization,eds. N. Christophides, P. Toth and C. Sandi (Wiley, New York, 1979) pp. 211235.Google Scholar
- 13 M. Kubale and B. Jackowski, A generalized implicit enumeration algorithm for graph coloring, Communications of the ACM 28 (1985) 412418. Google Scholar
- 14 T. Makansi, Transmitted-oriented code assignment for multihop packet radio, IEEE Transactions on Communications 35 (1987) 13791382.Google ScholarCross Ref
- 15 A. Mehrotra and M.A. Trick, A column generation approach to graph coloring, Technical report series, Graduate School of Industrial Administration, Carnegie Mellon University (1995).Google Scholar
- 16 R. Nelson and L. Kleinrock, Spatial TDMA: a collision-free multihop channel access protocol, IEEE Transactions on Communications 33 (1985) 934944.Google Scholar
- 17 M.J. Post, A.S. Kershenbaum and P.E. Sarachik, Scheduling multihop CDMA networks in the presence of secondary conflicts, Algorithmica 4 (1989) 365394.Google Scholar
Index Terms
- Assigning codes in wireless networks: bounds and scaling properties
Recommendations
Contention in multi-hop wireless networks: model and fairness analysis
MSWiM '09: Proceedings of the 12th ACM international conference on Modeling, analysis and simulation of wireless and mobile systemsIn multi-hop wireless networks with Carrier Sense Multiple Access (CSMA), unfairness may arise due to a number of reasons. A majority of the existing work focuses on fairness issues due to hidden terminals and the impact on backoff mechanisms. This ...
Performance of multichannel wireless ad hoc networks
This paper addresses the design of Medium Access Control (MAC) protocols for wireless ad hoc networks that derive benefits from using multiple orthogonal channels for data transmission. Each node is assumed to have a single half-duplex transceiver that ...
High performance wireless switch protocol for IEEE 802.11 wireless networks
All mobile stations (STAs) in IEEE 802.11 infrastructure wireless local area networks (IWLAN) are coordinated by an access point (AP). Within the 2.4 GHz unlicensed industry, science, and medicine (ISM) band defined in the IEEE 802.11 2.4 GHz physical ...
Comments