throbber
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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket