the experiments discussed in this chapter.
1. A. Acharya, A. Misra, and S. Bensal, â€śA Label-switching Packet Forwarding Architecture for
Multi-hop Wireless LANs,â€ť in Proceedings of the ACM Workshop on Mobile Multimedia
(WoWMoM 2002), Atlanta, GA, September 28, 2002.
2. A. Ahuja et al., â€śPerformance of TCP over Different Routing Protocols in Mobile Ad-Hoc Net-
works,â€ť in Proceedings of the IEEE Vehicular Technology Conference (VTC 2000), Tokyo,
Japan, May 2000.
3. G. Anastasi , E. Borgia, M. Conti, and E. Gregori, â€śIEEE 802.11 Ad Hoc Networks: Perfor-
mance Measurements,â€ť in Proceedings of the Workshop on Mobile and Wireless Networks
(MWN 2003), Providence, Rhode Island, May 19, 2003.
4. K. Chandran, S. Raghunathan, S. Venkatesan, and R. Prakash, â€śA Feedback Based Scheme for
Improving TCP Performance in Ad Hoc Wireless Networks,â€ť IEEE Personal Communication
Magazine, Special Issue on Ad Hoc Networks, 8, 1, 34â€“39, February 2001.
5. T. Clausen et al., â€śOptimized Link State Routing Protocol,â€ť Internet Draft, IETF MANET
Working Group, November 2002, available at http://menetou.inria.fr/olsr/draft-ietf-manet-olsr-
6. T. D. Dyer and R. V. Boppana â€śA Comparison of TCP Performance over Three Routing Proto-
cols for Mobile Ad Hoc Networks,â€ť in Proceedings of the ACM Symposium on Mobile Ad Hoc
Networking & Computing (MobiHoc), October 2001.
7. T. Ephremides, â€śA Wireless Link Perspective in Mobile Networking,â€ť ACM Mobicom 2002
keynote speech, available at http://www.acm.org/sigmobile/mobicom/2002/program/.
8. T. Ephremides, â€śEnergy Concerns in Wireless Networks,â€ť IEEE Wireless Communications,
48â€“59, August 2002.
9. Z. Fu, X. Meng, and S. Lu, â€śHow Bad TCP Can Perform in Mobile Ad Hoc Networks,â€ť in Pro-
ceedings of the IEEE Symposium on Computers and Communications (ISCC 2002), Taormina-
Giardini Naxos, Italy, July 2002, pp. 298â€“303.
10. Z. Fu, P. Zerfos, K. Xu, H. Luo, S. Lu, L. Zhang, and M. Gerla, â€śThe Impact of Multihop Wire-
less Channel on TCP Throughput and Loss,â€ťProceedings of IEEE INFOCOM 2003, San Fran-
cisco (CA), March 30 - April 3, 2003.
11. GloMoSim, Global Mobile Information Systems Simulation Library, http://pcl.cs.ucla.edu/pro-
12. G. Holland and N. Vaidya, â€śAnalysis of the TCP Performance over Mobile Ad Hoc Networks,â€ť
in Proceedings of the ACM International Conference on Mobile Computing and Networking
(MobiComâ€™99), Seattle, WA, August 1999, pp. 207â€“218.
13. G. Holland and Nitin H. Vaidya â€śAnalysis of TCP Performance over Mobile Ad Hoc Networks,â€ť
ACM/Kluwer Journal of Wireless Networks 8(2â€“3), 275â€“288, 2002.
14. Official Homepage of the IEEE 802.11 Working Group, http://grouper.ieee.org/groups/802/11/.
15. IEEE Standard 802.11, â€śWireless LAN Medium Access Control (MAC) and Physical Layer
(PHY) Specifications,â€ť August 1999.
16. J. Li, C. Blake, D. De Couto, H. Lee, and R. Morris, â€śCapacity of Wireless Ad Hoc Wireless
Networks,â€ť in Proceedings of the ACM International Conference on Mobile Computing and
Networking (MobiComâ€™01), Rome, Italy, pp. 61â€“69, July 2001.
17. J. Liu and S. Singh, â€śATCP: TCP for Mobile Ad Hoc Networks,â€ť IEEE Journal on Selected
Areas in Communications (J-SAC), 19(7), 1300â€“1315, July 2001.
18. H. Lundgren, E. Nordstron, and C. Tschudin, â€śCoping with Communication Gray Zones in
IEEE 802.11 Based Ad Hoc Networks,â€ť in Proceedings of the ACM Workshop on Mobile Multi-
media (WoWMoM 2002), Atlanta, GA, September 28, 2002, pp. 49â€“55.
19. J. P. Monks, P. Sinha, and V. Bharghavan, â€śLimitations of TCP-ELFN for Ad Hoc Networks,â€ť in
Proceedings of MoMuc 2000, Tokyo, Japan, October 2000.
20. The Network Simulatorâ€“ns-2. http://www.isi.edu/nsnam/ns/index.html.
21. M. S. Obaidat and D. G. Green, â€śAn Accurate Line of Sight Propagation Performance Model
for Ad Hoc 802.11 Wireless LAN (WLAN) Devices,â€ť in Proceedings ICC 2002, New York City,
April 28â€“May 2, 2002.
22. C. Perkins and E. Royer, â€śAd Hoc On-Demand Distance Vector Routing,â€ť in Proceedings of the
2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSAâ€™99), February
23. Qualnet simulator, http://www.qualnet.com/.
24. K. Tang and M. Gerla, â€śFair Sharing of MAC under TCP in Wireless Ad Hoc Networks,â€ť in
Proceedings of IEEE MMTâ€™99, Venice (I), October 1999.
25. C. Tschudin and R. Gold, â€śLUNAR: Lightway Underlay Network Ad Hoc Routing,â€ť available
26. S. Xu and T. Saadawi, â€śDoes the IEEE 802.11 MAC protocol Work Well in Multihop Wireless
Ad Hoc Networks?â€ť IEEE Communication Magazine, 39, 6, 130â€“137, June 2001.
27. S. Xu and T. Saadawi, â€śRevealing the Problems with 802.11 MAC Protocol in Multi-hop Wire-
less Networks,â€ť Computer Networks, 38, 4, March 2002.
28. K. Xu, S. Bae, S. Lee, and M. Gerla, â€śTCP Behavior across Multihop Wireless Networks and
the Wired Networks,â€ť in Proceedings of the ACM Workshop on Mobile Multimedia (WoWMoM
2002), Atlanta (GA), September 28, 2002, pp. 41â€“48.
29. K. Xu and M. Gerla, â€śTCP over an IEEE 802.11 Ad Hoc Network: Unfairness Problems
and Solutions,â€ť UCLA Computer Science Deptartment Technical Reportâ€”020019, May
30. G. Zaruba and S. Das, â€śOff-the-Shelf Enablers of Ad Hoc Networks,â€ť in Mobile Ad Hoc Net-
116 IEEE 802.11 AD HOC NETWORKS: PROTOCOLS, PERFORMANCE, AND OPEN ISSUES
working, S. Basagni, M. Conti, S. Giordano, and I. Stojmenovic (Eds.), IEEE Press/Wiley,
Hoboken, NJ, 2004.
31. Feng Wang and Yongguang Zhang, â€śImproving TCP Performance over Mobile Ad-Hoc Net-
works with Out-of-Order Detection and Response,â€ť in Proceedings of ACM MobiHoc 2002,
Lausanne, Switzerland, 2002.
SCATTERNET FORMATION IN
STEFANO BASAGNI, RAFFAELE BRUNO, and CHIARA PETRIOLI
It is widely anticipated that fourth-generation wireless systems will extensively rely on
the unlicensed operations provided by ad hoc communications . Allowing spontaneous
deployment and self-planning/management, ad hoc networking will play an important
role in delivering all kinds of wireless services from the Internet to the very hands of the
The Bluetooth (BT) technology, as described in the Specifications of the Bluetooth
System, Version 1.1 , is expected to be one of the most promising enabling technolo-
gies for ad hoc networks. Originally introduced as short-range cable replacement, the BT
specifications define ways that each BT device can set up multiple connections with
neighboring devices so that communication can be established in a multihop fashion. In
this sense, Bluetooth devices spread out in a geographic area can provide the missing
wireless extension to the various heterogeneous network infrastructures, allowing a more
pervasive wireless access.
This chapter describes solutions to the fundamental problems that need to be addressed
for the self-organization of Bluetooth devices into an ad hoc network.
According to the specifications, when two BT nodes that are in each othersâ€™ communi-
cation range want to set up a communication link, one of them must assume the role of
master of the communication while the other becomes its slave. This simple â€śone-hopâ€ť
network is called a piconet and may include several slaves, no more than seven of which
can be actively communicating with the master at the same time. If a master has more
than seven slaves, some slaves have to be â€śparked.â€ť To communicate with a parked slave,
a master has to â€śunparkâ€ť it, while possibly parking another slave.
Mobile Ad Hoc Networking. Edited by Basagni, Conti, Giordano, and Stojmenovic.
ISBN 0-471-37313-3 Â© 2004 Institute of Electrical and Electronics Engineers, Inc.
118 SCATTERNET FORMATION IN BLUETOOTH NETWORKS
Figure 4.1. Five piconets forming a connected scatternet.
The specifications allow each node to assume multiple roles. A node can be a master in
one piconet and a slave in one or more other piconets, or a slave in multiple piconets. De-
vices with multiple roles act as gateways to adjacent piconets, thus creating a multihop ad
hoc network called a scatternet.
Figure 4.1 shows the case in which 13 BT devices have been partitioned into four pi-
conets (A, B, C, and D). Masters are represented by pentagons (surrounded by a large cir-
cle that represents their transmission radius), whereas slaves are depicted as small circles.
Adjacent piconets can be interconnected in different ways. Piconets A and B depict the
masterâ€“master case, when two masters are neighbors and interconnection is achieved by
having one of the two masters joining the piconet of the other as a slave (in the figure,
node 2 became the slave of node 1). Two piconets can be joined by a common slave,
termed a gateway slave. This is the case of piconets B and C, which are joined by node 5.
The third case is when piconets are interconnected through a pair of neighboring slaves,
called in the following intermediate gateways, as in the case of piconets C and D, joined
by nodes 6 and 7. In the latter case, interconnection requires that one of the two interme-
diate gateways becomes the master of a new piconet that includes the other intermediate
gateway as a slave (in the figure, node 7 becomes the master of the extra piconet). With
the creation of piconet E, the five piconets of Figure 4.1 form a connected scatternet.
In this chapter, we describe the solutions proposed so far for scatternet formation. The
next section introduces to the basics of the Bluetooth technology. In Section 4.3, we de-
fine the problems underlying scatternet formation, and we also sum up the desirable prop-
erties that should be satisfied by a generated scatternet. Section 4.4 surveys solutions that
have appeared so far in the literature. Sections 4.5 and 4.6 describe in detail two protocols
for generating connected scatternets. Section 4.7 describes some concerns raised by the
implementation of some of the protocols according to the current version of the Bluetooth
specifications. Finally, Section 4.8 concludes the chapter.
4.2 BLUETOOTH BASICS
In this section, we briefly describe the procedures of the Bluetooth technology that are
needed to describe solutions for scatternet formation. This section is not intended to pro-
vide a detailed description of the Bluetooth system, for which the reader is referred to .
Bluetooth operates in the 2.4 GHz, unlicensed ISM band. Frequency-hopping spread
spectrum technology is adopted to reduce interference both among BT nodes and with
technologies that operate in the same band such as IEEE 802.11b.
4.2 BLUETOOTH BASICS
In order to establish a connection between two BT nodes, one of them assumes the role
of master of the communication and the other one becomes its slave. This simple â€śone
hopâ€ť network is called a piconet and may include many slaves, no more than seven of
which can be active at the same time. All devices in a piconet share the same channel (i.e.,
a frequency-hopping sequence) which is derived from the unique ID and Bluetooth clock
of the master.
Communication to and from a device is always performed through the master of the pi-
conet to which it belongs. In particular, a Time-Division Duplex (TDD) scheme is em-
ployed for intrapiconet communications: transmissions occur in pairs of 625 s slots, the
first of which is for masterâ€“slave communication, and the second for the communication
from the polled slave to the master.
A BT device can time share among different piconets. In particular, a device can be ei-
ther the master of one piconet and a slave in other piconets or a slave in multiple piconets.
A node with multiple roles acts as gateway between the piconets to which it belongs. Pi-
conets can be interconnected through gateways into a multihop ad hoc network called a
Piconet formation is performed in two steps: first, devices must become aware of their
neighboring nodes, that is, the nodes in their transmission range (device discovery); then,
information must be exchanged to set up a link between a candidate slave and a candidate
master (link establishment). According to the current BT specifications, the former step is
accomplished by means of the inquiry and inquiry scan procedures, whereas the latter re-
quires the page and page scan procedures.
For device discovery to happen, two neighboring devices have to be in â€śoppositeâ€ť
modes, namely one must be the inquirer (the discovering device), and the other device has
to be willing to be discovered. These modes are implemented in BT by having the inquir-
er be in inquiry mode, and the other device be in inquiry scan mode. The inquirer trans-
mits inquiry ID packets asking neighboring devices to identify themselves and to provide
synchronization information needed for link establishment at a later time. To minimize
the device discovery time, the BT specifications state that ID packets must be very small
(i.e., they include only the General Inquiry Access Code, GIAC, and nothing else) and
that they must be transmitted over the frequencies of a predefined inquiry/inquiry scan
frequency hopping sequence, changing frequencies at a high rate (twice a slot). A device
in inquiry scan hops among different frequencies at a very low rate (one frequency every
1.28 s), thus increasing the probability of a handshake on the same frequency of the in-
quirer. As soon as an ID packet is received at a device in the inquiry scan mode, the device
computes a backoff interval and starts listening again. Only when an ID packet is received
after the backoff phase, the unit in inquiry scan mode will send an FHS (Frequency Hop
Synchronization) packet containing its identity and synchronization information (its BT
The described inquiry procedures lead to an asymmetric knowledge of two neighboring
devices: The inquirer identity is not known at the device that received an inquiry ID packet.
After successful reply from the device in the inquiry scan mode, the inquirer instead, knows
the identity and the clock of the neighbor that just replied. This enables the inquirer v to es-
timate the frequency hopping sequence used by its neighbor and thus to invite it to join its
piconet as a slave. This invitation is accomplished by means of the paging procedures.
In order for two neighboring devices u and v to establish a link, one must be in page
mode (for instance, node v) and the other in page scan mode (node u). By definition, the
device that is in page mode is the master. Node v transmits a page ID packet on uâ€™s fre-
120 SCATTERNET FORMATION IN BLUETOOTH NETWORKS
quencies, containing uâ€™s address. When u, which is in page scan mode, receives such a
packet, it immediately acknowledges it. At this point, v transmits to u a FHS packet that
bears all the required information for u to synchronize on vâ€™s own frequency-hopping se-
quence. Finally, the two devices exchange all the information for setting up a link and a
piconet is formed with v as the master and u as its slave.
It may happen that device u, which is in page scan, is already the master of another pi-
conet and that it could host v as one of its slaves. In this case, once a piconet has been es-
tablished between v and u, with v as the master, the slave u can request a switch of role.
This situation is explicitly addressed by the BT specifications, and it is implemented via
exchanging a specific Link Manager Protocol (LMP) packet that instructs the two devices
to switch to the frequency-hopping sequence of the new master.
To save the energy of BT devices, â€ślow-power operation modesâ€ť have been included in
the specifications that allow BT nodes to â€śgo to sleepâ€ť when they are not actively in-
volved in communication. This feature is also used to let a master â€śreleaseâ€ť a slave so that
the slave can perform protocol-related operations in another piconet. Among the several
modes provided in the specifications for low-power operations, we outline here the func-
tioning of the park mode. A slave that has been put in park mode by its master cannot be
actively involved in communication with that master. However, parked slaves periodically
wake up in predefined beacon slots to listen to their master communication. Unparking of
(possibly multiple) devices is achieved by transmitting an LMP unpark Protocol Data Unit
(PDU) in the beacon slot. This packet carries the ID of the devices to be unparked and
their new active slave addresses. Parked slaves can trigger an unpark LMP PDU by send-
ing explicit requests during preallocated slots (access window). Similarly, active devices
can ask to be parked (or they can be parked by their master) by exchanging an LMP park
packet with their master.
4.3 PROBLEM DESCRIPTION
The problem of scatternet formation concerns the grouping of the network nodes into pi-
conets (piconet formation), and the joining of the piconets into a connected scatternet (pi-