US009179495B1
`
`a2) United States Patent
`US 9,179,495 B1
`(10) Patent No.:
`Nov.3, 2015
`(45) Date of Patent:
`Scherzeret al.
`
`
`(54)
`
`IMPLEMENTING “ALL WIRELESS”
`NETWORK OVER WIFI EQUIPMENT USING
`“SCHEDULED TDMA”
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`(75)
`
`onnuswamy, Folsom,CA(US); Ronen 2002/0105970 Al* 8/2002 Shvodian .... ".. 370/468
`
`:
`.
`7
`(73) Assignee: HEWLETT-PACKARD
`DEVELOPMENT COMPANY, L.P.,
`Houston, TX (US)
`
`ae
`+
`(*) Notice:
`
`:
`:
`:
`:
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1625 days.
`
`.
`(21) Appl. No.: 10/615,095
`
`(22)
`
`Filed:
`
`Jul. 8, 2003
`
`6/2003 Lundhetal. ow. 455/502
`6,577,872 B1*
`.
`7/2005 Kato wc.
`.. 370/442
`6,920,148 BI*
`Inventors: Shimon B. Scherzer, Sunnyvale, CA
`
`8/2006 Aiello etal.
`1. 375/356
`7,088,795 B1*
`(US); Patrick A. Worfolk, Campbell,
`2001/0031621 AL* 10/2001 Schmutz wesc 455/7
`CA (US); Armin D. Haken, San
`2001/0031624 A1* 10/2001 Schmutz .....
`.. 455/13.4
`:
`.
`.
`
`2002/0078072 AL*
`praneisco CA we): Supburajan
`707/201
`6/2002 Tanetal.
`....
`
`
`
`
`.. 370/238
`Vainish, Sunnyvale, CA (US)
`2002/0145978 Al* 10/2002 Batsell et al.
`..
`... 370/347
`2002/0176396 A1* 11/2002 Hammel etal.
`...
`
`2002/0196749 AL* 12/2002 Eyuboglu et al. 0... 370/328
`2003/0058828 Al
`3/2003 Shearer, III
`...cscccseeeen 370/328
`2003/0067891 AL*
`4/2003 Jones et al.
`2004/0038697 Al*
`2/2004 Attar et al.
`..
`wo. 455/522
`
`2004/0052227 A1l*
`3/2004 Juddetal. we 370/334
`2004/0090312 Al*
`5/2004 Manisetal.
`...
`.. 340/310.02
`5/2004 Chiuetal. 370/463
`3004/0100089 Al*
`
`2004/0160986 A1*
`8/2004 Perlman ......
`... 370/480
`
`2004/0181569 Al*
`9/2004 Attar etal.
`..
`.. 709/200
`2004/0203791 A1* 10/2004 Panetal.
`.......
`... 455/442
`...
`2004/0208140 Al* 10/2004 Noguchi etal.
`... 370/328
`w. 713/200
`2005/0102529 Al*
`5/2005 Buddhikot et al.
`
`... 375/132
`2006/0056492 A1l*
`3/2006 Honda............
`6/2009 Choietal. woe 370/329
`2009/0154405 A1*
`* cited by examiner
`
`(51)
`
`Int. Cl.
`HOAW 4/00
`HOAW 84/12
`(52) US.CL
`CPC ceccccccccccesertestereretseenees HO4W 84/12 (2013.01)
`(58) Field of Classification Search
`CPC .... HO4W 84/12: HO4W 84/18: HO4Ww 74/004
`USPC
`370/463. 442. 238. 328: 455/522. 502:
`vereeseees
`?
`?
`?
`?
`375zB56
`See application file for complete search history.
`
`(2009.01)
`(2009.01)
`
`Primary Examiner — Wayne Cai
`(74) Attorney, Agent, or Firm — Van Cott, Bagley, Cornwall
`& McCarthy
`ABSTRACT
`(57)
`er
`oe,
`Atechnique is disclosed to schedule frame transmissions ina
`wireless network utilizing scheduled TDMAbysynchroniz-
`ing clocks in repeater and backhaul access points.
`19 Claims, 9 Drawing Sheets
`
`req. packet with timestamp
`t0 sent
`
`
`
`resp.
`packet with remote
`fimestomp tl created
`
`resp. packet received and
`timestamped t2
`
`network delay
`
`:
`Prdelay
`
`network delay
`
`
`
`a
`
`Page 1 of 19
`
`Samsung Exhibit 1038
`
`Page 1 of 19
`
`Samsung Exhibit 1038
`
`

`

