We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
TIGHT ANALYSIS OF SHORTEST PATH CONVERGECAST IN WIRELESS SENSOR NETWORKS.
- Authors
AUGUSTINE, JOHN; HAN, QI; LODEN, PHILIP; LODHA, SACHIN; ROY, SASANKA
- Abstract
We consider the convergecast problem in wireless sensor networks where each sensor has a reading that must reach a designated sink. Since a sensor reading can usually be encoded in a few bytes, more than one reading can readily fit into a standard transmission packet. We assume that each packet hop consumes one unit of energy. Our objective is to minimize the total energy consumed to send all readings to the sink. We show that this problem is NP-hard even when all readings are of fixed size. We then study a class SPEP of distributed algorithms that is completely defined by two properties. Firstly, the packets hop along some shortest path to the sink. Secondly, the nodes use an elementary packing algorithm to pack readings into packets. Our main technical contribution is a lower bound. We show that no algorithm for UCCP that either follows the shortest path or packs in an elementary manner is a (2 -- e)-approximation, for any fixed e > 0. To complement this, we show that SPEP algo-rithms are (2 -- 3/2k)-approximation for UCCP and 3-approximation for CCP, where k ≥ 2 is the number of readings that can fit within a packet. We conclude with some special cases and experimental observations.
- Subjects
WIRELESS sensor networks; DATA packeting; INFORMATION technology; ENERGY consumption; ALGORITHMS; APPROXIMATION theory; EXPERIMENTAL design
- Publication
International Journal of Foundations of Computer Science, 2013, Vol 24, Issue 1, p31
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054113400030