Energy Aware Router Placements Using Fuzzy Differential Evolution

Abstract

The increasing demand of communication services have led to the increase in energy consumption. Energy sustainability is important and challenging research in current world. An energy aware nearest cell association algorithm is proposed to make the mesh routers (MRs) to sleep if they are in idle state. If the MRs have no associated clients, then the MR is considered to be idle. Any network device in idle state consumes power hence a sleep mechanism is introduced to place energy aware routers. A fuzzy differential evolution (FDE) is introduced to dynamically decide the state of the MR by gaining the knowledge from the fuzzy table for parameters like traffic load, minimum distance and transmission power. Transmission cost and failure rate of the deployed network is evaluated and their performance is analyzed.

1. Introduction

Future wireless network will make use of more renewable energy sources like solar, wind and hydro. Developing a sustainable communication is one of the critical and challenging issues in order to sustain the ever-growing traffic demands while alleviating the need of increased energy consumption. Traditional solutions have assumed that mesh routers have consistent power supply through wired electricity. Increasing demand for green mesh networks that can harvest their energies via solar or wind power have reached greater attention. But the energy supplies of these rechargeable routers are not consistent but depend on many environmental conditions [1]. For each router, energy consumption is due to the traffic demand of its associated mesh client and the distance between them. The existing router placement algorithms such as, exhaustive search and greedy search [2] are easily running into local optima. To overcome this drawback fuzzy differential evolution (FDE) placement of nodes with Energy Aware Nearest Cell Association (EANCA) algorithm is proposed in this module.

2. System configuration

System model: In this work, any renewable energy powered MRs is considered to be deployed in a grid scenario where the field is divided into grid cells of equal area. The deployed MRs should provide wireless access for all the stationary MCs which are assumed to be distributed using normal probability distribution. The number of MCs associated with the MR changes periodically. Each MR deployed in the candidate location consumes more energy to guarantee QOS and ensure the traffic demands of the associated MCs [3, 4, 5].

Energy flow model: The renewable energy powered routers are equipped with battery storage. The continuous time line of energy stored is divided into consecutive slots of ‘t’. The energy charging and discharging of a router can be defined with a discrete time energy model as [6, 7]

$$\mathit{E}\left(\mathit{t}\right)=\mathit{E}\left(\mathit{t}-1\right)+\mathit{H}\left(\mathit{t}\right)-\mathit{Ec}\left(\mathit{t}\right)$$ E1

where $\mathit{E}\left(\mathit{t}\right)$ is the residual energy of the router after the tth slot. If $\mathit{t}=0$ , $\mathit{E}\left(0\right)$ is the initial stored energy in the router. The harvested energy is denoted as $\mathit{H}\left(\mathit{t}\right)$ and the energy consumed is denoted as $\mathit{Ec}\left(\mathit{t}\right)$ . $\mathit{H}\left(\mathit{t}\right)$ is a dynamic function since it purely depends on the nature. Let the maximum charging power of renewable energy powered routers is 100 mW. Here two cases can be analyzed, and the connection failures are adjudged.

$$\text{Case}\left(1\right):\text{If}\mathit{H}\left(\mathit{t}\right)>\mathit{Ec}\left(\mathit{t}\right)\text{and}\mathit{E}\left(\mathit{t}\right)=1;\text{failure rate is less}$$ E2

$$\text{Case}\left(2\right):\text{If}\mathit{H}\left(\mathit{t}\right)<\mathit{Ec}\left(\mathit{t}\right)\text{and}\mathit{E}\left(\mathit{t}\right)=0;\text{failure rate is more}$$ E3

3. Problem definition

The objective is to place minimum number of energy aware routers such that user’s traffic demand is satisfied to minimize energy consumption. Here energy consumption is referred as function of a cost metric called transmission cost (TC). The objective function is given by

$$\mathit{Minimize}\mathit{TC}=\mathit{f}\left({\mathit{\text{D}}}_{\mathit{min}},\mathit{TL},{\mathit{P}}_t\right)$$ E4

where TC is the transmission cost, ${\mathit{D}}_{\mathit{min}}$ is the minimum distance between the mesh routers and clients, TL is the traffic load and ${\mathit{P}}_{\mathit{t}}$ is transmission power.

