6.1 Introduction

Nodes should be grouped into clusters in a way that maintains maximum connectivity. Maximizing the stability and links connectivity as well as traffic intensities within each cluster leads to efficient clustering, routing, and overall communication efficiency. Minimizing the amount of clustering and routing information and numbers of intracluster links contributes also to overall communication efficiency.

Clustering helps also to manage the allocation of wireless channel resources, e.g., in the IEEE 802.11 Standard, the access point coordinates the transmission times of various nodes. Clustering leads also to formation of backbones and reduction of the state of the network. As an example, it is easier for cluster heads to exchange information in regard to 50 nodes in each cluster rather than allowing the 10,000 nodes of the whole wireless network to exchange information about the other 9,999 nodes. Clustering and subsequent formulation of backbone links of high quality and low delay may lead to overall end-to-end transmission delay in multihop networks.

Because of node movement, the establishment and maintaining of clusters in ad hoc wireless networks where there is no access point becomes a harder task compared to fixed nodes. More-frequent exchange of clustering information and routing tables may lead to less time available for information transmission and hence less communication efficiency. Added to this inefficiency is the nature of the wireless channel, which faces additive Gaussian noise, path loss due to shadowing and various obstacles, fading, sensitivity to distance, nodes transmission powers, etc.

In this chapter, some of the basic clustering techniques for wireless LANs and the various trade-offs involved are presented. While trying to explain the clustering/routing interrelationship, more details on the wireless LAN routing techniques may be found in Elhakeem ^[1] complementing the clustering techniques discussed herein. Other issues such as security and authentication are related but not investigated here.

^[1]Elhakeem, A.K., Ad-hoc routing techniques for wireless LANs, in The Communications Handbook, 2nd ed., Gibson, J.D., Ed., CRC Press, Boca Raton, FL, 2002, 92-1.