An effective channel allocation algorithm to maximize system utility in heterogeneous DCB WLANs

Abstract

IEEE 802.11ac is a recent amendment that improves the system throughput to meet the rapidly growing data rate requirements of Wireless Local Area Networks (WLANs). One important technique adopted by 802.11ac is Dynamic Channel Bonding (DCB) that allows for the selection and combination of multiple contiguous basic channels in a single transmission. For a particular link, the adoption of wider bandwidth can offer it a higher data rate, while also makes it suffer from much severer competition with other links for wireless channel airtime occupation. Thus, there is a basic tradeoff between data rate and channel access opportunity for a link in DCB WLANs and it is then non-trivial to come up with an effective way to properly allocate the limited orthogonal basic channels to each WLAN and assign the corresponding primary channel. This paper attempts to explore the optimal channel allocation problem in a heterogeneous DCB network, in which all WLANs are operating under DCB while not all of them are within the carrier-sensing range (CSRange) of each other. In particular, we first introduce an analytical framework that uses Continuous Time Markov Chain (CTMC) model to analyze the throughput performance and present a CTMC construction algorithm to generate the Markov chain for any given heterogeneous DCB network. After that, we analyze the system utility under different channel allocation schemes and formulate an optimization problem with the target of maximizing the system utility, which is a concave and non-decreasing function of the achievable link throughputs. Due to the high complexity of the optimization problem, we design a heuristic and effective algorithm to find the near-optimal channel allocation that achieves good system utility for the heterogeneous DCB networks. Simulations validate that our proposed MIS-based channel allocation algorithm (MCAA) can achieve good performance in terms of both system utility and aggregate throughput under various network topologies and protocol parameter settings.

Introduction

Nowadays, the demand of Wireless Local Area Networks (WLANs) in terms of both coverage area and data rate keeps quickly increasing to meet the ever-growing mobile data traffic for various wireless applications. To provide high data-rate access, IEEE 802.11n amendment adopted the channel bonding (CB) technique [1], in which two basic 20MHz channels can be aggregated to obtain a 40MHz channel. Later, IEEE 802.11ac [2] further allowed a wireless user to combine multiple available basic channels, maximum up to eight channels, for obtaining higher data rate. Thanks to the CB technique, Gigabit WLAN has been enabled for emerging data-rate hungry wireless applications.

In CB-enabled WLANs, each node with a packet to transmit still contends for channel access on the primary channel according to the CSMA/CA protocol (i.e., 802.11-like mechanism) [2], while the contending node is allowed to dynamically select its transmission channels based on the instantaneous spectrum occupancy status just at the beginning of the transmission. Such a CB technique is referred to as Dynamic Channel Bonding (DCB) [3], [4], and we call a network that all WLANs within it are operating under DCB as a DCB network in this paper¹.

It is known that the adoption of a wider bandwidth can increase the data rate of single transmission. However, recall that the nodes in WLANs competes for channel airtime according to the CSMA/CA protocol [2], the CB technique also makes the channel contentions among the neighboring WLANs more complicated and competitive. In general, there is a basic tradeoff between the date rate and channel airtime occupation for each WLAN. As has been pointed out by [3], [5], the basic channel allocation and the selection of primary channels have important effects on the system performance. That is, different assignments of basic channels and the primary channel could lead to rather different system performances. Thus, it is desirable to figure out the optimal channel allocation for DCB networks and this paper makes such an attempt.

In the literature, there has much prior work that considered the performance analysis and channel allocation in WLANs with CB. Specifically, the network performance has been analyzed experimentally in [3], [4], [6], [7], [8], [9] and theoretically in [10], [11], [12], [13], [14], [15], [16]. Also, either distributed [17], [18], [19], [20], [21] or centralized [5], [11], [22] channel allocation schemes have been designed to improve the system performance. However, most prior studies did not investigate the heterogeneous DCB networks, in which the interactions and dependencies among WLANs are more complicated due to the heterogeneous network topology and the flexible DCB operation. By saying heterogeneous, we refer to a more practical network in which not all the WLANs can sense each other (i.e., the carrier sensing relationship is “non-all-inclusive”). In such a network different WLANs sense different subsets of the other WLANs and then have different channel competition experiences, the throughput analysis becomes intractable due to the heterogeneous behavior of WLANs.

This paper formulates an optimal channel allocation problem for heterogeneous DCB networks with the target of maximizing the system utility, which is a concave and non-decreasing function of the achievable throughput. To examine the system utility under different channel allocations, we first design a Continuous Time Markov Chain(CTMC) model to analyze the throughput performance, given a specific channel allocation (i.e., the number of basic channels each WLAN is allowed to use as well as its pre-determined primary channel). Based on the CTMC model, we then carefully analyze how different channel allocations affect its system performance and design a heuristic algorithm to generate the near-optimal channel allocation scheme. The main contributions of this paper are as follows:

• We formulate the optimal channel allocation problem for heterogeneous DCB networks. As a first step, we propose an analytical framework that uses CTMC model to capture the interactions and dependencies among WLANs under the DCB mode. Moreover, we design an algorithm for the CTMC construction that is applicable for any network topology under any channel allocation.

• We design a Maximal Independent Set-based (MIS-based) channel allocation algorithm (MCAA) to figure out the near-optimal channel allocation. The main procedure of MCAA is as follows: given the contention graph, we first find out all the MISs and assign appropriate basic channels to them; for the WLANs that are not within any MIS, we allocate the remaining basic channels with the objective of minimizing the number of the overlapped basic channels.

• Simulations validate the accuracy of our constructed CTMC model and show that the proposed MCAA could achieve near-optimal system utility under various network topologies and protocol parameter settings.

The remainder of the paper is organized as follows. Section 2 introduces related work. Section 3 presents the DCB operation defined by IEEE 802.11ac standard and then formulates the optimal channel allocation problem. Section 4 introduces the analytical framework and the designed algorithm for the CTMC construction. The proposed channel allocation algorithm, MCAA, is presented in Section 5 and Section 6 shows simulation results. Finally, Section 7 concludes the paper.