More Web Proxy on the site http://driver.im/

research-article

Cross-sender bit-mixing coding

Authors:

Steffen Bondorf,

Jonathan Scarlett,

Yuda ZhaoAuthors Info & Claims

IPSN '19: Proceedings of the 18th International Conference on Information Processing in Sensor Networks

Pages 205 - 216

https://doi.org/10.1145/3302506.3310401

Published: 16 April 2019 Publication History

Abstract

Scheduling to avoid packet collisions is a long-standing challenge in networking, and has become even trickier in wireless networks with multiple senders and multiple receivers. In fact, researchers have proved that even perfect scheduling can only achieve R = O(1/lnN). Here N is the number of nodes in the network, and R is the medium utilization rate.

Ideally, one would hope to achieve R = Θ(1), while avoiding all the complexities in scheduling. To this end, this paper proposes cross-sender bit-mixing coding (BMC), which does not rely on scheduling. Instead, users transmit simultaneously on suitably-chosen slots, and the amount of overlap in different user's slots is controlled via coding. We prove that in all possible network topologies, using BMC enables us to achieve R = Θ(1). We also prove that the space and time complexities of BMC encoding/decoding are all low-order polynomials.

References

[1]

M. Aldridge, L. Baldassini, and O. Johnson. 2014. Group testing algorithms: bounds and simulations. IEEE Transactions on Information Theory 60, 6 (2014), 3671--3687.

[2]

G. Atia and V. Saligrama. 2012. Boolean Compressed Sensing and Noisy Group Testing. IEEE Transactions on Information Theory 58, 3 (2012).

Digital Library

[3]

A. Barg and A. Mazumdar. 2017. Group Testing Schemes From Codes and Designs. IEEE Transactions on Information Theory 63, 11 (2017), 7131--7141.

[4]

T. Berger, N. Mehravari, D. Towsley, and J. Wolf. 1984. Random Multiple-Access Communication and Group Testing. IEEE Transactions on Communications 32, 7 (1984), 769--779.

[5]

Steffen Bondorf, Binbin Chen, Jonathan Scarlett, Haifeng Yu, and Yuda Zhao. 2018. Cross-Sender Bit-Mixing Coding. Arxiv preprint, arXiv:1807.04449.

Digital Library

[6]

A. De Bonis and U. Vaccaro. 2017. ε-Almost Selectors and Their Applications to Multiple-Access Communication. IEEE Transactions on Information Theory 63, 11 (2017), 7304--7319.

[7]

T. Bui, M. Kuribayashi, and I. Echizen. 2017. Non-Adaptive Group Testing Framework based on Concatenation Code. Arxiv preprint, arXiv:1701.06989v3.

[8]

T. Bui, O. Nguyen, V. Dang, N. Nguyen, and T. Nguyen. 2013. A Variant of Non-Adaptive Group Testing and Its Application in Pay-Television via Internet. In Information and Communication Technology - EurAsia Conference.

Digital Library

[9]

S. Cai, M. Jahangoshahi, M. Bakshi, and S. Jaggi. 2017. Efficient Algorithms for Noisy Group Testing. IEEE Transactions on Information Theory 63, 4 (2017), 2113--2136.

Digital Library

[10]

Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, and Muriel Médard. 2012. Bounded-contention coding for wireless networks in the high SNR regime. In DISC.

Digital Library

[11]

K. Censor-Hillel, E. Kantor, N. Lynch, and M. Parter. 2015. Computing in Additive Networks with Bounded-Information Codes. In DISC.

Digital Library

[12]

C. Chan, S. Jaggi, V. Saligrama, and S. Agnihotri. 2014. Non-adaptive group testing: Explicit bounds and novel algorithms. IEEE Transactions on Information Theory 60, 5 (2014).

[13]

M. Cheraghchi. 2013. Noise-resilient group testing: limitations and constructions. Discrete Applied Mathematics 161, 1 (2013), 81--95.

Digital Library

[14]

M. Cheraghchi, A. Hormati, A. Karbasi, and M. Vetterli. 2009. Compressed sensing with probabilistic measurements: a group testing solution. In Allerton Conference on Communication, Control, and Computing.

Digital Library

[15]

M. Cheraghchi, A. Hormati, A. Karbasi, and M. Vetterli. 2011. Group testing with probabilistic tests: theory, design and application. IEEE Transactions on Information Theory 57, 10 (2011), 7057--7067.

Digital Library

[16]

Manjunath Doddavenkatappa, Mun Choon Chan, and Ben Leong. 2013. Splash: Fast Data Dissemination with Constructive Interference in Wireless Sensor Networks. In NSDI.

Digital Library

[17]

D. Du and F. Hwang. 1999. Combinatorial Group Testing and Its Applications. Vol. 2. Singapore: World Scientific Publishing Company.

[18]

