Inter-channel bridge node communications protocol for TDMA networks

• US 7,639,652 B1
• Filed: 09/28/2005
• Issued: 12/29/2009
• Est. Priority Date: 09/28/2005
• Status: Expired due to Fees

• Current Assignee: Rockwell Collins, Inc. (Rtx Corporation)
• Original Assignee: Rockwell Collins, Inc. (Rtx Corporation)
• Inventors: Creech, Lawrence C., Stevens, James A., Amis, Alan D., Parekh, Hersh B.
• Primary Examiner(s): Kincaid; Lester
• Assistant Examiner(s): Khan; Mehmood B
• Application Number:
  US11/237,636
• Time in Patent Office: 1,553 Days
• Field of Search: 370/28, 370/329, 370/256, 370/238, 370/400, 370/331, 370/335, 455/41.2, 455/445, 455/453, 455/450, 455/519, 709/228, 709/238, 709/239
• US Class Current: 370/337
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/14 Backbone network devices
• CPC Class Codes: H04W 92/02 Inter-networking arrangements

Abstract

An improved protocol for MANETs used in TDRS, JTRS systems and the like, where multiple channels have multiple communication links operating simultaneously within range of each other. All nodes in such MANETs are able to communicate with all their “1 hop” neighbors, even if the neighbors are on different channels. An improved inter-channel communication protocol using a bridge node allows nodes on separate channels to communicate. The bridge node operates as a pseudo-bi-directional link between two neighboring channels in the MANET. An Inter-Channel Bridge Node Communication Protocol determines contention free time slots on both channels, and then reserves one time slot to be used for inter-channel communications. The reserved time slot usage is then divided between the transmitted bridge node and the receiving node in the neighboring channel.

Claims

1. An inter-channel communications bridge node MANET architecture, comprising:

a plurality of nodes forming a first communications channel group (CG);

a plurality of nodes forming a second communications channel group (CG);

a software program run by a processor, said software program associated with each of said nodes;

at least one bridge node selected from said first and second communication channel groups (CGs) nodes by said program, said bridge node forming a bridge for communication between said nodes of said first and second channel groups;

said nodes of said first and second channel groups communicating with one another via said bridge node according to said software program, said plurality of first and second channel group nodes form a mobile ad-hoc network (MANET), said nodes from said first CG passing and receiving messages to and from said nodes from said second CG according to Time Division Multiple Access (TDMA) via said bridge node, each node having time slots in a time domain for TDMA, said bridge node is selected by said software program from “

1 hop”

neighboring nodes from said nodes in said first and second channel groups, said nodes in said first and second channel groups transmit messages at a predetermined periodicity according to said software program, said bridge node reserves a time slot in said TDMA for sending and receiving said messages from said first and second CGs, a plurality of Potential Bridge Nodes comprising “

1 hop”

neighboring nodes to said bridge node, said Potential Bridge Nodes having a plurality of time slots in the time domain for TDMA of said messages, said Potential Bridge time slots having idle slots suitable for transmission of inter-channel messages between said first and second CGs, said software program determines a common set of intersecting idle slots between said Potential Bridge Nodes time slots to reserve for inter-channel communication by said bridge node, said nodes in said first and second channel groups transmit bootstrap messages at a predetermined periodicity according to said software program; and

, based upon information from a Traffic Assigned Slots Record of the bridge node and further, based upon information from Bridge Assigned Slots Records of each of the bridge node'"'"'s one-hop neighboring nodes, said bridge node reserves a traffic slot in the time domain of said TDMA for sending and receiving said messages from said first and second CGs, prior to having a specific point-to-point destination for the messages, by taking ownership of a predetermined time domain traffic slot portion in said TDMA time domain and using a node ID of the bridge node as a bootstrap message destination node ID without specifying a point-to-point link in the bootstrap message, wherein a provisional parameter indicates a percent usage of said reserved traffic slot allocated by said bridge node for bi-directional communications to and from said bridge node.

2. The architecture according to claim 1, wherein:

said bridge node is selected from said nodes according to heuristic software of said software program.

3. The architecture according to claim 2, wherein:

said heuristic software selects said bridge node from said nodes in said first and second channel groups that are “

1 hop”

neighbors to one another.

4. The architecture according to claim 3, wherein:

said nodes in said first and second channel groups transmit bootstrap messages at a predetermined periodicity;

