Efficient Routing In Wireless Sensor Networks Synopsis Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

A pervasive network consists of heterogeneous devices with different computing, storage, mobility and connectivity properties working together to solve real-world problems. The emergence of wireless sensor networks has enabled new classes of applications in pervasive world that benefit a large number of fields. A wireless sensor network consists of light-weight, low power, small size sensor nodes. A typical wireless sensor network configuration consists of sensors working unattended and transmitting their observation values to some processing or control center, the so called sink node, which serves as a user interface. Due to the limited transmission range, sensors that are far away from the sink deliver their data through multi hop communications, i.e., using intermediate nodes as relays. The generation of data at source nodes occurs either proactively or in response to some request.

A fundamental problem in wireless sensor networking is how to deliver data packets among nodes efficiently without predetermined topology or centralized control. Each node in the network functions as both a host and a router, and changes of network topology are distributed among the nodes. Design of efficient and reliable routing protocols in such a network is a challenging issue. In this work, solutions are proposed after analyzing the existing conditions that will extend the lifetime of the sensor network.

1.1. Rationale

Unique characteristics of a WSN include limited power, ability to withstand harsh environmental conditions, ability to cope with node failures, mobility of nodes, dynamic network topology, communication failures, heterogeneity of nodes, large scale of deployment and unattended operation. The key challenge in wireless sensor networks is maximizing network lifetime. Energy efficiency and network capacity are perhaps two of the most important issues in wireless ad hoc networks and sensor networks. Their new requirements need optimized solutions at all layers of the protocol stack in an attempt to optimize the use of their scarce resources. In particular, the routing problem, has received a great deal of interest from the research community with a great number of proposals being made. The main objective of this work is to maximize the life time of the network by efficient routing.

The layering paradigm designed for the wired networks limits the overall functionalities of the wireless sensor networks as the very physical nature of the transmission medium is different. To overcome these limitations, a modification of the layering paradigm has been proposed, namely, cross-layer design. The different parameters can be intelligently exchanged in multi-hop wireless networks to select a route which has: more link life, good signal strength, less interference and noise ratio, less media access delay, more bandwidth and throughput and less congestion.

Many routing protocols have been developed to meet the unique and challenging characteristics of WSNs. No standards for routing have been developed yet for WSNs, nor has any protocol gained a dominant position among the research community. The assumption of homogeneous nodes does not always hold in practice since even devices of the same type may have slightly different maximal transmission power. There is very less research work done related to heterogeneous sensor networks. This research work addresses the issue of designing WSN routing methods for both stationary and heterogeneous networks that feature energy efficiency.

1.2. Scope

The main focus of this work is to analyse and investigate existing routing protocols for WSN and identify areas of improvement and to consider energy efficient routing protocols for stationary as well as heterogeneous sensor networks. Applications of wireless sensor networks often include sensitive information such as enemy movement on the battlefield or the location of personnel in a building. Lacking security services in the routing protocols, WSNs are vulnerable to many kinds of attacks. In this research work, an secure energy efficient routing protocol is also studied. Also random geometric graph as a mathematical model of WSN , and its properties are studied. A new graph model is proposed to represent heterogeneous sensor networks. Finally the social implications of pervasive computing in general and its impact on health, education and agriculture are investigated.

1.3. Research Design - Simulation

The GloMoSim library is used for protocol development in sensor networks. The library is a scalable simulation environment for wireless network systems using the parallel discrete event simulation language PARSEC. Intel Research Berkeley Sensor Network Data and WiFi CMU data from Select Lab are used to get the positions for the nodes. Data collected from 54 sensors deployed in the Intel Berkeley Research lab between February 28th and April 5th, 2004 is used for location. The new protocol is written in Parsec and hooked to GloMoSim.

1.4 Chapters Description

The thesis consists of the following chapters.

Chapter 1 Introduction

Chapter 2 Routing in wireless sensor networks

Chapter 3 A Faster routing protocol for stationary sensor networks

Chapter 4 An energy efficient routing protocol for heterogeneous WSN

Chapter 5 Secure neighbour authentication in WSN

Chapter 6 Analysis of social factors in pervasive computing

Chapter 7 Summary and Conclusions

2. Routing in wireless sensor networks

In chapter 2 , a through investigation of existing routing protocols for WSN is made. Basically WSN routing protocols can be fit in one of two major categories: on-demand such as AODV and DSR and proactive such as DSDV and OLSR. Directed diffusion is a good candidate for robust multi hop multipath routing and delivery. Location-based algorithms rely on the use of nodes position information to find and forward data towards a destination in a specific network region.

3. A Faster routing protocol for stationary sensor networks

In chapter 3, a hybrid routing protocol for stationary sensor network is proposed. A static network which is fairly distributed with a single base station is assumed for the experiment. When a node senses an event , it compares the residual energy (r) and the threshold energy (tr) levels. If r < tr, then the node has no more energy to take any transmission job and it goes off to sleep. If the node has sufficient energy, it checks the data buffer for an equivalent entry. If a match is not found, it measures the strength of the received signal. If it finds one, the packet will be discarded. The node calculates the feasibility of a single hop transmission taking into account SNR and location of the destination. If feasible, it sends the data directly to the destination. Otherwise the node computes the best neighbor and forwards data.

3.1 Best Neighbour Algorithm

This is based on residual energy level of the neighbour, signal strength, usage count and the location.

Pick the first neighbour with the least use count

If (residual energy level > threshold )

If (SNR is high) Forward the data

Else Repeat the process eliminating the current node explored.

3.2 MELP Metric

A new metric called MELP is proposed for optimizing the life time of WSN for stationary sensor networks. Minimum energy load aware path metric (MELP) is defined as

where S is the packet size and the remaining terms are defined below.

Expected transmission time, where pf is the probability of packet loss in the forward direction and pr is the packet loss probability in the reverse direction.

Remaining capacity, where Bi is the transmission rate of node i, fik is the transmission rates of Ni current flows that traverse node i and is the link quality factor.

Load balancing factor,

Interference ratio for a link i ,

3.3 Results and Discussion

Fig 1 Fig 2

Figure 1 shows the execution time of three protocols for different sets of nodes and traffic. The execution time increases as the traffic increases. Due to control packets overhead in route discovery and maintenance AODV and DSR have high execution time as against the proposed protocol. Figure 2 is an indication of congestion control in the various protocols. The more number of collisions indicate high traffic in a particular region. The redundancy suppression and SNR factor manage the congestion efficiently than AODV and DSR.

Fig 3 Fig 4

Figure 3 shows the average hop count where the proposed model has the lowest and AODV has the highest. If the link quality is good then direct transmission is possible. In this case the hop count will be equal to 0. The average hop count will always be less than or equal to the other models as it chooses the best neighbour at each cycle. Figure 4 shows the total number of signals transmitted for a given traffic. The proposed model has transmitted less number of signals and therefore consumed less energy compared to the other protocols.

3.4 Conclusion

Latency time is critical to the functioning of the environmental monitoring sensor networks. Also energy resource limitations are of priority concern in sensor networks. The proposed model has less time delay, more energy and better distributed work mode. This can be very effective for detecting environmental changes where sensors have a fixed location.

4. An energy efficient routing protocol for heterogeneous sensor networks

In chapter 4, an energy efficient routing protocol for heterogeneous sensor networks is proposed with the goal of finding the nearest base station or sink node. Hence the problem of routing is reduced to finding the nearest base station problem in heterogeneous networks. When a node senses an event, it sends a request packet which contains the Node ID, Destination ID , Time and Location. A node (i) which receives the request packet computes the probability of a link between itself and the source. The factors that are taken into consideration are the distance between the source and the node, the energy level of the node, the type of the node and the type of the node's neighbours. The initial probabilities are set based on the type of the node. If the type is a base station or a sink node (Value : 2) , the probability p(i) is set to 0.75. If the type is a high energy rechargeable node (Value : 1) , the probability p(i) is set to 0.5 and for the low energy static node (Value : 0), p(i) is set to 0.1. The probability may be increased or decreased after receiving a request packet. If the probability is greater than 0.5, a reply packet is sent to the source node. Otherwise the request packet will be discarded. The reply packet consists of Neighbour ID, Location, Type, Time and the Probability. When a node receives a reply packet, it updates its routing table with Neighbour ID, Location, Time, Type and the Probability. Finally the node picks the best neighbour from the routing table by applying the A* search algorithm. The protocol HLAODV when compared with popular routing protocols AODV and DSR is energy efficient.

4.1 Algorithm

Source Sends REQ packet

Node Receives REQ packet

Node Checks Recent REQ/REP List

If (! Recent)

Node Self computes Probability P

If P >= 0.5 , node sends a REP packet

Else discard it; Exit;

Else Discard it; Exit;

Source receives a REP packet

Source updates the Route Table

Apply A* Algorithm to pick the best neighbour

Forward Data to the next Hop

If the next Hop is the Destination , Exit;

Else If the next Hop is a base station , Exit;

Else Forward; Go to 1;


4.2 NSM Metric

A new metric NSM is proposed for energy efficient routing. Nearest sink node metric (NSM) is defined as

Where Tj represents the type of node.

Tj = {0 , if i = Stationary node

1 , if i = rechargeable mobile node

2. if i = Sink node/Base station

NTj = max { NSMk

and the other parameters as defined in MELP metric.

4.3 Results and Discussion

Fig 5 Fig 6

Figure 5 shows the execution time of three protocols for different sets of nodes and traffic. The execution time increases as the traffic increases. When there are no base stations HLAODV tends to take more time than AODV and DSR protocol. Figures 7 and 8 show the number of signals received and transmitted by the nodes. There is a sharp difference in signals received in the new protocol as compared to others.

Fig 7 Fig 8

Fig 9

Figure 6 and 9 show the congestion control of the protocols by studying the number of collisions and time out packets. The proposed protocol has very few numbers of collisions as compared with other protocols. Moreover the timeout packets are generated less in number in HLAODV. The reason is that within a specific region, only one node is allowed to transmit for a period of t seconds. This not only avoids congestion but also takes care of redundancy suppression.

4.4 Optimized Routing using random geometric graph model

Optimized routing is maximizing the network life time by minimizing energy consumption through efficient transmission in a multihop communication. Random Geometric Graphs (RGGs) have been a very influential and well-studied model of large networks, such as sensor networks, where the network nodes are represented by the vertices of the RGG, and the direct connectivity between nodes is represented by the edges. The random geometric graph denoted G(n,r), is where the n nodes (or sensors) locations are chosen uniformly and independently at random (according to some probability distribution) in a region and two points are connected by an edge if they are within a distance less then a certain value r .

Let there be n number of nodes within a radius r. The problem is to find an optimal path from a source to a destination. Connecting two vertices, u, v is possible if and only if the distance between them is at most a threshold r, ie. d (i, j) ≤ r. An edge appears iff d(i,j) is less than r and if the probability computed based on the distance between i and j , type of j , neighbours of j and energy level of j is greater than a threshold value(0.5). A random geometric graph with radius r as the transmission range of the node can be constructed. The essential conditions for optimized routing namely, a one dominant random geometric graph and coveredness of the vertex are identified using random Geometric Graph model.


Optimized Routing : Maximizing the network life time by minimizing energy consumption through efficient transmission in a multihop communication .

One dominant random geometric graph : In a RGG, if there exists atleast one base station/sink node within the radius r.

Energetic node :A node is said to be energetic, if the remaining energy E(v) is above the energy threshold. ET.

Coveredness of a vertex: A vertex v is to be covered if there is atleast one dominant vertex dv in the random geometric graph with radius r that includes both v and dv and is energetic.

4.5 Results and Discussion

Fig 10 Fig 11

Fig 10 shows the distribution of sensors under study. The sensors filled as black are the nodes that are not covered. They can not ideally participate in optimized routing. Figure 11 shows the number of signals received and transmitted by the nodes. There is equal energy spent on receiving phase as transmission phase. There is a sharp difference in signals received in the new protocol as compared to others.

4.6 A new graph model to represent heterogeneous sensor networks

The standard RGG model is proved to be not suitable to represent real time heterogeneous WSN and therefore a new graph model to represent heterogeneous sensor network is suggested. Also the properties of dynamic RGG are studied.

Fig 12

Fig 12 shows the non uniform radii RGG representing a real time heterogeneous network.


Strong Links SL: Between two vertices v1 and v2 , the edge connecting v1 and v2 is said to be strong when P(v1,v2) >= 0.5. where p(i,j) = f(d(i,j) , e(j), t(j),n(j))

Weak Links WL : Between two vertices v1 and v2 , the edge connecting v1 and v2 is said to be weak when P(v1,v2) < 0.5.

Path in DRGG - A set of (V, E) such that E {SL}

Guaranteed Delivery - If there exists a path in DRGG , the delivery is guaranteed.

Strong Node SN - A node is strong if it lies in a path in DRGG

Weak Node WN - A node that is within the transmission range of any node X but is not in a path in DRGG.

Isolated Node - A node is isolated if there is no node within its transmission range.

4.7 Transmission Range Vs Radius

To calculate radius r, Friis transmission equation is used. Friis transmission equation for free space loss is given by ,

There can be a big difference between the theoretical transmission distance and the actual results in the field. These calculations are based on an unobstructed line-of-sight signal with no electronic interference. However, the real world presents many variables that result in less-than-perfect wireless performance, such as mismatched impedance, electronic noise, building obstructions, reflected signals, etc.

The distance is further reduced based on the remaining energy level (Er) , threshold energy level (Eth) and the type of the node (Tn).

If (Er ≈ Eth and Tn = 0) then r = 0.

If (Er ≈ Eth and Tn = 1) then r = r - µ , where µ is a constant which is proportional to Er.

For the other cases the actual transmission distance as computed by the formula is retained.

4.8 Results and Discussion

Table 1 shows the reachability matrix. The first column represents the nodes. Each row has the reachability of the nodes arranged in the order of best neighbour.

Table 1 Sample Reachability matrix

































Fig 13 Fig 14

Figure 13 shows the transmission range of the nodes as computed. The fluctuations prove that the uniform radius RGG is not suitable to represent real time network. Figure 14 shows NBS based node distribution. As per the routing metric NBS , optimized results can be obtained at time 't' if the nodes on 1 scale are selected to transmit. Those on the 0 scale do not have a base station within its transmission range.

4.9 Conclusion

An energy efficient routing protocol for heterogeneous pervasive networks based on location is proposed to maximize network life time. Simulation results show that our protocol HLAODV outperforms AODV and DSR in energy efficiency, latency, load balancing, redundancy suppression and congestion control. The model is a cross layer design as the link parameters determine the routing scheme.

5. Secure neighbour authentication in WSN

In chapter 5, a secure neighbour authentication mechanism for WSN is proposed. A secure routing in WSN must address several challenges: vulnerable wireless communication, highly resource-constrained senor nodes in terms of processing power, storage, and battery life, and the risk of physically captured. However, a few of existing routing protocols for WSNs have been designed with security as a goal. As sensors communicate in a multi-hop fashion, identification of secure neighbours in a mobile topology is critical for routing. Since these devices are resource constrained, a secure neighbour authentication protocol based on a variant of HB , an authentication protocol for RFID devices is proposed. Our work described the defense against some attacks in WSN by introducing neighbour authentication in routing using shared secret keys between the sensor nodes. The basic version of HB+ a protocol for resource constrained WSN is adopted. The key objective of our approach is to choose a trusted neighbour for multihop communications. For most of the known attacks, the proposed scheme does well to identify trusted neighbour. Also the given scheme is energy efficient for the resource constrained sensor networks.

All communications via a node are not confidential messages. So a field is introduced in the request packet which differentiates a secret message. When a node receives a request packet with the secret field set, it assumes secure communication mode. The following scenarios are expected.

The reply node is a known node to the request node.

The reply node is an unknown node but has a known friend node to the request node.

The reply node is a stranger to the request node.

5.1 To prove knownness of a node

Since both the request and reply nodes are relatives, they are assumed to be sharing two secret keys x, y and a refreshable noise parameter €. A variant of HB+ protocol is applied for secure neighbour authentication. The mechanism is based on learning parity with noise and is NP hard. In the original HB+ protocol , n number of rounds are used between the reader and the tag. The sensor networks can not afford n number of transmissions for every request-reply. Here a varying number of rounds of HB+ protocol are performed to convince the source node. Two more parameters time and route are introduced for better authentication. Both the relative nodes share two secret keys x, y { 0, 1}k . A noise factor € { 0, 1}k is added to signal to noise ratio (SNR) to tighten the security. It is very difficult for an adversary to capture x and y with the presence of noise.

Source node challenges with a { 0, 1}k . The reply node responds by sending b { 0, 1}k and in two different routes. This is repeated for several times with a new set of a and b values. a, b and z are sent via different routes. Estimated time to get the response is set in the request node. If it fails to get a response within 't' seconds, automatically the request packet is refreshed with another challenge number a. The request node keeps track of recent response numbers 'b' s. This helps to avoid an adversary trying to capture the pattern x and y. The noise parameter is computed at the request node based on SNR. The noise factor is also periodically refreshed by the base station. It is very difficult to compute x and y from a, b and z. The problem is NP hard.

Req (x, y, €)

Rep (x, y, €)

a { 0, 1}k

b { 0, 1}k


Fig 15 One round of authentication

5.2 Voucher System

The reply node is an unknown node but it has a friend neighbour node. This is called a voucher system. A node becomes a friend if the base station authenticates it as a friend node and updates the nodes about its presence. The friend node does the authentication on behalf of the reply node. In secure communication mode, the reply node contacts the friend node which knows the shared keys. After verification, the reply node becomes the trusted neighbour of the request node.

Request Node ---------ƒ Reply Node ------------------ƒ  Friend Node -----------------ƒ  Request node

5.3 Results

Fig 16 Fig 17

Fig 16 shows the usage of nods in transmission. The malicious nodes are never used as per the protocol. Fig 17 explains the energy efficiency of the protocol.

5.4 Conclusion

For most of the known attacks, the proposed scheme does well to identify trusted neighbour. Also the given scheme is energy efficient for the resource constrained sensor networks.

6. Analysis of social factors in pervasive computing

In chapter 6, the social factors pertaining to pervasive computing and in particular to WSN are analyzed. Pervasive computing has the potential to cut across cultures and countries, to be both locally valuable and globally pervasive. To reach this potential, it's important for researchers to recognize the challenges, rewards, goals, and methods of developing these technologies not just in wealthy IT-saturated environments, but in developing economies and regions as well. Technology assessment for pervasive computing that is oriented towards sustainable development should, therefore, pay attention to trends that may be socio-economically irreversible. Since pervasive computing is expected to become ubiquitous in the coming years, the question arises whether it will support sustainable development or may counteract that aim. The results of a technology assessment study show that pervasive computing could amplify already existing problems related to the environment, human health, and society. Power consumption for digital networks, e-waste streams, and exposure to non-ionizing radiation may all increase. Furthermore, social sustainability could be threatened by the technology if it is applied in a way that restricts consumers' privacy and freedom of choice.  

   To make pervasive computing sustainable, precautionary measures have to be initiated at the earliest possible time. First of all, national strategies towards sustainability are to be seen as a paradigm for the technological innovation process. Without a clear strategy to promote the social and ecological compatibility of new technologies, the innovation process would be purely technology-driven and might cause severe conflicts and high external costs in the future.   Foresight and monitoring activities are appropriate methods to generate early warnings about risks caused by novel technologies. Scientific minority opinions may serve as early warnings.

  Pervasive computing becomes interesting for business and consumers when opportunities outweigh the risks - not only for the individual user, but also for society and the environment.

7. Summary and Conclusion

Wireless sensor networks and radio frequency identification (RFID) devices are quickly becoming a vital part of our infrastructure with applications ranging from supply-chain management to home automation and healthcare. These tiny, pervasive computing devices have extremely limited power resources and computational capabilities. On the other side there also exist heterogeneous wireless networks in which devices have dramatically different capabilities. Also some applications in WSN require authentication protocols that work in general such that a resource limited device authenticates another resource limited device. In this work a complete framework is proposed for routing in WSN taking into account the different types of applications.