Topology Control in Wireless Sensor Network using Fuzzy Logic

محورهای موضوعی : Sensor Networks

Samaneh Nazari Dastjerdi ¹ (Science and Research Branch, Islamic Azad University, Tehran, Iran)
Hamid Haj Seyyad Javadi ² (Department of Mathematics and Applications, Shahed University)

تاریخ دریافت : 1393/11/14 تاریخ پذیرش : 1393/12/28 تاریخ انتشار : 1394/02/11

کلید واژه: Fuzzy Logic, Topology control, Wireless Sensor Network,

چکیده مقاله :

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 Membership functions Output Very low – low – middle – high – very high Current distance

 

TABLE 1 input functions Membership functions Input Very low – low – middle – high – very high %Residual Energy DiffMax/Min Covered Very near – near – middle – far – very far Proximity         Each input function has five membership functions

 

 

 

 

 

The architecture of the model is shown in fig 1.

 

3-input fuzzy Mamdani 125 rules Residual energy percentage   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 Current distance Proximity Diff Max/Min covered %Residual energy high Far high high middle middle low High Very high Very far high middle high Very far Very high low

 

 

 

 

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.

 

 

 

 

 

 

 

 

The fig (4) and (5) illustrate the mean and STD residual energy percentage when the network fails. As it can be

Fig. 2. Iteration of unreachable nodes

 seen100% energy has remained so the STD is meaningless. Because of the load balancing in 3-input fuzzy and Max, mean and STDhas remained steady.

 

 

 

 

 

 

 

 

Fig. 3. Packet delivery ratio

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fig. 4.Mean residual energy percentage

 

Fig. 5. The STD residual energy percentage

The tables (6) thru (10) are for networks with these properties:

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.

 

 

 

 

 

---