said heuristic software selects said bridge node from at least one candidate bridge node selected from said nodes in said first and second channel groups according to a set of rules, said rules selected from the group consisting of;

whether the candidate bridge node is already a bridge node to a neighboring Channel Group, said neighboring Channel Group being the Channel Group other than the Channel Group the candidate bridge node belongs to;

whether the candidate bridge node can hear the bootstrap message of nodes in a Channel Group other than the Channel Group the candidate bridge node belongs to;

or, whether the candidate bridge node is “

1 hop”

away from another active bridge node of said first and second Channel Group.

5. The architecture according to claim 4, wherein:

said heuristic software further selects said candidate node according to heuristic rules comprising;

the candidate bridge node has no existing “

good”

“

1 hop”

neighbor nodes of the same CG from said first and second CG that the candidate bridge node resides in, said “

good”

“

1 hop”

neighbors being bridge nodes to the other CG of said first and second CGs that the candidate bridge node resides in, wherein “

good”

refers to link quality sufficient to provide a predetermined level of bi-directional communication between two nodes, and,

said candidate bridge node has the lowest “

node ID”

within all its said “

good”

“

1 hop”

neighbors in the same CG the candidate bridge node resides in.

6. The architecture according to claim 1, wherein:

said bridge node is selected as a bridge node from said plurality of nodes and deselected as a bridge node according to a heuristic program performed by said software;

said heuristic program deselects said bridge node from said nodes in said first and second channel groups, so said bridge node is no longer a bridge node, according to heuristic rules comprising;

said bridge node no longer has any existing “

good”

“

1 hop”

neighbor nodes in the other CG to the CG said bridge node resides in, from said first and second CGs, wherein “

good”

refers to link quality sufficient to provide a predetermined level of bi-directional communication between two nodes, and,

said bridge node has more than “

N”

“

good”

“

1 hop”

neighbor nodes, in the existing CG said bridge node resides in, that are themselves bridge nodes to the other CG from said first and second CGs that the bridge node resides in, with “

N”

>

=1.

7. The architecture according to claim 1, wherein:

said software program ensuring all “

1 hop”

neighbor nodes, in the other CG to the CG said bridge node resides in, listen during the predetermined time domain of said traffic slot for messages from said bridge node.

8. The architecture according to claim 1, wherein:

said Potential Bridge Node time slots comprise traffic time slots and bridge time slots, each having idle slots;

wherein said software program determines said common set of intersecting idle slots by finding a set of Potential Bridge Node Idle Time Slots that are common to all said plurality of Potential Bridge Nodes traffic time slots and bridge time slots;

said bridge node having a plurality of traffic time slots having idle slots; and

,

said software program determining the idle slots according to TDMA for said bridge node inter-channel communication between CGs by finding the common idle slots between said Potential Bridge Node Idle Time Slots and said bridge node traffic idle time slots.

9. The architecture according to claim 1, wherein:

said bridge node is selected by said software program according to data received from said “

1 hop”

neighboring nodes from said nodes in said first and second channel groups;

said nodes in said first and second channel groups transmit messages at a predetermined periodicity according to said software program, each of said nodes having a plurality of time slots to communicate data according to said TDMA;

each of said nodes having a Bridge Neighbor List (BNL), stored by said software program, consisting of all “

1 hop”

neighboring nodes within each other of said first and second CGs that each of said nodes resides in, and the “

1 hop” and

“

2 hop”

neighbors of said neighboring nodes;

said software program determines said bridge node by selecting a node having the greater degree of connectivity according to each of said BNL.

10. The architecture according to claim 9, wherein:

each of said nodes in said CGs is identified by a channel group number (CGN), with said software program classifying said nodes by their CGN according to the intersection of said nodes BNL and the degree of common nodes shared by said nodes according to said BNL.

11. The architecture according to claim 10, wherein said program classifies said nodes according to each of said CGN as belonging to either a disjoint CG or a non-disjoint CG.

12. The architecture according to claim 11, wherein:

said program reserving in said bridge node time slot two time slots in the frame of said TDMA for communication between nodes that belong to two disjoint Channel Groups having the same CGN.

13. A method for an inter-channel communications bridge node MANET TDMA protocol, comprising the steps of:

providing a plurality of nodes forming a first communications channel group (CG);

providing a plurality of nodes forming a second communications channel group (CG);

said first and second channel groups form a mobile ad-hoc network (MANET), each of said nodes controlled by a software program run by a processor;

