Coverage Improvement In Wireless Sensor Networks Based On Fuzzy-Logic And Genetic Algorithm
Subject Areas : Sensor Networks
Elaheh Radmehr
1
,
HASSAN SHAKERI
2
1 - Islamic Azad University Neyshabour Branch
2 - DEPARTMENT OF COMPUTER-FERDOWSI UNIVERSITY OF MASHHAD
Keywords: wireless sensor networks, coverage hole, Genetic algorithm, fuzzy-logic,
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
[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 S
is 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}