DISTRIBUTED STOCHASTIC CLUSTERING FOR AUTOMATED FORMATION OF CONNECTED NETWORKS OF AGENTS
First Claim
1. A method for forming a hierarchical network from an arbitrary set of agents, comprising steps for:
- initially designating each agent of an arbitrary set of agents as a “
head node”
of its own hierarchical cluster;
initiating an iterative process comprising steps for;
causing each head node of each hierarchical cluster to randomly choose between a role as a “
requestor” and
a role as a “
listener”
;
for each requestor, randomly selecting an agent from the set of agents and sending a merge request to that agent;
for each agent receiving a merge request, recursively passing that merge request to that agents head node;
for each head node acting as a listener that receives only a single merge request, causing the head node to accept the merge request;
for each head node acting as a listener that receives multiple merge requests, causing the head node to select a single one of the multiple merge requests;
for all accepted merge requests, performing a separate disjoint merge to merge the hierarchical cluster of the requestor as a child cluster to the agent receiving the corresponding merge request; and
repeating the steps of the iterative process until only a single hierarchical cluster remains for the arbitrary set of agents.
2 Assignments
0 Petitions
Accused Products
Abstract
A “Stochastic Clustering-Based Network Generator” enables rapid formation of an interconnected hierarchical network structure from an arbitrary number of agents via an iterative turn-based coalescence process. Given N agents wishing to coalesce into one hierarchical network, a turn-based process allows each agent (or the head of each hierarchical cluster of agents), to randomly decide whether to issue or listen for merge requests in each round. Issuing a request amounts to contacting a randomly chosen agent with a merge request. Given multiple received requests, a cluster head will randomly accept one request for a merge received by any agent in that cluster. The requesting cluster then merges as a hierarchical child of the accepting cluster. In a related embodiment, given multiple merge requests, the request from the smallest cluster is accepted. In further embodiments, ties of the smallest cluster size are broken based on various options.
-
Citations
20 Claims
-
1. A method for forming a hierarchical network from an arbitrary set of agents, comprising steps for:
-
initially designating each agent of an arbitrary set of agents as a “
head node”
of its own hierarchical cluster;initiating an iterative process comprising steps for; causing each head node of each hierarchical cluster to randomly choose between a role as a “
requestor” and
a role as a “
listener”
;for each requestor, randomly selecting an agent from the set of agents and sending a merge request to that agent; for each agent receiving a merge request, recursively passing that merge request to that agents head node; for each head node acting as a listener that receives only a single merge request, causing the head node to accept the merge request; for each head node acting as a listener that receives multiple merge requests, causing the head node to select a single one of the multiple merge requests; for all accepted merge requests, performing a separate disjoint merge to merge the hierarchical cluster of the requestor as a child cluster to the agent receiving the corresponding merge request; and repeating the steps of the iterative process until only a single hierarchical cluster remains for the arbitrary set of agents. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system for forming a hierarchical network of agents, comprising:
-
a device for identifying an arbitrary set of agents having network communications capabilities; a device for providing each agent contact information for each other agent; a device for initially designating each agent as a root of its own hierarchical cluster; a device for initiating a round-based coalescence process comprising; a device for causing each root of each hierarchical cluster to randomly choose between a role as a “
requestor” and
a role as a “
listener”
;a device for causing each requestor to randomly select an agent from the set of agents and sending a merge request to that agent; a device for causing each agent receiving a merge request to recursively pass that merge request to that agents root; a device for causing each listener that receives only a single merge request to accept the merge request; a device for causing for each listener that receives multiple merge requests to select a single one of the multiple merge requests; a device for performing a separate disjoint merge for all accepted merge requests to merge the hierarchical cluster of the corresponding requestor as a child cluster to the agent receiving the corresponding merge request; and a device for iterating the round-based coalescence process until only a single hierarchical cluster remains for the arbitrary set of agents. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A computer-readable medium having computer executable instructions stored therein for causing an arbitrary set of agents to coalesce into a hierarchical network of agents, comprising instructions for:
-
providing each agent contact information for each other agent; initially designating each agent as a root of its own hierarchical cluster; initiating a round-based coalescence process comprising; causing each root of each hierarchical cluster to randomly choose between a role as a “
requestor” and
a role as a “
listener”
;causing each requestor to randomly select an agent from the set of agents and sending a merge request to that agent; causing each agent receiving a merge request to recursively pass that merge request to that agents root; causing each listener that receives only a single merge request to accept the merge request; causing for each listener that receives multiple merge requests to select a single one of the multiple merge requests; performing a separate disjoint merge for all accepted merge requests to merge the hierarchical cluster of the corresponding requestor as a child cluster to the agent receiving the corresponding merge request; and iterating the round-based coalescence process until only a single hierarchical cluster remains for the arbitrary set of agents. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification