View Full Document

25 views

Unformatted text preview:

Rendezvous Regions A Scalable Architecture for Service Location and Data Centric Storage in Large Scale Wireless Networks Karim Seada Ahmed Helmy Electrical Engineering Department University of Southern California seada helmy usc edu Abstract In large scale wireless networks such as mobile ad hoc and sensor networks efficient and robust service discovery and data access mechanisms are both essential and challenging Rendezvous based mechanisms provide a valuable solution for provisioning a wide range of services In this paper we describe Rendezvous Regions RRs a novel scalable rendezvous based architecture for wireless networks RR is a general architecture proposed for service location and bootstrapping in ad hoc networks in addition to data centric storage configuration and task assignment in sensor networks In RR the network topology is divided into geographical regions where each region is responsible for a set of keys representing the services or data of interest Each key is mapped to a region based on a hash table like mapping scheme A few elected nodes inside each region are responsible for maintaining the mapped information The service or data provider stores the information in the corresponding region and the seekers retrieve it from there We run extensive detailed simulations and high level simulations and analysis to investigate the design space and study the architecture in various environments including node mobility and failures We evaluate it against other approaches to identify its merits and limitations The results show high success rate and low overhead even with dynamics RR scales to large number of nodes and is highly robust and efficient to node failures It is also robust to node mobility and location inaccuracy with a significant advantage over point based rendezvous mechanisms 1 Introduction Current research in infrastructure less wireless networks can be categorized into two main categories mobile ad hoc networks and sensor networks There are many similarities between the two categories but the major challenges are typically different For efficient service provisioning the challenges in ad hoc networks are the lack of infrastructure and the highly dynamic nature of nodes and their unpredicted mobility patterns While in sensor networks the challenges are mainly the limited resources and the extremely large number of nodes Some applications of sensor networks involve also mobility In sensor networks each device is capable of some computation wireless communication and sensing under energy constrained conditions Communication in sensor networks is typically application specific and data centric and it consists of the tasks sent to nodes and the data recorded by nodes about the environment Typical approaches for locating resources and data items in these networks rely on either flooding or centralized external storage Both could suffer from scalability and efficiency problems In this paper we describe Rendezvous Regions RRs a novel self configuring scalable efficient and robust rendezvous based architecture In our architecture the network topology space is divided into rectangular geographical regions where each region is responsible for a set of keys representing the data or resources of interest A key ki is mapped to a region RRj by using a hash table like mapping function h ki RRj The mapping is known by all nodes and is used during the insertion and lookup operations A node wishing to insert or lookup a key obtains the region responsible for that key through the mapping then uses geographic aided routing to send a message to the region Inside a region a simple local election mechanism dynamically promotes nodes to be servers responsible for maintaining the mapped information Replication between servers in the region reduces the effects of failures and mobility By using regions instead of points our scheme requires only approximate location information and accordingly is more robust to errors and imprecision in location measurement and estimation than schemes depending on exact location information Regions also provide a dampening factor in reducing the effects of mobility since server reelection is not invoked as long as current servers move inside their regions and hence the overhead due to mobility updates is quite manageable We run extensive detailed simulations to investigate the design space and study the architecture in various environments including node mobility and failures In addition we perform high level simulations and analysis to analyze RR scalability and evaluate it against other approaches flooding centralized storage and GHT 17 to identify its merits and limitations The results show that RR is scalable to large number of nodes and is highly efficient and robust with node mobility failures and location inaccuracy We like to emphasize that our goal from the comparison is not to say that one approach is always better but to show the strengths and limitations of different approaches and under which conditions and environments each is preferable The rest of the paper is outlined as follows In Section 2 we discuss related work In Section 3 we provide the context and assumptions under which our architecture operates Section 4 explains the design and section 5 contains the detailed evaluation of the architecture Conclusions are presented in Section 6 1 2 Related Work In wireless networks the simplest form of data dissemination or resource discovery is global flooding Flooding does not scale well Other approaches that address scalability employ hierarchical schemes based on cluster heads or landmarks 12 These architectures however require complex coordination between nodes and are susceptible to major re configuration e g adoption re election schemes due to mobility or failure of the cluster head or landmark incurring significant overhead GLS 13 provides a scalable location service by using a predefined geographic hierarchy and a predefined ordering of node identifiers to map nodes to their locations GLS is presented for locating nodes and assumes that node identifiers are known In sensor networks communication is identified as data centric based on the content of data rather than node identities A data centric routing scheme presented is directed diffusion 8 Directed diffusion uses flooding to advertise the interests from sinks to sources throughout the network We believe that our rendezvous based architecture can be integrated with directed


Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Large-Scale Wireless Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Large-Scale Wireless Networks and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?