Skeletal node rules for connected dominating set in ad-hoc networks

• US 7,606,171 B1
• Filed: 07/28/2005
• Issued: 10/20/2009
• Est. Priority Date: 07/28/2005
• Status: Active Grant

• Current Assignee: Rockwell Collins, Inc. (Raytheon Technologies Corporation d/b/a RTX)
• Original Assignee: Rockwell Collins, Inc. (Raytheon Technologies Corporation d/b/a RTX)
• Inventors: Venkatesan, Subbarayan, Young, C. David
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): LEE, KEVIN H
• Application Number:
  US11/191,876
• Time in Patent Office: 1,545 Days
• Field of Search: 370/225, 370/254, 370/310
• US Class Current: 370/254
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method of establishing an arterial sub-network of nodes in a communications network is disclosed. According to the method, the one-hop neighbor sets of each node are compared with the one-hop neighbor sets of the neighbors of each node, and a set of rules are applied to determine whether or not each node is to be part of the arterial sub-network.

Claims

1. In an ad-hoc wireless communications network comprised of a plurality of nodes, a method of establishing an arterial sub-network of nodes such that each of the plurality of nodes in the communications network is within one hop of a node in the arterial sub-network, the anterial sub-network of nodes assigning slots to neighboring nodes, the method comprising steps of:

(a) assigning a first node of the plurality of nodes to be part of the arterial sub-network when a set comprising the one-hop neighbors of the first node is a proper superset of each of the first node'"'"'s one-hop neighbors'"'"' sets of neighbors;

the method further including assigning the first node to not be a part of the arterial sub-network when one of the following is true;

(b) the set of one-hop neighbors of the first node is a proper subset of another node'"'"'s one-hop neighbors;

(c) the set of one-hop neighbors of the first node is equal to a set of one-hop neighbors of a second node, and an identifier of the first node is different from an identifier of the second node such that the identifiers prioritize the second node over the first node;

(d) the first node has a set of neighbors that is different from at least one of said first node'"'"'s neighbors'"'"' neighbor sets and said first node'"'"'s neighbors are either directly connected or they are connected by a node having one-hop neighbors that are reporting disjoint sets of one-hop neighbors,

(e) all nodes in the intersection of the neighbor sets of said first node'"'"'s neighbors have the same number of neighbors where said first node'"'"'s identifier is less than the identifier of one of said all nodes or one of said all nodes has more neighbors than said first node;

(f) the set of one-hop neighbors of said each node is equal to a set of one-hop neighbors of another node, and the identifier of said each node is different from an identifier of said another node such that the identifiers prioritize said another node over said each node,

(g) all nodes in the intersection of the neighbor sets of said each node'"'"'s neighbors have the same number of neighbors where said each node'"'"'s identifier is less than the identifier of one of said all nodes or one of said all nodes has more neighbors than said each node, and

(h) said each node has a set of neighbors that is different from at least one of said each node'"'"'s neighbors'"'"' neighbor sets and said each node'"'"'s neighbors are either directly connected or they are connected by the node having one-hop neighbors that are reporting disjoint sets of one-hop neighbors,

and further wherein said each node is assigned to be part of the arterial sub-network when none of conditions (a), (b), (c), (d), (e), (f), (g), or (h) are true and when one of

said each node has no one-hop neighbors that are part of the arterial sub-network, and

two one-hop neighbors of said each node each have a set of neighbors excluding said each node that are part of the arterial sub-network wherein said sets of neighbors have no nodes in common are true.

2. The method of claim 1, the nodes in the arterial sub-network are assigned time slots that can be made available to non-artery nodes.

3. The method of claim 2, wherein skeletal node rules are utilized.

7. The method of claim 1, further comprising:

when the first node has not been assigned to be part of the arterial sub-network, assigning the first node to be part of the arterial sub-network when one of

the first node has no one-hop neighbors that are part of the arterial sub-network, and

two one-hop neighbors of the first node each have a set of neighbors that excludes said first node and are part of the arterial sub-network, wherein said sets of neighbors are disjoint

is true.

4. In a communications network comprised of a plurality of nodes, a method of establishing an arterial sub-network of nodes such that each of the plurality of nodes in the communications network is within one hop of a node in the arterial sub-network, the method comprising steps of:

(a) assigning a first node of the plurality of nodes to be part of the arterial sub-network when a set comprising the one-hop neighbors of the first node is a proper superset of each of the first node'"'"'s one-hop neighbors'"'"' sets of neighbors;

the method further including assigning the first node to not be a part of the arterial sub-network when one of the following is true;

(b) the set of on e-hop neighbors of the first node is a proper subset of another node'"'"'s one-hop neighbors;

(c) the set of one-hop neighbors of the first node is equal to a set of one-hop neighbors of a second node, and an identifier of the first node is different from an identifier of the second node such that the identifiers prioritize the second node over the first node;

