Li L.(E)., Halpern J., Bahl P., Wang Y., Wattenhofer R. A Cone-Based Distributed Topology-Control Algorithm for Wireless Multi-Hop Networks

Подождите немного. Документ загружается.

LI et al.: A CONE-BASED DISTRIBUTED TOPOLOGY-CONTROL ALGORITHM FOR WIRELESS MULTI-HOP NETWORKS 157

Fig. 7. Performance comparison through detailed network simulation. (a) Number of trafﬁc sources that remain alive. (b) Average power levels.

1) Energy Consumption: We investigate the energy con-

sumption of the three approaches in terms of the number of

trafﬁc sources alive and the average transmission power levels

over time. As can be seen from Fig. 7, OPT-CBTC has the

best performance. CBTC performs worse than the SMECN

algorithm, but uses only directional information. MaxPower

has signiﬁcantly worse performance than the other algorithms.

Fig. 7(a) shows the number of trafﬁc sources that remain alive

over time. We can see that when almost all the trafﬁc sources

in MaxPower are dead at time 600, about 45% and 30% of the

trafﬁc sources are still alive in SMECN and CBTC, respec-

tively, and more than 79% of the trafﬁc sources are still alive

in OPT-CBTC. The basic CBTC algorithm does not perform

as well as OPT-CBTC, but it still performs much better than

MaxPower.

Next, we consider how the transmission power evolves over

time as nodes die over time. Fig. 7(b) shows the average power

level averaged over all nodes. The “average power level” at time

is computed by considering, for each node still alive at time

, the minimum power currently needed for to reach all its

neighbors (recall that this is the power that

uses in the simu-

lation to send all messages except the NDP “Hello” beacons),

and then averaging this number over all nodes still alive. For

MaxPower, the average power is constant over time because the

maximum power is always used. The curves show that, while

the average power level of CBTC and SMECN increases rapidly

over time as more nodes die, the power level of OPT-CBTC in-

creases rather slowly and remains much lower.

2) Total Number of Packets Delivered and Latency: We

collected packet delivery and latency statistics at the end of

our simulation. SMECN, CBTC and OPT-CBTC were able

to deliver 1.66, 1.44, and 2.94 times the amount of packets

delivered by MaxPower, respectively, throughout the simula-

tion. The statistics for packet delivery and the number of trafﬁc

sources still alive together show that it is undesirable to transmit

with large radius because it increases energy consumption and

causes unnecessary interference, and consequently decreases

throughput. The average packet latencies in decreasing order

are 271, 170, 126, and 79 ms for MaxPower, OPT-CBTC,

CBTC, and SMECN, respectively. MaxPower has the highest

latency due to its low spatial reuse of the spectrum. That is, a

successful transmission by MaxPower reserves a large physical

area. Any node that hears the transmission within this area

backs off and does not transmit itself. Therefore, the larger the

area reserved, the fewer nodes can transmit at any particular

time. OPT-CBTC has higher latency than CBTC and SMECN

because it typically takes longer routes due to the use of lower

transmission power.

VI. C

ONCLUSION

We have analyzed the distributed cone-based algorithm

and proved that

is a tight upper bound on the cone

degree for the algorithm to preserve connectivity. We have

also presented three optimizations to the basic algorithm—the

shrink-back operation, asymmetric edge removal, and pairwise

edge removal—and proved that they improve performance

while still preserving connectivity. Finally, we showed that

there is a tradeoff between using CBTC

with and

, since using allows an additional opti-

mization, which can have a signiﬁcant impact on reducing the

transmission radius. The algorithm extends easily to deal with

reconﬁguration and asynchrony. Most importantly, simulation

results show that it is very effective in reducing power demands

and increases the overall throughput.

Since the focus of this paper has been on reducing energy

consumption, we conclude with some discussion of this goal.

Reducing energy consumption has been viewed as perhaps the

most important design metric for topology control. There are

two standard approaches to doing this: 1) reducing the trans-

mission power of each node as much as possible; and 2) re-

ducing the total energy consumption through the preservation

of minimum-energy paths in the underlying network. These two

approaches may conﬂict: reducing the transmission power re-

quired by each node may not result in minimum-energy paths

or vice versa. Furthermore, there are other metrics to consider,

such as network throughput and network lifetime. Reducing en-

ergy consumption tends to increase network lifetime. (This is

particularly true if the main reason that nodes die is loss of bat-

tery power.) However, there is no guarantee that it will. For

example, using minimum-energy paths for all communication

may result in hot spots and congestion, which in turn may drain

battery power and lead to network partition. Using approach

1) in this case may do better. If topology control is not done

