research-article

Broadcast routing based on new link cost model for ad-hoc networks

Authors:

Hwang-Cheng WangAuthors Info & Claims

PE-WASUN '08: Proceedings of the 5th ACM symposium on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks

Pages 27 - 32

https://doi.org/10.1145/1454609.1454616

Published: 27 October 2008 Publication History

Abstract

For many wireless applications such as group conference and digital audio/video broadcast, it is necessary to send data to all devices that form an ad-hoc network. In this paper, minimum cost broadcast routing (MCBR) and minimum cost broadcast routing with forbidden set (MCBRF) are proposed. We first formulate a new cost model for the underlying graph by considering the distance between nodes, the remaining battery energy, and battery discharge pattern at each node. A minimum cost broadcast routing (MCBR) based on minimum cost graph spanning is described. Then forbidden set is introduced into MCBR to obtain MCBRF. The performance of the algorithms is investigated through simulations and contrasted against several other routing methods. A set of performance metrics are defined. The results on a variety of topologies of different sizes indicate that the spanning tree constructed by MCBRF algorithm has more leaf nodes than BIP and MMLE. Although the broadcast trees constructed by MWIS and MCDS have more leaf nodes, they suffer serious drawbacks in terms of energy consumption. Also, MCBR and MCBRF generate spanning trees that select nodes with higher remaining battery capacity as relay nodes. Thus more robust broadcast routes are established.

References

[1]

L. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc, "Power consumption in packet radio networks," Proc. 14th Symp. on Theoretical Computer Science (STACS 97), pp. 363--374, 1997.

Digital Library

[2]

J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, "On the construction of energy-efficient broadcast and multicast trees in wireless networks," Proc. IEEE INFOCOM, pp. 585--594, 2000.

[3]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed., MIT Press and McGraw-Hill, 2001.

Digital Library

[4]

X. Y. Cheng, J. H. Sun, M. K. Min, and D. Z. Du, "Energy-efficient broadcast and multicast routing in ad-hoc wireless networks," Proc. IEEE International Conf. on Performance, Computing, and Communications, pp. 87--94, 2003.

[5]

W. Wang and B. H. Soong, "Collision-free and low-latency scheduling algorithm for broadcast operation in wireless ad-hoc networks," IEEE Communications Letters, pp. 793--795, October 2007.

[6]

S. Sakai, M. Togasaki, and K. Yamazaki, "A note on greedy algorithm for the maximum weighted independent set problem," Discrete Applied Mathematics, vol. 126, no. 2-3, pp. 313--322, 2003.

Digital Library

[7]

S. M. Banik and S. Radhakrishnan, "Minimizing broadcast latency in ad-hoc wireless networks," Proc. 45th Annual Southeast Regional Conference, pp. 533--534, 2007.

Digital Library

[8]

W. Lou and J. Wu, "On reducing broadcast redundancy in ad hoc wireless networks," Proc. 36th Hawaii International Conf. on System Sciences, pp. 305--314, 2003.

Digital Library

[9]

D. B. West, Introduction to Graph Theory, Prentice Hall, 2000.

[10]

J. L. Gross and J. Yellen, Handbook of Graph Theory, CRC, 2003.

[11]

S. Singh and M. Woo, "Power-aware routing in mobile ad-hoc networks," Proc. 4th annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 181--190, 1998.

Digital Library

[12]

L. Campelli, M. Cesana, and R. Fracchia, "Directional broadcast forwarding of alarm messages in VANETs," Fourth Annual Conf. on Wireless on Demand Network Systems and Services, pp. 72--79, Jan 24-26, 2007.

[13]

O. Tonguz, N. Wisitpongphan, F. Bait, P. Mudaliget, and V. Sadekart, "Broadcasting in VANET," 2007 Mobile Networking for Vehicular Environments, pp. 7--12, May 11-11, 2007.

[14]

S. Gold, "A PSPICE macromodel for lithiumion batteries," Proc. Twelfth Annual Battery Conf. on Applications and Advances, pp. 215--222, 1997.

[15]

H. C. Wang and W. H. Chen, "Maximum path lifetime routing for ad-hoc wireless networks," Proc. IFIP/IEEE MWCN2007, pp. 166--170, Cork, Ireland, September 19-21, 2007.

[16]

H. C. Wang and Y. H. Wang, "Energy-efficient routing algorithms for wireless ad-hoc networks", Proc. 18th IEEE PIMRC, Athens, Greece, Sept. 2-6, 2007.

[17]

C. K. Yen, "Restricted independent domination problems on graphs," International Journal of Computer Systems Science & Engineering, vol. 23, no. 4, pp. 23--29, 2008.

[18]

X. Z. Zhang, "Efficient broadcast scheduling based on fuzzy clustering and Hopfield network for ad-hoc networks," Proc. International Conf. on Machine Learning and Cybernetics, vol. 6, pp. 3255--3260, 2007.

[19]

G. Tan, S. A. Jarvis, J. W. J. Xue, and S. D. Hammond, "Distributed broadcast scheduling in mobile ad-hoc networks with unknown topologies," Proc. IEEE International Symp. on Parallel and Distributed Processing, pp. 1--7, 2007.

[20]

C. H. Yen, Broadcast Routing Algorithm Based on Minimum Cost Spanning Tree for Ad-Hoc Networks, Master Thesis, Dept. of Electronic Engineering, National Ilan University, July, 2008.

[21]

J. Chang and L. Tassiulas, "Maximum Lifetime Routing in Wireless Sensor Networks," IEEE/ACM Trans. on Networking, vol. 12, no. 4, pp. 609--619, Aug. 2004

Digital Library

Cited By

Xia Li Li Qilong Zou Jian Zhang Qianyu (2010)A state-aware routing protocol based on energy and stability for mobile Ad Hoc networks2010 Second International Conference on Communication Systems, Networks and Applications10.1109/ICCSNA.2010.5588734(329-332)Online publication date: Jun-2010
https://doi.org/10.1109/ICCSNA.2010.5588734

Index Terms

Broadcast routing based on new link cost model for ad-hoc networks

Recommendations

Minimum Cost Broadcast Routing with Forbidden Set for Ad-Hoc Networks
CMC '09: Proceedings of the 2009 WRI International Conference on Communications and Mobile Computing - Volume 02

In many wireless applications, it is necessary for one device in an ad-hoc network to send data to all the other devices. In this paper, broadcast routing algorithms that aim to minimize the cost of the routing path are proposed. A new cost model is ...
Energy efficient broadcast routing in mobile ad hoc networks: Research Articles

In this paper, we address the problem of broadcast routing in mobile ad hoc networks from the viewpoint of energy efficiency. In an ad hoc wireless network, each node runs on a local energy source which has a limited energy lifespan. Thus, energy ...
EZRP: an enhanced zone-based routing protocol for ad-hoc networks: Research Articles
Performance Analysis and Enhancements of Wireless Networks

In mobile ad-hoc networks (MANETs), the nodes intercommunicate through single-hop and multi-hop paths in a peer-to-peer fashion. Intermediate nodes between two pairs of communication nodes act as routers. Thus, the nodes operate both as hosts and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PE-WASUN '08: Proceedings of the 5th ACM symposium on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks

October 2008

110 pages

ISBN:9781605582368

DOI:10.1145/1454609

Program Chairs:
Luciano Bononi
University of Bologna, Italy
,
Isabelle Guerin Lassous
University Lyon I / LIP, France

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MSWiM '08

Sponsor:

MSWiM '08: The 11th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems

October 27 - 28, 2008

British Columbia, Vancouver, Canada

Acceptance Rates

PE-WASUN '08 Paper Acceptance Rate 16 of 42 submissions, 38%;

Overall Acceptance Rate 70 of 240 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
237
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xia Li Li Qilong Zou Jian Zhang Qianyu (2010)A state-aware routing protocol based on energy and stability for mobile Ad Hoc networks2010 Second International Conference on Communication Systems, Networks and Applications10.1109/ICCSNA.2010.5588734(329-332)Online publication date: Jun-2010
https://doi.org/10.1109/ICCSNA.2010.5588734

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents