{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:27:09Z","timestamp":1760243229069,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2014,3,17]],"date-time":"2014-03-17T00:00:00Z","timestamp":1395014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We study the scheduling problem for data collection from sensor nodes to the sink node in wireless sensor networks, also referred to as the convergecast problem. The convergecast problem in general network topology has been proven to be NP-hard. In this paper, we propose our heuristic algorithm (finding the minimum scheduling time for convergecast (FMSTC)) for general network topology and evaluate the performance by simulation. The results of the simulation showed that the number of time slots to reach the sink node decreased with an increase in the power. We compared the performance of the proposed algorithm to the optimal time slots in a linear network topology. The proposed algorithm for convergecast in a general network topology has 2.27 times more time slots than that of a linear network topology. To the best of our knowledge, the proposed method is the first attempt to apply the optimal algorithm in a linear network topology to a general network topology.<\/jats:p>","DOI":"10.3390\/a7010145","type":"journal-article","created":{"date-parts":[[2014,3,17]],"date-time":"2014-03-17T12:40:04Z","timestamp":1395060004000},"page":"145-165","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The Minimum Scheduling Time for Convergecast in Wireless Sensor Networks"],"prefix":"10.3390","volume":"7","author":[{"given":"Changyong","family":"Jung","sequence":"first","affiliation":[{"name":"Computer and Information Science, ECPI University, 1001 Omni Blvd., Newport News,  VA 23606, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suk","family":"Lee","sequence":"additional","affiliation":[{"name":"Computer Science Department, Texas A&M University-Texarkana, 7101 University Ave, Texarkana, TX 75503, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay","family":"Bhuse","sequence":"additional","affiliation":[{"name":"Department of Computing, East Tennessee State University, POB 70711, Johnson City, TN 37614, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,3,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Ghosh, A., Incel, O.D., Kumar, V.S.A., and Krishnamachari, B. (2009, January 12\u201315). Multi-Channel Scheduling Algorithms for Fast Aggregated Convergecast in Sensor Networks. Proceedings of the IEEE 6th International Conference on Mobile Adhoc and Sensor Systems, Macau, China.","DOI":"10.1109\/MOBHOC.2009.5336979"},{"key":"ref_2","first-page":"7","article-title":"A survey on scheduling algorithms for wireless sensor networks","volume":"20","author":"Kumar","year":"2011","journal-title":"Int. J. Comput. Appl."},{"key":"ref_3","unstructured":"Choi, H., Yang, S., Kim, Y., and Joo, H. (2011, January 31). On the Scheduling for Convergecast in Power Controlled Wireless Sensor Networks. Proceedings of the IEEE ICCCN Workshop, Arlington, UT, USA."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s11276-007-0050-9","article-title":"Schduling for Information Gathering on Sensor Network","volume":"15","author":"Choi","year":"2009","journal-title":"Wireless Networks"},{"key":"ref_5","unstructured":"Annamalai, V., Gupta, S., and Schwiebert, L. (2003, January 20). On tree-based convergecasting in wireless sensor networks. Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), New Orleans, LA, USA."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Bechkit, W., Koudil, M., Challal, Y., Bouabdallah, A., Souici, B., and Benatchba, K. (,  2012). A New Weighted Shortest Path Tree for Convergecast Traffic Routing in WSN. Proceedings of the 2012 IEEE Symposium on Computers and Communications (ISCC), Washington, DC, USA.","DOI":"10.1109\/ISCC.2012.6249291"},{"key":"ref_7","unstructured":"Gandham, S., Zhang, Y., and Huang, Q. (2006, January 4\u20137). Distributed Minimal Time Convergecast Scheduling in Wireless Sensor Networks. Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, Lisboa, Portugal."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1109\/TMC.2011.22","article-title":"Fast data collection in tree-based wireless sensor networks","volume":"11","author":"Incel","year":"2012","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_9","unstructured":"Li, X., Wang, Y., Wan, P., Song, W., and Feieder, O. (2004, January 7\u201311). Localized Low-Weight Graph and its Application in Wireless Ad Hoc Networks. Proceedings of the IEEE INFOCOM, Chicago, IL, USA."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Peleg, D. (2000). Distributed Computing: A Locality-Sensitive Approach, SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1109\/90.222924","article-title":"Scheduling algorithms for multihop radio networks","volume":"1","author":"Ramanathan","year":"1993","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1007\/s11276-009-0183-0","article-title":"TDMA scheduling algorithms for wireless sensor networks","volume":"16","author":"Sinem","year":"2010","journal-title":"Wirel. Netw."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1016\/j.jpdc.2007.12.006","article-title":"Link scheduling in sensor networks: Distributed edge coloring revisited","volume":"68","author":"Gandham","year":"2008","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_14","unstructured":"Zhang, H., Soldati, P., and Johansson, M. (2009, January 23\u201327). Optimal Link Scheduling and Channel Assignment for Convergecast in Linear Wireless HART Networks. Proceedings of the 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, Seoul, Korea."},{"key":"ref_15","unstructured":"Suh, C., Shin, J., and Lee, J. (2008, January 19\u201321). Fusion Rate Based Spanning Tree. Proceedings of the 11th IEEE Singapore International Conference on Communication Systems, Seoul, Korea."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Tsai, H., and Chen, T. (2008, January 19\u201323). Minimal Time and Conflict-Free Schedule for Convergecast in Wireless Sensor Networks. Proceedings of IEEE International Conference on Communications, Beijing, China.","DOI":"10.1109\/ICC.2008.529"},{"key":"ref_17","unstructured":"Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows-Theory, Algorithms, and Applications, Prentice Hall. Chapter 4."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/s11276-010-0282-y","article-title":"Aggregation convergecast scheduling in wireless sensor networks","volume":"17","author":"Malhortra","year":"2011","journal-title":"Wirel. Netw."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Luo, D., Zhu, X., Wu, X., and Chen, G. (2011, January 10\u201315). Maximizing Lifetime for the Shortest Path Aggregation Tree in Wireless Sensor Networks. Proceedings of the IEEE INFOCOM, Nanjing, China.","DOI":"10.1109\/INFCOM.2011.5934947"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1109\/TMC.2007.250673","article-title":"Variable-range transmission power control in wireless ad hoc networks","volume":"6","author":"Gomez","year":"2007","journal-title":"IEEE Transactions Mob. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1109\/JSAC.2004.837354","article-title":"Principles and protocols for power control in wireless ad hoc networks","volume":"23","author":"Kawadia","year":"2005","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1109\/TWC.2003.819032","article-title":"Joint scheduling and power control for wireless ad hoc networks","volume":"3","author":"ElBatt","year":"2004","journal-title":"IEEE Transactions Wirel. Commun."},{"key":"ref_23","unstructured":"Kesselman, A., and Kowalski, D. (2005, January 19\u201321). Fast Distributed Algorithm for Convergecast in Ad Hoc Geometric Radio Networks. Proceedings of the Second Annual Conference on Wireless on Demand Network Systems and Services (WONS), St. Moritz, Switzerland."},{"key":"ref_24","unstructured":"Huang, Q., and Zhang, Y. (2004, January 16\u201318). Radial Coordination for Convergecast in Wireless Sensor Networks. Proceedings of the 29th Annual IEEE Internaitonal Conference on Local Computer Networks (LCN), Tampa, FL, USA."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Vergados, D.J., Manolaraki, M.-Y., and Vergados, D.D. (2009, January 17\u201320). Evaluation of Broadcast Scheduling Algorithm for Ad-hoc TDMA Networks. Proceedings of the ITAE, Aalborg, Greece.","DOI":"10.1109\/WIRELESSVITAE.2009.5172480"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S1570-8705(03)00015-5","article-title":"Effectiveness of RTS\/CTS handshake in IEEE 802.11 based ad hoc networks","volume":"1","author":"Xu","year":"2003","journal-title":"Ad hoc Networks"},{"key":"ref_27","unstructured":"Zhou, G., He, T., Stankwic, J., and Abdelzaher, T. (2005, January 13\u201317). RID: Radio Interference Detection in Wireless Sensor Network. Proceedings of the INFOCOM, Charlottesville, VA, USA."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1002\/wcm.107","article-title":"Algorithmic, Geometric and graphs issues in wireless networks","volume":"3","author":"Li","year":"2003","journal-title":"J. Wirel. Comm. Mob. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1109\/TPDS.2008.57","article-title":"Distributed algorithms for constructing approximate minimum spanning trees in wireless sensor networks","volume":"20","author":"Khan","year":"2009","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/1\/145\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:09:18Z","timestamp":1760216958000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/1\/145"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,17]]},"references-count":29,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2014,3]]}},"alternative-id":["a7010145"],"URL":"https:\/\/doi.org\/10.3390\/a7010145","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2014,3,17]]}}}