Wan Du, Jansen Christian Liando, Huanle Zhang, and Mo Li. 2015. When Pipelines Meet Fountain: Fast Data Dissemination in Wireless Sensor Networks. In ACM SenSys.

Digital Library

[19]

F. Ferrari, M. Zimmerling, L. Thiele, and O. Saukh. 2011. Efficient network flooding and time synchronization with Glossy. In IPSN.

[20]

Simon Foucart and Holger Rauhut. 2013. A Mathematical Introduction to Compressive Sensing. Birkhauser.

Digital Library

[21]

Mohsen Ghaffari, Bernhard Haeupler, Nancy Lynch, and Calvin Newport. 2012. Bounds on Contention Management in Radio Networks. In International Symposium on Distributed Computing. (Also see full verison as Arxiv preprint, arXiv:1206.0154v2).

Digital Library

[22]

A. Gilbert, B. Hemenway, A. Rudra, M. Strauss, and M. Wootters. 2012. Recovering simple signals. In Information Theory and Applications Workshop.

[23]

A. Gilbert, M. Iwen, and M. Strauss. 2008. Group testing and sparse signal recovery. In Asilomar Conference on Signals, Systems and Computers.

[24]

Shyamnath Gollakota and Dina Katabi. 2008. Zigzag decoding: combating hidden terminals in wireless networks. SIGCOMM Computer Communication Review 38, 4 (2008), 159--170.

Digital Library

[25]

Piyush Gupta and P. R. Kumar. 2000. The Capacity of Wireless Networks. IEEE Transactions on Information Theory 46, 2 (2000), 388--404.

Digital Library

[26]

Carsten Herrmann, Fabian Mager, and Marco Zimmerling. 2018. Mixer: Efficient Many-to-All Broadcast in Dynamic Wireless Mesh Networks. In ACM SenSys.

Digital Library

[27]

H. Inan, P. Kairouz, and A. Ozgur. 2017. Sparse group testing codes for low-energy massive random access. In Allerton Conference on Communication, Control, and Computing.

[28]

P. Indyk, H. Ngo, and A. Rudra. 2010. Efficiently decodable non-adaptive group testing. In ACM-SIAM Symposium on Discrete Algorithms.

Digital Library

[29]

W. Kautz and R. Singleton. 1964. Nonrandom binary superimposed codes. IEEE Transactions on Information Theory 10 (1964), 363--377.

Digital Library

[30]

J. Komlos and A. Greenberg. 1985. An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Transactions on Information Theory 31, 2 (1985), 302--306.

Digital Library

[31]

Olaf Landsiedel, Federico Ferrari, and Marco Zimmerling. 2013. Chaos: Versatile and Efficient All-to-All Data Sharing and In-Network Processing at Scale. In ACM SenSys.

Digital Library

[32]

K. Lee, R. Pedarsani, and K. Ramchandran. 2016. SAFFRON: a fast, efficient, and robust framework for group testing based on sparse-graph codes. In IEEE International Symposium on Information Theory.

[33]

Tianji Li, Mi Kyung Han, Apurv Bhartia, Lili Qiu, Eric Rozner, Yin Zhang, and Brad Zarikoff. 2011. CRMA: collision-resistant multiple access. In MobiCom.

Digital Library

[34]

Shu Lin and Daniel J. Costello. 2004. Error Control Coding. Prentice-Hall, Inc.

[35]

A. Macula. 1997. Error-correcting nonadaptive group testing with d<sup>e</sup>-disjunct matrices. Discrete Applied Mathematics 80, 2-3 (1997), 217--222.

Digital Library

[36]

Arya Mazumdar. 2012. On Almost Disjunct Matrices for Group Testing. In International Symposium on Algorithms and Computation.

[37]

Arya Mazumdar. 2016. Nonadaptive Group Testing With Random Set of Defectives. IEEE Transactions on Information Theory 62, 12 (2016), 7522--7531.

Digital Library

[38]

A. Mazumdar and S. Mohajer. 2014. Group testing with unreliable elements. In Allerton Conference on Communication, Control, and Computing.

[39]

Mobashir Mohammad and Mun Choon Chan. 2018. Codecast: Supporting Data Driven In-Network Processing for Low-Power Wireless Sensor Networks. In IPSN.

Digital Library

[40]

I. Newman. 1991. Private vs. common random bits in communication complexity. Inform. Process. Lett. 39, 2 (July 1991), 67--71.

Digital Library

[41]

H. Ngo, E. Porat, and A. Rudra. 2011. Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications. In ICALP.

Digital Library

[42]

S. Olariu and M. Weigle. 2009. Vehicular Networks: From Theory to Practice. Chapman and Hall/CRC.

[43]

E. Porat and A. Rothschild. 2011. Explicit Nonadaptive Combinatorial Group Testing Schemes. IEEE Transactions on Information Theory 57, 12 (2011), 7982--7989.

