TY - GEN
T1 - Enhancing location service scalability with HIGH-GRADE
AU - Yu, Yinzhe
AU - Lu, Guor Huar
AU - Zhang, Zhi-Li
PY - 2004
Y1 - 2004
N2 - Location-based routing significantly reduces routing overheads in mobile ad hoc networks (MANETs) by utilizing position information of mobile nodes in forwarding decisions. Location service is therefore critical to location-based routing, the scalability of which hinges largely on the overheads of such service. Although several location service schemes have been proposed, most of them focus only on one or two aspects of the scalability in their performance evaluations, and a comprehensive comparative study is missing. In this paper, we first explore the design space of location services and present a taxonomy of existing schemes. We then propose HIGH-GRADE, a new location service scheme that employs a multilevel hierarchical location server structure and a multi-grained location information organization. We develop a uniform theoretical framework to analyze HIGH-GRADE and four other existing schemes in terms of three metrics: location maintenance cost, location query cost, and storage requirement cost. We show that the design of a location service scheme involves tradeoffs among all the three kind of overheads. Further, in our theoretical analysis and simulation experiments, HIGH-GRADE demonstrates superior scalability, especially when a localized data traffic pattern is assumed.
AB - Location-based routing significantly reduces routing overheads in mobile ad hoc networks (MANETs) by utilizing position information of mobile nodes in forwarding decisions. Location service is therefore critical to location-based routing, the scalability of which hinges largely on the overheads of such service. Although several location service schemes have been proposed, most of them focus only on one or two aspects of the scalability in their performance evaluations, and a comprehensive comparative study is missing. In this paper, we first explore the design space of location services and present a taxonomy of existing schemes. We then propose HIGH-GRADE, a new location service scheme that employs a multilevel hierarchical location server structure and a multi-grained location information organization. We develop a uniform theoretical framework to analyze HIGH-GRADE and four other existing schemes in terms of three metrics: location maintenance cost, location query cost, and storage requirement cost. We show that the design of a location service scheme involves tradeoffs among all the three kind of overheads. Further, in our theoretical analysis and simulation experiments, HIGH-GRADE demonstrates superior scalability, especially when a localized data traffic pattern is assumed.
UR - http://www.scopus.com/inward/record.url?scp=20344399390&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=20344399390&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:20344399390
SN - 0780388151
SN - 9780780388154
T3 - 2004 IEEE International Conference on Mobile Ad-Hoc and Sensor Systems
SP - 164
EP - 173
BT - 2004 IEEE International Conference on Mobile Ad-Hoc and Sensor Systems
T2 - 2004 IEEE International Conference on Mobile Ad-Hoc and Sensor Systems
Y2 - 25 October 2004 through 27 October 2004
ER -