In this paper, a new green clustering algorithm is proposed to be as a first approach in the framework of an energy efficient strategy for centralized enterprise highdensity WLANs. Traditionally, in order to maintain the network coverage, all the APs within the WLAN have to be poweredon. Nevertheless, the new algorithm can poweroff a large proportion of APs while the coverage is maintained as its alwayson counterpart. The two main components of the new approach are the faster procedure based on Kmeans and the more accurate procedure based on Evolutionary Algorithm (EA), respectively. The two procedures are processes in parallel for different designed requirements and there is information interaction in between. In order to implement the new algorithm, EA is applied to handle the optimization of multiple objectives. Moreover, we adapt the method for selection and recombination, and then introduce a new operator for mutation. This paper also presents simulations in scenarios modeled with raytracing method and FDTD technique, and the results show that about 67% to 90% of energy consumption can be saved while it is able to maintain the original network coverage during periods when few users are online or the traffic load is low.
1. Introduction
M
ore and more enterprise offices
[1]
, university campuses
[2]
and municipal downtowns
[3]
deploy WLANs for flexible Internet connectivity. In many offices and campuses WLANs are deployed consisting of hundreds even thousands of APs (access point) which make the WLAN highdensity to meet the increasing demand of network accesses. Many of those WLANs, so called traditional WLANs, are designed to improve the usage of users during times of peak demands, but the peak demand rarely occurs
[4]
. All APs in traditional WLANs are alwayson to ensure the coverage of network, and many of the APs are considered idle or redundant when no users are associated with them. The utilization rate will be even lower during weekends or school holidays, and this is a kind of energy wastage which can be evitable.
SEAR (Survey, Evaluate, Adapt and Repeat) is an energy efficient strategy in highdensity WLANs proposed by Jardosh et al. to manage the network resource
[5]
. In
[5]
, a green clustering algorithm is introduced to form AP clusters and select the clusterhead APs for SEAR. Green clustering is the first algorithm for energy efficient strategies such as SEAR and the green clustering selects clusterhead APs to form a topology which can maintain the same (almost the same) coverage of network as the traditional WLANs.
In this paper, a new green clustering algorithm based on Evolutionary Algorithm (EA)
[6]
is proposed, and this method will henceforth be referred to as NGCA. NGCA consists of two different procedures which are the faster procedure implemented by
K
means algorithm and the more accurate procedure implemented by EA, respectively. The new approach forms AP clusters and selects clusterhead AP in a completely new perspective. Actually, either of the two procedures may achieve the designed requirements of the new algorithm, but reasonably combining the two approaches and integrating as the proposed NGCA can lead to a further improvement in terms of efficiency and accuracy.
The remainder of this paper is arranged as follow. An overview of related work is given in Section II. The highdensity WLAN is introduced firstly, followed by expression about the mechanism of SEAR, and then we detail the differences with respect to the green clustering algorithm of SEAR in Section III. While in Section IV we propose NGCA based on
K
means algorithm and EA. Section V provides simulation results and performance analysis. Section VI is conclusion and discussion of the paper.
2. Related Work
Concerning of energy efficiency in WLANs, D. Alessandro et al. introduce a multicarrier infrastructure to implement energy conservation in WLANs
[7]
. According to the analysis in
[8]
, L. Miliotis et al. study about the relations between communication efficiency and energy consumption which are important to wireless network management in wireless communication. In
[9]
, J. Rabaey considers that most energy consumption of wireless communication device is in standby mode and reducing the energy consumption of components is an important way to implement green communication. Marsan et al. introduce an analytical model for traffic in WLANs and present the threshold determined by the number of clients and traffic of an AP switch algorithm
[10]
. Y. Chen
[11]
and A. Kushki et al.
[12]
use information theory and probability theory to implement AP selection and A. Kushki et al. quantify the resolution of location on the basis of Fisher Rule for AP selection
[13]
. In
[14]
, S. H. Fang et al. use a predictionbased method to cluster APs in a decorrelated space In WSNs (wireless sensor networks) Y. Kang ret al. study about the lowpower asynchronous broadcast MAC protocol which employs the strobe preamble, compute the energy consumption via rigorous mathematical analysis, and the results show that the proposed scheme outperformance BCAST, a simple broadcast extension of the wellknown BMAC
[15]
. Lim S. et al. consider the stateoftheart ACKbased low power listening (LPL) scheme in WSNs suffers from collision problems due to the protocol incompleteness, and propose τduration CCA and Short Preamble Counter to mitigate the collision problem in ACKbased LPL MAC protocol and conserve more energy by reducing unnecessary overhearing, respectively, and they demonstrate the improvement of their scheme via a mathematical analysis and experiments, and their results show that up to 36% of energy is saved
[16]
. TDMA (Time Division Multiple Access) is a widely used MAC technique, and in TDMA energy saving is achieved by switching radio of nodes which are not engaged off, but the switching may increase endtoend delay. In
[17]
, Y. Zuo et al. propose hybrid algorithm which combines genetic algorithm and simulated annealing algorithm to solve a multiobjective TDMA scheduling problem. Kim D. W. and Park T. study about energy efficient MAC protocol for WSNs, and their scheme use the superframe structure which is bounded by the transmission of a beacon frame and have active and inactive portions, to save power consumption and guarantee QoS of realtime traffic
[18]
. S. Kang et al. consider that the clustering method is one of the preferred ways to produce a topology for reduced electrical energy consumption in wide area sensor networks, and propose cluster topology method based on sociological structures and concepts
[19]
. In WSN, the most important and common requirements regardless of application types are to provide a long network lifetime and small endtoend delay. J. Oak et al. propose Early Preamble MAC with improved energy conservation and low latency, and the proposed scheme is based on CMAC and adopts an early preamble type
[20]
. Y. Zhang et al. propose the unit QoE per Watt, which is termed QoE efficiency, as a useroriented metric to evaluate energy efficiency for wireless networks, investigate the tradeoffs between QoE efficiency and spectral efficiency, and their results show the proposed unit are helpful for network design and optimization
[21]
. J. Zhu studies about energy efficient cellular transmission which can improve the energy efficiency of wireless communication, he considers a cellular network consisting of one base station (BS) and multiple user terminals and explore the network coding for enhancing the energy efficiency of cellular downlink transmission from BS to users, and he proposes a network coded cellular transmission scheme which significantly outperformance the traditional cellular transmission in terms of energy efficiency
[22]
. Due to the uncertain of connections in Delay Tolerant Networks (DTNs), most routing algorithms in DTNs need nodes to forward the message to others based on the opportunistic contract which is related with the beaconing rate, and bigger beaconing rate uses more energy. In
[23]
, Y. Wu et al. try to exploit the optimal beaconing rate and forwarding rate when total energy is constraint. Employing mobile sinks for data gathering become a trend for energy conservation in WSN, and in
[24]
M. Eslaminejad et al. study about an energy efficient dualsink algorithm with role switching mechanism which utilizes both static and mobile sinks. Their algorithm could be employed in eventdriven and multihop scenarios with improvements on the lifetime, the load and the endtoend delay. However, few of these works above involve the concept of energy efficiency in highdensity WLANs or green clustering.
SEAR (Survey, Evaluate, Adapt and Repeat) is an energy efficient strategy in highdensity WLANs proposed by Jardosh et al. to manage the network resource
[5]
. An energy efficient algorithm in highdensity WLANs based on SEAR is studied in this paper, and green clustering algorithm is proposed and implemented.
Green clustering algorithm is an algorithm which generates the initial topology of APs for the energy efficient strategy. An AP selection is done by green clustering algorithm, and the coverage can be ensured by the selected APs which are a small part of the total ones in a highdensity WLAN. The selection process is dynamic. APs are poweredoff for energy conservation in an energy efficientWLAN, and the transmission power of clusterhead APs is optimized for energy conservation further more. In some particular scenarios which are not strict with coverage of network and allow spectrum holes to emerge only in the edge region APs can continue declining the transmission power and even be poweredoff to reduce the number of idle APs.
3. Analysis of Energy Efficient Strategy and Green Clustering Algorithm
 3.1 Centralized HighDensity WLANs
