NDLI: An Efficient Randomized Routing Protocol for Single-Hop Radio Networks

Content Provider	IEEE Xplore Digital Library
Author	Rajasekaran, S. Sharma, D. Ammar, R. Lownes, N.
Copyright Year	2010
Abstract	In this paper we study the important problems of message routing, sorting, and selection in a radio network. A radio network consists of stations where each station is a hand-held device. We consider a single-hop radio network. In a single-hop network it is assumed that each station is within the transmission range of every other station. Let RN(p; k) stand for a single-hop network that has p stations and k communication channels. The problems of sorting and selection have been studied on RN(p; k). For these problems it is assumed that there are n/p elements to start with at each station. At the end of sorting, the least n/p elements should be in the first station, the next smallest n/p elements should be in the second station, and so on. The best known prior algorithm for sorting takes 4n/k +o(n/k) broadcast rounds on a RN(p; k). In this paper we present a randomized algorithm that takes only 3n/k +o(n/k) broadcast rounds with high probability. For the selection problem, it is known that the maximum or minimum element can be found in O(log n) rounds on a RN(n; 1), provided broadcast conflicts can be resolved in O(1) time. The problem of general selection has not been addressed. In this paper we present a randomized selection algorithm that takes O(p/k) rounds on a RN(p; k) with high probability. An important message routing problem that is considered in the literature is one where there are n/p packets originating from each station and there are n/p packets destined for each station. The best known routing algorithms take nearly 2n/k times slots. An important open question has been if there exist algorithms that take only close to n/k time slots. Note that a trivial lower bound for routing is n/k. The existence of such algorithms will be highly relevant especially in emergencies and time critical situations. In this paper we answer this question by presenting a randomized algorithm that takes nearly n/k time slots with high probability.
Starting Page	160
Ending Page	167
File Size	322766
Page Count	8
File Format	PDF
ISBN	9781424479139
ISSN	01903918
DOI	10.1109/ICPP.2010.25
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-09-13
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing Radio network Sorting Communication channels Routing protocols Nickel Computational modeling
Content Type	Text
Resource Type	Article

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

An energy-efficient permutation routing protocol for single-hop radio networks

Energy-Efficient Multi-hop Hierarchical Routing Protocol for Wireless Sensor Networks

Energy Efficient and Cluster Based Routing Protocol for WSN

Spectrum Aware Routing for Multi-Hop Cognitive Radio Networks with a Single Transceiver

Communication-Efficient Anonymous Routing Protocol for Wireless Sensor Networks Using Single Path Tree Topology

A simulation study of multi-hop wireless network

An Energy-Efficient Routing Protocol for Wireless Sensor Networks

An efficient routing protocol to increase the communication reliability of multi-hop cellular networks

Spectrum-aware Cluster-based routing protocol for multiple-hop cognitive wireless network

An Efficient Randomized Routing Protocol for Single-Hop Radio Networks

Similar Documents

An energy-efficient permutation routing protocol for single-hop radio networks

Energy-Efficient Multi-hop Hierarchical Routing Protocol for Wireless Sensor Networks

Energy Efficient and Cluster Based Routing Protocol for WSN

Spectrum Aware Routing for Multi-Hop Cognitive Radio Networks with a Single Transceiver

Communication-Efficient Anonymous Routing Protocol for Wireless Sensor Networks Using Single Path Tree Topology

A simulation study of multi-hop wireless network

An Energy-Efficient Routing Protocol for Wireless Sensor Networks

An efficient routing protocol to increase the communication reliability of multi-hop cellular networks

Spectrum-aware Cluster-based routing protocol for multiple-hop cognitive wireless network

An Efficient Randomized Routing Protocol for Single-Hop Radio Networks