Energy-Efficient User Association with Congestion Avoidance and Migration Constraint in Green WLANs

Abstract

Green wireless local area networks (WLANs) have captured the interests of academia and industry recently, because they save energy by scheduling an access point (AP) on/off according to traffic demands. However, it is very challenging to determine user association in a green WLAN while simultaneously considering several other factors, such as avoiding AP congestion and user migration constraints. Here, we study the energy-efficient user association with congestion avoidance and migration constraint (EACM). First, we formulate the EACM problem as an integer linear programming (ILP) model, to minimize APs’ overall energy consumption within a time interval while satisfying the following constraints: traffic demand, AP utilization threshold, and maximum number of demand node (DN) migrations allowed. Then, we propose an efficient migration-constrained user reassociation algorithm, consisting of two steps. The first step removes $k$ AP-DN associations to eliminate AP congestion and turn off as many idle APs as possible. The second step reassociates these $k$ DNs according to an energy efficiency strategy. Finally, we perform simulation experiments that validate our algorithm’s effectiveness and efficiency.

This work is licensed under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

1. Introduction

The IEEE 802.11-based wireless local area network (WLAN) is one of the most popular, widely used wireless access technologies in fog computing [1, 2]. WLANs are especially popular for campuses, enterprise environments, and public hotspots, serving a large number of users while satisfying their continuously growing traffic demands. Network operators usually deploy thousands of access points (APs) to achieve full coverage and provide enough capacity. Although each AP only consumes a little energy, the overall network’s energy consumption is significant due to the large-scale deployment. Escalating energy consumption increases greenhouse gas emissions and becomes a threat to environment protection and sustainable development. Moreover, it leads to higher energy costs, which is a critical component of network operational expenditures. Because the APs in a WLAN are overprovisioned with respect to peak traffic demands, but only handle peak traffic for small portions of time, energy is wasted when network traffic is low [3]. Thus, it is unnecessary to keep all resources active, which is why many researchers have pursued energy efficiency in the resource allocation and proposed many green scheduling strategies [4–6], and thus the concept of green WLANs is proposed [7–10]. In green WLANs, APs are scheduled on/off according to time-varying traffic demands, thereby saving energy.

User association is an important issue in WLAN research, and it aims to determine AP selection for each user and optimize APs’ resource allocation. Most existing studies focus on performance optimization—such as load balancing, user fairness, and user quality of service (QoS)—and they propose several user association approaches [11–18]. However, little attention has been paid to energy efficiency and the impact of different association solutions on saving energy [19]. Taking the case in Figure 1 as an example, a WLAN with three APs needs to serve six users in the current scenario, and we assume that each AP has the ability to serve three users. When each AP serves two users, respectively, no AP can be turned off. However, when we migrate the users associated with the middle AP to other APs, the middle AP can be turned off. Hence, some of the less-utilized APs can be turned off by adjusting user association, and this saves energy.

[figure omitted; refer to PDF]

Energy efficiency is a necessity for user association in green WLANs, and finding the right balance is challenging. On one hand, to turn off as many APs as possible, adjusting user association inevitably increases other APs’ load, and these other APs could become congested. Therefore, we must find the tradeoff between energy efficiency and congestion avoidance. On the other hand, because of time-varying traffic demands, user association should be adjusted dynamically with several user migrations. These migrations will negatively impact the corresponding users’ experience. Hence, we must reduce user migrations in the process of dynamic user association.

In this paper, we investigate the user association problem in green WLANs, to minimize the network’s energy consumption while satisfying time-varying traffic demands. Moreover, AP congestion avoidance and user migration constraints are both considered. The main contributions of this paper are as follows:

(i)

We investigate the energy-efficient user association with congestion avoidance and migration constraint (EACM) in green WLANs and formulate the EACM problem as an integer linear programming (ILP) model.

(ii)

We propose an efficient migration-constrained user reassociation algorithm (MURA), where $k$ AP-DN (DN stands for demand node) associations are removed to eliminate AP congestion and make as many APs as possible idle, and then the $k$ DNs are reassociated according to an energy efficiency strategy.

(iii)

We conduct simulation experiments to evaluate the performance of the proposed algorithm, and the results show its efficiency and effectiveness.

The rest of the paper is structured as follows. In Section 2, we discuss the related work. We then present the system model and problem formulation in Section 3. Next, we propose MURA, an efficient algorithm in Section 4. Section 5 evaluates MURA using simulations. Finally, Section 6 concludes the paper.

2. Related Work

User association optimization is of interest to many researchers, because it improves network performance significantly under current transmission technologies.

Over the years, several user association approaches have been proposed. Bejerano et al. [11] propose an efficient algorithm to determine the AP-user associations that achieve load balancing and max-min fair bandwidth allocation, that is, maximizing the minimum user throughput. Li et al. [12] investigate the problem of optimizing AP-user association to achieve proportional fairness in multirate WLANs and present a centralized algorithm to derive the AP-user association. To handle the case of dynamic user membership, a distributed heuristic is proposed to provide an AP selection criterion for newcomers.

Gong et al. [13] study the user association problem for 802.11n WLANs with heterogeneous clients (802.11a/b/g/n) and present solutions whereby each user achieves the throughput proportional to its usable data rate. Yu et al. [14] investigate the problem of optimal user association in wireless mesh networks, considering max-min fairness, proportional fairness, and link interference. The problem is formulated as two-step mixed ILP models, and then two rounding algorithms and their corresponding approximation ratio improvement algorithms are proposed to address the problem.

Wong et al. [15] consider the cost of user migration in the process of user reassociation and propose an efficient approximation algorithm to achieve max-min fairness, while satisfying a certain total user migration cost constraint. Raschellà et al. [16] present a centralized network management framework for user association based on software-defined networking (SDN), where an AP section metric jointly considers the QoS requirements of a user joining the network, the bandwidth efficiency, and the QoS requirements of other users active in the networks.

Chen et al. [17] explore the user association problem in SDN WLANs with some new features, such as centralized association, global network state awareness, seamless handoff, and flow-level association. The problem is formulated as a delay-minimized optimization problem to minimize the interpacket delay of individual flows, and the greedy algorithm and bounded local search algorithm are proposed to solve the problem. Kim et al. [18] consider the link interference and AP load and design a user association mechanism that is based on metrics derived by signal strength variance and a beacon collision rate.

However, all the aforementioned works only take into consideration network performance, which does not translate well when applied in green WLANs. In green WLANs, there is an energy-saving mechanism that dynamically turns APs on/off to adapt to users’ resource demands [7]. Related to green WLANs, there are only a few recent works on user association. These works focus on improving energy efficiency by optimizing user association.

Kumazoe et al. [19] propose a user reassociation scheme where an AP migrates its associated users to another AP and then switches its status to sleep when the AP finds that its utilization is lower than the predefined threshold. Wang et al. [20] consider user association in a heterogeneous network with hybrid energy supplies, where energy saving is subject to the constraints of a user data rate requirement, transmission power budget, and so forth. They formulate the energy cost saving optimization problem and present both centralized and distributed solutions.

Chen et al. [21] propose an AP energy-saving mechanism using SDN, aiming to reduce the amount of idle APs while satisfying QoS requirements. In the mechanism, the user association problem is formulated as an ILP model. Lee et al. [22] present a centralized management mechanism to improve energy efficiency and avoid interference without sacrificing users demands, and jointly optimize the AP on/off scheduling, channel assignment, and user association.

As discussed above, several energy-efficient user association solutions have been proposed in the past. However, to the best of our knowledge, no prior work exists that deals with the issues of AP congestion and user migration in the context of energy-saving optimization in WLANs. Hence, here we study the user association problem in green WLANs, which aims to achieve energy efficiency with AP congestion avoidance and user migration constraints.

3. System Model and Problem Formulation

3.1. System Model

Our IEEE 802.11-based multirate WLAN consists of multiple APs. The set of APs is denoted by $A$, and we use $m$ to denote their number, i.e., $A=\{a_{\mathrm{1}},a_{\mathrm{2}},\dots ,a_m\}$. Because users are on the go and their traffic demands are dynamic in WLANs, we represent the distribution of user traffic demands by discrete points (that is DNs) that are the center of an area aggregating the traffic demands of several users [23]. Thus, AP-user associations can be represented by AP-DN associations. We use $U$ to denote the set of DNs, and the number of DNs is represented by $n$—that is, $U=\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n\}$. As shown in Figure 2, the AP-DN associations can be modeled as a directed graph $G(A\cup U,E)$, where $E$ is the set of potential association relations between DNs and APs.

[figure omitted; refer to PDF]

Because multimedia content and downloads of mobile applications dominate the traffic demand, downlink traffic is much larger than uplink traffic, and thus we focus on downlink traffic (from the APs to DNs). For a DN $u_j\in U$, we assume that its traffic demand is a constant for a certain time interval $T$, and the constant is denoted by $r_j$.

We assume that neighboring APs do not interfere with each other through allocating nonoverlapping channels. For the transmission between $a_i\in A$ and $u_j\in U$, its available transmission rate is denoted by $c_{ij}$. We exploit the PHY multirate capability and enable each device to select the best transmission rate according to the received signal noise ratio (SNR), which we obtain by $$\begin{array}{}\text{(1)}& SN{R}_{ij}=p_i-PL\left(d_{ij}\right)-N\end{array}$$where $SN{R}_{i,j}$ represents the SNR of signals that are transmitted from AP $a_i$ and received at DN $u_j$; $p_i$ is the transmit power of AP $a_i$; $d_{ij}$ is the distance between AP $a_i$ and DN $u_j$, and $PL(d_{ij})$ denotes the propagation path loss; $N$ is the background noise power.

To characterize energy consumption of APs correctly, we use a fine-grained power model where we ascribe the power consumed by AP $a_i$ to the following two elements [24, 25]:

(i)

The baseline power (denoted by $b_i$) is a constant, which quantifies power consumption when the AP neither sends nor receives traffic after it is powered on.

(ii)

The traffic-related power, a variable part, is generated by the wireless interface and relevant components. Because we only consider downlink traffic in this paper, the traffic-related power pertains to AP transmitting wireless signals, and thus it positively correlates with AP transmit power and AP utilization. AP utilization is defined by the fraction of time during which the AP transmits traffic.

For $a_i\in A$, we define AP power as follows: $$\begin{array}{}\text{(2)}& P_i=b_i+{\eta }_i{p}_i{\displaystyle \sum }_{j\in U\left(a_i\right)}\frac{r_j}{c_{ij}}\end{array}$$where the power of AP $a_i$ is denoted by $P_i$, $U(a_i)$ represents the set of DNs that are associated with AP $a_i$, and ${\eta }_i$ is an efficiency factor that accounts for the AP’s electrical model.

The notations and their definitions are summarized in Table 1.

Table 1

Notations.

Symbol	Definition
$A$	The set of access points (APs)
$U$	The set of demand nodes (DNs)
$E$	The set of potential association relations
$m$	The number of APs
$n$	The number of DNs
$a_i$	An AP
$u_j$	Am DN
$r_j$	The traffic demand of DN $u_j$
$T$	Time interval
$c_{ij}$	The available transmission rate between AP $a_i$ and DN $u_j$
$SN{R}_{ij}$	The received SNR at DN $u_j$ when signal is from AP $a_j$
$P_i$	The power of AP $a_i$
$b_i$	The baseline power of AP $a_i$
$p_i$	The transmit power of AP $a_i$
${\eta }_i$	The efficiency factor of AP $a_i$
$d_{ij}$	The distance between AP $a_i$ and DN $u_j$
$PL(d_{ij})$	The propagation path loss
$N$	The background noise power
$U(a_i)$	The set of DNs that are associated with AP $a_i$
${\beta }_{ij}$	The coverage indicator between AP $a_i$ and DN $u_j$
$\phi$	The threshold of AP utilization
$\alpha (j)$	The previous association indicator
$k$	The maximum allowed number of migrations

3.2. Problem Formulation

In this section, we formulate the energy-efficient user association as an optimization problem based on an ILP model. Specifically, we not only consider energy optimization in the context of user association, but also take AP congestion avoidance and user migration constraints into account. We therefore define the problem as follows.

Definition 1 (EACM).

Given the network $G(A\cup U,E)$, the current traffic demands of DNs (i.e.,$\{r_j\mid u_j\in U\})$, and the previous AP-DN associations, the problem is to minimize the overall energy consumption of the APs in the current time interval through optimizing the AP-DN associations; while the traffic demands of the DNs are satisfied, the utilization of each AP is limited by a threshold, and DN migrations are also constrained.

To formulate the ILP model, we define the following sets of binary variables:

(i)

$x_i$, which is set to 1 if AP $a_i$ is turned on, or 0 otherwise.

(ii)

$y_{i,j}$, which is set to 1 if DN $u_j$ is associated with AP $a_i$, or 0 otherwise.

For each $a_i\in A$ and $u_j\in U$, we also define a coverage indicator to denote whether DN $u_j$ is in the coverage range of AP $a_i$; that is, $$\begin{array}{}\text{(3)}& {\beta }_{i,j}=\left\{\begin{array}{cc}1\hfill & c_{i,j}>\mathrm{0}\hfill \\ 0\hfill & c_{i,j}=\mathrm{0}.\hfill \end{array}\right.\end{array}$$

In addition, let $\alpha (j)$ be the previous association indicator that represents the AP-DN association in the previous time interval for DN $u_j$.

The objective is to minimize the overall energy consumption of the APs in the current time interval, as described by$$\begin{array}{}\text{(4)}& \min T{\displaystyle \sum }_{i\in A}\left(b_i{x}_i+{\eta }_i{p}_i{\displaystyle \sum }_{j\in U}\frac{r_j{y}_{ij}}{c_{ij}}\right).\end{array}$$

The minimization is subject to the following constraints:$$\begin{array}{}\text{(5)}& y_{ij}\le {\beta }_{ij}{x}_i\hspace{1em}\forall i\in A,\hspace{0.17em}\hspace{0.17em}j\in U\text{(6)}& {\displaystyle \sum }_{i\in A}{y}_{ij}=\mathrm{1}\hspace{1em}\forall j\in U\text{(7)}& {\displaystyle \sum }_{j\in U_i}\frac{r_j{y}_{ij}}{c_{ij}}\le \phi x_i\hspace{1em}\forall i\in A\text{(8)}& {\displaystyle \sum }_{j\in U}{y}_{\alpha \left(j\right)j}\ge n-k\text{(9)}& x_i\in \left\{\mathrm{0,1}\right\}\hspace{1em}\forall i\in A\text{(10)}& y_{ij}\in \left\{\mathrm{0,1}\right\}\hspace{1em}\forall i\in A,\hspace{0.17em}\hspace{0.17em}j\in U.\end{array}$$

In the aforementioned formulation, the constraint (5) states that no DN is associated with powered-off APs and an AP does not provide services for DNs beyond its coverage range. The constraint (6) imposes that each DN must be associated with an AP only. The constraint (7) ensures that each AP can satisfy the traffic demands of its associated DNs, and its AP utilization is limited by the coefficient $\phi$. The constraint (8) denotes the allowed maximum number of migrations that cannot be exceeded. Finally, the constraints (9) and (10) define the binary of the variables.

The EACM problem is NP-hard, because it includes as a special case the set-covering problem, known to be NP-hard [26]. Although the schemes that solve the ILP model directly can find the optimal solution or at least bound it, they are impractical for a relatively large-scale scenario, because of computational complexity and memory limitations [27]. Thus, the better alternative here is to design a heuristic algorithm to solve the EACM problem efficiently.

4. MURA

In this section, we propose MURA, our efficient two-step algorithm to solve the EACM problem. The basic idea is to migrate at most $k$ DNs from their original APs to neighboring APs, while considering energy saving and congestion avoidance. We solve this in two steps. In Step 1, we select $k$ DNs that are associated with heavily loaded or idle APs and remove them from the current associations. In Step 2, we reassociate the removed DNs according to the energy efficiency strategy.

4.1. Step 1: DN Removal

In this step, we need to determine which $k$ DNs to remove from the current associations. As described in Algorithm 1, we first initialize the set of APs that are turned on ($A\_on$), the utilization of each AP ($P\_Util$), the number of associated DNs for each AP ($AP\_UNum$), the set of current AP-DN associations ($UA\_fxd$), the set of removed DNs ($U\_rmv$), and the required number of DN removals ($rm\_cnt$). Then, we remove DNs from the current associations, successively considering AP congestion avoidance and energy saving. Specifically, we divide the process of DN removal into two parts. In the first part (lines $(7)$ to $(23)$), we iteratively remove DNs to address the issue of AP congestion. In each iteration, we find the AP with the maximum utilization and select a DN migrating from it if its utilization exceeds the threshold $\phi$. The DN selection strategy is to make AP utilization lower than the threshold or nearer to the threshold. In the second part (lines $(24)$ to $(32)$), we remove DNs so as to turn off as many APs as possible for energy saving. In each iteration, we find the AP with the minimum number of associated DNs, remove these DNs, and turn off the APs. The step stops when the total number of removed DNs reaches $k$ and returns $UA\_fxd$ and $U\_rmv$.

Algorithm 1: DN removal.

Input:   $A$ , $U$, $E$, $UA\_pre\hspace{0.17em}\hspace{0.17em}k$, $\phi$, $\{r_j\mid u_j\in U\}$,

$\{c_{ij}\mid a_i\in A,u_j\in U\}$

Output:   $UA\_fxd$ , $U\_rmv$

$(1)$ Initialize $A\_on$ // Set of APs that are

turned on

$(2)$ Initialize $AP\_Util$ // AP utilization

$(3)$ Initialize $AP\_UNum$ // Number of associated

DNs for each AP

$(4)$ $UA\_fxd\leftarrow UA\_pre$ // Set of fixed AP-DN

associations

$(5)$ $U\_rmv\leftarrow \varnothing$

$(6)$ $rm\_cnt\leftarrow k$ // Limitation of DN removal

$(7)$ while  true  do

$(8)$ $a_q\leftarrow \mathrm{a}\mathrm{r}\mathrm{g}{\hspace{0.17em}\mathrm{m}\mathrm{a}\mathrm{x}}_{a_i\in A}AP\_Util(a_i)$

// Find the AP with the maximum

utilization

$(9)$ if   $AP\_Util(a_q)>\phi$   then

$(10)$ if  $rm\_cnt=\mathrm{0}$  then

$(11)$ return   null,  null  //  Failure of AP

congestion avoidance

$(12)$ else

$(13)$ $U\_a\leftarrow \{u\mid (a_q,u_j)\in UA\_fxd,\forall u_j\in U\}$

$(14)$ Select a proper DN $u_p$ from $U\_a$

$(15)$ Remove $(a_q,u_p)$ from $UA\_fxd$

$(16)$ $U\_rmv\leftarrow U\_rmv\cup \{u_p\}$

$(17)$ Update $AP\_Util(a_q)$, $AP\_UNum(a_q)$

$(18)$ $rm\_cnt=rm\_cnt-\mathrm{1}$

$(19)$ else

$(20)$ if   $rm\_cnt=\mathrm{0}$   then return  $UA\_fxd$, $U\_rmv$

$$(21)$$

$(22)$ else  break

$$(23)$$

$(24)$ while   true   do

$(25)$ $a\_q\leftarrow \mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}{\mathrm{m}\mathrm{i}\mathrm{n}}_{a_i\in A\_on}AP\_UNum(a_i)$

