Abstract
Wireless Sensor Networks (WSNs) are widely-used. The nodes in traditional WSNs are usually fixed, which means that the nodes around the base stations will bear more communication load. This uneven load will cause quick exhaustion of network energy and the phenomenon of “Energy Hole”. In recent years, researchers have been trying to solve this problem by introducing moving nodes that are considered as the sink nodes (Sink) to collect the data in WSNs. A moving node can be moving tramcars, moving cars on bridge or autonomous underwater vehicles, etc. However, in reality, the moving nodes have certain constrains on both space and capacity. In this paper, the network problems such as the node energy, the sink movement distance upper limit and the communication loss, are formally modeled as linear programming models. Thus, the optimal sink moving path can be determined by solving these models. Experiments show that the models can be applied to small and medium size WSNs with acceptable running time. However, the running time becomes extremely long when the network size is scaled up.
Introduction
The Wireless Sensor Network technology is one of the most important emerging technologies in the 21th century and one of the key technologies in the next generation networks [1–3]. The Wireless Sensor Networks (WSNs) have integrated different technologies such as micro computer technology, distributed computing technology and modern network technology, etc. They mainly use various multi-functional and low-power micro sensors to realize the perception, data collection and real-time monitoring of monitored targets. The data is transmitted by the network nodes using the multi-hop relay topology through the embedded system information processing. The WSNs have the features such as limited node communication ability, limited energy, limited computing ability, variable network structure and high demand of instantaneity [4].
In recent years, researchers have introduced mobile sinks in the WSNs. The sink nodes collect the node data within the communication range while moving in the network, then fuse the data and send to the base station. The mobile sinks use single hop communication with the nodes to avoid the energy consumption of the nodes around the base station caused by multi-hop transmission. Meanwhile, the mobility of the sinks makes the communication unaffected among the nodes that have lost contact with the network. The mobile sink processor has high processing speed and larger capacity than the normal nodes. The single hop communication method between the sinks and the nodes can reduce the consumption of node energy. The sinks can serve as the communication mediation among the independent sub-networks. The WSNs with mobile sinks have obvious advantages in collecting data in the sparse network [5, 6]. For example, in non-urgent applications such as forest environment monitoring or hydrologic data monitoring, one collection every certain time is feasible. Energy conservation is the biggest optimization target of such sort of networks when the application time-delay is guaranteed. After collecting the data, the nodes will transmit the data to the mobile sink by single hop or multiple hops in real time. In [7, 8], the mobile sink has constructed the shortest path to access all the sensor nodes and conducted the data transmission communication with the sensor nodes within the range of one hop communication. This kind of problems can be solved in a way similar to the traveling salesman problems. The system has an ordinary real-time performance because of the mobile sink time-delay in the path. In references [9–11], the mobile sink has communicated directly with all sensor nodes. Since the mechanical movement speed of the sink is far lower than the optoelectronic signal transmission rate, it leads to large time delay. The number of the sensor nodes accessed directly by the sink is decreased by dividing the entire region into several sub-regions and setting the sink nodes in each sub-region.
The mobile sink can solve the problem of “Energy Hole” better than the other nodes but in actual application, a sink’s energy is not infinite. In particular, when a sink’s movement distance is limited, its moving path and its sojourn time in each node will determine the lifetime of the whole network. In this paper, the network problem such as node energy, sink movement distance upper limit and communication loss, are modeled formally as linear programming models, which implies that the optimal sink moving path can be determined by solving these models.
Problem description
In WSNs, the problem of sink movement distance limited path selection is about selecting a path for a sink starting from a base station, via several nodes, then going back to the base station, and maximizing the lifetime of the network. The constraint is that the total movement distance of a mobile sink should not exceed the limit L for each round.
The optimization objectives of the optimal moving path are: 1) the movement distance of each round is less than or equal to the limit value L; 2) the system has the longest network lifetime based on object 1; 3) the algorithm execution time is not required.
This problem usually refers to several basic assumptions: A mobile sink moves at a constant speed and the movement distance has a linear proportional relationship with the time; Cache space of each node data is large enough to collect and send the data consecutively; Each node must and can only select one cache point as its objective; All nodes can communicate by single hop or multiple hop method; Each node sends data to its belonging cache point along the shortest path; Each node is the potential sojourn location of mobile sink and a sink will not stay at places other than nodes; The network lifetime is counted until the time of death of the first node in the network.
Network definition
An end-to-end communication network is defined as N (V, E) consisting of a series of nodes V and their connection edges E. Any node in the network can be accessed by other nodes and any two nodes can be connected via at most one directed edge. A directed edge is defined as e = (u, v) ∈ E, having two non-negative valued attributes D (e) and C (e), in which D (e) is its length and C (e) is the cost when passing the directed edge or any other desirable optimization scale.
Through cross permutation of nodes and edges, a path is defined as P (v0, v
k
) = v0, e1, v1, e2, v2, …, vk-1, e
k
, v
k
, in which e
i
= (vi-1, v
i
) ∈ E, (1 ≤ i ≤ k). A path can also be described as P (v0, v
k
) = {v0 → v1 → … → vk-1 → v
k
}. For a given source node s ∈ V and a destination node d ∈ V, p (s, d) = {P1, …, P
m
} is the set of all paths from s to d. The cost of path P
i
can be defined as in Equation (1):
Movement distance is defined as in Equation (2):
In the process of sink movement from one node to another, the node needs to store the collected data into its cache until a sink reaches to a new location and starts data collection. To avoid the inability of data collection caused by the small node data buffer, each time the movement distance of a sink between two locations should not exceed Rmax. Each time when a sink moves to a new location, it will reconstruct an access forwarding tree to each node and will stay at this location for a while. The reconstruction leads to extra energy consumption. In order to guarantee enough time for each node to transmit the data to the sink, the sojourn time of a sink at each new location should not be shorter than Tmin units of time.
v1, v2, … v k are defined as the access location (node) set of base station and t i is defined as the residence time at the node v i (1 ≤ i ≤ k).
Parameters and variables are defined in Table 1.
Definitions of model parameters and variables
The constraints are presented in Table 2.
Network model constraints
Constraint (3) ensures that the total energy consumption by each sensor v j does not exceed IE; Equation (4) ensures the input and output balance of each node; Equations (5 and 6) mark the states of the sink starting from and returning to location v0; Equation (7) shows that there is at most one incoming edge into v j if v j is a sojourn location of the sink to avoid loop; constraint (8) ensures that the sojourn time of the sink at node v j is at least Tmin; constraint (9) ensures that the total movement distance of sink does not exceed L; and constraint (10) ensures that the distance of each movement in the path is not larger than Rmax. It can be seen that the optimal path problem of limited movement distance is a NP problem and a special case that assumes the sojourn time at a potential sojourn location.
The network lifetime with several constraints defined in Section 2, is in fact the sum of the sojourn time on each moving location. Therefore, the problem of optimized network lifetime is converted to the problem of the sink’s sojourn nodes and its sojourn time at each node. The optimization objectives can be formalized into solving the following objective functions:
Based on the above optimized objective functions, the problem can be modeled as a mixed linear programming model. The longest network lifetime on the constraints can be obtained by solving the mixed linear programming model. In the network N (V, E) model, let the variable matrix f indicates the parameters in Table 1 and matrices A, G and B represent the network model constraints in Table 2. Figure 1 illustrates the internal structures of matrices A, f, G and B. The converted network model is a mixed integer linear programming model and its solution provides the optimal moving path of the sink node.
Internal structures of matrices A, f, G and B.
The parameters and matrices of converted linear programming model are as follows:
Optimization objective: Maximize
Constraint: Distance (P i ) = ∑e∈P i D (e) ≤ L
Relationship matrix
Figure 1 illustrates the internal structures of matrices A, f, G and B, where the lines from 5n + 5 to 5n + 5 + RNum are the loop detection lines and the values are calculated dynamically by each node’s loop. More details are provided in Section 3.3.
Construction of relationship matrices
The constraints in Table 2 are formulated and modeled as a conditional matrix of linear programming model. The method of construction is presented as follows:
Constraint (7) is expressed as:
Constraint (8) is expressed as:
Constraint (9) is expressed as:
Constraint (10) is expressed as:
Constraint (11) is expressed as:
Constraint (12) is expressed as:
Constraint (13) is expressed as:
Constraint (14) is controlled through the upper limit value of the variables, where Lmax is the upper limit of sink movement distance; IE is the initial energy of each node; ec v is the energy consumption coefficient of node j in the spanning tree rooted at node i, with value proportional to the number of child nodes of j node; and D (i, j) is the distance between i and j. When the sink moves to each node v i , the node is considered as the root node to construct the data forwarding tree using the Breadth-First-Search. The number of child nodes of each node in T i tree is also calculated to determine the energy consumption of each node when the sink sojourns at v i .
Loop detection algorithm
In a common solving process, a potential loop may exist in a sink node’s moving path, which makes it impossible for the model to reach the global optimal solution. For this problem, the constraint strategy in [12] cannot be directly converted to relationship matrix that needs further manual verification. In order to solve this problem, a loop detection-aided algorithm is introduced in this paper. This algorithm can automatically detect and avoid the loop in a solving process by generating the constraints called by the linear programming algorithm.
Algorithm 1 iterates over each node. It starts from each node, accesses the adjacent nodes and generates multiple paths. It then records the path that can return to the starting point and stores them in the Road array. The Road array can be used to construct the expressions of A, B and G to avoid the loop. The ‘for’ loop from line 2 to line 25 constructs the iteration loop taking each node as the starting node. The ‘for’ loop from line 8 to line 22 realizes the selection for all potential next moving locations starting from the current node in a loop detection. The instructions from line 11 to line 16 add the nodes that meet the loop detection conditions at the end of the current row of the loop array and update the serial number of current row and column of the loop array.
The generated Road array is embodied in matrices A, B and G to avoid loops, as shown below, where Len (Road (i)) is the nonzero element number of the ith row of Road array.
Energy consumption model
First-order wireless communication model is used to calculate the consumed energy of transmitting or receiving l bits between the two nodes with distance of d. The energy consumption model is shown in Fig. 2. The energy consumptions of sending information and receiving information are calculated using Equations (16 and 17), respectively, where ETx-elec and ERx-elec are the energies consumed by sending and receiving 1 bit data, respectively. Their values are equal and can be uniformly represented by E
elec
. d is the distance between the sending and receiving nodes. d
toBS
is the distance between the cluster head and the base station. When d is less than d0, automatic space path assumption model is adopted and when d is larger than d0, multiple paths fading model is adopted. ξ
fs
and ξ
amp
are the energies of sending a unit data required by these two models’ power amplifiers.
First-order wireless energy consumption model.
In integer programming, it is called the pure integer programming or the full integer programming if all variables are restricted to be (nonnegative) integers; whereas, it is called the mixed integer programming if only one part of variables is restricted to be integer. The network in Section 3 contains connection variable sojourn time t i of each node and integer variables xi,j and y i , therefore, the network is a mixed integer linear programming problem. While solving this integer programming, if the feasible region is bounded, the optimal solution can be obtained by exhausting all the feasible integer combinations of variables and then comparing their objective function values. This method is feasible and effective for small-scale problems, where the variable number and the feasible integer combination number are small. For large-scale problems, the feasible integer combination number is large, which means the exhaustive method is inadvisable. Hence, in general, a feasible method to determine the optimal integer solution is merely checking a part of the feasible integer combinations, such as branch and bound method.
Branch and bound method is a widely-used algorithm for not only discrete and combinatorial optimization problems but also for general real valued problems. The advantages of branch and bound method are: reduction of calculation while guaranteeing the precision; elimination of a large number of nodes that are unlikely to exceed the known best values, thus finally obtaining the optimal solution of problems, i.e., the best value. The basic idea of branch and bound method is to search the space of all feasible solutions (limited number) of optimization problems with constraints. During the implementation of this algorithm, all the feasible solution spaces are segmented into smaller and smaller subsets (called branch) and the next lower bound or upper bound (called delimitation) is calculated for each solution value within each subset. After each branch, the subsets whose bounds exceed the known feasible solution value will not be further segmented. Therefore, many subsets of solution (i.e., nodes on search tree) will not be considered and thus the search scope is narrowed. This process will be conducted until a feasible solution is found. This feasible solution is not larger than the bound of any subset. Generally, the optimal solution is obtained using this algorithm. Like greedy algorithm, this algorithm is also used to design the solution algorithm for combinational optimization problems. The difference is that the branch and bound method explores in the entire solution space. The time complexity of the designed algorithm is higher than that of the greedy algorithm, but its advantage is similar to the exhaustion method that can guarantee to obtain the optimal solution of the problem. In addition, this algorithm is not blind exhaustive exploration, on the contrary, it can stop further exploration for those subsets that are unlikely to obtain the optimal solution (similar to the pruning in artificial intelligence) by bounding during the exploration. Thus, it has higher efficiency than the exhaustion method. Comprehensively, considering the operations of node sorting such as father node initialization, upper bound calculation, etc., the algorithm time and space complexities both in the worst case are O (n * 2 n ).
Branch and bound method can be used to solve pure integer or mixed integer programming problems. Due to its flexibility and easy implementation, it has become one of the most common methods to solve integer programming. Set the integer programming problem with maximization as A and its corresponding linear programming problem as B. Starting from solving problem B, if the optimal solution does not fit the integer condition of A, the optimal objective function of B must be the upper bound of the optimal objective function Z* of A, marked as Z-. And the objective function value of any feasible solution of A will be a lower bound Z- of Z*. Branch and bound method is just a method to segment the feasible region of B into sub-regions (called branch), then gradually decrease and increase Z-, to finally obtain Z*.
In accordance to parameter f and relationship matrices A, B and G based on the network modeling, the branch and bound method is used to obtain the optimal programming path and the sojourn time on each node of the optimal path. The matrices A, B and G take into account of loop in the path. All the potential loops are eliminated from the matrices.
Simulation and analysis
Simulation environment
The WSNs simulated in this paper consists of 20 to 400 nodes that are randomly distributed in a rectangular region with length 200 m and width 150 m. The transmission range of a node is Rmax = 35 m, and the initial energy IE is 50 Jules. The data collection rate of each node is set as r = 40 bits/s. In order to track additional information of energy consumption of nodes around the sink, initially the sink and the base station are both placed at (150, 100). The comparison relations of network key performance indexes are approximately similar to the situation when the sink and the base station are both located at (200, 75), middle of the right part. The energy consumption model in section 3.4 is used for the node transmission and energy. The experiment parameters are shown in Table 3.
Main parameters of the sensor network
Main parameters of the sensor network
Network lifetime of different scale networks with different upper limits
For this simulation, the network node number n is set as 15, 20 and 25, and the movement distance upper limit is set as 100, 150 and 200. The obtained simulation results of network lifetime, actual movement distance and execution time are shown in Table 4. Each value is the average value of five time continuous executions under the same network structure, which means that the randomness of data is eliminated. Table 4 shows that under different movement distance constraints, the network lifetime of the same scale network is different. The larger the movement distance upper limit is, the longer the network lifetime will be. Under the same movement distance constraints, the network lifetime decreases with increase in the network scale. The sink can sojourn more nodes with large movement distance upper limit. The nodes in different regions are regarded as neighbor nodes to balance the energy consumption of each node as data transit node. When the network is scaled up, the probability of each node as data transit node increases and the consumed energy to transmit data becomes larger than that of smaller network. Under the condition of unchanged consumed energy to transmit data, the entire energy consumption of nodes increases and the lifetime of nodes decreases slightly.
Experimental results
Experimental results
Figures 3–5 present the data in Table 4 in a more intuitive way. As it can be seen from them that when the sink movement distance upper limit is increased, the network lifetime, the actual movement distance and the execution time are also increased accordingly. In particular, the algorithm execution time is rapidly increased when the network is scaled up. When the number of network nodes exceeds 50, the algorithm execution time is particularly long. For example, when n = 25 and the longest movement distance is 200, the algorithm execution time reaches 397.86, which is 30.97 times of that when n = 20. When the number of network nodes increases to a certain amount, the algorithm execution time becomes too long. This is mainly because the algorithm needs to collect data globally to obtain the optimal solution. Meanwhile, constructing network access spanning tree on each passing node will also require a certain amount of time that will be accumulated and thus will lead to a slow execution speed when the number of nodes is large.
Trend of network lifetime under different longest movement distance constraints.
Trend of sink actual moving distance under different longest movement distance constraints.
Trend of algorithm execution time under different longest movement distance constraints.
Figure 6 and Table 5 indicate that when the sink movement distance upper limit L exceeds a certain value, it no longer affects the network lifetime. For example, when L = 250, the actual movement distance is 222.1977 and the network lifetime is 1.2055e+005. When L increases to 300 and 350, the actual sink movement distance and the network lifetime are unchanged. This is mainly because the network lifetime is restricted by multiple factors and movement distance is only one of them. Other conditions such as the initial energy of each node, the deployment density and the distribution location of nodes in network are also the key factors to restrict the network lifetime. Hence, when L is large enough, its effect on the network generated lifetime can be ignored and other constraints will determine the network lifetime.
Results of different sink movement distance upper limits when n = 25.
Results of different movement distance upper limit constraints when n = 25
The sink movement to new locations increases with increase in number of network nodes, and every movement requires reconstruction of access spanning tree. Thus, while solving the linear programming problems through modeling, the execution time is long and increases rapidly. The proposed model is suitable for finding the optimal path of moving sink with limited distance for small and medium scale WSNs. Further research is needed for large-scale WSNs.
In this paper, the authors have introduced a definition of communication network and have presented the network optimization objectives and constraints via conversion. The described problem has been converted into one mixed network integer linear programming by formalizing the optimization objectives into function variables of mixed programming model and converting the network constraints into constraint matrices of mixed programming model. The authors have provided detailed steps of using the branch and bound method to solve the proposed model. The analysis of experimental simulation results has shown that the network lifetime can be improved by increasing the movement distance upper limit. However, the execution time of mixed linear programming model increases rapidly when the network is scaled up. Hence, further research is required to obtain better optimized solutions.
Footnotes
Acknowledgments
This work is supported by the Natural Science Foundation (61370206), Natural Science Foundation of the Jiangsu Higher Education Institutions of China (Grant No. 16KJD510002).