Topology Control in Wireless Sensor Network using Fuzzy Logic
Subject Areas : Sensor NetworksSamaneh Nazari Dastjerdi 1 , Hamid Haj Seyyad Javadi 2
1 - Science and Research Branch, Islamic Azad University,
Tehran, Iran
2 - Department of Mathematics and Applications, Shahed
University
Keywords: Fuzzy Logic, Topology control, Wireless Sensor Network,
Abstract :
Network sensors consist of sensor nodes in which every node covers a limited area. The most common use ofthese networks is in unreachable fields.Sink is a node that collects data from other nodes.One of the main challenges in these networks is the limitation of nodes battery (power supply). Therefore, the use oftopology control is required to decrease power consumption and increase network accessibility.In this paper, a network is modeled by a graph. Each vertex in the graphindicatesa sensor node and the edges display the communication links between them.Changes in the graph show changes in network topology and a different path to the sink.In this research, “fuzzy logic” is used for topology control. As the fuzzy logic utilizes optimized sensing radius comparing with minimum-maximum sensing radius, we expect less dead nodes, more mean residual energy and relatively more load balance in the network. At first, 2-input fuzzy algorithm was chosen. However 3-input fuzzy algorithm was also observed due to reasons explained in the main text. In both algorithms, we haveload balance in network and prolong network lifetime. Unreachable paths are less encountered with higher rates of packet delivery. The final standard deviation (STD) reaches to its minimum level, while the residual energy in sensors remains close to each other.
[1] paoloSanti. 2005. Topology Control in wireless AdHoc and sensor networks, wiley.
[2] Croce, Silvio, Francesco Marcelloni, and Massimo Vecchio."Reducing power consumption in wireless sensor networks using a novel approach to data aggregation." The Computer Journal 51, no. 2 ,2008.
[3] Nehra, Vibha, Raju Pal, and Ajay K. Sharma. "Fuzzy-based Leader Selection for Topology Controlled PEGASIS Protocol for Lifetime Enhancement in Wireless Sensor Network." INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY 4, no. 3 (2013): 755-764.
[4] S. Lindsey, C.S. Raghavendra,” PEGASIS: Power-efficient gathering in sensor information systems”, IEEE Aerospace and Electronic Systems Society, Proc of the IEEE Aerospace Conf, Montana, 2002:1125-1130.
[5] Wang, Xijun, Min Sheng, Mengxia Liu, DaosenZhai, and Yan Zhang. "RESP: A k-connected residual energy-aware topology control algorithm for ad hoc networks." In Wireless Communications and Networking Conference (WCNC), 2013 IEEE, pp. 1009-1014. IEEE, 2013.
[6] Huang, Yuanjiang, José-FernánMartínez, Vicente Hernández Díaz, and Juana Sendra. "Localized and Energy-Efficient Topology Control in Wireless Sensor Networks Using Fuzzy-Logic Control Approaches."Mathematical Problems in Engineering 2014 (2014).
[7] Wen, Longfei, Baihai Zhang, Senchun Chai, and Rui Zhao. "A Connectivity-Keeping Hierarchical Topology for mobile Wireless Sensor Networks." In Control and Decision Conference (CCDC), 2012 24th Chinese, pp. 3378-3383. IEEE, 2012.
[8] Akyildiz, Ian F., and Mehmet Can Vuran. Wireless sensor networks. Vol. 4.John Wiley & Sons, 2010.
6
Journal of Advances in Computer Engineering and Technology
Topology Control in Wireless Sensor Network using Fuzzy Logic
Received (Day Month Year)
Revised (Day Month Year)
Accepted (Day Month Year)
Abstract—Network sensors consist of sensor nodes in which every node covers a limited area. The most common use ofthese networks is in unreachable fields.
Sink is a node that collects data from other nodes.One of the main challenges in these networks is the limitation of nodes battery (power supply). Therefore, the use oftopology control is required to decrease power consumption and increase network accessibility.
In this paper, a network is modeled by a graph. Each vertex in the graphindicatesa sensor node and the edges display the communication links between them.Changes in the graph show changes in network topology and a different path to the sink.
In this research, “fuzzy logic” is used for topology control.
As the fuzzy logic utilizes optimized sensing radius comparing with minimum-maximum sensing radius, we expect less dead nodes, more mean residual energy and relatively more load balance in the network. At first, 2-input fuzzy algorithm was chosen. However 3-input fuzzy algorithm was also observed due to reasons explained in the main text.
In both algorithms, we haveload balance in network and prolong network lifetime. Unreachable paths are less encountered with higher rates of packet delivery. The final standard deviation (STD) reaches to its minimum level, while the residual energy in sensors remains close to each other.
Index Terms—Wireless sensor network, Topology control, Fuzzy logic
I. INTRODUCTION
W
ireless Sensor Network (WSN) is used to monitor a vast and remote region [1], WSNis composed of small sensor nodes collaborating among themselves [2].
Topology control is used in WSNs to achieve energy conservation and longer network lifetime. This technique applies fuzzy logic approach to control the topology of network.
All nodes in a network are randomly and uniformly deployed. First we use two inputs:Difference between the number of nodes with minimum-maximum sensing radius and Percentage of residual energy.However, because of a few disadvantagesanother input Proximity to sink was added.
This paper is organized as follows. Section II focuses on related works. Section IIIprovides formulationforenergy consumption. Section IV presents the proposed algorithm. Section V discusses thesimulation results followed by the conclusion part in section VI.
II. Related WORKS
In [3] fuzzy logic control is chosen to select leader in PEGASIS protocol. High power consumption in long chains is a disadvantage in PEGASIS [4]. In PEGASIS-TC, network topology concept is utilized for determining the node. Congestion in a spot in chain formationsavesthe energy and prolongs network lifetime. In additions to node’s residual energy and sink’s vicinity algorithm in fuzzy logic, leader is also chosen (not a very clear sentence).In [5], the proposed algorithm is referred to as Residual Energy-aware Shortest Path (RESP). RESP is a localized and distributed topology control algorithm. It provides fault tolerance and extended network lifetime, by varying battery drain rates at different nodes and repeating periodically to adaptively adjust the transmission power levels at each node. In every round, each node builds its local shortest path tree by considering residual energy of neighbor nodes. Then, additional edges are added to the local sub graph so that the k-edge connectivity is guaranteed.
RESP consist of four phases: information collection, topology construction, and transmission power control and edge augmentation.
In [6] two new fuzzy controllers are proposed: LFTC (Learning-based Fuzzy-logic Topology Control and RFTC (Rules-based Fuzzy-logic Topology Control).In LFTC controller is learnt from a training dataset and in RFTC controller is obtained through designing if-then rules and membership functions.
None of them rely on location information whilebeing localized. When a node fails in these models, energy-efficient communications improve the network connectivity because: 1) due to closed loop feedback, systems are able to trace the desired node degree as node density changes. 2) The average communication range is lower than other algorithms. 3) Systems are totally localized and anted controllers’ inputs are gained easily. 4) In networks with randomly failed nodes, (dynamic) connectivity shows to be still reasonable. In [7] a new algorithm is introduced for the mobile WSNs in which the distributions of the nodes are frequently changed. Here, two other topologies (chain-based and cluster-based) are compared with a topology called back-bone based. In this topology, the network is divided into upper and lower layers. In the upper layer, a backbone network is generated in which three kind of node are defined: 1) cluster- head node, 2) Gateway node, 3) Portal node. The rest are called ordinary ones. In this network, each sensor node only communicates with an ambient neighbor for data collection therefore the energy saving is highly obtained.
III. energy cost
In this algorithm, the formulas covered in [8] are used to calculate consumed energy for transmitting (ETx) and receiving (ERx)of a k bit message and a distance d=D(i,j) between them are shown as follows:
Energy for transmitting:
ETx= Eelec × k + Eamp × k×d2(1)
Energy for receiving:
ERx = Eelec×k(2)
The energy consumption is divided into the transmit electronics (Eelec) and transmitter amplifier(Eamp)
In this research, the distance between Node I and
Node j is represented by d=D(i,j) which is defined as:
D(i,j) =
(3)
Where
i,j = 1,2,3,…,n ; i≠j
xi ,yi are coordinate of node(i)
IV. the proposed algorithm
Our proposed fuzzy logic assignsthe amount of “current distance” to each node according to the inputs and defined rules.
Nnodes are located in an L×L sensor field. In the proposed algorithm, sensors’ locations are determinate by a random number generator. They are also able to collect data from all covered nodes for to decide which node will be used in the next step of data transmission.
Fuzzification Module
In this paper, fuzzy logic model of Mamdani and triangular membership function are used. Each input function has five membership functions that depict the degree of the membership function. Also the output function is consists of five. The four Fuzzification functions (inputs and output) are shown in tables 1 and 2 respectively.
TABLE 2 output functions
| ||||||||||||
TABLE 1 input functions
Each input function has five membership functions
| |||||||||||||||||
The architecture of the model is shown in fig 1.
Difference Max-Min covered current distance
Proximity to sink |
Fig. 1. System architecture
Our system consists of 25 rules for 2-input and 125 rules for 3-input in the fuzzy inference. The form of the rules is: IF A and Band C (C used for 3-input) THEN D, where A, B, C, D represent residual energy percentage, difference maximum-minimum covered, proximity to sink and current distance. Some examples of the rules are shown in Table 3.
TABLE 3 some examples of rules
|
The pseudo-code of the algorithm is given below:
Algorithm: Topology control in wireless sensor network using fuzzy logic
1) //Read Excel file that is containing properties of Nodes such as id, Xcor,Ycor, Residual Energy, Current Distance, Min Covered, Max Covered, Difference Max Min Covered, proximity to the sink
2) //N= Number of nodes
3) //Sink is nth nodes
4) //Proximity to sink is distance each node to sink
5) //ERxConsumption is energy using in receiving
6) //ETxConsumption is energy using in transmitting
7) //Read start nodes from text file
8) //Maximum energy of each node is 1j
9) //Minimum energy of each node is 0.1j
10) //Minimum distance each node can cover is 20m
11) //Maximum distance each node can cover is70 m
12) //Packet size is k=10,000 bit
13) for all of nodes do
14) Calculate Euclidean distance between nodes
15) end for
16) for all nodes do
17) Current Distance = Max Distance;
18) end for
19) while ~end of text file
20) Read start file
21) If Residual Energy of start node <Min Energy do
22) continue;
23) end if
24) calculate iteration
25) for all nodes do
26) if Euclidean distance between nodes is smaller than min distance
27) calculate Min Covered
28) end if
29) if Euclidean distance between nodes is smaller than max distance
30) calculate Max Covered
31) end if
32) end for
33) for all nodes do
34) calculate difference min covered and max covered
35) end for
36) open fuzzy file
37) for all nodes do
38) evaluate fuzzy rules according to inputs
(%Residual energy, DiffMaxMin covered, proximity) for 3input Fuzzy and
(%Residual energy, DiffMaxMin covered) for 2input Fuzzy
39) end for
40) draw graph
41) if distance from start node to sink=infdo
42) calculate iteration of unreachable nodes
43) end if
44) for all nodes do
45) //sending packet
46) If Residual Energy>Min Energy do
47) calculate ETxConsumption
48) end if
49) //receiving packet
50) If Residual Energy>Min Energy do
51) calculate ERxConsumption
52) end if
53) for all nodes do
54) If Residual Energy<Min Energy do
55) calculate dead nodes
56) end if
57) end for
58) end for
59) end while
The descriptions of Pseudo-Code are given below:
Line14: The distance between all nodes are calculated by equation (3) and are inserted in N×N matrix.
Line17: While the fuzzy logic is not determined yet, covered distance for all nodes will be equal to maximum distance before starting the program.
Line21: Starting point is checked for having minimum energy and being alive.
Line25 thru 32: The numbers of accessible nodes are verified according to the number of nodes located in between minimum/ maximum transmission radius.
Line34: Above mentioned amount will be one input for each node fuzzy logic system.
Line38: 2-input fuzzy system is used in this paper. The residual energy of a sensor, the difference numbers of nodes located between minimum/ maximum distance and finding the nearest node to sink within permitted radius are three criteria from which the first two are used in 2-input fuzzy and all of them are used in 3-input fuzzy systems. The current distance for each node is calculated according to the used algorithm.
Line40: When current distance for a node is verified, the nodes located in the vicinity would be defined. Graph theory is used to determine the path between these nodes.
Line44 thru 52: The energy of nodes involved in a transmission path is deducted according to equation (1) and (2) which residual energy is updated for each node. Both the source and the sink loose energy for transmittance and reception respectively.Depending to their function the remaining nodes in the path loose both kinds.
In each step, the residual energy is checked with a minimum level of energy, defined at the beginning of each algorithm.
Line54thru 57: If residual energy is less than the minimum level, the node fails, its relation with other nodes terminates, the received packet is decreased, it is deleted from network topology, creating the hole instead.
Below parameters are calculated in this research:
• The total of unreachable nodes
• The mean and the STD residual energy
• The percentage of successful transmission
• The number of program iteration in which first node dies.
In proposed algorithm definitions of network lifetime are:
1) The first node to die (the network died when the residual energy of node is less than the threshold).
2) When a node lose connection with other nodes.
V. simulation results
We simulated our algorithms in MATLAB R2012a to verify our results. We consider other two algorithms: Min which node covers minimum radius and Max which node covers maximum radius.
TABLE 4
assumption issue
value | parameter |
1.0 j | Maximum energy of node |
0.1 j | Minimum energy of node |
70m | Max Distance |
20 m | Min Distance |
50 nj | Eelec |
10000 bit | K |
50 ,100 | Number of nodes |
Randomly placed within the sensing region | Initial node location |
50 pj | Eamp |
(0,0) | Place of sink |
The table (5) and fig (2) thru (5) are for networks with these properties:
Number of Nodes =50 and iteration=10,000
TABLE 5
first iteration dead node
200×200 | 150×150 | 120×120 | 100×100 | 80×80 | Network size | |
- | - | 875 | 1616 | 1344 | Min | |
966 | 1097 | 1464 | 1264 | 967 | Max | |
- | - | 568 | 988 | 2844 | 2-Input Fuzzy | |
622 | 1019 | 1013 | 3812 | 3023 | 3-Input Fuzzy | |
Table (5) illustrates five networks size for showing the number of program iteration in which first node dead.
Overall, it can be seen that when the network size became larger, in Min and 2- inputs fuzzy algorithms the first node dies earlier than 2 other algorithms. “-“indicates network failure. Because of load balancing in 3- input fuzzy algorithm, sensor nodes collaborate with each other so the lifetime of sensor nodes can be prolonged.
Figure (2) shows the iteration of unreachable nodes when the size of network became large and number of neighbors became unreachable. They are not able to cover each other, because it will result in network disconnection. According to fig (2), (3) in 3-input fuzzy and Max algorithms, unreachable node does not occur and the sink receives all of packets. The packet delivery ratio is 100% which in Min and 2- input fuzzy arein smallest ratio.
Fig. 2. Iteration of unreachable nodes
|
Fig. 3. Packet delivery ratio
|
Fig. 4.Mean residual energy percentage |
Fig. 5. The STD residual energy percentage |
Network size=100×100 and iteration=10,000
TABLE 6
first iteration node dies
3Input Fuzzy | 2Input Fuzzy | Max | Min | algorithm |
3812 | 988 | 1264 | 1616 | 50 nodes |
1143 | 1096 | 837 | 1204 | 100 nodes |
TABLE 7
iteration of unreachable nodes
3Input Fuzzy | 2Input Fuzzy | Max | Min | algorithm |
0 | 216 | 0 | 1222 | 50 nodes |
0 | 0 | 0 | 0 | 100 nodes |
TABLE 8
packet delivery ratio
3Input Fuzzy | 2Input Fuzzy | Max | Min | algorithm |
100 | 97.623 | 100 | 86.4896 | 50 nodes |
100 | 100 | 100 | 100 | 100 nodes |
TABLE 9
mean residual energy percentage
3Input Fuzzy | 2Input Fuzzy | Max | Min | algorithm |
64.386 | 53.199 | 58.234 | 58.982 | 50 nodes |
68.249 | 71.240 | 80.804 | 68.96 | 100 nodes |
TABLE 10
std residual energy percentage
3Input Fuzzy | 2Input Fuzzy | Max | Min | algorithm |
26.47 | 28.1515 | 18.1403 | 33.8585 | 50 nodes |
23.4131 | 26.9609 | 10.9294 | 29.5138 | 100 nodes |
With increasing number of nodes in the network, we expect nodes centralize in a place with more collaboration between them. This causes nodes to consume energy while they send and receive packets and die faster.
When the number of nodes increases, the central nodes in the transmission of the packets increase as well. This also causes energy lost in most of the nodes and result in them dying faster.
As mentioned, centralize nodes prevent the unreachable nodes to occur more frequently. Furthermore packet delivery ratio will increase.
VI. conclusion
Although nodes decision making, takes place locally in our algorithm. However by omitting required energy to contactthe main decider node, packet transmissions occur faster with more power consumption efficiency.
This algorithm is a time-driven procedure, instead of event-driven. In order to overcome this void, a new column can be added to node definition Excel file, showing the dead nodes to their ambient partners.
In 2-input fuzzy algorithm, according to each node the fuzzy logic output covers a part of its maximum radius. Meanwhile if this node adds a new criterion forselecting next node to the selection process (e.g.) finding accessible nodes which are closer to sink- the probability of reaching for a finer node with better access and less distance to the sink will efficiently increase. This leads us to a new 3-input fuzzy algorithm. In this algorithm the above mentioned rule is considered in conjunction with two other criteria: node’s residual energy and the difference number of nodes covered by maximum and minimum radius respectively. Less number of involved nodes in packet transmission, less dead nodes and less unreachable nodes are considered as benefits for recent algorithm.
According to simulation, algorithms which use fuzzy logic are energy efficient. This is because of the defined rules and nodes sensing percentage of maximum radius. This causes nodes to not waste energy so the residual energy is much more than the others. With fuzzy logic most of the nodes will collaborate. This collaboration of the nodes will result load balancing in network. So the nodes in this algorithm will survive longer than others which cause an increase in packet deliverty ratio.
In Min algorithm, because of the sensing minimum radius, there will be more unreachable nodes. This will result low Packet delivery ratio.
Fuzzy logic systems encounter some problems in accordance with changing environments.Therefore, utilizing the neural networks’ learning concepts in fuzzy systems, which is often named neural modeling, is presumed a good substitution in future networks.
References
[1]paoloSanti. 2005. Topology Control in wireless AdHoc and sensor networks, wiley.
[2]Croce, Silvio, Francesco Marcelloni, and Massimo Vecchio."Reducing power consumption in wireless sensor networks using a novel approach to data aggregation." The Computer Journal 51, no. 2 ,2008.
[3]Nehra, Vibha, Raju Pal, and Ajay K. Sharma. "Fuzzy-based Leader Selection for Topology Controlled PEGASIS Protocol for Lifetime Enhancement in Wireless Sensor Network." INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY 4, no. 3 (2013): 755-764.
[4] S. Lindsey, C.S. Raghavendra,” PEGASIS: Power-efficient gathering in sensor information systems”, IEEE Aerospace and Electronic Systems Society, Proc of the IEEE Aerospace Conf, Montana, 2002:1125-1130.
[5] Wang, Xijun, Min Sheng, Mengxia Liu, DaosenZhai, and Yan Zhang. "RESP: A k-connected residual energy-aware topology control algorithm for ad hoc networks." In Wireless Communications and Networking Conference (WCNC), 2013 IEEE, pp. 1009-1014. IEEE, 2013.
[6] Huang, Yuanjiang, José-FernánMartínez, Vicente Hernández Díaz, and Juana Sendra. "Localized and Energy-Efficient Topology Control in Wireless Sensor Networks Using Fuzzy-Logic Control Approaches."Mathematical Problems in Engineering 2014 (2014).
[7] Wen, Longfei, Baihai Zhang, Senchun Chai, and Rui Zhao. "A Connectivity-Keeping Hierarchical Topology for mobile Wireless Sensor Networks." In Control and Decision Conference (CCDC), 2012 24th Chinese, pp. 3378-3383. IEEE, 2012.
[8] Akyildiz, Ian F., and Mehmet Can Vuran. Wireless sensor networks. Vol. 4.John Wiley & Sons, 2010.