We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Towards a queueing-based framework for in-network function computation.
- Authors
Banerjee, Siddhartha; Gupta, Piyush; Shakkottai, Sanjay
- Abstract
We seek to develop network algorithms for function computation in sensor networks. Specifically, we want dynamic joint aggregation, routing, and scheduling algorithms that have analytically provable performance benefits due to in-network computation as compared to simple data forwarding. To this end, we define a class of functions, the Fully-Multiplexible functions, which includes several functions such as parity, MAX, and kth-order statistics. For such functions we characterize the maximum achievable refresh rate of the network in terms of an underlying graph primitive, the min-mincut. In acyclic wireline networks we show that the maximum refresh rate is achievable by a simple algorithm that is dynamic, distributed, and only dependent on local information. In the case of wireless networks we provide a MaxWeight-like algorithm with dynamic flow-splitting, which is shown to be throughput-optimal.
- Subjects
ALGORITHMS; SENSOR networks; QUEUING theory; DATA transmission systems; COMPUTER scheduling; ROUTING (Computer network management)
- Publication
Queueing Systems, 2012, Vol 72, Issue 3/4, p219
- ISSN
0257-0130
- Publication type
Article
- DOI
10.1007/s11134-012-9296-8