Digital Library

[44]

A. Sebő. 1985. On two random search problems. Journal of Statistical Planning and Inference 11 (1985), 23--31.

[45]

Felix Sutton, Bernhard Buchli, Jan Beutel, and Lothar Thiele. 2015. Zippy: On-Demand Network Flooding. In ACM SenSys.

Digital Library

[46]

D. Taipale and M. Seo. 1994. An efficient soft-decision Reed-Solomon decoding algorithm. IEEE Transactions on Information Theory 40, 4 (1994), 1130--1139.

Digital Library

[47]

Fouad Tobagi and Leonard Kleinrock. 1975. Packet switching in radio channels: part II-the hidden terminal problem in carrier sense multiple-access and the busy-tone solution. IEEE Transactions on communications 23, 12 (1975), 1417--1433.

[48]

A. Vem, N. Janakiraman, and K. Narayanan. 2017. Group Testing using left-and-right-regular sparse-graph codes. Arxiv preprint, arXiv:1701.07477v1.

[49]

Mythili Vutukuru, Kyle Jamieson, and Hari Balakrishnan. 2008. Harnessing Exposed Terminals in Wireless Networks. In NSDI.

Digital Library

[50]

J. Wolf. 1985. Born again group testing: multiaccess communications. IEEE Transactions on Information Theory 31, 2 (1985), 185--191.

Digital Library

[51]

Kai Xing, Xiuzhen Cheng, Liran Ma, and Qilian Liang. 2007. Superimposed code based channel assignment in multi-radio multi-channel wireless mesh networks. In MobiCom.

Digital Library

[52]

Jun Zheng and Abbas Jamalipour. 2008. Wireless Sensor Networks: A Networking Perspective. John Wiley & Sons.

Digital Library

[53]

Yuanqing Zheng and Mo Li. 2014. Towards More Efficient Cardinality Estimation for Large-Scale RFID Systems. IEEE Transactions on Networking 22, 6 (2014).

Digital Library

[54]

A. Zhigljavsky. 2003. Probabilistic existence theorems in group testing. Journal of Statistical Planning and Inference 115 (2003), 1--43. Issue 1.

Cited By

Oostvogels JMichiels SHughes D(2022)One-Take: Gathering Distributed Sensor Data Through Dominant Symbols for Fast Classification2022 21st ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN)10.1109/IPSN54338.2022.00034(337-349)Online publication date: May-2022
https://doi.org/10.1109/IPSN54338.2022.00034

Index Terms

Cross-sender bit-mixing coding
1. Mathematics of computing
  1. Information theory
    1. Coding theory
2. Networks
  1. Network protocols
    1. Network protocol design

Recommendations

Distributed MAC Protocol Supporting Physical-Layer Network Coding

Physical-layer network coding (PNC) is a promising approach for wireless networks. It allows nodes to transmit simultaneously. Due to the difficulties of scheduling simultaneous transmissions, existing works on PNC are based on simplified medium access ...
A cross-layer protocol for exploiting cooperative diversity in multi-hop wireless ad hoc networks

Cooperative communication has emerged to reap the benefits of spatial diversity. To fully exploit cooperative diversity, we propose a medium access control and routing enabled cross-layer cooperative transmission (MACR-CCT) protocol for improving the ...
Saturation throughput analysis of error-prone 802.11 wireless networks: Research Articles
RRM for Next-Generation Wireless and Mobile Communication Systems

It is well known that the medium access control (MAC) layer is the main bottleneck for the IEEE 802.11 wireless LANs. Much work has been done on performance analysis of the 802.11 MAC. However, most of them assume that the wireless channel is error ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IPSN '19: Proceedings of the 18th International Conference on Information Processing in Sensor Networks

April 2019

365 pages

ISBN:9781450362849

DOI:10.1145/3302506

General Chair:
Rasit Eskicioglu
University of Manitoba, Canada
,
Program Chairs:
Luca Mottola
Politecnico di Milano, Italy
,
Bodhi Priyantha
Microsoft Research

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems

In-Cooperation

IEEE-SPS: Signal Processing Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 April 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National University of Singapore
National Research Foundation Singapore
Ministry of Education - Singapore

Conference

IPSN '19

Sponsor:

SIGBED

IPSN '19: The 18th International Conference on Information Processing in Sensor Networks

April 16 - 18, 2019

Quebec, Montreal, Canada

Acceptance Rates

IPSN '19 Paper Acceptance Rate 25 of 91 submissions, 27%;

Overall Acceptance Rate 143 of 593 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
114
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Oostvogels JMichiels SHughes D(2022)One-Take: Gathering Distributed Sensor Data Through Dominant Symbols for Fast Classification2022 21st ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN)10.1109/IPSN54338.2022.00034(337-349)Online publication date: May-2022
https://doi.org/10.1109/IPSN54338.2022.00034

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents