Localized Broadcasting with Guaranteed Delivery and Bounded Transmission Redundancy

TitleLocalized Broadcasting with Guaranteed Delivery and Bounded Transmission Redundancy
Publication TypeJournal Article
Year of Publication2008
AuthorsKhabbazian, M., and V. K. Bhargava
JournalComputers, IEEE Transactions on
Volume57
Pagination1072 -1086
Date Publishedaug.
ISSN0018-9340
Keywordsad hoc networks, approximation algorithm, bandwidth allocation, bandwidth saving, bounded transmission redundancy, broadcasting, computational complexity, information exchange, localized broadcast algorithm, message complexity, self-pruning algorithm, wireless ad hoc network
Abstract

The common belief is that localized broadcast algorithms are not able to guarantee both full delivery and a good bound on the number of transmissions. In this paper, we propose the first localized broadcast algorithm that guarantees full delivery and a constant approximation ratio to the minimum number of required transmissions in the worst case. The proposed broadcast algorithm is a self-pruning algorithm based on one round of information exchange. Using the proposed algorithm, each node determines its forwarding status in 0(DeltaG logDeltaG), where DeltaG is the maximum node degree of the network. By extending the proposed algorithm, we show that localized broadcast algorithms can achieve both full delivery and a constant approximation ratio to the optimum solution with message complexity O(N), where JV is the total number of nodes in the network and each message contains a constant number of bits. We also show how to save bandwidth by reducing the size of piggybacked information. Finally, we relax several system-model assumptions, or replace them with practical ones, in order to improve the practicality of the proposed broadcast algorithm.

URLhttp://dx.doi.org/10.1109/TC.2008.51
DOI10.1109/TC.2008.51

a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949
Email:

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia