A distributed min-max tree algorithm for maximum-lifetime multicast in resource-limited wireless ad hoc networks

Song Guo; Victor M. Leung

doi:10.1109/SAHCN.2006.288529

A distributed min-max tree algorithm for maximum-lifetime multicast in resource-limited wireless ad hoc networks

Song Guo, Victor M. Leung

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

Abstract

We consider the problem of maximizing the multicast lifetime in multihop wireless networks in which each node is static and has limited energy, bandwidth, memory, and computation capabilities. Unlike most multicast algorithms that use centralized greedy algorithms, our algorithm can construct a global optimal maximum lifetime multicast tree in a distributed manner. It has a low complexity of O(λu) for both memory and computation requirements at each node u, where λu is the degree of node u. The simulation results have shown that it has an expected linear communication complexity under different network sizes and multicast group sizes. This means that our distributed algorithm is also scalable in terms of communication overhead and it is very useful for large-scale energy and bandwidth constrained multihop wireless networks like sensor networks.

Original language	English
Title of host publication	2006 3rd Annual IEEE Communications Society on Sensor and Adhoc Communications and Networks, Secon 2006
Pages	673-677
Number of pages	5
Volume	2
DOIs	https://doi.org/10.1109/SAHCN.2006.288529
Publication status	Published - 1 Dec 2007
Externally published	Yes
Event	2006 3rd Annual IEEE Communications Society on Sensor and Ad hoc Communications and Networks, Secon 2006 - Reston, VA, United States Duration: 25 Sep 2006 → 28 Sep 2006

Conference

Conference	2006 3rd Annual IEEE Communications Society on Sensor and Ad hoc Communications and Networks, Secon 2006
Country	United States
City	Reston, VA
Period	25/09/06 → 28/09/06

Keywords

Distributed algorithm
Maximum-lifetime multicast
Wireless ad hoc networks

ASJC Scopus subject areas

Computer Networks and Communications

More information

10.1109/SAHCN.2006.288529

Scopus Link

Cite this

@inproceedings{f731796e43f44d5d9fcb022f572db027,

title = "A distributed min-max tree algorithm for maximum-lifetime multicast in resource-limited wireless ad hoc networks",

abstract = "We consider the problem of maximizing the multicast lifetime in multihop wireless networks in which each node is static and has limited energy, bandwidth, memory, and computation capabilities. Unlike most multicast algorithms that use centralized greedy algorithms, our algorithm can construct a global optimal maximum lifetime multicast tree in a distributed manner. It has a low complexity of O(λu) for both memory and computation requirements at each node u, where λu is the degree of node u. The simulation results have shown that it has an expected linear communication complexity under different network sizes and multicast group sizes. This means that our distributed algorithm is also scalable in terms of communication overhead and it is very useful for large-scale energy and bandwidth constrained multihop wireless networks like sensor networks.",

keywords = "Distributed algorithm, Maximum-lifetime multicast, Wireless ad hoc networks",

author = "Song Guo and Leung, {Victor M.}",

year = "2007",

month = dec,

day = "1",

doi = "10.1109/SAHCN.2006.288529",

language = "English",

isbn = "1424406269",

volume = "2",

pages = "673--677",

booktitle = "2006 3rd Annual IEEE Communications Society on Sensor and Adhoc Communications and Networks, Secon 2006",

note = "2006 3rd Annual IEEE Communications Society on Sensor and Ad hoc Communications and Networks, Secon 2006 ; Conference date: 25-09-2006 Through 28-09-2006",

}

Guo, S & Leung, VM 2007, A distributed min-max tree algorithm for maximum-lifetime multicast in resource-limited wireless ad hoc networks. in 2006 3rd Annual IEEE Communications Society on Sensor and Adhoc Communications and Networks, Secon 2006. vol. 2, 4068330, pp. 673-677, 2006 3rd Annual IEEE Communications Society on Sensor and Ad hoc Communications and Networks, Secon 2006, Reston, VA, United States, 25/09/06. https://doi.org/10.1109/SAHCN.2006.288529

A distributed min-max tree algorithm for maximum-lifetime multicast in resource-limited wireless ad hoc networks. / Guo, Song; Leung, Victor M.

2006 3rd Annual IEEE Communications Society on Sensor and Adhoc Communications and Networks, Secon 2006. Vol. 2 2007. p. 673-677 4068330.

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - A distributed min-max tree algorithm for maximum-lifetime multicast in resource-limited wireless ad hoc networks

AU - Guo, Song

AU - Leung, Victor M.

PY - 2007/12/1

Y1 - 2007/12/1

N2 - We consider the problem of maximizing the multicast lifetime in multihop wireless networks in which each node is static and has limited energy, bandwidth, memory, and computation capabilities. Unlike most multicast algorithms that use centralized greedy algorithms, our algorithm can construct a global optimal maximum lifetime multicast tree in a distributed manner. It has a low complexity of O(λu) for both memory and computation requirements at each node u, where λu is the degree of node u. The simulation results have shown that it has an expected linear communication complexity under different network sizes and multicast group sizes. This means that our distributed algorithm is also scalable in terms of communication overhead and it is very useful for large-scale energy and bandwidth constrained multihop wireless networks like sensor networks.

AB - We consider the problem of maximizing the multicast lifetime in multihop wireless networks in which each node is static and has limited energy, bandwidth, memory, and computation capabilities. Unlike most multicast algorithms that use centralized greedy algorithms, our algorithm can construct a global optimal maximum lifetime multicast tree in a distributed manner. It has a low complexity of O(λu) for both memory and computation requirements at each node u, where λu is the degree of node u. The simulation results have shown that it has an expected linear communication complexity under different network sizes and multicast group sizes. This means that our distributed algorithm is also scalable in terms of communication overhead and it is very useful for large-scale energy and bandwidth constrained multihop wireless networks like sensor networks.

KW - Distributed algorithm

KW - Maximum-lifetime multicast

KW - Wireless ad hoc networks

UR - http://www.scopus.com/inward/record.url?scp=44049088959&partnerID=8YFLogxK

U2 - 10.1109/SAHCN.2006.288529

DO - 10.1109/SAHCN.2006.288529

M3 - Conference article published in proceeding or book

SN - 1424406269

SN - 9781424406265

VL - 2

SP - 673

EP - 677

BT - 2006 3rd Annual IEEE Communications Society on Sensor and Adhoc Communications and Networks, Secon 2006

T2 - 2006 3rd Annual IEEE Communications Society on Sensor and Ad hoc Communications and Networks, Secon 2006

Y2 - 25 September 2006 through 28 September 2006

ER -