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
Share
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
10.1109/TVT.2011.2162086
Neither Shortest Path Nor Dominating Set: Aggregation Scheduling by Greedy Growing Tree in Multihop Wireless Sensor Networks
C. Tian (2011)
10.1016/j.comnet.2013.09.007
MC-MLAS: Multi-channel Minimum Latency Aggregation Scheduling in Wireless Sensor Networks
Fatemeh Ghods (2013)
10.1016/j.comcom.2004.12.025
Energy-efficient coverage problems in wireless ad-hoc sensor networks
M. Cardei (2006)
10.1109/TMC.2011.22
Fast Data Collection in Tree-Based Wireless Sensor Networks
Özlem Durmaz Incel (2012)
10.1109/TPDS.2010.80
A Delay-Efficient Algorithm for Data Aggregation in Multihop Wireless Sensor Networks
XiaoHua Xu (2011)
10.1109/CSNDSP.2016.7574007
Convergecast scheduling problem in case of given aggregation tree: The complexity status and some special cases
Adil I. Erzin (2016)
10.1007/978-3-319-69404-7_4
Solution of the Convergecast Scheduling Problem on a Square Unit Grid When the Transmission Range is 2
Adil I. Erzin (2017)
10.1007/978-0-387-35608-2_11
Symmetric Connectivity with Minimum Power Consumption in Radio Networks
G. Calinescu (2002)
10.1016/j.adhoc.2011.01.003
Near optimal scheduling of data aggregation in wireless sensor networks
Pei Wang (2013)
10.1109/MC.2004.1266294
Energy-efficient area monitoring for sensor networks
J. Carle (2004)
10.1007/s11276-010-0282-y
Aggregation convergecast scheduling in wireless sensor networks
B. Malhotra (2011)
10.3390/s90402446
Energy-efficient Area Coverage by Sensors with Adjustable Ranges
Vyacheslav V. Zalyubovskiy (2009)
10.1007/11599463_14
Minimum Data Aggregation Time Problem in Wireless Sensor Networks
Xujin Chen (2005)
10.1016/j.cor.2016.05.010
Variable neighborhood search variants for Min-power symmetric connectivity problem
Adil I. Erzin (2017)
10.1007/978-3-662-46018-4_10
Minimum Latency Aggregation Scheduling in Wireless Sensor Networks
J. Gagnon (2014)



Semantic Scholar Logo Some data provided by SemanticScholar