Clusterhead selection in wireless ad hoc networks
First Claim
1. A method for selecting a clusterhead not greater than d hops from any node in a cluster within an ad hoc network, wherein d>
- 1, comprising the steps of;
determining at least one largest node identifier for each node within a d-neighborhood of at least one node;
determining at least one smallest node identifier from the at least one largest node identifier;
selecting a clusterhead for the d-neighborhood of at least one node responsive to the determined at least one largest identifier for each node of the d-neighborhood of at least one node and the determined at least one smallest identifier for each node of the d-neighborhood of at least one node; and
linking each node of the d-neighborhood of at least one node to the selected clusterhead.
1 Assignment
0 Petitions
Accused Products
Abstract
A system and method is disclosed wherein a plurality of nodes within an ad hoc wireless network are able to wirelessly communicate with each other. Each node includes a first data array for storing a node identifier used in selecting a clusterhead and a second data array for storing information relating to the node providing the node identifier for selecting the clusterhead to the node. Control logic of each node is configured according to a heuristic wherein the node initially determines a largest and smallest node identifier for each node. The node selects a clusterhead for the node responsive to the largest node identifier and the smallest node identifier using a set of predefined rules. The nodes within the area are then linked with the selected clusterhead.
-
Citations
28 Claims
-
1. A method for selecting a clusterhead not greater than d hops from any node in a cluster within an ad hoc network, wherein d>
- 1, comprising the steps of;
determining at least one largest node identifier for each node within a d-neighborhood of at least one node;
determining at least one smallest node identifier from the at least one largest node identifier;
selecting a clusterhead for the d-neighborhood of at least one node responsive to the determined at least one largest identifier for each node of the d-neighborhood of at least one node and the determined at least one smallest identifier for each node of the d-neighborhood of at least one node; and
linking each node of the d-neighborhood of at least one node to the selected clusterhead. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19)
- 1, comprising the steps of;
-
14. A method for selecting a clusterhead for a cluster of nodes within a packet radio network, comprising the steps of:
-
setting a largest node identifier for each node of the cluster of nodes initially equal to an identifier of each node;
receiving a plurality of largest node identifiers from each neighboring node at each node of the cluster of nodes;
selecting a largest one of the plurality of largest node identifiers as the largest node identifier at each node of the cluster of nodes;
setting a smallest node identifier for each node associated with the at least one largest node identifier initially equal to an identifier of each node;
receiving a plurality of smallest node identifiers from each neighboring node at each node associated with the at least one largest node identifier;
selecting a smallest one of the plurality of smallest node identifiers as the smallest node identifier at each node associated with the at least one largest node identifier;
determining if a smallest node identifier for a node equals an original node identifier for the node for each node of the cluster of nodes;
selecting the node as its own clusterhead if the smallest node identifier for the node equals the original node identifier of the node for each node of the cluster of nodes;
identifying all node duplicates for the node if the smallest node identifier for the node does not equal the original node identifier of the node for each node of the cluster of nodes;
if node duplicates exist for the node, selecting a node associated with a smallest node duplicate as the clusterhead for each node of the cluster of nodes;
if node duplicates do not exist for a node, selecting a node associated with the largest node identifier for the node as the clusterhead for each node of the cluster of nodes;
transferring the node to a cluster served by a second clusterhead if a pathway between the node and the selected clusterhead passes through another cluster for each node of the plurality of nodes; and
linking each node of the cluster of nodes to the selected clusterhead.
-
-
20. A communications network comprising:
a plurality of nodes capable of wirelessly communicating with each other, each of the nodes further comprising;
a first data array for storing a winning node identifier for selecting a clusterhead;
a second data array for storing an identity of a node transmitting the winning node identifier to the node; and
a set of rules for selecting a clusterhead for the node no more that d-hops from any node in a cluster of the node, where d>
1, from the winning node identifier in the first data array.- View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28)
Specification