Towards a queueing‐based framework for in‐network function computation

Towards a queueing‐based framework for in‐network function computation

0.00 Avg rating0 Votes
Article ID: iaor20126419
Volume: 72
Issue: 3
Start Page Number: 219
End Page Number: 250
Publication Date: Dec 2012
Journal: Queueing Systems
Authors: , ,
Keywords: networks
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.

Reviews

Required fields are marked *. Your email address will not be published.