Distributed topology control for wireless multi-hop sensor networks

• US 20020044533A1
• Filed: 08/07/2001
• Published: 04/18/2002
• Est. Priority Date: 08/07/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bahl, Paramvir, Wang, Yi-Min, Li, Li, Wattenhofer, Roger P.
• Granted Patent: US 6,990,080 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 52/46 in multi hop networks, e.g. wireless relay networks
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

The following description provides direction-based topology control to a distributed wireless multi-hop network. The network includes multiple potentially mobile nodes. Each node sends a discovery message in all directions. Each node discovers a set of neighboring nodes using a set of incoming signals from the neighboring nodes that are responsive to the discovery message. Responsive to receiving the incoming messages, each node makes a local decision about a substantially optimal transmission power with which to communicate with at least a portion of the discovered neighboring nodes. The decisions are based on the incoming signals and are also independent of positional information (e.g., latitude and longitude). Each node in the network maintains communications with the decided portion of nodes to provide connectivity between each of the nodes.

Claims

1. A method providing topology control to a distributed wireless multi-hop network comprising a plurality of nodes, the method comprising:

for each node, discovering a set of neighboring nodes of the nodes using a set of incoming signals from the neighboring nodes, the incoming signals being responsive to receipt by the neighboring nodes of an outgoing signal from a respective node of the nodes;

for each node, making a respective decision about a substantially optimal transmission power to communicate with at least one subset of the neighboring nodes, the respective decision being based on the incoming signals and being independent of positional information;

for each node, maintaining communications with the at least one subset to provide connectivity between each of the nodes.

2. A method as recited in claim 1, wherein collectively each respective decision provides substantially complete connectivity between the nodes in a power efficient manner.

3. A method as recited in claim 1, wherein an incoming signal comprises directional information.

4. A method as recited in claim 1, wherein an incoming signal comprises directional information and an indication of transmission power used by a neighboring node of the neighboring nodes to communicate the incoming signal.

5. A method as recited in claim 1, further comprising:

identifying a particular cone of degree α

that is within a boundary node'"'"'s transmission radius that is not covered by at least one other node of the nodes, α

being less than or equal to 5π

/6; and

decreasing the boundary node'"'"'s transmission radius to exclude other nodes of the nodes that were acquired within the boundary node'"'"'s transmission radius as part of an attempt to communicate with a nodes of the nodes in the particular cone.

6. A method as recited in claim 1, further comprising:

detecting a change in topology of the wireless multi-hop network by a first node of the nodes, the change corresponding to a second node of the nodes entering or leaving a radius of coverage corresponding to the first node; and

responsive to detecting the change, dynamically reconfiguring the at least one subset of nodes with which the first node maintains communications to provide collective connectivity between each of the nodes in a manner that reflects the change.

7. A method as recited in claim 1, further comprising removing a special edge from the wireless multi-hop network, an edge being a communication pathway between two nodes of the nodes, and wherein an edge is a special edge if:

(a) a first node of the at least two nodes is inside of a first transmission radius that corresponds to a second node of the at least two nodes; and

(b) the second node is outside of a second transmission radius that corresponds to the first node.

8. A method as recited in claim 1, wherein discovering the neighboring nodes further comprises:

broadcasting the outgoing signal in all directions at a portion of a substantially optimal termination power;

receiving the incoming signals; and

wherein making the respective decision further comprises;

determining whether a predetermined criteria has been met; and

responsive to determining that the predetermined criteria has not been met;

(a) increasing the portion by a quantum;

(b) re-broadcasting the outgoing signal at the portion;

(c) receiving a set of incoming signals;

(d) determining whether the predetermined criteria has been met; and

(e) responsive to determining that the predetermined criteria has not been met, repeating (a) through (e) until either the predetermined criteria is met or until the portion reaches the substantially optimal termination power.

9. A method as recited in claim 8, wherein the substantially optimal termination power is less than or equal to a node'"'"'s maximum transmission power.

10. A method as recited in claim 8, wherein the predetermined criteria is based on identifying at least one node of the neighboring nodes within each of a plurality of cones of degree α

, each cone being centered on the respective node and spanning a degree of α

/2 on each side of the at least one node, the cones collectively spanning 2π

degrees around the respective node.

11. A method as recited in claim 10, wherein α

≦

5π

/6.

12. A method as recited in claim 1, wherein an edge is a communication pathway between at least two nodes of the nodes, wherein connectivity in the multi-hop network is represented by a plurality of edges in a topological graph, and wherein the method further comprises removing a redundant edge from the wireless multi-hop network.

13. A method as recited in claim 12, wherein removing the redundant edge further comprises:

assigning each edge (u, v) an edge ID as represented by;

eid(u, v) =(i₁, i₂, i₃),

