Toward resource-optimal averaging consensus over the wireless medium

Matthew Nokleby, Waheed Uz Zaman Bajwa, Robert Calderbank, Behnaam Aazhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We carry out a comprehensive study of the resource costs of distributed averaging consensus in wireless sensor networks. In particular, we consider two metrics appropriate to the wireless medium: total transmit energy and time-bandwidth product. Most previous approaches, such as gossip algorithms, suppose a graphical network, which abstracts away crucial features of the wireless medium, and measure resource consumption only in terms of the total number of transmissions required to achieve consensus. Under a path-loss dominated protocol interference model, we study the performance of several popular gossip algorithms, showing that they are nearly order-optimal with respect to transmit energy but strictly sub-optimal with respect to time-bandwidth product. We also propose a new scheme, termed hierarchical averaging, which is tailored to the wireless medium, and show that in general this approach is nearly order-optimal with respect to time-bandwidth product but strictly sub-optimal with respect to transmit energy. For the special case of free-space propagation, however, the proposed hierarchical scheme is approximately order-optimal with respect to both metrics.

Original languageEnglish (US)
Title of host publicationConference Record of the 46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012
Pages1197-1201
Number of pages5
DOIs
StatePublished - Dec 1 2012
Event46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012 - Pacific Grove, CA, United States
Duration: Nov 4 2012Nov 7 2012

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers

Other

Other46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012
CountryUnited States
CityPacific Grove, CA
Period11/4/1211/7/12

Fingerprint

Bandwidth
Wireless sensor networks
Network protocols
Costs

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Networks and Communications

Cite this

Nokleby, M., Bajwa, W. U. Z., Calderbank, R., & Aazhang, B. (2012). Toward resource-optimal averaging consensus over the wireless medium. In Conference Record of the 46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012 (pp. 1197-1201). [6489211] (Conference Record - Asilomar Conference on Signals, Systems and Computers). https://doi.org/10.1109/ACSSC.2012.6489211
Nokleby, Matthew ; Bajwa, Waheed Uz Zaman ; Calderbank, Robert ; Aazhang, Behnaam. / Toward resource-optimal averaging consensus over the wireless medium. Conference Record of the 46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012. 2012. pp. 1197-1201 (Conference Record - Asilomar Conference on Signals, Systems and Computers).
@inproceedings{93f1e00b712d4a4fa95fde2f4540db02,
title = "Toward resource-optimal averaging consensus over the wireless medium",
abstract = "We carry out a comprehensive study of the resource costs of distributed averaging consensus in wireless sensor networks. In particular, we consider two metrics appropriate to the wireless medium: total transmit energy and time-bandwidth product. Most previous approaches, such as gossip algorithms, suppose a graphical network, which abstracts away crucial features of the wireless medium, and measure resource consumption only in terms of the total number of transmissions required to achieve consensus. Under a path-loss dominated protocol interference model, we study the performance of several popular gossip algorithms, showing that they are nearly order-optimal with respect to transmit energy but strictly sub-optimal with respect to time-bandwidth product. We also propose a new scheme, termed hierarchical averaging, which is tailored to the wireless medium, and show that in general this approach is nearly order-optimal with respect to time-bandwidth product but strictly sub-optimal with respect to transmit energy. For the special case of free-space propagation, however, the proposed hierarchical scheme is approximately order-optimal with respect to both metrics.",
author = "Matthew Nokleby and Bajwa, {Waheed Uz Zaman} and Robert Calderbank and Behnaam Aazhang",
year = "2012",
month = "12",
day = "1",
doi = "https://doi.org/10.1109/ACSSC.2012.6489211",
language = "English (US)",
isbn = "9781467350518",
series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",
pages = "1197--1201",
booktitle = "Conference Record of the 46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012",

}

Nokleby, M, Bajwa, WUZ, Calderbank, R & Aazhang, B 2012, Toward resource-optimal averaging consensus over the wireless medium. in Conference Record of the 46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012., 6489211, Conference Record - Asilomar Conference on Signals, Systems and Computers, pp. 1197-1201, 46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012, Pacific Grove, CA, United States, 11/4/12. https://doi.org/10.1109/ACSSC.2012.6489211

Toward resource-optimal averaging consensus over the wireless medium. / Nokleby, Matthew; Bajwa, Waheed Uz Zaman; Calderbank, Robert; Aazhang, Behnaam.

Conference Record of the 46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012. 2012. p. 1197-1201 6489211 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Toward resource-optimal averaging consensus over the wireless medium

AU - Nokleby, Matthew

AU - Bajwa, Waheed Uz Zaman

AU - Calderbank, Robert

AU - Aazhang, Behnaam

PY - 2012/12/1

Y1 - 2012/12/1

N2 - We carry out a comprehensive study of the resource costs of distributed averaging consensus in wireless sensor networks. In particular, we consider two metrics appropriate to the wireless medium: total transmit energy and time-bandwidth product. Most previous approaches, such as gossip algorithms, suppose a graphical network, which abstracts away crucial features of the wireless medium, and measure resource consumption only in terms of the total number of transmissions required to achieve consensus. Under a path-loss dominated protocol interference model, we study the performance of several popular gossip algorithms, showing that they are nearly order-optimal with respect to transmit energy but strictly sub-optimal with respect to time-bandwidth product. We also propose a new scheme, termed hierarchical averaging, which is tailored to the wireless medium, and show that in general this approach is nearly order-optimal with respect to time-bandwidth product but strictly sub-optimal with respect to transmit energy. For the special case of free-space propagation, however, the proposed hierarchical scheme is approximately order-optimal with respect to both metrics.

AB - We carry out a comprehensive study of the resource costs of distributed averaging consensus in wireless sensor networks. In particular, we consider two metrics appropriate to the wireless medium: total transmit energy and time-bandwidth product. Most previous approaches, such as gossip algorithms, suppose a graphical network, which abstracts away crucial features of the wireless medium, and measure resource consumption only in terms of the total number of transmissions required to achieve consensus. Under a path-loss dominated protocol interference model, we study the performance of several popular gossip algorithms, showing that they are nearly order-optimal with respect to transmit energy but strictly sub-optimal with respect to time-bandwidth product. We also propose a new scheme, termed hierarchical averaging, which is tailored to the wireless medium, and show that in general this approach is nearly order-optimal with respect to time-bandwidth product but strictly sub-optimal with respect to transmit energy. For the special case of free-space propagation, however, the proposed hierarchical scheme is approximately order-optimal with respect to both metrics.

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

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

U2 - https://doi.org/10.1109/ACSSC.2012.6489211

DO - https://doi.org/10.1109/ACSSC.2012.6489211

M3 - Conference contribution

SN - 9781467350518

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 1197

EP - 1201

BT - Conference Record of the 46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012

ER -

Nokleby M, Bajwa WUZ, Calderbank R, Aazhang B. Toward resource-optimal averaging consensus over the wireless medium. In Conference Record of the 46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012. 2012. p. 1197-1201. 6489211. (Conference Record - Asilomar Conference on Signals, Systems and Computers). https://doi.org/10.1109/ACSSC.2012.6489211