$(26)$ $U\_a\leftarrow \{u_j\mid (a_q,u_j)\in UA\_fxd,\forall u_j\in U\}$

$(27)$ foreach   $u_j\in U\_a$   do

$(28)$ Remove $(a_q,u_j)$ from $UA\_fxd$

$(29)$ $rm\_cnt=rm\_cnt-\mathrm{1}$

$(30)$ if   $rm\_cnt=\mathrm{0}$   then return   $UA\_fxd$ , $U\_rmv$

$$(31)$$

$(32)$ $A\_on=A\_on\setminus \{a_q\}$ // Turn off as many

APs as possible

4.2. Step 2: DN Reassociation

As DNs in set $U\_rmv$ are removed from the current associations, we need to reassociate them in this step. As described in Algorithm 2, first we initialize the set of APs turned on ($A\_on$), the utilization of each AP ($AP\_Util$), and the set of current AP-DN associations ($UA$). Then, we determine the new reassociations of these DNs in sequence and prioritize the DN with greater traffic demand. For each DN, we choose an AP with the lowest increment of network energy consumption and assign the new association. The increment of network energy consumption is the additional energy consumption caused by the AP-DN association. If the AP is not active, it should be turned on first, and its baseline power should be involved in the increment of network energy consumption. After each reassociation, the set $U\_rmv$ and $AP\_Util$ are updated.

Algorithm 2: DN reassociation.

Input:  $A$, $U$, $E$, $U\_rmv$, $UA\_fxd$, $\phi$, $\{r_j\mid u_j\in U\}$,

$\{c_{ij}\mid a_i\in A,u_j\in U\}$ , $\{b_i,p_i,{\eta }_i\mid a_i\in A\}$

Output:  $UA$

$(1)$ Initialize $A\_on$ // Set of APs that are

turned on

$(2)$ Initialize $AP\_Util$ // AP utilization

$(3)$ $UA\leftarrow UA\_fxd$ // Set of AP-DN

associations

$(4)$ Sort $U\_rmv$ in descending order by traffic demand

$(5)$ while  $U\_rmv\ne \varnothing$  do

$(6)$ obtain DN $u_p$ from $U\_rmv$ in sequence

$(7)$ $a\_weight(i)\leftarrow \infty \hspace{0.17em}\hspace{0.17em}\forall a_i\in A$

$(8)$ if  $AP\_Util(a_i)+r_p/c_{ip}\le \phi$  then

$(9)$ if  $a_i\in A\_on$  then

$(10)$ $a\_weight(i)\leftarrow {\eta }_i{p}_i{r}_p/c_{ip}$ // increment of

