(12) Unlted States Patent
`(10) Patent No.:
`US 9,179,495 B1
`
`Scherzer et a].
`(45) Date of Patent:
`Nov. 3, 2015
`
`USOO9179495B1
`
`(54)
`
`(75)
`
`IMPLEMENTING “ALL WIRELESS”
`NETWORK OVER WIFI EQUIPMENT USING
`“SCHEDULED TDMA”
`
`_
`Inventors: Shlmon B. Scherzer, Sunnyvale, CA
`(US); Patrick A. Worfolk, Campbell,
`CA (US); Armin D_ Haken, San
`-
`.
`-
`Framsco’ CA (U? subburalal.‘
`POFEMVVamys F0 50m: CAGE): R0119“
`Valnlsh, Sunnyvale, CA (US)
`
`_
`.
`-
`(73) ASSlgnee' HEWLETT PACKARD
`DEVELOPMENT COMPANY: L-P-s
`Houston, TX (US)
`
`.
`.
`(*) Notlce.
`
`.
`.
`.
`.
`Subjectto any d1scla1mer, the term ofth1s
`Patent IS extended or adJusted under 35
`U.S.C. 154(b) by 1625 days.
`
`.
`(21) APPI‘NO" 10/615’095
`
`(22)
`
`Filed;
`
`Ju1_s,2003
`
`(51)
`
`(2009.01)
`(2009.01)
`
`Int. Cl.
`H04 W 4/00
`H04 W 84/12
`(52) U.S.Cl.
`CPC ................................... .. H04W84/12 (2013.01)
`(58) Field of Classification Search
`CPC
`H04W 84/12; H04W 84/18; H04W 74/004
`USPC """"“ 370/463’ 442’ 238’ 328; 455/533’5/55526;
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`..
`
`................ .. 455/502
`6/2003 Lundh etal.
`6,577,872 131*
`7/2005 Kato ............ N
`370/442
`6,920,148 131*
`
`8/2006 Aiello et a1.
`375/356
`7,088,795 B1 *
`. . . . . .. 455/7
`2001/0031621 A1* 10/2001 Schmutz . . . . .
`.. 455/13.4
`2001/0031624 A1* 10/2001 Schmutz
`2002/0078072 A1*
`6/2002 Tan etal.
`707/201
`2002/0105970 A1*
`8/2002 Shvodian
`370/468
`2002/0145978 A1* 10/2002 Batselletal.
`370/238
`2002/0176396 A1* 11/2002 Hammeletal.
`370/347
`2002/0196749 A1* 12/2002 Eyuboglu etal.
`........... .. 370/328
`2003/0058828 A1
`3/2003 Shearer, 111
`................. .. 370/328
`2003/0067891 A1*
`4/2003 Jones et al.
`..
`455/522
`2004/0038697 A1*
`2/2004 Attar etal.
`. . . . . .
`. . . . . .. 370/334
`2004/0052227 A1*
`3/2004 Judd etal.
`
`2004/0090312 A1*
`5/2004 Manisetal.
`.. 340/310.02
`N
`2004/0100989 A1,,
`5/2004 Chiu et al.
`..... N 370/463
`2004/0160986 A1*
`8/2004 Perlman .... ..
`370/480
`
`2004/0181569 A1*
`9/2004 Attar etal.
`..
`709/200
`..... ..
`2004/0203791A1* 10/2004 Panetal.
`455/442
`2004/0208140 A1* 10/2004 Noguchietal.
`370/328
`2005/0102529 A1*
`5/2005 Buddhikotetal.
`713/200
`2006/0056492 A1*
`3/2006 Honda ............. ..
`375/132
`
`
`
`2009/0154405 A1*
`
`6/2009 Choietal.
`
`.................. .. 370/329
`
`* cited by examiner
`
`Primary Examiner 7 Wayne Cai
`(74) Attorney, Agent, or Firm iVan Cott, Bagley, Comwall
`&McCaIthy
`(57)
`
`ABSTRACT
`
`Atechmque 1s d1sclosed to schedule frame transm1ss10ns 1n a
`wireless network utilizing scheduled TDMA by synchroniz-
`ing clocks in repeater and backhaul access points.
`19 Claims, 9 Drawing Sheets
`
`req. packet with timestamp
`10 sent
`
`network delay
`
`processmg
`delay
`
`network delay
`
`
`
`timestamped t2
`
`resp. packet with remote
`timestamp t1 created
`
`resp. pocket received and
`
`Page 1 of 19
`
`Samsung Exhibit 1038
`
`Page 1 of 19
`
`Samsung Exhibit 1038
`
`

`

`US. Patent
`
`Nov. 3, 2015
`
`Sheet 1 019
`
`US 9,179,495 B1
`
`10
`
`IO
`
`10
`
`Chonnel#2
`
`AP#3
`Chonnd#3
`
`AP#4
`Channd#1
`
`
` AP#4
`
`
`
`Chonnd#1
`
`Channd#2
`
`FTC}.
`
`llk
`
`
`
`FTC}.
`
`113
`
`PRIOR ART
`
`Page 2 of 19
`
`Page 2 of 19
`
`

`

`US. Patent
`
`Nov. 3, 2015
`
`Sheet 2 of9
`
`US 9,179,495 B1
`
`
`
`Page 3 of 19
`
`Page 3 of 19
`
`

`

`US. Patent
`
`Nov. 3, 2015
`
`Sheet 3 of9
`
`US 9,179,495 B1
`
`req. packet with timestamp
`t0 sent
`
`network delay
`
`PI'OCBSSIng
`delay
`
`network delay
`
`timestamped t2
`
`resp. pocket with remote
`timestomp t1 created
`
`resp. pocket received and
`
`FIG. 3
`
`Page 4 of 19
`
`Page 4 of 19
`
`

`

`U.S. Patent
`
`Nov. 3, 2015
`
`Sheet 4 of 9
`
`US 9,179,495 B1
`
`
`
`Receive Data Set
`(to.t1.t2)
`
`
`
`Store (trt.tr.ta)
`
`Y5
`Shutdown
`
`
`
`FIG. 4A
`
`Page 5 of 19
`
`Page 5 of 19
`
`

`

`U.S. Patent
`
`Nov. 3, 2015
`
`Sheet 5 of9
`
`US 9,179,495 B1
`
`
`
`N Recent Sets of
`{trbtr’tA‘
`
`450
`
`FIG. 4B
`
`Page 6 of 19
`
`Page 6 of 19
`
`

`

`US. Patent
`
`Nov. 3, 2015
`
`Sheet 6 of9
`
`US 9,179,495 B1
`
`
`From APs
`
`Collect Time Reports
`
`500
`
`Page 7 of 19
`
`Page 7 of 19
`
`

`

`U.S. Patent
`
`Nov. 3, 2015
`
`Sheet 7 of9
`
`US 9,179,495 B1
`
`§
`
`r
`
`7
`
`v
`
`/ f,
`
`216—1
`Bockhoul #1
`
`216-2
`
`Bockhoul #2 E
`
`-1
`
`Rep2e102ter #1
`
`Reggie? #2
`
`210—1
`
`Client #2
`
`210—2
`Client #2
`
`216—1
`Backhaul #1
`
`Client #2
`
`_:.:,:_:_
`
`:EE
`55%
`
`212—1
`
`21 6- 2
`Backhaul #2
`Repeater #1
`Repeater #2
`
`212—2
`
`210—1
`
`Client #2
`
`210—2
`
`Page 8 of 19
`
`Page 8 of 19
`
`

`

`U.S. Patent
`
`Nov. 3, 2015
`
`Sheet 8 of 9
`
`US 9,179,495 B1
`
`:85
`
`E26
`
`Swan11Q
`
`mmm
`
` h“‘3
`
`m.wE
`
`Page 9 of 19
`
`Page 9 of 19
`
`

`

`US. Patent
`
`Nov. 3, 2015
`
`Sheet 9 of9
`
`US 9,179,495 B1
`
`Outbound (Downlink)
`
`Inbound (Uplink)
`
`B22
`
`I
`I
`I
`i
`i
`I
`:
`I
`B12 B13
`BO 80 B11
`BO
`1 \/euao so
`so
`
`B12
`824
`
`B12
`823
`
`B11
`B22
`
`B13
`821
`
`B12
`824
`
`B22
`B11
`
`B24
`812
`
`821
`B13
`
`B21
`B31
`
`823
`B36
`
`B22
`B33
`
`B24
`B37
`
`823
`B35
`
`B31
`B21
`
`B33
`
`Page 10 0f 19
`
`Page 10 of 19
`
`

`

`US 9,179,495 B1
`
`1
`IMPLEMENTING “ALL WIRELESS”
`NETWORK OVER WIFI EQUIPMENT USING
`“SCHEDULED TDMA”
`
`BACKGROUND
`
`1. Field of the Invention
`
`The present invention relates to wireless networks, and
`more particularly, to the benefits of scheduling transmissions
`in such networks.
`2. Related Art
`
`Wireless local networks (WLANs) based on the IEEE
`802.11 standard have proven to be popular. IEEE 802.11 is a
`wireless standard related to the IEEE 802.3 standard estab-
`lished for wired Ethernets. In contrast to wired networks, an
`IEEE 802.11 WLAN must conserve the limited bandwidth
`
`presented by a wireless transmission medium. Accordingly, a
`set of rules in the IEEE 802.11 standard is dedicated to
`
`medium access control (MAC), which governs accessing the
`wireless medium and sending data through it.
`The 802.11 rigidity and power allocation limits present
`severe challenges to users during network deployment and
`modification. Even if careful network planning is imple-
`mented, there may still be loss of bandwidth due to unpre-
`dictable circumstances such as a subscriber’s movement and
`
`activity level. Further, with existing WiFi chipsets, bandwidth
`may not be fully utilized due to various factors, including
`unpredictable communication trafiic and “hidden node” situ-
`ations (which will be described below).
`For example, FIG. 1A illustrates an ideal situation where
`each cell 10 has a circular coverage area. However, in reality,
`the coverage area of each cell 10 is not a circle. For example,
`in an enterprise application, such as in a building with large
`numbers of walls and offices, numerous APs and STAs are
`needed to allow STAs to transfer information between each
`other. The walls and other barriers result in non-uniform
`
`coverage areas for each cell 10.
`FIG. 1B shows coverage areas or cells 20 in a practical
`WLAN environment. As seen, the coverage areas are no
`longer uniform circles, but are irregular having areas of
`broader coverage (the peaks) and areas of lower coverage (the
`nulls). For example, long peaks 25 may correspond to long
`hallways in the building. Because cells 20 do not have uni-
`form coverage, “holes” 30 exist in the network, where com-
`munication is not possible. Holes 30 do not necessarily rep-
`resent areas where no frames can be sent and received;
`however, only a small percentage of dropped frames may be
`enough severely disrupt TCP/IP behavior, thereby effectively
`ending communication ability within that area.
`A possible solution to “fill” holes 30 may be to increase the
`density of the APs in the WLAN, i.e., move the APs closer to
`each other, which requires more APs for the same outer cov-
`erage area. However, increasing the density of the APs will
`result in increased interference betweenAPs and STAs, while
`also increasing the cost of the system. Consequently, in order
`to reduce interference, the transmit power of the APs must be
`reduced. But, this may again result in holes in the WLAN
`coverage due to irregular coverage “footprints” of the APs at
`an additional cost of a reduction in maximum throughput of
`the system.
`Thus, even if throughput can be increased, the network
`operator must continually adjust parameters of the WiFi net-
`work, such as power, frequency, and location. This increases
`the complexity in setting up and maintaining an optimal net-
`work.
`
`Another challenge in deploying WiFi networks is the need
`for wiring. Each access point must be fed by a wire through
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`regular network infrastructure. Even when LAN wiring
`already exists, it seldom fits the specific needs of radio based
`network, e.g., connecting socket locations are normally at
`lower sections ofthe walls while the location of access points
`is desired to be at the highest places (for better radio cover-
`age). In many cases, people prefer to segregate the radio
`network from the wire-line network for security reasons. If
`the radio network could be supported by wireless backhaul
`instead, deployment could be less expensive and flexible.
`Significant amount of art has been published relative to this
`subject, such as mesh networks. However, mesh networks or
`any wireless backhaul that relies on native 802.11 standards
`suffers from prohibitive bandwidth loss. When one node in
`such a network is active, all other nodes around it must be
`silent, hence unable to communicate. A method to increase
`the transmission efficiency by overcoming this shortfall is
`required to implement efficient wireless backhaul. The defi-
`ciencies of WiFi in producing multi-hop (“mesh networks”)
`have been described in many papers. An example is “Reveal-
`ing the Problems of 802.1 1 MediumAccess Control in Multi-
`hop Wireless Ad Hoc Networks” by Shugong Xu and Tarek
`Saabdawi, published in “Computer Networks” magazine in
`2002, that emphasized particularly the difficulties of TCP/IP
`in this environment.
`
`In general, ad hoc, distributed control wireless networks, in
`particular 802.11 based, are not very suitable to multi-hop
`communications. An example of shared media (point-to-mul-
`tipoint) based protocol that is used is the cable modem stan-
`dard (DOCSIS). This protocol is a clear example of central-
`ized control in shared media. Elements of this protocol were
`adopted by the WWAN industry (802.16).
`Accordingly, there is a need in the art for improved tech-
`niques for scheduling transmissions in wireless networks,
`such as WiFi, that avoids the disadvantages of conventional
`methods discussed above.
`
`SUMMARY
`
`In accordance with one aspect of the invention, a wireless
`local area network (WLAN) includes a plurality of stations
`(STAs), a plurality ofrepeater access points (APs), a plurality
`of backhaul APS, and a central controller. The repeater APs
`incorporate two transceivers of two different WiFi bands
`(e.g., 2.4 GHz and 5 GHz) that are able to communicate
`between themselves to create a network bridge. This bridge
`allows information received by one transceiver to be sent to
`the second transceiver, which in return can send information
`to another transceiver (e.g., a station or another AP). The
`backhaul APs can be identical to the repeater APs or simple,
`single transceiver APs. The central controller and backhaul
`APs may reside in the network closet, where the backhaul
`APs are further grouped together. The central controller
`schedules the transmissions between backhaul APs and
`
`repeater APs, between repeater APs and other repeater APs,
`and between repeater APs and STAs.
`The present invention allows multiple WiFi transceivers to
`transmit at the same time by synchronizing access points
`across the network and using scheduled TDMA. The central
`controller, based on network traffic, can schedule more or
`longer transmission slots for one AP than for another AP
`during any time interval. Further, based on various network
`and transmission characteristics, the central controller may
`determine which transceivers may transmit simultaneously at
`which times.
`
`Scheduled TDMA is defined as methods of making WiFi
`transceivers operate in time division multiple access (TDMA)
`and, by synchronizing all access points in the network, one
`
`Page 11 of19
`
`Page 11 of 19
`
`

`

`US 9,179,495 B1
`
`3
`can force multiple transceivers to transmit at the same time.
`By re-packing data, transmissions can be divided into time
`slots of equal or of variable length. Knowing which transmis-
`sions can co-exist without interfering with each other (spatial
`compatibility) allows the system controller to determine
`which transmissions may execute in parallel. A detailed
`description of this method is described in commonly-owned
`US. patent application Ser. No. 10/306,972, entitled “Space-
`Time-Power Scheduling For Wireless Networks”, filed Nov.
`27, 2002. The central controller may grant transmission slots
`as necessary based on traffic to be delivered. For example, if
`a first AP has more data to transmit and a second AP does not,
`the central controller can grant more transmission slots or
`longer transmission slots to the first AP.
`Scheduled TDMA may also be utilized for wireless back-
`haul. A central controller may schedule simultaneous trans-
`missions inward to or outward from a backhaul AP at the
`
`center or nexus of a network. This network has repeater APs
`that can be viewed as a series of concentric circles or spheres
`about the center. The repeaterAPs may have bands that can be
`used for backhaul and bands that can be used for communi-
`
`cation with STAs. Since non-interfering simultaneous trans-
`missions in one direction can be determined, multiple such
`transmissions can be scheduled within the network to
`
`increase network throughput. Several such networks can
`share the same physical space. Each network operates on a
`single frequency channel, such that when simultaneous trans-
`missions are not possible in one network, the transmissions
`can be scheduled or moved to another network operating on a
`different frequency channel.
`In one embodiment, communication between the repeater
`APs and backhaul APs 216 is by scheduled TDMA, while
`communication between both APs and the STAs is a mix of
`
`10
`
`15
`
`20
`
`25
`
`30
`
`scheduled TDMA and standard WiFi (e.g., DCF). Another
`embodiment uses scheduled TDMA between backhaul APs
`
`35
`
`and repeater APs and standard 802.11 between repeater APs
`and clients. In addition, transmission can be unidirectional,
`i.e., no separate ACK packet per frame, instead accumulating
`the ACKs within a message that is going in the opposite
`direction. This method increases the probability of finding
`concurrent connections. When scheduled TDMA is used as
`for the first embodiment, the central controller schedules the
`transmissions on the backhauls and between repeaters APs
`and STAs. When standard 802.11 is used between repeater
`APs and clients, the central controller schedules only the
`connections between the backhaul and repeater APs. The
`central controller synchronizes the clocks ofthe APs so that it
`can schedule (or grant) and allocate time slots.
`Although wireless backhaul techniques are well known in
`the art (e.g., “multi-hop networ ” and mesh networks as
`mentioned above), these methods are very unsuitable for
`standard 802.11-based networks. Any node that is transmit-
`ting will silence any nodes in its reach, while any node receiv-
`ing requires all nodes in reach to be silenced as well. This
`means that only a small fraction of the network nodes can be
`active, thereby significantly reducing network bandwidth and
`rendering the wireless backhaul essentially useless. Sched-
`uled TDMA (e.g., capitalizing on RF Routing technology,
`which is described in commonly-owned US. patent applica-
`tion Ser. No. 10/306,972, incorporated above) alleviates this
`problem, allowing backhaul efficiency to be very high (ap-
`proaching 100%). Backhaul efficiency is defined as the per-
`centage of time data is streaming on the network backhaul.
`For example, ifwhen every time a repeater AP connected to a
`network backhaul AP is transmitting, the backhaul AP must
`not transmit, the best efficiency that can be achieved is 50%.
`The proposed approach using AP synchronization and sched-
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`uled TDMA on top of 802.1 1 PHY allows all APs to transmit
`together, hence the efficiency increase.
`This approach will allow fast and easy deployment of
`WLAN. Whenever more bandwidth is needed, the user may
`add additional access points to the network without the need
`for detailed planning and wiring. Further, the APs of the
`present invention do not need to be continually adjusted, such
`as continually monitoring and adjusting transmission power
`levels for the APs. In one embodiment, the power level of the
`APs is maintained at the maximum.
`
`Other advantages provided by the present invention are 1)
`easy deployment, since network devices, such as APs, are
`standard off-the-shelf components that may only require
`minor modifications, 2) larger number of concurrent trans-
`missions in the network, 3) increased expected data rate for
`clients, 4) reduction in data rate fallback loss (normally expe-
`rienced in closed loop rate control), 5) more efficient trans-
`mission power control for the STAs, 6) less effect of external
`interference, 7) easier packet fragmentation and transmission
`re-tries, and 8) reduced power required by the stations.
`The invention will be more fully understood upon consid-
`eration of the following detailed description, taken together
`with the accompanying drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1A illustrates cells with theoretical footprints for a
`conventional WLAN;
`FIG. 1B illustrates an example of cells with realistic foot-
`prints in an enterprise;
`FIG. 2 is a block diagram of a wireless LAN according to
`one embodiment of the invention;
`FIG. 3 is shows the timing of time synchronization request
`and response packets according to one embodiment;
`FIGS. 4A and 4B are flowcharts illustrating an example of
`coarse time synchronization;
`FIG. 5 is a flowchart illustrating an example of fine time
`synchronization according to one embodiment;
`FIG. 6 is a time-line representation oftransmission slots of
`using a single band;
`FIG. 7 is a time-line representation of transmission slots
`using two bands, according to one embodiment;
`FIG. 8 is a diagram ofa backhaul network topology accord-
`ing to one embodiment; and
`FIG. 9 is a timing diagram showing examples of transmis-
`sion slots from the bridges of FIG. 8.
`Use of the same or similar reference numbers in different
`
`figures indicates same or like elements.
`
`DETAILED DESCRIPTION
`
`In accordance with one aspect of the invention, a time
`division multiple access (TDMA) based method is used to
`schedule transmissions in a wireless network, such as 802.1 1
`or WiFi. Data traffic through the network is scheduled for
`specific time slots so that only those sets of links that can
`share the wireless medium are active simultaneously and all
`traffic is granted time to reach its destination.
`FIG. 2 shows a block diagram of a wireless LAN network
`200 that utilizes TDMA scheduling according to one embodi-
`ment of the present invention. A network closet or center 202
`includes a central controller 204, a switch 206, and an access
`point (AP) stack 208 (backhaulAPs). In another embodiment,
`backhaul APs are located in different locations, i.e., not col-
`located. Network closet 202 may be located at a suitable
`location in the network or enterprise, such as within a closet,
`on a roof, or on a ceiling, to provide sufficient coverage for
`
`Page 12 of 19
`
`Page 12 of 19
`
`

`

`US 9,179,495 B1
`
`5
`clients, stations (STAs), or users 210 within network 200.
`Central controller 204 (1) collects received signal strength
`information (RSSI) from repeater access points (or AP trans-
`ceivers) 212 for each STA or AP heard, (2) estimates the RF
`reception conditions at the STAs and APs if certain transmis-
`sions are to be executed, (3) collects information about data
`traffic load based on monitoring the APs as well as monitoring
`the data traffic that is in some embodiments routed through
`the controller,
`(4) schedules transmission opportunities
`(slots) from APs and STAs based on traffic distribution and
`anticipated carrier to interference and noise ratio (CINR) to
`maximize the CINR conditions at receive points, number of
`concurrent transmis sions, and hence network throughput, and
`(5) pre-assigns transmission data rate per frame to avoid data
`rate fallback. Central controller 204 may also be referred to as
`a router, an RF router, or radio processor and is described in
`commonly-owned US. patent application Ser. No. 10/306,
`972, entitled “SPACE-TIME-POWER SCHEDULING FOR
`WIRELESS NETWORKS”, by Shimon Scherzer and Patrick
`Worfolk, incorporated by reference in its entirety. Central
`controller 204 allows a standard 802.11 multiple APs based
`network to be modified and operate as a scheduled TDMA
`based network, as will be described in detail below.
`A multi-hop network, such as described above, presents
`some unique problems if based on standard 802.11 technol-
`ogy. To facilitate connectivity among access points (e.g.,
`repeaterAPs 212 and backhaul APs 216) within network 200,
`the typical distance between these access points must be
`similar to the distance between the access points (212 or 216)
`and clients or STAs 210. As a result, network cells (or BSSs)
`are greatly overlapping. Consequently, unless exotic antenna
`techniques are employed, network bandwidth is expected to
`be rather small, since each time a network transceiver trans-
`mits, all the transceivers that “hear” the transmitting trans-
`ceiver must not transmit. Since there is significant BSS over-
`lap, the probability of any transceiver to be transmitting is
`very low, resulting in poor network bandwidth.
`Transmission coordination of the present invention miti-
`gates the above shortcomings. Central controller 204 is used
`to schedule transmissions based on estimated signal condi-
`tions (C/I) at the designated receivers, hence allowing many
`more concurrent transmissions than in a standard 802.11
`
`network. The scheduling is designed to maximize the net-
`work throughput at all times by first checking which trans-
`missions can be executed simultaneously. Simultaneous
`transmission requires AP clock synchronization, as detailed
`below. Otherwise,
`since multiple transmissions can be
`detected by the wireless MAC module within typically a few
`usecs, transmissions may cease unless AP time synchroniza-
`tion is within that range.
`The data transmission time slots are dynamically assigned
`by the central controller to combinations of wireless connec-
`tions which can be active simultaneously. The assignment is
`based on various factors, such as load, delay, and traffic.
`Traffic and delay are monitored by collecting reports from the
`APs and can also be monitored directly in those embodiments
`where the data traffic passes through the central controller. In
`one embodiment, all the slot lengths are equal and the slots
`are filled according to the amount of data queued for a par-
`ticular destination. In another embodiment, the slot assign-
`ments are somewhat randomized to avoid repetition of unfa-
`vorable combinations.
`
`The slots can also be made different lengths, corresponding
`to the data traffic that needs to be sent by those connections
`granted use of the slot time. Given a collection of sets of
`connections such that each set is capable of having all its
`connections simultaneously active without mutual interfer-
`
`6
`ence, a schedule can be computed using a linear programming
`algorithm (known to those familiar with the art). For example,
`let S1 to S" be the sets of simultaneously feasible connections.
`Each set S will be granted a corresponding slot time ai. The
`lengths of slot time al. are constrained to be long enough to
`permit the required amount of data to be sent along the con-
`nections activated in Si. Linear programming is used to mini-
`mize the sum of the lengths al. for i between 1 and 11, subject to
`these constraints. The resulting slot lengths are in the most
`efficient ratio to each other. The system can make best use of
`the slot lengths when the data packets are aggregated for
`transmission between the APs as explained later.
`Once central controller 204 receives and processes the
`required information (as described above), the schedules and
`other control information is sent via switch 206 coupled to
`central controller 204 to AP stack 208. In some embodiments,
`all external data traffic from and to the APs and stations
`
`10
`
`15
`
`travels through the central controller and the switch, which
`provides layer 2 connection between the central controller
`and the APs.
`
`20
`
`25
`
`30
`
`A plurality of APs 216 (or backhaul APs) are stacked or
`co-located within AP stack 208. When 802.11(a) is used for
`backhaul, twelve APs 216 can be stacked; however, if 802. 11
`(b) or 802.11(g) is used, three APs 216 can be stacked. Note
`that AP stack 208 does not need to be a physically confining
`device. In one embodiment, each AP 216 (or AP transceiver)
`is a standard off-the-shelf 802.11 device. Each AP 216 is
`
`tuned to a different frequency channel, with the number
`depending on whether the AP is an 802.11(a) or 802.11(b)
`device. Thus, multiple channels can be used for backhaul
`connectivity to the repeater APs 212. When the backhaul APs
`are not collocated, the channel limits are eliminated and there
`is no constraint on the number of backhaul APs. Communi-
`
`35
`
`cation between repeater APs 212 and backhaul APs 216 is by
`TDMA, while communication between APs (212 or 216) and
`STAs 210 is a mix of scheduled TDMA and standard WiFi
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`(DCF). Thus, a wireless LAN can be deployed by grouping
`backhaul access points in the network main closet or spread-
`ing backhaul access points around the establishment wired to
`the main closet, each set on a different frequency channel, to
`feed repeaters access points that replace the traditional wired
`access points to form a wireless connection.
`Each backhaul AP 216 in AP stack 208 may use high gain,
`directional antennas to communicate with repeater APs 212
`to maximize range and minimize interference. In one embodi-
`ment, an antenna with a gain of 15 dBi and about 30° beam
`width is used, although other antennas may be suitable. Since
`the connection between backhaul APs 216 and repeater APs
`212 is effectively “point-to-point”, effective radiated power
`(ERP) can be substantially higher, thereby increasing the
`backhaul range and allowing higher data rates and better
`penetration.
`RepeaterAPs 212 can also be standard off-the-shelf802.11
`access points, modified to serve as “wireless-to-wireless
`bridges” between the STAs and backhaul APs. The trans-
`ceiver for repeater APs 212 can be used for both backhaul and
`for communication with STAs 210 (also referred to herein as
`client serving). Each AP 212 and/or 216 may communicate
`with a plurality of N stations (STAs). STAs may include
`laptop PCs and handheld devices, such as PDAs. These
`devices can be mobile, portable, or stationary. AP devices also
`contain an 802.1 1 conformant MAC and PHY interface to the
`
`wireless medium and provide access to a distribution system
`for associated stations.
`
`In one embodiment, repeater APs 212 have two radios
`(e.g., an 802.11(a) and an 802.11(b)), one used for backhaul
`communication and one for client serving or communication.
`
`Page13 of 19
`
`Page 13 of 19
`
`

`

`US 9,179,495 B1
`
`8
`variation in message latency, thereby make the synchroniza-
`tion process much more difficult.
`According to one embodiment of the invention, a first
`“coarse” time synchronization is obtained through an Ether-
`net connection. Central controller 204 is connected to back-
`
`haul access points 208 and repeater access points 212. Peri-
`odically, each AP 208 and 212 will
`receive a time
`synchronization request
`(Time_Synch_Req) packet from
`central controller 204. In one embodiment, central controller
`204 sends five packets per second. In response, the specific
`access point (either backhaul AP 208 or repeater AP 212)
`responds with a synchronization response (Time_Synch_
`Resp) packet. As a result of this interchange, central control-
`ler 204 obtains three time stamp values: 1) the time t0 the
`query (Time_Synch_Reqpacket) was sent, 2) the local time t 1
`at the access point when the response (Time_Synch_Resp
`packet) was generated, and 3) the arrival time t2 of the
`response. When the clocks are synchronized and when the
`round trip time of the interchange is short, the second time
`stamp value is expected to be in the middle between the first
`and third time stamps, as shown in FIG. 3. However, practi-
`cally, factors, such as channel variations, processing delays,
`and communication traffic, introduce delays that shift the
`second time stamp from the middle.
`Central controller 204 stores a number N (120 in one
`embodiment) of the most recent sets of time stamps and
`calculates the AP clock offset (i.e., the time difference at the
`sampled instance) and clock skew (i.e.,
`the difference
`between “ticking” rate of the clocks). Periodically, central
`controller 204 sends a time set command (Time_Synch_Set)
`packet to the AP instructing how to adjust its local clock. The
`period can be after intervals in which central controller 204
`has determined adjustments, if any, to the clock offset and
`skew, as discussed below. In response, the AP then sends an
`acknowledgement (Time_Synch_Set_Ack) and makes the
`necessary adjustments for time synchronization.
`In one embodiment, the calculations required to keep the
`clocks in the APs adjusted are performed in central controller
`204, such as by a synchronization module. This allows sim-
`plifying the process within the APs, thereby providing the
`advantages of simpler deployment, fewer processor cycles
`used at the AP, and easier tuning and change to the synchro-
`nization algorithm once the networks are deployed. Calcula-
`tions may also be performed within the APs or an external
`processor. Central controller 204 operates individually on
`each AP that
`it
`is synchronizing and sends individually
`directed Time_Synch_Req packets. In other embodiments,
`the packets may be sent by broadcasting or multicasting;
`however, this may cause queuing delays.
`Regardless of how the packets are sent and received, cen-
`tral controller 204 obtains the most recent N (N:120 in one
`embodiment) sets of time stamps for an AP and generates an
`estimate of the time difference and clock skew at the AP. The
`
`information contained in each set of time stamps allows cen-
`tral controller 204 to calculate the total communication or
`
`round trip time t”, a reference time t,, the AP’s time tAP, and
`
`
`the time difference t
`as follows:
`
`r 2
`
`l 2:12—10
`
`,:(z0+z2)/2
`
`l2113:11
`
`zfl:zl—z,
`
`FIGS. 4A and 4B are flowcharts showing one embodiment
`for determining the AP clock offset and skew. FIG. 4A is a
`
`7
`Because each repeater AP 212 may be used for different
`communications to different devices, as seen in FIG. 2,
`repeater APs 212 may use two different antennas for the
`different communications. In one embodiment, repeater APs
`212 utilize an antenna that is omni-directional (used for client
`serving) and a high directional antenna aimed at backhaul
`APs 216 (used for backhaul communication). In one embodi-
`ment, the high directional antenna for repeater AP 212 is
`similar to the ones used with transceivers ofthe backhaul APs
`
`described above. With networks in which repeater APs 212
`operate in dual-band, i.e., capability for both 802.11(a) and
`802. 1 1 (b), backhaul communication can be handled through
`802. 1 1 (a) and client communication can be handled through
`802.11(b), in one embodiment. Other channel assignments
`may also be suitable for the present invention.
`However,
`in conventional systems, collocated multiple
`channel operation is not practical due to issues such as inter-
`channel interference, even if different frequency channels are
`used. The present invention uses central controller 204 to
`synchronize AP transmissions,
`thereby minimizing inter-
`channel interference and allowing simultaneous multi-chan-
`nel transmissions. Besides synchronizing the transmissions
`between the APs, the present invention specifies that the data
`can be packed efiiciently into the allocated transmission time
`slots. By combining the data from IP packets and pieces of IP
`packets, a specific amount of transmission time can be effi-
`ciently used for a unidirectional transmission. An acknowl-
`edgement and possible request for re-transmission of part of
`the data can be returned later. Unidirectional transmissions,
`not interleaved with returning acknowledgement packets are
`much more amenable to simultaneous non-interference than
`the standard 802.1 1 transmissions. For the transmission to the
`
`stations or back into the wire, the packets are reassembled
`back into their original lengths.
`A further reason time synchronization is needed is due to
`the fact that when multiple access points are collocated, such
`as within AP stack 208, transmission on one channel may
`hamper transmission on another channel due to “RF leakage”,
`i.e., the modulation spectrum tends to spread into other fre-
`quency channels. So, even though 802.11(a) may use man