KR100801246B1 - Electronic tag location information management system and method - Google Patents

Abstract

The present invention is to manage the location of the electronic tag to give the reader proximity between readers so that when the location information of the electronic tag is stored in the storage by using the ID of the reader that can recognize the electronic tag close to the location information A system and method, comprising: a location tracking application for making a query to search for location information obtained through an ID of a reader obtaining information from tags; collecting location information according to filtering and collection conditions registered by the location tracking application; And a location information management unit for storing the transmitted location information and searching for information matching the query condition of the location tracking application.

Description

System and method for managing of tag locations

1 is a block diagram of an electronic tag location information management system according to an embodiment of the present invention

2 is a detailed configuration diagram of an information management unit of the electronic tag location information management system;

3A and 3B are diagrams illustrating the interrelationships between a physical leader, a logical leader, and a logical space generated by a spatial topology between readers according to an embodiment of the present invention.

4 illustrates an input / output reader, a reader including an input / output logical space, and a logical space configuration according to an embodiment of the present invention.

5 is a diagram illustrating a shortest leader movement path of an electronic tag according to an embodiment of the present invention.

6A and 6B are flow diagrams for a reader proximity grant element and method between readers in accordance with one embodiment of the present invention.

7 is a diagram illustrating a weight graph configuration using a reader proximity as a weight value and using a leader as a node according to an embodiment of the present invention.

8 is a flowchart illustrating a method of ordering leader IDs in one dimension by a graph traversal method according to an embodiment of the present invention.

9 is a flowchart illustrating a method of applying to a 3D location tracking index for storing electronic tag location information using an ordered reader ID according to an embodiment of the present invention.

FIG. 10 is a block diagram illustrating a reader ID dynamic reconfiguration method using Kalman filtering to reflect reader proximity changed over time according to an embodiment of the present invention.

<Description of the symbols for the main parts of the drawings>

100 ... Electronic Tag Location Information Management System

110 ... electronic tag 120 ... reader

130 ... location information collection section 140 ... location information management section

141 ... Location query module 142 ... Location index module

143 ... Location store 150 ... Location tracking application

160 ... Network

The present invention relates to electronic tag location information management for real-time electronic tag location tracking, and in particular, when storing the location information of the electronic tag in the storage by using the ID of the reader that can recognize the electronic tag, the proximity of the location information is closely located. The present invention relates to an electronic tag location information management system and method for providing proximity between readers.

With the rapid development of information and communication technology, efforts are being made to create a so-called ubiquitous environment in which information and communication devices can be applied to real life naturally and conveniently regardless of place or time. In order to create such a ubiquitous environment, wireless recognition technology capable of effectively detecting and recognizing each other remotely between information communication devices is essential.

At present, a representative radio recognition technology is attracting attention as a radio frequency identification (RFID) technology. RFID is a field of automatic recognition such as barcode, magnetic sensor, IC-CARD, etc., and is a state-of-the-art technology for wirelessly recognizing data stored in a microchip using microwave or long wave.

RFID is increasingly used in the industry to be recognized as a technology to replace bar codes currently used in logistics, distribution and financial services. In addition, RFID does not require a separate process of directly contacting the reader to the microchip or scanning with the reader at a visible distance to obtain data stored in the microchip, and has the advantage of transmitting a large amount of data.

RFID (Radio Frequency Identification) is a technology that automatically recognizes an article equipped with an electronic tag when it enters the reader's recognition area by using radio frequency and reads information about the article. Are used in a variety of applications such as automated production, inventory management, and supply chain management.

In recent years, tracking the location of electronic tags has become an important issue, and it is possible to build a system that can track the entire process of production, distribution, storage, and consumption using RFID technology.

For example, an application that tracks the distribution path from the place of origin to the consumer for all related items when a recall occurs because of problems with imported agricultural or livestock products already in circulation, In the application of inventory identification, it can be processed by attaching an electronic tag to a product and retrieving the current position and past history information of the electronic tag.

EPCglobal is actively promoting standardization of RFID technology, and in particular, provides a standard for electronic product code information service (EPCIS) middleware that can permanently store collected electronic tags.

In addition to the static attribute information of the product, EPCIS stores the location information of the electronic tag that changes over time, so that the location of the product with the electronic tag can be tracked.

In addition, EPCglobal stores the location information in the existing RDBMS (Relational Database Management System) using the ID of the reader that recognizes the electronic tag in order to express the location information of the electronic tag. I'm using the method.

Queries that can track the location of electronic tags are classified into Temporal Tag Query and Temporal Reader Query. The electronic tag based time query retrieves electronic tag location information expressed as a set of reader IDs passed by the electronic tag, and the reader based time query retrieves a set of electronic tags recognized by the reader in a specific time domain.

In order to efficiently process the location query, the information that is likely to be accessed at the time of query should be stored close to the storage. In the existing spatial database and mobile database, in order to arrange the information that is most likely to be accessed at the time of query closely, it is based on spatial proximity and spatial topology to obtain a result set with only a small number of searches. .

In the electronic tag location tracking system, the location information is represented as the reader ID, so there is a problem in placing the location information closely using the spatial proximity and the spatial phase relationship used in the existing research.

In addition, since the front and rear position information for the specific position information is not a spatially adjacent position as the movement characteristic of the article attached the electronic tag, a new proximity according to the movement characteristic of the electronic tag should be defined. Does not consider the movement characteristics of such an electronic tag.

The present invention is to solve the problem of the conventional electronic tag tracking system of the prior art, when the location information of the electronic tag is stored in the storage by using the ID of the reader that can recognize the electronic tag close to close to the location information The purpose of the present invention is to provide an electronic tag location information management system capable of providing proximity between readers.

The present invention is to locate the location of the electronic tag so that the location of the electronic tag that is likely to be approached together when the query is executed in order to efficiently process the location tracking query in the electronic tag location information management system for electronic tag location tracking It is an object of the present invention to provide an electronic tag location information management system and method for applying a leader ID representing information to a storage structure for accessing a location tracking query by ordering proximity.

Another object of the present invention is to reflect the more accurate proximity value by reflecting the proximity value that was calculated in the past when calculating the current proximity value when the order of the leader ID is changed by changing the proximity value between the reader over time changes An object of the present invention is to provide an electronic tag location information management system capable of dynamically changing the layout of electronic tag location information by reordering leader IDs.

Electronic tag location information management system according to the present invention for achieving the above object is a location tracking application for making a query for searching for location information obtained through the ID of the reader to obtain information from the tags; And a location information collection unit for collecting and transmitting location information according to the registered filtering and collection conditions; a location information management unit for storing the transmitted location information and searching for information matching the query condition of the location tracking application. It features.

Here, the location information management unit, a location information storage for storing the location information of the electronic tag collected through the location information collection unit, the location information stored in the location information storage and the location information of the collected electronic tag in the location information storage application A location information index module for searching for and transmitting the result, and transmitting the location information of the collected electronic tags to the location information index module, sending a query of the location tracking application to the location information index module, and transmitting the search result to the location tracking application. It characterized in that it comprises a location information query processing module.

And the location information index module is configured to provide proximity between readers in order to provide proximity between electronic tag location information collected by the location information collection unit; to store and store electronic tag location information close to the location information store. And a part of ordering the leader IDs; and a part of dynamically reordering the leader IDs by calculating a current proximity value by reflecting a past proximity value between readers that change over time.

An electronic tag location information management system according to the present invention for achieving another object is a system for managing electronic tag location information using information from a plurality of tags, the ID of the reader to obtain information from the tags Location tracking application for making a query for searching the location information obtained through; Location information collection unit for collecting and transmitting location information according to the filtering and collection conditions registered in the location tracking application; Electronic tag location collected by the location information collection unit A part that provides proximity between readers to give proximity between information, A part that orders reader ID to place and store electronic tag location information close to the location information storage, and the past between readers changed over time Current proximity value reflecting proximity value And a location information index module having a part for calculating and dynamically reordering leader IDs, and including a location information management unit for storing the transmitted location information and retrieving information meeting a query condition of the location tracking application. It is characterized by.

According to another aspect of the present invention, there is provided a method for managing electronic tag location information, the method comprising: defining a logical space using phase information between readers to manage electronic tag location information; an amount of movement of a logical space and a tag, and a location tracking query Computing reader proximity between readers using the frequency; Comprising a weight graph with a leader as a node based on the logical space proximity; Ordering the weighted graph nodes in one dimension to store the electronic tag position information Sorting IDs; applying to a three-dimensional location indexing method for storing electronic tag location information using an ordered reader ID; a current reader proximity value to reflect a reader proximity value that changes over time Dynamically reorder leader IDs to reflect past leader proximity values in calculations It characterized in that it comprises a.

