Maximizing aggregated revenue in sensor networks under deadline constraints
Authors:
- 1 December 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01912216,p. 4846-4851
Abstract
We study the problem of maximizing the aggregated revenue in sensor networks with deadline constraints. Our model is that of a sensor network that is arranged in the form of a tree topology, where the root corresponds to the sink node, and the rest of the network detects an event and transmits data to the sink over one or more hops. We assume a time-slotted synchronized system and a node-exclusive (also called a primary) interference model. We formulate this problem as an integer optimization problem and show that the optimal solution involves solving a Bipartite Maximum Weighted Matching problem at each hop. We propose a polynomial time algorithm based on dynamic programming that uses only local information at each hop to obtain the optimal solution. Thus, we answer the question of when a node should stop waiting to aggregate data from its predecessors and start transmitting in order to maximize revenue within a deadline imposed by the sink. Further, we show that our optimization framework is general enough that it can be extended to a number of interesting cases such as incorporating sleep-wake scheduling, minimizing aggregate sensing error, etc.Keywords
This publication has 9 references indexed in Scilit:
- On the Construction of a Maximum-Lifetime Data Gathering Tree in Sensor Networks: NP-Completeness and Approximation Algorithm2008
- Optimal Policies for Distributed Data Aggregation in Wireless Sensor Networks2007
- Latency Constrained Aggregation in Sensor NetworksLecture Notes in Computer Science, 2006
- Data-aggregation techniques in sensor networks: A surveyIEEE Communications Surveys & Tutorials, 2006
- Computing and communicating functions over sensor networksIEEE Journal on Selected Areas in Communications, 2005
- Aggregation in sensor networks: an energy-accuracy trade-off2003
- The impact of data aggregation in wireless sensor networks2003
- Aggregation tree construction in sensor networks2003
- Fine-grained network time synchronization using reference broadcasts2002