[go: up one dir, main page]

WO2003005653A1 - Acces a fonction de coordination hybride (hcf) par contention progressive et limitation de cellules sans fil se chevauchant - Google Patents

Acces a fonction de coordination hybride (hcf) par contention progressive et limitation de cellules sans fil se chevauchant Download PDF

Info

Publication number
WO2003005653A1
WO2003005653A1 PCT/US2002/021330 US0221330W WO03005653A1 WO 2003005653 A1 WO2003005653 A1 WO 2003005653A1 US 0221330 W US0221330 W US 0221330W WO 03005653 A1 WO03005653 A1 WO 03005653A1
Authority
WO
WIPO (PCT)
Prior art keywords
cell
contention
free period
access point
inter
Prior art date
Application number
PCT/US2002/021330
Other languages
English (en)
Other versions
WO2003005653A8 (fr
Inventor
Mathilde Benveniste
Original Assignee
At & T Corp.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US10/187,158 external-priority patent/US7136361B2/en
Priority claimed from US10/187,132 external-priority patent/US7277413B2/en
Application filed by At & T Corp. filed Critical At & T Corp.
Priority to AU2002320300A priority Critical patent/AU2002320300A1/en
Publication of WO2003005653A1 publication Critical patent/WO2003005653A1/fr
Publication of WO2003005653A8 publication Critical patent/WO2003005653A8/fr

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W16/00—Network planning, e.g. coverage or traffic planning tools; Network deployment, e.g. resource partitioning or cells structures
    • H04W16/14—Spectrum sharing arrangements between different networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W74/00—Wireless channel access
    • H04W74/04—Scheduled access
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W56/00—Synchronisation arrangements
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W74/00—Wireless channel access
    • H04W74/08—Non-scheduled access, e.g. ALOHA
    • H04W74/0808—Non-scheduled access, e.g. ALOHA using carrier sensing, e.g. carrier sense multiple access [CSMA]
    • H04W74/0816—Non-scheduled access, e.g. ALOHA using carrier sensing, e.g. carrier sense multiple access [CSMA] with collision avoidance
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W84/00—Network topologies
    • H04W84/02—Hierarchically pre-organised networks, e.g. paging networks, cellular networks, WLAN [Wireless Local Area Network] or WLL [Wireless Local Loop]
    • H04W84/10—Small scale networks; Flat hierarchical networks
    • H04W84/12—WLAN [Wireless Local Area Networks]

Definitions

  • HYBRID COORDINATION FUNCTION (HCF) ACCESS THROUGH TIERED CONTENTION AND OVERLAPPED WIRELESS CELL
  • the invention disclosed broadly relates to telecommunications methods and more particularly relates to Quality of Service (QoS) management in multiple access packet networks.
  • QoS Quality of Service
  • Wireless local area networks generally operate at peak speeds of between 10 to 100 Mbps and have a typical range of 100 meters.
  • Single cell Wireless LANs are suitable for small single-floor offices or stores.
  • a station in a wireless LAN can be a personal computer, a bar code scanner, or other mobile or stationary device that uses a wireless network interface card (NIC) to make the connection over the RF link to other stations in the network.
  • NIC wireless network interface card
  • the single-cell wireless LAN provides connectivity within radio range between wireless stations.
  • An access point allows connections via the backbone network, to wired network-based resources, such as servers.
  • a single cell wireless LAN can typically support up to 25 users and still keep network access delays at an acceptable level.
  • Multiple cell wireless LANs provide greater range than does a single cell, by means of a set of access points and a wired network backbone to interconnect a plurality of single cell LANs.
  • Multiple cell wireless LANs can cover larger multiple-floor buildings.
  • a mobile laptop computer or data collector with a wireless network interface card (NIC) can roam within the coverage area while maintaining a live connection to the backbone network.
  • NIC wireless network interface card
  • Wireless LAN specifications and standards include the IEEE 802.11 Wireless LAN Standard and the HLPERLAN Type 1 and Type 2 Standards.
  • the IEEE 802.11 Wireless LAN Standard is published in three parts as IEEE 802.11-1999: IEEE 802.11a-1999: and IEEE 802.1 lb-1999, which are available from the IEEE, Inc. web site http://grouper.ieee.org/groups/802/ll.
  • An overview of the HJPERLAN Type 1 principles of operation is provided in the publication HIPERLAN Tvne 1 Standard, HIPERLAN Type 1 Standard, ETSI ETS 300 652, WA2 December 1997.
  • An overview of the HIPERLAN Type 2 principles of operation is provided in the Broadband Radio Access Networks (BRAN), HIPERLAN Type 2: System Overview.
  • BRAN Broadband Radio Access Networks
  • a subset of wireless LANs is Wireless Personal Area Networks (PANs), of which the Bluetooth Standard is the best known.
  • PANs Wireless Personal Area Networks
  • the Bluetooth Special Interest Group Specification Of The Bluetooth System. Version 1.1, February 22, 2001, describes the principles of Bluetooth device operation and communication protocols.
  • the IEEE 802.11 Wireless LAN Standard defines at least two different physical (PHY) specifications and one common medium access control (MAC) specification.
  • the IEEE 802.11(a) Standard is designed to operate in unlicensed portions of the radio spectrum, usually either in the 2.4 GHz Industrial, Scientific, and Medical (ISM) band or the 5 GHz Unlicensed-National Information
  • U-NII Ultra-Fi Protected Access
  • b 2.4 GHz ISM band
  • DSSS direct sequence spread spectrum
  • IEEE 802.11 Wireless LAN Standard describes two major components, the mobile station and the fixed access point (AP).
  • IEEE 802.11 networks can also have an independent configuration where the mobile stations communicate directly with one another, without support from a fixed access point.
  • a single cell wireless LAN using the IEEE 802.11 Wireless LAN Standard is an Independent Basic Service Set (IBSS) network.
  • An IBSS has an optional backbone network and consists of at least two wireless stations.
  • a multiple cell wireless LAN using the IEEE 802.11 Wireless LAN Standard is an Extended Service Set (ESS) network.
  • ESS Extended Service Set
  • An ESS satisfies the needs of large coverage networks of arbitrary size and complexity.
  • Each wireless station and access point in an IEEE 802.11 wireless LAN implements the MAC layer service, which provides the capability for wireless stations to exchange MAC frames.
  • the MAC frame transmits management, control, or data between wireless stations and access points. After a station forms the applicable MAC frame, the frame's bits are passed to the Physical Layer for transmission.
  • the MAC layer Before transmitting a frame, the MAC layer must first gain access to the network. Three interframe space (IFS) intervals defer an IEEE 802.11 station's access to the medium and provide various levels of priority. Each interval defines the duration between the end of the last symbol of the previous frame, to the beginning of the first symbol of the next frame.
  • the Short Interframe Space (SIFS) provides the highest priority level by allowing some frames to access the medium before others, such as an Acknowledgement (ACK) frame, a Clear to Send (CTS) frame, or a subsequent fragment burst of a previous data frame. These frames require expedited access to the network to minimize frame retransmissions.
  • the Priority Interframe Space is used for high priority access to the medium during the contention-free period.
  • the point coordinator in the access point connected to backbone network, controls the priority-based Point Coordination Function (PCF) to dictate which stations in cell can gain access to the medium.
  • the point coordinator in the access point sends a contention-free poll frame to a station, granting the station permission to transmit a single frame to any destination. All other stations in the cell can only transmit during contention-free period if the point coordinator grants them access to the medium.
  • the end of the contention-free period is signaled by the contention-free end frame sent by the point coordinator, which occurs when time expires or when the point coordinator has no further frames to transmit and no stations to poll.
  • the distributed coordination function (DCF) Interframe Space (DIFS) is used for transmitting low priority data frames during the contention-based period.
  • the DIFS spacing delays the transmission of lower priority frames to occur later than the priority-based transmission frames.
  • An Extended Interframe Space (EIFS) goes beyond the time of a DIFS interval, as a waiting period when a bad reception occurs.
  • the EIFS interval provides enough time for the receiving station to send an acknowledgment (ACK) frame.
  • ACK acknowledgment
  • DCF uses the Carrier-Sense Multiple Access With Collision Avoidance (CSMA/CA) contention-based protocol, which is similar to IEEE 802.3 Ethernet.
  • CSMA/CA Carrier-Sense Multiple Access With Collision Avoidance
  • the CSMA/CA protocol minimizes the chance of collisions between stations sharing the medium, by waiting a random backoff interval, if the station's sensing mechanism indicates a busy medium. The period of time immediately following traffic on the medium is when the highest probability of collisions occurs, especially where there is high utilization. Once the medium is idle, CSMA/CA protocol causes each station to delay its transmission by a random backoff time, thereby minimizing the chance it will collide with those from other stations.
  • the CSMA/CA protocol computes the random backoff time as the product of a constant, the slot time, times a pseudo-random number RN which has a range of values from zero to a collision window CW.
  • the value of the collision window for the second try to access the network is CW2, which yields the second try random backoff time. This process by the CSMA/CA protocol of increasing the delay before transmission is called binary exponential backoff.
  • CSMA allows access attempts after sensing the channel for activity. Still, simultaneous transmit attempts lead to collisions, thus rendering the protocol unstable at high traffic loads. The protocol also suffers from the hidden terminal problem.
  • the origin node sends a request to send (RTS) notice of the impending transmission.
  • RTS request to send
  • a response is returned by the destination if the RTS notice is received successfully and the origin node proceeds with the transmission.
  • RTS request to send
  • This protocol also reduces the average delay as collisions are detected upon transmission of merely a short message, the RTS.
  • CTS clear to send
  • a five-way handshake MACA protocol provides notification to competing sources of the successful termination of the transmission, [see, V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, "MACAW: A media access protocol for wireless LANs, SIGCOMM '94. Pages 212-225, ACM, 1994.]
  • CSMA and MACA are combined in CSMA/CA, which is MACA with carrier sensing, to give better performance at high loads.
  • a four-way handshake is employed in the basic contention-based access protocol used in the Distributed Coordination Function (DCF) of the IEEE 802.11 Standard for Wireless LANs, [see, IEEE Standards Department, D3, “Wireless Medium Access Control and Physical Layer WG,” IEEE Draft Standard P802.11 Wireless LAN, Jan 1996.]
  • DCF Distributed Coordination Function
  • each terminal determines whether it has permission to transmit using a random number generator and a permission probability "p" that depends on the estimated backlog, [see, R.L. Rivest, "Network control by Bayesian Broadcast", IEEE Trans. Inform. Theory, Vol IT 25, pp. 505-515, Sept 1979]
  • a backoff counter tracks the number of pauses and hence the number of completed transmissions before a node with pending packets attempts to seize the channel.
  • a contending node initializes its backoff counter by drawing a random value, given the backoff window size. Each time the channel is found idle, the backoff counter is decreased and transmission is attempted upon expiration of the backoff counter. The window size is doubled every time a collision occurs, and the backoff countdown starts again, [see, A. Tanenbaum, rd Computer Networks, 3 ed.. Upper Saddle River, NJ, Prentice Hall, 1996] The window size is doubled every time a collision occurs, and the backoff countdown starts again, [see, A. Tanenbaum, rd Computer Networks, 3 ed.. Upper Saddle River, NJ, Prentice Hall, 1996] The
  • DCF Distributed Coordination Function
  • LANs employs a variant of this contention resolution scheme, a truncated binary exponential backoff, starting at a specified window and allowing up to a maximum backoff range below which transmission is attempted.
  • a truncated binary exponential backoff starting at a specified window and allowing up to a maximum backoff range below which transmission is attempted.
  • the channel is shared by a centralized access protocol, the Point Coordination Function (PCF), which provides contention-free transfer based on a polling scheme controlled by the access point (AP) of a basic service set (BSS).
  • PCF Point Coordination Function
  • AP access point
  • BSS basic service set
  • the centralized access protocol gains control of the channel and maintains control for the entire contention- free period by waiting a shorter time between transmissions than the stations using the Distributed Coordination Function (DCF) access procedure. Following the end of the contention-free period, the DCF access procedure begins, with each station contending for access using the CSMA/CA method.
  • DCF Distributed Coordination Function
  • the 802.11 MAC Layer provides both contention and contention-free access to the shared wireless medium.
  • the MAC Layer uses various MAC frame types to implement its functions of MAC management, control, and data transmission.
  • Each station and access point on an 802.11 wireless LAN implements the MAC Layer service, which enables stations to exchange packets.
  • the results of sensing the channel to determine whether the medium is busy or idle, are sent to the MAC coordination function of the station.
  • the MAC coordination also carries out a virtual carrier sense protocol based on reservation information found in the Duration Field of all frames. This information announces to all other stations, the sending station's impending use of the medium.
  • the MAC coordination monitors the Duration Field in all MAC frames and places this information in the station's Network Allocation Vector (NAV) if the value is greater than the current NAV value.
  • NAV Network Allocation Vector
  • the NAV operates similarly to a timer, starting with a value equal to the Duration Field of the last frame transmission sensed on the medium, and counting down to zero. After the NAV reaches zero, the station can transmit, if its physical sensing of the channel indicates a clear channel.
  • the access point senses the medium, and if it is idle, it sends a Beacon packet to all stations.
  • the Beacon packet contains the length of the contention-free interval.
  • the MAC coordination in each member station places the length of the contention-free interval in the station's Network Allocation Vector (NAV), which prevents the station from taking control of the medium until the end of the contention-free period.
  • NAV Network Allocation Vector
  • the access point can send a polling message to a member station, enabling it to send a data packet to any other station in the BSS wireless cell.
  • QoS Quality Of Service
  • QoS Quality of service
  • the primary measures of QoS are message loss, message delay, and network availability.
  • Voice and video applications have the most rigorous delay and loss requirements.
  • Interactive data applications such as Web browsing have less restrained delay and loss requirements, but they are sensitive to errors.
  • Non-real-time applications such as file transfer, Email, and data backup operate acceptably across a wide range of loss rates and delay.
  • Some applications require a minimum amount of capacity to operate at all, for example, voice and video.
  • Many network providers guarantee specific QoS and capacity levels through the use of Service-Level
  • SLAs SLA Agreements
  • An SLA is a contract between an enterprise user and a network provider that specifies the capacity to be provided between points in the network that must be delivered with a specified QoS. If the network provider fails to meet the terms of the SLA, then the user may be entitled a refund.
  • the SLA is typically offered by network providers for private line, frame relay, ATM, or Internet networks employed by enterprises.
  • QoS Quality of Service
  • Prioritized packet scheduling, preferential packet dropping, and bandwidth allocation are among the techniques available at the various nodes of the network, including access points, that enable packets from different applications to be treated differently, helping achieve the different quality of service objectives.
  • Such techniques exist in centralized and distributed variations. The concern herein is with distributed mechanisms for multiple access in cellular packet networks or wireless ad hoc networks.
  • Management of contention for the shared transmission medium must reflect the goals sought for the performance of the overall system. For instance, one such goal would be the maximization of goodput (the amount of good data transmitted as a fraction of the channel capacity) for the entire system, or of the utilization efficiency of the RF spectrum; another is the minimization of the worst-case delay. As multiple types of traffic with different performance requirements are combined into packet streams that compete for the same transmission medium, a multi-objective optimization is required.
  • TCMA Tiered Contention Multiple Access
  • E-DCF Extended-DCF
  • the various stations on the network contend for access to the network.
  • the MAC protocol requires that each station first wait for a randomly- chosen time period, called an arbitration time. Since this period is chosen at random by each station, there is less likelihood of collisions between stations.
  • TCMA uses the contention window to give higher priority to some stations than to others. Assigning a short contention window to those stations that should have higher priority ensures that in most cases, the higher-priority stations will be able to transmit ahead of the lower-priority stations.
  • TCMA schedules transmission of different types of traffic based on their QoS service quality specifications. As seen in Figure 1, which depicts the tiered contention mechanism, a station cannot engage in backoff countdown until the completion of an idle period of length equal to its arbitration time.
  • HCF hybrid coordination function
  • the access point sends polling packets to a succession of stations on the network.
  • the individual stations can reply to the poll with a packet that contains not only the response, but also any data that needs to be transmitted.
  • Each station must wait to be polled.
  • the access point establishes a polling priority based on the QoS priority of each station.
  • HCF hybrid coordination function
  • the Tiered Contention Multiple Access (TCMA) protocol is applied to wireless cells which have overlapping access points contending for the same medium.
  • Quality of Service (QoS) support is provided to overlapping access points to schedule transmission of different types of traffic based on the service quality specifications of the access points.
  • the inventive method reduces interference in a medium between overlapping wireless LAN cells, each cell including an access point station and a plurality of member stations.
  • the method assigns to a first access point station in a first wireless LAN cell, a first scheduling tag.
  • the scheduling tag has a value that determines an accessing order for the cell in a transmission frame, with respect to the accessing order of other wireless cells.
  • the scheduling tag value is deterministically set.
  • the scheduling tag value can be permanently assigned to the access point by its manufacturer, it can be assigned by the network administrator at network startup, it can be assigned by a global processor that coordinates a plurality of wireless cells over a backbone network, it can be drawn from a pool of possible tag values during an initial handshake negotiation with other wireless stations, or it can be cyclically permuted in real-time, on a frame-by-frame basis, from a pool of possible values, coordinating that cyclic permutation with that of other access points in other wireless cells.
  • An access point station in a wireless cell signals the beginning of an intra- cell contention-free period for member stations in its cell by transmitting a beacon packet.
  • the duration of the intra-cell contention-free period is deterministically set.
  • the member stations in the cell store the intra-cell contention-free period value as a Network Allocation Vector (NAV).
  • NAV Network Allocation Vector
  • Each member station in the cell decrements the value of the NAV in a manner similar to other backoff time values, during which it will delay accessing the medium.
  • the method assigns to the first access point station, a first inter-cell contention-free period value, which gives notice to any other cell receiving the beacon packet, that the first cell has seized the medium for the period of time represented by the value.
  • the inter-cell contention-free period value is deterministically set.
  • any station receiving the beacon packet immediately broadcasts a contention-free time response (CFTR) packet containing a copy of the first inter-cell contention-free period value.
  • CFTR contention-free time response
  • the notice is distributed to a second access point station in an overlapping, second cell.
  • the second access point stores the first inter-cell contention-free period value as an Inter-BSS Network Allocation Vector (IBNAV).
  • IBNAV Inter-BSS Network Allocation Vector
  • the second access point decrements the value of IBNAV in a manner similar to other backoff time values, during which it will delay accessing the medium.
  • the method also assigns to first member stations in the first cell, a first shorter backoff value for high Quality of Service (QoS) data and a first longer backoff value for lower QoS data.
  • the backoff time is the interval that a member station waits after the expiration of the contention- free period, before the member station contends for access to the medium. Since more than one member station in a cell may be competing for access, the actual backoff time for a particular station can be selected as one of several possible values. In one embodiment, the actual backoff time for each particular station is deterministically set, so as to reduce the length of idle periods.
  • the actual backoff time for each particular station is randomly drawn from a range of possible values between a minimum delay interval to a maximum delay interval.
  • the range of possible backoff time values is a contention window.
  • the backoff values assigned to a cell may be in the form of a specified contention window.
  • High QoS data is typically isochronous data such as streaming video or audio data that must arrive at its destination at regular intervals.
  • Low QoS data is typically file transfer data and email, which can be delayed in its delivery and yet still be acceptable.
  • the Tiered Contention Multiple Access (TCMA) protocol coordinates the transmission of packets within a cell, so as to give preference to high QoS data over low QoS data, to insure that the required quality of service is maintained for each type of data.
  • TCMA Tiered Contention Multiple Access
  • the method similarly assigns to a second access point station in a second wireless LAN cell that overlaps the first sell, a second contention-free period value longer than the first contention-free period value.
  • the method also assigns to second member stations in the second cell, a second shorter backoff value for high QoS data and a second longer backoff value for lower QoS data.
  • the first and second cells are considered to be overlapped when one or more stations in the first cell inadvertently receive packets from member stations or the access point of the other cell.
  • the invention reduces the interference between the overlapped cells by coordinating the timing of their respective transmissions, while maintaining the TCMA protocol's preference for the transmission of high QoS data over low QoS data in each respective cell.
  • the method transmits a first beacon packet including the intra-cell contention-free period value (the increment to the NAV) and inter-cell contention-free period value (the CFTR), from the first access point to the first member stations in the first cell.
  • the beacon packet is received by the member stations of the first cell and can be inadvertently received by at least one overlapped member station of the second cell.
  • Each member station in the first cell increments its NAV with the intra-cell contention-free period value and stores the inter-cell contention-free period value as the CFTR.
  • each station that receives the first beacon packet immediately responds by transmitting a first contention-free time response (CFTR) packet that contains a copy of the inter-cell contention-free period value (CFTR).
  • CFTR contention-free time response
  • a CFTR packet is transmitted from the first member stations in the first cell and also by the overlapped member stations of the second cell. The effect of the transmission of CFTR packets from member stations in the second cell is to alert the second access point and the second member stations in the second cell, that the medium has been seized by the first access point in the first cell.
  • the second access point in the second cell receives the CFTR packet it stores the a copy of the inter-cell contention-free period value as the IBNAV.
  • a first IBNAV is set at the second access point to indicate the time the medium will be free again. Also similar to the NAV, the first IBNAV is decremented with each succeeding slot, similar to the decrementing of other backoff times.
  • the second access point receives the first IBNAV representing the first cell's contention-free period value, the second access point must respect the first IBNAV value and delay transmitting its beacon packet and the exchange of other packets in the second cell until the expiration of the received, first IBNAV.
  • the second access point When the second access point has decremented the first IBNAV to zero, the second access point transmits its second beacon packet including its second contention-free period values of NAV and a second IBNAV, to the second member stations in the second cell. Each station that receives the second beacon packet immediately responds by transmitting a second contention-free time response (CFTR) packet that contains a copy of the second IBNAV inter-cell contention-free period value.
  • the second CFTR packet is transmitted from the second member stations in the second cell and also by the overlapped member stations of the first cell. The effect of the transmission of the second CFTR packets from overlapped member stations in the first cell is to alert the first access point and the first member stations in the first cell, that the medium has been seized by the second access point in the second cell.
  • the first access point in the first cell When the first access point in the first cell receives the CFTR packet it stores the a copy of the second IBNAV inter-cell contention-free period value, to indicate the time the medium will be free again.
  • the second BBNAV is decremented with each succeeding frame, similar to the decrementing of other backoff times.
  • the second member stations in the second cell wait for completion of the count down of their NAVs to begin the TCMA protocol of counting down the second shorter backoff for high QoS data and then transmitting second high QoS data packets.
  • the first access point in the first cell waits for completion of the count down of the second IBNAV inter-cell contention-free period before starting the countdown of its own NAV for its own intra-cell contention-free period.
  • the first member stations in the first cell wait for the count down of their NAVs, to begin the TCMA protocol of counting down the first longer backoff for low QoS data and then transmitting first low QoS data.
  • the second member stations are waiting for the TCMA protocol of counting down the second longer backoff for lower QoS data before transmitting the second lower QoS data.
  • TCMA protocol Potential collisions between cells engaged in centralized access can be averted or resolved by the TCMA protocol.
  • deterministically set backoff delays are used, which tend to reduce the length of the idle periods.
  • the possibility of coincident or overlapping contention-free periods between neighboring cells is eliminated through the use of an "interference sensing" method employing a new frame.
  • the invention enables communication of channel occupancy information to neighboring access points. When a beacon packet is transmitted, and before transmission of any other data or polling packets, all stations hearing the beacon will respond by sending a frame, the contention-free time response (CFTR), that will contain the duration of the contention-free period found in the beacon.
  • CFTR contention-free time response
  • An access point in neighboring cells, or stations attempting contention-based channel access, which receive this message from a station in the cell overlapping region, are thus alerted that the channel has been seized by an access point. Similar to a station's Network Allocation Vector (NAV), an Inter-Cell Network Allocation Vector at the access point accordingly indicates when the time the channel will be free again. Unless the Inter-Cell Network Allocation Vector is reset, the access point will decrease its backoff value only after the expiration of the Inter-Cell Network Allocation Vector, according to the backoff countdown rules.
  • NAV Network Allocation Vector
  • potential collisions between different access points engaged in centralized access can be averted or resolved by using deterministic backoff delays, which avoid collisions between access points, and eliminate gaps between consecutive poll/response exchanges or contention-free bursts (CFBs) between the access point and its associated stations.
  • deterministic backoff delays which avoid collisions between access points, and eliminate gaps between consecutive poll/response exchanges or contention-free bursts (CFBs) between the access point and its associated stations.
  • the resulting invention applies the Tiered Contention Multiple Access (TCMA) protocol to wireless cells which have overlapping access points contending for the same medium.
  • TCMA Tiered Contention Multiple Access
  • Figure 1 depicts the tiered contention mechanism.
  • Figures 1 A through 1 J show the interaction of two wireless LAN cells which have overlapping access points contending for the same medium, in accordance with the invention.
  • Figure IK shows a timing diagram for the interaction of two wireless LAN cells in Figures 1A through 1J, in accordance with the invention.
  • Figure IL shows the IEEE 802.11 packet structure for a beacon packet, including the increment to the NAV period and the CFTR period, in accordance with the invention.
  • Figure IM shows the IEEE 802.11 packet structure for a CFTR packet, including the CFTR period, in accordance with the invention.
  • Figure 2 illustrates the ordering of transmissions from three groups of BSSs.
  • Figure 3 illustrates how three interfering BSSs share the same channel for two consecutive frames.
  • Figure 4 illustrates how three interfering BSSs, each with two types of traffic of different priorities, share the same channel in two consecutive frames.
  • Figure 5 illustrates the possible re-use of tags.
  • Figure 6 illustrates the deterministic post-backoff.
  • Figure 7 shows the relationships of repeating sequences of CFBs.
  • Figure 8 illustrates the role of pegging in a sequence of CFBs by three overlapping access points.
  • Figure 9 illustrates the start-up procedure for a new access point, HC2, given an existing access point, HCl.
  • Figure 10 shows the relationship of repeating sequences of Tier I CFBs.
  • Figure 11 illustrates the start-up procedure for a new access point, HC2, given an existing access point, HCl.
  • the invention disclosed broadly relates to telecommunications methods and more particularly relates to Quality-of-Service (QoS) management in multiple access packet networks.
  • QoS Quality-of-Service
  • Several protocols either centralized or distributed can co-exist on the same channel through the Tiered Contention Multiple Access method.
  • the proper arbitration time to be assigned to the centralized access protocol must satisfy the following requirements: (i) the centralized access protocol enjoys top priority access, (ii) once the centralized protocol seizes the channel, it maintains control until the contention-free period ends, (iii) the protocols are backward compatible, and (iv) Overlapping Basic Service Sets (OBSSs) engaged in centralized-protocol can share the channel efficiently.
  • OBSSs Basic Service Sets
  • the Tiered Contention Multiple Access (TCMA) protocol is applied to wireless cells which have overlapping access points contending for the same medium.
  • Quality of Service (QoS) support is provided to overlapping access points to schedule transmission of different types of traffic based on the service quality specifications of the access points.
  • the inventive method reduces interference in a medium between overlapping wireless LAN cells, each cell including an access point station and a plurality of member stations.
  • Figures 1 A through 1J show the interaction of two wireless LAN cells which have overlapping access points contending for the same medium, in accordance with the invention.
  • the method assigns to a first access point station in a first wireless LAN cell, a first scheduling tag.
  • the scheduling tag has a value that determines an accessing order for the cell in a transmission frame, with respect to the accessing order of other wireless cells.
  • the scheduling tag value is deterministically set.
  • the scheduling tag value can be permanently assigned to the access point by its manufacturer, it can be assigned by the network administrator at network startup, it can be assigned by a global processor that coordinates a plurality of wireless cells over a backbone network, it can be drawn from a pool of possible tag values during an initial handshake negotiation with other wireless stations, or it can be cyclically permuted in real-time, on a frame-by-frame basis, from a pool of possible values, coordinating that cyclic pe ⁇ nutation with that of other access points in other wireless cells.
  • the interaction of the two wireless LAN cells 100 and 150 in Figures 1 A through 1J is shown in the timing diagram of Figure IK.
  • FIG. 1 A shows access point 152 of cell 150 connected to backbone network 160, transmitting the beacon packet 124.
  • the beacon packet 124 includes two contention-free period values, the first is the Network Allocation Vector (NAV) (or alternately its incremental value ⁇ NAV) , which specifies a period value P3 for the intra-cell contention-free period for member stations in its own cell.
  • NAV Network Allocation Vector
  • the other contention- free period value included in the beacon packet 124 is the Inter-BSS Network Allocation Vector (IBNAV), which specifies the contention-free time response (CFTR) period P4.
  • IBNAV Inter-BSS Network Allocation Vector
  • CFTR contention-free time response
  • P4 gives notice to any other cell receiving the beacon packet, such as cell 100, that the first cell 150 has seized the medium for the period of time represented by the value P4.
  • the beacon packet 124 is received by the member stations 154A (with a low QoS requirement 164A) and 154B (with a high QoS requirement 164B) in the cell
  • FIG. IL shows the IEEE 802.11 packet structure 260 for the beacon packet 124 or 120, including the increment to the NAV period and the CFTR period.
  • the beacon packet structure 260 includes fields 261 to 267.
  • Field 267 specifies the ⁇ NAV value of P3 and the CFTR value of P4.
  • the method assigns to the first access point station, a first inter-cell contention-free period value, which gives notice to any other cell receiving the beacon packet, that the first cell has seized the medium for the period of time represented by the value.
  • the inter-cell contention- free period value is deterministically set.
  • any station receiving the beacon packet 124 immediately rebroadcasts a contention-free time response (CFTR) packet 126 containing a copy of the first inter-cell contention-free period value P4.
  • the value P4 specifies the Inter-BSS Network Allocation Vector (IBNAV), i.e., the contention-free time response (CFTR) period that the second access point 102 must wait, while the first cell 150 has seized the medium.
  • Figure IB shows overlap station 106 in the region of overlap 170 transmitting the CFTR packet 126 to stations in both cells 100 and 150 during the period from Tl to T2.
  • Figure IM shows the IEEE 802.11 packet structure 360 for a CFTR packet 126 or 122, including the CFTR period.
  • the CFTR packet structure 360 includes fields 361 to 367. Field 367 specifies the CFTR value of P4. In this manner, the notice is distributed to the second access point station 102 in the overlapping, second cell 100.
  • Figure 1C shows the point coordinator in access point 152 of cell 150 controlling the contention-free period within the cell 150 by using the polling packet 128 during the period from T2 to T3.
  • the second access point 102 in the second cell 100 connected to backbone network 110 stores the first inter-cell contention-free period value P4 received in the CFTR packet 126, which it stores as the Inter-BSS Network Allocation Vector (IBNAV).
  • IBNAV Inter-BSS Network Allocation Vector
  • the second access point 102 decrements the value of IBNAV in a manner similar to other backoff time values, during which it will delay accessing the medium.
  • the method uses the Tiered Contention Multiple Access (TCMA) protocol to assign to first member stations in the first cell 150, a first shorter backoff value for high Quality of Service (QoS) data and a first longer backoff value for lower QoS data.
  • TCMA Tiered Contention Multiple Access
  • Figure ID shows the station 154B in the cell 150, having a high QoS requirement 164B, decreasing its High QoS backoff period to zero and beginning TCMA contention to transmit its high QoS data packet 130 during the period from T3 to T4.
  • the backoff time is the interval that a member station waits after the expiration of the contention-free period P3, before the member station 154B contends for access to the medium.
  • the actual backoff time for a particular station can be selected as one of several possible values.
  • the actual backoff time for each particular station is deterministically set, so as to reduce the length of idle periods.
  • the actual backoff time for each particular station is randomly drawn from a range of possible values between a minimum delay interval to a maximum delay interval.
  • the range of possible backoff time values is a contention window.
  • the backoff values assigned to a cell may be in the form of a specified contention window.
  • High QoS data is typically isochronous data such as streaming video or audio data that must arrive at its destination at regular intervals.
  • Low QoS data is typically file transfer data and email, which can be delayed in its delivery and yet still be acceptable.
  • Tiered Contention Multiple Access (TCMA) protocol coordinates the transmission of packets within a cell, so as to give preference to high QoS data over low QoS data, to insure that the required quality of service is maintained for each type of data.
  • Figure IE shows the second access point 102 in the cell 100 transmitting its beacon packet 120 including its contention-free period values of NAV (P6) and IBNAV (P7), to the member stations 104A (with a low QoS requirement 114A) , 104B (with a high QoS requirement 114B) and 106 in the cell 100 during the period from T4 to T5.
  • Figure IF shows that each station, including the overlap station 106, that receives the second beacon packet 120, immediately responds by retransmitting a second contention-free time response (CFTR) packet 122 that contains a copy of the second inter-cell contention-free period value P7 during the period from T4 to T5.
  • CFTR contention-free time response
  • Figure 1G shows the point coordinator in access point 102 of cell 100 controlling the contention-free period within cell 100 using the polling packet 132 during the period from T5 to T6.
  • the method uses the Tiered Contention Multiple Access (TCMA) protocol to assign to second member stations in the second cell 100, a second shorter backoff value for high QoS data and a second longer backoff value for lower QoS data.
  • Figure IH shows the station 104B in the cell 100, having a high QoS requirement 114B, decreasing its High QoS backoff period to zero and beginning TCMA contention to transmit its high QoS data packet 134 during the period from T6 to T7.
  • TCMA Tiered Contention Multiple Access
  • Figure II shows the first member stations 154A and 154B in the first cell 150 waiting for the count down of their NAVs, to begin the TCMA protocol of counting down the first longer backoff for low QoS data and then transmitting first low QoS data 136 during the period from T7 to T8.
  • Figure IJ shows the second member stations 104A, 104B, and 106 are waiting for the TCMA protocol of counting down the second longer backoff for lower QoS data before transmitting the second lower QoS data 138 during the period from T8 to T9.
  • the first and second cells are considered to be overlapped when one ⁇ ⁇ r more stations in the first cell can inadvertently receive packets from member stations or the access point of the other cell.
  • the invention reduces the interference between the overlapped cells by coordinating the timing of their respective transmissions, while maintaining the TCMA protocol's preference for the transmission of high QoS data over low QoS data in each respective cell.
  • the method in Figure 1 A transmits a first beacon packet 124 including the intra-cell contention-free period value (the increment to the NAV) and inter-cell contention-free period value (the CFTR), from the first access point 152 to the first member stations 154B and 154A in the first cell 150.
  • the beacon packet is received by the member stations of the first cell and inadvertently by at least one overlapped member station 106 of the second cell 100.
  • Each member station 154B and 154A in the first cell increments its NAV with the intra-cell contention-free period value P3 and stores the inter-cell contention- free period value P4 as the CFTR.
  • each station that receives the first beacon packet 124 immediately responds by transmitting a first contention-free time response (CFTR) packet 126 in Figure IB that contains a copy of the inter-cell contention-free period P4 value (CFTR).
  • a CFTR packet 126 is transmitted from the first member stations 154B and 154A in the first cell 150 and also by the overlapped member stations 106 of the second cell 100.
  • the effect of the transmission of CFTR packets 126 from member stations 106 in the second cell 100 is to alert the second access point 102 and the second member stations 104A and 104B in the second cell 100, that the medium has been seized by the first access point 152 in the first cell 150.
  • the second access point 102 in the second cell 100 receives the CFTR packet 126 it stores the a copy of the inter-cell contention-free period value P4 as the IBNAV.
  • an IBNAV is set at the access point to indicate the time the medium will be free again. Also similar to the NAV, the IBNAV is decremented with each succeeding slot, similar to the decrementing of other backoff times.
  • the second access point receives a new IBNAV representing the first cell's contention-free period value, then the second access point must respect the IBNAV value and delay transmitting its beacon packet and the exchange of other packets in the second cell until the expiration of the received, IBNAV.
  • each station that receives the second beacon packet immediately responds by transmitting a second contention-free time response (CFTR) packet 122 in Figure IF, that contains a copy of the second inter-cell contention-free period value P7.
  • a CFTR packet 122 is transmitted from the second member stations 104A, 104B and overlapped station 106 in the second cell and also by the overlapped member stations of the first cell.
  • the effect of the transmission of CFTR packets from overlapped member station 106 is to alert the first access point 152 and the first member stations 145A and 154B in the first cell 150, that the medium has been seized by the second access point 102 in the second cell 100.
  • the first access point 152 in the first cell 150 receives the CFTR packet 122 it stores the a copy of the second inter-cell contention-free period value P7 as an IBNAV, to indicate the time the medium will be free again.
  • the IBNAV is decremented with each succeeding slot, similar to the decrementing of other backoff times.
  • the second member stations 104 A, 104B, and 106 in the second cell 100 wait for completion of the count down of their NAVs to begin the TCMA protocol of counting down the second shorter backoff for high QoS data and then transmitting second high QoS data packets, as shown in Figures 1G and IH.
  • the first access point 152 in the first cell 150 waits for completion of the count down of the second inter-cell contention-free period P7 in its IBNAV in Figures 1G and IH before starting the countdown of its own NAV for its own intra-cell contention-free period.
  • the first member stations 154A and 154B in the first cell 150 wait for the count down of their NAVs, to begin the TCMA protocol of counting down the first longer backoff for low QoS data and then transmitting first low QoS data in Figure II.
  • E-DCF Hybrid Coordination Function
  • HCF Hybrid Coordination Function
  • the channel must remain under the control of the centralized access protocol until the contention-free period is complete once it has been seized by the centralized access protocol. For this, it is sufficient that the maximum spacing between consecutive transmissions exchanged in the centralized access protocol, referred to as the central coordination time (CCT), be shorter than the time the channel must be idle before a station attempts a contention-based transmission following the end of a busy- channel time interval.
  • the centralized access protocol has a CCT equal to the Priority Interframe Space (PIFS).
  • no station may access the channel by contention, using either the distributed coordination function (DCF) or Extended-DCF (E-DCF) access procedure, before an idle period of length of the DCF Interframe Space (DIFS) equaling PIFS+l(slot time) following the end of a busy-channel time interval.
  • DCF distributed coordination function
  • E-DCF Extended-DCF
  • DCF Interframe Space PIFS+l(slot time) following the end of a busy-channel time interval.
  • DCF DCF Interframe Space
  • UATj Urgency Arbitration Time
  • Backward compatibility relates to the priority treatment of traffic handled by enhanced stations (ESTAs) as compared to legacy stations (STAs).
  • the ESTAs In addition to traffic class differentiation, the ESTAs must provide certain traffic classes with higher or equal priority access than that provided by the STAs. That means that certain traffic classes should be assigned a shorter arbitration times than DIFS, the de facto arbitration time of legacy stations.
  • DIFS de facto arbitration time of legacy stations.
  • an arbitration time of PIFS appears to fail meeting the requirement for uninterrupted control of the channel during the contention-free period, it is possible for an ESTA to access the channel by E-DCF using an arbitration time of PIFS and, at the same time, allow priority access to the centralized access protocol at PIFS.
  • the residual backoff value of a backlogged station will be greater than or equal to 1 whenever countdown is resumed at the end of a busy channel period.
  • the station will decrease its residual backoff value by 1 following each time slot during which the channel remains idle. If m reaches 0 before countdown is interrupted by a transmission, the station will attempt transmission. The transmission will either fail, leading to a new backoff being drawn, or succeed. Therefore, countdown will be resumed after the busy-channel period ends, only with a residual backoff of 1 or greater. Consequently, if the smallest random backoff that can be drawn is 1 or greater, an ESTA will always wait for at least a DIFS idle interval following a busy period before it attempts transmission.
  • ESTA with arbitration time of PIFS has a residual backoff of 1. Moreover, a legacy station will be unable to transmit until all higher-priority ESTAs with residual backoff of 1 have transmitted. Only legacy stations that draw a backoff value of 0 will transmit after a DIFS idle period, thus competing for the channel with the higher priority stations. This occurs only with a probability less than 3 per cent, since the probability of drawing a random backoff of 0 from the range [0,31] is equal to 1/32.
  • PIFS -1 (slot time) the Short Interframe Space (SIFS).
  • SIFS Short Interframe Space
  • the random backoff values for the beacon of the centralized access protocol must be drawn from a range with a lower bound of at least 1.
  • inter-BSS interference Another aspect of inter-BSS interference that affects the performance of centralized protocols adversely is the possible interruption with a collision of what starts as an interference-free poll/response exchange between the access point and its associated stations.
  • the possibility of coincident or overlapping contention-free periods between neighboring BSSs is eliminated through the use of an "interference sensing" method employing a new frame. Deterministic backoff procedure for the centralized access protocol
  • a modified backoff procedure is pursued for the beacons of the centralized access protocols.
  • a backoff counter is employed in the same way as in TCMA. But while the backoff delay in TCMA is selected randomly from a contention window, in the case of the centralized access protocol beacons, the backoff value is set deterministically.
  • the backoff delay is selected through a mechanism called "tag scheduling".
  • Tags which are ordinal labels, are assigned to different BSSs. BSSs that do not interfere with one another may be assigned the same tag, while BSSs with the potential to interfere with one another must receive different tags.
  • the tags are ordered in a way that is known a priori. This order represents the sequence in which the BSS with a given tag will access the channel in that frame.
  • the backoff delay increases with the rank of the "tag" that has been assigned to the BSS for the cu ⁇ ent frame, as tags are permuted to give each group of BSS with the same tag a fair chance at the channel.
  • the difference in the backoff delays co ⁇ esponding to two consecutive tags is one time slot.
  • Figure 2 illustrates the ordering of transmissions from three groups of BSSs.
  • a backoff counter is associated with each backoff delay. It is decreased according to the rules of TCMA using the arbitration time of Short Interframe Space (SIFS) as described in the preceding section. That is, once the channel is idle for a time interval equal to SIFS, the backoff counter associated with the centralized protocol of the BSS is decreased by 1 for each slot time the channel is idle. Access attempt occurs when the backoff counter expires.
  • the minimum backoff value associated with the highest-ranking tag is 1.
  • Figure 3 illustrates how three interfering BSSs share the same channel for two consecutive frames.
  • the tags assigned in each of the two frames are (1, 2), (2, 3), and (3, 1) for the three BSSs, respectively.
  • the backoff delays for the three tags are 1, 2, and 3 time slots.
  • the channel When the channel is seized by the centralized protocol of a BSS, it engages in the polling and transmission functions for a time interval, known as the contention- free period. Once the channel has been successfully accessed that way, protection by the Network Allocation Vector (NAV) prevents interference from contention based traffic originating within that BSS. Avoidance of interference from neighboring BSS is discussed below. A maximum limit is imposed on the reservation length in order to even out the load on the channel from different BSSs and allow sufficient channel time for contention-based traffic.
  • NAV Network Allocation Vector
  • the backoff delays are set in a deterministic manner, there are no guarantees that collisions will always be avoided. Unless the duration of the contention-free period is the same for all BSSs, there is the possibility that interfering BSSs will attempt to access the channel at once. In case of such a collision, the backoff procedure starts again with the backoff delay associated with the tag assigned to the BSS, decreased by 1 , and can be repeated until expiration of the frame. At the start of a new frame, a new tag is assigned to the BSS according to the pre-specified sequence, and the defe ⁇ al time interval associated with the new tag is used.
  • Interference sensing is the mechanism by which the occupancy status of a channel is determined.
  • the access point only needs to know of channel activity in interfering BSSs.
  • the best interference sensing mechanism is one that ensures that the channel is not used simultaneously by potentially interfering users. This involves listening to the channel by both the access point and stations. If the access point alone checks whether the channel is idle, the result does not convey adequate information on the potential for interference at a receiving station, nor does it address the problem of interference caused to others by the transmission, as an access point may not be able to hear transmissions from its neighboring access points, yet there is potential of interference to stations on the boundary of neighboring BSSs. Stations must detect neighboring BSS beacons and forward the information to their associated access point. However, transmission of this information by a station would cause interference within the neighboring BSS.
  • the invention includes the following mechanism.
  • CFTR contention-free time response
  • An access point in neighboring BSSs, or stations attempting contention-based channel access, that receive this message from a station in the BSS overlapping region are thus alerted that the channel has been seized by a BSS.
  • NAV Network Allocation Vector
  • Inter-BSS NAV Inter-BSS NAV
  • IBNAV Inter-BSS NAV
  • the access point will decrease its backoff value only after the expiration of the IBNAV, according to the backoff countdown rules.
  • beacons are sent at fixed time increments, receipt of the contention-free time response (CFTR) frame would suffice to extend the IBNAV.
  • CFTR contention-free time response
  • the alternative would be convenient in order to obviate the need for full decoding of the CFTR frame. It is necessary, however, that the frame type of CFTR be recognizable.
  • IBCP Inter-BSS Contention Period
  • a QoS-capable centralized protocol will have traffic with different time delay requirements queued in different priority buffers. Delay-sensitive traffic will be sent first, followed by traffic with lower priority. Tag scheduling is used again, but now there are two or more backoff values associated with each tag, a shorter value for the higher priority traffic and longer ones for lower priority.
  • a BSS will transmit its top priority packets first, as described before. Once the top priority traffic has been transmitted, there would be further delay before the BSS would attempt to transmit lower priority traffic in order to give neighboring BSSs a chance to transmit their top priority packets.
  • any of the deferral time intervals for low- priority traffic is longer than the defe ⁇ al time intervals for higher priority traffic of any tag, in general all neighboring BSSs would have a chance to transmit all pending top-priority packets before any lower-priority packets are transmitted.
  • Figure 4 illustrates how three interfering BSSs, each with two types of traffic of different priorities, share the same channel in two consecutive frames.
  • the tags assigned in each of the two frames are (1, 2), (2, 3), and (3, 1) for the three BSSs, respectively.
  • the deferral times for the top priority traffic are 1, 2, and 3 time slots for tags 1, 2, and 3, respectively.
  • the deferral times for the higher priority traffic are 4, 5, and 6 time slots for tags 1, , and 3, respectively.
  • tags must be given to user entities with potential to interfere. This is not a difficult requirement to meet.
  • a different tag could be assigned to each user entity. In that case, non-interfering cells will use the channel simultaneously even though they have different tags. Interference sensing will enable reuse of the channel by non-interfering BSSs that have been assigned different tags. There are advantages, however, in reducing the number of different tags.
  • Tag assignment can be done without knowledge of the location of the access points and/or the stations.
  • Tag assignment like channel selection can be done at the time of installation. And again, like dynamic channel selection, it can be selected by the access point dynamically.
  • RF planning which processes signal-strength measurements can establish re-use groups and thus reduce the required number of tags.
  • Figure 5 which includes Figures 5(a) and 5(b), illustrates the possible re-use of tags.
  • the access points are located at ideal spots on a hexagonal grid to achieve a regular tessellating pattern.
  • the access points have been placed as convenient and tags are assigned to avoid overlap. Imperfect tag assignments will lead to collisions between the access points, but such collisions can be resolved.
  • E-DCF has the top priority
  • E-DCF can offer traffic classes with priority access both above and below that provided by legacy stations using DCF.
  • Table 1 illustrates the parameter specification for K+l different classes according to the requirements given above.
  • the centralized access protocol is assigned the highest priority classification, and hence the shortest arbitration time.
  • the top k-1 traffic classes for the E-DCF have priority above legacy but below the centralized access protocol; they achieve differentiation through the variation of the contention window size as well as other parameters.
  • E-DCF traffic classes with priority above legacy have a lower bound, rLower, of the distribution from which backoff values are drawn that is equal to 1 or greater. Differentiation for classes with priority below legacy is achieved by increasing arbitration times; the lower bound of the random backoff distribution can be 0.
  • BSSs within interfering range of one another compete for the channel through a deterministic backoff procedure employing tag scheduling, which rotates the backoff value for fairness among potentially interfering BSS. Re-use of a tag is permitted in non-interfering BSS. Multiple queues with their own backoff values enable prioritization of different QoS traffic classes.
  • potential collisions between different BSSs engaged in centralized access can be averted resolved by deterministic backoff delays, which avoid collisions between access points, and eliminate gaps between consecutive poll/response exchanges between the access point and its associated stations. These are referred to as contention-free bursts (CFBs).
  • CFBs contention-free bursts
  • a modified backoff procedure is pursued for the beacons of the centralized access protocols.
  • a backoff counter is employed in the same way as in TCMA. But while the backoff delay in TCMA is selected randomly from a contention window, in the case of the centralized access protocol beacons, the backoff value is set deterministically to a fixed value Bkoff, at the end of its contention-free session. Post-backoff is turned on.
  • the deterministic post-backoff procedure is illustrated in Figure 6.
  • the channel When the channel is seized by the centralized protocol of a BSS, it engages in the polling and transmission functions for a time interval, known as the contention- free period. Once the channel has been successfully accessed that way, protection by the NAV prevents interference from contention based traffic originating in the BSS. Avoidance of interference from neighboring BSS is discussed below.
  • Non-conflicting contiguous sequences of CFBs As long as the value of Bkoff is greater than or equal to the maximum number of interfering BSS, it is possible for the contention-free periods of a cluster of neighboring/overlapping BSSs to repeat in the same order without a collision between them. CFBs of different BSSs can be made to follow one another in a contiguous sequence, thus maximizing access of the centralized protocol to the channel. This can be seen as follows.
  • an HC In order to maintain contiguity, an HC that does not have any traffic to transmit when its backoff expires, it will transmit a short packet - a "peg" - and then engage in post-backoff. This way no gaps of length DIFS+1 are left idle until all HCs have completed one CFB per cycle, and restarted the backoff countdown procedure. E-DCF stations are thus prevented from seizing the channel until each BSS completes at least one CFB per cycle.
  • Figure 8 illustrates the role of pegging in a sequence of CFBs by three overlapping access points. Finally it is shown how such a contiguous sequence can constructed by analyzing how a new access point initiates its first CFB.
  • a new access point Every time a new access point is installed, it must find its position in the repeating sequence of CFBs.
  • the new access point listens to the channel for the desired cycle, trying to recognize the sequence. It listens for an "idle" PIFS following a busy channel. When that occurs, or after counting Bkoff time slots, whichever comes first, the new access point starts looking for the first idle longer than PIFS, which signifies the end of the sequence of CFBs. As long as the Bkoff is greater than the number of interfering BSS, there will always be such an idle period.
  • the access point sets its post-backoff delay so that it transmits always right at the end of the CFB sequence.
  • FIG. 9 illustrates this start-up procedure for a new access point, HC2, given an existing access point, HCl.
  • Interference sensing is the mechanism by which the occupancy status of a channel is determined.
  • the access point only needs to know of channel activity in interfering BSSs.
  • the best interference sensing mechanism is one that ensures that the channel is not used simultaneously by potentially interfering users. This involves listening to the channel by both the access point and stations. If the access point alone checks whether the channel is idle, the result does not convey adequate information on the potential for interference at a receiving station, nor does it address the problem of interference caused to others by the transmission, as an access point may not be able to hear transmissions from its neighboring access points, yet there is potential of interference to stations on the boundary of neighboring BSS. Stations must detect neighboring BSS beacons and forward the information to their associated access point.
  • an inter-BSS NAV Similar to a station's NAV, an inter-BSS NAV (IBNAV) will be set at the access point accordingly indicating the time the channel will be free again. Unless the IBNAV is reset, the access point will decrease its backoff value only after the expiration of the IBNAV, according to the backoff countdown rules. Alternatively, if beacons are sent at fixed time increments, receipt of the IBNAV
  • CFTR frame would suffice to extend the IBNAV.
  • the alternative would be convenient in order to obviate the need for full decoding of the CFTR frame. It is necessary, however, that the frame type of CFTR be recognizable.
  • Contention by E-DCF traffic while various interfering BSSs attempt to initiate their contention-free period can be lessened by adjusting the session length used to update the NAV and IBNAV.
  • the contention-free period length is increased by a period IBCP (inter-BSS contention period) during which the access points only will attempt access of the channel using the backoff procedure, while ESTAs wait for its expiration before attempting transmission.
  • IBCP inter-BSS contention period
  • a QoS-capable centralized protocol will have traffic with different time delay requirements queued in different priority buffers. Delay-sensitive traffic will be sent first, followed by traffic with lower priority.
  • a BSS will schedule transmissions from separate queues so that the QoS requirements are met. It will transmit its top priority packets first, as described before. Once the top priority traffic has been transmitted, the BSS would attempt to transmit lower priority traffic in the CFBs allotted.
  • Three parameters are employed to help manage QoS. The deterministic backoff delay, Bkoff, and the maximum length of a CFB and of a DCF transmission. Since these parameters determine the relative allocation of the channel time between the centralized and distributed protocols, they can be adjusted to reflect the distribution of the traffic load between the two protocols. It must be kept in mind, however, that the same value of Bkoff should be used by all interfering BSSs.
  • CFBs of an access point are separated into two types, or tiers.
  • the first contains time sensitive data and is sent when the period TXdt expires.
  • the second tier contains time non-sensitive traffic and is sent when the backoff counter expires as a result of the countdown procedure.
  • EDCF transmissions can be mitigated in case (1) or prevented in case (2) through the use of the IBNAV with an IBCP.
  • Random post-backoff assigns an access point a backoff drawn from a prespecified contention window.
  • a short contention window would lead to conflicts between Tier II CFBs.
  • a long contention window reduces the conflict between interfering BSS attempting to access the channel at once.
  • Long backoff values would reduce the fraction of the time the channel ca ⁇ ies CFBs.
  • the gaps created by multiple consecutive idle slots make room for DCF transmissions, reducing further the channel time available to CFBs.
  • a long IBCP value would alleviate some of the conflict with DCF transmissions.
  • Deterministic post-backoff eliminates the problems present with random post-backoff. Conflicts with top priority EDCF transmissions can be prevented with an IBCP of 1. Moreover, as explained above, the Tier II CFBs generated by this method, do not conflict with one another and form contiguous repeating sequences.
  • Periodic transmission is achieved by maintaining a timer which is reset at the desired period TXdt as soon as the timer expires.
  • a CFB is initiated upon expiration of the timer.
  • Tier I contention-free periods are all made the same size (by adding time non-critical traffic), which is not less than the maximum DCF transmission or Tier II CFB length, it is possible for the contention-free periods of a cluster of neighboring/overlapping BSSs to repeat in the same order without a collision between them.
  • CFBs of different BSSs can be made to follow one another in a contiguous sequence, thus maximizing access of the centralized protocol to the channel. This can be seen as follows.
  • the new access point listens to the channel for the desired cycle, trying to recognize the sequence. It listens for an "idle" PIFS following a busy channel. When that occurs, or after a period TXdt, whichever comes first, the new access point starts looking for the first idle longer than PIFS, which signifies the end of the sequence of Tier I CFBs. As long as the TXdt is greater than the number of interfering BSS times the duration of a Tier I CFB, TICFBLength, there will always be such an idle period. The access point sets its timer so that it transmits always right at the end of the CFB sequence.
  • FIG. 11 illustrates this start-up procedure for a new access point, HC2, given an existing access point, HCl.
  • Arbitration times are assigned to a centralized access protocol that co-exists with ESTAs accessing the channel through E-DCF.
  • the centralized access protocol has the top priority, while E-DCF can offer traffic classes with priority access both above and below that provided by legacy stations using DCF.
  • Table 1 illustrates the parameter specification for K+l different classes according to the requirements given above.
  • the centralized access protocol is assigned the highest priority classification, and hence the shortest arbitration time.
  • the top k-1 traffic classes for the E-DCF have priority above legacy but below the centralized access protocol; they achieve differentiation through the variation of the contention window size as well as other parameters.
  • E-DCF traffic classes with priority above legacy have a lower bound, rLower, of the distribution from which backoff values are drawn that is equal to 1 or greater. Differentiation for classes with priority below legacy is achieved by increasing arbitration times; the lower bound of the random backoff distribution can be 0.
  • BSSs within short interfering range of one another can compete for and share the channel through the use of a deterministic backoff procedure employing post-backoff.
  • Contiguous repeating sequences of contention-free periods provide the centralized protocol efficient access to the channel which is shared by E-DCF transmissions.
  • the relative channel time allotted to the two protocols can be adjusted by tuning parameters of the protocol. Scheduling of traffic queued in multiple queues at the access point can meet QoS requirements. More stringent latency requirements can be met with a two-tiered method, which employs both a timer and post-backoff to initiate CFBs.
  • CFB contiguity is preserved when using deterministic post-backoff or if CFBs of constant length are used whenever transmission is caused by the expiration of the TXdt timer - the Tier I approach. Contiguity is not necessarily preserved, however, if the CFBs have variable length when the Tier I approach is used. Any gaps that would arise in this case would allow contention-based transmissions to be interjected, thus risking delays and possible collisions between HCs. Because of the fixed CFB length requirement, whereas the Tier I approach delivers regularly-spaced CFBs, using it alone, without a Tier II protocol, results in inefficient utilization of the channel. The same fixed bandwidth allocation to each BSS gives rise to situations where channel time allocated for a CFB to one BSS may be left idle while another BSS is overloaded. The Tier II protocols provide for dynamic bandwidth allocation among BSSs.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

L'invention concerne un procédé et un système permettant de réduire les interférences entre une première (150) et une deuxième (100) cellule de réseau local sans fil se chevauchant dans un milieu. Chaque cellule comporte une pluralité respective de stations membres (154 et 104), au moins une station de chevauchement occupant les deux cellules (106) à la fois. Une valeur de période exempte de contention intercellulaire est attribuée à une première station de point d'accès dans la première cellule (152). Le point d'accès (152) transmet un paquet balise contenant ladite valeur de période exempte de contention intercellulaire (124), ce paquet étant intercepté au niveau de la station de chevauchement (106) dans laquelle la valeur de période exempte de contention intercellulaire est transmise aux stations membres situées dans la deuxième cellule (104). Un deuxième point d'accès situé dans la deuxième cellule (104) peut ensuite retarder les transmissions par les stations membres dans la deuxième cellule (104), jusqu'à ce que la période exempte de contention intercellulaire se termine.
PCT/US2002/021330 2001-07-05 2002-07-02 Acces a fonction de coordination hybride (hcf) par contention progressive et limitation de cellules sans fil se chevauchant WO2003005653A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
AU2002320300A AU2002320300A1 (en) 2001-07-05 2002-07-02 Hybrid coordination function (hcf) access through tiered contention and overlapped wireless cell mitigation

Applications Claiming Priority (10)

Application Number Priority Date Filing Date Title
US30266101P 2001-07-05 2001-07-05
US60/302,661 2001-07-05
US30412201P 2001-07-11 2001-07-11
US60/304,122 2001-07-11
US31793301P 2001-09-10 2001-09-10
US60/317,933 2001-09-10
US10/187,158 US7136361B2 (en) 2001-07-05 2002-06-28 Hybrid coordination function (HCF) access through tiered contention and overlapped wireless cell mitigation
US10/187,158 2002-06-28
US10/187,132 US7277413B2 (en) 2001-07-05 2002-06-28 Hybrid coordination function (HCF) access through tiered contention and overlapped wireless cell mitigation
US10/187,132 2002-06-28

Publications (2)

Publication Number Publication Date
WO2003005653A1 true WO2003005653A1 (fr) 2003-01-16
WO2003005653A8 WO2003005653A8 (fr) 2003-07-24

Family

ID=27539172

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US2002/021330 WO2003005653A1 (fr) 2001-07-05 2002-07-02 Acces a fonction de coordination hybride (hcf) par contention progressive et limitation de cellules sans fil se chevauchant

Country Status (2)

Country Link
AU (1) AU2002320300A1 (fr)
WO (1) WO2003005653A1 (fr)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2391137A (en) * 2002-07-19 2004-01-28 Synad Technologies Ltd A dual mode access point using different wireless LAN standards
WO2005109761A1 (fr) * 2004-05-07 2005-11-17 Philips Intellectual Property & Standards Gmbh Procede de reservation distributive d'un support dans un reseau de radiocommunications
WO2007078073A1 (fr) 2006-01-05 2007-07-12 Samsung Electronics Co., Ltd. Procede et dispositif servant a transmettre une trame de controle a un noeud cache dans un reseau local sans fil
DE102006021930A1 (de) * 2006-05-11 2007-11-15 Kress, Wolfram Verfahren zur exklusiven Bevorzugung von Nachrichtentelegrammen

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5185739A (en) * 1990-02-27 1993-02-09 Motorola, Inc. Time-allocation of radio carriers
US5329531A (en) * 1993-03-06 1994-07-12 Ncr Corporation Method of accessing a communication medium
US5644576A (en) * 1994-10-26 1997-07-01 International Business Machines Corporation Medium access control scheme for wireless LAN using a variable length interleaved time division frame
US5999818A (en) * 1996-08-06 1999-12-07 Cirrus Logic, Inc. Frequency re-used and time-shared cellular communication system having multiple radio communication systems

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5185739A (en) * 1990-02-27 1993-02-09 Motorola, Inc. Time-allocation of radio carriers
US5329531A (en) * 1993-03-06 1994-07-12 Ncr Corporation Method of accessing a communication medium
US5644576A (en) * 1994-10-26 1997-07-01 International Business Machines Corporation Medium access control scheme for wireless LAN using a variable length interleaved time division frame
US5999818A (en) * 1996-08-06 1999-12-07 Cirrus Logic, Inc. Frequency re-used and time-shared cellular communication system having multiple radio communication systems

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
"Operation with overlapping point-coordinated BSSs", IEEE 802.11 STANDARD, 26 June 1997 (1997-06-26), pages 92, CHAPTER 9.3.3.2, XP002957710 *

Cited By (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2391137A (en) * 2002-07-19 2004-01-28 Synad Technologies Ltd A dual mode access point using different wireless LAN standards
GB2391137B (en) * 2002-07-19 2004-09-01 Synad Technologies Ltd Method of controlling access to a communications medium
US7710929B2 (en) 2002-07-19 2010-05-04 Synad Technologies Limited Method of controlling access to a communications medium
WO2005109761A1 (fr) * 2004-05-07 2005-11-17 Philips Intellectual Property & Standards Gmbh Procede de reservation distributive d'un support dans un reseau de radiocommunications
US8400960B2 (en) 2004-05-07 2013-03-19 Koninklijke Philips Electronics N.V. Method of distributive reservation of a medium in a radio communications network
WO2007078073A1 (fr) 2006-01-05 2007-07-12 Samsung Electronics Co., Ltd. Procede et dispositif servant a transmettre une trame de controle a un noeud cache dans un reseau local sans fil
EP1969771A4 (fr) * 2006-01-05 2012-10-03 Samsung Electronics Co Ltd Procede et dispositif servant a transmettre une trame de controle a un noeud cache dans un reseau local sans fil
EP2595443A1 (fr) * 2006-01-05 2013-05-22 Samsung Electronics Co., Ltd. Procédé et appareil de transmission de trame de commande vers un nýud caché dans un réseau local sans fil
EP3288331A1 (fr) * 2006-01-05 2018-02-28 Samsung Electronics Co., Ltd. Procédé et appareil de transmission de trame de commande vers un noud caché dans un réseau local sans fil
USRE47579E1 (en) 2006-01-05 2019-08-20 Sisvel International S.A. Method and apparatus for transmitting control frame to hidden node in wireless LAN
DE102006021930A1 (de) * 2006-05-11 2007-11-15 Kress, Wolfram Verfahren zur exklusiven Bevorzugung von Nachrichtentelegrammen
DE102006021930B4 (de) * 2006-05-11 2009-12-31 Wolfram Kress Verfahren zur exklusiven Bevorzugung von Nachrichtentelegrammen

Also Published As

Publication number Publication date
WO2003005653A8 (fr) 2003-07-24
AU2002320300A1 (en) 2003-01-21

Similar Documents

Publication Publication Date Title
US9699793B2 (en) Hybrid coordination function (HCF) access through tiered contention and overlapped wireless cell mitigation
US9420611B2 (en) Hybrid coordination function (HCF) access through tired contention and overlapped wireless cell mitigation
US9319906B2 (en) Preemptive packet for maintaining contiguity in cyclic prioritized multiple access (CPMA) contention-free sessions
US9191971B2 (en) ‘Shield’: protecting high priority channel access attempts in overlapped wireless cells
US7180905B2 (en) Access method for periodic contention-free sessions
US7983231B2 (en) Staggered startup for cyclic prioritized multiple access (CPMA) contention-free sessions
US8064415B2 (en) Fixed deterministic post-backoff for cyclic prioritized multiple access (CPMA) contention-free sessions
WO2003041343A2 (fr) Post-regression deterministe fixe pour sessions sans collision a acces multiple a priorite cyclique (cpma)
WO2003005653A1 (fr) Acces a fonction de coordination hybride (hcf) par contention progressive et limitation de cellules sans fil se chevauchant

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NO NZ OM PH PL PT RO RU SD SE SG SI SK SL TJ TM TN TR TT TZ UA UG UZ VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR IE IT LU MC NL PT SE SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
CFP Corrected version of a pamphlet front page
CR1 Correction of entry in section i

Free format text: IN PCT GAZETTE 03/2003 UNDER (30) REPLACE "NOT FURNISHED" BY "10/187,132" AND "10/187,158"

REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

122 Ep: pct application non-entry in european phase
NENP Non-entry into the national phase

Ref country code: JP

WWW Wipo information: withdrawn in national office

Country of ref document: JP