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

DOI10.1007/S11134-012-9296-8zbMATH Open1273.68068arXiv1105.5651OpenAlexW2568789534MaRDI QIDQ373447FDOQ373447

Authors: Siddhartha Banerjee, Piyush Gupta, Sanjay Shakkottai 

Publication date: 22 October 2013

Published in: Queueing Systems (Search for Journal in Brave)

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 k th -order statistics. For such functions we exactly 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.

Full work available at URL: https://arxiv.org/abs/1105.5651

Recommendations

• Lower bounds for in-network computation of arbitrary functions
• Function computation in wireless sensor networks
• Fast Distributed Algorithms for Computing Separable Functions
• Computing separable functions via gossip
• Distributed Symmetric Function Computation in Noisy Wireless Sensor Networks

zbMATH Keywords

wireless sensor networksdynamic routing and scheduling algorithmsin-network function computation

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Network protocols (68M12)

Cites Work

• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• The capacity of wireless networks
• Maximizing queueing network utility subject to stability: greedy primal-dual algorithm
• Resource Allocation and Cross-Layer Control in Wireless Networks
• Coding for computing
• SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATES
• Network Coding for Computing: Cut-Set Bounds
• Distributed Random Access Algorithm: Scheduling and Congestion Control
• Optimal resource allocation for multicast sessions in multi-hop wireless networks

Cited In (2)

• Function computation in wireless sensor networks
• Lower bounds for in-network computation of arbitrary functions

Uses Software

• TAG

This page was built for publication: Towards a queueing-based framework for in-network function computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q373447)