Dynamic multicast grouping for vehicles and other mobile objects

• US 7,065,576 B2
• Filed: 09/27/2001
• Issued: 06/20/2006
• Est. Priority Date: 09/27/2001
• Status: Active Grant

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Zou, Li, Kamel, Ibrahim Mostafa
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): SALL, EL HADJI MALICK
• Application Number:
  US09/965,691
• Publication Number:
  US 20030060216A1
• Time in Patent Office: 1,727 Days
• Field of Search: 709/205, 709/209, 709/227, 709/228, 709/223, 709/239, 455/519
• US Class Current: 709/227
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04W 4/08 User group management
• CPC Class Codes: H04W 8/08 Mobility data transfer
• CPC Class Codes: H04W 8/14 between corresponding nodes

Abstract

An area is divided into regions or cells each having an associated multicast group address. The cells are organized using a quad-tree data structure that is dynamically updated. Mobile entities within a given cell elect one of their members as coordinator for assessing cost data associated with subdividing or merging the cell with other sibling cells. The coordinators communicate this cost data to a partitioning entity, which may be a central server, that computes a new partition scheme using a greedy algorithm. The new partition scheme is then broadcast to the mobile entities for use in subsequent communication. Mobile entities join multicast groups that intersect with their individual vision domains. In this way, mobile entities can acquire information from other mobile entities without the need to monitor all multicast group transmissions.

Claims

1. A method for grouping mobile entities, comprising:

defining a partitioning entity;

constructing an initial data structure that defines a plurality of cells occupied by said mobile entities;

for each cell, electing a coordinator from a set of mobile entities occupying that cell;

said coordinators cooperatively computing costs associated with selectively subdividing and merging said cells and communicating said costs to said partitioning entity; and

said partitioning entity using said costs to generate a new partition scheme and communicating said new partition scheme to said mobile entities;

wherein said mobile entities use their respective vision domains and a most current partitioning scheme to effect a state disseminating protocol designed to ensure that state messages originating from each mobile entity reach all other interested mobile entities, each vision domain corresponding to a predefined area of interest.

2. The method of claim 1 further comprising:

associating a multicast group with each of said cells and using said multicast group to support communication among mobile entities within each cell.

3. The method of claim 1 wherein said step of cooperatively computing comprises:

each coordinator computing a first cost associated with subdividing that coordinator'"'"'s cell; and

using said data structure to identify sibling relationships among said coordinators to define sibling coordinators; and

said sibling coordinators collectively computing a second cost associated with merging cells occupied by said sibling coordinators.

4. The method of claim 1 further comprising:

associating a multicast group with each of said cells;

associating a vision domain with each of said entities; and

enabling said entities to selectively join at least one of said multicast groups based on said vision domain.

5. The method of claim 1 further comprising associating a multicast group with each of said cells, allowing said entities to join at least one of said multicast groups and computing said costs by assessing the number of multicast groups said entities have joined.

6. The method of claim 1 further comprising associating a multicast group with each of said cells and using said multicast groups to communicate said new partition scheme to said mobile entities.

7. The method of claim 1 further wherein said partitioning entity generates said new partition scheme by dividing the one of said cells that gives the largest cost decrease.

11. The method of claim 2 wherein said state disseminating protocol includes:

computing by each user of cells which intersect with its own vision domain using its knowledge of the current partition scheme;

joining by each user of all multicasting groups associated with its intersecting cells, and preparing to receive information from these groups;

sending by each user of its state information to its own cell group in which it is located; and

upon receiving the information from all joined multicast groups, filtering out by each user of superfluous messages and maintaining by each user of a record of a number of messages filtered to serve as a cost metric used by one or more coordinators.

8. A system for grouping mobile entities comprising:

a partitioning server;

said partitioning server defining a data structure having nodes corresponding to cells occupied by said mobile entities;

a plurality of client applications each associated with one of said mobile entities;

said client applications each having communication mechanism capable of communicating with the communication mechanism of other client applications and with said partitioning server; and

said client applications and said partitioning server being configured to establish a dynamic partition protocol whereby said data structure is reconfigured based on the number of communicating entities within each of said cells;

wherein said mobile entities use their respective vision domains and a most current partitioning scheme to effect a state disseminating protocol designed to ensure that state messages originating from each mobile entity reach all other interested mobile entities, each vision domain corresponding to a predefined area of interest.

9. The system of claim 8 wherein said client applications each have memory for storing the vision domain corresponding to the predefined area of interest and said communication mechanism of each of said client applications is configured to join in multicast group communication mobile entities in cells that overlap with said vision domain.

10. The system according to claim 8 wherein said mobile entities are vehicles having position location equipment that generates vehicle position data and wherein said client applications communicate said vehicle position data to other client applications associated with mobile entities occupying a common cell.

12. The system of claim 8 wherein said state disseminating protocol includes:

computing by each user of cells which intersect with its own vision domain using its knowledge of the current partition scheme;

joining by each user of all multicasting groups associated with its intersecting cells, and preparing to receive information from these groups;

sending by each user of its state information to its own cell group in which it is located; and

upon receiving the information from all joined multicast groups, filtering out by each user of superfluous messages and maintaining by each user of a record of a number of messages filtered to serve as a cost metric used by one or more coordinators.