Routing Protocol Sensor

RGP: A QoS routing protocol for sensor networks

Abstract Since wireless sensor networks are used in many applications to collect real time data, it is necessary to develop lightweight protocols which satisfy the real time requirements. In this paper we have developed and implemented a DFS (Depth First Search) based routing protocol to guarantee the end to end delay under a given delay bound. The proposed Real time Geographic Routing Protocol (RGP) routes a packet towards the destination based on a compromise between distance and queue count to reduce traffic concentration on some nodes closest to destination and uses Gradient Table to store the route satisfying the delay bound. We evaluated the performance of our protocol by using TOSSIM - a TinyOS mote simulator. The simulation results show that the End to End delay of our routing protocol is improved significantly for large networks.

Keywords sensor networks, geographic routing, real time, DFS, QoS

INTRODUCTION

Advances in micro-mechanical and computer engineering technology facilitate the development of low cost, low power, multifunctional sensor devices. It is feasible to deploy these small sensor nodes in large numbers, and without pre-existing infrastructure. Therefore sensor networks, with their flexible and scalable nature, have great potential for a variety of applications such as battlefield surveillance, monitoring wildlife habitats, tracking vehicles, health monitoring, etc.

Since Wireless Sensor Networks (WSNs) deal with real world, the timeliness requirement is now becoming an important issue for sensor network. In fact, sensor devices are intended to capture data from the physical environment, process them and send them to the base station in order to interpret the data, and consequently take the convenient action. Hence, a sensory data that reaches the base station out of a given delay may have negative effect on the quality of some sensor applications. A lot of real-time sensor applications are being defined. In military or environmental surveillance systems, the sensory data must reach the control monitor in a limited time interval to ensure a fluid tracking in the observed region. Also, for medical care applications, sensor devices are expected to capture real-time vital signs from a large number of patients. In emergency situation, critical sensory data must be displayed at the doctor's control monitor in a limited time so that to take the correct action.

In this paper we present and implement a real-time routing protocol based on Depth First Search (DFS) algorithm for sensor networks. We evaluate our proposal by using TOSSIM, a TinyOS simulator that compiles directly from TinyOS code.

This paper is organized as follows. Section 2 discussed related work. The detail of our protocol is described in Section 3. Experiment results are given in section 4. Section 5 concludes the paper.

RELATED WORK

Although the main focus on WSN research and development is the ad hoc protocol design and power saving, some proposals have existed for supporting real time communication under the term of QoS (Quality of Service). In WSN, QoS and real-time mechanisms (scheduling, routing, medium access) are typically defined at the MAC and Network Layers. For example, LEACH is a MAC protocol which is based on TDMA for providing bounded access time but suffers the scalability problem. Additional examples for MAC protocol are DB-MAC and D-MAC which are based on CSMA/CA with dynamic priority assignment but in condition that the network can be organized as a hierarchical data gathering tree topology (note that this limits their deployment on a general meshed network). Examples of routing protocols can also be found such as SPEED [2], and network architecture RAP [1]. The SPEED protocol is a sensor network specific routing solution that aims to reduce the end-to-end deadline miss ratio by maintaining a desired delivery speed across the sensor network. However, SPEED does not consider any further problems such as power energy, transient behavior, message losses, congestion, noise, etc. RAP is real-time communication architecture for large-scale sensor networks which uses velocity monotonic scheduling (velocity is defined as the ratio between the distance of the packet to its destination and its deadline) to prioritize real-time traffic and enforces such prioritization in a traffic differentiated MAC layer. But there is no guarantees are given in RAP.

In sensor networks, location is more important than specific node's ID. The Greedy Perimeter Stateless Routing (GPSR), the Depth First Search (DFS) and SPEED are geographic routing protocols which discover the route based on geolocation of sensor nodes in condition that each sensor knows the location coordinates of itself, its neighbors, and the base stations. This assumption can be performed by virtual coordinate systems such as NoGeo [11], GEM [12], and BVR [13]. The routing strategy of a sensor in geographic routing protocol is simply to forward its packets to the neighbor that is closest to a base station. Because there is no routing information (other than the set of neighbors) to be maintained, the routing paths instantly adapt to the change of the topology. But there may be void(s) between a source sensor and a base station. A routing path based on geolocations may be blocked from moving closer to a base station due to the lack of relaying nodes to cross the void. One solution for this problem is based on the right-hand rule, which routes a packet around the void. However, the right-hand rule may produce inefficient routing paths that include many unnecessary nodes.

RGP PROTOCOL

Overview and Assumption

We now describe the detail of RGP. Our protocol has been broken into several components, show in Figure 1.

