I. INTRODUCTION
WIRELESS sensor networks (WSN) have been a promising technology trend in the last decade. A smart sensor node that is capable of sensing data, processing information, and communicating is in demand for different applications such as environmental monitoring, security surveillance, threat detection, smart agriculture monitoring, natural disaster warning systems, etc. There are two types of WSN, i.e., a heterogeneous WSN that is composed of different types of sensor nodes and a homogeneous WSN that has the same type of sensor nodes. Sensor nodes are usually deployed in harsh environments, where they stay at fixed locations. However, in order to enhance network performances such as coverage, connectivity, and robustness, mobile nodes, which are movable nodes, can be deployed. Depending on the sensing model, the WSN is classified as a directional WSN or an omnidirectional WSN. For directional WSN, a sensor node can detect a particular direction, usually represented as a cone. The omnidirectional node can detect in all directions with some sensing radius, which is often modeled by a circle or a sphere.
The most fundamental problem in WSN is the coverage problem; that is, trying to maximize the coverage area of a given area of interest with a minimum number of sensor nodes. There are several factors that relate to coverage, i.e., network connectivity and network lifetime. Network connectivity refers to the capability of routing information from sensor nodes to a sink node [1]. If the sensed data cannot reach the sink node, then there is no benefit of coverage. Similarly, because the energy stored in sensor nodes is limited, being able to maintain coverage requires an energy-efficient scheme. In general, there are two approaches to solving the coverage problem in WSN. The first is based on deployment technique, and the second is based on metaheuristic algorithms. WSN deployment can be classified as either random or deterministic. Deterministic deployment methods try to precompute the sensors’ positions to accomplish the desired outcomes.
There are various deployment techniques for WSN coverage. Abidin et al. [2] proposed a virtual force algorithm to make decisions on sensor positions and the direction of each sensor node. The drawback of the algorithm is that it is complex, and the sink node requires high processing power. Al-turjman et al. [3] applied a grid-based technique to determine the locations of the sensor nodes on different shapes such as rectangular, triangular, and hexagon. There is some work that is based on computational geometry, such as Voronoi-based algorithms [4], [5]. Gupta et al. [6] presented a genetic algorithm to provide an optimal solution for Kconnectivity relay node positioning. The results illustrated that the genetic algorithm is superior to the greedy algorithm. Gupta et al. [7] applied a genetic algorithm to solve a node placement problem in target-based wireless sensor networks. The authors in [8] proposed a hybrid algorithm that is based on a gradient method and a simulated annealing approach to solve blanket and barrier coverage problems. Particle swarm optimization (PSO) technique is applied to solve a heterogeneous sensor deployment in three-dimensional space in [9], where the objectives are to maximize the network lifetime and coverage. A more thorough survey on deployment techniques in WSN can be found in [1].
Another challenge in the WSN research problem is a routing problem, in which the flow of data from sensor nodes to sink nodes is determined with the objective of minimizing energy consumption and maximizing the network lifetime. For this work, we will only consider the routing protocols in the network layer, which are responsible for network topology control and transmission plans. Much work has been proposed to address these problems, which we can categorize as flat networks, hierarchical networks, and location-based networks. In flat protocols, the sink node sends queries to a particular region and waits for the data from sensor nodes to be broadcast. The first flat network protocol is SPIN (Sensor Protocols for Information via Negotiation) [10], which information among sensors is disseminated in order to conserve energy consumption. Ye et al. [11] proposed a minimum cost forwarding algorithm (MCFA) based on a cost field approach to find the optimal cost from sensor nodes to sink. Schurgers and Srivastava [12] presented a gradient-based routing (GBR) based on an energy histogram with different data dissemination techniques to reduce energy consumption. In the work of Shah and Rabaey [13], an energy-aware routing (EAR) protocol is proposed to enhance network lifetime. A sub-optimal path based on probability is chosen so that the energy dissipation is more balanced. In general, flat network routing consumes more energy because the sensor node has to transmit the data to the sink node regardless of the distance between them.
Unlike flat routing, hierarchical routing segregates the network into multiple clusters, with each cluster composed of a cluster head (CH) and member nodes in order to minimize the communication distance. Generally, it consists of two phases, i.e., a setup phase in which cluster head node selection is performed and a steady state phase in which network routing is calculated. The most classical hierarchical based routing protocol is the low energy adaptive clustering hierarchy (LEACH) protocol [
14]. In this protocol, a specific number of cluster heads are selected at random to evenly distribute the load among nodes. Data fusion processes have also been integrated in order to reduce the transmitted information. Asvial et al. [
15] extended the LEACH protocol by dividing the region for cluster head selection. This approach improves the distribution of the cluster heads over the region. Lindsey and Raghavendra [
16] presented power-efficient gathering in the sensor information systems (PEGASIS) protocol, which is an improvement over LEACH. The protocol forms a chain connecting each sensor node with the closet node until reaching the sink node in a greedy fashion. After that, there are a number of LEACH-based protocols in the literature. Examples of such work are [
17]–[
22]. Various protocols are based on multi-hop LEACH, aiming to improve energy efficiency [
23]–[
26]. More details on energy-aware wireless sensor network routing protocols can be found in [
27].
Location-based routing protocols use information about the location of nodes provided by some localization techniques such as received signal strength (RSSI), link quality indicators (LQI) or the global positioning system (GPS). Examples of location-based routing algorithms are [28]–[30]. Another energy-saving technique commonly applied to WSN is sleep/wake-up schemes [31]. The basic concept of sleep/wakeup protocols is to schedule the wireless sensor node into a sleep mode during the inactive period and a wake-up mode during the active period, i.e., when it is receiving and transmitting data. Duty cycle adjustment and topology control can be used to implement this scheme. The duty cycle scheme turns off the sensor node most of the time and wakes it up when needed. However, this can lead to data latency problems [32]. The topology control technique determines the state of each node as an active mode or an inactive (sleep) mode [33].
Some of the work utilizes an optimization-based routing approach. Ke et al. [34] proposed a nonlinear programming method to solve a relay node selection problem. Elhabyan et al. [35] formulated a multi-objective optimization to address the clustering and routing problems. The optimization problem is then solved by multi-objective evolutionary algorithms (MOEA). Several studies are based on genetic algorithms. The authors in [36] present a genetic algorithm to determine the cluster heads in the LEACH-C routing protocols. Liu and Ravishankar [37] proposed an adaptive protocol based on LEACH to search for optimal cluster heads. A genetic algorithm based energy efficient clusters (GABEEC) protocol is proposed in [38] to maximize the network lifetime. In this work [39], a hybrid optimization model based on the cuckoo search algorithm and rider optimization algorithm is proposed to select the cluster heads, aiming to minimize the energy consumption. Mehta and Saxena [40] presented a multi-objective-based sailfish optimizer (SFO) for routing and clustering problems. The objectives are to minimize energy consumption and reduce the number of dead nodes in the network. It should be noted that genetic algorithms are metaheuristics that often provide local optimal solutions, i.e., not the global optimal solution.
Most of the existing work in this area is designed for twodimensional networks, which might not be applicable to threedimensional networks in the real world. Only a little work has been done to address the WSN problems in a 3D environment. To solve the deployment of sensors in 3D terrain, Temel et al. [
41] proposed a cat swarm optimization with a wavelet transform. The Bresenham’s line of sight is adopted to provide constraints on sensing models in 3D terrain. Pan et al. [
42] addresses the 3-D node coverage problem of WSN using a meta-heuristic approach called the Black Hole Algorithm. Examples of the studies on a clustering routing problem in a 3D environment are [
43]–[
45]. In [
46], an adaptive clustering energy-optimization routing protocol for 3D WSN is proposed. The work is also considered an unreliable channel in the network. In this work, we address the energy-optimization routing problem in a 3D environment. Our work is based on the work of Thammawichai et al. [
47], in which a UAV network is considered. Here, we assume that there is a single target area of coverage where nodes are randomly deployed in threedimensional terrain. The nodes are static, that is, at a fixed location within the ROI. Our network is a cluster-based multihop WSN with multiple sink nodes. Unlike all others in the literature, which only try to solve for optimal clusters, our work also optimally solves for the connections among nodes in the network with a realistic channel model. Moreover, we are the first to combine clustering and sleep/wake protocols into our energy-saving schemes. Specifically, this paper proposes a 3D WSN topology control algorithm using a mathematical optimization method. The objectives are to guarantee Kconnectivity for each sink node and minimize the total power consumption in order to maximize the network lifetime. The main contributions of this paper are as follows:
1) An optimal multi-hop self-organized network topology control and node scheduling strategy is proposed for 3D WSN. The objectives are to minimize energy consumption and maximize the network lifetime. The WSN dynamic is represented by a state vector of node energy levels. The control inputs are the communication link matrix and the energy consumption at each decision round.
2) The scheme combines two energy-saving techniques, i.e., clustering and sleep/wake-up protocols at the network level, to reduce energy consumption. Precisely, at each decision round, the algorithm decides on the optimal number of wake-up nodes and their routing to guarantee K-connectives at each sink node with minimum energy consumption.
3) Our formulation is a mixed integer linear programming. The solutions obtained are global optimal, which is a benchmark for all heuristic algorithms. Moreover, our scheme is adaptive and scalable since the problem is formulated as an optimal control problem. Signifying that the model parameters can be easily updated with changes in state variables and environment as time progresses.
4) Though the number of variables grows nonlinearly as the number of nodes increases, the computational effort to solve the problem is rather practical due to the linearity of the proposed model. The rest of the paper is organized as follows. Section II provides definitions, assumptions and related problem setup. Section III introduces the dynamic model and constraints. Section IV discusses the simulation results. Lastly, Section V summarises this research and suggests future work.
II. PROBLEM SETUP
A. Definitions
A homogeneous WSN refers to a wireless sensor network that has the same type of sensor nodes, i.e., has the same sensing, storage, processing, power consumption, and communication protocol. A sensor node refers to a node that senses data in the region of interest (ROI).
A relay node is a node that relay its data to another node.
An aggregator node refers to a node that receives data from other nodes, then aggregates the data with its own data.
Redundant nodes refers to nodes in the network that are not active at the time for the purpose of redundancy. A sink node refers to node that accumulates the sensed data from other nodes to be used by the user.
K-connectivity means that the sink node is connected to a minimum of K sensor nodes. In other words, there are at least K connections between sensor nodes and each sink node. K-connectivity is directly related to the WSN’s performance.
Network lifetime defines the time until the Kconnectivity between sensor nodes and sink nodes cannot be satisfied. This is also considered one of the WSN performance metrics.
B. Assumptions
We assume that nodes in our network are composed of two types, i.e., sensor nodes and sink nodes. All nodes except sink nodes are homogeneous and can act as a sensor node, a redundant node, and an aggregator node at the same time. However, we do not consider data fusion, i.e., nodes will only act as relay nodes. Sink nodes have unlimited energy.
C. Communication Model
In this study, we adapt from the work of [
41], in which the sensing model is a function of distance between sensor node and environment conditions. In particular, the communication model is adopted from the binary sensing model. We assume that nodes are omnidirectional. Node i can communicate with node j if the distance between them is within the predefined communication range
[TeX:] $$c_r$$ and is not blocked by any obstacles. They cannot communicate otherwise. If
[TeX:] $$d_{i,j}$$ denotes the threedimensional Euclidean distance between nodes i and j and
[TeX:] $${LOS}_{i j} \in\{0,1\}$$ is a binary variable representing a line of sight between two nodes, the binary communication model can be expressed as follows:
Note that the line of sight LOS can be calculated with the adopted version of Bresenham algorithm, which has been widely used in computer graphics for line drawing on 2-D surfaces [
48].
D. Energy Consumption Model
The energy consumption of a WSN node is consumed by three terms: sensing energy, receiving energy, and transmitting energy. We assume that the sensing energy of one unit of data is a constant denoted by [TeX:] $$e_s \text {. }$$ The receiving energy of one unit of data [TeX:] $$e_r \text {. }$$ is also a constant. For the transmitting energy, we adopt a free space model of a wireless channel, which depends on the transmission distance d [49]. Hence, the transmitting energy consumption of transmitting one unit of data from node i to node j is as follows:
where [TeX:] $$e_{\mathrm{elec}}$$ is the circuit loss energy, [TeX:] $$\epsilon_{f s}$$ is the energy consumed by RF amplifier in the free space model, and [TeX:] $$d_{i j}$$ is the three-dimensional Euclidean distance between nodes i and j.
III. WSN DYNAMIC MODEL WITH CONSTRAINTS
Let
[TeX:] $$N:=\{1, \cdots, n\}$$ denote the set of sensor nodes in the network, where n is the total number of sensor nodes. Let
[TeX:] $$S:=\{1, \cdots, s\}$$ denote the set of sink nodes, where s is the total number of sink nodes in the network. Let node 0 represent the origin node that connects to every sensor node in the network. Let
[TeX:] $$N^{+}:=\{0\} \cup N$$ be the set of sensor nodes, including the origin node. It is worth noting that our network topology is not fully connected. Only links between sensor nodes are fully connected, while the links from the origin node to sensor nodes and the links from sensor nodes to sink nodes are directional graphs. Fig. 1 illustrates an example of our network topology at one decision round, where dashed lines represent active links. Notice that not all of the nodes are active due to the sleep/wake-up scheduling protocol.
WSN Topology when filled nodes and red arrows are the active nodes and active lines (X—Sink node, A—Relay nodes and S—Sensor nodes).
A. Communication Constraints
Let [TeX:] $$C:=\left[c_{i j}\right]$$ denotes the communication link matrix between node i and node j with a size of [TeX:] $$\{N \cup S\} \times N^{+}$$ That is, [TeX:] $$c_{i j}=1$$ if node j transmits data to node i for all [TeX:] $$i \in\{N \cup S\}, j \in N^{+} \text {. }$$ Note that sink nodes cannot transmit data to any other nodes, and the origin node cannot receive data from other nodes. The communication link is subject to
where (3) states that the communication link is a binary variable. The constraint (4) guarantees the K-connectivity for each sink node. The constraint (5) prohibits the selfcommunication of sensor nodes. The constraint (6) enforces that there is no communication link between nodes if the distance between them exceeds the communication range or the line of sight is occluded. These can be implemented as inequality constraints as follows:
where m and M is sufficiently small and big positive numbers, respectively. Let
[TeX:] $$D_{i j}$$ be 1 if
[TeX:] $$d_{i j} \leq c_r$$ and 0 otherwise.
[TeX:] $$D_{i j} \wedge L O S_{i j}$$ denote the logical AND operation of
[TeX:] $$D_{i j} \text{ and } L O S_{i j}.$$ Clearly, suppose
[TeX:] $$D_{i j} \wedge L O S_{i j}=1$$ then (6) is true if and only if
[TeX:] $$c_{i j}=1 \text{ or } 1.$$ Suppose
[TeX:] $$D_{i j} \wedge L O S_{i j}=0$$ then (6) is true if and only if
[TeX:] $$c_{i j}=0.$$ The constraint (7) imposes a conservation of data with the node, i.e., the summation of data in equals the summation of data out.
B. Energy Constraints
The total energy usage by node i during the time interval is composed of sensing energy, receiving energy, and transmitting energy. The sensing and receiving of energy are assumed to be constant. Let L denote the length of sensing data at a time (bits). Thus, the sensing and receiving energy consumed by node i within the time interval are
where
[TeX:] $$c_{i 0}$$ represents the connection between the origin node and node i. The transmitting energy is a function of the distance between nodes in 3D terrains, as described in Section II-D. Therefore, the transmitting energy consumed by node i within the time interval is
Let
[TeX:] $$e_i$$ be energy stored in node i. Each sensor node i in the network is subjected to
where constraint (13) defines
[TeX:] $$E_i$$ as the total energy consumed by node i during the time interval for sensing, receiving and transmitting. The constraint (14) assures that the energy usage will not exceed the current energy of the node.
C. WSN Dynamic Model
Let k denote the kth decision at time interval [TeX:] $$\left[t_k, t_{k+1}\right]$$ where [TeX:] $$t_{k+1}-t_k=h .$$ The WSN state space model X and the control input u at decision round k are defined as
where E(k) defined as a vector of the energy consumption of all sensor nodes at decision round kth, i.e,
[TeX:] $$\left[E_1(k) ; E_2(k), \cdots, E_n(k)\right..$$ Also, notice that all variables in previous sections can be considered as a function of k. The state update equation is given by
D. Objective Function
For this work, our objective is to minimize energy consumption in order to maximize the network lifetime. To achieve that, we consider two objective functions: the total energy consumption
[TeX:] $$f_1:=\sum_{i=1}^n E_i$$ and the deviation of the remaining energy of each node from the average remaining energy
[TeX:] $$f_2:=\sum_{i=1}^n\left|\left(e_i-E_i\right)-\bar{e}\right|,$$ where
[TeX:] $$\bar{e}$$ is the average remaining energy of all sensor nodes. It can be seen that our second objective function
[TeX:] $$f_2$$ is nonlinear, which can be reformulated as a linear function by introducing new variables and constraints [
50] as follows:
Then our new linear objective function is
Clearly, the new objective function [TeX:] $$\hat{f}_2$$ is the sum of positive and negative values of the absolute. It also should be noted that the solution obtained by solving the optimization problem with the objective function [TeX:] $$f_2$$ is the same as with the objective function [TeX:] $$\hat{f}_2$$. Therefore, the complexity of the optimization problem can be greatly reduced from nonlinear to linear.
E. Optimal Control Problem
To summarise, the WSN scheduling problem with Kconnectivity in 3D terrains can be formulated as the following optimal control problem: Given n sensor nodes and s sink nodes, at each decision round k, determine the nodes schedule and the communication links that solves
It is worth noting that our optimization problem is a mixedinteger linear programming (MILP) as our objective function and constraints are linear but some of the decision variables are integers. MILP can be solved by commercial software packages such as CPLEX [51], GUROBI [52], MATLAB Optimization Toolbox [53] and non-commercial software packages such as SCIP [54] and SYMPHONY [55].
IV. SIMULATION AND RESULT DISCUSSIONS
A. Simulation Setup
To validate the proposed scheme, our MILP is compared with the well-known multi-hop LEACH-based clustering protocol [25] in terms of energy consumption and network lifetime. The compared protocol is described in detail in Section IV-B. The proposed method is implemented in MATLAB [56] and solved by the MATLAB Optimization Toolbox.
For each simulation, sensor nodes, sink nodes, and an origin node are randomly distributed within a random [TeX:] $$256 \times 256 \mathrm{~m}^2$$ 3D terrain with a maximum height of 17.1 meters and an average height of 4.65 meters, as can be seen in Fig. 2. The total number of sensor nodes n varies from 50 to 100. The number of sink nodes s varies from 1 to 5. As stated in our assumption, we assume that sink nodes have unlimited energy. All sensor nodes are the same, i.e., the communication and sensing models as well as the initial energy. Other simulation parameters are shown in Table I.
256-by-256-meter 3D terrain and sensor nodes (id number is in red).
B. Multi-hop LEACH Protocol
The multi-hop LEACH is an improved version of the classical LEACH. At each decision round, a cluster head is randomly selected. If the selected cluster head cannot connect to any sink node, i.e., its path is blocked by terrain or it is out of communication range, then the data is transmitted to the nearest available cluster head. This process is repeated until the number of selected nodes (nodes that are able to transmit or relay data to a sink node) meets the K-connectivity constraints. In the event that there is an insufficient number of selected nodes, the routine will jump to the next round and begin to randomize the cluster head nodes. The full details of this algorithm can be found in [25] and the algorithm steps are illustrated in Algorithm 1.
C. Simulation Results and Discussions
In this section, we demonstrate the capabilities of our MILP. To do so, we assume fifty sensor nodes are distributed randomly in a 256-by-256-meter 3D terrain. Three sink nodes are pre-located at the locations (192,130,16.7271), (50,100,6.2081), (150,50,2.0214). The objective function is to minimize [TeX:] $$f_1+\hat{f}_2 .$$ The number of guaranteed K-connectivity is set to 12 per sink node. The sensor nodes initially have 1 J of energy. At each decision round, the algorithm computes the optimal communication links between sensor nodes and sink nodes to guarantee that each sink node will have at least 12 sensor nodes to connect to. The algorithm ends when there is no solution. For this scenario, the algorithm runs for a total of 890 rounds. Fig. 3 shows examples of optimal multi-hop network topologies generated by our MILP at different time steps, that is, 0, 50, 500, and 800. Here we display the terrain as a contour plot, where blue square boxes are sink nodes and blue circles are sensor nodes. The orange arrow lines represent the communication links between nodes. The numbers over the lines designate the number of transmitting packets. As can be seen in the simulation, the network topology obtained from our algorithm is adaptive to the current information at each decision round of the network, i.e., the remaining energy levels of the remaining nodes.
WSN Network for 50 sensor nodes and 3 sink nodes.
Fig. 4 exhibits an example of node scheduling from the simulation, where an active node is set to one and a sleep node is set to zero at each time step. Note that we only showed the sleep and wake-up schedules of nodes 1, 10, 20, 30, and 50. As can be seen in Fig. 4a, node 10 is frequently active throughout the simulation. This is because node 10 is placed near the sink node (at the middle left), meaning that it will be cheaper to route from this node. Now let us consider the remaining energy plot in Fig. 4b. It can be observed that there are some nodes that cannot be used due to the terrain blocking the communication path (nodes 15 and 45). Nodes that are closest to the sink will deplete energy faster than the others. It is also worth noting that the remaining active nodes have balanced energy levels as a result of our objective function, which seeks to minimize the variance in remaining energy among nodes.
Node scheduling and energy plots
Next, we experiment on test #2 by varying the number of sensor nodes from 50 to 100 nodes with a step size of 10 to observe the performance metric, i.e., the network lifetime. We fix the terrain and place one sink node at the highest location on the map. The number of K-connectivity is set to 70% of the total number of sensor nodes in all cases. Fig. 5 presents the network lifetime plots and the optimal objective value plots for different numbers of sensor nodes. It can be seen that, for this particular terrain, the case with 60 sensor nodes provides the longest network lifetime. Further increasing the number of nodes does not improve the lifetime of the network. Fig. 5b suggests that the objective value increases as the number of sensor nodes increases. It also shows rapid growth near the end of the simulation. This happens because the nearer sensor nodes die out, causing the optimizer to choose a further node, leading to extreme energy consumption.
Test #2: n = 50 − 100, s = 1,K = 70% of n.
To further analyze our proposed method, we run the simulations of test #3 for different numbers of sink nodes s and test #4 for varying the k-connectivity percentages with three objective functions. Specifically, we fix the number of sensor nodes n to 50 nodes, vary the number of sink nodes s from 1 through 5, and the k-connectivity from 50%–90% of n. The terrain is the same as before, and the locations of five sink nodes are fixed for all simulations. The results are illustrated in Figures 6 and 7. It is obvious that the network lifetime decreases as the K-connectivity constraint increases, as shown in Fig. 6. On the other hand, placing more sink nodes in the area will prolong the network lifetime, as displayed in Fig. 7. This is due to the shorter communication distance between a node and the sink node, hence the lesser transmitting energy usage. The multi-objective function of minimizing the total energy and balancing energy [TeX:] $$(f_1+\hat{f}_2 .)$$ achieves a longer network lifetime than the others in most cases. The objective of minimizing total energy performs worst in all cases, meaning that balancing energy consumption among nodes should be considered in designing routing schemes. Finally, the graphs suggest that there is an optimal number of sensors and an optimal K-connectivity value for maximizing network lifetime. However, this is not the objective of this study.
Test #3: Network lifetime vs K-connectivity, n = 50.
Test #4: Network lifetime vs Number of sink nodes, n = 50.
Next, we present the performance comparisons of our MILP with the multi-hop LEACH. In this comparison, both algorithms are applied to the same terrain when there is only one sink node located at (192, 130, 16.7271). All sensor nodes’ locations remain the same as in Fig. 2. Both algorithms aim to maximize the number of transmission rounds with guaranteed K-connectivity.
Fig. 8 shows the performance comparison between MILP and multi-hop LEACH. In this comparison, the K-connectivity is varied from 0.5 to 0.9, and the maximum number of transmissions is determined when there are no more solutions for the K-connectivity. In Fig. 8a, the blue dot line is the result of multi-hop LEACH, while the red yellow-dot line is the result of MILP. The multi-hop LEACH can reach 764, 599, 477, 380, and 228 rounds of transmissions for K-connectivity of 0.5, 0.6, 0.7, 0.8, and 0.9, respectively. The MILP algorithm can improve the performance by increasing the network lifetime to 1,060, 839, 647, 475, and 294 transmission rounds for K-connectivity of 0.5, 0.6, 0.7, 0.8, and 0.9, respectively. It can be seen in Fig. 8b that the network lifetime of MILP is significantly improved over the multi-hop LEACH for all Kconnectivity cases, with at least 25% for 0.8 K-connectivity. The improvement maxes out at 0.45% for a 0.7 K-connectivity case. This evidence proves that the MILP provides significant potential for WSN technology and further development. The explanation for these results is that the MILP optimally determines the topology according to the energy balance objective function instead of randomly choosing cluster heads as in the multi-hop LEACH.
Performance comparison between MILP and multi-hop LEACH.
In Fig. 9, the remaining energy of each node after the final transmission round for the case of 0.7 K-connectivity is shown. The red bars represent the energy of each node in the MILP algorithm, while the blue bars represent the energy in the multi-hop LEACH algorithm after the final transmission rounds, which are rounds 647 and 477, respectively. In this figure, the energy of nodes 15, 45, and 47 remains the same as the initial energy of one joule. This is because these three nodes cannot connect to other nodes on the network because the transmission line is blocked by the rough terrain. The MILP has five dead nodes with node ids of 6, 17, 25, 32, and 50. The multi-hop LEACH algorithm has six dead nodes, which are node ids: 6, 17, 25, 32, 40, and 50. From this figure, it can be inferred that the MILP can balance the energy consumption of each node throughout the simulations better than the multi-hop LEACH algorithm. As a result, the network can extend the transmission round by 35%.
Remaining energy of each node after the final transmission round (rounds: 647 for MILP and 477 for Multi-hop LEACH).
Lastly, we demonstrate the robustness of our proposed method by comparing our MILP with the multi-hop LEACH. In this comparison, both algorithms aim to maximize the number of transmission rounds with guaranteed K-connectivity. The maximum number of transmissions per round, i.e., a network lifetime, is determined when there is no solution to the topology control problem with K-connectivity constraints. Both algorithms are applied to three different terrains. The [TeX:] $$256 \times 256 \text { meter}^2$$ terrains are randomly generated with heights varying between 0 - 20 meters, as shown in Fig. 10.
Three randomly generated terrains for comparison of MILP and multihop LEACH performance.
For this comparison, the simulation is run for 30 rounds (ten for each terrain × three) for each K-connectivity and each algorithm. The total is 150 rounds for each algorithm (five Kconnectivity values). For each round, all 50 sensor nodes are randomly located over the terrain. These locations are used for both algorithms in one simulation run. Then, for the next round, the sensor node locations are random again. On the other hand, a sink node is manually selected by choosing the highest point around the center area of each terrain.
The simulations have demonstrated that the MILP substantially improves the network lifetime over the multi-hop LEACH in every case. The performance gains for each individual case vary from 3 to 198%. The comparison of the maximum number of transmissions is shown in Fig. 11. In this figure, the blue bars are the results of MILP, while the red bars are the results of multi-hop LEACH. For each bar, the middle line is the average value of the maximum number of transmissions, while the top and bottom lines are the maximum and minimum of the maximum number of transmissions for each K-connectivity from all three terrains with 30 rounds of random node locations.
Performance comparison between MILP and multi-hop LEACH.
For MILP, the average maximum number of transmission rounds is 839.06, 676.40, 548.40, 432.86, and 292.4 for k = 0.5 – 0.9, respectively. Whereas the average maximum number of transmissions for the multi-hop LEACH are 635, 494.66, 382.53, 295.53, and 191.13 for k = 0.5 – 0.9, respectively. Here, it can be seen that the average performance increases are 31.50, 36.31, 45.77, 49.80 and 61.34 percent for k = 0.5 – 0.9, respectively, and the overall increase for all cases is 44.94 percent.
V. CONCLUSIONS
This paper considers an energy-efficient WSN routeing problem in 3D terrain. The MILP, with the objective of minimizing energy consumption and maximizing network lifetime, is formulated as an optimal control problem. Our network topology is capable of self-organization; that is, the optimal number of active nodes and routing paths is automatically determined at each decision round. Energy balance and sleep/wake-up schemes are adopted to prolong the network lifetime. Simulation results illustrated that the MILP algorithm proposed in this study has shown promising performance over the notable multi-hop LEACH protocol, with an improvement of at least 25% for all cases, reaching a maximum of 45%. Furthermore, it is proven that the objective of balancing energy consumption among nodes achieves a longer network lifetime than that of minimizing total energy in general. For future work, one can extend the approach to address the heterogeneous WSN routing protocol. Another is to consider a more realistic communication channel model.