selecting at least one bridge node from said first and second communication channel groups, said bridge node forming a bridge between said first and second communication channel groups, wherein said bridge node is selected from “

1 hop”

neighboring nodes of said nodes in the first and second channel groups via the software program;

allowing communication of data between the nodes of said first and second communication channel groups via said bridge node during predetermined time slots via Time Division Multiple Access (TDMA);

transmitting messages to and from said nodes in said first and second channel groups at a predetermined periodicity according to said software program;

based upon information from a Traffic Assigned Slots Record of the bridge node and further, based upon information from Bridge Assigned Slots Records of each of the bridge node'"'"'s one-hop neighboring nodes, reserving in said bridge node a time slot in said TDMA for sending and receiving said messages from said first and second CGs;

having a plurality of Potential Bridge Nodes comprising “

1 hop”

neighboring nodes to said bridge node, said Potential Bridge Nodes being in the other CG to the CG of said bridge node, each of said Potential Bridge Nodes having a plurality of time slots in the time domain for TDMA of said messages, said Potential Bridge Nodes time slots having idle slots suitable for transmission of inter-channel messages between said first and second CGs;

determining with said software program a common set of intersecting idle slots between said Potential Bridge Nodes time slots to reserve for inter-channel communication by said bridge node;

transmitting bootstrap messages from said nodes in said first and second channel groups at a predetermined periodicity according to said software program;

reserving a traffic slot of said bridge node in the time domain of said TDMA for sending and receiving said messages to and from said first and second CGs, prior to having a specific point-to-point destination for said messages, by taking ownership of a predetermined time domain traffic slot portion in said TDMA time domain and using a node ID of the bridge node as a bootstrap message destination node ID without specifying a point-to-point link in the bootstrap message, wherein a provisional parameter indicates a percent usage of said reserved traffic slot allocated by said bridge node for bi-directional communications to and from said bridge node; and

having said software program ensure all “

1 hop”

neighbor nodes, in the other CG to the CG said bridge node resides in, listen during the predetermined time domain of said traffic slot for messages from said bridge node.

14. The method according to claim 13, further comprising the steps of:

selecting said bridge node using said software program that is heuristic;

selecting said bridge node from at least one candidate bridge node from the nodes in said first and second channel groups that are “

1 hop”

neighbors of one another, using said heuristic program according to a set of rules comprising the steps of;

determining whether the candidate bridge node is already a bridge node to a neighboring Channel Group, said neighboring Channel Group being the Channel Group other than the Channel Group the candidate bridge node belongs to;

determining whether the candidate bridge node can hear the bootstrap message of nodes in a Channel Group other than the Channel Group the candidate bridge node belongs to; and

,

determining whether the candidate bridge node is “

1 hop”

away from another active bridge node of said first and second Channel Group.

15. The method according to claim 14, further comprising the steps of:

selecting said bridge node from at least one candidate node using said heuristic program according to a set of rules comprising the steps of;

determining whether the candidate bridge node is already a bridge node to the candidate bridge node has no existing “

good”

“

1 hop”

neighbor nodes of the same CG from said first and second CG that the candidate bridge node resides in, said “

good”

“

1 hop”

neighbors being bridge nodes to the other CG of said first and second CGs that the candidate bridge node resides in, wherein “

good”

refers to link quality sufficient to provide a predetermined level of bi-directional communication between two nodes, and,

determining which candidate bridge node has the lowest “

node ID”

within all its said “

good”

“

1 hop”

neighbors in the same CG the candidate bridge node resides in.

16. The method according to claim 13, further comprising the steps of:

selecting and deselecting said bridge node using said software program that is heuristic;

deselecting said bridge node from said plurality of nodes according to said heuristic program performed by said software, using said heuristic program according to a set of rules comprising the steps of;

ascertaining whether said bridge node no longer has any existing “

good”

“

1 hop”

neighbor nodes in the other CG to the CG said bridge node resides in, from said first and second CGs, wherein “

good”

refers to link quality sufficient to provide a predetermined level of bi-directional communication between two nodes, and,

deselecting said bridge node if said bridge node has more than “

N”

“

good”

“

1 hop”

neighbor nodes, in the existing CG said bridge node resides in, that are themselves bridge nodes to the other CG from said first and second CGs that the bridge node resides in, with “

N”

>

=1.

17. The method according to claim 13, wherein:

