On the scalability of IEEE 802.11 ad hoc networks

ABSTRACT

The IEEE 802.11 standards support the peer-to-peer mode Independent Basic Service Set (IBSS), which is an ad hoc network with all its stations within each other's transmission range. In an IBSS, it is important that all stations are synchronized to a common clock. Synchronization is necessary for frequency hopping spread spectrum (FHSS) to ensure that all stations "hop" at the same time; it is also necessary for both FHSS and direct sequence spread spectrum (DSSS) to perform power management. This paper evaluates the synchronization mechanism, which is a distributed algorithm, specified in the IEEE 802.11 standards. By both analysis and simulation, it is shown that when the number of stations in an IBSS is not very small, there is a non-negligible probability that stations may get out of synchronization. The more stations, the higher probability of asynchronism. Thus, the current IEEE 802.11's synchronization mechanism does not scale; it cannot support a large-scale ad hoc network. To alleviate the asynchronism problem, this paper proposes a simple modification to the current synchronization algorithm. The modified algorithm is shown to work well for large ad hoc networks.

REFERENCES

• 1: G. Bianchi. Performance analysis of the IEEE 802.11 distributed coordination function. IEEE Journal on Selected Areas in Communications, 18(3):535--547, 2000.
• 2: G. Bianchi, L. Fratta, and M. Oliveri. Performance evaluation and enhancement of the CSNA/CA MAC protocol for 802.11 wireless LANs. In Proc. PIMRC 1996, pages 392--396.
• 3: J. Elson, L Girod and D. Estrin. Fine-grained network time synchronization using reference broadcasts. Submitted for review, February 2002. http://lecs.cs.ucla.edu/Publications/Publications.html.
• 4: IEEE Std 802.11. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specification , 1999 edition edition.
• 5: IEEE Std 802.11b. Higher-Speed Physical Layer Extension in the 2.4 GHz Band, 1999 edition edition.
• 6: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 7: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 8: D. L. Mills. Internet time synchronization: the network time protocol. In Global States and Time in Distributed Systems. IEEE Computer Society Press, 1994.
• 9: K. Römer and E. Zurich. Time synchronization in ad hoc networks. In Proceedings of MobiHoc 2001.
• 10: Y. C. Tay , K. C. Chua, A capacity analysis for the IEEE 802.11 MAC protocol, Wireless Networks, v.7 n.2, p.159-171, March/April 2001 [doi>10.1023/A:1016637622896]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Performance

Keywords:
IEEE 802.11, ad hoc networks, clock synchronization, scalability