Packet received from Application Layer will be passed to Forwarding Handling Component where it is processed. The Forwarder Module in Forwarding Handling Component is responsible for choosing the next node from its Neighbor Table to forward the packet. Each time the next node is known, sensor node will set up appropriate gradient in Gradient Table which is used in future.

Neighbor Handling component stores the information of one hop neighbors in Neighbor Table which is updated by beacons (e.g. HELLO message).

Before we discuss the operation of each component in detail, we state the assumptions:

The link is bi-directional, i.e. if node A is a neighbor of node B then node B is A's neighbor.
The time is synchronized on all nodes in networks.
Each node knows its own location and base station's location.
Neighbor Handling

Due to the routing decision based on the information of one hop neighbors, it is very important to guarantee that this information is correct and up to date. Each sensor node broadcasts the HELLO message to its neighbors periodically. To avoid collision of the HELLO messages from two neighbors, the sensor node adds a random delay (within the selected range) before broadcasting. The HELLO message includes the identifier of node (ID), location of node and a sequence number. The purpose of the sequence number is to ensure freshness of an HELLO message.

Upon receiving HELLO message from node B, node A checks to see if node B is in its neighbor table. If so, it will update new lifetime for B's entry. If not, A will add a new entry for B.

The information in neighbor table has become less accurate as one of neighbors may leave out or a new sensor node enters radio range. If a node does not receive a HELLO message from a neighbor after a period of time, it will delete that neighbor from its Neighbor Table and make the appropriate changes to its Gradient Table.

The Neighbor Table includes following fields:

Neighbor address (NodeID) - This is the identifier of node.
Lifetime - This is the interval to wait without receiving anything from a neighbor before considering the link unavailable.
Queue count - This is the number of packets waiting in a queue to be sent. If this value is zero, there are no packets need to be sent to this neighbor in the queue.
Sequence Number (SeqNo) - This is the number of the last packet received from that neighbor. RGP uses this field to acknowledge a transmission of a neighbor and to identify packets that are out of sequence.
Location - geographic position of the node.
Forwarding Handling

We designed and implemented our protocol based on the Depth First Search (DFS) routing algorithm. In DFS, each node puts its name and address on the route discovery packet p. Then it forwards p to a neighbor who has not seen p before. This neighbor is one of all the neighbors which minimize d(S,y)+d(y,D), where d(x,y) is Euclidean distance between nodes x and y. If a node has no possibilities to forward the packet, it removes its name and address from the packet and returns the packet to the node from which it originally received it. Route discovery packets are kept for some time. If a node receives twice the same packet, it refuses it [7].

Let S be a sensor node generating time sensitive data to be sent to the sink D. Node S checks its Neighbor Table and finds that node A has smallest distance to D. Therefore node S forwards packet to node A. Similarly, the packet is forwarded to node B, C, E. At node E, there is no neighbor which satisfies the forwarding condition of DFS algorithm. Node E will send packet back to node C and node C send to node B. Node B forwards the packet to the next choice H in its sorted list of neighbors, if such a neighbor exists. Finally node H forwards packet to node D.

It is easy to see that DFS does not support QoS. First, the link between sensor node and the neighbors closest to the destination may have high delay. Second, those neighbors can attract much traffic. It results in the increasing of delay and collision probability. Third, in some cases the packet has to go through many unnecessary nodes. It means the end to end delay may be very high.

Where

c(Ai, D): the cost value of neighbor Ai of node A to forward to destination D (in case of broadcasting to region R, D is center of R).
r: a weight that is generated randomly
d(Ai, D): the Euclidean distance from Ai to the D.
Max{di}: the largest Euclidean distance among all neighbors of A to N.
qci: the number of messages is waiting in queue to be sent to node Ai.
Max{qci}: the highest queue count (qci) of all neighbors.

The cost function is a compromise between queue count and the distance to destination. It helps to reduce the traffic concentration on nodes closest to destination.

In order to guarantee the end to end delay, we add a delay bound to packet header. Each time node detects the invalidation of delay bound in received packet it will send packet back to the neighbor which sent the packet. The reason we don't include the single hop delay in cost function is that it is difficult to measure this delay exactly.

The use of routing table in sensor network is infeasible since WSN can have a large number of sensor nodes. But it is inefficient if we have to discover the route each time sending packet. Especially, the route can include many unnecessary nodes (e.g C,E as shown in figure 1). To solve this problem we create a Gradient Table with following fields:

Next Hop - This is the next hop to forward
Location - The location of destination
Radius - The radius of region R (equal to 0 for unicast communication)
Expire time

In Gradient Table, there is not the identifier of source node. For the vast majority of applications the most important communication is from sensors to base stations. Since the number of base stations is limit, the size of table is decreased significantly.

We now describe the process of forwarding a packet to base station D.

RGP packet header includes a flag field indicating whether the packet is in outside forward mode, outside backward mode or inside broadcast mode. Upon receiving a packet P, node A checks its gradient table. If a matching gradient is found out, A will forward P to the node indicated in gradient. If such a gradient does not exist, packet P will be handled according to one of following cases:

P is an outside forward packet. A inspects the delay bound field to determine whether or not the deadline of P has expired. If delay bound is negative, P will be immediately returned to node which sent P. A also checks whether it is destination. If yes, A transmits P to higher layer. If not, Forwarder Module memorizes the neighbor node S that forwarded P and sorts A's Neighbor Table according to cost function c(Ai, D). From this sorted list, we can choose node B which has smallest c(Ai, D) and Ai is different from S, is the next hop for forwarding. If node B exists, A set up a gradient to B in Gradient Table, update delay bound field in P and then forward P to B. If not, node A changes the flag field in P's header to outside backward and returns P to S.

Delay Bound = Delay Bound - (Current Time - Sent Time)

P is an outside backward packet. Forwarder Module in node A sorts Neighbor Table of A according to c(Ai, D) and selects the next choice B in that sorted list, if such a neighbor exists. Assume that A has the set {B1, B2, ..., Bi, ..., Bk} is the sorted list neighbors where Bi is the node from which A received P. If k > i, the next hop for forwarding will be Bi+1. In that case, the flag field will be changed to outside forward. A also updates the gradient to node E. If k = i, it will return P to the neighbor S which was memorized above and delete the gradient with respect to destination in Gradient Table. To prevent loop, node will drop packet if it is source node. There is not any route to destination in this case.

The forwarding process to a region R is almost similar to the above process but it also has some differences. When a node receives an outside forward packet, it checks whether the packet is inside the region R. If the condition is satisfied, it sets the flag field in P to inside forward and broadcasts P to its neighbors. Therefore it has one more case that need to be considered.

P is an inside broadcast packet. In case P is a new packet and A is inside R, A will broadcasts P to its neighbors. Otherwise, A simply drops P. We don't need to check the value of delay bound here because most of sensor network applications only require guaranteeing End to End Delay when sensor nodes send data to base station.

EXPERIMENTAL RESULTS

We have implemented our protocol in TOSSIM [8]. TOSSIM is a discrete event simulator for TinyOS sensor networks. Instead of compiling a TinyOS application for a mote, users can compile it into the TOSSIM framework, which runs on a PC. This allows users to debug, test, and analyze algorithms in a controlled and repeatable environment. As TOSSIM runs on a PC, users can examine their TinyOS code using debuggers and other development tools. Although TOSSIM is a very simple simulator, it tries to capture high fidelity of TinyOS in a very low level, which simulates the network at bit level. However TOSSIM doesn't model radio propagations and provides random ADC readings.

In order to generate network traffic we created a simple temperature monitoring application. The application uses a timer to periodically request data from the temperature sensor and send the current reading to base station.

Since every node can communicate with each other by default in TOSSIM, we defined a loss topology manually. The links between pairs of nodes that can communicate with each other are shown in Fig. 3. Asymmetric links were not used during the evaluation of our protocol. All links were defined as having a 0% error rate. We can guarantee the bi-direction neighbor relationship by using ACK. Fortunately, ACKs are on in TOSSIM by default.

We used the following metrics to evaluate the performance of our protocol.

Packet Delivery Ratio: is defined as ratio of the total over all nodes of the number of data packets received, divided by the total number of data packets sent from the sources.

Routing Overhead: the number of routing packets transmitted per data packet delivered at the destination.

End to end delay: the time taken for a packet to be transmitted across a network from source to destination.

In our evaluation, we compare the performance of our protocol with DFS. As the number of motes increases, the delivery ratio of data packets decreases because more packets need to be retransmitted due to errors. With most of cases, the packet delivery rate of RGP is higher than DFS except for 25 motes, RGP is little smaller than DFS.

The routing overhead of DFS and RGP is almost similar (Fig. 5). With a smaller number of motes, the congestion at some attractive nodes rarely occurs. Moreover the route discovered by DFS has smallest distance to destination due to the characteristic of our simulation topology. Hence, the End to End (E2E) Delay of DFS is lower than the one of RGP. With a larger number of motes, however, E2E of RGP is better.

V. CONCLUSIONS

We have proposed a DFS based routing protocol that provides QoS for sensor networks. Our protocol does not require sending back pressure beacons for solving the congestion and void problem like SPEED. It means RGP saves power energy than SPEED. The results of our implementation in TOSSIM show that the End to End delay of our routing protocol is improved significantly with large number of motes. We are working to implement our protocol in Mica Mote to study its performance in a real world.

We provide a professional essay writing service that thousands of our customers use as an effective way of improving their grades, improving their research and saving them lots of time.