<<

. 34
( 87 .)



>>

forming. This is due to the fact that directional neighbor discovery tends to use the longer
links by virtue of the shortest-path routing, which, in turn, causes more interference (re-
call the sidelobes). This bears out and extends to directional communications the conclu-
sion in [40] that, all things being equal, one should use the smallest power (shortest links)
that provides a connected network. This motivates the use of novel topology control and
routing algorithms that use shorter links even when longer directional links exist. It also
motivates cross-layer optimization.
An interesting question, and one that is unique to switched beams, is the dependence of
the performance on the beamwidth and number of beams. Informally, one may think of
the coverage of a switched beam system as B · N/360, where B is the beamwidth of each
beam in degrees and N is the number of beams. Reducing the beamwidth (and thus in-
creasing the gain) has two counteracting effects: on the positive side, range is increased so
farther neighbors are acquired into the topology; on the negative side, the coverage is de-
creased, and the number of “blind” spots increases (directions where there is little or no
gain) increases, and even nearby neighbors that can be acquired with omnidirectional
beams cannot now be acquired.
There has been no study of this trade-off. However, we note that that the optimal value
of the coverage (with N constant) could well be less than 1. For instance, in Figure 5.11,
170 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


consider density 8 and gain of 20 dBi (beamwidth of 20 degrees). The number of antennas
used is 12, giving a coverage of 12 — 20/360, or 0.67. This does substantially better than
omnidirectional (coverage of 1), and somewhat better than 10 dBi antenna (60 degree
beamwidth, coverage of 2).



5.5 SUMMARY AND FUTURE DIRECTIONS

The control of transmit power and antenna beamforming by the medium-access and net-
work layers offers a synergistic way of reducing interference while improving connectivi-
ty. To convert the potential into actual performance gains is a hard problem and requires
radical modifications to existing mechanisms, or new mechanisms.
In this chapter, we considered mechanisms for the exploitation of antenna beamform-
ing and power control for increased spatial reuse and richer connectivity with the goals of
improved throughput, delay, and robustness in mind. Specifically, we considered the four
combinations:

Medium access with beamforming antennas (Directional MAC).
1.
Medium access with power control (Power-controlled MAC).
2.
Neighbor discovery with beamforming antennas (Antenna-based topology control)
3.
Neighbor discovery with power control (Power-based topology control).
4.

Directional MAC in the context of CSMA/CA introduces difficult new problems such
as directional hidden/exposed terminals, loss of NAV state, and so on. A number of new
innovations such as the use of a short NAV directional virtual carrier sensing, and so on.
,
have been utilized to partially overcome these problems.
Power-controlled MAC allows a tighter packing of simultaneous transmissions within
the network. However, new collision scenarios get introduced, an avoidance of which has
thus far required additional capabilities such as busy tone.
Although power control and beamforming by themselves enable a considerable in-
crease in the spatial reuse achivable by a channel-access mechanism, it is when both are
used together that the full potential is achieved. This is intuitively apparent (see Figure
5.6), and borne out by simulations.
Neighbor discovery is the key mechanism that decides the routing topology of the net-
work. This topology can be controlled using beamforming and power control. Power-
based topology control offers an algorithmically rich set of problems. Although many of
these problems are computationally intractable, distributed heuristics have been devel-
oped that provide a good balance between connectivity and spatial reuse.
There are other benefits of transmit-power control and beamforming that have not been
addressed in this chapter. Chief among those is the capability for covertness, or, in mili-
tary parlance, low probability of detection (LPD). Narrow power-controlled beams pro-
vide minimal leakage of energy so that intruders (eavesdroppers) can rarely intercept the
packets. This is a physical layer security feature complementing other features such as
spreading, encryption, and so on.
Although some advances have been made in the exploitation of beamforming antennas
and power control for ad hoc networking, a lot more remains to be done. Some areas that
offer exciting research opportunities include:
171
REFERENCES


Directional CSMA/CA. Current work still does not fully exploit the potential of
beamforming antennas. Multicasting, multichannel operation, and QoS differentia-
tion are some of the other issues in this context. Use of optimum power to further
pack simultaneous transmissions is another area of interest. Finally, the problems of
deafness and loss of state are among the least studied.
Power-controlled CSMA/CA. The solutions for collision avoidance with heteroge-
neous powers rely on busy tones. Can one do this without using an additional chan-
nel?
Neighbor discovery with beamforming. This is a very interesting and under-ex-
plored area. In particular, discovering neighbors when they are not connected by
DO or OO paths is an important but difficult problem.
Theoretical work on limits of ad hoc network capacity with power control and
beamforming, for instance, an extension of [40].
Exploitation of beamforming for other functions such as routing. An example is the
use of directional antennas to reduce the query flooding overhead and simultane-
ously shorten the average hop count of routes in a reactive protocol.

Additionally, there are other physical-layer parameters such as modulation, spreading
codes, and so on. that can also be exploited for improving ad hoc networking perfor-
mance. A study of these in conjunction with beamforming and power control will open up
several new frontiers in research.



REFERENCES

1. J. C. Liberti and T. S. Rappaport, Smart Antennas for Wireless Communications, Prentice-Hall
PTR, 1999.
2. J. Butler and R. Lowe, “Beamforming Matrix Simplifies Design of Electronically Scanned An-
tennas,” Electronic Design, April 1961.
3. P. Karn, “MACA”A New Channel Access Method for Packet Radio,” in Proceedings of
ARRL/CCRL Amateur Radio 9th Computer Networking Conference, September 1990.
4. V. Bhargavan, A. Demeers, S. Shenker, and L. Zhang, “MACAW”A Media Access Protocol
for Wireless LANs,” in Proceedings of ACM SIGCOMM ˜94, September 1994.
5. C. L. Fullmer, J. J. Garcia-Luna-Aceves, “Floor Acquisition Multiple Access (FAMA) for Pack-
et Radio Networks,” in Proceedings of ACM SIGCOMM, 1995, pp. 212“225.
6. IEEE Standards Department, ANSI/IEEE Standard 802. 11”Wireless LAN, IEEE Press, 1999.
7. M. S. Gast, 802. 11 Wireless Networks: The Definitive Guide, O™Reilly and Associates, 2002.
8. R. Ramanathan, “On the Performance of Ad Hoc Networks with Beamforming Antennas,” in
Proceedings of ACM MobiHoc, Long Beach, CA, October 2001.
9. R. R. Choudhury, X. Yang, R. Ramanathan, and N. Vaidya, “Using Directional Antennas for
Medium Access Control in Ad Hoc Networks,” in Proceedings of ACM MOBICOM, Atlanta,
Georgia, September 2002.
10. Y. B. Ko and N. H. Vaidya, “Medium Access Control Protocols Using Directional Antennas in
Ad Hoc Networks,” in Proceedings of IEEE INFOCOM, March 2000.
11. M. Sanchez, T. Giles, and J. Zander, “CSMA/CA with Beam Forming Antennas in Multi-Hop
Packet Radio,” in Proceedings of the Swedish Workshop on Wireless Ad Hoc Networks, March
2001.
172 ANTENNA BEAMFORMING AND POWER CONTROL FOR AD HOC NETWORKS


12. M. Takai, J. Martin, A. Ren, and R. Bagrodia, “Directional Virtual Carrier Sensing for Direc-
tional Antennas in Mobile Ad Hoc Networks,” in Proceedings of ACM MOBIHOC, Lausanne,
Switzerland, June 2002.
13. A. Nasipuri, S. Ye, and R. E. Hiromoto, “A MAC Protocol for Mobile Ad Hoc Networks Using
Directional Antennas,” in Proceedings of the IEEE Wireless Communications and Networking
Conference (WCNC), 2000.
14. S. Bandyopadhyay, K. Hasuike, and S. Horisawa, S. Taware, “An Adaptive MAC and Direction-
al Routing Protocol for Ad Hoc Wireless Network Using ESPAR Antenna,” in Proceedings of
ACM MOBIHOC, Long Beach, California, October 2001.
15. E. Arikan, “Some Complexity Results About Packet Radio Networks,” IEEE Transactions on
Inform. Theory, IT-30, 910“918, July 1984.
16. N. Alon, A. Bar-Noy, N. Linial, and D. Peleg, “ On the Complexity of Radio Communication,”
in Proceedings of Twenty First Annual ACM Symposium on Theory of Computing, pp. 274“285,
1989.
17. S. Ramanathan, “A Unified Framework and Algorithm for Channel Assignment in Wireless
Networks,” Wireless Networks, 5, 81“94, 1999.
18. I. Cidon and M. Sidi, “Distributed Assignment Algorithms for Multihop Radio Networks,”
IEEE Transactions on Computers, 38, 10, 1353“1361, Oct. 1989.
19. R. Ramaswami and K. K. Parhi, “Distributed Scheduling of Broadcasts in a Radio Network,” in
Proceedings of the INFOCOM, 1989.
20. K. Dyberg, L. Farman, F. Eklof, J. Gronkvist, U. Sterner, and J. Rantakokko, “On the Perfor-
mance of Antenna Arrays in Spatial Reuse TDMA Ad Hoc Networks,” in Proceedings of IEEE
MILCOM, Anaheim, California, October 2002.
21. L. Bao, and J. J. Garcia-Luna-Aceves, “Transmission Scheduling in Ad Hoc Networks with Di-
rectional Antennas,” in Proceedings of ACM MOBICOM, Atlanta, Georgia, September 2002.
22. J. P. Monks, V. Bhargavan, and W. W. Hwu, “A Power Controlled Multiple Access Protocol for
Wireless Packet Networks,” in Proceedings of IEEE INFOCOM, Anchorage, Alaska, April
2001.
23. S.-L. Wu, Y.-C. Tseng, and J.-P. Sheu, “Intelligent Medium Access for Mobile Ad Hoc Net-
works with Busy Tones and Power Control,” IEEE Journal on Selected Areas in Communica-
tions, 18, 9, September 2000.
24. J. Deng and Z. J. Haas, “Dual Busy Tone Multiple Access (DBTMA): A New Medium Access
Control for Packet Radio Networks,” in Proceedings ICUPC, October 1998.
25. T. ElBatt and A. Ephremides, “Joint Scheduling and Power Control for Wireless Ad-Hoc Net-
works,” in Proceedings of IEEE INFOCOM, New York, June 2002.
26. N. S. Fahmy, T. D. Todd, and V. Kezys, “Ad Hoc Networks with Smart Antennas Using IEEE
802. 11-Based Protocols,” in Proceedings of IEEE ICC, 2002.
27. R. Ramanathan and R. Hain, “Topology Control of Multihop Radio Networks using Transmit
Power Adjustment,” in Proceedings of IEEE INFOCOM, Tel Aviv, Israel, 2000.
28. N. Shacham, “Protocols for Multi-Satellite Networks,” in Proceedings of IEEE MILCOM,
1988.
29. R. Ramanathan, “Making Ad Hoc Networks Density Adaptive,” in Proceedings of IEEE
MILCOM, Vienna, Virginia, October 2001.
30. F. Harary, Graph Theory, Addison-Wesley, 1972.
31. W. Chen and N. Huang, “The Strongly Connecting Problem on Multihop Packet Radiio Net-
works,” IEEE Transactions on Communications, 37, 3, March 1989.
32. A. E. F. Clementi, P. Penna, and R. Silvestri, “Hardness Results for the Power Range Assign-
ment Problem in Packet Radio Networks,” in Proceedings of 3rd International Workshop on
173
REFERENCES


Randomization and Approximation in Computer Science (APPROX 1999), Lecture Notes in
Computer Science, Vol. 1671, Springer-Verlag, 1999, pp. 195“208.
33. E. L. Lloyd, R. Liu, M. V. Marathe, R. Ramanathan, and S. S. Ravi, “Algorithmic Aspects of
Topology Control Problems for Ad Hoc Networks,” in Proceedings of ACM MOBIHOC, Lau-
sanne, Switzerland, June 2002.
34. V. Rodoplu and T. H. Meng, “Minimum Energy Mobile Wireless Networks,” IEEE Journal on
Selected Areas in Communications, 17, 8, 1333“1344, August 1999.
35. R. Wattenhofer, L. Li, P. Bahl, and Y-M. Wang, “Distributed Topology Control for Power Effi-
cient Operation in Multihop Wireless Ad Hoc Networks,” in Proceedings of IEEE INFOCOM,
Anchorage, Alaska, April 2001.
36. P. Jacquet, P. Muhlethaler, and A. Quayyum, “Optimized Link State Routing Protocol,” IETF
MANET Working Group Internet-Draft, Work in Progress.
37. B. Bellur and R. Ogier, “A Reliable, Efficient Topology Broadcast Algorithm for Dynamic Net-
works,” in Proceedings of IEEE INFOCOM, 1999.
38. Y. B. Ko and N. H. Vaidya. “Location-Aided Routing (LAR) in Mobile Ad Hoc Networks,” in
Proceedings of ACM/IEEE MOBICOM, Dallas, TX, October 25“30, 1998.
39. S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward. “A Distance Routing Effect Al-
gorithm for Mobility (DREAM),” in Proceedings of ACM/IEEE MOBICOM, Dallas, TX, Octo-
ber 25“30, 1998.
40. P. Gupta and P. R. Kumar, “The Capacity of Wireless Networks,” IEEE Transactions on Infor-
mation Theory, IT-46, 2, 388“404, March 2000.
CHAPTER 6




TOPOLOGY CONTROL IN WIRELESS
AD HOC NETWORKS

XIANG-YANG LI




6.1 INTRODUCTION

Recent years have seen a great amount of research in wireless networks, especially ad hoc
wireless networks due to their potential applications in various situations such as battle-
field, emergency relief, and so on. There are no wired infrastructures or cellular networks
in ad hoc wireless network. In this chapter, we assume that each wireless node has an om-
nidirectional antenna and a single transmission of a node can be received by any node
within its vicinity, which we assume is a disk centered at this node. We also discuss
specifically the topology control when directional antennas are used. Each mobile node
has a transmission range. Node v can receive the signal from node u if node v is within the
transmission range of the sender u. Otherwise, they communicate through multihop wire-
less links by using intermediate nodes to relay messages. Consequently, each node in the
wireless network also acts as a router, forwarding data packets for other nodes. In addi-
tion, we assume that each node has a low-power Global Position System (GPS) receiver,
which provides the position information of the node itself. If GPS is not available, the dis-
tance between neighboring nodes can be estimated on the basis of incoming signal
strengths and the direction of arrival. Relative coordinates of neighboring nodes can be
obtained by exchanging such information between neighbors [1].
It is common to separate the network design problem from the management and con-
trol of the network in the communication network literature. The separation is very conve-
nient and helps to significantly simplify these two tasks, which are already very complex
on their own. Nevertheless, there is a price to be paid for this modularity, as the decisions
made at the network-design phase may strongly affect the network management and con-

175
Mobile Ad Hoc Networking. Edited by Basagni, Conti, Giordano, and Stojmenovic.
ISBN 0-471-37313-3 © 2004 Institute of Electrical and Electronics Engineers, Inc.
176 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS


trol phase. In particular, if the issue of designing efficient routing schemes is not taken
into account by the network designers, then the constructed network might not be suited
for supporting a good routing scheme. For example, a backbone like network topology is
more suitable for a hierarchical routing method than a flat network topology.
Wireless ad hoc networks need some special treatment as they intrinsically have their
own special characteristics and some unavoidable limitations compared with wired net-
works. For example, wireless nodes are often powered by batteries only, and they often
have limited memories. A transmission by a wireless device is often received by many
nodes within its vicinity, which possibly causes signal interferences at these neighboring
nodes. On the other hand, we can also utilize this property to save the communications
needed to send some information. Unlike most traditional static communication devices,
the wireless devices often are moving during the communication. Therefore, it is more
challenging to design a network topology for wireless ad hoc networks that is suitable for
designing an efficient routing scheme to save energy and storage memory consumption
than for the traditional wired networks.
To simplify the question so we can derive some meaningful understanding of wireless
ad hoc networks, we assume that the wireless nodes are quasistatic for a period of time.
Then, in technical terms, the question we deal with is whether it is possible (and if possi-
ble, then how) to design a network that is a subgraph of the unit disk graph, such that it
ensures both attractive network features such as bounded node degree, low stretch factor,
and linear number of links, and attractive routing schemes such as localized routing with
guaranteed performance.
Unlike the wired networks that typically have fixed network topologies, each node in a
wireless network can potentially change the network topology by adjusting its transmis-
sion range and/or selecting specific nodes to forward its messages, thus controlling its set

<<

. 34
( 87 .)



>>