Routing in Wireless Sensor Networks with Asymmetric Links
Laxita Vyas1 Ph.D Research Scholar,
JECRC University,Jaipur(Rajasthan), India.
[email protected] Dr. Manoj Gupta2 Associate Professor
Department of Electronics and Communication Engineering, JECRC University,Jaipur (Rajasthan)India.
Abstract—Energy utilization is a significant factor while designing a routing algorithm in Wireless Senor Networks (WSN).
In Wireless networks, network lifetime is directly related to energy consumption of senor nodes. Initial energy of nodes reduces at every transmission of data packets and once complete energy of nodes depletes node dies and replacement of battery is not possible in every case due to hassle environment. To improve lifetime period sensing, aggregation and transmission function performs in such a way that minimizes the energy consumption. Direct transmission of data from sensor to Base station consumes more energy; hence it is important to choose routing that had energy efficient mechanism. In proposed work, clustering algorithm used to organize nodes into cluster for transmission of data from nodes to base station.
Proposed algorithm works well in both centralized and distributed environment. Proposed routing Cluster formation and selecting cluster head, which transfer data from their cluster nodes to base station, uses hierarchical clustering algorithm and considers distance parameter, energy index and RSSI value to compute proximity matrix for forming clusters. In proposed algorithm randomized and distributed approach taken which exhibits improvement in network lifetime by reducing energy consumption while transmission. Comparison of results with exiting algorithm shows the better performance of proposed algorithm.
Keywords—Clustering, WSN, Asymmetric Links, DHAC, Cluster Head
I. INTRODUCTION
Wireless Sensor Network is a self-configured and distributed network comprises of tiny and low powered devices known as sensors to monitor and gathers information from surrounding environment .WSN shows its impact in diverse application areas [1, 2]. In WSN, randomly distributed sensors from hostile environment collect data and transmit it to Base Station for further processing. Sending data packets directly to Base Station consumes more energy by sensors that are far away from Base Station that result in fast depletion of energy rate as compared to the nodes that are located at smaller distance from Base Station. Sensor becomes inoperable once all energy depletes. Energy utilization is directly proportional to radio transmission in wireless sensor network. Clustering algorithm shows improvement in network lifetime as compared to direct transmissionas in clustering nodes consumes less energy as rather than sending data to Base Station located at far, it transmits to nearest node which further responsible of transmitting data to Base station in an aggregated manner. Hierarchical clustering starts forming cluster on basis of some resemblance matrix. Nodes start organizing in cluster with their neighbour on basis of proximity matrix. After cluster formation, randomized approach is used to calculate probability of nodes to become a cluster head. Node with high probability value among cluster is selected as cluster head. Proximity matrix is important factor while creating cluster. In proposed work proximity matrix comprises of functional value of Euclidean distance between nodes, residual energy index and Received Signal strength indicator (RSSI).
Computed value of transmission cost including above factors make asymmetric communication as transmission cost of sending data from node A to node B is different than sending data from node B to node A. This asymmetric type of transmission helps in taking all above factors into account while cluster formation and cluster head selection which results in better performance as compared to pre-exists routing algorithm where mostly algorithm considers symmetric communication costs while transferring data from nodes to Base station.
II. RELATEDWORK
Energy efficient routing is a broad area of research, many researchers analysis the efficiency of routing algorithm.
In energy efficiencyanalysis, LEACH [5] is the foremostalgorithm; LEACH follows TDMA approach to transmit data packets. LEACH operates in two phases. In phase one, node starts organizing them in cluster and selects cluster head with high probability value node which serve as local base station. In second phase, transmission of
data, aggregated at cluster head, to base station occurs. LEACH is randomized and distributed approach to increase life-span of network. LEACH major drawback is random and variable amount of cluster and energy index is does not taken into account while forming a cluster.
LEACH-C [6] is acentralizedapproach of LEACH protocol. In LEACH – C, Base station have prior global knowledge of network. Cluster head selection done by base station by taking residual energy of node into account.
There is no contact between nodes. Rest functionalities are similar to LEACH protocol. In LEACH –C due to global knowledge of network, optimal cluster formation done at base station that result in reduction in energy consumption by node as in LEACH energy required by node in forming cluster and choosing cluster head.
PEGASIS [7] shows better network life expectancy rate as compared to LEACH protocol. PEGASIS forms a chain like structure where each node received data packets from their closest neighbour. Data gathered at each node move from one node to another until Cluster head transmits data to base station. Cluster Head at each round is elected by i mod N, where i is the round number and N is the number of node in network. Major drawback of PEGASIS is distance and energy parameters are not taken into account while selecting cluster head which in worst case scenario node with less energy as compared to other node in network selects as CH and dies early.
Another drawback is that only one node is selected as CH among whole network which increases the load on single node that results in fast energy depletion rate.
HEED [8]protocol removes some of the major drawbacks of LEACH protocol. Rather than selecting cluster head randomly as in LEACH, HEED selects cluster head on basis of residual energy and inter cluster communication cost. Initially each computes their probability to become cluster head by CHprob=Cprob*Eresidual/Einitial, node starts communicating with their CHprob with one another till each nodes finds their CH that transmits data to Base Station with minimum energy. Node that not finds their respective CH elects itself as CH with single node with its own cluster. HEED helps in load balancing by uniform distributing CH across the network but number of iterations increases overhead in transmission.
In EECH [9] algorithm, each node within a network declare itself as CH with probability p. This type of cluster head is termed as volunteer CH. These CH advertise themselves as cluster head to the node that are k hops away.
Any node receive this advertisement and not CH, aggregated itself with the cluster of closest CH. Node that are neither cluster head nor part of any cluster declare themselves as forced cluster head. Advertisement for joining cluster broadcasts for time duration t, any node that not receives a message within time duration t; declare itself as forced Cluster head. The energy consumption depends on two factors p and k. EECH follows approach that suggests the environment needs to be contaminated so node do not transmits data again and all nodes have same power level that result in same radio range r. EECH shows better performance in life span of node as compared to LEACH protocol.
RRCH [10] creates static size of cluster in beginning of transmission and works on round robin approach to selects the node as cluster head. RRCH does not use re-clustering which results in bad quality cluster as either too large or too tiny cluster creates.
V-LEACH [11]handles problems in LEACH when cluster head dies while transmission of data from cluster head to base station, in this scenario V-LEACH along with primary CH selection, it also selects some other node as CH that termed it as vice cluster head which takes the responsibility of CH when primary cluster head dies. V- LEACH has issues in transmission when there is no CH presents in the network.
HAC (Hierarchical Agglomerative Clustering) [12] is the hierarchical clustering approach which forms the cluster in a tree shape like structure.HAC is a top-down approach where CH selected firsts and on the basis of cluster head, cluster formation occurs. HAC is the centralized architecture where base station has prior global knowledge.
Nodes start organizing in cluster on basis of resemblance matrix. Process continues till all nodes in the network are not associated themselves with any cluster.
DHAC [12] DHAC overcomes the limitation of HAC algorithm. It is a distributed algorithm where first cluster formation stage completes, then cluster head selection done. IN DHAC, nodes are formed into clusters on basis of resemblance matrix. Resemblance matrix formed by the distance between two nodes. Each node in the network has one-hop neighbor information. Node starts communication by sending HELLO message to all other node that is at one-hop distance. In response to this message node share their location, RSSI and residual energy value.
After receiving response message, nodes starts organizing them in cluster and node with lowest ID are selected as CH. This minimizes the energy utilization required in CH selection. DHAC performs HAC algorithm after computing proximity coefficient. DHAC shows better performance in energy utilization and network lifetime as compared to pre-existing, LEACH and LEACH –C algorithm. DHAC not works well in failure of GPS and also GPS enabled system costs more.
H-DHAC [13] overcomes the GPS limitation of DHAC algorithm. H-DHAC required two kinds of data for clustering: (a) Qualitative Data (include binary number 0 and 1 to indicate whether nodes are connected or not).
(b) Quantative data (location information). To avoid randomness in CH selection, H-DHAC uses two factors (1) CL (Confidence level) and (2) Cmin which helps in selecting cluster head in view where location of information of node is missing.
[15 Sichitu and Ramadurai]Localization is the way of calculating position of node in wireless sensor network.
Localization is important for different types of observations such as acoustic, thermal, seismic etc. GPS provide accurate location information but due to costs involved in extra hardware and inappropriateness for indoor area make it less valuable in different environment conditions. RSSI estimates the coordinates of sensor nodes to find location of node within network without need of any additional hardware.
III. PROPSOEDWORK
Proposed algorithm is based on hierarchical clustering architecture. As proposed approach uses resemblance coefficient a function of RSSI, energy and distance, communication between nodes becomes asymmetric in transmission cost from node A to node B is not equivalent to node B to node A. In proposed approach, first, nodes starts organizing themselves into cluster and after cluster formation cluster head selection done, cluster head selected on basis of RSSI and energy index.
The following assumptions are made for an algorithm:
Base station has central fixed location in the network.
Each node communicates to each other through their RSSI (Received Signal Strength Indicator).
Each node in the network has same initial energy level.
Processing capabilities of sensor may differ at different time instance as energy index and distancehas different value.
3.1 Cluster Formation
Step I: Local Information gathering
Node exchanges JOIN message with all other node that are at 1-hop distance. These messages from nodes contain their residual energy, RSSI and their ID.
Step II: Proximity matrix
Calculating the distance between two nodes using RSSI value received. After which resemblance matrix is created on the basis of location information in first round as initially energy is same of every node while in other round functional value of energy and distance is used which results in asymmetric nature of communication as energy vary of nodes vary after each round of communication.
Step III: Clustering
Cluster formation involves several iterations till all nodes that are on hop distance are not associated with any cluster. Nodes that are unreachable declare themselves as singleton CH which directly transfers data to base station.
For creating clusters, nodes starts organizing themselves into group in hierarchical way using average linkage criteria, each node computes its proximity coefficient as function of RSSI, energy index and calculated Euclidean distance, after final matrix computation where each node either associate themselves with any cluster or declare themselves a singleton CH, selection of CH steps within the cluster starts.
Step IV: Cluster Head Selection
According to the energy model given by [5] –
2, 0)
( ) ( , )
4, 0) mEelec m fsd d d ETx ETx elec m ETx amp m d
mEelec m ampd d d
• m is the number of bit forwarding on the distance d.
• Eelec is the transmitter circuitry dissipation per bit.
• ε is the transmit amplifier dissipation per bit.
• ETX is the transmission energy
The receiving cost is:
( ) . 2
. 2
ERx ERx elec m mEelec
N N
ECH L Eelec LEDA L fsd toBS
k k
ENonCH L Eelec L fsd toCH ETotal= k * ECH+ nENon-CH
2 2
ETotal= nLEelec+ nLEDA + k.Le dfs toBS• + nLEelec+ nLe dfs toCH
M2 E[dto CH2 ] =
2 k M2
nEelec+ nEDA+ k fsd2toBS+ nEelec + n fs = 0 2 k
Differentiating above eq. w.r.t k and equalizing equation to zero
2 0 2
2
2
k M n fs d toBS
fs
dtoBS M n
k 2
According to [9]
dtoBS=0.3826*a
Substituting value of dtoBS in above eq. –
0.9587 n k
Since there are on an average n*p cluster heads so value of k equal to n*p where p is the probability of becoming CH-
k = n*p
9587 . 0
* 1 n p
The proposed algorithm comprised of the following steps for communication in WSN-
Fig.1 Energy Model
I. Initialization
Node presented in a network identified their neighbouring nodes that are suited at their one hop distances.
II. Each node starts computing its proximity value from another node that respond to their Hello message by below formulae,
B y A x
y x proximity
B A n n B A
C
,
) , (
* )
* / 1 ( ,
III. Cluster Head Selection for r =1 to rmax
for i= 1:N
t(i)= p*(Er/Ei) end of for loop [C,ind]=max(t)
Node i with index ind would be selected as cluster Head end of for loop
3.2 Clustering algorithm
Transmission of data packets from nodes to Base station involve below listed steps:-
1. Advertisement Phase: All nodes within cluster broadcasts JOIN message as the invitation message with their probability values of becoming cluster node. Nodes start organizing them in cluster by responding to JOIN message which includes their RSSI value and energy index. Node with maximum probility value declares itself as cluster for that particular round. Cluster head sends an acknowledgement message to other node informing them that they are now part of its cluster.
2. Aggregation Phase: In this phase sensors node starts sensing data from environments and wait for their turn to transmits data to cluster head as cluster head create TDMA schedule so that collision not happens among nodes. All nodes’ data within cluster are aggregated at cluster head.
3. Transmission Phase: Aggregated data packets from all nodes within cluster at cluster head, starts transmitting by cluster head to base station.
IV. EXPERIMENT&RESULT
To analysis the performance of algorithm MATLAB 2016a is used for simulation. For simulation model, network of 100 stationary sensors and one sink is used. The nodes are supposed to be randomly arranged within the field which is a square area of (a*a).
A comparison of projected work performance to that of LEACH and projected work shows that algorithm provides improvements of up to 60% in lifetime. LEACH has the worst performance. It is due to node that behave as CHs in LEACH send data to base station directly which consumes large amount of energy as random selection of node as CH and thus the energy consumption is not consistent. The performance of our projected algorithm is more resourceful. It splits the network into k clusters, which guarantees the uniform distribution of CH in the whole network. CHs conduct data aggregation in cluster and relay cluster heads are responsible for forwarding data between clusters through a routing tree.
V. CONCLUSION
In this paper we proposed new routing algorithm that organized nodes into clusters by considering different routing parameter. This routing algorithm is asymmetric in nature in which transmission costs of sending data from node 1 to node 2 is different from transmission costs of node 2 to node 1. Proposed algorithm is also a cost effective solution as it not required GPS (Global positioning system) to calculate the distance between nodes which make it suitable for
both indoor and outdoor environment. Proposed algorithm does not require prior global information which makes it suitable for distributed environment.
The result of proposed algorithm evaluated in MATLAB 16(a). Numerical and graphical comparison of proposed algorithm with pre-exits algorithm such as LEACH, HEED, PEGASIS and DHAC shows improvement in network life time as it shows from calculation that time required to die first and last node in network is more as compared to the pre-existing algorithm.
In future scope, research on experimental analysis going too carried out for mobile sink to study’s the network lifetime and energy consumption effects of proposed algorithm with mobile sink.
VI. REFRENCES
1. AkyildizI.F,Wu S.,Sankarasubramaniam Y, CayirciE.,”Wireless Network Survey” ,Computer Networks Journal (Elsevier),vol 40,no. 8,2002, pp 393-422.
2. Gupta C.P., Kumar A.,”Wireless Sensor Networks: Review”, International Journal of Sensors, Wireless Communication and Control, vol., no., 2013, pp 25-36.
3. Takumi S.,&,Miyamoto,S.,”Agglomerative Clustering Using Asymmetric Similarities” in Proc. Of 2006 3rd IEEE international Conference on information Technology New Generation, 2006, pp 34-39.
4. Matthew H, et al. "Optimizing physical-layer parameters for wireless sensor networks." ACM Transactions on Sensor Networks (TOSN) 7.4 (2011): 28.
Parameter Value
Node Number 100
Sensing Field
Range (0,0)-(100,100)
Channel bandwidth 1 Mbps Threshold
distance(d0) 87.7m
Eelec 50 nJ/bit
fs 10 pJ/bit/m2
amp 0.0013 pJ/bit/m4Einitial
0.5 J Data Packet Size 2000 bytes
EDA 5 nJ/bit
5. Heinzelman,W.B., Chandrakasan,A.,Balakrishnan, H,”Energy efficient communication protocol for wireless microsensor networks”, in Proc of 33rdHawaii International Conference on System Sciences (HICSS), Wailea Maui, Hawaii, USA, January 2000.
6. Heinzelman,W.B., Chandrakasan,A.,Balakrishnan,:” An application specific protocol architecture for wireless microsensor networks”, IEEE Transactions on Wireless Communications,vol.1,no.4,2002,pp 660-670.
7. Lindsey, S.; Raghavendra, C.; Krishna Sivalingam,"Data gathering in sensor networks using the energy*delay metric," Parallel and Distributed Processing Symposium.,in Proc of 15th International , vol. 23, no. 27, April 2000,pp.
001-2008,doi: 10.1109/IPDPS.2001.925196.
8. Younis, O.; Fahmy, Sonia,"Distributed clustering in ad-hoc sensor networks: a hybrid, energy-efficient approach," INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies , vol.1, no.7,March 2004 ,pp. ,640,doi: 10.1109/INFCOM.2004.1354534.
9. Bandyopadhyay, S.; Coyle, E.J.,"An energy efficient hierarchical clustering algorithm for wireless sensor networks," INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications.
IEEE Societies, vol.3,no.,2003, pp 1713-1723,doi: 10.1109/INFCOM.2003.1209194.
10. Pradhan, Nirnaya & Sharma, Kalpana & Kumar, Vikash. “ A Survey on Hierarchical Clustering Algorithm for Wireless Sensor Networks”. International Journal of Computer Applications.2016,pp.134. 30-35. 10.5120/ijca2016907896.
11. Young M.B., Al-zou'bi A., Khamayesh Y,,& Mardini W., “Improvement on LEACH Protocol of Wireless Sensor Network (VLEACH),” International Journal of Digital Contents Technology and Its Applications, Vol. 3, No. 2, 2009, pp. 132-136.
12. Lung,C.H., &, Zhou,C.,” Using Hierarchical Agglomerative Clustering In Wireless Sensor Network: An Energy Efficient and Flexible Approach”,Adhoc Networks,vol.8,no.3,2010, pp 328-344, doi: 10.1109/GLOCOM.2008.ECP.55.
13. Lung C.H, Zhu J.,Srivastava V.,”H-DHAC: A Hybrid Clustering Protocol for Wireless Sensor Networks”, in Proc. Of IWCMC,2013,pp.183-188,doi: 10.1109/IWCMC.2013.6583556.
14. Gupta, C P, Kumar A,”Optimal Number of Cluster in Wireless Sensor Network with Mobile Sink ”, International Journal of Scientific and Engineering Research, vol 4,no. 8, 2013,pp 1706-1710.
15. Ramadurai, Vaidyanathan & Sichitiu, Mihail. “Localization in Wireless Sensor Networks: A Probabilistic Approach”.In:
Proceedings of the international conference on wireless network.2003, 275-281.
16. Kim, YoungJoon & Lee, Byeongho & So, Hyoungmin & Hwang, Dong-Hwan & Kim, Seong-Cheol.“Cooperative localization considering estimated location uncertainty in distributed ad hoc networks”. International Journal of Distributed Sensor Networks. 2018,14.
17. Frank M.P., et al., "Design of a wireless sensor network with nanosecond time resolution for mapping of high-energy cosmicray shower events," in Proc. of SPIE Defense, Security, andSensing Symposium, 2010,pp. 2-10.
18. Zhou, Bingpeng & Chen, Q. & Wymeersch, Henk & Xiao, Pei & Zhao, Lian. “Variational Inference-Based Positioning with Nondeterministic Measurement Accuracies and Reference Location Errors”. IEEE Transactions on Mobile Computing. 2016, pp 1-1. 10.1109.
19. Wang, Jing & Ghosh, Ratan & Das, Sajal.” A survey on sensor localization”. Journal of Control Theory and Applications. 2010,pp 2-11.