Cluster Based Beaconless Voting Algorithm for Wireless Sensor Networks

Cluster Based Beaconless Voting Algorithm for Wireless Sensor Networks

Suganthi.K1 and Gayathri.R2

1Department of Computer Technology, Madras Institute of Technology, India

2Department of Computer Technology, Madras Institute of Technology, India

Abstract

Routing protocols used in sensor networks are unique from the protocols used in other fixed networks. Sensor networks are infrastructure-less. The nodes in the sensor networks are very prone to failure. When the network becomes mobile, routing becomes a challenging issue in the network. In this paper, we focus on the novel algorithm of beaconless voting, that rotates the role of the cluster head periodically by a voting mechanism. The new cluster head is elected based on the vote which includes factors like node mobility, residual energy. Further to reduce message overhead, we concentrate on the beaconless messages to transfer votes. Also to utilize energy efficiently, the operational states of the nodes are changed during transfer of data.

Keywords:

Cluster head, Node mobility, and Residual energy.

1. INTRODUCTION

   Wireless Sensor Networks (WSNs) consists of nodes which performs sensing in the deployed area. Sensor nodes have additional capabilities of sensing, processing and transmitting the gathered information to the sink or the base-station (BS [1]. This communication maybe of direct link or indirect (multi-hop) links. Sensor nodes are constrained in energy supply and bandwidth. Thus, a technique that extends the network lifetime with limited energy is highly required. Nodes in the wireless networks are free to move, hence causes changes in the network topology which are more frequent. Various techniques have been proposed for routing, one of which is the clustering technique. Nodes are grouped as cluster and among them, one node is chosen as a cluster head which coordinates the cluster. In flat networks, nodes play the similar role. These nodes works together, performs the sensing task and transfer the data sensed to the respective nodes.

   LEACH [2] is the first protocol proposed for energy efficient cluster based routing. LEACH uses a distributed clustering algorithm. Among the sensor nodes, a few are randomly selected as cluster heads (CHs). To maintain lifetime of the CH, the role of CH is rotated after a certain time. Also the energy load of the nodes is evenly distributed by rotating the role of CHs. The works of CH nodes is to aggregate data collected from nodes and send it to the base-station. LEACH uses a TDMA/CDMA MAC technique which reduces collisions in the inter-cluster and intra- cluster. Although LEACH is able to increase the network lifetime, there are still a number of issues about the assumptions

   used in this protocol. It is not applicable to networks deployed in large regions. The basis of PEGASIS [3] protocol is to extend network lifetime. Based on this, nodes need only communicate with their closest neighbors. These nodes then communicate with the base-station. When the first round of communication ends, next round will start and so on. Hence power required to transmit data per round is reduced as the power draining is spread uniformly over all nodes. The chain of nodes is those that are closest to each other and form a path to the base-station. TEEN and APTEEN [3] are the hierarchical routing protocol proposed for time-critical applications. In TEEN, nodes sense the medium continuously, but the data transmission is done rarely. Two threshold values are sent by the cluster head to its member nodes. Hard threshold is the value of the sensed attribute while soft threshold gives a small change in the value of attribute sensed. This value triggers the node to switch on the transmitter for transmission. The MECN protocol [4] defines a sub-network of nodes. This network contains less number of nodes and hence requires lesser power for transmission between nodes. By this minimum power path is found which has only selected nodes of the network. This is performed by using a localized search for nodes and also considering its relay region in the network. The protocol, called Geographic and Energy Aware Routing (GEAR), uses energy aware and geographically-informed neighbor selection heuristics to route a packet towards the destination region. The basic idea is to reduce the number of interests in directed diffusion by only considering a certain region rather than sending the interests to the whole network. By doing this, GEAR [4] can conserve more energy than directed diffusion.

   The paper is structured as follows. Section 2 introduces the existing works on clustering in sensor networks. The system model of the proposed algorithm and its features are dealt in Section 3. Section 4 provides the simulation and experimental results and the paper is concluded in Section 5.

2. EXISTING WORKS

   A variety of clustering protocols [5], [15] have been proposed to address the energy efficiency problem in different network scenarios. In MBC [6], sensor node elects itself as head based on its residual energy and mobility. TDMA schedule is allotted for the node in the cluster and based on estimated connection time link stability is maintained between cluster head and other nodes. This protocol supports mobile environment.

   In [7], vote based clustering algorithm has been discussed. The cluster head role is rotated when the residual energy falls below threshold. Node receiving maximum ballot is elected as new head and the information is passed to all other nodes of cluster. EE-DVC achieves energy utility. According to the partition based scheduling algorithm, defined in [8], a mobile element (ME) is used to avoid sensor data loss at low ME speeds. Also a multihop route to Mobile Element is proposed that extends PBS to deliver urgent messages within specific bounds. No buffer overflow occurs if ME traverses path at computed minimum speed. Unequal clustering concept has been discussed in [10]. It considers distance and residual energy factors while electing the cluster head node. Common nodes of cluster will transmit data to closest CH, which collects and fusion those data to base-station CH. The data transmission here is based on the TDMA schedule. A geographic routing based protocol proposed in [9], [17]. The protocol uses the greedy forwarding and recovery modes of transmission. According to this protocol, nodes in the relay search region are forwarders of the data packet. Nodes use RTS/CTS handshaking mechanism to find its next relay hop. Base station controlled dynamic protocol have been proposed in [11]. Here the base station decides the cluster head based on the energy levels received from all the nodes. The cluster splitting algorithm works iteratively by first dividing the network into two sets and further sub-dividing into smaller sub-clusters. A rendezvous design approach has been discussed in [13]. According to the author, approximation algorithms are used to track location of rendezvous points from BS. A minimum Steiner tree is constructed which connects all nodes through a point, with a source node as root. The tree is traversed to find RPs [13], which serves as transmission link to the BS. Duty-cycled protocols have been proposed in [12] which uses the idea of sleep scheduling for extending the lifetime of the network and also saves energy of the sensor nodes. Two states are defined for each node, sleep and active where the nodes wake up to send a packet. Further rendezvous scheduling and asynchronous scheduling are discussed in [12].

   Network dynamics have been used to manage the mobility of the sensor network in [16]. In PDND [16, a node which intends to move can start immediately and hence all other nodes follow. Force is calculated for each node based on which the direction of movement is desired. If the potential energy falls below minimum, the node stops movement.

   To overcome these issues, we propose a beaconless voting algorithm which is used in electing suitable cluster head for next round of data transmission. The network is divided into sectors, which in turn is divided tracks on which clusters are formed. TDMA schedule is used for data transmission from nodes to respective cluster heads.

3. SYSTEM MODEL

   1. NETWORK MODEL

      The network is divided into sectors. The base station has a fixed location. The function which uses base stations position, desired number of sectors is formulated to divide the network area. Applying De-Morgans law on complex numbers we arrive at,

      where k represents the number of sectors and a represents the (x,

      1. co-ordinates of the base station.

         Each sector consists of circular tracks with each assigned a level. This kind of arrangement of nodes improves the performance and lifetime of the network. The track closest to the base station is assigned as level 1 and next as level 2 and so on. Each level is considered as a cluster. The nodes in each level generate a random number based on which the initial cluster head is chosen.

         BS

         CH MN

         Fig.1. Network diagram

         For the proposed network, the following assumptions are made:

         1. All the sensor nodes are homogeneous.

         2. All the sensor nodes in the network are considered as mobile nodes.

         3. The base station is stationary.

   2. SET UP PHASE

      In this phase, a sensor node is elected as cluster head if its random value is greater than a threshold value. This threshold value is set based on the probability that a node can be a cluster head or not. Once cluster head is chosen, sensor nodes sends hello messages to suitable cluster head and joins in the cluster. TDMA schedule is created for the nodes for transmission by the cluster head.

      Z= a + r ei (+2(k-1) /n), k= 1…n (1)

   3. CLUSTER HEAD ELECTION

      In LEACH protocol [2], threshold is formulated and based on it, cluster head is elected. Using this threshold a node can be a cluster head at a point within 1/p rounds. In MBC protocol [6], cluster head is elected based on the threshold which includes both residual energy and speed of the sensor nodes as factors. With this, the node with higher residual energy and lower speed has higher probability to be elected as cluster head. This results in a situation of suitable node not being elected as cluster head for a prolonged time. To overcome these issues, we propose a voting algorithm for electing the suitable cluster head. Votes are collected from the nodes of the cluster and the one with higher number of votes is elected as cluster head. Here vote is calculated based on the residual energy and mobility of the node. Mobility of the node is taken as the ratio of movement of the node in and out of the cluster. A similar vote based approach is proposed in [7]. It involves additional messages which results in overhead of packets in the cluster. Addressing this problem, we use two way handshake mechanisms for voting.

      VOTE message

      Sender ID

      Time T

      CH ID

      CH Location

      Vote

      ACK message

      CH ID

      Receiver Node Location

      Receiver node ID

      Time T time at which packet is being generated Vote contains the Node ID

      Fig.2. Vote message formats

      The base station initiates the cluster head re-election process. Nodes within the cluster transfer their residual energy among them. Each node after receiving the neighbors energy value, computes mobility factor of the node and decides the next cluster head. Each node sends a VOTE message containing the new cluster head information. The current cluster head acknowledges this message. After receiving votes from all nodes, next Cluster Head (CH) node is chosen. After cluster head is elected, the information is updated in the cluster table.

      3.3.1 Schedule creation:

      The cluster head creates a TDMA schedule for the nodes of its cluster. Each node is assigned a timeslot for data transmission as in [14]. According to this schedule nodes transfer data to its Cluster-head. If the cluster head node does not receive messages from its node, it assumes that the node has moved out of its cluster and removes it from the schedule. New schedule is created and assigned to each of the nods in the cluster.

      3.4 STEADY-STATE PHASE

      Each track is considered as a cluster.

      Each track is considered as a cluster.

      CH in each cluster is selected based on the probability factor.

      CH in each cluster is selected based on the probability factor.

      Sensor nodes dissipate more energy during transmission/ communication than sensing [1]. Hence scheduling is used in WSN and many algorithms have been proposed based on sleep/wakeup scheduling [18]. In this paper, we schedule the nodes to switch between active and sleep states during data transmission. Nodes will be in active state during its timeslot and goes to sleep state after transmission. Nodes wake up one slot before its time schedule and transfer data. After its schedule it goes to sleep data. In active state, nodes can sense and transfer data while in sleep state it is in idle mode.

      (i) Initialization

      (i) Initialization

      Divide the area into sectors.

      Divide the area into sectors.

      Each sector is in turn divided into circular tracks.

      Each sector is in turn divided into circular tracks.

      1. Voting new cluster head

         • After a periodic time BS initiates cluster re- election.

         • Each node receives residual energy of all other nodes.

         • Based on this energy & mobility factor, each node nominates vote.

      2. Clustering

         • Current CH receives votes, counts the received packets.

         • Selects the node with maximum votes as new CH.

      1. Voting new cluster head

         • After a periodic time BS initiates cluster re- election.

         • Each node receives residual energy of all other nodes.

         • Based on this energy & mobility factor, each node nominates vote.

      2. Clustering

         • Current CH receives votes, counts the received packets.

         • Selects the node with maximum votes as new CH.

      Fig.3. Beaconless voting algorithm

4. SIMULATION

   In this section, we describe about the set up of simulation and results obtained. The beaconless voting algorithm was simulated using Network Simulator tool on a network of 100 nodes distributed in a. All the nodes are set with equal energy. Based on the angle function, the area is divided into 4 sectors each with three tracks or levels. Each level is defined as a cluster.

   To compute the transmitting and receiving energy, we use the Radio Model as in [2]. In this model, the transmitter and receiver

   dissipate Eelec = 50 nJ/bit. Energy dissipated in transmitting and receiving k bits of message between transmitter and receiver through a distance d is;

   ETx (k,d) = Eelec × k + amp × k × d2 (2) ERx (k) = Eelec × k (3)

   Table.1. Parameters and values for simulation

   Parameters	Value
   Network Area	3000 m, 3000 m
   Number of sensor nodes	100
   Node Deployment	Random, Uniform
   Initial energy of ndes	100mJ
   Eelec	50 nJ/bit
   Data Size	250 bytes

   1. PERFORMANCE ANALYSIS

      We analyze our proposed algorithm with simulation results. For evaluation of our algorithm we use MBC protocol and compare in terms of percentage of successfully received data packets and energy consumption of successfully received data packets.

      Fig.5 shows the percentage of successfully received packets of our proposed algorithm with the MBC protocol. Our algorithm achieves better successful packet rate when compared with the MBC protocol. It is seen that the successful delivery rate of packet decreases with increase in number of mobile nodes because of the broken links.

      The average energy consumption is shown in the Fig. 4 which results from the transmission between member nodes and the cluster head. In our algorithm, the cluster head is chosen based on the residual energy and mobility factor, hence a stable link is achieved. Therefore our protocol consumes less power in comparison with the MBC protocol.

      We vary the speed of the mobile nodes and analyze the performance in terms of successful packet delivery rate, average energy consumption. It shows that our protocol can adapt to a mobile environment as to that of MBC protocol. Fig. 6-7 shows the performance against speed.

      Fig.4. Average energy consumption against number of mobile nodes

      Fig.5. Percentage of received packets against number of mobile nodes

      Fig.6. Average energy consumption against speed

      Fig.7. Percentage of received packets against speed

5. CONCLUSION

In this paper, based on mobility of the nodes, we present a beaconless voting algorithm for wireless sensor network. This algorithm has three features: It divides the network into sectors. The cluster head is selected based on the mobility and residual energy. Beaconless voting is introduced in this paper which reduces the message overhead in the clusters.

Vote based clustering allows a suitable node to be cluster head. Further efficiency can be achieved by considering additional factors while electing cluster heads. These factors may include nodes sensing capability, performance of the node.

REFERENCES

1. Chiara Buratti, Andrea Conti, Davide Dardari and Roberto Verdone, An Overview on Wireless Sensor Networks Technology and Evolution, MDPI, Journals, Sensors, pp. 6869- 6896, August 2009

2. W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, An Application-specific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Communications, vol. 1, pp. 660-669, October 2002

3. Xuxun Liu, A Survey on Clustering Routing Protocols in Wireless Sensor Networks MDPI Journals, Sensors, pp. 11113- 11153,August 2012

4. K. Padmanabhan, A Study on Energy Efficient Routing Protocols in Wireless Sensor Networks, European Journal of Scientific Research, Vol.60 No.4, pp. 499-511, 2011

5. Ameer Ahmed Abbasi, Mohamed Younis, A survey on clustering algorithms for wireless sensor networks, Elsevier Computer Communications, pp. 2826-2841, June 2007

6. Deng.S, J.Li L.Shen, Mobility-based clustering protocol for wireless sensor networks with mobile nodes, IET Wireless Sensor Systems., Vol.1, Iss. 1, pp. 39-47, Jan 2011

7. Ming Zhang, Chenglong Gong, Yuan Feng, Chao Liu, Huibin Feng, A Novel Energy-Efficient Dynamic Voting Cluster Algorithm for Wireless Sensor Networks, IEEE International Conference on Networks Security, Wireless communications and Trusted Computing, 2009

8. Ekici, E., Yaoyao, G., Bozdag, D.: Mobility-based communication in wireless sensor networks, IEEE Commun.Mag.,44,(7),pp.56-62, 2006

9. Haibo Zhang and Hong Shen, Energy Efficient Beaconless Geographic Routing in Wireless Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, pp.881-896,

   June 2010

10. Zhe JI, Liping Cai, Li Hong, Load-balanced Unequal Clustering Algorithm in UWB-based Wireless Sensor Network, IEEE International Conference on Information Technology & Computer Science, 2009

11. Siva D. Muruganathan, Daniel C. F.MA, Rolly I.Bhasin, and Abraham O.Fapojuwo, A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks, IEEE Radio Communications, pp. S8-S13, March 2005

12. Jie Hao and Baoxian Zhang, Routing Protocols for Duty Cycled Wireless Sensor Networks: A Survey, IEEE Communications Magazine, pp. 116-123, 2012

13. Guoliang Xing, Tian Wang, Weijia Jia and Jun Huang,

    Efficient Rendezvous Algorithms for MobilityEnabled Wireless Sensor Networks, IEEE Transactions on Mobile Computing, Vol 11, No.1, pp. 47-60, January 2012

14. Chunjuan Wei, Junjie Yang, Yanjie Gao, Zhimei Zhang,

    Cluster-based Routing Protocols in Wireless Sensor Networks: A Survey, pp. 1659-1663, International Conference on Computer Science and Network Technology, 2011

15. Samer A. B. Awwad, Chee K. Ng, Nor K. Noordin, and Mohd. Fadlee A. Rasid, Cluster Based Routing Protocol for Mobile Nodes in Wireless Sensor Network, IEEE International Conference, pp. 233-241, 2009

16. Ke Ma, Yanyong Zhang and Wade Trappe, Managing the Mobility of a Mobile Sensor Network Using Network Dynamics, IEEE Trans. on Parallel And Distributed Systems,

    Vol. 19, Jan 2008

17. Juan A. Sanchez, Rafael Marin-Perez and Pedro M.Ruiz

    BOSS: Beacon-less On Demand Strategy for Geographic Routing in Wireless Sensor Networks, Mobile Adhoc and Sensor Systems, IEEE International Conference, 2007

18. Y. Gu and T. He, Data Forwarding in Extremely Low Duty-Cycle Sensor Networks with Unreliable Communication Links, Proc. ACM SenSys 07, Nov. 2007, pp. 321-34.