(12) United States Patent
`US 6,704,293 B1
`(10) Patent N0.:
`Larsson et al.
`
`(45) Date of Patent: Mar. 9, 2004
`
`US006704293B1
`
`(54) BROADCAST AS A TRIGGERING
`MECHANISM FOR ROUTE DISCOVERY IN
`AD-HOC NETWORKS
`
`(75)
`
`Inventors: Tony Larsson, Stockholm (SE); Johan
`Rune, Lidingo (SE); Johan Sijrensen,
`Eslov (SE)
`
`(73) Assignee: Telefonaktiebolaget LM Ericsson
`(publ), Stockholm (SE)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/455,460
`
`(22)
`
`Filed:
`
`Dec. 6, 1999
`
`Int. Cl.7 ................................................ H04L 12/28
`(51)
`(52) US. 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
`
`9/1991 Mostafa et 211.
`5,051,984 A
`10/1991 Vu
`5,056,085 A
`11/1991 Hasegawa et 211.
`5,065,399 A
`12/1992 Kusano
`5,173,689 A
`8/1993 Nishimura et 211.
`5,235,599 A
`2/1998 Okanoue
`5,719,861 A
`4/1998 Mahany et 211.
`5,740,366 A
`5/1998 Allen et 211.
`5,748,611 A
`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
`
`0599764
`0883265
`0913965
`9911025
`9923799
`
`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., “IP Services 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
`
`M [PHIN{MI
`mummy/mam _ II/mtmmrmz
`
`”mm mm
`
`mm;
`”MW/0mm;
`
`[HM/M [Hf/f
`
`If7’01?!
`lfllflflflfl/IMIT/l
`
`[IF
`
`12m #120” [IF
`- W,” -
`£45m”
`
`ilflf/M/W flI/f/ M [PH/HIM!
`
`
`[ASH/ID
`
`l
`
`IMF/Will ”III I
`
`1
`
`APPLE 1014
`
`APPLE 1014
`
`1
`
`

`

`US. Patent
`
`Mar. 9, 2004
`
`Sheet 1 0f 11
`
`US 6,704,293 B1
`
`F/y. /
`
`Prior Art
`
`102
`
`101
`
`Fig. 2
`Prior Art
`
`208
`
`/
`
`mom I
`
` \
`
`/f“"
`
`\
`mom 3/ \
`
`2
`
`

`

`US. Patent
`
`Mar. 9, 2004
`
`Sheet 2 0f 11
`
`US 6,704,293 B1
`
`Hg 40
`Prior Art
`
`401
`
`402
`
`”/00 (HT! 570/0001
`0,? 1001/04/70!
`
`0/00 M”! 000M001
`00 APPZ MAI/00’
`
`”7’00! [Ari/f
`
`”7’0,” 1.4/5?
`
`MP H UP
`
`04011 I”
`
`451
`
`04550100
`
`I
`
`010Ef00f/i (ll/f I
`
`04550400
`
`452
`
`Ell/£70070 ”ll/'2
`fill/[700M 00/7 2
`
`”MW [H’fl 000/0001
`00 APP! It‘d/70!
`
`”7’00!HIM
`
`”7’0”
`AWN/W00 (”[0
`
`19/0” [fl/[l 1900/0001
`00 1000017700
`
`III/V00!MIT/f I
`
`IfflMl
`1010/7770! [AYE/i
`
`I
`
`um
`
`12w @1— mm m
`- WW - I
`
`34559.4” _ 5.4559110
`
`0102‘7007/1’ 00” /
`
`3
`
`

`

`US. Patent
`
`Mar. 9, 2004
`
`Sheet 3 0f 11
`
`US 6,704,293 B1
`
`Flg. 5
`Prior Art
`
`505
`
`50006? 000;” 0f0f00ff5 0555005
`
`
`510
`00/0/157 00 000000457?
`
`00/0057
`
`000000157
`
`
`
`SE00 000,400,457 H0051"
`fp [fly/mag 0005'
`
`515
`
`520
`
`
`
`/.5'
`
`mm m par/MUM
`
`
`no”;
`
`00
`
`530 mm: 0005 mum/'5 mmr
`mm mm #555165
`
`YES
`
`5500 000015f f0000f
`SPEC/H50 /0 0007/00 Hfllf
`
`525
`
`535
`
` ”-5
`
`
`mm” mm mam
`mom/m #555405
`
`
`
`
`
`”700000 0005
`
`0105407 00005930 0f00f5ff00
`
`000/[01'550052
`
`
`
`00
`
`
`
`
`5700i 5000” 00015000035
`000 000000057 /0[0/'/f/[0
`
`
`
`05000000057 015005.57 F00 000f£r
`05550015 ['0 01700000 0005
`
`555
`
`
`057/007/00 0006?
`
`560
`
`[’55
`
`
`
`
`,0
`
`000/J 069.5140[
`
`545
`
`565
`
`51500 05000.91: 0.400
`f0 500005
`
`570
`
`050/0 5500/00 7'0
`0(5f/0lf/00 0050 0!", 000ff
`
`4
`
`

`

`US. Patent
`
`Mar. 9, 2004
`
`Sheet 4 0f 11
`
`US 6,704,293 B1
`
`Fig. 60
`
`602
`
`mm mm mm755‘
`”wow #55er
`
`604
`
`
`
`
`”[5 5W” "W
`
`
`mm A RESPMSE m mwmr
`
`
`1mML:2
`
`
`me
`
`608
`
`
`
`mm l/Mf Pmmm
`WWW 1mm" II I
`FEW/[5f I'M #0075 13.5146?
`
`615
`
`SWIM? IMF ”010614513 [[0057
`FM #01172“ ”195165
`
`M
`
`5m Mfllflé‘lS/lfSSlé‘f
`m m llama/H1005:
`
`606
`
`RIMES? I’M lMflff #5551455
`WEI/I’M 3/ 15/67/30:? #00:?
`
`617
`
`620
`
`
`
`
`
`
`If/MIM Iflflf
`Al #540, ”0555350 ”WI/£57 F01?
`MW!" ”$5,465?
`
`
`
`
` m
`
`wrap 1mm
`
`625
`
`I0
`
`630
`
`670:?! ”WM #00!" AMFFSS
`”0 ”01400137 IDEIf/f/[fl
`
`635
`
`[VF/MM)? llflflf 570,95 fflfflfi/flfl'
`[Ml/ff RAM 70 Soil/ME IMF
`
`5
`
`

`

`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
`
`#0
`
`I005 RIF/’1 MES 40017595
`M #555455
`
`653
`
`5570 ”WI
`fifSPflISf #155546?
`
`M 500M! #005
`
`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'
`
`6
`
`

`

`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 0550105
`
`705
`
`
`
`0/0070100 100, 0105 0500107/00, 00 0000
`000100157 0555105 /0 011 0500557 500
`00075 000000500 000100107 0550105
`
`710
`
`000100157 011 0500557 500
`00075 06000507 0500105
`
`715
`
`
`
`717
`
`0500507 500 00075 0500105 0505/050 170005
`
`
`
`
`
`0500507 500
`
`
`0000
`
`
`00075 0/500050)’ 0555105110510)’
`0555105
`
`
`0550 0000555500
`
`
`00
`
`.S'7005 500005 0005 1000550
`100 000100107 /0507/5/50
`
`
`
`0005 570055 750000107 00075
`0101' 70 500005 0005
`
`5500 0/00/0100 0171 70 070050 [50515
`
`
`
`
`
`
`0005 050001001575 0505105
`
`755
`
`7
`
`

`

`US. Patent
`
`Mar. 9, 2004
`
`Sheet 7 0f 11
`
`US 6,704,293 B1
`
`740
`
`
`
`
`
`I005 I'll/41' MIMI”? ”Pl/f
`
`
`765
`
`”@
`
`745
`
`Fifi/546‘! /I Ht
`MW!" IFS/WISE 135.4”
`
`750
`
`007/007? 0007070 0000
`
`755
`
`Si” 041 000/? 0550005!
`0055400 07/50 75100000,? 000/:r
`
`760
`
`766
`
`407/0070 00mr
`0/ 5000050001r
`
`r05
`
`500000 00050
`
`765
`
`
`
`5000 0/00/000000
`0m 0/7 00070001
`mar I” 5700:"
`Edi/ff f0 ”Hf/Ilf/fll
`
`007/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
`
`8
`
`

`

`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 ”If
`
`9
`
`

`

`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
`
`10
`
`10
`
`

`

`US. Patent
`
`Mar. 9, 2004
`
`Sheet 10 0f 11
`
`US 6,704,293 B1
`
`Hg 90
`
`5003051005 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‘
`
`0MP
`”[55”;
`
`”:5
`
`725
`
`
`
`my!” FM
`[Ml/IT WSMVHFI’ #5515511!le
`
`
`JEEI P30669550?
`
`'
`
`945
`
`FffllfllflflSfS ,m
`
`I005
`
`#5516?
`
`570” 5001905 #00:? [WIPES
`MW 5070100457 lflflf/f/[I
`
`Wflf mm rrmmr mm
`316‘! m 500,901: Iflflf
`
`7 7
`2
`
`730
`
`515W ”FF/316‘! 04/! f0 WEI/[I lfl’flé’
`
`732
`
`”If Pifflffffll/IM AIM/If 01‘ I715
`
`934
`
`
`
`____.__ ._____._____J___
`
`11
`
`11
`
`

`

`US. Patent
`
`Mar. 9, 2004
`
`Sheet 11 0f 11
`
`US 6,704,293 B1
`
` —-———-
`
`936
`
`940
`
`f/leI MM}?! A’fflf/I’ffl
`70/667,946! 01/74
`
`
`
`
`film/[I lA/[IS
`Ila/6W? 17/1] 4 REPU'
`
`f0 PIN/MM 0AM
`
`MAT/HIM?
`
`r59
`
`#66781” M’ Ill
`MW? [[5100le [EH/46'!
`
`T50
`
`Apr/mi MM? ll pawl/7MWI
`
`755
`
`mm m ml? ,mflo/Isf
`#5546! am? mil/WI” 7707/75
`
`m
`
`766
`
`Aer/V475 ”WI
`
`75
`
`765
`
`55M Pix/mm)
`mm W I’M/71M!
`mm mm mm;
`[WI/2' f0 flffflllf/fll
`
`I” #0072:
`
`ifF/I SEW/[6‘
`0.4M WM
`
`Aer/ml? 701/75 ll
`717579150777! #005
`
`
`
`
`
`
`
`WM 55”! #55165
`['0 #5171005 /I
`
`MIMI!” [Ml/ff
`
`767
`
`759
`
`F[9 90
`
`12
`
`12
`
`

`

`US 6,704,293 B1
`
`1
`BROADCAST AS A TRIGGERING
`MECHANISM FOR ROUTE DISCOVERY IN
`AD-HOC NETWORKS
`
`This application is related to: US. Pat. No. 6,535,498
`“Route Updating In Ad-Hoc Networks”; US. Provisional
`Application No. 60/168,742 “Route Discovery Based Pico-
`net Forming”; US. patent application Ser. No. 09/454,758
`“Inter Piconet Scheduling”; and US. Pat. No. 6,480,505
`“Batched Fair Exhaustive Polling Scheduler”, all of which
`are herein expressly incorporated by reference.
`BACKGROUND
`
`5
`
`10
`
`The present invention relates to ad-hoc networks. More
`particularly,
`the present
`invention relates to routing in
`ad-hoc networks.
`
`15
`
`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.
`
`is formed by multiple independent and
`A scatternet
`unsynchronized piconets. FIG. 3 illustrates an exemplary
`scatternet 300. In FIG. 3, piconet 1 includes a master node
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`303 and the slave nodes 301, 302 and 304; piconet 2 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.
`in
`If a route to the destination node is not known,
`accordance with the “No” path out of decision step 520, then
`13
`
`13
`
`

`

`US 6,704,293 B1
`
`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.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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
`14
`
`14
`
`

`

`US 6,704,293 B1
`
`5
`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.
`
`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
`
`invention is directed to minimizing the
`The present
`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
`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 (BDiADDR) 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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
`source.
`
`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
`15
`
`15
`
`

`

`US 6,704,293 B1
`
`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 scatternet can be regarded as an IP subnet. Since the
`IP protocol layer assumes that there is a shared network, the
`network adaptation layer emulates a shared network, i.e., a
`broadcast network. The network adaptation layer provides a
`routing mechanism to route information within a scatternet
`while emulating towards the IP layer that the scatternet is
`actually a single s