Location Based Service
Advances in mobile hardware and the increasing sophistication of handheld software have made many devices location-aware. Existing location-based services are limited to specialized niche markets such as geographical information systems (GISs), they are typically constrained to a fixed set of moving objects and expensive to maintain and expand. This is in large part because the first generation of GIS systems and applications provide little or no system support for serving a large and growing number of mobile users and providing continuous delivery and dissemination of location-based information in real time. Offering system support for location based service fundamentally expands the service range and guarantees the service quality. In particular coupling many individual location aware components to provide cooperative location service greatly improves the resource sharing and significantly releases the power of location-awareness. One typical location service example, As a typical location service example, a tourist arriving a new place may eagerly demand services which is associated with his or her location and thus may posts location based request like " where are the restaurants 5 miles around downtown" or "what is the traffic conditions in downtown area".
What is GeoGrid
As the cost of the mobile devices and its accessories continue to decrease, there is a growing demand for high performance location based service architecture, aiming at providing scalable and reliable location based information delivery in large scale pervasive computing environments. In contrast to centralized client-server architecture, decentralized management and provision of location based services have gained lot of attentions in the recent years due to its low cost in ownership management and its inherent scalability and selfconfigurability.
GeoGrid is a decentralized location service overlay network system proposed by DiSL group in Georgia Institute of Technology. It provides scalable location-based services to a large and growing number of mobile users. GeoGrid is designed as a decentralized and geographical location aware overlay network and provides system-level facilities and optimizations for balancing load in the presence of node heterogeneity, dynamically moving hot-spots (location queries), and unpredictable rate of node join, departure and failure. GeoGrid uses geographical mapping of nodes to regions and geographical proximity based routing to take advantage of the similarity between physical and network proximity. Furthermore, GeoGrid exploits multiple opportunities for dynamic workload adaptation in the presence of static hotspot queries and moving hotspot queries. Its dynamic load balancing algorithms can efficiently utilize the heterogeneous capacities of end systems and balance both the location query workload and the routing workload.
Reliability is critical to guarantee the service performance for systems operating in a totally decentralized environment and participating nodes present high dynamics. GeoGrid is equipped with a specially designed distributed replication scheme, aiming at providing scalable and reliable processing of location service requests in decentralized pervasive computing environments. The replica management operates on a network of heterogeneous nodes and utilizes a shortcut-based optimization to increase the resilience of the system against node failures and network failures. In addition to the fault tolerance, we also designed a dynamic load balancing technique that exploits the service processing capabilities of replicas to scale the system in anticipation of unexpected workload changes and node failures by taking into account of node heterogeneity, network proximity, and changing workload at each node.
GeoGrid Architecture
GeoGrid consists of a network of nodes interconnected through the GeoGrid topology and routing protocol. All nodes are represented as points in a two dimensional geographical coordinate space, which bears a one-to-one mapping to the physical coordinate system. Similar to CAN system, at any point in time, the network of N nodes will dynamically partition the entire GeoGrid coordinate space into N disjoint rectangles such that each node "owns" rectangular region. For example, Figure 1 shows a two dimensional geographical coordinate space partitioned among 15 GeoGrid nodes. Nodes in GeoGrid self-organize into an overlay network. A node establishes its overlay connectivity with other nodes through its immediate neighbors. A mobile user may use the GeoGrid service network by connecting her mobile devices to one of the nodes in the network, usually through wireless or wired network connection. Each node runs the GeoGrid middleware and serves as the proxy for the mobile users. Depending on the applications implemented over the GeoGrid middleware, a proxy can submit queries, process data, cache query results, and send event notifications on behave of mobile users. A proxy can be a personal computer or a server at the edge of the Internet.
Reliability
To ensure the reliable location service request processing in an environment of heterogeneous nodes with continuously changing workloads. GeoGrid replication framework provides failure resilience to both individual node failures and massive node failures, aiming at keeping the service consistently accessible to users and eliminating the sudden interruption of the ongoing tasks. Further with the replicas, we devise a dynamic replica-based load balancing technique, which utilizes a parameterized utility function to control and scale the system in the presence of varying workload changes by taking into account of several workload relevant factors. The experimental results verifies that reliable GeoGrid architecture is highly scalable under changing workloads and moving hotspots, and highly reliable in the presence of both individual node failures and massive node failures.
