Energy Efficient Cluster Based Routing Algorithms with MMS in Wireless Sensor Networks

Energy Efficient Cluster Based Routing Algorithms with MMS in Wireless Sensor Networks

Ajay Kumar Singh

Department of Electronics and Communication Engineering, National Institute of Technical Teachers Training and Research (NITTTR), Chandigarh, India

Kanika Sharma

Department of Electronics and Communication Engineering, National Institute of Technical Teachers Training and Research (NITTTR), Chandigarh, India.

Abstract- In order to improve the energy efficiency of the wireless sensor network, it is necessary to provide an efficient routing algorithm which consumes less power and enhance the lifetime of the network. In this paper we propose a method to reduce the energy consumption and prolong the network lifetime of the wireless sensor networks. In this approach we achieve energy efficiency by using cluster routing with multiple mobile sinks (MMS). Consumption of energy of sensor network is reduced by 23% and network lifetime is increased using this technique. Here we have considered three scenarios, in the first scenario all cluster heads are interested to send data to only one sink. In the second scenario and third scenario all cluster heads are interested to send the data to any other mobile sinks among the selected group of mobile sinks. We have simulated the environment using MATLAB and simulated results show that the update energy cost of the sensor network is reduced by 23%.

Keywords: sensor node, cluster routing, wireless sensor networks, Energy efficiency, multiple mobile sinks.

1. INTRODUCTION

   The deployment of sensor nodes for monitoring or detection of different events in a number of environments in wireless sensor networks, recent development have enabled the development of low power, low cost, multifunctional sensor nodes that are small in size and communicate over the distance. The wireless sensor network has been researched for different areas such as environment, energy, medical monitoring and military surveillance. Data gathering from many sensor nodes by the base station is the goal of the network.

   Recent developments in wireless communication, micro-electrical mechanical system and battery operated technologies have enabled the less energy consumption by multifunctional sensor nodes that are small in size with sensing, processing and communication properties. The flexibility, high sensing, low cost and rapid development characteristics for the sensor networks creates many new and existing applications areas for remote sensing [1], [2]. The sensor nodes have strong limitations on energy, bandwidth and memory; the traditional routing protocols [3], [4] can not be used in wireless sensor networks. At present many routing protocols have been proposed for wireless sensor networks and most of them are designed for static sensor nodes and static sink, i.e. both the sensor nodes and sink are the stationary. To avoid the sensor hole problem in the network the sink node requires mobility in the wireless sensor network. The mobile sink saves the energy for sensor networks and mobility makes the sink keep continuous communications to sensors by confining the destination area into a local area for updating the sinks location information [5], [6]. Generally sensor node does not have sufficient

   power and communication range to directly forward the sensed data to the base station. Hence sensor node sense and sends its own data and also act as router and propagate the data to its neighbours. Gathering of data from sensor nodes to sink is a challenging task in the wireless sensor network applications.

   In recent years mobile sink approach has attracted instead of stationary sink to reduce the sensor hole problem and increase potential for wireless sensor network applications and to improve network performance such as energy efficiency and network lifetime of the wireless sensor networks. Based on the structure of the networks, routing in WSN can be categorized into three types i.e., Flat based routing, hierarchical-based routing and location based routing. Among the existing protocols for data forwarding the cluster based structure is considered to be an effective architecture.

   Cluster base routing (hierarchical routing) is an efficient routing method where area of interest is divided into multiple clusters. Each cluster has one cluster head which is responsible for data aggregation. In this paper we propose a method to reduce the energy consumption and prolong the network lifetime of the wireless sensor networks. The selection of cluster head is based on the residual energy of the sensor node. This approach saves energy of the network and ensures that the lifetime of the network is increased.

