Polarity Assignment in a Multi-Hop Wireless Network

• US 20170196000A1
• Filed: 12/28/2016
• Published: 07/06/2017
• Est. Priority Date: 12/31/2015
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Tujkovic, Djordje
• Granted Patent: US 10,582,567 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/34 Signalling channels for network management communication
• CPC Class Codes: H04L 41/344 Out-of-band transfers
• CPC Class Codes: H04W 16/28 using beam steering
• CPC Class Codes: H04W 24/04 Arrangements for maintaining operational condition
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 84/10 Small scale networks; Flat hierarchical networks
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In one embodiment, a method includes determining a plurality of network nodes of a multi-hop wireless network, wherein each network node comprises an array of beamforming antennae; assigning to each network node in a first subset a first bipartite-graph polarity; assigning to each network node in a second subset a second bipartite-graph polarity; and configuring the multi-hop wireless network according to a bipartite-graph representation of the multi-hop wireless network. During first time slots network nodes of the first bipartite-graph polarity transmit to network nodes of the second bipartite-graph polarity and network nodes of the second bipartite-graph polarity receive from network nodes of the first bipartite-graph polarity. During second time slots that alternate with the first time slots, network nodes of the second bipartite-graph polarity transmit to network nodes of the first bipartite-graph polarity and network nodes of the first bipartite-graph polarity receive from network nodes of the second bipartite-graph polarity.

Claims

1. A method comprising:

determining a plurality of network nodes of a multi-hop wireless network, wherein each of the network nodes of the multi-hop wireless network comprises at least one array of beamforming antennae;

determining a first subset of the network nodes;

determining a second subset of the network nodes different from the first subset;

assigning to each network node in the first subset a first bipartite-graph polarity;

assigning to each network node in the second subset a second bipartite-graph polarity;

configuring the multi-hop wireless network according to a bipartite-graph representation of the multi-hop wireless network, wherein;

during first time slots;

network nodes of the first bipartite-graph polarity transmit to network nodes of the second bipartite-graph polarity; and

network nodes of the second bipartite-graph polarity receive from network nodes of the first bipartite-graph polarity; and

during second time slots that alternate with the first time slots;

network nodes of the second bipartite-graph polarity transmit to network nodes of the first bipartite-graph polarity; and

network nodes of the first bipartite-graph polarity receive from network nodes of the second bipartite-graph polarity.

2. The method of claim 1, wherein the method is executed in conjunction with installation of at least some of the network nodes of the multi-hop wireless network.

3. The method of claim 1, wherein the method is executed in response to a change in a topology of the multi-hop wireless network.

4. The method of claim 3, wherein the change comprises:

failure of one or more wireless connections between network nodes;

creation of one or more new wireless connections between network nodes;

addition of one or more new network nodes;

or

creation of one or more new wireless connections between network nodes in response to one or more changes to an interference measurement on the multi-hop wireless network.

5. The method of claim 1, further comprising adding one or more new network nodes to the multi-hop wireless network and assigning to each of the new network nodes the first bipartite-graph polarity or the second bipartite-graph polarity to conform the wireless multi-hop network to the bipartite-graph representation.

6. The method of claim 1, further comprising changing the assigned bipartite-graph polarities of one or more of the network nodes based on an application of:

an Odd Cycle Transversal (OCT) algorithm to a topology of the multi-hop wireless network;

or

an Edge Bipartization (EBP) algorithm to the topology of the multi-hop wireless network.

7. The method of claim 6, wherein the method is executed in conjunction with installation of at least some of the network nodes of the multi-hop wireless network.

8. The method of claim 6, wherein the method is executed in response to a change in a topology of the multi-hop wireless network.

9. The method of claim 8, wherein the change comprises:

failure of one or more wireless connections between network nodes;

creation of one or more new wireless connections between network nodes;

addition of one or more new network nodes;

or

creation of one or more new wireless connections between network nodes in response to one or more changes to an interference measurement on the multi-hop wireless network.

10. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

determine a plurality of network nodes of a multi-hop wireless network, wherein each of the network nodes of the multi-hop wireless network comprises at least one array of beamforming antennae;

determine a first subset of the network nodes;

determine a second subset of the network nodes different from the first subset;

assign to each network node in the first subset a first bipartite-graph polarity;

assign to each network node in the second subset a second bipartite-graph polarity;

configure the multi-hop wireless network according to a bipartite-graph representation of the multi-hop wireless network, wherein;

during first time slots;

network nodes of the first bipartite-graph polarity transmit to network nodes of the second bipartite-graph polarity; and

network nodes of the second bipartite-graph polarity receive from network nodes of the first bipartite-graph polarity; and

during second time slots that alternate with the first time slots;

network nodes of the second bipartite-graph polarity transmit to network nodes of the first bipartite-graph polarity; and

network nodes of the first bipartite-graph polarity receive from network nodes of the second bipartite-graph polarity.

11. The media of claim 10, wherein the software is operable to be executed in conjunction with installation of at least some of the network nodes of the multi-hop wireless network.

12. The media of claim 10, wherein the software is operable to be executed in response to a change in a topology of the multi-hop wireless network.

13. The media of claim 12, wherein the change comprises:

failure of one or more wireless connections between network nodes;

creation of one or more new wireless connections between network nodes;

addition of one or more new network nodes;

or

creation of one or more new wireless connections between network nodes in response to one or more changes to an interference measurement on the multi-hop wireless network.

14. The media of claim 10, wherein the software is further operable when executed to add one or more new network nodes to the multi-hop wireless network and assign to each of the new network nodes the first bipartite-graph polarity or the second bipartite-graph polarity to conform the wireless multi-hop network to the bipartite-graph representation.

15. The media of claim 10, wherein the software is further operable when executed to change the assigned bipartite-graph polarities of one or more of the network nodes based on an application of:

an Odd Cycle Transversal (OCT) algorithm to a topology of the multi-hop wireless network;

or

an Edge Bipartization (EBP) algorithm to the topology of the multi-hop wireless network.

16. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors being operable when executing the instructions to;

determine a plurality of network nodes of a multi-hop wireless network, wherein each of the network nodes of the multi-hop wireless network comprises at least one array of beamforming antennae;

determine a first subset of the network nodes;

determine a second subset of the network nodes different from the first subset;

assign to each network node in the first subset a first bipartite-graph polarity;

assign to each network node in the second subset a second bipartite-graph polarity;

configure the multi-hop wireless network according to a bipartite-graph representation of the multi-hop wireless network, wherein;

during first time slots;

network nodes of the first bipartite-graph polarity transmit to network nodes of the second bipartite-graph polarity; and

network nodes of the second bipartite-graph polarity receive from network nodes of the first bipartite-graph polarity; and

during second time slots that alternate with the first time slots;

network nodes of the second bipartite-graph polarity transmit to network nodes of the first bipartite-graph polarity; and

network nodes of the first bipartite-graph polarity receive from network nodes of the second bipartite-graph polarity.

17. The system of claim 16, wherein the processors are operable to execute the instructions in conjunction with installation of at least some of the network nodes of the multi-hop wireless network.

18. The system of claim 16, wherein the processors are operable to execute the instructions in response to a change in a topology of the multi-hop wireless network.

19. The system of claim 18, wherein the change comprises:

failure of one or more wireless connections between network nodes;

creation of one or more new wireless connections between network nodes;

addition of one or more new network nodes;

or

creation of one or more new wireless connections between network nodes in response to one or more changes to an interference measurement on the multi-hop wireless network.

20. The system of claim 16, wherein the processors are further operable when executing the instructions to add one or more new network nodes to the multi-hop wireless network and assign to each of the new network nodes the first bipartite-graph polarity or the second bipartite-graph polarity to conform the wireless multi-hop network to the bipartite-graph representation.