Data Centric Routing In Sensor Networks Using Biased Walk

Abstract :

We present Spiral , a data centric routing algorithm for short term communication in unstructured sensor networks . Conventional data centric routing algorithms are based on flooding or random walk . Flooding returns the shortest route but has a high search cost ; random walk has a lower search cost but returns a sub optimal route . Spiral offers a compromise between these two extremes it has a lower search cost than flooding and returns better routes than random walk . Spiral is a biased walk that visits nodes near the source before more distant nodes . This results in a spiral like search path that is not only more likely to find a closer copy of the desired data than random walk , but is also able to compute a shorter route because the network around the source is more thoroughly explored . Our experiments show that in a 500 node network with an average degree of 20 and two copies of every data object , for a short term communication of 40 packets the total communication cost by Spiral is only 72% of that by flooding , 81% of ERS , 74% of random walk , and 73% of DFS .

Introduction :

We present a data centric routing algorithm called Spiralfor short term communication in wireless sensor networks . Spiral balances the cost of route discovery and route length , making it efficient for short term communication of tens or hundreds of messages . This reduces the overall communication overhead , and hence the energy consumption , for short term data transmission in wireless sensor networks . Spiral is intended for data centric routing . Unlike address centric routing in which the source node searches for a route to the destination node , in data centric routing the source searches for a particular data object stored on an unknown subset of nodes . Hence the routing problem is actually a query problem the routing algorithm must search for the route to a node with the desired data , then the data can be transmitted along the discovered route . Due to the large data redundancy in sensor networks , data centric routing has proven to be a good scheme for minimizing communication overhead and energy consumption . Data centric routing normally has two phases : route discovery and communication . The route discovery phase determines the best route between the source node and a node with the desired data . During the communication phase the data are transmitted from the destination to the source . The relative lengths of these two phases influences the choice of routing algorithm . At the two extremes either the communication is long lived , or it consists of a single response to the query ( one shot ) . For the former the route discovery overhead is less important , as it will be amortized over the long communication . What is important is the resulting route length , as the subsequent communication must traverse the route and a sub optimal route will have high overhead . For the latter extreme the route discovery cost is much more important than the discovered route length ; it may not pay to find a short route if the communication is one shot . In this paper we propose a route discovery algorithm , Spiral , for short term communication in which both the route discovery cost and resulting route length are important . For example , in data queries for historic data , the collected data may be much bigger than a single datum , hence need to be encapuslated in multiple packets for transmission . Another example is short term monitoring , in which the observer searches for an interesting sensor and then monitors it for a short time . These data transfers are likely to require multiple messages , but will not be long lived . Spiral reduces the communication overhead and the energy consumption for both route discovery and subsequent communication . Like the route discovery algorithms for one shot communication , Spiral uses a walk based mechanism to reduce the overhead of searching for the desired data ; Spiral uses a spiral like search path that visits nodes near the source before more distant nodes . This is particularly beneficial when there are multiple copies of the desired data , as Spiral will tend to find a close one first . Our experimental results show that for  route discovery in a 500 node network with average node degree of 20 and two copies of every data object , Spiral’s message overhead is only 8% higher than the random walk  based algorithms , but only 46% of that in the flood based algorithms . Spiral’s route lengths are only 10% longer than the optimal routes ( from the flood based algorithms ) , but only about 66% as long as those produced by the random walk based algorithms . Overall , Spiral is most efficient for short  term communication of tens to hundreds of messages in dense networks . For example , Spiral’s total cost for a short term communication of 40 packets is only 72% of that by flooding , 81% of ERS , 74% of random walk , and 73% of DFS .