2. RELATED WORK

   In the previous Studies related to mobile sink node it generally attempt to prolong the lifetime of the sensor network. In mobile sink approach, mobile sink is a node which collects the data from the source nodes and sends the collected data to the end user through the internet or satellite communication System. Sink mobility has been exploited to reduce and balance energy expenditure among sensors. Sink mobility can effectively improve network lifetime without bringing negative impacts on the network. The reason is evident as sinks move, the role of hot spot (i.e., heavily loaded nodes around sink) rotates among sensors, Sink should move toward data sources so as to shorten path length and thus reduce and balance energy consumption. Due to the sink mobility, the sensor nodes in the network can take turns to become the neighbours of the sink so energy can be consumed evenly among the sensor nodes, and consequently the spent energy of sensor node is reduced and lifetime of the entire network can be prolonged. But during the mobility of sink the network topology changes which gives an impact on routing. Thus reconstruction of routes is the need in this type of applications. The paper [3]-[5] to update the new location of the sink with a single mobile sink, the energy consumption is just compared with the flooding method, and paper [7] shows that to reduce the energy consumption of sensor network by using multiple mobile sinks without clustering approach.

   Data gathering in mobile sink based clustered wireless sensor network can be divided into two main phases i.e. setup phase and steady phase. In the setup phase mobile sink send beacon message to the sensor nodes in its vicinity. The closest cluster head which receives that message and forwarded to other cluster heads. Setup phase is further divided into initialization, mobile sink advertisement and cluster head registration phase. In initialization phase clustering is done and nodes send their data to the cluster head and then wait for mobile sink to come in its vicinity to send sensed data to it. In mobile sink advertisement phase mobile sink when reaches any new destination the highest residual energy cluster head sends the location information of the mobile sink to other cluster heads. In cluster head registration phase, all the CHs which receive the location of mobile sink responds by sending registration message to the mobile sink.

   In the steady phase mobile sink performs actual work for which it is moved in the network, i.e. data gathering steady phase is further divided into TDMA scheduling, forwarding to sink and about the sink movement. In TDMA scheduling mobile sink sends TDMA schedule to the registered CHs. In forwarding to sink phase each CH use single hop or multi-hop communication to forward sensed data to the sink. In sink movement phase mobile sink takes the decision to move to the next place. Movement of mobile sink is first movemnt cycle is according to predefined position, to ensure balance use of energy movement of mobile sink. In second and subsequent cycles are dictated by the residual energy of the CHs in the network and mobile sink will move to higher CHs [7].

3. PROPOSED WORK

   The rectangular or square shape of the sensor field is considered, the chosen sensor field is divided into different regions. The numbers of sensor nodes are deployed in each region of the sensor field, clusters are created in each region of the field and for data collection on mobile sink is placed in each region.

   The sensor field allocation for each sink is shown in fig.1. Sensors are marked with small circles and sinks are marked with small triangles. Some assumptions are taken i.e. division of area of interest into equal size of region of interests and equal size of clusters is formed in region of interests. Initially the mobile sink sends its present position to its neighbour nodes. The neighbour nodes sends message of the sink to its cluster head, this cluster head forwarded the message to other cluster heads. After receiving the location message of the sink, the all CHs of the particular region sends information about its energy to the mobile sink. Among the energies of the CHs, which has highest energy the sink will move close to that cluster head, the data collection is by CHs to sink and CHs to CHs forwarding basis. The CH which has highest energy that inform to the other CHs to update the new location of the sink. When the data collected by the mobile sink, the mobile sink also knows about the next higher residual energy of the CH in the region of interest. In the next round another CH is selected to send the data to the mobile sink and sink will move close to that CH which has next higher residual energy in the region of interest. In the first scenario, it is considered that only one mobile sink is present in the network. If the sink moves from one position to another then the new position of the sink is depends on the residual energy of the cluster head. This cluster head will send the information about the new location of the sink to all the cluster heads in the network. Then the data is transmitted to the sink which is present at the new position. In the second scenario, it is considered that two sinks are present. The sensor field for each sink is fixed, i.e. one sink is used to cover one half of the sensor field. If any one of the sink moves initially from one position to another then the new position of that particular sink is depends on the residual energy of the CH. These nodes will flood the information about the

   new location of the sink to only one half of the network. The same rule is applied for other sink also. Then using this routing algorithm the data is transmitted to the sink at the new location. Now both the sinks collect the data from the sensor field. The sensor field with two sinks of two different positions is shown in fig.1.

   Region of interest Area of interest

   Sink node Sensor node Cluster head Cluster

   Fig.1. Sensor field with two sinks.

   In the third scenario, now the number of sinks is increased from two to three for the same sensor field. Like the second scenario, the sensor field for each sink is fixed, i.e., one sink is used to cover the one third of the sensor field. Initially the position of particular sink is first informed to its one hop neighbour sensor nodes.

   If any one of the sink initially moves from one location to another then the new location of that particular sink is first informed to its one hop sensor node. These nodes will send the information about the location of the sink to only its cluster head and that cluster head forward the information of location of sink to other cluster heads of that particular one third of the network. When sink again moves to new location it depends on the residual energy of the cluster heads. The same rule is applied for other sinks also. The collection of data is being done by sensor nodes to its cluster head, cluster head to cluster head and cluster head to sink. Here all the three sinks collect the data from the sensor field. The sensor field split up for three sinks is shown in fig.2.

   Region of interest Area of interest

   Sensor node Sink node Cluster head Cluster

   Fig.2. Sensor field with three sinks.

   Just like the three scenarios more scenarios can be developed with multiple-sinks where the selection of scenario depends on the requirement of data in short time. The destination area of a sink which is indicated by dotted circles. The present location of the sink is forwarded by cluster head to cluster head is shown in fig.3.

   Destination area

   Region of interest

   Start

   of the sink Cluster head Cluster

   Create a WSN of area of interest and place the number of sensor nodes and mobile sinks in the network.

   Divide the area of interest into region of interests and one mobile sink in each region.

   Round (S) = 5000

   Fig.3. Sink gives its initial position information to all Cluster heads.

   Data collection from sensor nodes to Cluster Head, Cluster Head to Cluster Head and Cluster Head to sink is shown in fig.4.

   Region of interest

   Destination area Cluster head Cluster of the sink

   No

   If

   r T(n)

   Yes

   Selection of Cluster heads (CHs)

   End

   Sensor nodes send sensed data to their respective CHs.

   CHs aggregate data.

   Each CH sends aggregated data to the Mobile sink of that region.

   Fig.4. Data collection from sensor nodes to Cluster Head,

   Cluster Head to Cluster Head and Cluster Head to mobile Sink.

   Data collection from sensor nodes to Cluster Head, Cluster Head to Cluster Head and Cluster Head to Sink is shown in fig.4.The system is designed in such a way to collect more data within a short period with the help of multiple mobile sinks. This proposal makes the system energy efficient and prolongs the lifetime of the sensor networks.

   Fig.5. shows flow diagram for the proposed algorithm. Initially the network has formed and area of interest is created. Area of interest is divided into number of region of interest. Each region of interest consists of number of sensor nodes and one mobile sink. Clustering is used to group the sensor nodes to form a number of non- overlapping clusters. In the cluster head selection process maximum energy level of node acts as a cluster head. Movement of sink depends on the higher residual energy of cluster head of particular region of interest.

   In the next round, sink moves to the close of higher residual energy of CH of that region.

   CHs send data to the Mobile sink and protocol goes in next round.

   Fig.5. Flow chart of proposed algorithm.

4. PROBLEM FORMULATION

   In wireless sensor networks energy is the major constraint to improve the lifetime of the network. To overcome the limitations the overall energy required for data gathering can be minimized in the sensor networks. One of the ways for energy minimization is to reduce the routing cost; maximum possible data should be gathered before the sensor nodes die. In a very short period maximum data can be collected if a mobile sink is used. Moreover if multiple mobile sinks are used with cluster routing the conservation of energy and lifetime of the sensor nodes are increased and maximum data can be collected within a short span. This is the concept of our proposed system.

   The wireless sensor network is considered as homogenous static sensor nodes. During the movement of mobile sinks in the network

   Thus the common equation for the update cost is given as-

   there is no collision between sensor nodes and mobile sinks. Data

   =

   [ 2 + 1 ] (10)

   packets are generated by all the sensor nodes in regular intervals. The

   =1

   nmber of mobile sinks are varied in the different scenarios which is explained earlier. So it is considered that the entire sensor nodes of the region should be connected to only one sink which is assigned for that region, each sink is moved within a restricted region of the network.

5. EVALUATION METRICS

   The numbers of sensor nodes are distributed randomly in the network with side length L. It is an assumption that the mobile sink changes its position number of times within a time period T. The destination area or the radius of the coverage is given by in the case of single mobile sink and 1 & r2 in the two mobile sinks. The velocity of the mobile sink is represented by . The energy spent to update the new location of the mobile sink for each cluster head is considered as jouls. The total energy cost to update the new location of the mobile sink for each node is given by [8].

   = + (/) (1)

   Where n is the number of nodes in the destination area, it may be increases if density of sensor nodes increases or destination area of the sink increases. It can be calculated by [5]:

   = 2 × /2 (2)

   Period of time consumed by the mobile sink to move out of the destination area is represented by t. m is the number of times the mobile sink changes its position. The value t increases with increase in destination area and decreases with the velocity v [8].

   / ; = / (3) Where is the proportionality constant, in the same way m depends on T & . The relation is given as –

   ; = (4) Where is the proportionality constant. The energy consumption for update can be rewritten as [8].

   We use the same radio model as stated in [9] with = 50nJ/bit energy dissipated to operate the transmitter or receiver circuit and

   =100pJ bit/2 as the energy dissipation of the transmitter amplifier. The energy cost of transmitter and receiver for common sensor nodes is calculated as [8].

   , = +

   =

   Where k is the length of the message in bits, d is the distance between transmitter and receiver node and is the path loss exponent.

6. SIMULATION RESULT

   In this paper, simulation is run on MATLAB platform. Parameters for setting up the simulation environment are listed in Table.1.

   Table.1. Network Parameters

   Parameter name	Value
   Number of sensor nodes ( N )	10000
   Length of the packet ( l )	6 bit
   Initial energy of the sensor nodes ( )	0 2 J
   Energy consumption on circuit ( )	50 nJ/bit
   Channel parameter in free-space model ( )	10 pJ/bit/2
   Channel parameter in multi-path model ( )	0.0013 pJ/bit/4

   The other parameters are set as for the three scenarios are carried out with m=30, = 10 /, L=50000 m and = 10 . To update the location of sink over number of nodes with the fixed area of sensing field, the energy spent for single sink, two sinks or three sinks are shown in fig.6 (a), 6(b) and 6(c).

   2

   2

   2 1

   -3

   x 10

   3.5

   Energy consumed to update the new location of sink

   E= [

   2 + ] = (

   +

   ) (5)

   Existing with single sink

   Existing with two sinks

   As , are all constants. For minimum energy consumption

   3 Existing with three sinks

   Energy Spent for update(J)

   Proposed with single sink

   1=0 which gives 3 = 2 ,

   R= [ 3 2

   ] (6)

   2.5

   Proposed with two sinks

   3

   2

   1

   thus

   1

   2

   Proposed with three sinks

   2

   E= [ 4 2 22m + ]= [4 3 ( 22) 3 + ] (7)

   Thus for large scale network, consumption of energy decreases with increase in the length of the network. When single mobile sink is used, the energy spent for updating the new location of the mobile sink in each cluster head in the network is given by

   2

   1.5

   1

   0.5

   0

   1

   = (

   2

   + 1 ) (8)

   2000 3000 4000 5000 6000 7000 8000 9000 10000

   Number of Nodes

   The energy spent for two mobile sinks are given as [8]- Fig.6 (a). Energy consumed to update the new location of sink with =1

   2=

   [ 1 +

   2

   2 1

   1 ] +

   1

   [ 2 +

   2

   2 2

   1

   2

   ] (9)

   3.5

   -3

   x 10

   Energy consumed to update the new location of sink Existing with single sink

   Existing with two sinks

   1.4

   -3

   x 10

   Energy consumed to update the new location of sink Existing with single sink

   Existing with two sinks

   3 Existing with three sinks

   Energy Spent for update(J)

   Proposed with single sink

   1.2

   Existing with three sinks Proposed with single sink

   Energy Spent for update(J)

   2.5

   Proposed with two sinks

   Proposed with three sinks

   1 Proposed with two sinks Proposed with three sinks

   2 0.8

   1.5 0.6

   1 0.4

   0.5 0.2

   0

   2000 3000 4000 5000 6000 7000 8000 9000 10000

   Number of Nodes

   0

   0 5 10 15 20 25

   Velocity(m/s)

   Fig.6 (b). Energy consumed to update the new location of sink with =2

   Fig.6 (d). Energy spent to update the new location of sink over velocity with

   =1

   3.5

   -3

   x 10

   Energy consumed to update the new location of sink Existing with single sink

   Existing with two sinks

   1.4

   1.2

   -3

   x 10

   Energy consumed to update the new location of sink

   Existing with single sink Existing with two sinks

   Existing with three sinks

   3 Existing with three sinks

   Proposed with single sink

   Proposed with single sink

   Energy Spent for update(J)

   1 Proposed with two sinks

   Energy Spent for update(J)

   2.5

   2

   Proposed with two sinks

   Proposed with three sinks

   0.8

   Proposed with three sinks

   1.5

   0.6

   1 0.4

   0.5

   0.2

   2000	3000	4000	5000 6000 7000	8000	9000	10000	0 0	5	10	15	20	25
   			Number of Nodes						Velocity(m/s)

   0

   Fig.6 (c). Energy consumed to update the new location of sink with =3

   Fig.6 (e). Energy spent to update the new location of sink over velocity with

   =2

   From the fig.6 (a), 6(b) and 6(c) it is clear that energy spent for update is reduced from one mobile sink scenario to two mobile sinks scenario and it is further reduced in three mobile sinks scenario. We can say that the energy spent to update the location of the mobile sink is reduced by increasing the time taken to move out of the destination area which reflects the increase in radius of the destination area.

   In the same manner the energy spent to update the location of the mobile sink over velocity of one mobile sink, two mobile sinks and three mobile sinks as shown in fig.6 (d), 6(e) and 6(f).

   1.4

   1.2

   Energy Spent for update(J)

   1

   0.8

   0.6

   0.4

   0.2

   -3

   x 10

   Energy consumed to update the new location of sink

   Existing with single sink Existing with two sinks Existing with three sinks Proposed with single sink Proposed with two sinks Proposed with three sinks

   0

   0 5 10 1520 25

   Velocity(m/s)

   Fig.6 (f). Energy spent to update the new location of sink over velocity with

   =3

   It is clear that energy spent for updating is reduced when mobile sinks are increases in the sensing field. It shows that as velocity increases m increases in tern increases the energy spent. Comparison table for improved efficiency of the sensor network between existing and proposed algorithms are given in table.2. and table.3.

   Table.2. Comparison table for energy spent to update (J) Vs.

   Number of sensor nodes.

   Number of Mobile Sinks	Value of	Energy spent to update (J) for Existing Algorithms	Energy spent to update (J) for Proposed Algorithms	Improved Efficiency (%)
   1	1	3.2*103	2.7*103	15.62 %
   2	1	2.6*103	2.15*103	17.30 %
   3	1	2.4*103	1.95*103	18.75 %
   1	2	1.6*103	1.35*103	15.62 %
   2	2	1.3*103	1.075*103	17.30 %
   3	2	1.2*103	0.975*103	18.75 %
   1	3	1.067*103	0.9*103	15.65 %
   2	3	0.87*103	0.72*103	17.24 %
   3	3	0.8*103	0.65*103	18.75 %

   Table.3. Comparison table for energy spent to update (J) Vs.

   Velocity of Mobile Sinks.

   Number of Mobile Sinks	Value of	Energy spent to update (J) for Existing Algorithms	Energy spent to update (J) for Proposed Algorithms	Improved Efficiency (%)
   1	1	1.37*103	1.1*103	19.70 %
   2	1	0.7*103	0.55*103	21.42 %
   3	1	0.6*103	0.464*103	22.66 %
   1	2	0.685*103	0.55*103	19.70 %
   2	2	0.35*103	0.275*103	21.42 %
   3	2	0.3*103	0.232*103	22.66%
   1	3	0.456*103	0.366*103	19.73 %
   2	3	0.233*103	0.183*103	21.45 %
   3	3	0.2*103	0.154*103	23 %

7. CONCLUSION

   In this paper we developed an energy efficient cluster based routing algorithm with multiple mobile sinks in WSNs. The result shows that it reduces the energy spent of sensor network during update process of sensor nodes by 23% with respect to existing algorithm to update the new location of the mobile sink in wireless sensor networks. The obtained results increase the energy efficiency and also enhance the lifetime of the wireless sensor networks.

8. FUTURE WORK

Our future work is to consider congestion control mechanism and reliability in data transfer so that lifetime of the network can further be enhanced.

REFERENCES

1. Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci, "A Survey on Sensor Networks", IEEE Communications Magazine, Vol. 40, No. 8, pp. 102-114, August 2002.

2. Kazem Sohraby, Daniel Minoli, Taieb, Znati Wireless Sensor Networks, John Wiley & Sons Inc. publication, Canada, ISBN No.- 978- 0-471-74300-2, 2007.

3. Jamal N.Al-Karaki, Ahmad E.Kamal, Routing techniques in wireless sensor networks: a survey, IEEE International Conference on wireless communications, Vol.11, Issue.6, pp.6-28,

   Dec. 2004

4. N.Narasimha Datta, K.Gopinath, A Survey of Routing Algorithms for Wireless Sensor Networks

5. Guojan Wang, Tian Wang, et.al., Local Update Routing Protocol in Wireless Sensor Networks with Mobile Sinks, IEEE Communications Society, 2007

6. Guojun Wang, Tian Wang, Weijia Jia, Minyi Guo, Jie Li, Adaptive location updates for mobile sinks in wireless sensor networks, Journal of Supercomputing Volume 47, Issue 2, pp.127-145, February 2009,

7. B.Nazir, H. Hasbullah, Mobile Sink based Routing Protocol (MSRP) for Prolonging Network Lifetime in Clustered Wireless Sensor Network, IEEE International conference on Computer Applications and Industrial Electronics (ICCAIE), pp.624-629, 2010.

8. M.S.Godwin Premi, K.S.Shaji, MMS Routing for Wireless Sensor Networks, IEEE International Conference on Communication Software and Networks, pp.482-468, 26-28 Feb.2010

9. O. Younis and S. Fahmy, HEED: A Hybrid, Energy-Efficient distributed clustering approach for adhoc sensor networks, Approach, IEEE Transactions in mobile computing, vol. 3, pp. 366-379, Oct. 2004.