Multiplex communications – Communication over free space – Having a plurality of contiguous regions served by...
Reexamination Certificate
1999-07-30
2003-10-21
Patel, Ajit (Department: 2664)
Multiplex communications
Communication over free space
Having a plurality of contiguous regions served by...
C370S348000, C370S447000
Reexamination Certificate
active
06636494
ABSTRACT:
BACKGROUND OF THE INVENTION
The field of the invention is that of detecting and resolving collisions between packets in a system where a plurality of transmitters transmit data packets to a receiver by means of a random access protocol, for example by radio.
In the description below, the term “collision” is used to designate a receiver receiving at least two packets whose contents are superposed at least in part and that come from transmitters for which no indication makes it possible to distinguish between them at the receiver. Collision is detected by a conventional collision detection method: each packet transmitted by a transmitter includes not only a field of information bits, but also a field containing redundancy bits calculated on the basis of the information bits by means of a predefined algorithm. By way of example, the redundancy bits can be calculated on the basis of using a parity bit, a Hamming code, or a cyclic redundancy code (CRC), where use of a CRC is the most widespread. When a packet is received, the receiver calculates the redundancy bits on the basis of the information bits it has received and using the same algorithm as that which was used by the transmitter of the packet. If the comparison shows a match between the redundancy bits as received and as recalculated, then the packet is deemed to have been received without error, otherwise the packet is erroneous, and the error is assumed to be due to a collision.
The signal corresponding to the collision is constituted by superposing at least two packets, at least in part. Nevertheless, for the purposes of calculating redundancy bits, the receiver treats such superposition of packets as a single packet which is referred to below as the “resulting” packet, in which the information bit field and the redundancy bit field are defined as though only one packet was involved. The signal level of the bits in the resulting packet is the sum of the signal levels of the corresponding bits in the packets that have collided.
In the state of the art, the receiver does no more than detect that collision has taken place and it ignores the contents of the packets that have collided. Collision resolution is the subject of a communications protocol between the transmitter and the receiver.
An example of such a protocol is constituted by the Aloha protocol. On transmitting each packet, the transmitter starts a timer which it stops on receiving an acknowledgment for that packet from the receiver. If the acknowledgment has not been received when the timer times out, that means a collision might have happened, and the transmitter automatically retransmits the same packet after a random length of time has elapsed.
Such a communications protocol is generally implemented in a radio network while a mobile terminal is requesting connection to the network. At that moment, the mobile terminal still does not have a dedicated channel and it must access the network by means of a channel that is shared by random access.
That solution suffers from the drawback of generating a high overall level of interference in the network due to the numerous unsuccessful attempts at connection. Also, the mechanism whereby packets that have collided are repeated increases the time required to establish a connection.
SUMMARY OF THE INVENTION
A particular object of the present invention is to provide a method of resolving collisions that makes it possible to avoid retransmitting packets that have collided.
Another object of the invention is to accelerate connection when it relies on a random access protocol to a shared channel.
Another object of the invention is to provide a receiver that implements the method.
These objects, and others that appear below, are achieved by a method of resolving collisions between packets transmitted to a receiver by different transmitters using a random access protocol, a signal corresponding to said packets colliding being received at the receiver, the method including a step of detecting errors and a step of identifying the transmitter of a packet, the method further comprising the steps of: selecting the fingers of the receive signal that have a power level greater than a threshold level; searching for a first configuration of contributions from the fingers for which the resulting packet is error-free, and identifying the corresponding transmitter, referred to as the first transmitter; and searching for a second configuration of contributions from the fingers for which the resulting packet is error-free, and for which the identified transmitter is different from the first transmitter. The inventive method may also involve the transmitting of an acknowledgement to each identified transmitter.
The step of detecting errors may be based on a CRC check for each of the resulting packets. In addition, the search for the first configuration may comprise the steps of: selecting the received signal finger having the highest power level; and searching for the minimum configuration of contributions from fingers for which the resulting packet is error-free; and the method of the invention may then further comprise the excluding of the fingers constituting the minimum configuration from the search for the second configuration.
The inventive method may be used in a CDMA type cellular network during the stage in which connection messages are interchanged between a terminal and a base station, a collision occurring when the base station receives connection messages from at least two terminals using different preambles within a predetermined period of time.
According to a further aspect of the invention, there is provided a receiver for receiving packets transmitted by different transmitters using a random access protocol, the receiver comprising means (
14
) for detecting the presence of errors in a packet, and means (
15
) for identifying the transmitter of a packet that has been correctly received, the receiver also comprising means for resolving collisions between packets. The means for resolving collisions may comprise: means (
11
) for storing the signal received in a predetermined period of time; means (
12
) for selecting from the received signal fingers having a power level greater than a threshold value; and means (
13
) for combining contributions from the fingers, followed by the means (
14
) for detecting the presence of errors, and the means (
15
) for identifying the transmitter.
According to the invention, the means (
14
) for detecting the presence of errors may comprise a CRC check for each of the resulting packets. Further, the receiver may have means for transmitting an acknowledgement to each of the identified transmitters.
Advantageously, an acknowledgment can usually be generated directly by the receiver, thereby avoiding the need for packets that have collided to be repeated.
REFERENCES:
patent: 5673252 (1997-09-01), Johnson et al.
patent: 5818826 (1998-10-01), Gfeller et al.
patent: 5856971 (1999-01-01), Gitlin et al.
patent: 6181683 (2001-01-01), Chevillat et al.
patent: 6269088 (2001-07-01), Masui et al.
patent: 2002/0061050 (2002-05-01), Ozluturk
patent: 2002/0071411 (2002-06-01), Masui
Zorzi, M.: “Mobile Radio Slotted Aloha with Capture and Diversity” Wireless Networks, US, ACM, vol. 1m, No. 2, pp. 227-239 XP000524646 ISSN: 1022-0038.
Kane, Jr. R. E. et al.: “Performance of a Rake Demodulator with Pre-Decision Multipath Thresholding” Proceedings of the Military Communications Conference (Milcom), US, New York, IEEE, vol. -, pp. 1025-1029 XP000222000.
Chen, X. et al.: “New Collision-Channel Model for Packet-Switched CDMA Networks” Electronics Letters, GB, IEE Stevenage, col. 27, No. 20, pp. 1792-1793 XP000264339 ISSN. 0013-5194.
Ramabadran, T. V. et al.: “A Tutorial on CRC Computations” IEEE Micro, US, IEEE, Inc. New York, col. 8, No. 4, pp. 62-75 XP002912523 ISSN: 0272-1732.
Alcatel
Patel Ajit
Shah Chirag
LandOfFree
Method of resolving physical layer collisions in a random... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of resolving physical layer collisions in a random..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of resolving physical layer collisions in a random... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3138125