Subject to:

$${\mathit{E}}_{\mathit{in}}-{\mathit{E}}_r\ge {\mathit{E}}_i$$ E5

where $\mathit{Ein}$ is the initial energy, $\mathit{Er}$ is the residual energy and $\mathit{Ei},\mathit{j}$ is the energy required to guarantee QOS between the mesh routers and clients.

$${\mathit{P}}_t\le {\mathit{P}}_t$$ E6

where ${\mathit{P}}_t$ is the transmission power required for any ith mesh router to associate with the jth mesh client and ${\mathit{P}}_t$ denotes the maximum transmission power.

$${\mathit{E}}_{\mathit{c}}\le {\mathit{E}}_{\mathit{h}+}$$ E7

where ${\mathit{E}}_{\mathit{C}}$ is the energy consumed and ${\mathit{E}}_{\mathit{h}+}$ is the energy harvested.

$$\mathit{FR}\le {\mathit{F}}_{\mathrm{th}}$$ E8

where FR indicates the failure rate and $\mathit{Fth}$ denotes the failure threshold.

The FR is expressed as

$$\mathit{FR}=\sum _{\mathit{t}\in \mathit{K}}\sum _{\mathit{i}\in \mathit{C}}\left(1-\sum _{\mathit{j}\in \mathit{S}}\mathit{xij}\left(\mathit{t}\right)\right)/\left|\mathit{C}\right|\ast \left|\mathit{K}\right|$$ E9

where $\mathit{x}\mathit{ij}\left(\mathrm{k}\right)=\left\{\begin{array}{l}1\mathit{\text{if}}\mathit{a}\mathit{\text{node is associated with the}}\mathit{MR}\\ 0\mathit{\text{otherwise}}\end{array}\right\}$ , |C| stands for total number of clients, |K| denotes the time slots and S denotes the set of candidate locations [8]. The renewable energy powered routers are equipped with battery storage.

Eq. (5) ensures that the difference between the initial and residual energy must be greater or equal to the energy required to guarantee QOS between the mesh routers and clients. Eq. (6) ensures that the transmission power required for any mesh router to get associated with any client must be less than the maximum transmission power. Eq. (7) ensures that the energy consumed is less than the energy harvested. Eq. (8) ensures that the failure rate (FR) a parameter which is incurred from [8] measures the network performance. The constraint specifies that FR must be less than a predefined failure threshold (Fth).

4. Fuzzy differential evolution

According to the former literatures [9] the control parameters S,CR were kept fixed during the optimization process. The control parameters of DE is made adaptive using fuzzy logic. Here in this proposed optimization model fuzzy rules are defined for two sets of input parameters respectively as follows:

1. DE control parameters

2. Network inputs

DE control parameters: In DE algorithm, usually empirical values are selected for its search process. Using fuzzy rules the system is made adaptive to search the parameters for mutation and crossover operation. The setting of parameter values can be done in two ways through parameter tuning and parameter control. Parameter tuning is one of the common methods used to find out good values before running the algorithm. Using the best result the algorithm is made to run. In parameter control approach the values are changed while the algorithm is running [10, 11]. This later approach is further divided into deterministic, adaptive and self-adaptive parameter controls.

Deterministic parameter control: A rule strategy is defined to deterministically change the parameters. It strategically changes the values without getting any feedback from the search.

Adaptive parameter control: This approach is handled when a feedback arises from the search and this feedback is used to determine the values to the parameters.

Self-adaptive parameter control: Here in the evolutionary search encoded parameters are used in the chromosomes to perform the mutation and crossover operation to produce effective individuals that could survive and produce offspring.

Network inputs: In the deployed network the distance between the client and the mesh router in each grid cell is calculated and formulated as a matrix called the distance matrix. The minimum distance value is returned from the matrix which is denoted as Dmin. The Traffic Load (TL) is calculated from the number of clients which are associated with the MRs. The Transmission Power (Pt) needed to associate a MC with MR also varies between low and high.

4.1 Proposed optimization control flow model

