Coverage Improvement In Wireless Sensor Networks Based On Fuzzy-Logic And Genetic Algorithm

الموضوعات :

Elaheh Radmehr ¹ , HASSAN SHAKERI ²

1 - Islamic Azad University Neyshabour Branch
2 - DEPARTMENT OF COMPUTER-FERDOWSI UNIVERSITY OF MASHHAD

تاريخ الإرسال : 14 الإثنين , شعبان, 1436 تاريخ التأكيد : 12 الأحد , ذو الحجة, 1438 تاريخ الإصدار : 12 الأربعاء , صفر, 1439

الکلمات المفتاحية: wireless sensor networks, coverage hole, Genetic algorithm, fuzzy-logic,

ملخص المقالة :

Wireless sensor networks have been widely considered as one of the most important 21th century technologies and are used in so many applications such as environmental monitoring, security and surveillance. Wireless sensor networks are used when it is not possible or convenient to supply signaling or power supply wires to a wireless sensor node. The wireless sensor node must be battery powered.Coverage and network lifetime are major problems in WSNs so in order to address this difficulty we propose a combinational method consists of fuzzy-logic and genetic algorithms. The proposed scheme detects the coverage holes in the network and selects the most appropriate hole's neighbor to move towards the blank area and compensate the coverage loss with fuzzy-logic contribution and above node new coordinate is determined by genetic algorithm. As fuzzy-logic will be so effective if more than one factor influence on decision making and also genetic algorithms perform well in dynamic problems so our proposed solution results in fast, optimized and reliable output

المصادر:

[1] A survey on sensor networks author={Akyildiz, Ian F and Su, Weilian and Sankarasubramaniam, Yogesh and Cayirci,Erdal},journal={Communications magazine, IEEE}, volume={40}, number={8}, pages={102--114},year={2002}, publisher={IEEE}
[2] Wireless sensor networks: applications and challenges of ubiquitous sensing,author={Puccinelli, Daniele and Haenggi, Martin}, journal={Circuits and SystemsMagazine, IEEE}, volume={5}, number={3}, pages={19--31}, year={2005}, publisher={IEEE}
[3] Coverage problems in sensornetworks: A survey},author={Wang, Bang}, journal={ACM Computing Surveys (CSUR)}, volume={43}, number={4}, pages={32}, year={2011},publisher={ACM}
[4] A coverage-preserving node scheduling scheme for large wireless sensor networks, author={Tian, Di and Georganas, Nicolas D}, booktitle={Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications}, pages={32--41}, year={2002}, organization={ACM}
[5] Estimating coverage oles sensornetworks},author={Ghosh,Amitabha}, booktitle={Local Computer Networks, 2004. 29th Annual IEEE International Conference on},year={2004}, organization={IEEE}
[6] The coverage problem in a ireless sensor network},author={Huang, Chi-Fu and Tseng, Yu-Chee},journal={Mobile Networks and applicaations},year={2005},publisher={Springer-Verlag New York, Inc.}
[7] Connectivity constrained wireless sensor deployment using multiobjective evolutionary algorithms and fuzzy decision making}, author={Pradhan, Pyari Mohan and Panda, Ganapati}, journal={Ad Hoc Networks}, volume={10}, number={6}, pages={1134--1145}, year={2012},
[8] An exact algorithm for providing multi-perspective event coverage in wireless multimedia sensor networks, author={Yildiz, Enes and Akkaya, Kemal and isikoglu, Esra and others}, booktitle={Wireless Communications and Mobile Computing Conference (IWCMC), 2011 7th International}, pages={382--387}, year={2011}, organization={IEEE}
[9] Virtual potential field based coverage-enhancing algorithm for directional sensor networks.}, author={Tao, Dan and Ma, Hua-Dong and Liu, Liang}, journal={Ruan Jian Xue Bao(Journal of Software)}, number={5}, pages={1152--1163}, year={2007}
[10] A virtual centripetal force-based coverage-enhancing algorithm for wireless multimedia sensor networks}, author={Jing, Zhao and Jian-Chao, Zeng}, journal={Sensors Journal, IEEE}, volume={10}, number={8}, pages={1328--1334}, year={2010}, publisher={IEEE}
[11] Coverage-enhancing algorithm based on overlap-sense ratio in wireless multimedia sensor networks}, author={Chen, Jian and Zhang, Lu and Kuo, Yonghong}, journal={Sensors Journal, IEEE}, number={6}, pages={2077--2083}, year={2013}, publisher={IEEE}
[12] An efficient genetic lgorithm for maximum coverage deployment in wireless sensor networks}, author={Yoon, Yourim and Kim, Yong-Hyuk}, journal={Cybernetics, IEEE Transactions on}, volume={43}, number={5}, pages={1473--1483}, year={2013}, publisher={IEEE}

نص كامل:



 

 

Coverage Improvement In Wireless Sensor Networks Based On Fuzzy-Logic And Genetic Algorithm

 

Elaheh Radmehr, Hassan Shakeri 

Isalmic Azad University-Neyshabour Branch –Iran

Department of computer-Ferdowsi university of mashhad-Iran

 

 

ABSTRACT

 

Wireless sensor networks have been widely considered as one of the most important 21th century technologies and are used in so many applications such as environmental monitoring, security and surveillance. Wireless sensor networks are used when it is not possible or convenient to supply signaling or power supply wires to a wireless sensor node. The wireless sensor node must be battery powered.Coverage and network lifetime are major problems in WSNs so in order to address this difficulty we propose a combinational method consists of fuzzy-logic and genetic algorithms. The proposed scheme detects the coverage holes in the network and selects the most appropriate hole's neighbor to move towards the blank area and compensate the coverage loss with fuzzy-logic contribution and above node new coordinate is determined by genetic algorithm. As fuzzy-logic will be so effective if more than one factor influence on decision making and also genetic algorithms perform well in dynamic problems so our proposed solution results in fast, optimized and reliable output.

 

 

Key words: wireless sensor networks/ fuzzy-logic/ genetic algorithm/ coverage hole.

 

 

1. INTRODUCTION

 

As the scope of WSNs applications has been expanding beyond its original military purposes, such as habitat monitoring, rescue and medical care [1] [2] so it requires more attention and tendency. Since wireless sensor networks mostly are used to monitor inaccessible, dangerous and sometimes polluted areas, so deploying sensor nodes in the region of interest randomly is so common. For example, the enemy martial regions in wars are so dangerous and risky. In these areas there are so many elements such as obverse equipment's behavior that needs to be recorded accurately to defend an attack. In such areas sensors are aimed to be deployed randomly, however there is no insurance of uniform distribution after random deployment and also meeting overlapped regions and coverage holes are inevitable. Additionally the sensor nodes are battery-powered and mostly located in noisy environments, so coverage maintaining is essential as it influences the quality of gathered data.

 

 

2. Literature review

 

In WSNs, maintaining both coverage and uniformity is vital and there have been so many investigations with the aim of improving it. Coverage percentage fundamentally represents perception area of sensing environment [3].In traditional wireless sensor networks (WSNs) with isotropic sensors, several algorithms have been used to increase coverage and prolong network lifetime such as shutting off redundant sensors [4] assigning sensing work tasks for nodes[5].Haung and Tseng proposed an efficient polynomial time solution[6] by considering the coverage of each sensor's sensing range. In this algorithm each point in the area of interest is supposed to be covered by at least K sensors, where K is an integer.

This method drawback is that the number of sensor nodes and uniformity are not considered. Panda [7] presented an energy-efficient deployment for WSN based on a multi objective particle swarm optimization algorithm. In this method, coverage and lifetime of the network are considered as main purposes, whereas the lack of uniformity is observed as a disadvantage. Another solution which paying less attention to overlapping and redundant sensing regions is proposed[8] provides multi perspective coverage with the least number of the nodes. Based on virtual force for a given region to optimize network coverage several algorithms have been presented [9] [10].For the problems with genotype space in mathematical view which frequently arises in real world applications to gain maximum coverage Yourim Yoon and Yong-Hyuk Kim proposed a genetic algorithm[12]. Based on overlap-sense ratio by adjusting the sensing direction of the nodes Jian Chen and Yonghong Kuo proposed a coverage enhancing algorithm[11].

As it is recognized most of above researches considered as single objective and more importantly have dynamic environment limitations. This necessitates a more accurate and energy-efficient method to increase coverage ratio.

 

3. Problem Description

 

The proposed algorithm objective is reducing overlapping regions and cover blank areas as much as possible. meanwhile the complexity of the algorithm should be taken into account due to the limited accessible energy of the nodes. In a densely deployed WSNs sensing areas might be overlapped. So the quality of the collected data and energy-efficiency is influenced. The coverage function of a given target is defined by f(x):

 

        1 if d(s, x) ≤  RS      

       f(x) =                     

                        0     otherwise

 

 

 

