Advanced
A New Green Clustering Algorithm for Energy Efficiency in High-Density WLANs
A New Green Clustering Algorithm for Energy Efficiency in High-Density WLANs
KSII Transactions on Internet and Information Systems (TIIS). 2014. Feb, 8(2): 326-354
Copyright © 2014, Korean Society For Internet Information
  • Received : August 22, 2013
  • Accepted : February 09, 2014
  • Published : February 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Yang Lu
Xuezhi Tan
Yun Mo
Lin Ma

Abstract
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 high-density WLANs. Traditionally, in order to maintain the network coverage, all the APs within the WLAN have to be powered-on. Nevertheless, the new algorithm can power-off a large proportion of APs while the coverage is maintained as its always-on counterpart. The two main components of the new approach are the faster procedure based on K-means 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 ray-tracing 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.
Keywords
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 high-density 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 always-on 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 high-density 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 cluster-head APs for SEAR. Green clustering is the first algorithm for energy efficient strategies such as SEAR and the green clustering selects cluster-head 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 cluster-head 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 high-density 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 multi-carrier 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 prediction-based method to cluster APs in a decorrelated space In WSNs (wireless sensor networks) Y. Kang ret al. study about the low-power 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 B-CAST, a simple broadcast extension of the well-known B-MAC [15] . Lim S. et al. consider the state-of-the-art ACK-based 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 ACK-based 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 end-to-end delay. In [17] , Y. Zuo et al. propose hybrid algorithm which combines genetic algorithm and simulated annealing algorithm to solve a multi-objective 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 real-time 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 end-to-end 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 user-oriented 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 dual-sink algorithm with role switching mechanism which utilizes both static and mobile sinks. Their algorithm could be employed in event-driven and multi-hop scenarios with improvements on the lifetime, the load and the end-to-end delay. However, few of these works above involve the concept of energy efficiency in high-density WLANs or green clustering.
SEAR (Survey, Evaluate, Adapt and Repeat) is an energy efficient strategy in high-density WLANs proposed by Jardosh et al. to manage the network resource [5] . An energy efficient algorithm in high-density 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 high-density WLAN. The selection process is dynamic. APs are powered-off for energy conservation in an energy efficientWLAN, and the transmission power of cluster-head 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 powered-off to reduce the number of idle APs.
3. Analysis of Energy Efficient Strategy and Green Clustering Algorithm
- 3.1 Centralized High-Density 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 .
PPT Slide
Lager Image
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 high-density WLANs. To determine that either a WLAN is high-density or not, a parameter is introduced and defined as
PPT Slide
Lager Image
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 large-scale 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 high-density.
- 3.2 Study of Green Clustering Algorithm in SEAR
SEAR is proposed by Jardosh as a demand-driven strategy to manage APs in high-density WLANs efficiently. And it is a policy-based 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 always-on 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] .
PPT Slide
Lager Image
Components of SEAR.
A green clustering algorithm forms AP clusters and selects a cluster-head 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 cluster-head AP as shown in Fig. 3 .
PPT Slide
Lager Image
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 Wireless-N 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 powering-off 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 pre-determined 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 ni 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, ni occurs as attribute value of AP i . To implement cluster formation, the maximum ni 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 Ri 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 Ri if and only if the new j is in the neighborhood set of every other AP already added to Ri . Once all the APs that satisfy the condition that being added to Ri , AP i is made the cluster-head 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 cluster-head APs remain powered-on 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 cluster-head APs needs to be increased to maintain the network coverage.
Green clustering algorithm of SEAR is measurement-based 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 high-density 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 pre-determined 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 ray-tracing and FDTD (finite-different time-domain) 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
PPT Slide
Lager Image
where Pt is the transmitting power, Pr is the received power which is a function of the distance d , Gt is the transmitter antenna gain, Gr 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
And if the value of Pt 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 ray-tracing and FDTD is introduced.
Ray-tracing method is presented to evaluate the indoor wave propagation and penetration [27] . According to ray-tracing, waves from a Tx antenna could be modeled as ray tubes, and from geometrical optics, the E-field of the ray tube at Rx can be given by
PPT Slide
Lager Image
where
PPT Slide
Lager Image
denotes the E-field at a reference point RP 0 ,
PPT Slide
Lager Image
represent the reflection and transmission coefficient dyads along the whole path, respectively.
PPT Slide
Lager Image
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
PPT Slide
Lager Image
where A 0 and A are the cross-sectional 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 E-field components and H-filed components at different directions are discretized, so each E-filed component is encircled by four H-field components, and also each H-filed component is encircled by four E-field components. Moreover, in time domain, E- and H-field components are also discretized arranging at regular intervals. According to FDTD, in a 3-D scenario, for instance, E-filed component at direction x ( Ex ) can be given by
PPT Slide
Lager Image
where n denotes time, ε and σ are material constants, E and H represent values of E- and H-filed, 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 Ey , Ez , Hx , Hy and Hz 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 H-field 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 ray-tracing 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 ray-tracing and FDTD is that the propagation between AP and B, C and D is analyzed based on ray-tracing 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 Ez , Hx and Hy is assumed. The derivation for horizontal polarization is analogous.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the Hankel function of second kind,
PPT Slide
Lager Image
denote the vectors to Tx and to the brick point, respectively. k is the wavenumber.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
are the electric surfaces fields in the z-direction, and
PPT Slide
Lager Image
is the surface normal vector of the brick.
PPT Slide
Lager Image
PPT Slide
Lager Image
Illustration of modeling indoor wave propagation.
And the analogous combinations of ray-tracing 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 K-means 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 ray-tracing and FDTD is more complex, time-consuming 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 D-dimension data set consisting of N samples can be divided into K categories by minimizing a criterion function J which be expressed by
PPT Slide
Lager Image
where rnk is a clustering index, rnk = 1 and rnj = 0 for j k . μ k is the cluster center of the k th cluster and ‖ • ‖ is an operator that calculates Euclid distance between xn 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 E-step and M-step. In E-step, on the basis of rnk , μ k is generated following optimization criterion expressed by
PPT Slide
Lager Image
In M-step, according to μ k , rnk is generated following optimization criterion. K -means iterates E-step and M-step 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 trade-off of this approach is the number of categories K which is problem-specific.
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 RK .
(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 cluster-head 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, RK 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 cluster-head APs as RK . Then we remove APs from RK . In term of the number of trail cluster-head 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 pre-determined 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 cluster-head 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
PPT Slide
Lager Image
where Si and Sj 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 .
PPT Slide
Lager Image
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
PPT Slide
Lager Image
where R is a feasible solution consisting of a set of trial cluster-head 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 pre-determined. According to (13), the working mechanism to solve the transformed problem would be optimizing processes over locations, so the selection of step-size would be critical for optimization and convergence time. Therefore, an optimization algorithm which could support multi-step sizes should be introduced. In general, different step sizes should be applied to different data sets, and most methods implement multi-step 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 multi-step 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 multi-population model. The structure of multi-population EA is shown in Fig. 5 .
PPT Slide
Lager Image
The structure of multi-population EA.
In single-objective problems, rank-based 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 non-dominated. All the non-dominated vectors in the Pareto Optimal Set can form a front, and in the general case, it can be considered that these non-dominated points produce the Pareto Front. The purpose of applying multi-objective 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 non-dominated 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]
PPT Slide
Lager Image
where ai 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. Vali is the variable of the i th dimension from offspring, Vali P 1 and Vali 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
PPT Slide
Lager Image
where ValiP is the variable of the parent chosen from population, and REP [ h ] is a value taken from the repository. As non-dominated 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 trade-off 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.
PPT Slide
Lager Image
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 problem-specific 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 .
PPT Slide
Lager Image
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 RF consisting of feasible APs can be obtained. Similarly, the results of Proc. A expressed as RA can also be obtained, and the APs in RA are the ultimate green cluster-head APs. In Fig. 7 , OPR. I denote operations of increasing the transmitting power of APs in the set of RF and then powering-off APs in RF ð , and OPR. II denote operations of powering-on APs with maximum transmitting power in RF ð RA and then powering-off APs in RF RA ð . After OPR. II, cluster-head 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 high-density 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 high-density 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.
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 cluster-head 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 non-dominated 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 non-dominated 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 .
PPT Slide
Lager Image
Results of PROC. F, in which 9 APs are powered-on.
PPT Slide
Lager Image
Illustration of feasible solutions, the objectives are to minimize uncovered and overlap rates.
PPT Slide
Lager Image
Results of NGCA, in which 8 APs are powered-on 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 .
PPT Slide
Lager Image
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 powered-on. 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.
PPT Slide
Lager Image
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 cluster-head 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.
PPT Slide
Lager Image
Illustrations of RPs on corridors.
PPT Slide
Lager Image
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 .
PPT Slide
Lager Image
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 arc-shaped. 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 arc-shaped.
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.
PPT Slide
Lager Image
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 pre-determined 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.
PPT Slide
Lager Image
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 .
PPT Slide
Lager Image
Results of Proc. F, in which 14 APs are powered-on.
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 .
PPT Slide
Lager Image
Results of NGCA obtained in the actual model, in which 9 AP are powered-on 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 powered-off 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 .
PPT Slide
Lager Image
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 powered-off 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 .
PPT Slide
Lager Image
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 powered-off. 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
PPT Slide
Lager Image
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 environment-specified, 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
High-density 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 powered-on 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 high-density WLANs in this paper. The algorithm will be the foreshadowing for future study about energy efficient strategy in which the optimization of cluster-head 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 high-density 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 high-density 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 indoor-positioning.
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.
References
(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
http://muniwifi.org
Jardosh A. P. , Iannaccone G. , Papagiannaki K. , Vinnakota B. “Towards an energy-star WLAN infrastructure” in Proc. of HotMobile February 26-27, 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: On-demand WLAN infrastructures” Mobile Networks and Applications Article (CrossRef Link). 14 (6) 798 - 814    DOI : 10.1007/s11036-008-0123-8
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 20-22, 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 26-30, 2010 Article (CrossRef Link). 347 - 351
Rabaey J. “The standby power challenge: Wake-up receivers to the rescue” in Proc. of VLSI-TSA April 27-29, 2009 Article (CrossRef Link) 42 -
Marsan M. A. , Chiaraviglio L. , Ciullo D. “A simple analytical model for the energy-efficient activation of access points in dense WLANs” in Proc. of ICEEC-NE April 13-15, 2012 Article (CrossRef Link). 159 - 168
Chen Y. , Yang Q. , Yin J. , Chai X. 2006 “Power-efficient access-point 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 “Kernel-based 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 energy-efficient 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 “Energy-efficient low-delay 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 “EP-MAC: 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 “User-oriented energy-and spectral-efficiency 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 “Energy-efficiency 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 energy-efficient dual-sink algorithm with role switching mechanism for event-driven 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 multi-hop 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. , Safavi-Naeini S. , Chaudhuri S. K. 2000 “A hybrid technique based on combing ray tracing and FDTD methods for site-specific 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. , Safavi-Naeini S. 2002 “An FDTD/ray-tracing 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 “Multi-objective 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. , Schlierkamp-Voosen 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