Figure 1 shows the fuzzy DE control flow model for optimizing the transmission cost (TC) metric. In general the DE key operators are fixed. In order to overcome the premature convergence which usually occurs in DE, a fuzzy DE approach is implemented wherein the scaling factor (S) and cross over constants (CR) are adapted using the fuzzy inference engine (FIS) [12].

Figure 1.

Optimization control flow model using fuzzy differential evolution.

As the network size increases the load of the network, transmission power and the distance between the router and client varies in different instances. The proposed FDE is a knowledge based system which dynamically selects the best search parameters from the fuzzy set. The Mamdani’s fuzzy inference method is used to map the output function. The output of each rule is a fuzzy set and the output fuzzy set is the aggregation of all the sets. The sample rule set is constructed and given as follows for the fuzzy inputs CR, S and output F(x) using IF-THEN structure.

IF (CR is low) AND (S is low) THEN F(x) is low.

IF (CR is average) AND (S is low) THEN F(x) is low.

IF (CR is high) AND (S is average) THEN F(x) is medium.

The categorical value for CR includes {low, average, high}, the categorical values for S include {low, average, high}. The decision attribute F(x) i.e. output has four categorical values that include {very low, low, medium, high, very high}. A total number of possible fuzzy inference rules will be 9(3*3), hence there are two linguistic states. The fuzzy rules are given in Table 1. An example membership plot of the input variables CR, S and output variable F(x) using triangular membership function is shown in Figure 2.

CR	S
	Low	Average	High
Low	VL	L	M
Average	L	M	M
High	M	H	VH

Table 1.

Fuzzy rules-DE control inputs F(x).

VL, very low; L, low; medium, M; H, high.

Figure 2.

Membership plot of DE inputs CR, S and output F(x) with surface view plot.

Defuzzification is used to get the crisp values from the fuzzy inference rules. The input fuzzy set ‘μ’ is defuzzified into crisp value ‘c’ using centroid technique. For example the linguistic values of CR (low = 0.3, average = 0.6, high = 1) and S (low = 0.2, average = 0.6, high = 1) the crisp output can be calculated by

$$\mathit{C}\left(\mathit{\text{out}}\right)=\sum \mathit{xi}\mathit{\mu }\left(\mathit{xi}\right)/\sum \mathit{\mu }\left(\mathit{xi}\right)$$ E10

where xi is the CR or S and μ(xi) is the linguistic value.

As the network control parameters like the minimum distance (Dmin), Traffic Load (TL) and Transmission power (Pt) are uncertain parameters, a fuzzy inference method is used to map the input parameters with output cost metric function TC which refers only the energy consumption of mesh nodes. A sample rule set is given by:

1. IF (Dmin is short) AND (TL is low) AND (Pt is low) THEN TC is low.

2. IF (Dmin is medium) AND (TL is medium) AND (Pt is low) THEN TC is acceptable.

3. IF (Dmin is long) AND (TL is high) AND (Pt is low) THEN TC is high.

4. IF (Dmin is very long) AND (TL is high) AND (Pt is high) THEN TC is very high.

The categorical value for Dmin includes {short, medium, long, very long}, the categorical values for TL include {low, medium, high} and the categorical value for $\mathit{Pt}$ includes {low, medium, high}.The decision attribute i.e. output cost has 3 categorical values that include {low, acceptable, high}. A total number of possible fuzzy inference rules will be 36(4*3*3), hence there are three linguistic states. The fuzzy rules for TC are tabulated in Table 2. with respect to four categorical values of minimum distance (a) short (b) medium (c) long and (d) very long. For example the linguistic values of $\mathit{D}min$ ranges from zero to 1 km and categorized as (short = 0.2; medium = 0.4; long = 0.6, very long = 1), the values of P_t ranges from 1 to 15 dBm and categorized as (low = 5; medium = 10; high = 15). The values of TL is the number of clients associated to a MR which ranges from 1 to 45 and categorized for fuzzy rule as (low = 15; medium = 30; high = 45).

1. Input: TL➔Traffic Load; Pt➔Transmission power; Distance.

2. Output: TC➔Transmission Cost.

3. Output variables: L➔Low; A ➔Acceptable; H➔High.

Pt	TL
	Low	Medium	High
(a) Distance: short TC
Low	L	L	A
Medium	L	A	H
High	A	A	H
(b) Distance: medium TC
Low	L	L	H
Medium	L	A	H
High	A	H	H
(c) Distance: long TC
Low	A	H	H
Medium	A	H	H
High	L	A	A
(d) Distance: very long TC
Low	H	H	H
Medium	A	H	H
High	A	A	H

Table 2.

Fuzzy rules_Transmission cost.

The membership plots of each input variable and the output variable shown in Figure 3(a)–(d). The input variables are minimum distance, traffic load and transmission power. The fuzzy rule viewer and surface view plot are shown in Figures 4 and 5.

Figure 3.

Membership plot of network inputs and output transmission cost metric.

Figure 4.

Fuzzy rule viewer.

Figure 5.

Surface view plot.

5. Energy aware nearest cell association (EANCA) algorithm

An energy aware MR placement is accomplished by developing an EANCA algorithm. The conditions for associating the MC with a MR are the residual energy must be greater than the consumed energy and the power consumed by the both the mesh nodes must be less than the maximum power allocated. Even if any MR has no client association and it is in idle state, still there is some minimum amount of energy consumption. In order to overcome this, the proposed energy aware scheme turns the inactive mesh routers to sleep mode thus minimizing the energy consumption [13]. The energy consumption level of a node at any time of the simulation can be determined by finding the difference between the current energy value and initial energy value.

The methodology is illustrated as follows:

Step 1: The network input parameters like the number of mesh routers and clients are specified.

Step 2: Compute the distance of clients with respect to each router and store in a matrix and calculate the minimum distance at each generation.

Step 3: The DE control parameters CR,S are applied to the fuzzy inference engine and adaptively controlled to select the best optimum inputs for best result.

Step 4: The important parameters like distance between MR and MC, Traffic Load(TL) for each router and transmission power of router are fuzzy ruled and adaptively tuned for optimal setting.

Step 5: If TL = f(medium, high, very high) and

If Dmin = f(short, medium) and.

If Pt = f(medium, high) then MR ∈ active mode.

If TL = f(low, very low) and.

If Dmin = f(long, very long) and.

If Pt = f(low) then MR ∈ sleep mode.

Step 6: Check the QOS constraints

Step 7: If true then

Mc(j) ∈ MR(i)

Er(new) = Er-1

Else if.

Mc(j) ∉ Mr.(i)

Then.

Compute the fitness value.

Step 9: End

The performance of the proposed scheme is analyzed based on three important metrics PDR, throughput and FR.

5.1 Performance metrics

1. Throughput. Network throughput is the average rate of successful message delivery over a communication channel.

2. Packet delivery rate. The ratio of the average number of data packets received by the destination node to the number of data packets transmitted.

3. Failure rate (FR). In a time slot there is a possibility for a MC not to be assigned to a MR, hence they get disconnected which is referred as connection failure. The network performance is evaluated through a metric failure rate and it is defined as the number of failures to the attempts to make the connection.

6. Simulation results and discussion

The proposed approach is evaluated in NS2 simulator and compared with the existing algorithms. The MRs is deployed in a large terrain area of 1000 m × 1000 m and the clients are distributed normally. The deployment field is equally divided into grid cells with equal area. The simulation period is set as 12 hours i.e. half a day, which is divided into 108 consecutive slots each with time duration of 400 seconds. The failure rate threshold is set as 1. The network performance metrics are evaluated for this simulation model. The simulation is repeated for 200 generations and the FR percentage is calculated after each generation. The input simulation parameters are given in Tables 3 and 4.

Parameters	Values
Area size	1000 m × 1000 m
MAC	802.11 s
No. of mesh routers	16
No. of mesh clients	45
Application type	CBR
Packet size	1024 bytes
Transmission power	15 dBm

Table 3.

Simulation parameters.

Parameters	SA	DE	FDE
Placement of nodes	Random	Random	Random
Population size	100	100	100
CR	Probabilistic selection	0.5	Fuzzy rule based selection

Table 4.

Simulation settings-optimization methods.

