Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-02-10
2003-06-03
Channavajjala, Srirama (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06574633
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the field of searching for physical entities or devices and more particularly to a method for grouping such physical entities or devices in a topological or physical space.
BACKGROUND OF INVENTION
In various applications, it becomes necessary to select an entity or various entities from a pool of entities to perform certain tasks within a topological area. For example, in cellular phone communications, it is necessary to determine which node is the appropriate node to carry a particular signal when the cellular phone user travels from place to place. To track the user, the cellular phone system can poll each and every node that it controls to determine which node is appropriate for the present location of that user.
Another example of locating physical entities in a physical space arises from the desire to include sensors or physical data sensing devices in fields or other open spaces where they can be used to detect various types of activities. These data sensing devices may be located in an area if possible military activity and be positioned to detect targets, such as tanks, trucks, helicopters, or even people. At the present, such devices tend to be quite expensive and quite large. The expense presents a problem as at least three such data sensing devices are needed for accurate location of any activity and, in case one of these is defective or becomes destroyed, at least one other standby must have been positioned to allow for continued receipt of sensing data. Obviously, the more such sensing devices that can be placed out in the field, the more accurate and the better the collection of data on whatever activity is to be observed. The size becomes a problem as in most instances it is desirable that for whatever activity that is being observed. Finally, present such devices tend to work only in flat or open spaces and not in an environment such as brush or forest.
It is therefore advantageous that the data sensing devices to be placed out in the field should be small, cheap enough to be entirely expendable, and not be active devices that could alert whoever is engaged in the activity to be observed that they are being observed. However, problems arise with the handling of such a large number of sensing devices. The problems involve the selection process for determining which groups of devices are to be active at a given time. It is therefore necessary to segment or section up the space both in terms of the space it self and the groupings of the sensor devices.
In general, such a selection process can be made more efficient by limiting the number of entities that will be searched. The distribution of entities in a topographical space allows for a grouping of the entities on the basis of location. The search and selection process becomes more complex when there are a number of entities distributed in a topological space which utilize different methods to perform their tasks and have differing ranges of effectiveness. The range of effectiveness of an entity for a specific function can be referred to as the entity's footprint. Specific applications can concentrate on only one method of performing a task or what can be referred to as the morphology of the entity. By concentrating on one particular morphology, the application can omit entities that perform the same function, albeit by a different method.
For example, in tracking a particular traveling object, different detection methods can include infrared, RF and visual morphologies. Concentration on only infrared methods of tracking this object can exclude a RF detector that can achieve the function of tracking that particular object. In other instances, depending on the type of object being tracked, visual detection might be unable to track the object while RF detection will accomplish that function. Thus, visual detection exists in a different functional domain than the RF detector. In addition, two different entities might utilize the same method of detection, but still have different functional domains. For example, light detectors might have different frequency ranges which would create different functional domains if the object being detected were light of a specific frequency.
Choosing a subset of entities from the whole set is a combinatorial optimization problem. Almost all the relevant classes of combinatorial optimization problems are NP hard. NP hard problems typically lead to time-consuming searches. Reducing this search space becomes a requirement when there is a time constraint in selecting appropriate entities.
The distribution of entities in a topographical space allows for a separation of these entities on the basis of location. Space partitioning methods based on topology of morphologically different entities and Binary Space Partitioning Trees techniques are useful in limiting the areas of search based on location. In the case of the former, only the partitioning of physical space is considered for better packing of physical objects in a limited space. In the latter, search space partitioning is performed by the separation of entities that are all of different types (there is no distinction between functional and morphological characteristics and there is no concept of physical space). This invention is concerned with the functional partitioning of entities based on the type of objects the entity responds to in a physical space.
SUMMARY OF THE INVENTION
This invention utilizes standard physical space partitioning techniques along with entity characteristics to distribute them into limited size overlapping sets. Partitioning is performed based on the functionality and location of the entity rather than on the morphology of the entity. A membership value, ranging from 0 to 1, is assigned to each entity associated with each set resulting in fuzzy characteristics for the sets. Dynamic variation in the range of effectiveness of the entity is accounted for by changing the memberships of the entities to the groups based on the varying range of effectiveness. A metric can be derived from the membership value list of each entity to enable a unique single dimensional comparison of two disparate entities that are described in many dimensions.
The procedure of partitioning, in summary, is the following: a distribution of the entities in a topographical space is provided as input. The input includes the type and functionality of each entity. Further, the variation of the entity range of effectiveness is input.
First, separate grids are created for each functional attribute of the entities. The grid spacing is an independent parameter that is loosely tied to the range of the functional attribute of the particular grouping of entities. If the ranges of separate types of entities for the same functional characteristics are unequal, the smaller range is selected. The spacing parameter can be, and is, changed if required.
For each grid space of each functional attribute a fuzzy set is created. All those entities of the particular functional attribute whose range of effectiveness overlap a portion of a grid space are assigned to be members of the particular fuzzy set associated with the grid space. The membership value of the entity to that group is determined. This procedure is completed for the entire group of entities that exist in the particular space. A change in the footprint of an entity results in the entity initially being removed from membership of all groups. The assignation is then recomputed based on the aforementioned procedure.
In accordance with one embodiment of the invention, a method for dynamically grouping limited range entities in a topological space is disclosed where the method comprises the steps of: determining functional domains for each entity in the topological space; partitioning the topological space into grids wherein the partitioning step is performed on the topological space for each different functional domain that exists; associating a group with each grid that corresponds to a unique functional domain and unique topological space;
Burne Richard Allen
Jamalabad Vikram Ramesh
Loskiewicz-Buczak Anna
Channavajjala Srirama
Honeywell International , Inc.
LandOfFree
Method for dynamically grouping limited range physical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for dynamically grouping limited range physical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for dynamically grouping limited range physical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3121123