Data Centric Routing In Sensor Networks Using Biased Walk

2011-04-15T12:08:00.000+04:30

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 .

In The Name Of God ...

2011-04-09T22:02:00.006+04:30

سال 85 بود که اولین بلاگمونو رو سرورای بلاگفا آوردیم بالا ... یادش بخیر ، چه حالی میداد . ایام جالبی بود . تا این که چو افتاد بلاگفا اطلاعات کاربراشو می فروشه به این ور اونور !!! خداییش من ترسیدم . یوخده با خودم کلنجار رفتم اما در نهایت از بلاگفا زدم بیرون . در به در دنبال یه سرور خوب تا خوردم به پست گوگل و بلاگر . اما چشتون روز بد نبینه تا اومدم استفاده کنم زدن بابای بلاگرو آوردن جلوی چشش و فیلترش کردن . مام که از این جا مونده و از اون جا رونده رفتیم دنبال یه خونه جدید تا با پدیده ای به نام وردپرس آشنا شدیم . اما نمی دونم مشکل از کی بود . از من بود که نتونستم با وردپرس خوب کار کنم یا واقعا خوب نبود اصلا . آخرشم نفهمیدم . حدود یه ماه باهاش کلنجار رفتم اما رام نشد که نشد . اونجارم ول کردم و رفتم دنبال یه جای دیگه غافل از این که دارم میرم سراغ یه خونه دایمی . رفتمو وبلاگ رو پیدا کردم . باید اعتراف کنم که طولانی ترین مدت رو اونجا بودم . وبلاگ سرورای خیلی قوی داشت . کار کردن باهاش راحت بود و از کلی از سرویسای خام وردپرسم پشتیبانی می کرد . فضای نامحدود میداد بهتون و هزارتا کار دیگه می کرد . تا زمانی که چشتون روز بد نبینه ( اگه رو لینک وبلاگ کلیک کنید چشتون میبینه .) وبلاگ زد و خودشو خراب کرد . ما موندیمو کلی اطلاعات تو وبلاگمون که پریده بود . کلی پروژه . اما چاره ای نبود . باید دوباره را میوفتادیم . را افتادیم و گشتیم . اومدیم سراغ خونه اول . هنوز فیلتر بود . احتمالا حالا حالا ها هم فیلتر باقی خواهد موند اما چاره چیه ؟ بلاخره باید کاری کرد . حالا اینجاییم و شما دوست عزیز ، حتی شما دارید این پست اول رو می خونید . این پست اوله که انشالا باهم پست هزارم رو جشن بگیریم . خودمونو محدود به مضمون نمی کنیم . هر چی که به درد خورد میذاریم . خودمونو محدود به زبانم نمی کنیم ، فارسی یا انگلیسی به هر زبونی بود میذاریم اما سعی میکنیم عنوان پستامون انگلیسی باشه . همین . سرتونو درد نمیارم . موفق باشید و کمکمون کنید . یا علی

Black Crow

Data Centric Routing In Sensor Networks Using Biased Walk

In The Name Of God ...