United States Patent
`Fischer
`[45] Date of Patent: Dec. 6, 1994
`
`[19]
`
`[11] Patent Number:
`
`5,371,734 '
`
`
`
`USOOS371734A
`
`[54] MEDIUM ACCESS CONTROL PROTOCOL
`FOR WIRELESS NETWORK
`
`Model 200 RF Modem, Signal Tech, Inc., Nov. 14,
`199].
`
`[75]
`
`Inventor: Michael A. Fischer, San Antonio,
`Tex.
`
`Primary Examiner—Wellington Chin
`Attorney, Agent, or Firm—John R. Ley
`
`[73] Assignee: Digital Ocean, Inc., Overland Park,
`Kans.
`
`[21] App]. No.: 11,415
`
`[22] Filed:
`
`Jan. 29, 1993
`
`Int. Cl.5 ........................ H043 7/216; H04B 7/26
`[51]
`[52] US. Cl. ..................................... 370/18; 370/95. 1;
`370/953; 340/825.47; 455/382; 455/542
`[58] Field of Search ....................... 370/18, 95.], 95.3;
`340/825.44, 825.47; 455/382, 38.3, 53.1, 54.1,
`.
`54.2, 68, 69, 70
`
`[55]
`
`Referencs Cited
`U.S. PATENT DOCUMENTS
`
`4,449,248 5/1984 1.85116 et a1. ........................ 455/383
`5,241,542 8/1993 Natarajan et al.
`..
`....... 455/383
`5,276,680
`1/1994 Messenger ......................... 370/95.1
`
`OTHER PUBLICATIONS
`
`AS-IOO Spread Spectrum ASIC, Sigml Technologies,
`Inc., Nov. 14, 1991.
`CSL-IOO MOD/DEMOD ASIC, Signal Tech. Inc.,
`Nov. 14, 1991.
`
`[57]
`
`ABSTRACT
`
`A communicator station wirelessly transmits frames to
`and receives frames from a least one additional commu-
`
`nicator in a Group in accordance with a MAC protocol.
`One of the communicators functions as a hub and the
`remaining communicators function as remotes. The hub
`sends control information to the hubs to establish re-
`peating communication cycles, each of which has inter-
`vals during which the hub and the remotes transmit and
`receive frames. The intervals allow the hub and the
`remotes to anticipate transmitting and receiving frames,
`thereby allowing the remotes to power off their receiv-
`ers and transmitters to achieve a considerable savings in
`power consumption without degrading communica-
`tions. Other improved features include adjusting the
`intervals and the durations of transmission opportunities
`in the communication cycle to obtain the beneficial
`aspects of TDMA and PRMA for LAN-like communi-
`cation without also incurring most of the undesirable
`aspects of such MAC techniques. Other control func-
`tions such as arbitration determine which communica-
`tor is better suited to act as the hub.
`
`47 Claims, 12 Drawing Sheets
`
`
`
`w “W“
`macaw m
`
`
`
`34
`
`as
`
`36
`
`34
`
`34
`
`300
`I
`
`RESOURCE
`
`36
`
`36
`
`.2
`
`60:1
`
`304
`
`38
`
`34
`
`RESOURCE
`
`mERFACE ID
`
`36
`
`ST. JUDE 1001
`ST. IUDE 1001
`
`1
`
`

`

`
`
`
`
`
`W -
`
`301:
`/34
`
`34
`
`34
`
`36
`
`W
`
`36
`
`32
`
`as
`
`32
`
`36
`
`30d
`
`38
`
`34
`
`
`
`30c
`K
`
`60c
`
`34
`
`38
`
`m 3
`
`32
`
`4
`
`38
`
`34
`
`60d
`
`36
`
`We:
`
`
`6
`36
`Fig_1
`32
`
`32
`
`'NTEMQD
`36
`
`VQL‘ILS‘S
`
`2
`
`

`

`US. Patent
`
`Dec. 6, 1994
`
`Sheet 2 of 12
`
`5,371,734
`
`
`
`3
`
`

`

`US. Patent
`
`Dec. 6, 1994
`
`Sheet 3 of 12
`
`5,371,734
`
`
`
`_
`
` DIRECTED
`£9
`
`
`
`
`
`
`
`ALTERNATIVE
`INFORMATION
`
`.82.
`
`4
`
`

`

`34
`
`m
`
`3?
`
`34
`
`38
`
`36
`
`[02
`
`V
`
`
`
`U3°’9WISm‘9mamama'S‘fl
`
`vsL‘ILe‘s
`
`5
`
`

`

`
`
`ZIJO5IIquV66I‘978a”1913aoSon
`
`vsL‘ILs‘s
`
`I02 I00
`v v
`
`’0
`
`”4
`
`"2
`g
`.mm
`~
`«24
`A
`”0 %
` .
`. N .
`.
`'Rx/Tx RF SYNTHESIZER
`E g \x [as
`’40
`’03
`
`II6\
`I42
`1’
`f-—'_A———fi
`r_-___—_—-_—__—_-——'
`- _I
`
`"T;
`
`4
`
`I
`I
`TRANSVERSAL
`I
`’3’
`[34
`128
`I
`|
`-Il
`L- 22:".5232:
`- - - — '1
`I
`CLOCK
`.
`DISTRIBUTOR
`,_ ____________________ _ J
`Fig-5
`
`[38
`
`130
`
`’32
`[36 TRANSVERSAL
`
`SYNTHESIZER
`
`“EAD spec RUM
`
`awn
`
`mmzea
`
`SPREAD SPECTRUM
`G
`R T
`
`Tx/Rx CONTROL
`
`TIMING
`
`”a
`
`122
`
`PROGRAM
`
`124
`
`[26
`
`120
`
`I
`
`I'
`
`I
`
`6
`
`

`

`I44
`
`Fig-6
`
`I48
`
`I46
`
`I48
`
`I50
`
`PREAMBLE
`
`' PAYLOAD
`
`POSTAMBLE
`
`
`
`
`
`I52 \
`
`Fig-8
`
`
`
`
`
`
`
`
`Z11"9mus.7661‘9'090manad'S'n
`
`VSL‘ILS‘S
`
`7
`
`

`

`70
`
`82
`80
`78
`I-—->T|ME 76
`84
`
`
`86
`
`88
`
`F/
`g.
`
`BROADCAST DIRECTED ALT INFO
`,0 INFO
`INTERVAL INTERVAL
`INTERVAL INTERVAL
`
`
`L——-OUTEOUNO PORTION zg—J-———INEOUNO PORTION zg
`
`REMOTE TRANSMISSION
`TXOP INTERVALS
`
`TXOP
`HUB
`$639,152: flfigfim
`
`
`
`___,jINaOUNo l.
`OUTBOUND
`
`72
`
`Fig.”
`
`
`
`I46
`
`200 I54
`
`202
`
`PRE-
`AMBLE
`
`BROADCAS
`FRAM 1
`
`'
`
`
`
`
`I44
`
`I54 202 I54 204
`
`BROADCAST
`FRAME n
`
`DIRECTED
`FRAME 1
`
`I54 204
`
`I50 I46 206 I50
`
`DIRECTED POST- PRE~ mg, posr
`FRAME n AMBLE AMBLE Fm mas
`
`
`
`
`
`L____Y__.__I
`I44
`
`
`
`
`
`REMOTE TXOPl
`
`REMOTE TXOP 2
`
`REMOTE TXOP n
`
`[50
`
`I50
`
`I46
`
`[5/
`
`
`POST-
`TXOP
`PRE-
`AMBLE REQUEST AMBLE
`
`
`
`
`TXOP REQLEST INTERVAL
`
`88
`
`I50 I47 I46
`I49
`I46
`
`
`‘
`
`
`PRE-
`”“9 N
`POST-
`PRE-
`23300
`
`N
`AMBLE WREPLY
`Fig.I4
`AMBLE FRAME AMBLE
`
`
`
`HUB BEACON INTERVAL
`
`
`
`
`
`150
`
`POST-
`AMBLE
`
`
`
`
`
`Z1)0L19948V661‘9'33“111918‘1oSOn
`
`VSL‘ILS‘S
`
`8
`
`

`

`RETRY
`
`
`
`£9?
` N0 HUB
`HUB ACTIVE
`
` DETECTED
`
`
`
`
`NO
`
`ACTIVITY
`
`NO TXOP
`
`VAILABLE
`
`
`TXOP REQUISTED BY
`COMMUNICATOR
`
`
`WITH BETTER
`
`
`ARBITRATION
`
`
`VALUE
`
`ACTIVITY
`
`HUB DETECTED
`
`
`
`
`
`REMOTE
`ACTIVE
`
`
`
`
`211°8wasWI‘9ma”1913a.STI
`
`VSL‘ILC‘S
`
`9
`
`

`

`US. Patent
`
`Dec. 6, 1994
`
`Sheet 9 of 12
`
`5,371,734
`
`SELECT NEXT
`AVAILABLE CHANNEL
`
`ENABLE RECEIVER
`FOR IIO °/o 0F MAX
`COMM. CYCLE
`
`25/
`
`253
`
`2'57
`
`YES
`
`
`HAN“
`
`c
`NEL
`
`VAILAaLE
`
`
`252] NO
`
`TO HUB ACT IVE
`STATE
`
`255
`
`YES
`
`259
`
`
`
`
`AcTRICm
`
`DETgCTED
`
`'
`
`
`DETE?CTED
`
`
`VALID
`YES
`FRAMES
`
`ADJUST CALIBRATION
`
`
`
`YES
`
`WAIT TO RECEIVE
`
`INFO FRAME
`
`26/
`
`I(2:58
`
`TO REQUEST
`TXOP STATE
`
`Fig-l6
`
`10
`
`10
`
`

`

`US. Patent
`
`Dec. 6, 1994
`
`Sheet 10 of 12
`
`5,371,734
`
`DETERMINE TIME OF
`TXOP. REQUEST
`INTERVAL
`
`SEND TXOP REQUEST
`FRAME
`
`275
`
`WAIT FOR RANDOM
`NO. OF COMM.
`CYCLES
`
`AWAIT, REPLY
`DURING NEXT CYCLE
`
`267
`
`269
`
`27/
`
`273
`
`MODE
`
`HUB HANDOFF FRAME
`
`TXOI;
`mm
`
`277
`
`279
`
`2502
`
`NO
`
`260]
`
`TXOP
`"0:0
`YES
`
`TO LISTEN RF
`STATE
`
`TO REMOTE
`ACTIVE STATE
`
`SEND HUB HANDOFF.
`REPLY FRAME
`Zia—ZU—fi
`
`T0 HUB ACTIVE
`STATE
`
`Fig-1?
`
`11
`
`11
`
`

`

`US. Patent
`
`Dec. 6, 1994
`
`Sheet 11 of 12
`
`5,371,734
`
`ALLOCATE 1x093 PER
`PREVIOUS REQUESTS
`
`252
`
`DETERMINE COARSE
`CYCLE DURATION
`
`RANDOMLY SELECT
`FINE DURATION
`ADJUSTMENT
`
`264
`
`256
`
`284
`
`WAIT FOR
`POTENTIAL TXOF‘~
`REQUEST FRAMES
`
`
`
`286
`
`ASSEMBLE AND
`
`268
`
`TRANSMIT “=0 FRAME
`BEACON FRAME
`
`
`
`SEN) I'IJB
`
`WAIT FOR
`POTENTIAL HUB
`3m" REPL'ES
`_
`
`27"
`
`276
`
`YES -mnsm PENDING
`DIRECTED FRAMES
`
`
`
`DIRECTED
`““55
`PENDING
`
`N0.
`
`RETRANSMIT INFO
`FRAME (ALT INFO)
`
`78
`
`2
`
`280
`
`282
`
`YES
`
`RECEIVE PENDING
`
`I INCWING FRAMI
`
`NO
`
`Fig- I8
`
`12
`
`12
`
`

`

`US. Patent
`
`Dec. 6, 1994
`
`Sheet 12 of 12
`
`5,371,734
`
`290
`
`ACTIVATE RECEIVER
`FOR INFO FRAME
`
`2.92
`
`o ‘ u
`FRAME
`PENPING
`
`294
`
`
`
`
`
`
`
` RECEIVE BROADCAST
`
`FRAMES AND
`TRANSFER TO LAN
`
`
`
`
`
`
`DIRECTED
`FRAMES
`PENPING
`
`
`
` RECEIVE DIRECTED
`
`
`
`304
`
`
`
`
`Pgoolne
`N0
`REMAIN WITH -
`POWER DOWN
`MMED;ATELY
`UNTIL TXOP TIME
`
`300
`
`NO
`
`POWER DOWN
`UNTIL TXOF TIME
`
`296
`
`298
`
`302
`
`FRAMES AND
`TRANSFER TO LAN
`
`
`
`
` ACTIVATE
`
`
` ACTIVATE
`
`AND SEND
`CONTROL FRAME
`
`
`TRANSMITTER
`
`
`
`TRANSMITTER
`
`AND SEND
`
`PENDING FRAMES
`
` 3/2
`
`13
`
`

`

`1
`
`
`
`5,371,734
`
`
`
`
`2
`
`
`
`
`
`
`
`Because of the increasing recognition of the benefits
`
`
`
`
`
`of communicating information quickly between re-
`
`
`
`
`
`
`
`sources and of sharing resources in computational situa-
`
`
`
`
`
`
`
`tions, LANs and networking in general are becoming
`
`
`
`
`
`
`widely used. Networking of personal computers and
`
`
`
`
`
`
`
`work stations allows for easy and effective communica-
`
`
`
`
`
`
`tion and exchange of information between computers,
`
`
`
`
`
`
`
`
`as well as cost effective sharing of computer resources
`
`
`
`
`
`
`such as hard disks and printers.
`
`
`
`
`
`Implementing a LAN can present a significant imped-
`
`
`
`
`
`
`
`
`
`
`iment when it is recognized that all of the resources
`
`
`
`
`
`
`
`
`must me wired together, particularly if the resources
`
`
`
`
`
`
`
`
`are physically separated and numerous. It is not unusual
`
`
`
`
`
`
`
`
`
`
`that many thousands or tens of thousands of feet or
`
`
`
`
`
`
`
`
`
`
`
`meters of cable may be required to connect a few tens or
`hundreds of resources, even when none of the resources
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`is separated by more than a few hundreds of feet or
`
`
`
`
`
`
`
`meters. In existing facilities, sufficient physical access
`
`
`
`
`
`
`
`
`
`may not be available to route the necessary cabling.
`
`
`
`
`
`
`
`
`Installation, even if possible, may be very expensive.
`
`
`
`
`
`
`
`
`Even in designing and constructing new facilities, the
`
`
`
`
`
`
`
`cable expense itself for networking among a large num-
`
`
`
`
`
`
`
`
`
`ber of personal computers or work stations may be
`cost-prohibitive.
`
`Networks of LAN-like functionality have been estab-
`
`
`
`
`
`
`
`
`
`
`
`
`
`lished in the past by implementing the communication
`medium with wireless RF links between the resources.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`One difficulty presented by such systems is that MAC
`
`
`
`
`
`
`
`becomes considerably more difficult, because the RF
`
`
`
`
`
`
`
`
`links do not permit the transmitting and receiving sta-
`
`
`
`
`
`
`
`
`
`
`tions (akin to nodes on a LAN) to sense the use of the
`
`
`
`
`
`
`
`
`
`
`
`medium (the RF signals) as reliably as in a wired net-
`
`
`
`
`
`
`
`work. Timing and synchronization requirements for the
`
`
`
`
`
`
`
`transmission of messages, static and interference from
`
`
`
`
`
`
`
`
`sources of RF noise, transmission and reception range
`
`
`
`
`
`
`
`limitations, multipath interference and fading and other
`
`
`
`
`
`
`
`known difficulties, all become significant concerns and
`
`
`
`
`
`
`
`limitations in implementing MAC protocols for wireless
`
`
`
`
`
`
`
`networks. These same concerns are generally not re-
`
`
`
`
`
`
`
`
`
`garded as highly significant in wired or optical fiber
`
`
`
`
`
`
`
`
`networks because the integrity of the cabled medium
`
`
`
`
`
`
`
`
`
`
`usually avoids most if not all of these concerns. The
`
`
`
`
`
`
`
`integrity of the wired communication medium usually
`
`
`
`
`
`
`
`eliminates or significantly reduces the concerns about
`
`
`
`
`
`
`interference because the cabling offers inherent shield-
`
`
`
`
`
`
`
`
`ing from interference. Because the integrity of the com-
`
`
`
`
`
`
`munication is essentially assured in transmissions over
`
`
`
`
`
`
`
`
`the wires, range and signalling issues generally do not
`
`
`
`
`
`
`
`become significant. Light links have also been em-
`
`
`
`
`
`
`
`
`
`ployed in networks, but the difficulties with light linked
`
`
`
`
`
`
`
`
`networks are usually even more exaggerated because of
`
`
`
`
`
`
`
`
`the directionality required for directing light beams in
`
`
`
`
`unobstructed, line-of-sight, signal paths.
`
`
`
`
`
`
`
`To make the communications more reliable by avoid-
`
`
`
`
`
`
`
`
`
`ing many of the problems caused by the difficulties
`associated with the wireless medium, a variety of differ-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ent MAC techniques have been employed in wireless
`
`
`
`
`
`
`
`
`network systems. In general
`the objective of these
`
`
`
`
`
`
`
`
`
`MAC techniques has been to add reliability to the com-
`
`
`
`
`
`
`
`munication process by compensating, to a certain de-
`
`
`
`
`
`
`
`gree, for the greater uncertainties associated with the
`wireless medium.
`
`
`
`
`
`
`
`
`
`
`One of the most widely used MAC techniques, origi-
`
`
`
`
`
`
`
`nally developed for wireless network systems, but now
`
`
`
`
`
`
`
`
`employed for several of the most common wired net-
`work standards, is referred to as carrier-sense multiple
`
`
`
`
`
`
`
`
`access (CSMA). In CSMA, each station uses its receiver
`
`
`
`
`
`
`
`
`
`to monitor the network medium for other transmission
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`MEDIUM ACCESS CONTROL PROTOCOL FOR
`
`
`
`
`WIRELESS NETWORK
`
`
`
`
`
`
`
`CROSS-REFERENCE TO RELATED
`
`
`APPLICATION
`
`
`
`
`
`
`
`
`This invention relates to an invention for a Technique
`
`
`
`
`
`
`for Bridging Local Area Networks Having Non-
`Unique Node Addresses, Ser. No. 08/011,361, filed
`
`
`
`
`
`
`
`concurrently herewith, by the inventor hereof, and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`assigned to the assignee of this Application. The disclo-
`
`
`
`
`
`
`
`
`sure of this related invention is incorporated herein by
`this reference.
`
`
`FIELD OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
`This invention relates to a technique and protocol for
`
`
`
`
`
`
`connecting multiple distinct computer resources by
`
`
`
`
`
`
`
`radio frequency (RF) or other wireless communications
`
`
`
`
`
`
`
`
`
`to establish a single logical network of the resources to
`permit communication between the distinct resources
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`similar to that of a local area network (LAN). Even
`
`
`
`
`
`
`
`
`more specifically, the present invention relates to a
`
`
`
`
`
`
`
`medium access control (MAC) technique or protocol
`
`
`
`
`
`
`for selectively activating and deactivating the transmit-
`
`
`
`
`
`
`
`
`ters and receivers of the means for communicating be-
`
`
`
`
`
`
`
`
`tween the resources to save electrical power consumed
`
`
`
`
`
`
`while still permitting LAN-like functionality, thereby
`
`
`
`
`
`
`
`
`extending considerably the ability of the resources to
`
`
`
`
`
`remain operable when battery powered.
`BACKGROUND OF THE INVENTION
`
`
`
`
`A LAN is a well-known means of achieving commu-
`
`
`
`
`
`
`
`nication between different resources,
`typically com-
`
`
`
`
`
`puter resources such as computers, work stations, print-
`
`
`
`
`
`
`
`ers and the like. The LAN itself includes a network
`
`
`
`
`
`
`
`
`
`
`interface connected to each resource and a physical
`
`
`
`
`
`
`
`
`communication medium connecting all of the interfaces.
`
`
`
`
`
`
`
`The interface and connected resource constitute a node.
`
`
`
`
`
`
`
`Each node has an unambiguous address or identification
`
`
`
`
`
`
`
`
`(ID). Communication between nodes is typically ac-
`
`
`
`
`
`
`complished by sending and receiving an ordered Group
`
`
`
`
`
`
`
`
`of bits known as a frame or packet. Each frame is sent
`
`
`
`
`
`
`
`
`
`
`
`
`from a source node, and is received by a destination
`
`
`
`
`
`
`
`
`
`
`node. The ID of the source node (SID) and the ID of
`
`
`
`
`
`
`
`
`
`
`
`
`the destination node (DID) are frequently included
`
`
`
`
`
`
`
`within the frame in Groups of sequential bits known as
`
`
`
`
`
`
`
`
`
`
`fields. The technique of communicating between the
`
`
`
`
`
`
`
`nodes, and of controlling the composition of frames, is
`
`
`
`
`
`
`
`
`
`defined by a network protocol.
`
`
`
`
`The network protocol includes a MAC aspect which
`
`
`
`
`
`
`establishes an orderly and predictable ability of each
`
`
`
`
`
`
`
`node to access the medium, for the purposes of commu-
`
`
`
`
`
`
`
`
`
`nicating with another node by transmitting and receiv-
`
`
`
`
`
`
`
`ing frames, of requesting access to the medium and
`
`
`
`
`
`
`
`
`
`acknowledging previous frame communication. With-
`
`
`
`
`out an orderly and predictable MAC technique, chaotic
`
`
`
`
`
`
`
`
`and inefficient communication, if any, would prevail,
`
`
`
`
`
`
`
`because it is highly unlikely that the frames sent from
`
`
`
`
`
`
`
`
`
`
`the source node would reach the destination node with-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`out interference and disruption caused by conflicting
`
`
`
`
`
`
`
`
`
`
`frames sent by another node at the same or overlapping
`
`
`
`
`
`
`
`
`
`
`time periods or at a time that the destination node was
`not ready to receive a frame. Therefore, the MAC facil-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ities are one of the very important aspects of any LAN-
`
`
`
`
`
`
`
`like communication protocol among a plurality of equal
`
`
`
`
`
`
`
`peer-type transmitting and receiving stations such as
`nodes.
`
`
`5
`
`
`
`10
`
`15
`
`
`
`
`
`
`
`
`
`20
`
`
`25
`
`
`30
`
`
`35
`
`
`
`
`45
`
`
`
`
`
`SO
`
`
`55
`
`
`
`
`65
`
`
`14
`
`14
`
`

`

`
`5,371,734
`
`
`
`
`
`10
`
`
`
`
`
`
`25
`
`
`3
`
`
`
`
`
`
`
`
`activity prior to activating its transmitter. If any such
`
`
`
`
`
`
`
`
`activity is detected, the station waits until a predeter-
`mined time after the end of the detected network activ-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ity. If two or more stations begin transmitting at close
`
`
`
`
`
`
`
`
`
`
`
`
`enough to the same point in time so that none of these 5
`
`
`
`
`
`
`
`stations detect each other’s transmission, the resulting
`transmissions are said to collide, with the result that
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`none of the frames being transmitted by these stations
`
`
`
`
`
`
`
`
`
`are able to be successfully received at their intended
`destinations.
`
`
`
`
`
`
`
`
`
`While CSMA protocols offer very low latency to
`
`
`
`
`
`
`
`
`begin communication during periods when little or no
`
`
`
`
`
`
`
`
`other network message traffic is active, they perform
`
`
`
`
`
`
`
`
`
`poorly when many stations are contending for access to
`
`
`
`
`
`
`
`
`
`the medium to send frames or when the aggregate 15
`amount to be transmitted exceeds about half of the data
`
`
`
`
`
`
`
`
`
`
`bandwidth of the network medium. In addition to this
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`problem with saturation at well below the rated capac-
`ity of the network, wireless CSMA networks have in-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`creased chances for collisions when compared with 20
`wired CSMA networks, because obstructions to RF
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`signal propagation could permit a station to erroneously
`
`
`
`
`
`
`
`detect an available network medium, allowing that sta-
`tion to activate its transmitter while another station was
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`in the process of sending a frame.
`
`
`
`
`
`
`
`
`Another MAC technique which is typically used in
`
`
`
`
`
`
`
`
`
`wireless networks is referred to as time division multiple
`
`
`
`
`
`
`
`
`
`access (TDMA). In TDMA, the available time for the
`multiplicity of the stations to access and use the radio
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`links is divided among each of the stations. Each station 30
`
`
`
`
`
`
`
`
`has its own predesignated and assigned time Txop for
`
`
`
`
`
`
`
`
`communicating RF messages with other stations. Each
`
`
`
`
`
`
`
`
`station recognizes and operates under recognition of the
`
`
`
`
`
`
`
`
`
`
`order and sequence of the time Txops assigned to the
`
`
`
`
`
`
`
`
`
`
`other stations, to avoid overlap and conflict in the com- 35
`munications.
`
`
`
`
`
`
`
`
`While TDMA protocols are generally very effective
`
`
`
`
`
`
`in providing reliably recognized opportunities for com-
`
`
`
`
`
`
`
`
`municating messages, they can result in a reduced ca-
`
`
`
`
`
`
`
`
`pacity or data bandwidth for transmitting information 40
`between stations when the communications are inter-
`
`
`
`
`
`
`
`
`
`
`
`
`quantities of
`variable
`length messages
`mittent
`
`
`
`
`
`
`
`
`(“bursts”). In burst message situations, which are highly
`
`
`
`
`
`
`typical of LAN-type communications, TDMA results
`
`
`
`
`
`
`
`
`in reduced useable data bandwidth because a large por- 45
`tion of the available time is unused for data communica-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tions because that time is assigned to stations that have
`
`
`
`
`
`
`
`
`
`
`nothing to send when their time slots occur. In situa-
`tions where one station may have a considerable
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`amount to send, the information must be broken up into 50
`
`
`
`
`
`
`
`
`
`
`parts and sent in sequence, one part each time the sta-
`
`
`
`
`
`
`
`tion’s time occurs. Thus, TDMA, while providing reli-
`able medium access in the difficult medium access envi-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ronment of wireless networks, does not provide the
`
`
`
`
`
`
`
`
`
`
`higher message throughput or bandwidth as do some of 55
`the more traditional LANs.
`
`
`
`
`
`
`
`
`
`
`
`
`Another MAC technique which is typically used in
`
`
`
`
`
`
`
`
`wireless networks is referred to as packet reservation
`multiple access (PRMA). In PRMA, each of the multi-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`plicity of the stations must request and reserve a time to 60
`
`
`
`
`
`
`
`
`
`
`
`access and use the radio link to send its packets or
`
`
`
`
`
`
`
`
`
`
`frames. The requests are made on the basis of the
`amount of time that each station expects to use in com-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`municating the amount of information it has queued for
`delivery to another station. The available time for all 65
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the stations to communicate is divided among each of
`
`
`
`
`
`
`
`
`
`the stations according to the requests of the stations.
`The time allocation reserved for each station is commu-
`
`
`
`
`
`
`
`
`
`
`
`15
`
`
`
`
`
`4
`nicated to all of the stations, so all of the stations recog-
`
`
`
`
`
`
`
`
`
`
`
`nize which stations have a time allocation, how long the
`
`
`
`
`
`
`
`
`
`time allocation is and in what order the stations will
`
`
`
`
`
`
`
`
`
`
`receive and use their allocations. After this information
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`is conveyed, each station requesting time uses its re-
`served time in its assigned order to communicate pack-
`
`
`
`
`
`
`
`
`ets or frames with other stations.
`
`
`
`
`
`
`
`
`
`
`
`
`PRMA techniques are more effective than TDMA
`
`
`
`
`
`
`
`techniques in utilizing the available time, because only
`
`
`
`
`
`
`
`
`
`those stations with messages to send need to be pro-
`
`
`
`
`
`
`
`
`vided with an opportunity to send messages. However,
`
`
`
`
`
`
`
`
`
`fast response to requests is impossible because of the
`
`
`
`
`
`
`
`delays inherent in obtaining a reservation. A consider-
`able amount of the available time is consumed in the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`rather complex communication of control information,
`referred to as “overhead.” The overhead is used for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`requesting time, allocating a reservation of time, com-
`
`
`
`
`
`
`municating the amount of time reserved, communicat-
`
`
`
`
`
`
`
`
`
`
`ing the order in which the stations receive the time
`
`
`
`
`
`
`
`reservations, and the like. As a consequence, the quan-
`
`
`
`
`
`
`
`
`
`
`tity of useful data bandwidth of PRMA networks is also
`limited.
`
`
`
`
`
`
`
`
`Another recent deve10pment in the field of comput—
`
`
`
`
`
`
`
`ing is the increasing proliferation of battery-powered,
`
`
`
`
`
`
`portable computers. These portable computers allow
`
`
`
`
`
`
`
`
`computational tasks to be performed wherever the user
`
`
`
`
`
`
`
`
`happens to be located. Portable computers are usually
`
`
`
`
`
`
`
`
`used during travel, because portability is their primary
`
`
`
`
`
`
`
`
`advantage. Even during travel, however, there may be
`
`
`
`
`
`
`
`
`
`a need to access other computer resources through the
`
`
`
`
`
`
`
`
`
`portable computer, just as is more typically done with
`
`
`
`
`
`
`
`stationary resources. It may desirable to create tempo—
`
`
`
`
`
`
`
`
`
`
`rary, ad hoc networks of portable computers so that, for
`
`
`
`
`
`
`
`
`example, users can network their portable computers to
`
`
`
`
`
`
`
`
`
`exchange data in meetings and classrooms. Of course in
`
`
`
`
`
`
`these situations, physically connecting the portable
`
`
`
`
`
`
`
`computers to a wired network medium may be inconve-
`
`
`
`
`
`
`
`
`
`nient or impossible. In addition, the users and their
`
`
`
`
`
`
`
`
`locations may not be specifically predefined, and may
`
`
`
`
`
`
`
`change intermittently. In addition, to connect portable
`
`
`
`
`
`
`
`computers with RF or other wireless networking capa-
`bility, it is necessary that the transmitters and receivers
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`also operate from battery power, otherwise one of the
`
`
`
`
`
`
`
`
`primary benefits of wireless networking is negated by
`
`
`
`
`
`
`
`
`
`requiring the use of a power wire instead of a network
`
`
`
`
`
`
`
`medium wire. The additional power drain resulting
`
`
`
`
`
`
`from operating the transmitters and receivers dimin-
`
`
`
`
`
`
`
`
`
`ishes the available power for the portable computer. If
`
`
`
`
`
`
`
`
`separate batteries are employed for the transmitter and
`
`
`
`
`
`
`
`
`
`
`receiver on one hand and for the portable computer on
`the other hand, the batteries for the transmitter and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`receiver should be able to provide as much longevity of
`use for the transmitter and receiver as the batteries for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the portable computer provide, without being so large
`
`
`
`
`
`
`
`or heavy as to interfere with portability.
`
`
`
`
`
`
`
`
`A major obstacle to adequate battery life for battery-
`
`
`
`
`
`
`operated wireless network interfaces is that conven-
`
`
`
`
`
`
`tional MAC protocols, whether using CSMA tech
`
`
`
`
`
`
`
`niques, TDMA techniques, PRMA techniques, or other
`
`
`
`
`
`
`
`
`
`techniques (such as token passing), all assume that the
`network receivers are capable of receiving frames at all
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`times that they are not actively transmitting. Conse-
`
`
`
`
`
`
`
`quently these MAC prior techniques are concerned
`only with controlling access to the network medium by
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`transmitters. Because low-power, short-distance radio
`
`
`
`
`
`
`
`
`transceivers consume about as much electrical power in
`
`
`
`
`
`
`
`
`their receiving function as in their transmitting function,
`
`
`
`
`
`
`
`
`a useful protocol for battery operated networking must
`
`15
`
`

`

`5,371,734
`
`
`5
`
`
`
`
`
`
`
`
`avoid this assumption, and must concern itself with the
`access to the network medium by the receivers as well
`
`
`
`
`
`
`
`
`
`as the transmitters.
`
`
`
`
`
`
`
`
`
`
`It is against this background that the significant im-
`
`
`
`
`
`
`provements and advancements of the present invention
`have evolved.
`
`
`
`
`
`SUMMARY OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10
`
`15
`
`
`
`
`
`20
`
`
`25
`
`
`30
`
`
`
`
`
`35
`
`
`
`
`
`
`4s
`
`
`50
`
`
`It is the overall objective of the present invention to
`
`
`
`
`
`
`
`
`
`provide a reliable medium access control (MAC) proto-
`
`
`
`
`
`
`for wireless, preferably radio frequency (RF),
`col
`
`
`
`
`
`
`LAN-type network communications among a plurality
`
`
`
`
`of resources, such a battery powered portable comput-
`
`
`
`
`
`
`ers. The MAC protocol of the present invention pro-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`vides the reliable, predictable aSpects of medium access
`
`
`
`
`
`
`
`
`
`similar to those obtained in TDMA, and also provides
`
`
`
`
`
`
`
`the more effective allocation of available bandwidth
`
`
`
`
`
`
`
`
`among those resources which have messages to send,
`
`
`
`
`
`
`
`
`
`similar to those available from PRMA. In addition, the
`
`
`
`
`
`
`
`
`
`MAC protocol of the present invention avoids many of
`
`
`
`
`
`
`
`the disadvantages associated with the inefficiencies of
`
`
`
`
`
`
`
`LAN-type burst communications in TDMA, the high
`
`
`
`
`
`
`overhead requirements for communications in PRMA,
`
`
`
`
`
`
`
`
`and the problems of avoiding collisions and saturation
`
`
`
`
`
`
`
`
`that affect CSMA. Further still, the present invention
`
`
`
`
`
`
`
`
`provides a MAC protocol which may be very effec-
`
`
`
`
`
`
`tively implemented with communicator stations used
`
`
`
`
`
`
`
`with portable computers, because it obtains significant
`
`
`
`
`
`
`
`
`reductions in battery power drain by permitting the
`receivers as well as the transmitters of the communica-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tor stations to be powered off during a majority of the
`
`
`
`
`
`
`
`time, but selectively and predictably powered on to
`send or receive relevant communications.
`
`
`
`
`
`In accordance with these and other aspects, a com-
`
`
`
`
`
`
`
`
`municator station or communicator wirelessly transmits
`
`
`
`
`
`
`frames to and receives frames from a least one addi-
`
`
`
`
`
`
`
`
`
`tional communicator in accordance with a predeter-
`
`
`
`
`
`
`mined MAC protocol. Each communicator includes a
`
`
`
`
`
`
`
`transmitter and a receiver. The communication occurs
`
`
`
`
`
`
`
`among members of a Group of communicators. The
`
`
`
`
`
`
`
`MAC protocol controls each communicator of the
`
`
`
`
`
`
`
`Group. One of the communicators of the Group is des-
`
`
`
`
`
`
`
`
`
`ignated as a “hub” and the remaining communicators
`
`
`
`
`
`
`
`are designated as “remotes”. The hub establishes repeat-
`
`
`
`
`
`
`
`ing communication cycles, each of which has intervals
`
`
`
`
`
`
`
`
`during which the hub and the remotes transmit and
`
`
`
`
`
`
`
`
`
`receive frames. The hub transmits control information
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`to the remotes to establish the communication cycle and
`
`
`
`
`
`
`
`to establish a plurality of predeterminable intervals
`
`
`
`
`
`
`during each comrhunication cycle. These intervals
`
`
`
`
`
`
`
`
`
`
`allow the hub to transmit frames to the remotes, allow
`
`
`
`
`
`
`
`
`
`
`the remotes to transmit frames to the hub, and allow
`
`
`
`
`
`
`
`
`each remote to anticipate receiving frames from the
`hub. Due to the defined intervals of the communication
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`cycle and the information conveyed by the hub, the
`
`
`
`
`
`
`
`
`
`remotes are able to power off their transmitters during
`times other than those intervals when the remote is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`allowed to transmit frames to the hub. In addition, and
`
`
`
`
`
`
`
`
`
`very significantly, the remotes are able to power off
`
`
`
`
`
`
`
`
`their receivers during times other than those intervals
`
`
`
`
`
`
`
`
`
`
`when the remote is expected to receive frames from the
`hub. Thus, the control information and the communica-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion cycle conserve considerable power because the
`
`
`
`
`
`
`
`
`receivers and transmitters of the remotes may remain
`
`
`
`
`
`
`
`
`powered off for a considerable portion of time without
`degrading communications.
`
`
`
`
`
`
`
`
`
`
`Another desirable aspect of the MAC protocol of the
`present invention is that the hub allocates transmission
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`6
`
`
`
`
`
`
`
`opportunities (Txops) to the remotes, preferably based
`
`
`
`
`
`
`
`
`on bandwidth requests from the hubs. Txop allocation
`information is communicated to the remotes. Previous
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Txop allocations may be revoked or relinquished for
`non-use or very low use as determined by the hub moni-
`
`
`
`
`
`
`
`
`
`
`toring the frames transmitted by each remote, for exam-
`
`
`
`
`
`
`
`
`ple. In addition the Txop allocations may be varied or
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`adjusted by the hub from one communication cycle to
`
`
`
`
`
`
`
`
`
`the next
`to account for changes in activity of the
`
`
`
`
`
`
`
`
`remotes. The adjustment occurs in relation to the num-
`
`
`
`
`
`
`
`
`
`
`ber of frames or quantity of data transmitted by each
`
`
`
`
`
`
`
`remote during recent communication cycles. Thus, the
`
`
`
`
`
`
`
`
`desirable aspects of TDMA are achieved by providing
`
`
`
`
`
`
`
`specific predeterminable intervals for Txops, and the
`desirable aspects of PRMA are achieved by adjusting
`
`
`
`
`
`
`
`
`the durations of the Txops to accommodate the commu-
`
`
`
`
`
`
`
`
`nication of the more active remotes. Battery power
`
`
`
`
`
`
`
`concerns are addressed by allowing the predetermina-
`
`
`
`
`
`
`ble intervals for receiving frames, thus allowing the
`
`
`
`
`
`
`
`receivers to be powered off until the frames are antici-
`
`
`
`
`
`
`
`
`
`pated.
`
`Another aspect of the MAC protocol of the present
`
`
`
`
`
`
`
`
`
`invention involves conveying a variety of beneficial
`
`
`
`
`
`
`
`information concerning the communication cycle to the
`
`
`
`
`
`
`
`remotes, preferably at the beginning of each communi-
`
`
`
`
`
`
`
`cation cycle, to achieve numerous other improvements.
`
`
`
`
`
`
`
`The hub transmits information to the remotes in a man-
`
`
`
`
`
`
`
`
`ner which does not incur a high overhead penalty. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(hub preferably adjusts the length of a communication
`
`
`
`
`
`
`
`cycle relative to the length of a previous communica-
`tion cycle to avoid some of the problems of interference
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`from sources of periodic noise. The hub preferably
`transmits the information to the remotes twice during
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`each communication cycle to reduce the possibility of a
`
`
`
`
`
`
`
`
`remote failing to receive the information during any
`
`
`
`
`
`
`
`communication cycle. Each remote preferably has the
`
`
`
`
`
`
`
`
`
`ability to select one among the plurality of antennas
`
`
`
`
`
`
`
`
`with which to receive RF signals during each commu-
`
`
`
`
`
`
`
`
`nication cycle based on the strength of the received
`
`
`
`
`
`
`signal, preferably during a preamble portion of a trans-
`fer unit from the hub which includes the information.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Preferably,
`the RF signals .employ direct sequence
`
`
`
`
`
`spread spectrum modulation and demodulation estab-
`
`
`
`
`
`
`
`
`
`lished by a predetermined spreading code set by the hub
`
`
`
`
`
`
`
`to more effectively achieve good communication. The
`hub and a newly active remote also exchange operating
`
`
`
`
`
`
`
`
`characteristic information to allow negotiation of which
`
`
`
`
`
`
`
`communicator would better serve as a hub for the
`
`
`
`
`
`
`
`
`
`Group. The operational responsibility as the hub is
`
`
`
`
`
`
`
`
`preferably transferable from one communicator to an-
`
`
`
`
`
`
`other. Adjacent hubs of di