《网络通信专业资料：a scalable location service for geographic ad hoc routing》由会员分享，可在线阅读，更多相关《网络通信专业资料：a scalable location service for geographic ad hoc routing（30页珍藏版）》请在金锄头文库上搜索。
1、Proc. of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM 2000), Boston MA, pp. 120130, August 2000. A Scalable Location Service for Geographic Ad Hoc Routing Jinyang Li, John Jannotti, Douglas S. J. De Couto, David R. Karger and Robert Morris ? MIT Laboratory for
2、Computer Science jinyang, jj, decouto, karger, rtmlcs.mit.edu Abstract. GLS is a new distributed location service which tracks mobile node locations. GLS combined with geographic forwarding allows the construction of ad hoc mobile networks that scale to a larger number of nodes than possible with pr
3、e- vious work. GLS is decentralized and runs on the mobile nodes themselves, requiring no fi xed infrastructure. Each mobile node periodically updates a small set of other nodes (its location servers) with its current location. A node sends its position updates to its location servers without knowin
4、g their actual identities, assisted by a predefi ned ordering of node identifi ers and a predefi ned geographic hierarchy. Queries for a mobile nodes location also use the predefi ned identifi er ordering and spatial hierarchy to fi nd a location server for that node. Experiments using the ns simula
5、tor for up to 600 mobile nodes show that the storage and bandwidth requirements of GLS grow slowly with the size of the network. Furthermore, GLS tolerates node failures well: each failure has only a limited eff ect and query performance degrades gracefully as nodes fail and restart. The query perfo
6、rmance of GLS is also relatively insen- sitive to node speeds. Simple geographic forwarding combined with GLS compares favorably with Dynamic Source Routing (DSR): in larger networks (over 200 nodes) our approach de- livers more packets, but consumes fewer network resources. ? Jinyang Li and John Ja
7、nnotti are supported by DARPA contract N66001- 99-2-8917. David Karger is supported by NSF contract CCR-9624239, an Alfred P. Sloane Foundation Fellowship, and a David and Lucille Packard Foundations Fellowship. 46Jinyang Li, John Jannotti, et al. 1Introduction This paper considers the problem of ro
8、uting in large ad hoc networks of mobile hosts. Such networks are of interest because they do not require any prior investment in fi xed infrastructure. Instead, the network nodes agree to relay each others packets toward their ultimate destinations, and the nodes automatically form their own cooper
9、ative infrastructure. We describe a system, Grid, that combines a cooperative infrastructure with location information to implement routing in a large ad hoc net- work. We analyze Grids location service (GLS), show that it is correct and effi cient, and present simulation results supporting our anal
10、ysis. It is possible to construct large networks of fi xed nodes today. Prominent examples include the telephone system and the Internet. The cellular telephone network shows how these wired networks can be extended to include large numbers of mobile nodes. However, these net- works require a large
11、up-front investment in fi xed infrastructure before they are usefulcentral offi ces, trunks, and local loops in the case of the telephone system, radio towers for the cellular network. Furthermore, upgrading these networks to meet increasing bandwidth requirements has proven expensive and slow. The
12、fact that large fi xed communication infrastructures already ex- ist might seem to limit the usefulness of any competing approach. There are, however, a number of situations in which ad hoc networks are de- sirable. Users may be so sparse or dense that the appropriate level of fi xed infrastructure
13、is not an economical investment. Sometimes fi xed infrastructure exists but cannot be relied upon, such as during disaster recovery. Finally, existing services may not provide adequate service, or may be too expensive. Though ad hoc networks are attractive, they are more diffi cult to implement than
14、 fi xed networks. Fixed networks take advantage of their static nature in two ways. First, they proactively distribute network topology information among the nodes, and each node pre-computes routes through that topology using relatively inexpensive algorithms. Second, fi xed networks embed routing
15、hints in node addresses because the complete topology of a large network is too unwieldy to process or distribute globally. Neither of these techniques works well for networks with mobile nodes because movement invalidates topology information and permanent node addresses cannot include dynamic loca
16、tion infor- mation. However, there is a topological assumption that works well for radio-based ad hoc networks: nodes that are physically close are likely to be close in the network topology; that is, they will be connected by a small number of radio hops. A Scalable Location Service for Geographic Ad Hoc Routing47 Grid uses geographical forwarding to take advantage of the similar- ity between physical and network proximity. A source must know the geographical positions of any destinatio
