Abstract: Clustering topology control and optimization is a basic issue in wireless sensor networks. In order to establish the hierarchical clustering topology to improve the performance of network topology, an immune system mechanism based clustering topology control algorithm is presented. It adopts the information processing mechanisms of biological immune system such as memory learning, feedback regulation and no center distributed autonomy to cluster the network. The work studies the definition of related immune issues in the scenario of wireless sensor networks, immune optimization of clustering topology control and theoretical analysis on the clustering performance. The theoretical analysis and simulations are carried out to analysis the performance of clustering compactness, energy consumption and the convergence of clustering algorithm. The algorithm is proved to be with better clustering performance when adopting the immune system mechanism into clustering topology establishment in wireless sensor networks. It overcomes the defect of traditional methods to the establishment of clustering topology and provides novel solutions to this issue.
INTRODUCTION
Wireless Sensor Networks (WSN) consist of a large number of micro sensor nodes with the abilities of perception, calculation and communication which are randomly deployed in the area for detection. Multi-hop self-organizing network system is formed by these nodes through wireless communication. Topology control is a basic issue, the study is to eliminate unnecessary communication link between the nodes and to form a data forwarding optimal topology by power control and backbone node selection under the precondition of coverage and connectivity of the nodes. It is the core to establish the hierarchical clustering topology when establishing the transmission routing. This will directly affect the transmission performance of the routing (Tuah et al., 2012).
For the characteristics of Ad hoc network with no center, dynamic topology, source restriction on calculation, transmission and energy, as well as the unpredictability of the working scenario especially brought by vibration and electromagnetic interference, the network often meets the failures of nodes or links which seriously affect the stability and reliability of topology in a network. Stable network topology should have the characteristics of scalability and dynamic adaptability but not being based on the fixed topology (Schaffer et al., 2012). Many challenging issues are presented for wireless sensor networks in the aspects of the basic theory and engineering technology of topology establishment and optimization. Therefore, it is greatly significant to establish the robust adaptive network topology for improving self-organizing ability, adaptability and robustness of network (Kumar et al., 2011).
Biological immune system has the information processing mechanisms such as memory learning, feedback regulation and no-center distributed autonomy (Yan, 2009). Artificial immune system, based on the biological immune theory, has the basic immune methods including immune recognition, immune learning, immune memory and clonal selection. It provides no teachers learning and self-organization mechanism. Therefore, it has the characteristics of open, distributed, dynamic and robustness, etc. (Liu et al., 2010; Gong et al., 2009). Biological immune system has the striking similarity with the distributed and self-organizing wireless sensor networks. Both are to maintain the system stability in the changing scenario. The characteristics and working mechanism of the biological immune system inspire researchers to adopt its idea, principle, structure and algorithm to solve the issue of topology control. This becomes a research direction to study on the mechanism of the biological immune system based clustering topology control in wireless sensor networks in recent years.
Much attention is attracted to the mechanism of the immune system based clustering topology control. However, the work is in the initial stage at present and needs further study. Some foundational researches have been done on this subject. Chen Yongjun establishes frequency control mathematical model and controlling method of minimum energy consumption inspired by the artificial immune theory (Chen et al., 2010). Salmon presented collaborative monitoring and intrusion detection mechanism inspired by the immune system. Li Qiao presented the immune intrusion detection mechanism based on the tree topology (Salmon et al., 2013). Wang Yaqi presented the clustering topology evolution model with the function of fault tolerance based on immune mechanism (Wang and Yang, 2012). Lim applied immune mechanism to diagnose and repair the failures of nodes or links in order to improve the stability. Tatiana Bokareva, etc. presented the fault-tolerant structure SASHA which is based on the biological immune mechanism (Bokareva et al., 2005). Amir Jabbari applied the theory of clonal selection, immune affinity and immune network to establish the network model by simulating self-learning, self-organization, memory and information processing mechanism in the biological immune system or nerve immune system (Jabbari and. Lang, 2010; Atakan and Akan, 2006).
For characteristics of dynamic topology affecting the key performance of network, mechanism of immune system based clustering topology control algorithm is presented to give the overall optimization on the hierarchical clustering topology control. The main contribution of this study includes definitions of immune issues, optimization of immune clustering topology, theoretical analysis and simulation test, etc.
MECHANISM OF IMMUNE SYSTEM BASED CLUSTERING TOPOLOGY CONTROL ALGORITHM
Methodology: Firstly ordinary nodes are randomly selected as the initial clusters by the probability which names the initial antibodies. It adopts the distance factor to form the initial antibody population. Then it calculates the affinity of antibody and antigen by the affinity function defined by the nodes’ energy and distance. Some excellent antibodies are selected into the memory according to the threshold value to do the variation. It recalculates the affinity and outputs the optimal antibody solution by the terminating condition. Finally, it forms the clustering topology with the good performance of clustering compactness as well as giving consideration to the energy factor.
Results: Problems in the scenario of wireless sensor networks are defined such as affinity, antibody memory, etc. An immune system mechanism based clustering algorithm is presented and details are given. Through the theoretical analysis and simulations on indicators of clustering compactness, algorithm convergence and optimization of energy consumption, algorithm is proved to be with better clustering performance when adopting the mechanism of immune system into clustering in wireless sensor networks.
Mechanism of immune system: Biological immune system adopts the mechanisms of self-recognition, mutual stimulation and restriction to constitute a dynamic balance network according to the basic immune methods such as immune recognition, immune learning, immune memory and clonal selection, etc. Biological immune system is a highly distributed, safe, efficient and adaptive learning system with hierarchical topology. It has good robustness and high complexity due to the information processing mechanism such as self-learning, feedback regulation and no-center distributed autonomy. Artificial immune system, based on the biological immune theory, has the basic immune methods including immune recognition, immune learning, immune memory and clonal selection. It provides no teachers learning and self-organization mechanism. So it has the characteristics of open, distributed, dynamic and robustness, etc., (Yan, 2009; Liu et al., 2010; Gong et al., 2009). These can overcome the defect of traditional methods to the establishment of clustering topology and provide novel solutions to the issues.
Problem definitions
Antibody: Defined as clustering nodes in wireless sensor networks, namely
the solution to the problem.
Antigen: Defined as the sensor nodes randomly deployed in the network, namely the problems needing to be solved.
Antigen recognition: For the issues of clustering topology optimization in the network, antigen is correspond to each node in the network, the antibody is correspond to the clustering node, so the antigen recognition is defined as the process that the clustering node exchanges information with its neighbor nodes within the power coverage.
Initial antibody populations: A number of average nodes are randomly selected as the clustering nodes and forms the initial antibody population. Each clustering node has its location and energy information.
Affinity: Affinity reflects the matching degree between the antigen and antibody or between the antibody and antibody. Greater the affinity value is, greater the antibody matches the antigen. The affinity function is defined as follows:
| (1) |
where, η+γ = 1
d(i, j) is the Euclidean distance from node Ni, to node Nj. Affinity function is related to the node’s energy and distance factor. Energy factor is defined as the ratio of the current node’s energy and the average of all nodes’ energy in a cluster. The distance factor is defined as the ratio of the average of the sum of the distance from each node to the clustering nodes and the distance of the current node to the clustering nodes. Farther the distance to the clustering node is, lower node energy is, lower the affinity value is. Affinity value reflects the inspiration of a node joining into a cluster:
| • | Encoding: Natural number is selected as the coding method for node’s coding |
| • | Antibody memory: It selects the antibodies with high affinity values into the memory as the candidates for optimal clustering nodes |
Algorithm steps:
| Step 1: | Initialize the parameters, set the basic parameters of immune algorithm | ||
| Step 2: | Antigen recognition. Antigen recognition reflects the communication process between the clustering node and its neighbor nodes within the power coverage | ||
| Step 3: | Establish the initial antibody population. The p average nodes are randomly selected as the initial clustering nodes by the probability, namely the initial antibodies. It calculates the distance from the nodes to the clustering node itself within its power coverage. The node which is nearer to the clustering node is to be selected as a cluster so as form the initial antibody population, namely: | ||
| (2) |
| Step 4: | Fitness calculation. It uses the defined affinity function to calculate the affinity of the antibody and antigen |
| Step 5: | Memory generation. Clustering nodes which have: |
| are selected into memory as candidates for the optimal antibody | |
| Step 6: | Generate new antibody population by variation. According to the calculation of affinity between antibody and antigen, antibodies with affinity value being higher than the set threshold are selected into the next iteration. New antibody populations are generated by the variation of antibody gene. Nodes in the network are coding in natural number, e.g., i is the natural number code of node Ni, iε(1, 2,...n). It adopts the variation rules in Eq. 3 to mutate the antibodies in the memory: |
| (3) |
| where, r is the natural number randomly generated in [1, n]. So new antibody population is formed by new mutated antibodies and the former antibodies in the memory. It adopts the rules NiεCLj if min {d(i, j), I = 1, 2..., n, j = 1, 2,..., n} to form new antibody population, then it calculates f’ (i, j) and: |
| by the affinity function. If: | |
| turn to step 5; Otherwise go to step 7 | |
| Step 7: | Set termination condition and output the optimal solution. When meeting the condition of iteration n and: |
| it stops iteration and output the optimal solution, otherwise it goes to step 4 | |
| Step 8: | Confirm the clustering. The antibodies in the final memory library are selected as the clustering nodes and exchange packets with the member nodes to confirm the clustering |
THEORETICAL ANALYSIS AND SIMULATION TEST
Performance analysis
Clustering compactness: Compactness and alienation are adopted to evaluate
the clustering performance of the network. Compactness reflects the minor sum
of the distance between clustering node and member nodes. Alienation reflects
the distance from one cluster to another. Compactness of a cluster is calculated
by:
Lemma 1: Mechanism of immune system based clustering in wireless sensor networks has better clustering effect, namely:
Proof: Because:
When η→0, It has:
Thus the affinity value is only related to the distance between the current average node and clustering node. For the kth (k = 1, 2,..., k) iteration clustering it has:
where:
represents the sum of in-cluster distance of the optimal m clusters in the kth memory in the kth iteration. These M clusters will be kept in next iteration clustering:
represents the sum of in-cluster distance of N-M clusters in the (k+1)th current iteration. When entering:
iteration clustering, it has. According to the mechanism of immune algorithm, it only selects some clusters with better performance into the next iteration, it has:
and
Performance of energy consumption: Energy consumption model of data transmission is defined as:
| (4) |
where, ETX(k, d) is energy consumption of sending packets, ETX(k) is energy consumption of receiving packets, Eelec is the circuit energy consumption of per bit packet transmission. Parameters εfs and εamp are the coefficients of transmission amplifier.
For the ordinary node i sending k bits packets, the residual energy is as follows:
| (5) |
Because:
It has:
| (6) |
| (7) |
From Eq. 5 and 7, the residual energy of member nodes in one cluster is directly related to the distance between itself and the clustering node. It also has close relationship with affinityfunction value from Eq. 7. Greater the distance is, less the affinity function value is, smaller the residual energy is.
For the clustering node in the jth cluster, giving the consideration on receiving the packets from member node and transmitting packets to neighbor clustering nodes, the residual energy is:
| (8) |
Suppose that transmission distance between clustering nodes dj>d0.
Owing to
| (9) |
From Eq. 9, residual energy of the jth cluster after one round packets transmission is related with the transmission distance d1 between current clustering node and the neighbor, as well as the distance:
between the clustering node and its members.
The residual energy of the whole network after one round packets transmission is:
| (10) |
From Eq. 10, the residual energy of all nodes in the network after one round packets transmission is related to two factors. Clustering node’s transmission distance:
and network clustering performance namely the clustering compactness:
The former one is directly related to clustering topology based on the transmission routing.
Mechanism of immune system based network clustering has achieved the optimal clustering pattern, namely:
It has energy consumption balance among the clusters, the difference between the maximum and minimum cluster energy consumption can be reduced to the smallest range, namely:
| (11) |
Performance optimization and convergence: It has been proved that the immune algorithm has good performance of convergence. Mechanism of immune system based clustering in wireless sensor networks needs good convergence. Good convergence reflects good calculation performance of algorithm and is of great significance to energy restrained wireless sensor networks. The convergence of immune system based clustering can be calculated by Lemma 2.
Lemma 2:
| (12) |
Proof: In Lemma 2, r is the operation rounds of the network. It has:
represents distance sum of clusters which has higher value than the setting threshold when network working at a certain round. These corresponding clusters, namely the excellent antibody population, will be kept in the memory for the next iteration. According to the algorithm’ principle, it has:
Thus:
The compactness of network clustering based on the mechanism of immune system reflects that greater r is, better compactness of clusters which will finally converge to a fixed value.
Simulation analysis
Assumptions: (1) Network node is static and each node’ location is
known, (2) The initial state of the nodes is equal, each has the same parameters
and initial energy, (3) The network node in full duplex work mode and (4) The
nodes are randomly uniformly distributed in the rectangular area.
Communication model is based on the clustering topology. Parameters are set as follows: Probability p = 0.15, the weight coefficients w1 = 0.3, w2 = 0.5, w3 = 0.2, η = 0.4, γ = 0.6. The initial energy of the node is set with 1000 nJ. The model of the energy consumption and parameters εamp, Efuse, Eelec, Etx and Erx refer to the reference Lindsey et al. (2002). The size of source packet is set with 2000 bits. Fault node is defined as the node which energy consumption achieves the initial threshold value δ = 0.3 Eini. Parameter Eini represents the nodes’ initial energy. Lifetime of the network is defined as the period form the network beginning to run until the moment that 10% of the nodes in the network run out of energy. The sensor data are acquired and transmitted periodically. The node reconstructs the received coded fragments into the source packets at a certain interval Δt.
Result: Compactness of immune clustering and performance of energy consumption are analyzed in the simulations. Clustering algorithm based on immune mechanism is more uniform and optimal from the clustering result. It also reflects good convergence and more residual energy during the process of clustering than any other two methods.
Compactness of immune clustering:
| • | Clustering effect: Simulation is based on clustering topology of network according to the immune mechanism. Figure 1 shows that 150 nodes are randomly deployed in the area [200, 200]. The destination node is located in the right side of the area. Figure 2 shows the initial randomly selected clustering nodes which are not based on the immune mechanism. It adopts K-means algorithm to establish the clustering topology by distance factor. Figure 3 shows the clustering topology based on the immune mechanism by repeatedly antibody variations. From the comparison analysis of Fig. 2 and 3, clustering based on immune mechanism in Fig. 3 is more uniform and optimal |
| • | Clustering compactness The compactness value is calculated by: |
which defined as the sum of distance within a cluster, it reflects the compact performance within a cluster and discrete performance among the clusters:
represents the optimal clustering result. It is shown in Fig. 4
| Fig. 1: | Network constituted by 150 nodes randomly deployed in the area [200, 200] |
| Fig. 2: | Initial clustering topology not based on immune system mechanism |
| Fig. 3: | Optimized clustering topology based on immune system mechanism |
| Fig. 4: | Performance of clustering compactness when network runs to 50 times |
Figure 4 shows the variation tendency of clustering compactness of immune mechanism based network. The compactness values at each iteration round of antibody variation are calculated by:
From Fig. 4, it has greater values at the initial stage of clustering. After optimization by immune mechanism, the value decreases dramatically and finally converges to a fixed value. Its variation tendency reflects the performance of convergence and optimization of immune clustering.
Performance of energy consumption: The residual energy of all nodes in the network is calculated at different operation rounds. Now the comparison is done among following three methods: (1) Mechanism of immune system based clustering topology control algorithm presented in this study, (2) Method in the reference Chen et al. (2010) and (3) Method in the reference Wang and Yang (2012). Simulation on the performance of energy consumption is as shown in Fig. 5.
Figure 5 shows the comparison of average residual energy of all the nodes, including the clustering nodes and members among these three methods.
| Fig. 5: | Comparison of efficiency of energy consumption among three methods when network runs at 1000-2000 times |
It does the comparison when network runs at 1000-2000 times. From Fig. 5, the average residual energy of the nodes among three methods appears not to be much different. At any operations rounds during 1000-2000 times when network runs, Method 1 presented in this study has more residual energy than any other methods.
CONCLUSION
It is significant to establish the hierarchy clustering topology when establishing the transmission routing in wireless sensor networks. This will directly affect the transmission performance of the routing. Clustering topology control and optimization are the basic issues in wireless sensor networks. Biological immune system has the information processing mechanisms such as memory learning, feedback regulation and no memory distributed autonomy. Therefore, it provides a novel approach to the topology control for wireless sensor networks. The work of mechanism of immune system based clustering topology control algorithm presented in this study mainly includes the definition of immune parameters, optimization of clustering topology control and theoretical analysis on the clustering performance which includes clustering compactness, convergence and optimization of energy consumption, as well as the simulations. Simulation result shows that it has better clustering performance when adopting the mechanism of immune system into clustering in wireless sensor networks.
ACKNOWLEDGMENTS
This study was supported by National Science and Technology Major Projects of China (No. 2009ZX07528-003-09), Specialized Research Fund for the Doctoral Program of Higher Education of China (No. 20100191110037), Chongqing Key Project of Science and Technology of China (No. CSCT2010AA2036), Chongqing Key Project of Science and Technology of China (No. cstc2012gg-yyjs40008), Science and Technology Project of Chongqing City Board of Education Committee (KJ131117), Wanzhou Science and Technology Planning Projects of China (No. 201203037) and ([2010]23), Youth Project of Chongqing Three Gorges University of China (No.12QN14) and Science and Technology Projects of Chongqing Three Gorges University ([2011]52).