`LarSSOn et al.
`
`USOO6704293B1
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,704,293 B1
`Mar. 9, 2004
`
`(54) BROADCAST AS A TRIGGERING
`MECHANISM FOR ROUTE DISCOVERY IN
`AD-HOC NETWORKS
`
`(75) Inventors: Tony Larsson, Stockholm (SE); Johan
`Rune, Lidingö (SE); Johan Sörensen,
`Eslöv (SE)
`(73) Assignee: Telefonaktiebolaget LM Ericsson
`(publ), Stockholm (SE)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/455,460
`(22) Filed:
`Dec. 6, 1999
`(51) Int. Cl. ................................................ H04L 12/28
`(52) U.S. Cl. ........................ 370/255; 370/351; 370/400
`(58) Field of Search ................................. 370/351, 400,
`370/401, 328, 254, 255
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,051984. A 9/1991 Mostafa et al.
`5,056,085. A 10/1991 Vu
`5,065,399 A 11/1991 Hasegawa et al.
`5,173,689 A 12/1992 Kusano
`5,235.599 A 8/1993 Nishimura et al.
`5,719,861 A 2/1998 Okanoue
`5,740,366 A 4/1998 Mahany et al.
`5,748,611 A 5/1998 Allen et al.
`5,987,011 A 11/1999 Toh ............................ 370/331
`6,304,556 B1 10/2001 Haas .......................... 370/254
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`WO
`WO
`
`O599764
`O883265
`O913965
`9911025
`992.3799
`
`6/1994
`12/1998
`5/1999
`3/1999
`5/1999
`
`OTHER PUBLICATIONS
`W. Richard Stevens, “TCP/IP Illustrated, vol. 1, The Proto
`cols,” 1994, Addison-Wesley, pp. 53-64.*
`Pravin Bhagwat and Adrian Segall, “A Routing Vector
`Method (RVM) for Routing in Bluetooth Scatternets," IEEE
`1999, pp. 375–379.*
`
`Albrecht, M.,et al., “IPServices over Bluetooth: Leading the
`Way to a New Mobility”, Proceedings of the Conference on
`Local Computer Networks, Oct. 1999.
`Tode, H., et al., “A Routing Method Using a Tunable Cost
`Function to Obtain Required Communication Quality and
`Performance', Electronics and Communications in Japan,
`Part 1. Vol, 81, No. 5, 1998.
`Haartsen, J., “Bluetooth-The Universal Radio Interface for
`Ad Hoc, Wireless Connectivity”, Ericsson Review No. 3
`(1998), pp. 110–117.
`Takagi, Hideaki, “Queuing Analysis of Polling Models”,
`ACM Computing Surveys, vol. 20, No. 1, Mar. 1988.
`Johansson, Per, et al., “Short Range Radio Based Ad-hoc
`Networking: Performance and Properties”, Proceedings of
`International Conference on Communications (ICC 99),
`Jun. 6-10, 1999.
`“Specification of the Bluetooth System”, Bluetooth SIG,
`vol. 10, pp. 35–40 and 121-122; Jul. 24, 1999.
`European Search Report Issued Jul. 28, 2000.
`
`* cited by examiner
`
`Primary Examiner-Chau Nguyen
`Assistant Examiner Keith M. George
`(74) Attorney, Agent, or Firm-Burns, Doane, Swecker &
`Mathis, LLP
`(57)
`
`ABSTRACT
`
`A method and/or an apparatus which places a broadcast
`message which the Source expects a reply message in a
`broadcast message for route discovery. The combined mes
`Sage is broadcast throughout the ad-hoc network. When the
`combined broadcast message is received at the destination
`node, the destination node generates a response message
`including a reply message to the broadcast message that the
`Source node expects a reply. The response message is sent
`back to the Source node over the route which the combined
`broadcast message traveled to the destination node.
`
`36 Claims, 11 Drawing Sheets
`
`
`
`telli; fell K---) "life
`Appiano
`AAPACAF
`
`TAF
`
`Fialap
`
`Alpi AAE?
`task-tae
`lip
`120AP K
`) lacAP
`
`f
`Adaptaifaat
`
`SA
`
`lAP
`
`s
`
`Affif, iff
`
`Alientifia
`
`Page 1 of 21
`
`
`
`U.S. Patent
`
`Mar. 9, 2004
`
`Sheet 1 of 11
`
`US 6,704,293 B1
`
`Afg. f.
`Prior Art
`
`02
`
`0.
`
`Afg. 2
`Prior Art
`
`
`
`208
`
`
`
`n
`
`1
`
`V
`- - - - -
`A/(A) -1
`
`Aft?/Aff
`
`Page 2 of 21
`
`
`
`US. Patent
`
`Mar. 9, 2004
`
`Sheet 2 0f 11
`
`US 6,704,293 B1
`
`Hg 40
`Prior Art
`
`401
`
`402
`
`ll/M lfl’fl I’M/0001
`0,? APPZ MAI/01V
`
`
`
`MP H MP
`
`04M! I”
`
`451
`
`452
`
`34559.4” _ 5.4559110
`
`19102“fo/I’ ”AW /
`
`fill/[700M WI] 2
`
`Page 3 of21
`
`Page 3 of 21
`
`
`
`US. Patent
`
`Mar. 9, 2004
`
`Sheet 3 0f 11
`
`US 6,704,293 B1
`
`Flg. 5
`Prior Art
`
`505
`
`50006? 000;” 0flfilff5‘ #555105
`
`0004003457
`
`5670 000100157’ ”MEI"
`m Alf/00000 mi:
`
`5'“
`
`52°
`
`
`
`
`00/0157 00 000100457?
`
`MIMI
`
`
`
`/5
`
`’9'01/7[ figfig’mfl”
`
`
`
`m
`
`r5
`
`530
`
`50m; 0005 0001001575 ”oz/£57
`F0? 000/? IISSMF
`
`”70000)? 000! Fifi/V5
`000100157 #5516?
`
`
`
`
`
`”Ml/000 I00[
`
`
`14105407 00005930 0f00f5ff00
`
`
`000/51554052
`
`
`
`I0
`
`
`
`
`5700i 5000” 0001“ 100035
`M0 000400157 /0[If/f/[0
`
`
`
`05000100157 N005” F00 WW1r
`”£551” ['0 05/000019 I005
`
`535
`
`”-5
`
`555
`
`560
`
`
`otsr/mr/omoofi/
`
`
`
`,m
`
`”5
`
`515
`
`5:70 mm 70 MM
`SPEfl/F/[fl /// roar/M mu
`
`525
`
`0000 15.9.5140!
`
`545
`
`565
`
`55"” fig‘gfiéfl"
`
`570
`
`Bic/II 5.5mm 70
`oar/(mm WEI? If! fiat/rt"
`
`Page 4 of21
`
`Page 4 of 21
`
`
`
`US. Patent
`
`Mar. 9, 2004
`
`Sheet 4 0f 11
`
`US 6,704,293 B1
`
`Fly. 60
`
`602
`
`mm mm mm7:":
`5190106945f #5954”
`
`604
`
`
`
`
`005' 500/705 IMF
`[mom mm” m ”mam
`#5554652
`
`
`
`
`IE?
`
` Ifl
`
`
`
`SEID ”WWI” IfSS/M‘f
`70 All If/é'Ififl/f I005
`
`606
`
`608
`
`
`
`500m l/Mf mama/(5
`IMAM!” ”may“
`IERIESI MI III/T #3516?
`
`615
`
`Sfllffifif IMF ”010614.575 [[70fo
`MI #01171“ ”3516'!"
`
`IfoSf f0! MW? IESSMI
`”it'll/[0 fl If/é'l/MI I001"
`
`617
`
`620
`
`
`
`
`
`
`If/MIM Iflflf
`
`Al I540, PIML‘SSEI ”WI/£57 MI
`MW!" ”$5,465?
`
`
`
`
`I0
`
`m
`
`wrap 1mm
`
`625
`
`630
`
`670:?! ”MM I00!" AMIFSS
`III III/400,437 MEII/HEI
`
`635
`
`If/é‘IMI Iflflf 570,95 ffIPflIl/H’
`III/ff RAM 70 Sol/I65 IMF
`
`Page 5 of21
`
`Page 5 of 21
`
`
`
`US. Patent
`
`Mar. 9, 2004
`
`Sheet 5 0f 11
`
`US 6,704,293 B1
`
`305‘ #6512915le?
`MM ”10/6/4715" I00[ /5 0557/14/70!
`AWE?
`
`”-5
`
`P/é‘é‘l’fllfll [501/
`II My]? fifSPflle
`
`#1555452"
`
`642
`
`840
`
`I0
`
`w my”? ”a”; II #5554”
`
`I005 M71105? 40017595
`
`658
`
`5570 170075
`fifSPflISf ”[5546?
`
`645
`
`
`
`
`19551701061457 ”'00fo Ml? Mil/E
`1mm 70 mmm mm
`
`660
`
`r55
`
`501m; ME;
`
`865
`
`680
`
`6 85
`
`AN/VA/Y‘ mar/I
`mm mm
`
`356/! 5570/” 01/74
`ME? I!" MW?
`
`61.
`
`675
`
`F/y. 6b
`
`Aer/m; mm H
`llfffllfflllff mm
`
`
`
`
`
`#005 if”! 155165
`70 I517 IMF II
`ffl/‘W’lfl’ IflM/Z'
`
`Page 6 of21
`
`Page 6 of 21
`
`
`
`US. Patent
`
`Mar. 9, 2004
`
`Sheet 6 0f 11
`
`US 6,704,293 B1
`
`Fig. 70
`
`
`
`000005 0005 050501750 10/3
`0105 05.90107/00 00 0000 000100157 050105
`
`705
`
`0/00/0100 100, 0105 0500107/00, 00 0007’
`000100157 0555105 /0 011 0500557 500
`00075 000000507 000100107 0550105
`
`000100157 011 0500557 500
`00075 06000507 0500105
`
`
`
`710
`
`715
`
`
`
`
`717
`
`0500507 500 00075 0500105 0505/050 170005
`
`
`
`
`001/750/500000050fggfi05110510/
`0’”
`
`
`”55‘”
`0550 000055550?
`
`
`
`
`
`
`
`
`755
`
`00
`
`.S'7005 500005 0005 1000555
`100 000100107 /0507/5/50
`
`
`
`0005 070050 7511000107 00075
`0101’ 70 500005 0005
`
`5500 0/00/0100 0171 70 0/0050 [50515
`
`0005 050001001575 0505105
`
`
`
`
`
`Page 7 of21
`
`Page 7 of 21
`
`
`
`US. Patent
`
`Mar. 9, 2004
`
`Sheet 7 0f 11
`
`US 6,704,293 B1
`
`740
`
`
`I005 I'll/41' HIM/7T5 MPH? ”@
`
`
`
`
`745
`
`765
`
`Fifi/546‘! /I Ht
`MW!" IFS/WISE 135.4”
`
`750
`
`007/00,? 0007070 0000
`
`755
`
`Si” 041 000/? 0550005!
`0055400 0050 75100000,? 000/:r
`
`760
`
`766
`
`407/0070 0007;
`0/ 5000050001r
`
`r0:
`
`500000 00000
`
`765
`
`
`
`5!” 0/00/040000
`0m 00 00070001
`mar I” 5700:"
`Edi/ff f0 ”Hf/Ilf/fll
`
`407/0775 770075 0/
`76? mmvmuri 0001r
`
`It" Ml/ff 775
`
`
`
` I001" 5M” ”29.5345?
`
`In If.” IMF M’
`IEIMRM’)’ 7701/75
`
`IH'II SEW/’6'
`I”! 01/5?
`
`769
`
`Fig. 70
`
`Page 8 of21
`
`Page 8 of 21
`
`
`
`US. Patent
`
`Mar. 9, 2004
`
`Sheet 8 0f 11
`
`US 6,704,293 B1
`
`Hg 80
`
`500000 #005 05/159,473 MP,
`”If 0501 07/0! 00 0000 0001001457 ”[5546?
`
`705
`
`0/00”)!” 40/? ”If 0590107/00', 00 0000
`BR0140015713516? ll Ml 0500557" [’00
`
`00075 0/500”??? 000,400!” #6951405
`
`000100157011 ”001557 [0]?
`000}? 0/500VE/H’ ”£55240!
`
`710
`
`"5
`
`717
`
`0500557 F00 0001'! #055,405 FEM/I’M If I005
`
`0MP
`11mm
`
`’55
`
`725
`
`
`
`[Ml/[Sf F00
`0007')? 0500!??? [5540514105407
`
`0ffl P000550?
`
`w
`
`#005
`340 mmwum
`
`my”
`
`57005 500005 #00!" 1000055
`M0 000400157 Mill/”[0
`
`0005 570055 #1000107 000}?
`010! 70 50000!" I00£
`
`727
`
`730
`
`5500 #067010! 04/74 M 0/06??? If”?!
`
`732
`
`834
`
`”If FFf0ffEIl/lf0 1101/," 0f ”I!"
`
`Page 9 of21
`
`Page 9 of 21
`
`
`
`US. Patent
`
`Mar. 9, 2004
`
`Sheet 9 0f 11
`
`US 6,704,293 B1
`
`836
`
`IVE/TM! Mal/”MIMI 11/5? [Ill/#5
`04/74 M01 WWII? [AIMS
`
`
`
`
`
`r59
`839
`
`mm; mmrm mm
`IfMM/ZEmy;
`
`mama/I m
`mm RES/”MS! mm;
`
`75
`
`0
`
`”Ill/Ari Mflff ll Iflflf
`
`755
`
`5570 I'll ”WE ”5/00le
`#5516? WE? ffl/‘W’Mr Mflff
`
`760
`
`766
`
`4mm ff Mari
`M’ 500mm;
`
`r55
`
`50”” mg
`
`765
`
`
`
`mp mama/(£0
`mm ff mm 0
`mm 1/; ”mm m mama/1r: #00!
`mm m 57m
`Mflff f0 HEW/Ilf/M
`
`If” Wl/ff 775
`
`KIWI SEW/IT
`MM Wt)?
`
`769
`
` AWE SIMS IESSIFF
`
`70 If,” IMF ll
`[fl/’0’?!” mm
`
`Mg. 8b
`
`Page 10 of21
`
`Page 10 of 21
`
`
`
`US. Patent
`
`Mar. 9, 2004
`
`Sheet 10 0f 11
`
`US 6,704,293 B1
`
`Hg 90
`
`@
`
`sol/#051005 fiflffilffs A”,
`”If R550! ”/70! M 0:96P 19170100157 ”£55145?
`
`705
`
`H6375!” A”; ”If FfSfllW/fll, 0:? 0176',”
`”0.4061457 lfSSMf II Ill Ifflflfiffflfi
`
`Mflfi WSW/[If 19/70/0614.;I 1595,46?
`
`”01061451711 ”00fo I’M
`WWI WSW/[Ff ”[5546?
`
`710
`
`715
`
`717
`
`RIM/[Sf I‘M ”WE #551465 [Hf/Vii U [001‘
`
`MW
`”(5516?
`
`755
`
`725
`
`
`
`[Ml/[5f f0)?
`190(le MEMVHFI’ #55515? IMHW
`
`
`JEEI ”06695150?
`
`
`945
`M
`
`I00!
`K55301001573'
`
`#155516?
`
`570” 5001905 #00:? [WIPES
`MW 5070100457 lflflf/f/[I
`
`Wflf mm rrmmr mm
`316‘! m 500,901: Iflflf
`
`7 7
`2
`
`730
`
`934”II
`
`515W ”FF/316‘! 04/! f0 WEI/[I lfl’flé’
`
`732
`
`”If Pifflffffll/IM AIM/If 01‘ I715
`
`I
`
`Page 110f21
`
`Page 11 of 21
`
`
`
`US. Patent
`
`Mar. 9, 2004
`
`Sheet 11 0f 11
`
`US 6,704,293 B1
`
`
`
`936
`
`940
`
`f/leI 1,475?! A’fflf/I’ffl
`ӣ67546! 01/74
`
`
`
`
`
`
`film/[I 1 1/595
`Ila/6W? 17/1] 4 REPU'
`
`f0 PIN/MM 0AM
`
`MAT/HIM?
`
`r59
`942
`
`#66731” M’ Ill
`MW? [[5100le [EH/46'!
`
`T50
`
`[If/I’ll? WWI II 05/71/77” AWE
`
`755
`
`if” Ml Mil/T [75/0055
`15.95.46! W5? HIM/M” 1901/72"
`
`?60
`
`766
`
`Aer/V475WWI
`
`r5 -
`
`765
`
`55w Pix/mm
`mm W I’M/71M
`mm mm mm;
`[WI/2' f0 flffflllf/fll
`
`I” #0072:
`
`ifF/I SEW/[6‘
`0”! WM
`
`767
`
`759
`
`Aer/ml? [oz/rt ll
`mafia/m #005
`
`
`
`
`
`
`
`WM 55”! #55165
`['0 #5171005 /I
`
`MIMI!” [Ml/ff
`
`F[9 90
`
`Page 12 of21
`
`Page 12 of 21
`
`
`
`1
`BROADCAST AS A TRIGGERING
`MECHANISM FOR ROUTE DISCOVERY IN
`AD-HOC NETWORKS
`
`This application is related to: U.S. Pat. No. 6,535,498
`“Route Updating In Ad-Hoc Networks”; U.S. Provisional
`Application No. 60/168,742 “Route Discovery Based Pico
`net Forming”; U.S. patent application Ser. No. 09/454,758
`“Inter Piconet Scheduling”; and U.S. Pat. No. 6,480,505
`“Batched Fair Exhaustive Polling Scheduler”, all of which
`are herein expressly incorporated by reference.
`BACKGROUND
`The present invention relates to ad-hoc networks. More
`particularly, the present invention relates to routing in
`ad-hoc networkS.
`Conventional networking protocols are based on the char
`acteristics and/or features of fixed networks. In fixed
`networks, the network configuration typically does not
`change. Although nodes can be added and removed in fixed
`networks, the route traveled by data packets between two
`nodes typically does not change. The disadvantage is that
`fixed networks cannot be easily reconfigured to account for
`increases in data traffic, also called System loading.
`Accordingly, when System loading increases for one node,
`the Surrounding nodes are likely to experience increased
`delays in the transmission and reception of data.
`In contrast to fixed networks, ad-hoc networks are
`dynamic. An ad-hoc network is formed when a number of
`nodes decide to join together to form a network. Since nodes
`in ad-hoc networks operate as both hosts and routers, ad-hoc
`networks do not require the infrastructure required by fixed
`networks. Accordingly, ad-hoc networking protocols are
`based upon the assumption that nodes may not always be
`located at the same physical location.
`Bluetooth is an exemplary ad-hoc networking technology.
`Bluetooth is an open specification for wireleSS communica
`tion of both voice and data. It is based on a short-range,
`universal radio link, and it provides a mechanism to form
`Small ad-hoc groupings of connected devices, without a
`fixed network infrastructure, including Such devices as
`printers, PDAS, desktop computers, FAX machines,
`keyboards, joysticks, telephones or virtually any digital
`device. Bluetooth operates in the unlicenced 2.4 GHz
`Industrial-Scientific-Medical (ISM) band.
`FIG. 1 illustrates a Bluetooth piconet. A piconet is a
`collection of digital devices, Such as any of those mentioned
`above, connected using Bluetooth technology in an ad-hoc
`fashion. A piconet is initially formed with two connected
`devices, herein referred to as Bluetooth devices. A piconet
`can include up to eight Bluetooth devices. In each piconet,
`for example piconet 100, there exists one master Bluetooth
`unit and one or more slave Bluetooth units. In FIG. 1
`Bluetooth unit 101 is a master unit and unit 102 is a
`Bluetooth slave unit.
`According to Bluetooth technology a Slave unit can only
`communicate directly with a master unit. FIG. 2 illustrates
`a piconet with a master unit 201 and a plurality of slave units
`202-208 arranged in a star network topology. If slave unit
`202 wishes to communicate with slave unit 206, slave unit
`202 would have to transmit the information it wished to
`communicate to master unit 201. Master unit 201 would then
`transmits the information to slave unit 206.
`A Scatternet is formed by multiple independent and
`unsynchronized piconets. FIG. 3 illustrates an exemplary
`scatternet 300. In FIG. 3, piconet 1 includes a master node
`
`5
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,704,293 B1
`
`2
`303 and the slave nodes 301,302 and 304; piconet2 includes
`the master node 305 and the slave nodes 304,306, 307 and
`308; and piconet 3 includes the master node 309 and the
`slave nodes 308, 310 and 311. To implement a scatternet it
`is necessary to use nodes which are members of more than
`one piconet. Such nodes are herein referred to as forwarding
`nodes. If, for example, node 301 wishes to communicate
`with node 310, then nodes 304 and 308 might act as
`forwarding nodes by forwarding the connection between the
`two piconets and in particular between nodes 301 and 310.
`For example, node 301 transfers the information to the
`master node of piconet 1 node 303. Master node 303
`transmits the information to forwarding node 304. Forward
`ing node 304 then forwards the information to master node
`305, which in turn, transmits the information to forwarding
`node 308. Forwarding node 308 forwards the information to
`master node 309 which transmits the information to the
`destination node 310.
`FIG. 4a illustrates the protocol layers of two conventional
`Bluetooth units. AS indicated, both units 401 and 402
`includes a high level protocol or application 411. They also
`include a network layer 421, a data link layer including a
`logical link control and adaptation protocol (L2CAP) 441
`and link manager protocol (LMP), and the physical layer
`including a baseband component.
`In general, the protocols which govern the formation
`and/or updating of routes in an ad-hoc network may be
`classified as either proactive or reactive. Proactive routing
`protocols attempt to update and maintain routes between
`nodes, including routes which are not currently in use.
`Typically, proactive routing protocols react to network
`topology changes, even if there is no current traffic which is
`affected by the topology change. To update and maintain the
`routes between nodes in an ad-hoc network employing
`proactive routing, each node periodically transmits control
`information to other nodes in the network. However, this
`requires a large amount of Signaling, which consumes pre
`cious bandwidth and leads to network congestion. The
`network congestion, in turn, results in greater transmission
`delays for packets traveling through the network.
`In contrast to proactive routing protocols, reactive routing
`protocols establish routes only when there is an immediate
`need to transmit packets. Moreover, reactive routing proto
`cols only maintain information about routes which are
`currently being used for transmitting data packets.
`Accordingly, reactive protocols result in leSS network
`Signaling, and hence, leSS network congestion and less delay
`due to the congestion as compared to proactive routing
`protocols.
`FIG. 5 illustrates conventional routing techniques. In Step
`505 the source node generates a message. In step 510 the
`node determines whether the message is a broadcast mes
`Sage or a unicast message. If the message is a broadcast
`message, in accordance with the "Broadcast path out of
`decision step 510, then the source node broadcasts the
`packets to its neighbor nodes.
`If the message is a unicast message, in accordance with
`the “Unicast” path out of decision step 510, then it is
`determined whether the Source node knows a route to the
`destination node in accordance with step 520. If a route to
`the destination node is known, in accordance with the “Yes”
`path out of decision step 520, the source node will send the
`unicast message to the node specified in the Source node's
`routing table in accordance with step 525.
`If a route to the destination node is not known, in
`accordance with the “No” path out of decision step 520, then
`
`Page 13 of 21
`
`
`
`3
`the Source node broadcasts a request for route message in
`accordance with step 530. In step 535 a neighbor node
`receives the request for route message. In Step 540 the
`neighbor node determines whether it has already processed
`the request for route message. The neighbor node makes this
`determination based upon a Source node address and broad
`cast identifier in the request for route message. If the
`neighbor node has already processed the request for route
`message, in accordance with the “Yes” path out of decision
`step 540, the node will drop the message in accordance with
`step 545.
`If the node has not already processed the message, in
`accordance with the “No” path out of decision step 540, then
`the node Stores the Source node address and broadcast
`identifier. In step 555 the node rebroadcasts the request for
`route message to its neighbor nodes. In step 560 the node
`determines whether it is the destination node. If the node
`determines that it is not the destination node, in accordance
`with the “No” path out of decision step 560, then the node
`is done with its processing for this message. However, if the
`node is the destination node, in accordance with the “Yes”
`path out of decision step 560, the node will send a response
`back to the source node in accordance with step 565. In step
`570 the source node sends the unicast message to the
`destination node over the newly established route. In accor
`dance with reactive routing, the Source node will only
`request a new route when the actual route being used is
`broken.
`In conventional networks there are typically two types of
`broadcast messages. The first type of broadcast message are
`messages which the Source node Sends to Spread information
`to other nodes in the network. When this type of broadcast
`message is sent the Source does not expect to receive a reply
`message. The Second type of broadcast message are mes
`Sages which the Source node expects to receive a reply
`message from one or more network nodes.
`Since ad-hoc networks are dynamic, nodes may change
`their location in the network. When the node changes its
`location, the node may not have the same address as the node
`had at its prior location. In order to transmit data from a
`Source node to a destination node the Source node may first
`obtain its own network address, resolve the name of the
`destination, obtain the hardware address of the destination
`node and determine a route to the destination node.
`However, Since conventional ad-hoc routing protocols are
`based on the characteristics and/or features associated with
`fixed networks, the conventional ad-hoc routing protocols
`assume that the Source node and destination node hardware
`addresses are known.
`One exemplary networking protocol is Internet Protocol
`(IP). In IP there are several different broadcast messages that
`a Source node generates where the Source node expects a
`reply from one or more node(s) in the network. In IP three
`exemplary types of broadcast messages where the Source
`expects a reply are dynamic host configuration protocol
`(DHCP), name resolution and address resolution protocol.
`DHCP is concerned with dynamic allocation of IP addresses
`to nodes. Name resolution is used to obtain the IP address
`when the name of the node. ARP is used when the logical
`address of the node is known, e.g., the IP address, but the
`hardware address, e.g., the Ethernet address of the node is
`not known.
`Accordingly, in an ad-hoc network the Source node may
`have to perform a separate broadcast for DHCP, name
`resolution or ARP, and route discovery before the source
`node can begin to transmit data to the destination node.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,704,293 B1
`
`4
`These Separate broadcasts result in delay in Sending the
`information from the Source node to the destination node.
`Sending these separate broadcasts also adds to the load of
`the network.
`Accordingly, it would be desirable to minimize the num
`ber of broadcast messages required for Setting up a route
`from a Source node to a destination node when employing
`reactive protocols in an ad-hoc network.
`SUMMARY
`These and other problems, drawbacks and limitations of
`conventional techniques are overcome according to the
`present invention by placing a broadcast message which the
`Source expects a reply message in a broadcast message for
`route discovery. The combined message is broadcast
`throughout the ad-hoc network. When the combined broad
`cast message is received at the destination node, the desti
`nation node generates a response message including a reply
`message to the broadcast message that the Source node
`expects a reply. The response message is Sent back to the
`Source node over the route which the combined broadcast
`message traveled to the destination node.
`Accordingly, it is an objective of the present invention to
`minimize the amount of broadcasts required for Setting up a
`route in an ad-hoc network.
`It is another objective of the present invention to mini
`mize the load on the network when Setting up a route in an
`ad-hoc network by placing a broadcast message which the
`Source node expects a reply message in a broadcast message
`which determines a route to the node which generates the
`reply message.
`It is also an objective of the present invention to lower the
`delay at the Source node by Speeding up the Signaling
`required to Set up a route between a Source and destination
`node.
`In accordance with one aspect of the present invention,
`the foregoing and other objects are achieved by a method
`and/or an apparatus for determining a route from a Source
`node to a destination node, wherein a request for route
`broadcast message is used to discover and establish routes
`between the Source node and destination node. The Source
`node generates a broadcast message for which the Source
`node expects a reply message. The broadcast message is
`placed in a request for route broadcast message. The Source
`node then broadcasts the request for route broadcast mes
`Sage to neighboring nodes.
`In each of the neighboring nodes it is determined whether
`the particular neighboring node is the node which generates
`a reply message. If the particular node is the node which
`generates a reply message then a response message to the
`request for route broadcast message is generated. The
`response message is Sent to the Source node over the
`temporary route Stored in each neighboring node in a path
`between the Source node and the node which generated the
`reply message. AS the response message is Sent from the
`node which generate the reply message to the Source node a
`route is activated in each of the neighboring nodes in the
`route between the Source node and the destination node.
`In accordance with yet another aspect of the present
`invention, the foregoing and other objects are achieved by a
`method and/or an apparatus for determining a route from a
`Source node to another node, wherein all nodes in the
`network include a network adaptation layer and a higher
`layer. In the higher layer of the Source node a broadcast
`message for which the Source node expects a reply message
`is generated. The message for which the Source node expects
`
`Page 14 of 21
`
`
`
`US 6,704,293 B1
`
`S
`a reply message is placed in a network adaptation layer
`request for route broadcast message. The network adaptation
`layer request for route broadcast message is broadcast from
`the Source node to neighboring nodes.
`
`15
`
`6
`will broadcast the message to all neighbor nodes in accor
`dance with step 606.
`If the Source node does expect a reply to the broadcast
`message, in accordance with the “Yes” path out of decision
`Step 604, the Source node piggybacks the broadcast message
`in a request for route broadcast message in accordance with
`step 608. In addition, if the source node cannot determine
`whether it expects a reply message in response to the
`broadcast message then the Source node will piggyback the
`broadcast message in a request for route message in accor
`dance with the “Yes” path out of decision step 604. In step
`615 the source node broadcasts the request for route mes
`Sage to its neighbor nodes. For example, referring now to
`FIG. 3, if node 303 were the Source node then the broadcast
`message would be sent to nodes 301, 302 and 304.
`Alternatively, the source node will only broadcast the
`request for route message to forwarding nodes.
`In Step 617 the request for route message is received by
`a neighbor node. In step 620 the neighbor node determines
`whether the node has already processed the request for route
`message. Each node has a broadcast buffer which Stores the
`Source address and broadcast identifier pair. The broadcast
`buffer also stores the time which the message has been
`received to determine if the node has processed the broad
`cast message within a predetermined period of time. AS one
`skilled in the art will recognize the predetermined time
`period is Set long enough that the node will not rebroadcast
`a message it has already rebroadcast, but short enough that
`the buffer does not require an extensive amount of memory.
`If the node determines that Source address and broadcast
`identifier pair of the received message matches one of the
`Source address and broadcast identifier pairs Stored in the
`broadcast buffer, in accordance with the “Yes” path out of
`decision Step 620, the node will drop the message in
`accordance with step 625.
`If the node determines that the request for route message
`has not been previously processed, in accordance with the
`“No” path out of decision step 620, the node will store the
`Source address and broadcast identifier pair in the broadcast
`buffer along with the time that the request for route message
`was received by the node in accordance with step 630. In
`step 635 the node stores a temporary route back to the
`SOCC.
`In step 640 the node determines whether the piggybacked
`data indicates that the node is the destination node. If the
`piggybacked data does not indicate that the node is the
`destination node, in accordance with the “No” path out of
`decision Step 640, the node replaces its address in the request
`for route message in accordance with Step 658.
`Alternatively, if the protocol used provides a mechanism for
`retrieving this information from the lower layers, the node
`will not need to insert its own address. In step 660 the node
`rebroadcasts the request for route message to its neighbor
`nodes. This processing occurs in each node which receives
`the broadcast message as illustrated by the return path from
`step 660 to step 617.
`If the piggybacked data indicates that the node is the
`destination node, in accordance with the “Yes” path out of
`decision Step 640, the node will piggyback a reply message
`in the route response message in accordance with Step 642.
`In step 645 the node will send the route response to the next
`node in the temporary route. In step 665 the next node
`determines whether it is the Source node by examining the
`address in the message. If the node is not the Source node,
`in accordance with the “No” path out of decision step 665,
`the node activates the route in accordance with step 670. In
`
`25
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The objects and advantages of the invention will be
`understood by reading the following detailed description in
`conjunction with the drawings in which:
`FIG. 1 illustrates an exemplary piconet;
`FIG. 2 illustrates an exemplary Star-topology network;
`FIG. 3 illustrates an exemplary scatternet formed by a
`plurality of piconets,
`FIG. 4a illustrates the protocol layers of a conventional
`Bluetooth unit;
`FIG. 4b illustrates the protocol layers of a Bluetooth unit
`according to an exemplary embodiment of the present
`invention;
`FIG. 5 illustrates conventional route discovery tech
`niques,
`FIG. 6 illustrates an exemplary method for performing
`route discovery in an ad-hoc network;
`FIG. 7 illustrates an exemplary method for combining a
`broadcast for which a Source node expects a reply message
`with route discovery in an ad-hoc network,
`FIG. 8 illustrates another exemplary method for combin
`ing a broadcast for which a Source node expects a reply
`message with route discovery in an ad-hoc network; and
`FIG. 9 illustrates yet another exemplary method for
`combining a broadcast for which a Source node expects a
`reply message with route discovery in an ad-hoc network.
`DETAILED DESCRIPTION
`The present invention is directed to minimizing the
`amount of broadcast messages Sent during route discovery.
`In general, the present invention accomplishes this by com
`bining broadcast messages which the Source node expects a
`40
`reply message with broadcast messages for route discovery.
`In So doing, the broadcast messages for which a Source node
`expects a reply message can also be used to Support route
`discovery.
`In the following, the present invention is described as a
`route discovery technique for use in a Bluetooth Scatternet.
`However, one skilled in the art will recognize that the
`present invention is applicable to wireline or wireleSS
`networks, fixed networks and other types of ad-hoc net
`WorkS.
`Every broadcast message should contain a broadcast
`identifier in the network adaptation layer header. In addition,
`the broadcast messages should contain a Source address
`which uniquely identifies the Source. For example, at the
`time of manufacture each Bluetooth unit is assigned a
`globally unique 48 bit IEEE 802 address called the Blue
`tooth Device Address (BD ADDR) which is never
`changed. Accordingly, the broadcast identifier together with
`the Source address will uniquely identify the particular
`broadcast.
`FIG. 6 illustrates an exemplary method for using broad
`cast messages for route discovery. In Step 602 the Source
`node generates a broadcast message. In Step 604 the Source
`node determines whether the broadcast message is the type
`for which the Source node expects a reply message. If the
`Source node does not expect a reply message, in accordance
`with the “No” path out of decision step 604, the source node
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 15 of 21
`
`
`
`US 6,704,293 B1
`
`1O
`
`15
`
`35
`
`40
`
`25
`
`7
`Step 675 the node Sends the route response message to the
`next node in the temporary route. If the node is the Source
`node, in accordance with the “Yes” path out of decision Step
`665, the node activates the route in accordance with step
`680. In step 685 the source node begins sending data over
`the new route identified in the route response message. Since
`a period of time will have passed between the time that the
`Source node requested a route to the destination and the
`Source node has received the route response, the Source node
`can buffer the data packets which it desires to transmit over
`the route. Alternatively, the Source node can simply drop the
`packets. Since the destination node does not rebroadcast the
`request to Surrounding nodes, the Surrounding nodes will not
`be disturbed by the route request broadcast. This will
`remove Some of the load on the network.
`It would be desirable to support IP in a Bluetooth scat
`ternet. However, Since Bluetooth requires the Slave nodes to
`communicate through a master node to transmit data to other
`nodes, Bluetooth does not provide a true shared network.
`Accordingly, Bluetooth cannot currently Support IP.
`FIG. 4b illustrates exemplary Bluetooth units which can
`implement IP. The Bluetooth units of FIG. 4b are similar to
`the Bluetooth units of FIG. 4a with the exception that the
`Bluetooth units of FIG. 6 include a network adaptation
`layerS 461 and 462. Using the network adaptation layer, an
`entire Scatterne