The energy consumption is evaluated for FDE approach and is compared with the DE, SA and conventional method using only the traffic weight to allot the gateway. From the simulated results shown in Figure 6, it is observed that in DE and FDE placement scheme the number of routers required is minimum to cover the given number of clients and it is found that there is a gradual decrease in energy consumption from 80th generation to 120th. From 120th generation the schemes have converged for the optimal result. Whereas SA and the conventional method using Traffic Weight (TW) allotment of gateways show high energy consumption as the number of routers required are high as well as the routers are inactive with no client association.

Figure 6.

Energy consumption of mesh nodes.

In order to overcome the premature convergence in DE, fuzzy DE method uses the knowledge base fuzzy rules. When CR is high than the scaling factor the convergence rate is faster. The proposed FDE scheme utilizes also the knowledge about the network load, router and client distance which enables the system to consume less power than other node placement schemes.

The FDE approach shows 5.12% lesser energy consumption than TW method, 4.4% lesser energy consumption than SA and 0.75% lesser than DE algorithm. The network performance is evaluated through metrics such as throughput and PDR. Throughput refers how much data can be transferred from one location to another in a given amount of time.

PDR is defined as the ratio between the successfully received packets in the destination to the number of data packets sent from the source node. The comparative results of the conventional methods and evolutionary approaches are tabulated in Table 5 for 45 clients, 16 routers and one gateway in normal distribution.

Data rate = 12 Mbps; no. of clients = 45; no. of MRs = 16
Methodology	Throughput (Mbps)	PDR (%)	Failure rate (%)
Conventional	6	61	27.35
TW	6.8	67	20.2
SA	8.9	71	13.25
DE	11	97	12.12
FDE	11.12	97.34	10.1

Table 5.

Performance evaluation.

The observed results show that the FDE approach produces better results compared to the other approaches. The number of failures for the clients to associate with the mesh routers are high for conventional and TW methods compared to the evolutionary schemes. The results show that the FDE approach has 20% less failure rate than DE and 23.7% less than SA schemes. Even if the network size increases with more number of clients the proposed FDE approach is able to show less failure percentage as displayed in Figure 7.

Figure 7.

Percentage of failure rate vs. no. of mesh clients.

The conventional method show a steep increase as the number of mesh clients increases whereas the evolutionary approaches tries to settle down in optimum points. As the number of clients increases FDE and DE approaches converge and show only 11% of FR. The comparison of the three evolutionary approaches with convergence graphs are shown in Figure 8. Standard deviation is calculated for each approach. The algorithm is run for 1000 iterations and it is observed that the result of FDE approach converged with 0.001787, which is a very low value from 300th iteration. The results obtained from FDE approach is consistent and has faster convergence speed compared to DE and SA.

Figure 8.

Convergence rate.

7. Summary

To summarize, energy aware placement using FDE approach is proposed to minimize the energy consumption. A transmission cost metric is defined as a function. Three important parameters, the minimum distance between the MRs and MCs, the transmission power of routers and traffic load.

The deployment field is divided into cells of equal area wherein the candidate locations of each MR is positioned. Normal distribution is selected to distribute the clients as it shows 36.6% increase of PDR than SA approach in the previous module.

Usually the DE control parameters are fixed but the FDE scheme uses the CR and S values adaptively to settle for optimum point. A fuzzy inference engine is used to map the input to the output function. The uncertain network parameters are also mapped using the fuzzy inference engine to evaluate the transmission cost.

An energy aware nearest cell association algorithm is proposed to make the MRs to sleep if they are in idle state. If the MRs have no associated clients then the MR is considered to be idle. Any network device in idle state consumes power hence a sleep mechanism is introduced to place energy aware routers.

The FDE approach shows 5.12% lesser energy consumption than TW method, 4.4% lesser energy consumption than SA and 0.75% lesser than DE algorithm. The failure rate is also observed to be less than the other schemes. The proposed FDE method has 20% less failure rate than DE and 23.7% less than SA schemes. The conventional method shows a steep increase as the number of mesh clients increases whereas the evolutionary approaches tries to settle down in optimum points. As the number of clients increases FDE and DE approaches converge and show only 11% of FR. Thus the results obtained using FDE shows less energy consumption and failure rate.