Adaptive access-point and channel selection method using Markov approximation

Abstract

This article proposes an access-point and channel selection method for Internet of Things environments. Recently, the number of wireless nodes has increased with the growth of Internet of Things technologies. In order to accommodate traffic generated by the wireless nodes, we need to utilize densely placed wireless access-points. This article introduces a joint optimization problem of access-point and channel selection for such an environment. The proposed method deals with the optimization problem, using Markov approximation which adapts to dynamic changes in network conditions. Markov approximation is a distributed optimization framework, where a network is optimized by individual behavior of users forming a time-reversible continuous-time Markov chain. The proposed method searches optimal solution for the access-point and channel selection problem on the time-reversible continuous-time Markov chain. Simulation experiments demonstrate the effectiveness of the proposed method.

Keywords

Internet of Things access-point selection channel selection Markov approximation optimization problem

Introduction

Recently, a huge number of network devices have connected to the Internet, which leads to the realization of Internet of Things (IoT).^1–5 The number of network devices will further increase with the growth of IoT technologies. In IoT environments, many wireless nodes and access-points are assumed to be densely distributed, and they construct wireless local area networks.⁶ In fact, the number of access-points has increased rapidly in public spaces such as train stations and airports. When there are some access-points in a given area, wireless nodes can select an access-point from among them. Each access-point selects a channel to communicate and then communicates with wireless nodes on the channel. The quality of the communications strongly depends on the selected access-points and channels. Therefore, access-point and channel selection has become an important technical issue.^7–10

Under current IEEE 802.11 specifications, wireless nodes select the access-point with the highest received signal strength indicator (RSSI). In this RSSI-based selection, traffic loads among access-points are often uneven. Some access-points have many wireless nodes, whereas others have relatively few wireless nodes. When many wireless nodes connect to an access-point, the throughput drastically decreases because of traffic congestion. To alleviate this traffic congestion, some wireless nodes should switch to access-points that have lower loads but somewhat lower RSSIs. Moreover, RSSI-based selection causes another problem in terms of frequency resource utilization of access-points because the RSSI values are independent of channels of access-points. In cases where neighboring access-points use the same channel, we should avoid simultaneously using the access-points even if those RSSIs are high. Frequency resources can be effectively used by selecting an access-point that has a lower RSSI and uses a different channel.

In the past, several access-point selection methods have been considered.^7–9 Most of those methods use techniques such as mathematical programming and heuristic algorithms to select the optimal access-point based on the number of wireless nodes and RSSI levels at a given time.⁷ These methods must conduct the optimization process in a centralized manner each time the number of users changes or any RSSI value is updated. Hence, they are not suitable for access-point selection in situations where network conditions change dynamically. In public spaces such as train stations and airports, network conditions frequently change. Typically, users stay in public spaces for a short period, and most users briefly connect to particular access-points. Especially, in IoT environments, namely, densely deployed wireless networks, network conditions more frequently change because there are a lot of access-points and wireless nodes in a small area. Therefore, an access-point and channel selection method that can flexibly accommodate such dynamic situations is needed for IoT environments.

To effectively select access-points and/or channels in IoT environments, some methods have been proposed in the literature.^10–15 Karimi et al.¹² have proposed an access-point and channel selection method. In this method, multiple access-points collaborate with each other in order to accommodate users’ traffic. The authors have formulated the proposed method as a mathematical programming and maximized the throughput of the users. However, this method is centralized optimization and does not consider dynamic situations. Wu et al.^13,14 have proposed channel selection and access scheduling methods for wireless mesh networks and sensor networks. These methods select a channel for each wireless node and schedule packet transmission among wireless nodes based on Latin squares. Although these methods enhance the throughput of wireless nodes, they also do not consider dynamic situations. Zhu et al.¹⁵ have proposed a channel selection method for sensor networks in IoT environments, which utilizes the multi-armed bandit model. This method assumes dynamic situations, but does not consider an access-point selection problem. Bai et al.¹¹ have proposed an access-point selection for enterprise wireless local area networks (WLANs), which collects information on networks and selects access-point based on stochastic dominance tools. Xu et al.¹⁰ have proposed an online access-point selection method named SmartAssoc that aims at maximizing the minimum throughput among users. SmartAssoc considers dynamic situations. When a new user arrives, the user connects to an access-point based on p-norm of current loads for access-points. Although these access-point selection methods work under dynamic situations, they do not consider a channel selection problem.

