Method of assigning communication links in a dynamic communication network

Claim 2

In a communication network including a plurality of communication nodes, each node having at least one communication transceiver adapted to form a communication link with a compatible communication transceiver at another of said nodes, a method of assigning communication links between transceivers at the nodes, said method comprising at each node the steps of: (a) storing a set of link assignment constraints; (b) designating a subset of the constraints as high priority constraints; (c) determining a set C of candidate nodes having an unassigned transceiver with which an unassigned transceiver at said each node is compatible to form a communication link; (d) determining a set L of possible links that satisfy the high priority subset of constraints and that can be formed by said unassigned transceiver at said each node and the unassigned transceivers at the candidate nodes in set C; (e) evaluating the possible links in set L to determine a set of link assignments in set L satisfying the greatest number of the stored set of constraints; and (f) assigning the links in accordance with the set of link assignments determined in step (e).

Claim 3

A method as claimed in claim 1, wherein the communication links include links within a plurality of communication link classes having different communication characteristics, said method further comprising performing steps (c) through (f) once for each class.

Claim 4

A method as claimed in claim 2, further comprising assigning selected transceivers for communication links of a selected one of the classes, assigning the selected class of links priority over links of other classes, and designating as one of the high priority constraints the assigning of all of the selected transceivers to links of the selected class, whereby if a selected transceiver is unassigned following the performing of step (d) for its class of links, a link of another class is broken, the transceivers from the broken link are added to set C, and steps (c) and (d) are repeated for that class of links.

Claim 5

A method as claimed in claim 1, wherein the communication nodes are earth orbiting communication satellites.

Claim 6

A method as claimed in claim 4, wherein step (d) includes determining whether the pairs of nodes forming each possible link are in line of sight with each other.

Claim 7

A method as claimed in claim 5, wherein step (d) further includes determining whether the transceivers forming each possible link are compatible to form a communication link.

Claim 8

A method as claimed in claim 4, wherein step (d) includes determining whether the transceivers forming each possible link are compatible to form a communication link.

Claim 9

A method as claimed in claim 4, wherein step (e) includes determining the set of links formed by the set of satellite pairs having the maximum expected time in line of sight.

Claim 10

A method as claimed in claim 8, wherein the set of satellite pairs having the maximum expected time in line of sight is determined by direct computation, assuming a spherical earth.

Claim 11

A method as claimed in claim 8, wherein the set of satellite pairs having the maximum expected time in line of sight is determined at time t for those satellite pairs having a common finite T max by determining the pairs of satellites that are closest together at time ##EQU2## where for each satellite pair T max is the maximum time over which the pair can remain in line of sight with each other.

Claim 12

A method as claimed in claim 1, wherein step (d) includes determining whether the transceivers forming each possible link are compatible to form a communication link.

Claim 13

A method as claimed in claim 1, wherein step (e) includes determining whether the set L includes a number of links sufficient for desired communication in the network, and if not, determining at least one existing link to be broken to provide additional unassigned transceivers and repeating steps (c) through (e).

Claim 14

A method as claimed in claim 1, further comprising: at each node at which a change of a link from the node occurs, broadcasting, to all the communication nodes with which said each node is forming a communication link, an update of the network topology as a result of the change, and repeating steps (c) through (f); and at each node at which a broadcast of an update of the network topology is received, repeating steps (c) through (f).

Claim 15

A method as claimed in claim 13, wherein following the broadcast of a first update of the network topology, each node waits a first preset time interval before repeating steps (c) through (f) to permit broadcasting of additional updates of the network topology.

Claim 16

A method as claimed in claim 14, further comprising repeating steps (c) through (f) at second preset time intervals.

Claim 17

A method as claimed in claim 14, wherein the first preset time interval is of a duration sufficient to permit receiving of any additional broadcasts of updates of the network topology resulting from the same topology change that resulted in the broadcast of the first update.

Claim 18

A method as claimed in claim 1, further comprising repeating steps (c) through (f) at preset time intervals.

Claim 19

In a communication network including a plurality of communication nodes, each node having at least one communication transceiver adapted to form a communication link with a compatible communication transceiver at another of said nodes, an apparatus for assigning communication links between transceivers at the nodes, said apparatus comprising at each node: means for storing a set of link assignment constraints; means for designating a subset of the constraints as high priority constraints; first determining means for determining a set C of candidate nodes having an unassigned transceiver with which an unassigned transceiver at said each node is compatible to form a communication link; second determining means for determining a set L of possible links that satisfy the high priority subset of constraints and that can be formed by said unassigned transceiver at said each node and the unassigned transceivers at the candidate nodes in set C; evaluating means for evaluating the possible links in set L to determine a set of link assignments in set L satisfying the greatest number of the set of constraints stored in said storing means; and assigning means for assigning the links in accordance with the set of link assignments determined by said evaluating means.

