JP4795277B2 - DATA MANAGEMENT SYSTEM, DATA SEARCH METHOD, AND DATA MANAGEMENT DEVICE - Google Patents

Description

  The present invention relates to a data management method for improving data search efficiency in a structured overlay network, and in particular to a data management method for enabling range search and nearest point search and realizing flexible data search. .

  An overlay network is a network composed of logical links formed on a physical network. Data search on the overlay network is performed by routing at the component node and following the logical link until the component node holding the data to be searched is reached.

  In an unstructured overlay network, the above routing is performed by flooding a search query for all logical links whose end points are their own nodes. In this case, since the search query is distributed to all the nodes, data can be obtained even for a complicated query. However, since a large number of search queries are sent over the network by flooding, there is a feature that when the network is enlarged, the load on the network increases due to the flood of search queries.

  On the other hand, in a structured overlay network, data retrieval can be efficiently performed by determining data holding nodes in the overlay network, forming logical links, and routing during retrieval based on consistent rules. A DHT (Distributed Hash Table) is known as a data structure used in a structured overlay network. Further, as a structural overlay network system using DHT, Chord and the like shown in Non-Patent Document 1 are known.

  DHT is a data structure in which nodes constituting an overlay network and identifiers indicating data are set as one-dimensional key values by a hash function and mapped on one dimension, and a data management node is determined based on the one-dimensional distance. It is. The main advantage of using DHT is that, by using a hash function, the key values of nodes and data are uniformly distributed in one dimension, and thus have excellent distribution characteristics.

  Chord provides a means for efficiently retrieving nodes and data located on the DHT. Data having the key value k is managed by the node having the key value at the closest position in the direction in which the key value increases from k. The node establishes a logical link between the closest node in the key space and a remote node, and determines a transfer destination logical link based on the magnitude relation of the key value at the time of data retrieval. Here, a logical link with a remote node is set to be sparse as the distance in the key space increases.

  With these mechanisms, data search can be performed with the number of hops of about log N with respect to the number N of data and nodes. In addition, flooding of search queries due to flooding seen in unstructured overlay networks can be suppressed, and a larger-scale network can be configured as compared to unstructured overlay networks. On the other hand, since data search in Chord is performed only by exact match search using an ID as a key, a flexible query search that is possible in an unstructured overlay network cannot be performed.

“Cord: A scalable peer-to-peer lookup service for Internet applications” ACM SIGCOMM (2001)

  As described above, in unstructured overlay networks, flexible query searches are possible. However, there is a problem that it is difficult to increase the scale of the network due to an increase in the load on the network due to flooding of search queries. there were. On the other hand, in the structural overlay network based on DHT represented by Chord, there is a problem that it is difficult to perform range search or nearest point search for a certain parameter.

  The present invention has been made in view of the above, and in a structured overlay network based on DHT, data enabling a range search and a nearest point search for an arbitrary parameter, particularly a parameter indicating a position (coordinate). It is an object to provide a management system, a data search method, and a data management device.

  In order to solve the above-described problems and achieve the object, the present invention provides a data management system in which a plurality of node devices constituting an overlay network manage data, and each of the node devices is itself or adjacent to each other. When data held by a node device changes, search parameters included in the changed data are mutually exchanged with adjacent node devices, and itself and each adjacent node device based on the search parameters obtained by the exchange Obtained by exchanging the search parameters with each other between the table update function for updating the search parameter table held by and the neighboring node device in which the difference between the held data is within a predetermined range. Retain search parameters that retain search parameters in association with the search parameters included in the retained data And when a data search request is received, based on the search parameters included in the data search request and the search parameter table, the necessity determination of the transfer of the data search request and the transfer destination when the transfer is required A transfer necessity determination function for specifying a node device, and a search parameter included in the data search request and the search parameter holding function when the transfer necessity determination function determines that no transfer is necessary A proximity transfer necessity determination function for determining the necessity of transfer of the data search request to the adjacent node device based on the stored search parameter.

  According to the present invention, a link is created by exchanging information with adjacent nodes on the overlay network, and a node that manages data within a certain range from a predetermined reference point is within the range. A link is created with data managed by all existing nodes. When searching for data, the search request is transferred to the transfer destination selected from the adjacent nodes on the overlay network until the vicinity of the desired data is reached. Since the search processing is executed for all nodes in the range by narrowing down to the range of, the range search and the nearest point search in the structured overlay network can be performed.

  Embodiments of a data management system according to the present invention will be described below in detail with reference to the drawings. Note that the present invention is not limited to the embodiments.

Embodiment.
First, an outline of the present invention will be described before detailed description. The data management system according to the present invention roughly divides and executes two characteristic processes. First, the first characteristic process constitutes a procedure for registering data to be searched in the overlay network. This is a process of generating management information for realizing an efficient search operation. Specifically, when registering data to be searched for in the overlay network, a link that considers the value of the parameter to be searched between the data of the overlay network and between the nodes constituting the overlay network (hereinafter referred to as geo (Referred to as a local link).

  The second characteristic process constitutes a procedure for retrieving data registered on the overlay network. This is because, when each node constituting an overlay network receives a parameter nearest point search request, the geographical points set between the data and between the nodes in response to the nearest point search request for the parameter to be searched. This is a process (geographic routing process) in which a parameter closest to a search target value is selected from links and a search request is transferred to a node having the parameter.

  The geographical link creation processing further includes proximity data measurement processing for finding a set in which the parameters to be searched are closely related from among the data registered on the overlay network, and between adjacent nodes on the overlay network. By communicating with the node, the node executes the parameter notification process for notifying the parameter to be searched included in the data managed by the mutual nodes, and the parameter notification process, and the search target parameter obtained as a result A parameter selection process for selecting an important one from among them.

  The parameter selection process is intended to prevent the number of data flowing on the network from becoming too large by executing the parameter notification process. By executing this parameter selection process, the number of geographical links is suppressed when the number of data managed by one node increases.

  In addition, in order to reach the search target data quickly in the above-described geographical routing process, the distribution of the search target parameters of the geographical links possessed by each node is important. If the distribution of the search target parameters is uniformly random, the search target data can be approached in the first stage of the geographical routing process, and the search efficiency is improved.

  Here, as a method of improving the search efficiency in the parameter selection process, for example, a method of randomly selecting a certain number is conceivable. Since the search target parameter of the geographical link obtained by executing the parameter notification process has a random distribution due to the characteristics of the overlay network, the search target parameter of the geographical link possessed by the node is also randomly determined by using this method. Can keep. As another method, a method of maximizing the variance value of the search target parameter of the geographical link possessed by the node is conceivable. When this method is used, the distribution of the search target parameters of the geographical link can be further randomized as compared with the method of selecting the certain number at random.

  Further, in the above-described geographical routing process, after reaching a node having data that can be regarded as being closest to the value to be searched, a difference from the value to be searched is detected from among the geographical links of the node. A range search (query) is transferred to all nodes that manage data having parameters within a certain range, and the transfer destination node has the same transfer processing or parameters included in the search range among the data managed by the node. It includes a range search routing process that executes a process of transmitting the data it has to the search source, and a loop prevention process that prevents the range search transferred in the range search routing process from going through the node that passed through again. .

  Next, the present invention will be described in more detail. FIG. 1 is a diagram showing a configuration example of a data management system according to the present invention. This data management system includes a radio access network 10 constituted by a plurality of access points 1 and a structured overlay network 20 constituted on the radio access network, and the radio communication terminal 2 is any one radio access point. 1 to the radio access network 10.

  Here, in the present embodiment, search target data is wireless access point information (hereinafter referred to as AP information), and search target parameters are coordinates on a map. The wireless access point means an access point in a general wireless access network system, and the method of the wireless access network system is not specified in the present invention. Each wireless access point has a unique identifier (ID), and AP information is registered on the overlay network using this as a key. That is, all AP information is managed by one of the constituent nodes based on the overlay network method. Registration of AP information is performed by an administrator of the radio access network system. The AP information includes at least coordinate information indicating the position where the wireless access point is installed. However, the means for obtaining the coordinates indicating the position is not specified in the present invention.

  Such proximity data measurement processing when the search target data is AP information and the search target parameter is a position (coordinate) on the map is such that a wireless terminal that can access the wireless access network system has predetermined position coordinates. Information notification step of notifying the overlay network via the radio access network system, with the measurement information (measurement result) as “identifiers of all wireless access points accessible at the position coordinates” obtained by searching in FIG. And a neighboring data link setting step in which the constituent node of the overlay network that has received the notification of the measurement information sets a link between the AP information corresponding to each of the notified measurement information (wireless access point identifier).

  More specifically, in the proximity data link setting step, in the above link setting process, AP information (one of the links) is AP information (one pair of AP information for setting the link). (AP information) is updated, and an identifier (ID) indicating a wireless access point and coordinate information indicating the position of the wireless access point included in the AP information (other AP information) serving as the other end of the link are added. The details of this proximity data link setting step will be described separately in detail with specific examples.

  In the above parameter notification process, each overlay network constituent node manages the logical link connection destination (adjacent node) between nodes set based on the structural overlay network method. Among the AP information, the identifier of the wireless access point and the coordinate information indicating the position are notified.

  Here, the parameter notification processing will be specifically described with reference to FIG. FIG. 2 is a diagram illustrating an example of the parameter notification process. In FIG. 2, node A and node B are constituent nodes of the overlay network, and node A and node B are adjacent to each other in the overlay network. FIG. 2 shows a state in which the parameter notification process is executed following the process of adding registration data to the overlay network.

  In the example shown in FIG. 2, the registration data is passed to the node A which is the management node of the registration data determined based on the key calculated from the ID (= abc) included in the registration data (step S11). The node A first stores and manages the received additional data (registered data) in its own storage unit or the like. Next, the node A notifies the registration data to be newly managed to all the nodes in the adjacent relationship (in this example, only the node B is a target) (step S12), and the registration data is sent to the registration data. Based on this, the retained geographical routing table is updated (step S13). Specifically, necessary parameters are selected from the parameters included in the registration data and additionally registered in the geographical routing table. The update of the geographical routing table means addition of information indicating that the node (A) manages (holds) the newly added data (registered data) to the overlay network.

  Each adjacent node (only node B in this example) that has received registration data notification from node A in step S12 updates the geographical routing table recorded therein (step S14). The update of the geographical routing table means that information indicating that data newly added to the overlay network (registered data) is managed by the node A is added.

  By executing the above series of processing, a link (geographic link) from node B to node A relating to data additionally registered in the overlay network is created.

  Next, proximity data measurement processing (particularly, proximity data link setting step) included in the geographical link creation processing will be described with reference to FIG. FIG. 3 is a diagram illustrating an example of the proximity data measurement process, and the node A, the node B, and the node C are constituent nodes of the overlay network. It does not matter whether the set of nodes is adjacent to each other in the overlay network. Node A holds management data 31 having ID = abc, and node C holds management data 32 having ID = def.

  When the wireless communication terminal is notified of the measurement result obtained by executing the search for the wireless access point (step S21), the node B detects all the data in the proximity relationship indicated by the measurement result (detected in the search process). Wireless access point data). That is, the node A holding the management data with ID = abc is requested to notify the data (step S22), and the data with ID = abc is acquired (step S23). Similarly, the node C holding management data with ID = def is requested to notify the data (step S24), and data with ID = def is acquired (step S25). Note that communication performed between nodes to acquire data can be performed using communication in a general structural overlay network by setting a key calculated from an ID as a destination.

  Then, the node B that has acquired all the data close to the measurement result adds position (coordinates) information included in the acquired data to the measurement result, and holds the acquired data. Transmit to all nodes (nodes A and C in this example) (steps S26 and S28). The node A that has received the measurement result to which the position information is added from the node B updates the management data 31 held so far (stores the received measurement result) based on the received measurement result (step S27). ), The updated management data 31a is obtained. The update means adding the proximity relationship with the management data having ID = def and the position information of the management data having ID = def to the management data 31 having ID = abc held in advance. . When three or more data are included in the measurement result, that is, when the wireless communication terminal detects three or more wireless access points, the management data in proximity to the management data held by itself is 2 More than one. Similarly, the node C that has received the data in step S28 updates the held management data 32 (step S29) to obtain the management data 32a.

  By executing the above series of processing, a mutual link between management data having ID = abc and management data having ID = def is created.

  In addition, when the wireless communication terminal is made to search for a wireless access point, a threshold for a reception level of a search signal (beacon signal) is specified, a range of IDs to be detected is specified, and an ID for which detection is prohibited (temporarily It is possible to limit the search range by specifying an ID that is not included in the detection result even if it is detected.

  Next, the geographical routing process will be described in detail with reference to FIG. FIG. 4 is a diagram illustrating an example of the geographical routing process, and the nodes A, B, and C are constituent nodes of the overlay network. In addition, node A and node B are adjacent to each other in the overlay network, and it does not matter whether the other node sets are adjacent. FIGS. 5A, 5B, and 5C are diagrams illustrating examples of the geographical routing tables held by the nodes A, B, and C illustrated in FIG.

  In the example shown in FIG. 4, as shown in the geographical routing table of the node A in FIG. 5A, the node A holds management data 31a having ID = abc. Further, as shown in the geographic routing table of the node B in FIG. 5B, a geographic link from the node B to the node A is created for the management data having ID = abc. This geographical link is created by executing the parameter notification process described above. Further, as shown in the geographical routing table of the node C in FIG. 5C, the node C holds management data 32a having ID = def.

  Furthermore, as shown by the management data 31a having ID = abc held by the node A and the management data 32a having ID = def held by the node C, the management data 31a having ID = abc and ID = def A link (neighbor =... (X =..., Y =...)) Indicating a proximity relationship is created between the management data 32a having This link is created by executing the proximity data measurement process described above.

  For example, when the node B receives a nearest point search request from a subordinate wireless communication terminal or another node (nodes other than the nodes A and C) (step S31), the node B holds the geographical routing that it holds. Referring to the table (FIG. 5-2), the entry closest to the search target point (X = 152, Y = 220) is examined. Then, the closest point search request is transferred to the data indicated by the entry obtained as a result of the scrutiny, in this example, the management data having ID = abc (step S32). The transfer is performed using communication in a general structured overlay network with the key calculated from the ID as the destination. As a result, the nearest point search request reaches the node A. Since the entry can also be held by the peer, it can be transmitted directly to the node A without using communication in a general structured overlay network.

  The node A that has received the transferred nearest point search request refers to the stored geographic routing table (FIG. 5A) and examines the entry closest to the point to be searched. Since the entry obtained as a result indicates the management data 31a having ID = abc, the node A refers to the management data 31a. If an entry closer to the search target point than the management data 31a exists in the geographical routing table, the closest point search request is transferred to data indicated by the entry closest to the search target point.

  Next, the node A selects the search target from the position (coordinate) information (X = 100, Y = 200) of the management data 31a and the position information (x = 150, y = 230) of the data in proximity relation. Scrutinize the data closest to the point. Note that there may be a plurality of pieces of positional information of data in proximity relations. Then, the node A transfers the closest point search request to the data obtained as a result of the scrutiny (step S33). In this example, the closest point search request is transferred to the management data 32a having ID = def. Note that the transfer is performed using communication in a general structured overlay network with the key calculated from the ID as the destination. As a result, the nearest point search request reaches the node C.

  The node C that has received the transferred nearest point search request refers to the stored geographic routing table (FIG. 5C) and examines the entry closest to the point to be searched. Since the entry obtained as a result shows the management data 32a that owns ID = def, the node C refers to the management data 32a.

  Next, the node C selects from the position information (x = 100, y = 200) of the management data 32a (X = 150, Y = 230) and the position information (x = 100, y = 200) of the proximity data recorded in the data. Scrutinize the data closest to the point being searched. Data obtained as a result, in this example, management data 32a having ID = def is data managed by node C itself.

  Therefore, the node C determines that the management data 32a having ID = def is a solution for the closest point search, and sets the search result as data (management data 32a) with ID = def to the transmission source of the closest point search. The search result is notified (step S34).

  By executing the series of processes as described above, the result of the closest point search is obtained.

  Here, handling of measurement data in the wireless access point search system will be described. The measurement data has an expiration date, and the proximity relationship based on the measurement data whose expiration date has expired is deleted (information indicating the proximity relationship is deleted). By doing in this way, even if it is a system which a terminal transmits measurement data regularly, it can prevent that measurement data becomes a huge number. In addition, even when the radio wave environment at a certain point changes and the proximity relationship between access points changes, it is possible to prevent information indicating an erroneous proximity relationship before the change from remaining in the system for a long period of time. More specifically, when a node adds information indicating a proximity relationship to data, a timer is set, and when the timer expires, the proximity relationship is deleted. Can be prevented. The validity period information may be included in the information indicating the proximity relationship, and the validity period may be individually set for each data. Depending on the situation, for example, if the radio wave environment is not good or the radio wave environment is likely to change, set the effective period short, while if the radio wave environment is stable, set the effective period long. The effective period can be changed.

  Further, when the first measurement data indicating a certain proximity relationship is notified to the system and the proximity relationship between the data is created, and then the second measurement data indicating the proximity relationship is notified to the system, the proximity relationship is Only the timer is updated without creating (without executing the proximity data measurement process for creating the proximity relationship). This can also prevent the measurement data from becoming an enormous number.

  A method of developing the wireless access point search system will be described. In this method, data managed by the system is not limited to access point information, and measurement data is also targeted. In this case, after the measurement data is notified to the system, the measurement data is registered as data in the overlay network. Then, an inter-data link is also created between the access point information indicated by the measurement data and the data of the measurement data itself. Thereafter, the measurement data is also used as a data having position information at the time of searching in the same manner as the access point information. The Rukoto.

  Thus, in this embodiment, a node is created by exchanging information with adjacent nodes on the overlay network, and a node that manages data within a certain range from a predetermined reference point is A link is created between the data managed by all the nodes existing in the range. When searching for data, the search request is transferred to the transfer destination selected from the adjacent nodes on the overlay network until the vicinity of the desired data is reached. The search processing is executed for all nodes in the range by narrowing down to the range of. Thereby, range search and nearest point search are possible.

  According to the above-described wireless access point search system, it is possible to search for an access point closest to an arbitrary position. Also, by applying this system, it is possible to search for an access point to be connected using the position of the mobile terminal and the movement prediction.

  Further, according to the above-described advanced method, not only the access point information but also the measurement information is a search target, so that a radio wave environment at a point closer to the search target point can be acquired.

  More generally, the nearest point search and the range search can be performed for parameters other than position information by link construction based on proximity measurement according to the present invention and routing based on the constructed link.

  As described above, the data management system according to the present invention is useful for data management in an overlay network, and is particularly suitable for managing information on wireless access points constituting a wireless access network.

It is a figure which shows the structural example of the data management system concerning this invention. It is a figure which shows an example of a parameter notification process. It is a figure which shows an example of a proximity data measurement process. It is a figure which shows an example of a geographic routing process. It is a figure which shows an example of the geographical routing table which the node A hold | maintains. It is a figure which shows an example of the geographical routing table which a node B hold | maintains. It is a figure which shows an example of the geographical routing table which the node C hold | maintains.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Wireless access point 2 Wireless communication terminal 10 Wireless access network 20 Structural overlay network 31, 31a, 32, 32a Management data

Claims (4)

A data management system in which a plurality of node devices constituting an overlay network manage data,
The data to be managed is access point information including the identifier and location information of each access point constituting the radio access network.
Each of the node devices is respectively
If the access point information themselves managed is changed, notifies the change to the access point information to adjacent nodes apparatus, the data search request adjacent when the node device receives a data retrieval request A table update function that updates the geographic routing table used in the process of determining whether or not to transfer to a node device ,
When managing access point information of an access point detected as an access point connectable by access point search in a wireless communication terminal, access point information of another access point detected by the access point search, A management data update function for acquiring the access point identifier and location information contained in the acquired access point information from other node devices and adding the access point information managed by the own device;
When a data search request is received, based on the location information included in the data search request and the geographical routing table, the necessity of transferring the data search request to the adjacent node device and the transfer are necessary A first transfer necessity determination function for performing the identification of the transfer destination adjacent node device,
If it is determined that there is no need of transfer in the first transfer necessity determining function, based on the position information and management to have access point information included in the data retrieval request, transfers of the data search request A second transfer necessity judgment function for judging the necessity;
A data management system comprising: The management data update function sets and holds an expiration date in the identifier and location information of the access point acquired from another node device, and when the expiration date has passed, the identifier and location of the access point The data management system according to claim 1, wherein the information is deleted from the access point information . A plurality of node devices constituting the overlay network, a Contact Keru data search method in a data management system for managing access point information including an identifier and position information of each access point constituting the radio access network,
As a process for each node device to update information used for data search ,
If the access point information managed by itself is changed, notifies the change to the access point information to adjacent nodes device and the node device adjacent the data retrieval request when receiving the data retrieval request A table update step for updating the geographical routing table used in the process of determining whether or not to transfer to a certain node device;
When managing access point information of an access point detected as an access point connectable by access point search in a wireless communication terminal, access point information of another access point detected by the access point search, A management data update step for adding the identifier and location information of the access point acquired from another node device and included in the acquired access point information to the access point information managed by the own device;
Including
Said node device, a process to be executed when receiving a data search request,
Based on the position information and the geographic routing table included in the data retrieval request, certain of the data retrieval and necessity determination of the transfer to the adjacent node device requests the transfer destination adjacent node apparatus when the transfer is necessary And a first transfer necessity determination step for performing
If it is determined that there is no need of transfer in the first transfer necessity determination step, on the basis of the positional information and management to have access point information included in the data retrieval request, transfers of the data search request A second transfer necessity determination step for determining the necessity;
A data search method comprising: A data management apparatus that implements the data search method according to claim 3 .

Images