Electronic tag location information management method according to the present invention for achieving another object calculates a value proportional to the proximity of the reader to the frequency of the reader-based time query issued to the logical space including the two readers of the total query issued by the location tracking application Comprising: a first step of calculating a value inversely proportional to the proximity of the reader to the shortest leader movement path distance between the two readers; including the electronic tag position information of the two readers as the location information of the entire query as a result set Calculating a value proportional to the proximity of the reader by the frequency of the electronic tag-based time query; calculating a value proportional to the proximity of the reader by the ratio of the movement amount of the electronic tag moving between two readers among the collected location information of the electronic tag And a fourth step of providing the reader proximity between the readers.

Electronic tag location information management method according to the present invention for achieving another object in order to order the leader ID using the calculated reader proximity value and apply it as a location tracking index, the reader proximity value between the reader as a node Constructing a weight graph using a weight value; ordering nodes of the weight graph for use in arranging leader IDs of the leader ID domain; ordered leader IDs and positions using the collected electronic tag position information using a mapping table Inserting the electronic tag location information by connecting the reader ID in the reader ID domain of the information index module.

Hereinafter, a preferred embodiment of the electronic tag location information management system and method according to the present invention will be described in detail.

Features and advantages of the electronic tag location information management system and method according to the present invention will become apparent from the following detailed description of each embodiment.

1 is a configuration diagram of an electronic tag location information management system according to an embodiment of the present invention, Figure 2 is a detailed configuration diagram of an information management unit of the electronic tag location information management system.

The configuration of the electronic tag location information management system 100 according to the present invention is as shown in Figure 1, a plurality of electronic tags 110, a plurality of readers 120, location information collection unit 130, location information management unit 140 ), A plurality of location tracking applications 150.

The plurality of electronic tags 110 are attached to the article so that the reader 120 has a small IC chip and antenna for identifying the electronic tag 110 by using the radio frequency, so that the RFID code and related information of the attached article are stored. Stored.

Here, the related information of the article may include a manufacturer, a product type, a product serial number, options, and other information, but is not limited thereto.

In addition, the plurality of readers 120 are provided at a designated location, obtain relevant information of the article from the plurality of electronic tags 110 through radio frequency, and filter and transmit only the information requested by the location information collection unit 130.

In addition, the location information collecting unit 130 may register the location information of the item among the information collected from the plurality of readers 120 according to the filtering and collection conditions registered by the location information managing unit 140 and the location tracking application 150. Collect it and send it.

The location information of the item is expressed using the ID of the reader 120 that obtained the information of the electronic tag 110, the ID of the recognized electronic tag 110, and the recognized time.

The location information manager 140 stores the location information of the electronic tag 110 collected and transmitted by the location information collector 130, and searches for and transmits information corresponding to a query condition required by the location tracking application 150.

The plurality of location tracking applications 150 query the location information manager 140 and the location information collector 130 to search the location information of the electronic tag 110 acquired through the reader ID.

The location information retrieved by the location tracking application 150 is the current location information of the item recognized by the specific reader 120 at a specific time, or the trajectory history information of the item represented by the ID of the reader at which the specific item has passed a specific time. .

The network 160 is a network in which the location information collecting unit 130, the location information managing unit 140, and the location tracking application 150 are commonly connected to each other to exchange data with each other, and include a wired / wireless communication network. to be.

The detailed configuration of the location information management unit 140 of the electronic tag location information management system according to the present invention is as follows.

Location information management unit 140 according to a preferred embodiment of the present invention, as shown in Figure 2, includes a location information storage 143, a location information index module 142, a location information query processing module 141.

First, the location information storage unit 143 for storing the location information of the electronic tag 110 collected through the location information collection unit 130, and the location information collection unit based on the reader ID, the electronic tag ID, and time. The location information index module 142 for storing the location information of the electronic tag 110 collected in the 130 in the location information storage 143, and quickly retrieves and transmits the information required by the location tracking application 150 in the storage; In order to store the electronic tag location information collected by the location information collecting unit 130 in the location information storage unit 143, information is transferred to the location information index module 142 and information requested by the location tracking application 150 is stored. It is configured to include a location information query processing module 141 for giving a query to the location information index module 142 to transmit the search results to the location tracking application 150.

In this case, the proximity ID is changed by changing the reader ID order of the location information index module 142 through the proximity of the reader using the reader ID ordering method proposed in the present invention to quickly transmit the search result to the location tracking application 150. Position information is stored close to the location information storage 143.