where i₁=d(u, v), i₂=max(node IDs of u and v), and i₃=min(node IDs of u and v); and

comparing edge IDs based on lexicographical order, wherein given any θ

≦

π

/3 and given any pair of edges (u, v) and edges (u, w) such that angle vuw<

θ

, a communication pathway between nodes (u, v) is a redundant edge if a first edge ID of (u, v) is greater than a second edge ID (u, w).

15. A computer-readable medium as recited in claim 14, wherein collectively each respective decision provides substantially complete connectivity between the nodes in a power efficient manner.

16. A computer-readable medium as recited in claim 14, wherein an incoming signal comprises directional information.

17. A computer-readable medium as recited in claim 14, wherein an incoming signal comprises directional information and an indication of transmission power used by a neighboring node of the neighboring nodes to communicate the incoming signal.

18. A computer-readable medium as recited in claim 14, wherein the computer-executable instructions further comprise instructions for:

detecting a change in topology of the wireless multi-hop network by a first node of the nodes, the change corresponding to a second node of the nodes entering or leaving a radius of coverage corresponding to the first node; and

responsive to detecting the change, dynamically reconfiguring the at least one subset of nodes with which the first node maintains communications to provide collective connectivity between each of the nodes in a manner that reflects the change.

19. A computer-readable medium as recited in claim 14, wherein the computer-executable instructions further comprise instructions for:

identifying a particular cone of degree α

that is within a boundary node'"'"'s transmission radius that is not covered by at least one other node of the nodes, α

being less than or equal to 5π

/6; and

decreasing the boundary node'"'"'s transmission radius to exclude other nodes of the nodes that were acquired within the boundary node'"'"'s transmission radius as part of an attempt to communicate with a nodes of the nodes in the particular cone.

20. A computer-readable medium as recited in claim 14, further comprising instructions for removing a special edge from the wireless multi-hop network, an edge being a communication pathway between at least two nodes of the nodes, and wherein an edge is a special edge if:

(a) a first node of the at least two nodes is inside of a first transmission radius that corresponds to a second node of the at least two nodes; and

(b) the second node is outside of a second transmission radius that corresponds to the first node.

21. A computer-readable medium as recited in claim 14, wherein the instructions for discovering the neighboring nodes further comprise instructions for:

broadcasting the outgoing signal in all directions at a portion of a substantially optimal termination power;

receiving the incoming signals; and

wherein making the respective decision further comprises;

determining whether a predetermined criteria has been met; and

responsive to determining that the predetermined criteria has not been met;

(a) increasing the portion by a quantum;

(b) re-broadcasting the outgoing signal at the portion;

(c) receiving a set of incoming signals;

(d) determining whether the predetermined criteria has been met; and

(e) responsive to determining that the predetermined criteria has not been met, repeating (a) through (e) until either the predetermined criteria is met or until the portion reaches the substantially optimal termination power.

22. A computer-readable medium as recited in claim 21, wherein the substantially optimal termination power is less than or equal to a node'"'"'s maximum transmission power.

23. A method as recited in claim 21, wherein the predetermined criteria is based on identifying at least one node of the neighboring nodes within each of a plurality of cones of degree α

, each cone being centered on the respective node and spanning a degree of α

/2 on each side of the at least one node, the cones collectively spanning 2π

degrees around the respective node.

24. A computer-readable medium as recited in claim 23, wherein α

≦

5π

/6.

25. A computer-readable medium as recited in claim 14, wherein an edge is a communication pathway between at least two nodes of the nodes, wherein connectivity in the multi-hop network is represented by a plurality of edges in a topological graph, and wherein the computer-executable instructions further comprise instructions for removing a redundant edge from the wireless multi-hop network.

26. A computer-readable medium as recited in claim 25, wherein the computer-executable instructions for removing the redundant edge further comprises instructions for:

assigning each edge (u, v) an edge ID as represented by;

eid(u, v)=(i₁, i₂, i3),

where i₁=d(u, v), i₂=max(node IDs of u and v), and i₃=min(node IDs of u and v); and

comparing edge IDs based on lexicographical order, wherein given any θ

≦

π

/3 and given any pair of edges (u, v) and edges (u, w) such that angle vuw<

θ

, a communication pathway between nodes (u, v) is a redundant edge if a first edge ID of (u, v) is greater than a second edge ID (u, w).

28. A computing device as recited in claim 27, wherein collectively each respective decision provides substantially complete connectivity between the nodes in a power efficient manner.

29. A computing device as recited in claim 27, wherein an incoming signal comprises directional information.

30. A computing device as recited in claim 27, wherein an incoming signal comprises directional information and an indication of transmission power used by a neighboring node of the neighboring nodes to communicate the incoming signal.

31. A computing device as recited in claim 27, wherein the computer-executable instructions further comprise instructions for:

