{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:12:02Z","timestamp":1760242322499,"version":"build-2065373602"},"reference-count":34,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2017,4,20]],"date-time":"2017-04-20T00:00:00Z","timestamp":1492646400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>The problem of finding the number and optimal positions of relay nodes for restoring the network connectivity in partitioned Wireless Sensor Networks (WSNs) is Non-deterministic Polynomial-time hard (NP-hard) and thus heuristic methods are preferred to solve it. This paper proposes a novel polynomial time heuristic algorithm, namely, Relay Placement using Space Network Coding (RPSNC), to solve this problem, where Space Network Coding, also called Space Information Flow (SIF), is a new research paradigm that studies network coding in Euclidean space, in which extra relay nodes can be introduced to reduce the cost of communication. Unlike contemporary schemes that are often based on Minimum Spanning Tree (MST), Euclidean Steiner Minimal Tree (ESMT) or a combination of MST with ESMT, RPSNC is a new min-cost multicast space network coding approach that combines Delaunay triangulation and non-uniform partitioning techniques for generating a number of candidate relay nodes, and then linear programming is applied for choosing the optimal relay nodes and computing their connection links with terminals. Subsequently, an equilibrium method is used to refine the locations of the optimal relay nodes, by moving them to balanced positions. RPSNC can adapt to any density distribution of relay nodes and terminals, as well as any density distribution of terminals. The performance and complexity of RPSNC are analyzed and its performance is validated through simulation experiments.<\/jats:p>","DOI":"10.3390\/s17040902","type":"journal-article","created":{"date-parts":[[2017,4,21]],"date-time":"2017-04-21T04:51:46Z","timestamp":1492750306000},"page":"902","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Connectivity Restoration in Wireless Sensor Networks via Space Network Coding"],"prefix":"10.3390","volume":"17","author":[{"given":"Alfred","family":"Uwitonze","sequence":"first","affiliation":[{"name":"School of Electronic Information &amp; Communications, Huazhong University of Science &amp; Technology, 1037 Luoyu Road, Hongshan District, Wuhan 430074, China"}]},{"given":"Jiaqing","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Electronic Information &amp; Communications, Huazhong University of Science &amp; Technology, 1037 Luoyu Road, Hongshan District, Wuhan 430074, China"}]},{"given":"Yuanqing","family":"Ye","sequence":"additional","affiliation":[{"name":"Department of Electrical &amp; Computer Engineering, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA 15213, USA"}]},{"given":"Wenqing","family":"Cheng","sequence":"additional","affiliation":[{"name":"School of Electronic Information &amp; Communications, Huazhong University of Science &amp; Technology, 1037 Luoyu Road, Hongshan District, Wuhan 430074, China"}]}],"member":"1968","published-online":{"date-parts":[[2017,4,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/j.comnet.2013.08.021","article-title":"Topology management techniques for tolerating node failures in wireless sensor networks: A survey","volume":"58","author":"Younis","year":"2014","journal-title":"Comput. Netw."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.comcom.2015.07.022","article-title":"Exploiting skeletonization to restore connectivity in a wireless sensor network","volume":"75","author":"Joshi","year":"2016","journal-title":"Comput. Commun."},{"key":"ref_3","first-page":"1932","article-title":"Relay node placement in structurally damaged wireless sensor networks via triangular Steiner tree approximation","volume":"34","author":"Senel","year":"2011","journal-title":"Comput. Commun."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1109\/JSAC.2010.100611","article-title":"Optimized Relay Placement to Federate Segments in Wireless Sensor Networks","volume":"28","author":"Lee","year":"2010","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","article-title":"Steiner minimal trees","volume":"16","author":"Gilbert","year":"1968","journal-title":"SIAM J. Appl. Math."},{"key":"ref_6","first-page":"457","article-title":"Quadrilateral Steiner tree based connectivity restoration for wireless sensor networks","volume":"37","author":"Chen","year":"2014","journal-title":"Chin. J. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0020-0190(98)00201-4","article-title":"Steiner tree problem with minimum number of Steiner points and bounded edge-length","volume":"69","author":"Lin","year":"1999","journal-title":"Inf. Process. Lett."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s11276-006-0724-8","article-title":"Relay sensor placement in wireless sensor networks","volume":"14","author":"Cheng","year":"2008","journal-title":"Wirel. Netw."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1023\/A:1008384012064","article-title":"Approximations for Steiner trees with minimum number of Steiner points","volume":"18","author":"Chen","year":"2000","journal-title":"J. Glob. Optim."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Zeng, Y., Xu, L., and Chen, Z. (2016). Fault-Tolerant Algorithms for Connectivity Restoration in Wireless Sensor Networks. Sensors, 16.","DOI":"10.3390\/s16010003"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1835","DOI":"10.1109\/TVT.2011.2131158","article-title":"Bio-inspired Relay Node Placement Heuristics for Repairing Damaged Wireless Sensor Networks","volume":"60","author":"Senel","year":"2011","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1204","DOI":"10.1109\/18.850663","article-title":"Network information flow","volume":"46","author":"Ahlswede","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Li, Z., and Wu, C. (2012, January 1\u20136). Space information flow: Multiple unicast. Proceedings of the 2012 IEEE International Symposium on Information Theory (ISIT), Cambridge, MA, USA.","DOI":"10.1109\/ISIT.2012.6283627"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Huang, J., and Li, Z. (2016, January 4\u20138). A delaunay triangulation approach to space information flow. Proceedings of the 2016 IEEE Workshop on Network Coding and Applications (NetCod), Washington, DC, USA.","DOI":"10.1109\/GLOCOMW.2016.7848807"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Huang, J., Yin, X., Zhang, X., Du, X., and Li, Z. (2013, January 7\u20139). On space information flow: Single multicast. Proceedings of the 2013 International Symposium on Network Coding (NetCod), Calgary, AB, Canada.","DOI":"10.1109\/NetCod.2013.6570816"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1002\/(SICI)1097-0037(199710)30:3<149::AID-NET1>3.0.CO;2-L","article-title":"Euclidean Steiner minimum trees: An improved exact algorithm","volume":"30","author":"Winter","year":"1997","journal-title":"Networks"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1016\/j.adhoc.2007.05.003","article-title":"Strategies and Techniques for Node Placement in Wireless Sensor Networks: A Survey","volume":"6","author":"Younis","year":"2008","journal-title":"Ad-Hoc Netw."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1109\/MNET.2004.1316760","article-title":"Movement control algorithms for realization of fault-tolerant ad hoc robot networks","volume":"18","author":"Basu","year":"2004","journal-title":"IEEE Netw."},{"key":"ref_19","unstructured":"Baroudi, U., and Younis, M. (2010, January 12\u201314). Optimal node repositioning for tolerating node failure in wireless sensor actor network. Proceedings of the 25th Biennial Symposium on Communications (QBSC), Kingston, ON, Canada."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/j.jnca.2016.03.009","article-title":"Restoring connectivity in a resource constrained WSN","volume":"66","author":"Joshi","year":"2016","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1669","DOI":"10.1109\/TC.2010.174","article-title":"A localized algorithm for restoring internode connectivity in networks of moveable sensors","volume":"59","author":"Younis","year":"2010","journal-title":"IEEE Trans. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Wang, H., Ding, X., Huang, C., and Wu, X. (2016). Adaptive Connectivity Restoration from Node Failure (s) in Wireless Sensor Networks. Sensors, 16.","DOI":"10.3390\/s16101487"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Senel, F., and Younis, M. (2011, January 5\u20139). Optimized Connectivity Restoration in a Partitioned Wireless Sensor Networks. Proceedings of the 2011 IEEE Global Communications Conference (GLOBECOM), Houston, TX, USA.","DOI":"10.1109\/GLOCOM.2011.6134397"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1007\/s11227-013-1054-0","article-title":"An efficient routing algorithm to preserve k-coverage in wireless sensor networks","volume":"68","author":"Ahmadi","year":"2014","journal-title":"J. Supercomput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1007\/s11227-016-1785-9","article-title":"P-SEP: A prolong stable election routing algorithm for energy-limited heterogeneous fog-supported wireless sensor networks","volume":"73","author":"Naranjo","year":"2016","journal-title":"J. Supercomput."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"2884","DOI":"10.1109\/TIT.2014.2308998","article-title":"A geometric perspective to multiple-unicast network coding","volume":"60","author":"Xiahou","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/1362542.1362545","article-title":"Partial network coding: Concept, performance, and application for continuous data collection in sensor networks","volume":"4","author":"Wang","year":"2008","journal-title":"ACM Trans. Sens. Netw."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1109\/TWC.2012.111412.112124","article-title":"Enhancement of lifetime using duty cycle and network coding in wireless sensor networks","volume":"12","author":"Rout","year":"2013","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2934","DOI":"10.1109\/JSEN.2014.2386536","article-title":"Improving the Performance of Wireless Sensor Networks Through Optimized Complex Field Network Coding","volume":"15","author":"Eritmen","year":"2015","journal-title":"IEEE Sens. J."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/2140522.2140523","article-title":"Data authenticity and availability in multihop wireless sensor networks","volume":"8","author":"Ayday","year":"2012","journal-title":"ACM Trans. Sens. Netw."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/net.3230110104","article-title":"An O (n log n) heuristic for Steiner minimal tree problems on the Euclidean metric","volume":"11","author":"Smith","year":"1981","journal-title":"Networks"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Li, Z. (2007, January 6\u201312). Min-cost multicast of selfish information flows. Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM), Anchorage, AK, USA.","DOI":"10.1109\/INFCOM.2007.35"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Yin, X., Wang, Y., Wang, X., Xue, X., and Li, Z. (2012, January 1\u20136). Min-cost multicast networks in euclidean space. Proceedings of the 2012 IEEE International Symposium on Information Theory (ISIT), Cambridge, MA, USA.","DOI":"10.1109\/ISIT.2012.6283071"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Huang, J., and Li, Z. (2014, January 8\u201312). A recursive partitioning algorithm for space information flow. Proceedings of the 2014 IEEE Global Communications Conference (GLOBECOM), Austin, TX, USA.","DOI":"10.1109\/GLOCOM.2014.7037014"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/17\/4\/902\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:33:00Z","timestamp":1760207580000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/17\/4\/902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,20]]},"references-count":34,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,4]]}},"alternative-id":["s17040902"],"URL":"https:\/\/doi.org\/10.3390\/s17040902","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2017,4,20]]}}}