International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 328

ISSN 2229-5518

Energy Efficient Routing Using Random Walk and Best Route Selection for

Sensor Networks

Bhanu Prakash Lohani#1, Monika Jena*2, Sanjay Kumar Dubey@3

#1 M.Tech (CSE), Amity University, Sec-125, Noida, India

1 bhanuplohani@gmail.com

*2 Assistant Professor, Amity School of Computer Science, Sec-44, Noida, India

2mjena@amity.edu

@3Assistant Professor, Amity University, Sec-125, Noida, India

3skdubey1@amity.edu

Abstract— this paper discusses about a new routing technique based on the idea of random walk with the objective of saving energy. Energy consumption is a vital factor in the successful deployment of wireless sensor networks because sensor nodes are powered by on board battery which are extremely difficult to be recharged. Our approach is inspired by an existing TDMA like routing protocol. In this paper we have given a description of our algorithm by taking help of a small size network and performed simulations on large network to draw a comparative analysis with the existing algorithm.

Keywords— Sensor, Wireless, Network, TDMA, Routing, Battery, Energy.

I. INTRODUCTION
Among several challenges in wireless sensor network, efficient energy management is of particular importance, since sensor nodes are constrained by battery power which have limited amount of energy. This energy used in sensor networks is be very expensive and it is very difficult or even impossible to renew. Thus energy efficient techniques are critical to maximize network lifetime [1],[2].
Efficient energy management in ad hoc networks can be done in different ways considering energy consumption at multiple layers in the network protocol stack. Starting with the Application layer, methods can be developed to reduce the amount of data to send to consume energy. However, once the data is send by the application layer, it is up to the network to try to deliver it in an energy-efficient manner. At the network layer, intelligent routing protocols can reduce overhead and discover routes in energy efficient manner. At the medium access control (MAC) layer, methods can be used to minimize the energy consumed during transmitting and receiving data. Additionally, an intelligent MAC protocol can turn off the wireless communication device when the node is idle[3]. In a device network most of the ability is consumed for act between nodes, i.e. for transmission and receiving. so energy saving is directly proportional to the time a node stay in idle state (Neither transmission nor receiving) or reciprocally proportional to range of transmissions [4]. Therefore it's necessary to style a routing formula that should avoid or scale back redundant causation of messages. This can minimize power consumption by reducing the time that a node is transmission or receiving (duty cycle)[5],[6]. In impromptu state of affairs it's terribly troublesome if not
not possible to route the message within the best path (in terms of hop count and time) in the main attributable to following constraints:
a) Network configuration isn't far-famed before.
b) The network being dynamic and nodes area unit mobile, best route between a combine of nodes might amendment, therefore it's necessary to calculate the recent route before every transmission.
II. PROBLEM STATEMENT
Given a network and a source-destination try, the matter is to route a packet from the supply to the destination node exploitation minimum number of transmissions or hop count. Assumptions- we have a tendency to create the subsequent assumptions:
a) every node is connected to one or a lot of nodes
Within the network (neighbours).
b) A node is also a supply, a destination, or it's going to act as a router for a communication between a distinct try nodes.
c) Neither network configuration nor nearness data is understood beforehand.
d) an equivalent quantity of power is needed for causing a message between any try of adjacent nodes throughout the network.
III. PROPOSED APPROACH
In this approach, every node discovers its neighbours and agrees to speak with each of them solely throughout a little interval randomly(shown in fig 1). Thus every node

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 329

ISSN 2229-5518

remains active throughout a little amount of the network time (T) and remains idle most of the time. Every node maintains a contact list containing the knowledge of its direct neighbours and adjacent nodes of its neighbours, beside the interval during which they convey. Therefore a Two hop node (two hop neighbours area unit referred to as as routers) list is maintained by every and each node. s".A queried node may be a node that has received the request to forward an information packet. Whereas causation multiple copies of same knowledge to completely different nodes (potential routers), the queried node can send a “tentative path list” containing the nodes to that constant knowledge is forwarded beside the time slots[9].
After choosing a router the queried node can generate a random range say x between zero and one. If x is a smaller amount than P, choose that router else discard it. By this we have a tendency to area unit proscribing the amount of transmission of constant knowledge thus saving energy[10].

In device network, since the nodes are also mobile the route between any two nodes could amendment with time. As a result when a node desires to send some knowledge it's to seek out the trail and therefore the knowledge packet is distributed whereas discovering the route and no separate message is employed for route discovery.

Fig 1: Communication time slots of node A Proposed Algorithm:

1. Each node broadcasts its one level contact list; at the end
of the process every node has an updated routing table with nodes reachable in two hops and corresponding time slots.
2. A sender or a queried node will do the following:
a) If it has forwarded the packet then stop.
b) Else if final node in contact list then do not consider any other nodes.
c) Else find a router and select it with probability
P from its contact list which is not:
- The sender
- a neighbour of sender and queried node
- Those nodes which the concerned node knows have already been queried (those in “tentative path list”)
- neighbour nodes of nodes in “tentative path list” visible from current node.
3. If a final node or router says x is detected then evaluate
P1 and P2 such that:
a) P1=best route to x from current node (in terms of time delay).
b) P2=best route to x (if reachable) among all nodes in the “tentative path list”.
4. If time delay of P1 is less than P2 then send the packet to x else inhibit.

Example for above algorithm:

We contemplate the network given in fig. 2 to understand
the operating of the algorithm. at first every node can discover its neighbours and broadcast this link info in conjunction with the corresponding communication time slots to every of its adjacent nodes. When the invention section each node has associate degree updated routing table with nodes approachable in two hops and corresponding time slots. The time slots assumed for bi- directional communication between every try of nodes is shown in fig. 3. The contact list of node A is shown in fig.
3.

Fig 2: An example of sensor network showing the time slots agreed upon for bidirectional communication between each pair of

nodes.

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 330

ISSN 2229-5518

Fig3: Contact list of node A.

Suppose at network time T1, A needs to send a packet to J, since J isn't in its contact list it'll attempt to realize a router to forward the packet. The potential routers for A ar D, E and F. Let, say solely E and F is chosen at random, then whereas causing the packet to F, A can consult its contact list and selected the trail A-C-F that is accessible in time interval t5 of network time T1 (t5-T1), instead of the trail A-B-F that takes t1-T2 time (step 3-a of the algorithm).
Now E on receiving routing request at t4-T1 will resolve from the “tentative path list” that A has send an equivalent request to F at t5-T1. Since E cannot realize the destination node in its contact list it searches for a router among the nodes A, B, D, F, H, I and K to that it's access. However solely D and K may be its potential routers, since A is that the sender, B and H ar its neighbours, F is within the “tentative path list” and that i is that the neighbour of F (step 2-c of the algorithm). however before causing the packet to K it consult its contact list and “tentative path
increase number of requests. Hence we can predict that our algorithm will give even better performance for higher values of number of requests.

250

P=0.5

200

150

100

list” to finds that F will reach K in t2-T2 following the trail F-I-K that is best than its path E-H-K that takes t3-T2 time, therefore the best path is F-I-K (step 3-b of the algorithm).

0 5 10 15 20 25 30 35

Number of requests

Fig 4.1: For NW 1
IV. SIMULATION RESULT
We have evaluated the performance of our algorithm considering the subsequent networks:
a) A little network of fourteen nodes (say NW1)
b) A randomly generated network (say NW2)
with the subsequent parameters:
1. Range of nodes: sixty
2. Minimum connectivity of every node: one
3. Maximum connectivity of any node: six

10000

9000

8000

7000

6000

5000

4000

3000

Existing algorithm

Proposed algorithm

P=0.5

We have compared the performance of the proposed algorithm with the existing algorithm [12],[13], using sample networks NW1 and NW2. We have tried to find out how different factors like number of requests and the control parameter P affect average number of transmissions and hence energy consumption. In fig. 4.1and fig. 4.2 average number of transmissions is plotted as a function of number of requests and the control parameter P, respectively. All the results have been obtained after performing 50 simulations and then taking their mean. The request sets are generated randomly and they are distinct

2000

1000

0 20 40 60 80 100 120

Number of requests

Fig 4.2: For NW2
V. CONCLUSION
for each simulation.
The average number of transmissions versus number of requests for a fixed value of the control parameter P (here
0.5) is shown in fig. 4. As seen from the figure, proposed
algorithm performs better than the existing one for both the networks NW1 and NW2. It is interesting to note that as we increase the number of requests, average no of transmissions increase almost linearly. Further since slope of the line corresponding to the proposed algorithm is smaller than the existing algorithm, the plots diverge as we
For implementing the above algorithm first of all we have
analysed some protocols of WSN with respect to some specified criteria’s and then we have proposed an energy aware routing method for wireless sensor network using random walk. Our objective is to avoid redundant sending of information so as to reduce number of transmission hence conserve energy. When a node finds more than one possible routers it will forward the packet to a set of router depending on a control parameter p. By tuning the value of p we can control and restrict redundant sending of a data

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 331

ISSN 2229-5518

packet. The algorithm is based on a decentralized approach and it maintains a very simple routing table.
The routing algorithm which we have proposed is an example of multipath routing which enjoys the advantage of being fault tolerant since more than one path from source to destination are discovered. The proposed technique results higher percentage of successful connections for larger size network for same value of P. This also leads to better distribution of the traffic load.

References:

[1]: A. Milenkovic, C. Otto, E. Jovanov, "Wireless sensor networks for personal health monitoring: Issues and an implementation," Computer Communications (Special issue: Wireless Sensor Networks: Performance, Reliability, Security, and Beyond), vol. 29, no. 14, pp. 2521-2533, August, 2006.

[2]: C. Wenjie, C. Lifeng, C. Zhanglong, T. Shiliang, "A Realtime Dynamic Traffic Control System Based on Wireless Sensor Network," International Conference on Parallel Processing Workshops (ICPPW’05), pp. 258 - 264, 2005.

[3]: 10 emerging technologies that will change the world," vol.

106, Feb, 2003

[4]: B. Blum, P. Nagaraddi, A. Wood, T. Abdelzaher, S. Son, and J. Stankovic, "An entity maintenance and connection service for sensor networks," ACM MobiSys, San Francisco, California, pp.

201 - 214, May 2003.

[5]: A. Savvides, C.C. Han and M. Srivastava, "Dynamic fine- grained localization in ad-hoc networks of sensors," MOBICOM

2001, Rome, Italy, pp. 166 - 179, July 2001.

[6]: B. C. Lai, D. D. Hwang, S. P. Kim, I. Verbauwhede, "Reducing radio energy consumption of key management protocols for wireless sensor networks," ACM International Symposium on Low Power Electronics and Design (ISLPED), California, USA, pp. 351 - 356, August 2004.

[7]: Z. J. Haas, M. R. Pearlman, P. Samar, "The Zone Routing

Protocol (ZRP) for ad hoc networks," IETF Internet Draft, July

2002.

[8]: M. Joa-Ng, I-Tai Lu, "A peer-to-peer zone-based two-level link state routing for mobile ad hoc networks," IEEE Journal on Selected Areas in Communications, , vol. 17, no. 8, pp. 1415 -

1425, August 1999.

[9]: M. J. Handy, M. Haase, D. Timmermann, "Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection," Fourth

[10]: Q. Li, J. Aslam, D. Rus, "Online Power-aware Routing inWireless Ad-hoc Networks," 7th annual international conference on Mobile computing and networking (MOBICOM), Rome, Italy, pp. 97 - 107, 2001.

[11]: M. G. Zapata and N. Asokan, "Securing ad hoc routing protocols," 1st ACM workshop on Wireless security, pp. 1 - 10, Sept. 2002.

[12]: S. Dulman, J. Wu, P. Havinga, "An energy efﬁcient multipath routing algorithm for wireless sensor network," , Pisa, Italy, April 2003.

[13]: Y. Wang, W. Song, W. Wang, X. Li, T. A. Dahlberg, "LEARN: Localized Energy Aware Restricted Neighborhood Routing for Ad Hoc Networks," IEEE Transactions on Parallel and Distributed Systems, Sept. 2006.

[14]: D. Baghyalakshmi, J. Ebenezer and S.A.V. Satyamurty, "low latency and energy efficient routing protocols for wireless sensor network," International Conference on Wireless Communication and Sensor Computing (ICWCSC ), 2010.

[15]: J. Liu, E. Poon, A. C. Chan, B. Li R. Leung, "MP-DSR: A QoS-aware Multi-path Dynamic Source Routing Protocol for Wireless Ad-Hoc networks," 26th Annual IEEE Conference on Local Computer Networks, pp. 132-141, 2001.

Author Profile:

1.Bhanu Prakash Lohani:

Bhanu Prakash Lohani is B.Tech in CSE and pursuing in M.Tech from Amity University Noida. He has three years teaching experience and one year experience in industry.

2.Monika Jena :

Monika Jena is working as Assistant

Professor in Amity School of Computer Sciences. She has

12 years of teaching experience. Her current research interests include QoS routing, multimedia communication and network computing.

3. Sanjay Kumar Dubey:

Mr. Sanjay Kumar Dubey is Assistant Professor and Proctor in Amity University, Uttar Pradesh, India. He has published more than 73 papers in National/International Journals. He has presented 14 research papers at various National/International conferences. He is member of IET and IEANG. His research areas include Human Computer Interaction, Soft Computing, and Usability Engineering.