In the following, the correlation between the physical leader, the logical leader, and the logical space generated by the spatial phase between the readers will be described.

3A and 3B are diagrams illustrating the interrelationships between a physical leader, a logical leader, and a logical space generated by a spatial topology between readers according to an embodiment of the present invention.

4 is a diagram illustrating an input / output reader, a reader including an input / output logical space, and a logical space configuration according to an embodiment of the present invention, and FIG. 5 illustrates a shortest reader movement path of an electronic tag according to an embodiment of the present invention. The illustrated figure.

As shown in FIG. 3A, a leader is disposed at a strategic position at which the electronic tag is to be recognized, thereby checking information of an article entering and exiting the electronic tag interrogation zone.

As such, a reader that can physically check the information of the electronic tag by radio frequency is called a physical leader. The physical leader may represent one or more strategic specific areas. An area composed of one or more physical leaders and representing a specific space is called a logical leader.

By separating the meaning of the reader as described above, when the leader is physically added or deleted, the upper location tracking application 150 can query the logical leader representing a specific area without having to recognize the internal leader setting state. There is no need to know.

In this sense, the relationship between the physical leader and the logical leader can be specified, but if the physical leader and the logical leader are set to have a 1: 1 relationship, they can be used as the same meaning.

And as shown in Figure 3b, a space that can be provided as the location information of the electronic tag in the RFID environment is composed of a logical space (Zone) which is an area formed by a set of one or more logical reader.

For example, in FIG. 3A and FIG. 3B, the logical leader “store 1” to “store 7” and the “special sale corner” all include stores on the first floor of “discount store A”, and thus the logical space “store”. Is defined. The logical space is defined by a larger parent logical space with a containment relationship.

For example, in FIG. 3A and FIG. 3B, the doorway, the store, the checkout counter, and the workplace are all defined as a logical space called “first floor” because they are all located on the first floor of “discount point A”.

Here, the logical space including only the logical leader is called a terminal logical space, and the upper logical space including the terminal logical space is called an index logical space.

In the present invention, the location tracking application 150 directs a location tracking query of an electronic tag directly to a logical leader or a location tracking query to a logical space including a logical leader.

Therefore, the location information of the electronic tag collected by the location information collecting unit 140 is stored as the ID of the logical leader when stored in the location information storage 143. When a query for a logical space is requested from the location tracking application 150, the location tracking query processing module 141 searches for IDs of all logical leaders included in the logical space and makes a query to the logical leader.

The electronic tag location information management system and method according to the present invention targets an environment using a logical leader ID as the electronic tag location information.

4 illustrates an input / output reader, a reader including an input / output logical space, and a configuration of a logical space, wherein the input / output reader is a reader that is responsible for electronic tag input / output to a terminal logical space including a reader and at least one terminal in each terminal logical space. I / O reader exists. Here, the electronic tag cannot enter or leave the terminal logical space from other readers except the input / output reader.

The I / O logical space is a logical space that is responsible for electronic tag I / O to the upper logical space including the logical space, and at least one input / output logical space exists in the set of logical spaces included in the upper logical space. Here, access to the upper logical space cannot be made from other logical spaces other than the input / output logical space.

"Leader _2", "leader _3," and "leader _5", "leader _7" in Figure 4, the "reader _8" is input reader, in order to access the "logical space _first," "leader _2" or "readers _3" For example, you must go through “Reader ₅ ” to enter and exit “Logical Space ₂ ”, “Reader ₇ ” to enter and exit ”Logical Space ₃ ” and “Reader 8” to enter and exit ”Logical Space ₄ ”.

“Logic space ₂ ”, “Logic space ₃ ”, “Logic space ₄ ” must go through “Logic space ₂ ” to enter and exit “Logic space ₅ ” into I / O logical space, and to enter and exit “Logic space ₆ ” It must always pass through logical space ₃ ”or“ logical space ₄ ”.

Referring to FIG. 5 showing the shortest leader movement path of an electronic tag according to an embodiment of the present invention, in order to make a minimum reader visit when the electronic tag moves from “Reader _A ” to “Reader _B ”, the I / O leader and I / O logic You have to move to space only.

If “leader _A ” and “leader _B ” are included in the same terminal logical space, no other leader is included in the shortest leader movement path.

