Abstract: Due to the environment of coal mine underground is poor, need to establish a stable and reliable network topology quickly during building the monitoring network and the topology must has reconfigurability, connectivity and reliability. For the above request, the topology control algorithm for wireless sensor network based on the PID of self-adapt hierarchical genetic (SAHGA-PID) in the coal mine underground was proposed. Based on the adaptive genetic algorithm, introduced hierarchical search strategy, divided the solution space into two-layers and improved the optimization efficiency. This algorithm combined biological intelligence algorithm to closed-loop control theory, overcame the shortcoming of slow convergence and instability of the existing topology control algorithm and improved the energy efficiency and convergence rate. The simulations and results show that, this algorithm can achieve the goal of optimizing the topology control quickly and effectively.
INTRODUCTION
Topology control is one of the core issues in the wireless sensor network research (Zhang et al., 2007). The basic problem of network is that ensures connectivity between all nodes. But, the way of wireless communication and the complexity of the working environment make wireless sensor network to face greater challenges than traditional network in the network connectivity. In the wire network, when the communication medium (cable, routers, etc.) has been deployed, the structure type of the network will not be changed and the communication will not be affected by outside interference. Wireless sensor network needs to build the network structure by itself. So, some tasks are simple in the wire network, but very difficult in the wireless network. Wireless communication is interfered easily by the environment, especially the low-power wireless communication between nodes. Therefore, it is importance and arduousness to ensure and maintain the network connectivity.
Topology control locates under-layer position in the protocol stack (Akyildiz et al., 2002), belongs to network layer. The network layer has two tasks, topology control and protocol plan. The topology control is the foundation and prerequisite of protocol plan (Yang et al., 2007). The other important role of topology control is maintains topology or rebuild topology.
In recent years, a lot of researchers have designed different topology control algorithm. An optimal fault-tolerant topology control algorithm with three mixed integer programming formulations was presented by Moraes et al. (2009); A fair and energy efficient topology control algorithm based on two-dimensional random distribution with weighted relaying regions proposed by Dargie et al. (2009); The topology control method for the wireless sensor network with vast intensity constraint was discussed by Yu et al.(2010). MTCP topology control algorithm by transmitting information with shared broadcast tree built in the network was designed by Wieselthier et al. (2000). The polynomial time algorithm for finding minimum energy k node-disjoint paths and making sure that the k-point communication between the source node and the target node was put forward by Srinivas and Modiano (2003). A power saving technique with the distributed, randomized algorithm for maintaining topology with little energy was presented by Mahesh and Srivatsa (2006). A self-organizing fault-tolerant topology control protocol for guaranteeing k-connectivity and ensuring the bounded node degree was proposed by Wang et al. (2009). The discrete Particle Swarm topology algorithm for dealing the problem of degree-constrained minimum spanning tree was designed by You et al. (2009). The network performance based on different kinds of topology structure was researched by Gao et al. (2012).
This study based on the analysis of the existed topology control algorithm, proposes a new topology control optimization algorithm for the coal mine underground.
PID CONTROL AND SELF-ADAPTIVE HIERARCHICAL GENETIC ALGORITHM
PID control: PID controller has the advantages of structure simple, efficiency, setting convenient, robustness, etc. It has been the reliable technical solution and tool in industrial control process and is very broad and flexible in applications. According to the statistics, the PID controller has been used in more than 70% of the industrial process. PID control system is show as Fig. 1.
PID is a linear controller, it constitutes a control deviation(error(t)) with expect output(eout(t)) and actual output(yout(t)), as the Eq. 1:
| (1) |
error(t) is the input and gets the relation between input error(t) and output u(t):
| (2) |
The transfer function is:
| (3) |
KP, KI and KD expresses proportional coefficient, integration coefficient and differential coefficient, respectively. TI and TD are integral time constant and derivative time constant. In the different applications, need to set the parameters of KP, KI and KD.
Self-adaptive hierarchical genetic algorithm: The thought of self-adaptive hierarchical genetic algorithm is that, in the start, the population is evolved globally in the entire variable space with the genetic algorithm (initial operator), when the global optimization search reaches a certain level, the better individuals are used as new population and switches to optimization search of smaller area in local search gene segment with self-adaptive genetic operator, until gets the satisfactory solution. In the process of two layers evolution, adopts elites to keep the tactics. The best individual of each generation is reserved to next generation unconditionally, makes sure that the best individual gene get best utilization.
Dispersion based on the fitness value of evolutionary population: When the global optimization search gets a certain stage, the difference of individual fitness value will become smaller and smaller. The global optimization search is difficult to increase the fitness value of the population at this moment and the efficiency of evolution decreased. Therefore, the evolution must be switched to local search from global search.
Define:
| (4) |
where, δ(t) is the fitness dispersion. When δ(t) = Δ(Δ is the dispersion threshold), the individual fitness values have little difference in the global evolution, play little role for the individuals and the population must be optimized from global to local. The best individual in the global evolution is:
| (5) |
Gg is the terminate generation of global evolution.
The following are the steps of self-adaptive hierarchical genetic algorithm:
| Step 1: | Initialize the algorithm, determine algorithm control parameters |
| Step 2: | According to the initial population size, generate the initial populations in the global |
| Step 3: | Execute the genetic algorithm with adaptive operator(include elites to keep the tactics) |
| Step 4: | Evaluate the evolution individual with the fitness value of population individuals |
| Step 5: | Judge the evolution individual, if satisfied the requirement of algorithm terminated, turn to 8, otherwise, turn to next step |
| Step 6: | Judged the evolution, if satisfy the stratified conditions, turn to next step, otherwise, generate the initial population with genetic operations and turn to setp 3 |
| Step 7: | Determine local search gene segments, generate the initial population in the local area and turn to setp 3 |
| Step 8: | Get the best individual satisfied the algorithm requirements |
| Fig. 1: | Diagram of SAHGA-PID controller regulate power |
TOPOLOGY CONTROL ALGORITHM BASED ON SAHGE-PID
Energy consumption model of wireless sensor network: When a node sends n bits date to the other node, the distance is d, energy consumption is:
| (6) |
in which, dc can be calculated by the Eq. 7.
| (7) |
L is transmission loss, hr is the receiving antenna height, ht is the transmitting antenna height, λ is transmission signal wavelength.
And the energy consumption a node received n bits data is:
| (8) |
Set the energy consumption transmitted 1 bit data as:
| (9) |
For receiving signal, each node has a received threshold power pr-thresh, if bit rate is Rb, Pt is Pt = Etx-amp (n,d) Rb, set into Etx-amp (n, d)
| (10) |
According to actual situation, select the appropriate channel model, the received power Pr is:
| (11) |
Set Eq. 11 is equal to Pr-thresh, can get and εtwo-ray-amp:
| (12) |
| (13) |
Analysis of optimization algorithm based on self-adaptive hierarchical genetic pid: The algorithm flow is show as Fig. 2, in the initialization of power control, select the individuals enough as initial population at the sampling time I and calculate the value of individual fitness function. Through genetic algorithm, select the best individual as the PID parameters. This algorithm can get better result than traditional algorithms.
Firstly, encode the parameters, initialize a certain size population and each individual in the population is a possible solutions potentially. Secondly, calculate the individual fitness value with fitness function and control the regeneration operation with the fitness value, execute the crossover and mutation operations according to the probability. The population execute the genetic evolution, until satisfy the stratified condition, the better individuals from global optimization are used as new population and execute smaller area search in the local search gene segment, until obtain the satisfactory solution.
Selection and analysis of self-adaptive genetic operator: In the global search, selection operator without elitist strategy, but the fitness value transforms method based on adaptive strategy. In the initial stage of population evolution, the individuals with small fitness value may have greater fitness value by transforming. Therefore, the probability of individual inherited to the next generation is increased.
| Fig. 2: | Flow chart of SAHGA-PID algorithm |
The individuals with big fitness value, part of them with little role for improving may have smaller fitness value by transforming and the survival probability is decrease with the fitness. By this method, can increase the search area as possible, optimize in the entire space, reduce the probability fall into the local optimal value. At the same time, adopt elites to keep the tactics, select the best individual of each generation to next generation.
Crossover operator uses the closed crossing avoidance strategy, the thought is that, if the hamming distance of two individuals is large, the two individuals are selected as the cross parent, if not, selects the other individual. The lower limit of the hamming distance is changed with the evolution of population.
The ith and jth evolution individuals of Xu(t) are xi(u, t) and xj(u, t). If H(xi(u, t), xi(u, t))>ρ(t)H(Xu(t)), selects xi(u, t) and xj(u, t) as the parents wait for crossing; otherwise, selects xjo(u, t)∈Xu(t), jo = argmaxj∈{1,2þNu}, {H(xi(u, t), xj(u, t))} and use xjo (u, t) as the parent. In which, H(xi(u, t), xj(u, t)) and H(Xu(t)) is hamming distance from xi(u, t) to xj(u, t) and average hamming distance of population Xu(t). ρ(t) is the acting factor function, reflects the population evolution process.
When the crossover operation is running, if the hamming distance of two cross gene segment is 0, the operation can’t produce new individual. At this moment, need the method to select new cross point as follows (Gong et al., 2007).
xi(u, t), xj(u, t) is the parents individuals of crossover operation, c is the cross point, Seg(xic1(u, t)), Seg(xjc1(u, t)) is th gene of xi(u, t) and xj(u, t) since point c, Seg(xic2(u, t)), Seg(xjc2(u, t)) is after point c.
If H (Seg(xic1(u, t), Seg(xjc1(u, t))) = 0, c is:
Mutation operator uses the adaptive single point mutation strategy, the selected individual evolves with single point mutation and the mutation probability is relative with population evolution ability and individual fitness. If the population evolution ability is weak or the individual fitness value is small, the mutation probability is great. This method can maintain the diversity of the evolutionary population, protect the superior individuals and improve the search ability.
Defined:
| Fig. 3: | Flow chart of SAHGA-PID power control algorithm |
Du(t) is the evolution ability of Xu(t), Du(t)∈[0,1), xi(u, t) is mutated according to the probability as follows:
In which, μ∈(0, 1) is the factor for adjusting the population evolution ability and individual fitness.
The PID control with self-adaptive hierarchical genetic algorithm has the advantages of adaptive control, hierarchical genetic and Conventional PID. Firstly, it has the characterized of identifying the control process parameters automatically and adapting process change. Secondly, it can overcome the locality of optimization and improve the convergence rate. Finally, it has the characterized of simple structure, robustness and high reliability.
Topology control algorithm: The execution flow of power optimization algorithm is show as Fig. 3 and the steps as follows:
| Step 1: | Initial the network, each node executes the initialization operation and sets the same initial transmission power. Each node broadcasts the node-information by cycle and the information contains the unique ID of the transmitting node in the network. And other all nodes received the information send the response information, contains the ID itself and sender’s ID. When there are nodes received the response information, adjust whether received the information is first time or not, generate a response for the first time and add the node ID to neighbor set. After a round, generate the initial network topology and take into the second step power control |
| Step 2: | Before sending the node-information of next cycle, counts the number of response information the node received in last round and the number is potential neighbors. If the potential neighbor number is greater or less than the thresholds, calls the adaptive hierarchical genetic PID algorithm for topology control. Through this algorithm, the transmitting power is more ideal |
| Step 3: | During the judgment, the neighbor list of each node is changed. When the node is discovered at first time and added to the list; when reduces the transmit power, there are some nodes need to leave and deletes them from the list. Corresponding to the two response events are JoinA(B) and LeaveA(B). After the operation of adding or deleting, needs to update the neighbor list |
| Step 4: | When the neighbor number of each node reaches the ideal range, the algorithm is stop |
SIMULATION ANALYSES AND PERFORMANCE EVALUATION
Simulation parameters and conditions: The simulation software of this algorithm is Matlab, the simulation area is a two-dimensional place of 1000x1000. There are 60 nodes deploy in the area equably with regional grid, generate the initial coverage. For the node, the maximum communication distance is 250, the power is 0.1W in the idle mode, 0.5W in the receive mode and the transmit power is changed with the algorithm. The wireless transmission model selects the free-space model or dual- path attenuation model according to the distance. The initial parameter of PID is Gaussian distribution taken (8.5, 1, 1) as the center and as the initial population of the genetic algorithm. The size of population is 50, use binary code, the operators is 0.9, 0.6 and 0.2 for selection, crossover and mutation. The termination condition is continuous loop 50 times or optimization efficiency is smaller than 0.008 continuously.
Contrast of topology control simulation: Figure 4 is the network topology of initialization and optimization with SAHGA-PID. The optimization improved the structural sparsity and node degree boundedness.
Figure 5a is total energy each node consumed in the process of network boot under the condition of 60 nodes distributed randomly. The node consumed a little energy by optimization, is 16% of boot energy consumption with LMA.
| Fig. 4(a-b): | Two topology structures of monitor network. The first is the topology without optimization, each node communicates with neighbors by the max power. The other is topology after optimized with the power control method (PID of Self-adaptive Hierarchical Genetic Algorithm), each node communicates with the neighbors by the optimum power |
| Fig. 5(a-c): | Performance comparisons of LMA and SAHGA-PID. Through the optimization with Local averaging algorithm and the PID-of self-adaptive Hierarchical Genetic Algorithm, (a) compared the total energy consumption of all nodes in the network, (b) compared the boot energy of different sizes and (c) compared the boot time of different sizes |
| Fig. 6(a-b): | This two figures show the network coverage and the algorithm’s output response, (a) is the network coverage rate change with the iterations, the coverage of entire network achieve to 92% rapidly, reflect network can cover the monitor area in short time and (b) is the output response of SAHGA-PID, the algorithm can reach the steady state rapidly |
Figure 5b is energy consumption of all nodes in the boot process under the conditions of different total nodes. The total energy consumption optimized is 30-40% of LMA. Figure 5c is the boot time-consuming comparison of optimized and LMA. The optimization can improve the boot time-consuming by 9.2-12.7%.
Figure 6a is the diagram of iteration and network connectivity, when in the fifth iteration, the entire network achieve 92% connectivity. And Fig. 6b is output response of improved PID algorithm, has good following performance.
CONCLUSION
This study analyzed the existing actual network, established the energy consumption model of wireless sensor network. To the special environment underground, select the different model and parameters. Introduced the control thought and artificial Intelligence to the optimization of network topology, proposed the topology control algorithm based on the PID of self-adapt hierarchical genetic. The network boot energy consumption is reduced by 70-84% and the boot time-consumption is improved by 9.2-12.7%. Through this algorithm, the node can get the ideal neighbor number and complete network topology faster, improve the convergence and energy efficiency of the algorithm.
ACKNOWLEDGMENT
Financial support for this works which provided by State Key Laboratory of Integrated Service Networks under grant ISN10-10.