Distributed tempero-spatial query service

• US 20070041336A1
• Filed: 07/28/2005
• Published: 02/22/2007
• Est. Priority Date: 07/28/2005
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Murray, Paul, Wan, Ming, Erignac, Charles
• Granted Patent: US 7,616,590 B2
• Time in Patent Office: Days
• 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;

(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; and

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

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 service agent'"'"'s AOR by octal encoding.

4. The method of claim 2, 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 path 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.

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

6. The method of claim 5, 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.

7. The method of claim 6, wherein generating a local AORH at a 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.

8. 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.

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

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

11. The method of claim 10, wherein responding to a subscribing agent'"'"'s query through the distributed AORH in a 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.

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

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

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

15. 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.

16. A method of operating a tempero-spatial query service, the method comprising:

(a) assigning areas of responsibility (AORs) to a plurality of service agents;

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

(c) processing multiple requests from subscribing agents in parallel with the service agents.

17. The method of claim 16, further comprising generating a distributed AORH among the service agents and distributing and hosting the AORH on each of the service agents.

18. The method of claim 17, further comprising dynamically maintaining the distributed AORH among the service agents.

19. The method of claim 17, further comprising publishing a publishing agent'"'"'s area of coverage on the distributed AORH on the service agents in a distributed manner.

20. The method of claim 16, further comprising registering publishing agents with the service agents through the AORH based upon spatial attributes of the publishing agents'"'"' areas of coverage and the service agents'"'"' AORs.

21. The method of claim 20, further comprising matching a request from a subscribing agent with a publishing agent based upon spatial attributes of the subscribing agent'"'"'s area of interest and the publishing agent'"'"'s area of coverage.

22. The method of claim 16, further comprising registering a subscribing agent with the service agents through the AORH based upon spatial attributes of the subscribing agent'"'"'s area of interest and the service agents'"'"' AORs.

23. A method of operating a tempero-spatial query service, the method comprising:

(a) assigning areas of responsibility (AORs) to a plurality of service agents;

(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; and

(d) dynamically maintaining the distributed AORH hosted on each of the service agents.

24. The method of claim 23, wherein (d) includes dynamically maintaining the distributed AORH hosted on each of the service agents to account for insertion of new service agents and removal of existing service agents.

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

26. The method of claim 23, wherein (b) includes organizing the service agents into a tree-based spatial hierarchy having a predetermined depth.

27. The method of claim 26, 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 service agent'"'"'s AOR by octal encoding.

28. The method of claim 23, wherein (d) includes dynamically maintaining the distributed AORH hosted on each of the service agents to account for registration of new publishing agents'"'"' areas of coverage.

29. The method of claim 23, wherein (d) includes dynamically maintaining the distributed AORH hosted on each of the service agents in a distributed manner.

30. The method of claim 23, further comprising matching a request from a subscribing agent with a publishing agent based upon spatial attributes of the subscribing agent'"'"'s area of interest and the publishing agent'"'"'s area of coverage.