Wireless sensor network design with reliable and long network lifetime.

Wireless sensor network design with reliable and long network lifetime - PMC Skip to main content An official website of the United States government Here's how you know Here's how you know Official websites use .gov A .gov website belongs to an official government organization in the United States. Secure .gov websites use HTTPS A lock ( Lock Locked padlock icon ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites. Search Log in Dashboard Publications Account settings Log out Search… Search NCBI Primary site navigation Search Logged in as: Dashboard Publications Account settings Log in Search PMC Full-Text Archive Search in PMC Journal List User Guide PERMALINK Copy As a library, NLM provides access to scientific literature. Inclusion in an NLM database does not imply endorsement of, or agreement with, the contents by NLM or the National Institutes of Health. Learn more: PMC Disclaimer | PMC Copyright Notice Sci Rep . 2026 Apr 14;16:12458. doi: 10.1038/s41598-026-46014-x Search in PMC Search in PubMed View in NLM Catalog Add to search Wireless sensor network design with reliable and long network lifetime Esra Çelik Esra Çelik 1 Department of Industrial Engineering, Faculty of Engineering, Ataturk University, Erzurum, Turkey Find articles by Esra Çelik 1, ✉ , Muhammed Emre Keskin Muhammed Emre Keskin 1 Department of Industrial Engineering, Faculty of Engineering, Ataturk University, Erzurum, Turkey Find articles by Muhammed Emre Keskin 1 Author information Article notes Copyright and License information 1 Department of Industrial Engineering, Faculty of Engineering, Ataturk University, Erzurum, Turkey ✉ Corresponding author. Received 2025 Oct 20; Accepted 2026 Mar 23; Collection date 2026. © The Author(s) 2026 Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/ . PMC Copyright notice PMCID: PMC13083951  PMID: 41981015 Abstract In Wireless Sensor Networks (WSNs), sensors transmit collected data to a sink using limited battery power. Deployment in remote or inaccessible areas often necessitates networks that remain operational for long periods. Since replacing batteries in numerous sensors is often unfeasible, extending network lifetime is a primary design goal. This is typically addressed by solving four key design problems: coverage, sink placement/routing, sensor activity scheduling, and data routing. These are usually studied individually, or rarely in combination. Network reliability is also crucial for protecting against attacks or failures, preventing coverage holes and data loss. Unlike most studies, this work addresses all four design problems and network reliability in an integrated manner. We propose strategies such as Single Copy (SC) for single-path data transmission, Double Copy (DC) for multi-copy transmission, and a Hybrid (H) strategy where copying occurs in sensors transmitting to central nodes. Tests under various scenarios reveal that the SC strategy is superior for network lifetime, while the DC strategy excels in reliability. The H strategy provides a balanced performance in both lifetime and reliability. Furthermore, to enable the H strategy to find solutions efficiently in large-scale scenarios, we apply a Lagrangian Heuristic (LH) approach. The Lagrangian subproblem is solved using a Dantzig–Wolfe column generation algorithm and a feasible solution is constructed from the Lagrangian subproblem solution at each step. The performance of this heuristic is demonstrated by comparing its results to those obtained with the Gurobi solver. The results show that the LH method provides higher network lifetime compared to Gurobi, especially for medium and large-scale networks. Keywords: Optimization algorithms, Wireless sensor networks, Reliability, Network lifetime, Multi-copy, Lagrangian relaxation Subject terms: Energy science and technology, Engineering, Mathematics and computing Introduction Wireless Sensor Networks (WSNs) typically consist of small, autonomous sensors with limited battery power that communicate with each other or with sinks via wireless connections. These networks are used to monitor and control various physical and environmental variables such as light, temperature, sound, vibration, pressure, motion, and pollution. WSNs hold a prominent position today due to their ability to provide real-time data, their ability to operate for long periods despite energy constraints, and their broad application potential. Therefore, reliability and energy efficiency are among the key priorities in wireless sensor network designs 1 . Literature suggests that these networks can be used in various environments, such as environmental monitoring in agricultural fields, oceans, and cities; inventory management, product quality control, and disaster zone surveillance in commercial applications; patient monitoring and support systems for individuals with disabilities in healthcare; It is used in many areas, including smart grid applications and monitoring of renewable energy plants below 2 . The use of WSNs for long-term, uninterrupted data collection, often in hard-to-reach or remote areas, makes network lifetime crucial. Replacing the abundant sensor batteries is often not considered a feasible option. For this reason, the network should have as long a lifetime as possible for the application to operate successfully. Inefficient energy use can lead to reduced coverage, connection interruptions, and consequently, loss of network functionality. Therefore, distributing energy consumption evenly among sensors is a fundamental approach to increasing network lifetime. To this end, to conserve energy and extend network lifetime in WSNs, researchers focus on combinations of four fundamental design problems: the Coverage Problem (CP), the Activity Scheduling Problem (ASP), the Sink Placement Problem (SPP), and the Data Routing Problem (DRP). CP is addressed to monitor areas of interest by placing sensors in specific areas. Coverage levels can vary, especially in regions with varying degrees of importance 3 , 4 . Sensors are placed considering their coverage demands. Optimal sensor placement both improves detection quality and reduces energy consumption. ASP addresses the planning of the time periods during which sensors will be active or idle. Scheduling achieved with ASP is essential for ensuring a balanced distribution of energy consumption among sensors and ensuring the network’s continuous operation and longevity. Furthermore, coverage demands are expected to be met by a sufficient number of active sensors in each time period. SPP deals with determining the sink locations to which sensor data will be transmitted and establishing data transmission paths to these locations. The location of the sinks directly affects the data transmission paths and, consequently, the energy consumption of the sensors. As a result of unbalanced energy consumption, sensors that communicate directly with a sink may consume energy faster than others. This can lead to the death of nearby sensors and the disconnection of some sinks from the rest of the network. Such situations can lead to the failure of critical data transmission or the collection of incomplete information. By using mobile sinks, the load on the sensors can be reduced. When the sink is mobile, SPP transforms into the Sink Routing Problem (SRP). Routing the sinks can contribute to extending the network lifetime. DRP, on the other hand, deals with ensuring the optimal paths for data flow from sensors to other sensors or to the sinks. Energy efficiency is essential in determining these paths. In addition to the four basic WSN design problems mentioned, there are some important factors to be considered. These factors include connectivity, reliability, energy efficiency, fault tolerance, security, cost and scalability. Many studies in the literature aim to develop more efficient sensor networks by considering these design factors. In this context, the integrated consideration of different design elements has the potential to increase network lifetime. Connectivity is defined as the ability of all sensors in a network to connect to at least one sink 5 . The accurate, complete, and secure transmission of data indicates that the network is reliable. Not only extending the network lifetime but also ensuring reliable data transmission is also very critical 1 , 6 , 7 . In the real world, reliability is crucial, as sensor failures, network outages, or data loss can threaten network operation. Especially in WSNs used for critical missions such as border surveillance, protecting the infrastructure against malicious attacks or failures is essential for network sustainability. For example, in critical applications such as surveillance systems, even the failure of a single sensor can disrupt coverage integrity. Networks where data transmission occurs in a one-way manner are vulnerable to data loss if a single communication link fails. If data is transmitted to the sink via a single sensor or link, and this sensor fails or the link is lost, the data cannot reach the destination. Therefore, researchers have adopted and implemented strategies such as Sensor Balanced Utilization (SBU), Multipath Routing Utilization (MRU), Multicopy Sending (MCS), and Central Node Utilization (CNU). SBU is based on preventing certain sensors with high data density from becoming critical to the network. By limiting the amount of data sensors can receive from each other, the risk of network congestion is mitigated. SBU and CNU increase network resilience by establishing redundant communication paths or multiple copying mechanisms. In MRU, sensors divide their data into multiple sub-packets and transmit them to the sink via different routes. In CNU, data is sent to the sink with redundant copies. These methods, which ensure route diversity, also increase reliability by providing alternative routes in the event of a failure. It has been observed that copying data from each sensor in the network and transmitting it to the sink leads to inefficient energy consumption, leading to premature network lifetime. To this end, the CNU strategy requires selecting a sensor node with the highest data density whose damage would most significantly impact the entire network. This sensor, called the central node, replicates data sent to or received from the source 8 . Because the decisions that optimize network lifetime and network reliability in the most efficient WSN design are interrelated, they must be addressed within a unified framework. Most existing studies focus on only a single type of decision or a subset of four design issues to improve network lifetime. It should be noted that WSN design problem affects the performance of other design problems. Furthermore, a comprehensive approach integrating the four fundamental design problems along with network reliability within the same model is lacking in the literature. Therefore, a study that addresses both design issues in an integrated manner and network reliability is needed. We hope to cover this gap by this study. Four main contributions of this study to the literature can be listed as: Three strategies were developed to jointly address four fundamental design problems and network reliability in WSN design. Mixed-integer mathematical models were created for the developed strategies. Different scenarios were generated to measure the network reliability of the strategies. A heuristic method was developed to effectively design reliable large-scale networks with long lifetimes. The remainder of the article is structured as follows: “ Related studies ” section reviews literature studies on network lifetime and reliability in WSNs. In “ Integrated mathematical models ” section defines the problem and presents mathematical models for the developed strategies. In “ Heuristic method ” section provides a detailed description of the proposed heuristic solution algorithm. In Section “ Numerical results ”, the numerical results of the strategies and heuristic method are presented. Finally, in “ Conclusion ” section, the findings are evaluated, the study’s contribution to the field is summarized, and potential future research directions are discussed. Related studies We examine the relevant literature on this research topic as studies addressing the four design issues and studies addressing network reliability. The heuristic methods developed in these studies are also of interest. Table 1 summarizes the studies in the literature. Table 1. Problems concerned by studies in the literature. Author Network lifetime Network reliability CP ASP SRP DRP SBU MRU MCS CNU Other Altınel et al. 9 X Türkoğulları et al. 3 X X X X Türkoğulları et al. 4 X X X X Türkoğulları et al. 23 X X X X Güney et al. 17 X X Keskin et al. 18 X X X Güney et al. 21 X X X Keskin et al. 24 X X X X Keskin et al. 25 X X X X Keskin et al. 22 X X X Keskin 26 X X X X Keskin 27 X X X X Keskin and Yiğit 19 X X X Aznoli and Navimipour 5 X X Boubrima et al. 12 X X Torlak 2 X X X X Boubrima et al. 13 X X Guimarães et al. 14 X X Nguyen and Nguyen 28 X X X X Amutha et al. 15 X X Kuang et al. 16 X X Srinivas and Amgoth 20 X X Serper and Altın-Kayhan 10 X Kundaliya et al. 29 X X X X Naik and Shetty 11 X Çelik et al. 30 X X X X Stavrou and Pitsillides 32 X X X İncebacak et al. 31 X X Incebacak et al. 33 X X X Altın-Kayhan and Şendil 6 X X X X X Ekmen and Altın-Kayhan 8 X X X X Ekmen and Altın-Kayhan 7 X X X Yücel and Altın-Kayhan 1 X X X X X X Persis 35 X X Yang et al. 34 X Sun et al. 36 X X X Cav and Altın-Kayhan 37 X X Biswas et al. 38 X X X X Zhen et al. 39 X X X Shakhov and Migov 40 X X X Shakhov et al. 41 X X X Chen 42 X X X This Study X X X X X X X Open in a new tab Design issues We first present studies examining WSN design issues below. Altinel et al., Serper and Altın-Kayhan, and Naik and Shetty attempt to achieve a long-lived network by focusing solely on CP in WSN design 9 – 11 . Altinel et al. propose a binary integer linear programming model for heterogeneous sensor networks with varying coverage requirements and costs 9 . Furthermore, two different heuristic methods are developed by combining the greedy approach and Lagrangian relaxation with subgradient optimization. Serper and Altın-Kayhan present a multi-period design approach that includes coverage and connectivity requirements when the network topology changes 10 . Additionally, the use of mobile sensors is proposed to address coverage gaps that may occur in smart grid applications of WSNs. An optimization model that enables sensors to follow the shortest path is also developed. Naik and Shetty propose an approach to increase energy efficiency and achieve longer network lifetimes with higher coverage/connectivity ratios. Sensor placement is performed using a multi-criteria decision-making method 11 . Aznoli and Navimipour address the need for systematically examining deployment strategies in addition to coverage and connectivity issues in WSNs by considering both CP and DRP 5 . To this end, they analyzed the deployment mechanisms used in WSNs and attempted to identify the types of challenges addressed. Boubrima et al. note that general deployment models do not fit the stochastic nature of air pollution 12 . Therefore, the study designed an integer programming model that calculates sensor deployments that capture pollution coverage and infrastructure connectivity under time-varying weather conditions. Furthermore, Boubrima et al. propose new optimization models and algorithms for optimal wireless sensor network design for air pollution mapping 13 . Guimarães et al., Amutha et al., and Kuang et al. focus on ASP along with CP 14 – 16 . Based on simulations and analysis of variance (ANOVA) results, Guimarãesa et al. state that both node mobility models and energy models should be considered and analyzed together for long-lasting network design 14 . Amutha et al. present a comprehensive classification that examines sensor types, placement strategies, sensing models, coverage areas, sensor idle/active state, and energy efficiency in wireless sensor networks 15 . Kuang et al. focus on the scheduling problem of mobile underwater wireless sensor networks with a small number of mobile sensors and a large number of fixed sensors. The proposed algorithm aims to maximize coverage and minimize energy consumption 16 . Focusing on SPP and DRP, Güney et al. develop new mixed integer linear programming models to determine optimal sink placements and information flow paths between sensors, given sensor locations. They also propose three different heuristics for solving these models 17 . In addition, Keskin et al. present two new mathematical programming models that consider ASP, SPP and DRP in an integrated manner to address the problem of premature power depletion of relay sensors and potentially disconnection of some sinks from the rest of the network 18 . Regarding the same integrated problem, Keskin and Yiğit also develop a mathematical model that considers sink travel times for multiple mobile sinks 19 . Srinivas and Amgoth focus solely on ASP and SPP and discuss a hierarchical clustering approach to ensure that mobile sinks are in the right place at the right time for data collection in large-scale WSNs. This approach aims to achieve a long-lived network design by using energy efficiently and minimizing data loss 20 . Güney et al. incorporate sensor distribution or sensing area coverage into the sink location and data routing problems of Güney et al. 17 in sensor network design 21 . A tabu search heuristic is presented to determine the optimal sensor locations to meet coverage requirements. Keskin et al. integrate CP, SPP, and DRP into a WSN design using mobile sinks. The developed mixed integer linear programming model examines how mobile sinks extend network lifetime 22 . Türkoğulları et al. aim to maximize network lifetime by determining the placement of sensors and data collection points (sinks), data flow paths, and sensor activity schedules (active and idle times) in a network subject to energy and budget constraints. To this end, they propose a new mixed integer linear programming (MILP) model. The model also has a structure that accommodates various sensors with different energy consumption rates, detection and communication ranges, and unit costs. A heuristic approach based on Lagrangian relaxation and subgradient optimization is presented 3 . Türkoğulları et al. develop a heuristic to produce an efficient solution on large-scale examples by adding heterogeneous sensor types with different coverage requirements to the model 3 proposed by Türkoğulları et al. 4 . The offered heuristic generates a feasible solution using a subset of sensors that met the coverage requirements during a specific period when the sensors were active. Türkoğulları et al. improve the model proposed by Türkoğulları et al. 3 , 4 . They also propose a heuristic method to solve large-scale examples in acceptable time 23 . Keskin et al. indicate that a holistic mathematical optimization model that can provide an effective and accurate solution that can be practically applied in wireless sensor network design is lacking. A mathematical model that integrates four design problems is developed. In addition, two heuristic methods are proposed for solving the model 24 . Keskin et al. use a two-stage heuristic method instead of classical optimization methods for their integrated WSN design problem. In the first stage, the optimal sink locations are determined using Simulated Annealing. Then, a Dantzig–Wolfe decomposition approach is applied to determine event scheduling and data flow paths 25 . Keskin presents a heuristic method for applying the CASD formulation introduced by Keskin et al. 24 to four fundamental design problems in wireless sensor networks. Network designs are generated using the developed column generation method and Lagrangian relaxation 26 . Keskin develop a mixed integer linear program that integrates the cost of sinks into the four design problems 27 . Torlak addresses design issues in an integrated manner and provides a realistic network lifetime definition 2 . Accordingly, the total coverage time of the point to be covered should be a certain percentage of the lifetime. Nguyen and Nguyen present a comprehensive review of advanced methods that leverage the mobility of sensor nodes and/or sink(s) to extend the lifetime of mobile wireless sensor networks. The study details networks with mobile sensor nodes, networks with a single mobile sink, and networks with multiple mobile sinks. The issue of energy-efficient routing of mobile collectors is also addressed 28 . Kundaliya et al. develop examples of smarter and more efficient network designs by providing solutions to fundamental problems in WSN design using machine learning algorithms 29 . Çelik et al. address the WSN design problem in an integrated manner, placing sensors and sinks on a grid-free structure. It is stated that this positioning allows WSNs to meet their specific requirements in a more flexible way 30 . Reliability We present how researchers have adopted and implemented strategies to ensure network reliability in WSN design in this sub-section. In WSNs, multipath routing has been proposed for energy balancing, which extends network lifetime compared to single-path routing, which uses only one path between a source node and the sink. Furthermore, multipath routing strategies make the network more secure and resilient. However, keeping the number of routing paths low is also essential to avoid negatively impacting network lifetime. Therefore, determining the optimal number of routing paths in multipath routing is an interesting research problem that needs to be explored to maintain the balance between routing complexity and network lifetime extension 31 . Stavrou and Pitsillides examine the current status of secure multipath routing protocols in WSNs and categorize them according to their security-related operational objectives. They evaluate how routing protocols can increase network reliability, resilience, and self-healing capacity 32 . Incebacak et al. evaluate the energy cost of path diversity used to enhance security in WSNs. To this end, a new mixed integer programming framework is developed to investigate the effect of the number of paths in multipath routing on maintaining network-wide energy balance under optimal operating conditions 31 . Similarly, Incebacak et al. model three path diversity techniques against different attack types within a linear programming framework. These attack types include node-only capture, eavesdropping, and both node-only capture and eavesdropping attacks. The energy distribution and data transfer behaviors are examined to mitigate the effects of these attacks 33 . Altın-Kayhan and Şendil examine multipath routing with various levels of multiple replication and four different routing strategies with respect to no redundancy, full redundancy, and partial redundancy. Mathematical models are created for the routing strategies, incorporating balanced energy distribution. Tests demonstrate the trade-off between energy efficiency and network reliability across strategies. Accordingly, the partial multi-copy protocol with the extended balanced utilization rule is found to be quite suitable for efficient and secure energy use in networks 6 . Ekmen and Altın-Kayhan develop a conditional multi-copy and multi-path routing strategy to improve network reliability and security in WSNs. Addressing design issues such as SPP and DRP, they propose that replication should only occur for sensor data using central nodes. Replication only at central nodes reduces unnecessary data duplication and increases network security 8 . Ekmen and Altın-Kayhan further expand the design problem of Ekmen and Altın-Kayhan 8 to improve network reliability by presenting two new data transfer strategies. These strategies ensure that the sensor is selected as the central node only if it is beneficial for network life. Furthermore, the number of central nodes can vary depending on the circumstances 7 . Yücel and Altın-Kayhan develop a strategy in which data is retransmitted to increase network reliability and extend network lifetime 1 . Contrary to Ekmen and Altın-Kayhan’s proposal, the strategy backs up data passing through the central node to the neighboring node, not the central node. Furthermore, unlike traditional approaches, only the data at the critical node is copied. Furthermore, balancing routing is implemented across all nodes of the network to prevent data congestion at a single node 8 . Yang et al. emphasize the importance of being able to model, evaluate, and predict the reliability of WSNs. In their reliability models, they use masked data, which they defined as "a type of missing data used to represent system failure when the exact cause of the failure is unknown." 34 . Persis emphasizes the vital importance of underwater communication and states that communication must be efficient and uninterrupted. A bio-purpose routing protocol is proposed for underwater wireless sensor networks to transmit data to the surface faster, more reliably, more accurately, and with minimal energy consumption 35 . Sun et al. propose an energy-efficient and reliable multipath transmission strategy for mobile wireless sensor networks. The strategy implements the shuffled frog-hopping algorithm, using particle swarm optimization. The presented algorithm creates the optimal transmission path and aims to increase the stability and reliability of the network 36 . Cav and Altın-Kayhan state that the coverage level for a target region is an indicator of how effectively that region can be monitored. Like Serper and Altın-Kayhan 10 they discuss the use of mobile sensors to ensure full coverage in a WSN. This study also attempts to determine the shortest mobile sensor lap time to cover all these regions in the shortest possible time. Furthermore, unlike other studies, this approach ensures data transmission reliability and achieves a reliable network design 37 . Biswas et al. analyze how multipath routing and the use of multiple sinks in WSNs affect network lifetime. They also use Automatic Repeat ReQuest and Energy Efficient Secure Multipath protocols to ensure reliable data transmission and energy efficiency 38 . Zhen et al. investigate the integration and timing control of data transmission via role nodes, even if sensor nodes lose connection to their sinks. The presented approach ensures reliable data transmission in WSNs used in complex environments, using real-time software-based intervention without affecting the hardware 39 . Shakhov and Migov present new methods to ensure and increase network reliability in WSNs with multiple sinks. Using the sink placement method, a reliability metric is calculated based on the placement of the sinks each time. This metric reflects the probability that sensors in the network can transmit data to the sinks. This process continues until no better placement can be found with the potential sinks in the network 40 . Shakhov et al. apply the forward error correction method to analyze and optimize the reliability of long-distance WSNs. The error correction strategy is implemented in three different ways: only at the edge, at intermediate nodes, and as a hybrid. Correcting these at intermediate nodes is found to significantly increase network reliability 41 . Chen (2025) attempts to increase network lifetime and energy efficiency by balancing loads among sensors using K-means clustering and the firefly algorithm. Dynamic sensor relocation allows for the fulfillment of coverage demands and the optimization of data transmission paths. He states that this reduces the risk of data loss and ensures network reliability 42 . To our knowledge, few studies in the literature integrate WSN design decisions by addressing four fundamental design issues to optimize network lifetime. This study, unlike existing studies, presents, for the first time, four fundamental design issues in WSN design integrated with the network reliability strategies. The performance of the network reliability strategies are then assessed using the different scenarios developed to measure network reliability. Additionally, a heuristic solution strategy is developed to solve large examples in reasonable time. Integrated mathematical models Here, we present the formulation of the developed mathematical models which integrate four WSN design issues with three different network reliability strategies. First, in Section " Sets, parameters and variables ", we explain the sets, parameters, and variables used in the formulations. We then introduce the formulation of models for three different strategies developed. Sets, parameters and variables We represent the locations to be covered by , the set of candidate locations where sensors can be placed by , and the possible points where sinks can be placed by , respectively. In the sequel, we will be using "sensor " to represent a sensor located at location and similarly "sink l " to represent a sink located at location l . Each sensor can directly transmit the data it produces to a sink within its communication range. However, if there is no sink within its communication range, the data is delivered to the target sink via neighboring sensors. The set of other candidate sensor locations within the communication range of sensor is expressed as , and the set of sink locations it can reach is expressed as . Similarly, is the set containing the coverage points that sensor can detect. Finally, the set of periods is represented by . In the models, a number of parameters such as energy consumption of sensors, data production and placement costs are defined. The initial energy level of each sensor is expressed by , while the amount of data produced by a sensor in unit time is indicated by . The energy spent during data sensing and receiving processes are modeled by the parameters and , respectively. Similarly, the energy spent during the transmission of data from sensor to sink l is defined by , and the energy used in case of transmission from sensor to sensor is defined by . The coverage requirements of the network are expressed by the help of parameter , which requires that coverage point is monitored by at least active sensors at any time during the network lifetime. In addition, the parameter indicates the cost of placing a sensor at location . The total budget allocated for sensor placement is defined by . In addition, the actual number of sinks is defined by parameter . There are various decision variables in the model regarding the operation of the network. While the length of the period is represented by the variable , and represent the amount of data transmitted from sensor to sensor and from sensor to sink l in period t, respectively. Decisions regarding positioning are modeled with binary variables and . Here, if , a sensor is placed at ; otherwise, it is not. Similarly, if , a sink is placed at location l in period , otherwise, it is not. Finally, the binary variable is used to determine whether sensor is active or passive in period . parameter represents large enough value. The sets, parameters and decision variables used in the developed strategies are summarized in Table 2 . Table 2. Sets, parameters and decision variables. Sets Definition Set of candidate sensor locations Set of sensor locations within communication range of sensor Set of candidate sink locations Set of sink locations within communication range of sensor Set of time periods Set of coverage points Set of coverage points within sensing range of sensor Parameters Definition Amount of data produced by each sensor per unit time Energy spent to detect and process data per unit time Energy spent by the sensor to receive one bit of data Energy spent to transmit one bit of data from sensor to sink l Energy spent to transmit one bit of data from sensor to sensor Initial energy of the sensors A large number Number of actual sinks Number of sensors required to monitor position Cost of placing sensor at location Sensor placement budget Decision variables Definition Length of period Amount of data transmitted from sensor to sensor in period Amount of data transmitted from sensor to sink l in period A binary variable indicating whether sensor is placed at location A binary variable indicating whether sensor is active at time period A binary variable indicating whether sink l is placed at time period Open in a new tab Developed strategies Three different strategies are designed and implemented: Single Copy (SC), Double Copy (DC) and Hybrid (H). Each strategy has different modeling scenarios in terms of data transmission structure and reliability approach. The mathematical models of these strategies are presented below. Single copy strategy The SC strategy is the basic strategy where sensors and sinks are placed based on four main design problems, and data transmission is done in a single copy over minimum-cost paths. The model for SC strategy is given below: 1 subject to 2 3 4 5 6 7 8 9 10 11 The objective function (1) of the model aims to maximize the sum of the period lengths representing the total lifetime of the network. Constraint (2) balances the data flow for each sensor in each period; a balance is established between the amounts of data received, transmitted and produced by the sensor. Constraint (3) is the energy constraint defined for each sensor. Accordingly, the energy consumption of sensor in each period is calculated depending on its activity status. This consumption consists of data detection, receiving data from neighboring sensors and sending data. The total energy consumption resulting from these processes should not exceed the initial battery energy of the sensor. Constraint (4) states that data transmission from sensor to sink l in period can only occur if there is a sink at location l . Constraint (5) requires that exactly sinks have to be placed in each period. Constraint (6) provides the coverage requirement; it requires that each coverage location be monitored by at least active sensors in each period. Constraint (7) limits the total cost of sensor placement by budget limit . Constraint (8) states that a sensor can only be active if it is placed. Constraint (9) states that no data flow can occur through an inactive sensor. In other words, no data input or output is allowed for inactive sensors. Finally, constraint (10) states that all continuous decision variables must be nonnegative while constraint (11) defines the placement and activity decision variables. The SC strategy is based on the formulation developed by Keskin to extend network lifetime 26 . The main objective of the strategy is to maximize the network lifetime. However, this approach does not explicitly address network reliability. Therefore, data transmission could be completely interrupted in the event of node or link damage. Double copy strategy The DC strategy is developed to increase data security and transmission continuity. While the SC strategy transmits only a single copy of each sensor’s data, the DC strategy ensures that each data is transmitted in multiple copies over both the primary and secondary paths. This strategy aims to increase the network’s resilience to node or link failures. Here, each sensor copies its data and forwards it to the sink via routing from two disjoint nodes called the primary and secondary paths 6 . Table 3 includes the additional decision variables representing the transmission of data through primary and secondary paths in period . Table 3. Additional decision variables used in DC strategy. Symbol Definition Primary data of sensor transmitted through sensor i to sensor at period Secondary data of sensor transmitted through sensor i to sensor at period Primary data of sensor transmitted through sensor i to sink l in period Secondary data of sensor transmitted through to sensor i to sink l in period Binary variable indicating whether the primary data of sensor is transmitted via sensor i in period Open in a new tab The DC strategy can be modeled with the following mixed integer programming model: 1 subject to (5)-(8), (11) 12 13 14 15 16 17 18 19 20 21 Constraints (12) and (13) define the flow balancing condition for primary and secondary data flows, respectively. If sensor is actually the source sensor , it generates a certain amount of data; otherwise, the received and transmitted data amounts are equalized. This ensures correct routing of data flow within the network. Constraint (14) limits the energy consumption for each sensor. In constraints (15) and (16), the binary variable ensures that primary and secondary data originating from the same source are routed via node-disjoint paths which we call as primary and secondary paths, respectively. Constraint (17) prevents any primary or secondary data transmission to location l if no sink is placed there. Constraint (18) states that data cannot be transmitted from inactive sensors. Similarly, constraint (19) defines that data can be transmitted to active sensors only. Finally, constraint (20) satisfies the positivity condition for continuous variables, while constraint (21) specifies that the variable is binary. A network with a DC strategy can compensate for any problems that may arise on the primary path or at the sensor node by transmitting data via a secondary path. This method of data transmission attempts to increase network reliability. However, copying the data of each sensor causes the limited energy of the sensors to be consumed quickly and the lifetime of the network to be shortened. A data transmission structure that balances energy and reliability while ensuring long network lifetime is needed which we propose in the following. Hybrid strategy Here, we offer a new approach which balances the high network lifetime of the SC strategy with the network reliability effort of the DC strategy. The idea is that data copying is performed not on every sensor, but on the sensors that transmit data to the central nodes. The central node is defined here as the sensor with the high data density in the network and considered vulnerable to damage. Adopting the CNU strategy for data copying will ensure network reliability while preserving energy efficiency. At the same time, an optimal data routing process is achieved, improving overall system performance. The decision variables that should be added to the model are presented in Table 4 . 1 subject to Table 4. Decision variable and its definition. Symbol Definition The total amount of data transmitted from sensor i in period A binary variable indicating whether sensor i is central in period A binary variable indicating whether data generated by sensor k is transmitted through a central node in period t Open in a new tab (5)-(8), (12), (14)-(21) 22 23 24 25 26 27 28 29 According to constraint (22), the amount of secondary data transmitted by sensor is equal to the amount of secondary data it receives for source sensor . The left side of constraint (23) calculates the total amount of primary data generated at sensor and transmitted to the central nodes. If this amount is greater than zero, the variable takes the value 1. In other words, if = 0, the amount of data generated at sensor and transmitted from the central node will be 0. According to constraint (24), if data generated by sensor is transmitted from a central node in period , then = 1, the amount of secondary data generated and transmitted by sensor must be at least . Otherwise ( = 0), no secondary data flow is generated at sensor . Constraint (25) calculates the total data flow by combining the primary and secondary data flows transmitted by sensor . Constraint (26) guarantees a certain minimum data flow for central nodes. If = 1 (i.e., sensor is the central node in period ), the amount of data transmitted by sensor must be at least . If (i.e., sensor i is not central), constraint (26) is automatically satisfied because the right-hand side becomes a large negative value. Constraint (27) ensures that less than data passes through sensors that are not central nodes ( = 0). Constraint (28) states that the continuous variable must be positive, while constraint (29) states that binary variables must take on the value 0 or 1. The expression in constraints (2), (3), (12), (13), and (14) represents the amount of time during which sensor is active at period , but it transforms the model into a nonlinear structure because it involves the multiplication of the binary variable and the continuous variable . To linearize this expression, the multiplication in question is represented by a new continuous variable called and following four linear constraints are added to the model to accurately describe this variable. 30 31 32 33 Constraints (30)–(33) define the relationship between the continuous variable and the variables and Constraints (30) and (32) ensure that if sensor is active in time period ( ), the variable equals . Similarly, Constraints (31) and (33) ensure that if sensor is in standby mode ( ), the value is equal to zero. Constraint (33) also specifies that the continuous variable must take a nonnegative value. Similarly, the expression in Constraint (23) renders the model nonlinear because it involves the multiplication of the binary variable and the continuous variable . To eliminate this nonlinear term, the multiplication expression is represented by a new continuous variable, . To ensure the accuracy of this variable and to preserve the linear structure of the model, following additional constraints are included in the model. 34 35 36 37 When constraints (34) and (36) are considered together, the variable is guaranteed to be equal to the value of if sensor is the central node in period ( ​). Conversely, constraints (35) and (37) guarantee that the value of is zero if sensor is not the central node in that time period ( ). It should be noted that in the notation used for decision variables ( and ), subscripts represent indices (e.g., candidate sensor locations, candidate sink visit locations, period), while superscripts represent different flow/path types of the same variable. A visual summary of the strategies developed is presented in Fig. 1 . Fig. 1. Open in a new tab Formation stages of SC, DC and H strategies. Computational complexity of SC, DC, and H strategy The article discusses the single-copy transmission (SC) strategy first, which is the most basic one out of the mentioned three problems. This problem is very similar to the problem of analyzed by Keskin 27 . He is show that the SC strategy transmission problem is NP-hard. The DC strategy is an extended version of the SC strategy. If, in the DC strategy, data is transmitted as a single copy instead of copying and constraints (15) and (16) are relaxed, the DC strategy transforms into the SC strategy. In the H strategy, if constraints (23), (26), and (27) are relaxed and all sensors are assigned as central nodes, the H strategy transforms into the DC strategy. Therefore, both the DC and H strategies are NP-hard problems. Heuristic method As previously mentioned, the computational time required for the complete solution of H model is not reasonable for medium and large instances due to the large number of binary decision variables included in the formulation. The commercial solver cannot achieve an optimal solution for large-sized instances within tolerable computation times as we witness in the numerical experiments. Therefore, a method that divides the problem into smaller subproblems is needed. We use a Lagrangian Heuristic (LH) approach for that manner. This method provides acceptable solution quality in reasonable time for medium- and large-sized instances. Lagrangian relaxation scheme We relax the constraints (6), (15), (16), (17), (18), (19), (23), (24), (26), (27), (31), (32), (35), and (36) and add them to the objective function by multiplying with Lagrange multipliers and respectively. We express the resulting Lagrangian subproblem as H( and the objective function value of the Lagrangian subproblem as ). We organize the formulation in the following. H( ): 38 subject to (5), (7), (8), (10)-(12), (14), (20)-(22), (25), (28)-(30), (33), (34), (37). The Lagrangian subproblem can be decomposed into six independent subproblems and the constant part of the objective function. The first subproblem defined by ( ) is a linear programming (LP) problem involving only continuous decision variables and the related constraints. In addition, ( represents the objective function value of subproblem . The formulation for the first subproblem is as follows. ( ): 39 subject to 40 41 42 43 44 45 46 The second Lagrangian subproblem is defined as ( ), and the objective function value is denoted by ( ). We give the formulation for ( ) below. H 2 ( ): 47 subject to 48 49 50 Upon careful examination, it becomes clear that ( ) can be transformed into a binary knapsack problem for which we provide the formulation below. To accomplish this transformation, the parameter is defined as . 51 subject to 52 53 ( ) is first solved by the solver to obtain . Then, by inspecting, the values can be found; if no sensor is located at position ( ), it will be inactive for all periods ( ). If the sensor is located at position ( ), and the value is greater than or equal to zero, the sensor will be active in period ( ), otherwise . The mathematical representation of the inspection is as follows: 54 Substituting the found values of into (47), we find the value of ( ). The third subproblem H 3 (γ) for which the formulation is given below, involves the variable related to the positioning of the sink. The objective function value for this subproblem is expressed as (γ). H 3 ): 55 subject to 56 57 We can decompose ( ) into smaller subproblems, denoted as for each period . can be easily solved for any given value of as explained later and can be obtained accordingly. ): 58 subject to 59 60 ( ) can be solved by inspection. First, alternatives with the highest objective function coefficient ( ) are selected sequentially in each period . Then, the selected location l is assumed to be a sink location for period ( ). Substituting the found values of (58), we find . The fourth subproblem ( ), contains only the variable , which indicates whether the primary flow of data from source was transmitted through sensor in period . The expression ( ) represents the objective function value of this subproblem. ): 61 subject to 62 In order to solve the fourth sub-problem and find the variable, the following mathematical expression ( 63 ) is applied. 63 Substituting the found values of into (61), we find ( ). The fifth subproblem , , ), contains the variable , which indicates whether sensor is central in period . The objective function value for the subproblem is shown by , , ). ( , , ): 64 subject to 65 In order to solve the fifth sub-problem and find the variable, the following mathematical expression ( 66 ) is applied. The refence for expression (66) appears to be equ65. No other expession references are given. 66 Substituting the found values of into (64), we find , , ). The sixth subproblem ( ) contains the binary variable , which indicates whether data generated by sensor k is transmitted through a central node in period t . shows the objective function value. ( ): 67 subject to 68 In order to solve the sixth sub-problem and find the value of variable, the following mathematical expression ( 69 ) is used. The refence for expression (69) appears to be equ68. 69 Substituting the found values of into (67), we find . Finally, ( ) represents the constant part of the objective function, which is given in the following. 70 The objective function value constitutes an upper bound on the optimal objective function value for given multipliers . can be expressed as summation of the objective function values of the subproblems and the constant part as: , = , + + + + ( ). The path to achieving the minimum Lagrangian upper bound is to determine the optimal Lagrangian multipliers. These optimal multipliers are obtained using the Dantzig–Wolfe column generation method, which will be explained in detail in the subsection " Solving the lagrangian dual problem ". The subproblem solutions generated in each iteration of the algorithm cover a large portion of the solution space. Therefore, we anticipate that the subproblem solutions may provide high-quality solutions for the original Hybrid formulation after transforming them for feasibility by the help of a little heuristic. Details of this heuristic is also provided in subsection " Generation of the feasible solutions ". The numerical results section experimentally validates the effectiveness of this approach. In summary, as discussed in the next section, we use the column generation method to determine optimal Lagrange multiplier values. Solving the Lagrangian dual problem The Lagrangian Dual (LD) problem aims to find the optimal multiplier values ​​that minimize the objective function It can be written as follows: which is equivalent to. + + + + ( ). One may define the upper bounds for each and for the objective function values and the constant part , for each , , and ( ), respectively. Then, the new representation of the LD problem can be constructed as follows: 71 subject to 72 73 74 75 76 77 78 79 80 We now define as the index set labeling the extreme points of the feasible region of the first subproblem. We define , , , , and as the points labeling the feasible solutions of the other subproblems. For defined by the constraints (40)-(46), we define as the set of the extreme points of the feasible region. In addition, for , is the set of points satisfying (48)-(50). is the set of points satisfying (56) and (57) (i.e., the feasible region of ) for all . Similarly, for ), for ) and for are the sets of points satisfying (62), (65) and (68), respectively. The new representation of the LD problem depending on the above described sets is as follows: 81 subject to 82 83 84 85 86 87 88 89 90 Since the sets , , , , and may have an enormous number of members, numbers of constraints are also enormous. This means that it is impossible to include all constraints in the form of (82)-(87). Therefore, instead of the constraints (82)-(87), we start with a subset of them which we call as the Restricted Lagrangian Dual Problem (RLD). is the optimum value of the LD problem, and we let the optimum value of the RLD problem with fewer constraints be represented by . Since RLD is obtained by relaxing LD, is a lower bound for , i.e., ≤ . Also is an upper bound to for any value of the multipliers. We attempt to obtain optimal Lagrangian multiplier values that provide the minimum Lagrangian dual value. For this purpose, the Dantzig Wolfe column generation implementation of Wentges is used to solve the Lagrangian Dual Problem 44 . The iterations of the Dantzig–Wolfe column generation algorithm consist of two stages. In the first stage, , , , ), ), and are solved, and the constraints in the form of (82)-(87) are added to the RLD according to the optimal solutions of the subproblems. Then, the RLD is solved to optimality to update the Lagrange multiplier values. The subproblems are solved again according to the updated multipliers. The process continues until one of the stopping criteria is met. The upper bounds coming from subproblem solutions generally fluctuate. The one with the lowest value, , is kept as the best upper bound. The Lagrange multipliers that find are noted as the best multipliers. and 1- are chosen as the current and best multiplier weights, respectively where is the number of improvements in the value and is the number of current iteration of the Dantzig Wolfe decomposition algorithm. The best multiplier weights are increased with the number of iterations and improvements. This ensures convergence of the algorithm. If the value of exceeds , the coefficient of the current multiplier is set to to keep the current multiplier effect above a threshold. The optimal dual variable values corresponding to the relaxed constraints for to the linear relaxation of the original hybrid model are selected as the initial multiplier values. The algorithm is iterated until the difference between and is less than a given small positive value ∈ , i.e., - or until the time limit is reached. The Dantzig–Wolfe column generation algorithm used to solve the LD problem is summarized in Algorithm 1 , and the flowchart of the algorithm is given in Fig. 2 . The next section will explain how feasible solutions for hybrid model are generated from the optimal solutions of the subproblems at each step of the algorithm. Fig. 2. Open in a new tab Flowchart of the proposed Lagrangian relaxation based Dantzig–Wolfe column generation algorithm. Algorithm 1. Open in a new tab Dantzig–Wolfe Column Generation Algorithm. Generation of the feasible solutions Optimal solutions of the subproblems are obtained at each iteration of the algorithm. For instance, the continuous variables values are obtained from , the variable values belonging to the sensor locations ( ) and activity schedules ( ) come from , the variable value representing the sink location ( ) is obtained from , the variable value showing the direction of the primary flow of data ( ) is obtained from , the central sensor location variable value ( ) is obtained from ) and the variable value indicating whether data generated by sensor k is transmitted through a central node ( ) is obtained from . However, these variables do not necessarily form a feasible solution for the hybrid model and are not expected to satisfy the relaxed constraints. To obtain a feasible solution, we start with the binary variable values ( and ) and try to obtain the closest values that satisfy the constraints. To this end, the decision variables and are defined, respectively, as the closest and feasible binary variables and . The model called the Coverage and Budget Model (CBM) given below is used to determine the values of the variables. The variable values (i.e., the values of and ) coming from the solution of subproblem 2 are entered as input in the CBM formulation. We define the variables and to represent the changes in the and values, respectively. The CBM formulation is presented below. 91 subject to 92 93 94 95 96 97 98 99 100 The objective function (91) of the CBM aims to minimize the changes in the values of and . As a reminder, note that and values coming from are treated as parameters (not variables) in CBM formulation. To ensure that the and to satisfy the scope, budget and activity constraints, constraints (92), (93) and (94) were added to the CBM model, similar to constraints (6), (7) and (8). Constraints (95) and (96) ensure that is at least 1 if the values of and are different. Since the objective function’s goal is minimization, the value of will be equal to 1 if and are different. On the other hand, if the values of and are the same, then is satisfied, and since minimization is the goal, is equal to 0. Similarly, if the values of and are different, they are set to 1 by (97) and (98), and to 0 otherwise. The variable is defined to satisfy the relevant constraints for the binary variable . A model called the Flow Direction Model (FDM) was developed to find the value of the variable. The variable is obtained by solving the subproblem. It is then included as an input parameter in the FDM formulation. We define the variable to represent the change in the value. The FDM formulation is presented below. 101 subject to 102 103 104 105 106 The objective function of FDM (101) aims to minimize the change in the value of . To constrain the variable to determine the primary and secondary flow paths, constraint (102) is added to the FDM model, similar to constraint (15). With constraints (103) and (104), the value is if the and values are different, and if they are the same. For binary variables and , a model called the Central Node Model (CNM) is developed. The decision variables and were defined as the closest feasible binary variables and , respectively. The parameters and are obtained by solving the and subproblems. They are entered as input parameters in the CNM formulation. We define the variables and to represent the changes in the and values, respectively. The CNM formulation is presented below. 107 subject to 108 109 110 111 112 113 114 115 116 The objective function (107) of the CBM aims to minimize the changes in the values of and . The constraints (108), (109), and (110) are added to CNM, respectively, to satisfy the constraint (23) that directs the primary flow through central node , and the constraints (26) and (27) that limit the minimum data flow for central node . The value of is set to 1 by (111) and (112) if the values of and are different, and to 0 otherwise. Similarly, the value of is set to 1 by (113) and (114) if the values of and are different, and to 0 otherwise. In the CBM, FDM and CNM formulations, the variables , , and , which represent the changes in , , and are minimized in the objective functions, and the closest , , , and values to , , and are tried to be found. The values { , , }, { , and obtained from the optimal solution of CBM, FDM, CNM and , respectively, are then fixed in the hybrid model and the remaining LP is solved for only continuous decision variables and . , which is the result of the LH method, is obtained as the objective function value of the determined feasible solution. Figure 3 shows a flowchart illustrating how feasible solutions can be generated from subproblems using CBM, FDM, and CNM. Fig. 3. Open in a new tab Generating feasible solutions from subproblems using CBM, FDM, and CNM. Time complexities of the proposed methods It is not possible to have a polynomial-time exact solution algorithm for NP-hard problems with computational complexity. Commercial solutions are not as efficient as heuristic-based methods in solving medium and large-scale mixed integer programming models with a large number of binary decision variables 23 . The Gurobi solver used for the solution of our mixed integer programming model operates on an LH-based branch-and-cut basis. The solution time increases exponentially and depends on the number of nodes visited in the branch-and-cut tree and the number of iterations of LP relaxations solved at each node. In another study, it was mentioned that MILP problems are considered NP-hard problems and that as the size of the problem increases, the number of related combinations for possible solutions can increase nonlinearly (exponentially, etc.). In this way, reaching the optimum solution of the problems becomes difficult 45 . The method we applied is an application of the method discussed in Wentges’, to our Hybrid strategy model 44 . In Wentges’ work, the Lagrangian Dual Problem, generated for a general integer program model, is solved using the Weighted Dantzig–Wolfe decomposition method. Wentges’ work specifies the convergence properties of the applied algorithm and shows that it converges to optimal Lagrangian multipliers. However, a time complexity analysis of the algorithm is not presented. Therefore, since our LH method is a much more complex application of Wentges’ work, we cannot present a time complexity analysis. However, although our work ultimately provides a framework for optimally solving the Lagrangian Dual problem and finding the multipliers, our main focus is not on finding optimal multipliers, but on using the procedure intuitively by generating a feasible solution from Lagrangian subproblems at each step of the LH. Numerical results This section presents the numerical analyses performed on the implementation of the developed strategies and the proposed solution method. First, creation of the test problems are explained, and the parameters used in the performance evaluation of the SC, DC, and H strategies are defined. Each strategy is then examined in terms of key performance metrics such as network lifetime, solution time, and network reliability. Finally, numerical results are presented for the Lagrange heuristic method to ensure that it can produce good feasible solutions for larger problems in tolerable computation times. Creating a test problem and selecting parameters The determination of the parameters used in the formulation of the strategies and the creation of test instances are explained below. The candidate sensor locations are arranged to be located on the intersection points of a grid structure. The dimensions of the grid are chosen to be as close as possible to the square structure of the area. For example, the grid dimensions for the 30 and 90 sensor candidate locations are determined as and , respectively. In this context, the created grid structure is called the “sensor grid”. It is assumed that the sink locations will have a similar grid pattern, thus ensuring that the sensor and sink grids exhibit an intertwined structure. The size of this structure, which we may also call the "sink grid," is obtained by multiplying the vertical and horizontal dimensions of the sensor grid by one minus one. For example, in a grid area with 30 sensor candidate locations, there are 20 candidate sink visit locations of size . The sink locations are determined as the centroid points of the sensor grids. The neighborhood distance between candidate sensor locations is assumed to be 60 m, and the horizontal and vertical distances between the sink visit locations are also assumed to be 60 m. In addition, the sensing and transmission distance of each sensor is assumed to be 75 and 100 m, respectively. These values are compatible with real sensor specifications and implementations from the literature. We also assume that the points that have to be covered by the sensors, which we call coverage points, coincide with the sink visit locations. Different coverage requirements are set for each coverage point. An example sensor and sink grid structure is visually presented in Fig. 4 . Fig. 4. Open in a new tab A sensor network with sensors, mobile sinks, and data flows. Figure 4 shows an example network with a grid structure, 20 candidate visit points, two sinks, and 30 candidate sensor locations. The candidate sensor and sink locations, located sensors and sinks, the sensors in active and standby modes, and the data flow paths during the network’s two-period network lifetime are graphically presented. The coverage points are the same with the sink visit points. Each coverage point is assumed to have coverage requirement by at least two sensors at each time period. Recalling that the distance between the sensors and the sensing and transmission distance of each sensor are 60, 75 and 100 m respectively, the sensor network shown in the figure meets these coverage requirements. Furthermore, in the given network, some sensors transmit their data to the sensors, while others relay their data to neighboring sensors. In this way, an appropriate network design is obtained by optimizing the active/standby modes and data transmission paths of the sensors. A total of 15 different sample sizes were designed, consisting of candidate sensor locations of 9, 20, 30, 40, 50, 60, 70, 80, 90, 100, 125, 150, 175, 200, and 250. For each sample size, three different problem sets are created, where only the coverage requirements ( ) of the locations were randomly varied. The values of the test parameters used in the study are listed in Table 5 . Table 5. Test parameters. Parameters Values 4096 bit/hour joule joule ( joule joule ) ( joule joule ) joule 1 for , 2 for , and 3 for Randomly determined within ~ Allowed computation timer 3 h Open in a new tab Energy consumption values are based on the parameters recommended in Heinzelman et al. and Türkoğulları et al. 3 , 43 . The energy consumed during sensing ( ) and receiving ) operations is constant and is set at joules for both parameters. and vary depending on the Euclidean distance , between the transmitter–receiver sensors and the transmitter sensor and the sink. The total initial energy available to the sensors is taken as 42,624 J. The required sink quantity ( ) varies depending on the number of sensors. The value is set to 1 for , to 2 for , and is set to 3 for . The number of sensors that need to monitor coverage point c ( ) is randomly determined within the set {0,1,2,3}. The cost of placing a sensor at point ( ) is uniformly distributed between 1 and 10. The total sensor placement budget is set to 70% of the sum of the placement costs of all candidate sensors. Performance analysis of SC, DC and H strategies To analyze the impact of the developed strategies on network lifetime and network reliability, the SC, DC and H formulations are coded in C# in the Visual Studio environment and solved by the state-of-the-art MILP solver Gurobi for the above mentioned problem instances. All tests are conducted on an Intel Core i7-4770 quad-core CASPER computer with 8 GB of RAM. The flowchart showing the process of using the Gurobi solver is presented in Fig. 5 . Fig. 5. Open in a new tab The flowchart of the Gurobi solver usage process. Performance of SC, DC and H strategies with respect to network lifetime A maximum computation time of three hours is given for each test instance for each of the three formulations. If the solver reaches the optimal solution in less than three hours, it is reported immediately. The network lifetimes obtained for all three formulations are presented in Table 6 . This table includes the problem sizes ( , ), calculated network lifetimes ( , , and for SC, DC, and H strategies, respectively), percentage deviations from the optimal solution ( , , ), and computation times ( , , ) for each strategy. Table 6. Performances of the SC, DC and H formulations in terms of network lifetime. Instance Network Lifetimes (Hours) Percent Deviations (%) Computation Time (Second) ) (9,4) 31786.30 14753.50 31786.30 0.00 0.00 0.00 1.27 44.79 7.80 (9,4) 41395.36 21110.63 41395.36 0.00 0.00 0.00 3.90 44.41 35.04 (9,4) 50000.00 40404.41 50000.00 0.00 0.00 0.00 0.75 8.50 0.53 (20,12) 28826.92 13076.28 28826.92 0.00 17.29 2.64 2836.11 10800.19 10801.69 (20,12) 36588.77 17015.08 36588.77 0.00 7.00 0.17 1146.34 10800.19 10800.25 (20,12) 49992.05 27027.33 49992.05 0.02 7.70 0.02 10800.22 10800.28 10800.13 (30,20) 17766.72 6796.33 17740.80 9.04 23.90 11.70 10801.01 10801.50 10801.06 (30,20) 24803.95 8723.97 24776.79 5.45 28.36 6.40 10800.55 10800.52 10800.88 (30,20) 22937.20 8509.62 23098.25 7.32 26.76 7.53 10800.54 10800.30 10,800.49 (40,28) 17893.80 6791.05 16765.49 25.08 40.67 37.64 10801.11 10800.34 10801.11 (40,28) 21616.32 7296.38 19444.52 23.40 45.43 34.50 10800.99 10801.52 10805.89 (40,28) 20870.20 7660.67 20444.51 21.33 39.90 24.37 10800.83 10800.52 10800.41 (50,36) 12064.87 3662.52 5474.48 41.08 64.61 73.55 10801.22 10800.61 10801.88 (50,36) 17984.74 4431.89 11164.46 30.83 64.83 59.52 10801.60 10800.72 10820.89 (50,36) 18445.80 6864.44 13973.88 39.42 57.40 57.61 10801.33 10800.48 10800.69 (60,45) 12159.02 2613.02 2898.32 40.22 75.54 90.92 10803.26 10803.13 10801.53 (60,45) 13517.27 2856.84 7762.87 42.44 75.22 69.90 10803.06 10800.57 10804.50 (60,45) 10179.04 3029.02 7840.69 49.82 72.30 64.68 10801.79 10802.34 10802.86 (70,54) 6682.69 0.00 0.00 51.50 100.00 100.00 10802.68 10800.30 10802.54 (70,54) 9959.98 0.00 3063.13 51.91 100.00 86.05 10803.94 10800.87 10800.59 (70,54) 11585.68 0.00 447.14 32.62 100.00 97.49 10802.77 10813.81 10800.45 (80,63) 3469.75 0.00 0.00 74.87 100.00 100.00 10804.12 10801.49 10801.94 (80,63) 5032.98 0.00 0.00 58.52 100.00 100.00 10804.25 10802.89 10803.05 (80,63) 6451.26 0.00 0.00 68.52 100.00 100.00 10803.40 10803.89 10800.59 (90,72) 4480.59 0.00 0.00 72.02 100.00 100.00 10805.52 10800.66 10806.07 (90,72) 4803.37 0.00 0.00 69.88 100.00 100.00 10805.60 10801.32 10801.18 (90,72) 4448.81 0.00 0.00 72.97 100.00 100.00 10804.54 10805.15 10802.38 (100,81) 3875.79 0.00 OOM 76.26 100.00 NA 10805.09 10801.00 NA (100,81) 5024.73 0.00 0.00 77.12 100.00 100.00 10805.89 10801.60 10801.16 (100,81) 3812.74 0.00 0.00 83.93 100.00 100.00 10805.40 10802.14 10802.40 (125,96) 3867.15 0.00 OOM 77.49 100.00 NA 10808.37 10801.07 NA (125,96) 3145.24 0.00 OOM 86.02 100.00 NA 10808.19 10803.36 NA (125,96) 1057.06 0.00 OOM 95.18 100.00 NA 10807.80 10803.60 NA (150,126) 0.00 OOM OOM 100.00 NA NA 10810.59 NA NA (150,126) 1944.84 OOM OOM 86.01 NA NA 10815.18 NA NA (150,126) OOM OOM OOM NA NA NA NA NA NA (175,144) 0.00 OOM OOM 100.00 NA NA 10814.29 NA NA (175,144) 0.00 OOM OOM 100.00 NA NA 10818.06 NA NA (175,144) OOM OOM OOM NA NA NA NA NA NA (200,171) 0.00 OOM OOM 100.00 NA NA 10819.49 NA NA (200,171) 0.00 OOM OOM 100.00 NA NA 10848.37 NA NA (200,171) OOM OOM OOM NA NA NA NA NA NA (250,216) 0.00 OOM OOM 100.00 NA NA 10837.56 NA NA (250,216) OOM OOM OOM NA NA NA NA NA NA (250,216) OOM OOM OOM NA NA NA NA NA NA Open in a new tab The results show that network lifetime decreases as the instance size increases for all three strategies. This is due to two reasons: First, even if the network’s observation area expands, the initial energy level of the sensors remains the same. In larger networks, the distances to the sinks, and therefore the average energy consumed for data transmission, are greater, leading to rapid energy dissipation. Second, as the network size grows, the total amount of data generated will also increase. Therefore, sensors in larger networks must transmit more data over longer distances with the same amount of energy. When comparing the strategies, the SC strategy provides the longest network lifetime. However, the DC strategy, developed to increase network reliability, is observed to significantly reduce network lifetime compared to the SC strategy. Therefore, the H strategy, developed to both maximize network lifetime and increase network reliability, provides a balanced solution by providing network lifetime values close to the SC strategy. Figure 6 shows how the network lifetime values obtained by averaging the 3 instances for each sensor grid size by different strategies (SC, DC, and H) vary depending on the number of candidate sensor locations. Fig. 6. Open in a new tab Network Lifetime Change according to the number of candidate sensor locations (SC, DC, H). The deviation percentage from the best upper bound found is obtained by calculating the distance between the objective function value of the current solution (i.e., the network lifetime value) and the best upper bound reported by the solver. While this value exhibits low deviations in small-sized instances for all three strategies, the deviations increase significantly as the instance size increases. This can be explained as follows: As the sample size increases, the problem becomes more and more complex. Consequently, the solver must search a much larger solution space. This, in turn, widens the gap between the current objective function value and the upper bound. Figure 7 shows the percentage deviations of all three strategies relative to the optimal solution to assess solution quality. The SC strategy has low deviation rates on small instance sizes, while deviations increase significantly as the instance size increases. The DC strategy offers the lowest solution quality, with high deviation rates across all dimensions. While the H strategy yields similar results compared to SC on medium-sized instance sizes, it fails to maintain its performance on large instance sizes, and its deviation rates increases. These results demonstrate that the computational capacity of the strategies is limited by the instance size and that more effective heuristic approaches are needed for large-sized examples. Fig. 7. Open in a new tab Percent deviation change according to the number of candidate sensor locations (SC, DC, H). In terms of computation time, all strategies produce solutions up to a certain instance size in a maximum of 10,800 s (3 h). However, as the instance size increases, the solution-generating capacity of each strategy decreases, and after a certain point, an "Out of Memory" (OOM) error is encountered. Accordingly, in cases where no solution can be produced, computation times are not calculated and are designated as “Not Applicable” (NA). Finally, the H strategy performed worse than the SC strategy but better than the DC strategy in terms of network lifetime performance. Performance of SC, DC and H formulation with respect to network reliability A reliable network is expected to deliver all the data generated by all deployed sensors to the sink. We create six different scenarios to evaluate the reliability of networks adopting different strategies. In each of the scenarios, a list of the candidate damaged sensors or a list of the candidate damaged connections is created at the beginning. Note that each deployed sensor is a candidate for being a damaged sensor, and each connection between deployed sensors/sinks is a candidate for being a damaged connection. Data flow routes and the amount of data passing through these routes are determined for all periods. The total amount of data transmitted across all routes is calculated the sum of the data generated by the source sensor on each route that must be transmitted to the sink. Then, according to the rules for each scenario, the “damaged sensor” or “damaged connections” is determined by varying degrees of damage to specific sensors or data transmission paths. The data from routes using the identified damaged sensor or connections is called “damaged data”. The net data (received data) collected at the sinks through each route represents the remaining amount of data obtained by subtracting the damaged data from the total data. Network reliability rates are then calculated by , where target data represents the total amount of data that deployed sensors are expected to generate under normal operating conditions (without multiple copies) in each period. Scenarios are classified into two main groups for evaluating network reliability through both sensors and data transmission paths (connections): Scenarios based on sensors: Four scenarios are generated based on the sensor damage reactions. In Scenario 1 according to a pre-determined percentage ratio level, a subset of the deployed sensors is randomly chosen as the damaged sensors. The damaged data is obtained by summing the data generated by the damaged sensors throughout the whole network lifetime. Network reliability is then calculated. Scenario 2 is similar to Scenario 1 but the damaged sensor is not assumed to be damaged throughout the whole lifetime but after a randomly selected period. The impact of the data carried by routes containing the damaged sensor during the given period on reliability over the entire network lifetime is then measured. A scenario of type Scenario 1 and Scenario 2 assumes that the density of sensors constituting the network is equal. Since each sensor is chosen for damage with equal probabilities. Scenario 3 and Scenario 4 are similar to Scenario 1 and Scenario 2 respectively, but the probability of a sensor being damaged is obtained by dividing the number of neighbors of each sensor by the total number of neighbors. Hence, selection probability of a sensor is proportional to the number of its neighbors causing the central nodes prone to damage more. The number of damaged sensors is determined by a certain damage ratio of the total number of deployed sensors. Additionally, according to Scenario 4, a damaged sensor is assumed to become damaged after a randomly selected period. A scenario like Scenario 3 and Scenario 4 can be used to determine how network reliability is affected when the network is not homogeneous. (2) Scenarios based on connections: Two scenarios are generated based on the connection damage reactions. In In Scenarios 5 and Scenarios 6, the connections consisting of sensor to sensor or sensor to sink in all data flow routes are listed. According to a pre-determined percentage ratio level, a subset of these links is randomly selected as damaged connections. The route containing the relevant connection is considered damaged, and network reliability is measured based on the amount of damaged data it carries. Additionally, according to Scenarios 6, a damaged connection is assumed to become damaged after a randomly selected period. With scenarios like Scenarios 5 and Scenarios 6, it is possible to determine how damage to communication paths, independent of sensors and sinks, affects network reliability. Through these scenarios, the effects of multicopy strategies on reliability are evaluated in detail by analyzing the network’s resilience to damage and the changes in data transmission performance. An example of how the scenarios is implemented is presented in Fig. 8 , Table 7 and Fig. 9 for a network with a DC strategy. Figure 8 presents a network view of a data flow with 20 candidate sensor locations ( dimensions). The direction of data flow transmitted through this structure is graphically illustrated through the connections in the network. Fig. 8. Open in a new tab Data flow at time in DC with 20 candidate sensor locations ( dimensions). Table 7. Data flow routes. The data flow Route 1 16,350,065 S5-S6-Sink5 1 16,350,065 S5-Sink5 1 16,350,065 S6-Sink5 1 16,350,065 S6-S5-Sink5 1 458,026 S7-S6-Sink5 1 15,892,038 S7-Sink3 1 16,350,065 S7-S3-Sink 3 1 16,350,065 S8-Sink3 1 16,350,065 S8-S3-Sink3 1 16,350,065 S9-Sink3 1 16,350,065 S9-S3-Sink3 1 16,350,065 S11-Sink5 1 16,350,065 S11-S5-Sink5 1 11,806,010 S12-S7-Sink3 1 4,800,020 S12-S11-Sink5 1 11,550,044 S12-Sink7 1 4,544,055 S12-S7-Sink7 1 16,350,065 S13-Sink7 1 16,350,065 S13-S7-Sink7 1 16,350,065 S14-S8-Sink3 1 16,350,065 S14-S9-Sink3 Open in a new tab Fig. 9. Open in a new tab Reliability performances of three strategies (SC, DC and H) with the application of six different damage scenarios. Table 7 shows the amount of data flow paths (routes) created by the sensors and reaching the sink at time for a network with a DC strategy. This transparently demonstrates the total data flow occurring in the network and the connections through which this flow occurs. Note that in the routes means the sensor placed at candidate sensor location , while means the sink that is at the sink visit location. Table 8 examines the effects of different damage scenarios on the data flow routes given in Table 7 . Different damage types are applied to the same network structure in different column groups, calculating the total data, damaged data, data flow, and target data. Here, what we mean by target data is the total amount of data produced by the distributed sensor throughout the life of the network, without the need for any replication. The data flow cells of the routes traversed by the damaged sensor are shown in bold. In the first scenario in the figure, it is assumed that 20% of the sensors, for instance randomly selected sensors S6 and S7, are damaged, and accordingly, 100% reliability is achieved based on the ratio of the data that can be delivered to the target data amount. The second scenario also yields the same result, with a different 20% of the network, namely sensors S6 and S8, being damaged. In the third scenario, under the assumption that 30% of the network, namely sensors S6, S7, and S8, are damaged, further data loss occurs, and the reliability rate drops to 89%. These calculations reveal how data transmission performance changes when specific sensors on the network are damaged, and how reliability can be maintained with data replication strategies. As a result, network reliability depends directly on the critical sensor structures, network topology and transmission strategies used. Table 8. Calculation of reliability rate according to damages on routes. t The data flow Route t The data flow Route t The data flow Route 1 16,350,065 S5-S6-Sink5 1 16,350,065 S5-S6-Sink5 1 16,350,065 S5-S6-Sink5 1 16,350,065 S5-Sink5 1 16,350,065 S5-Sink5 1 16,350,065 S5-Sink5 1 16,350,065 S6-Sink5 1 16,350,065 S6-Sink5 1 16,350,065 S6-Sink5 1 16,350,065 S6-S5-Sink5 1 16,350,065 S6-S5-Sink5 1 16,350,065 S6-S5-Sink5 1 458,026 S7-S6-Sink5 1 458,026 S7-S6-Sink5 1 458,026 S7-S6-Sink5 1 15,892,038 S7-Sink3 1 15,892,038 S7-Sink3 1 15,892,038 S7-Sink3 1 16,350,065 S7-S3-Sink 3 1 16,350,065 S7-S3-Sink 3 1 16,350,065 S7-S3-Sink 3 1 16,350,065 S8-Sink3 1 16,350,065 S8-Sink3 1 16,350,065 S8-Sink3 1 16,350,065 S8-S3-Sink3 1 16,350,065 S8-S3-Sink3 1 16,350,065 S8-S3-Sink3 1 16,350,065 S9-Sink3 1 16,350,065 S9-Sink3 1 16,350,065 S9-Sink3 1 16,350,065 S9-S3-Sink3 1 16,350,065 S9-S3-Sink3 1 16,350,065 S9-S3-Sink3 1 16,350,065 S11-Sink5 1 16,350,065 S11-Sink5 1 16,350,065 S11-Sink5 1 16,350,065 S11-S5-Sink5 1 16,350,065 S11-S5-Sink5 1 16,350,065 S11-S5-Sink5 1 11,806,010 S12-S7-Sink3 1 11,806,010 S12-S7-Sink3 1 11,806,010 S12-S7-Sink3 1 4,800,020 S12-S11-Sink5 1 4,800,020 S12-S11-Sink5 1 4,800,020 S12-S11-Sink5 1 11,550,044 S12-Sink7 1 11,550,044 S12-Sink7 1 11,550,044 S12-Sink7 1 4,544,055 S12-S7-Sink7 1 4,544,055 S12-S7-Sink7 1 4,544,055 S12-S7-Sink7 1 16,350,065 S13-Sink7 1 16,350,065 S13-Sink7 1 16,350,065 S13-Sink7 1 16,350,065 S13-S7-Sink7 1 16,350,065 S13-S7-Sink7 1 16,350,065 S13-S7-Sink7 1 16,350,065 S14-S8-Sink3 1 16,350,065 S14-S8-Sink3 1 16,350,065 S14-S8-Sink3 1 16,350,065 S14-S9-Sink3 1 16,350,065 S14-S9-Sink3 1 16,350,065 S14-S9-Sink3 Total data 294,301,168 Total data 294,301,168 Total data 294,301,168 Damaged data 114,450,454 Damaged S6 and S7 Damaged data 98,558,416 Damaged S6 and S8 Damaged data 163,500,649 Damaged S6, S7 and S8 Received data 179,850,714 Received data 195,742,752 Received data 130,800,519 Target data 147,150,584 Target data 147,150,584 Target data 147,150,584 Reliability Rate 179,850,714 > 147,150,584 Reliability Rate 195,742,752 > 147,150,584 Reliability Rate 130,800,519 < 147,150,584 100% 100% 89% Open in a new tab Figure 9 shows the reliability performance of the three proposed strategies (SC, DC, and H) with respect to different damage rates under six different damage scenarios. When the damage ratio is gradually changed from 10 to 80%, reliability rates decrease across all strategies. However, the reduction rates and level differences vary across strategies. While the SC strategy offers acceptable reliability at low damage ratios, the system’s resilience decreases significantly as the damage ratio increases. The reliability ratio drops sharply, particularly for damage ratios of 50% and above. This result demonstrates that the SC strategy remains weak in terms of network reliability. The DC strategy achieves the highest reliability values across all scenarios and maintains stability at certain levels despite damage ratios reaching up to 80%. This demonstrates that the DC strategy is highly resilient to damage scenarios thanks to its multicopy data transmission mechanism. However, as noted in previous analyses, this reliability increase has a negative impact on network lifetime. The H strategy, with its structure aimed at striking a balance between network lifetime and reliability, produces higher reliability values compared to SC and higher network lifetime values compared to DC. The H strategy demonstrates balanced and sustainable performance, particularly at moderate damage ratios (e.g., 30–50%). In Strategy H, data replication occurs only where data flow is high and the presence of a central sensor is important. Table 9 summarizes the contribution of the presence of a central sensor used in strategy H to both network lifetime and network reliability. Table 9. Average contribution of a central node to lifetime and reliability. ) (9,4) (20,12) (30,20) (40,28) (50,36) (60,45) Increase in network lifetime (%) Compared to DC 38.08 50.51 63.38 61.61 51.14 54.06 Increase in network reliability (%) Compared to SC 15.04 13.75 5.14 15.39 11.99 29.70 Open in a new tab As seen in Table 9 , the first row shows the percentage increase in network lifetime achieved by the H strategy compared to the DC strategy. According to the results, a significant increase in network lifetime is achieved for instance sizes between (9,4) and (60,45). The highest increase, 63.38%, is achieved in the (30,20) instance. This indicates that employing central nodes reduces communication load by balancing energy consumption and contributes to a longer network lifetime. The second row presents the percentage increase in network reliability that the H strategy brings compared to the SC strategy. The results indicate a positive contribution. The highest reliability increase, 29.70%, is achieved in the (60,45) example. This indicates that the central sensor reduces data loss in the event of damage by increasing the diversity of data flow paths and alternative routing possibilities. The SC, DC, and H strategies do not produce a common positive result in the (70, 54) and larger instances. Therefore, the benefit of using a central sensor could not be measured in the specified large-sized instances. While the SC strategy is the most suitable option for networks seeking to maximize network lifetime, the DC strategy is more suitable for networks seeking to increase network reliability. However, as noted, the DC strategy significantly reduces network lifetime while SC strategy leads to low network reliability issues. The H strategy offers an alternative for networks seeking to balance both network lifetime and reliability. While the H strategy offers a balanced solution for small and medium-sized instances, it requires further development in terms of computational power for large-sized instances. To this end, the LH approach is supported to achieve solutions to large-sized instances in reasonable time. Performance of the Lagrangian heuristic Here, we illustrate of the performance of LH by running Gurobi and LH on the same problem instances. For each problem instance, Gurobi and LH are allowed to run for a maximum of 3 h. The maximum network lifetimes found during this time are presented in Table 10 . The first column of the table contains the number of candidate sensor and sink locations. The second and third columns present the maximum network lifetimes found by the Gurobi and LH, respectively, for the corresponding test samples. The fourth column shows the percentage deviations between the Gurobi and LH results. The mathematical formulation is used for the percentage deviations. Here, and represent the maximum network lifetimes found by the Gurobi and LH, respectively. Additionally, the performance of the Gurobi solver and Lagrange heuristic method is visually presented in Fig. 10 depending on the average lifetimes. The percentage deviations between the Gurobi and Lagrange heuristic methods are also plotted in Fig. 11 . Table 10. Network lifetimes obtained from Gurobi and LH methods for strategy H. Instance Network lifetimes (h) Percent deviations (%) Computation time (s) ) (9,4) 31786.30 31786.30 0.00 7.80 9947.25 (9,4) 41395.36 41395.36 0.00 35.04 10800.26 (9,4) 50000.00 50000.00 0.00 0.53 12.08 (20,12) 28826.92 28826.92 0.00 10801.69 10805.95 (20,12) 36588.77 36588.77 0.00 10800.25 10800.20 (20,12) 49992.05 49992.05 0.00 10800.13 10800.48 (30,20) 17740.80 17740.80 0.00 10801.06 10813.79 (30,20) 24776.79 24776.79 0.00 10800.88 10805.99 (30,20) 23098.25 23098.25 0.00 10800.49 10800.74 (40,28) 16765.49 17507.93 4.24 10801.11 10814.62 (40,28) 19444.52 22121.59 12.10 10805.89 10802.23 (40,28) 20444.51 20437.15 -0.04 10800.41 10801.14 (50,36) 5474.48 7200.00 23.97 10801.88 10814.96 (50,36) 11164.46 13322.16 16.20 10820.89 10807.22 (50,36) 13973.88 13425.85 -4.08 10800.69 10810.94 (60,45) 2898.32 5625.00 48.47 10801.35 10800.00 (60,45) 7762.87 7762.87 0.00 10804.50 10804.48 (60,45) 7840.69 7840.69 0.00 10802.86 10808.86 (70,54) 0.00 4615.38 100.00 10802.54 10800.03 (70,54) 3063.13 3063.13 0.00 10804.53 10800.59 (70,54) 447.14 447.14 0.00 10800.45 10805.77 (80,63) 0.00 2179.78 100.00 10801.94 10803.61 (80,63) 0.00 411.78 100.00 10828.89 10808.26 (80,63) 0.00 0.00 0.00 10800.59 10805.14 (90,72) 0.00 3724.03 100.00 10806.07 10800.00 (90,72) 0.00 0.00 0.00 10801.18 10807.48 (90,72) 0.00 0.00 27.58 10802.38 10815.44 (100,81) OOM 3201.32 NA NA 10800.63 (100,81) 0.00 OOM NA 10801.16 NA (100,81) 0.00 OOM NA 10802.40 NA Open in a new tab Fig. 10. Open in a new tab Change of network lifetime according to the number of candidate sensor locations (Gurobi, LH). Fig. 11. Open in a new tab Change of percentage deviation according to the number of candidate sensor locations (Gurobi, LH). As shown in Table 10 , the comparison of the LH method with the Gurobi solution is presented by analyzing it in networks with 15 different sample sizes and different coverage requirements. Both solution methods consume all the computation time allocated for all samples except the smallest sample with candidate sensor locations. Furthermore, while both methods produce the same results on average for 9, 20, and 30 candidate sensor locations, the Lagrangian heuristic method yields higher values than the Gurobi solver as the network size increases. In small-scale network problems, the consistency of the proposed LH method with the best solution found by Gurobi in similar computation times demonstrates that the LH method is also successful in finding the optimal solution for the NP-hard WSN design problem. In networks of 40 and larger, the mathematical model becomes more complex, making the problem more difficult to solve. In this case, the LH approach produces a better network lifetime than Gurobi. Additionally, after 80 candidate sensor locations, the Gurobi solver cannot produce a positive lifetime result. Therefore, in realistic WSN design applications, the Gurobi solver is not an alternative for large-scale networks with more than 80 candidate sensor locations. Consistent with the results in Table 10 , Fig. 10 shows that the LH method provides higher network lifetime compared to H, especially for medium and large-scale networks, depending on the sample size. This is also supported by the percentage deviation values presented in Fig. 11 . Based on the results, considering only network lifetime (objective function value) and solution quality, we can say that the LH method offers better performance than Gurobi. However, in terms of computation time, the LH method is not faster than Gurobi. Furthermore, the consistency of the network lifetimes offered by the Gurobi and LH approaches at small sample sizes and similar computation times proves that the obtained results are correct. While the proposed hybrid strategy has numerous limitations, the LH method is a good alternative for real-world applications because it searches for an optimal solution by moving from the current feasible solution to the neighboring solution and is amenable to random changes. Conclusion In this study, we first introduce the SC strategy, which addresses four fundamental WSN design problems in an integrated manner. Since network reliability is not directly considered in the strategy, constraints to ensure network reliability are incorporated. Thus, three different strategies, SC, DC, and H, have been developed. The basic model, in which data transmission is performed using only primary paths, was defined as the SC strategy. To increase network reliability and data transmission continuity, the model, in which data is copied and transmitted via primary and secondary paths, was developed as the DC strategy. Finally, in order to increase network reliability and extend network lifetime, the H strategy is modeled, which performs data replication on the resources that provide data transmission to critical nodes with high data density. The performances of the strategies were evaluated using scenarios developed in terms of network lifetime and reliability. A network with the SC strategy demonstrated the highest performance in terms of lifetime. A network with the DC strategy, in which data transmission is performed via multiple paths, was found to have the highest reliability. A balanced result in both network lifetime and network reliability was obtained from the H strategy. A column generation heuristic was developed to achieve solutions to large-scale instances in reasonable time using the H strategy. For this purpose, some constraints of the H strategy model were relaxed and incorporated into the objective function. The relaxation decomposed the model into seven Lagrangian subproblems. The Dantzig–Wolfe column generation algorithm, first developed by Wentges, was used to solve the problem 44 . The obtained decision variable values were then used to generate a suitable solution for the H strategy model and satisfy the relaxed constraints, starting with binary variables and finding values that would satisfy the constraints. For this purpose, three different models (CBM, AYM, MDM) and the subproblem model were used. By fixing the obtained binary variables in the H strategy model, the objective function resulting from the continuous variables and the LH was calculated. The performance of the LH is presented by comparing it with the network lifetimes found by Gurobi. This study contributes to the literature by integrating the coverage problem, the sink placement/routing problem, the sensor activity scheduling problem, and the data routing design problems to achieve long network lifetimes in WSNs, and by developing strategies to increase network reliability. In future studies: The performance of the strategies and heuristics in the current study can be analyzed with different strategies and heuristics developed to increase network reliability. A model in which the detection ranges of sensor nodes vary probabilistically can be implemented. A constraint or variable that measures network reliability can be added to the model during the network design phase. In addition to classifying data as primary or secondary, classifying the type of data being generated allows for a more reliable identification of missing (damaged) data. Acknowledgements This article was prepared as part of a thesis. It was also supported by the Atatürk University Scientific Research Projects Coordination Unit with project code AU BAP-FDK-2023-11657. Author contributions EÇ: Writing—review & editing, Investigation, Formal analysis, Data curation, Conceptualization. MEK: Writing—review & editing, Methodology, Software. Both authors reviewed the results and approved the final version of the manuscript. Data availability The datasets generated and analyzed during the current study are available at Zenodo: (10.5281/zenodo.19135285). The code generated during the current study are publicly available in the GitHub repository: ( https://github.com/esraaclk64-collab/wsn-rln-article-gurobi-csharp -). It is also archived at Zenodo: (10.5281/zenodo.19135285). Code availability The code generated during the current study are publicly available in the GitHub repository: ( https://github.com/esraaclk64-collab/wsn-rln-article-gurobi-csharp - ). It is also archived at Zenodo: (10.5281/zenodo.19135285). Declarations Competing interests The authors declare no competing interests. Footnotes Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. References 1. Yücel, T. & Altın-Kayhan, A. A copy-at-neighbouring-node retransmission strategy for improved wireless sensor network lifetime and reliability. J. Oper. Res. Soc. 70 , 1193–1202. 10.1080/01605682.2018.1475108 (2019). [ Google Scholar ] 2. Torlak, E. Kablosuz sensör ağları için yeni bir ömür tanımı: Bütünleşik karma tamsayılı doğrusal programlama yaklaşımı. MSc thesis, Atatürk Univ. (2018). 3. Türkoğulları, Y. B., Aras, N. & Altınel, İK. Optimal placement, scheduling, and routing to maximize lifetime in sensor networks. J. Oper. Res. Soc. 61 , 1000–1012. 10.1057/jors.2008.187 (2010). [ Google Scholar ] 4. Türkoğulları, Y. B., Aras, N., Altınel, İK. & Ersoy, C. A column generation based heuristic for sensor placement, activity scheduling and data routing in wireless sensor networks. Eur. J. Oper. Res. 207 , 1014–1026. 10.1016/j.ejor.2010.05.020 (2010). [ Google Scholar ] 5. Aznoli, F. & Navimipour, N. J. Deployment strategies in the wireless sensor networks: Systematic literature review, classification, and current trends. Wirel. Pers. Commun. 95 , 819–846. 10.1007/s11277-016-3800-0 (2017). [ Google Scholar ] 6. Altın-Kayhan, A. & Şendil, M. Optimal path selection under different data redundancy policies for energy efficient wireless sensor networks. INFOR Inf. Syst. Oper. Res. 54 , 121–146. 10.1080/03155986.2016.1167316 (2016). [ Google Scholar ] 7. Ekmen, M. & Altın-Kayhan, A. Reliable and energy efficient wireless sensor network design via conditional multi-copying for multiple central nodes. Comput. Netw. 126 , 57–68. 10.1016/j.comnet.2017.06.028 (2017). [ Google Scholar ] 8. Ekmen, M. & Altın-Kayhan, A. A conditional multi-copy strategy with multiple central nodes for more secure wireless sensor networks. Electron. Notes Discrete Math. 52 , 261–268. 10.1016/j.endm.2016.03.035 (2016). [ Google Scholar ] 9. Altınel, İK., Aras, N., Güney, E. & Ersoy, C. Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks. Comput. Netw. 52 , 2419–2431. 10.1016/j.comnet.2008.05.002 (2008). [ Google Scholar ] 10. Serper, E. Z. & Altın-Kayhan, A. Coverage and connectivity based lifetime maximization with topology update for WSN in smart grid applications. Comput. Netw. 209 , 108940. 10.1016/j.comnet.2022.108940 (2022). [ Google Scholar ] 11. Naik, C. & Shetty, D. P. Multi-attribute decision making approach for energy efficient sensor placement and clustering in wireless sensor networks. Telecommun. Syst. 88 , 3. 10.1007/s11235-024-01250-2 (2025). [ Google Scholar ] 12. Boubrima, A., Bechkit, W. & Rivano, H. Optimal WSN deployment models for air pollution monitoring. IEEE Trans. Wirel. Commun. 16 , 2723–2735. 10.1109/TWC.2017.2658601 (2017). [ Google Scholar ] 13. Boubrima, A., Bechkit, W. & Rivano, H. On the deployment of wireless sensor networks for air quality mapping: Optimization models and algorithms. IEEE/ACM Trans. Netw. 27 , 1629–1642. 10.1109/TNET.2019.2923737 (2019). [ Google Scholar ] 14. Guimarães, D. A., Frigieri, E. P. & Sakai, L. J. Influence of node mobility, recharge, and path loss on the optimized lifetime of wireless rechargeable sensor networks. Ad Hoc Netw. 97 , 102025. 10.1016/j.adhoc.2019.102025 (2020). [ Google Scholar ] 15. Amutha, J., Sharma, S. & Nagar, J. WSN strategies based on sensors, deployment, sensing models, coverage and energy efficiency: Review, approaches and open issues. Wirel. Pers. Commun. 111 , 1089–1115. 10.1007/s11277-019-06903-z (2020). [ Google Scholar ] 16. Kuang, Y. et al. Dynamic multi-objective cooperative coevolutionary scheduling for mobile underwater wireless sensor networks. Comput. Ind. Eng. 156 , 107229. 10.1016/j.cie.2021.107229 (2021). [ Google Scholar ] 17. Güney, E., Aras, N., Altınel, İK. & Ersoy, C. Efficient integer programming formulations for optimum sink location and routing in heterogeneous wireless sensor networks. Comput. Netw. 54 , 1805–1822. 10.1016/j.comnet.2010.02.009 (2010). [ Google Scholar ] 18. Keskin, M. E., Altınel, İK., Aras, N. & Ersoy, C. Lifetime maximization in wireless sensor networks using a mobile sink with nonzero traveling time. Comput. J. 54 , 1987–1999. 10.1093/comjnl/bxr048 (2011). [ Google Scholar ] 19. Keskin, M. E. & Yiğit, V. Maximizing the lifetime in wireless sensor networks with multiple mobile sinks having nonzero travel times. Comput. Ind. Eng. 148 , 106719. 10.1016/j.cie.2020.106719 (2020). [ Google Scholar ] 20. Srinivas, M. & Amgoth, T. Data acquisition in large-scale wireless sensor networks using multiple mobile sinks: A hierarchical clustering approach. Wirel. Netw. 28 , 603–619. 10.1007/s11276-021-02845-2 (2022). [ Google Scholar ] 21. Güney, E., Aras, N., Altınel, İK. & Ersoy, C. Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks. Comput. Oper. Res. 39 , 1530–1539. 10.1016/j.cor.2011.09.002 (2012). [ Google Scholar ] 22. Keskin, M. E., Altınel, İK., Aras, N. & Ersoy, C. Wireless sensor network design by lifetime maximisation: An empirical evaluation of integrating major design issues and sink mobility. Int. J. Sens. Netw. 20 , 131–146. 10.1504/IJSNET.2016.075363 (2016). [ Google Scholar ] 23. Türkoğulları, Y. B., Aras, N., Altınel, İK. & Ersoy, C. An efficient heuristic for placement, scheduling and routing in wireless sensor networks. Ad Hoc Netw. 8 , 654–667. 10.1016/j.adhoc.2010.01.005 (2010). [ Google Scholar ] 24. Keskin, M. E., Altınel, İK., Aras, N. & Ersoy, C. Wireless sensor network lifetime maximization by optimal sensor deployment, activity scheduling, data routing and sink mobility. Ad Hoc Netw. 17 , 18–36. 10.1016/j.adhoc.2014.01.003 (2014). [ Google Scholar ] 25. Keskin, M. E., Altınel, İK. & Aras, N. Combining simulated annealing with Lagrangian relaxation and weighted Dantzig–Wolfe decomposition for integrated design decisions in wireless sensor networks. Comput. Oper. Res. 59 , 132–143. 10.1016/j.cor.2015.02.001 (2015). [ Google Scholar ] 26. Keskin, M. E. A column generation heuristic for optimal wireless sensor network design with mobile sinks. Eur. J. Oper. Res. 260 , 291–304. 10.1016/j.ejor.2016.12.006 (2017). [ Google Scholar ] 27. Keskin, M. E. Lifetime maximization of wireless sensor networks with sink costs. Turk. J. Electr. Eng. Comput. Sci. 25 , 4602–4614. 10.3906/elk-1702-107 (2017). [ Google Scholar ] 28. Nguyen, L. & Nguyen, H. T. Mobility based network lifetime in wireless sensor networks: A review. Comput. Netw. 174 , 107236. 10.1016/j.comnet.2020.107236 (2020). [ Google Scholar ] 29. Kundaliya, B. L., Patel, J., Hadia, S. K. & Patel, U. Machine learning in wireless sensor networks. Wirel. Pers. Commun. 137 , 367–397. 10.1007/s11277-024-11413-8 (2024). [ Google Scholar ] 30. Çelik, E., Keskin, M. E. & Yiğit, V. Wireless sensor network design in grid-free structure. Tech. Gaz. 32 , 1798–1809. 10.17559/TV-20241211002189 (2025). [ Google Scholar ] 31. İncebacak, D., Tavlı, B., Biçakcı, K. & Altın-Kayhan, A. Optimal number of routing paths in multi-path routing to minimize energy consumption in wireless sensor networks. EURASIP J. Wirel. Commun. Netw. 2013 , 252. 10.1186/1687-1499-2013-252 (2013). [ Google Scholar ] 32. Stavrou, E. & Pitsillides, A. A survey on secure multipath routing protocols in WSNs. Comput. Netw. 54 , 2215–2238. 10.1016/j.comnet.2010.02.015 (2010). [ Google Scholar ] 33. İncebacak, D., Biçakcı, K. & Tavlı, B. Evaluating energy cost of route diversity for security in wireless sensor networks. Comput. Stand. Interfaces 39 , 44–57. 10.1016/j.csi.2014.12.003 (2015). [ Google Scholar ] 34. Yang, J., Chen, J., Huo, Y. & Liu, Y. A novel cluster-based wireless sensor network reliability model using the Expectation Maximization algorithm. J. Sensors 2021 , 8869544. 10.1155/2021/8869544 (2021). [ Google Scholar ] 35. Persis, J. A novel routing protocol for underwater wireless sensor network using Pareto uninformed and heuristic search techniques. Wirel. Pers. Commun. 121 , 1917–1944. 10.1007/s11277-021-08747-y (2021). [ Google Scholar ] 36. Sun, C. et al. An energy efficient and reliable multipath transmission strategy for mobile wireless sensor networks. Comput. Intell. Neurosci. 2022 , 8083804. 10.1155/2022/8083804 (2022). [ DOI ] [ PMC free article ] [ PubMed ] [ Google Scholar ] 37. Cav, C. & Altın-Kayhan, A. Coverage hole optimization with a mobile sensor in wireless sensor networks for smart grid. Ad Hoc Netw. 140 , 103039. 10.1016/j.adhoc.2022.103039 (2023). [ Google Scholar ] 38. Biswas, K. et al. Lifetime modelling of wireless sensor networks with multipath routing. In Proceedings IEEE International Conference on Pervasive Computing and Communications Workshops 178–183. 10.1109/PerComWorkshops59983.2024.10502447 (IEEE, 2024). 39. Zhen, Y., Peng, Y. Q., Feng, H. & Shi, D. A design and implement of real-time wireless sensor network protocols with relay nodes. In Proceedings of IEEE Wireless Communications and Networking Conference 1–6. 10.1109/WCNC57260.2024.10571201 (IEEE, 2024). 40. Shakhov, V. & Migov, D. On the reliability of wireless sensor networks with multiple sinks. Sensors 24 , 5468. 10.3390/s24175468 (2024). [ DOI ] [ PMC free article ] [ PubMed ] [ Google Scholar ] 41. Shakhov, V., Migov, D., Chen, H., Polina, M. & Koo, I. Towards reliability of long wireless sensor networks. IEEE Access 10.1109/ACCESS.2024.3454367 (2024). [ Google Scholar ] 42. Chen, R. Optimizing wireless sensor network topology with node load consideration. Virtual Real. Intell. Hardw. 7 , 47–61. 10.1016/j.vrih.2024.08.003 (2025). [ Google Scholar ] 43. Heinzelman, W. R., Chandrakasan, A. & Balakrishnan, H. Energy-efficient communication protocol for wireless microsensor networks. In Proceedings of the 33rd Annual Hawaii International Conference on System Sciences 10 (IEEE, 2000). 10.1109/HICSS.2000.926982. 44. Wentges, P. Weighted Dantzig-Wolfe decomposition for linear mixed-integer programming. Int. Trans. Oper. Res. 4 , 151–162. 10.1016/S0969-6016(97)00001-4 (1997). [ Google Scholar ] 45. Bragin, M. A. & Tucker, E. L. Surrogate “level-based” Lagrangian relaxation for mixed-integer linear programming. Sci. Rep. 12 , 22417. 10.1038/s41598-022-26264-1 (2022). [ DOI ] [ PMC free article ] [ PubMed ] [ Google Scholar ] Associated Data This section collects any data citations, data availability statements, or supplementary materials included in this article. Data Availability Statement The datasets generated and analyzed during the current study are available at Zenodo: (10.5281/zenodo.19135285). The code generated during the current study are publicly available in the GitHub repository: ( https://github.com/esraaclk64-collab/wsn-rln-article-gurobi-csharp -). It is also archived at Zenodo: (10.5281/zenodo.19135285). The code generated during the current study are publicly available in the GitHub repository: ( https://github.com/esraaclk64-collab/wsn-rln-article-gurobi-csharp - ). It is also archived at Zenodo: (10.5281/zenodo.19135285). Articles from Scientific Reports are provided here courtesy of Nature Publishing Group ACTIONS View on publisher site PDF (6.9 MB) Cite Collections Permalink PERMALINK Copy RESOURCES Similar articles Cited by other articles Links to NCBI Databases Cite Copy Download .nbib .nbib Format: AMA APA MLA NLM Add to Collections Create a new collection Add to an existing collection Name your collection * Choose a collection Unable to load your collection due to an error Please try again Add Cancel Follow NCBI NCBI on X (formerly known as Twitter) NCBI on Facebook NCBI on LinkedIn NCBI on GitHub NCBI RSS feed Connect with NLM NLM on X (formerly known as Twitter) NLM on Facebook NLM on YouTube National Library of Medicine 8600 Rockville Pike Bethesda, MD 20894 Web Policies FOIA HHS Vulnerability Disclosure Help Accessibility Careers NLM NIH HHS USA.gov Back to Top