Large-scale access scheduling in wireless mesh networks using social centrality

• Distributed node cliques for cluster communications by social centrality metrics.
• Efficient channel access in each cluster by compact schedule based on Latin squares.
• Valid node and cluster access activation using an on-demand coloring algorithm.
• Fair radio and channel allocation to nodes and clusters in large scale WMNs.
• Coexistence of LaSoLaSo with traditional 802.11 DCF channel access mechanisms.

Wireless mesh networking is an economic and convenient way to provide last mile Internet access through ad hoc peer-to-peer communication links. However, without systematic network configuration and channel resource management, these networks suffer from scalability, performance degradation and service disruption issues due to overwhelming co-channel interference, unscrupulous channel utilization and inherent network mobility. The IEEE 802.11 DCF and EDCA mechanisms based on CSMA/CA are the most widely used random channel access mechanisms, but unfortunately these cannot effectively eliminate hidden terminal and exposed terminal problems in multi-hop scenarios. Social network analysis techniques proposed for economic and social studies have recently been shown to be a successful approach for characterizing information propagation in multi-hop wireless networks. We propose a set of efficient resource allocation algorithms and channel access scheduling protocols based on Latin squares and social centrality metrics for wireless mesh networks (WMNs) with multi-radio multi-channel (MRMC) communication capabilities, called LaSoLaSo, which can coexist with IEEE 802.11 DCF and be effectively applied in large scale WMNs. Based on interference information provided by the interference graph, LaSoLaSo uses nodal degree centrality to form cliques for intra-cluster communication, and betweenness centrality to choose bridge nodes to form cliques for inter-cluster communication in WMNs, and then applies Latin squares to map the clique-based clustering structure to radios and channels for wireless communication purposes. Afterwards, LaSoLaSo again applies Latin squares to schedule the channel access amongst nodes within each cluster in a collision-free manner. We evaluate LaSoLaSo using simulations, and results show that LaSoLaSo achieves much better performance than existing IEEE 802.11 standards and other multi-channel access control protocols.