US 7,110,783 B2
`(10) Patent No:
`a2) United States Patent
`
`Bahlet al. Sep. 19, 2006 (45) Date of Patent:
`
`
`US007110783B2
`
`(75)
`
`73)
`
`(73)
`*)
`(")
`
`e
`Notice:
`Notice
`
`(54) POWER EFFICIENT CHANNEL
`SCHEDULING IN A WIRELESS NETWORK
`.
`.
`Inventors: Paramvir Bahl, Sammamish, WA (US);
`Atul Adya, Redmond, WA (US);
`Jitendra D. Padhye, Kirkland, WA
`(US)
`P
`(US)
`Assignee: Microsoft Corporation, Redmond, WA
`Subject t
`disclai
`the
`t
`f thi
`en seen eg ae
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 607 days.
`(21) Appl. No.: 10/124,721
`(22)
`Filed:
`Apr. 17, 2002
`(65)
`Prior Publication Data
`US 2003/0203740 Al
`Oct. 30, 2003
`Int. CL
`(2006.01)
`HOAR 7/00
`(2006.01)
`HO4B 7/212
`(2006.01)
`H040 7/20
`(2006.01)
`HO4s 1100
`(2006.01)
`G06F 15/16
`(52) US. Ch. ceccccssssseseeeeee 455/516; 370/208; 370/347,
`709/200
`
`(51)
`
`(58) Field of Classification Search ................ 455/434,
`455/516; 370/347, 208; 709/200
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,241,542 A
`8/1993 Natarajan et al.
`.
`(Continued)
`FOREIGN PATENT DOCUMENTS
`1089500 A2
`4/2001
`
`EP
`
`OTHER PUBLICATIONS
`
`Nandagopal, T., et al., “A Unified Architecture for the Design and
`Evaluation of Wireless Fair Queueing Algorithms”, ACM
`MobiCom 1999,
`in proceedings of The Fifth Annual ACM/AEE
`International Conference on Mobile Computing andNetworking pp.
`132-173 (Aug. 1999).
`
`.
`
`(Continued)
`Primary Examiner—William D. Cumming
`(74) Attorney, Agent, or Firm—Wolf, Greenfield & Sacks,
`PC.
`(57)
`
`ABSTRACT
`
`A method and system for optimizing channel access sched-
`uling for multiple wireless computing devices over a wire-
`less network improves channel access efficiency with
`respect to a primary channel. An access point, or host
`computer, includes a host transceiver for receiving control
`information from the wireless computing devices over a low
`power channel. Upon receiving the control information, the
`access point applies a scheduling algorithm to schedule
`Channel access forthe wireless computing devices to trans-
`mit data over the primary communication channel. The
`wireless computing devices include a low powerradio for
`receiving scheduling information via the low power channel
`during idle periods. When the scheduling information is
`received, the wireless computing device activates its pri-
`mary channel network interface components to communi-
`cate data through the primary channel. When the computing
`device is idle, the device is configured to power downall of
`its components with the exception of the circuitry required
`to power the low power channel. As such, the low power
`channel is maintained in an active state for receiving sched-
`uling information, such as an access schedule, during both
`idle and non-idle periods.
`
`(Continued)
`
`15 Claims, 9 Drawing Sheets
`
`. i
`
`—
`
`
`
`ae
`
`Wireless computing device sends control
`information over low power channel
`
`Hosttransceiver at access point transmits
`
`
`
`
`scheduling information (i.e. 802.11 standard Protocol408
`
`
`scheduling information over low power a 404/406
`
`channel
`
`»
`
`Transmit data over the primary channel based upon
`
`channel)
`
`1
`1
`
`DELL EX. 1011
`
`DELL EX. 1011
`
`

`

`US 7,110,783 B2
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`1/1994 Mabeyet al.
`5,278,831 A
`4/1995 Diepstraten et al.
`5,410,738 A
`5/1996 Gilhousen
`5,519,761 A
`1/1997 Reissner
`5,594,731 A
`4/1997 Rochester et al.
`5,621,735 A
`4/1998 Siepet al.
`5,740,363 A
`8/1998 Mahanyetal.
`5,790,536 A
`12/1998 Gollnick et al.
`5,844,893 A
`12/1998 Heinrich et al.
`5,850,181 A
`4/1999 Wang
`5,898,904 A
`7/1999 Akhavan
`5,920,815 A
`9/1999 Mahanyet al.
`5,949,776 A
`9/1999 Mahany
`5,960,344 A
`6/2001 Ohyamaetal.
`6,243,575 Bl
`8/2001 Choi
`6,278,883 Bl
`3/2002 Menardetal.
`6,356,192 Bl
`3/2004 Wanget al.
`6,711,418 Bl
`6,807,165 B1* 10/2004 Belcea ou... eee 370/347
`2001/0055275 Al
`12/2001 Herrmann etal.
`2002/0132603 Al
`9/2002 Lindskoget al.
`2003/0198196 Al
`10/2003 Bahlet al.
`2003/0203740 Al* 10/2003 Bahlet al. .......... 455/516
`2004/0179469 Al*
`9/2004 Attar et al.
`..
`370/208
`
`2004/0181569 Al*
`9/2004 Attar et al. we. 709/200
`2005/0059347 Al
`3/2005 Haartsen
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`1137226 A2
`
`9/2001
`
`OTHER PUBLICATIONS
`
`Keshav, S., “On the Efficient Implementation of Fair Queueing”
`Internetworking, Research and Experience, vol. 2, No. 3., 157-173
`(1991).
`Barghavan, V., et al., “Fair Queuing in Wireless Networks: Issues
`and Approaches”, IEEE Personal Communications Magazine, pp.
`44-53 (Feb. 1999).
`Parekh, A.K., et al., “A Generalized Processor Sharing Approach to
`Flow Control in Integrated Services Networks: The Single-Node
`Case”, IEEE/ACM Transactions on Networking, vol. 1, No. 3, pp.
`344-357 (Jun. 1993).
`Parekh, A.K., et al., “A Generalized Processor Sharing Approach to
`Flow Control in Integrated Services Networks: The Multiple Node
`Case”, IEEE/ACM Transactions on Networking, vol. 1, No. 2, pp.
`137-150 (Mar. 1994).
`NG,T.S., “Packet Fair Queueing: Algorithms for Wireless Networks
`with Location-Dependent Errors”, Proceedings ofINFOCOM ’98,
`The Conference on Computer Commications vol. 3, Seventh Annual
`Joint Conference of the IEEE Computer and Communications
`Societies, pp. 1103-1111 (Mar. 1998).
`Benini, L., et al., “System-Level Dynamic Power Management’,
`Low-Power Design, 1999; Proceedings. IEEE ALessandro Volta
`Memorial Workshop On Como, Italy Mar. 4-5, 1999, Los Alamitos,
`CA USA, IEEE Comput. Soc. US, Mar. 4, 1999, pp. 23-41.
`Benini, Luca et al., “Monitoring System Activity for OS-Directed
`Dynamic Power Management”,
`In Proceedings of 1998 ACM
`ISLPED, pp. 185-19.
`Benini, L. et al., Dynamic Power Management of Electronic Sys-
`tems, in Proceedings of the 1998 IEEE/ACM ICCAD,Nov.8-12,
`1998, San Jose CA, pp. 696-702.
`Hinckley, K., et al., “Sensing Techniques for Mobile Interaction”,
`ACM UIST 2000 Symposium on User Interface Software & Tech-
`nology, CHIletters 2(2), pp. 91-100.
`Intel Microsoft Toshiba, “Advanced Configuration and PowerInter-
`face’, Revision 1.0 Feb. 2, 1999, 323 pages.
`Simunic, Tajana,et al., “Dynamic Power Managementfor Portable
`Systems”, In Proceedings of ACM MOBICOM 2000, Aug. 2000,
`Boston, MA pp. 11-19.
`Simunic, Tajana, et al., “Dynamic Voltage Scaling and Power
`Management for Portable Systems”, In Proceedings ofACM DAC
`2001, Aug. 2001, pp. 524-529.
`
`Fleishman, Glenn, New Wireless Standards Challenge 802.11b, The
`O'Reilly Network,
`at
`oreillynet.com/Ipt/a//wireless
`/2001/05/
`O8standards.html (Jun. 8, 2001), pp. 1-4.
`Flickenger, Rob, 802.//B Tips, Tricks and Facts, The O'Reilly
`Network, retrieved from oreillynet.com/Ipt/a//wireless/2001/03/02/
`802.11b_facts_html (Mar. 2, 2001), pp. 1-3.
`Press Release, “Atheros Ships Combo Rolling Three WLAN Stan-
`dards into a Single Solution”, Atheros Communication retrieved
`from atheros.com/news/combo.html (Mar. 11, 2002) pp. 1-3.
`Atheros Communications, AR500LX Combo WLAN Solution Bro-
`chure, retrieved from atheros.com pp. 1-2.
`Nobel , Carmel, For WLAN, It’s 802.11bm Eweek retrieved from
`eweek.com/print_article /0.3668.a=18648.00.asp (Nov. 19, 2001)
`pp. 1-2.
`Liu,Jun,et al., “Using Loss Pairs to Discover Network Properties”,
`ACM SIGCOM Internet Measurement Workshop, 2001, 12 pages.
`Zhang, Yin, et al., “On the Constancy ofInternet Path Properties”,
`SIGCOM Internet Measurement Workshop, 2001, 15 pages.
`Lai, Kevin,et al., “Measuring Link Bandwidths Using A Determin-
`istic Model of Packet Delay”, In Proceedings of ACM SIGCOM
`2000, 12 pages.
`Balakrishnan, Hari, et al., “Analyzing Stability in Wide-Area Net-
`work Performance”, In Proceedings of CAN SIGMETRICS Con-
`ference on Measurement & Modeling of Computer Systems, Seattle,
`WA Jun. 1997, 11 pages.
`Yavatkar, R., et al., “SBM (Subnet Bandwidth Manager): A Protocol
`for RSVP-based Admission Control Oveer IEEE 802-style Net-
`works”, IETF RFC 2814, retrieved from faws.org/rfcs/rfc28 14 html
`on May 19, 2002.
`Breslau, Lee, eet al., “Endpoint Admission Control: Architectural
`Issues and Performance”, In Proceedings of ACM SIGCOMM
`2000, pp. 57-69.
`Chiasserini, Carla, F.. “Combining Paging with Dynamic Power
`Management’, in IEEE INFOCOM 2001, pp. 996-1004.
`Shih, Eugene,et al., “Wake on Wireless: An Event Driven Energy
`Saving Strategy for Battery Operated Devices”, MOBICOM ’02,
`Sep. 23-26, 2002, pp. 1-12.
`Yung-Hsiang, Lu, “Reguester-Aware Power Reduction”, IEEE, Sep.
`20, 2000, pp. 18-23.
`Lettieri, Paul, “Advances in Wireless Terminals”, JEEE Personal
`Communications, Feb. 1999, pp. 6-19.
`Kleynhans, Steve, “JBM: Back in the PC Game”, retrieved from
`techupdate.zdnet.com/techupdate/stories/main/0,14179,2868907-
`2,00html (last visited Sep. 16, 2002).
`“Wayports Successful Trail of Microsoft Windows XP and 802. 1x
`Forecasts a More Secure Environmentfor Wireless Users”, HITCH
`Online 2002 edition at online.hitec.org/news/4009856,20000343.
`htm (last visited Sep. 16, 2002).
`“Wireless LAN Computing with IBM Personal Device”, IBM White
`papers, IBM Personal Systems Group, Dec. 2001, 9 pages.
`Bowman, Barb,“Unplugged and Unwired”, Microsoft Corporation
`at microsoft.com/windowsxp/expertzone/columns/bowman/june11.
`asp (last visited Sep. 16, 2002).
`“Windows XP Segment Analysis of the IBM ThinkPad Notebook
`Platform”, Strategic Relationship Marketing Oct. 2001, 1 page.
`Boingo Launches Nationwide WI-FI Service, Boingo Press Releases
`at boingo.com/pr/pr3/html (last visited Sep. 20, 2002).
`Boingo Wireless Announces Founding and Funding, Boingo Press
`Releases at boingo.com/pr/pr1/html (last visited Sep. 20, 2002).
`802.11b has reached ’escape Velocity Boingo Wireless Market
`Overview at boingo.com/marketoverview.html(last visited Sep. 20,
`2002).
`Chan, Sharon Pian, Wireless where you want: WI-FT is the guerrilla
`revolution of wireless computing, Seattle Times Wireless where you
`want
`it
`at
` seattletimes.nwsource.com/htm/businesstechnology/
`1344028 14wirelesslan11-html last visited Sep. 20, 2002.
`Wireless Technology, Wireless Technology at microsoft.com/hwdev/
`wireless (last visited Dec. 8, 2000).
`Lough, Daniel, L., et al., A Short Tutorial on Wireless LANs and
`IEEE 802.11 at computer.org/students/looking/summer97/iece8702.
`htm (last visited Dec. 12, 2000), 5 pages.
`
`2
`
`

`

`US 7,110,783 B2
`Page 3
`
`Mubashir, Alam, Descriptive Analysis ofIEEE 802.11 Standardfor
`Wireless Networks, at triton.cc.gatech.edu/ubicomp.257 (last visited
`Dec. 12, 2000).
`Zero Configuration Networking (zeroconf) at zeroconf.org (last
`visited Dec. 12, 2000).
`Cheshire, Stuart, “Dynamic Configuration of IPv4 Link-local
`Addresses”, Apple Computer Oct. 8, 2000 at zeroconf.org/draft-
`ietf-zeroconf-ipv4-linklocal-00.txt (last visited Dec. 12, 2000).
`Hattig, M., Zeroconf Requirements draft-ietf-zeroconf-reqts-06. txt
`(Dec. 12, 2002).
`“Enabling IEEE 802.11 Networks with Windows “Whistler”, at
`microsoft.com/hwdev/wireless/ieee802Net.-htm (last visited Dec. 8,
`2000).
`Specification of the Bluetooth System, vol. 1, Dec. 1, 1999, pp.
`(1,082 pages).
`Miller, Brent, et al., Mapping Salutation Architecture APIs to
`Bluetooth Service Discovery Layer (White Paper), vol. 1.0, IBM
`Corporation, Jul. 1, 1999, pp. (pp. 1-26).
`IEEE Standard, 802.11, Part 11: Wireless LAN Medium Access
`Control (MAC) and Physical Layer (PHY) Specifications, \** Edition
`1999 (512 pages).
`O’Hara, Bob, et al., JEEE 802.11 Handbook A Designer’s Com-
`panion, Dec. 1999, (174 pages).
`Rigney, C., et al., “Remote Authentication Dial in User Service
`(Radiusy’, The INternet Society, Jun. 2000, (pp. 1-59).
`Aboda, B., et al. RFC 2716, “PPP EAP TLS Authentication
`Protocol’. The Internet Society, Oct. 1999, (pp. 1-19).
`Blunk,L., et al., RFC 2284, PPP Extensible Authentication Protocol
`(EAP), The Internet Society, Mar. 15, 2000, (pp. 1-12).
`
`IEEE 802.11 Security White Paper, vol. 1., Windows Network
`Infrastructure team, Microsoft Corporation, Mar. 15, 2000, pp.
`IEEE 802.1X Supported Scenarios, Windows Network Infrastruc-
`ture team, Microsoft Corporation, vol. 1, Apr. 7, 2000, (7 pages).
`Mettala, Riku, et al., “Bluetooth Protocol Architecture” (White
`paper), vol. 1.0, Nokia Mobile Phones, Sep. 29, 1999.
`Muller, T., Bluetooth Security Architecture, (White paper), vol. 1.0,
`Jul. 15, 1999.
`Chunlong Guo et al., Low Power Distributed MAC for AD Hoc
`Sensor Radio Networks, TEEE Online! 2001, pp. 2944-2948,
`XP0023 16297, no month listed.
`Intel Wireless Gateway,
`Intel: Sample Installation Scenarios,
`Online! Oct. 9, 2001, pp. 103, XP0023 16298.
`Olofsson et al., “Performance Evaluation of Different Random
`Access Power Ramping Proposals For The WCDMA System,”,
`Proceedings of PIMRC ’99: International Symposium on Personal
`and Indoor Mobile Radio Communications Sep. 12-15, 1999 Osaka,
`Japan, Online! vol. 3, Sep.
`12,
`1999, pp. 1505-1509, vol.
`XP002317518 10 International Symposium on Personal, Indoor
`and Mobile Radio Communications (PIMRC’99). Proceedings
`Osaka
`Univ
`Odsaka;
`s3.kth.se/radio(COURSES/
`OPACKETRADIO32E5503 ,32004/Slides/PIMRC99 ,,RA.pd.
`Jorgen Bach Andersen: “Antenna Arrays in Mobile Communica-
`tions: Gain, Diversity, and channel Capacity” TEE Antennas and.
`Propagation Magazine, vol. 42, No. 2, Apr. 2000; pp. 12-16,
`XP002334673.
`
`* cited by examiner
`
`3
`
`

`

`U.S. Patent
`
`Sep. 19, 2006
`
`Sheet 1 of 9
`
`US 7,110,783 B2
`
`029
`
`Jelndwo
`
`0ztoD
`
`Jainduwio
`
`02
`
`\YJayndwos==)
`
`0z1o
`
`Jeyndwo
`
`|“bi4
`
`02
`
`dayndwog
`
`0c
`
`sayndwoy
`
`02
`
`4
`
`

`

`U.S. Patent
`
`Sep. 19, 2006
`
`Sheet 2 of 9
`
`US 7,110,783 B2
`
`LV
`
`
`
`(s)ad1IAeqjndu|
`
`uonHeolunwuwos)
`
`(s)uo]oeuU0yD
`
`ebei0js
`
`S|QeAOLWSY-UON
`
`a6eJO}S
`
`
`
`(s)ed1AeqIndino
`
`B|GeAowsay c‘ble
`
`OS
`
`Asayeg
`
`S/}E|OA-UON
`
`
`
`
`
`WiuUf)Buisse90l¢SIHEOA
`
`
`
`Aloweywayshs
`
`5
`
`
`
`
`

`

`U.S. Patent
`
`abeyoA
`
`Joyeinbay
`
` OOL
`
`MO}
`
`JOMOd
`
`Areyeg
`
`Sep. 19, 2006
`
`Sheet 3 of 9
`
`US 7,110,783 B2
`
`
`
`ZHING/6olpey
`
` (sdqyZ61)
`
`Ld-pOLL419}
`
`JId
`
`
`
`(d|AEpSSalalIM0})ZEZSY
`
`
`
`SJUBUOULUOJEUIO
`
`€bi4
`
`
`
`6
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 19, 2006
`
`Sheet 4 of 9
`
`US 7,110,783 B2
`
`
`
`
`
`so1naqBunndwogjualD
`
`CCC
`
`pybi
`
`0c
`
`\oot
`
`SSeSee
`
`2OuUeseld
`
`JOAIOS
`
`oeLay
`
`OLZ
`
`
`
`
`
`JUIOdSSBDDVSSA/QIIAA
`
`7
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 19, 2006
`
`Sheet 5 of 9
`
`US 7,110,783 B2
`
`cOV
`
`vOv
`
`907
`
`
`
`007eBuraeyao!AepBuljndwodssajasiAA
`
`
`
`
`
`
`____(84)YIMsiajsibolJaAlsosued}JamodMo}
`
`
`
`-
`
`
`
`‘JOAIOSyOUg
`
`
`
`SU}O}JBUUBYOJamodMoO]SU}BIAUOHPEWJOJU!
`
`
`
`‘julodssaa0e
`
`
`
`PULUONEWJOJUIJO4JUODOU}SOAIBDEJUIOdsseooy
`
`
`
`
`
`
`
`
`
`
`
`BunndwosssajeJimJO}sse00eJ|BUUBYOSeiNnpEeyos
`
`
`
`
`
`
`
`
`
`|OUJUODSPUSSBdIASPBuljndwodssajaulAA
`
`
`
`
`
`
`
`‘WyywobjeBuljnpayosuodnpaseqseoihep
`
`
`
`
`
`
`
`G‘bl
`
`
`
`907JidnpasamodsiaoiAepBulyjndwiodssajesiA\
`
`
`
`
`[ieday}yBnosu}asjeyoedejep(SAAI900JJO)sIgysues}pueAlesseoeu
`uodnpaesegjeuueyo
`
`
`
`
`
`
`
`‘uolyeuOjuUlHullnpayos
`
`
`
`‘aolaapBurndwosssajeulm0}j|aUUeYSJemodMO}
`
`
`
`
`
`
`
`
`
`
`
`yBnoiy}uonewuoju!Buljnpeyosspuesjulodssesoy
`
`
`
`
`
`8
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 19, 2006
`
`Sheet 6 of 9
`
`US 7,110,783 B2
`
`022
`
`g0z—”
`
`NLOOL
`
`LOZ
`
`
`
`
`
`JUIOdSSED0'YSSEIOUI\
`
`\—zo
`
`L-°208Sal
`
`
`
`
`
`9“Biz
`
`CCS
`
`JBAISOSUBILAY
`
`
`
`g91AaqBuljndwoy
`
`}SOH
`
`9
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 19, 2006
`
`Sheet 7 of 9
`
`US 7,110,783 B2
`
`cOV-
`
`
`
`
`
`[O4JU0dSpuasadIAepBuljndwioossejeuiA
`
`
`
`
`
`
`
`
`90r/rOrJamodmojJ8A0UOHeUWOjUBulinpeyos
`_/jauueyo
`
`
`
`
`
`
`SJILUSUBI]JUIOdSS8d0eJeJAAISOSUEI}JSOH
`
`
`
`
`
`[auUeYSaMmodMOJSAOUOELWOJUI
`
`
`
`uodnpasegjouueyoAewuidoy}JeaoByepyWsuUeL
`
`
`
`
`
`80¢_soyoudPJEPURIS|1°Z08°9'!)UONeWWOjUGuljnpauos
`
`
`
`
`
`
`
`Z‘bid
`
`(jauueYo
`
`10
`
`10
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 19, 2006
`
`Sheet 8 of 9
`
`US 7,110,783 B2
`
`90¢
`
`yore
`
`eg
`614
`
`JOAsosues]+YCo
`
`
`00€
`
`
`JUIOgSSSo0VySSOIAUI/A
`
`ZOE
`
`80&
`
`
`
`OlZ
`
`11
`
`11
`
`
`
`

`

`U.S. Patent
`
`Sep. 19, 2006
`
`Sheet 9 of 9
`
`US 7,110,783 B2
`
`00€
`
`Oe
`
`Iw)
`(=ady
`
`
`JUlIOgSSE00YSS3ISUIM,
`
`—-Oe
`
`qg“bl
`
`12
`
`12
`
`
`
`

`

`US 7,110,783 B2
`
`1
`POWER EFFICIENT CHANNEL
`SCHEDULING IN A WIRELESS NETWORK
`
`TECHNICAL FIELD OF THE INVENTION
`
`10
`
`30
`
`40
`
`45
`
`50
`
`55
`
`The present invention relates generally to wireless com-
`puting devices, and more particularly,
`to power efficient
`channel access scheduling for wireless computing devices
`using multiple radios.
`
`BACKGROUND OF THE INVENTION
`
`Many wireless computing devices, such as laptop com-
`puters, personal digital assistant devices, etc., may act as
`client devices in a wireless networking environment. Often
`these multiple clients all communicate via the network
`through shared radio frequency channels to a shared access
`point. However, when a large numberof such client devices
`attempt to access the network, this sharing of network access
`points often leads to congestion and a wasting of bandwidth.
`Congestion often leads to collisions in the channel between
`data signals and hence to delay.
`To overcomethese challenges, various control techniques
`have been implemented with respect to wireless networksto
`aid in scheduling to avoid collisions. For example, clients
`may engagein listen-before-transmit (“LBT’’) mechanisms,
`such as the CSMA-CA channel access mechanism,vying for
`space in the shared channel before transmitting. LBT tech-
`niques are a type of distributed coordinated function.
`CSMA-CAis a particular Ethernet LAN access method.
`However, with all LBT schemes, if one client device is
`currently transmitting signals (i.e. data packets) in the chan-
`nel, other senders are forced to back off and wait a random
`amountof time before attempting access again. Additionally,
`even if the client devices detect that the network is free, two
`such devices may access the channel at exactly the same
`time, causing a signal collision. When this type of collision
`is detected, both client devices are forced to back off and
`wait a random amount of time before attempting transmis-
`sion again. While the client devices are waiting, channel
`bandwidth is wasted, packet transmission is delayed, and
`battery power on the client machine is wasted.
`Other mechanisms exist for aiding in scheduling and
`avoiding collision between data signals over a shared chan-
`nel. Another example is a point-coordinated function
`(“PCF”), which repeatedly polls the client devices in order
`to avoid collisions of signals. However, while PCF tech-
`niques avoid the constant back and forth between the
`competing data signals, the constant polling on the primary
`channel wastes a large amount of bandwidth, thus making
`this technique highly inefficient.
`While current wireless channel access techniques do
`produce collision avoidance, they also waste bandwidth on
`the primary channel used to send data packets because these
`techniques use the channel both to transmit control and
`scheduling information and to send useful data. Distributed
`coordinated functions, such as CSMA-CA,are further inef-
`ficient for real-time data because of the forced waiting
`period. Real-time audio data may no longer be useful, or
`sufficient, after a forced delay, such as a 100-millisecond
`delay. Additionally, there is no guarantee of channel access
`by any of these techniques and there is no mechanism to
`assure that high priority data signals are transferred in a
`timely manner.
`However, if the access point knows the exact state of
`every client it is servicing (e.g. number of packets pending
`in the queue, the packets deadlines, and packet priorities), it
`
`2
`independently on the channel.
`can schedule each client
`While researchers have attempted to build true work con-
`serving fair queuing algorithms based upon this premise,
`these algorithms have not been truly work conserving
`because part of the bandwidth on the channel is used up in
`transmitting control
`information to the scheduler and in
`many cases the media-access control (MAC)protocol has to
`be changed. Therefore, even with such techniques band-
`width is wasted.
`
`Additionally, while largely avoiding signal collisions,
`these techniques cause inefficient use of power because they
`often use a high-powered channel to send control data in
`addition to useful data. A particular componentof a wireless
`device that consumes a significant amount of power is the
`network interface card (NIC), which handles the wireless
`transmission and reception of network communication data.
`It has been estimated that on average, about 20% of the total
`poweravailable to a wireless device is dissipated as a result
`of the connection of a NIC, or other wireless LAN interface
`component. This phenomenonis dueto the fact that the NIC
`and wireless device must be in a constant“listening”state in
`order to receive and transmit data via the network. Since the
`amount of power a battery can provide is rather limited,
`minimizing the power consumption of a mobile device in
`order to extend its operation time is an important consider-
`ation in the design of battery operated wireless devices, and
`any communication systems involving such devices.
`
`SUMMARY OF THE INVENTION
`
`To address the challenges described above, a method and
`system are disclosed for powerefficient channel scheduling
`of wireless client devices in a wireless network using
`multiple radios. This method and system lead to optimum
`use of channel bandwidth and power in wireless computing
`devices. Therefore, true work conserving algorithms can be
`implemented. Such wireless computing devices include, but
`are not limited to, personal data assistants (““PDAs’’), cellular
`phones, and laptop computers having network interface
`capabilities.
`In accordance with an embodiment of the invention, a
`wireless computing device enables a low power control
`channel to exchange information including control informa-
`tion for a network interface card (NIC), and other power
`consuming components of the computing device, with a host
`transceiver, referred to as a smartbrick. Initially, the low
`powertransceiver registers with the host transceiver, such as
`a host transceiver located at a network wireless access point.
`The low powertransceiver operated by the wireless com-
`puting device then sends control information data signals to
`the host transceiver. This information may be, but is not
`limited to, state information, the numberof data packets in
`a queue, the packetpriority, and/or packet deadline. The host
`transceiver then responds by transmitting scheduling infor-
`mation back to the low power transceiver. This scheduling
`information may include, among other things, channel
`access information.
`
`Prior to receiving scheduling information from a host
`transceiver component,
`the high power wireless network
`interface components, such as associated with an ordinary
`wireless NIC, are idle. Idle periods are periods when a low
`powerstate of operation is employed by the wireless com-
`puting device, or periods when no substantive network
`activity (e.g., sending or receiving of data) is being engaged
`in by the wireless computing device via its high frequency
`communication channel(e.g., IEEE 802.11 based channel).
`After receiving the scheduling information on the low power
`
`13
`
`13
`
`

`

`US 7,110,783 B2
`
`3
`control channel, the full power NIC and necessary circuitry
`are automatically activated consistent with the scheduling
`information. For example, in one embodiment, upon receiv-
`ing channel access information, such as a message that the
`channel is free for transmission, the NIC and other compo-
`nents of the wireless computing device are powered up. The
`network interface component, such as the NIC, then trans-
`mits or receives data over the high power channel.
`The low power control channel is implemented via an
`internal or external radio frequency (RF) transceiver com-
`ponent, referred to as a minibrick, which preferably operates
`at a low frequency (such as lowerthan that of the full power
`NIC) and low powerlevel. In operation, when the comput-
`ing device is idle, the device is configured to power down
`substantially all of its components with the exception of the
`circuitry required to power the low power transceiver. As
`such, the control channel is maintained in an active state for
`receiving signals during both idle and non-idle periods.
`In accordance with another embodiment of the invention,
`the smartbrick is implemented as a host transceiver that
`operates at a host computer, or network access point, to
`communicate with the minibrick. The host computer may
`also be equipped with an IEEE 802.11 based NIC for
`supporting wireless communication to access the network
`through a wireless access point (AP). The wireless AP acts
`as an interface to a network infrastructure, such as a wired
`enterprise LAN. When a requesting device wishes to com-
`municate with a wireless computing device,
`it queries a
`server in order to determine the location and presence of the
`wireless computing device. In response, the server submits
`the query to the host computer. The smartbrick operating on
`the host computer receives the query from the server, and
`communicates with the minibrick via the low power channel
`to begin scheduling and operation of full power communi-
`cations. The wireless computing device receives this signal
`and powers up the NIC and other components accordingly,
`resulting in activation of the wireless device prior to any
`actual transmission of data by the requesting device.
`Additional features and advantages of the invention will
`be made apparent from the following detailed description of
`illustrative embodiments that proceeds with reference to the
`accompanying figures.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`While the appended claims set forth the features of the
`present invention with particularity, the invention and its
`advantages may be best understood from the following
`detailed description taken in conjunction with the accom-
`panying drawings, of which:
`FIG. 1 is a schematic diagram of an exemplary computer
`network within which embodiments of the invention may be
`implemented;
`FIG.2 is a schematic diagram illustrating the architecture
`of an exemplary computing device in which an embodiment
`of the invention may be implemented;
`FIG. 3 is a schematic diagram illustrating an architecture
`of a transceiver component operated by a computing device
`for maintaining a low powercontrol channel in an embodi-
`ment of the invention;
`FIG. 4 is a schematic diagram illustrating an exemplary
`operating environment for optimum channel scheduling
`through a low power control channel according to an
`embodiment of the invention;
`FIG. 5 is a flowchart illustrating the operation of a host
`transceiver for communicating with a wireless computing
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`device via a low power control channel according to an
`embodiment of the invention;
`FIG. 6 is a schematic diagram illustrating an operating
`environmentfor optimizing channel scheduling wherein the
`host transceiver is logically connected to a host computer
`according to an embodiment of the invention;
`FIG. 7 is a channel diagram illustrating bi-directional
`communications in a two-channel system;
`FIG. 8a is a schematic diagram illustrating a networked
`environment wherein the multiple wireless network devices
`vying for channel space are out-of-range of the wireless
`access point; and
`FIG. 86 is a schematic diagram illustrating a multi-hop
`network operating environment
`for optimizing channel
`scheduling when one or more of the multiple wireless
`devices vying for channel space are out-of-range, according
`to an embodimentof the invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`The invention relates to a method and system fortraffic
`handling of computing devices that are capable of commu-
`nicating over a wireless link. Wireless computing devices
`usable within embodiments of the invention include, but are
`not limited to, personal data assistants, cellular phones, and
`laptop computers having wireless network interface capa-
`bilities. In the context of the invention, wireless communi-
`cation is the transmission of data between computing
`devices using radio frequency (RF) and electromagnetic
`waves rather than wires. To facilitate wireless communica-
`tion, a computing device may be equipped with a network
`interface component, such as a network interface card (NIC)
`that interfaces the device to the network. Typically, the NIC
`is implementedas a plug andplay device that can be inserted
`into a network card slot of the computing device or that can
`be otherwise interfaced to the device. Alternatively, the NIC
`can be built integrally as part of the circuitry of the com-
`puting device.
`To facilitate wireless communication, the NIC supports a
`wireless protocol, such as pursuant to the JEEE 802.11
`standard. General reference will be made throughout the
`course ofthis description to 802.11 as a suitable protocol for
`facilitating wireless communication between devices. How-
`ever, those skilled in the art will recognize that 802.11 is
`only one protocol for facilitating wireless communication,
`and that
`the invention is not
`limited to any particular
`wireless protocol. Indeed, other wireless protocols may be
`utilized alternatively or additionally in connection with the
`invention. It will also be recognized by those skilled in the
`art that the designation 802.11 refers to other protocols
`within the same family,
`including 802.1la, 802.11b or
`802.11g.
`An example of a networked environment in which the
`invention may be used is shown in FIG. 1. The example
`network includes several computing devices 20 communi-
`cating with one another over a network 30, such as the
`Internet, as represented in the figure by a cloud. Network 30
`may include one or more well-known components, such as
`routers, gateways, hubs, etc. and may allow the computers
`20 to communicate via wired and/or wireless media.
`
`Referring to FIG. 2, an example of a basic configuration
`for a computing device on which the system described
`herein may be implemented is shown. In its most basic
`configuration, the computing device 20 typically includesat
`least one processing unit 42 and memory 44 although such
`is not required. Depending on the exact configuration and
`
`14
`
`14
`
`

`

`US 7,110,783 B2
`
`5
`type of the computing device 20, the memory 44 may be
`volatile (such as RAM), non-volatile (such as ROM orflash
`memory) or some combination of the two. The most basic
`general configuration is illustrated in FIG. 2 by dashed line
`46. Additionally, the computing device may also have other
`features/functionality. For example, computer 20 may also
`include additional data storage components (removable and/
`or non-removable) including, but not limited to, magnetic or
`optical disks or tape. Computer storage media includes
`volatile and non-volatile, removable and non-removable
`media implemented in any method or technology for storage
`of information such as computer-readable instructions, data
`structures, program modules, or other data. Computer stor-
`age media includes, but is not limited to, RAM, ROM,
`EEPROM,flash memory or other memory technology, CD-
`ROM,digital versatile disk (DVD)or other optical storage,
`magnetic cassettes, magnetic tape, magnetic disk storage or
`other magnetic storage devices, or any other medium which
`can be used to store the desired information and which can
`
`be accessed by the computing device 20. Any such computer
`storage media may bepart of the computing device 20.
`The computing device 20 also preferably contains com-
`munication connections 48 that allow the device to commu-
`nicate with other devices. A communication connection is an
`example of a communication medium. Communication
`media typically embodies readable instructions, data struc-
`tures, program modules or other data in a modulated data
`signal such as a carrier wave or other transport mechanism
`and includes any information delivery media. By way of
`example, and not limitation, communication media includes
`wired media such as a wired network or direct-wired con-
`nection, and wireless media such as acoustic, RF, infrared
`and other wireless media. The term computer readable
`media as used herein includes both storage media and
`communication media.
`
`25
`
`35
`
`Acomputing device 20 may also have input devices such
`as a keyboard, mouse, pen, voice input device, touch input
`device, etc. Output devices such as a display 48, speakers, a
`printer, etc. may also be included. Furthermore, for wireless
`mobile devices,
`the computing device 20 is preferably
`provided with a portable power source 50, such as a battery
`pack, fuel cell or other power module. The power source 50
`acts as a primary source of power for computations and
`wireless data transmissions to be performed by the device.
`All the aforementioned components and features are well
`knownin theart.
`
`The device 20 preferably supports an operating system,
`for example stored in nonvolatile memory and executed by
`the processing unit 42 from volatile memory. According to
`an embodiment of the invention, the operating system con-
`tains instructions for interfacing the device 20 to a full power
`wireless network and to a low power wireless network. In
`this manner, scheduling information usable to schedule
`access of the device 20 to the full power wireless network
`may be sent over the low power wireless network, saving
`device power and saving bandwidth in the full power
`channel, according to the techniques to be more fully
`discussed elsewhere