REDUCING THE IMPACT OF HIDDEN NODES IN MESH NETWORKS

• US 20120320768A1
• Filed: 06/20/2011
• Published: 12/20/2012
• Est. Priority Date: 06/20/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shaffer, Shmuel, Okwudiafor, Charles, Shetty, Sandeep J.
• Granted Patent: US 9,019,846 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04W 40/16 based on interference
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In one embodiment, hidden neighbor relationships are identified based on received neighbor information from a plurality of nodes in a communication network. Based on determining a number of hidden neighbors for a particular node at various node parameters, a cost function associated with the particular node may be determined and utilized. In another embodiment, a number of hidden nodes of the particular node is determined across a range of transmission powers, and a delay associated with the particular node reaching a root node in the network across the range of transmission powers is also determined based on the neighbor nodes reachable at respective transmission powers. A tradeoff is determined across the range of transmission powers between the number of hidden nodes and the delay, and then the transmission power of the particular node can be set based on an acceptable determined tradeoff.

Claims

1. A method, comprising:

receiving neighbor information from a plurality of nodes in a communication network;

identifying hidden neighbor relationships within the communication network based on the neighbor information;

determining a number of hidden neighbors for a particular node of the plurality of nodes at various node parameters; and

determining a cost function associated with the particular node, the cost function based on the number of hidden neighbors for the particular node, wherein routing functions operate in the communication network based on the cost function.

2. The method as in claim 1, wherein determining the cost function comprises:

selecting a set of node parameters based on the number of hidden nodes of the particular node to minimize interference between hidden neighbors.

3. The method as in claim 1, wherein the node parameters comprise transmission power, transmission channel, and receiver sensitivity.

4. The method as in claim 1, wherein determining the cost function comprises:

selecting a route cost based on the number of hidden nodes of the particular node to minimize interference between hidden neighbors, wherein the route cost is increased with regard to increased numbers of hidden nodes.

5. The method as in claim 1, wherein determining the cost function comprises:

applying a weight to the number of hidden nodes when determining the cost function.

6. The method as in claim 1, wherein determining the cost function comprises:

determining a delay associated with the particular node reaching a root node in the computer network according to node parameters of a particular cost function;

determining a tradeoff between the number of hidden neighbors of the particular node and the delay associated with the particular node reaching the root node; and

determining the cost function based on an acceptable determined tradeoff.

7. The method as in claim 1, further comprising:

selecting a subset of particular nodes within the computer network for which a cost function is based on the number of hidden neighbors.

8. A method, comprising:

determining a number of hidden nodes of a particular node across a range of transmission powers in a computer network, the hidden nodes able to reach neighbor nodes of the particular node, the particular node able to reach the neighbor nodes but not the hidden nodes at the respective transmission power;

determining a delay associated with the particular node reaching a root node in the computer network across the range of transmission powers based on the neighbor nodes reachable at respective transmission powers;

determining a tradeoff across the range of transmission powers between the number of hidden nodes of the particular node and the delay associated with the particular node reaching the root node; and

setting the transmission power of the particular node based on an acceptable determined tradeoff.

9. The method as in claim 8, further comprising:

examining tradeoffs for a plurality of particular nodes;

selecting certain particular nodes of the plurality of particular nodes for which the transmission power is set to a reduced value based on the certain particular nodes having a best tradeoff.

10. The method as in claim 9, wherein setting comprises:

setting a respective transmission power of each certain particular node independently of other certain particular nodes.

11. The method as in claim 8, further comprising:

determining whether tradeoffs are acceptable based on a policy defining a desired maximum number of hidden nodes per particular node and a maximum allowed delay.

12. The method as in claim 8, wherein determining the delay comprises:

basing the delay on expected traffic flow between the particular node and the root node.

13. The method as in claim 8, further comprising:

receiving a packet at the particular node;

classifying the packet as one of either a low-delay packet or a delay-acceptable packet;

setting the transmission power as a first transmission power in response to the packet being a low-delay packet; and

setting the transmission power as the transmission power that is based on an acceptable determined tradeoff in response to the packet being a delay-acceptable packet, the transmission power that is based on an acceptable determined tradeoff in response to the packet being a delay-acceptable packet being lower than the first transmission power.

14. The method as in claim 13, wherein the packet carries an indication of its classification as either a low-delay packet or a delay-acceptable packet.

15. The method as in claim 8, wherein determining the tradeoff comprises:

weighting the tradeoff for one of either the number of hidden nodes of the particular node or the delay associated with the particular node reaching the root node.

16. The method as in claim 8, further comprising:

adjusting a routing cost for a set of certain nodes in the computer network based on a number of hidden neighbor nodes of a set of particular nodes at correspondingly set transmission powers, wherein each node of the set of certain nodes has a corresponding number of hidden nodes above a configured threshold, the adjusted routing cost configured to reduce a likelihood that the certain nodes are selected as intermediate nodes for traffic in the computer network.

17. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

receive neighbor information from a plurality of nodes in a communication network;

identify hidden neighbor relationships within the communication network based on the neighbor information;

determine a number of hidden neighbors for a particular node of the plurality of nodes at various node parameters; and

determine a cost function associated with the particular node, the cost function based on the number of hidden neighbors for the particular node, wherein routing functions operate in the communication network based on the cost function.

18. The computer-readable media as in claim 17, wherein the software when executed to determine the cost function is further operable to:

select a set of node parameters based on the number of hidden nodes of the particular node to minimize interference between hidden neighbors; and

select a route cost based on the number of hidden nodes of the particular node to minimize interference between hidden neighbors, wherein the route cost is increased with regard to increased numbers of hidden nodes.

19. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

determine a number of hidden nodes of a particular node across a range of transmission powers in a computer network, the hidden nodes able to reach neighbor nodes of the particular node, the particular node able to reach the neighbor nodes but not the hidden nodes at the respective transmission power;

determine a delay associated with the particular node reaching a root node in the computer network across the range of transmission powers based on the neighbor nodes reachable at respective transmission powers;

determine a tradeoff across the range of transmission powers between the number of hidden nodes of the particular node and the delay associated with the particular node reaching the root node; and

set the transmission power of the particular node based on an acceptable determined tradeoff.

20. The computer-readable media as in claim 19, wherein the software when executed is further operable to:

examine tradeoffs for a plurality of particular nodes;

select certain particular nodes of the plurality of particular nodes for which the transmission power is set to a reduced value based on the certain particular nodes having a best tradeoff.

21. The computer-readable media as in claim 19, wherein the particular node is configured to classify the packet as one of either a low-delay packet or a delay-acceptable packet, and to set the transmission power as a maximum transmission power in response to the packet being a low-delay packet and set the transmission power as the transmission power that is based on an acceptable determined tradeoff in response to the packet being a delay-acceptable packet.

22. The computer-readable media as in claim 19, wherein the software when executed to determine the tradeoff is further operable to:

weight the tradeoff for one of either the number of hidden nodes of the particular node or the delay associated with the particular node reaching the root node.

23. The computer-readable media as in claim 19, wherein the software when executed is further operable to:

adjust a routing cost for a set of certain nodes in the computer network based on a number of hidden neighbor nodes of a set of particular nodes at correspondingly set transmission powers, wherein each node of the set of certain nodes has a corresponding number of hidden nodes above a configured threshold, the adjusted routing cost configured to reduce a likelihood that the certain nodes are selected as intermediate nodes for traffic in the computer network.