A message complexity oriented design of distributed algorithm for long-lived multicasting in wireless sensor networks

Xiaofei Liu; Song Guo; Abdulmotaleb El Saddik

doi:10.1109/ICCCN.2008.ECP.145

A message complexity oriented design of distributed algorithm for long-lived multicasting in wireless sensor networks

Xiaofei Liu
, Song Guo
, Abdulmotaleb El Saddik

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

Abstract

We consider an optimization problem in wireless sensor networks (WSNs) that is to find a multicast tree rooted at the source node and including all the destination nodes such that the lifetime of the tree is maximized. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, we show that its high message complexity may prevent such contribution from being practically used in resource-constrained WSNs. In this paper, we proposed a new distributed suboptimal algorithm that achieves a good balance on the algorithm-optimality and message complexity. In particular, we prove that it has a linear-message complexity. The tradeoff between algorithm sub-optimality and message complexity is also studied by simulations.

Original language	English
Title of host publication	2008 Proceedings of 17th International Conference on Computer Communications and Networks, ICCCN 2008
Pages	771-776
Number of pages	6
DOIs	https://doi.org/10.1109/ICCCN.2008.ECP.145
Publication status	Published - 26 Dec 2008
Externally published	Yes
Event	17th International Conference on Computer Communications and Networks, ICCCN 2008 - St. Thomas, Virgin Islands, U.S. Duration: 3 Aug 2008 → 7 Aug 2008

Conference

Conference	17th International Conference on Computer Communications and Networks, ICCCN 2008
Country/Territory	Virgin Islands, U.S.
City	St. Thomas
Period	3/08/08 → 7/08/08

Keywords

Communication complexity
Distributed algorithm
Energy efficiency
Multicasting
Wireless sensor network

ASJC Scopus subject areas

Computer Networks and Communications
Hardware and Architecture
Software

More information

10.1109/ICCCN.2008.ECP.145

Cite this

@inproceedings{295978c6b8a74a2cbd4b5921cf29442b,

title = "A message complexity oriented design of distributed algorithm for long-lived multicasting in wireless sensor networks",

abstract = "We consider an optimization problem in wireless sensor networks (WSNs) that is to find a multicast tree rooted at the source node and including all the destination nodes such that the lifetime of the tree is maximized. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, we show that its high message complexity may prevent such contribution from being practically used in resource-constrained WSNs. In this paper, we proposed a new distributed suboptimal algorithm that achieves a good balance on the algorithm-optimality and message complexity. In particular, we prove that it has a linear-message complexity. The tradeoff between algorithm sub-optimality and message complexity is also studied by simulations.",

keywords = "Communication complexity, Distributed algorithm, Energy efficiency, Multicasting, Wireless sensor network",

author = "Xiaofei Liu and Song Guo and Saddik, \{Abdulmotaleb El\}",

year = "2008",

month = dec,

day = "26",

doi = "10.1109/ICCCN.2008.ECP.145",

language = "English",

isbn = "9781424423903",

pages = "771--776",

booktitle = "2008 Proceedings of 17th International Conference on Computer Communications and Networks, ICCCN 2008",

note = "17th International Conference on Computer Communications and Networks, ICCCN 2008 ; Conference date: 03-08-2008 Through 07-08-2008",

}

Liu, X, Guo, S & Saddik, AE 2008, A message complexity oriented design of distributed algorithm for long-lived multicasting in wireless sensor networks. in 2008 Proceedings of 17th International Conference on Computer Communications and Networks, ICCCN 2008., 4674305, pp. 771-776, 17th International Conference on Computer Communications and Networks, ICCCN 2008, St. Thomas, Virgin Islands, U.S., 3/08/08. https://doi.org/10.1109/ICCCN.2008.ECP.145

A message complexity oriented design of distributed algorithm for long-lived multicasting in wireless sensor networks. / Liu, Xiaofei; Guo, Song; Saddik, Abdulmotaleb El.
2008 Proceedings of 17th International Conference on Computer Communications and Networks, ICCCN 2008. 2008. p. 771-776 4674305.

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

TY - GEN

T1 - A message complexity oriented design of distributed algorithm for long-lived multicasting in wireless sensor networks

AU - Liu, Xiaofei

AU - Guo, Song

AU - Saddik, Abdulmotaleb El

PY - 2008/12/26

Y1 - 2008/12/26

N2 - We consider an optimization problem in wireless sensor networks (WSNs) that is to find a multicast tree rooted at the source node and including all the destination nodes such that the lifetime of the tree is maximized. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, we show that its high message complexity may prevent such contribution from being practically used in resource-constrained WSNs. In this paper, we proposed a new distributed suboptimal algorithm that achieves a good balance on the algorithm-optimality and message complexity. In particular, we prove that it has a linear-message complexity. The tradeoff between algorithm sub-optimality and message complexity is also studied by simulations.

AB - We consider an optimization problem in wireless sensor networks (WSNs) that is to find a multicast tree rooted at the source node and including all the destination nodes such that the lifetime of the tree is maximized. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, we show that its high message complexity may prevent such contribution from being practically used in resource-constrained WSNs. In this paper, we proposed a new distributed suboptimal algorithm that achieves a good balance on the algorithm-optimality and message complexity. In particular, we prove that it has a linear-message complexity. The tradeoff between algorithm sub-optimality and message complexity is also studied by simulations.

KW - Communication complexity

KW - Distributed algorithm

KW - Energy efficiency

KW - Multicasting

KW - Wireless sensor network

UR - https://www.scopus.com/pages/publications/57849157846

U2 - 10.1109/ICCCN.2008.ECP.145

DO - 10.1109/ICCCN.2008.ECP.145

M3 - Conference article published in proceeding or book

SN - 9781424423903

SP - 771

EP - 776

BT - 2008 Proceedings of 17th International Conference on Computer Communications and Networks, ICCCN 2008

T2 - 17th International Conference on Computer Communications and Networks, ICCCN 2008

Y2 - 3 August 2008 through 7 August 2008

ER -

A message complexity oriented design of distributed algorithm for long-lived multicasting in wireless sensor networks

Abstract

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this