Journal of Communication and Computer 9 (2012) 28-32
Three Dimensional Fault Tolerant Energy Efficient Distributed Clustering for Wireless Sensor Networks (3DFEED)
茉莉花 英文Mohammad Hasannejad1, Mohammad. Mehrani1 and Amir Afsheh2
1. Department of Computer Science, Andimeshk Branch, Islamic Azad University, Andimeshk, Iran
2. Department of Computer Science, Shoushtar Branch, Islamic Azad University, Shoushtar, Iran
Received: September 22, 2011 / Accepted: October 23, 2009 / Published: January 31, 2012.
Abstract: An important issue in WSN (Wireless Sensor Networks) is the regional covering. A coverage algorithm should solve this problem by considering the power consumption to improve the network lifetime. This requires employing the lowest number of nsors. Clustering is an approach by which network nodes are organized into some partitions named cluster. This is a uful method as the ba of coverage methods. In this paper we try to perform clustering in real three dimensional regions as our purpo. Recently we prented FEED clustering algorithm for two dimensional regions. Now, 3DFEED denotes some clusters for real world of wireless nsor networks. This algorithm achieves at f
ull coverage in three dimensional wireless nsor networks. After making sure about dividing all the network nodes into some clusters full coverage will be satisfied. Also considering three dimensions for the network clustering method increas the accuracy of network partitioning such that more energy efficiency would be performed which conquently increas network overall lifetime.
maximum是什么意思Key words: Wireless nsor network, cluster head, supervisor node, energy efficiency, life time.
1. Introduction
Wireless Sensor Networks consist of a huge number
of nsor nodes, with limitations like their energy resources, disperd in a region. All network nodes have wireless communications and nd information about their region to a ba station either directly or via other nodes. Energy efficiency is one of the most important factors in wireless nsor networks. Routing plays a critical role in energy efficiency, so a suitable routing protocol should be lected for this purpo. Clustering is an approach by which, all network
Mohammad Hasannejad, graduate student, rearch fields: wireless nsor networks, Ad hoc. E-mail: **************************.ir.
Amir Afsheh, graduate student, rearch fields: wireless nsor networks, computer software. E-mail: *****************.
Corresponding author: Mohammad Mehrani, graduate student, rearch fields: wireless networks, Ad hoc. E-mail:
**************************.ir.nodes are organized into clusters and communicate with a cluster head which forwards received data to ba station. Clustering aims at achieving an energy efficient routing protocol. In clustering, every cluster has a cluster head. In every round, some nodes are lected to act as cluster heads and regular nodes try to join to the nearest clusters.
In some clustering algorithms, cluster heads are lected randomly in every round [1]. Some others are nsitive to energy, distance, etc. like the algorithms mentioned in Refs. [2-3]. Moreover, the algorithm mentioned in Ref. [3] has tried to u other techniques including fuzzy logic to form clusters.
Selecting suitable cluster heads can lead to a decrea in overall energy consumption and also an increa in network lifetime.
Some clustering algorithms like FEED [4] pay
attention to some very important factors like energy,
l Rights Rerved.
Three Dimensional Fault Tolerant Energy Efficient Distributed Clustering for Wireless
Sensor Networks (3DFEED)
29
density, centrality and distance between nodes to form clusters. FEED propo an energy efficient clustering method which lects suitable cluster heads by paying attention to energy, density, centrality and the distance between nodes for making clusters. Moreover, in this approach every cluster head has a supervisor node. This property leads to an increa in network life time and also a fault tolerant clustered network.
Lots of recent prented clustering algorithms have considered two dimensions for performed wireless nsor network while in practice the networks are utilized in three dimensional areas. The methods are two dimensional which is against the real three dimensional entity of the networks. Paying attention to the third dimension of the region is the purpo of our new prented clustering method that is bad on our last work (FEED) considered for two dimensional world. 3DFEED is the result of applying a big enhance in FEED. All the network activities and nsor functioning for making clusters in all the states of this new method are done in three dimensional world. So the conditions are considered in calculations.
In Section 2, we review related works. Then we describe our propod algorithm in Section 3. Section 4 reveals the evaluation of the performance of the propod algorithm. We conclude in Section 5, with a summary of the contributions of the propod approach.
2. Related Works
2.1 Leach
LEACH (Low Power Adaptive Clustering Hierarchy) is an algorithm ud for clustering in WSN. In this algorithm, there is a probability formula for every node to be a cluster head in every round. At the
beginning of every round every node choos a random number between 0 and 1. There is a threshold number T(n) which varies in every round. The node can be a cluster head in the current round if the random number chon by it is less than T (n). If a node decides to be a cluster head in a certain round, it informs other nodes about this fact by broadcasting a message. Then every regular node joins the nearest cluster. The LEACH probability formula is:
))))
(
/1
mod(
(*)
(
1/()
(
)
(n
p
r
yieldedn
p
n
p
n
T-
=∀G
n∈(1) Where n is the number of network nodes, r is the number of the round, G is the t of nodes that have not been cluster head in the last 1/p rounds and p is the desired percentage of cluster heads which equals to 0.05. This formula lets every node to have the chance of being a cluster head once in every 1/p rounds. LEACH enhances network lifetime and energy consumption compared with the Direct algorithm. One shortcoming of LEACH is that it does not consider the energy factor in lecting cluster heads. Thus chon cluster heads are not always suitable for the network. 2.2 HEED
In HEED (A Hybrid, Energy-Efficient, Distributed Clustering) veral iterations are needed to choo a cluster head. The time slice for each iteration should be long enough for a node to receive all nt messages from its neighbor nodes. All nodes assume the initial probability to become a cluster head as follows:
皮袍max
E
E
C
CH residual
prob
prob
⨯
=(2) At the beginning of each round all uncovered nodes
decide to be cluster heads with probability
prob
CH. If a node decides to be a cluster head, it broadcasts a message to other nodes. In this message if
prob
CH is less than 1, the node introduces itlf as a tentative
cluster head. If
prob
CH is equal to or greater than 1, the node introduces itlf as a final cluster head. At the end
of each iteration all nodes double their
prob
CH. A node assumes itlf covered if it is covered by at least one tentative or final cluster head. If at the end of a round, a certain node is not covered by any tentative or final cluster head, it reveals itlf as a final cluster head. Then each node joins a cluster which generates the lowest cost for it.
leisuretime2.3 Feed
FEED (Fault Tolerant, Energy Efficient Distributed
l Rights Rerved.
Three Dimensional Fault Tolerant Energy Efficient Distributed Clustering for Wireless
Sensor Networks (3DFEED)
30
专业日语翻译
Clustering for Wireless Sensor Network) lects the cluster heads bad on factors such as: energy, density, centrality and distance between nodes. FEED algorithm executes in four phas. In the first pha each nsor node nds its id and coordinates to around neighbours and receives same messages from them. By doing such, each node can compute its density and centrality. A new method for computing centrality factor is also introduced in FEED algorithm. Each node calculates its first score by mixing energy, centrality and density factors and getting an average from them.
In the cond pha, tho of nodes that their energy and density factors are good introduce themlves as volunteers. Then in the third pha, each node gives cond scores to its near volunteers by entering distance factor to first scores of the volunteers and reveals a volunteer with best cond score as its deputy. In the fourth pha volunteers calculates their final scores and according to that reveals themlves as CH, PCH or SN nodes. Then regular nodes join to nearer clusters.
This algorithm improves the network lifetime in a significant way in comparison with two well known clustering algorithms LEACH [1] and HEED [2]. Furthermore, FEED algorithm leads the network to b
e fault tolerant. Fig. 1 shows the improvement of network life time by FEED in comparison to LEACH and HEED algorithms. In FEED when the remained energy of a cluster head falls under a threshold, its supervisor node will replace it and the cluster can continue its activity by the new cluster head. This property leads network to be fault tolerant. According to Fig. 1, FEED algorithm improves network lifetime in comparison to two other algorithms. Supervisor node replacement can be a reason for this enhancement.
Fig. 2 shows the percentage of total remaining energy of the network nodes after 1, 20 and 50 rounds. After one round, HEED algorithm outperforms the best, but in later rounds FEED algorithm performance is the best. After round 300 only FEED algorithm is still
Fig. 1 Total number of nodes per rounds.
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
12050
R
e
m
a
i
n
e
d
E
胖人穿什么好看n
e
r
g
y
P
e
r
c
e
n
t
a
g
e
Rounds
Percentage of Total Remained Energy of the Network
FEED
LEACH
HEED
汽车安全气囊检测Fig. 2 Percentage of total remained energy of the network nodes.
executing, but LEACH and HEED algorithms have terminated. Fig. 2 shows that FEED significantly improves the network energy consumption.
3. The Propod Algorithm
The propod algorithm prents a new method for grouping the three dimensional networks in to three dimensional clusters. For briefness we avoid writing the details of 3DFEED similar to tho performed in FEED but the important changes would be mentioned as well.
3DFEED is an enhancement for FEED. The first change in FEED is to consider z axis (height) of all the nsor nodes in all the calculations rather than x and y
l Rights Rerved.
Three Dimensional Fault Tolerant Energy Efficient Distributed Clustering for Wireless
Sensor Networks (3DFEED)
31
axis. Sensor nodes are equipped with GPS and are aware about their exact positions. So they know about their height and assume it as another factor of their coordinates. The height of a node will be ud wherever needed, for examples in calculating the density in the first pha, in giving scores to
volunteers and also themlves during algorithm execution, etc. The area that 3DFEED considers is like Fig 3. This figure shows a 100 × 100 × 100 region that nsor nodes are disperd in. So it has x, y and z axes that reprent the three dimensions of a real network. Like FEED, 3DFEED executes in four phas: in the first pha each network node evaluates its situations and decide whether to be a volunteer or not while in the cond pha all the nsor nodes give scores to the volunteers. The volunteers calculate their final scores in the third pha and finally in the fourth pha they introduce themlves as cluster heads, pivot cluster heads or supervisor nodes.
One of the most important differences between FEED and 3DFEED is the pha of calculating angles between two nodes meaning the centrality calculation pha. For this purpo first the mentioned angle bad on x axes is calculated as follows:
Fig. 3 The network nodes are dispersd in a 100 × 100 × 100 region.
ӨNodeID = arc tan ( NodeID.Y-me.Y/
NodeID.X-me.X ) (3) Now calculating this angle bad on y axes would be considered as following:
ӨNodeID = arc tan ( NodeID.Z-me.Z/
NodeID.X-me.X ) (4) For example, the x bad angle which is rated from 0o to 360o maybe equal to 12o which is to be calculated using formula (3). This angle will be put in the corresponding element of an array of 24 elements. Then y bad angle using formula (4) would be achieved. This angle also can be rated from 0o to 360o so an array of 24 elements should also be ud to save this angle. Thus a 24 × 24 element matrix would be utilized for this purpo. This matrix is shown in Fig 4. The best situation for centrality factor occurs when the content of element (i, j) and element (I + 12, j) of the matrix are equal. If this difference equals zero then the corresponding node has best possible situation for centrality factor. Suppo B as the mentioned matrix; we u an array for saving the mentioned differences as follows:
C(i) = |B(i, j)-B(i+12, j) | (5) Then the summation of all the C array elements shows the centrality fact
or. As mentioned before, if this digit is equal to zero then the corresponding node is placed exactly at the center of its neighbours.
4. Performance Evaluation
reply什么意思
Now, in this ction we evaluate the functionality of the propod algorithm. We ud Matlab as a well known and powerful programming software to simulate our works. As can be en in Fig. 5 using the new prented three dimensional clustering method leads increasing network overall lifetime as well. This figure is the result of simulating both FEED and 3DFEED and comparing them. Bad on this figure FEED finishes after 600 rounds while 3DFEED continues until round 750. This event shows 25% increasing in network lifetime which is a good achievement.
l Rights Rerved.
Three Dimensional Fault Tolerant Energy Efficient Distributed Clustering for Wireless
Sensor Networks (3DFEED)底盘装甲是什么
32
Fig. 4 The matrix ud by each node to calculate its centrality.
Fig. 5 Total number of nodes per rounds.
5. Conclusions
In this paper we prented an extension and significant improvements in FEED algorithm [our last work] for clustering three dimensional wireless nsor networks. In this work network clustering method performs in real three dimensional environment and all the operation and calculations execut
es in such a region. The simulation results demonstrate the satisfying functionality of our new propod approach.
Acknowledgment
This paper is the result of a rearch program done by scientific board members of Department of Computer Science, Andimeshk Branch, Islamic Azad University, Andimeshk, Iran. References
[1]W. Heinzelman, A. Chandrakasan, H. Balakrishnan,
Energy-efficient communication protocol for wireless
micronsor networks, in: Proc. of the 33rd Annual
Hawaii International Conference on System Sciences
(HICSS), Maui, 2000, pp. 3005-3014.
[2]O. Younis, S. Fahmy, HEED: a hybrid, Energy-efficient,
distributed clustering approach for Ad-hoc nsor networks,
NSF grant ANI-0238294 (CAREER) and the Schlumberger
Foundation.
[3]I. Gupta, D. Riordan, S. Sampalli, Cluster-head Election
using Fuzzy Logic for Wireless Sensor Networks, Proceedings of the 3rd Annual Communication Networks
and Services Rearch Conference (CNSR’05), 2005.
[4]M. Mehrani, J. Shanbehzadeh, A. Sarrafzadeh, S.J.
Mirabedini, C. Manford, FEED—Fault tolerant Energy
Efficient Distributed Clustering for Wireless Sensor Networks, The 12th International Conference on Advanced Communication Technology (ICACT2010),
2010, Phoenix Park, Korea.
l Rights Rerved.