In traditional WLANs APs are independent of each other and access Internet through wired switches. As the enterprise WLAN generally consists of hundreds even thousands of APs, it is obviously inconvenient for management. For the purpose to make WLAN easier and friendlier to manage, many WLAN vendors such as Aruba Networks, Meru Networks, Symbol Technologies and Trapeze Networks have adopted the centralized approach to WLANs, as shown in
Fig. 1
.
A centralized WLAN infrastructure.
The deployment of centralized WLANs, which are convenient for network resource management, contributes to the growth and proliferation of enterprise WLANs. The number of APs in an enterprise WLAN increases exponentially every year
[1]
[2]
[25]
. So the energy efficient strategy studied in this paper is mainly concentrated on centralized highdensity WLANs. To determine that either a WLAN is highdensity or not, a parameter is introduced and defined as
where
n
_{AP}
is the number of APs in the WLAN, and
S
is the coverage of the WLAN relatively. So
μ
_{AP}
denotes the number of APs per unit area in the coverage region. Apparently, a bigger value means the density of APs within the WLAN is comparatively higher.
We present case studies from two different largescale enterprise WLANs. One example of such an enterprise WLAN is installed at Intel Corporation's building in Portland, OR, U.S., where 125 APs have been deployed at a distance of 5m from each other. There are four floors in the building and each floor is 80m × 38m. Another example is in the Microsoft campus at Redmond, WA, U.S., where 5000 APs have been deployed and the area is about 32,000 square meters
[4]
. According to (1), the values of
μ
_{AP}
are 0.01028 in Intel Corporation's building and 0.01563 in the Microsoft campus, respectively. From the two instances mentioned above, in the case that the value of
μ
_{AP}
within a concerned WLAN is more than 0.01, the corresponding WLAN is considered highdensity.
 3.2 Study of Green Clustering Algorithm in SEAR
SEAR is proposed by Jardosh as a demanddriven strategy to manage APs in highdensity WLANs efficiently. And it is a policybased method which can be tailored to achieve the performance desired by WLAN administrators. Moreover, based on some certain policies used, SEAR can conserve energy while the same performance is maintained as clients receive in its alwayson counterpart.
SEAR resides on the central controller of a centralized WLAN through which it can control all APs. SEAR is assumed to have complete knowledge of the physics position and status of all APs managing the WLAN to achieve the designed requirements efficiently and switch the APs on or off in accordance with the policy used. SEAR consists of four components which are green clustering algorithm, user demand estimation, topology management, and user association, as shown in
Fig. 2
[5]
.
Components of SEAR.
A green clustering algorithm forms AP clusters and selects a clusterhead AP for per cluster. SEAR uses green clustering algorithm as the initialization to provide necessary information for the further processing. The premise of green clustering is that a single AP from each of those clusters is sufficient to provide basic coverage to users in the vicinity of any AP within that cluster. As shown in
Fig. 3
, consider five APs (1 to 5) are placed within close proximity. Before applying green clustering all the five APs work in smaller transmitting powers. However, in case of green clustering deployed, AP with label 1 is able to provide coverage to the region while others are shut down. Moreover, the transmitting power of AP1 has been increased for extended coverage. Therefore, the five APs form a new cluster and AP1 is the clusterhead AP as shown in
Fig. 3
.
Illustration of cluster formation.
Besides, it is worth mentioning that the transmitting power of a net device is only a tiny part of the total power consumption. Taking Cisco WAP4410N WirelessN AP of S series for example, its transmitting power with single antenna is 13dBm to 17dBm (12.6 to 50.1 in mW), while this AP's total power consumption is about 10W during normal work. Therefore, even the transmitting power increases for satisfying the algorithm requirement, the impact on total power consumption could be ignored because the energy saving by poweringoff APs is much more significant.
In SEAR, green clustering is implemented in two steps which are neighborhood discovery and cluster formation, respectively.
In the first step of SEAR's green clustering, the APs need to work as a sniffing monitor and the central controller need to configure all the APs within the WLAN to the same channel for more than 1 min interval, even while the AP may be providing connectivity to clients. During that interval, each AP records the number and the signal strength of beacon frames from every other AP. If and only if the number and the signal strength are both no smaller than the predetermined thresholds, the two AP are assumed to be in very close proximity. By deploying this method, the number of neighbors within each AP's neighborhood is obtained and then we let
n_{i}
denote the number mentioned for AP
i
.
In the second step, similar to the algorithm suggested by Bejerano
[26]
,
[5]
utilizes a fast greedy clustering approach. In this step,
n_{i}
occurs as attribute value of AP
i
. To implement cluster formation, the maximum
n_{i}
is chosen first and the corresponding AP forms the first cluster .After that, a set as a cluster is formed,
i
is added into the set
R_{i}
as the first component of the cluster and at the meantime
i
is removed from all neighborhood sets of other APs. After
i
is added, all the APs
j
in the neighborhood of
i
are stepped through and added to the set
R_{i}
if and only if the new
j
is in the neighborhood set of every other AP already added to
R_{i}
. Once all the APs that satisfy the condition that being added to
R_{i}
, AP
i
is made the clusterhead of the cluster. Then the algorithm of cluster formation is iterated until all the APs in the WLAN have been added to some sets.
Once SEAR forms green clusters, the clusterhead APs remain poweredon by default, while the other ones in each cluster, which are called secondary APs, are supposed to be off for energy conservation. Moreover, the transmitting power of clusterhead APs needs to be increased to maintain the network coverage.
Green clustering algorithm of SEAR is measurementbased to form AP clusters which are in close proximity of each other. The neighborhoods can be varied based on the thresholds of signal strength and number of received beacon messages, and the thresholds directly affect the results of green clustering. In other words, if low thresholds are chosen, SEAR's green clustering algorithm forms smaller size of clusters which means smaller power saving. Conversely, high thresholds may results in the lack of the network coverage. The choice of thresholds is critical for SEAR's green clustering.
4. A New Green Clustering Algorithm
In Section III we illustrate about SEAR and its green clustering. To implement the initialization of the energy efficient strategy in highdensity WLANs, we propose a new green clustering algorithm (NGCA) with a completely different perspective and approach. In order to implement our method, we analyze and study the propagation model of a typical indoor environment to indicate the coverage of an AP, and then on the basis of the propagation models a new green clustering consisting of the faster procedure and the more accurate procedure, is proposed to form green clusters of APs.
 4.1 Estimation of APs' Coverage