In FIG. 5, when moving from “Reader ₁ ” to “Reader ₂ ”, the shortest leader travel path is “Reader ₁ ” → “Reader ₂ ”, and when moving from “Reader ₁ ” to “Reader ₅ ”, the shortest leader travel path is “Reader ₁ ”→“ Reader ₂ ”→“ Reader ₅ ”.

And "reader _1", the "reader _7" to move the closest leader movement path is moved to the "reader _1" → "leader _2" → "leader _5" → "leader _7", and "reader _7" "Reader _10" in The shortest leader movement path is “leader ₇ ” → “leader ₁₁ ” → “leader ₁₀ ”.

Next, an electronic tag location information management method according to the present invention will be described.

6A and 6B are flow diagrams of a leader proximity grant element and method between readers in accordance with one embodiment of the present invention.

7 is a diagram illustrating a weight graph configuration using a reader proximity as a weight value and using a leader as a node according to an embodiment of the present invention.

8 is a flowchart illustrating a method of ordering leader IDs in one dimension by a graph traversal method according to an embodiment of the present invention.

The method for managing electronic tag location information according to the present invention includes the steps of providing reader proximity between redundancy, ordering and applying a leader ID as a location tracking index, and dynamically reordering the leader ID.

That is, defining logical space by using topological information between readers, calculating leader proximity between readers to arrange electronic tag location information in storage by using the amount of logical space and tag movement and location tracking query frequency. Constructing a weight graph using the leader as a node based on the proximity; ordering the leader ID by ordering the weight graph nodes in one dimension to store the electronic tag position information in the storage; and using the ordered leader ID Step of applying to 3D location tracking indexing method for storing electronic tag location information. To reflect the reader proximity value that changes over time, the reader ID is dynamically reflected when the current reader proximity value is calculated. Reordering.

First, a description will be given of an element of reader proximity (Reader Proximity) between the readers, which indicates the probability that the electronic tag location information included in the two readers will be accessed together during the electronic tag location tracking query.

For example, when two readers are called rid _i and rid _j , the leader proximity is represented by the proximity function prox (rid _i , rid _j ).

The attributes of reader proximity are as follows.

First, reader proximity exists between all readers in RFID environment.

Second, the proximity reader is identical to rid rid _i at _{i, j} from rid rid _i.

Third, if there is no rid _k with prox (rid _i , rid _j ) <prox (rid _i , rid _k ), the closest leader in leader rid _i is rid _j . That is, the probability that when the electronic tag location query location information to be accessed with a rid _i the electronic tag location information highest position information rid _j.

FIG. 6A illustrates a leader proximity function determinant for two readers, and the first element prox ₁ (rid _i , rid _j ) of the leader proximity determinants of the two readers rid _i and rid _j is the position tracking index module 142. Calculates a value proportional to reader proximity based on the frequency of leader-based temporal queries in the logical space including rid _i and rid _j among all queries. That is, when a query is made to a logical space including two readers, a reader-based time query is performed for all the readers included in the logical space, and there is a possibility that the electronic tag position information with rid _i and rid _j as location information is accessed together. Increases.

The second element, prox ₂ (rid _i , rid _j ), computes a value inversely proportional to reader proximity as the shortest leader travel distance between rid _i and rid _j . In other words, as the distance of the shortest leader movement path increases, the inclusion level of the logical space to which both leaders belong simultaneously increases and the probability of asking a leader-based time query to the logical space becomes low. Therefore, the electronic tag having rid _i and rid _j as location information is used. The probability of accessing location information at the same time becomes low.

The third element, prox ₃ (rid _i , rid _j ), is an electronic tag-based time that includes electronic tag position information including rid _i and rid _j as position information among all queries in the position tracking index module 142. Calculate a value proportional to reader proximity as the frequency of the query.

That is, since the position information of rid _i and rid _j is included in the result set more than other readers, the probability of retrieving the electronic tag position information using the two readers as the position information is increased in the subsequent electronic tag-based time query.

The last element, prox ₃ (rid _i , rid _j ), calculates a value proportional to the proximity of the reader as the ratio of the movement of the electronic tag moving between rid _i and rid _j with respect to the total movement of the electronic tag. In other words, as the number of electronic tags passing through the two readers increases, more queries are searched for the electronic tags using the reader as the location information than the other readers. As a result, the electronic tag location information for the two readers is accessed together. The probability of doing so increases.

6B is a flowchart of a method of calculating a proximity value to give a reader proximity between rid _i and rid _j .