In this article, we deal with a joint optimization problem of access-point and channel selection for IoT environments, considering dynamic situations. We first introduce a mixed-integer programming (MIP) for the joint optimization problem of access-point and channel selection. The MIP represents ideal performance, but it is difficult to apply the MIP to large-scale problems in dynamic situations. We then propose a new access-point and channel selection method using Markov approximation in order to adapt to dynamic changes in network conditions. Markov approximation is a distributed optimization framework¹⁶ and provides approximate solution for optimization problems. In Markov approximation, a network system is designed in such a way that it follows a time-reversible continuous-time Markov chain, where its states correspond to network conditions. The sojourn time in each state depends on the utility value of the network system. By doing so, the time average of the utility value approaches the optimal value. The proposed method searches approximate solution for the joint optimization problem of access-point and channel selection on the time-reversible continuous-time Markov chain, aiming at maximizing the minimum throughput of wireless nodes. To do so, the proposed method represents combinations of access-points selected by wireless nodes and channels selected by access-points as states of the Markov chain.

The motivation for this article is as follows. Markov approximation optimizes the network configurations by adaptively changing independent behaviors of users (i.e. wireless nodes) with time based on minimum necessary information. It flexibly responds to dynamic characteristics of the network conditions caused by arrival and departure of wireless nodes because the network configurations are optimized by just the behaviors of the mobile users without network operators. Therefore, it is suitable for situations where network conditions frequently change. In IoT environments, network conditions often change in a given area. In such environments, as mentioned above, conventional optimization techniques used in access-point and channel selection methods do not work well. They are done in centralized control by resolving optimization problems according to a network condition at a certain time. In these methods, network operators collect information on the network, and they optimize and configure the whole network, which has large overhead, every time the network condition is updated. Therefore, they are not suitable for IoT environments. To overcome this difficulty, we apply Markov approximation to the access-point and channel selection problem.

Note that the previous works about Markov approximation assumed static situations where the network condition do not change despite the characteristic of Markov approximation, which is suitable for IoT environments. In this article, we focus on the adaptability of Markov approximation to dynamic situations. The proposed method applies Markov approximation to the access-point and channel selection problem so as to adapt to the dynamic characteristic of the IoT environments and we reveal the impact of the proposed method through simulation experiments.

This article is an extended version of our conference paper. The conference paper introduced the main idea of our proposed method and showed its fundamental performance. In this article, we modify the proposed method in order to improve not only total throughput of users but also throughput fairness of users by changing the definition of the objective function of the optimization problem. Furthermore, this article provides the MIP for the optimization problem to obtain its optimal solution. We also add the results of simulation experiments in several scenarios for depicting the performance of the proposed method in detail.

The rest of this article is organized as follows. We first describe the system model and access-point selection problem. We then introduce the MIP for the problem and provide the proposed dynamic selection method using Markov approximation. We present experimental results to evaluate the performance of our proposed method. Finally, we conclude this article.

System model and access-point selection problem

System model

We assume that there are multiple users (wireless nodes) and multiple access-points in a given area, as shown in Figure 1. Let $K (t)$ , $A$ , and $C$ denote the set of users at time $t$ , the set of access-points, and the set of channels, respectively. Each access-point $a \in A$ selects one of the $| C |$ channels, and each user $k \in K (t)$ selects one of the $| A |$ access-points. We also assume dynamic situations where users dynamically arrive at and depart from the area with time $t$ .

Figure 1.

System model $(| K (t) | = 5, | A | = 3)$ .

The system state is represented by combinations of channels selected by access-points and access-points selected by users. We define the $1 \times | A |$ vector $x$ as the access-point state, in which the ith element $x_{i} \in {1, 2, \dots, | C |}$ is the channel selected by access-point $i$ . We also define the $1 \times | K (t) |$ vector $y$ as the user state, in which the jth element $y_{j} \in {1, 2, \dots, | A |}$ is the access-point selected by user $j$ . With these definitions, the system state at time $t$ is denoted by $(x, y)$ . We further define the set $Z (t)$ of feasible system states at time $t$ as follows

\begin{matrix} Z (t) \\ = {(x, y) | x_{i} \in {1, 2, \dots, | C |}, y_{j} \in {1, 2, \dots, | A |} \\ i = 1, 2, \dots, | A |, j = 1, 2, \dots, | K (t) |} \end{matrix}

In this article, we refer to $z \in Z (t)$ as a strategy. When there is no need to distinguish between access-points and users, each of them is collectively referred to as a player.

Let $N_{k} (z)$ and $u_{k} (z)$ denote the total number of users that use the same channel as user $k$ (including user $k$ ) and the throughput of user $k$ , respectively, under strategy $z$ . Let $m_{k, a}$ denote the maximum throughput that user $k$ achieves when the user connects to access-point $a$ and exclusively occupies a single channel. We assume that when there are multiple users on a channel, the frequency resources on the channel are evenly available for their communications by means of time-division multiplexing (i.e. $u_{k} (z) = m_{k, a} / N_{k} (z)$ for user $k$ connecting access-point $a$ under strategy $z$ ).