As mentioned in Section III, a central controller has the complete knowledge of physics positions of all APs in the WLAN, and the coverage of AP is the evaluation index of our algorithm for future processing. The coverage region of an AP can be described as an area in which the Rx RSS (received signal strength) from the current AP is over a predetermined criterion, and the value determining the boundary of access service can refer to Rx sensitivity of some protocol. In order to specify network parameters, the WLAN we investigate is assumed as an IEEE 802.11b WIFI network, and typical Rx sensitivities for IEEE 802.11b are 86dBm at 1Mbps, 83dBm at 2Mbps, 79dBm at 5.5Mbps and 76dBm at 11Mbps, respectively. Therefore, for better network performance the area in which Rx RSS from an AP exceeds the biggest Rx sensitivity of 802.11b is considered to be in the coverage region.
NGCA usually works in indoor environments, and consists of two procedures which are for clustering fast and accurately, respectively. When few users are online or the traffic load is low, in order to maintain the basic network coverage which is measured by coverage of each AP, the fast procedure could supply a coarse result of AP clusters in a relatively short time, then the algorithm carries on to achieve a more accurate AP deployment for further power conservation. For different purposes of the algorithm, the coverage of an AP should be measured in different methods. Therefore, we introduce a simple and fast method based on the Friis free space equation for the fast procedure, and then employ a complex but accurate method based on raytracing and FDTD (finitedifferent timedomain) for the accurate one. First, the simple method (named simple modeling) would be presented as follow.
In the free space, the power received by a receiver antenna which is separated from a radiating transmitter antenna by a distance
d
is given by the Friis free space equation
where
P_{t}
is the transmitting power,
P_{r}
is the received power which is a function of the distance
d
,
G_{t}
is the transmitter antenna gain,
G_{r}
is the receiver antenna gain,
l
is the system loss factor not related to propagation (
l
≠1), and
λ
is the wavelength in meters.
The environment algorithm is generally concentrated in an indoor environment. Due to the complex propagation environment, the attenuation factor model is introduced and analyzed to estimate the value of coverage radius of APs. According to (2), considering of the propagation loss of EM wave, the path loss of EM wave in the band around 2.4 G is given by approximately
where
L
denotes the path loss and
n
is the attenuation factor which differs in different environments. Generally, in the relatively isolated environment,
n
is set 3.0 to 3.5. So the coverage radius
Rad
can be given by
And if the value of
P_{t}
is set to 15dBm,
Rad
can be considered as 30m.
For the fast procedure, the coverage of an AP is considered as a circle of which radius can be estimated according to (4). However, for future energy efficiency, a more accurate method to estimate the coverage should be employed. The coverage region can be measured with devices, and we have made a radio map consisting of RSS values from APs deployed in the building where our office resides (detailed in Subsection 5.2), but there are several serious problems to seek for the boundary of AP in this way, and some of the problems are that if the location or Tx power of some AP changes, or a new AP is deployed, the radio map might have to be rebuilt which makes the timeliness poor, so building a radio map, particular in a large area, is a hard work but with limited robustness and poor generalization. Therefore, for better exactness and robustness, a method for indoor propagation modeling (named complicated modeling) based on raytracing and FDTD is introduced.
Raytracing method is presented to evaluate the indoor wave propagation and penetration
[27]
. According to raytracing, waves from a Tx antenna could be modeled as ray tubes, and from geometrical optics, the Efield of the ray tube at Rx can be given by
where
denotes the Efield at a reference point
RP
_{0}
,
represent the reflection and transmission coefficient dyads along the whole path, respectively.
denotes the propagation phase variations and exponential losses for the ray contribution from
RP
_{0}
. From the conservation of energy flux in a ray tube,
SF
can be obtained as
where
A
_{0}
and
A
are the crosssectional areas at
RP
_{0}
and the filed point, respectively.
FDTD is presented by Kane Yee for numerical solution of Maxwell's Equations
[28]
. In FDTD, a space grid is introduced in which Efield components and Hfiled components at different directions are discretized, so each Efiled component is encircled by four Hfield components, and also each Hfiled component is encircled by four Efield components. Moreover, in time domain, E and Hfield components are also discretized arranging at regular intervals. According to FDTD, in a 3D scenario, for instance, Efiled component at direction x (
E_{x}
) can be given by
where
n
denotes time,
ε
and
σ
are material constants,
E
and
H
represent values of E and Hfiled, respectively, and propagation directions of EM waves are denoted by x, y and z in a rectangular coordinate system. Δ
x
, Δ
y
and Δ
z
are space increments in Yee grid,
i
,
j
and
k
are parameters to describe distances at direction x, y, and z, respectively. Δ
t
is the time increment. Analogously, components
E_{y}
,
E_{z}
,
H_{x}
,
H_{y}
and
H_{z}
can be obtained with Yee grid through FDTD technology. Therefore, with previous time filed, another field at adjacent nodes, electric and magnetic current sources, values of E and Hfield can be achieved at arbitrary point in Yee grid.
However, in FDTD, the space grid size must be a fraction of the wavelength for ensuring that over one increment the EM field does not change significantly. That means modeling indoor wave propagation in a larger area could be very difficult using existing equipment and the computation amount would be huge. Balancing between exactness and feasibility, a combination of raytracing and FDTD is introduced.
In a scenario of indoor environment illustrated by
Fig. 4
, the wave propagation between AP and Location D is investigated. The combination of raytracing and FDTD is that the propagation between AP and B, C and D is analyzed based on raytracing method, and the propagation between B and C is calculated on the basis of FDTD technique, similarly with the algorithm proposed in
[29]
. Every wall of the building is discretized into a unit cell (brick), Tx and Rx are added. The interaction between Tx and the bricks can be calculated iteratively according to (8), (9) and (10), and to simplify the explanation, vertical polarization with the three field components
E_{z}
,
H_{x}
and
H_{y}
is assumed. The derivation for horizontal polarization is analogous.
where
is the Hankel function of second kind,
denote the vectors to Tx and to the brick point, respectively.
k
is the wavenumber.
where
are the electric surfaces fields in the zdirection, and
is the surface normal vector of the brick.
Illustration of modeling indoor wave propagation.
And the analogous combinations of raytracing and FDTD have already been proved in
[29

31]
. Thus, for obtaining APs' coverage, it is unnecessary to configure all the APs within the WLAN to the same channel as in SEAR, and the experience of clients in the WLAN is guaranteed. In our algorithm, with the indoor propagation model, the central controller would update the information about the radio map in the WLAN which can be estimated and AP clusters will be formed on the basis of this data set.
 4.2 The Faster Procedure Based on Kmeans Algorithm
As mentioned above, NGCA could form green clusters based on access coverage of APs which is needed to be evaluated in an indoor environment. One simple but quick method for supplying coverage is based on the Friis free space equation, the other one which is a hybrid method consisting of raytracing and FDTD is more complex, timeconsuming but accurate. Therefore, in our algorithm, two parallel procedures are introduced. One, named the fast procedure, is for forming coarse results about AP clusters in a relatively short time. And the other one, named the accurate procedure, is for achieving a more accurate AP deployment. Moreover, both procedures would work on the radio map built by modeling methods discussed in Subsection 4.1. In order to obtain a solution fast,
K
means technique is employed.
K
means algorithm is a kind of simple and efficient clustering approach.With
K
means a Ddimension data set consisting of
N
samples can be divided into
K
categories by minimizing a criterion function
J
which be expressed by
where
r_{nk}
is a clustering index,
r_{nk}
= 1 and
r_{nj}
= 0 for
j
≠
k
.
μ
_{k}
is the cluster center of the
k
th cluster and ‖ • ‖ is an operator that calculates Euclid distance between
x_{n}
and
μ
_{k}
.
In order to apply
K
means the number of categories
K
should be given, and the first step of
K
means is to initialize a cluster center for each category at random.
K
means consists of Estep and Mstep. In Estep, on the basis of
r_{nk}
,
μ
_{k}
is generated following optimization criterion expressed by
In Mstep, according to
μ
_{k}
,
r_{nk}
is generated following optimization criterion.
K
means iterates Estep and Mstep until the value of the criterion function
J
is smaller than a very small number
ξ
, and
μ
_{k}
is the ultimate cluster center of the
k
th category.
The faster procedure of our algorithm is based on
K
means, each AP in the WLAN is regarded as the sample to be classified while the tradeoff of this approach is the number of categories
K
which is problemspecific.
To begin the procedure we choose a bigger
K
and the method is discussed in the next section where we present a specific scenario (in Subsection 5.1).
The faster procedure of NGCA is the following.
(1) Initialization:

(a) Obtain the modified positions of all APs in the WLAN.

(b) Calculate and determine the number of categoriesK.
(2) Generate cluster centers for
K
categories at random.
(3) Apply
K
means algorithm, and obtain the results of clustering expressed as
R_{K}
.
(4)
WHILE
the condition of network coverage is met:

(a) Step through all the samples inRKand attempt to remove a single AP while keeping others APs reside inRK, and check the condition of network coverage. The condition of network coverage is the constrain condition of our new algorithm. In order to fulfill the constrain condition, we mesh the region, calculate the area covered by clusterhead APs, and compare with the total area. If the difference between the two areas is a very small number, we consider the condition of network coverage is met.

(b)IFany of the conditions calculated is met,THENremove the corresponding AP fromRKand increase the loop counter.

IFall of the conditions calculated are not met,THEN GOTOStep 5.
(5)
END WHILE
(6) After removing some APs,
R_{K}
is the result obtained with the faster procedure.
 4.3 The More Accurate Procedure Based on EA
In this procedure, we form AP clusters in another different perspective from both the approaches in our faster algorithm and in SEAR. In the faster procedure, we obtain results of green clustering with a bigger number first, and we express the results consisting of a set of clusterhead APs as
R_{K}
. Then we remove APs from
R_{K}
. In term of the number of trail clusterhead APs, the more accurate step is an opposite procedure during which we begin the approach with a smaller number of clusters, and then step up the number, while in the faster procedure a larger number is predetermined and the number is stepped down.
1) Problem description
In the more accurate procedure, we regard the area covered by the WLAN as the boundary for feasible solutions, and a set of trial clusterhead APs as a feasible solution
R
. And corresponding APs' physics positions express as
Loc
. The problem that green clustering attempts to handle can be addressed and define as
where
S_{i}
and
S_{j}
are the cover area of the
i
th AP and the
j
th AP, respectively, which are both in the set of a feasible solution, and
i
≠
j
.
represents overlap area, and
S
_{basic}
represents the condition of network coverage.
We adapt the basic problem and transform it into a matter of multiple objective optimization which can be expressed as
where
R
is a feasible solution consisting of a set of trial clusterhead APs,
objfunc
1(
Loc
) denotes the function that calculates the coverage with
Loc
. As this is a minimizing process the results
Scale
is handled by (1−
Scale
)abs which means the area not covered by
R
. While
objfunc
2(
Loc
) represents the function that calculates the overlap area, Ω denotes the region of the WLAN, and
R
∈ Ω means that the location of each AP in
R
is reasonable.
2) EA in the new algorithm.
We adapt the basic problem and transform it into a matter of multiple objective optimization
[32]
. Similar with the faster procedure, the more accurate procedure forms green clusters also based on the radio map. The methods to build a radio map here are measuring and simulating, but in both methods RSS values obtained at reference points are predetermined. According to (13), the working mechanism to solve the transformed problem would be optimizing processes over locations, so the selection of stepsize would be critical for optimization and convergence time. Therefore, an optimization algorithm which could support multistep sizes should be introduced. In general, different step sizes should be applied to different data sets, and most methods implement multistep size mechanisms through independent calculation processes rather than one execution procedure, so there would be no relations amongst results obtained with different step sizes during calculating. However, interactions among results are also critical for optimization and convergence time. In order to handle the new problem, we adapt and apply Evolutionary Algorithm (EA) in which multistep sizes can be involved to subpopulations, and interactions among results can be implemented through Reinsertion, Migration and Competition amongst subpopulations
[33]
.
EA is a stochastic search method that mimics the metaphor of natural biological evolution and models natural processes, such as selection, recombination, mutation, migration, locality and neighborhood
[34]
. To handle the new problem we adapt some processes in EA, and introduce a multipopulation model. The structure of multipopulation EA is shown in
Fig. 5
.
The structure of multipopulation EA.
In singleobjective problems, rankbased fitness assignment is involved, but in our problem there are two criteria to be considered in order to evaluate the quality of an individual. The superiority of one feasible solution over the other can be decided by comparing the two solutions. It can be carried out following Pareto Dominance.
Definition 1
(Pareto Dominance): A vector
μ
= (
μ
_{1}
, ⋯,
μ_{k}
) is said to dominate
ν
= (
ν
_{1}
, ⋯,
ν_{k}
) (denoted by
μ
°
ν
) if and only if
μ
is partially less than
ν
, i.e., ∀
i
∈ {1, ⋯,
k
},
μ_{i}
≤
ν_{i}
∧ ∃
i
∈ {1, ⋯,
k
}
μ_{i}
˃
ν_{i}
.
If in a set of feasible solutions which can be regard as Pareto Optimal Set, a vector is not dominated by any other vector, it is nondominated. All the nondominated vectors in the Pareto Optimal Set can form a front, and in the general case, it can be considered that these nondominated points produce the Pareto Front. The purpose of applying multiobjective algorithm is to achieve the Pareto Front approximately.
In order to apply EA in NGCA for better performance, we adapt some processes which are shown as follow.
(1) The structure of EA. The population is divided into five subpopulations and in each subpopulation some parameters and methods of EA, such as mutation rate, mutation range and the approach of recombination, are accordingly different.
(2) Selection and recombination. In terms of the new problem the coverage is considered as a more important property than the overlap. However, it is difficult to assign them weights accurately. To deal with that, we introduce bias as an assistant approach to our method. We use a repository
REP
to store nondominated vectors and the corresponding sets of APs. In most EAs, individuals to produce offspring are chosen from population, and offspring are produced according the rule expressed as
[35]
where
a_{i}
is a scaling factor and chosen uniformly at random over an interval [−
d
,1 +
d
] for the
i
th dimension, and a value of
d
= 0.25 ensures that the variable area of the offspring is the same as the variable area spanned by the variables of the parents statistically.
Val_{i}
is the variable of the
i
th dimension from offspring,
Val_{i}
^{P}
^{1}
and
Val_{i}
^{P}
^{2}
are the variables from Parent1 and Parent2, respectively. In the new algorithm, a scheme is introduced to apply bias. If the event of bias is triggered, offspring are produced according the rule expressed as
where
Val_{i}^{P}
is the variable of the parent chosen from population, and
REP
[
h
] is a value taken from the repository. As nondominated vectors are stored in
REP
, we repeatedly bisect the range in each objective to obtain several hypercubes. Such hypercubes have as many components as objective functions. Those hypercubes containing more than one individuals are assigned a fitness equal to
x
/
n
, where
n
is the number of individuals within the corresponding hypercube and
x
is a number (we use
x
= 1 here). We decrease the fitness of those hypercubes containing more individuals and it can be seen as a form of fitness sharing
[36]
. Then, we apply roulette wheel selection
[37]
and tournament selection
[38]
with the fitness values to select the hypercubes within which
REP
[
h
] is selected at random.
(3) Mutation. In each subpopulation different mutation rate and range are applied to maintain genetic diversity. At the beginning of the search, the mutation operator attempts to explore all the new individuals. Then, the mutation rate might be decreased in accordance with the number of generations. And, as a consequence, the mutation range is affected by the rate. The pseudo code of the mutation operator applied in the new algorithm is the following.
%
individual
= individual to be mutated
%
dims
= number of dimensions
%
currentgen
= current generation
%
totalgen
= total number of generations
%
mutrate
= mutation rate
%
mutrange
= mutation range
function
mutation_operator(
individual
,
dims
,
currentgen
,
totalgen
,
mutrate
)
IF
flip ((1 −
currentgen
/
totalgen
)
^{1/mutrate2}
),
THEN
whichdim
= randpm(0,
dims
− 1)
mutrange
= (
upperbound
[
whichdim
] −
lowerbound
[
whichdim
]) • (1 −
currentgen
/
totalgen
)
^{1/mutrate2}
ub
=
individual
[
whichdim
] +
mutrange
lb
=
individual
[
whichdim
] −
mutrange
IF
ub
˃
upperbound
[
whichdim
],
THEN
ub
=
upperbound
[
whichdim
]
IF
lb
˂
lowerbound
[
whichdim
],
THEN
lb
=
lowerbound
[
whichdim
]
individual
^{NEW}
[
whichdim
] = RealRandom(
lb
,
ub
)
END IF
END function
3) The more accurate procedure based on EA.
We mesh the WLAN region to calculate the coverage and overlap, and more specifically, we represent the coverage and overlap of a grid area with the status of a point within it. As shown in
Fig. 6
, a dot circle represents the coverage area of an AP, and each point amongst A, B, C and D denotes a grid area, respectively. For example, the gird area denoted by A is covered by two APs all together, and the property of coverage and overlap within point A are 1 and 1, respectively. Similarly, the values are 1 and 2 for point B, 1 and 0 for point C, 0 and 0 for point D. The tradeoff for meshing is the choice of the grid number which affects the operation speed directly, so we introduce the concept of resolution for meshing. With low and high resolutions, coarse and precise results can be obtained.
Illustration of calculating coverage and overlap.
The more accurate procedure of NGCA is the following.
(1) Initialization:

(a) Obtain the physical positions of all APs in the WLAN.

(b) Calculate and determine the original number of green clustersN, and set an upper boundNubforN.

(c) Set a smaller number of total generations for EA expressed astotalgen1, a low resolution and a smaller ratioξ1which represents the uncovered area.
(2)
WHILE
totalgen
1 has not been reached.

(a) Apply the modified EA and the objective values are calculated with the low resolution.

(b) Increase the counter of generations.
(3)
END WHILE
(4) Evaluate the results with
ξ
_{1}
.

(a)IFany of feasible solutions' coverage is no bigger thanξ1,THEN GOTOstep 5.

(b)IFall of feasible solutions' coverage is bigger thanξ1, andNhas not reachedNub,THENN+ + andGOTOStep 2.

(c)IFall of feasible solutions' coverage is bigger thanξ1, andNhas reachedNub,THENthe algorithm fails. To avoid this situation, we recommend a biggerNub, and in the new green clustering we handle this by combining the faster procedure, and we will discuss the approach in the next subsection.
(5) Initialization for another EA processing:
Set a high resolution and a bigger number of total generations for the current EA expressed as
totalgen
2, and
totalgen
2 ≥ 2 ×
totalgen
1 is recommended.
(6)
WHILE
totalgen
2 has not been reached.

(a) Apply the modified EA and the objective values are calculated with the high resolution.

(b) Increase the counter of generations.
(7)
END WHILE
(8) Set a bigger ratio
ξ
_{2}
, the value of
ξ
_{2}
is problemspecific and
ξ
_{2}
≤
ξ
_{1}
/ 5 is recommended. With
ξ
_{2}
the feasible solutions in
REP
whose first objective value (calculated by
objfunc
1(
Loc
)) is no bigger than
ξ
_{2}
, are acceptable. Once acceptable solutions are obtained, we choose the solution from the acceptable solutions which is most close to the acceptable hyperplane
ObjVal
1 =
ξ
_{2}
as the ultimate feasible solution
 4.4 A New Green Clustering Algorithm
The new green clustering algorithm (NGCA) consists of modeling the environment, analysis of APs' coverage, the faster procedure and the more accurate procedure. For an illustrative purpose, the structure and operation mechanism of the proposed method are shown in
Fig. 7
.
The structure and operation mechanism of NGCA.
In
Fig. 7
, Loc. of AP and RP denotes the data base which stores physical positions of APs and RPs (reference point), Proc. F is short for the faster procedure, and Proc. A is short for the more accurate procedure. Once Proc. F has been executed, results
R_{F}
consisting of feasible APs can be obtained. Similarly, the results of Proc. A expressed as
R_{A}
can also be obtained, and the APs in
R_{A}
are the ultimate green clusterhead APs. In
Fig. 7
, OPR. I denote operations of increasing the transmitting power of APs in the set of
R_{F}
and then poweringoff APs in
R_{F}
^{ð}
, and OPR. II denote operations of poweringon APs with maximum transmitting power in
R_{F}
^{ð}
⋂
R_{A}
and then poweringoff APs in
R_{F}
⋂
R_{A}
^{ð}
. After OPR. II, clusterhead APs are formed, and the results of NGCA are obtained.
Once Proc. F obtains results, information interaction occurs between Proc. F and A. Proc. F can determine the number of clusters, this number is set as the upper bound of green cluster number used in Proc. A, and as shown in
Fig. 7
the processing of interaction expresses as the vertical dot line from the results of Proc. F towards Proc. A.
Going through procedures and operations in NGCA, the green clusters can be obtained in a different but new perspective.
5. Simulation Results and Analysis of New Green Clustering Algorithm
In this section we carry on simulations to verify the new green clustering algorithm (NGCA) proposed in this paper. Firstly, an ideal model is introduced and simulation is conducted in this model, then we model our office as an actual scenario and run NGCA on it. Besides, the green clustering algorithm in SEAR is presented as a comparison in the last subsection.
 5.1 Simulation and Analysis in the Ideal Model
The deployment of APs in an ideal enterprise (where deployed highdensity WLAN) is modeled for our simulation experiment first. The size of experimental region is 100 m × 100 m, and the deployment of APs is shown in
Fig. 8
where an empty circle denotes an AP and the number nearby is the label of the corresponding AP. According to (1), the value of
μ
_{AP}
in our simulation experiment is 0.0081 and deploying APs (where distance in between is 10m) can be considered as a highdensity WLAN. As experimental setup, we need to set an indoor maximum coverage radius of AP expressed by
Rad
. Assuming that the Rx sensitivity is 76dBm, the maximum indoor propagation distance is about 31.62m according to (3), and in the simulation experiment of this subsection,
Rad
is set to 30m.
Deployment of APs in simulation experiment.
In Proc. F,
K
means is applied and the number of original categories
K
is determined as following. In ideal conditions, to cover an experiment area which is 100 m × 100 m, only
APs are needed, though it is unreachable in practice. Supposing that the area as a piece of paper, and folding the paper in half horizontally and vertically in turn. Then repeat these processes until the folded area can be fully covered by one single AP with
Rad
, and denoting the times of folding is
n
, 2
^{n}
is the number we looking for. Therefore,
K
is 16 for our simulation.
In Proc. A, as discussed in the above section, the upper bound of green cluster number is derived from the results of Proc. F. The first objective value
ξ
_{1}
for low resolution is set to 0.01, and
ξ
_{2}
for high resolution is set to 0.002. And the low resolution is set to 100 × 100 which means the experimental region is divided into 100 × 100 meshes, while the high resolution is set to 1000 × 1000.
According to
Fig. 7
, to simulate NGCA, the first step is to decide the coverage area of an AP. In the simulation, the AP deployment is shown as
Fig. 8
, and it is an experimental scenario in which no walls, doors or furniture exist, and that means the coverage can be estimated through the radius. Then, Proc. F and A would be carried on simultaneously. Proc. F completes faster than Proc. A, and the results of Proc. F are shown in
Fig. 9
. where a circle denotes a clusterhead AP, and the number nearby with the dotted line around it are the AP's label and its coverage border, respectively.
Fig. 9
shows that to cover such a region 9 APs are needed according to Proc. F. At this point, the number of clusters obtained is passed to Proc. A as the upper bound of green cluster number. After passing parameters, Proc. F completes, and Proc. A carries on. In EA, feasible solutions are stored in the repository
REP
, after the total generations are reached, the feasible solutions are shown in
Fig. 10
. where a solid red circle denotes a nondominated solution, a blue asterisk denotes a dominated solution and the dotted fold line is the approximate Pareto Front.
ξ
_{1}
and
ξ
_{2}
are the thresholds for our modified EA, x =
ξ
_{1}
and x =
ξ
_{2}
are acceptable lines. The nondominated solutions which are on the left of x =
ξ
_{2}
are acceptable solutions, and the one close to x =
ξ
_{2}
most is the ultimate feasible solution which is shown in
Fig. 11
.
Results of PROC. F, in which 9 APs are poweredon.
Illustration of feasible solutions, the objectives are to minimize uncovered and overlap rates.
Results of NGCA, in which 8 APs are poweredon and 88.89% of energy can be saved.
According to
Fig. 11
, it shows that to cover such a region, 8 APs are needed deriving from Proc. A. Concerning of coverage rate, a comparison is introduced between Proc. F and A, and the results are shown in
Fig. 12
.
Illustration of the comparison between Proc. F and A.
Fig. 12
clearly illustrates that Proc. A maintains coverage with less APs than Proc. F. Thus far, Proc. A is finished and after some operations the new algorithm is completed.
In traditional WLANs, to cover our experimental area, all the 81 APs are poweredon. With the new approach, 8 APs are needed. As the first step of energy efficient strategy, about 90% energy is saved with NGCA.
 5.2 Simulation and Analysis in the Actual Model