where  d(s ,x) is the Euclidean distance between the sensor s and target x and calculated by:

                                       d=

and  RS is a constant value and called sensing range which is technology-dependent and used to define the sensing capability of the sensor-node.

 

The coverage redundancy of each node is defined by:

                            

Where Sis the sensing area of which has been overlapped by and  is the sensing area of . Following figure shows a randomly deployed WSN consists of uncovered area along with overlapped regions.

 

 

4. The new proposed method

 

In WSNs when a sensor node fails we experience coverage hole(following figure), to solve this we should adopt a compensation method, which takes power consumption into consideration.

 

 

Fuzzy-logic selects one of neighbors of the hole and genetic algorithm determines its destined coordinate in the blank area as demonstrated below.

 

The inputs of fuzzy-logic system are the 3 attributes of each sensor node in the defined domain. As descried below.

 

E: accessible energy

ND: node density

D: distance to the detected hole

 

And the output of the above system is the ID of the node which has got the  chance to move towards the hole. As it is seen node density has taken into consideration in this algorithm to guarantees uniformity in the network. Each of the input functions has 3 membership routines itself.(Table 1)

 

Table 1: Input membership

Input	Memberships
Energy	low	medium	high
Node Density	few	Ave	many
Distance	near	middle	far

 

And also the output function has 5 memberships routines. As shown in Table 2.

 

Table 2: output memberships

output	Membership
Chance	Very bad-bad-Ave-good-very good

 

Our fuzzy-logic uses 27 rules for its inference-engine (Table3). 

 

Table 3: Applied rules for fuzzy-logic system

Rule Number	Input variable			Output
	Energy	Node Density	Distance
1	low	few	Far	Very bad
2	Low	Few	middle	Very bad
3	Low	Few	Near	Bad
4	Low	Ave	Far	Very bad
5	Low	Ave	Middle	Very bad
6	Low	Ave	Near	Bad
7	Low	Many	Far	Bad
8	Low	Many	Middle	Bad
9	Low	Many	Near	Bad
10	med	Few	Far	AVG
11	Med	Few	Middle	AVG
12	Med	Few	Near	AVG
13	Med	Ave	Far	Good
14	Med	Ave	Middle	Good
15	Med	Ave	Near	AVG
16	Med	Many	Far	AVG
17	Med	Many	Middle	Good
18	Med	Many	Near	AVG
19	high	Few	Far	Good
20	High	Few	Middle	Good
21	High	Few	Near	Good
22	High	Ave	Far	Very good
23	High	Ave	Middle	Very good
24	High	Ave	Near	Very good
25	High	Many	Far	Good
26	High	Many	Middle	Good
27	High	Many	Near	Very good

 

 

 

 

 

 

The following plan shows our proposed algorithm architecture.

 

WSN Inference Engine     27 Rules

Chance

Out put

Inputs

Distance

Node Density

Energy

 

 

 

 to continue we benefit of genetic algorithm. The problem domain is a circle centered at the failed node with the radius of sensing range. Our aim is to find a position in this circle as the hole's neighbor destination that satisfies our fitness function (having the least coverage redundancy).

Now we describe the genetic framework used in this study. Let N=50 be the population size. A collection of N/2 pair  is randomly composed. And crossover and mutation are applied to each pair, generating N/2 offspring. Parents and newly generated off springs are ranked and the best individuals among them are selected for population in the next generation. Our G.N. terminates after 100 generations.

Crossover and mutation operators described as bellows.

Parents A B C D,… 

offspring AB  CD ,…

 we produce off springs by substituting the x values of 2 candidate parents.

And mutation (on for example A) is done by  where ∆ is the modules difference between ,  The fitness function calculated the coverage redundancy for each new coordinate produced by genetic algorithm(CRi). 

Finally the coordinate which best satisfies the fitness function will be chosen as our selected sensor node new position. The following algorithm describes the explained relocation process(Pm and Pc both considered .5 in this algorithm). 

 

 

Relocation Algorithm:

 

While (detects a coverage hole) do

for i=1 to K (the number of failed node neighbors)

                  sensor i  fuzzy-logic (i)

            end for

     (selected node) ID Max (sensor i)

     Domain area  circle (ID, RS)

  For is 1 to 100 (the number of generations)

compose initial population randomly

                         Apply crossover

                         Compose offspring

                         Apply mutation

                          Evaluate fitness function

                 Choose best chromosomes               for next generation

                   End for

Calculate the accessible energy of selected node

End while

 

 

 

 

 

As it is observed we used while loop in our algorithm which indicates that all the sensor nodes dislocate after node failure to compensate coverage-loss. The following figure describes the coverage improvement process.

 

 

 

 

 

 

5. Performance analysis and conclusion

 

One of the significant challenges in wireless sensor networks is coverage problem as redundant data and overlapped regions beside blank areas influence on QOS and power-efficiency in the network. On the other way the nature of WSNs makes users to apply random deployment so experiencing coverage holes and overlapped areas are inevitable. In this paper to overcome this problem we employ fuzzy-logic system which takes power-consumption into consideration along with uniformity (as a uniform network consumes energy more efficiently) and to reduce algorithm complexity and get the fast and optimized result in following we have the benefit of genetic algorithm which takes coverage redundancy into consideration.

We claim our proposed method is more energy-efficient than the previous researches as takes advantage of both fuzzy-logic and genetic algorithms simultaneously to solve coverage-problem and takes power-consumption and uniformity into account and also leads to fast and optimized output.

 

 

 

 

 

 

 

6. References

 

 [1]: A survey on sensor networks author={Akyildiz, Ian F and Su, Weilian and Sankarasubramaniam, Yogesh and Cayirci,Erdal},journal={Communications magazine, IEEE}, volume={40}, number={8}, pages={102--114},year={2002}, publisher={IEEE}

[2] : Wireless sensor networks: applications and challenges of ubiquitous sensing,author={Puccinelli, Daniele and Haenggi, Martin}, journal={Circuits and SystemsMagazine, IEEE}, volume={5}, number={3}, pages={19--31}, year={2005}, publisher={IEEE}

[3]: Coverage problems in sensornetworks: A survey},author={Wang, Bang}, journal={ACM Computing Surveys (CSUR)}, volume={43}, number={4}, pages={32}, year={2011},publisher={ACM}

[4]: A coverage-preserving node scheduling scheme for large wireless sensor networks, author={Tian, Di and Georganas, Nicolas D}, booktitle={Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications}, pages={32--41}, year={2002}, organization={ACM}

[5]: Estimating coverage oles sensornetworks},author={Ghosh,Amitabha}, booktitle={Local Computer Networks, 2004. 29th Annual IEEE International Conference on},year={2004}, organization={IEEE}

[6]:  The coverage problem in a ireless sensor network},author={Huang, Chi-Fu and Tseng, Yu-Chee},journal={Mobile Networks and applicaations},year={2005},publisher={Springer-Verlag New York, Inc.}

[7]:  Connectivity constrained wireless sensor deployment using multiobjective evolutionary algorithms and fuzzy decision making}, author={Pradhan, Pyari Mohan and Panda, Ganapati}, journal={Ad Hoc Networks}, volume={10}, number={6}, pages={1134--1145}, year={2012},

[8]: An exact algorithm for providing multi-perspective event coverage in wireless multimedia sensor networks, author={Yildiz, Enes and Akkaya, Kemal and isikoglu, Esra and others}, booktitle={Wireless Communications and Mobile Computing Conference (IWCMC), 2011 7th International}, pages={382--387}, year={2011}, organization={IEEE}

[9]: Virtual potential field based coverage-enhancing algorithm for directional sensor networks.}, author={Tao, Dan and Ma, Hua-Dong and Liu, Liang}, journal={Ruan Jian Xue Bao(Journal of Software)}, number={5}, pages={1152--1163}, year={2007}

[10]: A virtual centripetal force-based coverage-enhancing algorithm for wireless multimedia sensor networks}, author={Jing, Zhao and Jian-Chao, Zeng}, journal={Sensors Journal, IEEE}, volume={10}, number={8}, pages={1328--1334}, year={2010}, publisher={IEEE}

[11]: Coverage-enhancing algorithm based on overlap-sense ratio in wireless multimedia sensor networks}, author={Chen, Jian and Zhang, Lu and Kuo, Yonghong}, journal={Sensors Journal, IEEE}, number={6}, pages={2077--2083}, year={2013}, publisher={IEEE}

[12]: An efficient genetic lgorithm for maximum coverage deployment in wireless sensor networks}, author={Yoon, Yourim and Kim, Yong-Hyuk}, journal={Cybernetics, IEEE Transactions on}, volume={43}, number={5}, pages={1473--1483}, year={2013}, publisher={IEEE}

 

---