`Fifield
`
`US006504834B1
`(10) Patent No.:
`US 6,504,834 B1
`(45) Date of Patent:
`Jan. 7, 2003
`
`5,594.738 A * 1/1997 Crisler et al. ............... 370/347
`5,638,371. A * 6/1997 Raychaudhuiri et al. ... 370/347
`5,640,395 A * 6/1997 Hamalainen et al. ....... 370/322
`5,644,576 A * 7/1997 Bauchot et al. ............. 370/437
`5,729,534 A * 3/1998 Jokinen et al. ............. 370/280
`5,752,193 A * 5/1998 Scholefield et al. ........ 455/452
`5,818,830 A * 10/1998 Daane et al. ............... 370/347
`
`SE A : i. Echo - - - - - - - - - - - - - - - - - - - - - - - 3.85
`6,055.242 A
`4/2000 Doshi et al. ................ 370/458
`6,097,707 A * 8/2000 Hodzic et al. .............. 370/321
`6,178,512 B1 * 1/2001 Filfield ....................... 713/201
`6.243,372 B1 * 6/2001 Petch et al. ................. 370/350
`6,295.285 B1 * 9/2001 Whitehead .................. 370/329
`
`
`
`FOREIGN PATENT DOCUMENTS
`
`GB
`
`2O69799 B
`
`8/1981
`
`............. HO4J/3/16
`
`(54) WIRELESS NETWORK
`
`(75) Inventor: Robert Fifield, Redhill (GB)
`(73) Assignee: Koninklijke Philips Electronics N.V.,
`Eindhoven (NL)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`past isis'', adjusted under 35
`a --
`y
`ayS.
`
`(56)
`
`21) Appl. No.: 09/102,838
`(21) App
`9
`22) Filled:
`Jun. 23, 1998
`(22)
`9
`(30)
`Foreign Application Priority Data
`Aug. 7, 1997 (GB) ............................................. 9716626
`* cited bw examiner
`y
`(51) Int. Cl. ............................. H04Q 7/00; H04J 3/00;
`Primary Examiner Wellington Chin
`HO4B 7/212
`ASSistant Examiner M. Phan
`(52) U.S. Cl. ....................... 370/345; 370/329; 370/327;
`(74) Attorney, Agent, or Firm-Daniel J. Piotrowski
`370/437; 435/426; 435/447
`(58) Field of Search ................................. 370/314, 337,
`(57)
`ABSTRACT
`370/345,346,347, 350, 508, 445,449.
`468, 458, 474, 321, 329, 280,455.426, A method of operating a wireleSS network comprising a
`447, 66; 713/150, 160,213; 320/337
`plurality of wireleSS terminals and optionally a base Station
`uses a transmission frame (300) including an association
`References Cited
`section (310) for use by wireless terminals wishing to join
`U.S. PATENT DOCUMENTS
`the network. A variable number of association sections (310)
`:
`is Scheduled in response to operating characteristics Such as
`55. A :
`1. NE tal... E.
`the load on the network or the presence of a high Security
`5,276.703 A
`1. Naras alm : application on the network.
`5,384,777. A
`1/1995 Ahmadiet al... ... 370/337
`5,559,804 A
`9/1996 Amada et al. .............. 370/347
`10 Claims, 2 Drawing Sheets
`
`N/
`
`T
`
`106
`K-102
`104
`
`N/
`
`Egg e-102
`
`HO4
`
`-"
`
`Uplink
`
`Burst
`
`T
`
`--106
`e-O2
`104
`
`Association
`
`c:
`lio 16
`108
`
`Control
`
`Downlink
`
`3O2
`
`304
`
`306
`
`3O8
`
`30
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1016, p. 1
`
`
`
`U.S. Patent
`
`Jan. 7, 2003
`
`Sheet 1 of 2
`
`US 6,504,834 B1
`
`106
`102
`104
`
`N
`
`106
`102
`104
`F.G. 1
`
`106
`102
`104
`
`106
`102
`104
`FIG. 2
`
`106
`102
`104
`
`106
`102
`104
`
`
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1016, p. 2
`
`
`
`U.S. Patent
`
`Jan. 7, 2003
`
`Sheet 2 of 2
`
`US 6,504,834 B1
`
`302
`
`304
`
`
`
`402
`
`-80
`
`306
`FIG. 3
`400
`
`308
`
`310
`
`405
`F.G. 4
`
`408
`
`410
`
`502
`
`504
`
`506
`
`508
`
`510
`
`514 512 516
`
`t1
`
`602
`
`A
`
`F.G. 5
`516
`
`F.G. 6
`
`FIG. 7
`
`t
`
`t
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1016, p. 3
`
`
`
`1
`WIRELESS NETWORK
`
`US 6,504,834 B1
`
`BACKGROUND OF THE INVENTION
`The present invention relates to wireless networks for
`communication between a number of wireleSS terminals
`which are free to join and leave the network at any time. The
`network may be configured So that all the wireleSS terminals
`communicate through a base Station, or So that the devices
`communicate directly with one another.
`Wireless networks are intended to offer flexible and
`cost-effective alternatives to wired networks, for example as
`Local Area Networks (LANs). An advantage of wireless
`over fixed networks is the ease with which new networks can
`be created and with which new devices, known as wireleSS
`terminals, can be added to the network. Some wireleSS
`network standards exist, for example IEEE 802.11 in the
`USA and HIPERLAN in Europe, whilst others are under
`development, for example Wireless Asynchronous Transfer
`Mode (WATM). Such standards define the format of a
`transmission frame, within which control and data transfer
`functions can take place. The format and length of trans
`mission frames may be fixed or dynamically variable.
`Known wireleSS networks, for instance as disclosed in
`U.S. Pat. No. 5,274,841, typically operate in one of two
`different configurations:
`1 Abase Station orientated configuration in which wireleSS
`terminals can only communicate with each other with the
`Support of a base Station, which is responsible for all
`wireless terminals within a certain radio coverage area. The
`base station itself may be connected to further wired net
`works for communications beyond the radio coverage area.
`The base Station may be a separate unit, or it may be a
`wireless terminal with additional functionality.
`2 A peer to peer configuration in which wireleSS terminals
`communicate directly with one another. One of the wireleSS
`terminals is typically chosen dynamically to perform the
`control function.
`The first configuration is generally considered to be most
`suitable for networks with a relatively fixed structure, while
`the Second is considered most Suitable for the generation of
`dynamic networks, Such as for document eXchange at a
`meeting.
`In order for a wireleSS network to realise the advantage of
`flexibility, the procedure for wireleSS terminals joining and
`leaving the network should be as Simple as possible. The act
`of a wireless terminal joining a network is known as
`asSociation and needs to be Scheduled within the data
`transmission format defined for the wireless network.
`Examples of known techniques for association include
`dynamic framelength slotted ALOHA, described in GB-B-2
`069799, carrier sense multiple access and address based tree
`resolution algorithms.
`OBJECTS AND SUMMARY OF THE
`INVENTION
`An object of the present invention is to improve the
`flexibility and efficiency of association to a wireleSS net
`work.
`According to a first aspect of the present invention there
`is provided a method of operating a wireleSS network,
`wherein transmission of data takes place in transmission
`frames of variable length subdivided into a plurality of time
`Slots, the wireleSS network comprising a controller and a
`variable number of wireless terminals, the method compris
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`ing the controller maintaining a list of wireleSS terminals
`currently registered with the network, determining the
`lengths of Successive transmission frames, and allocating
`time slots within Said frame for various purposes, charac
`terised by the controller scheduling a variable number n of
`asSociation Sections in each transmission frame, where n has
`a minimum value of Zero, in response to the current oper
`ating characteristics of the network, by which association
`Sections the wireleSS terminals can register with the control
`ler.
`If desired, the association Sections may use a contention
`based protocol.
`According to a Second aspect of the present invention
`there is provided a controller for a wireleSS network having
`a plurality of wireless terminals, the controller comprising
`means for maintaining a list of wireleSS terminals currently
`registered with the network, means for monitoring the
`operating characteristics of the network, means for deter
`mining the lengths of Successive transmission frames and
`means for allocating time slots within each of Said frames,
`characterised by means responsive to the current operating
`characteristics of the network for Scheduling a variable
`number n of association Sections in each transmission frame,
`where n has a minimum value of Zero.
`According to a third aspect of the present invention there
`is provided a wireless terminal for use in a wireleSS network
`constituted by at least one wireless terminal and a controller,
`the wireleSS terminal comprising transceiver means for
`obtaining Scheduling information relating to transmission
`frames in the network, characterised by means for deter
`mining whether an association Section is available in a
`transmission frame and in that in response to Said means the
`wireleSS terminal attempts association during the association
`Section.
`The present invention is based upon the recognition, not
`present in the prior art, that adding an explicit association
`Section to a transmission frame format and enabling this
`asSociation Section to be Scheduled more or less frequently
`depending on System load improves the efficiency and
`flexibility of operation of a wireless network.
`By means of the present invention a wireleSS network can
`Schedule a variable number of association Sections depen
`dent on considerations Such as network loading and the
`number of active wireleSS terminals.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The present invention will now be described, by way of
`example, with reference to the accompanying drawings,
`wherein:
`FIG. 1 is a block schematic diagram of a wireless network
`made in accordance with the present invention, having a
`base Station orientated configuration;
`FIG. 2 is a block Schematic diagram of a wireleSS network
`made in accordance with the present invention, having a
`peer to peer configuration;
`FIG. 3 is a diagram of an example of a possible trans
`mission frame format Suitable for use in a wireleSS network
`configured with a base station of the type shown in FIG. 1;
`FIG. 4 is a diagram of an example of a possible trans
`mission frame format Suitable for use in a peer to peer
`configured wireless network of the type shown in FIG. 2;
`FIG. 5 shows in outline the process of a wireless terminal
`asSociating with the network,
`FIG. 6 is a diagram showing an expanded view of the
`asSociation Section in a transmission frame; and
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1016, p. 4
`
`
`
`US 6,504,834 B1
`
`15
`
`25
`
`35
`
`40
`
`3
`FIG. 7 in the lower half is a graph showing an example of
`the variation of network load with time (t) and in the upper
`half showing the corresponding Scheduling of association
`Sections.
`In the drawings the same reference numerals have been
`used to indicate corresponding features.
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`The base station orientated wireless network shown in
`FIG. 1 comprises a number of wireless terminals 102 and a
`base station 108, which base station is optionally connected
`to a fixed telecommunications network, for example the
`PSTN. The wireless terminals 102 comprise transceivers
`106 which communicate with one another via the base
`station 108 which comprises a transceiver 106 and a con
`troller 110. The controller 110 may be at the same location
`as the transceiver 106 or remote from it and connected by
`land line connection means. A variety of devices may be
`configured to act as wireleSS terminals 102, for example
`portable computers, printers and measurement equipment.
`In addition to the transceiver 106 each wireless terminal also
`comprises an application-specific block 104 which imple
`ments the required functionality.
`The peer to peer wireless network shown in FIG. 2
`comprises a number of wireless terminals 102 and an
`enhanced wireleSS terminal 202, which comprises a trans
`ceiver 106 and application-specific block 104, as for a
`Standard wireleSS terminal, and further comprises a control
`ler 110 to enable it to perform the control function in a
`wireless network if required. The wireless terminals 102 and
`enhanced wireless terminals 202 communicate directly with
`one another rather than via a base Station. If there is only one
`enhanced wireless terminal 202 it performs the control
`function for the network, otherwise, one of the enhanced
`wireless terminals 202 is chosen dynamically to perform the
`control function.
`The format of the transmission frame 300 shown in FIG.
`3 is for a base Station orientated configuration of the type
`shown in FIG. 1. This particular format is intended for use
`with WATM and similar standards aimed at wireless local
`area networks. The format is a time division format com
`prising Successive transmission frames 300, where each
`transmission frame 300 is divided into a number of sections,
`each of which contains a number of slots in which data is
`transmitted. The lengths of the complete frames and the
`Sections within them can be varied in response to changing
`requirements for data transmission to and from the wireleSS
`terminals 102.
`A control section 302 is used by the base station 108 to
`signal the allocation of slots to wireless terminals 102 in the
`sections comprising the remainder of the frame 300. The
`allocation takes into consideration the number of slots
`requested by the wireless terminals 102, the available
`bandwidth, restrictions on the length of transmission frames
`and any other relevant criteria.
`A downlink section 304 is used for transfer of data from
`the base station 108 to wireless terminals 102, the transfer of
`data to a particular wireleSS terminal 102 taking place in the
`slots allocated for it during the control section 302. An
`uplink section 306 is used for transfer of data in the reverse
`direction, from wireless terminals 102 to the base station
`108. Again, the transfer of data from a particular wireless
`terminal 102 takes place in the slots allocated for it during
`the control section 302.
`An energy burst section 308 is provided for use by
`wireless terminals 102 that have associated with the network
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`but are inactive. Each of these terminals is assigned a unique
`slot within the energy burst section 308 in which it may
`transmit to indicate that it requires an uplink slot to transmit
`data. The base station 108 will then take this request into
`account when scheduling the slots in the uplink section 306
`of the next transmission frame 300.
`An association section 310 is provided for use by wireless
`terminals 102 that wish to join the network. The detailed
`working of this Section is described below. The association
`Section may not always be present, as it is Scheduled under
`control of the base station 108. The base station 108 may
`modify the scheduling of the association section 310 to:
`Schedule an association section 310 when it is conve
`nient. This minimises the risk of losing transmission
`packets due to peaks in transmission traffic. Under
`conditions of high network traffic the base station 108
`may not Schedule an association Section 310 in a
`transmission frame. In order to avoid completely shut
`ting out new wireless terminals 102 the base station 108
`may be controlled So that there is a maximum time
`delay between one association Section and the next.
`Schedule association Sections 310 more frequently during
`conditions of low network traffic. This allows faster
`asSociation for waiting wireleSS terminals 102.
`Schedule multiple association sections 310. This may be
`desirable when many wireless terminals 102 wish to
`asSociate, for example if no association Sections 310
`have been scheduled for Some time.
`Schedule no association sections 310, which may be
`desirable in Some special circumstances. One example
`when the network has no spare capacity, another
`example is When a high Security application is running
`and wishes to prevent any further wireleSS terminals
`102 joining the network.
`It should be noted that the order of sections within the
`transmission frame illustrated in FIG. 3 may be varied, in
`particular it may be beneficial to Schedule the energy burst
`Section 308 and the association section 310 near the start of
`the frame to reduce transmission time delayS.
`The format of the transmission frame 400 shown in FIG.
`4 is for a peer to peer configuration of the type shown in FIG.
`2, although much of the format is the same as for the base
`station orientated frame format shown in FIG. 3. A control
`section 402 is used by the enhanced wireless terminal 202
`acting as base Station to allocate slots to wireleSS terminals
`102 in the remainder of the frame. There are no separate
`downlink and uplink Sections instead there is a data transfer
`Section 405, where transfer of data from one wireless
`terminal 102 to another occurs in the slots allocated to it, the
`reservation of which was detailed during the control Section
`402.
`The energy burst section 408 and association section 410
`work in a similar manner to a base Station orientated
`configuration.
`Consider now in more detail the Sequence of events
`occurring when a wireleSS terminal wishes to associate with
`a network, taking a base Station orientated configuration as
`the example. FIG. 5 shows a Sequence of transmission
`frames 502, 504, 506, 508, 510 and 512 transmitted over
`time t. Each frame has a format identical to or based on that
`shown in FIG. 3, although the total length of the transmis
`sion frame 300 and the sections within it may vary. At time
`t a wireless terminal 102, identified subsequently as WTA,
`is Switched on and wishes to associate with the network. The
`control section 302 of frame 502 indicates that no associa
`tion section 310 is scheduled in this frame. The control
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1016, p. 5
`
`
`
`US 6,504,834 B1
`
`15
`
`25
`
`S
`section 302 also indicates the length of the frame 502, to
`enable WTA to turn off its radio transceiver for the duration
`of the frame to save battery power.
`WTA then turns on its transceiver to receive the control
`Section 302 of the next frame 504 which indicates that there
`5
`is no association section 310 scheduled in this frame. WTA
`optionally turns off its receiver for the remainder of this
`frame to conserve power. The same procedure is followed
`for the subsequent frames 506, 508 and 510 which also have
`no association Section 310 Scheduled. Finally, Scheduling
`information transmitted within the control section 514 of the
`next frame 512 indicates that an association section 516 is
`Scheduled for the frame 512.
`An expanded view of the association section 516 of frame
`512 is shown in FIG. 6. In this example the association
`section 516 is subdivided into 20 slots, indicated by the tick
`marks in the figure. WTA has determined when the asso
`ciation section 516 will occur within the frame 512 from
`Scheduling information transmitted in the control Section
`514 of frame 512. WTA then proceeds to poll in this section,
`for example using a contention based protocol Such as the
`slotted ALOHA format disclosed in GB-B-2 069799, which
`requires WTA to choose at random a slot within the asso
`ciation section 516. FIG. 6 shows WTA polling in the fourth
`slot 602. The base station 108 listens to any polls occurring
`during the association Section 516, and notes the association
`request in the fourth slot 602.
`The base station 108 now Schedules a transmission slot in
`the uplink section 306 of a Subsequent transmission frame.
`At this point the base station 108 can only determine that a
`wireless terminal attempted association in slot 602 of the
`association section 516 in frame 512. Hence in the control
`Section 302 of the Subsequent frame slots in the uplink
`Section 306 are reserved for the wireless terminal 102 that
`attempted association in the fourth slot 602 of the associa
`35
`tion section 516. The information transmitted by WTA
`during this uplink slot enables the base station 108 to decide
`whether to allow WTA to associate with the network. If
`WTA is allowed to associate with the network, the associa
`tion proceeds in the manner defined for the particular
`network Standard being used.
`It is possible for two or more wireless terminals 102 to
`poll in the same slot during an association Section 310. This
`might not be detected by the base station 108 which would
`typically just be detecting whether any energy was trans
`mitted in a particular slot. Hence the same wireleSS terminals
`102 would then transmit during the transmission slot in the
`uplink section 306 reserved for the associating wireless
`terminal. If the base station 108 receives a corrupted signal
`during the Scheduled transmission slot it therefore assumes
`that two or more wireless terminals 102 have transmitted at
`the same time, and takes appropriate actions. These actions
`may include not acknowledging the association requests,
`and Scheduling another association Section 310 as Soon as
`convenient Since it is known that there are wireleSS terminals
`102 attempting association. The wireleSS terminals them
`Selves know by not receiving an acknowledgement that their
`requests have not been Successful, and will attempt asso
`ciation again.
`A method of association in accordance with the present
`invention has the advantage of allowing the base station 108
`the flexibility to determine when to schedule association
`sections 310. This is useful during periods of high trans
`mission activity, when an association Section 310 may be
`postponed to maximise data throughput in the network. An
`upper limit to the length of time that an association Section
`310 can be postponed may be specified for the system. The
`
`6
`flexibility in scheduling association sections 310 is also
`useful during periods of lower activity, when more associa
`tion sections 310 may be scheduled to enable wireless
`terminals 102 to associate with small time delays.
`A possible Scenario showing the Scheduling of association
`sections with varying network load is shown in FIG. 7. The
`lower part of the figure is a plot of network activity Aagainst
`time t, where A might be measured in transmitted bytes per
`Second. The upper part of the figure shows the times at
`which association sections 310 are scheduled. In this
`example when the network load is high the frequency of
`association sections 310 is reduced, but the base station 108
`also ensures that the time between association sections 310
`never exceeds a maximum (for example at least one asso
`ciation section 310 every five seconds).
`The approach described above is equally applicable to a
`peer to peer network using the transmission frame format
`shown in FIG. 4. The main difference is that the control
`function for the network is performed by a dynamically
`chosen enhanced wireless terminal 202.
`From reading the present disclosure, other modifications
`will be apparent to perSons Skilled in the art. Such modifi
`cations may involve other features which are already known
`in the design, manufacture and use of wireleSS networks and
`component parts thereof which may be used instead of or in
`addition to features already described herein.
`What is claimed is:
`1. A method of operating a wireleSS network, wherein
`transmission of data takes place in transmission frames of
`variable length subdivided into a plurality of time slots, the
`wireleSS network comprising a controller and a variable
`number of wireleSS terminals, the method comprising the
`controller maintaining a list of wireless terminals currently
`registered with the network, determining the lengths of
`Successive transmission frames, and allocating time slots
`within Said frame for various purposes, wherein the control
`ler Scheduling a variable number n of association Sections in
`each transmission frame, where n has a minimum value of
`Zero, in response to the current operating characteristics of
`the network, by which asSociation Sections the wireleSS
`terminals can register with the controller.
`2. A method as claimed in claim 1, characterised in that an
`operating characteristic of the network used to determine the
`number of association Sections to Schedule is the loading of
`the network.
`3. A method as claimed in claim 1, characterised in that an
`operating characteristic of the network used to determine the
`number of association Sections to Schedule is the presence of
`a high Security application utilising the network.
`4. A method as claimed in claim 1, characterised in that
`the Scheduling of association Sections can be Suspended
`when the network has allocated its entire capacity to tasks
`other than association.
`5. A controller for a wireless network having a plurality of
`wireleSS terminals, the controller comprising means for
`maintaining a list of wireleSS terminals currently registered
`with the network, means for monitoring the operating char
`acteristics of the network, means for determining the lengths
`of Successive transmission frames and means for allocating
`time slots within each of Said frames, means responsive to
`the current operating characteristics of the network for
`Scheduling a variable number n of association Sections in
`each transmission frame, where n has a minimum value of
`ZCO.
`6. A base Station comprising a controller for a wireleSS
`network having a plurality of wireleSS terminals, the con
`troller comprising means for maintaining a list of wireleSS
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1016, p. 6
`
`
`
`US 6,504,834 B1
`
`7
`terminals currently registered with the network, means for
`monitoring the operating characteristics of the network,
`means for determining the lengths of Successive transmis
`Sion frames and means for allocating time slots within each
`of Said frames, means responsive to the current operating
`characteristics of the network for Scheduling a variable
`number n of association Sections in each transmission frame,
`where n has a minimum value of Zero.
`7. Abase Station as claimed in claim 6, further comprising
`means for connecting to a fixed telecommunications net
`work and means for exchanging data with Said network.
`8. A wireless terminal for use in a wireless network
`constituted by at least one wireless terminal and a controller,
`the wireless terminal comprising transceiver means for
`obtaining Scheduling information relating to transmission
`frames in the network, means for determining whether an
`asSociation Section is available in a transmission frame and
`in that in response to Said means the wireleSS terminal
`attempts association during the association Section.
`9. A wireless terminal as claimed in claim 8, characterised
`in that means are provided for turning off at least the
`transceiver means for the duration of a transmission frame if
`no association Section-has been Scheduled.
`
`8
`10. A wireless terminal for use in a wireless network
`constituted by at least one wireless terminal and a controller,
`the wireleSS terminal comprising transceiver means for
`obtaining Scheduling information relating to transmission
`frames in the network, means for determining whether an
`asSociation Section is available in a transmission frame, Said
`means enabling the wireleSS terminal to attempt association
`during the association Section, and a controller comprising
`means for maintaining a list of wireleSS terminals currently
`registered with the network, means for monitoring the
`operating characteristics of the network, means for deter
`mining the lengths of Successive transmission frames, means
`for allocating time slots within each of Said frames and
`means responsive to the current operating characteristics of
`the network for Scheduling a variable number n of associa
`tion Sections in each transmission frame, where n has a
`minimum value of Zero, the controller enabling the wireleSS
`terminal to function as a base Station in a peer to peer
`network.
`
`15
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1016, p. 7
`
`