System and method for identifying potential hidden node problems in multi-hop wireless ad-hoc networks for the purpose of avoiding such potentially problem nodes in route selection

• US 7,200,149 B1
• Filed: 11/19/2002
• Issued: 04/03/2007
• Est. Priority Date: 04/12/2002
• Status: Expired due to Term

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: MeshNetworks, Inc. (Motorola Solutions, Inc.)
• Inventors: Hasty, Jr., William V.
• Primary Examiner(s): To, Doris H.
• Assistant Examiner(s): Tsegaye, Saba
• Application Number:
  US10/298,542
• Time in Patent Office: 1,596 Days
• Field of Search: 370/238, 370/252, 370/254, 370/255, 370/310, 370/312, 370/338, 370/400, 455/7, 455/445
• US Class Current: 370/400
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A system and method for identifying potential hidden node problems in a multi-hop wireless ad-hoc communication network, such as an 802.11 network. The system and method evaluates the relationship between the neighbors of each respective node to identify nodes of a wireless ad-hoc communication network whose capabilities of receiving data packets can be adversely affected by hidden node problems in order to avoid selecting paths containing those potentially problem nodes for routing data packets. Specifically, for each node, the system and method generates a node metric identifying the relationship between the neighbors of a node. Each node can then transmit its respective metric with its routing advertisement data, so that other nodes can assess the degree of potential hidden node problem that may be experienced by that node, and can choose to avoid using that potentially problem node for routing data packets to other nodes.

Claims

1. A method for route selection in an ad-hoc communications network utilizing medium access protocols (MAC), said network including a plurality of nodes wherein each of the plurality of nodes includes a transceiver for transmitting and receiving signals to and from other nodes in said network, the method comprising:

identifying hidden nodes which adversely affect communication between nodes comprising;

calculating a first neighbor node set for at least one node of said plurality, and calculating a second neighbor node set for at least one neighbor node contained in said first neighbor node set, and

calculating a degree of hidden nodes value for said at least one node based on said first and second neighbor node sets and communicating said value as part of a routing advertisement; and

selecting a routing path which avoids an area containing a high degree of said hidden nodes.

2. A method as claimed in claim 1, wherein said identifying hidden nodes step further comprises:

calculating said first neighbor node set to include each neighbor node of said at least one node, said each neighbor node comprising a node of said plurality with which said at least one node can directly communicate.

3. A method as claimed in claim 1, wherein said identifying hidden nodes step further comprises:

communicating said first neighbor node set to said at least one neighbor node.

4. A method as claimed in claim 1, wherein said identifying hidden nodes step further comprises:

calculating said second neighbor node set to include each neighbor node of said at least one neighbor node, said each neighbor node comprising a node of said plurality with which said at least one neighbor node can directly communicate.

5. A method as claimed in claim 1, wherein said identifying hidden nodes step further comprises:

communicating said second neighbor node set to said at least one node.

6. A method as claimed in claim 1, wherein said identifying hidden nodes step further comprises:

calculating a third neighbor node set to include each neighbor node that is included in said first neighbor node set which is not also a neighbor node that is included in said second neighbor node set.

7. A method as claimed in claim 6, wherein said identifying hidden nodes step further comprises:

locating each neighbor node that is contained in said third neighbor node set which is a sub-neighbor node, said sub-neighbor node comprising at least one neighbor node that is contained in said third node set which can directly communicate with at least one other neighbor node contained in said third neighbor node set; and

combining at least one sub-neighbor node plurality into a single representative neighbor node in said third neighbor node set.

8. A method as claimed in claim 7, wherein said identifying hidden nodes step further comprises:

calculating said degree of hidden nodes value based on said third neighbor node set.

9. A method as claimed in claim 1,

wherein said identifying hidden nodes step further comprises:

calculating said degree of hidden nodes value for each node of said plurality; and

further wherein said selecting a routing path step further comprises;

calculating at least one transmission route from a source node to a destination node based upon at least one said degree of hidden nodes value.

10. A method as claimed in claim 1, wherein said selecting a routing path step further comprises:

calculating at least one transmission route via a routing algorithm based upon said degree of hidden nodes value.

11. A system for route selection in an ad-hoc communications network utilizing medium access protocols (MAC), said network including a plurality of nodes wherein each of the plurality of nodes includes a transceiver for transmitting and receiving signals to and from other nodes in said network, the system comprising:

a first node, wherein said first node calculates a first neighbor node set for at least one node of said plurality;

wherein said first node further calculates a second neighbor node set for at least one neighbor node contained in said first neighbor node set;

wherein said first node further calculates a degree of hidden nodes value for said at least one node based on said first and second neighbor node sets and communicate said value as part of a routing advertisement; and

wherein said first node further selects a routing path which avoids an area containing a high degree of said hidden nodes.

12. A system as claimed in claim 11, wherein:

said first node is calculates said first neighbor node set to include each neighbor node of said at least one node, said each neighbor node comprising a node of said plurality with which said at least one node can directly communicate.

13. A system as claimed in claim 11, wherein:

said first node communicates said first neighbor node set to said at least one neighbor node.

14. A system as claimed in claim 11, wherein:

said first node calculates said second neighbor node set to include each neighbor node of said at least one neighbor node, said each neighbor node comprising a node of said plurality with which said at least one neighbor node can directly communicate.

15. A system as claimed in claim 11, wherein:

said first node communicates said second neighbor node set to said at least one node.

16. A system as claimed in claim 11, wherein:

said first node calculates a third neighbor node set to include each neighbor node that is included in said first neighbor node set which is not also a neighbor node that is included in said second neighbor node set.

17. A system as claimed in claim 16, wherein:

said first node locates each neighbor node that is contained in said third neighbor node set which is a sub-neighbor node, said sub-neighbor node comprising at least one neighbor node that is contained in said third node set which can directly communicate with at least one other neighbor node contained in said third neighbor node set; and

said first node combines at least one sub-neighbor node plurality into a single representative neighbor node in said third neighbor node set.

18. A system as claimed in claim 17, wherein:

said first node calculates said degree of hidden nodes value based on said third neighbor node set.

19. A system as claimed in claim 11, wherein:

said first node calculates said degree of hidden nodes value for each node of said plurality; and

said first node calculates at least one transmission route from a source node to a destination node based upon at least one said degree of hidden nodes value for selecting said routing path.

20. A system as claimed in claim 11, wherein:

said first node calculates at least one transmission route via a routing algorithm based upon said degree of hidden nodes value for selecting said routing path.