US6791949B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Network protocol for wireless ad hoc networks
Assignee: Raytheon Co
•
Filing: 2000-04-28
•
Granted: 2004-09-14
•
Expires: 2020-04-28
Abstract
Abstract A method for establishing and maintaining a wireless ad hoc network comprising backbone nodes which forward packets through the network and non-backbone nodes which are capable of using the network, but do not forward packets. Signaling packets containing one or more protocol support records are periodically generated and transmitted by each node to neighboring nodes and are forwarded through the network by backbone nodes. Non-network nodes are initially selected to become backbone members during a SELECTION process based on an assessment of the node's connectivity relative to its neighbors. Link quality between nodes is monitored and used during an EXPANSION process in which additional non-network nodes may become backbone members. Disconnected backbone segments are interconnected during a CONNECTION process and the network is maintained during a MAINTENANCE process by periodically assessing the value of a backbone node's membership in the backbone. Efficient multicast routing is supported over the backbone by dynamically establishing and maintaining multicast trees. Signaling packets are periodically and frequently generated, thereby facilitating rapid adaptation to network changes. Further, the signaling packets are efficiently forwarded only by backbone nodes, thereby reducing bandwidth associated with establishing and maintaining the network.
Inventors
- 👤 Bong K. Ryu
- 👤 Jason C. Erickson
- 👤 James X. Smallcomb
- 👤 Son K. Dao
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:32
CPC Classifications
H; H04; H04W; H04W84/00; H04W84/18; H04W88/00; H04W88/02; H04W88/04
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
122 words
A method for establishing a network from a plurality of nodes, said network comprising a first subset of said plurality of nodes designated as backbone nodes and a second subset of said plurality of nodes designated as non-backbone nodes, said method comprising the steps of: periodically transmitting a signaling packet by each of said plurality of nodes, wherein each of said plurality of nodes transmitting said signaling packet is a transmitter and each of said signaling packets contains at least one protocol support record; selecting as backbone nodes a subset of said plurality of nodes in response to said at least one protocol support record; and forwarding said at least one protocol support record to neighboring nodes only by said backbone nodes.
Claim 2
Independent Claim
122 words
A method for establishing a network from a plurality of nodes, said network comprising a first subset of said plurality of nodes designated as backbone nodes and a second subset of said plurality of nodes designated as non-backbone nodes, said method comprising the steps of: periodically transmitting a signaling packet by each of said plurality of nodes, wherein each of said plurality of nodes transmitting said signaling packet is a transmitter and each of said signaling packets contains at least one protocol support record; selecting as backbone nodes a subset of said plurality of nodes in response to said at least one protocol support record; and forwarding said at least one protocol support record to neighboring nodes only by said backbone nodes.
Claim 3
Dependent Claim
57 words
The method of claim 1 wherein each of said plurality of nodes transmits signaling packets containing at least one protocol support record indicating transmitter status at a random rate between a maximum rate and a minimum rate, wherein said maximum rate and said minimum rate are a function of an expected mobility of said plurality of nodes.
Claim 4
Dependent Claim
65 words
The method of claim 2 wherein each of said plurality of backbone nodes transmits additional signaling packets at a second rate determined by either (a) the number of protocol support records contained in a record queue if the available bandwidth of the transmitter dedicated to signaling packet processing has not been exceeded or (b) a predetermined maximum rate if said available bandwidth has been exceeded.
Claim 5
Dependent Claim
24 words
The method of claim 3 wherein said predetermined maximum rate is a predetermined percentage of a total system bandwidth allocated for signaling packet processing.
Claim 6
Dependent Claim
43 words
The method of claim 1 wherein each protocol support record supports a predetermined function related to establishing or maintaining said network and wherein protocol support records are forwarded by said backbone nodes according to a predetermined priority assigned to said protocol support records.
Claim 7
Dependent Claim
37 words
The method of claim 1 wherein said backbone selecting step comprises the step of selecting as a backbone node each of said plurality of nodes which has more non-backbone neighboring nodes than any of its neighboring nodes.
Claim 8
Dependent Claim
46 words
The method of claim 1 further comprising the step of connecting said backbone nodes together in response to receipt by a non-backbone node of a protocol support record containing the address of the non-backbone node and a request that the non-backbone node become a backbone node.
Claim 9
Dependent Claim
32 words
The method of claim 1 further comprising the step of maintaining said network by each backbone node monitoring receipt of protocol support records identifying the backbone node as a valuable backbone member.
Claim 10
Dependent Claim
31 words
The method of claim 8 wherein each of said backbone nodes remains a backbone node as long as it is identified as a valuable backbone member at a predetermined minimum rate.
Claim 11
Independent Claim
147 words
A method for establishing a network from a plurality of nodes, said network comprising a first subset of said plurality of nodes designated as backbone nodes and a second subset of said plurality of nodes designated as non-backbone nodes, said method comprising the steps of: periodically transmitting a signaling packet by each of said plurality of nodes to neighboring nodes, wherein each of said plurality of nodes transmitting said signaling packet is a transmitter and each of said signaling packets contains at least one protocol support record indicating status information about the transmitter; and prior to one of said plurality of nodes transitioning to a backbone node in response to receipt of said at least one protocol support record, evaluating the quality of a link between said node and at least one neighboring node in order to verify that said link quality meets a predetermined minimum requirement.
Claim 12
Independent Claim
147 words
A method for establishing a network from a plurality of nodes, said network comprising a first subset of said plurality of nodes designated as backbone nodes and a second subset of said plurality of nodes designated as non-backbone nodes, said method comprising the steps of: periodically transmitting a signaling packet by each of said plurality of nodes to neighboring nodes, wherein each of said plurality of nodes transmitting said signaling packet is a transmitter and each of said signaling packets contains at least one protocol support record indicating status information about the transmitter; and prior to one of said plurality of nodes transitioning to a backbone node in response to receipt of said at least one protocol support record, evaluating the quality of a link between said node and at least one neighboring node in order to verify that said link quality meets a predetermined minimum requirement.
Claim 13
Dependent Claim
38 words
The method of claim 10 wherein said link quality evaluating step comprises the step of determining whether or not signaling packets are received from said at least one neighboring node at rate greater than a predetermined minimum rate.
Claim 14
Dependent Claim
53 words
The method of claim 10 further comprising the step of maintaining a table at each of said plurality of nodes in response to receipt of said signaling packets from other nodes, wherein said table contains an indicator of link quality from said other nodes to said node at which said table is maintained.
Claim 15
Dependent Claim
47 words
The method of claim 12 further comprising the step of maintaining, at each of said plurality of nodes, at least one statistic based on data contained in said table, wherein said link quality evaluating step is performed prior to said other nodes being included in said statistic.
Claim 16
Dependent Claim
31 words
The method of claim 12 wherein said table is a Neighbor Status Table and each of said other nodes is a neighbor of said node at which said table is maintained.
Claim 17
Dependent Claim
30 words
The method of claim 14 wherein said Neighbor Status Table further contains an indicator of link quality from said node at which said table is maintained to said other nodes.
Claim 18
Dependent Claim
30 words
The method of claim 12 wherein said table is a Route Table and none of said other nodes is a neighbor of said node at which said table is maintained.
Claim 19
Dependent Claim
41 words
The method of claim 10 further comprising the step of designating a subset of said plurality of backbone nodes as a multicast tree, wherein said plurality of backbone nodes comprising said multicast tree forward packets to members of a multicast group.
Claim 20
Dependent Claim
34 words
The method of claim 17 wherein each of said plurality of backbone nodes comprising said multicast tree maintains a Multicast Routing Table based on received protocol support records comprising Multicast Join and Leave Records.
Claim 21
Dependent Claim
34 words
The method of claim 18 wherein each of said plurality of backbone nodes comprising said multicast tree forwards multicast packets to members of said multicast group based on entries in said Multicast Routing Table.
References Cited (Backward Citations)
US5355371A
Cited
US5455569A
Cited
US5974236A
Cited
US5495479A
Cited
US5850592A
Cited
US5987011A
Cited
US6396814B1
Cited
US6304556B1
Cited
US6349210B1
Cited
US6385174B1
Cited
US6349091B1
Cited
US6535498B1
Cited
US6456599B1
Cited
US6512935B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-09-14 | 2008-03-15 | 2008-09-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-09-14 | 2012-03-15 | 2012-09-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-09-14 | 2016-03-15 | 2016-09-14 | $7700.00 | Window Closed / Lapsed |