Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1998-11-17
2003-06-24
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S336000, C370S338000, C370S345000, C370S346000, C370S458000
Reexamination Certificate
active
06584100
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a system for establishing a transmission sequence by which terminals in a wireless network communicate. In particular, the invention is directed to a system which generates a matrix identifying which terminals are to transmit and/or receive data, and which uses entries in that matrix to establish a transmission sequence with a reduced number of one-slot transition turnarounds in the wireless terminals. The invention has particular utility in connection with the medium access control protocol for wireless ATM networks, in which the transmission sequence for wireless terminals is defined by slots in a control data frame.
2. Description of the Related Art
ATM (“asynchronous transfer mode”) is a protocol which was developed to address problems associated with transmitting multimedia data between networked devices. In particular, ATM networks are systems that negotiate and establish transmission parameters (e.g., bandwidth) prior to connecting two networked devices, “packetize” different types of data (e.g., video and audio data) into cells based on the established transmission parameters, and then multiplex these cells so that they can be transmitted over a single communication line to a receiving device. The receiving device then checks the transmitted data for errors and, if any are present, requests retransmission of the data by the transmitting device.
Traditionally, ATM networks were wire-based, meaning that devices therein were interconnected using fiber optic cables or the like. Recently, however, wireless ATM networks have been developed which replace at least some of these fiber optic cables with point-to-point wireless connections, such as radio-frequency (“RF”) and infrared (“IR”) links. A wireless ATM network of this type is described in U.S. patent application Ser. No. 08/770,024, entitled “Medium Access Control (MAC) Protocol For Wireless ATM”, the contents of which are hereby incorporated by reference into the subject application as if set forth herein in full.
In detail, the foregoing U.S. patent application describes a communications protocol (i.e., the MAC protocol) for wireless ATM networks, which increases network quality of service, particularly in terms of allocated bandwidth, by first reserving and then scheduling resources required for data transmission.
FIGS. 1 and 2
show different configurations of wireless ATM networks on which the MAC protocol is implemented. Specifically,
FIG. 1
shows a “base station” configuration, in which base stations (or “BSs”) control communications among various wireless terminals (or “WTs”), and
FIG. 2
shows a so-called “ad-hoc” configuration in which one of the wireless terminals is assigned the task of controlling communications (i.e., the central controller, or “CC”).
In both the base station and ad-hoc configurations, communications among the various wireless terminals are effected via a time-slot based control data frame (“CDF”). As shown in
FIG. 3
, this CDF includes both a control phase
1
and a data phase
2
, each of which includes plural slots
4
for transmitting requests or data to/from various wireless terminals. Specifically, in the control phase, a wireless terminal sends a request to a scheduler in a base station or central controller via a control slot in the CDF. Generally speaking, this is a request for permission for the wireless terminal to transmit data packet(s) to another wireless terminal during the data phase of a next CDF. The scheduler gathers all such requests from the wireless terminals, and then allocates available data slots in the data phase of the next CDF to appropriate pairs of wireless terminals. That is, the scheduler allocates each data slot to a transmit/receive terminal pair, such that the transmitting terminal is permitted to send data in a particular data slot and the receiving terminal is permitted to receive the data from that data slot. Once these allocations are made, they are broadcast to the various wireless terminals, thereby informing each wireless terminal which data slots in the next CDF it can use to transmit/receive data.
In MAC-based wireless ATM networks of the type described above, all wireless terminals typically operate on the same frequency. As a result, it is not possible to switch a wireless terminal from a transmitting mode to a receiving mode without some time delay. This delay, which is commonly referred to as the minimum transceiver turnaround time (“MINTAT”), needs to be taken into account when determining the transmission sequence by which wireless terminals in the network communicate. Specifically, in order to reduce a degradation in network performance resulting from the MINTAT, slots in the CDF should be allocated so that each wireless terminal has enough time (at least the MINTAT) to switch from its transmitting mode to its receiving mode without adding additional delay into the network. To this end, when designing a transmission sequence, it is thus desirable to avoid situations where a wireless terminal changes from its transmitting mode to its receiving mode in adjacent slots of a CDF. This “one-slot transition turnaround” (or “OTT”) as it is called, results in additional networks delays and, therefore, should be avoided (or minimized) whenever possible.
Conventional systems reduce the number of OTTs during a transmission sequence by using dynamic programming or conventional back-tracking techniques, such as the “branch and bound” method. In brief, the branch and bound method is performed by generating a plurality of groups of transmission sequences for a single CDF. These groups are then divided into two sub-groups, from which the better of the two sub-groups (i.e., the sub-group which includes the fewest OTTs) is selected. Thereafter, the selected sub-group is then divided into two sub-sub-groups, from which the better of the two is selected, and so on until the best transmission sequence is selected. The problem with methods of this type is that they are computationally intensive, and become even more so as the number of communications per transmission sequence increase.
In response to the deficiencies of the foregoing methods, heuristic methods were developed for establishing a transmission sequence with relatively few OTTs. However, these heuristic methods have proven unsatisfactory for a number of reasons. For example, conventional heuristic methods have, heretofore, been unable to reduce the number of OTTs per transmission sequence to a satisfactory level. Moreover, these methods are often difficult to implement and can be computationally intensive.
Accordingly, there exists a need for a system which establishes a transmission sequence for terminals in a wireless network, which reduces the number of OTTs per transmission sequence, and which is less computationally intensive than its conventional counterparts. In particular, there exists a need for a system which allocates slots in a control data frame of a wireless ATM network running the MAC protocol so as to achieve these and other advantages.
SUMMARY OF THE INVENTION
The present invention addresses the foregoing needs by allocating slots in a CDF based on entries in a transmit/receive matrix. In particular, the invention generates a transmit/receive matrix which includes rows of terminals and columns of terminals. At each row/column nexus is an entry which defines whether communications are to be effected between a pair of terminals corresponding to that entry. The invention uses these entries to select the order in which pairs of terminals are to appear in the CDF. By establishing a transmission sequence in this manner, the invention is able to reduce the number of OTTs to two or less in most cases, and to do so using relatively simple calculations. Thus, unlike its conventional counterparts, the invention is able to reduce network degradation relatively easily.
Thus, according to one aspect, the present invention is a system (e.g., a method, an apparatus, and computer-executable process steps)
Kizou Hassan
Koninklijke Philips Electronics , N.V.
Logsdon Joe
Piotrows Daniel J.
LandOfFree
System for establishing a transmission sequence for plural... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for establishing a transmission sequence for plural..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for establishing a transmission sequence for plural... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3137371