Claim 20

In a communication network including a plurality of communication nodes, each node having at least one communication transceiver adapted to form a communication link with a compatible communication transceiver at another of said nodes, an apparatus for assigning communication links between transceivers at the nodes, said apparatus comprising at each node: means for storing a set of link assignment constraints; means for designating a subset of the constraints as high priority constraints; first determining means for determining a set C of candidate nodes having an unassigned transceiver with which an unassigned transceiver at said each node is compatible to form a communication link; second determining means for determining a set L of possible links that satisfy the high priority subset of constraints and that can be formed by said unassigned transceiver at said each node and the unassigned transceivers at the candidate nodes in set C; evaluating means for evaluating the possible links in set L to determine a set of link assignments in set L satisfying the greatest number of the set of constraints stored in said storing means; and assigning means for assigning the links in accordance with the set of link assignments determined by said evaluating means.

Claim 21

Apparatus as claimed in claim 18, wherein said transceivers include transceivers capable of forming communication links of a plurality of communication link classes having different communication characteristics, said apparatus further comprising means for storing the assignments of selected transceivers for communication links of a selected one of the classes; means for storing the assignment of links to the selected class, the assigned links having priority over links of other classes; means for designating as one of the high priority constraints the assigning of all of the selected transceivers to links of the selected class; and means responsive to a selected transceiver remaining unassigned following the determining of the set L for breaking a link of another class to permit the transceivers from that link to be utilized with the unassigned selected transceivers to form a link of the selected class.

Claim 22

Apparatus as claimed in claim 18, wherein the communication nodes are earth orbiting communication satellites.

Claim 23

Apparatus as claimed in claim 20, wherein the second determining means includes means for determining whether the pairs of noes forming each possible link are in line of sight with each other.

Claim 24

Apparatus as claimed in claim 21, wherein the second determining means further includes means for determining whether the transceivers forming each possible link are compatible to form a communication link.

Claim 25

Apparatus as claimed in claim 20, wherein the second determining means includes means for determining whether the transceivers forming each possible link are compatible to form a communication link.

Claim 26

Apparatus as claimed in claim 20, wherein the evaluating means includes means for determining the set of links formed by the set of satellite pairs having the maximum expected time in line of sight.

Claim 27

Apparatus as claimed in claim 24, wherein the means for determining the set of satellite pairs having the maximum time in line of sight comprises means for directly computing the expected times in line of sight for the links of set L, assuming a spherical earth.

Claim 28

Apparatus as claimed in claim 24, wherein the means for determining the set of satellite pairs having the maximum expected time in line of sight comprises means for determining T max for the links of set L, and means for determining at time t the pairs of satellites that are closest together at time ##EQU3## for those satellite pairs having a common finite T max , where for each satellite pair T max is the maximum time over which the pair can remain in line of sight with each other.

Claim 29

Apparatus as claimed in claim 18, wherein the second determining means includes means for determining whether the transceivers forming each possible link are compatible to form a communication link.

Claim 30

Apparatus as claimed in claim 18, wherein the evaluating means includes means for determining whether the set L includes a number of links sufficient for desired communication in the network, and means responsive to a determination that the set L does not include a sufficient number of links for determining existing links to be broken to provide additional unassigned transceivers.

Claim 31

Apparatus as claimed in claim 18, further comprising: means responsive to a change of a link from the node for broadcasting, to all the communication nodes with which said each node is forming a communication link, an update of the network topology as a result of the change; and means responsive to receipt of a broadcast of an update of the network topology for activating said first determining means, said second determining means, said evaluating means, and said assigning means to provide an updated set of link assignments.

Claim 32

Apparatus as claimed in claim 29, wherein said responsive means includes a first timer for timing a preset time interval before activating, to permit broadcasting of additional updates of the network topology.

Claim 33

Apparatus as claimed in claim 30, further comprising a second timer for timing a second preset time interval; and means responsive to completion of timing of the second time interval for activating said first determining means, said second determining means, said evaluating means, and said assigning means to provide a new set of link assignments.

Claim 34

Apparatus as claimed in claim 30, wherein the first preset time interval is of a duration sufficient to permit receiving of any additional broadcasts of updates of the network topology resulting from the same topology change that resulting in activation of the first timer.

Claim 35

Apparatus as claimed in claim 29, further comprising a timer for timing a preset time interval; and means responsive to completion of timing of the time interval for activating said first determining means, said second determining means, said evaluating means, and said assigning means to provide a new set of link assignments.