`U.S. Patent
`
`Nov. 3, 2015
`
`Sheet 1 of 9
`
`US 9,179,495 B1
`
`FIG. 1A
`
`
`
`
`FIG. 1B
`
`PRIOR ART
`
`Page 2 of 19
`
`Page 2 of 19
`
`

`

`U.S. Patent
`
`Nov. 3, 2015
`
`Sheet 2 of 9
`
`US 9,179,495 B1
`
`
` Client
`
`\200
`
`
`
`Ko aBo
`
`Page 3 of 19
`
`Page 3 of 19
`
`

`

`U.S. Patent
`
`Nov. 3, 2015
`
`Sheet 3 of 9
`
`US 9,179,495 B1
`
`req. packet with timestamp
`0 sent
`
`network delay
`
`processing
`delay
`
`network delay
`
`timestamped t2
`
`resp. packet with remote
`timestamp tl created
`
`resp. packet 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
`
`trt,min = 1 hour
`
`
`
`to, ty. t2
`Receive Data Set
`
`
` tr =t2- to
`tr = (tot t2)/2
`ta = ty- tr
`
`
`
`
`System
`
`Shutdown
`
`
`
`FIG. 4A
`
`Page 5 of 19
`
`Page 5 of 19
`
`

`

`U.S. Patent
`
`Nov. 3, 2015
`
`Sheet 5 of 9
`
`US 9,179,495 B1
`
`
`
`N Recent Sets of
`{trttr, ta}
`
`450
`
`
`Wace = Wace + Wi
`
`Yace = Yace + Wi: tai
`
`FIG. 4B
`
`Page 6 of 19
`
`Page 6 of 19
`
`

`

`U.S. Patent
`
`Nov. 3, 2015
`
`Sheet 6 of 9
`
`US 9,179,495 B1
`
`
`
`Collect Time Reports
`From APs
`
`900
`
`
`
`Calculate Avg.
`
`time, t ref
`
`504
`
`506
`
`tref, ty = tsk—tref
`
`
`
`908
`
`Page 7 of 19
`
`Page 7 of 19
`
`

`

`U.S. Patent
`
`Nov.3, 2015
`
`Sheet 7 of 9
`
`US 9,179,495 B1
`
`216-1
`Backhaul #1
`
`216-2
`Backhaul #2
`
`212-1
`Repeater #1
`
`Repeater #2
`
`210-1
`Client #2
`
`210-2
`Client #2
`
`Z
`
`WU
`
`Y
`
`Client #2
`
`216-1
`Backhaul #1
`216-2
`oe
`Sa
`Backhaul #2
`ke
`3
`Repeater WO.CALL
`watp WAMIDWA\|CA
`client#2
`
`3
`3
`
`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
`
`qualvedPa\oe~~<P
`
`8“Old
`
`Page 9 of 19
`
`Page 9 of 19
`
`
`

`

`U.S. Patent
`
`Nov. 3, 2015
`
`Sheet 9 of 9
`
`US 9,179,495 B1
`
`Qutbound (Downlink)
`
`Inbound (Uplink)
`
`BON
`VEN
`
`30 YYZ7RN BI? B13
`B12 YerANBON
`80
`BOY
`
`
`
`Bi2|B12 Bi3|B12Bl1| B22} B24 B21
`
`
`
`
`
`
`
`
`B24] B21|B24 Bll|Bt2B23 B22| B13
`
`
`
`BOS | BS7
`
`| B55
`
`| B21|
`
`
`
`B22
`
`B21} B22|B24|B23B23 B31 B33
`
`
`
`BSI
`
`
`
`B56
`
`FIG. 9
`
`Page 10 of 19
`
`Page 10 of 19
`
`

`

`US 9,179,495 B1
`
`1
`IMPLEMENTING “ALL WIRELESS”
`NETWORK OVER WIFT EQUIPMENT USING
`“SCHEDULED TDMA”
`
`BACKGROUND
`
`1. Field of the Invention
`
`The present invention relates to wireless networks, and
`moreparticularly, 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 throughit.
`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 maystill 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 communicationtraffic 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 STAsare
`needed to allow STAsto 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
`WLANenvironment. 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
`enoughseverely disrupt TCP/IP behavior, thereby effectively
`ending communication ability within that area.
`A possible solutionto “fill” holes 30 may be to increase the
`density of the APs in the WLAN,i.e., move the APscloser 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 between APs 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 WiFinet-
`work, such as power, frequency, and location. This increases
`the complexity in setting up and maintaining an optimalnet-
`work.
`Anotherchallenge in deploying WiFi networks is the need
`for wiring. Each access point must be fed by a wire through
`
`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
`lowersections 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 publishedrelative 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 networkis 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 implementefficient wireless backhaul. The defi-
`ciencies of WiFi in producing multi-hop (“mesh networks”)
`have been described in many papers. An exampleis “Reveal-
`ing the Problems of 802.11 Medium Access Control in Multi-
`hop Wireless Ad Hoc Networks” by Shugong Xu and Tarek
`Saabdawi, published in “Computer Networks” magazine in
`2002, that emphasizedparticularly the difficulties of TCP/IP
`in this environment.
`
`In general, adhoc, 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 protocolis a clear example of central-
`ized control in shared media. Elements of this protocol were
`adopted by the WWANindustry (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)includesa 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 mayreside 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 whichtransceivers 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 of 19
`
`Page 11 of 19
`
`

