Reliable neighbor node discovery

Abstract

Methods and systems for reliable neighbor discovery in wireless ad hoc networks are provided herein. In one aspect, embodiments of the present invention provide methods and systems for analyzing the quality of a communication link. In embodiments, several factors affecting link quality may be incorporated in the analysis, and basic and/or complex statistical and/or probabilistic analysis may be used. In another aspect, embodiments of the present invention provide methods and systems for neighbor node discovery that adapt to network and/or node operating conditions and that dynamically maintain a neighbor node set at a given node according to these conditions. In a further aspect, embodiments of the present invention extend the utility of neighbor node discovery beyond the customary role of data routing support into the problem of deploying an ad hoc network by providing a display module for displaying node connectivity information.

What is claimed is: 
     
       1. A wireless device for use in a wireless ad hoc network, comprising:
 a wireless network interface that connects said wireless device to said wireless ad hoc network;   a neighbor node discovery module that generates a neighbor node set of said wireless device; and   a display module that displays network connectivity information of said wireless device;   wherein said neighbor node discovery module comprises:
 a transmitter configured to generate and forward a plurality of HELLO messages to said wireless network interface according to a specified messaging rate, wherein said plurality of HELLO messages are characterized by one or more of variable HELLO message packet sizes and variable transmission data rates; 
 a receiver configured to receive at least one REPLY message from said wireless network interface in response to each of said plurality of HELLO messages; 
 a memory configured to store cumulative HELLO/REPLY message data generated based on said plurality of HELLO messages and REPLY messages received in response thereto; and 
 a statistical analyzer module configured to analyze said cumulative HELLO/REPLY message data stored in said memory to generate said neighbor node set of said wireless device. 
   
     
     
       2. The wireless device of  claim 1 , wherein said neighbor node discovery module further comprises:
 a network traffic monitor configured to monitor traffic through said wireless network interface and to generate information regarding network conditions based on the monitored traffic.   
     
     
       3. The wireless device of  claim 2 , wherein said network traffic monitor communicates the generated information regarding network conditions to said transmitter, wherein said transmitter adjusts characteristics of said HELLO message based on said generated information. 
     
     
       4. The wireless device of  claim 1 , wherein said transmitter is configured to generate said HELLO message according to an inter-hello message period. 
     
     
       5. The wireless device of  claim 4 , wherein said inter-hello message period is set according to network conditions. 
     
     
       6. The wireless device of  claim 1 , wherein said transmitter is configured, upon forwarding said HELLO message to said wireless network interface, to store information regarding said HELLO message in said memory. 
     
     
       7. The wireless device of  claim 1 , wherein said receiver is configured to extract information from said REPLY message and to store said extracted information in said memory. 
     
     
       8. The wireless device of  claim 1 , wherein said statistical analyzer module is configured to analyze said information stored in said memory to generate HELLO/REPLY statistics. 
     
     
       9. The wireless device of  claim 1 , wherein said neighbor node discovery module controls said display module based on the generated neighbor node set. 
     
     
       10. The wireless device of  claim 1 , wherein the display module comprises one or more light emitting diodes (LEDs), wherein one of said LEDs is on when said neighbor node set is non-empty and is off when said neighbor node set is empty. 
     
     
       11. The wireless device of  claim 10 , wherein another one of said LEDs is on when said neighbor node set includes a command node of said wireless ad hoc network and is off when said neighbor node set does not include said command node. 
     
     
       12. A method for ad hoc wireless networking, the method comprising:
 broadcasting a plurality of hello messages to nodes in an ad hoc wireless network using a wireless network interface of a broadcasting node, wherein the plurality of hello messages vary with respect to one or more of packet size and data transmission rate;   generating cumulative hello/reply message data in response to receiving replies to the hello messages from one or more of the nodes in the ad hoc wireless network, including a first node; and   processing, at the broadcasting node, the cumulative hello/reply message data to determine whether to include a communication link with the first node in a neighbor node set of the broadcasting node, whereby the neighbor node set comprises nodes in the ad hoc wireless network having reliable communication links with the broadcasting node.   
     
     
       13. The method of claim 12, further comprising:
 determining an inter-hello message period; and   broadcasting the plurality of hello messages according to the inter-hello message period.   
     
     
       14. The method of claim 13, wherein the broadcasting node is mobile, the method further comprising:
 determining the inter-hello message period based upon a rate of change of the broadcasting node.   
     
     
       15. The method of claim 13, wherein a node other than the broadcasting node is mobile, the method further comprising:
 determining the inter-hello message period based upon a rate of change of the node relative to the broadcasting node.   
     
     
       16. The method of claim 12, further comprising:
 removing the first node from the neighbor node set of the broadcasting node in response to processing, at the broadcasting node, the cumulative hello/reply message data.   
     
     
       17. The method of claim 12, further comprising:
 determining a route in the ad hoc wireless network to a node that is not in the neighbor node set of the broadcasting node, the route comprising a node that is in the neighbor node set of the broadcasting node.   
     
     
       18. The method of claim 17, wherein determining the route comprises accessing a neighbor node set of another node in the ad hoc wireless network. 
     
     
       19. The method of claim 12, further comprising:
 determining whether to include the communication link with the first node in the neighbor set of the broadcasting node based upon one of a reply latency and a reply probability of the first node in the cumulative hello/reply message data.   
     
     
       20. The method of claim 19, wherein the reply probability is based upon an error rate of the cumulative hello/reply message data as a function of one or more of packet size and data rate of the plurality of broadcast hello messages. 
     
     
       21. The method of claim 19, wherein the reply latency is based upon a reply latency of the cumulative hello/reply message data as a function of one or more of packet size and data rate of the plurality of broadcast hello messages. 
     
     
       22. The method of claim 19, further comprising:
 determining whether to include the communication link with the first node in the neighbor node set of the broadcasting node using one of a threshold comparison and adaptive trend analysis.   
     
     
       23. A method for ad hoc wireless networking, the method comprising:
 broadcasting a plurality of hello messages on an ad hoc wireless network using a wireless network interface of a broadcasting node;   varying a transmission power of one or more of the plurality of hello messages;   generating cumulative hello/reply message data in response to receiving replies to the hello messages from one or more nodes in the wireless ad hoc network, including a first node, wherein the cumulative hello/reply message data comprises reply characteristics as a function of transmission power of the broadcast hello messages; and   processing at the broadcasting node, the cumulative hello/reply message data to determine whether to include a communication link with the first node in a neighbor node set of the broadcasting node, whereby the neighbor node set comprises nodes in the ad hoc wireless network having reliable communication links with the broadcasting node; and   generating hello/reply message statistics comprising one or more of reply message latency and reply message probability using the cumulative hello/reply message data.   
     
     
       24. The method of claim 23, further comprising:
 determining whether to include the communication link with the first node in the neighbor node set of the broadcasting node using one of a threshold comparison, maximum likelihood analysis, maximum a priori analysis, fuzzy logic analysis, and hidden Markov model analysis.   
     
     
       25. The method of claim 23, further comprising:
 determining an inter-hello message period; and   broadcasting the plurality of hello messages according to the inter-hello message period.   
     
     
       26. The method of claim 25, wherein the inter-hello message period is based upon one or more of a velocity of the broadcasting node and a velocity of a node in the ad hoc wireless network relative to the broadcasting node. 
     
     
       27. The method of claim 23, further comprising:
 removing the first node from the neighbor node set of the broadcasting node in response to processing, at the broadcasting node, the cumulative hello/reply message data.   
     
     
       28. The method of claim 23, further comprising:
 determining a route to a node in the ad hoc wireless network that is not in the neighbor node set of the broadcasting node.   
     
     
       29. The method of claim 28, wherein determining the route comprises accessing a neighbor node set of another node in the ad hoc wireless network. 
     
     
       30. A method for ad hoc wireless networking, the method comprising:
 determining an inter-hello message period of a broadcasting node based upon one of network conditions and operating conditions of the broadcasting node;   broadcasting a plurality of hello messages according to the inter-hello period using a wireless network interface of the broadcasting node, wherein broadcasting comprises varying one or more of a packet size and data transmission rate of one or more of the broadcast hello messages;   generating cumulative hello/reply message data in response to receiving replies to the broadcast hello messages from a first node in the ad hoc wireless network; and   processing, at the broadcasting node, the cumulative hello/reply message data to determine whether to include a communication link with the first node in a neighbor node set of the broadcasting node, whereby the neighbor node set comprises nodes in the ad hoc wireless network having reliable communication links with the broadcasting node.   
     
     
       31. A method for ad hoc wireless networking, the method comprising:
 broadcasting a plurality of hello messages on an ad hoc wireless network using a wireless network interface of a broadcasting node;   varying a transmission power of one or more of the plurality of hello messages;   generating cumulative hello/reply message data in response to receiving replies to the hello messages from one or more nodes in the wireless ad hoc network, including a first node, wherein the cumulative hello/reply message data comprises reply characteristics as a function of transmission power of the broadcast hello messages;   processing at the broadcasting node, the cumulative hello/reply message data to determine whether to include a communication link with the first node in a neighbor node set of the broadcasting node, whereby the neighbor node set comprises nodes in the ad hoc wireless network having reliable communication links with the broadcasting node;   determining an inter-hello message period, wherein the inter-hello message period is based upon one or more of a velocity of the broadcasting node and a velocity of a node in the ad hoc wireless network relative to the broadcasting node; and   broadcasting the plurality of hello messages according to the inter-hello message period.   
     
     
       32. The method of claim 31, further comprising:
 determining whether to include the communication link with the first node in the neighbor node set of the broadcasting node using one of a threshold comparison, maximum likelihood analysis, maximum a priori analysis, fuzzy logic analysis, and hidden Markov model analysis.   
     
     
       33. The method of claim 31, further comprising:
 removing the first node from the neighbor node set of the broadcasting node in response to processing, at the broadcasting node, the cumulative hello/reply message data.   
     
     
       34. The method of claim 31, further comprising:
 determining a route to a node in the ad hoc wireless network that is not in the neighbor node set of the broadcasting node.   
     
     
       35. The method of claim 34, wherein determining the route comprises accessing a neighbor node set of another node in the ad hoc wireless network.