Distributed tempero-spatial query service

• US 7,616,590 B2
• Filed: 07/28/2005
• Issued: 11/10/2009
• Est. Priority Date: 07/28/2005
• Status: Expired due to Fees

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Murray, Paul, Erignac, Charles A, Wan, Ming
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): LEE, KEVIN H
• Application Number:
  US11/191,625
• Publication Number:
  US 20070041336A1
• Time in Patent Office: 1,566 Days
• Field of Search: 370/256, 370/408, 707/10
• US Class Current: 370/256
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/45 Network directories; Name-to-address mapping
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1089 Hierarchical topologies

Abstract

A distributed tempero-spatial query service uses a plurality of service agents each having an assigned area of responsibility. The service agents are organized into a spatial hierarchy based upon each service agent'"'"'s area of responsibility. The spatial hierarchy is distributed and hosted on each of the service agents. The spatial hierarchy enables matching of requests from subscribing agents with publishing agents based upon spatial attributes. The spatial hierarchy is dynamically maintained in a distributed manner on each of the service agents. The service agents can be arranged into a tree-based spatial hierarchy having a limited depth.

Claims

1. A method of matching a publishing agent'"'"'s area of coverage with a subscribing agent'"'"'s area of interest using a distributed tempero-spatial query service, the method comprising:

(a) assigning areas of responsibility (AORs) to a plurality of service agents, the AORs corresponding to three-dimensional volumes of space;

(b) organizing the service agents into a spatial hierarchy (AORH) based upon each service agent'"'"'s AOR;

(c) distributing and hosting the spatial hierarchy on each of the service agents;

(d) matching a request from a subscribing agent with a publishing agent based upon spatial attributes; and

wherein (b) includes defining a local AORH stored at each service agent by;

(i) a service agent'"'"'s containing node that corresponds to the service agent'"'"'s AOR;

(ii) a parent oath from the service agent'"'"'s containing node to a root of the AORH; and

(iii) a subtree rooted at the service agent'"'"'s containing node and ending at a first-encountered contained node of another AOR along each branch of the spatial hierarchy.

2. The method of claim 1, wherein (b) includes organizing the service agents into a tree-based spatial hierarchy.

3. The method of claim 2, wherein (b) includes organizing the service agents into an octree-based spatial hierarchy and representing each node of the spatial hierarchy that corresponds to a particular one of the service agent'"'"'s AOR by octal encoding.

4. The method of claim 1, wherein (c) includes generating a distributed AORH among the service agents.

5. The method of claim 4, wherein generating the distributed AORH among the service agents includes generating a local AORH at a root service agent who'"'"'s AOR covers an entire agent environment and generating a local AORH at service agents that are coworker agents with the root service agent and whose AOR'"'"'s are identical to the root agent'"'"'s AOR.

6. The method of claim 5, wherein generating the local AORH at the service agent includes:

(i) generating the service agent'"'"'s parent path by generating a node path from the service agent'"'"'s containing node towards a root of the AORH and then registering the service agent'"'"'s parent agents at their containing node in that path;

(ii) registering the service agent'"'"'s coworker agents at the service agent'"'"'s containing node;

(iii) collecting the service agent'"'"'s direct-child agents from a set of the service agent'"'"'s child agents; and

(iv) registering each of the direct-child agents at its containing node by generating a node path from the service agent'"'"'s containing node to the direct-child agent'"'"'s containing node and registering the direct-child agent and its coworker agents at the direct-child agent'"'"'s containing node.

7. The method of claim 1, further comprising dynamically maintaining the distributed AORH to account for insertion of new service agents and removal of existing service agents.

8. The method of claim 7, wherein insertion of a new service agent and removal of an existing service agent is done in a distributed manner by the service agents.

9. The method of claim 1, further comprising responding to a subscribing agent'"'"'s query through the distributed AORH in a distributed manner.

10. The method of claim 9, wherein responding to the subscribing agent'"'"'s query through the distributed AORH in the distributed manner includes searching along a parent path in a local AORH to find a nearest registered service agent whose AOR fully contains the subscribing agent'"'"'s area of interest (AOI) and recursively detecting all sensed nodes in that service agent'"'"'s local AORH that intersect with the subscribing agent'"'"'s AOI.

11. The method of claim 1, further comprising registering a new subscribing agent'"'"'s area of interest in the distributed AORH in a distributed manner.

12. The method of claim 1, further comprising registering a new publishing agent'"'"'s area of coverage in the distributed AORH in a distributed manner.

13. The method of claim 1, further comprising processing requests from multiple subscribing agents in parallel on the service agents.

14. The method of claim 1, wherein (d) includes matching the subscribing agent'"'"'s request with the publishing agent based upon spatial attributes of the subscribing agent'"'"'s area of interest and the publishing agent'"'"'s area of coverage.