Distribution of potential neighbor information through an ad hoc network

• US 6,456,599 B1
• Filed: 02/07/2000
• Issued: 09/24/2002
• Est. Priority Date: 02/07/2000
• Status: Expired due to Term

• Current Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation), Verizon Corporate Services Group Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Corporate Services Group Incorporated (Verizon Communications Inc.)
• Inventors: Elliott, Brig Barnum
• Primary Examiner(s): Jung, Min
• Application Number:
  US09/499,842
• Time in Patent Office: 960 Days
• Field of Search: 370/254, 370/255, 370/310, 370/312, 370/238, 455/445, 455/519
• US Class Current: 370/254
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing

Abstract

A communication network includes plural nodes capable of receiving and issuing messages. Each node has actual neighboring nodes to which it is connected. At each node, network information is received from other nodes of the network. Information of potential neighboring nodes to which the node could possibly be connected is generated in the node in response to the network information received from other nodes of the network. A network information message issued from the node to the other nodes of the network that includes information of the potential neighboring nodes.

Claims

1. A network node apparatus comprising:

a memory which stores link-state information regarding neighboring nodes in a network;

a processor which (i) determines a list of potential neighbor nodes with which the network node could communicate directly but to which the network node is not currently linked, and (ii) determines cost-of-transaction information regarding each potential neighbor node on the list of potential neighbor nodes; and

a transmitter which transmits the list of potential neighbor nodes and the determined cost-of-transaction information to the network.

2. A programmable computer for use in operating a communication node in an ad hoc communication network, the communication node capable of issuing and receiving messages, each node having neighboring nodes including actual neighboring nodes to which the communication node is linked and potential neighbor nodes with which the communication node could communicate directly but to which the communication node is not currently linked, said programmable computer comprising:

at least one memory including at least one region for storing computer executable program code; and

a processor for executing the program code stored in said memory,

wherein the program code includes code to receive at the node, network information from other nodes in the network, code to generate in the node, information of potential neighboring nodes responsive to the received network information from other nodes of the network, and code to issue a network information message from the node to the other nodes of the network, which network information message includes information of the potential neighboring nodes.

3. In a communication network having plural nodes capable of receiving and issuing messages, each node having neighbor nodes including actual neighboring nodes to which the node is linked and potential neighbor nodes with which the node could communicate directly but to which the node is not currently linked, a method of distributing node information comprising the steps of:

receiving at a node, network information from other nodes in the network;

generating in the node, information of potential neighboring nodes responsive to the received network information from other nodes of the network; and

issuing a network information message from the node to the other nodes of the network, which network information message includes information of the potential neighboring-nodes.

4. The method according to claim 3, wherein the potential neighboring node information includes a node identifier for the node, a node specific sequence number for the node and a list of potential neighbors of the node.

5. The method according to claim 4, wherein the information for each potential neighboring node includes a metric corresponding to a cost of linking the potential neighbor and the node.

6. The method according to claim 3, wherein the information for each potential neighboring node includes a metric corresponding to a serviceability of a link between the potential neighbor and the node.

7. The method according to claim 3, wherein the network information message which includes the information of potential neighboring nodes is issued from the node less frequently than other network information messages.

8. The method according to claim 7, wherein the network information message that includes the information of potential neighboring nodes is issued in response to an occurrence of a predetermined event.

9. The method according to claim 8, wherein the predetermined event comprises at least one of the node realizing a change in the potential neighbors, a change in a state of a potential neighboring node, and an occurrence of a predetermined time-period.

10. The method according to claim 3, wherein the network information messages of the node are issued to the actual neighboring nodes for reissuance to other nodes of the network.

11. The method according to claim 3, further comprising the steps of:

storing network topology information in the node;

processing the received network information messages including the information of potential neighboring nodes to modify the network topology information; and

issuing network information messages including the network topology modifying information.

12. The method according to claim 11, wherein the network topology modifying information includes information corresponding to network reconfiguration.

13. The method according to claim 11, wherein the network reconfiguring information includes at least one of changing potential neighboring nodes to actual neighboring nodes and changing actual nodes to potential neighboring nodes.

14. A method of operating a mobile station for use in a wireless mobile communication network, the network employing a plurality of mobile stations, each of the plurality of stations capable of transmitting and receiving communication signals said method comprising the steps of:

receiving at the mobile station, network information from other stations in the network;

generating in the mobile station, information of potential neighboring stations with which the mobile station could communicate directly but to which the mobile station is not currently linked, that are responsive to the received network information from other stations of the network; and

issuing a network information message from the mobile station to the other stations of the network, which network information message includes information of the potential neighboring stations.

15. The method according to claim 14, wherein the potential neighboring mobile station information includes a station identifier for the mobile station, a station specific sequence number for the mobile station and a list of potential neighbors of the mobile station.

16. The method according to claim 15, wherein the information for each potential neighboring station includes a metric corresponding to a cost of linking the potential neighbor and the mobile station.

17. The method according to claim 14, wherein the information for each potential neighboring station includes a metric corresponding to a serviceability of a link between the potential neighbor and the mobile station.

18. The method according to claim 14, wherein the network information message that includes the information of potential neighboring stations is issued from the mobile station less frequently than other network information messages.

19. The method according to claim 18, wherein the network information message that includes the information of potential neighboring stations is issued in response to an occurrence of a predetermined event.

20. The method according to claim 19, wherein the predetermined event comprises at least one of the mobile station realizing a change in the potential neighbors, a change in a state of a potential neighboring station, and an occurrence of a predetermined time-period.

21. The method according to claim 14, wherein the network information messages of the mobile station are issued to the actual neighboring stations for reissuance to other stations of the network.

22. The method according to claim 14, further comprising the steps of:

storing network topology information in the mobile station;

processing the received network information messages including the information of potential neighboring stations to modify the network topology information; and

issuing network information messages including the network topology modifying information.

23. The method according to claim 22, wherein the network topology modifying information includes information corresponding to network reconfiguration.

24. The method according to claim 22, wherein the network reconfiguring information includes at least one of changing potential neighboring stations to actual neighboring stations and changing actual stations to potential neighboring stations.

25. Computer executable code stored on a computer readable medium, the code for operating a communication node in a communication network having plural nodes capable of receiving and issuing messages, each node having neighboring nodes including actual neighboring nodes to which the communication node is linked and potential neighbor nodes with which the communication node could communicate directly but to which the communication node is not currently linked, said code comprising:

code to receive at the node, network information from other nodes in the network;

code to generate in the node, information of potential neighboring nodes responsive to the received network information from other nodes of the network; and

code to issue a network information message from the node to the other nodes of the network, which network information message includes information of the potential neighboring nodes.

26. A network node apparatus comprising:

means for storing link-state information regarding neighboring nodes in a network;

means for determining a list of potential neighbor nodes with which the network node apparatus could communicate directly but to which the network node is not currently linked and cost-of-transaction information regarding each node on the list of potential neighbor nodes; and

means for transmitting the list of potential neighbor nodes and the determined cost-of-transaction information to the network.