Network protocol for wireless ad hoc networks

• US 6,791,949 B1
• Filed: 04/28/2000
• Issued: 09/14/2004
• Est. Priority Date: 04/28/2000
• Status: Expired due to Term

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Ryu, Bong K., Smallcomb, James X., Erickson, Jason C., Dao, Son K.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): McLoughlin, Mike
• Application Number:
  US09/561,399
• Time in Patent Office: 1,600 Days
• Field of Search: 370/254, 370/255, 370/310, 370/312, 370/328, 370/329, 370/351, 370/400, 370/401, 370/410, 370/432, 370/465, 370/475, 455/422.1, 455/445, 455/452.1
• US Class Current: 370/254
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

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.

Claims

1. 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.

2. 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.

3. 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.

4. The method of claim 3 wherein said predetermined maximum rate is a predetermined percentage of a total system bandwidth allocated for signaling packet processing.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.