Online citations, reference lists, and bibliographies.

The Accuracy Of One Polynomial Algorithm For The Convergecast Scheduling Problem On A Square Grid With Rectangular Obstacles

Adil I. Erzin, Roman V. Plotnikov
Published 2018 · Computer Science

Cite This
Download PDF
Analyze on Scholarcy
In the Convergecast Scheduling Problem, it is required to find in the communication graph an oriented spanning aggregation tree with a root in a base station and the arcs oriented to the root and to build a conflict-free min-length schedule for aggregating data along the arcs of the aggregation tree. This problem is NP-hard in general, however, if the communication graph is a unit square grid in each node of which there is a sensor and in which a data packet is transmitted along any edge during a one-time slot, the problem is polynomially solvable. In this paper, we consider a communication graph in the form of a square grid with rectangular obstacles impenetrable by the messages. In our previous paper, we proposed a polynomial algorithm for constructing a feasible schedule and intensive numerical experiment allowed us to make a hypothesis that the algorithm constructs an optimal solution. In this paper, we present a counterexample and prove that the proposed algorithm constructs a schedule of length at most one time round longer than the optimal schedule.
This paper references
Neither Shortest Path Nor Dominating Set: Aggregation Scheduling by Greedy Growing Tree in Multihop Wireless Sensor Networks
C. Tian (2011)
MC-MLAS: Multi-channel Minimum Latency Aggregation Scheduling in Wireless Sensor Networks
Fatemeh Ghods (2013)
Energy-efficient coverage problems in wireless ad-hoc sensor networks
M. Cardei (2006)
Fast Data Collection in Tree-Based Wireless Sensor Networks
Özlem Durmaz Incel (2012)
A Delay-Efficient Algorithm for Data Aggregation in Multihop Wireless Sensor Networks
XiaoHua Xu (2011)
Convergecast scheduling problem in case of given aggregation tree: The complexity status and some special cases
Adil I. Erzin (2016)
Solution of the Convergecast Scheduling Problem on a Square Unit Grid When the Transmission Range is 2
Adil I. Erzin (2017)
Symmetric Connectivity with Minimum Power Consumption in Radio Networks
G. Calinescu (2002)
Near optimal scheduling of data aggregation in wireless sensor networks
Pei Wang (2013)
Energy-efficient area monitoring for sensor networks
J. Carle (2004)
Aggregation convergecast scheduling in wireless sensor networks
B. Malhotra (2011)
Energy-efficient Area Coverage by Sensors with Adjustable Ranges
Vyacheslav V. Zalyubovskiy (2009)
Minimum Data Aggregation Time Problem in Wireless Sensor Networks
Xujin Chen (2005)
Variable neighborhood search variants for Min-power symmetric connectivity problem
Adil I. Erzin (2017)
Minimum Latency Aggregation Scheduling in Wireless Sensor Networks
J. Gagnon (2014)

Semantic Scholar Logo Some data provided by SemanticScholar