(d) the first node has a set of neighbors that is different from at least one of said first node'"'"'s neighbors'"'"' neighbor sets and said first node'"'"'s neighbors are either directly connected or they are connected by a node having one-hop neighbors that are reporting disjoint sets of one-hop neighbors, and

(e) all nodes in the intersection of the neighbor sets of said first node'"'"'s neighbors have the same number of neighbors where said first node'"'"'s identifier is less than the identifier of one of said all nodes or one of said all nodes has more neighbors than said first node;

further comprising assigning the first node to be a part of the arterial sub-network when one of the following is true;

(f) a set comprising all one-hop neighbors of the first node is not a proper subset of any of the first node'"'"'s one-hop neighbor'"'"'s sets, where

the set comprising the one-hop neighbors of the first node is a proper superset of at least one of the first node'"'"'s one-hop neighbor'"'"'s sets of neighbors, or

the set comprising the one-hop neighbors of the first node is the same as the one-hop neighbor sets of each of the one-hop neighbors of the first node, and where the identifier of the first node is different from identifiers of the one-hop neighbors of the first node such that the identifier of the first node prioritizes the first node over the one-hop neighbors of the first node, and

(g) for the nodes of the set comprising the one-hop neighbors of the first node, the intersection of the neighbor sets of said nodes have the same number of neighbors where the identifier of said first node is greater than the identifiers of all the nodes in the intersection;

(h) assigning the first node of the plurality of nodes to be part of the arterial sub-network when the one-hop neighbors of the first node have sets of neighbors with no nodes in common

(i) assigning, after a time delay, the first node to be part of the arterial sub-network when none of conditions (a), (b), (c), (d), (e), (f), (g) or (h) apply to the first node and when one of

the first node has no one-hop neighbors that are part of the arterial sub-network, and

two one-hop neighbors of the first node each have a set of neighbors that excludes said first node and are part of the arterial sub-network, wherein said sets of neighbors are disjoint

is true.

5. The method of claim 4, wherein the time delay has a random value.

6. The method of claim 4, further comprising:

determining whether each node of the plurality of nodes is to be part of the arterial sub-network by applying conditions (a), (b), (c), (d), (e), (f), (g) and (h) to said each node; and

applying condition (i) to said each node when said each node is not assigned an artery node status after applying conditions (a)-(h) to said each node.

8. An ad-hoc communications network, comprising:

a plurality of nodes, each of the plurality of nodes having a set of one-hop neighbors, said one hop neighbors of each node being nodes directly communicating with said each node;

an arterial, connected sub-network within the plurality of nodes, the arterial sub-network configured to assign communication resources to adjacent nodes that are not part of the arterial sub-network, wherein each of the plurality of nodes are assigned to be part of the arterial sub-network when one of

(a) the set of one-hop neighbors of said each node is a proper superset of each of said each node'"'"'s one-hop neighbors'"'"' sets of neighbors,

(b) the set of one-hop neighbors of said each node is not a proper subset of any of said each node'"'"'s one-hop neighbor'"'"'s sets, where

the set of said each node'"'"'s one-hop neighbors is a proper superset of at least one of said each node'"'"'s one-hop neighbor'"'"'s sets of neighbors, or

the set of said each node'"'"'s one-hop neighbors is the same as the one-hop neighbor sets of each of said each node'"'"'s one-hop neighbors, and where an identifier of said each node is different from identifiers of the one-hop neighbors of said each node such that the identifier of said each node prioritizes said each node over the one-hop neighbors of said each node,

(c) for the nodes of the set comprising the one-hop neighbors of a first node, the intersection of the neighbor sets of said nodes have the same number of neighbors where node i'"'"'s identifier is greater than the identifiers of all the nodes in the intersection, and

(d) one-hop neighbors of said each node have unconnected sets of one-hop neighbors are true, and further wherein said each node is assigned to not be part of the arterial sub-network when one of

(e) the set of one-hop neighbors of said each node is a proper subset of another node'"'"'s one-hop neighbors,

(f) the set of one-hop neighbors of said each node is equal to a set of one-hop neighbors of another node, and the identifier of said each node is different from an identifier of said another node such that the identifiers prioritize said another node over said each node,

(g) all nodes in the intersection of the neighbor sets of said each node'"'"'s neighbors have the same number of neighbors where said each node'"'"'s identifier is less than the identifier of one of said all nodes or one of said all nodes has more neighbors than said each node, and

(h) said each node has a set of neighbors that is different from at least one of said each node'"'"'s neighbors'"'"' neighbor sets and said each node'"'"'s neighbors are either directly connected or they are connected by a node having one-hop neighbors that are reporting disjoint sets of one-hop neighbors

are true, and further wherein said each node is assigned to be part of the arterial sub-network when none of conditions (a), (b), (c), (d), (e), (f), (g), or (h) are true and when one of

said each node has no one-hop neighbors that are part of the arterial sub-network, and

two one-hop neighbors of said each node each have a set of neighbors excluding said each node that are part of the arterial sub-network, wherein said sets of neighbors have no nodes in common

are true.