detecting a change in topology of the wireless multi-hop network by a first node of the nodes, the change corresponding to a second node of the nodes entering or leaving a radius of coverage corresponding to the first node; and

responsive to detecting the change, dynamically reconfiguring the at least one subset of nodes with which the first node maintains communications to provide collective connectivity between each of the nodes in a manner that reflects the change.

32. A computing device as recited in claim 27, wherein the computer-executable instructions further comprise instructions for:

identifying a particular cone of degree α

that is within a boundary node'"'"'s transmission radius that is not covered by at least one other node of the nodes, α

being less than or equal to 5π

/6; and

decreasing the boundary node'"'"'s transmission radius to exclude other nodes of the nodes that were acquired within the boundary node'"'"'s transmission radius as part of an attempt to communicate with a nodes of the nodes in the particular cone.

33. A computing device as recited in claim 27, further comprising instructions for removing a special edge from the wireless multi-hop network, an edge being a communication pathway between at least two nodes of the nodes, and wherein an edge is a special edge if:

(a) a first node of the at least two nodes is inside of a first transmission radius that corresponds to a second node of the at least two nodes; and

(b) the second node is outside of a second transmission radius that corresponds to the first node.

34. A computing device as recited in claim 27, wherein the instructions for discovering the neighboring nodes further comprise instructions for:

broadcasting the outgoing signal in all directions at a portion of a substantially optimal termination power;

receiving the incoming signals; and

wherein making the respective decision further comprises;

determining whether a predetermined criteria has been met; and

responsive to determining that the predetermined criteria has not been met;

(a) increasing the portion by a quantum;

(b) re-broadcasting the outgoing signal at the portion;

(c) receiving a set of incoming signals;

(d) determining whether the predetermined criteria has been met; and

(e) responsive to determining that the predetermined criteria has not been met, repeating (a) through (e) until either the predetermined criteria is met or until the portion reaches the substantially optimal termination power.

35. A computing device as recited in claim 34, wherein the substantially optimal termination power is less than or equal to a node'"'"'s maximum transmission power.

36. A computing device as recited in claim 35, wherein the predetermined criteria is based on identifying at least one node of the neighboring nodes within each of a plurality of cones of degree α

, each cone being centered on the respective node and spanning a degree of α

/2 on each side of the at least one node, the cones collectively spanning 2π

degrees around the respective node.

37. A computing device as recited in claim 36, wherein α

≦

5π

/6.

38. A computing device as recited in claim 27, wherein an edge is a communication pathway between at least two nodes of the nodes, wherein connectivity in the multi-hop network is represented by a plurality of edges in a topological graph, and wherein the computer-executable instructions further comprise instructions for removing a redundant edge from the wireless multi-hop network.

39. A computing device as recited in claim 38, wherein the computer-executable instructions for removing the redundant edge further comprise instructions for:

assigning each edge (u, v) an edge ID as represented by;

eid(u, v)=(i₁, i₂, i₃),

where i₁=d(u, v), i₂=max(node IDs of u and v), and i₃=min(node IDs of u and v); and

comparing edge IDs based on lexicographical order, wherein given any θ

≦

π

/3 and given any pair of edges (u, v) and edges (u, w) such that angle vuw<

θ

, a communication pathway between nodes (u, v) is a redundant edge if a first edge ID of (u, v) is greater than a second edge ID (u, w).

14. A computer-readable medium comprising computer-executable instructions providing topology control to a distributed wireless multi-hop network comprising a plurality of nodes, the computer-executable instructions comprising instructions for:

for each node, discovering a set of neighboring nodes of the nodes using a set of incoming signals from the neighboring nodes, the incoming signals being responsive to receipt by the neighboring nodes of an outgoing signal from a respective node of the nodes;

for each node, making a respective decision about a substantially optimal transmission power to communicate with at least one subset of the neighboring nodes, the respective decision being based on the incoming signals and being independent of positional information;

for each node, maintaining communications with the at least one subset to provide connectivity between each of the nodes.

27. A computing device comprising:

a memory comprising computer-executable instructions for providing location-based topology control to a wireless multi-hop network comprising a plurality of nodes;

a processor that is operatively coupled to the memory, the processor being configured to fetch and execute the computer-executable instructions from the memory, the computer-executable instructions comprising instructions for;

for each node, discovering a set of neighboring nodes of the nodes using a set of incoming signals from the neighboring nodes, the incoming signals being responsive to receipt by the neighboring nodes of an outgoing signal from a respective node of the nodes;

for each node, making a respective decision about a substantially optimal transmission power to communicate with at least one subset of the neighboring nodes, the respective decision being based on the incoming signals and being independent of positional information;

for each node, maintaining communications with the at least one subset to provide connectivity between each of the nodes.