NDLI: Information exchange with collision detection on multiple channels

Content Provider	Springer Nature Link
Author	Wang, Yuepeng Wang, Yuexuan Yu, Dongxiao Yu, Jiguo Lau, Francis C. M.
Copyright Year	2014
Abstract	Information exchange is a fundamental communication primitive in radio networks. We study this problem in multi-channel single-hop networks. In particular, given $$k$$ pieces of information, initially stored in $$k$$ nodes respectively, the task is to broadcast these information pieces to the entire network via a set of $$\mathcal {F}$$ channels. We develop efficient distributed algorithms for this task for the scenario where both the identities and the number $$k$$ of the initial information holders are unknown to the participating nodes. Assuming nodes with collision detection, we present an efficient randomized algorithm for unrestricted information exchange, where multiple information items can be combined into a single message. The algorithm disseminates all the information items within $$O(\frac{k}{\mathcal {F}}+\mathcal {F}\log ^2n)$$ timeslots with high probability. To the best of our knowledge, this is the first algorithm that breaks the $$\varOmega (k)$$ lower bound for unrestricted information exchange if only a single channel is available. This result establishes the superiority of multiple channels for the task of unrestricted information exchange. Moreover, for restricted information exchange, where each message can carry only one information item, we devise a randomized algorithm that completes the task in $$O(k+\frac{\log ^2n}{\mathcal {F}}+\log n)$$ timeslots. When $$k$$ is large, both algorithms are asymptotically optimal, as they can reach the trivial lower bounds of $$\varOmega (\frac{k}{\mathcal {F}})$$ and $$\varOmega (k)$$ for unrestricted and restricted information exchange, respectively.
Starting Page	118
Ending Page	135
Page Count	18
File Format	PDF
ISSN	13826905
Journal	Journal of Combinatorial Optimization
Volume Number	31
Issue Number	1
e-ISSN	15732886
Language	English
Publisher	Springer US
Publisher Date	2014-02-23
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Wireless network Multiple channels Information exchange Distributed algorithm Randomized algorithm Combinatorics Convex and Discrete Geometry Mathematical Modeling and Industrial Mathematics Theory of Computation Optimization Operation Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Control and Optimization Discrete Mathematics and Combinatorics Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bounded information dissemination in multi-channel wireless networks

Distributed wireless link scheduling in the SINR model

$$(\alpha , \tau )$$ -Monitoring for event detection in wireless sensor networks

An improved distributed data aggregation scheduling in wireless sensor networks

OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks

Coverage by directional sensors in randomly deployed wireless sensor networks

Improved approximation algorithms for single-tiered relay placement

A novel approach for detecting multiple rumor sources in networks with partial observations

An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models

Information exchange with collision detection on multiple channels

Similar Documents

Bounded information dissemination in multi-channel wireless networks

Distributed wireless link scheduling in the SINR model

$$(\alpha , \tau )$$ -Monitoring for event detection in wireless sensor networks

An improved distributed data aggregation scheduling in wireless sensor networks

OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks

Coverage by directional sensors in randomly deployed wireless sensor networks

Improved approximation algorithms for single-tiered relay placement

A novel approach for detecting multiple rumor sources in networks with partial observations

An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models

Information exchange with collision detection on multiple channels