Access-point and channel selection problem

This article deals with a problem that maximizes the minimum throughput of users at a given time $t$ . The objective function of the problem is as follows

\max_{z \in Z (t)} {\min_{k \in K (t)} u_{k} (z)}

(1)

Equation (1) is a combinatorial optimization problem which is known to be non-deterministic polynomial-time (NP)-hard. Therefore, a brute-force search is the only way to correctly obtain the optimal solution. However, even if the numbers of users and access-points are small, the total number of strategies $| Z (t) |$ becomes extremely large. This makes it difficult to obtain the optimal solution with a brute-force search in a reasonable time. Moreover, under situations where users dynamically arrive and depart, we need to obtain the optimal strategy $z^{*} \in Z (t)$ in order to maximize the utility every time the system conditions change. Our proposed method thus uses Markov approximation¹⁶ to obtain approximate solution to equation (1) in a dynamic manner.

MIP

Before we explain the proposed access-point and channel selection method, we introduce the following MIP that maximizes the minimum throughput of users at a given time $t$ . The symbols used in the MIP are listed in Table 1.

Table 1.

List of symbols in MIP.

Symbol	Meaning
$ψ$	Real variable that represents the minimum throughput of users.
$Y_{k, a}$	Binary variable that is equal to 1 if user $k \in K (t)$ uses access-point $k$ ; otherwise, 0.
$X_{a, c}$	Binary variable that is equal to 1 if access-point $a \in A$ uses channel $c \in C$ ; otherwise, 0.
$δ_{k, a, c}$	Binary variable that is equal to 1 if user $k \in K (t)$ connects to access-point $a \in A$ with channel $c \in C$ ; otherwise, 0.
$γ_{k, k', c}$	Binary variable that is equal to 1 if user $k \in K (t)$ and user $k' \in K (t)$ use the same channel $c \in C$ ; otherwise, 0.
$N_{k}$	Positive integer variable that indicates the number of users that use the same channel as user $k \in K (t)$ .
$M$	Sufficiently large value.
$σ_{k, n}$	Binary variable that is equal to 1 if $N_{k} = n$ ; otherwise, 0.
$μ_{k, a, n}$	Binary variable that is equal to 1 if user $k \in K (t)$ uses access-point $a \in A$ and $N_{k} = n$ .

Maximize

ψ

(2)

subject to

\forall k \in K (t); \sum_{a \in A} Y_{k, a} = 1

(3)

\forall a \in A; \sum_{c \in C} X_{a, c} = 1

(4)

\begin{matrix} \forall k \in K (t), c \in C, a \in A; X_{a, c} + Y_{k, a} - 1 \leq δ_{k, a, c} \\ X_{a, c} \geq δ_{k, a, c}, Y_{k, a} \geq δ_{k, a, c} \end{matrix}

(5)

\begin{matrix} \forall k, k' \in K (t), c \in C; \\ \sum_{a \in A} δ_{k, a, c} + \sum_{a \in A} δ_{k', a, c} - 1 \leq γ_{k, k', c} \\ \sum_{a \in A} δ_{k, a, c} \geq γ_{k, k', c}, \sum_{a \in A} δ_{k', a, c} \geq γ_{k, k', c} \end{matrix}

(6)

\forall k \in K (t); N_{k} = 1 + \sum_{k' \in K (t) \ {k}} \sum_{c \in C} γ_{k, k', c}

(7)

\begin{matrix} \forall k \in K (t), n = 1, 2, \dots, | K (t) |; \\ N_{k} - n \leq M (1 - σ_{k, n}) \\ - (N_{k} - n) \leq M (1 - σ_{k, n}) \end{matrix}

(8)

\begin{matrix} \forall k \in K (t), a \in A, n = 1, 2, \dots, | K (t) |; \\ Y_{k, a} + σ_{k, n} - 1 \leq μ_{k, a, n} \\ Y_{k, a} \geq μ_{k, a, n}, σ_{k, n} \geq μ_{k, a, n} \end{matrix}

(9)

\forall k \in K (t); \sum_{n = 1}^{| K (t) |} \sum_{a \in A} m_{k, a} μ_{k, a, n} / n \geq ψ

(10)

Equation (2) is the objective function, which indicates the minimum throughput of users. Equation (3) means that user $k$ connects to one of the access-points. Equation (4) indicates that access-point $a$ selects one of the channels. Equations (5)–(7) provide the number $N_{k}$ of users that use the same channel as user $k$ . Equations (8)–(10) calculate the throughput of user $k$ , and equation (10) represents that the throughput of each user is equal to or more than $ψ$ . Therefore, equations (2) and (10) maximize the minimum throughput of users, which correspond to equation (1).

Although the MIP provides the optimal solution, it is not suitable for large-scale problems and dynamic situations because the MIP is NP-hard. Therefore, the proposed access-point and channel selection method aims to obtain approximation solution, using Markov approximation.

Dynamic selection using Markov approximation

This section first gives an overview of Markov approximation and then describes the proposed access-point selection method that uses Markov approximation under dynamic situations.

Markov approximation

Under static situations, equation (1) is equivalent to^16,17

\begin{matrix} \max_{p (t) \geq 0} \sum_{z \in Z (t)} p_{z} Φ_{z} \\ subject to \sum_{z \in Z (t)} p_{z} = 1 \end{matrix}

(11)

where $p_{z}$ is the percentage of time that strategy $z \in Z (t)$ is selected, $p (t)$ is the $1 \times | Z (t) |$ vector $(p_{1} p_{2} \dots p_{| Z (t) |})$ , and $Φ_{z} = \min_{k \in K (t)} u_{k} (z)$ .

Markov approximation obtains approximate solution to an optimization problem using the following relation

\begin{matrix} \max {w_{1}, w_{2}, \dots, w_{n}} \\ \leq \frac{1}{β} \log (\sum_{i = 1}^{n} \exp (β w_{i})) \\ \leq \max {w_{1}, w_{2}, \dots, w_{n}} + \frac{1}{β} \log n \end{matrix}

where $β$ is a positive constant, and $w_{1}, w_{2}, \dots, w_{n}$ are non-negative variables. From this relation, we have the log-sum-exponential (LSE) function as follows

\max (w_{1}, w_{2}, \dots, w_{n}) = \lim_{β \to \infty} \frac{1}{β} \log (\sum_{i = 1}^{n} \exp (β w_{i}))

When we define $w_{i}$ as

w_{i} = Φ_{z_{i}}, z_{i} \in Z (t), i = 1, 2, \dots, | Z (t) |

we have the following approximation

\max_{z \in Z (t)} Φ_{z} \approx \frac{1}{β} \log (\sum_{z \in Z (t)} \exp (β Φ_{z}))

(12)

From the above, we can see that the accuracy of the approximation depends on $β$ , and we obtain the optimal value when $β = \infty$ .

Owing to the fact that the LSE function is a closed and convex function, we obtain the following approximation for equation (11) from equation (12)¹⁶

\begin{matrix} \max_{p (t) \geq 0} \sum_{z \in Z (t)} p_{z} Φ_{z} - \frac{1}{β} \sum_{z \in Z (t)} p_{z} \log p_{z} \\ subject to \sum_{z \in Z (t)} p_{z} = 1 \end{matrix}

This is a nonlinear programming problem, and thus, we can obtain an optimal solution $p_{z}^{*}$ by solving the Karush–Kuhn–Tucker conditions

\begin{matrix} Φ_{z} - \frac{1}{β} \log p_{z}^{*} - \frac{1}{β} + η = 0, \forall z \in Z (t) \\ \sum_{z \in Z (t)} p_{z}^{*} = 1 \\ η \geq 0 \end{matrix}

where $η$ is a Lagrange multiplier. Solving the above problem, $p_{z}^{*} (z \in Z (t))$ is given by

p_{z}^{*} = \frac{\exp (β Φ_{z})}{\sum_{z' \in Z (t)} \exp (β Φ_{z'})}

(13)

With $p_{z}^{*}$ , the approximate value of equation (11) is given by

\sum_{z \in Z (t)} p_{z}^{*} Φ_{z}

(14)

As $β$ increases, the accuracy of the approximation improves, and the value of equation (14) approaches the optimal value.

We now consider a time-reversible continuous-time Markov chain, where states are elements in $Z (t)$ and each steady-state probability is equal to $p_{z}^{*}$ . In order to construct such a time-reversible continuous-time Markov chain, for each pair of adjacent states $z, z' \in Z (t)$ , the local balance equation should be satisfied as follows¹⁶

p_{z}^{*} q_{z, z'} = p_{z'}^{*} q_{z', z}

where $q_{z, z'}$ represents the transition rate from the state $z$ to its adjacent state $z'$ . One way to satisfy the local balance equation is to set the transition rate $q_{z, z'}$ to

q_{z, z'} = \frac{α (t)}{\exp (β Φ_{z})}

(15)

where $α (t)$ is a parameter controlling the transition rate. As we can see from equation (15), the transition rate depends on the utility value. Specifically, transition rates from states with high utility values to other states are small, and thus, the sojourn time of the states becomes large. However, the sojourn time of states with low utility values is small. As a result, the time average of the utility values approaches to the optimal value. In the literature,¹⁶ performance evaluations were conducted under static situations with fixed $α (t)$ . In dynamic situations, however, we should dynamically adjust the value of $α (t)$ according to system conditions because the transition rate $q_{z, z'}$ depends on the number of users.

Proposed method

In our proposed method, each access-point selects a channel and each user selects an access-point according to a time-reversible continuous-time Markov chain on $Z (t)$ . To do so, each player follows the flow in Figure 2. Each player first generates a counter $r$ that is random value according to the exponential distribution with a parameter $λ (t)$ depending on the current utility $Φ_{z}$ (i.e. minimum throughput of users). For access-points, $λ (t)$ is defined as

λ (t) = \frac{α (t) (| C | - 1)}{\exp (β Φ_{z})}

(16)

and for users, $λ (t)$ is defined as

λ (t) = \frac{α (t) (| A | - 1)}{\exp (β Φ_{z})}

(17)

Figure 2.

Player operation.

Note that each player knows the current utility by exchanging information on its current throughput. After setting $r$ , each player decreases the counter $r$ with time.

When the counter $r$ of a player reaches zero, the player changes a current strategy as follows. In the case where the player is access-point $a$ , it randomly selects a channel from $C \ {c}$ (i.e. a channel other than the current channel $c$ ) and switches to that channel. Similarly, in the case where the player is user $k$ , it randomly selects an access-point from $A \ {a}$ (i.e. an access-point other than the current access-point $a$ ) and reconnects to the selected access-point. Immediately after the new strategy $z_{new}$ is adopted, the player changing the strategy sends a notification to all other players. When receiving the notification, each player then estimates and broadcasts its current throughput. By doing so, each player knows the new utility $Φ_{z_{new}}$ . Furthermore, each player generates a new counter $r$ with $Φ_{z_{new}}$ and repeats the above procedure.

When the number of users changes, all players are also notified of the change in the utility. Specifically, when a new user arrives, the new user sends a notification to participate. Moreover, when a user departs, it sends a notification immediately before the departure. Players receiving these notifications halt their countdowns and then reset their counters to random value according to the exponential distribution with the parameter $λ (t)$ .

In our proposed method, we define $α (t)$ in equations (16) and (17) as

α (t) = \frac{ξ \cdot \exp (β M (t))}{| A | (| C | - 1) + | K (t) | (| A | - 1)}

where $ξ$ is a positive constant, and $M (t)$ is the maximum utility from the occurrence of a change in the user number to time $t$ (Figure 3). $M (t)$ is updated as follows. When a notification of a change to strategy $z$ is received at time $t$ , if $Φ_{z} > M (t)$ , then $M (t)$ is updated by setting $M (t) : = Φ_{z}$ . This update is also performed when the number of users changes at time $t$ . Because the number of feasible transitions from strategy $z$ is equal to $| A | (| C | - 1) + | K (t) | (| A | - 1)$ (see Figure 4), the transition rate $q_{z} (t)$ from strategy $z$ is given by

\begin{matrix} q_{z} (t) & = \frac{α (t) (| A | (| C | - 1) + | K (t) | (| A | - 1))}{\exp (β Φ_{z})} \\ = \frac{ξ \cdot \exp (β M (t))}{\exp (β Φ_{z})} \end{matrix}

Figure 3.

Example of change in $M (t)$ .

Figure 4.

Feasible transitions from strategy z.

When $Φ_{z} = M (t)$ , the strategy changes according to the exponential distribution with the rate $q_{z} (t) = ξ$ . In contrast, when $Φ_{z} < M (t)$ , we have $q_{z} (t) > ξ$ , and thus, the mean time over which strategy $z$ is adopted is shorter than that in strategies that attain $M (t)$ as shown in Figure 5.

Figure 5.

Strategy changes in our proposed method.

Performance evaluation

Evaluation model

We evaluate our proposed method through simulation experiments. We consider two scenarios with different values for maximum throughput $m_{k, a}$ . In the first scenario, we set $m_{k, a} = 50$ for each user $k \in K (t)$ and access-point $a \in A$ . In the second scenario, $m_{k, a}$ is randomly selected from among ${40, 45, 50}$ . In the following, we refer to the first scenario as the homogeneous scenario and the second scenario as the heterogeneous scenario.

We assume that immediately after the strategy of a player changes, other players can know the change. We set the number $| A |$ of access-points to $20$ , the number $| C |$ of channels to $10$ , and the parameter $ξ$ to $0.01$ . At time $t = 0$ , each user randomly selects an access-point, and each access-point randomly selects a channel.

We use three indices as performance metrics: the mean utility, the mean number of iterations, and the mean total throughput. The mean utility is the time average of the utility value normalized by $ϕ$ , where $ϕ$ denotes the time average of the optimal value of the total throughput $\sum_{k \in K (t)} u_{k} (z)$ divided by the number $| K (t) |$ of users. Note that the optimal value of the total throughput can be easily obtained, that is, $| C | \times \max {m_{k, a}} = 10 \times 50 = 500$ . The mean number of iterations is the mean number of strategy changes per player per unit time, and the mean total throughput is the time average of the total throughput of users. Unless stated otherwise, in each simulation experiment, the simulation runs until 50,000 time units.

For the sake of comparison, we show the results of the RSSI-based method, the simulated annealing method, SmartAssoc method,¹⁰ and the proposed method, the objective function of which is maximizing the total throughput (abbreviated as the throughput-based method).¹⁸

The RSSI-based method

A player is randomly chosen among $K (t) \cup A$ according to a Poisson process with rate 0.1 and then the player changes its strategy. In the case where the player is a user, it selects the access-point that has the highest maximum throughput (i.e. $m_{k, a} = 50$ ). If there are multiple access-points with the highest maximum throughput, the access-point is randomly selected among them. In contrast, in the case where the player is an access-point, it randomly selects the channel among $C$ .

The simulated annealing method

The optimization problem equation (1) is solved by the simulated annealing algorithm,¹⁹ which is one of the most widely used optimization techniques. This algorithm simulates the cooling process by gradually decreasing the temperature until the temperature is sufficiently low. The initial state $z_{init}$ of the system is randomly chosen from $Z (t)$ and the temperature $T$ is initially set to be $10^{6}$ . Until the temperature $T$ decreases below the threshold $t_{h} (t_{h} = 1)$ , the following procedure is repeated: we randomly choose a solution $z_{new}$ from the neighboring set $N_{z}$ of the current state $z$ , where $N_{z}$ is defined as the set of the feasible states that transition from the current state $z$ (Figure 4). The solution $z_{new}$ is accepted with the following probability $P_{A} (T)$

P_{A} (T) = (\begin{matrix} 1 & (Φ_{z} - Φ_{z_{new}} \leq 0) \\ \overset{- (Φ_{z} - Φ_{z_{new}}) / T}{\exp} & (Otherwise) \end{matrix}

(18)

If the solution $z_{new}$ is accepted, then the current state $z$ is updated to the solution $z_{new}$ , that is, $z : = z_{new}$ . After that, the temperature $T$ is updated to $T : = 0.95 T$ . In our experiments, we conducted 100 trails for different initial states, and obtained the best solution among solutions in these trails.

SmartAssoc

SmartAssoc is an online access-point selection method for maximizing throughput fairness.¹⁰ When a user arrives, it selects an access-point according to the following procedure. Let $A_{c}$ denote a set of access-point using channel $c \in C$ . For each access-point $a \in A_{c}$ in each set $A_{c}$ , the user calculates $L_{p}$ norm loads for all the access-points in $A_{c}$ in the case where the user connects to the access-point $a$ . The $L_{p}$ norm load is defined as $L_{p} = (\sum_{a \in A_{c}} L_{a}^{p})^{1 / p}$ , where $L_{a} = \sum_{k \in K_{a}} (1 / m_{k, a})$ , $K_{a}$ denotes the set of users using access-point $a$ , and $p$ is the natural logarithm of the number of the access-points in $A_{c}$ (i.e. $p = \ln (| A_{c} |)$ ). After calculating $L_{p}$ norm loads for all access-points in $A$ , the user selects the best candidate access-point that has the smallest $L_{p}$ norm load. However, the access-point selects a channel randomly.

The throughput-based method

The objective function equation (1) is substituted by the normalized total throughput, that is, $Φ_{z} = \sum_{k \in K} u_{k} (z) / | K |$ .¹⁸

Evaluation results

To evaluate the basic performance of our proposed method, we first consider static situations where the number of users is fixed. Figure 6 shows the mean utility value as a function of the parameter $β$ . In both scenarios, the mean utility value of our proposed method increases with $β$ . This result indicates that, for large $β$ , our proposed method can select access-points effectively in static situations. The proposed method can obtain the optimal value when $β = \infty$ , which is the characteristic of LSE function. Therefore, the proposed method works well when $β$ is large.

Figure 6.

Mean utility value: (a) homogeneous scenario and (b) heterogeneous scenario.

Figure 7 shows the mean number of iterations as a function of $β$ . In the homogeneous scenario, the mean number of iterations is relatively small, whereas in the heterogeneous scenario the mean number of iterations rapidly increases with $β$ . These results imply that the utility value in the homogeneous scenario tends to be larger than that in the heterogeneous scenario. In the proposed method, strategies with high utility values remain for long periods because the transition rates from the strategies to other strategies are set to be low values (see equations (16) and (17)). However, strategies with low utility values are frequently changed to other strategies. In the homogeneous scenario, the maximum throughput that users can achieve is the same for each access-point (i.e. $m_{k, a} = 50$ ). Therefore, even if a user changes an access-point, it is not easy to decrease the throughput. In contrast, in the heterogeneous scenario, the maximum throughput of users is different, and thus, the throughput tends to decrease when a user changes an access-point. As a result, the number of iterations in the heterogeneous scenario becomes large.

Figure 7.

Mean number of iterations: (a) homogeneous scenario and (b) heterogeneous scenario.

Figure 8 shows the normalized utility value as a function of elapsed time $t$ , where $β = 5$ . “Instantaneous” refers to the instantaneous utility value, and “Average” is the average utility value at each time. In both scenarios, strategy changes occur more frequently when $| K (t) | = 50$ . The reason is that strategies with small utility values are more likely to be selected when $| K (t) | = 50$ than when $| K (t) | = 20$ . Moreover, there is also a higher probability of selecting strategies with small utility values in the heterogeneous scenario than in the homogeneous scenario. This results in frequent strategy changes in the heterogeneous scenario.

Figure 8.

Changes in utility value with elapsed time $t$ (static situation): (a) $| K (t) | = 20$ (homogeneous scenario), (b) $| K (t) | = 50$ (homogeneous scenario), (c) $| K (t) | = 20$ (heterogeneous scenario), and (d) $| K (t) | = 50$ (heterogeneous scenario).

We then compare the proposed method with the RSSI-based method, the simulated annealing method and the throughput-based method. Figure 9 shows the mean utility value and the mean total throughput as a function of $β$ , where $| K (t) | = 50$ . In the figures, “Proposal (Fairness),”“Proposal (Throughput),”“Simulated Annealing,”“SmartAssoc,” and “RSSI” refer to our proposed method, the throughput-based method, the simulated annealing method, SmartAssoc method, and the RSSI-based method, respectively. In SmartAssoc, when new users arrive, they sequentially select access-points. We also plot the optimal values of the total throughput in the results. As we can see from Figure 9(a) and (c), for large $β$ , the mean utility value of our proposed method is larger than that of other methods. Specifically, our proposed method can improve the throughput fairness of users. Moreover, from Figure 8, we observe that the total throughput of our proposed method is comparable with that of the throughput-based method and the optimal value of the total throughput. We also observe that our proposed method outperforms the RSSI-based method, SmartAssoc and the simulated annealing method in terms of the total throughput. These results indicate that the proposed method increases not only the throughput fairness of users but also the total throughput. However, for small $β$ , the total throughput of our proposed method is smaller than that of the RSSI-based method in the heterogeneous scenario. This stems from the fact that our proposed method randomly selects the access-point among all access-points, whereas the RSSI-based method selects the access-point among the access-points with the highest RSSI value. This result implies that the performance of our proposed method could be improved by restricting the selection of access-point to access-points that have high RSSI value. We left the evaluation of the effectiveness of the restriction for the future work.

Figure 9.

Performance comparison $(| K (t) | = 50)$ : (a) mean utility (homogeneous scenario), (b) mean total throughput (homogeneous scenario), (c) mean utility (heterogeneous scenario), and (d) mean total throughput (heterogeneous scenario).

To demonstrate that our proposed method is effective under the dynamic situations where the number of users changes dynamically with time, we consider the following situation: $| K (t) | = 50$ for $0 < t \leq 20, 000$ , $| K (t) | = 30$ for $20, 000 < t \leq 40, 000$ , $| K (t) | = 50$ for $40, 000 < t \leq 60, 000$ , $| K (t) | = 20$ for $60, 000 < t \leq 80, 000$ , and $| K (t) | = 40$ for $80, 000 < t \leq 100, 000$ . We also show the results of SmartAssoc and the simulated annealing method. As for the simulated annealing method, the simulated annealing algorithm is conducted every time the number of users in the system is changed. Note that in SmartAssoc, we sequentially add all the users to the system in random order. Moreover, to fairly compare the performance, we modify SmartAssoc in such a way that players can dynamically change their strategies. Specifically, a player is randomly chosen among $K (t) \cup A$ according to a Poisson process with rate 0.1 and then the player changes its strategy. When the player is a user, it selects the access-point using SmartAssoc algorithm. By contrast, when the player is an access-point, it randomly selects the channel among $C$ .

Figure 10 shows the normalized utility value as a function of elapsed time $t$ , where $β = 5$ . From this figure, we observe that the normalized utility of SmartAssoc is stable because users periodically selects access-points with small $L_{p}$ norm load. We also observe that immediately after the number of users $| K (t) |$ changes, the utility value of our proposed method dropped significantly. As the time goes by, the mean utility value of our proposed method becomes large and is larger than the utility values of SmartAssoc and the simulated annealing method, because the selection of strategies with large utility values increases. This result indicates that our proposed method can adapt to sudden changes in the number of users and is an effective method for selecting access-points.

Figure 10.

Changes in utility with elapsed time $t$ (dynamic situation): (a) homogeneous scenario and (b) heterogeneous scenario.

Conclusion

We have proposed a new method for selecting access-points and channels using Markov approximation. Through simulation experiments, we showed that our proposed method can obtain the high mean utility value under static situations. Therefore, our proposed method is effective at improving the throughput fairness of users. We also showed that our proposed method adapts to dynamic changes in the number of users. In this article, we assumed instantaneous notification of strategy changes throughout the network. In practice, however, there is some latency in the exchange of information. We thus will consider the effects of latency in the future work.

Footnotes

Handling Editor: Sang-Woon Jeon

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Al-Fuqaha

Guizani

Mohammadi

et al . Internet of Things: a survey on enabling technologies, protocols, and applications. IEEE Commun Surv Tut 2015; 17: 2347–2376.

Gazis

A survey of standards for Machine-to-Machine (M2M) and the Internet of Things (IoT). IEEE Commun Surv Tut 2017; 19: 482–511.

Gubbi

Buyya

Marusic

et al . Internet of Things (IoT): a vision, architectural elements, and future directions. Future Gener Comp Sy 2013; 29: 1645–1660.

Whitmore

Agarwal

LD.

The Internet of Things–a survey of topics and trends. Inform Syst Front 2015; 17: 261–274.

Internet of things in industries: a survey. IEEE T Ind Inform 2014; 10: 2233–2243.

Balachandran

Bahl

Voelker

GM.

Hot-spot congestion relief in public-area wireless networks. In: Proceedings of the 4th IEEE workshop on mobile computing systems and applications (WMCSA’02), Callicoon, NY, 20–21 June 2002. New York: IEEE.

Akl

Park

Optimal access point selection and traffic allocation in IEEE 802.11 networks. In: Proceedings of the 9th world multi-conference on systemics, cybernetics and informatics (WMSCI’05), Orlando, FL, 10–19 July 2005.

Hamamoto

Takano

Obata

et al . An access point selection mechanism based on cooperation of access points and users movement. In: Proceedings of the 2015 IFIP/IEEE international symposium on integrated network management (IM’15), Ottawa, ON, Canada, 11–15 May 2015. New York: IEEE.

Koutsopoulos

Tassiulas

Joint optimal access point selection and channel assignment in wireless networks. IEEE ACM T Network 2007; 15: 521–532.

10.

Zhu

Tan

et al . SmartAssoc: decentralized access point selection algorithm to improve throughput. IEEE T Parall Distr 2013; 24: 2482–2491.

11.

Bai

Vuran

Batur

et al . Stoop: stochastically-dominant access point selection in enterprise WLANs. In: Proceedings of the 2017 IEEE international conference on smart computing, Hong Kong, China, 29–31 May 2017. New York: IEEE.

12.

Karimi

Liu

Rexford

. Optimal collaborative access point association in wireless networks. In: Proceedings of the 2014 IEEE INFOCOM, Toronto, ON, Canada, 27 April–2 May 2014. New York: IEEE.

13.

Bao

Regan

et al . Large-scale access scheduling in wireless mesh networks using social centrality. J Parallel Distr Com 2013; 73: 1049–1065.

14.

Bao

Liu

CH.

Scalable channel allocation and access scheduling for wireless Internet-of-Things. IEEE Sens J 2013; 13: 3596–3604.

15.

Zhu

Song

Jiang

et al . Multi-armed bandit channel access scheme with cognitive radio technology in wireless sensor networks for the Internet of Things. IEEE Access 2016; 4: 4609–4617.

16.

Chen

Liew

Shao

et al . Markov approximation for combinatorial network optimization. IEEE T Inform Theory 2013; 59: 6301–6327.

17.

Chen

Gan

Feng

et al . Markov approximation for Multi-RAT selection. In: Proceedings of the 2015 IEEE international conference on communications (ICC’15), London, 8–12 June 2015. New York: IEEE.

18.

Kimura

Hirata

Muraguchi

Dynamic access-point selection method using Markov approximation. In: Proceedings of the 2017 international conference on information networking (ICOIN’17), Da Nang, Vietnam, 11–13 January 2017. New York: IEEE.

19.

Van Laarhoven

PJM

Aarts

EHL

. Simulated annealing. In: Van Laarhoven

PJM

Aarts

EHL

(eds) Simulated annealing: theory and applications, vol. 37. Dordrecht: Springer, 1987, pp.7–15.