158 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 13, NO. 1, FEBRUARY 2005

carefully, network throughput can be hurt. As we have already

pointed out, eliminating edges may result in more congestion

and, hence, worse throughput, even if it saves power in the short

run. The right tradeoffs to make are very much application de-

pendent. Therefore, an algorithm that adapts to the speciﬁc ap-

plication setting is much needed. Reconﬁguration in response to

node mobility and failure consumes precious energy resources.

Fast convergence of topology control is critical to keep the net-

work functioning well. It would be interesting to investigate how

much mobility CBTC can handle. We hope to explore these is-

sues in more detail in future work.

PPENDIX

PROOF FOR

THEOREM II.2

Fact A.1: The distance

between any two points in a

sector of a circle is no greater than the circle radius .

If both

and are not the center of the circle, then .

Lemma A.2: In Fig. 8,

intersects on the

arc from

clockwise to at point .

Proof: For any two points

, on the arc from clock-

wise to

,if , then . This

follows from a simple geometry argument. Consider triangles

and . Since and the tri-

angles have one side

in common, implies

. Since (by assumption) and

(by Fact A.1), there must be a point on the arc

from

clockwise to such that .

Lemma A.3: Let line intersect at point (if

is the same as , then ) in Fig. 8. To cover

, in the case of of Lemma II.1,

must have at lease one neighbor in sector of

and outside . Among these neighbors, let be the

one such that

is the smallest. cannot lie within the

Proof: For the case of

of Lemma II.1, we

only need to show that

cannot lie within the region (the

region inside sector

of and outside of ).

We prove by contradiction. Suppose

lies in that region. By the

previous lemma,

lies in the arc from to . So both and

are in the sector of . By Fact 1, . Our

assumption is that

. Thus,

. Therefore,

(3)

Since

( is the intersection of

and )

(4)

Since

is inside

(5)

Draw a line

parallel to .Wehave

. By (3), . By (4)

and (5),

. Since

,wehave . This contradicts

our assumption of

’s position. Thus, must be outside

Fig. 8. Illustration for the proof of Lemma A.2 and Lemma A.3.

REFERENCES

[1] K. Calvert, M. Doar, and E. W. Zegura, “Modeling internet topology,”

IEEE Commun. Mag., vol. 35, no. 6, pp. 160–163, Jun. 1997.

[2] A. Chandrakasan, R. Amirtharajah, S. H. Cho, J. Goodman, G. Kon-

duri, J. Kulik, W. Rabiner, and A. Wang, “Design considerations for

distributed microsensor systems,” in Proc. IEEE Custom Integrated Cir-

cuits Conf. (CICC), May 1999, pp. 279–286.

[3] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “Span: an en-

ergy-efﬁcient coordination algorithm for topology maintenance in ad

hoc wireless networks,” in Proc. 7th Annu. ACM/IEEE Int. Conf. Mo-

bile Computing and Networking (MobiCom), 2001, pp. 85–96.

[4] L. P. Clare, G. J. Pottie, and J. R. Agre, “Self-organizing distributed

sensor networks,” in Proc. SPIE Conf. Unattended Ground Sensor Tech-

nologies and Applications, Apr. 1999, pp. 229–237.

[5] J. Gomez, A. T. Campbell, M. Naghshineh, and C. Bisdikian, “Con-

serving transmission power in wireless ad hoc networks,” in Proc. Int.

Conf. Network Protocols (ICNP), Nov. 2001, pp. 24–34.

[6] CMU Monarch Group. (1999, Oct.) Wireless and Mobility Extensions to

ns-2. [Online]. Available: http://www.monarch.cs.cmu.edu/cmu-ns.html

[7] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-

efﬁcient communication protocol for wireless micro-sensor networks,”

in Proc. IEEE Hawaii Int. Conf. System Sciences, Jan. 2000, pp. 4–7.

[8] T.-C. Hou and V. O. K. Li, “Transmission range control in multihop radio

networks,” IEEE Trans. Commun., vol. 34, no. 1, pp. 38–44, Jan. 1986.

[9] L. Hu, “Topology control for multihop packet radio networks,” IEEE

Trans. Commun., vol. 41, no. 10, pp. 1474–1481, Oct. 1993.

[10] L. Jia, R. Rajaraman, and C. Scheideler, “On local algorithms for

topology control and routing in ad hoc networks,” in Proc. SPAA, 2003,

pp. 220–229.

[11] R. E. Kahn, “The organization of computer resources into a packet radio

network,” IEEE Trans. Commun., vol. COM-25, no. 1, pp. 169–178, Jan.

1977.