energy consumption

$(11)$ else

$(12)$ $a\_weight(i)\leftarrow b_i+{\eta }_i{p}_i{r}_p/c_{ip}$

$(13)$ $a_q\leftarrow \mathrm{a}\mathrm{r}\mathrm{g}{\hspace{0.17em}\mathrm{m}\mathrm{i}\mathrm{n}}_{a_i\in A}a\_weight(i)$

$(14)$ if  $a\_weight(q)\ne \infty$  then

$(15)$ if  $a_q\notin A\_on$  then

$(16)$ $A\_on\leftarrow A\_on\cup \{a_q\}$

$(17)$ $UA\leftarrow UA\cup \{(a_q,u_p)\}$

$(18)$ $U\_rmv\leftarrow U\_rmv\setminus \{u_p\}$

$(19)$ Update $AP\_Util(a_q)$

$(20)$ else

$(21)$ return  null // Reassociation failed

$(22)$ return $UA$

4.3. Time Complexity

In the following, we analyze the time complexity of the MURA algorithm. This includes the two steps for DN removal and DN reassociation.

In the first step, the algorithm is initialized in O($mn$), and DN removal iterates at most $k$ times. For each iteration (lines $(8)$ to $(23)$ or lines $(25)$ to $(32)$), the time complexity is O($m+n+|U\_a|$). Because $m<n$ and $|U\_a|<n$, the time complexity of this step is O($(m+k)n$).

In the second step, again the initialization completes within O($mn$), and the sorting of $U\_rmv$ can be accomplished in O($k\hspace{0.17em}\mathrm{l}\mathrm{g}\hspace{0.17em}k$). DN reassociation iterates at most $k$ times. For each iteration (lines $(5)$ to $(20)$), the time complexity is O($m$). Because $k<n$, the time complexity of this step is O($mn+k\hspace{0.17em}\mathrm{l}\mathrm{g}\hspace{0.17em}k$).

Therefore, as discussed, the time complexity of the MURA algorithm is O($(m+k)n$).

5. Simulation Evaluation

In this section, we evaluate the performance of the proposed MURA algorithm via simulations and compare its solutions with the solutions of the ILP-based association scheme and the solutions of the received signal strength indication- (RSSI-) based association scheme. First, we validate the MURA algorithm’s effectiveness in terms of energy consumption and execution time. Then, we evaluate how the performance of the MURA algorithm is affected by the AP utilization threshold, number of allowed migrations, AP types, and traffic patterns.

5.1. Performance Metrics

We are interested primarily in energy consumption and execution time as performance metrics. Here, energy consumption is the overall energy consumption of all APs in a time interval. By execution time, we mean the algorithm’s execution time within a time interval. In addition, we compare MURA to the following schemes:

(i)

ILP-based association scheme: in this scheme, our EACM model is solved by an ILP solver, such as Gurobi.

(ii)

RSSI-based association scheme: in this scheme, each DN is associated with the AP that offers the best signal strength.

5.2. Simulation Setup and Parameters

In the simulation, we consider small-scale scenarios, medium-scale scenarios, and large-scale scenarios, respectively. As shown in Table 2, the network field is divided by grids, and APs are deployed at the center of grids to provide full coverage to the field. In addition, the same number of DNs are randomly placed in each grid.

Table 2

Network scenarios.

Network size	Number of APs	Number of DNs
Small ($\mathrm{100}\times \mathrm{100}{m}^{\mathrm{2}}$)	4	20
Medium ($\mathrm{250}\times \mathrm{250}{m}^{\mathrm{2}}$)	25	125
Large ($\mathrm{1000}\times \mathrm{1000}{m}^{\mathrm{2}}$)	400	2000

To characterize the indoor environment, we define the path loss calculation as follows [28]: $$\begin{array}{}\text{(11)}& PL\left(d_{ij}\right)=\mathrm{40}+\mathrm{10}\times \mathrm{3.3}\hspace{0.17em}\mathrm{l}\mathrm{g}\hspace{0.17em}{d}_{ij}.\end{array}$$

After the transmit power of AP is set to be 20 dBm (i.e., 0.1 W) and the background noise level is set to −93 dBm, we can compute the SNR of DNs. In this paper, we consider an IEEE 802.11n WLAN with 40 MHz channel, and we list the corresponding link rates in Table 3 [29, 30].

Table 3

SNR and link rates.

SNR range(dB)	Link rate (Mbps)
$\left[\mathrm{5,8}\right)$	15
$\left[\mathrm{8,12}\right)$	30
$\left[\mathrm{12,14}\right)$	45
$\left[\mathrm{14,18}\right)$	60
$\left[\mathrm{18,21}\right)$	90
$\left[\mathrm{21,23}\right)$	120
$\left[\mathrm{23,28}\right)$	135
$\left[\mathrm{28},\infty \right)$	150

We take the traffic pattern shown in Table 4, where the time duration is three hours, and assign a probability $pro{b}_t$ of DNs requesting demands in each interval $t$ [31]. Moreover, we use two different traffic demand profiles:

(i)

Standard mode, where each DN’s traffic demands randomly are generated in intervals of 1 to 10 Mbps.

(ii)

Busy mode, where each DN’s traffic demand varies between 8 and 10 Mbps.

Table 4

Traffic pattern.

Index $t$	Starting	Ending	Duration(h)	$pro{b}_t$
1	0	3	3	0.35
2	3	6	3	0.1
3	6	9	3	0.45
4	9	12	3	1
5	12	15	3	0.7
6	15	18	3	0.85
7	18	21	3	0.6
8	21	24	3	0.5

For each setting, we execute these schemes 20 times with different scenarios and use the average results as the final results. We conduct the simulation experiments on a PC equipped with an Intel Core i7 3.40 GHz processor, 8 GB RAM, Microsoft Windows 7, and MATLAB environment, where the proposed ILP model is solved by Gurobi.

5.3. Verification of Energy Efficiency

We compare the solutions obtained from the MURA algorithm with those obtained from the ILP-based association scheme and the RSSI-based association scheme. For the AP power model, we set the baseline power ($b_i$) to be 9 W and the efficiency factor (${\eta }_i$) to be 30. For the traffic pattern, we adopt the standard mode. We set the AP utilization threshold ($\phi$) to be 0.8 and the maximum allowed number of migrations ($k$) to be 30 percent of the DN amount. We perform the simulations for small-scale, medium-scale, and large-scale scenarios, respectively.

Figure 3 shows the performance of the MURA algorithm, the ILP-based association scheme, and the RSSI-based association scheme. From this figure, we can see that the MURA algorithm achieves significant energy savings comparing to the RSSI-based association scheme. Also, there is only a small gap in performance between our solution and the optimal solutions obtained by the ILP-based association scheme, which validates the near optimality of our algorithm. When the network scenarios become large, the ILP model cannot be solved by Gurobi directly, but our algorithm provides solutions within an acceptable time, as shown in Table 5. Moreover, the curves of our algorithm in Figure 3 show that an interval’s energy consumption is proportional to the traffic demand, and energy consumption greatly diminishes when traffic demand is low.

Table 5

Execution Time.

Time intervals	Execution time (Sec.)
	Small scenarios			Medium scenarios			Large scenarios
	MURA	ILP-based	RSSI-based	MURA	ILP-based	RSSI-based	MURA	ILP-based	RSSI-based
1	0.0013	0.0086	0.0005	0.0057	0.4928	0.0017	0.2718	-	0.0176
2	0.0004	0.0068	0.0002	0.0015	0.0235	0.0009	0.0524	-	0.0127
3	0.0008	0.0099	0.0003	0.0051	0.7347	0.0013	0.3151	-	0.0193
4	0.0008	0.0124	0.0003	0.0052	0.5227	0.0016	0.4825	-	0.0306
5	0.0007	0.0120	0.0004	0.0042	3.8941	0.0014	0.2137	-	0.0239
6	0.0008	0.0137	0.0003	0.0051	6.8822	0.0015	0.4613	-	0.0276
7	0.0007	0.0128	0.0003	0.0043	2.6668	0.0013	0.2814	-	0.0219
8	0.0008	0.0122	0.0003	0.0045	1.0751	0.0012	0.3111	-	0.0202

[figures omitted; refer to PDF]

5.4. Varying the Maximum Allowed Number of Migrations

Here, we evaluate the performance of the MURA algorithm, while varying the maximum allowed number of migrations (the parameter $k$). We perform simulations on large-scale scenarios and set the AP utilization threshold ($\phi$) to be 0.8. For the AP power model, we again set the baseline power ($b_i$) to be 9 W and the efficiency factor (${\eta }_i$) to be 30. For the traffic pattern, we adopt the standard mode. We set the maximum allowed number of migrations ($k$) to be 50, $100,\hspace{0.17em}\dots$, and 550.

Figures 4 and 5 show the results. From the two figures, we can see that energy consumption decreases as the maximum allowed number of migrations relaxes, because we can further optimize energy consumption through more DN migrations. We also find that the decrement of energy consumption is extremely limited once the parameter $k$ has reached 350. This substantiates why we set 350 as the maximum number of migrations allowed.

[figure omitted; refer to PDF] [figure omitted; refer to PDF]

5.5. Varying the AP Utilization Threshold

Next, we evaluate the MURA algorithm’s performance while varying the AP utilization threshold (the parameter $\phi$). In performing simulations on large-scale scenarios, we set the maximum allowed number of migrations ($k$) to be 350. For the AP power model, we set the baseline power ($b_i$) to be 9 W and the efficiency factor (${\eta }_i$) to be 30. For the traffic pattern, we adopt the standard mode. We set the AP utilization threshold to be 0.7, $0.75,\dots$, and 1.0.

Figures 6 and 7 show the results. We can see that energy consumption decreases as the AP utilization threshold relaxes, because each AP is able to serve more DN migrations and thus we can turn off more APs. Hence, $\phi$ is an adjustable parameter that can provide a tradeoff between energy efficiency and congestion avoidance.

[figure omitted; refer to PDF] [figure omitted; refer to PDF]

5.6. Impacts of AP Types

Now, we evaluate the MURA algorithm’s performance while varying AP types. We perform simulations on large-scale scenarios, setting the AP utilization threshold to be 0.8 and the maximum allowed number of migrations ($k$) to be 350. For the traffic pattern, we adopt the standard mode. Table 6 shows parameter settings of the AP power model [25].

Table 6

Parameters of the AP power model.

Type ID	Baseline power ($b_i$)	Efficiency factor (${\eta }_i$)
1	9	30
2	7	50
3	6	60
4	3	90

As shown in Figure 8, no matter which APs we use, our algorithm’s solutions perform better on energy consumption than the RSSI-based association scheme does. In addition, type 1 APs show greater energy savings, because any baseline power that can be eliminated by turning off APs plays a decisive role in AP power.

[figure omitted; refer to PDF]

5.7. Impacts of Traffic Pattern

Here, we evaluate the performance of the MURA algorithm under different traffic patterns, such as standard mode and busy mode. We perform simulations on large-scale scenarios, set the AP utilization threshold to be 0.8, and set the maximum allowed number of migrations ($k$) to be 350. For the AP power model, we set the baseline power ($b_i$) to be 9 W and the efficiency factor (${\eta }_i$) to be 30.

As shown in Table 7, no matter which traffic pattern we adopt, the solutions of our algorithm perform better on energy consumption than that of the RSSI-based association scheme. In addition, we find that when a traffic pattern switches from the busy mode to the standard mode, the decrement of our algorithm’s energy consumption is more than the RSSI-based association scheme’s, because some APs will turn off while executing our algorithm.

Table 7

Energy consumption affected by traffic pattern.

Traffic pattern	Energy consumption in a day (W $\cdot$ h)
	MURA algorithm	RSSI-based association
Standard	36752	89237
Busy	48934	91501

6. Conclusion

We investigated the energy-efficient user association in green WLANs while considering AP congestion avoidance and user migration constraints. First, we formulated the EACM problem as an ILP model, to minimize APs’ overall energy consumption in a current time interval under the constraints of traffic demand, the AP utilization threshold, and the maximum number of migrations allowed. Then, we proposed MURA, a two-step algorithm that efficiently solves the problem. Finally, we conducted simulation experiments to evaluate the performance of our proposed algorithm. The results demonstrate that MURA effectively saves energy—beyond that, the algorithm can obtain the tradeoff between energy efficiency, congestion avoidance, and migration cost.

In the future, we plan to measure traffic patterns in real-world scenarios through crowdsourcing and propose a data-driven user association algorithm that applies well to a real network.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

This work was supported by National Key R & D Program of China 2017YFB1003000, National Natural Science Foundation of China under Grants no. 61632008, no. 61572130, no. 61502100, no. 61602111, no. 61532013, and no. 61320106007, Jiangsu Provincial Natural Science Foundation of China under Grants no. BK20150637 and no. BK20150628, Jiangsu Provincial Key Laboratory of Network and Information Security under Grant no. BM2003201, and Key Laboratory of Computer Network and Information Integration of Ministry of Education of China under Grant no. 93K-9.

References

[1] P. Hu, S. Dhelim, H. Ning, T. Qiu, "Survey on fog computing: architecture, key technologies, applications and open issues," Journal of Network and Computer Applications, vol. 98, pp. 27-42, DOI: 10.1016/j.jnca.2017.09.002, 2017.

[2] B. Bellalta, L. Bononi, R. Bruno, A. Kassler, "Next generation IEEE 802.11 Wireless Local Area Networks: Current status, future directions and open challenges," Computer Communications, vol. 75,DOI: 10.1016/j.comcom.2015.10.007, 2016.

[3] M. Afanasyev, T. Chen, G. M. Voelker, A. C. Snoeren, "Usage patterns in an urban WiFi network," IEEE/ACM Transactions on Networking, vol. 18 no. 5, pp. 1359-1372, DOI: 10.1109/TNET.2010.2040087, 2010.

[4] Ł. Budzisz, F. Ganji, G. Rizzo, M. Ajmone Marsan, M. Meo, Y. Zhang, G. Koutitas, L. Tassiulas, S. Lambert, B. Lannoo, M. Pickavet, A. Conte, I. Haratcherev, A. Wolisz, "Dynamic resource provisioning for energy efficiency in wireless access networks: A survey and an outlook," IEEE Communications Surveys & Tutorials, vol. 16 no. 4, pp. 2259-2285, DOI: 10.1109/COMST.2014.2329505, 2014.

[5] X. Xu, W. Dou, X. Zhang, J. Chen, "EnReal: An Energy-Aware Resource Allocation Method for Scientific Workflow Executions in Cloud Environment," IEEE Transactions on Cloud Computing, vol. 4 no. 2, pp. 166-179, DOI: 10.1109/TCC.2015.2453966, 2016.

[6] X. Xu, X. Zhang, M. Khan, W. Dou, S. Xue, S. Yu, "A balanced virtual machine scheduling method for energy-performance trade-offs in cyber-physical cloud systems," Future Generation Computer Systems,DOI: 10.1016/j.future.2017.08.057, 2017.

[7] A. P. Jardosh, K. Papagiannaki, E. M. Belding, K. C. Almeroth, G. Iannaccone, B. Vinnakota, "Green WLANs: on-demand WLAN infrastructures," Mobile Networks and Applications, vol. 14 no. 6, pp. 798-814, DOI: 10.1007/s11036-008-0123-8, 2009.

[8] P. Serrano, A. De La Oliva, P. Patras, V. Mancuso, A. Banchs, "Greening wireless communications: Status and future directions," Computer Communications, vol. 35 no. 14, pp. 1651-1661, DOI: 10.1016/j.comcom.2012.06.011, 2012.

[9] F. Ganji, Ł. Budzisz, F. G. Debele, N. Li, M. Meo, M. Ricca, Y. Zhang, A. Wolisz, "Greening campus WLANs: Energy-relevant usage and mobility patterns," Computer Networks, vol. 78, pp. 164-181, DOI: 10.1016/j.comnet.2014.10.033, 2015.

[10] V. Sivaraman, J. Matthews, C. Russell, S. T. Ali, A. Vishwanath, "Greening residential Wi-Fi networks under centralized control," IEEE Transactions on Mobile Computing, vol. 14 no. 3, pp. 552-564, DOI: 10.1109/TMC.2014.2324582, 2015.

[11] Y. Bejerano, S. Han, L. E. Li, "Fairness and load balancing in wireless LANs using association control," pp. 315-329, DOI: 10.1145/1023720.1023751, .

[12] W. Li, S. Wang, Y. Cui, X. Cheng, R. Xin, M. A. Al-Rodhaan, A. Al-Dhelaan, "AP association for proportional fairness in multirate WLANs," IEEE/ACM Transactions on Networking, vol. 22 no. 1, pp. 191-202, DOI: 10.1109/tnet.2013.2245145, 2014.

[13] D. Gong, Y. Yang, "On-line {AP} association algorithms for 802.11n {WLAN}s with heterogeneous clients," Institute of Electrical and Electronics Engineers. Transactions on Computers, vol. 63 no. 11, pp. 2772-2786, DOI: 10.1109/TC.2013.156, 2014.

[14] J. Yu, W.-C. Wong, "Optimal association in wireless mesh networks," IEEE Transactions on Vehicular Technology, vol. 64 no. 5, pp. 2084-2096, DOI: 10.1109/TVT.2014.2339214, 2015.

[15] W. Wong, A. Thakur, S. G. Chan, "An approximation algorithm for AP association under user migration cost constraint," Proceedings of the IEEE INFOCOM 2016 - IEEE Conference on Computer Communications,DOI: 10.1109/INFOCOM.2016.7524397, .

[16] A. Raschella, F. Bouhafs, M. Seyedebrahimi, M. Mackay, Q. Shi, "Quality of service oriented access point selection framework for large Wi-Fi networks," IEEE Transactions on Network and Service Management, vol. 14 no. 2, pp. 441-455, DOI: 10.1109/TNSM.2017.2678021, 2017.

[17] J. Chen, B. Liu, H. Zhou, Q. Yu, L. Gui, X. S. Shen, "QoS-Driven Efficient Client Association in High-Density Software-Defined WLAN," IEEE Transactions on Vehicular Technology, vol. 66 no. 8, pp. 7372-7383, DOI: 10.1109/TVT.2017.2668066, 2017.

[18] H. Kim, W. Lee, M. Bae, H. Kim, "Wi-Fi Seeker: A link and Load Aware AP Selection Algorithm," IEEE Transactions on Mobile Computing, vol. 16 no. 8, pp. 2366-2378, DOI: 10.1109/TMC.2016.2618790, 2017.

[19] K. Kumazoe, D. Nobayashi, Y. Fukuda, T. Ikenaga, K. Abe, "Multiple station aggregation procedure for radio-on-demand WLANs," Proceedings of the 2012 7th International Conference on Broadband, Wireless Computing, Communication and Applications, BWCCA 2012, pp. 156-161, .

[20] B. Wang, Q. Kong, L. T. Yang, "Context-aware user association for energy cost saving in a green heterogeneous network with hybrid energy supplies," Mobile Networks and Applications, vol. 20 no. 6, pp. 802-816, DOI: 10.1007/s11036-015-0621-4, 2015.

[21] Y. Chen, Y. Shen, L. Wang, "Achieving energy saving with QoS guarantee for WLAN using SDN," Proceedings of the ICC 2016 - 2016 IEEE International Conference on Communications,DOI: 10.1109/ICC.2016.7511355, .

[22] K. Lee, Y. Kim, S. Kim, J. Shin, S. Shin, S. Chong, "Just-in-time WLANs: On-demand interference-managed WLAN infrastructures," Proceedings of the IEEE INFOCOM 2016 - IEEE Conference on Computer Communications,DOI: 10.1109/INFOCOM.2016.7524451, .

[23] K. Tutschku, "Demand-based radio network planning of cellular mobile communication systems," Proceedings of the IEEE INFOCOM'98 Conference on Computer Communications Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies Gateway to the 21st Century, pp. 1054-1061, DOI: 10.1109/INFCOM.1998.662915, .

[24] A. Garcia-Saavedra, P. Serrano, A. Banchs, G. Bianchi, "Energy consumption anatomy of 802.11 devices and its implication on modeling and design," Proceedings of the 8th ACM International Conference on Emerging Networking EXperiments and Technologies, CoNEXT 2012, pp. 169-180, .

[25] R. G. Garroppo, G. Nencioni, G. Procissi, L. Tavanti, "The impact of the access point power model on the energy-efficient management of infrastructured wireless LANs," Computer Networks, vol. 94, pp. 99-111, DOI: 10.1016/j.comnet.2015.11.018, 2016.

[26] V. Chvatal, "A greedy heuristic for the set-covering problem," Mathematics of Operations Research, vol. 4 no. 3, pp. 233-235, DOI: 10.1287/moor.4.3.233, 1979.

[27] M. Rim, A. Mujumdar, R. Jain, R. DeLeone, "Optimal and Heuristic Algorithms for Solving the Binding Problem," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 2 no. 2, pp. 211-225, DOI: 10.1109/92.285747, 1994.

[28] Y. Bejerano, S.-J. Han, "Cell breathing techniques for load balancing in wireless LANs," IEEE Transactions on Mobile Computing, vol. 8 no. 6, pp. 735-749, DOI: 10.1109/tmc.2009.50, 2009.

[29] MCS index - 802.11n and 802.11ac,2015, https://www.wlanpros.com/resources/mcs-index-802-11ac-vht-chart/

[30] MCS value achieved by clients at various signal to noise ratio levels (SNR), 2015, https://www.wlanpros.com/resources/revolution-wifi-mcs-to-snr-single-page/

[31] A. Capone, F. Malandra, B. Sansò, "Energy savings in Wireless Mesh Networks in a time-variable context," Mobile Networks and Applications, vol. 17 no. 2, pp. 298-311, DOI: 10.1007/s11036-011-0339-x, 2012.