US Patent No. 10,973,085

POLARITY ASSIGNMENT IN A MULTI-HOP WIRELESS NETWORK


Patent No. 10,973,085
Issue Date April 06, 2021
Title Polarity Assignment In A Multi-hop Wireless Network
Inventorship Djordje Tujkovic, Mountain View, CA (US)
Assignee FACEBOOK, INC., Menlo Park, CA (US)

Claim of US Patent No. 10,973,085

1. A method comprising:determining a plurality of network nodes of a multi-hop wireless network, wherein each of the plurality of network nodes of the multi-hop wireless network comprises at least one array of beamforming antennae;
assigning a first bipartite-graph polarity to each network node in a first subset of network nodes in the plurality of network nodes;
assigning a second bipartite-graph polarity to each network node in a second subset of network nodes in the plurality of network nodes;
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; and
changing, responsive to a change in a topology of a multi-hop wireless network, the assigned bipartite-graph polarities of one or more of the plurality of network nodes based on an application of an Edge Bipartization (EBP) algorithm to the topology of the multi-hop wireless network, the Edge Bipartization algorithm configured to designate one or more wireless connections for removal, wherein the change in the topology comprises a change to a total number of network nodes and a total number of wireless connections in the multi-hop wireless network.