Alternative Title地理位置情報に基づく分散ルーティングテーブルを用いた情報検索システム
Note (General)In this thesis, we propose an information look up system using geographic location-based distributed routing (GDR) table that collects and manages information gathered by moving vehicles in urban areas. Throughout this thesis, weassume the underlay network of the GDR system can be modeled as a grid. This assumption makes a sense for an urban area where the roads are paved on a grid pattern. The system uses area nodes placed on several locations where each node manages location-oriented information on a designated non-overlapping area. The GDR system provides an information lookup based on the geographic latitude and longitude coordinates. A geographic coordinate is assigned for a node as its identifier (ID), and each node manages an overlay routing table. The routing table consists of pointers to other nodes in the network in order to forward messages to the geographically nearest overlay node toward its final destination. In a system with N nodes, each node has a routing table of size log N and a search is possiblein O(log N). We evaluate the mean and the variance of the path length and the relay length of GDR, CAN, Chord and Kademlia, under the assumptions that the ID is in cartesian format (x, y), all nodes are active, and the source node and the destination node are chosen independently with equal probability. We show that regardless of the ID format (i.e. even though the ID is in cartesian format or the ID is generated by using Space Filling Curve (SFC)), GDR, Chord and Kademlia have the same mean and the same variance of the path length,while the mean and the variance of the relay length of GDR are smaller than those of Chord and Kademlia. Furthermore, while GDR and CAN have the same mean and the same variance of the relay length, the mean and the variance of the pathlength of GDR are smaller than those of CAN.We show that the mean relay length of GDR is about half of that of Chord, and about 2/3 of that of Kademlia, and the mean path length is about (3/4) log N/√N of that of CAN. In addition, the GDR system has a routing redundancy to increase robustness. When a node fails, its neighbor node behaves as an agent for the failing node. To know the agent node of the failing node, each node has an agent list which is the records of the agent nodes of the nodes of its routing table. Since the number of the agent nodes is 2, the size of the agent list is 2 log N. If an underlay network can be modeled as a grid, it is easy to assign a physical address for a node. However, if a node fails, it is difficult to modify or change its physical address. In the GDR system, the nodes can avoid a failed node by using its agent list on the overlay network. We also present an application of the GDR system. In order to send a reply to a terminal after it moves to the neighboring area, we proposed Wall Pass (WP) algorithm. We consider a node as a wall player of wall pass in football. We evaluated the performance of the GDR system when the mobile mobile terminals are moving. The results show that WP algorithm can decrease the communication overhead.
開始ページ : 1
終了ページ : 112
Collection (particular)国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文
Date Accepted (W3CDTF)2016-07-07T04:28:02+09:00
Data Provider (Database)国立国会図書館 : 国立国会図書館デジタルコレクション