said Potential Bridge Node time slots comprise traffic time slots and bridge time slots, each having idle slots;

determining said common set of intersecting idle slots by idle slots that are common to all said plurality of Potential Bridge Notes traffic time slots and bridge time slots, using said software program, comprising Potential Bridge Node Idle Time Slots;

said bridge node having a plurality of traffic time slots having idle slots; and

,

determining with said software program the idle slots for TDMA for said bridge node inter-channel communication between CGs by finding the common idle slots between said Potential Bridge Node Idle Time Slots and said bridge node traffic idle time slots.

18. The method according to claim 13, further comprising the steps of:

selecting said bridge node by said software program according to data received from said “

1 hop”

neighboring nodes from said nodes in said first and second channel groups;

transmitting messages from said nodes in said first and second channel groups at a predetermined periodicity according to said software program, each of said nodes having a plurality of time slots to communicate data according to TDMA;

storing each of said nodes Bridge Neighbor List (BNL), via by said software program, consisting of all “

1 hop”

neighboring nodes within the other of said first and second CGs that each of said nodes resides in, and the “

1 hop” and

“

2 hop”

neighbors of said neighboring nodes;

determining said bridge node by selecting a node having the greater degree of connectivity according to each of said BNL.

19. The method according to claim 18, further comprising the steps of:

identifying each of said nodes in said CGs by a channel group number (CGN), with said program classifying said nodes by their CGN according to the intersection of said nodes BNL and the degree of common nodes shared by said nodes according to said BNL.

20. The method according to claim 19, wherein said program classifies said nodes according to each of said CGN as belonging to either a disjoint CG or an non-disjoint CG.

21. The method according to claim 20, wherein:

reserving in said bridge node time slot two time slots in the frame of TDMA for communication between nodes that belong to two disjoint Channel Groups having the same CGN.

22. A MANET architecture comprising:

means forming a first communications channel (CC) comprising a first plurality of nodes;

means forming a second communications channel (CC) comprising a second plurality of nodes;

means for bridging said first and second communication channels;

said means for bridging comprising at least one node selected from said first and second CC;

said first and second CC means communicating with one another via said bridging means;

means for processing associated with said first and second CC means;

said means for processing is programmable with a software program, said software program controlling said first and second CC means to pass and receive data to each other according to Time Division Multiple Access (TDMA);

wherein,

said software program controls the selection of said bridging node, and selects said bridging node from said first and second plurality of nodes of said first and second CC means that are “

1 hop”

neighbors to one another;

said plurality of nodes forming a mobile ad-hoc network (MANET);

said nodes of said first and second CC means transmit bootstrap messages,

said bridging node reserves a slot in said TDMA for communication to and from said first and second CC means,

said software program transmitting bootstrap messages from said nodes in said first and second channel groups at a predetermined periodicity;

based upon information from a Traffic Assigned Slots Record of the bridge node and further, based upon information from Bridge Assigned Slots Records of each of the bridge node'"'"'s one-hop neighboring nodes, said software program reserving a traffic slot of said bridge node in the time domain of said TDMA for sending and receiving said messages to and from said first and second CC means, prior to having a specific point-to-point destination for said messages, by taking ownership of a predetermined time domain traffic slot portion in said TDMA time domain of said bridge node and using a node ID of the bridge node as a bootstrap message destination node ID without specifying a point-to-point link in the bootstrap message, wherein a provisional parameter indicates a percent usage of said reserved traffic slot allocated by said bridge node for bi-directional communications to and from said bridge node;

said software program ensures all “

1 hop”

neighbor nodes, in the other CC to the CC said bridge node resides in, listen during the predetermined time domain of said traffic slot for messages from said bridge node,

said nodes of said first and second CC means transmit bootstrap messages, said bridging node reserves a slot in said TDMA for communication to and from said first and second CC means,

said software program transmitting bootstrap messages from said nodes in said first and second channel groups at a predetermined periodicity;

a plurality of Potential Bridge Nodes comprising said “

1 hop”

neighboring nodes to said bridge node, said Potential Bridge Nodes being in the other CC to the CC of said bridge node, each of said Potential Bridge Nodes having a plurality of time slots in the time domain for TDMA of said messages, said Potential Bridge time slots having idle slots suitable for transmission of inter-channel messages between said first and second CC means;

said software program determining a common set of intersecting idle slots between said Potential Bridge Nodes time slots to reserve for inter-channel communication by said bridge node.