`

`US 9,179,495 B1
`
`3
`can force multiple transceivers to transmit at the same time.
`Byre-packing data, transmissions can be divided into time
`slots of equal orof 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
`USS. 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 basedontraffic to be delivered. For example,if
`a first AP has more data to transmit and a second AP doesnot,
`the central controller can grant more transmission slots or
`longer transmissionslots to thefirst AP.
`Scheduled TDMA mayalso be utilized for wireless back-
`haul. A central controller may schedule simultaneoustrans-
`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 bandsthat can be
`used for backhaul and bands that can be used for communi-
`
`cation with STAs. Since non-interfering simultaneoustrans-
`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 simultaneoustrans-
`missions are not possible in one network, the transmissions
`can be scheduled or movedto 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 STAsis a mix of
`
`20
`
`25
`
`30
`
`scheduled TDMA andstandard 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 synchronizesthe clocks ofthe APssothatit
`can schedule (or grant) andallocate timeslots.
`Although wireless backhaul techniques are well known in
`the art (e.g., “multi-hop network” and mesh networks as
`mentioned above), these methods are very unsuitable for
`standard 802.11-based networks. Any nodethatis transmit-
`ting will silence any nodesin its reach, while any nodereceiv-
`ing requires all nodes in reach to be silenced as well. This
`meansthat 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,
`whichis described in commonly-owned U.S. 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 APis 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 ontop of 802.11 PHYallowsall APsto 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 powerlevel of the
`APsis 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 powercontrol for the STAs, 6) less effect of external
`interference, 7) easier packet fragmentation and transmission
`re-tries, and 8) reduced powerrequired bythe 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 embodimentof the invention;
`FIG.3 is showsthe timing of time synchronization request
`and response packets according to one embodiment;
`FIGS. 4A and4Bare flowcharts illustrating an example of
`coarse time synchronization;
`FIG. 5 is a flowchart illustrating an example offine time
`synchronization according to one embodiment;
`FIG.6 is a time-line representation oftransmissionslots of
`using a single band;
`FIG.7 is a time-line representation of transmission slots
`using two bands, according to one embodiment;
`FIG. 81s a diagram ofa backhaul network topology accord-
`ing to one embodiment; and
`FIG.9 is a timing diagram showing examplesof transmis-
`sion slots from the bridges of FIG.8.
`Use of the same or similar reference numbersin different
`
`figures indicates sameorlike elements.
`
`DETAILED DESCRIPTION
`
`In accordance with one aspect of the invention, a time
`division multiple access (TDMA) based methodis used to
`schedule transmissions in a wireless network, such as 802.11
`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 showsa block diagram of a wireless LAN network
`200 that utilizes TDMA scheduling according to one embodi-
`mentof the present invention. A networkcloset or center 202
`includesa central controller 204, a switch 206, and an access
`point (AP) stack 208 (backhaul APs). 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 (RSSJ) 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 APsif certain transmis-
`sions are to be executed, (3) collects information about data
`traffic load based on monitoring the APs as well as monitoring
`the datatraffic that is in some embodiments routed through
`the controller,
`(4) schedules transmission opportunities
`(slots) from APs and STAs based ontraffic distribution and
`anticipated carrier to interference and noise ratio (CINR) to
`maximize the CINR conditions at receive points, number of
`concurrent transmissions, and hence network throughput, and
`(5) pre-assigns transmission data rate per frame to avoid data
`rate fallback. Central controller 204 mayalso bereferred to as
`a router, an RF router, or radio processor and is described in
`commonly-owned U.S. 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 problemsif based on standard 802.11 technol-
`ogy. To facilitate connectivity among access points (e.g.,
`repeater APs 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 mustnot 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/T) 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
`lsecs, transmissions may cease unless AP time synchroniza-
`tion is within that range.
`The data transmission timeslots are dynamically assigned
`by the central controller to combinations of wireless connec-
`tions which can be active simultaneously. The assignmentis
`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 monitoreddirectly in those embodiments
`wherethe data traffic passes through the central controller. In
`one embodiment,all the slot lengths are equal andthe slots
`are filled according to the amount of data queued for a par-
`ticular destination. In another embodiment, the slot assign-
`ments are somewhatrandomizedto avoid repetition of unfa-
`vorable combinations.
`Theslots can also be madedifferent 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 computedusing a linear programming
`algorithm (knownto those familiar with the art). For example,
`let S, toS,, be the sets of simultaneously feasible connections.
`Eachset S, will be granted a corresponding slot time a,. The
`lengths of slot time a, are constrained to be long enough to
`permit the required amountof data to be sent along the con-
`nectionsactivated in S,. Linear programmingis used to mini-
`mize the sum ofthe lengthsa, fori between 1 and n, subject to
`these constraints. The resulting slot lengths are in the most
`efficient ratio to each other. The system can makebest use of
`the slot lengths when the data packets are aggregated for
`transmission between the APs as explainedlater.
`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
`
`travels through the central controller and the switch, which
`provides layer 2 connection between the central controller
`and the APs.
`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 channellimits are eliminated and there
`is no constraint on the number of backhaul APs. Communi-
`
`20
`
`25
`
`30
`
`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 andstandard 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 thetraditional wired
`access points to form a wireless connection.
`Each backhaul AP 216 in AP stack 208 mayuse high gain,
`directional antennas to communicate with repeater APs 212
`to maximize range and minimizeinterference. 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 usedfor 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.11 conformant MACand PHYinterface to the
`wireless medium and provide accessto 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 onefor client serving or communication.
`
`Page 13 of 19
`
`Page 13 of 19
`
`

`

`US 9,179,495 B1
`
`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 antennathat 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.11(b), backhaul communication can be handled through
`802.11(a) and client communication can be handled through
`802.11(b), in one embodiment. Other channel assignments
`mayalso be suitable for the present invention.
`However,
`in conventional systems, collocated multiple
`channel operation is not practical due to issues such asinter-
`channelinterference, 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 packedefficiently into the allocated transmission time
`slots. By combiningthe data from IP packets and pieces of IP
`packets, a specific amount of transmission time can beeffi-
`ciently used for a unidirectional transmission. An acknowl-
`edgementand possible request for re-transmission of part of
`the data can be returned later. Unidirectional transmissions,
`not interleaved with returning acknowledgementpackets are
`much more amenable to simultaneous non-interference than
`the standard 802.11 transmissions. For the transmissionto 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
`hampertransmission 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 many
`frequency channels (up to 12 channels), it may be quite hard
`to capitalize on this available spectrum when multiple 802.11
`transceivers are collocated. For example, if the signallevel is
`not low enoughandisolation is not great(as for typical 802.11
`equipment), it may hit the intermediate RF circuits directly.
`To avoid this, all transmissions may be synchronized such
`that all collocated transceivers or APs will either be transmit-
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`ting or receiving at each instance. Both backhaul and repeater
`APs mustbe operated in TDMA mode. This synchronization
`will not allow for one transceiver to transmit while another
`
`50
`
`oneis trying to receive. In this case, the effects of the inter-
`channel interference can be eliminated and all frequency
`channels can be simultaneously used.
`However, 802.11-based equipment is not designed for
`TDMA operation since the common DCFprotocol requires
`entirely different functionality. For example, in 802.11, every
`transceiver may access the channelat any time, provided the
`carrier sense mechanism (e.g., CSMA/CA) permits (no
`energy or carrier is being sensed). This means that channel
`access timing is very random, which is contradictory to
`TDMA operation.
`Thus, to accurately synchronize the transmissions, access
`points must be time synchronized. If standard WiFi equip-
`mentis to be used (e.g., off-the-shelf access points), the only
`way to access the devices is through an Ethernet connection.
`Furthermore, the access points may use Ethernet connections
`that share other network traffic, which could cause significant
`
`55
`
`60
`
`65
`
`8
`variation in messagelatency, thereby make the synchroniza-
`tion process much moredifficult.
`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 t, the
`query (Time_Synch_Req packet) wassent, 2) the local timet,
`at the access point when the response (Time_Synch_Resp
`packet) was generated, and 3) the arrival time t, 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 betweenthefirst
`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 (1e.,
`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 adjustits 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