NDLI: Energy-efficient randomized routing in radio networks

Please wait, while we are loading the content...

On-line algorithms for the channel assignment problem in cellular networks (extended abstract)

Worst-case analysis of a dynamic channel assignment strategy (extended abstract)

Efficient use of radio spectrum in wireless networks with channel separation between close stations

Blocking probability estimates in a partitioned sector TDMA system

Energy-efficient randomized routing in radio networks

Data structures for mobile data (invited talk) (abstract only)

Mobile facility location (extended abstract)

Clustering algorithms for wireless ad hoc networks

The post-PC era: it's about the services-enabled new Internet

Dynamic session management for static and mobile users: a competitive on-line algorithmic approach

Efficient memoryless protocol for tag identification (extended abstract)

Application of a theory of simulation to models of mobile communication systems (invited talk) (abstract only)

A decision-theoretic approach to resource allocation in wireless multimedia networks

Leader election algorithms for mobile ad hoc networks

Energy-efficient randomized routing in radio networks

Content Provider	ACM Digital Library
Author	Olariu, Stephan Nakano, Koji
Abstract	The main contribution of this work is to present an energy-efficient routing protocol for single-channel, single-hop radio networks (RN, for short). Such networks are usually deployed in support of special events including search-and-rescue, disaster relief, law enforcement, and collaborative computing, among many others. An RN is typically populated by hand-held, commodity devices, running on batteries. Since recharging batteries may not be possible while on mission, we are interested in designing protocols that are highly energy-efficient. One of the most effective energy-saving strategies is to mandate individual stations to go to sleep whenever they are not transmitting or recieving messages. Consequently, we are interested in protocols that allow stations to power off their transceiver to the largest extent possible.Suppose that station S(i), (1 ≤ i ≤ p), of the RN stores si items. Each item has a unique destination which is the identity of the station to which the item must be routed. The routing problem asks to route all the items to their destinations, while expending as little energy as possible. Since, in the worst case, each item must be transmitted at least once, every routing protocol must take at least n = s1 + s2 ··· sp time slots to terminate. Similarly, each station S(i), (1 ≤ i ≤ p), must be awake for at least si + di time slots, where di denotes the number of items destined for S(i). It is well known that a station is expending power while its transceiver is active that is, while transmitting or receiving a packet. It is perhaps surprising at first that a station expends power even if it receives a packet that is not destined for it. Since in single-hop radio networks every station is within transmission range from every other station, the design of energy-efficient protocols is highly nontrivial! An additional complication stems from the inherent asymmetry of the routing problem: no destination knows the identity of the sender, precluding à priori arrangements between senders and receivers.We show that for every ƒ ≥ 1, the task of routing n items can be completed, with probability exceeding 1 - 1/ƒ, in n + O(q + ln ƒ) time slots and that no station S(i), (1 ≤ i ≤ p), has to be awake for more than si + di + O(qi + ri log p + log ƒ) time slots, where qi is the number of stations that have items destined for S(i), q = q1 + q2 + ··· + qp, and ri is the number of stations for which S(i) has items. Since qi ≤ di, ri ≤ si, and q ≤ n our protocol is close to optimal.
Starting Page	35
Ending Page	44
Page Count	10
File Format	PDF
ISBN	1581133014
DOI	10.1145/345848.345856
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2000-08-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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