王勝德臺灣大學：電機工程學研究所王皓漢Wang, Hau-HanHau-HanWang2007-11-262018-07-062007-11-262018-07-062006http://ntur.lib.ntu.edu.tw//handle/246246/53189Position-based routing has been proven to be a scalable and efficient solution for packet routing in mobile ad hoc networks (MANETs) by utilizing location information of mobile nodes. The location service provides geographic locations for all nodes and is therefore critical to position-based routing. In general, the control overhead in a position-based routing protocol is mainly dominated by location updates. In this paper, we propose a location service called Modified Grid Location Service (MGLS), which employs an enhanced grid partitioning scheme to reduce the control overhead associated with the location management and supports large scale ad hoc networks. We then use a theoretical model to analyze both MGLS and GLS, in terms of three scalable metrics: the location maintenance cost, the location query cost, and storage requirement. Both theoretical analysis and simulation results confirm that MGLS supports the superior scalability.Contents 1 Introduction - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1 1.1 Topology-Based Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1.2 Position-Based Routing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 1.2.1 Location Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Forwarding Strategy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Other Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 6 2 Overview of MGLS Scheme - - - - - - - - - - - - - - - - - - - - - - - - - - 8 2.1 Grid Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Location Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 Selecting Location Servers and Updating Location Information . . . . . . 10 2.2.2 Location Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Design Tradeoffs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Comparisons Based On Theoretical Model - - - - - - - - - - - - - - - - 15 3.1 Metrics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Model Assumptions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 MGLS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.1 Location Maintenance Cost. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.2 Location Query Cost. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.3 Storage Requirement Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4 GLS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 22 3.5 Summary of Theoretical Analyses . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Performance Analyses - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 25 4.1 Simulation Setup. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.1.1 Global Settings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.1.2 Protocol Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.1.3 Performance Metrics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2.1 Protocol Overhead. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2.2 Protocol Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2.3 Dual Server Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5 Conclusion and Future Works - - - - - - - - - - - - - - - - - - - - - - - - 33en-US行動隨意網路位址服務移動模型位址繞送Mobile ad hoc networksscalable routinglocation servicemobility modelposition(location)-based routingthesis