eral case of multihop topologies have been illustrated. Two approaches for generating con-
nected scatternets whose piconets have no more than seven slaves for multihop networks
have been illustrated in detail. Observations and comments were given that described con-
136 SCATTERNET FORMATION IN BLUETOOTH NETWORKS
cerns arising while implementing scatternet formation protocols by following the current
specifications (Version 1.1).
The authors wish to thank Carla Fabiana Chiasserini, Imrich Chlamtac, Francesca Cuo-
mo, Gabriele Mambrini, and Ivan Stojmenovic for valuable comments and useful discus-
sions on the topics of this chapter.
1. W. Kellerer, H.-J. VĂ¶gel, and K.-E. Steinberg, â€śA communication gateway for infrastructure in-
dependent 4G wireless access,â€ť IEEE Communications Magazine, 40, 3, pp. 126â€“131, March
2. http://www.bluetooth.com, Specification of the Bluetooth System, Volume 1, Core, Version 1.1,
February 22, 2001.
3. B. N. Clark, C. J. Colburn, and D. S. Johnson, â€śUnit disk graphs,â€ť Discrete Mathematics, 86,
4. G. MiklĂłs, A. RĂˇcz, Z. Turanyi, A. ValkĂł, and P. Johansson, â€śPerformance aspects of Bluetooth
scatternet formation,â€ť in Proceedings of ACM MobiHoc 2000, Boston, MA, August 11 2000.
5. P. Bhagwat and S. P. Rao, â€śOn the characterization of Bluetooth scatternet topologies,â€ť
6. R. Guerin, E. Kim, and S. Sarkar, â€śBluetooth technology: Key challenges and initial research,â€ť
in Proceedings of the SCS Conference on Networks and Distributed Systems, CNDS 2002, San
Antonio, TX, January 27â€“31 2002.
7. F. Cuomo and T. Melodia, â€śA general methodology and key metrics for scatternet formation in
Bluetooth,â€ť in Proceedings of IEEE Globecom 2002, Taipei, Taiwan, 17â€“21 November 2002.
8. T. Salonidis, P. Bhagwat, L. Tassiulas, and R. LaMaire, â€śDistributed topology construction of
Bluetooth personal area networks,â€ť in Proceedings of the IEEE Infocom 2001, Anchorage, AK,
April 22â€“26 2001, pp. 1577â€“1586.
9. M. Ajmone Marsan, C. F. Chiasserini, A. Nucci, G. Carello, and L. De Giovanni, â€śOptimizing
the topology of Bluetooth wireless personal area networks,â€ť in Proceedings of IEEE Infocom
2002, New York, 23â€“27 June 2002.
10. S. Baatz, C. Bieschke, M. Frank, P. Martini, C. Scholz, and C. KĂĽhl, â€śBuilding efficient Blue-
tooth scatternet topologies from 1-factors,â€ť in Proceedings of WOC 2002, 2002.
11. C. Law, A. K. Mehta, and K.-Y. Siu, â€śA new Bluetooth scatternet formation protocol,â€ť
ACM/Kluwer Journal on Mobile Networks and Applications (MONET), Special Issue on Mobile
Ad Hoc Networks (A. Campbell, M. Conti and S. Giordano, eds.), 8, 5, 485â€“498, October 2003.
12. G. Tan, A. Miu, J. Guttag, and H. Balakrishnan, â€śAn efficient scatternet formation algorithm for
dynamic environment,â€ť in Proceedings of the IASTED Communications and Computer Net-
works (CCN), Cambridge, MA, November 4â€“6 2002.
13. S. Basagni and C. Petrioli, â€śMultihop scatternet formation for Bluetooth networks,â€ť in Proceed-
ings of the 55th IEEE Semiannual Vehicular Technology Conference, VTC Spring 2002, Birm-
ingham, AL, May 6â€“9 2002, vol. 1, pp. 424â€“428.
14. C. Petrioli, S. Basagni, and I. Chlamtac, â€śConfiguring BlueStars: Multihop scatternet formation
for Bluetooth networks,â€ť IEEE Transactions on Computers, special issue on Wireless Internet
(Y.-B. Lin and Y.-C. Tseng, eds.), 52, 6, 779â€“790, June 2003.
15. G. ZĂˇruba, S. Basagni, and I. Chlamtac, â€śBlueTreesâ€”Scatternet formation to enable Blue-
tooth-based personal area networks,â€ť in Proceedings of the IEEE International Conference on
Communications, ICC 2001, Helsinki, Finland, June 11â€“14 2001, vol. 1, pp. 273â€“277.
16. Z. Wang, R. J. Thomas, and Z. Haas, â€śBlueNetâ€”A new scatternet formation scheme,â€ť in Pro-
ceedings of the 35th Hawaii International Conference on System Science (HICSS-35), Big Is-
land, Hawaii, January 7â€“10 2002.
17. I. Stojmenovic, â€śDominating set based Bluetooth scatternet formation with localized mainte-
nance,â€ť in Proceedings of the Workshop on Advances in Parallel and Distributed Computational
Models, Fort Lauderdale, FL, April 2002.
18. X. Li and I. Stojmenovic, â€śPartial Delaunay triangulation and degree-limited localized Blue-
tooth scatternet formation,â€ť in Proceedings of AD-HOC NetwOrks and Wireless (ADHOC-
NOW), Fields Institute, Toronto, Canada, September 20â€“21 2002.
19. C. Petrioli, S. Basagni, and I. Chlamtac, â€śBlueMesh: Degree-constrained multihop scatternet
formation for Bluetooth networks,â€ť ACM/Kluwer Journal on Special Topics in Mobile Network-
ing and Applications (MONET), Special Issue on Advances in Research of Wireless Personal
Area Networking and Bluetooth Enabled Networks (G. Zaruba and P. Johansson, eds.), 9, 1,
33â€“47, February 2004.
20. S. Basagni, â€śDistributed clustering for ad hoc networks,â€ť in Proceedings of the 1999 Interna-
tional Symposium on Parallel Architectures, Algorithms, and Networks (I-SPANâ€™99), A. Y.
Zomaya, D. F. Hsu, O. Ibarra, S. Origuchi, D. Nassimi, and M. Palis eds., Perth/Fremantle, Aus-
tralia, June 23â€“25 1999, pp. 310â€“315, IEEE Computer Society.
21. C. Petrioli and S. Basagni, â€śDegree-constrained multihop scatternet formation for Bluetooth
networks,â€ť in Proceedings of the IEEE Globecom 2002, Taipei, Taiwan, R.O.C., November
17â€“21 2002, vol. 1, pp. 222â€“226.
22. I. Chlamtac and A. FaragĂł, â€śA new approach to the design and analysis of peer-to-peer mobile
networks,â€ť Wireless Networks, 5, 3, 149â€“156, May 1999.
23. S. Basagni, R. Bruno, and C. Petrioli, â€śPerformance evaluation of a new scatternet formation
protocol for multi-hop Bluetooth networks,â€ť in Proceedings of the 5th International Symposium
on Personal Wireless Multimedia Communications, WPMC 2002, Honolulu, Hawaii, October
27â€“30 2002, vol. 1, pp. 208â€“212.
24. S. Basagni, R. Bruno, G. Mamerini, and C. Petrioli, â€śComparative performance evaluation of
scatternet formation protocols for networks of Bluetooth devices,â€ť Wireless Networks, 10, 12,
197â€“213, March 2004.
25. A. C.-C. Yao, â€śOn constructing minimum spanning trees in k-dimensional spaces and related
problems,â€ť SIAM Journal on Computing, 11, 4, 721â€“736, November 1982.
ANTENNA BEAMFORMING AND POWER
CONTROL FOR AD HOC NETWORKS
The physical layer underlying ad hoc networks has a number of parameters that can be
controlled for improved performance. Such parameters include modulation, transmit pow-
er, spreading code, and antenna beams. By controlling these transceiver parameters adap-
tively and in an intelligent manner, one can increase the capacity of the system tremen-
This chapter addresses the question: how do we control the physical layer parameters
for best performance? We consider two parametersâ€”transmit power and antenna beam
directionâ€”and present state-of-the-art methods for their control and their effect on per-
formance. Although control of other parameters (such as modulation, coding, etc.) can
also yield benefits, we shall focus on antennas and power control as they have been the
most studied, perhaps because they are intuitively the easiest to exploit. Further, as we
shall examine in considerable detail later, power control and beamforming are highly syn-
ergistic. It is therefore useful to study these parameters jointly, as this chapter does.
The benefits of antenna beamforming include reduced interference due to the narrower
beamwidth, longer range due to higher signal-to-noise ratio (by virtue of higher gain and
lesser multipath), and improved resistance to jamming. The benefits of power control in-
clude reduced interference and lower energy consumption. Beamforming and lower pow-
ers are also good for covertness [often referred to as low probability of detection (LPD)].
In sum, using antenna beamforming and power control enables higher capacity due to in-
creased spatial reuse, lower latency, better connectivity, longer battery lifetime, and better
Mobile Ad Hoc Networking. Edited by Basagni, Conti, Giordano, and Stojmenovic.
ISBN 0-471-37313-3 Â© 2004 Institute of Electrical and Electronics Engineers, Inc.
140 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS
Controlling antenna beamforming and transmit power judiciously is far from easy. Im-
proper control may result in performance that is poorer than without such control. For in-
stance, reducing the power too much may leave the network unconnected, or produce ex-
cessive delays. Further, directional transmissions introduce new hidden and exposed
terminal problems that may cause a decrease in capacity if not addressed.
Thus, although the use of directional communications and power control appears to
have potential, a number of questions need to be answered: What techniques are required
for power and beamforming control? What are the tradeoffs involved in such control? Do
existing network- and link-layer protocols have to be changed drastically? Does the per-
formance improvement depend on the kind of antennas used, or the granularity of power
control? Is this kind of control feasible in practice; has it been demonstrated? What kinds
of performance improvements are possible, and what has been shown?
This chapter presents an overview of the work done toward answering these and other
such questions. The goal is to provide the reader with an understanding of the problems
encountered in the exploitation of beamforming antennas and power control, solution ap-
proaches to these problems, and their performance benefits. It is targeted toward the mo-
bile ad hoc networking protocol researcher, providing her or him the necessary back-
ground, design tools, ideas, and insights for exploiting beamforming and power control at
the medium-access and network layers.
We note that this is not a chapter on the physical layer. Rather, it is on how such higher
layers as the medium-access control (MAC) and network layers can control the parame-
ters of physical layer technologies. One can think of the details of the particular technolo-
gy itself as a black box that offers â€śknobsâ€ť for control by higher layers. Such a control
may be provided, architecturally, by way of application program interfaces (APIs) above
the physical and the medium-access layers. Use of such APIs facilitates a clean way of
controlling the transceiver parameters without layering violations.
This is also not a chapter on power conservation. Although battery savings may occur
as a side benefit of interference-reducing mechanisms, that is not a focus. Rather, the fo-
cus is on using antenna and power control for increasing the capacity, reducing delay, and
increasing the connectivity of ad hoc networks.
A typical ad hoc network needs a number of mechanisms at the link and network layers
working in cohesion to provide data communications. The medium-access control (MAC)
module provides distributed access to the channel, neighbor discovery is responsible for
identifying nodes within one hop, routing determines routes to destinations, and the for-
warding module uses this information for, say, hop-by-hop packet forwarding. The exact
functions performed by these modules is obviously system- and protocol-specific. For in-
stance, in some reactive (on-demand) protocols, there is no explicit neighbor discovery;
this is implicitly done as part of routing.
Of these mechanisms, the MAC and the neighbor discovery are the most impacted with
respect to antenna and power control. This is not surprising when you consider the fact
that antenna beamforming and power control both most affect spatial reuse and communi-
cation range, which, respectively, are the focus of MAC and neighbor discovery. There are
some opportunities for exploiting antenna beamforming and power control in some other
mechanisms as well, for instance, in route discovery using directional transmissions, but
the majority of the interesting issues (and therefore research) are in the MAC and neigh-
The majority of this chapter is thus devoted to a presentation of the problems in, and
state-of-the-art solutions for, the four combinations shown in Table 5.1.
5.2 BEAMFORMING ANTENNAS
Table 5.1. The Four Different Areas Arising out of a Combination of Modules, and Physical Layer
Parameters that are the Subject of this Chapter
Medium access Directional MAC Power-controlled MAC
Neighbor discovery Antenna-based topology control Power-based topology control
The rest of this chapter is organized as follows. We begin with a brief and very infor-
mal tutorial on beamforming antennas. Then, in Section 5.3, we discuss medium-access
control, in particular, directional MAC, power-controlled MAC, and the benefits of com-
bining the two controls. In Section 5.4, we discuss neighbor discovery, which results in a
mechanism for topology control. We first discuss power-based topology control and then
antenna-based topology control. Section 5.5 summarizes the chapter and overviews some
open problems and interesting areas of research.
5.2 BEAMFORMING ANTENNAS
Of the two transceiver parameters that are the subject of this chapter, namely, transmit
power and beamforming antennas, transmit power control is easily understood. Beam-
forming antennas, however, are a complex and intriguing subject that is not very well un-
derstood by the typical ad hoc neworking researcher. We therefore devote this section to a
brief tutorial on beamforming antennas. This is not intended to cover all aspects of this
technology, nor do we cover it precisely or formally. Rather, the idea is to give the basics
in an informal and intuitive fashion to equip the reader unfamiliar with this topic with just
enough knowledge to understand the remainder of this chapter. Readers familiar with
beamforming antennas may skip this section. Readers wishing to explore this field in de-
tail are referred to  and the citations therein.
5.2.1 Antenna Concepts
Radio antennas couple energy from one medium to another. An isotropic antenna radiates
or receives energy equally well in all directions.1 A directional antenna has certain pre-
ferred transmission and reception directions, that is, it transmits/receives more energy in
one direction compared to the other.
The gain of an antenna is an important concept, and is used to quantify the directional-
ity of an antenna. The gain of an antenna in a particular direction d = ( , ) is given  by
G(d) = (5.1)
where U(d) is the power density in the direction d, Uave is the average power density over
all directions, and is the efficiency of the antenna that accounts for losses. Informally,
gain measures the relative power in one direction compared to an omnidirectional anten-
In reality, no antenna is perfectly omnidirectional, but we use this term to represent any antenna that is not in-
142 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS
na. Thus, the higher the gain, the more directional is the antenna. The peak gain is the
maximum gain taken over all directions. When a single value is given for the gain of an
antenna, it usually refers to the peak gain. Gain is often measured in unitless decibels
(dBi), that is, GdBi = 10 Â· log10(Gabs), where Gabs is the absolute value of gain. An isotrop-
ic antenna has a gain of 0 dBi.
An antenna pattern is the specification of the gain values in each direction in space,
sometimes depicted as projections on the azimuthal and elevation planes. It typically has a
main lobe of peak gain and (smaller gain) side lobes. An example antenna pattern is
shown in Figure 5.1. As is common practice, we use the word beam as a synonym for
â€ślobe,â€ť especially when discussing antennas with multiple/controllable beams/lobes. A
null is a direction of negative (in dBi) gain. For example, the pattern in Figure 5.1 has a
null at 30 degrees.
We note that a larger gain in one direction necessarily results in a reduced gain in some
other direction. Intuitively, one can think of an omnidirectional antennaâ€™s pattern as a ball
of dough around the antenna. The volume of the ball represents the total power. Replacing
this with a directional antenna causes the dough to be â€śsquishedâ€ť around so that some di-
rections are pulled out (gain higher than 0 dB) and some are pushed in (gain lower than 0