In the above subsection, simulations based on an ideal model have been conducted, and the validity and efficiency of NGCA have been proved. In this subsection a practical model will be introduced, and for verifying the proposed algorithm, 27 AP are deployed on the floor where our office resides as shown in
Fig. 13
. The area of our floor is about 1875m
^{2}
, and according to (1), the value of
μ
_{AP}
is 0.0144.
The floor layout and AP deployment of our office, and the numbers denote doors.
The purpose of the proposed algorithm is that when few users are online or the traffic load is low, for energy efficiency NGCA classifies AP in the WLAN, and remains clusterhead APs on, powers off secondary APs while the basic network coverage of corridors and offices can be maintained. Unlike discussions in the above subsection, the model introduced to decide the coverage of an AP here is more complex and practical, so it is not appropriate to estimate the path loss with (4) and measure the coverage area of AP with a reference circle. Therefore, we select some locations on our floor as reference points (RP), measure and record values of Rx RSS at each RP as shown in
Fig. 14
, and with these data a radio map can be built. And, with either measured or estimated radio maps, the coverage region of an AP can be evaluated.
Illustrations of RPs on corridors.
Measured RSS at RPs from AP deployed in Room1202 with a sapling interval of 0.5 m.
For instance,
Fig. 15
illustrates RSS at RPs received from the AP deployed in Room1202, where values of RSS are represented through different colors, and the AP is denoted by a solid blue triangle. As the constraint of authorization, RSS values are measured and recorded in 3 dedicated offices, and RPs are set unbalanced as all offices are furnished with tables, chairs, computers and other laboratory furniture, which makes only sampling RPs in aisles are available, as shown in
Fig. 15
. But in corridors, RPs are setup homogeneously with a 0.5m sampling interval. Therefore, with the measured radio map, the coverage region of an AP can be evaluated. Moreover, for better accuracy and robustness, the method of complicated modeling is introduced. According to the investigation and discussion in Subsection 4.1, RSS at an arbitrary location on our floor from each AP can be estimated. In order to compare, RSS data of AP in Room1202 is demonstrated as the example shown in
Fig. 16
.
Calculated RSS on our floor from AP deployed in Room1202 with a sampling interval of 0.1 m.
To be specific, RSS has been estimated at almost each location on our floor including all the offices, corridors, the hall, staircases and even W.C., and the 3 blank areas denote elevator shafts where the network coverage is meaningless. It is worth noticing that boundaries of dark blue which denote values of RSS less than 80dBm are arcshaped. In order to reduce unnecessary calculation, it is assumed that if the distance between an AP and a RP exceeds 30m, the value of RSS at this RP from the AP is concerned as a value between 80 and 100dBm which is similar to the noise power setting in simulations, thus boundaries of RSS values less than 80dBm present arcshaped.
RSS measured and estimated from the AP deployed in Room1210 are shown in
Fig. 17
at different distances. The estimating method could provide more RSS information. Measured RSS changes severely, particularly when RSS values are smaller, but estimated RSS is more stable. And with the increase of distance, the number of RPs at one same distance grows and wave propagation between the AP to each RP becomes more complex, such as the number of walls and doors to be through may be diverse. Due to the more diverse propagation environment, RSS in a small range could vary a lot, and the increased distance between AP and RP would contribute to this phenomenon which is proved by both blue and red curves of measured and calculated RSS.
Comparison of measured RSS and estimated results, and in order to reduce unnecessary calculation, when the distance between RP and AP exceeds 30m, RSS value is assigned between 90 and 100dBm.
In the method of sampling model which is the preprocessing of Proc. F, estimation of AP's coverage is simply based on coverage radius. However, in the complicated modeling which is the preprocessing of Proc. A, estimation of AP's coverage is based on modeling indoor wave propagation. And in Proc. A, in order to determine if a predetermined unit area is covered by some AP, the WLAN region is meshed to form several grids. As the value of sampling interval in modeling indoor propagation is smaller, the grid in modified EA can be expressed as relations amongst RPs within it (as shown in
Fig. 18
). For instances, if RSS from an AP at any RP in the grid is less than the coverage condition this grid would be consider as uncovered by this AP, or conversely, the grid is concerned to be covered if RSS at any RP meets the condition. As the area of a grid is relatively small in term of the WLAN region, the ways to decide a grid's network coverage have little impact on results of NGCA. And in our simulation, if the mean value of RPs' RSS in a grid meets the coverage condition, the gird would be regarded as being covered by the corresponding AP.
Illustration of relations between RPs (denoted by solid red diamonds) built in complicated modeling, and the grid (denoted by the square) in modified EA.
Through the simple modeling and complicated modeling, the coverage of an AP can be determined, and with the coverage information, NGCA can generate appropriate AP clusters. Similar with the above subsection, results of Proc. F is presented first.
In this actual model, the coverage radius
Rad
for Proc. F should decrease as the complex indoor environment, and
Rad
is set to 15m. According to the work mechanism of Proc. F, similar with the above subsection, results of coarse clusters are shown in
Fig. 19
.
Results of Proc. F, in which 14 APs are poweredon.
With the results obtained from Proc. F, the upper bound of AP clusters for Proc. A is set to 14, and it is assumed that simulation parameters for Proc. A in the actual model are as same as those in the ideal model. For each feasible solution which represents a set consisting of APs, the network coverage conditions should be calculated of which the results could be concerned as objects. And in this practical model, the network coverage conditions are evaluated through that RSS at all RPs in complicated modeling from each AP in the feasible solution is estimated. According to the RSS values RPs covered by this AP can be determined, and all APs in the feasible solution will be traverse to find the uncovered and overlap rates under the current conditions. Iterating the steps in accordance with the working mechanism of Proc. A, the results, which are also the ultimate solutions of NGCA, can be achieved, as shown in
Fig. 20
.
Results of NGCA obtained in the actual model, in which 9 AP are poweredon and 66.7%of energy can be saved.
Results of NGCA show that 9 APs at locations specified by our algorithm are enough to provide basic network coverage in the scenario modeled as the floor where our office resides, so 18 AP can be poweredoff for energy efficiency when few users are online or the traffic load is low, which means about 66.67% of power can be saved. In order to verify the results, RSS values from these 9 APs are measured and recorded, and the results are shown in RSS values from these 9 APs are measured and recorded, and the results are shown in RSS values from these 9 APs are measured and recorded, and the results are shown in
Fig. 21
.
RSS measured on our floor, and only the maximal RSS at each RP is recorded.
In
Fig. 21
, only the maximal RSS received among the 9 APs at each RP is recorded. Therefore, according to the measurement, the basic network coverage is maintained by the 9 APs NGCA specified when other APs are poweredoff for energy efficiency.
 5.3 Comparison and Analysis
In Subsection 5.1 and 5.2, simulations have been conducted to verify the validity and efficiency of NGCA in an ideal scenario and an actual scenario modeled as our offices, respectively, in the ideal model 88.89% of energy is saved, and 66.67% is saved in the practical model. Moreover, in this subsection, the green clustering algorithm in SEAR
[5]
is introduced and compared.
In
[5]
, in order to implement green clustering, Jardosh conducts experiments in their building, and the building layout and AP deployment are shown in
Fig. 22
.
The floor layout and AP deployment of the comparison task, where on 2 floors, each of which is 50 m × 20 m , 14 APs are deployed.
In
Fig. 22
, 14 APs are deployed in their building, and 7 AP clusters are formed according to their green clustering algorithm, which means 50% of energy is saved, while the results of NGCA are 88.89% in the ideal model and 66.67% in the actual model. Therefore, only in term of the saved energy ratio, our NGCA outperforms their algorithm, especially results in the ideal model. However, the comparison of ratios seems to be unfair and also not convincing due to the different indoor layouts and wave propagation environments. For clarifying issue about the disadvantage of only comparing saved energy ratios, a theoretical example is presented. It is assumed that in an office which is 10 m × 10 m, 100 APs are deployed there, and 99 APs can be poweredoff. Therefore, 99% of energy is saved. However, in this assumption the number 99% cannot reflect the better performance as the scenario is too simple.
In order for fairness, a parameter which can describe the gain of algorithms in different indoor environments to a certain extend is introduced, and the parameter
θ
can be defined as
where
r
_{SAVED}
denotes the ratio of saved energy,
μ
_{AP}
is the parameter in (1) to describe the density of APs, and
n
is the attenuation factor in (3) to demonstrate different environments. So according to (16),
θ
can be calculated in different scenarios, and a bigger value of
θ
denotes the better performance of an algorithm, so
θ
can be introduced as the algorithm gain to measure the performance of different green clustering algorithms. Firstly, we begin with
θ
in the theoretical model.
In the theoretical model,
μ
_{AP}
is 1, and as in a simple wave propagation environment
n
is set to 3, so
θ
is 2.97.
In the experiment environment of SEAR, 14 APs are deployed on 2 floors. In order to calculate
μ
_{AP}
, the area of experiment
S
should be determined first. It is considered that
S
is assigned with only one floor's area, as APs in our simulations can also provide network coverage for upstairs and downstairs, so for uniformity, only the area of one floor is taken into consideration for each simulation experiment. Therefore,
μ
_{AP}
here is 0.014, and
n
is set to 3.5, which makes
θ
equal to 125.
And then, referring to our simulation in the ideal model,
r
_{SAVED}
is 88.89%,
μ
_{AP}
is 0.0081, and
n
is set to 3, so
θ
is 329.22 which is bigger than
θ
of SEAR.
Finally,
θ
of our simulation in the actual model is calculated.
r
_{SAVED}
is 66.67%,
μ
_{AP}
is 0.0144 which is similar to the AP density in SEAR, and
n
is 3.5 as same as the attenuation factor in SEAR, and the value of
θ
is 162.05 which is also bigger than
θ
of SEAR.
According to these values of
θ
which are environmentspecified, the unfairness of comparing only ratios of saved energy can be proved and surmounted, and both in terms of the saved energy ratio and algorithm gain, the performance of NGCA is better provably.
6. Conclusion
Highdensity WLANs are deployed in more and more enterprise offices and college campuses at present. To ensure network coverage, all the APs in the WLANs are poweredon and this causes huge energy wastage. In this paper, the energy efficient strategy is discussed and a new green clustering which is an innovative algorithm of the strategy is proposed.
In this paper, we study the energy efficient strategy and the green clustering algorithm in SEAR. Theoretically, the green clustering in SEAR is a kind of greedy algorithm. And it has to configure all APs to a same channel compulsively and keeps status for more than 1 minute in order to apply those APs within the WLAN, even while the APs may be providing connectivity to clients meantime, which could severely impact the experience of terminals.
While in the new green clustering algorithm, with a different method to form AP clusters, it is unnecessary for the central controller to configure all APs to a same channel initially, which, to same context, guarantee the performance and facilitate the end users.
Then, we propose a new green clustering algorithm (NGCA) in a completely different perspective. The two main components of our approach are the faster procedure (Proc. F) based on
K
means and the more accurate procedure (Proc. A) based on EA. The two procedures are processes in parallel for different designed requirements, and meantime there is information interaction in between. In Proc. A, for better performance in the new algorithm, we adapt Evolutionary Algorithm. Population is averagely divided into 5 subpopulations for applying different parameter settings, and a repository
REP
is introduced to store feasible solutions obtained by EA. With
REP
additional operations for selection and recombination is introduced, and also a new operator for mutation is applied.
Finally, simulations of NGCA are clearly presented in both ideal model and actual model, besides the comparison with an existing green algorithm is introduced as well. The results of the simulations verify the feasibility of NGCA and show that the new approach can save about 90% energy consumption in the ideal scenario and 67% in the actual scenario meanwhile coverage is maintained during periods when few users are online or the traffic load is low.
The green clustering algorithm is proposed as the first method of energy efficient strategy in highdensity WLANs in this paper. The algorithm will be the foreshadowing for future study about energy efficient strategy in which the optimization of clusterhead APs' transmitting power will be concerned, and NGCA will be supplemented comprehensively further. After green clustering, the mechanism of estimating user demand based on Markov Chain Model and queuing theory will also be studied, and an access selection based on IEEE 802.11 PCF for energy efficiency in highdensity WLANs will be proposed in the near future.
BIO
Yang Lu received his B.S. and M.S. in information and communication engineering from Harbin Institute of Technology, Harbin, China, in 2007 and 2011, respectively. He is currently working toward the Ph.D. degree with School of Electronics and Information Engineering, Harbin Institute of Technology. His research interests include energy efficient strategy in highdensity wireless LANs and networking technology in cognitive radio.
Xuezhi Tan received his B.S., M.S. and Ph.D. from Harbin Institute of Technology, Harbin, China, in 1982, 1986 and 2005, respectively. From Oct.1988 to Mar. 1990, he was a visiting scholar with Kyoto University, Kyoto, Japan. He is currently a professor with School of Electronics and Information Engineering, Harbin Institute of Technology. He is a Senior Member of Chinese Institute of Electronics and Chinese Institute of Communication. He has published more than 70 papers in international journals. His research interests include wireless communication, digital trunking communication, and cognitive radio.
Yun Mo received the B.S. degree from Beijing Technology and Business University, Beijing, China, in 2009, and the M.S. degree from University of Melbourne, Melbourne, Australia in 2011, respectively. He is working currently toward the Ph.D. degree with the School of Electronics and Information Engineering, Harbin Institute of Technology. His current research interests include pattern recognition, machine learning and indoorpositioning.
Lin Ma received his B.S., M.S. and Ph.D. in communication engineering from Harbin Institute of Technology, Harbin, China, in 2003, 2005 and 2009, respectively. In 2009, he joined Communication Research Center of Harbin Institute of Technology. His current research activities are in wireless LAN networking, indoor positioning and indoor navigation.
(2005)
Aruba selected by Microsoft for next generation wireless LAN
http://www.arubanetworks.com/news/release/2005/06/13
Dartmouth College WLAN
http://crawdad.cs.dartmouth.edu
Jardosh A. P.
,
Iannaccone G.
,
Papagiannaki K.
,
Vinnakota B.
“Towards an energystar WLAN infrastructure”
in Proc. of HotMobile
February 2627, 2007
vol. 15, Article (CrossRef Link).
85 
90
Jardosh A. P.
,
Papagiannaki. K.
,
Belding E. M.
,
Almeroth K. C.
,
Iannaccone G.
,
Vinnakotan B.
2009
“Green WLANs: Ondemand WLAN infrastructures”
Mobile Networks and Applications
Article (CrossRef Link).
14
(6)
798 
814
DOI : 10.1007/s1103600801238
Holland J. H.
1975
“Adaptation in natural and artificial systems”
in The University of Michigan Press
Alessandro D.
,
Moret S.
,
Tonello N.
“Green hybrid FMT for WLAN applications”
in Proc. of WD
October 2022, 2010
Article (CrossRef Link).
1 
5
Miliotis L.
,
Apostolaras V.
,
Korakis A.
,
Tao T.
,
Tassiulas Z.
“New channel allocation techniques for power efficient WiFi networks”
in Proc. of PIMRCW
September 2630, 2010
Article (CrossRef Link).
347 
351
Rabaey J.
“The standby power challenge: Wakeup receivers to the rescue”
in Proc. of VLSITSA
April 2729, 2009
Article (CrossRef Link)
42 
Marsan M. A.
,
Chiaraviglio L.
,
Ciullo D.
“A simple analytical model for the energyefficient activation of access points in dense WLANs”
in Proc. of ICEECNE
April 1315, 2012
Article (CrossRef Link).
159 
168
Chen Y.
,
Yang Q.
,
Yin J.
,
Chai X.
2006
“Powerefficient accesspoint selection for indoor location estimation”
IEEE Trans. on Knowledge and Data Engineering
Article (CrossRef Link).
18
(7)
877 
888
DOI : 10.1109/TKDE.2006.112
Kushki A.
,
Plataniotis K.
,
Venetsanopoulos A.
2007
“Kernelbased positioning in wireless local area networks”
IEEE Trans. on Mobile Computing
Article (CrossRef Link).
6
(6)
689 
705
DOI : 10.1109/TMC.2007.1017
Kushki A.
,
Plataniotis K. N.
,
Venetsanopoulos A. N.
2010
“Intelligent dynamic radio tracking in indoor wireless local area networks”
IEEE Trans. on Mobile Computing
Article (CrossRef Link).
9
(3)
405 
419
DOI : 10.1109/TMC.2009.141
Fang S. H.
,
Lin T. N.
,
Lin P. C.
2008
“Location fingerprinting in a decorrelated space”
IEEE Trans. on Knowledge and Data Engineering
Article (CrossRef Link)
20
(5)
685 
691
DOI : 10.1109/TKDE.2007.190731
Kang Y.
,
Lim S.
,
Yoo J.
,
Kim C.
2011
“Design, analysis and implementation of energyefficient broadcast MAC protocol for wireless sensor networks”
KSII Trans. on Internet and Information Systems
Article (CrossRef Link).
5
(6)
1113 
1132
DOI : 10.3837/tiis.2011.06.002
Lim S.
,
Kang Y.
,
Jeong J.
,
Kim C.
2012
“Design, analysis and evaluation of a new energy conserving MAC protocol of wireless sensor networks”
KSII Trans. on Internet and Information Systems
Article (CrossRef Link).
6
(12)
3046 
3060
Zuo Y.
,
Ling Z.
,
Liu L.
2012
“Energyefficient lowdelay TDMA scheduling algorithm for industrial wireless mesh networks”
KSII Trans. on Internet and Information Systems
Article (CrossRef Link).
6
(10)
2509 
2528
Kim D. W.
,
Park T.
2011
“An energy efficient MAC protocol providing guaranteed service for wireless sensor network”
KSII Trans. on Internet and Information Systems
Article (CrossRef Link).
5
(1)
Kang S.
,
Lee S.
,
Ahn S.
,
An S.
2012
“Energy efficient topology control based on sociological cluster in wireless sensor networks”
KSII Trans. on Internet and Information Systems
Article (CrossRef Link).
6
(1)
361 
380
Oak J.
,
Choi Y.
,
Park W.
2012
“EPMAC: Early preamble MAC to achieve low delay and energy consumption in duty cycle based asynchronous wireless sensor networks”
KSII Trans. on Internet and Information Systems
Article (CrossRef Link).
6
(1)
2980 
2991
Zhang Y.
,
Long H.
,
Peng Y.
,
Zheng K.
,
Wang W.
2013
“Useroriented energyand spectralefficiency tradeoff for wireless networks”
KSII Trans. on Internet and Information Systems
Article (CrossRef Link).
7
(2)
216 
233
Zhu J.
2013
“Energy efficiency analysis of cellular downlink transmission with network coding over Rayleigh fading channels”
KSII Trans. on Internet and Information Systems
Article (CrossRef Link).
7
(3)
456 
468
Wu Y.
,
Deng S.
,
Huang H.
2013
“Energyefficiency joint control of epidemic routing in delay tolerant networks”
KSII Trans. on Internet and Information Systems
Article (CrossRef Link).
7
(2)
234 
252
Eslaminejad M.
,
Razak S. A.
,
Ismail A. S. H.
2012
“Eedars: An energyefficient dualsink algorithm with role switching mechanism for eventdriven wireless sensor network”
KSII Trans. on Internet and Information Systems
Article (CrossRef Link).
6
(10)
2473 
2492
(2006)
Forrester research
http://www.forrester.com
Bejerano Y.
2002
“Efficient integration of multihop wireless and wired network with QoS constrains”
in IEEE/ACM Trans. on Networking
Article (CrossRef Link).
12
(6)
1064 
1078
DOI : 10.1109/TNET.2004.838599
Yang C. F.
,
Ko C. J.
1998
“A ray tracing method for modeling indoor wave propagation and penetration”
IEEE Trans. on Antennas Propagat.
Article (CrossRef Link).
46
907 
919
DOI : 10.1109/8.686780
Yee K. S.
1966
“Numerical solution of initial boundary value problems involving Maxwell's Equations in isotropic media”
IEEE Trans. on Antennas Propagat.
Article (CrossRef Link).
14
(3)
302 
307
DOI : 10.1109/TAP.1966.1138693
Thiel M.
,
Sarabandi K.
2008
“A hybrid method for indoor wave propagation modeling”
IEEE Trans. on Antennas and Propagat.
Article (CrossRef Link).
56
(8)
2703 
2708
DOI : 10.1109/TAP.2008.927548
Wang Y.
,
SafaviNaeini S.
,
Chaudhuri S. K.
2000
“A hybrid technique based on combing ray tracing and FDTD methods for sitespecific modeling of indoor radio wave propagation”
IEEE Trans. on Antenna Propagat.
Article (CrossRef Link).
48
(5)
743 
754
DOI : 10.1109/8.855493
Wang Y.
,
Chaudhuri S. K.
,
SafaviNaeini S.
2002
“An FDTD/raytracing analysis method for wave penetration through inhomogeneous walls”
IEEE Trans. on Antenna Propagat.
Article (CrossRef Link).
50
(11)
1598 
1604
DOI : 10.1109/TAP.2002.802157
Deb K.
2001
“Multiobjective optimization using Evolutionary Algorithm”
in Wiley
Chichester
Fogel D. B.
1994
“An introduction to simulated evolutionary optimization”
IEEE Trans. on Neural Networks: Special Issue on Evolutionary Computation
Article (CrossRef Link).
5
(1)
3 
14
DOI : 10.1109/72.265956
Haupt R. L.
,
Haupt S. E.
1998
“Partical genetic algorithm”
in John Wiley & Sons
New York
Muhlenbein H.
,
SchlierkampVoosen D.
1993
“Predictive models for breeder genetic algorithm”
Evolutionary Computation
Article (CrossRef Link).
25 
49
DOI : 10.1162/evco.1993.1.1.25
Deb K.
,
Goldberg D. E.
1989
“An investigation of Niche and Species formation in genetic function optimization”
in Proc. of 3rd Int. Conf. Genetic Algorithm
Article (CrossRef Link).
42 
50
Baker J. E.
1987
“Reducing bias and inefficiency in the selection algorithm”
ICGAI
Article (CrossRef Link).
14 
21
Goldberg D. E.
,
Deb K.
1991
“A comparative analysis of selection schemes used in Genetic Algorithm” FGAI
Article (CrossRef Link).
63 
93