Link layered communications network and method

• US 5,455,569 A
• Filed: 10/06/1994
• Issued: 10/03/1995
• Est. Priority Date: 03/25/1992
• Status: Expired due to Term

• Current Assignee: AES Corporation
• Original Assignee: AES Corporation
• Inventors: Sherman, Michael J., Tait, Timothy S.
• Primary Examiner(s): Yusko, Donald J.
• Assistant Examiner(s): Rinehart, Mark H.
• Application Number:
  US08/318,984
• Time in Patent Office: 362 Days
• Field of Search: 370/60.1, 370/92, 370/94.3, 370/95.1, 370/95.3, 455/18, 455/17, 455/53.1, 455/56.1, 455/54.1, 340/825.02, 340/825.52, 340/826, 340/825.54, 340/825.44
• US Class Current: 370/228
• CPC Class Codes: H04W 4/12 Messaging; Mailboxes; Announcements
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 80/02 Data link layer protocols

Abstract

A wireless, dynamically reconfigurable link layered communications network and method are disclosed. A destination transceiver such as, a central transceiver, has a unique, permanent identification with a predetermined numerical link layer level n. A plurality of remote transceivers each having a unique, permanent identification and a variable, stored numerical link layer x where x>n and x and n are integers and x-n-1 represents the number of remote transceivers through which a communication must pass to reach the destination transceiver. The variable, stored numerical link layer level of each remote transceiver is dependent upon the dynamic condition of the network at the time of message transmission from or through the particular remote transceiver.

Claims

1. A method for dynamically configuring a wireless communications network between and among a plurality of transceivers each having a unique, permanent identification and a variable, stored numerical link layer level, said method comprising the steps of:

(1) designating one of said transceivers as a central transceiver and assigning it a predetermined numerical link layer level n, and assigning to all other transceivers a maximal link layer level;

(2) transmitting a message from the central transceiver that includes its own unique, permanent identification and its link layer level;

(3) to each of said other transceivers that received the message from the central transceiver reassign a link layer level by incrementing by 1 the said link layer level included in the said received message, said reassigned link layer level being stored at each of said other transceivers;

(4) transmitting a status message from each such other transceiver reassigned a link layer level in Step 3, said status message being transmitted after the occurrence of a variable transmission delay for each such other transceiver and including each such other transceiver'"'"'s own unique, permanent identification and its link layer level assigned and stored in Step 3;

(5) to each such other transceivers that received the status message transmitted in the prior Step, and has not yet been reassigned a link layer level, reassign a link layer level by incrementing by 1 the said link layer level included in the said received message, the so reassigned link layer level being stored at each such other transceiver;

(6) transmitting a new status message from each transceiver reassigned a link layer level in the prior Step, said new status message being transmitted after a variable transmission delay and including each such other transceiver'"'"'s own unique, permanent identification and its link layer level assigned and stored in the prior Step;

(7) repeating Steps 5 and 6 until all of the other transceivers have been reassigned a link layer level.

2. The method of claim 1 further comprising the step of repeating steps (2) through (7) for at least some of the transceivers in said plurality of transceivers in response to a change in said wireless communications network, if change affects, either the then stored routing list or the stored link layer level of a remote transceiver.

3. The method of claim 1 further comprising the step of repeating steps (2) through (7) for at least some of the transceivers in said plurality of transceivers when the number of transceivers in said plurality of transceivers change.

4. The method of claim 1 further comprising the step of generating at each transceiver a list of the unique, permanent identifications of all transceivers from which a message was received.

5. The method of claim 1 further comprising the step of repeating steps (2) through (7)for at least some of the transceivers in said plurality of transceivers.

6. The method of claim 1 further comprising the step of repeating steps (2) through (7) for at least some of the transceivers in said plurality of transceivers at time intervals that are not longer than a predetermined time interval t.

7. A method for communicating over a wireless communication network comprising a central transceiver having a unique, permanent identification with a predetermined numerical link layer level n and a plurality of remote transceivers each having a unique, permanent identification and a variable, stored numerical link layer level x, where x>

n and x and n are integers and x-n-1 represents the number of remote transceivers through which a message must pass to reach the central transceiver, and each remote transceiver, such method comprising the steps of;

(1) transmitting a message from one of said remote transceivers having a stored numeric link layer level x, said message being addressed to the central transceiver if x=n+1, or to another remote transceiver having a link layer level x-1, if x>

n+1, said message constituting the unique permanent identification of the transmitting transceiver, its currently stored link layer level x, the unique permanent identification of the transceiver to which the message is addressed, and a content portion;

(2) receiving said message at the addressed transceiver;

(3) retransmitting the message received in Step 2 if the addressed transceiver is other than the central transceiver, but with said message addressed to a different transceiver having a link layer level less than that of the retransmitting transceiver and said retransmitted message including the unique permanent identification and the currently stored link layer level of the retransmitting transceiver; and

,

(4) repeating Steps 2 and 3 until the message is received by said central transceiver.

8. A wireless communication network comprising:

(A) a central transceiver having a unique, permanent identification with a predetermined numerical layer level n;

(B) a plurality of remote transceivers each having a unique, permanent identification and a variable, stored numerical link layer level x, where x>

n and x and n are integers and x-n-1 represents the number of remote transceivers through which a must be retransmitted to reach the central transceiver;

(C) means for transmitting a message from one of said remote transceivers having a stored numeric link layer level x, said message being addressed to the central transceiver if x=n+1, or to another remote transceiver having a link layer level less than or equal to x-1, if x>

n+1, said message constituting the unique permanent identification of the transmitting transceiver, its currently stored link layer level x, the unique permanent identification number of the central transceiver to which the message is addressed, and a content portion;

(D) means for receiving said message at the addressed transceiver; and

,

(E) means for retransmitting the received message, if the addressed transceiver is other than the central transceiver, to a different transceiver having a link layer level less than that of the

retransmitting addressed transceiver and said retransmitted message including the unique permanent identification and the currently stored link layer level of the retransmitting transceiver.

9. The wireless communication network of claim 8 further comprising means for changing the stored, variable link layer level x of an addressed transceiver in response to a change in the link layer level of a transceiver having a lower link layer level than said addressed transceiver and whose message has been received by said addressed transceiver.

10. The wireless communication network of claim 8 further comprising means for establishing a routing list of transceivers with which said one of said remote transceivers can communicate.

11. The wireless communication network of claim 10 further comprising means for sorting the routing list.

12. The wireless communication network of claim 11 wherein said routing list is sorted in ascending order by link layer level with the lowest link layer level at the top of the routing list.

13. The wireless communication network of claim 10 further comprising means for ordering the routing list at each remote transceiver in an order determined by the minimum of transceivers required to send a message from said remote transceiver to the central transceiver.

14. The wireless communication network of claim 9 wherein the stored, variable link layer level x is changed in response to a change in said wireless communication network, if said change affects, either the then stored routing list or the stored link layer level of a remote transceiver.

15. The wireless communication network of claim 9 wherein the stored, variable link layer level x is changed when the number of transceivers in said plurality of transceivers changes.

16. The wireless communication network of claim 9 wherein the stored, variable link layer level x is changed at time intervals that are not longer than a predetermined interval t.

17. A method for dynamically reconfiguring with or without operator intervention, transmission paths in a wireless communication network between a plurality of remote transceivers and a central transceiver comprising the steps of:

(A) Assigning to each remote transceiver a variable link layer level, x, and another permanent identification, and assigning to the central transceiver a fixed link layer level, 0, said link layer level x, being the minimum number of transmissions required to retransmit a message to reach said central transceiver,

(B) Providing each remote transceiver with means to determine its own link layer level, x, and create its own prioritized routing list that are both updated during every message reception by said remote transceiver, from data attached to such received messages, and;

(C) At any time, routing communications between the said central transceiver and any remote transceiver having a link layer order x, through x-1 transceivers having a descending link layer level, when sending a message to the central transceiver, and having an ascending link layer level when messages are sent in the reverse direction.

18. A method of claim 17 whereby the means for determining a remote transceiver'"'"'s link layer level and create its own routing list include:

(A) a data controller at each transceiver to format messages for transmission, and to include in each transmitted message the transceiver'"'"'s permanent identification and the link layer level of said transceiver at the time of the transmission;

(B) means to monitor the loop for other transceivers transmitted messages and acknowledgments and to transmit messages and acknowledgments;

(C) said data controller having embedded in it a software algorithm determining link layer level hierarchy in the system, and an updatable message priority routing list, by;

(i) comparing the link layer level of other transmitting transceivers whose messages have been received to its then current link layer level; and

,

(ii) adding to its routing list any such transmitting transceiver having a link layer level lower than its own link layer level; and

,

(iii) sorting the routing list by link layer level so that the top of the list includes the lowest link layer level of such other transmitting transceiver; and

,

(iv) resetting its own link layer level to be the lowest link layer level on the routing list plus one; and

,

(v) in the event that the routing list is empty, increment its own link layer level by one, then transmit a message, and repeat steps i to iv; and

,

(vi) in the event that an acknowledgment of message receipt is past due from a transmitting transceiver at the top of its routing list, delete said transmitting transceiver from the routing list, then repeat steps i to iv or step v.

19. A dynamically self reconfiguring wireless communication network comprising:

(A) a central transceiver having a unique permanent identification and a link layer level 0;

(B) a plurality of remote transceivers each having a unique, permanent identification and a variable link layer level, x, said link layer level x, being the minimum number of transmissions required to retransmit a message to reach said central transceiver; and

,

(C) data control and processing means at each remote transceiver to determine each transceiver'"'"'s own link layer level, x, and update at each transceiver a prioritized routing list.

20. A self reconfiguring wireless communication network as in claim 19, whereby each remote transceiver'"'"'s routing list and link layer level are updated upon each transmission received by said remote transceiver.