1 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 re-election 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.2 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