[12] K. Krizman, T. E. Biedka, and T. S. Rappaport, “Wireless position loca-

tion: fundamentals, implementation strategies, and source of error,” in

Proc. IEEE 47th Vehicular Technology Conf., 1997, pp. 919–923.

[13] L. Li and J. Y. Halpern, “Minimum energy mobile wireless networks

revisited,” in Proc. IEEE Int. Conf. Communications (ICC), Jun. 2001,

pp. 278–283.

[14] L. Li, J. Y. Halpern, P. Bahl, Y. M. Wang, and R. Wattenhofer, “Anal-

ysis of distributed topology control algorithms for wireless multi-hop

networks,” in Proc. ACM Symp. Principles of Distributed Computing

(PODC), Aug. 2001, pp. 264–273.

[15] J. Monks, V. Bharghavan, and W. Hwu, “A power controlled multiple ac-

cess protocol for wireless packet networks,” in Proc. IEEE INFOCOM,

Apr. 2001, pp. 219–228.

[16] C. E. Perkins, Ad Hoc Networking. Reading, MA: Addison-Wesley,

2001.

[17] C. E. Perkins and E. M. Royer, “Ad-hoc on-demand distance vector

routing,” in Proc. 2nd IEEE Workshop on Mobile Computing Systems

and Applications, Feb. 1999, pp. 90–100.

[18] G. J. Pottie and W. J. Kaiser, “Wireless integrated network sensors,”

Commun. ACM, vol. 43, no. 5, pp. 51–58, May 2000.

LI et al.: A CONE-BASED DISTRIBUTED TOPOLOGY-CONTROL ALGORITHM FOR WIRELESS MULTI-HOP NETWORKS 159

[19] R. Prakash, “Unidirectional links prove costly in wireless ad hoc net-

works,” in Proc. Int. Workshop on Discrete Algorithms and Methods for

Mobile Computing and Communications (dialM), 1999, pp. 15–22.

[20] VINT Project. The UCB/LBNL/VINT Network Simulator—ns (Version

2). [Online]. Available: http://www.isi.edu/nsnam/ns

[21] R. Ramanathan and R. Rosales-Hain, “Topology control of multihop

wireless networks using transmit power adjustment,” in Proc. IEEE IN-

FOCOM, Mar. 2000, pp. 404–413.

[22] T. S. Rappaport, Wireless Communications: Principles and Prac-

tice. Englewood Cliffs, NJ: Prentice-Hall, 1996.

[23] V. Rodoplu and T. H. Meng, “Minimum energy mobile wireless net-

works,” IEEE J. Select. Areas Commun., vol. 17, no. 8, pp. 1333–1344,

Aug. 1999.

[24] H. Takagi and L. Kleinrock, “Optimal transmission ranges for randomly

distributed packet radio terminals,” IEEE Trans. Commun., vol. 32, no.

3, pp. 246–257, Mar. 1984.

[25] B. Tuch, “Development of WaveLAN, an ISM band wireless LAN,”

AT&T Tech. J., vol. 72, no. 4, pp. 27–33, 1993.

[26] Y. Wang and X. Y. Li, “Localized construction of bounded degree and

planar spanner for wireless ad hoc networks,” in Proc. ACM DIALM-

POMC Joint Workshop on Foundations of Mobile Computing, 2003, pp.

59–68.

[27] R. Wattenhofer, L. Li, P. Bahl, and Y. M. Wang, “Distributed topology

control for power efﬁcient operation in multihop wireless ad hoc net-

works,” in Proc. IEEE INFOCOM, Apr. 2001, pp. 1388–1397.

[28] R. Wattenhofer and A. Zollinger, “XTC: a Practical Topology Control

Algorithm for Ad-Hoc Networks,” Computer Science Department, ETH

Zurich, Tech. Rep. 407, 2003.

[29] S. L. Wu, Y. C. Tseng, and J. P. Sheu, “Intelligent medium access control

for mobile ad hoc networks with busy tones and power control,” IEEE

J. Select. Areas Commun., vol. 18, no. 9, pp. 1647–1657, Sep. 2000.

[30] Y. Xu, J. Heidemann, and D. Estrin, “Geography-informed energy con-

servation for ad hoc routing,” in Proc. 7th Annu. ACM/IEEE Int. Conf.

Mobile Computing and Networking (MobiCom), 2001, pp. 70–84.

[31] E. W. Zegura, K. Calvert, and S. Bhattacharjee, “How to model an inter-

network,” in Proc. IEEE INFOCOM, vol. 2, 1996, pp. 594–602.

Li (Erran) Li (M’99) received the B.E. degree in au-

tomatic control from Beijing Polytechnic University,

China, in 1993, the M.E. degree in pattern recognition

from the Institute of Automation, Chinese Academy

of Sciences, Beijing, in 1996, and the Ph.D. degree

in computer science from Cornell University, Ithaca,

NY, in 2001, where Joseph Y. Halpern was his ad-

visor.

During his graduate study at Cornell University, he

worked at Microsoft Research and Bell Labs Lucent

as an intern, and at AT&T Research Center at ICSI

Berkeley as a visiting student. He is presently a member of the Networking Re-

search Center, Bell Labs, Holmdel, NJ. His research interests are in networking

with a focus on wireless networking and mobile computing. He has been a

member of ACM since 1999.

Joseph Y. Halpern (SM’00) received the B.Sc. de-

gree in mathematics from the University of Toronto,

Canada, in 1975 and the Ph.D. degree in mathematics

from Harvard University in 1981.

He spent two years as the head of the Mathematics

Department at Bawku Secondary School in Ghana.

He is currently a Professor of computer science at

Cornell University, Ithaca, NY, where he has been

since 1996. He has coauthored six patents, two books

(Reasoning About Knowledge and Reasoning About

Uncertainty), and over 100 journal publications and

100 conference publications. He is a former editor-in-chief of the Journal of the

ACM.

Together with his former student, Y. Moses, he pioneered the approach of ap-

plying reasoning about knowledge to analyzing distributed protocols and multi-

agent systems; he won a Gödel Prize for this work. He received the Publishers’

Prize for Best Paper at the International Joint Conference on Artiﬁcial Intelli-

gence in 1985 (joint with R. Fagin) and in 1989. He has been a Fellow of the

ACM since 2002.

Paramvir Bahl (SM’97) received the Ph.D. degree

in computer systems engineering from the University

of Massachusetts, Amherst.

He is a Senior Researcher and the Manager

of the Networking Group in Microsoft Research.

His research interests span a variety of problems

in wireless networking including low-power RF

communications; ubiquitous wireless Internet access

and services; location determination techniques and

services; self-organizing, self-managing multi-hop

community mesh networks; and real-time audio-vi-

sual communications. He has authored over 65 scientiﬁc papers, 44 issued and

pending patent applications, and book chapters in these areas.

Dr. Bahl is the founder and Chairman of the ACM Special Interest Group

in Mobility (SIGMOBILE); the founder and past Editor-in-Chief of the ACM

Mobile Computing and Communications Review, and the founder and Steering

Committee Chair of ACM/USENIX Mobile Systems Conference (MobiSys).

He has served on the editorial board of the IEEE J

OURNAL ON SELECTED AREAS

COMMUNICATIONS, and is currently serving on the editorial boards of El-

sevier’s Ad hoc Networking Journal, Kluwer’s Telecommunications Systems

Journal, and ACM’s Wireless Networking Journal. He has served as a guest

editor for several IEEE and ACM journals and on networking panels and work-

shops organized by the National Science Foundation (NSF), the National Re-

search Council (NRC) and European Union’s COST. He has served as the Gen-

eral Chairman, Program Chair and Steering Committee member of several IEEE

and ACM conferences and on the Technical Program Committee of over 40 in-

ternational conferences and workshops. He is the recipient of Digital’s Doctoral

Engineering Award (1994) and the ACM SIGMOBILE’s Distinguished Service

Award (2001). He has been a Fellow of the ACM since 2003.

Yi-Min Wang received the B.S. degree from the

Department of Electrical Engineering at National

Taiwan University in 1986, and the Ph.D. degree

from the Department of Electrical and Computer

Engineering, University of Illinois at Urbana-Cham-

paign, in 1993, where he received the Robert T.

Chien Memorial Award from the Graduate College

for excellence in research.

From 1993 to 1997, he was with AT&T Bell Labs

and worked primarily in the area of checkpointing

and rollback recovery, both in theory and practice.

Since he joined Microsoft Research in 1998, he has expanded his research ef-

forts into distributed systems and home networking. He is currently a Senior

Researcher in the Systems and Networking group, leading an R&D effort in

systems management and diagnostics.

Roger Wattenhofer received the Ph.D. degree in

computer science from ETH Zurich, Switzerland, in

1998.

From 1999 to 2001, he was ﬁrst with Brown

University, Providence, RI, then with Microsoft Re-

search, Redmond, WA. Currently, he is an Assistant

Professor at ETH Zurich. His research interests in-

clude a variety of algorithmic aspects in networking

and distributed computing, in particular, peer-to-peer

computing and ad hoc networks.

Dr. Wattenhofer has been a member of the ACM

since 1999.