Improving Scalability for Longest-lived Multicast Using Localized Operations in WANETs

TitleImproving Scalability for Longest-lived Multicast Using Localized Operations in WANETs
Publication TypeConference Paper
Year of Publication2007
AuthorsGuo, S., O. Yang, and V. C. M. Leung
Conference NameSensor, Mesh and Ad Hoc Communications and Networks, 2007. SECon '07. 4th Annual IEEE Communications Society Conference on
Pagination243 -252
Date Publishedjun.
Keywordsdistributed algorithms, graph theory, max-tree max-min- cut theorem, minimax techniques, multicast communication, multicast lifetime, optimization problem, static resource-constrained multihop wireless networks, trees (mathematics), WANET scalability, wide area networks

We consider the problem of maximizing the multicast lifetime in multihop wireless networks in which each node has limited energy, bandwidth memory, and computation capabilities. We explore some important properties of this optimization problem from a graph theory perspective and obtain a min-max-tree max-min- cut theorem, which connects some important while separated results in recent literature together under the same philosophy. We also apply the theorem to derive our algorithms and localized operations that can construct a global optimal maximum lifetime multicast tree for a static resource-constrained (e.g. memory and computation capability) wireless multihop network. The distributed algorithms have low complexity for both memory and computation requirements at each node. Our localized operations allow our distributed algorithms with expected linear communication complexity. To our best knowledge, this is the first contribution that possesses all the desirable properties of distributed, localized, and scalable for the maximum-lifetime multicast problem, and is especially beneficial to the large-scale resource-limited wireless multihop networks, like sensor networks.


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

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