First, in order to set the reader proximity value between the readers, a weight graph in which all nodes are connected is constructed. The weight graph is used as a data structure necessary to provide a method for ordering the leader ID to be presented in one dimension in the present invention. The inter-node weight of the weight graph is set to the reader proximity value calculated in FIG. 6B.

In order to calculate a reader proximity value, which is a weight value between nodes of the constructed weight graph, the following order is used.

First, it is checked whether a leader proximity value between readers is initially set, or whether there is a change in addition or deletion of a leader since calculation of a previous weight value (S601).

If the reader proximity value is first set or there is a change in the leader, the weight value between the graph nodes is updated with the value calculated by prox ₂ (rid _i , rid _j ) among the reader proximity function determination elements (S602). If you are not satisfied, proceed to the next step.

Here, prox ₂ (rid _i , rid _j ) is a proximity function determinant that does not change unless a change in leader placement occurs, so the value is updated only when a change occurs after the initial setting.

Next, it is examined whether an electronic tag movement has occurred between readers since the previous weight value calculation (S603).

If the movement occurs, the weight value between the graph nodes is updated with the value calculated by prox ₄ (rid _i , rid _j ) among the reader proximity function determination elements, and if the electronic tag movement does not occur, the process proceeds to the next step (S604).

Next, it is examined whether a leader-based time query has occurred since the previous weight value calculation (S605).

When the query occurs, the weight value between the graph nodes is updated with the value calculated as prox ₁ (rid _i , rid _j ) among the reader proximity function decision elements, and when the query does not occur, the process proceeds to the next step (S606).

Next, it is examined whether an electronic tag based time query has occurred since the previous weight value calculation (S607).

If a query occurs, the weight value between graph nodes is updated with the value calculated by prox ₃ (rid _i , rid _j ) among the reader proximity function decision elements, and if the query does not occur, the process proceeds to the next step (S608).

Finally, in order to order the leader IDs through the graph traversal illustrated in FIG. 8, the weight values between the graph nodes set in S602, S604, S606, and S608 are provided as a result (S609).

Here, the condition for providing the weight value between the graph nodes as a result is to provide the accumulated information at a predetermined time interval set in advance in the electronic tag location information management system 100 as a result or accumulated at irregular intervals at the request of an administrator. Information can be provided as a result.

After the results are provided, the reader proximity value calculation step is started again after a preset time interval.

In order to give the proximity of the reader of FIG. 6B, the calculation of the proximity value may be performed for each unit time at which the electronic tag location information is collected through the location information collecting unit 130, and preset in the electronic tag location information management system 100. It may be performed at regular time intervals.

7 is a diagram illustrating a weight graph configuration using a reader proximity as a weight value and a leader as a node according to an embodiment of the present invention.

The weight graph can be expressed as H = (V, E, w), where V is a set of nodes constituting the weight graph, and the node represents the reader that collects the information by recognizing the electronic tag in the RFID environment. Same as the ID of. E is a connecting line connecting two nodes constituting the weight graph, and all nodes are connected by connecting lines. w is a weight value of the connection line connecting the nodes and is set to the reader proximity value calculated in FIG. 6B.

8 is a flowchart illustrating a method of ordering leader IDs in one dimension by a graph traversal method according to an embodiment of the present invention.

Reordering the reader IDs composed of the weight graph in one dimension is to store the electronic tag location information logically adjacent to each other on the physical disk when storing the electronic tag location information in the location information storage 143. It is.

The Traveling Salesman Problem (TSP) is used as a method for ordering weight graph nodes. The traveling salesman problem is when you have a large number of cities, and you know the cost of travel from one city to another, you can visit each city once and return to the city where you left off to calculate the least expensive travel route. This is the most used method when ordering weight graph in one dimension.

To find the travel route, we need to find the Hamiltonian cycle with the minimum miminum total weight. In order to apply the weighted graph between the leaders presented in the present invention to the traveling salesman problem, a node for starting and ending the traversal of the graph node is required.

Therefore, in order to apply the traveling salesman problem to the weighted graph shown in FIG. 7, one initial node v0 is created, a connection is generated with all nodes of the graph, and the weight of the generated connection is set to zero.

Also, since the larger the reader proximity value, the two leaders are logically adjacent to each other, but the traveling salesman problem is to find the Hamilton cycle with the minimum weight. There is. Therefore, the w value set in the connecting line E in the weight graph H is set to 1 w.

Next, the leader ID is ordered one-dimensionally by applying the salesman traversal problem, starting with the generated v0 and visiting all nodes of the weight graph once and returning back to v0 at a minimum cost.

Hereinafter, a method of applying to a 3D location tracking index and a leader ID dynamic reconstruction method for storing electronic tag location information using an ordered reader ID will be described in detail.

9 is a flowchart illustrating an application method to a 3D location tracking index for storing electronic tag location information using an ordered reader ID according to an embodiment of the present invention. FIG. 10 is a block diagram illustrating a leader ID dynamic reconfiguration method using Kalman filtering to reflect reader proximity between readers changed over time according to an embodiment of the present invention.

First, the ordered leader ID generated by FIG. 8 is used for a leader ID domain that provides location information in the three-dimensional index of the location tracking index module 142.

Since the order of the leader IDs in the leader ID domain of the location tracking index cannot be changed, the mapping table that maintains the mutual mapping relationship between the leader IDs of the leader ID domains and the ordered leader IDs is updated (S901).

The mapping information adds new mapping information every time an ordered set of leader IDs is generated to maintain the previous leader ID mapping information.

The location information collection unit 130 collects the electronic tag location information and transmits the location information to the location tracking query processing module 141 of the location information management unit 140 (S902).

The location tracking query processing module 141 transmits a query for inserting data to the location information index module 142 in order to store the electronic tag location information transmitted to the location information storage 143. (S903)

The location information indexing module 142 searches the last updated leader ID mapping table to find the leader ID of the leader ID domain of the location tracking index that matches the leader ID recorded in the electronic tag location information (S904).

Subsequently, the electronic tag location information is inserted into the location information store 143 by inserting the electronic tag location information into the location tracking index using the searched reader ID, the electronic tag ID, and the time information of the searched reader ID domain. It is disposed close to the other electronic tag position information with the adjacent position information.

FIG. 10 is a diagram illustrating a leader ID dynamic reconstruction method using Kalman filtering to reflect reader proximity between readers changed over time according to an embodiment of the present invention.

The method of calculating a reader proximity value between two readers described in FIG. 6B may use a Kalman filter, which is a dynamic prediction model that estimates a value over time and corrects an error of the estimated value.

The Kalman filter can be used to calculate a more accurate current reader proximity value that reflects the leader proximity value between two leaders that were calculated in the past.

The electronic tag location information management system and method according to the present invention is a reader between readers so that close location information can be closely located when storing the location information of the electronic tag using the ID of the reader capable of recognizing the electronic tag. Allow proximity to be given.

Those skilled in the art will appreciate that various changes and modifications can be made without departing from the spirit of the present invention.

Therefore, the technical scope of the present invention should not be limited to the contents described in the embodiments, but should be defined by the claims.

The electronic tag location information management system and method according to the present invention has the following effects.

First, by defining and ordering proximity between readers according to the electronic tag location tracking and tag movement characteristics, the location of adjacent electronic tag locations may be closely located in the storage, thereby improving response time of the electronic tag location tracking query.

In addition, according to the present invention, when the proximity between readers is changed by changing the amount of tag movement and the electronic tag location tracking query for each reader over time, based on the changed proximity value by dynamically reordering leader IDs. By dynamically changing the location of the electronic tag location information in the repository, the performance of the query can be maximized when the location tracking query is issued.

In addition, the reader ID ordering method proposed in the present invention uses the performance of the location tracking query by using the 3D location tracking index for storing and tracking the location information of the electronic tag in the EPCIS, the electronic tag information storage middleware proposed by EPCglobal. It can be improved.

Claims (17)

A system for managing electronic tag location information using information from a plurality of tags, A location tracking application that issues a query to search for location information obtained through an ID of a reader obtaining information from the tags; A location information collection unit for collecting and transmitting location information according to filtering and collection conditions registered by the location tracking application; And a location information management unit for storing the transmitted location information and retrieving information meeting the query conditions of the location tracking application. The method of claim 1, wherein the location information, Electronic tag location information management system characterized in that it is expressed including the ID of the reader that obtained the information of the electronic tag, the ID of the recognized electronic tag, the recognized time. The method of claim 1, wherein the location information retrieved by the location tracking application, Electronic tag position, characterized in that the current position information of the item recognized at any one point in any one reader, or the movement trajectory history information represented by the ID of the leader indicating that any one item is moved at the selected time. Information Management System. The method of claim 1, wherein the location information management unit, A location information storage for storing location information of the electronic tag collected through the location information collecting unit; A location information index module for storing the location information of the collected electronic tags in the location information storage, searching for location information required by a location tracking application, and transmitting the result; And a location information query processing module which transmits the location information of the collected electronic tags to the location information index module, lowers the query of the location tracking application to the location information index module, and transmits the search results to the location tracking application. Tag geolocation management system. The method of claim 4, wherein the location information index module A part of providing reader proximity between readers to give proximity between electronic tag location information collected by the location information collecting unit; Ordering reader IDs to arrange and store electronic tag location information close to the location information storage; And a part of dynamically reordering leader IDs by calculating a current proximity value reflecting past proximity values between readers that change over time. The method of claim 4, wherein when a query for logical space is requested from a location tracking application, The location tracking query processing module searches for IDs of all logical readers included in the logical space and makes a query to the logical leader. According to claim 6, Logical space is a space that can be provided as the location information of the electronic tag in the RFID environment is an area formed by one or more logical reader, Logical reader is an electronic tag location information management system, characterized in that the area representing a specific space composed of one or more physical reader that can identify the information of the electronic tag by radio frequency. 6. The system of claim 5, wherein the Kalman filtering method is used to calculate the current inter-reader proximity value by reflecting the past inter-reader proximity value. A system for managing electronic tag location information using information from a plurality of tags, A location tracking application that issues a query to search for location information obtained through an ID of a reader obtaining information from the tags; A location information collection unit for collecting and transmitting location information according to filtering and collection conditions registered by the location tracking application; A part for providing reader proximity between readers to give proximity between the electronic tag location information collected by the location information collecting unit, and a part for ordering leader ID for arranging and storing electronic tag location information in proximity to the location information storage. And a location information index module having a portion that dynamically reorders the leader ID by calculating a current proximity value by reflecting a past proximity value between readers changed over time, and stores the transmitted location information. An electronic tag location information management system comprising: a location information management unit for searching for information matching the query condition of the location tracking application. In order to manage electronic tag location information, Defining a logical space using phase information between readers; Calculating leader proximity between readers using the moving amount of the logical space and the tag and the location tracking query frequency; Constructing a weight graph using a leader as a node based on the leader proximity; Arranging the leader IDs by ordering the weight graph nodes in one dimension to store the electronic tag position information; Applying to a 3D location tracking indexing method for storing electronic tag location information using an ordered reader ID; Dynamically reordering the leader ID by reflecting the past reader proximity value when calculating the current reader proximity value to reflect the reader proximity value that changes over time; Electronic tag location information management method comprising the . 11. The system of claim 10, wherein the Kalman filtering method is used to calculate the current inter-reader proximity value by reflecting the past inter-reader proximity value. A first step of calculating a value proportional to reader proximity by the frequency of leader-based temporal queries issued to the logical space including two readers among all queries issued by the location tracking application; Calculating a value inversely proportional to leader proximity with the shortest leader movement path distance between the two readers; A third step of calculating a value proportional to the proximity of the reader by the frequency of the electronic tag-based temporal query including the electronic tag location information including the two readers as the location information among the entire queries as a result set; A fourth step of calculating a value proportional to the proximity of the reader as a ratio of the movement amount of the electronic tag moving between the two readers among the collected electronic tag location information; and providing the proximity of the reader to the reader. Information management method. 13. The method of claim 12, wherein the first step for calculating the reader proximity value is Electronic tag location information management method characterized in that proceeds when a leader-based time query occurs after the previous weight value calculation. The method of claim 12, wherein the second step for calculating the reader proximity value comprises: Electronic tag location information management method characterized in that the first step of setting the reader proximity value between the reader, or when there is a change in the addition, deletion, etc. of the reader after the previous weight value calculation. The method of claim 12, wherein the third step for calculating the reader proximity value comprises: Electronic tag location information management method characterized in that proceeds when the electronic tag-based time query occurs after the previous weight value calculation. The method of claim 12, wherein the fourth step for calculating the reader proximity value comprises: Electronic tag position information management method characterized in that proceeds when the electronic tag movement between readers after the previous weight value calculation. In order to order the leader ID using the calculated reader proximity value and apply it to the location index, Constructing a weight graph using a reader as a node as a weight value of the reader proximity value between the readers; Ordering the nodes in the weight graph for use in placing a leader ID in the leader ID domain; Inserting the electronic tag location information by connecting the ordered reader ID and the reader ID in the reader ID domain of the location information index module by using the mapping table with the collected electronic tag location information; How to manage location information.

Images