Abstract:
A data communications system, e.g. for &#34;hands free&#34; personnel location or access control, comprises a master transceiver and a plurality of slave transceivers for transmitting individual identification messages to the master in accordance with a code in which binary values are represented by an infra-red transmission occuring during a first portion or a second portion of a bit period respectively. The master alternately echoes back to the slaves a binary value corresponding to the value last received. In the event of a clash, however, i.e. different values transmitted from different slaves during the same bit period, the master echoes back only a predetermined single value and the slave(s) which did not transmit that value then cease transmission. This process continues until one of the slaves has transmitted and had echoed back bit-by-bit the whole of its message. That slave then ceases transmission and the remaining slaves recommence until by repetition of the process all of the individual slave messages have been transmitted and echoed back.

Description:
BACKGROUND 
     The present invention relates to data communications and more particularly concerns a communication protocol designed to resolve clashes in a system where a plurality of separate devices (termed herein &#34;slaves&#34;) may attempt to communicate simultaneously with another device (termed herein &#34;master&#34;) over a common communication channel. 
     One field of &#34;master and slaves&#34; communication with which the invention is particularly concerned is a so-called &#34;hands-free&#34; access control system. In such a system the &#34;slaves&#34; comprise individual tokens worn or carried by different persons and capable of trasmitting respective identifiction codes to &#34;master&#34; control units associated with doorways in a building, when in the vicinity thereof, so that a control unit can determine if an approaching person is authorised to pass through without requiring the person to request access by means of a specific manipulative action. A similar system can be used for monitoring the whereabouts of persons within a building, e.g. patients within a hospital, where each wears a &#34;slave&#34; token the transmissions of which are received by &#34;master&#34; control units distributed throughout the institution and linked to a central monitoring station. Systems such as these can operate through a variety of communications media, including by way of infra-red, ultrasonic or radio emissions, or inductive or capacitative coupling techniques. In principle, however, the invention is not restricted to any particular field of application or communications medium, and may be found of general utility in resolving clashes between simultaneous slave-to-master transmissions in wireless or wired data communication environments. 
     Assuming that data is transmitted in binary form, the communication protocol employed in any such system must enable the simultaneous reception of a &#34;0&#34; and a &#34;1&#34; from different slave transmitters to be recognize and resolved. Furthermore, the reception of a &#34;0&#34; or a &#34;1&#34; must still be reliably achieved if a number of slaves simultaneously transmit that same value. The protocol of the present invention is based upon binary coding having the characteristics of the known Manchester II code. In Manchester II code the values &#34;0&#34; and &#34;1&#34; are distinguished not by different high and low logic levels but by the position of a high logic level in either the first half or the second half of a defined bit period. There is therefore a logic transition at the middle of each bit period, the binary value of data being represented by the direction the transition. By way of example, the accompanying FIG. 1 is a representation of the word &#34;10110&#34; in the Manchester II code where a &#34;0&#34; is represented by a high level in the first half of a bit period and a &#34;1&#34; is represented by a high level in the second half; (of course in any particular implementation the definitions of a &#34;0&#34; and a &#34;1&#34; could be exchanged if desired). If such a coding scheme is to be used in a system where two or more slaves transmit different data simultaneously over the same communication channel it will be appreciated that when both a &#34;0&#34; and a &#34;1&#34; are transmitted by different slaves in the same bit period the signal received by the master will be a high level throughout that period and that in the absence of some means of resolving the clash the data will be unreadable. It is to the resolution of such clashing transmissions that the present invention is directed. 
     SUMMARY OF THE INVENTION 
     Accordingly the invention resides in a data communication system comprising a master transceiver and a plurality of slave transceivers for transmitting respective messages to the master transceiver in accordance with a code in which binary values are represented by a specified logic level occurring during a first portion or a second portion of a bit period respectively; means for synchronizing the operation of the transceivers such that said slave transceivers transmit the first bit of their respective messages simultaneously and the transmission of bits then alternates between the master and slave transceivers; the master transceiver being adapted to transmit back to the slave transceivers a binary value corresponding to the value last received when it receives only a single binary value (from any number of said slave transceivers) in the preceding bit period, and to transmit back to the slave transceivers a predetermined single binary value when it receives both binary values in the preceding bit period; each slave transceiver being adapted to transmit the next successive bit of its respective message when the last binary value received from the master transceiver corresponds to the preceding bit of its message, but to cease transmission until a subsequent instruction from the master transceiver when the last binary value received from the master transceiver does not so correspond. 
     In this way clashes between the slave messages are in effect resolved by the master transceiver arbitrarily reading the simultaneous reception of both a &#34;0&#34; and a &#34;1&#34; as only one of those values, say a &#34;1&#34;, and returning that value to the slave transceivers. By monitoring the master&#39;s transmissions, the slaves know which value has been read by the master and if it was not the one which a particular slave last sent then that slave will cease transmitting. The process will continue bit by bit until only one slave message remains transmitting. The successful slave, knowing that its entire message has been received by monitoring its echo from the master can then remain silent while the whole process is repeated and the other slave messages are received one by one. 
     An example of the operation of this protocol within a data communication system according to the invention will now be described with reference to FIGS. 2 to 4 of the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a diagram exemplifying the known Manchester II code; 
     FIG. 2 is a schematic plan view of an environment in which the invention may be utilised; 
     FIG. 3 is a transmission diagram of the data exchange occurring in the example of FIG. 2; 
     FIG. 4 illustrates a modified transmission scheme. 
    
    
     DETAILED DESCRIPTION 
     For the purposes of illustration the invention will be described hereinafter in the context of a &#34;hands-free&#34; access control or personnel location system. In this system the persons occupying a particular building each wear a &#34;slave&#34; identification token including a microprocessor programmed with an individual identification code and an infra-red emitter and detector for two-way communication with &#34;master&#34; control or monitoring units distributed throughout the building. Data exchange between the tokens and control units is by way of a binary coding in which a &#34;0&#34; is represented by an infra-red transmission during the first half of a bit period and a &#34;1&#34; is represented by an infra-red transmission during the second half of a bit period. The intention is that each token within range of any control unit should signal its presence by transmitting its individual identification code. Clearly, since there may be any number of tokens within range of a control unit at any one time it is necessary for the communication protocol employed to be capable of resolving clashes between the simultaneous transmissions of different tokens. 
     In the example of FIG. 2, two persons 1 and 2 are seen approaching a doorway 3 in a building and each wears an individually-coded identification token A, B respectively. Associated with the doorway 3 is a control unit M for reading the codes of the tokens worn by persons in its vicinity and relaying these codes to a central monitoring station from which the whereabouts of the respective persons can be identified at any time. The control unit M may additionally or alternatively perform the function of permitting or denying access through the doorway 3 by controlling the locking of its door in accordance with the level of authorisation associated with the identification codes which it reads. 
     A session of communication commences with the control unit M (i.e. &#34;master&#34;) broadcasting a predefined signal which is interpreted by the tokens (i.e. &#34;slaves&#34;) which are within its range as an invitation to commence transmission of their identification.. codes. This signal also includes information whereby synchronization of the subsequent data exchanges is maintained. In the simple example depicted in FIGS. 2 and 3 there are only two tokens in range, i.e. slave A and slave B, each with a four-bit code to transmit, say &#34;1010&#34; for slave A and &#34;1001&#34; for slave B. Consequently, on receipt of the invitation signal from the master, both slaves simultaneously transmit the respective first bits of their identification codes, which in this case are both a &#34;1&#34;. The master listens for the transmissions from the slaves following its invitation signal and, depending on the compositions of the codes of the slaves in range, it may receive a signal only in the first half of the bit period (i.e. any number of slaves all sending a &#34;0&#34;), a signal only in the second half of the bit period (i.e. any number of slaves all sending a &#34;1&#34;) or a signal in both halves of the bit period (i.e. two or more slaves, some sending a &#34;0&#34; and some sending a &#34;1&#34;). In addition, if no slave is in range the master will receive no transmission at all. The master responds by transmitting a signal in the next bit period determined in accordance with the following rules: 
     
         ______________________________________If a &#34;0&#34; is received:   Send a &#34;0&#34;If a &#34;1&#34; is received:   Send a &#34;1&#34;If both a &#34;0&#34; and a &#34;1&#34; are received:                   Send a &#34;1&#34;If nothing is received: Send another                   invitation                   signal.______________________________________ 
    
     In the illustrated example, since both slaves A and B have sent a &#34;1&#34; in bit period 1 the master responds by echoing back a &#34;1&#34; in bit period 2. The slaves all monitor this transmission. If the value they receive back is the one they sent, they proceed to send the next bit of their message. If not, they cease transmission. This means that where two messages differ in a particular bit, the slave(s) which sent a &#34;1&#34; will continue and those which sent a &#34;0&#34; will cease. In the illustrated example, since both slaves A and B received back their first &#34;1&#34; they proceed to transmit their respective second bits in bit period 3, which in this case are both a &#34;0&#34;. Accordingly this &#34;0&#34; is echoed back by the master in bit period 4 and the two slaves continue with.the transmission of their next respective bits. 
     The third bits of slaves A and B differ, however, so that in bit period 5 the master receives a signal in both halves of the period. This it recognizes as a clash and in accordance with the above rules reads this transmission as a &#34;1&#34; and transmits back a &#34;1&#34; in bit period 6. Slave A recognizes this as the same value as it transmitted in the preceding bit period and accordingly proceeds with the transmission of its final bit. Slave B, however, does not recognize this as the same value as it transmitted in the preceding bit period and accordingly it ceases transmission. Since the only value which the master received in bit period 7 was a &#34;0&#34; it accordingly echoes this back in bit period 8. 
     At the end of eight bit periods, therefore, the master will have received, and echoed back, the complete identification code of slave A. Having read this code the master issues a confirmation signal. This is interpreted by all the other slaves in range as a fresh invitation to commence transmitting their identification codes--which in the case of the illustrated example proceeds for slave B as shown in the second block of eight bit periods. Slave A, however, having had its complete message echoed back by the master knows that it has accomplished a successful exchange and remains silent for the remainder of the session; otherwise, of course, its message would again be read in preference to that of slave B. When slave B&#39;s message has itself been received and echoed back by the master it issues another confirmation signal. If there are no other slaves in range the master considers the session to be closed and thereafter issues a fresh invitation signal, whereupon the whole process is repeated with whatever slaves are then in range. To avoid unnecessary repetition of identification codes from a slave to the same master in successive sessions the slaves may be programmed not to retransmit to the same master within a predetermined time from its last complete transmission, the invitation codes from different masters themselves being coded to enable a slave to identify when it moves into range of a new master. 
     The example depicted in FIG. 3 is of course a very simple illustration of a system in accordance with the invention. In other situations and embodiments of the invention there may be a large number of potential slaves communicating with a master in any one session, each having an identification code comprising many more bits than four. The principles by which the protocol proceeds to resolve clashes between a greater number of longer slave messages remains precisely the same, however. Generally stated, with a series of slaves each wishing to transmit a different message N bits long, the above protocol ensures that after 2N bit periods the master will have received that message which, expressed as a binary number, is the largest; furthermore, the slave which sent that message will have had it echoed back from the master and will therefore know that it has been received successfully; during the next 2N bit periods the master will receive and echo back the message which is the next largest; and so on. In a practical embodiment each bit period may occupy approximately one millisecond, so that a communication session involving 10 slaves each with a message of, say, 88 bits long, together with the various invitation and confirmation signals, may take in the region of two seconds. 
     The system as so far described can be refined in several ways. Thus for example, let the invitation message from the master which initiates transmissions from the slaves contain a bit field large enough to represent a number from 0 to N-1, where N is the length of each slave message. The significance of this field is that if it represents the binary number M, then slave transmissions should start at bit M (the first bit being bit zero). The procedure starts as previously described, with M being set to zero. The master notes the bit number where the first clash occurs (i.e. a &#34;0&#34; and a &#34;1&#34; simultaneously received). Following successful reception of the first slave&#39;s message, the master then sends another initial message (confirmation signal) with M set equal to this value. It already knows that the bits 0 to M-1 of the messages from all the slaves were the same, and so can copy those from the message it has already received. It receives bits from M to N-1 as before, so receiving another slave&#39;s message after 2(N-M) bit periods. The procedure is then repeated until all messages have been received. The total time to receive all slave messages is much reduced by this scheme if the messages are long but only differ in the last few bits - which may be the case for identification codes in an access control system. 
     A variation of this is to note the bit position of the last clash, and to start retransmission from this point. If there are clashes in this attempt, the next start is made from the last clash. If not, the location of the most recent unresolved clash is used. This could be more efficient still, although requires more complex software. 
     With infra-red transmission particularly, continuous signals may be hard to detect due to interference from ambient light. To overcome this, a pulsed message could be sent rather than transmitting continuously for half of the bit period, as indicated in FIG. 4. Of course, many more than four pulses could be used. 
     If a long (or variable length) message is to be sent, the protocol can be refined by defining periods when the above scheme for resolving clashes is employed, and periods during which only a specific slave may transmit (and so there can be no clashes). These periods can be defined by the master, possibly in response to the initial message from a slave. Similarly, periods can be defined when the master is transmitting messages which are neither invitations for the slaves to transmit nor echoes of messages from the slaves. If this is done, care must be taken that these messages cannot be mistaken for invitations, for example by suitable encoding of the invitations. 
     An alternative method for sending variable length messages from a slave to the master is for the slave to cease transmitting after it has completed its message, and for the master to recognize this absence of a signal as indicating the end of the message. 
     Messages may contain a parity bit or checksum, to protect against errors in transmission. Alternatively (or in addition), a slave may have to send its message a number of times, with a certain number of successful receptions being necessary before the message is accepted by the master. As an alternative to this, data within the message could be protected by an error-correcting code such as the Golay code. 
     As a security feature, messages from the slaves could contain a bit field which is generated from the identification code of the individual slave and a message sent periodically by the master. The master would change this message from time to time. This would protect the system against compromise through the recording and retransmission of messages from a slave.