{"title":"Aggregation Scheduling Algorithms in Wireless Sensor Networks","authors":"Min Kyung An","volume":125,"journal":"International Journal of Computer and Information Engineering","pagesStart":562,"pagesEnd":571,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/10007096","abstract":"In Wireless Sensor Networks which consist of tiny
\r\nwireless sensor nodes with limited battery power, one of the most
\r\nfundamental applications is data aggregation which collects nearby
\r\nenvironmental conditions and aggregates the data to a designated
\r\ndestination, called a sink node. Important issues concerning the
\r\ndata aggregation are time efficiency and energy consumption due
\r\nto its limited energy, and therefore, the related problem, named
\r\nMinimum Latency Aggregation Scheduling (MLAS), has been the
\r\nfocus of many researchers. Its objective is to compute the minimum
\r\nlatency schedule, that is, to compute a schedule with the minimum
\r\nnumber of timeslots, such that the sink node can receive the
\r\naggregated data from all the other nodes without any collision or
\r\ninterference. For the problem, the two interference models, the graph
\r\nmodel and the more realistic physical interference model known as
\r\nSignal-to-Interference-Noise-Ratio (SINR), have been adopted with
\r\ndifferent power models, uniform-power and non-uniform power (with
\r\npower control or without power control), and different antenna
\r\nmodels, omni-directional antenna and directional antenna models.
\r\nIn this survey article, as the problem has proven to be NP-hard,
\r\nwe present and compare several state-of-the-art approximation
\r\nalgorithms in various models on the basis of latency as its
\r\nperformance measure.","references":"[1] S. Roy, Y. C. Hu, D. Peroulis, and X.-Y. Li, \u201cMinimum-Energy\r\nBroadcast Using Practical Directional Antennas in All-Wireless\r\nNetworks,\u201d in INFOCOM, 2006.\r\n[2] P. Gupta and P. R. Kumar, \u201cThe Capacity of Wireless Networks,\u201d IEEE\r\nTransctions on Information Theory, vol. 46, pp. 388 \u2013 404, 2000.\r\n[3] X.-Y. Li, X. Xu, S. Wang, S. Tang, G. Dai, J. Zhao, and Y. Qi,\r\n\u201cEfficient Data Aggregation in Multi-hop Wireless Sensor Networks\r\nunder Physical Interference Model,\u201d in MASS, 2009, pp. 353\u2013362.\r\n[4] X. Chen, X. Hu, and J. Zhu, \u201cMinimum Data Aggregation Time Problem\r\nin Wireless Sensor Networks,\u201d in MSN, 2005, pp. 133\u2013142.\r\n[5] \u2014\u2014, \u201cData Gathering Schedule for Minimal Aggregation Time in\r\nWireless Sensor Networks,\u201d IJDSN, vol. 5, no. 4, pp. 321\u2013337, 2009.\r\n[6] D. Lichtenstein, \u201cPlanar Formulae and Their Uses,\u201d SIAM J. Comput.,\r\nvol. 11, no. 2, pp. 329\u2013343, 1982.\r\n[7] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, \u201cMinimum\r\nData Aggregation Schedule in Wireless Sensor Networks,\u201d IJCA, vol. 18,\r\nno. 4, pp. 254\u2013262, 2011.\r\n[8] C. Lund and M. Yannakakis, \u201cOn the Hardness of Approximating\r\nMinimization Problems,\u201d Journal of the ACM, vol. 41, no. 5, pp. 960 \u2013\r\n981, 1994.\r\n[9] U. Feige, \u201cA Threshold of ln(n) for Approximating Set Cover,\u201d J. ACM,\r\nvol. 45, no. 4, pp. 634\u2013652, 1998.\r\n[10] N. X. Lam, M. K. An, D. T. Huynh, and T. N. Nguyen, \u201cMinimum\r\nLatency Data Aggregation in the Physical Interference Model,\u201d in\r\nMSWiM, 2011, pp. 93\u2013102.\r\n[11] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, \u201cMinimum\r\nLatency Data Aggregation in the Physical Interference Model,\u201d\r\nCOMCOM, vol. 35, no. 18, pp. 2175\u20132186, 2012.\r\n[12] R. Karp, \u201cReducibility among Combinatorial Problems,\u201d in Complexity\r\nof Computer Computations. Plenum Press, 1972, pp. 85\u2013103.\r\n[13] N. X. Lam, T. Tran, M. K. An, and D. T. Huynh, \u201cA Note on the\r\nComplexity of Minimum Latency Data Aggregation Scheduling with\r\nUniform Power in Physical Interference Model,\u201d Theoretical Computer\r\nScience, vol. 569, pp. 70\u201373, 2015.\r\n[14] C. H. Papadimitriou and M. Yannakakis, \u201cOptimization, Approximation,\r\nand Complexity Classes,\u201d J. Comput. System Sci., vol. 43, no. 3, pp.\r\n425\u2013440, 1991.\r\n[15] S. C. H. Huang, P.-J. Wan, C. T. Vu, Y. Li, and F. Yao, \u201cNearly Constant\r\nApproximation for Data Aggregation Scheduling,\u201d in INFOCOM, 2007,\r\npp. 6\u201312.\r\n[16] B. Yu, J. Li, and Y. Li, \u201cDistributed Data Aggregation Scheduling in\r\nWireless Sensor Networks,\u201d in INFOCOM, 2009, pp. 2159\u20132167.\r\n[17] X. Xu, S. Wang, X. Mao, S. Tang, P. Xu, and X.-Y. Li, \u201cEfficient\r\nData Aggregation in Multi-hop WSNs,\u201d in GLOBECOM, 2009, pp.\r\n3916\u20133921.\r\n[18] P.-J. Wan, S. C.-H. Huang, L. Wang, Z. Wan, and X. Jia,\r\n\u201cMinimum-Latency Aggregation Scheduling in Multihop Wireless\r\nNetworks,\u201d in MOBIHOC, 2009, pp. 185\u2013194.\r\n[19] X. Xu, X. Y. Li, X. Mao, S. Tang, and S. Wang, \u201cA Delay-Efficient\r\nAlgorithm for Data Aggregation in Multihop Wireless Sensor\r\nNetworks,\u201d IEEE Transactions on Parallel and Distributed Systems,\r\nvol. 22, pp. 163\u2013175, 2011.\r\n[20] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, \u201cMinimum\r\nLatency Aggregation Scheduling in Interference-Aware 3-Dimensional\r\nWSNs,\u201d in ICWN, 2013.\r\n[21] T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson, Introduction\r\nto Algorithms, 3rd ed. McGraw-Hill Higher Education, 2009.\r\n[22] P.-J. Wan, K. Alzoubi, and O. Frieder, \u201cDistributed Construction\r\nof Connected Dominating Set in Wireless Ad Hoc Networks,\u201d in\r\nINFOCOM, 2002, pp. 159\u20131604.\r\n[23] H. Li, Q. S. Hua, C. Wu, and F. C. M. Lau, \u201cMinimum-Latency\r\nAggregation Scheduling in Wireless Sensor Networks under Physical\r\nInterference Model,\u201d in MSWiM, 2010, pp. 360\u2013367.\r\n[24] N. X. Lam, M. K. An, D. T. Huynh, and T. N. Nguyen, \u201cScheduling\r\nProblems in Interference-Aware Wireless Sensor Networks,\u201d in ICNC,\r\n2013, pp. 783\u2013789.\r\n[25] V. Annamalai, S. K. S. Gupta, and L. Schwiebert, \u201cOn Tree-based\r\nConvergecasting in Wireless Sensor Networks,\u201d in WCNC, 2003, pp.\r\n1942\u20131947.\r\n[26] H. Du, X. Hu, and X. Jia, \u201cEnergy Efficient Routing and Scheduling\r\nfor Real-time Data Aggregation In WSN,\u201d COMCOM, vol. 29, no. 17,\r\npp. 3527\u20133535, 2006.\r\n[27] S. Khuller, B. Raghavachari, and N. E. Young, \u201cBalancing Minimum\r\nSpanning Trees and Shortest-Path Trees,\u201d Algorithmica, vol. 14, no. 4,\r\npp. 305\u2013321, 1995.\r\n[28] H. Yousefi, M. Malekimajd, M. Ashouri, and A. Movaghar, \u201cFast\r\nAggregation Scheduling in Wireless Sensor Networks,\u201d IEEE Trans.\r\nWireless Communications, vol. 14, no. 6, pp. 3402\u20133414, 2015.\r\n[29] A. Kesselman and D. R. Kowalski, \u201cFast Distributed Algorithm for\r\nConvergecast in Ad Hoc Geometric Radio Networks,\u201d Journal of\r\nParallel and Distributed Computing, vol. 66, no. 4, pp. 578\u2013585, 2006.\r\n[30] N. Hobbs, Y. Wang, Q.-S. Hua, D. Yu, and F. C. M. Lau, \u201cDeterministic\r\nDistributed Data Aggregation under the SINR Model,\u201d in TAMC, 2012,\r\npp. 385\u2013399. [31] H. Li, C. Wu, Q.-S. Hua, and F. C. Lau, \u201cLatency-minimizing Data\r\nAggregation in Wireless Sensor Networks under Physical Interference\r\nModel,\u201d Ad Hoc Networks, vol. 12, pp. 52\u201368, 2014.\r\n[32] M. M. Halld\u00b4orsson and P. Mitra, \u201cWireless Connectivity and Capacity,\u201d\r\nin SODA, 2012, pp. 516\u2013526.\r\n[33] H. Liu, Z. Liu, D. Li, X. Lu, and H. Du, \u201cApproximation Algorithms\r\nfor Minimum Latency Data Aggregation in Wireless Sensor Networks\r\nwith Directional Antenna,\u201d Theor. Comput. Sci., vol. 497, pp. 139\u2013153,\r\n2013.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 125, 2017"}