`
`(12) United States Patent
`Belcea
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,796,573 B2
`*Sep. 14, 2010
`
`(54) TERMINAL OPERATING WITHIN AN
`AD-HOC, PEER-TO-PEER RADIO NETWORK
`(75) Inventor: John M. Belcea, West Melbourne, FL
`(US)
`(73) Assignee: Meshnetworks, Inc., Lake Mary, FL
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 544 days.
`This patent is Subject to a terminal dis
`claimer.
`
`(*) Notice:
`
`(21) Appl. No.: 11/776,273
`
`(22) Filed:
`
`Jul. 11, 2007
`
`(65)
`
`Prior Publication Data
`US 2008/OO13497 A1
`Jan. 17, 2008
`
`Related U.S. Application Data
`(63) Continuation of application No. 09/846,434, filed on
`May 2, 2001, now Pat. No. 7,266,104, and a continu
`ation of application No. 09/815,157, filed on Mar. 22,
`2001, now Pat. No. 6,807,165.
`(60) Provisional application No. 60/246,833, filed on Nov.
`8, 2000.
`
`(51) Int. Cl.
`(2009.01)
`H0474/00
`(52) U.S. Cl. ....................................... 370/338: 370/436
`(58) Field of Classification Search ................. 370/338,
`37Of 436
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`4,494,192 A
`
`1, 1985 Lew et al.
`
`4,617,656 A 10/1986 Kobayashi et al.
`4,736,371 A
`4/1988 Tejima et al.
`4,742,357 A
`5/1988 Rackley
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`CA
`
`213218O
`
`3, 1996
`
`(Continued)
`OTHER PUBLICATIONS
`
`Broch, Josh et al. A Performance Comparison of Multi-Hop Wireless
`Ad Hoc Network Routing Protocols, Proceedings of the 4th Annual
`ACM/IEEE International Conference on Mobile Computing and
`Networking, Oct. 25-30, 1998, 16 pages.
`(Continued)
`Primary Examiner Anh-Vu Ly
`(74) Attorney, Agent, or Firm Randi L. Karpinia
`
`(57)
`
`ABSTRACT
`
`A terminal for operation within an ad-hoc, peer-to-peer radio
`system wherein the system includes a series of radio termi
`nals forming a service group. The terminal having a trans
`ceiver for communicating with terminals in the same service
`group, computer means, and memory for storing program
`software. Within the system, the terminal establishes a con
`nection with one radio terminal based on time-division
`access; initiating an outgoing call from the radio terminal
`including registering with another radio terminal for serving
`as a node in the call connection by transmitting a registration
`request; and initially transmitting said registration request on
`a last time slot (TS) of a respective time frame (TF), said last
`time slot serving as a configuration channel.
`
`14 Claims, 6 Drawing Sheets
`
`f
`
`TIME
`FRAME
`
`
`
`TIME
`18 SLOT
`
`LAST TIME
`SLOT
`
`INTER
`FRAMETIME-20
`GAP
`
`Uniloc Ex. 2003
`Microsoft v. Uniloc
`IPR2019-01116
`1
`
`
`
`U.S. PATENT DOCUMENTS
`
`4,747,130
`4,910,521
`5,034,961
`5,068,916
`5,231,634
`5,233,604
`5,241,542
`5,317,566
`5,392.450
`5,412,654
`5,424,747
`5,502.722
`5,517.491
`5,555.425
`5,555,540
`5,572,528
`5,615,212
`5,618,045
`5,621,732
`5,623,495
`5,627,976
`5,631,897
`5,644,576
`5,652,751
`5,680,392
`5,684,794
`5,687,194
`5,696,903
`5,701,294
`5,706428
`5,717,689
`5,745.483
`5,748,624
`5,774,876
`5,781,540
`5,787,076
`5,787,080
`5,794,154
`5,796,732
`5,796,741
`5,805,593
`5,805,842
`5,805,977
`5,809,518
`5,822.309
`5,844,905
`5,845,097
`5,857,084
`5,870,350
`5,877,724
`5,881,095
`5,881,372
`5,886,992
`5,896,561
`5,903.559
`5,909,651
`5,936,953
`5,943,322
`5,987,011
`5,987.033
`5.991,279
`6,016,311
`6,028,853
`6,029,074
`6,029,217
`6,034,542
`6,044,062
`6,047,330
`6,052,594
`6,052,752
`6,058, 106
`
`5, 1988
`3, 1990
`7, 1991
`11, 1991
`7, 1993
`8, 1993
`8, 1993
`5, 1994
`2, 1995
`5, 1995
`6, 1995
`3, 1996
`5, 1996
`9, 1996
`9, 1996
`11, 1996
`3, 1997
`4, 1997
`4, 1997
`4, 1997
`5, 1997
`5, 1997
`7, 1997
`7, 1997
`10, 1997
`11, 1997
`11, 1997
`12, 1997
`12, 1997
`1, 1998
`2, 1998
`4, 1998
`5, 1998
`6, 1998
`7, 1998
`7, 1998
`7, 1998
`8, 1998
`8, 1998
`8, 1998
`9, 1998
`9, 1998
`9, 1998
`9, 1998
`10, 1998
`12, 1998
`12, 1998
`1, 1999
`2, 1999
`3, 1999
`3, 1999
`3, 1999
`3, 1999
`4, 1999
`5, 1999
`6, 1999
`8, 1999
`8, 1999
`11, 1999
`11, 1999
`11, 1999
`1, 2000
`2, 2000
`2, 2000
`2, 2000
`3, 2000
`3, 2000
`4, 2000
`4, 2000
`4, 2000
`5, 2000
`
`Ho
`Mellon
`Adams
`Harrison et al.
`Giles et al.
`Ahmadi et al.
`Natarajan et al.
`Joshi
`Nossen
`Perkins
`Chazelas et al.
`Fulghum
`Nanni et al.
`Zeller et al.
`Radke
`Shuen
`Ruszczyk et al.
`Kagan et al.
`Osawa
`Eng et al.
`McFarland et al.
`Pacheco et al.
`Bauchot et al.
`Sharony
`Semaan
`Lopez et al.
`Paneth et al.
`Mahany
`Ward et al.
`Boer et al.
`Ayanoglu
`Nakagawa et al.
`Kondo
`Woolley et al.
`Malcolm et al.
`Anderson et al.
`Hulyalkar et al.
`Bar-On et al.
`Mazzola et al.
`Saito et al.
`Busche
`Nagaraj et al.
`Hill et al.
`Lee
`Ayanoglu et al.
`McKay et al.
`Kang et al.
`Klein
`Bertin et al.
`Davis
`Cadd
`Kruys
`Raatikainen et al.
`Schrader et al.
`Acharya et al.
`Chander et al.
`Simmons
`Mayor et al.
`Toh
`Boer et al.
`Haugliet al.
`Gilbert et al.
`Haartsen
`Irvin
`Arimilli et al.
`Ridgeway
`Brownrigg et al.
`Stracke, Jr.
`Chuang et al.
`Kwon
`Cudak et al.
`
`US 7,796,573 B2
`Page 2
`
`5, 2000 Stevens
`6,064,626 A
`5/2000 Kamerman et al.
`6,067,291 A
`5, 2000 Beach
`6,067,297 A
`6/2000 Kikinis
`6,078,566 A
`7/2000 Eastmond et al.
`6,088,337 A
`8/2000 Jackson et al.
`6,097,704 A
`8, 2000 Robert et al.
`6,104,712 A
`8/2000 Agrawal et al.
`6,108,316 A
`8, 2000 Chambers et al.
`6,108,738 A
`9/2000 Chuprunet al.
`6,115,580 A
`9, 2000 Nannetti et al.
`6,122,690 A
`6,130,881 A 10/2000 Stiller et al.
`6,132,306 A 10/2000 Trompower
`6,163,699 A 12/2000 Naor et al.
`6,178,337 B1
`1/2001 Spartz et al.
`6, 192,053 B1
`2/2001 Angelico et al.
`6,192.230 B1
`2/2001 Van Bokhorst et al.
`6,208,870 B1
`3/2001 Lorello et al.
`6,222,463 B1
`4/2001 Rai
`6,223,240 B1
`4/2001 Odenwald et al.
`6,240,294 B1
`5, 2001 Hamilton et al.
`6,246,875 B1
`6/2001 SeaZholtz et al.
`6,249,516 B1
`6/2001 Brownrigg et al.
`6,275,707 B1
`8, 2001 Reed et al.
`6,285,892 B1
`9/2001 Hulyalkar
`6,304,556 B1
`10/2001 Haas
`6,327,300 B1
`12/2001 Souissi et al.
`6,349,091 B1
`2, 2002 Li
`6,349,210 B1
`2, 2002 Li
`6,359,872 B1
`3/2002 Mahany et al.
`6,404,756 B1* 6/2002 Whitehill et al. ............ 370,338
`6,807,165 B2 * 10/2004 Belcea ....................... 370,347
`6,868,075 B1
`3/2005 Narvinger
`6,873,839 B2
`3/2005 Stanforth
`6,904,275 B2
`6/2005 Stanforth
`7,099.296 B2 * 8/2006 Belcea ....................... 370,338
`7,151,769 B2 12/2006 Stanforth
`7,266,104 B2 * 9/2007 Belcea ....................... 370,338
`2001/0053699 A1 12/2001 McCrady et al.
`2003, OO87603 A1
`5/2003 Li et al.
`2005.0185627 A1
`8/2005 Bolgiano et al.
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`
`O513841
`O627827
`O924890
`96.08884
`9724005
`9839.936
`99.12302
`OO34932
`O110154
`O13377O
`O135567
`O 137481
`O 137482
`O 137483
`O235253
`
`11, 1992
`12/1994
`6, 1999
`3, 1996
`7/1997
`9, 1998
`3, 1999
`6, 2000
`2, 2001
`5, 2001
`5, 2001
`5, 2001
`5, 2001
`5, 2001
`5, 2002
`
`OTHER PUBLICATIONS
`Elliott, Chipetal, Self-Organizing, Self-Healing Wireless Networks,
`Aerospace Conference Proceedings, Mar. 18-25, 2000, vol. 1, IEEE,
`2000, pp. 149-156.
`Garcia-Luna-Aceves, J.J. et al. Reversing the Collision-Avoidance
`Handshake in Wireless Networks, Mobicom, Seattle, Washington,
`1999, 12 pages.
`Garcia-Luna-Aceves, J.J. et al. Transmission-Efficient Routing in
`Wireless Networks. Using Link-State Information, Mobile Networks
`and Applications, vol. 6, No. 3, Jun. 2001, pp. 223-238.
`Garcia-Luna-Aceves, J.J. et al. The Core-Assisted Mesh Protocol,
`IEEE Journal on Selected Areas in Communications, vol. 17, No. 8,
`Aug. 1999, 18 pages.
`
`IPR2019-01116
`2
`
`
`
`US 7,796,573 B2
`Page 3
`
`Kamerman, AD et al. Net Throughput with IEEE 802.11 Wireless
`LANs, Wireless Communications and Networking Conference
`(WCNC), Sep. 23-28, 2000, Chicago, Illinois, vol. 2, IEEE, 2000, pp.
`747-752.
`McChesney, J.R. et al. Optimization of an Adaptive Link Control
`Protocol for Multimedia Packet Radio Networks, Military Commu
`nications Conference Proceedings (MILCOM), Oct. 31-Nov. 3,
`1999, Atlantic City, NJ, IEEE, 1999, vol. 1, pp. 261-265.
`North, Richard et al. Wireless Networked Radios: Comparison of
`Military, Commercial, and R&D Protocols, 2nd Annual UCSD Con
`ference on Wireless Communications, San Diego, Feb. 28-Mar. 3,
`1999, 8 pages.
`Ramanathan, Ram et al. Topology Control of Multihop Wireless
`Networks. Using Transmit Power Adjustment, INFOCOM Mar.
`26-30, 2000, IEEE vol. 2, pp. 404-413.
`Ramanathan, Rametal, Hierarchically-Organized, Multihop Mobile
`Wireless Networks for Quality of Service Support, Mobile Networks
`and Applications, vol. 3, Issue 1, Jun. 1998, pp. 101-119.
`Valko, Andras G., Cellular IP: A New Approach to Internet Host
`Mobility, ACM Computer Communication Review, Jul. 2000, 16
`pageS.
`Peterson, Benjamin B. et al. Spread Spectrum Indoor Geolocation,
`Navigation: Journal of the Institute of Navigation, vol. 45, No. 2,
`Summer 1998, Aug. 1998, 8 pages.
`Wong et al. A Pattern Recognition System for Handoff Algorithms,
`IEEE Journal on Selected Areas in Communications, vol. 18, No. 7,
`Jul. 2000, 14 pages.
`
`Young, C. David, USAP: A Unifying Dynamic Distributed
`Multichannel TDMA Slot Assignment Protocol, MILCOM, Oct.
`21-24, 1996, IEEE vol. 1, 1996, pp. 235-239.
`Zhenyu Tang etal, Collision-Avoidance Transmission Scheduling for
`Ad-Hoc Networks, IEEE International Conference on Communica
`tions (ICC), Jun. 18-22, 2000, IEEE vol. 3, 2000, pp. 1788-1794.
`Wong etal, Soft handoffs in CDMA Mobile Systems, IEEE Personal
`Communications, Dec. 1997, 14 pages.
`USPTO, Office Action, Non-Final Rejection, May 17, 2005, appli
`cation No. 09846434, 18 pages.
`USPTO, Office Action, Final Rejection, Oct. 27, 2005, U.S. Appl.
`No. 09/846,434, 10 pages.
`Royer, Elizabeth M. etal. A review of Current Routing Protocols for
`Ad Hoc Mobile Wireless Networks, IEEE Personal Communica
`tions, Apr. 1999, 10 pages.
`Broch, Josh et al. The Dynamic Source Routing Protocol for Mobile
`Ad Hoc Networks, IETF MANET Working Group, Dec. 8, 1998, 52
`pageS.
`Perkins, Charles E., Ad hoc On-Demand Distance Vector (AODV)
`Routing, Mobile Ad Hoc Networking Group, Mar. 2, 2001, 27 pages.
`Jacquet, Philippe etal, Optimized Link State Routing Protocol, IETF
`MANET Working Group, Mar. 2, 2001, 29 pages.
`Johnson, David B. et al. The Dynamic Source Routing Protocol for
`Mobile Ad Hoc Networks, IETF MANET Working Group, Mar. 2,
`2001, 62 pages.
`Steenstrup, Martha E., Dynamic Multipoint Virtual Circuits for Mul
`timedia Traffic in Multihop Mobile Wireless Networks, BBN Tech
`nologies, Wireless Communications and Networking Conference,
`IEEE, 1999, pp. 1018-1022.
`* cited by examiner
`
`IPR2019-01116
`3
`
`
`
`U.S. Patent
`
`Sep. 14, 2010
`
`Sheet 1 of 6
`
`US 7.796,573 B2
`
`APPLICATIONS
`
`LOGICALLINK CONTROL (LLC)
`
`14
`
`
`
`
`
`MEDIUMACCESS CONTROL (MAC)
`
`12
`
`PHYSICALACCESSLAYER (PAL)
`
`10
`
`FIG. I.
`
`
`
`18- TIME
`SLOT
`
`LAST TIME
`SLOT
`
`INTER
`FRAME -20
`G
`
`FIG. 2
`
`IPR2019-01116
`4
`
`
`
`U.S. Patent
`
`Sep. 14, 2010
`
`Sheet 2 of 6
`
`US 7.796,573 B2
`
`GATEWAY
`
`AT1
`
`FIG. 3
`
`
`
`GATEWAY - 22
`
`AT1
`
`FIG. 4
`
`IPR2019-01116
`5
`
`
`
`U.S. Patent
`U.S. Patent
`
`Sep. 14, 2010
`Sep. 14, 2010
`
`Sheet 3 of 6
`Sheet 3 of 6
`
`US 7.796,573 B2
`US 7,796,573 B2
`
`
`
`GATEWAY
`
`GATEWAY
`
`FIG. 5
`
`ATH RTS !
`
`! RTS !
`
`|
`
`!
`
`|
`
`NCTS
`ATx,Ft+++
`
`ATI2 |
`
`!
`
`1 CTS 1
`
`1 CTS 1 RTS 1
`
`FIG. 6
`
`IPR2019-01116
`6
`
`IPR2019-01116
`6
`
`
`
`U.S. Patent
`
`Sep. 14, 2010
`
`Sheet 4 of 6
`
`US 7.796,573 B2
`
`
`
`GATEWAY
`
`AT1
`
`AT7
`
`FIG. 7
`
`AT12
`
`AT11
`
`AT13
`
`FIG. 8
`
`IPR2019-01116
`7
`
`
`
`U.S. Patent
`
`Sep. 14, 2010
`
`Sheet 5 of 6
`
`US 7.796,573 B2
`
`AT11 O AT13
`
`FIG. 9
`
`AT12
`
`AT11
`
`AT13
`
`FIG. 10
`
`IPR2019-01116
`8
`
`
`
`U.S. Patent
`
`Sep. 14, 2010
`
`Sheet 6 of 6
`
`US 7.796,573 B2
`
`AT12
`
`AT11
`
`AT13
`
`FIG. I. I
`
`AT11
`
`AT13
`
`FIG. I2
`
`IPR2019-01116
`9
`
`
`
`US 7,796,573 B2
`
`1.
`TERMINAL OPERATING WITHIN AN
`AD-HOC, PEER-TO-PEER RADIO NETWORK
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This is a continuation of a prior U.S. patent application Ser.
`No. 09/846,434, filed May 2, 2001 by inventor John M. Bel
`cea, entitled “Time Division Protocol For An Ad-Hoc, Peer
`To-Peer Radio Network Having Coordinating Channel
`Access To Shared Parallel Data Channels With Separate Res
`ervation Channel,” which is a continuation of a prior U.S.
`patent application Ser. No. 09/815,157, filed Mar. 22, 2001 by
`inventor John M. Belcea, now granted U.S. Pat. No. 6,807,
`165, granted Oct. 19, 2004, entitled “Time Division Protocol
`For An Ad-Hoc, Peer-To-Peer Radio Network Having Coor
`dinating Channel Access To Shared Parallel Data Channels
`With Separate Reservation Channel.” each application
`assigned to MeshNetworks, Inc. the disclosure of which prior
`applications are hereby incorporated by reference, verbatim
`and with the same effect as though they were fully and com
`pletely set forth herein.
`Additionally, this application claims priority benefit and is
`related to U.S. Provisional patent application 60/246,833,
`filed on Nov. 8, 2000, the disclosure of which is hereby
`incorporated by reference, verbatim and with the same effect
`as though it were fully and completely set forth herein.
`
`10
`
`15
`
`25
`
`BACKGROUND OF THE INVENTION
`
`2
`information as to which time slot is to be used being included
`in the messaging transmitted by the reservation channel. Such
`a format not only provides collision-free transmission, but
`also allows for Quality-of-Service (QOS) for different types
`of Class-of-Service (CoS). Thus, not only may voice and
`Video be transmitted, besides data, but Voice and data trans
`mission may be prioritized, so that when competing calls vie
`for a data channel, the delay-dependent Voice or video trans
`missions will take precedence. This prioritization is accom
`plished by assigning prioritized calls for transmission in ear
`lier time slots of a time frame.
`The network system disclosed in U.S. Pat. No. 6,404,756
`ensures that every node or terminal of a service set of termi
`nals has the most information regarding all of other terminals
`of that service set, so that the choice of data channel to be
`used, any required delay is transmitting the call, information
`on power level, and the like, are checked and updated by each
`terminal by a practically continuous monitoring of the reser
`Vation channel.
`As explained above, the system disclosed in U.S. Pat. No.
`6,404,756 utilizes protocol that provides collision-free chan
`nel access, which also emphasizes improving geographic
`reuse of the frequency spectrum.
`In U.S. Pat. No. 5,943,322, Mayer, et al., which patent is
`incorporated by reference herein, the radio system thereof is
`for use in battlefield conditions. The ad-hoc, peer-to-peer
`radio system of this patent does not have, nor require, a base
`station, as conventional cellular systems, personal communi
`cations system (PCC), and the like, require; instead, each
`radio terminal forming part of the ad-hoc, peer-to-peer radio
`system may alternatively serve as a base station, in addition to
`being an ordinary link terminal of the radio system, whereby,
`if one Such terminal serving as a base station should for some
`reason become inoperative, another terminal may take over
`and serve as the base station. In this patent, personal Voice
`communications is based on a time division duplex (TDD)
`technique in a code division multiple access (CDMA) system,
`is operated without a fixed base station, and is provided with
`simultaneous transmission of a communications channel and
`a control channel, each spread by different PN codes. The PN
`code facilitates restricting communications on the network to
`a particular voice-conversation mode and between identified
`radios. Transmissions are performed in a time division duplex
`manner in 62.5 milliseconds slots. One of the radios initiates
`transmission and maintains power control and time synchro
`nization normally done by a base station. A network control
`station can Voluntarily or by command transfer control of the
`network to any of the other radios on the network. Colliding
`transmissions from more than one radio require the radios to
`retry transmitting until one of the radios transmits in an earlier
`time slot. Conversational mode capability is provided by
`equipping the radio receivers with despreaders in parallel for
`permitting a receiving radio to separately despread the simul
`taneously transmitted signals all other radios on the network
`and responding to each radio transmission individually.
`Simultaneous voice and data communications can be accom
`plished by equipping the receivers with despreaders for dis
`criminating Voice and data information signals spread by
`different PN codes.
`In commonly-owned U.S. Pat. No. 6,873,839, issued Mar.
`29, 2005, entitled Prioritized Routing For An Ad-Hoc, Peer
`To-Peer Mobile Radio Access System, which application is
`incorporated by reference herein, there is disclosed an ad
`hoc, peer-to-peer radio system for use as a stand-alone system
`that is also connected to a cellular network and/or PSTN. The
`ad-hoc mobile radio networking system thereof is capable of
`receiving and transmitting Voice, data and video calls through
`
`30
`
`35
`
`40
`
`The present invention is directed to a terminal operating
`within an ad-hoc, peer-to-peer radio network system, the
`network having coordinating channel access to shared paral
`lel data channels via a separate reservation channel.
`The network system having coordinating channel access to
`shared parallel data channels via a separate reservation chan
`nel in U.S. Pat. No. 6,404,756 is directed to a network system,
`Such as radio network, where each node, or radio terminal, of
`the network is capable of serving as a node or hop of a routing
`path of a call from another, or to another radio terminal. In that
`system, communication between nodes or radio terminals is
`achieved using Carrier Sense Multiple Access with Collision
`Avoidance (CSMA/CA) protocol with the addition of mul
`tiple parallel data channels serviced by one reservation chan
`nel. By dedicating a separate reservation channel for the
`45
`multiple parallel data channels, collision-free access by all of
`the competing nodes or terminals of the service group of the
`network is greatly reduced.
`Communications between terminals or nodes is set up by
`information exchanged on the separate reservation channel,
`which information includes all of the call set-up information
`Such as data channel desired to be used for transferring Voice,
`video or data, the desired power level of at least initial trans
`mission, messaging Such as Request-to-Send (RTS), Clear
`to-Send (CTS), Not-Clear-to-Send (NCLS), Acknowledg
`ment (ACK) for indicating reception of the transmitted call,
`Non-Acknowledgment (NACK) for indicating improper
`reception of the call, etc. In this system, in order to further
`ensure fast, adequate and collision-free transmission and
`reception, besides a primary modem typically provided with
`the transceiver of each node or terminal, a secondary modem
`is also provided which is dedicated to the reservation channel
`when the primary modem of the transceiver is occupied, Such
`as when sending out data on a data channel. This system also
`provides for collision free transmission and reception
`between nodes or terminals by transmitting the reservation
`and data channels in time slots of time frames, with the
`
`55
`
`50
`
`60
`
`65
`
`IPR2019-01116
`10
`
`
`
`US 7,796,573 B2
`
`10
`
`15
`
`25
`
`30
`
`35
`
`3
`any number of different types of telecommunication net
`works, such as the PSTN, the Internet, and the like, besides
`the cellular and next-generation cellular networks.
`Past research has shown that conventional Carrier Sense
`Multiple Access (CSMA) algorithms experience diminishing
`returns when networks approach their ultimate capacity. The
`vast majority of current research centers on channel access
`algorithms that provide transmission capacity over a single
`shared medium. An example of this is the IEEE 802.11 wire
`less standard which employs a Carrier Sense Multiple
`Access/Collision Avoidance (CSMA/CA) algorithm. All
`users within a Basic Service Set (BSS) share a common
`channel resource.
`The ad-hoc, peer-to-peer radio system of the present inven
`tion is based on a transport-mechanism using a time division
`duplex (TDD) technique in a code division multiple access
`(CDMA) system. Time Division Duplex (TDD) is a way of
`maximizing the bits/hz/km2. Such a system not only may be
`used for providing commercial Voice, but is also quite Suited
`to both transmission and reception of data and video services.
`Time Division Duplex (TDD) systems are typically used for
`packet data systems, since they make much more efficient use
`of the available bandwidth, in order to deliver a much higher
`effective data rate to the end user. TDD is typically used in
`fixed wired solutions or point-to-point wireless systems
`because it has its own spectrum limitations. TDD Systems,
`however, have not hitherto been deployed for voice systems.
`Unlike the personal communication radio system of U.S.
`Pat. No. 5,943,322, Mayer, et al., the Time-Division Protocol
`(TDP) of the present invention does not care about the
`modem-type of access to radio spectrum, and is designed to
`work with or without a base station orgateway, since modem
`functionality is not part of the TDP of the present invention.
`The protocol of the present invention uses one control/con
`figuration channel and three or more data channels, where
`communication between radio terminals is planned for pre
`40
`venting interference. Time synchronization is independent of
`the communication, whereby no collisions among terminals
`are possible for configuration data, excepting in the last time
`slot, and no collisions are possible in the data channels, as
`described above. The protocol of the present invention may
`45
`transmit data and video, in addition to voice, since each is just
`another class of data.
`The system of the present invention is much more complex
`due to multiple, parallel data channels that are coordinated by
`a single reservation channel. In this system, a combination of
`50
`CSMA/CA, TDMA (time division multiple access), FDMA
`(frequency division multiple access), and CDMA (code divi
`sion multiple access) is used within the channel access algo
`rithm. The transceiver used in the system employs two
`modems to solve the channel reliability issues with multiple
`channel designs, as disclosed in the above-described U.S. Pat.
`No. 6,404,756. Specifically, the system dedicates a receive
`only modem for gathering channel usage information on the
`reservation channel. The reservation channel operates a
`hybrid CSMA/CA and TDMA algorithm. The remainder of
`the protocol uses FDMA for the multiple data channels, and
`CDMA for multiple users on the same data channel. Refer
`ence is also had to copending, commonly-owned U.S. Pat.
`No. 6,873,839, issued Mar. 29, 2005, entitled “Prioritized
`Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access
`System”, which is incorporated by reference herein, in which
`
`55
`
`60
`
`65
`
`4
`there is disclosed an example of routing table messaging
`which may be used in the present invention.
`
`SUMMARY OF THE INVENTION
`
`It is the primary objective of the present invention to pro
`vide an ad-hoc radio system as part of an overall, larger
`cellular network, and/or as a stand-alone, independent sys
`tem, in order to provide commercial use for providing Voice,
`data and video communications between radio terminals of
`the radio system of the invention and between equipment
`outside the system of the invention.
`It is also a primary objective of the present invention to
`provide an overall protocol for ad-hoc radio system not uti
`lizing a fixed base station, whereby a connection path by
`which a call is made takes into consideration the power loss
`associated therewith, in order to determine the least-energy
`routing of a call for the particular service type being trans
`mitted. Such as Voice, data or video.
`The protocol of the present invention is based on a time
`division duplex (TDD) plus code-division multiple access
`(CDMA) burst packet technology used within the channel
`access algorithm of the system of the present invention. This
`provides the improvements in throughput and reliability that
`are required to deliver high quality Voice, video and data The
`reservation channel implements a time division multiple
`access algorithm with dynamic slot allocation. In a distrib
`uted manner, nodes determine geographic reuse of slots based
`on channel quality. Signal quality calculations are used to
`determine the likelihood of a slot reuse causing destructive
`interference within a node's neighborhood. Requests for slot
`usage are compared with the known traffic pattern and
`accepted or rejected by nodes within RF signal range based on
`the signal quality calculations. Additionally, the algorithm of
`the present invention readily provides for the mobility of
`nodes between geographic areas through the use of a special
`slot that is reserved for nodes without reservations. Nomadic
`nodes use this slot to locate a permanent slot to claim for their
`use. Once claimed, the collision free properties can be
`enforced to improve the reliability and throughput of mes
`sages generated by this node. This results in a maximal use of
`the spectrum within a geographic area.
`The system of the present invention utilizes a method and
`algorithm which, in the preferred embodiment, is intended for
`an ad-hoc network system called 'ArachNet, and is based on
`least-energy routing of calls from between network radio
`terminals. In simple terms, the major component of the rout
`ing decision is to choose to route to the destination that uses
`the least amount of energy over the complete route. The major
`reason for this is that at least-energy routing minimizes the
`radiated RE energy, in order to reduce interference between
`terminals. A consequence of this is that it creates the most
`efficient use of the power supply of the terminals. Routing
`tables based on this least energy routing a developed by the
`system of the invention, and stored at one or more radio
`terminals, which routing tables are transmitted and stored by
`other terminals forming part of the link by which a call is
`connected. An example of Such a routing table is disclosed in
`copending, commonly-owned U.S. Pat. No. 6,873,839,
`issued Mar. 29, 2005, entitled “Prioritized-Routing for an
`Ad-Hoc, Peer-to-Peer, Mobile Radio Access System', which
`is incorporated by reference herein.
`Variants or equivalents of the system of the invention are
`possible. There are a number of variants of this approach that
`would provide acceptable performance. These variants
`include tuning of each of the four access schemes: CSMA/
`CA, TDMA, FDMA, and CDMA. For example, the width of
`
`IPR2019-01116
`11
`
`
`
`5
`the time slots may be adjusted based on the specific network
`over which the protocol is executing. Performance of the
`network is very dependent on the number of parallel data
`channels which can be used. A balance exists between the
`capacity of the reservation channel to make data reservations
`and the capacity of the data channels to provide service. This
`balance is dependent on the underlying capabilities of the
`dedicated, reservations-channel modem that implements the
`protocol. The performance of the protocol is also dependent
`on the inclusion of the channel quality extracted from the
`channel. Accurate estimates of the signal strength translate
`into improvements in geographic reuse, which can be
`obtained by aggressive power control schemes. Another
`example is the use of advancements in the codes used within
`the CDMA portion. Codes which improve the cross-correla
`tion performance of terminals which share a common data
`channel improve the throughput and reliability of the overall
`network performance.
`The adaptive power algorithm of system of the present
`invention leads to improvements in the determination of RF
`radius for a given data rate. Increasing the data rate and
`reducing power promotes geographic reuse. Any loss in com
`munication is easily compensated by our ad-hoc routing algo
`rithms.
`The channel access approach of the invention is equally
`applicable for Subnets which include or do not include gate
`ways. In the gateway approach, time is coordinated within the
`ad hoc environment by the gateway. In the non-gateway
`approach, a distributed time algorithm provides acceptable
`performance. In general, gateways permit the creation of
`larger networks such as MAN's and WAN's.
`While the protocol method of the present invention is dis
`closed with regard to an ad-hoc, peer-to-peer radio system,
`the protocol is equally applicable to any wireless LAN, wire
`line network, and the like, to which the method and system
`disclosed in U.S. Pat. No. 6,404,756 may apply.
`
`10
`
`15
`
`25
`
`30
`
`35
`
`BRIEF DESCRIPTION OF THE INVENTION
`
`The present invention will be more readily understood with
`reference to the accompanying drawings, wherein:
`FIG. 1 is a logical flow chart showing the software structure
`of the protocol of the system of the present invention;
`FIG. 2 is depiction of the time-division of the TDD proto
`col (AP) of the present invention showing the time frames
`thereof with separated time slots;
`FIG.3 is a depiction of the many terminals AT connected to
`a particular gateway of the system of the present invention
`connecting the terminals to an exterior network, with one
`particular AT entering the service domain thereof and the
`connection path thereof;
`FIG. 4 is a depiction similar to FIG. 3, but showing the
`particular AT moving away from the gateway and other ATs,
`whereby disconnection or reconnection must be carried out;
`FIG. 5 is a depiction similar to FIGS. 3 and 4, showing a
`gateway connecting the system to outside networks, which
`connection path does not require very high speed, and where
`the total energy for passing data along the route is minimized;
`FIG. 6 is a depiction of the time frames (TFs) with time
`slots (TS’s) of the protocol of the system of the present
`invention required for performing one hop between terminals
`(ATs) for a permanent link, in order to assure proper com
`munication;
`FIG. 7 is a depiction similar to FIGS. 3-5, but showing the
`connecting route between two AT’s of a local link, in order to
`control power requirements of the ATs;
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,796,573 B2
`
`6
`FIG. 8 is a graphical depiction showing an AT approaching
`a group of ATS and the closed triangular connection therebe
`tween;
`FIG. 9 is a graphical depiction similar to FIG. 8 showing
`the open triangular connection therebetween if the AT’s expe
`rience power reduction, whereby connection is preserved via
`the intermediate AT with ensuing reduction in energy loss;
`FIG. 10 is a graphical depiction similar to FIGS. 8 and 9
`showing the perturbed power profile of the ATs and the
`connection therebetween after the lowering of the power of
`all of the ATs;
`FIG. 11 is a graphical depiction similar to FIG. 10 and
`showing the closed triangular connection therebetween after
`one time frame after power perturbation; and
`FIG. 12 is a graphical depiction similar to FIG. 11 and
`showing the open triangular connection therebetween after
`two time frame after power perturbation with the ensuing
`steadyState, energy-saving path-connection between the
`ATS.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`For purposes of a better understanding of the description,
`the following definitions and abbreviations are hereby given:
`Definitions
`“Service Area of a Terminal
`The geographical area where the transmission of a terminal
`can be received at a level higher than environment noise.
`“Receive Set of a Terminal
`The set of terminals located within the service area
`“Transmit Set of a Terminal
`The set of terminals containing one particular terminal within
`their service areas.
`“Service Set of a Terminal
`The set of terminals that can receive the transmission of one
`particular terminal and can be received at that terminal (the
`intersection between the receive set and the transmit set).
`“Simple Connection
`An abstract notion associated to two terminals that can com
`municate one with another.
`“Connecting Path’
`A set of adjacent Simple Connections.
`“Service Group of a Terminal”
`The largest set of terminals containing at least one Connect
`ing Path between the host terminal and any other terminal
`of the set.
`“Set of Active Time Slots’
`All time slots used by t