We consider the convergecast problem in wireless sensor networks where readings generated by each sensor node are to reach the 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 any such packet consumes one unit of energy every time it hops from a node to a neighbor regardless of the total size of the readings in it. Our objective is to minimize the total energy consumed to send all the readings to the sink. Consequently, we ask the question: can we pack the readings in common routes to minimize the number of hops? It is quite elementary to see that this problem is NP-hard when the size of the readings are arbitrary via reductions from bin packing or set partition.
We study the simple version with readings normalized to 1 byte in length. However, we make no
assumptions on the underlying graph. We show this
to be NP-hard by way of a reduction from Set Cover.
We 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, given all the readings that enter into a node,
it sends out as many fully packed packets as possible
followed by at most one partial packet — the elementary packing property. We show that any algorithm
in this class is (2− 3 )-approximate where k ≥ 2 is the 2k
size of a data packet in bytes. We additionally show that this class is optimal when the underlying sensor network is a tree or grid topology. Our main technical contribution is a lower bound. We show that no algorithm that either follows the shortest path or packs in an elementary manner is a (2 − ε)-approximation, for any fixed ε > 0. |
| Cite as: Augustine, J., Han, Q., Loden, P., Lodha, S. and Roy, S. (2011). Tight Analysis of Shortest Path Convergecast in Wireless Sensor Networks. In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 31-40 |
 (from crpit.com)
(local if available)
|