Patent ID: 7542459

Claim:
A method of creating a backbone in an ad hoc network, the method comprising: at a first node, selecting one node from a group of neighboring nodes of the first node to be a first primary relay node for the first node based, at least in part, on router metrics of the neighboring nodes of the first node, said first primary relay node being part of a network backbone; at a second node, selecting one node from a group of neighboring nodes of the second node to be a second primary relay node for the second node based, at least in part, on router metrics of the neighboring nodes of the second node, said second primary relay node being part of the network backbone; at a third node, determining whether said first primary relay node and said second primary relay node are in communication with one another and, when it is determined that said first primary relay node and said second primary relay node are not in communication with one another: initiating a timer with a timer value that is selected based upon a router metric of said third node; when said timer times out, determining whether said first primary relay node and said second primary relay node are still not in communication with one another; and when it is determined that said first primary relay node and said second primary relay node are still not in communication with one another, designating said third node as a secondary relay node to provide communication between said first primary relay node and said second primary relay node, said secondary relay node being part of said network backbone; wherein a primary relay node is a router node that provides communication between a non-router node and the network backbone and a secondary relay node is a router node that provides communication between multiple primary relay nodes.